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

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

Kyushu University Institutional Repository

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

石川, 勉

https://doi.org/10.11501/3052535

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

権利関係：

︒ ω

沼

@ a

玄白

@@

コ

S

︿︿

23

@

R o a ω R n

O

﹃

一 o

コ n o マ

o 一 勺

n 一 見

回 一 c

o O

︼ 面 コ

03

コ0

d e

‑ E

毒

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

m w  

石 川 勉

日 とた

第 l章 序 論

1.  1 研究の目的

1.  2 並列計算機研究の歴史 上 3 研究の動機と主な成果 1.  4 本論文の構成

第2章 並 列 計 算 機 の 結 合 方 式 2.  1 結合方式の分類

2.  2 ネットワーク型結合網の評価パラメータ 2.  3  2次元アレイ結合

2.  4 ハイパキュープ結合

第3章階層化アレイアーキテクチャ・

3.  緒 言 ーー・・・

3.  2 階層化アレイ構成

3.  3 PE間通信性能評価

3.  3.  評価モデル

3.  3.  2 解析方法

3.  3.  3 評価結果

3.  4 ^{一平百一百}

n H u n H U

円/

︼ 円

/︼ 門 ぺ

u p h d F h d

門t t ' I A p h d n h U

円hU

門︐

g門

t ' n H u n u u n H U

円︽

υ円

hu

円乙η乙η

乙 円 /

︼ 円 〆

︼ 円 / 旬 円

〆︼ 円

︑

u

内ぺ

U

円円υ

t u n

べU

円 べu n t u n t U A ω

企

4 4 A 8 H

守

第4章 分割ノくス結合付加型ノ¥イパキューブアーキテクチャ 緒言

4.  2 直径の短縮法

4.  2.  諸定義 ‑・ ・・・・ ・・・・・・・

4.  2.  2 基本構成

4.  2.  3 集合の構成法と直径

4.  2.  4 ハミング符号を用いた直径の短縮 4.  3 任意のハイパキュープでの直径2の実現法 4.  4 遠 隔PE開通信の通信ルート決定法

4.  4.  中継PEの決定法 4.  4.  2 具体例

4.  5 放送への応用 4.  6 評価

4.  6.  直径の短縮効果 4.  6.  2 通信遅延解析評価 4.  7 結言

7.  3.  1 予備PE 1個の 1‑FTi次元キュープ 7.  3.  2 予備PE 2個の 1‑FTi次元キューブ 7.3.3  k‑FTi次元キュープへの拡張 7.  4  グラフの積による k‑FTキュープの拡大 7.  5 必要なハードウェア量とMTTFの向上

円O n o

‑

‑

A斗

A S A

可

F H U

95  98 

句EEム

n H U

‑ ‑  

E g‑ ‑

• •

•

• •

•

•

•

内喝

UF H U

‑ ‑  

•

•

•

•

•

•

₁₀₃ 

106  109  110  110 

q u A 4 τ n u t

‑

‑ i

の/︼

F h d F h d n o

‑

‑ A せ に

. U F U P D o o

‑

‑

‑ i n / M

ウI可I門

i n u n u n u η

乙

F h d

R U F b n U F O P O

円b p O

にu n b

門i勺i勺l

ウ

﹄ ウ

t F i n o o O Q U n O Q u n o n O G d n U Q u n u

‑・・・

7.  6 結言 ・・・・

第8章 超 高 並 列 計 算 機 向 き ネ ッ ト ワ ー ク "CCTcube" 

第5章 高並列計算機の高信頼化に関する一般的考察 8 .  緒言

8.  2  CCTcubeの構成 8.  2.  完全対称型の最大構成 8.  2.  2 フォールトトレラントな構成 8.  3 ルーティング法

8.  4 評価 8.  5 結言

111  111  114  116 

119  121  122  122  124  127  127  131  133  135  139  142  142  142  150  151  154  155  5.  ^緒

5.  2 高信頼化の主要課題 ・・・

5.  3 基本的冗長構成適用による効果

5.  3.  1 多重化、 n+1予備によるMTTFの向上

5.  3.  2 誤り訂正機能の付加の効果

5.  4 ネットワーク型並列計算機の診断法

5.  5 結言 _第9章 階層化2次元アレイ計算機のハードウェア設計例

第6章 2次元アレイ型のフォールトトレラント構成法 9.  1 緒言 ‑・・・ー・・・・・・・・・・・・・・・・

9.  2 システム構成 9.  3  PE間通信法

9.  3.  同一階層内通信 9.  3.  2 異種階層間通信 9.  3.  3 デッドロックの防止 9.  4  PE間同期法

9.  5 フォールトトレラント構成 9.  6 部分試作機 HAP32/8"

9.  6.  1 全体構成

. 

9.  6.  2  PEの構成 9.  6.  3 制御法

9.  6.  4 プログラミングと実行 9.  7 主~・士口至Eコ・宝

第 10章 結 論

6.  1 緒言

6.  2  2次元n

+ 

1予備構成

6.  3  2次元n+ 1予備によるMTTFの向上

6.  4  2次元n

+ 

1予備のためのPE間結合法と切替え制御法

6.  4.  1 PE間結合法 6.  4.  2 切替え制御法

6.  5 システム自動再構成法

6.  5.  1 自動再構成法

6.  .5.  2 無保守化システム実現の可能性 6.  6 結言

第 7章 ハイパキュープのフォールトトレラント構成法 7.  1 緒言

7.  2 諸定義 ・・

7.3  k‑FTi次元キュープの構成法

謝辞 160  _{多手~ 1} ^‑J寺三.^=三=‑ I亨 言 命

献文

161  付 録 l

付 録 2

170 

172  1.  1  石 汗 デEa:>目 白 勺

L S 1技術の急速な発展に支えられ、計算機性能は著しく向上し最近では数GFLOPS (  Floating point  Operation/Second)のスーパコンピュータも出現している。しかし、電子 装置は基本的にはスイッチング素子と配線からなり、配線での速度は光速以上にはなり得 ないため、素子速度が如何に向上しようとも逐次型計算機の性能には限界がある。そこで、

理想的には構成する処理要素 CProcessingElement:  P E)の数に比例した性能が期待で きる並列計算機が注目され、その研究開発が活発化してきている。

さらに近年、高性能かっ安価なマイクロプロセッサが開発されてきており、これを多数 用いることにより、性能向上だけでなく性能価格比の向上も可能になりつつある。即ち、

現在より数桁高い性能を、 10³ ‑‑10.あるいはそれ以上のPEを用いた高並列計算機 により、経済的に実現することが可能になりつつある。

このような高並列計算機では、大多数のPEを休止させること無く動作させる効率的な 並列処理アルゴリズムが重要な課題となるが、これについては一般解は無く、解こうとす

る問題毎に個別に開発する必要がある。一方、システム具体化の視点からは、如何に性能 上、運用上のボトルネック無くこれを構成するかが重要な課題となる。このボトルネック には主要なものとして、 PE間通信に代表される並列化に伴うオーバヘッド(以下、並列 化オーバヘッドと呼ぶ)の増大、大量のハードウェアの使用による信頼性の低下が挙げら れる。

本研究は、高性能かつ高信頼な高並列計算機の実現をノ¥ードウェアアーキテクヂャの観 点から追究する。具体的には、高並列化向きと考えられる 2次元アレイ型とハイパキュー ブ型をベースに、 PE数比例のシステム性能の実現を目指した高PE開通信性能を有する アーキテクチャと PE故障に効果的に対処できるフォールトトレラント構成を考案し、こ れにより、 10³ ‑‑10⁴ PE以上の高並列計算機の実用への道を切り開くことを目的と する。

‑1 4 

1 ̲  2  並 列 計 算 機 研 究 の 歴 史 ャ、の開発が必要となる。

並列処理アルゴリズムとは、解こうとする問題の中から並列性を最大限に引き出せる処 理手法^20・21 )を意味し、これは従来の逐次的なアルゴリズムを並列向きに変更する方向も あるが、むしろ問題の本質をとらえた並列向きの新たなアルゴリズムの探究という方向で 研究が進んでいる。しかし、現在までに得られているのは、科学技術計算や画像処理とい った数値処理用でかつ処理の過程で^Z並列数が一定な、いわゆる静的並列問題²²⁾ に属する ものが殆どである。例えば、連立一次方程式の解法23‑26)、高速 Fourier変換 (FFT)2 7 ‑3 

0)、ソーテイング3I・32 )等である。並列数が時間的に変動し予測がつかない、いわゆる動 的並列問題22 )については、論理シミュレーション33・34 )やプロダクションシステム35 ‑3 

7 )の並列化等に関するいくつかの研究例が有るが、まだまだこれからである。むしろこれ については問題の求解アルゴリズムのレベルでなく、言語のセマンティックスレベルでの 並列性の抽出の方向が主流と言えよう。いずれにしても、現在開発されている並列処理ア ルゴリズムはほんの僅かであり、今後の研究に期待するところが多い。

並列プログラミング言語は、プログラミングの際ユーザが問題に内在する並列性を陽に 記述することにより、効率的な並列性の抽出を達成することを目的としている。これには 並列処理の研究の歴史は長いが、実用を目指し本格化してきたのは1972年にイ リノイ大

学により ILLIAC‑IVが開発されてからと言える。 ILLIAC‑IVI・2)は、 64台のPE (Proces  sing  Element)を2次元アレイ状に結合した、一つの命令で複数のデータを同時に処理す るS1 MD型3)(Single Instruction stream‑Mulitiple Data  stream)の並列計算機であ る。これは性能的には数10MFlops程度で、実用上は失敗と言えるが、 LSIも無い時代 であることを考えると極めて挑戦的であったと言えよう。

その後、 LS 1化時代を迎え、マルチマイクロプロセッサの走りである Cm*りがカー ネギ・メロン大学 (CMU)で作られて以来、複数のプログラムが複数のデータを同時に 処理するマイクロプロセッサベースのMIMD型3)(Multiple  Instruction  stream‑Mult 

iple  Data  stream)の並列計算機の開発が世界的に活発化した。例えば、米国ではBBN

社の8utterfly¥Intel社の PS C 6)、我が国では阪大のLINKS⁷⁾、筑波大の P A X

U 等がある。又、最近では汎用のマイクロプロセッサでなく、専用化したLS 1化PEを 用いたマシンの開発も盛んである。米国では 10 3規模の並列度を持つN‑cube9)が商品 化され、欧州ではInmos社のLS 1化PEであるTransputer^'O)を用いたいくつかのマシ

ンが開発されている。

これらのマシンは、ほとんどが科学技術計算や画像処理と言った数値処理を目的として いるが、最近は知識処理や自然言語処理への適用を目指した記号処理用のマシンの研究も 活発である。記号処理用マシンではそれに適した言語である論理型言語¹¹⁾ あるいは関数 型言語12) を対象とするため、非ノイマン型であるデータフロー型I3) やリダクション型

10が多い。たとえば、前者としてはICOTのPIM‑DI5)、NTTのDHp^S)等が、後者としては 東大のPIE‑II'^{7l、ロンドン大の}ALICEI8)等がある。

従来の手続き型言語から発展したConcurrentPasca138_・39)、Ada40)、

o

c c am 4 1. 4 2)、論 理型言語の流れをくむICOTのGH C (Guarded Horn  C 1 auses) 43・44 、) ConcurrentProlog 

川、並列オブジェクト指向言語のA8CL/146)等がある。他方、並列化コンパイラは、元 来 FORTRAN等の逐次型言語で記述されたプログラムからの並列性の抽出を目的に研究され てきており、最近ではDOループ間あるいはサブルーチン聞の並列性を抽出する研究⁴⁷・⁴

8 )も行われてはいるが、実用的なものはDOループ内を対象としている49‑5110しかし、

並列処理における逐次処理の影響を定式化したアムダールの法則52) からも予想されるよ うに、本論文で対象としている 10 3規模の高並列計算機では、記述されたプログラムの なかから並列性を抽出するというアプローチはかなり難しいと考えられる。即ち、問題か

ら直接並列性を抽出するほうが適切と言えよう。

並列計算機は、ここで挙げた以外にも開発中のものを含めると 100以上あるが19)、本 格的に商業ベースで成功しているのは数少なく、まだ研究段階にあると言えよう。並列計 算機研究の究極的な課題は、 PE数に見合ったシステム性能が安定に得られること"で あり、この実現のためのには、イ)問題に適した効率的な並列処理アルゴリズム、ロ)並 列性を表現し易いプログラミング言語あるいは記述されたプログラムのなかから並列性を 抽出する並列化コンパイラ、ハ〉並列化オーバヘッドが少なく高信頼な並列アーキテクチ

並列アーキテクチャで最も重要なのはPE間の結合方式である。問題が複数のPEに独 立に分割できればPE間相互の通信は不要であるが、一般には相互に関連をもつことが多 くPE間通信は不可欠である。例えば、論理シミュレーションにおいて対象となる回路を 各PEに分割した場合、各PEは自分が担当する回路部分と接続された回路部分を担当す

