２０００　研究テーマ

(1)

1

山崎研究室紹介

２０１１年１０月２４日

山崎勝弘

[email protected] １．研究室の目標２．育成したい人材像３．指導方針４．研究分野：並列処理とハード/ソフト・コデザイン５．研究テーマ６．貴君らに提供できること 1

(2)

１．研究室の目標

• ハードウェアとソフトウェアの両方分かる人

材の育成

• コミュニケーション能力、スケジューリング

能力、および知的体力の養成

• 社会人としての基本的素養をつけ、努力を

継続して、目標を達成できる人材の育成

• 並列処理とハード/ソフト・コデザインを融合

した高性能な問題解決システムの構築

(3)

3

２．育成したい人材像

• あいさつ

• コミュニケーション能力

– 日本語で正しく表現、発表、議論

– 英語能力

• スケジューリング能力

– 立案、実行、チェック（Plan, do ,check）

• 知的体力

– 最後まであきらめずにやり遂げること

3

(4)

３．指導方針

• 前向きに楽しく： positive thinking

• 研究テーマの設定、研究環境の整備

• 社会人としての基本的素養をつけて欲しい。

• 社会人になるための実力をつけて欲しい。

• 英会話学習のきっかけをつかんで欲しい。

• 自分の夢を将来にわたって実現して欲しい。

(5)

5

４．研究分野

並列処理とハード/ソフト・コデザインを融合した高性能な問題解決システムの構築

(6)

研究経歴

_{（1976～現在）}

FPGA ハードソフトアーキテクチャ並列アプリ知識工学 QA-1 MUNAP レイトレーシングラジオシティハード/ソフト・コラーニングシステム JPEG、MPEG N体、グリッド電力系統知的CAI 事例ベース並列プログラミングハッシュ関数高速化同期マルチメディア MAP設計ガラス傷検出 AES OpenMP 動作合成 _{リアルタイム} レイトレーシングモンテカルロ囲碁ルーティングトランスピュータ AP1000+ PCクラスタ SMPクラスタ KSR1 GPU FPGA プロセッサ４台の並列マシンマイクロプログラム制御ハードウェア、システムソフトアプリケーション SMPクラスタ情報工学科情報学科電子情報デザイン学科 1988 2004 1994

(7)

なぜハードとソフトか

• 人間：強い肉体（体力）＋知恵（知力） • コンピュータ：高い性能（ハード）＋使いやすさ（ソフト） • ハードのみ：組み立ては容易 – 差別化が難しい。低価格化にさらされる。 • ソフトのみ：技術者が多い。 – Cプログラミングだけなら理工系なら誰でもできる。 • ハードとソフト：できる人材が極めて尐ない。ニーズは高い。 • Cプログラミング：アセンブリ言語やコンパイラのコード生成が分かれば、コンパクトで速いプログラムができる • プロセッサ設計：命令の使われ方や使用頻度が分かれば、良い命令セットを設計できる。 7

(8)

ハード/ソフト・コデザインの目標

• プロセッサ設計 • 命令セットアーキテクチャ • アセンブリ言語、C言語、コンパイラ • ハードウェア設計言語 • ハードウェアとソフトウェアの最適バランス • FPGA：プログラム可能なLSI 目標 • 学生独自のプロセッサをFPGA上で動かす。 • 暗号化、画像処理、囲碁などをFPGA上で動かす。 • ＦＰＧA上で動作させて、感激を味わう。

(9)

9

並列処理の目標

• マルチコアプロセッサ • マルチスレッド：スレッドレベル並列処理 • PCクラスタ、SMPクラスタ • ハイブリッド並列処理 – 共有メモリ＋分散メモリ、OpenMP＋MPI

• GPU(Graphics Processing Unit) 目標

• リアルタイムレイトレーシングや画像処理など、大規模問題をSMPクラスタやGPU上で高速に解く。

• 実際に動作させて、高速化を実感し、感激を味わう。

(10)

５．研究テーマ

５．１マルチALUプロセッサの設計とコンパイ

ラ設計支援

５．２ FPGAを用いたガラス傷検出とAESの高

速化

５．３ GPUによるリアルタイムレイトレーシング

５．４ OpenMPハードウェア動作合成システム

５．５モンテカルロ囲碁システム

