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.

LibrEDA Book