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.