Two-dimensional router for double layer layout

ABSTRACT

A heuristic algorithm for two dimensional routing utilizing two distinct layers is presented. It is assumed that all terminals are on the boundary of a rectilinear routing region with or without initial routes present. The router produces a Manhattan-style routing collapsed into one layer. Another program decides the layering, however, it is not described here. By default, when the layering program is not used, vertical segments of routes are placed on one layer, horizontal on the other.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing; Layout

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

  J. Computer Applications

General Terms:
Algorithms, Design, Performance, Theory