JAIST Repository: 超並列システムの将来像と課題

Japan Advanced Institute of Science and Technology

JAIST Repository

https://dspace.jaist.ac.jp/

Title

超並列システムの将来像と課題

Author(s)

井口, 寧

Citation

Research report (School of Information Science,

Japan Advanced Institute of Science and

Technology), IS-RR-2001-028: 1-53

Issue Date

2001-12-13

Type

Technical Report

Text version

publisher

URL

http://hdl.handle.net/10119/8396

Rights

Description

リサーチレポート（北陸先端科学技術大学院大学情報

超 並列 システ ムの将 来像 と課題

井 口 寧 2001年12月13日 IS-RR-2001-0028 北 陸 先 端 科 学 技 術 大 学 院 大 学 情 報 科 学 セ ン タ ー 〒923-1292石 川 県 能 美 郡 辰 口 町 旭 台1-1 [email protected] OYasushiInoguchi,2001 1SSNO918-7553

要 旨

大 学 におけ る高 度 な教 育研究 活動 を支援 す る情報 環境 を構 築す る こ とは,情 報 科学

セ ン ター にお いて非常 に重 要 な役割 の一 つで あ る.実 用 シス テム と して構築 す る場

合 は,既 存 の計 算機 シス テム を組 み合 わせ て,必 要 と され る情報 環境 を提 供 す る.

一方 で

,将 来 にわた る大 学 の教 育研究 活動 を支援 す るため に,将 来望 まれる情 報環

境 整備 に必要 な技 術 要素 の研 究 開発 もまた情報科 学 セ ン ター に とって重要 な課題 で

あ る.

本 論 文で は,北

陸先端 科学技 術 大学 院大学 情 報科 学 セ ンターの超 並列 計算 サ ー

バ を通 じて,学 術 目的 の情 報科 学 セ ンターが将来提 供 すべ き超高速計 算 サーバ に必

要 とされ る技術 とその解決 方法 につ いて検 討 す る.最 初 に同セ ンターに これ まで導

入 され た超並 列 シス テム につ い て検討 し,こ れ らの システ ムの特徴,利 点,課 題 と

なってい る点 につ いて議論 す る.同 セ ンターの超 並列 シス テム を用 い て,相 互結 合

網 の通信性 能 が シス テム全体 の性 能 に与 え る影響 につい て調べ た とこ ろ,PE間

通

信 のバ ン ド幅が重 要で あ り,特 に通信 遅延 が シス テム全 体 に大 き く影響 す る ことが

分 か った.

相互 結合網 の トポ ロジについ て検 討 した ところ,同 セ ンターが導 入 してい る よう

な二次元 や三次元 の トー ラス結 合 網 が科学 技術 計 算 に適 してい る こ とが示 された.

三次 元 トー ラス網 の シス テムは 同セ ン ターで既 に稼働 してお り,高 い計算 性能 を有

して い る こ とが示 され て い るが,将 来 超 高速 計 算 サ ーバ とな り得 る数 百万 の プ ロ

セ ッサ を有 す るシス テムへ の拡張 の ため には,再 帰 的 な結 合網 が有効 であ る ことが

分 か った.再 帰 的 な トー ラス網 と して 「

再 帰 シフ トトー ラス相 互結合 網」 につ いて

詳 し く議論 した結 果,本 相 互結合網 は従 来 の相 互結 合網 と遜色 ない通信 性能 を有 し

なが ら,非 常 に高 い拡 張性 が あ る こ とが分 か っ た.

また,実 装手 法 につい て議 論 し,シ ステ ム全 体 の高速化 のため には,シ ス テ ムを

高度 に集積 す る こ とが可能 な三次元 実装 が重要 で あ るこ とを示 した.三 次元実 装で

は放熱 が重要 な課題 で あるが,放 熱 を考慮 して予備PEを

選択 す る 「WSIス タ ック

の ヒュー リス テ ィック配 置方式 」 を用 い る こ とに よ り,ウ ェーハ ス タ ックのス タッ

ク 内 最 高 温 度 を大 幅 に冷 却 で きる こ とが 分 か っ た.

これ らの知 見 を踏 ま えて,情 報科 学 セ ンターで提 供 す べ き,将 来 の超高 速計 算

サ ーバ を実現 す るため の課題 の解 決へ の見 通 しを述べ た.

1は

じ め に

教育研 究活動 を支援 す る情報環境 を構 築す るこ とは,大 学 の情報 科学 セ ンターに

お いて非常 に重 要 な役割 の一 つで あ る.実 用 シス テ ム と して構築 す る場合 は,既 存

の計 算機 シス テム を組 み合 わせ て,必 要 とされ る情 報環 境 を提供 す る.一 方で,将

来 にわた る大学 の教育研 究活動 を支援 す るため に,将 来望 まれる情報環 境整備 に必

要 な技 術 要素 の研 究 開発 もまた情報科 学 セ ンター に とって重 要 な課 題 であ る.本 論

文 で は,北 陸先 端科 学技術 大学 院大 学(以 下 本学)情 報科 学 セ ンターの超並列 計算

機群 を導 入 ・管 理 ・運営 を通 じて得 られ た知 見 を もとに,将 来の情 報科 学 関連 の セ

ンターに必 要 な超並列 シス テム の ア0キ テ クチ ャを明 らか に し,そ の実現手 法 につ

いて展 望す る。

自然科学 にお ける シ ミュ レー シ ョンやVLSI設

計 な ど,先 端科 学技術 分野 にお け

る大規 模科 学技 術計 算 の需 要 は増大 してお り,多 数 のマ イクロ プ ロセ ッサ(MPU)

を用 いた超並列 計算機 に よる高速処 理が 求め られ てい る.こ の よ うな学 内の先進 的

な研 究 を支 援 す るた め,本 学 情 報科 学 セ ンタ0は,同

セ ンターの機 能 の一 つで あ

るコ ンピュテ ー シ ョンセ ンタ0と 情報科 学研 究科 の教 育研 究設備 との両面 にお ける

基盤情報 環境 として,様 々 なアー キテ クチ ャを有す る超並列 計算機 群 を導 入 して き

た.本 セ ン ター は最新 鋭 の超並 列計算 機 シス テムや ソ フ トウ ェ アシス テ ムの導入,

維持管 理,及 びユ ーザー教育 を行 ない,研 究基盤 の整備 を行 なって きた.こ の よう

な研 究基盤 を活 用 し,情 報科 学研 究科[1,2,3],材

料 科学研 究 科,お

よび知 識科 学

研 究 科 は,超 並 列計 算機 群 を活用 して優 れ た研 究 を行 なって きて い る.

しか しなが ら,本 学 発足 当 初 は,「超並 列計 算機 」 とい うだけ で非 常 に先 進 的 な

システ ムで あ ったが,現 在 におい ては,超 並列 システ ムは既 に実用 システ ム と して

用 い られて い る.情 報 科学 セ ンターが本 学 の先進 的 な研 究 活動 を支 える ため には,

新 しい アー キテ クチ ャや技術 を開拓 す る必 要 が強 く望 まれ てい る.

そ こで,本 論 文 で は,こ れ まで に本 学 情報 科 学 セ ンター におい て導 入運 営 され

て きた超 並 列 シス テム につ い て分析 し,次 世代 の研 究 を支 え る超 高 速計 算機 シス

テム に必要 な技術 を展望 し,現 在研 究が な されて い る課題 につ い て議論 す る.最 初

に これ まで情 報科 学 セ ンターが導 入 した シス テムの特 徴 につい て述べ る.第3章

で

現有 システ ム を用 い た性 能評価 を行 ない,既 存 の システ ムの問題 点 を探 る.第4章

で,相 互 結 合 網 につ い て 議 論 し,数 百 万 の プ ロ セ ッサ を用 い た真 の超 並 列 計 算 機 シ

ステ ム を実現 す るための結合 方式 につ いて議論 す る.第5章

で は,シ ス テム を現 実

の もの とす るための実装技 術 につ いて展 望 し,高 度 な集積 を可能 とす るため の三次

元 実装技 術 の放 熱手法 につい て研 究 を行 な う.第6章

は まとめ で あ る.

翼

2こ

れ ま での超 並 列計 算機 群

2.1情 報 科 学 セ ン タ ー の 超 並 列 シ ス テ ム の 遷 移 本 学 に は 開 学 以 来,多 数 の 超 並 列 計 算 機 が 設 置 さ れ,教 育 お よ び 研 究 に 盛 ん に 活 用 さ れ て き た.表1に 本 学 に 導 入 さ れ た 超 並 列 計 算 機 の 一 覧 を 示 す.超 並 列 処 理 研 究 用 シ ス テ ム と し てCM5とT3E,高 度 デ ー タ ベ ー ス 処 理 研 究 用 シ ス テ ム と し て nCUBE2,nCUBE3,並 列 ソ フ ト ウ ェ ア 研 究 用 シ ス テ ム と し てParsytecGC/MPC-128,さ ら に 情 報 環 境 の 一 部 と し て,UltraEnterprise10000を 導 入 し て い る.こ の う ち,CM5,CRAY-T3E,RS/6000-SP,CRAY-T3E-1200Eは,数 値 演 算 に 適 し た ア ー キ テ ク チ ャ と な っ て お り,高 い 演 算 性 能 を 有 し て い る. 2.2CM-5 本 学 で 最 初 に 導 入 さ れ た 超 並 列 計 算 機ThinkingMachines社 のConnectionMa-chineCM5は,64プ ロ セ ッ サ で 構 成 さ れ,最 大 で 毎 秒80億 回 の 浮 動 小 数 点 演 算 が 可 能 で あ る.使 い こ な す の が か な り 困 難 な 一 面 も あ る が,適 当 な 問 題 に お い て プ ロ グ ラ マ が 注 意 深 く使 用 す れ ば 非 常 に 高 い 性 能 が 得 ら れ る シ ス テ ム と な っ て い る.主 な 特 徴 は 次 の 通 りで あ る. 1.最 大 で8192CPUま で の 拡 張 性 2.分 散 記 憶,メ ッ セ ー ジ パ ッ シ ン グ ア ー キ テ ク チ ャ 3.単 位 プ ロ セ ッ サ に ベ ク トル 演 算 機 構 を 付 加 し た こ と に よ る 高 速 性 4.合 計2Gバ イ トの 記 憶 域,23Gバ イ トの デ ィ ス ク ア レ イ(SDA) 5.多 様 な ソ フ トウ ェ ア 環 境 2.2.1ハ ー ド ウ エ ア 構 成 CM5の 相 互 結 合 網 は,図1に 示 す よ う な 不 完 全FATTreeで あ る. 表2に,全 体 の 構 成 お よ び 各 プ ロ セ ッ シ ン グ エ レ メ ン ト(PE)の 構 成 を 示 す.並 列 化 さ れ た プ ロ セ ス が そ れ ぞ れ の ノ ー ドの ロ ー カ ル メ モ リ に ロ ー ドさ れ,実 行 さ れ る 分 散 メ モ リ型 の ア ー キ テ ク チ ャ で あ る. イ ン タ ー フ ェ ー ス ユ ニ ッ トは20MB/sの パ ケ ッ ト発 信 能 力 を 持 っ て い る が,ノ ー ドプ ロ セ ッサ 自体 が 低 速 で あ る た め,実 測 値 と し て の ノ ー ド対 ノ ー ドの 通 信 能 力 は 最 良 で も10MByte/sec程 度 に 制 限 さ れ る. 2

表1:本

学 にお け る超並 列計 算機

メ ー カ ー ・機 種 nCUBE社 ・nCUBE2 ThinkingMachines社 ・CM5 Parsytec社 ・GC/MPC-128 nCUBE社 ・nCUBE3 SiliconGraphics社 ・CRAYT3E SunMicrosystems社 ・UltraEnterprise10000 IBM社 ・RS/6000SP CrayInc.社 ・CRAYT3E-1200E

