一种带权动态调整的总体布线算法及其实现

本文对现有的总体布线方法及宏单元阵列总体布线问题进行了详细分析,提出了一种基于带权动态调整思想的适合于宏单元阵列一层半和双层版图模式的总体布线算法,其目标是合理地利用已确定的布线区域,使各线网均匀地分布在芯片上,获得尽可能高的布通率。

A Dynamic Global Routing Algorithm with weights and Its Implementation

This paper reports several global routing approaches and studies the problem of globalrouting in macro-cell gate array, and proposes a dynamic global routing algorithm with weightsfor both one and a half layer and double layer macro-cell gate array. Its aim is to distributeall interconnection requirements over routing channels evenly, so as to attain 100 percentintercon nections within a limited area. The algorithm consists of two phases: initial routingand rerouting.In order to minimize the maximum density among all channels, dynamic weightsare introduced to construct routing paths for all signal nets.This new approach makesthe whole routing procedure efficient and promotes routing completion.In rerouting phase,a novel method which determines the ordering of nets to be rerouted under the whole considerationis presented.It improves the efficiency of rerouting. Convergence process in rerouting isstable.The algorithm has been implemented in C on PCS 68000 microcomputer and experimentalresults are satisfactory.