CSIE - Computer Organization

CSIE - Computer Organization

LAVI
  2022-05-10 2022-05-10 Created   2024-09-11 2024-09-11 Updated    

Ch 1 Computer Abstractions and Technology

Formula

    • =
    • =
    • 該 processor 在整體電腦裡所佔的比例
    • 加速多少倍

Definition

  • CPI
    • Average Clock cycles per instruction.

Ch2 Conclusion

Format

R format 詳細

op rs rt rd shamt funct
  • R format 的 op code 是 0
    • 沒有 shamt 的邏輯 / Conditional 指令是 func rd, rs, rt
      • ex add、sub、mult、slt、and
    • 有 shamt 的邏輯指令是 func rd, rt, shamt
      • ex sll、srl
      • 如何判斷是否有 shamt -> 看神奇小卡

I format 詳細

op rs rt constant or address
  • I format 的 op code 不是 0
    • 儲存型 (跟記憶體有關的) 指令是 func rt, offset(rs)
      • offset 以 byte 為單位
        • = index * 4
      • ex lw、sw、lbu、sb、ll、sc
    • Conditional 型的指令是 func rs, rt, Label
      • 如果符合 func 的指令條件就跳去 L1
      • ex beq、bne、blt
    • immediate 型的 Conditional 指令是 func rt, rs, constant
      • ex slti、addi
op address

  • J format 的 op code 不是 0

    • jump and link 指令是 func Label/procedure
      • ex j、jal
    • jump register 指令是 func $ra
      • ex jr

  • index、constant 都比直觀思考要多 * 4 bytes

  • Conditional 有可能是 I fromat 或 R format，要看小卡上他是否有 destination (不限 rd、rt)

    • 如果有 -> R format
    • 如果沒有 -> I format

Instruction

  • R format
    • add 是 reg + reg，addi 是 reg + constant
    • slt 通常會搭配 bne 使用，有點像旗標的概念

Register 判斷

  • 判斷 rd、rt、rs
  • 看小卡
Name Number Use
$zero 0 Value 0
$at 1 Assembler Temporary
v1 2 ~ 3 Value of Func Results 回傳值
a3 4 ~ 7 Arguments 參數
t7 8 ~ 15 Temporaries 暫存值
s7 16 ~ 23 Saved Temporaries 陣列
t9 24 ~ 25 Temporaries
k1 26 ~ 27 Reserved for OS Kernel
$gp 28 Global Pointer
$sp 29 Stack Pointer
$fp 30 Frame Pointer
$ra 31 Return Address 回家的路

Function 指令判斷

  • R format 根據 Func code 判斷
  • I、J format 根據 OP code 判斷
  • 看小卡

    列幾個常用的

Func Format Decimal
sll R 0
j J 2
jal J 3
beq I 4
bne I 5
addi I 8
slti I 10
mult R 24
div R 26
lb I 32
add R 32
sub R 34
lw I 35
and R 36
sb I 40
sw I 43
ll I 48

Ch2 ISA - Instruction Set architecture of MIPS

Opcode

Assembler names

  • t1, …, $t9 for temporary values
  • s1, …, $s7 for saved variables

Example

  • c
    • f = (g + h) - (i + j);
    • f ~ j in s4
  • compiled MIPS code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    ; load operation
    lw $s1, g
    lw $s2, h
    lw $s3, i
    lw $s4, j

    ; compiled MIPS code
    add $t0, $s1, $s2
    add $t1, $s3, $s4
    sub $s0, $t0, $t1

    ; store operation
    sw f, $s0

MIPS is Big Endian

記憶體位址
high address 0x78
0x56
0x34
low address 0x12

Memory Operand

Example 1

  • c
    • g = h + A[8];
      • g in s2, base address of A in $s3
  • MIPS code
    • Index 8 requires offset of 32
      • 4 bytes per word
1
2
lw  $t0, 32($s3)   ; load word
add $s1, $s2, $t0

Example 2

  • c
    • A[12] = h + A[8];
    • h in s3
  • MIPS code
    1
    2
    3
    lw  $t0, 32($s3)    ; load word
    add $t0, $s2, $t0
    sw  $t0, 48($s3)    ; store word

Immediate Operands

  • 可以用常數在指令裡
    • addi s3, 4
  • 沒有減法指令
    • 所以要用加 negative constant 的方式
    • addi s1, -1
  • 不用 load
  • 0 的寫法是 $zero

Binary Integers

Example

  • x = xn-12^n-1^ + xn-22^n-2^ + … + x12^1^ + x02^0^
    • Range: 0 to + 2^n^ - 1
  • 0000 0000 0000 0000 0000 0000 0000 1011
  • 0 + … + 1×2^3^ + 0×2^2^ + 1×2^1^ + 1×2^0^

