Proceedings of 9th International Conference on Internet and Distributed Computing Systems (IDCS)

In this paper, we propose and investigate a dynamic heuristicmapping algorithm with lookup table optimizations. Distributed andparallel computing are trends due to the performance requirement ofmodern applications. Application mapping in a multiprocessor systemis therefore critical due to the dynamic and unpredictable nature of theapplications. We analyse the communication delay among different tasksin an application. A fundamental algorithm is analysed to optimize theaverage delay of the mapping region. We discuss and evaluate the effectivenessof the algorithm in terms of average intra-application latency.Results from synthetic applications revealed that average latencies fromthe mapping regions of the fundamental algorithm have reduced up to23% compared with the incremental mapping. By noticing the time overheadof the algorithm due to extra number of search spaces, we introducea mechanism with lookup tables to speed up the process of searching optimizedmapping regions. The lookup table is examined with both sizeand construction time. Experiments shown that the lookup table is smallenough to fit into the cache, and the table can be constructed in millisecondsin most practical cases. The results from real applications show thatthe average execution time of applications of the proposed algorithm hasreduced by 15.2% compared with the first fit algorithm.