JPH0217821B2 - - Google Patents

Description

【発明の詳細な説明】 〔発明の技術分野〕 本発明は、複数台の処理装置と記憶装置からな
る並列データ処理装置における、処理装置と記憶
装置間とのデータ転送方式に関する。

〔発明の技術的背景とその問題点〕

近年、VLSI技術の発展に伴い多数の、VLSIに
より製作された処理装置からなる並列データ処理
装置の構築が容易となつた。これらの装置を構築
する上で最大の問題となる点は、その構成要素で
ある記憶装置部と多数の処理装置をいかに接続す
るかである。これまでの計算機システムなどでよ
く用いられた方式を第１図に示す。同図は、複数
台の処理装置１２〜１４が記憶制御部１１を介し
記憶装置１０に接続されている様子を示してい
る。記憶制御部１１は、処理装置１２〜１４から
のアクセフ要求を受けつけ、それらの要求を出し
ている処理装置の１つを選択し記憶装置にアクセ
スせしむる制御をするものである。この方式は、
処理装置の台数が多くなると、記憶制御部１１の
構造が複雑で多量のハードウエアが必要であり、
処理装置の台数は高々８台程度が限度であつた。
しかしひとたび第１図に示すような方式で並列デ
ータ処理装置を構築した後、処理装置の台数を増
やすことは、あらかじめ記憶制御部１１に処理装
置を接続するポートを余分に用意しておかない限
りほとんど不可能である。このような余分のポー
トを常に用意しておくことはハードウエア資源を
有効に利用したことにならずはなはだ好ましくな
い。さらに各処理装置１２〜１４は、記憶装置内
に格納されているデータのどの部分を処理すべき
か常に管理しておらねばならず、これらの管理が
通常プログラムで行なわれることから、各処理装
置のプログラムを複雑なものとしている。また処
理装置の台数が故障などの理由で変更された時、
各処理装置内にある、データのアクセスを管理す
るプログラム部分を変更する必要があり、場合に
よつては各処理装置に対するプログラムを再ロー
テイングするなど煩雑な処理が要求されることが
ある。

以上に述べたような欠点を克服するため、第２
図に示すように、各処理装置１２〜１４内にそれ
ぞれレジスタ２２〜２４を設置し、これらのレジ
スタと記憶装置１０の制御部１１をリング状に接
続し、記憶装置と各処理装置間のデータ転送を行
なわせしむる方式が考えられる。処理装置の台数
をｎとした時、ｎ個のレジスタ２２〜２４をシフ
トレジスタとして構成し、制御部１１はｎ個のデ
ータを記憶装置から読み出し、転送路２０を介し
てシフトレジスタを構成しているレジスタ２２〜
２４に送出し、各処理装置にデータを受けとら
せ、各処理装置１２〜１４は受けとつたデータを
処理しその結果を対応するレジスタ２２〜２４に
それぞれ格納し、その後シフトレジスタ２２〜２
４、転送路２１を介して制御部１１に送り、記憶
装置１０に結果を書き込むわけである。この方式
では、処理装置の台数を追加するには、リング状
に接続した経路上にレジスタを１つ追加し、その
レジスタに処理装置を接続すれば良い。前記経路
上にレジスタを追加することは容易であり、処理
装置を任意個数追加することができる。またこの
場合各処理装置の処理手順は、処理装置の台数に
無関係なく対応するレジスタからデータを受けと
り、処理後その結果を該レジスタに格納する手順
で良く、プログラムの変更などは不必要であ。制
御部１１や処理装置台数分のデータを送出し、処
理結果も同数受けとるように変更するだけで良
い。しかしながらこの方式の大きな欠点は、全処
理装置にデータを分配している間処理を開始する
ことができず、処理装置が遊んでしまう点であ
る。

