出版者 静岡大学

並列分散処理及び多並列計算を用いた大規模線形回 路網の高速過渡解析に関する研究

著者 井上 雄太

発行年 2011‑06

出版者 静岡大学

URL http://doi.org/10.14945/00007628

静岡大学   ^博士論文

並列分散処理及び多並列計算 を用いた

大規模線形回路網の高速過渡解析 に関す る研究

2011年 6月

大学院   自然科学 系教育部 情報科学専攻

井上   雄太

目 次

第 ■章

11 12

13

本論 文 の 目的 と構成

第

2章  

クラウ ドコンピューテ ィング と並列分散型

LIRIに

_{よる高速過渡解析}

21 

概要

 

… …

 

… … … …

 

… … … …

22 

クラ ウ ドコンピューテ ィング

  

_{… …}

 

_…

 

_{… … … … …}

2 3 Latency lnsertion Method(LIM)…

… … … …

2.31 0rl脚 al LIM         .

232 

並列分散型

LIM 

_{… …}

 

_…

 

_…

 

… … … …

24 

計測結果

 

…

 

… … … …

 

… … … …

241 LIMと SPICE系

シ ミュ レー タの比較

 

… … … …

242 

クラウ ドコン ピューテ ィング と既存 の並列計算機 の比較

  肺 韻

並列化 に よる高速 回路 シ ミュ レー シ ョン手 法

13

５     ５ １     １

″′       ８

９     ０ Ｚ     ５       ５       ８

18

29

25 

本 章 の総括

GPGPUに

基づ く^LI]√ の高速過渡解析 概 要

GPGPU(General PurpOse computing on Graphcs Processing U」 ts)

321 CUDA(Compute u五

ned De宙ce Ar面tecture)

32.2 CUDA対

応

GPUア

ー キテ クチ ャ

 

…

 

_{… … … … …}

33 GPGPUに

基づ く

LIM(GPGPU― LIM)

331 

枝電流 の領域分割

332 

節 ′点電圧 の領域分割

333 GPGPU― ^LIMの

更新手順 計測結果

本章 の総括

並列分散型 ブロック

LIMに

よる高速過渡解析

35

３８     ３８

第

3章 31 32

第

4章

41 42

概 要

40 41 42 45 46

４     ５

００      ００

８       ０ ４     ５

Ｑ じ       ６        

60

６２     ６２

ブ ロ ック

LIM

421 0r増 halブ

ロ ツク

LIM

44 

本章 の総括 第

5章  

結論

０         ２     ２ ８       ８    

51 

総括 ８

謝辞

第 1章 _論

1.1

近年 の回路実装技術 の進歩 に よ り

,集

積 回路やパ ッケー ジ

,PCBの

高密度集積 化 は著 しい

 

加 えて

,回

路 の動作周波数 が高速 になるにつれ て

,立

ち上 り時間 と 立下 り時間が短 くな り

,回

路 内の信 号波 は さま ざまな高調波 を含 む高周波信 号 と なってい る

 

その結果 として

,チ

ップやパ ッケー ジ上では高周波 の影響 に よる配 線上の信号の遅延や反射

,配

線 間の クロス トー ク

,グ

ラン ドバ ウンスな どの予期 し ない現象 が発生 し

,回

路 の誤動作 を引 き起 こす ことになる

 

これ は

,製

造 した回 路 で所望の動作 を得 られ無 い こ とを意味 し

,対

策 を講 じた回路 の再設計

,再

製 造 を必要 とす る

 

^{しか しなが ら}

,所

望 の動作 を得 られ るまで何度 も試作 を繰 り返 し,

検証す るこ とは現実的ではない

.そ

のた め

,回

路設計の段 階で高周波 による影響 を考慮 した動作検証

,対

策 が必要 とされ てい る。 この回路の動作検証 には

,古

く か ら回路 シ ミュ レー タ と電磁界 シ ミュ レー タが用い られて来 てい る

 

回路 シ ミュ

背

旦 累

第

1章  

序論

表 され

,各

要素が強 く結合 された等価 回路網 を用 い るこ とにな る

.一

_{般的 に}

_,こ

の等価回路網は

CADモ

デルか ら抽 出ツール を用いて作成 され る

.そ

して

,抽

出対 象 として回路 の配線 をモデル化 した場合 には

,素

子 の数 は百万 を超 える

 

回路 シ ミュ レー タ として標 準的に用 い られ てい る

SPICE卜

_l系シ ミュ レー タは行列演算に 基づ いてお り

,行

列 に各要素 をス タンプ してい くと密結合 に近 い行列 にな る

 

そ のた め

,行

列演算 に必要 とす る計算 時間が膨大 とな り

,実

用的な時間で解析結果 を得 ることが困難 で ある

.一

方 で

,電

磁界 シ ミュ レー タでは

,高

密度実装 に伴 う 微細構造 を再現す るた め

,非

常 に細 かい メ ッシュに よつて再現 された物理 モデル

を解析す ることにな り

,実

際に数 十億 のメ ッシュを用い ることにな る。そ のた め^, 代入計算のみで電磁界の解析結果 を得 る

FDTD法

_レIを用いて も

,回

路 シ ミュ レー シ ョン と同様 に実用的な時間で解析結果 を得 ることが困難 である

.こ

の よ うな背 景 の下

,従

来のシ ミュ レー タ と比べ て

,高

速 に解析 が可能 なシ ミュ レー シ ョン技 術 に基づ くシ ミュ レー タが求 め られ てい る

高速 なシ ミュ レー シ ョン技術 の実現 のた めには

,二

種類 のアプ ローチ に よ り高 速化 が試み られてい る

 

一つ は従来 よ りも高速 なアル ゴ リズムを開発す る試みで あ り

,も

う一つはハー ドウェアア クセ ラ レー タを用 いた高速化 であ る。回路 の過

渡解析に限定した場合では,前者は連立一次方程式の解法の高速化 _B,4,司 や緩

和法に基づく手法Ю

^,司

^,回 路縮小法ド l,ま た,新 たな定式化手法 ^p,10,1」 に

第

1章  

序論

よる高速化が提案されている。後者においては ,行 列演算と非線形素子のモデル 評価の並列化 卜2,13,14,15,16)17,18,19,20,2」 ,特 定のハー ドウェアの適用 p2,23,24,25,2qが 提案されている ^.し かしながら,いずれか一方の高速化には

限界 があ り

,両

方共のアプ ローチ を取 り入れ た手法 も提案 されてい る。す なわち^, 新た に開発 した手法の並列化 であ る レ7,15,2剣

この よ うにい くつかの従 来 よ りも高速

,か

^つ

,並

列化 され た手法 が提案 され て い るが

,い

ずれ の場合 であつて も十分 に高速 で ある とは言 いに くい

 

これ は並列 化 にお ける欠点 として

,未

並列化時 よ りもアル ゴ リズムが複雑 にな るこ とな どの オーバーヘ ッ ドの出現

,ハ

ー ドウェアによる制限を受 けることが挙 げ られ る

.並

列化 によるオーバーヘ ッ ドや制 限 は

,過

渡解析 で は各時間ステ ップや各反復処理 中の更新手順 の変化や前処理

,通

信

,同

期 処理 といつた逐次処理

,そ

れ らに必要 とす る実行 時間 として現れ る

 

これ らは並列化 における高速化のボ トルネ ックで あ り

,こ

の よ うなオーバーヘ ッ ドは極 めて少 な くしなけれ ばな らない

 

そのため,

オーバーヘ ッ ドの発生が少 ない

,よ

り並列化 に適 してい るアル ゴ リズムを用い る 必要性 がある。加 えて

,既

存 の環境 にあ る高速 なハー ドウェアヘの展 開 も考 える 必要がある

.こ

れ は

,画

像処理用の演算装置 である

GPUが

急速 に性能 を伸 ば して お り

,近

年 では浮動小数点の演算 も可能 となつた。そのため

,GPUを

^{利用す るこ}

第1章

 

序論

開発 が可能 とな つてい る

.従

つて

,高

速 な回路 シ ミュ レー タの開発 を行 うた め に は

,高

速 で並列化 に適 したアル ゴ リズムに対 して

,並

列計算機 や

GPUを

適用す る こ とが必要 で あ る^.

1.2  並列化による高速回路 シ ミュ レー シ ョン手法

工学分野では

,微

分方程式 によ り記述 され た多 くの問題 がある

 

しか しなが ら,

これ らのほ とん どは解析解 を持たず

,通

常 は数値計算 に よって解 かれ る

 

そのた め

,数

値計算 の 目的は微 分方程式 を数値 的 に解 くこ とで ある

.回

_{路 の過渡解析 の}

場合 には

,こ

れ は非線形常微分方程式 と して記述 され る

 

回路 シ ミュ レー タ とし て標 準的に用い られている

SPICE系

のシ ミュ レー タでは

,回

路素子 とそれ らの接 続情報 が記述 されたネ ッ トリス トを基 に修正節 点解析 法

