2016q 3Homework4 (clz)

contributed by <heathcliffYang>, <janetwei>

請記得更新分組面中的 github 連結
課程助教

目標

閱讀重新理解數值
設計實驗，測試各個 clz 程式處理 32-bit 數值的效能差異，並分析原因
進行效能優化

重新理解數值

bite-wise operator

x & (x - 1) == 0
在unsigned的情況下,可以判別X是否為2的N次方,若為true則是
x | (x + 1)
確定最低位元的值

Count leading zero

ffs():回傳給定數值的first bit set的位置
例如
- 128 在 32-bit 表示為 0x10000000，ffs(128)會回傳 8
- 129 在 32bit 表示為 0x10000001，ffs(129) 會回傳 1
  但是這裡發現錯誤,應該是寫成
- 128 在 32-bit 表示為10000000,ffs(128)會回傳 8
- 129 在 32bit 表示為 10000001,ffs(129) 會回傳 1

觀察與實驗設計

1. clz.c & clz.h : 將各個clz函式蒐集

現有材料為五種clz的函式:
iteration, binarySearch, byteShift, recursive, harley

recursive 修正
32可以由16,8,4,2,1 組成 (有或沒有總共32種組合，0~31)

uint32_t count = 16;     // Global variable 讓 recursive 每一層知道shift到哪
int recursive(uint32_t x)
{
    int result;
    // shift upper half down, rest is filled up with 0s
    uint16_t upper = (x >> count);    // 另存shift之後的值以供檢查是否足夠shift

    if(x==0) return 32;

    // stopping condition
    if(count == 1) {
        return !(x >> 1);
        /* 01 & 10 為例，shift 1之後分別為0 & 1，
           前者是多一個0，但shift 1之後沒有值代表x還有一個0，所以要回傳1(也就是要+1)*/
    }

    // shifting count and go into recursive
    count >>= 1;
    result = upper ? recursive(upper) : (count << 1) + recursive(x);
    /* shift成功代表leading zero的數量不足count，shift之後繼續用更小的count去檢查
       shift不成功代表leading zero的數量足夠count，用shift前的值繼續檢查，而count<<1則把
    該次檢查計算的leading zero數量加上*/
    count <<= 1;  // 以防多次執行時count的值發生錯誤
    
    return result;
}

參考黃鏡清同學的版本，並做一些修改，e.g. 拿掉mask，因為在mask後x跟lower的值會不同的情況下，必是做upper的

for example 的縮寫是 e.g.，不是 "ex" jserv

harley
(仍在理解中)

int harley(uint32_t x)
{

    static int table[64] =
     {32,31, u,16, u,30, 3, u,15, u, u, u,29,10, 2, u,
       u, u,12,14,21, u,19, u, u,28, u,25, u, 9, 1, u,
      17, u, 4, u, u, u,11, u,13,22,20, u,26, u, u,18,
       5, u, u,23, u,27, u, 6, u,24, 7, u, 8, u, 0, u};

    /* 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);
    /*把最高位後的位元全部補為1*/
	
    /* 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];
	/*用前面6個位元表示ｌｅａｄｉｎｇ　ｚｅｒｏ有幾個*/
}

第一部分 : 把最高不為零位之後的位元全部補為1可以算是一種第一次的分類，歸類相同clz數值的數。
第二部分 : 之後用一些運算(尚在理解中)讓各個數產生一對一的對應，之後做表格 -> hash function 的概念應用。
shift 26 bits，也就是用剩下的 6 bits 來表示0~32的 clz 可能值，但總數是64。根據程式碼的觀察結果，我們認為他是用 output 的結果去做 table

延伸閱讀: Fast, Deterministic, and Portable Counting Leading Zeros jserv

error : initializer element is not constant –-> const int 在 C 裡面不算是 constant，要用#define

2. 測試效能 & 作圖

測執行時間

用0 ~ 4000先小測試一次

製圖不要用 "function1", "function2" 一類不容易看不出來的名稱 jserv

Performance counter stats for './benchmark_time_１':

      12,2282,3714      cache-misses                                                
 10,2295,7826,9347      cpu-cycles                                                  
 17,5241,2939,1061      instructions # 1.71  insns per cycle
      18,9201,5112      branch-misses

    8635.382627756 seconds time elapsed

除了 cache miss，也用 prefetch 案例裡頭 perf 參數和分析方式去探討 jserv

資料處理：

一開始嘗試用Makefile的for去做跑數值的輸入，但是常常跑到一段時間後電腦就掛了，錯誤訊息是: too long list。
把 list 移到 benchmark 裡面，也因為 csv 的檔案太大開不太起來，連圖也不太能畫
目前正在改寫 Makefile，預計分別輸入到不同檔案，正在解決檔案名稱與變數相關的問題…

我們試著用 iteration 函式執行一次0到2^32-1的時間,做圖結果如上
因為資料龐大,每執行一次就會耗費很多時間,因此我們還在思考簡化執行的方法

因為跑全部的資料檔案太大，所以我們只取 clz 的不同值跑了一次
用 perf top 觀察到函式熱點依序為harley-> iteration-> recursive-> binary-> byteSearch

效能分析：

iteration version:
當數字小的時候跑的很快,但是當數字很大時,迴圈裡面執行的行數更多,所以和其他函式比較起來效能不是很好
binary version & byte Shift:
因為在判斷後做的事情一樣，可是判斷的方法略有不同，一個是直接去比值，一個是shift之後值是否為零，我們認為， byteShift 做的事情比較多，但是他的效能卻比較好;對於數值的大小來說,因為做的判斷次數一樣,所以執行時間和其他函式比相對穩定
recursive version：
在數值較小時,叫用函式次數較多,所以執行時間較長;和其他函式相比,他的函式執行次數多了幾倍,因此效能最差
harley's algorithm:
不管輸入的數值大小為何,函式所執行的動作都相同,因此他是執行時間最穩定的函式

3. 應用（not yet）

null suppression

中英文關鍵字之間要使用空白區隔喔！課程助教