Processor Design: Important Example Solved Problems

Example: 1

Generate the logic circuit for the following function

End = T7 .ADD +T5 BR + (T5 . N + T4 . ) BRN + ….

Solution:

Fig. 3.5.5 shows the circuit that generates the End control signal from the logic function.

End = T7 . ADD + T5 . BR + (T5 . N + T4) . BRN + ......

Microprogrammed Control

Example: 1

Write a combined micro routine that can implement that BGT (Branch if > 0), BPL (Branch if plus) and BR (Branch Unconditionally) instructions. The branch conditions. for the BGT and BPL instructions are Z + (N XOR V) = 0 and N = 0, respectively. What is the total number of micro instructions required? How many micro instructions are needed if a separate micro routine is used for each machine instruction?

Solution:

For bus organisation, we write microroutine for the implementation of BGT (Branch if > 0), BPL (Branch if plus) and BR (Branch unconditionally) instructions as follows.

Combine Microroutine

• The first three microinstructions in the combine microroutine are used to fetch the opcode. The total number of microinstructions required are 11. If a separate microroutine is used for el each machine instruction 17 microinstructions are needed.

Example: 2

For a single bus organisation of CPU, write a microprogram for instruction. Add (Rsrc) +,R dst.

Solution:

Let us examine the path needed for the flowchart in 3.6.5 to execute the instruction Add(Rsrc)+, Rdst

In this instruction the source operand is accessed in the autoincrement mode and the Rsrc and Rast are general purpose registers in the processor. We assume that the processor has 16 registers that can be used for addressing purpose, each specified using a 4‒bit code. We also assume that the instruction has a 3‒bit field, (bits 8‒10) used to specify the addressing mode for the source operand, as shown in Fig. 3.6.6. Bit patterns 11,10,01 and 00 located in bits 10 and 9 denote the indexed, auto decrement, autoincrement and register modes respectively. For each of these modes bit‒8 is used to specify the indirect version. For example, 100 in the mode field specifies the direct version of the autodecrement mode, whereas 101 specifies the indirect version.

As a part of execution, first the opcode and mode fields are decoded to determine that an Rsrc or Rdst register is involved. The decoded output is then used to gate the contents of the Rsrc or Rdst fields in the IR into a second decoder, which produces the gating signals for the actual registers R0 to R15.

The flowchart of a microprogram for the ADD Rsrc, Rdst instruction in Fig. 3.6.5 is drawn by combining the microroutines for all possible values of the mode field, resulting in a structure that requires many branch points. The instruction Add (Rsrc)+, Rdst requires two branch microinstructions. In each branch microinstruction, the expression in brackets indicates the branch address that is to be loaded into the upc and how this address is modified using the bit‒ORing scheme. For example, the branch instruction at location 123 modifies the branch address 170 to 171 by ORing the bit‒8 in the IR with bit pc0 to change the addressing mode from indirect to direct, as shown in Fig. 3.6.7.

The address for branch microinstruction at location 003 is generated as shown in Fig. 3.6.8.

Table 3.6.2 gives the microinstruction sequence for the execution of Add (Rsrc)+, Rdst instruction.

Example: 3

For a single bus organisation of data paths inside the CPU, write a microprogram of micro‒instructions and draw chart of a microprogram for the following instruction.MOV (Rsrc)+, Rdst

Rast uses direct and autoincrement addressing.

Solution: Flowchart

Basic Concepts of Pipelining

Example: 1

 Explain the function of a six segment pipeline and draw a space diagram for a six segment pipeline showing the time it takes to process eight tasks.

Solution: Six stages in the pipeline :

1) Fetch Instruction (FI) : Read the next expected instruction into a buffer.

2) Decode Instruction (DI) : Determine the opcode and the operand specifiers.

3) Calculate Operands (CO) : Calculate the effective address of each source operand.

4) Fetch Operands (FO) : Fetch each operand from memory.

5) Execute Instruction (EI) : Perform the indicated operation and store the result, if any in the specified destination operand location.

6) Write Operand (WO) : Store the result in memory.

Example: 2

What is the ideal speed‒up expected in a pipelined architecture with 'n' stages? Justify your answer.

Solution:

The pipelined processor ideally completes the processing of one instruction in each clock cycle, which means that the rate of instruction processing with n stage pipeline is n times that of sequential operation. Therefore, ideal speed‒up factor is n. However, such ideal performance of the pipeline is achieved only when pipeline stages must complete their processing tasks for a given instruction in the time allotted. Unfortunately, this is not the case; pipeline operations could not sustained without interruption throughout the program execution.

Handling Data Hazards

Example: 1

Convert the following code segment in C to MIPS instructions, assuming all variables are in memory and are addressable as offsets from $t0 :

a = b+e ;

c = b+f ;

Solution :

lw $t1, 0($t0)

lw $t2, 4($t0)

add $t3, $t1,$t2

sw $t3, 12($t0)

lw $t4, 8($t0)

add $t5, $t1,$t4

sw $t5, 16($t0)

Example: 2

Find the hazards in the code segment of the previous example and reorder the instructions to avoid any pipeline stalls.

Solution:

Both add instructions have a hazard because of their respective dependence on the immediately preceding lw instruction. It is important to note that bypassing eliminates several other potential hazards, including the dependence of the first add on the first lw and any hazards for store instructions. Moving up the third lw instruction to become the third instruction eliminates both hazards:

lw $t1, 0($t0)

lw $t2, 4($t0)

lw $t4, 8($t0)

add $t3, $t1,$t2

sw $t3, 12($t0)

add $t5, $t1,$t4

sw $t5, 16($t0)