31.

[Top] [Next] [Prev]


1. (Register Transfer and State Diagrams) Assume that you have a bus-connected assembly of a 4-bit subtractor and four registers, as shown in Figure Ex11.1.

All registers are positive edge--triggered, and registers R2 and O have tri-state outputs. All buses are 4 bits wide. You are to perform the following sequence of register transfer -operations: (1) compute R1-R0, latching the result into R2, (2) display the result on the LEDs attached to register O, and (3) replace R0 with the result.

Tabulate all of the register transfer operations and their detailed microoperations that are supported by this data-path organization.

Create a timing waveform for the control signals LD (load), S (select), and OE (output enable) to implement this sequence in a minimum number of clock cycles. This diagram should include traces for all of the control signals in the figure: R0:LD, R1:LD, A:S, B:S, R2:LD, R2:OE, O:LD, O:OE. Recall that the state changes on the positive edge of the clock, and don't forget to incorporate signal propagation delays in your timing waveforms.

Show the state diagram, annotated with control signal assertions and their corresponding register transfer operations, that corresponds to the timing waveforms you filled out in part (b).

2. (Memory Interface) A read-only memory and a microprocessor need to communicate asynchronously. The processor asserts a signal to indicate READ and sets the ADDRESS signals. The memory asserts COMPLETE when the data is available on the DATA signals. Draw two simple state diagrams that indicate the behavior of the processor and the memory controller for a simple read operation. The READ and COMPLETE signals should follow the four-cycle handshake protocol. Assume that the memory controller cycles in an initial state waiting for a memory READ request.

3. (Memory Interface) For the memory interface and state diagrams in this chapter, we assumed a Princeton architecture. In this exercise, you will rederive these for a Harvard architecture.

Modify the memory interface of Figure 11.5 for a Harvard architecture. Provide two separate memory interfaces, one for instructions and one for data.

What changes are necessary in the state diagram of Figure 11.23 to reimplement this machine for a Harvard -architecture?

What new register transfer operations are needed to support this alternative memory interface? Modify Figure 11.24 to reflect these additions.

4. (Instruction Prefetch) In Exercise 11.3 you modified the memory interface to provide separate instruction and data memories. Modify the state diagram of Figure 11.23 to allow the next instruction to be fetched while the current instruction is finishing its execution. Tabulate the register transfer operations used in each state.

5. (Control State Diagram) The state diagram derived in Section 11.3.2 assumed a synchronous Mealy implementation. Rederive the state diagram, but this time assume a Moore machine implementation. Associate the appropriate register transfer operations with the states you derive. Also describe for each state the function, such as instruction fetch, operand fetch, or decode that it is implementing.

6. (Datapath Design) Consider the following portion of a simple instruction set encoded in 4-bit words. The machine has a single accumulator (R0), a rotating shifter (R1), four general-purpose registers (R0, R1, R2, R3), four accumulator/shifter oriented instructions (COMP, INC, RSR, ASR), and two register-register instructions (ADD, AND). In register transfer-like notation, these instructions are defined as follows:

Op Code (Binary)	Op Code (Symbolic)	Function
00 X1X0	ADD	R[0] := R[0] + R[X1X0]
01 X1X0	AND	R[0] := R[0] AND R[X1X0]
10 00	COMP	R[0] := ~R[0]
10 01	INC	R[0] := R[0] + 1
10 10	RSR	R[1]<0> := R[1]<1>,
		R[1]<1> := R[1]<2>,
		R[1]<2> := R[1]<3>,
		R[1]<3> := R[1]<0>;
10 11	ASR	R[1]<0> := R[1]<1>,
		R[1]<1> := R[1]<2>,
		R[1]<2> := R[1]<3>,
		R[1]<3> := R[1]<3>;

