A fast implementation of the first fit contiguous partitioning strategy for cubic topologies. (12th February 2014)

• Record Type: Journal Article
• Authors: Pascual, Jose A.; Miguel‐Alonso, Jose; Lozano, Jose A.
• Is Part Of: Concurrency and computation. Volume 26:Number 17(2014:Dec.)
• Page Start: 2792
• Page End: 2810
• Publication Date: 2014-02-12
• Subjects: Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.3174
• Languages: English
• ISSNs: 1532-0626

Abstract

<abstract abstract-type="main" id="cpe3174-abs-0001"> <title>SUMMARY</title> <p id="cpe3174-para-0001">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 &amp; Sons, Ltd.</p> </abstract>