JPS6084661A - 経路指定装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔発明の背景〕 本発明は、並列プロセッサを用いるコンピュータ、特に
、従来よりも非常に数多くの並列プロセッサを用いるコ
ンピュータに関する。

典型的なデジタルコンピュータは、中央処理装置（ＣＰ
Ｕ）、データを記憶するメモリ及びコンピュータを制御
するためのプログラム、そして、種々の入出力装置とを
持つ。記憶されたプロクラムは、ＣＰＵが、コンピュー
タに入力されるデータに基づいて、計算、転送、または
論理演算を行なうようにするための一連の指令となる。

このようなデータは、究極的には入力装置からコンピュ
ータに入れられ、ＣＰＵ演算の結果は、出方装置に供給
される。典型的なコンピュータでは、この一連の指令は
、一時に一つずつ直列的に行なわれる。

デジタルコンピュータか用いられてきた４０年余りの間
に、コンピュータ及びそれを動かすプログラムはより複
雑になってきた。直列式コンピュータにおける複雑さは
、そのメモリ及びそこに記憶されるプログラム及び／又
はデータの規模が大きくなってきたことで増してきてい
る。しかし、ある意味では、これらのより複雑化した直
列式コンピュータは、より効率の悪いものになってきて
いる。どの時間にも、直列式コンピュータのごくわずか
な部分が利用されているたけである。何故なら、ＣＰＵ
によって実行される命令は、二、三のメモリロゲーショ
ンからしが得られず、また、データを二、三の他のロゲ
ーションに向けるのみである。さらに、コンピュータが
、そのメモリの規模において機能が良くなるにつれ、メ
モリがら出力を発生する能力の点では、にぶくなってぎ
ている。何故なら、メモリからデータを検索するのに要
する時間は、メモリに記憶したデータの量と共に増加す
るからである。。

直列式コンピュータにおけるこれらの問題点は、直列式
コンピュータの初期における発達に多大な貢献をしたジ
ョン・フォンニューマンの名前をとって、フォンニュー
マン障害と呼ばれてきた。Ｊ．バッカスによる論文「プ
ログラミングをフォンニューマン形式がら開放出来るか
？」（ＡＣＭの通信第２１巻第８号、第６１３ベージ、
１９７８年８月）を参照されたい。

これらの問題点は、コンピュータを用いて、意味結合ネ
ットワークとよばれる相互関係ネットワークに記憶され
た知識を検索することの多い人工知能の分野において、
特に深刻である。この知識を検索するために、ネットワ
ーク全体を探査することもあり得る。また、他の記憶さ
れた情報から、希望する事実を推論しなげれはならない
こともあるだろう。このような検索を行なうために、二
、三の単純な演算を、プログラムの演算時間の大部分に
わたって何回も繰り返すことになる。この演算は下記の
ことを含む。

１、大きさ又は数学的順序といったパラ−メータに従っ
て一組のデータを分類する。

２、特定の構造を持つサブセット又はサブグラフのため
にデータ又はグラフの指定された絹み合わせを探索する
。

３、捉言の組み合わせに対してパターンの突き合わせを
する。

４、記憶されている情報の意味結合ネットワークから事
実を推論する。

このような演算を一時に一つすつ行なうことは、コンピ
ュータの時間及び機能という点て非常な浪費となる。そ
の結果、人工知能における多数の問題か、現在入手可能
な直列式コンピュータでは、アドレスされないでいる。

しかし、これらの問題は、解決策を緊急に要する、例え
ば、画像処理のような基本的な問題なのである。

換言すると、このような演算を並行して行なうことが出
来れば、演算に要する時間を減少させることが出来る。

このようなことの有利さは良く認識されている。例えば
、［ＶＬＳＩ方式の導入］第８章におけるＣ．ミード及
びＬ．コンウェイの「高度兼用方式」（アヂソンウエズ
レー、１９８０年）、及びその中に引用された参考文献
、Ｗ．Ｄ．ヒリスによる「結合装置」（マサチュセッッ
工科大学人工知能研究室メモ、第６４６番、１９８１年
９月）、及びその中に引用されている参考文献、そして
、Ａ．ローゼンフェルドによる論文「細胞状アレイを用
いる並行画像処理」（「コンピュータ」第１６巻、第１
号、第１４ページ、１９８３年１月）を参照すると良い
。

程度の差はあるが、これらの文献では、データの並行演
算を行なうための装置についての一般概念を述へている
。例えば、ヒリスとローゼンフエルドは、同一のプロセ
ッサ／メモリのアレイで、それぞれがデータを記憶する
に必要なハードウェアと、それを処理摺るハードウェア
とを持つものを考えている。しかし、プロセッサ／メモ
リとその制御との相互結合を含む完全演算コンピュータ
について明確な詳細を述べることがこれらの論文の目的
ではない。

〔発明の要約〕

我々は、プロセッサ／メモリのアレイ、及び、データを
アレイ内の１つのプロセッサ／メモリから他のプロセッ
サ／メモリへ送るための少なくとも２°個のノードを持
つｎ−次元パターンで、それらのプロセッサ／メモリを
相互結合させる手段からなる並行プロセッサアレイを考
案した。都合の良いことに、ｎ−次元パターンは、１５
次元のプール立方体である。

各プロセッサ／メモリは、読み出し／書き込みメモリと
、少なくとも一部は読み出し／書き込みメモリで読んだ
データ及び命令情報とに基づく出力を作るプロセッサと
からなる。相互結合手段は、メッセージパケット内のア
ドレス情報に従って、１つのプロセッサ／メモリから他
のプロセッサ／メモリへ径路指定されるアドレスされた
メソセージパケットを生成する手段と、パケット内のア
ドレス情報に従ってメッセージパケットを径路指定する
ためにｎ−次元パターン内の各ノードにある径路指定回
路とからなる。

本発明の好ましい実施例では、プロセッサ／メモリは、
２次元パターンでも相互結合され、その場合は、各プロ
セッサ／メモリは、２次元パターンで隣り合わせている
プロセッサ／メモリと直接相互結合される。

現在可能な技術では、そのようなプロセッサ／メモリは
、これらの相互結合手段で結合させると、１００万個以
上も並行して操作できる。

メッセージパケット内のアドレス情報は、メッセージパ
ケットが送られるノードに対して相対であり、アドレス
の各数字が、メッセージパケットの、メッセージパケッ
トが送られるノードからの１次元における相対変位を意
味していることが望ましい。ｎ−次元の各次元に対して
、径路指定回路が、メッセージパケットがその次元内の
行き先に到達したかどうかを決め、もし到達せず、また
、その次元内の他のノードが使用出来る場合には、その
ノードへ径路指定するための論理を作る。最初の行き先
決穴論理から他のノードへの結合が不可能な時、または
、最初の行き先決穴論理が、メッセージパケットがその
次元内の行き先に到達したと決定した時には、径路指定
回路が、メッセージパケットが、第２の次元での行き先
に到達したかどうかを決定するための似たような論理に
メッセージパケットを導く。さらに、径路指定回路は、
行き先ノードに到達したメッセージパケットをそのノー
ドのプロセッサ／メモリに導く論理と、接続抵触によっ
て径路指定出来なかったメッセージパケットを記憶する
手段とを含む。

好都合なことに行き先決定論理及び各次元の径路指定論
理は、ｎ−次元パターンの全てのノードにわたって同時
に演算される。その結果、メッセージパケットは、単一
の径路指定サイクルの間にｎ−次元パターン全体に径路
指定される。加えて、各径路指定回路は小さいので、数
個のプロセッサ／メモリと共に１個の非積回路チップ上
に組み立てられる。

〔好適実施例の説明〕

読者の便宜のため、本発明の好ましい実施例の説明を、
下記の区分に分ける。

Ａ、システムの全体的説明 Ｂ、並行処理ＩＣの全体的説明 Ｃ，プロセッサ／メモリの説明 Ｄ、通信インタフェース装置の説明 Ｅ、径路指定回路の説明 Ｆ、例 Ｇ、代替案 Ａ、システムの全体的説明 第１Ａ図に示されるように、本発明は、本体コンピュー
タ１０、マイクロコントローラ２０、並行処理集積回路
３５のアレイ３０、データソース４０、第１バッフア及
びマッチプレクサ／デマルチプレクサ５０、第１、第２
、第３及び第４の双方向パス制御回路６０．５５、７０
．７５、第２バッファ及びマッチプレクサ／デマルチプ
レクサ８０、及び、データシンク９０を含むコンピュー
タシステムにおいて実行される。本体コンピュータ１０
は、デジタル装置会社（Ｄｉｇｉｔａｌ　Ｅｑｕｉｐｍ
ｅｎｔ　Ｃｏｒｐ．）製造のＶＡＸコンピュータのよう
な、適合するようにプログラムされ、市販されている汎
用コンピュータでよい。

マイクロコントローラ２０は、３２ビット並列バス２２
によってアレイ３０に与えられる命令の順序付けをする
ための従来からあるデザインの命令シーケンサである。

バス２２中の３２回線の１回線は、アレイ３０にＲＥＳ
ＥＴ信号を与え、３回線はタイミング信号を出し、他の
２８回線は、命令の伝送に使われる。アレイ３０の各並
行処理ＩＣ３５をアドレス指定するための追加のアドレ
ス指定信号は、バス２４上のアレイに与えられる。マイ
クロコントローラ２０は、アレイ３０から回線２６上の
信号を受け取る。この信号は、データ出力及び状態情報
として用いることの出来る一般目的または大域的信号で
ある。

バス２２及び回線２６は、各ＩＣ３５に並列に接続され
る。その結果、マイクロコントローラ２０からの信号は
、アレイ３０内の各ＩＣ３５に同時に与えられ、回線２
６上のマイクロコントローラ２０に与えられる信号は、
アレイのＩＣ３５の全てからの信号出力を統合して形成
される。

アレイ３０は、３２，７６８（＝２１５）個の同一なＩ
Ｃ３５を持ち、各ＩＣ３５は３２（＝２５）個の同一プ
ロセッサ／メモリ３６を持つ。このようにして全体のア
レイ３０は１，０４８，５７６（＝２２０）個の同一プ
ロセッサ／メモリ３６を含む。

プロセッサ／メモリ３６は、２つの形状寸法に構成され
、相互結合される。一番のものは、従来からある２次元
の格子パターンで、プロセッサ／メモリは方形アレイ内
に構成され、アレイ内の最も近くにある４個のプロセッ
サ／メモリに接続される。第２のものは、１５次元のプ
ールｎ−次元立方体である。２次元の格子パターンのプ
ロセッサ／メモリを接続するには、アレイ３０のＩＣ３
５を２５６（＝２８）行と１２８（＝２３）列の長方形
アレイに構成し、各ＩＣの３２のプロセッサ／メモリは
、４（＝２２）行で８（＝２３）列の長刀形アレイ内に
接続される。その結果、アレイ３０の１，０４８，５７
６個のプロセッサ／メモリ３６が、１０２４（＝２１０
）行と１０２４列の正方形内で接続される。便宜上、こ
の出力形のアレイの側面を、北、東、南及び西とする。

各プロセッサ／メモリをその最も近くにある４個のプロ
セッサ／メモリに接続するには、各プロセッサ／メモリ
を、各行、各列の隣接するプロセッサ／メモリとの間を
電気感体で接続すれば、アレイの端にあるもの以外のＩ
Ｃの最も近くにある４個のＩＣを、それぞれ北、東、南
及び西の隣接する４個のＩＣであると認識されるように
なる。

２次元アレイの列及び行にある各プロセッサ／メモリは
、第１次元での列番号又は位置を表わすために最初の数
字を、また、２次元での行番号又は位置を表わすために
二番目の数字を用いて系統的に番号付けをすることによ
って識別しても良い。

例えば、もし、左端又は最西端の列をゼロとして列に番
号付けし、底部又は最南端の行をゼロとして行の番号付
けをすると、底部左端又は南西の角に近い９個のプロセ
ッサ／メモリは、 ０、２　１，２　２、２ ０、１　１，１　２、１ ０．０　１，０　２，０ と識別又はアドレス指定され、上部右端又は北東角にあ
るプロセッサ／メモリは、１０２３、１０２３の数字で
識別される。このような数字の組の各々は、連想プロセ
ッサ／メモリのアドレスと言われるようになる。

この番号付けのため、２次元アレイ内のいずれかのプロ
セッサ／メモリの最も近い４個は、そのアドレスを作る
２つの数の１個だけが、そのプロセッサ／メモリのアド
レスと１だけ違うアドレスを持つということが認識され
るだろう。例えば、アドレス１，１を持つプロセッサ／
メモリの最も近い４個は、それぞれ北、東、南及び西に
アドレス１、２；２，１；１，０；Ｏ，１の４個のプロ
セッサ／メモリである。

第１Ａ図に図式的に示されるように、アレイ３０の２次
元格子パターンは、第１、第２、第３及び第４の双方向
バス制御回路６０．６５．７０、７５に向かって、アレ
イ３０の北、東、南及び西の端を越えて、第１、第２バ
ッファ５０．８０まで伸びている。特に。

アレイの４端の各々にある１０２４個のプロセッサ／メ
モリ３６の各々は、１０２４個の双方向導線６１．６６
．７１．７６のうちの１本で、バス制御回路６０．６５
．７０．７５にそれぞれ、接続されている。

データソース４０は、高速データバス４１を経てバッフ
ァ及びマルチプレクサ／デマルチプレクサ５０に入力デ
ータを送る。データソース４０は、コンピュータ端子、
通信回線、視覚、聴覚又は触覚入力、レーダー又はソナ
ー装置、ディスクファイル又はその組合わせ等のどのよ
うなデータ源でもよい。

実例をあげると、データバス４１は、３２ビット幅のバ
スで、バッファ５０は、各々３２ビット容量を持つ３２
個の直列入力、並列出力シフトレジスタでよい。

このような構成において、バス４１の各回線は、別個の
直列入力シフトレジスタに供給するので、従来からの多
重化又は多重分離の必要がない。バス４１内の回線数が
、シフトレジスタの数と異なる場合は、多重化又は多重
分離回路が、バス４１の個々のデータ回線からバッファ
５０内のシフトレジスタの直列入力にデータを分散する
ために用いられる。

バッファ５０は、１０２４個の回線バス５１上の並列デ
ータを、バス制御回路６０．６５．７０、７５のうちの
１つに入れ、それが、バス６１．６５、７１又は７６を
経て接続されている側のアレイの外端にあるプロセッサ
／メモリに、それらのデータを与える。

アレイ３０からのデータは、アレイの一端に治っている
プロセッサ／メモリからバス制御回路６０．６５．７０
．７５のうちの１つに、バス６１、６６、７１又は７６
のうちの１本に並列に与えられ、バス制御回路は、バッ
ファ８０への入力に接続されているバス８１へ向けてデ
ータを切り換える。バッファ８０の出力は、データシン
ク９０に接続されている高速データバス８６である。実
例をあげると、バッファ８０は、各々が３２ビット容量
を持つ３２の並列入力、直列出力シフトレジスタのアレ
イで、データバス８６は３２ビット幅のバスでよい。こ
の構造では、従来からの多重化又は多重分離の必要がな
い、、バス８６内のデータ回線の数が、バッファ８０内
のシフトレジスタの数と異なる場合は、多重化又は多重
分離回路が、シフトレジスタの直列出力から、バス８６
の各データ回線へデータを送るために用いられる。デー
タシンク９０は、コンピュータ端子、通信回線、ディス
プレー、プリンタ、プロッタ、音声シンセサイザ、機械
的装置、ロボット、ディスクファイル、またはそれらの
組合わせのようなデータ源のどれでも良い。

アレイ３０を通るデータの流れの方向は、マイクロコン
ピュータ２０及びハス制御回路６０．６５．７０．７５
によって制御され、東から西へ、北から南、又は、その
逆であってもよい。第１Ｂ図に示すように、各バッファ
６０．６５．７０又は７５は、１０２４個のセレクタ１
０，００１．１０，００２．１０，００３・・１１，０
２４を持つ。

各セレクタへの信号入力のうちの１つは、バス５０から
のデータバス５１の回線のうちの１本である。

他の２本の信号入力は、アレイ３０からの出力である。

ある場合には、入力はセレクタと同じ行又は列にあるア
レイからの出力である。他の場合には、入力はセレクタ
のすぐ隣の行又は列のアレイからの出力である。最下部
のセレクタの場合には、セレクタへの入力のうち２本は
接地している。４本の人力セレクタ回線の各々は、４本
の信号入力のうちの１本を選び、各セレクタからの出力
になる。

４本の入力セレクタ回線上の信号は、マイクロコントロ
ーラ２０によって生成される。

この配置の結果として、各バッファは、４組の信け、即
ち、バッファ５０からのデータ入力、アレイ３０からの
再循環データ、アレイ３０内の隣接する行又は列からの
再循環データ、そして、全てのゼロの４組の信号のうち
の１組をアレイに送ることもある。隣接する行又は列か
らの再循環データの場合には、バッファは、実際に、ア
レイの全ての個別プロセッサ／メモリを、アレイの１０
２４行又は列を螺旋状に通る１本の回線に相互結合させ
てしまっている。

上記の相互結合の２次元格子は、例えば計算の初期段階
のように、アレイ３０に大量のデータを俳き込むため、
また、例えば、処理を中断し、アレイの状態を記憶させ
る必要のある場合に、アレイの内容を読み出すためには
、役立つ。しかし、この相互結合アレイは、２次元アレ
イ中のプロセッサ／メモリ３６間の任意の方向への敏速
なデータ中継は行なえない。その上、アレイの端と特定
のプロセッサ／メモリとの間にデータを移動させるには
、その端と問題のプロセッサ／メモリとの間にある全て
のプロセッサ／メモリにデータをシフト移動する必要が
あり、５００個以上ものプロセッサ／メモリにシフト移
動を行なう必要も出てくる。

非常に高速でこのようなシフト移動を行なえる場合でも
、５００回以上もこうしたシフトを行なう必要があると
、全操作を非常に遅いものにしてしまう。こうしたシフ
トを、同時に無作為でばらばらな方向で大量のプロセッ
サ／メモリについて行なうことの煩雑さも加わって、妥
当な費用でそのように太きなプロセッサ／メモリの２次
元格子を運転することは不可能になる。

本発明においては、第２形状寸法に従ってプロセッサ／
メモリ３６詮作り、相互結合することに十って、この問
題点を緩和している。特に、ＩＣ３５は、１５次元のブ
ールｎ−立方体の形に作られ、相互結合されている。各
ＩＣは論理回路系を持ち、その相互結合網を通るメッセ
ージの径路指定を制御しており、また、各ＩＣ内では、
３２プロセッサ／メモリにバス接続が用意され、１００
万個以上のプロセッサ／メモリのどれもが、他のとれに
対してもメッセージを送ることが出来る５、その上、大
量のメッセージがいつでも送られ、無作為の方向へ径路
指定出来る。

ＩＣ３５のこの接続パターンを理解するために、Ｏから
３２，７６７番までＩＣに番号を付け、表１のように１
５個の２進数字を用いる２進法で、これらの数字又はア
ドレスを表わすのが良い。

２次元格子の相互結合に関して上に述べた概念は、１５
次元格子の相互結合に関しても充分通用するものである
。各プロセッサ／メモリ３６を、２つの数字を用いて、
その１つが２次元格子の第１次元での位置を示し、他の
１つが第２次元での位置を示したように、ブール１５−
立方体の１５次元のそれぞれにおけるＩＣの位置を識別
するために、番号を使うことが出来る。しかし、ｎ−立
方体ではＩＣは、各数元において２つのみの異なる位置
。

０及び１のうちのどちらかをとることが出来る。

このように、表１に書かれたような２進法での１５個の
数字によるＩＣアドレスは、ｎ−立方体の１５次元での
ＩＣの位置も示すのである。便宜上、１５個の２進数字
の最左端の数字を、第１次元のＩＣの位置を示すものと
して用い、その順番で、最右端の数字が、第１５次元で
のＩＣの位置を示すものとする。

その上、２進数字が０又は１の２つの値しか持つことが
出来す、各ＩＣは１５個の２進数字によって独自に識別
されるので、各ＩＣには、自分のアドレスと１個の数字
が違うだけの２進アドレスを持つ他のＩＣが１５個ある
ことになる。我々はこれらの数字が一字しか違わない１
５個のＩＣを、最初のＩＣの最も近い隣接者と呼ぶ。ハ
ミング距離の数学的定義を知っている人々は、最初のＩ
Ｃかその１５個の最も近い隣接者の各々から、ハミング
距離だけ離れていることに気づくだろう。１個のＩＣと
それに最も近い１５個の隣接者のアドレスの２例を表１
１に示す。

ブール１５−立方体の形に１Ｃ３５を接続するには、各
ＩＣをそれに最も近い１５個の隣接ＩＣに接続する。第
１図では、この接続が１５本の入力回線３８及び１５本
の出力回線３９で図式的に示されているが、実際の接続
径路は、図がますます複雑になるので描かれてはいない
。各ＩＣ３５へのこれら１５本の入力回線３８のそれぞ
れは、ブール１５−立方体の１５次元のうちの異なる」
っと関連しており、同様に、各ＩＣ３５からの１５木の
出力回線３９のそれぞれは、違う次元と関連している。

