Matrix-vector multiplication on a fixed-size linear systolic array

This paper considers the multiplication of matrix A = (a(ik))(n x n) by vector (c) over right arrow = (b(k))(n x 1) on the bidirectional linear systolic array (BLSA) comprised of p less than or equal to [n/2] processing elements. To accomplish this matrix, A is partitioned into quasi-diagonal blocks. Each block contains p quasi-diagonals. To avoid zero element insertion between successive iterations during the computation of the resulting vector (c) over right arrow, we perform index transformation in the block matrices and vector (c) over right arrow. The index transformation can be described as perfect shuffle followed by the shifting. Besides, we propose an efficient hardware interface, called memory interface subsystem (MIS), located between the host and BLSA, which optimize memory access by elimination of extraneous main-memory operations. Then we evaluate the speedup and efficiency of the proposed matrix-vector multiplication algorithm. To estimate benefits obtained by introducing MIS, we compare host occupation with data transfer during matrix-vector multiplication an the BLSA without MIS and when it is involved. (C) 2000 Elsevier Science Ltd. All rights reserved.