この様子をもう少し詳しく説明する。今データ
が時間τごとにレジスタ２２〜２４間を次々と転
送されるものとし、各処理装置は受け取つたデー
タをＴ時間かかつて処理するとする。この場合ｎ
個のデータを処理するのに要する時間は、ｎ個の
シフトレジスタにデータを送る時間nτと処理時
間Ｔの和nτ＋Ｔである。処理結果をレジスタ２
２〜２４を介して記憶装置の制御部１１に送る時
間は、次に処理するｎ個のデータを各処理装置に
分配する時間を利用することができ上記時間に加
える必要はない。すなわち処理装置１２〜１４
が、その結果をレジスタ２２〜２３に格納した時
点で、制御部１１から次々と処理すべきデータを
送出するようにすれば良い。このnτ＋Ｔ時間の
うち処理装置が動作しているのは、Ｔ時間のみで
あり、処理装置の台数を増加し、転送時間nτと
処理時間がほぼ同じ程度とすると各処理装置の稼
動率は1/2程度なつてしまう。

さらに各データに対する処理時間が異なる場
合、この方式では、最も時間のかかる処理が終了
するまで、データの転送が行なえず、処理装置が
遊ぶ可能性が更に大きくなる。例えば４台の処理
装置が、第３図に示すような処理時間の異なる16
ケのデータのすべてを処理し、記憶装置に返送す
るまでの時間は、４つづつに区切つた４組のデー
タに対し、4τの転送時間、20τの処理時間、さら
に最後の組データに対しては結果を返送する4τの
時間かかり計100τ時間となり、その転送のオーバ
ヘツドは大変大きなものとなつてしまう。

〔発明の目的〕

本発明は以上に鑑みなされたもので、その目的
とするところは、記憶装置と複数台の処理装置を
結合してなる並列データ処理装置において、処理
装置の追加が容易な並列データ処理装置を提供す
ることにある。

また他の目的とするところは、処理装置の追加
や、故障などにより処理装置の台数に変化が生じ
ても、記憶装置の読み出し、書き込みの制御手
順、各処理装置のデータ送受の制御手順のいずれ
をも変更する必要のない並列データ処理装置を提
供することにある。

さらに他の目的は、記憶装置と処理装置間のデ
ータ転送時において、処理装置が処理すべきデー
タを受けとれずに休止しているオーバヘツド時間
を極力少なくした並列データ処理装置を提供する
ことにある。

〔発明の概要〕

本発明は、制御部を有する記憶装置とｎ台処理
装置をノードとしリング状に結合し、前記ノード
上を、パケツトにより一方向に転送するシステム
において、パケツトは、データを保持しているか
否かを示す識別子と、第１種あるいは第２種のい
ずれのパケツトかを判別する識別子を持たせ、前
記制御部には、１つの第１種のパケツトと、ｎ個
の第２種のパケツトを生成する手段と、これらの
パケツトを生成した時およびリング上のノードか
らパケツトを受けとつた時、そのパケツトが第１
種のパケツトならデータを格納せず空状態としノ
ードに送出し、そのパケツトが第２種のパケツト
なら、前記記憶装置より処理すべきデータを読み
出し前記パケツトに格納しノードに送出する手段
と、さらにノードからパケツトを受け取つた時、
そのパケツトがデータを保持していればそのデー
タを取り出し前記記憶装置に格納する手段をもた
せ、一方、各処理装置にはパケツトを受け取つた
時 (1) そのパケツトにデータが格納されており、そ
の処理装置が処理中あるいは処理を終了したデ
ータを保持していないなら、パケツト内のデー
タを受けとり空状態のパケツトを次のノードに
転送し、 (2) そのパケツトが空状態の場合、その処理装置
が処理中あるいは処理を終了したデータを保持
している時、処理中の場合は処理が完了するの
を待ち、処理結果をパケツトに格納し次のノー
ドへ転送し、 (3) 上記(1)、(2)以外の場合は、そのまま受け取つ
たパケツトを次のノードへ転送する。

手段を持たせたものである。

〔発明の効果〕

