Agenda

並列処理プロセッサのスケーラビリティの検証
～PSOアルゴリズムを中心として～
数理情報科学専攻福永研究室
大井謙
2012.02.01
首都大学東京修士論文発表会 Y.Oi
1
目次
• 研究背景
– 並列処理とスケーラビリティ
– TPCOREの開発
– 研究の動機
• 検証方法
– PSOアルゴリズムとその並列化
– TPCOREネットワークの構成
• 検証結果
• まとめと今後の展望
2012.02.01
首都大学東京修士論文発表会 Y.Oi
2
研究背景-並列処理とスケーラビリティ
• 並列処理
– 1つの処理を複数に分割して同時に行うこと(⇔逐次処理)
– 処理内容を共有するため互いが通信する必要がある
時間
：計算時間
1
：スケジューリング
逐次処理では必要ない
(オーバーヘッド)
1/2
1/4
逐次処理
2012.02.01
並列処理
(2分割)
並列処理
(4分割)
首都大学東京修士論文発表会 Y.Oi
3
研究背景-並列処理とスケーラビリティ
• 並列処理
– 1つの処理を複数に分割して同時に行うこと(⇔逐次処理)
– 処理内容を共有するため互いが通信する必要がある
– 分割した中で最も遅いものが性能を決めるので
：計算時間
均等に分割した方が良い
時間
均等でない並列処理
(4分割)
2012.02.01
：スケジューリング
逐次処理では必要ない
(オーバーヘッド)
この幅が
性能の差になる
均等な並列処理
(4分割)
首都大学東京修士論文発表会 Y.Oi
4
研究背景-並列処理とスケーラビリティ
• スケーラビリティ
– ネットワークやアルゴリズムが持つ拡張性のこと
• 並列処理におけるスケーラビリティ
– 前述のオーバーヘッドにより
分割する数を増やしすぎると処理効率が落ちる
– 「いくつまでの拡張ならば効率的なのか」を検証する
• 検証するもの
– 並列処理プロセッサTPCORE
2012.02.01
首都大学東京修士論文発表会 Y.Oi
5
研究背景-TPCOREの開発
• 当研究室で開発している並列処理プロセッサ
• Inmos社のTransputer-T425互換を目指し作成(2005)
• 並列プログラミング言語Occamを実行可能
– 言語自体が並列処理の仕組みを持っておりOSが必要ない
• TPCOREは4本のLinkを持っており
これを用いることで様々なネットワークを構成できる
TP
TPCORE
TP
TP
TPCOREとLink
2012.02.01
Pipeline構造
TP
TP
TP
TP
TP
Star構造
首都大学東京修士論文発表会 Y.Oi
TP
TP
TP
TP TP
TP
Tree構造
6
研究背景-TPCORE
• VirtualChannel&Routerにより
ネットワークトポロジの制限から開放(2009)
• T425 の次世代プロセッサT800 と互換性をもたせた
ハードウェアによる実数演算が実現(2010)
TP
TP
TP
TP
Router
TP TP TP TP TP
Star構造
TP
TP
TP
TP
Routerの開発によって
すべての TPCOREを
1対1で接続できるようになった
2012.02.01
TP
TP
TP
TP
TP
Fully Connected構造
首都大学東京修士論文発表会 Y.Oi
7
研究背景-動機
• これまでの研究方針からの課題
– ハードウェア実装の優先により
複雑なソフトウェア実装による検証が検討課題となっていた
• 「電動車椅子危険探知および回避システム」の開発
– これは当研究室で現在推し進めているプロジェクトである
– 危険感知・回避という性質から高速処理が求められるため
ハード・ソフト両面からの処理能力に焦点を当てたい
– しかしこのシステムはまだ構想段階にある
並列処理研究でよく用いられるアルゴリズムをOccamにて実装
ＴＰＣＯＲＥのネットワークごとに処理効率を検証した
2012.02.01
首都大学東京修士論文発表会 Y.Oi
8
検証方法-PSOアルゴリズム
• PSO(Particle Swarm Optimization)
– James Kennedy と Russell C. Eberhart による(1995)
– 自然界で群れを成す動物に見られる
一匹が経路を発見すると残りが素早くそれに倣う性質を
particle(粒子)の群でモデル化したアルゴリズム
– 解が点や面で表される問題の最適解を探索する
2012.02.01
首都大学東京修士論文発表会 Y.Oi
9
検証方法-PSOアルゴリズム
• ランダムに配置された各particleは規定回数移動し
「良い位置」についての情報を交換しながら収束する
一つ一つのparticleが
自発性を持って
移動している
それらの計算は
独立しているため
並列性がある
particleは
中央に収束した
「良い位置」=中央
その評価基準は?
2012.02.01
首都大学東京修士論文発表会 Y.Oi
10
検証方法-PSOアルゴリズム
• particleの位置評価方法
– 評価用の関数(フィットネス関数：f)を用いる
– 各particleの位置情報 X  ( x1, x2 ,, xn ) を f に入力
– 評価値 f(X) の中で最小となるものを最適値とし
このときの位置情報を「最も良い位置」とする
• 検証に使うフィットネス関数
– ベンチマーク関数としてよく使われているものを選択した
• Ridge関数
• Ackley関数
– ともに X = (0, 0, … , 0) にて f(X) = 0 (最小値) となる
2012.02.01
首都大学東京修士論文発表会 Y.Oi
11
検証方法-PSOアルゴリズム
• Ridge関数
n
i
f ( X )   ( x j )
i 1
j 1
2
• Ackley関数
1 n 2
1 n
f ( X )  a  exp(b 
cos(c  xi ))  a  e
 xi )  exp(n 
n i 1
i 1
a  20, b  0.2 c  2
図はともに2次元の場合である
2012.02.01
首都大学東京修士論文発表会 Y.Oi
12
検証方法-並列化
• どのように並列化するのか(負荷分割)
– PSOの計算負荷はparticle数にほぼ比例するので
各TPCOREの扱うparticle数が均等になるように分割する
– particleが持つ「良い位置」についての情報は
各TPCOREが通信する事によって交換される
TPCORE
1, 2, 3
TPCORE
4, 5, 6
TPCORE
7, 8, 9
TPCORE
10, 11, 12
2
1
3
4
6
5
7
12
9
8
11
10
2012.02.01
首都大学東京修士論文発表会 Y.Oi
13
検証方法-TPCOREのネットワーク構成
• TPCOREのみを用いた並列化
– 1台での逐次処理にかかる時間を基準とする
– ネットワークに制限があるため, 2台, 3台, 7台のみ
TP
TP
TP
TP
TP
TP
TP
TP
TP
TP TP
TP
• Routerを用いた並列化
– 2台～6台のFully Connected構造
TP
TP
Router
TP
TP
・・・
TP
Router
TP
2012.02.01
首都大学東京修士論文発表会 Y.Oi
TP
TP
14
検証結果
• Ridge関数の実行結果
Ridge関数
時間(秒)
効率(倍)
10.0
9.0
7.0
8.9
5.9
6.0
8.0
5.0
7.0
4.7
6.0
5.0
5.0
1.8
3.0
2.0
4.1
2.6
4.0
1.0
4.0
3.4
2.6
3.0
2.17
2.0
1.9
1.5
3.4
1.0
0.0
1.0
0.0
1
2012.02.01
TPCOREのみ(時間)
Router使用(時間)
TPCOREのみ(効率)
Router使用(効率)
2
3
4
5
TPCOREの数(台)
6
首都大学東京修士論文発表会 Y.Oi
7
15
検証結果
• Ackley関数
Ackley関数
時間(秒)
効率(倍)
35.0
30.0
5.5
29.0
6.0
5.0
4.8
25.0
20.0
16.5 15.0
3.6
2.9
2.8
4.0
4.0
3.0
15.0
10.4 10.1
10.0
1.0
2.0
8.1
1.9
1.8
7.3
6.1
5.0
5.3
0.0
1.0
0.0
1
2012.02.01
TPCOREのみ(時間)
Router使用(時間)
TPCOREのみ(効率)
Router使用(効率)
2
3
4
5
TPCOREの数(台)
6
首都大学東京修士論文発表会 Y.Oi
7
16
まとめと今後の展望
• 今回の検証の結果
– TPCOREのみを用いた並列化では
7台のTree構造で最大5.9倍の効率
– VirtualChannel&Routerを用いた並列化では
6台のFully Connected構造で最大4.8倍の効率
– 台数効率は直線を維持している
• 今後の展望
– 現在の開発環境は容量の関係上これが限界の台数なので
将来はこれ以上のネットワークを構築できる余地がある
– 「電動車椅子危険探知および回避システム」においても
並列化の効率はこの結果を参考に開発する事ができる
2012.02.01
首都大学東京修士論文発表会 Y.Oi
17

Download Report