Grid環境に適した並列組み合わせ最適化システムの提案 秋山 智宏*1, 中田 秀基*2*1, 松岡 聡*1*3, 関口 智嗣*2 *1東京工業大学 *2産業技術総合研究所 *3国立情報学研究所

発表の概要 組み合わせ最適化問題について 並列最適化システム jPoP 遺伝的アルゴリズム用クラス群 jPoP-GA まとめと今後の課題 提案するシステムの対象となる組み合わせ最適化問題について述べる 提案するシステムについて述べる 最適化アルゴリズムの一つである遺伝的アルゴリズムを 本システムで実装したものについて述べる 最後にまとめと今後の課題について述べる

はじめに 組み合わせ最適化問題 Gridとの親和性 Grid上で組み合わせ最適化問題を解く研究が多く行われている。 多次元パラメータ関数の最適値を求める スケジューリング, 設計問題, 生産計画,バイオインフォマティクスなどの実社会においての応用範囲が広い Gridとの親和性 実社会で求められる問題を解くには膨大な計算量が必要 自明な並列性が大きく、実行粒度の調整が容易 Grid上で組み合わせ最適化問題を解く研究が多く行われている。 はじめに、 組み合わせ最適化問題とは。。。 であり、また、。。。といった特徴をもつためGridとの親和性が高いと考えられており、 Grid上でこれらの問題を解く最適化アプリケーションの研究が多く行われている。

Grid RPC によるGrid化 Grid RPC システム Ninfによる最適化アプリケーションの実装 BMI固有値問題[01,合田ら] 半正定値計画問題(SDP)[01,藤沢ら] タンパク質構造決定[小野] 既存のGrid RPC システムを用いることで、以下のような負担が軽減される セキュリティ データのマーシャリング リソースの選択 その研究のひとつとして、GridRPCを用いた最適化アプリケーションのGrid化があげられる これはGridRPCシステムであるNinfを用いて 。。。などの問題を解く研究がなされており、実行時間の短縮や適用問題の大規模化などといった結果が報告されている このような既存のGridRPCシステムを用いることによって、。。。といったユーザの負担が削減される 2001-HPC-86-6：広域分散コンピューティング環境における数理計画ソフトウェア SPDA，藤沢ら］ 半正定値計画問題（SemiDefinite Programming：SDP）は，線形計画問題（LP）や凸二次計画問題などを含んだより大きな凸計画問題の枠組みである．しかしながら，制約は半正定値制約という非線形制約である． SDP は主双対内点法を用いることで多項式時間で最適解を導くことが可能である． SDP は組合せ最適化，制御分野，構造最適化，データマイニングなどに応用できる． SDPA（SemiDefinite Programming Algorithm）は SDP を解くためのソフトウェア． 非凸二次最適化問題（NQP）に対して逐次半正定値計画緩和法を適用する．逐次半正定値計画緩和法では，１反復の中で複数の SDP 緩和問題を解く必要がある．この部分を，Ninf RPC を用いて非同期に解かせる． 128 CPU のクラスタを用いて，90/128 程度の効率が得られている．

問題点 既存のGrid RPC システムを用いた場合でも、以下のような問題が残る プログラムを記述する煩雑さ アルゴリズム、同期、負荷分散・・・ 並列度のスケーラビリティの獲得が困難 マスター・ワーカー方式ではマスターに負荷が集中してボトルネックとなり、並列性に限界 数台～数十台→数百台～数千台へのスケールアップ 低いポータビリティ 各々の環境でのプログラムのコンパイル しかし、以下のような問題が依然として残っている。 まず、アルゴリズムや同期、負荷分散などといったことを考慮したプログラムの煩雑さ、既存の手法では1つのマスタに対し複数のワーカーといったマスター・ワーカー形式をとった実装が多く、この場合、マスタに通信などの負荷が集中し、マスタがボトルネックとなり並列性に限界が生じてしまい、スケールアップが難しいといった点、 Grid環境下ではサイトによってアーキテクチャやOSが違うので実行する環境ごとプログラムをコンパイルし、ロードしなければならない点

