Premium
A fast implementation of the first fit contiguous partitioning strategy for cubic topologies
Author(s) -
Pascual Jose A.,
MiguelAlonso Jose,
Lozano Jose A.
Publication year - 2014
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.3174
Subject(s) - computer science , set (abstract data type) , process (computing) , network topology , algorithm , parallel computing , computer network , programming language , operating system
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.