JPH0668053A

JPH0668053A - 並列計算機

Info

Publication number: JPH0668053A
Application number: JP4221592A
Authority: JP
Inventors: Hiroshige Fujii; 洋重藤井; Takashi Yoshida; 尊吉田; Hisatomo Satou; 寿倫佐藤; Masashi Takahashi; 真史高橋
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 1992-08-20
Filing date: 1992-08-20
Publication date: 1994-03-11

Abstract

(57)【要約】【構成】ｎ個のプロセッサ１からなるプロセッサアレ
イと、このプロセッサアレイを制御すると共に、命令列
から並列実行可能な２種類の命令列を抽出してプロセッ
サアレイに供給するプロセッサアレイ制御装置２とを備
え、プロセッサアレイ制御装置２の出力端子ＯＵＴ０，
１から供給される２種類の命令列のうちの１種類を各プ
ロセッサ１が受け取り、２種類の命令列をｎ個のプロセ
ッサ１で並列実行する。【効果】並列度がプロセッサ数より小さい場合でも、
実行時間の短縮とプロセッサの有効利用を図れる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、並列計算機に関する。

【０００２】

【従来の技術】大規模な科学技術計算を高速に実行する
ために、並列計算機が期待されている。並列計算機の１
つとしてＳＩＭＤ型並列計算機がある。ＳＩＭＤ型並列
計算機は、複数のプロセッサ上に配置された複数のデー
タに対して、すべてのプロセッサで同じ命令を実行す
る。この場合、プロセッサ数分だけのデータに対する処
理を並列に実行することになる。

【０００３】一般に、並列計算機上で実行しようとする
プログラムには、並列度というものがあり、それ以上の
プロセッサがあっても、速度は向上しない。例えば、繰
り返し処理を並列実行するときに、１回の繰り返しを１
台のプロセッサで実行することを考えると、１０００回
の繰り返し処理を１００００台のプロセッサで実行して
も、１０００倍以上には速度向上は望めない。したがっ
て、プロセッサの数よりも少ない並列度の問題を解く場
合には、実質的に使用されないプロセッサが多くなり、
無駄である。

【０００４】問題の並列度が少ない場合に、実行時間の
短縮とプロセッサの有効利用を考える必要がある。例え
ば、上述の例では繰り返し処理が複数命令からなり、そ
の複数命令の中で並列に実行できる命令があれば、その
命令を複数のプロセッサで並列実行できる可能性があ
る。しかしながら、このような複数命令の並列実行は、
単一命令を全プロセッサが実行するというＳＩＭＤ型並
列計算機では、実現するのは困難である。

【０００５】ここで、一般的な並列計算機について図６
を用いて説明する。

【０００６】同図で、この並列計算機は、大きく分け
て、１台の制御プロセッサ（ＣＰ）１１と、複数台の演
算プロセッサ（ＰＥ）１２から構成される。制御プロセ
ッサ１１には全体メモリ（Ｍ）１３が接続され、演算プ
ロセッサ１２にはそれぞれローカルメモリ（ＬＭ）１４
が接続される。制御プロセッサ１１と各演算プロセッサ
１２は、グローバルバス１５で接続される。演算プロセ
ッサ１２は、ネットワーク１６で相互接続される。ネッ
トワーク１６の形態としては、格子結合、２進ｎキュー
ブ結合、木結合等、多くのものが知られている。

【０００７】制御プロセッサ１１は、それ自体が一つの
情報処理装置であり、全体メモリ１３に格納されている
プログラム（機械語命令列）を読み込み、解読する。解
読した命令が制御プロセッサ１１で実行すべき命令であ
れば制御プロセッサ１１自身で実行する。解読した命令
が演算プロセッサ１２で実行すべき命令であれば、制御
プロセッサ１１はこの命令をグローバルバス１５を介し
て全演算プロセッサ１２に放送し、演算プロセッサ１２
でこの命令の実行が行われる。

【０００８】制御プロセッサ１１は、グローバルバス１
５を介して、すべての、あるいは特定の演算プロセッサ
１２から、データの読み出し、および書き込みを行うこ
とができる。また、同期バス１７を介して、すべての演
算プロセッサ１２の状態の論理和を認識することができ
る。

【０００９】さらに、制御プロセッサ１１は、フロント
エンド計算機１８と結合されている。フロントエンド計
算機１８では、制御プロセッサ１１および演算プロセッ
サ１２で実行するプログラムの開発を行ったり、処理す
べきデータの入出力を行う。

【００１０】演算プロセッサ１２は、制御プロセッサ１
１から放送される命令に従って、自ローカルメモリ１４
のデータに対して演算を行ったり、ネットワーク１６を
介して他の演算プロセッサ１２とデータ通信を行ったり
して処理を行う。

【００１１】演算プロセッサ１２は、例えば、図３７に
示すような構成になっている。

【００１２】命令レジスタ２４には、制御プロセッサ１
１から放送される命令が、１クロックごとに格納され
る。演算プロセッサ１２を構成する他のすべての要素、
すなわち、アドレスレジスタ（ＡＲ）２６、データレジ
スタ（ＤＲ）２７、状態制御レジスタ（ＰＳＷ）３１、
プロセッサ番号レジスタ（ＰＮＲ）３２、ＡＬＵ２９、
レジスタファイル３０、通信制御部３３は、命令レジス
タ２４の内容によって制御される。

【００１３】制御プロセッサ１１からは、一時期には常
に同じ命令が全演算プロセッサ１２に対して放送され、
全演算プロセッサ１２が一斉に同じ処理を行うことにな
る。いわゆるＳＩＭＤ（Single Instruction Multiple
Data Stream ）方式と呼ばれるものである。一方、各演
算プロセッサ１２が独自にプログラムを持ち、各演算プ
ロセッサ１２が独立して動作する方式も提案されてお
り、ＭＩＭＤ（MultipleInstructionMultiple Data Str
eam）方式と呼ばれる。

【００１４】図３７に示したＳＩＭＤ方式は、ＭＩＭＤ
方式に比較して制御が簡単でハードウェアが少なくてす
み、多くのデータに対して同じ処理を行う必要のある場
合に有効である。しかし、データによって異なった処理
が必要となる場合に、効率よく処理できないという欠点
があり、この場合はＭＩＭＤ方式が有利になる。

【００１５】このような、並列計算機においては、各演
算プロセッサ（演算要素／以下、ＰＥ：Ｐｒｏｃｅｓｓ
ｉｎｇ−Ｅｌｅｍｅｎｔという）間の接続方式がその並
列計算機をどのようにするかがその並列計算機の特徴を
出す大きな要因となっている。ＰＥ間接続方式は大きく
分けて、静的結合と動的結合の２つがある。

【００１６】静的結合は、隣接する通信相手のＰＥが経
路によって固定されているもので、リング結合、トーラ
ス結合、木構造結合などがある。その特徴は、通信経路
が確定しているため、隣接経路のあるＰＥ間でのデータ
通信は速いが、逆に遠くのＰＥ、すなわち他のＰＥを経
由して通信を行わなければならない相手との通信は非常
に遅くなるという問題がある。

【００１７】動的結合は、通信相手が固定でなく、クロ
スバスイッチを多段に設けて通信時にスイッチを切り替
え、通信相手を決定するもので、クロスバネット、オメ
ガネットなどがある。その特徴は、スイッチ群を経由す
ることにより、ほぼ全てのＰＥへの通信距離が等価に見
えることであり、任意のＰＥ間の通信時間がほぼ一定と
なることである。

【００１８】また、ＰＥが故障した場合の故障ＰＥの切
り放しも容易に行うことが出来る。しかし、経路の確定
のためと、スイッチのディレイのために、通信のための
時間がかかり、また、スイッチでのデータの衝突などが
問題となる。

【００１９】これらの結合路の使い分けとして、隣接作
用問題でよく行われる隣のＰＥへのデータ転送では静的
結合である隣接結合路を使用し、任意のＰＥから他の任
意のＰＥへデータを転送するいわゆるランダム通信では
動的結合の通信経路を使用する場合が多い。

【００２０】静的結合網の並列計算機に、サイズの合う
問題を実行させる場合は効率はよいが、サイズの異なる
問題を実行させる場合は、ＰＥ台数が中途半端になり、
非常に効率が落ちてしまう。例えば３２×３２の２次元
トーラス結合の並列計算機に問題サイズ３２×３２×１
０の隣接作用問題を乗せる場合、ｘ軸、ｙ軸をそれぞれ
ＰＥアレイの各辺に対応させれば効率は非常によい。

【００２１】ところが、問題サイズ３０×３０×１０の
問題では、ｘ，ｙ軸をＰＥアレイの各辺に対応させても
それぞれ２行分のＰＥ列が余ってしまう。この場合は、
各２行分が余ったことをプログラマーあるいはコンパイ
ラが認識してこれに見合ったコードを出力しなければな
らない。

【００２２】例えばリング状に隣接ＰＥに接続されてい
る場合、問題サイズのために使用しないＰＥがあれば、
同ＰＥを通過させるために、余分な転送動作を行う必要
があり、各々のＰＥでは使用するＰＥと使用しないＰＥ
の判別動作も必要となってくる。そのため問題サイズと
アレイサイズが一致した場合に比べ、データ転送でのオ
ーバーヘッドにより明らかに処理効率が落ちる。

【００２３】並列計算機の他の特徴としては、各ＰＥの
演算データを保持するメモリの構成も挙げられる。大き
く分けると。共有メモリ型と、分散メモリ型がある。共
有メモリ型は、各ＰＥとメモリ間を共有バスあるいは動
的結合路で結合する場合が多く、比較的プロセッサ台数
が少ない場合に有効である。

【００２４】一方、分散メモリ型は各々のＰＥにローカ
ルメモリを付け、データの共有性を無くするかわりにデ
ータアクセスのコンフリクトを解消している。そのた
め、近年のＰＥ台数の多い並列計算機では、ほぼこの分
散メモリ型で構成されている。

【００２５】分散方式のローカルメモリでは、解く問題
の並列度は低いが１台のＰＥで分担するデータ量が多い
場合、一度に乗せることのできるデータ量は１台のＰＥ
のローカルメモリに依存してしまう。稼動しているＰＥ
よりもＩＤＬＥのＰＥの方が多い場合、本来１台のＰＥ
で受け持つデータを２台のＰＥに振り分け、２台のＰＥ
の連動により、疑似的に１台のＰＥとして処理を行う。
この場合、２台の連動を処理するためのソフトウェアの
オーバーヘッドと、隣接通信が行えないオーバーヘッド
から、処理能力が低下する。

【００２６】以上のように、従来の並列計算機では問題
サイズが異なることによるオーバーヘッドが大きいた
め、以前よりオーバーヘッドを小さくするような並列計
算機が必要とされていた。

【００２７】一方、複数の演算プロセッサを相互結合す
る通信ネットワークは、これらの演算プロセッサを相互
に結合するが、プロセッサの数は非常に多いので、任意
の演算プロセッサから他の全ての演算プロセッサに結合
するための通信経路を備えるのは、物理的にも経済的に
も現実的ではない。

【００２８】そこで、例えば図１９に示すように、相互
に隣接する演算プロセッサ５５間の通信チャネル５６だ
けを備えさせ、隣接せず直接に結合されていない演算プ
ロセッサ５５間では、一つ以上の中継プロセッサを介し
て通信を行う方法がある。

【００２９】このようなプロセッサ間通信方式として
は、例えばW.J.Dally 他の”Deadlock-Free Message Ro
uting in Multiprocessor Interconnection Networks”
（IEEETrans. Comput., vol.C-6, No.5, May 1987)に開
示されているワームホール・ルーティングがある。この
ワームホール・ルーティングでは、メッセージをフリッ
トと呼ばれる小さな単位に分割して通信を行う。通信は
送信側プロセッサから受信側プロセッサまでの経路を確
定して開始され、その経路は通信が終了するまでそのメ
ッセージに占有される。

【００３０】ワームホール・ルーティングは以上のよう
な通信を行うので、あるメッセージの通信が行われてい
る間は、その通信で使用されている通信チャネルを他の
メッセージの通信に使用することはできない。したがっ
て、あるメッセージを構成する全てのフリットの通信が
途中で停止してしまうと、その通信に使用されている通
信チャネルを必要とする通信は、その間ずっと待ち続け
なければならない。すなわち、あるメッセージの通信が
他のメッセージの通信を妨害してしまうという問題があ
る。

【００３１】この問題を解決するために、例えばW.J.Da
lly の”Virtual-Channel Flow Control”（IEEE Tran
s. Para. and Dist. Sys., vol.3, No.2, Mar. 1992）
に開示されているように、各演算プロセッサのメッセー
ジの受信側に複数個のフリットを蓄えることのできるバ
ッファを設ける。

【００３２】こうすることで、通信が停止しているメッ
セージを演算プロセッサ内に蓄え、これがネットワーク
に広がる範囲を狭め、このメッセージがさらに他のメッ
セージの通信を妨害しないようにしてる。

【００３３】このような演算プロセッサの従来例を図３
８に示す。ルータ部５１と演算処理部５２から構成され
る。ルータ部５１はフリットを蓄えるバッファ５３ｘ，
５３ｙ，５３ｐと、フリットの出力先を決定するスイッ
チ５４から構成される。

【００３４】Ｐｉｎ，Ｐｏｕｔはルータ部５１と演算処
理部５２とを接続する通信チャネルである。Ｘｉｎ，Ｘ
ｏｕｔ，Ｙｉｎ，Ｙｏｕｔはそれぞれ隣接する演算プロ
セッサとの間の入力および出力のための通信チャネルで
ある。

【００３５】しかしこのプロセッサを用いた場合、以下
のような問題がある。図３９において、５５ａ〜５５ｅ
は演算プロセッサであり、それそれバッファ５３ｘ，５
３ｙ，５３ｐ、スイッチ５４および演算処理部５２から
構成される。

