MMXテクノロジによるCAシュミレータの高速化: University of the Ryukyus Repository

Title

MMXテクノロジによるCAシュミレータの高速化

Author(s)

赤嶺, 有平; 遠藤, 聡志; 山田, 孝治

Citation

琉球大学工学部紀要(60): 119-125

Issue Date

2000-09

URL

http://hdl.handle.net/20.500.12000/13817

Rights

琉球 大学工学部紀要 第60号.2000Ll･'･

MMX

テ クノロジに よる

CA

シ ミュ レー タの高速化

赤嶺 有平 一

,

遠 藤 聡 志 州,

山 田 孝 治 *

'

Acceleration ofCellularAutom ata SimulatorUsing

MMX

Technology YulleiAIくAMINE■, SatoshiENDO ' and KojiYAMADAH

Abstract

CellularAutomata(CA)areinherentlysuitedforparallelI)rOCeSSing,andhavebccncharacterizedas easytopal･alleliBe･ThererorctheirsimulationllaSpl･OSPCCLsorspCCdingupusingSIMD (SingleInstruc -t.ionstream.Mult･ipleDatastream).Furthermorealow-costCPU hasbeenhadSIMD suchasMMX technology.MMX technology)sakindoTSIMD whatpermitsoneinstructio】一CyCIctoactonmultiple datapleCeSandisSIMDwhatmaybeoneorthemostfamoustechI10logleS.Inthispaper,weproposea mctl10dofhigh-speedCAsimulationusingMMXtechllOlogywit110utdedicatedpurposehardware.The resultsofsimulationsrCPreSenH hatourmethodisbetterwith7timesthanscalararithmetic.

KeyW ords: MMX,SIMD,CA

1. は じめに

1950年代 に,S.Ulam と

J.

