Title セルオートマトン・モデル記述言語DORA及び並列化コンパイラ
Author(s) 赤嶺, 有平; 遠藤, 聡志; 山田, 孝治
Citation 沖縄大学マルチメディア教育研究センター紀要 = TheBulletin of Multimedia Education and Research Center, University of Okinawa(5): 1-13
Issue Date 2005-03-31
URL http://hdl.handle.net/20.500.12001/6401
セルオートマトン・モデル記述言語ＤＯＲＡ及び
並列化コンパイラ
赤嶺有平↑遠藤聡志↑山田孝治↑↑琉球大学工学部
あらまし本論文では，筆者らが開発したセルオートマトン・シミュレータ用並列化コンパイラの仕様及びその性 能評価について述べる．セルオートマトン（○Ａ）法は，局所的な相互作用を定義することで複雑現象を不規則性も含 めて再現することができるため，流体の乱流，交通渋滞，自然災害など従来の微分方程式を基礎とするモデルでは解 析の難しかった現象も解明できるとされている．ＣＡ法は，本質的に高いデータ並列性をもっており，ＳＩＭＤ(Single lnstructionstream,MultipleDatastream)による並列処理に適している．一方，メディア系処理の高速化に対応す るため拡張ＳＩＭＤ命令を搭載したプロセッサが増加しているがｊ利用にはデータ並列型言語を利用するかアセンブリ 言語で直接記述することが多い．多くの現象に対しＣＡ法を適用するためには，ユーザに並列化やプログラミングの 知識を要求しない環境が望まれる．本研究では，拡張ＳＩＭＤ命令を用いて高速なＣＡシミュレータを生成するコンパ イラの開発を行った．本コンパイラを用いることで，ユーザは並列化を意識することなく，高速なＣＡシミュレーショ ンシステムを利用することが可能となる．また，本コンパイラを用いてＯＡシミュレータを作成しＣ言語や他のＣＡ シミュレータ生成システムを用いて作成したものと比較実験を行ったところ，本コンパイラの出力するシミュレータ が高速であることが示されたTheDORALanguagefbrModelingCellularAutolnataandthe
ParallelizingCompiler
YuheiAKAMINE↑,SatoshiENDOt,andKojiYAMADA↑ lFacultyofEngineering,UniversityoftheRyukyus AbstractThispaperdescribesthespecificationsoftheparallelizingcompilerwehavedevelopedfbrsimu-latingcellularautomataandtheperfbrmanceevaluationtest､Acellularautomaton(CA)ismethodtosimulate complexphenomenamcludingitsirregularitywithadefinitionofsimplelocalinteractions、CAisideallysuited fbrparallelprocessing，andhavebeencharacterizedaseasytoparallelizeusingextendedSIMDinstruction、 ＳＩＭＤmeans“singleinstructionstream，multipleinstructionstream.，，Ｏｎｏｎｅｈａｎｄ，extendedSIMDinstruc-tionscanbeusednowbymanyprocessors・However，weoftenuseadataparalleltypelanguagefbrusing SIMDinstructions，orprograminanassemblylanguagedirectlybThereisdemandfbrtheenvironmentwhere theknowledgeofparallelizingorprogrammingisnotrequiredofauser・Wehavedevelopedthecompilerthat generateshighspeedCAsimulatorusingextendedSIMDinstructionｓｉｎｔｈｉｓｓｔｕｄｙ・Usingthiscompiler，the usercanuseahigh-speedCAsimulationsystemwithoutconsiderationofparallelization．、Theresultofthe perfOrmanceevaluationtestshowsthattheCAsimulatorgeneratedbyourcompilerisfasterthanthesimulators madebytheothermethod． －１－Ｌはじめに セルオートマトン（CA）法はプ局所的な相互作用（近傍則と呼ばれる）を定義する
ことで複雑現象を不規則性も含めて表現できるため，流体の乱流，交通渋滞，自然災
害など従来の微分方程式を基礎とするモデルでは解析の難しかった現象も解明できる
とされていろ[']．例えば，水の流れは，ナピエ・ストークス方程式などの微分方程式で表すことができるが，川の流れのように幅が変化したり様々な障害物によって複雑
に流れが変化するような現象を単純な数式で表すことは困難である．それに対してＯＡ
法では，流体粒子間で質量と運動量を保存する衝突を繰り返させることにより，ナピ
エ・ストークス方程式を解いた場合と同等な結果を得ることができる[2Ｌ
ＣＡ法は，本質的に高いデータ並列性をもっており，単一の演算命令で複数のデー
タを並列処理するＳＩＭＤ(SingleInstructionstream,MultipleDatastream)[3]による並列
化に適している．そのためＳＩＭＤアーキテクチャにより構成されたＯＡ専用計算機[4］
やcellangと呼ばれる言語によって記述されたＣＡ遷移規則をもとにソフトウエア的に
ＳＩＭＤ並列化したシミュレータを生成するツールが開発されている[５１
－方，メディア系処理の高速化に対応するため拡張ＳＩＭＤ命令に対応したプロセッサが増加しており，多くの対応アプリケーションが開発されている．拡張ＳＩＭＤ命令
は，機械語命令であるため利用するには拡張ＳＩＭＤ命令を利用した最適化を行うコン
パイラを用いるかアセンブリ言語を直接記述することが多い．拡張ＳＩＭＤ命令は，命
令セットが非対称であるなどの制約が多く性能を引き出すには高度な知識が必要であ
る．特にＣＡシミュレーションを並列化する際には，データのアラインメントの問題や
データに依存する分岐の問題などがあり効率的なコードを記述することは容易ではな
い．ＳWARC[6]や1ＤＣ[7]と呼ばれるＳＩＭＤ命令を生成する拡張Ｃコンパイラが開発さ
れているが，ＳＩＭＤアーキテクチャを意識したコードを記述する必要があるためユー
ザに並列化の知識が要求されろ．多くの現象に対しＣＡ法を適用するためには，ユー
ザに並列化やプログラミングの知識を要求しない環境が望まれる．
本研究の目的は，ユーザが並列化を意識することなく自動的に拡張ＳＩＭＤ命令を用
いて高速な○Ａシミュレータを生成するシステムの構築である．筆者らはこれまでに，
ＣＡ近傍則の設計やシミュレーションを効率的に行うシステムの開発を行ってきた[8]・
開発システムは，対話‘性を重視したインタプリタ型シミュレータと高速'性を重視した
コンパイラ型シミュレータを状況に応じて選択可能とすることで，近傍則の設計効率 と○Ａシミュレーションの実行効率を両立することを目標としている．今回開発したコンパイラ(DORAC)は，同システムの一部として組み込むことを想定しているため，
近傍則記述言語として，同システムで採用しているＤＯＲＡ言語を用いる．また，これ
までに筆者らが提案した，ＯＡシミュレーションをＭＭＸ命令セット(ＭＭＸ)を用いて
高速化する手法を一般化し，より並列度の高いSSE２（StreamingSIMDExtension2)[9］
命令セットを用いたコードを生成するコンパイラを作成した本論文では，２章で対
象とするＯＡ法とその近傍則を定義する記述言語の仕様について述べ，３章でDORAC
の構成および最適化について説明する．４章で性能評価実験の結果を示し，５章で他の
並列化システムとの関連について考察を行う〆 －２－型 表１ＤＯＲＡ言語のオブジェクトの種類と型
２．ＣＡ法と近傍則記述言語ＤＯＲＡ
２．１対象とするＣＡモデル ＤＯＲＡ言語が対象とするＯＡモデルは，以下のように定義されろ． ．ｎ次元空間に規則的に配置された格子を考える、時刻ｔ＝0,1,2,…において定義される各格子点〆（セルと呼ばれる）の整数値
集合（状態と呼ばれる）を⑨(穴ｔ)＝{の,(穴t),の2(穴t),…,①m(穴t)｝とする
・時刻ｔ＋１の状態⑪(穴t＋1)は，近傍則Ｒ＝{R1,Ｒ2,…,Ｒｍ｝によって以下のよ
うに決定される ①jにt＋1)＝Ｅｊ(⑪(穴t),⑪(〆＋5,,t)，⑪「＋52,t),…,⑪(〆＋Jq,t)）（１）
〆＋品は，セルデの近傍セルを表す．
２２言語仕様ＤＯＲＡ言語は，○Ａの近傍則を簡潔に記述することを目的として設計されている．言
語仕様については，ｃ言語を参考に構文・演算子を設計し，理解しやすいよう考慮し
た．また，記述においてユーザはデータ並列性について考慮する必要はない．
ＤＯＲＡ言語は，１つのソースファイルに１つの近傍則関数（前節，式l）を定義する．
シミュレータは，全てのセルについてソースコードに記述されたプログラムを実行す るように実装される．処理するセルの)|頂序は，実装により自由である．ソースコードは，基本的に，時刻ｔにおける着目セル及びその近傍セルの状態を記'億すろ変数（状
態変数）の値を元に時刻t＋１における対象セルの状態変数の値を決定するように記述
する．ＤＯＲＡ言語で利用できる演算子を図１に示す．優先度はＣ言語と同じである．角カッ
コ（[]）はセル指定子と呼び）近傍セルの状態や近傍セルそのものを参照するのに用いる．参照する近傍セルの位置は，［Ｍ]のように指定する．ただし，座標Ｍは定数
でなければならない．ＤＯＲＡ言語では，英数字で表される識別子つきオブジェクトとして，５種類のオブ
ジェクトを扱う．オブジェクトの型は，宣言子を用いた宣言時および他のオブジェクトの代入時に決定する．ＤＯＲＡ言語のオブジェクトの種類を以下に示す．
未宣言の識別子つきオブジェクトに対する代入式において，右辺値が整数型の場合，
左辺のオブジェクトは一時変数となる．右辺値がセル型の場合，すなわち右辺値がセ
－３－ オブジェクトの種類 型 定数 〆 パラメトリック定数 一時変数 状態変数 セルエイリアス 整数型 整数型 整数型 整数型 セル型ル指定子およびセルエイリアスの時は，左辺オブジェクトはセルエイリアスとなる． consｔキーワードを用いて宣言を行うと「定数」となり初期化以外の代入は禁止さ れる．para,､キーワードは，ユーザがシミュレーション時にGUI等によって動的に調 整可能なパラメトリック定数を宣言する．ＯＡモデルのパラメータ調整に利用される． 一時変数は，値が代入されてからコードの終端までの期間，整数値が保持･変更でき る．一方，状態変数は，全てのセルに対して記`億域が割り当てられ，シミュレーショ ンの終了までの期間，整数値を保持・変更できる．これは，ＣＡモデルにおける状態
を表現することを想定した設計である．状態変数に対して代入することで，対象セル
の時刻ｔ＋１における状態変数ｓの値が決定する． セルエイリアスは，セルを表現するオブジェクトである．セル指定子で指定された セルヘのエイワアスを保持する．例えば， eastceU＝［1,0兆では，eastcellは，２次元空間において着目セルを中心に座標(1,0)の位置にあるセ
ルヘのエイリアスとなる． 状態の参照は，セル型オブジェクト（セル指定子およびセルエイワアス）と状態変 数の組み合わせで記述する．例えば， states；／/ｓを状態変数として宣言 eastｓ＝［１，０］．ｓ；では，座標(1,0)のセルの時刻ｔにおける状態変数ｓの値が一時変数eastsに代入され
る．ここで，“state，，キーワードは，状態変数を宣言するキーワードである．状態変数 は，整数型なので，eastsは一時変数となる．同様にセルエイリアスを用いても記述できる．例えば，以下の通り．states;eastcell＝[1,0];easts＝eastcelLsiセル型オブジェ
クトを整数型オブジェクトヘ代入すると，セル型オブジェクトが状態変数に暗黙に変換される．変換される状態変数は，先頭に宣言されたものである．例えば，
ｓｔａｔｅｓｌ； ｓｔａｔｅｓ２； ｃ＝［0,1]；／/ｃは位置[0,1］のセルエイリアス ｖ＝Ｏ；／／ｖは一時変数 ｖ＝ｃ；／／ｄ＝ｃ・ｓｌと同じ ｓ２＝［1,0]；／／ｓ２＝［1,0Ｊｓｌと同じ となる． 全セルにおいて有効なグローバル変数は，書き込みの競合が発生するため定義して いない．例外的に，シミュレーション開始時をＯとする時刻tの値をtimeキーワード を用いて全セルから参照できる．本システムのＯＡシミュレータは，可視化する手法の制約から，３次元以下のモデル
のみ対応しているが，ＤＯＲＡ言語の言語仕様としては，任意の次元のモデルの記述を 許容していろ． ＤＯＲＡ言語の予約語を図２に示す．dimensionは空間次元を指定し，when，otherwiseは条件付きの代入文を指定するためのキーワードである．他に組み込み変数として，
-４－［］＋ ＊／％＆ &＆｜’ 図１ＤＯＲＡ言語の演算子 iｆｅｌｓｅ ｆｏｒ ｃｏｎｓｔｓｔａｔｅｗｈｅｎ dimensionparam otherwise 図２ＤＯＲＡ言語の予約語 ‐→whi1e（ｅ”）ｓｔｍｔ －→ｉｒ（ｅｚｐｒ）stmt -→ｉｆ（ｅｍｐｒ）ｓｔｍｔｅｌｓｅｓｔｍｔ →Ｕａｒｊａｂｌｅ＝ｅｚｐｒ； -→｛stmtstmt…｝ ｔｔｔｔｔ ｍｍｍｍｍ ｔｔｔｔｔ ｓ８ｓ８ｓ Ｊ ｔ ｎ ｑ ｔ Ｓ
ｍ〃〃〃〃
仁ｚＺｚｚ ｍｅｅｅｅ ｍ＋｜＊ノ ８ ，〃〃〃〃 、Ｚｚｚｚ Ⅲｅｅｅｅ →→→→→ ７７７町〃 叩叩叩、ｍ ｅｅｅｅｅ 図３ＤＯＲＡ言語の文法規則の一部（演算子 の結合優先度はＣ言語に準ずる） 擬似乱数を発生するｒand変数，シミュレーション開始時からの時間ステップを返す time変数がある．ＤＯＲＡ言語の文法規則の一部を図３に示す． 時亥ﾘｵ＋１における状態は，処理時点で未定であるので代入のみが許され，時刻ｔに おける状態は，処理時点においては過去の値であるので参照のみが許される．また， 時刻ｔおよびt＋１における近傍の状態を変更するようなコードは記述できない．これ により，ＯＡ定義に違反しないことと，拡張ＳＩＭＤ命令で並列化可能であることが保障 される．ＤＯＲＡ言語によるライフゲームのＣＡ遷移規則の記述を図４に示す． 時刻ｔ＝ｏにおける各セルの状態は，初期状態ファイルに記述ざれシミュレーション 時に読み込まれる．３．コンパイラの仕様
DORACは，ＤＯＲＡ言語によるＯＡモデルの仕様記述を元に拡張ＳＩＭＤ命令を用いて 並列化したＯＡシミュレータを生成する．本章では，拡張ＳＩＭＤ命令の概要とDORAC の行う操作及び最適化について述べる．DORACは，構文解析器，ｉｆ変換器，最適化器，コード生成器で構成されている(図
5)．構文解析器では，構文解析を行い構文木を生成する．本研究では，構文解析器の
生成にyacc[10]を用いた‘構文解析器は，インタプリタ版シミュレータと共通であり，
－５－/／ｓを状態変数として宣言 ｓｔａｔｅｓ； //近傍の８つの状態を合計する 、＝［-1,-1]＋[０，－１]＋[１，－１]＋[－１，０］ ＋[１，０]＋[－１，１]＋[０，１]＋[１，１］； //sum=３もしくはsum=2且つ着目セルの状態が１の時，次の状態は１，それ以外は０ ｓ＝１：ｗｈｅｎ（n－3） ［0,0］：when（n－2） ０：ｏｔｈｅｒｗｉｓｅ； ｝ 図４ＤＯＲＡ言語によるライフゲームのＣＡ 遷移規則の記述 、 ＣＡ仕儀定3ＦのＯﾉ卸
篭|腰
図６拡張ＳＩＭＤ命令のパツクド・データ演 算の例 コート生成■ 図５ＤＯＲＡＣのパス構成インタプリタは，構文木を直接解釈し実行する[8]・
ＳＩＭＤ命令による並列化の際は，データに依存した分岐を直接コード化できないこ
とが問題となる．そのため，ｉｆ変換器で条件分岐を比較演算と論理演算からなる式に
if変換[11]する．比較演算とは，比較結果に応じたビットマスクを生成する演算であ
る．最適化器は，変換によって生じた冗長部分を検出しより最適な式に変換する．変
換後の構文木は，すべてＳＩＭＤ命令によりコード化可能である．コード生成器は，構
文木を基にマイクロソフト社製アセンブラ（ＭASM）互換のアセンブリコードを出力
する．最終的にユーザインターフェースを実装したライブラリとリンクざれexeファ イルが出力される． ３１拡張ＳＩＭＤ命令拡張ＳＩＭＤ命令は，マルチメディアの処理を高速化するために導入された技術で，１
つの命令が複数のデータを並列に処理する機構を用いることで演算を並列化する．拡
張ＳＩＭＤ命令は，並列度の小さいベクトル演算命令と考えることもでき，ベクトル演
算命令と比較すると実行コストが小さい[12]・拡張ＳＩＭＤ命令では，ピット幅の大きな
1つのレジスタ（以下パックＦ・データレジスタと記す）に複数のピット幅の小さい
データを並べてロードし，それぞれの小データ対して同じ演算を独立に実行すること
でＳＩＭＤ演算を実現しており，そのような演算をパツクド・デーダ演算と呼ぶ（図6)．
したがって，並列実行するデータ群は，パックド・データレジスタに並べて配置しておく必要がある．本論文では,配置された小データをサブオペランドと呼ぶ．
－６－(蕊Ni霧蕊蕊霧jl1露蕊馨鱸鮒鱸１
ijil1lillilliiilliilil霧illlilllll
鍼?/N1i1i鑿､！ 鰯１７鰯)1J/蝋([)鰯L■鰯、｡②｢||Ⅲ|｢llliW1
図７７０＝８の抽象ＳＩＭＤマシンとローカル メモリ 、口熱１コ蕊爪丁騨LL仔鰯、 図８ＣＡ空間の分割 領域） ｄＳＷＩ鰯鍬鍵 (グレー部はシャドウ 一般に，プロセッサはそのパックド・データレジスタのデータ幅がnバイトの時， パックド・データレジスタとメモリ間のｎバイト境界をまたぐアクセスは，大きなペ ナルティ（プロセッサ・ストール）や例外の発生，期待しないメモリアクセスなどを伴う[9]ため，メモリアクセスの際は整序（アラインメント）を行う．これらの仕様を
図７のような抽象SIMDマシンとして考えると，メモリ空間をｎ個（データ幅が8-bitの時）に分割し，それぞれを各プロセッサエレメント(PE)のローカルメモリとみなす
ことが出来る.メモリアドレスは，全てのＰＥに同時に指定されアクセスも同時に起 こる．パックド・データ演算は，ＰＥのローカル演算であり，パックＦ・データに対す るシフト演算は，ＰＥ間の通信である．ＰＥのリモートメモリヘのアクセスには，余分 なコストがかかる．従って，演算に必要なデータをローカルメモリに配置することが 処理を効率化する． DORACは，ＯＡ空間を部分空間に分割し各ＰＥのローカルメモリに配置する．ＯＡにおいては，近傍セルの状態を参照して次の状態を決定するが．サイクリック分割['3］
では，隣接するセルの状態が異なるＰＥのローカルメモワに配置されるためＰＥ間通信 が多く必要となる．そのためDORACでは，図８のように○Ａ空間をｘ軸方向にブロッ ク分割し各ローカルメモリに配置する．また，各部分空間のエッジにシャドウ領域を 用意し隣接エッジの状態をコピーする．ＤＯＲＡ言語では，近傍の範囲は静的に決定で きるため必要なシャドウ幅もコンパイラが決定できる．本システムにおいてＣＡ空間 はトーラス空間として扱われるため，ＣＡ空間全体のエッジの状態は，反対側のシャド ウ領域にコピーされる．分割した各部分空間のセル状態は，それぞれのＰＥのローカ ルメモリに分散して配置する．このとき，各ローカルメモリの状態の並びを同じにす る．各ＰＥのメモリアクセス時のアドレスは（ＳＩＭＤマシンなので）同一となるため， ある方向の隣接するセルの状態のアドレスは，全てのローカルメモリにおいて，同じ 方向の隣接するセルの状態を指し示すことになる．したがって，あるセルに着目して 近傍の状態の合計を算出する処理を行うと，ほかの部分空間上の状態の合計も同時に算出される(図9)．実際のメモリ上の配置は図10のようになる．
Ｍ演算のＳＩＭＤ並列化 コード生成器は，各部分空間上のセルの状態遷移処理を，それぞれのＰＥに割り当て -７－分■した拍子室、 釣助勘ＳｂＳｂ勘Ｓｂ・帥 〆－－－ﾉー ■■■■■■■■■■■■■■■■■■■■ ■■■■■■■■■■■＝■■■■■■■■■■■■ ■■■■■■■■■■■■■■■■ ［ⅡFFF］［】nF］［Ｉｒｌｎ】］】【H１uＤｆｕＩ１Ｌ【】FIE］ 、ｐＥ「 ｍＪｒ］ｈ｣」、ｕＪ□rI[，ｈ」】」、】r]「渤【][〕ｂ｣【
〃-=胆■■■
■■ －－ヨ■■■■ １１１ ＋＋＋＋＋＋＋＋ Ｅ２ＥＥ向1百1可豆1三1苞１ １１１１：ｉｉｉ ＄８８２！；！； 図９近傍状態の合計算出の並列化 メモリに■■された状■伍 図１０状態のメモリ上の配置るようにパックド・データ演算命令を生成する．ＤＯＲＡ言語においては，近傍セルの位
置はコンパイル時に静的に決定する．また，IA32プロセッサは，オペランドにメモリ
アドレスを指定できるためメモリからの値のロードと演算をｌ命令で行える．DORAC
は，着目するセルの状態を記'億したメモリアドレスをあるレジスタに記録しておき，
近傍セルヘのアクセスは，そのレジスタとオフセットを組み合わせたアドレッシングで表現することで状態の参照と演算をｌ命令でコード化する．
SSE2のパツクド・データ演算命令には，ラップアラウンド型（オーバーフローは無視される）と飽和型（オーバーフローの場合は最大値，アングーフローは最小値とな
る）があるが，DORACではデータ幅も含めてコンパイル時にユーザが指定する．し
たがって，ユーザは値の溢れが起きないようにデータ幅を検討する必要がある．必要
なデータ幅の特定が難しい場合は，インタプリタ版シミュレータの状態の最大，最小
値を記録する機能が利用できろ．ＳＩＭＤ演算における問題の一つにデータに依存して分岐する処理（if文など）が難し
いことが挙げられる．一般に，ＳＩＭＤ演算ではif文は条件付き移動命令に変換するこ
とで処理する(if変換と呼ばれる[11]）．SSE2では，条件付移動命令は用意されていな
いためサブオペランドの比較結果によってビットマスクを生成するＳＩＭＤ比較命令と
マスク演算を利用して条件付き移動命令をエミュレートする[9]・
ＳＩＭＤ比較演算は，サブオペランド間で比較を行い条件を満たすサブオペランドのピットを全て１（8-bitなら255)，他のサブオペランドをＯとする演算である．条件に
は,「等しい」「より大きい」の何れかが指定できる．
３．３ｉｆ変換ｉｆ変換は，ｉｆ文内の代入文を条件付代入文に変換することで分岐命令を除去する．SSE２
を用いる場合は，比較演算と論理演算に置き換えて処理する．例えば，ｃ言語で記述
された ｉｆ（ｘ＝＝ｙ） ａ＝２； ｅｌｓｅ ａ＝３； は， ｍ＝ｍask(ｘ－ｙ)； ａ＝、＆２１～ｍ＆３；と置き換えることができる[6]．これを「変換１」とする．ここで，maslK（条件）は，
以下のように定義される． －８－ ￣左一二コ＃
鰯 ｜ﾛ 千FＴ 鰯＃
鰯沖
鰯沖
鰯神
鰯 ----_￣ －～ ’－１ ＝ １ １ １ １ １ 111 ｜ﾛ 千FＴ 鰯禅
鶴 ￣ ８ ４ 、Ｌ 、 」 × 二 ￣■〆 ￣ ，房▲Ｚ 1111 １ １． 「 2８一 ￣４ 二 戸 Ｕ１ 2１しり‘21212▲ １ － ノ ２ ￣￣３ ４二〆 ' ＝ ＝ １』〆 ８’ ４一typedefunsignedcharDATATYPE； DATATYPEmask(boolcond） ｛ returncond？（DATATYPE)（-1）：Ｏ； ）
DATATYPEは，扱うデータの型である．上記の記述では符号なしバイトで宣言している
が，実際には，符号なしバイト，ワード，ダブルワードの何れかである．（DATATYPE)(-1）は，全てのビットが１となる値である．ｉｆ文がネストしている場合は，代入文に到達
するまでに評価される条件から生成される複数のビットマスクの論理積をマスクとし
て用いることで処理できろ． 以下のif文を例にDORACが行う変換に説明する． １：ｉｆ(ｂ〈Ｏ）｛’ ２：ａ＝ａ＋１； ３： ｉｆ(ａ〈Ｏ） ４： ｂ＝２； ５：ｅｌｓｅ ６： ｂ＝１； ７：）elseｉｆ(ａ〉Ｏ)｛ ８：ａ＝２； ９：）else（ １０： ｂ＝３； １１：ａ＝ｂ； １２：） 4行目の代入は，１，３行目の条件を満たす時に行われるのでピツトマスクは， 、＝ｍask(ｂ〈０）＆、ask(ａ〈Ｏ）； となる．else部は，条件の否定から生成したピットマスクを用いろ．したがって，上 記のコードは以下のようにif変換できる． 、＝、ask(ｂ＜Ｏ）； -,11＝、ask(ｂ〉＝Ｏ）； ａ＝ａ+１＆ｍｌｌａ＆－ｍ； 、３＝ｍｌ８ｔｍａｓｋ(ａ〈Ｏ）； －，３＝ｍｌ８Ｚｍａｓｋ(ａ〉＝Ｏ）； ｂ＝２＆ｍ３１ｂ＆～､３； ｂ＝１＆－，３１ｂ＆～－，３； 、７＝＿ｍｌ８Ｚｍａｓｋ(ａ〉Ｏ）； －，７＝-ｍｌ８Ｚｍａｓｋ(ａ＜＝Ｏ）； ａ＝２＆ｍ７１ａ８Ｚ－ｍ７； ｂ＝３＆－，７１ｂ＆～－，７； ａ＝ｂ＆＿ｍ７１ａ＆￣-,7；ピットマスク、,-ｍ〃は，上記コードのｎ行目のthen部，else部の条件に対応する．
m３，，７は，２行目の変数ａの演算結果に依存するので，変換１のようにelse部の代入文
をまとめて処理することはできない． －９－2ｍｍ，［e8i＋(-304)］〃1ｏａｄｓ上ate mnn2，［esi+(-288)】ノノｌｏａｄｓｔａｔｅａｎｄａｄｄ 】ｍｍ２，［esi+(-272)］〃1ｏａｄｓｔａｔｅａｎｄａｄｄ ｡､､２，［esi+(-16)］ﾉﾉﾕｏａｄｓ上ａｔｅａｎｄａｄｄ ｍｎ２，【esi+16］〃ｌｏａｄｓｔａｔｅａｎｄａｄｄ 麺､２，【esi+272］〃loadBta上ｅａｎｄａｄｄ 極､２，にＢｉ+2881ノノloadstateandadd ｡ｍｍ２，【esi+304］〃ｌｏａｄｓｔａｔｅａｎｄａｄｄ 】匝匡､４，，，２／／ａＳＢｉｍＢｕｍ ｡□回２，．，，５/／Ｂｕｍ＝２ ｍｍ２，【esi+0】ノノ（ｓｕｍ－２）＆［0,0】 ｡区、３，，，４〃ｓｕｎ ｡画回３，２，，５〃Ｂｕｍ＝＝３ ]画､３，２，，７〃（Sun＝＝３）＆１ ｍｍ，〕ｍｍ３ノノ（Sum-2)&【0'011(Sum-3)と１ 【edi+0】，2,,2／／ａｓsigns上a上ｅ mvdqa paddb paddb paddb paddb paddb paddb paddb moVd回a pmpeqb Pand mcvdqa pc亜Peqb pand pOr movdqa CdeEineST(。x,ｏｙ）（（(BYTE★)psrc）［。y*SｴZEOFX+ox]） for(y=O；ｙ＜SｴZEOFX）ｙ++）（ ２ｏｚ(x=O；ｘ＜SｴZEOFX；ｘ+＋）（ ｉｎｔｓｕｍ＝ＳＴｕ,Ｏ)＋ＳＴ(-1,0)＋ＳＴ(０，１１＋ＳＴ(０，－１） ＋ＳＴ(１，１)＋S⑩(１，－１)十sＴ(-1,１)＋ＳＴ(－ユ,－ユル 正(sｕｍ－３１１（sum＝＝２“ＳＴ(0,0）＝＝１） ＊（（BYTE★)pdst+＋）＝1； ｅ１ｓｅ ＊（（BYTE＊)pdst+＋）＝Ｏ； 図１１ライフゲームに対するＤＯＲＡＣの コード出力 図１２ライフゲームのＣ言語の記述 ３．４コード生成 コード生成器は，構文木からよりアセンブラ命令に近い中間コード（擬似レジスタ， メモリ間の演算）として生成し，その後対象とするＳＩＭＤ命令群に変換する．中間コー
ド生成には，使用レジスタ数が少なくなるアルゴリズムを用いる[14]、現状では，DO-RACはＭＭＸ及びSSE2の命令セットを対象としたコンパイルが可能である．式の評 価で利用されなかったレジスタには，最も多く使われるものから順に定数，変数が割 り当てられる．“pandn，'命令（オペランドａを論理否定してオペランドｂと論理積をと る）も可能場合は利用する．また，中間コードの変換ルーチンを変更することで他の ＳＩＭＤ命令セットにも対応可能である．図４の近傍則に対してDORACが出力する状態 更新処理のコードを図11に示す．４．評価実験
DORACが生成するＯＡシミュレータの実用性を示すため，Ｃコンパイラが生成する シミュレータと処理時間の比較する実験１を行った．実験１に用いたＣＡモデルは，多 数決モデル，ライフゲーム，ＨＰＰモデル，道路交通モデル，砂モデルである．実験は，900ＭHzのPentiumＭ(ＰＭ）と850ＭHzのPentiumllI(P3)の計算機で行ったＰＭに対し
てはSSE2のコード，Ｐ３についてはＭＭＸのコードを実行した．状態は８ビットで表現 し，セル数256x256で全セルの状態を5000回更新するのに必要な処理時間を計測した． DORAC版は，ｘ軸に対するループが展開ざれ１重ループのコードが出力されるように 設定した．ｃ言語版は，状態の取得にマクロを用い，境界付近はシャドウ・エッジを 行うことで境界処理を最適化した．また，VisualＣ+＋バージョン６０においてPentium Proプロセッサ向けの実行速度に対する最適化のオプションをつけてコンパイルした． 一般にこのオプションをつけてコンパイルした場合がもっとも実行速度が速くなる． 図１２にＣ言語版ライフゲームシミュレータのプログラムの主要部を示す。 評価に用いたＣＡモデルは，よく知られた３つのモデル（多数決モデル，ライフゲーム，ＨＰＰモデル)[2]，道路交通シミュレーションに用いられるモデル（道路交通モデ
ル），コンパイラの性能評価のために我々が設計したモデル（砂モデル）の５モデル である．また,ｉｆ変換が性能に与える影響を調べるため全体の演算に対するif変換の 対象となる代入文の割合を算出した算出は，以下で行った ｉｆ文ブロック内の代入文の数 演算子の数十代入文の数 －１０－多数決モデルは，対象セルの状態と対象セルに接する８つのセルの状態の合計が５ 以上の時，次の状態は１，それ以外の時０とするモデルである．ランダムに生成され た初期状態に対して多数決モデルを適用すると，動物の模様に似た形状が現れる．こ れは，ＯＡのもつ自己組織化の‘性質の一つとされている． ライフゲームは，対象セルに接する８つのセルの状態の合計（SUM）に以下の規則 を適用して，次の時間ステップの状態を決定する． ●ＳＵＭが２の時，状態は変化しない 。ＳＵＭが３の時，次の状態は１ 。それ以外の時，次の状態はO HPＰモデルは，流体解析に用いられる格子ガスオートマトン法で最初に提案された モデルである．このモデルでは単位質量の粒子が正方格子の格子点上に存在し，格子 状を単位速度で移動し別の粒子と散乱する．衝突後の粒子はそれぞれ，それまで粒子 のなかった方向へ跳ね返る．
道路交通モデルは，Nagelらが提案し，MicroSimやTRANSＩＭＳに採用されている多
速度モデルを用いた[15]～[17]、このモデルは，多くの交通シミュレーションに適用さ
れており，再現性と実用性が確認されていろ['８１
実験に用いたモデルは，Nagelらが提案した初期のモデルで，近傍則は以下のように
定義されろ． ・減速：前方の車が，近すぎると減速する ・加速：前方の車間距離が十分あり，最大速度に達していなければ加速する 最大速度は，４（1時間ステップで４セル移動する）とし，参照する近傍セルの範囲は ５セルである． 砂モデルは，ｉｆ文を多重にネストした例として筆者らが作成したモデルである．コ ンパイラの性能試験用に設計したため，厳密に砂の振る舞いを再現するモデルではな い．条件文の割合は，４５％である．このモデルは，以下の規則に従って状態が変化す る．参照する近傍の範囲は２セル分である． ・砂は，下に何もなければ落下する ・砂は，下に砂があればある確率で停止する ・停止しなかった砂は，等確率で左右どちらかにスライドする 実験１の結果を図１３に示す．棒グラフは，各シミュレーションの実行時間を表して いる．ＭＭＸの結果グラフにおける下部の折れ線グラフは，ｉｆ変換される代入文の割合 である．上部の折れ線グラフは，○版に対してＤＯＲＡ版のシミュレータが何倍に高速 化されるかを示している． ＤＯＲＡ版のシミュレータは，Ｃ版と比較して多数決モデルで，ＭＭＸでは156倍，ラ イフゲームで15.4倍，ＨＰＰモデルで109倍，道路交通モデルで４９倍，砂モデルで7.6 倍高速化されることが示された．ＭＭＸと比べてSSE2の速度向上比が小さいのは，実 験に用いたＰＭでは通常の整数演算性能が大幅に向上（スループットは２倍以上）と条 件分岐命令の分岐予測精度の向上が理由として考えられる．また，ＭＭＸはスーパース カラにより演算命令同士が並列実行されるのに対してSSE2の命令は並列実行されない[９１したがって，６４ビットレジスタに対するＭＭＸ命令に対して128ビットのSSE２
-１１－蛾蕊瀦観《堂切謬〕 騨鋒ｶﾞﾄﾞq aGpI鶇 4.巳ひび :&(》｡” Ｚ⑥囮○百 ｉｐＤ礎 ｡ ＃ ｑ ０ ０ 。 ⑥ Ｑ 側 ０ を６ ロ 伽 ３ 口 回 心。⑥ 晒 晶 姻鰄如緬坤心邸杁、、 １１１１１３旬４２ｂ 恵sB Fi⑪ 4蝉 争.Ｃ 患黛 *ＪＵ 酋且 Ｉ 鵡間l掛 …帝 毎F３８
伽關｡.樹,鐵臘綴
１
嶽轍艤織鐵謬
図１３実験ｌの結果 命令が倍の性能を発揮するわけでない。また，ｉｆ変換が多く行われるモデルほど速度 向上比が小さいことから，ｉｆ変換による演算の増加が性能低下を招いていると考えら れる。 ５．おわりに 本論文では，拡張ＳＩＭＤ命令を用いて高速なＯＡシミュレータを生成するDORAOの 仕様及び最適化とＯＡ近傍則記述言語ＤＯＲＡの言語仕様について述べた。ＤＯＲＡ言語 は，近傍則の記述に特化した言語であるためＯＡモデルの仕様を簡潔に記述できる。ま た，DORAOは，ＯＡの持つ本質的なデータ並列性を利用して並列化したＯＡシミュレー タを生成するためユーザは並列化に関して意識することなく高速なＯＡシミュレーショ ン環境が利用できる。近傍則の複雑さが異なる５つのＯＡモデルに対してDORAOと Ｏコンパイラを用いて実験的に開発したＯＡシミュレータについて処理時間の比較を 行ったところ，ＭＭＸでは約５倍以上，SSE2では約２倍以上高速化されることが示さ れた。 拡張ＳＩＭＤ命令を用いた並列化は，ＰＶＭなどを利用した他の並列化手法と基本的に 併用可能であるため，これらを組み合わせた並列化を行うことでさらに高速なＯＡシ ミュレーション環境の構築が期待できる。 文献 ［1］Wblfram，Ｓ：Computationtheoryofcellularautomata，OommwzZcqtZo〃ｓＺｎＭｑｔ/１ｃｍ(utjccILPhWcs、 ＶｂＬ９６,ｐｐｌ５－５７(1984） ［2］加藤恭義,光成友孝,築山洋:セルオートマトン法,森北出版(1998） ［3lPatterson,DAandHennessyうＪＬ：OomputerAmc/ZitectureAQuqntitqtjueAZlpmoｑｃ/j,MorganKauf mannPublishers,Inc.,secondedition(1996） ［4］Margolus,Ｎ:CAM-8:acomputerarchitecturebasedoncelluarautomata(1993）Physiscsofcomputation seminar． ［5］EckaIt,J、.:AOellularAutomataSimulationSystem,ACMSIGPLAjWVbtjce,VbL26,Ｎｏ８,pp80-85 （1991） ［6］Fisher,Ｒ・andDietz,ＨＱ:ＣompilingfbrSIMDWithinaRegister,LOPO'98(nVCFI650,pp290-304 （1998） ［7］京昭倫,岡崎信一郎,黒田一郎:画像フィルタ処理の高速化に向けたメディア拡張プロセッサ用ＳＩＭＤコンパイ ラ,情報処理学会研究報告計算機アーキテクチャ2003-ARC-154,ｐＰ８５－９０(2003）[s]鳶瀧fFi穰瀞雛團鵜flIiijid)ﾌﾞｰﾄﾏﾄﾝｼﾐｭﾚｰﾀ用ｲﾝﾀﾌﾟﾘﾀの開発人工知能学会論文
［9］Ｃor]p､,I:IA-32mtelArchZtectureOptimZzqtiomRG/brenceMqm‘αl(2003） [10］Johnson,ｓｏ：Yacc：YetAnotherCompileHOompileⅢ，［WZXPro9mmmer'SML"uql,ＶｂＬ２,Holt， Rinehart,andWinston,NewYbrk,ＮＹ,USA,pp353-387(1979） [11］A11en,ＪＲ.,KennedyうＫ,Porterfield,ＯａｎｄＷａｒ正en,ルConversionofcontroldependencetodata dependende,Proceedin9solfiihelO仇ＡＯＭＳＩＧＡＣＺＬⅥGPLAjVsZ/mposzT‘monPrjncjplesqfPro9rqmmm9 JqnDuQ9es,ＡＣＭＰｴess,ppl77-189(1983） [12l藤波順久,阿部正佳:ＳＩＭＤ型拡張命令をもっと使った最適化への道のり,第43回プログラミング・シンポジウ-12-ム報告集． [13］ [14］ [15］ [16］ 天野英晴,高橋義造,富田眞治,渡辺勝正,渡辺琢美:並列処理機構,丸善株式会社(1989)． 中田育男：コンパイラの構成と最適化,朝倉書店(1999)． Schreckenberg,Ｍ､,Schadschneider,Ａ､,Nagel,Kandlto,Ｎ：DiscretestochasticmodelsfbrtrafIicflow， P/23/sjcql比Weu）Ｅ,ＶＯＬ51,Ｎ。､４，ｐ２９３９(1995)． Ｎage1,Ｋ.OStretz,Ｐ.,Pieck,Ｍ,LeckeyぅＳ､,DonnellyiR・andBarrett,ＣＬ.：ＴＲＡＮＳIMStrafIicflowchar-acteristics,nchnicalReportLosAlamosUnclassifiedReport97-3531，LosAlamosNationalLaboratory (1997)． Rickert，MandWagner，Ｐ.：Parallelreal-timeimplementationoflarge-scale，route-plan-driventraflic simulation,InMMD〃ｂＺ/s､Ｃ,ＶｂＬＶＯＬ７,ｐｐ､133(1996） 加藤恭義：セルオートマトン法による道路交通シミュレーション，人工知能学会誌,ＶＯＬ15,No.２，pp242-250 [17］ [18］ ● 、ｎ日■８〃〃 （姻皿叩） （“叩叩） 〈叩叩） （叩。〈】 〃〃ⅡｕⅡ、 －１３－
