Pipelined adder graph optimization for high speed multiple constant multiplication

• Main Authors: Kumm, Martin, Zipf, Peter, Faust, Mathias, Chang, Chip Hong
• Other Authors: School of Electrical and Electronic Engineering
• Format: Conference or Workshop Item
• Language: English
• Published: 2013
• Subjects: DRNTU::Engineering::Electrical and electronic engineering
• Online Access: https://hdl.handle.net/10356/103747; http://hdl.handle.net/10220/16910
• Institution: Nanyang Technological University

This paper addresses the direct optimization of pipelined adder graphs (PAGs) for high speed multiple constant multiplication (MCM). The optimization opportunities are described and a definition of the pipelined multiple constant multiplication (PMCM) problem is given. It is shown that the PMCM problem is a generalization of the MCM problem with limited adder depth (AD). A novel algorithm to solve the PMCM problem heuristically, called RPAG, is presented. RPAG outperforms previous methods which are based on pipelining the solutions of conventional MCM algorithms. A flexible cost evaluation is used which enables the optimization for FPGA or ASIC targets on high or low abstraction levels. Results for both technologies are given and compared with the most recent methods. Even for the special case of limited AD it is shown that RPAG often produces better results compared to the prominent Hcub algorithm with minimal total AD constraint.