VOIINeumanllによって提 案 されたセルラオー トマ トン法 (CellutarAutomata,以下 CA と記す)は,簡単なセル間の局所的相互作用か ら,複 雑 な現象 を再現で きる手法である.その後の研究 により. 生態 (種の増軌 種の住み分け,捕食関係 など),反応 ･ 拡散現象 (生物の紋様形成,化学反応など),フラクタル 自然現象 (結晶成長.凝塊な ど),災害 (森林火災,地震 など),交通 (高速道路の車の流れ) といった,様 々な分 野に適応で きることが分っている [加藤

9

8

】

.

CAは本質的に高度なデータ並列性 を持 ち.並列処軌 二 向いているため.CA専用計算機の開発 【Margolus931や, 収用記述言語か らCA シミュレー タを自動生成するソフ ト ウエアの開発【Beck】,また.ネットワークで相互接続 され た複数の計算機で,CA を高速にシミュレー トするソフ ト ウエアの開発が行われている t平林

9

8

ト

これ らの システ ムは.それぞれ実装 レベルの違いはあるが,SlMDlの概 念 を用いて高速化 を行っている.SIMDは,一つの命令の 流れが複数のデ-タの流れ を処理する並列 アーキテ クチャ の一種である[Patterson96ト CA は全てのセルの更新処 理 を同時 に行 う必要があるため,SIMD を用いることで効 率的に処理で きる. 従来,SIMDをハー ドウエアで扱 うためには.スーパー 受理 :2000年6月 5円 一大学院理工学研究科梢糾_工学.T*攻 (M.-LStCL･Coust'i‖ColtlPLcxtnLclligentSysccms臥Igin･jCring.G･･払(L -LJatCSchoolorScicnccandEngineering) " 工学部情報工学科 (Dcpl.orlnrorl11at･ionri11ghlCC山1g,FactofEl一g･) )sillglcTnstrucLi川一StrtW一一Mu)tiplcDatastI･canl 119 コンピュー タや専用プロセ ッサが必要であったため,コス トが高 くなる傾向にあった.ところが,近年の半導体技術 の向上 により,パーソナルコンピュー タ用の廉価なCPU に もSIMD型並列演算命令の実装が一般的になって きた. したがって,これ らの技術 を用いることで,ローコス トで 高速なCA シ ミュ レータの開発が可能である. MMX テクノロジは,MMX テクノロジ Pentium プロ セ ッサ,Celcronプロセッサ,Pcnt.iumIIプロセ ッサ,Pe n-tiumlllプロセ ッサ に搭載 されたSIMD型演算命令セ ット である 【インテル99a]llnLOO】.これ らのプロセ ッサは一般 的なパーソナルコンピュータに採用 されているため,普及 率が非常に高 くかつ ローコス トである.また,プロセ ッサ を特定することにより,そのプロセ ッサに特有の放退化 も 可能である.MMXテクノロジによる並列化 と,この よう な揖適化技術 を組み合わせて.ハー ドウエアの もつポテン シャルを最大限に引 き出すことがで きる. 本研究の巨川勺は,汎用プロセ ッサ用のSIMD技術であ るMMXテクノロジを用いて.高速かつ低 コス トなCAシ ミュ レー タの開発 を行 うことである.本論文においては, 例題 としてライフゲームの シミュレー タをMMX テ クノ ロジを用いて作成する際の高速化手法 を述べ る.

2. MMX

テ クノロジと

SI

MD

2.

1

概要 MMXテクノロジは,マルチメデ ィアの処理 を高速化す るためにr朋 邑された技術である.マルチメデ ィアの処理_で は.大fLi･のデー タに対する単純 な操作の繰 り返 しがその処 卵 割Juの大半を占めることが多いため.複数のデータをま とめて処理で きれば効率的である.MMX テ クノロジは, sIMDの概念 を用いることで演算を並列化 し,処理の尚速 化 を問っている 【小

骨 97

1

.

1

20 バックド･データ 亦嶺 ･遠藤 ･山田 :岨Ⅸテ クノロジによるCAシミュレータの高速化 rT T 358まeedJ.I L

1

1

- 1- + + + + + +

1 1

⊥ ⊥ 1 1 1

1

Fig.L MMXのバ ック TL.･7- タ流乾の例 各要素16ビ.Jト(W) /人 ヽ 4要素(I) Fig.2.4×16バ ック fZ.デー タ SIMDとは,1つの命令 の流れが複数のデー タの流れ を 並行 して処理する機構である[Patterson961.MMXテ ク ノロジは

,6

4

ピッ トの演算器 を命令単位 で分割 して

,8

組 の8ビッ ト演算器,4組の16ビット演算器,2組の32ビッ ト演算器,1組 の

6

4

ビッ ト演算器 として動作 させ るこ と が出来 る [小

管 9

7

]

.

そのため.た とえば

8

組 の

8

ピッ ト 演算器 として動作 させた場合,逐次演算 に対 して

8

倍の性 能向上の可能性がある.

2.

2

パ ック ド･データ演算 パ ック ド･デー タ演算は,MMXテ クノロジの中核 とな る機能であ り,SIMD機構 に基づ く演算である.パ ック ド･ デー タ演算では,

6

4

ビッ トの演算器 を分割 して複数 の演 算器の集合 として動作 させ る.演算 を行 う際は,複数の

8

ビツI,16ビッ ト,あるいは32ビッ トのデー タをパ ック ド･データレジス タと呼ばれる

6

4

ピッ トの レジス タにパ ッ ク化 (packing)す る.パ ック ド･デー タ演算は,このパ ッ ク化 されたデー タに演算 を施す ことを意味す る (1). 定義 1:パ ック ド･デー タVが

,

Z個 の W ビットデー タ の集合である とき,パ ック ド･デー タVの i番 目の要素 と は

,i

w

ビッ ト日か ら

(

i

+

1

)

W

-1

ピッ ト目までの部分的 なビッ ト列で表 される値 である. パ ック ド ･デー タ演掛 ま,パ ック ド ･デー タ u,Vの各要 素叫 と V.Jに対 して独 立 した演算 を施す.本論 文では

.

I 個の W ビッ トデー タか らなるパ ック ド･デー タを

,

Lxw パ ック ド ･デー タ と表現す る.例 えば,

4

つの16ビッ ト のデー タをパ ック化 したデー タは4×16パ ック.ド･デー タ である (2).

2.

3

比較演算 比較演算 は,パ ック ト データ演算において条件判断 を 並列 に行 う命令である. 定義 2:Zxwパ ック ド ･デー タ a,bに対 して条件 を " 等 しい''とする比較演算 を適用 した とき,結果Cは以下の ように定義 される (3).

1

1

1

1 1 1 1

Fig.3.比較杭解 の例 / l ＼ ′

1

いBt岬 汀日 はptcew ,日 は叩 けII.叫 W

j

Pis.4.分 散 メモ り型SIMD マシン C 2･-

(

喜

W

(a

z

･

-b

l･の時)

(

a

z

･

≠ biの時) (1) ただ し

,i

=

(

0

,

1

,- ,

I

-

1

)

条件 としては,"等 しい (=)'',"よ り大 きい (>)''の

2

つ を 指定で きる. 本論文では,式 1を

C

-comp(

a=

b

)

と表記する. カ ッコ内の等号 は条件 を表す.

2

.4 データ分割法 2.2節 において,パ ック ド･デー タ演算では各 デー タを パ ック ド･デー タレジス タにパ ック化す る必要があること を述べ た.デー タ分割法 【天野

89

]

は,分散 メモ リ塑並列 計算機の概念 だが,MMXテクノロジのパ ック化 に対 して も有効である. パ ック ド･デー タ演算は,単一の演算命令がパ ック ド･ データの各要素に作用する.そのため,8x8パ ック ド･デー タ演算 を行 う時,MMXテ クノロジの演算器 は,8個の8 ビッ トプ ロセ ッサエ レメ ン ト (以下PEと記す)か らな る分散 メモ リ型SIMDマ シ ン[Patterson96】とみ なせ る (4).各pEは,8ビッ トの レジスタと演算器 を持 ち,並列 に動作す る. MMXテクノロジにおいて,パ ック ド･デー タレジス タ とメモ リ間の8バイ ト境界 をまた ぐアクセスは,大 きなペ ナルテ ィ (プロセ ッサ ･ス トール)を伴 う 【イ ンテル

9

9

C

1

ため, メモ リア クセスの際は位置合わせ (alignment)を 行 う (5).8個の8ビッ トPEか らなるSIMDマ シンの 観点か らは,メモ リ空間 を8つ に分割 し,それぞれの メ モ リ空間を各pEの ローカルメモ リとみなす ことが出来る (6). メモ リア ドレスは,全てのPEに同時 に指定 され. アクセス も同時に起 こる.パ ック ド ･デー タ演算は,PE のロ-カル演算であ り,パ ック ド･デー タレジス タ全体 に 対する シフ ト演算 は,PE間の通信 である. PEは, リモー トメモ リへのアクセスには,余分なコス トがかかる.従 って,演算に必要 なデー タをローカルメモ リに配置す ることが処理 を効率化す る. 2.5 データ構造の最適化

琉球大学工学 部紀要 第60g･,2000年

ペ

ナ

ル

テ

ィ

が

A

生

了ル

仙

"

'

A

L

-

1

二 :

:

二

∴

ニ∴

I

I

I

l

I

t

イ

ト

J

A

■

一

バ

イ

ト

J

I

J

I

t

バ

イ

ト

4

J

t

Fig.5.デー タ .ア ラ インメ ン ト Fig.6･ ロー *)レメモ リ 分散 メモ リ型

SI

MD

マシンでは,出来るだけ

PE

問通 信が少な くなるようにデータを分割 して各

pE

に割 り当て る 【天野891.パ ック ド･デー タ演算においては,データ のメモ リ上の配置 を並 び替えることにより処理 を効率化す る.例 えば,n

x8

個の要素 を持つ配列

al

i

】を

8×8

パ ック ド･デー タ演算で隣接す る要素間の演算 を効率 よく行 うた めに配列

b【

i

]

に並び替 える操作 は,以下の棟 に表現で きる (7).

fo

r(

i

=0;

i

く

8;

i

+

+)t

fo

r(

j

=0;

jく

n;

j

++)t

b[

j*8

+i

]≡a[

i

*

n+j

];

ナ I 通常の配置 8 0 -n

-m g∼ S ∼ 恥 _■ 1 _▲

_A

0

0

0

0

Om OI0008 01伽10

0

10018 0Z0020 0Z帥28 0zM D Ol0038 Jtl

J

7

I

F

'

レ

ス

a○ ▲ I ー ∴j::ド fl

≡

幸

三. 'Lij●..

1

○ I

川

lf I l7 jIHJ 7JT輔-1iJH Li叶 20 ZZ Z4 ZS2 〟

3

0 I 1

一I

II

J

7

転換後の

配怒

VLQV上tVuI/JJI

/

I

.

I

V

'

,

.I y 一応 Vl.7 ○ 一〇こlIf

2

0

-

/

オ-1○ 二ip . l 日:iJ.

2

1

こ

,

l

車

.:)IJ f I l一小一.21こ_.:# i 31-.i li

I I一 i,i一

f

I≡

ヰ

!. JJ 三や 二

● 川-一事JI●i,.iiT=IN 亨ヰ i. ; >.. a... ; >R 的 竹

Fig.7.隣接す る'&'･捌IJの油井 を効率 よく11･う配列 (V.は′i･yク ド ･デー タ)

121 この配置法 は,配列の隣接す る要素が同 じローカルメ モ リに存在するため,プロセ ッサ間の通信,つ まり,パ ッ ク ト データ演算におけるシフ ト演算 を不要に し

,

演算を 大幅に効率化 している.

3.

提案手法 提案手法は, CA シミュ レータにおけるセル状態の更新 処世 を

MMX

テ クノロジを用いて並列化 し,プロセ ッサ 特有の放適化 を行 うことにより,シミューシ ョンを高速化 するものである.対象 とするプロセ ッサは,

MMX

テ クノ ロジを搭載 したPentiumプロセ ッサである. 提案手法が対象 とする CA は,ライフゲームに代表 さ れる半合計的な CAである.この種の CA は,セルの新 し い状態 を隣接するセルの状態 と自身の状態 とのルールセ ッ トに基づいて決定する

【

L

a

d

d9

5

]

.

本論文では,半合計的 な CAのセル状態 を更新する処理における,近傍のセルの 状態値の合計 を求める部分 を "状態和の算出", また求め た状態和の値 にルールを適用 して新 しい状態 を決定する処 理 を "次状態の決定"と表現する. 提案手法では,パ ック ド･デー タ演算 を用いて状態和の 算出 と次状態を決定を行 うが,この処理 を効率的に行 うた めにデータ構造 を境遇化する.に示 したように,パ ック化 の際の配置を工夫する事で,余分なデータの移動 をな くす ことがで きる.この配置の転換 は最初に一皮行 えば よいの で.時間的なコス トは無視で きる. 本論文では,説明のためライフゲーム ･シミュ レー タに 対する具体的な最適化手法 を述べる.ライフゲームは,状 態和の算出,次状態の決定などの処理が一般的であ り,セ ル間のルールが単純2なことか ら,例題 として適当である と考えた. 提案手法の処理の概要 を以下に示す. step.1 パ ック ド･データ演算 を用いて近傍セルの状 態和の算出 を並列化する. step.2 比較演算を用いて次状態の決定 を並列化する.

3.

1

状態和算出の並列化 まず,近傍のセルの状態値 を合計す る処理 をパ ック ド･ データ演算で並列化する.

3.

1.

1

状態和算出の定義 ライフゲームのセル空間は2次元 なので. 〟 ×〃 の2 次元格子空間を考える.各セルは,0及び1の2つの状態 をとりうる.格子空間上の横方向を 3軸,縦方向 を y軸 として,セル座標 を位置ベ ク トルであ らわす.ただ し,左 上のセル座標 を原点

(

0

,

0

)

として,右方向 と下方向 を正 と する.3

'-(

C

,

y

)

