Using Transposition to Efficiently Solve Constant Matrix-Vector Multiplication and Sum of Product Problems
| Autor: | Mario Garrido, Oscar Gustafsson, Narges Mohammadi Sarband |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
010302 applied physics
Adder Computer science Transposition (telecommunications) Canonical normal form Signalbehandling 02 engineering and technology 01 natural sciences Matrix multiplication 020202 computer hardware & architecture Theoretical Computer Science Reduction (complexity) Matrix (mathematics) Hardware and Architecture Control and Systems Engineering Modeling and Simulation 0103 physical sciences Signal Processing 0202 electrical engineering electronic engineering information engineering Constant matrix multiplication (CMM) Multiple constant multiplication (MCM) Shift-and-add Sum of products (SOP) Minimum depth expansion algorithm Arithmetic Hardware_ARITHMETICANDLOGICSTRUCTURES Constant (mathematics) Realization (systems) Information Systems |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|