【００３６】出力先の演算プロセッサ５５ｂのバッファ
が一杯で、通信が停止しているフリット６７が演算プロ
セッサ５５ａのバッファ５３ｘに蓄えられているとす
る。このとき演算プロセッサ５５ｃから演算プロセッサ
５５ａに、別のメッセージのフリット６８が入力される
とする。このメッセージの出力先が演算プロセッサ５５
ｅであるとすると、演算プロセッサ５５ｅのバッファに
空きがあれば、フリット６８は出力されるべきである。

【００３７】ところが、バッファ５３ｘに蓄えられてい
るフリット６７の通信が停止しているため、フリット６
８を出力することができない。すなわち、出力先の通信
チャネルが空いており本来出力されるべきであるメッセ
ージが、通信の停止している他のメッセージによって通
信を妨害される。したがって、並列計算機全体としての
通信時間は増大し、スループットも低下する。

【００３８】ところで、図１９で示した通信方法とは別
に、図２９に示すような、通信方法がある。この方法に
おけるワームホール・ルーティングでは、メッセージを
フリットと呼ばれる小さな単位に分割し、中継プロセッ
サはメッセージが全て到達するのを待たないで、あるフ
リットが到着したら直ちにそのフリットを次のプロセッ
サに転送する。

【００３９】ワームホール・ルーティングを行うプロセ
ッサの構成例を図４０に示す。９０はルータ部で、Ｘｉ
ｎ、Ｘｏｕｔはそれぞれ隣接するプロセッサとの間の入
力および出力チャネルである。Ｐｉｎ、Ｐｏｕｔはルー
タ部９０と演算処理部７２を接続する通信チャネルであ
る。

【００４０】図２９においてプロセッサ７４ａからプロ
セッサ７４ｅへの通信を考える。ワームホール・ルーテ
ィングではハンドシェイクを行って通信を行う必要があ
る。ハンドシェイクのリクエストとアクノリッジとで一
回のフリットの通信が成立するので、一単位時間は２と
考えることができる。Ｄをプロセッサ間の距離、Ｌをフ
リットの数として、図４１のＤ＝４、Ｌ＝４の場合を例
にして、必要な通信時間を考察する。

【００４１】例えばプロセッサ７４ｂからプロセッサ７
４ｃへ先頭フリットを送信している間に、プロセッサ７
４ａはプロセッサ７４ｂに二番目のフリットを送信する
ことができる。同様の考察から、プロセッサ７４ａから
プロセッサ７４ｅまでの通信を考える。

【００４２】先頭フリットがプロセッサ７４ａからプロ
セッサ７４ｅに到達するまでに必要な時間は２×Ｄであ
り、この間に二番目のフリットは、プロセッサ７４ｄに
到達している。したがって、二番目以降の全てのフリッ
トが、プロセッサ７４ａから７４ｅに到達するまでに必
要な時間は２×（Ｌ−１）となる。この結果、ワームホ
ール・ルーティングの場合に必要なプロセッサ間の通信
時間は２×（Ｄ＋Ｌ−１）となる。

【００４３】プロセッサ間通信の他の方式には、特開平
２−２２８７６２に開示されているワームホール・ルー
ティングを変形した方法がある。この方法ではメッセー
ジとともに伝達されるクロックの制御のもとに、プロセ
ッサ間で通信が行われる。ワームホールでは通信を行う
ごとに、ハンドシェイクを行って隣接プロセッサ間で同
期をとらなければならないのに対して、この方法ではい
ったんプロセッサ間の経路が決定してしまえば、クロッ
ク同期にしたがって通信すればよく、ハンドシェイクを
行う必要がない。

【００４４】この方法ではいったん経路が確定した後で
は、ハンドシェイクを行う必要がないので（Ｄ＋Ｌ−
１）で通信が行える。しかし、経路を確定するときと、
経路の確定を送信側プロセッサへ報告するときには、ワ
ームホール・ルーティングと同様にハンドシェイクを行
わなければならず、それぞれ（２×Ｄ）の通信時間を必
要とする。したがってワームホール・ルーティングの変
形を用いた場合に必要なプロセッサ間の通信時間は（５
×Ｄ＋Ｌ−１）となる。図４２にＤ＝４、Ｌ＝４の場合
のタイミング図を示す。

【００４５】プロセッサの数が１，０００を越えるよう
な大規模なネットワークになると、これらのＤの項によ
る影響が無視できなくなる。このとこはＤが大きくなる
とそのメッセージの通信に要する時間が増大するだけで
はない。すなわち、通信中のメッセージがプロセッサや
プロセッサ間のチャネルを占有し、他のメッセージはそ
のプロセッサやチャネルを利用することができなくな
る。

【００４６】そのためプロセッサやチャネルが解放され
るのを待たなければならない。つまり、あるメッセージ
の通信が他のメッセージの通信の妨げとなるわけであ
る。したがってメッセージの通信に時間がかかると、ほ
かのメッセージの障害となる時間も増加し、ネットワー
ク全体での通信時間はさらに増大することになる。

【００４７】

【発明が解決しようとする課題】以上で述べたように、
従来のＳＩＭＤ型並列計算機では、問題の並列度がプロ
セッサよりも大きい場合には、その並列度を生かして高
速に問題を解くことができるが、問題の並列度がプロセ
ッサ数よりも小さい場合には、有効に利用できるのは問
題の並列度分のプロセッサのみで、それ以外のプロセッ
サは遊ぶことになり、問題を解く時間を短縮するのには
役にたたないという問題がある。

【００４８】また、ＳＩＭＤ型並列計算機は、多くのデ
ータに対して同じ処理を行う必要のある場合に有効であ
る。しかし、データによって、異なった処理が必要とな
る場合に、効率よく処理できないという欠点があった。
一方ＭＩＭＤ型並列計算機では、データによって異なる
処理が必要な場合も柔軟に対応できるが、制御が複雑
で、ハードウェアが増大するという欠点があった。

【００４９】さらに、従来の静的結合網の並列計算機で
は、問題のサイズが異なる場合にＰＥ台数がが中途半端
になり、効率が低下してしまったり、データ量が多い場
合に複数台数のＰＥを連動させるためのオーバーヘッド
が大きくなるという問題があった。

【００５０】一方、従来の並列計算機では、出力先の通
信チャネルが空いており、通信が可能であるにも関わら
ず、通信が停止しているメッセージによって他のメッセ
ージの通信が妨害されてしまうという問題があった。

【００５１】また、ネットワークの規模がプロセッサ間
通信に与える影響が大きく、大規模なネットワークでは
通信に非常に時間がかかってしまうという問題もあっ
た。

【００５２】この問題を解決するために、第１の発明
は、問題の並列度がプロセッサ数よりも小さい場合で
も、できるだけ多くのプロセッサを効率よく利用できる
並列計算機を提供することを目的とする。

【００５３】第２の発明は、ＳＩＭＤ型並列計算機に若
干のハードウェアを付加するだけで、ＭＩＭＤ処理を可
能とする並列計算機を提供することを目的とする。

【００５４】第３の発明は、問題のサイズが異なる場合
に、使用されないＰＥをバイパスすることによって処理
効率の低下を防ぎ、さらにデータ量が多い場合に、使用
されないＰＥのローカルメモリを使用されるＰＥからア
クセス可能にすることによってオーバーヘッドを小さく
することができる並列計算機を提供することを目的とす
る。

【００５５】また、第４の発明は、通信可能なメッセー
ジが妨害されずに、通信時間の短縮を可能とする並列計
算機を提供することを目的とする。

【００５６】第５の発明は、通信チャネルおよび制御信
号を中継プロセッサでバイパスすることにより、通信時
間の短縮を可能とする並列計算機を提供することを目的
とする。

【００５７】

【課題を解決するための手段】上記目的を達成するた
め、第１の発明は、複数個のプロセッサからなるプロセ
ッサアレイと、そのプロセッサアレイに対して並列実行
可能な複数種類の命令列を抽出して供給するなどの制御
を行なうプロセッサアレイ制御手段から構成される。

【００５８】各プロセッサは、プロセッサアレイ制御手
段から供給される複数種類の命令列の中の１種類ずつを
受け取る機能と、受け取った命令列を他のプロセッサと
並列に実行する機能とを持つ。

【００５９】また、第２の発明の並列計算機は、大きく
分けて、複数個の演算プロセッサと、これを制御する単
一の制御プロセッサとから構成される。さらに、演算プ
ロセッサは、演算プロセッサでの実行を制御する命令を
格納するためのレジスタと、このレジスタに、制御プロ
セッサからの命令を入力するか、あらかじめメモリに格
納されている命令を格納するかを選択するためのマルチ
プレクサと、レジスタに格納されている命令にしたがっ
て演算を実行する演算部とから構成される。

【００６０】第３の発明は、個々の通信経路で接続され
ている複数の演算要素と、各々の演算要素と個々に結合
しているローカルメモリと、解く問題のサイズに応じて
演算に使用する演算要素と使用しない演算要素とを識別
する識別手段と、この識別手段によって識別された、演
算に使用しない演算要素をバイパスするバイパス手段
と、前記識別手段によって識別された、演算に使用しな
い演算要素と結合しているローカルメモリを、演算に使
用する演算要素から直接アクセス可能にするアクセス手
段とから構成されている。

【００６１】さらに、第３の発明は、前記複数の演算要
素、識別手段、バイパス手段、ローカルメモリ、及びア
クセス手段を１つのチップ上に配置し、前記バイパス手
段及びアクセス手段を前記演算要素上に配線する。

【００６２】また、第４の発明は、複数のプロセッサが
Ｎ次元ネットワークで相互接続され、各プロセッサが、
隣接するプロセッサからメッセージを受信し、出力先を
決定する出力先決定手段と、出力先ごとに設けられ、前
記出力先決定手段によって出力先が決定されたメッセー
ジを受信した順に蓄える蓄積手段と、蓄積されたメッセ
ージを、決定された出力先のプロセッサに出力する出力
手段とから構成される。

【００６３】第５の発明は、複数のプロセッサがＮ次元
ネットワークで相互接続され、各プロセッサが、隣接す
るプロセッサからメッセージおよび制御信号を受信し、
メッセージの宛先を判定する判定手段と、判定されたメ
ッセージが自プロセッサ以外の場合、受信したメッセー
ジおよび制御信号を隣接するプロセッサにバイパスする
バイパス手段とから構成されている。

【００６４】

【作用】上記手段により、第１の発明は、対象とする問
題の並列度が十分大きい場合には、従来のＳＩＭＤ型並
列計算機と同様の動作をさせる。その場合には、プロセ
ッサアレイ制御手段が、プロセッサアレイへ供給する複
数個の命令列をすべて同一の命令列にすることによって
実現できる。各プロセッサは、プロセッサアレイ制御手
段が供給する複数個の命令列の一つを受け取り実行する
ことができるから、複数個の命令列がすべて常に同一で
あれば、すべてのプロセッサが常に同一命令を並列実行
することになる。

【００６５】対象とする問題の並列度がプロセッサ数よ
り小さい場合には、以下のように制御する。ここで、プ
ロセッサアレイ制御手段は、並列実行可能なｍ種類の命
令列を抽出してプロセッサアレイへ供給できるようにな
っており、プロセッサはｎ個あるものとする。そして、
ｎ個のプロセッサをｍ個ずつのｋ組に分ける（すなわ
ち、ｎ＝ｍ×ｋ、ｎ、ｍ、ｋは整数とする）。このｍ個
のプロセッサからなる組をクラスタと呼ぶことにする。

【００６６】各クラスタにはすべて同じｍ種類の命令列
を供給し、同じ処理を行なうように制御する。プロセッ
サアレイ制御手段から供給されるｍ種類の命令列は、各
クラスタ内のｍ個のプロセッサのそれぞれに１種類ずつ
供給され、各プロセッサは、供給された命令列を実行す
る。

【００６７】また、第２の発明は、通常のＳＩＭＤ処理
では、各演算プロセッサは、制御プロセッサから放送さ
れる命令にしたがって処理を行う。制御プロセッサから
指示があると、あらかじめ各演算プロセッサのローカル
メモリに格納されている命令が命令レジスタに格納され
るようにマルチプレクサが切り換わる。各演算プロセッ
サのローカルメモリに異なる命令を格納しておくことに
よって、ＭＩＭＤ処理を行う。

【００６８】さらに、第３の発明は、ＰＥアレイのサイ
ズと問題サイズが異なる場合、コンパイラあるいは他の
手段により、使用するＰＥと、使用しないＰＥを予め決
定し、決定されたＰＥ情報を識別手段に送る。識別手段
では、ＰＥ毎の使用する／しないの情報を保持してお
く。

【００６９】処理実行時に隣接通信を行う際、各ＰＥの
バイパス手段は自ＰＥに対応する識別手段から、バイパ
スを行うかどうかが指示される。稼動中のあるＰＥは、
隣のＰＥが休止である場合、休止のＰＥのバイパス手段
により、さらに先の稼動中のＰＥがあたかも隣のＰＥに
見える。

【００７０】以上から、処理する問題のサイズに合わせ
て使用するＰＥと使用しないＰＥを適切に選択すること
により、解く問題に最適なハードウェアのアレイサイズ
を用意する。

【００７１】また、アクセス手段に予め休止となるＰＥ
のローカルメモリをアクセスする稼動ＰＥの情報を与え
ておき、同情報と識別手段の情報から、稼動するＰＥは
休止しているＰＥのローカルメモリに直接アクセスし、
同ローカルメモリを稼動するＰＥのローカルメモリの一
部として使用する。

【００７２】さらに、バイパス手段とアクセス手段を、
同一チップ内に納められた複数ＰＥに適用する事によ
り、高速な動作を保証すると共に、バイパス手段及びア
クセス手段をＰＥの上に配線することにより配線面積を
小さくし、チップ面積の縮小を行う。

