2017q1 Homework1 (clz)

contributed by < twzjwang >
作業說明: B04: clz
github: twzjwang/clz-tests

開發環境

Ubuntu Ubuntu 16.04.2 LTS
Linux 4.8.0-36-generic
cpu
version: Intel® Core™ i5-3337U CPU @ 1.80GHz
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K
memory
size: 4GiB

開發前

重新理解數值
- Leading Zeros
  - 在 1 前面(左邊)有幾個 0
  - 浮點數運算

實驗一 - 比較不同實作方法的差異

執行make run make plot 結果
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →

recursive version

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);
}

初始呼叫 clz2(x,0)
若 x 為 0 回傳 32
將 x 分為 upper 跟 lower
- c = 0 (第一次) x = abcdefgh₁₆
  - upper : abcd₁₆
  - lower : efgh₁₆
- c = 1 (第二次) x = abcd₁₆
  - upper : ab₁₆
  - lower : cd₁₆
- c = 2 (第三次) x = ab₁₆
  - upper : a₁₆
  - lower : b₁₆
- c = 3 (第四次) x = a₁₆ = bcde₂
  - upper : bc₂
  - lower : de₂
若 upper 不為 0 遞迴呼叫 clz2(upper, c+1) ，否則 clz2(lower, c+1)
建 mask[] 及 magic[] 協助計算

iteration version

static inline __attribute((always_inline))
unsigned clz(uint32_t x)
{
    int n = 32, c = 16;
    do {
        uint32_t y = x >> c;
        if (y) { n -= c; x = y; }
        c >>= 1;
    } while (c);
    return (n - x);
}

初始呼叫 clz(x)
類似 clz2 將 x 分為兩部分
- c = 16 x = abcdefgh₁₆
  - y = abcd₁₆
  - if(y) x = abcd₁₆
  - else x = efgh₁₆
- …
- c = 1 x = ab₂
  - y = ab₂
  - if(y) x = a₂
  - else x = b₂
N 紀錄目前 X 長度，包括 Leading 0
X 最後剩下一位，可能為 0 或 1
回傳 N-X

binary search technique

static inline __attribute((always_inline))
unsigned clz(uint32_t x)
{
    if (x == 0) return 32;
    int n = 0;
    if (x <= 0x0000FFFF) { n += 16; x <<= 16; }
    if (x <= 0x00FFFFFF) { n += 8; x <<= 8; }
    if (x <= 0x0FFFFFFF) { n += 4; x <<= 4; }
    if (x <= 0x3FFFFFFF) { n += 2; x <<= 2; }
    if (x <= 0x7FFFFFFF) { n += 1; x <<= 1; }
    return n;
}

將迴圈拆開
改變判斷方式
- x = abcdefgh₁₆
- if (x <= 0x0000FFFF) x = efgh0000₁₆
- else x = abcdefgh₁₆
- …

byte-shift version

static inline __attribute((always_inline))
unsigned clz(uint32_t x)
{
    if (x == 0) return 32;
    int n = 1;
    if ((x >> 16) == 0) { n += 16; x <<= 16; }
    if ((x >> 24) == 0) { n += 8; x <<= 8; }
    if ((x >> 28) == 0) { n += 4; x <<= 4; }
    if ((x >> 30) == 0) { n += 2; x <<= 2; }
    n = n - (x >> 31);
    return n;
}

透過 shift x 判斷前幾 bits 是否為 0
- x = abcdefgh₁₆
- if ((x >> 16) == 0) x = efgh0000₁₆
- else x = abcdefgh₁₆
- …

Harley’s algorithm
- 可以根據不同 table 實作 CLZ 或 CTZ

CLZ 應用

資料壓縮

資料壓縮加密及解密過程與 leading zero 相關
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
- Advances in Databases and Information Systems：19th East European Conference, ADBIS 2015, Poitiers, France, September 8-11, 2015, Proceedings
Fast Integer Compression using SIMD Instructions

浮點數

在浮點數架構下，檢查 leading zero 是必要的
e.g. fixed-point to floating-point format conversion
High-Performance System Design: Circuits and Logic

2017q1 Homework1 (clz)

開發環境

開發前

實驗一 - 比較不同實作方法的差異

CLZ 應用

資料壓縮

浮點數

參考