Scaling multiple addition and prefix sums on the reconfigurable mesh

作     者：Trahan, JL Vaidyanathan, R 

作者机构：Louisiana State Univ Dept Elect & Comp Engn Baton Rouge LA 70803 USA 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2002年第82卷第6期

页      面：277-282页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation, NSF, (CCR-0073429) National Science Foundation, NSF 

主　　题：reconfigurable mesh parallel algorithms scalability arithmetic algorithms reconfigurable models 

摘      要：Multiple addition is the problem of adding N b-bit integers. Prefix sums and multiple addition play fundamental roles in many algorithms, particularly on the reconfigurable mesh (R-Mesh). Scaling algorithms on the R-Mesh to run with the same or increased efficiency on fewer processors is a challenging and important proposition. In this paper. we present algorithms that scale with increasing efficiency for multiple addition, prefix sums. and matrix-vector multiplication. Along the way. we obtain an improved multiple addition algorithm. (C) 2001 Elsevier Science B.V. All rights reserved.