Mr. Li Liang received the Outstanding Thesis Award 2010

Congratulation to Mr. Li Liang, a MPhil student supervised by Prof. Young Fung Yu, received the Outstanding Thesis Award 2010 for his thesis entitled "Obstacle-avoiding Rectilinear Steiner Tree".

Abstract: In today's VLSI designs, the obstacle-avoiding rectilinear Steiner minimum tree (OARSMT) problem has become an important problem in the physical design stage of VLSI circuits. This problem has attracted a lot of attentions in research and many approaches have been proposed to solve this problem. In this thesis, we will present our research and findings on this OARSMT problem. We try to solve this problem in two different ways. Our first approach is trying to obtain a good approximate solution to this OARSMT problem within a short time using heuristic. The second approach is trying to find optimal solutions in a reasonable amount of time.

Firstly, we will present a heuristic maze routing based approach to solve this OARSMT problem. It is commonly believed that maze routing based approaches can only handle small scale problems and there is a lack of an effective multi- terminal variant to handle multi-pin nets in practice. We show in this thesis that maze routing based approaches can also handle large scale OARSMT problems effectively. Our approach is based on the searching process as in maze routing and can handle multi-pin nets very well in both solution quality, running time and memory space usage. Up till now, our approach is the best among all the previous works in terms of wire length optimization.

Secondly, we try to solve this obstacle-avoiding rectilinear Steiner tree problem optimally. Our work is developed based on the GeoSteiner approach, modified and extended to allow rectilinear blockages in the routing regions. We extended the proofs on the possible topologies of full Steiner tree in [13] to allow blockages, which are the basic concept behind GeoSteiner. We can now handle hundreds of pins with multiple blockages, generating an optimal solution in a reasonable amount of time. This work serves as a pioneer in providing an optimal solution to this difficult problem.