Placement is one of the most important steps in the post-RTL synthesis process, as it directly defines the interconnects, which are now the bottleneck in circuit and system performance in deep submicron technologies. The placement problem has been studied extensively in the past 30 years. However, a study from UCLA shows that existing placement solutions are surprisingly far from optimal. Using a set of cleverly constructed circuit placement examples with known optima (PEKO) that match many industrial circuit characteristics, the study shows that the results of leading placement tools from both industry and academia are 70% to 150% away from the optimal solutions in terms of the total wirelength on these cases [Chang et al., 2003]. If such a gap could be closed, the resulting benefit would be equivalent to advancing several technology generations. In comparison, the introduction of copper interconnects is equivalent to a 30% wirelength reduction, and so is each process technology scaling. But both require multi-billion dollar investments.
We shall develop a highly scalable placement engine that provides significant quality improvement over the existing state-of-the-art placement tools to reduce the gap between current achievable solutions and the optimal solutions. The placement engine will be built on the multilevel optimization framework, which has strong advantages in scalability, flexibility, and adaptability to new and complex constraints. We plan to apply recent advances in multilevel optimization and adapt and extend them to the problems and challenges unique to VLSI placement. In particular, our research will lead to efficient solutions to the following placement problems. (i) The large-scale mixed-size placement problem, which has become very common for advanced IC designs, with the extensive reuse of IP blocks for multi-million-gate ASICs and SOC designs. We must efficiently handle a very large number of standard cells mixed with many big macros, such as ROMs, RAMs and IP blocks. (ii) The constraint-driven placement problem, which considers delay, routability, and possibly other manufacturing- related constraints. We shall also develop new metrics and examples for measuring the quality of results in meeting such constraints. (iii) Incremental placement, which supports frequent dynamic netlist adjustment (say, due to physical re-synthesis) and design updates. Our three-year target is to achieve significant improvement in quality of results over state-of-the-art solutions with clearly measured goals on benchmarks with known optima, e.g., 20-30% gap reduction in wirelength.
