Paper Authors and Title
Yi Ming Tan (Munster Technological University), Paul Davern, “Algorithmic Techniques for Minimizing Congestion in VLSI Global Routing”
Abstract
The physical design of Integrated Circuits (ICs) remains a challenging yet fascinating aspect of Electronic Design Automation (EDA). Routing holds immense importance among the various steps involved in physical design, as it involves establishing physical connections based on logical connectivity. Routing consists of two main stages: Global Routing and Detailed Routing. Global Routing aims to generate a coarse route for each net while optimising objectives such as total overflow, wire length, and circuit timing.
In this final-year project, we explored algorithmic techniques used in Global Routing, a known NP-hard problem, to achieve near-optimised solutions. The objective was to optimise congestion and minimise wire length on a chip. We employed algorithms such as Lee Maze Router, Dijkstra Algorithm, and heuristic algorithms like A* Search Algorithm and Best First Search Algorithm.
The research involved a meticulous analysis of the challenges and intricacies of Electronic Design Automation (EDA). By leveraging patterns within the problem domain, we devised an algorithm that organises the netlist in ascending order of its half perimeter wirelength (HPWL).
By employing this sorting technique, an average decrease of 82.6% in congestion was achieved. This enhancement positively impacted overall circuit connectivity and contributed to a more efficient physical design.
The algorithm’s results demonstrated a commendable level of performance and achieved comparable outcomes to competitors at NTHU, surpassing their results for one of their benchmarks. Through extensive evaluation, we analysed the time and space complexity of the algorithms and visualised the layout’s congestion through a heat map.
Poster
Download and view Yi Ming Tan’s poster.