CS 152 Computer Architecture and Engineering Lecture 16 Vector Computers Krste Asanovic Electrical Engineering and Computer Sciences University of California Berkeley http www eecs berkeley edu krste http inst cs berkeley edu cs152 March 18 2010 CS152 Spring 2010 Last Time Lecture 15 VLIW In a classic VLIW compiler is responsible for avoiding all hazards simple hardware complex compiler Later VLIWs added more dynamic hardware interlocks Use loop unrolling and software pipelining for loops trace scheduling for more irregular code Static scheduling difficult in presence of unpredictable branches and variable latency memory March 18 2010 CS152 Spring 2010 2 Intel EPIC IA 64 EPIC is the style of architecture cf CISC RISC Explicitly Parallel Instruction Computing IA 64 is Intel s chosen ISA cf x86 MIPS IA 64 Intel Architecture 64 bit An object code compatible VLIW Itanium aka Merced is first implementation cf 8086 First customer shipment expected 1997 actually 2001 McKinley second implementation shipped in 2002 Recent version Tukwila 2008 quad cores 65nm not shipping until 2010 March 18 2010 CS152 Spring 2010 3 Quad Core Itanium Tukwila March 18 2010 Intel 2008 4 cores 6MB core 24MB total 2 0 GHz 698mm2 in 65nm CMOS 170W Over 2 billion transistor CS152 Spring 2010 4 IA 64 Instruction Format Instruction 2 Instruction 1 Instruction 0 Template 128 bit instruction bundle Template bits describe grouping of these instructions with others in adjacent bundles Each group contains instructions that can execute in parallel bundle j 1 bundle j group i 1 March 18 2010 bundle j 1 bundle j 2 group i group i 1 CS152 Spring 2010 5 group i 2 IA 64 Registers 128 General Purpose 64 bit Integer Registers 128 General Purpose 64 80 bit Floating Point Registers 64 1 bit Predicate Registers GPRs rotate to reduce code size for software pipelined loops March 18 2010 CS152 Spring 2010 6 IA 64 Predicated Execution Problem Mispredicted branches limit ILP Solution Eliminate hard to predict branches with predicated execution Almost all IA 64 instructions can be executed conditionally under predicate Instruction becomes NOP if predicate register false b0 Inst 1 Inst 2 br a b b2 b1 Inst 3 Inst 4 br b3 b2 Inst 5 Inst 6 if else then Predicatio n Inst 1 Inst 2 p1 p2 cmp a b p1 Inst 3 p2 Inst 5 p1 Inst 4 p2 Inst 6 Inst 7 Inst 8 One basic block b3 Inst 7 Inst 8 Four basic blocks March 18 2010 Mahlke et al ISCA95 On average 50 branches removed CS152 Spring 2010 7 Fully Bypassed Datapath PC for JAL stall 0x4 nop Add PC addr ASrc inst IR Inst Memory D IR A ALU GPRs Y B IR we addr rdata Data Memory wdata BSrc wdata MD1 MD2 Where does predication fit in March 18 2010 M 31 we rs1 rs2 rd1 ws wd rd2 Imm Ext IR E CS152 Spring 2010 8 R W IA 64 Speculative Execution Problem Branches restrict compiler code motion Solution Speculative operations that don t cause exceptions Inst 1 Inst 2 br a b b2 Load r1 Use r1 Inst 3 Can t move load above branch because might cause spurious exception Load s r1 Inst 1 Inst 2 br a b b2 Chk s r1 Use r1 Inst 3 Speculative load never causes exception but sets poison bit on destination register Check for exception in original home block jumps to fixup code if exception detected Particularly useful for scheduling long latency loads early March 18 2010 CS152 Spring 2010 9 IA 64 Data Speculation Problem Possible memory hazards limit code scheduling Solution Hardware to check pointer hazards Inst 1 Inst 2 Store Load r1 Use r1 Inst 3 Can t move load above store because store might be to same address Load a r1 Inst 1 Inst 2 Store Load c Use r1 Inst 3 Data speculative load adds address to address check table Store invalidates any matching loads in address check table Check if load invalid or missing jump to fixup code if so Requires associative hardware in address check table March 18 2010 CS152 Spring 2010 10 Limits of Static Scheduling Unpredictable branches Variable memory latency unpredictable cache misses Code size explosion Compiler complexity Despite several attempts VLIW has failed in general purpose computing arena Successful in embedded DSP market March 18 2010 CS152 Spring 2010 11 Supercomputers Definition of a supercomputer Fastest machine in world at given task A device to turn a compute bound problem into an I O bound problem Any machine costing 30M Any machine designed by Seymour Cray CDC6600 Cray 1964 regarded as first supercomputer March 18 2010 CS152 Spring 2010 12 Supercomputer Applications Typical application areas Military research nuclear weapons cryptography Scientific research Weather forecasting Oil exploration Industrial design car crash simulation Bioinformatics Cryptography All involve huge computations on large data sets In 70s 80s Supercomputer Vector Machine March 18 2010 CS152 Spring 2010 13 Vector Supercomputers Epitomized by Cray 1 1976 Scalar Unit Load Store Architecture Vector Extension Vector Registers Vector Instructions Implementation Hardwired Control Highly Pipelined Functional Units Interleaved Memory System No Data Caches No Virtual Memory March 18 2010 CS152 Spring 2010 14 Cray 1 1976 64 Element Vector Registers Single Port Memory 16 banks of 64 bit words 8 bit SECDED Ah j k m A0 80MW sec data load store Tjk Ah j k m A0 320MW sec instruction buffer refill 64 T Regs Si 64 B Regs Ai Bjk V0 V1 V2 V3 V4 V5 V6 V7 S0 S1 S2 S3 S4 S5 S6 S7 A0 A1 A2 A3 A4 A5 A6 A7 NIP 64 bitx16 4 Instruction Buffers memory bank cycle 50 ns March 18 2010 Vi V Mask Vj V Length Vk FP Add Sj FP Mul Sk FP Recip Si Int Add Int Logic Int Shift Pop Cnt Aj Ak Ai Addr Add Addr Mul CIP LIP processor cycle 12 5 ns 80MHz CS152 Spring 2010 15 Vector Programming Model Scalar Registers r15 v15 r0 v0 Vector Registers 0 1 2 VLRMAX 1 Vector Length Register Vector Arithmetic Instructions ADDV v3 v1 v2 v1 v2 March 18 2010 0 1 v3 Vector Load and Store Instructions LV v1 r1 r2 Base r1 VLR Stride r2 v1 VLR 1 Vector Register Memory CS152 Spring 2010 16 Vector Code Example Vector Code C code Scalar Code LI VLR 64 for i 0 i 64 i LI R4 64 LV V1 R1 C i A i B i loop LV V2 R2 L D F0 0 R1 ADDV D V3 V1 V2 L D F2 0 R2 SV V3 R3 ADD D F4 F2 F0 S D F4 0 R3 DADDIU R1 8 DADDIU R2 8 DADDIU R3 8 DSUBIU R4 1 BNEZ R4 loop March 18 2010 CS152 Spring 2010 17 Vector Instruction Set Advantages Compact one short instruction encodes N operations Expressive tells hardware that these N operations are independent use the same functional unit access disjoint registers access registers in same pattern as previous instructions access a contiguous
View Full Document
Unlocking...