CS计算机代考程序代写 mips compiler Java cache assembly CS3350B Computer Organization Chapter 3: CPU Control & Datapath Part 1: Introduction to MIPS

CS3350B Computer Organization Chapter 3: CPU Control & Datapath Part 1: Introduction to MIPS
Alex Brandt
Department of Computer Science University of Western Ontario, Canada
Monday February 22, 2021
Alex Brandt
Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 1 / 44

Outline
1 Overview
2 MIPS Assemebly
3 Instruction Fetch & Instruction Decode
4 MIPS Instruction Formats
5 Aside: Program Memory Space
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 2 / 44

Layers of Abstraction
We will put together the combinational circuits and state circuits to see how a CPU actually works.
How does data flow through the CPU?
How are the path and circuits (MUX, ALU, registers) controlled?
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 3 / 44

Preview: MIPS Datapath
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 4 / 44

MIPS ISA
MIPS ISA: Microprocessor without Interlocked Pipelined Stages. ë ISA: The language of the computer.
ë Microprocessor: a CPU.
ë Interlocking: To come in chapter 4.
ë Pipelined Stages: The data path is broken into a ubiquitous 5-stage pipeline (also chapter 4).
MIPS is a RISC ISA.
RISC: Reduced Instruction Set Computer.
ë Provided instructions are simple, datapath is simple. Contrast with CISC: Complex Instruction Set Computer.
ë Instructions can be very “meta”, each performing many lower-level instructions.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 5 / 44

The 5-Stages of the Datapath
1 IF: Instruction Fetch
2 ID: Instruction Decode
3 EX/ALU: Execute/Arithmetic 4 MEM: Access Memory
5 WB: Write-back result
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 6 / 44

MIPS Datapath, Spot The Stages
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 7 / 44

Coupling of ISA and Datapath
A datapath must be built to satisfy the requirements of the ISA. Instructions in the ISA determine what is needed internally. Circuitry limit possible instructions.
Built from combinational blocks composed together.
Very hard to decouple the two.
We begin by looking at the MIPS ISA before looking at the datapath components.
ë We need a common language to discuss the datapath and give concrete examples.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 8 / 44

Layers of an ISA
Start at high-level and work down. MIPS assembly
MIPS instruction formats MIPS instruction binary
ë Everything on a computer is a number
ë Recall instruction memory cache (banked L1 cache)
MIPS assembly is a type of RTL: Register transfer language.
Everything in MIPS is specified by registers and movement between them or between registers and memory.
Most often, we abstract away the concept of caches here and assume CPU talks directly with memory.
ë In reality, the circuity of the cache automatically abstracts away the memory hierarchy and handles cache hits/misses.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 9 / 44

MIPS Assembly: The Basics
Registers:
32 general purpose 32-bit integer registers, denoted $0–$31.
$0 always holds the value 0.
$31 is reserved as the link register: stores the the point in instruction memory to return to after a function call.
$PC holds the program counter – address of current instruction $HI & $LO store results of multiplication/division
Memory:
32-bit words and 32-bit memory addresses.
Byte-addressable memory.
Indexed like a big array of bytes: Mem[0], Mem[1024], Mem[32768].
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 11 / 44

MIPS Assembly: RTL Examples
3-Operand Arithmetic:
add $8, $9, $10 ≡ R[8] ← R[9] + R[10]; sub $8, $9, $10 ≡ R[8] ← R[9] – R[10];
2-Operand Arithmetic (Immediate Arithmetic): addi $8, $9, 127 ≡ R[8] ← R[9] + 127; addi $8, $9, 913 ≡ R[8] ← R[9] + 913; addi$8,$9, -6 ≡ R[8]←R[9]-6;
Data Transfer (Memory Accesses):
lw $13, 32($10) ≡ R[13] ← Mem[R[10] + 32]; sw $13, 8($10) ≡ Mem[R[10] + 8] ← R[13];
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 12 / 44

MIPS Assembly: 3 Operand Arithmetic
op $rd, $rs, $rt ≡ $rd=$rsop$rt
$rd is the destination register.
$rs is the (first) source register.
$rt is the second source register.
op is some arithmetic operation:
ë add, addu, sub, subu, and, or, xor, . . .
These instructions assume an interpretation of the bits stored in the register.
Programmer/compiler must choose proper instruction for data. add vs addu
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 13 / 44

MIPS Assembly: 2 Operand Arithmetic
op $rt, $rs, imm ≡ $rt = $rs op imma
$rt is the destination register. $rs is the source register.
imm is an immediate—a number whose value is hard-coded into the instruction.
ë CExample: inti=j+12;
op is some arithmetic operations:
ë addi, addiu, subiu, andi, ori, xori, . . .
ë sll, srl (logical); sla, sra (arithmetic) (shifts are really a special case of R-type instr.)
These instructions assume an interpretation of the bits stored in the register.
Programmer/compiler must choose proper instruction for data. Signed vs unsigned arithmetic. Logical vs arithmetic shifts.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 14 / 44

MIPS Assembly: Data Transfer
lw $rt, offset($rs) ≡ $rt = Mem[$rs + offset] sw $rt, offset($rs) ≡ Mem[$rs + offset] = $rt
$rt is the “value” register. $rs is the “address” register. offset is an immediate.
It is also possible to load and store bytes, halfwords: lb, sb (byte);
lwr, swr (least-signficiant halfword); lwl, swl (most-significant halfword).
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 15 / 44

MIPS: A View of Memory
Note: In reality the processor interfaces with the L1 data cache
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 16 / 44

Aside: Endianness Defined
Endianness: The ordering of multiple bytes which are intended to be interpreted together as a single number.
Important in memory layout, digital signals, networks, etc. Consider the number: 0xAABBCCDD
Little-Endian: The least-significant byte is stored/sent first. Ordering: 0xDD, 0xCC, 0xBB, 0xAA
Big-Endian: The most-significant byte is stored/sent first. Ordering: 0xAA, 0xBB, 0xCC, 0xDD
MIPS is big-endian.
Big-endian conceptually easier but little-endian has performance benefits. In reality, hardware handles all conversions to and from, so we rarely care.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 17 / 44

MIPS Datapath, Instruction Fetch
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 19 / 44

Instruction Fetch
IF — Instruction Fetch
The simplest part of the datapath.
One job: fetch the next instruction to execute from memory. Banked L1 cache 􏰸⇒ separate cache just for instructions
1. On the clock’s rising edge, update the value of PC—program counter. ë Essentially the index into instruction memory.
2. Fetch the instruction from memory and pass it to next stage: instruction decode.
3. Prepare for next instruction: calculate PC + 4 (4 bytes since instructions are word-aligned).
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 20 / 44

MIPS Datapath, Instruction Decode
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 21 / 44

Instruction Decode
ID — Instruction Decode
Break the binary value of an instruction into its parts and decide what to do.
ë Recall: instructions eventually get compiled down to bytecode (i.e. binary).
Get the values ready for arithmetic: registers, immediates.
1. Break the instruction into individual bit segments. 2. Access operand values from registers.
3. Extend immediate to 32 bits (if using).
But how to break the instruction?
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 22 / 44

Aside: MIPS Special Register Names
$zero: the zero-valued register ($0) $at: reserved for compiler ($1) $v0, $v1: result values ($2, $3) $a0 – $a3: arguments ($4–$7)
$t0 – $t9: temporaries ($8–$15, $24, $25) ë Can be overwritten by callee
$s0 – $s7: saved ($16–$23)
ë Must be saved/restored by callee
$gp: global pointer for static data ($28) $sp: stack pointer ($29)
$fp: frame pointer ($30)
$ra: return address ($31)
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 23 / 44

MIPS Instruction Formats
Every instruction in MIPS is 32-bits.
A memory word is 32 bits, after all.
All instructions belong to 3 pre-defined formats:
R-Type: “Register” I-Type: “Immediate” J-Type: “Jump”
Each format defines how those 32 bits of instruction data are broken up into individual “bit-fields” and how they are interpreted during ID stage.
The first 6 bits always encode the opcode.
The opcode determines the type of instruction and format of the
remaining bits.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 25 / 44

R-Type Instructions
R-Type instructions usually have 3 registers as its operands.
ë “Register type”.
ë General arithmetic operations.
op rs rt rd shamt funct 6bits 5bits 5bits 5bits 5bits 6bits
op — the opcode.
rs — first source register.
rt — second source register.
rd — destination register.
shamt — shift amount; used for shift instructions, 0 otherwise. funct — the arithmetic function the ALU should perform.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 26 / 44