本発明によれば、記憶装置と複数台の処理装置
を結合してなる並列データ処理装置において、各
装置をノードとしてリング状に結合しているた
め、処理装置の追加が非常に単純に行なうことが
でき、また、データを転送する手順が、各装置が
受けとつたパケツトの状態にのみ影響され、処理
装置の台数とは無関係に、データの送受を行なう
ことができ、処理装置の台数が変化しても、その
データ送受の制御手順をなんら変更する必要のな
い結合手段が実現できる。さらにデータの転送お
よびその処理は並列に行なうことができ、データ
の処理時間が異なる場合もデータ転送のオーバヘ
ツドを極力少なくすることができる。

また制御部は送信するデータがどの処理装置で
行なわれるかまた受け取つたデータがどの処理装
置からのものであるのか等を全く知る必要がない
ので極めて簡単な回路構成とすることができる。

〔発明の実施例〕

次に本発明を実施例にもとづき詳細に説明す
る。第４図に全体の構成を示す。１０はデータを
格納している記憶装置、１１はその制御部であ
り、処理装置１２〜１４がそれぞれをノードとし
て転送路２０，２１等によりリング状に結合され
ている。制御部１１内の３１はデータを記憶装置
１０から取り出すためのアドレスカウンタであ
る。３２は処理装置から送られてきた結果を１０
に格納するためのアドレスカウンタである。３
１，３２はいずれも初期設定時において、それぞ
れデータの先頭番地がセツトされ、記憶装置への
アクセス時＋１される。３４は読み出したデータ
を一時格納するレジスタ、３５は処理装置から送
られてきたデータを一時格納するレジスタであ
る。３３は、リング上を巡回するパケツトを一時
格納するFIFO（First Fn First Out）構成のレジ
スタである。１２〜１４はそれぞれ処理装置であ
りｎ台接続されているものとする。処理装置１２
〜１４内の４２〜４４は、パケツトを格納するレ
ジスタであり、４５〜４７はデータの処理を行な
う部分である。

データを転送する転送路２０，２１上のデータ
形式は第５図に示すように、データを格納するフ
イールド５４の他、転送路上にパケツトが存在す
ると１となるEXISTフイールド５１、そのパケ
ツトにデータが存在する時１となるFULLフイー
ルド５２、さらにそのパケツトが第１種のパケツ
トである時１になるＮフイールド５３から構成さ
れているものとする。なお後ほど詳しく説明する
が、パケツトを格納するFIFO３３は、第５図に
示したパケツト全体を格納する必要はなく、その
パケツトが第１種のものであるか否かを示すＮフ
イールド５３の状態のみを憶えておけばよく、
FIFOのデータ幅は１ビツトで済む。

まずはじめに、制御部１１がｎ＋１個のパケツ
トを発生する。そのうちの１つは第１種のパケツ
トでｎ個は第２種のパケツトである。１つのパケ
ツトを第１種とするための（Ｎフイールドを１に
するための）手順について説明する。なおパケツ
トはノード間をτ時間ごとに移動しその移動は同
期して行なわれるものとする。初期状態において
アドレスカウンタ３１には処理すべきデータが格
納されている記憶装置１０の先頭番地、３２には
処理された処理結果を格納する記憶装置１０内の
領域の先頭番地が入つているとする。制御部１１
は最初のタイミングでFULLフイードを０（デー
タが格納されていない空状態を示す）、Ｎフイー
ルド１（第１種のパケツトであることを示す）と
したパケツトを処理装置１２へ送る（当然
EXISTフイールドは１になつている）。

次にアドレスカウンタ３１により、記憶装置１
０からデータを順に読み出し、データフイールド
５４にセツトし、FULLフイールドを１、Ｎフイ
ールドを０（第２種のパケツトを示す）としたパ
ケツトを次々と処理装置へ走る。これらのｎ個の
パケツトは、各処理装置を順に回り、先頭のパケ
ツト（Ｎフイールドを１とした第１種のパケツ
ト）は、丁度ｎ＋１クロツク目に制御部１１に戻
つてくる。制御部１１は、この時点でパケツトの
発生を停止すれば、ｎ＋１ケのパケツトが発生さ
れたことになる。

