Supporting non-contiguous processor allocation in mesh-based chip multiprocessors using virtual point-to-point links

In this study, the authors propose a processor allocation mechanism for run-time assignment of a set of communicating tasks of input applications onto the processing nodes of a chip multiprocessor, when the arrival order and execution lifetime of the input applications are not known a priori. This mechanism targets the on-chip communication and aims to reduce the power and latency of the network-on-chip employed as the communication infrastructure. In this work, the authors benefit from the advantages of non-contiguous processor allocation mechanisms, by allowing the tasks of the input application mapped onto disjoint regions (submeshes) and then virtually connecting them by bypassing the router pipeline stages of the inter-region routers. Among different existing contiguous and non-contiguous processor allocation techniques, the authors have chosen and implemented four efficient schemes for the comparison purpose: the best fit and stack-based allocation algorithms as contiguous techniques and the greedy-available-busy-list algorithm and run-time incremental mapping as non-contiguous techniques. Experimental results show considerable improvements over all selected contiguous and non-contiguous methods.