A new global router based on a flow model and linear assignment

Abstract

A novel heuristic for global routing in graphs is developed. Based on a flow model it can handle many nets simultaneously, thus reducing the net ordering problem. To demonstrate the validity of the method it was applied to standard cell design style. For this application the authors combined the flow model approach with linear assignment to achieve a hierarchical global routing scheme. This procedure is about six times faster than the old flat net by net global router, while producing denser layouts for the majority of testcases. Good quality was achieved in comparison with the TimberwolfSC version 5.4 global router.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>