The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] hypercube(38hit)

1-20hit(38hit)

  • Node-to-Node and Node-to-Set Disjoint Paths Problems in Bicubes Open Access

    Arata KANEKO  Htoo Htoo Sandi KYAW  Kunihiro FUJIYOSHI  Keiichi KANEKO  

     
    PAPER-Fundamentals of Information Systems

      Pubricized:
    2024/05/17
      Vol:
    E107-D No:9
      Page(s):
    1133-1139

    In this paper, we propose two algorithms, B-N2N and B-N2S, that solve the node-to-node and node-to-set disjoint paths problems in the bicube, respectively. We prove their correctness and that the time complexities of the B-N2N and B-N2S algorithms are O(n2) and O(n2 log n), respectively, if they are applied in an n-dimensional bicube with n ≥ 5. Also, we prove that the maximum lengths of the paths generated by B-N2N and B-N2S are both n + 2. Furthermore, we have shown that the algorithms can be applied in the locally twisted cube, too, with the same performance.

  • Node-to-Set Disjoint Paths Problem in Cross-Cubes

    Rikuya SASAKI  Hiroyuki ICHIDA  Htoo Htoo Sandi KYAW  Keiichi KANEKO  

     
    PAPER-Fundamentals of Information Systems

      Pubricized:
    2023/10/06
      Vol:
    E107-D No:1
      Page(s):
    53-59

    The increasing demand for high-performance computing in recent years has led to active research on massively parallel systems. The interconnection network in a massively parallel system interconnects hundreds of thousands of processing elements so that they can process large tasks while communicating among others. By regarding the processing elements as nodes and the links between processing elements as edges, respectively, we can discuss various problems of interconnection networks in the framework of the graph theory. Many topologies have been proposed for interconnection networks of massively parallel systems. The hypercube is a very popular topology and it has many variants. The cross-cube is such a topology, which can be obtained by adding one extra edge to each node of the hypercube. The cross-cube reduces the diameter of the hypercube, and allows cycles of odd lengths. Therefore, we focus on the cross-cube and propose an algorithm that constructs disjoint paths from a node to a set of nodes. We give a proof of correctness of the algorithm. Also, we show that the time complexity and the maximum path length of the algorithm are O(n3 log n) and 2n - 3, respectively. Moreover, we estimate that the average execution time of the algorithm is O(n2) based on a computer experiment.

  • Minimal Paths in a Bicube

    Masaaki OKADA  Keiichi KANEKO  

     
    PAPER-Fundamentals of Information Systems

      Pubricized:
    2022/04/22
      Vol:
    E105-D No:8
      Page(s):
    1383-1392

    Nowadays, a rapid increase of demand on high-performance computation causes the enthusiastic research activities regarding massively parallel systems. An interconnection network in a massively parallel system interconnects a huge number of processing elements so that they can cooperate to process tasks by communicating among others. By regarding a processing element and a link between a pair of processing elements as a node and an edge, respectively, many problems with respect to communication and/or routing in an interconnection network are reducible to the problems in the graph theory. For interconnection networks of the massively parallel systems, many topologies have been proposed so far. The hypercube is a very popular topology and it has many variants. The bicube is a such topology and it can interconnect the same number of nodes with the same degree as the hypercube while its diameter is almost half of that of the hypercube. In addition, the bicube keeps the node-symmetric property. Hence, we focus on the bicube and propose an algorithm that gives a minimal or shortest path between an arbitrary pair of nodes. We give a proof of correctness of the algorithm and demonstrate its execution.

  • Node-Disjoint Paths Problems in Directed Bijective Connection Graphs

    Keiichi KANEKO  

     
    PAPER-Fundamentals of Information Systems

      Pubricized:
    2019/09/26
      Vol:
    E103-D No:1
      Page(s):
    93-100

    In this paper, we extend the notion of bijective connection graphs to introduce directed bijective connection graphs. We propose algorithms that solve the node-to-set node-disjoint paths problem and the node-to-node node-disjoint paths problem in a directed bijective connection graph. The time complexities of the algorithms are both O(n4), and the maximum path lengths are both 2n-1.

  • Constructing Two Completely Independent Spanning Trees in Balanced Hypercubes

    Yi-Xian YANG  Kung-Jui PAI  Ruay-Shiung CHANG  Jou-Ming CHANG  

     
    LETTER-Fundamentals of Information Systems

      Pubricized:
    2019/06/17
      Vol:
    E102-D No:12
      Page(s):
    2409-2412

    A set of spanning trees of a graphs G are called completely independent spanning trees (CISTs for short) if for every pair of vertices x, y∈V(G), the paths joining x and y in any two trees have neither vertex nor edge in common, except x and y. Constructing CISTs has applications on interconnection networks such as fault-tolerant routing and secure message transmission. In this paper, we investigate the problem of constructing two CISTs in the balanced hypercube BHn, which is a hypercube-variant network and is superior to hypercube due to having a smaller diameter. As a result, the diameter of CISTs we constructed equals to 9 for BH2 and 6n-2 for BHn when n≥3.

  • Implementing Exchanged Hypercube Communication Patterns on Ring-Connected WDM Optical Networks

    Yu-Liang LIU  Ruey-Chyi WU  

     
    PAPER-Interconnection networks

      Pubricized:
    2017/08/04
      Vol:
    E100-D No:12
      Page(s):
    2771-2780

    The exchanged hypercube, denoted by EH(s,t), is a graph obtained by systematically removing edges from the corresponding hypercube, while preserving many of the hypercube's attractive properties. Moreover, ring-connected topology is one of the most promising topologies in Wavelength Division Multiplexing (WDM) optical networks. Let Rn denote a ring-connected topology. In this paper, we address the routing and wavelength assignment problem for implementing the EH(s,t) communication pattern on Rn, where n=s+t+1. We design an embedding scheme. Based on the embedding scheme, a near-optimal wavelength assignment algorithm using 2s+t-2+⌊2t/3⌋ wavelengths is proposed. We also show that the wavelength assignment algorithm uses no more than an additional 25 percent of (or ⌊2t-1/3⌋) wavelengths, compared to the optimal wavelength assignment algorithm.

  • Stochastic Fault-Tolerant Routing in Dual-Cubes

    Junsuk PARK  Nobuhiro SEKI  Keiichi KANEKO  

     
    LETTER-Dependable Computing

      Pubricized:
    2017/05/10
      Vol:
    E100-D No:8
      Page(s):
    1920-1921

    In the topologies for interconnected nodes, it is desirable to have a low degree and a small diameter. For the same number of nodes, a dual-cube topology has almost half the degree compared to a hypercube while increasing the diameter by just one. Hence, it is a promising topology for interconnection networks of massively parallel systems. We propose here a stochastic fault-tolerant routing algorithm to find a non-faulty path from a source node to a destination node in a dual-cube.

  • Node-to-Node Disjoint Paths Problem in Möbius Cubes

    David KOCIK  Keiichi KANEKO  

     
    PAPER-Dependable Computing

      Pubricized:
    2017/04/25
      Vol:
    E100-D No:8
      Page(s):
    1837-1843

    The Möbius cube is a variant of the hypercube. Its advantage is that it can connect the same number of nodes as a hypercube but with almost half the diameter of the hypercube. We propose an algorithm to solve the node-to-node disjoint paths problem in n-Möbius cubes in polynomial-order time of n. We provide a proof of correctness of the algorithm and estimate that the time complexity is O(n2) and the maximum path length is 3n-5.

  • Node-to-Set Disjoint Paths Problem in a Möbius Cube

    David KOCIK  Yuki HIRAI  Keiichi KANEKO  

     
    PAPER-Dependable Computing

      Pubricized:
    2015/12/14
      Vol:
    E99-D No:3
      Page(s):
    708-713

    This paper proposes an algorithm that solves the node-to-set disjoint paths problem in an n-Möbius cube in polynomial-order time of n. It also gives a proof of correctness of the algorithm as well as estimating the time complexity, O(n4), and the maximum path length, 2n-1. A computer experiment is conducted for n=1,2,...,31 to measure the average performance of the algorithm. The results show that the average time complexity is gradually approaching to O(n3) and that the maximum path lengths cannot be attained easily over the range of n in the experiment.

  • Secure Sets and Defensive Alliances in Graphs: A Faster Algorithm and Improved Bounds

    Kazuyuki AMANO  Kyaw May OO  Yota OTACHI  Ryuhei UEHARA  

     
    PAPER

      Vol:
    E98-D No:3
      Page(s):
    486-489

    Secure sets and defensive alliances in graphs are studied. They are sets of vertices that are safe in some senses. In this paper, we first present a fixed-parameter algorithm for finding a small secure set, whose running time is much faster than the previously known one. We then present improved bound on the smallest sizes of defensive alliances and secure sets for hypercubes. These results settle some open problems paused recently.

  • Longest Fault-Free Cycles in Folded Hypercubes with Conditional Faulty Elements

    Wen-Yin HUANG  Jia-Jie LIU  Jou-Ming CHANG  Ro-Yu WU  

     
    PAPER

      Vol:
    E97-A No:6
      Page(s):
    1187-1191

    An n-dimensional folded hypercube, denoted by FQn, is an enhanced n-dimensional hypercube with one extra link between nodes that have the furthest Hamming distance. Let FFv (respectively, FFe) denote the set of faulty nodes (respectively, faulty links) in FQn. Under the assumption that every fault-free node in FQn is incident to at least two fault-free links, Hsieh et al. (Inform. Process. Lett. 110 (2009) pp.41-53) showed that if |FFv|+|FFe| ≤ 2n-4 for n ≥ 3, then FQn-FFv-FFe contains a fault-free cycle of length at least 2n-2|FFv|. In this paper, we show that, under the same conditional fault model, FQn with n ≥ 5 can tolerate more faulty elements and provides the same lower bound of the length of a longest fault-free cycle, i.e., FQn-FFv-FFe contains a fault-free cycle of length at least 2n-2|FFv| if |FFv|+|FFe| ≤ 2n-3 for n ≥ 5.

  • Multi-Layer Hypercube Photonic Network Architecture for Intra-Datacenter Network

    Toshikazu SAKANO  Akihiro KADOHATA  Yoshiaki SONE  Atsushi WATANABE  Masahiko JINNO  

     
    PAPER

      Vol:
    E94-B No:4
      Page(s):
    910-917

    The popularity of cloud computing services is driving the boom in building mega-datacenters. This trend is forcing significant increases in the required scale of the intra-datacenter network. To meet this requirement, this paper proposes a photonic network architecture based on a multi-layer hypercube topology. The proposed architecture uses the Cyclic-Frequency Arrayed Waveguide Grating (CF-AWG) device to realize a multi-layer hypercube and properly combines several multiplexing systems that include Time Division Multiplexing (TDM), Wavelength Division Multiplexing (WDM), Wave-Band Division Multiplexing (WBDM) and Space Division Multiplexing (SDM). An estimation of the achievable network scale reveals that the proposed architecture can achieve a Peta-bit to Exa-bit class, large scale hypercube network with existing technologies.

  • Cayley Graph Representation and Graph Product Representation of Hypercubes

    Miya MOROTA  Ryoichi HATAYAMA  Yukio SHIBATA  

     
    PAPER-Graphs and Networks

      Vol:
    E94-A No:3
      Page(s):
    946-954

    Hypercube Qn is a well-known graph structure having three different kinds of equivalent definitions that are: 1. binary n bit sequences with the adjacency condition, 2. Q1=K2, Qn=Qn-1 K2, where means the Cartesian product, 3. the Cayley graph on Z2n with the generator set {100, 0100, , 001}. We give a necessary and sufficient condition for a set of binary sequences to be a generator set for the hypercube. Then, we give relations between some generator sets and relational products. These results show the wide variety of representability of hypercubes which would be used for many applications.

  • An N-Dimensional Pseudo-Hilbert Scan for Arbitrarily-Sized Hypercuboids

    Jian ZHANG  Sei-ichiro KAMATA  

     
    PAPER-Image

      Vol:
    E91-A No:3
      Page(s):
    846-858

    The N-dimensional (N-D) Hilbert curve is a one-to-one mapping between N-D space and one-dimensional (1-D) space. It is studied actively in the area of digital image processing as a scan technique (Hilbert scan) because of its property of preserving the spatial relationship of the N-D patterns. Currently there exist several Hilbert scan algorithms. However, these algorithms have two strict restrictions in implementation. First, recursive functions are used to generate a Hilbert curve, which makes the algorithms complex and computationally expensive. Second, all the sides of the scanned region must have the same size and the length must be a power of two, which limits the application of the Hilbert scan greatly. Thus in order to remove these constraints and improve the Hilbert scan for general application, a nonrecursive N-D Pseudo-Hilbert scan algorithm based on two look-up tables is proposed in this paper. The merit of the proposed algorithm is that implementation is much easier than the original one while preserving the original characteristics. The experimental results indicate that the Pseudo-Hilbert scan can preserve point neighborhoods as much as possible and take advantage of the high correlation between neighboring lattice points, and it also shows the competitive performance of the Pseudo-Hilbert scan in comparison with other common scan techniques. We believe that this novel scan technique undoubtedly leads to many new applications in those areas can benefit from reducing the dimensionality of the problem.

  • Adaptive Diagnosis of Variants of the Hypercube

    Aya OKASHITA  Toru ARAKI  Yukio SHIBATA  

     
    PAPER-Graphs and Networks

      Vol:
    E88-A No:3
      Page(s):
    728-735

    System-level fault diagnosis deals with the problem of identifying faulty nodes (processors) in a multiprocessor system. Each node is faulty or fault-free, and it can test other nodes in the system, and outputs the test results. The test result from a node is reliable if the node is fault-free, but the result is unreliable if it is faulty. In this paper, we prove that four variants of the hypercube: the crossed cube, the twisted cube, the Mobius cube, and the enhanced cube, are adaptively diagnosed using at most 4 parallel testing rounds, with at most n faulty nodes (for the enhanced cube, with at most n + 1 faulty nodes), where each processor participates in at most one test in each round. Furthermore, we propose another diagnosis algorithm for the n-dimensional enhanced cube with at most n + 1 faulty nodes, and show that it is adaptively diagnosed with at most 5 rounds in the worst case, but with at most 3 rounds if the number of existing faulty nodes is at most n -log(n + 1).

  • Optimal Multicast Tree Routing for Cluster Computing in Hypercube Interconnection Networks

    Weijia JIA  Bo HAN  Pui On AU  Yong HE  Wanlei ZHOU  

     
    PAPER-Networking and System Architectures

      Vol:
    E87-D No:7
      Page(s):
    1625-1632

    Cluster computation has been used in the applications that demand performance, reliability, and availability, such as cluster server groups, large-scale scientific computations, distributed databases, distributed media-on-demand servers and search engines etc. In those applications, multicast can play the vital roles for the information dissemination among groups of servers and users. This paper proposes a set of novel efficient fault-tolerant multicast routing algorithms on hypercube interconnection of cluster computers using multicast shared tree approach. We present some new algorithms for selecting an optimal core (root) and constructing the shared tree so as to minimize the average delay for multicast messages. Simulation results indicate that our algorithms are efficient in the senses of short end-to-end average delay, load balance and less resource utilizations over hypercube cluster interconnection networks.

  • Scheduling Trees onto Hypercubes and Grids

    Satoshi TAYU  

     
    PAPER

      Vol:
    E85-A No:5
      Page(s):
    1011-1019

    In the last three decades, task scheduling problems onto parallel processing systems have been extensively studied. Some of those problems take communication delays into account. In most of previous works, the structure of the parallel processing systems of the scheduling problem is restricted to be fully connected. However, the realistic models of parallel processing systems, such as hypercubes, grids, tori, and so forth, are not fully connected and the communication delay has a great effect on the completion time of tasks. In this paper, we show that the problem of scheduling tasks onto a hypercube/grid is NP-complete even if the task set forms an out- or in-tree and the execution time of each task and each communication take one unit time. Moreover, we construct linear time algorithms for computing an optimal schedule of some classes of binary and ternary trees onto a hypercube if each communication has one unit time.

  • A Generalized Processor Allocation Scheme for Recursively Decomposable Interconnection Networks

    Fan WU  Ching-Chi HSU  

     
    PAPER-Computer Systems

      Vol:
    E85-D No:4
      Page(s):
    694-713

    The Recursively Decomposable Interconnection Network (RDIN) is a set of interconnection networks that can be recursively decomposed into smaller substructures whose topologies and properties are similar to the original one. The examples of the RDIN are hypercubes, star graph, mesh, tree, pyramid, pancake, and WK-recursive network. This paper proposed a uniform and simple model to represent the RDIN inside computers at first. Based on the model, a generalized and efficient allocation scheme capable of being applied to all the members of the RDIN is developed. The proposed scheme can fully recognize the substructures (such as subcube, substar, subtree,. . . ) more easily than ever, and it is the first one that can fully recognize all the incomplete substructures. The best-fit allocation is also proposed. The criterion aims at keeping the largest free parts from being destroyed, as is the philosophy of the best-fit allocation. Moreover, the proposed scheme can be performed in an injured RDIN with its processors and/or links faulty. Finally, the mathematical analysis and simulations for two instances, hypercubes and star graphs, of the RDIN are presented. The results show that the generalized scheme outperforms or is comparable to the other proprietary allocation schemes designed for the specific structure.

  • Competitive Analysis of Minimal Oblivious Routing Algorithms on Hypercubes

    Tzuoo-Hawn YEH  Chin-Laung LEI  

     
    PAPER-Algorithms

      Vol:
    E84-D No:1
      Page(s):
    65-75

    We study the performance of oblivious routing algorithms that follow minimal (shortest) paths, referred to as minimal oblivious routing algorithms in this paper, using competitive analysis on a d-dimensional, N = 2d-node hypercube. We assume that packets are injected into the hypercube arbitrarily and continuously, without any (e.g., probabilistic) assumption on the arrival pattern of the packets. Minimal algorithms reduce the total load in the network in the first place and they preserve locality. First we show that the well known deterministic oblivious routing algorithm, namely, the greedy routing algorithm, has competitive ratio Ω(N1/2). Then we show a problem lower bound of Ω(Nlog 2 (5/4)/log5 N). We also give a natural randomized minimal oblivious routing algorithm whose competitive ratio is close to the problem lower bound we provide.

  • Fault-Tolerant Routing Algorithms for Hypercube Interconnection Networks

    Keiichi KANEKO  Hideo ITO  

     
    PAPER-Fault Tolerance

      Vol:
    E84-D No:1
      Page(s):
    121-128

    Many researchers have used hypercube interconnection networks for their good properties to construct many parallel processing systems. However, as the number of processors increases, the probability of occurrences of faulty nodes also increases. Hence, for hypercube interconnection networks which have faulty nodes, several efficient dynamic routing algorithms have been proposed which allow each node to hold status information of its neighbor nodes. In this paper, we propose an improved version of the algorithm proposed by Chiu and Wu by introducing the notion of full reachability. A fully reachable node is a node that can reach all nonfaulty nodes which have Hamming distance l from the node via paths of length l. In addition, we further improve the algorithm by classifying the possibilities of detours with respect to each Hamming distance between current and target nodes. We propose an initialization procedure which makes use of an equivalent condition to perform this classification efficiently. Moreover, we conduct a simulation to measure the improvement ratio and to compare our algorithms with others. The simulation results show that the algorithms are effective when they are applied to low-dimensional hypercube interconnection networks.

1-20hit(38hit)