1、Supercomputing in Plain English Instruction Level Parallelism,Henry Neeman Director OU Supercomputing Center for Education & Research October 1 2004,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,2,Outline,What is Instruction-Level Parallelism? Scalar Operatio
2、n Loops Pipelining Loop Performance Superpipelining Vectors A Real Example,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,3,Parallelism,Less fish ,More fish!,Parallelism means doing multiple things at the same time: you can get more work done in the same time.
3、,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,4,What Is ILP?,Instruction-Level Parallelism (ILP) is a set of techniques for executing multiple instructions at the same time within the same CPU. The problem: the CPU has lots of circuitry, and at any given tim
4、e, most of it is idle. The solution: have different parts of the CPU work on different operations at the same time if the CPU has the ability to work on 10 operations at a time, then the program can run as much as 10 times as fast (although in practice, not quite so much).,Supercomputing in Plain En
5、glish: ILP OU Supercomputing Center for Education & Research,5,Kinds of ILP,Superscalar: perform multiple operations at the same time (e.g., simultaneously perform an add, a multiply and a load) Pipeline: start performing an operation on one piece of data while finishing the same operation on anothe
6、r piece of data perform different stages of the same operation on different sets of operands at the same time (like an assembly line) Superpipeline: combination of superscalar and pipelining perform multiple pipelined operations at the same time Vector: load multiple pieces of data into special regi
7、sters and perform the same operation on all of them at the same time,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,6,Whats an Instruction?,Memory: e.g., load a value from a specific address in main memory into a specific register, or store a value from a spec
8、ific register into a specific address in main memory Arithmetic: e.g., add two specific registers together and put their sum in a specific register or subtract, multiply, divide, square root, etc Logical: e.g., determine whether two registers both contain nonzero values (“AND”) Branch: jump from one
9、 sequence of instructions to another and so on,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,7,Whats a Cycle?,Youve heard people talk about having a 2 GHz processor or a 3 GHz processor or whatever. (For example, Henrys laptop has a 1.5 GHz Pentium4.) Inside
10、every CPU is a little clock that ticks with a fixed frequency. We call each tick of the CPU clock a clock cycle or a cycle. So a 2 GHz processor has 2 billion clock cycles per second. Typically, a primitive operation (e.g., add, multiply, divide) takes a fixed number of cycles to execute (assuming n
11、o pipelining).,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,8,Whats the Relevance of Cycles?,Typically, a primitive operation (e.g., add, multiply, divide) takes a fixed number of cycles to execute (assuming no pipelining). IBM POWER4 1 Multiply or add: 6 cy
12、cles (64 bit floating point) Load: 4 cycles from L1 cache14 cycles from L2 cache Intel Pentium4 2 Multiply: 7 cycles (64 bit floating point) Add, subtract: 5 cycles (64 bit floating point) Divide, square root: 38 cycles (64 bit floating point) Tangent: 225-250 cycles (64 bit floating point),Scalar O
13、peration,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,10,DONT PANIC!,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,11,Scalar Operation,Load a into register R0 Load b into R1 Multiply R2 = R0 * R1 Load c into R3 Load d
14、 into R4 Multiply R5 = R3 * R4 Add R6 = R2 + R5 Store R6 into z,z = a * b + c * d;,How would this statement be executed?,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,12,Does Order Matter?,Load a into R0 Load b into R1 Multiply R2 = R0 * R1 Load c into R3 Loa
15、d d into R4 Multiply R5 = R3 * R4 Add R6 = R2 + R5 Store R6 into z,z = a * b + c * d;,In the cases where order doesnt matter, we say that the operations are independent of one another.,Load d into R0 Load c into R1 Multiply R2 = R0 * R1 Load b into R3 Load a into R4 Multiply R5 = R3 * R4 Add R6 = R2
16、 + R5 Store R6 into z,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,13,Superscalar Operation,Load a into R0 AND load b into R1 Multiply R2 = R0 * R1 AND load c into R3 AND load d into R4 Multiply R5 = R3 * R4 Add R6 = R2 + R5 Store R6 into z,z = a * b + c * d
17、;,So, we go from 8 operations down to 5. (Note: there are lots of simplifying assumptions here.),Loops,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,15,Loops Are Good,Most compilers are very good at optimizing loops, and not very good at optimizing other cons
18、tructs.,DO index = 1, lengthdst(index) = src1(index) + src2(index) END DO,Why?,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,16,Why Loops Are Good,Loops are very common in many programs. Also, its easier to optimize loops than more arbitrary sequences of inst
19、ructions: when a program does the same thing over and over, its easier to predict whats likely to happen next. So, hardware vendors have designed their products to be able to execute loops quickly.,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,17,DONT PANIC!,
20、Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,18,Superscalar Loops,DO i = 1, nz(i) = a(i)*b(i) + c(i)*d(i) END DO,Each of the iterations is completely independent of all of the other iterations; e.g.,z(1) = a(1)*b(1) + c(1)*d(1) has nothing to do withz(2) = a
21、(2)*b(2) + c(2)*d(2) Operations that are independent of each other can be performed in parallel.,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,19,Superscalar Loops,for (i = 0; i n; i+) zi = ai * bi + ci * di; ,Load ai into R0 AND load bi into R1 Multiply R2 =
22、 R0 * R1 AND load ci into R3 AND load di into R4 Multiply R5 = R3 * R4 AND load ai+1 into R0 AND load bi+1 into R1 Add R6 = R2 + R5 AND load ci+1 into R3 AND load di+1 into R4 Store R6 into zi AND multiply R2 = R0 * R1 etc etc etc Once this loop is “in flight,” each iteration adds only 2 operations
23、to the total, not 8.,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,20,Example: IBM POWER4,8-way Superscalar: can execute up to 8 operations at the same time1 2 integer arithmetic or logical operations, and 2 floating point arithmetic operations, and 2 memory
24、access (load or store) operations, and 1 branch operation, and 1 conditional operation,Pipelining,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,22,Pipelining,Pipelining is like an assembly line or a bucket brigade. An operation consists of multiple stages. Af
25、ter a particular set of operandsz(i)=a(i)*b(i)+c(i)*d(i)completes a particular stage, they move into the next stage. Then, another set of operandsz(i+1)=a(i+1)*b(i+1)+c(i+1)*d(i+1)can move into the stage that was just abandoned by the previous set.,Supercomputing in Plain English: ILP OU Supercomput
26、ing Center for Education & Research,23,DONT PANIC!,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,24,Pipelining Example,i = 1,i = 2,i = 3,i = 4,Computation time,If each stage takes, say, one CPU cycle, then once the loop gets going, each iteration of the loop
27、increases the total time by only one cycle. So a loop of length 1000 takes only 1004 cycles. 3,t = 0,t = 1,t = 2,t = 3,t = 4,t = 5,t = 6,t = 7,DONT PANIC!,DONT PANIC!,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,25,Pipelines: Example,IBM POWER4: pipeline len
28、gth 15 stages 1,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,26,Some Simple Loops,DO index = 1, lengthdst(index) = src1(index) + src2(index) END DO ! index = 1, lengthDO index = 1, lengthdst(index) = src1(index) - src2(index) END DO ! index = 1, lengthDO ind
29、ex = 1, lengthdst(index) = src1(index) * src2(index) END DO ! index = 1, lengthDO index = 1, lengthdst(index) = src1(index) / src2(index) END DO ! index = 1, lengthDO index = 1, lengthsum = sum + src(index) END DO ! index = 1, length,Reduction: convert array to scalar,Supercomputing in Plain English
30、: ILP OU Supercomputing Center for Education & Research,27,Slightly Less Simple Loops,DO index = 1, lengthdst(index) = src1(index) * src2(index) END DO ! index = 1, lengthDO index = 1, lengthdst(index) = MOD(src1(index), src2(index) END DO ! index = 1, lengthDO index = 1, lengthdst(index) = SQRT(src
31、(index) END DO ! index = 1, lengthDO index = 1, lengthdst(index) = COS(src(index) END DO ! index = 1, lengthDO index = 1, lengthdst(index) = EXP(src(index) END DO ! index = 1, lengthDO index = 1, lengthdst(index) = LOG(src(index) END DO ! index = 1, length,Loop Performance,Supercomputing in Plain En
32、glish: ILP OU Supercomputing Center for Education & Research,29,Performance Characteristics,Different operations take different amounts of time. Different processors types have different performance characteristics, but there are some characteristics that many platforms have in common. Different com
33、pilers, even on the same hardware, perform differently. On some processors, floating point and integer speeds are similar, while on others they differ.,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,30,Arithmetic Operation Speeds,Supercomputing in Plain Englis
34、h: ILP OU Supercomputing Center for Education & Research,31,Fast and Slow Operations,Fast: sum, add, subtract, multiply Medium: divide, mod (i.e., remainder) Slow: transcendental functions (sqrt, sin, exp) Incredibly slow: power xy for real x and y On most platforms, divide, mod and transcendental f
35、unctions are not pipelined, so a code will run faster if most of it is just adds, subtracts and multiplies (e.g., solving systems of linear equations by LU decomposition).,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,32,What Can Prevent Pipelining?,Certain e
36、vents make it very hard (maybe even impossible) for compilers to pipeline a loop, such as: array elements accessed in random order loop body too complicated if statements inside the loop (on some platforms) premature loop exits function/subroutine calls I/O,Supercomputing in Plain English: ILP OU Su
37、percomputing Center for Education & Research,33,How Do They Kill Pipelining?,Random access order: ordered array access is common, so pipelining hardware and compilers tend to be designed under the assumption that most loops will be ordered. Also, the pipeline will constantly stall because data will
38、come from main memory, not cache. Complicated loop body: the compiler gets too overwhelmed and cant figure out how to schedule the instructions.,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,34,How Do They Kill Pipelining?,if statements in the loop: on some p
39、latforms (but not all), the pipelines need to perform exactly the same operations over and over; if statements make that impossible. However, many CPUs can now perform speculative execution: both branches of the if statement are executed while the condition is being evaluated, but only one of the re
40、sults is retained (the one associated with the conditions value). Also, many CPUs can now perform branch prediction to head down the most likely compute path.,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,35,How Do They Kill Pipelining?,Function/subroutine ca
41、lls interrupt the flow of the program even more than if statements. They can take execution to a completely different part of the program, and pipelines arent set up to handle that. Loop exits are similar. Most compilers cant pipeline loops with premature or unpredictable exits. I/O: typically, I/O
42、is handled in subroutines (above). Also, I/O instructions can take control of the program away from the CPU (they can give control to I/O devices).,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,36,What If No Pipelining?,SLOW!(on most platforms),Supercomputing
43、 in Plain English: ILP OU Supercomputing Center for Education & Research,37,Randomly Permuted Loops,Superpipelining,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,39,Superpipelining,Superpipelining is a combination of superscalar and pipelining. So, a superpip
44、eline is a collection of multiple pipelines that can operate simultaneously. In other words, several different operations can execute simultaneously, and each of these operations can be broken into stages, each of which is filled all the time. So you can get multiple operations per CPU cycle. For ex
45、ample, a IBM Power4 can have over 200 different operations “in flight” at the same time.1,Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,40,More Operations At a Time,If you put more operations into the code for a loop, youll get better performance: more operat
46、ions can execute at a time (use more pipelines), and you get better register/cache reuse. On most platforms, theres a limit to how many operations you can put in a loop to increase performance, but that limit varies among platforms, and can be quite large.,Supercomputing in Plain English: ILP OU Sup
47、ercomputing Center for Education & Research,41,Some Complicated Loops,DO index = 1, lengthdst(index) = src1(index) + 5.0 * src2(index) END DO ! index = 1, lengthdot = 0 DO index = 1, lengthdot = dot + src1(index) * src2(index) END DO ! index = 1, lengthDO index = 1, lengthdst(index) = src1(index) *
48、src2(index) + & src3(index) * src4(index) END DO ! index = 1, lengthDO index = 1, lengthdiff12 = src1(index) - src2(index)diff34 = src3(index) - src4(index)dst(index) = SQRT(diff12 * diff12 + diff34 * diff34) END DO ! index = 1, length,madd (or FMA): mult then add (2 ops),Euclidean distance (6 ops),
49、dot product (2 ops),from our example (3 ops),Supercomputing in Plain English: ILP OU Supercomputing Center for Education & Research,42,A Very Complicated Loop,lot = 0.0 DO index = 1, lengthlot = lot + & src1(index) * src2(index) + & src3(index) * src4(index) + & (src1(index) + src2(index) * & (src3(index) + src4(index) * & (src1(index) - src2(index) * & (src3(index) - src4(index) * & (src1(index) - src3(index) + & src2(index) - src4(index) * & (src1(index) + src3(index) - & src2(index) + src4(index) + & (src1(index) * src3(index) + & (src2(index) * src4(index) END DO ! index = 1, length,
