We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 17 Issue 6
November  2002
Turn off MathJax
Article Contents
Abstract
Related Articles
DONG Sheqin, ZHOU Shuo, HONG Xianlong. An Optimum Placement Search Algorithm Based on Extended Corner Block List[J]. Journal of Computer Science and Technology, 2002, 17(6).
Citation: DONG Sheqin, ZHOU Shuo, HONG Xianlong. An Optimum Placement Search Algorithm Based on Extended Corner Block List[J]. Journal of Computer Science and Technology, 2002, 17(6).
shu

An Optimum Placement Search Algorithm Based on Extended Corner Block List

More Information
  • Published Date: November 14, 2002
    Abstract
  • A non-slicing approach, Corner Block List (CBL), has been presented recently.Since CBL only can represent floorplans without empty rooms, thealgorithm based on CBL cannot get the optimum placement. In this paper,an extended corner block list, ECBLla, is proposed. It canrepresent non-slicing floorplan including empty rooms. Based on theoptimum solution theorem of BSG (bounded-sliceline grid), it is provedthat the solution space of ECBLn, where n is the number ofblocks, contains the optimum block placement with the minimum area. Aplacement algorithm based on ECBLla, whose solution space can becontrolled by setting la, the extending ratio, is completed. Whenla is set as n, the algorithm based on ECBLn is theoptimum placement search algorithm. Experiments show that lahas a reasonable constant range for building block layout problem, sothe algorithm can translate an ECBLla representation to itscorresponding placement in O(n) time. Experimental results on MCNCbenchmarks show promising performance with 7% improvement in wirelength and 2% decrease in dead space over algorithms based on CBL.Meanwhile, compared with other algorithms, the proposed algorithm canget better results with less runtime.
    • FullText(HTML)
    • References (0)
    • Relative Articles

  • Related Articles

    [1]Seong Woo Kwak, Jung-Min Yang. Optimal Checkpoint Placement on Real-Time Tasks with Harmonic Periods[J]. Journal of Computer Science and Technology, 2012, 27(1): 105-112. DOI: 10.1007/s11390-012-1209-0
    [2]Hui Dai, Qiang Zhou, Ji-Nian Bian. Multilevel Optimization for Large-Scale Hierarchical FPGA Placement[J]. Journal of Computer Science and Technology, 2010, 25(5): 1083-1091. DOI: 10.1007/s11390-010-1085-4
    [3]Feng Zeng, Zhi-Gang Chen. Cost-Sensitive and Load-Balancing Gateway Placement in Wireless Mesh Networks with QoS Constraints[J]. Journal of Computer Science and Technology, 2009, 24(4): 775-785.
    [4]Yu-Chun Ma, Xian-Long Hong, She-Qin Dong, C. K. Cheng, Jun Gu. General Floorplans with L/T-Shaped Blocks Using Corner Block List[J]. Journal of Computer Science and Technology, 2006, 21(6): 922-926.
    [5]Song Chen, Xian-Long Hong, She-Qin Dong, Yu-Chun Ma, Chung-Kuan Cheng, Jun Gu. Fast Evaluation of Bounded Slice-Line Grid[J]. Journal of Computer Science and Technology, 2004, 19(6).
    [6]DONG SheQin, HONG XianLong, WU YuLiang, GU Jun. Deterministic VLSI Block Placement Algorithm Using Less Flexibility First Principle[J]. Journal of Computer Science and Technology, 2003, 18(6).
    [7]HOU WenTing, HONG XianLong, WU WeiMin, CAI YiCi. FaSa: A Fast and Stable Quadratic Placement Algorithm[J]. Journal of Computer Science and Technology, 2003, 18(3).
    [8]Zhao Yu, Shi Jiaoying, He Zhijun. Synchronization-Oriented Placement and Retrieval Strategies for Delay-Sensitive Media Streams[J]. Journal of Computer Science and Technology, 1996, 11(2): 150-160.
    [9]Xu Jianguo, Gou Yuchai, Lin Zongkai. HEPAPS:A PCB Automatic Placement System[J]. Journal of Computer Science and Technology, 1992, 7(1): 39-46.
    [10]Klaus Buchenrieder. Standard-Cell Placement from Functional Descriptions[J]. Journal of Computer Science and Technology, 1991, 6(1): 37-46.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (16) PDF downloads (1535) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return