ブールｎ−立方体の相互結合パターンを正しく認識する
には、３次元及び４次元のブールｎ−立方体内のＩＣ３
５′のアレイに用いられる相互結合を考えると良い。第
２図は、３次元のブールｎ−立方体の図式的描写である
。８個の頂点又はノードと１２のへりを持つ従来がらあ
る立方体とみなされるであろう。この立方体の３次元は
ローマ数字Ｉ、ＩＩ、ＩＩＩで識別される。頂点のそれ
ぞれに、ＩＣ３５′があり、各ＩＣからは３本の出力回
路３９′が出て、立方体の３次元に沿って、そのＩＣの
３個の最も近い隣接ＩＣまで伸びている。後に明らかに
なるように、各ＩＣ３５′にはそれに最も近い３個の隣
接ＩＣからの出力回線である２３本の入力回線３８′も
ある。下部左端の頂点は、このシステムの原点と仮定さ
れ、従って、この頂点のＩＣが第２図の３次元立方体の
第１、第２及び第３次元中のＯポジション又はアドレス
に持つことになる。

このアドレスが０００と書かれる３、各ＩＣは、各次元
内の２つだけのポジションのうちの１つにあるので、他
のＩＣは、第２図に示されるように０及び１の３桁の数
字の他の組み合わせから成るアドレスを持つ。

第３図は、４次元のプールｎ−立方体を示す。

このような立方体には、１６個の頂点と３２個の稜があ
る。ここでも、１個のＩＣ３５′は各頂点又はノードに
置かれ、入力回線３８′及び出力回線；３９′によって
最も近い隣接ＩＣに接続される。しかしこの場合には各
ＩＣには４個の最も近い隣接ＩＣがあり、従って、４−
立方体の４次元に沿って伸びる４本の入力回線と４本の
出力回線を持つことになる。ブール４−立方体内の各Ｉ
Ｃの位置は、第３図に示したように４桁の２進数字で識
別され、この４−立方体の４次元は、第３図に示される
ように、ローマ数字のＩ、■、ＩＩＩ、ＩＶで識別され
る。

より高次元の立方体へのこのパターンの外挿法も明らか
にされる。どの場合にも、次に高い次元では、頂点の数
が２倍になり、各ＩＣは１個余分な最も近い隣接ＩＣを
持つことになる。従って、プール１５−立方体は、３２
，７６８の頂点を持ち、各頂点にＩＣを１個持つことに
なり、１５個の最も近い隣接ＩＣを持つようになる。

ブール１５−立方体の相互結合パターンに通信を行なわ
せるには、コンピュータシステムか、処理サイクルと径
路指定サイクルの両方を持つように操作する。計算は処
理サイクルの間に行なわれる。

径路指定サイクルの間に、計算の結果がメッセージパケ
ットの形に編成され、これらのメッセージパケットは、
パケットの一部となっているアドレス情報に従って、各
ＩＣ中の回路系を径路指定することによって、１つのＩ
Ｃから次のＩＣへ径路指定されて行く。メッセージパケ
ットの様式は第４図に描かれているが、それは、ＩＣア
ドレス１５ビット、書式ビットが１ビット、ＩＣアドレ
スを複写する他の１５ビット、ＩＣ中のプロセッサ／メ
モリへのアドレスが５ビット、メッセージの３２ビット
と誤り検出の１ピットの合計７３ビットがら成り立つこ
とかわかる。誤り訂正のために追加のビットを加えても
良い。実例として、各ビットの持続時間は、１から１０
メガヘルッ（ＭＨｚ）の周波数に応じて、０．１から１
マイクロ秒である。第４図には、システムに用いられる
基本的クロック信号ＰＨＩ１及び１ＰＨＩ２２も示され
ている。これらの信号は、各々がメッセージパケットの
１ビットと同じ周期と周波数を持つ、非重複２相クロッ
クである。

メッセージパケット内では、ＩＣアドレス情報は、行き
先ＩＣのアドレスに対して相対である。

最初は、メッセージ源であるＩＣのアドレスとその行き
先のアドレスとの相違又は変位である。例えば、原始Ｉ
Ｃのアドレスが０１０　１０１　０１００１０であり、
行き先ＩＣのアドレスが１１１　１１１１１１　１１１
　１１１であると、原始ＩＣで生成サレタ相対アドレス
は、１０１　０１０　１０１　０１０　１０１となる。

この相対アドレスか、原始及び行き先のアドレスの排他
的論理和（ＸＯＲ）になることが明らかになる。相対ア
ドレス中の１−ビットトが、メッセージパケットが正し
い位置にない次元を識別し。

従って、行き先ＩＣに到達しようとメッセージパケット
が移動する次元を識別することも明らかになる。このよ
うに、偶数番号の次元において、原始及び行き先ＩＣの
アドレスが同じであるような上記の例においては、メッ
セージはそれらの次元の正しい位置にすでに置かれてい
る。しかし、原始及び行き先ＩＣのアドレスが違う術数
番号の次元では、それらの次元のための相対アドレス内
に１−ビットが存在することは、その次元において、メ
ッセージパケットを１つのＩＣから他のＩＣへ移動させ
る必要があることを意味する。

メッセージが１つのＩＣから他のＩＣへ径路指定される
時に、相対アドレスは各移動を考慮に入れるため更新さ
れる。このことば、メッセージバケットが移動される次
元と関連する２重ＩＣアドレス中のビットを考えると都
合良く行なわれる。

その結果、メッセージパケットが行き先ＩＣへ到着する
と２重ＩＣアドレス中のビットは全てゼロになる。

全てのＩＣ中の径路指定回路系は、同一になっていて、
同じ径路指定サイクルを用いて同期的に操作される。Ｉ
Ｃアドレスを１５ビット持つ７３ビットのメッセージパ
ケットの第４図の例として、径路指定サイクルの長さは
基礎的クロック信号ＰＨＩ１の８８サイクルである。各
径路指定サイクルの１回目の間に、各ＩＣにおける径路
指定回路系が径路指定回路系内の各メッセーシパケット
のＩＣアドレスの最初のコピーの先行ビットをテストし
て、そのレベルを決める。この位置にトピットがあり、
第１次元に関連している１０からの出力回線がふさがっ
ていない場合、メッセージパケットは、第１次元出力回
線から、第１次元内でそのＩＣに最も近い隣接ＩＣまで
径路指定される。

メッセージパケットアドレスの先行ビットが０−ビット
であると、メッセージパケットは、第１次元内の正しい
位置にあるので、同じＩＣ内にとどまる。その結果、１
回目の間に、ＩＣの径路指定回路間のメッセージの流れ
は第１次元に沿ったものになる。

メッセージパケット内のＩＣアドレスの最初のコピーの
先行ビットは、その後で破棄される。メッセージパケッ
トが他のＩＣに径路指定されたとすると、２重ＩＣアド
レス内の対応するアドレスビットが、そうした動きを償
うために補足される。

２回目のアドレス時間には、各ＩＣの径路指定回路系は
、再び、ＩＣに存在するメッセージバケットの先行ビッ
トをテストする。しかし、このビットは、メッセージパ
ケットが、第２次元の正しい位置にあるかどうかを表示
するビットである。

もし、このビットが１−ビットで、第２次元出力回路が
ふさがっていなければ、メッセージパケットは、第２次
元出力回線上を、第２次元中のそのＩＣに最も近い隣接
ＩＣに向かって径路指定される。もし、最初のビットが
０−ビットであると、メッセージパケットはＩＣ内にと
どまる。

この過程は、１５回のアドレス時間の間続き、その最後
に、メッセージパケットの最初の１５のアドレスビット
が使い切られる。しかし、必要とされる出力回線が利用
出来れば、ブール１５−立方体を通る径路が確立され、
メッセージパケットの残りを転送することが出来る。

この径路指定機構の実例は、第；３図のフール４−立方
体を参考にして示される。メッセージが、アドレス１１
１１を持つ原始ＩＣ３５′から、アドレス００１０を持
つ行き先ＩＣ３５′へ送られる。、相対アドドレス又は
行き先ＩＣの変位は、原始および行き先ＩＣのアドレス
の排他的論理和を取ることによって得られる。従って、
相対アドレスは、メッセージパケットを第１、第２、第
４次元で移動させ、第３次元では移動してはならないこ
とを表わす１１０１になる。それから、原始ＩＣにある
径路指定回路は、相対アドレスの最初のコピーの最初の
ビットを調べて１−ビットを識別し、もしこの出力回路
が利用出来れば、メッセージを第１次元に沿ってＩＣ０
１１１に径路指定し、ＩＣアドレスの最初のコピーの最
初のビットを破棄し、複製ＩＣアドレス内の最初の１−
ビットを補充する。２回目のアドレス時間内に、アドレ
スが０１１１のＩＣにある径路指定回路が、残りの３個
のアドレスビットの最初のものを調べて、再び１−ビッ
トを見つけ出す。従って、出力回線が利用出来れば、径
路指定回路はメッセージパケットをアドレスが００１１
であるＩＣに送り、第２次元での動きを表示するＩＣア
ドレスの最初のコピー内の１−ビットを破棄し、その動
きが起きたことを示すために複製ＩＣアドレス内に１−
ビットを補充する。

３回目のアドレス時間中に、アドレス００１１にある径
路指定回路が、残りの２個のアドレスビットの最初のも
のを調べて０−ビットを識別する。このＩＣにメッセー
ジパケットを保持し０−ビットを破棄する。４回目のア
ドレス時間には、アドレス００１１にある径路指定回路
が残りのアドレスビットを調べて１−ビットを識別する
。従って、それはメッセージパケットを出力回線に沿っ
てＩＣ００１０まで径路指定し、ＩＣアドレスの最初の
コピーの最後のビットを破棄し、複製ＩＣアドレスの最
後のビットを補充する。

ＩＣ００１０に到着すると、径路指定回路は、テストす
る複製ＩＣアドレス内のどの１−ビットでも無ければそ
れを察知し、従って、メッは−ジパケットがその行き先
に到着したことがわかる。それからメッセージパケット
は、アドレスがメッセージパケット内に明記されている
プロセッサ／メモリに運ばれる。径路指定過程について
の詳細は、第１１図〜第１６図を参照して下記て述へら
れる。

Ｂ、並行処理ＩＣの統括説明 各ＩＣは非常に大きい規格の集積回路（超ＬＳＩ）とし
て単一のシリコンチップ上に組み立てられる。第５図に
示すように、これらのチップの６４（＝２６）個が各チ
ップパッケージ１００に入れられ、各印刷配線回路（Ｐ
Ｃ）板１３０上に取り付けられ、相互結合される。この
ような３２，７６８個のＩＣにそなえて、５１２（＝２
９）枚の印刷配線回路板が、適当な枠体内に取り付けら
れる。従来からある配線取り付は具１３２が、２次元格
子及びブール１５−立方体構造の双力において、これら
の配線板を相互結合する。第５図に示した構成では、Ｉ
Ｃの最も近い隣接ＩＣのうち６個が、それと共に同じＰ
Ｃ板に取り付けられ、他の９個は違うＰＣ板に取り付け
られる。

９７本のビン１０２かそれぞれのパッケージ上に付けら
れ、そのチップをＰＣ板上の他のチップとシステムの他
の部分に接続している。これらの９７本のビンが運ぶ信
号を表ＩＩＩに示す。■○−Ｉ２７、リセット、ＰＨＩ
１、ＰＨＩ２及びにシンクと名付けられたピンはバス２
２に接続され、命令信号、リセット信号及びタイミンク
信号、ＰＨＩ１、ＰＨＩ２及びにシンクをマイクロコン
トローラ２０から受ける。ＣＳ０及びＣＳ１ビンは、両
方のピンでの信号が低い時にチップをアドレス付けする
チップ選択ピンである。これらのピンを選択する信号は
バス２４によってアレイ３０に与えられる。

Ｎ０−７，ＳＷ０−７及びＥ０−７ビンは、北、南、西
及び東の隣接するチップ上の最も近いプロセッサ／メモ
リへの接続を行なう。Ｃｕｂｅ　ｉｎ０−１４及びＣｕ
ｂｅ　Ｏｕｔ０−１４ピンは、ブール１５−立方体内の
最も近い隣接プロセッサ／メモリへの接続を行なう。グ
ローバルピンは、回線２６を越えてマイクロコントロー
ラ２０に接続される。ＬＥＤピンは、活性化されている
時に発光ダイオードを駆動してチップに視覚信号を生成
させる出力を提供する。この信号を用いてテストや監視
を行い、また計算の結果を表示したりすることも出来る
。６本の接地及び電源ピンは、チップに接地及び電源接
続をする。

第６Ａ図及び第６Ｂ図は、アレイ３０の３２，７６８個
の同一のＩＣ３５のうちの１個をブロック図で構いてい
る。第６Ａ図に示すように、１個のＩＣの；３２のプロ
セッサ／メモリ３６は、８列で４行のアレイ内で接続さ
れている。そして便宜上、このアレイの稜は、北、東、
南及び西と識別されている。第６Ａ図には個別のプロセ
ッサ／メモリの空間関係が描かれていないが、第１７図
のチップ配置図に見られるように、それらの空間関係は
異なっている。

第６Ａ図にもどると、各プロセッサは、Ｎ，Ｅ，Ｓ及び
Ｗとラベルを付けた入出端子を通じて、北、東、南及び
西の最も近い隣接者と接続されている。

また、各プロセッサはデイジーとラベルを付けた入力端
子を通じて１つの回線内にデイジーチェーンにつながれ
ている。各プロセッサからこれら５個の入力端子への出
力は、最も近い隣接者のＮ、Ｅ，Ｓ及びＷ入力端子と、
チェーン内に次のプロセッサ／メモリのディジー入力端
子とに接続されている出力端子キャリー上にある。後に
明らかになるように、ディジーチェーンは１３部左端角
に始まり、第１列目を上へ行き、２列１１は下行し、２
３列１１は上へ行きというように進んで、アレイの下部
右端角に達する。

８本の双方向回線１０４か、このプロセッサ／メモリア
レイから北のＮ０−７チップピンに伸び、さらに８本の
双方向回線１０６かプロセッサアレイから南のＳＷＯ−
７に伸びる。これらの８本の回線１０６のうち４本は、
西からの４本の双方向回線１０８と多重化される。さら
に３４本の双方向回線１１０が、アレイから東のＥＯ−
３チップピンへ伸びる。

これらの回線の読み取り／書き取り機能は、書き取り回
線１１３．１１４．１１５によって制御され、それらは
回線励振器１１７．１１８．１１９をそれぞれ制御し、
データを北、東又は南／西に書き込む。南と西の導線の
多重化は、２次元格子アレイ内のデータの流れか一時的
に一方向（例えば、東から西）にしか流れないので、可
能である。

格子及びティジ−チェーン接続に加えて、各プロセッサ
／メモリは共通してアドレス及び出力伝号バス１２１、
メンセージパケット入力信号回線１２２、メッセージパ
ケット出力信号回線１２３、及びグローバル出力信号回
線１２４に接続されている。これらの回線とバスへの接
続は、最東端の４個のプロセッサ／メモリについてのみ
第６Ａ図に示されているが、３２個全てのプロセッサ／
メモリにも同じ接続がなされることが理解出来るだろう
。

第６Ｂ図に示すように、各ＩＣはタイミング発生器１４
０、プログラム可能な論理アレイ（ＰＬＡ）１５０、通
信インタフェース装置（ＣＩＵ）１８０、及び径路指定
回路２００から成る。タイミング発生器はシフトレジス
タ１４５で、システムクロック信号ＰＨＩ１及びＰＨＩ
２によってパルスがきざまれる。この発生器はマイクロ
コントローラ２０からのタイミング信号、Ｋシンクによ
ってリセットされる。よく知られる技術によって、この
レジスタは第９図、第１０図、第１４図及び第１６図に
示される型のタイミング波形を作り出し、通信インタフ
ェース装置１８０及び径路指定回路２００の動作を制御
する。

プログラム可能な論理アレイ（ＰＬＡ）１５０は、マイ
クロコントローラ２０から回線２２上の命令を受け、こ
れらの命令をアドレス及び出力信号バス１２１の信号に
復号化する復号化マトリックスである。命令は、表■に
識別されている２８本のピンの上にあるチップパッケー
ジ１００で受け取られる。

１５−８及び２７ピンの信号は例外であるが、これらの
信号はＰＬＡ入力ラッチ１５１に直接送られＰＬＡ１５
０によって復号され、プロセッサ／メモリ：３６によっ
て使われる間、そこに記憶されている。

１５−８ピン上の信号は、４個のＡＮＤゲート１６５に
送られ、そこで、ピン１２７上の信号が高くなった時に
メンセージパケット入力信号回線１２２に受けた信号の
最後の４ビットに従って変更される。

ピン１２７は、否定回路１６６によって、これら最後の
４個のビットを記憶する直列−入力、並列−出力ラッチ
１６７、及び、ピン１２７上の否定信号とラッチ１６７
の並列出力との論理和を形成する４個のＯＲゲート１６
８に接続される。

第６Ｂ図に示されるように、バス１２１は、２個の１６
６回線バス１５２１５４及び各プロセッサ／メモリ内の
ＲＡＭレジスタ２５０に接続されている２個の３２回線
バス１５６．１５８、ＡＬＵ２７０に接続されている２
個の８回線バス１６２，１６４．８回線バス１７２、２
個の１６回線バス１７４，１７６、そして、各プロセッ
サ／メモリ内のフラグコントローラ２９０に接続されて
いる１本の回線１７８を含む。バス１５２．１５４．１
５６．１５８．１７２．１７４及び１７６上の信号は、
ＲＡＭレジスタ２５０及びフラグコントローラ２９０内
の特定の場所から又はそこへの情報を読み出すか書き込
むために使われる復号アドレス信号である。このアドレ
ス指定を完成するには、バスの１回線が１個の２進信号
、例えば、高信号又は１−ビットを送り、他の回線全て
が他の２進信号、例えば低信号又は０−ビットを送る。

ＡＬＵ２７０へのバス１６２１６４上の信号は、ＡＬＵ
２７０の違う可能性のある出力である。これらの信号に
ついての詳細は、第７Ａ図と第７Ｂ図を用いて下記に述
へる。

通信インタフェース装置（ＣＩＵ）１８０は、ＩＣのプ
ロセッサ／メモリとそのＩＣに関連する径路指定回路と
の間で出入りするメッセーシパケットの流れを制御する
。ＣＩＵ１８０は否定回路１８１、ラッチ１８２、タッ
プされたシフトレジスタ１８４、第１、第２セレクタ１
８６，１８８及び第１、第２パリテイ論理回路１９０，
１９２とを含む。第６Ｂ図に示すように、ＩＣのプロセ
ッサ／メモリ３６からのメッセージパケット出力信号回
線１２３は、否定回路１８１によって、ラッチ１８２へ
の入力、シフトレジスタ１８４、セレクタ１８６、及び
パリティ論理回路１９０に接続される。

ラッチ１８２の出力は、回線１９４上を径路指定回路２
００へ送られ、プロセッサ／メモリ３６のうちの１個か
らメッセージパケットが利用出来る時を指示する。メッ
セージパケット自体は、セレクタ１８６から回線１９６
上の径路指定回路に送られる。

ＣＩＵ１８０で受け取られた時の状態では、出て行くメ
ッセージパケットは、行き先ＩＣの相対ＩＣアドレスの
コピーを１つだけ持っている。タイミング発生器１４０
からのタイミング信号の制御のもとで、セレクタ１８６
及びシフトレジスタ１８４が相対ＩＣアドレスのコピー
を生成し、メッセージパケットの前端部に挿入する。パ
リティ論理回路１９０がメッセージパケットの正しいパ
リティビットを計算し、それをメッセージパケットの一
部として径路指定回路に供給する。

径路指定回路からの信号は、回線１９７、１９８及び１
９９上セレクタ１８８に送られる。これらの信号回線は
、それぞれ、入ってくるメッセージパケットが径路指定
回路から来るかどうかの指示、入ってくるメッセージパ
ケット自体、そして、回線１９６上の出て行くメッセー
ジパケットが首尾よく径路指定回路に受け取られたかど
うかの指示を出す。セレクタ１８８の出力は、メッセー
ジパケット入力回線１２２上のプロセッサ／メモリ３６
に送られるメッセージ検知器１９２である。パリティ計
算はパリティ論理１９２によって行なわれる。これらの
回線の動作についての詳細は、下記の第８図の説明中で
述べる。

径路指定回路２００は、ブールｎ−立方体中の最も近い
隣接ＩＣから又はそれらへのメッセージパケットの径路
指定を制御する。回路２００は、回線割り当て器２０５
、メッセージ検知器、バッファ及びアドレス復元器２１
５、及びメッセージインジェクタ２２０とから成る。回
線割り当て器２０５は、その特殊なＩＣの１５個の最も
近い隣接ＩＣからの１５本の入力回線３８及び同じ１５
個の最も近い隣接ＩＣへの１５本の出力回線３９とを持
つ。回線割り当て器２０５には、メッセージ検知器２１
０への１５本のメッセージ出力回線２０６及びメッセー
ジインジェクタ２２０からの１５本のメッセージ入力回
線２０７も持つ。加えて、各メッセージ入力回線２０７
には、関連するメッセージ入力回線２０７上にメッセー
ジがあることを表示するもう１本の回線２０８がある。

