Towards optimal multiple constant multiplication: a hypergraph approach
2008 (English)In: Conference Record of the Asilomar Conference on Signals Systems and Computers, Piscataway, NJ: IEEE , 2008, 1805-1809 p.Conference paper (Refereed)
In this work a novel approach to the multiple constant multiplication problem, i.e., finding a realization of a number of constant multiplications by using shift and addition with a minimum number of additions, is presented. By using a directed hypergraph, the problem comes down to finding a Steiner hypertree in the graph. The proposed formulation can guarantee an optimal solution, given that an optimal Steiner hypertree is found. However, finding a Steiner tree in a hypergraph is an NP-hard problem. Therefore, we present algorithms for different partial problems and discuss how they can be used to solve the whole problem. An integer linear programming model is used to solve the Steiner hypertree problem. The model can also include additional constraints such as adder depth and fan-out.
Place, publisher, year, edition, pages
Piscataway, NJ: IEEE , 2008. 1805-1809 p.
National CategoryEngineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-44137DOI: 10.1109/ACSSC.2008.5074738ISI: 000274551001126Local ID: 75782ISBN: 978-1-4244-2940-0 (print)ISBN: 978-1-4244-2941-7 (online)OAI: oai:DiVA.org:liu-44137DiVA: diva2:264998
42nd Asilomar Conference on Signals, Systems and Computers