Index set splitting

Citation
M. Griebl et al., Index set splitting, INT J P PRO, 28(6), 2000, pp. 607-631
Citations number
26
Categorie Soggetti
Computer Science & Engineering
Journal title
INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING
ISSN journal
08857458 → ACNP
Volume
28
Issue
6
Year of publication
2000
Pages
607 - 631
Database
ISI
SICI code
0885-7458(200012)28:6<607:ISS>2.0.ZU;2-C
Abstract
There are many algorithms for the space-time mapping of nested loops. Some of them even make the optimal choices within their framework. We propose a preprocessing phase for algorithms in the polytope model, which extends the model and yields space-time mappings whose schedule is, in some cases, ord ers of magnitude faster. These are cases in which the dependence graph has small irregularities. The basic idea is to split the index set of the loop nests into parts with a regular dependence structure and apply the existing space-time mapping algorithms to these parts individually. This work is ba sed on a seminal idea in the more limited context of loop parallelization a t the code level. We elevate the idea to the model level (our model is the polytope model), which increases its applicability by providing a clearer a nd wider range of choices at an acceptable analysis cost. Index set splitti ng is one facet in the effort to extend the power of the polytope model and to enable the generation of competitive tar-get code.