Methods for Precise Submesh Allocation

Issue title: Operating system Support for Massively Parallel Computer Architectures

Article type: Research Article

Authors: Morgenstern, Craig

Affiliations: epartment of Computer Science, Texas Christian University, Fort Worth, TX 76129

Abstract: In this article we describe and compare several recently proposed algorithms for precise submesh allocation in a two-dimensional mesh connected system. The methods surveyed include various frame sliding strategies, the maximum boundary value heuristic, and interval set scan techniques. In addition, a new enhancement to the interval set scan method is described. This enhancement results in an algorithm that has better allocation and run-time performance under a FCFS scheduling policy than any of the other proposed methods. We present results drawn from an extensive simulation study to illustrate the relative efficiency of the various methods.

Journal: Scientific Programming, vol. 3, no. 4, pp. 353-364, 1994