High-performance Routing at the Nanometer Scale

Abstract — In this work we describe significant improvements to core routing technologies and outperform the best results from the ISPD ‘07 Global Routing Contest, as well as previous literature, in terms of route completion, runtime and total wirelength. In particular, our router, FGR, improves upon wirelengths produced by BoxRouter and MaizeRouter in March 2007 by 9.9 % and 8.4%, respectively. Additionally, we reveal the mathematical basis of negotiated-congestion routing, offer comprehensive analysis of existing routing techniques and discuss several applications at the nanometer scale. 1