Logical and physical restructuring of fan-in trees

Abstract

A symmetric-function fan-in tree (SFFT) is a fanout-free cone of logic that computes a symmetric function, so that all of the leaf nets in its support set are commutative. Such trees are frequently found in designs, especially when the design originated as two-level logic. These trees are usually created during logic synthesis, when there is no knowledge of the locations of the tree root or of the source gates of the leaf nets. Because of this, large SFFTs present a challenge to placement algorithms. The result is that the tree placements are generally far from optimal, leading to wiring congestion, excess buffering, and timing problems. Restructuring such trees can produce a more placeable and wire-efficient design. In this paper, we propose algorithms to identify and to restructure SFFTs during physical design. The key feature of an SFFT is that it can be implemented with various structures of a uniform set of gates with commutative inputs, i.e. AND, OR, or XOR. Drawing on the flexibility of SFFT logic structures, the proposed tree restructuring algorithm uses existing placement information to rebuild the SFFTs with reduced tree wire lengths. The experimental results demonstrate the efficiency and effectiveness of the algorithms. Copyright 2010 ACM.