JP4974508B2 - バスマスタ装置、バス調停装置及びバス調停方法 - Google Patents

Description

本発明は、複数のマスタが共有しているバスの使用権を調停するバスマスタ装置、バス調停装置及びバス調停方法に関するものである。

複数のマスタが共有のリソース（バス、メモリ）を使用する場合、そのリソースを時分割で使用することになる。このとき、どのマスタにリソースの使用権を与えるかを、ある一定のルール（マスタのリソース使用優先度）に従って調停（アービトレーション）する必要がある。従来から知られているアービトレーションスキームの中で最も代表的なものが以下のアービトレーションスキームである。

・ラウンドロビン
・固定優先度
・重み付き優先度
「ラウンドロビン」調停は、リソースの使用権を獲得したマスタの優先度を、次の調停時に最低レベルにすることにより全てのマスタを公平に扱うものである。この場合、マスタがバス使用権を獲得する度に優先度がリアルタイムに変更される。この調停方法の特徴は、全てのマスタに公平にリソース使用権を与えることができる点にある。しかし、相対的に要求帯域幅の大きいマスタの場合、その帯域幅を確保できなくなる可能性がある。

「固定優先度」調停は、各マスタの優先度を予めスタティックに決定するもので、要求帯域幅の大きいマスタや、低レイテンシでの動作を保証する必要のあるマスタに対して常に優先度を高く設定することができる。この調停方法の場合、必要帯域幅の大きいマスタ順に優先度を持たせることにより、優先度の高いマスタは充分に帯域幅を確保できる。しかし、優先度が低く設定されたマスタは、長時間リソースを使用できない不利を被ることになる。

これら「ラウンドロビン」と「固定優先度」のデメリットを解決する手段として知られる「重み付き優先度」は、マスタ毎に例えば「４：３：２：１」のように帯域割付比を与え、この比でリソースを割り付けられるように調停する方法である。この場合、１０回の調停のうち４回、３回、２回、１回の比で割り付けを行うことを期待している。具体的な制御方法は様々であるが、代表的な制御方法としては以下のような方法が挙げられる。

各マスタ毎に、使用権を獲得する度に使用権の獲得回数をカウントし、このカウント値と設定比が一致すると帯域幅を満たしたものとして他のマスタにバス使用権を譲る。具体的には、獲得回数のカウント値が設定比と一致したマスタは、他の全マスタのカウンタ値がそれぞれの設定値と一致するまで使用権を他のマスタに譲る処理を繰り返す。こうして全てのマスタのカウント値が設定値と同じになると、全マスタの獲得回数のカウント値をクリアする。これを繰り返すことによって設定された比でリソースを割り付ける。この場合、全てのマスタが常に使用要求を出している状況では、この比と一致した帯域幅での割り付けが可能となる。しかし、カウンタ値が小さいこともあり、各々のマスタによる使用要求の出し方によっては、特定のマスタだけが使用権を獲得してしまうといった状況が発生してしまう。

例えば、特許文献１には、基準より遅れているデバイスに対して、優先的にバスを割り当てるバス調停装置が記載されている。この特許文献１のバス調停装置は、この割り当てのために、各デバイスに要求されている転送レートに基づいたクロックで動作する基準カウンタと、実際に転送したデータ量を計測する転送データカウンタとを設ける。そして、バス調停時にこれら２つのカウンタの値を比較している。
特開平１０−２８９２０３号公報

上記のアービトレーション、特に重み付き優先度を拡張させたアービトレーションとして、要求帯域幅に対する実転送量をマスタ毎にカウントして、要求帯域幅を満たしているマスタの優先度を下げるという調停方法が提案されている。この方法の場合、要求帯域を大きく超えて特定のマスタがリソース使用権を独占することなく、各々のマスタの要求帯域に応じた調停が可能となる。また「重み付き優先度」のように相対的な比を設定するわけではなく、マスタ毎の要求値を直接設定可能である。但し、もし複数のマスタが要求帯域に達していない場合、ある特定のマスタ或はラウンドロビンによって、リソース使用権が決定されることになる。

この方法の場合、共有しているリソースへの要求帯域の合計が１００％を超えていない場合は、各マスタの要求帯域は満たされる。しかし、共有しているリソースへの要求帯域の合計が、ある一定期間１００％を超えた場合には、本当に優先すべきマスタに対してリソース使用権が与えられなくなる可能性がある。要求帯域の合計が１００％を超えた場合に優先されるべきマスタを動作前に決定できれば、この方法でも事足りると思われる。しかし、要求帯域の合計が１００％を越えた場合の各マスタの優先順位が予め設定できない場合は、各マスタの要求帯域を満足するような帯域の割り付けを行うことは困難であった。

本発明の目的は、上記従来技術の問題点を解決することにある。

本願発明の特徴は、複数のバスマスタが共通のリソースを取り合うバス構成において、各マスタのそれぞれの帯域幅の要求を満足できるバス使用権の割り当てを容易にする技術を提供することにある。

上記本願発明の特徴は、特許請求の範囲の独立項に記載の特徴の組み合わせにより達成され、従属項は更なる有利な具体例を規定するものである。また、この課題を解決するための手段は、本願発明の特徴を全て列挙しているものではない。

上記目的を達成するために本発明の一態様に係るバス調停装置は以下のような構成を備える。即ち、
各マスタのバス使用権の調停を行うバス調停装置であって、
各マスタが転送すべきデータのデータ量を設定するデータ量設定手段と、
各マスタによる前記データ量のデータ転送の転送期限を設定する転送期限設定手段と、
各マスタの前記転送期限までの残り時間を計時する計時手段と、
各マスタが転送すべきデータの残りデータ量を検知する残データ量検知手段と、
前記残り時間と前記残りデータ量とに基づいて、データ転送を開始しているマスタを含む複数のマスタのうち緊急度の高いデータ転送に対応するマスタに、優先してバス使用権を割り当てるバス調停手段と、を有することを特徴とする。

