2017-11-17 課堂練習

2.58: 撰寫函式 is_little_endian，在 Little endian 機器上返回 1，反之返回 0，應能再任意機器上，無論幾位元的架構都適用 (Page 88)

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)

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 電腦上執行則需要對應的修改，如：

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 的方法

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 是
$N a N$ ，直接回傳 f。輸入數值範圍為有效的 2³² 個數值 (Page 96)

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)^{s i g n} * 2^{e x p o n e n t} * s i g n i f i c a n d

表示，而另外有幾種特別的表示法：

規格化的值：這個是最常見的表示法，exponent 值不全為 0 也不全為 1，且 significand 須介於 1 <= significand < 2 之間，用於表示一般的浮點數。
非規格化的值：這裡非規格化的值指的是 exponent 全為 0 的情況，通常用於表示 +0.0（sign 為 0）以及 -0.0（sign 為 1），或是非常接近 0 的數。
而最為特殊的則是 exponent 全為 1 的情況，假如 significand 全為 0 則代表無窮大，反之則表示
$N a N$ 。

有了上述觀念之後，本題的解題方向就很清楚了，題目要求判斷

N a N

，因此不能夠簡單的把 sign 取 not，而需要判斷 exponent 是否全為 1 即 0xFF 且 significand 是否為 0，這時候就需要將浮點數完全拆開來，最後將浮點數的 3 個部分合在一起輸出即可。

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

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% )

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

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 修改如下

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, 相鄰矩陣 (Adjacency Matrix)
本題與上一題類似，不過先來執行原本的程式碼看看結果（ 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 修改如下

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
CS:APP p.441-442
CS:APP p.456