Physical Design: Methodologies and Developments

A 2021 research by Dmitry Bulakh et al. published at the International Seminar on Electron Devices Design and Production was aimed at developing a Graphical User Interface (GUI) to visualize, control and interpret the various stages of Physical Design. The framework was developed in C++ using a few inherited classes from a cross-platform Qt library. Some .hpp, .dll and lib files can been provided as input along with layer map files, and the framework would then render a GDSII file as output.[17]

The main steps in Physical Design flow are:

• •

  Post-synthesis Netlist Optimization

• •

  Floor Planning

• •

  Power Planning

• •

  Placement (Pre-CTS)

• •

  Clock Tree Synthesis (CTS)

• •

  Routing

• •

  Post Route Timing Optimization

• •

  Physical Verification

.

.

As the name suggests Floor Planning helps create a skeletal level framework for spatial locations of standard cells, macros, analog IPs and all other blocks on a circuit. The goal is to optimize design layout on the given die area while keeping close tabs on probable congestion and density violations. Typically floor planning is done to make the layout compact wherein logically connected instances are placed in close proximity to each other as well as everything else. This is done to make effective use of the routing resources available.

Goals for Floor Planning:

• •

  Minimize the total chip area and dead space

• •

  Minimize total wire length

• •

  Minimize Interconnection complexity

• •

  Improve the performance by minimize delay

Naushad Manzoor Laskar et al. have documented a comprehensive study of all the prominent Floorplan Representations and the means of achieving them in their 2015 publication titled ”A Survey on VLSI Floorplanning: Its Representation and Modern Approaches of Optimization”. This detailed research covers all aspects of floorplan and floorplanning algorithms starting with all different ways of denoting a floorplan.[18] Different ways of representing a floor plan are as follows:

• •

  Polish
  Polish notation is widely used in the world of computing to read and express logic embedded in data structures, but most prominently binary trees in the form of equations. Such a notation is used to read the information conveyed by the sliced up floorplan binary tree in post-fix form.

  

• •

  Sequence Pair

• •

  Bounded Slicing Grid (BSG)

• •

  TCG

• •

  O-Tree
  The O-Tree algorithm is one of the least computationally expensive algorithms with a complexity of O(n). It is a local-search algorithms and hence deterministic by nature. Being deterministic means that this algorithm will try to optimize the layout on the basis of immediate short term solutions in contrast to a few greedy algorithms which are a bit more experimental in their approach and tend to be better at optimizing. Despite being one of the most computationally efficient algorithm, O-Tree based approach may not always find the best possible solution owing to its deterministic nature. A research done in 2005 by Maolin Tang and Alvin Sebastian addresses this very issue and proposes a more greedy Genetic Algorithm (GA) to optimize Floor Plan based on O-Tree representation.[19]

• •

  B* Tree
  Similar to O-Tree, the B* algorithm showcases a computational complexity of O(n). It is widely regarded as one of the most efficient and flexible Floor Plan notations to optimize upon. It makes use of ordered weighted binary tree, the root of which is located at the bottom left corner of the placement area at the coordinate (0,0).Once the root is fixed, the rest of the tree is built recursively, first populating the left branch and then the right.

.
Optimization
Once the initial Floorplan notation is decided upon, then begins the process of optimizing the layout to have the smallest area with the most optimum core utilization. [18]

• •

  Simulated Annealing
  Simulated Annealing is the oldest Floorplanning algorithm and has been extensively used over the years. It can be used effectively with slicing as well as compacted notations like Polish, B*Tree etc. This algorithm can converge to a fairly optimal solution but is irregular in doing so. In modern day, this algorithm is used as a preliminary benchmark for researchers to test newer algorithms on.[18]

• •

  Genetic Algorithm
  Soon after the success of Simulated Annealing algorithm, the Genetic Algorithm (GA) was developed. GA optimization begins with arbitrary placement of blocks on the pre-defined die area. The Cost Function of this initial floorplan is calculated using some distance metrics. Then any two of the blocks are spatially swapped and a new revised cost function is deduced. This is then compared with the initial value and a decision is made whether the swapping has affected the layout positively or adversely. This process is recursively carried out until the most optimum value is obtained for the cost function.[18]

• •

  Partical Swarm Optimization (PSO)
  In PSO, each block is treated as an individual entity with the same weight. The premise of this algorithm is to spatially change the position of these individual blocks so as each block determines its own best position with respect to its nearest neighbours in the design. A research published in 2019 by S.B.Vinay Kumar et al. proposed an Adaptive PSO model which tunes the PSO model further by adding a weight factor to the block. All blocks are defined weight values at the initial stage. Over successive iterations as the block gets closer and closer to determining its optimum posititon, its weight and hence priority for optimization keeps on reducing. So all blocks will start with a high inertia value and end at a smaller value towards the completion of the optimization process. Such an adaptive architecture is more likely to give better results than GA and traditional PSO models, as claimed by the study.[20]

