2024q1 Homework4 (quiz 3+4)

contributed by < otteryc >

第三次小考

測驗一

在第一個版本中，先透過 math.h 中的 log2 函式找出數字的最高有效位，然後再透過時間複雜度為

$O(lo{g}_{2}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;
}

而在第二個版本中，透過了一個 while 迴圈來除去對於 math 函式庫的相依性。

-    int msb = (int) log2(N);
+    int n = N;
+    while (n > 1) {
+       n >>= 1;
+       msb++;
+   }

測驗二

測驗三

測驗四

EWMA 在 Linux 核心中的應用

Kernel Samepage Merging (KSM) is a Linux kernel module for improving memory utilization by searching and merging the redundant memory pages. When working with the hypervisors, such as Kernel-based Virtual Machine, KSM helps share identical memory pages of the hosted virtual servers so as to increase the server density. Nevertheless, while KSM improves the efficiency of the host system, it hurts the performance of the virtualized systems since part of the CPU cycles is spent on exploring the page sharing opportunities.
Wei-Cheng Lin, Chia-Heng Tu, Chih-Wei Yeh, Shih-Hao Hung, "GPU acceleration for Kernel Samepage Merging," 2017 IEEE 23rd International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), Hsinchu, Taiwan, 2017, pp. 1-6

由於 ksmd 會使用 CPU 資源，而且只有在應用程式啟動時，所需要掃描的記憶體分頁數量才會變多。根據 Linux 核心文件 KSM 的 Advisor 被用來動態的分析，藉以根據需求調整掃描強度。
在 mm/ksm.c 中，EWMA 被用來避免所估算的掃描時間被異常值擾動。
在閱讀 KSM 程式碼的時候，有發現文法上的謬誤，並已經提交 PATCH 。

@@ -385,7 +385,7 @@ static unsigned long ewma(unsigned long prev, unsigned long curr)
  *
  *      new_pages_to_scan = pages_to_scan * (scan_time / target_scan_time)
  *
- * To avoid perturbations it calculates a change factor of previous changes.
+ * To avoid perturbations, it calculates a change factor of previous changes.
  * A new change factor is calculated for each iteration and it uses an
  * exponentially weighted moving average. The new pages_to_scan value is
  * multiplied with that change factor:

後來這個 PATCH 被 Andrew Morton 拒絕了。

測驗五

ceil_ilog2 與 ilog2 的差別在於，兩者分別對以二為底 log 所得的小數，取上高斯與下高斯，亦即，當輸入整數為 5 (0b101) 時，前者回傳的是 3 而後者是 2 。
原本題目是用二分搜尋來實作 ceil_ilog2 ，考慮到取上高斯時，如低於最高有效位 (a.k.a. MSB) 的任意位元為 1 ，即可進位， ceil_ilog2 的實作可以簡化成：

int ceil_ilog2(int x) {
    __uint32_t r = 31 - __builtin_clz(x);
    x ^= 1 << r;
    return r + (x != 0);
}

但是，這樣的實作方式，仍然不能解決傳入整數是 0 時的狀況。