Browse Prior Art Database

Timing Aware Fan-in Tree Re-Synthesis

IP.com Disclosure Number: IPCOM000224844D
Publication Date: 2013-Jan-08
Document File: 2 page(s) / 45K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed are algorithms to identify and to restructure SFFTs during physical design. The proposed tree-restructuring algorithm uses existing placement information to rebuild the SFFTs with improved timing.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 58% of the total text.

Page 01 of 2

Timing Aware Fan-in Tree Re-Synthesis

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. 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.

A previous work is to re-build the tree for shorter wirelength. However, that approach is based on Steiner-Tree, and may increase the tree levels significantly and make the timing worse.

This invention proposes algorithms to identify and to restructure SFFTs during physical design. The proposed tree-restructuring algorithm uses existing placement information to rebuild the SFFTs with improved timing.

Different from the previous Steiner-tree based approaches, the invented approach builds SFFTs level by level from bottom to top. In this way, the tree height is constrained, and the delay from a tree leaf to the tree root can be well controlled. A new partition algorithm is developed to group inputs at each level such that each group corresponds to one commutative gate. In addition, various optimization techniques, such as gate merging, gate promotion, and direct upper level connection, are deve...