# 2017-11-17 課堂練習
- [ ] 2.58: 撰寫函式 `is_little_endian`，在 Little endian 機器上返回 `1`，反之返回 `0`，應能再任意機器上，無論幾位元的架構都適用 (==Page 88==)
```clike=c
bool is_little_endian(){
int char_var=1;
unsigned char *test = (unsigned char*) &char_var;
return test[0]==0;
}
```
已知一台 little endian 的機器，byte order如下
且對於所有位元來說 unsigned char 的大小較 int 為小，因此當將 int 強制轉為 unsigned char 時會使得最高位為 1 因此我們可以藉由排列順序特性來判斷電腦是 little endian 還是 big endian。
- [ ] 2.66: 撰寫函式 `leftmost_one`，產生得以找出數值 x 最高位 `1` 的位元遮罩 (==Page 90==)
```clike=c
int leftmost_one(unsigned x){
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x ^ (x >> 1); //保留最左邊的位元
}
```
首先該程式碼只能夠在 32 bit 電腦上執行，若要在 64 bit 電腦上執行則需要對應的修改，如：
```clike=c
int leftmost_one(unsigned x){
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
return x ^ (x >> 1); //保留最左邊的位元
}
```
舉個例子來說，10 進位 `65280` 轉為 2 進位為 `1111 1111 0000 0000`，因此遮罩就是二進位 `1000 0000 0000 0000` 的 `32768`，這題有點類似先前的 clz，我們先來回顧計算 clz 的方法
```clike=c
int clz(uint32_t x) {
int n = 32, c = 16;
do {
uint32_t y = x >> c;
if (y) { n -= c; x = y; }
c >>= 1;
} while (c);
return (n - x);
}
```
是以每次 shift 2 的次方位來計算最大的`1`所在的位置，但不同的地方在於 clz 要算的是位數，而本題想要得到的答案為最大`1`和後面無數`0`的數值，因此我們可以透過轉換 `1111 1111 0000 0000` 成 `1111 1111 1111 1111` 的方式再藉由與向右 shift 1 位的`111 1111 1111 1111`做 xor 得到`1000 0000 0000 0000`，因此透過每次向右 shift 2 次方位取 or 的方式轉換結果，code 如上所示。
- [ ] 2.92: 撰寫函式 `float_negate`，給定浮點數 `f`，回傳 `-f`，倘若 `f` 是 $NaN$，直接回傳 `f`。輸入數值範圍為有效的 2^32^ 個數值 (==Page 96==)
```clike=c
typedef unsigned float_bits;
float_bits float_negate(float_bits f){
unsigned sign = f >> 31;
unsigned exponent = f >> 23 & 0xFF; //f >> 23 & 11111111
unsigned significand = f & 0x7FFFFF;
/*23bit 111 1111 1111 1111 1111 1111*/
if (exponent == 0xFF && significand != 0) //detect NaN
return f;
return ~sign << 31 | exponent << 23 | significand;
}
```
本題需要複習 IEEE754 的浮點數表示法，在 IEEE 的標準中，32bit 的浮點數可以表示為 1 bit 的 sign，8 bit 的 exponent 以及 23 bit 的 significand，而完整的浮點數可以由 $(-1)^{sign}*2^{exponent}*significand$ 表示，而另外有幾種特別的表示法：
1. 規格化的值：這個是最常見的表示法，exponent 值不全為 0 也不全為 1，且 significand 須介於 1 <= significand < 2 之間，用於表示一般的浮點數。
2. 非規格化的值：這裡非規格化的值指的是 exponent 全為 0 的情況，通常用於表示 +0.0（sign 為 0） 以及 -0.0（sign 為 1），或是非常接近 0 的數。
3. 而最為特殊的則是 exponent 全為 1 的情況，假如 significand 全為 0 則代表無窮大，反之則表示$NaN$。
有了上述觀念之後，本題的解題方向就很清楚了，題目要求判斷 $NaN$，因此不能夠簡單的把 sign 取 not，而需要判斷 exponent 是否全為 1 即 0xFF 且 significand 是否為 0，這時候就需要將浮點數完全拆開來，最後將浮點數的 3 個部分合在一起輸出即可。
- [ ] 4.47: 以 C 語言指標改寫原本使用陣列表示法的氣泡排序程式碼 (==Page 327==) / 延伸題目: [最佳化](https://en.wikipedia.org/wiki/Bubble_sort#Optimizing_bubble_sort) / [Analysis on Bubble Sort Algorithm Optimization](http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5635119)
```clike=c
void bubble_p(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 adjacent elements */
long t = *(i+1);
*(i+1) = *i;
*i = t;
}
}
}
}
```
由於需要使用指標來當索引，因此最顯著的差別就是一開始 last = data + count - 1 直接將 last 指向該序列的最後一欄，原本的 last > 0 改寫為 last > data，只要指標位置在 data 後則迴圈繼續執行，而其他部分則與原本的類似，只差在使用了 *i 去指向原先的 data 欄位。
- [ ] 6.37: 計算 `N=64` 和 `N=60` 的 cache miss rate (==Page 455==)
首先看 A 的部分，sumA 會先讀取整列，而讀取的單位為 16 byte 即 4 個 int，因此由於 N=64 與 60 都是 4 的倍數，所以每 4 個 int 組為 `miss hit hit hit`所以 sumA 都是 25%。
再來是 sumB，由程式碼中可以看出 A 與 B 差在讀取的順序差異，A 先讀列，B則先讀直行，已知 direct map 的 cache 大小為 4K，因此可以塞得下 4096 個整數，所以以 N=64 來說前 64 次讀取都會是 miss，再來連 3 次 64 直行讀取都會全中，同樣的 N=60 也是 4 的倍數因此也會有相同的過程，故 cache miss 一樣是 25%。
比較麻煩的是 sumC，同時讀取一整塊 2×2 （ a[i][j], a[i+1][j], a[i][j+1], a[i+1][j+1]）的整數，因為一次讀 2×2 個，因此 miss rate 為 50%，分別為 `miss miss hit hit` 但因為該迴圈有兩層，故第一層讀完之後，外面那層會全命中，故最終答案為 25%，N=60 時亦同。
該題答案皆為 25%。
- [ ] 6.45: 撰寫更快的轉置矩陣實作 (==Page 458==)
首先使用原先提供的函式，以 perf 執行 100 次得到結果如下 ( dim = 1024 )
```
Performance counter stats for './test' (100 runs):
39,254 cache-misses # 3.565 % of all cache refs ( +- 5.68% )
1,101,006 cache-references ( +- 0.01% )
28,452,308 instructions # 0.60 insn per cycle ( +- 0.00% )
47,351,420 cycles ( +- 0.24% )
0.012327468 seconds time elapsed ( +- 1.33% )
```
```clike=c
void transpose(int* dst, int* src, int dim) {
int i, j;
for (j = 0; j < dim; j++)
for (i = 0; i < dim; i++)
dst[j*dim+i] = src[i*dim+j];
}
```
perf 執行 100 次得到的結果如下
```
Performance counter stats for './test' (100 runs):
5,938 cache-misses # 1.039 % of all cache refs ( +- 13.29% )
571,488 cache-references ( +- 0.99% )
28,407,630 instructions # 2.05 insn per cycle ( +- 0.07% )
13,846,782 cycles ( +- 0.35% )
0.003801669 seconds time elapsed ( +- 2.03% )
```
第一個加速版本只將行列 i, j 進行調換，使得讀取資料彼此接近，locality 發揮作用，大量減少 cache-miss，以 dim = 1024 為例，執行時間由 0.012327468 秒提升為 0.003801669 秒。
```
```
第二個加速版本透過上題的 sumC 啟發，一次處理一整塊 2×2，以下為改寫後的 code
```clike=c
void transpose(int* dst, int* src, int dim) {
int i, j;
for (i = 0; i <= dim-2; i+=2)
for (j = 0; j <= dim-2; j+=2) {
dst[j*dim+i] = src[i*dim+j];
dst[j*dim+i+1] = src[(i+1)*dim+j];
dst[(j+1)*dim+i] = src[i*dim+j+1];
dst[(j+1)*dim+i+1] = src[(i+1)*dim+j+1];
}
}
```
以 perf 執行 100 次的結果如下，可看出效果比一個一個來還要好，時間提升了 0.007078113 秒
```
Performance counter stats for './test' (100 runs):
33,621 cache-misses # 5.844 % of all cache refs ( +- 4.48% )
575,360 cache-references ( +- 0.02% )
26,068,849 instructions # 1.32 insn per cycle ( +- 0.01% )
19,722,537 cycles ( +- 0.16% )
0.005249355 seconds time elapsed
```
如果將第一個與第二個合在一起實作，可以比單使用第一個加速方法還要好上一點點，cache-miss 甚至少了 26.4%
```
Performance counter stats for './test' (100 runs):
4,371 cache-misses # 1.444 % of all cache refs ( +- 9.98% )
302,790 cache-references ( +- 0.15% )
26,063,880 instructions # 2.28 insn per cycle ( +- 0.01% )
11,421,497 cycles ( +- 0.23% )
0.003153592 seconds time elapsed
```
那有沒有可能 4×4 一組會更提升效能呢？以下做了實驗，code 修改如下
```clike=c
void transpose(int* dst, int* src, int dim) {
int i, j;
for (j = 0; j <= dim-4; j+=4)
for (i = 0; i <= dim-4; i+=4) {
dst[j*dim+i] = src[i*dim+j];
dst[j*dim+i+1] = src[(i+1)*dim+j];
dst[j*dim+i+2] = src[(i+2)*dim+j];
dst[j*dim+i+3] = src[(i+3)*dim+j];
dst[(j+1)*dim+i] = src[i*dim+j+1];
dst[(j+1)*dim+i+1] = src[(i+1)*dim+j+1];
dst[(j+1)*dim+i+2] = src[(i+2)*dim+j+1];
dst[(j+1)*dim+i+3] = src[(i+3)*dim+j+1];
dst[(j+2)*dim+i] = src[i*dim+j+2];
dst[(j+2)*dim+i+1] = src[(i+1)*dim+j+2];
dst[(j+2)*dim+i+2] = src[(i+2)*dim+j+2];
dst[(j+2)*dim+i+3] = src[(i+3)*dim+j+2];
dst[(j+3)*dim+i] = src[i*dim+j+3];
dst[(j+3)*dim+i+1] = src[(i+1)*dim+j+3];
dst[(j+3)*dim+i+2] = src[(i+2)*dim+j+3];
dst[(j+3)*dim+i+3] = src[(i+3)*dim+j+3];
}
}
```
perf 結果如下，發現並沒有提升很多，cache-miss 甚至不減反增，可得一次處理 2×2 是比較好的執行結果
```
Performance counter stats for './test' (100 runs):
5,386 cache-misses # 3.083 % of all cache refs ( +- 7.56% )
174,716 cache-references ( +- 0.28% )
26,652,693 instructions # 2.42 insn per cycle ( +- 0.01% )
11,031,122 cycles ( +- 0.24% )
0.003144989 seconds time elapsed
```
- [ ] 6.46: 有向圖轉換為無向圖 (==Page 458==) / 參考: [Graph](http://www.csie.ntnu.edu.tw/~u91029/Graph.html), [相鄰矩陣 (Adjacency Matrix)](https://hellolynn.hpd.io/2017/09/22/%E5%AF%A6%E4%BD%9Cgraph%E8%88%87dfs%E3%80%81bfs%E8%B5%B0%E8%A8%AA/)
本題與上一題類似，不過先來執行原本的程式碼看看結果（ dim = 1024 ）
```
Performance counter stats for './test' (100 runs):
11,724 cache-misses # 1.037 % of all cache refs ( +- 14.13% )
1,130,432 cache-references ( +- 0.01% )
44,279,814 instructions # 1.49 insn per cycle ( +- 0.00% )
29,741,080 cycles ( +- 0.84% )
0.007950646 seconds time elapsed
```
若我們使用了上題一次處理 2×2 的解法，code 修改如下
```clike=c
void convert(int* src, int dim) {
int i, j;
for (j = 0; j <= dim-2; j+=2)
for (i = 0; i <= dim-2; i+=2){
src[j*dim+i] = src[i*dim+j] || src[j*dim+i];
src[j*dim+i+1] = src[(i+1)*dim+j] || src[j*dim+i+1];
src[(j+1)*dim+i] = src[i*dim+j+1] || src[j+1*dim+i];
src[(j+1)*dim+i+1] = src[(i+1)*dim+j+1] || src[(j+1)*dim+i+1];
}
}
```
可得執行結果如下，得到較好的執行時間
```
Performance counter stats for './test' (100 runs):
11,903 cache-misses # 2.669 % of all cache refs ( +- 10.73% )
445,967 cache-references ( +- 0.98% )
43,205,153 instructions # 2.28 insn per cycle ( +- 0.04% )
18,931,655 cycles ( +- 1.13% )
0.005099529 seconds time elapsed
```
### 參考資料
* [little-endian-vs-big-endian](https://chuck42315.wordpress.com/2011/10/30/little-endian-vs-big-endian/)
* CS:APP p.441-442
* CS:APP p.456
Sign in with Wallet
Connect another wallet