2017q1 Homework1 (clz)

contributed by<zhanyangch>

tags:zhanyangch sysprog2017 week1

執行環境

$ lscpu
Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              42
Model name:            Intel(R) Core(TM) i7-2640M CPU @ 2.80GHz
製程：              7
CPU MHz：             855.421
CPU max MHz:           3500.0000
CPU min MHz:           800.0000
BogoMIPS:              5587.06
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           4096K
NUMA node0 CPU(s):     0-3

觀察時間分佈

$ make
$ make run
$ make plot

harley algorithm

• 首先會將第一次出現 1 以後的 bit 都填為 1，例如 計算0xF1
  00000000000000000000000011110001 的結果如下：
  00000000000000000000000011111111
  做完這個動作後，數值只剩下 33種形式(以 32bit 為例)，前面有 m 個 0 之後有 n 個 1，m+n=32

    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);

• 只剩下 33 個值之後，卻仍然佔據 32bit，思考如何可以快速判定這 33 個值的 clz，如果可以找到合適 hash function，可以在不碰撞的情況下 mapping 到較小的數值範圍，並建立 table 對應 clz 的結果。
  如何找到此種 hash function ，有比較快的方式嗎？需要再研究

 static uint8_t const Table[] ={
        32,31, 0,16, 0,30, 3, 0,15, 0, 0, 0,29,10, 2, 0,
        0, 0,12,14,21, 0,19, 0, 0,28, 0,25, 0, 9, 1, 0,
        17, 0, 4, 0, 0, 0,11, 0,13,22,20, 0,26, 0, 0,18,
        5, 0, 0,23, 0,27, 0, 6,0,24, 7, 0, 8, 0, 0, 0
    };
/* 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)];

recursive

• 利用 magic[] 減少遞迴次數

static const int mask[]={0,8,12,14};
static const int magic[]={2,1,0,0};

unsigned clz2(uint32_t x,int c)
{
    if (!x && !c) return 32;

    uint32_t upper = (x >> (16>>c)); 
    uint32_t lower = (x & (0xFFFF>>mask[c]));
    if (c == 3) return upper ? magic[upper] : 2 + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}