システムLSIとアーキテクチャ技術 (part III:チップ

その他の並列アーキテクチャ
コンピュータアーキテクチャ特論
hunga@am.ics.keio.ac.jp
テキスト pp.10-12(該当個所なし)
Fine grain
SIMD
Coarse grain
マルチプロセッサ
バス結合型UMA
スイッチ結合型UMA
コントロール
フロー制御
MIMD
Simple NUMA
NUMA CC-NUMA
COMA
NORA マルチコンピュータ
データフロー制御
その他 混合制御
要求駆動
シストリックアレイ
SIMD
•全プロセッサが同一命令で
動作
•柔軟性が低い
命令メモリ
命令
演算プロセッサ
データメモリ
SIMD型の分類

粗粒度型:各ノードで浮動小数点演算処理が可
能
– ILLIAC-IV,BSP,GF-11
– 最近の高性能CPUのマルチメディア命令

細粒度型:各ノードは1bitまたは数bitの演算しか
できない
– ICL DAP, CM-2,MP-2
– コネクションマシンは応用分野を人工知能に拡大
(CmLispの功績)
CM-2のプロセッサ
Flags
A
B
F
OP
s
256bit
memory
c
C
Context
1bit serial ALU
CM2のプロセッサチップ
4096チップで
64K PE
命令
1チップ構成
Router
P
P
P
P
P P P
P P P
P P P
P P P
4x4 Processor Array
12links 4096 Hypercube
connection
256bit x 16 PE RAM
SIMD型の将来

粗粒度SIMD
– 大規模なものの復活はないだろう
– マイクロプロセッサの高速化技術として小規模
なものが生き残る

細粒度SIMD
– 画像処理等で圧倒的に有利
– CM2 → CM5のようにマルチプロセッサ化し
た方が性能が高い
シストリックアーキテクチャ
Data列x
演算アレイ
Data列y
特定の演算能力を持つアレイ列に一定の間隔で
リズミカルにデータを送りこみ、並列演算
帯行列の行列積 y=Ax
y0
a11 a12 0
0
x0
y1
a21 a22 a23 0
x1
0
a32 a33 a34
x2
0
0
x3
y2
=
y3
a43 a44
a
yi
yo
x
X+
yo= a x + y i
帯行列の行列積 y=Ax
a11 a12 0
0
a21 a22 a23 0
a23
a32
a22
a12
a21
a11
X+
x1
0
a32 a33 a34
0
0
a43 a44
帯行列の行列積 y=Ax
a11 a12 0
0
a21 a22 a23 0
a33
a23
a32
a22
a12 y1=a11x1
a21
X+
x2
X+
x1
0
a32 a33 a34
0
0
a43 a44
帯行列の行列積 y=Ax
a11 a12 0
0
a21 a22 a23 0
a34
a43
a33
a23
0
a32 a33 a34
0
0
a32
a22
y1=a11 x1+
a12 x2
y2=a21 x1
X+
x3
x2
x1
a43 a44
帯行列の行列積 y=Ax
a11 a12 0
a21 a22 a23 0
a44
a34
a43
a33
a23 y2=a21 x1+
a32
a22 x2
X+
x3
0
X+
x2
0
a32 a33 a34
0
0
a43 a44
帯行列の行列積 y=Ax
a11 a12 0
0
a21 a22 a23 0
a44
a34
0
a32 a33 a34
0
0
a43
y2=a21 x1+
a22 x2+
a23 x3
a33 y3= a32 x2
X+
x3
x2
a43 a44
シストリックアーキテクチャの
特長




入出力ピン数が少ない
単純な同期制御
近接接続のみで構成可能
1980年代Kungらの提案により注目された
がLSI実装面積の不足により普及しなかっ
た
他の「VLSIアルゴリズム」と共に復活の可能性
データフローアーキテクチャ



データをトークンとして考え、到着と共に計
算処理が駆動される。
記憶要素を明示的に指定しない。
アルゴリズムの持つ並列性を最大限に引
き出すことができる。
データフローグラフ
d
a
b
c
+
e
x
+
x
(a+b)x(c+(dxe))
命令実行サイクル
命令読み出し
データ待ち合せ
データ読み出し
命令読み出し
命令実行
命令実行
データ格納
あて先指定
通常のプロセッサ
データフローマシン
データフローマシンの問題点





純粋なデータフローマシン(Dennisのマシ
ン)は無駄が多い。
色付きトークン等の導入でデータフローグ
ラフの再利用。
構造の複雑化
演算器レベルの処理時間とそれに要する
時間の比率の問題
局所性の無視
日本はデータフローマシン研究
の世界的な中心(だった)




電総研 Sigma-I :科学技術用
電総研 EM-4/EM-X:演算の粒度を高める
工夫
NTT DFM:関数型言語を指向。Lenient
Consの提案
NEC ImPP:画像処理用のチップ。商用
化を目指した
要求駆動マシン(リダクションマ
シン、デマンドドリブンマシン)
Z:(/,x,y)
x: (+,a,b)
a: (3)
y: (-,a,b)
b: (5)
要求駆動マシン

値が必要になった時点で計算を駆動
– cf. データフローマシン
– データフローマシンに比べて並列性は小さい
が、無駄は少ない(のではないか)

実装例はほとんどない(どうやって実装す
るんだ??)
Reconfigurable System
(Custom Computing Machine)

SRAM型プログラマブルデバイスから構成
されるシステム上で問題の解法アルゴリズ
ムを直接ハードウェア化して実行する
– 専用マシンのスピード
– 汎用マシンの柔軟性

プログラム格納型計算機とはまったく異な
る原理でしかも堂々たる体系を作ることが
できる
5入力テーブル
SRAM型FPGA
(Field Programmable Gate Array)
2 F.F.
I/O
Logic Block
Switch
SRAM(Configuration Memory)
SRAM型CPLD
(Complex Programmable Logic Device)
I/O
Logic Block
Switch
SRAM(Configuration Memory)
最近の状況





Xilinx社Virtex、ALTERA社APEX等新世代が登
場
ゲート数は500Kゲートに及ぶ(メモリ等を換算する
場合が多いが、、、)
最大動作周波数は設計次第だが30MHz程度な
らば容易に実現可能
内部データ格納用SRAM
Partial Reconfiguration、マルチコンテキスト等
の新機能を持ったデバイスの登場
Reconfigurable Systemの分類

スタンドアローン型
– 独立性の高い専用システム
– Splash 1・2, RM-I,II,III,IV, RASH(三
菱)、ATTRACTOR(NTT)

コ・プロセッサ型
– 汎用プロセッサの一部の処理を高速化
– PRISM I,II、DISC-II、PipeRench、
CHIMAERA,Chameleonなど
Reconfigurable Systemの発達
Stand Alone Co-processor
1990年 第1回FPL
SPLASH
1992年 第1回Japanese SPLASH-2
FPGA/PLD Conf.
RM-I
RM-II
1993年 第1回FCCM
RM-III
RM-IV
YARDS
1995年
RM-V
2000年
PRISM-I
PRISM-II
New Device
MPLD
WASMII
Cache Logic
DISC
DISC-II
Mult.Context
FPGA
HOSMII
ATTRACTOR
FIPSOC
Cont.Switch.FPGA
RASH
PipeRench
DRL
PCA
CHIMERA
Chamereon
Splash-2 (Arnoldら 92)





米国計算機科学セン
ター
文字列検索、画像処理、
DNAの塩基配列間の
距離を求める問題で
Cray-IIの330倍の性能
を発揮
直線シストリックアレイ
構造
VHDL, 並列Cによる
プログラミング
Annapolis Micro
Systems社より商用化
Splash-II




米国計算機科学センタ
文字列検索、画像処理、DNAの塩基配列
間の距離を求める問題でCray-IIの330倍
の性能を発揮
直線アレイ構造
VHDL,並列Cによるプログラミング
RM-IV(神戸大学)
mem.
FPGA
FPGA
mem.
mem.FPGA
FPGA
mem.
mem.
FPGA
FPGAmem.
mem.
FPGA
FPIC
FPGA
FPGA
mem.
FPGA
mem.
mem.FPGA
FPGA
mem.
mem.
mem.
FPGA
FPGAmem.
mem.
FPGA
FPGA
Interface
mem.
RASH
(三菱電機)
CompactPCI bus
EXEボード
CPUボード
ディスプレイ
Ethernet
LAN
CD
RASH unit
disk
1Unit: 最大6枚のEXEボードとCPUボード(Pentium)
複数のUnitを接続可能
This slide is supported by Dr.Nakajima of Mitsubishi.
&p
32
EXEボードの構成
PCI-bus
リンク接続とバス接続
PCI-bus I/F
PCI Local-bus
EXE-board controller
FPGA
FPGA
SRAM
(2MB)
Clocks/Cont. signals
Local-bus
FPGA
FPGA
2系統のクロック
PCIバスI/F
SRAM搭載
DRAM付加ボード搭載可
FPGA
FPGA
FPGA
FPGA
FPGA Altera FLEX10K100A (62K-158KGate)
&p
33
ATTRACTOR(NTT)
高速シリアルリンク
(1Gbps)
ATM
I/O
RISC
FPGA
RAM
(LUT)
ATM
SW
FPGA
Buffer
RISC
RISC
RISC
RISC
RISC
Ethernet
ATM通信処理に
特化したシステム
MPU
Mem.
Compact PCI
多種類のボードを接続
ボードレベルで再構成可能
RHiNETー1/NI
(RWCP+Keio U.)
NI board
Interconnecting PC nodes
with flexible NI
RHiNET-1/NI: Flexible Interface
Various message
handling primitives
can be changed
Optical
Interconnect
FIFO
Packet Buffer
Twin Memory
Primitive Handler
(FLEX10K)
Region Buffer
Address Translate
Table
PCI Interface
RHiNET-1/NI
Optical Interconnection Module

133MHz operation 1.5Gbps
bandwidth
コ・プロセッサ型



Core CPUと密接続
プログラムの一部を高速化
最近、Core CPUと同一チップ上に実装
が可能になり、様々なシステムが提案され
ている
– NAPA, Garp, Chameleon, Chimaera,
PipeRench
PRISM II(Brown大学)
Am2955
CPU
Data
Address
Control
Boot ROM
DRAM
Burst Mode
Memory Controller
Switch
DRAM
FPGA Module
FPGA Module
FPGA Module
プログラムのよく使う部分を高速化
コプロセッサ型の元祖
Garp (Hauserら 97)
Memory queue




UCBのプロジェクト
MIPSコアとReconfigurable
Arrayが強結合しメモリ階層
を共有
コンパイラの静的解析によ
りループ処理を抽出しハー
ドウェア化
画像処理などでUltrasparc
の43倍の性能
MIPS
Cache
Q Q Q
Crossbar
32bit buses x 5
Reconfigurable Array
DISC (Wirthlinら 95)



Brigham Young大学
動的な部分書き換え機能を
用いた汎用プロセッサ
任意のカスタム命令を基本
命令セットに追加可能
– 各モジュールをユーザが設計
– C言語上から関数として利用

FPGA 3
Processor
Core
System
Memory
FPGA 1
FPGA 2
Bus I/F
Configuration
Controller
Custom
Instruction
Space
FPGAをカスタム命令モ
ジュールのキャッシュのよう
に使用
Host P/C
CHIMAERA (Yeら 2000)





Northwestern大学
スーパスカラプロセッ レジスタ
ファイル
サのデータパスに可
変構造アレイを挿入
シャドウレジスタファ
イルから9レジスタを
一度に読込み
uPコア
Out of Order制御
10~20%の高速化
シャドウレジスタ
ファイル
可変構造
アレイ
コントローラ
Chameleon(Chameleon社)

Field Programmable System Level
Integrated Circuits (FPSLICs)
– 疎粒度のReconfigurable Processing
Fabric、RISC Core、PCI Controller、
Memory Controller、DMA Controller、
SRAMを1チップ上に混載
– 信号処理、通信プロトコル処理用、高速DSP
の5-10倍の性能
Chameleon CS2112
32-bit PCI Bus
64-bit Memory Bus
Memory
RISC Core
Controller
PCI Cont.
128-bit RoadRunner Bus
Configuration
Subsystem
DMA
Subsystem
Reconfigurable
Processing
Fabric
160-pin Programmable I/O
CTL中の最大8命令をDPU中で
実行可能
Reconfigurable Processing Fabric
の構造 CTLは、同じサイクルで次の命
令を決定可能
LM
DPU 新しいbit
CTL
LM DPU
streamをloadする
ことで構成を変えられる
Tile 0
Slice 0
CTL
Tile 0
Slice 3
108のDPU(Data Path Unit)が4つのSlice(各3Tile)を構成
1Tile: 9DPU=32bit ALU X 7 16bit + 16bit乗算器 X 2
DPUの構成
OP:C、Verilog演算子サポート
DPU単位のSIMD,パイプライン
Routing
MUX
Routing
MUX
Instruction
Register
&
Mask
Barrel
Shifter
OP
Register
&
Mask
Register
Register
Reconfigurable Systemの
問題点




SRAM型FPGAの演算器は専用
CPU,DSPよりも10倍遅く、10倍集積度が
劣る
メモリとの接続が脆弱
アルゴリズムを変換するための標準的方
法が存在しない
問題サイズがシステムサイズを越えるとお
手上げ
問題の解決 1

SRAM型FPGAの演算器は専用CPU,DSPより
も10倍遅く、10倍集積度が劣る
– 最新のプロセス利用により差が縮まる
– 粗粒度FPGA
– CPUとの混載

メモリとの接続が脆弱
– 大規模SRAMとの混載
– DRAM混載
FPAccA(広島市立大)
Routing
Matrix
Array of floating
ALU(Add/Mult)
model2(0.35um)
ALU
12x 25MFLOPS
Communication centric FPGA
Proteus-Lite (NTT)
Programmable Interconnection
(Directional)
Logic Block
(Lookup Table)
Latches
Wide
Bit
F
D
F
D
Pipelining (Synchronous)
Large number of latches
This slide is supported by Dr.Miyazaki of NTT.
Structure of PROTEUS-Lite
PROTEUS-Lite
IOC: I/O Cell
BC: Basic Cell
Middle Lines
Long Lines
This slide is supported by Dr.Miyazaki of NTT.
DRAM混載型FPGA(NEC)
Logic
Element
256 X 256
DRAM
Module
Word Driver(128)
Sense Amp.(128)
Logic
Element
Sense Amp.(128)
Word Driver(128)
Logic
Element
Logic
Element
問題の解決 2

アルゴリズムを変換するための標準的方法が存
在しない
– CPUとの混載、分担処理
– DA,Compile技術の発展
– データフロー型実行

問題サイズがシステムサイズを越えるとお手上
げ
– Partial Reconfiguration
– Multi-context FPGA
– 仮想ハードウェアの研究が進む
PCA(Plastic Cell
Architecture)
16word x 1bit
memory(LUT)
12コマンドを実行する
ハードウェアコントローラ
16bits
output: 1bit
14bits
Built-in
Part
input: 1bit
Logic/メモリ
Plastic
Part
16bits
0
14bits
control: 6bits
data: 8bits
可変部
基本セル→これが
さらに格子状接続
する
7
7
双方の利用可
マルチコンテキストFPGAの基本
構造
PAGE1
Logic Cells
Multiplexer
PAGE2
PAGE3
ページ間の共有
Partial Configuration との組み合わせ
DRL(NEC)は実際に利用可能
SRAM型マルチコンテキスト
FPGA (基本的なもの)



MPLD(Multi-functional Programmable
Logic Device) 富士通,1990
WASMII 慶大,1992
Time Multiplexed FPGA,Xilinx,1997
マルチコンテキスト型FPGA
(最近の実現例)

FIPSOC(Field Programmable System On
Chip)
– 混載チップ、2 Context、片方を利用中にもう片方を
設定可

Context Switching FPGA, Sanders A
Lockheed Martin Company
– コンテキスト間のデータ共有
– Partial Configuration

DRL, NEC
– 8 Context,部分的な切り替え可能
CSRC Device
(Context Switching Reconfigurable Computing)
Clock Enable



あるContextがActiveの間で
も、別のContextを
Download可能
Contextの切り替えに5ns
Private/Public Addressable
Sharing (P/PASS)
4 Input
ROM
(Look Up Table)
D
Q
MUX
F/F
Back Up
RAM(SRAM)
MUX
EN
動的再構成ロジックDRL


マルチコンテキスト構成を持つ部分再構成可能な論
理デバイス(8コンテキスト)
チップ全体の構成
– 4×12の論理ブロック(Logic Block, LB)
– 外部入出力用の制御回路

論理ブロックの構成
– 4×4の統合セル(Unified Cell, UC)
– 動的再構成制御回路(Reconfiguration Controller, RC)
– バスコネクタ(Bus Connector, BC)
DRL
Configuration Store
Address(10b)
LB:論理ブロック
Input Selector
Configuration/Data Input(79b)
LB LB LB LB LB LB LB LB LB
Global
Bus
Switch
BC BC BC
LB LB LB LB LB LB LB LB LB
LB
RC
BC
UC UC UC
Memory
LB LB (4b×2)
LB
BC
Data
(4b×2)
LB LB Config
LB
(3b×2)
UC
LB LB LB LB LB LB LB LB LB LB LBHorizontal
LB
BC
UC UC UC UC
BC
UC UC UC UC
BC
UC UC UC UC
Local Bus
(4b×2)
LB LB LB LB LB LB LB LB LB LB LB LB
Input
Select
External Config.
Control(4b)
Config. Store
Control(2b)
Reset
CLK
Output
Select
Configuration/Data Output(79b)
Vertical Local Bus
Data Config
(4b×2)
(4b×2) (3b×2)Address Decoder
Output Selector
UC:統合セル
RC:再構成制御回路
BC:バスコネクタ
WASMIIアーキテクチャ
トークンルータ




アプリケーションをデー
タフローグラフで表現
1ページに収まる単位
のサブグラフに分割
チップ内のコンテキスト
数は4から8程度
外部メモリからの結線
情報の読み込みがボト
ルネック
Active Page
コンテキスト1
結線情報
コンテキストn
ページコントローラ
入力トークン
レジスタ
バックアップメモリ
WASMIIシステム
Configuration
Data line
Input Token
Registers
WASMIIシステム
Configuration
Data line
Input Token
Registers
WASMIIチップ
External Input
Token Registers
Backup RAM
PipeRench Architecture(CMU)
Global
buses
PE
PE
PE
PE
Pass
registers
・・・
Interconnection
stripe
PE
・・・
PE
Interconnection
PE
PE
Pipelined Reconfiguration
Cycle:
1
2
3
4
5
6
Stage 1
Stage 2
大きなlogical design
を小さなハードウェア
の迅速な書き換えに
よって実現する方法
Stage 3
Virtual pipeline
Stage 4
Stage 5
Cycle:
1
2
3
4
5
6
Stage 1
1
4
Stage 2
2
5
Stage 3
3
6
Physical pipeline
アプリケーション




頻繁にプログラム変更のないもの
IEEE標準浮動小数点演算を用いない
メモリバウンドでない
– 画像処理、解析、パタンマッチング
– 論理シミュレーション、故障シミュレーション
– ニューラルネットワークシミュレーション
– 暗号化処理、解読処理
– Queuing Model、Markov解析
– 電力潮流計算
– センサ処理
混載I/Oを利用できるもの
– 通信処理、プロトコル制御
– ソフトウェア無線
Reconfigurable Systemのまとめ

Reconfigurable Systemはいよいよ
Commercial Levelに達しつつある
– 半導体技術の進展の恩恵を直接享受できる
– システムLSI化によりCPU、I/Oと同一チップに
混載可能となった
– DA、Compile技術が鍵
– キラーアプリは通信制御か?
まとめ


システムLSI時代の到来により、様々な並
列アーキテクチャが再び実現される可能
性がある。
しかし、滅んで行ったものにはそれなりの
理由がある。
演習

8行8列の3重対角型行列Aと8行のベクト
ルxをシストリックアレイで演算するのに要
するクロック数を求めよ。ただし、xを左端
のアレイに最初に格納する時刻を1と考え
る。