In the fast-paced realm of semiconductor technology, optimizing chip design to meet the dual challenges of performance enhancement and cost reduction has emerged as a pivotal focus. A new study published in Engineering introduces a groundbreaking approach to address this challenge, presenting an exact algorithm for placement optimization in mixed-cell-height (MCH) circuits. Led by researchers Binqi Zhang, Lu Zhen, and Gilbert Laporte, the work tackles the intricate task of arranging diverse circuit cells within constrained chip regions while adhering to critical design rules, including non-overlapping placement, power rail alignment, and minimum implantation area (MIA) constraints.
Chip placement, a foundational step in semiconductor design, involves strategically positioning cells to minimize wirelength and maximize space utilization. Modern chip designs increasingly rely on MCH configurations, where cells of varying heights—single, double, triple rows, and special types with internal pin structures—must coexist. However, existing methods struggle to balance multiple constraints simultaneously, such as ensuring precise alignment of cell pins with power rails (VDD/VSS), preventing physical overlaps, and meeting MIA requirements that govern manufacturing feasibility.
To address these complexities, the researchers developed an MILP model that formalizes the placement problem as a mathematical optimization task. The model aims to minimize placement cost, measured through metrics like wirelength and compactness, while enforcing three key constraints: non-overlapping cell positions, accurate VDD/VSS alignment to ensure signal integrity, and compliance with MIA rules by aggregating undersized cells horizontally. This approach avoids the need for additional filler cells, optimizing both space and cost.
The study introduces a BD-based exact algorithm to solve the MILP model efficiently. The algorithm partitions the problem into two components: a master problem (MP) that handles discrete decisions such as cell grouping by threshold voltage (Vth) type and bin allocation, and a subproblem (SP) that optimizes continuous cell coordinates to satisfy geometric and electrical constraints. By leveraging dual theory, the algorithm iteratively refines solutions, balancing computational efficiency with solution accuracy—a critical advantage for large-scale designs.
Extensive validation using benchmark data from the International Symposium on Physical Design (ISPD) 2014 contest demonstrated the algorithm's effectiveness. In small-scale instances, the BD algorithm matched the optimal solutions of commercial solver CPLEX, while in larger-scale scenarios, it outperformed CPLEX significantly in terms of computation time. For example, in instances with 35+ cells, BD delivered solutions in under 5 minutes, whereas CPLEX often failed to converge within feasible timeframes, highlighting BD's scalability for industrial applications.
Sensitivity analyses revealed critical design insights: Chip regions with higher width-to-height aspect ratios (w:h) reduced placement costs by enabling more compact vertical cell arrangements; designs with a higher proportion of taller cells (e.g., triple-row height) improved space utilization; and reducing the number of bins (chip subregions) minimized edge spacing overhead, though excessive bin division led to diminishing returns. These findings provide practical guidance for engineers to optimize chip layout strategies, such as prioritizing uniform cell heights and balanced aspect ratios.
The study bridges theoretical modeling with industrial requirements, offering a robust framework for modern chip design. By integrating mathematical rigor with real-world design constraints, the BD algorithm addresses a long-standing gap in placement optimization for MCH circuits. This approach not only enhances the efficiency of chip design processes but also supports the development of more cost-effective, high-performance semiconductor devices—a critical advancement as the industry navigates the challenges of post-Moore's Law scaling.
The paper "An Exact Algorithm for Placement Optimization in Circuit Design," is authored by Binqi Zhang, Lu Zhen, Gilbert Laporte. Full text of the open access paper: https://doi.org/10.1016/j.eng.2025.03.020
