Title :
A novel optimal single constant multiplication algorithm
Author :
Thong, Jason ; Nicolici, Nicola
Author_Institution :
Electr. & Comput. Eng., McMaster Univ., Hamilton, ON, Canada
Abstract :
Existing optimal single constant multiplication (SCM) algorithms are limited to 19 bit constants. We propose an exact SCM algorithm. For 32 bit constants, the average run time is under 10 seconds. Optimality is ensured via an exhaustive search. The novelty of our algorithm is in how aggressive pruning is achieved by combining two SCM frameworks.
Keywords :
constants; directed graphs; search problems; aggressive pruning; exhaustive search; optimal single constant multiplication algorithm; word length 19 bit; word length 32 bit; Adders; Algorithm design and analysis; Costs; Digital signal processing; Discrete cosine transforms; Hardware; Logic design; Logic devices; Signal processing algorithms; Silicon; Single constant multiplication; common subexpression elimination; directed acyclic graphs; optimal algorithm;
Conference_Titel :
Design Automation Conference (DAC), 2010 47th ACM/IEEE
Conference_Location :
Anaheim, CA
Print_ISBN :
978-1-4244-6677-1
