Optical transpose k-ary n-cube networks

This paper derives a number of results related to the topological properties of OTIS k-ary n-cube interconnection networks. The basic topological metrics of size, degree, shortest distance, and diameter are obtained. Then results related to embedding in OTIS k-ary n-cubes of OTIS k-ary (n−1)-cubes, cycles, meshes, cubes, and spanning trees are derived. The OTIS k-ary n-cube is shown to be Hamiltonian. Minimal one-to-one routing and optimal broadcasting algorithms are proposed. The OTIS k-ary n-cube is shown to be maximally fault-tolerant. These results are derived based on known properties of k-ary n-cube networks and general properties of OTIS networks.     

Data Rearrangement between Radix-k and Lee Distance Gray Codes in k-ary n-cubes

The k-ary n-cube is one of the popular topologies for interconnecting processors in multicomputers. This paper studies the difference in communication requirements between two Lee distance Gray codes when moving data from processors in normal radix k order to those in Gray code order in k -ary n-cube networks. Algorithms for k-ary to Gray code conversion, and vice versa, in k-ary n-cube networks are described under various channel constraints, i.e., one-port and all-port communication assumptions. The minimum length path routing algorithm for nonreflective Gray code requires roughly M(k/4) and (n−1) M(k/4) steps for data element transfers under all-port communication and one-port communication, respectively, for M elements per node. It is also shown that using a nonminimum length path routing algorithm, the number of steps for data element transfers can be halved. Lower bounds for the number of element transfers are derived, and the proposed algorithm using nonminimum length paths under one-port communication is shown to be near optimal.     

Incomplete k-ary n-cube and its derivatives

Incomplete or pruned k-ary n-cube, n⩾3, is derived as follows. All links of dimension n−1 are left in place and links of the remaining n−1 dimensions are removed, except for one, which is chosen periodically from the remaining dimensions along the intact dimension n−1. This leads to a node degree of 4 instead of the original 2n and results in regular networks that are Cayley graphs, provided that n−1 divides k. For $\text{n=3}\text{(n=5)}$, the preceding restriction is not problematic, as it only requires that k be even (a multiple of 4). In other cases, changes to the basis network to be pruned, or to the pruning algorithm, can mitigate the problem. Incomplete k-ary n-cube maintains a number of desirable topological properties of its unpruned counterpart despite having fewer links. It is maximally connected, has diameter and fault diameter very close to those of k-ary n-cube, and an average internode distance that is only slightly greater. Hence, the cost/performance tradeoffs offered by our pruning scheme can in fact lead to useful, and practically realizable, parallel architectures. We study pruned k-ary n-cubes in general and offer some additional results for the special case n=3.     

Modeling Free-Space Opticalk-aryn-Cube Wormhole Networks

This paper presents an optical interconnect model fork-aryn-cube network topologies based on free-space analysis. This model integrates relevant parameters inherent to optics with traditional network parameters to make it applicable for performance evaluation of parallel processor optical network designs. We apply this model to a free-space diffractive–reflective optical interconnect design and compare our results with electronic-based networks.     

Multi-Radio Multi-Channel无线传感器网络中信道分配和路由策略

针对无线传感器网络中传输时延长、传输冲突大和吞吐量低等问题,提出了一种在Multi-Radio Multi-Channel无线传感器网络中信道分配和路由策略.该策略动态地建立k元n立方体拓扑结构,使用优化的静态信道分配算法提高节点的吞吐量,使用维序寻径的路由算法减少传输冲突.该方法适用于网络节点稠密、节点相互之间通信冲突大的情况,并且在单跳和多跳的网络环境下均适用.实验结果表明,基于k元n立方体这一拓扑结构的信道分配和路由策略与传统方法相比,有效地减少了端到端时延,降低了网络冲突,减少了节点能量消耗,延长了网络寿命,提高了网络吞吐量.     

Hamiltonian paths and cycles with prescribed edges in the 3-ary n-cube

The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. Given a set P of at most 2n − 2 (n ? 2) prescribed edges and two vertices u and v, we show that the 3-ary n-cube contains a Hamiltonian path between u and v passing through all edges of P if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as end-vertices. As an immediate result, the 3-ary n-cube contains a Hamiltonian cycle passing through a set P of at most 2n − 1 prescribed edges if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths.     

Strongly Hamiltonian laceability of the even k-ary n-cube

The interconnection network considered in this paper is the k-ary n-cube that is an attractive variance of the well-known hypercube. Many interconnection networks can be viewed as the subclasses of the k-ary n-cubes include the cycle, the torus and the hypercube. A bipartite graph is Hamiltonian laceable if there exists a Hamiltonian path joining every two vertices which are in distinct partite sets. A bipartite graph G is strongly Hamiltonian laceable if it is Hamiltonian laceable and there exists a path of length N − 2 joining each pair of vertices in the same partite set, where N = |V(G)|. We prove that the k-ary n-cube is strongly Hamiltonian laceable for k is even and n  2.     

Efficient implementation of globally-aware network flow control

Network flow control mechanisms that are aware of global conditions potentially can achieve higher performance than flow control mechanisms that are only locally aware. Owing to high implementation overhead, globally-aware flow control mechanisms in their purest form are seldom adopted in practice, leading to less efficient simplified implementations. In this paper, we propose an efficient implementation of a globally-aware flow control mechanism, called Critical Bubble Scheme, for k-ary n-cube networks. This scheme achieves near-optimal performance with the same minimal buffer requirements of globally-aware flow control and can be further generalized to implement the general class of buffer occupancy-based network flow control. We prove deadlock freedom of the proposed scheme and exploit its use in handling protocol-induced deadlocks in on-chip environments. We evaluate the proposed scheme using both synthetic traffic and real application loads. Simulation results show that the proposed scheme can reduce the buffer access component of packet latency by as much as 62% over locally-aware flow control, and improve average packet latency by 18.8% and overall execution time by 7.2% in full system simulation.     

Augmented k-ary n-cubes

We define an interconnection network AQ_n,k which we call the augmented k-ary n-cube by extending a k-ary n-cube in a manner analogous to the existing extension of an n-dimensional hypercube to an n-dimensional augmented cube. We prove that the augmented k-ary n-cube AQ_n,k has a number of attractive properties (in the context of parallel computing). For example, we show that the augmented k-ary n-cube AQ_n,k: is a Cayley graph, and so is vertex-symmetric, but not edge-symmetric unless n = 2; has connectivity 4n − 2 and wide-diameter at most max{(n − 1)k − (n − 2), k + 7}; has diameter , when n = 2; and has diameter at most , for n ? 3 and k even, and at most , for n ? 3 and k odd.     

The diagnosability of the k-ary n-cubes using the pessimistic strategy

The pessimistic strategy, also called the t ₁/t ₁-diagnosis strategy, allows to contain all faulty vertices and at most one fault-free vertex. However, the degree of the diagnosability of a system increases quickly using the pessimistic strategy. In this paper, we consider the k-ary n-cube, which is an important hypercube variant, and show that the 3-ary n-cube and k-ary n-cube with k≥4 are (4n?3)/(4n?3)-diagnosable and (4n?2)/(4n?2)-diagnosable, respectively. Finally, we obtain the degree of the diagnosability of the tori using the pessimistic strategy.     

Edge-bipancyclicity of the k-ary n-cubes with faulty nodes and edges

The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. In this paper, we investigate the edge-bipancyclicity of k-ary n-cubes with faulty nodes and edges. It is proved that every healthy edge of the faulty k-ary n-cube with f_v faulty nodes and f_e faulty edges lies in a fault-free cycle of every even length from 4 to kⁿ − 2f_v (resp. kⁿ − f_v) if k ? 4 is even (resp. k ? 3 is odd) and f_v + f_e ? 2n − 3. The results are optimal with respect to the number of node and edge faults tolerated.     

Parallel Lagrange interpolation on <Emphasis Type="Italic">k</Emphasis>-ary <Emphasis Type="Italic">n</Emphasis>-cubes with maximum channel utilization

This paper proposes an efficient parallel algorithm for computing Lagrange interpolation on k-ary n-cube networks. This is done using the fact that a k-ary n-cube can be decomposed into n link-disjoint Hamiltonian cycles. Using these n link-disjoint cycles, we interpolate Lagrange polynomial using full bandwidth of the employed network. Communication in the main phase of the algorithm is based on an all-to-all broadcast algorithm on the n link-disjoint Hamiltonian cycles exploiting all network channels, and thus, resulting in high-efficiency in using network resources. A performance evaluation of the proposed algorithm reveals an optimum speedup for a typical range of system parameters used in current state-of-the-art implementations.

Path embeddings in faulty 3-ary n-cubes

The class of k-ary n-cubes represents the most commonly used interconnection topology for distributed-memory parallel systems. In this paper, we study the problem of embedding paths of various lengths into faulty 3-ary n-cubes and prove that a faulty 3-ary n-cube with f?2n-3 faulty vertices admits a path of every length from 2n-1 to 3ⁿ-f-1 connecting any two distinct healthy vertices. This result is optimal with respect to the number of vertex faults tolerated.     

A Generic Design Methodology for Deadlock-Free Routing in Multicomputer Networks

This paper introduces a generic methodology for defining deadlock-free wormhole routing schemes in any arbitrary network. The basic strategy is to partition a graph into subdigraphs with no cyclic dependencies and selectively assign virtual channels. The usefulness of our scheme is shown for the n-dimensional hypercube, the n-dimensional mesh, and the k-ary n-cube torus by identifying subdigraph characteristics that ensure acyclic routing. Further generalization which allows partial cyclic dependencies without deadlock is achieved by our extended generic methodology. We also illustrate how to identify shortest fixed path and nonminimal adaptive routing schemes using minimum required channels.     

Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes

In this paper, we investigate the fault-tolerant capabilities of the k-ary n-cubes for even integer k with respect to the hamiltonian and hamiltonian-connected properties. The k-ary n-cube is a bipartite graph if and only if k is an even integer. Let F   be a faulty set with nodes and/or links, and let k?3$k?3$ be an odd integer. When |F|?2n-2$\left|F\right|?2n-2$, we show that there exists a hamiltonian cycle in a wounded k-ary n  -cube. In addition, when |F|?2n-3$\left|F\right|?2n-3$, we prove that, for two arbitrary nodes, there exists a hamiltonian path connecting these two nodes in a wounded k-ary n-cube. Since the k-ary n  -cube is regular of degree 2n$2n$, the degrees of fault-tolerance 2n-3$2n-3$ and 2n-2$2n-2$ respectively, are optimal in the worst case.     

The Generalized Dimension Exchange Method for Load Balancing in k-ary n-Cubes and Variants

The generalized dimension exchange (GDE) method is a fully distributed load balancing method that operates in a relaxation fashion for multicomputers with a direct communication network. It is parameterized by an exchange parameter λ that governs the splitting of load between a pair of directly connected processors during load balancing. An optimal λ would lead to the fastest convergence of the balancing process. Previous work has resulted in the optimal λ for the binary n-cubes. In this paper, we derive the optimal lambda′s for the k-ary n-cube network and its variants-the ring, the torus, the chain, and the mesh. We establish the relationships between the optimal convergence rates of the method when applied to these structures, and conclude that the GDE method favors high-dimensional k-ary n-cubes. We also reveal the superiority of the GDE method to another relaxation-based method, the diffusion method. We further show through statistical stimulations that the optimal lambda′s do speed up the GDE balancing procedure significantly. Because of its simplicity, the method is readily implementable. We report on the implementation of the method in two data-parallel computations in which the improvement in performance due to GDE balancing is substantial.     

Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links

The k-ary n-cube, denoted by , is one of the most important interconnection networks for parallel computing. In this paper, we consider the problem of embedding cycles and paths into faulty 3-ary n-cubes. Let F be a set of faulty nodes and/or edges, and n?2. We show that when |F|?2n-2, there exists a cycle of any length from 3 to in . We also prove that when |F|?2n-3, there exists a path of any length from 2n-1 to between two arbitrary nodes in . Since the k-ary n-cube is regular of degree 2n, the fault-tolerant degrees 2n-2 and 2n-3 are optimal.     

Fast and efficient processor allocation algorithm for torus-based chip multiprocessors

Processor Allocator (PA) is a crucial factor in modern Chip MultiProcessors (CMPs). A modern CMP uses Network on Chip (NoC) as communication technique between cores. Thus, the topology of the implemented NoC has also significant impact on the CMP’s performance. A good processor allocation technique needs to be fast and ensure the highest possible system utilization. In this paper, we propose a processor allocation technique for such an efficient and fast PA. The PA is driven by a Bit Map Allocation for Torus (BMAT) algorithm, which is a technique designed for k-ary 2-cube topology. The proposed BMAT scheme is presented and described along with a new Busy List Allocation for Torus (BLAT), Sorting Allocation for Torus (SAT) and Stack Based Allocation for Torus (SBAT) algorithms. The presented techniques are compared with previously known important schemes for k-ary 2-mesh topology. The research ideas have been verified using experiments that have also been described in the paper. The presented simulation results reveal that the proposed processor allocation algorithm for k-ary 2-cube, as a technique for PA, achieves better allocation time than all other existing algorithms while the CMP with such a PA is characterized by very high system utilization.     

A novel path protection scheme for MPLS networks using multi-path routing

Multi-protocol label switching (MPLS) is an evolving network technology that is used to provide traffic engineering (TE) and high speed networking. Internet service providers, which support MPLS technology, are increasingly demanded to provide high quality of service (QoS) guarantees. One of the aspects of QoS is fault tolerance. It is defined as the property of a system to continue operating in the event of failure of some of its parts. Fault tolerance techniques are very useful to maintain the survivability of the network by recovering from failure within acceptable delay and minimum packet loss while efficiently utilizing network resources.In this paper, we propose a novel approach for fault tolerance in MPLS networks. Our approach uses a modified (k, n) threshold sharing scheme with multi-path routing. An IP packet entering MPLS network is partitioned into n MPLS packets, which are assigned to node/link disjoint LSPs across the MPLS network. Receiving MPLS packets from k out of n LSPs are sufficient to reconstruct the original IP packet. The approach introduces no packet loss and no recovery delay while requiring reasonable redundant bandwidth. In addition, it can easily handle single and multiple path failures.     

Pancyclicity of ternary n-cube networks under the conditional fault model

A graph G is said to be conditional k-edge-fault pancyclic if after removing k faulty edges from G, under the assumption that each vertex is incident to at least two fault-free edges, the resulting graph contains a cycle of every length from its girth to |V(G)|. In this paper, we consider ternary n-cube networks and show that they are conditional (4n−5)-edge-fault pancyclic.