A LINK-DISJOINT SUBMESH FOR PROCESSOR ALLOCATION IN MESH COMPUTERS

A processor allocation scheme for mesh computers greatly affects their system utilization. The performance of an allocation scheme is largel y dependent on its ability to detect available submeshes. We propose a new type of submesh, called a link-disjoint submesh, for processor al location in mesh computers. This type of submesh increases the submesh recognition capability of an allocation scheme. A link-disjoint subme sh is not a contiguous submesh as in the previous scheme, but this sub mesh still has no common communication link with any other submesh. Wh en wormhole routing or circuit switching is used, the communication de lay caused by non-contiguous processor allocation is minor. Through si mulation, the performance of our scheme is measured and compared to th e previous schemes in terms of such parameters as finish time and syst em utilization. It is shown through simulation that the link-disjoint submesh increases the performance of an allocation scheme.