中継器
【課題】集積回路全体の遅延時間やジッターの増加、スループットの低下などを抑制させるよう、トラヒックの流量を制御する。
【解決手段】分散型のバスを備える集積回路において、複数のバスを接続する中継器は、トラヒックデータの入出力の組み合わせを切り替えるスイッチと、複数のトラヒックを共通して扱う隣接の中継器からのトラヒックごとの混雑情報と自中継器におけるトラヒックごとの混雑情報とを取得する混雑情報処理部と、各混雑情報に基づいて、トラヒックごとの流れにくさを示す混雑度の情報を求める混雑情報比較部と、混雑度に基づいて、トラヒックごとにバスの伝送帯域を割り当てて送信スケジュールを調整する調整部と、割り当て結果に基づきスイッチを切り替える割当部と、混雑度が閾値よりも大きいトラヒックのパケットを廃棄する廃棄部と、廃棄されたパケットの再送を送信元のバッファに要求する要求部とを備えている。
【解決手段】分散型のバスを備える集積回路において、複数のバスを接続する中継器は、トラヒックデータの入出力の組み合わせを切り替えるスイッチと、複数のトラヒックを共通して扱う隣接の中継器からのトラヒックごとの混雑情報と自中継器におけるトラヒックごとの混雑情報とを取得する混雑情報処理部と、各混雑情報に基づいて、トラヒックごとの流れにくさを示す混雑度の情報を求める混雑情報比較部と、混雑度に基づいて、トラヒックごとにバスの伝送帯域を割り当てて送信スケジュールを調整する調整部と、割り当て結果に基づきスイッチを切り替える割当部と、混雑度が閾値よりも大きいトラヒックのパケットを廃棄する廃棄部と、廃棄されたパケットの再送を送信元のバッファに要求する要求部とを備えている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散型のバスを備える半導体の集積体回路において、バス間を接続する複数の中継器間を流れる複数のトラヒックの送信スケジューリングを調整する技術に関する。
【背景技術】
【０００２】
図１（ａ）は、集中型のバス制御の例を示す。集中型のバス制御を行う従来の集積回路では、主に複数のバスマスタとメモリとの間は１つのバスによって接続され、アービターによって各バスマスタからメモリへのアクセスが調停される。しかし、集積回路の高機能化、マルチコア化により、回路の規模が増大し、トラヒックも複雑に変動しながらバスを流れており、集中型のバス制御による集積回路の設計が困難になってきている。
【０００３】
その一方で、近年、並列計算機での接続技術や、ネットワーク制御の技術を取り入れた分散型のバスを有する半導体集積回路の開発が進んでいる。図１（ｂ）は、分散型のバス制御の例を示す。分散型のバスを有する半導体集積回路は、複数の中継器が複数のバスで接続されて構成されている。近年、図１（ｂ）に示すような分散型のバスを用いることにより、大規模化した集積回路内のトラヒックを、複数のバスに分散して伝送するネットワークオンチップ（Network on Chip）の取り組みがある。
【０００４】
しかしながら、分散型のバスでは、中継器によって隔てられたバスマスタ間で、互いの送信スケジュールで調停が行われない。そのため、中継器において、トラヒックが合流する数やトラヒックの流量の変化によって干渉が発生し、遅延時間やジッターの増加、スループットの低下など、伝送品質の低下を引き起こす。
【０００５】
分散型バスを流れるトラヒックの伝送品質の低下を回避する技術として、中継器において、トラヒックごとの送信スケジューリングを調整することで、中継器でのトラヒック間の干渉を抑制する技術が従来知られていた（例えば、特許文献１参照）。
【０００６】
図２は、特許文献１に記載された、従来の送信スケジューリングを制御する中継器の構成、および、トラヒックＡ〜Ｃの送信経路を示す。トラヒックＡは、バスマスタＡから、中継器Ｅおよび中継器Ｆを介してメモリＤへ送信される。トラヒックＢは、バスマスタＢから、中継器Ｅおよび中継器Ｆを介してメモリＤへ送信される。トラヒックＣは、バスマスタＣから、中継器Ｆを介してメモリＤへ送信される。
【０００７】
図２に示す中継器は、複数の送信バッファを備えている。また、バスマスタＡ〜Ｃから送信されるデータパケットには、そのデータパケットがどのトラヒックのデータパケットであるかを特定するための情報が付与されている。
【０００８】
各中継器は、データパケットを受信するとトラヒックごとに区別して各データパケットを異なるバッファに蓄える。そして、次の中継器へデータパケットを送信する際に、各トラヒックの伝送品質（遅延時間やスループット）が公平となるように、各バッファ内のデータパケットを送信する。この処理は、「スケジューリング調整処理」と呼ばれる。
【０００９】
図２の例では、トラヒックＡとトラヒックＢとが合流する中継器Ｅでは、それぞれのトラヒックを中継器２へ中継する際に、５０％ずつ公平に帯域が割り当てられるように、送信スケジューリングが調整される。さらに、トラヒックＡ、トラヒックＢ、トラヒックＣが合流する中継器Ｆでは、同様に各トラヒックに３３％ずつ公平に帯域が割り当てられるように、送信スケジューリングが調整される。
【００１０】
これにより、３つのバスマスタからメモリＤへの各トラヒックには公平に伝送帯域が割り当てられるため、トラヒック間の干渉による伝送性能の低下を抑制することができる。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００８−５４１６４７号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
従来の中継器では、中継器ごとに自身を通過するトラヒックの状態のみに基づいて、送信スケジューリングが調整され、局所的には伝送性能が公平となるように制御が行われている。言い換えると、各中継器は、独立して利己的に送信スケジューリングを調整している。これでは、優先度が高く設定されたトラヒックなどの、回路を流れるトラヒックの条件によっては、各中継器が行う送信スケジュールの調整によってトラヒック間の競合が発生し、却って回路全体の伝送性能（遅延時間やスループット）を低下させることがあった。
【００１３】
この課題を、以下、より具体的に説明する。
【００１４】
図３は、トラヒック間で競合が発生したときのトラヒックＡ〜Ｃを示している。
【００１５】
図３において、バスマスタＡはトラヒックＡを、中継器Ｅと中継器Ｆを介してメモリＧへ送信し、バスマスタＢはトラヒックＢを、中継器Ｅと中継器Ｆを介してメモリＤへ送信し、バスマスタＣはトラヒックＣを、中継器Ｆを介してメモリＤへ送信している。
【００１６】
さらに、図３では、トラヒックＣは、緊急時に送信される、相対的に高い優先度が設定されていると想定している。このようなトラヒックＣに、中継器Ｆは優先的にメモリＤへのバスの全ての伝送帯域（１００％）を割り当てる。この結果、トラヒックＢにはメモリＤへのバスの帯域が割り当てられていないことになる。
【００１７】
中継器Ｅと中継器Ｆにおける送信スケジュールの調整を、従来のように、各中継器が自身を通過するトラヒックの状態のみに基づいて行ってしまうと、トラヒックＢの送信先の中継器ＦがトラヒックＢにバスの帯域を割り当てていないにもかかわらず、中継器Ｅは、トラヒックＡとトラヒックＢに、それぞれ５０％の伝送帯域を公平に割り当ててしまう。これでは、回路全体では、中継器Ｅによる送信スケジューリング制御は、中継器Ｅから中継器Ｆへのバスの利用効率を却って低下させることになる。
【００１８】
本発明は上記課題を解決するためになされたものであり、その目的は、回路全体の遅延時間やジッターの増加、スループットの低下などを抑制させるよう、中継器におけるトラヒックの流量を制御することにある。
【課題を解決するための手段】
【００１９】
本発明による中継器は、分散型のバスを備える集積回路において、複数のバスを接続する中継器であって、前記バス上を伝送される各トラヒックのトラヒックデータは、パケットに分割されており、前記中継器は、トラヒックデータを受け取る入力および前記トラヒックデータを送出する出力の組み合わせを切り替えるスイッチと、複数のトラヒックを共通して扱う隣接の中継器からのトラヒックごとの混雑の程度を示す混雑情報と、自中継器における前記トラヒックごとの混雑情報とを取得する混雑情報処理部と、前記隣接の中継器から取得した前記混雑情報および自中継器における前記混雑情報に基づいて、伝送経路上でのトラヒックごとの流れにくさを定量的に示す混雑度の情報を求める混雑情報比較部と、前記混雑度に基づいて、前記トラヒックごとにバスの伝送帯域を割り当てて送信スケジュールを調整する送信スケジュール調整部と、前記バスの伝送帯域の割り当て結果に基づき、前記スイッチを切り替えるスイッチ割当部と、前記混雑度が予め定められた閾値よりも大きいトラヒックのパケットを入力バッファから廃棄するパケット廃棄部と、廃棄されたパケットの再送を送信元のバッファに要求する再送要求部とを備えている。
【００２０】
本発明による他の中継器は、分散型のバスを備える集積回路において、複数のバスを接続する中継器であって、前記バス上を伝送される各トラヒックのトラヒックデータは、パケットに分割されており、前記中継器は、トラヒックデータを受け取る入力および前記トラヒックデータを送出する出力の組み合わせを切り替えるスイッチと、複数のトラヒックを共通して扱う隣接の中継器からのトラヒックごとの混雑の程度を示す混雑情報と、自中継器における前記トラヒックごとの混雑情報とを取得する混雑情報処理部と、前記隣接の中継器から取得した前記混雑情報および自中継器における前記混雑情報に基づいて、伝送経路上でのトラヒックごとの流れにくさを定量的に示す混雑度の情報を求める混雑情報比較部と、前記混雑度に基づいて、前記トラヒックごとにバスの伝送帯域を割り当てて送信スケジュールを調整する送信スケジュール調整部と、前記バスの伝送帯域の割り当て結果に基づき、前記スイッチを切り替えるスイッチ割当部と、異なるバスにデータを送出する複数の出力にそれぞれ接続された複数の出力バッファと、前記混雑度が予め定められた閾値よりも大きいトラヒックの連続するパケットに対して、同じ出力バッファを割当て、さらにトラヒックが送信される次の中継器に対して、ルーティングの設定の再利用を通知するルーティング再利用通知部とを備えている。
【００２１】
本発明による中継器は、分散型のバスを備える集積回路において、複数のバスを接続する中継器であって、トラヒックデータを受け取る入力および前記トラヒックデータを送出する出力の組み合わせを切り替えるスイッチと、複数のトラヒックを共通して扱う隣接の中継器からのトラヒックごとの混雑の程度を示す混雑情報と、自中継器における前記トラヒックごとの混雑情報とを取得する混雑情報処理部と、前記隣接の中継器から取得した前記混雑情報および自中継器における前記混雑情報に基づいて、伝送経路上でのトラヒックごとの流れにくさを定量的に示す混雑度の情報を求める混雑情報比較部と、前記混雑度に基づいて、前記トラヒックごとにバスの伝送帯域を割り当てて送信スケジュールを調整する送信スケジュール調整部と、前記バスの伝送帯域の割り当て結果に基づき、前記スイッチを切り替えるスイッチ割当部と備えている。
【００２２】
前記混雑情報は、自中継器において各トラヒックのトラヒックデータが自中継器を通過するのに要する遅延時間を示しており、前記混雑情報比較部は、前記隣接の中継器から取得したトラヒックごとの遅延時間および自中継器におけるトラヒックごとの遅延時間に基づいて、伝送経路上でのトラヒックごとの流れにくさを定量的に示す混雑度の情報を求めてもよい。
【００２３】
前記混雑度は、伝送経路上でのトラヒックごとの流れにくさを示す数値であって、トラヒックが流れやすいほど小さい数値が与えられ、流れにくいほど大きい数値が与えられ、前記送信スケジュール調整部は、前記混雑度が相対的に小さいトラヒックに対して前記バスの伝送帯域を優先的に割り当ててもよい。
【００２４】
前記送信スケジュール調整部は、前記混雑度が相対的に小さいトラヒックに対して前記バスの伝送帯域を相対的に広く確保し、前記バスの伝送帯域を先に利用可能にし、または、前記バスの伝送帯域の利用可能時間を相対的に長く確保することによって、前記バスの伝送帯域を優先的に割り当ててもよい。
【００２５】
各トラヒックのトラヒックデータは、パケットに分割されて前記バス上を伝送されており、前記中継器は、前記混雑度が予め定められた閾値よりも大きいトラヒックのパケットを入力バッファから廃棄するパケット廃棄部と、廃棄されたパケットの再送を送信元のバッファに要求する再送要求部とをさらに備えていてもよい。
【００２６】
各トラヒックのトラヒックデータは、パケットに分割されて前記バス上を伝送されており、前記中継器は、異なるバスにデータを送出する複数の出力にそれぞれ接続された複数の出力バッファと、前記混雑度が予め定められた閾値よりも大きいトラヒックの連続するパケットに対して、同じ出力バッファを割当て、さらにトラヒックが送信される次の中継器に対して、ルーティングの設定の再利用を通知するルーティング再利用通知部とをさらに備えていてもよい。
【００２７】
前記バスの動作クロックは変更可能であり、前記中継器は、前記混雑度が予め定められた閾値よりも大きいトラヒックが送信されるときは、前記出力が接続されたバスの動作クロックを向上させる動作クロック制御部をさらに備えていてもよい。
【００２８】
前記中継器は、自中継器において予め定められた閾値よりも大きな遅延が発生したときにおいて、自中継器における前記トラヒックデータが自中継器を通過するのに要する遅延時間にのみ基づいて前記混雑度を決定する協調制御停止部をさらに備えていてもよい。
【００２９】
本発明による他の中継器は、分散型のバスを備える集積回路において、複数のバスを接続する中継器であって、トラヒックデータを受け取る入力バッファおよび前記トラヒックデータを送出する出力バッファの組み合わせを切り替えるスイッチと、複数のトラヒックを共通して扱う隣接の中継器からのトラヒックごとの混雑の程度を示す混雑情報と、自中継器における前記トラヒックごとの混雑情報とを取得する混雑情報処理部と、前記隣接の中継器から取得した前記混雑情報および自中継器における前記混雑情報に基づいて、伝送経路上でのトラヒックごとの流れにくさを定量的に示す混雑度の情報を求める混雑情報比較部と、各トラヒックの混雑度を各トラヒックのトラヒックデータを格納する入力バッファの混雑度とし、前記入力バッファの混雑度に応じて、前記トラヒックデータが格納される出力バッファの重みの値を決定し、決定した重みの値に応じて前記トラヒックごとにバスの伝送帯域を割り当てて送信スケジュールを調整する送信スケジュール調整部と、前記バスの伝送帯域の割り当て結果に基づき、前記スイッチを切り替えるスイッチ割当部と備えている。
【００３０】
前記送信スケジュール調整部は、送信要求を受けた入力バッファに対し、各出力バッファに付与された重みの値に応じた確率でスイッチを接続してもよい。
【００３１】
前記送信スケジュール調整部は、前記伝送帯域を時間的に複数のタイムスロットに分割し、前記重みの値によって指定された数のタイムスロットをそれぞれの出力バッファに割り当ててもよい。
【００３２】
前記送信スケジュール調整部は、前記重みの値によって予め指定された割合で、確率的に前記出力バッファを選択してもよい。
【発明の効果】
【００３３】
本発明の中継器によれば、隣接の中継器から取得した混雑情報および自中継器における混雑情報に基づいて、伝送経路上でのトラヒックごとの流れにくさを定量的に示す混雑度の情報が求められる。そして、当該混雑度に基づいて、トラヒックごとにバスの伝送帯域を割り当てて送信スケジュールが調整される。これにより、各トラヒックの伝送経路上でのトラヒック間の干渉による伝送品質（遅延時間、スループットなど）の低下を抑えることができる。分散バス全体の利用効率を向上させることで、集積回路全体の伝送性能の向上（低遅延、高スループット）を実現できる。
【図面の簡単な説明】
【００３４】
【図１】（ａ）は、集中型のバス制御の例を示す図であり、（ｂ）は、分散型のバス制御の例を示す図である。
【図２】特許文献１に記載された、従来の送信スケジューリングを制御する中継器の構成、および、トラヒックＡ〜Ｃの送信経路を示す図である。
【図３】トラヒック間で競合が発生したときのトラヒックＡ〜Ｃを示す図である。
【図４】本発明による中継器の動作の概要を示す図である。
【図５】実施形態１における分散型のバスの構成図である。
【図６】パケット６０の伝送フォーマットの一例と、パケット６０を複数のフリットに分割した例を示す図である。
【図７】実施形態１における中継器７００の構成図である。
【図８】実施形態１における中継器７００の動作の流れを説明するフローチャートである。
【図９】伝送経路ごとに各トラヒックのパケットデータの流れにくさを混雑情報として定量的に測定可能な対象を説明する図である。
【図１０】中継器自身７００と隣接する中継器７１１の混雑状態を比較して、自中継器７００において、トラヒックＡとトラヒックＢの混雑度を算出する方法を説明する図である。
【図１１】送信スケジュール調整部７０９と、バッファ割当部７０５による出力バッファ７０３の割り当て方法を説明する図である。
【図１２】スイッチ割当部７０６による出力バッファが割り当てられたトラヒック間での送信スケジューリングの方法を説明する図である。
【図１３】重み付きラウンドロビンにより、スイッチを切り替える場合の、重みの割り当て方法を説明する図である。
【図１４】図５の多段接続網における、トラヒックＡ〜Ｃの各伝送経路を示す図である。
【図１５】トラヒックＡとトラヒックＢとが同時に流れている場合の、トラヒックＡの伝送経路上での各中継器の遅延時間の例を示す図である。
【図１６】トラヒックＡとトラヒックＢに加えて、トラヒックＣが同時に流れる場合の各中継器内でのトラヒックの遅延時間の例を示す図である。
【図１７】混雑度の定義として、自中継器と隣接中継器との混雑情報の比率の変わりに、差分を用いた例を示す図である。
【図１８】中継器Ｒ６に、トラヒックの流れの上流側にある中継器Ｒ０での遅延時間と、中継器Ｒ２での遅延時間とを基に、トラヒックＡおよびトラヒックＣに対して中継器Ｒ１０へのバスの伝送帯域の割り当てを説明する図である。
【図１９】中継器を格子状に並べた種々のトポロジーを示す図である。
【図２０】実施形態２における中継器８００の構成図の構成図である。
【図２１】実施形態２においてバスマスタから送信されるパケットとそのフリット群、および、ヘッダーフリットに記載される情報を示す図である。
【図２２】実施形態２における中継器８００の動作を説明する図である。
【図２３】実施形態３における中継器８１０の構成図である。
【図２４】実施形態３における中継器８１０の動作を説明する図である。
【図２５】実施形態４における中継器８２０の構成図である。
【図２６】実施形態４における中継器８２０の動作を説明する図である。
【図２７】実施形態５における中継器８３０の構成を示す図である。
【図２８】実施形態５における中継器８３０の動作を説明する図である。
【図２９】パケット交換方式と回線交換方式の違いを説明する図である。
【図３０】実施形態６による、回線交換方式の中継器８４０の構成を示す図である。
【発明を実施するための形態】
【００３５】
本発明の各実施形態の説明に先立って、まず本発明による中継器の動作原理を説明する。
【００３６】
図４は、本発明による中継器の動作の概要を示す。
【００３７】
図４では、図３と同様、バスマスタＡがトラヒックＡを、中継器Ｅおよび中継器Ｆを介してメモリＧへ送信し、バスマスタＢが中継器Ｅおよび中継器Ｆを介してメモリＤへトラヒックを送信し、バスマスタＣが中継器Ｆを介してメモリＤへトラヒックを送信することを想定している。
【００３８】
本発明による中継器Ｅは、トラヒックＡおよびトラヒックＢを、中継器Ｆに送信する。トラヒックＡおよびトラヒックＢの伝送帯域を決定するに際して、中継器Ｅは、隣接する中継器Ｆに要求を出し、中継器ＦにおけるトラヒックＡおよびトラヒックＢのデータパケットの流れにくさを定量的に示した値を中継器Ｆに通知してもらう。以下に説明する実施形態では、この値を「混雑情報」と呼ぶ。本明細書では、各トラヒックのデータパケットがそれぞれその中継器を通過するのに要する時間（以下、各トラヒックの「遅延時間」と呼ぶ）を混雑情報として利用する。
【００３９】
中継器Ｆから混雑情報を受け取った中継器Ｅは、各トラヒックについて、自中継器Ｅにおける遅延時間と、隣接する中継器Ｆにおける遅延時間とを比較する。そして中継器Ｅは、トラヒックごとに経路上でのデータパケットの流れにくさを定量的に示す情報を算出する。本明細書においては、この情報を「混雑度」とも呼ぶ。トラヒックごとの混雑度が求められると、中継器Ｅは、その値の大きさに基づいて中継器Ｆへのバスの伝送帯域が割り当てられるように、各トラヒックの送信スケジュールを調整する。
【００４０】
図４では、バスマスタＣからメモリＤへ、緊急時用の優先トラヒックＣが送信される状況を想定している。このとき、中継器Ｆにおいて中継器ＦからメモリＤへのバスの伝送帯域がトラヒックＣによって一時的に占有される。緊急時の優先トラヒックＣの発生により、トラヒックＢのデータパケットがメモリＤへと送信できないため、中継器Ｆ内でのトラヒックＢの遅延時間が長くなる。
【００４１】
中継器Ｆは、トラヒックＡおよびトラヒックＢの各遅延時間を自身の混雑情報として中継器Ｅに通知する。中継器Ｅは、中継器Ｆから通知された遅延時間および自中継器での遅延時間を比較する。その結果中継器Ｅは、中継器Ｆにおいて、トラヒックＡよりもトラヒックＢのデータパケットが流れにくくなったことを特定することができる。そこで中継器Ｅは、トラヒックＡに対しては、中継器Ｆに至るバスの伝送帯域を５０％から１００％へと優先的に割り当てるように送信スケジュールを調整する。一方トラヒックＢに対しては、バスの伝送帯域を５０％から０％へと削減するように送信スケジュールを調整する。
【００４２】
なお、本願明細書において、バスの伝送帯域を「優先的に割り当てる」とは、上述のように伝送帯域を相対的に広く確保することを意味することに限られない。その他、そのトラヒックがバスの伝送帯域を先に利用できるように解放してそのトラヒックを相対的に先に伝送させることを意味してもよいし、その伝送帯域の利用可能時間（許容時間）を相対的に長く確保することを意味してもよい。
【００４３】
本発明では、優先度が高いトラヒックを優先して伝送しつつ、優先度が低いトラヒック、または、優先度が設定されていないトラヒック同士のフロー制御をどのように行うかを問題としている。
【００４４】
以下、添付の図面を参照しながら、本発明による中継器の実施形態を説明する。
【００４５】
（実施形態１）
図５は、本実施形態における分散型のバスの構成図である。
【００４６】
本実施形態では、複数のバスマスタ（ＢＭ）とメモリとを、複数の中継器をバスで多段に接続した構成（多段接続網：ＭＩＮ（Ｍｕｌｔｉｓｔａｇｅ Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ Ｎｅｔｗｏｒｋ））を例に説明する。
【００４７】
図５では、８個のバスマスタ（ＢＭ０〜ＢＭ７）と、１２個の中継器（Ｒ０〜Ｒ１１）と、８個のメモリ（メモリ０〜７）とがバスで接続される回路の様子を示している。１２個の中継器は、４個ずつ３つのグループに分類されている。３つのグループは、８個のバスマスタに接続されるグループ（Ｒ０、Ｒ１、Ｒ２、Ｒ３）、８個のメモリに接続されるグループ（Ｒ８、Ｒ９、Ｒ１０、Ｒ１１）、及び、バスマスタ、又はメモリに接続する中継器を結ぶグループ（Ｒ４、Ｒ５、Ｒ６、Ｒ７）である。
【００４８】
多段接続網を構成する各中継器は、２入力２出力のクロスバースイッチを備えている。図５（ｂ）に示すように、スイッチを切り替えることによって入力と出力の組合せを変更することで、トラヒックの流れを２種類の伝送経路へ切り替えて送信できる。なお、出力先の伝送経路が異なっていれば、中継器は２つのトラヒックを各伝送経路に同時に出力することが可能である。
【００４９】
多段接続網では、各中継器でのスイッチの切り替えによって、全バスマスタと全メモリ間で、必ず１つ以上の伝送経路を構築することができる。
【００５０】
一般的に、クロスバースイッチによって、Ｎ個のバスマスタとＭ個のメモリの全てを接続するためには、スイッチがＮ×Ｍ個の必要となる。そしてバスマスタやメモリの数が増えるにつれてスイッチの数は急激に増加してしまう。これに対し、多段接続網（ＭＩＮ）では、入出力数の小さいクロスバースイッチを階層的に接続することで少ないスイッチでバスマスタとメモリ間の接続を切り替えることができるという特徴がある。
【００５１】
なお、本実施形態においては多段接続網を例に挙げて説明するが、これは一例である。集積回路の構成がその他のトポロジーであっても本発明を適用することが可能である。また、本実施形態では、バスマスタからメモリへのデータ転送は、パケット交換方式により複数の中継器を介して行われるとして説明する。
【００５２】
パケットは、図５（ａ）に示すように、フリットと呼ばれるサイズに分割されて、隣接する中継器へと送信される。
【００５３】
図６は、パケット６０の伝送フォーマットの一例と、パケット６０を複数のフリットに分割した例を示す。
【００５４】
パケット６０は、ヘッダフィールド６１、データフィールド６２および制御コードフィールド６３を備えている。
【００５５】
ヘッダフィールド６１には、たとえば、送信先のアドレス、送信元のアドレス、トラヒックの優先度を示す情報が記述される。優先度の記述方法は任意であるが、多値で表現されてもよい。多値で記述する場合、高い応答性が必要なユーザインターフェースの処理には高い数値を割り当てて優先度を高く設定することができる。一方、バックグラウンド処理で対応可能な映像のトランスコード処理には低い数値を割り当てて優先度を低く設定できる。これらの情報の後に、伝送すべきデータが記述される。
【００５６】
データフィールド６２には、たとえば映像データ、音声データが記述される。制御コードフィールド６３には、たとえば、予め定められたパケット６０の終了コードが記述される。
【００５７】
上述のヘッダフィールド６１のデータのうち、送信先のアドレスと、送信元のアドレスとに基づいて、パケット６０の中継処理と、受信側での受信処理とが行われる。
【００５８】
送信側のバスマスタは、パケット６０を、フリットと呼ばれる小さなパケット単位に分解して伝送する。１フリットは、バスを使って１サイクルで伝送可能なデータであり、そのサイズはバス幅の大きさによって決定される。パケット６０を分割したフリットのうち、最初に送信されるフリットは、ヘッダーフリットと呼ばれる。ヘッダーフリットには、パケットの先頭であることを示すフラグ情報、及びパケットの送信先のアドレス情報が付与されている。
【００５９】
なお、ヘッダーフリットに続く各フリットには、送信先を特定するアドレス情報は格納されていない。その理由は、ヘッダーフリットに続くフリットは、ヘッダーフリットと同じ宛先に送られるためである。ヘッダーフリットによって宛先が決まり、そのトラヒックのフリットを出力する出力バッファが決まると、後に続くフリットは、ヘッダーフリットと同じ出力バッファを利用してヘッダーフリットが示す宛先に伝送される。
【００６０】
受信側のメモリは、制御コードフィールド６３に記述された終了コードを検出すると、その終了コードに基づき、伝送されたフリットをパケットへ再構築する。
【００６１】
たとえば、１パケットのサイズは１２８バイト、１フリットのサイズは３２ビットまたは６４ビットである。ただし、１パケットのサイズおよび１フリットのサイズはアプリケーションによって異なり得るため、上述のサイズは一例に過ぎないことに留意されたい。フリットの長さは、送信先のアドレスと、送信元のアドレスなど、制御データを記述できる長さを基準としてもよい。
【００６２】
各中継器には、送られてきたフリットを蓄えるためのバッファが用意されている。フリットは一旦そのバッファに蓄えられた後、スイッチの切り替えによって目的の経路へと続く中継器や、宛先のメモリへ送信される。
【００６３】
図７は、本実施形態における中継器７００の構成図である。
【００６４】
図７の中継器７００は、隣接する中継器群７１０、７１１と、バスによって接続されており、隣接の中継器群７１０から送信されたフリットを、正しい宛先へとつながる隣接中継器７１１群へ中継するために、スイッチを切り替えて、フリットの送信スケジュールを制御する。
【００６５】
中継器７００は、入力バッファ７０１と、スイッチ７０２と、出力バッファ７０３と、ルーティング処理部７０４と、バッファ割当部７０５と、スイッチ割当部７０６と、混雑情報処理部７０７と、混雑情報比較部７０８と、送信スケジュール調整部７０９とを有している。
【００６６】
以下、各構成要素の機能を説明する。
【００６７】
入力バッファ７０１は、隣接する中継器（またはバスマスタ）から送られてきたフリットを蓄える一時バッファである。入力バッファ７０１を構成する一時バッファは、中継器７００の入力ごとに１つ設けられていてもよいし、または、宛先の異なるパケットを区別して個別に蓄えて、それぞれ個別に送信スケジュール制御ができるように、入力ごとに複数の一時バッファが設けられていてもよい。本実施形態では、図７に示すように、入力毎に２個ずつ入力バッファを備えているとする。
【００６８】
スイッチ７０２は、中継器７００の入力と出力の接続の組合せを切り替えるためのクロスバースイッチである。
【００６９】
出力バッファ７０３は、隣接する中継器７１１へフリットを送信する際に利用する一時バッファである。出力バッファ７０３は、隣接する中継器７１１の入力バッファと同じ数だけ設けられている。中継器７００の各出力バッファと、中継器７１１の各入力バッファとの間には、１対１の対応関係が決められている。中継器７００の出力バッファから送信されたフリットは、その出力バッファ７０３に対応する隣接の中継器７１１の入力バッファに蓄えられる。したがって、中継器７００は、フリットの送信に利用する出力バッファを選択することで、隣接する中継器７１１の入力バッファを指定できる。
【００７０】
ルーティング処理部７０４は、入力バッファ７０１に新しいヘッダーフリットが送られてくると、それを受け取り、ヘッダーフリットに記述された宛先情報を基に、次に受け渡す中継器を特定する。
【００７１】
バッファ割当部７０５は、フリットが適切な経路へと中継されるように、フリットが蓄えられている入力バッファに対して、フリットを送信するための専用の出力バッファを割り当てる。
【００７２】
バッファ割当部７０５では、入力バッファにヘッダーフリットが到着すると、ルーティング処理部７０４で特定された送信経路に接続されている出力バッファ７０３の中から、その時点で利用されていない出力バッファを選択し、フリットを送信するための専用のバッファとして出力バッファ７０３を１つ割り当てる。
【００７３】
バッファ割当部７０５により、入力バッファと出力バッファとの組合せは、１つのパケット全体が中継器を通過するまで維持される。
【００７４】
スイッチ割当部７０６は、バッファ割当部７０５によって決定された入力バッファ７０１と出力バッファ７０３の組合せの中から、実際に隣接の中機器７１１に対してフリットを送信する組合せを決定し、入力バッファ７０１と出力バッファ７０３間のスイッチ７０２を切り替える。
【００７５】
混雑情報処理部７０７は、複数のトラヒックを共通して扱う近隣の中継器群７１０、７１１に対して要求を出し、トラヒックごとの混雑の程度を示す混雑情報を取得する。また混雑情報処理部７０７は、近隣の中継器群７１０、７１１から混雑情報の要求を受けたときは、その中継器に対して、各伝送経路のトラヒックごとにデータパケットの流れにくさを定量的に示した混雑情報を測定することによって取得し、取得した混雑情報をその中継器に出力する。
【００７６】
なお、混雑情報としては、例えばデータパケットが中継器を通過するまでにかかる遅延時間を測定し、その値を用いる。
【００７７】
伝送経路上でデータパケットが流れにくくなるほど、中継器７００内からバスへフリットが送信されなくなるため、データパケットの遅延時間が長くなるため、各伝送経路でのデータパケットの流れにくさを遅延時間から定量的に特定することができる。
【００７８】
混雑情報比較部７０８は、近隣の中継器７１０、７１１から通知されたトラヒックごとの混雑情報と、ヘッダに記述されている送信先によって定まる、トラヒックごとの中継器７００自身の混雑情報とを比較し、各トラヒックの経路上での流れにくさを定量的に示す混雑度を算出する。
【００７９】
送信スケジュール調整部７０９は、混雑情報比較部７０８で求められた混雑度に基づき、各トラヒックに対して、バスの伝送帯域の割り当てを調整する。
【００８０】
中継器７００における伝送帯域の割り当ての調整には、バッファ割当部７０５で出力バッファ７０３において一時バッファをどのように割り当てるかのスケジューリングの調整と、スイッチ割当部７０６がスイッチ７０２をどのように切り替えるかのスケジューリングの調整とが含まれている。
【００８１】
次に、各中継器７００の動作について説明する。
【００８２】
図８は、本実施形態における中継器７００の動作の流れを説明するフローチャートである。
【００８３】
中継器７００は、近隣の中継器７１０からフリットが送られてくると、入力バッファ７０１のうち、所定のバッファにそのフリットを蓄積する（ステップ８０１）。フリットを蓄積するバッファの選択方法は種々考えられる。たとえば先に説明したように、前段の中継器７１０の出力バッファから送信されたフリットを、その出力バッファ７０３に対応する隣接の中継器７１１の入力バッファに蓄えればよい。前段の中継器が存在せず、バスマスタからフリットが直接送信される場合には、バスマスタ側でフリットを蓄積する入力バッファを指定し、中継器７００はバスマスタ側で指定された入力バッファにフリットを蓄積すればよい。これ以外にも、フリットがヘッダーフリットの場合には、空のバッファへ蓄積し、ヘッダーフリットでない場合には、そのフリットに対応するヘッダーフリットが蓄積されたバッファへ蓄積してもよい。同じパケットを構成するフリットごとに区別して、異なる入力バッファを選択すればよい。
【００８４】
入力バッファ７０１は蓄積されたフリットがヘッダーフリットであるかどうかを判定する（ステップ８０２）。
【００８５】
蓄積されたフリットがヘッダーフリットであった場合には、ステップ８０３に進んでデータの次の送信先を特定するための処理に移り、ヘッダーフリットでない場合には、ステップ８０７に進み、そのフリットに対応するヘッダーフリットと同じ経路を送信先とする。
【００８６】
ルーティング処理部７０４は、入力バッファに送られてきたフリットがヘッダーフリットの場合、ヘッダーフリットに付与されている宛先のアドレス情報を基に、次に送る中継器を決定する（ステップ８０３）。
【００８７】
図５に示した多段接続網の場合では、各メモリに対し３桁の２進数でアドレスが割り当てられ、各パケットのヘッダーフリットには、宛先となるメモリのアドレスが、３桁の２進数が付与されている。
【００８８】
各中継器のルーティング制御部７０４は、ヘッダーフリットに付与された３桁のアドレスのうち、中継器の段数と同じ桁の数字を読み取る。そしてその値が０ならば図５における右上の中継器へフリットを送り、値が１ならば図５における右下の中継器へフリットを送るように経路を決定する。
【００８９】
例えば、バスマスタＢＭ２から、メモリ５（アドレス：１０１）へデータを送る場合には、アドレスに記載された３桁の数字に従って、まず中継器Ｒ１では右下の中継器Ｒ７へフリットが送信され、次に中継器Ｒ７では右上の中継器Ｒ１０にフリットが送信され、最後に中継器Ｒ１０で右下のメモリ５へフリットが送信される。これにより、バスマスタＢＭ５からメモリ２へとフリットが伝送される。
【００９０】
なお、ルーティング処理部７０４でのルーティング（経路）制御の方法としては、分散バスのトポロジーに応じて、適切に目的地までフリットが送られる方法であれば、上記以外の方法であってもよい。
【００９１】
フリットを送信する隣接の中継器が決まると、中継器７００は、混雑情報処理部７０７を介して、隣接する中継器７１１と中継器７１０から混雑情報を取得・参照する（ステップ８０４）。
【００９２】
図９は、伝送経路ごとに各トラヒックのパケットデータの流れにくさを定量的に測定可能な対象を説明する図である。測定された結果が混雑情報として取り扱われる。混雑情報は、中継器７００内での（１）データパケットが中継器７００を通過するまでにかかる遅延時間や、（２）入力バッファ内に残っているフリット数、（３）バスの空帯域等である。
【００９３】
集積回路では、実装面積やコスト等の課題から、回路上のバッファのサイズをできるだけ小さくすることが望まれる場合が多い。このため、入力バッファのサイズが小さい場合には、入力バッファ内のフリット数（２）を混雑の程度を測る指標として採用しては精度が低くなってしまう。また、バスの空帯域（３）を測定する場合には、所定の時間、バスの状態を記録ためのメモリ（バッファ）が必要となる。これに対し中継器内のフリットの遅延時間（１）を混雑の程度を測る指標とする場合には、少ないバッファサイズでも混雑の程度を精度よく測ることができる。
【００９４】
また、本実施形態では、中継器間を接続するバス（３）として電気信号を伝えるバスを想定しているが、これ以外にも、光信号によりデータを伝える有線バスや、磁気や電磁波を利用して信号を伝える無線バスであっても良い。さらに、光信号や電磁波による通信では、１つのバス上で異なる波長や周波数を同時に用いることができる。このためバス上で利用されている波長や周波数の利用数、又は空き数を基に混雑度と定義しても良い。
【００９５】
以下の説明では、中継器７００内のバッファサイズが少ない場合を想定し、（１）データパケットが中継器７００を通過するまでにかかる遅延時間を混雑情報として説明する。なお、バッファを確保できるのであれば、上述の（２）または（３）を採用してもよい。この混雑情報は、混雑情報処理部７０７によって取得される。
【００９６】
次に、混雑情報比較部７０８により、中継器７００と、隣接する中継器７１０（中継器７１１）との間での混雑情報を比較し、経路上でのトラヒックごとの流れにくさを示す混雑度を求める（ステップ８０５）。
【００９７】
図１０は、中継器自身７００と隣接する中継器７１１の混雑状態を比較して、自中継器７００において、トラヒックＡとトラヒックＢの混雑度の算出方法を説明する図である。
【００９８】
本実施形態では、混雑度の値は、混雑情報比較部７０６により、トラヒックごとに下流側にある中継器７１１から通知されたデータパケットの遅延時間と、自中継器７００でのデータパケットの遅延時間の比率を混雑度として定義する。
【００９９】
例えば、図１０において、トラヒックＡは、データパケットが中継器７００を通過するまでに１０サイクル、下流側の中継器７１１を通過するのに５サイクルの遅延が発生しているとする。このとき、トラヒックＡの混雑度は以下のように算出できる。
トラヒックＡの混雑度： ５／１０ ＝ ０．５
【０１００】
一方、トラヒックＢでは、データパケットが中継器７００を通過するために１２サイクル、中継器７１１を通過するために１５サイクルかかるとする。このとき、トラヒックＡの混雑度は以下のように算出できる。
トラヒックＢの混雑度： １５／１２ ＝ １．２５
ここで、混雑度の値が大きいほど、データパケットが流れにくいものとすると、中継器７００の近隣では、トラヒックＡの方がトラヒックＢよりもデータパケットの流れやすさを定量的に特定できる。
【０１０１】
図１０では、混雑度を中継器１の遅延時間と、中継器２の遅延時間の比率として定義したが、これ以外にも、例えば中継器１での遅延時間と中継器２での遅延時間の差分や、遅延時間の総和など、自中継器７００と隣接する中継器７１１の混雑情報の比較した値を混雑度として定義し、その値を用いてもよい。
【０１０２】
また、中継器間の遅延時間の値と混雑度の値との対応関係を予めテーブル情報として定義しておき、通知された遅延時間に対応する混雑度をテーブル情報を参照することで求める方法であってもよい。
【０１０３】
次に、図８のステップ８０６において、送信スケジュール調整部７０９は、トラヒックの混雑度に基づき、混雑度が求まっている入力バッファに対してフリットを送信するための優先順位を決定する。「混雑度が求まっている入力バッファ」とは、各トラヒックの混雑度と同じである。すなわち、混雑度ｘを有するトラヒックｔが存在するとき、そのトラヒックｔのフリットが入力される入力バッファの混雑度は、ｘとなる。そしてバッファ割当部７０５は、入力バッファの優先順位に基づいて出力バッファを割り当てる。
【０１０４】
図１１は、送信スケジュール調整部７０９と、バッファ割当部７０５とによる出力バッファ７０３の割り当て方法を説明する図である。
【０１０５】
中継器内で入力バッファには、トラヒックごとに区別されてフリットが蓄えられ、出力バッファを介して次の中継器へと送信される。
【０１０６】
図１１では、入力０からのトラヒックに対して入力バッファ０と入力バッファ１が用意されており、入力１からのトラヒックに対しては、入力バッファ２と入力バッファ３が用意されている。そして、混雑情報比較部７０８により入力バッファ０、入力バッファ１、入力バッファ２に対して、混雑度がそれぞれ１．０、０．２５、０．５と求められているとする。
【０１０７】
入力バッファがどの出力バッファに対して割り当てを要求するかは、先に説明したように、入力バッファに蓄積されている各トラヒックのフリットがどの送信経路でメモリに送信されるかによって特定される。異なる入力バッファが同じ出力に接続された２つの出力バッファに対して割り当てを要求することがあるため、出力バッファの割り当てを決定する必要がある。
【０１０８】
送信スケジュール調整部７０９は、混雑情報比較部７０８によって求められた混雑度の情報を基に、各入力バッファに対して、出力バッファの割り当ての優先順位を付与する。図１１の例では、各入力バッファの混雑度を、そのまま出力バッファの割り当ての優先順序として用いる場合を想定して説明する。なお、出力バッファの割り当ての優先順序は、その出力バッファから送出されるフリットが格納された入力バッファの混雑度の値が小さいものほど優先されるものとする。
【０１０９】
各入力バッファの優先度が決まると、各入力バッファは、ルーティング処理部７０４によって特定された次の中継器へ接続する出力側の出力バッファのうち、利用されていない出力バッファに対して、出力バッファの割り当てを要求する。
【０１１０】
バッファ割当部７０５は、各出力バッファに対して割り当て要求をしている入力バッファの中から、最も混雑度の小さいものに対して割り当ての決定を通知する。
【０１１１】
図１１の例では、入力バッファ０、入力バッファ１、入力バッファ２が、出力０側の出力バッファに対して、それぞれ割り当てを要求している。そして、要求のあった出力バッファごとに混雑度の最も小さかった入力バッファ０と、入力バッファ２に対して割り当ての決定がなされる。
【０１１２】
出力バッファの割り当ては、ヘッダーフリットを送信する際に決定され、そのヘッダーフリットに対応するパケットを構成する全てのフリットが送信されるまで、出力バッファが割り当てられている状態が継続される。
【０１１３】
次にスイッチ割当部７０６は、入力バッファの混雑度の小さいものから順番に入力バッファと出力バッファ間のスイッチを接続し、入力バッファ内のフリットを、隣接する中継器へと送信する（ステップ８０７）。
【０１１４】
図１２は、スイッチ割当部７０６によって出力バッファが割り当てられたトラヒック間で、送信スケジューリングを調整する方法を説明する図である。
【０１１５】
本実施形態における中継器での送信スケジューリングは、入力バッファと出力バッファ間でのスイッチの接続の切り替えによって行われる。
【０１１６】
図１２では、全ての入力バッファに対して、出力バッファの割り当てが完了している。入力バッファ０には出力バッファ０が割り当てられ、入力バッファ１には出力バッファ３が割り当てられている。また、入力バッファ２には出力バッファ１が割り当てられ、入力バッファ３には出力バッファ２が割り当てられている。
【０１１７】
スイッチ割当部７０６は、それぞれの出力に接続する出力バッファに接続する入力バッファの中で混雑度が小さい入力バッファに対してスイッチを接続し、隣接する中継器へフリットの送信を許可する。入力および出力の組が異なっていれば、スイッチ割当部７０６は、当該異なる組についてはスイッチを同時並列的に接続できる。
【０１１８】
図１２に示す、出力０に接続する出力バッファ０と出力バッファ１について検討すると、出力バッファ１を割り当てられた入力バッファ２の混雑度０．５の方が、出力バッファ０を割り当てられた入力バッファ０の混雑度１．０よりも小さい。そのため、入力バッファ２と出力バッファ１との間でスイッチの接続が行われる。スイッチが接続された入力バッファの中身が空になり、そのフリットの送信が終了すると、入力バッファ０と出力バッファ０との間でスイッチの接続が行われ、フリットが送信される。
【０１１９】
同様に、出力１に接続する出力バッファ２と出力バッファ３について検討すると、出力バッファ３を割り当てられた入力バッファ１の混雑度０．２５の方が、出力バッファ２を割り当てられた入力バッファ３の混雑度２．０より小さい。そのため、入力バッファ３と出力バッファ２との間でスイッチの接続が行われる。スイッチが接続された入力バッファの中身が空になり、そのフリットの送信が終了すると、入力バッファ１と出力バッファ３との間でスイッチの接続が行われ、フリットが送信される。その結果、それぞれフリットが隣接する異なる中継器に送信される。
【０１２０】
このように、各トラヒックの混雑度の値に基づいて、スイッチの割り当ての優先順序を調整することにより、各トラヒックに対して出力側のバスに対して伝送帯域の割り当て量を調整することができる。
【０１２１】
なお、スイッチの切り替え方法としては、混雑度の小さい入力バッファからスイッチの接続を切り替えて、順番に入力バッファの中身を空にする方法以外にも、例えば、重み付きラウンドロビン（Weighted Round Robin：WRR）を用いる方法がある。
【０１２２】
図１３は、重み付きラウンドロビンにより、スイッチを切り替える場合の、重みの割り当て方法を説明する図である。
【０１２３】
重み付きラウンドロビンでは、フリットの送信要求のあった全ての入力バッファに対して、１フリット送信するごとに、各出力バッファに付与された重みの値に応じた（比例した）確率でスイッチを接続する方法である。以下に説明する重みの算出処理や、割り当て処理は、送信スケジュール調整部７０９によって実行される。
【０１２４】
図１３の例では、各出力バッファの重みは、その出力バッファが割り当てられた入力バッファの混雑度に基づき、その逆数を重みとして用いている。具体的には、出力バッファ０に付与された重みは、入力バッファ０の混雑度１．０の逆数で１．０となる。出力バッファ１に付与された重みは、入力バッファ２の混雑度０．５の逆数で２．０となる。出力バッファ２に付与された重みは、入力バッファ３の混雑度２．０の逆数で０．５となる。出力バッファ３に付与された重みは、入力バッファ１の混雑度０．２５の逆数で４となる。
【０１２５】
重み付きラウンドロビンを使ってスイッチを切り替えた場合、出力０は、出力バッファ０と出力バッファ１のそれぞれの重みから、１対２の割合でそれぞれの出力バッファを経由してフリットを送信する。また出力１は、出力バッファ２と出力バッファ３のそれぞれの重みから、約１対８の割合でそれぞれの出力バッファを経由してフリットを送信する。
【０１２６】
このように、重み付きラウンドロビンによる送信スケジューリングでは、重みの値によって、出力バッファ間で、出力側のバスに対して伝送帯域の割り当ての割合を調整することができる。
【０１２７】
なお、図８のステップ８０６および８０９では、混雑度の値を、そのまま出力バッファの割り当てに用い、及びスイッチの割り当てに用いる場合を例に説明した。しかしながら、混雑度の値を反映したものであれば、別の定義を用いても良い。また出力バッファとスイッチの割り当てを優先させたい入力バッファに対して、優先度の値を小さくする例を説明したが、逆に大きい値を与え、値の大きいものから出力バッファとスイッチを与えるようにしてもよい。
【０１２８】
また、重み付きラウンドロビンによる各出力バッファへの伝送帯域の割り当ての具体的な調整方法としては、伝送帯域を時間的に複数のタイムスロットに分割し、重みの値によって指定された数のタイムスロットをそれぞれの出力バッファに割り当てる方法や、重みの値によって予め指定された割合で、確率的に出力バス（出力バッファ）を選択する方法などがある。
【０１２９】
ヘッダーフリット以外のフリットを送信する場合には、ステップ８０３のルーティングおよびステップ８０６の出力バッファの割り当ては行われない。混雑情報処理部７０７は、隣接する中継器の混雑情報の取得と参照（ステップ８０７）を行い、混雑情報比較部７０８は近隣の中継器と互いの混雑状況の比較（ステップ８０８）のみを行う。隣接する中継器の混雑情報の取得・参照方法（ステップ８０７）と近隣の中継器と互いの混雑情報の比較方法（ステップ８０８）については、それぞれ（ステップ８０４）と（ステップ８０５）の処理と同じであるため、説明を省略する。
【０１３０】
中継器７００は、スイッチ割当部７０６によってスイッチ７０２の割り当てが決定すると入力バッファ内のフリットを、割り当てられた出力バッファを介して隣接する中継器７１１へと送信する（ステップ８１０）。
【０１３１】
混雑情報処理部７０７は、フリット送信後の中継器の混雑情報を近隣の中継器７１０、７１１に通知する（ステップ８１１）。
【０１３２】
次に図１４、図１５、図１６を用いて、本実施形態における中継器の動作を詳細に説明する。
【０１３３】
図１４は、図５の多段接続網における、トラヒックＡ〜Ｃの各伝送経路を示す。トラヒックＡはバスマスタＢＭ０からメモリ４へ伝送される。トラヒックＢは、バスマスタＢＭ１からメモリ６へ伝送される。トラヒックＣは、バスマスタＢＭ５からメモリ５へ伝送される。
【０１３４】
トラヒックＡとトラヒックＢが同時に流れる場合には、中継器Ｒ０から中継器Ｒ６へのバス上で干渉が発生する。また、トラヒックＡとトラヒックＣが同時に流れる場合には、中継器Ｒ６から中継器Ｒ１０へのバス上で干渉が発生する。
【０１３５】
図１５は、トラヒックＡとトラヒックＢとが同時に流れている場合の、トラヒックＡの伝送経路上での各中継器の遅延時間の例を示す。
【０１３６】
図１５において、中継器Ｒ０内でのトラヒックＡとトラヒックＢの遅延時間は、互いの干渉により、それぞれ１０サイクルとする。また、中継器Ｒ６内でのトラヒックＡとトラヒックＢの遅延時間はそれぞれ別の経路に流れるため、それぞれ５サイクルとする。すると、中継器Ｒ０でのトラヒックＡの混雑度は０．５、トラヒックＢの混雑度は０．５となり、伝送経路上の流れにくさは、どちらのトラヒックも同じになる。そのため、中継器Ｒ０は、中継器Ｒ６へのバスの伝送帯域を、トラヒックＡとトラヒックＢに対して均等に５０％ずつ割り当てるように送信のスケジューリングを調整する。スケジューリングとは出力バッファの割り当てと、スイッチの割り当てを意味する。以下も同様である。
【０１３７】
次に、図１６は、トラヒックＡとトラヒックＢに加えて、トラヒックＣが同時に流れる場合の各中継器内でのトラヒックの遅延時間の例を示す。
【０１３８】
図１６において、中継器Ｒ０内でのトラヒックＡとトラヒックＢの遅延時間は互いの干渉によりそれぞれ１０サイクルとする。また、中継器Ｒ６内では、トラヒックＡとトラヒックＣとが互いに干渉することにより、遅延時間がそれぞれ１０サイクルとする。一方、別の経路へ流れるトラヒックＢは、他のトラヒックと干渉しないため、遅延時間が５サイクルとする。すると、中継器Ｒ０でのトラヒックＡの混雑度は１、トラヒックＢの混雑度は０．５となり、トラヒックＡの方がトラヒックＢよりも伝送経路上において流れにくいことが特定される。
【０１３９】
中継器Ｒ０は、トラヒックＡとトラヒックＢの混雑度の大きさに合わせて、中継器Ｒ６へのバスの伝送帯域を割り当てる。例えば、中継器Ｒ１が重み付きラウンドロビンを用いて各トラヒックに混雑度の値に反比例させた伝送帯域を割り当てた場合には、中継器Ｒ０は、トラヒックＡには伝送帯域の３３％、トラヒックＢには伝送帯域の６６％を割り当てるように送信のスケジューリングを調整する。
【０１４０】
また、中継器Ｒ０によってトラヒックＡの伝送帯域の割り当てが少なくなると、中継器Ｒ０では、トラヒックＡとトラヒックＢの干渉が弱められるため、トラヒックＢの遅延時間が削減される。また、Ｒ６ではトラヒックＡとトラヒックＣの干渉が弱められるため、トラヒックＣの遅延時間が削減される。
【０１４１】
このように、トラヒック数や流量の変化に対し、伝送経路上において複数のトラヒックと干渉しているトラヒックＣの伝送帯域を減らすことで、互いに干渉しないトラヒックＢとトラヒックＣの伝送帯域を増やし、優先的にトラヒックＢとトラヒックＣを流すことで、回路全体の利用効率の低下を防ぎ、遅延の増加やスループットの低下を抑止することができる。
【０１４２】
図１７は、混雑度の定義として、自中継器と隣接中継器との混雑情報の比率の変わりに、差分を用いた例を示す。
【０１４３】
図１７では、トラヒックごとに自中継器での遅延時間から、送信先の隣接中継での遅延時間を引いた値を混雑度として定義している。なお、図１７の式では、混雑度を重み付きラウンドロビンで扱えるようにするために、定数αを加えている。これにより、混雑度を正の数として扱うことが可能となる。定数αの具体的な値としては、混雑度が負の値とならないように、中継内で許容できる遅延時間の最大値の値を設定する方法が考えられる。
【０１４４】
また、本実施形態では、トラヒックが流れる下流側の中継器の混雑情報を基に、送信スケジューリング（出力バッファの割り当て、スイッチの割り当て）が調整される例を説明した。しかしながら、トラヒックが流れてきた上流側の中継器の混雑情報を基に送信スケジューリングが調整されてもよい。
【０１４５】
図１８は、トラヒックの流れの上流側にある中継器Ｒ０での遅延時間と、中継器Ｒ２での遅延時間とを基に、中継器Ｒ６がトラヒックＡとトラヒックＣに中継器Ｒ１０へのバスの伝送帯域をどのように割り当てるかを説明する図である。
【０１４６】
図１８では、中継器Ｒ０内でのトラヒックＡとトラヒックＢの遅延時間は、互いの干渉によりそれぞれ１０サイクルとする。また、中継器Ｒ６内では、トラヒックＡとトラヒックＣが互いに干渉し、遅延時間はそれぞれ１０サイクルとする、中継器Ｒ２では、トラヒックＣのみが流れているため遅延時間が５サイクルであるとする。
【０１４７】
中継器Ｒ６は、中継器Ｒ０より、トラヒックＡとトラヒックＢの遅延時間を取得し、中継器Ｒ２より、トラヒックＣの遅延時間を取得し、自中継器内でのそれぞれのトラヒックの遅延時間との比較から混雑度を算出する。ここでトラヒックが流れる下流側の中継器から通知された遅延時間を使って混雑度を算出した場合と同様に、混雑度の定義として、トラヒックが流れる上流側の中継器での遅延時間に対する、その下流にある自中継器Ｒ６での遅延時間の比率の値を用いる。
【０１４８】
トラヒックＡの混雑度は、１（＝１０÷１０）、トラヒックＢの混雑度は０．５（＝５÷１０）と求められる。
【０１４９】
混雑度が求まると、中継器Ｒ６は、例えば、中継器Ｒ１が重み付きラウンドロビンを用いて、混雑度の値に反比例させて各トラヒックに伝送帯域を割り当てた場合には、トラヒックＡには伝送帯域の３３％、トラヒックＣには伝送帯域の６６％が割り当てるように送信のスケジューリングの調整が行われる。
【０１５０】
また、中継器Ｒ６において、トラヒックが流れる上流側の中継器からの混雑情報だけでなく、下流側の中継器からの混雑情報も用いて伝送経路上での混雑度を求め、これを送信スケジューリングの調整に用いてもよい。
【０１５１】
例えば、トラヒックごとに上流側の混雑度と下流側の混雑度を求め、その平均値を混雑度と定義してもよい。
【０１５２】
以上のように、図７を用いて説明した構成と、図８で説明した処理とにより、伝送経路上の各中継器が、隣接する中継器間で混雑情報を交換し、その比較から伝送経路上でのトラヒックの流れにくさを示す混雑度を基に、各トラヒックの送信スケジューリングを調整する。これにより、トラヒック間の干渉による遅延の増加を抑制が可能となる。
【０１５３】
なお、本実施形態では、集積回路のトポロジーが多段接続網の場合を例に説明したが、図１９に示すように中継器を格子状に並べてメッシュ型や、トーラス型、バスを階層的に接続したトポロジーなど中継器やスイッチを介して複数のバスを経由するトポロジーでも同様に適用できる。
【０１５４】
（実施形態２）
実施形態１では、隣接する中継器間で混雑情報を交換し、トラヒックごとに伝送経路上でのデータパケットの流れにくさを示す混雑度に基づいて、各トラヒックの送信スケジューリングを調整した。
【０１５５】
これに対し、本実施形態の中継器は、求められた混雑度を比較し、データパケットの流れにくい方のパケットをいったん廃棄し、再度、廃棄したパケットの送信元となるバスマスタにパケットの再送を要求する。これにより、混雑度の小さいトラヒックの遅延時間の増加を抑制することができる。なお、バスマスタにパケットの再送を直接要求するのではなく、宛先をそのバスマスタとする再送要求を含むフリットを、そのパケットを送信してきた隣接する中継器のバッファに送信することに留意されたい。隣接する中継器は、その再送要求をさらに上流の中継器または当該バスマスタに送信することになる。
【０１５６】
中継器は、再送要求を、１サイクルで送信可能なデータ量である１フリットで送信することができる。しかしながら、フリット数は２以上であってもよい。または、再送要求をパケットで送信してもよい。再送要求は通常のトラヒックが流れる伝送経路上を送信されてもよいが、再送要求専用の伝送経路を設けてもよい。
【０１５７】
インターネットや無線ＬＡＮ等でのネットワーク制御では、一般的に中継器での混雑（輻輳）を抑制する方法としてパケットを廃棄が用いられる。しかしながら、集積回路では信頼性への要求が高いため、回路内を流れるトラヒックのデータロスが発生すると、混雑時に廃棄したパケットを再度、送信元から再送する必要がある。
【０１５８】
図２０は、本実施形態における中継器８００の構成図の構成図である。図２０の構成要素のうち図７と同じ構成については、同じ参照符号を付与し説明を省略する。
【０１５９】
パケット廃棄部１４０１は、混雑情報比較部７０８によって求められたトラヒックごとの混雑度のうち、所定の閾値を越えるトラヒックを検出した場合に、該当するトラヒックのパケットを入力バッファ７０１から削除する。
【０１６０】
再送要求部１４０２は、前記パケット廃棄部により、削除されたパケットの再送要求を、送信元のバスマスタに通知する。
【０１６１】
図２１は、本実施形態においてバスマスタから送信されるパケットとそのフリット群、および、ヘッダーフリットに記載される情報を示す。ヘッダーフリットには、ヘッダフラグや宛先アドレスの他、送信元のアドレス、及び、パケットのＩＤが記載されている。パケット廃棄部１４０１がパケットを廃棄する場合に備えて、再送要求部１４０２はそのパケットのヘッダーフリットの情報（少なくとも送信元のアドレス、及び、パケットのＩＤ）をヘッダーフリットが到着するたびに記憶しておく。そして、保持していたその情報に基づいて、送信元のバスマスタに、特定のＩＤを有するパケットの再送を要求する。
【０１６２】
パケットを廃棄されたバスマスタは、混雑を避けるために所定の時間待機し、再びパケットの送信を開始する。
【０１６３】
図２２は、本実施形態における中継器８００の動作を説明する図である。
【０１６４】
図８と同様の動作については、同じ参照符号を付与し説明を省略する。
【０１６５】
中継器８００は、隣接する中継器７１０と互いの混雑情報を交換し、トラヒックごとに経路上でのトラヒックの流れにくさを混雑度として算出し、その値が所定の閾値以内に収まっているかどうかを判定する（ステップ２４０１）。混雑度の値が、閾値以下であれば、入力バッファ内のフリットを送信するためにスイッチの割り当て処理を行うためにステップ８０９に移る。
【０１６６】
ステップ２４０１において、混雑度が所定の閾値を超えたと判定された場合には、中継器８００のパケット廃棄部１４０１は、該当する入力バッファ内のフリットを全て廃棄し、また、その入力バッファに割り当てられた出力バッファを開放する（ステップ２４０２）。
【０１６７】
混雑度が所定の閾値以上を越えた入力バッファ内のフリットが廃棄されると、中継器内の再送要求部１４０２は、廃棄したパケットの送信元に、廃棄したパケットの再送を要求する（ステップ２４０３）。
【０１６８】
再送要求部１４０２から送信元に再送を通知する方法として、トラヒックが流れてきた伝送経路を、逆方向に、再送要求を伝えるパケットを転送する方法や、中継器８００と送信元との間で再送を通知するための、専用の制御信号線を用いる方法が挙げられる。
【０１６９】
以上の構成と処理を加えることにより、本実施形態における中継器８００は、混雑度が所定の閾値よりも高いトラヒックのパケットを廃棄するので、パケットデータの流れにくいトラヒックによる、回路全体での伝送性能の低下を抑制できる。
【０１７０】
（実施形態３）
本実施形態では、宛先が共通するパケットを連続して次の中継器に送信する際に、同じ出力バッファを利用して次の中継器に送信し、さらに、連続して送ったパケットが同じ宛先に向かうパケットであることを次の中継器に通知することで、後続のパケットで行われるルーティング処理（ステップ８０３）と出力バッファの割り当て（ステップ８０６）省略し、中継器内での遅延時間を短縮する。
【０１７１】
図２３は、本実施形態における中継器８１０の構成図である。図２３の構成要素のうち図７と同じ構成については、同じ参照符号を付与し説明を省略する。
【０１７２】
ルーティング再利用通知部１５０１は、宛先が共通するパケットが、同じ出力バッファを介して、次の中継器７１１に伝送される際に、連続して送ったパケットが同じ宛先に送られるパケットであることを次の中継器７１１に通知する処理部である。なお、同じ出力バッファを介して次の中継器７１１に送られたパケットは、次の中継器７１１において同じ入力バッファに送られるものとする。
【０１７３】
図２４は、本実施形態における中継器８１０の動作を説明する図である。
【０１７４】
図８と同様の動作については、同じ参照符号を付与して説明を省略する。
【０１７５】
連続して送ったパケットが同じ宛先に送られるパケットである場合には、中継器８１０のルーティング再利用通知部１５０１は、ルーティング処理の再利用を行わせるための通知を次の中継器７１１に送信する。以下、この処理を行う中継器８１０の処理を説明する。
【０１７６】
隣接する中継器７１０からフリットが送られてくると、中継器８１０は、自らの入力バッファ７０１のうち、所定の入力バッファにフリットを蓄積する（ステップ８０１）。
【０１７７】
ステップ８０２において、受信したフリットがヘッダーフリットである場合には、ルーティング処理部７０１は、中継器７１０からルーティングの再利用通知を受信しているか否かを確認する（ステップ２６０１）。
【０１７８】
ルーティングの再利用通知がない場合には、次の送信先を特定する必要がある。そこで、ルーティング処理部７０４はルーティング処理を行う（ステップ８０３）。
【０１７９】
一方、ルーティングの再利用通知がある場合には、ルーティング処理部７０４はルーティング処理を省略し、1つ前のパケットの送信時に用いたルーティングの処理結果を利用できるか否か、言い換えると、出力バッファの再利用が可能か否かを判断する（ステップ２６０２）。
【０１８０】
バッファ割当部７０５は、再利用通知を受信した入力バッファを継続して利用でき、かつ、1つ前のパケットの送信時に利用した出力バッファが他の入力バッファからの要求によって割り当てられていない場合には、出力バッファの再利用が可能であると判断する。このとき、バッファ割当部７０５は、出力バッファの割当の決定（ステップ８０６）を省略し、１つ前のパケットの送信時に用いた出力バッファを再利用する。さらに、ルーティング再利用通知部１５０１は、次の中継器７１１にルーティングの再利用を通知する（ステップ２６０３）。
【０１８１】
１つ前のパケットの送信時に利用した出力バッファを継続して利用できない場合には、処理はステップ８０４に進み、バッファ割当部７０５は利用する出力バッファを再度決定する。
【０１８２】
ステップ８０６において、バッファ割当部７０５により、入力バッファに対して出力バッファが割り当てられると、ルーティング再利用通知部１５０１は、入力バッファ内のパケットの宛先が、１つ前のパケットの宛先と同じかどうか判定する（ステップ２６０４）。同じ出力バッファに宛先が同じパケットが連続して割り当てられると、ルーティング再利用通知１５０１は、ルーティング処理が不要であることをパケットが中継される次の中継器に通知する（ステップ２６０５）。
【０１８３】
このように、本実施形態の中継器８１０は、ルーティング再利用通知部１５０１により、ルーティングの再利用の可否を判定し、再利用が可能な場合には、ルーティングの再利用が可能であることを次の中継器７１１に通知する。そして次の中継器７１１でのルーティング処理（ステップ８０３）および出力バッファの割り当て（ステップ８０６）を省略する。これにより、中継器内での遅延時間の削減できる。
【０１８４】
また、バッファ割当部７０５において、各入力バッファに対して、出力バッファを割り当てる際に、混雑情報に基づいて、宛先が同じパケットを、同じ出力バッファに連続して割り当てるようにしても良い。
【０１８５】
例えば、中継器を通過するトラヒックの数に対して、入出力バッファの数が少ない場合には、トラヒック間で入出力バッファを交代して利用しなければならない。このため、混雑度の低いトラヒックに対してのみ、優先的に同じ入出力バッファを割り当てて、連続して同じ宛先のパケットが、同じ出力バッファを介して次の中継器に送信されるようにする。これにより混雑度が低いトラヒックの遅延時間をさらに削減することができる。
【０１８６】
以上の構成と処理を加えることにより、本実施形態における中継器８１０は、混雑度が低いトラヒックに対するルーティング処理と出力バッファの割り当てに必要な処理を省略できるため、回路全体での伝送性能の低下を抑制することができる。
【０１８７】
なお、本実施形態の説明では、混雑度の低いトラヒックには、同じ出力バッファを優先的に割り当てる場合を例に説明した。しかしながら、逆に混雑度の高いトラヒックに同じ出力バッファを優先的に割り当てることによって、混雑度の高いトラヒックの遅延時間を抑制してもよい。これにより、伝送遅延の改善をするようにしてもよい。
【０１８８】
なお、本実施形態では、ルーティング再利用通知により、ルーティング処理を省略するとした。ルーティング処理のための計算処理、および再利用の可否判定は、いずれも最低１サイクルかかる。したがって、トラヒックを受信した中継器自らがルーティングを行わないことにより、処理時間を改善することが可能になる。
【０１８９】
ルーティング再利用通知の「判定処理」は、たとえば、ヘッダーフリットの「判定処理」と並行して行うことができる。よって、処理時間を増加させることはない。
【０１９０】
よって、前段の中継器でのルーティングの結果を、次の中継器に順番に伝えて同じ処理を省略することにより、処理時間の削減が可能になる。
【０１９１】
（実施形態４）
本実施形態では、中継器により、分散バスの動作クロックを個別変更ができる場合を想定し、混雑度の大きいトラヒックが流れる経路上のバスの動作クロックを上げ、フリットを他のバスよりも早く送信することで、伝送遅延を抑制する。
【０１９２】
図２５は、本実施形態における中継器８２０の構成図である。図２５の構成要素のうち図７と同じ構成については、同じ参照符号を付与し説明を省略する。
【０１９３】
動作クロック調整部１６０１は、送信スケジュール調整部７０９により、混雑度が大きく優先度の低いトラヒックを検出すると、トラヒックが出力される側のバスの動作クロックを向上させる。
【０１９４】
図２６は、本実施形態における中継器８２０の動作を説明する図である。
【０１９５】
図８と同じ動作については、同じ参照符号を付与し説明を省略する。
【０１９６】
動作クロック調整部１６０１は、スイッチ割当部７０６によって、各入力バッファと出力バッファ間でのスイッチの割り当てが決定されると、バッファの混雑度が所定の閾値よりも高いかどうかを判定する（ステップ２７０１）。
【０１９７】
混雑度が閾値を超える入力バッファが存在しなければ、動作クロック調整部１６０１は、対応するバスの動作速度を、通常の利用時を想定して事前に設定した動作速度に設定する（ステップ２７０２）。
【０１９８】
混雑度が閾値を越える入力バッファが存在する場合には、動作クロック調整部１６０１は、対応するバスの動作速度を、通常の利用時を想定して事前に設定した動作速度よりも早い動作速度に設定する（ステップ２７０３）。
【０１９９】
以上の構成を加えることにより、本実施形態の中継器８２０は、混雑度の高いトラヒックを素早く次の中継器へ送信し、遅延時間を削減することが可能になる。よって、回路全体の伝送性能の低下を抑制することができる。
【０２００】
（実施形態５）
本実施形態１から４においては、隣接する中継器間でトラヒックごとの遅延時間を交換し、互いの遅延時間の比較によってトラヒックごとに経路上での流れにくさを求め、その値に基づいて各トラヒックへの送信スケジューリングを調整する。このため、実施形態１から実施形態４の中継器は、隣接する中継器どうしが連携し、協調した送信スケジューリング制御を行う。
【０２０１】
このような中継器間で協調した送信スケジューリング制御では、ある中継器において、あるトラヒックの遅延時間が、所定の閾値よりも大きくなった場合。このトラヒックの遅延時間を抑制しようとしても、隣接する中継器と協調した送信スケジューリングが優先され、すぐに自中継器内でトラヒックの遅延が発生する。
【０２０２】
これに対し、本実施形態では、自中継器での混雑度が所定の閾値よりも高い場合は、隣接する中継器と協調した送信スケジューリングを行わず、自中継器内での混雑の状況にのみに基づいて、自中継器内での遅延を抑制するように利己的な送信スケジューリングを行う。
【０２０３】
図２７は、本実施形態における中継器８３０の構成を示す図である。図２７の構成要素のうち図７と同じ構成については、同じ参照符号を付与し説明を省略する。
【０２０４】
内部混雑情報監視部２８０１は、自中継器８３０でのトラヒックの遅延時間が、所定の閾値を越えているかどうかを判定する処理部である。
【０２０５】
協調制御停止部２８０２は、自中継器８３０でのトラヒックの遅延時間が、所定の閾値を超えた場合に、隣接する中継器７１１との遅延時間の比較による混雑度の算出をやめて、代わりに自中継器での遅延時間にのみ基づいて、混雑度を特定する処理部である。
【０２０６】
図２８は、本実施形態における中継器８３０の動作を説明する図である。
【０２０７】
図８と同じ動作については、同じ参照符号を付与し説明を省略する。
【０２０８】
中継器８３０の内部混雑度監視部２８０１は、自中継器８３０内の入力バッファの遅延時間が、所定の閾値よりも大きいかどうかを判定する（ステップ２８０１）。
【０２０９】
自中継器８３０内の入力バッファの遅延時間が、所定の閾値よりも小さい場合には、協調制御停止部２８０２は、混雑情報比較部７０８に指示して、隣接する中継器７１１での遅延時間と自中継器８３０での遅延時間の比較により混雑度を求め、送信スケジュール調整部７０９に混雑度を伝える（ステップ２８０２）。
【０２１０】
一方、自中継器８３０内の入力バッファの遅延時間が、所定の閾値よりも大きい場合には、協調制御停止部２８０２は、混雑情報比較部７０８に代わり自中継器８３０での遅延時間の大きさだけを利用して混雑度を求め、送信スケジュール調整部７０９に混雑度を伝える（ステップ２８０２）。
【０２１１】
以上の構成を加えることにより、本実施形態の中継器８３０は、自中継器で発生している遅延時間が所定の閾値よりも高い場合には、隣接する中継器の混雑の状況に合わせることなく、利己的な送信スケジューリング制御によって、自中継器内での遅延時間の削減を最優先させることができるため、回路全体の伝送性能の低下を抑制しながらも、局所的な伝送性能の低下も抑制することができる。
【０２１２】
（実施形態６）
実施形態６では、回線交換方式の中継器が送信スケジュールを調整する処理を説明する。
【０２１３】
図２９はパケット交換方式と回線交換方式の違いを説明する図である。
【０２１４】
図２９（ａ）、（ｂ）のグラフは、それぞれ交換方式でのデータの流れ方を表しており、グラフの縦軸はデータの位置、横軸は時間の流れを表している。
【０２１５】
パケット交換方式では、図２９（ａ）に示すように、トラヒックはフリット単位でバスマスタから順番に中継器へと送信される。
【０２１６】
これに対し、回線交換方式では、図２９（ｂ）に示すように、最初に回線交換のための信号がバスマスタから順番に中継器を通って宛先まで送られる。これにより回線が切り替えられ、その後、データが送信される。
【０２１７】
図３０は、本実施形態による、回線交換方式の中継器８４０の構成を示す。中継器８４０では、図３０に示すように、入力バッファ７０１は、スイッチの切り替え信号を蓄えるための１フリット分のサイズだけあればよい。それ以外は図７のパケット交換方式の構成と同じであるため説明は省略する。
【０２１８】
回線交換方式では、回線が確保された後は、トラヒック間で干渉が発生しないため、データの送信前のスイッチの切り替え用の信号についてのみ送信スケジューリングを調整すればよく、その調整は、パケット交換方式のヘッダーフリットと同様の方法で調整できる。
【０２１９】
以上、本発明の各実施形態を説明した。本明細書においては、各実施形態の中継器の構成要素はいずれもハードウェアによって実現されることを想定して説明した。ハードウェアは、構成要素ごとに設けられてもよいし、複数の構成要素を統合した回路などとして設けられてもよい。ハードウェアとして設けることにより、各中継器の処理が高速化され、内部処理遅延を最小限に抑えることが可能になる。なお、内部処理遅延が問題とならない程度に高速に処理できる場合には、上述の構成要素の１つまたは複数の機能をマイコンがソフトウェアを実行することにより、ソフトウェア的に実現してもよい。
【産業上の利用可能性】
【０２２０】
本発明にかかる中継器は、分散型のバスを備える集積回路において、複数のトラヒックの干渉による遅延やジッターの増加を抑制することができるため、メディア処理などリアルタイムで複数のトラヒック伝送が発生するＳｏＣ（System on Chip）などでの分散バス制御において有用である。
【０２２１】
また、遅延時間を抑制による処理時間の短縮化により、集積回路の省電化にも有用である。
【符号の説明】
【０２２２】
７００ 中継器
７０１ 入力バッファ
７０２ スイッチ
７０３ 出力バッファ
７０４ ルーティング処理部
７０５ バッファ割当部
７０６ スイッチ割当部
７０７ 混雑情報処理部
７０８ 混雑情報比較部
７０９ 送信スケジュール調整部
７１０ 隣接の中継器（受信側）
７１１ 隣接の中継器（送信側）
１４０１ パケット廃棄部
１４０２ 再送要求部
１５０１ ルーティング再利用通知部
１６０１ 動作クロック調整部
２８０１ 内部混雑情報監視部
２８０２ 協調制御停止部
【技術分野】
【０００１】
本発明は、分散型のバスを備える半導体の集積体回路において、バス間を接続する複数の中継器間を流れる複数のトラヒックの送信スケジューリングを調整する技術に関する。
【背景技術】
【０００２】
図１（ａ）は、集中型のバス制御の例を示す。集中型のバス制御を行う従来の集積回路では、主に複数のバスマスタとメモリとの間は１つのバスによって接続され、アービターによって各バスマスタからメモリへのアクセスが調停される。しかし、集積回路の高機能化、マルチコア化により、回路の規模が増大し、トラヒックも複雑に変動しながらバスを流れており、集中型のバス制御による集積回路の設計が困難になってきている。
【０００３】
その一方で、近年、並列計算機での接続技術や、ネットワーク制御の技術を取り入れた分散型のバスを有する半導体集積回路の開発が進んでいる。図１（ｂ）は、分散型のバス制御の例を示す。分散型のバスを有する半導体集積回路は、複数の中継器が複数のバスで接続されて構成されている。近年、図１（ｂ）に示すような分散型のバスを用いることにより、大規模化した集積回路内のトラヒックを、複数のバスに分散して伝送するネットワークオンチップ（Network on Chip）の取り組みがある。
【０００４】
しかしながら、分散型のバスでは、中継器によって隔てられたバスマスタ間で、互いの送信スケジュールで調停が行われない。そのため、中継器において、トラヒックが合流する数やトラヒックの流量の変化によって干渉が発生し、遅延時間やジッターの増加、スループットの低下など、伝送品質の低下を引き起こす。
【０００５】
分散型バスを流れるトラヒックの伝送品質の低下を回避する技術として、中継器において、トラヒックごとの送信スケジューリングを調整することで、中継器でのトラヒック間の干渉を抑制する技術が従来知られていた（例えば、特許文献１参照）。
【０００６】
図２は、特許文献１に記載された、従来の送信スケジューリングを制御する中継器の構成、および、トラヒックＡ〜Ｃの送信経路を示す。トラヒックＡは、バスマスタＡから、中継器Ｅおよび中継器Ｆを介してメモリＤへ送信される。トラヒックＢは、バスマスタＢから、中継器Ｅおよび中継器Ｆを介してメモリＤへ送信される。トラヒックＣは、バスマスタＣから、中継器Ｆを介してメモリＤへ送信される。
【０００７】
図２に示す中継器は、複数の送信バッファを備えている。また、バスマスタＡ〜Ｃから送信されるデータパケットには、そのデータパケットがどのトラヒックのデータパケットであるかを特定するための情報が付与されている。
【０００８】
各中継器は、データパケットを受信するとトラヒックごとに区別して各データパケットを異なるバッファに蓄える。そして、次の中継器へデータパケットを送信する際に、各トラヒックの伝送品質（遅延時間やスループット）が公平となるように、各バッファ内のデータパケットを送信する。この処理は、「スケジューリング調整処理」と呼ばれる。
【０００９】
図２の例では、トラヒックＡとトラヒックＢとが合流する中継器Ｅでは、それぞれのトラヒックを中継器２へ中継する際に、５０％ずつ公平に帯域が割り当てられるように、送信スケジューリングが調整される。さらに、トラヒックＡ、トラヒックＢ、トラヒックＣが合流する中継器Ｆでは、同様に各トラヒックに３３％ずつ公平に帯域が割り当てられるように、送信スケジューリングが調整される。
【００１０】
これにより、３つのバスマスタからメモリＤへの各トラヒックには公平に伝送帯域が割り当てられるため、トラヒック間の干渉による伝送性能の低下を抑制することができる。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００８−５４１６４７号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
従来の中継器では、中継器ごとに自身を通過するトラヒックの状態のみに基づいて、送信スケジューリングが調整され、局所的には伝送性能が公平となるように制御が行われている。言い換えると、各中継器は、独立して利己的に送信スケジューリングを調整している。これでは、優先度が高く設定されたトラヒックなどの、回路を流れるトラヒックの条件によっては、各中継器が行う送信スケジュールの調整によってトラヒック間の競合が発生し、却って回路全体の伝送性能（遅延時間やスループット）を低下させることがあった。
【００１３】
この課題を、以下、より具体的に説明する。
【００１４】
図３は、トラヒック間で競合が発生したときのトラヒックＡ〜Ｃを示している。
【００１５】
図３において、バスマスタＡはトラヒックＡを、中継器Ｅと中継器Ｆを介してメモリＧへ送信し、バスマスタＢはトラヒックＢを、中継器Ｅと中継器Ｆを介してメモリＤへ送信し、バスマスタＣはトラヒックＣを、中継器Ｆを介してメモリＤへ送信している。
【００１６】
さらに、図３では、トラヒックＣは、緊急時に送信される、相対的に高い優先度が設定されていると想定している。このようなトラヒックＣに、中継器Ｆは優先的にメモリＤへのバスの全ての伝送帯域（１００％）を割り当てる。この結果、トラヒックＢにはメモリＤへのバスの帯域が割り当てられていないことになる。
【００１７】
中継器Ｅと中継器Ｆにおける送信スケジュールの調整を、従来のように、各中継器が自身を通過するトラヒックの状態のみに基づいて行ってしまうと、トラヒックＢの送信先の中継器ＦがトラヒックＢにバスの帯域を割り当てていないにもかかわらず、中継器Ｅは、トラヒックＡとトラヒックＢに、それぞれ５０％の伝送帯域を公平に割り当ててしまう。これでは、回路全体では、中継器Ｅによる送信スケジューリング制御は、中継器Ｅから中継器Ｆへのバスの利用効率を却って低下させることになる。
【００１８】
本発明は上記課題を解決するためになされたものであり、その目的は、回路全体の遅延時間やジッターの増加、スループットの低下などを抑制させるよう、中継器におけるトラヒックの流量を制御することにある。
【課題を解決するための手段】
【００１９】
本発明による中継器は、分散型のバスを備える集積回路において、複数のバスを接続する中継器であって、前記バス上を伝送される各トラヒックのトラヒックデータは、パケットに分割されており、前記中継器は、トラヒックデータを受け取る入力および前記トラヒックデータを送出する出力の組み合わせを切り替えるスイッチと、複数のトラヒックを共通して扱う隣接の中継器からのトラヒックごとの混雑の程度を示す混雑情報と、自中継器における前記トラヒックごとの混雑情報とを取得する混雑情報処理部と、前記隣接の中継器から取得した前記混雑情報および自中継器における前記混雑情報に基づいて、伝送経路上でのトラヒックごとの流れにくさを定量的に示す混雑度の情報を求める混雑情報比較部と、前記混雑度に基づいて、前記トラヒックごとにバスの伝送帯域を割り当てて送信スケジュールを調整する送信スケジュール調整部と、前記バスの伝送帯域の割り当て結果に基づき、前記スイッチを切り替えるスイッチ割当部と、前記混雑度が予め定められた閾値よりも大きいトラヒックのパケットを入力バッファから廃棄するパケット廃棄部と、廃棄されたパケットの再送を送信元のバッファに要求する再送要求部とを備えている。
【００２０】
本発明による他の中継器は、分散型のバスを備える集積回路において、複数のバスを接続する中継器であって、前記バス上を伝送される各トラヒックのトラヒックデータは、パケットに分割されており、前記中継器は、トラヒックデータを受け取る入力および前記トラヒックデータを送出する出力の組み合わせを切り替えるスイッチと、複数のトラヒックを共通して扱う隣接の中継器からのトラヒックごとの混雑の程度を示す混雑情報と、自中継器における前記トラヒックごとの混雑情報とを取得する混雑情報処理部と、前記隣接の中継器から取得した前記混雑情報および自中継器における前記混雑情報に基づいて、伝送経路上でのトラヒックごとの流れにくさを定量的に示す混雑度の情報を求める混雑情報比較部と、前記混雑度に基づいて、前記トラヒックごとにバスの伝送帯域を割り当てて送信スケジュールを調整する送信スケジュール調整部と、前記バスの伝送帯域の割り当て結果に基づき、前記スイッチを切り替えるスイッチ割当部と、異なるバスにデータを送出する複数の出力にそれぞれ接続された複数の出力バッファと、前記混雑度が予め定められた閾値よりも大きいトラヒックの連続するパケットに対して、同じ出力バッファを割当て、さらにトラヒックが送信される次の中継器に対して、ルーティングの設定の再利用を通知するルーティング再利用通知部とを備えている。
【００２１】
本発明による中継器は、分散型のバスを備える集積回路において、複数のバスを接続する中継器であって、トラヒックデータを受け取る入力および前記トラヒックデータを送出する出力の組み合わせを切り替えるスイッチと、複数のトラヒックを共通して扱う隣接の中継器からのトラヒックごとの混雑の程度を示す混雑情報と、自中継器における前記トラヒックごとの混雑情報とを取得する混雑情報処理部と、前記隣接の中継器から取得した前記混雑情報および自中継器における前記混雑情報に基づいて、伝送経路上でのトラヒックごとの流れにくさを定量的に示す混雑度の情報を求める混雑情報比較部と、前記混雑度に基づいて、前記トラヒックごとにバスの伝送帯域を割り当てて送信スケジュールを調整する送信スケジュール調整部と、前記バスの伝送帯域の割り当て結果に基づき、前記スイッチを切り替えるスイッチ割当部と備えている。
【００２２】
前記混雑情報は、自中継器において各トラヒックのトラヒックデータが自中継器を通過するのに要する遅延時間を示しており、前記混雑情報比較部は、前記隣接の中継器から取得したトラヒックごとの遅延時間および自中継器におけるトラヒックごとの遅延時間に基づいて、伝送経路上でのトラヒックごとの流れにくさを定量的に示す混雑度の情報を求めてもよい。
【００２３】
前記混雑度は、伝送経路上でのトラヒックごとの流れにくさを示す数値であって、トラヒックが流れやすいほど小さい数値が与えられ、流れにくいほど大きい数値が与えられ、前記送信スケジュール調整部は、前記混雑度が相対的に小さいトラヒックに対して前記バスの伝送帯域を優先的に割り当ててもよい。
【００２４】
前記送信スケジュール調整部は、前記混雑度が相対的に小さいトラヒックに対して前記バスの伝送帯域を相対的に広く確保し、前記バスの伝送帯域を先に利用可能にし、または、前記バスの伝送帯域の利用可能時間を相対的に長く確保することによって、前記バスの伝送帯域を優先的に割り当ててもよい。
【００２５】
各トラヒックのトラヒックデータは、パケットに分割されて前記バス上を伝送されており、前記中継器は、前記混雑度が予め定められた閾値よりも大きいトラヒックのパケットを入力バッファから廃棄するパケット廃棄部と、廃棄されたパケットの再送を送信元のバッファに要求する再送要求部とをさらに備えていてもよい。
【００２６】
各トラヒックのトラヒックデータは、パケットに分割されて前記バス上を伝送されており、前記中継器は、異なるバスにデータを送出する複数の出力にそれぞれ接続された複数の出力バッファと、前記混雑度が予め定められた閾値よりも大きいトラヒックの連続するパケットに対して、同じ出力バッファを割当て、さらにトラヒックが送信される次の中継器に対して、ルーティングの設定の再利用を通知するルーティング再利用通知部とをさらに備えていてもよい。
【００２７】
前記バスの動作クロックは変更可能であり、前記中継器は、前記混雑度が予め定められた閾値よりも大きいトラヒックが送信されるときは、前記出力が接続されたバスの動作クロックを向上させる動作クロック制御部をさらに備えていてもよい。
【００２８】
前記中継器は、自中継器において予め定められた閾値よりも大きな遅延が発生したときにおいて、自中継器における前記トラヒックデータが自中継器を通過するのに要する遅延時間にのみ基づいて前記混雑度を決定する協調制御停止部をさらに備えていてもよい。
【００２９】
本発明による他の中継器は、分散型のバスを備える集積回路において、複数のバスを接続する中継器であって、トラヒックデータを受け取る入力バッファおよび前記トラヒックデータを送出する出力バッファの組み合わせを切り替えるスイッチと、複数のトラヒックを共通して扱う隣接の中継器からのトラヒックごとの混雑の程度を示す混雑情報と、自中継器における前記トラヒックごとの混雑情報とを取得する混雑情報処理部と、前記隣接の中継器から取得した前記混雑情報および自中継器における前記混雑情報に基づいて、伝送経路上でのトラヒックごとの流れにくさを定量的に示す混雑度の情報を求める混雑情報比較部と、各トラヒックの混雑度を各トラヒックのトラヒックデータを格納する入力バッファの混雑度とし、前記入力バッファの混雑度に応じて、前記トラヒックデータが格納される出力バッファの重みの値を決定し、決定した重みの値に応じて前記トラヒックごとにバスの伝送帯域を割り当てて送信スケジュールを調整する送信スケジュール調整部と、前記バスの伝送帯域の割り当て結果に基づき、前記スイッチを切り替えるスイッチ割当部と備えている。
【００３０】
前記送信スケジュール調整部は、送信要求を受けた入力バッファに対し、各出力バッファに付与された重みの値に応じた確率でスイッチを接続してもよい。
【００３１】
前記送信スケジュール調整部は、前記伝送帯域を時間的に複数のタイムスロットに分割し、前記重みの値によって指定された数のタイムスロットをそれぞれの出力バッファに割り当ててもよい。
【００３２】
前記送信スケジュール調整部は、前記重みの値によって予め指定された割合で、確率的に前記出力バッファを選択してもよい。
【発明の効果】
【００３３】
本発明の中継器によれば、隣接の中継器から取得した混雑情報および自中継器における混雑情報に基づいて、伝送経路上でのトラヒックごとの流れにくさを定量的に示す混雑度の情報が求められる。そして、当該混雑度に基づいて、トラヒックごとにバスの伝送帯域を割り当てて送信スケジュールが調整される。これにより、各トラヒックの伝送経路上でのトラヒック間の干渉による伝送品質（遅延時間、スループットなど）の低下を抑えることができる。分散バス全体の利用効率を向上させることで、集積回路全体の伝送性能の向上（低遅延、高スループット）を実現できる。
【図面の簡単な説明】
【００３４】
【図１】（ａ）は、集中型のバス制御の例を示す図であり、（ｂ）は、分散型のバス制御の例を示す図である。
【図２】特許文献１に記載された、従来の送信スケジューリングを制御する中継器の構成、および、トラヒックＡ〜Ｃの送信経路を示す図である。
【図３】トラヒック間で競合が発生したときのトラヒックＡ〜Ｃを示す図である。
【図４】本発明による中継器の動作の概要を示す図である。
【図５】実施形態１における分散型のバスの構成図である。
【図６】パケット６０の伝送フォーマットの一例と、パケット６０を複数のフリットに分割した例を示す図である。
【図７】実施形態１における中継器７００の構成図である。
【図８】実施形態１における中継器７００の動作の流れを説明するフローチャートである。
【図９】伝送経路ごとに各トラヒックのパケットデータの流れにくさを混雑情報として定量的に測定可能な対象を説明する図である。
【図１０】中継器自身７００と隣接する中継器７１１の混雑状態を比較して、自中継器７００において、トラヒックＡとトラヒックＢの混雑度を算出する方法を説明する図である。
【図１１】送信スケジュール調整部７０９と、バッファ割当部７０５による出力バッファ７０３の割り当て方法を説明する図である。
【図１２】スイッチ割当部７０６による出力バッファが割り当てられたトラヒック間での送信スケジューリングの方法を説明する図である。
【図１３】重み付きラウンドロビンにより、スイッチを切り替える場合の、重みの割り当て方法を説明する図である。
【図１４】図５の多段接続網における、トラヒックＡ〜Ｃの各伝送経路を示す図である。
【図１５】トラヒックＡとトラヒックＢとが同時に流れている場合の、トラヒックＡの伝送経路上での各中継器の遅延時間の例を示す図である。
【図１６】トラヒックＡとトラヒックＢに加えて、トラヒックＣが同時に流れる場合の各中継器内でのトラヒックの遅延時間の例を示す図である。
【図１７】混雑度の定義として、自中継器と隣接中継器との混雑情報の比率の変わりに、差分を用いた例を示す図である。
【図１８】中継器Ｒ６に、トラヒックの流れの上流側にある中継器Ｒ０での遅延時間と、中継器Ｒ２での遅延時間とを基に、トラヒックＡおよびトラヒックＣに対して中継器Ｒ１０へのバスの伝送帯域の割り当てを説明する図である。
【図１９】中継器を格子状に並べた種々のトポロジーを示す図である。
【図２０】実施形態２における中継器８００の構成図の構成図である。
【図２１】実施形態２においてバスマスタから送信されるパケットとそのフリット群、および、ヘッダーフリットに記載される情報を示す図である。
【図２２】実施形態２における中継器８００の動作を説明する図である。
【図２３】実施形態３における中継器８１０の構成図である。
【図２４】実施形態３における中継器８１０の動作を説明する図である。
【図２５】実施形態４における中継器８２０の構成図である。
【図２６】実施形態４における中継器８２０の動作を説明する図である。
【図２７】実施形態５における中継器８３０の構成を示す図である。
【図２８】実施形態５における中継器８３０の動作を説明する図である。
【図２９】パケット交換方式と回線交換方式の違いを説明する図である。
【図３０】実施形態６による、回線交換方式の中継器８４０の構成を示す図である。
【発明を実施するための形態】
【００３５】
本発明の各実施形態の説明に先立って、まず本発明による中継器の動作原理を説明する。
【００３６】
図４は、本発明による中継器の動作の概要を示す。
【００３７】
図４では、図３と同様、バスマスタＡがトラヒックＡを、中継器Ｅおよび中継器Ｆを介してメモリＧへ送信し、バスマスタＢが中継器Ｅおよび中継器Ｆを介してメモリＤへトラヒックを送信し、バスマスタＣが中継器Ｆを介してメモリＤへトラヒックを送信することを想定している。
【００３８】
本発明による中継器Ｅは、トラヒックＡおよびトラヒックＢを、中継器Ｆに送信する。トラヒックＡおよびトラヒックＢの伝送帯域を決定するに際して、中継器Ｅは、隣接する中継器Ｆに要求を出し、中継器ＦにおけるトラヒックＡおよびトラヒックＢのデータパケットの流れにくさを定量的に示した値を中継器Ｆに通知してもらう。以下に説明する実施形態では、この値を「混雑情報」と呼ぶ。本明細書では、各トラヒックのデータパケットがそれぞれその中継器を通過するのに要する時間（以下、各トラヒックの「遅延時間」と呼ぶ）を混雑情報として利用する。
【００３９】
中継器Ｆから混雑情報を受け取った中継器Ｅは、各トラヒックについて、自中継器Ｅにおける遅延時間と、隣接する中継器Ｆにおける遅延時間とを比較する。そして中継器Ｅは、トラヒックごとに経路上でのデータパケットの流れにくさを定量的に示す情報を算出する。本明細書においては、この情報を「混雑度」とも呼ぶ。トラヒックごとの混雑度が求められると、中継器Ｅは、その値の大きさに基づいて中継器Ｆへのバスの伝送帯域が割り当てられるように、各トラヒックの送信スケジュールを調整する。
【００４０】
図４では、バスマスタＣからメモリＤへ、緊急時用の優先トラヒックＣが送信される状況を想定している。このとき、中継器Ｆにおいて中継器ＦからメモリＤへのバスの伝送帯域がトラヒックＣによって一時的に占有される。緊急時の優先トラヒックＣの発生により、トラヒックＢのデータパケットがメモリＤへと送信できないため、中継器Ｆ内でのトラヒックＢの遅延時間が長くなる。
【００４１】
中継器Ｆは、トラヒックＡおよびトラヒックＢの各遅延時間を自身の混雑情報として中継器Ｅに通知する。中継器Ｅは、中継器Ｆから通知された遅延時間および自中継器での遅延時間を比較する。その結果中継器Ｅは、中継器Ｆにおいて、トラヒックＡよりもトラヒックＢのデータパケットが流れにくくなったことを特定することができる。そこで中継器Ｅは、トラヒックＡに対しては、中継器Ｆに至るバスの伝送帯域を５０％から１００％へと優先的に割り当てるように送信スケジュールを調整する。一方トラヒックＢに対しては、バスの伝送帯域を５０％から０％へと削減するように送信スケジュールを調整する。
【００４２】
なお、本願明細書において、バスの伝送帯域を「優先的に割り当てる」とは、上述のように伝送帯域を相対的に広く確保することを意味することに限られない。その他、そのトラヒックがバスの伝送帯域を先に利用できるように解放してそのトラヒックを相対的に先に伝送させることを意味してもよいし、その伝送帯域の利用可能時間（許容時間）を相対的に長く確保することを意味してもよい。
【００４３】
本発明では、優先度が高いトラヒックを優先して伝送しつつ、優先度が低いトラヒック、または、優先度が設定されていないトラヒック同士のフロー制御をどのように行うかを問題としている。
【００４４】
以下、添付の図面を参照しながら、本発明による中継器の実施形態を説明する。
【００４５】
（実施形態１）
図５は、本実施形態における分散型のバスの構成図である。
【００４６】
本実施形態では、複数のバスマスタ（ＢＭ）とメモリとを、複数の中継器をバスで多段に接続した構成（多段接続網：ＭＩＮ（Ｍｕｌｔｉｓｔａｇｅ Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ Ｎｅｔｗｏｒｋ））を例に説明する。
【００４７】
図５では、８個のバスマスタ（ＢＭ０〜ＢＭ７）と、１２個の中継器（Ｒ０〜Ｒ１１）と、８個のメモリ（メモリ０〜７）とがバスで接続される回路の様子を示している。１２個の中継器は、４個ずつ３つのグループに分類されている。３つのグループは、８個のバスマスタに接続されるグループ（Ｒ０、Ｒ１、Ｒ２、Ｒ３）、８個のメモリに接続されるグループ（Ｒ８、Ｒ９、Ｒ１０、Ｒ１１）、及び、バスマスタ、又はメモリに接続する中継器を結ぶグループ（Ｒ４、Ｒ５、Ｒ６、Ｒ７）である。
【００４８】
多段接続網を構成する各中継器は、２入力２出力のクロスバースイッチを備えている。図５（ｂ）に示すように、スイッチを切り替えることによって入力と出力の組合せを変更することで、トラヒックの流れを２種類の伝送経路へ切り替えて送信できる。なお、出力先の伝送経路が異なっていれば、中継器は２つのトラヒックを各伝送経路に同時に出力することが可能である。
【００４９】
多段接続網では、各中継器でのスイッチの切り替えによって、全バスマスタと全メモリ間で、必ず１つ以上の伝送経路を構築することができる。
【００５０】
一般的に、クロスバースイッチによって、Ｎ個のバスマスタとＭ個のメモリの全てを接続するためには、スイッチがＮ×Ｍ個の必要となる。そしてバスマスタやメモリの数が増えるにつれてスイッチの数は急激に増加してしまう。これに対し、多段接続網（ＭＩＮ）では、入出力数の小さいクロスバースイッチを階層的に接続することで少ないスイッチでバスマスタとメモリ間の接続を切り替えることができるという特徴がある。
【００５１】
なお、本実施形態においては多段接続網を例に挙げて説明するが、これは一例である。集積回路の構成がその他のトポロジーであっても本発明を適用することが可能である。また、本実施形態では、バスマスタからメモリへのデータ転送は、パケット交換方式により複数の中継器を介して行われるとして説明する。
【００５２】
パケットは、図５（ａ）に示すように、フリットと呼ばれるサイズに分割されて、隣接する中継器へと送信される。
【００５３】
図６は、パケット６０の伝送フォーマットの一例と、パケット６０を複数のフリットに分割した例を示す。
【００５４】
パケット６０は、ヘッダフィールド６１、データフィールド６２および制御コードフィールド６３を備えている。
【００５５】
ヘッダフィールド６１には、たとえば、送信先のアドレス、送信元のアドレス、トラヒックの優先度を示す情報が記述される。優先度の記述方法は任意であるが、多値で表現されてもよい。多値で記述する場合、高い応答性が必要なユーザインターフェースの処理には高い数値を割り当てて優先度を高く設定することができる。一方、バックグラウンド処理で対応可能な映像のトランスコード処理には低い数値を割り当てて優先度を低く設定できる。これらの情報の後に、伝送すべきデータが記述される。
【００５６】
データフィールド６２には、たとえば映像データ、音声データが記述される。制御コードフィールド６３には、たとえば、予め定められたパケット６０の終了コードが記述される。
【００５７】
上述のヘッダフィールド６１のデータのうち、送信先のアドレスと、送信元のアドレスとに基づいて、パケット６０の中継処理と、受信側での受信処理とが行われる。
【００５８】
送信側のバスマスタは、パケット６０を、フリットと呼ばれる小さなパケット単位に分解して伝送する。１フリットは、バスを使って１サイクルで伝送可能なデータであり、そのサイズはバス幅の大きさによって決定される。パケット６０を分割したフリットのうち、最初に送信されるフリットは、ヘッダーフリットと呼ばれる。ヘッダーフリットには、パケットの先頭であることを示すフラグ情報、及びパケットの送信先のアドレス情報が付与されている。
【００５９】
なお、ヘッダーフリットに続く各フリットには、送信先を特定するアドレス情報は格納されていない。その理由は、ヘッダーフリットに続くフリットは、ヘッダーフリットと同じ宛先に送られるためである。ヘッダーフリットによって宛先が決まり、そのトラヒックのフリットを出力する出力バッファが決まると、後に続くフリットは、ヘッダーフリットと同じ出力バッファを利用してヘッダーフリットが示す宛先に伝送される。
【００６０】
受信側のメモリは、制御コードフィールド６３に記述された終了コードを検出すると、その終了コードに基づき、伝送されたフリットをパケットへ再構築する。
【００６１】
たとえば、１パケットのサイズは１２８バイト、１フリットのサイズは３２ビットまたは６４ビットである。ただし、１パケットのサイズおよび１フリットのサイズはアプリケーションによって異なり得るため、上述のサイズは一例に過ぎないことに留意されたい。フリットの長さは、送信先のアドレスと、送信元のアドレスなど、制御データを記述できる長さを基準としてもよい。
【００６２】
各中継器には、送られてきたフリットを蓄えるためのバッファが用意されている。フリットは一旦そのバッファに蓄えられた後、スイッチの切り替えによって目的の経路へと続く中継器や、宛先のメモリへ送信される。
【００６３】
図７は、本実施形態における中継器７００の構成図である。
【００６４】
図７の中継器７００は、隣接する中継器群７１０、７１１と、バスによって接続されており、隣接の中継器群７１０から送信されたフリットを、正しい宛先へとつながる隣接中継器７１１群へ中継するために、スイッチを切り替えて、フリットの送信スケジュールを制御する。
【００６５】
中継器７００は、入力バッファ７０１と、スイッチ７０２と、出力バッファ７０３と、ルーティング処理部７０４と、バッファ割当部７０５と、スイッチ割当部７０６と、混雑情報処理部７０７と、混雑情報比較部７０８と、送信スケジュール調整部７０９とを有している。
【００６６】
以下、各構成要素の機能を説明する。
【００６７】
入力バッファ７０１は、隣接する中継器（またはバスマスタ）から送られてきたフリットを蓄える一時バッファである。入力バッファ７０１を構成する一時バッファは、中継器７００の入力ごとに１つ設けられていてもよいし、または、宛先の異なるパケットを区別して個別に蓄えて、それぞれ個別に送信スケジュール制御ができるように、入力ごとに複数の一時バッファが設けられていてもよい。本実施形態では、図７に示すように、入力毎に２個ずつ入力バッファを備えているとする。
【００６８】
スイッチ７０２は、中継器７００の入力と出力の接続の組合せを切り替えるためのクロスバースイッチである。
【００６９】
出力バッファ７０３は、隣接する中継器７１１へフリットを送信する際に利用する一時バッファである。出力バッファ７０３は、隣接する中継器７１１の入力バッファと同じ数だけ設けられている。中継器７００の各出力バッファと、中継器７１１の各入力バッファとの間には、１対１の対応関係が決められている。中継器７００の出力バッファから送信されたフリットは、その出力バッファ７０３に対応する隣接の中継器７１１の入力バッファに蓄えられる。したがって、中継器７００は、フリットの送信に利用する出力バッファを選択することで、隣接する中継器７１１の入力バッファを指定できる。
【００７０】
ルーティング処理部７０４は、入力バッファ７０１に新しいヘッダーフリットが送られてくると、それを受け取り、ヘッダーフリットに記述された宛先情報を基に、次に受け渡す中継器を特定する。
【００７１】
バッファ割当部７０５は、フリットが適切な経路へと中継されるように、フリットが蓄えられている入力バッファに対して、フリットを送信するための専用の出力バッファを割り当てる。
【００７２】
バッファ割当部７０５では、入力バッファにヘッダーフリットが到着すると、ルーティング処理部７０４で特定された送信経路に接続されている出力バッファ７０３の中から、その時点で利用されていない出力バッファを選択し、フリットを送信するための専用のバッファとして出力バッファ７０３を１つ割り当てる。
【００７３】
バッファ割当部７０５により、入力バッファと出力バッファとの組合せは、１つのパケット全体が中継器を通過するまで維持される。
【００７４】
スイッチ割当部７０６は、バッファ割当部７０５によって決定された入力バッファ７０１と出力バッファ７０３の組合せの中から、実際に隣接の中機器７１１に対してフリットを送信する組合せを決定し、入力バッファ７０１と出力バッファ７０３間のスイッチ７０２を切り替える。
【００７５】
混雑情報処理部７０７は、複数のトラヒックを共通して扱う近隣の中継器群７１０、７１１に対して要求を出し、トラヒックごとの混雑の程度を示す混雑情報を取得する。また混雑情報処理部７０７は、近隣の中継器群７１０、７１１から混雑情報の要求を受けたときは、その中継器に対して、各伝送経路のトラヒックごとにデータパケットの流れにくさを定量的に示した混雑情報を測定することによって取得し、取得した混雑情報をその中継器に出力する。
【００７６】
なお、混雑情報としては、例えばデータパケットが中継器を通過するまでにかかる遅延時間を測定し、その値を用いる。
【００７７】
伝送経路上でデータパケットが流れにくくなるほど、中継器７００内からバスへフリットが送信されなくなるため、データパケットの遅延時間が長くなるため、各伝送経路でのデータパケットの流れにくさを遅延時間から定量的に特定することができる。
【００７８】
混雑情報比較部７０８は、近隣の中継器７１０、７１１から通知されたトラヒックごとの混雑情報と、ヘッダに記述されている送信先によって定まる、トラヒックごとの中継器７００自身の混雑情報とを比較し、各トラヒックの経路上での流れにくさを定量的に示す混雑度を算出する。
【００７９】
送信スケジュール調整部７０９は、混雑情報比較部７０８で求められた混雑度に基づき、各トラヒックに対して、バスの伝送帯域の割り当てを調整する。
【００８０】
中継器７００における伝送帯域の割り当ての調整には、バッファ割当部７０５で出力バッファ７０３において一時バッファをどのように割り当てるかのスケジューリングの調整と、スイッチ割当部７０６がスイッチ７０２をどのように切り替えるかのスケジューリングの調整とが含まれている。
【００８１】
次に、各中継器７００の動作について説明する。
【００８２】
図８は、本実施形態における中継器７００の動作の流れを説明するフローチャートである。
【００８３】
中継器７００は、近隣の中継器７１０からフリットが送られてくると、入力バッファ７０１のうち、所定のバッファにそのフリットを蓄積する（ステップ８０１）。フリットを蓄積するバッファの選択方法は種々考えられる。たとえば先に説明したように、前段の中継器７１０の出力バッファから送信されたフリットを、その出力バッファ７０３に対応する隣接の中継器７１１の入力バッファに蓄えればよい。前段の中継器が存在せず、バスマスタからフリットが直接送信される場合には、バスマスタ側でフリットを蓄積する入力バッファを指定し、中継器７００はバスマスタ側で指定された入力バッファにフリットを蓄積すればよい。これ以外にも、フリットがヘッダーフリットの場合には、空のバッファへ蓄積し、ヘッダーフリットでない場合には、そのフリットに対応するヘッダーフリットが蓄積されたバッファへ蓄積してもよい。同じパケットを構成するフリットごとに区別して、異なる入力バッファを選択すればよい。
【００８４】
入力バッファ７０１は蓄積されたフリットがヘッダーフリットであるかどうかを判定する（ステップ８０２）。
【００８５】
蓄積されたフリットがヘッダーフリットであった場合には、ステップ８０３に進んでデータの次の送信先を特定するための処理に移り、ヘッダーフリットでない場合には、ステップ８０７に進み、そのフリットに対応するヘッダーフリットと同じ経路を送信先とする。
【００８６】
ルーティング処理部７０４は、入力バッファに送られてきたフリットがヘッダーフリットの場合、ヘッダーフリットに付与されている宛先のアドレス情報を基に、次に送る中継器を決定する（ステップ８０３）。
【００８７】
図５に示した多段接続網の場合では、各メモリに対し３桁の２進数でアドレスが割り当てられ、各パケットのヘッダーフリットには、宛先となるメモリのアドレスが、３桁の２進数が付与されている。
【００８８】
各中継器のルーティング制御部７０４は、ヘッダーフリットに付与された３桁のアドレスのうち、中継器の段数と同じ桁の数字を読み取る。そしてその値が０ならば図５における右上の中継器へフリットを送り、値が１ならば図５における右下の中継器へフリットを送るように経路を決定する。
【００８９】
例えば、バスマスタＢＭ２から、メモリ５（アドレス：１０１）へデータを送る場合には、アドレスに記載された３桁の数字に従って、まず中継器Ｒ１では右下の中継器Ｒ７へフリットが送信され、次に中継器Ｒ７では右上の中継器Ｒ１０にフリットが送信され、最後に中継器Ｒ１０で右下のメモリ５へフリットが送信される。これにより、バスマスタＢＭ５からメモリ２へとフリットが伝送される。
【００９０】
なお、ルーティング処理部７０４でのルーティング（経路）制御の方法としては、分散バスのトポロジーに応じて、適切に目的地までフリットが送られる方法であれば、上記以外の方法であってもよい。
【００９１】
フリットを送信する隣接の中継器が決まると、中継器７００は、混雑情報処理部７０７を介して、隣接する中継器７１１と中継器７１０から混雑情報を取得・参照する（ステップ８０４）。
【００９２】
図９は、伝送経路ごとに各トラヒックのパケットデータの流れにくさを定量的に測定可能な対象を説明する図である。測定された結果が混雑情報として取り扱われる。混雑情報は、中継器７００内での（１）データパケットが中継器７００を通過するまでにかかる遅延時間や、（２）入力バッファ内に残っているフリット数、（３）バスの空帯域等である。
【００９３】
集積回路では、実装面積やコスト等の課題から、回路上のバッファのサイズをできるだけ小さくすることが望まれる場合が多い。このため、入力バッファのサイズが小さい場合には、入力バッファ内のフリット数（２）を混雑の程度を測る指標として採用しては精度が低くなってしまう。また、バスの空帯域（３）を測定する場合には、所定の時間、バスの状態を記録ためのメモリ（バッファ）が必要となる。これに対し中継器内のフリットの遅延時間（１）を混雑の程度を測る指標とする場合には、少ないバッファサイズでも混雑の程度を精度よく測ることができる。
【００９４】
また、本実施形態では、中継器間を接続するバス（３）として電気信号を伝えるバスを想定しているが、これ以外にも、光信号によりデータを伝える有線バスや、磁気や電磁波を利用して信号を伝える無線バスであっても良い。さらに、光信号や電磁波による通信では、１つのバス上で異なる波長や周波数を同時に用いることができる。このためバス上で利用されている波長や周波数の利用数、又は空き数を基に混雑度と定義しても良い。
【００９５】
以下の説明では、中継器７００内のバッファサイズが少ない場合を想定し、（１）データパケットが中継器７００を通過するまでにかかる遅延時間を混雑情報として説明する。なお、バッファを確保できるのであれば、上述の（２）または（３）を採用してもよい。この混雑情報は、混雑情報処理部７０７によって取得される。
【００９６】
次に、混雑情報比較部７０８により、中継器７００と、隣接する中継器７１０（中継器７１１）との間での混雑情報を比較し、経路上でのトラヒックごとの流れにくさを示す混雑度を求める（ステップ８０５）。
【００９７】
図１０は、中継器自身７００と隣接する中継器７１１の混雑状態を比較して、自中継器７００において、トラヒックＡとトラヒックＢの混雑度の算出方法を説明する図である。
【００９８】
本実施形態では、混雑度の値は、混雑情報比較部７０６により、トラヒックごとに下流側にある中継器７１１から通知されたデータパケットの遅延時間と、自中継器７００でのデータパケットの遅延時間の比率を混雑度として定義する。
【００９９】
例えば、図１０において、トラヒックＡは、データパケットが中継器７００を通過するまでに１０サイクル、下流側の中継器７１１を通過するのに５サイクルの遅延が発生しているとする。このとき、トラヒックＡの混雑度は以下のように算出できる。
トラヒックＡの混雑度： ５／１０ ＝ ０．５
【０１００】
一方、トラヒックＢでは、データパケットが中継器７００を通過するために１２サイクル、中継器７１１を通過するために１５サイクルかかるとする。このとき、トラヒックＡの混雑度は以下のように算出できる。
トラヒックＢの混雑度： １５／１２ ＝ １．２５
ここで、混雑度の値が大きいほど、データパケットが流れにくいものとすると、中継器７００の近隣では、トラヒックＡの方がトラヒックＢよりもデータパケットの流れやすさを定量的に特定できる。
【０１０１】
図１０では、混雑度を中継器１の遅延時間と、中継器２の遅延時間の比率として定義したが、これ以外にも、例えば中継器１での遅延時間と中継器２での遅延時間の差分や、遅延時間の総和など、自中継器７００と隣接する中継器７１１の混雑情報の比較した値を混雑度として定義し、その値を用いてもよい。
【０１０２】
また、中継器間の遅延時間の値と混雑度の値との対応関係を予めテーブル情報として定義しておき、通知された遅延時間に対応する混雑度をテーブル情報を参照することで求める方法であってもよい。
【０１０３】
次に、図８のステップ８０６において、送信スケジュール調整部７０９は、トラヒックの混雑度に基づき、混雑度が求まっている入力バッファに対してフリットを送信するための優先順位を決定する。「混雑度が求まっている入力バッファ」とは、各トラヒックの混雑度と同じである。すなわち、混雑度ｘを有するトラヒックｔが存在するとき、そのトラヒックｔのフリットが入力される入力バッファの混雑度は、ｘとなる。そしてバッファ割当部７０５は、入力バッファの優先順位に基づいて出力バッファを割り当てる。
【０１０４】
図１１は、送信スケジュール調整部７０９と、バッファ割当部７０５とによる出力バッファ７０３の割り当て方法を説明する図である。
【０１０５】
中継器内で入力バッファには、トラヒックごとに区別されてフリットが蓄えられ、出力バッファを介して次の中継器へと送信される。
【０１０６】
図１１では、入力０からのトラヒックに対して入力バッファ０と入力バッファ１が用意されており、入力１からのトラヒックに対しては、入力バッファ２と入力バッファ３が用意されている。そして、混雑情報比較部７０８により入力バッファ０、入力バッファ１、入力バッファ２に対して、混雑度がそれぞれ１．０、０．２５、０．５と求められているとする。
【０１０７】
入力バッファがどの出力バッファに対して割り当てを要求するかは、先に説明したように、入力バッファに蓄積されている各トラヒックのフリットがどの送信経路でメモリに送信されるかによって特定される。異なる入力バッファが同じ出力に接続された２つの出力バッファに対して割り当てを要求することがあるため、出力バッファの割り当てを決定する必要がある。
【０１０８】
送信スケジュール調整部７０９は、混雑情報比較部７０８によって求められた混雑度の情報を基に、各入力バッファに対して、出力バッファの割り当ての優先順位を付与する。図１１の例では、各入力バッファの混雑度を、そのまま出力バッファの割り当ての優先順序として用いる場合を想定して説明する。なお、出力バッファの割り当ての優先順序は、その出力バッファから送出されるフリットが格納された入力バッファの混雑度の値が小さいものほど優先されるものとする。
【０１０９】
各入力バッファの優先度が決まると、各入力バッファは、ルーティング処理部７０４によって特定された次の中継器へ接続する出力側の出力バッファのうち、利用されていない出力バッファに対して、出力バッファの割り当てを要求する。
【０１１０】
バッファ割当部７０５は、各出力バッファに対して割り当て要求をしている入力バッファの中から、最も混雑度の小さいものに対して割り当ての決定を通知する。
【０１１１】
図１１の例では、入力バッファ０、入力バッファ１、入力バッファ２が、出力０側の出力バッファに対して、それぞれ割り当てを要求している。そして、要求のあった出力バッファごとに混雑度の最も小さかった入力バッファ０と、入力バッファ２に対して割り当ての決定がなされる。
【０１１２】
出力バッファの割り当ては、ヘッダーフリットを送信する際に決定され、そのヘッダーフリットに対応するパケットを構成する全てのフリットが送信されるまで、出力バッファが割り当てられている状態が継続される。
【０１１３】
次にスイッチ割当部７０６は、入力バッファの混雑度の小さいものから順番に入力バッファと出力バッファ間のスイッチを接続し、入力バッファ内のフリットを、隣接する中継器へと送信する（ステップ８０７）。
【０１１４】
図１２は、スイッチ割当部７０６によって出力バッファが割り当てられたトラヒック間で、送信スケジューリングを調整する方法を説明する図である。
【０１１５】
本実施形態における中継器での送信スケジューリングは、入力バッファと出力バッファ間でのスイッチの接続の切り替えによって行われる。
【０１１６】
図１２では、全ての入力バッファに対して、出力バッファの割り当てが完了している。入力バッファ０には出力バッファ０が割り当てられ、入力バッファ１には出力バッファ３が割り当てられている。また、入力バッファ２には出力バッファ１が割り当てられ、入力バッファ３には出力バッファ２が割り当てられている。
【０１１７】
スイッチ割当部７０６は、それぞれの出力に接続する出力バッファに接続する入力バッファの中で混雑度が小さい入力バッファに対してスイッチを接続し、隣接する中継器へフリットの送信を許可する。入力および出力の組が異なっていれば、スイッチ割当部７０６は、当該異なる組についてはスイッチを同時並列的に接続できる。
【０１１８】
図１２に示す、出力０に接続する出力バッファ０と出力バッファ１について検討すると、出力バッファ１を割り当てられた入力バッファ２の混雑度０．５の方が、出力バッファ０を割り当てられた入力バッファ０の混雑度１．０よりも小さい。そのため、入力バッファ２と出力バッファ１との間でスイッチの接続が行われる。スイッチが接続された入力バッファの中身が空になり、そのフリットの送信が終了すると、入力バッファ０と出力バッファ０との間でスイッチの接続が行われ、フリットが送信される。
【０１１９】
同様に、出力１に接続する出力バッファ２と出力バッファ３について検討すると、出力バッファ３を割り当てられた入力バッファ１の混雑度０．２５の方が、出力バッファ２を割り当てられた入力バッファ３の混雑度２．０より小さい。そのため、入力バッファ３と出力バッファ２との間でスイッチの接続が行われる。スイッチが接続された入力バッファの中身が空になり、そのフリットの送信が終了すると、入力バッファ１と出力バッファ３との間でスイッチの接続が行われ、フリットが送信される。その結果、それぞれフリットが隣接する異なる中継器に送信される。
【０１２０】
このように、各トラヒックの混雑度の値に基づいて、スイッチの割り当ての優先順序を調整することにより、各トラヒックに対して出力側のバスに対して伝送帯域の割り当て量を調整することができる。
【０１２１】
なお、スイッチの切り替え方法としては、混雑度の小さい入力バッファからスイッチの接続を切り替えて、順番に入力バッファの中身を空にする方法以外にも、例えば、重み付きラウンドロビン（Weighted Round Robin：WRR）を用いる方法がある。
【０１２２】
図１３は、重み付きラウンドロビンにより、スイッチを切り替える場合の、重みの割り当て方法を説明する図である。
【０１２３】
重み付きラウンドロビンでは、フリットの送信要求のあった全ての入力バッファに対して、１フリット送信するごとに、各出力バッファに付与された重みの値に応じた（比例した）確率でスイッチを接続する方法である。以下に説明する重みの算出処理や、割り当て処理は、送信スケジュール調整部７０９によって実行される。
【０１２４】
図１３の例では、各出力バッファの重みは、その出力バッファが割り当てられた入力バッファの混雑度に基づき、その逆数を重みとして用いている。具体的には、出力バッファ０に付与された重みは、入力バッファ０の混雑度１．０の逆数で１．０となる。出力バッファ１に付与された重みは、入力バッファ２の混雑度０．５の逆数で２．０となる。出力バッファ２に付与された重みは、入力バッファ３の混雑度２．０の逆数で０．５となる。出力バッファ３に付与された重みは、入力バッファ１の混雑度０．２５の逆数で４となる。
【０１２５】
重み付きラウンドロビンを使ってスイッチを切り替えた場合、出力０は、出力バッファ０と出力バッファ１のそれぞれの重みから、１対２の割合でそれぞれの出力バッファを経由してフリットを送信する。また出力１は、出力バッファ２と出力バッファ３のそれぞれの重みから、約１対８の割合でそれぞれの出力バッファを経由してフリットを送信する。
【０１２６】
このように、重み付きラウンドロビンによる送信スケジューリングでは、重みの値によって、出力バッファ間で、出力側のバスに対して伝送帯域の割り当ての割合を調整することができる。
【０１２７】
なお、図８のステップ８０６および８０９では、混雑度の値を、そのまま出力バッファの割り当てに用い、及びスイッチの割り当てに用いる場合を例に説明した。しかしながら、混雑度の値を反映したものであれば、別の定義を用いても良い。また出力バッファとスイッチの割り当てを優先させたい入力バッファに対して、優先度の値を小さくする例を説明したが、逆に大きい値を与え、値の大きいものから出力バッファとスイッチを与えるようにしてもよい。
【０１２８】
また、重み付きラウンドロビンによる各出力バッファへの伝送帯域の割り当ての具体的な調整方法としては、伝送帯域を時間的に複数のタイムスロットに分割し、重みの値によって指定された数のタイムスロットをそれぞれの出力バッファに割り当てる方法や、重みの値によって予め指定された割合で、確率的に出力バス（出力バッファ）を選択する方法などがある。
【０１２９】
ヘッダーフリット以外のフリットを送信する場合には、ステップ８０３のルーティングおよびステップ８０６の出力バッファの割り当ては行われない。混雑情報処理部７０７は、隣接する中継器の混雑情報の取得と参照（ステップ８０７）を行い、混雑情報比較部７０８は近隣の中継器と互いの混雑状況の比較（ステップ８０８）のみを行う。隣接する中継器の混雑情報の取得・参照方法（ステップ８０７）と近隣の中継器と互いの混雑情報の比較方法（ステップ８０８）については、それぞれ（ステップ８０４）と（ステップ８０５）の処理と同じであるため、説明を省略する。
【０１３０】
中継器７００は、スイッチ割当部７０６によってスイッチ７０２の割り当てが決定すると入力バッファ内のフリットを、割り当てられた出力バッファを介して隣接する中継器７１１へと送信する（ステップ８１０）。
【０１３１】
混雑情報処理部７０７は、フリット送信後の中継器の混雑情報を近隣の中継器７１０、７１１に通知する（ステップ８１１）。
【０１３２】
次に図１４、図１５、図１６を用いて、本実施形態における中継器の動作を詳細に説明する。
【０１３３】
図１４は、図５の多段接続網における、トラヒックＡ〜Ｃの各伝送経路を示す。トラヒックＡはバスマスタＢＭ０からメモリ４へ伝送される。トラヒックＢは、バスマスタＢＭ１からメモリ６へ伝送される。トラヒックＣは、バスマスタＢＭ５からメモリ５へ伝送される。
【０１３４】
トラヒックＡとトラヒックＢが同時に流れる場合には、中継器Ｒ０から中継器Ｒ６へのバス上で干渉が発生する。また、トラヒックＡとトラヒックＣが同時に流れる場合には、中継器Ｒ６から中継器Ｒ１０へのバス上で干渉が発生する。
【０１３５】
図１５は、トラヒックＡとトラヒックＢとが同時に流れている場合の、トラヒックＡの伝送経路上での各中継器の遅延時間の例を示す。
【０１３６】
図１５において、中継器Ｒ０内でのトラヒックＡとトラヒックＢの遅延時間は、互いの干渉により、それぞれ１０サイクルとする。また、中継器Ｒ６内でのトラヒックＡとトラヒックＢの遅延時間はそれぞれ別の経路に流れるため、それぞれ５サイクルとする。すると、中継器Ｒ０でのトラヒックＡの混雑度は０．５、トラヒックＢの混雑度は０．５となり、伝送経路上の流れにくさは、どちらのトラヒックも同じになる。そのため、中継器Ｒ０は、中継器Ｒ６へのバスの伝送帯域を、トラヒックＡとトラヒックＢに対して均等に５０％ずつ割り当てるように送信のスケジューリングを調整する。スケジューリングとは出力バッファの割り当てと、スイッチの割り当てを意味する。以下も同様である。
【０１３７】
次に、図１６は、トラヒックＡとトラヒックＢに加えて、トラヒックＣが同時に流れる場合の各中継器内でのトラヒックの遅延時間の例を示す。
【０１３８】
図１６において、中継器Ｒ０内でのトラヒックＡとトラヒックＢの遅延時間は互いの干渉によりそれぞれ１０サイクルとする。また、中継器Ｒ６内では、トラヒックＡとトラヒックＣとが互いに干渉することにより、遅延時間がそれぞれ１０サイクルとする。一方、別の経路へ流れるトラヒックＢは、他のトラヒックと干渉しないため、遅延時間が５サイクルとする。すると、中継器Ｒ０でのトラヒックＡの混雑度は１、トラヒックＢの混雑度は０．５となり、トラヒックＡの方がトラヒックＢよりも伝送経路上において流れにくいことが特定される。
【０１３９】
中継器Ｒ０は、トラヒックＡとトラヒックＢの混雑度の大きさに合わせて、中継器Ｒ６へのバスの伝送帯域を割り当てる。例えば、中継器Ｒ１が重み付きラウンドロビンを用いて各トラヒックに混雑度の値に反比例させた伝送帯域を割り当てた場合には、中継器Ｒ０は、トラヒックＡには伝送帯域の３３％、トラヒックＢには伝送帯域の６６％を割り当てるように送信のスケジューリングを調整する。
【０１４０】
また、中継器Ｒ０によってトラヒックＡの伝送帯域の割り当てが少なくなると、中継器Ｒ０では、トラヒックＡとトラヒックＢの干渉が弱められるため、トラヒックＢの遅延時間が削減される。また、Ｒ６ではトラヒックＡとトラヒックＣの干渉が弱められるため、トラヒックＣの遅延時間が削減される。
【０１４１】
このように、トラヒック数や流量の変化に対し、伝送経路上において複数のトラヒックと干渉しているトラヒックＣの伝送帯域を減らすことで、互いに干渉しないトラヒックＢとトラヒックＣの伝送帯域を増やし、優先的にトラヒックＢとトラヒックＣを流すことで、回路全体の利用効率の低下を防ぎ、遅延の増加やスループットの低下を抑止することができる。
【０１４２】
図１７は、混雑度の定義として、自中継器と隣接中継器との混雑情報の比率の変わりに、差分を用いた例を示す。
【０１４３】
図１７では、トラヒックごとに自中継器での遅延時間から、送信先の隣接中継での遅延時間を引いた値を混雑度として定義している。なお、図１７の式では、混雑度を重み付きラウンドロビンで扱えるようにするために、定数αを加えている。これにより、混雑度を正の数として扱うことが可能となる。定数αの具体的な値としては、混雑度が負の値とならないように、中継内で許容できる遅延時間の最大値の値を設定する方法が考えられる。
【０１４４】
また、本実施形態では、トラヒックが流れる下流側の中継器の混雑情報を基に、送信スケジューリング（出力バッファの割り当て、スイッチの割り当て）が調整される例を説明した。しかしながら、トラヒックが流れてきた上流側の中継器の混雑情報を基に送信スケジューリングが調整されてもよい。
【０１４５】
図１８は、トラヒックの流れの上流側にある中継器Ｒ０での遅延時間と、中継器Ｒ２での遅延時間とを基に、中継器Ｒ６がトラヒックＡとトラヒックＣに中継器Ｒ１０へのバスの伝送帯域をどのように割り当てるかを説明する図である。
【０１４６】
図１８では、中継器Ｒ０内でのトラヒックＡとトラヒックＢの遅延時間は、互いの干渉によりそれぞれ１０サイクルとする。また、中継器Ｒ６内では、トラヒックＡとトラヒックＣが互いに干渉し、遅延時間はそれぞれ１０サイクルとする、中継器Ｒ２では、トラヒックＣのみが流れているため遅延時間が５サイクルであるとする。
【０１４７】
中継器Ｒ６は、中継器Ｒ０より、トラヒックＡとトラヒックＢの遅延時間を取得し、中継器Ｒ２より、トラヒックＣの遅延時間を取得し、自中継器内でのそれぞれのトラヒックの遅延時間との比較から混雑度を算出する。ここでトラヒックが流れる下流側の中継器から通知された遅延時間を使って混雑度を算出した場合と同様に、混雑度の定義として、トラヒックが流れる上流側の中継器での遅延時間に対する、その下流にある自中継器Ｒ６での遅延時間の比率の値を用いる。
【０１４８】
トラヒックＡの混雑度は、１（＝１０÷１０）、トラヒックＢの混雑度は０．５（＝５÷１０）と求められる。
【０１４９】
混雑度が求まると、中継器Ｒ６は、例えば、中継器Ｒ１が重み付きラウンドロビンを用いて、混雑度の値に反比例させて各トラヒックに伝送帯域を割り当てた場合には、トラヒックＡには伝送帯域の３３％、トラヒックＣには伝送帯域の６６％が割り当てるように送信のスケジューリングの調整が行われる。
【０１５０】
また、中継器Ｒ６において、トラヒックが流れる上流側の中継器からの混雑情報だけでなく、下流側の中継器からの混雑情報も用いて伝送経路上での混雑度を求め、これを送信スケジューリングの調整に用いてもよい。
【０１５１】
例えば、トラヒックごとに上流側の混雑度と下流側の混雑度を求め、その平均値を混雑度と定義してもよい。
【０１５２】
以上のように、図７を用いて説明した構成と、図８で説明した処理とにより、伝送経路上の各中継器が、隣接する中継器間で混雑情報を交換し、その比較から伝送経路上でのトラヒックの流れにくさを示す混雑度を基に、各トラヒックの送信スケジューリングを調整する。これにより、トラヒック間の干渉による遅延の増加を抑制が可能となる。
【０１５３】
なお、本実施形態では、集積回路のトポロジーが多段接続網の場合を例に説明したが、図１９に示すように中継器を格子状に並べてメッシュ型や、トーラス型、バスを階層的に接続したトポロジーなど中継器やスイッチを介して複数のバスを経由するトポロジーでも同様に適用できる。
【０１５４】
（実施形態２）
実施形態１では、隣接する中継器間で混雑情報を交換し、トラヒックごとに伝送経路上でのデータパケットの流れにくさを示す混雑度に基づいて、各トラヒックの送信スケジューリングを調整した。
【０１５５】
これに対し、本実施形態の中継器は、求められた混雑度を比較し、データパケットの流れにくい方のパケットをいったん廃棄し、再度、廃棄したパケットの送信元となるバスマスタにパケットの再送を要求する。これにより、混雑度の小さいトラヒックの遅延時間の増加を抑制することができる。なお、バスマスタにパケットの再送を直接要求するのではなく、宛先をそのバスマスタとする再送要求を含むフリットを、そのパケットを送信してきた隣接する中継器のバッファに送信することに留意されたい。隣接する中継器は、その再送要求をさらに上流の中継器または当該バスマスタに送信することになる。
【０１５６】
中継器は、再送要求を、１サイクルで送信可能なデータ量である１フリットで送信することができる。しかしながら、フリット数は２以上であってもよい。または、再送要求をパケットで送信してもよい。再送要求は通常のトラヒックが流れる伝送経路上を送信されてもよいが、再送要求専用の伝送経路を設けてもよい。
【０１５７】
インターネットや無線ＬＡＮ等でのネットワーク制御では、一般的に中継器での混雑（輻輳）を抑制する方法としてパケットを廃棄が用いられる。しかしながら、集積回路では信頼性への要求が高いため、回路内を流れるトラヒックのデータロスが発生すると、混雑時に廃棄したパケットを再度、送信元から再送する必要がある。
【０１５８】
図２０は、本実施形態における中継器８００の構成図の構成図である。図２０の構成要素のうち図７と同じ構成については、同じ参照符号を付与し説明を省略する。
【０１５９】
パケット廃棄部１４０１は、混雑情報比較部７０８によって求められたトラヒックごとの混雑度のうち、所定の閾値を越えるトラヒックを検出した場合に、該当するトラヒックのパケットを入力バッファ７０１から削除する。
【０１６０】
再送要求部１４０２は、前記パケット廃棄部により、削除されたパケットの再送要求を、送信元のバスマスタに通知する。
【０１６１】
図２１は、本実施形態においてバスマスタから送信されるパケットとそのフリット群、および、ヘッダーフリットに記載される情報を示す。ヘッダーフリットには、ヘッダフラグや宛先アドレスの他、送信元のアドレス、及び、パケットのＩＤが記載されている。パケット廃棄部１４０１がパケットを廃棄する場合に備えて、再送要求部１４０２はそのパケットのヘッダーフリットの情報（少なくとも送信元のアドレス、及び、パケットのＩＤ）をヘッダーフリットが到着するたびに記憶しておく。そして、保持していたその情報に基づいて、送信元のバスマスタに、特定のＩＤを有するパケットの再送を要求する。
【０１６２】
パケットを廃棄されたバスマスタは、混雑を避けるために所定の時間待機し、再びパケットの送信を開始する。
【０１６３】
図２２は、本実施形態における中継器８００の動作を説明する図である。
【０１６４】
図８と同様の動作については、同じ参照符号を付与し説明を省略する。
【０１６５】
中継器８００は、隣接する中継器７１０と互いの混雑情報を交換し、トラヒックごとに経路上でのトラヒックの流れにくさを混雑度として算出し、その値が所定の閾値以内に収まっているかどうかを判定する（ステップ２４０１）。混雑度の値が、閾値以下であれば、入力バッファ内のフリットを送信するためにスイッチの割り当て処理を行うためにステップ８０９に移る。
【０１６６】
ステップ２４０１において、混雑度が所定の閾値を超えたと判定された場合には、中継器８００のパケット廃棄部１４０１は、該当する入力バッファ内のフリットを全て廃棄し、また、その入力バッファに割り当てられた出力バッファを開放する（ステップ２４０２）。
【０１６７】
混雑度が所定の閾値以上を越えた入力バッファ内のフリットが廃棄されると、中継器内の再送要求部１４０２は、廃棄したパケットの送信元に、廃棄したパケットの再送を要求する（ステップ２４０３）。
【０１６８】
再送要求部１４０２から送信元に再送を通知する方法として、トラヒックが流れてきた伝送経路を、逆方向に、再送要求を伝えるパケットを転送する方法や、中継器８００と送信元との間で再送を通知するための、専用の制御信号線を用いる方法が挙げられる。
【０１６９】
以上の構成と処理を加えることにより、本実施形態における中継器８００は、混雑度が所定の閾値よりも高いトラヒックのパケットを廃棄するので、パケットデータの流れにくいトラヒックによる、回路全体での伝送性能の低下を抑制できる。
【０１７０】
（実施形態３）
本実施形態では、宛先が共通するパケットを連続して次の中継器に送信する際に、同じ出力バッファを利用して次の中継器に送信し、さらに、連続して送ったパケットが同じ宛先に向かうパケットであることを次の中継器に通知することで、後続のパケットで行われるルーティング処理（ステップ８０３）と出力バッファの割り当て（ステップ８０６）省略し、中継器内での遅延時間を短縮する。
【０１７１】
図２３は、本実施形態における中継器８１０の構成図である。図２３の構成要素のうち図７と同じ構成については、同じ参照符号を付与し説明を省略する。
【０１７２】
ルーティング再利用通知部１５０１は、宛先が共通するパケットが、同じ出力バッファを介して、次の中継器７１１に伝送される際に、連続して送ったパケットが同じ宛先に送られるパケットであることを次の中継器７１１に通知する処理部である。なお、同じ出力バッファを介して次の中継器７１１に送られたパケットは、次の中継器７１１において同じ入力バッファに送られるものとする。
【０１７３】
図２４は、本実施形態における中継器８１０の動作を説明する図である。
【０１７４】
図８と同様の動作については、同じ参照符号を付与して説明を省略する。
【０１７５】
連続して送ったパケットが同じ宛先に送られるパケットである場合には、中継器８１０のルーティング再利用通知部１５０１は、ルーティング処理の再利用を行わせるための通知を次の中継器７１１に送信する。以下、この処理を行う中継器８１０の処理を説明する。
【０１７６】
隣接する中継器７１０からフリットが送られてくると、中継器８１０は、自らの入力バッファ７０１のうち、所定の入力バッファにフリットを蓄積する（ステップ８０１）。
【０１７７】
ステップ８０２において、受信したフリットがヘッダーフリットである場合には、ルーティング処理部７０１は、中継器７１０からルーティングの再利用通知を受信しているか否かを確認する（ステップ２６０１）。
【０１７８】
ルーティングの再利用通知がない場合には、次の送信先を特定する必要がある。そこで、ルーティング処理部７０４はルーティング処理を行う（ステップ８０３）。
【０１７９】
一方、ルーティングの再利用通知がある場合には、ルーティング処理部７０４はルーティング処理を省略し、1つ前のパケットの送信時に用いたルーティングの処理結果を利用できるか否か、言い換えると、出力バッファの再利用が可能か否かを判断する（ステップ２６０２）。
【０１８０】
バッファ割当部７０５は、再利用通知を受信した入力バッファを継続して利用でき、かつ、1つ前のパケットの送信時に利用した出力バッファが他の入力バッファからの要求によって割り当てられていない場合には、出力バッファの再利用が可能であると判断する。このとき、バッファ割当部７０５は、出力バッファの割当の決定（ステップ８０６）を省略し、１つ前のパケットの送信時に用いた出力バッファを再利用する。さらに、ルーティング再利用通知部１５０１は、次の中継器７１１にルーティングの再利用を通知する（ステップ２６０３）。
【０１８１】
１つ前のパケットの送信時に利用した出力バッファを継続して利用できない場合には、処理はステップ８０４に進み、バッファ割当部７０５は利用する出力バッファを再度決定する。
【０１８２】
ステップ８０６において、バッファ割当部７０５により、入力バッファに対して出力バッファが割り当てられると、ルーティング再利用通知部１５０１は、入力バッファ内のパケットの宛先が、１つ前のパケットの宛先と同じかどうか判定する（ステップ２６０４）。同じ出力バッファに宛先が同じパケットが連続して割り当てられると、ルーティング再利用通知１５０１は、ルーティング処理が不要であることをパケットが中継される次の中継器に通知する（ステップ２６０５）。
【０１８３】
このように、本実施形態の中継器８１０は、ルーティング再利用通知部１５０１により、ルーティングの再利用の可否を判定し、再利用が可能な場合には、ルーティングの再利用が可能であることを次の中継器７１１に通知する。そして次の中継器７１１でのルーティング処理（ステップ８０３）および出力バッファの割り当て（ステップ８０６）を省略する。これにより、中継器内での遅延時間の削減できる。
【０１８４】
また、バッファ割当部７０５において、各入力バッファに対して、出力バッファを割り当てる際に、混雑情報に基づいて、宛先が同じパケットを、同じ出力バッファに連続して割り当てるようにしても良い。
【０１８５】
例えば、中継器を通過するトラヒックの数に対して、入出力バッファの数が少ない場合には、トラヒック間で入出力バッファを交代して利用しなければならない。このため、混雑度の低いトラヒックに対してのみ、優先的に同じ入出力バッファを割り当てて、連続して同じ宛先のパケットが、同じ出力バッファを介して次の中継器に送信されるようにする。これにより混雑度が低いトラヒックの遅延時間をさらに削減することができる。
【０１８６】
以上の構成と処理を加えることにより、本実施形態における中継器８１０は、混雑度が低いトラヒックに対するルーティング処理と出力バッファの割り当てに必要な処理を省略できるため、回路全体での伝送性能の低下を抑制することができる。
【０１８７】
なお、本実施形態の説明では、混雑度の低いトラヒックには、同じ出力バッファを優先的に割り当てる場合を例に説明した。しかしながら、逆に混雑度の高いトラヒックに同じ出力バッファを優先的に割り当てることによって、混雑度の高いトラヒックの遅延時間を抑制してもよい。これにより、伝送遅延の改善をするようにしてもよい。
【０１８８】
なお、本実施形態では、ルーティング再利用通知により、ルーティング処理を省略するとした。ルーティング処理のための計算処理、および再利用の可否判定は、いずれも最低１サイクルかかる。したがって、トラヒックを受信した中継器自らがルーティングを行わないことにより、処理時間を改善することが可能になる。
【０１８９】
ルーティング再利用通知の「判定処理」は、たとえば、ヘッダーフリットの「判定処理」と並行して行うことができる。よって、処理時間を増加させることはない。
【０１９０】
よって、前段の中継器でのルーティングの結果を、次の中継器に順番に伝えて同じ処理を省略することにより、処理時間の削減が可能になる。
【０１９１】
（実施形態４）
本実施形態では、中継器により、分散バスの動作クロックを個別変更ができる場合を想定し、混雑度の大きいトラヒックが流れる経路上のバスの動作クロックを上げ、フリットを他のバスよりも早く送信することで、伝送遅延を抑制する。
【０１９２】
図２５は、本実施形態における中継器８２０の構成図である。図２５の構成要素のうち図７と同じ構成については、同じ参照符号を付与し説明を省略する。
【０１９３】
動作クロック調整部１６０１は、送信スケジュール調整部７０９により、混雑度が大きく優先度の低いトラヒックを検出すると、トラヒックが出力される側のバスの動作クロックを向上させる。
【０１９４】
図２６は、本実施形態における中継器８２０の動作を説明する図である。
【０１９５】
図８と同じ動作については、同じ参照符号を付与し説明を省略する。
【０１９６】
動作クロック調整部１６０１は、スイッチ割当部７０６によって、各入力バッファと出力バッファ間でのスイッチの割り当てが決定されると、バッファの混雑度が所定の閾値よりも高いかどうかを判定する（ステップ２７０１）。
【０１９７】
混雑度が閾値を超える入力バッファが存在しなければ、動作クロック調整部１６０１は、対応するバスの動作速度を、通常の利用時を想定して事前に設定した動作速度に設定する（ステップ２７０２）。
【０１９８】
混雑度が閾値を越える入力バッファが存在する場合には、動作クロック調整部１６０１は、対応するバスの動作速度を、通常の利用時を想定して事前に設定した動作速度よりも早い動作速度に設定する（ステップ２７０３）。
【０１９９】
以上の構成を加えることにより、本実施形態の中継器８２０は、混雑度の高いトラヒックを素早く次の中継器へ送信し、遅延時間を削減することが可能になる。よって、回路全体の伝送性能の低下を抑制することができる。
【０２００】
（実施形態５）
本実施形態１から４においては、隣接する中継器間でトラヒックごとの遅延時間を交換し、互いの遅延時間の比較によってトラヒックごとに経路上での流れにくさを求め、その値に基づいて各トラヒックへの送信スケジューリングを調整する。このため、実施形態１から実施形態４の中継器は、隣接する中継器どうしが連携し、協調した送信スケジューリング制御を行う。
【０２０１】
このような中継器間で協調した送信スケジューリング制御では、ある中継器において、あるトラヒックの遅延時間が、所定の閾値よりも大きくなった場合。このトラヒックの遅延時間を抑制しようとしても、隣接する中継器と協調した送信スケジューリングが優先され、すぐに自中継器内でトラヒックの遅延が発生する。
【０２０２】
これに対し、本実施形態では、自中継器での混雑度が所定の閾値よりも高い場合は、隣接する中継器と協調した送信スケジューリングを行わず、自中継器内での混雑の状況にのみに基づいて、自中継器内での遅延を抑制するように利己的な送信スケジューリングを行う。
【０２０３】
図２７は、本実施形態における中継器８３０の構成を示す図である。図２７の構成要素のうち図７と同じ構成については、同じ参照符号を付与し説明を省略する。
【０２０４】
内部混雑情報監視部２８０１は、自中継器８３０でのトラヒックの遅延時間が、所定の閾値を越えているかどうかを判定する処理部である。
【０２０５】
協調制御停止部２８０２は、自中継器８３０でのトラヒックの遅延時間が、所定の閾値を超えた場合に、隣接する中継器７１１との遅延時間の比較による混雑度の算出をやめて、代わりに自中継器での遅延時間にのみ基づいて、混雑度を特定する処理部である。
【０２０６】
図２８は、本実施形態における中継器８３０の動作を説明する図である。
【０２０７】
図８と同じ動作については、同じ参照符号を付与し説明を省略する。
【０２０８】
中継器８３０の内部混雑度監視部２８０１は、自中継器８３０内の入力バッファの遅延時間が、所定の閾値よりも大きいかどうかを判定する（ステップ２８０１）。
【０２０９】
自中継器８３０内の入力バッファの遅延時間が、所定の閾値よりも小さい場合には、協調制御停止部２８０２は、混雑情報比較部７０８に指示して、隣接する中継器７１１での遅延時間と自中継器８３０での遅延時間の比較により混雑度を求め、送信スケジュール調整部７０９に混雑度を伝える（ステップ２８０２）。
【０２１０】
一方、自中継器８３０内の入力バッファの遅延時間が、所定の閾値よりも大きい場合には、協調制御停止部２８０２は、混雑情報比較部７０８に代わり自中継器８３０での遅延時間の大きさだけを利用して混雑度を求め、送信スケジュール調整部７０９に混雑度を伝える（ステップ２８０２）。
【０２１１】
以上の構成を加えることにより、本実施形態の中継器８３０は、自中継器で発生している遅延時間が所定の閾値よりも高い場合には、隣接する中継器の混雑の状況に合わせることなく、利己的な送信スケジューリング制御によって、自中継器内での遅延時間の削減を最優先させることができるため、回路全体の伝送性能の低下を抑制しながらも、局所的な伝送性能の低下も抑制することができる。
【０２１２】
（実施形態６）
実施形態６では、回線交換方式の中継器が送信スケジュールを調整する処理を説明する。
【０２１３】
図２９はパケット交換方式と回線交換方式の違いを説明する図である。
【０２１４】
図２９（ａ）、（ｂ）のグラフは、それぞれ交換方式でのデータの流れ方を表しており、グラフの縦軸はデータの位置、横軸は時間の流れを表している。
【０２１５】
パケット交換方式では、図２９（ａ）に示すように、トラヒックはフリット単位でバスマスタから順番に中継器へと送信される。
【０２１６】
これに対し、回線交換方式では、図２９（ｂ）に示すように、最初に回線交換のための信号がバスマスタから順番に中継器を通って宛先まで送られる。これにより回線が切り替えられ、その後、データが送信される。
【０２１７】
図３０は、本実施形態による、回線交換方式の中継器８４０の構成を示す。中継器８４０では、図３０に示すように、入力バッファ７０１は、スイッチの切り替え信号を蓄えるための１フリット分のサイズだけあればよい。それ以外は図７のパケット交換方式の構成と同じであるため説明は省略する。
【０２１８】
回線交換方式では、回線が確保された後は、トラヒック間で干渉が発生しないため、データの送信前のスイッチの切り替え用の信号についてのみ送信スケジューリングを調整すればよく、その調整は、パケット交換方式のヘッダーフリットと同様の方法で調整できる。
【０２１９】
以上、本発明の各実施形態を説明した。本明細書においては、各実施形態の中継器の構成要素はいずれもハードウェアによって実現されることを想定して説明した。ハードウェアは、構成要素ごとに設けられてもよいし、複数の構成要素を統合した回路などとして設けられてもよい。ハードウェアとして設けることにより、各中継器の処理が高速化され、内部処理遅延を最小限に抑えることが可能になる。なお、内部処理遅延が問題とならない程度に高速に処理できる場合には、上述の構成要素の１つまたは複数の機能をマイコンがソフトウェアを実行することにより、ソフトウェア的に実現してもよい。
【産業上の利用可能性】
【０２２０】
本発明にかかる中継器は、分散型のバスを備える集積回路において、複数のトラヒックの干渉による遅延やジッターの増加を抑制することができるため、メディア処理などリアルタイムで複数のトラヒック伝送が発生するＳｏＣ（System on Chip）などでの分散バス制御において有用である。
【０２２１】
また、遅延時間を抑制による処理時間の短縮化により、集積回路の省電化にも有用である。
【符号の説明】
【０２２２】
７００ 中継器
７０１ 入力バッファ
７０２ スイッチ
７０３ 出力バッファ
７０４ ルーティング処理部
７０５ バッファ割当部
７０６ スイッチ割当部
７０７ 混雑情報処理部
７０８ 混雑情報比較部
７０９ 送信スケジュール調整部
７１０ 隣接の中継器（受信側）
７１１ 隣接の中継器（送信側）
１４０１ パケット廃棄部
１４０２ 再送要求部
１５０１ ルーティング再利用通知部
１６０１ 動作クロック調整部
２８０１ 内部混雑情報監視部
２８０２ 協調制御停止部
【特許請求の範囲】
【請求項１】
分散型のバスを備える集積回路において、複数のバスを接続する中継器であって、前記バス上を伝送される各トラヒックのトラヒックデータは、パケットに分割されており、
トラヒックデータを受け取る入力および前記トラヒックデータを送出する出力の組み合わせを切り替えるスイッチと、
複数のトラヒックを共通して扱う隣接の中継器からのトラヒックごとの混雑の程度を示す混雑情報と、自中継器における前記トラヒックごとの混雑情報とを取得する混雑情報処理部と、
前記隣接の中継器から取得した前記混雑情報および自中継器における前記混雑情報に基づいて、伝送経路上でのトラヒックごとの流れにくさを定量的に示す混雑度の情報を求める混雑情報比較部と、
前記混雑度に基づいて、前記トラヒックごとにバスの伝送帯域を割り当てて送信スケジュールを調整する送信スケジュール調整部と、
前記バスの伝送帯域の割り当て結果に基づき、前記スイッチを切り替えるスイッチ割当部と、
前記混雑度が予め定められた閾値よりも大きいトラヒックのパケットを入力バッファから廃棄するパケット廃棄部と、
廃棄されたパケットの再送を送信元のバッファに要求する再送要求部と
を備えた、中継器。
【請求項２】
分散型のバスを備える集積回路において、複数のバスを接続する中継器であって、前記バス上を伝送される各トラヒックのトラヒックデータは、パケットに分割されており、
トラヒックデータを受け取る入力および前記トラヒックデータを送出する出力の組み合わせを切り替えるスイッチと、
複数のトラヒックを共通して扱う隣接の中継器からのトラヒックごとの混雑の程度を示す混雑情報と、自中継器における前記トラヒックごとの混雑情報とを取得する混雑情報処理部と、
前記隣接の中継器から取得した前記混雑情報および自中継器における前記混雑情報に基づいて、伝送経路上でのトラヒックごとの流れにくさを定量的に示す混雑度の情報を求める混雑情報比較部と、
前記混雑度に基づいて、前記トラヒックごとにバスの伝送帯域を割り当てて送信スケジュールを調整する送信スケジュール調整部と、
前記バスの伝送帯域の割り当て結果に基づき、前記スイッチを切り替えるスイッチ割当部と、
異なるバスにデータを送出する複数の出力にそれぞれ接続された複数の出力バッファと、
前記混雑度が予め定められた閾値よりも大きいトラヒックの連続するパケットに対して、同じ出力バッファを割当て、さらにトラヒックが送信される次の中継器に対して、ルーティングの設定の再利用を通知するルーティング再利用通知部と
を備えた、中継器。
【請求項１】
分散型のバスを備える集積回路において、複数のバスを接続する中継器であって、前記バス上を伝送される各トラヒックのトラヒックデータは、パケットに分割されており、
トラヒックデータを受け取る入力および前記トラヒックデータを送出する出力の組み合わせを切り替えるスイッチと、
複数のトラヒックを共通して扱う隣接の中継器からのトラヒックごとの混雑の程度を示す混雑情報と、自中継器における前記トラヒックごとの混雑情報とを取得する混雑情報処理部と、
前記隣接の中継器から取得した前記混雑情報および自中継器における前記混雑情報に基づいて、伝送経路上でのトラヒックごとの流れにくさを定量的に示す混雑度の情報を求める混雑情報比較部と、
前記混雑度に基づいて、前記トラヒックごとにバスの伝送帯域を割り当てて送信スケジュールを調整する送信スケジュール調整部と、
前記バスの伝送帯域の割り当て結果に基づき、前記スイッチを切り替えるスイッチ割当部と、
前記混雑度が予め定められた閾値よりも大きいトラヒックのパケットを入力バッファから廃棄するパケット廃棄部と、
廃棄されたパケットの再送を送信元のバッファに要求する再送要求部と
を備えた、中継器。
【請求項２】
分散型のバスを備える集積回路において、複数のバスを接続する中継器であって、前記バス上を伝送される各トラヒックのトラヒックデータは、パケットに分割されており、
トラヒックデータを受け取る入力および前記トラヒックデータを送出する出力の組み合わせを切り替えるスイッチと、
複数のトラヒックを共通して扱う隣接の中継器からのトラヒックごとの混雑の程度を示す混雑情報と、自中継器における前記トラヒックごとの混雑情報とを取得する混雑情報処理部と、
前記隣接の中継器から取得した前記混雑情報および自中継器における前記混雑情報に基づいて、伝送経路上でのトラヒックごとの流れにくさを定量的に示す混雑度の情報を求める混雑情報比較部と、
前記混雑度に基づいて、前記トラヒックごとにバスの伝送帯域を割り当てて送信スケジュールを調整する送信スケジュール調整部と、
前記バスの伝送帯域の割り当て結果に基づき、前記スイッチを切り替えるスイッチ割当部と、
異なるバスにデータを送出する複数の出力にそれぞれ接続された複数の出力バッファと、
前記混雑度が予め定められた閾値よりも大きいトラヒックの連続するパケットに対して、同じ出力バッファを割当て、さらにトラヒックが送信される次の中継器に対して、ルーティングの設定の再利用を通知するルーティング再利用通知部と
を備えた、中継器。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【公開番号】特開２０１１−２２９１９２（Ｐ２０１１−２２９１９２Ａ）
【公開日】平成２３年１１月１０日（２０１１．１１．１０）
【国際特許分類】
【出願番号】特願２０１１−１７８９０７（Ｐ２０１１−１７８９０７）
【出願日】平成２３年８月１８日（２０１１．８．１８）
【分割の表示】特願２０１１−５３２３７２（Ｐ２０１１−５３２３７２）の分割
【原出願日】平成２３年１月７日（２０１１．１．７）
【出願人】（０００００５８２１）パナソニック株式会社 (73,050)
【Ｆターム（参考）】
【公開日】平成２３年１１月１０日（２０１１．１１．１０）
【国際特許分類】
【出願日】平成２３年８月１８日（２０１１．８．１８）
【分割の表示】特願２０１１−５３２３７２（Ｐ２０１１−５３２３７２）の分割
【原出願日】平成２３年１月７日（２０１１．１．７）
【出願人】（０００００５８２１）パナソニック株式会社 (73,050)
【Ｆターム（参考）】
[ Back to top ]