高並列計算機ハードウェア構成法の研究

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

高並列計算機ハードウェア構成法の研究

石川, 勉

https://doi.org/10.11501/3052535

出版情報：Kyushu University, 1990, 工学博士, 論文博士 バージョン：

権利関係：

想定する適用領域 戸皆}書イヒ 2 汐ミテ己アF レイ言十算事務虫色

α

^{〉 ノ ¥ 一 一} ド

ェア言究言十イヲリ

存者言言

T

フ

多手~ 9 主主

9 ̲  1 

動的並列問題本 静的並列問題本

P E数比例のシステム性能の実現と実用に耐えうる信頼性確保という高並列 本章では、

計算機の基本的課題の解決を目指した、階層化2次元アレイ計算機 (M1 MD型)のハー

ドウェア設計例ついて述べる。

〔知識・言語処理〕

〔認識・合成〕

・デバイスシミュレーション;・音声・文字認識

〔シミュレーション/CAD

J 

(科学技術計算〕

1 )を目標に以下を 1 0 3以上の高並列化と幅広い適用性(図9.

設計に当たっては、

‑推論処理

‑電磁解析 前提とする。

‑自然言語処理 のパタン照合;

• 3次元画像合成

‑論理シミュレーション

;・ LSI配置・配線設計 (偏微分方程式)

‑構造解析

(連立一次方程式) i )階層化アレイ構造の適用

3章で提案した階層 代表的な並列化オーバヘッドである P E間通信の性能向上のため、

/j

^静的

並列度 化アレイ構造を適用する。上位PEアレイは最大PE間距離の削減だけでなく、下位PE 本

アレイへの初期データの並列供給、 AI処理等動的並列問題^II 9)への適用を考慮した負荷

分散制御等にも利用可能とする。

フォールトトレラント構成の適用

︑

1J一u

6章で提案した 2次元n+l予備による元長構 時刻Jt 稼動率の向上、保守周期の延長のため、

PE相互による並列診断法 (NV診断法)を適用する。

成、

想定する適用領域 図9.

L S 1化構成による PEの小型化

︑ ︑

︐

J

⁝

m 

物理構造への展開が比較的容易な 2次元アレイ構造においても、これを保守・冷却等を 考慮した実装構造へ展開する場合、 PE数の増大に伴ない隣接PE間の物理的距離が増大

3節で必要なPE間通信モード 4節で隣接PE問、階層間での同期法およびその制御メカニズム、

P 3 2/8の構成について述べる

9  6節で以上を具体化した部分試作機HA

P Eの物理的 このため、

PE開通信性能さらにはPEの実効性能を低下させる¹²⁰¹⁰ な小型化が必要となり、専用LS 1化によりこれを達成する。

9.  2節で想定するシステム構成、

9.  5節でフォールトトレラント化法と効果、

以下、本章では 9. 9.  とその実現法、

し、

9  2  シ ス テ ム キ 毒 反 文

想定するシステム構成を図 9. 2に示す。同図からわかるように基本的にはパックエン ド型の 2階層の 2次元アレイ計算機である。

( 1 )各部の構成と役割

並列タスクを実行する下位のPEアレイ、前述の各種処理を行う上位のPEアレイ のアレイのPEを制御P Eと呼ぶ)、全体の制御、 PE群へのプログラムロード等を行う

システム管理プロセッサ (SMP)よりなる。 MIMD型を想定しており、 PEはデータ 処理機能、プログラム実行機能、通信機能等を有する。又、告11御PEは前述の利用目的か

Control  P E Ar ray 

PE Ar ray 

図9. 2  システム構成

‑124‑

Urer' s Computer 

川

Interface Unit 

らデータ処理機能が不可欠でおり、 L S 1化をも考慮し PEと同一構成とする。制御PE アレイの規模 (PE数)は、 PEアレイの規模の平方根程度とする。又、 SMPには汎用 計算機を用い、小規模構成時(数lOOPE以下)にはユーザ計算機でこれを兼用する。図9

2のインタフェースユニットはユーザ・計算機対応のバッファ記憶を備え、各ユーザの処 理データは本システムで、の処理開始以前に、前もってこれにロードしておくことを想定す る。すなわち、ユーザ計算機のメモリからのデータロードを含めた処理全体のターンアラ ウンドタイムは、 P Eアレイが大規模化しその処理性能が向上すると、ユーザ計算機のメ モリのスループットに制限されることになる。従って、本システムではターンアラウンド タイムではなく、処理スループットの向上を狙ってマルチユーザかっパッチ処理を前提(

大規模構成時〉とする。

なお、本システムでは、問題の並列展開、 PEへのマッピング、 PEプログラムの記述 はすべてユーザが行う (P A X 8)と同じ)こととする。

( 2 ) _{P E}間のトポロジカル的結合

2次元アレイ結合を基本に、最大P E間距離を1/2にできるトーラス結合を併用する。

P E群と制御PE、制御PE群と SMPの結合(以下、 これらを階層間の結合と呼び、 S  M P側を上位P Eと呼ぶ〉は結合用ハードウェア量の削減のためパス結合を用いる。 この 結合において制御PEのバイパス (S M PとPEアレイの直結)も可能とする。

( 3 ) P E聞の論理的結合

P E開通信およびP E間同期(フラグ、 セマフォによる)のプログラミングの容易化等 のため、隣接P E問、各階層聞はPE内のローカルメモリを共有メモリ化することで論理 的に結合する (図 9. 3 )。同図は自 PEのメモリのアドレス空間と隣接PEあるいは下 位P Eのメモリのアドレス空間の写像関係を示しており、ハッチをした部分が実メモリで ある。すなわち、各PEは自PEの実メモリより上のアドレス空間へのアクセスにより、

隣接PEのメモリを自メモリの一部の如く直接アクセスでき、制御PEはさらにそれに結 合された下位のP E群のメモリも直接アクセスできる。 PE開通信は基本的にはこのメモ

リアクセスにより実現する。

‑125‑

North P E 

West  P E  メモリ

下位PE  I I I I Sou t h P E 

， ， 

， 

図9. 3 

( 4 )フォールトトレラント構成

PE間メモリ共有

East  P E 

下位PEアレイに 2次元n

+ 

1予備を適用する。従って、 PEアレイの実際的な結合は 6章で提案した IX‑NETとなる。なお、告IJ御PEアレイにはフォールトトレラント構 成は適用しない(詳細は9. 5節参照)。

9 ̲  3  P E医昌三亘イ言す去

階層化アレイ構造では以下の P E間通信が必要になる。

‑ 同 一 階 層 内 一 「 ① 隣 接P E開通信

」 ② 遠 隔P E間通信

・ 異 種 階 層 間 一 「 ③ 上 位PE→全下位PE ト ④ H  →特定下位PE

」 ⑤ 下 位PE→上位PE

これらのPE間通信により、パックエンド型並列計算機で必要となる各種のPE間データ 転送、具体的にはプログラムロード、初期データ供給、処理中のデータ交信、結果の回収 (それぞれ、③，④，①②，⑤)を実現する。これらは、基本的にはマスタ側PEがスレ ーブ側 PEを表9. 1のようにメモリアクセスすることにより行う。以下、具体的な実現 法を示す。

表 9. 1  PE問のメモリアクセス

マ ス タ 側

S M P   _{制 御} PE  P E 

S M P  

一 一 一

ス

レ 制 御PE _{¥V/R  W / R}  

_一

W(n>l)  フ

側 W / R   W / R   W / R  

P E  W(n>l)  vV (n > 1 )  (制御PEはバイパス)

¥V :書込み R 読 出 し n ス レ ー ブPEの 数

g.  3.  1 同一階層内通信

( 1 )隣接PE開通信

これは図 9. 3のように隣接P Eのメモリが写像されたアドレス空間をアクセスするこ

1 

イラッチタイミング発生回路 Req信 号

Ack信号 データ信号

4

^{制御コード}

アドレス

データ

そ

^パリティ

受信側P E  送信側PE

このためにはメモリアクセスに必要なアドレス、データを隣接P とにより実現されるが、

PEのLS 1化を想定する場合、各リヶク毎にアドレス用 Eに転送しなければならない。

、データ用の信号線を全数独立に設けることは非現実的であるため、これらは時分割的に 転送する必要がある。又、高並列構成の場合、全PEを同期させて動作させることは、ク

ロックスキューの発生から効率的でない。即ち、非周期的な転送が必要となる。

4に時分割非同期転送法の実現例を示す。同図に示す様に、まず送信担IJPEは転 図9.

送要求信号であるReq信号を送出する。受信側PEはこれを受けて転送了承信号である A c k信号を返送する。送信側P Eはこれを受けてデータ信号を送出する。受信組IJPEで これによりアドレス、データ等を はReq信号から各種ラッチタイミング信号を作成し、

レジスタに収容し、時分割非同期転送を完了する。

(a)転送系の構成 隣接P Eへの通信が送信の場合は、受信側P Eで転送されてきたアドレス、データをも

とにメモリに書き込むことによりこれを完了する。一方、受信の場合には、受信側P Eで 4の転送手順により返送する必要が この読み出し結果を図 9.

メモリの読み出しを行い、

SYSCLK 

この転送方法は以下の この場合には2回のPE間転送が必要となる。なお、

ある。即ち、

Req  (送出側)

すべての通信で利用できる。

データ信号 ( 2 )遠隔P E間通信

」 可 ー ノ

ハリティ

九州ノJ

‑J

7ドレス  

、ーー、~

制御コード

SMP中継は制御P

2の各種通信モードが可能となる。

階層化アレイ構成では、表g.

P E中継は隣接P E間通信の繰り返し Eをバイパスした異種階層開通信(後述)により、

Ack 

一寸

により、制御PE中継は異種階層間通信と隣接PE間通信の組合せより、 それぞれ実現さ

「 J L  

制御コード・う7チ・タイミング れる。

ここで用いる隣接PE間通信は前述の方法だけでは充分ではない。即ち、前述

︑1 ν  

だた

7ドレス・うヮチ・タイミング

(受信側)

ここでは通信先P Eの位置を指定する の方法は語(ワード)を通信の単位としているが、

データ・うヮチ・タイミング 5に示す様なメッセージパッシン

情報(通信先PE番号)も送る必要があるため、図9.

グ的な方法となる。具体的には、通信元P Eは通信先P E番号、通信するデータ数、通信

fL 

(b)転送タイムチャート

時分割転送による PE間通信

ー129‑ 4 

パリティ・うヲチ・タイミング

図9.  するデータをひと固まりのパケットとし、隣接PEへ 転 送 す る ( こ の 転 送 自 体 は (1 )で

これが自 PE番号と異なる場合はさらにその隣接PEに対

‑128‑

この通信は この通知は割り込み等により隣接P EのCPUに伝えられる。通知を受けた隣接P EのC 示した方法)。次に通信元P Eはパケットの転送が終了したことを隣接P Eへ通知する。

P Uは通信先PE番号を調べ、

してこのパケットを転送する。通信先P E番号と自PE番号が一致したとき、

概 要 _{1並 列 度} SMP  l S M Pを 中 継 し て 通 信

中 継 (PE → SMP~ PE;  制 御PEはバイパス〉 2 

制 御PE 通 信 デ ー タ を 制 御 PEに 上 げ ， 同

中 継 ア レ イ 内 を 中 継 し 相 手 P Eに 通 信 max 

N 

c 

n

^{苛c +2} 

(PE→ 制 御PE→・・→制御PE→PE) P E  P Eア レ イ 内 の 他 の P Eを 中 継 し

中 継 通 信 ( PE→PE→・・・・→PE) max 

N 

J寸す

9.  3.  2 異種階層開通信 表 g. 2  遠 隔PE間通信モード

完了する。

なお転送の終了の通知は、図 9. 4の制御コードの中に通常のメモリアクセスと区別す る情報を埋め込むこと(制御コマンドとする〉により隣接PEへ伝えることができる。

又 、 表 9. 2の各種通信モードは対象とする問題で発生する PE開通信分布にあわせ使 い分ければよい。例えば、遠隔PE間通信の発生頻度が極めて少ない場合にはSMP中継 が、これが比較的多い場合には制御PE中継が、比較的近くのPEとの通信が多い場合は

PE中継がそれぞれ有利になる。

N  P E数 Nc 制 御 P E数 ( 1 )上位PE一下位PE間通信

これも図9. 3のように下位PEのメモリが写像されたアドレス空間をアクセスするこ とにより実現される。制御PEをバイパスすればSMPからPEへの直接通信も可能であ

メモり る。

上 位PEから全下位PEへの通信(放送と呼ばれる)は、図9. 6 (a)のようにRe

タ} ア

通 信 データ

PE 

⑥トリガ

u ^{￨ ⑤}

^WRITE 

P E 

I 

②トリガ ③割り込み メモリ

① WRITE 

I 

司通信

④ READ  データ

上 位PE  _{上 位PE} 

通 信 元PE  通信データ

通 信 先PE  番 号 データ数

Ack信 号 Req 信 号 Ack信 号 Req信 号 Wi red  AND" 

d ミ

下 位PE _{下 位}PE 

(a)全PEへの通信 _(b)特定PEへの通信 図9. 5  中継による遠隔PE開通信法

図g. 6  _{上 位}PEから下位PEへのPE間通信制御

q信号を全下位P Eへ送出し、それら全てからのAck信号を受け、図 g. 4の転送手順 により実現される。当然、この通信は書き込みのみである。

一方、上位P Eから特定の下位 P Eへの通信は、通信に先立ち通信先 P Eとの問にチャ ネルを設定する必要がある。これは図 9. 6 (b) のように、通信先 P Eのみを選択状態 とし、非選択のP Eは常にAck信号を送出している状態とすることにより実現される。

このチャネル設定は図 g. 4の制御コードを用いて行えるが、この解除についてはそれ専 用の制御線を設ける必要がある。非選択のP Eへは知何なる情報も送れないからである。

文、上位P E ‑下 位 P E聞の接続にはパスを用いるが、下位 P E数が多い場合には図9 7のようにパスを階層化する必要がある。このときパス聞を接続する回路の方向制御が 必要になるが、これは同図に示すように下位P EのAck信号を利用して実現できる。

( 2 )下位P E一上位 P E間通信

この通信を、下位P Eによる上位 P Eのメモリへのアクセスで実現するには、下位 P E

‑上位P E聞のパスにアービタが必要になり、この設置場所が問題になる。従って図 9.

デス

く Ack信号

バス

図9. 7  ^{パス接続の階層化}

‑132‑

8のように、下位P Eは上位 P Eに対して通信要求を発し、上位 P Eが要求元 P E番号を 検出しマスタ P Eとなり、表 9. 1に示したメモリアクセス(読出し)を行うことにより 実現する。具体的には、下位P Eは通信要求を発出し(専用の制御線による)、上位 P E はこれを検出し承認信号を下位P Eへ送出する。承認信号は下位 P E聞に伝播され、自 P Eが通信要求を発出していない場合は次の P Eに伝えられる。通信要求を発出した P Eは 承認信号を受け、自 P E番号を上位 P Eへ送出し、承認信号の伝播を打ち切る。上位 P E

はこのP E番号をもとに、下位 P Eのメモリの読み書きを行うことにより、この通信を実 現する。

9.  3.  3 デッドロックの防止

デッドロックとは、タスクをA，B 、資源をa，bとするとき、タスクAが資源aを確 保しながら資源bを要求し、タスク Bが資源bを確保しながら資源aを要求しているとき、

タスクA，Bがともに永久に処理を進められない状態に陥ることをいう。

P E間通信を実現する場合にもこれについて充分注意する必要がある。図9. 9にデッ ドロックの例を示す。 PE 0 がPE Iのメモリ

M

1を読み出しにいき、 PE IがPE 0 の メモリMoを読み出しにいった場合である。メモリへのアクセスの問、 PE ⁰ が自らの出 力バッファOBo，P E1の入力バッファ 1B Iを確保し(アドレス送出に必要)、 P E

i が自らの出力バッファ O B1，PEo の入力バッファ 1B 0 を確保しているとすると、

両P Eともこれらバッファが使えないためメモリの読み出し結果を返送できなくなってし まう。これを防止するには、必要がなくなり次第資源を直ちに開放できる様な構成・制御 が必要になる。この例では、 P E開通信においてアドレスが自 P Eの出力バッファから他 のP Eの入力ノくッファに移り次第、自 P Eの出力ノくッファを開放するようにすればよい。

文、図9. 9の様に資源(この場合バッファ)の数を要求源(この場合CP U)の数より 多くしておく必要がある。資源の開放のため必要な条件である。

‑133‑

←  ④P E番 号

②ワイヤードオア線

①要求発生

図 9. 8  下位 PEから上位 P Eへの P E間通信制御手順

P E

。

P E I 

18:  入力バッファ 08:出力バッファ M:メモリ

図9. 9  P E開通信でのデッドロック

9 ̲  4  P E医男医司其尽マミ去

並列計算機では各 P Eに割り当てられた処理が全く独立でない限り、所望の処理手I}頂を 維持し、あるいは処理の歩調をとるため周期が必要となる。この同期には、隣接する P E 間での同期と多数の P E間での同期があり、前者はある P Eが処理したデータを隣接 P E が使用する場合等に、後者は全 P Eの処理の終了を待って、次の処理に一斉に移行する場 合等に用いられる。

( 1 )隣接 P E間同期

隣接 P Eを図 9. 3の様に共有メモリで結合するため、フラグ、セマフォ等の共有変数 の設定、参照による同期が可能である。又、制御用データ(後述)を送り隣接 P Eに割り 込みを発生させることにより周期をとることも可能である〈図9. 1 0)。

( 2 )多数 P E間同期

上位階層の P Eからの害'1り込みやルックインによっても実現可能であるが、大規模シス テムでは全 P E同期の場合の周期時間が大きくなる問題がある。従って、ここではハード ウェアによる実現法を図9. 1 1 に示す。同図に示す様に、全 P Eは特定メモリアドレス へのアクセスにより周期信号を発生させ、各 P Eからの同期信号との一致結果をメモリか らの応答信号 (Ready信号?としてCPUに返すことにより実現する。これにより、 lμs  以下の全 P E同期が可能となる。

又、認識処理、辞書検索処理等において、多階層接続した P E群へデータを害Ijり付けて 階層的に記述し処理する場合、特定階層内での独立同期が必要になると考えられる。そこ で、図 9. 1 2に示すような階層化周期機構を提案する。各 P Eには周期パタンレジスタ とその各ビットと対応する同期マスクレジスタ (M) を設け、 Mの内容により下位 P Eか らの同期信号(全同期ノぐタンレジスタのAND)をビット毎に制御する。同期は自 P Eに 入力される同期信号と自 P Eの同期レジスタの内容が一致したときにとられる。具体的に は同図 (a)のように、 M=lの場合には同期信号の対応するビットをその階層で折り返 し、 M = Oの場合にはその上の階層に伝達する。これにより、同図 (b) のような、柔軟 な同期機能が実現される(各階層の P Eの同期マスクレジスタは同図の右のように設定さ れているとする)。この場合、 3ピットの同期ノfタンで3種の同期を実現しており、周期

フラグ

/二9.~ 1 

， 

P E 

PEn 

P E 2  P E 1 

PE 

メモリ

ready 信号

致 回 路

￨処理 l

通常のメモリ Wr ite 

a)プラグ参照による同期

図9. 1 1  _{高速周期機構}

P E  P E 

割込み発生用 制御データ Wr i te 

パタンlの場合はC階層の同期マスクレジスタの対応するビットが 1"になっているた

図9. 1 0  隣接PE間同期

め、同期信号はC階層で折り返され、 C階層の PEの下位に位置するD階層のPE群間で 同期がとられる。同期ノ守タン 2の場合はB階層の同期マスクレジスタの対応するビットが 1 "になっているため、同期信号は B階層で折り返され、 B階層のPEの下位に位置す るD階層のPE群間で同期がとられる。同期パタン4の場合は同期信号はA階層で折り返 され、 D層の全PEで同期がとられることになる。又、全階層の全PE群問での周期は、

まず同期ノマタン lでC階層のPEの下位に位置するD階層のPE群間で同期とり、次にC

階層の同期マスクレジスタを全て 1"とし、同期ノ守タン2又は周期ノぞタン4でB階層の

PEの下位に位置するC階層のPE群間で同期とり、この手IJ慎を最上位の階層まで繰り返 すことにより実現される。即ち、同一階層内の部分的な同期から全階層にわたる全体的な 同期まで柔軟な同期機能が実現される。

なお、これらの同期信号の伝播にはPE間通信用のリンクは利用できず、専用の信号線 が必要である。

b)割込みによる同期

‑136‑ ‑137‑

/ 

~

上 位PE

￨ M = l 1

^吟

I M = O   I

^吟

/ 

同期パターン レジスタ 下位PE

( a )同期マスクピットによる同期パターンの伝播制御

A 階層

B階層

C階層

Ds'皆層

同期パタン 1Io I 0 I 1￨吟

同期パタン 2Io I 1 I 0I~

同期パタン 4I1  I 0 I 0￨時

D階層部分同期 (C階層の下位) D階層部分間期 (8階層の下位) D 階層全 PE周期

( b )各種階層での同期の実現例

図9.

， 

^{2  階層化同期機構}

。

ヒ

j J

￨1 

I 

¹ 

I 

¹ 

I 

￨1 

I 

1 

I 

￨o 

I 

⁰ 

  I  ' l

。

:自 P Eで折返し :上位P Eへ伝搬

9  5  τフ ォー一一ノレ ト ト ^しノそラ

ニ/

トキ鳶尾文

2次元n+ 1予備によるフォールトトレラント構成は、下位の P Eアレイのみに適用す る。以下、その理由、適用単位、 P E内のバイパス法、 MTTF評価例について述べる。

( 1 )制御P Eアレイのフォールトトレラント化

2次元n

+ 

1予備では 6章で述べたように、 MTTFをN1/2 

( N   :  P  E

数)倍程度向 上できる(図6. 2参照)。即ち、これを適用したP Eアレイの等価的な故障率はもとの 約 1/ N  1/2 に減少するため、 N1/2 個程度のPEからなる制御PEアレイの故障率と同 程度になる。従って、 MTTF向上の観点からは制御P Eアレイもフォールトトレラント 化した方が良いが、 これに2次元 n

+ 

1予備を適用すると下位PEアレイとの接続制御が 複雑化する問題がある。具体的には、制御P Eアレイ内については6章で述べた切替え制 御法がそのまま利用できるが、下位PEアレイとの間ではこれを結合したパスをどの制御

PEに接続するかの制御が必要になり、その制御回路を制御PEアレイ‑下位PEアレイ 聞に設けるか、あるいはこのパスを結合の可能性のある全制御PEに接続しておき制御P E内でこの制御を行わせる必要がある。 これは 2次元 n

+ 

1予備でなく、 2重化等の他の フォールトトレラント構成の場合でも基本的に同様である。

従って、 フォールトトレラント化した場合のMTTFの向上効果は前述の説明から最大 約 2倍となるが、 この接続制御の複雑化をさけるため制御 P Eアレイのフォールトトレラ

ント化は行わないこととする。

( 2 ) _{2次元 n}

+ 

1予備の適用単位

l個の制御PEに結合される下位のPE群、あるいはそれ以下の PE群を単位に適用す る。 これ以上のPE群 を 単 位 と す る と (1 )の接続制御の複雑化の問題が生じるためであ る。 なお、現実的には l枚のボードに実装できるP E群を単位とすることが考えられる。

( 3 ) PE内のバイパス法

6章で提案した 2次元 n

+ 

1予備ではPE内のバイパスが必要となる。 これは、インタ フェース部を図9. 1 3のように構成することにより容易に実現できる(バイパス回路は 1 "でオン)。同図からわかるように、信号はP Eの入口で直ちに折り返しかっ通過す

= f 了

^R R' dt  _( 9 . 

MTTF 

N/n^z 

(l‑R，) J 

(n + 1 ) 

+ 

n 

， ‑ R

， 

 

R  R， 

剛 ︑

.FA 

R' 

一 一

戸 ﹄

W  ここで、 Nc 制御PE数

︑1afvi 

'EEA 

︐ ︐ ︐ ︑ ︑

肉H

FA 

+ (n+1)  r n 

  ， +

S  RI 

(え:PEの故障率=

(‑).t)  r = exp 

n = N 1/4 

1 4に、 Nc = N 1/2 t 

図9.

PE毎に 2重化した場合〈破線)と比較して示す。同図か

1000fit)のときの評価例を、

2重化以上の効果が 2重化の約1/4)で，

n=8のとき，