【００７３】第４の発明の並列計算機によれば、メッセ
ージの出力先の決定後にフリットをバッファに蓄えるの
で、出力先チャネルが空いていれば、通信が停止してい
る他のメッセージによってそのメッセージの通信が妨害
されることはない。したがって、並列計算機全体として
通信時間は短縮され、スループットは向上する。

【００７４】第５の発明の並列計算機によれば、あるプ
ロセッサが隣接するプロセッサからメッセージを受け取
り、そのメッセージが自プロセッサ宛でなければ、通信
チャネルと制御信号をバイパスする。メッセージの中継
を行うプロセッサで、メッセージおよび制御信号をバイ
パスし、通信を行っているプロセッサ間の距離を実際よ
りも小さくしている。

【００７５】

【実施例】以下、図面を参照しながら本発明の実施例を
説明する。

【００７６】第１の発明第１の発明の一実施例の構成を図１に示す。図１に示し
た並列計算機は、ｎ個（ｎは整数）のプロセッサ１から
なるプロセッサアレイと、プロセッサアレイに対して命
令を供給するプロセッサアレイ制御装置２とからなる。
図示していないが、プロセッサ１間およびプロセッサ１
とプロセッサアレイ制御装置２間には、データ転送と制
御のための通信ネットワークが存在する。

【００７７】なお、今回の実施例では、プロセッサアレ
イ制御装置２が２種類の命令列を供給する場合について
示すが、第１の発明はこれに限らず、複数種類の命令列
を供給することができるものである。

【００７８】プロセッサアレイ制御装置２は、命令メモ
リを持ち、そこから命令を取り出し、プロセッサアレイ
に対して１度に２個の命令を供給することができる。各
プロセッサ１は、プロセッサアレイ制御装置２から同時
に供給された２個の命令のうちの１つの命令を受け取り
実行する。

【００７９】具体的には、プロセッサ番号が偶数のプロ
セッサ１はプロセッサアレイ制御装置２の出力端子ＯＵ
Ｔ０から出力される命令列の命令を受け取り実行し、プ
ロセッサ番号が奇数のプロセッサ１は出力端子ＯＵＴ１
から出力される命令列の命令を受け取り実行する。

【００８０】各プロセッサ１は、演算部、レジスタファ
イル、制御部、ローカルメモリ、メモリインターフェー
ス部、プロセッサ間通信部からなる。これらのプロセッ
サ１には２つの動作モードがある。１つは、各プロセッ
サ１が独立に動作するレジスタ非共有モードであり、も
う１つは、隣のプロセッサ１とレジスタを共有するレジ
スタ共有モードである。

【００８１】ここでいうレジスタの共有とは、自分のプ
ロセッサ１内のレジスタの内容が対応する相手のレジス
タの内容と常に同じようになっているということであ
る。つまり相手のプロセッサ１内のレジスタにデータを
書き込んだ後に、自分の対応するレジスタを読み出すと
相手のプロセッサ１が書き込んだデータと同じデータが
読み出せるというものである。

【００８２】プロセッサ番号が偶数のプロセッサ１は、
自分のプロセッサ番号より１つ大きい番号をもつプロセ
ッサ１とレジスタを共有し、プロセッサ番号が奇数のプ
ロセッサ１は、自分のプロセッサ番号より１つ小さいプ
ロセッサ１とレジスタを共有する。

【００８３】まず、プロセッサ数よりも並列度が大きい
処理を実行する場合について説明する。この場合には、
プロセッサ１の動作モードはレジスタ非共有モードと
し、すべてのプロセッサ１に同じ処理を実行させるため
に同じ命令を供給するようにする。そのためには、この
実施例では、プロセッサ１ごとに供給される命令列は固
定されているので、プロセッサアレイ制御装置２の２つ
の出力端子ＯＵＴ０，１から同一の命令列を供給するこ
とにより、１つの命令列を２つの命令列として供給する
ように制御する。

【００８４】次にプロセッサ数よりも並列度が小さい処
理を実行する場合について説明する。この場合には、プ
ロセッサ１の動作モードはレジスタ共有モードとする。
プロセッサ番号が偶数のプロセッサ１とその番号より１
つ大きい番号のプロセッサ１とが１つのクラスタを構成
する。

【００８５】クラスタ内の２つのプロセッサ１には、プ
ロセッサアレイ制御装置２によって抽出された並列実行
可能な２つの命令が出力端子ＯＵＴ０，１からそれぞれ
のプロセッサ１に同時に供給され、それぞれのプロセッ
サ１では供給された各命令を並列に実行する。

【００８６】ここで、図２のような式の計算をする場合
について説明する。例えば、プロセッサ数ｎが１０００
であるとする。

【００８７】この計算を１０００組のデータに対して行
なう場合には、プロセッサ１のモードをレジスタ非共有
モードにし、プロセッサアレイ制御装置２の出力端子Ｏ
ＵＴ０，１から、図３（ａ），（ｂ）のような同一な命
令列１，２を供給する。各プロセッサ１に１組ずつのデ
ータの処理を割当てることにより、１個のプロセッサ１
で１０００組のデータを処理するのに比べ１０００分の
１の時間で処理できる。

【００８８】しかし、このレジスタ共有モードで５００
組のデータを処理する場合は、１個のプロセッサ１で５
００組のデータを処理するのと比べ、プロセッサ数が１
０００であるのに５００分の１の時間でしかなく、並列
計算機の能力を十分に生かしきれない。

【００８９】一方、プロセッサ１のモードをレジスタ共
有モードにし、プロセッサアレイ制御装置２から図４
（ａ），（ｂ）のような並列実行可能な２種類の命令列
１，２を出力端子ＯＵＴ０，１からそれぞれ供給する
と、２台のプロセッサ１で１組のデータを処理すること
になり、１０００分の１の時間で実行することが可能で
ある。

【００９０】図３の命令列では、１回の処理を行なうの
に４命令分実行時間がかかるが、図４の場合には、２命
令分の実行時間ですみ、実行時間が半分になる。したが
って、５００組のデータに対する処理の場合でも図４の
命令列で実行させれば、１個のプロセッサ１で処理する
場合に比べて１０００分の１の時間で実行することが可
能である。

【００９１】なお、プロセッサアレイ制御装置２が供給
する並列実行可能な複数の命令は、もともとメモリ上に
並列実行可能な複数の命令列を用意しておき、それを供
給するという方法と、単一の命令列を用意しプロセッサ
アレイ制御装置２内で並列実行可能な命令を抽出して複
数命令を供給するという方法が考えられるがどちらでも
良い。後者の場合には、通常のＳＩＭＤ型並列計算機と
のオブジェクト互換性が保たれることになるため、その
点は有利である。

【００９２】図１に示した実施例では、複数供給される
命令列のうちのどちらを各プロセッサ１が受け取るかが
固定されているが、図５に示すように、いずれの命令列
を受け取るかをセレクタ３で選択できるようにする構成
もある。この構成では、すべてのプロセッサ１は、プロ
セッサアレイ制御装置２から供給される２つの命令列の
どちらでも選択して受け取ることができる。

【００９３】その選択は各プロセッサ１の命令入力の前
におかれているセレクタ３で行なわれ、どちらを選ぶか
は、あらかじめ設定することもできるし、各プロセッサ
１の演算結果からどちらを選択するかを決定することも
できる。クラスタを構成する際には、並列実行可能な２
つの命令列を受け取った２つのプロセッサ１で構成すれ
ば良い。

【００９４】この場合、ｉｆ−ｔｈｅｎ−ｅｌｓｅのよ
うな処理を実行するときに、ｔｈｅｎ処理とｅｌｓｅ処
理を並列に実行するように２つの命令列を出力端子ＯＵ
Ｔ０，１からそれぞれ供給し、各プロセッサ１はｉｆ文
の条件によりいずれかの命令列を選択するようにすれ
ば、ｉｆ−ｔｈｅｎ−ｅｌｓｅの並列実行が可能であ
る。

【００９５】ｓｕｐｅｒｓｃａｌａｒあるいはＶＬＩＷ
などの複数命令の並列実行機構を持ったプロセッサなど
を要素プロセッサとして用いる場合には、並列度の高い
問題を解く場合でも、問題の並列度を犠牲にして複数命
令の並列実行をすることになり、必ずしも効果があがる
とはかぎらないが、この第１の発明では、並列度の高い
問題では、問題の並列性を利用して解くことができるの
で、高速に解くことが可能である。

【００９６】第２の発明図６は、第２の発明の並列計算機に係わる一実施例の構
成を示すブロック図である。

【００９７】同図に示す並列計算機は、大きく分けて、
１台の制御プロセッサ（ＣＰ）１１と、複数台の演算プ
ロセッサ（ＰＥ）１２から構成される。制御プロセッサ
１１には全体メモリ（Ｍ）１３が接続され、演算プロセ
ッサ１２にはそれぞれローカルメモリ（ＬＭ）１４が接
続される。制御プロセッサ１１と各演算プロセッサ１２
は、グローバルバス１５、および同期バス１７で接続さ
れる。演算プロセッサ１２は、ネットワーク１６で相互
接続される。ネットワーク１６の形態としては、格子結
合、２進ｎキューブ結合、木結合等、多くのものが知ら
れており、いずれの方式でもよい。

【００９８】制御プロセッサ１１は、それ自体が一つの
情報処理装置であり、全体メモリ１３に格納されている
プログラム（命令列）を読み込み、解読し、解読結果に
したがって、全体メモリ１３に格納されているデータに
対して、処理を行う機能を有する。さらに制御プロセッ
サ１１には、演算プロセッサ１２に対して制御を行う機
能が追加されている。

【００９９】全体メモリ１３に格納されている制御プロ
セッサ１１のプログラムには、制御プロセッサ１１自身
での処理を指示する命令の他に、演算プロセッサ１２で
の処理を指示する命令が含まれている。

【０１００】制御プロセッサ１１は、メモリ１３から読
み出した命令を解読し、制御プロセッサ１１で実行すべ
き命令であれば、制御プロセッサ１１で実行する。解読
した命令が演算プロセッサ１２で実行すべき命令であれ
ば、グローバルバス１５を介して全演算プロセッサ１２
に放送する。ここで放送する命令は、解読済みのもの
（マイクロ命令）でも解読前のもの（機械語命令）でも
よいが、ここでは解読済みの命令を放送するものとして
話を進める。

【０１０１】制御プロセッサ１１は、グローバルバス１
５を介して、すべての、あるいは特定の演算プロセッサ
１２から、データの読み出し、および書き込みを行うこ
とができる。また、同期バス１７を介して、すべての演
算プロセッサ１２の状態の論理和を認識することができ
る。

【０１０２】さらに制御プロセッサ１１は、フロントエ
ンド計算機１８と結合されている。フロントエンド計算
機１８では、制御プロセッサ１１および演算プロセッサ
１２で実行するプログラムの開発を行ったり、処理すべ
きデータの入出力を行う。

【０１０３】フロントエンド計算機１８と制御プロセッ
サ１１は、実行時、制御プロセッサ１１で実行するべき
プログラムをフロントエンド計算機１８から全体メモリ
１３に転送する。さらに、制御プロセッサ１１で実行す
べきデータをフロントエンド計算機１８から全体メモリ
１３に転送したり、演算プロセッサ１２で実行するべき
データを、フロントエンド計算機１８から各演算プロセ
ッサ１２に分配したり、あるいは処理結果を各演算プロ
セッサ１２や全体メモリ１３からフロントエンド計算機
１８に転送したりする機能を有する。

【０１０４】演算プロセッサ１２は、制御プロセッサ１
１からグローバルバス１５を介して放送される命令にし
たがって、自ローカルメモリ１４のデータに対して演算
を行ったり、ネットワーク１６を介して他の演算プロセ
ッサ１２とデータ通信を行ったりして処理を行う。

【０１０５】第２の発明の中心となる演算プロセッサ１
２は、図７に示すような構成になっている。

【０１０６】まず、ローカルメモリ１４と演算プロセッ
サ１２とは、メモリアドレスバス２１と、メモリデータ
バス２２によって接続されている。

【０１０７】マルチプレクサ（ＭＵＸ）２３は、第２の
発明において追加されたものであり、命令レジスタ２４
に格納する命令として、制御プロセッサ１１からグロー
バルバス１５を介して放送される命令か、ローカルメモ
リ１４から読み出されたデータかを選択する。マルチプ
レクサ２３の一方の入力は、制御プロセッサ１１からの
グローバルバス１５が、もう一方の入力には、メモリデ
ータバス２２がそれぞれ接続されている。

【０１０８】命令レジスタ２４には、マルチプレクサ２
３で選択された命令が格納される。演算プロセッサ１２
を構成する他のすべての要素は、命令レジスタ２４から
の指示によって制御される。ここでは説明を容易にする
ために、命令レジスタ２４の最上位ビットでマルチプレ
クサ２３の制御を行うこととし、最上位ビットが０なら
ば、制御プロセッサ１１から放送される命令が命令レジ
スタ２４に格納され、最上位ビットが１ならば、ローカ
ルメモリ１４から読み出されるデータが命令レジスタ２
４に格納されるものと仮定して話を進める。

【０１０９】プログラムカウンタ（ＰＣ）２５は、第２
の発明をより効果的にするために追加されたものであ
り、ローカルメモリ１４に格納されているＭＩＭＤ処理
用の命令列を読み出すために用いられる。プログラムカ
ウンタにＭＩＭＤ用命令列のアドレスを格納し、読み出
し操作を行うことによって、メモリデータバス２２に命
令が読み出される。命令列を連続して読み出すために、
プログラムカウンタ２５には、自分自身の値をインクリ
メントする機能を持つ。

【０１１０】アドレスレジスタ（ＡＲ）２６、データレ
ジスタ（ＤＲ）２７は、ローカルメモリ１４をアクセス
するために用いられる。アドレスレジスタ２６は、内部
バス２８から書き込まれ、メモリアドレスバス２１に値
を出力する。データレジスタ２７は、メモリデータバス
２２と内部バス２８との間に置かれる双方向のレジスタ
である。

