LUTMap: A dynamic heuristic application mapping algorithm based on lookup tables

Abstract

<p>In this paper, we propose and investigate a dynamic heuristic<br />mapping algorithm with lookup table optimizations. Distributed and<br />parallel computing are trends due to the performance requirement of<br />modern applications. Application mapping in a multiprocessor system<br />is therefore critical due to the dynamic and unpredictable nature of the<br />applications. We analyse the communication delay among different tasks<br />in an application. A fundamental algorithm is analysed to optimize the<br />average delay of the mapping region. We discuss and evaluate the effectiveness<br />of the algorithm in terms of average intra-application latency.<br />Results from synthetic applications revealed that average latencies from<br />the mapping regions of the fundamental algorithm have reduced up to<br />23% compared with the incremental mapping. By noticing the time overhead<br />of the algorithm due to extra number of search spaces, we introduce<br />a mechanism with lookup tables to speed up the process of searching optimized<br />mapping regions. The lookup table is examined with both size<br />and construction time. Experiments shown that the lookup table is small<br />enough to fit into the cache, and the table can be constructed in milliseconds<br />in most practical cases. The results from real applications show that<br />the average execution time of applications of the proposed algorithm has<br />reduced by 15.2% compared with the first fit algorithm.<br /></p>