ｎ台の処理装置のそれぞれは、次に示す手順で
パケツトとのデータの受け渡しをする。パケツト
が処理装置に対応するレジスタ４２〜４４に格納
されたことを、フイールドEXISTにより検出し
た時、次のいずれかの動作をとる。この手順を処
理装置パケツト転送手順と呼ぶことにする。

(1) そのパケツトがデータを格納していること
が、FULLフイールドが１になつていることに
より検出され、かつその処理装置は、先に送ら
れたデータを処理中でない、あるいは処理を終
了したデータを保持していない（送出し済）場
合は、パケツトからデータを取り出し処理を開
始し、FULLフイールドを０として次のノード
へ送る (2) 受けとつたパケツトのFULLフイールドが１
であるが、その処理装置がすでにデータを保持
（先に受けとつたデータの処理中又はその処理
結果を未だ送出していない）しておれば、その
ままそのパケツトを次のノードへ送る (3) FULLフイールドが０（そのパケツトにはデ
ータが格納されていない）でありかつその処理
装置が保持しているデータがない時、そのまま
そのパケツトを次のノードへ送る (4) FULLフイールドが０でありかつその処理装
置が処理中あるいは処理を終了したデータを保
持しておれば、処理中であれば処理が終了する
のを待ち、処理結果をパケツトに格納し、
FULLフイールドを１とし次のノードへ送る これらの動作をする処理装置の回路例を説明す
る。

第６図に処理装置１２に対応した回路図を示す
がその他の処理装置も同様構成でよい。転送路２
０上の６１〜６４で示されるEXIST，FULL，
Ｎフイールドおよびデータはレジスタ４２の６５
〜６８にそれぞれクロツク９８に信号が印加され
た時セツトされる。クロツク信号９８は、全処理
装置に共通に送られるクロツク９７をANDゲー
ド７３で制御してつくられる。その制御の方法に
ついては後程詳しく説明する。なお以後しばらく
の間信号線９５は１として説明する。７０は処理
部４５がデータを保持しているかどうかを示すフ
リツプフロツプであり、信号線８０により処理部
４５がデータを受け取つた時リセツトされ、処理
結果を送り出した時セツトされる。今処理部４５
がデータを保持していない、すなわちフリツプフ
ロツプ７０はセツトされ、信号線８３は１になつ
ているとし、回路の動作を順を追つて説明する。

信号線８３は１になつているのでＲゲート７
７、ANDゲート７４、Ｒゲート７６の出力は
それぞれ１になり、クロツク信号９７はANDゲ
ート７３の出力に印加され、転送路２０の状態が
レジスタ４２に取り込まれる。いまレジスタ４２
のフイールド６５が０、すなわちEXISTフイー
ルドが０の時、処理部４５は信号線８２によりパ
ケツトが致着していないことを検出し何もしな
い。このフイールド６５が０である状態は、
ANDゲート７５を介して信号線９１により次報
の処理装置へ伝えられる。

