2025q1 Homework5 (assessment)

contributed by < JeffBla >

「自動販賣機而延畢的那一年」的讀後感想

正所謂人不輕狂枉少年，故事中的主角和當初國中的我相似，也因為這樣，引領我的是電機資訊學系。因為的遊戲關服，而決定模仿這種遊戲，踏上學習 3d 建模動畫、unity、python、c#等旅程，最後雖然 3d 建模動畫還堪用，但因為過程難度太高與瑣碎而澆熄了熱情，最後每個都會但，沒有把他們拼在一起，以失敗告終。那時的我貫徹一種精神，有些事情真的好難，我缺好多東西，我要把這些難題交給未來的我。就這樣，目前的我雖未完成這件事，但箇中原理現在的我已清楚知曉，大二的暑假，捨棄熟習的 unity，踏上 unreal 的旅程，我總稱它無字天書，因為文檔什麼也沒有，很多時候靠的是實驗與查資料，而 3d 模型的問題，也不再像小時候，每件事情都從重新造輪子，靠的是金錢的力量與修改別人檔案的本事。

很佩服作者找資源的本事，協調、還價與向人請教。目前的我還在重新找尋那種感覺，那種突破點，就像自動販賣機是作者想做的事情，是作者的青春，國中的我模仿已關服遊戲與製作 8 足機器人（在大三時利用 pic18f 重現了）是我的青春，而現在的我找不到在軟體的定位，唯一還算得上的是大三專題：AI 個人教練：結合電腦視覺在三維空間中呈現，並基於姿勢分析給出建議，也因此進入到交大的圖學與互動實驗室（目前大四）。奇怪的是，這些都符合我的興趣，也符合我的動機，但我的目標仍然不清楚，目前只是朝著我認為的未來機會與興趣，如：3d、多平行，發展。

這篇文章提醒了我對知識的貢獻與學習方法以及義無反顧的目標，我應該利用大四的剩餘時光，好好的重新審視。

前 6 週學習狀況

~~前六周教材進度大致有跟上，看完相關內容。作業未能撰寫完善，大多有缺漏沒有完成~~

不要書寫含糊的話語，紀錄你的問題！

在你所不知道的 C 語言：編譯器和最佳化原理篇有提到程式執行流程，介紹 ELF 但卻沒有他和程式執行流程的關聯，對我來說，ELF 只是一個儲存資訊的檔案，實際如何 execve 一無所知。因此進一步觀察，利用 objdump 與 readelf 搭配 chatgpt 了解 ELF 如何被載入、配置。

在並行程式設計: Atomics 操作中無法重現在 x64 與 aarch64 上：

int a = 0, b = 0;
void foo(void)
{ 
    a = 1; 
    b = 1;
}

void bar(void)
{ 
    while (b == 0)
        continue; 
    assert(a == 1);
}

而感到疑惑，並將所找資料記錄。
為了確認 cpu 有 out of order execution.
其在

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

static int loop_count;
static int A, B, X, Y;

static void *worker1(void *arg)
{
    X = 1;
    asm volatile("" ::: "memory");
    A = Y;
}

static void *worker2(void *arg)
{
    Y = 1;
    asm volatile("" ::: "memory");
    B = X;
}

int main(int argc, char *argv[])
{
    pthread_t thread_1, thread_2;

    int64_t count = 0;

    if (argc != 2) {
        fprintf(stderr, "USAGE: %s <loop_count>\n", argv[0]);
        exit(1);
    }

    loop_count = atoi(argv[1]); /* FIXME: format checks */

    for (int i = 0; i < loop_count; ++i) {
        X = 0;
        Y = 0;

        /* Start the threads */
        pthread_create(&thread_1, NULL, (void *(*) (void *) ) worker1, NULL);
        pthread_create(&thread_2, NULL, (void *(*) (void *) ) worker2, NULL);

        /* Wait for the threads to end */
        pthread_join(thread_1, NULL);
        pthread_join(thread_2, NULL);

        if (A == 0 && B == 0) /* reorder caught */
            count++;
    }

    printf("%d reorder caught in %d iterations.\n", count, loop_count);

    return 0;
}

等待一段時間後，會出現 out of order execution，之後，將目光放在 store buffer 上，也許 store buffer 停住，沒有運作？在 The microarchitecture of Intel, AMD, and VIA CPUs - An optimization guide for assembly programmers and compiler makers 確實說明 store buffer 會失效的情況，但上述程式碼並非失效的情形，因此為何該程式碼實驗沒有達成預期仍需進一步討論。

