The authors introduce and study a family of interconnection schemes, the Midimew networks, based on circulant graphs of degree 4. A family of such circulants is determined and shown to be optimal with respect to two distance parameters simultaneously, namely maximum distance and average distance, among all circulants of degree 4.. These graphs are regular, point-symmetric, and maximally connected, and one such optimal graph exists for any given number of nodes. The proposed interconnection schemes consist of mesh-connected networks with wrap-around links, and are isomorphic to the optimal distance circulants previously considered. Ways to construct one such network for any number of nodes are shown, their good properties to build interconnection schemes for multicomputers are examined, and some interesting particular cases are discussed. The problem of routing is also addressed, and a basic algorithm is provided which is adequate for implementing the routing policy required to convey messages, traversing shortest paths between nodes.>

A class of mesh networks with wrap-around links is obtained from a class of circulant graphs by means of a graph isomorphism. We demonstrate how to obtain, from the adjacency pattern of the graph, simple parameters that serve to construct a planar design of the network. Several performance parameters are evaluated: in particular, we show that diameter and average distance are simultaneously minimized. This implies a minimization of the network communication delays. Due to its easy implementation and good behavior characteristics, the proposed interconnection scheme is appropriate in several architectural environments. Specifically, this topology is suitable as an interconnection subsystem for message passing MIMD architectures, as well as for SIMD machines with a static interconnection scheme. In the particular case of SIMD machines, a comparison is made with the ILLIAC IV-type networks. As a consequence, we propose still another topology, when the number of processing elements is an even power of 2; for this solution, we show that a reduction in the network distances is achieved, without losing speed in performing arbitrary permutations.