円/M qu

 

るPEに対して信号の変化を伝える必要があり PE間通信が発生する3 4 1 0 このPE間通 信を高速に処理できないとそれがボトルネックとなり、 PE数に見合ったシステム性能が 得られなくなるため、どの様にPE聞をつなぎどの様に通信するかが重要になってくる。

これは高並列になる程重要になる。

PE間通信の方法には基本的に二つの方式53 )がある。一つは共有メモリを介して通信 する方法であり、もう一つは直接メッセージを伝達する方法である。前者は一般に共有メ モリ方式と呼ばれ、後者はメッセージパッシング方式と呼ばれる。共有メモリ方式ではP E聞の結合は、 PEとメモリ間の結合に置き換えられ、パス、クロスパスイッチ、多段ス イッチ網等で実現される。このうちパスは通信競合によりスループットが限られるため、

又、クロスパスイッチはそのハードウェア量がPE数N対し

o

(N2)となるため、多段スイ ッチ網についての研究が盛んである。多段スイッチ網は基本的にはクロスパスイッチを機 能縮小し簡略化したもので、ここでは、スイッチ網の接続制御法54‑56)や特定のメモリへ のアクセス集中である hotspot^{57• 58)} の処理法等が主な課題となっている。共有メモリ 方式は、すべてのPE間通信が等距離の通信となる利点があるが、通信に局所性が有る場 合にはこれはむしろ欠点となる。

メッセージパッシング方式では、一般にPE聞の結合は l対 lのリンク結合により実現 され、 2次元アレイ、トリーといった比較的単純な結合構成がよく用いられる。これらは、

対象とする問題の通信特性に適合すれば、少ない結合用ハードウェアにもかかわらず高い システム性能を得ることができる。例えば、ポアソン方程式をODD‑EVENSOR法で解く場合 刊 に は 、 全 て の 通 信 は 隣 接PE間で発生し 2次元アレイで充分であり、又、知識処理等 における探索処理や分割統治法では、 トリー状に処理が広がるためトリー結合が適してい る山。しかし、通信の局所性を利用し対象とする問題に専用化するのではなく、もう少 し汎用性を持たせようとするとこれでは充分とは言えない。本論文で提案する階層化アレ イi1)i は、 2次元アレイをベースとした改良型結合方式である。

又、 CosmicCube^S， 62)で初めて具体化されたハイパキューブも、より多くの問題への適 用を狙ったものである。ハイパキューブでは、 PE番号が lビットだけ異なる全てのPE 同士が直接結合され、各PEはPE数N対し最大でも

o

(log2N)回の中継によりどのPE とも通信できる。この強力な結合と短い通信距離の利点から最近特に注目されており、数 少ない商品化された高並列計算機である

N

‑cube⁹⁾ 、コネクションマシン6^3 ) もこの結合 を用いている。しかし、更に高並列化する場合あるいは 1L S 1に多数の PEを収容しょ

うとする場合、 PE当たり

o

(log2N)本のリンクを設けるのは問題として、 Preparataら は

cc 

C (Cube‑Connec t ed‑Cyc 1 e) ⁶⁴⁾ 、HwangらはHypernet 6;;)と呼ぶハイパキュープを 原型とする結合方式を提案している。これらは共に二つの結合方式を階層的にくみあわせ たもので、 CCCはリング結合を一つのノードとみなしこの聞をハイパキューブ状に結合 した構成であり、 Hypernetは、ハイパキュープあるし川まトリー結合を一つのノードとみな しこの聞を完全結合で結んだものである。共にPE当たりのリンク数(接続数と呼ばれる

〉がPE数に依存せず一定でありかっ 3本あるいは数本と少ないが、通信距離はやはりハ イパキューブ以上となる。一方、鈴岡らはノ¥イパキューブ以下の通信距離が得られる、 ba se‑m n‑cube66)と呼ぶ結合方式を提案している。これは、 Nニm" 個のPEをm進数表示

したとき一桁だけ異なる PE同士を完全結合網により接続する構成であり、通信距離は、

O(log m N)となる。ある程度結合用ハードウェアが必要になるものの興味深い構成と言 える。このようにハイパキューブを原型とする結合方式が盛んに研究されているのは、こ れが高並列計算機の一つの代表的な結合方式で あるからと言えよう。本論文で提案する分 割パス結合付加型ハイパキューブ6⁷ )および CCTcube⁸⁰⁾ もこの改良型の結合方式である。

並列アーキテクチャでのもう一つの大きな課題は高信頼化技術と言えるが、これは結合 方式等に比べると比較的最近の話題であり研究の歴史も浅い。ここでは、故障発生から処 理の再会までの各ステップ、具体的には故障検出・診断68. 6 9 )、システム再構成7ト 79)、 誤り回復8 ). 8 2 J等が課題となるが、中心的課題は故障PEを論理的あるいは物理的に切離

し、もとのシステムを再生するシステム再構成法である。

並列計算機でのシステム再構成法には基本的に二つのアプローチがある。一つは故障P Eを切離しシステム規模を縮小して運転を続ける、いわゆるgracefuldegradationと呼ば れる概念に基づくものである。もう一つは、予め予備を付加しておき故障PEをこれで置 き換え、もとの規模のシステムを再構成するものである。しかし、前者はただ故障部分を 切り離すだけであり、厳密な意味では再構成とは言えず(ここではむしろ負荷の再配置法 等の誤り回復の方が主要な課題となる)、後者についての研究の方が盛んである。後者で の主要課題は、 PE故障を許容できるフォールトトレラン卜構成であり、 VL S 1化の際 の欠陥救済を目的としたものを含め、 PE間の結合方式対応に多くの構成が提案されてい る。例えば、 トリー結合では Liveseyらがトリーを構成する 3個のPEの中央に予備PE を置き、周囲の 3個のPEの何れをも代替可能とする構成70) を提案している。 2次元ア

‑4‑ ^FH_U

 

レイでは、 Singhによる隣接する 4PE毎に予備PEを設ける構成^7I )、 Samiらによるい くつかの予備PE列を設け故障PEを隣接PEで置き換える構成72) 、横田らによる上下 方向に隣接する 2P E間にスイッチを設けこれにより故障PEを迂回させる構成13) (H  obonetと呼ばれる)等が提案されている。本論文で提案する 2次元n

+ 

1予備74l  も2次 元アレイのためのフォールトトレラント構成の一つである。

