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

✍ Scribed by E.I Milovanović; M.K Stojc̆ev; N.M Novaković; I.Z̆ Milovanović; T.I Tokić

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 956 KB
• Volume: 40
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/s0898-1221(00)00231-5

✦ Synopsis

This paper considers the multiplication of matrix A = (aik)n×n by vector b = (bk)n×l on the bidirectional linear systolic array (BLSA) comprised of p _~ In/2] processing elements. To accomplish this matrix, A is partitioned into quasi-diagonal blocks. Each block contains p quasidiagonals. To avoid zero element insertion between successive iterations during the computation of the resulting vector if, we perform index transformation in the block matrices and vector 5". 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 on the BLSA without MIS and when it is involved. (~) 2000 Elsevier Science Ltd. All rights reserved.