The optimization and parallelization of array language programs
Dz-Ching Ju · 1992
An array language embodies a rich set of array primitives and can provide an effective paradigm for developing portable parallel programs. This portable paradigm cannot be effective, however, unless compilers generate efficient codes for both single array operators and combinations of array operators. The optimization and parallelization schemes presented here make use of the semantic information of array primitives to reduce storage usage and synchronization overhead. These techniques enable a compiler to generate a more efficient code. Five techniques are developed and presented which improve the performance of array language programs at different levels. They are dynamic processor allocation, primitive fusion, primitive synthesis, statement merge, and inter-statement fusion. The dynamic processor allocation, an intra-primitive optimization scheme, estimates the number of processors for the optimal performance of a primitive at run time. Primitive fusion and primitive synthesis both optimize programs at the inter-primitive level. Primitive fusion aggressively fuses the translated loops of the same and different types of primitives. Primitive synthesis combines each of the data access patterns of multiple consecutive array functions into a single direct access to the source operand. Statement merge performs an inter-statement optimization to merge two statements through a def-use chain of a program variable for further inter-primitive optimizations. Inter-statement fusion generates a combined loop for statements with the same loop size. Experimental results on a Sequent Symmetry machine verify the benefits obtained by using each of the five techniques. The experimental results also show that the performance of array language programs can be effectively improved by using each of these optimizations separately or together. Five representative LINPACK routines achieve a two fold speedup by employing these optimizations. The enhancements of other interesting large scientific applications vary between a 1.7 and a 3.9 fold speedup. These techniques are applicable to compilers designed for Fortran 90, APL, and any other programming language that incorporates array primitives, such as C*.