Note that X1X0 represents a 2-bit encoding of the operand register. The RSR is a logical shift right: the 4-bit word is shifted from left to right, with the low-order bit replacing the high-order bit. ASR is an arithmetic shift right: the high-order bit fills the bit to its right during the shift while retaining its value. If the register contains signed data, the shift has the effect of dividing by 2 whether the stored number is positive or negative.

Design a point-to-point data-path that is appropriate for this instruction set fragment. Assume that you can use an -appropriately designed ALU and a shifter as functional units in your data-path. You may use multiplexers wherever you need them. Draw the register transfer diagram associated with your design.

Tabulate the register transfer operations and microoperations supported by your data-path.
Consider the execution of the ADD instruction. Draw a state diagram fragment that shows the sequencing of control signal assertions to implement the ADD instruction. How many states are required to execute the instruction?

Repeat part (c), but this time for the RSR instruction.

7. (Datapath Design) Repeat Exercise 11.6, but this time design the data-path using a single-bus interconnection scheme.

8. (Datapath Design) Repeat Exercise 11.6, but this time design a compromise multiple-bus data-path. Your goal should be to reduce the number of states it takes to implement the ADD and RSR instructions, short of using the point-to-point scheme.

9. (Control State Machine) The instruction set fragment of Exercise 11.6 provides no way to load the registers. We add the following multiple-word instructions to accomplish these functions:

1100 Y3Y2Y1Y0	XFER	R[Y3Y2] := R[Y1Y0]
1101 Y7Y6Y5Y4 Y3Y2Y1Y0	LD	R[0] := MEM[Y7Y6Y5Y4 Y3Y2Y1Y0]
1110 Y7Y6Y5Y4 Y3Y2Y1Y0	ST	MEM[Y7Y6Y5Y4 Y3Y2Y1Y0] := R[0]

The XFER instruction, encoded in two adjacent words in memory, replaces the register indicated by the high-order 2 bits of the instruction's second word with the register denoted by its 2 low-order bits. The LD (load) and ST (store) instructions are encoded in three adjacent words: the first denotes the instruction, the second and third the memory address (this machine can address up to 256 four-bit words). For completeness, the last instruction is BRN, Branch if R0 is Negative:

1111 Y7Y6Y5Y4 Y3Y2Y1Y0	BRN	IF R[0]<3> = 1 THEN
		PC := Y7Y6Y5Y4 Y3Y2Y1Y0

Draw the state diagram fragment for the instruction fetch and operation decode, given that an instruction may be encoded in one, two, or three 4-bit words.

Draw the memory interface register transfer diagram and the control's set of registers (PC, IR, possibly others). What new register transfer operations and microoperations are added by these four instructions?

10. (Datapath Design) How does the register-to-register transfer operation (XFER) affect your data-path designs in Exercises 11.6 (point-to-point), 11.7 (single bus), and 11.8 (multiple buses)?

11. (Datapath Design) Put together a unified data-path, integrating the control registers (PC, IR, etc.) from Exercise 11.9 with your data-paths from Exercises 11.6, 11.7, and 11.8. How many processor states (total clock cycles) does it take to implement the ADD and RSR instructions in each data-path? Explain how you derived your state/cycle count.

12. (Datapath Design) Consider the following change to the instruction set description of Exercise 11.6. The RSR and ASR are eliminated from the instruction set and replaced by the following two -instructions:

1010	CLC	CARRY := 0
1011	ADC	R[0] := R[0] + CARRY
		CARRY := Carry out from ALU

The ADD instruction now saves its carryout into a special Carry register. This is cleared by the CLC instruction and can be added to R0 by the ADC (add with carry) instruction.

How should the data-path be modified to support these instructions? Assume the ALU can perform only standard ADD, -INCrement, AND, and COMPlement operations.

Draw the state diagram fragment implementing the execution sequences for the ADC and CLC instructions.
Describe how the execution sequence for ADD is changed by introducing these instructions.

13.(Processor Datapath and Control) Consider the instruction format for a 16-bit computer in Figure Ex11.13. The high-order 4 bits specify the operation code. Every instruction contains two operands. The first operand is always one of the processor's general-purpose registers, which is specified by the Reg A field in the instruction (the machine has four general-purpose registers, R0, R1, R2, and R3). The second operand is always in memory. Its address is formed by the sum of the contents of a register, indicated by the Reg B field, and the offset value within the instruc-tion. The machine's initial data-path is shown in Figure Ex11.13. The ALU implements ADD, SUB, and so forth.

Tabulate the microoperations implied by the above data-path. Group the operations by common sources or destinations.

Write a sequence of register transfer microoperations to implement the execution of an Add instruction (assume the instruction has already been fetched and decoded), given the following "macrodefinition" of the add: ADD Ra, (Rb)offset  Ra := Ra + Memory[Rb + Offset]

For example, if the instruction is "Add R0, (R1) 10" and R1 contains 5, then the contents of memory location 15 are added to the contents of R0, with the result stored back into R0.

Assume that a memory access requires only a single state. Indicate any changes to or assumptions about the register transfer operations supported by the data-path to implement the instruction's execution sequence (you may need to add additional paths or operations). In your answer, show how register transfer operations should be grouped into states.

Write a sequence of register transfer microoperations to implement the execution of a Branch Negative instruction (assume the instruction has already been fetched and decoded), given the following macrodefinition of the branch: BRN Ra, (Rb)offset  If Ra < 0 then PC := Rb + Offset

However, unlike the add instruction, the offset in the branch instruction is a twos complement number. In other words, the offset can be interpreted as a number between +127 and -128. State any additions to or assumptions about the data-path that must be made to implement the execution sequence of this instruction. As in part (b), group the register transfer instruction into states.

14. (Processor Specification and Datapath Design) In this exercise, you will describe the architecture of a simple 4-bit computer. The machine is organized around an evaluation stack, an ALU that supports the twos complement operations SUB, ADD, and INCRement and the logical operators AND, OR, and COMPlement, and a rotating shifter supporting both logical rotating shifts and arithmetic shifts. The machine supports 16 different instructions, including those for accessing memory, call/return from subroutine, and conditional/unconditional branches. These instructions are encoded in one to three 4-bit word parcels. The machine can address 256 four-bit words, organized as a Harvard architecture.

A stack is a data structure in which the element last added is the first to be deleted. Hence, stacks are often called last in, first out data structures. Items are PUSHed to the top of the stack and POPed from the top of the stack. Consider the expression 9 - (5 + 2). This can be implemented by the following sequence of stack-oriented operations:

PUSHC	9	; Push constant 9 to top of stack
PUSHC	5	; Push constant 5 to top of stack
PUSHC	2	; Push constant 2 to top of stack
ADD		; Top two elements of the stack are added
		; Remove and replace with the number 7
SUB		; Top two elements of the stack are subtracted
		; Remove and replace with the number 2

The sequence and its effects on the stack are shown in Figure Ex11.14(a). The expression can be rewritten without parentheses as 9 5 2 + -.

We assume that the Top of Stack pointer is initialized to -1 at processor restart. This represents an empty stack. The TOS pointer is incremented before an item is added to the stack, and is decremented after an item is removed.

Instructions are encoded in one to three four-bit words. Arithmetic, logical, and shift instructions are encoded in a single word: all four bits form the op code. The operands are implicitly the elements on the top of the stack. The arithmetic/logical instructions are: ADD, SUB, AND, OR, COMP, INCR, RSR (rotating shift to the right), and ASR (arithmetic shift to the right), and their encodings are the following:

0000	ADD	Mem[TOS-1] := Mem[TOS-1] + Mem[TOS];
		TOS := TOS - 1;
0001	SUB	Mem[TOS-1] := Mem[TOS-1] - Mem[TOS];
		TOS := TOS - 1;
0010	AND	Mem[TOS-1] := Mem[TOS-1] AND Mem[TOS];
		TOS := TOS - 1;
0011	OR	Mem[TOS-1] := Mem[TOS-1] OR Mem[TOS];
		TOS := TOS - 1;
0100	COMP	Mem[TOS] := ~Mem[TOS];
0101	INCR	Mem[TOS] := Mem[TOS] + 1;
0110	RSR	Mem[TOS]<0> := Mem[TOS]<1>,
		Mem[TOS]<1> := Mem[TOS]<2>,
		Mem[TOS]<2> := Mem[TOS]<3>,
		Mem[TOS]<3> := Mem[TOS]<0>;
0111	ASR	Mem[TOS]<0> := Mem[TOS]<1>,
		Mem[TOS]<1> := Mem[TOS]<2>,
		Mem[TOS]<2> := Mem[TOS]<3>,
		Mem[TOS]<3> := Mem[TOS]<3>;

The next instruction group places data into the stack or removes data from the stack. The PUSHC instruction is encoded in two 4-bit words, one that contains the op code and one that contains 4-bit twos complement data to place on the top of the stack. PUSH and POP are three words long: one for the op code and two subsequent 4-bit words that when taken together contain an 8-bit address:

1000 X3X2X1X0	PUSHC data	TOS := TOS + 1; Mem[TOS] := X3X2X1X0;
1001 A7A6A5A4 A3A2A1A0	PUSH address	TOS := TOS + 1;
		Mem[TOS] := Mem[A7A6A5A4 A3A2A1A0];
1010 A7A6A5A4 A3A2A1A0	POP address	Mem[A7A6A5A4 A3A2A1A0] := Mem[TOS];
		TOS := TOS - 1;

The remaining instructions are conditional/unconditional branches and subroutine call and return. All but RTS (Return from Sub-routine) are encoded in three 4-bit words: one word for the op code and two words for the target address. The conditional branch instructions, BRZ and BRN, test the top of stack element for = 0 or < 0, respectively. If true, the PC is changed to the target address. In either case, the TOS element is left -undisturbed.

JSR (Jump to Subroutine) is a special instruction that is used to implement subroutines. The current value of the PC is placed on the stack and then the PC is changed to the -target address. Any values placed on the stack by the subroutine must be POPed before it returns. The RTS instruction restores the PC from the value saved on the stack. It is important to organize the processor state machine so that the PC always points to the next instruction to be fetched while executing the current -instruction.

1011 A7A6A5A4 A3A2A1A0	JSR address	TOS := TOS + 1;
		Mem[TOS] := PC; PC := A7A6A5A4 A3A2A1A0;
1100	RTS	PC:= Mem[TOS];
		TOS := TOS - 1;
1101 A7A6A5A4 A3A2A1A0	BRZ address	IF Mem[TOS] = 0
		THEN PC := A7A6A5A4 A3A2A1A0;
1110 A7A6A5A4 A3A2A1A0	BRN address	IF Mem[TOS] < 0
		THEN PC := A7A6A5A4 A3A2A1A0;
1111 A7A6A5A4 A3A2A1A0	JMP address	PC := A7A6A5A4 A3A2A1A0;

Figure Ex11.14(b) shows an initial data-path design for this -instruction set.

Extend this data-path with a Harvard architecture memory -interface.

What register transfer operations and microoperations are supported by this data-path?

How can the microoperations you found in part (b) be used to implement the execution portion for each of the 16 instructions of the instruction set?
15. (Processor Controller Design) Design a state diagram for the processor and instruction set described in Exercise 11.14. You can choose a Moore or Mealy design style.

Draw the modified state design. Identify in general terms what is happening in each state.

What microoperations should be associated with each state?

For each of the 16 instructions in the instruction set, describe the number of states required for its fetch and execution. You may assume that the memory system responds in a single processor cycle for the purposes of this calculation.

[Top] [Next] [Prev]

---

This file last updated on 07/16/96 at 04:05:25.
[e-mail];