上記目的を達成するために本発明の一態様に係るバスマスタ装置は以下のような構成を備える。即ち、
バスアービタに転送要求信号を送出し、バスにアクセスするバスマスタ装置であって、
データ転送すべき期限までの残り時間を検知する残り時間検知手段と、
転送すべき残りデータ量を検知する残りデータ量検知手段と、
前記残り時間及び前記残りデータ量に基づいて前記転送要求信号の優先度を算出する優先度算出手段と、
前記優先度算出手段により算出した優先度をバスアービタに通知する通知手段と、
前記バスアービタからの許可に基づいて前記バスを介してデータ転送を開始する出力手段と、を有することを特徴とする。

上記目的を達成するために本発明の一態様に係るバス調停方法は以下のような工程を備える。即ち、
各マスタのバス使用権の調停を行うバス調停方法であって、
各マスタが転送すべきデータのデータ量を設定するデータ量設定工程と、
各マスタによる前記データ量のデータ転送の転送期限を設定する転送期限設定工程と、
各マスタの前記転送期限までの残り時間を計時する計時工程と、
各マスタが転送すべきデータの残りデータ量を検知する残データ量検知工程と、
前記残り時間と前記残りデータ量とに基づいて、データ転送を開始しているマスタを含む複数のマスタのうち緊急度の高いデータ転送に対応するマスタに、優先してバス使用権を割り当てるバス調停工程と、を有することを特徴とする。

本発明によれば、複数のバスマスタが共通のリソースを取り合うバス構成において、各マスタのそれぞれの帯域幅の要求を満足できるようにバス使用要求を適切にスケジューリングできる。

以下、添付図面を参照して本発明の好適な実施の形態を詳しく説明する。尚、以下の実施の形態は特許請求の範囲に係る本発明を限定するものでなく、また本実施の形態で説明されている特徴の組み合わせの全てが本発明の解決手段に必須のものとは限らない。

本実施の形態を説明する前に、上記で背景技術でとり挙げた「平均レート保証」の問題点を解決する一手法である「デッドライン保証」を説明する。

共有しているリソースへの要求帯域の合計が、その共有リソースの転送能力の１００％を超えている場合、個々のマスタのデッドラインまでの猶予を考慮した上で最適な調停を行う。これにより、アービタの設定として、マスタ間の相対的な要求帯域幅比を考慮してアービタを設定するのではなく、マスタ個々のパラメータ（保証期間、保証データ量）を与えるだけで、アービタがリアルタイムにデッドライン保証するのに最適な調停を行う。このデッドライン保証を行うアービタは、マスタ毎に保証期間、保証データ量というパラメータを与え、「各マスタが各々の保証期間内に保証データ量を転送し終える」ようにバス使用権を調停する。こうすることによって、マスタ毎に保証時間、保証データ数を設定するだけで、アービタがリアルタイムで、各マスタの要求帯域幅に対する不充足を計算する。これと同時に、デッドラインに対する緊急度を用いて、最適なバス使用権を調停する。その結果、各マスタのＱｏＳ（Quality of Service）を達成できるようになる。具体的には、調停回路は以下の計算を内部のカウンタ値を使って行う。
（１）保証期間内に保証データ量を転送し終えるのに必要な転送の緊急度。

マスタごとにデータ転送の緊急度を計算し、各マスタの緊急度の計算結果を評価値として比較し、評価値が最も大きいマスタにバス使用権を与える。この評価値が大きいことは、転送を完了するまでの残り時間が短いか、又は転送を完了するまでの残り転送データ量が多いことを意味している。この調停回路は、評価値が最も大きいマスタにバス使用の優先権を与えるように動作する。

［実施の形態１］
図１は、本発明の実施の形態１に係るバス調停装置（バスアービタ）の構成図である。このバス調停装置では、説明を間単にするために３個のマスタ０〜２（１４〜１６）と、１個のスレーブ（１７）が接続されているバスシステムを示しているが、本発明を実施するにあたり、これらマスタの数やスレーブの数には特に制限はない。

この実施の形態１では、マスタ１４〜１６のそれぞれが、バス１８を経由してスレーブ１７にデータを転送するバスシステムで示している。複数のマスタ１４〜１６が共通のバス１８を使用するため、これら複数のマスタ１４〜１６が同時にデータ転送を行うことができない。そのため、アービタ１０がバス１８の調停を行い、どのマスタにバス１８の使用権を与えるかを決定する。各マスタ１４〜１６は、バスの使用権要求信号１９をアービタ１０に対して発行する。これによりアービタ１０は、優先順位によって決定したマスタに対してバス使用許可信号２０を発行する。こうしてアービタ１０からバス使用権を得たマスタは、バス１８を占有してスレーブ１７との間でデータ転送を行う。

アービタ１０の調停部１３は、マスタからのバス権要求信号１９に応じて、要求のあったマスタに対して、どのマスタにバス使用許可を与えるか決定する。即ち、調停部１３は、優先順位に従って決定したマスタに対してバス使用許可信号２０を返すことによりマスタに対してバス使用許可を与える。この際、調停部１３はカウンタ部１２からのカウント値（評価値）に基づいて優先順位を決定する。カウンタ部１２は、各マスタごとに、転送時間カウンタと転送データ量カウンタを有している。転送時間カウンタは、各マスタごとに、そのデータ転送開始からの経過時間を計時する。転送データ量カウンタは、バス１８を監視し、各マスタごとに、そのデータ転送開始から転送されたデータ量を測定する。

