An Optimum Placement Search Algorithm Based on Extended Corner Block List

A non-slicing approach,Corner Block List(CBL),has been presented recently.Since CBL only can represent floorplans without empty rooms,the algorithm based on CBL cannot get the optimum placement.In this paper,an extended corner block list,ECBLλ,is proposed.It can represent non-slicing floorplan including empty rooms.Based on the optimum solution theorem of BSG(bounded-sliceline grid),it is proved that the solution space of ECBLn,where n is the number of blocks,contains the optimum block placement with the minimum area.A placement algorithm based on ECBLλ,whose solution space can be controlled by setting λ,the extending ratio,is completed.Whenλ is set as n,the algorithm based on ECBLn is the optimum placement search algorithm.Experiments show that λ has a reasonable constant range for building block layout problem,so the algorithm can translate an ECBLλ representation to its corresponding placement in O(n) time,Experimental results on MCNC benchmarks show promising performance with 7% improvement in wire length and 2% decrease in dead space over algorthms based on CBL.Meanwhile,compared with other algorithms,the proposed algorithm can get better results with less runtime.

An optimum placement search algorithm based on extended Corner Block List

A non-slicing approach, Corner Block List (CBL), has been presented recently. Since CBL only can represent floorplans without empty rooms, the algorithm based on CBL cannot get the optimum placement. In this paper, an extended corner block list, ECBL_λ, is proposed. It can represent non-slicing floorplan including empty rooms. Based on the optimum solution theorem of BSG (bounded-sliceline grid), it is proved that the solution space of ECBL _n , wheren is the number of blocks, contains the optimum block placement with the minimum area. A placement algorithm based on ECBL_λ, whose solution space can be controlled by setting λ, the extending ratio, is completed. When λ is set asn, the algorithm based on ECBL _n is the optimum placement search algorithm. Experiments show that λ has a reasonable constant range for building block layout problem, so the algorithm can translate an ECBL_λ representation to its corresponding placement inO(n) time. Experimental results on MCNC benchmarks show promising performance with 7% improvement in wire length and 2% decrease in dead space over algorithms based on CBL. Meanwhile, compared with other algorithms, the proposed algorithm can get better results with less runtime. This work is supported by the National Natural Science Foundation (Grant No.60076016) and the NKBRSF (‘973’) of China (Grant No.G1998030403). DONG Sheqin received the B.S. degree (with the highest honors) in computer science in 1985, M.S. degree in semiconductor physics and device in 1988, and Ph.D. degree in mechantronic control and automation in 1996, all from Harbin nstitute of Technology. From 1997 to 1999, he worked as a postdoctoral fellow in the State Key Lab of CAD and CG, Zhejiang University. He is currently an associate professor at the Department of Computer Science and Technology of Tsinghua University. His current research interests include CAD for VLSI, parallel algorithms, multi-media ASIC and hardware design. SHOU Shuo graduated from Tsinghua University, She is now a Ph.D. candidate of UCSD. HONG Xianlong graduated from Tsinghua University, Beijing, China in 1964. Since 1988, he has been a professor in the Department of Computer Science and Technology, Tsinghua University. His research interests include VLSI layout algorithms and DA systems. He is a senior member of IEEE and Chinese Institute of Electronics. CHENG Chungkuan is an IEEE fellow. He received his Ph.D. degree from UC Berkeley in 1984. He is now a professor of UCSD. GU Jun received B.S. degree from University of Science and Technology, China in 1982 and Ph.D. degree from Utah University in 1989. He was a professor of Calgary University in Canada and currently he is a professor of the Department of Computer Science in Hong Kong University of Science and Technology. His research interests include optimization algorithm, local search and global optimization, and their application in VLSI CAD, system engineering, communication and multi-media fields. He is a chief scientist of the ‘973’ Key Foundation Research and Development Project “The Application Theories and High Performance Software in Information Technology” of China. CAI Yici received B.S. and M.S. degrees from Tsinghua University in 1983 and 1986 respectively. She has been an associate professor in the Department of Computer Science and Technology, Tsinghua University, Beijing, China. Her research interests include VLSI layout.