J.Silc, B.Robic.
Processor allocation based on weighted bipartite matching.
Proc. 2nd Int'l Conf. Parallel Processing and Applied Mathematics,
pp. - , Zakopane, Poland, September 2-5, 1997.
Many processor allocation methods for two-dimensional mesh connected parallel computers have been proposed in the literature. Generally, allocation methods can be divided into two categories, first-fit and best-fit. Assume that a mesh can be dynamically partitioned into several submeshes each of which can be concurrently allocated to one of incoming independent programs and, after completion of that program, reclaimed by the system for future use. A first-fit allocation methods allocates the incoming programs to the first free submesh it detects. A best-fit methods identifies several candidate submeshes, and the program is allocated to the best-fit candidate based on certain heuristic. In this paper, we describe and evaluate a new best-fit processor allocation method called Weighted Bipartite Matching Allocation (WBMA) that, combined with static optimizing mapping, reduces mesh system fragmentation and improves system's throughput.