Routing L-shaped channels in nonslicing-structure placement

ABSTRACT

The concept of L-shaped channels was first introduced in RRDO [1] to generate a feasible routing order for nonslicing-structure placement in building-block layout design. This paper presents two approaches for the L-shaped channel-routing problem. In the Manhattan approach, only horizontal and vertical wires are used. The L-shaped channel is divided into two subchannels. The vertical subchannel will be routed first, then the horizontal subchannel will be routed by a special channel router which can handle fixed terminals on 3 sides. Since the routing constraints will change during the boundary movement, several iterations may be needed to complete the routing. In the non-Manhattan approach, 45 ° wires are used to preserve the routing constraints when the boundary is moved in the 45 ° direction. With all the vertical constraints substituted by 45 ° constraints, the L-shaped channel-routing problem can be directly mapped into the straight-type channel-routing problem. Horizontal or vertical extension wires are used to connect terminals on an indented boundary and to separate terminals which are too close to allow the generation of 45 ° wires. Experimental results show that both approaches provide good solutions to the L-shaped channel-routing problem.

REFERENCES

• 1: W.-M. Dai, T. Asano, and E. S. Kuh, "Routing region definition and ordering scheme for building-block layout," 1EEE Trans. Computer-Aided Design, vol. CAD-4, no. 3, pp. 189-197, July 1985.
• 2: A.S. LaPaugh and R.. Y. Pinter, "On minimizing channel density by lateral shifting," in Dig. Tech. Papers, 1EEE Int. Conf. Computer-Aided Design, Santa Clara, CA, November 1983, pp. 121-122.
• 3: H.H. Chen and E. S. Kuh, "A variable-width grid}ess channel router," in Dig. Tech. Papers, IEEE Int. Conf. Computer-Aided Design, Santa Clara, CA, November 1985, pp. 304-306.
• 4: H. H. Chen and E. S. Kuh, "Glitter: A grid}ess variable-width channel router," IEEE Trans. Computer-Aided Design, vol. CAD-5, no. 4, pp. 450-465, October 1986.
• 5: Ronald L. Rivest , Charles M. Fiduccia, A “greedy” channel router, Proceedings of the 19th conference on Design automation, p.418-424, January 1982
• 6: D. Braun, Extensions of channel routing techniques and the implementation of a standard-cell placement and routing system, U.C. Berkeley, Electronics Research Laboratory, Memorandum No. UCB/ERL M85/77, September 1985.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  C. Computer Systems Organization

General Terms:
Design, Experimentation, Measurement