The Experts below are selected from a list of 3138 Experts worldwide ranked by ideXlab platform

Kiyoshi Sawada - One of the best experts on this subject based on the ideXlab platform.

  • A model of adding two edges in levels of a Complete Binary Tree
    ITM Web of Conferences, 2017
    Co-Authors: Kiyoshi Sawada
    Abstract:

    This study proposes a model of adding two edges between nodes of the same level of a Complete Binary Tree. Firstly we add one edge between the optimal two nodes with the optimal depth N* maximizing a total shortening distance. Secondly we add another edge between nodes with the same depth M (M = 1, 2, …, H). The total shortening distance to obtain the optimal two nodes with the optimal depth M* maximizing a total shortening distance is formulated.

  • a model of adding relations in multi levels to a formal organization structure with two subordinates
    International MultiConference of Engineers and Computer Scientists, 2009
    Co-Authors: Kiyoshi Sawada, Kazuyuki Amano
    Abstract:

    This paper proposes a model of adding relations in multi‐levels to a formal organization structure with two subordinates such that the communication of information between every member in the organization becomes the most efficient. When edges between every pair of nodes with the same depth in L (L = 1, 2, …, H) levels are added to a Complete Binary Tree of height H, an optimal set of depths {N1, N2, …, NL} (H⩾N1>N2> …>NL⩾1) is obtained by maximizing the total shortening path length which is the sum of shortening lengths of shortest paths between every pair of all nodes in the Complete Binary Tree. It is shown that {N1, N2, …, NL}* = {H, H−1, …, H−L+1}.

  • A Model of Adding Relations in Multi‐levels to a Formal Organization Structure with Two Subordinates
    AIP Conference Proceedings, 2009
    Co-Authors: Kiyoshi Sawada, Kazuyuki Amano
    Abstract:

    This paper proposes a model of adding relations in multi‐levels to a formal organization structure with two subordinates such that the communication of information between every member in the organization becomes the most efficient. When edges between every pair of nodes with the same depth in L (L = 1, 2, …, H) levels are added to a Complete Binary Tree of height H, an optimal set of depths {N1, N2, …, NL} (H⩾N1>N2> …>NL⩾1) is obtained by maximizing the total shortening path length which is the sum of shortening lengths of shortest paths between every pair of all nodes in the Complete Binary Tree. It is shown that {N1, N2, …, NL}* = {H, H−1, …, H−L+1}.

  • Adding Edges for a Simple Cycle to a Complete Binary Tree Maximizing Total Shortening Path Length
    2009
    Co-Authors: Kiyoshi Sawada
    Abstract:

    This study proposes a model of adding edges of forming a simple cycle to a level of depth N in a Complete Binary Tree of height H under giving priority to edges between two nodes of which the deepest common ancestor is deeper. An optimal depth N* is obtained by maximizing the total shortening path length which is the sum of shortening lengths of shortest paths between every pair of all nodes in the Complete Binary Tree.

  • Adding Edges for a Simple Path to a Level of a Complete Binary Tree Maximizing Total Shortening Path Length
    2009
    Co-Authors: Kiyoshi Sawada
    Abstract:

    This study proposes a model of adding edges of forming a simple path to a level of depth N in a Complete Binary Tree of height H under giving priority to edges between two nodes of which the deepest common ancestor is deeper. An optimal depth N∗ is obtained by maximizing the total shortening path length which is the sum of shortening lengths of shortest paths between every pair of all nodes in the Complete Binary Tree.

Fang Zhifeng - One of the best experts on this subject based on the ideXlab platform.

  • new xml document coding scheme based on Complete Binary Tree
    Journal of Computer Applications, 2008
    Co-Authors: Fang Zhifeng
    Abstract:

    In this paper,a new coding scheme was proposed,which was based on the sequence of its Complete Binary Tree.The scheme is easy to realize and only one positive integer is needed to express the position of the node in XML Tree.The time-bounding of identifying the ancestor-descendant relationships is only O(log n).It also supports XML document update.In the scheme,the length of the code is short.

H. Wang - One of the best experts on this subject based on the ideXlab platform.

  • ON IMPROVING THE PERFORMANCE OF Tree MACHINES
    International Journal of High Speed Computing, 1995
    Co-Authors: Ajay Gupta, H. Wang
    Abstract:

    In this paper we introduce a class of Trees, called generalized compressed Trees. Generalized compressed Trees can be derived from Complete Binary Trees by performing certain ‘contraction’ operations. A generalized compressed Tree CT of height h has approximately 25% fewer nodes than a Complete Binary Tree T of height h. We show that these Trees have smaller (up to a 74% reduction) 2-dimensional and 3-dimensional VLSI layouts than the Complete Binary Trees. We also show that algorithms initially designed for T can be simulated by CT with at most a constant slow-down. In particular, algorithms having non-pipelined computation structure and originally designed for T can be simulated by CT with no slow-down.

  • Generalized Compressed Tree Machines (Extended Abstract)
    1992
    Co-Authors: Ajay Gupta, H. Wang
    Abstract:

    compressed Tree machine is obtained by ‘merging’ k interior processors of an n-leaf Complete Binary Tree machine into an interior processor of the generalized compressed Tree machine. Hence, they have the same number of leaf processors as Complete Binary Trees but have a total of approximately 25% less processors. We show that generalized compressed Tree machines exhibit significantly better (up to 74% reduction) 2-d and 3-d VLSI layouts than the Complete Binary Trees. Furthermore, we show that many parallel algorithms, that have been designed for Complete Binary Trees, can be easily implemented to run on generalized compressed Tree machines with no loss in their execution times. We also show that for some cases generalized compressed Tree machines can be simulated better on a hypercube multiprocessor than the most efficient simulation of a Complete Binary Tree on a hypercube multiprocessor. For other cases the simulation exhibits similar performance.

  • IPPS - Generalized compressed Tree machines
    Proceedings Sixth International Parallel Processing Symposium, 1
    Co-Authors: Ajay Gupta, H. Wang
    Abstract:

    Parallel machines interconnecting up to thousands of processors have been proposed and recently built. One of the earliest and the most prominent one is a Complete Binary Tree machine. The authors propose a family of Tree machines called generalized compressed Tree machines. Generalized compressed Tree machines may, in general, be viewed as a derivative of the Complete Binary Tree networks. >

Kazuyuki Amano - One of the best experts on this subject based on the ideXlab platform.

  • a model of adding relations in multi levels to a formal organization structure with two subordinates
    International MultiConference of Engineers and Computer Scientists, 2009
    Co-Authors: Kiyoshi Sawada, Kazuyuki Amano
    Abstract:

    This paper proposes a model of adding relations in multi‐levels to a formal organization structure with two subordinates such that the communication of information between every member in the organization becomes the most efficient. When edges between every pair of nodes with the same depth in L (L = 1, 2, …, H) levels are added to a Complete Binary Tree of height H, an optimal set of depths {N1, N2, …, NL} (H⩾N1>N2> …>NL⩾1) is obtained by maximizing the total shortening path length which is the sum of shortening lengths of shortest paths between every pair of all nodes in the Complete Binary Tree. It is shown that {N1, N2, …, NL}* = {H, H−1, …, H−L+1}.

  • A Model of Adding Relations in Multi‐levels to a Formal Organization Structure with Two Subordinates
    AIP Conference Proceedings, 2009
    Co-Authors: Kiyoshi Sawada, Kazuyuki Amano
    Abstract:

    This paper proposes a model of adding relations in multi‐levels to a formal organization structure with two subordinates such that the communication of information between every member in the organization becomes the most efficient. When edges between every pair of nodes with the same depth in L (L = 1, 2, …, H) levels are added to a Complete Binary Tree of height H, an optimal set of depths {N1, N2, …, NL} (H⩾N1>N2> …>NL⩾1) is obtained by maximizing the total shortening path length which is the sum of shortening lengths of shortest paths between every pair of all nodes in the Complete Binary Tree. It is shown that {N1, N2, …, NL}* = {H, H−1, …, H−L+1}.

  • Adding Relations in Multi-levels to an Organization Structure of a Complete Binary Tree Maximizing Total Shortening Path Length
    2009
    Co-Authors: Kiyoshi Sawada, Kazuyuki Amano
    Abstract:

    This paper proposes a model of adding relations in multi-levels to an organization structure which is a Complete Binary Tree such that the commu- nication of information between every member in the organization becomes the most efficient. When edges between every pair of nodes with the same depth in L(L = 1;2; ;H ) levels are added to a Complete Binary Tree of height H, an optimal set of depths fN1;N2; ;NLg (H N1 > N2 > > NL 1) is ob- tained by maximizing the total shortening path length which is the sum of shortening lengths of shortest paths between every pair of all nodes in the com- plete Binary Tree. It is shown that fN1;N2; ;NLg = fH;H 1; ;H L + 1g.

