WIXLIB

EPIC Architectures OverviewCS 211Introduction to Explicitly ParallelInstruction Computing (EPIC)Architectures History Overview of key EPIC concepts– speculation, predication, register files Introduction to Compiler OptimizationBhagi NarahariCS 211The EPIC Concept- A little history The great CISC vs RISC debate– who won?VLIW and EPIC VLIW architectures progressed to EPIC A quick look at “pure” VLIW approach Intel’s “combination approach”– CISC instructions running on RISC core (486)– adding superscalar features (Pentium)– RISC proc had CISC like features for special units 64 bit RISC instructions– HP PA-RISC project, Early Intel efforts– iterative improvements but no revolution To make programs run faster need to lookat new architectures– something radical had to be done for more performanceCS 211CS 2111

What Is VLIW? VLIW hardware is simple andstraightforward, like SIMD machines. While SIMD broadcasts one instruction,VLIW separately directs eachfunctional unit add cutionCS 211FUFUFUadd r1,r2,r3load r4,r5 4FUFUmov r6,r2microsequencermicrocodestoredatapath controlnanocodestoremul r7,r8,r9FUFU A generation of high-performance, applicationspecific computers relied on horizontallymicroprogrammed computing engines.datapath controlCS 211Principles of VLIW Operation Statically scheduled ILP architecture. Wide instructions specify many independentsimple operations.VLIW Instruction100 - 1000 bitsMicrocode MemoryBitSliceALUBitSliceALUBitSliceALU Aggressive (but tedious) hand programming at themicrocode level provided performance well abovesequential processors.CS 211MacroInstructionsFUHorizontal Microcode and VLIWMicrosequencer(2910)Historical Perspective:Microcoding, nanocoding (and RISC) Multiple functional units executes all of theoperations in an instruction concurrently,providing fine-grain parallelism within eachinstruction Instructions directly control the hardware with nointerpretation and minimal decoding. A powerful optimizing compiler is responsible forlocating and extracting ILP from the program andCS 211for scheduling operations to exploit the availableparallel resources2

Formal VLIW Models Josh Fisher proposed the first VLIW machine at Yale(1983) Fisher’s Trace Scheduling algorithm for microcodecompaction could exploit more ILP than any existingprocessor could provide. The ELI-512 was to provide massive resources to asingle instruction stream––––Ideal Models for VLIW Machines Almost all VLIW research has been based uponan ideal processor model. This is primarily motivated by compiler algorithmdevelopers to simplify scheduling algorithms andcompiler data structures.– This model includes: Multiple universal functional units Single-cycle global register file16 processing clusters- multiple functional units/cluster.partial crossbar interconnect.multiple memory banks.attached processor – no I/O, no operating system.and often: Single-cycle execution Unrestricted, Multi-ported memory Multi-way branching Later VLIW models became increasingly more regularand sometimes:– Compiler complexity was a greater issue than originally envisionedCS 211 Unlimited resources (Functional units, registers, etc.)CS 211VLIW Execution Characteristics Unresolved design issuesGlobal Multi-Ported Register FileFunctionalUnitFunctionalUnitFunctionalUnitVLIW Design IssuesFunctionalUnit––––The best functional unit mixRegister file and interconnect topologyMemory system designBest instruction format Many questions could be answered throughexperimental researchInstructionMemorySequencerCondition CodesBasic VLIW architectures are a generalized form ofhorizontally microprogrammed machinesCS 211– Difficult - needs effective retargetable compilers Compatibility issues still limit interest ingeneral-purpose VLIW technologyHowever, VLIW may be the only way to build 8-16operation/cycle machines.CS 2113

Realistic VLIW DatapathNo Bypass!!No Stall!!Multi-Ported Register FileMulti-Ported Register FileFAdd(1 cycle)FMul4 cyc unpipeFMul4 cyc pipeFDiv16 cycleInstructionMemorySequencerCondition CodesCS 211Scheduling for Fine-Grain Parallelism The program is translated into primitive RISCstyle (three address) operations Dataflow analysis is used to derive an operationprecedence graph from a portion of the originalprogram Operations which are independent can bescheduled to execute concurrently contingentupon the availability of resources The compiler manipulates the precedence graphthrough a variety of semantic-preservingtransformations to expose additional parallelismCS 211ExampleA:B:C:D:e (a b) * (c d)b ;Original ProgramADr1 a br2 c de r1 * r2b b 13-Address CodeBVLIW List Scheduling Assign Priorities Compute Data Ready List - all operations whosepredecessors have been scheduled. Select from DRL in priority order while checkingresource constraints Add newly5 ready operations to DRL and repeat for1next instruction4-wide VLIWData Ready ListC2233Dependency Graph00:add a,b,r1add c,d,r2add b,1,b01:mul r1,r2,enopnopVLIW InstructionsCS 2113427110CS 12 10 11{10,11,12}13{13}134

Strengths of VLIW TechnologyEnabling Technologies for VLIW VLIW Architectures achieve highperformance through the combination of anumber of key enabling hardware andsoftware technologies.––––––Optimizing Schedulers (compilers)Static Branch PredictionSymbolic Memory DisambiguationPredicated Execution(Software) Speculative ExecutionProgram CompressionCS 211 Parallelism can be exploited at the instruction level– Available in both vectorizable and sequential programs. Hardware is regular and straightforward– Most hardware is in the datapath performing useful computations.– Instruction issue costs scale approximately linearlyPotentially very high clock rate Architecture is “Compiler Friendly”– Implementation is completely exposed - 0 layer of interpretation– Compile time information is easily propagated to run time. Exceptions and interrupts are easily managed Run-time behavior is highly predictable– Allows real-time applications.– Greater potential for code optimization.CS 211VLIW vs. Superscalar [Bob Rau, HP]Weaknesses of VLIW Technology No object code compatibility betweengenerations Program size is large (explicit NOPs)Multiflow machines predated “dynamic memory compression”by encoding NOPs in the instruction memory Compilers are extremely complex– Assembly code is almost impossible Philosophically incompatible with cachingtechniques VLIW memory systems can be very complex– Simple memory systems may provide very low performance– Program controlled multi-layer, multi-banked memory Parallelism is underutilized for some algorithms.CS rations/instructionInstruction streamparsingRun-time analysis ofregister dependenciesRun-time analysis ofmemory dependenciesRuntime instructionreorderingRuntime registerallocationCS terationframes)5

Real VLIW MachinesWhy VLIW Now? VLIW Multiflow TRACE 7/300, 14/300, 28/300 [Josh Fisher]Multiflow TRACE /500 [Bob Colwell]Cydrome Cydra 5 [Bob Rau]IBM Yorktown VLIW Computer (research machine)CPU Single-Chip VLIW Processors:DataCacheInstructionCache– Intel iWarp, Philip’s LIFE Chips (research) Single-Chip VLIW Media (through-put) Processors:(1MB)(1.5MB)– Trimedia, Chromatic, Micro-Unity16 IPCVLIW CPUInstructionCacheDataCache DSP Processors (TI TMS320C6x )1 Billion Transistor Intel/HP EPIC IA-64 (Explicitly Parallel InstructionComp.) Transmeta Crusoe (x86 on VLIW?) Sun MAJC (Microarchitecture for Java Computing)CS 211– ILP and complexity Better compilation technologyCS 211Performance Obstacles of Superscalars Branches– branch prediction helps, but penalty is still significant– limits scope of dynamic and static ILP analysis code motion Memory Load Latency– CPU speed increases at 60% per year- memory speed increases only 5% per year Memory Dependence– disambiguation is hard, both in hardware and software Sequential Execution Semantics ISAs– total ordering of all the instructions– implicit inter-instruction dependences1 Billion TransistorSuperscalar ProcessorProcessor Nonscalabilityof Superscalar VLIWProcessorIntel/HP EPIC/IA-64 Architecture EPIC (Explicitly Parallel InstructionComputing)– An ISA philosophy/approache.g. CISC, RISC, VLIW– Very closely related to but not the same as VLIW IA-64– An ISA definitione.g. IA-32 (was called x86), PA-RISC– Intel’s new 64-bit ISA– An EPIC type ISA Itanium (was code named Merced)Very expensive to implement wide dynamicsuperscalarsCS 211– A processor implementation of an ISA»e.g. P6, PA8500– The first implementation of the IA-64 ISACS 2116

IA-64 EPIC vs. Classic VLIWEPIC Concepts Similarities:––––Compiler generated wide instructionsStatic detection of dependenciesILP encoded in the binary (a group)Large number of architected registers Differences:– Instructions in a bundle can have dependencies– Hardware interlock between dependent instructions– Accommodates varying number of functional units andlatencies– Allows dynamic scheduling and functional unit bindingStatic scheduling are “suggestive” rather than absolute Code compatibility across generations Explicitly Parallel Instruction Computing– unlike early VLIW designs, EPIC does not use fixedwidth instructions.as many parallel as possible! Programs must be written usingsequential semantics– parallel semantics not supported– explicitly lay out the parallelism– eg: swapping of operandsbut software won’t run at top speed until it is recompiled so“shrink-wrap binary” might need to include multiple buildsCS 211CS 211EPIC: Key Concepts Speculation Predication (and parallel compares) Large (Rotating) Register FilesEPIC - Philosophy How do we increase performance– work harder or– work smarter To make the computer run faster– Principle 1: make it do each thing faster– Principle 2: make it do more things at once key to success of EPIC neither running fast nor juggling lots ofthings at once is simple!CS 211CS 2117

EPIC Concepts: Speculation What do you do with all the parallelism andhow– traditional problem has been that we never have enoughwork ready in order to keep a machine fully busy what happens when you stop worrying aboutonly doing things we must– if we have the power of parallelism, key is to not throw itaway– anytime processor is ready to do six things, do not give itonly two things to do and ignore ability to do more– how?CS 211EPIC Concepts: Speculation Speculatively ask machine to do morethings pick tasks that might be needed in future––––just aren’t sure whether they will be needed at the timemake sure you can determine if they will be neededextra tasks does not involve time (due to parallel units)even if they useful only 50% of the time, we havecompleted 50% of the tasks ahead of time! Promise of EPIC based on speculation– goal is to compute things before they are needed, sowhen program needs result it is already there!CS 211EPIC Concepts: PredicationEPIC Concepts: Predication Branching is generally bad because itinterferes with the ideal pipeline model ofreading instructions while earlier inst isexecuted ideally, if we eliminate branches then thisproblem disappears Predication is process by which branchesare eliminated Predication allows instructions to executein parallel, with some “on”and some “off”but without need for branchesCS 211CS 211– Every instruction written with a specified predicateregister to control whether instruction executes at runtime Ability to do “parallel compares”– ability to compute and combine comparison operationsin parallel– (A B) and (B 0) can be computed in parallel usingparallel compare instructions8