# 2022q1 Homework2 (quiz2)
contributed by <`curlyw819` >
###### tags: `linux2022`
[測驗2題目](https://hackmd.io/@sysprog/linux2022-quiz2)
## 測驗 1
:::info
- [x] 解釋上述程式碼運作的原理
- [ ] 比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀 (可研讀 CS:APP 第 3 章)
- [ ] 研讀 Linux 核心原始程式碼 [include/linux/average.h](https://github.com/torvalds/linux/blob/master/include/linux/average.h)，探討其 [Exponentially weighted moving average (EWMA)](https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average) 實作，以及在 Linux 核心的應用
> 移動平均（Moving average)，又稱滾動平均值、滑動平均，在統計學中是種藉由建立整個資料集合中不同子集的一系列平均數，來分析資料點的計算方法。
> 移動平均通常與時間序列資料一起使用，以消除短期波動，突出長期趨勢或周期。短期和長期之間的閾值取決於應用，移動平均的參數將相應地設置。例如，它通常用於對財務數據進行技術分析，如股票價格、收益率或交易量。它也用於經濟學中研究國內生產總值、就業或其他宏觀經濟時間序列。
:::
### 程式碼
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
### 延伸問題 1
#### `EXP1 : a & b & 1`
說明 : 當 a 和 b 分別左移 1bit 後，若是 a 和 b 原本都是奇數，則原本的算法先加再除時，從二進制的觀點來看 LSB 會產生進位，但位移法卻直接移除LSB，實際上位移法在兩數都為奇數的情況下應該要再 + 1才是正確結果。所以要使用 a&b 來確認 a 與 b 是不是皆為奇數，若是則 and 的結果 LSB 為 1 ，此結果再與 1 做 and 得到數字 1，就能達到判斷是否兩數皆偶數，是的話要再 + 1。
#### `EXP2 : a & b` `EXP3 : a ^ b`
說明 : `a & b` 表進位，`a ^ b` 表位元和。
(x + y) / 2
若用二進制的角度去運算則算式如下 :
= `(x + y) >> 1`
上式的加法可以使用加法器的角度去分解。加法器使用一個 and 閘與 xor 閘進行加法運算，得到位元和與進位 :
將得到的進位左移1bit再相加來使進位加法運算成立，則我們可以再將上式拆分成如下算式 :
= `(x ^ y + (x & y) << 1) >> 1`
上式的位元右移具有分配性，並與括弧內的算術左移作抵銷，得到以下算式 :
= `(x & y) + ((x ^ y) >> 1)`
## 測驗 2
:::info
- [x] 解釋上述程式碼運作的原理
- [ ] 針對 32 位元無號/有號整數，撰寫同樣 [branchless](https://en.wikipedia.org/wiki/Branch_(computer_science)) 的實作
- [ ] Linux 核心也有若干 branchless / branch-free 的實作，例如 [lib/sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c):
```c
/*
* Logically, we're doing "if (i & lsbit) i -= size;", but since the
* branch is unpredictable, it's done with a bit of clever branch-free
* code instead.
*/
__attribute_const__ __always_inline
static size_t parent(size_t i, unsigned int lsbit, size_t size)
{
i -= size;
i -= size & -(i & lsbit);
return i / 2;
}
```
請在 Linux 核心原始程式碼中，找出更多類似的實作手法。請善用 git log 檢索。
:::
### 程式碼
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
### 延伸問題 1
#### `EXP4 : a ^ b` `EXP5 : a < b`
說明 : 從互斥或的性質來推斷，由於
`a ^ 0 = a`
`a ^ a = 0`
由以上兩式可推出
`a ^ 0 = a ^ b ^ b = a`
`a ^ a ^ b == b`
若想 return a，則 `((EXP4) & -(EXP5)) 需為 0`
若想 return b，則 `((EXP4) & -(EXP5))須為 a ^ b`
`-EXP5` 只會是 `0x00000000` 或 `0xffffffff`，而和 `-EXP5` 做運算的下場只會是0或是保持不變，所以`EXP4 = a ^ b`。
接下來觀察真值表推出`EXP5`
|a|b|說明|-EXP5|EXP5|
|:-:|:-:|:-:|:-:|:-:|
|0|0|return `a` 即可，也就是希望 `a ^ ((EXP4) & -(EXP5)) = a`，所以 `-EXP5 = 0`|0|0|
|0|1|`b` 大，所以希望 `((EXP4) & -(EXP5)) = a ^ b`，所以 `-EXP5 = -1`|-1|1|
|1|0|`a` 大，所以希望 `((EXP4) & -(EXP5)) = 0`，所以 `-EXP5 = 0`|0|0
|1|1|同 `a = 0`，`b = 0`|0|0|
由以上真值表可得當 `a < b` 時 `EXP5 = 1` ，所以 `EXP5 = a < b`
## 測驗 3
:::info
- [x] 解釋上述程式運作原理;
- [ ] 在 x86_64 上透過 `__builtin_ctz` 改寫 GCD，分析對效能的提升;
- [ ] Linux 核心中也內建 GCD (而且還不只一種實作)，例如 [lib/math/gcd.c](https://github.com/torvalds/linux/blob/master/lib/math/gcd.c)，請解釋其實作手法和探討在核心內的應用場景。
:::
### 程式碼
```c
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
if (!u || !v) return u | v;
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
while (!(u & 1))
u /= 2;
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (COND);
return RET;
}
```
### 延伸問題 1
#### `COND = v`, `RET = u << shift`
說明 : 首先可以從GDB改寫前的程式碼做參考依據
```c
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
if (!u || !v) return u | v;
while (v) {
uint64_t t = v;
v = u % v;
u = t;
}
return u;
}
```
觀察改寫後程式碼，可以發現之間的差別在於改寫後的演算法強調減少演算法iteratioin次數而先將兩數字中具有2的倍數的公因數的部分給除掉，也就是邏輯右移，但為了不影響最後輸出的結果，得在 `return` 前將要 `return` 的數字乘回前面除掉的公因數，而在改寫後程式碼中都沒有看到這樣的操作，所以可以推斷是在 return 那行計算的。而至於要乘幾次 2，在程式碼一開始
```c
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
就用 `shift` 記錄了除以2的次數，所以 return 那行勢必會有 `2 * shift` 或 `<< shift` ，使用 `<< shift` 可減少CPU運算量，故使用之。
```c
while (!(u & 1))
u /= 2;
```
這邊將不是公因數部分的2的倍數剔除，以減少之後iteration的次數
```c
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
```
這部分是很值觀的輾轉相除演算法，其中` while (!(v & 1)) v /= 2;`這段是將相除的過程中產生的2的倍數去除，以減少iteration的次數，由於本質上是標準的輾轉相除，因此可得 `COND = v` ， 且最後 `return u`，再結合前文推導，得出 `RET = u << shift`。
## 測驗 4
:::info
- [ ] 解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中;
- [ ] 設計實驗，檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 [bitmap density](http://www.vki.com/2013/Support/docs/vgltools-3.html);
- [ ] 思考進一步的改進空間;
- [ ] 閱讀 [Data Structures in the Linux Kernel](https://0xax.gitbooks.io/linux-insides/content/DataStructures/linux-datastructures-3.html) 並舉出 Linux 核心使用 bitmap 的案例;
:::
### 程式碼
```c
#include <stddef.h>
size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
size_t pos = 0;
uint64_t bitset;
for (size_t k = 0; k < bitmapsize; ++k) {
bitset = bitmap[k];
while (bitset != 0) {
uint64_t t = EXP6;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
### 延伸問題 1
#### `EXP6 = bitset & (~bitset + 1)`
說明 : 參考網站 [[C 語言] Bitwise operation note](https://m033010041.github.io/2020/02/28/bitwise-operation-in-C/)，要取 `bit array` 中最低位元是 1 的位置，方法為和 `bit array` 本身的 2 的補數作 AND。
## 參考資料
加法器 : [維基百科](https://zh.wikipedia.org/wiki/%E5%8A%A0%E6%B3%95%E5%99%A8)
Sign in with Wallet
Connect another wallet