(57)【特許請求の範囲】
【請求項１】
複数のリクエスタからアクセス対象へのアクセス要求を調停するアクセス調停装置であって、
各リクエスタに対するアクセス許可の優先度を保持する優先度保持手段と、
上記優先度保持手段に保持される優先度を制御する優先度制御手段と、
上記優先度保持手段に保持された優先度が最も高いリクエスタにアクセス許可を与えるアクセス許可手段と、
を備え、
上記優先度制御手段は、
リクエスタからアクセス要求がある場合、およびアクセス要求がなくて優先度が所定の基準優先度よりも低い場合に、時間経過に応じて、優先度を所定の上昇程度だけ上昇させる一方、
アクセスが許可された場合に、優先度を一定の低下程度だけ低下させるように構成されていることを特徴とするアクセス調停装置。
【請求項２】
請求項１のアクセス調停装置であって、
上記優先度の低下程度が、リクエスタごとに設定されるように構成されていることを特徴とするアクセス調停装置。
【請求項３】
請求項１のアクセス調停装置であって、
上記優先度の低下が、リクエスタによるアクセスの完了時点で行われるように構成されていることを特徴とするアクセス調停装置。
【請求項４】
請求項１のアクセス調停装置であって、
上記アクセス許可手段は、上記優先度の低下によって優先度が所定の許可停止優先度よりも低くなったリクエスタへのアクセス許可を与えないように構成されていることを特徴とするアクセス調停装置。
【請求項５】
請求項１のアクセス調停装置であって、
上記優先度制御手段は、さらに、全てのリクエスタについての優先度が、上記基準優先度よりも低い場合に、少なくとも一部の所定のリクエスタについての優先度を基準優先度に設定するように構成されていることを特徴とするアクセス調停装置。
【請求項６】
請求項１のアクセス調停装置であって、
上記優先度制御手段は、さらに、全てのリクエスタからのアクセス要求がない場合に、少なくとも一部の所定のリクエスタについての優先度を上記基準優先度に設定するように構成されていることを特徴とするアクセス調停装置。
【請求項７】
請求項１のアクセス調停装置であって、
上記優先度制御手段は、さらに、１つのリクエスタだけからアクセス要求がある場合に、他のアクセス要求がないリクエスタのうち、少なくとも一部の所定のリクエスタについての優先度を上記基準優先度に設定するように構成されていることを特徴とするアクセス調停装置。
【請求項８】
請求項１のアクセス調停装置であって、
上記優先度制御手段は、さらに、何れかのリクエスタに対して、上記優先度が所定の限界優先度に達するまでアクセス許可が与えられなかった場合に、エラー信号を出力するように構成されていることを特徴とするアクセス調停装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はメモリインターフェースやタスクの制御などに用いられるアクセス調停装置（アービター）に関するものである。
【背景技術】
【０００２】
システムＬＳＩ（Large Scale Integrated circuit）が用いられつつある今日では、以前の複数チップの機能を有する複数の機能ブロックを１チップに集積することがよく行われている。このような場合には、コストダウンを図るために、外部メモリの統合がなされることが多い。すなわち、以前のように複数チップのＬＳＩが用いられる場合であれば、メモリも複数設けられて、それぞれ各ＬＳＩに占有されることが多かったが、システムＬＳＩでは、複数の機能ブロックが１つのメモリを共用することが非常に多く行われるようになる。そこで、複数の機能ブロックからの競合するアクセスを調停するために、アクセス調停装置が用いられる。
【０００３】
アクセス調停装置の性能は、特に、デジタルＡＶ（audio visual）家電におけるＡＶ処理ブロックのように、リアルタイム性の高い処理が要求される場合に重要となる。このような高いリアルタイム性が要求される処理に対しては、例えばワーストアクセスタイム（アクセス要求があってからアクセスがなされるまでの最長時間）を保証できるラウンドロビン方式を用いるハードウェアメカニズムが知られている（例えば、特許文献１参照。）。
【０００４】
また、特にバス調停に関するものではないが、マルチタスキング処理において複数のプログラムの実行をスケジューリングするために、ＥＤＦ（Earliest Deadline First）と呼ばれる手法を用いたものなども知られている。具体的には、実行待ち行列を生成し、新たなタスクの生成時などに、デッドラインまでの時間の長さによってソートする処理が行われる（例えば、特許文献２参照。）。
【０００５】
一方、例えば、近年のデジタルＡＶ（audio visual）家電においては、システムＬＳＩの内部に、リアルタイム性の高いＡＶ処理を行うＡＶ処理ブロックと、ＧＵＩ（graphical user interface）などのコンピュータ並みの複雑な制御を行う汎用マイコン（マイクロコンピュータ）などが設けられ、それぞれの機能ブロックが同一のメモリを共有するような構成が考えられる。このようにリアルタイム性を要求するシステムと、マイコンのようにリアルタイム性はそれほど要求しないが高いパフォーマンス（平均した性能）を要求するようなシステムでは、特にリアルタイム性とパフォーマンスを両立させ得るように統合化されたメモリアクセスの効率的な調停が必要になる。
【特許文献１】特表２００１−５１６１００号公報
【特許文献２】特開平５−２７４１６２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上記のようなラウンドロビン方式は、リアルタイム性を保証することは可能ではあるが、そのためには、調停の対象となる処理に過大な処理能力が必要とされる。すなわち、アクセスを要求する処理の優先度に係わらず一定の順序でアクセスが許可されるので、優先度の低い処理が行われた後に優先度の高い処理が行われてもよいような処理能力が必要となる。
【０００７】
一方、ＥＤＦ手法は、最適なスケジューリングを行い得ることが知られているが、タスクの生成時や実行完了時ごとに頻繁に待ち行列の項目を並べ換える処理などをハードウェアで行うことは困難である。それゆえ、バス調停などのような高速な応答が必要とされる場合に適用することは困難である。
【０００８】
また、ＥＤＦ手法は、デッドラインが明確に決定されるリアルタイム系の処理には容易に適用できるが、非リアルタイム系の処理は明確なデッドラインがない（平均的な処理能力は必要とされるが、個々の処理がいつまでに完了しなければならないという制約はない）ために、必ずしも適用が容易ではない。特に、リアルタイム系の処理と非リアルタイム系の処理とが混在する場合に、リアルタイム性とパフォーマンスを両立させ得るように統合化されたメモリアクセスの効率的な調停を行わせることは困難である。
【０００９】
本発明は、上記の点に鑑み、簡潔なハードウェア構成で適切な調停を高速に行わせることができ、しかも、リアルタイム系の処理と非リアルタイム系の処理とが混在する場合でも、これらを共通に扱えるようにして、リアルタイム性とパフォーマンスを両立させ得る効率的な調停を行わせることも容易なアクセス調停装置を提供することを目的としている。
【課題を解決するための手段】
【００１０】
上記の課題を解決するため、本発明の実施形態の第１のアクセス調停装置は、
複数のリクエスタからアクセス対象へのアクセス要求を調停するアクセス調停装置であって、
各リクエスタに対するアクセス許可の優先度を保持する優先度保持手段と、
上記優先度保持手段に保持される優先度を制御する優先度制御手段と、
上記優先度保持手段に保持された優先度が最も高いリクエスタにアクセス許可を与えるアクセス許可手段と、
を備え、
上記優先度制御手段は、
リクエスタからアクセス要求がある場合、およびアクセス要求がなくて優先度が所定の基準優先度よりも低い場合に、時間経過に応じて、優先度を所定の上昇程度だけ上昇させる一方、
アクセスが許可された場合に、優先度を一定の低下程度だけ低下させるように構成されていることを特徴とする。
【００１１】
また、本発明の実施形態の第２のアクセス調停装置は、
第１のアクセス調停装置であって、
上記優先度の低下程度が、リクエスタごとに設定されるように構成されていることを特徴とする。
【００１２】
また、本発明の実施形態の第３のアクセス調停装置は、
第１のアクセス調停装置であって、
上記優先度の低下が、リクエスタによるアクセスの完了時点で行われるように構成されていることを特徴とする。
【００１３】
これらにより、待ち行列のソート処理などを必要とすることなく、加減算など程度の処理によって、適切な応答時間でアクセスが行われるように調停することができる。また、いわゆる非リアルタイム系の処理などに対しても、基準優先度などの値を設定することによって、リアルタイム系の処理などと併せて調停することも容易にできる。
【００１４】
また、本発明の実施形態の第４のアクセス調停装置は、
第１のアクセス調停装置であって、
上記アクセス許可手段は、上記優先度の低下によって優先度が所定の許可停止優先度よりも低くなったリクエスタへのアクセス許可を与えないように構成されていることを特徴とする。
【００１５】
これにより、連続してアクセス要求がなされたときに優先度に応じた値が過大になったり過小になったりするのが防止される。
【００１６】
また、本発明の実施形態の第５のアクセス調停装置は、
第１のアクセス調停装置であって、
上記優先度制御手段は、さらに、全てのリクエスタについての優先度が、上記基準優先度よりも低い場合に、少なくとも一部の所定のリクエスタについての優先度を基準優先度に設定するように構成されていることを特徴とする。
【００１７】
また、本発明の実施形態の第６のアクセス調停装置は、
第１のアクセス調停装置であって、
上記優先度制御手段は、さらに、全てのリクエスタからのアクセス要求がない場合に、少なくとも一部の所定のリクエスタについての優先度を上記基準優先度に設定するように構成されていることを特徴とする。
【００１８】
また、本発明の実施形態の第７のアクセス調停装置は、
第１のアクセス調停装置であって、
上記優先度制御手段は、さらに、１つのリクエスタだけからアクセス要求がある場合に、他のアクセス要求がないリクエスタのうち、少なくとも一部の所定のリクエスタについての優先度を上記基準優先度に設定するように構成されていることを特徴とする。
【００１９】
これらにより、連続したアクセス要求によって優先度が低くされた場合でも、他のアクセス要求がない場合などには、優先度が戻されてアクセス許可されやすくなるようにされる。
【００２０】
また、本発明の実施形態の第８のアクセス調停装置は、
第１のアクセス調停装置であって、
上記優先度制御手段は、さらに、何れかのリクエスタに対して、上記優先度が所定の限界優先度に達するまでアクセス許可が与えられなかった場合に、エラー信号を出力するように構成されていることを特徴とする。
【００２１】
これにより、適切に調停が行われるかどうかの確認などが容易に行われる。
【発明の効果】
【００２２】
本発明によれば、単純な回路で、複数の処理や装置（リクエスタ）がメモリを共有する場合のバス調停などに対して、例えばリアルタイム性とパフォーマンスを両立させ得る効率よい調停を実現できる。
【発明を実施するための最良の形態】
【００２３】
本発明の実施形態として、図１に示すように、２つのリクエスタ２０１・２０２によるメモリ２０３へのアクセスを調停するアクセス調停装置１００の例を説明する。
【００２４】
このアクセス調停装置１００は、リクエスタ２０１・２０２から与えられる基準優先値（ＴＭＩＮ）、優先度低下値（ＰＥＲＩＯＤ）、および許可停止優先値（ＴＭＡＸ）に基づいて調停を行うようになっている。（上記各値および後述する優先度制御値は、優先度に関連する値であるが、その単位は、説明の便宜上、クロックサイクル数またはこれに対応した時間の次元として説明する。）
上記基準優先値（ＴＭＩＮ）は、リクエストが所定以上のリクエスト周期でなされる場合には、リクエストがなされてからその値の応答時間（クロックサイクル数）以内にアクセスが完了すべきことを示すものである。上記所定以上のリクエスト周期は、（リクエスト周期−優先度低下値（ＰＥＲＩＯＤ））の累積値≧０となるような周期である（上記累積値は、累積値＞０になるごとに０にリセットされるとした値である。）。ここで、上記応答時間は、上記基準優先値（ＴＭＩＮ）および優先度低下値（ＰＥＲＩＯＤ）と、各リクエスタ２０１・２０２のアクセスに要する時間（Ｔａｃｃｅｓｓ）とが後に詳述するように所定の条件を満たすことによって保証することができる。
【００２５】
また、許可停止優先値（ＴＭＡＸ）は、優先度制御値がこの値を越えている間は、他のリクエスタの優先度制御値との大小関係に係わらず、アクセスが許可されなくてもよいことを示すものである。（なお、優先度制御値が増大して許可停止優先値（ＴＭＡＸ）を越えたりするのは、例えば優先度低下値（ＰＥＲＩＯＤ）より短い周期でのリクエストが連続した場合であり、優先度制御値が許可停止優先値（ＴＭＡＸ）を越えている間にアクセスが許可されなくても、平均的な応答時間は守られる。）
なお、通常、非リアルタイム系の処理や処理装置については、必ずしも絶対的な応答性は要求されないが、リアルタイム系と同様に上記各パラメータを設定することにより、調停動作自体は特に区別することなく行わせることができる。これによって、例えばリアルタイム系のアクセスの残りバンド幅を非リアルタイム系のアクセスについて最低保証として与えることなどができる（この場合でも、後述するように、処理に余裕があれば、それ以上の性能を実質的に発揮させることもできる。）。
【００２６】
（アクセス調停装置１００について）
アクセス調停装置１００は、具体的には、各リクエスタ２０１・２０２に対する優先度制御値を保持する優先度制御値レジスタ１０１・１０１と、上記優先度制御値を制御する優先度制御値制御部１０２・１０２と、優先度制御値レジスタ１０１・１０１に保持された優先度制御値に基づいてアクセスを許可するリクエスタ２０１・２０２を選択する選択部１０３と、選択結果に基づいてアクセス制御をするアクセス制御部１０４とを備えて構成されている。
【００２７】
上記優先度制御値レジスタ１０１に保持される優先度制御値は、例えば各リクエスタ２０１・２０２によるアクセスが完了すべき時刻までの時間（クロックサイクル数）を示すようになっている。したがって、この場合には値が小さいほど優先度が高いことになる。上記優先度制御値レジスタ１０１は、具体的には、例えばカウンタを用いて構成されている。
【００２８】
優先度制御値制御部１０２は、リクエスタ２０１・２０２から与えられる所定の基準優先値（ＴＭＩＮ）、および優先度低下値（ＰＥＲＩＯＤ）に基づいて、上記優先度制御値レジスタ１０１に保持される優先度制御値を図２および以下に示すように制御するようになっている。
【００２９】
（ａ）  １クロックサイクルごとに、優先度制御値を１ずつ減少させる。
【００３０】
（ｂ）  ただし、リクエスタ２０１・２０２からのリクエストがない場合（リクエスト信号がアサートされていない場合）には、基準優先値（ＴＭＩＮ）よりも小さくはしない。
【００３１】
（ｃ）  リクエスタ２０１・２０２によるメモリ２０３へのアクセスが完了すると、優先度制御値を優先度低下値（ＰＥＲＩＯＤ）だけ増加させる。上記アクセスの完了は、具体的には、例えばアクセス完了時にリクエスト信号がネゲートされることによって検知される。
【００３２】
さらに、優先度制御値制御部１０２は、優先度制御値が基準優先値（ＴＭＩＮ）以上の（優先度が低い）場合にネゲートされるビジー信号を出力するとともに、このビジー信号が何れのリクエスタ２０１・２０２についてもネゲートされた場合に、後述するようにアクセス制御部１０４からの初期化信号がアサートされるのに応じて、優先度制御値を基準優先値（ＴＭＩＮ）に設定するようになっている。
【００３３】
また、優先度制御値が負になった場合（１を減算する前に０であった場合）にアサートされるエラー信号を出力するようになっている。このエラー信号は、例えばアクセス調停装置のデバッグの際に調停が破綻しないことを確認するためなどに用いることができるが、必ずしもこのようなエラー信号が出力されるようにしなくてもよい。
【００３４】
また、選択部１０３は、リクエスト信号がアサートされているリクエスタ２０１・２０２のうち、優先度制御値レジスタ１０１に保持されている優先度制御値の小さい方を選択して、セレクト結果信号を出力するようになっている。ただし、優先度制御値がリクエスタ２０１・２０２から出力される許可停止優先値（ＴＭＡＸ）を越える場合には、選択がなされないようになっている。
【００３５】
アクセス制御部１０４は、上記セレクト結果信号に応じて、リクエスタ２０１・２０２にアクセス許可信号を出力するようになっている。また、前記のように全ての優先度制御値制御部１０２から出力されるビジー信号がネゲートされた場合（何れのリクエスタ２０１・２０２についても、優先度制御値が基準優先値（ＴＭＩＮ）以上である場合）に、少なくともリクエスタ２０１・２０２の一方に対応した優先度制御値制御部１０２に出力する初期化信号をアサートし、優先度制御値を基準優先値（ＴＭＩＮ）に設定させるようになっている。
【００３６】
なお、上記基準優先値（ＴＭＩＮ）等の値は、リクエスタ２０１・２０２から与えられるのに限らず、他の管理装置などから与えられるようにしたり、あらかじめアクセス調停装置に設定されるようにしたりしてもよい。また、レジスタなどに保持されるようにして、回路を変更することなくパラメータの変更ができるようにすれば、仕様変更に対する柔軟性や汎用性などを高めることができる。
【００３７】
また、リクエスタの数は２つに限るものではないが、特に、リクエスタの数が多い場合でも、各リクエスタは同じように扱われ、回路規模や複雑さが大幅に増すことはないので、多くのリクエスタを調停し得る装置を構成することも容易にできる。
【００３８】
また、優先度低下値（ＰＥＲＩＯＤ）の加算タイミングなどは、上記に限らず、実質的に同じ動作が得られる種々の変形例を適用してもよい。具体的には例えば優先度低下値（ＰＥＲＩＯＤ）が上記のようにアクセス完了時に加算される場合には、リクエスト周期などとの関係で値の意味を把握しやすいが、アクセス許可がなされた時点で、アクセス中の優先度制御値の減少を考慮した値が加算されるようにしたりしてもよい。
【００３９】
上記のように構成されたアクセス調停装置１００では、後に詳述するように所定の条件を満たしていれば、リクエスタ２０１・２０２によるアクセスは、必ず、優先度制御値が０になるまでに完了する。すなわち、優先度制御値は、リクエストがなされた場合に、アクセスが完了すべき時刻（デッドライン）までの時間を示していることになる。また、上記優先度制御値が最も小さい（デッドラインが最も近い）リクエスタ２０１・２０２が選択されるので、このアクセス調停装置１００ではＥＤＦ（Earliest Deadline First）アルゴリズムによる調停が行われていることになる。
【００４０】
以下、具体的な動作の例を図２に基づいて説明する。
【００４１】
（Ａ）  調停が開始される際など、優先度制御値が基準優先値（ＴＭＩＮ）の状態でリクエスト信号がアサートされたとすると、優先度制御値は時間の経過とともに減少する（優先度が徐々に上昇する。）。
【００４２】
（Ｂ）  やがて優先度制御値が他のリクエストがなされているリクエスタの優先度制御値よりも小さくなると、アクセスが許可される。アクセス時間（Ｔａｃｃｅｓｓ）のアクセスが完了してリクエスト信号がネゲートされると、優先度制御値は、優先度低下値（ＰＥＲＩＯＤ）が加算された値に上昇する。
【００４３】
（Ｃ）  上昇した優先度制御値は、少なくとも基準優先値（ＴＭＩＮ）に低下するまでは、次のリクエストの有無に係わらず徐々に減少する。
【００４４】
（Ｄ）  次のリクエストがあった場合には、優先度制御値が基準優先値（ＴＭＩＮ）に低下した後も、さらに低下し続ける。やがて上記（Ｂ）と同様にアクセスが許可され、優先度制御値が０になるまでにアクセスが完了する。そこで、優先度制御値は、さらに優先度低下値（ＰＥＲＩＯＤ）が加算された値に上昇する。
【００４５】
（Ｅ）  優先度制御値は（Ｃ）と同様に徐々に減少するが、優先度制御値が基準優先値（ＴＭＩＮ）に低下した時点で次のリクエストがない場合には、次のリクエストがあるまで、基準優先値（ＴＭＩＮ）に保たれる。
【００４６】
（Ｆ）  次のリクエストがあると、優先度制御値は低下し始める。そしてアクセスが許可され、アクセスが完了すると、優先度低下値（ＰＥＲＩＯＤ）が加算された値に上昇する。
【００４７】
（Ｇ）  やはり、優先度制御値が徐々に減少する。ここで、優先度制御値が基準優先値（ＴＭＩＮ）よりも大きくても、他のリクエスタの優先度制御値よりも小さければ、アクセスは許可される。ただし、優先度制御値が許可停止優先値（ＴＭＡＸ）よりも大きい場合には、アクセス許可は抑制される。それゆえ、短期間にリクエストが繰り返されても、優先度制御値が（許可停止優先値（ＴＭＡＸ）＋優先度低下値（ＰＥＲＩＯＤ））よりも大きくならないので、優先度制御値レジスタ１０１のオーバーフローが回避される。そして、上記のようにアクセス許可が抑制されても、前記のように平均的な応答時間は守られる。
【００４８】
また、上記許可停止優先値（ＴＭＡＸ）が比較的小さい値に設定されると、リクエストが頻繁になされたとしても一定周期以下のアクセスが禁止されて、アクセスの平均化が図られることになるので、例えばメモリのリフレッシュ動作を適切に行わせることなどが容易にできる。一方、許可停止優先値（ＴＭＡＸ）が大きい値に設定されると、連続したアクセスが許可されるようにすることができる。それゆえ、例えば非リアルタイム系のリクエスタなどに対しては、許可停止優先値（ＴＭＡＸ）を大きく設定することによって、パフォーマンスを高く設定することができる。
【００４９】
なお、必ずしも上記のようなアクセス許可の抑制がなされるようにしなくても、優先度制御値レジスタ１０１のサイズが十分に大きければ、調停動作自体は適切に行わせることができる。
【００５０】
（Ｈ）  一方、優先度制御値が許可停止優先値（ＴＭＡＸ）よりも大きい場合でも、全てのリクエスタ２０１・２０２の優先度制御値がそれぞれ基準優先値（ＴＭＩＮ）以上（ビジー信号がネゲート状態）であれば、全ての、または一部のリクエスタについての優先度制御値が例えば基準優先値（ＴＭＩＮ）に設定され、その後にリクエストがなされた後、または既にリクエストされている場合には直ちに、上記基準優先値（ＴＭＩＮ）から低下し始める。
【００５１】
ここで、上記のように全てのリクエスタ２０１・２０２の優先度制御値がそれぞれ基準優先値（ＴＭＩＮ）以上である場合に、各優先度制御値が基準優先値（ＴＭＩＮ）に設定されても、適切なアクセスが損なわれることはない。このことは、以下の観点から明らかである。すなわち、所定の条件が満たされていれば、各リクエスタは、基準優先値（ＴＭＩＮ）以内の期間にアクセスが完了することが保証される。したがって、何れのリクエスタも、優先度制御値を基準優先値（ＴＭＩＮ）より大きい値から基準優先値（ＴＭＩＮ）に引き下げても、当該リクエスタのアクセスは保証される。また、上記保証は、他のリクエスタの優先度制御値がどのように設定されいるかに係わらないので、上記他のリクエスタの優先度制御値をそれぞれ基準優先値（ＴＭＩＮ）に引き下げても差し支えない。それゆえ、全てのリクエスタの優先度制御値が基準優先値（ＴＭＩＮ）より大きい場合には、何れのリクエスタの優先度制御値も基準優先値（ＴＭＩＮ）に変更することができることになる。
【００５２】
そして、上記のように、調停が破綻しないと判断される場合に優先度制御値が変更されることにより、許可停止優先値（ＴＭＡＸ）を越えたリクエスタでも、可能な限りアクセスが許可されるようにすることができる。それゆえ、全てのリクエスタについて基準優先値（ＴＭＩＮ）に変更されるようにしてもよいが、例えば、非リアルタイム系のリクエスタに対して上記のような変更がなされるようにすることにより、リアルタイム系のリクエスタに必要なアクセスを確保しつつ（最長遅延時間を保証してリアルタイム性を保証しつつ）、非リアルタイム系のリクエスタによる処理のパフォーマンスを高くすることなどが容易にできる。
【００５３】
なお、上記のように全てのリクエスタ２０１・２０２についてのビジー信号がネゲート状態であるかどうかの判定に代えて、何れのリクエスタ２０１・２０２からもリクエストがなされていないかどうかを判定するようにしてもよい。すなわち、リクエストがなされていなければ優先度制御値が基準優先値（ＴＭＩＮ）より小さくなることはないので、得られる判定結果は同じである。さらに、リクエストのなされているリクエスタが１つだけの場合にも、そのリクエスタは直ちにアクセスが許可されているので、そのような場合に、他の全て、または一部のリクエスタについて優先度制御値が変更されるようにしてもよい。また、変更される値は基準優先値（ＴＭＩＮ）に限らず、これを限度として優先度が高くなる変更であればよい。
【００５４】
上記のような調停が行われる場合のリクエストがなされてからアクセスが完了するまでの応答時間最大値は、ｎ番目のリクエスト時刻をＴ（ｎ）とすると、
ｍａｘ｛（ｎ−１）×ＰＥＲＩＯＤ−Ｔ（ｎ），０｝＋ＴＭＩＮ
（ｍａｘ｛，｝は｛，｝内の大きい方の値を意味する。）
となる。なぜならば、優先度制御値は、ｎ−１番目までの各リクエストに対するアクセスが完了するごとに優先度低下値（ＰＥＲＩＯＤ）ずつ増加し、時刻Ｔ（ｎ）までの経過時間だけ減少し、ただし、リクエストがない状態で基準優先値（ＴＭＩＮ）から減少することはないからである。
【００５５】
（調停可能条件について）
次に、各リクエスタのリクエスト周期がそれぞれ所定以上でさえあれば、何れのリクエストについても、リクエストがなされてから所定の応答時間以内に、すなわち優先度制御値が０になるまでに必ずアクセスが行われる（完了する）ことを保証するための条件（調停可能条件）およびその検証について説明する。
【００５６】
上記調停可能条件については、まず、ある時刻ｔ＝Ｔｅｒｒｏｒで調停が破綻する場合、すなわち時刻ｔ＝Ｔｅｒｒｏｒで、あるリクエスタの最後のアクセスが完了せずに優先度制御値が０になる場合を考え、それ以前のアクセスが全て許可され完了する条件を求めて、さらに、その条件を任意のｔ＝Ｔｅｒｒｏｒに対して満たす条件を求めればよい。
【００５７】
調停が破綻する場合については、以下のような２つの破綻パターンに分けることができる。ここで、前記のように優先度低下値（ＰＥＲＩＯＤ）はアクセス完了時に加算されるとする。また以下では、各リクエスタ、および各リクエスタに関する値を一般化して添え字（ｊ）等を付けて表す。
【００５８】
（１）  第１の破綻パターン
各リクエスタ（ｊ）について、最後にアクセスが完了するまでの優先度制御値Ｐ（ｊ）が、Ｔｅｒｒｏｒ−ｔ以下の場合
各リクエスタ（ｊ）の時刻ｔでの優先度制御値Ｐ（ｊ）は、図３に示すように、基準優先値（ＴＭＩＮ（ｊ））を初期値として、アクセス完了ごとに優先度低下値（ＰＥＲＩＯＤ（ｊ））だけ増加し、時間経過とともにｔだけ減少する。そこで、時刻ｔ＝Ｔｅｒｒｏｒまでにリクエスタごとのアクセスが完了した回数をｎ０（ｊ）、優先度制御値Ｐ（ｊ）がＴＭＩＮ（ｊ）に保たれている時間の合計をＴｗａｉｔ（ｊ）とすると、ｎ０（ｊ）回目のアクセスが完了するまでのＰ（ｊ）は、（最後のアクセス完了後に加算されるＰＥＲＩＯＤ（ｊ）は考慮しなくてよいから、）
Ｐ（ｊ）
＝ＴＭＩＮ（ｊ）＋｛ｎ０（ｊ）−１｝×ＰＥＲＩＯＤ（ｊ）−ｔ＋Ｔｗａｉｔ（ｊ）
である。そして、第１の破綻パターンの場合、全てのリクエスタ（ｊ）について、常に
Ｐ（ｊ）≦Ｔｅｒｒｏｒ−ｔ
であるから、
ＴＭＩＮ（ｊ）＋｛ｎ０（ｊ）−１｝×ＰＥＲＩＯＤ（ｊ）−ｔ＋Ｔｗａｉｔ（ｊ）
≦Ｔｅｒｒｏｒ−ｔ
である。それゆえ、上記アクセス完了回数ｎ０（ｊ）は、
ｎ０（ｊ）
≦｛Ｔｅｒｒｏｒ−ＴＭＩＮ（ｊ）−Ｔｗａｉｔ（ｊ）｝／ＰＥＲＩＯＤ（ｊ）＋１
≦｛Ｔｅｒｒｏｒ−ＴＭＩＮ（ｊ）｝／ＰＥＲＩＯＤ（ｊ）＋１
（∵Ｔｗａｉｔ（ｊ）≧０）
となる。すなわち、各リクエスタ（ｊ）について、ｔ＝Ｔｅｒｒｏｒまでに完了するアクセス回数は、｛Ｔｅｒｒｏｒ−ＴＭＩＮ（ｊ）｝／ＰＥＲＩＯＤ（ｊ）＋１以下となる。
【００５９】
一方、各リクエスタ（ｊ）のアクセスに要する時間をＴａｃｃｅｓｓ（ｊ）とし、最初のリクエスタのリクエストに対してアクセスが許可されアクセスが開始されるまでの時間をｄｅｌａｙとすると、全リクエスタについてのアクセス時間の総合計（Ｔａｌｌ）は、
Ｔａｌｌ
＝ｄｅｌａｙ＋Σｎ０（ｊ）×Ｔａｃｃｅｓｓ（ｊ）
≦ｄｅｌａｙ＋Σ〔｛Ｔｅｒｒｏｒ−ＴＭＩＮ（ｊ）｝／ＰＥＲＩＯＤ（ｊ）＋１〕×Ｔａｃｃｅｓｓ（ｊ）
である。これがＴｅｒｒｏｒ以下であれば、時刻ｔ＝Ｔｅｒｒｏｒよりも前の全てのアクセスは確実に完了している（破綻していない）ことになるから、
ｄｅｌａｙ＋Σ〔｛Ｔｅｒｒｏｒ−ＴＭＩＮ（ｊ）｝／ＰＥＲＩＯＤ（ｊ）＋１〕×Ｔａｃｃｅｓｓ（ｊ）
≦Ｔｅｒｒｏｒ  （上記除算は切り捨て。）                              …（数１）
したがって、任意のＴｅｒｒｏｒに対して上記（数１）が成り立てば、各リクエスタのリクエスト周期がそれぞれ所定以上である場合には、何れのリクエストに対しても、優先度制御値が０になるまでに、すなわちリクエストがなされてから所定の応答時間以内に、アクセスが許可されて完了することが保証されることになる。
【００６０】
（２）  第２の破綻パターン
時刻ｔ＝Ｔｅｒｒｏｒよりも前にアクセスが完了するリクエスタ（ｊ）で、優先度制御値Ｐ（ｊ）がＴｅｒｒｏｒ−ｔよりも大きくなるものがある場合
この場合、優先度制御値Ｐ（ｊ）がＴｅｒｒｏｒ−ｔよりも大きくなる最後のリクエストが許可された後の動作だけを考えればよい。より詳しくは、例えば図４に示すように、リクエスタ（ｋ）のリクエストが許可されてアクセスが完了した後、ｔ＝Ｔｅｒｒｏｒまでに、それぞれ最後にアクセスが完了するまでの優先度制御値Ｐ（ｊ）が、Ｔｅｒｒｏｒ−ｔ以下である場合を考慮すればよい。（ここで、同図においては、便宜上、リクエスタ（ｋ）にアクセス許可がなされてから１クロックサイクル後のタイミングをｔ＝０とし、その後（ｄｅｌａｙ−１）だけ経過後からＴａｃｃｅｓｓ（ｋ）の間アクセスが行われるとしている。）
上記のような場合だけを考慮すればよいのは、次のような理由による。
【００６１】
ｔ＝−１より前にリクエストがなされる他のリクエスタ（ｊ）については、その優先度制御値Ｐ（ｊ）が優先度制御値Ｐ（ｋ）よりも小さければ、そのアクセスが完了してからリクエスタ（ｋ）のアクセスが許可されることになる（図４の状態になる）ので考慮する必要がない。一方、優先度制御値Ｐ（ｊ）が優先度制御値Ｐ（ｋ）よりも大きければ、そのリクエスタ（ｊ）がアクセス許可されるのはｔ＝Ｔｅｒｒｏｒ以降のことなので、やはり考慮する必要がない。リクエスタ（ｋ）が同図のアクセス後に再度リクエストする場合も同様である。（なお、上記のことから、ｔ＝０の時点では、リクエスタ（ｋ）以外のリクエスタ（ｊ）によるリクエストがないと考えてよい。）
さらに、リクエスタ（ｋ）のアクセス後に、優先度制御値ＰがＴｅｒｒｏｒ−ｔよりも大きくなる他のリクエスタについても考慮する必要がない。そのようなリクエスタがある場合には、そのリクエスタについて、図４の状態となるので、結局、リクエスタ（ｋ）について代表させて考えればよい。
【００６２】
第２の破綻パターンの場合、上記のようにｔ＝０の時点で、リクエスタ（ｋ）以外のリクエスタ（ｊ）によるリクエストがないと考えてよいので、それらの優先度制御値Ｐ（ｊ）は、それぞれＴＭＩＮ（ｊ）以上になっている（ＴＭＩＮ（ｊ）＋αとする。）。そこで、時刻ｔ＝０〜Ｔｅｒｒｏｒまでにリクエスタごとのアクセスが完了した回数をｎ１（ｊ）とすると、ｔ＝０以降、ｎ１（ｊ）回目のアクセスが完了するまでのＰ（ｊ）は、（１）と同じように考えれば、
Ｐ（ｊ）
＝｛ＴＭＩＮ（ｊ）＋α｝＋｛ｎ１（ｊ）−１｝×ＰＥＲＩＯＤ（ｊ）−ｔ＋Ｔｗａｉｔ（ｊ）
であり、第２の破綻パターンの場合、全てのリクエスタ（ｊ）について、常に
Ｐ（ｊ）≦Ｔｅｒｒｏｒ−ｔ
であるから、
｛ＴＭＩＮ（ｊ）＋α｝＋｛ｎ１（ｊ）−１｝×ＰＥＲＩＯＤ（ｊ）−ｔ＋Ｔｗａｉｔ（ｊ）
≦Ｔｅｒｒｏｒ−ｔ
である。それゆえ、上記アクセス完了回数ｎ１（ｊ）は、
ｎ１（ｊ）
≦｛Ｔｅｒｒｏｒ−ＴＭＩＮ（ｊ）｝／ＰＥＲＩＯＤ（ｊ）＋１
（∵α≧０、Ｔｗａｉｔ（ｊ）≧０）
となる。
【００６３】
一方、やはり（１）と同様に、全リクエスタについてのアクセス時間の総合計（Ｔａｌｌ）は、
Ｔａｌｌ
＝｛ｄｅｌａｙ−１＋Ｔａｃｃｅｓｓ（ｋ）｝＋Σｎ１（ｊ）×Ｔａｃｃｅｓｓ（ｊ）
≦｛ｄｅｌａｙ−１＋Ｔａｃｃｅｓｓ（ｋ）｝＋Σ〔｛Ｔｅｒｒｏｒ−ＴＭＩＮ（ｊ）｝／ＰＥＲＩＯＤ（ｊ）＋１〕×Ｔａｃｃｅｓｓ（ｊ）
である。これがＴｅｒｒｏｒ以下であれば、時刻ｔ＝Ｔｅｒｒｏｒよりも前の全てのアクセスは確実に完了している（破綻していない）ことになるから、
｛ｄｅｌａｙ−１＋Ｔａｃｃｅｓｓ（ｋ）｝＋Σ〔｛Ｔｅｒｒｏｒ−ＴＭＩＮ（ｊ）｝／ＰＥＲＩＯＤ（ｊ）＋１〕×Ｔａｃｃｅｓｓ（ｊ）
≦Ｔｅｒｒｏｒ  （上記除算は切り捨て。またΣ内のｊはｊ＝ｋを除く。）  …（数２）
したがって、任意のＴｅｒｒｏｒに対して上記（数２）が成り立てば、各リクエスタのリクエスト周期がそれぞれ所定以上であれば、何れのリクエストに対しても、優先度制御値が０になるまでに、すなわちリクエストがなされてから所定の応答時間以内に、アクセスが行われることが保証されることになる。
【００６４】
したがって、上記（数１、２）がともに満足されていれば、全ての場合について、優先度制御値が０になることなく調停が行われることを保証できることになる。
【００６５】
ここで、上記（数１、２）は、以上のように本実施形態のアクセス調停装置１００の動作を前提として導出されたものであるが、これらによって調停可能なことが保証されれば、ＥＤＦ手法を用いた他のアクセス調停装置を構成することも可能である。すなわち、何らかの方法で調停可能なことが示されていれば、ＥＤＦ手法のアクセス調停装置でも必ず調停可能なので、上記のような検証は、広く種々のアクセス調停装置における調停可能性の検証に用いることができる。
【００６６】
なお、上記（数１、２）においては≦が用いられて表されている例を示したが、実質的には、クロックタイミングの考慮の仕方などに応じて、＜が用いられた式を条件とするなどしてもよい。
【００６７】
（調停可能条件検証装置について）
次に、上記（数１、２）が利用される設計装置（調停可能条件検証装置）について説明する。この設計装置は、特に限定されないが、例えばコンピュータに、図５に示すような各機能を発揮するソフトウェアを組み込んで構成することができる。
【００６８】
（Ｓ１０１）  まず、例えばアクセス対象となる共有メモリにアクセスする機能ブロックが決定される。
【００６９】
（Ｓ１０２）  各機能ブロックのメモリアクセスに対する要求のパラメータである基準優先値（ＴＭＩＮ）と優先度低下値（ＰＥＲＩＯＤ）、および各機能ブロックのアクセスに要する時間（Ｔａｃｃｅｓｓ）が決定される。これらは、必要とされる応答時間（遅延時間）、リクエスト周期（要求バンド幅）、データ転送能力や入出力速度などに対応するものである。
【００７０】
なお、上記（Ｓ１０１、Ｓ１０２）の決定は外部で行われて、上記パラメータなどだけが入力部から入力されるようにしてもよい。
【００７１】
（Ｓ１０３）  前記（数１、２）を用いて、アクセス調停装置全体の成立性、すなわち、所定数の種々のＴｅｒｒｏｒの値について、これらが成り立つかどうかがチェックされる。
【００７２】
（Ｓ１０４）  調停が破綻するかどうかが判定され、破綻するなら、（Ｓ１０１）に戻って、共有メモリにアクセスする機能ブロックの取捨選択や、調停要求パラメータの変更が行われ、評価が繰り返される。
【００７３】
（Ｓ１０５）  一方、上記（Ｓ１０４）の判定で調停可能と判定されれば、上記パラメータを満足するような各機能ブロックや共有メモリ、メモリバスなどの詳細な回路設計が行われる。これによって、オーバースペックになることもなく最適なシステムが容易に構成できる。なお、設計製造の段階に応じて、シミュレーションや実機デバッグによって、優先度制御値が０になって優先度制御値制御部１０２からエラー信号が出力されるかどうかを確認したりしてもよい。
【産業上の利用可能性】
【００７４】
本発明にかかるアクセス調停装置は、単純な回路で、複数の処理や装置（リクエスタ）がメモリを共有する場合のバス調停などに対して、例えばリアルタイム性とパフォーマンスを両立させ得る効率よい調停を実現できるという効果を有し、メモリインターフェースやタスクの制御などに用いられるアクセス調停装置（アービター）等として有用である。
【図面の簡単な説明】
【００７５】
【図１】図１は、アクセス調停装置の構成を示すブロック図である。
【図２】図２は、調停動作と優先度制御値等の変化との関係の例を示す説明図である。
【図３】図３は、１つの調停可能条件の導出過程を示す説明図である。
【図４】図４は、他の調停可能条件の導出過程を示す説明図である。
【図５】図５は、調停可能条件検証装置の動作を示すフローチャートである。
【符号の説明】
【００７６】
１００      アクセス調停装置
１０１      優先度制御値レジスタ
１０２      優先度制御値制御部
１０３      選択部
１０４      アクセス制御部
２０１・２０２    リクエスタ
２０３      メモリ
【図１】
0004625836.tif 000002
【図２】
0004625836.tif 000003
【図３】
0004625836.tif 000004
【図４】
0004625836.tif 000005
【図５】
0004625836.tif 000006