回線割り当て器２０５は、入って来る回線３８上に受け
るメッセージパケットのアドレスを分析し、それらがこ
の特殊なＩＣに向けられたものか、あるいは他のＩＣ向
けのものかを決め、可能であれば、メッセージパケット
をその行き先まで径路指定し、このＩＣあてのメッセー
ジパケット、そして、回路割り付けの障害のために径路
指定出来なくなったメッセージパケットを記憶しておく
。

メッセージ検知器２１０はメッセージパケットの受け取
りをチェックし、回線割り当て器２０５から回線２０７
上に受けたメッセージパケットのアドレスを調べ、この
ＩＣあてのメッセージパケットを回線１９８上のＣＩＵ
１８０へ供給する。第６Ｂ図に示された回路内で、回線
１９８は、メッセージパケットを一度に１個しか転送出
来ない。このＩＣに１個以上のメッセージパケットがア
ドレス指定されている場合には、１個のバケットがＣ１
Ｕ１８０に提供され、他のバケットは、違うＩＣにアド
レス指定されている他のメッセージバケットとともにバ
ッファ２１５に提供される。

バッファ及びアドレス復元器２１５ば、タップされたシ
フトレジスタ１８４と構造と機能において似ているタッ
プされたシフトレジスタから成る。バッファ２１５はメ
ッセージバケットの初めにおいてメッセージパケット内
にある複製アドレス情報からメッセージパケットのアド
レスのコピーを再生する。バッファ及びアドレス復元器
の出力はメッセージパケットインジェクタ２２０に加え
られる。

メッセージパケットインジェクタ２２０は、ＣＩＵから
、径路指定回路を循環しているメッセージパケットのグ
ループの中に、一度に１つずつメッセージパケットを注
入する。径路指定回路の詳細は第１１図〜第１６図を参
照して説明される。

ＩＣ３５のチップ配置図は、第１７図に描かれている。

この配置図中でＰＬＡ１５０は右側のチップの上部を下
部のふちに位置する２つのアレイ内に入れられている。

個別のプロセッサ／メモリ３５は、ＰＬＡ１５０の間の
スペースにバス励振器を間に挾んで４つのグループに分
けて形成される。個別プロセッサ／メモリについての下
記の記述から明らかになるように、各プロセッサ／メモ
リは、動的読み−書き記憶装置、このような記憶装置へ
のアドレス指定回路系、ＡＬＵ、フラグレジスタ、フラ
グレジスタへのアドレス指定回路系及び他の励振器回路
の３８ビットを持つ。ＣＩＵ１８０はチップの上部中央
に置かれ、タイミング発生器１４０及び径路指定回路２
００は、チップの左側部分を占める。

この配置では−ＰＬＡ１５０から個別のプロセッサ／メ
モリ３６へのアドレス及び出力信号バス１２１は。

個別プロセッサ／メモリとバス励振器を通る垂直な回線
のアレイである。プロセッサ／メモリからＣＩＵ１８０
への出力回線も、同様に、本質的には垂直な回線である
。１個のプロセッサ／メモリの展開図に示されるように
、プロセッサ／メモリ内の信号の流れは、本質的には、
バス１２１に対して直角になる。その結果、回線の交差
は最小限になり１回路配置が簡素化される。

１個のプロセッサ／メモリ３６を超ＬＳＩ設計内におさ
めるのに要するトランジスタの概数は、１８００個であ
り、ＰＬＡ１５０．３２プロセッサ／メモリ及びバス励
振器のトランジスタの数は約６０，０００個である。タ
イミンク発生器、径路指定回路系及びＣＩＵには約２４
、０００個のトランジスタが必要である。１個のシリコ
ンチップ上に１００，０００以下のトランジスタの集積
回路を構成することは、現在の技術で充分行なえること
であり、約７ｍｍ×８ｍｍの１個のシリコンチップ上に
集積回路３５０大量生産も、今日の技術で可能と思われ
る。

Ｃ，プロセッサ／メモリの説明 プロセッサ／メモリが、第７Ａ図と第７Ｂ図により詳細
に開示されている。第７Ａ図に示されるように、プロセ
ッサ／メモリは、ランダムアクセスメモリ（ＲＡＭ）２
５０、演算論理装置（ＡＬＵ）２８０及びフラグコント
ローラ２９０から成る。ＡＬＵは、３送信源、即ちＲＡ
Ｍ内の２つのレジスタ及び１個のフラグ入力からのデー
タで動き、２出力、即ちＲＡＭレジスタの１個に書き込
まれた合計出力及び、フラグコントローラ内のいくつか
のレジスタと他のいくつかのプロセッサ／メモリにも利
用出来るキャリ出力とを発生する。ＡＬＵの動作は、読
み出しサイクル及び条件つき書き込みサイクルで行なわ
れる。書き込みサイクルの間に、特定の条件が満たされ
ていればこれらの結果がＲＡＭ及びフラグレジスタに書
き込まれる。

ＡＬＵのタイミングは、合計及びキャリ出力の新しく計
算された値が書き込みサイクルの前に利用出来るように
する。このことによって、合計出力信号が書込サイクル
の間にＲＡＭレジスタの１つに書きもどすことができ、
キャリ出力が、１回の命令サイクルの間に同じチップ上
の多数のプロセッサ／メモリを通って伝播することが出
来る。

ＲＡＭ２５０ ＲＡＭ２５０は、各々が３２ビットの１２個のレジスタ
２５４の形に配置された動的読み／書きメモリＩＣ２５
２のアレイから成る。３２ビットの各々は列０から３２
において個別にアドレス指定することができる。レジス
タには０から１５まで番号が付けられ、アドレス回線が
１６のレジスタを呼び出せるように準備される。しかし
、レジスタ１２及び１３は使用されず、レジスタ１４及
び１５は、ＲＡＭ２５０内に記憶されない信号を出す。

０から１１までのレジスタは汎用レジスタである。レジ
スタ１４及び１５は、特別の機能を持つ。レジスタ１４
の全てのビット位置はその時回線１２２上にあるビット
と回じ値を持ち、レジスタ１５のすべてのビット位置は
ゼロになる。このように、レジスタ１５はデータシンク
として働く。

ＲＡＭ２５０ヘの入力は、バスＩ５２．１５４．１５６
．１５８、ＡＬＵ２７０からの合計出力回線２８５．Ｃ
ＩＵ１８０からのメッセージパケット入力回線１２２、
及びフラグコントローラ２９０からの書き込み許可回線
２９８である。ＲＡＭ２５０からの出力は、回線２５６
、２５７である。回線２５６，２５７上の信号は、ＲＡ
Ｍ２５０内の２つの異なるレジスタの同じ列から得られ
、そのレジスタの１つはレジスタＡと呼ばれ、他はレジ
スタＢと呼ばれる。ハス１５２．１５４．１５６．１５
８はこれらのレジスタとその中の列を、マイクロコント
ローラ２０からの命令語に従ってアドレス指定する。

実例をあげると、表ＩＩＩを参考にして、回線１５−８
はＰＬＡ１５０で復号され、レジスタＡを選択又はアド
レス指令するバス１２１の１６本の回線１５２のうちの
１本に高い信号を送り、回線ｌ９−１２は復号されてレ
ジスタＢを選択する１６本の回線１５４のうちの１本に
高い信号を送り、回線Ｉ１３−１７は復号されて、ＲＡ
Ｍ２５０内の３２列のうちの１個を選択する３２本の書
き込み回線１５６のうちの１本又は３２本の読み取り回
線１５８のうちの１本のどちらかに高い信号を送る。こ
のようにして回線１５２−１５８か、１２×３２ビット
ＲＡＭ内の２個のセルを特定し動作が読み出しか書き込
みかを特定する。

ＲＡＭ２５０の詳細は、ＲＡＭ２５０の上部左隅の４個
のセルと関連する回路系とを描いている第７Ｂ図に示さ
れる。各セル２５２は、図示されるように接続されてい
る３個のパストランジスタ２６１、２６２．２６３を含
み、トランジスタ２６３内に情報の１ビットを記憶する
。データ１ビットは、読み出し選択回線の１つ及びパス
トランジスタ２５２の１つの上の信号の制御のもとに、
トランジスタ２６３がら読み出される。

３２個のセル２５２の各レジスタ２５４も、ビット回線
２５５、リフレッシュ回路２６４及びプレチャージ１、
ランジスタ２７１を含む。加えて、回線１２２は１組の
パストランジスタ２７３，２７４に接続され、他の１組
のパストランジスタ２７３．２７４には接地接続がなさ
れ、０−ビットの送信側となり、レジスタ１５としてデ
ータシンクとなる。１６個のパストランジスタ２７３は
レジスタＡ選択２７５を構成し、各パストランジスタは
、ＡＮＤゲートとして機能し、それは１６本の回線のう
ちの異なる１本によって使用可能になり、ＲＡＭ２５０
内の１６ものレジスタのうちの１個カラレジスタＡを選
択する。同様に、１６個のバストランジスタ２７４はレ
ジスタＢセレクタ２７６を構成し、各トランジスタは、
これら１６個のレジスタからレジスタＢを選択する１６
本の回線１５４の異なる１本に接続される。どのような
時も、パストランジスタ２７３のうちの１個のみ、そし
てパストランジスタ２７４のうちの１個のみが、レジス
タＡ及びレジスタＢの出力を選択するために導通してい
る。

各トランジスタ２７３の出力は一緒に接続され、回線２
５６上にレジスタＡ信号を出し、各トランジスタ２７２
の出力は一緒に接続され、回線２５７上にレジスタＢ信
号を送る。回線２５６１の信号が、双方向ドライバ２５
８によってＡＬＵ２１１１０への入力に送られる回線２
５７上の信号は、ドライバ２５９によってＡＬＵ２８０
への他の入力へ送られる。

ＡＬＵの書き込みサイクルの間、合計出力信号はレジス
タＡに書きもどされる。好都合なことに、この信号は、
双方向ドライバ２５８、回線２５６及び信号を導通して
いるパストランジスタ２７３を経てレジスタＡのトラン
ジスタ２６６へ送られる。

ＲＡＭ２５０は４相りロック信号で動くが、その信号の
うちの２個は基本的クロック信号ＰＨＩ１及びＰＨＩ２
であり、他のＰＨＩ１ｐ及びＰＨＩ２ＰはＰＨＩＩ及び
ＰＨＩ２のプレカーソルである。クロック信号ＰＨ１１
ｐ及びＰＨＩ２Ｐはプレチャージ回線２７２に与えられ
、クロックサイクルＰＨＩｌの間の各読み出し動作及び
クロックサイクルＰＨＩ２の間の各書き込み動作の前に
ビント回線２５５をプレチャージする。クロンクサイク
ルＰＨＩ１ｐ及びＰＨＩ２ｐの間、プレチャージ回線２
７２の信号は高く、プレチャージトランシスタ２７１を
導通させ、正電圧源ＶＤＤ及び各ビット回線との間の接
続を行なう。クロックサイクルＰＨＩ１ｐの間に、この
接続によって各ビット回線２５５を、高い信号又は１−
ビットに充電する。

タロックサイクルＰＨＩＩの間、１前回の書き込みサイ
クルの間にバストランジスタ２６３に記憶された信号が
反転された形でＲＡＭ２５０の各レジスタのビット回線
２５５で読み出される。記憶された信号が高い信号又は
１−ビットであると、バストランジスタ２６３は導通さ
れ、接地径路を形成する。

その結果、読み出し選択回線１５８上にパストランジス
タ２６２への高い信号が与えられると、接地点への径路
が出来て、それがビット回線２５５を低いものにする。

従って、前回の書き込みサイクルの間にトランジスタ２
６３に告、き込まれた１−ビットへはＯ−ビットに変換
される。逆に、０−ビットかトランジスタ２６３に書き
込まれていると、接地径路か出来ないため、ビット回線
２５５は高いままになる。

その結果、トランジスタ２６３上に書き込まれたビノト
は、再び反転され、この場合は１−ビッＩ−になる。反
転されたビットは、次のクロックサイクルであるリフレ
ッシュサイクルの間に、再反転される。

タロックサイクルＰＨＩ１の間、読み出し回線２５８上
の信号も高く、各トランシスタ２６５を導通させる。そ
の結果、各ビット回線２５５上の信号は、リフレッシュ
回路２６４内のトランジスタ２６０に書き込まれる。同
時に、レジスタＡセレクタのトランジスタ２７３によっ
て選択されたビット回線１の信号、及び、レジスタＢセ
レクタのトランジスタ２７４によって選択されたビット
回線上の信号とは、トライバ２５８．２５９に送られる
。これらのドライバが、回線２９８上の書き込み使用可
能信号によって使用可能になると、レジスタＡ及びレジ
スタＢ信号はそれぞれ、出力回線２５６及び２５アドの
ＡＬＵ２８０に送られる。

クロックサイクルＰＨＩ２Ｐの間、プレチャージ回線２
７２及びリフレッシュ／書き込み回線２６９は高く、各
トランジスタ２６７及び２７１を導通させる。

クロックサイクルＰＨＩ１の間にトランシスタ２６６上
に１−ビットが書き込まれると、そのトランジスタも導
通され、ビット回線２５５を低くする接地径路か形成さ
れる。その結果、クロックサイクルＰＨＩ１の間にトラ
ンジスタ２６６上に書き込まれた１−ビットは、０−ビ
ットに変換される。逆に、０−ビットトランジスタ２６
６に書き込まれていたとすると、リフレッシユ回路２６
４には接地径路かなく、ビット回線２５５は、正電圧源
ＶＤＤとビット回線２５５間に導電径路を作るプレチャ
ージトランジスタ２７１によって高くされる。その結果
、トランジスタ２６６に書き込まれた０−ビットは１−
ビットに反転される。

クロックサイクルＰＨＩ２の間、各ビット回線上の信号
は、書き込み選択回線１５６の１本によって選択された
列内のセルの各トランジスタ２６３に書き込まれる。特
に、書き込み選択回線１５６の１本に高い信号が加えら
れると、それが加えられたトランジスタ２６１は導通さ
れ、ビット回線２５５とトランジスタ２６３との間に径
路が出来て、各ビット回線上の信号がトランジスタ２６
３上に書き込まれる。この信号は、クロックサイクルＰ
ＨＩ１の間にトランジスタ２６３から読み出された時に
一度、又、クロックサイクルＰＨＩ２ｐの間にトランジ
スタ２６６から読み出された時に一度、反転されている
ので、トランジスタ２６３へ書きもどされた信号は、最
初に読み出された信号と同じであり、トランジスタはリ
フレッシュされる。

しかし、レジスタＡ出力を作るビット回線２５５の場合
は、クロックサイクルＰＨＩ２の間にトランジスタ２６
３に書き込まれた信号は、ＡＬＵ２８０の合計出力であ
り、トランジスタ２６３から最初に読み出された信号で
はない。合計出力信号は、クロックサイクルＰＨＩ２Ｐ
の間に、回線２８５上の双方向ドライバ２５８に使える
ようになる。この信号が低いと、ドライバ２５８は、ク
ロックサイクルＰＨＩ１の間にトランジスタ２６６上に
記憶された信号の状態に関係なく、レジスタＡ内のトラ
ンジスタ２６５上に０−ビットを書き込む。同様に、合
計出力信号が高いと、ドライバ２５８が、クロックサイ
クルＰＨＩ２ｐの間にトランジスタ２６６に上に記憶さ
れた信号に関係なく、トランジスタ２６６上に１−ビッ
トを書き込む正電圧源ＶＤＤに径路を作る。ここでも、
トランジスタ２６６上の１−ビットがビット回線２５５
を低くし、０−ビットか回線２５５を高くする。その結
果、クロックサイクルＰＨＩ２の間、レジスタＡのビッ
ト回線２５５の状態は合計出力信号の逆であり、あのレ
ジスタのセルのトランジスタ２６３上に書き込まれた信
号になる。

フラグコントローラ２９０ 第７Ａ図に示すように、フラグコントローラ２９０は、
８個の１−ビットＤ−タイプフリップーフロップ２９２
．１５から２を取り出すセレクタ２９４及びいくつかの
論理ゲートのアレイである。フリップ−フロップ２９２
への入力は、ＡＬＵ２８０からのキャリ出力信号、セレ
クタ２９４からの回線２９８上の再き込み使用可能信号
、及びＰＬＡ１６０からのバス１７２の８本の回線であ
る。回線１７２はアドレス回数であり、その各々はフリ
ップ−フロップ２９２の他の１つに接続され、フラグビ
ットが書き込まれるフリップ−フロップを選択する。実
例をあげると、フリップ−フロップはそのフリップ−フ
ロップに接続されている回線上の高い信号によって選択
され、低い信号は、他の７個のフリップ−フロップに接
続された他の７本の回線上におかれる。フリップ−フロ
ップ２９２の出力は、セレクタ２９４に加えられる。

これらのフリップ−フロップのうちの１つ、グローバル
フリップ−フロッブの出力は、パストランシスタ１２４
′によってグローバル出力信号回線１２４に加えられ、
他のフリップ−フロップ、ＣｏｍＥフリップ−フロップ
の出力は、ＮＡＮＤゲート２０３に加えられ、ＮＡＮＤ
ゲートの出力は、パストランジスタ１２３′によってメ
ッセージバケット出力信号回線１２３に送られる。

セレクタ２９４への入力は１６のフラグ借り回線２９５
にもなり、そのうち８本はフリップ−フロップ２９２か
らのもので、バス１７４．１７６の各々から１６本の回
線が来る。回線１７４．１７６はアドレス回線であり、
出力又はそれより先の処理のためのフラグシグナル回線
の１つを選択する。セレクタ２９４は回線２９６及び２
９７の出力を与え、それらの回線は、それぞれアドレス
回線１７４及び１７６によって選択されたフラグのどち
らかになる。回線２９６上のフラグはフラグアウト信号
である。回線２９７上のフラグは、排他的ＯＲゲート２
９９によってＰＬＡ１５０からの回線１７８上の信号と
比較され、書き込み使用可能信号を回線２９８上に作り
出す。

セレクタ２９４は、ＲＡＭ２５０内のアレイ２７５．２
７６に似た、各々１６のバストランジスタの２本のアレ
イによって助けられる。１６本の回線１７４の各々が最
初のアレイの１個のバストランジスタを制御し、１６本
の回線１７６の各々は、２番目のアレイの１個のバスト
ランシスタを制御する。バストランジスタの各々は、回
線１７４，１７６上の適すな信号によって使用可能にさ
れるＡＮＤゲートを構成する。個別のフラグ入力は、各
アレイに１個ずつ、２個の異なるバストランシスタに送
られる。回線１９６上のＦＬＡＧ　ＯＵＴ信号は、最初
のアレイの１６個のパストランジスタの出力の単なる論
理ＯＲである。回線１９８上の書き込み使用可能信号は
、２番目のアレイの１６個のパストランジスタの出力の
論理ＯＲを回線１７８上の信号と比較することによって
えられる。

フラグの名称、アドレス及び機能を表■に示す。

８個のフラグレジスタ２９２（アドレス０−７）は、Ａ
ＬＵ２８０のキャリ出力回線からのデータを書き込んで
もよい。これらの値は、プロセッサ／メモリの内部動作
に用いてもよい。フラングローバル及びＣｏｍＥは、特
別な機能を持っている。チップ上の全てのプロセッサ／
メモリからのグローバルフラグの出力は、一緒に反転及
びＯＲされ、チップ上のグローバルビン（表■参照）に
、バス１２４上に加えられる。３２，７６８個のチップ
のアレイ内の全てのグローバルビンの出力は、ともにＯ
Ｒされ、回線２６上でマイクロコントローラ２０に加え
られる。

ＣｏｍＥフラグはＡＬＵ２８０のキャリ出力を、ＣＩＵ
１８０へのメッセージバケット出力信号回線１２３へ送
る。チップ上の数個のプロセッサ／メモリが同時に回線
１２３に出力を与えると、径路指定回路２００への回線
１９６上のＣＩＵ１８０の出力が、その時に回線１２３
に出力を与えている全てのプロセッサ／メモリのキャリ
出力の論理和になる。

北、東、南及び西フラグは、北、東、南及び西の最も近
い隣接プロセッサ／メモリのキャリ出力回線からのプロ
セッサ／メモリへの入力となる。

同様に、ディジーフラグは、ディジーチェーンで隣にあ
るプロセッサ／メモリのキャリ出力回線からの入力であ
る。通信インタフェース装置（ＣＩＵ１８０からのメッ
セージは、メッセージパケット入力信号回線１２２によ
り、フラグコントローラ２９０とＲＡＭ２５０への入力
に送られる。プロセッサ／メモリからのメッセージは、
メッセージパケット出力信号回線１２３のＣＩＵ１８０
に与えられる。ゼロフラグは常にゼロ出力を提供する。

前述のように、プロセッサの動作には読み出しサイクル
及び書き込みサイクルが含まれる。読み出しサイクルの
間に、チップのピン１１８−２１上の信号が読み出され
るフラグのアドレスを特定する。

これらの信号はＰＬＡ１６０によって復号化され、１６
本回線バス１７４上のセレクタ２９４に送られる。書き
込みサイクルの間に、チップのピン１１８−２１上の信
号が、キャリ出力が読み出されにうとしているフラグレ
ジスタ２９２のアドレスを特定する。ビンＩ１８−２１
上の信号は、読み出し及び書き込みサイクルの間を変化
することもあり、送信側と行き先フラグが違うことがあ
る。