の とき

,S

(

a,)は,左か ら

∬+

1番 臥 上 か ら

y+

1番 目のセルの状態値 を表す

(

8)

.

ライフゲームにおける状態和の算出は,以下の様 に記述 される.

∫

S(

a)

-

∑ S

_i

₌

(

訂+

｡･

)

0

(

2

)

2致ステ ップ程度の械根語で記述可能.

1

2

2

赤城 ･遠藤 ･山田 :仙Ⅸテ クノロジによるCAシ ミュ レー タの高速化 {…

r

N ーヽ Fig.8. M xNの2次元格子空rlq ■一 eIr/一:一 亡■■

-

-

′

＼

-

l

l

､

-

.

■

一

■

■

/

C1

亡

1

一■

一

Fig.9.近傍 8セル ただ し,

S(

a

;

)

は格子空間上の位置 詔における近傍8セル の状態和 であ り,q は,"i"方向の,各要素が "0'',"1'', "-1"のいずれかである位置ベ ク トルである.

"

i

"

方向 とは, y軸の負の方向を基準 として,時計 回 りに

(

i

*

45)度回転 した方向のことである (9). 3.1.2 処理の並列化

式 2

の処理を複数のセルについて並列 に行 うため,格子 空間を分割 して各

pE

3に処理 を割 り当てる.状態値は

1

ピット 状態和は

3

ビットの ビット帽で表せ るので,パ ッ ク ド･データで最 も要素の ビット幅が小 さく,最 も要素数 の多い

8×8

パ ック ド･デー タを用いる.この場合

,8

つ のデー タを並列処理で きるため,

1

0

に示す とお り格子空 間を

8

分割する. 元のセル空間 -牲 て悶 分割牡のセル空間 轡 ふ

ふ

ふ

ふ

ふ

血

ふ

ふ Fig.10.柄+'jillUの分割 (グレー部はPEliIJjdィ.=享が必柴な郎Jh) 3において.′1.7ク ト デー タ演算 を分散 メモ リ型Sn4Dマ シンと置 き 換えて説明 したが.本節においでも円滑 に説明を進めるために,パ ック ド･データ演算 を分散 メモ リ型SIMDマ シンとみな して話 を進める. ■I

l

∫

-

i

◆

-

i

J

5

1

I -

I

I

- l

;

P

.

S

;

I

i

!_{+十十十十+◆+}1:1il三1j.11i!il. ;2誇言2;2'f272ぎ2 Fig.ll. 状脚 Il井LT-の曲列化

s

o(

0,

0

)

s

l

(

0,

0

)

s

o(1

,

0)

s

l

(

1

,

0

)

s

o

(

m,

0

) s

l

(

m,

0

)

s

o(

0,

1

) s

l

(

0

,

1)

･

･

･ S

7

(

0

,

0)

( (a)

･

･

･

sT(

1

,

0)

-

S

7

(

m,

0

)

ー

(

b

)

8

7

(

0,

1

)

ー

(

C

)

s

o

(

m

,

n)

s

l

(

m,

n)

･

- S

T

(

m,

n)

ただ し,

m,

n:

各部分空間の最 も大 きい

x

,y座標 Fig.12.状 態値 の メモ リ上の配置 分割 した格子空間のセルの状態値は,それぞれの

PE

の ローカルメモ リに分散 して配置する.このとき,各 ローカ ルメモ リの状態値の並びを同 じにする.各

pE

のメモ リア クセス時のア ドレッシングは同時に行われるため,ある方 向の隣接するセルの状態値のア ドレスは,全てのローカル メモ リにおいて,同 じ方向の隣接するセルの状態値 を指 し 示すことになる. したがって,あるセルに着 日して状態和 を算出する処理 を行 うと,ほかの7つの部分空間上のセル の状態和 も同時に算出 される(ll). 3.1.3 データ並び替 え SIMDマシンにおけるローカルメモ リへの配置は,パッ ク ド･デー タ演算ではデータの並 び方 を工夫することに よって行 う.

1

2

は.8つの各部分空間を

s

D

,

Sl,･･･

,

S

7

とし て, S.･(a

:

,

y)

はそれぞれの,空間の左上のセルを原点 とす るローカル座標 x

,

y

上の状態値 を表す とした ときの,状 態値のメモ リ上の配置を示 している.図中の各行はパ ック ド･デー タである.各列が

PE

のローカルメモ リに相当 する. 3.1.4 境界処理 一般に

CA

の格子空間は, トーラス構造であることが多 い.そのため,図の ように格子空間を

1

セル分大 きくとっ て,境界のセルの状態値 を反対側の余分にとった空間にコ ピーする (13).こうすることで,境界セルに対 して特別 な処理 を行 う必要はな くなる. さらに, この操作 を行 うことで各部分空間は連続的な もの として扱 える･例 えば

,s

o

(

m,

o

)

の右隣の状態値は

s

l

(

0,

0

)

でな くてはいけないが

,1

2

の並びでは

s

o

(

m

,

0

)

の

琉球大学工学部紀要 第60号,2000年 Fig.13.境界のセルの処理 右隣の状態値 は so(0,1)である (図中の(b)

,

(

C

)

).

この問題 を解決するために境界の処理は,単純 なコピー 操作 だけではな くパ ック ド･デー タの シフ ト演算 も行 う. 各部分空間の状態億 を保存するメモ リ領域 は1セル分大 き くとってあるので,国中の

(

a)

の前 と

(

a

)

,

(

C

)

の間に

1

パ ッ ク ド･デー タ分の''空 き "がある.

(

可

のパ ック ド･デー タを

8

ビット左 に回転 して

(

叫 C

)

聞 (右境界)の空 きにコ ピー し,(b)のパ ック ド･デー タを

8

ビッ ト右 に回転 して (α)の前 (左境界)の空 きにコピーする. これ らの コピー操作 は.セル状態が更新す るたびに行 う必要がある. しか しなが ら,この操作は,2回の コピー と

1

回の 回転 のみ なので,全体 の処理 に占める割合は少 ない.

3.

2

次状態の決定 次 に,近傍セルの状態和 をもとに新 しい状態 を決定する 処理の並列化 を行 う.新 しい状態 を決軍する際の条件判断 に,

MMX

テクノロジの比較演算 を用いる.比戟演算 を用 いた場合 ,通常 のスカラ演算の条件分岐の ように

br

anc

h

命令 を伴 わないため,制御ハザー ド押

棒 9

5

1が発生 しな い.制御ハザー ドが発生 した場合4,

pe

nt

i

umI

I

I

プロセ ッ サは

1

0-1

5

c

l

oc

kc

yc

l

e

分ス トール (停止)する 【インテル

9

9

C

】

.

3.

2.

1

次状態の決定の定義 本論文で扱 う半合計的なCAでは,新 しい状態は,処理 対象 となるセル自身の状態値 とその近傍

8

セルの状態和の 組み合 わせ に よって決定す る. ライフゲームにおいでは, 以下のルールに従 って新 しい状態 を決定す る 【加藤

9

8

1

.

.生 きているセルは,近傍セルの状態和が2または3の 時のみ,生 き続 ける.それ以外 は,死ぬ. .死 んでいるセルは,近傍 セルの状態和が3の時のみ, 生 き返 る.それ以外 は,変化 しない. これは,次 の ように言 いか えるこ とがで きる. .近傍セルの状態和が

3

の時 は生 きる. .近傍セルの状態和が 2の時は変化 しない. .上記以外 の時は死ぬ. これ を,式で記述すると.

C

叶

1

-

校

(

S

L

=

3の とき)

(

St

=

2

の とき) (それ ら以外の とき) (3) 4pentium プロセッサには分岐予測機構があるため,必ず しも制御ハザー ドが号を生するとは限 らない.

1

2

3

ただ し,Cf :時刻 Lにおけるセルの状態値 St:近傍のセルの状態和

3.

2.

2

比較演算の適用 状態和は.

s

t

e

p.

1

の処理が終了 した時点で状態値のデー タ構造 とまった く同 じような並 びでパ ック化 されている.

S

亡,C

t

を時刻 iにおける状態和,状態値のパ ック ド･デー タとすると,比牧演算 による次状態の決定 は以下の棟 にな る (14). C2

=

C

O

mp

(

St

-

al

1

3S)

&a

ll

ls

(

4)

cl

=

C

Omp

(

St

=

a

l1

25)

&

Cf

(

5

)

C叶 1

=

Cl lc2

(

6

)

ただ し,"&'',

"

l

"

はビッ ト単位 の論理積,論理和 を表 し, cl,C2は

8×8

パ ック ド･データである.また

,a

ll

(

n)

Sは. 全ての要素が nである

8×8

パック ド ･デー タである. 式4は,式

3

の最初の条件 に対応する式である.

c

omp

は,条件 を満たす要素 をその要素の最大値 に設定す る.最 大値 は全ての ビッ トが1である値なので.必要な値 と論理 積 を取 ることで求る値 になる.この式では,比較演算の結 果 とa

l

l

ls

との論理積 を取 ることで必要 な値 を求める. 式 5は.式 3の 2番 目の条件 に対応す る.ここでは,求 めたい値 は

C

fなので,

CC

との論理積 をとる. 最後 に,式

6

で式

4

と式

5

の結果の論理和 を とる こと で処理が完了する.式

3

の各条件は,排他 的であるため式 4と式5は,少 な くとも一方の結果が 0になる.従 って, 論理和 をとることは.条件の成 り立つ方の式の結果 をとる ことに等 しい.

s

t

e

p.

1

と

s

t

e

p.

2

の並列化の よって

8

つのセルの更新処 理が同時に行 われるため,逐次演算 と比較 して8分の 1の 処理時間です む可能性がある. 1 1 1 1

& & & & I I l 1 a i A 1 1 1 ＼ 1

互

r / Fig.14.比較折井 を川いた次状腰の決起

4.

実験 4.1 実験環境 提案 した手法の有効性 を確認するために,評価用 に作成 したライフ ･ゲームシ ミュ レー タを用いて実験 をおこなっ た.実験 は,提案手法の各ステ ップを段階的 に適用 した

3

124 赤嶺 ･遠藤 ･山田 :NNXテ ク ノロ ジに よるCAシ ミュ レー タの rF.bj速化 つのバ ージ ョンとスカラ演算バ ージ ョンの比較 を行 った. また,処理時間 を厳密 に計測するため に,時 間 をプロセ ッ サのclockcycle数 よって計測 した. さ らに, ビデ オメモ リへの転 送処理 に よるオーバヘ ッ ドを除去するため,CA の更新部分 のclockcycle数 のみ を計測 した. 実験環境 はWindows98だが, 同

O

Sは.マ ルチ タス ク

os

なので タス ク ･ス イ ッチ ングに よる結 果のば らつ きが でる.そのため,セル状態 の更新処理 を100回お こな うの に必要なclockcycleを計測 して,その平均値 を とった.実 験 に用 いた プ ロセ ッサ は,MMXテ クノロジPenLiumプ ロセ ッサ とPentiumIIIプ ロセ ッサであ る.clockcycleの 計測 には,MMXテクノロジPentiumプロセ ッサ のTime SLampCounterを用 いた 【小溝 97】. 実験 に用い た ライフ ･ゲームの格子 空 間は,256×256 である.この大 きさは,実験用 の システムにおいて,状態 値の全 デー タがプ ロセ ッサ (CPU)の

1

次 キ ャッシュには 収 まらないが

,2

次 キ ャッシュには入 りきる大 きさであ る. デー タの大 きさが

2

次 キ ャッシュのサ イズ を超 える と,メ モ リアクセス速度の ボ トルネックが急激 に増大5し,実験 結果が システムのバス速度 に依存 して しまうので.前述 し たサ イズが適 当であ る.実験 は,以下の ようなシ ミュ レー タをそれぞれ作成 ,比較 した. 1.評価基準 となる シ ミュ レー タ

(

C

言語 に よるス カラ 演算バー ジ ョン) 2.step.1を適用 した もの (状態 和 の算 出のみ に提 琴手 法 を適用) 3.step.1に加 えてstep.2を適用 した もの (状 態和 の算 出お よび次状態 の決定 に提 案手法 を適用) C言語によるスカラ演算バージ ョンは,VisualC++バー ジ ョン6.0の コ ンパ イラでPentiumプ ロセ ッサ を対象 と した速度 に対 す る最適化 を行 うオプ シ ョンをつ けて コン パ イル した. この オプシ ョンをつ けた場合, コンパ イラは MMXテ クノロジ を用い ないで,superSCalar実行 のため のpairingな どの,速度 を高速 にす るための最適化 を行 う.

4.

2

実験結果 前 述 した,4種類 の シ ミュ レー タをMMXテ クノロジ Pentiumプロセ ッサ.PentiumIIIプロセ ッサの各 プロセ ッ サ上で動 か して, その実行clockcycleを測定 し,それぞ れの値 を

C

言語 に よるスカラ演算バ ー ジ ョンの もの と比 較 を行 った.実験結果 をグラフに示す (15). 実験結果か ら,MMXテ クノロジPentiumプ ロセ ッサ 上で走 らせ た場合,

C

言語 に よるスカラ演算バ ージ ョンを 基準 と して,状態和 の算出のみ に提 案手法 を適用 した もの が約 3倍,状態和の算出お よび次状態の決定 に碇 案手法 を 適用 した ものが約5.5倍 の速度で処理が終了す る ことが わ かった. また,PentiumIIIプロセ ッサ上 で走 らせ た場 合 は,それぞれ,約

3

倍 ,約7.5倍 の速度 で処理 で きるこ と がわか った. 5.考察 5-枚的 なPCアー キテ クチ ャの システ ムで は.2次 キ ャッシュの ミス ヒッ ト時のペ ナルテ ィは.数十か ら百敢 clockc.yc)Cであ る. ( 触 喋 小 F F Y 夜 ) 当 超 せ 2 1 ｣ 6 4 2 団pentiumtII 田MMXPentium Fig.15. 実験柿米 MMXテ クノロジのパ ック ド･デー タ演算は

,8×8

パ ッ ク ド･デー タを用いた場合 ,最大 で

8

倍 の高速化 の可能性 がある. しか しなが ら,実際 にはループ制御やその他のス カラ演算が必 要であ るため理想値 には連 しない. 提案手法では,この ような並列化 を阻害する要因をデー タ構造 とコーデ ィングの工夫 に よって排 除 してい る.揺 案手法のstep.1で は, デー タ構造 の最適化 に よ り余分 な デー タ移動 を低 減す る こ とで,演 算 の並列度 を高めてい る.step.2では,比較演算 を用い ることで制御 ハザー ドを 無 くし,結果 と して並列度 が上が ってい る. 実験結果 は,提案手法が より複雑 なCAモデルに も適用 可能であることを示 している.例 えば,step.1のみ を適用 した場 合,評価 基準 であ る

C

言語バ ー ジ ョンに比べ て明 らかに高速である. これは,状態和 の算出 にはパ ック ド･ デー タ演算が適用で きるが,次状態の算出には適用が難 し い場合,つ ま り,次状態の決定のルールが複雑す ぎて並列 化で きない場合 な どで も,ある程度 は効果があ ることを示 している.

6.

あわ りに 本論文では,MMXテ クノロジのパ ック ド･デー タ演乱 比較演 算 に よる並 列 演 算 に よ り, ロー コス トで高速 なセ ルラ ･オー トマ トン ･シ ミュレー タを作成す る手法 を提案 した. 提 案 した手法 を用 いて ライフゲ ームの シ ミュ レー タを 作成 し,ス カラ演算 に よる もの との比軟 を行 った ところ. 良好 な結果 を得 た. 提 案手法 は,理論 的 には ライフゲー ムに限 らず一般 的 なCAに対 して適用可能 であ る.今 後,様 々なCAモ デ ルに対 して提案手法 を適用 し,その効果 を検証す る必要が あ る.

P3eck] Beck,M･‥TheCellularAutomataSimulationSys -tem:

琉球 大学工学 部紀 要 第60号,2000年

lBcck94] Beck,M.andCastelJano

