%0 Journal Article
%T An Optimum Placement Search Algorithm Based on Extended Corner Block List
%A Dong Sheqin
%A Zhou Shuo
%A Hong Xianlong
%A Cheng Chungkuan
%A Gu Jun
%A Cai Yici
%A <br>董社勤
%A 周硕
%A 洪先龙
%A 陈中宽
%A 顾钧
%A 蔡懿慈
%J 计算机科学技术学报
%D 2002
%I 
%X 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 th
%K corner block list
%K bounded slice-line grid
%K floorplanning
%K placement
%K HCG
%K VCG<br>VLSI
%K 超大规模集成电路
%K 设计
%K 平面布置图
%K 最佳布置寻找算法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=D4D1086184F571E5C2913C57FFB2F162&yid=C3ACC247184A22C1&vid=BCA2697F357F2001&iid=B31275AF3241DB2D&sid=2B25C5E62F83A049&eid=2B25C5E62F83A049&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=3&reference_num=10