ソフトコアプロセッサを用いた ハードウェア/ソフトウェア協調

平成22年2月5日（金）
平成21年度 日本大学
卒業研究発表会
＠37号館204教室
ソフトコアプロセッサを用いた
ハードウェア/ソフトウェア協調設計における
機能分割手法に関する研究
日本大学 生産工学部
数理情報工学科
須釜 裕太
1
発表内容





背景・目的
機能分割問題
機能分割アルゴリズム
実験結果
まとめ
2
携帯電話の構造
3
携帯電話の構造
制御システム
4
黄：ハードウェア領域
従来のシステム
PLL
UART
緑：ソフトウェア領域
ADC/DAC
DMA
MPU
User
Logic
RAM
Timer
Interface
Interface
Interface
5
黄：ハードウェア領域
現在のシステム
緑：ソフトウェア領域
青：中間領域
SoC（System on a chip）
PLL
UART
ADC/DAC
DMA
MPU
User
Logic
RAM
Timer
Interface
Interface
Interface
6
背景・目的
ハードウェア/ソフトウェア協調設計：SoCに対応した現在のシステム設計
問題点
中間領域に対して
ハードウェアとソフトウェア
どちらで実装するべきか？
7
SoCにおける
ハードウェア領域の実装方法
SoC
PLL
UART
ADC/DAC
DMA
MPU
User
Logic
RAM
Interface
Interface
Timer
Interface
データバスを介して接続（ハードウェア・アクセラレータ実装）
8
SoCにおける
ハードウェア領域の実装方法
SoPC（System on a Programmable Chip）
PLL
UART
ADC/DAC
DMA
MPU
User
Logic
RAM
Timer
Interface
Interface
Interface
9
SoPC特有の
ハードウェア領域の実装方法
Logic
Ａ
ＩＮ
ー
ＡＬＵ
＋
ＯＵＴ
＆
Ｂ
MPU内部のALUに接続（カスタム命令実装）
10
背景・目的
ハードウェア/ソフトウェア協調設計：SoCに対応した現在のシステム設計
問題点
中間領域について
ハードウェアとソフトウェア
どちらで実装するべきか？
問題点
ハードウェア領域に対して
ハードウェア・アクセラレータとカスタム命令
どちらで実装するべきか？
機能分割問題
解決策
機能分割アルゴリズムが注目されている
目的：ソフトウェア/ハードウェア・アクセラレータ/カスタム命令の
3分割に対応した機能分割アルゴリズムを提案し、実機で評価する
発表内容





背景・目的
機能分割問題
機能分割アルゴリズム
実験結果
まとめ
12
機能分割問題
SW実行時間 ：16[ms]
HW実行時間：8[ms]
HW面積：360[LCs]
M1
M2
SW実行時間 ：8[ms]
HW実行時間：1.5[ms]
HW面積：320[LCs]
M1
制約条件：実行時間40[ms]以下
SW実行時間 ：12[ms]
HW実行時間：2.5[ms]
HW面積：680[LCs]
M3
M4
M2
目的：面積最小化
SW実行時間 ：20[ms]
HW実行時間：11[ms]
HW面積：480[LCs]
M3
M4
SW
0
12
28
48
56
実行時間：56[ms]
実行時間[ms]
13
機能分割問題
SW実行時間 ：16[ms]
HW実行時間：8[ms]
HW面積：360[LCs]
M1
M2
SW実行時間 ：8[ms]
HW実行時間：1.5[ms]
HW面積：320[LCs]
目的：面積最小化
制約条件：実行時間40[ms]以下
SW実行時間 ：12[ms]
HW実行時間：2.5[ms]
HW面積：680[LCs]
M3
M4
SW実行時間 ：20[ms]
HW実行時間：11[ms]
HW面積：480[LCs]
実行時間：56[ms]
面積：0[LCs]
SW
0
面積[LCs]
14
目的：面積最小化
機能分割問題
SW実行時間 ：16[ms]
HW実行時間：8[ms]
HW面積：360[LCs]
制約条件：実行時間40[ms]以下
SW実行時間 ：12[ms]
HW実行時間：2.5[ms]
HW面積：680[LCs]
M1
M2
M3
SW実行時間 ：8[ms]
HW実行時間：1.5[ms]
HW面積：320[LCs]
M1
M4
M3
HW
SW実行時間 ：20[ms]
HW実行時間：11[ms]
HW面積：480[LCs]
M4
実行時間：15[ms]
M2
0
2.5
13.5
15
実行時間
[ms]
15
目的：面積最小化
機能分割問題
SW実行時間 ：16[ms]
HW実行時間：8[ms]
HW面積：360[LCs]
制約条件：実行時間40[ms]以下
SW実行時間 ：12[ms]
HW実行時間：2.5[ms]
HW面積：680[LCs]
M1
M2
SW実行時間 ：8[ms]
HW実行時間：1.5[ms]
HW面積：320[LCs]
M1
M3
SW実行時間 ：20[ms]
HW実行時間：11[ms]
HW面積：480[LCs]
M4
M2
M3
M4
HW
0
680
1040
1520
1840
実行時間：15[ms]
面積：1840[LCs]
面積[LCs]
16
目的：面積最小化
機能分割問題
SW実行時間 ：16[ms]
HW実行時間：8[ms]
HW面積：360[LCs]
制約条件：実行時間40[ms]以下
SW実行時間 ：12[ms]
HW実行時間：2.5[ms]
HW面積：680[LCs]
M1
M2
M3
SW実行時間 ：8[ms]
HW実行時間：1.5[ms]
HW面積：320[LCs]
SW
M1
M4
M3
HW
SW実行時間 ：20[ms]
HW実行時間：11[ms]
HW面積：480[LCs]
M4
実行時間：40[ms]
M2
12
32
40
実行時間
17
機能分割問題
SW実行時間 ：16[ms]
HW実行時間：8[ms]
HW面積：360[LCs]
M1
M2
SW実行時間 ：8[ms]
HW実行時間：1.5[ms]
HW面積：320[LCs]
SW
HW
制約条件：実行時間40[ms]以下
SW実行時間 ：12[ms]
HW実行時間：2.5[ms]
HW面積：680[LCs]
M3
M4
SW実行時間 ：20[ms]
HW実行時間：11[ms]
HW面積：480[LCs]
実行時間：40[ms]
面積：360[LCs]
M2
0
目的：面積最小化
360
面積[LCs]
18
発表内容





