(57)【要約】【課題】多数の選択肢に対応しつつも、論理回路の回路規模の増大を抑制することができる選択回路およびパケット処理装置を提供すること。【解決手段】それぞれが選択肢と対応し、対応する選択肢が選択可能な状態にあるか否かを示すｍ×ｎビットの情報を記憶するＲＲメモリ２０３と、それぞれがＲＲメモリ２０３に記憶されるｍビット幅のビット列に対応し、対応するビット列に選択肢が選択可能な状態にあることを示しているビットが含まれるか否かを示すｎビットの情報を記憶するステータスＦＦ２０４と、ステータスＦＦ２０４に対してラウンドロビン処理を行って、ビットの１つを選択するＲＲ回路２０５と、ＲＲ回路２０５によって選択されたビットに対応するｍビット幅のビット列に対してラウンドロビン処理を行って、対応する選択肢が選択可能な状態にあることを示しているビットの１つを選択するＲＲ回路２０６とを備える。【選択図】        図１
2010087887.tif 000002
【特許請求の範囲】
【請求項１】
それぞれが選択肢と対応し、対応する選択肢が選択可能な状態にあるか否かを示すｍ×ｎビットの情報を記憶する第１の記憶回路と、
それぞれが前記第１の記憶回路に記憶されるｍビット幅のビット列に対応し、対応するビット列に選択肢が選択可能な状態にあることを示しているビットが含まれるか否かを示すｎビットの情報を記憶する第２の記憶回路と、
前記第２の記憶回路に対してラウンドロビン処理を行って、対応するビット列に選択肢が選択可能な状態にあることを示しているビットが含まれるビットの１つを選択する第１のラウンドロビン回路と、
前記第１のラウンドロビン回路によって選択されたビットに対応するｍビット幅のビット列に対してラウンドロビン処理を行って、対応する選択肢が選択可能な状態にあることを示しているビットの１つを選択する第２のラウンドロビン回路と、
前記第１のラウンドロビン回路と前記第２のラウンドロビン回路とを制御する制御回路と
を備えることを特徴とする選択回路。
【請求項２】
前記制御回路は、前記第１のラウンドロビン回路によってビットが選択されるたびに、該ビットに対応するｍビット幅のビット列から、対応する選択肢が選択可能な状態にあることを示しているビットが全て選択されるように前記第２のラウンドロビン回路を制御することを特徴とする請求項１に記載の選択回路。
【請求項３】
前記第１の記憶回路は、複数の記憶回路を組み合わせて構成されることを特徴とする請求項１または２に記載の選択回路。
【請求項４】
前記制御回路は、予め記憶された設定情報に基づいて、前記第１の記憶回路の各ビットが選択される選択頻度を制御することを特徴とする請求項１〜３のいずれか１つに記載の選択回路。
【請求項５】
パケットが格納される複数のキューと、前記複数のキューの中からパケットを出力するキューを選択する選択回路とを有するパケット処理装置であって、
前記選択回路は、
それぞれが前記複数のキューのいずれかと対応し、対応するキューがパケットを出力可能な状態にあるか否かを示すｍ×ｎビットの情報を記憶する第１の記憶回路と、
それぞれが前記第１の記憶回路に記憶されるｍビット幅のビット列に対応し、対応するビット列にパケットを出力可能な状態にあることを示しているビットが含まれるか否かを示すｎビットの情報を記憶する第２の記憶回路と、
前記第２の記憶回路に対してラウンドロビン処理を行って、対応するビット列にパケットを出力可能な状態にあることを示しているビットが含まれるビットの１つを選択する第１のラウンドロビン回路と、
前記第１のラウンドロビン回路によって選択されたビットに対応するｍビット幅のビット列に対してラウンドロビン処理を行って、対応するキューがパケットを出力可能な状態にあることを示しているビットの１つを選択する第２のラウンドロビン回路と、
前記第１のラウンドロビン回路と前記第２のラウンドロビン回路とを制御する制御回路と
を備えることを特徴とするパケット処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ラウンドロビン方式の選択回路およびその選択回路を備えるパケット処理装置に関し、特に、多数の選択肢に対応しつつも、論理回路の回路規模の増大を抑制することができる選択回路およびパケット処理装置に関する。
【背景技術】
【０００２】
従来、複数の選択肢のいずれかを選択する選択回路においては、論理回路として、ラウンドロビン回路が用いられることが多い。パケット処理装置に用いられる選択回路の一例を図１３に示す。図１３に示した選択回路１００は、ラウンドロビン回路１０２を有し、ラウンドロビン回路１０２は、４つのキュー１０１に格納されたパケットを順次選択して出力する。
【０００３】
近年、パケット処理装置は、帯域制御機能等の実現のために、非常に多くのキューを扱うようになっており、それらのキューの選択に用いられる選択回路は、多数の選択肢の選択を高速に実行することが求められている。このような要求に応えるため、複数のラウンドロビン回路をループ状の検索経路を介して接続し、それぞれのラウンドロビン回路をコントロール部が制御する選択回路が知られている（例えば、特許文献１参照）。
【０００４】
【特許文献１】特開２００３−１７９６３２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、ラウンドロビン回路を用いた従来の選択回路には、対応する選択肢の数が増えるにしたがって、論理回路の規模も比例的に増大していくという問題があった。例えば、対象数が１６倍となった場合、１つのラウンドロビン回路で対応するとすれば、使用するゲート数が１６倍となる。
【０００６】
また、例えば、対象数が１６倍となった場合に、上記の特許文献１の方式を採用してラウンドロビン回路の数を増やすことで対応することとしても、１６倍のラウンドロビン回路が必要となり、論理回路の規模は１６倍程度になる。
【０００７】
開示の技術は、上述した従来技術による問題点を解消するためになされたものであり、多数の選択肢に対応しつつも、論理回路の回路規模の増大を抑制することができる選択回路およびパケット処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するため、本願の開示する選択回路およびパケット処理装置は、一つの態様において、それぞれが選択肢と対応し、対応する選択肢が選択可能な状態にあるか否かを示すｍ×ｎビットの情報を記憶する第１の記憶回路と、それぞれが前記第１の記憶回路に記憶されるｍビット幅のビット列に対応し、対応するビット列に選択肢が選択可能な状態にあることを示しているビットが含まれるか否かを示すｎビットの情報を記憶する第２の記憶回路と、前記第２の記憶回路に対してラウンドロビン処理を行って、対応するビット列に選択肢が選択可能な状態にあることを示しているビットが含まれるビットの１つを選択する第１のラウンドロビン回路と、前記第１のラウンドロビン回路によって選択されたビットに対応するｍビット幅のビット列に対してラウンドロビン処理を行って、対応する選択肢が選択可能な状態にあることを示しているビットの１つを選択する第２のラウンドロビン回路と、前記第１のラウンドロビン回路と前記第２のラウンドロビン回路とを制御する制御回路とを備える。
【０００９】
この態様によれば、２つのラウンドロビン回路を組み合わせてラウンドロビン制御を実現することとしたので、多数の選択肢に対応しつつも、論理回路の回路規模の増大を抑制することができる。
【００１０】
なお、本願の開示する選択回路の構成要素、表現または構成要素の任意の組合せを、方法、装置、システム、コンピュータプログラム、記録媒体、データ構造などに適用したものも上述した課題を解決するために有効である。
【発明の効果】
【００１１】
本願の開示する選択回路およびパケット処理装置の一つの態様によれば、多数の選択肢に対応しつつも、論理回路の回路規模の増大を抑制することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１２】
以下に添付図面を参照して、本願の開示する選択回路およびパケット処理装置の好適な実施の形態を詳細に説明する。
【実施例１】
【００１３】
まず、実施例１に係る選択回路２０１の構成について説明する。図１は、選択回路２０１の構成を示すブロック図である。選択回路２０１は、ｍ×ｎ個の選択肢から選択可能な状態にあるものを順次選択する回路であり、ラウンドロビン（以下、「ＲＲ」と略記する）制御部２０２と、ＲＲメモリ２０３と、ステータスフリップフロップ（以下、「ステータスＦＦ」もしくは単に「ＦＦ」と略記する）２０４と、ＲＲ回路２０５と、ＲＲ回路２０６とを有する。
【００１４】
ＲＲ制御部２０２は、ＲＲ回路２０５とＲＲ回路２０６とを組み合わせて用いてＲＲ制御を実現する。なお、ＲＲ制御部２０２の制御の詳細については後述する。
【００１５】
ＲＲメモリ２０３は、ｍ×ｎビットの情報を記憶する記憶回路であり、ｍビットのビット列（以下、このビット列を「ＷＯＲＤ」ともいう）単位でアクセスされる。ＲＲメモリ２０３のビットは、それぞれが１つの選択肢に対応し、対応する選択肢が選択可能であるか否かを示す。具体的には、ビットの値が「１」であれば、対応する選択肢が選択可能であることを示し、ビットの値が「０」であれば、対応する選択肢が選択不能であることを示す。
【００１６】
ステータスＦＦ２０４は、ｎビットの情報を記憶する記憶回路である。ステータスＦＦ２０４は、それぞれがＲＲメモリ２０３の１つのＷＯＲＤに対応し、ＷＯＲＤに対応する選択肢の中に選択可能な状態にあるものがあるか否かを示す。すなわち、ステータスＦＦ２０４の各ビットは、対応するＷＯＲＤのビットが全て「０」であれば「０」となり、対応するＷＯＲＤのビットに１つでも「１」があれば「１」となる。
【００１７】
ＲＲ回路２０５は、ｎビットのビット列の中から値が「１」のビットをラウンドロビン方式で選択し、選択したビットの番号を出力する。具体的には、ＲＲ回路２０５は、ステータスＦＦ２０４から、値が「１」のビットを選択するために用いられる。
【００１８】
ＲＲ回路２０６は、ｍビットのビット列の中から値が「１」のビットをラウンドロビン方式で選択し、選択したビットの番号を出力する。具体的には、ＲＲ回路２０６は、ＲＲ回路２０５によって選択されたステータスＦＦ２０４のビットに対応するＲＲメモリ２０３のＷＯＲＤから、値が「１」のビットを選択するために用いられる。
【００１９】
このＲＲ回路２０５とＲＲ回路２０６とを組み合わせて用いてＲＲ制御を実現することにより、選択肢の増大にともなう論理回路の規模の増大を抑制することができる。例えば、選択肢が１６倍になったとしても、ｍとｎをそれぞれ４倍にすればよいので、ＲＲ回路２０５とＲＲ回路２０６の回路規模の増大は４倍で済む。すなわち、選択肢がｘ倍になったとしても、論理回路の増大は√ｘ倍程度に抑制される。
【００２０】
次に、ＲＲメモリ２０３とステータスＦＦ２０４の具体例を参照しながら、ＲＲ制御部２０２の制御の詳細について説明する。図２は、実施例１に係る選択回路２０１のメモリ構成を示す図である。図２に示すように、ＲＲメモリ２０３は、それぞれが１つの選択肢に対応するｍ×ｎ個のビットを有する。ＲＲメモリ２０３において、値が「１」のビットは、対応する選択肢が選択可能な状態であることを示す。
【００２１】
そして、ステータスＦＦ２０４は、対応するＲＲメモリ２０３のＷＯＲＤに値が「１」のビットが存在するか否かを示すｎ個のビットを有する。ステータスＦＦ２０４において、値が「０」のビットは、対応するＲＲメモリ２０３のＷＯＲＤに値が「１」のビットが存在しないことを示す。
【００２２】
ＲＲ制御部２０２は、ＲＲメモリ２０３から値が「１」のビット、すなわち、対応する選択肢が選択可能な状態にあるビットを順次選択する。具体的には、ＲＲ制御部２０２は、ａ番目のＷＯＲＤのｂ番目のビットを（ａ，ｂ）と表記することとして、ＲＲメモリ２０３を下記の順序で走査した場合に発見される値が「１」のビットを順次選択する。
【００２３】
（０，０）、（０，１）、（０，２）、…、（０，ｍ−１）、（１，０）、（１，１）、（１，２）、…、（１，ｍ−１）、…、（ｎ−１，０）、（ｎ−１，１）、（ｎ−１，２）、…、（ｎ−１，ｍ−１）。
【００２４】
この制御を実現するため、ＲＲ制御部２０２は、ＲＲ回路２０５にＲＲ処理を実行させ、ステータスＦＦ２０４から、値が「１」のビットを取得する。このように、まず、ステータスＦＦ２０４に対してＲＲ処理を実行することにより、値が「１」のビットが存在するＷＯＲＤを特定することができる。
【００２５】
そして、ＲＲ制御部２０２は、ＲＲ回路２０６にＲＲ処理を実行させ、特定したＷＯＲＤから値が「１」のビットを１つずつ取得する。そして、ＲＲ回路２０６がＷＯＲＤの全てのビットを走査した後、ＲＲ制御部２０２は、再びＲＲ回路２０５に先程の続きのＲＲ処理を実行させ、ステータスＦＦ２０４から、値が「１」である次のビットを取得する。
【００２６】
このように、ＲＲ回路２０５とＲＲ回路２０６を組み合わせて用いることにより、ＲＲ制御部２０２は、ＲＲメモリ２０３を上記の順序で走査した場合に発見される値が「１」のビットを順次取得することができる。
【００２７】
図２に示した例の場合、ＲＲ制御部２０２は、ＲＲ回路２０５にＲＲ処理を実行させることにより、ステータスＦＦ２０４から、値が「１」のビットとして１番目のビットを取得する。そして、ＲＲ制御部２０２は、１番目のＷＯＲＤをＲＲ回路２０６にＲＲ処理させることにより、（１，４）と（１，８）を取得する。
【００２８】
続いて、ＲＲ制御部２０２は、ＲＲ回路２０５に先程の続きのＲＲ処理を実行させることにより、ステータスＦＦ２０４から、値が「１」のビットとして２番目のビットを取得する。そして、ＲＲ制御部２０２は、２番目のＷＯＲＤをＲＲ回路２０６にＲＲ処理させることにより、（２，２）、（２，５）、（２，６）、（２，ｍ−４）および（２，ｍ−３）を取得する。
【００２９】
以下同様にして、ＲＲ制御部２０２は、ＲＲメモリ２０３から値が「１」のビットを順次選択することができる。
【００３０】
次に、図１に示した選択回路２０１の処理手順についてフローチャートを参照しながら説明する。図３は、選択回路２０１におけるステータス更新処理の処理手順を示すフローチャートである。このステータス更新処理は、選択回路２０１において常に実行される処理である。
【００３１】
ＲＲ制御部２０２は、新たなＲＲ候補、すなわち、新たに選択可能な状態になった選択肢に関する通知を受信すると（ステップＳ１０１肯定）、ＲＲメモリ２０３における該当ビットの値を「１」に書き換える（ステップＳ１０２）。さらに、ＲＲ制御部２０２は、そのビットを含むＷＯＲＤに対応するステータスＦＦ２０４のビットの値を「１」に書き換える（ステップＳ１０３）。
【００３２】
また、ＲＲ制御部２０２は、ＲＲ処理が完了し、ＲＲメモリ２０３から値が「１」のビットを取得して、そのビットの番号を選択結果として外部に出力したならば（ステップＳ１０４肯定）、そのビットの値を「０」にクリアする（ステップＳ１０５）。ここで、そのビットを含むＷＯＲＤの全てのビットの値が「０」となった場合には（ステップＳ１０６肯定）、ＲＲ制御部２０２は、そのＷＯＲＤに対応するステータスＦＦ２０４のビットの値を「０」にリセットする（ステップＳ１０７）。
【００３３】
以降、ＲＲ制御部２０２は、上記の処理手順を繰り返し実行する。なお、上記の処理手順では、ＲＲ処理によって選択されたＲＲメモリ２０３のビットの値を常に「０」にクリアしているが、必ずしもこのタイミングで選択されたＲＲメモリ２０３のビットの値を常に「０」にクリアする必要はない。例えば、選択肢が、複数のパケットが格納されているキューである場合、そのキューが選択されてパケットが１つ出力されても、キューにパケットが残っているため、そのキューは依然として選択可能な状態にある。このような場合、キューのパケットが全て出力された段階で、対応するＲＲメモリ２０３のビットの値を「０」にクリアすればよい。
【００３４】
図４は、選択回路２０１における選択処理の処理手順を示すフローチャートである。この選択処理は、上記のステータス更新処理と並行して、選択回路２０１において常に実行される処理である。
【００３５】
ＲＲ制御部２０２は、ＲＲ回路２０５にステータスＦＦ２０４のＲＲ処理を実行させる（ステップＳ２０１）。そして、ＲＲ制御部２０２は、選択されたビットに対応するＲＲメモリ２０３のＷＯＲＤをリードする（ステップＳ２０２）。
【００３６】
続いて、ＲＲ制御部２０２は、リードしたＷＯＲＤのＲＲ処理をＲＲ回路２０６に実行させ、選択されたビットの番号を選択結果として外部に出力する処理を繰り返す（ステップＳ２０３）。そして、ＲＲ回路２０６がＷＯＲＤの全てのビットを走査して、選択すべきビットがなくなった場合（ステップＳ２０４肯定）、ＲＲ制御部２０２は、ステップＳ２０１に戻って、ＲＲ回路２０５にＲＲ処理の続きを実行させる。
【００３７】
上述してきたように、本実施例１では、２つのＲＲ回路を組み合わせて用いることとしたので、選択肢が増大した場合でも、論理回路の規模の増大を抑制することができる。
【実施例２】
【００３８】
実施例１では、１個のＲＲメモリを用いて選択回路を実現する例を示したが、複数のＲＲメモリを用いて選択回路を実現することとしてもよい。このように構成することにより、必要に応じてＲＲメモリを増設して対応可能な選択肢の数を拡張する等の柔軟な運用が可能になる。そこで、本実施例では、複数のＲＲメモリを用いて選択回路を実現する例について説明する。
【００３９】
なお、以下の説明では、既に説明した部位と同等の部位には、既に説明した部位と同一の符号を付して、重複する説明を省略することとする。
【００４０】
図５は、実施例２に係る選択回路３０１の構成を示すブロック図である。選択回路３０１は、ｍ×（ｎ１＋ｎ２）個の選択肢から選択可能な状態にあるものを順次選択する回路であり、ＲＲ制御部２０２と、ＲＲメモリ３０３ａと、ＲＲメモリ３０３ｂと、ステータスＦＦ３０４と、ＲＲ回路３０５と、ＲＲ回路２０６とを有する。
【００４１】
ＲＲメモリ３０３ａは、ｍ×ｎ１ビットの情報を記憶する記憶回路であり、ｍビットのビット列（ＷＯＲＤ）単位でアクセスされる。ＲＲメモリ３０３ｂは、ｍ×ｎ２ビットの情報を記憶する記憶回路であり、ｍビットのビット列（ＷＯＲＤ）単位でアクセスされる。このように、選択回路３０１は、２つのＲＲメモリ３０３を有し、対応が必要な選択肢が少なければ一方のＲＲメモリ３０３のみを実装して運用され、対応が必要な選択肢が多ければ両方のＲＲメモリ３０３を実装して運用される。
【００４２】
ステータスＦＦ３０４は、ＲＲメモリ３０３ａとＲＲメモリ３０３ｂの両方が実装された場合にも対応できるように、ｎ１＋ｎ２ビットの情報を記憶する。ＲＲメモリ３０３ａとＲＲメモリ３０３ｂの一方が実装されていない場合は、実装されていないＲＲメモリ３０３に対応するステータスＦＦ３０４の全てのビットは「０」に設定される。したがって、実装されていないＲＲメモリ３０３のＷＯＲＤがＲＲ回路２０６のＲＲ処理の対象となることはない。
【００４３】
ＲＲ回路３０５は、ＲＲメモリ３０３ａとＲＲメモリ３０３ｂの両方が実装された場合にも対応できるように、ｎ１＋ｎ２ビットのビット列の中から値が「１」のビットをラウンドロビン方式で選択し、選択したビットの番号を出力する。具体的には、ＲＲ回路３０５は、ステータスＦＦ３０４から、値が「１」のビットを選択するために用いられる。
【００４４】
上述してきたように、本実施例２では、複数のＲＲメモリ３０３が存在する場合でも対応できるように、ステータスＦＦ３０４とＲＲ回路３０５を構成したので、必要な選択肢の数に合わせて柔軟な運用をすることができる。
【実施例３】
【００４５】
実施例１では、全ての選択肢を均等な頻度で選択する例を示したが、選択頻度に重みをつけることとしてもよい。そこで、本実施例では、選択頻度に重みをつける例について説明する。
【００４６】
図６は、実施例３に係る選択回路４０１の構成を示すブロック図である。選択回路４０１は、ｍ×ｎ個の選択肢から選択可能な状態にあるものを順次選択する回路であり、ＲＲ制御部４０２と、ＲＲメモリ２０３と、ステータスＦＦ２０４と、ＲＲ回路２０５と、ＲＲ回路２０６と、比率メモリ４０７と、出力回数カウンタ４０８とを有する。
【００４７】
比率メモリ４０７は、選択肢に対応するビットの番号と、その選択肢の選択比率とを対応づけて記憶する。選択比率は、通常の選択頻度を１として設定される。図６に示した例では、（０，３）のビットに対応する選択肢の選択比率として「２」が設定され、（０，５）のビットに対応する選択肢の選択比率として「３」が設定されている。これは、（０，３）のビットに対応する選択肢の選択頻度を通常の２倍とし、（０，５）のビットに対応する選択肢の選択頻度を通常の３倍とすることを示している。
【００４８】
出力回数カウンタ４０８は、ＲＲ回路２０６によって選択されたビットの番号が、選択結果として出力された回数を記憶する。出力回数カウンタ４０８の値は、ＲＲ回路２０６によって新たなビットが選択されるたびに、「０」にリセットされる。
【００４９】
ＲＲ制御部４０２は、実施例１で説明したＲＲ制御部２０２と同様の制御を実行して、ＲＲ回路２０６によって選択されたビットの番号を選択結果として出力する。その後、ＲＲ制御部４０２は、選択結果として出力したビットの番号と対応する選択比率を比率メモリ４０７から取得し、それを出力回数カウンタ４０８の値と比較する。
【００５０】
そして、両者が一致しなければ、ＲＲ制御部４０２は、ＲＲ回路２０６によって選択されたビットの番号を選択結果として再び出力する。その結果、出力回数カウンタ４０８の値は１だけ増加する。このようにして、ＲＲ制御部４０２は、選択肢毎に定義された選択比率と、出力回数カウンタ４０８の値とが一致するまで、ＲＲ回路２０６によって選択されたビットの番号を選択結果として出力する。
【００５１】
ＲＲ制御部４０２がこのような制御を実行することにより、ＲＲ回路２０６によって選択されたビットの番号は、比率メモリ４０７に設定された選択比率の値の回数だけ連続して選択結果として出力される。
【００５２】
例えば、図７に示すように、ＲＲ回路２０６によって、
（０，０）、（０，２）、（０，３）、（０，５）、（０，７）
の順でビットが選択された場合、（０，３）と（０，５）の選択比率は、それぞれ２倍と３倍であるため、選択回路４０１が出力する選択結果は、
（０，０）、（０，２）、（０，３）、（０，３）、（０，５）、（０，５）、（０，５）、（０，７）
のようになる。
【００５３】
次に、図６に示した選択回路４０１の処理手順についてフローチャートを参照しながら説明する。図８は、選択回路４０１における選択処理の処理手順を示すフローチャートである。この選択処理は、図３に示したステータス更新処理と並行して、選択回路４０１において常に実行される処理である。
【００５４】
ＲＲ制御部４０２は、ＲＲ回路２０５にステータスＦＦ２０４のＲＲ処理を実行させる（ステップＳ３０１）。そして、ＲＲ制御部４０２は、選択されたビットに対応するＲＲメモリ２０３のＷＯＲＤをリードする（ステップＳ３０２）。
【００５５】
続いて、ＲＲ制御部４０２は、リードしたＷＯＲＤのＲＲ処理をＲＲ回路２０６に実行させ（ステップＳ３０３）、選択されたビットの番号を選択結果として外部に出力する（ステップＳ３０４）。その結果、出力回数カウンタ４０８の値が更新される（ステップＳ３０５）。
【００５６】
そして、ＲＲ制御部４０２は、選択結果として出力したビットの番号と対応する選択比率を比率メモリ４０７から取得する（ステップＳ３０６）。ここで、出力回数カウンタ４０８の値と選択比率とが一致しなければ（ステップＳ３０７否定）、ＲＲ制御部４０２は、ステップＳ３０４に戻って、選択結果を再び出力する。
【００５７】
一方、出力回数カウンタ４０８の値と選択比率とが一致した場合（ステップＳ３０７肯定）、ＲＲ制御部４０２は、ＲＲ回路２０６がまだＷＯＲＤの全てのビットを走査していなければ（ステップＳ３０８否定）、ステップＳ３０３から処理を再開する。また、ＲＲ回路２０６がＷＯＲＤの全てのビットを走査して、選択すべきビットがなくなっていれば（ステップＳ３０８肯定）、ＲＲ制御部４０２は、ステップＳ３０１に戻って、ＲＲ回路２０５にＲＲ処理の続きを実行させる。
【００５８】
上述してきたように、本実施例３では、選択肢毎に定義された選択比率に基づいて各選択肢の選択頻度を制御することとしたので、選択肢の選択において優先制御を実現することができる。
【００５９】
なお、上記の例では、選択されたビットの番号を選択比率の回数だけ無条件に選択結果として出力することとしたが、選択肢が選択可能な状態にあるか否かを考慮することとしてもよい。例えば、あるビットに対応する選択比率が「１０」であったとしても、そのビットの番号を選択結果として３回出力した段階で対応する選択肢が選択不能になった場合には、そのビットの番号の出力を中止することとしてもよい。
【実施例４】
【００６０】
実施例１では、２つのＲＲ回路を組み合わせて用いる例を示したが、１つのＲＲ回路に実施例１に示した２つのＲＲ回路の機能を実行させることもできる。そこで、本実施例では、１つのＲＲ回路でステータスＦＦとＷＯＲＤのＲＲ処理を実現する例について説明する。
【００６１】
図９は、実施例４に係る選択回路５０１の構成を示すブロック図である。選択回路５０１は、ｍ×ｎ個の選択肢から選択可能な状態にあるものを順次選択する回路であり、ＲＲ制御部５０２と、ＲＲメモリ２０３と、ステータスＦＦ２０４と、ＲＲ回路５０５と、位置情報レジスタ５０９とを有する。
【００６２】
ＲＲ回路５０５は、ｎビットもしくはｍビットのビット列の中から値が「１」のビットをラウンドロビン方式で選択し、選択したビットの番号を出力する。具体的には、ＲＲ回路５０５は、ステータスＦＦ２０４から、値が「１」のビットを選択するために用いられる。また、ＲＲ回路５０５は、ＲＲメモリ２０３から読み出されたＷＯＲＤから、値が「１」のビットを選択するためにも用いられる。
【００６３】
ＲＲ回路５０５は、前回選択したビットの次のビットから値が「１」のビットを探索するように構成されているが、前回選択したビットの位置を１つしか記憶しない。このため、対象ＡについてＲＲ処理を実行している途中で対象ＢについてＲＲ処理を開始すると、対象Ａにおいて前回選択したビットが不明となり、適切なＲＲ制御が行われないおそれがある。
【００６４】
そこで、ＲＲ制御部５０２は、ステータスＦＦ２０４を対象としてＲＲ回路５０５にＲＲ処理を実行させて選択されたビットの位置を位置情報レジスタ５０９に記憶させておく。そして、ＲＲ制御部５０２は、ステータスＦＦ２０４を対象としてＲＲ回路５０５にＲＲ処理を再び実行させる場合に、位置情報レジスタ５０９の値の次のビットをＲＲ処理の開始位置としてＲＲ回路５０５に指定する。
【００６５】
このように、ステータスＦＦ２０４を対象としてＲＲ処理を実行して選択されたビットの位置を位置情報レジスタ５０９に記憶させておくことにより、ＲＲ回路が１つであっても、ステータスＦＦ２０４を対象とするＲＲ処理を適切に実行することができる。
【００６６】
なお、ＲＲメモリ２０３については、先頭のビットから末尾のビットまで連続して走査されるため、選択されたビットの位置を記憶させる必要はない。また、位置情報レジスタ５０９は、０〜ｎ−１の値を格納することができるだけの容量、すなわち、少なくともｌｏｇ2ｎビットの容量があればよい。
【００６７】
次に、図９に示した選択回路５０１の処理手順についてフローチャートを参照しながら説明する。図１０は、選択回路５０１における選択処理の処理手順を示すフローチャートである。この選択処理は、図３に示したステータス更新処理と並行して、選択回路５０１において常に実行される処理である。
【００６８】
ＲＲ制御部５０２は、位置情報レジスタ５０９の値を読み出し（ステップＳ４０１）、その値に１を加算した値を開始位置として指定して、ＲＲ回路５０５にステータスＦＦ２０４のＲＲ処理を実行させる（ステップＳ４０２）。そして、ＲＲ制御部５０２は、選択されたビットの番号を位置情報レジスタ５０９に記録し（ステップＳ４０３）、選択されたビットに対応するＲＲメモリ２０３のＷＯＲＤをリードする（ステップＳ４０４）。
【００６９】
続いて、ＲＲ制御部５０２は、リードしたＷＯＲＤのＲＲ処理をＲＲ回路５０５に実行させ、選択されたビットの番号を選択結果として外部に出力する処理を繰り返す（ステップＳ４０５）。そして、ＲＲ回路５０５がＷＯＲＤの全てのビットを走査して、選択すべきビットがなくなった場合（ステップＳ４０６肯定）、ＲＲ制御部５０２は、ステップＳ４０１から処理を再開する。
【００７０】
上述してきたように、本実施例４では、ステータスＦＦ２０４のＲＲ処理によって選択されたビットを位置情報レジスタ５０９に記録することとしたので、ＲＲ回路を１つで済ますことができ、論理回路の規模をさらに小さくすることができる。
【実施例５】
【００７１】
本実施例では、上述した選択回路の適用例の１つとして、上述した選択回路をパケット処理装置に適用した例について説明する。なお、ここでは、実施例１で示した選択回路２０１をパケット処理装置に適用した例について説明するが、他の実施例で示した選択回路も同様にパケット処理装置に適用できる。
【００７２】
図１１は、実施例５に係るパケット処理装置６０１の構成を示すブロック図であり、図１２は、実施例５に係るパケット処理装置６０１の選択回路６１１のメモリ構成を示す図である。パケット処理装置６０１は、帯域制御を行う通信装置であり、パケットバッファ６０２と、パケットスケジューラ６０３とを有する。パケットバッファ６０２は、受信したパケットをキューに保持し、パケットスケジューラ６０３の指示に従ってパケットを出力する。
【００７３】
ここで、パケット処理装置６０１は、２５６のユーザを収容し、それぞれのユーザ毎に２５６種のサービスの帯域制御を行うものとする。このような帯域制御を実現するため、パケットスケジューラ６０３は、キュー管理部６０８に、２５６×２５６個、すなわち、６５５３６（６４Ｋ）個のキュー６０５と、それぞれのキュー６０５に対応するｓｈａｐｅｒ６０７とを有する。そして、パケットスケジューラ６０３の選択回路６１１は、出力可能なキュー６０５の１つを選択する。
【００７４】
パケット処理装置６０１は、パケットを受信すると、受信したパケットをパケットバッファ６０２に格納する。さらに、パケット処理装置６０１は、受信したパケットのヘッダ情報から８ビットのユーザＩＤと８ビットのサービスＩＤを取得し、パケットスケジューラ６０３のキュー振り分け部６０４に通知する。このとき、パケット処理装置６０１は、ユーザＩＤとサービスＩＤの他に、受信されたパケットのパケット長と、パケットがパケットバッファ６０２に格納された位置を示す格納アドレスもキュー振り分け部６０４に通知する。
【００７５】
キュー振り分け部６０４は、通知されたパケット長と格納アドレスを、通知されたユーザＩＤとサービスＩＤの組合せに対応するキュー６０５に格納する。そして、各ｓｈａｐｅｒ６０７は、対応するキュー６０５に格納された情報に基づいて帯域制御を実施し、パケットを出力可能であれば、対応するキュー６０５のキュー番号を、選択候補としてＭＵＸ部６０６に通知する。
【００７６】
キュー番号は、０〜６５５３５のいずれかの値をとる１６ビットの数値であり、上位８ビットがユーザＩＤに相当し、下位８ビットがサービスＩＤに相当する。ＭＵＸ部６０６は、各ｓｈａｐｅｒ６０７から通知されたキュー番号を多重して選択回路６１１へ出力する。このときの多重方式は先着順である。
【００７７】
選択回路６１１のＲＲ制御部６１２は、通知されたキュー番号に対応するＲＲメモリ６１３のビットに「１」を設定する。ＲＲメモリ６１３は、それぞれがいずれかのキュー番号に対応する６５５３６（６４Ｋ）ビットの情報を記憶する記憶回路であり、２５６ビット幅のＷＯＲＤ単位でアクセスされる。そして、ＲＲ制御部６１２は、図１２に示すように、キュー番号に対応するＲＲメモリ６１３のビットを特定するために、ユーザＩＤに相当するキュー番号の上位８ビットを、ＷＯＲＤの番号を表す値として扱う。また、ＲＲ制御部６１２は、サービスＩＤに相当するキュー番号の下位８ビットを、ＷＯＲＤ内のビットの番号を表す値として扱う。
【００７８】
ＲＲ制御部６１２は、ＲＲメモリ６１３のビットに「１」を設定するに際して、他のビットの値を上書きしないように、更新対象のビットを含むＷＯＲＤを一旦読み出す。そして、読み出したＷＯＲＤに論理ＯＲ演算を行って、更新対象のビットのみを書き換えた後に、そのＷＯＲＤをＲＲメモリ６１３に書き戻す。
【００７９】
通知されたキュー番号に対応するＲＲメモリ６１３のビットに「１」を設定した後、ＲＲ制御部６１２は、「１」を設定したビットを含むＷＯＲＤに対応するステータスＦＦ６１４のビットに「１」を設定する。
【００８０】
例えば、キュー番号として「０１０４（１６進数）」が指定された場合、ＲＲ制御部６１２は、図１２に示すＲＲメモリ６１３の上から２番目、左から５番目のビットに「１」を設定し、ステータスＦＦ６１４の上から２番目のビットに「１」を設定する。
【００８１】
選択回路６１１では、上記のようなステータス更新処理と並行して、選択処理が実行される。すなわち、ＲＲ回路６１５が、ステータスＦＦ６１４に対してＲＲ処理を実行して、値が「１」のビットを選択する。そして、ＲＲ回路６１６が、ＲＲ回路６１５によって選択されたＷＯＲＤに対してＲＲ処理を実行して、値が「１」のビットを選択していく。なお、ＲＲ回路６１５とＲＲ回路６１６を組み合わせて行うＲＲ制御の詳細については、既に説明済みであるので、詳細な説明は省略する。
【００８２】
選択回路６１１は、ＲＲ回路６１６によって選択されたＲＲメモリ６１３のビットに対応するキュー番号をキュー管理部６０８に通知する。例えば、図１２に示すＲＲメモリ６１３の上から２番目、左から５番目のビットが選択された場合は、選択回路６１１は、キュー番号として「０１０４（１６進数）」をキュー管理部６０８に通知する。
【００８３】
キュー管理部６０８は、選択回路６１１からキュー番号の通知を受けると、そのキュー番号に対応するキュー６０５からパケット長と格納アドレスを取り出し、取り出した格納アドレスをパケットバッファ６０２へ通知する。
【００８４】
パケットバッファ６０２は、キュー管理部６０８から格納アドレスの通知を受けると、その格納アドレスの位置に格納されているパケットを取り出して送出する。上述した動作により、パケット処理装置６０１において、選択回路６１１を用いた帯域制御が実現される。
【００８５】
なお、キュー管理部６０８の各キュー６０５には、パケット長と格納アドレスを複数格納することができる。したがって、ＲＲ回路６１６がＲＲ処理を実行してＲＲメモリ６１３のあるビットを選択した場合、そのビットに対応するキュー６０５からパケット長と格納アドレスを取り出しても、そのキュー６０５にパケット長と格納アドレスが残っている可能性がある。
【００８６】
このため、ＲＲ回路６１６によって選択されたビットの値を無条件に「０」にリセットすると、対応するキュー６０５に残っているパケット長と格納アドレスが選択対象から外れてしまう可能性がある。そこで、キュー管理部６０８は、キュー６０５の格納されているパケット長と格納アドレスの組合せの数をキュー番号毎にレジスタ６０９に設定する。そして、ＲＲ制御部６１２は、ＲＲ回路６１６によってビットが選択された場合に、レジスタ６０９を参照して、そのビットを「０」にリセットするか否かを判定する。
【００８７】
具体的には、ＲＲ制御部６１２は、ＲＲ回路６１６によって選択されたビットに対応するキュー番号を求め、そのキュー番号に対応するキュー６０５に格納されているパケット長と格納アドレスの組合せの数をレジスタ６０９から取得する。そして、取得された数が「１」であれば、今回の選択によって、キュー６０５が空になるはずであるので、ＲＲ回路６１６によって選択されたビットの値を「０」にリセットする。一方、取得された数が「２」以上であれば、今回の選択によっては、キュー６０５は空にならないので、ＲＲ回路６１６によって選択されたビットの値を「０」にリセットしない。
【００８８】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００８９】
（付記１）それぞれが選択肢と対応し、対応する選択肢が選択可能な状態にあるか否かを示すｍ×ｎビットの情報を記憶する第１の記憶回路と、
それぞれが前記第１の記憶回路に記憶されるｍビット幅のビット列に対応し、対応するビット列に選択肢が選択可能な状態にあることを示しているビットが含まれるか否かを示すｎビットの情報を記憶する第２の記憶回路と、
前記第２の記憶回路に対してラウンドロビン処理を行って、対応するビット列に選択肢が選択可能な状態にあることを示しているビットが含まれるビットの１つを選択する第１のラウンドロビン回路と、
前記第１のラウンドロビン回路によって選択されたビットに対応するｍビット幅のビット列に対してラウンドロビン処理を行って、対応する選択肢が選択可能な状態にあることを示しているビットの１つを選択する第２のラウンドロビン回路と、
前記第１のラウンドロビン回路と前記第２のラウンドロビン回路とを制御する制御回路と
を備えることを特徴とする選択回路。
【００９０】
（付記２）前記制御回路は、前記第１のラウンドロビン回路によってビットが選択されるたびに、該ビットに対応するｍビット幅のビット列から、対応する選択肢が選択可能な状態にあることを示しているビットが全て選択されるように前記第２のラウンドロビン回路を制御することを特徴とする付記１に記載の選択回路。
【００９１】
（付記３）前記第１の記憶回路は、複数の記憶回路を組み合わせて構成されることを特徴とする付記１または２に記載の選択回路。
【００９２】
（付記４）前記制御回路は、予め記憶された設定情報に基づいて、前記第１の記憶回路の各ビットが選択される選択頻度を制御することを特徴とする付記１〜３のいずれか１つに記載の選択回路。
【００９３】
（付記５）前記第２のラウンドロビン回路が、第１のラウンドロビン回路を兼ね、
前記第２のラウンドロビン回路は、前記第２の記憶回路に対してラウンドロビン処理を行って選択したビットの位置をレジスタに記憶させ、次回、前記第２の記憶回路に対してラウンドロビン処理を行う場合に、該レジスタに記憶された位置の次のビットからラウンドロビン処理を開始することを特徴とする付記１〜４のいずれか１つに記載の選択回路。
【００９４】
（付記６）前記制御回路は、前記第２のラウンドロビン回路によってビットが選択された場合に、対応するビット列に選択肢が選択可能な状態にないことを示すように該ビットを更新することを特徴とする付記１〜５のいずれか１つに記載の選択回路。
【００９５】
（付記７）パケットが格納される複数のキューと、前記複数のキューの中からパケットを出力するキューを選択する選択回路とを有するパケット処理装置であって、
前記選択回路は、
それぞれが前記複数のキューのいずれかと対応し、対応するキューがパケットを出力可能な状態にあるか否かを示すｍ×ｎビットの情報を記憶する第１の記憶回路と、
それぞれが前記第１の記憶回路に記憶されるｍビット幅のビット列に対応し、対応するビット列にパケットを出力可能な状態にあることを示しているビットが含まれるか否かを示すｎビットの情報を記憶する第２の記憶回路と、
前記第２の記憶回路に対してラウンドロビン処理を行って、対応するビット列にパケットを出力可能な状態にあることを示しているビットが含まれるビットの１つを選択する第１のラウンドロビン回路と、
前記第１のラウンドロビン回路によって選択されたビットに対応するｍビット幅のビット列に対してラウンドロビン処理を行って、対応するキューがパケットを出力可能な状態にあることを示しているビットの１つを選択する第２のラウンドロビン回路と、
前記第１のラウンドロビン回路と前記第２のラウンドロビン回路とを制御する制御回路と
を備えることを特徴とするパケット処理装置。
【００９６】
（付記８）前記制御回路は、前記第１のラウンドロビン回路によってビットが選択されるたびに、該ビットに対応するｍビット幅のビット列から、対応するキューがパケットを出力可能な状態にあることを示しているビットが全て選択されるように前記第２のラウンドロビン回路を制御することを特徴とする付記７に記載のパケット処理装置。
【００９７】
（付記９）前記第１の記憶回路は、複数の記憶回路を組み合わせて構成されることを特徴とする付記７または８に記載のパケット処理装置。
【００９８】
（付記１０）前記制御回路は、予め記憶された設定情報に基づいて、前記第１の記憶回路の各ビットが選択される選択頻度を制御することを特徴とする付記７〜９のいずれか１つに記載のパケット処理装置。
【００９９】
（付記１１）前記第２のラウンドロビン回路が、第１のラウンドロビン回路を兼ね、
前記第２のラウンドロビン回路は、前記第２の記憶回路に対してラウンドロビン処理を行って選択したビットの位置をレジスタに記憶させ、次回、前記第２の記憶回路に対してラウンドロビン処理を行う場合に、該レジスタに記憶された位置の次のビットからラウンドロビン処理を開始することを特徴とする付記７〜１０のいずれか１つに記載のパケット処理装置。
【０１００】
（付記１２）前記制御回路は、前記第２のラウンドロビン回路によってビットが選択された場合に、対応するビット列に選択肢が選択可能な状態にないことを示すように該ビットを更新することを特徴とする付記７〜１１のいずれか１つに記載のパケット処理装置。
【図面の簡単な説明】
【０１０１】
【図１】実施例１に係る選択回路の構成を示すブロック図である。
【図２】実施例１に係る選択回路のメモリ構成を示す図である。
【図３】実施例１に係る選択回路におけるステータス更新処理の処理手順を示すフローチャートである。
【図４】実施例１に係る選択回路における選択処理の処理手順を示すフローチャートである。
【図５】実施例２に係る選択回路の構成を示すブロック図である。
【図６】実施例３に係る選択回路の構成を示すブロック図である。
【図７】実施例３に係る選択回路の選択結果の一例を示す図である。
【図８】実施例３に係る選択回路における選択処理の処理手順を示すフローチャートである。
【図９】実施例４に係る選択回路の構成を示すブロック図である。
【図１０】実施例４に係る選択回路における選択処理の処理手順を示すフローチャートである。
【図１１】実施例５に係るパケット処理装置の構成を示すブロック図である。
【図１２】実施例５に係るパケット処理装置の選択回路のメモリ構成を示す図である。
【図１３】従来の選択回路の一例を示す図である。
【符号の説明】
【０１０２】
１００、２０１、３０１、４０１、５０１、６１１  選択回路
１０１  キュー
１０２、２０５、２０６、３０５、５０５、６１５、６１６  ラウンドロビン回路（ＲＲ回路）
２０２、４０２、５０２、６１２  ＲＲ制御部
２０３、３０３ａ、３０３ｂ、６１３  ＲＲメモリ
２０４、３０４、６１４  ステータスフリップフロップ（ステータスＦＦ）
４０７  比率メモリ
４０８  出力回数カウンタ
５０９  位置情報レジスタ
６０１  パケット処理装置
６０２  パケットバッファ
６０３  パケットスケジューラ
６０４  キュー振り分け部
６０５  キュー
６０６  ＭＵＸ部
６０７  ｓｈａｐｅｒ
６０８  キュー管理部
６０９  レジスタ
【図１】
2010087887.tif 000003
【図２】
2010087887.tif 000004
【図３】
2010087887.tif 000005
【図４】
2010087887.tif 000006
【図５】
2010087887.tif 000007
【図６】
2010087887.tif 000008
【図７】
2010087887.tif 000009
【図８】
2010087887.tif 000010
【図９】
2010087887.tif 000011
【図１０】
2010087887.tif 000012
【図１１】
2010087887.tif 000013
【図１２】
2010087887.tif 000014
【図１３】
2010087887.tif 000015