An α-approximate algorithm for delay-constraint technology mapping

Variants of delay-cost functions have been used in a class of technology mapping algorithms. We illustrate that in an industrial environment the delay-cost function can grow unboundedly and lead to very large runtimes. The key contribution of this work is a novel bounded compression algorithm. We introduce a concept of α delay-cost curve, (α-DC-curve) that requires up to exponentially less delay-cost points to be stored compared to that stored by the delay function. We prove that the solution obtained by this exponential compaction of the delay-function is bounded to α% of the optimal solution. We also suggest a large set of CAD applications which may benefit from using α-DC-curve. Finally, we demonstrate the effectiveness of our compaction scheme on one such application, namely technology mapping for low power. Experimental results on industrial environment show that we are more than 17 times faster than on certain MCNC circuit