Addressing, Routing, And Broadcasting In Hexagonal Mesh Multiprocessors

Abstract

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