背景・目的
機能分割問題
機能分割アルゴリズム
実験結果
まとめ
19
機能分割アルゴリズム
① システムの有向グラフ入力
② 中間領域をハードウェア/ソフトウェア分割
③ ハードウェア領域をハードウェアアクセラレータ/
カスタム命令分割
④ 最小カット容量を求める
最大フロー問題の解法を用いたアルゴリズム
20
中間領域を
ハードウェアとソフトウェアに分割
中間領域
ノード
A
B
C
D
E
エッジ
21
コストの設定
SWコスト：4
HAコスト：5
CIコスト：5
A
SWコスト ：5
HAコスト：3
CIコスト：3
SWコスト ：1
HAコスト：2
CIコスト：2
B
C
SWコスト ：9
HAコスト：7
CIコスト：7
D
E
SWコスト ：9
HAコスト：6
CIコスト：6
定義①： コスト＝実行時間＋面積
22
コストの設定
SWコスト：4
HAコスト：5
CIコスト：5
A
SWコスト ：5
HAコスト：3
CIコスト：3
SWコスト ：1
HAコスト：2
CIコスト：2
B
C
SWコスト ：9
HAコスト：7
CIコスト：7
D
E
SWコスト ：9
HAコスト：6
CIコスト：6
仮定①： HAコスト＝CIコスト
23
コストの設定
SWコスト：4
HWコスト：5
A
SWコスト ：5
HWコスト：3
SWコスト ：1
HWコスト：2
B
C
SWコスト ：9
HWコスト：7
D
E
SWコスト ：9
HWコスト：6
定義②： HWコスト=HAコスト or CIコスト
24
コストの設定
SW-HA間の通信コスト：4
SW-CI間の通信コスト：7
HA-CI間の通信コスト：∞
A
SW-HA間の通信コスト：2
SW-CI間の通信コスト：2
HA-CI間の通信コスト：∞
B
SW-HA間の通信コスト：8
SW-CI間の通信コスト：6
HA-CI間の通信コスト：∞
C
SW-HA間の通信コスト：3
SW-CI間の通信コスト：1
HA-CI間の通信コスト：∞
D
E
SW-HA間の通信コスト：6
SW-CI間の通信コスト：4
HA-CI間の通信コスト：∞
定義③： 通信コスト=通信時間
25
コストの設定
SW-HA間の通信コスト：4
SW-CI間の通信コスト：7
HA-CI間の通信コスト：∞
A
SW-HA間の通信コスト：2
SW-CI間の通信コスト：2
HA-CI間の通信コスト：∞
B
SW-HA間の通信コスト：8
SW-CI間の通信コスト：6
HA-CI間の通信コスト：∞
C
SW-HA間の通信コスト：3
SW-CI間の通信コスト：1
HA-CI間の通信コスト：∞
D
E
SW-HA間の通信コスト：6
SW-CI間の通信コスト：4
HA-CI間の通信コスト：∞
仮定②： HA-CI間の通信コスト=∞
26
コストの設定
SW-HA間の通信コスト：4
SW-CI間の通信コスト：7
HA-CI間の通信コスト：∞
A
SW-HA間の通信コスト：8
SW-CI間の通信コスト：6
HA-CI間の通信コスト：∞
SW-HA間の通信コスト：2
SW-CI間の通信コスト：2
HA-CI間の通信コスト：∞
B
C
SW-HA間の通信コスト：3
SW-CI間の通信コスト：1
HA-CI間の通信コスト：∞
D
E
SW-HA間の通信コスト：6
SW-CI間の通信コスト：4
HA-CI間の通信コスト：∞
仮定③： 上記の通信コスト以外の通信コストは発生しない
27
ネットワークグラフの作成
中間領域
A
B
C
D
E
28
ネットワークグラフの作成
ソース
中間領域
SW
0/5
0/3
0/7
0/6
0/2
A
B
C
D
E
0/1
0/5
青：HWコスト
赤：SWコスト
0/4
0/9
HW
シンク
0/9
29
最小カットを求める
ソース
中間領域
SW
0/5
0/3
0/7
0/6
0/2
A
B
C
D
E
0/1
0/5
青：HWコスト
赤：SWコスト
0/4
0/9
HW
シンク
0/9
30
最小カットを求める
ソース
中間領域
SW
4/5
3/3
最小カット
7/7
6/6
1/2
A
B
C
D
E
1/1
3/5
青：HWコスト
赤：SWコスト
4/4
6/9
HW
シンク
7/9
31
最小カットを求める
ソース
SW領域
HW領域
SW
4/5
3/3
最小カット
7/7
6/6
1/2
A
B
C
D
E
1/1
3/5
青：HWコスト
赤：SWコスト
4/4
6/9
HW
シンク
7/9
32
ハードウェア領域を
ハードウェアアクセラレータとカスタム命令に分割
ソース
SW領域
HW領域
SW
4/5
3/3
最小カット
7/7
6/6
1/2
A
B
C
D
E
1/1
3/5
青：HWコスト
赤：SWコスト
4/4
6/9
HW
シンク
7/9
33
ハードウェア領域を
ハードウェアアクセラレータとカスタム命令に分割
ソース
SW領域
HA領域
SW
4/5
CI領域
3/3
最小カット
7/7
6/6
1/2
A
B
C
D
E
1/1
3/5
青：HWコスト
赤：SWコスト
4/4
6/9
HW
シンク
7/9
34
最小カット容量を求める
最小カット容量：34
ソース
SW領域
SW
4/5
HA領域
CI領域
最小カット
7/7
3/3
6/6
1/2
A
4/4
B
C
3/3
D
E
6/6
1/1
定理： 最小カット容量は機能分割の最小コストに等しい
3/5
6/9
Harold S.Stone, "Multiprocessor Scheduling with the Aid of
4/4
7/9
HW
Network
Flow
Algorithms.",
IEEE
Transaction
on Software
赤：SWコスト
Engineering, Vol.SE-3, No.1,
シンク pp.85-93, January 1977.
黒：SW-HW間の通信コスト
青：HWコスト
35
発表内容





