User:Brunasunagai/Placement (electronic design automation)

Placement is an essential step in integrated circuit (IC) design where logic components or standard cells are assigned to allowed positions within the chip's layout area. The primary goal is to optimize metrics such as timing, power consumption, congestion, and routability. Due to the increasing complexity of modern circuits, this step completely relies on electronic design automation (EDA) tools to complete the physical design flow. A poor placement affects the chip's performance, potentially making it non-manufacturable or using excessive wire routing resources. Consequently, this step must fulfill the placing assignment while optimizing several objectives to ensure that a circuit meets its performance demands. Placement is followed by routing, and these steps are often referred to as place and route (PnR), however routing information is not yet available during placement step.

The placement tool takes a synthesized circuit netlist and the technology library to produce a valid layout. Clock tree synthesis and routing follow, completing the main physical design process. In many cases, parts of, or even the entire, physical design flow are repeated multiple times until a design closure is achieved. The layout is verified to ensure that all performance, area, and manufacturability constraints are satisfied before tape-out. As a final result, the GDSII or OASIS file is generated, and the design is sent for fabrication.

Constraints and objectives

Placement is formulated as a constrained optimization problem. From a performance specification, the placer must assign exact spatial coordinates to all components while ensuring that the given constraints are satisfied and the design objectives are optimized.

Placement design constraints

The main constraints considered by the placement tool are:

• Timing constraint (critical path): the clock period of a digital circuit is limited by the delay of the critical path hence the placer must ensure that no path exists with a delay exceeding the maximum specified delay.
• Boundary constraint: all components must be placed within the chip's core area, which was determined in the floorplan step.
• No overlaps: there should not exist any overlap between circuit components.
• Alignment constraint: all standard cells must be placed into predefined spaces, called sites, which are discrete spaces defined by the technology.

Placement optimization objectives

There are usually multiple optimization objectives, including:

• Total wire length: the sum of the lengths of all the wires in the design should be minimized.
• Signal delay: related to wire length, as signal propagation is affected by wire resistance and capacitance.
• Routing congestion: the placement tool must balance local routing demand with the available routing resources. Local congestion metrics can be aggregated in several ways, such as by summing the top 10% of highest local congestion values.
• Power: dynamic switching power depends on wire lengths and signal activity, so the components with higher switching activity have priority to use shorter connections.
• Assignment of I/O pads: the I/O pads are typically assigned during the floorplan step, however during the placement refinement their locations might be adjusted, since it directly affect the routing path between I/O and internal logic blocks.

Additionally to these design requirements, it is important to finish the placement process quickly and efficiently. The tool must be runtime-efficient as this step is repeatedly used in the physical flow.

Total wire length is typically the primary objective of most existing placers and acts as a precursor to other optimizations. Minimizing the routing throughout the circuit design often improves timing and power, however it may cause local congestion. Congested regions may need extra routing detours, increasing delays and wire length itself. Total wire length determines the routing demand and whether it can be satisfied by the routing supply defined by available routing tracks. Therefore, the tool must balance the optimization of total wire length and routing congestion.

Power minimization typically considers wires with greater switching activity factors and assigns greater priority to making them shorter. When many "hot" components are placed nearby, a thermal hot spot may arise and lead to harmful temperature gradients. In such cases, components may be spread out to mitigate temperature gradients.

Placement techniques

The placement step is divided into global placement, legallization, and detailed placement.

• Global placement distributes all the cells to appropriate locations across the global layout area with a focus on optimizing overall density distribution. In this step, it is allowed limited overlaps as it is still a coarse optimization.
• In legalization, the cells are aligned to the row boundaries and power rails. The tool should make sure there are no more overlaps.
• Detailed placement moves each cell to adjust it locally to a legal location (site). These changes cause a very moderate layout change compared to the global placement results.

Placement and overall design quality are most dependent on the global placement performance. Due to runtime limitations (since one IC can have millions of gates), the placement step is usually performed using heuristics algorithms, where a good enough and optimized solution is found to place the standard cells through the layout.

Stochastic placement methods