R-Type Examples 1
op rs rt rd shamt funct 6bits 5bits 5bits 5bits 5bits 6bits
add $t0, $s1, $s2
op $s1 $s2 $t0 shamt add 0 17 18 8 0 32 000000 10001 10010 01000 00000 100000
sub $t0, $s1, $s2
op $s1 $s2 $t0 shamt sub
0 17 18 8 0 34 000000 10001 10010 01000 00000 100010
For R-Type instructions the opcode and funct together determine the operations to perform.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 27 / 44

R-Type Examples 2
op rs rt rd shamt funct 6bits 5bits 5bits 5bits 5bits 6bits
sll $s0, $t0, 4
op rs $t0 $s0 4 shift left 0 0 8 16 4 0
000000 00000 01000 10000 00100 000000
Note: shift instruction have two registers and an immediate, but are not immediate instructions.
Here, the allowed value of the shift amount is only 5 bits, not 16 bits as in an immediate-type instruction.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 28 / 44

R-Type Examples 3: Bit-Wise Logical Operations
Useful to mask (remove) bits in a word. ë Select some bits, clear others to 0.
and $t0, $t1, $t2
$t2 0000 0000 0000 0000 0000 1101 1100 0000 $t1 0000 0000 0000 0000 0011 1100 0000 0000 $t0 0000 0000 0000 0000 0000 1100 0000 0000
Useful to include bits in a word.
ë Set some bits to 1, leave others unchanged.
or $t0, $t1, $t2
$t2 $t1 $t0
0000 0000 0000 0000 0000 1101 1100 0000 0000 0000 0000 0000 0011 1100 0000 0000 0000 0000 0000 0000 0011 1101 1100 0000
Alex Brandt
Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 29 / 44

I-Type Instructions
I-Type instructions always have 2 registers and an immediate.
ë “Immediate type”.
ë Immediate arithmetic, data transfer, branch.
op rs rt immediate 6 bits 5 bits 5 bits 16 bits
op — the opcode.
rs — first source register.
rt — second source (or destination) register. imm — the immediate/constant.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 30 / 44

I-Type Examples 1
op 6 bits
rs rt immediate 5 bits 5 bits 16 bits
addi $t1, $t0, 10
rs rt immediate 001000 01000 01001 0000000000001010
addiu $t1, $t0, 10
op rs rt immediate 9$t0$t1 10
001001 01000 01001 0000000000001010
Note: unsigned instructions will not signal exception on overflow.
op
8$t0$t1 10
Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 31 / 44

I-Type Examples 2
op 6 bits
op
rs rt immediate 5 bits 5 bits 16 bits
lw $t1, 12($t0)
rs rt immediate $t0 $t1 12
35
100011 01000 01001 0000000000001100
sw $t1, 32($t0)
op rs rt immediate
43 $t0 $t1 32
101011 01000 01001 0000000000100000
Alex Brandt
Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 32 / 44

