(57)【要約】【課題】複数の転送待ちのパケットが有する、パケットの転送に使用される情報を更新する場合に、全てのパケットの情報を時間をかけることなく更新すること。【解決手段】本発明にかかるパケット転送装置は、送信先への到着期限までの残り時間を示す残時間情報を有するパケットを、送信元から受信して、送信先に転送するパケット転送装置である。パケット転送装置は、パケットが一時的に格納される複数のパケット記憶部と、複数のパケット記憶部に格納されたパケットのうち、残時間情報が示す残り時間のより少ないパケットを優先的に転送する転送制御部とを備える。複数のパケット記憶部は、所定のタイミングで当該複数のパケット記憶部に同時に入力される指示信号に応じて、パケット記憶部に格納されたパケットが有する残時間情報が示す残り時間が少なくなるように残時間情報を更新する。【選択図】図４
2013005145.tif 000002
【特許請求の範囲】
【請求項１】
送信先への到着期限までの残り時間を示す残時間情報を有するパケットを、送信元から受信して、前記送信先に転送するパケット転送装置であって、
前記パケットが一時的に格納される複数のパケット記憶部と、
前記複数のパケット記憶部に格納されたパケットのうち、前記残時間情報が示す残り時間のより少ないパケットを優先的に転送する転送制御部と、を備え、
前記複数のパケット記憶部は、所定のタイミングで当該複数のパケット記憶部に同時に入力される指示信号に応じて、当該パケット記憶部に格納されたパケットが有する残時間情報が示す残り時間が少なくなるように前記残時間情報を更新する、
パケット転送装置。
【請求項２】
前記パケット記憶部に格納されたパケットが有する残時間情報が示す残り時間が下限値となった場合に、当該パケットが有する時間情報の更新を停止する更新停止部をさらに備えた請求項１に記載のパケット転送装置。
【請求項３】
前記送信先は、第１の送信先又は第２の送信先を含む複数の送信先のうち、いずれかであり、
前記パケットは、前記送信先を示す送信先情報を有し、
前記複数のパケット記憶部は、前記第１の送信先を示す送信先情報を有するパケットが格納される複数の第１のパケット記憶部と、前記第２の送信先を示す送信先情報を有するパケットが格納される複数の第２のパケット記憶部と、を含み、
前記パケット転送装置は、前記受信したパケットに含まれる送信先情報に応じて、当該パケットを前記第１のパケット記憶部又は前記第２のパケット記憶部に振り分ける振り分け部をさらに備え、
前記転送制御部は、前記複数の第１のパケット記憶部に格納されたパケットを前記第１の送信先に転送する第１の転送制御部と、前記複数の第２のパケット記憶部に格納されたパケットを前記第２の送信先に転送する第２の転送制御部と、を有する、
請求項１に記載のパケット転送装置。
【請求項４】
前記パケット転送装置は、前記振り分け部が振り分けるパケットのうち、少なくとも前記送信先情報及び前記残時間情報が一時的に格納される一時記憶部をさらに備え、
前記振り分け部は、前記一時記憶部に格納された送信先情報に応じて、前記パケットを振り分け、
前記指示信号は、前記一時記憶部と前記複数のパケット記憶部に同時に入力され、
前記一時記憶部は、前記指示信号に応じて、当該一時記憶部に格納されたパケットが有する残時間情報が示す残り時間が少なくなるように前記残時間情報を更新する、
請求項３に記載のパケット転送装置。
【請求項５】
前記パケット転送装置は、前記送信元又は前記送信先となる複数のノードを有する半導体チップに含まれる、請求項１乃至４のいずれか１項に記載のパケット転送装置。
【請求項６】
前記パケット転送装置は、前記残時間情報を有するパケットであるリアルタイムパケットに加えて、さらに前記残時間情報を有しないノーマルパケットを転送するパケット転送装置であって、
前記複数のパケット記憶部は、前記リアルタイムパケット又は前記ノーマルパケットが一時的に格納され、
前記転送制御部は、前記ノーマルパケットよりも前記リアルタイムパケットを優先的に転送する、
請求項１乃至５のいずれか１項に記載のパケット転送装置。
【請求項７】
前記パケット転送装置は、前記パケット記憶部に格納されたパケットが前記ノーマルパケットである場合に、当該ノーマルパケットに対する前記残時間情報の更新を抑止する更新抑止部をさらに備えた、請求項６に記載のパケット転送装置。
【請求項８】
前記ノーマルパケットは、前記ノーマルパケットであることを示す種別情報を有し、
前記リアルタイムパケットは、前記リアルタイムパケットであることを示す種別情報を有し、
前記転送制御部及び前記更新抑止部は、前記パケットが有する種別情報に基づいて、当該パケットが前記ノーマルパケットであるか前記リアルタイムパケットであるかを判定する、
請求項７に記載のパケット転送装置。
【請求項９】
前記指示信号は、所定の時間経過するごとに入力されるパルスであり、
前記パケット記憶部は、前記パルスに応じて、前記残時間情報をディクリメントする、請求項１乃至８のいずれか１項に記載のパケット転送装置。
【請求項１０】
送信先への到着期限までの残り時間を示す残時間情報を有するパケットを、送信元から受信して、前記送信先に転送するパケット転送方法であって、
所定のタイミングで複数のパケット記憶部に同時に指示信号を入力し、
前記複数のパケット記憶部が、前記指示信号に応じて、当該パケット記憶部に格納されたパケットが有する残時間情報が示す残り時間が少なくなるように前記残時間情報を更新し、
前記複数のパケット記憶部に格納されたパケットのうち、前記残時間情報が示す残り時間のより少ないパケットを優先的に転送する、
パケット転送方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット転送装置及びパケット転送方法に関する。
【背景技術】
【０００２】
携帯端末及び制御装置等の組み込み機器において、高機能化、高性能化、及び低電力化の要求が強くなってきている。そのため、組み込み機器においても、マルチコア化が進んできている。マルチコア構成は、デスクトップPC（Personal Computer）でも採用が進んでいる構成である。
【０００３】
また、マルチコア化に伴い、ネットワークオンチップ（Network On Chip（NoC））技術の採用も進んでいる。NoCでは、ネットワークスイッチを用いたネットワークでコア間通信を実現する。今後、コア間通信におけるネットワークスイッチは、組み込み用のプラットフォームとして期待が持てる。しかしながら、組み込み機器に必要な実時間性を実現するためには、コア間通信路に実時間性を保証する機構を設けるか、システムの最大性能を平均的な処理に必要な性能以上に高くする等、冗長な性能を準備する必要がある。例えば、外部I/O、メモリ、及びコア間の通信路におけるネットワークスイッチに、実時間性を保証する通信機構を備えることができれば、組み込み機器に必要な実時間性の実現に非常に有効である。
【０００４】
特許文献１には、特に輻輳時において、必要なパケットのみに限定したパケットの処理や転送が可能となり、パケット網全体の信頼性が向上するパケット転送処理方式が開示されている。以下、このパケット転送処理方式の処理手順について説明する。
【０００５】
まず、新たなパケットが到着したときに、パケットの許容可能な処理時間に基づいて、許容可能な処理時間の小さなものから順にチェイン状に配列されるように、蓄積部に蓄積されたパケットの転送待ちキューの配列を行う。この処理時間は、パケットのヘッダ部に設定された許容処理時間情報によって示される。各パケットの許容可能な処理時間は、その処理時間の基本単位であるクロックの到来毎に１カウントずつ減算されてゆく。蓄積部から送出される以前に許容可能な処理時間が経過してしまったパケットの廃棄の可否が、ヘッダ部に設定された処理種別に基づいて判別される。そして、パケットが廃棄可能であれば、そのパケットを配列より取り出して廃棄する。
【０００６】
上述したように、特許文献１に開示のパケット転送処理方式では、許容可能な処理時間を基本単位としたクロックの到来に応じて、各パケットの許容可能な処理時間を１カウントずつ減算するようにしている。しかしながら、特許文献１には、クロックの到来に応じて、全てのパケットの許容可能な処理時間をどのように減算していくかについては、具体的に述べられていない。
【０００７】
ここで、例えば、各パケットの許容可能な処理時間を順番に減算していくようにしている場合について考える。この場合、パケットの許容可能な処理時間の減算を開始してから、全てのパケットの許容可能な処理時間の減算が完了するまでに、一定の時間がかかってしまうことになる。よって、全てのパケットの許容可能な処理時間の減算が完了するまでに、新たなパケットが到着したときには、許容可能な処理時間を減算済みのパケットと、許容可能な処理時間を減算済みでないパケットとが混在した転送待ちキューに対して、新たなパケットの配列が行われてしまい、期待した順序で転送待ちキューが配列されなくなってしまう。その結果、期待した順序でパケットを転送することができなくなってしまうという問題がある。
【０００８】
このように、複数の転送待ちのパケットが有する、パケットの転送に使用される情報を更新する場合に、全てのパケットの情報の更新に時間がかかってしまうと、不整合が生じてしまうという問題がある。特に、NoCのように、高速動作を行うハードウェアでの実装を前提としたネットワーク環境においては、パケットの送受信頻度も極めて高くなる。そのため、上述したようなパケットの転送に関する情報の更新に時間をかける余裕はなく、全てのパケットの情報を同期して更新することが特に必要となる。
【０００９】
ここで、パケットの転送に関する技術を開示したものとして、以下の特許文献２〜６もある。
【００１０】
特許文献２に開示の技術は、パケットに、パケットが目的地に着くまでの遅延時間の上限値Tmaxを示すエリアと、出発地を起点に現時点までの経過時間Tacmを示すエリアを設けている。そして、Tmax−Tacmがある値以上の時は、優先度クラスに対応する送出待ち行列に加え、Tmax−Tacmがある値以下になった時は、優先度クラスより高優先度の送出待ち行列に加えるようにしている。
【００１１】
特許文献３に開示の技術は、パケットごとに優先度（＝移動局の受信品質×１／パケットの残余時間）を算出する。そして、優先度が最大であるパケットの格納されているキューを選択する。
【００１２】
特許文献４に開示の技術は、必着時刻指定の転送要求の残り時間を管理し、管理結果に基づいて目的ノードに対する転送優先順位を任意に変更する。
【００１３】
特許文献５に開示の技術は、複数の情報処理装置間で実時間通信を行う場合において、通信ノード（情報処理装置）毎に優先度に応じた通信パケットの追い越しを行う。その際に通信ノード毎に優先度を付け替え、さらに優先度毎に異なる経路を設定できるようにしている。
【００１４】
特許文献６には、複数の入力ポートから入力された通信パケットを複数の出力ポートへ出力するスイッチ部が開示されている。スイッチ部は、空間スイッチと、時間スイッチとで構成されている。空間スイッチは、通信パケットに付与された宛先アドレスに対応してその経路を切り替える。時間スイッチは、複数の通信パケットの順序を任意に入れ替え可能である。時間スイッチは、複数の通信パケットの順序が各通信パケットに付与された送達希望時刻に対応する順序となるように制御される。
【００１５】
しかしながら、特許文献２〜６のいずれも、複数の転送待ちのパケットが有する、パケットの転送に使用される情報を更新する場合に、全てのパケットの情報を時間をかけることなく更新する技術を具体的に開示したものではない。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特開平０１−１３３４４７号公報
【特許文献２】特開平６２−０２８９０５号公報
【特許文献３】特開２００４−１４７２７５号公報
【特許文献４】特開６２−２１７７４９号公報
【特許文献５】特開２０００−２２８６７７号公報
【特許文献６】特開２０００−０７８１８８号公報
【発明の概要】
【発明が解決しようとする課題】
【００１７】
背景技術として説明したように、複数の転送待ちのパケットが有する、パケットの転送に使用される情報を更新する場合に、全てのパケットの情報の更新に時間がかかってしまうと、不整合が生じてしまうという問題がある。
【課題を解決するための手段】
【００１８】
本発明の第１の態様にかかるパケット転送装置は、送信先への到着期限までの残り時間を示す残時間情報を有するパケットを、送信元から受信して、前記送信先に転送するパケット転送装置であって、前記パケットが一時的に格納される複数のパケット記憶部と、
前記複数のパケット記憶部に格納されたパケットのうち、前記残時間情報が示す残り時間のより少ないパケットを優先的に転送する転送制御部と、を備え、前記複数のパケット記憶部は、所定のタイミングで当該複数のパケット記憶部に同時に入力される指示信号に応じて、当該パケット記憶部に格納されたパケットが有する残時間情報が示す残り時間が少なくなるように前記残時間情報を更新するものである。
【００１９】
本発明の第２の態様にかかるパケット転送方法は、送信先への到着期限までの残り時間を示す残時間情報を有するパケットを、送信元から受信して、前記送信先に転送するパケット転送方法であって、所定のタイミングで複数のパケット記憶部に同時に指示信号を入力し、前記複数のパケット記憶部が、前記指示信号に応じて、当該パケット記憶部に格納されたパケットが有する残時間情報が示す残り時間が少なくなるように前記残時間情報を更新し、前記複数のパケット記憶部に格納されたパケットのうち、前記残時間情報が示す残り時間のより少ないパケットを優先的に転送するものである。
【００２０】
これによれば、複数のパケット記憶部のそれぞれに格納された残時間情報を更新する場合に、全てのパケットにおける残時間情報を同期して更新することができる。ここで、残時間情報は、パケットの転送に使用される情報となる。
【発明の効果】
【００２１】
上述した本発明の各態様によれば、複数の転送待ちのパケットが有する、パケットの転送に使用される情報を更新する場合に、全てのパケットの情報を時間をかけることなく更新することができるパケット転送装置及びパケット転送方法を提供することができる。
【図面の簡単な説明】
【００２２】
【図１】本発明の実施の形態１にかかるマルチコアシステムの構成図である。
【図２】本発明の実施の形態１にかかるノード及びネットワークスイッチの接続関係を示す図である。
【図３】本発明の実施の形態１にかかるパケットの構成を示す図である。
【図４】本発明の実施の形態１にかかるネットワークスイッチの構成図である。
【図５】本発明の実施の形態１にかかるパケットバッファのヘッダ部の構成図である。
【図６Ａ】本発明の実施の形態１にかかる入力制御部の処理を示すフローチャートである。
【図６Ｂ】本発明の実施の形態１にかかる出力制御部の処理を示すフローチャートである。
【図７】本発明の実施の形態２にかかるネットワークスイッチの構成図である。
【図８Ａ】本発明の実施の形態２にかかる入力制御部及びDeMux部の処理を示すフローチャートである。
【図８Ｂ】本発明の実施の形態２にかかるArbiter部及びMux部の処理を示すフローチャートである。
【図９】本発明の実施の形態１にかかるネットワークスイッチを２×２とした構成図である。
【図１０】本発明の実施の形態３にかかるネットワークスイッチの構成図である。
【発明を実施するための形態】
【００２３】
発明の実施の形態１．
まず、図１を参照して、本発明の実施の形態１にかかるマルチコアシステム１について説明する。図１は、本発明の実施の形態１にかかるマルチコアシステム１の構成図である。
【００２４】
マルチコアシステム１は、処理要素（PE：Processing Element）ノード２ａ〜２ｅ、I/O（Input/Output）ノード３ａ、３ｂ、メモリノード４ａ、４ｂ、通信路（NoC）５、及びグローバルタイマ６を有する。通信路５には、複数のネットワークスイッチ（図示せず）が含まれている。処理要素ノード２ａ〜２ｅ、I/Oノード３ａ、３ｂ、メモリノード４ａ、４ｂのそれぞれは、通信路５を介して相互に接続されている。マルチコアシステム１は、例えば、１つの半導体チップ上に構成される。
【００２５】
処理要素ノード２ａ〜２ｅのそれぞれは、例えば、プロセッサコア又はプロセッサ等の演算装置である。処理要素ノード２ａ〜２ｅのそれぞれは、データ書き込み要求パケット又はデータ読み出し要求パケットを生成してI/Oノードに出力する。データ書き込み要求パケットは、I/Oデバイスへのデータ書き込みを要求するパケットであり、データ読み出し要求パケットは、I/Oデバイスからのデータ読み出しを要求するパケットである。データ書き込み要求パケットは、I/Oデバイスに書き込むデータを含む。
【００２６】
また、処理要素ノード２ａ〜２ｅのそれぞれは、データ書き込み要求パケット又はデータ読み出し要求パケットを生成してメモリノードに送信する。データ書き込み要求パケットは、メモリへのデータ書き込みを要求するパケットであり、データ読み出し要求パケットは、メモリからのデータ読み出しを要求するパケットである。データ書き込み要求パケットは、メモリに書き込むデータを含む。
【００２７】
I/Oノード３ａ、３ｂのそれぞれは、例えば、I/Oデバイスを制御するI/Oコントローラである。I/Oノード３ａ、３ｂのそれぞれは、処理要素ノードからのデータ書き込み要求パケットに応じて、I/Oデバイスにデータを書き込む。なお、ここで書き込まれるデータは、データ書き込み要求パケットに含まれていたデータとなる。また、I/Oノード３ａ、３ｂのそれぞれは、処理要素ノードからのデータ読み出し要求パケットに応じて、I/Oデバイスからデータを読み出す。そして、I/Oノード３ａ、３ｂのそれぞれは、読み出したデータを含めたパケットを、データ読み出しを要求した処理要素ノードに送信する。パケットの内容によってはデータ読み出しを要求した処理要素ノードとは別のノードにデータを送信することも考えられる。
【００２８】
メモリノード４ａ、４ｂのそれぞれは、例えば、メモリコントローラである。メモリノード４ａ、４ｂのそれぞれは、処理要素ノードからのデータ書き込み要求パケットに応じて、メモリにデータを書き込む。なお、ここで書き込まれるデータは、データ書き込み要求パケットに含まれていたデータとなる。また、メモリノード４ａ、４ｂのそれぞれは、処理要素ノードからのデータ読み出し要求パケットに応じて、メモリからデータを読み出す。そして、メモリノード４ａ、４ｂのそれぞれは、読み出したデータを含めたパケットを、データ読み出しを要求した処理要素ノードに送信する。パケットの内容によってはデータ読み出しを要求した処理要素ノードとは別のノードにデータを送信することも考えられる。
【００２９】
I/Oノード３ａ、３ｂのそれぞれは、データ書き込み要求パケット又はデータ読み出し要求パケットを生成してメモリノードに送信するように構成することも可能である。
【００３０】
通信路５は、各ノード２ａ〜２ｅ、３ａ、３ｂ、４ａ、４ｂ間で、パケットを相互に伝送する。通信路５は、各パケットの転送先を切り替えるネットワークスイッチ（図示せず）を有している。ネットワークスイッチについては、後述する。
【００３１】
グローバルタイマ６は、絶対時刻を示す絶対時刻情報を、各ノード２ａ〜２ｅ、３ａ、３ｂ、４ａ、４ｂ、及び通信路５に出力する。
【００３２】
ここで、マルチコアシステムにおける通信のように、実時間性が要求される通信においては、パケットが送信先のノードへの到着すべき時刻（以下、「送達時刻」と言う）より前に届く必要がある。そこで、パケットの送信元のノードは、余裕時間（以下、「マージン」とも言う）をパケットの優先度としてパケットに設定する。ここで、余裕時間とは、送達時刻と現在時刻の差である。本実施の形態１では、パケットに設定されたマージンをネットワークスイッチでのパケットの滞留時間に応じて更新することで、パケットの優先度が適切になるように制御する。
【００３３】
ここで、パケットの生成時刻から、そのパケットの送達時刻が相対的に決定される場合、現在時刻とは無関係にマージンを設定することも可能である。例えば、処理要素ノードがメモリから一定時間内にデータを取得する必要がある場合、データ読み出し要求パケットがその時間に応じた時間内にメモリノードに到着している必要がある。より具体的には、処理要素ノードがメモリから１ｍｓｅｃ以内にデータを取得する必要があり、そのために５００μｓｅｃ以内にメモリノードにデータ読み出し要求パケットが到達している必要がある場合、現在時刻とは無関係にマージンとして単純に５００μｓｅｃを設定すればよい。
【００３４】
このようなパケットのみを取り扱う場合は、絶対時刻を各ノード２ａ〜２ｅ、３ａ、３ｂ、４ａ、４ｂ、及び通信路５に含まれるネットワークスイッチ（図示せず）で共有する必要はなく、時間の最小単位の間隔（例えば、１ｍｓｅｃ又は１μｓｅｃ等）を共有しておけばよい。言い換えると、ノードが設定する余裕時間の単位と、ネットワークスイッチで余裕時間を更新する単位とを一致させておけばよい。
【００３５】
一方で、パケットの生成時刻に関係なく、そのパケットの送達時刻が、ある絶対時刻として決定されている場合、送達時刻と現在時刻との差を算出してマージンとして設定する必要がある。例えば、処理要素ノードが予め定められた絶対時刻におけるI/Oデバイスのデータを取得する必要がある場合、その時刻までにデータ読み出し要求パケットがI/Oノードに到達している必要がある。より具体的には、処理要素ノードがI/Oデバイスから、絶対時刻ｔ１におけるデータを取得する必要があり、現在時刻がｔ０である場合、絶対時刻から現在時刻を減算したｔ１−ｔ０をマージンとして設定する必要がある。
【００３６】
このようなパケットを取り扱う場合は、絶対時刻を各ノード２ａ〜２ｅ、３ａ、３ｂ、４ａ、４ｂ、及びネットワークスイッチで共有する必要がある。これは、本実施の形態１に示すように、グローバルタイマから絶対時刻情報を各ノード２ａ〜２ｅ、３ａ、３ｂ、４ａ、４ｂ、及びネットワークスイッチにブロードキャストで出力することによって、各ノード２ａ〜２ｅ、３ａ、３ｂ、４ａ、４ｂ、及びネットワークスイッチで共通の絶対時刻を認識可能とすることで実現することができる。なお、各ノード２ａ〜２ｅ、３ａ、３ｂ、４ａ、４ｂ、及びネットワークスイッチで絶対時刻を共有する方法は、これに限られない。例えば、それぞれのノード及びネットワークスイッチが現実世界の絶対時刻に正確に一致している時計を有するようにすることで実現することも可能である。なお、時間の最小単位の間隔のみ共有する場合は、グローバルタイマ６は不要となる。
【００３７】
このように、本実施の形態にかかるパケット転送方式は、時間の最小単位の間隔のみ共有する場合、絶対時刻を共有する場合のいずれの場合にも適用可能である。
【００３８】
続いて、図２を参照して、本発明の実施の形態１にかかるノード及びネットワークスイッチの接続関係について説明する。図２は、本発明の実施の形態１にかかるノード及びネットワークスイッチの接続関係を示す図である。なお、図２では、ノード２ｃ〜２ｅ、３ｂ、４ｂの図示は省略している。
【００３９】
複数のネットワークスイッチ１０のそれぞれは、ネットワーク上に２次元配列状に配置される。この場合、１つのネットワークスイッチ１０には、最大で４つのネットワークスイッチが接続されることになる。また、１つのネットワークスイッチ１０には、１つのノードが接続される。例えば、処理要素ノード２ａからI/Oノード３ａにパケットを送信する場合、２つのネットワークスイッチ１０を介してパケットが転送される。
【００４０】
ネットワークスイッチの接続関係は図２の２次元配列状には限定されない。これ以外のツリー状、トーラス状、スター状等任意のトポロジとしてもよい。その場合、ネットワークスイッチにはトポロジに応じた数のネットワークスイッチが接続されることになる。
【００４１】
続いて、図３を参照して、本発明の実施の形態１にかかるパケットの構成について説明する。図３は、本発明の実施の形態１にかかるパケットの構成を示す図である。
【００４２】
パケットは、Dst.IDフィールド、Src.IDフィールド、Lengフィールド、Typeフィールド、Priorityフィールド、及びPayloadフィールドを含む。本実施の形態１では、パケットの種類として、ノーマルパケットとリアルタイムパケットの２種類がある。Dst.IDフィールド、Src.IDフィールド、及びLengフィールドは、パケットの種類のよらず共通である。Dst.ID、Src.ID、Leng、Type、Priorityの各フィールドを含む部分をパケットのヘッダと呼ぶ。
【００４３】
ayload時間内にメモリノードに到達している必要がある。例え  Dst.IDフィールドは、パケットの送り先のノードを示すＩＤが格納される。
Src.IDフィールドは、パケットの送り元のノードを示すＩＤが格納される。
Lengは、パケット長を示す値が格納される。
【００４４】
Typeフィールドは、パケットがノーマルパケットかリアルタイムパケットかを示す指定値が格納される。リアルタイムパケットは、ノーマルパケットより常に優先度が高い。つまり、リアルタイムパケットは、ノーマルパケットより優先的に転送される。ノーマルパケットの指定値Type Nと、リアルタイムパケットの指定値Type RTとの関係は、
Type N > Type RT
となる。したがって、Typeフィールドの指定値の比較した結果、指定値の小さいパケットを転送することで、リアルタイムパケットを優先的に転送することができる。また、リアルタイムパケット同士の関係においても、異なる指定値を設定するようにして、優先度付けを行うようにしてもよい。ノーマルパケット同士の関係においても同様である。
【００４５】
Priorityフィールドは、パケットの優先度を示す値が格納される。同じ種類のパケット同士では、Priorityフィールドの値が小さいパケット程、より優先的に転送される。リアルタイムパケットでは、パケットが送信先のノードに到着すべき時刻までの余裕時間(マージン)がPriorityフィールドに設定される。ノーマルパケットでは、余裕時間と関係なく、単純に優先度付けのための値を任意にPriorityフィールドに設定するようにしてよい。
【００４６】
Payloadフィールドは、パケットで伝送すべき情報の本体が格納される。このフィールドは、可変長であり、Lengフィールドの値に依存して長さが変化する。
【００４７】
続いて、図４を参照して、本発明の実施の形態１にかかるネットワークスイッチ１０の構成について説明する。図４は、本発明の実施の形態１にかかるネットワークスイッチ１０の構成図である。図２に示すように、２次元配列状のトポロジを有するネットワークの場合、ネットワークスイッチは、５×５の構成が一般的であるが、図３では、４×４の構成である場合について例示している。なお、４×４のネットワークスイッチと言った場合、４つの入力ポートと４つの出力ポートとを有するネットワークスイッチのことである。なお、ネットワークスイッチのポート数は、これに限られない。入力ポート数及び出力ポート数を任意の数としたＮ×Ｎのネットワークスイッチに拡張することができることは自明である。ここで、Ｎは、２以上の正整数である。
【００４８】
ネットワークスイッチ１０は、入力制御部（Input Control）１１ａ〜１１ｄ、パケットバッファ（PKT_Buf）１２ａ〜１２ｈ、TickGen部１３、出力制御部１４ａ〜１４ｄを有する。ネットワークスイッチ１０は、パケット転送装置に対応する。
【００４９】
ネットワークスイッチの入力ポート（Input Port）は、隣接するネットワークスイッチの出力ポート、又は、そのネットワークスイッチと接続されるノードの出力ポートに接続される。ネットワークスイッチの出力ポート（Output Port）は、隣接するネットワークスイッチの入力ポート、又は、そのネットワークスイッチと接続されるノードの入力ポートに接続される。ここで、ネットワークスイッチに隣接するネットワークスイッチとは、ネットワークスイッチと接続されたネットワークスイッチのことになる。
【００５０】
入力制御部１１ａ〜１１ｄのそれぞれは、入力ポートから入力されるパケットの入力制御を行う。具体的には、入力制御部１１ａは、入力ポート１（Input Port１）から入力されるパケットの入力制御を行い、入力制御部１１ｂは、入力ポート２（Input Port２）から入力されるパケットの入力制御を行い、入力制御部１１ｃは、入力ポート３（Input Port３）から入力されるパケットの入力制御を行い、入力制御部１１ｄは、入力ポート４（Input Port４）から入力されるパケットの入力制御を行う。
【００５１】
入力制御部１１ａ〜１１ｄのそれぞれは、入力制御対象の入力ポートにパケットが到着したとき、自身に接続されているパケットバッファに空きがある場合、その空いているパケットバッファのいずれかに、到着したパケットを格納する。ここで、入力制御部１１ａは、パケットバッファ１２ａ、１２ｂに接続されており、入力制御部１１ｂは、パケットバッファ１２ｃ、１２ｄに接続されており、入力制御部１１ｃは、パケットバッファ１２ｅ、１２ｆに接続されており、入力制御部１１ｄは、パケットバッファ１２ｇ、１２ｈに接続されている。
【００５２】
なお、入力制御部１１ａ〜１１ｄのそれぞれは、空きがあるパケットバッファがない場合は、パケットは受け付けない。つまり、入力制御部１１ａ〜１１ｄのそれぞれは、入力ポートの先のノード又はネットワークスイッチからパケットを受信してパケットバッファに格納しないようにする。この場合、そのパケットは、入力ポートの先のノード又はネットワークスイッチで保持されたままとなる。つまり、入力ポートにパケットが到着したときとは、その入力ポートを制御対象とする入力制御部がパケットを受け付け可能であり、かつ、その入力ポートの先に接続されているノード又はネットワークスイッチからのパケットが送信可能となっているときのことである。なお、ネットワークスイッチが、接続されているノード又はネットワークスイッチがパケットを送信可能となっていることを検出する方法はどのように実現してもよい。例えば、その旨を示す信号をノード又はネットワークスイッチから受信することで検出するようにしてもよい。この信号は、後述の転送要求として機能する。
【００５３】
パケットバッファ１２ａ〜１２ｈのそれぞれは、自身に接続されている入力制御部からパケットが格納される。パケットバッファ１２ａ〜１２ｈのそれぞれは、最大のパケット長のパケットを格納できるだけの容量を有する。ここでは、１つのパケットバッファに１つのパケットを格納することができるものとする。なお、図４では、１つの入力ポートに、２つのパケットバッファが接続されている場合について例示しているが、これに限られない。例えば、１つの入力ポートに３つ以上のパケットバッファが接続されるようにしてもよい。パケットバッファには、パケットのヘッダが特定の場所（パケットバッファのヘッダ部）に格納される。図４では、ヘッダのTypeフィールド及びPriorityフィールドが格納されている場所を、「Pri」として図示している（以下、「Pri部」とする）。
【００５４】
パケットバッファ１２ａ〜１２ｈのそれぞれは、自身に格納されるパケットがリアルタイムパケットである場合、一定時間毎にPriorityフィールドの値をディクリメントする。なお、パケットバッファ１２ａ〜１２ｈのそれぞれは、Priorityフィールドの余裕時間が０になった場合、それ以上ディクリメントは行わず、Priorityフィールドの値を０に固定したままとする。パケットバッファ１２ａ〜１２ｈのそれぞれは、例えば、パケットを格納するためのメモリ又はレジスタ等を含む。パケットバッファ１２ａ〜１２ｈは、パケット記憶部に対応する。
【００５５】
TickGen部１３は、一定時間毎に信号を生成してパケットバッファ１３ａ〜１３ｈのそれぞれに出力する。この信号は、パケットバッファ１３ａ〜１３ｈのそれぞれに同時に入力される。この信号は、パケットバッファ１２ａ〜１２ｈのそれぞれがPriorityフィールドの余裕時間をディクリメントするトリガとなる信号である。好ましくは、この信号の発生間隔は、ネットワーク全体で共通にするとよい。本実施の形態１では、この信号がパルスである場合について例示する。TickGen部１３は、グローバルタイマ６から出力された絶対時刻情報が示す絶対時刻の最小時間間隔毎、又は、最小時間間隔を分周した時間間隔毎に、パルスを発生するようにする。一方で、システム全体で絶対時刻を共有しない場合、TickGen部１３は、予め設定しておいた時間間隔(例えば1ｍ秒、1μ秒)毎にパルスを発生するようにする。
【００５６】
よって、ノードが設定する余裕時間の単位と、TickGen部１３がパルスを発生する時間間隔とは一致させておく必要がある。例えば、ノードが１μｓｅｃ単位で余裕時間を設定した場合、TickGen部１３は、１μｓｅｃ毎にパルスを発生するようにする。そのようにすることで、１μｓｅｃ経過する毎に、パケットバッファで余裕時間の１μｓｅｃ毎のディクリメントが行われるようになる。
【００５７】
出力制御部１４ａ〜１４ｄのそれぞれは、出力ポートに出力されるパケットの出力制御を行う。具体的には、出力制御部１４ａは、出力ポート１（Output Port１）に出力されるパケットの出力制御を行い、出力制御部１４ｂは、出力ポート２（Output Port２）に出力されるパケットの出力制御を行い、出力制御部１４ｃは、出力ポート３（Output Port３）に出力されるパケットの出力制御を行い、出力制御部１４ｄは、出力ポート４（Output Port４）に出力されるパケットの出力制御を行う。
【００５８】
出力制御部１４ａ〜１４ｄのそれぞれは、全てのパケットバッファ１２ａ〜１２ｈに格納されているヘッダを参照することができる。出力制御部１４ａ〜１４ｄのそれぞれは、パケットバッファ１２ａ〜１２ｈに格納されているパケットのDst. IDフィールドの送り先のノードのＩＤを参照して、そのパケットを出力する出力ポートが自身の出力制御対象の出力ポートであるかどうか判定する。この判定は、例えば、送り先と、出力ポートとが対応付けられたルーティング表を参照して行うようにする。ネットワークスイッチ１０は、例えば、ルーティング表が格納された記憶装置（図示せず）を有する。記憶装置は、例えば、レジスタ又はメモリ等である。
【００５９】
同じ出力ポートへの転送が必要なパケットがパケットバッファに複数存在する場合、出力制御部１４ａ〜１４ｄのそれぞれは、それらのパケットバッファのPri部を参照して、Pri部の値(Typeフィールドの値及びPriorityフィールドの値)に基づいて、優先度が最も高いパケットを優先して出力ポートに出力する。
【００６０】
この動作によって、優先度の高いパケットによる、優先度の低いパケットの追い越しが可能となる。例えば、入力ポート１から優先度の低いパケットが到着しパケットバッファ１２ａに格納され、その後、同じ入力ポート１から優先度の高いパケットが到着して他の空いているパケットバッファ１２ｂに格納される場合について考える。これは、パケットバッファ１２ａに格納された優先度の低いパケットが、他の入力ポート（入力ポート２〜４のいずれか）から到着した優先度の高いパケットの転送のために待たされたときに発生する可能性がある。そのときに、後から到着してパケットバッファ１２ｂに格納されたパケットが、パケットバッファ１２ａに格納されたパケットより優先度が高い場合、パケットバッファ１２ａに格納されている優先度の低いパケットを追い越して先に転送される。このように１つの入力ポートに対して、複数のパケットバッファを設けることにより、パケットの追い越しが可能となる。出力制御部１４ａ〜１４ｄは、転送制御部に対応する。
【００６１】
続いて、図５を参照して、本発明の実施の形態１にかかるパケットバッファのヘッダ部１２０の構成について説明する。図５は、本発明の実施の形態１にかかるパケットバッファのヘッダ部１２０の構成図である。
【００６２】
パケットバッファのヘッダ部１２０は、AND演算回路１２１、Priority比較回路１２２、及びType比較回路１２３を有する。パケットバッファのヘッダ部１２０は、パケットバッファに格納されたパケットのヘッダのTypeフィールドの値及びPriorityフィールドの値に応じて、Priorityフィールドを更新する。
【００６３】
AND演算回路１２１は、TickGen部１３から出力されたパルスと、Priority比較回路１２２から出力された信号と、Type比較回路１２３から出力された信号をAND演算する。AND演算回路１２１は、AND演算結果をパケットバッファのPri部に出力する。パケットバッファは、AND演算回路１２１からAND演算結果としてアクティブな信号がPri部に出力されたときに、それに応じてPriorityフィールドの値をディクリメントする。
【００６４】
Priority比較回路１２２は、パケットバッファに格納されるパケットのPriorityフィールドの値と、０の値とを比較する。例えば、０の値は、Priority比較回路１２２が有する記憶装置（図示せず）に予め格納しておくことで参照可能とする。Priority比較回路１２２は、Priorityフィールドの値が０でない場合、アクティブな信号をAND演算回路１２１に出力し、Priorityフィールドの値が０である場合、インアクティブな信号をAND演算回路１２１に出力する。例えば、アクティブは、１であり、インアクティブは、０である。
【００６５】
Type比較回路１２３は、パケットバッファに格納されるパケットのTypeフィールドの値と、リアルタイムパケットの指定値とを比較する。例えば、リアルタイムパケットの指定値は、Type比較回路１２３が有する記憶装置（図示せず）に予め格納しておくことで参照可能とする。Type比較回路１２３は、Typeフィールドの値が、リアルタイムパケット（ＲＴ）を示す場合、アクティブな信号をAND演算回路１２１に出力し、Typeフィールドの値が、リアルタイムパケット以外を示す場合、インアクティブな信号をAND演算回路１２１に出力する。Typeフィールドの値がリアルタイムパケット以外を示す場合とは、例えば、Typeフィールドの値がノーマルパケットの指定値を示す場合である。
【００６６】
以上に説明したパケットバッファのヘッダ部１２０の構成によって、Typeフィールドの値がリアルタイムパケットの指定値を示し、かつPriorityフィールドの値が０でない場合に、TickGen部１３からパルスが出力されたとき、AND演算回路１２１は、アクティブな信号をPri部に出力することになる。つまり、TickGen部１３から出力されるパルスとは、一定期間の間、０から１となる幅を有するパルスのことである。これによって、Priorityフィールドの値がディクリメントされる。つまり、パケットバッファのヘッダ部１２０は、TickGen部１３からPri部にアクティブな信号が出力されたときに、Priorityフィールドの値をディクリメントする。
【００６７】
続いて、図６を参照して、本発明の実施の形態１にかかるネットワークスイッチ１０の処理について説明する。図６は、本発明の実施の形態１にかかるネットワークスイッチ１０の処理を示すフローチャートである。入力制御部１１ａ〜１１ｄ、出力制御部１４ａ〜１４ｄはそれぞれ独立に動作する。図６Ａは入力制御部１１ａ〜１１ｄ、図６Ｂは出力制御部１４ａ〜１４ｄの処理を示すフローチャートである。ここでは、入力制御部１１ａ及び出力制御部１４ａにおける処理を例に挙げて説明するが、入力制御部１１ｂ〜１１ｄ及び出力制御部１４ｂ〜１４ｄにおける処理についても同様であるため、説明を省略する。
【００６８】
入力制御部１１ａはパケットバッファ１２ａ、１２ｂのいずれにも空きがない場合（Ｓ１：Ｎｏ）は、パケットバッファ１２ａ、１２ｂのいずれかに空きができるまで待ち合わせる。この間、入力ポート１に接続されている隣接するネットワークスイッチの出力ポート、又は、入力ポート１に接続されるノードの出力ポートからのパケットの転送要求は受け付けられず待たされる。パケットバッファ１２ａ、１２ｂのいずれかに空きができると（Ｓ１：Ｙｅｓ）、入力ポート１に接続されている隣接するネットワークスイッチの出力ポート、又は、入力ポート１に接続されるノードの出力ポートからのパケットの転送要求は受付可能な状態となる。
【００６９】
入力制御部１１ａは、入力ポート１にパケットが到着するまで待ち合わせる（Ｓ２：Ｎｏ）。なお、パケットの到着とは、入力制御部１１ａが、ネットワークスイッチの出力ポート、又は、ノードの出力ポートからのパケットの転送要求を受付可能な状態としているときに、そのネットワークスイッチ又はそのノードからパケットの転送要求を受けることである。
【００７０】
入力ポート１にパケットが到着すると（Ｓ２：Ｙｅｓ）、入力制御部１１ａは、入力ポート１に到着したパケットを受信して、受信したパケットをパケットバッファ１２ａ、１２ｂのいずれか空いているパケットバッファに格納する（Ｓ３）。
【００７１】
他方、出力制御部１４ａは、パケットバッファ１２ａ〜１２ｈに格納されたパケットのDst. IDフィールドの送り先のノードのＩＤを参照して、パケットバッファ１２ａ〜１２ｈに出力ポート１に出力するパケットが格納されているか否かを確認する（Ｓ４）。
【００７２】
パケットバッファ１２ａ〜１２ｈにパケットが格納されていない場合（Ｓ４：Ｎｏ）、出力制御部１４ａは、そのようなパケットが、パケットバッファ１２ａ〜１２ｈのいずれかに格納されるまで待ち合わせる。
【００７３】
パケットバッファ１２ａ〜１２ｈの少なくとも１つにパケットが格納されていた場合、又は、待ち合わせの結果、パケットバッファ１２ａ〜１２ｈの少なくとも１つにパケットが格納された場合（Ｓ４：Ｙｅｓ）、出力制御部１４ａは、それらのパケットのTypeフィールドの値及びPriorityフィールドの値を参照して、それらのパケットの中で最も優先度の高いパケットを判定する（Ｓ５）。出力制御部１４ａは、最も優先度が高いと判定したパケットを出力ポート１から出力する（Ｓ６）。つまり、出力制御部１４ａは、最も優先度が高いと判定したパケットを、出力ポート１の先に接続されているノード又はネットワークスイッチに転送する。
【００７４】
以上に説明したように、本実施の形態１では、パケットの優先度として送達時刻までの余裕時間(マージン)をパケットのPriorityフィールドに格納するようにしている。これにより、単純にディクリメントすることができる値として、優先度を格納することができる。そのため、少ないビット数で優先度を設定することができ、かつ優先度に応じたパケットの転送制御にかかる処理を単純にすることができる。例えば、パケットに送達時刻を持ち、その送達時刻と現在時刻との比較することによって、その都度、余裕時間を算出して優先度制御を行うネットワークスイッチと比較して、処理を単純にすることができる。また、実時間である送達時刻と比較して、ビット数を少なくすることができる。
【００７５】
また、本実施の形態１では、ネットワークスイッチのパケットバッファにパケットが滞留している時間に応じて、パケットのPriorityフィールドの値をディクリメントするようにしている。つまり、パケットが滞留している時間に応じて、優先度を高くするようにしている。これによれば、滞留時間が長いパケットの優先度を高くして、より優先的に転送することができる。そのため、ネットワークにおけるパケットの転送状況に応じて、実時間性を保証したパケット転送を行うことができる。
【００７６】
また、本実施の形態１では、出力制御部が、複数のパケットバッファに格納されるパケットのうち、優先度の最も高いパケットを選択して出力する構成としている。そのため、特許文献１に開示の技術のように、パケットをソートするといった複雑な処理を行うための機構を実行する必要が無い。
【００７７】
また、本実施の形態１では、複数のパケットバッファが、所定のタイミングで複数のパケットバッファに同時に入力されるパルスに応じて、パケットバッファに格納されたパケットが有する余裕時間が少なくなるように余裕時間を更新するようにしている。したがって、本実施の形態１によれば、複数のパケットバッファのそれぞれに格納された余裕時間を同期して更新することができる。つまり、複数の転送待ちのパケットが有する、パケットの転送に使用される情報を更新する場合に、全てのパケットの情報を時間をかけることなく更新することができる。
【００７８】
また、このように、本実施の形態１では、複数の転送待ちのパケットが有する、パケットの転送に使用される情報の更新に時間がかかることがない。そのため、半導体チップ上に構成されたNoCのように、高速動作を行うハードウェアでの実装を前提としたネットワーク環境に適用すれば特に有効である。
【００７９】
本発明の実施の形態２．
続いて、図７を参照して、本発明の実施の形態２にかかるネットワークスイッチ２０について説明する。図７は、本発明の実施の形態２にかかるネットワークスイッチ２０の構成図である。図７では、ネットワークスイッチ２０が、２×２の構成である場合について例示している。なお、入力ポート数及び出力ポート数を任意の数としたＮ×Ｎのネットワークスイッチに拡張することができることは自明である。なお、説明の明確化のため、実施の形態１と同様の内容については、適宜説明を省略する。
【００８０】
ネットワークスイッチ２０は、入力制御部（Input Control）２１ａ、２１ｂ、ヘッダバッファ（HDR_Buf）２２ａ、２２ｂ、DeMux部２３ａ、２３ｂ、パケットバッファ（PKT_Buf）２４ａ〜２４ｈ、TickGen部２５、Arbiter部２６ａ、２６ｂ、及びMux部２７ａ、２７ｂを有する。
【００８１】
入力制御部２１ａ、２１ｂのそれぞれは、入力ポートから入力されるパケットの入力制御を行う。具体的には、入力制御部２１ａは、入力ポート１（Input Port１）から入力されるパケットの入力制御を行い、入力制御部２１ｂは、入力ポート２（Input Port２）から入力されるパケットの入力制御を行う。入力制御部２１ａ、２１ｂのそれぞれは、自身に接続されているヘッダバッファに空きがあるときに、入力制御対象の入力ポートにパケットが到着した場合、到着したパケットのヘッダのみを格納する。つまり、入力制御部２１ａ、２１ｂのそれぞれは、その入力ポートの先のノード又はネットワークスイッチから、パケットのヘッダのみを受信してヘッダバッファに格納する。パケットのヘッダ以外の部分の転送は待たされることになる。ヘッダバッファに空きがない場合はパケットの転送は待たされる。ここで、入力制御部２１ａには、ヘッダバッファ２２ａが接続されており、入力制御部２１ｂには、ヘッダバッファ２２ｂが接続されている。
【００８２】
ヘッダバッファ２２ａ、２２ｂのそれぞれは、パケットのヘッダを格納するためのバッファである。ヘッダバッファ２２ａ、２２ｂのそれぞれは、実施の形態１にかかるパケットバッファと同様に、一定時間毎にPriorityフィールドの値をディクリメントする。なお、ヘッダバッファ２２ａ、２２ｂのそれぞれは、実施の形態１にかかるパケットバッファのヘッダ部１２０のみから構成されることになる。
【００８３】
入力制御部２１ａ、２１ｂのそれぞれに対応してDeMux部２３ａ、２３ｂが接続されている。入力制御部２１ａは、DeMux部２３ａと対応し、入力制御部２１ｂは、DeMux部２３ｂと対応する。またDeMux部２３ａは、ヘッダバッファ２２ａと接続されており、DeMux部２３ｂは、ヘッダバッファ２２ｂと接続されている。DeMux部２３ａ、２３ｂのそれぞれは、自身に接続されるヘッダバッファに格納されたヘッダに含まれるDst. IDフィールドの送り先のノードのＩＤを参照して、そのヘッダを含むパケットを出力する出力ポートを判定する。
【００８４】
出力先の出力ポートに対応するパケットバッファのいずれかに空きがある場合、DeMux部２３ａはヘッダバッファ２２ａのヘッダを空いているパケットバッファに転送する。具体的には、DeMux部２３ａは、出力先が出力ポート１である場合、パケットバッファ２４ａ、２４ｂのいずれかが空いているかどうかを確認し、空いているパケットバッファ２４ａ、２４ｂのいずれかにヘッダを転送する。出力先が出力ポート２である場合に関しても転送先のパケットバッファをパケットバッファ２４ｅ、２４ｆとして同様の動作を行う。DeMux部２３ａはヘッダをパケットバッファに転送するとともにヘッダバッファを空の状態にする。
【００８５】
入力制御部２１ａはヘッダバッファが空になると、待たされていたパケットのヘッダ以外の部分も順次ヘッダバッファ２２ａに出力する。DeMux部２３ａは入力制御部２１ａから順次出力されるパケットのヘッダ以外の部分を入力制御部２１ａと同期してヘッダバッファ２２ａから取り出し、先にヘッダを出力したパケットバッファに転送する。
【００８６】
以上によって、パケット全体がヘッダバッファ２２ａ、DeMux部２３ａを介して所定のパケットバッファに出力される。なお、入力制御部２１ｂ、ヘッダバッファ２２ｂ、DeMux部２３ｂ、およびパケットバッファ２４ｃ、２４ｄ、２４ｇ、２４ｈに関する動作についても、上述した動作と同様であるため説明を省略する。
【００８７】
DeMux部２３ａ、２３ｂのそれぞれは、パケットを出力する出力ポートの判定が終了したときに、入力制御部からヘッダバッファを介して出力されたパケットを、そのパケットの出力先の出力ポートとして判定した出力ポートに対応するパケットバッファに空きがあるかどうか確認し、空きがあれば格納する。具体的には、DeMux部２３ａは、出力先が出力ポート１である場合、パケットバッファ２４ａ、２４ｂのいずれかにパケットを格納し、出力先が出力ポート２である場合、パケットバッファ２４ｅ、２４ｆのいずれかにパケットを格納する。また、DeMux部２３ｂは、出力先が出力ポート１である場合、パケットバッファ２４ｃ、２４ｄのいずれかにパケットを格納し、出力先が出力ポート２である場合、パケットバッファ２４ｇ、２４ｈのいずれかにパケットを格納する。
【００８８】
パケットバッファ２４ａ〜２４ｈのそれぞれは、実施の形態１にかかるパケットバッファと同様にパケットが格納され、一定時間毎にPriorityフィールドの値をディクリメントする。なお、本実施の形態２においても、実施の形態１と同様に、１つの入力ポートと１つの出力ポートとの間に最低で２つのパケットバッファを設けるようにすることで、優先度の異なる２つのパケットが同じルートを辿った場合に、優先度の高いパケットが、優先度の低いパケットを追い越せるようにしている。なお、パケットバッファ数は、多い程、追い越しの可能性が高くなる。本実施の形態２では、１つの出力ポートに対して、入力ポート毎に２つのパケットバッファを有するようにしているため、１つの出力ポートに対して合計４つのパケットバッファを有することになる。
【００８９】
TickGen部２５は、実施の形態１と同様に、一定時間毎にパルスをパケットバッファ２４ａ〜２４ｈのそれぞれに出力する。本実施の形態２では、TickGen部２５は、このパルスを、さらにヘッダバッファ２２ａ、２２ｂにも出力する。このパルスは、ヘッダバッファ２２ａ、２２ｂ及びパケットバッファ２４ａ〜２４ｈのそれぞれに同時に入力される。
【００９０】
本実施の形態２では、Arbiter部及びMux部によって、出力ポートに出力されるパケットの出力制御が行われる。つまり、本実施の形態２にかかるArbiter部及びMux部の組み合わせは、実施の形態１にかかる出力制御部に対応する。具体的には、Arbiter部２６ａ及びMux部２７ａは、出力ポート１（Output Port１）に出力されるパケットの出力制御を行い、Arbiter部２６ｂ及びMux部２７ｂは、出力ポート２（Output Port２）に出力されるパケットの出力制御を行う。
【００９１】
ただし、本実施の形態２では、DeMux部によって出力ポートに対するパケットの振り分けが行われることになるため、Arbiter部及びMux部では、パケットの優先度に応じた出力制御のみが行われることになる。
【００９２】
Arbiter部２６ａ、２６ｂのそれぞれは、自身の出力制御対象の出力ポートに対して振り分けられたパケットが格納されるパケットバッファのPri部の値に基づいて、最も優先度の高いパケットを判定する。具体的には、Arbiter部２６ａは、パケットバッファ２４ａ〜２４ｄのPri部の値に基づいて、パケットバッファ２４ａ〜２４ｄに格納されたパケットのうち、最も優先度の高いパケットを判定する。また、Arbiter部２６ｂは、パケットバッファ２４ｅ〜２４ｈのPri部の値に基づいて、パケットバッファ２４ｅ〜２４ｈに格納されたパケットのうち、最も優先度の高いパケットを判定する。
【００９３】
Arbiter部２６ａ、２６ｂのそれぞれは、最も優先度の高いパケットを格納するパケットバッファの選択を指示する選択信号をMux部２７ａ、２７ｂのそれぞれに出力する。具体的には、Arbiter部２６ａは、パケットバッファ２４ａ〜２４ｄのうちのいずれかのパケットバッファの選択を指示する選択信号をMux部２７ａに出力し、Arbiter部２６ｂは、パケットバッファ２４ｅ〜２４ｈのうちのいずれかのパケットバッファの選択を指示する選択信号をMux部２７ｂに出力する。
【００９４】
Mux部２７ａ、２７ｂのそれぞれは、Arbiter部２６ａ、２６ｂのそれぞれから出力された選択信号によって指示されたパケットバッファを選択する。Mux部２７ａ、２７ｂのそれぞれは、選択したパケットバッファに格納されたパケットを出力ポートから出力する。具体的には、Mux部２７ａは、出力ポート１からパケットを出力し、Mux部２７ｂは、出力ポート２からパケットを出力する。
【００９５】
続いて、図８を参照して、本発明の実施の形態２にかかるネットワークスイッチ２０の処理について説明する。図８は、本発明の実施の形態２にかかるネットワークスイッチ２０の処理を示すフローチャートである。ここでは、入力制御部２１ａ、DeMux部２３ａ、Arbiter部２６ａ及びMux部２７ａにおける処理を例に挙げて説明するが、入力制御部２１ｂ、DeMux部２３ｂ、Arbiter部２６ｂ及びMux部２７ｂにおける処理についても同様であるため、説明を省略する。
【００９６】
入力制御部２１ａとDeMux部２３ａは一体として動作する、またArbiter部２６ａとMux部２７ａは一体として動作する。入力制御部２１ａ、DeMux部２３ａとArbiter部２６ａ、Mux部２７ａは独立に動作する。図８Ａは入力制御部２１ａとDeMux部２３ａの処理を示すフローチャートである。図８ＢはArbiter部２６ａとMux部２７ａの処理を示すフローチャートである。
【００９７】
入力制御部２１ａは、ヘッダバッファ２２ａに空きがない場合（Ｓ１１：Ｎｏ）は、ヘッダバッファ２２ａに空きができるまで待ち合わせる。この間、入力ポート１に接続されている隣接するネットワークスイッチの出力ポート、又は、入力ポート１に接続されるノードの出力ポートからのパケットの転送要求は受け付けられず待たされる。ヘッダバッファ２２ａに空きができると（Ｓ１１：Ｙｅｓ）、入力ポート１に接続されている隣接するネットワークスイッチの出力ポート、又は、入力ポート１に接続されるノードの出力ポートからのパケットの転送要求は受付可能な状態となる。
【００９８】
入力制御部２１ａは、入力ポート１にパケットが到着するまで待ち合わせる（Ｓ１２：Ｎｏ）。入力ポート１にパケットが到着したとき（Ｓ１２：Ｙｅｓ）、入力制御部２１ａは、到着したパケットのヘッダのみを受信して、ヘッダバッファ２２ａに格納する（Ｓ１３）。ヘッダ以外の部分の転送は待たされる。
【００９９】
DeMux部２３ａは、自身に接続されるヘッダバッファ２２ａに格納されたヘッダに含まれるDst. IDフィールドの送り先のノードのＩＤを参照して、そのヘッダを含むパケットを出力する出力ポートを判定する（Ｓ１４）。以下では、判定された出力ポートが出力ポート１の場合について説明する。判定された出力ポートが出力ポート２の場合も同様である。DeMux部２３ａは、判定した出力ポート１に対応するパケットバッファ２４ａ、２４ｂのいずれかに空きがあるか否かを判定する（Ｓ１５）。
【０１００】
パケットバッファ２４ａ、２４ｂのいずれにも空きがない場合（Ｓ１５：Ｎｏ）、DeMux部２３ａは、パケットバッファ２４ａ、２４ｂのいずれかに空きができるまで待ち合わせる。
【０１０１】
パケットバッファ２４ａ、２４ｂのいずれかに空きがある場合（Ｓ１５：Ｙｅｓ）、DeMux部２３ａは、ヘッダバッファ２２ａに格納されたヘッダと、それ以外の部分も含んだパケット全体を、空いているパケットバッファに格納する（Ｓ１６）。このとき、入力制御部２１ａは入力ポート１からパケットのヘッダ以外の部分をヘッダバッファ２２ａを介してDeMux部２３ａに順次転送する。
【０１０２】
他方、Arbiter部２６ａは、パケットバッファ２４ａ〜２４ｄにパケットが格納されているかどうか確認し（Ｓ１７）、もしなければ（Ｓ１７：Ｎｏ）いずれかのパケットバッファにパケットが格納されるまで待ち合わせる。
【０１０３】
Arbiter部２６ａは、パケットバッファ２４ａ〜２４ｄの少なくとも１つにパケットが格納されていた場合、又は、待ち合わせの結果、パケットバッファ２４ａ〜２４ｄの少なくとも１つにパケットが格納された場合（Ｓ１７：Ｙｅｓ）、パケットバッファ２４ａ〜２４ｄに格納されたパケットのTypeフィールドの値及びPriorityフィールドの値を参照して、それらのパケットの中で最も優先度の高いパケットを判定する（Ｓ１８）。Mux部２７ｂは、最も優先度が高いと判定したパケットを出力ポート１に出力する（Ｓ１９）。つまり、Mux部２７ｂは、最も優先度が高いと判定したパケットを出力ポート１の先に接続されているノード又はネットワークスイッチに転送する。
【０１０４】
以上に説明したように、本実施の形態２では、DeMux部によって、パケットを転送する出力ポートの判定を行って、出力ポートに対するパケットの振り分けを行った後に、Arbiter部によって優先度の判定を行うようにしている。つまり、複数のパケットバッファに格納されたパケットを参照して、出力ポートに出力するパケットを判定するときに、優先度の判定に関係する情報のみを参照すればよい。そのため、出力制御における機構を簡略化することができ、スイッチの入出力ポート数が増加した場合も、より少ないハードウェアでネットワークスイッチが実現可能となる。
【０１０５】
ここで、図９を参照して、具体的に比較対象を挙げて説明する。図９は、比較検証を明確にするために、実施の形態１にかかる４×４のネットワークスイッチを、実施の形態２と同様のポート数である２×２のネットワークスイッチに変更した構成について例示している。
【０１０６】
図９に示すネットワークスイッチは、出力制御部が、４つのパケットバッファに格納される、４つのDst.IDフィールドの値、４つのTypeフィールドの値、及び４つのPriorityフィールドの値を参照する必要がある。それに対して、本実施の形態２では、DeMux部が１つのヘッダバッファに格納される１つのDst.IDフィールドの値を参照し、Arbiter部が４つのパケットバッファに格納される、４つのTypeフィールドの値、及び４つのPriorityフィールドの値を参照すればよい。そのため、単純に、参照する情報の数を比較したたけでも、３つ分のDst.IDフィールドの値を参照する必要がなくなる。
【０１０７】
本発明の実施の形態３．
続いて、図１０を参照して、本発明の実施の形態３にかかるネットワークスイッチ３０について説明する。図１０は、本発明の実施の形態３にかかるネットワークスイッチ３０の構成図である。本発明の実施の形態３にかかるネットワークスイッチ３０は、実施の形態１にかかるネットワークスイッチ１０の出力制御部の構成をより詳細に示したものである。ただし、図１０では、説明の明確化のため、ネットワークスイッチ３０が、２×２の構成である場合について例示している。なお、入力ポート数及び出力ポート数を任意の数としたＮ×Ｎのネットワークスイッチに拡張することができることは自明である。なお、説明の明確化のため、実施の形態１と同様の内容については、適宜説明を省略する。
【０１０８】
ネットワークスイッチ３０は、入力制御部（Input Control）３１ａ、３１ｂ、パケットバッファ（PKT_Buf）３２ａ〜３２ｄ、TickGen部３３、出力判定制御部（I/O_CTRL）３４ａ、３４ｂ、Arbiter部３５ａ、３５ｂ、及びMux部３６ａ、３６ｂを有する。
【０１０９】
本実施の形態３にかかる入力制御部３１ａ、３１ｂの動作は、実施の形態１にかかる１１ａ〜１１ｄと同様であるため、説明を省略する。ただし、本実施の形態３では、入力制御部３１ａが、入力ポート１（Input Port１）から入力されるパケットをパケットバッファ３２ａ、３２ｂのいずれかに格納し、入力制御部３１ｂが、入力ポート２（Input Port２）から入力されるパケットをパケットバッファ３２ｃ、３２ｄのいずれかに格納する。また、本実施の形態３にかかるパケットバッファ３２ａ〜３２ｄの動作についても、実施の形態１にかかるパケットバッファ１２ａ〜１２ｈと同様であるため、説明を省略する。
【０１１０】
また、本実施の形態３にかかるTickGen部３３の動作についても、実施の形態１にかかるTickGen部１３と同様であるため、説明を省略する。ただし、TickGen部３３は、信号をパケットバッファ３２ａ〜３２ｄのそれぞれに同時に入力されるように出力することになる。
【０１１１】
本実施の形態３では、出力判定制御部、Arbiter部、及びMux部によって、出力ポートに出力されるパケットの出力制御が行われる。よって、出力制御部は、出力判定制御部、Arbiter部、及びMux部を含むことになる。具体的には、出力判定制御部３４ａ、３４ｃ、Arbiter部３５ａ、及びMux部３６ａは、出力ポート１（Output Port１）に出力されるパケットの出力制御を行う出力制御部として機能し、出力判定制御部３４ｂ、３４ｄ、Arbiter部３５ｂ、及びMux部３６ｂは、出力ポート２（Output Port２）に出力されるパケットの出力制御を行う出力制御部として機能する。
【０１１２】
図１０に示すように、ネットワークスイッチ３０は、出力ポートのそれぞれに対応する出力判定制御部の組を、入力ポート毎に有している。具体的には、出力ポート１に対応する出力判定制御部３４ａと出力ポート２に対応する出力判定制御部３４ｂとの組を、入力ポート１に対して有し、出力ポート１に対応する出力判定制御部３４ｃと出力ポート２に対応する出力判定制御部３４ｄとの組を、入力ポート２に対して有している。
【０１１３】
出力判定制御部３４ａ〜３４ｄのそれぞれは、パケットバッファに格納されたヘッダに含まれるDst. IDフィールドの送り先のノードのＩＤを参照して、そのパケットを出力する出力ポートが、自身に対応する出力ポートであるか否かを判定する。
【０１１４】
同じ出力ポートへの転送が必要なパケットがパケットバッファに複数存在する場合、出力判定制御部３４ａ〜３４ｄのそれぞれは、それらのパケットバッファのPri部を参照して、Pri部の値(Typeフィールドの値及びPriorityフィールドの値)に基づいて、優先度が最も高いパケットを選択する。出力判定制御部３４ａ〜３４ｄのそれぞれは、選択したパケットの転送要求をArbiter部に出力する。ここで、出力判定制御部３４ａ、３４ｃからの転送要求は、Arbiter部３５ａに出力され、出力判定制御部３４ｂ、３４ｄからの転送要求は、Arbiter部３５ｂに出力される。
【０１１５】
Arbiter部３５ａ、３５ｂのそれぞれは、出力判定制御部から転送要求を受けたパケットの選択を指示する選択信号をMux部３６ａ、３６ｂのそれぞれに出力する。具体的には、Arbiter部３５ａは、出力判定制御部３４ａ、３４ｃのいずれかから転送要求を受けたパケットの選択を指示する選択信号をMux部３６ａに出力し、Arbiter部３５ｂは、出力判定制御部３４ｂ、３４ｄのいずれかから転送要求を受けたパケットの選択を指示する選択信号をMux部３６ｂに出力する。
【０１１６】
ここで、１つのArbiter部は、複数の出力判定制御部からパケットの転送要求を受ける場合がある。具体的には、Arbiter部３５ａは、出力判定制御部３４ａ、３４ｃの両方から転送要求を受ける場合があり、Arbiter部３５ｂは、出力判定制御部３４ｂ、３４ｄの両方から転送要求を受ける場合がある。この場合、転送要求を受けたパケットのうち、最も優先度の高いパケットの選択を指示する選択信号をMux部に出力する。
【０１１７】
ここで、Arbiter部による最も優先度の高いパケットの判定は、どのように行ってもよい。例えば、Arbiter部が判定対象となるパケットが格納されたパケットバッファのPri部を参照することによって判定してもよい。また、出力判定制御部からパケットの転送要求とともに、そのパケットのPri部の値もArbiter部に出力するようにしてもよい。
【０１１８】
Mux部３６ａ、３６ｂのそれぞれは、Arbiter部３５ａ、３５ｂのそれぞれから出力された選択信号によって指示されたパケットバッファを選択する。Mux部３６ａ、３６ｂのそれぞれは、選択したパケットバッファに格納されたパケットを出力ポートから出力する。具体的には、Mux部３６ａは、出力ポート１からパケットを出力し、Mux部３６ｂは、出力ポート２からパケットを出力する。
【０１１９】
以上に説明したように、本実施の形態３では、実施の形態１にかかる出力制御部のより詳細な構成の一例について述べた。しかし、出力制御部の構成は、実施の形態１で述べた動作を実現することができるものであれば、実施の形態３に例示した構成に限られない。
【０１２０】
なお、本発明は、上記の実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
【０１２１】
本実施の形態では、半導体チップ上に構成されたNoCに対して適用した場合について例示したが、これに限られない。例えば、インターネット及びＬＡＮ（Local Area Network）等のネットワーク環境に適用してもよい。
【０１２２】
本実施の形態では、TickGen部を、ネットワークスイッチに有する場合について例示したが、これに限られない。例えば、TickGen部を、マルチコアシステムのうち、ネットワークスイッチの外部のいずれかの場所に有するようにしてもよい。
【０１２３】
本実施の形態２では、DeMux部によるパケットバッファへの振り分け前のパケットのうち、ヘッダのみをヘッダバッファに格納するようにしているが、これに限られない。例えば、ヘッダバッファに代えて、パケット全体が格納されるパケットバッファを有するようにしてもよい。
【符号の説明】
【０１２４】
１        マルチコアシステム
２ａ、２ｂ、２ｃ、２ｄ、２ｅ    処理要素ノード
３ａ、３ｂ    I/Oノード
４ａ、４ｂ    メモリノード
５        通信路
６        グローバルタイマ
１０、２０、３０    ネットワークスイッチ
１１ａ、１１ｂ、１１ｃ、１１ｄ、２１ａ、２１ｂ、３１ａ、３１ｂ    入力制御部
１２ａ、１２ｂ、１２ｃ、１２ｄ、１２ｅ、１２ｆ、１２ｇ、１２ｈ、２４ａ、２４ｂ、２４ｃ、２４ｄ、２４ｅ、２４ｆ、２４ｇ、２４ｈ、３２ａ、３２ｂ、３２ｃ、３２ｄ    パケットバッファ
１３、２５、３３    TickGen部
１４ａ、１４ｂ、１４ｃ、１４ｄ    出力制御部
２２ａ、２２ｂ        ヘッダバッファ
２３ａ、２３ｂ        DeMux部
２６ａ、２６ｂ、３５ａ、３５ｂ    Arbiter部
２７ａ、２７ｂ、３６ａ、３６ｂ    Mux部
３４ａ、３４ｂ、３４ｃ、３４ｄ    出力判定制御部
１２０    ヘッダ部
１２１    AND演算回路
１２２    Priority比較回路
１２３    Type比較回路
【図１】
2013005145.tif 000003
【図２】
2013005145.tif 000004
【図３】
2013005145.tif 000005
【図４】
2013005145.tif 000006
【図５】
2013005145.tif 000007
【図６Ａ】
2013005145.tif 000008
【図６Ｂ】
2013005145.tif 000009
【図７】
2013005145.tif 000010
【図８Ａ】
2013005145.tif 000011
【図８Ｂ】
2013005145.tif 000012
【図９】
2013005145.tif 000013
【図１０】
2013005145.tif 000014