山崎研究室紹介
2010年10月20日
山崎 勝弘
yamazaki@se.ritsumei.ac.jp1.研究室の目標
12.育成したい人材像
3.指導方針
4.研究分野: 並列処理とハード
/ソフト・コデザイン
5.研究内容
6.貴君らに提供できること
11.研究室の目標
• ハードウェアとソフトウェアの両方分かる人
材の育成
• 並列処理とハード/ソフト・コデザインを融合
2並列処理とハ ド
/ソフト コデザインを融合
した高性能な問題解決システムの構築
• コミュニケーション能力、スケジューリング
能力、および知的体力の養成
• 社会人としての基本的素養をつけ、努力を
継続して、目標を達成できる人材の育成
22.育成したい人材像
• あいさつ
• コミュニケーション能力
– 日本語で正しく表現、発表、議論
3本語
く表現、発表、議論
– 英語能力
• スケジューリング能力
– 立案、実行、チェック(Plan, do ,check)
• 知的体力
– 最後まであきらめずにやり遂げること
33.指導方針
• 前向きに楽しく: positive thinking
• 研究テーマの設定、研究環境の整備
• 社会人になるための実力をつけて欲しい
4• 社会人になるための実力をつけて欲しい。
• 社会人としての基本的素養をつけて欲しい。
• 英会話学習のきっかけをつかんで欲しい。
• 自分の夢を将来にわたって実現して欲しい。
44.研究分野
OpenMP デザイン パターン ハード/ソフト・コラー ニングシステム 命令セット プロセッサ コンパイラ並列処理
PCクラスタの構築 1号機~4号機 画像圧縮 N体問題 音声圧縮 GPU ハイブリッド モンテカルロ 5 並列処理とハード/ソフト・コデザインを融合 した高性能な問題解決システムの構築 5 ハードウェア 動作合成 FPGA ボード DAP DNAハッシュ関数・
暗号高速化
パイプライ ン処理 MD5 SHA‐2 AES Reconfigurable Computing SHA‐2 画像処理 囲碁システムハード/ソフト・コデザインとは
ソフトウェア
ハードウェアになるかソフ
トウェアになるか分からな
い領域
6• ハードウェアとソフトウェアのバランスをうまく取っ
て、最適になるようにシステムを設計すること
• ハードウェアとソフトウェア両方の知識が必要
ハードウェア
システムLSI
携帯電話
ハード/ソフト・コデザインのキーワード
• ハードウェアとソフトウェアの最適バランス
• 命令セットアーキテクチャ
• アセンブリ言語・C言語
• ハードウェア設計言語
システム
LSI
7• システムLSI
• 専用ハードウェア(暗号化)
• FPGA:プログラム可能なLSI
• 情報家電(携帯電話、音楽プレーヤー)
7ハード/ソフト・コデザインのテーマ
• ハード/ソフト・コラーニングシステムの拡張
– コンパイラ学習支援システム、デザインパターン
• ハッシュ関数・AES暗号の高速化
• OpenMPハードウェア動作合成システム
• モンテカルロ囲碁システムのハードウェア化
82009年度卒論
• AES暗号化回路の設計とFPGAボードへの実装
• RSA暗号における冪剰余計算のFPGAボードへの実装
• OpenMPハードウェア動作合成のためのコード生成手法
の改良
大量データを扱い、計算時間が莫大であるような問題 気象予測、蛋白質構造解析、多体システム、画像処理 コンピュータグラフィックス、大規模データベースなど どのように並列に解くか プ グ グ応用
アルゴリズム
並列処理のイメージ
9 並列プログラミング言語、並列化コンパイラ デバッガ、エバリュエータ、OSソフトウエア
並列
マシン
メモリ プロセッサ 相互結合網 分散メモリ型 共有メモリ型 9並列処理のキーワード
• マルチコアプロセッサ
• マルチスレッド:スレッドレベル並列処理
• PCクラスタ、SMPクラスタ
• ハイブリッド並列処理
共有メモリ+分散メモリ
OpenMP+MPI
10– 共有メモリ+分散メモリ、OpenMP+MPI
• GPU
• High Performance Reconfigurable Computing
– CPU+FPGAによる並列処理
• グリッドコンピューティング
10
並列処理のテーマ
• 画像圧縮、音声圧縮の並列化
– JPEG, JPEG2000, MPEG2, Ogg Vorbis
• SMPクラスタ上でのハイブリッド並列処理
– N体問題、MPEG2、文字列処理、パズル
• GPUによる高並列処理
タ
グ
像処
11– リアルタイムレイトレーシング、画像処理
• モンテカルロ囲碁システムの並列化
2009年度卒論
• 文字列照合のOpenMPによる並列化
• OpenMPを用いた画像処理プログラムの並列化
115.研究内容
5.1 ハード
/ソフト・コラーニングシステム
コンパイラ学習支援システム、デザインパターン
5.2 ハッシュ関数・暗号の高速化
SHA-2、AES暗号
12SHA 2、AES暗号
5.3 OpenMPハードウェア動作合成システム
5.4
SMPクラスタ上でのハイブリッド並列処理
N体問題、文字列照合
5.5 GPUによるリアルタイムレイトレーシング
5.6 モンテカルロ囲碁システム
125.1 ハード/ソフト協調学習システム
サンプル
プログラム
ソフトウェア学習
ハードウェア学習
HDLによる
プロセッサ設計
HDL
シミュレータ
FPGAボード-MONI
シミュレータ
プロ セ ッ サ 学習 シ ス テ ム 13命令セット設計
命令セット
定義ツール
命令セット
アセンブラ
命令セット
シミュレータ
プロセッサ
モニタ
プロセッサ
デバッガ
MONIプロセッサ
アーキテクチャ理解
ボ ド
コンピュータ上で検証
プロセッサ設計
能力の習得
ムプロ
セ
ッ
サ
設計支援
ツ
ー
ル
シミュレーションまでの流れ
命令セット
定義した
命令セット
情報
14・命令長
・命令形式
・動作
・その他
定義した
命令セットの
プログラミング
命令セット
定義ツール
命令セット
シミュレータ
アセンブリ
プログラム
シミュレー
ション結果
定義項目
・
命令セットの名前 ・レジスタファイル・メモリの幅と容量 ・フィールド、フォーマット形式 ・命令名、各命令の命令動作 ・疑似命令シミュレーションのための定義条件
• 命令語長は、8,16,32ビットから選択
• 3オペランドまで対応
• 命令動作は用意された中から選択(
全70命令
)
– 算術・ビット演算子
各
5命令
– 単項演算子
6命令
15– 等号演算子、データ代入、ロード・ストア
各
2命令
– 関係演算子
4命令
– シフト演算子
3命令
– ポップ・プッシュ・コール・リターン
4命令
– ジャンプ
1命令
– 条件分岐
32命令
– キャリー・その他
各
2命令
デバッグコマンド
コマンド
load
file name
save
file name
引数
setpc / bp / stop / rf / dm
bp
del意味
命令セット・プログラムの読込み
シミュレーション結果を作成
レジスタ・メモリの設定
ブレイクポイント削除
16 stop : 最大実行命令数 inst : 各命令の実行数と全命令実行数bp
run list rstnone / bp / N
none / pc / bp / rf / sp / im / dm
none / pc / bp / rf / sp / im / dm / inst
exitブレイクポイント削除
通常
/ ブレイク / N命令実行
レジスタ・メモリの表示
レジスタ・メモリのリセット
シミュレータの終了
命令セットを用いたテスト
1
• MONI (ハード/ソフト協調学習システム)
– 命令語長16bit、3オペランド、全43命令、4命令形式
– Nまでの和、Nの階乗、除算、素数判定、根の判別
5 3 3 3 2 Opecode Opecode Opecode Opecode Rs Rs Rs Rt Rt Rd Fn Immediate Immediate Immediate命令形式
Register
JUMP
Immediate8
Immediate5
17 Opecode ImmediateJUMP
5 2 3 3 3 Opecode Opecode Opecode Opecode Rd Rs Rt Rt Rd FnImmediate
Immediate Immediate Rd命令形式
Register
JUMP
Transfer
Immediate
• SOAR (2004年度 4回生が設計)
– 命令語長16bit、3オペランド、全25命令、4命令形式 – Nまでの和、最大値、最大公約数、バブルソート命令セットを用いたテスト2
5 2 3 3 3 Opecode Opecode Rd Rs Rt Rt Rd FnImmediate
Fn命令形式
Register
Immediate3
• SARIS (2007年度 4回生が設計)
– 命令語長16bit、3オペランド、全22命令、4命令形式 – Nまでの和、Nの階乗、最大公約数、除算、根の判別 18• コマンド・全205パターンの動作が正しく動くことを確認
– フラグや境界値の変化も確認
• MONI, SOAR, SARISの命令セットを用いて、
それぞれのプログラムが正しく動くことを確認
Opecode Opecode Immediate Immediate (Rd)JUMP
Immediate8
システム全体の評価
• プロセッサ学習システム
– MONIプロセッサ設計時間の短縮
– 独自のプロセッサ設計にスムーズに入れる
• プロセッサデバッガ・モニタ
– 効率よいバグの発見で、デバッグ時間の短縮
– HDLシミュレータ上と実機上の動作の違いを的確に発見
19• 命令セット定義ツール・シミュレータ
– 命令セットの定義と評価を繰り返し行える環境
– 独自のプロセッサ設計時間の短縮
• ハード/ソフト協調学習システム
– 2人の学生が利用し、複数のアーキテクチャを設計
– 独自のプロセッサを設計
コンパイラとデザインパターン
• コンパイラ学習支援システム
– 字句解析、構文解析、意味解析、コード生成
– コンパイラ・コンパイラを利用
– コード生成部、最適化の学習
• デザインパターンによる設計支援
– 過去の設計パターンを再利用して、設計時間
の短縮を図る
– デザインパターンの設計、再利用の方法
20構文解析
定義ファイル
字句解析
定義ファイル
Flex
字句解析ツール
Bison
構文解析ツール
moni.l
moni.y
コンパイラ学習支援システム
21字句解析部
<lex.yy.c>
コード生成部
変数表
(レジスタ 番地登録) トークン列 構文木 (中間表現) Cソース コード アセンブリ コード構文解析部
<y.tab.c><y.tab.h>
コード最適化 ・名前 ・目的と用途 ・動機 ・構成要素 ・構造(アニメーション) ・本体 ソ スコ ドデザインパターン
新規設計
キーワード 類似設計パターンの検索 類似設計パターン 類似パターン キーワードプロセッサ設計におけるデザインパターンの利用
22 ・本体-ソースコード -対象プロセッサ インターフェースの修正 検証、再利用化 HDL設計 登録 機能の追加、削除 AL U M P ハザード検 IF ID EX MEM WBPC
RF
M P X M P X+
M P X+
1IM
DM
PC
+
IM
RF
RF
M P X M P X AL U AL U M P X M P XDM
23 IM DM PC RF P X CU + 1 M P X M P X imm rs rt rd M P X フォワーディン グユニット M P X ザ ド検 出 AL U M P X RF AL U MP X M P X AL U DM IM M P X命令フェッチ
R形式(ID,EXE,WB)
I8形式(ロード命
令,ID,EXE,MEM,WB)
RF5.2 ハッシュ関数・暗号の高速化
• 暗号化、電子署名
• 完全性、安全性、一方向性、非衝突性
• MD-5,SHA-1,SHA-2 次々と改訂
高速性
ド
パク さ
24• 高速性、ハードのコンパクトさ
• 入力データ長は128バイトの倍数、出力は64バイト
• 128バイト毎に圧縮関数を80回適用して、データを
かき混ぜる。
• パイプライン化による高速化の研究
+
E
∑
1
Ch
K
Maj
∑
0
D
F
G
H
B
A
C
Loop
80
t
512 512Secure hash algorithm: SHA
80 constants 16
Main
computations
25 25+
+
K
tW
t+
tim
es
E
D
F
G
H
B
A
C
+
+
+
+
+
+
+
+
512 Ha A B HbC HcD HdE HeF HfG HgH HhMessage digest
(8 words x 64 bits)Finalization
keysRelated work: Basic pipelining
80thstep 79thstep 2ndstep 1ststep tio ns + A completedIntermediate values (A~H)
3 adder-l
Imbalance in computation
Two stage pipelining
26 26 ∑1 A B C D E F G H Ch W K + ∑0 Maj Main co m ple t P re -co m put at io n Temp + + + + + + E completed 2 adder-layers layers Pre-computation Two operands computations Pre-computation Two operands computations Pre-computation Computes 80 times
Objectives
Pre-comp Pre-comp Pre-comp Pre-comp• Three stage pipelining
• Balanced critical paths
∑
0Maj
new-A
AcompB
movement (x2)+
new-E
2 adder-layersT
1 27 27 Computes 80 timesE-comp E-compE-comp E-comp A-comp A-comp A-comp A-comp
∑
1A B C D E F G H
Ch
W K
+ TEcomp KWH ForwardingKWH
+ + + + 2 adder-layers 2 adder-layersBalance in computation
Implementation results
Devices Slices Flip Flops LUTs Clock(MHz) Throughput (Mbps) Throughput/ Slices Virtex 1,574 1,700 2,891 73.1 936 0.59 Virtex-E 1,566 1,765 2,857 92.0 1,178 0.75 Virtex-2 1,542 1,636 2,788 115.9 1,485 0.96 Virtex-4 1,520 1,689 2,751 170.4 2,181 1.43 28 28
Devices Slices Clock (MHz) Throughput (Mbps) Throughput/ Slices Pipeline method Lien Virtex 2,384 56.0 717 0.30 basic Aisopos Virtex-E 2,710 58.0 1,485 0.54 basic Lien Virtex-E 3,517 72.0 1,034 0.29 unrolling McEvoy Virtex-2 4,107 65.9 1,466 0.36 unrolling Zeghid Virtex-2 1,938 - 1,580 0.82 unrolling Helion Virtex-4 1,487 133.0 1,660 1.12
-Related work
Area performance rate comparison
1 1 .2 1 .4 1 .6 Throughput/slices 29 29 0 0 .2 0 .4 0 .6 0 .8 Pr opos ed Lien Pr opos ed Lien A is opos Pr opos ed McEv oy Ze gh id Pr opos ed H elion
Virtex Virtex-E Virtex-2 Virtex-4
AES暗号の全体図
SubByte変換 Shiftrows変換 MixColumns変換 AddRoundKey変換 AddRoundKey変換 入力鍵 鍵拡張,w4-w7 平文 ラウンド1 逆MixColumns変 換 AddRoundKey変換 逆 変換 AddRoundKey変換 逆SubByte変換 逆Shiftrows変換 平文 ラウンド10 SubByte変換 Shiftrows変換 MixColumns変換 AddRoundKey変換 SubByte変換 Shiftrows変換 AddRoundKey変換 鍵拡張,w36-w39 鍵拡張,w40-w43 暗号文 ラウンド9 ラウンド10 AddRoundKey変換 逆MixColumns変 換 AddRoundKey変換 逆SubByte変換 逆Shiftrows変換 逆SubByte変換 逆Shiftrows変換 暗号文 ラウンド1 ラウンド9 30実験結果と今後の方針
暗号化
復号化
スライス数 最大遅延時間(ns) スライス数 最大遅延時間(ns) SubBytes 1024 10.33 1024 8.13 ShiftRows 14 4.10 0 4.63 MixColumns 133 9.27 314 9.27 AddR dK 74 7 76 74 5 75ラウンド1回分 1221 スライス
全体 3759 スライス
最大遅延時間 13.9 ns
19.6 ns
・AES暗号化回路の全体の設計
・Sbox(表)をBlockRAMに入れて処理する回路の設計
・1ラウンドを1クロック、複数クロックで完了する回路の設計
・パイプライン化の検討 ・DAPDNA上での設計
31 AddRoundKey 74 7.76 74 5.75 KeyExpansions 757 53.18 752 43.255.3 OpenMPハードウェア動作合成システム
OpenMP プログラム (動作記述) ハードウェ ア制約 OpenMP コンパイラ トランスレータ マルチスレッド 並列アルゴリズム 逐次プログラムから の段階的な設計 32 32 コード ジェネレータ SMP環境 (PCクラスタ) シミュレーション 並列動作 ハードウェア マルチスレッド プログラム 並列動作HW 中間表現 アルゴリズム評価 ハードウェア合成 並列効果 回路規模 性能評価 OpenMP構文を 利用した動作合成 早期に並列化手法の検討 検証時間の短縮CベースとOpenMPベースの比較
Cベース
OpenMPベース
Cプログラム
並列リージョン ユーザ記述 33OpenMPプログラム
ハードウェア記述
自動並列化 並列リージョン からの変換データ並列の実行モデル
• データ並列性のある処理をノードで分担
• 100回の繰り返しを4ノードで分担する場合
#pragma omp parallel for
for(i=0;i<100;i++) {
処理A
(i); }
34
#pragma omp parallel for (スレッド生成 & fork)
処理Aスレッド(i=0~24) 処理Aスレッド(i=25~49) 処理Aスレッド(i=50~74) 処理Aスレッド(i=75~99)
join 各スレッドはforループ内 の繰り返し処理を分担 終了時のリダクション演算 (結果の足し合わせなど)
sum= sum+i
データ並列のハードウェア構成
逐次データパス 並列データパス Control Control 並列HWの起動・終了 35 Memory or Register Op処理A 処理A 処理A 処理A
Arbiter スレッド間共有データへ の同時アクセス制御 Memory or Register 並列データパス 動作時は停止
SMP環境と動作合成による実行時間
スレッド数1
2
4
実行時間(ms)39.39
21.41
13.97
速度向上比1.00
1.84
2.82
スレッド数1
2
4
実行時間(ms)38.05
28.26
25.77
速度向上比1.00
1.35
1.48
SMP環境 生成ハードウェアエッジ検出
SMP環境 生成ハードウェアハフ変換
スレッド数 1 2 4 スレッド数 1 2 4 36• ほぼ理想的な速度向上
• SMPによる速度向上比と相関
• 生成ハードの方が速度向上比が高い:メモリアクセスの比率が少ない スレッド数 1 2 4 回路シミ 動作クロック数 (Mcycle) 158.7 79.4 39.8 ュレータ クロック減少比 1.00 2.00 3.99 並列ハー 動作周波数(MHz) 88 88 88 ドウェア 速度向上比 1.00 2.00 3.99 スレッド数 1 2 4 回路シミ 動作クロック数 (Mcycle) 51.3 29.5 26.2 ュレータ クロック減少比 1.00 1.74 1.96 並列ハー 動作周波数(MHz) 89 89 89 ドウェア 速度向上比 1.00 1.74 1.965.4
SMPクラスタ上でのハイブリッド並列処理
N-Body Problem
• Finding the positions and movements of the
bodies in space subject to gravitational forces
from other bodies
• Using Newtonian laws of physics
mb r
37
• Once bodies move to new positions, the forces
change and the computation has to be repeated
2
r
m
Gm
F
=
a bm
t
F
v
v
t+1=
t+
Δ
t
v
x
x
t+1=
t+
t+1Δ
Gravitational force Velocity Positionma
r)
(
2n
Θ
Too expensiveSpatial Partitioning
Each processor is assigned one
rectangle with approximately
equal number of bodies
1) A vertical line is found that
divides the area into two, each
i h
l
b
f b di
38
with an equal number of bodies
2) For each area, a horizontal line
is found to divide it into two with
equal number of bodies
3) The procedure is repeated until
there are as many areas as
processors
Spatial partitioning with 16 processors
Hybrid Parallel Programming
tion M P I: intra- + in ter-node + ho rizon tal m e ss ages
Gigabit
Ethernet
39 Share d mem o ry Share d mem o ry Share d mem o ry Share d mem o ry Intra -node c o mm unic a t Pure M = v e rtic a l +Performance Evaluation
Name
SMP Node
# of
Nodes
# of
CPUs
OS
MPICHIntel C
Compiler
Network
Diplo
Quad Xeon
4
16
CentOS4.4
with
1 2
9 1
Gigabit
•System specifications
40Diplo
3GHz
4
16
with
Rocks4.2
1.2
9.1
Gigabit
Atlantis
Dual Xeon
2.8GHz
16
32
RedHat8.0
with
SCore5.8
1.2
9.0
Gigabit
•3 data sets: 10,000; 50,000 and 100,000 bodies
MPI vs. Hybrid: Execution Time with
10
5
bodies
80 100 120 140 160 mi n u te sHybrid (4-way Diplo) MPI (4-way Diplo) Hybrid (2-way Atlantis) MPI (2-way Atlantis)
41 0 20 40 60 80 1 2 4 8 16 32 Number of Processors Tim e in
N体問題:the n-body problem
N-Body: One of the
grand challenge
problems
mb
ma
r
Strong desire for
computation speed
Parallelization
42
PC Clusters
SMP Clusters
Grid
MPI
Hybrid MPI-OpenMP
GridRPC
DATA Memory Processor 1 Send (DATA) DATA Memory Processor 2 Receive (DATA) Node 1 Node 2 Processor 0 Processor 1 Processor 0 Processor 1
GridRPC vs. the others: Execution Time with
10
5
bodies
80 100 120 140 160m
inut
es
Hybrid (4-way Diplo) MPI (4-way Diplo) GridRPC (4-way Diplo + Raptor)
43 0 20 40 60 80 1 2 4 8 16 24
Number of Processors
Ti
m
e
i
n
m
• 非常にリアルなCG画像を作成する手法のひとつ。
• 視点から光を追跡することにより画像を描画する。
• 映画制作、ゲームのCG表現、拡張現実感、試作レス化などに利用。
5.5 GPUによるリアルタイムレイトレーシング
<研究目標>
• GPUやマルチコアCPUを用いてリアルタイム(100ms以下)に画像を生
成する。
• 古典的レイトレーシングのみならず、モンテカルロレイトレーシング、フォト
ンマッピングも対象とする。
445.6 モンテカルロ囲碁システム
各種知的ゲームの比較
チェス
将棋
囲碁
局面数
10
12010
20010
300コンピュータ チャンピオン
アマ名人程度
アマ初段程度
の強さ
に勝利
女流トッププロ
アマ三段
程度
45の強さ
に勝利
女流トッププロ
アマ三段
程度
人間に勝つ
1997年
2010年
女流
?
のはいつ
Kasparov
2015年? 名人
トピック
IBM
評価関数の
モンテカルロ囲碁
DeepBlue
機械学習
人間との対戦
激指 清水上アマ名人に○ MoGo プロ8段に9子で○ 稲葉アマ準名人に× CrazyStone あから2010 清水女流王将に○ 青葉4段に8子で○モンテカルロ囲碁とは
• 囲碁は陣地をたくさん取った方が勝ち
• ある局面から最後まで実際に打って(プレイアウト)、
最も勝率の高い手を次の手とする。
• ランダムプレイアウト:乱数を用いて、適当に最後まで
打つ(弱い)
46打つ(弱い)
• パターンプレイアウト:よく出てくるパターンに基づいて
最後まで打つ(上より強い)
• 次の候補手を5つ位選ぶ→プレイアウト→最も勝率の
高い手を次の手とする。
モンテカルロ囲碁の並列化
盤面認識
候補手生成(5つ)
1 2 3 4 5プレイアウト
47プレイアウト
0.4 0.5 0.3 0.7 0.6 勝率 1 2 3 4 54を打つ
黒勝ち 白勝ち 0.8 0.66 0.6 0.5 大量のプレイアウトを高速に行う 1万回/秒 4プロセッサでは4万回/秒モンテカルロ囲碁のハードウェア化
• 序盤、中盤、終盤でアルゴリズムが異なる。
• 序盤、中盤、終盤に最適のハードウェアを用意し、実
行時に切り替える(動的再構成)
48 48行時 切り替
(動 再構成)
• 死活判定、詰碁用ハードウェアを検討し、実現する。
6.貴君らに提供できること
• 問題解決の仕方
– 卒論、進路、就職、‥
• スケジューリングの仕方
– Plan do check
49Plan, do, check
• 研究発表の仕方
– 日本語文章、スライド作成、発表、‥
• 英会話勉強の仕方
– IEEE student branch カウンセラー
– 英語プレゼン大会
49