Informatics Report Series


Report   

EDI-INF-RR-0497


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:Combined Selection of Tile Sizes and Unroll Factors Using Iterative Compilation
Authors: Peter M.W. Knijnenburg ; Toru Kisuki ; Michael O'Boyle
Date:Jan 2003
Publication Title:Journal of SuperComputing
Publication Type:Journal Article
Volume No:24(1) Page Nos:43-67
Abstract:
Loop tiling and unrolling are two important program transformations to exploit locality and expose instruction level parallelism, respectively. However, these transformations are not independent and each can adversely affect the goal of the other. Furthermore, the best combination will vary dramatically from one processor to the next. In this paper, we therefore address the problem of how to select tile sizes and unroll factors simultaneously. We approach this problem in an architecturally adaptive manner by means of iterative compilation, where we generate many versions of a program and decide upon the best by actually executing them and measuring their execution time. We evaluate several iterative strategies based on genetic algorithms, random sampling and simulated annealing. We compare the levels of optimization obtained by iterative compilation to several well-known static techniques and show that we outperform each of them on a range of benchmarks across a variety of architectures. Finally, we show how to quantitatively trade-off the number of profiles needed and the level of optimization that can be reached. In this way, we can reach high levels of optimization within 50 iterations.
Links To Paper
1st Link
Bibtex format
@Article{EDI-INF-RR-0497,
author = { Peter M.W. Knijnenburg and Toru Kisuki and Michael O'Boyle },
title = {Combined Selection of Tile Sizes and Unroll Factors Using Iterative Compilation},
journal = {Journal of SuperComputing},
year = 2003,
month = {Jan},
volume = {24(1)},
pages = {43-67},
url = {http://ieeexplore.ieee.org/iel5/7126/19206/00888348.pdf?arnumber=888348},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh