The Minimal Number of Communication Startups when Tiling Space-Time Mapped Programs
- Full Paper(.ps version)
Tiling is a well-known technique for cache-optimization or for obtaining
coarse grained parallelism. In our paper, we focus on the latter
aspect. In contrast to previous work, we apply tiling *after* a
space-time mapping (a parallelization based on a mathematical model
called the polyhedron model). We show that this new approach allows for
easier application of tiling methods compared to the traditional
approach (e.g., due to a simpler loop structure, the already extracted
fully permutable loops,...), and, at the same time, leads to more
efficient programs (e.g., due to the possibility of using more concrete
cost functions,...). Theoretical cost models are verified by practical
experiments which prove the effectiveness of the combination of loop
paralleization in the polytope model and tiling.
Please contact our
webadmin with any comments or changes.
Unless explicitly stated otherwise, all material is
copyright © The University of Edinburgh.