チップ上の全てのプロセッサ／メモリかアドレス及び出
力信号パス１２１に並列に接続されてるので、全てのプ
ロセッサ／メモリはピン１０−２７から同じ命令を受け
る。しかし、名命令の実行はコントローラ２９０のフラ
グの１個の状態によって条件付けされる。チップのピン
Ｉ２２−２５上の信号は、実行が条件付けられているフ
ラグのアドレスを特定し、ピンＩ２６上の信号が、テス
トがゼロのためであるか、それともの１のためであるか
どうかを特定する。これらのアドレス信号はＰＬＡ１５
０で復号化され、１６本回線パス１７６上の１６から２
とるセレクタ２９４へ送られる。ピン１２６上の信号は
、回線１７８上のＸＯＲゲート２９９に送られる。

ＸＯＲゲートへ２９９は、回線１７８上の信号をパス１
７６１６本回線の１本上の信号によって特定されたアド
レスのフラグと比較される。２つの信号が同じものであ
ると、書き込み使用可能信号が、書き込みサイクルの間
に回線２９８上に発生され、これにより、読み出しサイ
クルの間に決定された合計とキャリ出力とが、ＲＡＭレ
ジスタＡ及びバス１７２上の信号によって特定されたフ
ラグレジスタ２９２内に書き込まれる。

ＡＬＵ２８０ ＡＬＵ２８０は、８から１をとる復号器２８２、合計出
力セレクタ２８４及びキャリ出力セレクタ２８６を含む
。

ＡＬ０２８０は、一時に３個のビット上で動作する。そ
のうちの２個はＲＡＭ２５０内のレジスタＡと１３から
の回線２５６．２５７上に、１個はフラグコントローラ
２９０からの回線２９６上にある。ＡＬＵは、２個の出
力を持ち、それらはＲＡＭ２５０のレジスタＡ内に書き
込まれる回線２８５上の合計、及び、フラグレジスタ２
９２に書き込まれ、このプロセッサ／メモリが接続され
ている他のプロセッサ／メモリ３６の北、東、南、西及
びディジーチェーンに加えられる回線２８７上のキャリ
とである。レジスタＡをアドレスするピン１５−８上の
信号は、読み出しと書き込みの間で変化することもあり
、読み出しサイクルの間に特定されたレジスタＡは、書
き込みサイクルの間に特定されたものとは異なることも
ある。

ＡＬＵは、５種の基本動作ＡＤＤ、ＯＲ、ＡＮＤ、ＭＯ
ＶＥ及びＳＷＡＰの変形の全てである３２個の機能の合
計及びキャリ出力を発生することが出来る。特定の機能
が、ビン１０、１１及び１２（表ＩＩＩ）上の信号によ
って選択される。基本動作は、命令語中の適当なビット
を決めることによってＡＬＵへの３つの入力のいずれか
を選択的に補充することによって修正される。これらの
ビットは、ビンＩ２−１４上のチップに用いる。基本動
作、チップ入力及び合計とキャリ出力の要約を表Ｖに示
す。

ここで、Ａ、ＢとＦはそれぞれ、レジスタＡ、レジスタ
Ｂ及びフラグコントローラからの出力であり、Ｖは包含
的ＯＲ動作、＋は排他的ＯＲ動作、出力の組の間に記号
がないものはＡＮＤ動作を表わす。上記の表に示される
ように、■２ビットは、ＭＯＶＥと５ＷＡＰ動作の区別
をするために用いられる。ＭＯＶＥ機能の合計出力とＳ
ＷＡＰ機能の両出力は、Ａ入力からは独立しており、結
果として、レジスタＡからの入力の反転は、これらの動
作にとって意味がない、、ＭＯＶＥ機能のキャリ出力に
刻してレジスタＡの内容は反転されない。

単一のチップ上の３２個のプロセッサ／メモリ内にこの
能力を持たせるために、ＰＬＡ１８０は、ＡＬＵへの入
力の全ての可能な組合わせに列してピンＩ０からＩ４ま
での異なる命令の各々のための合計及びキャリ出力テー
ブルを発生ずるようプログラムされている。ＡＬＵは、
ＡＬＵに加えられた入力の実際の組合わせのため適切な
合計出力及びキャリ出力を選択するたけである。ＡＬＵ
２８０には、３本しか入力がないので、これらの入力上
の信号の可能な組合わせは８組しかない。即ち、０００
，００１，０１０、０１１、１１０．１１１である。こ
れら８組の組合わせに対して、ＰＬＡ１８０は、表Ｖ中
の式で特定されているように合計出力及びキャリ出力を
発生する。従って、ビン１０−Ｉ４上の命令によって特
定された１３２個の命令の各々に対して、ＰＬＡ１８０
は、バス１６４の８本の回線上に可能な合計出力とバス
１６６の８本の回線上に可能なキャリ出力信号とを発生
する。これら２組の信号は、それぞれ、チップ上の各Ａ
ＬＵの合計出力セレクタ２８４及びキャリ出力セレクタ
２８６にあたえられる。

第７Ａ図に示すように、これらのセレクタの各々はパス
トランジスタのアレイであり、パストランジスタの各々
は、復号器２８２の出力上の適切な信号によって使用可
能になるＡＮＤゲートを構成する。これらの出力のそれ
ぞれは、出力回線に隣接する桁の数字によって表示され
るようにその入力で受けた信号の８組の可能な組合わせ
の一つに相当する。それ故、回線２８５上の合計を出力
及び回線２８７上のキャリ出力とは、２個の信号となり
、１個は回線１６２の１本上にあり、他の１個は回線１
６４上にあり、復号器２７２への入力の特定の組合わせ
のために表Ｖの式で定義された出力である。

例えは、ＡＮＤ機能を考えてみると、表Ｖに特定されて
いるように、この機能のための合計出力とキャリ出力は
、復号器２８２への少なくとも１個の出力が０−ビット
の時は０−ビットであり、出力は、復号器２８２への入
力全てが１−ビットの時のみ１−ビットレこなる。復号
器２８２への入力の８組の可能な組合わせのうちの１組
のみか全て１−ビットなので、８本の回線１６２のうち
の１本のみ、そしてＰＬＡ１８０からＡＬＵ２８０への
８本の回線のうちの１本のみが、ＡＮＤ機能がピン１０
上のＩ−ビット及びピン１１上のＯ−ビットによって特
定された時に１−ビットを出す。従って、セレクタ２８
４及び２８６内のゲートによって送られる帰りは、復号
器２８２への全ての入力が１−ビットの時以外は０−ビ
ットである。

ピン１０−１４上に特定された３２個の機能のための回
線１６２及び１６４上の出力回線の完全な表が、表■に
示される。

これらの３２機能、及びＲＡＭレジスタ１５とフラグコ
ントローラ双方のゼロのソースは、下記の動作の全てを
実行することが出来る。。

整列したフィールトの加勢または減算、定数の加算また
は減算、 フラグレジスタ及び／またはレジスタＡへの出力を持つ
２つのレジスタのノール（または論理）機能の計算、 フラグレジスタ及び／またはレジスタＡへの出力を持つ
レジスタＡ及びフラグのフール機能の計算、 １つのＲＡＭレジスタから他へ、レジスタからフラグレ
ジスタへ、または、フラグレジスタからＲＡＭレジスタ
への移動、 レジスタの桁移動または置換、 整列したフィールドを比較して１つか他と等しいか、他
より大きいか、あるいはまた、小さいかということの決
定、 フィールを定数と比較して一方が他と等しいか、他より
大きいか、または小さいがということの決定、 均等性をめるため、一時に２ビットの定数を持つ欄の比
較。

例えば、レジスタＡ及びＢの内容を加算するためには、
レジスタＡ及びＢを識別するビン１５−１８、１９−Ｉ
１２上の信号、及び、ＡＤＤ命令が実行されるレジスタ
内の列を識別するピン１３、−１１７上の信号とともに
、ＡＤＤ命令０００００を、チップパッケージ１００の
ピンＩ０−１４へ３２回与える。

その上、ピンＩ１８−１２１上の信号は、各ＡＤＤ動作
への第３の入力とキャリ出力が書き込まれるフラグレジ
スタを構成するフラグを識別する。ビン１２２−Ｉ２５
上の信号は書き込み段階か条件付けられようとするフラ
グを特定し、ピンＩ２６上の信号が、テストの条件を特
定する。３２個の命令の実行過程を通して、ＡＤＤ命令
及びレジスタＡ及びＢの識別が一定なので、ピンＩＯか
らＩ１２上の信号は同しままである。ピンＩ１３−Ｉ１
７上の信号によって示される列数は、ＡＤＤ命令が実行
される度に１つずつ増加し、レジスタＡ及びＢ内の異な
る組のビットを呼び出す。ＡＤＤつ命令を最初に実行す
るには、読み出しサイクルの間にピン１１８−Ｉ２１上
の信号は１１１１となり、ゼロフラグをアドレス指定し
、それによってキャリ入力をゼロで初期値を設定する。

ＡＤＤ動作の残りの３２回の実行の最初の書き込みサイ
クル及び読み出し書き込みサイクルのために、ビンＩ１
８−Ｉ２１上の信号が、フラグレジスタ２９２のうちの
１つをアドレス指定し、キャリ出力がそこに記憶され、
そこから読み込み出されるようにする。回線２８５上の
合計出力は、レジスタ入力に書きもどされる。

減算は、減数であるレジスタ人力の相補を伴うＡ　Ｉ）
　Ｄ命令によって実行される。乗算及び除算は、種々な
加算及び減算算法を用いて実１１することかできる。

プール機能は、同じような方式で、一度に１列ずつ実行
される。ＡＮＤ及びＯＲ機能の場合は、結果は合計出力
を経てレジスタＡに与えられる。

結果は、キャリ出力を経てフラグレジスタにも与えても
よい。排他的ＯＲ（ＸＯＲ）機能は、フラグがＡ及びＢ
入力のいずれかの組が同じではないかどうかを記録する
ために用いられるＭＯＶＥ機能のキャリ出力によって与
えられる。ＮＡＮＤ及びＮＯＲ機能は、全ての入力が相
補された時、それぞれ、ＯＲ機能及びＡＮＤ機能から、
周知の論理式に従って与えられる。レジスタ転送動作も
、一度に１列ずつ、レジスタＢと指示されたレジスタの
内容を、レジスタＡと指示されたレジスタへ転送するＭ
ＯＶＥ機能を用いて、同様に行なわれる。

データ桁移動動作は、ＳＷＡＰ機能及びフラグレジスタ
を用いて行なわれる。桁移動されるデータの各ビットは
、先ず、レジスタＢと指示されたＲＡＭレジスタ内のそ
の列から読み出され、指示されたフラグレジスタに記憶
される。次のＳＷＡＰ命令の実行に際して、フラグレジ
スタ内のデータビットは、ＲＡＭレジスタ内の隣接する
列内に書き込まれ、ＲＡＭレジスタＢ内のその列中のデ
ータビットはは、フラグレジスタに書き込まれる。桁移
動の方向は、ＲＡＭレジスタ１３内のデータが最も有意
性の少ないビットから最も有意性のあるビットへ、ある
いはその逆にアドレス指定されたかどうかによって決ま
る。。

ＳＷＡＰ機能は、レジスタＢからキャリ出力回線へデー
タを与え、北、東、南、西またはデージーチェーンのい
ずれかからレジスタＢヘデータを書き込むことによって
、データが１つのプロセッサから他へ送られるようにも
する。

比較演算の実現のための算法は、この技術に通した人々
にとっては前述の説明で明らかであろう。

例えば、２ビット間の違いは、それらを合計しキャリを
無視することによって識別出来る、その場合の合計が０
−ビットならば、違いはない。１−ビットであれば、違
いがある。プロセッサ／メモリーによる異なる命令の各
々を実行することからくるキャリ出力は、チップ上の最
も近い隣接プロセッサ／メモリの北、東、南及び西入力
への回線２８７上で使用可能である。これは、ディジー
チェーン内の次のプロセッサ／メモリのディジー入力に
も使用出来る。これら隣接するプロセンサ／メモリへの
入力を経て、キャリ出力は、チップ上の他の離れている
プロセッサ／メモリにも使用可能にさせることも出来る
。

ＮＡＮＤゲート２９３が動作可能になると、キャリ出力
は、通信インタフェース装置１８０及び径路指定回路２
００へのメッセージパケット出力信号回線１２３へも使
用出来るようになる。この手段によりキャリ出力はメッ
セージバケット内で、アレイ３０中の他のどのプロセッ
サ／メモリにも送達される。

ＰＬＡ１６０、ＲＡＭ２５０、ＡＬＵ２８０及びフラグ
コントローラ２９０についての前述の説明から、ここに
説明されたコンピュータシステムの並行処理能力を利用
したあらゆる種類のコンピュータプログラムを案出する
ことが可能であろう。これらの処理動作は、通常は、処
理されているデータに適するよう選んだ基本的クロック
サイクルＰＨＩＩの持続時間を持つ処理サイクルで実行
される。アレイ３０の異なるプロセッサ／メモ１３６間
の相互作用を改善するには１個々のプロセッサ／メモリ
が径路指定回路２００を通じて互いに通信することも出
来る。このような径路指定について討議する前に、ＣＩ
Ｕ１８０及び径路指定回路２００の動作の理解が望まし
い。

Ｄ．通信インターフェース装置の説明 第６Ｂ図及び第８図に示すように、ＣＩＵ１８０は否定
回路１８１、ラッチ１８２、タップされたシフトレジス
タ１８４、第１及び第２セレクタ１８６、１８８及び第
１と第２パリテイ論理回路１９０，１９２を含み、これ
らの要素の各々は、各図中に同じ番号で識別されている
。第８図に示すように、ラッチ１８２は第１と第２のＤ
−型フリップ−フロッブ３１２，３１４がら形、シフト
レジスタ１８４は７３ビットのシフトレジスタで、入力
端子に続く、１５番と１７番のシフト位置の間に、入力
端子、出力端子及び出カタップを持つ。第１のセレクタ
１８６は、５個のデート３２０．３２２．３２４．３２
６，３２８及びＮＯＲゲート３３０を含む。

そして第１のパリティ論理１９６は、第１と第２のＤ−
型フリップ−フロップ３３２．３３４、及びＮＯＲゲー
ト３３６．３３８から成る。これらの要素は、チップ上
のプロセッサ／メモリからの回線１２３上のメッセージ
パケットを受け取り、それらを、下記のいくつかのタイ
ミング及びデータ処理動作の後に径路指定回路２００に
送信する。第２のセレクタ１８８は、否定回路３４０．
４個のＡＮＤゲート３４２．３４４．３４６．３４８及
びＮＯＲゲート３５２を含む。そして、第２のパリティ
論理は、Ｄ−型フリップ−フロップ３５６及びＮＯＲゲ
ート３５８を含む。これらの要素は、径路指定回路２０
０からメッセージバケットのビットを受け取り、同様に
下記に述べるいくつかのタイミング及びデータ処理動作
の後で、チップ上のプロセッサ／メモリのうちの１つに
伝送する。

メッセージパケットが径路指定回路２００に伝送される
時は、ＣＩＵ１８０ては、径路指定サイクル中の指示さ
れた時点でプロセッサ／メモリから下記の情報を、否定
回路１８１への入力で受け取る用意がある。

これらの信号の全ては、シフトレジスタ１８４に与えら
れ、レジスタからセレクタ１８６へシフトされる。しか
し、これらの信号のあるものは、ラッチ１８２、セレク
タ１８６及びパリティ論理１９０にも与えられる。

径路指定回路２００は、メッセーシバケットが送られる
径路指定サイクルの最初のクロックサイクルで始まる回
線１９４上の低い信号を受け取ることになっている。径
路指定回路２００は、指定された基本クロックサイクル
で回線１９６に下記の情報も受け取ることになっている
。

このメッセージパケットの様式は第４図に描かれている
。回線割り当て装置２０５によって導入される１５クロ
ックサイクルにもなる時間の遅れのために、メッセージ
パケットが完全に処理され、１個又はそれ以上の径路指
定回路によって伝達されるには、少なくとも合計８８ク
ロックサイクルを要する。従って、径路指定サイクルの
長さは、第９図に示すように８８本の基本クロックサイ
クルになる。

ＣＩＵ１８０から径路指定回路２００への信号の流れを
制御するには、タイミング発生器１４０が、第９図に示
すタイミング信号を発生する。回線１２３上のＣＩＵ１
８０が受け取ったメッセージバケットは第９図の上部近
くの２本の線内に描かれている。

メッセージパケットに関連するＣＩＵ１８０で受け取ら
れた最初のビットは、クロックサイクル５３で受け取ら
れたパリティビットである。このパリティビットは、信
号ＴＯＣＩＵ−ＰＡＲＩＴＹ−Ｉｎが、クロックサイク
ル５３の間に、フリップ−フロップ３３２のセラト端子
に与えられた時に、このフリップ−フロップ内にセット
される。このビットは、送信側ＩＣの絶対値中のアドレ
スのパリティである。、フリップ−フロップ３３４及び
ＸＯＲゲート３３６は、タロックサイクル１５での様式
ビットで始まり、クロックサイクル７２のメッセージの
終りまで続くメッセージパケットのパリティを計算する
、このパリティビット及びフリップ−フロップ３３２内
に記憶されたビントは、それからＸＯＲゲート３３８に
よって比較され、その結果のビットはセレクタ１８６へ
送られ、そこで反転され径路指定回路２００に送り出さ
れる。

パリティビットは、メッセージパケットがその行き先に
径路指定されるにつれて相対アドレス中に出来る変化を
償うためにこの方式で計算される。

メッセージパケットの相対アドレスは、メッセーシパケ
ットが、信号回線１２３ヘプロセッサ／メモリから読み
出される時に計算される。そしで、この相対アドレスの
コピート個を含めてメッセージパケット用のパリティビ
ットは、フリップ−フロップ３３４及びＸＯＲゲート３
３６によって計算される。

相対アドレスが、１−ビットの奇数を持っていると、こ
のメッセージパケット用のパリティビットは、メッセー
ジパケットがその行き先で受け取られた時に間違ってい
るであろう。これを補正するために、もし送信側のＩＣ
アドレスのためのパリティビットが１−ビットならば、
ＣＩＵ１８０がＸＯＲゲート内の計算されたパリティビ
ットを変える。行き先では、ＣＩＵ１８０が、受は取っ
たメッセージパケットのパリティビットを再度計算し、
メソセージパケットで受け取ったパリティビットが１−
ビットならば、それを変える。最後に、結果として出た
パリティは、行き先ＩＣのアドレスのパリティビットと
比較される。これら２個のビットが同じならば、パリテ
ィエラーはなかったことが分かるはずである。

クロックサイクル５４の間に、メッセージパケットを次
の径路指定サイクルに送信しなければならない時は、Ｃ
ＩＵ１８０に１−ビット与えられる。このビットは、否
定回路１８１によって反転させられ、信号ＴＯＣＩＵ−
ＭＰ−ｉｎが、クロックサイクル５４の間にこのフリッ
プ−フロップのセット端子に伝えられた時に、フリップ
−プロップ３１２内にセットされる。

その結果、メッセージパケットが送信されなけれがなら
ないと、フリップ−フロップ３１２のＱ出力端子は、ク
ロックサイクル５４につれて低くなる。グロックサイク
ル５５から８６の間に、メッセージデータは、シフトレ
ジスタ１８４の入力端子に入れられ、それを通ってシフ
トされる。レジスタは７３ビットの長さなので、メッセ
ージデータは、次の径路指定サイクルのクロックサイク
ル４０の間にシフトレジスタの出力に現われはじめる。

クロックサイクル８７の間、フリップ−フロップ３１２
のＱ端子の出力信号は、信号ＴＬＡＳＴがフリップ−フ
ロップ３１４のセット端子に入った時に、フリップ−フ
ロップ３１４内にセットされる。その結果、メッセージ
が送られる時は、径路指定サイクルの始まる前から、Ｑ
端子には低い信号が、そして、フリップ−フロップ３１
４のＱ端子には高い信号か存在する。第８図に示すよう
に、フリップ−フロップ３１４のＱ端子は、ＡＮＤゲー
ト３２８への１つの入力に接続され、Ｑ端子は回線１９
４に接続される。従って、もしメッセージが送られると
すると、回線１９４上の信号は第９図に示すようになる
。

クロックサイクルＯ−１４の間、メッセージデーットの
行き先のＩＣアドレスが、シフトレジスタ１８４及びＡ
ＮＤゲート３２６への回線１２３に送られる。

これらのクロックサイクルの間、ＡＮＤゲート３２６は
信号ＴＯＣＩＵ−Ａｄｄによって動作可能になり、その
ためＩＣアドレスは、ＮＯＲゲート３３０を通って径路
指定回路２００への回線１９６へ送られる。タロックサ
イクル１５の間に、ＡＮＤゲートは信号ＴＯＣＩＵ−Ｍ
Ｐ−ＯＵＴ′によって使用可能になり、フリップ−フロ
ップ３１４のＱ端子からＮＯＲゲート３３０及び回線１
９６へ信号を送る。メッセージを送ろうとすると、Ｑ端
子の信号は低い信号であるがそれがＮＯＲゲーグー３３
０によって反転され、メッセージパケットの様式ビット
のための高い信号を発生する。

クロックサイクル１５−１９の間では、行き先ＩＣ内の
特定のプロセッサ／メモリのアドレスがＣＩＵ１８０に
送られ、シフトレジスタ１８４にシフトされ、クロック
サイクル２０−２３の間に、行き先プロセッサ／メモリ
内のレジスタのアドレスが、シフトレジスタにシフトさ
れる。

クロックサイクル１６−３９の間に、ＡＮＤゲート３２
２が、信号ＴＯＣＩＵ−ＴＡＰによって動作可能になる
。

これらのクロックサイクルの間、行き先ＩＣアドレスの
１５ビット、プロセッサ／メモリアドレスの５ビット及
びレジスタアドレスの４ビットが、１６番目と１７番目
シフト位置の間に連続して現われ、ＡＮＤゲート３２２
及びＮＯＲゲート３３０によって回線１９６へ送られる
。

クロックサイクル４０−７１の間では、前回の径路指定
サイクルの間にシフトレジスタ１８４内に挿入されたメ
ッセージデータが、シフトレジスタの出力端子から現わ
れはじめる。これらのクロックサイクルの間、ＡＮＤゲ
ート１２４は信号ＴＯＣＩＵ−ＤＡＴＡによって動作可
能になり、メッセージデータはＮＯＲゲート３３０を通
って径路指定回路２００への回線１９６へ送られる。ゲ
ート３２４は、どのクロックサイクルの間にも動作可能
にされないので、前回のサイクルのクロックサイクル５
５−８６の他の時にシフトレジスタ１８４に送られたデ
ータは、いずれも否定される。

最後に、タロックサイクル７２の間は、ＡＮＤゲ−ト３
２０は信号ＴｏｃｌＵ−ＰＡＲＩＴＹによって動作可能
になり、パリティビットはＮＯＲゲート３３０を通って
径路指定回路２００への回線１９６へ送られる。結果と
して、径路指定サイクルの間の回線１９６上の信号は第
９図に示すようになる。

メッセー■パケットが径路指定回路２００から受け取ら
れると、回線１９７上の信号はクロックサイクル４５間
に低くなり、次の径路指定サイクルが始まるまで低いま
までいる。加えて、ＣＩＵ１８０は、表示された基本ク
ロックサイクルで回線１９８上の径路指定回路２００か
ら下記の情報を受け取ることになる。

回線１９９上の信号は径路指定サイクルの終りに低くな
り、回線１９４上の信号が代わるまで低いままでいる。

入ってくるメッセーパケットがＣＩＵ１８０で受け取ら
れている時に、ＣＩＵは表示されている基本クロックサ
イクルでメッセージデータ入力信号回線１２２へ下記の
信号を送る。

この信号の流れを制御するには、タイミング発生器１４
０も第１０図に示されている信号を発生する。

ＣＩＵ１８０からのメッセージ注入器トが径路指定回路
２００によって受け取られ送り出されている場合は、回
線１９９上の信号は、径路指定サイクルの初めから低い
。クロックサイクル０−４４の間にＡＮＤゲート３４６
は信号Ｔ：ｃｉｕ−ＭＷＩＮによって動作可能になり、
この信号をＮＯＲゲート３５２へ通し、そこで半減され
て信号回路１２２へ１ビットとして送られる。

入ってくるメッセージバケットがあるという事実は、回
線１９７上の信号か、クロックサイクル４５の間に低く
なる時に、確実なものになる。この信号は、クロックサ
イクル４５の間に信号ＴＩＣＩＵ−ＭＰ−ｉｎによって
動作可能にされてしするＡＮＤゲート３４２に送られる
。その結果、低い信号がＮＯＲゲート３５２を通って送
られ、クロッタサイクル４５の間に、メッセージデータ
入力回線１２２上に高い信号を加える。

クロックサイクル４６−５０の間に、セレクタ１８８は
入ってくるメッセージパケットが送られて行くプロセッ
サ／メモリのアドレスを回線１９８上に受け取る。この
信号は、否定回路３４０によって反転され、クロックサ
イクル４６から８６の間に信号ＴＩＣＩＵ−Ｍ−ｉｎに
よって動作可能になっているＡＮＤゲートに送られる。

その結果、プロセッサ／メモリのアドレスはＮＯＲゲー
ト３５２を経て信号回線１２２に通される。

同じような方式で、クロックサイクル５１−５４及び５
５−８６の間に、セレクタ１８８は回線１９８上に入っ
てくるメッセージバケットが送られているレジスタアド
レスとメッセージパケットのデータを受け取る。これら
の信号も否定回路３４０によって反転され、ＡＮＤゲー
グー３４８及びＮＯＲゲート３５２を通ってプロセッサ
／メモリ３６への信号回線１２２へ通される。回線１９
８上に受け取られる信号も、受け取られたメッセージパ
ケットのパリティビットへの計算のためにＸＯＲゲート
５８及びフリップ−フロップ３５６へ送られる。

タロックサイクル８７の間に、メッセージ検出器トのパ
リティビットは、回線１９８上に受け取られる。それは
計算されたパリティビットとＸＯＲゲート３５８で比較
され、結果として出たパリティビットがＡＮＤゲート３
４４に与えられる。クロックサイクル８７の間に、ＡＮ
Ｄゲート３４４が動作可能になり、パリティビットかＮ
ＯＲゲート３５２を経てメッセージデータ入力信号回線
１２２に与えられる。

その結果、径路指定サイクルの間にプロセッサ／メモリ
に送られる信号は第１０図に示す通りである。

Ｅ．径路指定回路の説明 序論 第６Ｂ図に示すように、径路指定回路２００は回路割り
当て装置２０５、メッセージ検出器２１０、バッファ及
びアドレス復元器２１５、及びメッセージ注入器２２０
を含む。回線割り当て装置２０５は、実質的には同一の
径路指定論理セルの１５×１５のアレイを含む。このア
レイの各列が、ブール１５−立方体の１次元中のメッセ
ージパケットの出力を制御する。

このアレイの各行は、径路指定回路２００中の１メッセ
ージパケットの記憶を制御する。９個のそのような径路
指定セル４００が第１１図に描かれているが、左側の列
中の３個は、第１次元に関連し、中間の列の３個は第２
次元と関連し、右側の列中の７３個は、第１５次元と関
連している。セルの各列は、その次元に関連する出力回
線３９に接続する出力バス４１０を持つ。行については
、下の３個がアレイ内で最も低いセルで、入力回線３８
から入力を受ける。上部３個のセルがアレイ内の最上部
のセルである。中間の３個のセルは、底部と上部の間の
どのセルの代理をするものであるが、図示されているよ
うに、最下行に接続されている。

同じく第１１図に示されているのは、３個の処理及び記
憶手段４２０で、回線割り当て器２０５中の対応する３
行のセルからのメッセージを処理し記憶する径路指定回
路２００のメッセージ検出器２１０バッフア及びアドレ
ス復元器２１５及びメッセージ注入器２２０の部分を表
わしている。１２個の似たような処理及び記憶手段（図
示されず）が、他の行からのメッセージを処理し記憶す
るために使用される。手段４２０は、第１５図において
より詳細に説明される。

径路指定において何の矛盾もおきなければ、メッセージ
パケットは、第１次元の径路指定セルへの入力から、プ
ロセッサ／メモリ内のレジスタへ径路指定され、プロセ
ッサ／メモリへは、８８個の基本クロック信号の１回の
メッセージサイクルの間にアドレス指定される。径路指
定に矛盾があると、メッセージパケットは、１ケ所又は
それ以上の中間地点で径路指定回路の処理及び記憶手段
内に一時的に記憶され、このメッセージパケットをその
行き先へ径路指定するには、１つ以上の径路指定サイク
ルが必要となる。

第１１図は、各径路指定セル４００の入力及び出力端子
の便利な概略図になっている。下の行に沿っている３個
のセル４００が示すように、ブール１５−立方体の違う
次元からのメッセージパケットは、ＮＡＮＤゲート４０
５に送られる。これらのゲートは、リセット状態の間で
なけれはいっても動作可能である。各ＮＡＮＤゲート４
０５の出力は、反転されたメッセージパケットであるが
、最下行のセル４００の１個の入力端子Ｌｉｎに送られ
る。端子Ｌｉｎにメッセージパケットが存在することを
表示する信号も、同じセルの入力端ＬＰｉｎに送られる
。下段の各セルのために、このメッセージの存在する信
号は接地され、このことは、セルで受け取ったメッセー
ジパケットをさらに処理するために、下行の隣の列中の
セルを条件付けする効果を持つ。後に明らかになるが、
セルへの入力にメッセージパケットの存在を示すこのよ
うなメッセージの存在する信号が、径路指定回路２００
全体に用いられ、メッセージパケットのための回路２０
０を通るデータ径路を確立する。

回路３８の１本から受け取られたメッセーシパケットは
、端子Ｍ−ＯＵＴからの１つの列内の最下部のセル４０
０の外へ径路指定され、そのＪぐ右の列内のセル４００
の端子Ｍ−ＩＮに印加される。同時に、メッセージの存
在する信号は、端子ＭＰ−ＯＵＴからすぐ右のセルの端
子ＭＰ−ＩＮへ径路指定される。

いずれかのセル４００のＭ−ＩＮ端子で受け取られる信
号は、他にどんな信号がそのネットワーク中にあるかに
よってＢＵＳ端子、Ｕｏｕｔ端子又はＭ−ＯＵＴ端子の
いずれか１つの上にあるセルの外へ径路指定してもよい
。１つの列中の全てのセル４００のＢＵＳ端子は、共通
の出力バス４１０に接続され、共通出力バス４１０はＸ
ＯＲゲート４１５を経て、ブールｎ−立方体のその次元
中の最も近い隣接セルへの出力回線３９に接続される。

ＸＯＲゲート４１５への他の入力は、タイミング信号ｔ
−ＩＮＶ−ＯＵＴｎであり、ここのｎは次元の数である
。このタイミング信号は、メッセージバケット内の複製
アドレス内の適切なアドレスビットを相補し、メッセー
ジパケットがブール１５−立方体を通って移動するにつ
れ、このアドレスを更新する。

Ｕｏｕｔ端子からセルを出るメッセージは、列内でその
すぐ上方にあるセルのＬｉｎ端子に送られ、Ｌｉｎ端子
に受け取られる信号と同し方式でそのセルによって処理
される。メッセージのある信号は、同じ方式で、ＵＰｏ
ｕｔ端子から、そのすぐ上方のセルのＬＰｉｎ端子へ転
送される。

各列のセル４００内の回路系は、各列（または次元）の
出力バス上で、上部に最も近い行内を循環している次元
にアドレスされたメッセージを置き、全ての行を上部の
行に向かって詰めるように設計されている。この目的の
ために、制御信号グレント（Ｇ）及びオールフル（ＡＦ
）が各列に用意され、列の個々のセルに、同じ列内でそ
れらの上方にあるセルの状態を知らせる。特に、グラン
ト（Ｇ）信号は、各列又は次元の出力バス４１０へのア
クセスを、Ｇｉｎ及びＧｏｕｔ端子を通ってセルの各列
へ送られる信号によって制御する。この信号を伝播する
回路系は、その次元へアドレス指定されている各列の最
上部のメッセージパケットへバスアクセスを与え、その
桁の下方のセルのいずれかにあるメッセージが、出力バ
スの上に径路指定されるのを防ぐ。オールフル（ＡＦ）
信号は、あるセル４００から同じ桁内のすぐ上のセルへ
のメッセージの転送を、ＡＦｏｕｔ及びＡＦｉｎ端子を
通じて各セルへ、列内の上方にある各セル内にメッセー
ジがあるかどうかを知らせることによって制御する。

上部のいずれかのセルが空であると、下方の各セル内の
メッセージが１列内の１セル上へ移動する。

セル内のあるフリップ−フロップの動作は、タイミング
信号ｔ＝ＣＯＬｎによって制御される。

この立は次元の数である。一方、他のフリップ−フロッ
プは、基本クロック信号ＰＨＩ１によってクロックされ
る。下記の説明から明らかになるように、各列内の径路
指定セルは、アレイ３０内の全ての径路指定回路の同じ
列内の他の径路指定セルと同期して動作する。

頂上の行のセルには、ＡＦｉｎ端子への入力が常に高い
。これらのセルにとって、Ｇｉｎ端子への入力信号は、
リセット信号の補数であり、それ故に、リセットの間以
外は高くなる。その結果、列内の上部セル中のメッセー
ジパケットは、その次元向けにアドレス指定されていれ
ば、通常は出力バス４２０への呼び出しを持っている。

しかし、もし出力回線３９が故障するようなことがある
と、その回線に関連する次元の上部セルのＧｉｎ端子に
低い信号を送ることにより、相互接続されている１５−
立方体のネットワークからこの回線を取り除くことが出
来る。セル４００の下行では、Ｇｏｕｔ端子からのグラ
ント信号が、出力バスに接地を与えることの出来るパス
トランジスタ４２５を制御するために用いられる。特に
、その出力回線上に送り出されるメッセージがない場合
は、０−ビットが、その次元の出力回線に書き込まれる
。

回線割り当て装置２０５ 回線割り当て装置２０５の論理回路系の詳細が第１２図
に示されている。この図は、例示的に最下部の２行及び
第１と第２の次元に関連する列内にあげた４個のセルを
示す。回路は、下記に説明されるように、ＯＲゲート４
８０を除いて、はぼ同じである。各回路は、第１１図に
関して説明したように、入力回線又は端子Ｌｉｎ、ＬＰ
ｉｎ、Ｍ−ＩＮ及びＭＰ−ＩＮを持つ。各回路は出力回
線又は端子Ｕｏｕｔ、ＵＰｏｕｔ、バス、Ｍ−ＯＵＴ及
びＭＰ−ＯＵＴも持つ。制御信号は、端子Ｇｉｎ及びＡ
Ｆｉｎで各セルに与えられ、最下部のセルを除いて、こ
れらの制御信号は、端子Ｇｏｕｔ、及びＡＦｏｕｔを経
て列内の、次に下方のセルへ送られる。

論理回路系は、２個のＮＡＮＤゲート４５０及び４５２
、端子Ｍ−ＯＵＴ及びＭＰ−ＯＵＴへの出力信号の選択
を制御する４個のＡＮＤゲート４６０．４６２．４６４
及び４６６、ＮＡＮＤゲート４７０及び、ＡＮＤゲート
４６０及び４６４の組、またはＡＮＤゲート４６２及び
４６６の組のどちらかを動作可能にする否定回路４７２
、ＡＮＤゲート４６０と４６２の出力を結合させるＮＯ
Ｒゲート４７６、そして、ＡＮＤゲート４６４と４６６
の出力を結合させるＮＯＲゲート４７８とを含む。

否定回路４７２の出力は、端子ＡＦｏｕｔによって、列
内の、次に下方のセルに与えられ、Ｍ−ＩＮとＭＰ−Ｉ
Ｎ回線からＵｏｕｔとＵＰｏｕｔ回線への信号の桁移動
を制御するオールフル（ＡＦ）信号でもある。さらに、
最下行のセルは、その入力がＡＦｉｎとＭ−ＩＮ端子に
接続されているＯＲゲート４８０を含む。各セルは、３
個のＤ−型フリップ−フロップ４９０．４９２及び４９
４．バス駆動５００そして、バス駆動とグラント信号を
制御するための論理回路５０２も持つ。

フリップ−フロップ４９０は、列クロック信号ｔ−ＣＯ
Ｌｎを受け取るとメッセージパケットの先頭ビットを記
録し、８８個の基本クロックサイクルあとで次の列クロ
ック信号を受け取るまで、この信号を保持する。先頭ビ
ットが１−ビットの場合、および、出力パス４１０が、
列内でより高いセルにグランドされていない場合には、
論理回路５０２はバス駆動に低い信号を送る。バス駆動
５００への回線上の低い出力は、パス駆動を動作可能に
し、ＮＡＮＤゲート４５０、４５２及び４７０を動作不
可能する。その結果、入力端子Ｍ−ＩＮ−上のメッセー
ジはパス４１０上を、その列又は次元に関連する出力回
線３９へ径路指定される。ＮＡＮＤゲート４７０が動作
不可能な時は、その出力は高く、ＡＮＤゲート４６２，
４６６を動作可能にし、否定回路４７２がらの出力を低
くさせ、それによってＡＮＤゲート４６０．４６４を動
作不可能にする。その結果、次に下方のセルに送られた
オールフル（ＡＦ）信号は低く、列内の上に空のセルが
あるということをそのセルに知らせ、ＡＮＤゲート４６
２．４６６は動作可能になって入力端子ＬｉｎとＬＰｉ
ｎで受け取った信号を通すようになる。

メッセージパケットの先頭ビットが０−ビットである場
合、または、径路指定セルのＭ−ＩＮ端子にメッセージ
パケットがない場合には、バス駆動５００への論理回路
５０２の出力は高くなる。バス駆動への高い信号は、Ｎ
ＡＮＤゲート４５０．４５２及び４７０にも送られ、ゲ
ート４５０及び４５２を動作可能にする。端子ＡＦｉｎ
におけるオールフル信号も高い場合は、その列内の上刃
のセルの各々にメッセージかあることを知らせており、
ＮＡＮＤゲート４７０も動作可能になる。

ゲート４７０が動作可能の時に、ＭＰ−ＩＮ端子の信号
が高いと、その高い信号は否定回路４７２を経て、ＡＮ
Ｄゲート４６０と４６４に送られ、それらのケートを動
作可能にし、近い信号がＡＮＤゲーゲート４６２と４６
６に送られ、これらのゲートを動作不可能にする。その
結果、Ｍ−ＩＮ及びＭＰ−ＩＮ端子における信号は、Ｎ
ＡＮＤゲート４５０．４５２、ＡＮＤゲート４６０．４
６４、そしてＮＯＲゲート４６６．４６８を通って、フ
リップ−フロップ４９２、４９４への入力へ送られる。

フリップ−フロップ４９２は、全ての基本クロックサイ
クルＰＨ１でセットされる。その結果、フリップ−フロ
ップ４９２を通って送信されるメッセージパケットの最
初の出力ビットは、フリップ−フロップ４９０に送られ
る先頭ビットのすぐ後に続くビットであり、メッセージ
パケットのもとの先頭ビットは破棄される。さらに、新
しい先頭ビットは、径路指定セルの出力端子Ｍ−ＯＵＴ
で利用出来るようになる前に、１回の基本クロッタサイ
クル分、遅くなる。そこで、メッセージパケットの各後
続ビットは、このフリップ−フロップを通じてクロック
され、端子Ｍ−ＯＵＴで、次のセルのＭ−ＩＮ端子に利
用出来るようにされる。

フリップーフロップ４９４も、同様にすべてのクロック
信号ＰＨＩ１でセットされるか、このフリッブ−フロッ
プの出力は、メッセージパケットの持続時間中は一定に
なっている。その結果、フリップ−フロップ４９４への
入力に送られる高い信号ＭＰ−ＩＮは、メッセージパケ
ットの新しい先頭ビントが出力端子Ｍ−ＯＵ　Ｔで利用
出来るようになるのと同時に、径路指定セルの出力端子
ＭＰ−ＯＵ　Ｔで利用出来るようになる。ＭＰ−ＯＵＴ
端子での信号は、それから、次のセルのＭＰ−ＩＮ端子
へ送られ、Ｍ−ＩＮ端子で受け取られたメンセージバケ
ットのために、そのセルに通るデータ通路を確立するた
めに用いられる。

フリップ−フロップ４９２．４９４が、回線割り当て装
置２０５の１５列の各々のセル４００に存在することか
ら、メッセージパケットか、１個又はそれ以上の回線割
り当て装置の１５列又は次元を通って行くうちに、］５
個の基本クロックサイクル分近くなる。

ＮＡＮＤゲート４７０が動作可能になった時にＭＰ−Ｉ
Ｎ端子の信号が低いと、ゲート４７０の出力は高くなり
、ＡＮＤゲート４６２，４６６を動作可能にし、否定回
路４７２からの出力を低くする。その結果、次に低いセ
ルに送られたオールフル（ＡＦ）信号は低くなり、その
セルに、列内の上に空のセルがあることを知らせ、ＡＮ
Ｄゲート４６２，４６６は動作可能になり、入力端子Ｌ
ｉｎ及びＬ、Ｐｉｎで受け取られた信号を通すようにな
る。

セルで受け取られたオールフルが低い時、ＮＡＮＤゲー
ト４７０は動作不可能になり、ＡＮＤゲート４６０及び
４６４も動作不可能になる。このようにして、Ｍ−ＩＮ
端子のいずれのメッセージバケットもＭ−ＯＵＴ端子に
径路指定されなくなる。

しかし、もしメッセージパヶットの先頭ビットが０−ビ
ットであれば、ＡＮＤゲート４５０，４５２は、セット
信号ｔ−ＣＯＬｎがフリップーフロップ４９０に送られ
た後に、動作可能になる。さらに、ＡＮＤゲート４６２
，４６６は、その列内のそのセルの上方の次のセル内で
動作可能になる。その結果、Ｍ−ＩＮ及びＭＰ−ＩＮ端
子は、ＵＯＵＴ及びＵＰＯＵＴ端子を経て、その列内の
次に高いセルの１７．。及びＬＰｉｎ端子へ送られ、Ａ
ＮＤケ−ト４６２．４６６及びＮＯＲゲート４７６．４
７８を通って、その次の高いセル内のフリップ−フロッ
プ４９２．４９６にへ送られる。

