Try   HackMD

2017q3 Homework1(clz)

contributed by <TsengWen>

Review by maskashura

  • 列出了各種 clz的程式碼,何不也寫下你對各種 clz 寫法的分析及理解呢?
  • 在程式執行結果只有原始程式執行出來的plot圖,但沒有看到對於這張圖中不同的執行時間做分析,也沒有針對分散的執行結果做統計分析

作業要求

  • 閱讀 重新理解數值 裡頭關於 count leading zero (clz) 的描述，設計實驗，比較 32-bit 數值對以下實做的效能差異：
    • recursive version
    • iteration version
    • binary search technique
    • byte-shift version
    • Harley's algorithm
  • [ ]除了在 重新理解數值 列出的程式，詳閱劉亮谷的實驗紀錄，予以重現並解釋個別實作的運作原理
  • [ ]走訪全部的 32-bit 數值，用上述演算法帶入計算 clz 值，先驗證正確性，如果演算法不正確，試圖改正
  • [ ]在 GitHub 上 fork clz-tests，以此為基礎進行以下調整 (如在 9 月 23 日就 fork 過，那請重新 fork)
    • 用 C99 或 C11 改寫程式碼，其中 C11 的 _Generic 非常好用，詳情可見 你所不知道的 C 語言：前置處理器應用篇
    • 比照 phonebook 和 compute-pi，設計一套 benchmark suite，得以針對所有的 32-bit 數值進行個別 clz 實做效能的分析，並透過 gnuplot 製圖
    • 要附上個別數值實際耗費時間，不能只列出平均值
    • 提供落點分析圖，類似 tcp-anaysis (with-code)
    • 為了避免編譯器最佳化的影響，務必指定編譯參數 -O0 來抑制最佳化
  • [ ]找至少 3 個案例，說明 clz 的應用場合
  • [ ]將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於「作業區」

De Bruijn sequence

  • B(k, n) 是一種 sequence，由 k 種不同符號組成，且其所有長度為 n 之連續子序列恰為 k 種符號組成長度為 n 的所有排列。
    • 例如：00010111 即為一 B(2, 3) 序列，因其連續子序列（尾端循環至開頭）
      000, 001, 010, 101, 011, 111, 110, 100 恰為所有由 {0, 1} 組成且長度 3 的序列。
  • 若由 k 種符號組成之所有長度為 n 之序列表為有向圖中的頂點，則圖中有 k^n 個頂點，
    若頂點 m 去掉第一個符號並在尾端添加一符號可得頂點 n，則有一有向邊由 m 指向 n，此即
    De Bruijn graph。
    • 例如：k = 2, n = 3 的圖中，頂點 010 有兩條對外的邊，分別指向 101 及 100。

參考

程式碼閱讀

make 
make run 
make plot

recursive version

static const int mask[] =  { 0, 8, 12,14 };
static const int magic[] = { 2, 1,  0, 0 };

unsigned clz2(uint32_t x,int c)
{
    if (!x && !c) return 32;

    uint32_t upper = (x >> (16 >> c));
    uint32_t lower = (x & (0xFFFF >> mask[c]));
    if (c == 3) return upper ? magic[upper] : 2 + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}

iteration version

unsigned 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);
}

binary search technique

unsigned clz(uint32_t x)
{
    if (x == 0) return 32;
    int n = 0;
    if (x <= 0x0000FFFF) {
        n += 16;
        x <<= 16;
    }
    if (x <= 0x00FFFFFF) {
        n += 8;
        x <<= 8;
    }
    if (x <= 0x0FFFFFFF) {
        n += 4;
        x <<= 4;
    }
    if (x <= 0x3FFFFFFF) {
        n += 2;
        x <<= 2;
    }
    if (x <= 0x7FFFFFFF) {
        n += 1;
        x <<= 1;
    }
    return n;
}

byte-shift version

unsigned clz(uint32_t x)
{
    if (x == 0) return 32;
    int n = 1;
    if ((x >> 16) == 0) {
        n += 16;
        x <<= 16;
    }
    if ((x >> 24) == 0) {
        n += 8;
        x <<= 8;
    }
    if ((x >> 28) == 0) {
        n += 4;
        x <<= 4;
    }
    if ((x >> 30) == 0) {
        n += 2;
        x <<= 2;
    }
    n = n - (x >> 31);
    return n;
}

Harley's algorithm

unsigned clz(uint32_t x)
{
    static uint8_t const Table[] = { 
      0xFF, 0, 0xFF, 15, 0xFF, 1, 28, 0xFF,
      16, 0xFF, 0xFF, 0xFF, 2, 21, 29, 0xFF,
      0xFF, 0xFF, 19, 17, 10, 0xFF, 12, 0xFF,
      0xFF, 3, 0xFF, 6, 0xFF, 22, 30, 0xFF,
      14, 0xFF, 27, 0xFF, 0xFF, 0xFF, 20, 0xFF,
      18, 9, 11, 0xFF, 5, 0xFF, 0xFF, 13, 
      26, 0xFF, 0xFF, 8, 0xFF, 4, 0xFF, 25, 
      0xFF, 7, 24, 0xFF, 23, 0xFF, 31, 0xFF,
    };  

    /* Propagate leftmost 1-bit to the right */
    x = x | (x >> 1); 
    x = x | (x >> 2); 
    x = x | (x >> 4); 
    x = x | (x >> 8); 
    x = x | (x >> 16);
 
    /* 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];
}

新加入 De Bruijn sequence 不同寫法

unsigned debruijn(uint32_t x)
{
    static const char Debruijn32[32] = {
        0, 31, 9, 30, 3, 8, 13, 29, 2, 5, 7, 21, 12, 24, 28, 19,
        1, 10, 4, 14, 6, 22, 25, 20, 11, 15, 23, 26, 16, 27, 17, 18
    };
    x |= x>>1;
    x |= x>>2;
    x |= x>>4;
    x |= x>>8;
    x |= x>>16;
    x++;
    return Debruijn32[x*0x076be629>>27];
}
  • 分佈圖
  • 分佈在於 iteration 附近

C11 _Generic

  • This is effectively a type-directed switch expression. It can be used to implement APIs like tgmath.h using standard C.
  • 我的理解：是一種能根據input的資料型態做不同處理函式的表達式。
#include <stdio.h>
#include <math.h>

#define cbrt(X) \
    _Generic((X), \                                                             
             long double: cbrtl, \
             default: cbrt,  \
             const float: cbrtf, \
             float: cbrtf  \
    )(X)

int main(void)
{
    double x = 8.0;
    const float y = 3.375;
    printf("cbrt(8.0) = %f\n", cbrt(x));
    printf("cbrtf(3.375) = %f\n", cbrt(y));
}

參考資料

Last changed by 
 
TsengWen
0
522
Published on HackMD