背景・目的
機能分割問題
機能分割アルゴリズム
実験結果
まとめ
36
実験環境
 Terasic Technologies社製 DE2開発学習ボード
 CycloneⅡ（EP2C35 FPGA）※内部にM4K（4kByte RAM）
 NiosⅡ/f（ソフトコアプロセッサ 32bit）
 開発ソフト
 QuartusⅡver9.0
 NiosⅡIDE ver9.0
 SOPC Builder
 ModelSim-Altera ver6.4a 等
 被分割システム
 64点高速フーリエ変換システム
37
PUSH!
緑：ソフトウェア領域
黄：ハードウェアアクセラレータ領域
青：中間領域
送信機
受信機
64点FFT演算器
ROM
RAM
38
入力データ
出力データ
ヘッドシグナル
ステート・マシン
4点FFT演算器
コントローラー
ＲＯＭ
メモリ
メモリ・
マネージャ
ヘッドシグナル
シフト・
レジスタ
RADIX-4
バタフライ
演算器
回転因子
乗算器
39
目的：面積最小化
緑：ソフトウェア領域
出力データ
制約条件：実行時間3000[s]/ 4846.64[s]
入力データ
緑：ハードウェアアクセラレータ領域
ヘッドシグナル
ステート・マシン
4点FFT演算器
コントローラー
ＲＯＭ
メモリ
メモリ・
マネージャ
ヘッドシグナル
シフト・
レジスタ
RADIX-4
バタフライ
演算器
回転因子
乗算器
40
コントローラの処理負荷の割合[%]
20.92
19.09
アドレス保持
ROM読み込み
アドレス計算
24.16
35.82
各演算器の制御
41
FFT実行回数：1,000,000回
目的：面積最小化
制約条件：実行時間3000[s]/4846.64[s]
実験結果
システムの面積[LCs]
システムの実行時間[s]
800
6000
696
700
5000
5004.31
4846.64
5049.69
600
4000
500
400
3000
300
2000
200
100
0
0
56
86
1000
0
3.53
42
発表内容





背景・目的
機能分割問題
機能分割アルゴリズム
実験結果
まとめ
43
まとめ


ソフトウェア/ハードウェア・アクセラレータ/カスタム命令
の3分割に対応した機能分割アルゴリズムを提案・評価
提案手法により分割したシステムを実装した結果、以下
のような結果が得られた

全てハードウェアで実装した場合に比べて面積が約92%減

全てソフトウェアで実装した場合に比べて実行時間が約3%増

制約条件を約40%オーバー
私は実験において、失敗など一度たりともしていない。この方法ではうまく行か
ないということを発見したのだ。
-Thom as Alva Edison-