Example

  • x = -xn-12^n-1^ + xn-22^n-2^ + … + x12^1^ + x02^0^
    • Range: –2^n–1^ to + 2^n-1^ - 1
  • 1111 1111 1111 1111 1111 1111 1111 1100
  • 0 + … + 1×2^3^ + 0×2^2^ + 1×2^1^ + 1×2^0^

R-format

MIPS R-format Instructions

點此回總結

op rs rt rd shamt funct
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
  • op : operation code (opcode)
  • rs : first source register number
  • rt : second source register number
  • rd : destination register number
  • shamt : shift amount (00000 for now)
  • funct : function code (extends opcode)

Example

op rs rt rd shamt funct
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
  • add s1, $s2
special $s1 $s2 $t0 0 add
0 17 18 8 0 32
000000 10001 10010 01000 00000 100000

Hexadecimal

  • 4 bits per hex digit
0 0000 4 0100 8 1000 c 1100
1 0001 5 0101 9 1001 d 1101
2 0010 6 0110 a 1010 e 1110
3 0011 7 0111 b 1011 f 1111
  • Example : eca8 6420
    • 1110 1100 1010 1000 0110 0100 0010 0000

I-format

MIPS I-format Instructions

點此回總結

op rs rt constant or address
6 bits 5 bits 5 bits 16 bits
  • rt : destination or source register number
  • rs : source register
  • Constant : –2^15^ to +2^15^–1
  • Address : offset added to base address in rs

Logical Operations

Operation C MIPS
Shift left << sll
Shift right >> srl
Bitwise AND & and/andi
Bitwise OR | or/ori
Bitwise NOT ~ nor

Shift Operations

op rs rt rd shamt funct
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
  • shamt : how many positions to shift
    • Shift left logical
      • Shift left and fill with 0 bits
      • sll by i bits multiplies by 2^i^
    • Shift right logical
      • Shift right and fill with 0 bits
      • srl by i bits divides by 2^i^ (unsigned only)

Conditional Operations

  • beq rs, rt, L1
    • if (rs == rt) branch to instruction labeled L1;
  • bne rs, rt, L1
    • if (rs != rt) branch to instruction labeled L1;
  • j L1
    • unconditional jump to instruction labeled L1
  • slt rd, rs, rt
    • if (rs < rt) rd = 1; else rd = 0;
  • slti rt, rs, constant
    • if (rs < constant) rt = 1; else rt = 0;

MIPS machine language

  • Format : R
op rs rt rd shamt funct
add s2, $s3 0 18 19 17 0 32
sub s2, $s3 0 18 19 17 0 34
slt s2, $s3 0 18 19 17 0 42
  • Format : I
op rs rt constant or address
lw s2) 35 18 17 100
sw s2) 43 18 17 100
beq s2, 100 4 17 18 25
bne s2, 100 5 17 18 25
  • Format : J
op address
j 1000 2 2500

Signed vs. Unsigned

  • Signed comparison :
    • slt、slti
  • Unsigned comparison :
    • sltu、sltui

Example

  • $s0 = 1111 1111 1111 1111 1111 1111 1111 1111
  • $s1 = 0000 0000 0000 0000 0000 0000 0000 0001
  • slt $t0, $s0, $s1 # signed
    • –1 < +1 $t0 = 1
  • sltu $t0, $s0, $s1 # unsigned
    • +4,294,967,295 > +1 $t0 = 0

Procedure Calling

  1. Place parameters in registers
  2. Transfer control to procedure
  3. Acquire獲得 storage for procedure
  4. Perform procedure’s operations
  5. Place result in register for caller
  6. Return to place of cal

Register

Register Usage

點此回總結

  • $a0 –$a3: arguments (reg’s 4 –7) 參數
  • $v0, $v1: result values (reg’s 2 and 3) 結果存放值
  • $t0 –$t9: temporaries 暫存
    • Can be overwritten by callee
  • $s0 – $s7: saved 儲存
    • Must be saved/restored by callee
  • $gp: global pointer for static data (reg 28) 全域指標
  • $sp: stack pointer (reg 29) stack指標
  • $fp: frame pointer (reg 30)
  • $ra: return address (reg 31)

Procedure Call Instructions

  • jal ProcedureLabel
    • Address of following instruction put in $ra
    • Jumps to target address

Procedure return : jump register

  • jr $ra
    • Copies $ra to program counter
    • Can also be used for computed jumps