ノ¥イパキューブについては、 PE間の結合が密なため予備PEの設置法あるいはこれと の結合法が難しくなり、今まであまり有効な構成は示されていない。最近、 Rennelsはハ イパキューブを分割した小さなキューブ(サブキューブと呼ぶ)毎に予備PEを設け、こ の聞をクロスパスイッチで結合する構成75) を提案したが、これも拡張性、結合用ハード ウェア量等の点で問題が有る構成である。本論文で提案する構成76) は、これら問題点を 解決した任意のサイズのハイパキューブに適用できる汎用的な構成である。なお、多段ス イッチ網のフォールトトレラント構成については、スイッチ網が故障した場合の迂回方法

7 8 )に関するものが多い。

1 ̲  3  を汗ヲモα〉重力格主きとヨ三え￡尾文身ミL

本研究の主要な動機を以下に示す。

(1)  10³ ‑‑10.以上の高並列計算機において、 PE数に見合ったシステム性能を実 現するには代表的な並列化オーバヘッドである PE間通信を高速に処理する必要があ り、これを可能とする並列アーキテクチャの確立が重要となる。このためには、全く 新たな結合方式を考案しこれをベースに研究するアプローチもあるが、これまでの 2 次元アレイ型あるいはハイパキューブ型と言った高並列向きの結合方式をベースとす るアプローチのほうが、既開発の並列化アルゴリズムをそのまま実装できる等の点で 効率的と言える。従って、これらの結合方式の原型を崩さず、若干のハードウェア付 加でその通信性能を向上できるアーキテクチャの導出が重要と考えた。

( 2 )高性能化が実現できてもシステムダウンが多発するようでは実用に耐えうるとは言 えない。即ち、元長構成の適用によるフォールトトレラント化が重要となる。並列計 算機では、 PEを切り換え単位とすることができ一般的な冗長構成でも効果が高いこ

とが予想されるが、その定量的な評価はあまりなされていない。

( 3 )フォールトトレラント化については、対象とする並列計算機の結合方式に適した構 成法を確立する必要がある。 2次元アレイ型では4隣接のPEしか結合していないた め各種の構成が考え得るが、少ない予備で冗長化効果が高くかっ結合の単純さを維持 できる構成が望まれる。又、ハイパキューブ型は最近特に注目を集めているが、これ に対する有効なフォールトトレラント構成はいままで報告されていない。

( 4)高PE間通信性能とフォールトトレラント性を両立させた高並列計算機の構成法を 確立する必要がある。そのためには、この条件を満たす具体的な装置を設計・試作す る等検討を詳細化し、この両立が可能であり、かっ実現性があることを示す必要があ る。又、 2次元アレイあるいはノ¥イパキューブ以上の可能性を持ち、先の条件を満た したより一層高並列向きの結合方式の模索も重要である。

円hu ‑7‑

( 1)  P E間通信性能向上のための 2次元アレイおよびノ、ィパキューブの改良型アーキテ クチャの提案と評価^{6 1}・67.83)

2次元アレイ型については、本来のPEアレイの上位に小規模なPEアレイを付加 した階層化アレイアーキテクチャを提案した。本構成では、距離が離れたPE聞の通 信を上位のPEアレイをバイパス路として用いることにより処理し、通信遅延を短縮 する。この効果を、並列処理モデルと PE開通信分布を仮定し、平均通信遅延(ある 時点で発生した通信をすべて処理するのに要する時間)の観点から解析的に評価し、

一般の 2次元アレイに対して最大 i桁近い改善が期待できること明らかにした。

ハイパキューブ型については、符号理論を利用しPE群を特定の性質を有する複数 の集合に分割し、集合毎にパス結合を付加するアーキテクチャを提案した。本構成で は、パスをバイパス路として用いることにより、如何なるサイズのハイパキュープに おいても、最大PE間距離(直径とも呼ばれる)を 2に短縮できる。又、バイパス路 が複数あるため、一般のハイパキューブ型あるいはそれに単一のパスを付加したアー

キテクチャに対し、大幅に平均通信遅延を短縮できることを示した。

予備を階層的に適用したもので、 2重化以上のMTTF向上度が得られ無保守化シス テム実現の可能性を持つことを示した。又、 PE間結合構造が単純で、かっ切替え制御 が容易な、 2次元η+1予備向きのPE間結合法 (IX‑NET)を示した。

ハイパキューブ型については、切替え用のハードウェアを不要とし、かつ如何なる サイズのハイパキューブにも適用可能なフォールトトレラント構成を提案した。この 構成では、まず全PEを集合内でその番号のハミング距離が互いに大きくなる複数の 集合に分割し、これらをパスを介し予備PEと接続することにより、ベースとなるフ ォールトトレラントなハイパキューブを得、次にこれをグラフの積を利用して拡大す る。又、この構成法によれば、予備PEのリンク数を本来のPEと同じにでき、完全 にモジュラなフォールトトレラント構成が得られることを示した。

このような観点から、本研究では高信頼・高性能な高並列計算機ハードウェア構成を追 求した。以下に主要な成果を示す。

( 4 )接続数、直径が小さくかっ高信頼な高並列向き結合方式の提案⁸⁰⁾ 

接続数、直径をハイパキューブのそれらの約 1/2に削減できる結合方式 CCTcube (Complete‑Connection  of  Torus‑Hypercube)を提案した。本結合方式は、ハイパキュ ーブにバイパス用リンクを付加してベースとなるサブネットを構成し、複数のサブネ ット聞を再帰的に完全結合するものである。又、サブネットを切替え単位とした

n+

1予備により、フォールトトレラント性を実現している。これまでの代表的な結合方 式に比べ、接続数、直径を共に大幅に削減できることを示した。

(2)高並列計算機に対する冗長構成適用の定量的評価74.84.85)

高並列計算機を高信頼化する場合の基本的課題を示すと共に、一般的な冗長構成で ある多重化、 n

+ 

1予備を PE毎に適用した場合のM T TF (Mean Time To  Failure)  向上効果を解析的に明らかにした。文、 PE数 (N)とMTTF向上効果の関係を与 える近似式を導出し、これら構成によりMTTFをQ(N^I/2

)倍程度向上できることを 示した。さらにPEの診断法として、直接結合されたPEを利用し、多数決でその良 否を判断する並列診断法を提案した。

( 5 )高PE間通信性能とフォールトトレラント性を備えた高並列計算機ハードウェアの 設計例の提示^61.88‑95)

2次元アレイ型については、少ない冗長度で高いMTTF向上度が得られる 2次元 n + 1予備と呼ぶ構成を提案した。この構成は、 1行 1列の予備PEを設け、 n+ 1 

