Depth controlled symmetric function fanin tree restructure

Abstract

A symmetric-function fanin tree (SFFT) is a fanout-free cone of logic that computes a symmetric function such as AND, OR and XOR. These trees are usually created during logic synthesis, when there is no knowledge of the tree gate locations. Because of this, large SFFTs present a challenge to placement algorithms. The consequence is that the tree placements are generally far from optimal, leading to wiring congestion, excess buffering, and timing problems. [10] proposed a fanin-tree restructure algorithm to reduce the SFFT wirelength. However, [10] was based on Steiner trees and might cause serious timing problems due to the high Steiner tree depth. In this paper, we extend the SFFT tree identification algorithm to allow both positive and negative tree inputs. Contrary to the Steiner-tree based approach, we propose a new tree restructure flow to build SFFTs from bottom to top level by level at the physical design stage. The tree restructure algorithm is in a transaction mode so that only improved trees are accepted, and the new tree won't cause any placement legal issue. A new partitioning algorithm is proposed to serve for gate creation. In addition, various optimization techniques are developed to reduce tree wirelength On tested designs, the total tree wirelength is reduced by 31% with similar tree gates and tree depths. © 2013 IEEE.