License Notice

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with the Invariant Sections being just "License Notice", with no Front-Cover Texts, and with no Back-Cover Texts. A copy of the license is included in the section entitled "GNU Free Documentation License".

Source code

The original source code of this book can be found on codeberg.

Introduction

Physical Design of Silicon Chips

Physical design or physical synthesis starts with a description of the chip on the gate level and turns that description step-by-step into a spacial representation that corresponds almost one-to-one to the piece of silicon that should be manufactured. This book covers the synthesis steps which come after logic synthesis and technology mapping.

For who is this book?

This book is for everybody interested in building software for the physical design of silicon chips. In order to build such software it is helpful to have a basic understanding of how silicon chips work and how digital circuits are designed and synthesized to gate-level netlists. There's no need to know much about high-level aspects such as architectures of digital circuits. This book deals with circuits mostly on the gate-level (standard-cells) or macro-level (e.g. memory block).

Prerequisites

Digital Circuits

A basic understanding of digital circuits is necessary. This includes how digital logic gates behave and how roughly they are implemented on silicon with transistors. Also it is important to be familiar with the physical structure of a chip (there's a silicon substrate which contains the transistors, on top of that come multiple metalized layers that are used to form wires, via layers connect between the metal layers).

Rust

LibrEDA is written in Rust. It is definitely helpful to have a basic understanding of the language. However, the examples showed here are probably understandable by people familiar with C-like languages.

Installing LibrEDA

See libreda.org.

Installing KLayout

KLayout is the recommended layout viewer. Any other layout viewer that can open OASIS files can be used though.

See klayout.org

LibrEDA

This books supports most topics with examples from an open-source implementation of the discussed datastructures and algorithms. There's a few open-source EDA tools, but since this book is written along the LibrEDA project it mainly focues on that.

From libreda.org:

LibrEDA is a young libre-software framework for the physical design of silicon chips and tries to simplify the development of place and route tools. A strong motivation is democratization fo silicon technology by making ASIC toolchains easily accessible for research, education and hobbyists. Today's society and especially the internet stand on integrated electronic circuits. Practically all chips that run the internet today are proprietary and closed-source pieces of hardware. This is a problem for transparency, trust, security and digital sovereignty. To build open-source alternatives it is important to have open-source Electronic Design Automation (EDA) software. Since the underlying optimization problems are not only computationally complex but also complicated it is necessary to create a collaborative ecosystem. The framework approach of LibrEDA is an attempt to go into this direction.

The following chapters are a higher level documentation of LibrEDA that often also applies to other tools. Lower-level documentation can be found in the actual software repositories of LibrEDA.

Idea and architecture

In contrast to other tools mentioned here, LibrEDA does not aim to be an end-user tool but a framework for creating such. LibrEDA has a focus on modularity. Major components such as place & route tools should be developed as separate Rust crates. They can then easily be integrated if they follow the core concepts of LibrEDA. This architecture should make it easier to cooperate on tool development. LibrEDA also defines fundamental structures for the representation of netlist and layouts, called data-base. The approach is different from many other tools. Instead of having a set of data-structures which every component must use, LibrEDA defines interfaces. The interfaces (Rust traits) define how such data-structures can be accessed and modified. This approach introduces more flexibility. Place & route engines build up on those interfaces are agnostic of the actual implementation of the data-base. This makes it possible to provide different implementations of data-bases consistently. Also it allows to build wrappers around data-base structures. For example this could be a in-memory flattened view of a hierarchical structure or a wrapper which allows to undo operations.

Other Free and Open-Source EDA Tools

Here's an incomplete list of other open-source Tools. Some of them are very helpful for working through this book. Especially KLayout is recommended to inspect generated layouts because at the time of writing LibrEDA does not provide a graphical user interface.

  • KLayout is a must - KLayout started as a GDSII layout viewer. In the meantime it grew considerably:
    • It is a versatile and scriptable layout editor with an active community
    • It can do design rule checks (DRC).
    • It can do layout versus schematic (LVS) checks.
  • Coriolis2 is one of the more mature open-source place & route tools. It is developed in Paris at Sorbonne University.
  • Magic/QFlow
  • OpenRoad is an effort DARPA and the US electronic resurgence initiative to boost EDA tool innovations by making use of the efficient nature of open-source software and by pulling-in universities across the globe.

Database

'Database' is an often used term around EDA software. It basically refers to datastructures which represent the chip during the design flow.

Most typically the following things need to be covered by the database:

  • Netlist: An abstract graph-like (actually hyper-graph) representation of circuits.
  • Layout: A two-dimensional representation of the actual circuit geometries.
  • Logic: The abstract logical behaviour of circuit components, usually of the standard-cells.
  • Timing: A representation of the signal delay when it passes through a circuit.
  • Hierarchy: Usually the above structures are put into a hierarchy. For example a circuit can be composed of other circuits.
  • Technology data: The fabrication technology puts constraints on designs. This constraints must be represented somehow. Often LEF/DEF files are used. In principle this can also be covered by the database.

Database access traits

The LibrEDA database has some important ideas at it's core:

Instead of putting a data structure at the core, the most important part in the LibrEDA DB are trait definitions (similar to interfaces in other languages) that specify how certain structures can be accessed and modified. In other words: Instead of telling how the data structures look, LibrEDA DB defines how they can be used. Of course there is a reference data structure which implements this behaviours.

This abstraction has certain advantages:

  • Algorithms are agnostic of the underlying netlist & layout representation in memory.
  • The underlying data structures can be easily swapped.
  • There can be different implementations in co-existence.
  • It is possible to create wrappers and modifier structures that for example allow to record database transactions and can undo them when needed.

Views

The database traits are structured to provide certain views of a chip:

  • Cell hierarchy: Composition relationship between the cells.
  • Netlist: Introduces electrical connectivity with pins and nets.
  • Layout: Introduces spacial layout and layered geometry. This includes position and orientation of cells and geometries on each of the layers.
  • Fused netlist & layout: This brings the layout and netlist into relation. Nets and pins can be linked to geometric shapes etc.

The mentioned views are discussed in more detail in the following sections.

Hierarchy

The digital representation of chips follows a hierarchical flyweight pattern. Hierarchy is used to represent the nested composition of circuit components - here usually called cells. The flyweight pattern is used to efficiently handle large numbers of almost identical cells.

Cells are the definitions of a certain component like a standard-cell or a memory block. Cells can be instantiated as cell instances that are contained in another cell. As an analogy this can be compared to classes and objects in object-oriented programming: Cells are the classes and cell instances the objects. Since cell instances usually differ only very little they can be handled as so-called flyweights. I.e. they can be represented by a reference to the template cell and some additional information such as the location or the nets connected from the outside.

Two traits define the hierarchical structure in LibrEDA: HierarchyBase and HierarchyEdit. The former defines only how a hierarchical structure can be accessed and traversed, the latter defines how it can be constructed and manipulated.

The following diagram illustrates how this composition graph can be traversed using the functions defined by HierarchyBase.

                              each_cell_dependency
                        +-------------------------------+
                        |                               |
                        +                               v
      +---------------------+   each_dependent_cell  +--------------------+
      |  Circuit (Top)      |<----------------------+|  Circuit (Sub)     |
      +---------------------+                        +--------------------+
      |  +               ^  |                        |   ^   +            |
      |  | each_instance |  |                        |   |   |            |
      |  |               |  |                        |   |   |            |
      |  +--+            | parent_cell               |   |   |            |
      |  |  v            |  |                        |   |   |            |
      |  | +-----------+ |  |                        |   |   |            |
 +-------->|Inst1 (Sub)|-+  |                        |   |   |            |
 |    |  | +-----------+    |                        |   |   |            |
 |    |  |                  |                        |   |   |            |
 |    |  +--+               |                        +---|---|------------+
 |    |     v               |                            |   |
 |    |    +-----------+    |  template_cell             |   |
 +-------->|Inst2 (Sub)|+--------------------------------+   |
 |    |    +-----------+    |                                |
 |    |                     |                                |
 |    |                     |                                |
 |    +---------------------+                                |
 |                                                           |
 |                              each_reference               |
 +-----------------------------------------------------------+

Some relations between the above components are worth mentioning. This is loosely taken from the API used in LibrEDA.

  • parent_cell(x): Get the cell where an instance lives in.
  • template_cell(x): Get the type of cell.
  • each_cell_dependency(x): Get all cell templates that are instantiated in a cell x.
  • each_dependent_cell(x): Get all cells that contain instances of cell x.
  • each_instance(x): Get all cell instances inside cell x.
  • each_reference(x): Get all instances of cell x in the whole hierarchy.

Using the functions defined in HierarchyEdit a hierarchical structure can be created as follows:

fn main() {
    use libreda_db::chip::Chip;
    use libreda_db::traits::{HierarchyEdit};
    
    let mut chip = Chip::new();
    // Create the cell templates.
    let top_cell = chip.create_cell("MyTopCell".into());
    let sub_cell = chip.create_cell("MySubCell".into());
    
    // Create an instance inside the top cell.
    let inst1 = chip.create_cell_instance(
        &top_cell, // Create an instance inside this cell.
        &sub_cell, // Create an instance of this template.
        Some("instance_name".into()) // Instances can have a name.
    );
}

Netlist

Netlists describe the electrical connections between circuit components. A 'net' is the represenation of a electrical potential, in practice a wire. Circuit components have pins which represent the electrical interface towards the outside. Pins can be connected to a net and a net can be connected to many pins of circuits. This connectivity information is used to fully describe a circuit on the 'netlist' level.

For pins and nets LibrEDA follows the nomenclature used in the Hierarchy. Nets are connected to 'terminals'. A terminal can either be a pin of a circuit (i.e. the interface to the outside of the circuit) or the terminal can be a 'pin instance' . As the name hints, a pin instance is an instantiation of a circuit pin which lives in a circuit instance.

LibrEDA currently defines two traits which allow to access and edit netlist structures.

  • NetlistBase: This trait provides functions to access, query, traverse netlists.
  • NetlistEdit: This trait provides functions to create/remove nets, create/remove pins, connect/disconnect pins and nets. Both traits are tightly linked to the hierarchy traits. A type implementing NetlistBase must also implement HierarchyBase and a type implementing NetlistEdit must also implement HierarchyEdit.

Similar to the hierarchy trait, the netlist traits also define Id types (NetId, PinId, PinInstId). They are handles to the netlist objects and can cheaply be cloned. TerminalId is used to abstract over PinId and PinInstId. It is an enum though.

An example of how to create a simple netlist is shown here:

fn main() {
    use libreda_db::chip::Chip;
    use libreda_db::prelude::*;
    use libreda_db::traits::{HierarchyEdit, NetlistEdit};
    
    let mut chip = Chip::new();
    // Create the cell templates.
    let top_cell = chip.create_cell("MyTopCell".into());
    let sub_cell = chip.create_cell("MySubCell".into());

    // Create pins.
    let top_pin_a = chip.create_pin(&top_cell, "A".into(), Direction::Input);
    let sub_pin_a = chip.create_pin(&sub_cell, "A".into(), Direction::Input);
    
    // Create an instance inside the top cell.
    // The instance will inherit 'pin instances' according to the 'pins'
    // of the template cell.
    let inst1 = chip.create_cell_instance(
        &top_cell, // Create an instance inside this cell.
        &sub_cell, // Create an instance of this template.
        Some("instance_name".into()) // Instances can have a name.
    );
    
    // Create a net. A net must not necessarily have a name.
    // Hence the name is an `Option`.
    let net = chip.create_net(&top_cell, Some("myNet".into()));
    
    // Connect the net to the pin of the top circuit and to the pin instance
    // if the instance of `MySubCell`.
    // This way the signal is passed from the top cell to the sub cell.
    chip.connect_pin(&top_pin_a, Some(&net));
    chip.connect_pin_instance(
        // Get a handle to the pin instance of pin `A` in the instance `inst1`.
        &chip.pin_instance(&inst1, &sub_pin_a),
        Some(&net)
    );
}

Layout

'Layout' refers to the multi-layer geometrical shapes which describe the physical circuit.

Cells may contain geometrical shapes on different layers. Instances of cells don't contain any shapes because they are 'clones' of their template cell. However, instances have a location, rotation and magnification (rarely used) relative to their parent cell.

Following the spirit of the hierarchy traits, LibrEDA also defines traits for accessing and editing layout information: LayoutBase and LayoutEdit. LayoutBase also defines ID types for layout objects (Coord, LayerId, ShapeId). Coord specifies the actual data type used for coordinates in the euclidean plane. For most applications this will be an i32. LayerId is a handle which points to a certain layer. Layers can be referenced also by name or (index, datatype) tuples as used in GDSII or Oasis file formats. However, names and layer numbers first need to be converted into a LayerId using methods like find_layer() or layer_by_name().

Geometrical shapes are based on the iron-shapes crate and further documented in Euclidean Geometry.

Fused Netlist & Layout

Netlists and layouts are just different representations of a circuit. LibrEDA reflects this with the netlist and layout traits which build on top a hierarchical structure. Having both of this views is not sufficient though. For many purposes it is necessary to know the links between netlist and layout. For example it is helpful to know which layout shape belongs to which net or to know where the physical geometry of a pin is located. For this reason LibrEDA uses the L2NBase and L2NEdit traits. L2N means layout-to-netlist. The both traits extend the layout and netlist traits with the most fundamental links. This includes

  • The layout shapes which belong to a pin.
  • The layout shapes which belong to a net.
  • The net which is connected to a layout shape.
  • The pin which is made by a layout shape.

Reference Access Pattern

Syntactic sugar for read-only access to netlists, layouts, hierarchies.

The basic traits for hierarchy, netlist and layout access are based on object IDs - handles which can cheaply be cloned. In the implementation this could be for instance integer numbers. Working with IDs also has disadvantages such as non-object-style syntax. For example to get all pins of a cell one might want to write cell.each_pin() instead of making the detour over chip.each_pin(&cell). This is where 'reference access' wrappers come into play. They wrap the object ID together with an immutable reference to the base data-structure (a HierarchyBase, NetlistBase, LayoutBase, ... trait). The wrapper data type now behaves much like an object with associated function. In the background this all maps back to the trait implementation with object IDs. Therefore the data-type implementing such traits needs only to provide ID based access and gets object-like access for free. This access method is currently limited to read-only access. Good use cases are code pieces which do not modify anything but for example analyze a netlist.

Euclidean Geometry

Euclidean geometry - geometry in the two dimensional plane - is important for handling chip layouts. A separate crate iron-shapes is devoted to this task. The crate defines geometric data types such as points, vectors, polygons and transformations. They are used for everything related to layouts.

Logic

Place and route tools at some point need to deal with the logic behaviour of components (e.g. standard-cells). Especially when the netlist is changed to reach timing constraints the algorithm must somehow understand the logic behaviour of the circuit in order to preserve it. An other example is timing-analysis where delays of a gate depend on the values of other inputs. Somehow the time-analysis algorithm needs to be able to compute this values to choose good estimates of the delays.

There are different types of logic commonly used in EDA software:

  • Two-valued logic (boolean logic) with values LOW and HIGH.
  • Three-valued logic with values LOW, HIGH and UNKNOWN.
  • 4-valued logic (IEEE 1364), with values LOW, HIGH, UNKNOWN, HIGH_IMPEDANCE
  • 5-valued logic (D-algebra), with values 0, 1, D, D', X.
  • 9-valued logic (IEEE 1164, less likely to be used in physical synthesis)

An example for usage of a 5-valued logic are automated test-pattern generators (ATPG). The 'D-algorithm' uses the 'D-algebra' to understand how manufacturing errors can be detected in a circuit.

TBD

  • To allow useful abstractions libreda-logic defines traits for dealing with logic.

File Formats

This section currently contains mainly links to implementations of named file formats.

Netlists

Verilog

  • libreda-structural-verilog - Verilog parser & writer for the structural netlist format used by Yosys. Behavioral verilog is not supported - only gate-level netlists. Netlists can be hierarchical though.

DEF

DEF can also encode netlists. At time of writing this is not supported yet though.

Layouts

GDSII

Probably the most famous file format for chip layouts. GDSII is unfortunately not nicely defined and has many pitfalls. There is no implementation yet to be mentioned here. The recommended way is to use OASIS as layout input and output format. OASIS can be reliably converted to and from GDSII using KLayout.

OASIS

OASIS is a good successor of GDSII. It is quite well defined and much more space efficient than GDSII, hence also faster to load and write.

LEF/DEF

Library

Liberty

Liberty encodes library data such as timing behaviour of cells.

Physical Synthesis - Place & Route

Physical synthesis is the process of converting a gate-level netlist into a physical chip layout which satisfies certain constraints. The layouts of the gates and their timing behaviour must be already given in a library. Usually the layouts are stored in a LEF library or separate GDS/OASIS files. The behaviour (logical and timing) is often described in 'liberty' files.

The following sections will cover the most important place & route steps and relate them to the relevant parts of the LibrEDA framework.

General idea of LibrEDA

The LibrEDA framework does not implement any place & route algorithms. But it provides fundamental data structures and interfaces. Place & route algorithms are developed as separate projects. As long as they follow the core ideas of LibrEDA they can easily be integrated with each other.

Example place & route flow

  • libreda-examples implements an example place & route flow. The program assembles parts of the LibrEDA framework into a stand-alone tool.

References

  • Electronic Design Automation: Synthesis, Verification, and Test (ISBN 9780123743640)
    • Some chapters can be found online:
    • http://cc.ee.ntu.edu.tw/~ywchang/Courses/PD_Source/EDA_Chapter1.pdf
    • http://cc.ee.ntu.edu.tw/~ywchang/Courses/PD_Source/EDA_floorplanning.pdf
    • http://cc.ee.ntu.edu.tw/~ywchang/Courses/PD_Source/EDA_placement.pdf
    • http://cc.ee.ntu.edu.tw/~ywchang/Courses/PD_Source/EDA_routing.pdf
    • Electronic Design Automation, Synthesis of clock and power/ground networks, (DOI: 10.1016/b978-0-12-374364-0.50020-5)

Placement

For all the cells in the netlist a position on the chip must be found. The position must satisfy geometrical constraints and should minimize certain metrics such as the required wiring length for connecting all the cells. To simplify the process, often placement is broken up into sub-steps:

  • Global placement: Find rough positions of cells. Overlaps are allowed but the average density should be below 1 such that in a later step it is possible to arrange the cells without overlap.
  • Buffer & Tie-cell insertion: The netlist must probably be modified after global placement. Usually synthesized netlists contain nets which have constant logic values 0 or 1. Constant nets are driven by 'tie'-cells, which tie the signal to either 0 or 1. It makes sense to put tie-cells close to where they are needed. For this reason they are best created after global placement when the necessary information is available. Similarly, some nets may have too many cells attached such that the driver cell is too weak to drive all the load. In such cases it is necessary to insert buffers. The structure of the buffer network depends also on the locations of the driver and the loads. There fore buffer insertion is best done after global placement.
  • Legalization: Arrange the cells such that they don't overlap and put them into rows such that the power rails and wells are connected by abutment.
  • Filler insertion: Remaining space between the cells must be filled with 'filler'-cells
    • to ensure connectivity of the power rails and wells
    • to stabilize the power rails with capacitors
    • to meet certain metal density constraints necessary for fabrication
  • Detail placement
    • Perform local optimizations
    • Mirroring cells, switching cells locally

References

Good overview: http://cc.ee.ntu.edu.tw/~ywchang/Courses/PD_Source/EDA_placement.pdf

Global Placement

Global placement: Given a netlist of standard-cells and macros arrange them on the chip.

The global placement has relaxed constraints: Cells and macros can overlap, the overlap will be removed during legalization. Also they need not be placed strictly in rows yet. However, certain values should be optimized.

  • Density: The average density must be below 1 or lower to guarantee overlap-free placement during the legalization step.
  • Wire-length / Routability: The global placement step should minimize an estimation of the required wiring length. Different estimates of wiring length are used in practices. Common ones are the half-perimeter wiring-length (HPWL).

Netlist might be modified during or after global placement by inserting tie-cells, buffers, delay cells. Such modifications could be neccessary to meet timing constraints.

Simulated Annealing

Simulated annealing is a so-called 'metaheuristic' which can be used to find approximate solutions of many optimization problems. The algorithm is rather simple to implement but does not scale well to large problems (e.g. one million cell designs). Simulated annealing, as the name says, simulates the cooling of a metal. While the temperature is hot a lot of random movements of the atoms happen. Also atoms which have an energetically low position can still leave it and go to a worse position. With lower temperature the capability of atoms to take a bad position over a good one decreases. This can be directly translated to placement of standard-cells. The 'cost' of a placement solution is computed for example by the necessary wire-length and the violation of overlap and density constraints. Cells get randomly perturbed. Perturbations which improve the solution are accepted with increasingly higher probability. Perturbations which worsen the solution are accepted with increasingly lower probability.

Analytic Approaches

Analytic approaches generally scale better to large placement problems than simulated annealing. An intuitive reason is that they iteratively change the placement towards a better solution.

Non-linear - ePlace

The state-of-the-art placement algorithms are 'non-linear' algorithms. Some successful algorithms like 'ePlace' model the cells as charged particles which repulse each other. The repulsion is used to satisfy density constraints. The particles feel another attracting force when they are connected with a net. This helps reducing the wire-length of the solution.

Quadratic Placement

Quadratic placers are simple and fast but do not solve density constraints. In practice they can be used to find initial solutions for non-linear placement solutions.

Idea: Minimize quadratic wire length and allow overlaps. Quadratic wire length is differentiable. Convex problem: There is a global optimum which can be found efficiently.

Minimizing the quadratic wire length is equal to the finding the equilibrium in a network of springs (assuming that there's no physical collisions). The cells can be treated as object which are connected together with springs according to the electrical connectivity. Some springs are also attached to fix-points (for instance the pad locations).

Finding this equilibrium is equal to solving a linear system.

As shown in the following illustration cells can be modelled as nodes in graph. The edges are treated as mechanical springs which pull the nodes together. Some nodes have fixed locations, for example pre-placed pad-cells, pins or macro-blocks.

Network of springs

Solving density constraints

Quadratic placement does not respect any density constraints. Highly connected cells will usually be placed tightly together.

Multiple methods exist to spread cells evenly based on quadratic placement.

  • Recursive partitioning
  • Spreading forces: iteratively insert more 'springs' which pull the cells away from dense locations. The direction and magnitude of the spring forces can be computed from the gradient of the placement density.

Multi-Terminal Nets

A net-list is a hyper-graph. An edge (net) can connect more than two nodes.

To convert a hyper-graph into graph additional edges have to be inserted to preserve the connectivity. This can be done in multiple ways. Two common ones are:

  • Clique: Insert an edge for each pair of connected nodes.
  • Star: Insert a virtual center node.

The edge weights have to be chosen accordingly. For instance in the clique model the number of edge connected to a single cell grows with the number of neighbours. To make sure that nets with many terminals are not weighted more than nets with only two terminals the edge weights need to be adjusted. (TODO: How?)

Multi-terminal net models: hyper-graph, clique, star

Mixed-Size Placement

In practice, macro-blocks are often placed manually. Then standard-cells are automatically placed within the remaining space. However, mixed-size placement algorithms can do a joint placement of macro-blocks and standard-cells together. A good example is ePlace.

Example implementations

The electron-placer crate contains example implementations of global placement algorithms. The name is derived from a analytic placement method which uses simulated electro-static repulsion to solve the density constraints.

libreda-pnr defines interfaces (traits) for placement algorithms. An implementation does not need to stick to this traits, but there are some benefits if it does. For example the implementation can then easily plugged into flows.

A simple trait for placement is shown here:


#![allow(unused)]
fn main() {
/// Interface definition for mixed-size placement engines (for macro blocks and standard cells).
pub trait MixedSizePlacer<C: L2NBase> {
    /// Get the name of the placement engine.
    fn name(&self) -> &str;

    /// Find the positions of all circuit instances inside `circuit`.
    ///
    /// # Parameters
    ///
    /// * `placement_problem`: [`PlacementProblem`] trait object. This object bundles the netlist, layout and
    /// other parameters relevant for placement such as cell-sizes, fixed/movable cells, net weights.
    ///
    /// # Returns
    ///
    /// Returns a `HashMap` which maps circuit instances to positions.
    fn find_cell_positions_impl(
        &self,
        placement_problem: &dyn PlacementProblem<C>
    ) -> Result<HashMap<C::CellInstId, db::SimpleTransform<C::Coord>>, PlacementError>;
}
}

MixedSizePlacer is kept minimal. It takes one argument which describes the placement problem and is supposed to return a map with positions (or an error).

The PlacementProblem encodes all necessary information needed to find the placement solution.

This includes amongst other:

  • the layout and the netlist of the design as well as the top-level cell
  • the regions where cells can be placed
  • the placement status of cells. Cells can be fixed, movable or ignored
  • initial positions
  • cell outlines, i.e. abutment boxes of the cells which should be placed
  • net weights can be used to steer the placement based on results of a the timing analysis step

The same interface can be used by global placers and also legalizers or detail placers. They just return another solution with tighter constraints.

Legalization

Legalization transforms an approximate global placement solution into a legal placement solution. This means in practice: Remove overlaps between standard-cells/macro-blocks and place standard-cells on rows.

There are possibly constraints and optimization criteria, for example minimization of wiring length.

Example implementations

The following repositories contain legalization engines which can be used as inspiration for other implementations:

Buffer and Tie-Cell Insertion

A netlist which comes from a logic synthesizer is often not fully suitable to be implemented as it is on a chip. Logic synthesizers such as Yosys are not aware of the placement and hence cannot do everything optimally. For example nets with constant values (0 or 1) must be driven from so-called 'tie-cells'. A tie-cell has just a constant output signal, either 0 or 1. To minimize the required wiring, it is much better to insert such tie-cells once it is known where they are needed. For that reason, synthesizers might not put tie-cells into the netlist at all but just use logic constants 0 and 1.

Another example are high-fanout nets and buffer trees. Often, so many cells are attached to a net such that the driver cell will be too weak and too slow. Typical techniques to solve this problem are

  • buffer insertion between the driver cell and the signal sinks
  • replication of the driver cell

Consider for example this setup with a driver and four sinks a, b, c, and d. Since the driver is too weak, two buffers are inserted do then drive the sinks.

driver           c
                     d


              buf2


     buf1
 a


   b

Logically, it does not matter which of the sinks is attached to which buffer. But it matters once the circuit is implemented. When the placement of the cells is known, it is easy to see that a and b are best attached to buf1 and the other sinks to buf2:

driver           c
     +-+---+     ^   d
       |   |     |   ^
       |   |     +   |
       |   +->buf2+--+
       |
       v
     buf1
 a<---+
      |
      |
   b<-+

Without knowing the placement it is likely that a much worse solution would be picked. For example driving sinks a and d with buf1 results in much more wiring:

driver           c
     +-+---+     ^   d
       |   |     |   ^
       |   |     +   |
       |   +->buf2   |
       |         +   |
       v         |   |
     buf1        |   |
 a<---+--------------+
                 |
                 |
   b<------------+

Tie-cells can be regarded as a type of buffer of a constant signal. Because the signal is constant they can easily be replicated without the need of wiring between them. But in order to share tie-cells among sinks which are close together it is necessary to know the global placement.

Implementations

Routing

References

A good introduction to routing can be found here: http://cc.ee.ntu.edu.tw/~ywchang/Courses/PD_Source/EDA_routing.pdf

Maze Routing

'Maze routing' is an approach for finding shortest paths on a grid. The algorithm is very similar to Dijkstra's shortest-path algorithm. Horizontal and vertical tracks form a routing grid graph as shown in the illustrations below. Routing between two graph nodes happens by propagating a 'wave' from the source node. In the beginning, all nodes are marked as not visited, except the source node. It is marked as visited with distance 0 to the source node. Iteratively, the closest neighbours of visited nodes are processed.

Multilevel Full-Chip Routing

TODO

See MARS.

Line-Probing / Line-Search

Line-probing algorithms search for routes directly based on the geometry. Unlike maze-routers, line-probing does not necessarily need a grid. Hence they can be more memory efficient and faster.

Example algorithms in the literature are:

  • Hightower's algorithm
  • Mikami-Tabuchi algorithm

The above algorithms do not guarantee finding the shortest path between two terminals.

Example implementations in LibrEDA

  • mycelium-router contains an experimental detail router based on a line-search algorithm which guarantees finding the shortest path between two nodes if one exists.

Clock-tree synthesis (CTS)

Clock-tree synthesis is the art of distributing clock and reset signals to the circuit components which need them. There are many requirements and many approaches.

H-tree

TODO

Example implementations

The arboreus-cts crate implements very simple algorithms for creating buffer trees. This is also useful for rebuffering of large-fanout nets and can be used for generating clock and reset trees - more for demonstration purposes though. There's no timing optimization involved yet.

ATPG

See wikipedia.