# 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
```c=
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
```c=
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
一半一半
```c=
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
直接做位移
```c=
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
```c=
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為底數的對數值
其實還在理解如何應用...
## 參考資料：
* [clz 應用1](https://embedded2015.hackpad.com/ep/pad/static/PLZhxd8JpQ4)
* [clz 應用2](https://hackmd.io/s/S153n-G1g)
* [Makefile 字串函式](http://deanjai.blogspot.tw/2008/02/subst-subst-subst-eeeefeet-on-street.html)
Sign in with Wallet
Connect another wallet