2017q3 Homework1 (clz)

contributed by <HMKRL>

---

TODO: cdf, pdf

首先觀察各個版本的實作方式，並與效能做比較：

此為 fork 後直接執行 make plot 得到的結果：

原先預期直接採用iteration會根據 leading zero 有不同表現，但發現不是如此，檢視程式碼：

    int n = 32, c = 16;
    do {
        uint32_t y = x >> c;
        if (y) {
            n -= c;
            x = y;
        }
        c >>= 1;
    } while (c);
    return (n - x);

可以發現此處也採用了每次減半的作法，因此不會因 leading zero 數量不同有太大差異。

嘗試將 iteration.c 修改如下：

static inline __attribute((always_inline))
unsigned clz(uint32_t x)
{
    int n = 32;
    while (x) {
        x >>= 1;
        --n;
    }

    return n;
}

得到以下結果：

可以明顯看出數值較小的部份，由於 leading zero 較多，花費的 cycle 數也較多

• binary & byte
  分別觀察這兩種作法的程式碼，可以發現實作幾乎相同，差別在是直接比較或先進行位移，因此效能分析的結果也幾乎相同

• recursive

為了減少遞迴末段的 function call 造成效能問題，採用了 magic 表做終止條件查表

• harley
  首先觀察這段程式碼：

x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);

直接帶入數值協助理解，帶入 0000 0000 0100 0000 1110 1111 0000 1000

得到 0000 0000 0111 1111 1111 1111 1111 1111

由此得知這段程式碼用途是將第一次出現的1之後的位元都設為1

/* x = x * 0x6EB14F9 */
x = (x << 3) - x;   /* Multiply by 7. */
x = (x << 8) - x;   /* Multiply by 255. */
x = (x << 8) - x;   /* Again. */
x = (x << 8) - x;   /* Again. */

return Table[(x >> 26)];

此區域經過觀察，得知其為一種 hash function ，可以將經過前項處理產生的33種可能數值轉化至最高5個位元，並透過查表對照相應的clz值

此種作法的優點：因為是採用查表實作，因此只要更改對應的表格，就可以便於計算其他數值(例如 CTZ )