As all the above discussed algorithms point out, optimization is a recursive process and hence may take up a lot of time to converge on an optimal floorplan. To reduce the time taken by traditional floorplan algorithms, Yanling Zhou et al. have proposed a quicker floorplanning method which involves breaking the full initial netlist into smaller parts and carrying out floorplanning for each individual sub-netlist in a parallel threaded manner thereby saving time on converging to the optimal floorplan.[21]

As discussed earlier, floor plan lays out a framework for the physical design to be built upon. While the process of defining a floor plan may be entirely different for designs with different level of heirarchies, there are a few common fields to be defined to ensure an efficient design layout. To begin with, floor plan defines the block dimensions thereby setting the die area. To make optimum use of this die area, it is critical to identify all the logic, IPs, macros, I/Os and memories which need to be placed in the design. For placement of all the aforementioned components, floor plan should take into account the possibility of cell density issues or routing congestion that may arise owing to poor or incorrect placement. The designer should also aim to make the layout compact so as to use routing resources efficiently as well as to avoid wastage of die area. Core area utilization should also be taken into account while define floor plan. Most industries target 60-70% initial core utilization to generate margin for timing optimization at a later stage. A compact floor plan presents a few advantages related to speed of operation of the chip, reason being, the more compact our design, closer will be the placement of on-chip components, lesser will be the routing resources used, lesser will be the interconnect length and subsequent net delay, thereby reducing net latency and increasing the speed of operations. This gives rise to an active trade-off between speed of design and resulting routing congestion.

Common steps panning the Floor Plan stage include:

• •

  Partitioning

• •

  Defining Block Dimensions

• •

  Pin Placement

• •

  Adding Decap, Tap and End Cap cells

  

• •

  Macro Placement

• •

  Adding Routing and Placement blockages

• •

  Adding IO buffers

Power Planning is the process involving power grid creation to facilitate equal distribution of energy to all parts of the design.

What creates the Power Grid? There are 3 levels of power distribution involved:

1. Rings: Carries VDD and VSS around the chip

2. Stripes: Carry VDD and VSS from the Rings around the chip

3. Rails: Connect VDD and VSS from chip level to standard cell level

Steps involved in this stage:

• •

  Width, pitch and offset dimensions of power stripes wrt each metal layer in accordance with provided metal stack.

• •

  Block and I/O Power connection at top level using power rings, bumps and stripes.

• •

  PG connection at standard cell and block level via power rails.

Power Planning is a very critical stage in Physical Design as it defines the Power/Ground mesh for any layout. The mesh needs to be built considering power requirement for all pins and macros in the design ; standard cell placement and the possibilty of congestion or high IR drop must also be taken into consideration while doing power and bump planning for any design. Any high voltage drop in the layout caused by EM/IR imbalance may cause circuital failure. Zhu Qing et al. in their publication titled ”Simulation and Planning Method for On-Chip Power Distribution – An Industry Perspective” have studied the different parameters affecting power distribution and have come up with a set of steps to be followed while power planning to minimize the chances of fatal voltage drop across the design.[22] The proposed steps are as follows:

• •

  Categorize all standard cells in the design into one of the two groups: those giving rise to severe IR drop and those with nominal IR drop.

• •

  Based on the IR drop metrics obtained in the previous step, draw a schematic for the power grid, with the horizontal and vertical layers being represented by a metal resistor. Compute the total RC parasitic offered by this schematic grid arrangement. For better accuracy, we may even include via parasitics in the calculation.

  

• •

  Add a current source to each cell of the mesh, to compute the magnitude of switching current originating from that cell.

• •

  The RC parasitic and switching current information thus obtained is used to calculate dynamic power dissipation for the schematic.

• •

  If the Power dissipation numbers are below a pre-defined threshold, we can realize the schematic grid using VDD and VSS stripes.

Researchers have also tried integrating Power Planning into the Floor Planning stage thereby letting the optimizing algorithms to optimize the floor plan while taking into consideration the parallel creation of an apt power mesh.[23,24] Shuo Zhou et al. have documented the integration of power planning with the Bounded Slicing Grid (BSG) floorplan representation as early as the year 2001. The proposed algorithm was aimed to complete the two planning stages simultaneously on a BSG representation with a view to optimize placement area and power resources.[23] Han Liying et al. in the year 2009 have documented an integrated power and floor planning algortihm based on the Genetic Algorithm (GA) method of optimization.

Based on the ground-work defined in Floor Plan stage, the objective of Placement stage is to optimize timing and routing within the design. Timing for any block is a function of the cell and net delay between all logically connected paths in the design. Cell delay is a property of the cell. By manipulating the VT flavor of an instance, its cell delay can be changed. Lower the Voltage Threshold (VT), lower the cell delay for the instance. Net delay on the other hand, is a function of the parasitics corresponding to interconnects in the design. These RC Parasitics either be derived from Wire Load Models (WLMs) which are in the form of look-up tables provided by the foundry or from Virtual Route (VR) parameters. Virtual Route model tends to provide more accurate parasitic extraction than WLM models leading to more refined timing calculations.

Need for placement:

Key factor in determining performance of the circuit: As it indirectly dictates the routing length of wires, it plays a role in determining the delay associated with each wire.

Determines routing ability of the design: A well placed design will have no problems with routing.

Decides distribution of heat on the die surface ; uneven temperature profiles can lead to reliability and timing issues Power consumption also gets affected by placement

Goal for placement stage:

• optimize routing resources

• optimize die utilization

• reduce routing congestion and hotspots

Once all the core logic has been placed during the previous stage, we start building paths for transmission of clock signal throughout the block. Clock Tree Synthesis is a very critical process owing to the numerous functional failures that may arise out of incorrectly built clock architectures. Misalignment in clock paths may cause setbacks such as failure to meet timing and skews, false outputs, data corruption or even chip-failure. CTS involves building of accurate clock paths and addition of buffers to balance these clock paths by minimizing clock skew. These addition of buffers also aids in reducing hold slack value. At the timing of defining clock tree, signal is derived from source clock for the block and traversed across numerous splits in the tree to ultimately reach the CK pins of flops. If any of these CK endpoint pins are defined to be ’Don’t touch’ or ’ignore pins’, then they are bypassed during clock tree synthesis. Alternatively if any pin is defined to be a ’through pin’, it is assumed that the clock path is already built and signal input to the pin is provided.

Types of skews:

• Global skew achieves zero skew between two synchronous pins without considering logic relationship.

• Local skew achieves zero skew between two synchronous pins while considering logic relationship.

• If clock is skewed intentionally to improve setup slack then it is known as useful skew.

.
Inputs to CTS stage:

• •

  Placement Data

• •

  Clock Specification File

  • –

    Maximum and Minimum insertion delay

  • –

    Target Skew

  • –

    Maximum transition value

  • –

    Non Default Rules (NDR)

  • –

    Auto CTS root pin

  • –

    Preferred metal layers for clock

  • –

    Type of buffers

  • –

    Latency

  • –

    Maximum fanout

  • –

    Maximum capacitance value , etc.

.
Steps involved in CTS:

• •

  Synthesize the Clock Tree

• •

  Optimize the Clock tree. This is done by

  • –

    Buffer relocation

  • –

    Buffer sizing

  • –

    Gate relocation

  • –

    Gate sizing

  • –

    Improve skew

  • –

    Delay insertion

• •

  Perform inter-clock balancing

  • –

    Between 2 flip flop delay balancing has to be done

  • –

    Clock group between which balancing has to be specified

While working on lower process nodes, it is observed that with the increase in sequential logic coupled with shorter and more dominant wire delays, it becomes increasingly complex and critical to balance clock skew. While building clock architecture, we generally have a source clock which distributes clock signal throughout the block via clock nets defined using CTS root pins. Clock specifications like max_capacitance, max_transition constraints along with max and/or min insertion delays are defined for every root pin and are thus implemented across all clock nets originating from the pin. Guirong Wu et al. in the year 2009, have proposed a more efficient clock splitting methodology to build better clock architectures. The proposed methodology talks about splitting the main source clock into multiple pseudo clock sources at transistor level based on the number of fanouts for every split. This would ultimately help with DRVs as well owing to the split distribution of fanouts, along with more balanced clock skew.[25]

Siong Kiong Teng et al. have proposed another ”Regional Clock-Splitting” methodology in their 2010 publication titled ”Regional Clock Gate Splitting Algorithm for Clock Tree Synthesis”.[26] The said methodology involves the following steps:

• •

  Clock Gate Marking
  Upon placement of standard cells, macros and other physical cells in the layout, all Clock Gating (asynchronous) cells are identified. Each of these Clock Gating (CG) cells are allotted a bounding box that encompasses all direct fanouts related to that cell. This bounding box is demarcated to compare the skews across clock nets affiliated to each of these cells. Simply put, a larger bounding box area implies that the fanouts are located farther away from the CG cell thereby drawing additional interconnect wire length and giving rise to higher skew.

