Loop Tiling for ParallelismSpringer Science & Business Media, 31 août 2000 - 256 pages Loop tiling, as one of the most important compiler optimizations, is beneficial for both parallel machines and uniprocessors with a memory hierarchy. This book explores the use of loop tiling for reducing communication cost and improving parallelism for distributed memory machines. The author provides mathematical foundations, investigates loop permutability in the framework of nonsingular loop transformations, discusses the necessary machineries required, and presents state-of-the-art results for finding communication- and time-minimal tiling choices. Throughout the book, theorems and algorithms are illustrated with numerous examples and diagrams. The techniques presented in Loop Tiling for Parallelism can be adapted to work for a cluster of workstations, and are also directly applicable to shared-memory machines once the machines are modeled as BSP (Bulk Synchronous Parallel) machines. Features and key topics:
|
Table des matières
V | 3 |
VII | 4 |
X | 6 |
XI | 11 |
XII | 17 |
XIII | 19 |
XIV | 20 |
XV | 28 |
XXXVIII | 120 |
XXXIX | 123 |
XL | 124 |
XLI | 130 |
XLII | 131 |
XLIII | 133 |
XLIV | 134 |
XLV | 137 |
XVI | 32 |
XVII | 35 |
XVIII | 36 |
XIX | 38 |
XX | 43 |
XXI | 59 |
XXII | 67 |
XXIII | 73 |
XXIV | 74 |
XXV | 78 |
XXVI | 85 |
XXVIII | 87 |
XXIX | 94 |
XXX | 96 |
XXXI | 101 |
XXXII | 102 |
XXXIII | 107 |
XXXIV | 113 |
XXXVI | 116 |
XXXVII | 118 |
XLVI | 146 |
XLVII | 156 |
XLVIII | 158 |
XLIX | 160 |
L | 168 |
LI | 169 |
LII | 172 |
LIII | 176 |
LIV | 179 |
LV | 187 |
LVI | 196 |
LVIII | 199 |
LX | 201 |
LXI | 202 |
LXII | 204 |
LXIV | 233 |
LXV | 245 |
247 | |
255 | |
Autres éditions - Tout afficher
Expressions et termes fréquents
algorithm array boundary canonical transformation Chapter column communication set communication volume computation convex cones d₁ data dependences defined denoted dependence cone dependence vector distance vectors distribution dmax dmin element loops equation execution extremal rays Ffree Fidle Fourier-Motzkin elimination function Hermite normal form hopt i₁ inequalities integer matrix integer points k-th legality test Lemma lexicographic order linear loop bounds loop indices loop nest loop skewing loop tiling loop transformations mapping message-passing code Minimise nonlocal data nonnegative nonsingular transformation optimal solution optimal tile optimisation problem parallelepiped tiling pass-free pass-idle perfect loop nest permutable loop nests permutable nest polyhedral polyhedron polytope positive root Proof PTab quartic equation read-only data rectangular tiling shown in Figure space graph SPMD code t₁ t₂ Tfree Theorem Tidle tile dependences tile loops tile sizes tiled code tiled iteration space transformed program unimodular matrix unimodular transformation Wopt
Fréquemment cités
Page iii - School of Computer Science and Engineering, The University of New South Wales, Sydney, NSW 2052, Australia, Email: arun@cse.unsw.edu.au Abstract.
Page 252 - Static and dynamic evaluation of data dependence analysis techniques. IEEE Transactions on Parallel and Distributed Systems, 7(1 1):1 121-1 132, november 1996. [31] K. Psarris and K. Kyriakopoulos. An experimental evaluation of data dependence analysis techniques.