Leaf Procedure

  • 普通的 call 一輪 fuc 的 procedure
    1
    2
    3
    4
    5
    int leaf_example (int g, h, i, j){ 
        int f;
        f = (g + h) -(i + j);
        return f;
    }

Non-Leaf Procedure

  • Procedures that call other procedures
    • 遞迴的 procedure
  • For nested call, caller needs to save on the stack
    • Its return address
    • Any arguments and temporaries needed after the call
  • Restore from the stack after the call
    1
    2
    3
    4
    int fact (int n){ 
        if (n < 1) return f;
        else return n * fact(n -1);
    }

Not much Important

Three-address machines

  • 2 source operands & 1 result
  • RISC processors
    1
    2
    3
    4
    5
    6
    add    dest,src1,src2 
        ; M(dest)=[src1]+[src2]
    sub    dest,src1,src2 
        ; M(dest)=[src1]-[src2]
    mult   dest,src1,src2 
        ; M(dest)=[src1]*[src2]

Eample

  • c
    1
    A = B + C * D – E + F + A
  • equivalent code
    1
    2
    3
    4
    5
    mult   T,C,D  ;T = C*D
    add    T,T,B  ;T = B+C*D
    sub    T,T,E  ;T = B+C*D-E
    add    T,T,F  ;T = B+C*D-E+F
    add    A,T,A  ;A = B+C*D-E+F+A

Two-address machines

  • 1 source operand & 1 result
    1
    2
    3
    4
    load   dest,src; M(dest)=[src] 
    add    dest,src; M(dest)=[dest]+[src]
    sub    dest,src; M(dest)=[dest]-[src]
    mult   dest,src; M(dest)=[dest]*[src]

Example

  • c
    1
    A = B + C * D – E + F + A
  • equivalent code
    • 相較於 three address machine，多了 load 的步驟
      1
      2
      3
      4
      5
      6
      load   T,C  ;T = C
      mult   T,D  ;T = C*D
      add    T,B  ;T = B+C*D
      sub    T,E  ;T = B+C*D-E
      add    T,F  ;T = B+C*D-E+F
      add    A,T  ;A = B+C*D-E+F+A

One-address machines

  • Uses special set of registers called accumulators
    • Specify one source operand & receive the result
  • Called accumulator machines
    1
    2
    3
    4
    5
    load   addr; accum = [addr] 
    store  addr; M[addr] = accum 
    add    addr; accum = accum + [addr]
    sub    addr; accum = accum -[addr]
    mult   addr; accum = accum * [addr]

Example

  • c
    1
    A = B + C * D – E + F + A
  • equivalent code
    • 相較 two address machine 多了 store 的步驟
      1
      2
      3
      4
      5
      6
      7
      load   C  ;load C into accum
      mult   D  ;accum = C*D
      add    B  ;accum = C*D+B
      sub    E  ;accum = B+C*D-E
      add    F  ;accum = B+C*D-E+F
      add    A  ;accum = B+C*D-E+F+A
      store  A  ;store accum contents in A

Zero-address machines

  • Stack supplies operands and receives the result
    • Special instructions to load and store use an address
  • call stack machine
    1
    2
    3
    4
    5
    push   addr ; push([addr]) 
    pop    addr ; pop([addr]) 
    add         ; push(pop + pop)
    sub         ; push(pop -pop)
    mult        ; push(pop * pop)

Example

  • c
    1
    A = B + C * D – E + F + A
  • equivalent code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    push E
    push C
    push D
    mult
    push B
    add
    sub 
    push F
    add
    push A
    add
    pop A
  • 運算是把 st(0) = st(0) +-*/ st(1) 的概念，最後會存回 st(0)
運算 push
C*D+B-E+F+A
A
C*D+B-E+F
F
C*D+B-E
C*D+B
B
C*D
D
C
E
On this page
CSIE - Computer Organization
  1. Ch 1 Computer Abstractions and Technology
    1. Formula
    2. Definition
  2. Ch2 Conclusion
    1. Format
    2. Instruction
    3. Register 判斷
    4. Function 指令判斷
  3. Ch2 ISA - Instruction Set architecture of MIPS
    1. Opcode
    2. Assembler names
    3. MIPS is Big Endian
    4. Memory Operand
    5. Immediate Operands
    6. Binary Integers
    7. R-format
    8. Hexadecimal
    9. I-format
    10. Logical Operations
    11. Shift Operations
    12. Conditional Operations
    13. MIPS machine language
    14. Signed vs. Unsigned
    15. Procedure Calling
    16. Register
    17. Procedure Call Instructions
    18. Leaf Procedure
    19. Non-Leaf Procedure
    20. Not much Important