「Cell Speed Challenge 2008 自由課題部門」 2008 年 6 月

Cell B.E. による SIMD-oriented Fast Mersenne Twister を用いた
Particle Swarm Optimization
五十嵐 潤

園尾 聡

古賀 崇了

九州工業大学大学院 生命体工学研究科 脳情報専攻
最適化問題において，群知能に着想を得た Particle Swarm Optimization (PSO) と呼ばれる手法の有効性が多数報告されている．PSO では，差分方程式による繰り返し計算を行い，パラメータ探索に膨大な計算が必要となる．PSO の一連の計算の中で，特に計算コストが高いのは，擬似乱数生成である．我々はこの点に着目し，擬似乱数生成に，Cell の高い SIMD 演算性能を用いることで，高速に計算できないかと考えた．そこで，高速かつ質の良い擬似乱数を生成することで知られる，SIMD-oriented Fast Mersenne Twister (SFMT) を Cellで実行し，PSO の計算を行った．その結果，汎用 CPU で通常の擬似乱数生成法を用いるのに比べて，14-42倍の高速な計算を実行することができた．

x 2k −11 はじめに

x 2kxi ,2x 2k +1最適化問題とは，制約条件を満たした上で目的関数を最x1k +1xi ,1小（もしくは最大）にするパラメータを探索する問題であx1kfitness ( x )highる．工学的な実応用における最適化問題は，その解空間が非線形・非凸・多峰性関数などの複雑な目的関数で表され

x3k −1p gk

x1k −1p1kることが多い．近年，そのような最適化問題を解決するものとして，Particle Swarm Optimization (PSO) と呼ばp k2

x3k +1x3kp3klow

れる最適化手法が注目されている [1]．PSO は，昆虫や動図1

物の群行動・人間の社会生活などの集団行動に着想を得た

PSO による探索過程の概略最適化手法である．そのアルゴリズムは簡素に記述できる上に，様々な最適問題に対して有効であるという特長を有する．

2 方法

PSO は優れた最適化手法であるが，大規模で複雑な問題

2.1 PSO のアルゴリズム

を PSO で探索するには，膨大な計算が必要になる．PSOの計算過程で，特に計算コストが高いものとして，多用さPSO では，群れ状の多数の探索点（パーティクル）が互れる擬似乱数生成が挙げられる．もし，PSO における擬いに情報を共有しながら解空間における探索を進める．図似乱数生成に，Cell B.E. の高い演算性能を活用できるな

1 に PSO の計算過程の概略を示す．

らば，計算の高速化が期待できる．

各探索点は，位置ベクトル xki ，速度ベクトル v ki ，各探索

近 年 ，高 速 で 質 が 良 い 擬 似 乱 数 を 生 成 す る ア ル ゴ リ

点の過去の最良値 Eik とその時の位置ベクトル pki を保持

ズ ム と し て ，SIMD-oriented Fast Mersenne Twister

している．パーティクル集合全体（群れ）では過去の最良(SFMT)[3] が提案されている．SFMT は多段パイプライ値 Egk とその時の位置ベクトル pkg の情報を共有する．こン処理や SIMD 演算などの並列演算処理を考慮した設計

こで i，k はそれぞれ各パーティクルの番号と計算ステッであり，さらに生成される擬似乱数は「長周期を有する」，プを表す．

「良好な均等分布特性が証明されている」などの非常に優以下に PSO の計算の処理手順を簡潔に示す．

れた性質を持っている．本稿では，SFMT を擬似乱数生

1. 探索空間における各パーティクルの初期位置と初期成法として用いて Cell B.E. に PSO を実装することで，速度をそれぞれ擬似乱数によって決定する．

非常に高速な計算を行えることを示す．

1

2. 現在の xki から，目的関数の値を計算する．

目的関数名と数式

3. 各パーティクルについて計算した目的関数の値を各目的関数の慨形

F1: Shpere Model

パーティクルの最良値 Eik と比較し，pki と xki を更新する．最後に全パーティクルで比較を行い，全体の最良値 Egk を得る．

4. 次時刻における各パーティクルの速度と位置を数式に従って計算する．

F2: Genelalized
RosenBrock’ s Function

v k+1= γv ki + c1 U (0, φ1 ) ⊗ (pki − xki )i+ c2 U (0, φ2 ) ⊗ (pkg − xki )xk+1= xki + v kii

F3: Step Function

ここで，γ, c1 , c2 は探索方針を決定するパラメータで，それぞれ 0.99, 0.9, 0.9 である． U (0, φi ) は区
間 [0, φi ] で一様分布をなす擬似乱数を要素とするベクトルを表し，各計算時刻，各パーティクルについて計算される．

F4: Quatric Function
with Noise

5. 上記 2.〜4. の手順を，規定回数繰り返す．

2.2 ベンチマーク関数
PSO の最適化問題のベンチマークとして，図 2 に示す

F5: Shekel’ s Foxholes

De Jong のテスト関数群 [2] の最小値を求めた．本研究では，パーティクル数は 32 とし，F1-F3 は 100，F4-F5 では 500 回，差分方程式の計算を繰り返し，1 試行とした．
全てのベンチマーク関数において，2400 回の試行を行い，計算に要した時間を測定した．

図2

DeJong のテスト関数群

2.3 使用機器と計算設定演算を用いなかった．SFMT では，乱数を一括生成する使用機器と計算環境について表 1 に示す．Cell B.E. のf ill array32 関数を用いた．

計算時間の測定には，主に SPU Decrementer を用い，50

図 3 で，PSO の探索の一例として，Dejong ベンチマー

秒以上かかる計算にのみ Linux シェルコマンド time を用ク関数 F1 で rand と SFMT を用いた場合の，400 試行いた．比較対象機では，C 言語標準ライブラリの clock 関の最良値の平均と標準偏差の推移を示す．rand と SFMT数を用いた．両計算環境において，数値演算精度には単精で，最良値の収束の速さと最終的な最良値に大きな違いは度を用いた．

なかった．

2.4 疑似乱数生成法 -SFMT と rand-

3 結果

疑似乱数生成には，松本眞，斎藤睦夫が WEB ページ[4] で公開している SFMT バージョン 1.3.3 と，C 言語標はじめに，擬似乱数生成に rand を用いて PSO の計算準ライブラリの rand 関数を用いた．PowerPC Altivec 用を行ったときの，Cell の性能を調べた．図 4 は，SPE 一の SFMT コードに変更を加え，Cell B.E. で実行できるよ

基で，組み込み関数を用いて SIMD 演算を使用したとき，うにした．Core 2 Duo で SFMT を実行する際は，SIMD使用しないとき，および Core 2 の計算時間を示している．

2表1

使用機器と計算環境

Cell B.E. 搭載機：PlayStation3

比較対象機：汎用 PC

CPU

Cell B.E. 3.2GHz (PPE+6SPE)

Core 2 Duo 2.66GHz (use 1-core)

MemoryXDR 256MB

DDR2 2GBOS

Fedora Core 6, (kernel2.6.18-53.1.4.el5)

CentOS 5, (kernel2.6.18-53.1.4.el5)

Compiler

Cell 用 GCC 4.1.1 (-O3)

Intel compiler ICC (-O3)

Library

Cell SDK 2.1, libspe2, SIMD Math Library

20050100

計算時刻

図3SPE 6基
SPE 1基Core 2rand
SFMT2410050

計算時刻

計算時間 [ 秒 ]rand
SFMT最良値の標準偏差最良値の平均

4100

最良値の推移の例

25000SPE 1基SIMDあり
SPE 1基SIMDなし
Core 2F120

図5800
計算時間 [ 秒 ]100

F2F3F4F5rand を用い SPE6 基を使用したときの計算時間

600
10全てのケースで，SPE6 基を使用したときは，Core 2 に比100べて，1/3-1/7 倍の計算時間であった．
00F1

図4F2F3

SPE6 基で計算を行ったときの計算時間の内訳を図 5 に
F4F5示す．PSO は，主要な計算部分として，位置の更新，評価値の算出，最良値の決定，速度の更新がある．図 5 の水色

rand を用い SPE1 基を使用したときの計算時間の速度の更新の部分は，主に rand により乱数生成を行う部分で，F1-F5 のテストにおいて，割合が非常に大きいこ

SIMD 演算を用いる場合は，4 試行をベクトルの 4 要素にとがわかる．この結果から，PSO における擬似乱数生成割り当て並列に計算を行った．F1-F5 の全てのケースで，を rand から SFMT に変えることで，より高速な計算を行

SIMD 演算を使用したとき，使用しないときに比べて，5うことが期待される．
そこで，擬似乱数生成に SFMT を用いて，PSO の計倍以上高速に計算された．ベクトル計算による高速化に加え，組み込み関数により，計算の効率が上昇しためである算を行った．図 7 は Cell

