Abstract
The submesh allocation problem is to recognize and locate a free space large enough to accommodate the required size of an incoming task. In the last decade, a number of submesh allocation strategies have been proposed. However, even the latest work suffers a large amount of waiting delay for each task. The main reason is, under FCFS (first-come-first-served) scheduling policy, the allocation failure of one task may block subsequent requests that can be serviceable.In this thesis, efficient algorithms are proposed to perform task reallocation on mesh-connected multicomputers. For an incoming allocation request, existing allocation strategies are applied. If these strategies fail to allocate a proper submesh for this task, we will try to choose and reallocate some resident submeshes to form a submesh larger than the required one. Such operation is called migration. A complete migration process can be divided into two phases: to choose candidates and to perform reallocation. Four and two strategies are proposed respectively, for these two phases in this thesis.Simulation results show that our migration methods can improve the system throughput by 25 to 40 percent under normal load. When system load is heavy, the benefit is even greater. Compared to the improvement, the cost of performing migration is relatively slight. Our results strongly suggest system administrators to apply migration to the submesh allocation problem.