Fast Evaluation of Bounded Slice-Line Grid

Bounded Slice-line Grid (BSG) is an elegant representation of block placement, because it is very intuitionistic and has the advantage of handling various placement constraints. However, BSG has attracted little attention because its evaluation is very time-consuming. This paper proposes a simple algorithm independent of the BSG size to evaluate the BSG representation inO (n log logn) time, wheren is the number of blocks. In the algorithm, the BSG-rooms are assigned with integral coordinates firstly, and then a linear sorting algorithm is applied on the BSG-rooms where blocks are assigned to compute two block sequences, from which the block placement can be obtained inO (n log logn) time. As a consequence, the evaluation of the BSG is completed inO (n log logn) time, wheren is the number of blocks. The proposed algorithm is much faster than the previous graph-basedO (n 2) algorithm. The experimental results demonstrate the efficiency of the algorithm. This work is supported by the National Natural Science Foundation of China (Grant Nos.90307005 and 60121120706), Hong Kong RGC Joint Project No.60218004, the National Natural Science Foundation of USA (Grant No. CCR-0096383) and the National Hi-Tech Development 863 Program of China (Grant No.2002AA1Z1460). Song Chen received the B.S. degree in computer science from Xi'an Jiaotong University in 2000. Since then, he has been a Ph.D. candidate in the Department of Computer Science and Technology, Tsinghua University. His research interests include VLSI layout algorithms and analog and mixedsignal system layout algorithms. Xian-Long Hong is a fellow of IEEE and a senior member of Chinese Institute of Electronics. He graduated from Tsinghua University, 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. She-Qin Dong received the B.S. degree (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 Institute of Technology. From 1997 to 1999, he worked as a postdoctoral fellow in the State Key Lab. of CAD&CG in 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. Yu-Chun Ma received B.S. degree in computer science from Xi'an Jiaotong University in 1999 and she is currently a Ph.D. candidate of the Department of Computer Science and Technology, Tsinghua University. Her research interests include algorithms for VLSI automation design, especially floorplanning. Chung-Kuan Cheng received the B.S. and M.S. degrees in electrical engineering from “Taiwan University”, and the Ph.D. degree in electrical engineering and computer science from the University o