Efficient and Scalable Algorithms for All-to-All Personalized Communication on Multidimensional Tori

LIU Gang; GU Nai-jie; REN Kai-xin; XIONG Yan

您当前的位置：

首页 >

文章列表页 >

Efficient and Scalable Algorithms for All-to-All Personalized Communication on Multidimensional Tori

更新时间：2025-07-16

- Efficient and Scalable Algorithms for All-to-All Personalized Communication on Multidimensional Tori
- Acta Electronica Sinica Vol. 33, Issue 9, Pages: 1723-1728(2005)
- 作者机构：
  
  中国科学技术大学计算机科学技术系,安徽,合肥,230027
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP311
- Published：2005
- 稿件说明：
移动端阅览
LIU Gang, GU Nai-jie, REN Kai-xin, et al. Efficient and Scalable Algorithms for All-to-All Personalized Communication on Multidimensional Tori[J]. Acta Electronica Sinica, 2005, 33(9): 1723-1728.
DOI：

LIU Gang, GU Nai-jie, REN Kai-xin, et al. Efficient and Scalable Algorithms for All-to-All Personalized Communication on Multidimensional Tori[J]. Acta Electronica Sinica, 2005, 33(9): 1723-1728. DOI：

摘要

全交换在并行计算领域中有着大量而且重要的应用

例如FFT和矩阵运算等.本文提出了一种适合环网结构的全交换算法.算法中采用了新的网络划分技术及通信模式

使高维环网上全交换算法的通信量的主项达到了理论下限

这是已知的其他相关算法未能达到的

且其启动次数与通信量均优于现有的其他同类算法.本文所述的算法并不要求环网每一维上的处理器结点数目是2的方幂或某一个数的平方.最后

该算法简单规范

易于硬件高效实现.

Abstract

All-to-all personalized communication

also known as complete exchange

is at the heart of numerous applications in parallel computing environment

such as FFT and matrix transpose.This paper presents new efficient algorithms for all-to-all personalized communication in ring and multidimensional torus.In this paper

we adopt new network-partitioning technique and communication pattern to improve the performance of all-to-all personalized communication for multidimensional torus-connected multiprocessors

and the number of nodes in each dimension needs not be a power of two and square of some number.The main item of the transmission time of the algorithms reaches the lower bound in theory

which can not be obtained in existing indirect algorithms proposed in the literature.Finally

the algorithms are conceptually simple and easily implemented in hardware.

关键词

Keywords

references

Views

886

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Via-Aware Parallel Layer Assignment Algorithm for VLSI Physical Design

A Fast Efficient Parallel Algorithm for Hough Transform

XPSort：A Multi-core Parallel Sorting Algorithm for Hierarchical Data in External Memory

An Efficient Parallel Algorithm for H.264/AVC Encoder

Related Author

XU Ning

CHEN Guo-long

GUO Wen-zhong

LI Ze-peng

LIU Geng-geng

QIN Ling

CHEN Ling

CHEN Hong-jian

Related Institution

College of Computer and Data Science, Fuzhou University

School of Information Engineering, Wuhan University of Technology

National Key Lab of Novel Software TechNanjing Univ.NanjingJiangsu 210093China

Department of Computer ScienceYangzhou UniversityYangzhouJiangsu 225009China

National Key Lab of Novel Software Tech,Nanjing Univ.

⁰