DocumentCode
523989
Title
A novel optimal single constant multiplication algorithm
Author
Thong, Jason ; Nicolici, Nicola
Author_Institution
Electr. & Comput. Eng., McMaster Univ., Hamilton, ON, Canada
fYear
2010
fDate
13-18 June 2010
Firstpage
613
Lastpage
616
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Design Automation Conference (DAC), 2010 47th ACM/IEEE
Conference_Location
Anaheim, CA
ISSN
0738-100X
Print_ISBN
978-1-4244-6677-1
Type
conf
Filename
5523542
Link To Document