SUBMESH ALLOCATION IN MESH MULTICOMPUTERS USING BUSY-LIST - A BEST-FIT APPROACH WITH COMPLETE RECOGNITION CAPABILITY

A new approach is proposed for dynamic submesh allocation in mesh-conn ected multicomputer system, which supports a multiuser environment. Th e proposed strategy effectively prunes the search space by searching f or free submeshes on the corners of allocated (busy) submeshes along w ith the four corners of the mesh system. A submesh is selected with th e potential of causing the least amount of fragmentation in the system . The proposed strategy possesses complete submesh recognition capabil ity; it is a best-fit strategy, as well. Existing strategies do not pr ovide this combination of capabilities. The deallocation time and memo ry overhead are shown to be constant in that they do not grow with the size of the mesh. To demonstrate effectiveness, the performance of th e proposed strategy is compared against all existing schemes. Simulati on results indicate that the proposed strategy outperforms existing on es in terms of parameters such as average delay in honoring a request, standard deviation of delay, average allocation time, average dealloc ation time, and amount of memory required. The proposed scheme achieve s a 20 to 30% improvement in the average waiting delay over the best p erforming existing algorithm to date. Our scheme is shown to be applic able to torus-connected multicomputers as well, with only minor modifi cations. The scheme can also be used for submesh allocation with failu res. (C) 1996 Academic Press, Inc.