@1992__SPAA__The Network Architecture of the Connection Machine CM-5

# The Network Architecture of the Connection Machine CM-5 > [!abstract] 概要 > Connection Machine Model CM-5 スーパーコンピュータは、1 テラフロップス(10^12 回の浮動小数点演算/秒)の範囲の性能を提供するよう設計された超並列計算機システムである。CM-5 は、プログラミングの容易さ、柔軟性、信頼性を備えたまま高い性能を得る。このマシンは 3 つの通信網、すなわちデータ網、制御網、診断網を持つ。本論文は、これら 3 つの網の構成と、それらが CM-5 の設計目標にどう寄与するかを述べる。 ## 論文情報 - 著者: [[Charles E. Leiserson]]、[[W. Daniel Hillis]]、[[Bradley C. Kuszmaul]] ほか 10 名([[Thinking Machines Corporation]]、マサチューセッツ州ケンブリッジ)。Leiserson は同社の Corporate Fellow で MIT 計算機科学研究所の教授、Kuszmaul は同社のコンサルタントで同研究所の大学院生と脚注にある。 - 掲載: SPAA '92(PDF 版面の著作権表示は「SPAA '92 - 6/92/CA」、© 1992 ACM)。ページ番号は 272 から 285。表題に Extended Abstract とあり、本文の日付は 1992 年 5 月 5 日である。 - 対象: [[Connection Machine CM-5]] の 3 つの通信網と、網とプロセッサの間に置いたネットワークインターフェース。 - DOI と公式 URL は本文から確認できなかったため記載しない。 ## 概要 CM-5 は 32 個から 16,384 個の処理ノードを持ち、各ノードは 32 MHz の SPARC プロセッサ、32 MB のメモリ、64 ビットの浮動小数点数と整数を扱える 128 メガフロップスのベクトル演算ユニットからなる。ノード、制御プロセッサ、入出力チャネルを 3 つの網でつなぎ、データ網が点対点通信を、制御網がブロードキャスト・同期・スキャンなどの協調演算を、診断網が全ハードウェアへの「裏口」アクセスを担う。データ網は 4 分木のファットツリー、制御網と診断網は 2 分木である。論文は、この 3 網構成を、性能・規模・データ並列モデル・信頼性・可用性・時分割と空間分割の両立という設計目標から順に説明し、開発の経過で結ぶ。 ## 問題設定設計の出発点は、著者らが最初に定めた目標である。単なる性能仕様にとどまらず、次の 9 点を掲げる。 - 利用者が容易に高い性能を引き出せること。病的な最悪ケースを気にさせず、最良ケースには特別な工夫なしで到達させる。 - 網の論理設計を 100 万ノードまで拡張できること。 - データ並列プログラミングモデルを効率よく支えつつ、他のモデルも許すこと。CM-2 で使った Fortran90、\*Lisp、C\* を CM-5 へ移植し、他機種向けのコードも競争力のある速度で動かす。 - 網の障害を検知し、素早く切り分け、迂回して再構成できること。部分故障でも性能低下が小さいこと。 - 空間分割の環境で、他の利用者や他のパーティションの入出力から通信が隔離されること。 - 時分割の環境で、各利用者が帯域を公平に得られ、素早くコンテキストスイッチでき、特権ソフトウェアが利用者のタスクを奪取できること。 - 網が早期に動作すること。市場投入の速さが重要であり、簡素で検証しやすく、設計変更に強いことを求める。そのため銅線、CMOS、スタンダードセル、性能に効く部分だけカスタムのマクロセルという保守的な技術を選んだ。技術の小刻みな改善より、アーキテクチャの改善のほうが得るものが大きいという立場である。 - 網のチップを、技術やアーキテクチャの改善を後の版で取り込みやすい形に分けること。CM-2 ではプロセッサと通信を同じチップに載せたため、片方だけの技術更新が難しかった。 - 機構の経済性と機能の単一性。データ網の仕事はメッセージを届けることだけであり、メッセージの結合・複製・受領通知は行わない。前作 CM-2 と比べ、最大構成で電子部品が 10 倍を超えるため、信頼性の設計に特に力を入れたと述べる。 ## 提案手法 ### システム構成 ![[_attachments/The-Network-Architecture-of-the-Connection-Machine-CM-5/fig01-cm5-organization.png]] *図1(Figure 1): CM-5 の構成。データ網・制御網・診断網の 3 網が、ネットワークインターフェース(NI)を介して処理ノード(P と M)、制御プロセッサ(CP)、入出力チャネルにつながる。* システムは 1 個以上のユーザーパーティションとして動く。各パーティションは 1 個の制御プロセッサ、処理ノードの集合、データ網と制御網の専用部分から構成される。制御プロセッサは Sun Microsystems のワークステーションで、1 台から数十台あり、システム管理と逐次のユーザータスクを実行し、Ethernet で接続する。最大構成の占有面積は約 30 m 四方で、1 テラフロップスを超える。システム機能は特権と非特権に分けられ、非特権の機能(データ網と制御網へのアクセスを含む)はシステムコールなしにユーザーコードから直接実行できる。診断網、入出力などの共有資源、他パーティションへのアクセスは特権であり、システムコールを要する。 ### ネットワークインターフェース網とプロセッサの間に、互いの詳細を隠すインターフェースを置く。プロセッサからはメモリマップされたレジスタと FIFO の集合に見え、特定のアドレスへの書き込みや読み出しがコマンドになる。メッセージ送信はプロセッサが出力 FIFO へデータを書き込むことで行い、到着は割り込みかステータスビットのポーリングで知る。保護はメモリ管理ユニットに任せ、特権操作に対応するレジスタを保護ページに置く。利用者にはプロセッサのアドレスを、パーティション先頭からの 0 起点の連続した相対アドレスとして見せる(故障したプロセッサは除外して詰める)。物理アドレスの指定は特権を要し、相対アドレスは範囲検査される。網のトポロジは利用者から隠す。配線が存在しないかもしれない(故障で迂回する)ためであり、著者らはトポロジ非依存による性能低下は当初の想定ほど大きくなかったと述べる。網は到達の保証を自ら負い、再送プロトコルを持たない。エラー検出回路の分だけ網の性能は少し下がるが、プロセッサが障害を扱わなくてよいので、利用者から見た性能は高くなるという判断である。インターフェースは 1 マイクロメートルのスタンダードセル CMOS チップ 1 個で、32 MHz のプロセッサクロックと 40 MHz の網クロックの両方で動き、非同期アービタで橋渡しする。同じチップが CMIO、VME、FDDI、HIPPI などの入出力チャネルにも使われる。 ### データ網 ![[_attachments/The-Network-Architecture-of-the-Connection-Machine-CM-5/fig02-binary-fat-tree.png]] *図2(Figure 2): 2 分ファットツリー。葉にプロセッサ、内部ノードにスイッチを置き、根に近づくほどチャネル容量が増える。パーティションは部分木に対応する。CM-5 のデータ網は 2 分木でなく 4 分木を使う。* 基本構造は[[Fat-Tree]]である。処理ノード、制御プロセッサ、入出力チャネルを葉に置き、根に近づくほどチャネル容量を太くする。ユーザーパーティションは部分木に対応するため、パーティション内で閉じる通信は木の上位の帯域を使わず、他のパーティションのトラフィックの影響を受けない。入出力チャネルも処理ノードと同じ方法でアドレスされ、データ網は全部品が単一の名前空間を持つ「システムバス」になる。メッシュやハイパーキューブは実装上の帯域制約に合わせてトポロジを調整しにくいが、ファットツリーは帯域を任意に選べる。どう選んでも、近似的に最適なルーティングアルゴリズムが存在する(引用文献 [8]、[14])と述べる。メッセージは送信元と宛先の最小共通祖先まで上り、そこから下る。 ![[_attachments/The-Network-Architecture-of-the-Connection-Machine-CM-5/fig03-data-network-interconnect.png]] *図3(Figure 3): CM-5 データ網の接続パターン。4 分木のファットツリーで、各内部ノードは複数のルーターチップからなり、各チップは子 4 本と親 2 本または 4 本につながる。* ピン数、ケーブル 1 本あたりの線数、最大ケーブル長などの実装上のトレードオフから、2 分木ではなく 4 分木を採った。ルーターチップは子への接続 4 本、親への接続 2 本または 4 本を持ち、各接続は各方向 20 メガバイト/秒(生の帯域。アドレス、タグ、誤り検査、輻輳制御にも使う)である。各プロセッサは網へ 2 本つながり、ノードの入出力は生で 40 メガバイト/秒になる。下位 2 段は親接続を 2 本しか使わず、16 ノードの部分木の外向き帯域は 160 メガバイト/秒である。それより上位は 4 本すべてを使い、2K ノード構成の半分ともう半分の間で各方向 10 ギガバイト/秒となる。帯域は 16,384 ノードまで線形に増え、アーキテクチャ自体は 100 万ノード以上に拡張できる。大規模構成では伝送線路技術で配線遅延の制限を避け、複数ビットを配線上に流し続ける。メッセージは上る際、他のメッセージに塞がれていない親リンクから擬似乱数で選ぶ。最小共通祖先の高さに達したら、下りの経路は 1 本に決まる。擬似乱数の選択が負荷を均し、病的なメッセージ集合による輻輳を避ける。これにより利用者は素直に書いて高い性能を得られ、ルーティングの性能は単純なモデル[16]で予測できる。各腕を通る負荷を利用可能な帯域で割り、全腕の最悪の比を推定値とする。ルーターチップは 1 マイクロメートルのスタンダードセル CMOS で、子へ 4 本、親へ 4 本の 8 ビット幅の双方向リンク(各方向のデータは 4 ビット)を持つ。8 入力 8 出力のクロスバーに見立てられるが、親ポートから別の親ポートへは経路にならないなど、不可能な接続がある。ブロックされたメッセージはバッファに入れ、逆方向にフロー制御情報を流す。出力ポートの競合は公平に調停する。チップ間は差動対の配線で送り、ノイズ耐性と低電力を得る一方でピン数が増える。最初の 2 段はバックプレーン、それより上はケーブル(9 フィートまたは 26 フィート)で、被覆に発泡テフロンを使い、光速の 90 % を超える速度で信号を運ぶ。データ網チップは 40 MHz で同期し、クロックは中央から放送する信号に局所クロックの位相を合わせて低スキューで配る。 ![[_attachments/The-Network-Architecture-of-the-Connection-Machine-CM-5/fig04-data-message-format.png]] *図4(Figure 4): データ網のメッセージ形式。ルーティング命令、長さ、タグ、データ、CRC の順に並ぶ。* メッセージは、上る高さと下る経路を示すチップ相対のルーティング命令、32 ビットワードを単位とするデータ長(現状 1 語から 5 語。これより長いメッセージは分割する)、4 ビットのタグ、データ、巡回冗長検査(CRC)の順に並ぶ。タグの一部はシステムメッセージに使われ、残りは利用者が使える。到着時にはタグでネットワークインターフェース内の 16 ビットのマスクレジスタを引き、対応するビットが 1 ならプロセッサへ割り込む。 **障害の検知と隔離。** 完全性はすべてのリンクとスイッチで検査する。メッセージはワームホール様に通り抜けるため、エラー検出時には先頭が遠くへ進んでいる。誤り連鎖を防ぐため、正しい CRC の補数を末尾に付け、それを見つけたチップは二次エラーを報告する。典型的な故障では 1 つのチップが一次エラー、以降のチップが二次エラーを出し、診断プログラムが診断網経由でこれを読んで故障チップやリンクを特定する。喪失や複製は、各チップとインターフェースがリンクごとに数えるメッセージ数で検知する。キルヒホッフの電流則の変形として、任意の領域(網全体や 1 チップを含む)に入るメッセージ数は出る数と最終的に一致しなければならず、この条件は制御網が網全体について検査する。故障したノード、チップ、リンクは特定してシステムから切り離す。データ網内の故障には、故障を避けるように経路を設定するか、影響するノードを切り離すかの 2 つの手段があり、良い方を選べば、網の損失を最大 6 % か、切り離すノードを最大 64 分の 1 のどちらかに抑えられると述べる。 **網の契約とデッドロック。** データ網は「プロセッサが到着したメッセージを最終的にすべて取り出すなら、網は注入されたメッセージを最終的にすべて受け入れて届ける」という契約をプロセッサと結ぶ。網は入力から出力へ非巡回のため、契約が守られればデッドロックしない。送信側は出力 FIFO が受け付けたかを確認し、受け付けられなければ後で再試行し、その間に到着したメッセージを受信しなければならない。単純な契約だけでは、各プロセッサが他から値を取ってくる往復通信のようなプロトコルを素直には実装できない(要求が溜まると受信を拒否して契約を破る)。バッファをプロセッサ数に比例して持てば往復プロトコルは組めるが、帳簿管理が要る。CM-5 は、各プロセッサに出力 2 本・入力 2 本の FIFO(左ポートと右ポート)があり、左から届く経路と右から届く経路が交わらない(網が独立な 2 つの交互配置の網になっている)ことを使う。要求を左で送り、応答を右で返すことで、一定のバッファで、記録も要らずデッドロックが起きない。応答を両側で送っても、要求を片側にだけ送るなら安全で、複数の中継先があっても通信を往復の集まりに分解できるので、2 側で足りる。CM-5 のプログラミングシステム(Fortran90、C\*、\*Lisp)はデッドロックフリーなプロトコルを実装しており、デッドロックの危険があるのは、利用者が各ノードを直接プログラムして送信ばかりで受信を怠る場合に限る。著者らはこれを無限ループを書く危険と同程度と見なし、その場合も他の利用者へ影響しないとする。 **時分割とコンテキストスイッチ。** タイムスライスが切れたとき、網内を進行中のメッセージをどうするかが問題になる。破棄する案は、利用者が絶えずチェックポイントを取る負担が大きく、全メッセージが同一ノード宛だと網を空にする時間がマシン規模に比例して長くなるため退けた。CM-5 は、データ網を**all-fall-down モード**(全メッセージ下降モード)にする。メッセージを宛先へ届けようとせず、すべて網の下方向へ誤ルーティングして処理ノードに均等に分散させ、利用者の状態と一緒にメモリに退避する。再開時に本来の宛先へ再送する。時分割中の利用者がデッドロックしても、他の利用者への影響をこの機構が防ぐ。 ### 同期 MIMD とデータ並列 CM-5 は同期 MIMD である。データ網が任意の 2 プロセッサ間のデータ移動を担うのに対し、制御網はプロセッサ集合の協調と同期の基盤を担う。通信を制御網とデータ網に分けたのは、プロセッサが制御部とデータパスに分かれるのと同様に、設計を簡素で効率的にするためと説明する。[[データ並列プログラミング]]の要請(大きなデータ集合に同一演算を適用する)は、従来は SIMD 機が支えた。SIMD 機は全ノードに同じ命令を放送して同時に実行させるため同期しやすく、各ノードに命令フェッチ機構がいらない。一方で、プロセッサごとに異なるコードを実行したい場面では、コードの節を順に実行して該当しないプロセッサは待つので効率が落ちる。MIMD 機は各プロセッサが独自の命令列を実行するので効率は落ちないが、集合的な操作の同期と集約を利用者が自作することになり、コードの複雑化と性能低下の代償が大きい。 CM-5 は CM-2 の SIMD を捨て MIMD を採ったうえで、SIMD の最良の性質、すなわちプロセッサ間でデータを効率よく共有できることと、プロセッサ集合を素早く同期できることを取り戻した。前者を制御網の高速ブロードキャスト、後者を高速な[[バリア同期]]で実現する。データ並列プログラムの実行では、制御プロセッサがプログラムの一区間(命令列全体ではなく)を処理ノードへブロードキャストし、各ノードがそれをローカルで実行する(SPMD)。通信を伴う場合、プログラムの正しさのため、いつ通信の後のコードへ進んでよいかを各プロセッサが知る必要がある。CM-5 は網内のメッセージ経路の完了を全プロセッサに通知する同期機構を持ち、バリアの一部として制御網で提供する。著者らは同期 MIMD が SIMD に対して持つ実装上の利点を 4 つ挙げる。第 1 に、ノードの入出力帯域は貴重な資源であり、プログラムは生成する命令列よりずっと短いので、プログラムを放送するとデータのための帯域が増える。第 2 に、ノードが命令を局所で取り出せるので、独自設計でなく標準のマイクロプロセッサ(当時登場しつつあった高性能 RISC)を使え、網とベクトルユニットに設計力を集中できた。第 3 に、制御網が他のシステム協調問題を解く土台になる(利用者が一部のプロセッサを停止させたとき、OS がブロードキャストでスーパーバイザ側へ移行させる)。第 4 に、従来型の MIMD コードを動かせ、他機種のメッセージパッシングアプリケーションを移植して、複雑なプロトコルを制御網の単純な使用に置き換えて簡素化できた。 ### 制御網 ![[_attachments/The-Network-Architecture-of-the-Connection-Machine-CM-5/fig05-control-message-format.png]] *図5(Figure 5): 制御網のメッセージ形式。種別、32 ビットのデータ、同期ビット、フラグ、CRC からなる。* 制御網の操作は、ブロードキャスト、コンバイニング、大域操作の 3 種類で、種類ごとに別の FIFO が対応する。全操作がほぼ全処理ノードに関与し、[[並列プレフィックス演算]]のように全プロセッサから入力を受けて全プロセッサへ出力するものもある。網はパイプライン化され、結果を受け取る前に複数のメッセージを送れる。各ノードは特定の制御網操作に参加しないよう設定でき、その場合は恒等元を与えたものとして完了する。全体として、二分帯域幅をほとんど要しない協調機能を、単純な木で効率よく実装する設計になっている。 **ブロードキャスト。** パーティション内の 1 プロセッサから全員へメッセージを送る。ユーザーブロードキャスト、スーパーバイザーブロードキャスト、割り込みブロードキャスト、ユーティリティブロードキャストの 4 種がある。ユーザーとスーパーバイザーの違いは特権かどうかだけである。割り込みは全プロセッサに割り込みを起こし、時分割の切り替えなどに使う。ユーティリティはパーティションの構成などに OS が使う。同時に放送できるのは 1 プロセッサで、競合すると衝突エラーになる。放送語数は利用者が最大 8 語、スーパーバイザーが最大 4 語である。 **コンバイニング。** リダクション、前方スキャン、後方スキャン、router-done の 4 種類がある。リダクションは 32 ビットワードに対し、ビット単位の OR、ビット単位の XOR、符号付き最大値(IEEE 浮動小数点数にも使える)、符号付き加算、符号なし加算の 5 種類の演算子のいずれかで全プロセッサの値を結合し、結果を全員に配る。AND など他の演算子は、これらと局所演算の組み合わせで作れる。前方スキャンは i 番目のプロセッサに、直前 i-1 個の値へリダクション演算子を適用した結果を返す(例: ベクトル (3, 2, 0, 4, 2, 6, 5, 8) を + で前方スキャンすると (0, 3, 5, 5, 9, 11, 17, 22) になる)。後方スキャンは逆向きである。「セグメント開始」ビットを立てるとそこからスキャンをやり直す、セグメント化スキャンも使える。スキャンをハードウェアに持つ判断は設計の早い段階で下したもので、CM-2 の経験から、組み合わせ論的・数値的を問わず、多くの高性能データ並列アルゴリズムがスキャンを多用するためと説明する。演算の選択は、ハードウェアを速く単純に保つことと、他の演算を作る部品として十分であることの折衷であり、例えば OR から AND をド・モルガンの法則で作れるので両方を実装しない。セグメント化リダクションは、セグメント化スキャンを前方と後方で 2 回行えば実現でき、網がパイプライン化されているので追加のオーバーヘッドは小さい。 router-done は、データ網を使う通信が終わったことをプロセッサに知らせる特殊なリダクションである。原理はキルヒホッフの電流則で、全プロセッサが送信を終え、データ網に入ったメッセージ数と出た数が等しくなれば、ルーティング周期が完了とみなす。ネットワークインターフェースが出入りするメッセージ数を数え、各プロセッサは送信完了後に出力用の router-done FIFO へメッセージを押し込む。全員が押し込むと、制御網が網内メッセージの入出差を監視し、これがゼロになると各プロセッサが入力 router-done FIFO でメッセージを受け取る。この方法にはハードウェア誤りでメッセージが失われたり生じたりした場合にそれを検知できる副次的な利点があり、router-done が完了しないか、完了後に予期しないメッセージが届くことで表面化する。 **大域操作。** 同期 OR 1 種類と、同一の非同期 OR 2 種類がある。同期 OR は OR リダクションに似るが、入出力が各 1 ビットである。非同期 OR は全プロセッサの参加を待たず継続的に動作し、各プロセッサはいつでも入力を変え出力を標本できる。条件や例外の通知に使い、0 から 1 への遷移を割り込みに使える。2 つの非同期 OR の一方は特権である。同期 OR やコンバイニング操作を使って**分割相バリア**を実装できる。バリアは入口と出口を持つコード領域であり、プロセッサは入口で入力メッセージを送り、他の全員が送った直後に対応する入力 FIFO から結果を受け取って、全員が入口に達したと推論する。通常のバリアと違い、待つ間に他のコードを実行できるので、RISC の遅延分岐が分岐遅延を補うのと同様に、同期の遅延を隠せる。router-done はバリア同期とデータ網の完了検査を結合したもので、全員が送信を終えるまでどのプロセッサも受信をやめない。時分割の切り替え時、制御網は放送に似た方法でフラッシュされ、進行中のユーザーレベル操作を中止する。ネットワークインターフェースは、利用者が押し込んだ値を対応する操作の完了まで保持するので、それを利用者の状態の一部として保存し、再開時に操作を再開できる。制御網は通信エラーも検出し、例えば 2 つのプロセッサが異なるコンバイニング操作を試みるとエラーを通知する。データ網とインターフェースが検出した致命的エラーを集めて OR で結合し、全プロセッサに再配布して、OS が切り分けと回復を試みられるようにする。 **構成。** 制御網は、処理ノード、制御プロセッサ、入出力チャネルを葉とする完全 2 分木である。各ユーザーパーティションは部分木に割り当てられ、処理ノードが葉に、制御プロセッサが追加の葉として配置される。実装は 1 マイクロメートルの CMOS スタンダードセルのチップで、40 MHz のクロックを使い、1 チップに 2 分木のノードを 3 個載せ、チップ間の信号は差動対で送る。パケットは 65 ビットの固定長(初期化時に境界を合わせるための 5 ビットのパケットも別にある)である。主ストリームは、パケット種別と具体的な操作(ユーザーブロードキャスト、スーパーバイザーブロードキャスト、割り込み、スキャン、リダクションなど)を示すフィールド、32 ビットのデータ、大域同期ビット、CRC の順で、副ストリームに誤りとステータスのフラグ、フロー制御ビット、セグメント化スキャン用ビットを置く。パケットは単一ソース、複数ソース、アイドル、棄権の 4 種類である。単一ソースはブロードキャストや割り込みに使い、葉から根へ上って折り返し、パーティション全員へ配る。異なる送信元の単一ソースパケットが同じノードで出会うとエラーとなり、他の種類と出会うと優先される。バッファリングは無く、フロー制御はネットワークインターフェースが端から端で行う。スキャンとリダクションは複数ソースパケットを使う。各内部ノードで、複数ソースのメッセージは兄弟のメッセージが着くまで待ち、その間アイドルパケットを上へ送る。着いたら算術・論理演算で 2 つを 1 つに結合して上へ送る。スキャンでは一方を別のバッファに置いて、親から来る値と後で結合する。根まで達すると下向きに送られ、内部ノードで複製されるか、待機中のメッセージとさらに結合される。同一入力に着いた他のパケットは処理でき、単一ソースは待機中のパケットを追い越すので、スーパーバイザーブロードキャストや割り込みを優先できる。複数ソース同士は待機パケットの後ろに並び、順序が保たれるので、複数のコンバイニング操作を適切にパイプライン化できる。棄権パケットは、複数ソースパケットを待つはずのノードが先へ進むために使う。制御プロセッサを各パーティションに 1 個対応させたのは、逐次部分を処理ノードの 1 個か全部に任せるより簡素になるためである。制御プロセッサのコストは大量の処理ノードに比べて低いので、大容量メモリと追加のアーキテクチャ機能で強化でき、逐次コードを処理ノードより効率よく実行できる。CM-2 上のデータ並列コードもすでに逐次部分と並列部分に分かれていて、移植しやすい。制御プロセッサは Ethernet に接続されるので、パーティションは標準の Unix を動かし、外部と通信できる。 **制御網の障害対応。** 制御網もデータ網と同様、故障を切り離せる。診断網が制御網内部のスイッチを設定して一部を切り離す。制御網の計算は 2 分木であることにのみ依存し、完全 2 分木であることには依存しないため、切り離された部分を安全に無視できる。加えて、制御網自体の故障を迂回し、任意の制御プロセッサを任意のパーティションへつなげるスイッチ機能があり、各スイッチは親 2 本と子 4 本を持ち、2 個の 2 分木ノードを静的に設定できる。これらをデータ網のファットツリーに似た形でつなぐことで、帯域の許す範囲で任意の制御プロセッサを任意のパーティションへ接続できる(例えば部分木への制御網チャネルが 4 本しかなければ、5 台の制御プロセッサを 5 つのパーティションにはつなげない)。この範囲なら、オフラインのルーティングアルゴリズム(引用文献 [15] の定理 1 に似たもの)で任意の割り当てを実装できる。 ### 診断網利用者から見えない唯一の網である。数万個のデバイスからなる最大構成では、部品の信頼性だけで高可用性を得ようとする方針を捨て、診断可能性(欠けた・壊れたハードウェアを検知して切り分ける)と構成変更可能性(一部が壊れたり保守中でもマシンの大半を動かす)の 2 つに頼った。診断の方式は 2 つに分けて論じる。**機能依存**の診断は、ノード上で動かす診断プログラムで各網を働かせるが、故障箇所のせいで診断プログラム自体が失敗し得る。CM-1 と CM-2 の経験では、書くのが極めて難しい、網羅性が曖昧、根本原因の報告精度が低いという限界があった。**機能独立**の診断は、通常動作の成否ではなく専用のテスト構造で故障を検知する。この設計観点(テスト容易化設計)では、マシンをレジスタと組み合わせ論理と配線の集合とみなせるため、市販のツールでチップ・ボード・配線の高い網羅率のテストを自動生成でき、失敗時は故障の位置と範囲が具体的に分かる。 CM-5 のすべての VLSI 部品は IEEE 1149.1 の試験容易化アーキテクチャ標準(JTAG)に対応する。JTAG は各チップに 4 ピンのインターフェースを与え、2 本が選択可能なスキャンチェーンの入出力、残り 2 本がクロックと制御である。全 I/O パッドをビット直列のシフトレジスタに接続するバウンダリスキャンレジスタで、チップコアへの刺激の印加や入出力の監視ができる。CM-5 は独自チップに完全な内部スキャンを加えるよう標準を拡張した(詳細は引用文献 [24])。これによりテストパターンの自動生成ソフトウェアで、故障網羅率の非常に高いスキャンベクトルを作り、製造・パッケージ時にも組み立て後のシステムでも診断網経由で同じテストを使える。(脚注: 実装時点で SPARC ノードと DRAM チップは JTAG に対応していなかった。ここでの「スキャン」はスキャンによる並列プレフィックス演算とは無関係である。) JTAG はチップ数が増えるとスキャンパスを直列につなぐ方式で、全チップの検査に直列アクセスが必要になる。1 デバイスあたり秒オーダーの理想的なテスト時間でも、数万個のデバイスからなる 16,384 ノードの CM-5 では遅すぎ、同じ部品を並列にテストできる並列性も生かせない。そこで、スキャン方式の診断を並列に支える診断網を設けた。JTAG に対応するすべてのチップへスキャンアクセスを、非対応のチップへプログラム可能なアドホックアクセスを与える。診断網自体も完全にテスト・診断でき、故障または電源断の部分を切り離して無視できて、ユーザーパーティションと整合するように分割できる。次の集合を並列に選べる。単一のチップ、単一種のチップ、ユーザーパーティション内のチップ、地理的な一部(ボード、バックプレーン、キャビネット等)、およびそれらの和と積である。診断網は完全でなくてもよい 2 分木で、根に 1 個以上の診断プロセッサ、葉に**ポッド**(ボードなど JTAG を直接支える物理的な部分系)を置く。ある時点で制御するのは 1 個の診断プロセッサである。根から個々のポッドへは、木の各レベルが 1 ビットに対応する 2 進数でアドレスする。高さ h の木では h ビットあれば足りる。複数ポッドをまとめて指定するため、「超立方体アドレス」に似た診断仮想アドレスを使う。h 桁の各桁を 0、1、B(both、0 と 1 の両方に一致するワイルドカード)とし、例えば高さ 6 の木のアドレス 00B10B は {4, 5, 12, 13} を指す。桁数を減らせば木の内部ノードもアドレスできる。デコードは、根から**トークン**を桁直列(上位桁から)で下へ導く方式である。 ![[_attachments/The-Network-Architecture-of-the-Connection-Machine-CM-5/fig06-diagnostic-token-steering.png]] *図6(Figure 6): 診断網でトークンを下へ導く様子。アドレスの各桁(0、1、B)が左・右・両方の部分木の選択を表す。* 根は先頭桁に応じて右、左、または両方の部分木を選び、両方なら分割する。以降の桁で下へ導き、アドレスが終わると、トークンを保持するノードが選択されたことになり、根までの経路が制御の導線になる。トークンと経路は、後続のアドレスが消すか明示的に消去するまで残るため、2 つの選択集合の和を取れる(例: 左の集合を 0 で選び、次に右の集合を 1 で選び、最後に B を持つトークンで根自体を選ぶと両方の子が有効になり、2 つの集合が併合される。図6 はこの選択の途中の様子を描く)。この仕組みの大半は診断技術者から隠され、ソフトウェアがポッド内のチップまで診断仮想アドレスを拡張し、キャビネット、バックプレーン、スロット種別、スロットなどを指定する**地理的アドレス**や、データ網・制御網から見た構成部品の位置を示す**網アドレス**との間で変換する。重要なのは、各種の部分集合へのアクセス時間が、マシンの規模が 2 倍になっても小さな加算分しか増えないことである。選択したポッドの集合へスキャンベクトルを並列に印加してエラーを検知する。JTAG の直列データと制御入力は全ポッドへ放送し、各ポッドのスキャン出力は選択されたポッド間で OR か AND で結合する。期待するビットが 1 なら AND(すべてが 1 を返すときだけ 1)、0 なら OR(すべてが 0 を返すときだけ 0)を選ぶ。エラーが見つかれば、群の各ポッドを 1 個ずつ、または分割統治で個別にアドレスして隔離し、ポッド内は JTAG インターフェースの直列連鎖の標準手法でチップまで切り分ける。木なので自己診断も容易である。根より下の各レベルを上位のレベルでテストでき、診断網はロジックが少なくそれ自体が故障する確率が他の部分より低い。ロジックの大半は葉の近くにあるので、故障しても隔離される範囲は小さい。根に近い少数の部品への依存は許容できる(小さな集合ならとても信頼性が高く、故障確率が高いのは大きな集合である)。現在の実装は、二分木ノードのアドレスデコードを 24 ピンの PAL(P22V10)、有限状態制御を 20 ピンの PAL(P18V8)にした 2 個の市販チップで実現し、約 1 MHz までのクロックで動く。4 分木や 8 分木のノードのデコードは、チップ数を節約するため 1 チップの PAL で直接実装した箇所もある。機内検査は、JTAG に対応するすべてのチップと全網について、単一縮退故障の網羅率が 99 % を超える。 ## 新規性 - 3 網を目的別に分離し、それぞれを最小限の機能へ絞る設計を、CM-5 の制約(市場投入の速さ、100 万ノードへの拡張、部分故障下での動作、時分割と空間分割の併存)から導いて示す点。 - ファットツリー(Leiserson の先行研究[8, 15])を、システム全体の名前空間を統一する「システムバス」として使い、空間分割(部分木がパーティションに対応)と入出力の統合に生かした実機の設計。 - SIMD を退け、SIMD の長所を制御網の機能として残す同期 MIMD というアーキテクチャ上の位置づけ。スキャンや分割相バリアをハードウェアの部品として持つ。 - データ網の契約と、左右 2 ポートを使う往復通信のデッドロック回避、all-fall-down によるメッセージの退避と再送。 - JTAG を基盤に、診断網を木と診断仮想アドレスで構成する点。同一部品の並列テストをシステム規模まで広げる。 ## 実験設定本論文は Extended Abstract であり、実験設定を持たない。性能値は、初版(initial release)の CM-5 の仕様と実測として本文中に示される。著者らは、これらの数値は進化する実装のスナップショットにすぎないと明記する。 ## 実験結果本論文には評価表や比較実験はない。本文中の定量的な記述は次のとおりである。 - ランダムな置換では、各プロセッサが網へデータを出し入れする速度が 4 メガバイト/秒を超える。最近傍などの局所的なパターン(規則的または不規則な 2 次元・3 次元格子)では 1 プロセッサあたり 15 メガバイト/秒に達する。 - 網の遅延は、マシンの規模に応じて 3 マイクロ秒から 7 マイクロ秒である。これらの値はプロセッサがメッセージを網へ出し入れする命令の実行時間を含む。 - 2K ノード構成の半分ともう半分の間の帯域は、各方向 10 ギガバイト/秒である。 - 最大構成は 16,384 ノード、1 テラフロップスを超え、約 30 m 四方を占める。 - 診断網による機内検査は、単一縮退故障の網羅率が 99 % を超える。 - 開発経過(結論節)。アーキテクチャの検討は 1987 年後半に始まり、1988 年 1 月までにネットワークシミュレーションからデータ網にファットツリーを選んだ。データ網チップは 1990 年 5 月に製造へ提出し、同年 7 月に受領した。制御網チップは同年 8 月、インターフェースチップは 9 月に届き、インターフェースチップの到着から 2 日以内に 2 ノードのマシンを組んで起動し、シミュレータ上で開発した OS が同日中に動いた。1991 年 2 月から 3 月に 256 ノード機、5 月に 544 ノード機を作り、8 月にミネソタ・スーパーコンピュータセンターへ出荷した(陸軍高性能計算機研究センター向け)。1991 年 10 月に CM-5 を公式発表した。制御網を含む MIMD の構成は 1988 年前半に提案され、1989 年 5 月に正式決定した。 ## 考察 - 経済性の原理(網を 1 つにする)に反して 3 網とした理由は、通信の機能を分けると各網が単純になり、全体の設計が簡素で効率的になる(制御部とデータパスの分離になぞらえる)からである。 - トポロジを利用者へ見せない判断は、故障時の迂回と、網とプロセッサの技術更新の独立を可能にした。 - 網とプロセッサの間に網インターフェースを置く判断により、同じインターフェースチップを多様な入出力チャネルにも使えた。 - 制御網にスキャンや分割相バリアを持たせた構造は、二分帯域幅をほとんど要しない協調機能を単純な木で実現でき、SIMD と MIMD の長所を両取りする。 - 診断可能性と構成変更可能性を、部品の信頼性より優先する信頼性戦略。 ## 強み / 弱点・課題強み: - 設計判断ごとに、当時の技術制約と代替案(破棄案、SIMD と MIMD、直列 JTAG など)を挙げて理由を述べており、設計の意図が読み取れる。 - 契約による網とプロセッサの責任分担、キルヒホッフ則による喪失・複製の検知など、故障を前提にした設計が一貫している。 - 網、制御網、診断網のそれぞれで、時分割・空間分割・故障迂回との整合が示される。弱点・課題(本文から読み取れる範囲): - Extended Abstract のため、評価は少数の代表値に限られ、比較対象との定量比較や、ファットツリーの負荷分散の効果の実験はない。 - データ網が配送を保証する代わりに、プロセッサが受信を怠ればデッドロックし得る契約に依存する。直接プログラミングした場合の危険は利用者側に残る。 - 性能値は初版時点のスナップショットであり、後の版の値ではない。 - 診断網で JTAG に対応しない SPARC ノードと DRAM は、当時は対象外だった。 ## 関連 - 概念: [[Fat-Tree]] / [[相互結合網]] / [[バリア同期]] / [[データ並列プログラミング]] / [[並列プレフィックス演算]] / [[インネットワーク集約]] / [[フォールトトレランス]] / [[スーパーコンピュータ]] / [[集合通信]] - エンティティ: [[Connection Machine CM-5]] / [[Thinking Machines Corporation]] / [[Charles E. Leiserson]] / [[W. Daniel Hillis]] / [[Bradley C. Kuszmaul]] / [[Sun Microsystems]] - ソース: [[@2005__IBM JRD__Overview of the Blue Gene／L system architecture]](専用のバリア網・集合網を分ける設計の後年の記述) ## 出典 - [[.raw/papers/The-Network-Architecture-of-the-Connection-Machine-CM-5.pdf]](SPAA '92、pp. 272-285)