Fast Evaluation of Bounded Slice-Line Grid  

作　　者：SongChen Xian-LongHong She-QinDong Yu-ChunMa Chung-KuanCheng JunGu 

机构地区：[1]DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084,P.R.China [2]DepartmentofComputerScienceandEngineering,UniversityofCalifornia,SanDiego,U.S.A. [3]DepartmentofComputerScience,HongKongUniversityofScienceandTechnology,P.R.China

出　　处：《Journal of Computer Science & Technology》2004年第6期973-980,共8页计算机科学技术学报（英文版）

基　　金：国家自然科学基金，香港研究资助局资助项目，美国国家自然科学基金，国家高技术研究发展计划(863计划)

摘　　要：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 in O(n log log n) time, where n 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 in O(n log log n) time. As a consequence, the evaluation of the BSG is completed in O(n log log n) time, where n is the number of blocks. The proposed algorithm is much faster than the previous graph-based O(n(2)) algorithm. The experimental results demonstrate the efficiency of the algorithm.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 in O(n log log n) time, where n 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 in O(n log log n) time. As a consequence, the evaluation of the BSG is completed in O(n log log n) time, where n is the number of blocks. The proposed algorithm is much faster than the previous graph-based O(n(2)) algorithm. The experimental results demonstrate the efficiency of the algorithm.

关 键 词：BSG FLOORPLAN PLACEMENT VLSI 

分 类 号：TN402[电子电信—微电子学与固体电子学]