CPU数

256 64 128 128 320 136 32 288 136

設置期間

1993-1996 1993-1996 1996-1997 1994-1997 1996-1999 1997-2000 1998-2001 1999一 2001一 Frontnet DataNetwork 圃 cm5-cpl 唖 cm5-cp2

塾

0 ProcessingNodes 63DiskArray 図1:64プ ロ セ ッ サ のCM5の 結 合 ネ ッ トワ ー ク 2.2.2ソ フ ト ウ ェ ア CM5の 特 徴 の 一 つ は,並 列 計 算 機 と し て は 極 め て 豊 富 な 言 語 や ソ フ トウ ェ ア ツ0 ル を 有 し て い た こ と で あ る.表3に 利 用 可 能 な ソ フ トウ ェ ア を 示 す. 特 にCM-Fortranは そ の 当 時 でFortran90の 自 動 並 列 化 記 述 を 先 取 りす る 形 で 実 現 さ れ,CM5上 で 開 発 さ れ た 超 並 列 ソ フ ト ウ ェ ア は,そ の 後 の 超 並 列 シ ス テ ム に

表2:CM5の 構 成

相互結合網

ノ ー ド数 ノ ー ド プ ロ セ ッ サ ロ ー カ ル メ モ リ

PE間

通信 速度

ノー ド演算 能力/PE間

通信 速 度

FATTree 64

SparcIU,FPU(33MHz,22Mips,4.2MFIops),

VectorProcessingUnit(16MHz,32Mflops)x4

32MB/node

20MB/s

6.4MFIops/(MB/s)

表3:CM5の 構 成

名称

CM-Fortran c* STARLISP Prism CMMD CMSSL CMX11 pndbx CMView CMFS CMNA CDPEAC

概要

限 定 的 な 自 動 並 列 化 コ ンパ イ ラ 言 語,拡 張Fortran90

限定 的 な 自動並 列 化が で きる拡 張C言

語

Commonlispの 並 列 拡 張 並 列 グ ラ フ ィ カ ル デ バ ッ ガ,兼 簡 易 ビ ジ ュ ア ラ イ ゼ ー シ ョ ン メ ッ セ ー ジ パ ッ シ ン グ を 提 供 す る ラ イ ブ ラ リ

並列 数値 演算 ライ ブ ラ リ

低 レ ベ ル グ ラ フ ィ ッ ク 出 力 ラ イ ブ ラ リ

並 列用 デバ ッガ

ハ イ パ ー テ キ ス ト風 オ ン ラ イ ン マ ニ ュ ア ル

SDA用

並 列入 出力 ライ ブ ラ リ

低 レベ ル通信 ライブ ラ リ

VectorUnit用 ア セ ン ブ ラ マ ク ロ お い て も,ス ム ー ス に利 用 で き た こ と は,ソ フ ト ウ ェ ア 上 非 常 に 有 意 義 で あ る. 2.3CrayT3E CrayT3Eは,CM5の 機 種 更 新 に よ っ て 導 入 さ れ た,本 学 の 数 値 計 算 系 の 超 並 列 シ ス テ ム の2世 代 目 の 機 種 で あ る.表4にT3Eの 構成 を 示 す.主 に 科 学 技 術 計 算 の 超 高 速 演 算 を 目 的 とす る 超 並 列 計 算 機 で,CPU,ロ ー カ ル メ モ リ及 び 通 信 プ ロ セ ッ 4

表4:T3Eの 構 戒

相互結合網

ノ ー ド数 ノ ー ドプ ロ セ ッ サ ロ ー カ ル メ モ リ

PE間

通信速 度

ノー ド演 算能 力/PE間

通信 速度

3DTorus 128

Alpha21164a(300MHz,600MFIops)

64MB/node

480NIB/s

1.25MFIops/(MB/s)

サ か ら成 るPEノ ー ド を,3次 元 トー ラ ス 相 互 結 合 網 で128台 結 合 し た 分 散 メ モ リ 型 の 並 列 計 算 機 で あ る.相 互 結 合 網 の ネ ッ トワ ー ク イ ン タ ー フ ェ ー ス は,CPUの バ ス に 直 接 接 続 さ れ,480MB/sと い うCPUの 能 力 に 対 して 非 常 に 高 速 なPE間 通 信 速 度 を 有 し て い る.プ ロ セ ッサ 間 通 信 は 通 信 リ ン ク ご と に 並 行 に 行 わ れ る た め, 1PEノ ー ドは 合 計2.88GB/sの 実 効 転 送 能 力 が あ る.

各PEノ ー ド は,Compaq社 の 高 速RISCプ ロ セ ッサAlpha21164を 核 と し て お り,C-chip(メ モ リ/デ ー タ制 御),R-chip(ネ ッ トワ ー ク ・ル ー タ),及 び64MBの ロ ー カ ル メ モ リ か ら構 成 さ れ て い る.導 入 当 時,Alpha21164aプ ロ セ ッ サ は,非 常 に 高 い ク ロ ッ ク 周 波 数 で 作 動 す る,世 界 最 速 の マ イ ク ロ プ ロ セ ッサ で あ り,ノ ー ド当 り300MHzのAlphaチ ッ プ を 用 い て600MFLOPS,1200MIPSの 演 算 性 能 を 実 現 し て い る. 本 計 算 機 の 特 徴 の1つ と し て,CPUと メ モ リ 問 の デ ー タ 転 送 能 力 が 非 常 に 高 い こ と が 挙 げ ら れ る.ス ト リ ー ム バ ッ フ ァ やEレ ジ ス タ と い う 高 速 な デ ー タ供 給 を 行 う機 構 に よ っ て,1.2GB/sと い う 高 い デ ー タ 転 送 能 力 を 達 成 し,実 際 の 利 用 に お い て も高 い 演 算 性 能 を 有 し て い る. ソ フ ト ウ ェ ア は,強 力 な 資 源 割 当 て 機 能 を 持 つOSUNICOS/mk,デ ー タ パ ラ レ ル モ デ ル に 基 づ くFortran90や 分 散 処 理 が 可 能 なC++/Cが 利 用 可 能 で あ る.CM5 の 時 に は,PE間 通 信 ラ イ ブ ラ リ は 標 準 化 さ れ た も の が な く,ThinkingMachines社 独 自 の も の で あ っ た が,T3Eで は,標 準 化 さ れ た 並 列 通 信 ラ イ ブ ラ リ と し てPVM やMPIが 利 用 可 能 と な っ て い る.ま た,数 値 演 算 ラ イ ブ ラ リ と し て,IMSLが 用 意 さ れ て い る.

表5:T3E-1200Eの 構 成

相互結合網

ノ ー ド数 ノ ー ド プ ロ セ ッ サ ロ ー カ ル メ モ リ

PE間

通信 速度

ノー ド演算 能力/PE間

通 信速 度

3DTorus 128

Alpha21164a(600MHz,1.2GFIops)

512MB/node

650MB/s

1.85MFIops/(MB/s)

2.4Cray-T3E-1200E CrayT3E-1200Eは,T3Eの 機 種 更 新 に よ っ て 導 入 さ れ た,本 学 の 数 値 計 算 系 の 超 並 列 シ ス テ ム の3世 代 目 の 機 種 で あ る.表5にT3E-1200Eの 構 成 を示 す.2世 代 目 のT3Eの グ レ ー ドア ッ プ 版 で あ り,ハ ー ド ウ ェ ア の 殆 ん ど の 機 能 はT3Eと 全 く 同 一 で あ る.し か し な が ら,CPUの ク ロ ッ ク 速 度 が 二 倍 と な っ て お り,そ れ に 合 せ て メ モ リ容 量 やPE間 通 信 速 度 も 高 速 化 さ れ て い る. プ ロ セ ッサ は,600MHzのAlpha21164aチ ップ で あ り,ノ ー ド当 り1200MFLOPS, 2400MIPSの 演 算 性 能 を 実 現 し て い る.ま た,PE間 通 信 が 高 速 化 さ れ て お り,通 信 リ ン ク 当 りT3Eの480MB/sに 対 し て650MB/sの 通 信 速 度 を 有 し て い る. ソ フ トウ ェ ア は,若 干 の 改 訂 は あ る も の の,T3Eの ソ フ トウ ェ ア と 同 一 の も の と な っ て い る.

2.51BMRS/6000SP

本 シ ス テ ム は,デ ー タ ベ ー ス 処 理 の 研 究 を 目 的 と し た 超 並 列 シ ス テ ム で あ り, nCUBE2,nCUBE3に 続 く3世 代 目 の デ ー タ ベ ー ス 処 理 研 究 用 超 並 列 シ ス テ ム で あ る.こ の 他 に,暗 号 系 の 研 究 を 目 的 と し た 大 規 模 問 題 解 決 教 育 シ ス テ ム と 統 合 さ れ て お り,こ れ ら は 相 互 に 乗 り 入 れ る こ と が 可 能 と な っ て い る.表6に,シ ス テ ム の 構 成 を示 す.本 シ ス テ ム の 特 徴 は,デ ー タ ベ ー ス や 暗 号 処 理 に 多 用 さ れ る 整 数 演 算 性 能 に 優 れ るCPUを 用 い て い る こ と と,並 列 デ ー タ ベ ー ス 処 理 を 可 能 と す る た め, ノ ー ドご と に ロ ー カ ル デ ィス ク を 有 し て い る こ と で あ る.こ れ ら の ノ ー ド を 高 速 ス イ ッチ に よ る 相 互 結 合 網 で 結 合 し た 分 散 メ モ リ 型 の 超 並 列 計 算 機 と な っ て い る.シ ス テ ム の ノ ー ドは2つ に 大 別 さ れ,デ ー タ ベ ー ス 処 理 や 暗 号 の 解 読 な ど を得 意 と す るPPC604eノ ー ド,お よ び 数 値 計 算 や 高 速 な1/0処 理 を 得 意 とす るPower3ノ ー 6

表6:RS/6000SPの 構 成

相互結合網

ノ ー ド数 ノ ー ド プ ロ セ ッ サ ロ ー カ ル メ モ リ

PE間

通信 速度

ノー ド演 算 能力/PE間

通信 速 度

3DTorus 64十4

PPC604e(332MHz,664MFIops)x4(64node)

Power3(222MHz,888NIFIops)x8(4node)

512MB/node

150MB/s

4.42MFIops/(MB/s)

ドか ら 構 成 さ れ て い る. PPC604eノ ー ド部 分 は,64ノ ー ドが 高 速 ス イ ッ チ に よ り結 合 さ れ,各 ノ ー ドは, 332MHzのPPC604e4CPU,512M共 有 メ モ リ,ロ ー カ ル デ ィ ス ク か ら 構 成 さ れ て い る.Power3ノ ー ド部 分 は,PPC604eノ ー ド部 分 は,4ノ ー ドか ら成 り,各 ノ ー ドは,222MHzのPower38CPU,8GB共 有 メ モ リ,並 列 ロ ー カ ル デ ィ ス ク か ら構 成 さ れ て い る. プ ロ セ ッサ 間 通 信 は,シ ン グ ル ス テ ー ジSPス イ ッチ に よ り行 な わ れ る.相 互 結 合 網 へ の 接 続 は,ノ ー ド上 のPCIバ ス の イ ン タ ー フ ェ ー ス カ ー ド を 介 し てSPス イ ッチ に 結 合 さ れ る.PCIバ ス を 介 し て い る た め,多 様 な シ ス テ ム に 対 応 で き,本 シ ス テ ム の よ う に 異 な る 種 類 の ノ ー ドの 混 載 シ ス テ ム や,相 互 結 合 網 部 分 だ け の ア ッ プ グ レ ー ド な ど が 可 能 と な っ て い る 反 面,通 信 速 度 はPCIの 速 度 に 制 限 さ れ, 特 に 通 信 の レ イ テ ン シ が 大 き い と い う 欠 点 が あ る.

