[SOLVED] CSE 141L: Introduction to Computer Architecture Lab

PolyPoint and the First Steps Towards Ubiquitous Localization

CSE 141L: Introduction to Computer Architecture Lab
Microprocessor Architecture & ISAs

Copyright By Assignmentchef assignmentchef

Pat Pannuto, UC SanSE 141L
CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others

Logistics Update: Waitlists
This is a big, hard project class
You now have the full scope of the big, hard project

If you are considering dropping this course, please do so ASAP
Please do not wait until the deadline [Friday!]

If you are far back on the waitlist for 141, then please make room in 141L
141 will be offered next quarter
(Im teaching it)

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
Logistics Updates
Project spec released for the quarter
Skim the whole document
Read the all the requirements
Read Milestone 1 in depth
Read the all the requirements again
Focus on the programs to start what must your processor do?
Milestone 1 is due in 16 days
Viva la Zoom
Full remote through Jan 31 at least
Remote participation will always be an option for 141L this quarter

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
Logistics Advice
Use Version Control
This is how your group should share across machines
Shouldnt matter if you use Questa/ModelSim locally, CloudLabs, etc

Good feedback from folks using VSCode to edit & manage code
Especially as it has built-in git support

Please no public repositories!

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
ISA Design and Processor Architecture are Interrelated
Your ISA expresses what your processor can do
So your architecture has to be able to do it!

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
The Instruction Set Architecture
that part of the architecture that is visible to the programmer
available instructions (opcodes)
number and types of registers
instruction formats
storage access, addressing modes
exceptional conditions
How do each of these affect your ISA design?

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
Note: visible to programmer includes by extension all the tools used by the programmer (i.e. toolchains)

Key questions to ask when designing an ISA
operations
which ones?
how to specify?
instruction format
how many formats?

source operands
destination operand

how does the computer know what
0001 0101 0001 0010 means?
Syntax choiceDesign choice
add r5, r1, r2add r5, r1 r4
add [r1, r2], r5
add r5, r1, r2

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
I use the canonical instruction to introduce all the things we need to think about in ISA design.

Instruction Formats: What does each bit mean?
Having many different instruction formats
complicates decoding
uses more instruction bits (to specify the format)
Could allow us to take full advantage of a variable-length ISA not in 141L!

VAX 11 instruction format
Serial decoding

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others

The MIPS Instruction Format
the opcode tells the machine which format

Register R-type
Immediate I-type
Jump J-type

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
Key point: The opcode field is the same in all encodings

Example of instruction encoding:

opcode=0, rs=1, rt=2, rd=5, sa=0, funct=32
00000000001 00010 00101 00000 100000

00000000001000100010100000100000
0x00222420

Register R-type
Immediate I-type
Jump J-type
add r5, r1, r2

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
TALK ABOUT FIELD NAMES AND WHY `rt` IS CONFUSING

rs = source
rt = 2nd source (letter after s?) [arguably also target, but like, not really because its read from not written to]
rd = destination
sa = shift amount
funct = sub-function

Rs = source
Rt = target Its read from for branches, but written to for others!

Accessing the Operands
aka, whats allowed to go here
operands are generally in one of two places:
registers (32 options)
memory (232 locations)
registers are
easy to specify
close to the processor (fast access)
the idea that we want to use registers whenever possible led to load-store architectures.
normal arithmetic instructions only access registers
only access memory with explicit loads and stores
add r5, r1, r2

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
Ask class where 32 regs comes from

Poll Q: Accessing the Operands
Faster accessFewer bits to specifyMore locations
AMemMemReg
BMemRegMem
CRegMemReg
DRegRegMem
ENone of the above

There are typically two locations for operands: registers (internal storage $t0, $a0) and memory.In each column we have which (reg or mem) is better.
Which row is correct?
Explain each but then point out how this leads to load/store

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
Reg faster (C, D)
Reg fewer (B, D)
Mem more locations (B, D)

Q: How does all of this align with the project restrictions?
[After class], re-read the restrictions with these slides in mind
Design Question you must answer:
How will your ISA encode operations and operands?
And how will that impact how your machine operates?

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
r6, r7, r8,
How Many Operands?
aka how many of these?
Most instructions have three operands (e.g., z = x + y).
Well-known ISAs specify 0-3 (explicit) operands per instruction.
Operands can be specified implicitly or explicity.
add r5, r1, r2

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others

