2016q3 Homework1(clz)

contributed by <shelly4132>

Reviewed by 0140454

• 應該善用 .gitignore 來排除編譯出來的可執行檔案。
• commit "add recursive version" 中包含多種實作方式，與 commit message 有些不符合。
• 未修正並實作 Harley 演算法。
• 未提出 clz 可應用之處。
• 未提及驗證正確性的結果。
• 可善用圖表來呈現各方式的效能，並進一步分析。

開發環境

• 作業系統：Ubuntu 16.04 LTS
• CPU：Intel® Core™ i5-4200U CPU @ 1.60GHz
• Cache：
  • L1d cache: 32K
  • L1i cache: 32K
  • L2 cache: 256K
  • L3 cache: 3072K

目標

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

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

builtin_clz()

• Returns the number of leading 0-bits in x, starting at the most significant bit position.
  If x is 0, the result is undefined.

int __builtin_clz (unsigned int x)

利用GCC提供的__builtin_clz (unsigned int x)去檢查重新理解數值裡，iteration、binary search、byte shift 算出來的結果。

for(uint32_t i=1; i<UINT_MAX; i++){
#if defined(ITERATIVE)
	assert(iterative_clz(i) == __builtin_clz(i));
#endif
#if defined(BINARY)
	assert(binary_clz(i) == __builtin_clz(i));
#endif
#if defined(BYTE)
	assert(byte_clz(i) == __builtin_clz(i));
#endif
}
	printf("Done!\n");

• assert() 裡面放的判斷式，如果「不成立的話」，程式便不會繼續執行下去。

Recursive

參照老師給的範例去改的，其實算法都大同小異。

int recursive_clz(uint32_t x, int shift)
{
	if(x == 0)
		return 32;
	if(!shift) 
		return 0;

	uint16_t upper = (x >> shift); 
	uint16_t lower = (x & (0xFFFF >> (16 - shift)));
	return upper ? recursive_clz(upper,shift>>1) : shift + recursive_clz(lower,shift>>1);
}

用之前教的time指令去看每一種算法的時間，可以發現recursive的版本比其他版本的時間要高出許，這可能是因為recursive的版本多了很多function call的成本。

time ./check_iterative
Done!
86.34user 0.05system 1:26.39elapsed 100%CPU (0avgtext+0avgdata 1304maxresident)k
0inputs+0outputs (0major+64minor)pagefaults 0swaps
time ./check_binary
Done!
28.20user 0.00system 0:28.20elapsed 100%CPU (0avgtext+0avgdata 1168maxresident)k
0inputs+0outputs (0major+61minor)pagefaults 0swaps
time ./check_byte
Done!
30.46user 0.02system 0:30.49elapsed 99%CPU (0avgtext+0avgdata 1168maxresident)k
0inputs+0outputs (0major+61minor)pagefaults 0swaps
time ./check_recursive
Done!
180.16user 0.27system 3:00.43elapsed 100%CPU (0avgtext+0avgdata 1256maxresident)k
0inputs+0outputs (0major+61minor)pagefaults 0swaps

參考

• 重新理解數值
• VVN