この転送時間カウンタと、予め設定された要求転送時間とを比較することで、各マスタの残り転送時間を求める。更に、転送データ量カウンタと予め設定された転送要求データ量とから、残りの転送データ量を計算する。これら計算した残り転送時間と残りの転送データ量とに基づいて演算回路で演算して評価値を決定し、調停部１３に通知する。尚、各マスタの要求転送時間と転送要求データ量は、各マスタからの転送要求に先立って、各マスタによりアービタ１０に設定されているものとする。

また、カウンタ初期化部１１からのカウンタ初期化信号によって、転送時間カウンタと転送データ量カウンタを初期化する。カウンタ初期化部１１は、各マスタの転送開始タイミングを検知する手段を持ち、各マスタの転送開始タイミングに同期したカウンタ初期化信号をカウンタ部１２に出力する。転送開始タイミングを検知する手段としては、マスタからの転送開始通知信号による検知方法等が考えられる。

次に、カウンタ部１２の内部処理を図２を参照して説明する。

図２は、本実施の形態１に係るアービタ１０の動作を説明するタイミングチャートである。

カウンタ部１２は、各マスタごとに調停を行うための評価に用いるための評価値を計算する機能を有する。図２に示したのは、マスタ１個当たりの評価値を計算する方法を示している。

カウンタ部１２は、マスタごとの残り転送時間を計算するための、転送時間カウンタと、残り転送データ量を計算するための転送データ量カウンタを有する。これら転送時間カウンタと転送データ量カウンタは、転送開始トリガ２００によって初期化される。その後、転送時間カウンタは、２０１で示すように、１サイクルごとにカウントアップして転送開始からの経過時間を計測する。また転送データ量カウンタはバスを監視しており、２０３で示すように、該当するマスタのデータ転送が行われたタイミング（２０２で示す）でカウントアップして転送開始からの転送データ量を計測する。

転送開始トリガ（２００）からの要求転送時間（２０４）と要求転送データ量（２０５）は予め設定されている。この要求転送時間（２０４）と転送時間カウンタのカウント値（２０１）との差分により、残り転送時間（２０６）が求められる。また要求転送データ量（２０５）と転送データ量カウンタのカウント値（２０３）との差分から、残り転送データ量（２０７）が求められる。

これら残り転送時間（２０６）と残り転送データ量（２０７）に基づいて、演算回路で計算した評価値が２０８で示されている。この評価値（２０８）は、図２では、「残りデータ量／残り転送時間」の演算結果を評価値とした計算結果で示している。

尚、図２に示した、評価値を求めるためのカウンタ及び演算回路は、各マスタごとに実装されている。この各マスタの評価値は同時に調停部１３に出力される。これにより調停部１３は、その評価値が大きいマスタの優先順位を高く設定し、評価値が大きいマスタのバス権要求に対して優先的にバス使用許可を与えるように動作する。

図３は、マスタごとに計算した評価値を分かりやすく解説する図である。この図３では説明を簡単にするために、２つのマスタ１４，１５がそれぞれ同じ要求転送時間と転送要求データ量で、転送開始タイミングが異なる場合のデータ転送の様子を示している。

マスタ１４及び１５で示されている各三角形において、底辺が要求転送時間を表し、高さが要求転送データ量を示している。また三角形の傾きの部分が、デッドラインを保証するために必要な平均転送レートを示している。

いま時刻ｔにおける、各マスタの転送開始からの経過時間と転送済みデータ量を示す位置を、各三角形の内側に黒丸で示している。２つのマスタにおいて、要求されている平均転送レートは同じである。本実施の形態１では、各マスタごとに評価値を計算して評価値に応じてバス使用権を与えるように動作する。

図３においては、評価値を「残りデータ量／残り転送時間」で求めた場合、時間ｔにおける各マスタの評価値が３１，３２で表されている。即ち、点線３１はマスタ１４の評価値を示し、点線３２はマスタ１５の評価値を示している。図３の例では、マスタ１４の評価値がマスタ１５の評価値と比較して大きいため、マスタ１５の優先順位はマスタ１４よりも高く設定される。そして時間の経過とともに、或はデータ転送が行われることにより評価値が変化してゆく。しかし、マスタ１４とマスタ１５の評価値の大小関係が変わらない限り、これらマスタ１４と１５の優先順位は一定に保たれる。

図３に示す場合は、時刻ｔの時点でマスタ１４の優先順位が高く設定され、評価値の大小関係がかわらない限り、マスタ１４のバス権要求がある場合は、調停部１３はマスタ１４に連続してバス使用権を与え続けるように動作する。また評価値の大小関係が変化し、マスタ１５の評価値がマスタ１４の評価値よりも大きくなった場合は、調停部１３はマスタ１５に優先的にバス使用権を与えるように動作する。

以上説明したように本実施の形態１によれば、各マスタの動作状況に応じて優先順位を動的に切り替えることが可能であり、各マスタに対して適切な調停を行うことが可能となる。

［実施の形態２］
次に本発明の実施の形態２について説明する。この実施の形態２にバス調停装置の構成と動作の主要部は、前述の実施の形態１の図１及び図２と同じであるため、その説明を省略する。

前述の実施の形態１における残り転送時間、残り転送データ量に基づいて評価値を決定するのに加えて、この実施の形態２では、各マスタに固有の転送能力値を、予め各マスタ毎にパラメータとして与えておく。ここで、転送能力値は、そのマスタが単独でバスを占有したと仮定したときに達成可能な転送速度の平均値とする。

即ち、残り転送時間及び残りデータ転送量から下記の式（１）により、デッドタイムまでに残りデータの転送を完遂するのに必要な転送速度を求める。

