Competing in the International Conference on Computer-Aided Design (ICCAD) 2021, which concluded on November 4th, the HUST team, led by Prof. Lv Zhipeng from the School of Computer Science, won first place in the Routing with Cell Movement Advanced competition in the CAD contest.
The ICCAD conference, which began in 1980, is one of the oldest top-level academic conferences in the EDA (Electronic Design Automation) field. Among the categories, the algorithm competition in the CAD contest plays a role as the most influential conference landmark event and has long been the subject of international academic and industrial attention.
Each year, the problems for the competition come from real business scenarios of widely known EDA or semiconductor companies such as Cadence, Synopsys, Mentor Graphics, Nvidia, and IBM. These problems focus on the core algorithm problems that are hard to solve in IC design, manufacturing, and testing processes, such as logic synthesis, placement and routing, equivalence verification, and timing analysis.
The contest this year was joined by 137 teams from 12 countries and regions, including teams from elite universities and institutes like UC Berkeley, the University of Tokyo, the Chinese University of Hong Kong, and Fudan University.
EDA is the cornerstone of the electronic design industry, also hailed as “the mother of chips”.The Routing with Cell Movement Advanced in this year’s competition, as the most important part of the EDA chip back-end physical design, directly affects the chip’s performance indexes including power dissipation, area, and time delay.
The placement distributes a series of circuit units in a given rectangular space, while the routing process wires the unit pins of the units in the same network. Therefore, with the constraints in the real scenarios like the spatial capacity, voltage area, minimum routing layer, and metal routing direction, the algorithm needs to determine the location of each unit in the chip and plan a signal transmission path for each network free of short and broken circuits, in order to ensure the shortest total weighted length of wires.
The heuristic optimized algorithm designed by Professor Lv Zhipeng and his team has achieved breakthroughs in several key technologies, including redundant wire detection, routing loop elimination, parallel neighborhood evaluation acceleration, and layout adjustment optimal moving area identification. According to the competition results announced at ICCAD 2021, the algorithms designed by the team achieved the best results in the competition in all test cases. It is the first time for the team to participate in the ICCAD 2021 competition.
For more than 40 years since its establishment, Prof. Lv's lab has been focusing on algorithms for NP-hard problems and industrial applications. The lab has achieved impressive results in many top international algorithm competitions, such as third place in ISPD Routing International Algorithm Competition in 2021, first place in GECCO International Algorithm Competition "Optimal Camera Layout and Ensemble Coverage" in 2021 and 2020, third place in SAT International Algorithm Competition in 2018, first place in SAT International Algorithm Competition in 2017, third place in ROADEF/EURO International Algorithm Challenge "LPG Inventory Routing" in 2016, third place in International Nurse Scheduling Algorithm Competition in 2010, second place in International University Scheduling Algorithm Competition in 2008, etc.
