# 2024q1 Homework4 (quiz3+4)
contributed by < `aa860630`>
## 第 3 週測驗題
### 測驗一
#### <版本一>
先是使用 $log$ 來找最高有效位數(```a```)，判斷 ```result + a``` 平方是否小於等於 N 的同時，不斷透過位移 ```a``` 與運算 ```result+a``` 的方式逼近 N

#include <math.h>
int i_sqrt(int N)
{
    int msb = (int) log2(N);
    int a = 1 << msb;
    int result = 0;
    while (a != 0) {
        if ((result + a) * (result + a) <= N)
            result += a;
        a >>= 1;
    }
    return result;
}

以 N = 36 為例 : (下方表示方法來自 [kevinzxc1217](https://hackmd.io/ZHWqRDtCRXCWcohnfdyWxw?view) )
| 迭帶次數 | a | result | (result + a) * (result + a) <= N) |result+=a|
|:-------------------------:|:-----:|:---------------:|:------------:|:------------:|
| 0 | 32 | 0 | False |0|
| 1 | 16 | 0 | False |0|
| 2 | 8 | 0 | False |0|
| 3 | 4 | 0 | True |$2^2$|
| 4 | 2 | 4 | True |$2^2$+$2^1$|
| 5 | 1 | 6 | False |$2^2$+$2^1$+$2^0$|

#### <版本二>
方法與<版本一>一致，差別為使用 ```while``` 迴圈來找到最高有效位元
#### <版本三>

### 測驗二
在程式開發中，除法運算的複雜度高，對於硬體的限制也極高，因此我們利用加法與乘法來取代除法，在提高程式效能的同時，在某些情況下可以提供更好的精確度和硬體實現的簡單性

### 測驗三
#### <版本一>
透過不斷右移來判斷 i 是否為零，為了找到最高有效位元
#### <版本二>
按照順序判斷 ```i``` 是否大於 $2^{16}$、$2^{8}$、$2^{4}$、$2^{2}$，若有則將該冪加到 ```result``` 並將 ```i``` 右移相對應的冪，最後得出的 ```result``` 為最高有效位元

static size_t ilog2(size_t i)
{
    size_t result = 0;
    while (i >= 65536) {
        result += 16;
        i >>= 16;
    }
    while (i >= 256) {
        result += 8;
        i >>= 8;
    }
    while (i >= 16) {
        result += 4;
        i >>= 4;
    }
    while (i >= 2) {
        result += 1;
        i >>= 1;
    }
    return result;
}

在<版本一>程式碼中，無論輸入的數值是多少位元，處理的時間都是與該數值的位元數成正比的。因此，如果最高有效位元是最高位元，則需要處理整個32位元或64位元

然而，在<版本二>程式碼中，根據數值的大小，處理的時間會根據不同的條件而有所不同。當輸入的數值足夠大時，透過逐步將數值除以較大的數（例如65536、256、16），可以快速地減小數值，因此在處理時間上會更有效率。這種方法類似於對數運算，每次除以一個較大的數相當於對數運算中的一次除法。因此，在一定的情況下，<版本二>程式碼只需處理較少的位元，其時間複雜度可以表示為 $O(\log n)$，其中 $n$ 是輸入的數值。
#### <版本三>
在 [GCC, THE GNU Compiler Collection](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)中提到 GCC 提供一系列的 built-in 函數用來優化編譯結果，這些函數以```__builtin_```作為前綴，以下介紹一些 built-in 函數及其作用

* ```__builtin_clz(int x)``` : 傳回x中前導 0 位的數量（從最高有效位元位置開始）。如果x為 0，則結果未定義
* ``` __builtin_ctz(int x)``` : 傳回x中尾隨 0 位的數量（從最低有效位位置開始）。如果x為 0，則結果未定義
* ``` __builtin_ffs(int x)``` : 返回 x 中最後一個為 1 的位數

最高位元減掉 ```v``` 的前導 0 位的數量即為最高有效位元，程式碼如下:

int ilog32(uint32_t v)
{
    return (31 - __builtin_clz(v | 1));
}

在 ```__builtin_clz()``` 函數中引數若直接為 ```v``` ，多數情況下是對的，但由於此函數在 ```v``` 為0的情況下結果未被定義，因此該處應為``` v | 1```

### 測驗四

/* Exponentially weighted moving average (EWMA) */
struct ewma {
    unsigned long internal;
    unsigned long factor;
    unsigned long weight;
};

* ```internal```: 是用來儲存內部表示的加權移動平均值，會隨著新的輸出被加到 moving average 中而更新
* ```factor```: 用來表示 internal 的縮放倍率，掌控 internal 的精度。
* ```weight```: 代表輸出的權重，不同 weight 表示輸出對整體平均影響的大小。通常會被設定為 2 的冪使得計算有效率

/**
 * ewma_init() - Initialize EWMA parameters
 * @avg: Average structure
 * @factor: Scaling factor for the internal representation of the value. The
 *     highest achievable average is determined by the formula
 *     ULONG_MAX / (factor * weight). To optimize performance, the scaling
 *     factor must be a power of 2.
 * @weight: Exponential weight, also known as the decay rate, dictates the rate
 *     at which older values' influence diminishes. For efficiency, the weight
 *     must be set to a power of 2.
 *
 * Initialize the EWMA parameters for a given struct ewma @avg.
 */
void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight)
{
    if (!is_power_of_2(weight) || !is_power_of_2(factor))
        assert(0 && "weight and factor have to be a power of two!");

    avg->weight = ilog2(weight);
    avg->factor = ilog2(factor);
    avg->internal = 0;
}

根據 [Exponentially Weighted Moving Average](https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average) 得出以下公式 :


$$S_t = \left\{
           \begin{array}{l}
              Y_0&   t = 0 \\
              \alpha Y_t + (1 - \alpha)\cdot S_{t-1}& t > 0 \\
           \end{array} 
       \right.$$


在```ewma_add```函式中，首先判斷```avg->internal```是否有值，若```avg->internal```不為0，則進行以下操作(為了方便解釋，所有參數皆省略前綴```avg->```):

**func1** :　internal = (((internal << weight) - internal) + (val << factor)) >> weight

為了更好的與上述公式做連結我們粗魯地將上述運算再簡化成以下 :

**func2**： internal = ((internal - (internal >> weight)) + (val << factor) >> weight)
其中```weight```對應到 $\alpha$，```val << factor```對應到 $Y_t$

既然可以用更吻合公式的 **func2** 來編寫，為何此處會使用 **func1** 的方式?
是因為在進行 bit 右移運算時可能會導致最右邊的 bit 移失，導致精準度下降，事先左移 bits 可以改善這個問題

struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
avg->internal = avg->internal
- ? (((avg->internal << EEEE) - avg->internal) +
+ ? (((avg->internal << avg->weight) - avg->internal) +
- (val << FFFF)) >> avg->weight
+ (val << avg->factor)) >> avg->weight
: (val << avg->factor);
return avg;
}

### 測驗五

int ceil_ilog2(uint32_t x)
{
uint32_t r, shift;

x--;
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
return (r | shift | x > 1) + 1;
}

1. `x--`: 將 x 減1。這是因為如果 x 已經是2的冪次方，我們想要得到的 r 應該是 x 的對數，而不是對數加1。舉例來說，如果 x 是4（即`2^2`），我們想要得到的 r 是2。如果 x 是3或者4，減去1之後都會得到2，然後我們會找到2的對數是 1，最後函數會返回 1 + 1 = 2

2. 根據數值大小逐步縮小範圍，同時累計需要的 bit 移位數來表示對數 r， `r = (x > 0xFFFF) << 4;`: 判斷 x 是否大於`0xFFFF`（即`65535`）。如果是，`r` 被設置為`16`，否則為`0`。

3. 下面的步驟重複上述過程，但範圍更小，並逐步累積 r 的值：
   
   - `shift = (x > 0xFF) << 3;`: 檢查 x 是否大於 `255`（`0xFF`），如果是，shift 被設置為 `8`，否則為 `0`。
   - `x >>= shift`: 根據 shift 的結果，進一步右移 x。
   - `r |= shift`: 使用位元或運算（`|`），將 shift 的結果累加到 r 上

4. 最後一行 `return (r | shift | x > 1) + 1;`：
   
   - `r | shift`：將 r 和最後的 shift 結果進行位元或運算。
   - `x > 1`：如果經過所有的右移之後 x 大於1，表示還需要額外加1到結果中。
   - 最後，將這些結果加起來，並且加 1（因為我們在開始時將 x 減了1，現在需要把這個減掉的1加回來）。
#### 在 Linux 核心原始程式碼類似於```ceil_ilog2()```實作
[linux/tools/testing/selftests/mm
/thuge-gen.c](https://github.com/torvalds/linux/blob/master/tools/testing/selftests/mm/thuge-gen.c#L51)

函式通過不斷地左移 1 來找到給定數字，當 ```(1UL << l)``` 大於或等於給定的```v```時，迴圈停止運行。這意味著找到了最小的```l```值，此時的```l```即為原程式碼```ceil_ilog2(v)```的結果

int ilog2(unsigned long v)
{
int l = 0;
while ((1UL << l) < v)
l++;
return l;
}

Huge page 是作業系統中使用的一種記憶體管理技術。它們比標準記憶體分頁更大，通常是 2MB 或更大。

Huge page 的主要目的是提高記憶體管理效率和系統性能。在傳統的記憶體中，作業系統為每個進程維護一個 page，將 virtual address 映射到 pysical address。當存在大量的小 pages 時，頁表可能變得非常大，導致性能下降，因為作業系統花費更多時間在管理它們上。Huge page 減少了映射給定記憶體範圍所需的頁表項目數量，從而提高了效率。

#define SHM_HUGE_SHIFT 26

for (i = 0; i < num_page_sizes; i++) {
unsigned long ps = page_sizes[i];
int arg = ilog2(ps) << MAP_HUGE_SHIFT;

ksft_print_msg("Testing %luMB mmap with shift %x\n", ps >> 20, arg);
test_mmap(ps, MAP_HUGETLB | arg);
}

* 透過```ilog2(ps)```計算出每個 pages 大小，假設 pages 大小為 2MB，我們知道 $2^{21}B = 2MB$，因此其對數為 21
* ```SHM_HUGE_SHIFT```預設為 26，```<< MAP_HUGE_SHIFT```的目的是確保 huge page 大小可以正確地對應到虛擬記憶體的地址空間。
* ```test_mmap```函式用於測試在指定條件下是否能夠成功使用 huge page 進行內存映射