Try   HackMD

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部份的操作到底再幹嘛呢 我不想理解了直接看數據
我將

20~
231 當作 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為底數的對數值

其實還在理解如何應用…

參考資料：

Last changed by 
 
baimao8437
0
868
Published on HackMD