関連研究 PopKern[01, 横山] MW(Master-Worker)[00, J.-P.Goux] 並列組み合わせ最適化ライブラリ CとKLICで実装 →ポータビリティが低い, 計算機のヘテロ性に対応してない MW(Master-Worker)[00, J.-P.Goux] Grid上でマスター・ワーカー形式のアプリケーションを容易に実行するためのフレームワーク Condorをリソース管理に使用 →ユーザは最適化アプリケーションを全て実装しなければならない クラスタ上やGrid上で組み合わせ最適化問題を解くためのシステムとして。。。があげられるが。。。。

jPoP Grid環境に適した並列最適化システム アルゴリズムのみを記述することでGrid上で最適化アプリケーションが実装, 実行可能 並列・分散実行を隠蔽 問題が持つ階層構造を利用した制御 プラットフォーム独立 Java言語でプログラムを記述 標準的なGrid技術を使用 Grid上のリソースの選択 高いセキュリティをもった通信、リソースの保護 そこで本研究ではGrid環境にてきした並列最適化システムjPoPを提案する。このシステムをもちいることで、ユーザは。。。 これはJPOPが。。。 また、実装や、ユーザが記述するプログラムがjavaで記述されているので様々な環境での実行が可能となっている 当然、Grid。。。

object passing library jPoP アーキテクチャ 最適化アルゴリズムのテンプレート(抽象クラス) アルゴリズムに特化したデータの構造・操作のシグネチャを定義 エンジン部 テンプレートを操作し、アルゴリズムの解法を実行 Object Passing 通信ライブラリ 階層制御を実現 algorithm template engine object passing library Jojo Java VM ・・・ user program 次にこのJPOPのアーキテクチャについて述べます。 図のようなモジュールから構成されており、 。。。

実行環境 サイト間通信 Secure Shell (ssh) Grid Security Infrastructure (GSI) Global address 131.112.x.xxx site C site A WAN JPOPは以下のようなクラスタオブクラスタを実行環境を想定している 各サイトにはクラスタがあり、そのうちの一つはグローバルなアドレスを持ったマスタノードが存在します。このノードを介してサイト内のローカルアドレスしか持たないノード群にジョブが割り当てられる 各サイト間やユーザのプログラムを実行するクライアントノード間は 。。。といった安全な通信で行われる。 Local address 192.168.x.1 ～ 192.168.x.8 user site B

jPoP の実行の様子 Engine Jojo Engine Jojo Cluster node Master node user user program Engine Client node Jojo user program 次にこのような環境におけるJPOPの実行の様子について述べます。 ユーザは図のような自分が記述したプログラム、エンジン部、JOJOなどを実行するクライアントノードに置く。ユーザがJPOPを実行することで、 グローバルなアドレスを持つマスターノードに対して、通信ライブラリであるJOJOをアップロードします。マスタノーノードはサイトローカルなクラスタノードに対し、JOJOをアップロードし通信路を確保します次に、クライアントノードからマスタノードに対して、エンジン部がアップロードされ、。。。最後に、ユーザプログラムがアップロードされ。。。 また、マスタとノードからなるサイト内では。。。といったリソースの保護が行われます。 これが実行の様子です。次にJPOPのそれぞれのコンポーネントについて述べる Engine サイト内のリソースの保護 サイト内で認証されたユーザのコードのみ実行 セキュリティマネージャの設定 Java ではクラスローダ別に設定可能 Jojo

テンプレート 各アルゴリズムのフレームワークを与える 遺伝アルゴリズム 分枝限定法 焼き鈍し法 アルゴリズムに依存したクラス群 ユーザはテンプレートクラスを実装 遺伝アルゴリズム 個体, 評価環境, プール 分枝限定法 ノード集合, 評価環境 焼き鈍し法 レプリカ, 評価環境 algorithm template engine object passing libray Jojo Java VM ・・・ user program

エンジン部 ユーザが記述したテンプレートクラスの実装を実行 アプリケーションプログラマから並列実行, 通信, 同期を隠蔽 ・・・ user algorithm template engine object passing libray Jojo Java VM ・・・ user program

Object Passing 通信ライブラリ Jojo 階層的な計算機構成を前提としたライブラリ 各ノード上のコードは自分の親ノード, 子ノード, 兄弟ノードと通信可能 通信単位はオブジェクト一つ 高度な通信機構を記述可能 階層ごとのSPMDプログラミングモデル 各階層内部では同一のコードを実行 階層間では異なるコードを実行 (同一のコードでも可能) algorithm template engine object passing libray Jojo Java VM ・・・ user program descendant sibling ascendant 親ノード ascendant 子ノードdescendant 兄弟ノードsibling