I-Type Examples 3
bne $t0, $t1, 24
op rs
6 bits 5 bits
rt immediate 5 bits 16 bits
if ($t0 != $t1)
PC = PC + 4 + (24 << 2); else PC = PC + 4; rt immediate 000101 01000 01001 0000000000110000 op rs 5$t0$t1 24 Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 33 / 44 J-Type Instructions J-Type instructions have just one big immediate, called a target. ë “Jump type”. ë Only two instructions: j (jump) and jal (jump and link). op target (jump address) 6 bits 26 bits op — the opcode. target — the target memory address to jump to. Note: target is always multiplied by 4 before being applied to program counter... Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 34 / 44 J-Type Instructions and Pseudo-Direct Addressing Pseudo-Direct Addressing: Almost a direct addressing of instruction memory. Compiler usually handles the calculation of the exact jump target. Next value of PC is target × 4 combined with upper 4 bits of current PC. nPC = (PC & 0xf0000000) | (target << 2); Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 35 / 44 Addressing Instruction Memory in MIPS Pseudo-Direct: J-Type instructions PC-Relative: Branch instructions Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 36 / 44 Addressing Operands in MIPS Immediate Addressing, I-Type instruction. Register Addressing, Almost all instructions. Base Addressing, Data transfer instructions. Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 37 / 44 MIPS ISA: Some Important Instructions Category Logic & Arith. Instruction add subtract add immediate and/or (and/or) immediate shift right logical shift right arithmetic load word store word load byte store byte br on equal br on not equal set less than set less than immediate jump jump register jump and link OP/ Example funct R 0/32 add $s1, $s2, $s3 R 0/34 sub $s1, $s2, $s3 I 8 addi $s1, $s2, 6 R 0/(36/37) (and/or) $s1, $s2, $s3 I 12/13 (andi/ori) $s1, $s2, 6 R 0/2 srl $rd, $rt, 4 R 0/3 sra $rd, $rt, 4 I 35 lw $s1, 24($s2) I 43 sw $s1, 24($s2) I 32 lb $s1, 25($s2) I 40 sb $s1, 25($s2) I 4 beq $s1, $s2, L I 5 bne $s1, $s2, L R 0/42 slt $s1, $s2, $s3 I 10 slti $s1, $s2, 6 J 2 j 250 R 0/8 jr $t1 J 3 jal 250 Meaning $s1 = $s2 + $s3 $s1 = $s2 - $s3 $s1 = $s2 + 6 $s1 = $s2 (∧/∨) $s3 $s1 = $s2 (∧/∨) 6 $rd = $rt >> 4
$rd = $rt >> 4
$s1 = Memory($s2+24) Memory($s2+24) = $s1 $s1 = Memory($s2+25) Memory($s2+25) = $s1 if ($s1==$s2) go to L if ($s1 != $s2) go to L if ($s2<$s3) $s1=1 else $s1=0 if ($s2<6) $s1=1 else $s1=0 go to 1000 go to $t1 go to 1000; $ra=PC+4 Data Transfer Cond. Branch Uncond. Jump Note: knowing the binary values of each bit-field is not neccesary, but understanding the semantic meaning of each instruction is important. Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 38 / 44 Full Method Example: C to MIPS swap: } sll $t1, $a1, 2 add $t1, $a0, $t1 lw $t0, 0($t1) lw $t2, 4($t1) sw $t2, 0($t1) sw $t0, 4($t1) jr $ra # $t1 = k * 4 # $t1 = v+(k*4) # (address of v[k]) # $t0 (temp) = v[k] # $t2 = v[k+1] # v[k] = $t2 (v[k+1]) # v[k+1] = $t0 (temp) # return to calling routine void swap(int v[], int k) { int temp; temp = v[k]; v[k] = v[k+1]; v[k+1] = temp; Note: words and int-type are both 32-bits here. Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 39 / 44 Outline 1 Overview 2 MIPS Assemebly 3 Instruction Fetch & Instruction Decode 4 MIPS Instruction Formats 5 Aside: Program Memory Space Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 40 / 44 Revisiting Program Basics Frame: The encapsulation of one method call; arguments, local variables. ë “Enclosing subroutine context”. (Call) Stack (of frames): The stack of method invocations. ë Base of stack is the main method, each method call adds a frame to the stack. Heap: globally allocated data that lives beyond the scope of the frame in which it was allocated. Static Data: Global data which is stored in a static memory address throughout life of program. Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 41 / 44 MIPS Special Registers $v0, $v1: result values ($2, $3) $a0 - $a3: arguments ($4–$7) $t0 - $t9: temporaries ($8–$15, $24, $25) ë Can be overwritten by callee $s0 - $s7: saved ($16–$23) ë Must be saved/restored by callee $gp: global pointer for static data ($28) $sp: stack pointer ($29) $fp: frame pointer ($30) ë The stack pointer before the current frame’s invocation. $ra: return address ($31) Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 42 / 44 Memory Layout in MIPS (and most languages) Text: program code Static data: global variables ë static/global variables, constant arrays, etc. ë $gp initialized to address allowing ±offsets into this segment Dynamic data: heap ë e.g., malloc in C, new in Java Stack: “automatic” storage Note: In this diagram the higher memory addresses are at top. Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 43 / 44 Handling the Stack in MIPS sort: addi $sp, $sp, -20 sw $ra, 16($sp) sw $s3,12($sp) sw $s2, 8($sp) # make room on stack for 5 registers # save $ra on stack # save $s3 on stack # save $s2 on stack # save $s1 on stack # save $s0 on stack # procedure body # call swap a bunch # restore $s0 from stack # restore $s1 from stack # restore $s2 from stack # restore $s3 from stack # restore $ra from stack # restore stack pointer # return to calling routine sw $s1, 4($sp) sw $s0, 0($sp) ... ... lw $s0, 0($sp) lw $s1, 4($sp) lw $s2, 8($sp) lw $s3,12($sp) lw $ra,16($sp) addi $sp, $sp, jr $ra to do bubble sort exit1: 20 Alex Brandt Chapter 3: CPU Control & Datapath , Part 1: Intro to MIPS Monday February 22, 2021 44 / 44

Related Posts