Historically, many classes of ISAs have been explored, and trade off compactness, performance, and complexity
Style# OperandsExampleOperation

Stack0addtos(N-1) tos(N) + tos(N-1)

Accumulator1add Aacc acc + mem[A]

General Purpose3add A B Rcmem[A] mem[B] + Rc
Register 2add A Rcmem[A] mem[A] + Rc

Load/Store:3add Ra Rb RcRa Rb + Rc
load Ra RbRa mem[Rb]
store Ra Amem[A] Ra

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
Expressiveness
Efficiency (runtime; size)
Programmer/compiler machine model

Comparing the Number of Instructions

Code sequence for C = A + B for four classes of instruction sets:
Accumulator
GP Register
GP Register
(register-memory)
(load-store)

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others

Comparing the Number of Instructions

Code sequence for C = A + B for four classes of instruction sets:
Accumulator
GP Register
GP Register
(register-memory)
(load-store)

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others

Comparing the Number of Instructions

Code sequence for C = A + B for four classes of instruction sets:
Accumulator
GP Register
GP Register
(register-memory)
(load-store)

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others

Comparing the Number of Instructions

Code sequence for C = A + B for four classes of instruction sets:
Accumulator
GP Register
GP Register
(register-memory)
(load-store)
ADD C, A, B

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others

Comparing the Number of Instructions

Code sequence for C = A + B for four classes of instruction sets:
Accumulator
GP Register
GP Register
(register-memory)
(load-store)
ADD C, A, B
LoadR1,A
LoadR2,B
Add R3,R1,R2
Store C,R3

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
Note: Code != cycle!!

A = X*Y B*C
Stack ArchitectureAccumulator GPRGPR (Load-store)

Accumulator

Exercise: Working through alternative ISAs

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others

Example: load-store (aka register-register) ISA
load words from memory to reg file
operate in reg file
store results into memory from reg file

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
Instruction Set Architecture

Before Register and Memory

add r1, r2, r3

(add r1, r2, r3)
(lw r2, 1(r0))
(sw r3, 0(r0))
(beq r0, r1, 2)
After Register and Memory

(add r1, r2, r3)
(lw r2, 1(r0))
(sw r3, 0(r0))
(beq r0, r1, 2)
Assumptions
8 bit ISA
# of registers = 4 + PC (Program Counter)
Memory size = 64B

Instruction Set Architecture
Before Register and Memory

lw r2, 1(r0)
After Register and Memory

(add r1, r2, r3)
(lw r2, 1(r0))
(sw r3, 0(r0))
(beq r0, r1, 2)

(add r1, r2, r3)
(lw r2, 1(r0))
(sw r3, 0(r0))
(beq r0, r1, 2)
Assumptions
8 bit ISA
# of registers = 4 + PC (Program Counter)
Memory size = 64B

Instruction Set Architecture
Before Register and Memory

sw r3, 0(r0)
After Register and Memory

(add r1, r2, r3)
(lw r2, 1(r0))
(sw r3, 0(r0))
(beq r0, r1, 2)

(add r1, r2, r3)
(lw r2, 1(r0))
(sw r3, 0(r0))
(beq r0, r1, 2)
Assumptions
8 bit ISA
# of registers = 4 + PC (Program Counter)
Memory size = 64B

Instruction Set Architecture
Before Register and Memory

beq r0, r1, 2
After Register and Memory

(add r1, r2, r3)
(lw r2, 1(r0))
(sw r3, 0(r0))
(beq r0, r1, 2)

(add r1, r2, r3)
(lw r2, 1(r0))
(sw r3, 0(r0))
(beq r0, r1, 2)
Assumptions
8 bit ISA
# of registers = 4 + PC (Program Counter)
Memory size = 64B

Instruction Set Architecture
Before Register and Memory

After Register and Memory

(add r1, r2, r3)
(lw r2, 1(r0))
(sw r3, 0(r0))
(beq r0, r1, 2)

