×

zbMATH — the first resource for mathematics

A framework for solving VLSI graph layout problems. (English) Zbl 0543.68052
Summary: A new divide-and-conquer framework for VLSI graph layout is introduced. Universally close upper and lower bounds are obtained for important cost functions such as layout area and propagation delay. The framework is also effectively used to design regular and configurable layouts, to assemble large networks of processors using restructurable chips, and to configure networks around faulty processors. It is also shown how good graph partitioning heuristics may be used to develop a provably good layout strategy.

MSC:
68R10 Graph theory (including graph drawing) in computer science
94C15 Applications of graph theory to circuits and networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bentley, J.; Kung, H.T., A tree machine for searching problems, ()
[2] Bhatt, S.N.; Cosmadakis, S., The complexity of minimizing wire lengths in VLSI layouts, (1982), MIT Cambridge, Mass, unpublished manuscript · Zbl 0653.68020
[3] Bhatt, S.N.; Leiserson, C.E., Minimizing the longest edge in a VLSI layout, MIT VLSI memo 82-86, (1982)
[4] Bhatt, S.N.; Leiserson, C.E., How to assemble tree machines,, ()
[5] Bilardi, G.; Pracchi, M.; Preparata, F., A critique and appraisal of VLSI models of computation, ()
[6] Breuer, M.A., MIN-cut placement, J. design automation and fault tolerant computing, 1, 4, 343-362, (1977)
[7] But, T., On bisecting random graphs, ()
[8] Cappello, P.R.; Steiglitz, K., Area-efficient VLSI structures for multiplying at clock rate, ()
[9] Dolev, D.; Leighton, F.T.; Trickey, H., Planar embeddings of planar graphs, MIT LCS technical memo 237, (1983)
[10] Fiduccia, C.M.; Mattheyses, R.M., An almost linear algorithm for partitioning networks, (1982), unpublished manuscript
[11] Floyd, R.; Ullman, J., The compilation of regular expressions into integrated circuits, () · Zbl 0485.68047
[12] Gabber, O.; Galil, Z., Explicit constructions of linear size superconcentrators, (), 364-370
[13] Garey, M.R.; Johnson, D., ()
[14] \scM. R. Garey and D. S. Johnson, unpublished manuscript, 1982.
[15] Gilbert, J.R., Graph separator theorems and sparse Gaussian elimination, ()
[16] Goldberg, C.; West, D., Even splittings of circle colorings, (1982), unpublished manuscript
[17] Greene, J.; El Gamal, A., Area and delay penalties in restructurable wafer-scale arrays, ()
[18] Kernighan, B.W.; Lin, S., An efficient heuristic procedure for partitioning graphs, Bell system tech. J., 291-307, (1970) · Zbl 0333.05001
[19] Leighton, F.T.; Leighton, F.T., Complexity issues in VLSI, (), revised version · Zbl 0852.68004
[20] Leighton, F.T., New lower bound techniques for VLSI, () · Zbl 0488.94048
[21] Leighton, F.T., A layout strategy for VLSI which is provably good, ()
[22] Leighton, F.T.; Leiserson, C.E., Wafer-scale integration of systolic arrays, () · Zbl 0558.94020
[23] Leighton, F.T.; Rosenberg, A.L., Three dimensional circuit layouts, M.I.T. VLSI memo 102, (1982)
[24] Leiserson, C.E., A model for VLSI computations, () · Zbl 0893.68075
[25] Leiserson, C.E., Systolic priority queues, ()
[26] Leiserson, C.E., Area-efficient layouts (for VLSI), () · Zbl 0929.68023
[27] Leiserson, C.E., Area-efficient VLSI computation, () · Zbl 0929.68023
[28] Lewis, P.M.; Stearns, R.E.; Hartmanis, J., Memory bounds for recognition of context-free and context-sensitive languages, () · Zbl 0272.68054
[29] Lipton, R.J.; Tarjan, R.E., A separator theorem for planar graphs, () · Zbl 0417.05023
[30] Magó, G.A., A network of microprocessors to execute reduction languages. I and II, Internat. J. comput. inform. sci., (1979) · Zbl 0427.68029
[31] Mead, C.; Conway, L., Introduction to VLSI systems, (1980), Addison-Wesley Reading, Mass
[32] \scK. Mehlhorn, personal communication, 1982.
[33] Nath, D.; Maheshwari, S.N.; Bhatt, P.C.P., Efficient VLSI networks for parallel processing based on orthogonal trees, IEEE trans. comput., (1983) · Zbl 0514.68029
[34] Paterson, M.; Ruzzo, W.; Snyder, L., Bounds on minimax edge for complete binary trees, ()
[35] Raffel, J., On the use of nonvolatile programmable links for restructurable VLSI, ()
[36] Ramachandran, V., On driving many long lines in a VLSI layout, () · Zbl 0634.94023
[37] Rivest, R.L., The “PI” (placement and interconnect) system, ()
[38] Rosenberg, A., Routing with permuters: toward reconfigurable and fault-tolerant networks, ()
[39] Ruzzo, W.; Snyder, L., Minimum edge length planar embeddings of trees, ()
[40] Sangiovanni-Vincentelli, A.; Chen, L.; Chua, L., An efficient heuristic cluster algorithm for tearing large-scale networks, IEEE trans. circuits systems, CAS-24, 12, 709-717, (1977) · Zbl 0368.94028
[41] Thompson, C.D., Area-time complexity for VLSI, () · Zbl 0573.68016
[42] Thompson, C.D., A complexity theory for VLSI, ()
[43] Ullman, J.D., Computational aspects of VLSI, (1983), Computer Science Press Rockville, Md · Zbl 0539.68021
[44] Valiant, L.G., On non-linear loweer bounds in computational complexity, () · Zbl 0584.68063
[45] Valiant, L.G., Universality considerations in VLSI circuits, IEEE trans. comput., (1981) · Zbl 0455.94046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.