Very large scale integration (VLSI) technology, which places and connects billions of transistors in a fingertip-sized chip, is the core of today’s electronic equipment and the foundation of our digital world. Mr. Gengjie Chen, a PhD student under the supervision of Professor Evangeline F. Y. Young at the Department of Computer Science and Engineering has taken First Place in the  Association for Computing Machinery (ACM) Student Research Competition Grand Finals, with the research project themed “VLSI Routing: Seeing Nano Tree in Giga Forest”. Mr. Chen received the award recently at the annual ACM Awards Banquet in San Francisco, where the prestigious Turing Award (also recognised as the Nobel Prize of Computing) for this year was also presented.

Nowadays, people are using nanometer-sized transistors and gigahertz clock frequency in VLSI design. In such extreme circumstances, timing, power, manufacturability and reliability are all crucial issues. Routing  connects the devices on the chip, which is usually automatically performed by software due to its large scale and high complexity. Tree structure is the major topology used in VLSI routing. Optimising the tree and the forest is essential for a successful automatic VLSI design flow.

However, the problems are generally challenging. First, even for many single-net routing problems, finding a quality tree from a huge candidate forest is already difficult. Second, for multiple-net routing, a large number of trees need to be built on the chip by sharing resources and they need to be well coordinated to avoid conflicts. Third, in order to achieve a full-flow success, it is also necessary to foresee the routing trees and to consider routability in the early stages, such as the placement stage.

Supervised by Professor Evangeline F. Y. Young, Mr. Chen Gengjie together with his labmates devises efficient and effective algorithms to tackle the three levels of challenges with not only practical considerations for VLSI design but also mathematical rigour and guarantee. Their research has been recognised by championships and runners-up in several international contests as well as the Best Paper Award from the International Conference on Computer-Aided Design (ICCAD).