（残りデータ転送量）／（残り転送時間） ...式（１）
そして、式（１）により求めた値を、マスタの転送能力で割ったものを新たなプライオリティ評価値として以下のように定義する。

（残りデータ量）／（残り転送時間）／（マスタの転送能力） ...式（２）
この式（２）は、ある一定の転送能力を持つマスタに対して課せられたデッドライン要求がどの程度厳しいものかを判断するための値である。この式（２）から導かれた値が大きいほど、デッドラインまでにデータ転送を終えるために、そのマスタに固有の転送能力に近い転送速度でのデータ転送が必要となることを意味する。また、値が「１」に到達したマスタは、要求速度がマスタの転送能力と一致していることになり、バスを占有できない限り、そのデータ転送要求を満たせないことを意味する。

カウンタ部１２は、各マスタ毎に、式（２）に基づいて、各マスタのバス使用緊急度を求める。

一方、調停部１３は、この評価値（緊急度）を大小比較し、評価値が大きいマスタに高い優先権を与えることでプライオリティを決定する。例えば、値が「０．１」であるマスタよりも「０．５」のマスタの方が転送を行う上で現時点での緊急度が高いと判断し、そのマスタに優先権を与える。

この評価値の算出と大小比較とをリアルタイムで実行することにより、精度の高いプライオリティ管理が可能となる。

残り転送時間と残り転送データ量、転送能力パラメータを演算回路で計算した値をマスタの評価値とする。

図４は、本発明の実施の形態２に係るアービタ１０による動作を説明するタイミングチャートである。図４において、「要求転送時間」から「残り転送データ量」までは、前述の実施の形態１の図２と同じである。

図４において、４０１は、前述の式（１）で得られる｛（残りデータ転送量）／（残り転送時間）｝の演算結果を示している。転送能力値４０２は、このマスタに対して予め与えられた値であり、ここでは「０．８」である。そして評価値４０３は、｛（残りデータ転送量）／（残り転送時間）｝の演算結果を、この転送能力値（０．８）で割ることにより得られる（式（２））。

図４に示した、評価値を求めるためのカウンタ、演算回路は、各マスタごとに実装されており、各マスタの評価値は同時に調停部１３に出力される。調停部１３は、評価値の大きいマスタの優先順位を高く設定し、評価値の大きいマスタのバス権要求に対してバス使用許可を与えるように動作する。

図５は、本実施の形態２において、各マスタごとに計算した評価値を分かりやすく解説する図である。

図５では説明を簡単にするために、２つのマスタ（マスタ０（１４），１（１５））がそれぞれ同時にデータ転送を開始し、同じ要求期間内にデッドライン保証することが期待されているとする。横軸は時間軸であり、ある時刻ｔにおいてデッドライン保証を完遂するのに必要な転送レート（残りデータ量／残り時間）は、マスタ０とマスタ１とで全く同じ値とする。且つ、マスタ０とマスタ１の転送能力のそれぞれが、直線の傾き３３，３４で表わされている。実際は、これら直線の傾き３３，３４（＝平均転送レート）は、パラメータとして予め設定されている。

図５では、マスタ０の転送能力がマスタ１の転送能力を上回っていることを表している。よって、上記式（２）で得られる評価値は、マスタ０よりもマスタ１の方が大きくなる。その結果、時刻ｔでは、マスタ１の優先度が高くなる。この緊急度の算出とバス使用権の割り付けをリアルタイムで行うことにより、その時点で最も負荷の重いマスタに対してバス使用権を与えることができる。特に非同期でバスアクセスを開始するマスタに対しても柔軟な対応が可能となる。

図６は、本実施の形態２に係るマスタ０と１の転送能力を説明する図である。この図６では、マスタ０の転送能力は、マスタ１の約３倍である。

以上説明したように実施の形態２によれば、各マスタによるデータ転送の調停に転送能力を加えることにより、よりマスタの特性に応じた精度の高いデッドライン保証が可能となる。

またマスタの転送能力を、平均転送レートという比較的シンプルで見積もりやすいパラメータとして与えても良い。

［実施の形態３］
図７は、本発明の実施の形態３に係るバスマスタ装置の構成を表すブロック図である。

このバスマスタ１００は、バススレーブＩ／Ｆ部１１０、転送時間レジスタ１１１、転送量レジスタ１１２、転送開始レジスタ１１３、転送能力レジスタ１１４、バスマスタＩ／Ｆ部１２０、バスマスタ制御部１２１、データ処理部１２２、転送要求度計算部１２３、残り転送時間レジスタ１２４、残り転送量レジスタ１２５を具備している。

図８は、実施の形態３に係るバスマスタ１００を用いたシステムの構成を表す概略ブロック図である。

このバスマスタシステム１００は、バス４０，ＣＰＵ４１、アービタ４２、バスマスタ４３〜４５、バススレーブ４６，４７を具備している。このうち、バスマスタ４３，４４，４５はそれぞれ図７のバスマスタ１００に相当している。

まず図７のバスマスタ１００の概要を説明する。バススレーブＩ／Ｆ部１１０は、バス０上のＣＰＵ（図８のＣＰＵ４１に相当）からのレジスタアクセスを受付けるインターフェースである。転送時間レジスタ１１１は、バスマスタ１００が行うデータ転送に要求される転送時間（即ち、転送開始から転送終了までの時間の最大値）を１μ秒単位で設定するレジスタである。転送量レジスタ１１２は、転送するデータの転送量をバイト単位で設定するレジスタである。またバスマスタ１００は、転送開始レジスタ１１３に「１」が書き込まれることによってデータ転送を開始し、このデータ転送が完了すると転送開始レジスタ１１３を自動的にクリアする。

転送能力レジスタ１１４は、バスマスタ１００の転送能力を設定する６ビットのレジスタである。バスマスタ１００が単独でデータ転送を行った場合（即ち、バスマスタ１００のみに連続してバス権許可が与えられ続けた場合）における平均転送能力を設定する（単位はワード／サイクル）。この転送能力レジスタ１１４の設定範囲は、「０．０１３２５（＝２ ^-5 ）」から「１（＝２ ⁰ ）」までである。これはハードウエア的には「１」を超える設定が可能であるが、１サイクルあたり１ワードを超えるデータ転送は、本実施の形態３に係るバスシステムでは不可能なため上限を「１」としている。

バスマスタＩ／Ｆ部１２０は、バス１０１上のバススレーブ（図８のバススレーブ４６又は４７に相当）と、後述するデータ処理部１２２との間のデータ転送を行うためのインターフェースである。バスマスタ制御部１２１は、バスマスタＩ／Ｆ部１２０、転送開始レジスタ１１３、後述の残り転送時間レジスタ１２４並びに残り転送量レジスタ１２５を制御する。データ処理部１２２は、転送データを生成又は受信する部分で、例えば画像処理を行うブロックや、外部との通信を行うインターフェースブロック等、バスマスタ１００に要求される機能によって異なる。

次に本実施の形態３に係るバスマスタ１００の詳細について説明する。

バス１０１上のＣＰＵ４１から転送開始レジスタ１１３に「１」が書き込まれると、バスマスタ制御部１２１は、残り転送時間レジスタ１２４及び残り転送量レジスタ１２５に対してロード信号をアサートする。これにより、転送時間レジスタ１１１の値が残り転送時間レジスタ１２４にコピーされると共に、転送量レジスタ１１２の値が残り転送量レジスタ１２５にコピーされる。その後、バスマスタ制御部１２１は、残り転送時間レジスタ１２４に対して、１μ秒ごとに時間減算信号をアサートする。また残り転送量レジスタ１２５に対しては、データ転送が行われる度に転送されたバイト数分のデータ転送量の減算信号をアサートする。例えば、本実施の形態３では、バス１０１における１ワードが４バイトである。このため、１ワードの転送が行われた場合は、転送量減算信号として「４」が、ハーフワード転送の場合には「２」が、バイト転送の場合には「１」がそれぞれアサートされる。そして残り転送量レジスタ１２５は、自身の値から転送量減算信号の値を減算する。

以上により、残り転送時間レジスタ１２４及び残り転送量レジスタ１２５の値が減算され、残り転送時間及び残り転送量の値が適切に更新される。

データ処理部１２２も、転送開始レジスタ１１３に「１」が書き込まれることによって起動される。データが送信或は受信可能になると、データ処理部１２２はバスマスタ制御部１２１に対してデータレディ信号をアサートする。このデータレディ信号のアサートを受けて、バスマスタ制御部１２１は、バス１０１上のアービタ（図８のアービタ４２に相当）に対して転送要求信号をアサートするようバスマスタＩ／Ｆ部１２０を制御する。

一方、転送要求度計算部１２３は、残り転送時間レジスタ１２４、残り転送量レジスタ１２５並びに転送能力レジスタ１１４の値に基づいて、データ転送の優先度を計算する。

本実施の形態３に係る転送要求度計算部１２３における計算は、上述の式（２）に対応する「（残り転送量レジスタ１２５の値／残り転送時間レジスタ１２４の値）／転送能力レジスタ１１４の値」である。この計算により、同一の残りデータ量に対しては、残り時間が少なくなるほど転送要求優先度が大きくなる。

一方、同一の残り時間に対しては、残りデータ量が多くなるほど転送要求優先度が大きくなる。更に、同一の「残りデータ量／残り時間」の値に対しては、転送能力の低いバスマスタほど転送要求優先度が大きくなる。バスマスタＩ／Ｆ部１２０はアービタ４２に対して、転送要求度計算部１２３における計算結果を転送要求優先度信号として出力する。この転送要求優先度信号のアサートタイミングは、転送要求信号のアサート開始と同一サイクルで、以降、転送が完了するまで値を保持する。

アービタ４２は、転送要求優先度信号の値がより大きいバスマスタに対して優先的に転送許可を与える。また転送要求優先度信号の値が最大のバスマスタが複数ある場合は、最大であるバスマスタを対象にラウンドロビン方式でバス調停を行う。

以上のような構成並びに方式を採ることにより、各バスマスタに対して適切なデッドライン保証を行うことが可能となる。

［実施の形態４］
図９は、本発明の実施の形態４に係るバスマスタ１００を用いた、別のシステムの構成を表す概略ブロック図である。

このシステムは、上位階層バス５０にＣＰＵ５１、アービタ５２、バスマスタ５３，５４、バススレーブ５５を接続している。またバスブリッジ５６を介して下位階層バス６０と接続されている。この下位階層バス６０には、アービタ６１、バスマスタ６２，６３、バススレーブ６４が接続されている。このうち、ＣＰＵ５１は図８のＣＰＵ４１と同一であり、アービタ５２，６１は、バスマスタのチャネル数が異なる点以外は、図８のアービタ４２と同じである。またバスマスタ５３，５４，６２，６３は、それぞれ図７のバスマスタ１００に相当し、バススレーブ５５，５６，６４はそれぞれ、図８のバススレーブ４６，４７と同一である。

前述の実施の形態３に係る図８との相違点は、上位階層バス５０と下位階層バス６０の２つにバスが階層化されている点にある。上位階層バス５０ではアービタ５２がバスの調停を行い、下位階層バス６０ではアービタ６１がバス調停を行う。またバス階層を跨いで転送を行う場合は、バスブリッジ５６を介して行う。