程式碼貢獻

[cling] Refine build and usage guide

fix typo in〈Demystifying the Linux CPU Scheduler〉

隨堂測驗和作業回顧

lab0

完成事項

完成 queue.c 的函式功能實現
追蹤並修改 dudect 的程式
追蹤 list_sort 的程式，並且嘗試理解它更有效率的原因

問題

和 weiso131 討論 merge_final 與 q_merge 的作法並參考 kdnvt的研讀 lib/list_sort.c筆記。在 list_sort.c 中提到：

/*
 * Combine final list merge with restoration of standard doubly-linked
 * list structure.  This approach duplicates code from merge(), but
 * runs faster than the tidier alternatives of either a separate final
 * prev-link restoration pass, or maintaining the prev links
 * throughout.
 */

其說明了 merge_final 會較快於其他兩個方法，這解釋了為何自己實作的 merge_final 會較差。

對於 dudect，程式碼的執行時間在不同類別有不同的執行分布，而其利用 t 檢定，希望兩者的平均數相近，若不符合前述，則判斷為非常數時間演算法。然而若將兩類別的分布畫出來，可以發現其平均數差異，如下圖。
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
與 weiso131 討論後發現，他們找到問題的原因： malloc 時間與 input_data 的關聯 - weiso131

kxo

完成事項

利用 bit 儲存棋盤資料
將 draw_board 移至 user space
將 select-based I/O 換成 coroutines 處理

quiz1+2

改進 random_shuffle_array

在從 √2 的存在談開平方根的快速運算遇到問題，不理解 Digit-by-digit Method 是如何寫成下列程式碼：

uint64_t sqrt_ceil(uint64_t x)
{
    uint64_t m, y = 0;
    if (x <= 1)
        return x;

    int total_bits = 64;

    int shift = (total_bits - 1 - clz64(x)) & ~1;
    m = 1ULL << shift;

    while (m) {
        uint64_t b = y + m;
        y >>= 1;
        if (x > b) {
            x -= b;
            y += m;
        }
        m >>= 2;
    }
    return y + 1;
}

在看了 rota1001 的筆記知道是從原本的數學式寫成程式碼：

uint64_t sqrti_simple(uint64_t x)
{
    uint64_t m, y = 0;
    if (x <= 1)
        return x;

    int total_bits = 64;
    int shift = (total_bits - 1 - clz64(x)) & ~1;

    uint64_t p = 0;
    for(int i = (shift / 2); i >= 0; i--) {
        uint64_t b = (p << (i + 1)) + (1 << (2 * i));
        if (x >= b) {
            x -= b;
            p += (1 << i);
        } 
    }
    return y;
}

並化簡。

一對一討論

2025年4月30日

期末專案討論

對於並行程式設計有興趣，但覺得並行程式設計: Atomics 操作的材料過於零散沒有一個很好的組織與實作，展現實際 atomic 、 store buffer 、fence 等操作，讓我有學到，但還是一知半解，不知道怎麼使用，甚至覺得這真的會發生嗎？以及誰寫程式會這麼複雜的想法？

另外， ktcp 中的 kernel thread 與 CMWQ ，對我來說也是很好的教材，也許可以從中讓我認識並行程式的實際案例。在 ktcp 的講解中提到 CMWQ 提升了接近一倍的 throughput ，那如果不只是多執行緒，甚至多台電腦溝通，效果會如何？

Jim Huang

2025/04/30 07:41:42

載入

搭配使用 strace 和 bpftrace 工具

2025/04/30 07:43:59

無法重現

在現代處理器上，reorder 很難在少數的步驟立刻發現，因此有 https://www.kernel.org/doc/Documentation/litmus-tests/README

2025/04/30 07:45:37

搭配閱讀: I/O ordering 學習紀錄 https://hackmd.io/@butastur/rkkQEGjUN

2025q1 Homework5 (assessment)

「自動販賣機而延畢的那一年」的讀後感想

前 6 週學習狀況

程式碼貢獻

隨堂測驗和作業回顧

lab0

完成事項

問題

kxo

完成事項

quiz1+2

一對一討論

期末專案討論

Read more

2025年4月30日 一對一討論

OpenGL NCKU HW3

How ELF exec

Concurrency Study – SPMC

2025年4月30日一對一討論