【０１１１】データ読み出し時は、内部バス２８からア
ドレスレジスタ２６に、読み出すべきメモリ１３のアド
レスが格納され、ローカルメモリ１４に対して読み出し
操作を行い、読み出されたデータはメモリデータバス２
２からデータレジスタ２７に格納される。データ書き込
み時は、アドレスレジスタ２６に書き込むべきメモリ１
３のアドレスを格納し、データレジスタ２７に書き込み
データを格納し、書き込み操作を行うことにより、書き
込みが行われる。

【０１１２】ＡＬＵ２９は、内部バス２８を介して、レ
ジスタファイル３０に格納されるデータに対して、算術
あるいは論理演算を行う。

【０１１３】状態制御レジスタ（ＰＳＷ：Prosessor St
atus Word ）３１は、ＡＬＵ２９での演算状態を表示す
るビットと、演算プロセッサ１２での演算を制御するビ
ットから構成される。演算を制御するビットの内訳は次
の通りである。このうち、（１）〜（３）は、演算のＡ
ＬＵ２９で演算が行われるたびに設定される。（４），
（５）は、直接、状態制御レジスタ３１を書き換えるこ
とによって設定する。

【０１１４】（１）ゼロビット：演算結果がゼロになる
とセットされる。

【０１１５】（２）正ビット：演算結果が正のときにセ
ットされる。

【０１１６】（３）オーバーフロービット：演算でオー
バーフローが発生したときにセットされる。

【０１１７】（４）同期ビット：全演算プロセッサ１２
の同期ビットはワイアード・オア接続され、制御プロセ
ッサ１１に接続される。同期を取る時点で演算プロセッ
サ１２がこのビットをセットすると、制御プロセッサ１
１は、全演算プロセッサ１２が同期ビットをセットした
か否かを認識できる。

【０１１８】（５）マスクビット：このビットがセット
されると、以後、制御プロセッサ１１からマスク解除命
令が発行されるまで、命令レジスタ２４の内容にかかわ
らず、演算プロセッサ１２は動作しない。

【０１１９】プロセッサ番号レジスタ（ＰＮＲ：Porces
sor Number Register ）３２は、各演算プロセッサ固有
のプロセッサ番号が格納されるレジスタである。このレ
ジスタを読み出すことによつて、自分のプロセッサ番号
を知ることができる。このレジスタはハードウェア的に
設定する方法や、システム立ち上がり時に制御プロセッ
サ１１が設定する方法等が考えられる。ここではハード
ウェア的に設定されているものとするが、他の方法でも
差し支えない。

【０１２０】通信制御部３３は、ネットワーク１６を介
して他の演算プロセッサ１２と通信したり、グローバル
バス１５を介して制御プロセッサ１１との通信を行うた
めのレジスタや外部の通信プロトコル制御装置から構成
される。演算プロセッサ１２は、この通信制御部３３に
よって、制御プロセッサ１１や他の演算プロセッサ１２
と通信を行うことができる。

【０１２１】命令レジスタ２４への命令の格納は、前述
したように、次の２通りの方法で行われる。第一の方法
は、制御プロセッサ１１より放送されるものである。制
御プロセッサ１１から全演算プロセッサ１２に同一の命
令が放送されるため、マスクビットがセットされていな
い演算プロセッサ１２は、すべて同じ処理を行う。すな
わち、ＳＩＭＤ方式の並列処理が行われる。

【０１２２】第２の方法は、ローカルメモリ１４にあら
かじめ格納されている命令を読み出して、命令レジスタ
２４に格納するものである。この命令は、あらかじめ各
演算プロセッサ１２で異なったものを格納しておくこと
により、各演算プロセッサ１２で異なった処理を行うこ
とができる。すなわち、ＭＩＭＤ方式の並列処理とな
る。

【０１２３】以下では、ＳＩＭＤ方式とＭＩＭＤ方式の
２つの処理方式、およびこの２つの処理方式間の以降を
中心に、本並列計算機での処理手順について説明する。

【０１２４】まず、第２の発明の並列計算機で実行する
プログラムについて説明する。このプログラムは、大き
く次の３つに分けられる（１）逐次処理される部分。

【０１２５】ループ制御等、並列処理できない部分で、
制御プロセッサ１１で実行される。（２）各演算プロセッサ１２が一斉に処理を行う部分
（ＳＩＭＤ処理）。

【０１２６】制御プロセッサ１１により、各演算プロセ
ッサ１２が同じ処理を行う。

【０１２７】（３）各演算プロセッサ１２で異なった処
理を行う部分（ＭＩＭＤ処理）。

【０１２８】制御プロセッサ１１の制御を離れて、各演
算プロセッサ１２が独自に実行する。

【０１２９】このうち、（１）と（２）は、制御プロセ
ッサ用プログラムとしてコンパイルされ、機械語命令列
が全体メモリ１３にロードされる。そして、制御プロセ
ッサ１１が解読、実行あるいは実行制御を行う。（３）
は各演算プロセッサ用としてコンパイルされ、さらにマ
イクロ命令列に展開された後、実行される演算プロセッ
サ１２のローカルメモリ１４にロードされる。

【０１３０】次に、初期データのマッピング処理につい
て説明する。

【０１３１】全体メモリ１３に、制御プロセッサ１１で
実行される命令とデータがフロントエンド計算機１８か
ら転送される。

【０１３２】次に、各演算プロセッサ１２のローカルメ
モリ１４に、演算データと、ＭＩＭＤ動作されるべき命
令とが格納される。これらのデータは、各演算プロセッ
サ１２によって異なるため、演算プロセッサ１２ごとに
逐次的に行われる。処理手順は次の通りである。

【０１３３】（１）制御プロセッサ１１は、全演算プロ
セッサ１２に対して、データを転送する演算プロセッサ
番号と、マスク命令を放送する。

【０１３４】（２）各演算プロセッサ１２は、制御プロ
セッサ１１からの命令に従って、制御プロセッサ１１か
ら放送されるプロセッサ番号と、自分のプロセッサ番号
とを比較し、一致していなければマスクビットをセット
する。したがって以後の処理は、制御プロセッサ１１が
指定した番号の演算プロセッサ１２のみで行われる。

【０１３５】（３）制御プロセッサ１１は、データを格
納するべきローカルメモリ１４の領域の先頭アドレスを
演算プロセッサ１２に転送し、ＤＭＡモードと、制御プ
ロセッサ１１から転送するデータのメモリ１３への書き
込みを指示する命令を発行する。

【０１３６】（４）制御プロセッサ１１は、指定した演
算プロセッサ１２に転送するデータをフロントエンド計
算機１８から取得し、グローバルバス１５を用いて演算
プロセッサ１２に順次転送する。

【０１３７】（５）指定された演算プロセッサ１２は、
制御プロセッサ１１から転送されるデータを、指定され
たローカルメモリ１４の領域に、ＤＭＡモードで順次書
き込む。

【０１３８】（６）転送が終了すると、制御プロセッサ
１１は、ＤＭＡ中止命令と、マスク解除命令を全演算プ
ロセッサ１２に対して発行する。

【０１３９】（７）以上で述べた（１）〜（６）の処理
を全演算プロセッサ１２に対して行う。

【０１４０】ＭＩＭＤ方式の並列処理を行うにあたっ
て、ＭＩＭＤ用命令アドレステーブルを作成する必要が
ある。このアドレステーブルの作成方法を下記に示す。

【０１４１】ＭＩＭＤ動作される命令列は、初期データ
マッピング時は、演算データと区別されることなくロー
カルメモリ１４に格納される。連続した命令列は、ロー
カルメモリ１４の連続したアドレスに格納されることが
望ましい。また、同一時刻にＭＩＭＤ処理される命令列
の開始アドレスは、各演算プロセッサ１２で同じである
ことが望ましいが、異なっていても実行可能である。

【０１４２】ＭＩＭＤ動作される命令列の開始アドレス
は、各演算プロセッサ１２で同一の場合は制御プロセッ
サ１１または演算プロセッサ１２が、各演算プロセッサ
１２で異なる場合は演算プロセッサ１２が認識しておく
必要がある。

【０１４３】図８に、各演算プロセッサ１２でＭＩＭＤ
動作命令開始アドレスが同一の場合の制御プロセッサ１
１のアドレステーブルの一例を示す。アドレステーブル
はどの領域に作成してもよいが、ここでは全体メモリ１
３の０番地から作成されるものと仮定する。同一時期に
ＭＩＭＤ動作される命令列の開始アドレスが、各演算プ
ロセッサ１２で異なる場合は、各演算プロセッサ１２が
ローカルメモリ１４中にアドレステーブルを作成する必
要がある。

【０１４４】以下に、ＳＩＭＤ方式による処理を説明す
る。

【０１４５】第２の発明の並列計算機における制御プロ
セッサ１１から放送される命令により、全演算プロセッ
サ１２が同一の処理を行う方式である。制御プロセッサ
１１は、全体メモリ１３から命令を読み込み、解読した
結果、それが演算プロセッサ１２で実行すべきものなら
ば、グローバルバス１５を介して全演算プロセッサ１２
に放送する。各演算プロセッサ１２では、制御プロセッ
サ１１から放送される命令を命令レジスタ２４に入力す
るように、マルチプレクサ２３を制御する。

【０１４６】マルチプレクサ２３の制御は、命令レジス
タ２４の最上位ビットで行われ、最上位ビットが０なら
ば、制御プロセッサ１１から放送される命令が命令レジ
スタ２４に格納される。したがって、制御プロセッサ１
１から放送されるＳＩＭＤ処理用の命令は、最上位ビッ
トは常に‘０’となるように制御プロセッサ１１を設計
する必要がある。命令レジスタ２４の各ビットが、演算
プロセッサ１２の他の構成要素を制御することによって
処理が行われる。

【０１４７】次に、ＳＩＭＤ方式からＭＩＭＤ方式へ移
行する処理手順を説明する。

【０１４８】制御プロセッサ１１の命令には、各演算プ
ロセッサ１２のローカルメモリ１４に格納されている命
令列に実行を移行するための命令が用意されている。こ
の命令は、図８に示すアドレステーブルの番号を指定す
るフィールドを持つ。この命令が制御プロセッサ１１で
実行されると、次のような手順で各演算プロセッサ１２
のＭＩＭＤ用命令列に処理が移行される。

【０１４９】（１）アドレステーブルから命令列の開始
アドレス読み出され、グローバルバス１５を介して全演
算プロセッサ１２に放送される。

【０１５０】（２）制御プロセッサ１１からの命令によ
る制御で、各演算プロセッサ１２で、（１）で転送され
たアドレスが、プログラムカウンタ２５に格納される。

【０１５１】（３）制御プロセッサ１１からの命令によ
る制御で、各演算プロセッサ１２で、プログラムカウン
タ２５で示されるローカルメモリ１４のアドレスから、
ＭＩＭＤ処理のための命令が読み出される。このときの
制御プロセッサ１１からの命令は、最上位ビットが
‘１’になっている。したがって、次の命令レジスタ２
４の入力は、ローカルメモリ１４から読み出されたＭＩ
ＭＤ用命令が選択されるよう、マルチプレクサ２３が切
り換わる。

【０１５２】（４）ローカルメモリ１４から読み出され
た命令は、命令レジスタ２４に格納され、命令レジスタ
２４からの指示によって処理が行われる。この処理は、
各演算プロセッサ１２で異なっていても良いため、ＭＩ
ＭＤ処理となる。

【０１５３】次に、ＭＩＭＤ方式に移行した後の処理を
以下に示す。

【０１５４】前述したように、ＭＩＭＤ処理が開始され
たとき、プログラムカウンタ２５には、ＭＩＭＤ用命令
列の先頭アドレスが格納されている。プログラムカウン
タ２５は、命令レジスタ２４からの制御によってインク
リメントされる機能を備えている。これによって、ロー
カルメモリ１４に格納されたＭＩＭＤ用命令列を順次読
み出すことができる。

【０１５５】また、命令レジスタ２４に格納される命令
の選択は、現在の命令レジスタ２４の最上位ビットで決
定される。すなわち最上位ビットが‘１’ならば、ロー
カルメモリ１４から読み出した命令が命令レジスタ２４
に格納される。

【０１５６】したがって、ローカルメモリ１４に格納さ
れるＭＩＭＤ処理用命令列は、最上位ビットを‘１’に
し、さらにプログラムカウンタ２５をインクリメントし
ながらローカルメモリ１４を読み出すように制御コード
を設定しておけば、ローカルメモリ１４の命令列を順次
命令レジスタ２４にロードして、ＭＩＭＤ処理が可能で
ある。命令列の最後尾は、最上位ビットを‘０’にして
おけば、ＭＩＭＤ処理終了後、制御プロセッサ１１から
の命令が命令レジスタ２４にロードされるように、マル
チプレクサ２３が制御される。

【０１５７】もちろん、単一の命令に、上記の最後尾の
命令の設定を行っておけば、単一の命令のＭＩＭＤ動作
も可能である。

【０１５８】最後に、ＭＩＭＤ方式からＳＩＭＤ方式へ
の移行処理を説明する。

【０１５９】ＭＩＭＤ処理の終了は、各演算プロセッサ
１２でまちまちであるため、制御プロセッサ１１は、全
演算プロセッサ１２でのＭＩＭＤ処理の終了を確認して
からＳＩＭＤ処理を開始する必要がある。

【０１６０】（１）制御プロセッサ１１は、各演算プロ
セッサ１２でのＭＩＭＤ処理を起動した後、待ち状態に
入る。この状態では、制御プロセッサ１１は、演算プロ
セッサ１２に対してＮＯＰ（No Operation）コードを発
行し続ける。

