執行人: Daniel-0224 任務簡介 重做第三次作業，並彙整其他學員的成果。 TODO: 以定點數實作 Monte Carlo tree search (MCTS) MCST（Monte Carlo Search Tree） 是一種搜尋樹的算法。它通常應用於決策問題的求解，特別是在棋類等遊戲中。MCST 通過隨機模擬和搜尋樹的擴展來評估每個可能的決策，以找到最佳的行動策略。 MCTS 在每一次的疊代一共會有 4 步，分別為： Selection ：

contributed by < Daniel-0224 > 測驗題改進 1.第三周測驗五 2.第四周測驗一 閱讀〈因為自動飲料機而延畢的那一年〉 :::danger 注意書名號 (即 〈 和 〉) 的使用，區分半形的小於和大於。 :::

contributed by < Daniel-0224 > 自我檢查清單 [x] 研讀前述 ==Linux 效能分析== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗; [x] 閱讀〈Linux 核心模組運作原理〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 insmod 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 strace 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？〈Linux 核心模組運作原理〉列出的程式碼較舊，歡迎編輯頁面，更新到 Linux v6.1 以上。 [ ] 閱讀《The Linux Kernel Module Programming Guide》(LKMPG) 並解釋 simrupt 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 lock-free;參照 2021 年的筆記。歡迎貢獻 LKMPG! $\to$ 搭配閱讀〈並行和多執行緒程式設計〉 [ ] 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 lib/sort.c 在排序過程中的平均比較次數，並提供對應的數學證明;對照 fluxsort 和 crumsort 的分析和效能評比方式 [ ] 研讀 CMWQ (Concurrency Managed Workqueue) 文件，對照 simrupt 專案的執行表現，留意到 worker-pools 類型可指定 "Bound" 來分配及限制特定 worker 執行於指定的 CPU，Linux 核心如何做到？CMWQ 關聯的 worker thread 又如何與 CPU 排程器互動？搭配閱讀《Demystifying the Linux CPU Scheduler》 [ ] 解釋 xoroshiro128+ 的原理 (對照〈Scrambled Linear Pseudorandom Number Generators〉論文)，並利用 ksort 提供的 xoro 核心模組，比較 Linux 核心內建的 /dev/random 及 /dev/urandom 的速度，說明 xoroshiro128+ 是否有速度的優勢？其弱點又是什麼？$\to$ 搭配閱讀: 不亂的「亂數」

contributed by < Daniel-0224 > 第三周測驗 測驗三 版本一 使用右移操作來計算 msb 在第幾位，以此當作 log 值，而計算 msb 也可以藉由計算 i 的 counting leading zero 來達成。 版本二 先判斷 i 是否大於 $2 ^ {16}$ ，若是則繼續往 i 是否大於 $2 ^ {24}$ 判斷，若不是則判斷 i 是否大於 $2 ^ {8}$ ，以此類推，原理其實就是二分搜尋，在32位元中找到 msb 。

contributed by < Dainel-0224 > Reviewed by david965154 這裡採取遞迴 merge_sort 來實作 q_sort 應該修改為 : 「這裡採取 merge sort 的遞迴版本來實作 q_sort 」較適當，加了底線會讓人誤以為你實作了這個函式，也應提到使用了下方函式 q_merge_two 完成 merge 的功能。 一開始想不到一個從頭走到尾的簡潔寫法，但在經過 HotMercury 及 devarajabc 的提醒，採取從尾走到頭的方式

contributed by < Dainel-0224 > 第一周測驗題 測驗一 :::danger 不用列出參考題解，專注於程式碼和你的洞見。 ::: :::danger 避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

DeadLine: 12/28 23:59:59 Submission Login the system by your personal account. (Use the ssh command) Create an directory with name “HW11” in your home directory.You can use the “pwd” command to confirm your current directory. The “mkdir [name]” command can create a directory with the name [name] In HW11 directory, you need to create 1 files with name “hw11.c” You need to compile your program by yourself, and create 1 executable files with the filenames “hw11”

contributed by < Daniel-0224 > Hello World in Chisel This code toggles an LED output based on a counter cntReg.LED change after CNT_MAX cycles. class Hello extends Module { val io = IO(new Bundle { val led = Output(UInt(1.W)) }) val CNT_MAX = (50000000 / 2 - 1).U;

contributed by < Daniel-0224 > Problem selet I choose the problem Output different number with same binary format by using counting leading zeros from classmate, 陳金諄. I believe I can enhance his assembly code. This classmate relies heavily on loops and branches to implement clz, which consumes a significant number of clock cycles. The origin code #include <stdint.h> #include <stdio.h> uint16_t count_leading_zeros(uint32_t x) {

Q1 : use pointer to implement swap #include <stdio.h> void swap(, ) { ///to-do/// } int main() { int a,b;

Q1 #include <stdio.h> void swap(int *x, int *y) { int tmp; tmp = *x; *x = *y; *y = tmp; }