山川栄樹, 牧英一
ブロック構造を持つ
2 次計画問題に対する
非同期並列型共役勾配法
Abstract:並列処理が身近なものとなりつつある中で、数理計画問題に対しても既に多くの並列アルゴリズムが提案されている[2,3]。その多くは、数理計画における双対理論と関数（行列）分割の考え方を基礎としており、もとの問題の近似モデルを複数の独立な部分問題に分割し、各反復でこれらを並列的に解くことによって原問題の解に至るような点列を生成しようとするものである。特に、主問題あるいは双対問題の変数を単位とするような粒度の細かい分割が行われ、生成された部分問題の解が解析的に求められるような場合には、最近盛んに開発が進められている超並列計算機上での実行に適したデータ並列型のアルゴリズムが得られる。一方、現実の大規模問題が持つ構造的な特徴を利用して、効率的な並列アルゴリズムを得ることも可能である。
文献[8]では、分離可能な目的関数を持つ2次計画問題に対して、双対問題の目的関数の係数行列をブロック対角行列を用いて分割し、その結果得られる複数の小さな部分問題を共役勾配法を用いて解くようなブロック並列型のアルゴリズムが提案されている。多期間計画問題や多品種流問題などのように、もとの問題の制約条件の係数行列がある種のブロック構造を持つ場合には、その双対問題の目的関数の係数行列も何らかのブロック構造を示す。従って、この構造に沿う形で双対問題を分割すれば、比較的少ない反復数で収束するような並列アルゴリズムを得ることができる。このアルゴリズムは、もとの問題のブロックを単位とする比較的粗い分割に基づいており、
各部分間題をそれぞれ反復解法を用いて解く必要があるため、コントロール並列型のアルゴリズムとなる。既に、コネクション・マシンCM-5をはじめとして、MIMD(Multiple-Instruction Multiple-Data)型の並列計算機もいくつか商品化されており、コントロール並列型のアルゴリズムの実行も現実のものとなっている。特にCM-5は、比較的少数のベクトル計算機を構成要素と
するような並列計算機であり、粗い粒度で分割された各部分問題にはそれぞれデータ並列型の計算モデルを、アルゴリズム全体に対してはコントロール並列型の計算モデルを適用することができるため、非常に良好な結果を得ることができる。
コントロール並列型のアルゴリズムを並列計算機上で実行する際には、各部分問題を解くことに専念するいくつかの処理装置の他に、アルゴリズム全体の進捗管理および各処理装置への仕事の分配を行うもう一つの処理装置を置くという計算モデルを用いる場合が多い。何人かの部下を使って管理戦が仕事を進める形態に似ていることから、前者の各処理装置はワーカー・ノード，後者の処理装置はマスター・ノードと呼ばれる。文献[8]で提案されたブロック並列型のアルゴリズムでは、ワーカー・ノード群が計算する各部分問題の解がすべて揃うのを待って、
マスター・ノードは収束判定と次の探索点における部分問題の構成を行う。
従って、もとの問題のブロック構造が一様ではないなどの理由により各ワーカー・ノードが部分問題を解くために要する時間に大きな差が生じる場合には、遊休状態となる処理装置が多数発生して、並列化効率が著しく低下する可能性がある。
そこで、本論文では、すべてのワーカー・ノードの処理について同期をとることを強制しないような非同期並列型のアルゴリズムを提案する。すなわち、マスター・ノードは、いくつかのワーカー・ノードが部分問題を解き終わった段階で探索点を更新して部分問題を構成し直し、遊休状態となったワーカー・ノードにこれらを分配して探索を再開させる。また、アルゴリズムの収束判定は、マスター・ノードが探索点を更新するたびに行うこととし、収束したと判定された場合には、現在稼働中のワーカー・ノードが遊休状態となった時点でアルゴリズム全体を終了させることにする。なお、マスター・ノードが収束判定を行っている間に各ワーカー・ノードが遊休状態に陥る可能性も考慮して、マスター・ノードの機能を二つの処理装置に分割し、部分問題の再構成を行う第1のマスター・ノードと収束判定のみを行う第2のマスター・ノードを用いるモデルについても検討を行う。