A Common Subexpression Elimination Tree Algorithm

Autor:	Andrew Bainbridge-Smith, Michael H. B. Hayes, Firas Ali Jawad Al-Hasani
Rok vydání:	2013
Předmět:	Tree (data structure) Computational complexity theory Linear programming Multiplication Node (circuits) Common subexpression elimination Partial redundancy elimination Electrical and Electronic Engineering Arithmetic Time complexity Algorithm Mathematics
Zdroj:	IEEE Transactions on Circuits and Systems I: Regular Papers. 60:2389-2400
ISSN:	1558-0806 1549-8328
DOI:	10.1109/tcsi.2013.2244328
Popis:	A common subexpression elimination algorithm is proposed to minimize the complexity of the multiple constant multiplication operation. The coefficients (constants) of the multiple constant multiplication are represented using the binary signed digit number system. The binary signed digit representations of each coefficient are enumerated using the representation tree. The algorithm traverses the tree to calculate the possible subexpressions at each node. Each subexpression is used to find a possible decomposition for the coefficient to be encoded. A complexity formula is proposed to compare the decompositions. The algorithm is designed to prune the tree when it finds a decomposition with minimum complexity. This reduces the search space while minimizing the hardware complexity. Results show that the algorithm has better performance than other published algorithms including linear programming optimization methods. The algorithm outperforms the subexpression sharing method in that uses only the canonical signed-digit representations.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::6ca28f4ecb3f6098a992e64c2f1093fd https://doi.org/10.1109/tcsi.2013.2244328 Zobrazit plný text záznamu