第37回 月例発表会（2000年12月） 知的システムデザイン研究室
資源追加削減法の改良アルゴリズムにおける並列性の検証
Study of Parallelization in the improved DORAR Method阿南 英文
Hidefumi Anan
Abstract:The DORAR method is a parallel distributed optimization method for the minimization of the total resource of a system with discrete elements. Now, the DORAR method is improved, and its effectiveness is reported. However, its Parallelization is not studied. In this paper, the Parallelization in the improved DORAR method is studied.
1 はじめに
離散構造物の最適設計に対して提案された局所ルー ルに基づく並列分散最適化の手法である資源追加削減 法1,2)(以下 DORAR 法) は, 各要素でその設計変数であ る資源に余裕があれば削減し，その後微小資源を追加す るというプロセスを繰り返すことで最適解を得る．しか し，従来のアルゴリズムでは，局所解に陥る場合があり， これを克服するために，アルゴリズムに改良が加えられ た．そして，工学的な問題に適用した結果，その有効性 が確認されている3) ．しかしながら，DORAR 法の特 徴の 1 つである並列性については考察されていない．そ こで，本研究では改良された DORAR 法における並列 性の検証を行う．2 資源追加削減法 (DORAR 法) 概略
DORAR 法は，離散的な要素からなるシステムを対 象とし，各要素を資源と考え，システム全体の資源の和 の最小化を目的とする．また，システムには要求される 機能が制約条件として課せられている．それらは，各要 素の情報により決定される局所制約条件とシステム全体 の情報から決定される全体制約条件である．DORAR 法 のアルゴリズムを以下に示す． (1) 局所制約条件に関する資源余裕を評価する． (2) 全体制約条件に関する資源余裕を評価する． (3) 上記の資源余裕の最小値を各要素の臨界資源余裕 とし，これを削減する (資源削減処理)． (4) 各要素に一定の微小な資源を追加する (資源追加 処理)． (5) (1)∼(4) を繰り返すことにより最適解を得る．3 制約条件の確率的選択による DORAR 法
の概略と研究目的
従来の DORAR 法のアルゴリズムでは，局所解に陥 る場合があった．それを改善するために各要素が基準と する制約条件を確率的に選択することを基本とするア ルゴリズムの改良が提案された．これは，各要素がラン ダムに基準とする制約条件を選択し，選択されなかった 制約条件の値の変化によって評価を行うというものであ る．これをトラス構造物最適化問題に適用した結果，良 好な解に収束した． ( 1 3 ) ( 1 1 ) ( 4 ) ( 5 ) ( 1 0 ) ( 1 2 ) ( 2 ) 7 ( 1 4 ) 8 i : n o d e i n d e x , ( i ) : m e m b e r i n d e x ( 3 ) ( 6 ) 0 . 3 0 m ( 1 ) 1 k N 1 3 4 5 6 0 . 4 0 m ( 7 ) ( 8 ) ( 9 ) 2 E = 1 0 G P AFig. 1 14 member truss
( a ) N o r m a l m e t h o d ( b ) P r o p o s e d m e t h o d
Fig. 2 Converged solutions
しかしながら，並列性については考察されていない． そこで，本研究では，この改良アルゴリズムにおける並 列性を検証することを目的とする．
Table 1 PC Cluster SPEC
jupiter
OS Linux2.2.17 NODE 8+1
CPU Pentium III(Katmai) 600MHz Memory 256MB
Network 100Mbps Fast Ethernet 通信ライブラリ MPICH
Table 2 RS/6000 SP SPEC
RS/6000 SP
OS AIX4.2.1 NODE 10
CPU Power2 Super Chip 160MHz Memory 1GB
Network 1.2Gbps SP スイッチ
通信ライブラリ IBM Parallel Environment for AIX-MPI Library
4 DORAR 法における並列化
DORAR 法における並列化とは，分散システムを構 成している各資源を分散させることを意味する．すなわ ち，トラス構造物最適化問題においては，トラス構造物 を構成している各部材が資源に相当し，並列化とはその 部材を各プロセッサに割り振ることである．通信ライブ ラリとしては MPI(Message Passing Interface) を用い た．通信手法としては，今回は任意のプロセッサ数で， かつ任意の部材数で並列化できるようにAllgatherv 通 信を用いた．Allgatherv 通信は，Allgather 通信が各 送信元プロセスからの受信メッセージの長さが一定なの に対して，受信メッセージの長さと受信バッファ内の位 置を，送信元プロセスごとに変えることができる通信で ある．5 計算環境
今回用いた計算環境は，PC クラスタ (jupiter) と IBM マシン (RS/6000 SP) である．Table 1 および 2 にそ の仕様を示す．6 数値実験
今回の適用問題は，トラス構造物最適化問題である． トラス構造物最適化問題とは，ある節点に負荷を加え， 複数の制約条件のもとで最小体積のトラス構造物を設計 するというものである．そして今回適用したトラス構造 物は Table 3 に示した 3 種類である．ここで，全体制約 Table 3 適用したトラス構造物 トラス構造物 8 節点 14 部材トラス構造物 16 節点 39 部材トラス構造物 36 節点 105 部材トラス構造物 条件として変位に関する制約を考え ( では 8, では 16, では 36 の節点の変位が 0.01m 以下)，局所制約 条件として各部材の引張応力，圧縮座屈を考える．また 負荷荷重として図中に示すように 1[kN] の水平荷重を加 えた． 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) ( 8 ) ( 9 ) ( 1 0 ) ( 1 1 ) ( 1 2 ) ( 1 3 ) ( 1 4 ) ( 1 6 ) ( 1 5 ) ( 1 7 ) ( 1 8 ) ( 1 9 ) ( 2 0 ) ( 2 1 ) ( 2 2 ) ( 2 3 ) ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) ( 2 9 ) ( 2 8 ) ( 3 0 ) ( 3 1 ) ( 3 2 ) ( 3 3 ) ( 3 4 ) ( 3 5 ) ( 3 6 ) ( 3 7 ) ( 3 8 ) ( 3 9 ) 0 . 3 0 m 0 . 4 0 m 1 k N E = 1 0 G P a i : n o d e i n d e x , ( i ) : m e m b e r i n d e xFig. 3 39 member truss
1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 3 0 3 1 3 2 3 3 3 4 3 5 3 6 ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) ( 8 ) ( 9 ) ( 1 0 ) ( 1 1 ) ( 1 2 ) ( 1 3 ) ( 1 4 ) ( 1 5 ) ( 1 6 ) ( 1 7 ) ( 1 8 ) ( 1 9 ) ( 2 0 ) ( 2 1 ) ( 2 2 ) ( 2 4 ) ( 2 3 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) ( 2 8 ) ( 2 9 ) ( 3 0 ) ( 3 1 ) ( 3 2 ) ( 3 3 ) ( 3 4 ) ( 3 5 ) ( 3 6 ) ( 3 7 ) ( 3 8 ) ( 3 9 ) ( 4 0 ) ( 4 1 ) ( 4 2 ) ( 4 3 ) ( 4 5 ) ( 4 4 ) ( 4 6 ) ( 4 7 ) ( 4 8 ) ( 4 9 ) ( 5 0 ) ( 5 1 ) ( 5 2 ) ( 5 3 ) ( 5 4 ) ( 5 5 ) ( 5 6 ) ( 5 7 ) ( 5 8 ) ( 5 9 ) ( 6 0 ) ( 6 1 ) ( 6 2 ) ( 6 3 ) ( 6 4 ) ( 6 6 ) ( 6 5 ) ( 6 7 ) ( 6 8 ) ( 6 9 ) ( 7 0 ) ( 7 1 ) ( 7 2 ) ( 7 3 ) ( 7 4 ) ( 7 5 ) ( 7 6 ) ( 7 7 ) ( 7 8 ) ( 7 9 ) ( 8 0 ) ( 8 1 ) ( 8 2 ) ( 8 3 ) ( 8 4 ) ( 8 5 ) ( 8 7 ) ( 8 6 ) ( 8 8 ) ( 8 9 ) ( 9 0 ) ( 9 1 ) ( 9 2 ) ( 9 3 ) ( 9 4 ) ( 9 5 ) ( 9 6 ) ( 9 7 ) ( 9 8 ) ( 9 9 ) ( 1 0 0 ) ( 1 0 1 ) ( 1 0 2 ) ( 1 0 3 ) ( 1 0 4 ) ( 1 0 5 ) 0 . 4 0 m 0 . 3 0 m 1 k N E = 1 0 G P a i : n o d e i n d e x , ( i ) : m e m b e r i n d e x
Fig. 4 105 member truss
6.1 実験結果
計測したデータは，各形状に対し，2 通りの初期値で， 従来の DORAR 法と改良を加えた DORAR 法で，500 回の計算回数で行った．計測したデータは通信時間，解
析時間及び総計算時間である．総計算時間には，通信時 間と解析時間に加えて，DORAR 法による最適化アルゴ リズムの実行時間が含まれている．Jupiter とRS/6000 SP において，105 部材のトラス形状に対して測定した 結果を Fig.5 に示す． 使用するプロセッサを増加すると，1 プロセッサの解 析負荷が分散するため，解析時間が短縮される．しかし， プロセッサの増加は通信回数を増加させ，通信負荷を大 きくする．Jupiter に比べ，RS/6000 SP は高速ネット ワークを使用しているため，通信負荷がかからず，プロ セッサ数が増えても，総計算時間が減少している． 各部材におけるスピードアップのグラフを，従来のア ルゴリズムと改良したアルゴリズムにおいて，Jupiter とRS/6000 SP それぞれで求めた．それらを Fig.6, 7 に 示す． まずJupiter とRS/6000 SP どちらにおいても，14 部 材のトラス構造物では，並列化を行っても総計算時間に 対する通信負荷が高くなり，有意にスピードアップが図 られなかった．39 部材のトラス構造物では，高速ネット ワークを用いているRS/6000 SP で，そのスピードアッ プが 7 プロセッサまで有意に図られた．一方，105 部材 の場合では，Jupiter でも 6 プロセッサまでは，有意な スピードアップが図られた． 0 1 2 3 4 5 6 7 8 9 0 5 10 15 20 25 30 35 40 Time(sec)
Number of Processors - jupiter total connection analysis 0 1 2 3 4 5 6 7 8 9 0 5 10 15 20 25 30 35 40 Time(sec) Number of Processors - RS/6000 SP total connection analysis
Fig. 5 Relation between time and number of proces-sors at 105 members (Jupiter & RS/6000 SP)
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 Speedup
Number of Processors - normal DORAR 14members 39members 105members 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 Speedup
Number of Processors - improved DORAR 14members
39members 105members
Fig. 6 Speedup by parallel processing (jupiter)
0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 Speedup
Number of Processors - normal DORAR 14members 39members 105members 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 Speedup
Number of Processors - improved DORAR 14members
39members
Fig. 7 Speedup by parallel processing (RS/6000 SP)
7 結論と今後の課題
本研究では，改良された DORAR 法の並列性の検証 を行った．その結果，従来のアルゴリズムと局所解から の脱出を目的とした改良アルゴリズムではほぼ同様な性 能を示した．したがって，この改良アルゴリズムでは， 並列性が損なわれないことが確認できた． 今後の課題として，さらに大規模なトラス構造物に対 してもデータを測定し，考察する．また，通信手法につ いても考察する必要がある．参考文献
1) Mitumori Miki, Tomoyuki Hiroyasu, Taiju Ikeda, 『Parallel Distributed Optimization by Resource Addition and Reduction』, Lecture Notes in Com-puter Science 1615, Springer, pp.194-205, 1999 2) 池田大樹, 『資源追加削減法による離散システムの最 適化』 , 同志社大学卒業論文，1998 3) 三木光範，廣安知之，小林繁, 『制約条件の確率的選 択に基づく資源追加削減法の改良』, 日本機会学会 第 13 回計算力学講演会講演論文，2000 4) 森俊明, 『資源追加削減法の PC クラスタへの実装と 評価』, 同志社大学卒業論文，1999 4