バス階層を跨いだ転送の例として、下位階層バス６０上のバスマスタ６２から上位階層バス５０上のバススレーブ５５へデータ転送を行う場合について説明する。

まずバスマスタ６２は、アービタ６１に対して、転送要求優先度信号と共に転送要求信号を送る。これに応答してアービタ６１により転送許可が与えられると、バスマスタ６２は、バスブリッジ５６を介してバススレーブ５５に対してデータ転送を開始する。これを受けてバスブリッジ５６は、アービタ５２に対して、バスマスタ６２が発行した転送要求優先度信号値と共にデータ転送を要求する。即ち、このときバスブリッジ５６は、上位階層バス５０上のバスマスタの１つとして動作する。また転送要求優先度信号は、下位階層バス６０上のバスマスタ６２が出力した値を継承する。アービタ５２によって上位階層バス５０における転送許可を与えられると、バスブリッジ５６はバススレーブ５５に対してデータ転送を行い、データ転送動作が終了する。

アービタ５２及び６１の調停動作は、前述の実施の形態３と同様であり、転送要求優先度信号の値がより大きいバスマスタに対して、優先的に転送許可を与える。また転送要求優先度信号の値が最大のバスマスタが複数ある場合は、最大であるバスマスタを対象にラウンドロビン方式でバス調停を行う。

以上のような構成並びに方式を採ることにより、階層化されたバスシステムにおいても、各バスマスタに対して適切なデッドライン保証を行うことが可能となる。

図１１は、図１０の転送条件に対して、デッドライン保証が可能となった例を示すグラフ図である。

図１０は、ラウンドロビン方式の調停アルゴリズムではデッドライン保証ができない例を示すグラフである。図１０では、１サイクルあたり１ワード（１ワードは４バイトとする）を転送できるバスシステムにおいて、３つのバスマスタが合計８９６ワードを転送している。マスタ０とマスタ２のデッドラインは、８００サイクル目である。またマスタ１のデッドラインは、１１００サイクル目である。また、各バスマスタのデータ転送量は、各々マスタ０が５１２バイト、マスタ１が２５６バイト、マスタ２が１２８バイトである。図１０においては、単純なラウンドロビン方式によるバス調停であるため、マスタ０の転送完了がデッドラインである８００サイクル目を越えてしまい、デッドライン保証ができていない。

これに対し図１１では、マスタ０（１４）がマスタ１（１５）並びにマスタ２（１６）よりも優先されてバス権許可を多く受けている。これによりデッドラインの保証が可能となり、かつ、マスタ２のデッドラインも保証も可能となっている。

また図１３は、図１２の転送条件に対して本実施の形態４を適用し、デッドライン保証が可能となった例を示すグラフ図である。

図１２は、バスマスタの転送能力が考慮されないことによってデッドライン保証ができない例を示すグラフ図である。バスマスタの転送能力には、一回当りの転送ビート数やデータ転送要求の発行頻度などが例として挙げられるが、同図における各バスマスタのデータ転送条件は以下のとおりである。

マスタ０は、１０００００サイクル以内に１６０００ワードの転送を保証、転送能力０．５７ワード／サイクル、バスリクエスト間隔１サイクルである。マスタ１は、１０００００サイクル以内に９０００ワードの転送を保証、転送能力０．１４ワード／サイクル、バスリクエスト間隔２５サイクルである。そしてマスタ２は、３００００サイクル以内に５０００ワードの転送を保証、転送能力０．４０ワード／サイクル、バスリクエスト間隔８サイクルである。

図１２では、残り時間検知手段と残り転送量検知手段の比によって、優先度を動的に変更する調停を行っている。転送能力が高いマスタ０が余裕を持ってデータ転送を完了している（１２００）。これに対して転送能力の低いマスタ１のデッドラインが保証できていない（１２０１）。

これに対して本実施の形態４では、残り時間検知手段と残り転送量検知手段の比に加え、バスマスタの転送能力をさらに加味して調停を行っている。これにより図１３に示すように、図１２ではデッドライン保証できていなかったマスタ１（１５）に対してもデッドラインの保証が可能となっている。

［実施の形態５］
図１４は、本発明の実施の形態５に係るバスマスタ１００ａの構成を表すブロック図で、前述の実施の形態３の図７と共通する部分は同じ記号で示し、それらの説明を省略する。この図１４では、図７と比較して、転送能力レジスタ１１４が省略されている。

このバスマスタ１００ａを用いたシステムの構成は前述の図８と同様である。

次に本実施の形態５に係るバスマスタ１００ａの詳細について説明する。

バス１０１上のＣＰＵから転送開始レジスタ１１３に「１」が書き込まれると、バスマスタ制御部１２１は、残り転送時間レジスタ１２４及び残り転送量レジスタ１２５に対してロード信号をアサートする。これにより、転送時間レジスタ１１１の値が残り転送時間レジスタ１２４にコピーされると共に、転送量レジスタ１１２の値が残り転送量レジスタ１２５にコピーされる。その後、バスマスタ制御部１２１は、残り転送時間レジスタ１２４に対して１μ秒ごとに時間減算信号をアサートする。また残り転送量レジスタ１２５に対して、データ転送が行われる度に、その転送されたバイト数分の転送量減算信号をアサートする。例えば本実施の形態５では、バス１０１における１ワードは３２ビットである。このため、１ワードの転送が行われた場合には転送量減算信号として「４」が、ハーフワード転送の場合には「２」が、バイト転送の場合には「１」がそれぞれアサートされる。そして残り転送量レジスタ１２５は、自身の値から転送量減算信号の値を減算する。

以上により、残り転送時間レジスタ１２４及び残り転送量レジスタ１２５の値が減算され、残り転送時間及び残り転送量の値が適切に更新される。

データ処理部１２２も、転送開始レジスタ１１３に「１」が書き込まれることによって起動される。データの送信或は受信が可能になると、データ処理部１２２はバスマスタ制御部１２１に対してデータレディ信号をアサートする。このデータレディ信号のアサートを受けて、バスマスタ制御部１２１は、バス１０１上のアービタ（図８のアービタ４２に相当）に対して転送要求信号をアサートするようにバスマスタＩ／Ｆ部１２０を制御する。

一方、転送要求度計算部１２３は、残り転送時間レジスタ１２４及び残り転送量レジスタ１２５の値に基づいて、データ転送の優先度を計算する。

本実施の形態５に係る転送要求度計算部１２３の計算は、「残り転送量レジスタ２５の値／残り転送時間レジスタ２４の値」である。この計算により、同一の残りデータ量に対しては、残り時間が少なくなるほど転送要求の優先度が高くなる。

一方、同一の残り時間に対しては、残りデータ量が多くなるほど転送要求優先度が高くなる。バスマスタＩ／Ｆ部１２０は、アービタ４２に対して、転送要求度計算部１２３の計算結果を転送要求優先度信号として出力する。この転送要求優先度信号のアサートタイミングは、転送要求信号のアサート開始と同一サイクルで、以降、転送が完了するまで値を保持する。

アービタ４２は、この転送要求優先度信号の値がより大きいバスマスタに優先的に転送許可を与える。また転送要求優先度信号の値が最大のバスマスタが複数ある場合は、最大であるバスマスタを対象にラウンドロビン方式でバス調停を行う。

以上のような構成並びに方式を採ることにより、各バスマスタに対して適切な帯域保証を行うことが可能となる。

［実施の形態６］
実施の形態６に係る、バスマスタ１００ａを用いた、別のシステムの構成を表す概略ブロック図は、前述の図９の構成と同じである。

ここでは上位階層バス５０と下位階層バス６０の２つにバスが階層化されている。上位階層バス５０においてはアービタ５２がバス調停を行い、下位階層バス６０においてはアービタ６１がバス調停を行う。また、バス階層を跨いで転送を行う場合は、バスブリッジ５６を介して行う。この場合のバス階層を跨いだ転送の例は、図９を参照して前述した説明と同じであるため、その説明を省略する。

図１５は、上述した実施の形態に係るバス調停装置、或はバスマスタにおける処理を説明するフローチャートである。

まずステップＳ１で、データ転送を実行する転送時間と、そのデータ転送量とを各レジスタに設定する。次にステップＳ２で、データの転送開始が指示されるのを待ち、データ転送の開始が指示されるとステップＳ３に進み、そのデータ転送を行うマスタに対応するデータ転送量及び転送経過時間を初期化する。次にステップＳ４で、そのデータ転送に選択したマスタとスレーブとの間でのデータ転送を実行し、そのデータ転送に同期して、そのマスタの転送データ量及び転送時間を更新する。次にステップＳ５で、（残りデータ量）／（残り時間）を計算する。次にステップＳ６では、図４や図７の例では、ステップＳ５で求めた値を転送能力値で割る。但し、図２や図１４に対応するバスマスタの場合には、このステップＳ６は省略できる。そしてステップＳ７で、前述した式（１）或は（２）に基づいて、そのマスタの評価値を求める。ここで、これらステップＳ１〜Ｓ７に示す処理は、各マスタのそれぞれに対して実行されている。次にステップＳ８で、各マスタに対して求めた評価値同士を比較し、最も評価値の大きいマスタを選択する。そしてステップＳ９で、その選択したマスタに対して、バスのアクセス使用権を与える。

こうして本実施の形態に係るバス調停装置或はバスマスタ装置は、各マスタに対してバスの使用権を付与するための調停処理を実行することができる。

（他の実施形態）
以上、本発明の実施形態について詳述したが、本発明は、複数の機器から構成される文書検索システムに適用しても良いし、また、一つの機器からなる文書検索装置に適用しても良い。

なお、本発明は、前述した実施形態の機能を実現するソフトウェアのプログラムを、システム或いは装置に直接或いは遠隔から供給し、そのシステム或いは装置のコンピュータが該供給されたプログラムを読み出して実行することによっても達成され得る。上記実施形態では、図５から７、及び図９から１３のフローチャートに対応したプログラムである。その場合、プログラムの機能を有していれば、形態は、プログラムである必要はない。 従って、本発明の機能処理をコンピュータで実現するために、該コンピュータにインストールされるプログラムコード自体も本発明を実現するものである。つまり、本発明のクレームでは、本発明の機能処理を実現するためのコンピュータプログラム自体も含まれる。その場合、プログラムの機能を有していれば、オブジェクトコード、インタプリタにより実行されるプログラム、ＯＳに供給するスクリプトデータ等、プログラムの形態を問わない。

プログラムを供給するための記録媒体としては、様々なものが使用できる。例えば、フロッピー（登録商標）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＤＶＤ（ＤＶＤ−ＲＯＭ，ＤＶＤ−Ｒ）などである。

その他、プログラムの供給方法としては、クライアントコンピュータのブラウザを用いてインターネットのホームページに接続し、該ホームページからハードディスク等の記録媒体にダウンロードすることによっても供給できる。その場合、ダウンロードされるのは、本発明のコンピュータプログラムそのもの、もしくは圧縮され自動インストール機能を含むファイルであってもよい。また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるホームページからダウンロードすることによっても実現可能である。つまり、本発明の機能処理をコンピュータで実現するためのプログラムファイルを複数のユーザに対してダウンロードさせるＷＷＷサーバも、本発明のクレームに含まれるものである。

