> >CRPC-TR93324-S: Initial Framework for Automatic Data Layout in
> >                Fortran D: A Short Update on a Case Study



> >Keywords:
> >
> >  interactive programming environment; Fortran D; automatic data layout; 
> >  automatic alignment; automatic distribution; distributed-memory machines; 
> >  search space approach; pruning heuristics 
> >
> >Abstract:
> >
> >We discuss an automatic data layout algorithm that takes Fortran 77 programs 
> >written in a data-parallel programming style as input and generates Fortran D
> >programs with data layout specifications. The generated specifications 
> >determine the layout of all arrays in the input program. 
> >
> >The algorithm partitions the program into code segments, called phases.
> >A phase represents a computation that does not require any data remapping. 
> >Alignment and distribution analysis are based on the phase concept.
> >The initial automatic data layout algorithm generates alignment and
> >distribution specifications for each phase.
> >
> >Alignment and distribution analysis use a search space approach to 
> >determine a set of good data layout schemes for each phase. The final 
> >selection of a single data layout scheme for each phase considers the
> >profitability of data remapping between phases.
> >
> >In this report, we describe the general concept of our search space 
> >approach. We provide the sizes of the exhaustive search spaces for 
> >alignment and distribution under some simplifying assumptions. We discuss 
> >pruning heuristics for alignment analysis and determine the maximal sizes 
> >of the resulting search spaces. As an indication of the feasibility
> >of our approach, we give the sizes of the exhaustive and pruned search 
> >spaces for two programs, namely Erlebacher (3-dimensional tridiagonal
> >solver) and ADI (alternate direction implicit integration).