Florian Richoux 
  
Yves Caniou 
  
Philippe Codognet 
  
, 我々は離散組合せ問題を並列処理により効率的に解く研究を進めてい 
  
, これを中心に 
  
, 我々の最近の研究成果 について報告する 
  
コスタス配置問題に対する超並列組み合わせ最適化解法

,効率的な並列実装を実現したいという期待が高まってきている。 実際のところ,並列アルゴリズムの研究は制約充足問題の研究の黎明期からすでに始まってい る。そのころの研究は,当時プログラミングのベースとされていた論理型プログラミング言語 が持つ並列探索の機能を活用するものであった。 その後,様々な研究が行われ,並列実装が提案されてきたが,多くの場合は何らかの形でい わゆるOR並列性に基礎を置く実装であり,大規模な探索空間を小空間に分割し,それらを異な るコアに割り当てることにより並列化方式を採用していた。また,多くの研究では共有メモリ 並列計算機を仮定して,大域的なメモリ空間に構築されたデータ構造を共有して,それを参照 しながら各コアが部分計算を進めるというものであった。このような方式で効率的に並列実装 ができるのは 8 コア程度であり,それより大規模な並列計算機を効率的に活用する制約充足問 題のアルゴリズムは少数であった。 その後は徐々に並列処理の効率的な実装に関する研究が進んでいる。Comet systemは制約充 足問題の解法の実装に関する一連の研究であるが,局所探索型アルゴリズムと制約伝搬型アル ゴリズムの両方を並列実装し,小規模なPCクラスタで並列計算を実現したものがある [1,2] 。 最近になって,12コア程度まで並列実装が進んでいる。PaCCS[3]はさらに進んだ研究で, 100 コアのオーダーまで高い性能を達成することが報告されている。 また,同じ離散組合せ問題に属する問題である充足可能性問題( Satisfiability Problem: SAT と略されることがある)は,制約充足問題を {0, 1} の 2 値に制約した有限値域制約充 足問題とみなすことができるが,これに関しては研究が多く進められており,いくつかのマル チコア並列実装,さらには大規模なPCクラスタでの実装も行われている。 これに対し我々は,制約充足問題を数千コア以上の大規模並列プラットフォームにおいて効 率的に並列化する研究に取り組んでいる。そのためには,従来手法で用いられてきた共有メモ リ計算機を想定した共有データ構造の利用や,クラスタ型並列計算機で用いられてきた密に連 携したマスター・ワーカー型並列制御ではなく,新たな形の並列性を検討する必要がある。 我々の取るアプローチは,まず完全に独立な並列計算,もしくは限られた通信による並列計算 で制約充足問題が効率的に解けるアルゴリズムを考える。現在,これが実現しつつある段階で ある。次のステップとして,これに何らかの通信を追加することによって実効性能を上げるの 工夫ができるかを研究している。 スケーラブルな制約充足問題の並列解法を検討するにあたって,従来手法である制約伝搬型 アルゴリズムをベースにして,大域的な制約グラフを多数のコアで共有して並列化するという アプローチでは,大規模な並列化が困難であることは明白と思われる。これとは別のアプロー チとして,探索空間を分割して並列化する領域分割法などがある。これは可能性のある興味深 い手法であるが,初期的な実装実験によれば,高性能化は数十コア程度で飽和する傾向にある ことが知られている。例えば17クイーン問題の全解探索においては,32コアで28倍の高速化率 であるところ,64コアで29倍の高速化率しか得られなかったという報告がある [4] 。最近では より細粒度の領域分割法を用いることでより高いスケーラビリティが得られるという報告もあ る [5] 。それによれば,制約充足問題の古典的なベンチマークにCSPLibがあるが,Gecodeをベ ースラインとしては40コアで平均14倍,or-toolsをベースラインとすると40コアで平均20倍の 性能を達成している。しかし,唯一80コアで70倍の性能を得た17クイーン問題を除いて,40コ アまでの性能しか報告されていない。 より広く組合せ最適化の研究において考えると,最初に大規模な並列計算が行われた手法は, 古典的なアルゴリズムである分枝限定法であった。分枝限定法において効率的な大規模並列計 算が成功した理由は,並列に走るプロセス間で通信しなければならない情報は,基本的には現 在の上限値だけであり,通信の必要性が多くはなかったということが考えられる。このような 背景から,グリッドコンピューティングにおいても最適化問題の解法として,分枝限定法が実 装され評価されたという成果が知られている [6] 。それによれば,数百コアに到るまで良好な 高速化率が達成されたということであるが,興味深いことに,それよりもコア数が増大すると 実行時間は一定になる傾向があると結論付けられている。また,プロジェクトスケジューリン グ問題に対する比較的シンプルな制約充足アルゴリズムを IBM Bluegene/P スーパーコンピュ ータに実装した事例 [7] があるが, 512 コアまではほとんど線形な高速化を達成したが,これ を越えて1024コアまで実行したが高速化が達成されなかったということで,完全な成功とはい えない事例である。ごく最近になって, Limited Discrepancy Search という最適化アルゴリ ズムについて数千コアというレベルまで良好な高性能化を達成する並列化の結果がある [8] 。 この研究で重要な特徴として,並列に実行されるプロセス間でほとんど通信が必要でないとい うことと,良好な負荷分散が得られるという 2 点が挙げられる。 3.我々のこれまでの研究 さらに異なるアプローチとして我々が採用しているのが,局所探索とメタヒューリスティッ クスによる手法である。ここでは,制約充足問題を最適化問題として定式化する。すなわち, 充足していない制約の数を最小化するような目的関数を設定し,これを最適化のアルゴリズム であるメタヒューリスティックスを伴う局所探索によって解くことで,目的関数がゼロになっ たときに制約充足問題の解が得られるという仕組みである。局所探索に属するアルゴリズムの 中で,特定の問題領域に依存しない汎用的な局所探索法として Philippe Codognet らにより提 案されたアルゴリズムに,適応的探索法( Adaptive Search )がある[9,10]。適応的探索法で は,ランダムな初期値からスタートして,満たされていない制約条件の数を減らすように,適 当な目的関数を設定し,その目的関数を減少させるように,解を少しだけ変更する(近傍探索 と呼ぶ)。このとき,目的関数は単純に満たされていない制約条件の数に設定するのではなく, うまく条件を満たす解に近づくように,問題ごとに工夫された適切な目的関数を選ぶことによ り,効率的に問題を解くことができるのである。ただし,近傍探索だけでは一般の初期値から 解には到達しない。このため,様々な初期値を取り,並列に探索する。この適応的探索法は, 制約充足問題のような問題の構造を利用して探索を方向付ける局所探索のヒューリスティック スであり,線形の算術的制約条件,非線形の算術的制約条件,記号的制約条件など,広いクラ スの制約に適用可能な手法である。また,適応的探索法は,本来的に過剰制約問題に適応する 能力を持っている点でも利点がある。我々の提案手法は,この適応的探索法をベースとして, 独立な複数の初期値から局所探索をスタートさせることにより,極めて少ないプロセス間通信 で並列化を可能にするものである。 我々の初期の実装[11]では,まず16 Cell/BE SPEコアを有する IBM BladeCenter で実験した ところ,魔方陣,全音程を列挙する音列,完全正方形分割など,さまざまな古典的な制約充足 問題に対してほとんど線形な高速化が得られた。さらに,このスケーラビリティが数百あるい は数千コアに到るまで維持されるような効率的な大規模並列実装を目指した。このために C 言 語による逐次の適応的探索法の実装をもとにして, MPI を用いた並列プログラムを構築した。 この実装は MPI が使える様々なプラットフォームで実行でき,PCクラスタ,スーパーコンピュ ータ,グリッドシステムでも動作する。性能評価においては,CSPLibにある制約充足問題のベ
子を考え,そこに n 個の印をつける。その際,印は各行および各列には必ずひとつずつなけれ ばならず,また, 2 つの印のすべてのペア(n (n-1)/2 通りある)を考えたときに,その格子 上の相対位置が異なるベクトルとなるようにしなければならない。図1にサイズ4のコスタス 配置問題の解の1つを示す。Vij は i 番目の点と j 番目の点の相対位置ベクトルである。 図1.コスタス配置問題 このように,コスタス配置問題は,記述すれば極めて単純であるが, 2 つめの条件が計算を 極めて複雑にする。コスタス配列問題の計算複雑性は指数関数的に増大し,ごく小規模の問題 を除いて,厳密に解くことは極めて難しくなる。これまでにn=32のコスタス配列問題について は,解があるかどうかも知られておらず,45年の間未解決問題として残っている。 そこで,我々はこのn=32のコスタス配列問題を大規模 HPC Challenge で取り組むこととした。 これまでの実行から見られる傾向から,n=32の問題が解けるのは76,800コアで少なくとも24時 間に近いオーダーと見積もられた。これはリスクのある選択であることはわかっていたが,成 功すれば歴史的な成果となるため,我々はこのような選択をした。22時間30分の間 76,800コ アを走らせて実行したが,残念ながらn=32の解は得られなかった。この結果は,下記のように, 適応的探索の実行時間の大きなばらつきから,ある程度予想された結果ではあった。さらに計 算時間を延ばすと解が見つかる可能性もあるが,今回の結果から,そもそもn=32の問題に解が ないという可能性も捨てられない。 まさしくチャレンジであったn=32の解は得ることができなかったが,滞在期間中にFX10を用 いて大規模なコスタス配列問題を適応的探索法で解くことができた。例えば,n=22のコスタス 配列問題を 512 コアと1152コアで解いたときに,スーパーリニアな高速化が達成された。また, 我々が従来は達成できていなかった大規模な問題として, n=23,

  ,近似アルゴリズムが必須である。局所探 索とメタヒューリスティックスに属するアルゴリズムとしては, Simulated Annealing, 各種 のGenetic Algorithm, Tabu Search, Swarm Optimization, Ant-Colony Optimization などが よく知られている。これらは乱数を用いており,Las Vegas アルゴリズムと呼ばれているアル ゴリズムに属している。 離散組合せ問題の重要なクラスのひとつである制約充足問題( Constraint Satisfaction Problem: CSPと略されることもある)においても,古典的手法である制約伝搬型アルゴリズム では到達できなかったような問題が,局所探索の手法により解くことができることが明らかに なってきており,研究者の注目を集めている。制約充足問題とは,離散的な変数に対して加え られた一連の制約条件をすべて満たすような変数の値を求める問題である。制約充足問題とし て古くから知られているものに魔方陣がある。魔方陣は,正方形n×nのますに数字を入れて, 縦・横・斜めのいずれについても和が同じになるものである。すなわち,ますの数字が変数と なり,縦・横・斜めのそれぞれについての和が制約条件となる。このほか n クイーン問題など が古典的な制約充足問題としてよく知られている。 最近では計算機の主流は 2 コア, 4 コア, 8 コア,16コアといった並列計算機になってきて おり,制約充足問題などの離散アルゴリズムの研究分野においても,これらの計算機が提供す る高い計算処理性能を活用し

まで実行してきており

  ンチマーク問題のほか,さらに難度の高い組合せ問題として,コスタス配列問題( Costas Array Problem )にも取り組んだ。このコスタス配列問題は,レーダーとソナーの周波数に関 する通信分野の応用のある組合せ問題である。これらの問題を,東京大学のFX10とHA8000スー パーコンピュータ, Grid'5000 インフラストラクチャ(フランスの科学技術計算のための全国 規模グリッドシステム),ならびにドイツのユーリヒスーパーコンピュータセンターにある JUGENEスーパーコンピュータにおいて実行してきている。これらのシステムは大規模並列計算 機アーキテクチャの様々な方式を代表するものであり,我々の目標としては,特定のハードウ ェアや特定のアーキテクチャに依存した結果ではなく,できるだけ汎用的な知見を得ることを 目指した。これまでにHA8000および Grid'5000 では 256 コア,JUGENEでは8192コアまで実行し, ほぼ線形な高速化率を達成してきている。今回の大規模 HPC Challenge ではFX10の76,800コア C 言語で MPI を用いて並列化されている ため,大規模な改変は必要なく,これまでの日本,フランス,ドイツにおける複数のスーパー コンピュータの利用経験も役立ち,比較的短期間でポーティングを実現できた。 この実績に基づいて,東京大学情報理工学系研究科コンピュータ科学専攻の須田礼仁と,同 専攻に所属するJFLI( Japan-French Laboratory for Informatics: 日仏情報学連携研究拠 点)の構成員であるPhilippe Codognet, Florian Richoux, Yves Caniou の連携で,東京大学 情報基盤センターの大規模 HPC Challenge に応募した。この大規模HPC Challenge はFX10の全 系が24時間利用できるというもので,我々の提案は採択されて, Florian Richoux の滞在期間 のほぼ最後にあたる 8 月28日に割り当てられた。当日はキューの設定などに手間取り,実際に 実行できた時間はおよそ22時間30分であったが,この間,FX10の全系76,800コアを最大限に活 用するために,日本学術振興会の短期滞在のサポートによる 5 か月間の滞在を利用して,適応 的探索法のFX10上での並列実装のために様々なテストやチューニングができたことに謝意を表 したい。 4.実装と結果 適応的探索法の並列実装のFX10へのポーティングは大きな問題なく実施でき,76,800コアの 全系を用いて実行することができた。大規模 HPC Challenge で取り組む問題としては,適応的 探索法が極めて良好に働くことが確認されている,コスタス配列問題を選んだ。 コスタス配列問題は,レーダーとソナーの周波数をノイズに強くなるように最適化する問題 に由来するもので,割り当て問題のひとつである。サイズ n のコスタス配列問題は,n×nの格

1 秒

 1 で最適解を求めることができた。また, 100 点程度のグラフに対しては,最適解から0.5%以内 の近似解を求めることができ,その所要時間は,逐次計算で約11秒,並列計算で 1 秒程度であ った。さらに大きな問題として 130 点程度のグラフでは,最適解から0.5%以内の近似解を求め ることができ,逐次計算で約 100 秒,並列計算で約10秒を要した。しかし, 150 点程度のグラ フに対しては,現在の実装では効率的に解を求めることができなかった。今後は,