(add r1, r2, r3)
(lw r2, 1(r0))
(sw r3, 0(r0))
(beq r0, r1, 2)
Assumptions
8 bit ISA
# of registers = 4 + PC (Program Counter)
Memory size = 64B

Addressing Modes
aka: how do we specify the operand we want?
Register directR3
Immediate (literal)#25
Direct (absolute)M[10000]

Register indirectM[R3]
Base+DisplacementM[R3 + 10000]
Base+IndexM[R3 + R4]
Scaled IndexM[R3 + R4*d + 10000]
AutoincrementM[R3++]
AutodecrementM[R3 -]

Memory IndirectM[ M[R3] ]

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
And shifts!

What does memory look like anyway?
Viewed as a large, single-dimension array, with an address.
A memory address is an index into the array
Byte addressing means that the index (address) points to a byte of memory.

8 bits of data
8 bits of data
8 bits of data
8 bits of data
8 bits of data
8 bits of data
8 bits of data

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others

Which kinds of things can a processor do?
arithmetic
add, subtract, multiply, divide
and, or, shift left, shift right
data transfer
load word, store word

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
Arithmetic
ADC, SBC (carry math)
x86 has SIN, COS, SQRT

BIC (bit clear, rd = r1 & ~r2)

MOV (why does MIPS not need MOV if it has add and r0=0)
STM/LDM (store/load multiple; fast stacking for procedure calls, bit array of regs to/from stack)

Control Flow describes how programs execute
Procedure call (jump subroutine)
Conditional Branch
Used to implement, for example, if-then-else logic, loops, etc.

Control flow must specify two things
Condition under which the jump or branch is taken
If take, the location to read the next instruction from (target)

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others

How do you specify the destination of a branch/jump?
Unconditional jumps may go long distances
Function calls, returns,
Studies show that almost all conditional branches go short distances from the current program counter
loops, if-then-else,
A relative address requires (many) fewer bits than an absolute address
e.g., beq $1, $2, 100=>if ($1 == $2):PC = (PC+4) + 100 * 4

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others

MIPS in one slide

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others
More Information? More Machine Types?
141 will talk some about other machine types
The 141 textbook goes into more detail
I will post a collection of slides and resources from others in Canvas
Many additional resources online

CC BY-NC-ND Pat Pannuto Content derived from materials from,,, and others

rs rt rd shamt funct

rs rt immediate

6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
Register R-type

Immediate I-type

Jump J-type

MIPS operands
$s0-$s7, $t0-$t9, $zero,
Fast locations for data. In MIPS, data must be in registers to perform
32 registers
$a0-$a3, $v0-$v1, $gp,
arithmetic.MIPS register $zero always equals 0.Register $at is
$fp, $sp, $ra, $at
reserved for the assembler to handle large constants.
Memory[0],
Accessed only by data transfer instructions. MIPS uses byte addresses, so
Memory[4], ,
sequential words differ by 4. Memory holds data structures, such as arrays,
Memory[4294967292]
and spilled registers, such as those saved on procedure calls.

MIPS assembly language
Instruction
add $s1, $s2, $s3
$s1 = $s2 + $s3
Three operands; data in registers
Arithmetic
sub $s1, $s2, $s3
$s1 = $s2 $s3
Three operands; data in registers
add immediate
addi $s1, $s2, 100
$s1 = $s2 + 100
Used to add constants
lw$s1, 100($s2)
Word from memory to register
store word
sw$s1, 100($s2)
+ 100] = $s1
Word from register to memory
Data transfer
lb$s1, 100($s2)
Byte from memory to register
store byte
sb$s1, 100($s2)
+ 100] = $s1
Byte from register to memory
load upper
lui $s1, 100
$s1 = 100 * 2
Loads constant in upper 16 bits
branch on equal
beq$s1, $s2, 25
$s1 == $s2
PC + 4 + 100
Equal test; PC-relative branch
Conditional
branch on not equal
bne$s1, $s2, 25
$s1 != $s2
PC + 4 + 100
Not equal test; PC-relative
set on less than
slt$s1, $s2, $s3
Compare less than; for beq, bne
set less than
slti$s1, $s2, 100
Compare less than constant
go to 10000
Jump to target address
jump register
For switch, procedure return
tional jump
jump and link
= PC + 4; go to 10000
For procedure call

