Research indexJournal article
A Fast Algorithm for Performance‐Driven Module Implementation Selection
Cheng, Sahni
VLSI design1 Jan 1999Open access
Journal articleOpen access
A Fast Algorithm for Performance‐Driven Module Implementation Selection
Cheng, Sahni · VLSI design · 1999
Abstract
We develop an O ( p log n ) time algorithm to obtain optimal solutions to the p ‐pin n ‐net single channel performance‐driven implementation selection problem in which each module has at most two possible implementations (2‐PDMIS). Although Her, Wang and Wong [1] have also developed an O ( p log n ) algorithm for this problem, experiments indicate that our algorithm is twice as fast on small circuits and up to eleven times as fast on larger circuits. We also develop an O ( p n c −1 ) time algorithm for the c, c > 1, channel version of the 2‐PDMIS problem.