---

---

---

並列環境部門 講評　課題：LIFE ゲーム

並列部門の本年の課題はConwayのライフゲームであった。参加者にはなじみやす
いものであったと思う。９作品の応募があった。

本部門の課題は、基本的にはシミュレーションの問題である。仮想時間(virtual
time)とそのロールバックを実装した作品が来るだろうかとか、セルのパターン
の変化を機械学習することによって計算量のオーダーを小さくするプログラムが
現れたらすごいなあ、とかいう話も審査員の間ではあったのだが、そこまで凝っ
た応募作品はなく、素直にシミュレーションをする“正統派”の作品がほとんど
であった。それはそれで適切な判断と言えよう。問題自身に本質的に難しいとこ
ろがなかったためもあって、すべての応募作品が正しく動作し、参加賞の授賞対
象となった。

ライフゲームをＮ台のプロセッサで並列処理する方法は、空間分割と時間分割に
大別できよう。空間分割とは、セルの存在範囲を含む２次元空間をＮ個（または
それ以上）の部分に空間的に分割して、それぞれの経時変化を各プロセッサが分
担して計算する方法である。時間分割とは、プロセッサｎがすべてのセルに関す
る１世代後の変化を計算してプロセッサ(ｎ＋１) mod Ｎに送るということを繰
り返す方法である。パイプライン処理による並列効果が期待できる。もちろん、
空間分割と時間分割のどちらにもさまざまな工夫の余地がある。

応募作品のうち、時間分割による並列処理を目指したものは一つだけであり、他
は空間分割を採用していた。空間分割の戦略には、Ｎ個の部分に分けるブロック
分割と、多数のより小さな部分空間を巡回的に各プロセッサに割り付けるブロッ
クサイクリック分割の両方がみられた。また、セルの存在範囲が動的に変化する
ようなパターンに追従する方法にもさまざまな工夫が見られた。

さて、評価は、並列処理が効果を発揮すると期待される大きな評価データを何組
か用意して行なった。あまり動かないパターン、移動するパターン、拡大するパ
ターンなどを用意し、それぞれについてプロセッサ台数を１，２，４，８，１２，
１６台と変えながら、詳細に評価データをとっていった。

大半の作品は並列効果を発揮していたが、作品および評価データによって、台数
効果の程度には大きな差が見られた。もちろん、評価は、台数効果ではなく、最
高性能が出たプロセッサ台数における実行時間（入出力の時間は除く）を主に参
考にして行なった。

《優秀賞》
   優秀賞１：宇佐 治彦殿 （東京大学大学院 工学系研究科 情報工学専攻）
   優秀賞２：福田 茂紀殿 （東京大学大学院 工学系研究科 電子情報工学専攻）
   優秀賞３：横山 大作殿 （東京大学 工学部 電子情報工学科）

この３作品は、それぞれに得意不得意があるものの、総合的にはどれも甲乙つけ
がたい性能をもっていた。優秀賞１は、移動するパターンや成長するパターンを
得意とし、オンのセルの数が比較的少ない問題から並列効果を出していた。優秀
賞２と優秀賞３は、オンのセルの数が多いパターンを得意とした。優秀賞２が成
長するパターンに対して良い成績を残す一方、優秀賞３は、オンのセルが非常に
多いパターンで強みを発揮した。しかし、審査員の一人が用意したプログラムの
性能に匹敵するものはなく、最優秀賞の授賞は見送られることとなった。並列計
算機による実行を真に正当化するためには、並列化の工夫もさることながら、や
はりセルの生成消滅に関する基本演算を高速化する工夫も大変重要である。

《佳作》網代 育大殿 （早稲田大学大学院 理工学研究科）

この作品は、優秀賞の３作品に準ずる性能をあげたため、佳作とすることにした。
特に、安定した大きなパターンについては優秀賞１を上回る成績をあげていたが、
パターンの移動や変化に対する追従性については優秀賞の作品の方が上回ってい
た。