つぎにEXISTフイールドが１かつフイールド
６６のFULLフイールドが１の場合、すなわちデ
ータを格納しているパケツトが到着した場合（上
記(1)）を考える。処理部４５は、処理すべきデー
タを保持していないため、データ線８５を介し、
レジスタ４２の６８に格納されたデータを受けと
り、フリツプフロツプ７０をリセツトし、処理を
開始する。さらに信号線８４を０にし、マルチプ
レクサ７１のＢ入力を選択し、信号線９２を０と
し（FULLフイールドを０とし）、データを格納
していないパケツトを転送することを次段の処理
装置に伝える。この時、信号線８３は０になつて
も信号線８７は１のままであるので、レジスタ４
２の内容はANDゲート７５を介し信号線９１に
そのまま伝えられる。なお信号線８４を０にしマ
ルチプレクサ７１のＢ入力を選択するのは次段の
処理装置がパケツトを受け取るまでの間である。
次段の処理装置がパケツトを受けとつたか否か
は、信号線９５により判断できるが、詳細は後ほ
ど説明する。フリツプフロツプ７０がリセツト状
態の時（すなわち処理中のデータを保持している
時）、レジスタ４２のフイールド６５が０になつ
ても（パケツトが存在しなくなつても）、あるい
はフイールド６５が１、フイールド６６が１とな
つても（データを格納したパケツトが到着して
も：上記(2)）、次段の処理装置にレジスタ４２の
内容がそのまま伝えられることは、回路図から容
易に判る。

さて次に、このフリツプフロツプ７０がリセツ
トの状態の時、空の状態のパケツトが到着した場
合（上記(4)）を想定してみる。すなわちレジスタ
４２のフイールド６５が１、６６が０になつた場
合である。この時まだ処理が終つておらずフリツ
プフロツプ７０はリセツトのままであるとする
と、Ｒゲート７７の出力は０となり、ANDゲ
ート７５の出力は０、さらにＲゲート７６の出
力は、インバータ７８の出力が０であることか
ら、０となり、７３の出力は抑制され、クロツク
がレジスタ４２に印加されず、その内容は不変と
なる。すなわち次のパケツトを受けとれない状態
になつている。この状態になつていることは前段
の装置に信号線９６が０になることにより伝えら
れる。さらにANDゲート７５の出力が０になる
ことにより、次段の処理装置へは、EXISTフイ
ールドが０のデータが送られ、パケツトを転送し
ていないことになる。さて、処理部４５での処理
が終了したとしよう。この時、フリツプフロツプ
７０が信号線８０によりセツトされ、データ線８
６に処理結果を載せ、信号線８４を１とし、マル
チプレクサ７１，７２のＢ入力を選択する。この
時信号線９１，９２は１となり、次段の処理装置
に、処理結果を格納したパケツトを送ることがで
きる。以上説明したように第６図に示す回路によ
り、先に説明した処理装置パケツト転送手順を実
現することができる。

以上の説明の中にもでてきたが、パケツトを次
段の装置へ送ることができない場合がある。その
原因には２つ考えられ、１つは上の説明に出てき
たようにFULLフイールドが０の空状態のパケツ
トを受けとつたが、処理がまだ終つていず、パケ
ツトを次に回せない場合（上記(4)）であり、他の
１つは、その処理装置自身はパケツトを次に送り
得るが、次段の処理装置がパケツトを受け取つて
くれない場合である。前者の場合の動作は先に説
明したとうりＲゲート７７の出力が０になるこ
とにより、ANDゲート７３の出力を抑圧し、ク
ロツクの印加を禁止し、信号線９６により前段の
装置に対しパケツトが受け取れないことを知らせ
ている。後者の場合、次段の処理装置が信号線９
５を０にすることにより、パケツトが受け取れな
いことを知らせてきた場合である。いまレジスタ
４２にパケツトが存在しなければ、次段の状態に
かかわらず前段からパケツトを受けとることがで
きる。第６図において、レジスタ４２のフイール
ド６５が０の場合インバータ７８の出力は１とな
りＲゲート７６の出力は信号線９５の状態にか
かわらず１となり、レジスタ４２にクロツクが印
加され、パケツトを受け取ることができるように
なつている。次にすでにレジスタ４２にパケツト
がある場合を考えてみる。この場合は、インバー
タ７８の出力は０であるので、信号９５の状態が
そのまま９６に伝えられ、前段の装置にパケツト
を受けとれないことを伝えることができる。なお
記憶装置の制御部からも前段の処理装置に対し、
パケツトを受け取れるか否かの信号が出力される
（但し本システムでは制御部はパケツトを格納す
るFIFがあるので常にパケツトが受け取れる状
態になつている）。また本制御部は、次段の処理
装置から送られる、パケツトが受け取り可能か否
かを示す信号に従い、パケツトの送り出しを制御
している。

