Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
計算機アーキテクチャ特論
•
前半(並列アーキテクチャの基本、枝廣)
–
10/1, 10/15, 10/22, 10/29, 11/5, 11/12(⽇程は予定)
–
内容(変更の可能性あり)
•
序論(マルチコア=並列アーキテクチャ概論)
•
キャッシュ・コヒーレンシ、メモリ・コンシステンシ
•
並列アーキテクチャモデル、OSモデル
•
スケーラビリティに関する法則
•
並列プログラミングモデル、⾔語
•
後半(最先端トピックス、加藤)
–
11/19, 11/26, 12/3, 12/10, 12/17, (12/25), (1/9), 1/21
–
内容(変更の可能性あり)
•
最先端計算機アーキテクチャのトレンド
•
Very Large Instruction Word (VLIW)
•
Simultaneous Multithreading (SMT)
•
Chip Multiprocessor (CMP)
•
Networks on Chips (NoC)
•
Graphics Processing Unit (GPU)
•
Many Integrate Core (MIC)
Page 1
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
前半の進め⽅
•
講義+理解度テスト (およそ半分の時間)
•
理解度テストが終われば帰ってよい
•
理解度テストの配点:出席=5, 問題=5 (提出=1, Q1=3, Q2=1)
•
アンケート1回 (10点)
–
単位が欲しいのに⽋席が多い場合、要相談
(基本的に前半部に関しては試験もレポートもない)
–
インターンシップなどは配慮する
•
(注)後半の進め⽅は異なる
•
第⼀回アンケート
•
第⼀回講義(概要)、理解度テストはなし
Page 2
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
⽬次
•
マルチコア化の背景
•
マルチコア・アーキテクチャとソフトウェア
のモデル
•
マルチコア向けソフトウェア開発
Page 3
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
あらゆる機器にマルチコア
•
シングルCPU: 性能向上に限界
–
半導体の微細化は継続
–
「低電⼒」または「⾼性能」 (従来は両⽅達成)
•
あらゆる機器にマルチコア
–
厳しい電⼒制約
–
マルチ「低電⼒」CPU
•
サーバー、パソコン、
⾼性能組込機器(携帯、⾞載、情報家電、etc.)
•
ソフトウェアに⼤きな課題: 並列性がなければ今後性能向
上しない
(従来はCPUが新しくなれば勝⼿に性能向上した)
Page 4
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
© NEC Corporation 2010
Page 5
背景:ハイエンドプロセッサでの電⼒傾向
1
10
100
1000
100
1000
10000
Performance (MIPS)
Po
wer
(W
)
Pentium4
PentiumIII
PentiumII
Pentium
PentiumPro
Itanium
Xeon
K6
Athlon
Opteron
Alpha
PowerPC
Sparc
MIPS
Power Limitation
0.35um
0.25um 0.18um
0.13um
90nm
100Wクラスに到達し、これ以上電力は増やしずらくなってきた
(冷却や信頼性確保などでコスト増、
ECOが問われる時代でもある)
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
© NEC Corporation 2010
Page 6
背景:周波数向上だけには頼れない時代に
ハイエンド
MPUの回路は 9FO4 (インバータ9段)に到達
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
© NEC Corporation 2010
Page 7
4
6 8 10
20
40
0.06 0.08 0.10 0.20 0.40 0.60 0.80 1.00 2.00 4.00Physical gate length L
g[nm]
Ga
te
d
ela
y time
CV
/I [p
se
c]
Close: nMOS Open: pMOS LSTP LOP HP ITRS 2003 , nM OS in p rogr es s ∝ Lg 2 ∝ Lg NiSi Fin
長期レンジでは、電力増大問題のみならず、トランジスタ性能
向上にも課題が生じる可能性がある(32nmノードから)。
半導体デバイス・プロセスの研究開発、
ブレークスルー創出がより重要に!
CMOSのマクロ・トレンド
¾
集積度は継続して向上
¾
トランジスタの性能向上は鈍化
(速度や電力のスケーリング)
並列化(面積活用)アプローチ
であるマルチコア化が進展
背景:今後のテクノロジスケーリングが直⾯する課題
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
© NEC Corporation 2010
Page 8
背景:リーク電流の増⼤
•
リーク電流
–
トランジスタの微細化によ
り、漏れ(リーク)が発⽣。
動作していないトランジス
タでも電流消費
–
もはや無視できない⼤きさ
(将来的に動作時電⼒より
も⼤きくなる)
–
⾼速トランジスタほどリー
ク電流は⼤きい
•
リーク電流削減
–
低速プロセッサの利⽤
(⾼性能を達成するために
はマルチコア化が必然)
–
使われていないプロセッサ
は電源OFF
CREST資料より
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
© NEC Corporation 2010
Page 9
マルチコアプロセッサの必要性 (性能電⼒⽐)
CPU
MPEG4
専用
HW
CPU
DSP
CPU
MPEG4 CODEC
実行時の
性能
/電力
他アプリケーションへの適用可能性
ある単一機能を低電力化したい場合、汎用
CPU
よりもヘテロジニアス・マルチコアが有利
性能電力比において
ヘテロジニアス・マルチコアが有利!
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
© NEC Corporation 2010
Page 10
マルチコアプロセッサの必要性 (性能電⼒⽐)
ホモジニアス・マルチコアにより
同じ性能を低電力で達成
性能を並列によって確保し、
動作周波数を下げ低電圧・低電力化
電力の基本式
Power
≅ f x C x V
2
Ferq.
×
C
Voltage
シングルプロセッサ
f x C x V
2
電圧不変
周波数
=> (1/(#PEs))
電力は変わらない
4PEs
(1/4 f) x (4 x C) x V
2
低電圧化
周波数
=> (1/(#PEs))
性能同じで電力低減
4PEs
(1/4 f) x (4 x C) x (Lower V)
2
Power
■動作周波数
1/4、4並列の場合
(1/4f)
×
4C
(1/4f)
×
4C
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
© NEC Corporation 2010
Page 11
マルチコアプロセッサの必要性 (リアルタイム性能)
マルチコアにより、リアルタイム性を向上させ、
性能保証を容易に
処理時間の見通しが悪いシステムは組込みで使いにくい!
シングルプロセッサ方式
CPU
MPEG-4
CODEC
割込み処理
MPEG-4
CODEC
処理時間の見通し:難
割込み等
予測不能要因
キャッシュミス等
予測不能要因
(性能保証のため
大きな
CPU性能
マージンが必要)
マルチプロセッサ方式
CPU
専用エンジン
起動処理
他からの
割込み処理
終了処理
MPEG-4
CODEC
処理時間の見通し:易
時間
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
© NEC Corporation 2010
Page 12
マルチコアプロセッサの必要性
(性能・電⼒スケーラビリティ)
・同じソフトウェアプラットフォームで様々な製品対応
・今後リーク電流が増大する時代に、電力制御容易
CPUx1
CPUx2
CPUx4
SMP対応OS
SMP対応OS
SMP対応OS
TV
専用
HW
DSP
ミドルレンジ
ハイエンド
ローエンド
DSP
CPU
CPU
CPU
CPU
CPU
CPU
CPU
CPU
低負荷時
(電源遮断)
高負荷時
性能
(
正規化)
消費電力(正規化) 0
1
2
3
4
5
6
1
2
3
シングル
プロセッサ
1 CPU
2 CPUs
マルチコア
3 CPUs
Better
シングルプロセッサとの
性能・電力スケーラビリティ比較
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
© NEC Corporation 2010
Page 13
ここまでのまとめ
•
マルチコアは広まっている
•
組込みシステムの性能向上に対し、電⼒や、リア
ルタイム性能の⾯から考えると、DSPや専⽤ハー
ドウェアの追加が有利であり、LSIの微細化と共に
ヘテロジニアス・マルチコアとして進化している
•
ところが組込みシステムであっても、携帯電話関
連等において様々なアプリケーションが実⾏され
るようになり、⾼いCPU性能が要求される分野が
出てきた
•
このような要求に対して⾼い動作周波数のCPUで
対応すると電⼒の⾯で⾒合わなくなるため、パソ
コンと同様、
ホモジニアス・マルチコアの時代に⼊りつつある
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
⽬次
•
マルチコア化の背景
•
マルチコア・アーキテクチャとソフトウェア
のモデル
•
マルチコア向けソフトウェア開発
Page 14
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
マルチコアプロセッサの分類
•
(ハードウェアのAMP vs. SMP)
ヘテロジニアス vs. ホモジニアス
–
ヘテロジニアス:異種コアによるマルチプロセッサ
–
ホモジニアス:同種コアによるマルチプロセッサ
•
(システムの)AMP vs. SMP
–
AMP (Asymmetric Multi-Processor、⾮対称型)
•
各コアが別々のソフトを実⾏(機能分散)
–
SMP (Symmetric Multi-Processor、対称型)
•
OSが複数ソフトウェアを複数コアに負荷分散しながら実⾏
(SMPはホモジニアス型のみ)
•
ただし組込み向けSoCでは様々な専⽤エンジンを搭載するため、全体はヘ
テロジニアス・AMPになり、その中の⼀部のCPUやメディアエンジンが
ホモジニアスAMP/SMPになることが多い
Page 15
DSP
CPU
HW
CPU
CPU
CPU
CPU
CPU
ヘテロジニアス
ホモジニアス
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
SMP型の定義
•
様々な定義がある。
ここでは以下のように考える
–
SMP型=「⼀つのOSで管理
され,すべての処理(タスク,
プロセス,スレッドなど)が
すべてのCPUにおいて対称的
に実⾏可能であるようなマル
チプロセッサによる並列処理
⽅式」
–
AMP型=SMP型以外のもの
•
同じバイナリがすべてのCPUで動作
する必要がある
–
(少なくとも命令セットは)同じCPU
である必要がある=ホモジニアス
–
ホモジニアス・AMP型とSMP型とは
キャッシュ⼀貫性に対するハードウェ
アサポートに違いがある
–
キャッシュの⼀貫性とは?
Page 16
SMP OS
CPU1
CPU2
CPU3
CPU4
SW1
SW2
SW3
SW4
ポイント1:一つの
OS
ポイント2:
対称的に実行可能=
別の
CPUに移すことが可能
(CPU1で動作させ中断していた
ものを
CPU2 で再開することが
可能。問題はキャッシュに一時
保存しているデータの扱い)
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
キャッシュと対称的動作
• SW1をCPU1からCPU2に移したとき、キャッシュにデータが
残っていると正しく動作しない?
Page 17
メモリバス
1.
SW1があるメモリ番地
から値3を読む
メモリバス
2.
SW1が値を4に
書き換える
3
CPU1
CPU2
3
→4 キャッシュ
SW1
3.
SW1をCPU1からCPU2に
移して同じメモリ番地から
データを読んだとき、
キャッシュにデータが残って
いると正しく動作しない?
3
CPU1
CPU2
3
→4 キャッシュ
3?
SW1
SW1
3
CPU1
CPU2
3
キャッシュ
SW1
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
AMPとSMPの違い
(キャッシュの⼀貫性(coherency) (1))
Page 18
3
3
CPU1
CPU2
3
→4
メモリバス
キャッシュ
3?
AMP型(ハードウェア
サポートなし)
CPU1
CPU2
3
→4
共有メモリ
4
SMP型 (キャッシュの
Snoop(盗み見)機構)
AMP型の場合、キャッシュ一貫性を保つた
めのハードウェアサポートがない。そのた
め
SW1を移動後にメモリ上の同じデータを
使いたい場合、キャッシュの内容を一度共
有メモリに戻す必要がある。そのオーバー
ヘッドが大きいため、別CPUに移すことは
普通は考えない。
SMP型では隣のCPUのキャッシュの内容
を盗み見る(Snoop)ハードウェア機構を
持つ。
そのため、比較的容易に
SW1をCPU1か
ら
CPU2に移すことができ、「対称的動作」
が可能になる。
キャッシュ
SW1
SW1
SW1
SW1
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
AMPとSMPの違い
(キャッシュの⼀貫性(coherency) (2))
Page 19
3
3
CPU1
CPU2
3
→4
メモリバス
キャッシュ
3?
AMP型(ハードウェア
サポートなし)
CPU1
CPU2
3
→4
共有メモリ
4
SMP型 (キャッシュの
Snoop(盗み見)機構)
AMP型の場合、SW2でメモ
リ上の同じデータを使いたい
場合、
SW1はキャッシュの内
容を一度共有メモリに戻す必
要がある。
SW1からSW2への「通信」を
プログラムに明示的に書く
SMP型では隣のCPUの
キャッシュの内容を盗み見
る(
Snoop)ハードウェア機
構を持つ。ソフトでは気に
せずに
SW1とSW2のデー
タ共有ができる。
(オーバーヘッドが小さい)
キャッシュ
SW1
SW2
SW1
SW2
CPU1
3
→4
キャッシュ
シングル
プロセッサ
3
SW1
SW2
共有メモリ
メモリバス
シングルプロセッサの場
合
SW1もSW2も同じ
キャッシュから読むので、
オーバーヘッドなく正しい
値が読める
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
AMPとSMPの違い(まとめ)
•
SMP型=「⼀つのOSで管理され,すべての処理
(タスク,プロセス,スレッドなど)がすべての
CPUにおいて対称的に実⾏可能であるようなマルチ
プロセッサによる並列処理⽅式」
–
SMP型にはホモジニアスしかない
–
SMP型は⼀つのOSがすべてのソフトウェアを動的に負荷
分散しながら実⾏する
–
AMP型は、各プロセッサにOS
*
を持ち、各プロセッサが
実⾏するソフトウェアが静的に決められている
* プロセッサ管理のみの簡易的な基本ソフトウェアも含む
–
従ってAMP型はそれぞれのプロセッサがサブシステムと
なる
Page 20
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
マルチコアプロセッサの分類
Page 21
▐
ヘテロジニアス・AMP
▐
ホモジニアス・SMP
SMP OS
CPU CPU CPU CPU
SW1 SW2 SW3 SW4
▐
ホモジニアス・AMP
HW&SW一体でサブシステム最適化
・サブシステム内変更が他に影響しにくい
→ リアルタイム性確保や、テストで有利
・ヘテロジニアスでは電力・性能・コスト面で
最適なHWを選択
・ホモジニアスではHWを同一化。SW環境を
同じにしつつサブシステム分離性確保
・SW-HWの割り当ては固定的
→ HW能力に分割損が発生しがち
OSがSWモジュール(スレッド)を
動的にHWへマッピング
•SWモジュール変更が全体性能に影響
→ リアルタイム性確保やテストで不利
•SW機能のマッピング自由度が大
→ HW能力の分割損は発生しにくい
CPU
SW1
CPU
SW2
CPU
SW3
CPU
SW4
OS
OS
OS
OS
CPU
SW1
DSP
SW2
HW1
SW3
HW2
SW4
OS
OS
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
AMP型マルチコアシステムのリアルタイム性
22
a) 1CPU
b) 3CPU
Delay from Scheduled Time (= Points above 40ms)
→Discontinuity of Audio & Video
Many Delays
Time
Execute Time for Periodical Processes
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
SMP型マルチコアシステムのスケーラビリティ
•
⼿ぶれ補正処理
–
シャッタースピードを遅くすると
⼿ぶれ発⽣。速くすると暗くなる (I,
II)
–
シャッタースピードを速くしつつ、
複数枚撮影し、画像補正 (III)
–
画質を⾼くすればするほど
⾼いCPU性能が必要
0
0.5
1
1.5
2
2.5
3
3.5
1
2
3
4
Number of Processors
Speedup
QVGA
VGA
Page 23▐
並列性能向上率
(1CPU対4CPU)
--- VGA: 2.94倍, QVGA: 3.15倍
(II) fast shutter:
dark but not blurry
(I) slow shutter:
bright but blurry
(III) bright and not blurry
Image
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
マルチプロセッサの分類
Page 24
AMP
SMP
ヘテロジニアス
CELL(ソニー、東芝、
IBM)
Uniphier(松下)
MeP(東芝)
EMMA(NEC)など
ホモジニアス
MP211(NEC)
FR-1000(富士通)
など
MPCore(NEC)
SH-X3(ルネサス)
など
(
SoC中の主たる構成部分における分類であり、実際には混在している)
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
ヘテロジニアス・AMPの例: CELL
•
ハードウエアを簡単化して極⼒ソフトにオフロード、⾼クロックを重視
HW/SWのライフタイムが⻑いゲーム⽤途からの展開を配慮
Page 25
同一構造をした多数の
SPEを結
合しメディアエンジンを構成し、
ひとつのホストプロセッサである
PPEを結合する.
(PPE:管理コア/OSが走行:
PowerPCベース,
SPE:小型DSP-メディアエンジン
8個のSPEはホモジニアス・
AMPと考えることもできる)
出展: 10.2 The Design and Implementation of a First-Generation CELL Processor, D. Pham, et.al ISSCC 2005
PPE
SPE
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
ヘテロジニアス・AMPの例: UniPhier
Page 26
出典: 日経エレクトロニクス
2004.10.11
▐
コスト・電力を考慮、すべてをシングルチップ化
情報家電向け
基本ユニットである命令並列コア(IPP)に、アレイ拡張可能なDPP、ハードウエアア
クセラレータを追加し、メディア処理部であるUniPhierプロセッサを構成する。さら
に汎用コア(ホストプロセッサ)を結合する。
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
ヘテロジニアス・AMPの例: MeP
Page 27
出典: http://www.MepCore.com/
ホストプロセッサ:
ARM or MIPS (TX)
CPU部
メディア処理部
命令やアーキテクチャを個別(ヘテロ
ジェニアス)に拡張したプロセッサを疎
結合しメディア処理部を構成し、
ひとつのホストプロセッサで制御する。
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
ホモジニアス・AMPの例: MP211
•
ARM926(200MHz)×3, DSP(200MHz),
Graphics Engine, Image Processor, Security Engine, etc.
•
CPUはARM3個のホモジニアス・AMPであるが、SoC全体でみると
多くの携帯電話向けエンジンを搭載したヘテロジニアス・マルチコ
ア
Page 28
MP211
-130nm
-8.9mm角
ARM926 PE0 ARM926 PE1 ARM926 PE2 USB OTG DMAC DSP SPX-K602 3DAcc. Rotater ImageAcc. CamI/F LCD I/F
Multi
-Layer AHB
SRAMIF On-Chip SRAM (512KB) Scheduler
Quad BUS
Interface
Frame Cache SDRAM Controller DDR SDRAMMobileDDR SDRAM APB Bridge1 TIM0 INTC uWIRE SIO PMU Async Bridge0 Async Bridge1 APB Bridge0 I2C PCM WDT FLASH LCD Camera BaseBand GPIO SMU Inst. RAM OSC PLL Mem. Card UA RT TIM3 TIM2 TIM1Always On
Area (Logic0)
Power Switched
Area (Logic1)
SIO NSTC I/F DTVI/F CCP I/F出展: S. Torii et al., “A 600MIPS 120mW 70uA
Leakage Triple-CPU Mobile Application
Processor Chip,” ISSCC2005
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
ホモジニアス・SMPの例: MPCore
•
ARM11™ ベース(VFP:浮動⼩数点演算ユニット) 1〜4コア構成
•
SCU (Snoop Control Unit) によりキャッシュの⼀貫性をハードウェ
アで保証。⾼効率なSMPを実現
•
負荷量に応じ動的にコア電源のON/OFFが可能
•
AMPモード、ハイブリッド(AMP+SMP)モードも可能
Page 29
PE0 PE2
PE1
SCU
PE3FPU
Snoop Control Unit (SCU)
I & D64bitbus Coherence Control Bus Primary AXI R/W 64bit bus Optional 2nd AXI R/W 64bit bus Private lines
Interrupt Distributor
Configurable number of hardware interrupt linesIRQ Configurable SMP (1 and 4 PEs) Per CPU Peripheral s
CPU/VFP
L1 Cache
CPU/VFP
L1 Cache
CPU/VFP
L1 Cache
CPU/VFP
L1 Cache
Timer Wdog CPU interface Timer Wdog CPU interface Timer Wdog CPU interface Timer Wdog CPU interface出展: P. Middleton, “A New ARMv6
Symmetric Multiprocessing Core”,
Embedded Processor Forum, 2004
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
タスク並列のメリットを⽣かし
ながらスケーラビリティも実現
•
SMP LinuxのAffinity: タスクを
固定的に特定CPUに割り付け可
能
•
AMP-SMPハイブリッド
•
リアルタイム系連携タスクと、
⾼度なマルチメディアタスクが
混在する今後の組み込みシステ
ムに適合
Page 30
MPCore
RTOS
SMP Linux
Task
F
CPU
OS
Task
F
CPU
Task
C
Task
B
Task
A
Task
D
Task
E
シングルCPU, マルチタスク
マルチCPU, マルチタスク、マルチスレッド
Task
E
Task
C
Task
B
Task
A
Task
D
MMタスクを
自動負荷分散
固定割付
タス
クF
Snoop Cache
CPU CPU CPU
スレッド化された
タスクA~D
CPU
CPU
CPU
制御系連携
タスク
CPU
タス
クE
Cache
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
⽬次
•
マルチコア化の背景
•
マルチコア・アーキテクチャとソフトウェア
のモデル
•
マルチコア向けソフトウェア開発
Page 31
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
マルチコア 活かすも殺すも ソフト次第
•
ソフトが複数のコアを有効利⽤しなければマ
ルチコアの意味が無い
•
システム、ソフトウェアの並⾏処理、並列処
理
–
並⾏・並列化の種類
•
複数ソフトウェアの並⾏処理(機能分割)
•
単⼀ソフトウェアの並列処理(スレッド化など)
–
アルゴリズム、システムロジックが並列・並
⾏実⾏可能
•
分割可能、依存がない
–
プログラムが並列・並⾏実⾏可能に記述
Page 32
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
アルゴリズムが並列実⾏可能 (1)
•
アルゴリズムが並列実⾏可能でなければマル
チコア上で性能向上しない
–
例:総和(1から1000000までの和を求め
る)
int i, sum;
for (i=1,sum=0; i<=1000000; i++) {
sum += i;
}
return sum;
–
i=k-1の時のsumの値を⽤いて i=kの時の
sumを計算するため、並列化は難しい
Page 33
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
アルゴリズムが並列実⾏可能 (2)
•
並列実⾏可能なアルゴリズム
–
例:総和(4コアで1から1000000までの和を求める)
int i, j, p, sum;
for (p=0,sum=0; p<4; p++) {
for(i=0,j=p*250000+1,s=0; i<=250000; i++, j++) {
s += j;
}
sum += s;
}
return sum;
–
4コアで並列実⾏可能。変数i, j, sをコアごとの局所変数とし
て割り当てて計算し、最後にそれぞれのコアの結果sを集計
(注意:現状の⾃動並列化コンパイラでは、前⾴のプログラム
から⾃動的に上記のような並列化は⾏われる。従ってア
ルゴリズム変更が必要な場合は、より複雑な例となる。)
Page 34
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
システムロジックが並⾏実⾏可能
Page 35
START
処理
A 処理B 処理C 処理D
END
START
処理
A
処理
B
処理
C
処理
D
END
処理の
依存関係
並行実行で性能向上する例 並行実行で性能向上しない例
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
プログラムが並列・並⾏実⾏可能に記述
•
AMP型とSMP型
–
AMP型はプロセッサごとの(別々のOS上の)プログラムとな
り、プログラム間の同期・通信を記載する。CPUへのタスク
(スレッド)割り当てはプログラム時に静的に⾏われる
–
SMP型はSMP OS上の⼀つのプログラムとなり、同期・通信も
含め、並列化⽀援⾔語・APIとして記載する。SMP OSが負荷
分散を考慮しながら動的にタスク(スレッド)をプロセッサに
割り当てる
Page 36
タスク7
タスク3
タスク5
タスク2
タスク1
タスク4
タスク6
タスク7
タスク3
タスク5
タスク2
OS
CPU1
OS
CPU2
OS
CPU3
SMP OS
CPU1
CPU2
CPU3
CPU1向け
プログラム
CPU2向け
プログラム
CPU3向け
プログラム
タスク1
タスク4
タスク6
並列化プログラム
AMP型
SMP型
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
プログラムが並列・並⾏実⾏可能に記述
•
AMP型のプログラム
–
同期・通信以外は通常のソフトウェア
•
SMP型のプログラム
–
スレッド・プログラミング
•
その他
–
ヘテロジニアス・マルチコア向け
•
OpenCL
–
GPU向け
•
CUDA
Page 37
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
AMP型マルチコアの同期・通信(起動・終了)
•
起動:CPUから専⽤エンジンのレジスタに書き込み
•
終了:
–
専⽤エンジンからCPUへの割込み
–
専⽤エンジンのレジスタをCPUからポーリング
•
起動・終了に多少の時間オーバーヘッドがある
–
変数共有を考えなくても数⼗〜数百サイクル必要
–
(SMP型のような)変数共有を考えるならば1変数
を1回共有するのにさらに数⼗〜数百サイクル必要
Page 38
CPU
専用エンジン
起動処理
他からの
割込み処理
終了処理
MPEG-4
CODEC
CPU
MPEG-4
専用
HW
Reg.
時間
ソフトウェアモデル
ハードウェアモデル
(AMP型)
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
AMP型マルチコアの同期・通信(共有メモリ)
•
AMP型ではデータ共有オーバーヘッドが⼤きいため、画像データ転送など
を除き、可能な限りメモリ共有しない
•
共有メモリを⽤いたプロセッサ間データ授受
–
専⽤エンジンでデータを使う前に、必要なデータが
CPUのキャッシュからメモリに戻されている必要あり
–
キャッシュ無効化などの処理が必要となり、
同⼀プロセッサでのデータ授受より時間オーバーヘッドがあ
る
•
データ書込後、起動・終了または割り込みなどで通知
Page 39
CPU
MPEG-4
専用
HW
Reg.
ソフトウェアモデル
ハードウェアモデル
Mem
CPU
専用エンジン
起動処理
終了処理
MPEG-4
CODEC
時間
データ書込
データ読込
データ書込
データ読込
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
スレッド化プログラミング
•
スレッドライブラリの例
–
pthread
•
IEEEのPOSIX Section 1003.1c規格
POSIX: Portable Operating System Interface
•
Linuxなどで標準的にサポート
–
Java Thread
•
Java⾔語の中に標準で定義
–
OpenMP
•
C/C++/FORTRANを並列プログラム可能にするために
⽶国コンパイラベンダグループによって作られた指⽰⽂
•
パソコン向けの開発環境などで標準的にサポート
–
TBB
•
Intel社が開発した⾔語。OpenMPと似ているレベルで
あるが、動的な負荷分散などをランタイムで⾏う
–
TPL
•
Microsoft社の⾔語。同様のレベル。 .NETに含まれる
参考⽂献: Nichols, Buttlar, and Farrell(榊 訳): 「PThreads プログラミング」、オライリー・ジャパン、1998
: Oaks and Wong(⼾松、⻄村 訳): 「Javaスレッドプログラミング」、オライリー・ジャパン、1997
: http://www.openmp.org/
: James Reinders (菅原 訳):「インテル スレッドビルディングブロック」、オライリー・ジャパン、2008
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
41
-スレッド化プログラミング(OpenMP)
•
OpenMPでの記述例(銀⾏系サーバの例)
–sections
指⽰されたブロック内の
各sectionは並列実⾏可能
#pragma omp parallel sections
{
#pragma omp section
main();
#pragma omp section
withdraw();
#pragma omp section
deposit();
#pragma omp section
balance();
}
–sections
の”}”において同期する。
(つまりすべてのsectionが終了後に待ち合わせ
る)
銀行系サーバ
main()
メインスレッド
withdraw()
支払スレッド
deposit()
預金スレッド
balance()
残高スレッド
顧客リ
ク
エ
ス
ト
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.
ERTL
ERTL
42
-スレッド化プログラミング(OpenMP)
•
OpenMPでの記述例(画像復号処理の例)
–for
指⽰されたループは並列実⾏可能
#pragma omp parallel for
for(i=1; i<=N; i++)
復号処理#i;
画像復号処理
複号
処理
#1
複号
処理
#2
複号
処理
#3
複号
処理
#5
複号
処理
#8
複号
処理
#7
複号
処理#
4
複号
処理
#5
Graduate School of Information Science, Nagoya Univ. Embedded and Real-Time Systems Lab.