Read register 1

Read register 2

Write register

Write data

Registers ALU Zero

Read data 1

Read data 2

Sign extend

16 32

Instruction [31–26]

Instruction [25–21]

Instruction [20–16]

Instruction [15–0]

ALU result

M u x

M u x

Shift left 2

Shift left 2

Instruction register

PC 0

1

M u x

0

1

M u x

0

1

M u x

0

1 A

B 0 1 2 3

M u x

0

1

2

ALUOut

Instruction [15–0]

Memory data

register

Address

Write data

Memory MemData

4

Instruction [15–11]

PCWriteCond

PCWrite

IorD

MemRead

MemWrite

MemtoReg

IRWrite

PCSource

ALUOp

ALUSrcB

ALUSrcA

RegWrite

RegDst

26 28

Outputs

Control

Op [5–0]

ALU control

PC [31–28]

Instruction [25-0]

Instruction [5–0]

Jump address [31–0]

Control

Hazard detection

unit

+

4

PC Instruction

memory

Sign- extend

Registers =

+

Fowarding unit

ALU

ID/EX

MEM/WB

EX/MEM

WB

M

EX

Shift left 2

IF.Flush

IF/ID

M u x

M u x

Data memory

WB

WBM

0

M u x

M u x

M u x

M u x

WB

M

EX

WB

M WB

M em

W rit

e

PCSrc

M em

to R

eg MemRead

Add

Address

Instruction memory

Read register 1

Read register 2

Instruction [15–0]

Instruction [20–16]

Instruction [15–11]

Write register Write data

Read data 1

Read data 2

Registers Address

Write data

Read data

Data memory

Add Add result

ALU ALU result

Zero

Shift left 2

Sign- extend

PC

4

ID/EX

IF/ID

EX/MEM

MEM/WB

16 632 ALU control

RegDst

ALUOp

ALUSrc

R eg

W rit

e

In st

ru ct

io n

Branch

Control

0 M u x

1

0 M u x

M u x

M u x

1

1

0

0

1

MemRead ALUSrcA = 0

IorD = 0 IRWrite

ALUSrcB = 01 ALUOp = 00

PCWrite PCSource = 00

ALUSrcA = 0 ALUSrcB = 11 ALUOp = 00

ALUSrcA = 1 ALUSrcB = 00 ALUOp = 10

ALUSrcA = 1 ALUSrcB = 10 ALUOp = 00

MemRead IorD = 1

MemWrite IorD = 1

RegDst = 1 RegWrite

MemtoReg = 0

RegDst = 0 RegWrite

MemtoReg = 1

PCWrite PCSource = 10

ALUSrcA = 1 ALUSrcB = 00 ALUOp = 01

PCWriteCond PCSource = 01

Instruction decode/ register fetch

Instruction fetch

0 1

Start

(Op =

'LW ') o

r (O p =

'SW ')

(O p

= R-

typ e)

