DependencePrecedence

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Slide,*,DependencePrecedence,Lecture 26,1,Precedence & Dependence,Can we execute a 1000 line program with 1000 processors in one step?,What are the issues to deal with in various parallelizing situations:,Parallel Programming?,Instruction Level Parallelism?,What type analysis is used to study concurrent database operation?,2,Dependence,3,Making Use of Processors,In parallelizing algorithms, we want to,use as many processors,as possible in an effort to finish in as little time as possible.,Often, it is not possible to make complete use of all processors in all time units,Some instructions (or sections of instructions),depend upon others,Others have a different, related problem called,precedence,(next section),4,Input and Output,Input and output cannot be parallelized in the strict sense because were dealing with a user.,We assume multiple, parallel streams of input and output (modems, etc.).,5,Read and Print statements,Read(x)x -,keyboard,Print(x),screen,- x,6,Dependency Relationships,Dependencies are relationships between the steps of an algorithm such that,one step depends upon another,.,(S1)read (,a,),(S2),b,-,a,* 3,(S3)c -,b,*,a,7,Dependency Relationships,Dependencies are relationships between the steps of an algorithm such that,one step depends upon another,.,(S1),a,-,keyboard,(S2),b,-,a,* 3,(S3)c -,b,*,a,Here, S2 is dependent on S1 to provide the appropriate value of a.,Similarly, S3 is dependent on both S1 (for as value) and S2 (for bs value).,Since S2 needs,a,also, we can simply say that S3 is dependent on S2.,Dont need,8,Dependence,Defined by a “read after write”,*,relationship,This means moving from the left to the right side of the assignment operator.,a - 5,b - a + 2,*,Note: “Read” and “Write” in,this case refer to reading the,value from a memory location,and writing a value to a memory,location. Not Input/Output.,9,Graphing Dependence Relations,S1,S2,Processors,Time,10,(S1)read (a),(S2)b - a * 3,(S3)c - b * a,Dependency Graphs,11,(S1),a -,keyboard,(S2)b - a * 3,(S3)c - b * a,In this case, it,does not matter,how many processors we have; we can use,only one,processor to finish in,3 time units.,Dependency Graphs,S1,S2,S3,Processors,Time,12,What If There Are No Dependencies?,S1,S2,S3,(S1) read (a),(S2) b - b + 3,(S3) c - c + 4,We can use,three processors,to get it done in a,single time chunk,.,Processors,Time,13,A Dependency Example,(S1) read (a),(S2) read (b),(S3) c - a * 4,(S4) d - b / 3,(S5) e - c * d,(S6) f - d + 8,14,A Dependency Example,(S1),a -,keyboard,(S2),b -,keyboard,(S3) c - a * 4,(S4) d - b / 3,(S5) e - c * d,(S6) f - d + 8,15,A Dependency Example,(S1) a -,keyboard,(S2) b -,keyboard,(S3) c - a * 4,(S4) d - b / 3,(S5) e - c * d,(S6) f - d + 8,S1,S2,16,A Dependency Example,(S1),a,-,keyboard,(S2) b -,keyboard,(S3) c -,a,* 4,(S4) d - b / 3,(S5) e - c * d,(S6) f - d + 8,S1,S2,S3,17,A Dependency Example,(S1) a -,keyboard,(S2),b,-,keyboard,(S3) c - a * 4,(S4) d -,b,/ 3,(S5) e - c * d,(S6) f - d + 8,S1,S2,S3,S4,18,A Dependency Example,(S1) a -,keyboard,(S2) b -,keyboard,(S3),c,- a * 4,(S4),d,- b / 3,(S5) e -,c,*,d,(S6) f - d + 8,S1,S2,S3,S4,S5,19,A Dependency Example,(S1) a -,keyboard,(S2) b -,keyboard,(S3) c - a * 4,(S4),d,- b / 3,(S5) e - c * d,(S6) f -,d,+ 8,S1,S2,S3,S4,S5,S6,20,A Dependency Example,(S1) a -,keyboard,(S2) b -,keyboard,(S3) c - a * 4,(S4) d - b / 3,(S5) e - c * d,(S6) f - d + 8,S1,S2,S3,S4,S5,S6,Using 2 processors,we finish 6 instructionsin 3 units of time.,WOW!,21,Dependence and Iteration,Ignore steps that are not part of loop (overhead costs similar to making parallelism work),Dont worry about loop, exitif, counter variables, endloop, etc.,Use notation to indicate passes: “ “,Unroll the loop, replacing the counter variable with a literal value.,22,An Iterative Example,I MAX_ARRAY),(S1)read (AI),(S2)BI - AI + 4,(S3)CI - AI / 3,(S4)DI - BI / CI,I - I + 1,endloop,23,(S1) read (A1),(S2) B1 - A1 + 4,(S3) C1 - A1 / 3,(S4) D1 - B1 / C1,(S1) read (A2),(S2) B2 - A2 + 4,(S3) C2 - A2 / 3,(S4) D2 - B2 / C2,(S1”) read (A3),(S2”) B3 - A3 + 4,(S3”) C3 - A3 / 3,(S4”) D3 - B3 / C3,Any interference between iterations?,S1,S2,S4,S3,One,iteration,24,An Iterative Example,S1,S2,S4,S3,S1,S2,S4,S3,S1”,S2”,S4”,S3”,Using 6 Processors,25,Limited Number of Processors,What if the number of processors is fixed?,Some processors may be being used by another program/user,If the number of processors available are less than the number of processors that can be utilized, shift instructions into lower time units.,26,A Limited Processor Example,Two Processors,S1,S2,S4,S3,S1,S2,S4,S3,S1”,S2”,S4”,S3”,27,Questions?,28,Precedence,29,Precedence Relationships,Exists,if a statement would contaminate the data,needed by another, preceding instruction.,(S1)read (,a,),(S2)print (,a,),(S3)a - a * 7,(S4)print (a),30,Precedence Relationships,Exists,if a statement would contaminate the data,needed by another, preceding instruction.,(S1)a -,keyboard,(S2),screen,- a,(S3)a - a * 7,(S4)screen - a,S2 and S3 are dependent on S1 (for the initial value of a).,31,Precedence Relationships,Exists,if a statement would contaminate the data,needed by another, preceding instruction.,(S1)a -,keyboard,(S2),screen,- a,(S3)a - a * 7,(S4)screen - a,S2 and S3 are dependent on S1 (for the initial value of a).,S4 is dependent on S3 (for updated a).,32,Precedence Relationships,Exists,if a statement would contaminate the data,needed by another, preceding instruction.,(S1)a -,keyboard,(S2),screen,- a,(S3)a - a * 7,(S4)screen - a,S2 and S3 are dependent on S1 (for the initial value of a).,S4 is dependent on S3 (for updated a).,There is also a precedence relationship between S2 and S3.,33,Precedence Relationships,Exists,if a statement would contaminate the data,needed by another, preceding instruction.,(S1)a -,keyboard,(S2),screen,- a,(S3)a - a * 7,(S4)screen - a,S2 and S3 are dependent on S1 (for the initial value of a).,S4 is dependent on S3 (for updated a).,There is also a precedence relationship between S2 and S3.,S3 must follow S2, else S3 could corrupt what S2 does.,34,Precedence Relationships,Exists,if a statement would contaminate the data,needed by another, preceding instruction.,(S1)a -,keyboard,(S2),screen,- a,(S3)a - a * 7,(S4)screen - a,S2 and S3 are dependent on S1 (for the initial value of a).,S4 is dependent on S3 (for updated a).,There is also a precedence relationship between S2 and S3.,S3 must follow S2, else S3 will corrupt what S2 does.,35,Precedence,Defined by a “write after write” or “write after read” relationship.,This means using the variable on the left side of the assignment operator,after,it has appeared previously on the right,or,left.,b - a + 2a - 7,a - 5a - 5,36,Showing Precedence Relations,S1,S2,Processors,Time,37,Precedence Graphs,(S1)read (a),(S2)print (,a,),(S3),a,- a * 7,(S4)print (a),38,S1,S2,S3,S4,Precedence Graphs,(S1)a -,keyboard,(S2),screen,-,a,(S3),a,- a * 7,(S4),screen,- a,Precedence arrow,blocks,S3 from executing until S2 is finished.,39,S1,S2,S3,S4,Precedence Graphs,(S1)a -,keyboard,(S2),screen,-,a,(S3),a,- a * 7,(S4),screen,- a,Precedence arrow,blocks,S3 from executing until S2 is finished.,Dependency arrow between S1 and S3 is superfluous,40,What if there is No Precedence?,(S1) read (a),(S2) b - b + 3,(S3) c - c + 4,We can use,three processors,to get it done in a,single time chunk,.,S1,S2,S3,41,Precedence and Iteration,Ignore steps that are not part of loop (overhead costs similar to making parallelism work),Dont worry about loop, exitif, counter variables, endloop, etc.,Use notation to indicated passes: “ “,Unroll the loop, replacing the counter variable with a literal value.,Same as dependence.,42,An Iterative Example,i 3),(S1)read (a),(S2)print (a),(S3)a - a * 7,(S4)print (a),i - i + 1,endloop,43,An Iterative Example,i 3),(S1)a -,keyboard,(S2),screen,- a,(S3)a - a * 7,(S4),screen,- a,i - i + 1,endloop,44,(S1) a -,keyboard,(S2),screen,- a,(S3) a - a * 7,(S4),screen,- a,(S1) a -,keyboard,(S2),screen,- a,(S3) a - a * 7,(S4),screen,- a,(S1”) a -,keyboard,(S2”),screen,- a,(S3”) a - a * 7,(S4”),screen,- a,S4,S1,S2,S3,S1,45,S1,S2,S3,S4,S1,S2,S3,S4,S1”,S2”,S3”,S4”,Iteration and PrecedenceGraphs,46,Space vs. Time,We can optimize time performance by changing,shared variable,to an,array of independent variables.,i 3),(S1)read (ai),(S2)print (ai),(S3)ai - ai * 7,(S4)print (ai),i - i + 1,endloop,47,S1,S2,S3,S4,S1,S2,S3,S4,S1”,S2”,S3”,S4”,Precedence Graphs,We can use 3 processors to finish in 4 time units.,Note that,product complexity,is unchanged.,48,What if Both Precedence and Dependence?,If two instructions have both a precedence and a dependence relation,(S1) a - 5,(S2) a - a + 2,showing only dependence is sufficient.,S1,S2,49,Another Iterative Example,i N),(S1) read (ai),(S2) ai - ai * 7,(S3) c - ai / 3,(S4) print (c),i - i + 1,endloop,50,Another Iterative Example,i N),(S1) ai -,keyboard,(S2) ai - ai * 7,(S3) c - ai / 3,(S4),screen,- c,i - i + 1,endloop,51,(S1) a1 -,keyboard,(S2) a1 - a1 * 7,(S3) c - a1 / 3,(S4),screen,- c,(S1) a2 -,keyboard,(S2) a2 - a2 * 7,(S3) c - a2 / 3,(S4),screen,- c,(S1”) a3 -,keyboard,(S2”) a3 - a3 * 7,(S3”) c - a3 / 3,(S4”),screen,- c,52,S1,S2,S3,S4,S1,S2,S3,S4,S1”,S2”,S3”,S4”,We have precedence,relationships,between iterations,because of the shared,c variable.,53,Crossing Index Bounds Example,I MAX ) / MAX is 3,(S1)AI - AI + BI,(S2)read( BI ),(S3)CI - AI * 3,(S4)DI - BI * A,I+1,I - I + 1,endloop,54,Crossing Index Bounds Example,I MAX ) / MAX is 3,(S1) AI - AI + BI,(S2) BI -,keyboard,(S3) CI - AI * 3,(S4) DI - BI * A,I+1,I - I + 1,endloop,55,(S1) A1 - A1 + B1,(S2) B1 -,keyboard,(S3) C1 - A1 * 3,(S4) D1 - B1 * A2,(S1) A2 - A2 + B2,(S2) B2 -,keyboard,(S3) C2 - A2 * 3,(S4) D2 - B2 * A3,(S1”) A3 - A3 + B3,(S2”) B3 -,keyboard,(S3”) C3 - A3 * 3,(S4”) D3 - B3 * A4,56,Precedence betweeniterations,S1,S2,S4,S3,S1,S2,S4,S3,57,Questions?,58,Practical Applications,We used the single assignments as easy illustrations of the principles.,There are additional real applications of this capability:,Much bigger than one assignment,Smaller than one assignment,59,60,Large Data Sets,Consider the SETI project,What do you now know about the data that makes it practical to distribute across millions of processors?,No precedence or dependence between data sets!,61,Instruction Processing,Break computers processing into steps,A - fetch instruction,B - fetch data,C - logical processing (math, test and branch),D - store result,Independent for all sequential processing,Dependency occurs when branch “ruins” three instruction fetches,1,5,4,3,2,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,A,B,C,D,1,2,3,4,5,6,7,0,time,I MAX),endloop,I -,I + 1,blah.,blah.,blah.,62,Questions?,63,