Document

大規模再構成可能データパスにおける
オンチップ・ネットワークの検討
九州大学 / JST CREST
○島崎慶太，長野孝昭
ファラハドメディプー，本田宏明
井上弘士，村上和彰
1
発表手順
• 研究背景
• 大規模再構成可能データパス
• オンチップネットワークの面積に関する評価
– 配線/演算資源間のトレードオフ解析
• おわりに
2
研究背景
• 近年、アクセラレータを用いた高性能計算機シス
テムが注目されている
– CSX600 processor（ClearSpeed社）
– Cell B.E. （Sony，東芝，IBM）
• アクセラレータ
– 演算性能に特化したコプロセッサ
– 演算性能の増加に伴い要求メモリバンド幅が増大
– メモリウォール問題の深刻化
• 演算性能と比較してメモリの性能が低いことにより計算機全
体としての性能が抑えられてしまう
要求メモリバンド幅を抑え、かつ高い演算性能
を実現するアクセラレータの提案
3
大規模再構成可能データパス
（LSRDP: Large-Scale Reconfigurable Datapath）
• 概要
ORN
...
FPU
ORN
:
:
:
:
...
ORN
...
ORN
SB
:
:
:
:
LM
SMAC
...
:
– 浮動小数点数演算器（FPU:
Floating-Point Unit）を2次元アレイ
状に配置
– FPUを相互接続する網（ORN:
Operand Routing Network）により
データ転送
– FPUで行う演算内容、ORN上の
FPU間接続関係を再構成可能
• データ依存関係を利用しメモリア
クセス回数を削減
4
メモリアクセス回数の削減
提案手法
プログラム
A = B + C;
デ
ー
タ
依
存
・
・
・
・
・
・
・
D = A－E;
・
・
・
・
・
load R0, [B] メモリ
読み込み
load R1, [C]
add R2, R0, R1
store R2, [A] メモリ
・
・
・
書き込み
load R3, [A] メモリ
読み込み
load R4, [E]
sub R5, R3, R4
store R5, [D] メモリ
・
・
・
・
B
C
＋
デ
ー A
タ
依
存
メモリ
読み込み
E
－
D
書き込み
・
・
・
5
LSRDPへのアプリケーションの
実装方法（1/2）
• アプリケーション
プログラムの解析
• GPPとLSRDPそれぞ
れ計算する部分の
振り分け
Application
Program
Exe. Code
for GPP
GPP
Mem.
LSRDP
Arc. Def.
LSRDP
Config. Data
LSRDP
Engine
6
LSRDPへのアプリケーションの
実装方法（2/2）
ソースコード
A  BC
D  EF
G  A D
データパス
DFG
B C
E
×
F
×
A
D
＋
マ
ッ
ピ
ン
グ
ORN
×
×
ORN
＋
ORN
G
ORN
7
ループ処理をLSRDPに実装（1/4）
入
力
デ
ー
タ
ソースコード
for (i=0; ; i++)
for (j=0; ; j++)
for (k=0; ; k++)
for (l=0; ; l++)
ループボディ
forend
forend
forend
forend
デ
ー
タ
パ
ス
を
構
成
イタレーション3のデータ
イタレーション2のデータ
イタレーション1のデータ
ORN
ORN
ORN
ORN
8
ループ処理をLSRDPに実装（2/4）
入
力
デ
ー
タ
ソースコード
for (i=0; ; i++)
for (j=0; ; j++)
for (k=0; ; k++)
for (l=0; ; l++)
ループボディ
forend
forend
forend
forend
デ
ー
タ
パ
ス
を
構
成
イタレーション3のデータ
イタレーション2のデータ
ORN
イタレーション1のデータ
ORN
ORN
ORN
9
ループ処理をLSRDPに実装（3/4）
入
力
デ
ー
タ
ソースコード
for (i=0; ; i++)
for (j=0; ; j++)
for (k=0; ; k++)
for (l=0; ; l++)
ループボディ
forend
forend
forend
forend
デ
ー
タ
パ
ス
を
構
成
イタレーション3のデータ
ORN
イタレーション2のデータ
ORN
イタレーション1のデータ
ORN
ORN
10
ループ処理をLSRDPに実装（4/4）
入
力
デ
ー
タ
ソースコード
for (i=0; ; i++)
for (j=0; ; j++)
for (k=0; ; k++)
for (l=0; ; l++)
ループボディ
forend
forend
forend
forend
デ
ー
タ
パ
ス
を
構
成
ORN
イタレーション3のデータ
ORN
イタレーション2のデータ
ORN
イタレーション1のデータ
ORN
11
パ
イ
プ
ラ
イ
ン
処
理
初期積分計算における
LSRDPの性能予備調査
５１列
入力数：17，出力数：1
演算器数：122
１３段
○ 横幅無限大の
LSRDP を仮定
○ 配線，演算器配置
技術
12
計算の遅延ならびに並列度
（LSRDP ループ計算の場合：120回）
初期積分連続計算における
※
LSRDP 内の計算並列度と計算推移時間との関係
最初の計算
の
出力
並列計算演算器数（個）
140
平均並列計算数： 97.3
ループの
最終回開始
メモリアクセス回数：2160
120
100
92
メモリアクセス
回数~1/5倍
80
通常プロセッサ：
60
メモリアクセス回数：
40
~ 10000
Simple Scalar
20
0
0
20
40
60
80
100
120
実行時間 (Clock Cycle)
140
160
180
※全演算器の遅延を一律 3CC
13 とした
LSRDPの特徴
• 利点
– 多数のFPUによる高い演算性能
– データ依存関係を利用してメモリアクセス回数の削減
• 実行方式
– コアとなるループのイタレーション間並列性を活用した
パイプライン実行
– 比較的頻度の低い再構成処理
• ハードウェア構成
– 面積の大部分はFPUとORN
14
研究目的
• LSRDPの構成を決定するには？
–
–
–
–
ORNの構成
FPUの配置数
FPUの演算の種類
etc…
• ORNの構成について検討
– 性能、面積に大きく影響
15
FPU間接続
隣接行間接続
– ORN
• 完全接続
• 制限付き接続
（前提）
非隣接行間接続
ORN
ORN
ORN
– データ転送にFPUを使用
ORN
16
ORNの構成例
（a）完全接続
（b）FPU間接続数３
FPU
O
R
N
17
ORNの構成例
制限付き接続におけるマッピング手法例
FPU内を経由
使用されるFPUの数が増える
行数が増える
18
配線/演算資源間のトレードオフ関係
１
４
２
５
３
６
接続数
多い少ない
配線面積
大
小
FPU数少ない多い
７
マッピング
１
２
１
３
２
３
FPU FPU ・・・・・ FPU
ORN
４
５
６
７
４
５
２’ ３’
FPU FPU ・・・・・ FPU
LSRDP
２行でマッピング可
６７
３行でマッピング可データ転送用に使用
19
配線/演算資源間のトレードオフ解析
• 目的
– 配線/演算資源間のトレードオフ関係を解析
– LSRDPの面積が最小となるORNの構成を検討
• 手法
– LSRDPの構成要素の面積見積もり
• FPUの面積
• FPU間接続数の異なるORNの面積
– 二電子積分計算における初期積分部分
• DFGを人手でマッピング
– 列数32、行数最小を目的
20
面積の見積もり方法
• LSRDPの面積はFPUとORNの面積の和に
より求める
LSRDP
– FPUの面積
• GRAPE-DRのPEのデータを参考
– プロセス90nmを前提
• 1行あたり32個配列
• LSRDPの横幅は約20mm
– ORNの面積
• レイアウト設計により見積もる
FPU FPU ・・・・・ FPU 1
組
ORN
FPU FPU ・・・・・ FPU
ORN
・
・
・
・
– デザインルールを違反しない範囲で面積ができるだけ小
さくなるように設計（配線幅と配線間隔を最小寸法にする）
21
構成の違うORNのレイアウト図
（a）完全接続
FPU
（b）FPU間接続数３
22
初期積分計算のDFG
• 入力データ数：18 出力データ数：1
• 演算ノード数：140 エッジ数：251
• クリティカルパス：16 （終端ノードまでの最大パス長）
23
1行あたりのORN面積と
マッピングに必要となる行数
FPUの行数
0.7
60
0.6
50
0.5
40
0.4
0.3
30
0.2
20
0.1
10
0
0
3
5
7
9
11 13 15 17 19 21 23 25 27 29 32
FPU間接続数
24
行数
面積(×20）m㎡
一行あたりのORNの面積
ORNの総面積
総ORNの面積
総ORNの面積（×20)m㎡
12
10
8
6
4
2
0
3
5
7
9
11 13 15
17 19 21 23
25 27 29 32
FPU間接続数
ORN1行の面積に必要な行数を乗算した値
25
FPUの総面積
総FPUの面積
総FPUの面積(×20)m㎡
35
30
25
20
15
10
5
0
3
5
7
9
11 13 15
17 19 21 23 25 27 29 32
FPU間接続数
FPU1行の面積に必要な行数を乗算した値
26
LSRDPの面積
総ORNの面積
総FPUの面積
LSRDPの面積（×20)m㎡
35
30
25
20
15
10
5
0
3
5
7
9
11 13 15 17 19 21 23 25 27 29 32
FPU間接続数
9個のFPU（左4/右4/下1）間接続で面積最小
27
まとめ
• ニ電子積分の初期積分部分をマッピング
したときの配線・演算資源間のトレードオフ
関係を明らかにし、LSRDPの面積を評価
• FPU間接続数9のORNをもつLSRDPが、
最も面積が小さくなることがわかった
28
今後の課題
• 他のアプリケーションを対象とした実験
– 数値計算ライブラリ
・・・
ORN
• アーキテクチャの設計空間の探索
– 配線資源を考慮したFPU間接続
・・・
ORN
・・・
ORN
・・・
• LSRDPアーキテクチャの決定・評価
29
ご静聴ありがとうございました
30
FPU間接続
・・・
• 隣接行間接続（ORN）
ORN
– 完全接続
– 制限付き
・・・
ORN
• 非隣接行間接続
・・・
– データ転送にFPUを使
用
– データ転送に配線資
源を使用
ORN
・・・
ORN
・・・
：配線資源
31
計算の遅延ならびに並列度
（LSRDP
１回計算の場合）
１つの初期積分計算時における
※
LSRDP 内の計算並列度と計算推移時間との関係
並列計算演算器数（個）
60
平均並列計算数： 10.8
50
LSRDP計算遅延： 35 CC
メモリアクセス回数： 18
40
メモリアクセス回数
30
~1/5倍
通常プロセッサ：
※※
122 演算の演算遅延見積り: 126 CC
メモリアクセス回数：
~80
Simple Scalar
20
10
0
0
5
10
15
20
25
実行時間 (Clock Cycle)
30
35
32 とした
※全演算器の遅延を一律 3CC
※ ※パイプライン化された逐次計算
LSRDP を利用した場合の
電子反発積分ループ計算アルゴリズム変
更
(d d ,d d )
LSRDP 使用時
loop: IJKLの各成分
begin
通常
loop： IJKL
begin
(IJ,KL)の全成分を同時に
計算
(IJ,KL)全成分を利用し計算
end
(IJ,KL) は，配列量
0 0
0 0
(d0d0,d0d1)
…
各成分に対応した
LSRDP構成情報の入替え
loop: 現成分を持つ IJKL
begin
LSRDP
(IJ,KL)の 1成分のみ
計算
(IJ,KL) 1成分のみ利用し計算
end
end
33
電子反発積分計算ループにおける，
各計算アルゴリズムの計算量とデータアクセス比較
(dd,dd) ,120 ループ繰り返しでの見積もり：
通常プロセッサ
LSRDP 使用時
計算遅延 (CC)
~5x10^9
~5x10^9/並列度
ロードストア回数
>5x10^9
※
※全演算器の遅延を一律１CC とした
※ ※１演算に対し１ロードストア以上と見積り
※※
<<5x10^9
動的再構成
演算器入れ替え分
１．(IJ,KL) = (JI,KL) = (IJ,LK) = (JI,LK)
= (KL,IJ) = (LK,IJ) = (KL,JI) = (LK,JI)
なる対称性を利用すると更に ld 数は削減
２．大多数の再構成の際に部分再構成で済む34
FPU間接続
 隣接行間接続（ORN）
完全接続
 制限付き
 非隣接行間接続
 データ転送にFPUを使用


ORN
ORN
完全接続
 １行のFPU数制限無し

制限付き
ORN
 １行のFPU数制限有り

データ転送に配線資源を使用

完全接続
ORN
 １行の配線資源数制限無し

制限付き
 １行の配線資源数制限有り
35
・・・
ORN
・・・
ORN
・・・
ORN
・・・
36

Download Report