Sheet: Sheet1
Sheet: Sheet2
Sheet: Sheet3
Sheet: Sheet4
Sheet: Sheet5
Sheet: Sheet6
Sheet: Sheet7
Sheet: Sheet8
Sheet: Sheet9
Sheet: Sheet10
Sheet: Sheet11
Sheet: Sheet12
Sheet: Sheet13
Sheet: Sheet14
Sheet: Sheet15
Sheet: Sheet16
MIPS operands
$s0-$s7, $t0-$t9, $zero,
Fast locations for data. In MIPS, data must be in registers to perform
32 registers
$a0-$a3, $v0-$v1, $gp,
arithmetic.MIPS register $zero always equals 0.Register $at is
$fp, $sp, $ra, $at
reserved for the assembler to handle large constants.
Memory[0],
Accessed only by data transfer instructions. MIPS uses byte addresses, so
Memory[4], ,
sequential words differ by 4. Memory holds data structures, such as arrays,
Memory[4294967292]
and spilled registers, such as those saved on procedure calls.
MIPS assembly language
Instruction
add $s1, $s2, $s3
$s1 = $s2 + $s3
Three operands; data in registers
Arithmetic
sub $s1, $s2, $s3
$s1 = $s2 $s3
Three operands; data in registers
add immediate
addi $s1, $s2, 100
$s1 = $s2 + 100
Used to add constants
lw$s1, 100($s2)
Word from memory to register
store word
sw$s1, 100($s2)
Word from register to memory
Data transfer
lb$s1, 100($s2)
Byte from memory to register
store byte
sb$s1, 100($s2)
Byte from register to memory
load upper immediate
lui $s1, 100
Loads constant in upper 16 bits
branch on equal
beq$s1, $s2, 25
Equal test; PC-relative branch
Conditional
branch on not equal
bne$s1, $s2, 25
Not equal test; PC-relative
set on less than
slt$s1, $s2, $s3
Compare less than; for beq, bne
set less than immediate
slti$s1, $s2, 100
Compare less than constant
go to 10000
Jump to target address
jump register
For switch, procedure return
tional jump
jump and link
For procedure call

Sheet: Sheet1
Sheet: Sheet2
Sheet: Sheet3
Sheet: Sheet4
Sheet: Sheet5
Sheet: Sheet6
Sheet: Sheet7
Sheet: Sheet8
Sheet: Sheet9
Sheet: Sheet10
Sheet: Sheet11
Sheet: Sheet12
Sheet: Sheet13
Sheet: Sheet14
Sheet: Sheet15
Sheet: Sheet16
MIPS operands
$s0-$s7, $t0-$t9, $zero,
Fast locations for data. In MIPS, data must be in registers to perform
32 registers
$a0-$a3, $v0-$v1, $gp,
arithmetic.MIPS register $zero always equals 0.Register $at is
$fp, $sp, $ra, $at
reserved for the assembler to handle large constants.
Memory[0],
Accessed only by data transfer instructions. MIPS uses byte addresses, so
Memory[4], ,
sequential words differ by 4. Memory holds data structures, such as arrays,
Memory[4294967292]
and spilled registers, such as those saved on procedure calls.
MIPS assembly language
Instruction
add $s1, $s2, $s3
$s1 = $s2 + $s3
Three operands; data in registers
Arithmetic
sub $s1, $s2, $s3
$s1 = $s2 $s3
Three operands; data in registers
add immediate
addi $s1, $s2, 100
$s1 = $s2 + 100
Used to add constants
lw$s1, 100($s2)
Word from memory to register
store word
sw$s1, 100($s2)
Word from register to memory
Data transfer
lb$s1, 100($s2)
Byte from memory to register
store byte
sb$s1, 100($s2)
Byte from register to memory
load upper immediate
lui $s1, 100
Loads constant in upper 16 bits
branch on equal
beq$s1, $s2, 25
Equal test; PC-relative branch
Conditional
branch on not equal
bne$s1, $s2, 25
Not equal test; PC-relative
set on less than

CS: assignmentchef QQ: 1823890830 Email: [email protected]