５．６命令スケジューリング

(11)

11

５．１マルチALUプロセッサの設計と

コンパイラ設計支援

命令セット設計命令セット定義ツール命令セットアセンブラ命令セットシミュレータプロセッサモニタプロセッサデバッガサンプルプログラム MONIプロセッサアーキテクチャ理解

ソフトウェア学習

ハードウェア学習

HDLによるプロセッサ設計 HDL シミュレータ FPGAボード- コンピュータ上で検証 MONI シミュレータプロセッサ設計能力の習得プロセッサ学習システムプロセッサ設計支援ツール

(12)

命令セットを用いたテスト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 5 2 3 3 3 Opecode Opecode Opecode Rd Rs Rt Rt Rd Fn Immediate Immediate Rd 命令形式 Register Transfer Immediate

• SOAR (2004年度 4回生が設計)

– 命令語長16bit、3オペランド、全25命令、4命令形式 – Nまでの和、最大値、最大公約数、バブルソート

(13)

13

命令セットを用いたテスト2

• コマンド・全205パターンの動作が正しく動くことを確認

– フラグや境界値の変化も確認

• MONI, SOAR, SARISの命令セットを用いて、

それぞれのプログラムが正しく動くことを確認

5 2 3 3 3 Opecode Opecode Opecode Opecode Rd Rs Rt Rt Rd Fn Immediate Immediate Immediate Fn (Rd) 命令形式 Register JUMP Immediate8 Immediate3

• SARIS (2007年度 4回生が設計)

– 命令語長16bit、3オペランド、全22命令、4命令形式 – Nまでの和、Nの階乗、最大公約数、除算、根の判別

(14)

マルチALUプロセッサMAPの設計

• 複数ALUによる並列処理が可能

• レジスタファイルは32個で、全ALUで共有

• ALUで並列演算と連鎖演算を行う

• FPGAボード上での実装・評価

• ハードウェアとアセンブラでの並列処理の検出・

比較

