Automated layout synthesis in the YASC silicon compiler

ABSTRACT

In this paper, we present algorithms and experimental results for an automated layout synthesis procedure that is used in a high-level silicon compiler. The techniques consist of a unique approach to generalized cell synthesis, together with a novel solution of the placement and routing problem. Our algorithms take advantage of a larger space of possible solutions than is available in conventional, fixed-cell approaches to achieve compact and efficient layouts. First, our techniques for cell synthesis are presented. Then, we describe our placement algorithm, in which the locations of the cells are determined by signal-flow considerations. Next, our pin permutation procedure is described. These permutations are not limited to the relatively few cases of logically equivalent pins, but rather, can exploit a much larger set of transformations involving the re-arrangement of the inner structure of the cells themselves. Finally, our techniques for both global and channel routing are discussed. Experimental results for a complete chip layout are included.

REFERENCES

• 1: David E. Krekelberg , Gerald E. Sobelman , Chu S. Jhon, Yet another silicon compiler, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.176-182, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317854]
• 2: C. S. John, G. E. Sobelman and D. E. Krekelberg, "Silicon Compilation Based on a Data-flow Paradigm", IEEE Circuits and Devices, Vol. I, No. 3, pp. 21-28 (1985).
• 3: C. S. Jhon, D. E. Krekelberg and G. E. Sobelman, "A Silicon Compilation Approach to Supercomputer Design", Proceedings, International Symposium on Circuits and Systems, pp. 47-50, Kyoto, Japan (1985).
• 4: R. K. Brayton, C.-L. Chert, C. T. McMullen, R. H. J. M. Otten and Y. J. Yamour, "Automated Implementation of Switching Functions as Dynamic CMOS Circuits", Proceedings, Custom Integrated Circuits Conference, pp. 346-350, Rochester, NY (1984).
• 5: T. Uehara and W. M. van Cleemput, "Optimal Layout of CMOS Functional Arrays", IEEE Transactions on Computers, Vol. C-30. No. 5, pp. 305-312 (1985).
• 6: R, Nair, A. Bruss and J. Reif, "Linear Time Algorithms for Optimal CA#mS Layout", in VLSI: Ajgorithms and Architectures, Elsevier Computer Science Publishers, pp. 327-338 (1985).
• 7: C. T. McMullen and R. H. J. M. Otten, "Layout Compilation of Linear Transistor Arrays", Proceedings, International Symposium on Circuits and Systems, pp. 5-7, Kyoto, Japan (1985).
• 8: kH. W. Leong and C. L. Liu, "Permutation Channel Routing", Proceedings, IEEE International Conference on Computer Desiqn: VLSI in Computers, pp. 579-584, Port Chester, New York (1985).
• 9: M. Terai, "A Method of Improving the Terminal Assignment in the Channel Routing for Gate Arrays", IEEE Transactfons of Computer-Aided Design, Vol. CAD-4, No. 3, pp. 329-336 (1985).
• 10: Gerald E. Sobelman , David E. Krekelberg, Advanced C: Techniques and Applications, Que Corp., Indianapolis, IN, 1986
• 11: R~ H. Krambeck, C. M. Lee and H.-F. S. Law, "High Speed Compact Circuits with CMOS", ZEEE Journal of Solid State Circuits, Vol~ SC-17, No. 3, pp. 614-619 (1982).
• 12: L. G. Heller, W. R. Griffin, J. W. Davis and N. G. Thoma, "Cascade Voltage Switch Logic: A Differential CMOS Logic Family", Proceedings, IEEE international Solid State Circuits Conference, pp. 16-17, San Francisco, California (1984).

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Languages and compilers
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing; Simulation

  J. Computer Applications

General Terms:
Algorithms, Design, Experimentation, Languages, Performance, Theory