计算机应用 ›› 2013, Vol. 33 ›› Issue (04): 1136-1138.DOI: 10.3724/SP.J.1087.2013.01136

• 计算机软件技术 • 上一篇    下一篇

随程序规模动态调整的通道优化布线算法

胡开宝1,张毅坤1,赵明2   

  1. 1. 西安理工大学 计算机科学与工程学院,西安 710048
    2. 上海零一拼装信息技术有限公司,上海 200120
  • 收稿日期:2012-10-10 修回日期:2012-11-25 出版日期:2013-04-01 发布日期:2013-04-23
  • 通讯作者: 张毅坤
  • 作者简介:胡开宝(1987-),男,甘肃庆阳人,硕士研究生,主要研究方向:自动化软件测试与维护工具;张毅坤(1958-),男,陕西西安人,教授,博士,CCF高级会员,主要研究方向:软件工程、测试方法与工具;赵明(1978-),男,吉林人,硕士研究生,主要研究方向:软件可视化测试平台与工具。
  • 基金资助:

    陕西省教育厅教学改革重点项目(11J15)

Optimized channel routing algorithms for dynamically adjusting channel with the program size

HU Kaibao1,ZHANG Yikun1,ZHAO Ming2   

  1. 1. School of Computer Science and Engineering, Xi'an University of Technology, Xi'an Shaanxi 710048, China
    2. Shanghai Zero One Assembly Software Company Limited, Shanghai 200120, China
  • Received:2012-10-10 Revised:2012-11-25 Online:2013-04-23 Published:2013-04-01
  • Contact: ZHANG Yikun

摘要: 针对常规层次型布图算法在大规模程序中布线混乱的缺点,借鉴Sugiyama层次布局算法,提出了一种随着程序规模动态调整的通道优化布线算法。通过将节点的通道数目与程序规模建立函数关系,以解决现有算法在布图时出现的线路重叠和效率低下的问题;在布图中结合广义张量平衡思想,以减少交叉并实现布图的美观性;并根据调用节点之间的相对位置关系,给出了相应的线路分配和申请策略,实现了布线的有序性。实践证明,该算法能够提高布图效率,有效地减少交叉,实现节点的有序布线和实现简单等优点。

关键词: 软件可视化, 层次图, 广义张量平衡算法, 交叉最小化, 通道布线

Abstract: To solve the routing confusion of the conventional hierarchical layout algorithm in the large-scale program, based on the Sugiyama hierarchical layout algorithm, this paper proposed an optimized algorithm for channel routing, which dynamically adjusted the number of channel according to the program size. In order to solve the low efficiency and lines overlap, the algorithm built functional relationships between channel number and program size. And by using the generalized tensor balance algorithm to reduce the crossings and realize the artistic layout. The algorithm also gave the corresponding line distribution and application strategy in accordance with the relative positional relationship between the calling nodes to achieve the ordered routing. The experimental results show that the algorithm has greater layout efficiency. It can reduce the crossings effectively, realize clear layout and is easy to implement.

Key words: software visualization, hierarchical graph, generalized tensility balance algorithm, crossing minimization, channel routing

中图分类号: