UART
Review For
Computer Organization Exam
Christopher Mar
Topics
Two’s Complement
Branch offset and jump target calculation
PLP/MIPS Datapath
Pipelining and Hazards
Two’s Complement Conversion
Flip all bits (bitwise NOT)
Add the value, 1
Lecture Question 1
If we know that 0b0101 is a signed 4-bit integer, is it a negative value?
Yes
No
Not enough information is given
Lecture Question 2
If we know that 0b1001 is a signed 4-bit integer, is it a negative value?
Yes
No
Not enough information is given
Lecture Question 3
How would 6 be represented as a signed 4-bit number?
0100
0101
0110
1010
1110
Lecture Question 4
How would -6 be represented as a signed 4-bit number?
0100
0101
0110
1010
1110
Jump Address Calculation
8
Jump Instruction Format
4 most significant bits and 2 least significant bits always the same
Use first 4 bits [31:28] of previous address
Truncate 2 least significant bits
CPU shifts address left two bits to restore 2 zeroes
opcode
immediate value
6 bits
26 bits
Lecture Question 5
If a jump instruction’s value is 0x08000321 and is located at the address, 0x10000044, then the address being jumped to is:
0x80000321
0x10000044
0x10000365
0x10000C84
0x10000CC8
Calculate Jump Address
000010
00 0000 0000 0000 0011 0010 0001
6 bits
26 bits
PC = PC[31:28] + (imm << 2) = 0x10000000 + (0x321 << 2) = 0x10000000 + (0xC84) = 0x10000C84 Branch Instruction Format Offset is the signed value Represents the number of instructions from the branch delay slot address to the label address 2 least significant bits of the offset are truncated just as they are for the jump opcode rs 6 bits 5 bits rt 5 bits offset 16 bits Lecture Question 6 If a branch instruction’s value is 0x12118000 and the instruction is located at the address, 0x10100000, then the target branch address is: 0x10108000 0x10108004 0x100E0004 0x100F0000 0x100F8004 Solution in following slides Calculate Branch Offset Instruction value: 0x12118000 (at 0x10100000) Offset: 0x8000 This value is negative (MSB is 1) so I recommend converting to its absolute value 0b1000 0000 0000 0000 0b0111 1111 1111 1111 (flip bits) 0b1000 0000 0000 0000 (add 1) = -0x8000 000100 10000 opcode rs 10001 rt 1000 0000 0000 00000 offset Calculate Branch Offset CPU shifts offset value left 2 bits for address offset Address offset: -0x20000 ( = -0x8000 << 2) Offset added to branch delay slot, which is branch instruction address + 4 ( = 0x10100000 + 4 = 0x10100004) Branch target address = (Branch Delay Addr.) + (Addr. Offset) = 0x10100004 -0x20000 = 0x100E0004 000100 10000 opcode rs 10001 rt 1000 0000 0000 00000 offset PLP/MIPS Datapath 16 Datapath Trace: subu $s5, $t1, $t3 26 opcode subu $s5, $t1, $t3 $t1 $t3 Function Field rs 6 bits 5 bits rt 5 bits opcode rd 5 bits shamt 5 bits 6 bits funct $s5 100010 Instruction separated into the 4 fields shown at the top right of the slide opcode subu $s5, $t1, $t3 $t1 $t3 $s5 Function Field RegDst selects second register as write destination opcode off subu $s5, $t1, $t3 $t1 $t3 $s5 Function Field Branch control signal is off so result of AND gate will be off. This causes the MUX to select the “PC + 4” input (the next instruction). opcode off subu $s5, $t1, $t3 $t1 $t3 $s5 Function Field The jump signal selects “PC + 4” from the previous MUX’s output. opcode x off subu $s5, $t1, $t3 $t1 $t3 $s5 Function Field The addiu instruction doesn’t read from memory, but the value written back to the register comes from the ALU so the value of the MemRead control signal doesn’t matter. opcode x off subu $s5, $t1, $t3 $t1 $t3 $s5 Function Field The value written back to register file comes from the ALU so the MemToReg is off. opcode x 10 off 0110 subu $s5, $t1, $t3 $t1 $t3 $s5 Function Field The ALU is used so ALUOp is on. opcode x 10 off off 0110 subu $s5, $t1, $t3 $t1 $t3 $s5 Function Field The addiu instruction doesn’t write to memory so the MemWrite control signal is off. opcode x 10 off off 0110 subu $s5, $t1, $t3 $t1 $t3 $s5 Function Field The second ALU input comes from the 16-bit immediate field so the ALUSrc control signal is on. opcode x 10 off On off 0110 subu $s5, $t1, $t3 $t1 $t3 $s5 Function Field The addiu instruction writes a result back to the register file so the RegWrite control signal is on. Pipelining 37 IF ID EX MEM WB Single cycle PLP/MIPS datapath with pipeline stage labels superimposed on top (approximately) Lecture Question 7 Pipelining is a form of __________ used to increase __________. Caching, Latency Caching, Throughput Parallelism, Latency Parallelism, Throughput None of the above Pipelining Parallelism Increases throughput (number of instructions processed per unit of time) As opposed to latency (time to complete one instruction) Pipelining Break up datapath into sequential pieces of instruction handling (pipeline stages) One instruction in each stage simultaneously (in parallel) Pipelining Hazards 42 Lecture Question 8 If a processor contains a single ALU and it is needed in both the IF and EX stages, this will most likely result in a: Structural hazard Data hazard Control hazard Lecture Question 9 Data hazards are typically resolved with… Branch prediction Forwarding Resource duplication Reversing Data prediction Lecture Question 10 Branches in a pipelined processor typically cause… Structural hazard Data hazard Control hazard Pipelining Hazards Structural Insufficient hardware resources Data Instruction depends on result of instruction that is still in the pipeline Control Branch resolution unknown when fetching next instruction Q & A 47