Application Level Synthesis: Creating Matrix-Matrix Multiplication Library: A Case Study

Abstract

Efficiently synthesizing an entire application that consists of multiple algorithms for hardware implementation is a very difficult and unsolved problem. One of the main challenges is the lack of good algorithmic libraries. A good algorithmic library should contain algorithmic implementations that can be physically composable, and their cost metrics can be accurately predictable. Physical composability and cost predictability can be achieved using a novel framework called SiLago. By physically abutting small hardware blocks together like Lego bricks, the SiLago framework can eliminate the time-consuming logic and physical synthesis and immediately give post-layout accurate cost estimation. In this paper, we build a library for matrix-matrix multiplication algorithm based on the SiLago framework as a case study because matrix-matrix multiplication is a fundamental operation in scientific computing that is frequently found in applications such as signal processing, image processing, pattern recognition, robotics, and so on. This paper demonstrates the methodology to construct such a library containing composable and predictable algorithms so that the application-level synthesis tools can utilize it to explore the design space for an entire application. Specifically, in this paper, we present an algorithm for matrix decomposition, several mapping strategies for selected kernel functions, an algorithm to construct the mapping of each matrix-matrix multiplication, and finally, the method to calculate the cost estimation of each solution.

Keywords

• Coarse grain reconfigurable architecture
• field programmable gate array (FPGA)
• dynamically reconfigurable resource array (DRRA)
• distributed memory architecture (DiMArch)
• matrix multiplication
• high-level synthesis