(O p

= 'B

E Q

')

(O p

= 'J

')

Jump completion

9862

3

4

5 7

Memory read completon step

R-type completion Memory access

Memory access

Execution Branch

completion Memory address

computation

(Op = 'SW ')

(O p

= 'L

W ')

Name:

0 M (2) Consider the MIPS implementation shown in Figure 4.65 (page 325) of the textbook. Assume thatthis implementation is modified by adding to it the ALUSrc MUX, as shown in Figure 4.57 (page

312). Furthermore, this implementation includes the logic described in Slide 7.54. The frequency of the clock signal in this implementation is 400 MHz. The workload executed on this processor requires executing 200,000,000,000 instructions. In this workload, 45% of the instructions are R-type, 22% are lw, 13% are sw, and 20% are beq. For 33% of the R-type instructions one of the operands is the output of the immediately preceding instruction, which is also an R-type instruction. For 28% of the lw instructions, the instruction that immediately follows the lw is an R-type instruction where one of the operands is the result of the lw instruction. Specify the execution time, in seconds, of the workload.

Answer: seconds Show how you derived the answer above. The derivation must start from basic principles. This requires showing and explaining every step.

Do not write anything in this space or below

2

Name:

a (3) Consider the MIPS implementation shown in Figure 4.51 (page 304) of the textbook. On this implementation, without any modifications, the following program is executed. Note that the labels il, i2, etc, are not part of the program but you can use them to refer to specific instructions in your explanation.

il a d d $ 4 , $ 2 , $ 2 i2 a n d $ 2 , $ 2 , $ 1 i3 s u b $ 5 , $ 2 , $ 7 i4 b e q $ 5 , $ 4 , 0 i5 a d d $ 1 , $ 1 , $ 7 i6 a d d $ 5 , $ 6 , $ 3 i7 s u b $ 4 , $ 4 , $ 3 i8 a d d $ 3 , $ 3 , $ 6 i9 o r $ 0 , $ 6 , $ 3 iJO a n d $ 0 , $ 3 , $ 2 ill a d d $ 0 , $ 5 , $ 5 il2 a d d $ 0 , $ 5 , $ 5 il3 a d d $ 0 , $ 5 , $ 5 il4 a d d $ 0 , $ 5 , $ 5

The second column of the following table provides the values in registers $0 through $7 before the execution of this program. Your task is to provide the "final" values in all those registers, defined as the values four cycles after instruction ilO is fetched.

register initial value final value $0 0 $1 7 $2 12 $3 2 $4 22 $5 24 $6 43 $7 3

Explain your answer. Your explanation must include the impact, if any, of the b e q instruction in this program.

Do not write anything in this space or below

3

N a m e :

a (4) Consider the multicycle MIPS implementation shown in Figures 5.28 and 5.37 of Chap 5, 3 r d E d (pages 323 and 338, slides 5.21 and 5.32). Assume that, in every cycle when a particular control sig n al is logically a don't care, it is actually set to 0. Due to a hardware fault (malfunction), the least-significant bit of ALUSrcB is always one (stuck-at-I). Except for this specific effect, the circuit operates normally. A) Specify i n full detail what will be the consequences of this fault when the processor executes

programs - how will it change the behavior of the processor as observed by a user/programmer who does not know and does not care how the processor is implemented internally? Be sure to clearly identify each and every consequence of this fault with as much detail and specificity as possible.

B) Explain your answer to Part A based on the effect of the fault on the operation of the implementation.

4

Name:

@) ( 5 ) It is, of course, possible to write a program that writes to memory machine instructions that it then executes. Such a program is referred to as self-modifying code. Consider the MIPS implementation shown in Figure 4.65 (page 325) of the textbook. Assume that this implementation is modified by adding to it the ALUSrc MUX, as shown in Figure 4.57 (page 312). Furthermore, this implementation includes the logic described in Slide 7.54. A) The specified implementation is capable of executing self-modifying code. Briefly explain how

this can be done.

B) With the specified implementation, self-modifying code may not always execute correctly. Explain in detail under what conditions self-modifying code may be executed incorrectly. Your explanation must provide as much detail and specificity as possible.

C) Provide a high-level explanation of how the specified implementation must be changed in order to ensure that self-modifying code is always executed correctly.

D) Provide details for how the idea described in Part C can be implemented. Your answer must be in the form of an itemized list, where each item is labeled with a Roman numeral: I) specify any new logic modules (e.g., ALUs, adders, comparators, MUXes, registers) that are needed; II) specify any required modifications to existing modules; III) specify, in detail, how each of the new and/or modified modules are connected and used.

5

Name:

0 (6) Consider the table on Slide 6.16 in the class notes.A) Explain how the compiler can affect the CPI.

B) Explain how the ISA can affect the instruction count.

C) Explain how the organization can affect the clock rate.

Q . , (7) Consider the multicycle implementation shown in Figure 5.28, page 323, and Figure 5.37, page 338, of Chap 5, 3rd Ed (slides 5.21 and 5.32). During manufacturing, the O input of the PCSource MUX was left disconnected. Unfortunately, it is no longer possible to change the datapath in any way. Fortunately, you can save the day by changing the control unit so that the processor will still execute programs correctly. All you have to do is change the state machine. A) Explain the basic idea of your modifications in 2-4 clear sentences.

B) On the next page is the original state diagram of the control unit. Modify this state diagram to show the required changes. You must make only the minimal changes necessary for correct operation. Any new nodes or edges drawn and any new text written must be in red. Remember that you can erase whatever you want by placing a borderless white shape over it. Note that, with LibreOffice, it is very easy to change the color of text and various objects. (If necessary, you are permitted to use Google to search of help on how to change colors with LibreOffice ).

C) Do your changes affect performance in any way? Your answer must be yes or no.

Answer: _ _ _ _ _ _ Explain your answer in detail.

6

Name:

Memory read completon step

0

Instruction fetch

MemRead ALUSrcA = 0

lorD = 0 IRWrite

ALUSrcB = 01 ALUOp = 00

PCWrite

7

Instruction decode/ register fetch

Jump completion