Jen-chih Lin - One of the best experts on this subject based on the ideXlab platform.

  • Load-balance and fault-tolerance for embedding a Complete Binary Tree in an IEH with N-expansion
    WSEAS Transactions on Computers archive, 2008
    Co-Authors: Jen-chih Lin
    Abstract:

    Embedding is of great importance in the applications of parallel computing. Every parallel application has its intrinsic communication pattern. The communication pattern graph is embedded in the topology of multiprocessor structures so that the corresponding application can be executed. This paper presents strategies for reconfiguring a Complete Binary Tree in a faulty Incrementally Extensible Hypercube (IEH) with N-expansion. This embedding algorithm show a Complete Binary Tree can be embedded in a faulty IEH with dilation 4, load 1, and congestion 1 such that O(n2-h2) faults can be tolerated, where n is the dimension of IEH and (h-1) is the height of a Complete Binary Tree. Furthermore, the presented embedding methods are optimized mainly for balancing the processor loads, while minimizing dilation and congestion as far as possible. According to the result, we can embed the parallel algorithms developed by the structure of Complete Binary Tree in an IEH. This methodology of embedding enables extremely high-speed parallel computation.

  • Faulty-tolerant algorithm for mapping a Complete Binary Tree in an IEH
    WSEAS Transactions on Computers archive, 2008
    Co-Authors: Jen-chih Lin, Huan-chao Keh
    Abstract:

    Different parallel architectures may require different algorithms to make the existent algorithms on one architecture be easily transformed to or implemented on another architecture. This paper proposes a novel algorithm for embedding Complete Binary Trees in a faulty Incrementally Extensible Hypercube (IEH). Furthermore, to obtain the replaceable node of the faulty node, 2-expansion is permitted such that up to (n+1) faults can be tolerated with dilation 3, congestion 1 and load 1. The presented embedding methods are optimized mainly for balancing the processor loads, while minimizing dilation and congestion as far as possible. According to the result, we can map the parallel algorithms developed by the structure of Complete Binary Tree in an IEH. These methods of reconfiguring enable extremely high-speed parallel computation.

  • Embedding of Complete Binary Tree with 2-expansion ina faulty Flexible Hypercube
    Journal of Systems Architecture, 2001
    Co-Authors: Jen-chih Lin, Tzong-heng Chi, Huan-chao Keh, Ay-hwa Andy Liou
    Abstract:

    Abstract Although the embedding of Complete Binary Trees in faulty hypercubes has received considerable attention, to our knowledge, no paper has demonstrated how to embed a Complete Binary Tree in a faulty Flexible Hypercube. Therefore, this investigation presents an algorithm to facilitate the embedding job when the Flexible Hypercube contains faulty nodes. Of particular concern are the network structures of the Flexible Hypercube that balance the load before as well as after faults start to degrade the performance of the Flexible Hypercube. Furthermore, to obtain the replaceable node of the faulty node, 2-expansion is permitted such that up to (n−2) faults can be tolerated with congestion 1, dilation 4 and load 1.

  • Simulation of Complete Binary Tree Structures in a Faulty Flexible Hypercube
    Journal of Scientific Computing, 1999
    Co-Authors: Huan-chao Keh, Jen-chih Lin
    Abstract:

    The Flexible Hypercube is a generalization of Binary hypercube networks in that the number of nodes can be arbitrary in contrast to a strict power of 2. Restated, the Flexible Hypercube retains the connectivity and diameter properties of the corresponding hypercube. Although the embedding of Complete Binary Trees in faulty hypercubes has received considerable attention, to our knowledge, no paper has demonstrated how to embed a Complete Binary Tree in a faulty Flexible Hypercube. Therefore, this investigation presents a novel algorithm to facilitate the embedding job when the Flexible Hypercube contains faulty nodes. Of particular concern are the network structures of the Flexible Hypercube that balance the load before as well as after faults start to degrade the performance of the Flexible Hypercube. Furthermore, to obtain the replaceable node of the faulty node, 2-expansion is permitted such that up to ( n − 2) faults can be tolerated with congestion 1, dilation 4 and load 1. That is, ( n − 1) is the dimension of a Flexible Hypercube. Results presented herein demonstrate that embedding methods are optimized.

  • Embedding a Complete Binary Tree into a faulty supercube
    Proceedings of 3rd International Conference on Algorithms and Architectures for Parallel Processing, 1
    Co-Authors: Huan-chao Keh, Jen-chih Lin
    Abstract:

    The supercube is a novel interconnection network that is derived from the hypercube. Unlike the hypercube, the supercube can be constructed for any number of nodes. That is, the supercube is incrementally expandable. In addition, the supercube retains the connectivity and diameter properties of the corresponding hypercube. In this paper, we consider the problem of embedding and reconfiguring Binary Tree structures in a faulty supercube. Further more, for finding the replaceable node of the faulty node, we allow 2-expansion such that we can show that up to (n-2) faults can be tolerated with congestion 1 and dilation 4 that is (n-1) is the dimension of a supercube.