Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Multilayer grid embeddings for VLSI

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

In this paper we propose two new multilayer grid models for VLSI layout, both of which take into account the number of contact cuts used. For the first model in which nodes “exist” only on one layer, we prove a tight area × (number of contact cuts) = Θ(n 2) tradeoff for embeddingn-node planar graphs of bounded degree in two layers. For the second model in which nodes “exist” simultaneously on all layers, we give a number of upper bounds on the area needed to embed groups using no contact cuts. We show that anyn-node graph of thickness 2 can be embedded on two layers inO(n 2) area. This bound is tight even if more layers and any number of contact cuts are allowed. We also show that planar graphs of bounded degree can be embedded on two layers inO(n 3/2(logn)2) area.

Some of our embedding algorithms have the additional property that they can respect prespecified grid placements of the nodes of the graph to be embedded. We give an algorithm for embeddingn-node graphs of thicknessk ink layers usingO(n 3) area, using no contact cuts, and respecting prespecified node placements. This area is asymptotically optimal for placement-respecting algorithms, even if more layers are allowed, as long as a fixed fraction of the edges do not use contact cuts. Our results use a new result on embedding graphs in a single-layer grid, namely an embedding ofn-node planar graphs such that each edge makes at most four turns, and all nodes are embedded on the same line.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A. Aggarwal, M. Klawe, D. Lichtenstein, N. Linial, and A. Wigderson, Multi-layer grid embeddings,Proc. IEEE 26th Anna. Symp. Foundations of Computer Science, 1985, pp. 186–196.

  2. A. Aggarwal, M. Klawe, D. Lichtenstein, N. Linial, and A. Wigderson, A Lower Bound on the Area of Permutation Layouts,Algorithmica, to appear.

  3. N. K. Bose and K. A. Prabhu, Thickness of Graphs with Degree Constrained Vertices,IEEE Trans. Circuits and Systems,24, (1977), 184–190.

    Article  MATH  MathSciNet  Google Scholar 

  4. F. R. K. Chung, On Concentrators, Superconcentrators, Generalizers and Non-blocking Networks,Bell Systems Tech. J.,58 (1978), 1765–1777.

    Google Scholar 

  5. R. Cori and J. Hardouin-Duparc, Manipulation des Cartes Planaires a Partir de leur Codage, Département de Mathématiques, Université de Bordeaux, Talence, France, 1975.

    Google Scholar 

  6. M. Cutler and Y. Shiloach, Permutation Layout,Networks,8 (1978), 253–278.

    Article  MATH  MathSciNet  Google Scholar 

  7. D. Dolev, F. T. Leighton, and H. Trickey, Planar Embeddings of Planar Graphs,Advances in Computing Research, Vol. 2, JAI Press, Greenwich, CT, 1984, pp. 147–161.

    Google Scholar 

  8. P. Eades and R. Tamassia, Algorithms for Automatic Graph Drawing: An Annotated Bibliography, Technical Report No. 82, Computer Science Department, University of Queensland, 1987.

  9. D. Greene, Drawing Planar Graphs and Their Duals, Technical Report, XEROX PARC 1983

  10. D. S. Johnson, NP-Completeness Column,J. Algorithms,3 (1982), 391.

    Google Scholar 

  11. Y. Kajitani, On Via Hole Minimization of Routings on a Two-Layer Board, Technical Report, Department of Electrical Engineering, Tokyo Institute of Technology, 1980.

  12. E. S. Kuh, T. Kashiwabara, and T. Fujisawa, On Optimum Single Row-Routing,IEEE Trans. Circuits and Systems,26, (1979), 361–368.

    Article  MATH  MathSciNet  Google Scholar 

  13. F. T. Leighton, Layouts for the Shuffle-Exchange Graph and Lower Bound Techniques for VLSI, Ph.D. Thesis, Department of Mathematics, Massachusetts Institute of Technology, 1981.

  14. F. T. Leighton, A Layout Strategy Which Is Provably Good,Proc. 14th Annu. ACM Symp. on the Theory of Computing, 1982, pp. 85–92.

  15. F. T. Leighton, New Lower Bound Techniques for VLSI,Math. Systems Theory,17 (1984), 47–70.

    Article  MATH  MathSciNet  Google Scholar 

  16. F. T. Leighton, Personal communication.

  17. C. E. Leiserson, Area Efficient Graph Layouts (for VLSI),Proc. 21st Annu. IEEE Symp. on Foundations of Computer Science, 1980, pp. 270–281.

  18. R. J. Lipton and R. E. Tarjan, A Separator Theorem for Planar Graphs,SIAM J. Appl. Math.,36 (1979), 177–189.

    Article  MATH  MathSciNet  Google Scholar 

  19. R. J. Lipton and R. E. Tarjan, Applications of a Planar Separator Theorem,SIAM J. Comput.,9 (1980), 615–627.

    Article  MATH  MathSciNet  Google Scholar 

  20. J. Makowsky, On the Complexity of Certain Decision Procedures for Propositional Calculus and Random Graphs, undated preprint, Free University, Berlin and Hebrew University, Jerusalem.

  21. A. Mansfield, Determining the thickness of graphs is NP-hard,Math. Proc. Cambridge Philos. Soc., to appear.

  22. C. A. Mead and L. A. Conway,Introduction to VLSI Systems, Addison Wesley, Reading Ma, 1980.

    Google Scholar 

  23. G. Miller, Finding Small Simple Cycle Separators for 2-Connected Planar Graphs,Proc. 16th Annu. ACM Symp. on Theory of Computing, 1984, pp. 369–376.

  24. M. S. Paterson, Universal Chains and Wiring Layouts, Technical Report, Department of Computer Science, University of Warwick, England, August 1986.

    Google Scholar 

  25. J. Peterson, Die Theorie der regulaeren Graphen,Acta Math.,15 (1891), 193–220.

    Article  MathSciNet  Google Scholar 

  26. R. Rivest, The Placement and Interconnect System,Proc. 19th Design Automation Conference, 1982, pp. 475–481.

  27. P. Rosenstiehl and R. E. Tarjan, Rectilinear Planar Layouts and Bipolar Orientations of Planar Graphs,Discrete Comput. Geom.,1 (1986), 343–353.

    Article  MATH  MathSciNet  Google Scholar 

  28. Y. Shiloach, Linear and Planar Arrangement of Graphs, Ph.D. Dissertation, Weizmann Institute, Rehovot, Israel, 1976.

    Google Scholar 

  29. I. Shirakawa, Letter to the Editor: Some Comments on Permutation Layout,Networks,10, (1980), 179–182.

    Article  Google Scholar 

  30. H. C. So, Some Theoretical Results on the Routing of Multilayer Printed Wiring Boards,Proc. 1974 IEEE Internat. Symp. on Circuits and Systems, pp. 296–303.

  31. C. D. Thompson, A Complexity Theory for VLSI, Ph.D. Dissertation, Carnegie-Mellon University, 1980.

  32. B. S. Ting, E. S. Kuh, and I. Shirakawa, The Multilayer Routing Problem: Algorithms and Necessary and Sufficient Conditions for the Single-Row Single Layer Case,IEEE Trans. Circuits and Systems,23, 12 (1979), 768–778.

    Article  MathSciNet  Google Scholar 

  33. S. Tsukiyama and E. S. Kuh, Double-Row Planar Routing and Permutation Layout,Networks,12 (1982), 287–316.

    Article  MATH  MathSciNet  Google Scholar 

  34. L. G. Valiant, Universality Considerations in VLSI,IEEE Trans. Comput.,30, 2 (1981), 135–140.

    MATH  MathSciNet  Google Scholar 

  35. H. Whitney, A Theorem on Graphs,Ann. of Math.,32 (1931), 378–390.

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IBM T. J. Watson Research Center, P.O. Box 218, 10598, Yorktown Heights, NY, USA

    Alok Aggarwal

  2. IBM Almaden Research Center, 650 Harry Road, 95120-6099, San Jose, CA, USA

    Maria Klawe

  3. A.T.&T. Bell Laboratories, 600 Mountain Avenue, 07974, Murray Hill, NJ, USA

    Peter Shor

Authors
  1. Alok Aggarwal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Maria Klawe
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Peter Shor
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by F. Thomson Leighton.

The first author's research was partially supported by NSF Grant No. MCS 820-5167.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Aggarwal, A., Klawe, M. & Shor, P. Multilayer grid embeddings for VLSI. Algorithmica 6, 129–151 (1991). https://doi.org/10.1007/BF01759038

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01759038

Key words

Search

Navigation