×

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
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bentley, J.; Kung, H. T., A tree machine for searching problems, (Proceedings of the 1979 International Conference on Parallel Processing (1979), IEEE: IEEE New York)
[2] Bhatt, S. N.; Cosmadakis, S., The Complexity of Minimizing Wire Lengths in VLSI Layouts (1982), MIT: 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,, (Fourteenth Annual ACM Symposium on Theory of Computing (1982))
[5] Bilardi, G.; Pracchi, M.; Preparata, F., A critique and appraisal of VLSI models of computation, (Proceedings, CMU Conference on VLSI Systems and Computations (1981))
[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, (S. M. thesis. S. M. thesis, MIT LCS Technical Report 287 (1983), Department of Electrical Engineering and Computer Science)
[8] Cappello, P. R.; Steiglitz, K., Area-Efficient VLSI Structures for Multiplying at Clock Rate, (Technical Report 289 (1981), Department of EECS, Princeton Univ. Princeton: Department of EECS, Princeton Univ. Princeton N. J)
[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, (Twenty-First Annual IEEE Symposium on Foundations of Computer Science (1980)) · Zbl 0485.68047
[12] Gabber, O.; Galil, Z., Explicit constructions of linear size superconcentrators, (Proceedings, 20th Annual IEEE Symposium on Foundations of Computer Science (1979)), 364-370
[13] Garey, M. R.; Johnson, D., (Computers and Intractability: A Guide to the Theory of NPCompleteness (1979), Freeman: Freeman San Francisco) · Zbl 0411.68039
[14] M. R. Garey and D. S. Johnson, unpublished manuscript, 1982.; M. R. Garey and D. S. Johnson, unpublished manuscript, 1982.
[15] Gilbert, J. R., Graph Separator Theorems and Sparse Gaussian Elimination, (Ph. D. thesis (1980), Stanford Univ)
[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, (Bryant, R., Third Caltech Conference on VLSI (1983), Computer Science Press: Computer Science Press Rockville, Md)
[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., Complexity Issues in VLSI, (Foundations of Computing Series (1983), M. I. T: M. I. T Cambridge, Mass), revised version · Zbl 0852.68004
[20] Leighton, F. T., New lower bound techniques for VLSI, (Twenty-Second Annual Symposium on Foundations of Computer Science (1981), IEEE: IEEE New York) · Zbl 0488.94048
[21] Leighton, F. T., A layout strategy for VLSI which is provably good, (Fourteenth Annual ACM Symposium on Theory of Computing (1982))
[22] Leighton, F. T.; Leiserson, C. E., Wafer-scale integration of systolic arrays, (Twenty Third Annual IEEE Symposium on Foundations of Computer Science (1982)) · 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, (Thesis proposal (1979), Carnegie-Mellon Univ: Carnegie-Mellon Univ Pittsburgh) · Zbl 0893.68075
[25] Leiserson, C. E., Systolic priority queues, (Seitz, C., Proceedings of the Caltech Conference on Very Large Scale Integration (1979), California Institute of Technology: California Institute of Technology Pasadena)
[26] Leiserson, C. E., Area-efficient layouts (for VLSI), (Twenty-First Annual Symposium on Foundations of Computer Science (1980), IEEE: IEEE New York) · Zbl 0929.68023
[27] Leiserson, C. E., Area-Efficient VLSI Computation, (Ph. D. thesis Carnegie-Mellon Univ., Pittsburg, 1981 (1983), MIT Press: MIT Press Cambridge, Mass) · Zbl 0929.68023
[28] Lewis, P. M.; Stearns, R. E.; Hartmanis, J., Memory bounds for recognition of context-free and context-sensitive languages, (IEEE Symposium on Switching Circuit Theory and Logical Design (1965)) · Zbl 0272.68054
[29] Lipton, R. J.; Tarjan, R. E., A separator theorem for planar graphs, (A Conference on Theoretical Computer Science (1977), Univ. of Waterloo) · 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: Addison-Wesley Reading, Mass
[32] K. Mehlhorn, personal communication, 1982.; K. 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, (Thirteenth Annual ACM Symposium on Theory of Computings (1981))
[35] Raffel, J., On the use of nonvolatile programmable links for restructurable VLSI, (Proceedings of the Caltech Conference on Very Large Scale Integration (1979))
[36] Ramachandran, V., On driving many long lines in a VLSI layout, (Proceedings, Twenty third Annual IEEE Symposium on Foundations of Computer Science (1982)) · Zbl 0634.94023
[37] Rivest, R. L., The “PI” (placement and interconnect) system, (Proceedings, 19th Annual Design Automation Conference (1982))
[38] Rosenberg, A., Routing with Permuters: Toward Reconfigurable and Fault-Tolerant Networks, (Technical Report CS-1981-13 (1981), Duke Univ: Duke Univ Durham, N. C)
[39] Ruzzo, W.; Snyder, L., Minimum edge length planar embeddings of trees, (Proceedings, CMU Conference on VLSI Systems and Computation (1981))
[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, (Eleventh Annual ACM Symposium on Theory of Computing (1979)) · Zbl 0573.68016
[42] Thompson, C. D., A Complexity Theory for VLSI, (Ph. D. thesis (1980), Carnegie-Mellon Univ: Carnegie-Mellon Univ Pittsburgh)
[43] Ullman, J. D., Computational Aspects of VLSI (1983), Computer Science Press: Computer Science Press Rockville, Md · Zbl 0539.68021
[44] Valiant, L. G., On non-linear loweer bounds in computational complexity, (Proceedings, Seventh Annual Symposium on Theory of Computing (1975)) · 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.