次に記憶装置１０の制御部の動作を説明する。
その基本的動作は次のような手順でおこなわれ
る。これを制御部パケツト転送手順と呼ぶことに
する。

(1) 処理装置からパケツトを受けとり、そのパケ
ツトがデータを格納している時、第４図に示し
たアドレスカウンタ３２で示す記憶装置の番地
にそのデータを書き込み、パケツトのＮフイー
ルド（第１種のパケツトか否かを示すフイール
ド）をFIF３３に格納する。その後アドレス
カウンタ３２の内容を＋１する (2) 送られてきたパケツトが空ならパケツトのＮ
フイールドをFIF３３にただ格納するだけで
ある (3) 次段の処理装置がパケツトを受けとることが
可能であり、FIF３３の先頭のデータをとり
出しその値が０であれば（第１種のパケツトで
ないことを意味する）、アドレスカウンタ３１
によりデータを読み出し、パケツトを、FULL
フイールドを１、Ｎフイールドを０として構成
し、データとともに次段へ送出する。この時ア
ドレスカウンタ３１の内容を＋１する (4) 次段の処理装置がパケツトを受けとることが
可能であり、FIF３３の先頭のデータを取り
出し１であれば（第１種のパケツトであること
を意味する）、FULLフイールドを０、Ｎフイ
ールドを１とし（データは格納せず）次段の装
置へ送出する。

以上の動作を行なう制御部の回路例を第７図に
示す。パケツトが送られてきたか否かは、転送路
上のEXISTフイールド１０１により判断できる。
１０１が１なら処理装置からパケツトが送られて
きており、その時FULLフイールド１０２が１
（上記(1)）なら１０４上のデータをレジスタ３５
に取り込み、アドレスカウンタ３２を番地として
記憶装置１０に書き込めば良い。この時第１種の
パケツトか否かを示すＮフイールド１０３の値を
FIF３３に格納する。また送られてきたパケツ
トのFULLフイールド１０２が０（上記(2)）なら
データは送られておらず、Ｎフイールドの値を
FIF３３に取り込むだけでよい。これらの制御
は制御回路１００により信号線１１２，１１４，
１１５を介して行なわれる。次段の処理装置がパ
ケツトを受け取れるか否かを示す信号９６が１で
あり（パケツトが受け取れることを示す）、かつ
第１種のパケツトか否かを示すFIF３３からの
出力が０（上記(3)）ならアドレスカウンタ３１を
番地として記憶装置１０から読み出し、レジスタ
３４に格納してあるデータを処理装置に送る。こ
の時転送路２０上のEXISTフイールド６１を１、
FULLフイールド６２を１（パケツトにデータが
格納されていることを示す）、Ｎフイールド６３
を０とする。

FIF３３の出力をそのままフイールド６３
に、インバータ１０７により反転した値をフイー
ルド６２に出力することによりフイールド６２，
６３の制御は簡単に実現できる。またFIF３３
からの出力が１（上記(4)）の時（第１種のパケツ
トである時）、FULLフイールド６２は０、Ｎフ
イールド６３は１となり、データを格納していな
いパケツトを送出したことになる（この場合は記
憶装置１０からの読み出しはおこらない）。記憶
装置１０からの読み出し、FIF３３からのデー
タの取り出しなどは、制御回路１００により信号
線１１２，１１３，１１５を介しておこなわれ
る。なお信号９５は、前段の処理装置に対しパケ
ツトが受けとれるか否かを示す働きをしている
が、この制御部１１にはパケツトを格納するFIF
Ｏ３３があるので、常にパケツトを受け取ること
ができるので常に１になつている。以上説明した
ように、第６図の回路により、前述の制御部パケ
ツト転送手順を実現することができる。

次にこれまで説明してきたパケツトの転送手順
により、データの送受がどのように行なわれるか
を説明する。簡単のため処理装置を３台としてデ
ータの送受法を中心に説明する。第８図ａ〜ｄに
おいて３台の処理装置Ｐ１〜Ｐ３がブロツク１２
０に示されている。記憶装置およびその制御部は
記していないが、その制御部は４つのパケツトを
生成し、記憶装置からデータを読み出し処理装置
に送る。この時４番目のパケツト（第１種のパケ
ツト）はデータを格納しない空の状態で処理装置
に送られる。すなわち３個のデータと、１つの空
きパケツトが組となりブロツク１２１に示すよう
に順々に送出されるわけである。ブロツク１２１
における番号は、識別のためデータに付した番号
であり、空欄はデータが格納されていないことを
示している。最初のデータ１がＰ１に送られた状
態が同図ａであり、Ｐ１はデータを保持していな
いため、データ１を取り込み処理をはじめる。さ
らにパケツトが送り込まれた空パケツトがＰ１に
送られた状態を同図ｂに示す。Ｐ１はデータ１を
保持しておりその処理の終るのを待ち結果をこの
空パケツトに格納する。同図ｂにおいて点線は次
のステツプで行なわれるデータの送受を示してい
る。同図ｃはさらにパケツトの転送が進んだ状態
である。直前のステツプでデータ４がＰ１にとり
込まれており、このデータ４を格納していたパケ
ツト（＊印で示してある）が空パケツトとしてＰ
２に送られている。なおハツチングをほどこして
あるのは、処理された結果であることを示してい
る。同図ｃにおいてＰ２が処理結果を空パケツト
＊に移し、次のステツプでデータ５がＰ２に取り
込まれる。同図ｄは同図ｃより転送が２ステツプ
進んだ様子を示しており、Ｐ３で処理されたデー
タ３と、Ｐ１で処理されたデータ４とが、それぞ
れ空パケツトに移されるところである。このよう
にして処理すべきデータが各処理装置に順に送り
込まれ、制御部は送り込まれた順序で次々と処理
結果を得ることができる。

次に処理装置が４台、データの処理時間が第３
図に示す場合について詳しくそのタイミングを調
べてみる。第９図にその結果が示されている。図
中P₁〜P₄は処理装置、Ｃは制御部を示す。また
添字Ｎは、第１種のパケツトであることを示し、
数字はデータの番号、〇で囲まれているのは、そ
のタイミングで処理装置にデータが取り込まれる
こと、さらに□で囲まれているのは処理結果であ
ることを示している。またｅは空パケツトである
ことを示している。さて制御部は最初に第１種の
パケツトを空状態（e_N）で送出し、続いて処理す
べきデータをパケツトを生成しながら順々に送り
出す。ステツプ５において制御部に第１種のパケ
ツトが戻つて来ており、５個のパケツトが生成さ
れたのでこの時点でパケツトの生成は停止され
る。図からも明らかなようにステツプ２でＰ１に
データ１が、ステツプ４でＰ２にデータ２が、さ
らにステツプ６でＰ３にデータ３が取り込まれて
いる。またステツプ６では、制御部１１は第１種
のパケツト（e_N）を、空状態のままＰ１へ転送し
ている。データ１に対する処理時間は、第３図に
示すように４であり、丁度第６ステツプでその処
理が終了する。すなわち第７ステツプでその結果
が、パケツトに格納されＰ２へ送られている。Ｐ
１はこのステツプ７で送られてきたデータ５を取
り込む、その時空になつたパケツトは第８ステツ
プでＰ２へ送られる。Ｐ２が処理しているデータ
２は、この第８ステツプで処理が終了し、処理結
果を送られてきた空パケツトに格納しＰ３へ送出
する。第９ステツプでＰ２は新しいデータ６を受
けとり、空パケツトを第10ステツプでＰ３へ送
る。第10ステツプで制御部１１にデータ１の処理
結果が得られる。第11ステツプで空パケツトを受
けとつたＰ３は、データ３を処理しているが、そ
の処理は第３図に示すように20ステツプかかるた
めその時点では終了せず、第26ステツプまでその
終了を待つ。したがつて、第26ステツプまでパケ
ツトは停止している。Ｐ３は第27ステツプで処理
結果をＰ４へ送り、次に処理すべきデータ７を受
けとる。Ｐ４で処理されているデータ４は、その
処理時間は10ステツプであり、第28ステツプで空
パケツトを受けた時点では処理は終了しており、
直ちに次のステツプでその結果が制御部１１へ送
られる。以下同様の手順で処理が進められ、制御
部１１から順に送られたデータが、処理されその
順序で処理結果が制御部１１に戻されてくる。な
おステツプ11〜26で制御部に２つのパケツトが存
在しているが、処理装置がまだパケツトを受け取
れる状態にならず、その内部（FIFO）に留めて
いるためである。但し、受け取つた処理結果はそ
のとき記憶装置に書き込んでいる。

