Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Simple three-layer channel routing algorithms

  • Compaction And Channel Routing
  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 319))

Included in the following conference series:

  • 179Accesses

Abstract

In this paper we present a simple three-layer assignment algorithm for planar layouts generated by a class of layout algorithms. This class of algorithms includes simple variations of the currently best algorithms for the three layer channel routing problem (CRP). More specifically, this class includes algorithms "equivalent" to the following algorithms (i–iii) developed by Mehlhorn, Preparata and Sarrafzadeh [7].

(i) The algorithm that generates planar layouts for the two-terminal net CRP withdmax tracks.

(ii) The algorithm that generates planar layouts for the two- and three-terminal net CRP with at most [3dmax/2] tracks.

(iii) The algorithm that generates planar layouts for the multi-terminal net CRP with at most 2dmax — 1 tracks.

The planar layouts generated by these algorithms and by their "equivalent" algorithms are three-layer wirable by the layer assignment algorithm given in [8]. Our approach is different. We make simple modifications to these layout algorithms and incorporate a simple wire assignment strategy to generate three-layer wirings under the knock-knee model. Consequently, we obtain simpler and faster algorithms that generate three-layer wirings with layouts similar to the ones generated by algorithms (i) – (iii). Our algorithms are faster and conceptually simpler because there is no need to construct diagonal diagrams and legal partitions. The channel width of the wiring generated by our algorithm is identical to that of the corresponding planar layout generated by algorithms (i) – (iii).

This research was supported in part by the National Science Foundation under Grant DCR - 8503163.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Bibliography

  1. Brady, M. L. and D. J. Brown, "VLSI Routing: Four Layers Suffice", Advances in Computing Research, vol. 2, 1984.

    Google Scholar 

  2. Gao, S. and M. Kaufmann, "Channel Routing of Multiterminal Nets", Proceedings of the 28th Symposium on Foundations of Computer Science, pp 316–325, 1987.

    Google Scholar 

  3. Gonzalez, T. and Zheng, S.-Q., "Wirability of Planar Layouts", Technical Report, # 87-11, CS Dept., UC Santa Barbara, Aug. 1987.

    Google Scholar 

  4. Gonzalez, T. and Zheng, S.-Q., "Three-Layer Channel Routing of Multi-terminal Nets", Technical Report, # 87-13, CS Dept., UC Santa Barbara, Aug. 1987.

    Google Scholar 

  5. Lipski, W. Jr, "An NP-complete Problem Related to Three-layer Channel Routing", Advances in Computing Research, vol. 2, 1984.

    Google Scholar 

  6. Mehlhorn, K. and F. P. Preparata, "Routing Through a Rectangle",J. ACM, vol. 33, no. 1, 1986.

    Google Scholar 

  7. Mehlhorn, K., F. P. Preparata and M. Sarrafzadeh, "Channel Routing in Knock-Knee Mode: Simplified Algorithms and Proofs",Algorithmica, no. 1, 1986.

    Google Scholar 

  8. Preparata, F. P and W. Lipski, Jr, "Optimal Three-layer Channel Routing",IEEE Transaction on Computer., vol. 33, no. 5, 1984.

    Google Scholar 

  9. Preparata, F. P. and M. Sarrafzadeh, "Channel Routing of Nets Bounded Degree",VLSI: Algorithms and Architectures, North-Holland, 1984.

    Google Scholar 

  10. Rivest, R. L., A. Baratz and G. Miller, "Provably Good Channel Routing Algorithms," in Proc. 1981 Carnegie-Mellon Conf on VLSI, Oct. 1981, pp. 153–159.

    Google Scholar 

  11. Sarrafzadeh, M. and F. P. Preparata, F. P., "Compact Channel Routing of Multiterminal Nets",Annals of Discrete Mathematics, no. 25, April 1985, pp. 255–279.

    Google Scholar 

Download references

Author information

Author notes

  1. Si-Qing Zheng

    Present address: Department of Computer Science, Louisiana State University, 70803-4020, Baton Rouge, Louisiana

Authors and Affiliations

  1. University of California, Santa Barbara

    Teofilo Gonzalez & Si-Qing Zheng

Authors
  1. Teofilo Gonzalez

    You can also search for this author inPubMed Google Scholar

  2. Si-Qing Zheng

    You can also search for this author inPubMed Google Scholar

Editor information

John H. Reif

Rights and permissions

Copyright information

© 1988 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Gonzalez, T., Zheng, SQ. (1988). Simple three-layer channel routing algorithms. In: Reif, J.H. (eds) VLSI Algorithms and Architectures. AWOC 1988. Lecture Notes in Computer Science, vol 319. Springer, New York, NY. https://doi.org/10.1007/BFb0040391

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp