高维环网上的一种可扩展的全交换算法

刘刚; 顾乃杰; 任开新; 熊焰

您当前的位置：

首页 >

文章列表页 >

高维环网上的一种可扩展的全交换算法

论文 | 更新时间：2025-07-16

- 高维环网上的一种可扩展的全交换算法
- Efficient and Scalable Algorithms for All-to-All Personalized Communication on Multidimensional Tori
- 电子学报 2005年33卷第9期页码：1723-1728
- 作者机构：
  
  中国科学技术大学计算机科学技术系,安徽,合肥,230027
- 作者简介：
- 基金信息：
  
  安徽省自然科学基金 (No.03042210)
- DOI：
  中图分类号： TP311
- 纸质出版：2005
- 稿件说明：
移动端阅览
刘刚, 顾乃杰, 任开新, 等. 高维环网上的一种可扩展的全交换算法[J]. 电子学报, 2005,33(9):1723-1728.

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.
刘刚, 顾乃杰, 任开新, 等. 高维环网上的一种可扩展的全交换算法[J]. 电子学报, 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

浏览量

886

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

面向超大规模集成电路物理设计的通孔感知的并行层分配算法

一种快速高效的Hough变换并行算法

XPSort——树形数据多核并行外存排序算法

高效的H.264并行编码算法