高性能・高信頼な高並列計算機ノ¥ードウェアの構成技術の確立をめざし、階層化2 次元アレイ計算機を設計し、小規模な実験機 (HA P 3 2/8)を試作した。この中 で、階層化構成の適用に伴い特殊化する点に着目した、各種PE間通信・同期の告iJ御 法、実現法等を示し、同構成の計算機に対する設計指針を与えた。 HAP32/8は 3 2個のPEと8個の制御PEからなり、これら PEは汎用マイクロプロセッサ、 D RAM素子、新たに開発した 2個の専用 LS 1のみから構成される、 LS 1化PEで ある。文、 2次元 n

+ 

1予備の適用に必要なすべてのフォールトトレラント機能を内 蔵している。

( 3)  2次元アレイおよびノ¥イパキューブに適したフォールトトレラント構成の提案74・ 76.85‑87) 

nHU  n

HU  

1 ̲  4  _{オヌ言命コと}αコキ毒疋文

本論文は 10章からなる。以下、各章の概要を示す。

第 2章では、本論への準備としてPE間通信性能向上の重要性について概説した後、そ れを左右する PE間結合構成とその重要な評価パラメー夕、高並列化に適合する 2次元ア

レイ型とハイパキュープ型の特徴等について述べる。

第3章では、 PE間通信性能向上を狙った、 2次元アレイをベースとした改良型アーキ テクチャである階層化アレイ構成を提案する。ここではその構成概要と平均通信遅延の解 析的な評価を中心に述べる。

第4章では、同じく PE間通信性能向上を狙った、ハイパキューブをベースとした分割 パス結合付加型アーキテクチャを提案する。符号理論に基づくパス結合の付加アルゴ.リズ

ムと通信ルートの決定法を中心に述べる。

第5章では、高並列計算機の高信頼化の基本的な課題を示すと共に、一般的な冗長構成 である多重化、 n+1予備等の適用効果を解析的に明らかにする。又、ネットワーク型並 列計算機に一般的に適用できる、直接結合されたPEを利用した並列診断法を提案する。

第6章では、 2次元アレイ型に適したフォールトトレラント構成法として、 l行 l列の 予備を設ける階層的な冗長構成法を提案する。又、この構成の適用効果を解析的に明らか にする。

第7章では、ハイパキューブのフォールトトレラント構成を提案する。ここでは、パス 接続を利用し切替え用のハードウェアを不要とする、符号理論を利用した構成アルゴリズ

ムを中心に述べる。

第 8章では、 2次元アレイあるいはノ¥イパキュープ以上の可能性を有する、より一層高 並列向きの結合方式 CCTcubeを提案する。フォールトトレラント化をも可能とする構成法 および接続数、直径の削減効果について述べる。

第 9章では、高PE間通信性能とフォールトトレラント性を両立させた高並列計算機の 実現の可能性を示すため、階層化2次元アレイ計算機を例とした具体的なハードウェア設 計例を示す。

第 10章は、以上の各章における結果を総括しまとめたものである。

‑10‑

第写 2 書室 立12::7リ言十算王務長色の*吉壬Erヌデ王丈二

並列計算機の本質的な狙いは、逐次型計算機で得られないような高性能を実現すること である。又、実用上からは、さらにこの高性能を経済的に実現することが必要であるロ

並列計算機のシステム性能Pは、 PE数をN、PE単体の性能をPoとすると以下で表 される。

P=αNP

。

_{( 2.  1)} 

ここで、 αはPE効率あるいはPE利用率と呼ばれ以下で表される。

α =  (To /N) / T   _{( 2.  2)} 

ここで、 Tはある問題をN個のPEで処理するのに要する時間、 Toはそれを l個のPE

で処理するのに要する時間である。

並列計算機では、一般に負荷を各PEに分割し、各PEはその負荷を他のPEと何らか の交信をしながら処理していく(ここでは機能分散型は対象としなしつ。従って、負荷ノ〈

ラツキあるいは通信オーバヘッドが発生し、 PE効率αはlにはならず、これをできるだ けlに近づけることが重要な課題となる。このためには、まず負荷バラツキやPE間通信 が少ない並列処理アルゴリズムの開発が重要であるが、ハードウェア実現の観点からは発 生したPE間通信を如何にして高速に処理するかが最大の課題となる。そして、このPE

開通信の性能に最も影響するのがPE問の結合方式である。

以下、本章では並列計算機の結合方式およびその評価ノぐラメータについて概説し、さら に、高並列化に適合すると考えられる 2次元アレイ型とハイパキューブ型について、その 構成と特徴を概説する。

一11‑

クロスパスイッチ 2 ̲  1  系吉恒三r

ヌ

7王丈二OJタテ美頁

並列計算機の結合方式は通信方法と密接に関連する。即ち、並列計算機では基本的に以

下の 2つの通信方法があり、結合方式もそれに対応して大別される(図 2. 1)。

イ)共有メモリへの情報の読み書きによる通信

ロ〉メッセージとして情報を交信することによる通信(一般にメッセージパッシング) 即ち、イ)の場合には、 PE聞の通信は共有メモリを介して行われ、 PEと共有メモリ の聞を何らかの結合網で接続することになる(図2. 2)。これを共有メモリ型と呼ぶ。

又、ロ〉の場合には、 PE間を l対 iの接続線(これをリンクと呼ぶ)で結合し、直接接 続されていないPEへの通信は他のPEを中継することにより行われる。これをネットワ

共有メモり型寸一一

」 ー 多段スイッチ網

一

^{3ステージC I 網}

再構成型非閉塞網 ‑ Benes網97)

パス

ーク型と呼ぶ。

ネットワーク型寸一 対称型

」 非 対 称 型

リング，アレイ，ハイパキューブ トリー，スノーフレーク9g) 

共有メモリ型には、パス結合、クロスパスイッチ、多段スイッチ網がある。パス結合は 単にPEや共有メモリをノ〈スに接続するだけであり、パスへのアクセス権を制御する調停 回路以外には、結合用のハードウェアは一切不要であるという利点があるo しかし、同時

図2. 1  _{結合方式の分類}

には一つの通信しか処理できないため、 PE数が多い場合にはパス上で、のアクセス競合に より、システム性能が制限されることになる。従って、パス結合は最大 10数並列程度の 計算機に適用されることが多い。クロスパスイッチは、 PE数Nに対してN!通りの結合 パターンを実現でき、しかもスイッチ 1段分の遅延しかないため、極めて高性能な結合網 であるが、そのハードウェア量は O(W)となる欠点がある。このため、

C .

mmp 100)、

S I G M

A‑110 1) 等のいくつかのマシンで用いられているのみであり、かっその適用範囲は多くて

も100並列程度までと考えられているI0 2 )。

多段スイッチ網は、図2. 3に示すように小スイッチを多段に結合したもので、クロス パスイッチを機能縮小し簡略化したものと言える。これには、ある接続要求があったとき に、接続中の他のスイッチ設定を変更しないでその接続を実現できる非閉塞網、任意の結 合パターンを実現できるが新たな接続要求があったときには、接続中の他のスイッチ設定 を変更する必要がある再構成型非閉塞網、および、 N!通りの結合パターンのうちその一 部しか実現できない閉塞網がある。非閉塞網には、図2. 3の小スイッチをクロスパスイ

ッチとしたClos網96) 等が有るが、そのハードウェア量はクロスパスイッチよりは少ない ものの、

o

(N^3/2)とかなり多い。再構成型非閉塞網の代表例は Benes網97 )であり、一般 に2入力2出力のスイッチを21og2N‑l段結合して構成されるが、任意の結合パターンに対

日

士 口

玄中 ，d..， 

E

コ 市 岡

• •

図2. 2  _{共有メモリ型結合}

円/‑1EA 

ー13‑

。

2  3 

a4_・

Fh u

6  7 

図2. 3  _{多段スイッチ網} (0m e 9 a網)

。

を接続したハイパキューブ等がある。非対象型には、 P Eを 2進木状に接続したト リー結 合、 P Eを三角形に接続しそれを階層的に積み上げていくスノーフレーク 99 )、リング結 合とハイノ号キューブを組み合わせたCC(⁵⁴) (これはほぼ対称ともいえる)等がある。 一般に非対象型は階層構造をとるものが多く、 P E当たりのリンク数が少ない割りには最 大PE間距離を短くできるロ例えばトリー結合では、 PE当たり 3本のリンクで最大PE

間距離を log2Nにで・きる。しかし、問題を並列展開したときの通信分布がネットワークの トポロジに適合する場合を除いて、いずれかの P Eあるいはリンクに通信が集中しがちで あり、これによりシステム性能が制限されることになる。ザJIえば、通信分布に局所性がな く全くランダムな場合には、 トリー結合タイプのネットワークでは根のPEに中継のため の通信が集中することになる。即ち、非対象型のネットワークは、広い問題適応性を狙っ た並列計算機にはあまり適さないと言えよう。

これに対し、対象型は非階層的なものが多く、最大PE問距離を短くしようとすると P E当たりのリンク数が多くなりがちである。しかし、特定の箇所への通信集中はおこらな いため、比較的広い問題適応性があると言え、多くの並列計算機で採用されている。特に 本研究で主対象としている、 2次元アレイ型とハイパキューブ型の開発が盛んである。

2  3 

4  5 

6  7 

するスイッチ設定を動的に行えない欠点がある (O(Nlog2N)の設定時間が必要〉。なお、

IBM社の GF 11¹⁰³)における Memphis網も、クロスパスイッチにより構成されるが再構成 型非閉塞網である。閉塞網には、 Omega網⁹⁸⁾ 、8aseline網¹⁰4)等多くの構成があり、 2 入力 2出力のスイッチを log2N段結合して構成されるが、これらはNl通りの結合パター

ンのうち、 NN/2通りしか実現できない欠点がある。さらに、これらのハードウェア量は

o 

(Nlog2N)で、あり、非閉塞網より少ないものの 10³ ‑‑‑‑10⁴ 規模の高並列化の場合には まだ問題になる量であると言えよう。多段スイッチ網はこのようにスイッチノ¥ードウェア 量が多くなるだけでなく、これをLS 1化する場合にも、その端子数が回路規模の害IJに大 きくなり、 LS 1化の利点が活かしにくい。従って、多段スイッチ網の適用範囲は数100 並列程度までと考えられている10 2 。)

一方、ネットワーク型は結合用ハードウェア量が少ないため、 1000並列以上も可能であ る。これには、 P E聞を結合するトポロジにより数多くのタイプがあるが、大別すると結 合が対象なものと非対象なものに分けられる。ここで対象とは、各PEで結合数、結合形 等が全く均一なことを言うこととする12 2 )。対象型には、 P Eをリング状に接続したリン グ結合、 2次元格子状に接続した 2次元アレイ、 PE番号が 1ビット異なる全てのPE間

‑14‑ ^Fhd 

'E EA  

2 ̲  2  才 ぇ ッ ト ワ ー ー ク 歪 包 系 吉 否 詮 剥 司O J言 平 イ 面 ノ 々 ラ メ 一 一 タ

主要な評価ノぞラメータを以下に示す。

( 1) P E間距離

直接接続されていないPEと通信する場合には他のPEを中継する必要がある。この中 継する PEの数に lを加えたものをPE間距離と呼び、ネットワークにおけるその最大値 を最大PE間距離(直径とも言う)と呼ぶ。 PE間距離が長いとメッセージの伝達に時間 がかかり、並列計算機のシステム性能を制限することになる。従って、最大PE間距離は ネットワークを性能面から評価する際の最も重要なパラメータである。

( 2 )中継量

ある PEが他のPE間通信の中継として使用される数を中継量と呼ぶ。即ち、 PE数が

Nのシステムでは

N ( N ‑

1)/2通りの通信があり、このうちいくつが自 PEを中継に用いる かを意味する。対象型のネットワークでは中継量は全てのPEで同一であるが、非対象型 では不均ーとなる。このため後者では、一部のPEに中継量が集中するとそこがボトルネ

ックとなりシステム性能が上がらないことになる。

( 3 )接続数

i個のPEに直接接続される他のPEの数、すなわちPE当たりのリンク数を接続数と 呼ぶ。一般に接続数が多い程問題への適用性は向上するが、結合部分のハードウェアコス トが高くなる。又、接続数がPE数に依存するネットワークでは高並列化する場合、 LS I、ボードといった実装の各レベルでその接続処理が問題になる。

( 4 )放送時間

ある PEが他の全てのPEへ同一のデータを送るのに要する最短の時間を放送時間と呼 ぶ。放送は、プログラムロードや初期データの供給の他、途中の処理結果を全PEへ伝達

し、それをもとに次の処理が再開されるような問題で用いられる。

‑16‑

