基于序列对表示的对齐约束模块布局算法
作者:
基金项目:

Supported by the National Education Promotion Project (Tsinghua) under Grant No.Jc2001025 (国家教育振兴计划(清华)); the National Natural Science Foundation of China under Grant No.60076016 (国家自然科学基金); the National Grand Fundamental Research 973 Program of China under Grant No.G1998030403 (国家重点基础研究发展规划(973)


A Block Placement Algorithm with Predefined Coordinate Alignment Constraint Based on Sequence Pair Representation
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [13]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    在片上系统(SOC)的设计中,常常需要把某些单元摆放在某一预定坐标线附近相对较小的区域内.这一约束的来源是,在总线结构中,通过总线传递的数据,应当同步地出现在总线上,不能有较大的时延.对带有预定坐标线对齐(PCA)约束的模块布局问题进行研究,导出了约束模块之间的一系列关系,由此得到满足约束布局的必要条件.并且设计了多项式时间复杂度的算法,能够确保得到可行的模块布局.使用ami33和ami49对该算法进行了测试.实验结果证明,算法是有效的.

    Abstract:

    In the system on a chip, some cells should be placed along a predefined coordinate within a relatively small region. This constraint comes from the requirement that the data should be ready on the common bus at the same time. In this paper, the module placement problem is studied where some modules have the predefined coordinate alignment (PCA) constraint. The relations are given between constrained modules, from which a necessary condition is induced. A polynomial-time algorithm is developed that can guarantee a feasible placement is always obtainable. The algorithm is implemented and tested on ami33 and ami49. The experimental results show that it is effective.

    参考文献
    [1]Otten R. Automatic floorplan design. In: Proceedings of the 19th ACM/IEEE Design Automation Conference. 1982. 261~267.
    [2]Wong DF, Liu CL. A new algorithm for floorplan design. In: Proceedings of the 23rd ACM/IEEE Design Automation Conference. 1986. 191~107.
    [3]Murata H, Fujiyoshi K, Nakatake S, Kajitani Y. Rectangle-Packing-Based module placement. In: Proceedings of the IEEE International Conference Computer-Aided Design. 1995. 472~479.
    [4]Murata H, Fujiyoshi K, Nakatake S, Kajitani Y. VLSI module placement based on rectangle-packing by the sequence pair. IEEE Transactions on Computer-Aided Design, 1996,15(11):1518~1524.
    [5]Nakatake S, Fujiyoshi K, Murata H, Kajitani Y. Bounded-Slicing structure for module placement. Technical Report, Institute of Electronics, Information, and Communication Engineers (IEICE), 1994,VLD94(313):19~24.
    [6]Nakatake S, Fujiyoshi K, Murata H, Kajitani Y. Module placement on BSG-structure and IC layout applications. In: Proceedings of the IEEE International Conference Computer-Aided Design. 1996. 484~491.
    [7]Hong XL, Huang G, et al. Corner block list: An effective and efficient topological representation of non-slicing floorplan. In: Proceedings of the IEEE International Conference Computer-Aided Design 2000. 2000.
    [8]Guo PN, Cheng CK, Yoshimura T. An O-tree representation of non-slicing floorplan and its applications. In: Proceedings of the 36th ACM/IEEE Design Automation Conference. 1999. 268~273.
    [9]Tang XP, Wong DF. FAST-SP: A fast algorithm for block placement based on sequence pair. In: Proceedings of the ASP-DAC. 2001, 521~526.
    [10]Murata H, Fujiyoshi K, Daneko M. VLSI/PCB placement with obstacles based on sequence pair. IEEE Transactions on Computer-Aided Design, 1998,17(1).
    [11]Lai JB, Lin MS, Wang TC, Wang LC. Module placement with boundary constraints using the sequence-pair representation. In: Proceedings of the ASP-DAC. 2001. 515~520.
    [12]Sawa T, Nagao A, Kambe T, Shirakawa I, Chihara K. A method for rectangle packing problem. IEICE Technical Report, CAS97-38, VLD97-38, DSP97-53, 1997. 159~166 (in Japanese).
    [13]Nagao A, Kambe T, Shirakawa I. A layout approach to monolithic microwave IC. In: Proceedings of the 1998 ISPD. 1998. 65~72.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

刘锐,洪先龙,董社勤,顾钧.基于序列对表示的对齐约束模块布局算法.软件学报,2003,14(8):1418-1424

复制
分享
文章指标
  • 点击次数:4170
  • 下载次数: 5389
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2002-04-01
  • 最后修改日期:2002-04-01
文章二维码
您是第19794085位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号