Optimisation of Global Routing for the UK5000 Gate Array by Iteration

A global router which has been developed for the UK5000 gate array is described. The algorithm employed treats all nets in parallel. It solves the problem set by the channels having fixed capacity by using cumulative weighting to direct connections away from regions of wiring congestion. It is shown that the convergence process is stable, that high channel utilisation can be accommodated and that the first pass of the process can be used to provide a measure of the quality of placement and of the ultimate solubility of the routing for a given circuit application.