User Tools

Site Tools


schedulers

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

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,​ P.},
 +    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,​ U. and Hartono, A. and Ramanujam, J. and Sadayappan, P.},
 +    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,​ String, int) : Builds an instance of PRDG for the specified system. Second argument is system name. Third argument is an integer value treated as a boolean value, when true the input variables are excluded from the PRDG. It is usually preferred to use this option so that input variables are not scheduled.
 +  * FarkasMDScheduler(PRDG) : Takes a PRDG and returns List<​ScheduledStatement>;​ uses Farkas scheduling.
 +  * PlutoScheduler(PRDG) : Takes a PRDG and returns List<​ScheduledStatement>;​ uses PLuTo scheduling.
 +  * setSchedule(Program,​ String, List<​ScheduledStatement>​) : Applies the schedules computed to the TargetMapping.
 +====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:​true>​
 +affine matrix_product {P, Q, R|P>1 && Q>1 && R>1}
 +       ​given ​ float A {i,k| 0<​=i<​P && 0<​=k<​Q};​
 +              float B {k,j| 0<​=k<​Q && 0<​=j<​R}; ​
 +     ​returns ​ float C {i,j,k| 0<​=i<​P && 0<​=j<​R && k==Q+1};
 +using // Using an accumulator locally
 +   float temp_C {i,​j,​k|0<​=i<​P && 0<​=j<​R && 0<​=k<​=Q};​
 +through
 +   ​temp_C[i,​j,​k] = case
 +               // 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)
 +               ​{|k>​0} ​ : temp_C[i,​j,​k-1] + A[i,​k-1]*B[k-1,​j];​
 +               ​{|k==0} : 0; // Initialization of the accumulator
 +            esac;
 +   ​C[i,​j,​k] ​     = temp_C[i,​j,​k-1];​
 +.
 +</​sxh>​
 +===Farkas Scheduler===
 +The following scripts uses FarkasMD scheduling to find schedules for the above program.
 +<sxh cs; gutter:​true>​
 +# Load Program and store as '​prog'​
 +prog = ReadAlphabets("​../​../​testcases/​matrix_product/​matrix_product.ab"​);​
 +# Define a variable '​system'​ to store the system name
 +system = "​matrix_product";​
 +
 +prdg = BuildPRDG(prog,​ system, 1);
 +schedules = FarkasMDScheduler(prdg);​
 +setSchedule(prog,​ system, schedules);
 +listSpaceTimeMaps(prog,​ system);
 +</​sxh>​
 +The output should look like the following:
 +  C (i,​j,​k->​k,​j,​i)
 +  temp_C (i,​j,​k->​k,​j,​i)
 +  ===SpaceTime Maps===
 +  SpaceTimeMap:​ C (i,​j,​k->​k,​j,​i) [SEQUENTIAL,​ SEQUENTIAL, SEQUENTIAL]
 +  SpaceTimeMap:​ temp_C (i,​j,​k->​k,​j,​i) [SEQUENTIAL,​ SEQUENTIAL, SEQUENTIAL]
 +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:​true>​
 +# Load Program and store as '​prog'​
 +prog = ReadAlphabets("​../​../​testcases/​matrix_product/​matrix_product.ab"​);​
 +# Define a variable '​system'​ to store the system name
 +system = "​matrix_product";​
 +
 +prdg = BuildPRDG(prog,​ system, 1);
 +schedules = PlutoScheduler(prdg);​
 +setSchedule(prog,​ system, schedules);
 +listSpaceTimeMaps(prog,​ system);
 +</​sxh>​
 +The output should look like the following:
 +  C (i,​j,​k->​i,​j,​k)
 +  temp_C (i,​j,​k->​i,​j,​k)
 +  ===SpaceTime Maps===
 +  SpaceTimeMap:​ C (i,​j,​k->​i,​j,​k) [SEQUENTIAL,​ SEQUENTIAL, SEQUENTIAL]
 +  SpaceTimeMap:​ temp_C (i,​j,​k->​i,​j,​k) [SEQUENTIAL,​ SEQUENTIAL, SEQUENTIAL]
 +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 ''​(t,​i%%->​%%t,​i+1)'',​ this program is not tilable with the identity schedule.
 +<sxh ab; gutter:​true>​
 +affine jacobi_1d {TSTEPS,N | TSTEPS > 2 && N > 5}
 +given 
 + double A {i|0<​=i<​N};​
 +returns ​
 + double B {t,​i|0<​=i<​N && t==TSTEPS};
 +using 
 + double temp_B {t,​i|0<​=i<​N && 0<​=t<​TSTEPS};​
 +through
 +
 + temp_B[t,​i] = case
 + {|t == 0} : A[i];
 + {|t > 0 && 1<​=i<​N-1} ​ : (temp_B[t-1,​i-1] + temp_B[t-1,​i] + temp_B[t-1,​i+1])*0.33333;​
 + {|t > 0 && 0==i } || {|t > 0 && i==N-1 } : temp_B[t-1,​i];  ​
 + esac; ​
 +
 + B[t,i] = temp_B[t-1,​i]; ​
 +.
 +</​sxh>​
 +PLuTo Scheduling, which tries to find tilable shcedules, gives the following. Note that the second dimension of the schedules are shifted by ''​t''​. This is an instance of "​skewing",​ and this schedule is tilable.
 +  temp_B (t,​i->​t,​i+t)
 +  B (t,​i->​t,​i+t)
 +  ===SpaceTime Maps===
 +  SpaceTimeMap:​ temp_B (t,​i->​t,​i+t) [SEQUENTIAL,​ SEQUENTIAL]
 +  SpaceTimeMap:​ B (t,​i->​t,​i+t) [SEQUENTIAL,​ SEQUENTIAL]
 +
 +Farkas Scheduling does not try to produce tilable schedule, and thus gives the following schedule.
 +  temp_B (t,​i->​t,​i)
 +  B (t,​i->​t,​i)
 +  ===SpaceTime Maps===
 +  SpaceTimeMap:​ temp_B (t,​i->​t,​i) [SEQUENTIAL,​ SEQUENTIAL]
 +  SpaceTimeMap:​ B (t,​i->​t,​i) [SEQUENTIAL,​ SEQUENTIAL]
schedulers.txt ยท Last modified: 2017/04/19 13:31 (external edit)