Custom Macro Placement

The previous post of mine described briefly about the various career paths that one can pursue and how to get started with each of them. Many of the readers found it to be extremely useful. I am happy that I am able to touch lives through my articles.

However, in this article I want to throw some light on some of the work we do in the VLSI industry. This article is not meant for the general audience.

← I am assuming that the reader understands that the lib,lef,netlist,constraints are already loaded even before we begin our design execution →

The Physical Design process starts after the Synthesis step. The SoC (System on Chip) is divided into various sub-blocks using a step called “Partitioning”. A processor contains various processing units (for eg, CPU,GPU,Camera, Video etc) and these are termed as Blocks. A block is assigned to the implementation engineer and he has to execute the design such that the Timing,DRC and Power requirements are met.

Implementation of a block starts with Floor-planning the design, followed by placement, CTS and routing the design. The floor-planning activity includes the arrangement of memory macros, pin placement and power planning of the design to minimise the wirelength and area of the design.

Here, I am about to present my understanding of one of the “research papers” written by my manager.

Majority of the designs these days involve manual placement of the macros and pins for optimal area and wire-length. The layout generated by conventional placement techniques will not be able to handle large incremental changes since a small change in the position of the macro cells will lead to displacement of a larger number of standard cells and hence will be significantly difficult to close the design.

There are however special tool features to accommodate these types of problems. (Automatic Floorplan Feature in Innovus → The user can feed the constraints and the tool generates a floor-plan). I do not know many people using this feature in the industry. So, what is this article about then? It’s about writing custom C++ code for very specific design requirements. The requirements and constraints to be met may vary from team to team.

There are 3 constraints in macro-placement.

1. Pre-Placed constraints (position of macros are fixed from top level)
2. Grouping constraints (macros of the same logic level are to be grouped and placed together)
3. Region constraints (The macro or a macro group should be placed with in a pre-determined rectangular boundary within the block)

Given below are the cost functions that capture the constraints.

Cost Function of the algorithm→

1. Wire-length (It’s the half perimeter of the minimum bounding rectangle containing the connected macro cells) (Not the actual wire-length) (handles the group and region constraints)
2. Effective standard cell placement area.
3. Corners (These are the physical corners)

These kind of problems fall under the following category of problems

1. Combinatorial Optimization Problem.
2. Multi-Objective Optimization Problem.

— — — — — — — — — — — — — — — — — —

Mapping of a Physical Design Problem onto a Computer Science Problem

Constraint Graph based Legalization →

The macros are mapped onto a constraint graph for overlap removal. Positive slack in the constraint graph denotes separation of macros and negative slack denotes overlap between the macros. The overlap is removed by redistributing the positive slack along the path having negative edges.

(So, I myself know only the theory behind the graph based legalization problem. I am a newbie in coding and I am exploring graph data structure. And also I haven’t seen the code that was developed).

Some of the inputs fed to the custom algorithm (that I can think of are)

1. The macro attributes (size and area)
2. The constraints (Grouping, Pre-placed, region )
3. B-Box Area.
4. Blockages (optional)

The placement and legalization of macros happens in the following manner.

1. Initial random arrangement of macros.
2. The macros are then clustered based on connectivity.
3. Overlaps are removed and macros are pushed towards the periphery.
4. Macros are aligned along the horizontal and vertical edges, compacted with a contiguous area at the center. (Removes corners and aids in routable congestion free placement)

Disclaimer → This article only demonstrates my understanding of the Macro Placement Algorithm. I in no way am the owner or the developer of the algorithm. This paper has been written by my mentor 9–10 years back and is patented.

-Sethupathi Balakrishnan