• •

  Clock Gate Splitting
  In the event where any CG cell is associated with any setup violations along with the area encompassed by the corresponding bounding box being greater than a pre-defined threshold, the clock gate cell will undergo splitting. While splitting, the bounding box will split at half the original length in its dominant direction i.e if any bounding box is horizontally oriented, it will split at X/2 distance keeping its Y metric stable, and vice-versa. This splitting is recursively carried out until bounding box area meets the threshold criteria defined earlier. Once such a stage is achieved, the parent clock gate will split ’n’ times, where ’n’ is the number of times the corresponding bounding box had split in order to meet threshold. The study claims to have achieved reduced post-split insertion delay along with a robust clock architecture with balanced skews.[26]

The Physical Design flow should have completed placement of standard cells, IPs, macros, physical cells and built the entire clock architecture before going for routing. Simply put, routing provides net or wire connectivity between all instances on the layout. Routing creates a grid for transmission of all signals throughout the design. Hence the interconnect nets it creates are also called ”signal nets”. Similarly CTS stage creates ”clock nets” and Power Planning generates ”power nets”. The aim of routing is to facilitate appropriate connectivity between instances in the design in accordance with the metal stack approved by industry, while also trying to optimize design with respect to possible congestion hotspots. There are two stages within routing methodology:

• •

  Global Routing
  Global Routing, also called Early Routing in some cases is the stage wherein routing metal is allocated to appropriate layers along with channel track alignment. It helps build a general topology for the resources to be used during Detailed Routing.

• •

  Detailed Routing
  Detailed Routing, also known as Nano Route in some cases makes use of the foundation laid down by Early routing, to actually route all interconnects in the design. Detailed routing weighs the trade-off between conservation of routing resources and LPA congestions, and optimizes its function accordingly. DFM and congestion checks are carried out for the same purpose.

Hao Tang et al. have published a comprehensive survey on the Steiner Tree Algorithm for Global Routing in their 2020 research work titled ”A Survey on Steiner Tree Construction and Global Routing for VLSI Design”. Steiner Tree is an extension of the Minimum Spanning Tree problem that is commonly used in processing methodologies. The objective of this algorithm is to optimize the routing graph or network to have minimum traversal cost. All vertices in the said graph that constitute the minimum cost tree are referred to as ”demand points”. All such demand points are connected via horizontal and vertical lines on a mesh referred to as the ”underlying graph”.[27,28]

The 1-Steiner optimization is further implemented on these underlying graphs, wherein a few common points are identified as ”1-Steiner Points”. These 1-Steiner points is chosen such as to minimize the routing distance (horizontal and vertical) between the dominant points.[28]

Just like the Steiner Tree algorithm, other minimum distance algorithms like PRIM, Bounded PRIM, Bounded Radius Spanning Tree have also been implemented to optimize routing for a layout.[28] .
Inputs to Routing stage:

• •

  Netlist with location of blocks and location of pins (after CTS has been completed)

• •

  Timing budget for critical net

• •

  Technology File

• •

  TLU+ File (Commonly included along with the Technology File .tf)

• •

  SDC

.
Checklist before Routing:

• •

  Placement completed

• •

  CTS completed

• •

  Power and ground nets routed

• •

  Estimated congestion is acceptable

• •

  Estimated Timing – acceptable (  0 ns slack )

• •

  Estimated max cap/trans – no violations

Routing Congestion: When designing chips on lower process nodes and critical utilization factors, it just may happen that routing resources would get crowded in a certain area. Such congestions may have been caused due to lack of routing resources or tracks or simply lack of adequate area to establish the routes. This is a common cause for Density-related DRCs and even EM-IR failures on-chip.

Physical verification is a process whereby complete Layout design is verified via EDA software tools to ensure correct logical functionality and manufacturability

Physical Verification involves the following validation checks:

• •

  Design Rule Check
  DRCs are of two kinds: Base DRCs and Metal layer DRCs ; of which Base DRCs need to be cleared in the floorplan or placement stage of the flow. These may include placement legalization issues, track misalignment violations, density and utilization requirements not being met, incorrect instance orientation and physical cell violations. Metal layer DRCs on the other hand can be cleared in the Post-Route database as well. These issues range from overlapping vias to metal shorts to even minimum spacing violations between instances and nets.

• •

  Layout versus Schematic
  In this process, the final streamout layout GDS is compared against the golden schematic netlist to check for any mismatches or missing instances. All connectivity issues (i.e opens and shorts) are also checked and fixed during cleaning LVS for a design.

• •

  Antenna Check

• •

  Electrical Rule Check