O Programa de Pós-Graduação em Microeletrônica – PGMICRO, da Universidade Federal do Rio Grande do Sul, tem a satisfação de convidar a Comunidade Universitária para assistir à defesa pública de Tese de Doutorado do aluno JUCEMAR LUIS MONTEIRO realizar-se:
Data: 17/05/2019 às 16h: 00
Local: Instituto de Informática 43412(65)- sala 215
Título: “Algorithms to improve area density utilization, routability and timing during detailed placement and legalization of VLSI circuits”
Orientador: Prof. Dr. Marcelo de Oliveira Johann
Coorientador- Profª. Drª. Laleh Behjat
Dr. Andrew Khang (UCSD)
Dr. Patrick Groeneveld (Stanford)
Dr. Ismail Bustany(Xilinx)
Placement is a challenging stage in Very-Large Scale Integration (VLSI) physical de- sign. In modern VLSI designs, several design restrictions have been imposed to address the complexity of advanced Complementary Metal-Oxide Semiconductor (CMOS) fab- rication nodes. These restrictions have a considerable influence on achieving optimized placement solution. The quality of placement solution has a significant impact on circuit performance. In placement, achieving circuit requirements of timing and routability is a very challenging task. These requirements are especially hard to achieve in circuits which have regions with high-density area utilization. Moreover, the quality of placement has a direct influence on circuit quality and optimization effort of Clock Tree Synthesis (CTS), router and post-placement algorithms. In this thesis, the contribution on routing-aware incremental timing-driven placement is given. The second contribution of this thesis is a cell spreading algorithm to move cells out of high-density regions considering adverse side effects on moved cells. The proposed cell spreading algorithm relies on network flow and branch and cut techniques to minimize high-density regions. Area flows are moved from high to low-density regions with optimized cost paths. Therefore, cell concentra- tion is reduced, and white spaces are opened in high-density regions with minimized ad- verse side effects on moved cells. Legalization and detailed placement algorithms can use these white spaces to optimize further the placement solution. In high-density regions, white spaces are limited resources. Extra white spaces in high-density regions can aid optimization algorithms to improve placement. In the traditional placement flow (global placement, legalization and detailed placement), placement optimization is limited by the strict placement flow. The proposed cell spreading algorithms can be integrated into a mixed placement flow composed of interleaved legalization and detailed placement al- gorithms. In this mixed placement flow, the restriction to optimize detailed placement in a legalized netlist can be relaxed. Detailed placement algorithms can achieve further placement optimization with less restricted placement formulation. Moreover, legaliza- tion can be inserted in different stages of the mixed placement flow. Legalization algo- rithms have placed circuits with a reduced number of high-density regions. The focus of legalization algorithms can be to fix cell overlap with minimized adverse effects on placement. Nowadays, legalization algorithms must also fix violations of area density utilization. The proposed cell spreading algorithm can improve high-density regions be- fore starting the legalization procedure. The proposed network flow-based legalization algorithm has achieved improvement on average (30%) and maximum (350%) cell dis- placement compared to state-of-arts legalization algorithms. In detailed placement, the proposed algorithm has been evaluated in industrial and academic placement flows. In in- dustrial placement flow, the proposed cell spreading algorithm has achieved improvement in power consumption, and timing. The proposed cell spreading algorithm can improve the quality of placement in mixed placement flow in both industrial and academic en- vironments. The proposed algorithm provides a uniform cell distribution placement in constrained designs with minimized adverse side effects on moved cells.
Keywords: Microelectronic. EDA. Placement. Placement Optimization. Network flow. Branch and Cut.