Download
Abstract:
We examine fast algorithms to allocate processors to compute jobs in mesh-connected clusters. We find that a 1D curve-based strategy can give allocations of comparable quality to a fully 3D algorithm MC1x1 using a snake curve that goes along the mesh's short dimensions first. We also propose several buddy-system strategies, the best of which actually finds better allocations than MC1x1 if the job sizes and mesh dimensions are powers of 2. Furthermore, these algorithms are much faster than MC1x1, which takes more than 200 times as long in some cases.