of 52

Monterey, California THESIS

NAVAL POSTGRADUATE SCHOOL Monterey, California o DTIC IIS ELECTE!1 v, j SIovoIZ THESIS I AUTOMATED DESIGN OF A MICROPROGRAMMED CONTROLLER FOR A FINITE STATE MACHINE by James Edward Harmon June 1988 Thesis
0 views52 pages
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Documenttranscript
NAVAL POSTGRADUATE SCHOOL Monterey, California o DTIC IIS ELECTE!1 v, j SIovoIZ THESIS I AUTOMATED DESIGN OF A MICROPROGRAMMED CONTROLLER FOR A FINITE STATE MACHINE by James Edward Harmon June 1988 Thesis Co-advisor: Thesis Co-advisor: D. E. Kirk H. H. Loomis Jr. Approved for public release; distribution is unlimited 0 UNCLASSIFIED SEC' RITY CiASS,,CATON OF - S :AGE REPORT DOCUMENTATION PAGE la REPORT SECR ', C-LSSt;CA ;- lb RESTR.CTIVE MARKINGS UNCLASSIFIED 2a SECURITY C.ASS PCTON C. A,7-OR 3 DISTRIBUTION.'AVAILAB;,:TY OF REPORT Approved for public release; 2b DEC.ASSFCA-'ON :OWNGRADtNG SC-'EDULE distribution is unlimited 4 PERFORMING ORGANIZATION REPORT NuMBER(S) 5 MONITORING ORGANIZATION REPORT NUMBER(S) 6a NAME OF PERFORMiNG ORGANIZATION 6o OFFICE SYMBOL 7a NAME OF MONITORING ORGANIZATION Naval Postgraduate School (If applicable) Naval Postgraduate School 6c. ADDRESS (City, State, and ZIP Code) 7b. ADDRESS (City, State, and ZIP Code) Monterey, California Monterey, California a \AVE Oc rind %G S-O .cO; \V- 8b OFFICE SYMBOL 9. PROCUREMENT INSTRUMENT IDENTIFICATION NUMBER ORGAN Z TO Q. (If applicable) Bc ADDRESS (City, State an ZIP Coce 10 SOURCE OF FUNDING NUMBERS PROGRAM PROJECT TASK WORK UNIT ELEMENT NO. NO. NO ACCESSION NO 11 TITLE (Include Security Classification) AUTOMATED DESIGN OF A MICROPROGRAMMED CONTROLLER FOR A FINITE STATE MACHINE 12 PERSONAL AUTHOR(S) HARMON, James E. 13a TYPE OF REPORT 13b T.ME COVERED 14 DATE OF REPORT (Year, Month, Day) 1s PAGE COUNT Master's Thesis ;ROM TO f 1988 June SUPPLEMENTARy NOTATION The views expressed in this thesis are those of the author and do not reflect the official policy or position of the Department of Defense or the U.S. Government 17 COSATi CODES 18 SUBJECT TERMS (Continue on reverse if necessary and identify by block number) FELD GROUP SUB-GROUP microprogrammed controller, VLSI design, silicon compiler, finite state machine 19 ABSTRACT (Continue on reverse if necessary and identify by block number) A Scalable Complementary Metal Oxide Semiconductor (SCMOS) microprogrammed controller for the Monterey Silicon Compiler (MSC) is implemented in the LISP programming language. The internal organization of MSC and the architectu:e of Very Large Scale Integrated (VLSI) circuits generated by MSC are discussed. 20 DiSTRIBuTION, AVAILABITY OF ABSTRACT 21 ABSTRACT SECURITY CLASSIFICATION XT, JNCLASSIFcED UNL%-iZ M;D 0l SAME AS RPT 0l DTIC USERS UNCLASSIFIED 22a NAVE Or RESPONS BLE ' DV!D'A. 22b TELEPHONE (Include AreaCode) z2c OFFICE SYMBOL H. H. Loomis, Jr. (408) Lm DD FORM 1473, 8. %1A L 83 APR ed t on may be wsed until exhausted SECURITY CLASSIFICATION OF THIS PAGE All o )er editions are obsolete a U.S. Government Printing Office f i UNCLASSIFIED Approved for public release; distribution is unlimited. Automated Design of a Microprogrammed Controller for a Finite State Machine by James Edward Harmon Lieutenant Commander, United States Navy B.S., University of New Mexico, 1975 Submitted in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE IN ELECTRICAL ENGINEERING from the NAVAL POSTGRADUATE SCHOOL June 1988 Author: ra J. E. Harmon Approved by: 26 4 L D. E. Kirk, Thesis Co-Advisor HmiLodis, Thesis Co dvisor Pwr, Chairman, Department of Electrical and Computer Engineering Gordon E. Schacher, Dean of Science and Engineering ii \ ABSTRACT A Scalable Complementary Metal Oxide Semiconductor (SCMOS) microprogrammed controller for the Monterey Silicon Compiler (MSC) is implemented in the LISP programming language. The internal organization of MSC and the architecture of Very Large Scale Integrated (VLSI) circuits generated by MSC are discussed. ,, ; OPY fn SP ECTED. H... .. i iii TABLE OF CONTENTS I.INTRODUCTION A. SILICON COMPILERS B. MONTEREY SILICON COMPILER (MSC) PROJECT C. MICROPROGRAMMED CONTROLLER D. NAME CONVENTIONS E. CONTENT DESCRIPTION Analysis Phase Design Phase Implementation Phase Test Phase Maintenance Phase I.MSC TARGET ARCHITECTURE A. PHYSICAL LAYOUT Data Path Control Logic Array B. FINITE STATE MACHINE (FSM) ARCHITECTURE Moore FSM Mealy FSM Moore FSM Timing Mealy FSM Timing State Transition Diagram Moore FSM State Transition Diagram Mealy FSM State Transition Diagram iv In. ns -_ C. MSC FSM STRUCTURE D. MULTIPLE FSM INTERACTION nmos Multiplexer Wired AND Logic SCMOS Multiplexer Logic E. ARCHITECTURAL REQUIREMENTS I II.MSC INTERNAL STRUCTURE A. DATA PRIMITIVES B. DATA STRUCTURES I C. CONTROL AND DATA FLOW D. PROGRAM COMPONENTS Program lincoln.l Program c-routines.c Program L Program defstructs.l Program front-page.l Program prepass.l Program library Program organelles.l Program general.l Program extract.l a. Get-sequencers-from-component-list b. Get-sequencers-required-definitions C. Extract-component-list d. Post-process Program order.l Program frame.l V 13. Program data-path Program control Program flags.l Program pads a. Program padgen.l b. Pad File pad2ob c. Pad File rinout Program interpret.l Makefile E. MSC INTERNAL STRUCTURE REQUIREMENTS IV. CONTROLLER GOALS AND REQUIREMENTS A. MSC CONTROLLER GOALS B. MSC CONTROLLER REQUIREMENTS V. ARCHITECTURE TRADE-OFF STUDIES A. LOGIC STRUCTURE TRADE-OFF STUDIES Structural Requirements Analysis a. Static CMOS Complementary Logic b. Pseudo-nMOS Logic c. Dynamic CMOS Logic d. Clocked CMOS Logic e. CMOS Domino Logic f. Cascade Voltage Switch Logic g. Modified Domino Logic h. Transmission Gate Logic i. Acceptable Structures Structural Goals Analysis vi - W VW WMIM,.1W a. Static CMOS Complementary Logic b. Pseudo-nMOS Logic c. Static Cascade Voltage Switch Logic d. Complementary Transmission Gate Logic Structure Selection B. LOGIC ORGANIZATION TRADE-OFF STUDIES Data Path Units a. Sequencer Types b. Data Path Unit Advantages c. Data Path Unit Alternatives Standard Cell or Microprogram ROM a. Standard Cell b. Microprogram ROM C. LOGIC STRUCTURE AND ORGANIZATION SELECTION VI. CONTROLLER DESIGN A. FUNCTIONAL REQUIREMENTS PARTITIONS B. UNIT IDENTIFICATION Data Path Units Microprogram ROM Units a. ROM Array b. Row Decoder c. Conditional d. Buffer C. FLOOR PLAN Controller Floor Plan Microprogram ROM Floor Plan vii Immxr t xm~ mum.it-x D. CELL LOGIC FUNCTIONS ROM Array Cells a. ROMi Cell b. ROMO Cell c. ROMnull Cell Row Decoder Cells a. DecodeLSB Cell b. DecodeEvenO and DecodeEveni Cells C. DecodeOddO and Decodeoddl Cells d. Evenlnverter and Oddlnverter Cells e. EvenConnect and OddConnect Cells f. Two-State Cell Conditional Cells a. COND Cell b. CONDtrue Cell c. CONDfeed and TopCONDfeed Cells d. CONDtap Cell e. CONDpass Cell f. CONDnopass Cells Buffer Cells a. RowBuffer Cell b. CONDbuffer Cell c. LSBbuffer Cell d. EvenBuffer Cell e. OddBuffer Cell E. CELL INTERNAL STRUCTURE viii 1.AM1 RO Ara Cll ROMira Cell a. ROMO Cell b. ROMnul Cell RDeoderl Cells a. DecodeLSB, DecodeEvenO, and DecodeEveni Cells b. DecodeOddO and DecodeOddl Cells c. Evenlnverter and Oddlnverter Cells- 130 d. EvenConnect and OddConnect Cells e. Two-State Cell Conditional Cells a. COND Cell b. CONDtrue Cell c. CONDfeed, TopCONDfeed, CONDtap, CONDpass, arnd CONDnopass Cells Buffer Cells a. RowBuffer Cell b. CONDbuffer Cell c. LSBbuffer Cell d. EvenBuffer and OddBuffer Cells F. DESIGN VERIFICATION VII. CONTROLLER IMPLEMENTATION A. MSC SOFTWARE INSTALLATION B. MSC MAGIC AND SCMOS UPGRADE C. CELL LAYOUT AND TEST D. ADDITION OF CELLS TO MSC ix E. MSC CONTROLLER EXTENSION Object File Modifications Extract.l Modifications Extraction Example Control.l Modifications Single Bit Data-Path F. IMPLEMENTATION STATUS VIII. CONTROLLER TESTING IX. CONCLUSIONS A. CONTROLLER DESIGN B. MSC STRUCTURE C. ADDITIONAL RESEARCH APPENDIX A ISI INSTALLATION LOG APPENDIX B SOFTWARE CHANGE PROPOSAL SCP LIST OF REFERENCES BIBLIOGRAPHY INDEX INITIAL DISTRIBUTION LIST x LIST OF TABLES TABLE 1.1 FILE NAME EXTENSIONS AND FILE TYPES TABLE 3.1 DATA PRIMITIVES TABLE 3.2 SEQUENCER TYPES TABLE 3.3 COUNTER-STACK SEQUENCER DEFINITIONS TABLE 3.4 COUNTER-NO-STACK SEQUENCER DEFINITIONS TABLE 3.5 NO-COUNTER-NO-STACK SEQUENCER DEFINITIONS xi ~ C~o~6 LIST OF FIGURES Figure 1.1 Silicon Compiler Figure 1.2 Microprogrammed Controller Figure 2.1 MSC Floor Plan Figure 2.2 Data Path Organization Figure 2.3 Register Unit Figure 2.4 Output Port and Internal Port Units Figure 2.5 Bit Unit Figure 2.6 Organelle Unit Figure 2.7 Unit Multiplexer Optiois Figure 2.8 Moore Finite State Machine Figure 2.9 Mealy Finite State Machine Figure 2.10 Moore FSM Timing Figure 2.11 Mealy FSM Timing Figure 2.12 Moore FSM State Transition Diagram Figure 2.13 Mealy FSM State Transition Diagram Figure 2.14 MSC Finite State Machine Figure 2.15 Multiple FSM Interaction Figure 2.16 Multiplexer Wired AND Logic Figure 3.1 MSC Control Flow Figure 5.1 Static CMOS Complementary Logic Figure 5.2 Pseudo-nMOS Logic Figure 5.3 Dynamic CMOS Logic Figure 5.4 Clocked CMOS Logic Figure 5.5 CMOS Domino Logic xii Figure 5.6 Cascade Voltage Switch Logic Figure 5.7 Transmission Gate Logic Figure 5.8 Transmission Gate Discrete Components Figure 5.9 Transmission Gate Logic Reduced Circuit Figure 5.10 No-Counter-No-Stack Sequencer Figure 5.11 Counter-No-Stack Sequencer Figure 5.12 Counter-Stack Sequencer Figure 6.1 Microprogram ROM Units Figure 6.2 Controller Floor Plan Figure 6.3 Alternate Controller Floor Plan Figure 6.4 Second Alternate Controller Floor Plan Figure 6.5 Microprogram ROM Floor Plan Figure 6.6 ROM Array Cells Figure 6.7 Row Decoder Figure 6.8 DecodeLSB Cell Figure 6.9 DecodeEvenO and DecodeEvenl Cells Figure 6.10 DecodeOddO and DecodeOddl Cells Figure 6.11 EvenInverter and OddInverter Cells Figure 6.12 EvenConnect and OddConnect Cells Figure 6.13 Two-State Cell Figure 6.14 Conditional Cells Figure 6.15 COND and CONDtrue Cells Figure 6.16 TopCONDfeed and CONDfeed Cells Figure 6.17 CONDtap, CONDpass, and CONDnopass Cells Figure 6.18 RowBuffer and CONDbuffer Cells Figure 6.19 LSBbuffer Cell xiii Figure 6.20 EvenBuffer and OddBuffer Cells Figure 6.21 ROM Array Cells Figure 6.22 Row Decode Logic Figure 6.23 DecodeLSB, DecodeEvenO, and DecodeEveni Logicl27 Figure 6.24 NOR Gate Figure 6.25 Decodeoddo and DecodeOddi Logic Figure 6.26 NAND Gate Figure 6.27 Evenlnverter and Oddlnverter Logic Figure 6.28 Inverter Figure 6.29 Two-State Logic Figure 6.30 COND Logic Figure 6.31 CONDtrue Logic Figure 6.32 RowBuffer and CONDbuffer Logic Figure 6.33 LSBbuffer Logic Figure 6.34 EvenBuffer and OddBuffer Logic Figure 7.1 Taxi Microprogram ROM Design xiv Dedicated to my wife, Emilie xv I. INTRODUCTION This thesis encompasses a complete development process. The goal of this process is to produce a Finite State Machine (FSM) controller that can be generated by a silicon compiler. This development supports the silicon compiler project at the Naval Postgraduate School. A. SILICON COMPILERS A silicon compiler' is a collection of computer programs that translates a high-level description of a Very Large Scale Integrated (VLSI) circuit into a complete layout that can be used to fabricate the circuit. The basic function of a silicon compiler is shown in Figure i To generate a layout, the silicon compiler produces instances of standard cells and interconnects them as required by the circuit description. The primary advantages of a silicon compiler are speed and reliability of design. A silicon compiler can produce a layout in minutes that would take months for a team of VLSI designers. A good silicon compiler will consistently produce correct layouts. A layout produced by hand may include errors. The disadvantage of using a 1 For more information on silicon compilers, see Princi- Rles of CMOS VLSI Desigin (Weste and Eshraghian, pp , 1985) and VLSI Electronics: Microstructure Science (Einspruch, Vol. 14, pp , 1986). Circuit Description Silicon Compiler Cell Ubrary Circuit Layout Figure 1.1 silicon Compiler silicon compiler is efficiency. A layout produced by a silicon compiler may be larger and slower than a layout produced by a skilled VLSI designer. Although layouts produced by future silicon compilers may be able to surpass the efficiency of layouts produced by human designers, current silicon compilers are most effective for rapid development of custom VLSI circuits that will not have large production runs. For a circuit that will have a large production run, the higher efficiency and smaller size of a human layout will offset the increased design cost that can be amortized over a large number of units. Many military circuits which have small production runs and require high reliability and 2 short development time are ideal for current silicon compilers, provided that performance requirements can be satisfied. B. MONTEREY SILICON COMPILER (MSC) PROJECT The Monterey Silicon Compiler (MSC) project at the Naval Postgraduate School is producing a technology independent silicon compiler. Based on the MacPitts 2 silicon compiler produced by MIT Lincoln Laboratory, MSC is written in the LISP 3 programming language. At present, MSC is essentially a modified version of MacPitts. Thus, the nmos capabilities and architecture of MSC are those of MacPitts. Circuit design specifications processed by MSC are in LISP format. The layout produced by MSC is a Caltech Intermediate Form (CIF) 4 file that can be used to fabricate a circuit at many VLSI foundries. MSC currently supports n-channel Metal Oxide Semiconductor (nmos) technology. Present development work on MSC involves the addition of Scalable Complementary Metal Oxide Semiconductor (SCMOS) technology. The microprogrammed controller in this thesis supports the SCMOS technology addition to MSC. 2 Use of the MacPitts silicon compiler is described in Introduction to MacPitts (MIT RVLSI-3, 10 February 1983). 3 MSC is written in Franz Lisp. For more information on Franz Lisp, see LISPcraft (Wilensky, 1984). 4 CIF is explained in A Guide to LSI Implementation (Hon and Sequin, pp , January 1980). 3 C. MICROPROGRAMMED CONTROLLER A microprogrammed controller is an electronic circuit that generates time based control signals for other circuits. The general configuration Qf a microprogrammed controller is shown in Figure 1.2. It contains a Read Only Memory (ROM) and next address logic. The ROM words contain information for controller output and for next address determination. The status inputs and next address information are used by the next address logic to determine the next ROM address. If each output signal corresponds to one bit of the words in the ROM, the microprogram format is horizontal. If the outputs are produced by decoding a smaller number of Clock Device Being Controlled Status Control Outputs Inputs Next Next Address Information Read Next Clock Address Address Only Logic Memory Figure 1.2 Microprogrammed Controller 4 -~~~ A r,~... ,g Ar,-, ~~et M M mt J bits in the ROM words, the microprogram format is vertical. Microprogrammed controllers are used in many applications from traffic lights and microwave ovens to computers. The MSC application of a microprogrammed controller contained in this thesis is similar to the controller in a microprocessor. D. NAME CONVENTIONS File name extensions and the file type associated with them are listed in Table 1.1. The extension is the last part of a file name. The library file is an exception to the file name extension convention. This file contains LISP TABLE 1.1 FILE NAME EXTENSIONS AND FILE TYPES File Name Extension No Extension File Type Executable File.c C Language Source File.cif.ext CIF File Circuit Extraction File.1 LISP Language Source File.mac.mag MSC Source File Magic Layout File.o Compiled Object File.obj.sim MSC Object File Simulation File 5 formatted statements that are interpreted while MSC is running. E. CONTENT DESCRIPTION The organization of this thesis matches a phased development process Analysis Phase The analysis phase includes planning, setting goals, and defining requirements. Chapter II starts the analysis phase with an examination of the nmos layout produced by MSC and development of architectural requirements for the controller. Chapter III includes a description of the programs and functions in the nmos MSC and software requirements for the controller. Chapter IV completes the analysis phase with a definition of MSC controller goals and a fusion of the requirements developed in Chapters II and III. 2. Design Phase The design phase starts with trade-off studies in Chapter V. In this chapter, different SCMOS logic structures and controller organizations are evaluated using the goals and requirements of Chapter IV. The logic structure and controller organization selected in Chapter V are used to create the design presented in Chapter VI. The design in 5 Based on the phased life-cycle model in Software Enuineering Concepts (Fairley, pp , 1985) Chapter VI is in two sections. One section is technology independent and one section is for the SCMOS technology. 3. Implementation Phase The implementation phase is contained in Chapter VII. The first part of implementation involves installation of the nmos MSC and modification to support the SCMOS technology. The second part of implementation involves layout and test of each cell in the SCMOS section of Chapter VI. 4. Test Phase The test phase is documented in Chapter VIII. This phase involves integration and test of controllers constructed from the cells generated in Chapter VII. The systems produced are verified against the design in Chapter VII and validated against the requirements in Chapter IV. 5. Maintenance Phase The maintenance phase of the controller starts with the conclusions presented in Chapter IX. These conclusions involve refinements to the design, methods of installing the controller in MSC, and suggested improvements to the organization of MSC. Additional research in support of MSC is included in these conclusions. 7 II. MSC TARGET ARCHITECTURE Understanding the physical and functional properties of the MSC target architecture is crucial to the formulation of requirements for the microprogrammed controller that is the subject of this thesis. MSC produces layouts for complete nmos VLSI circuits that may include one or more finite state machine controllers. A. PHYSICAL LAYOUT An MSC layout includes pads, a control logic array, a data path, a flags area, and distribution structures for signals and power. MSC nmos VLSI layout. Figure 2.1 shows the floor plan of an The perimeter of the layout is a pad frame with pads on three sides. The pads are numbered sequentially in a clockwise direction starting at the left pad on the top edge. Inside the pad frame is a frame for drain power (Vdd) and ground (GND) distribution. In between the pad frame and the Vdd and GND frame is a routing channel for signals to and from the pads. Inside the Vdd and GND frame are the data path, flags area, and control logic array. The data path and control logic array are separated by horizontal clock and power buses. The flags area is to the right of the data path. The pads are used for connections between the VLSI circuit and the package that encloses it. Word size data processing is accomplished in the data path and 8 Pad 1 PADS DATA ROUTING D. DQ A. A N T. A T DATA PATHA SFLAGS 0 S D T~ CLOCK BUSSES/DRIVERS T.U1 N DATA/CONTROL ROUTING N. G G CONTROL LOGIC ARRAY POWER FRAMEk DATA ROUTING El1 El E] E E]1 PADS Figure 2.1 MSC Floor Plan 9 single bit processing is accomplished in the control logic array. Word size data storage is performed in the data path and single bit storage is performed in the flags area. 1. Data Path The data path in an MSC layout is the area that contains most of the structures used for data processing and data storage. It is organized horizontally in bit slices and vertically in units. This organization is shown in Figure 2.2. Each horizontal bit slice contains all of the processing elements for one bit of word size data. Each vertical unit contains similar elements that perform one function on all bits in word size data structures. There are five types of units: register, output p
Advertisement
MostRelated
View more
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x