【０１６１】（２）演算プロセッサ１２はＭＩＭＤ処理
を行うが、ＭＩＭＤ処理用命令列の最後尾の命令とし
て、状態制御レジスタ３１の同期ビットをセットし、さ
らに最上位ビットを‘０’にした命令を挿入しておく。

【０１６２】（３）各演算プロセッサ１２では、ＭＩＭ
Ｄ処理用命令列の最後のコードを実行すると、状態制御
レジスタ３１の同期ビットがセットされ、さらに命令レ
ジスタ２４への入力が、以後は制御プロセッサ１１が発
行する命令を選択するようにマルチプレクサ２３が切り
換わる。各演算プロセッサ１２の同期ビットはワイヤー
ド・オア接続され、制御プロセッサ１１は、全演算プロ
セッサ１２で同期ビットが１にセットされたか否かを認
識できる。

【０１６３】（４）制御プロセッサ１１は、（１）で演
算プロセッサ１２のＭＩＭＤ処理を起動した後、全演算
プロセッサ１２で同期ビットに１がセットされたことを
認識するまでＮＯＰ命令を発行し続ける。早く処理が終
わった演算プロセッサ１２は、制御プロセッサ１１から
ＮＯＰコードを受け取って実行するが、副作用はない。（５）制御プロセッサ１１は、全演算プロセッサ１２の
同期ビットに１がセットされたこと、すなわち全演算プ
ロセッサ１２でＭＩＭＤ処理が終了したことを確認した
ら、ＮＯＰコードの発行を中止し、ＳＩＭＤ処理用の命
令の発行を開始する。

【０１６４】（６）以降は、制御プロセッサ１１からの
命令にしたがって、全演算プロセッサ１２でＳＩＭＤ処
理が行われる。

【０１６５】以上で述べたように、ＳＩＭＤ型並列計算
機にわずかなハードウェア（マルチプレクサ２３，プロ
グラムカウンタ２５）を追加するだけで、ＭＩＭＤ動作
が可能となる。

【０１６６】なお、以上の実施例は、第２の発明を実現
するための一例を示したものであり、これに限定される
ものではない。例えば、命令レジスタ２４への入力の選
択は、命令レジスタ２４の最上位の１ビットを用いて行
ったが、状態制御レジスタ３１の１ビットを用いて行う
ようにすることもできる。この場合の構成図を図９に示
す。

【０１６７】図７と異なる点は、命令レジスタ２４への
入力データを選択するマルチプレクサ２３の制御を、状
態制御レジスタ３１の１ビットを用いて行うことであ
る。このような構成で、ＭＩＭＤ動作を行うための手順
を次に示す。なお、図７の実施例と共通の処理は、記述
を省略した。

【０１６８】１．ＳＩＭＤ処理状態制御レジスタ３１の、マルチプレクサ２３を制御す
るビットを、制御プロセッサ１１からの命令を命令レジ
スタ２４に入力するように設定する。以後、状態制御レ
ジスタ３１のマルチプレクサ２３を制御するビットを書
き換えない限り、演算プロセッサ１２は制御プロセッサ
１１からの命令にしたがって処理を行う。

【０１６９】２．ＭＩＭＤ処理への移行制御プロセッサ１１の命令には、各演算プロセッサ１２
のローカルメモリ１４に格納されている命令列に実行を
移行するための命令が用意されている。この命令は、図
８に示すような命令列の開始アドレスの格納されている
番地を指定するフィールドを持つ。この命令が制御プロ
セッサ１１で実行されると、次のような手順で各演算プ
ロセッサ１２の命令列に処理が移行される。

【０１７０】（１）指定されたアドレステーブルに格納
されている命令列の開始アドレスがグローバルバス１５
を介して全演算プロセッサ１２に放送される。

【０１７１】（２）制御プロセッサ１１からの命令によ
る制御で、各演算プロセッサ１２で、（１）で放送され
たＭＩＭＤ用命令列の開始アドレスが、プログラムカウ
ンタ２５に格納される。

【０１７２】（３）制御プロセッサ１１からの命令によ
る制御で、各演算プロセッサ１２で、プログラムカウン
タ２５で示されるローカルメモリ１４の開始アドレスか
ら、ＭＩＭＤ処理のための命令が読み出され、命令レジ
スタ２４に格納される。

【０１７３】（４）状態制御レジスタ３１の、マルチプ
レクサ２３を制御するビットを、命令レジスタ２４への
入力データとして、ローカルメモリ１４から読み出した
データを選択するように設定する。

【０１７４】（５）命令レジスタ２４からの指示によっ
て処理が行われる。この処理は、各演算プロセッサ１２
で異なっていても良いため、ＭＩＭＤ処理となる。

【０１７５】３．ＭＩＭＤ方式による処理前実施例と同様に、プログラムカウンタ２５には、ＭＩ
ＭＤ用命令列の先頭アドレスが格納されており、この値
をインクリメントさせながら、ローカルメモリ１４から
命令列を順次読み出すことができる。状態制御レジスタ
の設定により、ローカルメモリ１４から読み出された命
令列は、命令レジスタ２４に格納されるようにマルチプ
レクサ２３が制御される。これによって、ローカルメモ
リ１４に格納された命令列を順次読み出し、実行するこ
とができる。

【０１７６】４．ＭＩＭＤ方式からＳＩＭＤ方式への移
行ＭＩＭＤ処理の終了は、各演算プロセッサ１２でまちま
ちであるため、制御プロセッサ１１は、全演算プロセッ
サ１２でのＭＩＭＤ処理の終了を確認してからＳＩＭＤ
処理を開始する必要がある。

【０１７７】（１）制御プロセッサ１１は、ＭＩＭＤ処
理を起動した後、待ち状態に入る。この状態では、制御
プロセッサ１１は、演算プロセッサ１２に対してＮＯＰ
（No Operation）コードを発行する。

【０１７８】（２）各演算プロセッサ１２のＭＩＭＤ処
理用命令列の最後尾に、状態制御レジスタ３１の同期ビ
ットをセットし、かつ、マルチプレクサ２３を制御する
ビットを制御プロセッサ１１からの命令を命令レジスタ
２４に入力するように設定する命令を挿入しておく。

【０１７９】（３）各演算プロセッサ１２では、ＭＩＭ
Ｄ処理用命令列の最後のコードを実行すると、状態制御
レジスタ３１の同期ビットがセットされ、さらに命令レ
ジスタ２４への入力が、以後は制御プロセッサ１１が放
送する命令を入力するようにマルチプレクサ２３が切り
換わる。

【０１８０】（４）制御プロセッサ１１は、（１）で演
算プロセッサ１２のＭＩＭＤ処理を起動した後、全演算
プロセッサ１２で同期ビットに１がセットされたことを
認識するまでＮＯＰ命令を発行し続ける。早く処理が終
わった演算プロセッサ１２は、制御プロセッサ１１から
ＮＯＰコードを受け取って実行するが、副作用はない。（５）制御プロセッサ１１は、全演算プロセッサ１２の
同期ビットに１がセットされたこと、すなわち全演算プ
ロセッサ１２でＭＩＭＤ処理が終了したことを確認した
ら、ＮＯＰコードの発行を中止し、ＳＩＭＤ処理用の命
令の発行を開始する。

【０１８１】（６）以降は、制御プロセッサ１１からの
命令にしたがって、全演算プロセッサ１２でＳＩＭＤ処
理が行われる。

【０１８２】このように、命令レジスタ２４への命令の
入力の選択を、状態制御レジスタによって設定すること
もできる。この方法では、制御レジスタの設定のために
命令が必要となるが、演算結果によって、制御プロセッ
サ１１からの命令列か、メモリ１３に格納されている命
令列かのどちらかを実行するかを選択することも可能
で、より柔軟性の高い処理が実現できる。

【０１８３】以上で述べた実施例では、制御プロセッサ
１１は解読済みの命令、すなわちマイクロ命令を各演算
プロセッサ１２に放送する方法を示した。これに対し
て、解読する前の機械語命令をそのまま放送することも
可能である。この場合、各演算プロセッサ１２に、機械
語を解読したマイクロ命令を発生するための機能を設け
る必要があり、ハードウェア量は増加する。

【０１８４】しかし、近年開発されているＲＩＳＣ（Re
duced Instruction Set Computer）プロセッサでは、機
械語の解読は比較的簡単に行われるため、それほどハー
ドウェア量は増加しないと考えられる。もちろん、この
ような場合でも、第２の発明で示したように、ＳＩＭＤ
処理とＭＩＭＤ処理の両方を可能にする構成が可能であ
る。

【０１８５】第３の発明図１０は、第３の発明の並列計算機に係わる一実施例の
構成を示す図である。同図には、簡単なモデルとして１
次元リング結合の並列計算機を示した。この図に示す通
り、１６個のＰＥ０〜１５がリング状に配置され、各々
のＰＥ０〜１５は隣のＰＥと通信を行うものとする。

【０１８６】問題サイズが１６の倍数の時、分割された
タスクのＰＥへの割り付けは容易である。すなわち例え
ばサイズが１６の場合、ＰＥ０には１番目のタスクを割
り当て、ＰＥ１には２番目のタスクの割り付けを行い、
ＰＥ１５には１６番目のタスクを割り付ける。この場
合、各ＰＥに均等にタスクが割り付けられ、バランス良
く処理を実行できる。

【０１８７】しかし、問題サイズが１０の場合、１６台
のＰＥ０〜１５の内の１０台にタスクを割り付けるが、
例えばＰＥ０からＰＥ９までに割り付けるとする。この
時ＰＥ１０からＰＥ１５までは休止となるので、識別回
路にＰＥ０からＰＥ９までが稼動であり、ＰＥ１０から
ＰＥ１５までが休止である情報をセットする。各ＰＥの
バイパス回路は識別回路からの情報により通信時のバイ
パスを行う。

【０１８８】本例ではＰＥ１０からＰＥ１５のバイパス
回路がバイパスを行う。これによりソフトから見たハー
ドウェアの構成はＰＥ０からＰＥ９までがリング状に接
続された１０台並列の１次元接続の並列計算機となる。
左から順にＰＥ０、ＰＥ１…ＰＥ９と並んでいる場合、
ＰＥ９の右の通信バスはＰＥ０の左側の通信バスに接続
される。

【０１８９】図１１，１２にバイパス回路の詳解図を示
す。図１１はＰＥ間が双方向バスで通信を行う場合のア
ドレス／データバスである。バイパス経路はＰＥを飛び
越すように、ＰＥの右側バスと左側バスに接続する。双
方向バスには双方向３−ｓｔａｔｅバッファ４１を挿入
する。３−ステートバッファには識別回路４２から自Ｐ
Ｅの稼動／休止情報が送られる。ＰＥが稼動の場合は３
−ｓｔａｔｅとなり、休止の場合はバッファがオープン
となり、通信可能となる。

【０１９０】双方向バッファ４１の方向制御は並列計算
機の仕様による。例えばＳＩＭＤ型並列計算機で、同期
的に処理を実行する場合、データの転送方向は全てのＰ
Ｅで同じであるため、ＰＥの制御を行うＡＣＵ（Ａｒｒ
ａｙＣｏｎｔｒｏｌＵｎｉｔ）から転送方向を指定
するだけでよい。

【０１９１】一方、ＭＩＭＤ型並列計算機では、隣接通
信は非同期である場合が多く、そのためハンドシェイク
を行う必要がある。ハンドシェイクには要求信号と許可
信号の信号線が必要となる。この場合、双方向バッファ
４１の方向は、アクセス要求を出した側とアクセスが読
み出しか書き込みかに依存してくる。そのため、バッフ
ァ４１の方向はバッファ４１に付属の制御回路で要求信
号とＲｅａｄ／Ｗｒｉｔｅ信号から決定する。

【０１９２】ＭＩＭＤ型並列計算機で必要となる要求信
号、許可信号、Ｒｅａｄ／Ｗｒｉｔｅ信号などは一方向
の信号である場合が多い。特に今問題としているＰＥ間
での転送は通信相手が固定できるためなおさらである。
通信方向が１方向の場合の詳解図が図１２である。例え
ば右方向への要求信号を考えると、自ＰＥの左のＰＥか
ら自ＰＥに向けられた要求信号と、自ＰＥから右のＰＥ
に送る要求信号を識別回路４２からの稼動／休止の信号
により、セレクタ４３ａで選択して右のＰＥへ送る。

【０１９３】例えば自ＰＥが稼動の場合、右のＰＥに送
る要求信号は自ＰＥからの要求信号をセレクタ４３ａで
選択して送り、自ＰＥが休止している場合は左のＰＥか
ら自ＰＥに送られてくる要求信号を右のＰＥに送る。こ
れにより、自ＰＥが休止の場合は左のＰＥからの要求信
号は直接右のＰＥに送られることになり、バイパスを行
うことが出来る。

【０１９４】上記例ではＰＥ１０からＰＥ１５のかたま
りを休止とした。しかし、このように局地的にかたまっ
て休止にした場合、バイパスする距離が大きくなる。上
記例では６ＰＥ分の距離をバイパスすることになる。図
１１の場合、バイパスの際にはバッファ４１を通過す
る。連続してバイパスする数が増えればそれだけ通過す
るバッファ４１の数は増え、なおかつ物理的な距離も遠
くなり、通信の為の時間が増加してしまう。

【０１９５】上記ＭＩＭＤ型並列計算機でのハンドシェ
イク方式ならば、多少通信時間に誤差が生じても防ぐこ
とが出来るが、ＳＩＭＤ型並列計算機での同期方式で
は、各ＰＥ間での通信所要時間にばらつきがあると、問
題が生ずる。

【０１９６】実際には、転送命令が４０ｎｓで実行しな
ければならず、隣接ＰＥ間で転送する場合２５ｎｓ必要
な場合、バイパス１段を通るのに５ｎｓの遅延が生ずる
とすると、１５÷５で最大３ＰＥ分のバイパスしか許さ
れず、上記例での６個のＰＥのバイパスは不可能とな
る。

