VLIW（Very Long Instruction Word）& マルチスレッドプロセッサ （Multi-Thread Processor） Super Scalarのような命令レベル並列処理 Parallel processing with Instruction level like Super.

Presentation on theme: "VLIW（Very Long Instruction Word）& マルチスレッドプロセッサ （Multi-Thread Processor） Super Scalarのような命令レベル並列処理 Parallel processing with Instruction level like Super."— Presentation transcript:

1 VLIW（Very Long Instruction Word）& マルチスレッドプロセッサ （Multi-Thread Processor）
Super Scalarのような命令レベル並列処理 Parallel processing with Instruction level like Super Scalar MT (Multi-Thread) Processor スレッドレベル並列処理 Thread Level parallel processing 同時（スループット指向）MT Simultaneous (Throughput oriented) MT Super scalarの上にスレッドレベル並列処理を重ねる Thread level processing on top of a super scalar processors 混合型 Mixture（SMT & VLIW） 福永　力；Chikara Fukunaga

2 Multi-Thread Processor
MT=Multi-Thread（ここでthreadとはプログラム並列処理単位：ループ、関数） Thread is a unit for parallel processing in a process; Loop or Function ここではスパスカラーを利用せず従来型のスカラープロセッサを利用（no. of ways=1） A conventional scalar processor will be used for this MT processing. 自分自身でthreadを切り替える The hardware makes the context-switch of threads. 福永　力；Chikara Fukunaga

3 細粒度あるいはインタリーブMT Fine Granularity or Interleaved MT
細粒度（Fine Granularity or Interleaved）MT： クロックあるいは命令ごとにthread切り替え Threads are executed one by one with clock or instruction. MIPS® MT Principles of Operation Document Number: MD より 福永　力；Chikara Fukunaga

4 粗粒度あるいはブロックMT Coarse Granularity or Blocked MT
粗粒度（Coarse Granularity or Blocked）MT：キャッシュ・ミスなど長期ストール時にthread切り替え （別名（a.k.a.）：Switch on Event MT：SoEMT） Switching of Threads is done at a long stall like cache miss or IO access MIPS® MT Principles of Operation Document Number: MD より 福永　力；Chikara Fukunaga

5 スーパスカラの非効率さ Inefficiency of Super scalar processors
（注意）今までのスパースカラプロセッサは命令レベルの並列性（ILP）に着目していた． A Super scalar is a parallel processor at the instruction level. しかし例えn命令同時並列処理（n-ways）の能力があってもIPCはせいぜいn/2程度、資源の半分は使われないままという研究結果がある． IPC is estimated to be only n/2 even if a super scalar has n-way pipelines. Efficiency can not be higher than 50%. 福永　力；Chikara Fukunaga

6 スループット指向 MT プロセッサ Throughput oriented MT Processor
スーパスカラを多数のthreadを並列処理するプロ セッサに改変させればその問題が解決できてス ループット（throughput）も向上する（だろう）． If a super scalar is used as MT processor , throughput will be expected to increase. スレッドコンテキスト（PCとレジスタ）をthread分用 意 Thread data units (PC and registers) are implemented with the number equal to the max. threads expected. 福永　力；Chikara Fukunaga

7 スループット指向MTプロセッサの考え方 Ideas of Throughput Oriented MT Processors
同時（Simultaneous） MT：複数thread同時実行 Multiple threads can be executed simultaneously. スーパスカラの埋まらないスロットを他のスレッドからの命令で充填させればよい． Empty slots of multiple ways can be used for instructions of other threads. Then the efficiency will be higher. MIPS® MT Principles of Operation Document Number: MD より 福永　力；Chikara Fukunaga

8 SMT Processor構造 structure
Extension of a simple super scalar structure Instruction of a thread is selected Number of registers are increased Renaming structure for Multi-threads 福永　力；Chikara Fukunaga

