(57)【要約】【課題】処理性能の低下やデッドロックの発生を軽減することを目的とする。【解決手段】複数のデータ処理手段がリング状のバスに接続され、複数のデータ処理手段が、データに含まれる処理順序情報の示す順番が先のデータから順番にデータ処理を行うデータ処理装置であって、バスを流れるパケットを受信する受信手段と、受信手段の受信したパケットに、複数のデータ処理手段の何れかで処理を保留したことを示す保留情報が付加されているか否かを識別する識別手段と、識別手段が識別した保留情報の付加されている保留パケットのデータを取り込んで保持する保持手段と、受信手段が空のパケットを受信した場合に、保持手段の保持しているデータのうち、処理順序情報の示す順序が先のデータを優先してバスに出力する送信手段と、を有することによって課題を解決する。【選択図】図２
2011180838.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータ処理手段がリング状のバスに接続され、前記複数のデータ処理手段が、データに含まれる処理順序情報の示す順番が先のデータから順番にデータ処理を行うデータ処理装置であって、
前記バスを流れるパケットを受信する受信手段と、
前記受信手段の受信したパケットに、前記複数のデータ処理手段の何れかで処理を保留したことを示す保留情報が付加されているか否かを識別する識別手段と、
前記識別手段が識別した前記保留情報の付加されている保留パケットのデータを取り込んで保持する保持手段と、
前記受信手段が空のパケットを受信した場合に、前記保持手段の保持しているデータのうち、前記処理順序情報の示す順序が先のデータを優先して前記バスに出力する送信手段と、
を有することを特徴とするデータ処理装置。
【請求項２】
前記送信手段は、前記保持手段がデータを取り出した保留パケットを空のパケットとして前記バスに出力することを特徴とする請求項１に記載のデータ処理装置。
【請求項３】
前記保持手段に空きがあるか否かを判定し、前記保持手段に空きがある場合に前記受信手段のした保留パケットに含まれるデータを前記保持手段に送信して記憶させる制御手段を更に有することを特徴とする請求項１又は２に記載のデータ処理装置。
【請求項４】
前記制御手段が前記保持手段に空きがないと判定する場合に、前記受信手段の受信した保留パケットの有するデータ及び前記保持手段の有するデータの中で前記処理順序情報の示す順序が先のデータを前記制御手段が前記送信手段から前記バスに出力させることを特徴とする請求項３に記載のデータ処理装置。
【請求項５】
前記受信手段の受信した保留パケットのデータが送信手段へ送信されなかった場合に、当該データを前記保持手段に送信して記憶することを特徴とする請求項４に記載のデータ処理装置。
【請求項６】
前記データは、どのデータ処理手段が次に当該データを処理するかを示すノード情報を更に有し、
前記送信手段は、前記受信手段の受信したパケットが空のパケットの場合に前記保持手段の保持しているデータのうち、先に入力したデータと同じノード情報を持つデータのうち前記処理順序情報の示す順序が先のデータを優先して前記バスに出力することを特徴とする請求項１乃至５の何れか１項に記載のデータ処理装置。
【請求項７】
前記データは、どのデータ処理手段が次に当該データを処理するかを示すノード情報を更に有し、
前記送信手段は、前記受信手段の受信したパケットが保留パケットで前記保持手段に空きがない場合に、前記受信手段の受信した保留パケットの有するデータ及び前記保持手段の有するデータの中で優先順位の最も高いノード情報を持つデータを優先して前記バスに出力することを特徴とする請求項１乃至５の何れか１項に記載のデータ処理装置。
【請求項８】
前記データは、どのデータ処理手段が次に当該データを処理するかを示すノード情報を更に有し、
前記送信手段は、前記受信手段の受信したパケットが空のパケットであって前記保持手段にデータが記憶されている場合に、前記保持手段に記憶されているデータのうち、優先順位の最も高いノード情報を持つデータを前記バスに出力することを特徴とする請求項１乃至５の何れか１項に記載のデータ処理装置。
【請求項９】
前記データは、どのデータ処理手段が次に当該データを処理するかを示すノード情報を更に有し、
前記送信手段は、前記受信手段の受信したパケットに含まれるノード情報と同じノード情報のデータが前記保持手段に記憶されている場合、同じノード情報のデータを前記処理順序情報で示される処理順序に並び替えて再出力できる状態でデータを記憶し、前記受信したパケットに含まれるデータに含まれるノード情報と同じノード情報のデータが前記保持手段に記憶されていない場合、前記受信したパケットに含まれるデータを前記保持手段に格納した順序で再出力できる状態で記憶することを特徴とする請求項１乃至５の何れか１項に記載のデータ処理装置。
【請求項１０】
前記保持手段は、前記受信手段から保留パケットのデータを取得した場合に、自身の保持するデータを前記処理順序情報の示す順に並び替えることを特徴とする請求項１乃至９の何れか１項に記載のデータ処理装置。
【請求項１１】
前記処理順序情報は、前記バス及び前記保持手段に同時に存在できるパケットの２倍以上の値を設定できることを特徴とする請求項１乃至１０の何れか１項に記載のデータ処理装置。
【請求項１２】
複数のデータ処理手段がリング状のバスに接続され、前記複数のデータ処理手段が、データに含まれる処理順序情報の示す順番が先のデータから順番にデータ処理を行うデータ処理装置の制御方法であって、
前記バスを流れるパケットを受信する受信工程と、
前記受信工程で受信したパケットに、前記複数のデータ処理手段の何れかで処理を保留したことを示す保留情報が付加されているか否かを識別する識別工程と、
前記識別工程で識別した前記保留情報の付加されている保留パケットのデータを取り込んで保持する保持工程と、
前記受信工程で空のパケットを受信した場合に、前記保持工程で保持したデータのうち、前記処理順序情報の示す順序が先のデータを優先して前記バスに出力する送信工程と、
を有することを特徴とする制御方法。
【請求項１３】
複数のデータ処理手段がリング状のバスに接続され、前記複数のデータ処理手段が、データに含まれる処理順序情報の示す順番が先のデータから順番にデータ処理を行うコンピュータを、
前記バスを流れるパケットを受信する受信手段と、
前記受信手段の受信したパケットに、前記複数のデータ処理手段の何れかで処理を保留したことを示す保留情報が付加されているか否かを識別する識別手段と、
前記識別手段が識別した前記保留情報の付加されている保留パケットのデータを取り込んで保持する保持手段と、
前記受信手段が空のパケットを受信した場合に、前記保持手段の保持しているデータのうち、前記処理順序情報の示す順序が先のデータを優先して前記バスに出力する送信手段と、
して機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置、制御方法及びプログラムに関する。
【背景技術】
【０００２】
従来、ハードウェアによって実現される処理回路を並列実行することによって効率よくデータ処理を行う方法として、バス型のパイプライン接続によるものがあった（特許文献１参照）。
この接続方式では、入力端において外部メモリＩ／Ｆ等から入力されたデータは、接続された順序に基づいて順次処理された後に出力端から外部メモリ等へ出力されるが、その処理順序は予めハードウェア実装時に接続された順序によって制限されていた。したがって、順序入れ替えを含む任意の処理順序を実行することはできなかった。
こうした課題を解決するために、処理回路間の接続をリング型のバスで接続する方法（特許文献２、特許文献３参照）等が提案されていた。
データフロー制御システムにおいて、前述のバス型接続の場合、パイプライン上のデータは、何れかの処理回路によってデータが受信不可能とされた際に、ストール信号によって全体がほぼ一斉に停止・流通を繰り返す。
一方、リングバスを用いたシステムでは、ストールによらず常に一定の速度でデータが移動しつづける。この特長により、複数データパスの実現や、接続順によらない処理順序等の自由度を持つことが可能になった。
リングバスにおけるデータフロー制御システムにおいては、処理サブモジュール（ＰＥ）のデータ処理順は接続順ではなく任意順とすることが可能である。また、データ処理中に別のデータが到来した際、そのデータにストール情報を付加してリングパスへ再出力することで、前段へストール状態を知らせることができる。つまり、ストール情報が付加されたデータは、何れかのＰＥにおいて受信不可能状態であったデータ、ということである。前段のＰＥは、自分の出力データにストール情報が付加されたデータ（以下、ストールデータ）を受けることで、後段でストールが発生していることを検知し、自分も処理をストールさせることで更に前段へ知らせることができる。このメカニズムで、通常のパイプラインによるデータフローにおけるストール信号相当の機能が実現されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第２７３４２４６号公報
【特許文献２】特開平０１−０２３３４０号公報
【特許文献３】特許第２８３４２１０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術では、ハードウェアとして実装された固定的な処理機能を持つ処理回路を接続したリング型バス接続において、物理的な接続順序と異なる処理順序を自在に実施することは困難であった。
例えば、接続順序を１、２、３、４とした場合に、４、３、２、１という順に処理を実行するため、トークンパッシング方式の通信方式を採用して、複数の処理回路間でデータを送受信しつつ処理を行う方式などが提案されているが、このようなデータパスを用いて接続順と異なる処理順序を実現しようとした場合、リング状に構成された通信路に順序入れ替えのために周回するデータが増えてしまうために、リング状のデータトラフィックが増加してしまい、処理性能を下げるばかりか、場合によってはデッドロックしてしまう恐れがあった。
【０００５】
本発明はこの様な問題点に鑑みなされたもので、処理性能の低下やデッドロックの発生を軽減することを目的とする。
【課題を解決するための手段】
【０００６】
そこで、本発明は、複数のデータ処理手段がリング状のバスに接続され、前記複数のデータ処理手段が、データに含まれる処理順序情報の示す順番が先のデータから順番にデータ処理を行うデータ処理装置であって、前記バスを流れるパケットを受信する受信手段と、前記受信手段の受信したパケットに、前記複数のデータ処理手段の何れかで処理を保留したことを示す保留情報が付加されているか否かを識別する識別手段と、前記識別手段が識別した前記保留情報の付加されている保留パケットのデータを取り込んで保持する保持手段と、前記受信手段が空のパケットを受信した場合に、前記保持手段の保持しているデータのうち、前記処理順序情報の示す順序が先のデータを優先して前記バスに出力する送信手段と、を有することを特徴とする。
【発明の効果】
【０００７】
本発明によれば、処理性能の低下やデッドロックの発生を軽減することができる。
【図面の簡単な説明】
【０００８】
【図１】情報処理装置のハードウェア構成の一例を示す図である。
【図２】データ処理装置の構成を示す図である。
【図３】バス間で通信されるパケットのフォーマットの一例を示す図である。
【図４】ストールデータ処理部の概念図である。
【図５】実施形態１における通信処理部及びストールデータ処理部の動作手順の一例を示すフローチャートである。
【図６】ステップＳ５０８におけるバッファへの格納手順の一例を示す図である。
【図７】ステップＳ５０７におけるデータ格納手順の一例を示す図である。
【図８】ステップＳ５１４においてデータが再出力される際のバッファの概念図である。
【図９】ステップＳ５１１を経由する際のデータの入れ替えが発生する動作手順の一例を示す図である。
【図１０】ステップＳ５１２を経由する際の受信データをそのまま再出力する動作手順の一例を示す図である。
【図１１】実施形態２における通信処理部及びストールデータ処理部の動作手順の一例を示すフローチャートである。
【図１２】ステップＳ１１０７の手順の詳細なフローチャートである。
【図１３】受信したストールデータがバッファ４０２の最後尾ではない領域に格納される動作手順の一例を示す図である。
【図１４】受信したストールデータがバッファ４０２の最後尾の領域に格納される動作手順の一例を示す図である。
【図１５】バッファ４０２にデータがある時に空パケットを受信する動作手順の一例を示す図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態について図面に基づいて説明する。
【００１０】
＜実施形態１＞
図１は、情報処理装置のハードウェア構成の一例を示す図である。
１０１は、例えばＣＰＵ等の制御処理装置である。
１０２は、画像処理部等のデータ処理装置である。
１０３は、処理される入力データや、処理後の出力データ、及びデータ処理装置１０２への設定パラメータデータ等を格納する読み書き可能なメモリ（以下、ＲＡＭ）である。
１０４は、データ処理装置１０２の処理手順や、設定パラメータ等の定数等を保持可能な読み出し可能なメモリ（以下、ＲＯＭ）である。
制御処理装置１０１において、ＲＯＭ１０４から読み出されたプログラムに従って、システムの制御並びにデータ処理装置１０２への指示等を行う。データ処理装置１０２は、制御処理装置１０１からの指示に従ってデータ処理を実行する。この際に、データ処理装置１０２は、ＲＡＭ１０３に予め格納されている入力データを読み出して処理を行い、処理結果を再びＲＡＭ１０３に書き込む。
【００１１】
図２は、データ処理装置１０２の構成を示す図である。
２０１は、ＲＡＭ１０３の様な外部記憶装置から処理すべきデータパケットを取得するデータ取得部である。
２０２は、取得されたデータパケットをリング状に構成されている通信路に供給する処理を行う通信処理部である。
２０３は、リング状に構成された通信路から、後述するデータ処理部２０４で処理すべきデータパケットを通信路から選別して取り込む通信処理部である
２０４は、供給されたデータパケットに対してしかるべき処理を行うデータ処理部である。図２に示す構成においては、２０３及び２０４からなる処理部が１つ以上接続されている。
２０５は、処理済のデータパケットを外部の記憶装置等に出力するため、リング状の通信路上から処理済のデータパケットを選択して取り込む通信処理部である。
２０９は、通信処理部２０５により取り込まれた処理済のデータパケットをＲＡＭ１０３の様な外部記憶装置に出力するデータ出力部である。
２０６は、これらの通信処理部を連結するリング状のデータバスである。
２０８は、ストールデータの保持、並び替え、再出力を行うためのストールデータ処理部である。ストールデータ処理部２０８の詳細に関しては後述するものとする。ストールデータとは、後述する図３に示されるように、複数のデータ処理部の何れかのデータ処理部で受信が不可能であった（処理が保留された）ことを示す受信不可識別情報（保留情報）の一例であるフラグが付加されているデータのことである。
２０７は、リング状に構成された通信路から、ストールデータ処理部２０８との間で入出力を行うべきデータを通信路から選別して取り込む通信処理部である
図２に示すように、リング状バスシステムは、リング状バス２０６よって構成されている。ここでリング状バス２０６は、通信処理部２０２、２０３、２０５、２０７等の複数の通信処理部を接続しているデータ伝送機能を有するバスである。図２においては６個の通信処理部を接続していることになる。
【００１２】
図３は、バス間で通信されるデータパケットのフォーマットの一例を示す図である。
３０１は、処理順序情報の一例であるデータの処理順序を示すカウント値である。リング状のデータバスにおいては、連続するストールデータがリング内を複数回周回することがありうる。そのため、データ処理部２０４がデータ受信可能となったときに最初に受信されるデータが必ずしも最初に処理されるべきデータであるとは限らない。したがって、この様な処理順序カウント値３０１をデータに付随して持たせることで、入力された順等の正しい処理順序に従って処理を実行する仕組みが必要となる。
３０２は、このデータパケットが保持しているデータが処理されるべき有効データであることを示すフラグである。これは即ち、パケットが現在使用中であるかどうかを示すフラグと同じ意味を持つ。
３０３は、このパケットが保持しているデータが、何らかの理由で処理すべきデータ処理部によって受け取られなかったことを示すフラグ（以下、ストールフラグ）である。以下、ストールデータは、このフラグが立っているデータである（ストールフラグを有するパケットは保留パケットと称する。）。
３０４は、このデータを処理したデータ処理部２０４により付加される接続ノード情報の一例であるノードＩＤである。通信処理部２０３では、リングバスを周回してきたデータパケットを受信した際に、このノードＩＤの照合を行うことにより、自身に接続されたデータ処理部２０４において次に処理すべきデータであるかどうかを特定することができる。
３０５は、データ処理部２０４において実際に処理されるべきデータに相当する。
【００１３】
次に、ストールデータ処理部２０８について説明する。
図４は、ストールデータ処理部２０８の概念図である。
４０１は、バッファ（保持手段）との間でデータの入出力を行うためのバッファ制御部である。バッファ制御部４０１は、通信処理部２０７より供給されたデータパケット内のストールデータの取り出しと格納を行う。詳細な動作例に関しては後述する。
４０２は、実際にデータの保持、再出力を行う一時記憶領域の一例であるストールデータ保持バッファ（以下、バッファ）である。バッファの容量については、例えばリング状バス２０６の容量と等しくなるように設定するといったことが考えられるが、ハードウェアのコストと対応させて自由に変えられることを想定しているため、特に限定しないものとする。本実施形態では１０パケット分の容量を持っているものとして説明を行う。なお、バッファ４０２の初期状態は空状態である。
４０３は、バッファ内に保持されているストールデータの先頭データである。バッファ４０２は、バッファ制御部４０１からの入力順にデータを保持するので、以降の説明におけるデータの並び替えが発生しなかった場合には一番初めに入力されたデータを示す。以降のバッファ４０２を示す図面では右を先頭、左を末尾としている。
【００１４】
通信処理部２０７及びストールデータ処理部２０８の動作手順を図５のフローチャートに示す。図５は、実施形態１における通信処理部２０７及びストールデータ処理部２０８の動作手順の一例を示すフローチャートである。これについて以下に説明する。
まず、データパケットが通信処理部２０７で受信されたとする。このとき、ステップＳ５０１において、通信処理部２０７は、受信パケットにデータが存在するか否かを判定し、データが存在するならば、ステップＳ５０２に進む。
ステップＳ５０２において、通信処理部２０７は、受信パケット内のデータがストールフラグのたったストールデータであるか否かを判定する。
バッファ４０２は、ストールデータのみを格納するものとしているので、ステップＳ５０２においてストールフラグのついていないデータであった場合、通信処理部２０７は、ストールデータ処理部２０８への取り込みは行わない。そして、通信処理部２０７は、ステップＳ５０３でストールフラグのついていないデータを含むパケットをそのままリングバスに流す。
ステップＳ５０２において、受信したパケット内のデータがストールデータであった場合、通信処理部２０７は、バッファ制御部４０１にデータパケットを送信する。ここでバッファ制御部４０１は、ステップＳ５０４においてバッファ４０２に所定の量の空きがあるかどうかを判定し、空きがあるならばＳ５０５で受信パケットからストールデータを取り出して空パケットをリングバス上に出力する。そして、バッファ制御部４０１は、取り出したストールデータを以降のステップにおいてバッファ４０２へ格納する。
ステップＳ５０６において、バッファ制御部４０１は、バッファ内に格納された全てのデータのノードＩＤと受信データに付加されたノードＩＤ３０４とを比較し、同じノードＩＤがあるかどうかを判定する。
【００１５】
ステップＳ５０６において同じノードＩＤが存在しなかった場合の、ステップＳ５０８におけるバッファ４０２へのストールデータ格納手順の例を図６に示す。図６は、ステップＳ５０８におけるバッファ４０２への格納手順の一例を示す図である。図６における６０１〜６０４はバッファ制御部４０１からバッファに入力されたデータであり、全てのノードＩＤが異なる。図６において、例えば６０１は、処理順序カウント値３０１が２、ノードＩＤ３０４が１であることを示している。バッファ４０２は時間０（ｔ＝０）では、空である。この例において、データは６０１、６０２・・・の順で入力されると、入力順にバッファの空き領域の先頭にデータが格納される。なお、入力順は、バッファ制御部４０１により保持されており、以降の説明における並び替えが発生しなければ、この順でリングバス上に再出力されることとなる。図では時間１（ｔ＝１）で６０１内のストールデータがバッファ４０２に格納され、ステップＳ５０５によって空パケット６０５が出力される様子を示している。同様に時間２（ｔ＝２）から４（ｔ＝４）で６０２から６０４内のストールデータが順にバッファ４０２に格納され空パケット６０６から６０８が出力される。
ステップＳ５０６において、同じノードＩＤが存在する場合について説明する。
ノードＩＤ３０４が等しいデータが存在するということは、同じデータ処理部によって受信不可能とされた複数のデータが、リング状バス内を周回していたことになる。これらのデータは、処理順序カウント値３０１に従って順に処理されるべきである。しかし、リング内のデータ処理部において、個々の処理の処理速度（スループット）に差があったり、処理部内でデータ量が増減してしまったりする場合、実際の処理順とは異なる順番で通信処理部２０７にデータパケットが流れるケースが考えられ、何も考慮しないとバッファ４０２内には処理の順序と異なる順序でストールデータが格納される。この場合、先に格納されていたデータをバッファ４０２から再出力しても、それより処理順序が前のデータがバッファ４０２内に存在する間は、再出力したデータを処理できないので再びバッファ４０２へ戻ってきてしまうので効率がよくない。
そこで、Ｓ５０６においてバッファ４０２内にノードＩＤ３０４が等しいデータが存在した際は、Ｓ５０７において、バッファ制御部４０１は、それらのデータを処理順序カウント値３０１に従って昇順に並び替えて、受信データの取り込みを行うようにする。
【００１６】
ステップＳ５０７におけるデータ格納手順の例を図７に示す。図７は、ステップＳ５０７におけるデータ格納手順の三つの例を示す図である。図７の時間ａ（ｔ＝ａ）、ｂ（ｔ＝ｂ）、ｃ（ｔ＝ｃ）に示したように予めバッファ４０２にはそれぞれ幾つかのデータが格納されているものとする。また図７における７０１〜７０３は、バッファ制御部４０１から入力されたデータである。例えばデータ７０１は、処理順序カウント値３０１が６、ノードＩＤ３０４が３であることを示している。
図７の時間ａ（ｔ＝ａ）は新たに入力されたデータ７０１と同じノードＩＤを持つデータが一つの場合のバッファ制御例である。この状態で、データ７０１が入力されると、バッファ４０２内にはデータ７０１とノードＩＤ３０４が等しいデータ７０４が存在するので、バッファ制御部４０１は、それぞれの処理順序カウント値３０１の値を比較する。ここで、データ７０４よりもデータ７０１の方が処理順序カウント値３０１が小さい、即ち７０１の方が７０４よりも先に処理されるべきデータである。したがって、バッファ制御部４０１は、並び替えをしなければバッファ４０２の空き領域の先頭位置に入れられるべきデータ７０１とバッファ４０２内にあった７０４との順序を入れ替えてバッファ４０２への格納を行う。この例での処理後の格納結果を図７の時間ａ．ｎ（ｔ＝ａ．ｎ）に示す。時間ａ（ｔ＝ａ）の状態でバッファ４０２の先頭（右）から３番目に格納されていた７０４は時間ａ．ｎ（ｔ＝ａ．ｎ）ではバッファ４０２の最後のデータとなり、７０４が格納されていた場所には７０１が格納されている。７０１と７０４との間にはノードＩＤ３０４が違うデータが格納されているが、７０１と７０４との処理順に限れば無関係であるので並び替える必要はない。但し、時間ａ（ｔ＝ａ）の状態では先頭に近かった７０４を先に処理すべき優先度があるようなシステムであれば、時間ａ（ｔ＝ａ）の状態で７０４以降のデータを、一つずつ順序を保ったまま後方へ移動させ、空いた場所に７０１を格納する等の処理が必要になる。
【００１７】
図７の時間ｂ（ｔ＝ｂ）は新たに入力されたデータ７０２と同じノードＩＤ３０４を持つデータが複数あり、かつ７０２はそれらのデータよりも処理順序が早い場合のバッファ制御の例である。この状態で、データ７０２が入力されると、バッファ４０２内にデータ７０２とノードＩＤ３０４の等しいデータ７０５及び７０６が存在するので、バッファ制御部４０１は、データ７０２、７０５、７０６の間で処理順序カウント値３０１に従って並び替えを行う。この例では、処理順序カウント値３０１が７０２、７０６、７０５の順に大きくなっているので、バッファ制御部４０１は、バッファ内にあるデータ７０５及び７０６を後方に移動し、時間ｂ（ｔ＝ｂ）の状態の時のバッファ４０２において７０６があった位置へデータ７０２を格納する。このとき、必要なのは先立つ処理によって処理順序カウント値３０１の順に格納されている同じノードＩＤ３０４を持つデータ（例では７０５、７０６）の順序を維持することである。この例での処理後の格納結果を図７の時間ｂ．ｎ（ｔ＝ｂ．ｎ）に示す。時間ｂ（ｔ＝ｂ）の状態でバッファ４０２の先頭（右）から３番目に格納されていた７０６は時間ｂ．ｎ（ｔ＝ｂ．ｎ）ではバッファ４０２の最後から２番目のデータとなり、７０６が格納されていた場所には７０２が格納されている。時間ｂ（ｔ＝ｂ）のバッファ４０２で最後のデータであった７０５は時間ｂ．ｎ（ｔ＝ｂ．ｎ）でも最後のデータであるが、７０２を格納したので位置は一つ後方に移動している。このようにするには新たに入力された７０２と同じノードＩＤ３０４を持つデータであって処理順序が最後のデータをまず空き領域の先頭に移動し、これにより空いた場所へ移動したものと同じノードＩＤ３０４で一つ前の処理順序を持つデータを移動する。そしてこの処理を繰り返すことによって最後に空く場所が、時間ｂ（ｔ＝ｂ）の状態で７０２と同じノードＩＤ３０４を持つデータであってかつバッファ４０２内にある中で最初に処理すべきデータが存在した場所であるので、ここへ７０２を格納すればよい。
図７の時間ｃ（ｔ＝ｃ）は新たに入力されたデータ７０３と同じノードＩＤ３０４を持つデータが複数あり、かつ７０３はそれらのデータの途中で処理されなければならない場合のバッファ制御の例である。この状態で、データ７０３が入力されると、バッファ４０２内にデータ７０３とノードＩＤ３０４の等しいデータ７０７及び７０８が存在するので、バッファ制御部４０１は、データ７０３、７０７、７０８の間で処理順序カウント値３０１に従って並び替えを行う。この例では、処理順序カウント値３０１が７０８、７０３、７０７の順に大きくなっているので、バッファ制御部４０１は、データ７０８はそのままで、データ７０７と７０３の順序を並び替えてバッファ４０２に格納する。この例での処理後の格納結果を図７の時間ｃ．ｎ（ｔ＝ｃ．ｎ）に示す。時間ｃ（ｔ＝ｃ）の状態でバッファ４０２の先頭（右）から３番目に格納されていた７０８は時間ｃ．ｎ（ｔ＝ｃ．ｎ）でも同じ位置にあるが、時間ｃ（ｔ＝ｃ）のバッファ４０２で先頭から５番目にあった７０７は時間ｃ．ｎ（ｔ＝ｃ．ｎ）では最後のデータとなり、７０７が格納されていた場所には７０３が格納されている。このようにするための手順は並び替え対象データの数によって前述の二つの例での並び替え方法を選択して実行すればよい。
以上説明したように、ステップＳ５０８における処理により、ストールデータが一時的にバッファ４０２に格納され、リングバスのみかけのパケット保持容量を上げることができる。また、ステップＳ５０７における処理により、バッファ４０２に格納されたデータを、最も処理効率のよい再出力順序に並び替えておくことができる。つまり、再出力の際にはバッファ４０２の先頭から単純にデータを再出力すると最も処理効率が良くなる。なお、処理順序カウント値３０１は、各バケットの順番を区別するため、（リング状バス２０６＋バッファ４０２に同時に存在できる同一ノード情報をもつパケット数）の２倍以上の値を保持できるものとする。これにより、カウント値が最大値を超えて０になっても、カウント値の差分絶対値が上記制限数（リング状バス２０６＋バッファ４０２に存在できる同一ノード情報をもつパケット数）を超えた場合に、大小判定を逆転させることで、正確な順序を判定できる。通常、上記制限数は（通信処理部の数＋バッファ４０２の容量）となる。
【００１８】
次に、バッファ４０２に格納されたデータのリングバス上への再出力の手順について説明する。データの再出力は、通信処理部２０７において空パケットを受信した際に起こる。
ステップＳ５０１において、あるサイクルにおいて通信処理部２０７が受信したパケットが空だった場合、バッファ制御部４０１は、ステップＳ５１３において、バッファ４０２内にデータが格納されているかどうかを判定する。バッファ４０２内にデータが存在した場合には、Ｓ５１４において、バッファ制御部４０１は、先頭データの再出力を行う。バッファ４０２が空の際には、バッファ制御部４０１は、何もしないで終了し、ステップＳ５１５においてリングバス上には受信した空パケットが出力される。
図８は、ステップＳ５１４においてデータが再出力される際のバッファの概念図である。図８の時間ｄ（ｔ＝ｄ）において、幾つかのデータがバッファ４０２に格納されているときに、通信処理部２０７に空パケット８０１が到達したとする。ここで、バッファ制御部４０１は、空パケット８０１に対して、バッファ４０２の先頭データ８０２を乗せることで再出力する。出力した結果、図８のｄ．ｎ（ｔ＝ｄ．ｎ）に示すように、バッファ４０２内では、格納されていたデータが一つ減り、残りのデータを先頭方向へ一つずつシフトすることで先頭データは更新される。
このようにステップＳ５１３及びＳ５１４における処理により、受信した空パケットにバッファ４０２内に一旦格納したストールデータを乗せて再出力することでこれが処理される機会を与えることができる。
【００１９】
次に、バッファ４０２に格納されたストールデータの入れ替え手順について説明する。データの入れ替えはバッファ制御部４０１がストールデータを受信した際にバッファ４０２の空き領域がない場合に起こる。
ストールデータを受信した際、バッファ制御部４０１では、Ｓ５０４においてバッファ４０２の状態を確認し、バッファフルであった場合にステップＳ５０９に進み、ここでデータの入れ替えを判断する。
ステップＳ５０９において、受信したパケット内のデータとバッファ４０２の先頭データとでノードＩＤ３０４を比較し、ノードＩＤ３０４が等しければ、ステップＳ５１０において両者の処理順序カウント値３０１の比較を行う。ステップＳ５１０において、受信データの処理順序カウント値３０１よりも先頭データの処理順序カウント値３０１が大きい（処理順序が後）場合、バッファ制御部４０１は、バッファに格納されたデータとの入れ替えは行わずに、ステップＳ５１２で受信データをそのまま再出力する。
一方、ステップＳ５０９で受信データとノードＩＤ３０４が異なる場合、ステップＳ５１１においてバッファ制御部４０１がバッファ４０２の先頭データを出力し、バッファ４０２内のデータを一つずつ前方へシフトする。このとき、バッファ４０２に空きがある状態でストールデータを受け取った前述の場合と同じになるので、ステップＳ５０６以降の手順でもって受信データをバッファ４０２へ格納する。この結果、バッファ４０２の先頭にあったデータと受信データとの入れ替えがおきる。また、Ｓ５１０において受信データの処理順序カウント値３０１よりも先頭データの処理順序カウント値３０１が小さい（処理順序が前）場合も同様の手順によりバッファ４０２の先頭にあったデータと受信データとの入れ替えがおきる。
【００２０】
図９及び図１０に、バッファフル時のデータ入出力の概念図を示す。
図９は、データの入れ替えが発生する際の動作手順の一例を示す図である。図９の時間ｅ（ｔ＝ｅ）に示したように、バッファ４０２は、予めデータで満たされているものとする。図９における９０１は、バッファ制御部４０１から入力されたデータである。図の例では、データ９０１は、処理順序カウント値３０１が１０、ノードＩＤ３０４が２であることを示している。
この例において、データ９０１と９０２、９０３、９０４のノードＩＤが等しくなっているので、バッファ制御部４０１は、ステップＳ５０９を経由して、ステップＳ５１０に進む。
ステップＳ５１０において、バッファ制御部４０１は、受信データ９０１と先頭データ９０２の処理順序カウント値３０１を比較する。例では、先頭データ９０２の処理順序カウント値３０１の方が小さい（処理順序が先）ので、バッファ制御部４０１は、ステップＳ５１１に進む。
ステップ５１１において、バッファ制御部４０１は、図９の時間ｅ．ｎ（ｔ＝ｅ．ｎ）に示すように、先頭データ９０２をバッファ４０２から再出力し、バッファ４０２内のデータを前方に一つずつシフトする。この結果、バッファ４０２の最後尾は空き領域となるので前述のステップＳ５０６以降の処理によって受信データ９０１の格納位置を決定して格納し処理を終了する。
【００２１】
図１０は、ステップＳ５０９及びＳ５１０を経由後に受信データをそのまま再出力する際の動作手順の一例を示す図である。図１０の時間ｅ（ｔ＝ｅ）に示したように、バッファ４０２は、予めデータで満たされているものとする。図１０における１００１は、バッファ制御部４０１から入力されたデータである。この例では、データ１００１は、同じノードＩＤ３０４を持つバッファ４０２の先頭データ１００２よりも処理順序カウント値３０１が小さい（処理順序が早い）。つまり、バッファ内にある同じノードＩＤ３０４を持つデータ１００２、１００３、１００４の方がデータ１００１よりも処理順序が遅い。したがって、バッファ制御部４０１は、ステップＳ５０９及びＳ５１０の後はステップＳ５１２へ進み、受信データをそのまま再出力する。したがって、この場合は受信されたデータとバッファとの間でのデータの入れ替えは発生しない。なお、先頭データ１００２はそのまま残るので、バッファ４０２へのデータの到着順とは関係なく、図１０の例のようにノードＩＤ３０４が同じものが連続してリングバス上へ再出力される場合があるが、処理されなければ戻ってくるので問題はない。
以上の様な手順でストールデータ処理部２０８においてデータの格納、並び替え、再出力、入れ替えを行うことで、リングバスを周回するストールデータの再出力順序を最適化し、処理されないデータがリング内のパケットを占有することを防ぐことができる。
データの並び替えが発生しなかったとしても、この様なバッファ４０２を用意することにより、リングバスのパケット保持容量が上がり、リングバス上のトラフィック減少が期待できる。
【００２２】
＜実施形態２＞
図１１は、実施形態２における通信処理部２０７及びストールデータ処理部２０８の動作手順の一例を示すフローチャートである。これについて以下に説明する。
データが通信処理部２０７で受信されたとする。ステップＳ１１０１において、通信処理部２０７は、受信パケットにデータが存在することを判定し、データが存在するならば、ステップＳ１１０２に進む。
ステップＳ１１０２において、通信処理部２０７は、受信データのストールフラグがたっているかどうかを判定する。
バッファ４０２は、ストールデータのみを扱うものとしているので、ステップＳ１１０２においてストールフラグのついていないデータであった場合、通信処理部２０７は、ストールデータ処理部２０８への取り込みは行わない。そして、ステップＳ１１０３において、通信処理部２０７は、受信したデータをそのままリングバスに出力して処理を終了する。
ステップＳ１１０２において、受信したデータがストールデータであった場合、通信処理部２０７は、バッファ制御部４０１にデータを送信する。ステップＳ１１０４以降のステップにおいて、バッファ制御部４０１は、バッファ４０２へ、ストールデータの格納を行う。
ステップＳ１１０４において、バッファ制御部４０１は、バッファ４０２の空き領域の先頭に受信データを格納する。このとき、ステップＳ１１０５では、受信データの格納場所がバッファ４０２の最後尾であったかどうかを判定する。判定の結果、最後尾でないのであれば、ステップＳ１１０６において空パケットを出力し、最後尾であったならば、ステップＳ１１０７へ進む。ステップＳ１１０７では後述の手順によってバッファ内からデータを一つ取り出し、ステップＳ１１０８でこれを出力して処理を終了する。
一方、ステップＳ１１０１において、受信パケットにデータが存在しない、すなわち空パケットならば、ステップＳ１１０９でバッファ４０２の先頭領域が空かどうかを調べる。先頭領域が空でない場合、ステップＳ１１０７以降の手順を実行し、空であればステップＳ１１１０で受信した空パケットをそのまま出力して処理を終了する。
【００２３】
図１２はステップＳ１１０７の手順の詳細なフローチャートである。これについて以下で説明する。
ステップＳ１１０７では、まずステップＳ１２０１においてバッファ４０２の先頭データを最終的に取り出すデータの候補である基準データとする。そして最初の基準データであった先頭データから一つ後方のデータ、すなわち先頭から２番目のデータと基準データとをステップＳ１２０３で比較するが、これに先立ちステップＳ１２０２で一つ後方の領域が空きでないことを確かめる。
ステップＳ１２０３では、比較対象のデータが基準データとノードＩＤ３０４が同じで処理順序カウント値３０１が小さいかどうかを調べ、そうであればステップＳ１２０４で比較対象データと標準データの格納位置を入れ替えて、比較対象データを新たな基準データとする。これにより比較対象データと比較前の標準データとが入れ替わる。新たな標準データの位置は常にバッファ４０２の先頭である。なお、ステップＳ１２０３で条件が成り立たない場合は、データの入れ替わりはない。
上記ステップＳ１２０２〜Ｓ１２０４はステップＳ１２０５で比較対象がバッファ４０２の最後のデータであることが検出されるまで比較対象データの位置を一つずつ後方へずらしながら繰り返す。但し、ステップＳ１２０２で一つ後方の領域が空きである場合は、繰返しを中止する。
繰り返し処理が終了したならば、ステップＳ１２０６において最後の基準データである先頭データをステップＳ１１０７の出力としてバッファ４０２から取り出し、空いた領域を埋めるためにステップＳ１２０７において残りのデータを一つずつ前方へシフトする。
【００２４】
図１３、１４、１５は、実施形態２におけるバッファ４０２の動作の概念図である。
図１３は、受信したストールデータ（１３０１、１３０２、１３０３）がバッファ４０２の最後尾ではない領域に格納される場合の動作例である。
図１３の時間０（ｔ＝０）は初期状態であり、バッファ４０２は空である。実施形態２において図１１に示した処理手順において、バッファ制御部４０１は、ストールデータをそれぞれの時間１（ｔ＝１）、２（ｔ＝２）、９（ｔ＝９）に取り込んだ際、バッファ４０２の空き領域の先頭へデータを格納し、空きパケット（１３０４、１３０５、１３０６）を出力する。
図１４は、受信したストールデータ１４０１がバッファ４０２の最後尾の領域に格納される場合の動作例である。
時間１０（ｔ＝１０）の状態で受信されたストールデータは、時間１０．ｌ（ｔ＝ｌ）でバッファ４０２の最後尾へ格納される。次にバッファ制御部４０１は、先頭データ１４０２を基準データとし、同じノードＩＤ３０４を持つデータ１４０３、１４０４、１４０５と処理順序カウント値３０１を比較していく。そして時間１０．ｍ（ｔ＝ｍ）で、時間１０．ｌ（ｔ＝ｌ）で基準データであった１４０２よりも処理順序カウント値３０１が小さなデータ１４０３を見つけると両者の格納場所を入れ替え、１４０３を新たな基準データとする。
バッファ制御部４０１は、最後に比較を行った位置以降のデータを対象として新たな基準データ１４０３との比較処理を進める。そして時間１０．ｎ（ｔ＝ｎ）で、基準データ１４０３よりも処理順序カウント値３０１が小さいデータ１４０４を見つけると両者の格納場所を入れ替え、１４０４を新たな基準データとする。この例では、新たな基準データ１４０４よりも処理順序カウント値３０１が小さいデータは存在しないので、時間１０．ｏ（ｔ＝ｏ）で比較処理が最後のデータに達すると最新の基準データである先頭データ１４０４を出力し、空き領域を埋めるために残りのデータをすべて先頭方向へ一つずつシフトして格納しなおす。この結果、バッファ４０２の最後尾は空き領域となり、上記の処理を繰り返すことができる。
このように本実施例では、バッファ４０２の最後尾が必ず空き領域になっているため、受信したパケットは常にバッファ４０２の最後尾に格納される。データの入れ替えが発生しても先頭のバッファと同じノードＩＤを持つデータ間での入れ替えになるので、異なるノードＩＤを持つデータはバッファ４０２への到着順に再出力されることとなる。
図１５はバッファ４０２にデータがある時に空パケット１５０１を受信した場合の動作例である。
時間１０（ｔ＝１０）の状態で空パケット１５０１を受信すると、バッファ制御部４０１は、時間１０．ｌ（ｔ＝ｌ）で先頭データ１５０２を基準データとし、同じノードＩＤ３０４を持つデータ１５０３、１５０４、１５０５と処理順序カウント値３０１を比較していく。そして時間１０．ｍ（ｔ＝ｍ）で、時間１０．ｌ（ｔ＝ｌ）で基準データであった１５０２よりも処理順序カウント値３０１が小さなデータ１５０３を見つけると両者の格納場所を入れ替え、１５０３を新たな基準データとする。
バッファ制御部４０１は、最後に比較を行った位置以降のデータを対象として新たな基準データ１５０３との比較処理を進める。そして時間１０．ｎ（ｔ＝ｎ）で、基準データ１５０３よりも処理順序カウント値３０１が小さいデータ１５０４を見つけると両者の格納場所を入れ替え、１５０４を新たな基準データとする。この例では、新たな基準データ１５０４よりも処理順序カウント値３０１が小さいデータは存在しないので、時間１０．ｏ（ｔ＝ｏ）で比較処理が最後のデータに達すると最新の基準データである先頭データ１５０４を出力し、空き領域を埋めるために残りのデータをすべて先頭方向へ一つずつシフトして格納しなおす。この結果、バッファ４０２の最後尾と一つ手前は空き領域となり、上記の処理を繰り返すことができる。
このように、バッファ４０２内に格納されたストールデータの再出力の際にデータの並べ替えをすることでも先の実施例と同様の効果を得ることができる。また、バッファ４０２の最後尾を必ず空き領域にしておくことで、異なるノードＩＤ３０４を持つデータがバッファ４０２への到着順で再出力されることを保証することもできる。
【００２５】
＜その他の実施形態＞
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【００２６】
以上、上述した各実施形態によれば、リングバス上のデータを一時退避させることで処理性能の低下やデッドロックの発生を軽減することができる。
また、退避したデータを正しく並び替えることで再出力の順番を最適化することができ、更なる処理性能の向上が可能である。
【００２７】
以上、本発明の好ましい実施形態について詳述したが、本発明は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
例えば、上記の実施形態におけるリングバス上のデータの並び替えは、同じノードＩＤ３０４を持つデータ間で処理順序カウント値３０１にしたがって行っているが、ノードの優先順位があるシステムでは、このノードＩＤ３０４で並べ替えを行うことも可能であり、両者を組み合わせることももちろん可能である。
【図１】
2011180838.tif 000003
【図２】
2011180838.tif 000004
【図３】
2011180838.tif 000005
【図４】
2011180838.tif 000006
【図５】
2011180838.tif 000007
【図６】
2011180838.tif 000008
【図７】
2011180838.tif 000009
【図８】
2011180838.tif 000010
【図９】
2011180838.tif 000011
【図１０】
2011180838.tif 000012
【図１１】
2011180838.tif 000013
【図１２】
2011180838.tif 000014
【図１３】
2011180838.tif 000015
【図１４】
2011180838.tif 000016
【図１５】
2011180838.tif 000017