MEISSA: Multiplying Matrices Efficiently in a Scalable Systolic Architecture
Bahar Asgari, Ramyad Hadidi, Hyesoon Kim
Abstract
The fundamental building block of many algorithms such as data analytics and neural networks is matrix multiplication. Besides its popularity, matrix multiplication is one of the rare algebraic computations that demand high data reuse rate. During the past decades, systolic arrays have been proposed as a low-cost solution for implementing high data reuse, and they have seen a resurgence of interest recently. Particularly, two categories of systolic arrays have been proposed, both of which are made of connected multiply-and-accumulate (MAC) units: non-stationary and stationary architectures. While in the nonstationary architecture both operands of the matrix multiplication flow through the MAC units, in the stationary architecture, only one of them flows. Regardless of their advantages, their common challenges are that they have high latency and are not scalable. In other words, latency increases linearly when the input size grows. Particularly, these are crucial challenges for applications of large matrix multiplication (e.g., deep neural networks (DNNs)) in the edge, in which latency must be optimized not throughput. To resolve this challenge, we propose multiplying matrices efficiently in a scalable systolic architecture (Meissa). Meissa is a novel stationary systolic array that, unlike prior work, separates multipliers from the adders rather than combining them in a unified array of MACs. Such an interconnection enables Meissa to sustain a sublinear growing rate in latency with scaling problem size. Our experimental results on a ZYNQ XC7Z020 FPGA show that Meissa executes the single-batch inference of DNNs 1.99× and 1.83× as fast as the prior non-stationary and stationary systolic arrays, respectively.