# Computer Org
###### tags: `courses`, `note`

## Cache
### 濃縮
> 參考：https://hackmd.io/@drwQtdGASN2n-vt_4poKnw/H1U6NgK3Z?type=view

digraph {
  rankdir=LR;
  cpu [label="CPU"]
  m [label="main memory"]
  
  cpu -> m [label="addr"]
  m -> cpu [label="data"]
  rank=same; cpu; m;
}

digraph {
  rankdir=LR;
  cpu [label="CPU"]
  c [label="cache"]
  m [label="main memory"]
  
  cpu -> c [label="addr"]
  c -> cpu [label="data"]
  c -> m [label="addr"]
  m -> c [label="data"]
  rank=same; cpu; m;
}

對 CPU 與 main memory 來說，他們的做的事完全沒有改變。
我們會將 main memory 分為很多個 **block**，一次 cache 一個 **block**

digraph {
  node [shape="pain text"];
  rankdir=LR;
  cache [label=<
    <table>
      <tr>
        <td colspan="3" border="0">Cache</td>
      </tr>
      <tr>
        <td>valid</td>
        <td>Tag</td>
        <td>Block data</td>
      </tr>
      <tr><td PORT="line0">1</td><td>01010011</td><td>1010101001</td></tr>
      <tr><td PORT="line1">0</td><td>01010011</td><td>1010101001</td></tr>
      <tr><td>0</td><td>01010110</td><td>1010101001</td></tr>
      <tr><td>:</td><td>:</td><td>:</td></tr>
    </table>
  >];
  
  l0 [label="line: 0" shape=""]
  l0 -> cache:line0
  l1 [label="line: 1" shape=""]
  l1 -> cache:line1
}

**Cache line**: 一個 line 包含 valid bit, tag, 與 block data
**Block data**: 從 main memory copy 下來的 data
**Tag**: 在後續用作查詢用的 key

### Cache mapping
在 CPU 要求某個 address 時，我們需要用某種算法查訊這個 address 的 data 在不在當前 cache 起來的 data 中。

#### **Fully-associated**
main memory 的 address 可以看成，第 x 個 block 中的第 y byte。
接著把 x 當成 tag，在查詢的時候便咳以直接 for 每一個 line 比較 tag

 CPU_get_byte(addr):
   for line in cache:
     if line.tag == addr.tag and line.vaild == True:
       return line.block_data[addr.block_offset]
   return Fetch_data_from_memory(addr)

##### example:

digraph {
  rankdir=LR;
  label="Assume:\n32-bit addressing arch,\nblock_size=32B"
  m [shape="record" label="main memory|block 0|block 1|<b2>block 2|...|..."]
  addr [shape="pain text" label=<
    <table border="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="10">
      <tr><td colspan="2">address: 32-bit</td></tr>
      <tr>
        <td>000000000000000000000000020</td>
        <td PORT="tail">00011</td>
      </tr>
      <tr>
        <td>tag: 27 bit</td>
        <td>block_offset: 5 bit</td>
      </tr>
    </table>
  >]
  
  addr:tail->m:b2
  cache [shape="pain text" label=<
    <table>
      <tr>
        <td colspan="3" border="0">Cache</td>
      </tr>
      <tr>
        <td>valid</td>
        <td>Tag</td>
        <td>Block data</td>
      </tr>
      <tr>
        <td PORT="b2">1</td>
        <td>000000000000000000000000020    </td>
        <td>block 2</td>
      </tr>
      <tr>
        <td>:</td><td>:</td><td>:</td>
      </tr>
    </table>
  >];
  
  addr:tail->cache:b2
}

缺點：查詢慢

#### **Directed mapped**
將 main memory 中的 block map 到特定 line。

CPU_get_byte(addr):
  target_line = addr.index
  if target_line.tag == addr.tag:
    return target_line.block_data[addr.offset]
  else:
    return Fetch_from_memory(addr)

##### example:
假設總共有 512 個 line。則：
block 0, 512, 1024.. 會 map 到 line 0
block 1, 513, 1025... 會 map 到 line 1

digraph {
  rankdir=LR;
  label="Assume:\
          32-bit addressing arch,\
          block_size = 32B\
          Number of line/block = 512\n"
          
  m [shape="record" label="main memory|block 0|...|<b514>block 514|...|..."]
  addr [shape="pain text" label=<
    <table border="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="10">
      <tr><td colspan="3">address: 32-bit</td></tr>
      <tr>
        <td>0000000000000000000001</td>
        <td>00010</td>
        <td PORT="tail">00011</td>
      </tr>
      <tr>
        <td>tag: 22 bit</td>
        <td>index: 5 bit</td>
        <td>block_offset: 5 bit</td>
      </tr>
    </table>
  >]
  
  cache [shape="pain text" label=<
    <table>
      <tr>
        <td colspan="3" border="0">Cache</td>
      </tr>
      <tr>
        <td>valid</td>
        <td>Tag</td>
        <td>Block data</td>
      </tr>
      <tr>
        <td>1</td><td>some tag</td><td PORT="b0_tail">some block data</td>
      </tr>
      <tr>
        <td>1</td><td>some tag</td><td PORT="b1_tail">some block data</td>
      </tr>
      <tr>
        <td PORT="b2">1</td>
        <td>0000000000000000000001   </td>
        <td PORT="b2_tail">block 514</td>
      </tr>
      <tr>
        <td>:</td><td>:</td><td>:</td>
      </tr>
    </table>
  >];
  
  addr:tail->m:b514
  addr:tail->cache:b2
  
  cache:b0_tail -> index0 [dir="back"]
  cache:b1_tail -> index1 [dir="back"]
  cache:b2_tail -> index2 [dir="back"]
}

缺點：有幾個 block 將會共用一個 line，導致他們不能同時存在於 cache 中：

#### **X byte N-way Set Associative**
> 合併上面兩者的好處

將 main memory 中的 block map 到特定 set。
**set**：包含 N 個 line。
因此在查詢時，只需要對一個 set 迭代一次找 tag 即可。
> 有點類似 hash

CPU_get_byte(addr):
  let target_set = addr.index
  for EACH line in target_set:
    if line.tag == addr.tag and line.vaild == True:
      return line.block_data[addr.block_offset]
    else:
      return Fetch_from_memory(addr)

## Page Table

union Content{
  struct Page_table*;
  Addr phy_addr;
}
struct Page_table {
  Content table[n];
}

Page_table first_table[n];

Addr get_PA_by_VA(Addr VA) {
    struct Page_table* second = first_table.table[VA[0:7]]
    struct Page_table* third = second->table[VA[7:14]]
    struct Page_table* f = third->table[VA[14:21]]
    Addr phy_page_number = f->table[VA[21:32]]
    Addr offset = VA[32:43]
    return concat(phy_page_number, offset)
}