3相

互 結 合 網 の通 信 速 度 と シス テ ム性 能

3.1は じ め に 本 節 で は,超 並 列 シ ス テ ム の 相 互 結 合 網 の 通 信 速 度 が シ ス テ ム 全 体 の 性 能 に 与 え る 影 響 に つ い て 議 論 す る.PE間 通 信 速 度 の 影 響 を 調 べ る た め に は,CPUや メ モ リ 等 の 性 能 が 同 一 で,PE問 通 信 速 度 を 変 化 さ せ る こ とが 可 能 な 実 験 シ ス テ ム を 用 い る の が 最 も理 想 的 で あ る.し か し な が ら,実 シ ス テ ム を構 築 す る の は 困 難 で あ り, シ ミ ュ レ ー シ ョ ン に よ る 評 価 で は,非 常 に 単 純 化 し た ベ ン チ マ ー ク と な る た め,現 実 の シ ス テ ム 性 能 を 評 価 す る こ と は 難 し い.情 報 科 学 セ ン タ ー で は,幸 いT3Eお

よ びT3E.1200Eと い う,CPUの ク ロ ッ ク 速 度 とPE間 通 信 速 度 の み が 異 な る 超 並 列 シ ス テ ム を 相 次 い で 導 入 した の で,こ の シ ス テ ム に よ っ て 標 準 的 な ベ ン チ マ ー ク に よ る 評 価 を 行 な い,相 互 結 合 網 の 通 信 速 度 が シ ス テ ム 全 体 に 及 ぼ す 影 響 に つ い て 考 察 す る. 3.2測 定 環 境 3.2.1CRAY-T3Eシ ス テ ム 評 価 に 用 い たCRAY-T3EとCRAY-T3E/1200Eに つ い て 概 略 を 述 べ る ・CRAY-T3Eは,CRAYInc.(旧CRAYResearch)が 開 発 し た 超 並 列 シ ス テ ム で あ る.こ れ に 対 し,CRAY-T3E/1200Eは,CRAY-T3EのCPUの ク ロ ッ ク 速 度 とPE問 通 信 速 度 を 向 上 さ せ て お り,シ ス テ ム の 特 徴 は 同 一 で あ る.CRAY-T3EとCRAY-T3E/1200Eに 共 通 す る 基 本 的 な シ ス テ ム の 特 徴 は,以 下 の 通 りで あ る.各PEは, 1つ のCPU,ロ ー カ ル メ モ リ,お よ び ネ ッ トワ ー ク イ ン タ ー フ ェ ー ス か ら構 成 さ れ る.CPUは,Alpha21164(EV5)を 用 い て お り,こ れ をCRAY-T3Eは300MHz, CRAY-T3E/1200Eは600MHzで 駆 動 して い る.一 次 お よ び 二 次 キ ャッ シ ュ をCPU 内 に 有 し て い る が,CPU外 に は 三 次 キ ャッ シ ュ は 持 た な い.代 わ り に ベ ク トル パ イ プ ラ ン の 概 念 を 取 り込 ん だStreamBufferと 呼 ば れ る 定 ス ト ラ イ ド(4段)の パ イ プ ラ イ ン 型(6本)の バ ッ フ ァ を持 ち,二 次 キ ャッ シ ュ の キ ャッ シ ュ ミ ス 時 に 先 読 み に よ る デ ー タ 転 送 を 行 な う.グ ロ ー バ ル ・ア ド レ ス 空 間 へ の デ ー タ ア ク セ ス の た め に, E-Registerと 呼 ば れ る バ ッ フ ァ を 有 し て お り,こ れ を 用 い て 全 て の デ ー タ(ロ ー カ ル/リ モ ー ト)に ア ク セ ス で き る.例 え ば,GatherやScatter等 の 操 作 で は 実 際 に は 通 信 を 行 な わ ず,直 接 リ モ ー トメ モ リ に 対 し て 操 作 が 行 な わ れ る.PE間 の 相 互 結 合 網 は,三 次 元 の トー ラ ス 構 造 の ネ ッ トワ ー ク トポ ロ ジ で あ る. 表7に,CRAY-T3Eお よ びCRAY-T3E/1200Eの シ ス テ ム の 性 能 を 示 す.表 中, 8

表7:CRAY-T3EとCRAY-T3E/1200Eの 性 能

CPU(Clock}

Primarycachesize(Bandwidth)

Secondarycachesize(Bandwidth)

StreamBufferBandwidth MainMemory InterconnectBandwidth CRAY-T3E

CRAY-T3E/1200E

EV5(300MHz)EV5(600MHz)

4KB(4.8GB/s)4KB(9.6GB/s)

96KB(4.8GB/s)96KB(9.6GB/s)

600MB/s

600MB/s

64MB 512MB

480MB/s

650MB/s

450MBls→650MB/s な8『Bls 9.6GB/s

図2:PE内

の概 要お よび性能

CRAY-T3EとCRAY-T3E/1200Eで 性 能 が 異 な る 部 分 を 太 字 で 示 して あ る.ま た 各PE内 部 の 概 念 図 を 図2に 示 し た.CPUの ク ロ ッ ク 速 度 向 上 に よ っ て 演 算 性 能 お よ びCPUの 内 部 キ ャッ シ ュ 速 度 は100%向 上 して い る.し か し,メ イ ン メ モ リ へ の 帯 域 等,CPUの チ ッ プ 外 の 性 能 は 同 一 と な っ て い る.ネ ッ トワ ー ク 性 能 は,通 信 帯 域 の 増 加 に よ っ て 約35%向 上 し た.ま た,CRAY-T3Eシ ス テ ム の 通 信 機 構 は,PE(CPU)の 動 作 と密 接 に 関 連 し た シ ス テ ム で あ る た め,通 常 のPCク ラ ス タ 等 よ り も 通 信 遅 延 が 非 常 に 少 な い シ ス テ ム と な っ て い る. ソ フ トウ ェ ア 環 境 と し て は,ど ち ら もProgramingEnvironmentVersion3.4を 用 い た.こ れ にMPI,Fortran90お よ びCコ ン パ イ ラ が 含 ま れ て い る.コ ン パ イ ル ・オ プ シ ョ ン は,全 て の 場 合 に つ い て"-03-dp",つ ま り最 適 化 レ ベ ル を 最 高, デ フ ォ ル トの 精 度 を 倍 精 度 の 指 定 と し た.

3.2.2NASParallelBenchmark つ ぎ に,NASParallelBenchmark(NPB)に つ い て 概 略 を 述 べ る.NPBは,NASA AmesReseearchCenterのNAS(NumericalAerodynamicsSimulation)Lab.で 開 発 さ れ た 熱 流 体 関 連 の 科 学 技 術 計 算 の ベ ン チ マ ー ク で あ る. NPBは,5つ の 主 要 ア ル ゴ リ ズ ム の カ ー ネ ル と3つ の 数 値 流 体 計 算 コ ー ド(ア プ リ ケ ー シ ョ ン コ ー ド:圧 縮 性 流 体 を 擬 似 的 に 計 算)か ら な る.そ れ ぞ れ,並 列 計 算 コ ー ド と 逐 次 計 算 コ ー ドか ら な り,並 列 計 算 コ ー ド は,Fortran77とMPI,逐 次 計 算 コ ー ド は,Fortran77で 記 述 さ れ て い る.ま た,問 題 サ イ ズ と し て4種 類 用 意 さ れ て お り,ベ ン チ マ ー ク コ ー ド は,問 題 サ イ ズ(メ モ リ サ イ ズ)の 大 き さ に よ っ て CLASS分 け が な さ れ て い る.評 価 で 用 い たCL,ASSは,問 題 サ イ ズ が 小 さ い 順 に CLASSW,A,B,Cで あ る. 以 下 に 各 ベ ン チ マ ー ク コ ー ド の 概 要 を 示 す. カ ー ネ ル ベ ン チ マ ー ク

CG正

値対 称 大規模 疎行 列 の最小 固有値 を共役勾 配 法 に よ り求 め るプロ グラ

ムであ る.非 構 造格子 を用 い た流体 アプ リケー シ ョンで 良 く用 い られ る.

計 算 は,多

くの メモ リ帯域 を必 要 とす る.同 一 長 のベ ク トルデ ー タの

通 信 と,内 積 を 得 る た め の1デ ー タ の 通 信 が 行 な わ れ る.

EP乗

算合 同法 に よって一様 な正規乱数 を生成す るプロ グラムで ある.モ ンテ

カル ロ法で よ く用 い られ,並 列 処理 では通信 が ほ とん ど発 生 しない.そ

の た め,浮 動 小 数 点 演 算 性 能 の み を 示 す. FTFFTを 用 い て 三 次 元 偏 微 分 方 程 式 を 解 く プ ロ グ ラ ム で あ る.FFTを 各 次 元 毎 に 解 い て い く た め 配 列 を 持 ち 替 え る.特 にFTは 複 素 数 型 の 配 列 をMPI-Alltoallに よ り通 信 す る た め,通 信 負 荷 が 非 常 に 大 き い. IS大 規 模 な 整 数 値 ソ ー トを 行 う プ ロ グ ラ ム で あ る.粒 子 法 等 で よ く用 い ら れ る.粒 子 を 再 び 適 切 な セ ル に 割 り当 て る た め の ソ ー トを行 な う.MPI.All toallvの 負 荷 が 通 信 の 多 く を 占 め る.こ の ベ ン チ マ ー ク の みC言 語 で 記 述 さ れ て い る. MG三 次 元Poisson方 程 式 をMultigrid法 に よ っ て 求 め る プ ロ グ ラ ム で あ る.非 圧 縮 流 体 計 算 中 に 現 れ るPoisson方 程 式 を 解 くた め に 用 い ら れ る. メ ッ セ ー ジ 長 が 非 一 様 な 通 信 を 行 な う が,計 算 負 荷 は 高 く な い. ア プ リケ ー シ ョ ン ベ ン チ マ ー ク 10

80 70 bo SO O40 30 20 io O CRAY-T3E/1200E(Mop/s/PE)QPerformanceratio QCRAY-T3E(Mop/s/PE)10.85 BTSPLUCGFI'MG 4 ヨ   の 、α o Σ 1 O 順 一 邸 ﹄ O Q 信 邸 已 ﹂ ε ﹄ O 畠 10 4 ・ 2 α α 0 o.00 EPIS o.g O 眉 邸 ﹂ O Q 目 邸 繧 ﹂ ρ U﹄ O ﹂ 1 0 4 2 α α α o.o 図3:1PEに お け る 性 能(CLASSW) BTブ ロ ッ ク3重 対 角 方 程 式 をADI法 を 用 い て 解 く プ ロ グ ラ ム で あ る. SP5重 対 角 方 程 式 を ス カ ラ ーADI法 を 用 い て 解 く プ ロ グ ラ ム で あ る. BT,SPと も に 物 理 量 等 の 格 子 面 デ ー タ の 送 受 信 を 行 な い,一 部 の デ ー タ通 信 に 関 し て 通 信 隠 蔽 が 行 な わ れ て い る.演 算 量 は,CLASSWを 除 い て,BTが 多 い. LU上 下 三 角 行 列 を 対 称SOR法 を 用 い て 解 く プ ロ グ ラ ム で あ る.並 列 化 に は パ イ プ ラ イ ン処 理 が 用 い ら れ,通 信 処 理 の 隠 蔽 が 行 な わ れ る.CLASS Wで は 最 も 演 算 量 が 多 い. 計 測 結 果 と し て,MoP/s(MegaOPerationperSecond)値 が 得 ら れ る.EPとIS 以 外 のMoP/s値 は,ほ ぼMFIoP/sと 同 等 の 値 で あ る.EPのOperationは,乱

