We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Space-Time Loop Tiling for Dynamic Programming Codes.
- Authors
Bielecki, Wlodzimierz; Palkowski, Marek
- Abstract
We present a new space-time loop tiling approach and demonstrate its application for the generation of parallel tiled code of enhanced locality for three dynamic programming algorithms. The technique envisages that, for each loop nest statement, sub-spaces are first generated so that the intersection of them results in space tiles. Space tiles can be enumerated in lexicographical order or in parallel by using the wave-front technique. Then, within each space tile, time slices are formed, which are enumerated in lexicographical order. Target tiles are represented with multiple time slices within each space tile. We explain the basic idea of space-time loop tiling and then illustrate it by means of an example. Then, we present a formal algorithm and prove its correctness. The algorithm is implemented in the publicly available TRACO compiler. Experimental results demonstrate that parallel codes generated by means of the presented approach outperform closely related manually generated ones or those generated by using affine transformations. The main advantage of code generated by means of the presented approach is its enhanced locality due to splitting each larger space tile into multiple smaller tiles represented with time slices.
- Subjects
DYNAMIC programming; SPACETIME; AFFINE transformations; TILES; PARALLEL programming; ALGORITHMS; SPACE-time codes
- Publication
Electronics (2079-9292), 2021, Vol 10, Issue 18, p2233
- ISSN
2079-9292
- Publication type
Article
- DOI
10.3390/electronics10182233