A new reasoning scheme for efficient redundancy addition and removal

TitleA new reasoning scheme for efficient redundancy addition and removal
Publication TypeJournal Article
Year of Publication2003
AuthorsChang, C-W, Hsiao, M-F, Marek-Sadowska, M
JournalComputer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Pagination945 - 951
Date Publishedjuly
Keywordsalternative wire identification, Boolean network, circuit optimisation, combinational circuits, combinational logic restructuring, directed acyclic graph, directed graphs, incremental logic restructuring, logic design, logic testing, network topology, physical synthesis, RAMFIRE, reasoning scheme, redundancy, redundancy addition, redundancy removal, redundant alternative wire, rewiring technique, target wire, timing, timing optimization
AbstractRedundancy addition and removal is a rewiring technique which, for a given target wire wt, finds a redundant alternative wire wa. The addition of wa makes wt redundant and, hence, removable without changing the overall circuit functionality. Incremental logic restructuring based on this technique has been used in many applications. However, in the earlier methods, the search for valid alternative wires required trial-and-error redundancy testing of a potentially large set of candidate wires. Here, we study the fundamental theory behind this technique and propose a new reasoning scheme (RAMFIRE), which directly identifies alternative wires without performing trial-and-error tests. Experimental results show speedup of up to 15 times than that of the best techniques in the literature.