# 2024q1 Homework4 (quiz3+4)
contributed by < `aa860630`>
## 第 3 週測驗題
### 測驗一
#### <版本一>
先是使用 $log$ 來找最高有效位數(```a```)，判斷 ```result + a``` 平方是否小於等於 N 的同時，不斷透過位移 ```a``` 與運算 ```result+a``` 的方式逼近 N
```c
#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``` 為最高有效位元
```c
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 位的數量即為最高有效位元，程式碼如下:
```c
int ilog32(uint32_t v)
{
return (31 - __builtin_clz(v | 1));
}
```
在 ```__builtin_clz()``` 函數中引數若直接為 ```v``` ，多數情況下是對的，但由於此函數在 ```v``` 為0的情況下結果未被定義，因此該處應為``` v | 1```
### 測驗四
```c
/* 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 的冪使得計算有效率
```c
/**
* 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;
}
```
```ewma_int```在資料初始化的過程順勢將```avg->weight```與```avg->factor ```都取了 $log2$，方便在之後透過位移```avg->weight```或```avg->factor```的方式達到更好的運算效果
根據 [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 可以改善這個問題
``` diff
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;
}
```
### 測驗五
```c
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)```的結果
```c
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 減少了映射給定記憶體範圍所需的頁表項目數量，從而提高了效率。
```c
#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 進行內存映射
Sign in with Wallet
Connect another wallet