Efficient indirect all-to-all personalized communication on rings and 2-D tori

All-to-All personalized communication is a basic communication operation in a parallel computing environment. There are a lot of results appearing in literature. All these communication algorithms can be divided into two kinds: direct communication algorithm and indirect communication algorithm. The...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer science and technology 2001-09, Vol.16 (5), p.480-483
Main Author: Gu, Naijie
Format: Article
Language:English
Subjects:
Algorithms
Channels
Communication
Complexity
Customization
Lower bounds
Optimization
Parallel processing
Personalized
Processors
Studies
Toruses
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:All-to-All personalized communication is a basic communication operation in a parallel computing environment. There are a lot of results appearing in literature. All these communication algorithms can be divided into two kinds: direct communication algorithm and indirect communication algorithm. The optimal direct all-to-all communication algorithm on rings and 2-D tori does exist. But, for indirect all-to-all communication algorithms, there is a gap between the time complexity of the already existing algorithm and the lower bound. In this paper an efficient indirect algorithm for all-to-all communication on rings and 2-D square tori with bidirection channels is presented. The algorithms is faster than any previous indirect algorithms. The main items of the time complexity of the algorithm isp2/8 andp3/2/8 on rings and 2-D tori respectively, both reaching the theoretical lower bound, wherep is the number of processors.
ISSN:1000-9000
1860-4749
DOI:10.1007/BF02948967