Academic
Publications
Executing Algorithms with Hypercube Topology on Torus Multicomputers

Executing Algorithms with Hypercube Topology on Torus Multicomputers,IEEE Transactions on Parallel and Distributed Systems,Antonio González,Miguel Val

Executing Algorithms with Hypercube Topology on Torus Multicomputers   (Citations: 11)
BibTex | RIS | RefWorks Download
Many parallel algorithms use hypercubes as the communication topology among their processes. When such algorithms are executed on hypercube multicomputers the communication cost is kept minimum since processes can be allocated to processors in such a way that only communication between neighbor processors is required. However, the scalability of hypercube multicomputers is constrained by the fact that the interconnection cost per node increases with the total number of nodes. From scalability point of view, meshes and toruses are more interesting classes of interconnecti on topologies. This paper focuses on the execution of algorithms with hypercube communication topology on multicomputer s with mesh or torus interconnection topologies. The proposed approach is based on looking at different embeddings of hypercube graphs onto mesh or torus graphs. The paper concentrates on toruses since an already known embedding, which is called standard embedding,is optimal for meshes. In this paper, an embedding of hypercubes onto toruses of any given dimension is proposed. This novel embedding is called xor embedding. The paper presents a set of performance figures for both the standard and the xor embeddings and shows that the latter outperforms the former for any torus. In addition, it is proven that for a one-dimensional torus (a ring) the xor embedding is optimal in the sense that it minimizes the execution time of a class of parallel algorithms with hypercube topology. This class of algorithms is frequently found in real applications, such as FFT and some class of sorting algorithms.
Journal: IEEE Transactions on Parallel and Distributed Systems - TPDS , vol. 6, no. 8, pp. 803-814, 1995
Cumulative Annual
    • ...In modern supercomputer distributed systems the 3D-torus is usually used as a network graph [1-3]...
    • ...This approach is based on usage the butterfly scheme in parallel realization of semigroup operation and mapping the butterfly onto hypercube with subsequent XOR-embedding [2] of the hypercube onto torus...
    • ...TORUS The hypercube can be mapped onto torus [2, 3]. A...
    • ...method for mapping the hypercube onto the torus ( XOR embedding) is proposed in [2]...
    • ...It is shown [2] that hypercube Hd can be embedded into torus...

    Mikhail S. Tarkov. Mapping semigroup array operations onto multicomputer with torus topol...

    • ...Paper [10] proposes algorithms which are executed on hypercube multi computers...

    Yuxin Wanget al. An Effective Approach for Multicast on Multi-core Architecture

    • ...Some authors, for instance, try to embed hypercubes into toruses and rings as in [14, 15]...

    Sanpawat Kantabutraet al. On Embedding of a Hypercube in a Completely Overlapping Network

    • ...The initial ideas from which we have developed the CALMANT methodology come from the study of graph embeddings of a hypercube onto a mesh or a torus [5]...
    • ...There are many important algorithms that fit into the CC-cube type [5]...
    • ...Different approaches for embedding hypercube algorithms onto meshes and tori have been proposed [4, 5, 8, 10]...
    • ...The standard embedding [10] has been shown to be optimal for meshes [5] in the sense of reducing the average dilation of the hypercube dimensions...
    • ...Nevertheless, the minimum average dilation property of the embedding is not affected [5]...

    Luis Díaz De Cerioet al. Hypercube Algorithms on Mesh Connected Multicomputers

    • ...The initial ideas from which we have developed the CALMANT methodology come from the study of graph embeddings of a hypercube onto a mesh or a torus [5]...
    • ...There are many important algorithms that fit into the CC-cube type [5]...
    • ...Different approaches for embedding hypercube algorithms onto meshes and tori have been proposed [4], [5], [8], [10]...
    • ...The standard embedding [10] has been shown to be optimal for meshes [5] in the sense of reducing the average dilation of the hypercube dimensions...
    • ...Nevertheless, the minimum average dilation property of the embedding is not affected [5]...

    Luis Diaz de Cerioet al. Hypercube algorithms on mesh connected multicomputers

Sort by: