X-routing using two Manhattan route instances

In deep sub-micron (DSM) technologies, wire delays comprise a dominant fraction of the total delay of a design. As a consequence, routing techniques which reduce the total wire length of a design are highly relevant to such technologies. One such approach which holds promise is that of non-Manhattan routing (or X routing). In this paper, we describe a technique to perform non-Manhattan routing by combining the results of two related Manhattan routing instances. The first is a regular, unrotated routing instance. The second routing instance is derived from the first by rotating the coordinate system by 45°. Both instances are routed on the same pair of metal layers. By selectively combining the results of the two instances, we obtain a final routing result that contains non-Manhattan wire segments. Our approach utilizes a powerful Floyd-Warshall based engine to combine the results of the two instances. We demonstrate that our router produces highly efficient results, reducing the total wire length by an average of about 20% (31%) over the unrotated (rotated) results, with a via-count decrease of between 4% (43%).