Logic decomposition algorithms for the timing optimization of multi-level logic

Novel fast decomposition algorithms that rely on precise linear models for gate delays are presented. Within the limits of the models, the algorithm performs locally optimal m-way balanced and unbalanced decompositions of logic gates to achieve a maximal timing gain. The decompositions take the output load into account and are characterized by a near-minimal area increase. The models were applied successfully to industrial standard cell and gate array libraries and the algorithms were integrated into a commercial technology mapping software package. Experimental results show that the speed improvement obtained by the m-way algorithms is nearly twice that resulting from optimal two-way decomposition