命令語長 64 SUB $0 $0 $0 LD $1 MEM[$0+#0]

(15)

2ALUのMAPのデータパス

(16)

(17)

MAPプログラミング

• 例整数同士による c=a×b の計算

プログラマは並列演算や連鎖演算を考慮せずに 1命令ずつ記述する。

(18)

ALU並列処理

ハードウェアによる並列性の検出

PPUで単一実行、並列演算、連鎖演算を判定

並列演算 連鎖演算

(19)

FPGAボード上への実装

• Xilinx社のSpartan-3A Starter Kitボードと、同社の論理合成ツール総合開発環境ISE13.2を使用する。

• 研究室で開発したプロセッサデバッガを使用する

(20)

プロセッサデバッガ・モニタ

コマンドをデコードボードコンピュータを制御

コマンドを入力

(21)

MAP用アセンブラ

• 2命令を取り出し、各オペコードで並列性を検出 • 並列性が検出できたらオペランドから命令間での連鎖を検出 21 並列並列連鎖連鎖

(22)

字句解析部 <lex.yy.c> 構文解析 定義ファイル 字句解析 定義ファイル Flex 字句解析ツール Bison 構文解析ツールコード生成部 変数表 （レジスタ番地登録） トークン列 構文木 （中間表現） Cソース コード アセンブリ コード 構文解析部 <y.tab.c><y.tab.h> moni.l moni.y コード最適化

コンパイラ設計支援システム

(23)

23 ・名前・目的と用途・動機・構成要素・構造（アニメーション）・本体 -ソースコード -対象プロセッサデザインパターン新規設計キーワード類似設計パターンの検索類似設計パターンインターフェースの修正検証、再利用化 HDL設計類似パターンキーワード登録

プロセッサ設計におけるデザインパターンの利用

機能の追加、削除

(24)

５．２ FPGAボードを用いたガラス傷検出

使用する欠損画像 TDI ラプラシアンフィルタ 2値化ラベリング判別ノイズ除去エッジ抽出閾値判定ラベル付け HW化液晶ガラス検査装置の高速化ケーデーイーとの共同研究

(25)

TDI（Time Delay Integration）

TDIとは同じ画像の画素をずらして撮影を繰り返し、その共通部分を重ね合わせ平均値を取ることで、ノイズの影響が小さい画像を得る手法 1 1 1 1 2 2 2 2 3 3 3 3 1 0 1 2 1 2 2 2 3 2 3 2 理想の画像現実の画像 25 0 0 0 0 1 0 1 2 2 1 1 1 1 2 2 2 2 2 3 2 3 2 3 2 3 3 3 4 3 4 4 4 1.5 0.5 1 1.5 1.5 2 2.5 2 3 2.5 3 3

(26)

ラプラシアンフィルタ

ラプラシアンフィルタとは、画像中に含まれる物体の輪郭抽出（エッジ）を抽出フィルタである。ラプラシアンフィルタ： f(x, y) y y) f(x, x y) L(x, ₂ 2 2 2       30 7 5 5 6 3 8 9 10 4 1 1 1 1 -8 1 1 1 1

(27)

ラベリング

ラベリングとは、画像の繋がっている画素（連結成分）に同じ番号（ラベル）をつけ、異なった連結部分には異なった番号をつける処理である。ラベリングにより、TDIやラプラシアンフィルタ処理後に残ったノイズ（傷）を検出する事ができる。 2 2 2 2 3 3 1 1 1 1 1 27

(28)

ラプラシアンフィルタのHW化（１）

アドレス調整メモリラプラシアンフィルタ 2値化画像データ Spartan3A SK lap EX 画像データ

(29)

ラプラシアンフィルタのHW化（2）

(30)

実験条件

•実験内容あらかじめTDI処理を128回行った画像でラプラシアンフィルタ処理を行う。FPGAボードとパソコン両方で処理させ、その処理時間を比較する。実際のガラス欠損画像データを使用（株式会社ケー・デー・イー提供） •使用したFPGAボード

Xilinx社のSpartan3A Starter Kitを使用し、同社の設計ツールを用いて設計を行った。

•パソコン

Intel® Core™2 Quad CPU Q9400 2.67GHz、実装メモリ4.00GB、 Windows 7 Ultimate 32bitオペレーティングシステム。

(31)

実験結果（1）

回路規模や遅延、最大動作周波数は以下のようになった

ラプラシアンフィルタの処理時間

31

Number of Slices 314 Number of Flip Flop 23 Number of 4 input LUTS 591

Delay 24.849（nsec） Maximum Frequency 40.243(MHz)

パソコン 108（msec） FPGAボード（Spartan3A SK） 7.6（msec）

(32)

実験結果（2）

(33)

AES暗号の全体図

SubByte変換 Shiftrows変換 MixColumns変換 AddRoundKey変換 AddRoundKey変換 SubByte変換 Shiftrows変換 MixColumns変換 AddRoundKey変換 SubByte変換 Shiftrows変換 AddRoundKey変換入力鍵鍵拡張,w36-w39 鍵拡張,w4-w7 鍵拡張,w40-w43 平文暗号文ラウンド1 ラウンド9 ラウンド10 AddRoundKey変換逆MixColumns変換 AddRoundKey変換逆SubByte変換逆Shiftrows変換逆MixColumns変換 AddRoundKey変換逆SubByte変換逆Shiftrows変換 AddRoundKey変換逆SubByte変換逆Shiftrows変換暗号文平文ラウンド1 ラウンド9 ラウンド10 33

(34)

• 非常にリアルなCG画像を作成する手法のひとつ。 • 視点から光を追跡することにより画像を描画する。 • 映画制作、ゲームのCG表現、拡張現実感、試作レス化などに利用。 ＜研究目標＞ • GPUを用いて、リアルタイム（１００ｍｓ以下）に画像を生成する。 • 古典的レイトレーシングのみならず、モンテカルロレイトレーシング、フォトンマッピングも対象とする。

５．３ GPUによるリアルタイムレイトレーシング

34

(35)

レイトレーシングの問題点

• 光線と物体との交差判定

が全処理の約８割

– 物体の数が増えると処理時間が増える

– 反射が多いと処理時間が増える

35

• 交差判定の高速化が必要

①交差判定自体を高速化する

②交差判定の回数を減らす

＜解決策＞

①GPUを用いた画面分割

②GPUを用いた適応型空間分割

(36)

NVIDIA Tesla C1060

• ストリーミング・マルチプロセッサ（SM）を30搭載 • 各SMにストリーミング・プロセッサ（SP）を8搭載 • 16KBの共有メモリ • 32bitのレジスタ（16K個） • Single Instruction Multiple Thread（SIMT）型プロセッサ

(37)

GPUを用いた画面分割

• スクリーンを分割

• 分割された画素ブロック

は各SMで処理

• 共有メモリを有効利用

37

(38)

適応型空間分割

• 含まれる物体が最も

多い空間を２分割

• 空間を１２８分割する

まで繰り返す。

• 各空間を各SPに割り

当て並列処理を行う。

(39)

現在までにできていること

（１）物体情報の定義ファイル読み込み（２）レイトレレーシング処理・拡散反射（物体に陰影をつける）・鏡面反射（物体に光沢感をつける）（３）レイトレーシング画像出力 39 実行時間：58.67(s) 実行時間：124.48(s) 実行時間：396.91(s) Intel（R）Core(TM)2 Duo CPU E6850 @3.00GHz

(40)

５．４ OpenMPハードウェア動作合成システム

コードジェネレータ OpenMP プログラム (動作記述) ハードウェア制約 SMP環境 (PCクラスタ) シミュレーション並列動作ハードウェア OpenMP コンパイラトランスレータ マルチスレッド プログラム 並列動作HW 中間表現アルゴリズム評価ハードウェア合成並列アルゴリズム並列効果回路規模性能評価 OpenMP構文を利用した動作合成早期に並列化手法の検討検証時間の短縮逐次プログラムからの段階的な設計

(41)

CベースとOpenMPベースの比較

Cベース

41

OpenMPベース

Cプログラム OpenMPプログラム並列リージョンユーザ記述ハードウェア記述自動並列化並列リージョンからの変換

(42)

データ並列の実行モデル

• データ並列性のある処理をノードで分担

• 100回の繰り返しを4ノードで分担する場合

#pragma omp parallel for

for(i=0;i<100;i++) { 処理A(i); }

#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

(43)

43

データ並列のハードウェア構成

逐次データパス Memory or Register 並列データパス Op 処理A 処理A 処理A 処理A Control Control 並列HWの起動・終了 Arbiter スレッド間共有データへの同時アクセス制御 Memory or Register 並列データパス動作時は停止

(44)

コードジェネレータの改善

44

the number of state

transitions

State1,2 state3 State4,5 state6 state7 state8 false true true false a = a + 1 b = b + 2 state1 state2 state3 state4 state5 state6 state7 state8 false true true false a = a + 1 b = b + 2 ・Sジェネレータ（１演算）とMジェネレータ（複数演算）・状態数と一時レジスタの削減による高速化を図るコードジェネレータを作成中・マンデルブロー、エッジ抽出で速度が 25％向上

(45)

45

５．５モンテカルロ囲碁システム

各種知的ゲームの比較

チェス将棋囲碁局面数１０１２０_１０２００_１０３００コンピュータチャンピオンアマ名人程度アマ初段程度の強さに勝利女流トッププロアマ三段_程度人間に勝つ１９９７年２０１０年女流２０３０年？のはいつ Kasparov ２０１５年？名人トピック IBM 評価関数のモンテカルロ囲碁 DeepBlue 機械学習人間との対戦激指清水上アマ名人に○ MoGo プロ8段に9子で○ 稲葉アマ準名人に× CrazyStone あから2010 清水女流王将に○ 青葉4段に8子で○

(46)

46

モンテカルロ囲碁とは

• 囲碁は陣地をたくさん取った方が勝ち

• ある局面から最後まで実際に打って（プレイアウト）、

最も勝率の高い手を次の手とする。

• ランダムプレイアウト：乱数を用いて、適当に最後まで

打つ（弱い）

• パターンプレイアウト：よく出てくるパターンに基づいて

最後まで打つ（上より強い）

• 次の候補手を５つ位選ぶ→プレイアウト→最も勝率の

高い手を次の手とする。

(47)

モンテカルロ囲碁の並列化

47 盤面認識候補手生成（５つ）プレイアウト１２３４５ 0.4 0.5 0.3 0.7 0.6 勝率１２３４５４を打つプレイアウト黒勝ち白勝ち 0.8 0.66 0.6 0.5 大量のプレイアウトを高速に行う１万回/秒４プロセッサでは４万回/秒

(48)

モンテカルロ囲碁のハードウェア化

• 序盤、中盤、終盤でアルゴリズムが異なる。

• 序盤、中盤、終盤に最適のハードウェアを用意し、実

行時に切り替える（動的再構成）

(49)

49 Miss-prediction Bias (MPB) の発見と応用予測ミスが一部の分岐命令に集中する。予測器LPHTを追加して、再予測する。分離式BTB

(Branch Target Buffer)

無条件分岐命令を従来のBTBから分離し，小さい特殊なBTBを追加する。

５．６命令スケジューリング

条件分岐命令（ beq ）の分岐予測の精度を上げる。ＢＴＢ：beq命令の分岐先の予測アドレスを格納する表ＢＴＢを工夫、追加して精度を上げる。

２０００ 研究テーマ

山崎研究室紹介

山崎 勝弘

１．研究室の目標

• ハードウェアとソフトウェアの両方分かる人

材の育成

• コミュニケーション能力、スケジューリング

能力、および知的体力の養成

• 社会人としての基本的素養をつけ、努力を

継続して、目標を達成できる人材の育成

• 並列処理とハード/ソフト・コデザインを融合

した高性能な問題解決システムの構築

２．育成したい人材像

• あいさつ

• コミュニケーション能力

– 日本語で正しく表現、発表、議論

– 英語能力

• スケジューリング能力

– 立案、実行、チェック（Plan, do ,check）

• 知的体力

– 最後まであきらめずにやり遂げること

３．指導方針

• 前向きに楽しく： positive thinking

• 研究テーマの設定、研究環境の整備

• 社会人としての基本的素養をつけて欲しい。

• 社会人になるための実力をつけて欲しい。

• 英会話学習のきっかけをつかんで欲しい。

• 自分の夢を将来にわたって実現して欲しい。

４．研究分野

研究経歴

（1976～現在）

なぜハードとソフトか

ハード/ソフト・コデザインの目標

並列処理の目標

５．研究テーマ

５．１ マルチALUプロセッサの設計とコンパイ

ラ設計支援

５．２ FPGAを用いたガラス傷検出とAESの高

速化

５．３ GPUによるリアルタイムレイトレーシング

５．４ OpenMPハードウェア動作合成システム

５．５ モンテカルロ囲碁システム

５．６ 命令スケジューリング

５．１ マルチALUプロセッサの設計と

コンパイラ設計支援

ソフトウェア学習

ハードウェア学習

命令セットを用いたテスト1

• MONI (ハード/ソフト協調学習システム)

• SOAR (2004年度 4回生が設計)

命令セットを用いたテスト2

• コマンド・全205パターンの動作が正しく動くことを確認

• MONI, SOAR, SARISの命令セットを用いて、

それぞれのプログラムが正しく動くことを確認

• SARIS (2007年度 4回生が設計)

マルチALUプロセッサMAPの設計

• 複数ALUによる並列処理が可能

• レジスタファイルは32個で、全ALUで共有

• ALUで並列演算と連鎖演算を行う

• FPGAボード上での実装・評価

• ハードウェアとアセンブラでの並列処理の検出・

比較

2ALUのMAPのデータパス

MAPプログラミング

• 例 整数同士による c=a×b の計算

ALU並列処理

ハードウェアによる並列性の検出

PPUで単一実行、並列演算、連鎖演算を判定

FPGAボード上への実装

プロセッサデバッガ・モニタ

MAP用アセンブラ

コンパイラ設計支援システム

プロセッサ設計におけるデザインパターンの利用

５．２ FPGAボードを用いたガラス傷検出

TDI（Time Delay Integration）

ラプラシアンフィルタ

ラベリング

ラプラシアンフィルタのHW化（１）

ラプラシアンフィルタのHW化（2）

実験条件

２０００　研究テーマ

山崎勝弘

_{（1976～現在）}

５．１マルチALUプロセッサの設計とコンパイ

５．５モンテカルロ囲碁システム

５．６命令スケジューリング

５．１マルチALUプロセッサの設計と

• 例整数同士による c=a×b の計算

５．５モンテカルロ囲碁システム

５．６命令スケジューリング