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 rearr...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.展开更多
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 fau...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.展开更多
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...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.展开更多
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 distanc...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.展开更多
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 ...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.展开更多
文摘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.
文摘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.
文摘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.
基金Sapienza University of Rome(project"Parallel and Distributed Codes")
文摘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.
基金supported by the National Science Foundation of USA(Grant No.9810692)University of Missouri-Kansas City Faculty Research Grant(UMKC FRG)(No.K-2-11678).
文摘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.