これらパラメータにおいて、放送時間と直径は互いに関連し、一般に一方が短ければ他 方も短いことが多い。又、中継数と直径についてもほぼ同様な傾向がある。従って、これ らのうち最も重要なパラメータは、直径と接続数であると言える。高並列計算機では、結 合の対称性を極力保ち、かっこの両者を同時に削減できるネットワークが望まれる。ただ し、これらパラメータは静的な評価指標であり、実際のネットワークの性能を評価するに はこれだけでは充分とは言えない。即ち、問題を並列展開する場合、遠くのPEとはでき るだけ通信が発生しないように工夫するのが普通であり、これら通信分布や通信が発生す る頻度を考慮した動的な評価も重要である。

2  3  2 と穴矛己フアレイ系吉モ三T

2次元アレイは、各PEを上下左右方向に隣接する 4個のPEと結合するネットワーク

である。さらに、最左端と最右端、最上端と最下端同土のPEを結ぶ(トーラス結合と呼 ばれる)と直径を 1/2にできるため、 トーラス結合を併用するシステムが多い。図 2.

4にこの場合の結合構成を示す。直径はN1/2 、接続数は4である。

この結合トポロジは、 PE間通信に局所性が有るような応用に適していると言える。例 えば、画像処理や科学技術計算では、通信が隣接PEとの問だけでしか発生しないように 並列展開できる問題が多くある(ポアソン方程式を ODD‑EVENSOR法で解く場合を図 2.

5に示す)。このため、この分野における代表的なネットワークとなっており、 ILLIAC‑

ト ー ラ ス 結 合

¥ 

司っ

町の時代から現在まで、 M P P 105)、PA X⁸)、CAP¹⁰⁶)等多くのシステムで採用され ている。しかし論理シミュレーション(一般に対象回路を各PEに分割して割当てる)等 の応用では、直接結合していない遠くのPE間との通信が発生するため、直径が大きいこ とに伴う通信遅延の増大が問題となる。即ち、より広範な適用を狙うにはこの結合だけで は充分とは言えない。

しかし、数値処理では前述のような分野でこそ、巨大計算の現実的時間内での処理が要 求されるとも考えられ、用途をこれらに限定しでも充分存在価値が有ると言えよう。又、

結合が単純でかつPE数に係わらず接続数が一定であることから、高並列化に極めて適し

図2. 4  2次元アレイ

問題領域 lPEの受け持ち領域

たネットワークであるとも言えよう。 ^Ui‑1・J

Ui ・^J‑1 

I 

^U i・

I

^U i.  J + 1 

U^1 + 1・J

2次元ポアソン方程式

基本式(会+赤

^)U+s=o

式分差 ^( n + I )  ( n ) 臼 (n )  ( n )  ( n )  ( n ) 

Ui・i= (1‑ω) U   i.i 十1一(Ui.i‑t+ Ui・ け1+ U iぺ ・ ; t U i什・ i+s i.  j  ) 

図2. 5  ODD‑EVEN  S O R法によるポアソン方程式の求解

ー18‑ ‑19‑

2 ̲  ₄  ノ ¥ イ ノ 々 キ ュ ー ブ 系 吉 壬 三r 従って、ハイパキューブは、 PE番号聞のハミンク'距離が互いに lであるすべてのPE

問にリンクを設けたネットワークということができ、 n次元キューブでは直径、接続数共 に nとなる。図2. 6にハイパキューブの構成例(4次元キューブ)を示す。

ノ¥イパキューブは、イ〉比較的多くのPEと直接結合される、ロ)その結合が完全に対 称、ハ)直径が小さい、等の他、そのネットワークの中にリング、トリー、 2次元アレイ を包含，0 7，・0 8)しているという特徴を有する。このため、幅広い問題に対応できるネット ワークとして注目されている。例えば、前節で述べた2次元アレイ向きの問題のほか、 F F T 3 0) 、各種シミュレーションあるいは意味ネットワーク，0 9)、知識ベースシステム1I  0)といった記号処理への適用も可能である。従って、最近この結合をもっ並列計算機の開 発が盛んになってきており、 iPSC^S)、N‑cube⁹) 、FPS‑T)")、コネクションマシン63) 

等で用いられている。

ノ¥イパキューブは、 PE番号を 2進表示したとき lビットだけ異なる全ての PE間を接 続したネットワークであり、厳密にはグラフの積を用いて以下のように定義される。

〔定義2. 1)  PEを節点、 PE聞のリンクを枝としたとき Q， 

=K

2 ， Qn 

=K

2 xQn^ーl

ここで、 K2  2節点の完全グラフ

で順次拡大されたネットワークをハイパキューブ(以下キュープとも呼ぶ〉という。

ここで、グラフの積は以下のように定義される。

〔定義2. 2)  グラフG，とグラフ G2の積Gp =Gl XG2は、 V_P = V， X V2を 節点集合とし、 VP中の任意の 2節点u =(UI，U2)， V =  (VI，V2)において、 U，

= V，でU2， V 2聞に枝があるか、 U2 = V 2でU1， V I聞に技がある場合に、 U，V間 に枝を張ったグラフである。ここでV)，V 2はそれぞれG)，G2の節点集合であり Vpは

VP  {(Vlt V2) 

I 

VI  E V1 ， V2 E V2}で表わされる。

。

^{(0101)  t・ ︑ ︐ ‑ ‑ i  4冒EEg J︑ ︑ ︐ ︐}

グラフの積は定義2. 2のように表わされるため、 K2とあるグラフGとの積は、グラ フGを2つ設けそれらのグラフの対応する節点同士に枝を張ったグラフとなる。従って、

PE数 N

= 

2 ⁿ のハイパキューブ(以下 n次元キューブと呼ぶ)は、 2つの n‑l次元キ ューブの対応する位置のPE間にリンクを設けることにより構成される。又、 n次元キュ ーブにおける PE番号は nピットのビットパターンで表現され、一般に以下のように付与 される。

(1011) 

(1110) 

