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.