NDLI: Depth controlled symmetric function fanin tree restructure

Content Provider	IEEE Xplore Digital Library
Author	Hua Xiang Reddy, L. Trevillyan, L. Puri, R.
Copyright Year	2013
Description	Author affiliation: IBM T.J. Watson Res. Center, Yorktown Heights, NY, USA (Hua Xiang; Trevillyan, L.; Puri, R.) \|\| IBM Syst. & Technol. Group, Yorktown Heights, NY, USA (Reddy, L.)
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.
Sponsorship	IEEE Counc. Electron. Design Autom.
Starting Page	585
Ending Page	591
File Size	894910
Page Count	7
File Format	PDF
ISBN	9781479910717
ISSN	10923152
DOI	10.1109/ICCAD.2013.6691176
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-11-18
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Logic gates Vegetation Timing Steiner trees Clustering algorithms Partitioning algorithms Algorithm design and analysis
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Computer Science Applications Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Depth controlled symmetric function fanin tree restructure

Obstacle-avoiding rectilinear Steiner tree construction based on Steiner point selection

Congestion aware layout driven logic synthesis

Interconnect resource-aware placement for hierarchical FPGAs

Algorithms for MIS Vector Generation and Pruning

Multiple tunable constant multiplications: Algorithms and applications

FOARS: FLUTE Based Obstacle-Avoiding Rectilinear Steiner Tree Construction

Free space management for cut-based placement [IC layout]

Timing-driven partitioning for two-phase domino and mixed static/domino implementations

Depth controlled symmetric function fanin tree restructure

Similar Documents

Depth controlled symmetric function fanin tree restructure

Obstacle-avoiding rectilinear Steiner tree construction based on Steiner point selection

Congestion aware layout driven logic synthesis

Interconnect resource-aware placement for hierarchical FPGAs

Algorithms for MIS Vector Generation and Pruning

Multiple tunable constant multiplications: Algorithms and applications

FOARS: FLUTE Based Obstacle-Avoiding Rectilinear Steiner Tree Construction

Free space management for cut-based placement [IC layout]

Timing-driven partitioning for two-phase domino and mixed static/domino implementations

Depth controlled symmetric function fanin tree restructure