An application of L systems to local microcode synthesis

ABSTRACT

In this paper we present a formal language model of register-transfer (RT) design, and apply the model to local microcode synthesis. We transform an RT design's data-path to a DTOL system—a parallel formal grammar—and formulate the design of the control part as a parsing problem of the corresponding DTOL language. The initial specification is based on the proposed SDC model of register-transfer design. We discuss the necessary steps for transforming a legal SDC-based data-path to its equivalent DTOL system. We then propose an efficient, goal-oriented, search algorithm to parse a behavioral specification, and use this method to generate the microcode for the corresponding control part. We close by presenting two examples, using a benchmark data-path.

REFERENCES

• 1: A. Lindenmayer, Mathematical Models for Cellular Interactions in Development, Journal of Theoretical Biology, vol. 18, pp. 280-315, 1968.
• 2: A. Lindenmayer and G. Rozenberg, editors, Automata, Languages, Development, North- Holland, 1976.
• 3: Grzegorz Rozenberg , Arto Salomaa, Mathematical Theory of L Systems, Academic Press, Inc., Orlando, FL, 1980
• 4: F. Mavaddat, Designing and Modeling VLSI Systems at the Register Transfer Level, Inlemational Journal of Compuler Aided VLSI Design, vol. 2, pp. 281-314,199O.
• 5: C.E. Leiserson and J.B. Saxe, Optimizing Synchronous Systems, in PTOC. 22nd Annual Symp. on Foundations of Compuler Science, pp. 23-36, Oct. 1981.
• 6: F. Mavaddat, A Model for Register-Transfer Level Design Specification: The SDC Notation, CS-84-34, University of Waterloo, Oct. 1984.
• 7: B.M. Pangrle and D.D. Gajski, Design Tools for Intelligent Silicon Compilation, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, CAD-6(6):1098-1112, Nov. 1987.
• 8: N.D. Jones and S. Skyum. Recognition of Deterministic ETOL Languages in Logarithmic Space. Information and Control 35, pp. 177-181, 1977.
• 9: Frederick J. Hill , Gerald R. Peterson, Introduction to Switching Theory and Logical Design, John Wiley & Sons, Inc., New York, NY, 1981
• 10: M. Mahmood, F. Mavaddat, and M.I. Elmasry, Experiments with an Efficient Heuristic Algorithm for Local Microcode Generation, in PTOC. Int. Conf. on Computer Design, pp. 319-323, Cambridge, MA, Jept. 1990.
• 11: M. Mahmood, A Formal Approach to VLSI Control-Unit and Local Microcode Synthesis, Ph.D. thesis, University of Waterloo, Canada, expected 1990.
• 12: M. Mahmood, F. Mavaddat, M.I. Elmasry, and M.H.M. Cheng, A Formal Language Model of Local Microcode Synthesis, in L.J.M. Claesen (ed.), Formal VLSI Specification and Synthesis: VLSI Design Methods-I, North-Holland, 1990, pp. 23-41.
• 13: Quintus Prolog User's Guide, Quintus Computer Systems, Inc., 1986.
• 14: D.D. Gajski and D.E. Thomas, Introduction to Silicon Compilation, in D.D. Gajski (ed.), Silicon Compilation, Addison-Wesley, 1988, pp. 1-48.
• 15: M. Mahmood, F. Mavaddat, and M.I. Elmasry, A Formal Approach to Control-Unit Synthesis, in PTOC. IFIP Working Conf. on Logic and Architecture Synthesis, pp. 126-135, May 1990.