Early placement techniques for integrated circuits were primarily based on combinatorial optimization, that was suitable for designs up to thousands or tens of thousands of components. Among them, stochastic methods such as simulated annealing, implemented in the early tool called TimberWolf, achieved strong results by randomly moving components to minimize a cost function - typically for wire length or congestion. This method is able to escape local minima, as there is a probability of accepting a worse solution.

Partitioning-based placement methods

As designs grew to millions of components, partitioning-based approaches appeared as a more scalable alternative. Then algorithms that employ minimum-cut placement and hypergraph partitioning emerged, using multilevel nested partitioning frameworks such as Capo. These methods may directly prevent component overlaps but struggle with interconnect optimization at a large scale.

Analytical placement methods

Analytical methods for global placement model the wire length as a continuous optimization problem and minimize this function directly subject to density constraints. These methods run faster and scale better than combinatorial methods, but do not prevent component overlaps and must be post-processed by combinatorial methods for detailed placement later.

Quadratic placement models wire length by a quadratic function and uses high-performance quadratic optimization techniques. When it was developed, it demonstrated a competitive quality of results and also stability, unlike combinatorial methods. GORDIAN formulates the wire length cost as a quadratic function while still spreading cells apart through recursive partitioning. The algorithm models placement density as a linear term in the quadratic cost function and solves the placement problem by pure quadratic programming. A common enhancement is weighting each net by the inverse of its length on the previous iteration. Provided the process converges, this minimizes a linear objective in the wire length. The majority of modern quadratic placers (KraftWerk, FastPlace, SimPL) follow this framework, each with different heuristics on how to determine the linear density force.

Nonlinear placement methods

Nonlinear placement models wire length using exponential (nonlinear) functions and density by local piece-wise quadratic functions, in order to achieve better accuracy thus quality improvement. Follow-up academic work includes APlace and NTUplace, which introduced local density penalties to improve routability and timing. ePlace algorithm spreads cells apart by simulating an electrostatic field and treating the components as charged particles, which minimizes quality overhead, thus achieving good performance.

Machine learning and AI-based placement

Some recent research has started an investigation to integrate AI, particularly reinforcement learning, into the physical design flow. In 2021, Google Brain reported good results from the use of AI for the placement problem, modeling it as a sequential decision making problem and using policy optimization to generate floorplans with improved power, performance, and area. By using this method, the results showed faster turnaround times than traditional tools, for some designs. However, this research received criticism, as the paper does not contain comparisons to other academic placers, and there were difficulties in replicating the experiments. Still, one initially favorable review has been retracted upon further analysis.

Placement for application specifics

In the case of application-specific integrated circuits (ASICs), the chip's core layout area is divided into rows with fixed height, that may have horizontal spacing between them. Each row contains a sequence of discrete sites, which define the allowed positions for placing the circuit components (cells). A site that is not occupied is considered a free site. The circuit components include standard cells, macro blocks, and I/O pads.

The standard cells are designed to match the height of a row, but have variable widths. The width of a cell is an integer multiple of the site widths. In contrast, macro blocks are typically larger than cells and can span more than one row, with variable dimensions that can occupy a multiple number of rows and sites. Some blocks can have preassigned locations — say from a previous floorplanning process — which limit the placer's task to assigning locations for just the cells. In this case, the blocks are typically referred to as fixed blocks. Alternatively, some or all of the blocks may not have preassigned locations. In this case, they have to be placed with the cells in what is commonly referred to as mixed-mode placement.

In addition to ASICs, placement retains its prime importance in gate array structures such as field-programmable gate arrays (FPGAs). Here, prefabricated transistors are typically arranged in rows (or “arrays”) that are separated by routing channels. Placement maps the circuit's subcircuits into programmable FPGA logic blocks in a manner that guarantees the completion of the subsequent stage of routing.

See also

• Electronic design automation
• Design flow (EDA)
• Integrated circuit design
• Floorplan (microelectronics)
• Place and route

Further reading/External links

• IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)
• ACM Transactions on Design Automation of Electronic Systems (TODAES)
• IEEE Transactions on Very Large Scale Integration Systems (TVLSI)