Arif Merchant, Kun-Lung Wu, et al.
IEEE Transactions on Knowledge and Data Engineering
A family of 6-regular graphs, called hexagonal meshes or Hmeshes, is considered as a multiprocessor interconnection network. Processing nodes on the periphery of an Hmesh are first wrapped around to achieve regularity and homogeneity. The diameter of a wrapped Hmesh is shown to be of O(p1/2), where p is the number of nodes in the Hmesh. An elegant, distributed routing scheme is developed for wrapped Hmeshes so that each node in an Hmesh can compute shortest paths from itself to any other node with a straightforward algorithm of O(1) using the addresses of the source-destination pair only, i.e., independent of the network's size. This is in sharp contrast with those previously known algorithms that rely on using routing tables. Furthermore, we also develop an efficient point-to-point broadcasting algorithm for the Hmeshes which is proved to be optimal in the number of required communication steps. The wrapped Hmeshes are compared against some other existing multiprocessor interconnection networks, such as hypercubes, trees, and square meshes. The comparison reinforces the attractiveness of the Hmesh architecture. © 1990 IEEE
Arif Merchant, Kun-Lung Wu, et al.
IEEE Transactions on Knowledge and Data Engineering
Ming-Syan Chen, Kun-Lung Wu, et al.
IEEE Transactions on Knowledge and Data Engineering
Mon-Song Chen, Zon-Yin Shae, et al.
GLOBECOM 1992
Ming-Syan Chen, Dilip D. Kandlur, et al.
MM 1994