Informatics Report Series



Related Pages

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

Title:Fast and Accurate Method for Determining a Lower Bound on Execution Time
Authors: Grigori Fursin ; Michael O'Boyle ; Olivier Temam ; Gregory Watts
Date:Feb 2004
Publication Title:Concurrency Practice and Experience
Publication Type:Journal Article
Volume No:16(2-3) Page Nos:271-292
In performance critical applications, memory latency is frequently the dominant overhead. In many cases, automatic compiler-based optimizations to improve memory performance are limited and programmers frequently resort to manual optimization techniques. However, this process is tedious and time-consuming. Furthermore, as the potential benefit from optimization is unknown there is no way to judge the amount of effort worth expending, nor when the process can stop, i.e. when optimal memory performance has been achieved or sufficiently approached. Architecture simulators can provide such information but designing an accurate model of an existing architecture is difficult and simulation times are excessively long. In this article, we propose and implement a technique that is both fast and reasonably accurate for estimating a lower bound on execution time for scientific applications. This technique has been tested on a wide range of programs from the SPEC benchmark suite and two commercial applications, where it has been used to guide a manual optimization process and iterative compilation. We compare our technique with that of a simulator with an ideal memory behaviour and demonstrate that our technique provides comparable information on memory performance and yet is over two orders of magnitude faster. We further show that our technique is considerably more accurate than hardware counters.
Links To Paper
1st Link
Bibtex format
author = { Grigori Fursin and Michael O'Boyle and Olivier Temam and Gregory Watts },
title = {Fast and Accurate Method for Determining a Lower Bound on Execution Time},
journal = {Concurrency Practice and Experience},
year = 2004,
month = {Feb},
volume = {16(2-3)},
pages = {271-292},
url = {},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh