Definition and analysis of a class of spanning bus orthogonal multiprocessing systems
Isaac D. Scherson · 1990
A graph theoretical representation for a class of interconnection networks is suggested. The idea is based on a definition of orthogonal binary vectors and leads to a construction rule for a class of orthogonal graphs. An orthogonal graph is first defined as a set of 2m nodes, which in turn are linked by 2m-n edges for every link mode defined in an integer set Q*. The degree and diameter of an orthogonal graph are determined in terms of the parameters n, m and the number of link modes defined in Q*. Routing in orthogonal graphs is shown to reduce to the node covering problem in bipartite graphs. The proposed theory is applied to describe a number of well known interconnection networks such as the binary m-cube and spanning-bus meshes. Multi-dimensional access (MDA) memories are shown as examples of orthogonal shared memory multi-processing systems.