数 生 成 数 で あ り,ISのOperationは,整 数 演 算 の 数 で あ る た め,プ ロ グ ラ ム 中 で 実 行 さ れ る 浮 動 小 数 点 演 算 は 極 め て 少 な い.こ の こ と か ら,EPとISに 関 し て の MOP/s値 は,MFlOP/sと 異 な る 処 理 速 度 の 指 標 と し て 考 え る 必 要 が あ る ・ 3.3結 果 と考 察 3.3.1CPUク ロ ッ ク 周 波 数 の 向 上 CPUの ク ロ ッ ク 速 度 向 上 に よ る シ ス テ ム 性 能 へ の 寄 与 に つ い て 検 討 す る.CPU の ク ロ ッ ク 速 度 の 差 に よ る 性 能 向 上 を 示 す た め に,1PEの み を 用 い て(つ ま りPE 間 通 信 を 行 な わ な い で)CRAY-T3Eお よ びCRAY-T3E/1200E上 に お け る 並 列 計 算 コ ー ドの 実 行 速 度 を 評 価 した.評 価 の 結 果 を 図3に 示 す.横 軸 は ベ ン チ マ ー ク プ ロ グ ラ ム の 種 類,左 縦 軸 はMop/s,右 縦 軸 は 次 式 で 定 義 さ れ る性 能 比(Performance

ratio)を 示 し た. Mop/s/PE(CRAY-T3E/1200E) -1 _.0(1) Performanceratio= Mop/s/PE(CRAY-T3E) CRAY-T3E/1200EはCRAY-T3Eの2倍 の ク ロ ッ ク 周 波 数 な の で,理 想 状 態 で は,2倍 の 性 能 比(Performanceratio=1.0)と な る が,メ モ リ な ど の 動 作 速 度 は 向 上 し て い な い た め,こ れ よ り は 小 さ い 性 能 比 と な る.CPUに お け る 演 算 量 が 大 き い 場 合 や,キ ャ ッ シ ュ メ モ リ が 有 効 に 動 作 す る 場 合 に お い て は 大 き な 性 能 比 が 得 ら れ,メ モ リへ の ア ク セ ス が 多 い 場 合 は,性 能 比 は 小 さ く な る こ とが 予 想 さ れ る. 図3に 示 す よ う に,EPは 最 も大 き な 性 能 比 が 得 ら れ た.EPは,メ モ リ ア ク セ ス に対 し て 極 め て 演 算 量 が 大 き く,CPUの ク ロ ッ ク 速 度 向 上 の 効 果 が 現 れ や す い ベ ン チ マ ー ク で あ る と 言 え る.こ の た め,PE単 体 の 性 能 向 上 が 高 い 結 果 と な っ て い る.一 ・方,CGとISは,他 の ベ ン チ マ ー ク と 較 べ て,性 能 向 上 が30%以 下 と な り,性 能 向 上 が 低 い.両 ベ ン チ マ ー ク と も,メ イ ン メ モ リへ の 広 範 な ア ク セ ス が 行 な わ れ る.CRAY-T3E/1200Eの メ モ リ帯 域 の 性 能 が 上 が っ て い な い た め,CPUの ク ロ ッ ク 速 度 向 上 に よ る 寄 与 が 少 な い と考 え ら れ る.こ れ 以 外 の 場 合,FTとMG が40%程 度,BT,SP,LUが35%程 度 の 速 度 向 上 が 得 ら れ た.EPを 除 い た 平 均 的 なPEの 性 能 向 上 は,お よ そ35%で あ る. 3.3.2PE間 通 信 性 能 本 節 で は,PE間 通 信 の 性 能 向 上 を 検 討 す る.各 ベ ン チ マ ー ク の 結 果 を並 べ る だ け で は,シ ス テ ム の 性 能 向 上 はCPUの 性 能 向 上 と 通 信 性 能 が 両 方 含 ま れ た 状 態 と して あ ら わ さ れ る.CPUの 性 能 向 上 は3.3.1節 で 明 ら か に な っ て い る.そ の 結 果 を 元 に,シ ス テ ム 全 体 の 性 能 比(Ptmp)か ら 既 知 のCPU性 能 向 上 の 割 合(pCPU)を 相 殺 す る こ と に よ り,通 信 性 能 比(瓦 。mm)の 向 上 を 類 推 す る こ と が で き る.つ ま り, 次 式 を 用 い て 間 接 的 に 推 測 す る. 瓦 。mm=PtmP-1コCPU

(2)

pCPUと し て,各 ベ ン チ マ ー ク をN個 のPEを 用 い て 並 列 化 す る と,PE当 りの 演 算 量 が 基 本 的 に は1/Nと な る.比 較 の た め,演 算 量 が3.3.1節 のCLASSWと 同 程 度 に な る 問 題 サ イ ズ とPE数 を 用 い る 。例 え ば,BTのCLASSW,1PEで 実 行 す る 際 の 演 算 量 は,BTをCLASSA,16PEで 実 行 す る 場 合 の 演 算 量 と ほ ぼ 同 一 で あ る.こ の 場 合,図3に 示 し たCLASSW,1PEのCPUの 性 能 向 上 比PCPUが 分 か っ て い る の で,CLASSA,16PEに よ るCRAY-T3EとCRAY-T3E/1200Eの 12 噂… 一』欄一 嗣 ■ ■■ ■■噸 ■■■ 圏■ ■■ ■ ■■ ■■■ ■ ■■■ ■ ■■■ ■

胴 80 70 60 崔50 040 30 20 10 0 ■CRAY-T3El200E(Mop/s1PE)口Performanceratio BTSPCGFTMG FE=100PE=25PE=64PE=64PE=64 1.0

:1:1

0.4 a O.2 o.o 図4:シ ス テ ム 全 体 の 性 能 比(CLASSB) 0.5 4 3 2 ﹂ 0 0 0 0 0 噛一 帽 ﹄ O Q 口 ￠ ∈ ﹄ O } ﹄ O 山 o.o BT SP CG Fr

且

J MGideal

図5:PE問

通信 性 能 に よ る性 能向上 率(CLASSB)

性 能 比Ptmpを 求 め,こ こ か らPtmp-'.PCPUを 計 算 し,間 接 的 に 通 信 性 能 比 瓦 。mm を 評 価 で き る. PE間 通 信 性 能 を 評 価 す る た め,NPBの う ち で 通 信 処 理 の 振 る 舞 い が 明 確 な ベ ン チ マ ー ク プ ロ グ ラ ム を 用 い る.LUは,通 信 隠 蔽 処 理 を 行 な っ て い る た め,理 論 的 に は 通 信 時 間 が 陽 に あ ら わ れ な い.ま た,ISもMPI-Alltoallvの 挙 動 が 明 確 で な い.ま た,EPは,並 列 実 行 時 に も通 信 が 発 生 し な い 。 よ っ て,LU,IS,EP以 外 の ベ ン チ マ0ク プ ロ グ ラ ム を 用 い る.用 い た 問 題 サ イ ズ はCLASSBと し,PE数 はCLASSWの1PEの メ モ リ ワ ー ク サ イ ズ と 同 程 度 の 量 と な る よ う に,ベ ン チ マ ー ク ご と に 調 整 す る.用 い たPE数 は,BTで100PE,SPで25PE,CGで 64PE,FTで64PE,MGで64PEで あ る.図4に,ベ ン チ マ ー ク プ ロ グ ラ ム

の 各PE数 で の 性 能 を 示 す.横 軸 に 各 ベ ン チ マ ー ク プ ロ グ ラ ム とPE数,左 縦 軸 に Mop/s/PE,右 縦 軸 にPerformanceratioを 示 す.こ れ に 式(2)を 適 用 し,図4か ら 図3の"1PEで の 性 能 比"を 差 し引 い て 推 測 さ れ た 通 信 性 能 比 瓦 。mmを 図5に 示 す. 図5に 示 さ れ る よ う に,FTの 通 信 性 能 向 上 率 が 最 も高 い.FTは 複 素 型 の 大 き な 配 列 デ ー タ を 多 く通 信 す る た め,通 信 帯 域 の 向 上 が 最 も 有 効 に 働 い た と考 え ら れ る.通 信 性 能 の 向 上 率 は,CRAY-T3EとCRAY-T3E/1200Eの 通 信 帯 域 の 性 能 差 に 近 い 値 と な っ て い る.そ の 他 の 場 合 で は,お よ そ3∼10%程 度 の 通 信 性 能 向 上 が 見 ら れ た.FT以 外 で は,通 信 回 数 が 多 い た め,通 信 性 能 の 多 く は 通 信 帯 域 で は な く ネ ッ ト ワ ー ク の レ イ テ ン シ ー に 依 存 す る も の と考 え ら れ る.SP,CG,お よ び MGの 結 果 よ り,平 均 的 な ア プ リ ケ ー シ ョ ン プ ロ グ ラ ム を 実 行 し た 場 合 の 通 信 性 能 の 向 上 は,お よ そ5%前 後 と推 測 さ れ る. 3.4ま と め 本 節 で は,本 学 情 報 科 学 セ ン タ ー のT3Eお よ びT3E-1200Eを 用 い て,超 並 列 シ ス テ ム の 相 互 結 合 網 の 通 信 速 度 が シ ス テ ム 全 体 の 性 能 に 与 え る 影 響 に つ い て 議 論 し た.実 用 的 な ア プ リ ケ ー シ ョ ン に よ る 通 信 性 能 の 影 響 を調 べ る こ と は 難 し い た め,T3Eお よ びT3E-1200Eに お い て 標 準 的 な 並 列 ベ ン チ マ ー ク プ ロ グ ラ ム で あ る NASAParallelBenchmarkを 用 い て 測 定 を 行 な い,シ ス テ ム 全 体 の 性 能 向 上 か ら CPUの ク ロ ッ ク 速 度 向 上 に よ る 処 理 速 度 の 改 善 を 差 し 引 く こ と に よ り,通 信 速 度 が シ ス テ ム の 性 能 に 与 え る 影 響 を 推 測 し た. 評 価 実 験 の 結 果,大 き な 配 列 デ ー タ を 相 互 に 交 換 す るFFTな ど の ア プ リ ケ ー シ ョ ン で は,CPU性 能 よ り もPE間 通 信 性 能 が 律 速 で あ り,両 シ ス テ ム のPE間 通 信 速 度 の 差 に か な り近 い 性 能 の 差 が 現 わ れ た.平 均 的 な ア プ リ ケ ー シ ョ ン で は,通 信 の バ ン ド幅 よ り も,む し ろ 通 信 の レ イ テ ン シ ー に 大 き く依 存 す る こ と が 推 測 さ れ た. 以 上 の こ と か ら,次 世 代 の 超 高 速 超 並 列 シ ス テ ム で は,非 常 に 低 レ イ テ ン シ ー の 高 速PE間 通 信 を 行 な う必 要 が あ る こ と が 分 か っ た.

4相

互結 合 網 の トポ ロジ