これらのフリップ−フロップは、径路指定セルのその列
内の他のフリップ−フロップ全てと同じょうに、そして
、同期して動作し、メッセージバケットへ及びメッセー
ジのある信号を、そのセルの出力端子Ｍ−ｏｕＴ及びＭ
Ｐ−○ＵＴ端子に与える。

セルの最下行内の各セルのＯＲゲート４８０は出力バス
４］Ｏｆに、Ｍ−ＩＮ端子を通ってセルの最下行のセル
に入るか、さもなけれは、列内のそれより上にあるセル
が全て満たされているので、Ｍ−ＯＵＴ端子を通ってそ
のセルから出て行く。このことは、メッセージパケット
のアドレスに関係なく、セルのその列に関連のある次元
上に、入ってくるメンセージパケットのために径路指定
回路内に場所があることを確かめるために行なわれる。

オールフル信号は、列内の上方セルの全てが満たされて
いる時に高くなり、そのような状況のもとで、出力ハス
が利用出来るようになる。従って、メノセージパケット
の最初のアドレスビットの状態に関係なく、ＯＲゲート
４８０の出力は高くなり、フリップ−プロップ４９０へ
の入力は、メッセージパケットの先頭ビッｌ−が１−ビ
ントの時と同じになる。このビットが、フリップ−フロ
ップ４９０にセットされた時、論理回路５０２の出力は
、バス５００への低い信号となり、それがバス駆動を使
用可能にし、Ｍ−ＩＮからのメッセージパケットを、そ
のメッセージパケットのアドレスに関りなくバス４２０
に送る。

各列又は次元のＸＯＲゲート４１５は、ヒット位置１６
から３０においてメッセーシバケットの相対アドレスを
更新する。このグートへの１個の入力は出力バス４１０
上を回線３９向けに送り出されるメッセージバケットで
ある。他の入力は、信号ｔ−ＩＮＶ−ｏｕｔｎであり、
ここでｎは次元の数であり、メッセージパケットの第２
のアドレス内のその次元のためのアドレスビットと同時
に、各次元のＸＯＲゲートに送られる。その結果、相対
アドレスビットは、メッセージパケットが、その次元上
に径路指定されたことを示して、相補されろ。メッセー
ジパケットが、出力バス４１０上に押し出されない時は
、メッセージバケット内の第２のアシレス内の関連のあ
るビットはＯ−ビットになり、このビットが１−ビット
に相補され、メッセージパケットが、その次元の希望す
るアドレスから径路指定されて離れたことを知らせる。

後に、この次元内の希望するアドレスにメッセージパケ
ットを径路指定してもどすことが必要になる。

論理回路５０２の詳細は第１３図に示される。ある列内
のセルの論理回路５０２を通しての伝播遅延を最小限に
するために、グラント信号が、列内の全てのセル内で反
転される。その結果、奇数行内の論理回路５０２の内部
回路は、列内の偶数行のものとは異なる。第１３図にお
いて、」二部行は、ゼロ行と考えられ偶数である。偶数
行内の論理回路は５０２″で、奇数行は５０２′で識別
される。各偶数論理回路５０２“は第１及び第２のＮＡ
ＮＤゲートグー２０．５２５を含む。各奇数論理回路５
２２は、ＮＡＮＤゲーート、ＮＯＲケ−ト５３５及び否
定回路５４０を含む。

ＮＡＮＤゲート２０及び５３０はバスアクセスのクラン
トを制御する。これらのゲートの両方の入力が高いと、
ゲートは、出力ハス４１０へのアクセスをグラントする
低い出力信号を出す。もしハスアクセスが、偶数番のセ
ル５０２″によってグラントされると、ＮＡＮＤゲート
５の出力は高くなる。

バスアクセスが奇数番のセル５ｏ２′によってグランド
されると、ＮＯＲゲートへの出力は低くなる。

さらに、もし高い信号が、列内で上方にある偶数番のセ
ルから奇数番のセルに受け取られると、ＮＡＮＤゲート
５３０の出力は高くなり、ＮＯＲゲート５３５の出力は
低くなる。また、低い信号が、列内で上方にある奇数番
のセルがら偶数番のセルに受け取られると、ＮＡＮＤゲ
ート５２０及び５２５の出力は高くなる。その結果、１
個のセルが出力バス４２０にアクセスをグラントする時
はい−）でも列内でその下方にあるセルはいずれｂ出方
ハスにアクスすることが出来なくなる。逆に、バスアク
セスがグランドされないと、各セルは、そのすく下方の
セルに、もしアクセスが要求されているならば、そのセ
ルがバスアクスをクランド出来るようにする信号を送る
。

違う列内のセル４００が、メッセージバヶノトのアドレ
スビットを処理するようにタイミング信号ｔ−ＣＯＬｎ
によって調時される。径路指定サイクルの初めに、径路
指定されるべき全てのメッセージバケットは、異なるＩ
Ｃ３５内の回線割り当て装置２０５のセル４００への入
力Ｍ−ＩＮに出される。１５個のアドレスビットの各々
は、それから一度に１個ずつ、２回の基本クロックサイ
クルの１５アドレス時間に分析される。第１４図に示す
ように、タイミング信号ｔ、−ＣＯＬ□は、基本クロッ
クサイクルＯの間に、全ての回線割り当て装置の最初の
列のフリップ−フロップ４９０に送られる。その結果、
各メッセージパケットの第１ビットは、フリップ−フロ
ップ４９０によって記録され、１−ビットのための論理
回路５０２によってテストされる。各回線割り当て装置
の最初の列内の論理回路５０２は、各回線割り当て装置
における頂部に最も近い行内に位置する先頭１−ビット
を持つメッセージパケットへの第１次元のバス４１０へ
のアクセスをグランドする。その結果、先頭１−ビット
を持つメッセージパケットの少なくともいくつかは、第
１次元の出力バス上へ径路指定され、出力回線：３９ト
を、最も近い隣接ＩＣ内の回線割り当て装置の最初の列
内の最下部の径路指定セル４００へ送り出される。

全ての回線割り当て装置の第１次元のセルのＭ−ＩＮ端
子にある他のメッセージパケットは、最初の列のセル内
で上方へ詰められフリップ−フロップ４９２を通ってセ
ルの最初の列のＭ−ＯＵＴ端子にクロックされる。同時
に、最も近い隣接ＩＣへ径路指定されたメッセージバケ
ットは、それらのＩＣの回線割り当て装置の最初の列内
の最下部のセルによって受け取られ、それらのセルのフ
リップ−フロップ４９２を通ってＭ−ＯＵＴ端子にクロ
ックされる。上記のように、フリップ−フロップ４９２
は、１回のクロックサイクル分、メッセージバケットを
送らせ、フリップ−フロップ４９０へ出された先頭ビッ
トは破棄される。

タイミング信号ｔ−ＣＯＬ２が、クロックサイクル２の
間に、回線割り当て装置内のセルの２番目の列のフリッ
プ−フロップに送らＡしると、これらのフリップ−フロ
ップが、各メッセージパケットの新しい先頭ビットを記
録する。再び、各回線割り当て装置の２番目の列内の論
理回路５０２が、各回線割り当て装置の２番目の列の最
上行内に先頭１−ビットを持つメッセージパケットへ、
第２次元のバス４１０へのアクセスをグランドする。そ
して、他のメッセージパケットは、セルの２番目の列内
で上へ向って詰められ、１回のクロックサイクル分の遅
れの後で各セルのＭ−ＯＵＴ端子へ送られる。再び、最
も近い隣接ＩＣへ第２次元のバス４１０を径路指定され
ているメッセージバケットは、そのセルの回線割り当て
装置の２番目の列の最下部のセルで受け取られ、それら
セルのフリップ−フロップ４９２を通ってＭ−ＯＵＴ端
子にクロックされる。メッセージパケットの先頭ビット
も破棄される。

同じような方式で、各メッセージバケットは、回線割り
当て装置の残りの１３次元を通って進み、各列内で先頭
ビットはテストされ破棄され、また、メッセージパケッ
トは１回のクロックサイクル分、遅延される。この処理
が進行している間にメッセージパケットは、１個のＩＣ
の回線割り当て装置から他のｉＣの装置へ、そのアドレ
スビットによって特定されているが希望する出力回線：
３９が利用出来ることが条件の径路指定に従って、進ん
で行く。その結果、クロックサイクルｚ９の後、各メッ
セージパケットの最初の１５ビットは破棄されているが
、各メッセージバケットの書式ビットは、回線割り当て
装置の１５番目の列内のセルの１個中のフリップ−フロ
ップ４９２の出力に達している。もし、何の径路指定障
害も起きなければ、この回線割り当て装置は、行き先に
置かれ、メッセージパケットはその行き先プロセッサ／
メモリにＪｊえられる。

もし径路指定障害が起きるようならば、メッセージパケ
ットは中間地点にいて、その旅を終えるまでにさらに少
なくとも１回径路指定ザイクルを持たなければならない
。クロックサイクル２１）の完了時には、メッセージバ
ケットの残りは、古°式ビノトの後に連なり、メッセー
ジへ′ケットの最初の２９ビットは、１個又はそれ以上
のＩＣの同線割り当て装置内に、最後の２７ビットは、
メッセージバケットが始まったＩＣのＣＩＵ１８０のシ
フトレジスタ１８４内にまだ置かれている。

例えば、メッセージパケットがＩＣ００Ｏ００００００
０００１１１から始まり、ＩＣ１１０００００００００
００１０ヘアドレスされるとすると、メッセージパケッ
トによって特定された相対アドレスは、１１０００００
０００００１０１になる。もし、径路指定障害がなけれ
ば、このメッセージパケットは、ＩＣ００００００００
００００１１１内のプロセッサ／メモリの１個によって
作成され、処理及び記憶手段４２０へ送られる。径路指
定サイクルのタロックサイクルＯから始まり、このメッ
セージパケットのビットは、このＩＣの回線割り当て装
置の最初の列内のセル４００の１つのＭ−ＩＮ端子に一
度に１個ずつ出される。アドレスタイム１中のタロック
サイクルＯの間に、タイミング信号ｔ−ＣＯＬ１が、各
回線割り当て装置の最初の列のフリップ−フロップ４９
０に送られる。ＩＣ００００００００００００１１１で
は、これがフリップ−フロップ４９０内のアドレスの先
頭ビットを記録する。このビットは１−ビットであり、
径路指定障害もないと仮定しているので、論理回路５０
２がメッセージバケットを、第１次元のバス４１０へ径
路指定する。従って、メッセージパケットは第１次元の
アドレス回線３９から１ζへ径路指定され、Ｉ　Ｃ１０
００００００００００１１１へ行き、そこで、セルのｍ
初の列内の最下部のセルのフリップ−フロップに送られ
る。そこで、メッセージバケットは、１回のクロックサ
イクル分遅延される。２回目のアドレス時間のクロック
サイクル２の間に、メッセージパケットの新しい先頭ビ
ットがテストされ、再び１−ビットであることがわかる
。従って、メッセージバケットは、今回は、アドレス１
１００００００００００１１１を持つＩＣへ、第２次元
の出力回線３９を下へ径路指定される。次の１０回のア
ドレス時間のクロックサイクル４，６・・・２２の間に
、ＩＣアドレスのその時の先頭ビットが、ＩＣ１１００
００００００００１１１の回線割り当て装置の３−１２
の各列内の論理回路５０２によってテストされる。いず
れの場合も、論理回路が０−ビットを識別し、メッセー
ジバケットを回線割り当て装置の中を上へ向って詰め、
先頭ビットを破棄し、１回のクロックサイクル分の遅れ
の後に次の列上メッセージパケットを径路指定する。

１３番目のアドレス時間内のクロックサイクル２４の間
に、論理回路５０２がその時のＩＣＣ１０レスの先頭ビ
ットをテストし、１−ビットを識別する。

径路指定に何の障害もないと仮定して、メッセージパケ
ットをＩＣ１１０００００００００００１１へ径路指定
し、そこで、回線割り当て装置の１３番目の列内の最下
部のセルによって受け取られ、１回のクロックサイクル
分遅延される。

１４番目のアドレス時間のクロックサイクル２６の間に
、タイミング信号ｔ＝ｃＯＬ１４か、各回線割り当て装
置の１４番目の列のフリップ−フロップ４９０に送られ
る。Ｉ　Ｃｌｌ０００００００００００１１においてＯ
−ビットは、１４番目の列内で最下部のセルのフリップ
−フロップ４９０内に記録される。その結果、メッセー
ジパケットはそのＩＣ内に留められ、１回分のタロック
サイクルの遅延の後にセルの１５番目の列に送られる。

１５番目のアドレス時間のクロックサイクル２８の間に
、タイミング信号ｔ＝ＣＯＬ１５が、各回線割り当て装
置の１５番目の列のフリップ−フロップ４９０に送られ
る。セルアドレス１１０００００００００００１１でこ
れらのフリップ−フロップの一つが、メッセージバケッ
トのアドレス内の残りの１−ビットを記録する。径路指
定に何の障害もないと仮定すると、論理回路５０２はメ
ッセージパケットのバスアクセスをグラントし、メッセ
ージパケットをアドレス１１０００００００００００１
０の回線割り当て装置内の最下部のセルのフリップ−フ
ロップへ径路指定する。タロックサイクル３０の初めし
こ、メッセージパケットの書式ビットが、アドレス１．
１０００００００００００１０の径路指定回路の記憶及
び処理手段に出される・ メッセージパケットの径路指定の間に、信号ｔ−ＩＮＶ
ｎが、回線割り当て装置の異なる列または次元のＸＯＲ
ゲート４１５へ、メッセージバケットの複製アドレス内
のその込元のためのアドレスと同時に送られる。これら
の信号は、その時にメッセージバケットが径路指定され
ている複製１Ｃアドレスのその次元のためのアドレスビ
ットを相補する。こわらの信号の数個を第１４図に示す
。上記のメッセージパケット径路指定の例として、クロ
ックサイクル１６．１８．４０及び４４での信号が、メ
ッセージパケットの複製相対アドレスの４個の１−ビッ
トを反転する。その結果、メッセージパケットか、記憶
及び処理手段に出される時、複製アドレスの全てのビッ
トへかＯ−ビットである。

記憶及び処理手段４２０ 記憶及び処理手段４２０は、メッセージパケットをチッ
プ上のプロセッサ／メモリへ径路指定し、プロセッサ／
メモリからメッセージパケットを送り出し、特殊な出力
回線３９か先に配置されてしするために、受は取ってす
ぐにセルから送り出せな６＞メッセージパケットを記憶
する。第１１図に示すように、経路指定回路の回線割り
当て装置２０５内のセル４００の各行に、ブロック４２
０で識別される個別の処理及び記憶装置がある。各ブロ
ックへの入力端子は、回線割り当て装置の１５番目の列
内の対応するセルの出力端子Ｍ−ＯＵＴに接続されてい
るＤ−ＩＮ、用意されたメッセージバケットを、ＣＩＵ
１８０からの回線１９６上の径路指定回路へ供給するＤ
−ＥＸＴｉｎそれに、ＣＩＵ１８０からの回線１９４上
の径路指定回路へ、送られてきた信号を供給するＤＰ−
ＥＸＴｉｎとである。ＤＰ−ＥＸＴｉｎへ送られてきた
信号は、最上部で利用可能な処理及び記憶手段４２０を
位置づけ、メッセージパケットを、ＣＩＵ１８０からそ
の手段４２０へ提供するために用いられる。各処理及び
記憶手段へのもう１つの人力は、最上部の処理及び記憶
装置４２０内に位置する特殊なセルにアドレス指定され
たメッセージバケットを抽出するために用いらＡしろグ
ラント信号である。各処理及び記憶手段／１２０からの
出力端ｆは、Ｄ−ＯＵＴ及びＤＰ−ＯＵＴであり、それ
らは、回線割り当て装置及び、ＣＩＵ１８０へ、回線１
９８をメッセージパケットを供給する局域内ハス端子内
の同じ行のセル４００のＭ−ＩＮ及びＭＰ−ＩＮ端子に
接続されている。さらに、各処理及び記憶手段４２０は
、すぐ下の行の処理及び記憶手段の対応する端子ＤＰ−
ＥＸＴｉｎ及びＧｉｎに接続されている出力端子ＤＰ−
ＥＸＴｏｕｔ及びＧｏｕｔを持つ。最下部の処理及び記
憶手段４２０の端子ＤＰ−ＥＸＴｏｕｔ及びＧ　ｏｕｔ
における信号は、それぞれ、回線１９９及び１９７上を
、ＣＩＵ１８０へ信号を提供する。特に、メッセージパ
ケットが回線１９８越しにＣＩＵ１８０へ提供されると
、回線１９８にアクセスを提供するグランド信号が、回
線１９７上に、そうしたアクセスを提供する時しこ低く
なるような信号を出す。そして、もしＣＩ　Ｕ１８０か
らのメッセージパケットが処理及び記憶手段４２０に受
け入れられると、端子ＤＰ−ＥＸＴｏｕｔ及び回線１９
９上の信号は低くなる。

各処理及び記憶手段４１０は、メッセージ検出器２］０
、バッファ及びアドレス復元器２１５及びメッセージ注
入器２２０から成り、それらの詳細は第１５図に示す。

第４図のメッセージ検出器トを処理するこの回路と共に
使用される信号のタイミング図表が第１６１Ａに示され
る。各メッセージ検出器は、３個のラッチ６１０．６１
２，６１６及び否定回路６１８．３個のＮＡＮＤゲート
グー２０．６２２．６２４、」個のＡＮＤゲーグー６３
０、論理回路６４０、そして、バス駆動６５０を含む。

ランチ６１０は、メッセージバケットのアンレスの２枚
のコビーの間を送イ１１さＪしる。！）式ビッｉ〜をチ
ェックする。このビットは、とのメッセージからも区別
のつがないメッセージのイｆｌ＋４ｒケ１１らせる。ラ
ッチは、基本りロソクザイクル；３（）の間に、信−’
５ｔ−ＭＳＧＰがセット端子で受け取られた時だけセッ
トされる。もし、書１式ビットがこのクロックサイクル
で識別されると、高い信号が出力端子Ｑに、低い信号が
ラッチ旧０の端子Ｑにセットさ九る。ＮＡＮＤゲート６
２０及びラッチ６１２は、もし全てのビットが０−ビッ
トであるかを決めるメッセージ注入器トの複製アドレス
をチェックする。

ラッチ６１２は、クロックサイクルＯの間にセットされ
、Ｑ端子での出力は、低い信号がＮＡＮＤゲート６２０
に受け取られなければ、また、受け取られるまでは、低
いままでいる。ゲート６２０は、基本タロックサイクル
３１−４５の間にメッセージパケットの第２アドレスの
受り取りの間たり、信号ｔ−ＡＤＤＲ２によって動作可
能になる。もし、全てのアドレスビットがＯ−ビットで
あると、メッセージパケットはアレイ内の正しいセルに
達し、ＣＩＵ１８０に径路指定されるだろう。そして、
ＮＡＮＤゲート６２０の出力は高いままである。ラッチ
６１２は、従って、ラッチ６１２の出力端子Ｑて低い信
号を出す。都合の良いことに、過渡状態からの干渉を最
小限にするため信号ｔ−ＡＤＤＲ２は、クロック信号Ｐ
ＨＩ１でＡＮＤされ、ＮＡＮＤゲ−ト６２０が各クロッ
クサイクルのＰＨＩ１札の間だけ動作可能になる。

ラッチ６１０及び６１２のＱ端子からの低い信号か、Ａ
ＮＤゲート６３０を動作可能にする。クロックサイクル
４４の間と、メッセージ注入器トの非アドレス部分かＤ
−ＩＮ端子で利用出来るタロックサイクル４５−８７の
全体を通して、信号ｔ−ＤＡＴＡが低くなり、それによ
ってＡＮＤゲーｈ６３０の出力で高い信号を作る。この
高い信号はＣＩＵ１８０への回線１９８へのアクセスの
要求となる。否定回路６１８によって作り出される高い
信号と低い信号−が論理回路６４０及びバス駆動６５０
へ送られ、バスアクセスをシークする最上行へバスアク
セスをグラントシ、他の全ての行のへのアクセスを否定
する。、論理回路６４０及びバス駆動６５０は、実例と
しては、第１２図及び第１３図の論理回路５０２及びバ
ス駆動５００のような装置と同じ型であり、同じ方式で
作動する。そして、ＡＮＤゲート６３０及び否定回路６
１８からの信号は、それぞれＱ及びＱ端子からの信号と
同し方式で機能する。その結果、径路指定回路２０ｏの
最下行内の処理及び記憶手段がらの回線１９アドのＧｏ
ｕｔ信号は、バス１９８へアクセスがグラントされると
すぐ低くなる。

ラッチ６１０のＱ端子がらの出力及び論理回路６４０か
らのバスアクセス出方とは、ＮＡＮＤゲート６２４へ送
られる。回路６４０のバスアクセス出方は、バスアクセ
スが、入力端子Ｄ−ＩＮでメッセージ注入器トにグラン
トされた時だけ、低くなる。そのような時、ＮＡＮＤゲ
ート６２４は高くなる。この出力はラッチ６１６の久方
へ送られ、信号ｔ−ＬＡＳＴが、メッセージサイクルの
最後のクロックサイクル８７の間にラッチへ送られる時
に、この高い信号は、ラッチ内に記憶される。ＮＡＮＤ
ゲート６２４の出力も、径路指定回路のこの行の中を循
環しているメッセージがないと高くなる。このような状
況のもとで、ラッチ６１０は、タロックサイクル３０の
間にセットされ、ラッチ６１０の。端子での信号は低く
なり、ＮＡＮＤゲートグー２４の出方を高くする。ラッ
チ６１６の出力は、バッファ及びアドレス復元器２１５
とメッセージ注入器２２０の双方に送られる。

ラッチ６１６のＱ出力も、Ｄ−ＩＮ端子からの信号とと
もに、ＮＡＮＤゲート６２２に送られる。その結果、Ｎ
ＡＮＤゲートは、メッセージ書式ビットが検出された時
に反転され、そのゲートはＤ−ＩＮ端子で受け取られた
メッセージバケットへを、それがバッファー復元器に送
られている時に反転する。

メッセージ注入器２２０は、セレクタ６７０、否定回路
６８０、ＯＲゲート６８２、ＡＮＤゲート６８４及びＮ
ＡＮＤゲート８６を含む。回線１９４上の信号は、処理
及び記憶手段４１０の上の行内の端子ＤＰ−ＥＸＴｉｎ
へ送られ、そこで、ＮＡＮＤゲート６８６とＯＲゲート
６８２及びＡＮＤゲート６８４に接続される。ＮＡＮＤ
ゲート６８６の出力は、セレクタ６７０の選択端子に送
られる。この信号が高いと、セレクタの端子Ａにおける
信号が、Ｄ−ＯＵＴ端子へ供給される。信号が、低いと
、端子Ｂでの信号は、出力端子Ｄ−ＯＵＴへ供給される
。

第８図と関連してＣＩＵ１８０の説明で述べたように、
フリップ−フロップ３１４が、基本クロックサイクル８
７の間に信号ｔ−ＬＡＳＴによってセットされる。その
結果、端子ＤＰ−ＥＸＴｉｎへの回線１９４上の信号は
、メッセージ注入器２２０へ送達されることになってい
るメッセージバケットがＣＩＴＵ１８０にある時はいつ
もメッセージサイクルが始まる前から高くなる。ラッチ
６１６も、基本クロックサイクル８７の間に信号ｔ−Ｌ
ＡＳＴによってセラトされる。その結果、ＮＡＮＤゲー
ト６２４の出力が、メッセージパケットがＣＩＵ１８０
へのバス１９８へ送達されている時と同じ位高いと、ラ
ンチ６１６の出力も、メッセージサイクルの開始以前か
ら高くなる。ラッチ６１６及び端子ＤＰ−ＥＸＴｉｎか
らの高い信号は、ＮＡＮＤゲート６８６の出力を低くす
る。その結果、セレクタ６７０の端子Ｂは、メッセージ
注入器２２０の端子Ｄ−ＯＵＴへ接続され、ＣＩＵ１８
０からの回線１９６上のメッセージパケットはメッセー
ジ注入器２２０で受け入れられ、Ｄ−ＯＵＴ端子へ供給
される。

同時に、ラッチ６１６からの高い信号が否定回路６８０
へおくられ、ＡＮＤゲート６８４を使用不可能にしＤ　
ｐ＝Ｅｘ　ＴＯｕｔ端子に低い信号を提供する。この信
号は、他の全ての低い行中のＡＮＤゲート６８４を動作
不可能にし、これらの行の各々のＤＰ−ＥｘＴｏ、Ｉｔ
において低い信号を提供する。これらの低い信号も、全
ての低い行中のラッチ６７０の選択端子に高い信号を提
供する。その結果、回線１９６上のメッセージは、注入
器２２０の一行に送達されるだけになる。さらにまた、
径路指定回路の最下行のためのメッセージ注入器の出力
端子ＤＩ）−ＥＸＴｏ、Ｌからの低い信号は、ＣＩＵ１
８０への回線１９９上に送られ、外へ出て行くメッセー
ジパケットが、回線割り当て装置２０５への応用のため
にメッセージ注入器２２０によって受け入れられたこと
を知らせる。回線１９６上に信−じを受ｔづろメッセー
ジ注入器の行のＯＲゲ−ト６８２へ端子ＤＰ−ＥＸＴｉ
ｎから送られる高い信号も端子Ｐ−ＯＵＴにおいて高い
信号を提供し、端子Ｄ−ＯＵＴにメッセージが存在する
ことを知らせる。

これとは別に、この行に循環するメッセージはないこと
もあるし、または、メッセージはこのセルにアドレス指
定されていないこともある。もし。

循環しているメッセージがないと、ラッチ６１０のＱ端
子からＮＡＮＤゲート６２４への入力は低くなり、ラッ
チ６１６の出力は、次のメッセージサイクルの間高くな
る。これらの状況のもとで、回線１９６からのメッセー
ジパケットは、メッセージ注入器トをバス１９８に書き
込むことによって行が空になった場合と同じようにメッ
セージ注入器によって受け入れられる。

もし、メッセージが行に存在していてもそのセルにアド
レス指定されていなけｈば、ＮＡＮＤゲーＩグーの両方
の入力は高くなり、その結果、ＮＡＮＤゲートの出力は
゛低くなり、ラッチ６１６の出力は、メッセージサイク
ルの開始より前から低くなる。結果として、ＮＡＮＤゲ
ート６８６の出力及びセレクタ６７０の選択端子が高く
なりセレクタの端子Ａに送られた信号は、Ｄ−ＯＵＴ端
子へ送られる。さらに、低い信号は否定回路６８０によ
って反転され、ＤＰ−ＯＵＴ端子で高い信号を提供し、
メッセージが行中にあることを知らせる。否定回路６８
０の出力も、ゲート６８４を使用可能にする。

その結果、回線１９４上のＣＩ　Ｕ１８０から、行の１
つにメッセージを入れるよう要求があると、この信号は
、ＡＮＤゲート６８４及びＤＰ−ＥＸＴｏｕｔ端子によ
って、次に低い行へ送られる。

セレクタ６７０の端子Ａに供給されたメッセージ注入器
トは、第１及び第２相対セルアドレスを持つメッセージ
パケットである。このメッセージパケットは、Ｄ−ＩＮ
端子で受け取ったメッセージバケットを記憶し、第２の
相対セルアドレスから第１の相対セルアドレスを再構成
するバッファ復元器２１０によって供給される。

バッファ復元器２１０は、シフトレジスタ７００、ＡＮ
Ｄゲート７１０．７１２、と７１４、そして、ＮＯＲゲ
ート７２０を含む。メッセージパケットは、Ｄ−ＩＮ端
子に到着すると、シフトレジスタ７００中にシフトされ
る。このレジスタは、第２の相対セルアドレスの初めか
ら最後の誤り訂正ビットまでの、全メッセージパケット
を記憶するに充分な長さを持つ。第１４図に示すように
、レジスタ７００は、その出力端子から１６のシフト位
置にあるタップ７０２を持つ。その結果、メッセージバ
ケットがシフトレジスタを通ってシフトされると、メル
−ジバケットの最初の１６ビットが、これらのビットが
シフトレジスタの出力端に達する前に、ＡＮＤゲート７
１４の入力で利用可能になる。これらビットの最初の１
５個は、相対セルアドレスである。

第１の相対セルアドレスを再構築するために、ゲート７
１４が、これらビットがタップ７０２にある基本クロッ
クサイクル０−１４の間に信号ＳＥＬ−ＴＡＰによって
動作可能になり、ゲート７１４の出力は、ＮＯＲゲート
７２０を通って、セレクタ６７０の端子Ａに送られる。

クロックサイクル１５の間に、ＡＮＤゲート７２０が、
信号ＳＥＬ−ＭＳＧＰによって動作可能になり、書式ビ
ットを発生する。このビットは、ラッチ６１６の出力か
ら得られ、ＡＮＤゲート７１０の出力はＮＯＲゲート７
２０を通ってセレクタ６７０の端子Ａへ送られる。クロ
ックサイクル１５の間、ラッチ６１６の出力は、メッセ
ージパケソトがバス１９８に転送されているところか、
または、そのメッセージサイクルの間にＤ−ＩＮ端子で
、メッセージパケットが受け取られていない場合は高く
なる。これらの場合、ＡＮＤゲーグー７１０によって送
られる信号は高い信号で、ＮＯＲケ−ト７２０によって
反転され、バッファ及び復元器２１５の出力に、有効な
メッセージパケントがないことを知らせる。他の全ての
場合には、ラッチ６１６の出力が低くなり、この信号は
ＮＯＲゲート７２０によって反転され、バッファ及び復
元器２１５からのメッセージパケットが有効であること
を知らせる。

これら１６サイクルの後で、シフトレジスタ７００を通
ってシフトされているメッセーシバケットが、出力端子
へ達し、また、ＡＮＤゲート７１２の入力に達する。そ
の時と、基本クロックシイクル１６−７２全体で、ゲー
ト７１２は信号ＳＥＬ−ＥＮＤによって動作可能になり
、第２の相対セルアドレス及びメッセージパケットの残
りをセレクタ６７０の端子Ａへ提供する。

Ｆ．例 プロセッサ／メモリのレジスタでのメッセージパケット
の発生及び受け取りの例は次の通りである。表■は、こ
の例で取り＋ばているプロセッサ／メモリの下記のレジ
スタ及びフラグで利用出来る情報を明記している。

局地アドレス情報は、レジスメアドレスの４ビットを列
０から３、局地プロセッサ／メモリを識別するアドレス
の５ビットを列４から８に、列９がら２３のＩＣアドレ
スの１５ビントは絶対値のＩＣのアドレスを明記し、Ｉ
Ｃアドレスにパリティを提供する列ｚ４には」、−ビッ
トを持つレジスタ２内に記憶される。メッセージが送ら
れてもよくなると、メッセージデ“−夕かレジスタ４内
に記憶され、ＩＣチップ、プロセッサ／メモリ及びレジ
スタを含めたその行き先のアドレスは、レジスタ２内の
局地アドレス情報と同し順序でレジスタ１内にあり、ビ
ノＩ〜を送れという要求は、状態レジスタ３の列０内の
１−ビットとしてセラトされ、フラグを送れという要求
は、クローバルフラグレジスタ６内の１−ビットへとし
てヤットされる。この例として、メッセーシバケットは
、偶数受Ｕ取りレジスタ６（レジスタアドレスが１１１
１０ならば）か、奇数受は取りレジスタ７（レジスタア
ドレスか１１１１ならば）のどちらかで受け取られる。

これらの地点で記憶された情報について、表■が、レジ
スタ１内のアドレスによって特定されたＩＣへ、レジス
タ４内のデータを送り出ずメッセージバケットを発生し
、メッセーシパケットのデータを受け取るに必要な命令
を示す。

サイクル５１の間に、局地プロセッサ／メモリがメッセ
ージを送ろうとしていて、ティジ−チェーン内で、高い
所のプロセッサ／メモリが、送Ａしという要求を出して
いなければ、ＣｏｍＥビットかセラトされる。この時に
、このゾロセッサ／メモリから送る要求は、グローバル
フラグレジスタ６内の１−ビットとして記憶され、より
高いプロセッサ／メモリからの送れの要求のいずれもか
、状態レジスタ３の０列内の１−ビットとして記憶され
ている。このゾロセッサ／メモリか、送られるかどうか
は、状態ビットを相補し、この相補されたビノトとグロ
ーバルフラグレジスタ６の内容のＡＮＤをとることによ
って計算される。結果は、ＣｏｍＥフラグレジスタに書
き込まれる。ＣｏｍＥビットかセットされると、ＮＡＮ
Ｄゲート２９３は動作可能になり、それによって、キャ
リ出力回線２８７上の信号をＣＩＵ１８０への信号回線
１２３へ提供する。サイクル５２の間に、グローバルレ
ジスタ６内に１−ビットが、ＳＷＡＰ動作によって状態
レジスタの０列に居き込まれる。

サイクル５３の間に、ブロセットノ／メモリは。

ＣＩＵ１８０への回線１２３へ、ＩＣアドレスのための
バリティビットを提供する。上記のように、このパリテ
ィビットはレジスタ２の列２４内に記憶される。それは
、Ｏフラグから得たＯ−ビントとともに、レジスタ２の
この桁の内容の０丁くをとることによって読み出しサイ
クルの間に読み出される。

この動作の結果は、キャリ出力回線上を、フラグ１ノシ
スタ２内のデータシンクとＮＡＮＤゲート２９３へ提供
され、そこから回線１２３へ送られる。

サイクル５３の間に、もしメッセージパケソトを送り出
すのならこの１−ビットが送りだされる。

この１−ビットは、ＣｏｍＥフラグレジスタ７内にセラ
トされる。ゼロを含むレジスタ及びＣｏｍＥフラグレジ
スタの内容のＯＲをとることによって読み出されるｄこ
の動作の結果は、ＮＡＮＤゲート２９３を通って回線１
２３へ送られる。

サイクル５５から８６の間に、データは、一度に１列ず
つ、レジスタ４から読み出され、″フラグを受けとるな
″か低いと、データは、一度に１列ずつ、受は取りレジ
スタ６．７の１つに書き込まれる。メッセージパケット
の同時送りと受け取りは、レジスタ■３の出力をキャリ
出力回線２８７へ提供し、フラグからレジスタＡへ入力
を提供するＳＷＡＰ動作によって達成される。レジスタ
１３はレジスタ４として特定され、この例としてレジス
タ八がレジスタ７として特定される。ＣＩＵ１８０から
の回線１２２からの入力は、フラグ１３であるデータイ
ンフラグへ送られる。これらのサイクルのに々の読み出
し部分の間に、レジスタ４の１列の信号と、データイン
端子の信号が読み出される。これらの動作の書き込み部
分の間に、キャリ出力回線上の信号がＮＡＮＤゲート２
９３を通って、出力回粕冒２３へ提供される。同時に、
ＣＩＵ１８０からデータインフラグ１３へ送られた信ゆ
は、レジスタ７の列に吉・き込まれる。

上述のごとく、レジスタ６又は′７へのデータの古、き
込みは、受は取るな″フラグ１の状態で条件付けされる
。この状態は、回線１７Ｉ）及びセレクタ２９４を用い
てフラグ１を読み出し、ＸＯＲゲート２９９内で、受は
取るな″フラグど回線１７８北の信号とを比較すること
によって決定される。読み出しフラグ１のための信号は
ビン１２２−２５上の０００１である。

サイクル８７の間、受は取られたメッセーシバケットへ
のパリティビットは、レジスタ２内の絶対】Ｃアドレス
のパリティビッＩ−と比較される。これは、レジスタ２
の桁２４のパリティビットで、データインフラグ人力の
信号の排他的０１くを実行するためにＭＯＶＥ動作を用
いてなされる。もしパリティ誤りがないと、この動作の
結果は、クローバルフラグレジスタ６に書き込まれる低
い信号でなければならない。マイクロコンＩ−ローラ２
０か、パリティ誤りを見張るために、この回線をチェッ
クする。

サイクルＯから１４の間に、メッセージパケソトのため
の相対ＩＣア１くレスが発生され、Ｃ’　Ｉ　Ｕ１８０
に提供さ汎る。このことは、ＭＯＶＩＥ動作を用いて、
送信側のＩＣアドレスの絶対値と、行き先のＩＣアドレ
スの絶対値の排他的ＯＲを作り、それをキャリ出力回線
へ提供することによって達成される。

サイクル１５から１９の間に、ＩＣ内の特定のプロセッ
サ／メモリのアドレスが、レジスタ」から読み取られ、
ＭＯＶＥ動作によってギ−Ｖり出力回線へ提供される。

サイクル２０の間に、１つのビットが行き先レジスタが
奇数かまたは偶数であるべぎかを特定して送られ、サイ
クル２１かＩ；２；ｌの間に、追加のビットが、行き先
レジスタの）′１クレスを特定しなから送られる。この
例の中で、サイクル２１から２３の間に送られたビット
の状ＪＩＭは、勺イクル２（＋の間に発生されたビット
の状態によって、レジスタ６又はレジスタ７のみにデー
タが１１：き込まれるため、不適切である。便宜」−、
サイクル２１がら７３の間に送り出されたビットへは、
ルロレシスタ１５の出力とゼロフラグ人力１５を反転し
、それらの値のＯＲをとることによって得られた１−ビ
ットである。

サイクル２４の間に、メンセージパケットが、径路指定
回路がメッセージバケットを受け入れしたかどうかを決
めるための回線１２３に、送られているかどうかのテス
トが行なわれる。５受は取りは、Ｎ　ＯＲグート３５２
によって反転され、サイクル０−４４の間にデータイン
フラグに送られた回線１９９上の低い信号によって知ら
される。サイクル２４の間に、この信号は再び反転され
て、５ＷＡＩ’動作によって状態レジスタ３の０列に書
き込まれる。

サイクル２５から３８は自由で、これらのサイクルへの
命令は、ＭＯＶＥ動作によるＯ−ビント転送の非動作（
ＮＯＩ））を提供する。

サイクル３９の間に、プロセッサ／メモリは、メソセー
ジパケットを次に径路指定サイクルで送る許可を要求す
るかどうかを計算する。この情報は状態レジスタから得
られ、ＯＲ動作によって回線１２４上の出力を提供して
いるクローバルフラグレジスタ６に提供される。サイク
ル４０−４３の間に、送れの要求は、状態レジスタから
読み出され、キャリ出力回線を経て、チップ」二のディ
ジーチェーン内の局地プロセッサ／メモリの下にあるプ
ロセッサ／メモリのディジー人カへ送られる。同時に、
ディジーチェーン内で高い所にあるプロセッサ／メモリ
からの入力は、ディジー人力から読み出され、キャリ出
力によって、デイジーナエーンの下の方のプロセッサ／
メモリに提供される。４つのサイクルが、プロセッサ／
メモリからの送れの要求が、チェーンの下方へ伝播され
るのを確かめるためにある。サイクル４４の間に、チェ
ーン内の高い所のプロセッサ／メモリのいずれかｊ′、
の送れの要求が、キャリ出力回線へ占き込まれ、この情
報は、状態レジスタにも書き込まれる、１サイクル４５
に間に、もしメッセージがこのＩＣに送達されようとし
ているな−らば、１個の１−ビットが、データインフラ
グへの回線１２２Ｊ二に提供される。このビットは、′
受は取るな″フラグレジスタ１を、ＣｏｍＩΣＩｎでの
人力の状態の反対であるＯ−ビットでセラトすることに
にす、このレジスタの状態を計算するのに用いら４Ｌる
。このことは、ＯＲ動作によって、データイン人力を相
補し、それをフラグレジスタ１へ−）・き込むことによ
って行なわれる。

サイクル４６から５０の間に、プロセ、フサ／アドレス
が、ＣＩＵｌ、８０からの回線１２２に送達される。

各プロセッサ／メモリはこのアドレジを自分のアドレス
と、これら２つのアドレスの排他的ＯＲをとり、フラグ
レジスタ１内で見られた相違を積み重ねるためにＭＯＶ
Ｅ動作を用いて、比較する。

もし、違いが見られない場合は、フラグレジスタ１は、
局地プロセッサ／メモリがメッセージバケットの行き先
であることを知らせるＯ−ビットを保持する。

その後、径路指定サイクルは、全てのメッセージパケッ
トが送達され終るまで続く。

Ｇ、代替案 この技術に熟練する人々には明らかであるように９本発
明の精神と範囲内で、上述のシステムには数多くの変更
が可能である。本体コンピュータ１０、マイクロコンピ
ュータ３０及びプロセッサ／メモリの直線のアレイの使
用、及び、データソース４０及びデータシンク９０及び
関連するバッファによるプロセッサ／メモリへ、そして
、それらからのデータの提供はほんの一例である。例え
ば、もし本体コンピュータが充分速ければ、命令シーケ
ンス発生は、マイクロコントローラの代わりにコンピュ
ータで行なうことも出来る。もしくは、多くの応用にお
いて、マイクロコントローラ及びプロセッサ／メモリの
アレイの動作に本体コンピュータを用いる必要がない。

データソース４０、バッファ５０．６０．６５．７０．
７５．８０、とデータシンク９Ｏの他の配置も可能であ
る。プロセッサ／メモリの直線状のアレイは、比較的簡
単な組織と厳密な並行動作の迅速な実行という長所を楯
っているが、この組織は、本発明の実行には必要ではな
い。個別のプロセッサ／メモリは厳密に線型アレイ内に
、第１Ｂ図の螺旋型接続に代表されるよ−）に接続出来
るが、２次元的８角形もしくはＨ１角形又は他の形態、
３次元的アレイで接続させることも出来る。

ある応用では、チップの径路指定回路を通る接続を除い
て、違うチップ上のプロセッサ／メモ９間のどのような
接続も使わないことも出来ろ１゜プロセッサ／メモリの
数、位「１ｉ、個別の機能も変化させられる。本発明の
コンピュータシステムはプロセッサ／メモリの数が、こ
れより多くても少なくても良い。本発明の利点は、約１
０，０００個のプロセッサ／メモリを使用した時にはつ
きりしてくる。各チップ上に３２のプロセッサ／メモリ
、各ＰＣ板上に６４チップという２２０プロセッサ／メ
モリの配置は、単なる一例である。現在の技術では、こ
の配置は、妥当な費用と思えるもので実現出来る。将来
は、各チップ上にもつと多くのプロセッサ／メモリを置
けるであろう。ｎ−立方体の次元の数も、相互結合させ
るプロセッサ／メモリの数に合わせて変化させられる。

