This shows you the differences between two versions of the page.
schedulers [2017/04/19 13:31] |
schedulers [2017/04/19 13:31] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | =====Schedulers===== | ||
+ | Thanks to ISL, we AlphaZ now have two schedulers. Multi-dimensional farkas scheduler by Paul Feautrier, and PLuTo scheduling by Uday Bondhugula. For details of the schedulers, refer to the corresponding articles. | ||
+ | @article{feautrier1992some, | ||
+ | title={Some efficient solutions to the affine scheduling problem. part II. multidimensional time}, | ||
+ | author={Feautrier, | ||
+ | journal={International Journal of Parallel Programming}, | ||
+ | volume={21}, | ||
+ | number={6}, | ||
+ | pages={389--420}, | ||
+ | year={1992}, | ||
+ | publisher={Springer} | ||
+ | } | ||
+ | |||
+ | @article{bondhugula2008practical, | ||
+ | title={A practical automatic polyhedral parallelizer and locality optimizer}, | ||
+ | author={Bondhugula, | ||
+ | journal={ACM SIGPLAN Notices}, | ||
+ | volume={43}, | ||
+ | number={6}, | ||
+ | pages={101--113}, | ||
+ | year={2008}, | ||
+ | publisher={ACM} | ||
+ | } | ||
+ | ====Scheduler Commands==== | ||
+ | Schedulers take PRDG (Polyhedral Reduced Dependence Graph) as inputs and returns affine functions for each node in the PRDG. Following commands are related to scheduling. | ||
+ | * BuildPRDG(Program, | ||
+ | * FarkasMDScheduler(PRDG) : Takes a PRDG and returns List< | ||
+ | * PlutoScheduler(PRDG) : Takes a PRDG and returns List< | ||
+ | * setSchedule(Program, | ||
+ | ====Scheduling Examples==== | ||
+ | Lets take a simple program, matrix multiply, as an example. | ||
+ | Matrix multiplication has a 3D iteration space, and the only dependence is along the k-axis for accumulating. | ||
+ | <sxh ab; gutter: | ||
+ | affine matrix_product {P, Q, R|P>1 && Q>1 && R>1} | ||
+ | | ||
+ | float B {k,j| 0< | ||
+ | | ||
+ | using // Using an accumulator locally | ||
+ | float temp_C {i, | ||
+ | through | ||
+ | | ||
+ | // For the computation of the value of temp_C at (i,j,k), | ||
+ | // we need the value of temp_C at (i,j,k-1), A at (i,k) and B at (k,j) | ||
+ | | ||
+ | | ||
+ | esac; | ||
+ | | ||
+ | . | ||
+ | </ | ||
+ | ===Farkas Scheduler=== | ||
+ | The following scripts uses FarkasMD scheduling to find schedules for the above program. | ||
+ | <sxh cs; gutter: | ||
+ | # Load Program and store as ' | ||
+ | prog = ReadAlphabets(" | ||
+ | # Define a variable ' | ||
+ | system = " | ||
+ | |||
+ | prdg = BuildPRDG(prog, | ||
+ | schedules = FarkasMDScheduler(prdg); | ||
+ | setSchedule(prog, | ||
+ | listSpaceTimeMaps(prog, | ||
+ | </ | ||
+ | The output should look like the following: | ||
+ | C (i, | ||
+ | temp_C (i, | ||
+ | ===SpaceTime Maps=== | ||
+ | SpaceTimeMap: | ||
+ | SpaceTimeMap: | ||
+ | Since Farkas scheduler tries to satisfy as much dependencies as possible in the outer dimensions, the k-axis has became the outer most dimension in the resulting schedule. | ||
+ | ===PLuTo Scheduler=== | ||
+ | The following is a similar script for matrix multiply, but uses PLuTo scheduling. | ||
+ | <sxh cs; gutter: | ||
+ | # Load Program and store as ' | ||
+ | prog = ReadAlphabets(" | ||
+ | # Define a variable ' | ||
+ | system = " | ||
+ | |||
+ | prdg = BuildPRDG(prog, | ||
+ | schedules = PlutoScheduler(prdg); | ||
+ | setSchedule(prog, | ||
+ | listSpaceTimeMaps(prog, | ||
+ | </ | ||
+ | The output should look like the following: | ||
+ | C (i, | ||
+ | temp_C (i, | ||
+ | ===SpaceTime Maps=== | ||
+ | SpaceTimeMap: | ||
+ | SpaceTimeMap: | ||
+ | Note that now the k-axis is the innermost dimension of the resulting schedules. Because PLuTo scheduler have a different cost function, the resulting schedule can be different. | ||
+ | ====PLuTo Scheduler for Jacobi 1D Stencil==== | ||
+ | Here is another example to illustrate the difference between Farkas and PLuTo scheduling. | ||
+ | The alphabets program below is a Jacobi-style stencil computation for 1D data. | ||
+ | Because of the dependence '' | ||
+ | <sxh ab; gutter: | ||
+ | affine jacobi_1d {TSTEPS,N | TSTEPS > 2 && N > 5} | ||
+ | given | ||
+ | double A {i|0< | ||
+ | returns | ||
+ | double B {t, | ||
+ | using | ||
+ | double temp_B {t, | ||
+ | through | ||
+ | |||
+ | temp_B[t, | ||
+ | {|t == 0} : A[i]; | ||
+ | {|t > 0 && 1< | ||
+ | {|t > 0 && 0==i } || {|t > 0 && i==N-1 } : temp_B[t-1, | ||
+ | esac; | ||
+ | |||
+ | B[t,i] = temp_B[t-1, | ||
+ | . | ||
+ | </ | ||
+ | PLuTo Scheduling, which tries to find tilable shcedules, gives the following. Note that the second dimension of the schedules are shifted by '' | ||
+ | temp_B (t, | ||
+ | B (t, | ||
+ | ===SpaceTime Maps=== | ||
+ | SpaceTimeMap: | ||
+ | SpaceTimeMap: | ||
+ | |||
+ | Farkas Scheduling does not try to produce tilable schedule, and thus gives the following schedule. | ||
+ | temp_B (t, | ||
+ | B (t, | ||
+ | ===SpaceTime Maps=== | ||
+ | SpaceTimeMap: | ||
+ | SpaceTimeMap: |