Section 7 of 7

4.7 Summary

This chapter has illustrated a number of techniques for automatic synthesis of VLSI circuitry. The list is not complete, since new methods are being proposed continuously. It is hoped that eventually the synthesis algorithms will be able to do the entire job of design. Until such time, however, humans will have to do much of the layout and will have to guide these synthesis tools carefully. Because this guidance is subject to errors, there will also have to be methods of analyzing a circuit for correctness. These analysis tools are the subject of the next two chapters.

Questions

1. How do PLAs and gate matrices differ in philosophy from gate-arrays?
2. Why do channel and switchbox routers produce better wiring patterns than do repeated applications of maze routers?
3. What is the most difficult aspect of global routing?
4. What other considerations should be addressed besides wire lengths when doing placement?
5. Why are rule-based systems attractive techniques for synthesis tools?
6. Why is there little hope that silicon compilers will ever be able to generate arbitrary and appropriate architectures?
7. In what sense are the results of simulated-annealing compaction incorrect?

References

• Ackland, Bryan; Dickenson, Alex; Ensor, Robert; Gabbe, John; Kollaritsch, Paul; London, Tom; Poirier, Charles; Subrahmanyam, P.; and Watanabe, Hiroyuki, "CADRE-A System of Cooperating VLSI Design Experts," Proceedings IEEE International Conference on Computer Design, 99-104, October 1985.
• Ackland, Bryan and Weste, Neil, "An Automatic Assembly Tool for Virtual Grid Symbolic Layout," VLSI '83 (Anceau and Aas, eds), North Holland, Amsterdam, 457-466, August 1983.
• Ayres, Ronald F., VLSI Silicon Compilation and the Art of Automatic Microchip Design, Prentice-Hall, Englewood Cliffs, New Jersey, 1983.
• Baker, Clark M. and Terman, Chris, "Tools for Verifying Integrated Circuit Designs," Lambda, 1:3, 22-30, 4th Quarter 1980.
• Balraj, T. S. and Foster, M. J., "Miss Manners: A Specialized Silicon Compiler for Synchronizers," Proceedings 4th MIT Conference on Advanced Research in VLSI (Leiserson, ed), 3-20, April 1986.
• Beresford, Roderic, "Comparing Gate Arrays and Standard-Cell ICs," VLSI Design, IV:8, 30-36, December 1983.
• Blank, Tom, "A Survey of Hardware Accelerators Used in Computer-Aided Design," IEEE Design and Test, 1:3, 21-39, August 1984.
• Breuer, Melvin A., "A Class of Min-Cut Placement Algorithms," Proceedings 14th Design Automation Conference, 284-290, June 1977.
• Buric, Misha R. and Matheson, Thomas G., "Silicon Compilation Environments," Proceedings Custom Integrated Circuits Conference, 208-212, May 1985.
• Burstein, Michael; Hong, Se June; and Pelavin, Richard, "Hierarchical VLSI Layout: Simultaneous Placement and Wiring of Gate Arrays," VLSI '83 (Anceau and Aas, eds), North Holland, Amsterdam, 45-60, August 1983.
• Cheng, Chung-Kuan and Kuh, Ernest S., "Module Placement Based on Resistive Network Optimization," IEEE Transactions on CAD, 3:3, 218-225, July 1984
• Deas, Alex R. and Nixon, Ian M., "Chromatic Idioms for Automated VLSI Floorplanning," VLSI '85, (Horbst, ed), 61-70, August 1985.
• Denyer, Peter B.; Murray, Alan F.; and Renshaw, David, "FIRST-Prospect and Retrospect," VLSI Signal Processing, IEEE press, New York, 252-263, 1984.
• Deutsch, David N., "A 'Dogleg' Channel Router," Proceedings 13th Design Automation Conference, 425-433, June 1976.
• Do, James and Dawson, William M., "Spacer II: A Well-Behaved IC Layout Compactor," VLSI '85, (Horbst, ed), 283-291, August 1985.
• Doreau, Michel T. and Koziol, Piotr, "TWIGY: A Topological Algorithm Based Routing System," Proceedings 18th Design Automation Conference, 746-755, June 1981.
• Dunlop, A. E., "SLIM-The Translation of Symbolic Layouts into Mask Data," Proceedings 17th Design Automation Conference, 595-602, June 1980.
• Entenman, George and Daniel, Stephen W., "A Fully Automatic Hierarchical Compactor," Proceedings 22nd Design Automation Conference, 69-75, June 1985.
• Freeman, William J. III and Freund, Vincent J. Jr., "A History of Semicustom Design at IBM," VLSI Systems Design, Semicustom Design Guide, 14-22, Summer 1986.
• Gajski, Daniel D., "ARSENIC Silicon Compiler," Proceedings International Symposium on Circuits and Systems, 399-402, June 1985.
• Garey, Michael R. and Johnson, David S., Computers and Intractability, A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, 1979.
• Goates, Gary B.; Harris, Thomas R.; Oettel, Richard E.; and Waldron, Harvey M. III, "Storage/Logic Array Design: Reducing Theory to Practice," VLSI Design, III:4, 56-62, 1982.
• Hachtel, G. D.; Newton, A. R.; and Sangiovanni-Vincentelli, A. L., "Techniques for Programmable Logic Array Folding," Proceedings 19th Design Automation Conference, 147-155, June 1982.
• Hamachi, Gordon T. and Ousterhout, John K., "A Switchbox Router with Obstacle Avoidance," Proceedings 21st Design Automation Conference, 173-179, June 1984.
• Heller, W. R., "An Algorithm for Chip Planning," Caltech Silicon Structures Project file #2806, 1979.
• Heller, William R.; Sorkin, G.; Maling, Klim, "The Planar Package Planner for System Designers," Proceedings 19th Design Automation Conference, 253-260, June 1982.
• Hightower, D. W., "A Solution to Line-Routing Problems in the Continuous Plane," Proceedings 6th Design Automation Workshop, 1-24, June 1969.
• Hon, Robert W. and Sequin, Carlo H., "A Guide to LSI Implementation," 2nd Edition, Xerox Palo Alto Research Center technical memo SSL-79-7, January 1980.
• Hsueh, Min-Yu and Pederson, Donald O., "Computer-Aided Layout of LSI Circuit Building-Blocks," Proceedings International Symposium on Circuits and Systems, 474-477, July 1979.
• Johannsen, D. L., "Bristle Blocks: A Silicon Compiler," Proceedings 16th Design Automation Conference, 310-313, June 1979.
• Kahrs, Mark, "Silicon compilation of a very high level signal processing specification language," VLSI Signal Processing, IEEE press, New York, 228-238, 1984.
• Keller, John, Power and Ground Requirements for a High Speed 32 Bit Computer Chip Set, Masters thesis, University of California at Berkeley, UCB/CSD 86/253, August 1985.
• Kernighan, B. W.; Schweikert, D. G.; and Persky, G., "An Optimum Channel-Routing Algorithm for Polycell Layouts of Integrated Circuits," Proceedings 10th Design Automation Workshop, 50-59, June 1973.
• Kim, Jin H.; McDermott, John; and Siewiorek, Daniel P., "Exploiting Domain Knowledge in IC Cell Layout," IEEE Design and Test, 1:3, 52-64, 1984.
• Kirkpatrick, S.; Gelatt, C. D. Jr.; and Vecchi, M. P., "Optimization by Simulated Annealing," Science, 220:4598, 671-680, May 1983.
• Kollaritsch, P. W. and Weste, N. H. E., "A Rule-Based Symbolic Layout Expert," VLSI Design, V:8, 62-66, August 1984.
• Kowalski, T. J. and Thomas, D. E., "The VLSI Design Automation Assistant: Prototype System," Proceedings 20th Design Automation Conference, 479-483, June 1983.
• Kozminski, Krzysztof and Kinnen, Edwin, "An Algorithm for Finding a Rectangular Dual of a Planar Graph for Use in Area Planning for VLSI Integrated Circuits," Proceedings 21st Design Automation Conference, 655-656, June 1984.
• Lauther, Ulrich, "Channel Routing in a General Cell Environment," VLSI '85, (Horbst, ed), 393-403, August 1985.
• Lee, C. Y., "An Algorithm for Path Connections and Its Applications," IRE Transactions on Electronic Computers, EC-10, 346-365, September 1961.
• Liu, Erwin S. K., "A Silicon Logic Module Compiler," Project Report, University of Calgary Department of Computer Science, April 1984.
• Lopez, Alexander D. and Law, Hung-Fai S., "A Dense Gate Matrix Layout Method for MOS VLSI," IEEE Transactions on Electron Devices, 27:8, 1671-1675, August 1980.
• Luk, W. K., "A Greedy Switch-box Router," Carnegie-Mellon University Department of Computer Science VLSI Document V158, May 1984.
• Maley, F. Miller, "Compaction with Automatic Jog Introduction," Chappel Hill Conference on VLSI (Fuchs, ed), 261-283, March 1985.
• Mayo, Robert N., "Combining Graphics and Procedures in a VLSI Layout Tool: The Tpack System," University of California at Berkeley Computer Science Division technical report, January 1984.
• McCreight, E.M., "Efficient Algorithms for Enumerating Intersecting Intervals and Rectangles," Xerox Palo Alto Research Center, CSL-80-9, 1980.
• Metropolis, Nicholas; Rosenbluth, Arianna W.; Rosenbluth, Marshall N.; Teller, Augusta H.; and Teller, Edward, "Equation of State Calculations by Fast Computing Machines," Journal of Chemical Physics, 21:6, 1087-1092, June 1953.
• Mitchell, Tom M.; Steinberg, Louis I.; and Shulman, Jeffrey S., "A Knowledge-Based Approach to Design," Proceedings IEEE Workshop on Principles of Knowledge-Based Systems, 27-34, December 1984.
• Moore, E. F., "Shortest Path Through a Maze," Harvard University Press, Cambridge, Massachusetts, 285-292, 1959.
• Mori, Hajimu, "Interactive Compaction Router for VLSI Layout," Proceedings 21st Design Automation Conference, 137-143, June 1984.
• Mosteller, R. C., "REST-A Leaf Cell Design System," VLSI '81 (Gray, ed), Academic Press, London, 163-172, August 1981.
• Nogatch, John T. and Hedges, Tom, "Automated Design of CMOS Leaf Cells," VLSI Systems Design, VI:11, 66-78, November 1985.
• Pope, Stephen; Rabaey, Jan; and Brodersen, Robert W., "Automated Design of Signal Processors Using Macrocells," VLSI Signal Processing, IEEE press, New York, 239-251, 1984.
• Ramsay, Frank R., "Automation of Design for Uncommitted Logic Arrays," Proceedings 17th Design Automation Conference, 100-107, June 1980.
• Rivest, Ronald L., "The 'PI' (Placement and Interconnect) System," Proceedings 19th Design Automation Conference, 475-481, June 1982.
• Rivest, Ronald L. and Fiduccia, Charles M., "A 'Greedy' Channel Router," Proceedings 19th Design Automation Conference, 418-424, June 1982.
• Schiele, W., "Design Rule Adaptation of Non-Orthogonal Layouts with Approximate Scaling," VLSI '85, (Horbst, ed), 273-282, August 1985.
• SCI, GENESIL System User's Manual, Silicon Compilers, Incorporated publication 110016, November 1985.
• Scott, Walter S. and Ousterhout, John K., "Plowing: Interactive Stretching and Compaction in Magic," Proceedings 21st Design Automation Conference, 166-172, June 1984.
• Seattle Silicon, The Mentor Idea/Concorde User's Manual, Seattle Silicon Technologies, Incorporated, publication UMC Beta 300 Rev 1, March 1986.
• Sechen, Carl and Sangiovanni-Vincentelli, Alberto, "The TimberWolf Placement and Routing Package," Proceedings Custom Integrated Circuit Conference, 522-527, May 1984.
• Simoudis, Evangelos and Fickas, Stephen, "The Application of Knowledge-Based Design Techniques to Circuit Design," ICCAD '85, 213-215, November 1985.
• Soukup, Jiri, "Circuit Layout," Proceedings IEEE, 69:10, 1281-1304, October 1981.
• Southard, Jay R., "MacPitts: An Approach to Silicon Compilation," IEEE Computer, 74-82, December 1983.
• Supowitz, Kenneth J. and Slutz, Eric A., "Placement Algorithms for Custom VLSI," Proceedings 20th Design Automation Conference, 164-170, June 1983.
• Teig, Steven; Smith, Randall L.; and Seaton, John, "Timing-Driven Layout of Cell-Based ICs," VLSI Systems Design, VII:5, 63-73, May 1986.
• Tompa, Martin, "An Optimal Solution to a Wire-Routing Problem," Proceedings 12th Annual ACM Symposium on Theory of Computing, 161-176, 1980.
• VTI, VLSI Design System, VLSI Technologies Inc., 1983.
• Wardle, C. L.; Watson, C. R.; Wilson, C. A.; Mudge, J. C.; and Nelson, B. J., "A Declarative Design Approach for Combining Macrocells by Directed Placement and Constructive Routing," Proceedings 21st Design Automation Conference, 594-601, June 1984.
• Watanabe, Hiroyuki, IC Layout Generation and Compaction Using Mathematical Optimization, PhD dissertation, University of Rochester Computer Science Department, TR 128, 1984.
• Weinberger, A., "Large Scale Integration of MOS Complex Logic: A Layout Method," IEEE Journal of Solid State Circuits, 2:4, 182-190, 1967.
• Weste, Neil, "Virtual Grid Symbolic Layout," Proceedings 18th Design Automation Conference, 225-233, June 1981.
• Weste, Neil and Eshraghian, Kamran, Principles of CMOS VLSI Design, Addison-Wesley, Reading, Massachusetts, 1985.
• Williams, John D., "STICKS-A graphical compiler for high level LSI design," Proceedings AFIPS Conference 47, 289-295, June 1978.
• Wilmore, James A., "Efficient Boolean Operations on IC Masks," Proceedings 18th Design Automation Conference, 571-579, June 1981.
• Wing, Omar; Huang, Shuo; and Wang, Rui, "Gate Matrix Layout," IEEE Transactions on CAD, 4:3, 220-231, July 1985.

Previous

Table of Contents

Next

Steven M. Rubin

Static Free Software