Annals of Faculty of Computer and Information Sciences, Hosei University
Department of computer science <<Previous Next>>
HOME >> No.3 CONTENTS >> Yamin LI
Professor
Yamin LI
Publications(January 2002 - December 2002)
  1. Yamin Li, Shietung Peng, and Wanming Chu, "Metacube -- A New Interconnection Network for Large Scale Parallel Systems'', Australian Computer Science Communications, Vol.24, No.3, 2002, Australian Computer Society, pp29-36.
    Abstract - The hypercube has been widely used as the interconnection network for parallel computers. However, in hypercubes, the number of communication links for each node is a logarithmic function of the total number of nodes. Therefore, the hypercube is not a good candidate for an interconnection network for a very large parallel computer that might contain hundreds of thousands of nodes due to IC technology and port number limitations. This paper introduces a new interconnection network for very large parallel computers called metacube (MC). An MC network has a 2-level cube structure. An MC(k,m) network can connect 2m2k+k nodes with m+k links per node, where k is the dimension of the high-level cubes (classes) and m is the dimension of the low-level cubes (clusters). An MC network is a symmetric network with short diameter, easy and efficient routing and broadcasting similar to that of the hypercube. However, an MC network can connect millions of nodes with up to 6 links per node. An MC(2,3) with 5 links per node has 16,384 nodes and an MC(3,3) with 6 links per node has 134,217,728 nodes. We describe the MC network's structure, topological properties and routing and broadcasting algorithms.
  2. Yamin Li, Shietung Peng, and Wanming Chu, "Efficient Communication in Metacube: A New Interconnection Network'', Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN 2002), Manila, Philippines, May 2002, IEEE Computer Society Press, pp165-170.
    Abstract - This paper introduces a new interconnection network for very large parallel computers called metacube (MC). An MC network has a 2-level cube structure. An MC(k,m) network connects 2m2k+k nodes with m+k links per node, where k is the dimension of a high-level cube and m is the dimension of low-level cubes (clusters). An MC network is a symmetric network with short diameter, easy and efficient routing similar to that of hypercubes. However, an MC network can connect more than one hundred of millions of nodes with only 6 links per node. Design of efficient routing algorithms for collective communications is the key issue for any interconnection network. In this paper, we also show that total exchange (all-to-all personalized communication) can be done efficiently in metacube.
  3. Yamin Li and Shietung Peng, "Algorithms of Routing and Matrix Multiplication on Dualcube'', Proceedings of the Second International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD01), Nagoya Institute of Technology, Japan, Aug., 2001, pp422-429.
    Abstract - Dualcube is an interconnection networks that has hypercube-like structure with the capacity to hold much more nodes than the conventional hypercube with the same number of links per node. The motivation of using dualcube as an interconnection network is to mitigate the problem of increasing the number of links in the large-scale hypercube network while keeps most of the topological properties of the hypercube network. In this paper, we focus on the design of efficient algorithms for routing and numerical operations on dualcube such as prefix computation, vector-matrix and matrix-matrix multiplications. Our results show that the routing and the basic numerical computations can be done on dualcube almost as fast as those on hypercube.
  4. Wanming Chu and Yamin Li, "Performance Evaluation of a Multiple-Threaded Multiple-Pipelined Java Processor'', Proceedings of the 6th World Multiconference on Systemics, Cybernetics and Informatics (SCI 2002), Orlando, USA, July 14-18, 2002, Vol. V, Computer Science I, pp281-286.
    Abstract - Executing Java bytecodes natively by high-performance Java processors has been becoming more attractive as network computing gains importance. This paper proposes a multiple-threaded multiple-pipelined Java processor architecture and presents the design and implementation of a tracer which gathers desirable information on the behavior of Java programs and an architectural simulator which investigates Java bytecode instruction/thread level parallelism and predicts the performance of the proposed processor. We use multiple pipelined functional units (FUs) to execute multiple bytecodes in parallel in our processor model. The types of FUs and the number of each type of FUs needed for executing Java bytecodes are also investigated. Our simulation results show that a Java processor with two issuing slots could achieve an average 5.86 IPC (instructions per cycle) performance. The simulator also predicts the utilization of FUs with different processor configurations. Since the processor configurations can be changed easily just by changing a configuration file, this simulator and the simulation results can be helpful for turning the processor design decisions.
  5. Yamin Li, Shietung Peng, and Wanming Chu, "Fault-tolerant Routing in Metacube'', Proceedings of the Third International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT'02), Kanazawa Bunka Hall, Kanazawa, Japan, September 2002, pp343-350.
    Abstract - A new interconnection network with low-degree for very large parallel computers called metacube (MC) has been introduced recently. The MC network has short diameter similar to that of the hypercube. However, the degree of an MC network is much lower than that of a hypercube of the same size. More than one hundred of millions of nodes can be connected by an MC network with up to 6 links per node. % The MC network has 2-level cube structure. An MC(k,m) network that connects 2m2k+k nodes with m+k links per node has two parameters, k and m, where k is the dimension of the high-level cubes (classes) and m is the dimension of the low-level cubes (clusters). % In this paper, we give an efficient algorithm for fault-tolerant routing in MC networks. The fault-tolerant routing problem in MC(k,m) is solved through a special structure in an MC network, called multi-channel cube. In order to construct k disjoint paths for each node pair in a multi-channel cube, an innovative technique, called signature, is introduced.
  6. Yamin Li, Shietung Peng, and Wanming Chu, "Hamiltonian Cycle Embedding for Fault Tolerance in Dual-cube'', Proceedings of the IASTED International Conference on Networks, Parallel and Distributed Processing, and Applications (NPDPA 2002), Tsukuba, Japan, October 2002, pp1-6.
    Abstract - The hypercube has been widely used as the interconnection network (IN) in parallel computers. However, the major drawback of the hypercube is the increase in the number of communication links for each node with the increase in the total number of nodes in the system. A dual-cube DC(m) has m+1 links per node where m is the degree of a cluster (m-cube), one more link is used for connecting to a node in another cluster. The dual-cube mitigates the problem of increasing number of links in the large-scale hypercube network while keeps most of the topological properties of the hypercube network. Embedding a linear array or a ring into interconnection networks even when faulty-links exit is an important issue for the design of INs. In this paper, we show that a hamiltonian cycle exists in a DC(m) with up to m-1 faulty links. This is optimal because the degree of a DC(m) is m+1. We also give efficient algorithms for constructing hamiltonian cycles in DC(m).
  7. Yamin Li, Shietung Peng, and Wanming Chu, "From Dual-cube to Metacube: Efficient Low-Degree Alternatives to Hypercube'', Proceedings of the First International Symposium on Cyber Worlds: Theory and Practice (CW 2002), November 2002, Tokyo, Japan. IEEE Computer Society Press, pp85-94.
    Abstract - The hypercube has been widely used as the interconnection network in parallel computers. However, when dealing with the parallel computers of very large scale, the port limitation due to the technology greatly forbid the use of hypercube networks. The hypercube-based SGI Origin2000, a newly developed multiprocessor system, tried to solve this problem by introducing a Cray router. In this paper, we first describe a hypercube-like network, called dual-cube, that was motivated by the structure of Origin2000. A dual-cube DC(m) has m+1 links per node where m is the degree of a cluster (m-cube), one more link is used for connecting to a node in another cluster. The dual-cube mitigates the problem of port limitation in the large-scale hypercube network while keeps most of the topological properties of the hypercube network. Then, we describe an interconnection network that extends dual-cube into a more general network called metacube. The metacube has a two-level cube structure with two parameters representing the dimensions of the two-level cubes. Metacube is much more flexible than dual-cube and can solve the port limitation problem completely. The dual-cube and metacube networks can be applied to SGI Origin2000 to connect large number of processors without using Cray router.

>PAGE TOP