### ex - okstate-ecen4243-plp-spring-2011

```Phase 1 Presentation
2/14/2011
Wisdom of the Day
 学而不思则罔，思而不学则殆
 Learning without thought is
useless; thought without learning is
perilous.
 Today we will encourage thoughts
while you learn about the execution
stage.
Confucius (551Bc-479BC) was
a Chinese thinker and social
philosopher whose teachings
and philosophy have deeply
influenced Chinese, Korean,
Japanese, and Vietnamese
thought and life.
Execution Engine Overview
 Responsible for producing the
result of almost every instruction
 Three design points:
 The ALU
 PC Manipulation
 Memory Accesses
Block Diagram
Execute Stage Block Diagram
THE ALU
POWERHOUSE OF THE CPU
ALU Overview
 The ALU is the main math unit of
the CPU
 It takes two inputs and then
returns the results of various
operations on them
ALU Datapath
ALU Operations
 Set Less Than Unsigned
 Subtract (SUBU)
(SLTU)
 Shift Logical Left (SLL)
 Shift Right Logical (SRL)
(LUI)
 Or (OR)
 And (AND)
 Nor (NOR)
 Set Less Than (SLT)
 Uses a ripple carry adder to
produce the sum
 Other options include a carry look
 We believe the ripple carry adder
is sufficiently fast for our
implementation.
C Code
return a+b;
}
Subtraction
 Modified existing adder to handle
 Subtraction is the addition of one
number and the 2s compliment of
a second number
 2s compliment: invert bits then

A-B = A + (B! + 1)
C Code
int SUBU(int a, int b){
return a-b;
}
Subtraction
and Subtract, we place a mux in
 Choice 1: signal unmodified
 Choice 2: inverted part of B

Then to add one we set the carry in
bit of the adder to high
C Code
SUBU(int a, int b){
return a-b;
}
Set Less Than
 On a set less than instruction, the
ALU determines if the first input is
less than the second.
 To implement, we subtract the two
operands and then determine if
the output is negative.
 The sign becomes the result.
 1 means it is less than.
 0 indcates that it is not.
C Code
boolean SLT(int a, int b){
return a<b;
}
Set Less Than Unsigned
 First, let's try using the exact same
logic as SLT:
 12<3?
 12-3<0?
 1100-0011 = 1100+1101 = 1001 = -7
 We have determined this won't
work.
 Ideas?
C Code
boolean SLTU(uint a, uint b){
return a<b;
}
Set Less Than Unsigned
 Let’s add an extra zero to make
them positive
 12<3?
 12-3<0?
 01100-00011 = 01100+11101 = 01001 = 9
 This does work.
 Sign bit is only the XOR of 0, 1 and
the last carry out bit.
 If you're savvy, you'll notice this is
simply the NOT of the carry-out
bit.
C Code
boolean SLTU(uint a, uint b){
return a<b;
}
Shifting
 The output bits choose their bit
based on the input shamt
 Implemented using MUXes.
 We made it faster by converting
shamt to one-hot encoding.
 Uses a bunch of and gates in
parallel
 Any ”leftover” bits are 0's.
C Code
uint SLL(uint a, int shamt){
return a<<shamt;
}
Logic Operations





AND
OR
NOR
In order to complete these
operations we use bitwise, AND,
OR, and NOR.
Uses 32 gates for each
operation.
C Code
int AND(int a, int b){
return a&b;
}
 Returns the value of the
immediate shifted left 16 times.
 Reusing SLL complicates the logic
of the ALU circuit.
 Uses a dedicated 16-shift left
module.
C Code
int LUI(int a){
return a<<16;
}
ALU Control
 How is the ALU controlled?
 How can we accomplish this?
 Alternative options?
ALU Control
 Nearly every operation is computer
in parallel
 When ADDU is performed, SUBU,
SLT and SLTU are not, and viceversa
 There is a MUX inside the ALU
 The MUX chooses the output
based on the requested operation
ALU Control
 One hot encoding
 SIG0 is for indicating the adder
must do subtraction.
Operation
Code
SIG0
000000001
0
SUB
000000001
1
OR
000000010
0
AND
000000100
0
NOR
000001000
0
SLT
000010000
1
SLTU
000100000
1
SLL
001000000
0
SRL
010000000
0
LUI
100000000
0
ALU Control
 Alternative Options
 Binary Encoding
 One Cold Encoding
 We use one hot to make the MUX
less complex
 Just as we did for the SLL and SRL
Immediates
immediates would be painstaking
and wasteful
 Determine second input from
outside the ALU
Immediate Datapath
PC Manipulation
PC Manipulation Overview
 Dynamic alteration of the PC
allows for programs to be nonlinear
 Greatly increases the capability of
computers
Branching
 Branch instructions modify the
program counter to skip over
sections of code or to go back to
repeat previous code.
 Our branches allow for conditional
movement to an offset.
Conditional Branch



BEQ: Branches when the values in
the two registers are equal
BNE: Branches when the values in
the two registers aren’t equal
Two things must be calculated:


Comparison
C Code
if(a == b) goto c; /* BEQ */
if(a != b) goto c; /* BNE */
Conditional Branch


The ALU can then do the
comparison

Extra output to determine if
subtraction results in a 0
C Code
if(a == b) goto c; /* BEQ */
if(a != b) goto c; /* BNE */
Branching Datapath
Jumping


Jumps unconditionally change the
PC
rather than offsets of the current
PC
C Code
goto c;
Jumps



Jump(J): jumps directly to the
instruction in the immediate field
Jump Register (JR): jumps to the
instruction whose location is the
value of the given register
C Code
goto c;
/* JR */
Jumping Datapath



Jump and Link(JAL): jumps to the
instruction in the immediate field
and saves the return address in \$ra
jumps to the instruction in the
immediate field and saves the
register
C Code
\$ra = PC+8;
of PC+8
 This is the instruction after the
delay slot instruction
 More MUXes on the ALU inputs to
C Code
\$ra = PC+8;
PC Change Determination
 PC will change on a successful
branch or a jump command
 Use and a combination of AND
gates and an OR gate
 Use JUMP? bit to choose the new
C Code
if(BEQ && !Not Zero || BNE &&
Not Zero || Jump){
}
MEMORY INTERFACING
Memory Interfacing Overview
 There are a limited number of
registers in the CPU
 To maintain and obtain more data,
we need to be able to access a
larger pool of data
 Loads some word into a register
from memory
 The address is determined by
adding an offset to the first
operand
 Easily implemented in the ALU
C Code
b = mem[a+0x000016]
Store Word
 Stores a register to memory
 We use the same method as load
C Code
mem[a+0x000016] = b
Memory Datapath
Conclusion
 Three design points:
 ALU
 PC Manipulation
 Memory Accesses
 Take advantage of repeated logic
 If all else fails, more hardware
Questions
Works Cited

















Confucius

Exeggutor

http://www.pokecommunity.com/signaturepics/sigpic136542_1.gif
Block Diagram

Doctor of Math

http://brownsharpie.courtneygibbons.org/?p=452
Flowchart

http://xkcd.com/210/
Bank Branch

http://media.glassdoor.com/m/7f/db/98/f9/a-typical-suntrust-bank-branch-this-one-located-at-4235-university-drive.jpg
Navy Seal

One Tree Hill

Van Halen

Paratroopers

Jumper

Jumping Spider

http://fc03.deviantart.net/fs23/f/2007/356/1/a/green_jumping_spider_closeup_by_troypiggo.jpg

http://farm1.static.flickr.com/145/329883185_6b80bde503.jpg
Battering Ram

http://4.bp.blogspot.com/_86fa3woQOHU/SwPiRaktsdI/AAAAAAAAA4c/pn35L4Ei7B8/s1600/BatteringRam.jpg
Tron Ram
