2022q1 Homework (quiz2)

contributed by < hankluo6 >

第 2 週測驗題

測驗 1

運作原理

將兩數

$x,y$ 分成，整數部分及小數部分：

$$\begin{gathered} \frac{x}{2}=\lfloor \frac{x}{2}\rfloor +frac(\frac{x}{2}) \\ \frac{y}{2}=\lfloor \frac{y}{2}\rfloor +frac(\frac{y}{2}) \end{gathered}$$

就能列出算式：

$$\begin{array}{rl}avg(x,y)& =\lfloor \frac{x+y}{2}\rfloor \\ & =\lfloor \lfloor \frac{x}{2}\rfloor +\lfloor \frac{y}{2}\rfloor +frac(\frac{x}{2})+frac(\frac{y}{2})\rfloor \\ & =\lfloor \frac{x}{2}\rfloor +\lfloor \frac{y}{2}\rfloor +\lfloor frac(\frac{x}{2})+frac(\frac{y}{2})\rfloor \end{array}$$

$$\lfloor frac(\frac{x}{2})+frac(\frac{y}{2})\rfloor =\{\begin{array}{ll}1,& \text{if }x\text{ and }y\text{ are odd}\\ 0,& \text{else}\end{array}$$

求出

$x$ 與

$y$ 皆為奇數時需要加一，EXP1 = a & b & 1。

根據加法器原理可得：

$a+b=a\oplus b+(a\wedge b)<<1$
所以：

$(a+b)>>1=(a\oplus b)>>1+a\wedge b$
得出 EXP2 = a & b，EXP3 = a ^ b。

對應組合語言輸出

• Target: x86_64-w64-mingw32
• Compiler: gcc

uint32_t averagev1(uint32_t low, uint32_t high)
	movl	%edx, %eax  // $eax = high
	subl	%ecx, %eax  // $eax = high - low
	shrl	%eax        // $eax = (high - low) / 2
	addl	%ecx, %eax  // $eax = low + (high - low) / 2
	ret
    
uint32_t averagev2(uint32_t low, uint32_t high)
	movl	%ecx, %eax  // $eax = high
	movl	%edx, %r8d  // $r8d = low
	andl	%edx, %ecx  // $ecx = low & high
	shrl	%eax        // $eax = high >> 1
	shrl	%r8d        // $r8d = low >> 1
	andl	$1, %ecx    // $ecx = low & high ^ 1
	addl	%r8d, %eax  // $eax = low >> 1 + high >> 1
	addl	%ecx, %eax  // $eax = low >> 1 + high >> 1 + (a & b & 1)
	ret
    
uint32_t averagev3(uint32_t low, uint32_t high)
	movl	%ecx, %eax  // $eax = high
	andl	%edx, %ecx  // $ecx = low & high
	xorl	%edx, %eax  // $eax = low ^ high
	shrl	%eax        // $eax = (low ^ high) >> 1
	addl	%ecx, %eax  // $eax = low & high + (low ^ high) >> 1
	ret

TODO

EWMA

#define DECLARE_EWMA(name, _precision, _weight_rcp)			\
	struct ewma_##name {						\
		unsigned long internal;					\
    };
    ...

• name: 決定宣告的 structure 和 function 名稱
• _precision: 決定需要用幾個 bit 來表示定點數小數
• _weight_rcp: EWMA 中的
  $\frac{1}{\alpha }$

static inline void ewma_##name##_init(struct ewma_##name *e)	\
{								\
    BUILD_BUG_ON(!__builtin_constant_p(_precision));	\
    BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));	\
    /*							\
     * Even if you want to feed it just 0/1 you should have	\
     * some bits for the non-fractional part...		\
     */							\
    BUILD_BUG_ON((_precision) > 30);			\
    BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);		\
    e->internal = 0;					\
}	