(MNA:Modened Nodal

Analysis)で 定式化 され る[」 そ して

,後

退 オイ ラー法や台形公式 な どの陰的数値 積分法を用いて非線形代数方程式 に離散化 し

,ニ

ュー トン・ラフソン法を用いて線 形代数方程式 とす る

 

この結果 として

,各

時間ステ ップやニュー トン・ラフソン法 の各反復は

,ヤ

コビアン行列の計算 を行 うことで得 られ る係数行列

Aを

持つ線形 代数 方程式

Ax=bを

解 く問題へ と帰着す る

.こ

の線形代数方程式は

,通

常

,LU

分解 法 を用い る事 で方程式 の解 を得 る

.そ

のため

,一

連 の処理 にお いて

,ニ

^ュー

第1章

 

序論

の二つ にシ ミュ レー シ ョン中の計算 時間のほ とん どが集 中す る

 

そ して

,高

速 な 回路 シ ミュ レー シ ョンを実現す るた めに これ らの並列化 を含 む高速化手法が提案

されてい る。

モデル評価 ではニュー トン・ ラフソン法 によ り

,各

時間ステ ップ 中の各反復 で ヤ コビア ン行列 の各要素のモデル評価 を行 う。 これ は

,回

路規模 が 中規模 までの 間では解析 に必要 とす る計算時間の多 くを占める。そのため

,テ

^{ーブルル ックア ッ}

プレ劇や,各要素の計算処理を一変数ごとに独立して更新できることに注目した

並列化 卜

2,15,19,2qが

行 われ てい る。カロえて

,モ

デ ル評価部分 のみ を

FPGAp司 や GPUp」 によつて高速化する手法も提案されている

^.

線形代数方程式の解法の一つである LU分 解法は ,寄 生素子を多数含む回路網 では最悪の場合

^0(れ3)の

計算量を必要 とし ,大 規模な回路網の場合には膨大な計 算時間を必要 とする。しか しながら ,SPICE系 シミュレータでは ,多 くの場合で 回路行列は疎行列で表 され ,疎 行列の性質を利用 したいくつかの高速化手法を用 いることができる .そ の中の一つが ,行 列の■■

inの

発生を抑える行列構造への リ オーダリングであり,更 に,回 路分割法による縁付きブロック対角 (BBD:bordered

block di電onal)行

列への変形 卜

Iや

,縁 付きブロック対角行列を再帰的に行い部分

回路行列ごとの潜在性を利用した動的分割技法 pqが _{挙げられる}   そして

, 

この

第

1章  

序論

縁付きブロック対角の LU分 解で発生する

^ill―inが

ブロック対角行列内に制限され

,

他のブロック対角行列 とは独立 して解を得 られ ることに注 目している。すなわち

,

対角成分のみ配置 されたブロック対角行列であった場合には ,各 ブロック対角行 列が独立 して解析結果を得 られることを意味 している

ここで ,縁 付きブロック対角行列を用いた場合の並列化によるオーバーヘ ッド について簡単に述べると ,ま ず ,線 形代数方程式 Ax=bを Å文 =3と して解 く ことになる   ここで

,

ABBl

ABB2

A=

_,X =

,b=

ABBA

Ac2 (  Acた

であ り

,ABBれ

(π

=1,2,…

,ん)は れπ×れπの行列

,Aη c,Aの  (2=1,2,…

,ん ),

Dは

要素 の接続 関係 を示す行列 である

.こ

こで注 目す るのは

,各

ブ ロ ック対角行 列 ABBれ は独立 して解 を得 られ るが

,右

下の部分回路行列

Dは

節点分割 を行 つた ことに よる接続情報が含 まれ る

 

^{そのた め}

,全

て のブ ロ ック対角行列 の情報 を基 に計算処理 が行 われ る。また

,こ

の縁付 きブ ロック行列 を解 くために,Sherman―

Ａｌ   Ａ２ 

 

⁚   れ   Ｄ

Acl

Xll

ｂ ・ ｌ

 

ｂ ・ ２

  ・⁚   鴫  

ｂ ２

X12

Xlん

X2

第

1章  

序論

Morrison-Woodbury o>A=t _131],

(e

+

cn")-' :

B-1

- ^B-1u

^(r."

^* arg-r1J;-r grg-r

_(1.2.1)

を用いる .こ の公式を用いるため ,行 列 Aは A=B+cRTと 分割される.こ の とき

,

ABβ_l

Alc

A2c

B= ,C= ,RT= 10  1ccI

ABB2

ABBス

Acl  Ar2 ‑  Acた  D

Aん_ε

0

である

 

公式 中には逆行列が存在す るが

,逆

行列 を求 めず に各 ブ ロック対角行列 ごとで解 を得 ることになる

 

す なわち

,ブ

ロック対角行列 とそれ以外の行列の順 に

LU分

_{解 法の前進代入}

,後

退代入 を用い る ことで並列化 が可能 とな る

.こ

こで,

各

PEに

割 り当て られ る回路行列 は,

第

1章  

序論

である。す なわち

,SPICE系

シ ミュ レー タの場合 には

,ブ

ロック対角行列である ABB・2以外 の行列 の要素 と更新処理 の複雑化

,リ

オー ダ リングがオーバーヘ ッ ドと して現れ ることにな る

.縁

付 きブ ロック対角行 列 を用 いた手法では

,並

列性 はブ ロック対角行列の数 によつて制限 され る。そのため

,縁

付 きブ ロック対角行列 を 入れ子構造 にす る入れ子縁付 きブ ロ ック対角行列 (Nested BBD:nested bordered b10clK diagonal)に

より,ブ ロック対角構造を増やす手法卜 4,15,lq,LU分 _解自体

にも並列化を施した並列 BBD行 列の解法 _1lqが 提案されている.し かしながら

^,

これ らの手 法 で は劇 的 に早 くな る こ とは無 く

,並

夕1性 の確保 とオーバ ーヘ ッ ドの トレー ドオ フ とな る

.そ

のた め

,回

路構造 に よって は並列 化 の効果 を十 分 に得 ら れ ない場 合 もあ る

この よ うに従来手法 の並列化 は

,更

新 処理 が複 雑 にな り

,同

期や通信 処理 といつ たオーバ ーヘ ッ ドの発 生 が問題 とな る

 

この よ うなオ ーバーヘ ッ ドの発 生 と

,並

列性 の確保 が 同時 に行 える行 列構 造 は

,行

列構 造 が 素子 をス タンプ した段 階で対 角行列

,ま

たはブ ロ ック対角行列 とな る場合 で あ る

 

これ は

,対

角行列

,ま

^たはブ

ロ ック対角行列 の場 合 には

,対

角成 分 の任 意 の要 素

,ま

た はブ ロ ックで行列 を分 割す る こ とがで き

,分

割 した部 分行 列 ご とに独 立 して解 を得 られ る

 

従 つて

,並

列化 に よる高速化 で は

,オ

ーバ ーヘ ッ ドの発 生 が少 ない並列性 の高 い新 たな手法,

特 に回路行 列 をス タ ンプ した際 に既 に対 角行 列

,ま

た はブ ロック対 角行 列 とな る

第

1章  

序論

手法へ の適 用 を行 うこ とが求 め られ る^.

1.3  本論文の 目的 と構成

本論文では ,従 来手法よりも並列化に適 している手法に基づき ,投 入する計算 機資源に応 じた高速化が得 られる回路シミュレーション技術を確立することを目 的とする.ま た ,電 子回路の設計では ,抵 抗 とキャパシタンス,イ ンダクタンスと いった線形素子のみではなく ,ダ イオー ドや トランジスタなどの非線形素子を含 んだ回路網の解析を行 うことが必要 となる   しかしながら ,本 論文では ,特 に線形 素子のみで記述 された電源

_/グ

ラィ ドプレーンの高速化に論点を絞るものとする

本論文では ,2章 でクラウドコンピューティングを用いて並列計算機を構築 し,高

速に回路の過渡解析ができる手法の一つである

Latency lnsertin Method(LIM)p刻 に並列化 を施 した並列分散型

L取

1卜3,34,3司 を用 いることで

,LIMの

並列性 の高 さとクラ ウ ドコン ピューテ ィングによる大規模 並列計算機 の有効性 につ いて述べ る

p6,343章

では

,近

年

,浮

動小数′点の演算処理 を行 うことがで きるよ うになっ た

GPUを

用 いた

LIMの

高速化 について述べ る

p8,39,4q.こ

_{れ は}

,数

値計算分 野の用途 で も大 き く注 目され るよ うになった

GPUに

対 して

,CPUと

は異 なるプ ログラ ミングモデル に基づ く適用 を行 つた ものである。そのため

,最

適化 に対す

第

1章  

序論

るた めの最適 化 につ いて も示す

 4章

で

,LIMを

寄生素子 を含 む 回路網 を解析 で きるよ うに拡 張 したアル ゴ リズムであるブ ロック

LIMの

並列化 に よる高速化 につ

いて述べる 降

^1,4鋼

.こ れは ,並 列分散型 LIMと 同様に並列化を行 うことができ

^,

かつ ,回 路構造に依存す るが利用 した PEの 数に応 じた高速化が可能であること

を示す。最後に ,5章 で本論文の総括を行 う

第 2 ^早 クラウ ドコンピューティング

と並列分散型 LIMに _よる高速

過渡解析

2.1  概 要

従来

,並

列計算機 資源 の獲得 には

,サ

ーバ機器類の購入 と設置

,保

守

,電

気 代 が必要であ り

,維

持す るだ けで も多 くの費用が発 生す る

 

特 に十台以上の計算機 をネ ッ トワー クで接続 した場合 には

,あ

る一台の故障 によ り並列計算機 が利用で きない状態 も発生す る。そのため

,研

究室 な どの規模 の小 さな組織 で

,並

列化 し たプ ログラムの実行 のた めに大規模 な並列計算機資源 を獲得す ることは悩ま しい 問題 の一つ である

近年

,計

算機 資源 の提 供方法 に大 きな変化 があ り

,新

たな提供方法 はクラ ウ ド コンピューティングと呼称 されている

 

クラウ ドコンピューテ ィングとい う言葉 自

第

2章  

クラウ ドコンピューテ ィング と並列分散型

LIMに

_{よる高速過渡解析}

ら

,計

算機 資源 のア ウ トソー シング と考 えた場合 には

,必

要 とす る計算機 資源 の 規模 を任意 に変更で き

,か

^つ

,導

入 コス トを必要 としない点 は

,普

^段

,研

^{究室 内}

で利 用す るのは困難 な大規模 な並列計算機 の構 築 を可能 にす る

 

これ は

,市

販 さ

れている PCを ネットワークで接続して構築する Pcク ラスタト司のことである また ,必 要とする金額は利用した計算機資源 ,つ まり ,サ ービスの種類とインス

タンス数

,利

用時間 に比例 した費用 のみであ り

,利

用の仕方 に よつては従来の計 算機 資源 の導入 と比べ て非 常に効果 的である と考 え られ る

 

しか しなが ら

,ク

ラ

ウ ドコン ピューテ ィング を計算機 資源 と捕 らえて科学技術計算 を行 つた場合 に ど の よ うに用いるのが効果 的であるかは述べ られていないため

,並

列化 に対応 した アプ リケー シ ョンを実行 す ることで検証 を行 う

並列化 に対応 したアプ リケーシ ョンには

,Lttenり Insertion Method(LIM)p刻

に並列分散処理化を施した並列分散型 ^LIMを 用いる _F3,34,3■ LIMは 陽的な差 分法の一つである

^leapfrogア

ルゴリズムに基づく手法であり ,従 来手法と比べて数 十倍から数百倍高速に回路の過渡解析を行える手法であるい 2,33,34,44,45,4q.

また

,小

規模 な並列計算機環境 では高い並列性 が得 られている

.し

か しなが ら

,大

規模 な並列計算機環境 下での並列化 の効果 が議論 され てお らず

,そ

の並列化の効 果 を検証す る必要がある^.

本 章では

,ク

ラ ウ ドコン ピューテ ィングを用 いた並列計算機 を構築 し

,そ

^の上

第 2章   クラウ ドコンピューティングと並列分散型 LIMに _{よる高速過渡解析}

で並列分散型

LIMに

よる性能評価 を行 うp6,3η_{。 ここでは}

,Amazon EC2卜 4に

よつて提供 されているサー ビスを用いる。また

,検

証では他 の並列計算機 システム との速度 向上の倍 率 を比較す る こ とで

,ク

ラ ウ ドコン ピューテ ィングに よる並列 計算機 システム と並列分散型

LIMの

_{評価 を行 う}

 

最終的 に

,ク

ラ ウ ドコン ピュー テ ィングによつて構築 した並列計算機 が大規模並列計算機 資源 として効果的であ るこ とを示す

2.2  クラウ ドコンピューティング

クラウ ドコンピューテ ィングは近年頻繁 に耳にす るバズワー ドの一つであ り

,明

確 な定義 はない

 

そのた め

 

本論文 中では

PCク

ラス タを構築す るために一時的

に利 用できる計算機 の提供サー ビス とす る

.こ

の クラ ウ ドコンピューテ ィングで は

,イ

ンスタンスの種類 と利用数

,利

用時間に よって利用料金 が決定 され る

.イ

ンスタンスは

,CPUや

メモ リ容量 な どの計算機 の構成 によつてい くつかの種類が 提供 され てお り

,利

用者 が任意 に選択 で きる。また

,利

用す るイ ンスタンスの規 模

,す

なわち利用す る計算機 の台数 について も任意 の時刻 に任意 の規模 に変更で きる

 

このイ ンス タンスの種類や料金な どはサー ビスの提供業者によって異なる ため詳細 は述べ ない

第

2章  

クラ ウ ドコン ピューテ ィング と並列分散型

LIMに

_{よる高速過渡解析}

を構築す る。 この並列計算機 は

,サ

ー ビス提供業者が用意 しているコマ ン ドを用 い る ことで

,直

ちに計算機 の規模 を任 意 に変更す ることができる

 

す なわ ち

,計

算機 資源 を大量 に必要 とす る ときには新 た なイ ンス タンス を立ち上 げることで規 模 を増加 させ

,必

要 としない時には利用 しないイ ンスタンスを終了す ることで規 模 を縮小 させ られ る

.ま

た

,ク

ラウ ドコン ピューテ ィングを用いた場合 には

,利

用料金 の関係 か ら必要 とす る ときに必要 な規模 のイ ンス タンスを適切 に用い る こ とが求 め られ る^.

2.3 ^Latency Insertion Method (LIM)

2.3.1 0riginal LIⅣ

I

LIMは

回路の過 渡解析 のためのアル ゴ リズムの一つであ り,leapfl・。

gア

ル ゴ リ ズムに基づいた手法である。従来の

SPICE系

シ ミュ レー タは行列演算 を用いるた め

,大

規模 回路 に対 して非 常 に多 くの計算 時間を必要 とす る

.一

方

,LIMで

^は行

列演算 を必要 としないため

,従

来 の

SPICE系

シ ミュレー タ と比較 して非常 に高速 に大規模 回路網 の過渡解析 を行 える^.

しか しなが ら

.LIMは

回路 の過渡解析 を行 うためには特定の回路構造 を必要 と す る。その特定の回路構造 を図

21に

示す

 LIMの

解析対象 は図

21(a)で

示す単位

第

2章  

クラウ ドコンピューテ ィング と並列分散型

LIMに

よる高速過渡解析

L Rα ^み

(a)単 位セル

tι

^ILι ソι

(b)枝^{部の構成要素}

第

2章  

クラウ ドコンピューテ ィング と並列分散型

LIMに

よる高速過渡解析

セルが複数接続 された構造であ り

,図

^21(b)と 図21(c)に示す よ うに枝部 と節点 部 によ り構成 され る

 

枝部 は直列 に接続 された抵抗

,イ

ンダクタンス

,電

^{圧源 で}

構成 され

,同

様 に

,節

点部 は並列 に接続 された コンダクタンス

,接

地 キャパ シタ ンス

,電

流源 で構成 され る

 

そ して

,枝

部 と節′点部 にはそれぞれイ ンダクタンス とキャパ シタンスが存在 す ることが解析 を行 う際 の条件 である

.そ

のため

,イ

^ン

ダクタンス とキャパ シタンスが存在 しない場合 には微小 な値 の素子 を挿入す る こ とで解析 を行 うことがで きるよ うにす る

 LIMで

は

,枝

部 で電流

,節

点部で電圧 を求 めるが

,電

流 と電圧 の時間ステ ップがそれぞれ半時間ステ ップずつ異 な る時 間に配置 され る

 

そのため

,電

流 と電圧 を交互 に更新す ることで過 渡解析が行 わ ねノる

ここで

,任

意の節点間に流れ る枝の電流 をづαし

,任

意 の節点の電圧 を

%と

^し

,時

間 ステ ップをれ

,時

間刻み幅 を △tと す ると

,図

^21(b)と

KVL(Kirchho「

ヽお

hage

La、

v)か

ら式

 (231)が

, 図21(c)と

KCL(Kirchhofも Current Law)か

ら式

(232)が

得 られ る

an+t/2

-,f,*,/, - t-(ry) * o"ony- lff,/,

^(2.3.1)

件

刺

  毛

︼   7) ^I

^{G ou!+1/2}

^{- P" o.3a}

第

2章  

クラウ ドコンピューテ ィング と並列分散型

LIMに

_{よる高速過渡解析}

(231),(232)を

未知変数 について整理す る と

LIMの

更新 式

(233),(234)

が得 られ る^.

o3o

ここで

,式 (233),(234)の

時間刻み幅である △ιは取 りうる値に制限があ り,

最大値 は解析対象 の回路 中にあ る最小のイ ンダクタンス とキャパ シタンスの素子 値 に依存す る

 

時間刻み幅の最大値 の条件 式 は式

(2.35)で

与 え られ る 卜制^.

づ 腋

^{1 五め[三}

i:二

重L空づ先+∠^｀1(υ_f+1/2̲υ『^+1/2̲卜 _E湯11/2)

υ _,+1/2=τ

了ギ考量に

=υ

I 1/2+乱

         (̲1]を

‰十力 T)

△ι れα ω<νり 善

ιた

¨ 炒 ｍ 日

Ｑ 一 可

／

′

︲

︲

︲ ヽ

(23o

(23つ

ここで ,馬 は回路中の総節′ 点数 ,窮 は節′ 点′に接続している枝の総本数 ,為

,た

は 節点′に接続している枝構造に含まれるインダクタンス ,oは _{節点′の接地キャ}

パシタンスである

^.

式

(233),(234)よ

り

,電

流

,電

圧 の更新 では共 に 自身 の過去の値 と

,半

時 間ステ ップ前 の電流 または電圧 の値 を参照す る

 

そのた め

,全

て既知の値 を用 い て更新処理 を行 うことになる。そのため

,電

流

,電

圧 は

1変

数 ごとに独 立 して更

第 2章   クラウ ドコンピューティングと並列分散型 LIMに _{よる高速過渡解析}

モ リ参照を必要 としない

 

この こ とは

,LIMが

並列計算 に適 してい ることを示唆 してい る^.

2.3.2  _{並列分散型} LIM

LIMは ,FDTD法 ^と同様に

^leapttogア

ルゴリズムに基づいてお り ,FDTD法 を 並列化 した場合には利用 した計算機資源に比例 した速度向上が得 られる降釧.そ の ため ,LIMの 場合でも同様の速度向上が得 られ ることが期待でき ,並 列化を行つ

た並列分散型 ^LIMが 提案されているい

^3,3牛

  しかしながら,大規模な並列計算機

環境 での並列化 の効果 は確認 され てお らず

,大

規模 な計算機 環境 での速度 向上の 検証が求 め られてい る。

並列分散型

LIMは

_通常の

LIMと

は異 な り

,複

数 の

PEを

用 いて過渡解析 を行 う 手法である

 

そのため

,通

常の

LIMで

行 われ る前処理 に加 えて計算領域の分割処 理が加 わ り

,過

渡解析 の更新処理 にオーバヘ ッ ドが現れ る

 

これ は

,更

新手順 の複 雑化 と同期

,通

信処理 が加 わることを意味す る

 LIMの

解析対象 を^6× 5セルのプ

リント基板の電源

_/グ

ランドの等価回路とし ,PE数 を 2,す なわち ,三 分割した時 の解析領域の領域分割を図 22と 図 23に ,過 渡解析のフローチャー トを図 24に _示

す

.図 22と

図

23に

示す よ うに

,各

部分回路 は均等 な計算領域 となるよ うに分割 す る

.計

算領域 の分割 で注意す る点 として

,境

界 とな る部分の電流変数 と電圧変数

第

2章  

クラ ウ ドコンピューテ ィング と並列分散型

LIMに

よる高速過渡解析

I′

1/

f7 _1/

g/

部分 回路

#1

3‐

ヒル

I=― I二

I

C  d    

^ι_′%″半

2  d  C  f   g

図 2.2:並 列分散型

LIMの

領域 分割^.

分回路 紗

3‐

ヒル

が

Ｉ ｂ 工 ａ

Ｔ ち

Ｑ

Ч

部

第 2章   クラウドコンピューティングと並列分散型 LIMに _{よる高速過渡解析}

in.r+l

眩 重複する節点

%更 新しない 境界の枝 目 通信する 境界の枝

:部

分回路紗

図

23行

列で表 した領域分割

q

PE2

´       ヨ

プ     謹

ψ      

■

プ     十

PEl:部 分回路

^#1

騰 ^L̲L

第

2章  

クラ ウ ドコン ピューテ ィング と並列分散型

LIMに

よる高速過渡解析

図

24並

列 分散型

LIMの

フ ロー チ ャー ト

゛●＋い＝ト く一

＋ い

＝ い

境界の電流

(れ

がの更新

^{境界の電流}(続″^)の更新

境界の電流ctぉ の通信 境界の電流

(ち

にθ

^oの

通信

境界を除く電流

(jαたらゃブレ蘊εDの 更新

境界を除く電流

(ら

た 勲

^Jた

ュ

^)の

更新

境界を除く電圧

(να々ソ″

b)の

^更新

境界を除く電圧

(ッ

″れれ

Dの

更新

電流の通信処理 完了待ち

電流の通信処理 完 了待ち

第 2章   クラウ ドコンピューティングと並列分散型 LIMに _{よる高速過渡解析}

を重複 して保持す るこ とである。 ここでは

,電

流変数^Ocた_,aる ^Oαた,eた(考

=1,2,…

^,,6) と電圧変数 物ん(ん

=1,2,…

,6)が 重複す る変数 である

 

これ らは

,通

信処理 に非 同期処理 を用いて計算処理 と重複 させ るために用い る 卜^q。

̲般

_{的 に}

_,並

_列計算で

はプ ログラム中に存在す る逐次処理 を最小 に しなけれ ば性能 を得 られ ない。ネ ッ トワー クを介 した通信処理 は

,CPUで

の計算処理 に比べて多 くの時間を必要 とし,

そのままでは多 くの時間 を必要 とす る逐次処理 として現れ る

.そ

のた め

,通

信処 理 と計算処理 を重複す ることで逐次処理 として現れ る通信時間を最小 に してい る

並列分散型

LIMは

図

24に

示す よ うに

,先

ず

,境

界 に位置す る電流変数 の更新 を行 う。 ここでは

,PElは

^jcん,αたが

PE2は

じαん,cた が対応す る

.そ

して

,行

列 では横 線 で囲まれた部分 の係 数 を利用す る変数 である。更新 した電流 変数 の値 は

,非

同 期 関数 を用いて各

PE間

で通信 を行 う。すなわち

,PElで

^{は じ}aた_,cん を

PE2で

は をcた,醗

の計算処理 を通信処理 に置 き換 えることになる

.こ

れ は

,斜

線 で囲 まれた部分 の 係数 を利用す る要素 が計算処理 を経ず に更新 され ることにな る

 

そ の後

,重

複 し て保持 され てい る電流変数 と電圧変数以外 の更新 を行 い

 

最後 に

,電

流変数 の通 信 が終了す るの を待 つた後 に υαたの更新 を行 い

1時

間ステ ップの更新 が完 了す る 並列分散型

LIMで

は

,こ

の一連 の処理 を解析終了時刻 まで繰 り返 して行 うことで 過渡解析 が行 われ る

ここで図

23に

示す行列 を用いて

LIMの

係数行列 の分割 を再考す る と

,LIMの

第

2章  

クラウ ドコン ピューテ ィング と並列分散型

LIMに

よる高速過渡解析

アル ゴ リズムでは各要素 の接続 関係 を示す接続行列が更新時 には右辺側 に配置 さ れ

,結

果 として対角行列 を解 くこ とが挙 げ られ る

.対

角行列 のみ であるため

,任

意の要素での行列 の分割 を実現で き

,か

^つ

,任

意 の数 の

PEを

用 いて並列計算 を行 うことができる。加 えて

,各 PEが

担 当す る領域 のみを保持すれ ば よいた め

,必

要 なメモ リの量に応 じた並列計算機環境 を提供す ることによって

,単

^一の

PEで

_は解

析 できない対象であつて も解析 を行 うことが可能 となる。

2.4  計測結 果

ここでは

,LIMが ^SPICE系

のシ ミュ レー タよ りも高速であることの確認

,ク

ラ ウ ドコンピューティングを用いた並列計算機 でプ ログラムを実行 した時の効果

,そ

して

,並

列計算機 の規模 を大規模化 した時の性能 について順 に検証 してい く

 

^こ

こでは ,図 25に 示す電源

_/グ

ラン ドプレーンの等価回路網を用いる   ^また ,全 ^て

の解析で ,入 力波形に遅延

^0 2nsec,立

ち上が り

0 1nsec,立

下 り

0 1nsec,パ

ルス 幅

^1 0nsec,振

幅 005Aの 電流を入力 し ,観 測点として右下に位置する節点の電圧

を測定する

^.

第 2章   クラウ ドコンピューティングと並列分散型 LIMに _{よる高速過渡解析}

観測点

鷹       I   I

図 25:電 源

_/グ

ランドプレーンの例題回路

^.

第

2章  

クラ ウ ドコンピューテ ィング と並列分散型

LIMに

_{よる高速過渡解析}

表

21:HSPICEと LIMの

実行 時間 の比較 セ ル数 実行 時間 _(sec)

HSPICE

^LIN〔

400

468 039

10,000

93588 578

2.4.l LIMと SPICE系 シ ミュ レー タの比較

LIMと SPICE系 シミュレータとの比較では ,代 表的な SPICE系 シミュレータ

の一 つ で あ る

HSPICEと

比 較 す る こ とで 検 証 す る

 

まず

,LIMと HSPICEで

⁴⁰⁰

セルと

10,000セ

ルでモデル化した電源

_/グ

ランドプレーンの等価回路の解析し ,計 算時間と出力波形の比較を行う。図 ^{26に 400セ} ルでモデル化された電源

_/グ

ラン

ドプ レー ンの等価 回路網 を解析 した ときの出力波形 と表

21に HSPICEと LIMの

計算時間を示す

.こ

の計測では

Sparcv9 1GHzを

搭載 した計算機 を用 いた

 

解析 結果 と計算時間の比較 によ り

,LIMは ^HSPICEと

同様 の出力波形 を得 ることがで きる

 

また

,計

算 時間は 10,000セ ル を解 析 した ときには160倍_{以上高速 に解析す} る事ができ

,LIMが

非常に効果 的な手法で あるこ とが分か る

2.4.2  クラウ ドコンピューティングと既存の並列計算機の比較

第

2章  

クラ ウ ドコンピューテ ィング と並列分散型

LIMに

よる高速過渡解析

006

,004

ピ

0

> 0.020

--- _LIM

-

HSPICE

0      2      4   [1×

lo 91

■me(Sec)

図 2α 出力波形

第

2章  

クラウ ドコンピューテ ィング と並列分散型

LIMに

よる高速過渡解析

並列分散型

LIMは MPI卜 Jを

用いて並列化 を行 っている

.す

なわ ち

,計

算機環境 に よるプ ログラムの差 はない

.例

題 回路 として,1,000,000セ ル,4)000,000セ^ル, 9,000,000セルでモデル化 した回路網 を用い

,1000時

間ステ ップまでの実行時間を 計測 を行 つた

.ク

ラ ウ ドコン ピュー テ ィングは

,AmazOn EC21471の

エ クス トラ ラー ジイ ンスタンス を2イ ンスタンス用 いて分散 メモ リ型の並列計算機 を構築 し た

 

エ クス トララージイ ンスタンスの1イ ンスタンスの構成を表

22に

示す

,本

来 な ら

,各

イ ンスタンス間のネ ッ トワー ク構成 が問題 となるが

,仮

想化 されたネ ッ ト ワー クであるため単にネ ッ トワークで接続 された構成であるとだけ述べる

 

また,

分散 メモ リ型 の並列計算機 とは

,並

列計算機 システ ムを構成す るそれぞれの計算 機 が独立 したメモ リ領域 を持つてお り

,異

なる計算機 同士では互いのメモ リ領域 を 参照できない構成 であ る。 ここでは

,各

イ ンス タンス間でのメモ リ参照ができな い ことを意味 している。比較対象 とす る既存の並列計算機環境は,SGI Altix4700 を用いた

 Alti逝

700の_{構成 を表}

23に

_示す

.加

えて

,ク

ラウ ドコン ピューテ ィン グ とは異な り,Altix 4700は共有 メモ リ型 の並列計算機 である

.共

_{有 メモ リ型 の並}

列 計算機 とは

,分

散 メモ リ型 の とき とは違 い並列計算機 全体で一つ のメモ リ領域 を共有 してい る構成 で あ る

.ま

た

,ク

ラ ウ ドコン ピューテ ィングの場合 では

,割

り当て られ たプ ロセ スは コアによって計算 が行 われ るのに対 して

,Alt破 4700で

第

2章  

クラウ ドコンピューテ ィングと並列分散型

LIMに

よる高速過渡解析

表

22:エ

クス トララー ジイ ンス タンスの計算機構成^.

CPU周

波数

23 GHz CPU数

^０一

コア数 8コア

メモ リ ₁₅ GByte

表

2&SGI Altix 4700の

計算機構成^.

CPU

Itallliun 1 6 GHz

CPU数

16

メモ リ

32 GBメ

e

ネ ットワーク NUMA

そのため,Altix 4700は多数の

CPUに

よつて構築 された並列計算機 である といえ る。表

24に CPU数

とコア数 の比較 について示す

 

表

27に ,各

並列計算機 での

PE数

を増や していつた速度 向上の倍 率の比較 を示す。

Altix 4700で 実行 した場合 には

,PEの

数 を増やす につれ て速度 が向上 してい く が

,ク

ラウ ドコンピューテ ィングを用 いた場合 には

PE数

が

8以

上では速度 の向上 を得 るこ とができない ことがわか る

 

これ は

,計

算機 のアー キテ クチャの違 いに よつて生 じてい ると考 えることがで きる

.す

なわち,Altix 4700で は各

CPUが

メ モ リを参照す るためのバスを占有できるのに対 して

,ク

ラ ウ ドコンピューテ ィン グを利用 した場合 には

,一

^つの

CPUか

らメモ リヘのバ スを複数 の コアで共有 して い る

 

そのため

,各 CPUへ

^2個以上のプ ロセ スが割 り振 られ た場合 には

,メ

モ リ

第

2章  

クラウ ドコンピューテ ィング と並列分散型

LIMに

よる高速過渡解析

図 2■ 速度 向上の倍率 の比較^.

０   ８   ６   ４   ２   ０   ８   ６   ４   ２   ０ ２   １   １   １   １   １

︵鯉

︶ヨ

＝ 恒 廻 躙

‑1,000,000単^{位 セル (CIoud)}

‑4,000,000Ц^{自位 t,レ (Cloud)}

‑9,000,000単位 セル (Cbud)

→← 1,000,000単 位 セル(ALix4700)

‑4,000.000月^に1立tル (A tix4フ00)

‑9,000,000増^に位tル (A tix4700)

6     8 PE数

第

2章  

クラウ ドコンピューテ ィング と並列分散型

LIMに

_{よる高速過渡解析}

表

24 CPU数

とコア数 の比較

SGI Altix4700 Cloud Computing System

CPU数

^{16 4}

Core数

16

とコアの間のデー タ転送 が計算 に対 して転送量が不足 しているた めであ ると考 え られ る

.こ

れ によ り

,並

列分散型

LIMは ,ハ

ー ドウェアによる制限を受 けなけれ ば高速 に回路 の過渡解析 を行 うことができる手法で あ る と考 え られ る^.

2.4.3 

大 規 模 並 列 計 算 機 で の 性 能 検 証

次 に

,ク

ラ ウ ドコン ピューテ ィングを利 用 し

,大

規模 並列計算機 を構築 して検 証 を行 う。 ここではエ クス トララー ジイ ンス タンスを 16イ ンスタンス用 いて構築 を行 つた

 

これ は

,CPU数

^では

32個 ,コ

アについては128個_{か らなる並列計算機} である

.前

_{節 で}

CPU数

^の

^2倍

程度 の

PE数

で あれ ば速度 の向上が得 られ ることを 確認 したため

,64PEま

^{で順 に}

PEの

数 を増や して計測 を行 う

 

図

28に

_実行時間

の推移 を図

29に

速度 向上の倍率 を示す

.速

度 向上 については

,32PE付

近 までの 間は順調 に増加 し

,lPEの

^{時 と比べて}

^2575倍

の高速化 を得 られ た

 

この結果 は^, 非常 に高い並列化 の効果 を得 られ てい るこ とがわか る。速度 向上 の倍率 とプ ログ ラム中の どれ ほ どまで を並列化す ることがで きたか を示す アムダール の法則 を式

第

2章  

クラ ウ ドコン ピューテ ィングと並列分散型

LIMに

_{よる高速過渡解析}

(241)に 示す

S=哉 941)

ここで

,Sは

並列計算実行時の速度向上の倍率,7・は並列化 可能 な部分 と並列化不 可能 な部分の比である

 

式

(241)よ

^り

,並

列分散型

LIMは 99%以

_{上の部分を並列} 化す ることが可能であることを示 している

 

しか しなが ら

,実

行時間が

32PEま

で は減少 し

,そ

れ以降は実行 時間の減少が飽和 した状態になる

 

す なわち

,シ

ステム のオーバヘ ッ ドが現れていると考え られ る

 

先 ほ どまでの計測結果 によ り

,Altix 4700で

_は

16PEま

での間は順調 に速度の向上を確認できていた

 

そのため

,ク

ラウ ドコンピューテ ィングでは

32PE以

上 を利 用 した場合には

CPuと

_{メモ リ間のデー}

タ転 送が飽和状態にあると考えられ る そのため

,ク

ラ ウ ドコン ピューテ ィング を用 いる場合 には

,得

たい速度 向上の倍率によって

CPuの

数 を選択すれ ばよい こ とが分か る

 

す なわち

,更

に速度 が欲 しい場合 には多数のインスタンスを用いて,

プ ログラムを実行すればよい

2.5  _{本章 の総括}

本章では,ク ラウドコンピューティングを用いて Pcク _{ラスタを構築し} ,並 列分

第 2章   クラウドコンピューティングと並列分散型 LIMに _{よる高速過渡解析}

図

28:実

行 時間^.

図 2針 速度 向上の倍率

―●‑1,000,000単_位=ヒフレ ー●‑4,000,000単_位=ヒフレ

→卜_9,000,000単位セル

０

︵８ じ 肛 士 ｔ

Ⅸ

16    24    32 PE数

40    48    56    64

‑1,000,000単 ^位tル

ー 4,000,000単位tル

ー 9,000,000単位 セ ル ３５

３０

万

ｍ

ｌ５

Ю

５

０

準︵ ヨ︶

＝ Ｅ 拠 爛

16    24    32    40    48    56    64 PE数

第 2章   クラウ ドコンピューティングと並列分散型 LIMに _{よる高速過渡解析}

並列化で きる高い並列性 を有 してい ることを示 した

.ク

ラ ウ ドコン ピューテ ィン グを用いた並列計算機 では

,並

列 分散型

LIMの

速度 向上の倍 率か ら

CPU数

と同 数までの

PEで

あれ ば理想的に速度 向上 を得 られ ることを示 した。これ は

,解

析規 模 に応 じた

CPU数

を持つイ ンス タンスを用い る事 によ り

,利

用者 が必要 とす る計 算速度 の向上 を得 られ ることがで きることを示 している

また

,大

学内で共有 してい る大型 計算機 の場合 には稼動率 の関係 か ら

,多

数 の 利用者 が共同で利用す る

 

そのため

,実

行 ジ ョブの管理 には多 くの場合 にバ ッチ方 式が用 い られ てい る。 この こ とは

,利

用者 か らはバ ッチシステ ムに登録 した 自ら の実行 ジ ョブがいつ実行 され るかを管理することができない ことを意 味す る

 

対

して

,今

回のよ うにクラ ウ ドコン ピューテ ィングを用いた場合 には

, 

自由に計算 規模 に応 じた計算機 を占有す るこ とがで きる

.し

か しなが ら

,利

用料金 が発生す るため

,常

に並列計算機 を構 築 した状態 に してお くのではな く

 

^{必要 とす る とき}

に必要なだ けのイ ンスタンスを用 いて並列計算機 の構築を行 うことが求められ る。

第 3章 GPGPUに 基づ く LIMの _高

速過渡解析

3.1  概要

GPU(Graphics Processing Units)￨ま

CPUと

は異な り,SIルIT(Single lnstruction, Multiple Thread)卜列 と呼ばれ るアーキテ クチャで設計 されてい る

 

これ は

,CPU

が複雑 な制御機能 を処理 できることに重点が置 かれているの に対 して

,GPUは

^メ

モ リ参照 と同時に大量のス レッ ドによる演算処理 に重点が置かれているためであ る

 

そ して

,画

像 の陰影処理 のた めに

GPU上

に浮動小数点演算ユニ ッ トが実装 さ れ

,画

像処理以外 の分野で

GPUを

活用す る 「

GPUを

用いた汎用計算

(GPGPU:

General Purpose computing on Graphcs Processing Units)」 が活発 に行 われてい

る 卜

^3,54,5司

.こ れは ,複 雑な制御を必要とする処理は CPUで 行い ,そ れ以外の 計算量を必要 とする処理で GPUを 用いる手法である。これには ,特 別な GPUを

購入する必要は必ず しも無い .す なわち ,一 般的な PCに 搭載 されている GPUを

ハー ドウェアアクセラレーションとして利用することが可能である

第

3章  GPGPUに

基づ く

LIMの

_{高速過渡解析}

2章

で

,並

列計算機 での高速化 について述べたが

,市

販 され ている

GPUは

最新の ものであれ ば100個以上 の演算 装置 が搭載 され てい る

 

そ のた め

,GPUに

よる高 速化 は多並列計算 と考 えるこ とが で き

,ま

^た

,一

つ のグラフィクスカー ド上 に搭載 され てい るメモ リを用 い るた め共有 メモ リ型 の並列 計算機 と考 え るこ とがで きる しか しなが ら

,前

述 の よ うに制御 処理 が不得 手 で あ るた め

,従

来 の

SPMD(Single

PrOraln Multiple Data)bqの

プログラミングモデルを用いた場合には性能を得る

ことができない。そのため ,ス トリームプログラミングモデルト

^31に

基づいたプ ログラミングを行う必要がある

2章

_{で並列分散型}

LIMが

並列化 に適 してお り

,投

入 した計算機 に比例 した高速化 の効果を得 られ ることを確認 している

 

そのた め

,GPUを

用 いた場合 には

,CPU

と比べ て非常 に高速 に解析 を行 うことが期待 で きる

 

そ こで

,本

章で は

GPUを

ハー ドウェアアクセ ラレー タとして用い

,GPUを

使 う上での最適化 と

LIMの

_高速

化 について述べ る^.

第 3章  GPGPUに 基づ く LIMの _{高速過渡解析}

3.2 GPGPU (General Purpose computing on Graph, ics Processing Units)

近年

,GPUに

よる浮動小数点演算が可能 にな り

,グ

ラフィックスカー ド上のメモ リと

GPU間

の メモ リバ ン ド幅が

CPUと

比べて非常 に早 いハー ドウェエ ア となっ た。 この浮動小数点演算性能 とメモ リバ ン ド幅を利用す る

,GPUを

用いた汎用計 算 (GPGPU:General Purpose colnputing on Graphcs PrOcessing Units)卜 司 が注 目を集 めてい る

 GPGPUで

は

,計

算アル ゴ リズムが並列化 に適 してい る場合

,高

性能な

GPU一

つ を搭載 した計算機で計算機数十台分の性能をまかな うことができ る。そのため

,並

列計算機 を構築す ることよ りも

,廉

価 に高性能な計算資源 を手 に 入れ ることができる

.さ

らに

,C言

語拡張 された開発環境である

CUDA(COmpute

Unined De宙ce Arditecture)卜列 の登場 によ り

,従

来のプ ログラムか ら

GPUを

利 用 したプ ログラムヘ の移植 が容易 とな り

,N体

問題や粒 子流体 の解析 に

GPGPU

が利用 されている 卜

^3,54,5司

.こ れは CPUで は実現が難 しかつた リアルタイム シミュレーションの実現が可能 となり ,N体 問題のシミュレーションで利用 され る GMPE卜

^61と

いつた専用ハー ドウェアがより容易に用いることができるとも言 える

^.

ここでは ,CUDAに 対応 した GPUの アーキテクチャと CUDAの プログラミン

第 3章  GPGPUに 基づ く LIMの _{高速過渡解析}

3.2.l CUDA(Compute unifled Device Architecture)

CUDAは GPUを

利用す るための開発環境 の一つで あ り

,他

に も

OpenCL卜

_」や

Brook1581と いつた開発環境がある。

CUDAの

利用 には

CUDAに

対応 した

GPUが

必要にな り

,こ

れは

CPUと

は異なる特殊 なハー ドウェアになる

 

そのため

,CUDA

で は特殊 な計算処理単位 が用い られ

, 

この計算単位 をス レッ ドと呼ぶ

.ス

レッ ド はプ ログ ラムの実行単位 の一つで あ り

,複

数 のス レッ ドが実行 され ている場合 に は

,同

じ命令 の処理 がス レッ ドごとに行 われ る

 CUDAで

は同時に実行可能 なス レッ ド数が非常に多 く

,こ

れ が高速 な計算 を可能 としてい る

 

この よ うに

CUDA

は特殊 な環境であるため

,CPUを

用 いた時のプ ログラ ミングモデル とは異な るス トリームプ ログラ ミングモデル ト制 を用い る。そのため

,CPUで

のループ処理 を 展 開 した特殊 なプ ログラ ミングを行 うこ とになる

 

そ して

,こ

^{のプ ログラ ミング}

モデルでは

,カ

ーネルによつて処理が

,参

照す るデー タの配列 をス トリー ム と し て管理 され る

CUDAで

は

,CPUの

^ことを

^Host,GPUの

ことを Deviceと 呼び Deviceで_実行 され る関数 のことをカーネル と呼ぶ

 

また

,De宙

^ceで処理 を実行す る際

,Hostか

らグ リッ ド情報 と共 にカーネルが発行 され ることで

D"iceで

処理 が行 われ る

 

^グ

リッ ドとは

,D"iceで

実行 され るス レッ ドを管理す る情報 をま とめた ものである^.

第

3章  GPGPUに

基づ く

LIMの

_{高速過渡解析}

ドによつて構成 され る

 

図

31に

グ リッ ドとブ ロ ック

,ス

レッ ドの関係 を示す そ して

,CUDAを

利 用 した計算 では

,メ

モ リアクセスの速度が演算性能に大 き な影響 を与 える

 

そのため

,同

じ計算 アル ゴ リズムであって もメモ リア クセ スの 方法によつては

,大

き く計算性能 が変化す る

.CUDAを

利用 して高い計算性能 を 導 き出す には

GPU上

に実装 された共有 メモ リや レジスタを利用 した効率的なメモ

リアクセ スが必須 とな る^.

3.2.2 CUDA対

応

GPUア

ー キ テ ク チ ャ

CUDA対

応 のアー キテ クチャは Single―Instruction,Multiple―Thread 1521と 呼 ばれ るアー キテ クチ ャによつて設 計 され てい る

.こ

れ は

,同

時 に多数 のス レッ ド によつて命 令 を実行す ることがで きるアー キテ クチ ャである

 

^ここで

CUDA対

応

GPUの

一つ である

GTX280の

ブ ロ ックダイ ア グラム を図

32に

示す。

GPUは

い くつかの

TPC(Te対

ure/ProceSSOr Cluster)か らな り

,1個

^の

TPCは 3個

の

SM

(Streaming Multiprocessor)と 襲 苅ure Unitに よ り構成 され る

 

そ して

,SMは

⁸

個 のSP(Streallling Processors cores)に よ り構成 され る。 この

SPが

実際に計算 を行 うプ ロセ ッサにな る。そのた め

,GPU上

に実装 され ている総

SPの

数 で

GPU

の計算能力が決定 され る

 

各

SMで

は

SM内

でのみ参照可能な

16KByteの

共有 メ モ リとコンス タン トメモ リ

,テ

クスチ ャメモ リと

8KBメ eの

レジス タを備 えてお

第

3章  GPGPUに

基づ く

LIMの

高速過渡解析

図

31:グ

リッ ドとブ ロ ック

,ス

レッ ドの関係

)avi

e,Y)

□ □

⁝□

第

3章  GPGPUに

^{基づ く}

^LIMの

^{高速過渡解析}

図

32:GTX280の

ブ ロ ックダイア グ ラム

スレッドスケジューラ

デバイス メモリ テクスチヤ

^/プ

ロセッサ

クラスタ (PC) ストリーミング マルチ プロセッサ (SM)

命令 ユニット

共有 メモリ コンスタントメモリ SP SP SP SP SP SP SP SP

テクスチヤユニット

第

3章  GPGPUに

基づ く

LIMの

高速過渡解析

り

, 

これ らの メモ リを効率的 に用 い ることが性 能 向上 の鍵 とな る

3.3 GPGPUに 基 づ く LIM(GPGPU… LIM)

GPGPU― LIMは ,LIMで

最 も計算量を必要 とす る電流 と電圧の更新処理 を

CPU

ではな く

GPUを

用い る手法である

 GPGPU― LIMで

は

,通

常の

LIMと

同様 に電 流 と電圧 を交互 に更新す るが

,電

流変数 と電圧変数 の更新 は変数毎 に割 り当て ら れたス レッ ドに よ り更新 され る

.LIMで

は式

(233),(234)よ

り

,電

^{流 または}

電圧 の各変数 の更新処理 において

,同

時刻 に更新 され る値 を参照 しない

 

そのた め

,各

変数 に割 り当て られ たス レッ ドは同時 に電流 または電圧 の更新処理 を行 え る

.す

なわち

,GPGPU― LIMで

^は

,更

新処理 を多数 のス レッ ドに よる電流 または 電圧 の同時 に多数 の並列計算 を行 うことで高速化 が実現 され る^.

LIMの

解 析 対象 を6×

5セ

ル とした時の例題 回路 を図

33に

示す

 

図

33中

に,

節点は^7×

6個 ,枝

は^7×

5+6× 6個

存在す る。

LIMで

は

,節

点に電圧変数が枝 に 電流変数 が定義 され るた め

,電

圧変数 を7×

6個 ,電

流変数 を7×

5+6× ^6個

用 いて過渡解析 を行 うことになる。従つて

,通

常の

LIMで

解析対象が π×π セルの 場合 に

,電

圧変数 は (η

+1)×

(れ

+1)個 ,電

流変数 につ いては^(れ

+1)×

π 個 と り×

+1)個

の二次元の変数配列の確保 し

,メ

モ リ参照時には順 に参照を行 う。