---
# System prepended metadata

title: 計組 - ch2
tags: [Computer Organization]

---

# 計組 - ch2
###### tags: `Computer Organization`

## 二 . MIPS指令
### (一) . R-format
![](https://i.imgur.com/6nLEgnb.png =500x)
- $Instrcution\  1$ : $add$
  1. 格式 ： ```add $rd, $rs, $rt```。
  2. 功用 ： 將```$rs```和```$rt```的和放到```$rd```。
- $Instrcution\  2$ : $sub$
  1. 格式 ： ```sub $rd, $rs, $rt```。
  2. 功用 ： 將```$rs```和```$rt```的差放到```$rd```。
- $Instrcution\  3$ : $srl$  (shift right logicly)  
  1. 格式 ： ```srl $rs, $rt, shamt```。
  2. 功用 ： 將```$rt```進行『shift right』shamt個bit的值放到```$rs```。
  3. 補充 ： 『shift right』 n個bit ，就是乘以 $2^n$ 。
- $Instrcution\  4$ : $sll$  (shift left logicly)  
  1. 格式 ： ```sll $rs, $rt, shamt```。
  2. 功用 ： 將```$rt```進行『shift left』shamt個bit的值放到```$rs```。
  3. 補充 ： 『shift right』 n個bit ，就是除以 $2^n$ 。
- $Instrcution\  5$ : $and$ 
  1. 格式 ： ```and $rd, $rs, $rt```。
  2. 功用 ： 將```$rs```和```$rt```的and放到```$rd```。
  
- $Instrcution\  6$ : $or$ 
  1. 格式 ： ```or $rd, $rs, $rt```。
  2. 功用 ： 將```$rs```和```$rt```的or放到```$rd```。
- $Instrcution\  7$ : $nor$ 
  1. 格式 ： ```nor $rd, $rs, $rt```。
  2. 功用 ： 將```$rs```和```$rt```的nor放到```$rd```。

### (二) . Conditional Instruction
![](https://i.imgur.com/St9KPSA.png =500x)

- $Instrcution\  1$ : $beq$ (branch if equal) 
  1. 格式 ： ```beq $rs, $rt, Labe```。
  2. 功用 ： 如果```$rs```和```$rt```相等，則切換到Label的code。
- $Instrcution\  2$ : $beq$ (branch if non-equal) 
  1. 格式 ： ```bne $rs, $rt, Label```。
  2. 功用 ： 如果```$rs```和```$rt```不相等，則切換到Label的code。 
- $Instrcution\  3$ : $j$ (jump to label) 
  1. 格式 ： ```j  Label```。
  2. 功用 ： 切換到Label的code。
- $Instrcution\  4$ : $slt$ (set one if right is bigger) 
  1. 格式 ： ```slt $rd, $rs, $rt```。
  2. 功用 ： 如果```$rs```$<$```$rt```，則將```$rd```設為1。
- $Instrcution\  5$ : $slti$ (set one if right is bigger) 
  1. 格式 ： ```slti $rt, $rs, const```。
  2. 功用 ： 如果```$rs```$<$ ```const```，則將```$rt```設為1。
- $Instrcution\  6$ : $lw$ (load word) 
  1. 格式 ： ```lw $rt, offset [$rs]```。
  2. 功用 ： 在記憶體中，以```$rs```為起始位置的offset個地方load進去```$rt```。
- $Instrcution\  7$ :  $sw$ (read word) 
  1. 格式 ： ```sw $rt, offset [$rs]```。
  2. 功用 ： 在記憶體中，以```$rs```為起始位置的offset個地方寫進去```$rt```。

- $Practice\ Condition$ :  $if$
  1. 概念 ： 處理```Not```的情況。 
  2. ```C code``` : 
      ![](https://i.imgur.com/wCbIw4u.png =350x)
  3. MISP code : 
    ```
          bne $s3 ,$s4 ,ELSE 
          add $s0 ,$s1 ,$s2
          j EXIT
    ELSE: sub $s0 ,$s1 ,$s2 
    EXIT:  .....
    ```
- $Practice\ Condition$ : $Loop$
  1. 概念一 ： 當不滿足condition時，跳出loop。 
  2. 概念二 ： 儲存記憶體指標的地方，需要仔細處理。
  3. ```C code``` : 
     ![](https://i.imgur.com/0hvn0b9.png =400x)
  3. MISP code : 
    ```
    LOOP: sll $t0, $s3, 2      
          add $t0, $t0, $s6
          lw  $t1, 0($t0)
          bne $t1, $s3, EXIT
          addi $s3, $s3, 1
          j LOOP
    EXIT: ....    
    ```   
## 三 . Procedure Call
### (一) . Function call 
- Leaf Procedure and Nested Procedure : 
  1. $Leaf\ Procedure$ : 一個function不會call其他function。
  2. $nonleaf\ Procedure$ : 一個function會call其他的function。
  3. C中的function call : 就是non-leaf呼叫其他的Procedure。
- Caller和Callee : 
  1. Caller : 呼叫其他function的角色。
  2. Callee : 被呼叫的function的角色。
- function call下系統幫我們處理的事 ： 
  1. 將```Caller```目前的```register```變數儲存。
  2. 將```Callee```需要的變數放到```$a```的暫存器。
  3. 將控制全放到```Callee```下 ： 使用```j```的指令。
  4. 執行```Callee```的程式碼。
  5. 將```Callee```執行完的值存到```$v```內。
  6. 回到```Caller``` : 使用```jr $ra```。

### (二) . Procedure Maintain - Example
- 假設有一個C的function被呼叫，系統需要處理的行為。
   1. 假設此時的```g h i j```都已經存在```$a```中了。
   2. 宣告的變數需要放到```$s```中。
```c=
int Leaf_Procedure(int g,int h,int i,int j){
      int f ;
      f = (g+h) - (i+j);
      return f;
}
```
- 所以，在Leaf Procedure被呼叫的時候，系統應該 ： 保存需要用到的變數空間。
  1. 要用到```$t```做**計算**：保存變數於記憶體，並在結束時回複(2-5行)。
  2. 要用到```$t```做**變數宣告**：保存```$s```的變數於記憶體，並在結束時回複(9-13行)。
  
    ```=
    Leaf_Procedure : 
        addi $sp, $sp, -12
        sw   $t0, 8($sp)
        sw   $t1, 4($sp)
        sw   $s0, 0($sp)
        add  $t0, $a0, $a1
        add  $t1, $a2, $a2
        sub  $s0, $t0, $t1
        addi $v0, $s0, $zero
        lw   $t0, 8($sp)
        lw   $t1, 4($sp)
        lw   $s0, 0($sp)
        addi $sp, $sp, 12
        ja   $ra
    ```
- 優化 ： 所有的事都由```Callee```來做，會使的Callee負擔很大。
  1. ```Caller```負責保存```$t```的變數(自己的)。
  2. ```Callee```負責保存```$s```的變數(caller的)。
  3. 問題 ： 那其他的register變數呢，要如何儲存？
- 總結 ： 下表為一個procedure被呼叫的時候，register的變數應該由誰維護。
   1. ```Perserved``` : 必須保留，由```callee```負責。
   2. ```non-perserved``` : 不一定保留，由```caller```視情況保留。
![](https://i.imgur.com/yj5MhNy.png =500x)

## 四 . Adressing Modal
### (一) . MISP的記憶體layout:
![](https://i.imgur.com/vJPjTDJ.png =500x)
- 記憶體分類 ： 
  1. $Static\ Text$ : 儲存程式碼。
  3. $Static\ Data$ : 儲存靜態變數或全域變數的。
  4. $Heap$ : 動態的記憶體。
  5. $Stack$ :  區域變數。
- 記憶體的指標 ： 
  1. ```pc``` : 下一個指令的位址。
  2. ```$sp``` : ```stack pointer```，代表stack的位置。
  3. ```$gp``` : ```gobal pointer```，操作gobal var，位於Static Data。
- ```$fp``` : 基準指標。
  1. 因為：```$sp```會在程式執行中變化。
  2. 所以：新增一個指標為```$fp```當為基準變化的地方。
- MISP的記憶體格式 ： 是一個**32bit*32bit**的空間。
  1. address-value : 分成個別32個位元儲存。
  2. 造成的問題 ： 記憶體的位址有$2^{32}$個，但是很多MISP操作記憶體的指令並沒有辦法有$2^{32}$個的移動空間，因此需要不同的『address modal』。

### (二) . 位元運算
- $Instrcution\  1$ : $lb$
  1. 格式 ： ```lb $rt, offset($rs)```。
  2. 功用 ： 將```$rs```offset後的『一個byte』放到```$rt```。
- $Instrcution\  2$ : $sb$
  1. 格式 ： ```sb $rt, offset($rs)```。
  2. 功用 ： 將```$rt```的『一個byte』放到```$rs```的offset之後。
- $Instrcution\  3$ : $lh$
  1. 格式 ： ```lh $rt, offset($rs)```。
  2. 功用 ： 將```$rs```offset後的『半個word』放到```$rt```。
- $Instrcution\  4$ : $sh$
  1. 格式 ： ```sh $rt, offset($rs)```。
  2. 功用 ： 將```$rt```的『半個word』放到```$rs```的offset之後。
- 例子 ： 存入一個32位元的整數。     
     
### (三) . Adress Modal
- 什麼是『Adress Modal』：
  1. 問題 ： 有時候記憶裝置(記憶體等等)的定址空間的範圍大於一個MISP的I/O指令可以操作的範圍，甚至大於32個bit。
  2. 所以 ： 我們必須在僅有的資源下，使用不同的定址模型，幫助我們操作儲存空間。
- $Immediate\ addressing$ : 帶有常數的操作時。
  - 例：帶有『 i 』的指令時。
  ![](https://i.imgur.com/5uZxBJC.png =400x)
- $Register\ addressing$ : 只有用到暫存器的操作。
  - 例：```add sub```等等。
    ![](https://i.imgur.com/XZP59iH.png)
- $Base\ or\ displacement\ addressing$ : 有關記憶體的操作。 
  - 例：```lw sw```等等。
  ![](https://i.imgur.com/RGqrm4r.png)
- $PC\ Relative$:也是有關記憶體的，但是開始的位置為```$pc```的位置。
   - 特別用於```beq bne```等等指令。
 ![](https://i.imgur.com/OE9aH2F.png)
- $Direct\ jump\ addressin$ : 可以使用整個32bit的大小轉換，但其實用的方法和PC relative差不多。
   - 特別用於```j jal```等等指令。
 ![](https://i.imgur.com/pspYzuR.png)


### (四) . PC-Relative和Direct jump addressin
- PC-Relative 
  1. offest代表 ： ```$pc```的相對位址**除以4**(注意，```$pc```會一直變化)。
  2. 使用format : ```L-format```，offset最高可以有$2^{16}*2^{2}=2^{18}$個bit。   
  3. 範圍 ： ```$pc```的正負$128K$個位置。
![](https://i.imgur.com/zAgaYnz.png =700x)


- Direct jump addressin : 
  1. offest代表 ： 要轉移的絕對位址**除以4**，但一定不足，所以再向```$pc```拿取前面4個bit。
  2. 使用format : ```j-format```，offset最高可以有$2^{26}*2^{2}=2^{28}$個bit。   
  3. 範圍 ： ```$pc```的正負$256M$個位置。
 
- 例子 ： 如果$pc=40000000(16進位)$下。下面指令是jump到多少。
![](https://i.imgur.com/DVgxPqe.png)
     - 對pc拿4個bit : 即一個16進位的大小。
     - 再把其加上j-format的offset。
     - **比較不會有錯的方法**：全畫成2進位相加減
        ```
        PC     : 0010 0000 0000 0000 0000 0000 0000 0000
        offset : 0000 0000 0000 0000 0000 0010 0000 0001
        end    : 0010 0000 0000 0000 0000 0010 0000 0001
        ```
- 例子 ： 預測終點
   -  用展開的方法，比較不會有問題。
   -  PC在```1ffff004```的地方，若目標在```20014924```上，可以用branch切換到嗎？
   -  可以 ： 用相減跟最大就可以知道。
   ```
   Target : 0010 0000 0000 0000 0100 1001 0010 0100
   PC     : 0001 1111 1111 1111 1111 0000 0000 0100
   相減   :  0000 0000 0000 0001 0100 1001 0010 0000
   最大   :  0000 0000 0000 0011 1111 1111 1111 1111
   ```

## 五. MISP 解碼方法
### (一) . MISP指令的型態
- 一個Forrmat可以用多個address model。
![](https://i.imgur.com/xbNFINv.png =1000x)


     