CS:APP 學習指引 (1)--隨堂練習
===

contributed by <`BreezeDa`>

###### tags: `sysprog2017`

## 計算機組織與結構

:::success
4.47: 以 C 語言指標改寫原本使用陣列表示法的氣泡排序程式碼 (Page 327) / 延伸題目: 最佳化 / Analysis on Bubble Sort Algorithm Optimization
:::
1. 改成用指標引用陣列

void bubble_a(long *data, long count){
    long *i, *last;
    for(last = data + count -1 ; last > data; last--){
        for(i = data; i<last; i++){
            if( *(i+1) < *i  ){
                //swap
                long t = *(i+1);
                *(i+1) = *i;
                *i = t;
            }
        }
    }
}

2. 最佳化
這邊一樣使用指標引用，與 1. 不同的地方: **多了一個指標 newLast，分別在 line 2, 3, 4, 11**。 newLast 的作用在於減少比較次數。減少的方法如右說明 : bubble sort 在比較的過程中，若倆倆順序不符，便會 swap，反過來說，若符合大小排列，便不會交換，因此只要找到每輪中最後一個被調換的位置，就可以確定其後方的數列已經排序完成。利用這點在每輪紀錄 newLast 並更新到 last 便可降低比較次數。

void bubble_a(long *data, long count){
    long *i, *last, *newLast;
    for(last = data + count -1 ; last > data; last = newLast){
        newLast = data;
        for(i = data; i<last; i++){
            if( *(i+1) < *i  ){
                //swap
                long t = *(i+1);
                *(i+1) = *i;
                *i = t;
                newLast = i;
            }
        }
    }
}

:::success
6.37: 計算 N=64 和 N=60 的 cache miss rate (Page 455)
:::

**由題目可知以下幾個條件**
1. int 大小為 4 bytes
2. cache size = 4KB
3. cache 為 direct map
4. block size = 16 bytes
5. 由 2. 4. 可知 ==**cache 可容納的 block 數量 = 4KB/16B = 256**==
6. 由 1. 4. 可知一個 ==**block 可塞 4 個 integer**==
7. 由 3. 5. 可想像 cache 的長相如下 ( 沒畫出 valid bit ):

|index| block content |
|-|--|
|0| mem[0x0800000] |
|1||
|...||
|255||
8. 其陣列從 0x08000000 開始，因為 LSB 為 0，所以 array 從該 block 的第一個 byte 開始，且
**block number = 0x0800000** ( 0x08000000 所在的 block 的編號 )
0x0800000 mod 0x100 = 0，所以**該 block 0x0800000 若讀取到 cache 中會放置在 index 為 0 的 地方** ( 如上示意圖 )

### N = 64

array 中，每一列都**剛好塞滿** 16 個 blocks，而**每 16 列可剛好塞滿 cache 0~255**，示意圖如下
其中
- 側標及上標表示 array 0~63 的索引
- 每一格代表一個 block
- blk [N] : 表示此 block 若被存放到 cache 將會放在 index = N 的那塊空間

|array|0|4|...|63|
|--|-|-|-|-|
|**0**|==blk [0]==| blk [1]|...|blk [15]
|**1**|blk [16]
|...|...
|**15**|blk [240]| blk [241]|... |==blk [255]==
|**16**|==blk [0]==| blk [1]|...| blk [15]
|**17**|blk [16]
|...|
|**31**|blk [240]|blk [241]|...|==blk [255]==
|**32**|
|...|
|**63**|

---
**sumA**

row major 的存取方式，在存取每個 block 的第一個 integer 時，會 miss，其他皆 hit

又因為條件 6，所以 **miss rate = 1/4 = 25 %**
e.g.
:::info
miss: a[0][0]
hit : a[0][1], a[0][2], a[0][3]
:::

**sumB**

col major 的存取方式，由上面的 array 示意圖可看出，在讀取行時，每 16 列，便會出現 index 相同的 block (cache 中)，因此在第一行全部 miss 後，讀到第二行時，仍會因為該 block 早就被其他 block 覆蓋而全部 miss。因此 **miss rate = 100%**

e.g.
:::info
在讀取 a[0][0] 時，系統將該 block 從 memory 搬到 cache index = 0 的位置中，同樣的當讀到 a[16][0] 時，系統也將該 block 從 memory 搬到 cache index = 0 的位置中，如此一來便覆蓋掉 a[0][0] 所在的 block，所以當讀取到第二行 a[0][1] 時，因為其所在的 block 已經被覆蓋掉了，所以仍會 miss。
:::

**sumC**

一次讀取 4 個元素，a[i][j]、a[i][j+1]、a[i+1][j]、a[i+1][j+1]，讀取流向與 col major 相同，其中前兩個元素屬於同一個 block，後兩個元素同屬於另一個 block。因此第一輪讀取時，也就是讀取第一、二行時，第一行的部分全部 miss，第二行的元素全部 hit，而在第二輪讀取時，也就是讀取第三、四行時，會因為如同 sumB 覆蓋的原因，使得情況與第一輪相同。因此，每一輪皆有一半 miss 一半 hit，所以 **miss rate = 50%**

### N=60

array 中，每一列都**剛好塞滿** 15 個 blocks，示意圖如下

|array|0|4|...|59|
|--|-|-|-|-|
|**0**|==blk [0]==| blk [1]|...|blk [14]
|**1**|blk [15]
|...|...
|**16**|blk [240]| blk [241]|... |blk [254]
|**17**|==blk [255]==| ==blk [0]==|...| blk [13]
|**18**|blk [14] | blk [15]
|...|
|**35**|blk [254]|==blk [255]==|..
|...|
|**59**|

**sumA**
row major order，同 N = 64 的 sumA 說明

=> **miss rate = 25%**

**sumB**

由上面 array 與 block 的混搭示意圖可看出，
第二個 blk [0] 的位置 = 第一個 blk [0] + 17 row + 1 col
第二個 blk [15] 的位置 = 第一個 blk [15] + 17 row + 1 col
...
所以可以推知，**index 相同的 block 不會出現在同一行中**，這表示讀完第一行後，a[0][0] 所在的 block 仍在 cache 中，因此接著讀第二、三、四行皆會 hit，而第一行全部 miss。接著每 4行一組皆如此，因此可知 **miss rate = 25%**

**sumC**

在第一輪讀取第一、二行的時候 :

miss : a[i][j]、a[i+1][j]
hit : a[i][j+1]、a[i+1][j+1]

在第二輪讀取第三、四行的時候 : all hit，原因同 sumB

一樣每4行一組都是這樣，所以 **miss rate = 25%**