Hexagonal minimum Steiner tree construction for Y architecture: A case of non-Manhattan routing

Construction of cost-effective global routing trees is one of the primary keys in today´s interconnect centric VLSI layout design under DSM (deep sub-micron) regime. In order to reduce the interconnect delay, traditional Manhattan (M-) routing architectures are currently being replaced by the diagonal X architectures. A recent routing architecture is based on Y interconnects, involving the pervasive use of 0°, 60°, and 120° oriented global and semi-global wirings. Unlike the X-routing, Y-routing is observed to support regular routing grid, which is important for simplifying manufacturing processes as well as for routing and design rule checking algorithms. In this paper, we propose a novel Y-routing algorithm that can solve reasonably sized problems in nominal time. Moreover, it can be easily extended for routing with any uniform orientation. Experimental results are quite encouraging and far better than the previously existing solution.