第９図から明らかなように、第３図に示す16個
のデータの処理が済み、かつすべての処理結果が
制御部に戻されるまで60ステツプで済んでいる。
これは第２図に関連して述べた処理方式の場合の
100ステツプより大幅に短縮されていることが判
る。

本発明によれば処理装置をリング状に接続して
いるため、その台数を増加することは非常に容易
であり、さらにデータ転送の手順が、装置台数と
無関係であるため、台数が増加したりあるいは故
障等により減少したとしても、その手順を何ら変
更する必要のない、並列データ処理装置を提供す
ることができる。

【図面の簡単な説明】

第１図、第２図は従来の並列データ処理装置の
ブロツク図である。第３図は、あるデータの処理
時間の一例を示す図、第４図は本発明の一実施例
のブロツク図、第５図はデータ転送の際のデータ
の形式を示す図、第６図は本発明の一実施例で用
いた処理装置を示す図、第７図は、本発明の一実
施例で用いる制御部の詳細ブロツク図、第８図及
び第９図は、データ転送の進行状態を示す図であ
る。 １０……記憶装置、１１……制御部、１２〜１
４……処理装置、３１，３２……カウンタ、３
４，３５……レジスタ、３３……FIFO、４２〜
４４……レジスタ、７３〜７８……論理ゲート、
７１，７２……マルチプレクサ。

Claims (1)

1. 【特許請求の範囲】 １ 制御部を有する記憶装置とｎ台の処理装置を
   ノードとしリング状に結合し、前記ノード上をパ
   ケツトにより一方向にデータを転送するシステム
   において、 該パケツトには、データを保持しているか否か
   を示す識別子と、第１種か第２種かの区別を示す
   識別子をもたせ、 前記制御部には、１個の第１種のパケツトとｎ
   個の第２種のパケツトを生成する手段と、これら
   のパケツトを生成した時および、リング上のノー
   ドからパケツトを受け取つた時、第１種のパケツ
   トに対してはデータを保持せしめず空状態とし、
   第２種のパケツトに対しては前記記憶装置より読
   み出したデータを格納せしめ、リング上のノード
   に送出する手段と、さらにノードから送られてき
   たパケツトにデータが格納されている時、該デー
   タを前記記憶装置に格納する手段を持たせ、 さらに各処理装置には、データを保持している
   パケツトを受け取つた時、該処理装置が既にデー
   タを保持しているならそのまま、次のノードへ送
   出し保持していないなら該パケツト内のデータを
   取り込みパケツトを空状態とし次のノードへ送出
   する手段と、空状態のパケツトを受けとつた時、
   該パケツトがデータを保持していなければそのま
   ま次のノードへ、データを保持していれば、該デ
   ータに対する処理の終了を待ちその結果を前記受
   け取つたパケツトに格納し次のノードに送出する
   手段を持たせたことを特徴とする並列データ処理
   装置。