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

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

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