Using Transposition to Efficiently Solve Constant Matrix-Vector Multiplication and Sum of Product Problems
- PDF / 1,534,137 Bytes
- 15 Pages / 595.224 x 790.955 pts Page_size
- 52 Downloads / 161 Views
Using Transposition to Efficiently Solve Constant Matrix-Vector Multiplication and Sum of Product Problems Narges Mohammadi Sarband1
· Oscar Gustafsson1 · Mario Garrido1
Received: 30 April 2019 / Revised: 30 December 2019 / Accepted: 26 May 2020 © The Author(s) 2020
Abstract In this work, we present an approach to alleviate the potential benefit of adder graph algorithms by solving the transposed form of the problem and then transposing the solution. The key contribution is a systematic way to obtain the transposed realization with a minimum number of cascaded adders subject to the input realization. In this way, wide and low constant matrix multiplication problems, with sum of products as a special case, which are normally exceptionally time consuming to solve using adder graph algorithms, can be solved by first transposing the matrix and then transposing the solution. Examples show that while the relation between the adder depth of the solution to the transposed problem and the original problem is not straightforward, there are many cases where the reduction in adder cost will more than compensate for the potential increase in adder depth and result in implementations with reduced power consumption compared to using sub-expression sharing algorithms, which can both solve the original problem directly in reasonable time and guarantee a minimum adder depth. Keywords Constant matrix multiplication (CMM) · Multiple constant multiplication (MCM) · Shift-and-add · Sum of products (SOP) · Minimum depth expansion algorithm.
1 Introduction In many applications, primarily within the field of digital signal processing (DSP), computations are performed with constant coefficient multiplication. Hence, one may replace the general multiplier with a network of adders, subtracters, and shifts [1, 2]. The computations may have a different number of inputs and outputs and allow to reduce the number of adders and subtracters by utilizing common partial results. The general case, supporting multiple inputs and outputs is constant matrix multiplication (CMM). This is the multiplication of a M × N constant matrix C, by a column vector I of dimension N that results a column vector O of dimension M, in which M is the number of rows and N is the
Narges Mohammadi Sarband
[email protected] Oscar Gustafsson [email protected] Mario Garrido [email protected] 1
Department of Electrical Engineering, Link¨oping University, Link¨oping, Sweden
number of columns of the constant matrix C, O = CI or on element form ⎤ ⎡ C1,1 C1,2 O1 ⎢ O2 ⎥ ⎢ C2,1 C2,2 ⎥ ⎢ ⎢ ⎢ .. ⎥ = ⎢ .. .. ⎣ . ⎦ ⎣ . . CM,1 CM,2 OM ⎡
⎤ ⎡ ⎤ I1 . . . C1,N ⎢ I2 ⎥ . . . C2,N ⎥ ⎥ ⎢ ⎥ .. ⎥ × ⎢ .. ⎥ .. . . ⎦ ⎣ . ⎦ . . . CM,N IN
(1)
The CMM problem is defined as finding a solution using adders, subtracters, and shifts that realizes the computation using a few adders and subtracters as possible [1–7]. As adders and subtracters have about the same complexity, we will from here refer to both as adders, and the number of adders as the adder cost. When the n
Data Loading...
