Computer Aids for VLSI Design
Steven M. Rubin
Copyright © 1994
Chapter 4: Synthesis Tools
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.
- How do PLAs and gate matrices differ in philosophy from gate-arrays?
- Why do channel and switchbox routers produce better wiring patterns than
do repeated applications of maze routers?
- What is the most difficult aspect of global routing?
- What other considerations should be addressed besides wire lengths when doing
- Why are rule-based systems attractive techniques for synthesis tools?
- Why is there little hope that silicon compilers will ever be able to
generate arbitrary and appropriate architectures?
- In what sense are the results of simulated-annealing compaction incorrect?
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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.