(57)【要約】【課題】  簡易な構成で、優先順位を確保しつつ全てのバスマスタが必ずリソースにアクセスできるとともに、バス占有率を容易に計算することができるバス調停装置及びバス調停方法を提供すること。【解決手段】  本発明にかかるバス調停回路１００は、バスマスタ１〜６のそれぞれを第１階層ＲＲ１，第２階層ＲＲ２に階層化する階層情報設定部１１１と、第１階層ＲＲ１のバスマスタのいずれかもしくは第２階層ＲＲ２を選択する第１階層選択部１１１と、第１階層選択部１１１が第２階層ＲＲ２を選択した場合に、第２階層ＲＲ２のバスマスタのいずれかを選択する第２階層選択部１１２と、第１階層選択部１１１もしくは第２階層選択部１１２が選択したバスマスタのバスアクセスを許可する選択信号出力部１３０と、を有するものである。【選択図】  図１
2007026022.tif 000002
【特許請求の範囲】
【請求項１】
バスに共通接続された複数のバスマスタのバスアクセスを調停するバス調停装置であって、
前記複数のバスマスタのそれぞれを第１の階層もしくは第２の階層に階層化する階層化部と、
前記第１の階層のバスマスタのいずれかもしくは前記第２の階層を選択する第１の階層選択部と、
前記第１の階層選択部が前記第２の階層を選択した場合に、前記第２の階層のバスマスタのいずれかを選択する第２の階層選択部と、
前記第１もしくは第２の階層選択部が選択したバスマスタのバスアクセスを許可するバスアクセス許可部と、を有する、
バス調停装置。
【請求項２】
前記第１の階層選択部は、ラウンドロビン方式により定まる選択順位にしたがい前記バスマスタのいずれかもしくは第２の階層を選択し、
前記第２の階層選択部は、ラウンドロビン方式により定まる選択順位にしたがい前記バスマスタのいずれかを選択する、
請求項１に記載のバス調停装置。
【請求項３】
前記第１もしくは第２の階層選択部は、前記選択したバスマスタについて、前記ラウンドロビン方式の選択順位を変更する、
請求項２に記載のバス調停装置。
【請求項４】
前記第１の階層は、前記第２の階層よりも優先順位が高い、
請求項１乃至３のいずれか一つに記載のバス調停装置。
【請求項５】
前記第１の階層と前記第２の階層には、同じバスマスタが含まれている、
請求項１乃至４のいずれか一つに記載のバス調停装置。
【請求項６】
前記階層化部は、前記第２の階層に含まれるバスマスタのそれぞれを第１のサブ階層もしくは第２のサブ階層にさらに階層化し、
前記第１の階層選択部は、前記第１の階層のバスマスタのいずれか、前記第１のサブ階層もしくは前記第２のサブ階層を選択し、
前記第２の階層選択部は、前記第１の階層選択部が前記第１のサブ階層を選択した場合に、前記第１のサブ階層のバスマスタのいずれかを選択し、前記第１の階層選択部が前記第２のサブ階層を選択した場合に、前記第２のサブ階層のバスマスタのいずれかを選択する、
請求項１乃至５のいずれか一つに記載のバス調停装置。
【請求項７】
前記第１のサブ階層と前記第２のサブ階層には、同じバスマスタが含まれている、
請求項６に記載のバス調停装置。
【請求項８】
バスに共通接続された複数のバスマスタのバスアクセスを調停するバス調停方法であって、
前記複数のバスマスタのそれぞれを第１の階層もしくは第２の階層に階層化し、
前記第１の階層のバスマスタのいずれかもしくは前記第２の階層を選択し、
前記第２の階層が選択された場合に、前記第２の階層のバスマスタのいずれかを選択し、
前記選択された前記第１もしくは第２の階層のバスマスタのバスアクセスを許可する、
バス調停方法。
【請求項９】
前記第１の階層のバスマスタもしくは前記第２の階層の選択は、ラウンドロビン方式により定まる選択順位にしたがい前記バスマスタのいずれかもしくは第２の階層を選択し、
前記第２の階層のバスマスタの選択は、ラウンドロビン方式により定まる選択順位にしたがい前記バスマスタのいずれかを選択する、
請求項８に記載のバス調停方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、バスアクセス調停装置及びバスアクセス調停方法に関し、特に、複数のバスマスタのバスアクセスを調停するバス調停装置及びバス調停方法に関する。
【背景技術】
【０００２】
従来から、種々のデータを処理するデータ処理システムでは、複数のデバイスが１つのバスに共通に接続され、特定のデバイスのみがバスを占有しデータ転送等のバスアクセスを行っている。データ処理システムには、バス調停回路（バスアービタ）が設けられており、このバス調停回路によって、各デバイスのバスアクセスが調停されバスを占有するための占有権が与えられる。バスアクセスをバス調停回路に要求しバスの占有権の取得するデバイスをバスマスタと呼んでいる。
【０００３】
例えば、複数のＣＰＵを接続するＣＰＵバスや複数のＤＭＡ（Direct Memory Access）を接続するＤＭＡ転送用バス等のように、複数のバスマスタが存在しバスマスタが１つのリソース（バススレーブ）にアクセスするようなシステムでは、バス調停回路が、所定の方式にしたがって、バスマスタからのバスアクセス要求を調停し、バスマスタにバス占有権を割り当てている。
【０００４】
バス調停回路がバスアクセス要求を調停する方式として、ラウンドロビン方式と固定優先順位方式が知られている。
【０００５】
ラウンドロビン方式は、所定の順序にしたがい各バスマスタに同じ割合でバス占有権を与える方式である。一般的なラウンドロビン方式では、複数のバスマスタをあらかじめ決められた順番に処理していく為、すべてのバスマスタが公平にアクセスすることはできるが、各バスマスタの優先順位を設定することはできない。
【０００６】
固定優先順位方式は、バスマスタの重要度に沿った優先順位にしたがい各バスマスタにバス占有権を与える方式である。一般的な固定優先順位方式では、優先順位の高いバスマスタからバスアクセス要求がある間はこのバスマスタがバスを占有し続けてしまうため、優先順位の低いバスマスタは待たされ、その間リソースにアクセスすることができない。そうすると、各バスマスタのデータ転送等が正常に行われなくなり、システムが破綻してしまう場合がある。
【０００７】
このようにシステムの破綻を防ぐ為、優先順位を確保し、且つ全てのバスマスタがリソースにアクセスすることの出来るバス制御方法が必要である。また、バスの最適化を行う為、システム設計時に各バスマスタのバス占有率を正確に求める必要もある。
【０００８】
そこで、各バスマスタのバス占有率が容易に計算でき、且つ、優先順位の高低に関わらず、全てのバスマスタが、必ずリソースにアクセスできる制御方法が必要である。
【０００９】
従来のバス調停回路として、特許文献１が知られている。図８は、特許文献１と同様の従来のバス調停回路を有するデータ処理システムの構成を示している。
【００１０】
従来のデータ処理システムでは、バスマスタ９２０ａ，９２０ｂとリソース９３０は、それぞれバス９４０に共通に接続されている。バス調停回路９１０は、バスマスタ９２０ａ，９２０ｂからのバスアクセス要求を調停し、バスマスタ９２０ａもしくはバスマスタ９２０ｂのいずれかにバス占有権を与える。バスマスタ９２０ａ，９２０ｂは、バス調停回路９１０からバスアクセスを許可されバス占有権を与えられると、バス９４０を介してリソース９３０との間でデータ転送を行う。
【００１１】
バスマスタ９２０ａ，９２０ｂは、図に示すように、それぞれプライオリティ情報（優先度情報）を生成するプライオリティ生成部９２１ａ，９２１ｂを備え、バスマスタ９２０ａ，９２０ｂは、バス調停回路９１０にリクエスト（バスアクセス要求）とプライオリティ情報をバス調停回路９１０に出力する。
【００１２】
バス調停回路９１０は、図に示すように、プライオリティチェック部９１１とラウンドロビン選択部９１２を有している。プライオリティチェック部９１１は、各バスマスタから与えられるプライオリティ情報をチェックし、優先順位の一番高いプライオリティ情報を出力しているバスマスタ、すなわち優先順位の一番高いバスマスタを検出し、そのチェック結果（検出結果）をラウンドロビン選択部９１２へ出力する。
【００１３】
ラウンドロビン選択部９１２では、前回の調停動作の結果を保持しており、プライオリティチェック部９１１のチェック結果と、前回の調停結果とから生成したラウンドロビン順位に基づいて、リクエスト選択信号を生成して、それぞれのバスマスタに出力する。
【００１４】
このリクエスト選択信号によりバスアクセスが受け付けられたバスマスタ９２０ａ，９２０ｂでは、バスを占有してデータ転送を行うと同時に、プライオリティ生成部９２１ａ，９２１ｂにおいて、当該バスマスタのプライオリティ情報をランクダウンする。また、リクエスト選択信号によりバスアクセスが受け付けられなかったバスマスタ９２０ａ，９２０ｂでは、プライオリティ生成部９２１ａ，９２１ｂにおいて、当該バスマスタのプライオリティ情報をランクアップする。すなわち、プライオリティ生成部９２１ａ，９２１ｂは、バスアクセスに応じてプライオリティを変更し、各バスマスタの優先順位を切り替えている。
【００１５】
このように従来のバス調停回路では、動的に変更される優先順位に応じたラウンドロビン制御を行うことにより、優先順位を保ちつつ、各バスマスタの公平化を可能にしている。
【００１６】
尚、その他の従来のバス調停回路として特許文献２が知られている。特許文献２では、複数のバスマスタをグループ化し、グループ内のバスマスタ間をラウンドロビン方式により調停し、グループ間を固定優先順位方式により調停している。したがって、優先度の高いグループが選択されている間は、優先度の低いグループはバスを使用することはできない。
【特許文献１】特開２００４−１７８０５６号公報
【特許文献２】特開２００３−３０１３４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１７】
しかしながら、図８の従来のデータ処理システムでは、各バスマスタにプライオリティ情報を生成するプライオリティ生成部９２１ａ，９２１ｂが必要であり、バス調停回路９２１０にプライオリティ情報をチェックするプライオリティチェック部９１１が必要となる。
【００１８】
プライオリティ生成部９２１ａ，９２１ｂは、ソフトウェアで制御されており、ソフトウェアによりリクエストの割り込みが受け付けられたかを判断し、リクエストが受け付けられなかった場合にはプライオリティ値を段階的に優先度をランクアップする制御を行うとともに、プライオリティ情報をバス調停回路９１０に出力する。また、プライオリティ生成部９２１ａ，９２１ｂは、全バスマスタに設けられ、バスマスタ毎に処理を行うため、バスマスタ数に応じてプライオリティ生成部の数も多くなってしまう。
【００１９】
このように従来技術では、優先順位を動的に変化させるプライオリティ制御とラウンドロビン制御の２つの制御方式を組み合わせてバスマスタの優先順位を固定させている。このため、バス調停回路９１０のプライオリティチェック部９１１とバスマスタ９２０ａ，９２０ｂのプライオリティ生成部９２１ａ，９２１ｂが必要となり、回路構成が複雑になるという問題がある。
【００２０】
また、プライオリティ生成部９２１ａ，９２１ｂでは、ソフトウェア制御が必要なため、バス占有率の計算はハードウェアとソフトウェアの両方に依存してしまう。したがって、バス占有率の計算は、ハードウェアの動作とソフトウェアの動作を考慮する必要があるため、その計算を行うのは非常に困難であり、システム設計時に、バス占有率を正確に計算することができないという問題がある。
【課題を解決するための手段】
【００２１】
本発明にかかるバス調停装置は、バスに共通接続された複数のバスマスタのバスアクセスを調停するバス調停装置であって、前記複数のバスマスタのそれぞれを第１の階層もしくは第２の階層に階層化する階層化部と、前記第１の階層のバスマスタのいずれかもしくは前記第２の階層を選択する第１の階層選択部と、前記第１の階層選択部が前記第２の階層を選択した場合に、前記第２の階層のバスマスタのいずれかを選択する第２の階層選択部と、前記第１もしくは第２の階層選択部が選択したバスマスタのバスアクセスを許可するバスアクセス許可部と、を有するものである。
【００２２】
このバス調停装置によれば、複数のバスマスタを階層化し、１つの階層を選択する際に、バスマスタもしくは他の階層を選択することにより、全てのバスマスタが必ず選択されるようになる。これにより、簡易な構成で、優先順位を確保しつつ全てのバスマスタがリソースにアクセスすることができるとともに、バス占有率を容易に計算することができる。
【００２３】
本発明にかかるバス調停方法は、バスに共通接続された複数のバスマスタのバスアクセスを調停するバス調停方法であって、前記複数のバスマスタのそれぞれを第１の階層もしくは第２の階層に階層化し、前記第１の階層のバスマスタのいずれかもしくは前記第２の階層を選択し、前記第２の階層が選択された場合に、前記第２の階層のバスマスタのいずれかを選択し、前記選択された前記第１もしくは第２の階層のバスマスタのバスアクセスを許可するものである。
【００２４】
このバス調停方法によれば、複数のバスマスタを階層化し、１つの階層を選択する際に、バスマスタもしくは他の階層を選択することにより、全てのバスマスタが必ず選択されるようになる。これにより、簡易な構成で、優先順位を確保しつつ全てのバスマスタがリソースにアクセスすることができるとともに、バス占有率を容易に計算することができる。
【発明の効果】
【００２５】
本発明によれば、簡易な構成で、優先順位を確保しつつ全てのバスマスタが必ずリソースにアクセスできるとともに、バス占有率を容易に計算することができるバス調停装置及びバス調停方法を提供することができる。
【発明を実施するための最良の形態】
【００２６】
発明の実施の形態１．
まず、本発明の実施の形態１にかかるバスアクセス調停装置及びバスアクセス調停方法について説明する。本実施形態は、階層化したラウンドロビン方式によりバスの調停を行うことを特徴としている。
【００２７】
ここで、図１及び図２を用いて、本実施形態にかかるデータ処理システム及びバス調停回路の構成について説明する。図１に示されるように、このデータ処理システムは、バスマスタ１〜６、バス調停回路１００、リソース２００を備えており、バスマスタ１〜６とリソース２００は、それぞれバス２１０に共通に接続されている。
【００２８】
バスマスタ１〜６はバス２１０を使用する際、バス調停回路１００にバスのアクセス要求であるリクエストＲ１〜Ｒ６をそれぞれ出力する。そして、バス調停回路１００からリクエスト選択信号ＳＳ１〜ＳＳ６によってそれぞれ選択されたバスマスタは、バスの占有権を与えられたと判断し、バス２１０にアクセスしてリソース２００とデータ転送等を行う。
【００２９】
リソース２００はバスマスタからアクセスされるバススレーブであり、例えば、ＲＡＭなどのメモリである。バスマスタ１〜６は、メモリに格納されたプログラムの実行等を行うＣＰＵや、外部データをメモリと直接やり取りするＤＭＡ等である。
【００３０】
バス調停回路（バス調停装置）１００は、バスマスタのバスアクセスを調停する。つまり、バス調停回路１００は、バスマスタ１〜６のリクエストを階層化されたラウンドロビン方式により調停しバスマスタの選択を行う。例えば、バス調停回路１００は、図２に示されるように、階層化ラウンドロビン選択部１１０、リクエスト入力部１２０、選択信号出力部１３０、階層情報設定部１４０から構成されている。
【００３１】
リクエスト入力部１２０は、バスマスタ１〜６からリクエストＲ１〜Ｒ６を受け取る。複数のバスマスタから同時にリクエストを受け取った場合には、それぞれのリクエストを選択待ちキューなどに格納し、調停されるまでリクエストを保持する。
【００３２】
階層情報設定部１４０は、各バスマスタをそれぞれ複数の階層に階層化する階層化部である。すなわち、階層情報設定部１４０は、各階層に属するバスマスタや階層を設定する。例えば、階層情報設定部１４０は、メモリ等を有し、各バスマスタ（リクエスト）の優先順位や、各バスマスタ（リクエスト）が属する階層、各バスマスタ（リクエスト）のラウンドロビン順位等を記憶している。
【表１】
2007026022.tif 000003
【００３３】
この表１は、階層情報設定部１４０に設定された各リクエストの優先順位の例である。優先順位の数が小さい方が、優先順位が高い。この例では、リクエストＲ１，Ｒ２が１番高い優先順位であり、リクエストＲ３，Ｒ４が２番目の優先順位であり、リクエストＲ５，Ｒ６が３番目の優先順位である。
【表２】
2007026022.tif 000004
【００３４】
この表２は、階層情報設定部１４０に設定された各リクエストと各階層のラウンドロビン順位の例である。ラウンドロビン順位とは、ラウンドロビン方式により選択する順番である。例えば、第１階層ＲＲ１では、リクエストＲ１、リクエストＲ２、第２階層ＲＲ２の順に選択される。第２階層ＲＲ２では、リクエストＲ３、リクエストＲ４、第２階層ＲＲ３の順に選択される。第３階層ＲＲ３では、リクエストＲ５、リクエストＲ６の順に選択される。
【００３５】
階層化ラウンドロビン選択部１１０は、リクエスト入力部１２０に入力されたリクエストが競合した場合、階層情報設定部１４０に設定された各階層ごとにラウンドロビン方式にしたがいリクエスト（バスマスタ）のいずれかを選択する。
【００３６】
選択信号出力部１３０は、階層化ラウンドロビン選択部１１０により選択されたリクエストに対応するリクエスト選択信号ＳＳ１〜ＳＳ６のいずれかを出力する。すなわち、選択信号出力部１３０は、選択されたバスマスタのバスアクセスを許可し、バス占有権を与えるバスアクセス許可部である。
【００３７】
さらに、図１に示すように、階層化ラウンドロビン選択部１１０は、第１階層ＲＲ１、第２階層ＲＲ２、第３階層ＲＲ３の各階層の選択処理を行う第１階層選択部１１１、第２階層選択部、第３階層選択部１１３を有している。この階層と各リクエストの対応は、階層情報設定部１４０に設定されており、上記の表２と同様である。優先順位は上記の表１の通りであり、第１階層ＲＲ１の優先順位が最も高く、第３階層ＲＲ３の優先順位が最も低い。すなわち、上位の階層の優先順位が高く、下位の階層の優先順位が低い。
【００３８】
第１階層選択部１１１は、第１階層ＲＲ１に含まれるリクエストＲ１、リクエストＲ２、第２階層ＲＲ２のいずれかを選択する。第２階層選択部１１２は、第１階層選択部１１１が第２階層ＲＲ２を選択した場合に、第２階層ＲＲ２に含まれるリクエストＲ３、リクエストＲ４、第３階層ＲＲ３のいずれかを選択する。第３階層選択部１１３は、第２階層選択部１１２が第３階層ＲＲ３を選択した場合に、第３階層ＲＲ３に含まれるリクエストＲ５、リクエストＲ６のいずれかを選択する。
【００３９】
第１階層選択部１１１、第２階層選択部１１２、第３階層選択部１１３は、それぞれ、ラウンドロビン方式により定まる選択順位にしたがって、リクエストや下位の階層を選択する。すなわち、各階層選択部は、上記の表２に設定されたラウンドロビン順位にしたがって選択を行う。
【００４０】
次に、図３のフローチャートを用いて、本実施形態にかかるバス調停方法について説明する。図３は、図１のバス調停回路１００におけるバスの調停方法を示している。例えば、バスマスタ１〜６からリクエストＲ１〜Ｒ６がそれぞれバス調停回路１００に出力されると、リクエスト入力部１２０に各リクエストが入力されて、以下の処理が行われる。
【００４１】
まず、階層化ラウンドロビン選択部１１０は、リクエストの競合判定を行う(ステップＳ１)。ステップＳ１の判定結果が'ＮＯ'の場合、すなわち、バスマスタからのリクエストが競合していない場合、階層化ラウンドロビン選択部１１０は、このリクエストを選択し、選択信号出力部１３０からこのリクエストに対応するバスマスタにリクエスト選択信号を出力する(ステップＳ７)。これにより、リクエスト選択信号を受けたバスマスタは、バス占有権を取得し、リソース２００へのアクセスが可能になる。尚、リクエストが競合していない場合には、ステップＳ８のラウンドロビン順位の変更を行わなくてよい。
【００４２】
また、ステップＳ１の判定結果が'ＹＥＳ'の場合、すなわち、バスマスタからのリクエストが競合している場合、階層化ラウンドロビン選択部１１０は、次のステップＳ２〜Ｓ６で上位の階層から順にバスの調停処理を行う。つまり、階層化ラウンドロビン選択部１１０は、各階層選択部により階層順に処理され、各階層でラウンドロビン方式によりリクエストもしくは次の階層が選択される。
【００４３】
バスの調停処理では、まず、第１階層選択部１１１は、第１階層ＲＲ１のバスの調停を行う（ステップＳ２）。すなわち、第１階層選択部１１１は、表２のラウンドロビン順位にしたがって、第１階層ＲＲ１において、ラウンドロビン順位が最上位（順位が１）であるリクエストＲ１，Ｒ２又は第２階層ＲＲ２のいずれかを選択する。
【００４４】
次いで、第１階層選択部１１１は、ステップＳ２で選択した結果が、階層(第２階層ＲＲ２)であるか判定する(ステップＳ３）。ステップＳ３の判定結果が'ＮＯ'の場合、すなわち、ステップＳ２において階層ではなくリクエストを選択していた場合、第１階層選択部１１１は、第１階層ＲＲ１で調停されたリクエストを選択し、選択信号出力部１３０からこのリクエストに対応するバスマスタにリクエスト選択信号を出力する(ステップＳ７)。
【００４５】
そして、第１階層選択部１１１は、ラウンドロビン順位の変更を行う（ステップＳ８）。すなわち、第１階層選択部１１１は、選択したリクエストのラウンドロビン順位を最下位にし、他のリクエストのラウンドロビン順位を一つランクアップする。
【００４６】
また、ステップＳ３の判定結果が'ＹＥＳ'の場合、すなわち、ステップＳ２において第２階層ＲＲ２を選択していた場合、第２階層選択部１１２は、第２階層ＲＲ２のバスの調停を行う（ステップＳ４）。すなわち、第２階層選択部１１２は、表２のラウンドロビン順位にしたがって、第２階層ＲＲ２において、ラウンドロビン順位が最上位（順位が１）であるリクエストＲ３，Ｒ４又は第３階層ＲＲ３のいずれかを選択する。
【００４７】
次いで、第２階層選択部１１２は、ステップＳ４で選択した結果が、階層(第３階層ＲＲ３)であるか判定する(ステップＳ５）。ステップＳ５の判定結果が'ＮＯ'の場合、すなわち、ステップＳ４において階層ではなくリクエストを選択していた場合、第２階層選択部１１２は、第２階層ＲＲ２で調停されたリクエストを選択し、選択信号出力部１３０からこのリクエストに対応するバスマスタにリクエスト選択信号を出力する(ステップＳ７)。そして、第２階層選択部１１２は、ラウンドロビン順位の変更を行う（ステップＳ８）。
【００４８】
また、ステップＳ５の判定結果が'ＹＳＥ'の場合、すなわち、ステップＳ４において第３階層ＲＲ３を選択していた場合、第３階層選択部１１３は、第３階層ＲＲ３のバスの調停を行う(ステップＳ６)。すなわち、第３階層選択部１１３は、表２のラウンドロビン順位にしたがって、第３階層ＲＲ３において、ラウンドロビン順位が最上位（順位が１）であるリクエストＲ５，Ｒ６のいずれかを選択する。
【００４９】
次いで、第３階層選択部１１３は、第３階層ＲＲ３で調停されたリクエストを選択し、選択信号出力部１３０からこのリクエストに対応するバスマスタにリクエスト選択信号を出力する(ステップＳ７)。そして、第３階層選択部１１３は、ラウンドロビン順位の変更を行う（ステップＳ８）。
【００５０】
尚、ステップＳ７，Ｓ８の後、まだ選択していないリクエストがリクエスト入力部１２０に残っている場合、ステップＳ１以下の処理を繰り返し行う。
【００５１】
このように、本実施形態では、選択されたリクエストのラウンドロビン順位を最下位にして、他のリクエストのラウンドロビン順位を一つランクアップさせる動作を階層毎に行う。すなわち、階層毎にラウンドロビン制御を行っている。
【００５２】
次の表３は、図３の動作でリクエストＲ１〜Ｒ６が連続１８回競合した場合のラウンドロビン順位の動作と選択されるリクエストを示している。
【表３】
2007026022.tif 000005
【００５３】
表３において、それぞれの数字が各リクエストのラウンドロビン順位を示しており、丸の付された数字が選択されたリクエストである。表３の動作を図３のフローチャートの各ステップと対応付けて説明する。
まず、１回目のアクセスでは、第１階層ＲＲ１で順位が１のリクエストＲ１が選択される（ステップＳ２）。そして、リクエストＲ１のラウンドロビン順位が３、リクエストＲ２のラウンドロビン順位が１、第２階層ＲＲ２のラウンドロビン順位が２に変更される（ステップＳ８）。２回目のアクセスでも同様に、リクエストＲ２が選択され、ラウンドロビン順位が変更される。
【００５４】
次いで、３回目のアクセスでは、第１階層ＲＲ１で順位が１の第２階層ＲＲ２が選択され（ステップＳ２）、第２階層ＲＲ２で順位が１のリクエストＲ３が選択される（ステップＳ４）。そして、第１階層ＲＲ１のラウンドロビン順位が変更されるとともに、リクエストＲ３のラウンドロビン順位が３、リクエストＲ４のラウンドロビン順位が１、第３階層ＲＲ３のラウンドロビン順位が２に変更される（ステップＳ８）。
【００５５】
次いで、４，５，６回目のアクセスでは、１，２，３回目のアクセスと同様に第１階層ＲＲ１のリクエストＲ１，Ｒ２、第２階層ＲＲ２のリクエストＲ４が選択され、選択ごとにラウンドロビン順位が変更される。
【００５６】
次いで、７，８回目のアクセスで第１階層ＲＲ１のリクエストＲ１，Ｒ２が選択された後、９回目のアクセスでは、第１階層ＲＲ１で順位が１の第２階層ＲＲ２が選択され（ステップＳ２）、第２階層ＲＲ２で順位が１の第３階層が選択され（ステップＳ４）、第３階層ＲＲ３で順位が１のリクエストＲ５が選択される（ステップＳ６）。そして、第１階層ＲＲ１，第２階層ＲＲ２のラウンドロビン順位が変更されるとともに、リクエストＲ５のラウンドロビン順位が２、リクエストＲ６のラウンドロビン順位が１に変更される（ステップＳ８）。
【００５７】
次いで、１０〜１８回目のアクセスでは、１〜９回目のアクセスと同様に、第１階層ＲＲ１のリクエストＲ１，Ｒ２、第２階層ＲＲ２のリクエストＲ３が選択された後、第１階層ＲＲ１のリクエストＲ１，Ｒ２、第２階層ＲＲ２のリクエストＲ４が選択された、さらに、第１階層ＲＲ１のリクエストＲ１，Ｒ２、第３階層ＲＲ３のリクエストＲ６が選択される。
【００５８】
表３の動作からもわかる通り、全てのバスマスタからリクエストが発生している場合には、各リクエストが決められた確率で選択されるため、バス占有率を容易に計算することができる。この場合のバス占有率の計算式を以下の式１−１〜式１−３に示す。
優先順位１のバス占有率＝（１／第１階層のリクエスト数）×１００      （式１−１）
優先順位２のバス占有率＝（１／第１階層のリクエスト数×第２階層のリクエスト数）×１００      （式１−２）
優先順位３のバス占有率＝（１／第１階層のリクエスト数×第２階層のリクエスト数×第３階層のリクエスト数）×１００      （式１−３）
【００５９】
次の表４は、この式１−１〜１−３によりバス占有率を計算した例を示している。優先順位が高いリクエストのバス占有率が高くなっている。
【表４】
2007026022.tif 000006
【００６０】
尚、上記の説明では、全体のバスマスタ数を６、ラウンドロビンの階層数を３、階層内のバスマスタ数を２、階層内の次の階層を１としたが、これらの数はその他の任意の数でもよい。この設定を変更することで、バスの占有率を調整することができる。図４のデータ処理システムは、バス２１０に複数のバスマスタ１〜Ｎ(Ｎは整数)を接続し、ラウンドロビンの階層数をＮ個とした例である。各バスマスタからのリクエストＲ１〜ＲＮ（Ｎは整数）は、階層化ラウンドロビン選択部１１０の各階層選択部で処理される。すなわち、第１階層選択部１１１と第２階層選択部１１２は、図１と同様である。第３階層選択部１１３は、第３階層ＲＲ３に含まれるリクエストＲ５、リクエストＲ６、第４階層ＲＲ４のいずれかを選択する。第Ｎ階層選択部１１Ｎは、第Ｎ−１階層選択部が第Ｎ階層ＲＲＮを選択した場合に、第Ｎ階層ＲＲＮに含まれるリクエストＲＮ、リクエストＲＮ−１のいずれかを選択する。
【００６１】
この場合のバス調停方法も図３と同様である。すなわち、各バスマスタからのリクエストが競合した場合、第１階層ＲＲ１〜第Ｎ階層ＲＲＮの順に処理され、各階層でラウンドロビン方式によりリクエストもしくは次の階層が選択される。
【００６２】
また、この場合のバス占有率も、上記と同様に以下の式２−１〜２−Ｎにより計算することができる。
優先順位１のバス占有率＝（１／第１階層のリクエスト数）×１００      （式２−１）
優先順位２のバス占有率＝（１／第１階層のリクエスト数×第２階層のリクエスト数）×１００      （式２−２）
優先順位３のバス占有率＝（１／第１階層のリクエスト数×第２階層のリクエスト数×第３階層のリクエスト数）×１００      （式２−３）
：
：
優先順位Ｎのバス占有率＝（１／第１階層のリクエスト数×第２階層のリクエスト数×第３階層のリクエスト数×...×第Ｎ階層のリクエスト数）×１００      （式２−Ｎ）
【００６３】
以上のように、本実施形態では、バスを調停する方式として、各バスマスタ（リクエスト）を階層化し、各階層でラウンドロビン方式により選択を行うことにより、階層ごとの優先順位を確保することができるとともに、優先順位の低いバスマスタでも必ず選択されるため、全てのバスマスタがリソースにアクセスすることができ、システムの破綻を防止することができる。
【００６４】
また、優先度を動的に変更するための回路が必要ないため、回路規模の増大を抑止することができる。さらに、ソフトウェアやハードウェアにより動的にバスを使用する確率が変動しないため、バス占有率も容易かつ正確に計算することが可能となる。
【００６５】
発明の実施の形態２．
次に、本発明の実施の形態２にかかるバスアクセス調停装置及びバスアクセス調停方法について説明する。本実施形態は、同じ優先度のバスマスタ（リクエスト）を含む階層を複数設けて、バスの調停を行うことを特徴としている。
【００６６】
本実施形態のデータ処理システム全体の構成やバス調停回路の構成は、実施の形態１と同様である。図５は、本実施形態にかかる階層化ラウンドロビン選択部１１０の構成を示している。この例では、ラウンドロビンの階層を４層とし、第２階層ＲＲ２と第３階層ＲＲ３に同じリクエストが含まれている。
【００６７】
各階層選択部は、ラウンドロビン方式によりリクエストや下位の階層を選択し、第１階層選択部１１１と第２階層選択部１１２は、図１と同じである。第３階層選択部１１３は、第２階層選択部１１２が第３階層ＲＲ３を選択した場合に、第３階層ＲＲ３に含まれるリクエストＲ３、リクエストＲ４、第４階層ＲＲ３のいずれかを選択する。第４階層選択部１１４は、第３階層選択部１１３が第４階層ＲＲ４を選択した場合に、第４階層ＲＲ４に含まれるリクエストＲ５、リクエストＲ６のいずれかを選択する。
【００６８】
この場合のバス調停方法も図３と同様である。すなわち、各バスマスタからのリクエストが競合した場合、第１階層ＲＲ１〜第４階層ＲＲ４の順に処理され、各階層でラウンドロビン方式によりリクエストもしくは次の階層が選択される。
【００６９】
また、この場合のバス占有率も、上記と同様に以下の式３−１〜３−Ｎにより計算することができる。
優先順位１のバス占有率＝（１／第１階層のリクエスト数）×１００      （式３−１）
優先順位２のバス占有率＝（１／第１階層のリクエスト数×第２階層のリクエスト数）×１００＋（１／第１階層のリクエスト数×第２階層のリクエスト数×第３の階層リクエスト数）×１００      （式３−２）
優先順位３のバス占有率＝（１／第１階層のリクエスト数×第２階層のリクエスト数×第３階層のリクエスト数×第４階層のリクエスト数）×１００      （式３−３）
【００７０】
次の表５は、この式３−１〜３−３によりバス占有率を計算した例を示している。表５では、表４と比べて、リクエストＲ３，Ｒ４のバス占有率が高く、リクエストＲ５，Ｒ６のバス占有率が低くなっている。
【表５】
2007026022.tif 000007
【００７１】
このように、同じ優先順位のリクエストＲ３とリクエストＲ４を第２階層ＲＲ２と第３階層ＲＲ３に配置することによって、優先順位が２番目のバス占有率をより高くし、優先順位が３番目のバス占有率をより低く設定することが可能である。したがって、同じ優先順位のリクエストを他階層に配置することで、各リクエストのバス占有率をさらに詳細に調整することができる。その結果、システムに適したバス占有率を設定でき、システムの破綻を効率よく防止することが可能である。
【００７２】
発明の実施の形態３．
次に、本発明の実施の形態３にかかるバスアクセス調停装置及びバスアクセス調停方法について説明する。本実施形態は、同じ階層に複数のサブ階層（グループ）を設けて、バスの調停を行うことを特徴としている。
【００７３】
本実施形態のデータ処理システム全体の構成やバス調停回路の構成は、実施の形態１と同様である。図６は、本実施形態にかかる階層化ラウンドロビン選択部１１０の構成を示している。この例では、ラウンドロビンの階層を２層とし、第２階層を２つのサブ階層（グループ）の第２階層ＲＲ２１と第２階層ＲＲ２２としている。
【００７４】
この階層化ラウンドロビン選択部１１０では、上記の例と同様に、各階層選択部は、ラウンドロビン方式によりリクエストや下位の階層を選択する。そしてここでは、第１階層選択部１１１は、第１階層ＲＲ１に含まれるリクエストＲ１、第２階層ＲＲ２１、第２階層ＲＲ２２のいずれかを選択する。第２階層選択部１１２ａは、第１階層選択部１１１が第２階層ＲＲ２１を選択した場合に、第２階層ＲＲ２１に含まれるリクエストＲ２、リクエストＲ３、リクエストＲ４のいずれかを選択する。第２階層選択部１１２ｂは、第１階層選択部１１１が第２階層ＲＲ２２を選択した場合に、第２階層ＲＲ２２に含まれるリクエストＲ２、リクエストＲ３のいずれかを選択する。
【００７５】
ここで第２階層に含まれるリクエストＲ２とリクエストＲ３は同じ優先順位であり、リクエストＲ４は、リクエストＲ２，Ｒ３よりも低い優先順位である。すなわち、第２階層には、優先順位の高いリクエストＲ２，Ｒ３が、優先順位の低いリクエストＲ４よりも多く含まれている。
【００７６】
次に、図７のフローチャートを用いて、本実施形態にかかるバス調停方法について説明する。図７は、図６の階層化ラウンドロビン選択部１１０におけるバスの調停方法を示している。例えば、バスマスタ１〜４からリクエストＲ１〜Ｒ４がバス調停回路１００に出力されると、リクエスト入力部１２０に各リクエストが入力されて、以下の処理が行われる。
【００７７】
まず、階層化ラウンドロビン選択部１１０は、リクエストの競合判定を行う(ステップＳ２１)。ステップＳ２１の判定結果が'ＮＯ'の場合、すなわち、バスマスタからのリクエストが競合していない場合、階層化ラウンドロビン選択部１１０は、このリクエストを選択し、選択信号出力部１３０からこのリクエストに対応するバスマスタにリクエスト選択信号を出力する(ステップＳ２７)。尚、リクエストが競合していない場合には、ステップＳ２８のラウンドロビン順位の変更を行わなくてよい。
【００７８】
また、ステップＳ２１の判定結果が'ＹＥＳ'の場合、すなわち、バスマスタからのリクエストが競合している場合、階層化ラウンドロビン選択部１１０は、次のステップＳ２２〜Ｓ２６で上位の階層から順にバスの調停処理を行う。つまり、階層化ラウンドロビン選択部１１０は、各階層選択部により階層順に処理され、各階層でラウンドロビン方式によりリクエストもしくは次の階層が選択される。
【００７９】
バスの調停処理では、まず、第１階層選択部１１１は、第１階層ＲＲ１のバスの調停を行う(ステップＳ２２)。すなわち、第１階層選択部１１１は、第１階層ＲＲ１において、ラウンドロビン順位が最上位（順位が１）であるリクエストＲ１、第２階層ＲＲ２１又は第２階層ＲＲ２２のいずれかを選択する。
【００８０】
次いで、第１階層選択部１１１は、ステップＳ２２で選択した結果が、階層(第２階層ＲＲ２１)であるか判定する(ステップＳ２３)。ステップＳ２３の判定結果が'ＹＥＳ'の場合、すなわち、ステップＳ２２において第２階層ＲＲ２１を選択していた場合、第２階層選択部１１２ａは、第２階層ＲＲ２１のバスの調停を行う（ステップＳ２４）。すなわち、第２階層選択部１１２ａは、第２階層ＲＲ２１において、ラウンドロビン順位が最上位（順位が１）であるリクエストＲ２，Ｒ３，Ｒ４のいずれかを選択する。そして、選択信号出力部１３０からこのリクエストに対応するバスマスタにリクエスト選択信号を出力する(ステップＳ２７)。さらに、第２階層選択部１１２ａは、ラウンドロビン順位の変更を行う（ステップＳ２８）。
【００８１】
ステップＳ２３の判定結果が'ＮＯ'の場合、すなわち、ステップＳ２２において第２階層ＲＲ２１を選択していない場合、第１階層選択部１１１は、ステップＳ２２で選択した結果が、階層(第２階層ＲＲ２２)であるか判定する(ステップＳ２５)。ステップＳ２５の結果が'ＹＥＳ'の場合、すなわち、ステップＳ２２において第２階層ＲＲ２２を選択していた場合、第２階層選択部１１２ｂは、第２階層ＲＲ２２のバスの調停を行う（ステップＳ２６）。すなわち、第２階層選択部１１２ｂは、第２階層ＲＲ２２において、ラウンドロビン順位が最上位（順位が１）であるリクエストＲ２，Ｒ３のいずれかを選択する。そして、選択信号出力部１３０からこのリクエストに対応するバスマスタにリクエスト選択信号を出力する(ステップＳ２７)。さらに、第２階層選択部１１２ｂは、ラウンドロビン順位の変更を行う（ステップＳ２８）。
【００８２】
ステップＳ２５の判定結果が'ＮＯ'の場合、すなわち、ステップＳ２２において階層ではなくリクエストを選択していた場合、第１階層選択部１１１は、第１階層ＲＲ１で調停されたリクエストを選択し、選択信号出力部１３０からこのリクエストに対応するバスマスタにリクエスト選択信号を出力する(ステップＳ２７)。そして、第１階層選択部１１１は、ラウンドロビン順位の変更を行う（ステップＳ２８）。
【００８３】
尚、ステップＳ２７，Ｓ２８の後、まだ選択していないリクエストがリクエスト入力部１２０に残っている場合、ステップＳ２１以下の処理を繰り返し行う。
【００８４】
この場合のバス占有率は、以下の式４−１〜４−３で容易に計算することができる。
優先順位１のバス占有率＝（１／第１階層リクエスト数）×１００      （式４−１）
優先順位２のバス占有率＝  （１／第１階層リクエスト数×第２階層ＲＲ２１リクエスト数）×１００＋（１／第１階層リクエスト数×第２階層ＲＲ２２リクエスト数）×１００      （式４−２）
優先順位３のバス占有率＝  （１／第１階層リクエスト数×第２階層ＲＲ２２リクエスト数）×１００      （式４−３）
【００８５】
次の表６は、この式４−１〜４−３によりバス占有率を計算した例を示している。第２階層でも優先順位の高いリクエストＲ２，Ｒ３のバス占有率が高く、優先順位の低いリクエストＲ４のバス占有率が低くなっている。
【表６】
2007026022.tif 000008
【００８６】
このように、本実施形態では、優先順位毎に階層を作らず、同じ階層に複数のサブ階層（グループ）を設け、階層内で優先度の高いリクエストの数を増やす事で、階層数を増やすことなく優先順位を保つことができる。これにより、バス占有率をさらに詳細に調整することができ、システムに適したバス占有率とすることができる。
【００８７】
尚、上述の実施の形態のほか、本発明の要旨を逸脱しない範囲で種々の変形、実施が可能である。例えば、上記のラウンドロビン方式の代わりに、所定の順序にしたがい選択するその他の選択方式を用いてもよい。
【図面の簡単な説明】
【００８８】
【図１】本発明にかかるデータ処理システムの構成を示す構成図である。
【図２】本発明にかかるバス調停回路の構成を示す構成図である。
【図３】本発明にかかるバス調停方法を示すフローチャートである。
【図４】本発明にかかるデータ処理システムの構成を示す構成図である。
【図５】本発明にかかるバス調停回路の構成を示す構成図である。
【図６】本発明にかかるバス調停回路の構成を示す構成図である。
【図７】本発明にかかるバス調停方法を示すフローチャートである。
【図８】従来のデータ処理システムの構成を示す構成図である。
【符号の説明】
【００８９】
１〜６  バスマスタ
１００  バス調停回路
１１０  階層化ラウンドロビン選択部
１１１  第１階層選択部
１１２  第２階層選択部
１１３  第３階層選択部
１２０  リクエスト入力部
１３０  選択信号出力部
１４０  階層情報設定部
２００  リソース
２１０  バス
ＲＲ１〜ＲＲ３  階層
Ｒ１〜Ｒ６  リクエスト
ＳＳ１〜ＳＳ６  リクエスト選択信号
【図１】
2007026022.tif 000009
【図２】
2007026022.tif 000010
【図３】
2007026022.tif 000011
【図４】
2007026022.tif 000012
【図５】
2007026022.tif 000013
【図６】
2007026022.tif 000014
【図７】
2007026022.tif 000015
【図８】
2007026022.tif 000016