S

,A.:VectorProcessing onScalarArchitecture(1994)･

lIntOO】 IntelCeLeronProcessor-Datasheet.IntelCeLeron Processorup to 533MH21(OrderNllmber:243658 -010)(2000).

【Ladd951 Ladd,S.氏.:C十十シ ミュ レーションズ&セルラ ･オー トマ トンE]本給版,株式 会社ディー ･アー ト(1995),朝 沼 美雪 :釈.

lMargolus931 Margo)us,N.: CAM-8:a computer architectul･C

basedoncelluarautomata,Physiscsorcomputa -tionseminar(1993)A

lPatterson96】Patterson.D.A.and Hennessy,J.L.:Computer Arch2'tecttLT･e ノI Qilanlitatt't･c jlppTl0aCh,Morgan KaufmannPublishers,Inc･,secondedition(1996)･

【インテル99al インテル株式会社 :インテル ･アーキテ クチ ャソフ ト ウェア ･ディベロッパーズ ･マニュアル下巻 :システム ･ プログラ ミング ･ガイ ド(資料番号2431921日 1999)･ 【インテル 99b】 インテル株式 会社 :インテル ･アーキテ クチ ャソフ ト ウェア ･デ ィベ ロ ッパ ーズ ･マニュアル上巻 :基本 アー キテ クチ ャ(資料番号243190J)(1999)･ [インテル99C] インテ ル株式会社 :インテル ･アーキテクチ ャ殺適化 (資料番号730795J-001)(1999). 【加藤98】 加藤,光成,築山 :セルオー トマ トン軌 森北出版(1998). [小食 97】 小管 英 一:MMXテ クノロジ優遇化 テクニ ック,アス 【中将 951 【天野89】 【平林98】 キー出版(1997). 中滞喜 三郎 :新井機 アーキテ クチャと柵成方式.朝倉沓 店 (1995). 天野 ,高橋,富 田,渡辺,渡辺 :並列処理機構,丸尊株式 会社 (1989). 平林,石塚 ,横 臥 伊藤,小前 ,渦度 ,竹岡,安相 通晃 : セルラオー トマ トン ･シ ミュレータ用並列 コンパ イラの 開発 ,情報処理振 興事業協 会 ｢創造的 ソフ トウェア育 成事 業｣最終成果発表会(1998).

1

2

5