Some LCP Decompositions of Multistage Interconnection Networks

Some useful layered cross product decompositons are derived both for general bit permutation networks and for(2n-1)-stage multistage interconnection networks.Several issues in related works are clarified and the rearrangeability of some interesting networks are considered.In particular, the rearrangeability of one class of networks is formulated as a new type of combinatorial design problmes.

A Kind of Multistage Interconnection Networks with Multiple Paths

Multistage Interconnection Networks (MINs) are often used to provide interconnections in multiprocessor systems. A unique path MIN usually has lower hardware complekity and a simple control algorithm, but it lacks fault tolerance.This paper proposes a kind of multipath MINs, which are obtained by adding auxiliary links at the final stage in Quad nee (QT) networks so that they canprovide more paths between each source-destination pair, and presents theirrouting algorithm which is both destination tag based and adaptive. Starting with the routing tag for the minimum path between a given source-destinationpair, the routing algorithm uses a set of rules to select switches and modifyrouting tag. In addition to trying the andliary link when linko and link1 areunavailable, link1 will be tried when link0 is unavailable. This feattire dis-tinguishing the proposed routing algorithm from that for QT networks makesbetter use of all the possible paths between the given source-destination pair.In the end, this paper introduces a performance index, which is called capacity,to compare different kinds of MINs. Comparison shows that the proposed MINshave better capacity than QT networks.

Fast Multicast on Multistage Interconnection Networks Using Multi-Head Worms

This paper proposes a new approach for implementing fast multicast on multistage interconnection networks (MINs) with multi-head worms. For an MIN with n stages of k×k switches, a single multi-head worm can cover an arbitrary set of destinations with a single communication start-up. Compared with schemes using unicast messages, this approach reduces multicast latency significantly and performs better than multi-destination worms.

A General Approach to L(h,k)-Label Interconnection Networks

Given two non-negative integers h and k, an L（h, k）-labeling of a graph G = （V, E） is a function from the set V to a set of colors, such that adjacent nodes take colors at distance at least h, and nodes at distance 2 take colors at distance at least k. The aim of the L（h, k）-labeling problem is to minimize the greatest used color. Since the decisional version of this problem is NP-complete, it is important to investigate particular classes of graphs for which the problem can be efficiently solved. It is well known that the most common interconnection topologies, such as Butterfly-like, Beneg, CCC, Trivalent Cayley networks, are all characterized by a similar structure： they have nodes organized as a matrix and connections are divided into layers. So we naturally introduce a new class of graphs, called （l × n）-multistage graphs, containing the most common interconnection topologies, on which we study the L（h, k）-labeling. A general algorithm for L（h, k）-labeling these graphs is presented, and from this method an efficient L（2, 1）-labeling for Butterfly and CCC networks is derived. Finally we describe a possible generalization of our approach.

Rearrangeability of 7-stage 16 × 16 shuffle exchange networks

It has long been an outstanding conjecture that any(2^(n)×2^(n))-stage shuffle exchange network(Omega net-work)is rearrangeable for 2n 62n.Many researchers have failed to prove this conjecture,including a recent one established by Hasan.However,nobody has pointed out its fallacy.Therefore,as one of the objectives,this paper shall clarify this fact.Since the case of n 53 has been proven by many researchers[1,2],this paper uses a con-structive approach to prove that when n 54,the 7-stage 16616 shuffle exchange network is also rearrangeable.The paper also presents the model of a balanced tree to avoid internal conflict,the representation of permutations using a connection graph and loop graph,and the con-cepts of symmetry graph and identical transform.Based on graphic composition and bipartition,the permutations 16×16 are divided into five classes,with five assignment algorithms proposed.These algorithms are simpler,clearer and easier to program.The techniques used for n=4 may provide hints for the general case of n>4.