2017q1 Homework1(clz)

contributed by < baimao8437 >

Reviewed by `jack81306`

在設計實驗的部分,可以多設計幾個範圍來測試不同方法的效能
把不同的方法弄成圖表來比較
弄成脈衝圖可以更明顯地觀察到變化
可以把應用實例的超連結直接放上去

花費時間 _3/3 _- _3/4

讀書：6 hr
文件：4 hr
coding: 4 hr
~~看著發呆：1 hr~~

目標設定

習慣 linux 系統基本操作
熟練 git 版本控管操作
繪圖工具 gnuplot
提升對 binary 、 bitwise 熟練度
減少發呆時間…

前置作業

一開始 make 發現沒有 git hook的兩個檔案
從之前的作業複製過來就可以 make 了

並將在 compute-pi 學習到的 makefile 簡化法套用這個作業
原本也想學習 compute-pi 的 test_time.c 將所有算法寫在一起
再用 define 去分別執行但在這裡程式的關係更為複雜
所以先不要亂動好了~

開發環境

baimao@baimao-Aspire-V5-573G:~$ lscpu
Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              69
Model name:            Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
製程：              1
CPU MHz：             1711.242
CPU max MHz:           2600.0000
CPU min MHz:           800.0000
BogoMIPS:              4589.38
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           3072K
NUMA node0 CPU(s):     0-3

CLZ

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

先看懂 return 跟 ternary(?:) 的混合使用

if (a >=0)
    return a;      ----->   return  a>=0  ? a : -a
else                               這是判斷
    return -a;                     後面才是回傳值

運作原理：
c 初始值為0 代表所在層數(32-16-8-4-2) 運作到 c=3 時會開始回傳加總結果
magic 主要做的是在剩下兩個 bits 以後（c==3）判斷有幾個 0
x 一進入後判斷都是0的話就回傳32

再來分為 upper & lower 兩半

當 c!=3 檢查 upper 是否為0 不是0就代 upper 進下層是0 就代 lower 進下層且回傳值會加上確定的 0 數 (16>>c)

當 c==3 檢查 upper 是否為0 此時 upper 剩下2bits
不是0 就回傳 magic[upper] 是0就回傳 2(upper=00) + magic[lower]
magic代表的就是最後有幾個0了接著回傳加上之前確定的0數就是答案

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

運作原理：
y 的性質跟 recursive 的 upper 一樣先判斷 upper 是否為 0
不為 0 就先把 n 扣掉已知不重要 bits 的個數 upper 範圍縮小一半再跑一次迴圈
等於 0 就往 lower 的地方縮小範圍去跑一次迴圈
直到 y 都是 0 了等 c 跑完跳出迴圈
最後回傳 n - x (x皆為1 n為左邊數來第幾個不為零的數)

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

運作原理：
每次比一半若 x <= 0x0000ffff 表示確定有前面 16 位是 0
就把 x 往左 shift 再比一半依此類推只要確定前面有幾個 0 就好

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

運作原理：
跟 binary 類似的原理每次砍半利用直接位移的方式來檢查前面有幾個確定為 0
有找到確定為 0 時就要把 x 往左 shift 檢查 lower 的前面有幾個 0
最後看第一位是否為 0 (x >> 31) 扣掉後即為答案

Harley's algorithm

算第幾個位置是 leading 1




























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];
}

運作原理：
主要操作分為兩部份第一部份較簡單是在將第一個(左到右)不為0的後面全部都變1 直接看數字就懂
至於這樣做的理由等等解釋

input:
00000000 00000000 00000000 10000000 
stage1:
00000000 00000000 00000000 10000000 
00000000 00000000 00000000 11000000 
00000000 00000000 00000000 11110000 
00000000 00000000 00000000 11111111 
00000000 00000000 00000000 11111111 
00000000 00000000 00000000 11111111

第2部份就比較神奇了我看不出這些操作是什麼道理看一下數據

延續上方
stage2:
00000000 00000000 00000110 11111001 
00000000 00000110 11110010 00000111 
00000110 11101011 00010100 11111001 
11100100 00101001 11100100 00000111 
^^^^^^
index:
111001  <--- x >> 26

只取最前面6個數字當 index 然後去找 Table[index]
得到的數字是右邊數來第幾個是 leading 1 (0 代表第一位)

神奇的來了第2部份的操作到底再幹嘛呢我不想理解了直接看數據
我將

2^{0}

2^{31}

當作 input 去看程式輸出結果:

     input =>Table[index]=> result
         1 => Table[ 1] =>  0
         2 => Table[ 5] =>  1
         4 => Table[12] =>  2
         8 => Table[25] =>  3
        16 => Table[53] =>  4
        32 => Table[44] =>  5
        64 => Table[27] =>  6
       128 => Table[57] =>  7
       256 => Table[51] =>  8
       512 => Table[41] =>  9
      1024 => Table[20] => 10
      2048 => Table[42] => 11
      4096 => Table[22] => 12
      8192 => Table[47] => 13
     16384 => Table[32] => 14
     32768 => Table[ 3] => 15
     65536 => Table[ 8] => 16
    131072 => Table[19] => 17
    262144 => Table[40] => 18
    524288 => Table[18] => 19
   1048576 => Table[38] => 20
   2097152 => Table[13] => 21
   4194304 => Table[29] => 22
   8388608 => Table[60] => 23
  16777216 => Table[58] => 24
  33554432 => Table[55] => 25
  67108864 => Table[48] => 26
 134217728 => Table[34] => 27
 268435456 => Table[ 6] => 28
 536870912 => Table[14] => 29
1073741824 => Table[30] => 30
2147483648 => Table[62] => 31

太神奇了傑克~ 32 個 input 剛好對應了不同的 index
那我合理的將這個算法理解為一個 Hash
那兩個操作部份的意義也很明顯了第1部份是為了同化結果
e.g. 1001 & 1100 經過 stage 1 都會變成 1111
那第2部份的操作就是他對 stage 1 ouput 的 Hash Function 愈複雜的函數能將資料分的愈均勻
Table 中就是各 index 對應的輸出結果右邊數來第幾個是leading 1(0是第一位)
那 hash 就是以空間換取時間的作法所以花費時間可以很短但空間花費相對大

原始效能 gnuplot

可以看到如影片中所說 byte & binary 所用 cycles 最少
harley 也相對平穩

偵錯

使用原本寫好的工具在 make run 後面加上 PROFILE=1
就會進入偵錯工具順利用所有 method 跑完所有 32-bit 數值沒有錯誤

設計benchmark suite

我覺得原本的 makefile 方式可以帶來非常大的便利性
只要加上不同的 define 就可以進行不同的操作
define 的用法又比上一個作業高上一層

我還沒想到有什麼更快更便利的方法來設計
但還是自己寫了一個能夠輸出不同位錯誤個數的測試方式
輸入make generrcsv就會產生64*5表格格式為

1bit_errcount , 1bit_time ,2bits_errcont , 2bits_time....
(next method)...

但是…還在思考圖像化要怎麼表示比較好…

應用 clz 的場合

在浮點數除法的優化
乘法的溢位偵測
計算以2為底數的對數值

其實還在理解如何應用…