Towards understanding optimal MIMD queueless routing of arbitrary permutations on hypercubes

Jung, Jean-Pierre; Sakho, Ibrahima
September 2012
Journal of Supercomputing;
This paper addresses the problem of the offline routing of arbitrary permutations on hypercubes under the MIMD queueless communication constraints which imposes that only one message can be located in each node of the hypercube right through the routing. According to e-cube routing, this kind of communication may require in the worst cases at least n exchanges steps on an n-dimensional hypercube. It has been conjectured that in the general case n steps suffice. The conjecture has been proved either by enumeration or by program for the particular cases of n≤3. We revisit the problem through the k-partitioning paradigm based on maximum matching of bipartite graphs concept to take advantage of the recursive structure of the hypercube topology. The paradigm consists in looking for each message a transition node distant of at most say k< n hops from its current node such that all the messages can be routed to their transition nodes in k hops then finally routed to their final destination nodes in n− k hops on two disjoints hypercubes. In others words, the paradigm consists to determine an upstream permutation routable in k steps and which leads to two independent downstream permutations routable in n− k steps on two disjoint hypercubes. With this purpose, we give a characterization of the non-1-partitionable permutations from which the proof of the conjecture comes straightforwardly for n≤2 and the non-1-partitionable permutations can be built whatever n may be. For n=3, we thus confirm the existence of exactly three classes of non-1-partitionable permutations and prove that there are two classes of upstream permutations to avoid when 2-partitioning any non-1-partitionable permutation. The process to avoid such upstream permutations is presented, and leads to a formal proof of the conjecture for n=3. For n>3, experiences gained in routing permutations on 4 D-hypercubes allow conjecturing that in these cases, too, any non-1-partitionable permutation is 2-partitionable. Indeed, the analysis carried out for the 3 D-hypercubes is repeatable to identify, certainly more laboriously given their combinatory, the upstream permutations to avoid when 2-partitioning a non-1-partitionable permutation on a 4 D-hypercube. The proof that resulting downstream permutations on a 3 D-hypercube can be routed in 2 steps is a consequence of the fact that for n=2 and 3 any permutation on a nD-hypercube can be routed in n steps.


Related Articles

  • Set-to-Set Disjoint Paths Routing in Hierarchical Cubic Networks. Bossard, Antoine; Kaneko, Keiichi // Computer Journal;Feb2014, Vol. 57 Issue 2, p332 

    Due to its simplicity, the hypercube topology is popular as interconnection network of parallel systems. However, due to physical restrictions of the number of links per node, this topology is no more satisfactory in the context of modern supercomputing. Effectively, today massively parallel...

  • Balancing virtual channel utilization for deadlock-free routing in torus networks. Yu, Zhigang; Xiang, Dong; Wang, Xinyu // Journal of Supercomputing;Aug2015, Vol. 71 Issue 8, p3094 

    Torus networks have been widely used by modern commercial supercomputers due to low node degree and linear scalability cost. Meanwhile, the ring in each dimension of a torus creates cyclic channel dependencies, which pose challenges to the design of deadlock-free routing and virtual channel...

  • Tight Bounds on the Diameter of Gaussian Cubes. Kwai, D.-M.; Parhami, B. // Computer Journal;1998, Vol. 41 Issue 1, p52 

    Gaussian cubes are derived by removing links from a hypercube in a periodic fashion. By varying the partition parameter, one can obtain networks with different characteristics, while maintaining a basic framework for computation and communication. Unfortunately, such networks are in general not...

  • An Analytical Model for Hypercube Network-On-Chip Systems with Wormhole Switching and Fully Adaptive Routing. Jin Liu; Xiaofeng Wang; Hongmin Ren; Jin Wang; Jeong-Uk Kim // International Journal of Grid & Distributed Computing;Dec2012, Vol. 5 Issue 4, p33 

    In this paper, we present a novel performance analysis model for predicting average message latency of hypercube network-on-chip (NoC) systems that employ wormhole switching and fully adaptive routing method with uniformly distributed traffic. Unlike previous works, our model calculates the...

  • Wormhole Routing.  // Network Dictionary;2007, p533 

    A definition of the term "wormhole routing" is presented. It refers to the system of simple routing in computer networking based on known fixed links. According to the article, wormhole routing is used primarily in multiprocessor systems such as hypercubes. It is noted that each central...

  • Connected Dominating Set of Hypercubes and Star Graphs. Y-Chuang Chen; Ya-Ling Syu // International Proceedings of Computer Science & Information Tech;2012, Vol. 41, p15 

    In wired or wireless networks, routing efficiently among immobile or mobile devices is an important issue. A connected dominating set (CDS) brings benefits to network routing. The CDS can be served as a virtual backbone of a network, and it always adapted easily to new network topology. A...

  • Grouping Technique for Re-Routing a Rearrangeable MIN. Salehnamadi, M. Reza // Journal of Applied Sciences;2008, Vol. 8 Issue 14, p2577 

    A new method for routing in a rearrangeable three-stage CLOS MIN is presented. The contribution of study is grouping all inputs according to a proper specification of MIN and then executing the selected algorithm within each group. The grouping title is selected because the process has two...

  • Has the tide turned for patch cords? McLAUGHLIN, PATRICK // Cabling Installation & Maintenance;Dec2015, Vol. 23 Issue 12, p3 

    An editorial is presented, in which the editor discusses development and availability of PerfectPatch, a device that shortens patch cord.

  • The Set-to-Set Disjoint-Path Problem in Perfect Hierarchical Hypercubes. Bossard, Antoine; Kaneko, Keiichi // Computer Journal;Jun2012, Vol. 55 Issue 6, p769 

    The perfect hierarchical hypercube (HHC) interconnection network has been introduced in the literature recently. An HHC can connect many nodes while retaining a low degree and a small diameter. It is thus a suitable topology for interconnection networks of massively parallel systems. We describe...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics