Synopsys – Macro Legalization in Chip Design #SWI2022

Advanced silicon chips power the amazing software we rely on every day. They are the foundation for everything from smartphones and wearables to self-driving cars and machines that learn. Synopsys is a company for electronic design automation (EDA), i.e., we develop software that enables our customers (Intel, Samsung, Mercedes-Benz, and many more) to design and optimize silicon chips.

Designing a computer chip is a very complex task that is solved by a divide-and-conquer approach, splitting the entire chip in smaller blocks that are designed separately first and put together later. A single block contains many physical components which are often rectangular: usually 1 to 10 million standard cells (very small) and up to several hundred macros (comparatively large). The placement of these components on the 2-dimensional block area is an important step of the design process.

A block, with standard cells in violet and macros in black with cyan border.

We consider the sub-problem of macro legalization. In a legal macro placement, macros do not overlap and fulfill various types of design constraints, e.g.:

  • Some macros may only be placed in certain regions of the block.
  • There are blockages in some regions of the block, forbidding macros to be placed there.
  • There are macro-specific grids that macros need to align to.
  • Neighboring macros either need to abut or to have a proper channel between them. Formally: Given numbers 0 ≤ b < c, any two macros need to either have an exact distance of b or at least a distance of c.

At the point in the placement step when macro legalization is applied, a coarse placement of both macros and standard cells has already been computed. This placement is optimized for timing and power, based on the inter-connectivity of the standard cells and macros, but it is typically not legal.

The goal of macro legalization is to find a legal macro placement which deviates as little as possible from the initial macro placement. Even without any design constraints, the problem is NP-hard; and due to the large number of macros, it is also difficult in practice as sometimes only few constraint violations can lead to many changes necessary compared to the input placement.

Our challenge for SWI 2022 is to develop an algorithm for macro legalization that finds a best possible solution in a reasonable amount of time. We provide realistic test instances the participants can use to compare their algorithms with the legalization tools we use in practice.


Print this page