作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2006, Vol. 32 ›› Issue (14): 11-13. doi: 10.3969/j.issn.1000-3428.2006.14.004

• 博士论文 • 上一篇    下一篇

一种自适应多层无网格布线算法

谢满德   

  1. 浙江工商大学计算机与信息工程学院,杭州 310035
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2006-07-20 发布日期:2006-07-20

A Self-adaptive Multi-layer Gridless Routing Algorithm

XIE Mande   

  1. College of Computer and Information Engineering, Zhejiang Gongshang Univ., Hangzhou 310035
  • Received:1900-01-01 Revised:1900-01-01 Online:2006-07-20 Published:2006-07-20

摘要: 为适应多布线层,采用非均匀网格图模型,引入了一种自适应迭代策略,将多层布线转化为多次两层布线来处理,既能适应任意布线层数,又大大减少了多层迷宫布线的搜索空间;针对非均匀网格图模型的特点,提出了优化的绕障长度的迷宫布线算法。实验数据显示算法具有较快的搜索速度和较好的布线质量。

关键词: 无网格布线, 详细布线, 迷宫算法

Abstract:

A non-uniform-grid graph model is introduced and a self-adaptive iterative algorithm is presented for multi-layer gridless area routing. The algorithm can not only handle the case in which the number of metal layers is uncertain but also greatly reduce the search space of multi-layer maze routing by converting multi-layer into multiple two-layer pairs. Based on the feature of non-uniform-grid graph, the optimal maze routing algorithm, which generates the shortest length by steering clear of obstacles, is employed. The experiment data shows the algorithm has rapid search speed and better routing quality.

Key words: Gridless routing, Detailed routing, Maze algorithm