Try   HackMD

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 )

迭帶次數 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
22
4 2 4 True
22
+
21
5 1 6 False
22
+
21
+
20

<版本二>

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

<版本三>

測驗二

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

測驗三

<版本一>

透過不斷右移來判斷 i 是否為零,為了找到最高有效位元

<版本二>

按照順序判斷 i 是否大於

216
28
24
22
,若有則將該冪加到 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(logn),其中
n
是輸入的數值。

<版本三>

GCC, THE GNU Compiler Collection中提到 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;
}

ewma_int在資料初始化的過程順勢將avg->weightavg->factor 都取了

log2,方便在之後透過位移avg->weightavg->factor的方式達到更好的運算效果

根據 Exponentially Weighted Moving Average 得出以下公式 :

St={Y0t=0αYt+(1α)St1t>0

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對應到

αval << factor對應到
Yt

既然可以用更吻合公式的 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 是否大於 2550xFF),如果是,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

函式通過不斷地左移 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,我們知道
    221B=2MB
    ,因此其對數為 21
  • SHM_HUGE_SHIFT預設為 26,<< MAP_HUGE_SHIFT的目的是確保 huge page 大小可以正確地對應到虛擬記憶體的地址空間。
  • test_mmap函式用於測試在指定條件下是否能夠成功使用 huge page 進行內存映射