[P E番号の付与法 n次元キューブでのPE番号は、一方の n‑1次元キューブに属 する PEの番号の最上位ビットに

o

"を、他方の n‑l次元キュープに属する PEの番 号の最上位ビットに 1"を付加することにより得られる。なおベースとなる l次元キュ

ーブでの 2つのPEの番号は

o

"と 1"である。

ハイパキューブの構成例 (4次元キューブ) 図2. 6 

‑20‑ ^‑21‑

多事 3 主主主 戸皆Y書 イ 七 フ ア レ イ フ ァ ー ー ニ キ ニ ラ 子 ク ヲ 二 ヤ

3  1  来者言言

本章では、高並列プロセッサ向きである 2次元アレイ型をベースとし、それらの直径お よび平均通信遅延の短縮による PE間通信性能の向上を狙った、改良型アーキテクチャの 提案を行う。

これは、基本的には本来のネットワークの他にバイパス路を設け、遠隔PE間通信はこ れにより処理しようとするものである。具体的には、本来のPEアレイの他にバイパス路 として小規模なPEアレイを設け、これらを階層構成化する。本章では、まず 3. 2節で この階層化アレイアーキチャの構成と狙いについて述べ、次に3. 3節でそのPE開通信 性能を平均通信遅延の観点から解析的に評価する。

通信性能評価では、まず並列処理モデルを設定し、 PE間通信に局所↑生が有る場合と無 い場合について、一般的な2次元アレイ型および それにパス結合を付加した構成と比較し ながら階層化の効果を明らかにする。

3 ̲  2  F皆 f畜 イ ヒ 7 レ イ キ 毒 疋 文

基本的な狙いは直径の短縮であり、図 3. 1にその構成を示す。即ち、小規模な PEア レイ (mXm)を本来のPEアレイ Cnxn=N)の上位に設け互いに結合する。以下、

両PEアレイをそれぞれ上位PEアレイ、下位PEアレイ、それらのPEをそれぞれ上位 PE 、下位PEと呼ぶ。これら PE聞は、下位PEアレイをmXmの小PEアレイ群に分

割し、各小PEアレイを l個の上位PEに結合する。なお具体的な結合方法は、上位PE のリンク数の増加を避けるため、又、上位PEは同時には i個の下位PEとの通信しか処 理できないため、パス接続を用いる。即ち、 N/m²個の下位PEがl個の上位PEにパ ス接続される。

このような構成を採り上位PEアレイをバイパス路として用いると、ネットワークの直 径は、 nからm+2に短縮されることになる。ここで2は下位PE‑上位PE間の往復の 距離である。又、両PEアレイはトーラス結合を併用するものとする。

なお、上位PEアレイを下位PEアレイに対しどの程度の規模にするかについては、そ の追加によるコスト増加と通信性能向上度を懸案して定めればよいが、後者は対象とする 問題のPE間通信特性に大きく依存するため一般解は存在しない。例えば、遠隔PE間通 信が極めて少ない場合には、 mはnに対し充分小さくてよいと言え、又、逆にこれが極め て多い場合には、下位PE‑上位PE間の通信がボトルネックとなり、 mをいかに大きく

しても階層化の効果はあまり期待できなし1かもしれない。従って、ここでは下位PE数が

10³ ‑‑10^{4規模の場合に、上位}PEアレイ付加によるコスト増加を数%以下とするこ とを想定し、上位PE数をn(= N 1/2 )程度に設定することを考える。

上位PE アレイ

/'(ス¥、

下位PE アレイ

図3.

庁1

下 位PE

r:(ぺ

ーーーーーーーーーーーーーーー『、，

n 

ι ;  

υ そ 〉

階層化アレイ構成

‑24‑

n 

3 ̲  3  _{P E昆男え亘イ言}

f

生 台 邑 言 平 イ 面

並列処理モデル、 PE間通信分布を仮定し、階層化アレイアーキテクチャのP E間通信 性能を、一般的な 2次元アレイ型およびそれにパス結合を付加した構成と比較しながら、

平均通信遅延の観点から解析的に評価する。

3.  3.  1 評 価 モ デ ル

( 1 )並列処理モデル

解析を簡単化するため以下のモデルを設定する。

<並列処理モデル(図3. 2) 

> 

・問題は演算と通信の繰り返しにより解かれる。

・演算フェーズと通信フェーズはオーバラップせず、かつそれらの聞の移行は全P E同期 して一斉に行われる。

P E 0 

P E I 

.P E 2 

P E ^I 

演算フェーズ 通信フェーズ 演算フェーズ 通信フェーズ

ヲ 〉 く タ 。 ご 三

同期 日 間 百四日

時刻t

図3. 2  並列処理モデル

‑25‑

‑通信フェーズでは各P Eは確率KでP E間通信を発生する (Kを通信発生率と呼ぶ)0 

.遠隔P E間通信は基本的には隣接P E間通信の繰り返しで実現する。

・各P Eは同時には l個の通信しか処理できない。

(2)  P E間通信分布

P E開通信に局所性が有る場合(距離が遠いP E間ほど通信が少ない場合)と無い場合 として以下の通信分布を仮定する。

i )局所性が有る場合 :PE間距離をし全体の通信に対する距離 iの通信の割合を fⁱ  としたとき、 fi = A /  i (A:定数、 1‑‑‑n)。なお、 n は (PE数N)1/20

u)局所性が無い場合:全てのP E間の通信の割合が均一。すなわち、各P Eは他の全て のP Eに対して等確率で通信を発生。この場合、

f i 

= 

(距離 iで到達できる P E数)/ ( (全P E数)一 1)  であり、 トーラス結合を付加した 2次元アレイ型では、

• nが偶数のとき

f i =4 i /  (n2 ‑1)  (i <n/2) 

=(4i‑2)/(n2^ー 1) (i=n/2) 

=4 (n‑i)/(ド ー 1) (n/2<i<n) 

=1/(n2‑1)  (i=n) 

• nが奇数のとき

fi =4 i /  (n2 ‑1)  (i <n/2) 

=4 (n‑i)/(η2 ‑1)  (i >n/2) 

一般にある問題を並列展開しP E空間上にマッピングする場合、出来るだけ遠隔P E問 で通信が生じないようにするのが普通であり、 u)の局所性がない場合というのは最悪の 通信分布と言える。すなわち、通信による並列化オーバヘッドはこの場合以上には大きく ならない。多くの問題では多少は局所性があるように並列展開できると考えられるので、

ここで採り上げた i)の分布は代表例と言えないまでも、一つの目安を与えるものと言え よう。

‑26‑

3.  3.  2 解析方法

( 1 )解析対象アーキテクチャと P E間通信方法

<対象アーキテクチャ >

• 2次元アレイ :一般の 2次元アレイにトーラス結合を付加(図2. 4) 

・パス結合付き 2次元アレイ:上記構成に全P Eが結合される共通ノ〈スを付加(図 3. 3) 

・階層化アレイ:本節で提案するアーキテクチャ(図3. 1) 

<PE間通信方法〉

• 2次元アレイ:隣接P E間通信の繰り返しで全通信を処理。

・パス結合付き 2次元アレイ :PE間距離 iが特定値 (d^t )以上の通信はパスをノ〈イパ ス路として用いて処理し、 d^t未満の通信は隣接P E開通信の繰り返しで処理。

パス

図3. 3  パス結合付き 2次元アレイ

‑27‑