A fast implementation of the first fit contiguous partitioning strategy for cubic topologies
Jose Antonio Pascual, José Miguel-Alonso, Jose Antonio Lozano · Concurrency and Computation Practice and Experience · 2014
SUMMARY In this paper, we propose and evaluate improved first fit (IFF), a fast implementation of the first fit contiguous partitioning strategy. It has been devised to accelerate the process of finding contiguous partitions in space‐shared parallel computers in which the nodes are arranged forming multidimensional cubic networks. IFF uses system status information to drastically reduce the cost of finding partitions with the requested shape. The use of this information, i combined with the early detection of zones where requests cannot be allocated, remarkably improves the search speed in large networks. An exhaustive set of simulation‐based experiments have been carried out to test IFF against other algorithms implementing the same partitioning strategy. Results, using synthetic and real workloads, show that IFF can be several orders of magnitude faster than competitor algorithms. Copyright © 2013 John Wiley & Sons, Ltd.