4.1は じ め に 本 章 で は,科 学 技 術 計 算 に 適 す る 相 互 結 合 網 の トポ ロ ジ に つ い て 議 論 す る. 科 学 技 術 計 算 の 多 く は2次 元 ま た は3次 元 構 造 の デ ー タ を 対 象 とす る た め,格 子 型 の 結 合 網 と適 合 しや す い.し か し,格 子 結 合 網 は,シ ス テ ム の 規 模 が 大 き く な る と 通 信 性 能 が 急 速 に 低 下 す る と い う 問 題 が あ る.そ こ で,ノ ー ド数 の 増 加 に 応 じ て1 ノ ー ド当 りの リ ン ク 数(次 数)を 増 加 さ せ る ハ イ パ ー キ ュ ー ブ 網 が 提 案 さ れ,nCUBE な ど の 中 規 模 並 列 処 理 シ ス テ ム に 実 装 さ れ て き た.ハ イ パ0キ ュ ー ブ 網 は,平 均 距 離 な ど の 通 信 性 能 に 優 れ,格 子 結 合 網 を は じ め 様 々 な 他 の 結 合 網 を 内 包 で き る 利 点 を 持 つ.し か し,大 規 模 な シ ス テ ム で は ノ ー ドの 次 数 が 非 常 に 大 き く な り,実 装 が 困 難 に な る と い う 問 題 点 が あ る. 結 合 網 を 実 装 性 の 観 点 か ら 考 え る と,配 線 密 度 に よ る チ ッ プ 面 積 や 配 線 の 容 易 さ か ら 格 子 結 合 網 は 重 要 性 を増 して い る.ま た,格 子 結 合 網 は 故 障 回 避 に 関 す る 多 く の 研 究 が な さ れ,実 装 性 に 関 し て 優 れ た 性 能 を 有 し て い る[4].そ こ で,近 年 で は,超 並 列 計 算 機 用 の 相 互 結 合 網 と し て,格 子 結 合 網 や トー ラ ス 網 を 基 本 と し て,遠 距 離 ノ ー ド間 の 結 合 を 付 加 し た 多 くの 相 互 結 合 網 が 提 案 さ れ て い る[5,6,7]. RDT網[5]は,基 本 トー ラ ス 網 に 対 して,グ リ ッ ド 間 隔 をV至 η(nは 整 数)倍 し450 傾 む け て 再 帰 的 に 上 位 の トー ラ ス を 構 成 す る 相 互 結 合 網 で あ る.RDTは,階 層 的 な 構 造 を 持 ち,直 径 も比 較 的 小 さ く,木 構 造 を 内 包 し 同 報 通 信 な ど が 容 易 に 行 え る 利 点 を 持 つ.し か し な が らRDT網 は,斜 め 方 向 の 配 線 を 含 む た め,故 障 回 避 が 難 し く な る な ど の 問 題 が あ る. 2次 元 のPackedExpornentialConnections(PEC)網[6]は,基 本 格 子 網 に 対 して, グ リ ッ ド間 隔 を2n(nは 整 数)倍 した 格 子 を,互 い に 重 な ら な い よ う に 再 帰 的 に 重 ね 合 せ て 構 成 す る 相 互 結 合 網 で あ る.2次 元 格 子 網 上 で,グ リ ッ ド間 隔 が 大 き な 格 子 網 を用 い る こ と に よ り木 状 網 及 び ハ イ パ ー キ ュ ー ブ 網 の エ ミ ュ レ ー シ ョ ン が 可 能 で あ る.し か し な が ら,2次 元PEC網 は 表 を 用 い て 定 義 を行 な っ て お り,直 径 や ル ー テ ィ ン グ ア ル ゴ リ ズ ム も 明 ら か で は な い.2次 元PEC網 は,1次 元PEC網[7]を 組 み 合 わ せ て 得 ら れ る.1次 元PEC網 に つ い て は,1次 元PEC網 の 直 径 と,特 定 の ノ ー ド か ら の ル0テ ィ ン グ ア ル ゴ リズ ム,及 び ル ー テ ィ ン グ の ス テ ッ プ 数 の 上 界 が 示 さ れ て い る が,任 意 の ノ ー ド間 の 効 率 的 な ル ー テ ィ ン グ に つ い て は 未 解 決 で あ る. 本 章 で は,ト ー ラ ス 結 合 網 を 基 に,ノ ー ド間 距 離 の 異 な る バ イ パ ス リ ン ク を 再 帰 的 に 付 加 し たShiftedRecursiveTorus(SRT)網[8,9,10,11,121に つ い て,ネ ッ ト

馴 ワ ー ク 性 能 に つ い て 検 討 す る.SRTは1次 元 か ら定 義 で き,2次 元 へ の 拡 張 が 容 易 で あ る.こ こ で は,1次 元SRTの 構 成 法 を 示 し,ネ ッ トワ ー ク 直 径 を 求 め る.1次 元 のSRTとPEC網 は 類 似 し た 結 合 網 で あ る.し か し な が ら,1次 元PEC網 の ル ー一 テ ィ ン グ で は,経 由 リ ン ク を 動 的 計 画 法 に よ っ て 求 め て い る の に 対 し,1次 元SRT で は ノ ー ド間 距 離 に よ っ て 一 義 的 に 決 定 す る 手 法 を 示 す.第3章 で1次 元SRTを2 次 元 に 拡 張 し,表 を 用 い な い 式 に よ る 定 義 を 示 す.ま た,直 径 や ル ー テ ィ ン グ ア ル ゴ リ ズ ム を 示 す.2次 元SRTは 階 層 的 な トー ラ ス だ け で 構 成 で き,斜 め 方 向 の リ ン ク な ど を 持 た な い 簡 単 な 構 造 を 持 ち な が ら,従 来 の 結 合 網 と 比 較 し て 遜 色 な い ネ ッ ト ワ ー ク 性 能 を 持 つ こ と を 明 か に す る. 4.21次 元SRT 4.2.1構 成 原 理 1次 元SRTは 環 状 網 を 基 に 構 成 さ れ る.通 信 性 能 向 上 の た め,遠 隔 ノ ー ド と 直 接 接 続 さ れ る リ ン ク を,各 ノ ー ドの 次 数 が 一 定 と な る よ う に,環 状 網 に 重 ね 合 わ せ る. ノ ー ド数N(N=2n)か ら 成 る 環 状 網 で,あ る ノ ー ド を 番 号0と し,ノ ー ドを 昇 順 に 番 号 付 け,次 の 基 本 トー ラ ス を 定 義 す る. 定 義1(基 本 トー ラ ス)Nノ ー ドか ら 成 る 基 本 トー ラ ス の ノ ー ド(o≦x<N)は, 隣 接 す る 左 右 の ノ ー ド(x土1)modNと 結 合 さ れ る.ロ トー ラ ス の 両 端 は 互 い に 結 合 さ れ る の で,ノ ー ド0の 隣i接 ノ ー ドは1とN-1で あ る.基 本 トー ラ ス を 構 成 す る 結 合 リ ン ク を レ ベ ル0の リ ン ク と呼 ぶ. トー ラ ス 結 合 網 の 直 径 お よ び 平 均 距 離 を 短 縮 す る た め に,基 本 トー ラ ス に バ イ パ ス リ ン ク を 付 加 し,上 位 トー ラ ス を 構 成 す る. 1D-SRTの 考 え 方 は 次 の 通 りで あ る.基 本 トー ラ ス か ら,xlmod2=1を 満 す ノ ー ド群 銑 を 取 り出 す.こ の ノ0ド 群 を レ ベ ル1の ノ0ド と 呼 ぶ.レ ベ ル1の ノ ー ド を バ イ パ ス リ ン ク に よ っ て 環 状 に 結 合 す る.同 様 に 基 本 トー ラ ス か ら,x2mod4=2 を 満 す レ ベ ル2の ノ ー ド群x2を 取 り 出 す.レ ベ ル2の ノ ー ド を バ イ パ ス リ ン ク に よ っ て 環 状 に 結 合 す る. レベ ル3以 上 の リ ン ク も,同 様 の 手 続 き を 再 帰 的 に 行 な う こ と に よ っ て,定 義2が 定 ま る. 定 義2(1D-SRT)N=2nノ ー ドか ら成 る 基 本 トー ラ ス か ら,ノ ー ド番 号 が xtmod2t=2t-i

₍₃₎

16

7 8 6 5 4 3 2 1031 30 29 28 27 9 5 26 威 10 11 12 13 14 1516 17 18 24 23 22 ●Level-Onode 21●Leve1 _-lnode 20●Leve1 -2node l9●Leve1-3node Level-4node ●Level-5node 図6:32ノ ー ド か ら 成 る 基 本 型1D-SRT. を 満 す ノ ー ド群xlを 取 り 出 し,環 状 に 接 続 す る.こ の 手 続 き を レ ベ ルZが1か ら lm。、-1ま で 繰 り 返 す.lm。 、 は,基 本 型1D-SRTの 最 大 の レ ベ ル で あ り,lm。 。= lo921V=nで あ る 。 □ 式(3)を 満 す ノ ー ド群 を レ ベ ルZの ノ ー ド と 呼 び,Vと す る.Z≧1の レ ベ ル を 上 位 レベ ル と 呼 ぶ.ノ ー ド0は,ど の よ う なZ≧1で も式(3)を 満 さ な い の で,上 位 レベ ル を 持 た な い.こ の た め,ノ ー ド0の レ ベ ル は0と す る.Uを 環 状 に 接 続 す る リ ン ク を 上 位 リ ン ク と 呼 び,Elと す る.xlは レ ベ ル0の リ ン ク と は 別 に,レ ベ ルZの リ ン ク に よ っ て21離 れ た 同 じ レ ベ ル 数 の ノ0ド((xl土2りmodN)に 接 続 さ れ る.従 っ てxiは, @,±1)m・dN,(xl土21)m・dN の4ノ ー ド に 接 続 さ れ る. こ の よ う に 決 定 さ れ た32ノ ー ドか ら 成 る1D-SRTの 結 合 の 様 子 を 図6に 示 す. ノ ー ドは レベ ル 毎 に2本 の リ ン ク を 持 つ た め,1D-SRTの ど の ノ ー ド も,基 本 トー ラ ス(レ ベ ル0)を 構 成 す る2本 と,上 位 リ ン ク を 構i成 す る2本 の 合 計4本 の リ ン ク を持 つ こ と が 分 る.但 し ノ ー ド0,N/2は 上 位 レ ベ ル が 割 り当 て ら れ な い た め,上 位 リ ン ク が 無 く,レ ベ ル は0と な る.ま た ノ ー ドit4>,3N4に 接 続 さ れ る 上 位 リ ン ク は1 つ で あ り,レ ベ ル はlma忽 で あ る.

4.2.21D-SRTの 直 径 本 節 で は,最 初 に,上 位 レベ ル の 階 層 が 下 位 の 階 層 を 包 含 す る こ と を 示 す.直 径 は 最 上 位 の 階 層 の,最 も離 れ た ノ ー ド間 の 距 離 と考 え れ ば 良 い.包 含 関 係 を 示 す た め に,上 位 ノ ー ドに 対 す る 下 位 ノ ー ドの 位 置 を 求 め,こ れ が 上 位 ノ ー ドの レ ベ ル に 依 存 し な い こ と を 示 す.こ こ で 位 置 と は,レ ベ ル0ト ー ラ ス で の ノ ー ド番 号 の 差 と す る.こ れ を 用 い て,レ ベ ル が 異 な る 最 近 隣 ノ ー ド間 の 距 離(レ ベ ル 問 距 離)が,下 位 ノ ー ドの レベ ル に よ っ て 決 定 さ れ る こ と を 示 す.こ の こ と と,上 位 の 階 層 が 下 位 の 階 層 を 包 含 す る こ と か ら,1D-SRTの 直 径 を レ ベ ル 間 距 離 に よ っ て 表 す.更 に レ ベ ル 間 距 離 を 求 め,1D-SRTの 直 径 を 求 め る. 上 位 レ ベ ル の ノ ー ドに 対 す る 下 位 ノ ー ドの 位 置 が,上 位 ノ ー ドの 位 置 に 依 存 し な い こ と を 示 す.つ ま り,図6に お い て,レ ベ ル1の ノ ー ドは,レ ベ ル3の ノ ー ド4か ら 21・2+21-1離 れ た 位 置 に あ る が,同 じ レ ベ ル の ノ ー ド12か ら も,同 様 に21・j+21-1 離 れ た 位 置 に 存 在 す る. 補 題1(上 位 レベ ル に 対 す る 下 位 レ ベ ル の 位 置)Vkか ら任 意 の ノ ー ド 娠(Z)を 取 り 出 す.賑(の に 対 す る 下 位 レベ ル の ノ ー ドxl∈vの 位 置 は,た>Zで あ る 限 り,鰹(の の 位 置 と レ ベ ル に 依 存 し な い. 証 明xk(i)に 対 す る ノ ー ドxl(の の 位 置 を,ノ ー ド番 号 の 差 と す る.定 義2よ り,レ ベ ル ん_{,Zの ノ ー ド番 号 は,} ∬た(の=2㌦+2κ 一1 xl(フ)=21・ ゴ 十21-1

)

)

4 rO

(

(

と書 け る.こ こ でi,jは そ れ ぞ れ レベ ル κ,Zの ノ ー ドの イ ン デ ッ ク ス で あ る.xk(の か ら 見 たxl(の の 相 対 的 な ノ ー ド番 号 は, 卿)一 蝋 の 一(21・ ブ+21-1)一(2㌦+2k-i) と書 け る.上 式 を 定 義 式(3)に 当 て は め る と, (xl(フ')一 ∬鳶(2))mod21=21-1 (ん>z)

(6)

が 成 立 す る.式(6)は 沸>1で あ れ ば ど の レ ベ ル ん で も成 立 す る の で,ノ ー ド 蝋 の

に対 す る 銑(の の位 置 は,蝋 のの レベ ル及 び ノー ド番 号 に依存 しない.

口 こ の こ と か ら,次 の 系 が 言 え る. 18

系1任 意 の ノ ー ド 蝋 の ∈ 琉 か ら,ω κ(の に 最 も 近 い ノ ー ドxl(の ∈Vま で の,ノ0 ド レ ベ ル の 並 び を5佛,Z)と す る 伝>1).す る と 5(ん,z)=3(κ+m,z)(o<m≦Z_一 κ) と な る.口 つ ま り, s(2,1)=s(3,1)=...=s(lmax,1)=・s(0,1) s(3,2)=...=s(lmax,2)=5(0,2) s(lm。x,lm。x-1)-s(0,lm。 ガ1) の よ う に 書 く こ と が で き る.従 っ て 次 の 系 が 言 え る. 系2任 意 の ノ ー ド 蝋 の ∈ 琉 か ら,蝋 の に 最 も近 い ノ ー ド 銑(の ∈Vま で の 距 離 をd(ん,の と す る6κ>1).す る と d(κ,z)=d(κ+m,z)(o<m≦Z_一 κ) と な る.距 離 と は,レ ベ ル0リ ン ク や 上 位 リ ン ク を 用 い た 蝋 の か らxl(の ま で の 経 路 の ホ ッ プ 数 で あ る.口 d(ん,1)は,ル ー テ ィ ン グ 時 に ノ ー ドの レ ベ ル を 乗 り換 え る(レ ベ ル κか ら レベ ルZの リ ン ク へ 乗 り換 え る)時 の 所 要 ホ ッ プ 数 に 等 し い.系2か ら,全 て の た,Z(κ 〉 の に つ い て,d(k,Z)はd(0,1)が 求 ま れ ば 十 分 で あ る.そ こ で,d(κ,1)をdoll)と 表 記 し,こ れ を レ ベ ル 間 の 距 離 と定 義 す る. 補 題1に よ り,下 位 レ ベ ル の ノ ー ド配 置 は 上 位 レ ベ ル の ノ ー ド配 置 に 包 含 さ れ る の で,1D-SRTの 直 径 は,上 位 の ノ ー ドを 持 た な い ノ ー ド0と こ れ か ら 最 も 離 れ た ノ ー ドN/2ま で の 距 離 と な る.ノ ー ド0とN/2ま で の 距 離 はd(Zm。 。+1,0)に 等 し い. 定 理1ノ ー ド数!Vか ら 成 る1D-SRTの 直 径D(N)は, 工)(1>)≡d(lmax,0)≡do(lo92N).(7) 次 に,レ ベ ル 間 の 距 離doll)を 具 体 的 に 計 算 す る.レ ベ ルz-cの リ ン ク を 通 過 す る と い う 条 件 の も とで の,ノ ー ド0か ら(基 本 トー ラ ス 上 で)最 近 隣 の レ ベ ルZノ ー ド ま で の 距 離 は, d8(1)一[2d・(1・)+(2c-1-・)](8)

と 表 わ す こ と が で き る.ル ー一 ト は,ホ ッ プ 数do(1-c)で ノ ー ド0か ら,ノ ー ド0に 最 近 隣iの レ ベ ルZ-cノ ー ド に 到 達 し,そ こ か ら レ ベ ル1-cの リ ン ク を2c-1-1ホ ッ プ 伝 わ り,最 後 にdo(1-c)の ホ ッ プ 数 で ノ ー ドZノ ー ド に 到 達 す る.ノ ー ド 間 の 距 離do(1)は,cを 変 化 さ せ た 時 のd8(Z)の 最 小 値 で あ る.cは2≦c≦1-1の 整 数 で あ る が,こ の 中 で,d8(1)を 最 小 と す るcは,

c-1{〉

胴

一1}

で あ る.cは 整 数 な の で,次 の 補 題 の 様 に レ ベ ル 問 の 距 離 を 示 す. 補 題2(レ ベ ル 間 の 距 離)レ ベ ル 問 の 距 離doの は, do(1)==2c∫-1(cf-1一 トsf)十1

ここで

c∫ 一[1{81+1-1}」 2 こ の 時 経 路 は レベ ル1-cの リ ン ク を 通 過 す る.

(9)

(10)

(11) (12) 口 補 題2で はcを 切 捨 て て 整 数 に し た が,同 様 に 切 上 げ て 整 数 化 し,doll)を 求 め る こ と も で き る.こ の 場 合, d。(1)-2c・-2(2(c。-1)+s。)+1(13)

ここで

免 一 「1{〉 舗 一1}1(・4) 亀 一 結 免(Cc十1)(・ ≦ 一亀 く の(15) と な る. 表8に1次 元SRTの レ ベ ルZ,c,経 由 レ ベ ル1-c,レ ベ ル 間 距 離do(1)(=直 径)の 関 係 を 示 す. 定 理1よ り,ノ ー ド 数N=2nか ら 成 る1D-SRTの 直 径D(N)は,Z=lo92!>と し て 表8のdo(1)の 項 と な る.1D-SRTの 直 径 の オ ー ダ ー は,補 題2よ り, D(N)-d。(1・9、N)-2>21092NN21・9、N.(・6) 従 っ て1D-SRTの 直 径 の オ ー ダ ー は, ・(2>21092NN∼logeN)で あ る ・ 20

1 表8:レ ベ ルZ,c,経 由 レ ベ ル1-c,レ ベ ル 間 距 離do(1)(直 径)の 関 係 1 1 2 3 4 5 6 7 8 9 to 11 12 13 14 15 16 cノ 2 2 2 3 3 3 3 4 4 4 4 4 5 5 8ノ 0 1 2 0 1 2 3 0 1 2 3 4 0 1 1‐cf 1 2 3 3 4 5 6 6 7 8 9 10 10 11 Cc 2 3 3 3 4 4 4 4 5 5 5 5 5 6 8c 0 一2 一1 0 一3 一2 .1 0 一4 一3 一2 一1 0 一5 Z-Cc 1 1 2 3 3 4 5 6 6 7 8 9 10 10

doll)

1 2 3 5 7 9 13 17 21 25 33 41 49 57 65 81 4.2.3ル ー テ ィ ン グ ア ル ゴ リ ズ ム 1D-SRTの ル0テ ィ ン グ ア ル ゴ リ ズ ム を 図7に 示 す.ル ー テ ィ ン グ の 始 点 ノ ー ド をxs,終 点 ノ ー ド をxdと す る.関 数FindMLevelに よ っ て,ル ー テ ィ ン グ に 使 用 す る リ ン ク の 最 大 レ ベ ルlrを 求 め,関 数FindNearestNodesで,こ の レ ベ ル の ノ ー ド xrs,xrdを 探 す.始 点 ノ ー ドxSとxrs,垢 終 点 ∬dと の 間 で,手 続 き を 再 帰 的 に 呼 び 出 し,経 路 を 求 め る.こ の 方 針 に 基 づ く ル ー テ ィ ン グ を 再 帰 ル ー テ ィ ン グ と 呼 ぶ.関 数 RecursiveRoutingに よ る ル ー テ ィ ン グ の 結 果 は,経 路 が 通 過 す る ノ ー ド リ ス ト と し て 得 ら れ,こ れ を 経 路 リ ス ト と 呼 ぶ.32ノ ー ド か ら 成 る1D-SRTに お け る,ノ ー ド0(x、=0)か ら ノ ー ド15(xd=15)ま で の ル ー テ ィ ン グ 概 念 を,図8に 示 す.以 下,図8を 例 に し て,ル ー テ ィ ン グ に つ い て 詳 細 に 述 べ る. 手 順1.最 大 レ ベ ル の リ ン ク の 決 定 ル ー テ ィ ン グ で 使 用 す る リ ン ク の う ち,最 大 の レ ベ ルlrを 決 定 す る.、FindMLevelで,補 題2に 基 づ き,レ ベ ルITを 計 算 す

RecursiveRouting(xs,xd){ if(xs=xd)return(); if(x5≦xd)(∫ 乞γ'=十1; elsedir=‐1; 1,.=FindMedLevel(xs,xd); (xs,xd)=FindNearestNodes(lr,xs,xd); lam,=FindUprLevel(xs,xd); (xus,xud)=FindNearestN・ 伽(z… 、,xd); if(1∬5-」 じusl十 レじd-∬ 陽1<1∬5一 コσ芸1十xd-∬rd[){ lr=lu; xrs=xus;xrd=境; } R・utingList=RecursiveR・u伽9@,,xrs); while(xrs≠xrd){ addlist(RoutingList,xs); xs=xs十dir*2tT; } addlist(RoutingList,RecursiveRouting(xd,xd)); return(R・u伽 ψ5の; } 図7:1次 元SRTの ル ー テ ィ ン グ ア ル ゴ リ ズ ム. 求 め る.図8の ノ ー ド0か ら15へ の 経 路 で は,log2115-Olを 切 り 上 げ,Z=5 を 得 る.式(11)よ り,cf=2を 計 算 し て,lr=Z-cf=3を 得 る. 手 順2.バ イ パ ス リ ン ク の 最 近 隣 端 点 の 探 索Findl>earestNodesで,レ ベ ルlrの ノ ー ド の う ち,xs,xdに 最 も 近 い ノ ー ド を 探 索 す る.ノ ー ド番 号 がxよ り 大 き い,xに 最 近 隣 の レ ベ ルZの ノ ー ド番 号 は 次 式 で 与 え ら れ る. x_2c-i nlnear_f(x,1)=21・21+21-1(17) 同 様 に,ノ ー ド 番 号 がxよ り小 さ い,xに 最 近 隣 の レ ベ ルZの ノ ー ド 番 号 は 次 22

ノ    も   ノ   コ    へ

絃鯵 鷺重:∼

∴へ1

lr=O /Xs℃ Xd=1 冒 麗 ω ●Leve pLeve pLeve ●Leve ●Leve . G 1 0 d ■ O d O O O O O n n n n n 心 ﹂ 2 3 4 Xｧニ13

響

♂＼ 轡1紙Xs=12

＼ ＼Xd・15♪Xd・X砲 ・15Xd.15 (b)(c)( a) 図8:1次 元SRTの ル ー テ ィ ン グ の 概 念 図 式 で 求 ま る. x_2t-1 nlnear_b(x,1)=2t・2t-}-2t-i

(ls)

最 近 隣iノ ー ド の 探 索 時,xSに 最 近 隣 の レ ベ ルlrの ノ ー ド は,xd側 だ け に 限 ら れ な い.そ こ で,通 信 相 手 と 反 対 側 の 逆 方 向 の レ ベ ルlrの ノ0ド も 探 索 し,よ り近 い ノ ー ド を 決 定 す る.決 定 さ れ たxs側 の 最 近 隣 ノ ー ド をxrs,xd側 の 最 近 隣 ノ ー ド をxrdと す る.図8(a)で,lr=3な の で,xrs=4,xrd=12と な る 。 手 順3.lrの 補 正 (手 川頁3-1)手 順1に よ る レ ベ ル の 決 定 は,ノ ー ドの 位 置 を 考 慮 し て い な い た め,上 位 レベ ル の リ ン ク を使 用 し た 経 路 の 方 が 明 か に 短 い 場 合 で も,上 位 レ ベ ル の リ ン ク を 使 用 し な い と い う 問 題 点 が あ る.例 え ば 図6で ノ ー ド8か ら24 へ の ル ー テ ィ ン グ の 場 合,式(11)を 用 い た レベ ル 決 定 で はlr=3と な る が,実 際 に はlr=4の リ ン ク を使 用 し た 方 が 良 い.そ こ で,FindUprLevelでxSか らxd間 の リ ン ク 中 の 最 大 の レ ベ ルluを 取 り 出 す.luは, lu=1・92(xd‐xsl); と 計 算 で き る.例 で はlu=3で あ る.

(手 順3-2)手 順2と 同 様 に,レ ベ ルluの ノ ー ド の う ち,xs,xdに 最 も 近 い ノ ー ド を 探 索 す る.例 で は,lu=3な の で,xus=4,畷=12と な る. (手 順3-3)ITを そ の ま ま 使 用 す る か,luを 使 用 し た 経 路 に す る か を 決 定 す る. xrs,xrdよ り もxus,婿 の 方 がxs,xdに 近 い 場 合 は,レ ベ ルITの 代 り に ㌔ を 使 用 す る.例 で は,1T=luな の で,lr=3を 使 用 す る. 手 順4.低 位 リ ン ク に 対 す る 再 帰 ル ー テ ィ ン グx,とxrs問 で,∬ 、=xrsと な る ま で 再 帰 的 にRecursiveRoutingを 呼 び 出 し,xs,xrs間 の 経 路 リ ス ト を 得 る. 次 にxTSか らxrd間 に あ る レ ベ ルITの ノ ー ド の リ ス ト を 経 路 リ ス ト に 加 え る.こ こ で は 経 路 リ ス ト に{4,12}が 加 え ら れ る.xrdとxd間 の 経 路 もxs,xrs間 と 同 様 に 求 め,経 路 リ ス ト の 末 尾 に 付 加 す る 図8(b)の よ う に,2回 目 の 再 帰 呼 び 出 し 時 に,前 回 不 明 だ っ た ノ ー ド0か ら4 の 問 の 経 路 を 求 め る.xS=0,xd=4と し て,Z,=1,経 路 リ ス ト{1,2}を 得 る.更 に 図8(c)に 示 す よ う に,3回 目 の 再 帰 呼 び 出 し で,x,=0,xd=1と し て,lr=0,経 路 リ ス ト{0,1},及 びx,=3,xd=4と し て,6T=0,経 路 リ ス ト {3,4}を 得 る.2,3回 目 の 経 路 リ ス ト を 継 げ,現 在 の 経 路 リ ス ト の 先 頭 に 加 え る({0,1,3,4,12}).同 様 に ノ0ド12か ら15に つ い て の 経 路({12,13,15})を, 経 路 リ ス ト の 末 尾 に 追 加 す る. 1D-SRTは ト ー ラ ス 結 合 を 基 本 と し て い る た め,[鞠 一x,1>21max-1の 場 合 に は, x、 か ら 逆 方 向 に 経 路 を 求 め る. 4.2.41D-SRTの ネ ッ ト ワ ー ク 性 能 1D-SRTの 平 均 距 離 を 表9に 示 す.表 中OptimalRoutingは 可 能 な 経 路 を 全 探 索 し,最 短 経 路 を 使 用 す る ル ー テ ィ ン グ 方 式 で あ る.こ れ に 対 し,1D-SRTの 再 帰 ル ー テ ィ ン グ で は10%前 後 平 均 距 離 が 長 くな る.こ の 平 均 距 離 の 増 加 は,ノ ー ド数 が 大 き い 場 合 に 大 き く な る.ノ ー ド数 が 大 き く な る と,距 離 を 短 縮 す る 上 位 レ ベ ルluと 補 題2で 計 算 さ れ る レベ ルlrの 差 が 大 き く な る.レ ベ ルZの ノ ー ド数 は,N/21な の で,距 離 の 短 縮 に 有 効 なluの ノ ー ドの 数 がlrの ノ ー ドの 数 に 比 べ て 少 な く な る.こ の た め,レ ベ ルluの リ ン ク を 使 用 し に く く な り,距 離 の 短 縮 が 有 効 に 行 な わ れ な い. 再 帰 ル ー テ ィ ン グ に よ る 直 径 は,1D-SRTの 理 論 直 径 で あ るD(!>)≡do(logeN)に 一 致 す る . 表10に1D-SRTや 他 の 結 合 網 の 直 径 と 次 数 を 示 す.ChordalRingは,次 数 が 小 さ く ノ ー ド数 が 少 な い 時 は1D-SRTよ り も 直 径 が 小 さ い.し か し ノ ー ド数 が 多 く な っ 24

表9:1次 元SRTの 平 均 距 離 Numberofnode OptimalRouting RecursiveRouting 8 2 (U 4 7 8 7 1 2io 11.5 12.4 212 17.7 20.0 2i4 30.2

表10=1次

元SRTと

他 の結 合 網 の直径(次 数)の 比較

Numberofnode 1D-SRT ChordalRing BarrelShifter 8 2

17(4)

15(3)

4(15)

2io

25(4)

31(3)

5(19}

Zia

41(4)

63(3)

6(23)

2i4

57(4)

127(3)

6(27)

2is

81(4)

255(3)

8(31)

て く る と,急 速 に 直 径 が 増 大 す る.BarrelShifterは ノ ー ド数 が 多 い 場 合 で も直 径 が 非 常 に小 さ い が,次 数 が0(logeN)で あ り,ノ ー ド数 が 大 き くな る と ノ ー ドの 次 数 が 非 常 に 大 き く な り,実 装 性 が 低 下 す る.1D-SRTは 次 数 がChordalRingと あ ま り 変 ら な い に も か か わ らず,ノ ー ド数 が 増 加 し て も直 径 が 急 激 に 増 加 し な い.1D-SRT は,階 層 構 造 に よ り次 数 や 網 の 構 成 を 変 化 さ せ る こ と な く ノ ー ド数 を 増 加 で き る の で,ス ケ ー ラ ビ リ テ ィ に 優 れ る.1次 元PEC網 は,1D-SRTが トー ラ ス 結 合 を 基 に し て い る の に 対 し,線 型 結 合 を 基 に し て い る の で,直 径 は1D-SRTよ り も1段 大 き く な る. 4.32次 元SRT 4.3.12D-SRTへ の 拡 張 本 章 で は,1次 元SRTを2次 元 に 拡 張 し た2D-SRTに つ い て 詳 し く議 論 す る.N× N(N=2n)の ノ ー ドか ら成 る2D-SRTは,x方 向 に 直 線 状 に 配 置 し たN/0ド か ら 成 る1D-SRTをy方 向 に 積 み 重 ね る こ と に よ り構 成 さ れ る.2D-SRTは,x方 向 と と も に,シ 方 向 に も1D-SRTが 構 成 可 能 で な く て は な ら な い.そ こ で,積 み 重 ね る段 ご と に,1D-SRTの 原 点 ノ ー ド(ノ ー ド0)の 位 置 を シ フ トす る 必 要 が あ る.シ フ ト の 幅 を 変 化 させ る こ と に よ り,様 々 な2D-SRTが 構 成 可 能 で あ る.最 初 に2D-SRT の 一 般 形 に つ い て 定 義 す る.

定 義3N×1V(1V;2n)の ノ ー ドか ら 成 る トー ラ ス 上 で,ア ド レ ス を 左 下 か ら順 に 与 え,(x,ッ)と 表 記 す る,1次 元SRTと 同 様 に,ト ー ラ ス 上 の ノ ー ドに 上 位 レ ベ ル を 割 り当 て る.レ ベ ルZの ノ ー ド(銑 融)は 次 の 式 を 満 す ノ ー ドで あ る.

(xl十s狙 ・!ノ∂mod21=・=2置 一1

(19)

こ こ でs, ,rはx方 向 の シ フ ト 幅 で あ る.ノ ー ド@ε,yc)は 隣 接 す る4ノ ー ド((xl土

1)modN,勉 ±1)modNノ と,21離 れ た4ノ ー ド ピ箇 士2りmodN,(肋 士2りmodNノ

と 接 続 さ れ る.ロ x方 向 に1D-SRTを 構 成 す る と 同 時 に,9方 向 に も1D-SRTが 構 成 さ れ る た め に は, シ フ ト幅8。 が 以 下 の 条 件 を 満 す 必 要 が あ る. 1.原 点 ノ ー ドが 各 行 ・列 に1つ だ け 存 在 す る 2.xと 雪が 転 置 関 係 に あ る 式 が 定 義 で き る こ と. つ ま り,式(19)に 対 し て, (肋+sy・ ∬∂mod21=2`-1が 得 ら れ る. 原 点 ノ ー ド と は,1D-SRTの ノ ー ド番 号 が0の ノ ー ドの こ と で あ る. 各 レ ベ ル の 通 信 特 性 を考 え る と,レ ベ ル が 低 い ノ ー ドは 近 距 離 の 通 信 に 適 し,レ ベ ル が 高 い ノ ー ド は 遠 距 離 の 通 信 に 適 し て い る.従 っ て,全 体 の 通 信 性 能 を 向 上 す る た め に は,レ ベ ル が 高 い ノ ー ドを 平 面 内 に均 等 に 配 置 す る こ と が 有 効 で あ る.N×N ノ ー ドか ら成 る2D-SRTは,1V個 の1D-SRTを 積 み 重 ね て 構 成 さ れ る た め,1V個 の 原 点 ノ ー ドを 持 つ.こ の1>個 の ノ ー ドをN×1Vの 平 面 内 に 均 等 に 割 り当 て る と, 原 点 ノ ー ド同 士 は 間 隔 が ∼々▽ の 格 子 状 に 配 置 さ れ る.こ の 格 子 配 置 に 基 づ い て,定 義3の 条 件 を 満 た す た め に,g方 向 に 進 む に 従 い 格 子 か らx方 向 に1列 ず ら し た 千 鳥 型2D-SRTを 定 義 す る. 定 義4(千 鳥 型2D-SRT)千 鳥 型2D-sRTは,一 般 型2D-SRTで Sx-±(2「Amax-Z)/21士 ・) の 時 の 構 成 で あ る.複 号 は 独 立 で あ る. 0 千 鳥 型2D-SRTで は,符 号 に よ っ て5。 が4通 り あ り,式(19)に 当 て は め る と,次 の 4つ の 式 は,ど れ も が 千 鳥 型2D-SRTの 定 義 式 と な り得 る. @(2「(置 … 一')/2]+1)yc)m・d21=21-1(2・) 26 騨

r Y X

OriginNode

図9:8×8ノ ー ドか ら 成 る 千 鳥 型2D-SRT. (xl+(2「(lmax-1)/2L1)ッ 」)m・d21-@(2「(z-一 一1)/2]-1)2」1)m・d21e (xl+(2「Amax-1)/21+1)ッ 置)m・d21一 こ こ で,lmax=nで あ る. 21-1 2t-i 21-1

(21)

(22)

(23)

ノ ー ド(xl,肋)は,隣i接 す る4ノ ー ド((xa士1)modN,(肋 土1)modN)と,21離 れ た4ノ ー ド(箇 士2りmodN,(99圭21)modN)に 接 続 さ れ る ・ 式(20)か ら 式(23)に よ り定 義 さ れ たSRTは,x方 向 に 関 し て1D-SRTを 形 成 す る こ と は 明 ら か で あ る.ま た,そ れ ぞ れ 転 置 関 係 に あ る 式 が 定 義 で き る の で,y方 向 に 関 し て も1D-SRTを 形 成 す る.式(20)と 式(21),式(22)と 式(23)は 転 置 の 関 係, 式(20)と 式(23),式(21)と 式(22)は 対 称 の 関 係 と な る ・図9に,8×8ノ ー ドか ら 成 る 式(22)に 基 づ く千 鳥 型2D-SRTの レ ベ ル 配 置 と 結 合 の 様 子 を 示 す.図 中 の 数 字 は ノ ー ドの レ ベ ル 番 号 を 示 す.

く  ,Y  ニく コ  ラ /1)(1  ) ,, ノ,, ' 蜘 、, Nearest vertex (4,8) (Xrd. =(12, (Xs,Ys)ニ(8,19) (5,18) /益 、.(点 痴 ノ ー 、 馳●'=(7」8) 覧 (Xd,Yd) =(4.16) (4.0)、 、 ノ (a)Findarectanglar atlevel-3 RoutingList= ((4.16),(4,8).(4,0),(12,0)} (Xd,Yd) =(12,2)

/

」

'N earest vertex (xrs.Yi's) =(5.16) d = X (Xd.Yd) (12,2) Nearest vertex (8.18) (Xs,Ys)=(8.19) ← ＼ コ    ド   L_・e宜ex (Xd.Yd)=(7,18)

輪

s.Ys)=(5.16) Nearest vertex 口Level-Onode Level-1node Level-2node Level-3node Newlists (Xs.Ys)=(12.0) (b)Findrectanglars(c)Findrectanglars atlevel-1,0atlevel-O RoutineList=RoutinList‐ {((7.18).(5.18).(5.16)).ｬ‐{(((8,19).(8.18).(7,18)}, {(4.16).(4.8).(4.0).(12.0)}.{(7・18)・(5・18)・(5・16)}・ 1{(12.0).(12」).(12.2川[{(5」6)・(4」6)}}・1 {(4,]6),(4,8),(4,0),(12,0).(12,1),(12,2)}) 図10:2D-SRTの ル ー テ ィ ン グ の 概 念 図. 4.3.22D-SRTの ル ー テ ィ ン グ 2次 元SRTの ル ー テ ィ ン グ の 基 本 方 針 は,1D-SRTの ル ー テ ィ ン グ と 同 様 に,ル ー テ ィ ン グ に使 用 す る 最 大 の レ ベ ル を 求 め,こ の レ ベ ル の ノ ー ド と始 点 ・終 点 ノ ー ド と の 間 で 再 帰 的 に 手 続 き を 繰 り返 し経 路 の リ ス ト を 作 成 す る.始 点 ノ ー ドを@,,〃 、), 終 点 ノ ー ド を(xd,駒)と して,経 路 リ ス トを 作 成 す る.2次 元SRTの ル ー テ ィ ン グ の 概 念 図 を 図10に 示 す.図 に 示 した(8,19)→(12,2)へ の ル ー テ ィ ン グ を 例 と して, 以 下 に 手 続 き の 流 れ に つ い て 述 べ る. 手 川頁1.最 大 レ ベ ル の リ ン ク の 決 定 ル ー テ ィ ン グ で 使 用 す る リ ン ク の う ち,最 大 の レ ベ ルlrを 求 め る.xS→xdと 雪s→ 駒 に つ い て,そ れ ぞ れ1D-SRTと 同 様 に レ ベ ル を 求 め,大 き い レ ベ ル をlrと す る.図10で は,xs=8→xd=12か ら Z。.=2,g,ニ19→9d=2か らITy=3と な る の で,ッ 方 向 の レ ベ ル が 大 き く, lr=3と す る. 手 順2.バ イ パ ス リ ン ク の 最 近 隣 端 点 の 探 索(∬8,ツ3),(xd,駒)に 近 い,レ ベ ルlrの ノ ー ド を 探 索 す る.複 数 あ る レ ベ ルlrト ー ラ ス の ノ ー ド の う ち,(xs,93), @d,ツd)に 最 も 近 い ノ ー ド を 基 準 と す る.こ の レ ベ ルlrト ー ラ ス に 含 ま れ る ノ ー 下 の う ち,@、,g、)の 最 近 隣 ノ ー ド を(xrs,〃 罫),(xd,駒)の 最 近 隣 ノ ー 28

ド を(xrd,yd)と す る.図10(a)で は,lr=3(グ リ ッ ド 間 隔 が8)の ト ー ラ ス の う ち,(xd,駒)に 近 い(12,0)を 基 準 と し た レ ベ ル3の ト0ラ ス を 選 択 し, @=,垢)=(4,16),@2,%)=(12,0)を と る. 手 順3.低 位 リ ン ク に 対 す る 再 帰 ル ー テ ィ ン グ(x、,〃,)と(xrs,謝 間 で,(∬ 、,g,)= (xrs,ッ∫)と な る ま で,本 手 続 き を 再 帰 的 に 行 い,@、,g,),(鰐,ッ;)問 の 経 路 リ ス ト を 得 る.次 に@;,〃 ζ)か ら(xrd,垢)問 に あ る レ ベ ルlrの ノ ー ド の リ ス ト を 経 路 リ ス ト に 加 え る.(xrd,垢)と@d,駒)問 の 経 路 も(鞠,9,),(xrs,卿 間 と 同 様 に 求 め,経 路 リ ス トの 末 尾 に 付 加 す る. 図10(b)で,(8,19)→(4,16)に つ い て 再 帰 的 に 経 路 を 求 め る と,2回 目 の 再 帰 呼 び 出 し でlr=1の ト ー ラ ス を 決 め,経 路 リ ス ト{(7,18),(5,18),(5,6)} を 得 る.図10(c)で,同 様 に3回 目 の 再 帰 呼 び 出 し を 行 な い,経 路 リ ス ト {(8,19),(8,18),(7,18)}と{(5,16),(4,16)}を 得 る.こ れ ら を 継 げ,レ ベ ル3 の ト ー ラ ス 上 の 経 路 リ ス ト{(4,16),(4,8),(4,0),(12,0)}の 前 に 加 え る.同 様 に(12,0)→(12,2)に つ い て の 経 路 を 求 め,経 路 リ ス ト の 末 尾 に 追 加 す る. 4.3.32D-SRTの 直 径 N×N(N=2n)ノ ー ドか ら 成 る2D-SRTの 直 径 は,単 純 に@,,〃,)→(xd,〃,)→ @d,〃d)と い う 経 路 を と れ ば2・DID-SRT(n)を 越 え な い こ と は 明 か で あ る.2D。SRT の ル0テ ィ ン グ で は,経 路 途 中 で 現 在 の 移 動 方 向 と 直 交 す る 方 向 の 移 動 も 含 ま れ る が,補 題1か ら,上 位 レ ベ ル に 対 す る 下 位 レ ベ ル の ノ ー ド配 置 が 同 じで あ る の で,移 動 途 中 で 直 交 す る 方 向 へ の 移 動 が 加 わ っ て も,直 交 方 向 移 動 後 の 下 位 レベ ル の ノ ー ド配 置 は 変 化 し な い.例 え ば 図10(a)で,ッ 方 向((4,16)→(4,0))に 移 動 後,x方 向((4,0)→(12,0))に 移 動 す る が,雪 方 向 の 下 位 レ ベ ル の ノ ー ド配 置 はx方 向 の 移 動 前(4,0)も 移 動 後(12,0)も 変 ら な い.従 っ て2D-SRTの 直 径 もNノ ー ドか ら成 る1D-SRTの 直 径 の2倍 を を 越 え な い.こ の た め,2D-SRTの 直 径 の オ ー ダ ー は, ・(21092N∼logeN)を 猷 な い. 4.3.42D-SRTの ネ ッ ト ワ ー ク 性 能 2D-SRTと 他 の 相 互 結 合 網 の 平 均 距 離,直 径 及 び 次 数 を 表11に 示 す.2D-SRTの 平 均 距 離 は,1D-SRTと 同 様 の 理 由 で,OptimalRouting(表 中Opt.)に 比 べ,再 帰 ル ー テ ィ ン グ(表 中Rec.)の 平 均 距 離 が 長 く な る.2次 元 で は,"1次 元 方 向 の 平 均 距 離 の 増 加"の2乗 と な る た め,OptimalRoutingと の 差 が1D-SRTよ り も大 き く,

表11:2次 元SRTと 他 の 結 合 網 の 平 均 距 離,直 径,次 数 の 比 較 Numberofnode28 210 212 214 2is Meandistance2D-SRTandothernetworks

2D-SRT(Opt.)

2D-SRT(Rec.)

2DTorus RDT(2,4,1)/α ρ 0 り 白 9 0 4 4.0 0 ◎ 7 8 4 ピ 0 0 ρ 0 8 ︻ り り 0 8 ρ 0 7 5 16.0 6.7 7.9 10.4 32.0 7.8 10.1 13.3 64.0 9.0

Diameter(Degree)of2D-SRTandothernetworks

2D-SRT(Opt.)

2DTorus 3DTorus

RDT(2,4,1)/cx

2D-DTN[13]

HyperCube ccc

HyperNet[14]

DeBruijn[15]

Pladhan

6(8)

16(4)

10(6)

8(8)

8(8)

16(4)

4(8)

7(4)

gds)

32(4)

16(6)

7(s)

16(8)

10(10)

14(3)

5(8)

9(4)

11(8)

64(4)

24(6)

8(8)

32(8)

12(12)

18(3)

19(5)

6(8)

11(4)

13(8)

128(4)

40(6)

lo(s)

64(8)

14(14)

7(8)

13(4)

16(8)

256(4)

64(6)

12(8)

128(8)

16(16)

24(3)

23(6)

8(8)

15(4)

未定数

10∼30%程 と な る.RDT(2,4,1)/α の 平 均 距 離 と比 べ る と,殆 ど 劣 ら な い 性 能 を 持 っ こ と が 分 る. 2D-SRTの 直 径 と次 数 を 他 の 結 合 網 と 比 較 す る と,2D-SRTは 少 な い 次 数 で ハ イ パ ー キ ュ ー ブ に 近 い 性 能 を 持 ち ,他 の 超 並 列 計 算 機 向 き の 結 合 網 と比 べ,遜 色 な い 性 能 を 持 つ こ とが 分 る.2D-SRTは,ト ー ラ ス だ け を 階 層 的 に 用 い て 構 成 さ れ る の で,配 線 が 容 易 で,故 障 回 避 ア ー キ テ ク チ ャ な ど の イ ン プ リ メ ン トが 可 能[11]と い う特 徴 を 有 し て い る. 4.4ま と め 本 章 で は,グ リ ッ ド の 大 き さ が 異 な る ト ー ラ ス 結 合 網 を,互 い に 重 な ら な い よ う に 再 帰 シ フ ト構 造 に 配 置 し た,超 並 列 計 算 機 の た め の 新 し い 相 互 結 合 網Shifted RecuresiveTorus(SRT)網 を 提 案 し た.最 初 に1次 元 のSRT(1D-SRT)の 構 成 法 を 30