HackMD
2016q3 Homework1 (clz)
contributed by <aweimeow>
tags: sysprog21 aweimeow
注意命名方式 Homework1 表示「第一週」，不是第一個，每週都有「若干多份作業」
作業環境
- OS: Ubuntu 14.04.4 LTS
- CPU: Intel® Core™ i5-4210M CPU @ 2.60GHz
- Memory: 8G
- Cache:
- L1d cache: 32KB
- L1i cache: 32KB
- L2 cache: 256KB
- L3 cache: 3072KB
recursive clz
把作業有瑕疵的版本修改一下變成：
unsigned clz(uint32_t x, int c)
{
if (!x) return 32;
if (c == 0) return 0;
/* shift upper half down, rest is filled up with 0s */
uint16_t upper = (x >> c);
// mask upper half away
uint16_t lower = (x & (0xFFFF >> (16 - c)));
return upper ? clz(upper, c / 2) : c + clz(lower, c / 2);
}
不過看了 louielu的共筆 得知有 __builtin_clz，也感謝他的踩雷，我會小心避開地雷 XD
About Testing
這邊在寫 Testing 的時候不知道為什麼碰到困難了，弄了二十分鐘還是找不到原因 QQ
assert(result && printf("Test Fault: %d", i));
result 是一個布林值，將 recursive clz 與 builtin_clz 互相比較結果，相等為 1，不同為 0。
但是這樣子 assert 時，不會有 assert Error (這個當然沒有錯），問題出在後面應該是錯誤時才會 print 的訊息也跟著出來了。
我思考了之後認為發生的原因是出在於 result = 1 因此 && 後面的句子理所當然也會執行了。
可是這樣就與老師上課時所提到的技巧不一樣，是不是我哪邊記錯了，在這篇 StackOverflow 的文章也有提到相同的用法。
assert 中的參數 expression 本身就是 scalar (純量，當然是數值)，於是你應該改成
assert(result && "messages")，這樣才符合期望。 jserv
暫時不知道怎麼解決，只好先把 printf 拿掉了，如果有人知道怎麼解請編輯我的紀錄留言告訴我，感謝 QQ。
以下是我的 Test Function
bool test_clz(void *test_func)
{
unsigned (*clz)(uint32_t, int) = test_func;
assert(clz(0, 16) == 32);
for (uint32_t i = 1; i < UINT_MAX; i++) {
bool result = (clz(i, 16) == __builtin_clz(i));
assert(result);
if (!result)
return 0;
}
return 1;
}
不過這個要跑多久呢 … 先看看 __builtin_clz 跑完 UINT_MAX 會多久，
在編譯的時候我用的是：
$ gcc -o main -O0 -std=gnu99 main.c -lm
然後執行結果：
$ ./main
execution time: 10.105143 sec
再來跑 recursive version：
$ ./main
execution time: 168.580997 sec
阿阿阿阿我的眼睛業障真重阿！！！跑一次實驗就要這麼久，更不用提要跑 Test Function 會跑多久了 …
但是最久的 recursive ver. 都跑完了，iteration ver 不可能比這個還久吧，總之就先把這些都跑一輪吧。
iteration version:
$ ./main
execution time: 91.110889 sec
binary search version:
$ ./main
execution time: 29.033097 sec
Byte Shift Version:
$ ./main
execution time: 28.998363 sec
為什麼 builtin 可以這麼快 Orz
gnuplot
接下來是把剛剛的結果們變成以 gnuplot 作圖，這邊先說明一下我給 gnuplot 的 input 是：
因為在這個題目當中，我們的 range 非常大，從 0 至 4294967295（大約是 42.9 億），這個要把這麼多筆寫到檔案也是一個很可怕的數字，所以在此我就不這麼作，我以 100萬 作為一個單位，也就是說，假設 x 是 input 的話，0 <= x < 1000000，會作為一筆資料寫入檔案當中。
檔案會長成這樣子：
1000000 0.010095
2000000 0.006899
3000000 0.006891
4000000 0.007032
5000000 0.006054
6000000 0.006080
7000000 0.005785
8000000 0.005898
9000000 0.005836
10000000 0.005786
第一筆資料表示是 0 ~ 1000000 所計算的秒數，時間長達0.010095 秒
而在產出來的結果，X 軸表示我輸入的數值，Y 軸表示我執行的時間。
Byte-Shift Version
Binary-Search Version
Iterate Version
Recursive Version
查表法？
如果說，程式在執行的時候有一個表可以查，那應該會快很多，在一個 32 bits 的狀況當中，我只需要建立出一個 16 bits 的表，與前面的 recursive 作法相似，把 32 bits 切成高、低兩組。
如果高位那半部非 0，那就直接回傳高位在 16 bits 表查出的結果。否則就回傳 16 + 低位在 16 bits 表查出的結果。
那麼這個表總共會有 65536 格，0 ~ 65535！
Table Initialize
#define L 65536
int T[L] = {0};
void init(int *T){
int i,j;
for ( i=0 ; i<L ; ++i ){
for ( j=i^0xffff ; j ; j>>=1 ){
T[i] = ((j&1) ? T[i]+1 : 0);
}
}
}
Calculate clz
int clz_T(uint32_t x, int *T){
return T[x>>16] + ( (T[x>>16]==16) ? T[x&0xffff] : 0 );
解釋一下程式在做什麼：
當 Table 要初始化的時候，會有 0 ~ 65535 的 Index，分別代表著 0 的 clz 計算後 value 應該是 32, 1 的結果是 31, … 等。
所以一開始會有一個 for loop(line 5)，然後 j 是一個 i 與 0xFFFF 互斥或後的結果，0 會變成 1111，且只要 j 不為 0 就會繼續執行，每次迴圈 j 會右移一位。
再來是檢查 j 的最後一位（j&1），如果結果為 1(True)，則代表在還沒互斥或之前的 i 的這個位置是 0，把 T[i] 累加上去。那如果 j&1 是 0(False) 呢，代表我們現在撞到 1 了，所以前面所計算的 0 都不能算數，因此把 T[i] 歸零。
===
再來是 clz_T 的部份，return 把他切成左右兩部份來看，左部份表示要查 x 的 higher part 的值是多少。右半部則是如果左半部高位結果為 16 （代表全部都是 0 組成），這時我們才需要繼續去看低位部份的結果，並把他加起來。反之，如果左半部非 16，那就直接回傳左半部的結果即可
實測數據
create table execution time: 0.004787 sec
execution time: 17.292436 sec
建立這個表格花費 0.004787 秒，而從 0 查到 232-1 總共花了 17.292436 秒。
！突然想到用前面學過的重複執行來平均執行的時間
$ perf stat --repeat 10 -e cache-misses,cache-references,instructions,cycles ./test
Performance counter stats for './test' (10 runs):
699,734 cache-misses # 35.430 % of all cache refs
1,374,100 cache-references
133,179,793,211 instructions # 2.55 insns per cycle
51,319,436,287 cycles
18.757043258 seconds time elapsed ( +- 2.60% )
但是這個作法並不是這麼的實用，因為 clz 不見得會需要查那麼多次阿 XDD 只是因為測試需求測完 32 bits 的所有輸入才比較實用而已。
再來用著 OpenMP 加速看看：
create table execution time: 0.014015 sec
execution time: 12.710633 sec
發現建立表格的時間變長了。不過這個時間與我使用 builtin clz 跑的 10.105143 sec 只差一點點了！心滿意足 XD
這會導致嚴重的 cache miss，應該透過數學分析法去降低表格大小，請研究 Harley’s algorithm jserv
最後再加上沒有開 OpenMP 的圖，不開的原因是因為開了之後時間飄很大，而且開了也沒快很多。
