1.2 Defining a Scanning Order: Scattering Functions

In CLooG, domains only define the set of integral points to scan and their coordinates. In particular, CLooG is free to choose the scanning order for generating the most efficient code. This means, for optimizing/parallelizing compiler people, that CLooG doesn’t make any speculation on dependences on and between statements (by the way, it’s not its job !). For instance, if an user give to CLooG only two domains S1:1<=i<=n, S2:1<=i<=n and the context n>=1, the following pseudo-codes are considered to be equivalent:

/* A convenient target pseudo-code. */
for (i=1;i<=N;i++) {
 S1(i) ;
}
for (i=1;i<=N;i++) {
 S2(i) ;
}

/* Another convenient target pseudo-code. */
for (i=1;i<=N;i++) {
 S1(i) ;
 S2(i) ;
}

The default behaviour of CLooG is to generate the second one, since it is optimized in control. It is right if there are no data dependences between S1 and S2, but wrong otherwise.

Thus it is often useful to force scanning to respect a given order. This can be done in CLooG by using scattering functions. Scattering is a shortcut for scheduling, allocation, chunking functions and the like we can find in the restructuring compilation literature. There are a lot of reasons to scatter the integral points of the domains (i.e. the statement instances of a program, for compilation people), parallelization or optimization are good examples. For instance, if the user wants for any reason to set some precedence constraints between the statements of our example above in order to force the generation of the first code, he can do it easily by setting (for example) the following scheduling functions:

T_S1(i) = (1)
T_S2(j) = (2)

This scattering means that each integral point of the domain S1 is scanned at logical date 1 while each integral point of the domain S2 is scanned at logical date 2. As a result, the whole domain S1 is scanned before domain S2 and the first code in our example is generated.

The user can set every kind of affine scanning order thanks to the scattering functions. Each domain has its own scattering function and each scattering function may be multi-dimensional. A multi-dimensional logical date may be seen as classical date (year,month,day,hour,minute,etc.) where the first dimensions are the most significant. Each scattering dimension may depend linearly on the original dimensions (e.g., i), the parameters (e.g., n) ans scalars (e.g., 2).

A very useful example of multi-dimensional scattering functions is, for compilation people, the scheduling of the original program. The basic data to use for code generation are statement iteration domains. As we saw, these data are not sufficient to rebuild the original program (what is the ordering between instances of different statements ?). The missing data can be put in the scattering functions as the original scheduling. The method to compute it is quite simple (see Fea92). The idea is to build an abstract syntax tree of the program and to read the scheduling for each statement. For instance, let us consider the following implementation of a Cholesky factorization:

/* A Cholesky factorization kernel. */
for (i=1;i<=N;i++) {
  for (j=1;j<=i-1;j++) {
    a[i][i] -= a[i][j] ;           /* S1 */
  }
  a[i][i] = sqrt(a[i][i]) ;        /* S2 */
  for (j=i+1;j<=N;j++) {
    for (k=1;k<=i-1;k++) {
      a[j][i] -= a[j][k]*a[i][k] ; /* S3 */
    }
    a[j][i] /= a[i][i] ;           /* S4 */
    }
  }
}

The corresponding abstract syntax tree is given in the following figure. It directly gives the scattering functions (schedules) for all the statements of the program.

T_S1(i,j)^T   = (0,i,0,j,0)^T
T_S2(i)       = (0,i,1)^T
T_S3(i,j,k)^T = (0,i,2,j,0,k,0)^T
T_S4(i,j)^T   = (0,i,2,j,1)^T

These schedules depend on the iterators and give for each instance of each statement a unique execution date. Using such scattering functions allow CLooG to re-generate the input code.

This document was generated on August 20, 2013 using texi2html 5.0.