Jojoの通信モデル メッセージ受信ハンドラ ３つのタイプの通信形式 オブジェクトの受信に伴い、自動的に新たなスレッドで起動 ハンドラ内で長大な処理を行うことが可能 ３つのタイプの通信形式 非同期通信(返値なし) オブジェクト送信後、直ちにリターン 非同期通信(返値あり) オブジェクト送信後、直ちにリターンするが、返値が将来収められるオブジェクト（Futureオブジェクト）を返す touch() 操作を行うことで返値を取り出し可能。ない場合はブロック 同期通信(返値あり) オブジェクトを送信後、それに対する返値を待つ 次にJOJOの通信モデルについて。。。 JOJOはメッセージ受信ハンドラがあり、。。。 JOJOの通信形式には以下の3つがあり。。。

ｊPoPの対象アルゴリズム 遺伝的アルゴリズム 分枝限定法 焼き鈍し法(レプリカ交換法） 以上がJPOPのモジュールである。 ユーザがこのアルゴリズムを用いてGrid上で問題を解くアプリケーションを実装するのをサポートする 現段階の実装では遺伝的アルゴリズム用のクラス群のみが存在し、 以下ではこれについて述べる。

遺伝的アルゴリズム用クラス群

遺伝的アルゴリズムの概要 遺伝的アルゴリズム(GA) GAの並列化手法 生物進化を模したシミュレーションを行うことで最適解を求める 問題によって計算粒度が異なる GAの並列化手法 交叉や評価の一部を複数のノードに分散 リモートで実行する部分を自由に変更可能 適用問題によって計算粒度が異なる はじめに遺伝的アルゴリズムの概要について簡単に述べる 。。。 遺伝的アルゴリズムは。。。で図のような処理がなされることで最適解を求める。 並列化手法としては。。。といったことで分散実行する。これは 問題によって、計算粒度がことなるからである

jPoP-GAの設計 GAを記述する際には以下の情報を記述 Driver クラス 個体(探索点) 個体を評価する環境 実行制御を行うPoolクラスに呼び出されるクラス 分散実行の制御を行う ユーザがリモートで実行する部分を自由に変更可能 以上のことをふまえてJPOP-GAの設計を行う ユーザが記述するのは。。。だけである

個体の定義(1/2) ユーザは、個体をあらわすクラスと個体生成を管理するクラスを用意 Individual クラス 個体をあらわすクラスのテンプレート /*static 変数propに設定されているSilfPropertiesを用いて自らを初期化*/ public static void initializeProperties(); /*static変数envに設定されているEnvironmentを用いて評価を行い結果を返す*/ public double evaluate(); /*引数で与えられた個体との間に次世代の個体を2個体作り、その配列を返す*/ public Individual [] crossover(Individual); /*自分の突然変異を新たに作成し返す*/ public Individual mutate; 以下ではユーザが記述する部分について述べる。 個体を定義する際にユーザは。。。 Individualクラスは個体をあらわすのテンプレート ユーザは以下のようなメソッドを記述する必要がある

個体の定義(2/2) IndividualFactory クラス 個体の生成を管理するクラスのテンプレート 初期個体集合と個体を生成するためのオブジェクト public interface IndividualFactory{ /*prop で初期化*/ void init(SilfProperties prop); /*新しい個体を生成*/ Individual createRandomInitial(); /*count で与えられた数からなる初期個体集合を生成*/ Individual [] getInitialSet(int count); ｝ IndividualFactoryクラスは初期個体集合と個体を。。。

環境の定義 Environment インターフェース 個体を評価する環境をあらわすクラスのテンプレート 例:TSPにおける都市間の距離のテーブルなどの評価に用いるデータを保持 個体と分離することで通信コストを削減 Interface Environment extends Clonable Serializable{ void init(SilfProperties prop); /*初期化*/ } 以下ではJPOP-GAの実行の様子について述べる。 ユーザは。。。

遺伝子プールの定義 Pool 抽象クラス 世代交代の管理を行うクラスのテンプレート デフォルトでいくつかのPoolクラスの実装を提供 世代管理の手法を変更することは可能 abstract public class Pool{ protected SilfProperties prop; protected boolean minimize; public void inint() throws SilfException{ //dummy// } /*プール内の最適な個体を返す*/ abstract public void setInitialSet(IndividualHolder [] individuals); /*プール内の全個体を返す*/ abstract public IndividualHolder [] getPopulation(); /*次世代へ交代する*/ abstract public void oneStep();

jPoP-GAの実行(1/2) プロパティファイルを準備 プロパティファイルを引数として、jpop-gaを起動 jpop.ga.Individual.classname = 個体クラス名 jpop.ga.IndividualFactory.classname = 個体ファクトリクラス名 jpop.ga.Environment.classname = 環境クラス名 jpop.ga.Pool.classname = プールクラス名 jpop.ga.Pool.minimize = 最小化問題かどうか jpop.ga.Pool.mutationRatio = 突然変異率 jpop.ga.Driver.loopTimes = 世代数 jpop.ga.Driver.initialPopuration = 初期個体数 >java silf.jpop.ga.SingleNodeDriver ‘property file’

jPoP-GAの実行(2/2) 1.DriverがIndividualFactoryを用いて個体の初期集合を生成 2.初期集合をプールに与えてプールを初期化 3.プロパティファイルで指定された回数だけループを実行 4.プールのoneStep()メソッドを実行 個体プールから個体を選び、交叉, 評価などの処理を行う IndividualFactoryを経由して制御がDriverクラスに渡り、リモートで実行が行われる 手順の表示、原稿の5．3にあたる プロパティファイルの例示

定義例 パラメータ x に依存する関数 x2+2x+1 を最適化 個体クラスと環境クラスを定義 プロパティファイル 用意されたテンプレートに従い、それぞれのクラスを記述 プールクラスはデフォルトのものを使用 プロパティファイル jpop.ga.Individual.classname = OneDim jpop.ga.IndividualFactory.classname = OneDimFactory jpop.ga.Environment.classname = OneDimEnvironment jpop.ga.Pool.classname = silf.jpop.ga.BasicPool jpop.ga.Pool.minimize = true jpop.ga.Pool.mutationRatio = 0.0 jpop.ga.Driver.loopTimes = 100 jpop.ga.Driver.initialPopuration = 50 並列実行:環境クラスが各ノードでロードされ、Driverクラスを経由し、クラス内のメソッドを実行

個体クラスの定義例 個体クラスのcrossover メソッドが交叉を行う 評価はevaluate メソッド内のcomputeメソッドで行う 新たな x をポワソン分布に従い生成 評価はevaluate メソッド内のcomputeメソッドで行う import silf.jpop.ga.*; import silf.util.*; import java.util.*; public class OneDim extends Individual{ double x; static Random rand = new Random(); public OneDim(double x){ this.x = x; } public double evaluate(){ OneDimEnvironment env0 = (OneDimEnvironment) env; return env0.compute(x); public Individual [] crossover(Individual that){ double mid = (this.x + (OneDim)that).x) / 2; double dif = (this.x - mid) * rand.nextGaussian(); return new Individual [] { new OneDim(mid + dif), new OneDim(mid – dif); } public Individual mutate(){ return new OneDim(this.x + 0.1);

環境クラスの定義例 Environmentクラス内のcomputeメソッドが評価を 行う実体 環境クラスが各ノードでロードされ、Driverクラスを 経由し、クラス内のメソッドを並列実行 import silf.jpop.ga.*; import silf.util.*; import java.util.*; public class OneDimEnvironment implements Environment{ public void init(SilfProperties prop){ // nothing todo } double compute(double x){ return x*x + 2*x + 1;

まとめ Grid上で組み合わせ最適化問題を容易に解くための最適化システム jPoP を提案 Object Passing通信ライブラリ Jojo を設計 遺伝的アルゴリズムを分散環境上で実行するための枠組みjPoP-GAを設計 現状 sshを使用した2層構造のJojoが稼動　 ｊPoP-GAの実用性の検証中

今後の課題 他のアルゴリズム向けの枠組みの設計、実装 分枝限定法 焼き鈍し法 JojoのGSI（Grid　Security　Infrastructure）を用いたバージョンの作成 Gridの標準的なセキュリティの枠組み 評価 汎用性の検証 スケーラビリティの検証 ほかのアルゴリズムについて、GSIによる実装について、評価？について