A fast implementation of the first fit contiguous partitioning strategy for cubic topologies

Abstract

In this paper, an efficient partitioning algorithm is proposed for cube-like topologies. The algorithm carriesout a fast implementation of the First Fit (Improved First Fit, IFF) allocation strategy, making use ofnetwork status information to drastically reduce the cost of finding partitions of the requested shape. Theuse of this information, combined with the detection of zones where requests can not be allocated, remarkablyimproves detection speed in large networks. An exhaustive set of simulation-based experiments have beencarried out to test IFF against another allocation algorithm based on a busy list (RBS). Experiments havebeen done with synthetic and real workloads. Results with synthetic workloads show that, with jobs ofsmall size (relative to the size of the system), IFF outperforms RBS. However, the performance of IFF isstill competitive for workloads with large-size jobs. Results with real workloads show that IFF does betterthan RBS in almost all situations.