B.E. と汎用 Core 2 においと考えられる．SPE1 基で SIMD 演算を使用したときは，て，SFMT と rand を用いたときの計算結果を示している．

Core 2 に比べ，約 2 倍の計算時間を要した．

Cell B.E. と汎用 CPU ともに，SFMT を用いることで，次に SIMD 演算を使用し，SPE6 基で計算を行った (図rand に比べ，計算時間は大幅に短縮された．F1-F5 の全5)．SPE6 基を使用したとき，SPE1 基を使用したときにてのケースにおいて，Cell B.E. で SFMT を用いて計算し比べて，計算時間がほぼ 1/6 になった．これは，PSO のたときは，もっとも高速に計算が行われた．

計算では SPE 間の通信の必要がないため，SPE の数が増

表 2 は，図 7 で示される Cell B.E. と Core 2 の計算時えた分だけ，計算時間が短縮されるためである．F1-F5 の間の比を求めたものである．Cell B.E. で SFMT を用いた

3

F1F2

表2F3F5F4Cell B.E. と Core 2 における計算時間の比

F1F2F3F4F5Core 2-rand/Cell-SFMT

41.442.0

29.1

33.513.9

Core 2-SFMT/Cell-SFMT

13.915.0

13.7

12.1

12.0Core-2-rand/Cell-SFMT

3.0

3.3

3.5

3.3

7.2

位置の更新
評価値の算出
最良値の決定
速度の更新

4 議論
図6

rand を用いたときの計算時間の内訳

本研究では，Cell B.E. で SFMT を用いて PSO を実行することで，非常に高速に計算を実現できることを示した．

Cell-SFMTCore 2-SFMT
Cell-randCore 2-rand

Cell B.E. の SIMD 演算やマルチコアを用いた並列計算だけで，汎用 CPU よりも約 3-7 倍高速な計算を行うことが可能である．さらに，Cell B.E. の得意な SIMD 演算を活60

計算時間 [ 秒 ]2

かせる SFMT を利用することで，汎用 CPU で rand を用いたときにくらべ，約 14-42 倍の高速な計算を達成することができた．

301

今回行った Dejong のベンチマークテストでは，rand とSFMT を用いて PSO を実行したとき，最終的に得られる0

図7最良値の値に，違いはみられなかった．しかしながら，今0F1F2F3F4F5回よりも複雑な高次元空間や，未知の空間を探索する場合，擬似乱数の性質の差が探索の効率を変える可能性がある．

Cell B.E. で SFMT を用いたときの計算時間

そのような場合，長周期かつ，高次元に均等分布の擬似乱数を生成する SFMT は，高い探索性能を発揮することがときは， Core 2 で rand を用いたときに比べ，約 14-42 倍期待される．の速度になった (表 2 ，Core 2-rand/Cell-SFMT の行)．
汎用 CPU で rand を用いた，通常の PSO の計算に比べ，参考文献

Cell B.E. で SIMD 演算，マルチコア，SFMT を用いた計算は，非常に高速であることがわかる．

[1] J. Kennedy and R. Eberhart, “Particle Swarm Opti-

また，Cell B.E. と Core 2 において，擬似乱数を randmization,” Proc. of IEEE the International Confer-

から SFMT へ変えた効果の違いを，表 2 からみることがence on Neural Networks, pp.1942-1948, 1995.

できる．Cell B.E. と Core 2 ともに rand を用いたとき，[2] KA. De Jong, “An analysis of the behavior of a class

Cell B.E. の計算速度は，Core 2 に比べ約 3-7 倍であるの

of genetic adaptive systems,” PhD thesis, University

に対し (表 2，Core 2-rand / Cell-rand の行)，Cell B.E.，

of Michigan, 1975.

Core 2 ともに SFMT を用いたときは，約 12-15 倍となっ

[3] M. Saito and M. Matsumoto, “SIMD-oriented Fast

た (表 2，Core 2-SFMT / Cell SFMT の行)．この結果かMersenne Twister: a 128-bit Pseudorandom Number

ら，Cell B.E. に SFMT を用いたときは，Core 2 に用いた

Generator,” Monte Carlo and Quasi-Monte Carlo

ときよりも，より高速化の効果が高いといえる．Cell B.E.

Methods 2006, Springer, pp.607-622, 2008.の SIMD 演算の高い演算性能が，SFMT を用いることで[4] http://www.math.sci.hiroshima-u.ac.jp/˜m-

より効果的に発揮されたといえる．

mat/MT/SFMT/index-jp.html
4