Efficient allocation of processors to incoming tasks in parallel computer systems is important to high performance. The authors present an efficient task allocation scheme for 2D architectures. By effectively manipulating the allocation status of each row of the mesh, the scheme can quickly determine whether a row can be part of the free submesh that can be allocated to the incoming task. The scheme can thus find the free submesh, if it exists, without scanning the entire 2D array, unlike earlier approaches. The proposed scheme is effective not only for a typical 2D mesh but also for more complex mesh architectures, such as 2D tori.

The paper is organized into five sections, the first of which is an introduction. In the second section, the authors provide definitions and an explanation of notation that is used throughout the paper. They also provide brief descriptions of five existing task allocation schemes (two-dimensional buddy, frame sliding, first fit and best fit, adaptive scan, and Sharma and Pradhan). Section 3 is dedicated to the proposed task allocation and deallocation scheme. In Section 4, the scheme is evaluated in terms of time complexity and is compared with existing schemes. An evaluation of the performances by computer simulation reveals that the average allocation time and waiting delay of the new scheme are up to several times smaller, regardless of the size of the meshes and the distribution of the shapes of the incoming tasks. In the last section, the authors present their conclusions about the proposed scheme.

The paper includes two appendices: a proof of a lemma defined in Section 3 and a description of a task allocation scheme for 2D tori. With its clearly presented information and good references, the paper is a valuable resource for people interested in developing parallel computer systems.