【０１９７】そのためバイパスするＰＥを選択する必要
がある。例えば休止にするＰＥを１つおきにすれば、Ｐ
Ｅ間には１ＰＥ分の遅延しか生じなくなる。上記例では
休止するＰＥを例えばＰＥ５，ＰＥ７，ＰＥ９，ＰＥ１
１，ＰＥ１３，ＰＥ１５と選択することにより可能とな
る。上記遅延の制約がある場合、上記１６台並列の計算
機では、４台並列から、１６台並列まで自由に並列台数
を変えることの出来る１次元リング結合並列計算機が実
現できる。

【０１９８】また、上記例では各ＰＥ０〜１５の保有す
るＰＥ番号（０〜１５）を固定としているが、これだと
休止するＰＥがある場合、稼動ＰＥの番号が連続となら
ない。実行するプログラムが連続したＰＥ番号を必要と
する場合は、ＰＥ番号を、稼動するＰＥに与えるデータ
の一変数の値とすることで連続したＰＥ番号とすること
ができる。

【０１９９】第３の発明は仮想プロセッサの概念にも応
用できる。すなわち、１６台並列のＰＥ０〜１５に問題
サイズが１６以上のタスクを割り付ける場合を考える。
タスクの数が１６の倍数の場合、各ＰＥ０〜１５に均等
に割り付けることが出来る。例えば３２のタスクを割り
付ける場合、各ＰＥ０〜１５に２タスクずつ割り付けれ
ば、通常の仮想プロセッサの処理で何等問題ない。

【０２００】すなわち各ＰＥ内部の２つのタスクを処理
するとき、それぞれのタスクを処理するために２つの状
態を示す状態保持手段を用い、タスク１とタスク２を各
々実行するとき上記状態を切り替えることにより、現在
どちらの処理を実行しているかを認識し、仮想プロセッ
サを実現し、１６台で３２のタスクを処理する。

【０２０１】しかし、例えばタスク数が２６の場合、各
ＰＥ０〜１５に均等に割り付けようとすると、タスクを
１個受け持つＰＥと、２個受け持つＰＥとができる。各
ＰＥが受け持つ２つのタスクをタスク１とタスク２とす
ると、タスク１を実行する場合は１６台のＰＥが一斉に
行えば良いが、タスク２を実行する際は１０台のＰＥが
稼動となり、残り６台のＰＥが休止となる。

【０２０２】つまりタスク２を実行する際は、上記例で
の１０個のタスクを実行する場合と同様の状態となる。
そのため、タスク１を実行する場合は１６台全てが稼動
し、タスク２を実行する場合はバイパス回路を使用して
１０台並列の計算機に切り替えて実行を行えば仮想マシ
ンとして２６台並列の並列計算機として使用できる。バ
イパス回路の使用／非使用は、上記状態保持手段に、上
記識別回路４２を連動することにより実現できる。すな
わちタスク１を処理する状態の時、識別回路４２は全て
のＰＥ０〜１５が稼動であるとしてバイパス回路を用い
ず、タスク２を処理する状態の時、識別回路４２は与え
られているＰＥの使用／非使用の情報からＰＥの稼動／
休止を決定し、バイパス回路の使用／非使用を決定す
る。

【０２０３】次に２次元格子トーラス結合の場合を示
す。基本的には１次元リング結合と同様であり、バイパ
スの方向が列方向と行方向の２方向になる。このため、
図１１，１２で示した双方向バッファ４１あるいはセレ
クタ４３も、列方向と行方向の２方向分必要となる。制
御の簡単化を考えると、１次元リング結合で１ＰＥが休
止の対象となったのに対し、２次元格子トーラス結合で
は行あるいは列が休止の対象となる。

【０２０４】図１３に８×８のアレイに問題サイズが６
×５の処理を割り付けた場合を示す。まず行方向に関し
ては、８行のＰＥ列のうち、６行を稼動とする。各ＰＥ
を（Ｘ，Ｙ）で表すとすると、１次元リング結合の場合
と同様に、局所的に休止ＰＥを固めないようにすると、
ＰＥ（０，Ｙ）、ＰＥ（１，Ｙ）、ＰＥ（２，Ｙ）、Ｐ
Ｅ（３，Ｙ）、ＰＥ（４，Ｙ）、ＰＥ（６，Ｙ）の６行
がそれぞれ稼動となる（図中、丸印）。

【０２０５】列方向に関してはＰＥ（Ｘ，０）、ＰＥ
（Ｘ，１）、ＰＥ（Ｘ，２）、ＰＥ（Ｘ，４）、ＰＥ
（Ｘ，６）の５列がそれぞれ稼動となる。休止となった
ＰＥ列のＰＥ（５，Ｙ）、ＰＥ（７，Ｙ）（図中、×
印）は行方向のバイパスを行い、ＰＥ（Ｘ，３）、ＰＥ
（Ｘ，５）、ＰＥ（Ｘ，７）はそれぞれ列方向のバイパ
スを行う。

【０２０６】特に休止の行と列の交差にあるＰＥ（３，
５）、ＰＥ（３，７）等は縦方向と横方向の双方をバイ
パスする。２次元格子トーラス結合において、仮想プロ
セッサを実現する際も、１次元リング結合で挙げた例と
同様にして行うことが出来る。

【０２０７】３次元格子トーラス結合の場合は、休止の
対象が２次元の行／列に対し、面が対象となる。

【０２０８】上記バイパス回路はＰＥと同一チップに納
めたときに有効となる。すなわち１方向に複数のチップ
をバイパスする場合、バイパス経路がチップ外にある場
合よりもはるかに高速にバイパスを行うことが出来る。
特に複数ＰＥ／ｃｈｉｐの場合、さらにバイパスの高速
化を行うことが出来る。

【０２０９】次にメモリアクセスに関して説明する。例
としてまず１６台並列の１次元リング結合の並列計算機
を挙げる。上記例で１６台並列の１次元リング結合型計
算機で問題サイズ１０の処理を行う場合を挙げたが、こ
の時上記並列計算機が分散メモリ型であり、各ＰＥ０〜
１５がローカルメモリ（ＬＭ）を持つ場合、休止となっ
ているＰＥのローカルメモリも使用されないことにな
る。

【０２１０】例えば問題サイズは４だが、１つのタスク
が必要とするメモリ量が１ＰＥの持つメモリの数倍の容
量を必要とする場合もある。通常この場合は１つのタス
クのデータを複数に分け、おおもとのデータ保持部から
随時転送する方法をとる。しかしこの場合、データを分
割したためにデータが分割されていることを意識したプ
ログラムが必要となる。

【０２１１】そこで、休止しているＰＥがある場合、同
ＰＥのローカルメモリを、稼動しているＰＥが使用でき
るようにすることにより、１ＰＥあたりのメモリ容量を
増やすことができる。

【０２１２】図１４に１６台並列１次元リング結合の並
列計算機の例を示す。同例で、上記バイパスに関する実
施例を条件とすると、本並列計算機は４台から１６台ま
でのスケーラブル並列計算機となる。

【０２１３】今、問題サイズが８とすると、稼動するＰ
ＥはＰＥ０，２，４，６，８，１０，１２，１４の８台
となる。各ＰＥが自ＰＥの右側のローカルメモリ（Ｌ
Ｍ）４４を切り換えスイッチ４５で直接アクセス出来る
ようにすると、８台並列で、各ＰＥのローカルメモリ４
４の容量が２倍となる。

【０２１４】問題サイズが５の場合は、稼動ＰＥをＰＥ
０，３，６，９，１２とし、ＰＥ０はＰＥ１，２のロー
カルメモリ４４を、ＰＥ３はＰＥ４，５のローカルメモ
リ４４を使用することにより、３倍のメモリ容量とな
る。４台のＰＥが稼動の場合は４倍のメモリ容量とな
る。アクセスのためのアドレス空間は、キャッシュメモ
リで用いるようなバンク方式あるいはウィンドウ方式も
考えられるが、連続したアドレス空間として使用しても
良い。

【０２１５】ここで、どのＰＥを休止とし、どの稼動Ｐ
Ｅがどの休止ＰＥのローカルメモリ４４を使用できる用
にするかを決定することが問題となる。まず稼動ＰＥを
ＰＥ０，１，２，３，４，５，６，７とし、ＰＥ８〜１
５を休止として、ＰＥ０がＰＥ８のメモリを、ＰＥ７が
ＰＥ１５のメモリを使用することにしても良いが、まず
稼動するＰＥは上記バイパスにおける制約条件もある
が、各ＰＥが番号順に左から順に実装されている場合、
ＰＥ０からＰＥ８への物理的距離が遠くなる。そのため
アクセス対象は実装時のモジュール間の距離を考慮して
決定すべきである。

【０２１６】上記例では、割り付けられるタスクの大き
さが均等の場合を念頭に述べたが、タスクの大きさすな
わち必要となるメモリ量が異なっても良い。すなわち今
６個のタスクがあり、それぞれ必要となるメモリ量が
４，２，３，４，１，２であった場合、稼動ＰＥはＰＥ
０，４，６，９，１３，１４となり、ＰＥ０はＰＥ１，
２，３をＰＥ４はＰＥ５を、ＰＥ６はＰＥ７，８を、Ｐ
Ｅ９はＰＥ１０，１１，１２を、ＰＥ１４はＰＥ１５の
ローカルメモリ４４をそれぞれ使用する。

【０２１７】このように、単純にタスクを左から割り付
けるとすると、タスクの大きさに適応するためには、前
述した通信時間の関係から、全てのＰＥが他の少なくと
も３つのＰＥにアクセスする経路を設けなければなら
ず、回路／配線の増大を招く。これを解消するため、例
えばＰＥ０，４，８，１２の各ＰＥは自ＰＥの右隣３Ｐ
Ｅへの経路をもち、他の偶数番号ＰＥは隣のＰＥへの経
路を持つように限定し、大きさの異なるタスクの割り付
けはスケジューリングを行い対処する。すなわちＰＥを
グループ化する。

【０２１８】これは複数ＰＥを１つのチップに載せた場
合にも有利となる。例えば、４ＰＥを１つのチップに配
置し、上記切り換えスイッチ４５などのアクセス回路も
チップ内に納める。これにより、アクセス回路の切り換
えによる速度低下を防ぐことが出来る。同一チップ上な
らば、多少の回路／配線が増加しても速度の低下は防ぐ
ことが出来る。そのため、同一チップに配置したＰＥ内
では、全てのＰＥが他のＰＥのローカルメモリ４４を使
用できるようにしても良い。こうすることにより、大き
さの異なるタスクへの対処の柔軟性は上がる。

【０２１９】次に２次元格子トーラス結合のメモリアク
セスの場合を示す。２次元の場合、休止の対象は行／列
である。そのため、アクセス回路も行方向と列方向に設
ける。上記１次元リング結合で、チップに載せることも
考慮して、ＰＥをグルーピングしたが、２次元の場合で
も同様のことがいえる。

【０２２０】図１５に２×２のグループを考える。ＰＥ
（０，０）は他のＰＥのローカルメモリ４４が使用でき
る。ＰＥ（１，０）とＰＥ（０，１）はＰＥ（１，１）
のローカルメモリ４４が使用できるようにする。これに
より列方向、行方向のスケーリングを利用してメモリ容
量の増加を行うことが出来る。また、ＰＥ（１，０）と
ＰＥ（０，１）は休止するため、バスパス回路４６を設
けている。

【０２２１】３次元格子結合に関しても上記例と同様に
することにより、メモリ容量の増加を行うことが出来
る。

【０２２２】次にハイパーキューブでのメモリアクセス
について説明する。並列計算機の静的結合方式の１つで
あるハイパーキューブは、通信距離の半径が小さいなど
の利点が挙げられるが、スケーラビリティの点でも有利
である。すなわちハイパーキューブの次元を１つ下げる
には、余分な次元に対応する通信経路を使用しなければ
よく、特別な回路は必要ない。

【０２２３】例として４次元から３次元にする例を図１
６に示す。稼動するＰＥをＰＥ０〜７とし、稼動しない
ＰＥをＰＥ８〜１５とすると、容易に１次元下がったハ
イパーキューブ結合の並列計算機となる。今、ＰＥ８〜
１５が休止であるので上記メモリアクセス路の例で述べ
たように、休止のＰＥのローカルメモリ４４を、稼動す
るＰＥのメモリとして使用することが出来る。

【０２２４】すなわちＰＥ８のローカルメモリ４４をＰ
Ｅ０が使用し、ＰＥ９のローカルメモリ４４をＰＥ１が
使用する。通信経路０−８，１−９，２−１０，３−１
１，４−１２，５−１３，６−１４，７−１５を使用し
ないので、メモリアクセス用バスとして上記通信経路を
使用しても良い。

【０２２５】次に複数ＰＥを１つのチップに配置する場
合の配線について説明する。図１７に２×２の４つのＰ
Ｅ４７ａ，ｂを１つのチップ４８に載せた場合の例を示
す。ＰＥ４７のモジュールをチップ４８内に配置する場
合、各ＰＥ間の通常の通信路の配線が場所を取る。そこ
で、アルミ等の配線層を複数化する近年のチップ製造技
術を用い、休止ＰＥ４７ａをバイパスする経路を休止Ｐ
Ｅ４７ａの上を通過するように配線する。これにより、
配線領域を縮小することが出来、余分な配線の引き回し
による遅延の増大を防ぐことが出来る。

【０２２６】同様に、休止ＰＥ４７ａのローカルメモリ
４４へのアクセス経路もＰＥ４７ａの上を通過するよう
に配線することにより、配線領域の縮小が行える。

【０２２７】第４の発明図１８は、第４の発明の並列計算機で用いられる演算プ
ロセッサの実施例である。

【０２２８】ルータ部５１と演算処理部５２から構成さ
れる。ルータ部５１はフリットを蓄えるバッファ５３ｘ
〜５３ｐと、フリットの出力先を決定するスイッチ５４
から構成される。

