Parallel prefix computation on extended multi-mesh network

被引：9
作者：
Jana, PK [1 ]
Naidu, BD
Kumar, S
Arora, M
Sinha, BP
机构：
[1] Indian Sch Mines, Dept Comp Sci & Engn, Dhanbad 826004, Bihar, India
[2] CReWMaN Lab, Arlington, TX 76019 USA
[3] Indian Stat Inst, Adv Comp & Microelect Unit, Kolkata 700035, W Bengal, India
来源：
INFORMATION PROCESSING LETTERS | 2002年 / 84卷 / 06期
关键词：
prefix computation; multi-mesh network; parallel algorithm; time complexity; associative binary operation;
D O I：
10.1016/S0020-0190(02)00317-4
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
A parallel algorithm for prefix computation of N = n(4) elements on an n x n extended multi-mesh network is presented. The A parallel algorithm for prefix computation of N = n(4) network is a modified version of an earlier multi-mesh network with a 4-regular structure. The algorithm takes O(N-1/4) time on N processors (13N(1/4)-5 communication steps and log N + 4 arithmetic/logic steps). (C) 2002 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：295 / 303
页数：9
相关论文
共 18 条
[1]  
AKL SG, 1989, DESIGN ANAL PRALLEL
[2]   LIMITED WIDTH PARALLEL PREFIX CIRCUITS [J].
CARLSON, DA ;
SUGLA, B .
JOURNAL OF SUPERCOMPUTING, 1990, 4 (02) :107-129
[3]   FASTER OPTIMAL PARALLEL PREFIX SUMS AND LIST RANKING [J].
COLE, R ;
VISHKIN, U .
INFORMATION AND COMPUTATION, 1989, 81 (03) :334-352
[4]   A new network topology with multiple meshes [J].
Das, D ;
De, M ;
Sinha, BP .
IEEE TRANSACTIONS ON COMPUTERS, 1999, 48 (05) :536-551
[5]   An efficient sorting algorithm on the multi-mesh network [J].
De, M ;
Das, D ;
Ghosh, M ;
Sinha, BP .
IEEE TRANSACTIONS ON COMPUTERS, 1997, 46 (10) :1132-1137
[6]  
DE M, 1994, TREPE9401 IND STAT I
[7]  
Egecioglu O., 1993, PARALLEL ALGORITHMS, V1, P191, DOI DOI 10.1080/10637199308915441
[8]  
Fich F. E., 1993, P 15 S THEOR COMP, P100
[9]  
JANA PK, 1999, P 2 INT C INF TECHN, P203
[10]  
KOGGE PM, 1974, IBM J RES DEV MAR, P138
12