Welcome to Computer Organization and Assembly!
The PC and Interconnect
CS/COE 0447
Jarrett Billingsley
1
Class announcements
lab 7 is out!
OMETs are out!
will they have any effect?
WHO KNOWWWWWWWS!!!!!!!
CS447
2
2
Machine code and Control
CS447
3
Why is machine code
text is human-oriented and informationally… sparse.
instead, we encode each instruction as a bitfield.
this encoding is specified by the ISA.
CS447
4
31 26 25 21 20 16 15 0
opcode rs rt immediate
31 26 25 21 20 16 15 11 10 6 5 0
opcode rs rt rd shamt funct
31 26 25 0
opcode target
R
I
J
the opcode (and funct) field identifies which instruction it is.
add rd,rs,rt
beq rs,rt,offset
jal target
MIPS has three instruction formats, all 32 bits (4 bytes).
sll rd,rs,shamt
– even if each letter is only 1 byte, each textual instruction would be huge.
– every ISA has its own format(s).
– so you don’t need to memorize these formats…
– christ why do they teach this. it’s useless.
4
How does it… do the thing?
to put it very simply…
CS447
5
31 26 25 21 20 16 15 11 10 6 5 0
000000 01001 01010 01000 00000 100000
add t0, t1, t2
Register File
WE
rd
rs
rt
ALU
gets encoded as…
“add”
1
the fields are used as the control signals to the CPU’s components.
5
The control
to put it less simply, the control’s job is to decode the instruction, and set all the control signals to make that instruction happen.
CS447
6
31 26 25 21 20 16 15 11 10 6 5 0
000000 01001 01010 01000 00000 100000
Register File
ALU
Data Memory
Control
today, we’re assuming that the control has already done its job, so we have a bunch of control signals to work with.
next time we’ll actually look at how it works.
– Powerpoint just Did That with the arrow from Control to ALU and it’s magical so I’m gonna leave it like that
– spoiler alert: the control in a single-cycle machine is just a really big boolean function!
6
The PC
CS447
7
What’s the next instruction?
what order do these instructions run?
CS447
8
li s0, 0
top:
move a0, s0
jal print_int
addi s0, s0, 1
blt s0, 5, top
li v0, 10
syscall
print_int:
li v0, 1
syscall
jr ra
most instructions change the PC to the next address
control flow instructions can change the PC to a constant…
…or the value from a register…
…or one of two choices, conditionally
Maybe you never noticed…
the control flow instructions are divided into two groups.
CS447
9
jumps make execution go to one specific place.
branches make execution go to one of two places.
j end
bne s1, t0, top
but.. why?
well, notice the operands of each.
– jumps include j, jal, jr. they uh, all start with j.
9
A matter of practicality
each jump or branch has a target: where it goes to
we’d like to be able to encode any target address…
but we have a fixed number of bits to encode our instructions.
CS447
10
think about the cases where jumps are used.
now think about the cases where branches are used.
some_function()
return;
while(true) {}
if(…) {}
while(…) {}
for(…) {}
how far away is a branch target likely to be?
how far away is a jump target likely to be?
– remember: every MIPS instruction must fit into 32 bits!
– jump targets might be far, far away – functions can be anywhere in the assembled program.
– branch targets are often very nearby – only a few dozen instructions away.
10
Absolute versus Relative
we say that MIPS jumps are absolute and branches are relative.
CS447
11
_top:
move a0, s0
jal print_int
add s0, s0, 1
blt s0, 5, _top
…
jumps just set the PC to a new value.
branches either add an offset to the PC or do nothing.
PC = 0x800400B0
PC += (-16)
jumps need a long address, but branches only need a small offset. so we can fit them into J and I instructions!
– USUALLY jumps need long addresses and branches only need a small offset.
– but we can get around those limitations in the rare cases when they don’t fit.
– the details of how the addresses/offsets are stuffed into the MIPS instructions are a little tedious
– read the book if you’re curious
11
Correlation, not causation
branches don’t have to be conditional…
and you can have conditional jumps.
CS447
12
Unconditional Conditional
Jumps j, jal, jr
Branches beq, bne, bgt, etc…
it’s just that in MIPS, those categories happen to be empty.
well there is a b pseudoinstruction which is like beq zero, zero, lab so it’s unconditional
– the term “jump” means “absolute” and “branch” means “relative.”
– in x86 for example you have relative (near) and absolute (far) jumps, which can be either conditional or unconditional.
– x86 just has a little of everything.
12
Position-independent code (animated)
relative branches have a nice advantage over absolute jumps:
they will work no matter what address the code is located at.
CS447
13
non-PIC
8000
9000
A000
B000
C000
D000
E000
F000
PIC
8000
9000
A000
B000
C000
D000
E000
F000
if we use absolute jumps, the code must be located at a specific address to work right.
if we only use relative branches, it will work at any address.
– note in the non-PIC example, the destinations of the absolute jumps stayed the same, even though the code moved.
– because “j 0x8000” will always go to 0x8000, no matter where the jump instruction is
– PIC would be a good use for those unconditional branches.
13
The PC FSM
CS447
14
Countin’ programs
the PC is its own little FSM within the CPU.
CS447
15
PC
logic!
inputs: regular instruction? jump? branch? jump target? branch offset?
output: the address of the instruction to execute
next PC
it’s not too complicated. let’s build it.
– “huh… could we make the PC FSM more complex? like, make it a whole CPU inside the CPU?” yes. wait for microcode
15
These boots are made for walking
moving ahead by 1 instruction after each cycle is easy enough.
CS447
16
4
+
the PC is a 32-bit register.
to make it move forward by one instruction, we…
okay. now we can run steps in order. but what about jumps?
PC
– addresses are measured in bytes, and each instruction is 4 bytes.
16
Jump
And that’s just what they’ll do
jumps (j, jal, jr) put a value (the jump target) into the PC
well now we have two choices of where to go after each instruction.
how do we choose?
CS447
17
4
+
PC
jump target
Jump is a control signal. many control signals are just MUX selectors.
normal instructions set Jump = 0. jumps set Jump = 1.
– remember the MUXes in the register file and ALU? those were more control signals…
– of course, there are two places that target can come from, so we’d need another mux for that…
– j and jal have the target inside the instruction; jr copies from a GPR into PC
– but maybe that is handled outside the PC FSM, in the INTERCONNECT!
17
Relative branches
think about a number line.
CS447
18
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
you are here
if you want to get here, what do you have to add to 10?
how about here?
what’s the formula?
offset = destination – here
(this applies in any number of dimensions, btw)
– you add -6 to get to 4; you add 2 to get to 12
– (where you want to be) – (where you are)
– e.g. if you have two points in 3D, you can get the vector that points from source to destination by doing (destination – source)
18
Jump
One of these days these boots are gonna… choose where to walk
branches add an offset to the PC.
wait, we’re doing that already… let’s reuse that adder.
CS447
19
4
+
PC
jump target
when you have muxes after muxes, it’s like an if-else if.
Branch
branch offset
if(Jump) PC = target
else if(Branch) PC += offset
else PC += 4
– btw, if(thing) is like if(thing == true).
– Java is super picky about booleans in conditions…
– but most languages let you write if(thing) where thing is not a boolean. 0 is false, non-0 is true.
19
How do we know whether to branch?
well.. let’s punt that question to the control.
a good technique is to keep each part of a circuit as simple and dumb as possible.
(this applies to functions in programming too.)
the control is what actually decides what these control signals will be.
CS447
20
The Interconnect
CS447
21
Gotta keep em separated interconnected
we’ve got pieces of a CPU, but they don’t operate in isolation
we gotta hook em together. but which parts hook to which?
the instructions in the ISA tell you what has to connect to what.
CS447
22
Instruction Memory
PC FSM
Register File
ALU
Data Memory
22
Slowly coming together
if we look at all the different instructions we want to support, we’ll start to get an idea of what data goes where
CS447
23
Register File
ALU
t0
t1
v0
–
Data Memory
Register File
ALU
s0
t3
+
4
Data
Address
sub v0, t0, t1
sw s0, 4(t3)
Register File
PC FSM
PC+4
address of
move_ball
jal move_ball
how do we make all these different things happen with one set of hardware…?
– lots of CHOOSING going on, huh…
23
PC to the left of me, ALU to the right, here I am
the interconnect lets the CPU parts combine in many ways
it’s like the CPU’s “circulatory system” – it moves data around
think about which instructions move data between which parts…
CS447
24
Register File
ALU
Data Memory
Instruction Memory
add, sub, etc.
stores
loads
PC
jr
li? (immediate)
addi, ori, lw, sw, etc. (immediate)
jal
it’s starting to take shape…
beq, j
lw/sw
(address)
– li is actually a pseudoinstruction in MIPS, cause you can implement it by doing e.g. zero + immediate. (or lui+ori for bigger numbers)
– but we can implement it however we want.
– addi/ori etc. are the “immediate” versions of add/or etc.
– in these, the second operand comes from the instruction, instead of from a register.
24
Conjunction junction
the interconnect makes choices about which things go where
CS447
25
Register File
data loaded from memory
ALU results
instruction immediates
PC+4 (for jal)
RegDataSrc
2
so how do we choooooose which thing to write?
now we have a select. this is another control signal!
every MUX in the interconnect needs a control signal.
the book calls this “MemToReg” which is a terrible name and is inconsistent with the rest of the control signal names
only one of these is written to the register file
– ALU instructions would set RegDataSrc to 0.
– loads set it to 1.
– li sets it to 2.
– jal sets it to 3.
– alternatively, you could have an “if-else if-” chain of 3 muxes, if that makes it easier to think about. (a multi-input mux is really just a bunch of two-input muxes after all.)
25
A technique: an interconnect matrix (animated)
you can make a table to keep track of what things connect to what.
CS447
26
ALU A ALU B PC Regs DM Data
ALU
PC+4
Regs
IM
DM
…to here?
Does the data flow from here…
now consider all the instructions your CPU should support, and mark the cells accordingly.
lw
add, sub, and, or
beq
j
sw
any component (column) with multiple things coming into it will need a MUX.
√
jal
li?
√?
jr
addi, subi…
√
√
√
√
√
√
√
√
– idk if this is a thing they do “in the real world” but it’s worked for me!
26
Interconnected (MIPS, not your project)
if we want to make a suuuuper simple version of MIPS, we can connect the pieces together like this:
CS447
27
Register File
imm field
ALU
MemWrite
ALUSrc
ALUOp
rd
RegWrite
RegDataSrc
rs
rt
Data Memory
Data
Address
(this version doesn’t support jal and li, but that’s fiiiine)
but now we need to, uh, control the control signals.
how can we use this to implement add? sub? addi? lw? sw?
– add and sub would turn on RegWrite; set RegDataSrc to use the ALU output; set ALUSrc to use the register; and set ALUOp appropriately.
– addi would do almost the same, except set ALUSrc to use the immediate.
– lw would set ALUSrc to immediate; ALUOp to add; set RegDataSrc to memory; and turn on RegWrite.
– sw would be kinda like lw, but turn on MemWrite instead of RegWrite.
27
/docProps/thumbnail.jpeg