Optimization of Constant Matrix Multiplication with Low Power and High Throughput
Authors:
- 4 May 2017
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 66 (12) , 2072-2080
Abstract
Constant matrix multiplication (CMM), i.e., the multiplication of a constant matrix with a vector, is a common operation in digital signal processing. It is a generalization of multiple constant multiplication (MCM) where a single variable is multiplied by a constant vector. Like MCM, CMM can be reduced to additions/subtractions and bit shifts. Finding a circuit with minimal number of add/subtract operations is known as the CMM problem. While this leads to a reduction in circuit area it may be less efficient for power consumption or throughput. It is well studied for the MCM problem that a) reducing the adder depth (AD) leads to a reduced power consumption and b) pipeline resources have to be considered during optimization to enhance throughput without wasting area. This paper addresses the optimization of CMM circuits which considers both adder depth and pipelining for the first time. For that, a heuristic is proposed which evaluates the most attractive graph topologies. It is shown that the proposed method requires 12.5% less adders with min. AD and 38.5% less pipelined operations. Synthesis results for recent FPGAs show that these reductions also translate to superior results in terms of delay and power consumption compared to the state-of-the-art.Keywords
This publication has 36 references indexed in Scilit:
- Combination of constant matrix multiplication and gate-level approaches for area and power efficient hybrid radix-2 DIT FFT realization2011
- Optimization of Area and Delay at Gate-Level in Multiple Constant Multiplications2010
- Lower Bounds for Constant Multiplication ProblemsIEEE Transactions on Circuits and Systems II: Express Briefs, 2007
- Multiplierless multiple constant multiplicationACM Transactions on Algorithms, 2007
- Optimisation of Constant Matrix Multiplication Operation Hardware Using a Genetic Algorithm2006
- Some Optimizations of Hardware Multiplication by Constant MatricesIEEE Transactions on Computers, 2005
- Low-complexity transform and quantization in H.264/AVCIEEE Transactions on Circuits and Systems for Video Technology, 2003
- A new algorithm for elimination of common subexpressionsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1999
- Multiple constant multiplications: efficient and versatile framework and algorithms for exploring common subexpression eliminationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1996
- Computation of the Fast Walsh-Fourier TransformIEEE Transactions on Computers, 1969