Computer Design A computer aided design and VLSI approach Paul J. Drongowski Chapter 9 - Control representation. In Chapter 8 we presented a simple scheme for the synthesis of an initial datapath for an ISA specification. We will now introduce a notation for expressing the control portion of the machine design and apply the notation to the SP.1. Section 1 - Control notation. The datapath portion of the ISA implementation is responsible for performing data storage, computation and transfer operations. In order to interpret the ISA, a (macro) instruction must be fetched from memory, decoded and interpreted through a sequence of datapath operations. The controller is a finite state machine that responds to (macro) instruction operation codes and processor conditions, and evokes the appropriate sequence of datapath operations to execute the instruction. | MICxx V XXX -------------------- | Description | |--------------------| | Actions | |--------------------| | Branch test | XXX -------------------- | V Figure 1 - Event (operation) symbol. The control notation must show the datapath operations to be invoked by the controller, the sequence in which those operations are to be invoked, and the conditions (control branches) that will affect the operation sequence. Practical issues such as the physical implementation of the operations and the decomposition and refinement of the control design must also be addressed. We will use a flow graph notation to describe the control design. Figure 1 shows the symbol for a control event -- a group of datapath operations to be performed and an optional control branch. The flow from one event to the next event is specified by drawing an arrow (arc) from the first event symbol to the symbol standing for the next event. A sequence of three events is shown in Figure 2. | FIG00 V 035 -------------------- | Subtract 1 from CR | |--------------------| | CR <- CR - 1 | -------------------- | FIG01 V 092 -------------------- | Set Z flag | |--------------------| | Z <- (CR = 0) | -------------------- | FIG02 V 016 -------------------- | Advance instr ptr | |--------------------| | IP <- IP + 1 | -------------------- | V Figure 2 - A sequence of three events. Six different annotations may appear in and around an event symbol. All symbols should be labeled with a name (appearing above the upper left corner of the symbol box) which gives some mnemonic indication of the symbol's function. A good naming convention splits the mnemonic into two parts. The first few characters group all of the events belonging to a particular ISA feature such as the Call instruction or fetch, decode and execute loop. The characters that follow in the mnemonic identify a specific event within a group. Thus, in Figure 2, all of the mnemonics share the prefix "FIG" and each event can be identified as "FIG00," "FIG01," and "FIG02." The annotation appearing above the upper right corner gives the physical location of the event in the controller. For microprogrammed machines, the physical location is the address of the microinstruction which corresponds to that control event. This identifier helps during debug to trace event execution. The microinstructions for FIG00, FIG01 and FIG02 will be stored at addresses 35, 92 and 16, respectively. | BRA03 V 061 -------------------- | Test Z and branch | |--------------------| | IP <- IP + 2 | |--------------------| | Branch on Z flag | 032,033 -------------------- | V Figure 3 - Branch example. The event box is separated in two, or optionally three parts. (Not all events will branch.) The top part contains a descriptive comment that should be as informative as possible. The middle part contains the datapath operations and transfers to be performed when the event is executed. The bottom and optional part specifies any control branch to be performed after the event. The branch box must specify the processor condition to be tested and one or more target locations for the branch (drawn next to the lower right hand corner.) An example event symbol is shown in Figure 3 that tests the state of the Z flag and branches to location 32 or 33 if Z is true or false, respectively. ( Entry ) | V Figure 4 - Entry symbol. | V < Entry > Figure 5 - Exit symbol. Symbols for off-page control flow appear in Figures 4 and 5. The entry symbol defines a point to which control may be sent from an exit symbol. Entry names must be unique, but two or more exit symbols may dispatch control to the same entry. Entry and exit symbols should be used to improve the readability of the control design. For a complex machine like the VAX, the control graph will cover many pages with a large number of entry and exit points. Entry names and event mnemonics can be used the designer or CAD system to manipulate and analyze the control design (i.e., they make good database identifiers or keys.) Section 2 - Semantics. Since the control graph is interpreted with respect to a particular datapath design, the actions and branch tests cannot be arbitrary. They must have physical relevance in the datapath. * Data operations and transfers (assignments) must be performed in one control step. * Branch conditions must be produced by the datapath and routed to the controller. Thus, the permissible assignments and the shape of the control graph will very much depend upon the registers, data operators and interconnections in the datapath. If information must be transfered from register A to C via intermediate register B, for example, then two sequential control events will be required. The number of operations to be performed in one step will depend upon the available parallelism in the datapath. (This is the subject of Chapter 11 on style.) | FIG04 V 043 -------------------- | Transfer to B 1st | |--------------------| | B <- A | -------------------- | FIG05 V 078 -------------------- | Then transfer to C | |--------------------| | C <- B | -------------------- | V Figure 6 - Transfer from A to C via B. The control style will also affect the topology of the graph. Factors here are the mechanism for selecting control events, microinstruction pipelining, the availability of independent processing elements, the use of single or multiple phase clocking, and the use of a stoppable clock. In describing the notation above, we assumed a non-pipelined, microprogrammed controller. Eventually, each control event will be translated to a binary microinstruction which will invoke the desired datapath operations. Sections 3 - SP.1 example. Before moving on to the issues of style and parallelism, let's take a look at a few examples based upon the SP.1. The fetch and decode portion of the SP.1 ISA is implemented by the graph in Figure 7. The SP.1 instruction is fetched and the instruction pointer is advanced in one event (FET00.) The operation code is decoded and control is dispatched to one of sixteen subgraphs. ( Fetch ) | FET00 V -------------------- | Fetch and decode | |--------------------| | IR<-M[IP];IP<-IP+1 | |--------------------| | Branch on IR<7:4> | -------------------- | V ----------------------- | | | |-> < Add > |-> < Call > |-> < Ret > |-> < Brz > Figure 7 - Fetch and decode. Figure 8 is the subgraph for the Add instruction. It simply adds the contents of the AC with the MD and stores the results back into the AC register. Control returns to the fetch and decode routine through the exit point. ( Add ) | ADD00 V -------------------- | Add MD to AC | |--------------------| | AC <- AC + MD | -------------------- | V < Fetch > Figure 8 - Add instruction. Figures 9 and 10 show the subgraphs for the SP.1 Call and Return instructions. Figure 9 is a sequence of two events while the return requires only one control event. After the graphs are executed, control will flow back to the fetch and decode graph. ( Call ) | CAL00 V -------------------- | Read entry address | |--------------------| | IR<-M[IP] | -------------------- | CAL01 V -------------------- | Transfer to IP | |--------------------| | IP <- IR | -------------------- | V < Fetch > Figure 9 - Call instruction. ( Ret ) | RET00 V -------------------- | Move SR to IP | |--------------------| | IP <- SR | -------------------- | V < Fetch > Figure 10 - Return instruction. Figure 11 illustrates a two way branch. To implement the SP.1 branch on zero instruction, the controller must test the state of the Z flag and either continue execution with the next IP value or branch to a new location. The false and true branches of the graph are clearly identified. Ultimately, execution will flow back to fetch and decode. ( Brz ) | BRZ00 V -------------------- | Read addr, test Z | |--------------------| | IR<-M[IP];IP<-IP+1 | |--------------------| | Branch on Z flag | -------------------- | V False(0) -------------------------- True(1) | | | BRZ01 V | -------------------- | | Perform branch | | |--------------------| | | IP <- IR | | -------------------- | | V V -------------------------- | V < Fetch > Figure 11 - Branch on zero instruction. Copyright (c) 1987-2013 Paul J. Drongowski