TriDenT CoLUMBO

My Research Team was in the University of Bordeaux I in the laboratory named LABRI (LABoratory of Research in Informatique/Computer Science). Our works began with the study in a new way to describe irregular data structures in HPF. This method is based on a treelike writing of the data structures by way of the derived types of Fortran 90/95 and the extensions approved of HPF 2.0. These notations allow to remove present necessary indirect accesses in the writing of the classic irregular data structures as the CCS (Compressed Column Storage). Indirect accesses prevent the compiler from generating parallel effective codes because of the not knowledge of the values of these indirect indices.

Following example shows a sparse matrix with accesses directed by column, its show under shape of a tree and its writing in HPF 2.0 as well as its distribution.

In spite of this improvement of analyses in the compilation, it remains unknown information during this one. The parallel properties of these applications are not, as a consequence, exploitable during the compilation. It is necessary to use paradigm of inspection-execution.

The compiler generates a code containing two phases: first phase, inspection, scans these information only known in the execution to produce, during the second phase, the execution, the realization of calculations with plans optimized as at the level of the communications as of the distribution of calculations. We used this paradigm for various properties which were not studied in the previous works until this day. We were notably interested in the cases of loops with partial inter-iterations dependences (BDIIP (french) - LPIID).
It should be noted that our inspector - executor is very different from classic approaches in the sense where, in our study, inspection must be made profitable with only one phase of execution, contrary to the other approaches which are used in an iterative context, that is to say with several identical phases of execution in terms of access and communications.

• Irregular sets of processors

• Irregular indexes of loops

• Communications inter-and extra - iterations (LPIID)

• Scheduling of the DAG associated to a LPIID

• Progressive Irregular Prefixe Operations

We present quickly each of these inspections - executions :

This is the results of a Cholesky factorization of sparse matrices in block-columns 1D version (distribution of blocks-columns). Every versions include more and more optimizations.

The last version corresponds to a Team's Cholesky factorization with important performances [A Mapping and Scheduling Algorithm for Parallel Sparse Fan-In Numerical Factorization, EuroPar'99, 1999, P. Henon, P. Ramet and J. Roman].

Factorization is placed in an iterative frame with a constant sparse matrix structure (only values evolve), as in Karmarkar's algorithm which solves AX system = B and which minimizes a function objectivizes CTX.