Congestion-Aware Logic Synthesis

Congestion-Aware Logic Synthesis

• In Deep Sub-Micron (DSM) technologies, interconnects play a crucial role in the overall performance of VLSI systems.
• Interconnect capacitance becomes dominant with respect to gate capacitance, rapidly increasing the interconnect delay.
• Wireload models used in timing-driven layout tools are inaccurate, and estimation based on fanout and design legacy statistics can be highly inaccurate.
• Wiring congestion is an extremely important design factor and should be considered at the earliest possible stages of the design flow.

Limitations of Wireload Models

• Wireload models often yield results that are significantly different from actual post-layout values.
• Many iterations between logic synthesis and physical design are necessary to achieve timing closure.
• Commercial approaches from EDA vendors have attempted to combine logic synthesis and placement in an iterative procedure or apply resynthesis during physical design.

Problem of Congestion Minimization

• Congestion minimization is a difficult problem since it depends on the structure of the gate-level netlist and the amount of routing resources available.
• Traditional synthesis does not address routability, and the problem of predicting the impact of interconnect on delay and area prior to physical design remains unsolved.

Approach to Congestion-Aware Logic Synthesis

• The objective is to synthesize structurally routable netlists that satisfy the constraints on total block area and meet other performance constraints such as timing.
• The approach involves exploring trade-offs between area (and/or delay) and congestion minimization when a fixed amount of routing resources are available.

Previous Work

• Significant progress has been made to provide logic synthesis with physical information to overcome the limitations of the wireload model.
• Previous work integrates technology mapping with a companion placement to generate trade-offs for area (and/or delay) minimization.### TOO_LARGE Benchmark
• TOO_LARGE is a benchmark used for phase partitioning
• It consists of 27,977 base gates (two-input NANDs and inverters)
• The Register-Transfer-Level (RTL) description of the circuit was synthesized by the logic synthesis tool SIS
• The RTL description was then mapped onto the CORELIB8DHS 2.0 technology independent representation

Placement-Driven DAG Partitioning

• The network DAG is partitioned into a forest of trees
• A matching algorithm identifies all possible matches corresponding to instances of a cell library for each tree
• During the covering phase, an optimal choice is selected according to some cost factor
• Physical information is included in the DAG partitioning and covering steps
• Technology independent network is placed to capture the connectivity on a chip layout image

Placement Results

• The results show that SIS yields the best result in terms of area minimization
• DAGON, which is a technology mapping program, is limited by the initial structure of the technology independent netlist
• The netlist obtained with SIS has less area utilization with respect to the netlist obtained with DAGON
• However, the netlist mapped with DAGON can be routed successfully in the same block area

Our Approach: Congestion-Aware Technology Mapping

• The objective is to produce a circuit which implements a set of logic equations, occupies minimum Si area, and satisfies performance constraints
• Modern logic synthesis systems divide this task into two phases: technology independent optimization and technology mapping
• The first phase is based on the RTL description of the circuit
• The second phase is based on the mapped gate level netlist

Placement-Driven DAG Partitioning Algorithm

• The algorithm is based on a Depth First Search (DFS) traversal from the circuit primary outputs to the primary inputs
• It takes into account physical location of the corresponding base gates obtained from the technology independent placement
• Partitioning is based on the property that the father of every internal vertex is always the nearest vertex on the chip layout image according to some distance metric

Congestion-Aware Tree Covering

• The tree covering step can be optimally solved in linear time with the size of the tree by means of a dynamic programming algorithm

• The basic structure of the covering algorithm does not significantly change, and the main difference lies in the optimization objective expressed by the cost function

• By modifying the cost function, different optimization targets can be addressed### Congestion Minimization in Technology Mapping

• The goal of congestion minimization is to reduce the number of routing violations and improve the overall routability of a circuit.

Dynamic Programming Algorithm

• The algorithm performs its choices based on a cost function that minimizes area.
• The cost function can be modified to include interconnection length for congestion minimization, but this may lead to sub-optimal solutions with respect to minimum cell area.

Impact of Wires on Cost Function

• The impact of wires on the cost function depends directly on their length, which is influenced by initial floorplan constraints, such as chip or block size.
• The absolute length of interconnections changes when the size of the layout image changes, affecting the wire cost during technology mapping.

Technology Mapping Tool

• A prototype technology mapping tool was implemented, which addresses typical optimization objectives, such as area and/or delay.
• The tool includes congestion minimization as an objective, controlled by the congestion minimization factor K.

Experimental Results

• The experimental results show that as K increases, the impact of congestion minimization on the cost function becomes more significant, leading to a trade-off between cell area and routability.
• The results also demonstrate that congestion minimization can improve timing, as it reduces the total wire length.

Benchmark Circuits

• The benchmark circuits used in the experiments were SPLA and PDC, with sizes of 22,834 and 23,058 base gates, respectively.
• The results show that even with a block size limit of 50,000 gates, wire congestion cannot be neglected.

Comparison with Other Methods

• The results were compared with DAGON (K = 0.0) and SIS, showing that the proposed approach can improve congestion and routability while reducing the total chip area.

Proposed Methodology

• The approach can be integrated into the traditional design flow, starting with a technology-independent netlist and its initial placement.
• The congestion minimization factor K is increased until a congestion map is acceptable, and then physical design can be carried out.

Advantages of the Approach

• The approach can efficiently generate solutions with less congestion, reducing the need for detailed place&route, which is computationally expensive.
• The congestion map can be quickly evaluated, and the final placement and routing can be executed when the designer is satisfied with the congestion map.