9 スループットMTプロセッサ問題点 Problems about Throughput MT Processors
レジスタ数の増加・増大 （IPCかクロック周期かなんらかの犠牲が必要） Increase of number of Registers. We need to sacrifice performance (IPC and/or clock frequency) メモリ参照の増加 Increase of memory access （thread単位で独立メモリ領域参照→キャッシュミスヒット） threadごとのキャッシュ領域=1/thread数 (Cache for each thread must be independently implemented→ Cache size reduction → cache miss) Cache size ~ 1/no. of threads Thread数の限界：資源の半分が通常のスーパスカラで利用されているとしたら資源のフル利用にはthread数は多くても2、それ以上は無意味 How many threads are really needed? Some study indicated Resource were most-effectively used with only two. 多重スレッドプログラム処理要求は高い？ （数値計算・メディア処理→‥‥） In which application, such a processor will be used. Numerical processing, Multimedia ? 福永　力；Chikara Fukunaga

10 MIPS32®34Kf™プロセッサProcessor
MIPS社開発Multi-thread プロセッサ（2006） Multi-thread processor developed by MIPS Technologies (2006) 2段階の多重thread構造（OS level/User level） Multiple thread structure with two ranks OS level thread → VPE（Virtual Processing Elements）×Max. 2 User level thread → TC（Thread Context）×Max. 9 TCはそれぞれ独自のPCとRegister File（RF）を持つ Each TC has own PC and Register File (RF) 単OS、異なるOSを各VPEに導入できる Single OS with one VPE or Different OS can be deployed to each VPE いくつかのTCsをVPEに配置 Several TCs/VPE QoSがTC選択アルゴリズムを内蔵 QoS contains TC selection Algorithm MIPS technologies WWW siteから 福永　力；Chikara Fukunaga

11 QoS in MT ASEによるTC選択 TC selection with QoS in MT ASE
9 stage pipeline基本構造（basic architecture）+ MT ASE & DSP ASE (Application Specific Extension) 利用者がASEを特定用途向けに改造 Customers can program ASE for their purpose TC優先順位付けPolicy manager in QoS of MT ASEの設定 Setup of Policy manager in QoS of MT ASE for TC selection 例えば（Examples:） Prioritization or Round Robin TC selection/ Cycle assignment to TCs Policy Manager 福永　力；Chikara Fukunaga

12 MIPS32®34Kf™ Block Diagram
Fetch UnitはすべてTCから 命令を受け取る Fetch Unit receives instructions from all TCs. Fetch Unit にはBranch Prediction Logic (512 entries) 各TCはIBFという8個命令収容のinstruction bufferをもつ Each TC has an instruction buffer (IBF) which can store 8 instructions TC Dispatch UnitはMT control block にあるpolicy managerから の決定によりどのTCからの命令 をとってくるか決める TC Dispatch Unit selects TC to execute the instruction. MT control block specify the TC. MIPS Technologies, MIPS32® 34KfTM Processor Core Datasheet （2008）より 福永　力；Chikara Fukunaga

13 EyeQ2 system with MIPS 34Kf
Embedded System Europe 8/ issue 福永　力；Chikara Fukunaga

14 EyeQ2 道路交通状況の実時間ビジュアル解析システム Road traffic condition vision analysis with max. two cameras input data 福永　力；Chikara Fukunaga

15 EyeQ2 block diagram with 2 MIPS 34Kfs
2 MIPS 34Kfs （1つ将来拡張用）が使われている 2 MIPS 34Kfs are used (one is for future extension) 8 Visual Computing Engines CE : Classifier Engine Image scaling & Preprocessing Unit Pattern classifier Tracker: Image warping and and Motion analysis PW: Pre-process Window Image converter and pyramid unit Computation of Vertical and horizontal edge map Filter: Feature based classify unit Dfinder (Display Finder) Stereo engine Programmable scan 2pixel/clock 3 Vector Microcode machines (VLIW) 福永　力；Chikara Fukunaga

16 VLIW or EPIC VLIW =Very Long Instruction Word or EPIC =Explicitly Parallel Instruction Computer 複数のInstructionを1つの非常に（Very）長い（Long）語（Instruction Word）に詰め込み並列処理を目論む Several instructions are put into a very long instruction word at once. Word（100〜200bitより構成）はいくつかのブロック（プロセッサの処理ユニットに対応）に分解され，各ブロックは数10bitでそのユニットの命令（＋オペランド）を形作る． The word is divided into some blocks (O(10) bit size). One block corresponds to the instruction word of a conventional processor. つまり非常に長い命令語に複数命令を詰め込めるだけ詰め込みそれらを並列動作させようとするもの． Multiple instructions are stored in each block of the instruction word amap. The block has own computing system so that instructions in the word are able to be executed in parallel. 福永　力；Chikara Fukunaga

