期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

用角轮廓结构实现基于O-Tree表示法的模块快速放置算法

Fast Module Packing Algorithm Using Corner Contour Based on O-Tree Representation
下载PDF
导出
摘要 在VLSI物理设计中,O-Tree是一种高效简洁的布局表示法,但其对应的模块放置算法因为基于水平和垂直约束图及其操作而复杂且费时(算法时间复杂度为O(n2)).文中算法利用模块放置过程中右上端边沿形成的角轮廓结构的阶梯下降性,结合O-Tree编码结点间的父子关系,快速确定模块的放置位置.在模块的放置过程中不需要约束图,只保持一个角轮廓,使模块的放置更加简单高效,算法时间复杂度降低为O(nlogn).在MCNC Benchmark上的实验结果验证了该算法的有效性. In VLSI physical design, O-Tree is regarded as one of the most effective and efficient placement/floorplan representations. However, its induced packing algorithms are complicated and time-consuming, because of their horizontal and vertical constraint graphs and involved operations. Based on stairway up-down characteristic of corner-contour, the proposed algorithm in this paper utilizes parent-son relationship embodied in a given O-Tree code to facilitate module placement. There is only one corner-contour being kept during packing, no constraint graphs and related operations are required. The time complexity of the proposed algorithm can be reduced to O（n log n）. Experimental results on MCNC Benchmarks verified the effectiveness of the our algorithm.
作者 李康 虞厥邦 于永斌
机构地区 电子科技大学电子工程学院
出处 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2008年第10期1297-1302,共6页 Journal of Computer-Aided Design & Computer Graphics
基金 国家“八六三”高技术研究发展计划(2006AA01Z173,2007AA01Z131)
关键词 VLSI物理设计 布局 O-Tree表示法 角轮廓 放置算法 VLSI physical design placement O-Tree representation corner contour packing algorithm
分类号 TP391.7 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献15

  • 1Murata H, Fujiyoshi K, Nakatake S, et al. VLSI module placement based on rectangle-packing by the sequence pair [J]. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 1996, 15(12): 1518-1524
  • 2Nakatake S, Fujiyoshi K, Murata H, et al. Module placement on BSG structure and IC layout applications [C]// Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, San Jose, 1996:484-491
  • 3Hong X L, Huang G, Cai Y C, etal. Corner block list: an effective and efficient topological representation of non-slicing floorplan [C] //Proceedings of the IEbZE/ACM International Conference on Computer-Aided Design, San Jose, 2000: 8- 12
  • 4Guo P N, Cbeng C K, Yoshimura T. An O-Tree representation of non slicing floorplan and its applications [C]//Proceedings of the 36th ACM/IEEE Design Automation Conference, New Orleans, 1999:268-273
  • 5Chang Y C, Chang Y W, Wu G M, etal. B*-tree: a new representation for non-slicing floorplans [C]//Proceedings of the 37th ACM/IEEE Design Automation Conference, Los Angeles, 2000:458-464
  • 6Lin J M, Chang Y W. TCG: a transitive closure graph-based representation for non slicing floorplans [C] //Proceedings of the 38th ACM/IEEE Design Automation Conference, Las Vegas, 2001:764-769
  • 7Lin J M, Chang Y W, Lin S P. Corner sequence-a P admissible floorplan representation with a worst case linear-time packing scheme [J]. IEEE Transactions on Very Large Integration Systems, 2003, 11(4): 679-686
  • 8Kajitani Y. Theory of placement by numDAG related with single-sequence, SP, BSG, and O-Tree[C] //Proceedings of the IEEE International Symposium on Circuit and System, Island of Kos, 2006:4471-4474
  • 9Yan T, Li J, Yang B, et al. A modified O-Tree based packing algorithm and its applications [C]//Proceedings of the International Conference on Communication, Circuit and System, Chengdu, 2004:1266-1270
  • 10Ma Y C, Hong X L, Dong S Q, et al. Stairway compaction using corner block list and its applications with rectilinear blocks [C] //Proceedings of the 15th International Conference on VLSI Design, Bangalore, 2002:387-392

二级参考文献13

  • 1Guo P N,Cheng C K,Yoshimura T.An O-tree representation of non-slicing floorplan and its applications[A].Proceedings of the 36^th Design Automation Conference[C].CA,USA:ACM/IEEE,1999.
  • 2Murata H,Fujiyoshi S,Nakatake S,et al.VLSI module placement based on rectangle-packing by the sequencepair[J].IEEE Trans On CAD,1996,15(12):1518-1524.
  • 3Sakanushi K,Kajitani Y.The quarter-state sequence (Q-sequence) to represent the floorplan and application to layout optimization[A].Proceedings of IEEE Asia-Pacific Conference on Circuits and Systems[C].Tokyo,Japan:ACM/IEEE,2000.
  • 4Hong X L,Dong S,Huang G,et al.Corner block list representation and its application to floorplan optimization[J].IEEE Trans On Circuits and Systems-Ⅱ,2004,51(5):228-233.
  • 5Chang Y C,Chang Y W,Wu G M,et al.B* -tree:A new representation for non-slicing floorplans[A].Proceedings of the 37th Design Automation Conference[C].CA,USA:ACM/IEEE,2000.
  • 6Murata H,Fujiyoshi K,Kaneko H.VLSI/PCB placement with obstacles based on sequence-pair[J ].IEEE Trans On CAD,1998,17(1):60-68.
  • 7Yingxin Pang, Balasa, F., Lampaert, K., Chung-Kuan Cheng.Block placement with symmetry constraints based on the O-tree non-slicing representation[J]. ACM/IEEE DAC,2000:464-467.
  • 8Rui Lu, Xianlong Hong, Sheqin Dong,YiciCai, Jun Gu.VLSI/PCB placement with predefined coordinate alignment constraint based on sequence pair[J].IEEE ISCAS,2001:167-170.
  • 9Xiaoping Tang,D.F. Wong. Floorplanning with alignment and performance constraints[J].ACM DAC,2002:848-853.
  • 10P.-N. Guo, C.-K. Cheng, T. Yoshimura.An O-tree representation of non-slicing floorplan and its applications[J]. ACM/IEEE DAC,1999:268-273.

共引文献3

计算机辅助设计与图形学学报
2008年 第10期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部