また、本発明のプログラムを暗号化してＣＤ−ＲＯＭ等の記憶媒体に格納してユーザに配布する形態としても良い。その場合、所定の条件をクリアしたユーザに対し、インターネットを介してホームページから暗号化を解く鍵情報をダウンロードさせ、その鍵情報を使用することにより暗号化されたプログラムが実行可能な形式でコンピュータにインストールされるようにする。

また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現される形態以外の形態でも実現可能である。例えば、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどが、実際の処理の一部または全部を行ない、その処理によっても前述した実施形態の機能が実現され得る。

更に、記録媒体から読み出されたプログラムが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれるようにしてもよい。この場合、その後で、そのプログラムの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行ない、その処理によって前述した実施形態の機能が実現される。

本発明の実施の形態１に係るバス調停装置（バスアービタ）の構成図である。 実施の形態１に係るアービタの動作を説明するタイミングチャートである。 実施の形態１においてマスタごとに計算した評価値を分かりやすく解説する図である。 本発明の実施の形態２に係るアービタによる動作を説明するタイミングチャートである。 本実施の形態２において、各マスタごとに計算した評価値を分かりやすく解説する図である。 本実施の形態２に係るマスタ０と１の転送能力を説明する図である。 本発明の実施の形態３に係るバスマスタの構成を表すブロック図である。 実施の形態３に係るバスマスタを用いたシステムの構成を表す概略ブロック図である。 本発明の実施の形態４に係るバスマスタを用いた、別のシステムの構成を表す概略ブロック図である。 ラウンドロビン方式の調停アルゴリズムでデッドライン保証ができない例を説明するグラフ図である。 図１０の転送条件に対して、デッドライン保証が可能となった例を示すグラフ図である。 バスマスタの転送能力が考慮されないことによってデッドライン保証ができない例を説明するグラフ図である。 図１２の転送条件に対して本実施の形態４を適用し、デッドライン保証が可能となった例を示すグラフ図である。 本発明の実施の形態５に係るバスマスタの構成を表すブロック図である。 本実施の形態に係るバス調停装置における処理を説明するフローチャートである。

Claims (10)

1. 各マスタのバス使用権の調停を行うバス調停装置であって、
   各マスタが転送すべきデータのデータ量を設定するデータ量設定手段と、
   各マスタによる前記データ量のデータ転送の転送期限を設定する転送期限設定手段と、
   各マスタの前記転送期限までの残り時間を計時する計時手段と、
   各マスタが転送すべきデータの残りデータ量を検知する残データ量検知手段と、
   前記残り時間と前記残りデータ量とに基づいて、データ転送を開始しているマスタを含む複数のマスタのうち緊急度の高いデータ転送に対応するマスタに、優先してバス使用権を割り当てるバス調停手段と、
   を有することを特徴とするバス調停装置。
2. 各マスタの転送能力を表す情報を格納する転送能力格納手段を更に有し、
   前記バス調停手段は、前記残り時間と前記残りデータ量と、前記情報との演算結果に基づいて、各マスタにバス使用権を割り当てることを特徴とする請求項１に記載のバス調停装置。
3. 前記残データ量検知手段は、データ転送を行う度にデータ量をカウントするデータ量カウンタを含むことを特徴とする請求項１又は２に記載のバス調停装置。
4. 前記バス調停手段は、前記残りデータ量と前記残り時間との除算結果に基づいて各マスタにバス使用権を割り当てることを特徴とする請求項１又は３に記載のバス調停装置。
5. バスアービタに転送要求信号を送出し、バスにアクセスするバスマスタ装置であって、
   データ転送すべき期限までの残り時間を検知する残り時間検知手段と、
   転送すべき残りデータ量を検知する残りデータ量検知手段と、
   前記残り時間及び前記残りデータ量に基づいて前記転送要求信号の優先度を算出する優先度算出手段と、
   前記優先度算出手段により算出した優先度をバスアービタに通知する通知手段と、
   前記バスアービタからの許可に基づいて前記バスを介してデータ転送を開始する出力手段と、
   を有することを特徴とするバスマスタ装置。
6. バスマスタ装置自身の転送能力を設定する転送能力設定手段を更に有し、前記優先度算出手段は、前記残り時間及び前記残りデータ量に加えて、更に前記バスマスタ装置自身の転送能力に基づいて前記優先度を算出することを特徴とする請求項５に記載のバスマスタ装置。
7. データ転送量を設定する転送データ量設定手段を更に有し、
   前記残りデータ量検知手段は、前記転送データ量設定手段により設定された前記データ転送量をデータ転送の開始からの転送データの量に応じて更新して前記残りデータ量を検知することを特徴とする請求項５又は６に記載のバスマスタ装置。
8. 各マスタのバス使用権の調停を行うバス調停方法であって、
   各マスタが転送すべきデータのデータ量を設定するデータ量設定工程と、
   各マスタによる前記データ量のデータ転送の転送期限を設定する転送期限設定工程と、
   各マスタの前記転送期限までの残り時間を計時する計時工程と、
   各マスタが転送すべきデータの残りデータ量を検知する残データ量検知工程と、
   前記残り時間と前記残りデータ量とに基づいて、データ転送を開始しているマスタを含む複数のマスタのうち緊急度の高いデータ転送に対応するマスタに、優先してバス使用権を割り当てるバス調停工程と、
   を有することを特徴とするバス調停方法。
9. 各マスタの転送能力を表す情報を格納する転送能力格納工程を更に有し、
   前記バス調停工程では、前記残り時間と前記残りデータ量と、前記情報との演算結果に基づいて、各マスタにバス使用権を割り当てることを特徴とする請求項８に記載のバス調停方法。
10. 前記残データ量検知工程では、データ転送の開始から、データ転送を行う度にデータ量をカウントすることを特徴とする請求項８又は９に記載のバス調停方法。

Images