【０２２９】Ｐｉｎ，Ｐｏｕｔはルータ部５１と演算処
理部５２とを接続する通信チャネルである。Ｘｉｎ，Ｘ
ｏｕｔ，Ｙｉｎ，Ｙｏｕｔはそれぞれ隣接する演算プロ
セッサとの間の入力および出力のための通信チャネルで
ある。上記の演算プロセッサを用いて、例えば図１９に
示すような並列計算機が構築される。各演算プロセッサ
５５は、互いに通信チャネル５６で接続される。

【０２３０】図２０は本実施例で通信されるメッセージ
のフォーマットの一例である。一つのメッセージは複数
のフリットに分割される。先頭の二つのフリットは図２
０（ａ）のフォーマットをしており、図中ａｄｄｒｅｓ
ｓで表されるメッセージの宛先が書かれている。左右方
向の宛先が書かれたフリットに上下方向の宛先が書かれ
たフリットが続く。各方向の宛先は送信側プロセッサと
受信側プロセッサとの間の相対距離で表される。

【０２３１】３つめのフリットからメッセージの本体と
なる。そのフォーマットは、図２０（ｂ）および（ｃ）
に示すとおりである。フリットは図中ｄａｔａで表され
るメッセージの格納されている部分と、図中右端のメッ
セージの継続あるいは終了を表す終了ビット（ｅｎｄ
ｂｉｔ）からなる。メッセージが継続する場合は図２０
（ｂ）のフォーマットのようにｅｎｔｂｉｔは０であ
り、メッセージが終了する場合は図３（ｃ）のフォーマ
ットのようにｅｎｄｂｉｔは１となる。

【０２３２】図２１は本実施例のルータ部５１で行われ
るルーティング方法である。まず左右方向の宛先が一致
するまで左右方向に隣接する演算プロセッサ間で通信を
行う（ステップ１００，１０１）。続いて上下方向の宛
先が一致するまで上下方向に隣接する演算プロセッサ間
で通信を行う（ステップ１０２，１０３）。第４の発明
はこのルーティング方法に限定されず、いかなるアルゴ
リズムにも適応可能である。

【０２３３】図２２はスイッチ５４の内部構成例であ
る。図１９における左右方向のスイッチ５７と上下方向
のスイッチ５８とからなる。左右方向のスイッチ５７と
上下方向のスイッチ５８は同じ構成で実現される。それ
を図２３に示す。二つの出力先決定回路６１と、二入力
二出力のクロスバスイッチ６２から構成される。クロス
バスイッチ６２には複数の方向から入力が与えられるの
で、これらが衝突する場合は調停が行われる。

【０２３４】図２４は出力先決定回路６１の構成例であ
る。入力されたフリットのａｄｄｒｅｓｓ部が宛先比較
部６３で比較される。内部状態保存部６４に記憶されて
いる現在の状態ｓｔａｔｅで、先頭フリットか否かが判
定される。Ｘ方向あるいはＹ方向における宛先が自演算
プロセッサと同じメッセージであれば信号ｅｑｌを、そ
うでなければ信号ｎｅｑを出力先決定部６５に出力す
る。出力先決定部６５では、これらの制御信号とフリッ
トのｅｎｄｂｉｔ，そして内部状態ｓｔａｔｅから出
力先制御信号を発生する。

【０２３５】ｃｔｌｉｎは自プロセッサ（スイッチ５
８の場合）あるいは次のスイッチ５８（スイッチ５７の
場合）を、ｃｔｌｏｕｔは隣接するプロセッサを出力
先に選択するための制御信号である。ｃｔｌｉｎ、ｃ
ｔｌｏｕｔはいずれもクロスバスイッチ６２に入力さ
れる。

【０２３６】出力先決定部６５は次状態を決定し、内部
状態保存部６４に記憶する。さらに出力先決定部６５は
デクリメンタ６６への制御信号ｃｔｌｒｅｍｏｖｅ、
ｃｔｌｄｅｃも発生する。ｃｔｌｒｅｍｏｖｅはメ
ッセージから先頭のフリットを取り除くための制御信号
で、ｃｔｌｄｅｃはａｄｄｒｅｓｓを１減ずるための
信号である。

【０２３７】デクリメンタ６６はこれらの制御信号にし
たがって、宛先が自演算プロセッサと同じ場合は先頭の
フリットを取り除き、そうでないときは先頭のフリット
に書かれたａｄｄｒｅｓｓを１減ずる。先頭フリットで
ない場合は、何も操作は行わないでフリットを通過させ
る。デクリメンタ６６はまた、リクエスト信号ｒｅｑを
発生する。

【０２３８】図２５は内部状態保存部６４の状態遷移の
様子を表している。初期状態Ｓ０にいる時にフリットを
受け取った場合には、このフリットは先頭であるので、
ａｄｄｒｅｓｓにしたがってＳ１あるいはＳ２に遷移す
る。ａｄｄｒｅｓｓが自演算プロセッサと同じ場合には
Ｓ１に遷移する。メッセージが続いている場合にはＳ１
あるいはＳ２の状態を継続し、ｅｎｄｂｉｔによりメ
ッセージの終了を検出すると初期状態Ｓ０に戻る。

【０２３９】第４の発明を用いた場合に、従来の問題が
解決することを図２６を用いて説明する。図２６におい
て、５５ａ〜５５ｅは演算プロセッサであり、それぞれ
バッファ５３ｘ，５３ｙ，５３ｐ、スイッチ５４および
演算処理部５２から構成される。

【０２４０】出力先の演算プロセッサ５５ｂのバッファ
が一杯で通信が停止しているフリット６７が演算プロセ
ッサ５５ａのバッファ５３ｘに蓄えられているとする。
このとき演算プロセッサ５５ｃから別のメッセージのフ
リット６８が入力されるとする。

【０２４１】このメッセージの出力先が演算プロセッサ
５５ｅとすると、演算プロセッサ５５ｅのバッファに空
きがあれば、フリット６８は出力されるべきである。フ
リット６８はバッファ５３ｙに入力されるので、バッフ
ァ５３ｘには関係なく演算プロセッサ５５ｅに出力する
ことができる。

【０２４２】すなわち、出力先の通信チャネルが空いて
さえいれば、通信の停止している他のメッセージに妨害
されることなく、出力可能である。したがって、並列計
算機全体としての通信時間が短縮し、スループットも向
上する。

【０２４３】従来例の場合では、先にバッファに蓄えら
れているフリットの通信が停止してしまうと、それ以降
にバッファに蓄えられたフリットは、たとえ出力先のチ
ャネルが空いていても出力されなかった。しかし第４の
発明では、受信されたフリットは、先に出力先を決定し
バッファに蓄えられる。したがって、ブロックされてい
る通信チャネルのメッセージだけが通信を停止し、他の
メッセージは通信を妨害されることはない。

【０２４４】本実施例では二次元のネットワークの場合
を説明したが、ルータ部５１にスイッチ５７を増設する
だけで高次元のネットワークに拡張可能である。たとえ
ば三次元の場合は図２７のようにスイッチ３９を増設す
ればよい。また通信ネットワークは、本実施例のような
トーラス構造に限らず、ハイパーキューブ構造など、他
のいかなる構造にも適応可能である。

【０２４５】さらに第４の発明は、ワームホール・ルー
ティングに限らず、ストア・アンド・フォワード・ルー
ティングなど、他のいかなる通信方式にも適応可能であ
る。

【０２４６】第５の発明図２８は第５の発明の並列計算機で用いられるプロセッ
サの構成図である。Ｘｉｎ、Ｘｏｕｔはそれぞれ隣接す
るプロセッサとの間の入力および出力チャネルである。
Ｐｉｎ、Ｐｏｕｔはルータ部７１と演算処理部７２を接
続する通信チャネルである。ルータ部７１はＸｉｎ、Ｐ
ｉｎから受信したメッセージの転送先を決定し、Ｘｏｕ
ｔあるいはＰｏｕｔに出力するものである。バイパスス
イッチ７３は、第５の発明のために追加された構成であ
り、Ｘｉｎからの入力をルータ部７１をバイパスして、
直接Ｘｏｕｔに出力するブロックである。

【０２４７】図２９は、図２８のプロセッサで構成され
る並列計算機である。各プロセッサ７４ａ〜７４ｅが通
信チャネル７５によって接続されている。図示していな
いが、リクエスト信号とアクノリッジ信号も接続されて
いる。

【０２４８】本実施例で通信されるメッセージのフォー
マットは、図２０で示したものと同様である。

【０２４９】図３０はルータ部７１の内部構成例であ
る。プロセッサはＸｉｎ方向のプロセッサからリクエス
ト信号を受けると、ラッチ７６にフリットを受け取る。
このフリットがメッセージの先頭であれば、転送先決定
ブロック７７で自プロセッサに取り込むか、バイパスす
るか、あるいは隣接するプロセッサに転送するかを決定
する。転送先決定ブロック７７は同時に出力先へのリク
エスト信号を生成する。クロスバスイッチ７８にはメッ
セージとリクエスト信号、そして転送先決定ブロック７
７からメッセージの出力先を示す信号が与えられる。こ
の信号は２方向から与えられるので、これらが衝突した
場合には調停を行って、メッセージとリクエスト信号を
出力先へスイッチする。その結果、フリットはバッファ
７９に入れられる。同時に転送先決定ブロック７７の発
したリクエスト信号は出力先のプロセッサに与えられ
る。

【０２５０】図３１は転送先決定ブロック７７を構成す
るブロック図である。入力されたフリットが、メッセー
ジの先頭である場合は宛先比較ブロック８１で宛先を比
較する。先頭フリットであるか否かは、状態記憶ブロッ
ク８２に記憶されている現在の状態ｓｔａｔｅで判定さ
れる。宛先はプロセッサ間の相対距離で表されるので、
宛先が０ならば自プロセッサ宛、０以外ならば他のプロ
セッサ宛である。

【０２５１】自プロセッサ宛ならば信号ｅｑｌを、他の
プロセッサ宛ならば信号ｎｅｑを、出力先決定ブロック
８３に出力する。出力先決定ブロック８３はこれらの制
御信号と内部ステートにしたがって出力先制御信号を発
生する。

【０２５２】ｃｔｌｂｙｐａｓｓはバイパスするため
の制御信号で、ｃｔｌｏｕｔ１、ｃｔｌｏｕｔ２は
それぞれ、バイパスしない場合の出力先としてＸｏｕ
ｔ、Ｐｏｕｔを選択するための制御信号である。

【０２５３】ｃｔｌｂｙｐａｓｓは第５の発明におい
て特徴となる制御信号であり、バイパススイッチ７３に
入力されて、バイパス動作を行う。ｃｔｌｏｕｔ１、
ｃｔｌｏｕｔ２はいずれもクロスバスイッチ７８に入
力されて、出力先を要求する。また出力先決定ブロック
８３は次の状態ｎｅｘｔｓｔａｔｅを決定し、状態記
憶ブロック８２に記憶する。さらに出力先決定ブロック
８３はデクリメンタ１２４に対する制御信号ｃｔｌｒ
ｅｍｏｖｅ、ｃｔｌｄｅｃも発生する。

【０２５４】ｃｒｌｒｅｍｏｖｅは、デクリメンタ８
４に入力される宛先を取り除くための制御信号で、ｃｔ
ｌｄｅｃは宛先を１減ずるため制御信号である。デク
リメンタ８４はこれらの制御信号にしたがって、宛先が
自プロセッサであるときには宛先を取り除き、そうでな
いときには宛先を１減ずる。先頭フリットでない場合
は、何もしないでフリットを通過させる。デクリメンタ
８４はまたリクエスト信号ｒｅｑを発生する。

【０２５５】図３２は状態記憶ブロック８２の状態遷移
を表す図である。初期状態Ｓ０のときにフリットを受け
取ると、このフリットはメッセージの先頭であるので、
宛先にしたがってＳ１、Ｓ２あるいはＳ３に状態を遷移
する。例えば、メッセージをバイパスする場合はＳ１
に、Ｘｏｕｔに出力する場合はＳ２に、Ｐｏｕｔに出力
する場合はＳ３に遷移する。

【０２５６】メッセージが続いている間はＳ１〜Ｓ３の
状態に留まり、ｅｎｄｂｉｔによりメッセージの終了
を検出すると初期状態Ｓ０に戻る。Ｓ１からＳ０に状態
が遷移するとバイパスは解除される。すなわちバイパス
している状態でも、メッセージはルータ部７１に取り込
まれている。ただし、取り込まれるメッセージは終了を
検出する目的だけに用いられ、中継されたりはしない。

【０２５７】第５の発明のバイパス動作を以下に説明す
る。図３３は図２８で示したプロセッサを用いて構成し
た並列計算機である。８５ａから８５ｅはメッセージを
通信するためのチャネル（図中、ｄａｔａ）、８６ａか
ら８６ｅはリクエスト信号、８７ａから８７ｅはアクノ
リッジ信号である。本実施例ではメッセージは単方向に
通信されるが、双方向通信の場合も本質的な違いはな
い。各プロセッサは図３３（ａ）に示すように隣接する
プロセッサ７４とチャネルおよび信号で接続される。

【０２５８】本実施例で、プロセッサ７４ａからプロセ
ッサ７４ｅに中継プロセッサを全てバイパスしてメッセ
ージを送信する場合を説明する。プロセッサ７４ａはプ
ロセッサ７４ｂへリクエスト信号８６ａを発し、宛先を
持ったフリットを７４ｂに送信する。プロセッサ７４ｂ
はリクエスト信号を受け取るとフリットを受信し、フリ
ットに書かれている宛先を読みだす。

【０２５９】プロセッサ７４ｂは宛先ではないので、次
の転送先プロセッサ７４ｃを選択する。同時にプロセッ
サ７４ｂは通信チャネル８５ａと８５ｂ、リクエスト信
号８６ａと８６ｂ、およびアクノリッジ信号８７ａと８
７ｂをバイパスする。リクエスト信号８６ａと８６ｂが
バイパスされることにより、プロセッサ７４ｃにリクエ
スト信号が要求されることになる。

【０２６０】同様な操作がプロセッサ７４ｃ及びプロセ
ッサ７４ｄで実行され、図３３（ｂ）のように経路が確
定される。プロセッサ７４ｅはリクエスト信号を受ける
と、フリットを受信して宛先を読む。プロセッサ７４ｅ
は受信側プロセッサであるので、プロセッサ７４ｄに対
してアクノリッジ信号を返す。このときプロセッサ７４
ｂからプロセッサ７４ｄの内部でアクノリッジ信号８７
ａから８７ｄはバイパスされているので、図３３（ｃ）
のようにアクノリッジ信号は直ちにプロセッサ７４ａに
到達する。

【０２６１】こうしてプロセッサ７４ａとプロセッサ７
４ｅとの間のハンドシェイクが完成し、メッセージを転
送する経路が確立される。以後は図３３（ｄ）のように
プロセッサ７４ａとプロセッサ７４ｅの間で２つめ以降
のフリットの通信が行われる。この間プロセッサ７４ｂ
〜７４ｄは、終了検出を行うためにバイパスしているフ
リットを監視しつづける。そしてメッセージの終了を検
出すると初期状態に戻る。

【０２６２】この方法を用いた場合に転送に必要な時間
は、経路を確立するためのリクエスト信号の伝達にＤ、
アクノリッジ信号の伝達に１、経路確立後のメッセージ
の送信に２×（Ｌ−１）必要で、全体で（Ｄ＋２×Ｌ−
１）となる。このようにプロセッサ間の通信時間が短縮
される。Ｄ＝４、Ｌ＝４の場合のタイミング図を図３４
に示す。

【０２６３】以上はプロセッサ間でのメッセージの通信
をハンドシェイクで行った場合であるが、さらに通信を
高速にするために、図３３（ｂ），（ｃ）の処理によっ
て経路を確立せさたのち、図３３（ｅ）のようにプロセ
ッサ７４ａとプロセッサ７４ｅをクロック同期させて通
信を行う方法が考えられる。この場合、メッセージの送
信に必要な時間は（Ｌ−１）となって、全体では（Ｄ＋
Ｌ）となる。これは従来のワームホール・ルーティング
のほぼ１／２の時間で、プロセッサ間の通信にかかる時
間は大いに短縮される。Ｄ＝４、Ｌ＝４の場合のタイミ
ング図を図３５に示す。

【０２６４】同期通信の場合は、プロセッサ間の距離が
非常に大きいと、１クロックではフリットが到達できな
い可能性がある。このような場合を考慮して、通信を行
っているプロセッサの間に存在するプロセッサの一部で
メッセージを中継することを考える。すなわち、上述し
た実施例では、自プロセッサ宛でないメッセージは全て
バイパスしていたが、転送先への距離に応じてバイパス
と中継を分けるように、宛先比較ブロック８１および出
力先決定クロック８３を変更する。

【０２６５】本実施例を用いて、例えば１クロックで到
達可能な距離を８とした場合を考える。先頭のフリット
に書かれているデータは、受信側プロセッサまでの相対
距離であるので、この宛先が８の倍数であるときには中
継し、そうでないときにはバイパスするように、宛先比
較ブロック８１と出力先決定ブロック８３を変更する。

【０２６６】こうして１クロックで到達できる距離毎に
中継プロセッサが選択される。このような変更で、非常
に規模の大きなネットワークでも、従来例よりも高速に
プロセッサ間通信を行うことができる。

【０２６７】なお、本実施例では一次元の場合を説明し
たが、第５の発明は一次元に限らず、容易に多次元に拡
張可能である。図３６は二次元の場合のプロセッサ構成
図である。Ｘｉｎ、Ｙｉｎ、Ｐｉｎからの入力を、Ｘｏ
ｕｔ、Ｙｏｕｔ、Ｐｏｕｔに出力する。バイパススイッ
チ８８はバイパススイッチ７３に比べてバイパスする信
号が一つ増えたブロックである。

【０２６８】このように次元を拡張するには、次元数Ｎ
分だけルータ部７１とバイパススイッチ７３を用意す
る。これで各次元でバイパスが可能になるが、異なる次
元間でもバイパス可能にするためには、バイパススイッ
チ８８のように他の次元からのバイパスも選択できるよ
うに、スイッチの入力を増やす。

【０２６９】

【発明の効果】以上のように、第１の発明の並列計算機
は、並列度がプロセッサの数よりも大きい場合は通常の
ＳＩＭＤ型並列計算機と同様に実行することができ、並
列度がプロセッサの数よりも少ない場合には、複数命令
の並列実行を行なうことにより、実行時間の短縮とプロ
セッサの有効利用を図ることができる。また、通常のＳ
ＩＭＤ型並列計算機とオブジェクト互換をもつようにす
ることが可能である。

【０２７０】また、第２の発明の並列計算機によれば、
ＳＩＭＤ型並列計算機にわずかなハードウェアを付加す
るだけで、ＭＩＭＤ処理が可能になり、より柔軟性の高
い処理が可能になる。

【０２７１】第３の発明の並列計算機によれば、処理す
る問題サイズに応じて使用しないＰＥをバイパスする事
により、結合形態を維持したまま、問題サイズに最適な
構成を取ることが出来る。使用しないＰＥのメモリを、
使用するＰＥがアクセスできるようにすることにより、
各ＰＥのメモリ容量を増やすことが出来る。

【０２７２】さらに、同一チップ内において、バイパス
経路、メモリアクセス経路をＰＥの上を通過するように
配線することにより、配線領域の縮小、遅延増大の防止
を行うことが出来る。

【０２７３】第４の発明の並列計算機によれば、フリッ
トは出力先毎に出力側のバッファに蓄えられるので、通
信可能なメッセージは、通信が停止している他のメッセ
ージによって妨害されることはない。その結果、通信時
間が短縮され、スループットが向上する。

【０２７４】さらに、第５の発明の並列計算機によれ
ば、中継プロセッサをバイパスすることにより、通信に
必要な時間を大いに短縮することができる。このため、
特にネットワークの規模が非常に大きくプロセッサ間の
距離が大きな場合に有効である。

【図面の簡単な説明】

【図１】第１の発明における並列計算機の一実施例の構
成図。

【図２】第１の発明における実施例で用いた処理の一
例。

【図３】並列度が大きい場合の図２の処理を行なうため
に供給される命令列。

【図４】並列度が小さい場合の図２の処理を行なうため
に供給される命令列。

【図５】第１の発明の図１と異なる実施例の構成図。

【図６】第２の発明の並列計算機に係わる一実施例の構
成を示すブロック図。

【図７】第２の発明の中心となる演算プロセッサの構成
例を示す図。

【図８】図７で示したローカルメモリ中に作成されるア
ドレステーブルのメモリマップ図。

【図９】図７と異なる演算プロセッサの構成例を示す
図。

【図１０】第３の発明における１次元リング結合並列計
算機のバイパスに関する一例の構成図。

【図１１】第３の発明においてバイパス回路として用い
た双方向バスの詳解図。

【図１２】第３の発明においてバイパス回路として用い
たハンドシェイク用信号線の詳解図。

【図１３】第３の発明における２次元トーラス結合並列
計算機のバイパスに関する一例の構成図。

【図１４】第３の発明における１次元リング結合並列計
算機のメモリアクセスに関する一例の構成図。

【図１５】第３の発明における２次元トーラス結合並列
計算機のバイパス及びメモリアクセスに関する一例の構
成図。

【図１６】第３の発明におけるハイパーキューブ結合並
列計算機のメモリアクセスに関する一例の構成図。

【図１７】第３の発明におけるバイパス経路及びアクセ
ス経路のチップ上での配線例。

【図１８】第４の発明における演算プロセッサの一実施
例を表す構成図。

【図１９】図１８で示した演算プロセッサで構成される
並列計算機の構成図。

【図２０】第４の発明において通信されるメッセージの
フォーマット例。

【図２１】第４の発明におけるルーティング方法を表す
フローチャート。

【図２２】図１８で示したスイッチの内部構成図。

【図２３】図２２で示した一方向のスイッチの内部構成
図。

【図２４】図２３で示した出力先決定回路の内部構成
図。

【図２５】図２３で示した出力先決定回路の状態遷移
図。

【図２６】図１８で示した演算プロセッサを用いた通信
方法を表す図。

【図２７】第４の発明における３次元ネットワークの場
合の一実施例を示す構成図。

【図２８】第５の発明におけるプロセッサの一実施例の
構成を示す構成図。

【図２９】図２８で示したプロセッサを用いた並列計算
機の構成図。

【図３０】図２８で示したルータ部の一例を示す図。

【図３１】図３０で示した転送先決定ブロックの構成
図。

【図３２】図３０で示した転送先決定ブロックの状態遷
移図。

【図３３】第５の発明におけるバイパス動作を表す図。

【図３４】第５の発明におけるバイパス動作時の転送時
間を表すタイミング図。

【図３５】第５の発明におけるクロック同期による転送
時間を表すタイミング図。

【図３６】第５の発明における２次元の場合のプロセッ
サ構成図。

【図３７】第２の発明に対する従来の演算プロセッサの
構成を示す図。

【図３８】第４の発明に対する従来の演算プロセッサの
構成図。

【図３９】図３８で示した演算プロセッサを用いた従来
の通信方法を表す図。

【図４０】第５の発明に対する従来のプロセッサ構成
図。

【図４１】第５の発明に対する従来のバイパス動作時の
転送時間を表すタイミング図。

【図４２】第５の発明に対する従来のクロック同期によ
る転送時間を表すタイミング図。

【符号の説明】

１プロセッサ２プロセッサアレイ制御装置３セレクタＯＵＴ０，１出力端子１１制御プロセッサ１２演算プロセッサ１３全体メモリ１４ローカルメモリ１５グローバルバス１６ネットワーク１７同期バス１８フロントエンド計算機２１メモリアドレスバス２２メモリデータバス２３マルチプレクサ２４命令レジスタ２５プログラムカウンタ２６アドレスレジスタ２７データレジスタ２８内部バス２９ＡＬＵ３０レジスタファイル３１状態制御レジスタ３２プロセッサ番号レジスタ３３通信制御部４１双方向バッファ４２識別回路４３セレクタ４４ローカルメモリ４５切り換えスイッチ４６バスパス回路４７ＰＥ（演算要素）４８チップ５１実施例のルータ部５２演算処理部５３ｘ，５３ｙ，５３ｐバッファ５４スイッチ５５ａ〜５５ｅ演算プロセッサ５６通信チャネル５７，５８，６９一方向のスイッチ６１出力先決定回路６２クロスバスイッチ６３出力先選択部６４内部状態保存部６５出力先決定部６６デクリメンタ７１ルータ部７２演算処理部７３，８８バイパススイッチ７４ａ〜７４ｅプロセッサ７５，８５ａ〜８５ｅ通信チャネル７６ラッチ７７転送先決定ブロック７８クロスバスイッチ７９バッファ８１宛先比較ブロック８２状態記憶ブロック８３出力先決定ブロック８４デクリメンタ８６ａ〜８６ｅリクエスト信号８７ａ〜８７ｅアクノリッジ信号

───────────────────────────────────────────────────── フロントページの続き (72)発明者高橋真史神奈川県川崎市幸区小向東芝町１株式会社東芝総合研究所内

Claims

【特許請求の範囲】

【請求項１】複数個のプロセッサからなるプロセッサ
アレイと、このプロセッサアレイを制御すると共に、並列実行可能
な複数種類の命令列を前記プロセッサアレイに供給する
プロセッサアレイ制御手段とを備え、前記プロセッサアレイ制御手段から供給される複数種類
の命令列の中の１種類ずつを各プロセッサが受け取り、
前記複数種類の命令列を前記複数個のプロセッサで並列
実行することを特徴とする並列計算機。
【請求項２】単一の制御プロセッサと、該制御プロセッサからアクセス可能な第１のメモリと、制御プロセッサから転送される命令情報にしたがって、
処理を行う複数個の演算プロセッサと、該演算プロセッサからアクセス可能な第２のメモリとか
ら構成され、さらに前記演算プロセッサには、演算プロセッサでの実行を制御する命令情報の格納手段
と、該格納手段に、前記制御プロセッサからの命令情報を入
力するか、第２のメモリに格納されている命令情報を格
納するかを選択する手段と、前記格納手段に格納されている命令情報にしたがって演
算を実行する手段とを備えることを特徴とする並列計算
機。
【請求項３】個々の通信経路で接続されている複数の
演算要素と、解く問題のサイズに応じて演算に使用する演算要素と使
用しない演算要素とを識別する識別手段と、この識別手段によって識別された、演算に使用しない演
算要素をバイパスするバイパス手段とを備えることを特
徴とする並列計算機。
【請求項４】個々の通信経路で接続されている複数の
演算要素と、各々の演算要素と個々に結合しているローカルメモリ
と、解く問題のサイズに応じて演算に使用する演算要素と使
用しない演算要素とを識別する識別手段と、この識別手段によって識別された、演算に使用しない演
算要素と結合しているローカルメモリを、演算に使用す
る演算要素から直接アクセス可能にするアクセス手段と
を備えることを特徴とする並列計算機。
【請求項５】複数のプロセッサがＮ次元ネットワーク
で相互接続され、各プロセッサが、隣接するプロセッサからメッセージを受信し、出力先を
決定する出力先決定手段と、出力先ごとに設けられ、前記出力先決定手段によって出
力先が決定されたメッセージを受信した順に蓄える蓄積
手段と、蓄積されたメッセージを、決定された出力先のプロセッ
サに出力する出力手段とを備えたことを特徴とする並列
計算機。