Fast problem-size-independent parallel prefix circuits

被引:8
作者
Lin, Yen-Chun [1 ]
Hung, Li-Ling [1 ]
机构
[1] Natl Taiwan Univ Sci & Technol, Dept Comp Sci & Informat Engn, Taipei 106, Taiwan
关键词
Combinational circuit; Depth-size optimal; Parallel algorithms; Prefix operation; Problem-size independent; Waist-size optimal; ALGORITHMS; COMPUTATIONS; FAMILY;
D O I
10.1016/j.jpdc.2008.12.003
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
A family of parallel algorithms solving the prefix problem on the combinational circuit model is presented. These prefix circuits are waist-size optimal with waist 1 (WSO-1). They are not only building blocks for constructing fast depth-size optimal prefix circuits, but also themselves fast problem-size-independent prefix circuits. When the problem size is greater than the circuit width. the presented prefix circuits may very much faster than any other prefix circuits of the same width, especially when the problem size is greater than or equal to twice the circuit width. The new prefix circuits are compared analytically with other representative prefix circuits to show how fast they are. They have the minimum depth and are the fastest among all WSO-1 prefix circuits of the same width and fan-out. Thus, they are better building blocks than other WSO-1 circuits for constructing fast depth-size optimal prefix circuits with the same fan-out. (C) 2009 Elsevier Inc. All rights reserved.
引用
收藏
页码:382 / 388
页数:7
相关论文
共 48 条
[21]   PARALLEL PREFIX COMPUTATION [J].
LADNER, RE ;
FISCHER, MJ .
JOURNAL OF THE ACM, 1980, 27 (04) :831-838
[22]  
Lakshmivarahan S., 1987, Proceedings of the 1987 International Conference on Parallel Processing, P58
[23]  
LAKSHMIVARAHAN S, 1994, PARALLEL COMPUTING U
[24]  
Leighton F. T., 1992, INTRO PARALLEL ALGOR
[25]   Scalable hardware-algorithms for binary prefix sums [J].
Lin, R ;
Nakano, K ;
Olariu, S ;
Pinotti, MC ;
Schwing, JL ;
Zomaya, AY .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2000, 11 (08) :838-850
[26]   Faster optimal parallel prefix circuits: New algorithmic construction [J].
Lin, YC ;
Su, CY .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2005, 65 (12) :1585-1595
[27]   A new approach to constructing optimal parallel prefix circuits with small depth [J].
Lin, YC ;
Hsiao, JW .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2004, 64 (01) :97-107
[28]  
Lin YC, 2003, J INF SCI ENG, V19, P75
[29]   Efficient parallel prefix algorithms on multiport message-passing systems [J].
Lin, YC ;
Yeh, CS .
INFORMATION PROCESSING LETTERS, 1999, 71 (02) :91-95
[30]   Constructing H4, a fast depth-size optimal parallel prefix circuit [J].
Lin, YC ;
Hsu, YH ;
Liu, CK .
JOURNAL OF SUPERCOMPUTING, 2003, 24 (03) :279-304