Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Communication Cost
Parallel Algorithm
Point of View
Sorting Algorithm
Related Publications
(1)
Emulation of Hypercube Architecture on NearestNeighbor MeshConnected Processing Elements
Subscribe
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
Edit
Executing Algorithms with Hypercube Topology on Torus Multicomputers
(
Citations: 11
)
BibTex

RIS

RefWorks
Download
Antonio González
,
Miguel Valerogarcía
,
Luis Díaz De Cerio
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 onedimensional 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. 803814, 1995
Cumulative
Annual
Citation Context
(6)
...In modern supercomputer distributed systems the 3Dtorus is usually used as a network graph [
13
]...
...This approach is based on usage the butterfly scheme in parallel realization of semigroup operation and mapping the butterfly onto hypercube with subsequent XORembedding [
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 Wang
,
et al.
An Effective Approach for Multicast on Multicore Architecture
...Some authors, for instance, try to embed hypercubes into toruses and rings as in [
14
, 15]...
Sanpawat Kantabutra
,
et 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 CCcube 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 Cerio
,
et 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 CCcube 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 Cerio
,
et al.
Hypercube algorithms on mesh connected multicomputers
References
(13)
Embedding Networks with Ring Connections in Hypercube Machines
(
Citations: 5
)
C. Y. Roger Chen
,
Yehching Chung
Conference:
International Conference on Parallel Processing  ICPP
, pp. 327334, 1990
Embedding ThreeDimensional Meshes in Boolean Cubes by Graph Decomposition
(
Citations: 9
)
Chingtien Ho
,
S. Lennart Johnsson
Conference:
International Conference on Parallel Processing  ICPP
, pp. 319326, 1990
Optimal numberings and isoperimetric problems on graphs
(
Citations: 172
)
L. Harper
Journal:
Journal of Combinatorial Theory
, vol. 1, no. 3, pp. 385393, 1966
Solving problems on concurrent processors
(
Citations: 619
)
G Fox
Published in 1988.
Emulation of Hypercube Architecture on NearestNeighbor MeshConnected Processing Elements
(
Citations: 14
)
Spira Matic
Journal:
IEEE Transactions on Computers  TC
, vol. 39, no. 5, pp. 698700, 1990
Sort by:
Citations
(11)
Mapping semigroup array operations onto multicomputer with torus topology
Mikhail S. Tarkov
Conference:
International Conference on Ubiquitous Information Management and Communication  ICUIMC
, pp. 13, 2011
An Effective Approach for Multicast on Multicore Architecture
Yuxin Wang
,
Liye Yuan
,
He Guo
,
Xinzhong Hui
,
Yuansheng Yang
Conference:
Scalable Computing and Communications  ScalComEmbeddedCom
, pp. 3741, 2009
On Embedding of a Hypercube in a Completely Overlapping Network
Sanpawat Kantabutra
,
Jakarin Chawachat
Journal:
Theory of Computing Systems / Mathematical Systems Theory  MST
, vol. 44, no. 1, pp. 105116, 2009
Hypercube Algorithms on Mesh Connected Multicomputers
(
Citations: 3
)
Luis Díaz De Cerio
,
Miguel Valerogarcía
,
Antonio González
Journal:
IEEE Transactions on Parallel and Distributed Systems  TPDS
, vol. 13, no. 12, pp. 12471260, 2002
Hypercube algorithms on mesh connected multicomputers
Luis Diaz de Cerio
,
Miguel ValeroGarcia
,
Antonio Gonzalez
Journal:
IEEE Transactions on Parallel and Distributed Systems  TPDS
, vol. 13, no. 12, pp. 12471260, 2002