A04: clz

tags: sysprog2016

主講人: jserv / 課程討論區: 2016 年系統軟體課程

返回「進階電腦系統理論與實作」課程進度表

作業要求

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

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

參考的程式碼

• 除了在 重新理解數值 列出的程式，以下也要評估:

• recursive version (注意: 以下的程式碼存在瑕疵，需要自行修正)

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

• Harley's algorithm

uint8_t clz(uint32_t x)
{
    static prog_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 pgm_read_byte(&Table[x >> 26]);
}

測試方式

• 走訪全部的 32-bit 數值，用上述演算法帶入計算 clz 值，先驗證正確性，如果演算法不正確，試圖改正
• 比照 phonebook 和 compute-pi，設計一套 benchmark suite，得以針對所有的 32-bit 數值進行個別 clz 實做效能的分析，並透過 gnuplot 製圖
  • 要附上個別數值實際耗費時間，不能只列出平均值
  • 落點分析圖，類似 tcp-anaysis (with-code)
  • 為了避免編譯器最佳化的影響，務必指定編譯參數 -O0 來抑制最佳化

作業繳交方式

• 在 GitHub 上建立一個名為 clz-tests 的 repository
• 將你的觀察、分析，以及各式效能改善過程，並善用 gnuplot 製圖，紀錄於「作業區」
• 找至少 3 個案例，說明 clz 的應用場合
  • 示範: A Fast Hi Precision Fixed Point Divide
  • 提示：透過 Google Books 可以找到一些專門探討 optimization 的書籍，裡頭會有 clz 的應用