Try   HackMD

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_finalq_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;
    ​​​​}
    

    並化簡。

一對一討論

期末專案討論

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

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