檢查輸入的數值是否合法，_precision 及 _weight_rcp 必須為編譯時期能決定的常數、_precision 不能大於 30、_weight_rcp須為 2 的倍數，因為add是用 shift 實作，最後初始化internal`。

static inline unsigned long					\
ewma_##name##_read(struct ewma_##name *e)			\
{								\
    BUILD_BUG_ON(!__builtin_constant_p(_precision));	\
    BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));	\
    BUILD_BUG_ON((_precision) > 30);			\
    BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);		\
    return e->internal >> (_precision);			\
}

read 數值時沒有將小數部分印出。

static inline void ewma_##name##_add(struct ewma_##name *e,	\
                     unsigned long val)		\
{								\
    unsigned long internal = READ_ONCE(e->internal);	\
    unsigned long weight_rcp = ilog2(_weight_rcp);		\
    unsigned long precision = _precision;			\
                                \
    BUILD_BUG_ON(!__builtin_constant_p(_precision));	\
    BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));	\
    BUILD_BUG_ON((_precision) > 30);			\
    BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);		\
                                \
    WRITE_ONCE(e->internal, internal ?			\
        (((internal << weight_rcp) - internal) +	\
            (val << precision)) >> weight_rcp :	\
        (val << precision));				\
}

根據目前 internal 的數值分成兩部分：

• internal > 0:
  
  $$\begin{array}{rl}internal& =\frac{(internal\times \frac{1}{\alpha }-internal)+(val\times 2^{precision})}{\frac{1}{\alpha }}\\ & =\frac{(internal\times (\frac{1}{\alpha }-1))+(val\times 2^{precision})}{\frac{1}{\alpha }}\\ & =(internal\times (1-\alpha ))+(val\times 2^{precision})\times \alpha \end{array}$$
• internal <= 0
  
  $$\begin{array}{r}internal=val\times 2^{precision}\end{array}$$

---

測驗 2

運作原理

#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
    return a ^ ((EXP4) & -(EXP5));
}

EXP5 為 boolean 運算，可知結果只可能為 0x0000 及 0xFFFF，當為 0x0000 時，回傳 a ^ 0 = a，當為 0xFFFF 時，回傳 a ^ EXP4。

所以當 a > b 時，EXP5 = 1 才能滿足條件，得出 EXP5 = a > b。
而當 b >= a 時，a ^ EXP4 = b，可得 EXP4 = a ^ b (根據 XOR 的特性 a ^ a = 0)。

32 位元有號數 branchless 實作

改寫〈解讀計算機編碼〉一文的「不需要分支的設計」

int32_t max(int32_t a, int32_t b) {
    int32_t diff = (a - b);
    return b + (diff & ~(diff >> 31));
}

只需在判斷大小的 diff >> 31 加上 NOT 運算，相反大小判斷便能改成回傳 max。

這實作僅在 INT32_MIN <= (a - b) <= INT32_MAX 成立時，才會發揮作用。

---

測驗 3

運作原理

根據輾轉相除法 的演算法可求出答案：

• COND = v
• RET = u << shift

在每次回圈中，持續保持 v 為最小值，當 v 為 0 時，表示無法再提出公因數，便跳出迴圈。而在函式剛開始時，透過迴圈將最大公因數的 2 的次方提出，記錄在 shift 當中，故最後回傳時需再將次方乘回去。

透過 __builtin_ctz 改寫 GCD

• 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升;

  ​​​​#include <stdint.h>
  ​​​​uint64_t gcd64(uint64_t u, uint64_t v) {
  ​​​​    if (!u || !v) return u | v;
  ​​​​    int shift;
  ​​​​    int a = __builtin_ctzl(u), b = __builtin_ctzl(v);
  ​​​​    shift = b ^ ((a ^ b) & -(a < b));
  ​​​​    u >>= shift, v >>= shift;
  ​​​​    int bit;
  ​​​​    if (bit = __builtin_ctzl(u))
  ​​​​        u >>= bit;;
  ​​​​    do {
  ​​​​        if (bit = __builtin_ctzl(v))
  ​​​​            v >>= bit;
  ​​​​        if (u < v) {
  ​​​​            v -= u;
  ​​​​        } else {
  ​​​​            uint64_t t = u - v;
  ​​​​            u = v;
  ​​​​            v = t;
  ​​​​        }
  ​​​​    } while (v);
  ​​​​    return u << shift;
  ​​​​}
  

  效能分析：

  隨機產生 64 bit 的資料，並測量 1000000 次的運行時間

  gcd64	__builtin_ctz gcd64
  0.667711 s	0.425873 s

  可發現效能有有效的提昇，約提昇

  $\frac{0.667711-0.425873}{1000000}=2.4\ast {10}^{-7}$ 秒。

• 2020q3 quiz3

---

測驗 4

運作原理

根據提示找出目前最低位元的 1 即為 bitset & (-bitset)，因為 -bitset = ~bitset + 1，~bitset 將所有位元反轉，+1 會將位元為 1 的部分 (原本為 0) 往 MSB 進位，直到位元為 0 (原本為 1) 的位元，AND 運算後該位元為唯一與 bitset 相同的位元，故能找到最低位元的 1。

ctz/clz 效能比較

其中 bit ratio 為 bitmap 中為 bit 為 true 的比率，可以發現原本的方法不管 bit 數多寡，其運行效率大致相同；而使用 ctz 的方法會受到 bit 數量，當 bit 數量越多，就執行越多次 __builtin_ctzll，在 bit 比率大約 50% 時為分水嶺。故可以得出結論：bit 比率小於 50% 時 __builtin_ctzll 效率較好，反之則為原本的方法較好。

---

測驗 5

運作原理

根據長除法演算法，可利用當前餘數

$\times 10$ 求出下個位數的數字及對應的餘數。程式內的 char *p 即指向一個 1024 bytes 空間的指標，在迴圈內會紀錄對應的商。

當出現重複的小數數值時，表示構成循環小數，便能直接從 hash table 中取出剩下的數字，並加上 ( 以及 ) 後回傳。

所以 MMM 應為將有存放小數數字的節點加入到 hash table 中的操作，即為 list_add，EEE 決定該節點插入的是 hash table 中的第幾個 bucket，從 find 中可以知道 hash function 為 number % size，所以 EEE 為 &heads[remainder % size]，當找到重複的數字時，pos >= 0 進到條件式中，while 迴圈將非循環的小數部分存到 p 中，而 node->index 紀錄數字為小數點後第幾個數，所以 PPP 應為 pos--。

---

測驗 6

#define ALIGNOF(t) \
    ((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)0)

根據你所不知道的 C 語言：記憶體管理、對齊及硬體特性在成員位址不能整除時，會自動加入 padding 做 alignment。&((struct { char c; t _h; } *)0)->_h 取出 _h 成員相對於 0 的位址，相減便能求出 alignment 的位址。

---