A link-disjoint submesh for processor allocation in mesh computers

Abstract

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