ら、本方式は少ない冗長度(例.

バイパス回路

入力パッフ

ア

" 

4.︐ 

••

 

出力パッフ

あることがわかる。又、 4096P Eと10 ³ 以上の高並列時でもMTTFは約 l年となり、

ア

冗長化しない場合に対し、約50倍の高信頼化が達成される。

PE 

¥ 、 え

D U ￨ / ¥ ¥ ¥・・

(hours) 

10⁵ 

10' 

Hh

ト ト 三

P E内で・のバイパス法 1 3 

図9.

ノ な

A 

Nc=yN=n² 

PE f a i I u r e r a t e  :10³fit 

10³ 

10² 

この部分の故障により 2次元n+ 1予備での切替え が不能になる可能性は極めて少ないと言える。

る回路も単純でその量も少ないため、

10⁴  10³ 

階層化2次元アレイ計算機のMTTF

‑141‑ 10² 

Number of  PEs  N 

1 4  図9.

10  (4) MTTF評価例

下位PEアレイのみに2次元n+ 1予備を適用した場合の、階層化2次元アレイ計算機

レイ、

rはそれぞれ PEアレイ、制御 P Eア ここではSMPはシステム規模により適用装置が

‑140‑ R' 、 ここでR、 PEの信頼度函数である。なお，

異なるため除いて考えている。

のMTTFは以下で与えられる。

9 ̲  6  音区タラ言式イ乍柊虫色 " H A P  3 2 / 8 "  

これまで述べてきたPE間通信法、 PE間同期法を適用した階層化2次元アレイ計算機 の部分試作機 (HAP3 2/8)を制作した。本節では主にそのPE構成について中心に のべる。

9.  6.  1 全体構成

ホスト計算機、 2x 4の制御PEアレイ、 4x 8のPEアレイから成る(図 9. 1 5)。 全ての制御PEはホスト計算機にパス接続され、又、 4個の PEとパス接続される。ホス

ト計算機としてはNEC社のパソコンPC 9 8を用いた。図9. 1 6に装置の外観、図9 1 7に制御PEボード及びPEボードを示す。各ボードは制御PE、PEをそれぞれ2 個、 4個ずつ実装する。

なお、本装置は小規模であるため元長構成は適用していないが、次に述べるPEには6 章のフォールトトレラント構成を実現するための全機能を収容している。

9.  6.  2  PEの構成

前述したように、高並列化にはLS1化による PEの小型化が必要となるがI2 0)、経済 性、開発期間の短縮、既存ソフトウェア(コンパイラ等)の利用の観点から市販のマイク

ロプロセッサ (μP)を活用し、 PE間結合系等並列計算機固有の部分についてのみ専用

LS1化を図ることとした。又、 LS 1開発品種の削減さらには 3階層以上の多階層構成 をも意識し、 PEと制御PEを同一構成とした。

図9. 1 8にPEの構成イメージ、図 9. 1 9に詳細構成、表9. 3に主な機能を示す。

CPU 、AP U (浮動少数点演算ユニット)、メモリ以外の全ての回路はMCU (メモリ 制御ユニット)、 CC U (通信制御ユニット)と呼ぶ2個のゲートアレイに収容される。

PEは基本的には32ビットのマイクロコンビュータであり、 INTEL社の80386， 80387をそれぞれCPU，APUとして用いている。又、メモリ容量は 4MBである。

PE  Ar r^eJy 

Cmtrol  P E Arr町

図9.15 HAP32/8の構成

制 御PEボード

(a) 

一 一

一

一 一

一 一

一

HAP 32/8 

1 6  図9.

n c  

nt  

︑AMps 

aA H 

HHH 

P Eボード

制 御PEボード及びPEボード

ー l~S-

1 J   sn u 

ffh︑

1 7  図9.

ー1~ ")‑

ZO

﹁ 同 才 勺m 2 0 ω

同 勺

m﹁020﹁勺一川

ω o c H

JT 勺m O白才ェ↑

﹃ 勺m

図9.

間クEン

DE

HJ  

可I

ll

i‑

‑p

il

li‑

‑1

1J

m ω ω

叶 可 問

CCUの機能分担

ノ

PEの内部構成とMCU，

守 人

‑

nk d

一

‑ 一

u‑工

円 ︒

一可J一.︐B‑

hu

‑

‑

+ L

‑ V J

e ll

一

JT

一

u u

‑

﹃ ︐

A司M川一dハ

MEM 

1 9 

，‑‑.、c ) 三::::(0

C コ

ー ‑ ( 0 rl‑ー 可 ーーω rn 

C ""'0  (f)  C 

ー目、

〈ごてコ三:::0 

け1(f) 

1<1> 

Gコ

C 0:コ

(f)  C 

(f)  (0  rl‑

() 

、‑‑"

図

U J  

可mS誠

司沖 よ Xl wu

co 

表 9. 3  P Eの 主 な 機 能

項 目 機 有E 概 要

デ ー タ 処 理 ‑ 一 般 の デ ー タ 処 理 と 高 速 浮 動 少 数 点 演 算 処 理

‑隣接PEの メ モ リ の Read/Write

‑隣接PEへ の 割 込 み ( 同 期 で も 利 用 ) PE間 通 信 ‑全下位PEのメモリに対する同時¥Vri t e 

‑特定下位PEと の 通 信 チ ャ ネ ル 設 定 と そ のPEの メ モ リ の Read/Write

‑上位PEに 対 す る 通 信 要 求 の 発 生

‑通信元下位PE番 号 の 検 出

同 期 ‑周期ノそタンの発生

‑同期ノそタンの上位PEへの伝達および マスク

‑全PE/個 別PEの ス タ ー ト 、 ス ト ッ プ 、 リ セ ッ ト 下 位PE群 制 御 ‑全P E /個 別PEへ の 割 込 み

‑全P E /^{個 別}PEの バ イ パ ス 指 示 上 位PEへ の 通 知 ‑上位PEに 対 す る 割 込 み 発 生

‑上位PEが Read/Writeで き る メ イ ル ボ ッ ク ス 具 備

‑メモリ及びPE間 デ ー タ 転 送 の パ リ テ ィ チ ェ ッ ク フォーノレトトレラント ‑隣接PEと の 冗 長 構 成 用 イ ン タ フ ェ ー ス 具 備

‑ 自 律 的 切 り 替 え 制 御 機 構 と 診 断 補 助 機 構

( 1 ) デ ー タ 処 理 系

デ ー タ 処 理 系 はCPU，APU， M E M， M C Uか ら 構 成 さ れ る ( 図9. 1 9の 左 半 分

)  0  M C  U はCPU，APUか ら の メ モ リ ア ク セ ス と PE開 通 信 に よ る メ モ リ ア ク セ ス と の 競 合 処 理 等 を 行 う 。 こ のLS 1は、各種のμP， メ モ リ デ バ イ ス に よ り い ろ い ろ な サ イ ズのPEが 構 成 で き る よ う に 、 具 体 的 に はCPU^，APU^， M E M^として表 9.4の す べ て の 組 合 せ が 可 能 と な る よ う に 構 成 し て い る (HAP3 2/8はタイプ1lI)。

M E Mの構成としては、 PEの 性 能 向 上 の 観 点 か ら は デ ー タ ・ プ ロ グ ラ ム 蓄 積 用 と PE 間 通 信 用 を 独 立 に 設 け る 多 パ ン ク 構 成 が 好 ま し い が 、 こ こ で は 、 イ ) 多 パ ン ク 構 成 は 小 型 化 に 不 利 、 ロ ) 1パ ン ク 構 成 で は 通 信 用 メ モ リ エ リ ア をPE内 の 全 メ モ リ エ リ ア に 設 定 可 能 、 等 を 考 慮 し lパ ン ク 構 成 と し た 。 又 、 メ モ リ 素 子 と し て は 小 型 化 を 最 重 視 しDRAM を用いた。

‑148‑

表 9. 4  _{構 成 可 能 な}PEの タ イ プ と そ の 主 な 仕 様

タイプ I(I6ピ7ト) タイプII06ピ7ト) 7イプ1lI(32ピ汁)

適 用CPU/APU 80186 /8087  80286/80287  80386/80387 

256Khプ 256K '  5" 12KB  512K '"  1MB  512K ' "1MB  M E M  

lMhプ 一 2MB  2 ^{' v}  4MB 

PE間 階 層 内 4bitsX(4+2予備):2MB/S 

インタ7エース

階 層 間 4bitsx2  : 2MB/S 

( 2 ) 通 信 処 理 系

PE間結合用・の イ ン タ フ ェ ー ス 回 路 ( リ ン ク ) 、 各 種 制 御 回 路 か ら な り 、 全 てCCUに 収 容 さ れ る く 図9. 1 9^{の右半分)。}

リンクは全部で8組 あ り 、 こ の う ち 2組 は 階 層 間 結 合 用 (1 : n接続)のパスであり、

残 り の 6組 が 隣 接 結 合 用 (1 接 続 ) で あ る 。 隣 接 結 合 用 の う ち 2組 は フ ォ ー ル ト ト レ ラ ン ト 構 成 用 で あ る 。 こ れ ら の リ ン ク は 汎 用 的 に 構 成 さ れ て い る た め 、 本PEはトリー、

ノ¥イパキューブ等の 2次元アレイ以外の並列計算機にも適用できる。

こ の リ ン ク に よ る 通 信 は 図9. 4に示したように時分割非同期転送化を図り、 lリンク 当 た り の デ ー タ 線 を 4本としている。文、この通信には、 13回 転 送 ( 制 御 コ ー ド 1 ， アドレス 7，データ 4，パリティ 1)と 9回 転 送 ( 制 御 コ ー ド 1， ア ド レ ス 7，  パ リ テ ィ ま た は 、 制 御 コ ー ド 1， デ ー タ :4， ダ ミ ー 3，パリティ 1)の 2種 類 が あ る 。 前 者 は デ ー タ 書 き 込 み 用 に 用 い 、 後 者 は デ ー タ 読 み 出 し 要 求 と そ の 返 送 デ ー タ 転送用に用いる。なお、 PE間 通 信 エ ラ ー の 検 出 の た め 、 通 信 毎 に パ リ テ ィ チ ェ ッ ク を 行 い、エラーの場合にはマスク不可の割り込みを発生させる。

‑149‑

g.  6.  3 制御法

階層化アレイ構成でのPEは、一般の 2次元アレイ型において必要となる、 アレイ内の

PE間通信・ 同期等に関する制御機能の他に、階層間の通信・周期、下位PEの起動、停 止等に関する制御機能が必要となる(表g. 3参照)⁰  HAP3 2/8ではこれらの制御 は、プログラム記述上はその開発の容易化のため l命令で記述可能とし(制御コマンドと して表g. 5のようにサブルーチン化)、実行上は高速化のためハードウ ェアで実現して いる。

表 g. 6に基本的な制御構造を示す。全ての制御は同表における動作を、制御側PEで 上から下へ、被制御側PEで下から上へ順次行うことにより実現される。具体的には、同 表のように制御側PE (SMP、制御PEを含む〉の全ての制御要求は、サブルーチンコ

表 9. 5  ハードウヱア制御ルーチンライブラリ例

ノレーチン名 機 能 概 要 S PERESET  全PEのリセット

HAPLOAD  全PEへのプログラム転送 S SELLOAD  ^{特 定}PEへのプログラム転送

PESTART  PEプログラムの起動 PESTOP  PEプログラムの停止

一PECONT  PEプログラムの再起動 S BRDCAST  全PEへの同一データ転送

一PESEND  特定PEべのデータ転送

一GETDATA  特 定PEからのデータ収集(ファイル〉

GETMEM  ^{特 定}PEからのデータ収集(メモリ) 一SYNC  ホスト‑PE間同期

S _一LOOKIN  特定PEの状態レジスタの監視 S BYPSON  バイパスモードの設定

S BYPSOFF  バイパスモードの解除

表 9. 6  _{制御階層構造}

実現機能 制御側PE _被制御側PE

告IJ御要求 PE起動 周期 要求検出 ソフトウェア サブルーチンコール 割込み処理 次処理 割込み処理

CPU動 作 メモ リ擬似アクセス 割込み 次命令実行 割込み (次命令/停止)

制御専用回路 アドレス/データ 割込み検出 レディ制御 割込みベクタ デコード

物理リンク データ線

l

^{個別線 データ線} 個別線

ールの形で行われ、これはCPU動作における疑似メモリアクセスとなる。即ち、図 g. 2 0に示したアドレス空間におけるシステム領域をアクセスする。このアクセス情報をも とに制御側PE内の専用ハードウェアは制御の種類の識別と制御情報の作成を行い、 告IJ御 情報は物理リンクであるデータ線 (PE間通信用)あるいは個別線により被制御PEに伝 えられる。個別線はインタフェース線の削減のため、データ線の利用が不可能なものに対 してのみ設けている。被制御側PEでは、その制御情報に従い、割り込みベクタの生成、

割り込み動作、害IJり込み処理を行い、各種制御動作が実現される。

ただし、高速性が要求される制御、例えばPE群の同期(この場合、制御側PEは被制 御側PEでもある)については、メモリの応答信号 (CPUへの Ready信号)を図 9. 1 1 

のように制御して実現している。

9.  6.  4 プログラミングと実行

HAP32/8では、並列構造を意識したプログラミングが必要であり、ホスト計算機 用と PE用の両方のプログラムを作成する必要がある。前者ではプログラムロードやPE

群の制御について、後者では並列アルゴリズムを中心に記述する。なお、制御PEにPE

間通信や同期以外の一般的な処理を害11り付ける場合には、当然そのためのプログラム作製 も必要である。

制 御PEおよびPEで実行するプログラムはホスト計算機上でC言語で開発し、コンパ イルした後オブジェクト形式でそれらPEにファイル転送する。各PEには予めモニタプ

FFFFFFFF 

システム領域 EOOOOOOO 

下位PEメモリ COOOOOOO 

West  PEメモリ AOOOOOOO 

South PEメモリ 80000000 

East  PEメモリ 60000000 

North PEメモリ 40000000 

20000000 

自PEメモリ 00000000 

図9. 2 0 

各種コマンド

下位PE割り込み

メールボックス アクセス

レ~

^{割り込みベクタ}

アドレス空間の利用法 ‑

FFFFD 1 00 

FFFFOOOO 

FFFEOOOO 

FFFDOOOO 

FFFCOOOO  400 

。

ログラムをロードしておき、上位からの起動指示(下位

PE

へ対する割り込みにより実現 される)により転送されたオブジェクトプログラムを実行する。これらプログラムのロー デイングは新たに開発したプログラムローダが行う。又、モニタプログラムは各種割り込 み処理や

PE

の初期設定

( P E

の番号付け等)を行う。

又、各

PE

内ではプログラムは

32GB

のアドレス空間(図g.

2  0 )

をアクセスでき るようにプロテクトモードで実行される。図 9. 2 1 に制御コマンドの使用法に着目した プログラムの記述例を示す。

このプログラムでは、

①ホスト計算機から

PE

へのプログラムロード

②

PE

の起動

(HOL 

0状態の解除)

③ホストの全

PE

の同期確認

(PE‑WAIT

状態の検出)

④初期データの放送

‑152‑

(HOST ProgramJ 

(PE  P rog r amJ  procedure HOST: 

begin 

CProgram Load) 

S

一

hapload( PE"); 

タ procedure PE; 

CPE Start) 

s̲PE start:  →begin 

s̲sync(PE̲init);  (Synchronization by PEs)  [Initial izationJ 

̲syncCend̲̲init); 

forN=1to pe‑numberdo(In i t i a￨Data supply)[Wa i t]  s̲pesend( PE̲FILE  [NJ"); 

(Synchronization by  HOST)  s̲pecont; 

(Synchronization by PEs)  s̲sync(PE̲̲end); モ

for  N=l  to  pe̲̲number  do  (Result  Col lection)  s̲getdata( PE̲̲F I LE  [N]"); モ

end 

ぅ [ProcessJ

sync(n);(lnter‑PE Synchronization)  [ProcessJ 

s̲sync( end); 

end 

図9. 2 1 

HAP

の並列処理プログラム記述例

⑤ホストからの全

PE

の起動 (VI

A  r  T

の状態の解除、

PE

は処理実行)

⑤ホストの全

PE

プログラムの終了状態検出

⑦

PE

からのプログラム実行結果の読出し(遂次)

を実行する。なお、

PE

に収容される実際に問題を解くための並列処理プログラムは、⑤

⑤の間で走行する。

‑153‑

9 ̲  7  _手吉言言

高P E間通信性能とフォールトトレラ ント性を両立させた高並列計算機の構成法の確立 を目指し、階層化2次元アレイ計算機ハードウェアの具体設計を行った。本アーキテクチ ャは、 2次元アレイ型を階層構造化したもので、並列アルゴリズムを実行する P Eアレイ の上位に小規模な制御用のP Eアレイを設ける構成である。

本章では主に階層構造化に伴い特殊化する部分に着目して、必要となるP E間通信・同 期の制御法・実現法、フォールトトレラント化法について述べ、又、これらを適用した部 分試作機HAP32/8の構成を示し、階層化2次元アレイ計算機ハードウェアの設計指 針を与えた。

具体的には、 P E間通信については同一階層内、異種階層聞の通信制御法とそれらの実 現に共通的に利用できる時分割非同期転送法を、 PE間周期についてはρオーダ以下で全 P Eの同期を実現する高速同期法と階層内あるいは階層間の部分的かっ柔軟な同期を可能 とする周期制御法を提案した。又、フォールトトレラント化については下位PEアレイの みに 2次元n

+ 

1予備を適用した場合でも、大幅な高信頼化が達成されること等を明らか にしfこ。

部分試作機HAP32/8については、主に各階層で共通に使用できる PEの構成につ いて示した。本装置は 32個のPEと8個の制御PEからなり、それら PEは、汎用のマ イクロプロセッサ， DRAM素子，新たに開発した 2個のLS 1のみで構成できる LS 1  化P Eである。本装置は、今後並列処理アルゴリズムの開発とそれを通した階層化アレイ の評価に利用してし1く予定である。

三事 1 0 宝章 子長吉言命

高並列計算機実現上の主要課題として、 PE開通信性能の向上法と高信頼化構成法を採 り上げ、ハードウェアアーキテクチャの観点から論じた。

具体的には、 10³ "'‑'10⁴ あるいはそれ以上の高並列化を想定し、これに比較的適合 する 2次元アレイ型およびハイパキュープ型をベースに、 PE間距離の削減ひいては高P

E間通信性能の実現を可能とする高並列アーキテクチャおよびこれらネットワークトポロ ジに適したフォールトトレラント構成を提案した。又、 2次元アレイ型あるいはハイパキ ューブ型以上の可能性を持つ新たな高並列向きネットワークの提案を行った。さらに、 高 P E開通信性能とフォールトトレラント性の両立を目指した、階層化2次元アレイ計算機 のハードウェア設計例を示した。

( 1 )高PE開通信性能を実現する高並列アーキテクチャの提案

ベースとする 2次元アレイ型あるいはハイパキューブ型のネットワークトポロジの 原型を崩さないことを前提に、 り〈イパス路の付加による P E間距離の削減"を基本 的考えとする改良型アーキテクチャを提案し、これらがPE間通信性能を大幅に向上 できることを解析的に明らかにした。

2 (欠元アレイ型の改良型アーキテクチャは、本来の PEアレイの上位に小規模なP Eアレイを付加した階層化アレイアーキテクチャであり、一般の 2次元アレイ型に対 し平均通信遅延(ある時点で発生した通信を全て処理する時間と定義)を最大 1桁近 く短縮できる。階層化によるハードウェア増以上の効果が期待できるアーキテクチャ と言えよう。

ハイパキューブ型の改良型アーキテクチャは、符号理論を利用したP E群の分割と パス結合の付加に基づ く構成であり、如何なるサイズのハイパキューブにおいても最 大PE間距離(直径)を2に短縮できる。さらに、パスの数だけノ〈イパス通信の並列 度が得られるため、一般のハイパキューブ型だけでなくこれに単一のパスを付加した アーキテクチャに対しても平均通信遅延の短縮が可能となる。本構成はP E当たり l 本のリンクを増加するだけで実現でき、文、パスをプログラムロードや初期データ供 給に利用できるため極めて実際的な解と言える。

( 2 )高並列計算機への冗長構成適用の定量的評価

高並列計算機の高信頼化では、 MTTF向上効果の高い冗長構成法およびシステム 自動再構成法とその際の診断の並列化法が基本的な課題となることを示すとともに、

一般的な冗長構成である多重化， n + 1予備をPE毎に適用した場合、 MTTFをO (N¹/2

)倍 (N: P E数〉程度向上できることを解析的に明らかにした。又、 PE内へ の効果的な誤り訂正回路の設置法とその適用によるMTTF向上効果を明らかにした。

さらに、 PEの診断法として、直接結合されたPEを利用し多数決でその良否を判断 する並列診断法 (NV診断法)を提案した。

( 3 )ネットワークの特徴を生かしたフォールトトレラント構成の提案

並列計算機では、故障PEを論理的あるいは物理的に切離し規模を縮小して動作を 継続する、いわゆる "gracefuldegradation"が可能であるが、本論文では、 PE故 障時にもとの規模のシステムを再構成可能なフォールトトレラント構成を提案した。

2次元アレイ型については、その平面的な特徴を生かした 2次元n+ 1予備と呼ぶ 構成とこれを実現する PE間結合法 (rX‑NET)を提案した。これは i行 l列の 予備PEを設けn+ 1予備を階層的に適用したもので、小さい冗長度にもかかわらず 2重化以上のMTTF向上度が得られ、無保守化システム実現の可能性を持つ。さら に、従来提案されてきた構成に比べ、冗長度が小さい、 PE間結合が単純、切替え制 御が容易等の特徴を有し、 VLSI化の際の欠陥救済手法としても適用可能である。

ハイパキューブ型については、切替え用のハードウェアを不要としかっ如何なるサ イズのハイパキュープにも適用可能な構成を提案した。これは、全PEを距離が大き なPE同士の集合に分割し、これらをパスを介し予備PEと接続することによりベー スとなるフォールトトレラントなハイパキュープを構成し、次にこれをグラフの積を 利用して拡大するものである。従来、ハイパキュープは結合が密なため汎用的なフォ ールトトレラント構成は得られていなかったが、本構成はこれを初めてかつスイッチ

レスで可能としたものである。

( 4 )接続数、直径が小さくかっ高信頼な高並列向きネットワークの提案

高並列計算機では、実装の各レベルで接続処理が問題になるため、直径が小さいだ

‑156‑

けでなく接続数 (PE当たりのリンク数〉が小さいネットワークが要求される。又、

PE間の結合が均一で通信が特定のPEに集中しない対称形であることも望まれる。

本論文では、これら要求を満たし接続数、直径をハイパキューブのそれらの約 1/2 に削減できるネットワークCCTcube(Cornplete‑Connectionof  Torus‑Hypercube)を提 案した。本ネットワークは、バイパス用リンクを付加したノ¥イパキューブをサブネッ

トとし、これを階層的・再帰的に完全結合するものである。これまでに提案されてき た代表的なネットワークに比べ、接続数、直径を共に大幅に削減でき、かっ、 n+1 予備によるフォールトトレラント化も容易に実現でき、高並列化に極めて適したネッ

トワークと言える。

( 5 )高PE間通信性能とフォールトトレラント性を備えた高並列計算機の設計例の提示 高性能・高信頼な高並列計算機の構成技術の確立をめざ し、階層化2次元アレイ計 算機の具体設計を行い、小規模な実験機 (HAP32/8)を試作した。このアーキ テクチャは、 ( 1 )で、述べた階層化アレイ構成であり、並列アルゴリズムを実行する PEアレイの上位に小規模な制御用のPEアレイを設けたものである。

これら設計・試作を通して、階層化で、特に必要となる PE開通信・同期の実現法を 明らかにし、同計算機のハードウェア設計指針を与えた。具体的には、 PE間通信に ついては同一階層内、異種階層聞の通信制御法とそれらの実現に共通的に利用できる 時分割非同期転送法を、 PE間同期についてはρオーダ以下で全PE同期を実現する 高速周期法と階層内あるいは階層間の部分的な同期を可能とする同期制御法を提案し た。

又、 HAP32/8は32個のPEと8個の制御PEからなり、それらPEは、汎 用のマイクロプロセッサ， DRAM素子，新たに開発した 2個のLS 

r

のみで構成で きるLS 

r

化PEである。又、 2次元n+ 1予備によるフォールトトレラント化に必 要な全ての機能を収容している。

本研究では、高信頼・高性能な高並列計算機の実現に向けノ¥ードウェア構成面から幾つ かの提案を行ったが、研究的な試用でなく本当の意味で実用に供していくには、今後次の ような課題を解決していく必要がある。

ー157‑