17 VLIW or EPIC（2） 現在までにさまざまなプロセッサが開発されていった．i860という64bitのLIWがある．整数計算浮動小数点計算を並列実行． Several LIW/VLIW were developed so far such as i860 which is LIW processor with 64bit instruction word. さらにIntel（主要開発はHPによる）のItanium（2001.5発売），TransmetaのCrusoe（2000.1）などが市場に出回った．ともにx86命令を展開するのでWindows系PCに使われている． Intel (although the main developer was HP) VLIW called Itanium has been put on the market in May 2001 on the market, Transmeta has had Crusoe in Jan Both processors are VLIW of x86 instructions. They have been used for Windows PCs. 福永　力；Chikara Fukunaga

18 VLIWの概念 Ideas of VLIW 例えば148bitで1語の命令長．いくつかのブロックに分けられ各部分に対応する命令をプログラムから取ってきて組み込む．それらは並列処理される． Instruction word length=148bit with several blocks. Each block is used for a particular kind of instructions. Instructions are processed in parallel. スケジューリングハードウェアがないので回路は簡単，低消費電力 A simple circuit and low power consumption because no complicated scheduling logic. プログラムから並列並びにハザードを考慮しながら命令を並べるのはソフトウェア（コンパイラあるいは変換ソフト）の仕事 A compiler/translator software arranges the instructions into appropriate blocks. 福永　力；Chikara Fukunaga

19 命令のVLIWへの組み込み Instructions into VLIW blocks
対応する命令が見つからない場合はNOP（No OPeration）を詰め込む． NOP (No operation) must be put into a block if no instruction candidate 効率的な並列処理は期待できない．動画データの解凍，表示，圧縮などの反復操作に有効か． Expected not efficient parallel processing. Effective for Moving picture? コンパイラに非常に多くのものを要求，依存しなければならない． Heavy duty for the compiler 構造上インオーダ発行、インオーダ終了となる． In order issue/in order completion 福永　力；Chikara Fukunaga

20 VLIWとスーパスカラ VLIW and Superscalar
VLIWはハードウェアの構成は単純、しかし The Hardware structure of VLIW is simple, but 硬直化したスケジューリング： 命令のインオーダ発行、インオーダ終了 inflexible scheduling with in-order issue and completion Compiler instructions Processors Scheduler 福永　力；Chikara Fukunaga

21 VLIW例：富士通FR-V（550） Example of VLIW : Fujitsu FR-V（550）
Parallel processing with max 8 instruction/28 calculations/clock 32kB I-cache (4 way set assoc.) and 32kB D-cache（4-set assoc.） 90nm CMOS Frequency 440MHz (upgraded in 2006) シングルチップFR-V550は2006年改変されマルチコア化されMB93577の型番で商品化されている FR-V550 has been upgraded to the multi-core chip with ID MB93577 64 福永　力；Chikara Fukunaga

22 FR-V 8-way VLIW architecture
福永　力；Chikara Fukunaga

23 FRV-550でねらう用途 Applications with FR-V550 cores
Multimedia processing with low power consumption Concurrent processing of Movie decoding (MPEG4/H.264 or MPEG2 decoding with 3D graphics) Bioinformatics simulation: Molecular Dynamics of Protein High performance but low energy consumption and price. 福永　力；Chikara Fukunaga

24 VLIW問題点 NOPsの増大による非効率な並列処理
世代交代による新規h/w拡張（つまりbit数/Wの増加）に簡単に対応できない．プログラムの再コンパイルあるいは改造 インオーダ終了により非効率なサイクル数の増加（早く終わった命令のアイドリング） ロード/セーブ命令のスケジューリング見積もりの不確定さ 細かく複雑な条件分岐を含むプログラムへの非力な適応 福永　力；Chikara Fukunaga

25 EPIC（Explicitly Parallel Instruction Computing）
Intel、HPはEPICなる概念のアーキテクチャ（IA64）を共同開発． Intel and HP together have developed a new architecture IA64 in the framework of EPIC VLIWだがその欠点を克服 It is VLIW in principle, but its drawback is tried to eliminate 両社はItaniumという名称のプロセッサを制作した（2001） They have put a new EPIC processor Itanium in market in 2001 福永　力；Chikara Fukunaga

26 Itanium Architecture 128ビットに3つの命令（各41ビット）と5ビットの「template」と呼ばれる フィールドをもつ． 3 instructions with each for 41 bit block + 5bit field called “template” この128ビットの命令ワードを 「bundle」と呼ぶ 128 IW is called “bundle” この命令を実行する（1）か しない（0）かを保持するレジスタ を指定predicate部に指定 A register to execute this instruction (1) or not (0) is specified in Predicate field 福永　力；Chikara Fukunaga

27 Itanium Instructions and Template
命令はハードウェアユニットの利用からいくつかのタイプに分類できる． Instructions can be divided into several types according to the main hardware unit. templateでハードウェア資源ユニットの数を考慮した並列できる命令の組み合わせを示す．templateで規定された組み合わせは独立であることが保証される． Template specifies a combination of instructions which can be put into three slots in bundle. templateの例Example MII, MI|I, MLX, MMI, M|MI, MFI, MMF, MIB, MBB, BBB, MFB … MFI = M inst. (slot 0) F in slot 1 I in slot 2 |はconflictが発生した場合の次のサイクルへの先送り（stop） | indicates that the instruction after it will be done in the next cycle if conflict may occur A型命令はI-unitでもM-unitでも処理可能Type A can be put into either I or M 命令型 Instruction type 意味 Description 実行ユニット Execution unit A Integer ALU I- or M-unit I Non-ALU integer I-unit M Memory M-unit F Floating -point F-unit B Branch B-unit L+X* Extended I-unit or B-unit * Long integer or Long Branch 福永　力；Chikara Fukunaga

28 Itanium ブロック図 Block diagram
Itanium 1 分岐ユニット（B）×3、整数(I)×4、メモリ（M）×4、浮動小数点（F）×2個 Itanium 1 Branch unit (B)×3, Integer (I)×4, Memory (M)×4, Floating Point (F)×2 Itanium 2 分岐ユニット（B）×3、整数(I)×6、メモリ（M）×6、浮動小数点（F）×2個 Itanium 2 Branch unit (B)×3, Integer (I)×6, Memory (M)×6, Floating Point (F)×2 福永　力；Chikara Fukunaga

29 Itanium Bundle Rotationと並列処理 and Parallel Processing
命令の実行例 （通常2 bundles同時実行） Example of instructions (Simultaneous execution of two bundles normally) template MFI & MIB Stop処理とbundle次回 まわし（rotation） Stop process and bundle rotation template MII & M|MI ここで2サイクルで9個の命令が 並列実行されている． 9/12=75% Nine instructions are executed in two cycles. Utilization=9/12=75% 福永　力；Chikara Fukunaga

30 Predicationの概念 Concept of Predicate
命令に6ビットのPredication Registerを指定（つまり全部で64個のregisters;各1ビット） 6bit Predication Register specification is added in the instruction. Total 64 registers. このRegister値が1であれば実行、0であればNOP、だから命令は以下のような形に If the value of this register = 1, execute, else =0, then NOP. (p1) ADD R1,R2,1 もしp1==1　ADD命令実行 else NOP if p1==1 ADD else NOP 福永　力；Chikara Fukunaga

31 Predication example/の例
… If (x==10) c=c+1 ; CMP.EQ P1, 0, R5 (P1) ADD C,1 If example If-else example CMP.EQ P1,P2, 10, R5 (P1) inst1 (P1) inst2 (P1) … (P2) inst3 (P2) inst4 …　… 福永　力；Chikara Fukunaga

32 x86とItanium コード比較 Code comparison between x86 and Itanium
x86 code example CMP AX, JE      L CMP BX, JE      L ADD J, JMP  L3 L1: CMP  CX, JE L ADD K, JMP L3 L2: SUB K, 1 L3:  ADD I, 1 Itanium code example //Compare R1 with 0, if it is true then P=1 and P2=0, // otherwise P1=0 and P2=1  CMP.EQ P1, P2, 0, R1                   (P2)  CMP.EQ P1, P3, 0, R2 (P3)  ADD  J,1 (P1)  CMP.NE P4, P5, 0, R3 (P4)  ADD K, 1 (P5)  SUB K, 1           ADD I,1 福永　力；Chikara Fukunaga