慶應義塾大学理工学部 天野英晴 hunga@am.ics.keio.ac.jp 新しいアーキテクチャ 慶應義塾大学理工学部 天野英晴 hunga@am.ics.keio.ac.jp
将来のマイクロプロセッサ 半導体技術の進展 スーパスカラプロセッサの複雑化 面積に見合った性能をいかに得るか? 面積は大きくなる しかし、性能はさほど向上しなくなる 0.1μm以降:スケーリング則の崩壊 スーパスカラプロセッサの複雑化 →設計コストの増大、性能向上の頭打ち 面積に見合った性能をいかに得るか? 拡張されたVLIW方式 SMT (Simultaneous MultiーThreading) マルチプロセッサ化 Reconfigurable Systems
Intel Itanium 64bit用命令セットIA-64に対応 VLIWの考え方を導入 投機的実行を支援 コンパイラ主導による複数命令同時発行 動的スケジューリングを行わない しかし、単純なVLIWではなく柔軟性が高い一方、構造はかなり複雑 投機的実行を支援 ループ処理向けの様々な機能を持つ
柔軟なVLIW(命令のグループ化) add r6=@gprel(a#),gp;; group1 r6=a[] ldfpd f1,f2=[r6] group2 f1=a[0],f2=a[1] ldfd f3=[r5],16;; f3=a[2] fma.d f4=f1,f2,f3 group3 f4=f1*f2+f3
柔軟なVLIW (グループとバンドル) group Bundle(128bit) Template(5bit) Cycle Break
パイプライン構成 10段パイプライン、6命令同時発行 Instruction Delivery Operand Delivery Execution Front end IPG FET ROT EXP REN WLD REG EXE DET WRB IPG:Instruction Pointer generation FET:Fetch ROT:Rotate EXP:Expand REN:Rename WLD:Word-line decode REG:Register Read EXE:Execute DET:Execute detect WRB:Write Back
Block Diagram Off Chip L3 Cache L2 Cache B B B M M I I F F L1 Instruction Cache・Fetch/Prefetch Engine IA-32 Decode and Control Off Chip L3 Cache L2 Cache Branch Prediction B B B M M I I F F RegisterStuck/Re-mapping Score boad etc. Branch Units Integer MMU Units FP Units Bus Controller
分岐命令の削減 predication register 1の時だけ指定されたレジスタを有効にする cmp eax,ebx jne L30 mov ebx,CONST1 jmp L31 L30: mov ebx,CONST2 L31: cmp.eq p7,p8=r14,r15;; (p7) movi r15=CONST1 (p8) movi r16=CONST2
Advanced Load Advanced Load ld4.a r2=[r33] add r3=4,r0;; add r3=4,r0;; st4 [r32]=r3 ld4.c r2=[r33];; add r5=r2,r3 add r3=4,r0;; st4 [r32]=r3 ld4 r2=[r33];; add r5=r2,r3 Check st命令との間のデータ依存性は、ALAT(Advanced Load Address Table)によって解決する。
Speculative Load add5: cmp.eq r6,p5=r32,r0;; add5: ld8.s r1=[r32] (p6) add r8=-1,r0 (p6) br.ret (p5) ld8 r1=[r32] add r8=5,r1 br.ret;; add5: ld8.s r1=[r32] cmp.eq p6,p5=r32,r0;; (p6) add r8=-1,r0 (p6) br.ret (p5) chk.s r1,return_error add r8=5,r1 br.ret page faultした場合、loadは待たされる
ループ演算の性能向上 カウンタ付きループ命令 ポストインクリメント命令 昔から存在する複合命令だが、VLIW並列実行の枠組みを 利用して、実行サイクル数を避けることができる
Software Pipelining i Loop: LD F0,0(R1) ADDD F4,F0,F2 SD 0(R1),F4 SUBI R1,R1,#8 BNEZ R1,Loop Loop: SD 0(R1),F4 ADDD F4,F0,F2 LD F0,-16(R1) SUBI R1,R1,#8 BNEZ R1,Loop i-1 i-2 どのようなマシンにも利用可能(これはDLXでのコード例) しかし、初期化と最後の部分がたいへん
Software Pipeliningのサポート Modulo Schedule loop命令 loop counterが0になっても実行を終了せず、新たなエピローグカウンタECが0になるまで実行 レジスタローテーション ループ毎に自動的にレジスタ番号を一つ増やしてリネームする。
その他 レジスタスタックによる関数呼び出しの高速化 関数呼び出し時のリネーミング
まとめ 単純なVLIWではない 命令セットは複雑であるが、RISCの高速化技法を数多く取り入れている コンパイラへの依存が中途半端 代償として構造の複雑化を招く危険性がある IA-32の実行も可能だが遅い
Simultaneous Multithreading (SMT) スーパスカラプロセッサ 複数命令同時発行 マルチスレッドプロセッサ コンテキストスイッチをハードウェアでサポート SMTは両方の特徴を継承 プロセッサの利用効率が向上
SMTの動作 Issue Slots Issue Slots Issue Slots Clock Cycles superscalar fine-grained multithreaded superscalar superscalar SMT
スーパスカラとの比較 SPECInt Apache OS 無し 有り superscalar 3.0 2.6 1.1 SMT 5.9 5.6 Instruction Per Cycle(IPC) による比較 SPECInt Apache OS 無し 有り superscalar 3.0 2.6 1.1 SMT 5.9 5.6 4.6 SPECInt : not OS intensive application Apache : OS intensive application
SMTの利点 並列度をスレッドレベルから命令レベルへ レイテンシの隠蔽が可能 コンテキストスイッチをハードウェアで実行 IPC の向上 OS(kernel)の影響が減少 コンテキストスイッチをハードウェアで実行
ユニプロセッサと並列計算機の境目 どのようなレベルの並列性を利用するか? ILP(Instruction Level Parallelism) 命令レベルの並列処理 Trace Level Parallelism 数命令から成る命令列 Thread Level Parallelism 一定の大きさの命令列(複数プロセス) Process Level Parallelism プログラマ、コンパイラが分割した一定の処理を行う命令列 ユニプロセッサ 並列計算機
同時発行数の増加vs. プロセッサを接続 単一パイプライン 高性能化 複数命令同時発行 複数Thread同時実行 オンチップ化 密結合 共有メモリ、共有レジスタ プロセッサを接続
Flynnの分類 命令流(Instruction Stream)の数: M(Multiple)/S(Single) データ流(Data Stream)の数:M/S SISD ユニプロセッサ(スーパスカラ、VLIWも入る) MISD:存在しない(Analog Computer) SIMD MIMD
SIMD 全プロセッサが同一命令で動作 柔軟性が低い Illiac-IV/マルチメディア命令タイプ(粗粒度) CM-2タイプ(細粒度) 命令メモリ 命令 演算プロセッサ データメモリ
SIMD型の分類 粗粒度型:各ノードで浮動小数点演算処理が可能 細粒度型:各ノードは1bitまたは数bitの演算しかできない ILLIAC-IV,BSP,GF-11 最近の高性能CPUのマルチメディア命令 細粒度型:各ノードは1bitまたは数bitの演算しかできない ICL DAP, CM-2,MP-2 コネクションマシンは応用分野を人工知能に拡大(CmLispの功績)
CM-2のプロセッサ Flags A B F OP C Context s c 256bit memory 1bit serial ALU
CM2のプロセッサチップ 4096チップで 命令 64K PE 1チップ構成 P Router P P P 4x4 Processor Array 12links 4096 Hypercube connection 256bit x 16 PE RAM
SIMD型の将来 粗粒度SIMD 細粒度SIMD 専用SIMDは、将来大いに伸びる可能性がある 大規模なものの復活はないだろう マイクロプロセッサの高速化技術として小規模なものが生き残る 細粒度SIMD 画像処理等で圧倒的に有利 CM2 → CM5のようにマルチプロセッサ化した方が性能が高い 専用SIMDは、将来大いに伸びる可能性がある
全プロセッサが自分の命令を独立に実行 同期が必要 汎用性が高い 様々な構成法が存在 MIMD プロセッサ 結合網 メモリ(命令・データ)
共有メモリの形態による分類 UMA(Uniform Memory Access Model) どのプロセッサからでも同様にアクセスすることができる共有メモリを持つ NUMA(Non-Uniform Memory Access Model) 共有メモリは持つがレイテンシが異なる NORA/NORMA(No Remote Memory Access Model) 共有メモリを持たずメッセージ交換で処理を行う
UMA 最も単純な共有メモリ型 単一プロセッサの延長 プログラム、OSの開発が楽 小規模システムに限られる バス結合型 スイッチ結合型 システム全体をLSI中に収める動きがある オンチップマルチプロセッサ
UMAの一例:バス結合型 Main Memory shared bus PU Snoop Cache PU Snoop Cache PU SMP(Symmetric MultiProcessor)として標準部品化 オンチップに格納可能
スイッチ結合型UMA Local Memory .... CPU Interface Switch …. Main Memory スイッチとバスの区別はどんどんなくなりつつある
Stanford’s Hydra CPU I/O Bus Interface Considerations in the design of Hydra CSL-TR-98-749, CPU Mem. Cont. L1 I Cache L1 D On-chip L2 Cache Off-chip L3 Cache Int. I/O Bus Interface Rambus Memory interface Cache SRAM Array Write Through Bus(64b) Read/Replace Bus(256b) DRAM Main Memory I/O
Daytona(Lucent) MESI Protocol RISC+DSP Pipelined operation of bus and memory controller. 128bit STBus 0.25μm CMOS 4.5m×6mm (small chip)
Daytona(Lucent) STBus L1 PE0 Memory and I/O Controller L1 PE1 I/O Controller PE1 L1 PE2 L1 semaphores arbiter PE3 L1
Power4(IBM) 0.18μm copper process, 400m㎡ 17000M Tr. Inter-chip interface for MCM(Multi-Chip Module) TLP(Thread Level Parallelism) Design considering memory bandwidth Shared cache + links
Power4(IBM) CPU1 CPU2 L3 Cache Main Memory L3 Tags L2 Shared Cache >100GByte/s >333MHz >10GByte/s CPU1 CPU2 L3 Cache Main Memory Chip-to-Chip Interconnect L2 Shared Cache L3 Tags >500MHz, Wave-Pipelined Expansion Buses >10GByte/s Chip-to-Chip Interconnect >500MHz >35GByte/s
MAJC Hierarchical structure Variable length VLIW processing element Shared cache I/O for inter-processor communication I/O for PCI,DRAM MAJC5200:0.22μm CMOS 220mm square
MAJC(Microprocessor Architecture for Java Computing: SUN) Rambus I/O N-UPA PCI I/O Graphic Processor FU 0 1 2 3 I-Cache FU 0 1 2 3 I-Cache Switch Shared Cache S-UPA
NUMA それぞれがローカルメモリを持ち、他のプロセッサのメモリをネットワーク経由でアクセスする アドレス変換、キャッシュ制御が必要でハードウェア制御が複雑 スケーラブル: UMAのプログラムがそのまま移植可能 プロセッサ数を大きくした分の性能向上が得られる クラスタ+ソフトウェアDSMと競合中
典型的な構成 論理アドレス空間 Node 0 0 Node 1 1 Interconnecton Network 2 Node 2 3
NUMAの分類 (ただの)NUMA: CC-NUMA:Cache Coherent リモートメモリをキャッシュしない 構成が単純、リモートメモリのアクセスにコストがかかる CC-NUMA:Cache Coherent キャッシュの一致制御を保証 複雑なハードウェアが必要 COMA:Cache Only Memory Architecture ホームメモリを持たない ハードウェアがより複雑
Interconnection Network (16GB/s x 2) Earth Simulator (2002,NEC) Peak performance 40TFLOPS Interconnection Network (16GB/s x 2) Vector Processor … 1 7 Shared Memory 16GB Vector Processor … 1 7 Shared Memory 16GB Vector Processor … 1 7 Shared Memory 16GB …. Node 0 Node 1 Node 639
SGI Origin Main MemoryはHub Chipから直接リンクを出す 2PEで1Cluster Bristled Hypercube Main Memory Hub Chip Network Main MemoryはHub Chipから直接リンクを出す 2PEで1Cluster
DDM(Data Diffusion Machine) D ... ... ... ...
NORA/NORMA 共有メモリを持たない 交信はメッセージのやりとりで行う 最も単純な構成で最大性能を得ることができる 一面、プログラムが難しい。汎用性に乏しい 技術的な問題は、プロセッサ間接続、パケット転送 チップ間接続網とパケット転送 クラスタコンピューティング
Fine grain SIMD Coarse grain マルチプロセッサ コントロール フロー制御 バス結合型UMA スイッチ結合型UMA Simple NUMA CC-NUMA COMA MIMD NUMA NORA マルチコンピュータ シストリックアーキテクチャ データフロー制御 混合制御 要求駆動 その他
シストリックアーキテクチャ Data列x 演算アレイ Data列y 特定の演算能力を持つアレイ列に一定の間隔で リズミカルにデータを送りこみ、並列演算
帯行列の行列積 y=Ax y0 y1 y2 y3 a11 a12 0 0 a21 a22 a23 0 0 a32 a33 a34 yi yo X+ yo= a x + y i x
帯行列の行列積 y=Ax a11 a12 0 0 a21 a22 a23 0 0 a32 a33 a34 0 0 a43 a44 X + x1
帯行列の行列積 y=Ax a11 a12 0 0 a21 a22 a23 0 0 a32 a33 a34 0 0 a43 a44 a33 X + X + x2 x1
帯行列の行列積 y=Ax a11 a12 0 0 a21 a22 a23 0 0 a32 a33 a34 0 0 a43 a44
帯行列の行列積 y=Ax a11 a12 0 0 a21 a22 a23 0 0 a32 a33 a34 0 0 a43 a44 a44 X + X + x2 x3
帯行列の行列積 y=Ax a11 a12 0 0 a21 a22 a23 0 0 a32 a33 a34 0 0 a43 a44 a44 X + x3 x2
シストリックアーキテクチャの 特長 入出力ピン数が少ない 単純な同期制御 近接接続のみで構成可能 1980年代Kungらの提案により注目されたがLSI実装面積の不足により普及しなかった 他の「VLSIアルゴリズム」と共に復活の可能性 オンチップメモリが活用されないのが問題
データフローアーキテクチャ データをトークンとして考え、到着と共に計算処理が駆動される。 記憶要素を明示的に指定しない。 アルゴリズムの持つ並列性を最大限に引き出すことができる。
データフローグラフ d e c x a b + + x (a+b)x(c+(dxe))
命令実行サイクル 命令読み出し データ待ち合せ データ読み出し 命令読み出し 命令実行 命令実行 データ格納 あて先指定 データフローマシン 通常のプロセッサ
データフローマシンの問題点 純粋なデータフローマシン(Dennisのマシン)は無駄が多い。 色付きトークン等の導入でデータフローグラフの再利用。 構造の複雑化 演算器レベルの処理時間とそれに要する時間の比率の問題 局所性の無視
Reconfigurable System (Custom Computing Machine) SRAM型プログラマブルデバイスから構成されるシステム上で問題の解法アルゴリズムを直接ハードウェア化して実行する 専用マシンのスピード 汎用マシンの柔軟性 プログラム格納型計算機とはまったく異なる原理でしかも堂々たる体系を作ることができる しかし誰も騒いでくれない
最近のFPGA/PLD ゲート数は1000Kゲートに及ぶ(半分嘘だけど、、) 最大動作周波数は設計次第だが30MHz程度ならば容易に実現 内部データ格納用SRAMを持つ 単純なゲートアレイは、使われなくなっている。
(Field Programmable Gate Array) SRAM型FPGA (Field Programmable Gate Array) 5入力テーブル スイッチ設定 Configuration Memory 2 F.F. I/O Logic Block Look Up Table Switch
(Complex Programmable Logic Device) SRAM型CPLD (Complex Programmable Logic Device) I/O SRAM(Configuration Memory) Logic Block Switch
代表的なReconfigurable System 独立実行型 スタンドアローンで動作 Splash 1・2, RM-I,II,III,IV, FLEMING コ・プロセッサ型 汎用プロセッサの一部の処理を高速化 PRISM I,II、 DISC II
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 New Device 1990年 第1回FPL SPLASH MPLD PRISM-I 1992年 第1回Japanese FPGA/PLD Conf. SPLASH-2 PRISM-II RM-I WASMII 1993年 第1回FCCM RM-II Cache Logic RM-III DISC RM-IV 1995年 YARDS Mult.Context FPGA RM-V DISC-II HOSMII ATTRACTOR FIPSOC Cont.Switch.FPGA RASH PipeRench DRL PCA 2000年 CHIMERA Chamereon
Splash-2 (Arnoldら 92) 米国計算機科学センター 文字列検索、画像処理、DNAの塩基配列間の距離を求める問題でCray-IIの330倍の性能を発揮 直線シストリックアレイ構造 VHDL, 並列Cによるプログラミング Annapolis Micro Systems社より商用化(WILDFIRE)
Splash-II 米国計算機科学センタ 文字列検索、画像処理、DNAの塩基配列間の距離を求める問題でCray-IIの330倍の性能を発揮 Splash-II 米国計算機科学センタ 文字列検索、画像処理、DNAの塩基配列間の距離を求める問題でCray-IIの330倍の性能を発揮 直線アレイ構造 VHDL,並列Cによるプログラミング
RM-IV(神戸大学) FPGA mem. FPGA mem. FPIC Interface
RASH (三菱電機) 1Unit: 最大6枚のEXEボードとCPUボード(Pentium) 複数のUnitを接続可能 ディスプレイ CompactPCI bus EXE- ボード CPUボード ディスプレイ disk Ethernet LAN RASH unit CD 1Unit: 最大6枚のEXEボードとCPUボード(Pentium) 複数のUnitを接続可能 &p This slide is supported by Dr.Nakajima of Mitsubishi.
EXEボードの構成 FPGA Altera FLEX10K100A (62K-158KGate) リンク接続とバス接続 2系統のクロック PCI-bus リンク接続とバス接続 2系統のクロック PCIバスI/F SRAM搭載 DRAM付加ボード搭載可 PCI-bus I/F PCI Local-bus SRAM (2MB) EXE-board controller Clocks/Cont. signals Local-bus FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA Altera FLEX10K100A (62K-158KGate) &p
ATTRACTOR(NTT) 高速シリアルリンク(1Gbps) RISC FPGA RISC FPGA ATM I/O RAM (LUT) SW Buffer RISC RISC RISC RISC Ethernet Compact PCI MPU ATM通信処理に 特化したシステム 多種類のボードを接続 Mem. ボードレベルで再構成可能
コ・プロセッサ型 Core CPUと密接続 プログラムの一部を高速化 NAPA, Garp, Chameleon, Chimaera, PipeRench
PRISM II(Brown大学) プログラムのよく使う部分を高速化 コプロセッサ型の元祖 Am2955 CPU Data Address Control Boot ROM Switch DRAM Burst Mode Memory Controller DRAM FPGA Module FPGA Module FPGA Module プログラムのよく使う部分を高速化 コプロセッサ型の元祖
Garp (Hauserら 97) UCBのプロジェクト MIPSコアとReconfigurable Arrayが強結合しメモリ階層を共有 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大学 動的な部分書き換え機能を用いた汎用プロセッサ FPGA 3 Processor Core System Memory Brigham Young大学 動的な部分書き換え機能を用いた汎用プロセッサ 任意のカスタム命令を基本命令セットに追加可能 各モジュールをユーザが設計 C言語上から関数として利用 FPGAをカスタム命令モジュールのキャッシュのように使用 FPGA 1 Bus I/F Configuration Controller FPGA 2 Custom Instruction Space Host P/C
CHIMAERA (Yeら 2000) Northwestern大学 スーパスカラプロセッサのデータパスに可変構造アレイを挿入 シャドウレジスタファイルから9レジスタを一度に読込み Out of Order制御 10~20%の高速化 シャドウレジスタ ファイル レジスタ ファイル 可変構造 アレイ uPコア コントローラ
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 PCI Cont. RISC Core Controller 128-bit RoadRunner Bus Configuration Subsystem DMA Subsystem Reconfigurable Processing Fabric 160-pin Programmable I/O
Reconfigurable Processing Fabricの構造 CTL中の最大8命令をDPU中で実行可能 CTLは、同じサイクルで次の命令を決定可能 新しいbit streamをloadすることで構成を変えられる Reconfigurable Processing Fabricの構造 DPU CTL LM Tile 0 Slice 0 LM DPU 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,パイプライン Instruction Routing Register & Mask Routing MUX OP Register Barrel Shifter Register Register & Mask Routing MUX
Reconfigurable Systemの 問題点 SRAM型FPGAの演算器は専用CPU,DSPよりも10倍遅く、10倍集積度が劣る メモリとの接続が脆弱 アルゴリズムを変換するための標準的方法が存在しない 問題サイズがシステムサイズを越えるとお手上げ
おわりに 様々な新しいアーキテクチャを概観した 今回の話はイントロのみ 個人的には並列アーキテクチャとReconfigurable Systemsに中心を置いて研究を進めている