ある応用では、径路指定回路を、プロセッサ／メモリが
取り付けられているＩＣとは違うＩＣに作る方が有利に
なるだろう。ある場合には、２つ以上のタイプのプロセ
ッサ／メモリを使用するのが良いこともある。例えは、
特別な算術的機能を持つプロセッサ／メモリが、汎用プ
ロセッサ／メモリと共に有用であることもある。設計変
化も、ＩＣの回路におし１て行なわれるだろう。例えば
、ビン開数は、命令ビンの時分割多重方式化によって、
変わってくるだろう。

立方体の各次元でＩＣチップに２つの可能な配置のある
ブールｎ−立方体の径路指定回路を説明してきたが、本
発明を、各チップが、ｎ−立方体の１次元以上の３つ以
上の位置に配置されてもよい。このような配置では、各
チップを接続するには、いくつかの可能性がある。、径
路４Ｈ定回路２００の一般的形態を保つ配置では、各セ
ルの各次元の出力回線３９を、同じ次元内の他の１つだ
けのセルの入力回線３８へ接続する。第５図の各チップ
１００の人力及び出力回線３８．３９の接続パターンを
一般化するため、１次元内の１アドレスにチップが位置
する場合に、その出力回線は０アドレスに位置する最も
近い隣接チップに接続さＡし、そのアドレスは１単位だ
け小さく、また、ある次元でチップが０アドレスに位置
する場合は、その出力回線は、その次元において最高の
アドレスであるｌアドレスに置かれたチップに接続され
る。このパターンを、ある次元の３つ以上のアド１ノス
にチップが買かれる場合に応用するには、最高アドレス
にあるチップの出力回線を、次に高いアドレスその他に
あるチップの入力に接続するだけで良−い。そして、Ｏ
アドレスにあるチップの出力回線を、最高アドレスにあ
るアドレスの入力回線に接続する。例えば、チップがあ
る次元の４アドレスに置くことが出来るとすると、アド
レス３のチップの出力回線を、７１ヘレス２にあるチッ
プの入力回線に接続し、アドレス２チップの出力回線を
、アドレス１のチップの入力回線に、アドレス１のチッ
プの出力回線をアドレス０の入力回線に、そしてアドレ
スＯの出力回線をアドレス３の入力回線に接続する。

あるいは、接続を反対の方向に行なうことも出来る。

４１１対アドレス発生及び径路指定回路においても修正
が必要になるだろう。しかし、これらの修正はこれらの
機能の汎用化から明らかになる。このように、各次元に
２つだけＩＣアドレスがある場合は、相対アドレスは、
２つのアドレスの排他的ＯＲをとることによって決めら
れる。しかし、これは、他のアドレスから１つのアドレ
スを減じ。

負数を補数として表わすことの等価である。同様に、先
頭アドレスビットを調べて、メッ芋−ジパケノトが行き
先へ着いたかどうかに決める径路決定機能は、一般的に
は、先頭アドレスビットがＯ−数字かそうでないかを決
めることである３、それが、〇−数字であれば、メッセ
ージバケットは、その次元内の行き先に到達している１
、さもなければ、その次元の他のアドレスへ径；酪指定
されなければならない。ある次元に２アドレス以上ある
場合、相対アドレスの発生と、そのアドレスＬこよって
特定されたメッセージバケットの径路指定は似たものに
なる。相対アドレスは、行き先ＩＣのアドレスを開始Ｉ
Ｃのアドレスから減算し、メッセージパケットが行き先
に達するために、その次元内で横切らねばならないノー
ドの数を得ることによって決められる。負数は、その補
数に変換することによって佃単に取り扱える。回路割り
当て装置の各列のバスアクセス論理内の径路指定回路は
。

メッセージバケッＩ−の先頭アドレスビノト内にＯ−数
字があるかどうかをテストするたりである。

もし、〇−数字があると、メッセージバケットへは、そ
の次元内でアドレス指定されているアドレスに達してお
り、その次元内の異なるアドレスへ径路指定する必要が
ない。先頭ビットが〇−数字でない場合は、メッセージ
パケットは、正しいアドレスになく、その次元内でのア
ドレスが１単位小さい最も近い隣接ノードに径路指定す
ることが出来る。複製アドレスが径路指定された場合、
その次元の相対アドレス数字は、１だけ減することによ
り更新出来る。

１次元内にＩＣチップに２アドレス以−ヒある回路のこ
の例を考えると、このようなスキーマは上記のブールロ
ー立方体内のＩＣチップの同数を相互接続させるために
用いられる入力及び出力回線３８．３９の数を減少させ
、従って、径路指定障害の可能性を増すことがわかる。

しかし、チップ間の相互通信が低い応用においては、こ
のような代替案は実用的であると分かるであろう。

上述の各構成要素についても、単なる一例である。ＲＡ
Ｍ２５０及びフラグコントローラ２９０の特定の大きさ
は、実例にすぎない。ある応用においては、もっと大型
のＲＡＭ及びコントローラの方が良いかも知れない。も
ちろん、もっと小型のものを用いても良い。ビットル直
列ＡＬＵ２８０は、並列ＡＬＵと入れかえることも出来
るし、ＡＬＵへの人力の数及び／又はそれからの人力の
敬か違っていても良い。プロセッサ／メモリの間車され
た実施例は、全てのアドレスデコーデインクをＰＬＡ１
５０内で行なうが、ある場合には、デコーディングのい
くらかを、各プロセッサ／メモリで行なう方が有利であ
ろう。各ブロセッサ／メモリのＡＬＵ−ＲＡＭ及びフラ
グコントローラは、上記の実施例では、他のプロセッサ
／メモリのそれらとは独立して作動しているが、そうで
はない組合わせも可能である。例えば、各ＡＬＵは、Ｉ
Ｃアドレスが、ＩＣチップ上二の全てのプロセッサ／メ
モリに記憶される単一のレジスタのようにト）又はそれ
以」二の同じレジスタへのアクセスを持つことも出来る
。ＡＮＤ、ＯＲ，ＡＡＤ、ＳＷＡＰ及びＭＯＶＥの５個
の基本動作の命令セットの使用が好ましいが、追加の動
作を用いてこの発明を実施しても良い。加えて、表■の
：Ｉ２の命令から異なる数の命令を用いて、発明を実施
しても良い。

径路指定回路２００においても、数多くの変更が出来る
だろう。回路割り当て装置２０５の列の数はｒ）−立方
体内の次元の数によって決まる。行数は、径路指定回路
の記憶要求量によって異なる。このような要求量は、ど
のくらいのメッセージパケット径路指定がシステムで用
いられているかによって、１つ１つのシステムによって
変る。ある応用では、メッセージ注入器２２０へ複数の
出力回線１９４゜１９６を、また／もしくは、メッセー
ジ検出器２１０及び注入器２２０から複数の出力回線１
９７．１９８，１９９を備えた方が良いこともある。メ
ッセージパケットが径路指定されねばならない次元の数
によって、バッファ及びアドレス復元器２１５内のメッ
セージ注入器トを分類することが望ましいこともある。

命令の処理において数多くの変更も行なえる。

前のメッセージ注入器Ｉ−が完全に送達されないうちに
、続きのメンセーシパケソトが発生されるように、径路
指定サイクルを重複させると有利であることもある。追
加の誤り検知及び訂正は、追加のパリティビットを使う
ことによ−、てｔｉなえる。。

条件的動作は１個以上のフラグにノ、ヒへ１てぃても良
い。間接アドレス指定が望ましいこともある。

性能を強化するために上記のシステ１１に、数多くの機
構を組み合わせることも出来る１２例えば、各チップに
、チップ上の各プロセッサ／メモリの個別のダイナミッ
クＲＡＭの内容の状態を保存するために、外部メモリを
追加して１ノ良い。各プロセッサ／メモリのアドレスは
、各アドレスを動作の開始時に装填する必要をなくすノ
ーめに、ハード配線で供給することも出来る。入力いデ
ータソース４０を通さず、イメージセンサを通して直接
各プロセッサ／メモ１ノーに行なうことも出来る。もし
くは、コンピュータ１０に、各プロセッサ／メモリの個
別のレジスタへの直接アクセスを持たせても良い。最後
に、シリコン作られ従来からある電線で接続された超Ｌ
ＳＩ回路の現在の技術の点から、発明を説明してきたが
、本発明の概念は、他の技術にも転用出来るということ
も認識されるべきである。シリコンＩＣ３５を、例えば
ガリウム砒素のようなもので作られていてしかも同し機
能を持つ他の回路で代替しても良く、従来からの電線を
、例えば、任意の繊維で代替しても良い。

【図面の簡単な説明】

第１Ａ図及び第１Ｂ図は、本発明による並列処理集積回
路（ＩＣ）のアレイを用いるコンピュータシステムの概
略説明図、第２図及び第３図は、並列処理ＩＣ間の相互
接続パターンのいくらかを理解する上に有用な概略説明
図、第４図は、第１図のアレイ内で１つのＩＣから他の
ＩＣへ送られるメッセージの書式と、第１図に描かれた
コンピュータシステムの動作を理解するのに有用なりロ
ック信号波形のいくつかを示す波形図、第５図は、並列
処理ＩＣを持ついくつかの超り、ＳＩパッケージを取り
付ける印刷配線板のＷ、略説明図、第６Ａ図及び第６Ｂ
図は、第１図のアレイの１個の並列処理ＩＣの実施例の
ブロック図、第７Ａ図及び第７Ｂ図は、第６Ａ図のブロ
ック図中に描かれたプロセッサ／メモリの１つのブロッ
ク図、第８図は、第６Ｂ図のブロック図中に描かれたイ
ンタフエース装置の論理図、第９図及び第０１図は、第
８図の回路の動作を理解するのに有用ないくつかの波形
１〆１、第１１図は、第６Ｂ図のブロック図に描かれた
径路指定回路のブロック図、第１２図は、第１１図の径
路指定回路中の回線割り当て機構の例示的実施例の論理
図、第１３図は、第１２図の回線割り当て機構の一部分
の論理図、第１４図は、第１１図〜第１３図の回路動作
を理解する上に有用ないくつかの波形図、第１５図は、
第１１図に描か汎だ径路指定回路の追加部分の例示的実
施例の論理図、第１６図は、第１４図に描かれた回路の
動作を理解する上に有用ないくつかの波形図、第１７図
は、第６Ａ図及び第６１３図に描かれた回路の超ＬＳ１
回路の配置図である。 符号の説明 １０・コンピュータ　２０・マイタロゾロセッサ３０・
・アレイ　４０・データソース ５０．６０．６５．７０．７５．８０・・バッファ９０
・データシンク 代理人弁理士　中　刊　純之助 手続補正書彷幻 昭和５９年１１月２９日 １、事件の表示　昭和５９年特許願第１０９７７６号２
、発明の名称　並列プロセッサ ３、補正をする者 事件との関係　特許出願人

Claims (11)

【特許請求の範囲】
1. （１）プロセッサ／メモリのアレイであって、プロセッ
   サ／メモリの各々が、データがそこに書き込まれ、また
   そこから読み出されるメモリ手段と、少なくとも一部は
   該メモリ手段から読み出されるデータおよび命令情報に
   依存して出力を発生するためのプロセッサとを含むプロ
   セッサ／メモリアレイと、 ｎを２より大きい数としたときに、データが前記アレイ
   内のいずれかのプロセッサ／メモリから、他のいずれか
   のプロセッサ／メモリへとそｈを介して径路指定される
   少なくとも２ｎノードを持つｎ−次元パターンに、前記
   アレイ内のプロセッサ／メモリを相互接続するための手
   段と、を含む並列コンピュータ処理のためのプロセッサ
   アレイであって、前記相互接続手段は、アートレス指定
   されたメッセージパケットに入れられたアドレス情報に
   従って前記ｎ−次元パターンにおける１つのプロセッサ
   ／メモリから他のプロセッサ／メモリへ径路指定される
   ようにしたアドレス指定されたメッセージパケットを発
   生する手段と、 前記ｎ−次元パターンの各ノードにおいて、前記メッセ
   ージパケット内のアドレス情報に従って該メッセージパ
   ケットへを径路指定するための手段を含むよう構成して
   成るプロセッサアレイ。
2. （２）特許請求の範囲第１項の記載において、ｍを少な
   くとも１としたときに、ｍ−次元パターンに、前記アレ
   イのプロセッサ／メモリを相互接続するための手段であ
   って、そのパターン内で個々のプロセッサ／メモリは、
   そのｍ−次元パターン内で隣接する少なくともいくつか
   のプロセッサ／メモリと接続されているようにする手段
   をさらに含み、該手段は、個々のプロセッサ／メモリと
   、それらが接続される隣接するプロセッサ／メモリの間
   の直接接続を含む、ことを特徴とするプロセッサアレイ
   。
3. （３）特許請求の範囲第１項の記載において、前記アド
   レス情報は、前記ｎ−次元パターン内での開始プロセッ
   サ／メモリ及び行き先プロセッサ／メモリの相対的変位
   であり、前記相互接続手段は更に、それを介してメッセ
   ージパケットが径路指定される各ノードにおいて相対変
   位を更新させる手段を含むことを特徴とするプロセッサ
   アレイ。
4. （４）特許請求の範囲第３項の記載において、前記相対
   変位の２つのコピーが開始プロセッサ／メモリで発生さ
   れ、１つめコピー内の変位が、それを介してメッセージ
   パケットが径路指定される各ノードで更新される一方で
   、相対変位の他方のコピー内の個々のビットはメッセー
   ジパケットの径路指定を制御するために前記径路指定手
   段によって用いられるようにしたことを特徴とするプロ
   セッサアレイ。
5. （５）特許請求の範囲第１項の記載において、前記アド
   レス情報は、次元と同じ数の桁から成る相対アドレスで
   あり、各桁は、メッセージパケットがアドレス指定され
   ているノードからのメッセージパケットの相対変位を表
   わしており、また前記径路指定手段が、 各次元に関連づけられ、ノードで受け取られたメッセー
   ジパケットのアドレスの桁を調べて、その次元内の変位
   がゼロであるかどうかを決めるための検査手段と、 各次元に関連づけられ、もし調べた桁が、メッセージパ
   ケットが行き先に到着していないことを示し、また、そ
   のノードへの接続が利用可能であれば、同じ次元内の他
   のノードへ該メッセージパケットを径路指定するための
   手段と、 メッセージパケットが、同じ次元内の他のノードへ径路
   指定されない時に、メッセージパケットを、１つの検査
   手段から他の検査手段へ送るための手段と、 行き先に到達したメッセージパケットをメッセージシン
   クへ径路指定し、行き先に径路指定されなかったメッセ
   ージパケットを一時的に記憶し、記憶されたメッセージ
   パケットをさらに径路指定するために前記検査手段へ再
   循環させるための記憶／処理手段とを含むようにしたこ
   とを特徴とするパッケージアレイ。
6. （６）特許請求の範囲第１項の記載において、面記アド
   レス情報は、次元と同数の桁からなる相対アドレスであ
   り、各桁は、メッセージパケットがアドレス指定されて
   いるノードからのメッセージパケットの相対変位を表わ
   し、各ノードにおける前記径路指定手段は、 ノードで受け取られる前記メッセージパケットのアドレ
   スの第１、第２、第３の桁をそれぞれ調べて、その次元
   での変位がゼロであるかどうかを決めるための、少なく
   とも、第１、第２、第３の検査手段と、 もし、検査した桁が、メッセージパケットが行き先に到
   達していないことを示し、そのノードへの接続が利用可
   能である場合に、該メッセージパケットを、それぞれ第
   １、第２、第３次元内の他のノードへ径路指定するため
   の少なくとも第１、第２、第３の径路指定手段と、 前記第１の接続が利用出来ない時、または前記第１の桁
   が、メッセージパケットがその次元内の行き先に到達し
   ていることを表わしている時に、アドレス情報の第２の
   桁を調べるためにメッセージパケットを前記第２の検査
   手段に提供するための第１の提供手段と、 接続が利用出来ないか、あるいは前記第２の桁が、メッ
   セージパケットがその次元内の行き先に到達しているこ
   とを示している時に、メッセージパケットを、アドレス
   情報の第３の桁を調べるための前記第３の検査手段に提
   供するための第２の提供手段と、 接続が利用出来ない時、または、前記第３の桁が、メッ
   セージパケットがその次元内の行き先に到達したことを
   示す時に、メッセージパケットを追加の検査手段又は記
   憶／処理手段に提供するための第３の提供手段と、 行き先に到達したメッセージパケットをメッセージシン
   クへ径路指定し、行き先に径路指定されなかったメッセ
   ージパケットへを一時的に記憶し、記憶したメッセージ
   パケットを、さらに径路指定するために前記第１の検査
   手段へ再循環するための記憶／処理手段とを含むように
   したことを特徴とするパッケージアレイ。
7. （７）２あるいはそれ以上の次元パターン内で相互接続
   されるノードのネットワークを通ってメッセージパケッ
   トを径路指定するための装量において、 メッセージパケット内に含まれている相対アドレス情報
   に従って、前記パターン内の１つのノートから他のノー
   ドへ径路指定されるメンセージパケットを発生するため
   の手段であって、該相対アドレスは次元と同じ数の桁か
   ら成り、名指はメッセージパケットがアドレス指定され
   ているノードからのメッセージパケットの相対変位を表
   わすようにしたメッセージパケット発生手段と、その次
   元での変位がゼロであるかどうかを決めるために、ノー
   ドで受け取る前記メッセージパケットのアドレスの第１
   および第２の桁をそれぞれ調べるための少なくとも第１
   と第２の検査手段と、もし、調べた桁がメッセージパケ
   ットが、行き先に到達していないことを示し、かつその
   ノードへの接続が利用可能の場合に、第１と第２の次元
   内の他のノードへそれぞれ該メッセージパケットを径路
   指定するための少なくとも第１と第２の径路指定手段と
   、 前記第１の接続が利用出来ず、または前記第１の桁かメ
   ッセージパケットがその次元内の行き先に到達している
   ことを示す時に、アドレス情報の第２の桁を調へるため
   に、メッセージパケットを前記第２の検査手段に提供す
   るための第１の提供手段と、 接続が利用出来ない時、または前記第２の桁が、メッセ
   ージパケットがその次元内の行き先に到達したことを示
   す時に、メッセージパケットを、追加の検査手段または
   記憶／処理手段に提供するための第２の提供手段と、 行き先に到達したメッセージをメッセージシンクへ径路
   指定し、行き先に径路指定されなかったメッセージを一
   時的に記憶し、さらに径路指定をするために、記憶され
   たメッセージを前記検査手段へ再循環するための記憶／
   処理手段と、を含むことを特徴とするメッセージパケッ
   ト径路指定装置。
8. （８）特許請求の範囲第７項の記載において、それを介
   してメッセージパケットが径路指定される各ノードにお
   ける相対変位を更新するための手段をさらに含むことを
   特徴とするメッセージパケット径路指定装置。
9. （９）特許請求の範囲第７項の記載において、相対変位
   の２つのコピーが開始ノードで発生され、１つのコピー
   中の変位は、それを介してメッセージパケットが径路指
   定される各ノードで更新される一方で、相対変位の他の
   コピー内の個々のヒソトが、メッセージパケットの径路
   指定を制御するために前記径路指定手段によって調べら
   れることを特徴とするメッセージパケット径路指定装置
   。
10. （１０）特許請求の範囲第９項の記載において、各ノー
    トにおける前記第１の検査手段、第１の径路指定手段、
    および第１の提供手段が、前記ネットワークの他のノー
    ドの第１の検査手段、第１の径路指定手段、および第１
    の提供手段と同期して作動し、各ノードにおける前記第
    ２の検査手段、第２の径路指定手段および第２の提供手
    段は、前記ネットワークの他のノードの第２の検査手段
    、第２の径路指定手段および第２の提供手段と同期して
    作動するようにしたことを特徴とするメッセージパケッ
    ト径路指定装置。
11. （１１）プロセッサ／メモリのアレイを含み、各プロセ
    ッサ／メモリが、そこにデータが書き込まれ、そこから
    データが読み出されるメモリ手段と該メモリ手段から読
    み出されるデータおよび命令情報の少なくとも一部に依
    存して出力を発生するためのプロセッサとを含むよう描
    成した並行コンピュータ処理のためのプロセッサアレイ
    において、ｎを２より大きい数としたときに、前記アレ
    イ内のいずれかのプロセッサ／メモリから他のいずれが
    のプロセッサ／メモリへ、それを介してデータが径路指
    定される少なくとも２ｎ個のノードを持つｎ−次元パタ
    ーン内のプロセッサ／メモリを内部接続する方法であっ
    て、 前記メッセージパケット内に含まれるアドレス情報に従
    って、前記ｎ−次元パターン内で１つのプロセッサ／メ
    モリから他のプロセッサ／メモリ径路指定されるアドレ
    ス指定されたメッセージパケットを発生するステップと
    、 前記ｎ−次元パターン内の各ノードにおいて、面記パケ
    ット内のアドレス情報に従って該メッセージパケットを
    径路指定するステップと、を含むことを特徴とする方法
    。