Architecture-Independent Loop ParallelisationArchitecture-independent programming and automatic parallelisation have long been regarded as two different means of alleviating the prohibitive costs of parallel software development. Building on recent advances in both areas, Architecture-Independent Loop Parallelisation proposes a unified approach to the parallelisation of scientific computing code. This novel approach is based on the bulk-synchronous parallel model of computation, and succeeds in automatically generating parallel code that is architecture-independent, scalable, and of analytically predictable performance. |
Contents
Introduction | 1 |
Communication Overheads in Loop Nest Scheduling | 4 |
Generic Loop Nest Parallelisation | 85 |
Copyright | |
7 other sections not shown
Other editions - View all
Common terms and phrases
a[Gi+v abstract syntax tree affine transformation algebraic path problem application architecture-independent array block array reference assign-stmt automatic parallelisation block-cyclic broadcast initialisation loop broadcast loop nest bsp_sync BSPSCHEDULER communication and synchronisation communication cost communication overheads comprises data dependence data partition dependence analysis dependence graph described distance vectors distribution elimination endfor endfor execution footprint forall Gaussian elimination identifier ik₁ imperative programs implemented input iteration points iteration space iterative scheduling K-level linear loop body loop interchange loop nest parallelisation loop nest scheduling loop parallelisation loop skewing LU decomposition main computation loop nest in Figure optimal paral parallel code parallel computer parallel loops parallel schedule parallel version parallelisation scheme parallelisation strategy parallelisation techniques parser perfect loop nest potential parallelism processor programming pseudocode result S₁ scalar sequential code sequential loop nest step strongly connected components superstep Theorem tiling matrix untightly nested loop variable wavefront block scheduling