LUTMap: A dynamic heuristic application mapping algorithm based on lookup tables - Xu Thomas Canhao; Leppänen Ville (My University, 2022)
In this paper, we propose and investigate a dynamic heuristic
mapping algorithm with lookup table optimizations. Distributed and
parallel computing are trends due to the performance requirement of
modern applications. Application mapping in a multiprocessor system
is therefore critical due to the dynamic and unpredictable nature of the
applications. We analyse the communication delay among different tasks
in an application. A fundamental algorithm is analysed to optimize the
average delay of the mapping region. We discuss and evaluate the effectiveness
of the algorithm in terms of average intra-application latency.
Results from synthetic applications revealed that average latencies from
the mapping regions of the fundamental algorithm have reduced up to
23% compared with the incremental mapping. By noticing the time overhead
of the algorithm due to extra number of search spaces, we introduce
a mechanism with lookup tables to speed up the process of searching optimized
mapping regions. The lookup table is examined with both size
and construction time. Experiments shown that the lookup table is small
enough to fit into the cache, and the table can be constructed in milliseconds
in most practical cases. The results from real applications show that
the average execution time of applications of the proposed algorithm has
reduced by 15.2% compared with the first fit algorithm.
Proceedings of 9th International Conference on Internet and Distributed Computing Systems (IDCS)