高度な問題領域依存チューニングを許す並列組合せ最適化ライブラリPopKern
16
0
0
全文
(2) 50. 情報処理学会論文誌：プログラミング. Mar. 2001. 2∼数プロセッサ程度の小規模な並列計算機や PC ク. 等の細部に至るまで自由に記述することができ，また. ラスタ等，安価に利用できる並列計算環境も身近なも. 解改善状況の表示等，さらなるチューニングの助けと. のとなっている．. なる部分の記述自由度も持っている．これらの型定義. しかしながら，組合せ最適化問題の並列計算はまだ それほど 普及しているとはいえない．この原因は，並. やサブルーチン等はすべて，従来の逐次処理言語で， 逐次処理として記述すればよく，通信，同期や負荷分. 列プログラミングの困難さにある．通信，同期，負荷. 散といった並列処理の細部については利用者は考慮す. 分散等，並列プログラミングでは様々な点についての. る必要がない．. 専門知識が必要とされる．通信タイミングに起因する. 本論文の構成は，以下のとおりである．2 章では，既. バグは，同一条件下での計算実行でも再現性がなく，. 存の並列化ライブラリの問題点と PopKern はその問. デバッグ作業を非常に困難にする．. 題点をどのように回避するのか，という PopKern 設. これらの問題を避けるべく設計された並列言語を用. 計にあたっての基本方針を示す．次に 3 章では，Pop-. いれば ，並列プログラミングは容易なものとなるが，. Kern の設計についてまとめる．4 章で実装方式と評. プログラマに学習を強いることになり，また過去のリ. 価を示し，最後に 5 章でまとめを行い，これからの展. ソースを生かすという意味においても不利となるため，. 望を示す．. 並列言語はあまり一般化していないのが現状である． そこで，従来の逐次言語上で並列化ライブラリを用. 2. 基 本 方 針. いて並列プログラミングを行うという手法が有力なも. 2.1 既存ライブラリの問題点. のになると考えられる．実際，いくつかのライブラリ. 組合せ最適化問題の並列化ライブラリはいくつか存. が研究されているが，実問題における組合せ最適化の. 在する1)∼3) ．これらを用いれば，並列プログラミング. 専門家たちはこれらのライブラリを使わない．これら. に関する専門知識がなくても簡単に並列計算を行うこ. のライブラリは特定の問題領域を想定していたり，逆. とができる．しかし，実問題を専門に解いている専門. に汎用性を追求した副作用として高い探索効率が得ら. 家たちはこのようなライブラリを使わない．これは，. れなかったりするためである．. 探索性能面に問題があるためである．. 組合せ最適化問題は，適用される問題領域に特化し. 既存ライブラリのほとんどは，プ ログラマが書く. たチューニングによって探索効率が大きく向上する．. コードの量をできるだけ少なくすることを目標として. 探索量のオーダーが変わるほどのチューニングが行え. 作られている．つまり，組合せ最適化をできるだけ簡. ることもしばしばあるため，問題領域に特化した技法. 単に実行できるよう，利用者は少しの部分を定義する. を使わないまま並列化したプログラムの性能は，問題. だけでよいように作られている．しかし，大規模な実. 領域専門に書かれた逐次プログラムのそれに劣ること. 問題を解く際には，このようなライブラリでは問題が. も多い．こういった問題領域依存のチューニング技法. 起きる．. は，汎用ライブラリに用意されたいくつかのパラメー. 組合せ最適化問題は，適用される問題領域に特化し. タを調整する，といった簡単な手段では実現できない. たチューニングによって探索効率が大きく向上する．. ことが多い．. 以前からさかんに研究されてきた問題領域では，その. 無数にある適用問題領域のすべてに対してチューニ ングを行った汎用並列化ライブラリを構築することは. 問題に特化したチューニング技法が多く存在しており， チューニングによって探索量のオーダーが変わるほど. 現実的ではない．しかし，組合せ最適化アルゴ リズム. の効果が出ることもしばしばである．よって，大規模. の並列化技法はある程度確立したものが存在する．し. な実問題を解く際には，これらのチューニングが行え. たがって，この技法を用いてプログラムを自動的に並. ないとまったく使いものにならない．. 列化してくれるライブラリを，問題対象領域に依存す. 例として，分枝限定法による探索を考えてみる．探. る部分の記述自由度を高くして構築すれば，実問題に. 索効率をあげ る技法としてまずあげられるのは問題. おける専門家にとって非常に有用なものとなる．. や解のデータ表現方法の工夫である．たとえば，探索. 本論文では，並列化ライブラリのパッケージである. 途中の解の表現を，探索木上での親に相当する解との. PopKern（ Parallel OPtimizer KERNel ）について論 じる．PopKern は，問題領域依存の高度なチューニン. 差分として表現することは，メモリの節約や評価値計. グを可能にした組合せ最適化問題の汎用ライブラリで. 問題が再利用できるようなデータ構造を作ったり，メ. ある．PopKern では，利用者は問題や解の表現形式. モリ上の配置を工夫したりと，データ表現では様々な. 算の高速化といった利点をもたらす．ほかにも，部分.
(3) Vol. 42. No. SIG 3(PRO 10). 並列組合せ最適化ライブラリ PopKern. チューニングが考えられる．また，探索途中の解候補 の集合をどのように保持するか，そしてどのような順. 51. 合等のデータ構造も同様に考えた． 一方，PopKern が提供すべき，問題領域に依存し. 番で解候補を選んで探索を進めていくか，といった工. ない部分については，探索アルゴ リズムに従って探索. 夫も考えられる．枝刈りを行うときも，類似局面が後. を制御するために必要な部分，として考え，PopKern. から現れたときに枝刈りの情報が生かせるような機構. のカーネルは基本的に探索を制御する役割だけを持つ. をつけたり，統計情報をとって方針決定に生かしたり. こととした．たとえば分枝限定法では，現時点での最. といった工夫がありうる．ワーキングセット縮小のた. 良解，上界，下界等を保持し，探索途中の解の選択・. めに探索途中の解集合全体を対象に 1 度に枝を刈る. 分枝・枝刈りの繰返しというアルゴ リズムの流れを実. のか，逐次に枝を刈っていくのか，その選択や枝刈り. 現する機能だけを PopKern に持たせる，という方針. のタイミングも問題領域によって異なる．さらに，入. で設計した．しかし，並列化ライブラリとしての側面. 力データに応じて探索戦略を変化させることも考えら. では，通信や同期，負荷分散といった並列処理に関す. れる．. る部分を利用者が極力意識しないように設計を行った．. このように，適用される問題領域に特化したチュー ニングの可能性は多岐にわたる．しかし，既存のライ ブラリでは，問題や解のデータ構造の自由度が低かっ たり，枝刈りの過程が利用者から見えなかったり，探. PopKern が想定する利用者は，並列計算の知識が必 ずしも十分ではない特定問題領域の逐次プログラミン グの専門家たちだからである． このような観点から，PopKern ライブラリが提供. 索途中の解候補集合をすべてライブラリが管理して，. する機能と利用者定義部分との切り分けにあたり，利. その試行順序が固定されていたり，または複数の方法. 用者の問題領域依存のプログラミング自由度をできる. から選ぶだけであったりと，このようなチューニング. だけ高くするように設計を行った．. の自由度が低いものであることが多い．それぞれのラ イブラリでは，ある程度特定された問題領域や非常に 包括的な問題領域を想定して，その中で高速な探索方 式を提供していることが多いため，想定と異なる問題 領域でのチューニングは困難になるのである．. 2.2 PopKern の設計方針. 3. PopKern 3.1 構. 成. PopKern の構成を図 1 に示す． PopKern は次の 3 つの機能部分からなる． 組合せ最適化ライブラリ PopKern は代表的な組合. 上に述べたように，既存のライブラリは，組合せ最. せ最適化アルゴ リズムを提供する．これらのア. 適化ライブラリとしての側面が強く， 「 組合せ最適化問. ルゴ リズムは，問題領域独立部分と問題領域依存. 題の専門知識がない初心者が，簡単にある解法のプロ. 部分に分けることができる．問題領域独立部分は. グラムを構築でき，それを並列実行できる」ことを目. PopKern の組合せ最適化ライブラリ部分に組み込. 的としている．しかし ，PopKern は，組合せ最適化. まれている．問題や解候補の型表現等，問題領域. ライブラリとしての側面は，問題領域に依存しないフ. 依存部分は PopKern には定義されていない．こ. レームワークを提供するだけであり，そのうえで並列. の問題領域依存部分を，PopKern の組合せ最適. 化ライブラリとしての側面を最大限に発揮しようとし. 化ライブラリ部分にプラグインすることで，並列. 「 組合せ最適化問題の ている．つまり，PopKern は，. 組合せ最適化アルゴ リズムの動作が実現される．. 専門知識を持つ問題領域専門家が，ある解法のフレー ムワークのもとで自由にプログラミングでき」 ，しか も「並列を意識することなく逐次プログラミングした ものが，ライブラリによって自動的に並列計算され， その結果，処理の高速化，問題の大規模化が可能にな る」ことを目標にしているのである． このような目標を達成するため，PopKern の設計 方針を以下のように定めた．まず，問題領域に依存す る最大の部分は問題，解等のデータ構造である．Pop-. Kern ではこのデータ構造に対する制限をなくし，完 全に利用者定義にした．よって，問題や解を操作する サブルーチンも必然的に利用者定義となった．解の集. 図 1 PopKern の構成 Fig. 1 The design of PopKern..
(4) 52. 情報処理学会論文誌：プログラミング. PopKern のカーネル部分は，問題領域に依存す. (1). 問題をファイルから読み込み，問題データをす べての PE（ Processing Element ）に配布する．. る利用者定義のデータ型をブラックボックスとし て扱い，利用者が定義したサブルーチンを介して. Mar. 2001. (2). それぞれの PE で，指定されたアルゴ リズムに 基づき求解を始める．各 PE はその PE 内で探. データを扱う．利用者の定義した，データ型定義 およびそのデータに直接アクセスするアルゴ リズ. 索された解候補のうち，最良となるものを保持. ム中で必要なサブルーチンを，PopKern のシス. している．これを局所最良解候補と呼ぶ．探索. テムと一緒にコンパイル，リンクして実行用バイ. が進むにつれ，より良質の解候補が見つかり，. ナリを作成する．これらのサブルーチンを記述す る際には，問題領域に関する専門知識を使い，こ. 局所最良解候補は更新されていく．. (3). ローバルマネージャは，システム全体の解候補. 並列計算に関する専門知識は必要としない． 並列化ライブラリ. PopKern の実行時には，すべての PE を統括 するグローバルマネージャが 1 つ作られる．グ. れまでどおりの逐次プログラミングを行えばよく，. PopKern の並列化ライブラリ部. のうち最良となるものを，大域最良解候補とし. 分は，プロセッサ間の通信，同期，および負荷分. て保持している．局所最良解候補が更新される. 散を実現する．組合せ最適化ライブラリ部がこれ. と，この解候補はグローバルマネージャに送ら. らの機能を使って並列計算を行う．利用者がこれ. れ，そこで大域最良解候補の更新が行われる．. らの機能を直接使うことはなく，並列計算技法に. (4). 大域最良解候補が更新されると，その解はすべ. 関して考慮する必要はない．PopKern のカーネ. ての PE に対して放送され，それぞれの PE が. ル部が，利用者定義データのプロセッサ間移動や. 持つ局所最適解に反映される．この，新たに設. 同期を自動的に行う．PopKern は利用者定義デー. 定された最適解候補は，次に呼ばれる組合せ最. タの内部構造を関知しないので，通信の際には利. 適化アルゴ リズム基本ステップから利用者定義. 用者が定義したシリアライズルーチン（バイト列. ルーチンに与えられ，反映される．たとえば ， 分枝限定法では， 「 ノード 集合から 1 つノードを. への変換ルーチン ）を用いる． 並列乱数生成ライブラリ. 選び，分枝，上下限チェックを行い，ノード 集. 確率的な組合せ最適化アル. ゴ リズムにおいて，利用者は乱数を用いて解の改. 合を書き換える」という流れが基本となる 1 つ. 善等を行うが，並列実行時の乱数生成器の呼び出. のステップであり，局所最適解の更新はこのス. し順が実行ごとに変化するため，並列動作を考慮. テップとステップの間に行われ，更新された最 適解の情報は次のステップから利用可能となる．. していない乱数生成器は実行ごとに異なる乱数列 を発生してしまう．これにより，利用者定義ルー. (5). また，最良解候補が更新されたとき，PopKern. チンの動作の再現性がなくなり，デバッグを大き. は利用者が定義した終了チェックルーチンを呼. く妨げることになる．このような問題に対応する. ぶ．最良解候補の質が十分満足のいくものであっ. ため，PopKern は，並列計算に適した，乱数列. た場合，その時点で探索を打ち切ることができ. が実行順には依存しない疑似乱数列生成ライブラ. る．また，同時に表示ルーチンを呼ぶこともで. リを提供する． PopKern は現在のところ次の 4 種類の並列組合せ. きるので，局所最良解候補や大域最良解候補の. 最適化アルゴ リズムを提供している．. • 山登り法 • 分枝限定法 • 焼き鈍し法 • 遺伝的アルゴ リズム. 改善の様子を追うこともできる．. (6). 終了指示があると，グローバルマネージャに保 持された大域最良解候補を出力して探索を終了 する．上に述べた終了チェックルーチン，およ び実行時引数に与える実行制限時間によって終 了の条件を決めることができる．. ヒューリスティックに基づいて近似解を探索するため. 3.3 共通する利用者定義部分 前述の基本動作を得るため，利用者は 4 つのアルゴ リズム共通に以下の部分を定義する．利用者は，C 言. のアルゴ リズムである．. 語で逐次処理として利用者定義部分のプログラミング. 分枝限定法はすべての組合せを探索して最良の解 を得るためのアルゴ リズムであり，その他の 3 つは. 3.2 基本的な動作 4 つのアルゴリズムで共通な，PopKern の基本的動 作を以下に示す．. を行えばよい． 問題/解の型定義 PopKern は問題や解がどのような データ構造で表現されているか関知しない．利用.
(5) Vol. 42. No. SIG 3(PRO 10). 並列組合せ最適化ライブラリ PopKern. struct city_coordinates { double x, y; }; typedef struct euclid_tsp_problem {. void popkern_encode_problem( popkern_problem *problem) { int k;. int num_cities; struct city_coordinates *coords;. popkern_send_long( problem->num_cities);. } popkern_problem;. for (k = 0; k < problem->num_cities; k++) {. typedef int *popkern_solution; 図 2 TSP のための問題/解記述データ型定義例 Fig. 2 An example of problem/solution definition for TSP.. popkern_send_double( problem->coords[k].x); popkern_send_double( problem->coords[k].y);. 者はこのデータ構造を C 言語の型として定義す. }. る．“問題” 構造には，計算途中で変化しない，組 合せ最適化の対象となる問題に関する情報を格 納する．“解” 構造には，計算途中で更新されて いく，可能な解を表現する情報を格納する．巡回. 53. } 図 3 TSP のための問題シリアライズルーチン定義例 Fig. 3 An example of serialize routine for TSP.. セールスマン問題を例としてあげると，たとえば 造には都市の巡回順序を示した数列を，それぞれ. PopKern のシステムが管理している． 問題/解のシリアライズ /アンシリアライズ 問 題 や. 格納するようにすればよい．図 2 に示した例で. 解のデータ構造は，並列計算のために PE 間を. 問題の構造には巡回すべき都市の座標を，解の構. は，popkern_problem と popkern_solution の. 必要に応じて移動する．しかし ，PopKern はそ. 定義がこれにあたる．. れらのデータがど のように表現されているか知. “問題” 構造は，各 PE ごとに 1 つずつ存在する データであり，すべての利用者定義サブルーチン. らない．したがって利用者は，利用者定義の表現 形式から PopKern システムが理解できるバイト. 群に引数として与えられるので，利用者定義サブ. 列の形式へと変換するサブルーチンを定義しなけ. ルーチンが必要とする様々な “static な” データ. ればならない．これを，シリアライズと呼ぶ．逆. 構造はこの “問題” 構造の中に定義しておけばよ. に，バイト列表現から利用者定義表現へと変換す. い．もちろん，“static な” データ構造を直接利用. るサブルーチン（アンシリアライズ）も定義する．. 者定義サブルーチンから参照・操作することも可. PopKern システムは，このバイト列表現を使っ. 能であるが，このときには当然，それらのデータ. て，利用者定義データ構造の PE 間通信や同期機. の初期化ルーチンを自分で呼ぶ必要がある．この，. 構を利用者に意識させないように実現する．. static なデータの初期化ルーチンは，PopKern が. 前に例示した巡回セールスマン問題による問題. 必要とする “問題” 構造の初期化ルーチン内から. デ ータ型のシ リアラ イズには ，図 3 のように. 呼べばよい．. コーデ ィングすればよい．popkern_send_long，. なお，この “問題” 構造は各 PE ごとに独立して. popkern_send_double はシリアライズのための. おり，PE 間での一貫性の保持といったことは行. プ リミティブであり，与えられたデータを Pop-. われない． 題データを読み込まなければならない．利用者は. Kern の理解するバイト列に変換し ，ユーザの関 与しない領域で通信を行う．都市数，各都市の x， y 座標の順にシステム提供のプリミテイブを使っ. このためのサブルーチンを定義する必要がある．. てシリアライズが行われている．アンシリアライ. 同様に，最終的な解を出力するサブルーチンも利. ズの際は，シリアライズした順にプリミティブを. 用者定義である．読み込み/書き出しのための入. 使うことで，バイト列表現からデータを取り出せ. 出力は並列計算環境を意識する必要があるため，. る．図 4 にアンシリアライズの例を示す．. 問題入力/解出力 計算を始める前に，PopKern は問.
(6) 54. 情報処理学会論文誌：プログラミング. void popkern_decode_problem(. void popkern_finish_copy(. popkern_problem *problem). popkern_solution *solution, const popkern_problem *problem). { int k;. Mar. 2001. {. problem->num_cities = popkern_receive_long();. int *copied = (int *)calloc(problem->num_cities,. problem->coords = (struct city_coordinates *) calloc(problem->num_cities,. sizeof(int)); if (copied == NULL) popkern_error(. sizeof( struct city_coordinates));. "Couldn’t allocate memory " "in popkern_finish_copy()");. if (problem->coords == NULL) popkern_error( "Couldn’t allocate memory ". memcpy(copied, *solution, problem->num_cities * sizeof(int));. "in reading problem spec"); for (k = 0;. *solution = copied;. k < problem->num_cities; k++) { problem->coords[k].x = popkern_receive_double(); problem->coords[k].y = popkern_receive_double(); } } 図 4 TSP のための問題アンシリアライズルーチン定義例 Fig. 4 An example of unserialize routine for TSP.. } 図5 Fig. 5. TSP のための解データコピールーチン定義例 An example of data-copy routine for TSP.. void popkern_free_solution( popkern_solution *solution, const popkern_problem *problem) { free(*solution); }. 利用者定義データ構造のコピー/解放ルーチン. PopKern を実現している下位のシステムはコピー方 式の GC 機構を持っているが，PopKern は利用. 図 6 TSP のための解データ解放ルーチン定義例 Fig. 6 An example of free routine for TSP.. 者定義データがどのようなデータ構造をとってい. 解放が行えるルーチンを定義する必要がある．例. るか関知しない．このため，利用者定義データ構. 示してきた巡回セールスマン問題の解データのコ. 造の GC 時にはコピーやメモリ解放のための利用. ピールーチン，および解データの解放ルーチンの. 者定義ルーチンを呼び出す．. popkern_problem やpopkern_solution のコピ. 例を，図 5，図 6 に示す． 解候補のコスト 関数 解候補の質をdouble 型で示す. ーの際，PopKern は メモリイメージをそのまま. 評価関数を作成する．なお，PopKern で扱う問. コピーする．したがって，これらのデータ型の中. 題はすべて「最小化問題」とし，評価値が小さい. にすべてのデータが格納されていれば，コピー/解. ほど 望ましい解であるとする．. 放ルーチンは特に定義する必要がなく，用意され ている何もしないダミールーチンを使えばよい． 内部でポインタを用いて外部のデータ構造を参照 している場合，たとえばツリー構造をとっていた り，例示しているプログラムのように外部にデー タをアロケートしている場合は，正しくコピー/. これらに加え，利用者は必要に応じて，解の可視化 ルーチン，終了チェックルーチン，等を定義する． これらの利用者定義部分を記述するために，Pop-. Kern は以下のようなプ リミティブを提供する． • シリアライズ/アンシリアライズプリミティブ • エラー処理プリミティブ.
(7) Vol. 42. No. SIG 3(PRO 10). 並列組合せ最適化ライブラリ PopKern. • メッセージ表示プ リミティブ である．. 55. 動的負荷分散を行う．PopKern は，各 PE が現時 点で探索すべきノード 集合を持っているか否かを. シリアライズに関するプリミティブは，利用者がプ. 把握するグローバルマネージャを作る．ある PE. ログラム中で使用している 1 つの数値と，PopKern. が，自分の持っていたノード 集合をすべて探索し. のカーネルが用意したメモリ上のバイト列との相互変. 尽くしたとき，この PE はグローバルマネージャ. 換を行うものである．エラー処理プリミティブは実行. にノード を要求する．グローバルマネージャは，. 制御を可能にする．メッセージ表示プリミティブは並. まだノードがある PE に対し，持っているノード. 列実行環境下でも使えるコンソールへのメッセージ出. 集合を分割し，ノード を要求していた PE に送る. 力を提供する．. よう命令する．このようなアルゴ リズムで動的負. 3.4 並列組合せ最適化アルゴリズム. 荷分散が実現される．. 現在の PopKern は，4 種類の並列組合せ最適化ア. 利用者定義部分 分枝限定法のように探索木を枝刈. ルゴ リズムに基づいた解探索機能を提供している．以. りしつつ全解探索する場合，探索木中のノード の. 下では，それぞれのアルゴ リズムと利用者定義部分の. 展開順序が探索効率を大きく左右する．よって，. 概要を示す．利用者定義部分の詳細については，並列. 展開途中のノード 集合のデータ表現やその操作. 分枝限定法の場合のみ代表例として示すことにする．. ルーチンは問題領域依存のチューニングが必要と. 並列山登り法 山登り法は探索空間が狭く，単独で用. なる．このため，PopKern はノード 集合を利用. いてもそれほど効率良く解が見つけられないことが. 者定義のデータ型とし，ノード 集合に対して操作. 多い．しかし，暫定解の近傍を高速に探索し，局所. を加えている．. 的な最適解をすばやく見つけることができる．よっ. し たがって，利用者は展開途中のノード 集合の. て，ヒューリスティックに基づいて暫定解を改善し. データ構造を定義する．また，このノード 集合に. ながら探索を進めるアルゴリズムと組み合わせると，. 対して，適当な 1 つのノード を選択して分枝し ，. 暫定解をより早く局所最適解に収束させることがで. 上界/下界チェックを行い，可能ならば枝刈りを行. きるため，効率が大きく向上する．PopKern では，. う，というサブルーチン群を定義する．さらに，. このような組合せによる使用を考え，並列山登り法. 負荷分散のために用いられている，ノード 集合分. を提供している．. 割/結合ルーチンも定義する必要がある．. アルゴリズム. 山登り法では，暫定解の近傍を探索. これらの定義すべきルーチンの役割，およびそ. し，コストが低くなる方向へ解を改善する操作を. の呼び出しの流れについて，疑似コードで示すと. 繰り返す．並列アルゴ リズムは，各 PE に異なる. 図 7 のようになる．[ ] で囲まれた部分が 1 つの. 初期解を設定し，山登りを各 PE で独立して行う，. 利用者定義関数に対応し ，PopKern は図 7 のよ. という手法となっている．山登りで局所最適解に. うな流れで利用者定義関数を呼び出して並列分枝. 収束した場合は，改めて初期解を設定し直し，山. 限定法による探索を行う．. 登りを繰り返す．. なお，図 7 中，[P 中の実現可能解の計算] とあ. 利用者定義部分 利用者は，ランダムに初期解を生. るのは，P がリーフであり，制約条件を満たす解. 成するサブルーチン，暫定解の近傍を探索し，改. として「解ける」場合に解を計算する，という利. 善された解を返すサブルーチンを定義する．. 用者定義ルーチンである．また，利用者が選んだ. 並列分枝限定法 枝刈りを用いて高速に全解探索を行. ノード P について処理を行うルーチンがいくつ. うための手法である．. かあるが，PopKern は，P がどんなノード であ. アルゴリズム. るか関知していない．つまり，P のノードを取り. 分枝限定法は，探索木における探索. 途中のノード の集合について，ノード 集合中から. 出したり，戻したりといった操作は行っていない．. 1 つのノードを選択し，分枝し，上界/下界チェッ クを行い，可能ならば枝刈りを行う，という操作 の繰返しで実現される．. これは，そのような操作は不必要であり，性能を. このアルゴリズムを並列に実行するためには，ノー. あるかを覚えておく必要がある．. 損なうと考えたためである．よって，利用者は自 分のノード 集合中のどのノードが選択した P で. ド 集合を適当に PE 間で分担して探索を行うこと. 並列焼き鈍し 法 焼き鈍し法とは，確率的に解候補を. になるが，枝刈りが行われるため，静的に均等に. 改善していく手法の 1 つである．山登り法と同じよ. 分担させることは難しい．そこで，PopKern は. うに，ある解の近傍を探索し，次の解を生成するの.
(8) 56. Mar. 2001. 情報処理学会論文誌：プログラミング. 異なった温度を設定され，独立して一定温度で焼 並列分枝限定法. き鈍しを続ける，という手法である．隣り合う PE. begin • [初期暫定解を計算する];. は一定周期ごとにお互いの解候補を調べ，もし温 度が高い方の解候補の質が良かった場合は無条件. • [探索のルートとなるノード 集合 L を 作成する]; • LOOPTOP:. に，そうでない場合は温度に対応した確率のもと. • while ([L = ∅]) do begin. て，さらに微妙な改善が施されていくことが期待. に，解候補の交換を行う．この交換により，質の 良い解は温度の低い方の PE へと次第に移動し される．. – マネージャから要求があれば，[ノ ード 集合分割] および [結合]; – 暫定解が更新されていたら，それ. 利用者定義部分 利用者は，ランダムな初期解候補. を反映; – [ノード P ∈ L を選び，下界値評. る，PE の温度分布と解交換周期も定義する必要. 価を行う];. の生成と解候補をランダムに変更するサブルーチ ンを定義する．温度並列アルゴ リズムで用いられ がある．. PE の温度分布と解交換周期という温度並列焼き. – if（下界値 > 暫定解コスト ）then. 鈍し法特有のパラメータは，利用者が普段適用し. goto 枝刈り; – [P 中の実現可能解の計算]; – if P の中の実現可能解が見つかっ. ている「通常の」焼き鈍し法の温度スケジューリ. PE の温度分布は，通常の焼き鈍し法で温度を減. ていた then. 少させるときの時間軸方向の温度分布に相当し ，. 実現可能解を暫定解と比較，コス. 解交換周期は，通常の焼き鈍し法で一定温度下で. トの低い方を新暫定解に ;. 解を変更する長さに相当する．このように，温度. – [P を展開し，L に追加]（ 分枝） ; – [L 中の不要ノード，および P を ; 削除]（ 枝刈り） end;. 並列焼き鈍し法は逐次焼き鈍し法と類似した側面 も持っており，利用者が持つ逐次焼き鈍し法での ノウハウをそれほど失うことなく移行することが できると考えられる．. • マネージャへのノード 集合要求; • 終了指示 or ノード 集合結合を待つ; • if ノード 集合が結合できる then begin – [ノード 集合結合]; – goto LOOPTOP; end; end.. Fig. 7. ングパラメータと同様に決定することができる．. 図 7 分枝限定法の概要 Algorithm of branch and bound.. ま た ，温 度 と 解 の 改 悪 方 向 へ の 変 更 を 受 理 す る 確 率 と の 関 係は ，PopKern が 提 供 す る. popkern_acceptable 関数によって定められてい る．解をランダムに変更する利用者定義ルーチン内 で，解の評価値の変動値を popkern_acceptable に与えると，この関数はその解が置かれている温 度に基づいて解の変更を受理するか否かを決定し， 返り値に示す．当然ながらこの関数は，逐次焼き 鈍し法と同様に，高い温度では改悪方向への解の 変更を受理する確率が高くなるように設定されて いる．. であるが，解のコストが悪くなる方向への移行を確. 並列遺伝的アルゴリズム. 遺伝的アルゴ リズムは，生. 率的に認めている点が山登り法と異なる点である．. 物学的進化を模したシミュレーションを行うことで. アルゴリズム. より優れた解を得ようという手法である．つまり，. 焼き鈍し法では，改悪方向への解候. 補の変更確率のパラメータとして「温度」と呼ば. 解を遺伝子と対応させ，コストの低い解は優秀な遺. れるパラメータを用いており，この温度を徐々に. 伝子であるため生き残りやすいという環境のもとで，. 下げることで効率の良い探索が得られるが，適切. 遺伝子の交配，突然変異を繰り返してより優秀な遺. な温度管理を行うことは難しい．この問題点を回. 伝子が残ることを期待するものである．. 避するために，PopKern は温度並列焼き鈍し法4). アルゴリズム. を採用している．これは，各々の PE はそれぞれ. 遺伝的アルゴ リズムの並列化のため. に，島モデルと呼ばれるモデルを採用する．海で.
(9) Vol. 42. No. SIG 3(PRO 10). 並列組合せ最適化ライブラリ PopKern. 隔てられた島での進化のように，各々の PE は独 立して遺伝子の世代交代を進める．ある一定世代 周期ごとに，PE の遺伝子の一部が他の PE へと 移動し ，元々存在していた遺伝子と混合される． これはちょうど ，動物が島の間を移住したことに 相当する． 利用者定義部分 分枝限定法と同様に，遺伝子集合 のデータ構造は問題領域依存のチューニングの対 象となるため，PopKern は遺伝子の集合をブラッ. Table 1. 57. 表 1 分枝限定法の探索時間（ sec ） The search time of branch and bound (sec).. PE 数 1 2 3 4 5 6 7 8. A12 14.4 3.9 2.7 2.8 2.7 2.7 2.7 2.7. A14 203 71.3 48.8 37.3 39.0 43.8 39.9 39.7. A16 2390 726 512 315 305 308 311 318. B14 2000 372 226 221 187 188 182 197. クボックスとして扱う．よって，利用者はこの遺 伝子集合の型，遺伝子集合を 1 世代だけ世代交代. SPARC 166 MHz × 10 ） ．KLIC システムはバージョ. させるルーチン，および遺伝子集合の分割/混合. ン 3.003．KLIC には，様々な低レベル PE 間通信手. ルーチンを定義する．また，移住が行われる世代. 段のための実装が存在するが，今回の評価はすべて，. 間隔も定義する必要がある．. 4. 実装と評価 4.1 実. 装. 通信路として共有メモリを用いたメッセージパッシン グモデルの実装を使っている． 逐次オーバヘッド. 山登り法を使った巡回セールスマ. ン問題ソルバーに関して，最適解の管理，探索のコ. PopKern は，並行並列論理型言語 KL1 のポータブ ルな処理系である KLIC 5) 上に実装されている．KLIC は KL1 のプログラムを C プログラムに変換して実行. ントロール等の PopKern が提供している機能を，. する．このため，適切に最適化された C コンパイラが. によって並列化されたプログラムの逐次実行時の性. すべて C 言語で逐次記述したプログラムを用意し た．この逐次版の山登り法プログラムと，PopKern. 存在する計算機上ならば，どこでも高い効率で動作す. 能を比較することで，PopKern の基本的なオーバ. ることができる．また，KLIC の並列実装は，共有メ. ヘッドが求められる．. モリ，PVM，MPI 等，多くの通信路上への実装が行. 性能比較は，同一問題，同一乱数列を用いて，ある. われており，大規模並列計算機から，小規模な共有メ. 解が発見されるまでの時間を比較することにより. モリ並列計算機，PC クラスタ等，多くの並列計算環. 行った．実験は 5 回行い，その平均実行時間の比を. 境で実行できる．. 求めた．. KLIC は “ジェネリック・オブジェクト ” と呼ばれ るデータ型を扱うことができる．これは，論理型プロ. その結果，PopKern システムの逐次オーバヘッド は約 1%であった．これは十分小さいといえる．. グラミングの世界に新たなデータ型を加えるための枠. 分枝限定法の速度向上 分枝限定法について，並列計. 組みである．この枠組みを使うことで，手続き的逐次. 算時の速度向上を測定した．. プログラミングを宣言的並行プログラミング中に簡単. 評価に用いたプログラムは，未訪問の都市のそれぞ. に導入することができる．PopKern では，利用者が. れから最近傍にある都市までの距離の総和を求め，. 定義した C 言語による逐次プログラミングのデータ. これと現時点での経路の距離との合計を現時点の部. 構造やその操作ルーチンを，ジェネリック・オブジェ. 分解の上界値とし，分枝限定法の上界評価を行うこ. クトによって KL1 のデータ型に導入している．利用. とで探索の枝刈りを行っている．また，探索ノード. 者定義部分はすべてジェネリック・オブジェクトにカ. のスケジューリングは，深さ優先である．別の PE. プセル化され，PopKern システムは完全に KLIC の. へ移動するために探索ノード 集合を分割する際には，. データ型として扱っている．したがって，通信や同期. 未探索のノード のうち探索が最も進んでいない（す. は KLIC のシステムにより，他の KLIC のデータと. なわち一番浅い）ものを移動することとした．ただ. 同様に扱われている．. し，探索木の末端から一定の閾値以下の深さしかな. 4.2 予備的評価. いノードは移動しないこととし，探索の粒度を一定. 巡回セールスマン問題を解く比較的単純なプログラ. 以上に保っている．なお，評価に使用する問題は，. ムを使って，PopKern ライブラリが提供する 4 種類の. TSPLIB 6) より選択した．. アルゴリズムすべてについて，予備的な評価を行った．. 表 1 に，すべての経路を探索して最良解を見つける. 評価環境は SUN Ultra Enterprise E/4000（ Ultra. までの実行時間を示す．実行は 3 回行い，その平均.
(10) 58. Fig. 8. 情報処理学会論文誌：プログラミング. 図 8 分枝限定法の台数効果 The speedup of the branch and bound algorithm.. 図 10 Fig. 10. Mar. 2001. 単位時間あたりに展開されたノード 数の変化 Number of nodes created per unit time.. B14 のように大きな台数効果が得られている問題 は，1∼3 PE の領域で展開されたノード 数も大きく 減っており，高速化の原因が枝刈りによるものであ ることが読み取れる．ただし，探索木のノード の展 開順をつねに適切なものに設定することは難しいた め，今回の評価プログラムの速度向上も十分意味の ある並列効果であるといえる． また，実際に行われた計算量に近い指標として，単 位時間あたりに展開されたノード 数の変化を図 10 図9 Fig. 9. に示す．ここでは，1 PE での展開ノード 数を 1 と 展開されたノード 数の変化 Number of created nodes.. している．どの問題においても，4∼5 PE 程度まで 高い並列性能を示している．なお，その後性能が横. をとってある．A12，A14，A16，B14 は異なった都. ばいになる傾向が見られるが，これは通信コストに. 市配置の巡回セールスマン問題を表している．A12. 対する問題の大きさが小さいためであり，PopKern. は 12 都市，のように末尾の数字は都市数であり，A. システムの限界ではない．これは，後述するより大. から始まるものは TSPLIB の問題 bayg29 の先頭. 規模な評価で示す．. の都市を必要な数だけ残したもの，B14 は TSPLIB. ところで，今回評価対象とした問題は，その探索空. の問題 burma14 となっている．. 間の規模が非常に大きく異なっているにもかかわら. 図 8 は実行時間の台数効果である．探索にかかった. ず，どれもほぼ同様の PE 数で並列化効率が最大と. 実行時間について，1 PE での実行時間と複数 PE で. なっている．これは，今回評価に用いたプログラム. の実行時間の比を台数効果とした．. の並列計算の粒度が問題にかかわらず一定であった. 図 8 に示されるように，このテストプログラムは. ことに起因すると考えられる．並列実行時の効率は，. 非常に高い台数効果が得られている．4∼5 PE 以下. 負荷のアンバランスが起きずかつ通信のオーバヘッ. の領域では，スーパリニアな速度向上が 4 つの問題. ドが大きくならないように探索を分割したときに最. すべてにおいて認められる．これは，逐次実行時の. 大になる．これは，並列計算の粒度，すなわちノー. チューニングが不十分で，探索木のノード の展開順. ド 集合の分割単位の大きさによって決定される．現. が適切なものでなかったためと考えられる．ノード. 在，粒度は利用者がノード 集合分割方法によって定. の展開順は枝刈りの効率に大きな影響を与える．PE. めている．粒度は，使用可能プロセッサ数，計算速. 数が増えることで，より質の良い解が早い段階で見. 度と通信速度の比によって適切に調整できると考え. つかり，枝刈りが効率良く行われたため，探索時間. られるので，PopKern システムが利用者に，これ. が大幅に短縮されたと考えられる．これは，図 9 に. らの要素によって計算される何らかの粒度の目安と. よって確認される．図 9 は，探索時に展開された. なる情報を提供することができれば，より効率の良. ノード 数の変化を表している．1 PE での探索時の. い戦略を利用者がとる大きな手助けとなると考えら. 展開ノード 数を 1 とし ，比をとって示されている．. れる．.
(11) Vol. 42. No. SIG 3(PRO 10). 並列組合せ最適化ライブラリ PopKern. 図 11 焼き鈍し法の解候補改善過程 Fig. 11 Improvement of solution candidates of the simulated annealing.. 焼き鈍し 法の速度向上 評価プログラムでは，ランダ. 59. 図 12 焼き鈍し法における単位時間あたりの近傍探索回数 Fig. 12 The number of neighbour search of SA per unit time.. た残りの部分は，並列動作によって生じる通信オー. ムに選択した 2 都市の訪問順を入れ替えることで，. バヘッドや負荷のアンバランスといった部分による. 暫定解の近傍の解を生成し，焼き鈍し法を行う．使 用 PE 数にかかわらず，つねに 32 の温度帯を使っ. 速度低下であると考えられる．特に，3 PE および 5∼7 PE での実行時に単位時間あたり計算量が落ち. て温度並列焼き鈍し法を行っている．PE 数 1 の場. ているのは，32 温度帯を PE 数でうまく割りきれ. 合は 1 PE で 32 温度分の焼き鈍しを，PE 数 8 の場. なかったため，負荷にアンバランスが生じているた. 合は 1 PE あたり 4 温度分の焼き鈍しを行う，とい. めである．. う方式である．隣の温度帯との解の交換周期は暫定. 結論として，PopKern の並列焼き鈍し法ライブラ. 解 1000 変更ごととした．また，山登り法との併用. リは，十分な性能を出したといえる．. も行っている．つまり，ランダムに生成した近傍の. 遺伝的アルゴリズムの速度向上 評価プ ログ ラ ムで. 解が一定回数だけ連続して不受理とされると，山登. は，巡回セールスマン問題を遺伝子表現するため. り探索を試みるのである．. の手法として，Grefenstette らによる方法7)を用い. なお，評価結果として示している解改善速度はそれ. た．以下に簡単にその手法を説明する．. ほど速いものではない．これは，ランダムな近傍の. 1 から N までの都市をある適当な順序で. 解の生成や山登り探索に用いている手法の探索範囲. 並べたリスト W を用意しておく．今，ある. が非常に狭いためであることに留意されたい．. 巡回経路が (c1 . . . cN ) という順序で都市を. 図 11 は，焼き鈍し法の探索で解がどのように改善. 訪問するとき，i 番目に訪問する都市 ci が，. されていったかという過程を示すため，その時点で. 未訪問都市のリスト W −{c1 , . . . , ci−1 } の. 発見されている最良解のコスト（巡回セールスマン. 何番めの都市であるかを調べ，これを li と. 問題では巡回経路長）を，実行 PE 数ごとにプロット. する．li は 1 ≤ li ≤ N − i + 1 の範囲の整. したものである．使用した問題は TSPLIB の a280. 数となる．このリスト L = (l1 . . . lN ) を. （ 都市数 280 ）である． 図 11 に示されるとおり，解の改善は PE 数が増え るほどより早い時点でコストの低い解が見つかって. 遺伝子として，遺伝的アルゴ リズムを実行 する． この方法を用いると，遺伝子はつねに実現可能な正. おり，並列計算の効果が現れている．また，より計. 当な巡回経路と 1 対 1 に対応し，2 つの遺伝子をあ. 算量を正確に表す指標による評価として，単位時間. る長さの点で切り取り入れ替えるという単純な交叉. あたりの暫定解近傍探索回数を求め，全温度帯につ. が行える．また，突然変異についても，遺伝子中の. いてその総和をとったものを図 12 に示す．1 回の. ある要素 li を li ∈ {1, . . . , N − i + 1} で置き換え. 暫定解の近傍探索操作がほぼ同じ計算量ならば，こ. ることで実現できる．. の指標はライブラリ全体の単位時間あたり計算量を. 今回の評価プログラムでは，この方法を用い，1 点. 正しく示すと考えられる．. 交叉による交叉演算と 1 要素の突然変異を行った．. 8 PE で 6 倍程度の計算が行われており，高い台数効 果が得られている．リニアな速度向上に達しなかっ. また，隣の PE へと移住する遺伝子は，遺伝子集合 からランダムに 16 個を選び，それらが無条件に隣.
(12) 60. 情報処理学会論文誌：プログラミング. Mar. 2001. の PE に受け入れられるものとした． ここで，遺伝子集合のサイズの異なる 2 つの方式を 評価することにした． 「 個別プールサイズ一定」方式 と「プールサイズ合計一定」方式の 2 種類である． 「個別プールサイズ一定」方式は，1 PE あたりの遺 伝子集合のサイズを一定とする方式である．つまり，. PE 数が増えるとそれに比例して遺伝子集合のサイ ズが大きくなることになる．これは，一定のメモリ を持つ複数の PC をネットワークでつないだ，PC クラスタ上での使用を想定した評価に相当する．こ こでは 1 PE あたり 64 の遺伝子を扱うことにした． また，1 回の世代交代で交叉を行う遺伝子数，およ. 図 13. 遺伝的アルゴ リズム（個別プールサイズ一定方式）の 解候補改善過程 Fig. 13 Improvement of solution candidates of GA (local pool size is constant).. び突然変異が起きる遺伝子数はそれぞれの PE で一 定とした． 「プールサイズ合計一定」方式は，全 PE の遺伝子 集合の合計サイズを一定にする方式である．PE 数 が増えると，遺伝子集合は PE 数で均等に分割され る．これは，共有メモリを持つ並列計算機上での使 用を想定した評価に相当する．ここでは遺伝子集合 の合計サイズを 512 とした．したがって，8 PE で 並列動作すると 1 PE あたり 64 の遺伝子を扱うこ とになる．また，1 回の世代交代で交叉を行う遺伝 子数，および突然変異が起きる遺伝子数の全 PE で の合計も一定とする．つまり，1 PE では 8 PE での 動作と比較して，8 倍の遺伝子集合中，8 倍の遺伝 子を交叉演算し，8 倍の遺伝子を突然変異させる．. 図 14. Fig. 14. 個別プールサイズ一定方式 GA の 単位時間あたり世代交代数 Number of generations per unit time (local pool size is constant).. なお，巡回セールスマン問題に対応し た遺伝子表 現や，交配する際の演算の工夫は広く研究されてい. ことにした．1 PE あたりの遺伝子集合の大きさ. る8)が，ここでは比較的単純な手法を用いて評価を. が一定であるので，1 PE の世代交代にかかる計. 行っている．結果に見られる解の改善速度が遅いの. 算コストがほぼ等しいと考えられ，この指標で単. はこのためであることに留意されたい．. 位時間あたりに実行された計算量を見積もること. 個別プールサイズ一定方式による評価 個別プール. ができる．. サイズ一定方式について，遺伝的アルゴ リズム. この指標をプロットしたものを図 14 に示す．ほ. の探索での解の改善過程をプ ロットし たものを. ぼ理想的な並列効果が現れている．このことから，. 図 13 に示す．評価問題は焼き鈍し法のときと同. 並列動作時のシステムのオーバヘッド 等は十分小. じ，TSPLIB の a280（ 都市数 280 ）である．. さく，PopKern は十分な性能を示したといえる．. 図 13 を見ると，PE 数を増やすほど よりコスト. プールサイズ合計一定方式による評価 プールサイ. の低い解が早い段階で見つかっていることが読み. ズ合計一定方式について，遺伝的アルゴ リズム. 取れる．. の探索での解の改善過程をプ ロットし たものを. この評価プログラムの場合，遺伝子集合の大きさ. 図 15 に示す．評価問題は焼き鈍し法のときと同. が変化しているため，総計算量も使用する PE 数. じ ，TSPLIB の a280（ 都市数 280 ）である．や. によって変化しており，理論上どのような速度向. はり PE 数を増やすほど解改善がすばやく行われ. 上が解改善過程に現れるはずであるかは一概にい. るようになることが読み取れる．. えない．そこで，単位時間あたりの計算量を正し. この評価プログラムの場合，交叉演算の対象とな. く見積もるための指標として，すべての PE につ. る遺伝子の選び方が変化したり，島モデルをとる. いて単位時間あたりの世代交代回数の総和をとる. ことによる遺伝子の移動の仕方が変化したりする.
(13) Vol. 42. No. SIG 3(PRO 10). 並列組合せ最適化ライブラリ PopKern. 61. 4.3 2 次割当問題による分枝限定法の評価 本パッケージの想定する，問題領域依存のチューニ ングを十分に行ったプログラムの並列化による評価と して，品野，藤江による 2 次割当問題求解プログラ ム9)を用いることとした．. 2 次割当問題とは，2 つの n × n 行列 F = (Fij )，. D = (Dij ) が与えられたとき， min. π∈Sn. 図 15. 遺伝的アルゴ リズム（プールサイズ合計一定方式）の 解候補改善過程 Fig. 15 Improvement of solution candidates of the GA (total pool size is constant).. n n . Fπ(i)π(j) Dij. i=1 j=1. を求めるものである．ここで，Sn は {1, . . . n} 上の 置換集合である． 今回，分枝限定法によって厳密解を求めるプログラ ムを PopKern 上に移植した．移植した元プログラム のとっていた解法の概略は，以下のとおり．. • 初期解 Taillard 10)によって提案された robust taboo search を用いていた．. • 下界値の計算 Gilmore-Lawler bound 11),12)を用いていた．すな わち，i, j = 1, . . . , n に対し，Lij を. Lij ≡ 図 16. Fig. 16. プールサイズ合計一定方式 GA の 単位時間あたり世代交代数 Number of generations per unit time (total pool size is constant).. ため，速度向上が解改善過程にどのように現れる. min. π∈Sn ,π(j)=i. n . Fiπ(k) Djk. k=1. と計算して求め，行列 L = (Lij ) に関する線形割 当て問題の最適値を求めるものである．. • 分枝方法 「 π(i) = 1, π(i) = 固定されていない添字 i を選び， 2, . . . , π(i) = n 」または「 π(1) = i, π(2) =. はずであるかはやはり一概にいえない．そこで，. i, . . . , π(n) = i 」と n 個の子問題を生成する．この. 個別プールサイズ一定方式と同様に，単位時間あ. とき，行列 L に関する割当て問題の最適解の情報. たりの世代交代回数を計算量の指標として測定し. や，行列 F ，D の対称性等の情報を利用して無駄. た．この方式の場合，遺伝子集合の全サイズが一. な分枝を省いていた． • 子問題の探索. 定であるので，すべての PE の世代交代回数の平 均をとれば，単位時間あたりに実行された計算量 この指標をプロットしたものを図 16 に示す．や. 深さ優先探索を適用していた． 3500 行程度の元プログラムの移植作業は約 7 人日 を要した．実行時間の測定は，QAPLIB 13) のベンチ. はりほぼ理想的な並列効果が見られている．なお，. マーク問題を用いて行った．また，実行環境として，. を正しく見積もることができる．. PE 数 3，および PE 数 5∼7 の場合にリニアな速. 共有メモリ型並列計算機と，PC をネットワーク接続. 度向上とずれを生じているのは，交叉を起こす遺. したクラスタ環境の 2 通りを用いて評価を行った．. 伝子数や突然変異を起こす遺伝子数が PE 数でう. 共有メモリ型計算機環境における評価 用 い た 計 算. まく割りきれず，負荷のアンバランスが生じるか. 機環境は巡回セールスマン問題の評価時と同じも. らである．. のである．探索時間を表 2 に示す．この探索時間は，. このとおり，プールサイズ合計一定方式の評価で. すべて対称性による枝刈りを行わない場合の結果で. も，本システムは十分な性能を示した．. ある．original が元々のプログラムを逐次実行した ときの探索時間である．1 PE での実行時間は若干.
(14) 62 表2. Mar. 2001. 情報処理学会論文誌：プログラミング 2 次割当問題，共有メモリ型計算機環境の探索時間（ sec ） Table 2 The search time of QAP on shared memory machine (sec). PE 数 original 1 2 3 4 5 6 7 8 9 10. nug15 212 229 117 78 60 48 41 35 31 28 26. nug16a 863 924 460 309 233 188 157 135 119 106 97. nug16b 1556 1588 799 580 429 321 270 232 202 180 164. 表 3 2 次割当問題，PC クラスタ環境の探索時間（ sec ） Table 3 The search time of QAP on PC cluster (sec).. PE 数 original 1 2 3 4 5 6 7 8. nug15 78 78 26 18 15 11 11 11 13. nug16a 316 318 91 74 54 54 44 34 44. nug16b 575 575 224 154 115 93 81 77 75. nug17 1738 1744 762 447 323 246 211 202 208. 表 4 2 次割当問題，PC クラスタ環境の展開ノード 数 Table 4 Number of nodes of QAP on PC cluster.. PE 数 original 1 2 3 4 5 6 7 8. nug15 292277 292277 186998 194409 213675 194060 233746 248277 257804. nug16a 1066193 1066193 595927 734335 702543 897722 872069 761803 798369. nug16b 1040923 1040923 1523339 1541731 1556417 1555255 1617293 1808268 1672530. nug17 5120744 5120744 4545393 3994108 3844748 3635620 3722881 4189867 4109164. 図 17 共有メモリ環境，2 次割当問題の速度向上 Fig. 17 The speedup of QAP (shared memory).. オリジナルより長くなっているが，この PopKern のオーバヘッドは大きいものでもおよそ 8%であり， 並列実行による速度向上で十分埋め合わせられるも のであることが分かる． また，オリジナルプログラムと PopKern を使用し た実行時間の比を図 17 に示す．ほぼ理想的な速度 向上を示している．. PC クラスタ環境における評価 100Base-TX で 8 台 の PC を接続した PC クラスタ環境での評価を行っ た．PC は Celeron 333 MHz，メモリ 128 MB，通. 図 18 PC クラスタ環境，2 次割当問題の速度向上 Fig. 18 The speedup of QAP (PC cluster).. ものであった．. 信ライブラリとして PVM ver.3.4.3 をインストー. 図 18 が示すように，どの問題についても高い並列. ルし ，KLIC ver.3.003 は通信路に PVM のみを用. 性能が得られている．また，問題の規模が大きくな. いる版を使用した．. るに従って並列実行性能は向上し，十分大きな問題. 探索時間を表 3 に示す．また，展開されたノード 数. ではほぼ理想的な速度向上が得られていることが読. を表 4 に示す．これらをもとに，展開されたノー. み取れる．. ド 数が一定な場合の実行時間を求め，オリジナルの. なお，どの問題でも 8 PE での並列性能が落ちてい. プログラムの速度を 1 として示したものが図 18 と. るが，これは KLIC がワーカ PE に加えて管理 PE. なる．. を 1 つ立ち上げることによる．すなわち，8 PE の. PC クラスタ環境においては，オリジナルと Pop-. ワーカを立ち上げるとき，KLIC システム全体では. Kern を用いて 1 PE で動かしたたときの実行速度 の差は 1%以下であり，オーバヘッドは十分小さな. 9 個のプロセスが立ち上がり，PVM がこれらを 8 個のプロセッサに分担させるときに，2 つのワーカ.
(15) Vol. 42. No. SIG 3(PRO 10). 並列組合せ最適化ライブラリ PopKern. 63. PE を 1 つのプロセッサ上で動かしてしまうためで. たが，実際にはごくわずかなオーバヘッドで収まって. ある．. いる．これは，実行時間のほとんどの部分が利用者が. 2 次割当問題による評価のまとめ 2 次割当問題は広 く研究されており，ヒューリスティクスに基づく初 期解の質は非常に良い．この評価プログラムに採用. するという今回の設計でも，並列実行による性能向上. された robust taboo search が導出する初期解も非. は十分に得られている．よってこれらの評価より，今. 常に良質で，今回評価に用いた問題ではすべて初期. 回提案したライブラリの設計，すなわち，問題領域依. 定義したプログラム部分であることによる．また，並 列化アルゴ リズムのフレームワークの部分だけを提供. 解がそのまま最良解であった．このため，分枝限定. 存の利用者定義データ構造を問題領域独立な並列化ア. 法の探索途中では，枝刈りができる枝は完全に枝刈. ルゴ リズムのフレームワークにプラグインする，とい. りされ，無駄な探索がまったく発生しない．これは，. うライブラリ構造は，問題領域依存知識の活用を重視. どのように探索ノードの分割を行っても同じである．. しながらかつ高い並列実行効率を得られる枠組みとし. よって，負荷のアンバランスが生じなければほぼ理. て適したものであると結論することができる．. 想的な並列効果が期待できる．これを示したのが共. また，2 次割当て問題を解くプログラムの移植作業. 有メモリ環境での評価結果であった．共有メモリ環. について，プログラムの大きさに対して PopKern へ. 境では，CPU の計算能力に対して通信能力が比較. の移植にかかった作業量はそれほど 大きくなかった．. 的高く，負荷のバランスがとりやすい環境といえる．. これにより，今回提案したライブラリの設計は，問題. このとき，図 17 に見られるように速度向上は理論. 領域依存部分の記述の自由度を下げることなく，しか. 値に非常に近く，高い性能を示していた．. も記述しやすい枠組みを持っているといえ，基本設計. 一方，PC クラスタ環境の場合，通信能力が若干低. の妥当さが確かめられた．. いものとなる．そのため，図 18 のように，小さな問 題については共有メモリ環境ほどの性能は得られな. 5. まとめと展望. い．しかし，大規模問題においては，このように特. 本論文では，最初に，既存の並列組合せ最適化ラ. 別なハード ウェアを用いない安価な並列計算環境で. イブラリが問題領域依存のチューニング能力を持って. あっても満足のいく性能が得られることが示された．. いないことを論じた．我々は十分な問題領域依存の. また，共有メモリ型計算機環境と PC クラスタ環境. チューニング能力を持つ並列ライブラリ・パッケージ. の 2 つでプログラムを実行しようとした際，当然な. である PopKern を開発した．PopKern は，探索のた. がらユーザのプログラムはまったく手を加える必要. めに必要となるデータ構造やそれを扱うサブルーチ. がなく，PopKern をそれぞれの環境に合わせてイ. ン群をユーザ定義とし，代表的な組合せ最適化アルゴ. ンストールし，コンパイルし直すだけでそれぞれの. リズムの並列実行をコントロールする PopKern カー. 環境で実行することができた．当然といえば当然で. ネル部にユーザ定義部分をプラグインすることで，高. あるが，これは大きな利点である．. いチューニング能力を実現した．また，評価の結果，. 4.4 評価のまとめ. PopKern は領域依存知識を用いてチューニングされ. 巡回セールスマン問題による各アルゴ リズムの評価. たプログラムの性能を損なうことなく適用することが. が示すとおり，PopKern の逐次オーバヘッド はご く. でき，大規模問題において，並列実行時には高い性能. 小さい．しかもその並列性能は高く，すべてのアルゴ. を得られることが示された．. リズムにおいてほぼ理想的な並列処理が行われた．こ. PopKern は広い問題領域への応用が可能な柔軟な. のことから，PopKern の基本性能は高く，利用者が並. 構造を持つ．今後，より広大な探索空間，より複雑な. 列化ライブラリとして使用するときに適切なプログラ. 制約条件，そしてより効率的な問題領域依存のチュー. ミングを行えば十分な性能が得られることが確認され. ニング技法を持つような産業的実問題への応用をは. た．また，問題領域依存知識を十分に活用したプログ. かり，システムの本格的評価を充実させたいと考えて. ラムである 2 次割当て問題による評価において，並列. いる．. 処理による速度向上もほぼ理想的であり，大規模な問. PopKern の発展として，2 つの方向性がある．1 つ. 題に対しても問題領域依存知識を活かして PopKern. は利用者の使い勝手を向上させる方向である．解の探. が適用できることが示された．. 索状況を表示し，対話的に探索をコントロールできる. 今回の実装では並列処理系として KLIC を使ってお. ような GUI の装備等を考えている．もう 1 つは並列. り，そのためある程度のオーバヘッドが予想されてい. 探索アルゴ リズムの拡充による適用問題領域の拡大で.
(16) 64. Mar. 2001. 情報処理学会論文誌：プログラミング. ある．たとえば，ゲームプログラミングで必要とされ るミニマックス木の探索アルゴ リズムを提供すること を考えている． 謝辞 三菱総合研究所の藤瀬哲朗氏には PopKern の実装時に多くのご助力をいただきました．また，東 京農工大学の品野勇治先生には評価に関して多大なご 助言をいただきました．ここに深謝いたします． なお，本研究の一部は情報処理振興事業協会の先端 的情報化推進基盤整備事業「組合せ最適化問題のため の汎用並列処理パッケージの技術開発」プロジェクト において実施された．. 参 考 文 献 1) Br¨ ungger, A., Marzetta, A., Fukuda, K. and Nievergelt, J.: The Parallel Search Bench ZRAM and its Applications, Annals of Operations Research: 90, pp.45–63, Baltzer Science Publisher (1999). 2) Argonne National Laboratory: PGAPack Parallel Genetic Algorithm Library (1998). http://www-fp.mcs.anl.gov/ccst/research/ reports pre1998/comp bio/stalk/pgapack.html 3) Bubak, M., Ciesla, W. and Sowa, K.: ObjectOriented Library of Parallel Genetic Algorithms and its Implementation on Workstations and HP/Convex Exemplar, Proc. Int. Conf. High Performance Computing and Networking, LNCS, Vol.1225, pp.514–523, Springer-Verlag (1997). 4) Kimura, K. and Taki, K.: Time-homogeneous Parallel Annealing Algorithm, Technical Report 673, ICOT (1991). 5) Chikayama, T.: KLIC: A Portable Parallel Implementation of a Concurrent Logic Programming Language, Parallel Symbolic Languages and Systems, LNCS, Vol.1068, pp.286– 294, Springer-Verlag (1995). 6) Reinelt, G.: TSPLIB – A Traveling Salesman Problem Library, ORSA Journal on Computing, Vol.3, No.4, pp.376–384 (1991). http://www.iwr.uni-heidelberg.de/iwr/ comopt/software/TSPLIB95/ 7) Grefenstette, J.J., Gopal, R., Rosmaita, B.J. and Gucht, D.V.: Genetic algorithms for the traveling salesman problem, Proc. 1st International Conference on Genetic Algorithmsand. their Applications, Grefenstette, J.J. (Ed.), pp.160–168, Pittsburgh, PA, Lawrence Erlbaum Associates (1985). 8) 三宮信夫ほか（ 著 ），シ ステ ム制御情報学会 （ 編） ：遺伝的アルゴ リズムと最適化，朝倉書店 (1998). 9) 品野勇治，藤江哲也：PUBB による PC クラス タ環境における並列分枝限定法，京都大学数理解 析研 講究録 特定領域研究（ B ）新しいパラダ イ ムとしてのアルゴ リズム工学：計算困難問題への 挑戦『アルゴ リズム工学』平成 11 年度全体会議 講演集 (1999). 10) Taillard, E.D.: Robust taboo search for the quadratic assignment problem, Parallel Computing, Vol.17, No.4–5, pp.443–455 (1991). 11) Gilmore, P.C.: Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem, Journal of the Society for Industrial and Applied Mathematics, Vol.10, No.2, pp.305–313 (1962). 12) Lawler, E.L.: The Quadratic Assignment Problem, Management Science, Vol.9, pp.586– 599 (1963). 13) Burkard, R.E., Karisch, S.E. and Rendl, F.: QAPLIB – A Quadratic Assignment Problem Library, Journal of Global Optimization, Vol.10, pp.391–403 (1997). http://www.imm.dtu.dk/˜sk/qaplib/ (平成 12 年 7 月 14 日受付) (平成 13 年 1 月 22 日採録) 横山 大作（ 学生会員）. 1974 年生．2000 年東京大学工学 系研究科情報工学専攻修士課程修了． 同年 4 月より同大学院博士課程在 学中．. 近山. 隆（ 正会員） 1977 年東京大学卒業．1982 年同 大学院博士課程修了．工学博士．同年 より第五世代コンピュータプロジェ クトに参加．1995 年より東京大学． 現在同大学新領域創成科学研究科 教授．.
(17)
図
+5
関連したドキュメント
"A matroid generalization of the stable matching polytope." International Conference on Integer Programming and Combinatorial Optimization (IPCO 2001). "An extension of
The performance of scheduling algorithms for LSDS control is usually estimated using a certain number of standard parameters, like total time or schedule
We present the new multiresolution network flow minimum cut algorithm, which is es- pecially efficient in identification of the maximum a posteriori (MAP) estimates of corrupted
In this paper, taking into account pipelining and optimization, we improve throughput and e ffi ciency of the TRSA method, a parallel architecture solution for RSA security based on
We present the new multiresolution network flow minimum cut algorithm, which is es- pecially efficient in identification of the maximum a posteriori (MAP) estimates of corrupted
節点領域辺連結度 (node-to-area edge-connectivity), 領域間辺連結度 (area-to-area edge-connectivity) の問題. ･優モジュラ関数
I Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf: Exponential Lower Bounds for Polytopes in Combinatorial Optimization. Gerards: Compact systems for
Karzanov: Minimum 0-extensions of graph metrics, Europ.. Metric relaxation (Karzanov
