RAPWBN的矩阵乘法并行算法

Parallel Matrix Multiplication Algorithm on Reconfigurable Computational Array with Wide Bus Network

在介绍带有宽总线网络的可重构计算阵列(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出了 RAPWBN 阵列上的整数求和算法,并由此得到了 RAPWBN 阵列上的两种快速高效的矩阵乘法运算并行算法。在具有 N3个处理器和 N2条行总线的 RAPWBN 阵列上,若总线带宽ω>logN 字节,矩阵乘法可以在 O(1)时间完成;在具有 N2个处理器和 N 条行总线的 RAPWBN 阵列上,矩阵乘法可以在 O(N)时间完成。它们的效率都为 O(N3),达到了最优。

Based on the structure and the binary prefix sum operation of the reconfigurable computational array with wide bus network (RAPWBN), algorithm for integer aggregation is presented and consequently two fast and efficient matrix multiplication parallel algorithms on RAPWBN array are given. One of the algorithms runs in O(1) time using of N3 processors and N2-row buses with bandwidth ω>logN. The other runs in O(N) time using N2 processors and N -row buses. Since the time-area cost of both algorithms are O(N3), they have optimal efficiency.