Congestion Reduction in Traditional and New RoutingArchitecturesAmeya R. Agnihotri Patrick H. MaddenState University of New York at BinghamtonComputer Science Department [email protected] dense integrated circuit designs, management of routing con-gestion is essential; an over congested design may be unroutable.Many factors influence congestion: placement, routing, and routingarchitecture all contribute. Previous work has shown that differentplacement tools can have substantially different demands for eachrouting layer; our objective is to develop methods that allow “tun-ing” of interconnect topologies to match routing resources.We focus on congestion minimization for both Manhattan andnon-Manhattan routing architectures, and have two main contribu-tions. First, we combine prior heuristics for non-Manhattan Steinertrees and Preferred Direction Steiner trees into a hybrid approachthat can handle arbitrary routing directions, via minimization, andlayer assignment of edges simultaneously. Second, we present aneffective method to adjust Steiner tree topologies to match rout-ing demand to resource, resulting in lower congestion and betterroutability.Categories and Subject DescriptorsJ.6 [Computer-Aided Engineering]: CADGeneral TermsAlgorithmsKeywordsGlobal routing, non-Manhattan design, Steiner trees, congestion1. INTRODUCTIONCongestion minimization for dense integrated circuits has beenwidely studied. Informally, congestion is the ratio of routing de-mand (interconnect wire) to available routing resource (open space);an over congested design may be unroutable, or can require longrouting detours that impact circuit speed.In this paper, we study routing congestion for both traditionalManhattan routing architectures, and also for non-Manhattan ar-chitectures that have recently attracted interest. We focus on meth-ods to optimize tree topologies and layer assignments to obtain lowPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.GLSVLSI’03, April 28–29, 2003, Washington, DC, USA.Copyright2003ACM1-58113-677-3/03/0004...$5.00.total wire length, low numbers of vias, and routing demand thatmatches available resources.The remainder of this paper is organized as follows. We firstbriefly discuss routing architectures, Steiner tree heuristics, andglobal routing. We also describe congestion metrics and the in-teractions between routing architectures and placement. Next, wepresent our main contributions: a combined non-Manhattan Pre-ferred Direction Steiner tree heuristic and an approach to adjustSteiner tree topologies such that routing demand matches availableresources. We conclude with a summary and a discussion of currentand future work.2. PRIOR WORKThere is an abundance of work on circuit routing and intercon-nect optimization. We briefly summarize this work.Routing ArchitecturesAn obvious issue in congestion minimization is the choice ofrouting architecture. In traditional design, individual layers have“preferred direction;” all (or almost all) wires on a given layer areoriented either horizontally or vertically. The directions on eachlayer usually alternate, and the minimum width wire on the lowerlayers is usually thinner than on upper layers.While Manhattan routing architectures have dominated circuitdesign, there is growing interest in non-Manhattan architectures.First proposed as a method to address modern interconnect delayproblems in [10], non-Manhattan routing is now championed bythe X Initiative[1], an industry consortium that is advocating rout-ing at 45 degree increments (the “X Architecture”). We use theterminology of [10], and refer to this as “octilinear” routing. In[10], routing at 60 degree increments was also discussed; there isalso growing interest in this “hexagonal” routing approach[6].With all routing metrics, there is the requirement of vias betweenlayers. These vias have non-zero cost, and connections from lowerlayers to upper ones create obstacles on the intermediate layers.Each routing metric offers different routing resources; tuning rout-ing demand to match resource is one focus of this paper. The threerouting architectures we focus on are illustrated in Figure 1.Steiner Algorithms and Layer AssignmentThe problem of interconnecting a set of points on an integratedcircuit is a variation of the classic Steiner problem. Well knownmethods for this include the 1-Steiner heuristic[9] and the edge-removal tree method[4]. Both works obtain Steiner trees that areclose to optimal in practice. While the underlying problem is NP-Complete, an approach that can handle relatively large planar prob-lems has been developed[11].Most Steiner tree algorithms use a planar formulation, and areintegrated into routing applications by adding a “layer assignment”step. In general, “global” wires are placed on upper layers, while211Manhattan (90 degreesbetween axis)Hexagonal (60 degreesbetween axis)Octagonal (45 degreesbetween axis)Figure 1: Manhattan, hexagonal, and octagonal routing met-rics. While the bulkof VLSI routing is performed using a Man-hattan metric, other routing architectures are possible.“local” wires reside on lower layers. There is good motivation forthis approach: by placing longer wires on upper layers, the avail-able resource of those layers can be used without requiring largenumbers of vias These issues are discussed in greater detail by [12].The edge-removal heuristic[4] has been adapted to simultaneouslyconsider layer assignment and via cost[15].While the bulk of work related to circuit design has focused onrectilinear formulations, some results have been obtained for non-Manhattan routing architectures[10, 8, 11].Congestion Minimization in Global RoutingCongestion minimization is one of the primary objectives of globalrouting. Each connection may have multiple possible paths, and byselecting an appropriate set, the routing demand in any given areacan be reduced.Many global routing tools share a common framework; a shortestpath algorithm (such as Dijkstra’s[7]) can be used to find a path fora single connection. If routing demand exceeds resources, “rip-up and