Architecture-Independent Loop Parallelisation

INTRODUCTION: Motivation. Parallelisation approach proposed in the book. Organisation of the book.- THE BULK-SYNCHRONOUS PARALLEL MODEL: Introduction. Bulk-synchronous parallel computers. The BSP programming model. The BSP cost model. Assessing the efficiency of BSP code. The development of BSP applications. BSP pseudocode.- DATA DEPENDENCE ANALYSIS AND CODE TRANSFORMATION: Introduction. Data dependence. Code transformation techniques.- COMMUNICATION OVERHEADS IN LOOP NEST SCHEDULING: Introduction. Related work. Communication overheads due to input data. Inter-tile communication overheads. Summary.- TEMPLATE-MATCHING PARALLELISATION: Introduction. Related work. Communication-free scheduling. Wavefront block scheduling. Iterative scheduling. Reduction scheduling. Recurrence scheduling. Scheduling broadcast loop nests. Summary.- GENERIC LOOP NEST PARALLELISATION: Introduction. Related work. Data dependence analysis. Potential parallelism identification. Data and computation partitioning. Communication and synchronisation generation. Performance analysis. Summary.- A STRATEGY AND A TOOL FOR ARCHITECTURE-INDEPENDENT LOOP PARALLELISATION: Introduction. Related work. A two-phase strategy for loop nest parallelisation. BSPscheduler: an architecture-independent loop paralleliser. Summary.- THE EFFECTIVENESS OF ARCHITECTURE-INDEPENDENT LOOP PARALLELISATION: Introduction. Matrix-vector and matrix-matrix multiplication. LU decomposition. Algebraic path problem. Finite difference iteration on a Cartesian grid. Merging. Summary.- CONCLUSIONS: Summary of contributions and concluding remarks. Future work directions.- A: THEOREM PROOFS.- B: SYNTAX OF THE BSPSCHEDULER INPUT LANGUAGE.- C: SYNTAX OF THE BSPSCHEDULER OUTPUT LANGUAGE.- D: AUTOMATICALLY GENERATED CODE FOR EXAMPLE 7.5.- Bibliography.- Index.