SpringerLink
Log in

Graphs in VLSI circuits and systems

  • Chapter
  • First Online:
Graphs in VLSI

  • 610 Accesses

Abstract

Large scale VLSI systems are highly complex, combining a diverse range of expertise, such as device physics, circuit design, computer architecture, and physical design. Abstraction is an effective tool for managing the complexity of these integrated systems. The abstract models described in this chapter exclusively focus on information relevant to a specific design objective. A graph is an effective tool for managing the complexity of large scale VLSI systems. By reducing the complex components of a VLSI system into nodes and edges, the design effort can be concentrated on the key features of a system while discarding extraneous information. The significance of graph theory at every abstraction layer of the VLSI design process is discussed in this chapter. At the register transfer layer, register allocation is often achieved by graph coloring, minimizing the communication between the CPU and memory. Ordered binary decision diagrams and AND-inverter graphs enable efficient graph-based processing of logic circuits. Graph-based techniques, such as random walks and network flow theory, facilitate the circuit analysis process of VLSI systems. Physical design is greatly enhanced by applying graph optimization algorithms to circuit partitioning, floorplanning, placement, and routing.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 79.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info
Hardcover Book
USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. M. R. Garey and D. S. Johnson, “The Complexity of Near-Optimal Graph Coloring,” Journal of the ACM, Vol. 23, No. 1, pp. 43–49, January 1976.

    Article  MathSciNet  MATH  Google Scholar 

  2. P. E. Ceruzzi, “The Early Computers of Konrad Zuse, 1935 to 1945,” Annals of the History of Computing, Vol. 3, No. 3, pp. 241–262, September 1981.

    Article  MathSciNet  MATH  Google Scholar 

  3. C. F. O’Donnell, “Engineering for Systems using Large Scale Integration,” Proceedings of the Fall Joint Computer Conference, Vol. 1, pp. 867–876, December 1968.

    Google Scholar 

  4. B. W. Kernighan and S. Lin, “An Efficient Heuristic Procedure for Partitioning Graphs,” The Bell System Technical Journal, Vol. 49, No. 2, pp. 291–307, February 1970.

    Article  MATH  Google Scholar 

  5. C. Y. Lee, “An Algorithm for Path Connections and its Applications,” IRE Transactions on Electronic Computers, Vol. EC-10, No. 3, pp. 346–365, September 1961.

    Article  MathSciNet  Google Scholar 

  6. L. W. Nagel, “SPICE2: a Computer Program to Simulate Semiconductor Circuits,” Memorandum No. ERL-M520, University of California, Berkeley, May 1975.

    Google Scholar 

  7. C. Ho, A. Ruehli, and P. Brennan, “The Modified Nodal Approach to Network Analysis,” IEEE Transactions on Circuits and Systems, Vol. 22, No. 6, pp. 504–509, June 1975.

    Article  Google Scholar 

  8. R. Bairamkulov, T. Jabbari, E.G. Friedman, “QuCTS-single-flux quantum clock tree synthesis”. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 41(10), 3346–3358 (October 2022)

    Article  Google Scholar 

  9. R. Bairamkulov and E. G. Friedman, “Effective Resistance of Two-Dimensional Truncated Infinite Mesh Structures,” IEEE Transactions on Circuits and Systems I: Regular Papers, Vol. 66, No. 11, pp. 4368–4376, November 2019.

    Article  MathSciNet  MATH  Google Scholar 

  10. R. Bairamkulov, K. Xu, M. Popovich, J. S. Ochoa, V. Srinivas, and E. G. Friedman, “Power Delivery Exploration Methodology based on Constrained Optimization,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 39, No. 9, pp. 1916–1924, September 2020.

    Article  Google Scholar 

  11. R. E. Bryant, “Graph-Based Algorithms for Boolean Function Manipulation,” IEEE Transactions on Computers, Vol. C-35, No. 8, pp. 677–691, August 1986.

    Article  MATH  Google Scholar 

  12. H. Topcuoglu, S. Hariri, and M.-Y. Wu, “Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing,” IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 3, pp. 260–274, March 2002.

    Article  Google Scholar 

  13. J. B. Kruskal, “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem,” Proceedings of the American Mathematical Society, Vol. 7, No. 1, pp. 48–50, February 1956.

    Article  MathSciNet  MATH  Google Scholar 

  14. M. Hanan, “On Steiner’s Problem with Rectilinear Distance,” SIAM Journal on Applied Mathematics, Vol. 14, No. 2, pp. 255–265, March 1966.

    Article  MathSciNet  MATH  Google Scholar 

  15. R. Bairamkulov, A. Roy, M. Nagarajan, V. Srinivas, and E. G. Friedman, “SPROUT - smart power routing tool for board-level exploration and prototy**,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 41, No. 7, pp. 2263–2275, July 2022

    Article  Google Scholar 

  16. C. Mead and L. Conway, Introduction to VLSI Systems, Addison-Wesley, 1980.

    Google Scholar 

  17. E. Gray and D. Tall, “Abstraction as a Natural Process of Mental Compression,” Mathematics Education Research Journal, Vol. 19, No. 2, pp. 23–40, September 2007.

    Article  Google Scholar 

  18. C. Panara and M. R. Varney, Local Government in Europe: the ‘Fourth Level’ in the EU Multi-Layered System of Governance, Routledge, 2013.

    Book  Google Scholar 

  19. Council of State Governments, The Book of the States, Council of State Governments, 2019.

    Google Scholar 

  20. Y. Wang, Software Engineering Foundations: a Software Science Perspective, CRC Press, 2007.

    Book  MATH  Google Scholar 

  21. B. Leiner, R. Cole, J. Postel, and D. Mills, “The DARPA Internet Protocol Suite,” IEEE Communications Magazine, Vol. 23, No. 3, pp. 29–34, March 1985.

    Article  Google Scholar 

  22. Y. LeCun, Y. Bengio, and G. Hinton, “Deep Learning,” Nature, Vol. 521, No. 7553, pp. 436–444, May 2015.

    Article  Google Scholar 

  23. N. H. E. Weste and K. Eshraghian, Principles of CMOS VLSI Design: a Systems Perspective, Addison-Wesley Publishing, 1985.

    Google Scholar 

  24. M.-B. Lin, Introduction to VLSI Systems: a Logic, Circuit, and System Perspective, CRC Press, 2011.

    Book  Google Scholar 

  25. C. H. Sequin, “Managing VLSI Complexity: an Outlook,” Proceedings of the IEEE, Vol. 71, No. 1, pp. 149–166, January 1983.

    Article  Google Scholar 

  26. A. Hashimoto and J. Stevens, “Wire Routing by Optimizing Channel Assignment within Large Apertures,” Proceedings of the ACM/IEEE Design Automation Conference, pp. 155–169, June 1971.

    Google Scholar 

  27. D. W. Hightower, “A Solution to Line-Routing Problems on the Continuous Plane,” Proceedings of the ACM/IEEE Design Automation Conference, pp. 1–24, January 1969.

    Google Scholar 

  28. K. Mikami, “A Computer Program for Optimal Routing of Printed Circuit Connectors,” Proceedings of the IFIPS, pp. 1475–1478, November 1968.

    Google Scholar 

  29. R. B. Hitchcock, “Cellular Wiring and the Cellular Modeling Technique,” Proceedings of the ACM/IEEE Design Automation Conference, pp. 25–41, January 1969.

    Google Scholar 

  30. J. D. Lesser and J. J. Shedletsky, “An Experimental Delay Test Generator for LSI Logic,” IEEE Computer Architecture Letters, Vol. 29, No. 3, pp. 235–248, March 1980.

    Google Scholar 

  31. Y. Crouzet and C. Landrault, “Design of Self-Checking MOS-LSI Circuits: Application to a Four-Bit Microprocessor,” IEEE Transactions on Computers, Vol. C-29, No. 6, pp. 532–537, June 1980.

    Article  MATH  Google Scholar 

  32. A. J. Carlan, State-of-the-Art Assessment of Testing and Testability of Custom LSI/VLSI Circuits, Vol. 2, Aerospace Corporation, El Segundo, California, 1982.

    Google Scholar 

  33. S. H. Gerez, Algorithms for VLSI Design Automation, Wiley, 1998.

    Google Scholar 

  34. T. C. Bartee, I. L. Lebow, and I. S. Reed, Theory and Design of Digital Machines, McGraw-Hill, 1962.

    MATH  Google Scholar 

  35. W. A. Clark, “Macromodular Computer Systems,” Proceedings of the Spring Joint Computer Conference, pp. 335–336, April 1967.

    Google Scholar 

  36. S. M. Ornstein, M. J. Stucki, and W. A. Clark, “A Functional Description of Macromodules,” Proceedings of the Spring Joint Computer Conference, pp. 337–355, April 1967.

    Google Scholar 

  37. M. J. Stucki, S. M. Ornstein, and W. A. Clark, “Logical Design of Macromodules,” Proceedings of the Spring Joint Computer Conference, pp. 357–364, April 1967.

    Google Scholar 

  38. J. R. Cox Jr., “Economy of Scale and Specialization in Large Computing Systems,” Computer Design, Vol. 77, No. 11, pp. 77–80, November 1968.

    Google Scholar 

  39. C. G. Bell and J. Grason, “The Register Transfer Module Design Concept,” Computer Design, Vol. 10, No. 5, pp. 87–94, May 1971.

    Google Scholar 

  40. S. H. Fuller, D. P. Siewiorek, and R. J. Swan, “Computer Modules: an Architecture for Large Digital Modules,” ACM SIGARCH Computer Architecture News, Vol. 2, No. 4, pp. 231–237, December 1973.

    Article  Google Scholar 

  41. J. Grason, C. G. Bell, and J. Eggert, “The Commercialization of Register Transfer Modules,” Computer, Vol. 6, No. 10, pp. 23–28, October 1973.

    Article  Google Scholar 

  42. D. E. Thomas, E. D. Lagnese, R. A. Walker, J. V. Rajan, R. L. Blackburn, and J. A. Nestor, Algorithmic and Register-Transfer Level Synthesis: the System Architect’s Workbench, Springer Science & Business Media, 1989.

    Google Scholar 

  43. A. K. Bose, “Progress in VLSI Design Automation,” Proceedings of the European Solid-State Circuits Conference, pp. 103–104, September 1984.

    Google Scholar 

  44. A. Dewey, “VHSIC Hardware Description (VHDL) Development Program,” Proceedings of the ACM/IEEE Design Automation Conference, pp. 625–628, June 1983.

    Google Scholar 

  45. C.-L. Huang and S. Y. H. Su, “Approaches for Computer-Aided Logic/System Design using Hardware Description Language,” Proceedings of the International Computer Symposium, pp. 772–790, December 1980.

    Google Scholar 

  46. G. De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994.

    Google Scholar 

  47. D. D. Gajski, S. Abdi, A. Gerstlauer, and G. Schirner, Embedded System Design: Modeling, Synthesis and Verification, Springer Science & Business Media, 2009.

    Google Scholar 

  48. M. R. Zargham, Computer Architecture: Single and Parallel Systems, Prentice-Hall, 1996.

    MATH  Google Scholar 

  49. P. Gray, “On the Arithmometer of M. Thomas (de Colmar), and its Application to the Construction of Life Contingency Tables,” Journal of the Institute of Actuaries and Assurance Magazine, Vol. 17, No. 4, pp. 249–266, October 1873.

    Article  Google Scholar 

  50. J. von Neumann, “First Draft of a Report on the EDVAC,” IEEE Annals of the History of Computing, Vol. 15, No. 4, pp. 27–75, April 1993.

    Article  MathSciNet  MATH  Google Scholar 

  51. R. Nair, “Evolution of Memory Architecture,” Proceedings of the IEEE, Vol. 103, No. 8, pp. 1331–1345, August 2015.

    Article  Google Scholar 

  52. D. Comer, Essentials of Computer Architecture, CRC Press, 2017.

    Book  Google Scholar 

  53. V. Herdt, D. Große, P. Pieper, and R. Drechsler, “RISC-V based Virtual Prototype: an Extensible and Configurable Platform for the System-Level,” Journal of Systems Architecture, Vol. 109, pp. 101756, October 2020.

    Article  Google Scholar 

  54. A. Waterman and K. Asanović, The RISC-V Instruction Set Manual, Volume I: User-Level ISA, RISC-V Foundation, 2019.

    Google Scholar 

  55. J. L. Hennessy and D. A. Patterson, Computer Architecture: a Quantitative Approach, Elsevier, 2011.

    MATH  Google Scholar 

  56. P. Briggs, K. D. Cooper, and L. Torczon, “Improvements to Graph Coloring Register Allocation,” ACM Transactions on Programming Languages and Systems, Vol. 16, No. 3, pp. 428–455, May 1994.

    Article  Google Scholar 

  57. G. J. Chaitin, “Register Allocation and Spilling via Graph Coloring,” ACM SIGPLAN Notices, Vol. 17, No. 6, pp. 98–101, June 1982.

    Article  MathSciNet  Google Scholar 

  58. D. Watson, A Practical Approach to Compiler Construction, Springer, 2017.

    Book  MATH  Google Scholar 

  59. D. J. A. Welsh and M. B. Powell, “An Upper Bound for the Chromatic Number of a Graph and its Application to Timetabling Problems,” The Computer Journal, Vol. 10, No. 1, pp. 85–86, January 1967.

    Article  MATH  Google Scholar 

  60. M. Poletto and V. Sarkar, “Linear Scan Register Allocation,” ACM Transactions on Programming Languages and Systems, Vol. 21, No. 5, pp. 895–913, September 1999.

    Article  Google Scholar 

  61. J. Schneider and R. Wattenhofer, “A New Technique for Distributed Symmetry Breaking,” Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 257–266, July 2010.

    Google Scholar 

  62. F. Kuhn, “Weak Graph Colorings: Distributed Algorithms and Applications,” Proceedings of the Symposium on Parallelism in Algorithms and Architectures, pp. 138–144, August 2009.

    Google Scholar 

  63. N. Alon, L. Babai, and A. Itai, “A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem,” Journal of Algorithms, Vol. 7, No. 4, pp. 567–583, December 1986.

    Article  MathSciNet  MATH  Google Scholar 

  64. M. Luby, “A Simple Parallel Algorithm for the Maximal Independent Set Problem,” SIAM Journal on Computing, Vol. 15, No. 4, pp. 1036–1053, November 1986.

    Article  MathSciNet  MATH  Google Scholar 

  65. M. Rigo, Advanced Graph Theory and Combinatorics, John Wiley & Sons, 2016.

    Book  MATH  Google Scholar 

  66. A. Y. Zomaya and Y.-C. Lee, Energy-Efficient Distributed Computing Systems, Wiley, 2012.

    Book  Google Scholar 

  67. P. Marwedel, Embedded System Design: Embedded Systems, Foundations of Cyber-Physical Systems, and the Internet of Things, Springer Nature, 2021.

    Google Scholar 

  68. E. G. Friedman, “Clock Distribution Networks in Synchronous Digital Integrated Circuits,” Proceedings of the IEEE, Vol. 89, No. 5, pp. 665–692, May 2001.

    Article  Google Scholar 

  69. I. S. Kourtev, B. Taskin, and E. G. Friedman, Timing Optimization through Clock Skew Scheduling, Springer Science & Business Media, 2008.

    Google Scholar 

  70. E. Salman and E. G. Friedman, High Performance Integrated Circuit Design, McGraw-Hill Professional, 2012.

    Google Scholar 

  71. J. P. Fishburn, “Clock Skew Optimization,” IEEE Transactions on Computers, Vol. 39, No. 7, pp. 945–951, July 1990.

    Article  Google Scholar 

  72. T. M. McWilliams, “Verification of Timing Constraints on Large Digital Systems,” Proceedings of the ACM/IEEE Design Automation Conference, pp. 139–147, November 1980.

    Google Scholar 

  73. T.-H. Chao, Y.-C. Hsu, J.-M. Ho, and A. B. Kahng, “Zero Skew Clock Routing with Minimum Wirelength,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, Vol. 39, No. 11, pp. 799–814, September 1992.

    Article  MATH  Google Scholar 

  74. H. B. Bakoglu, “A Symmetric Clock Distribution Tree and Optimized High-Speed Interconnections for Reduced Clock Skew in ULSI & WSI Circuits,” Proceedings of the IEEE International Conference on Computer Design: VLSI in Computers, pp. 118–122, October 1986.

    Google Scholar 

  75. J. L. Neves and E. G. Friedman, “Design Methodology for Synthesizing Clock Distribution Networks Exploiting Nonzero Localized Clock Skew,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 4, No. 2, pp. 286–291, June 1996.

    Article  Google Scholar 

  76. E. G. Friedman, Performance Limitations in Synchronous Digital Systems, Ph.D. Thesis, University of California, Irvine, 1989.

    Google Scholar 

  77. J. L. Neves and E. G. Friedman, “Optimal Clock Skew Scheduling Tolerant to Process Variations,” Proceedings of the ACM/IEEE Design Automation Conference, pp. 623–628, June 1996.

    Google Scholar 

  78. I. S. Kourtev and E. G. Friedman, “Simultaneous Clock Scheduling and Buffered Clock Tree Synthesis,” Proceedings of the IEEE International Symposium on Circuits and Systems, Vol. 3, pp. 1812–1815, June 1997.

    Google Scholar 

  79. I. S. Kourtev and E. G. Friedman, “Clock Skew Scheduling for Improved Reliability via Quadratic Programming,” Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 239–243, November 1999.

    Google Scholar 

  80. A. V. Mezhiba and E. G. Friedman, Power Distribution Networks in High Speed Integrated Circuits, Springer Science & Business Media, 2004.

    Google Scholar 

  81. J.-P. Queille and J. Sifakis, “Specification and Verification of Concurrent Systems in CESAR,” Proceedings of the International Symposium on Programming, pp. 337–351, April 1982.

    Google Scholar 

  82. E. M. Clarke and E. A. Emerson II, “Design and Synthesis of Synchronization Skeletons using Branching Time Temporal Logic,” Proceedings of the Logics of Programs Workshop, pp. 52–71, May 1982.

    Google Scholar 

  83. K. L. McMillan, Symbolic Model Checking, Springer, 1993.

    Book  MATH  Google Scholar 

  84. D. K. Pradhan and I. G. Harris, Practical Design Verification, Cambridge University Press, 2009.

    Book  MATH  Google Scholar 

  85. A. Mishchenko, S. Chatterjee, R. Jiang, and R. K. Brayton, FRAIGs: a Unifying Representation for Logic Synthesis and Verification, University of California, Berkeley, 2005.

    Google Scholar 

  86. M. K. Ganai and A. Kuehlmann, “On-the-Fly Compression of Logical Circuits,” Proceedings of the International Workshop on Logic Synthesis, pp. 1–7, June 2000.

    Google Scholar 

  87. A. Kuehlmann, V. Paruthi, F. Krohm, and M. K. Ganai, “Robust Boolean Reasoning for Equivalence Checking and Functional Property Verification,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 21, No. 12, pp. 1377–1394, December 2002.

    Article  Google Scholar 

  88. A. Kuehlmann and F. Krohm, “Equivalence Checking using Cuts and Heaps,” Proceedings of the ACM/IEEE Design Automation Conference, pp. 263–268, June 1997.

    Google Scholar 

  89. A. C. Ling, J. Zhu, and S. D. Brown, “Delay Driven AIG Restructuring using Slack Budget Management,” Proceedings of the ACM Great Lakes Symposium on VLSI, pp. 163–166, May 2008.

    Google Scholar 

  90. G. Pasandi and M. Pedram, “A Dynamic Programming-Based, Path Balancing Technology Map** Algorithm Targeting Area Minimization,” Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 1–8, November 2019.

    Google Scholar 

  91. A. Mishchenko, J. S. Zhang, S. Sinha, J. R. Burch, R. Brayton, and M. Chrzanowska-Jeske, “Using Simulation and Satisfiability to Compute Flexibilities in Boolean Networks,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 25, No. 5, pp. 743–755, May 2006.

    Article  Google Scholar 

  92. M. Backes, J. M. Matos, R. Ribas, and A. Reis, “Reviewing AIG Equivalence Checking Approaches,” Proceedings of the ACM Microelectronics Student Forum, pp. 1–4, September 2014.

    Google Scholar 

  93. K. T. S. Oldham, The Doctrine of Description: Gustav Kirchhoff, Classical Physics, and the “Purpose of all Science” in 19 th -Century Germany, Ph.D. Thesis, University of California, Berkeley, 2008.

    Google Scholar 

  94. G. R. Kirchhoff, “Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird,” Annalen der Physik, Vol. 148, No. 12, pp. 497–508, October 1847.

    Article  Google Scholar 

  95. P. Appell and J. Drach, Oeuvres de Henri Poincaré Tome I, Gauthier-Villars, 1928.

    Google Scholar 

  96. C. A. Desoer and E. S. Kuh, Basic Circuit Theory, McGraw-Hill, 1969.

    Google Scholar 

  97. R. Merris, “Laplacian Matrices of Graphs: a Survey,” Linear Algebra and its Applications, Vol. 197–198, pp. 143–176, February 1994.

    Article  MathSciNet  MATH  Google Scholar 

  98. L. Nagel and R. Rohrer, “Computer Analysis of Nonlinear Circuits, Excluding Radiation (CANCER),” IEEE Journal of Solid-State Circuits, Vol. 6, No. 4, pp. 166–182, August 1971.

    Article  Google Scholar 

  99. W. J. McCalla and W. G. Howard, “BIAS-3-A Program for the Nonlinear D.C. Analysis of Bipolar Transistor Circuits,” IEEE Journal of Solid-State Circuits, Vol. 6, No. 1, pp. 14–19, February 1971.

    Article  Google Scholar 

  100. A. Hemani, “Charting the EDA Roadmap,” IEEE Circuits and Devices Magazine, Vol. 20, No. 6, pp. 5–10, December 2004.

    Article  Google Scholar 

  101. A. B. Kahng, J. Lienig, I. L. Markov, and J. Hu, VLSI Physical Design: from Graph Partitioning to Timing Closure, Springer Science & Business Media, 2011.

    Google Scholar 

  102. T. Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, Springer Science & Business Media, 2012.

    Google Scholar 

  103. C. J. Alpert, D. P. Mehta, and S. S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, CRC Press, 2008.

    Book  MATH  Google Scholar 

  104. N. Cserhalmi, O. Lowenschuss, and B. Scheff, “Efficient Partitioning for the Batch-Fabricated Fourth Generation Computer,” Proceedings of the Fall Joint Computer Conference, Vol. 1, pp. 857–865, December 1968.

    Google Scholar 

  105. H. Beelitz, H. Miiller, R. Linhardt, and R. Sidnam, “Partitioning for Large-Scale Integration,” Proceedings of the IEEE International Solid-State Circuits Conference, Vol. 10, pp. 50–51, February 1967.

    Google Scholar 

  106. M. Armbruster, M. Fügenschuh, C. Helmberg, and A. Martin, “A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem,” Integer Programming and Combinatorial Optimization, pp. 112–124, May 2008.

    Google Scholar 

  107. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, “Multilevel Hypergraph Partitioning: Applications in VLSI Domain,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 7, No. 1, pp. 69–79, March 1999.

    Article  Google Scholar 

  108. C. M. Fiduccia and R. M. Mattheyses, “A Linear-Time Heuristic for Improving Network Partitions,” Proceedings of the ACM/IEEE Design Automation Conference, pp. 175–181, June 1982.

    Google Scholar 

  109. B. Krishnamurthy, “An Improved Min-Cut Algonthm for Partitioning VLSI Networks,” IEEE Transactions on Computers, Vol. C-33, No. 5, pp. 438–446, May 1984.

    Article  MATH  Google Scholar 

  110. L. A. Sanchis, “Multiple-Way Network Partitioning,” IEEE Transactions on Computers, Vol. 38, No. 1, pp. 62–81, January 1989.

    Article  MATH  Google Scholar 

  111. L.-T. Liu, M.-T. Kuo, S.-C. Huang, and C.-K. Cheng, “A Gradient Method on the Initial Partition of Fiduccia-Mattheyses Algorithm,” Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 229–234, November 1995.

    Google Scholar 

  112. G. Karypis and V. Kumar, METIS – Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 2.0, University of Minnesota, Minneapolis, Minnesota, 1995.

    Google Scholar 

  113. C. J. Alpert, L. W. Hagen, and A. B. Kahng, “A Hybrid Multilevel/Genetic Approach for Circuit Partitioning,” Proceedings of the IEEE Asia Pacific Conference on Circuits and Systems, pp. 298–301, November 1996.

    Google Scholar 

  114. G. Wang, W. Gong, and R. Kastner, “Application Partitioning on Programmable Platforms using the Ant Colony Optimization,” Journal of Embedded Computing, Vol. 2, No. 1, pp. 119–136, September 2006.

    Google Scholar 

  115. M. Abdelhalim, A. Salama, and S.-D. Habib, “Hardware Software Partitioning using Particle Swarm Optimization Technique,” Proceedings of the International Workshop on System on Chip for Real Time Applications, pp. 189–194, December 2006.

    Google Scholar 

  116. H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, “Rectangle-Packing-Based Module Placement,” Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 472–479, November 1995.

    Google Scholar 

  117. M. Tang and X. Yao, “A Memetic Algorithm for VLSI Floorplanning,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), Vol. 37, No. 1, pp. 62–69, January 2007.

    Article  MathSciNet  Google Scholar 

  118. I. L. Markov, J. Hu, and M.-C. Kim, “Progress and Challenges in VLSI Placement Research,” Proceedings of the IEEE, Vol. 103, No. 11, pp. 1985–2003, November 2015.

    Article  Google Scholar 

  119. X. Hong, Sheqin D., Gang H., Y. Cai, C.-K. Cheng, and J. Gu, “Corner Block List Representation and its Application to Floorplan Optimization,” IEEE Transactions on Circuits and Systems II: Express Briefs, Vol. 51, No. 5, pp. 228–233, May 2004.

    Article  Google Scholar 

  120. P.-N. Guo, C.-K. Cheng, and T. Yoshimura, “An O-Tree Representation of Non-Slicing Floorplan and its Applications,” Proceedings of the ACM/IEEE Design Automation Conference, pp. 268–273, June 1999.

    Google Scholar 

  121. F. Mao, N. Xu, and Y. Ma, “Hybrid Algorithm for Floorplanning using B ∗-Tree Representation,” Proceedings of the IEEE International Symposium on Intelligent Information Technology Application, Vol. 3, pp. 228–231, November 2009.

    Google Scholar 

  122. C. Chu and Y.-C. Wong, “FLUTE: Fast Lookup Table based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 27, No. 1, pp. 70–83, January 2008.

    Article  Google Scholar 

  123. R. H. J. M. Otten and R. K. Brayton, “Performance Planning,” Integration, the VLSI Journal, Vol. 29, No. 1, pp. 1–24, March 2000.

    Article  MATH  Google Scholar 

  124. H. Ren, D. Z. Pan, C. J. Alpert, G.-J. Nam, and P. Villarrubia, “Hippocrates: First-Do-No-Harm Detailed Placement,” Proceedings of the ACM/IEEE Asia and South Pacific Design Automation Conference, pp. 141–146, January 2007.

    Google Scholar 

  125. J. Westra and P. Groeneveld, “Is Probabilistic Congestion Estimation Worthwhile?,” Proceedings of the ACM International Workshop on System Level Interconnect Prediction, pp. 99–106, April 2005.

    Google Scholar 

  126. C.-K. Koh and P. H. Madden, “Manhattan or Non-Manhattan? a Study of Alternative VLSI Routing Architectures,” Proceedings of the ACM Great Lakes Symposium on VLSI, pp. 47–52, March 2000.

    Google Scholar 

  127. M. Pathak and S. K. Lim, “Performance and Thermal-Aware Steiner Routing for 3-D Stacked ICs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 28, No. 9, pp. 1373–1386, September 2009.

    Article  Google Scholar 

  128. N. J. Nilsson, The Quest for Artificial Intelligence, Cambridge University Press, 2009.

    Book  Google Scholar 

  129. T. Yoshimura and E. S. Kuh, “Efficient Algorithms for Channel Routing,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 1, No. 1, pp. 25–35, January 1982.

    Article  Google Scholar 

  130. T. G. Szymanski, “Dogleg Channel Routing is NP-Complete,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 4, No. 1, pp. 31–41, January 1985.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Rochester, Rochester, NY, USA

    Rassul Bairamkulov & Eby Friedman

Authors
  1. Rassul Bairamkulov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eby Friedman
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Bairamkulov, R., Friedman, E. (2023). Graphs in VLSI circuits and systems. In: Graphs in VLSI. Springer, Cham. https://doi.org/10.1007/978-3-031-11047-4_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-11047-4_3

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-11046-7

  • Online ISBN: 978-3-031-11047-4

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation