2016q3 Homework1(clz)

contributed by <TempoJiJi>

tags: `TempoJiJi` `clz` `sysprog21`

預期目標

閱讀重新理解數值裡頭關於 count leading zero (clz) 的描述，設計實驗，比較 32-bit 數值對以下實做的效能差異：

recursive version
iteration version
binary search technique
byte-shift version
Harley's algorithm

比照 phonebook 和 compute-pi，設計一套 benchmark suite，得以針對所有的 32-bit 數值進行個別 clz 實做效能的分析，並透過 gnuplot 製圖

開發環境

Ubuntu 16.04 LTS
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
Model name: Intel® Core™ i5-4200U CPU @ 1.60GHz

測試每種version的正確性

recursive version












uint8_t clz_recursive(uint32_t x, int shift_len)
{
    if(shift_len == 0)
        return 0;
    /* shift upper half down, rest is filled up with 0s */
    uint16_t upper = (x >> shift_len);
    // mask upper half away
    uint16_t lower = ( x & (0xFFFF >> (16 - shift_len)) );
    return upper ? clz_recursive(upper, shift_len >> 1) : 
                    shift_len + clz_recursive(lower, shift_len >> 1);
}

多了一個參數記錄每次要shift多少位，每次進入lower的遞回就加shift_len

Harley’s algorithm






















int clz_harley(unsigned x) {

   char u = 100; 
   static char 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};

   x = x | (x >> 1);    // Propagate leftmost
   x = x | (x >> 2);    // 1-bit to the right.
   x = x | (x >> 4);
   x = x | (x >> 8);
   x = x | (x >> 16);
   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];
}

其實有點不理解這個演算法的，可能還需要再研究一下…
參考資料：P. 99-106. Number of leading zeros algorithms. - Hacker's Delight












for(int i=1;i<UINT_MAX;i++){
	if( __builtin_clz(i) != clz_recursive(i,16))
		printf("%d\n",i);
	if( __builtin_clz(i) != clz_iteration(i))
    		printf("%d\n",i);
	if( __builtin_clz(i) != clz_binary_search(i))
		printf("%d\n",i);
	if( __builtin_clz(i) != clz_byte_shift(i))
		printf("%d\n",i);
	if( __builtin_clz(i) != clz_harley(i))
		printf("%d\n",i);
}