owned this note
owned this note
Published
Linked with GitHub
# 2025-06-03 問答簡記
> 回顧 [2025-05-27 問答](https://hackmd.io/L8NQsV0SRwmbKyXSayizWw)
[身為一個資工系的學生，不可能依靠什麼AI寫作業的！](https://www.threads.com/@julia_ohya/post/DKJb7gcROL1?xmt=AQF0jND24YkqGX1UL14pB95GW_5b4zmcE-fZGnXzpvwRtw&fbclid=IwY2xjawKiyrRleHRuA2FlbQIxMABicmlkETFiM1Vmam1sRk1ZZklOUXcyAR7kC6f27PbCPgTVUhmMjSv7t3K0jP9-bgem5R2YotWMhhJbU1XDdgKUzTqA1w_aem_utcnSIDmKf4FGfkDJD78oA)
## 訊息回顧
* [Andes 與 Imagination 合作，在 QiLai RISC-V 系統整合晶片與 Voyager 開發板上成功執行 Android 15](https://www.facebook.com/groups/system.software2025/posts/1003901395279995/)
* [Arm 公司宣布將其沿用近二十年的 Cortex 處理器核心品牌汰除，改採 5 個依據應用情境劃分的新品牌](https://www.facebook.com/groups/system.software2025/posts/1003699465300188/)
* [在 CTHPC 2025 探討 shecc (Self-Hosting Educational optimizing C Compiler) 目前的成果](https://www.facebook.com/groups/system.software2025/posts/1003305168672951/)
* [semu 這款 RISC-V 系統模擬器正式獲得音效的支援](https://www.facebook.com/groups/system.software2025/posts/1003238725346262/)
* [Linux v6.16 的 CPU 排程器囊括多項修正與改進](https://www.facebook.com/groups/system.software2025/posts/1002147402122061/)
* [德國慕尼黑工業大學研究團隊發布 TPDE，針對 SSA 中間表示形式打造的高速編譯器後端框架](https://www.facebook.com/groups/system.software2025/posts/1002132575456877/)
* [RV32/Linux 的核心空間定址限制](https://www.facebook.com/groups/system.software2025/posts/999693629034105/)
* [在網頁瀏覽器中執行 CUDA，不需要 NVIDIA GPU](https://x.com/lauriewired/status/1930340695291900147)
## 烏克蘭稱無人機突襲三分之一俄境內戰略轟炸機
> [BBC 報導-1](https://www.bbc.com/zhongwen/articles/c1kvg24ddmxo/trad)
> [BBC 報導-2](https://www.bbc.com/zhongwen/articles/c5ykel5g57yo/trad)
> [解說-1](https://x.com/rickawsb/status/1929230289051550142), [解說-2](https://x.com/rickawsb/status/1929547679824027792)
> [This Open Source Software Was Used in Ukraine's Drone Attack on Russia](https://news.itsfoss.com/open-source-drone-attack/)
烏克蘭於 2025 年 6 月 1 日發動代號 Pavutyna (蜘蛛網) 的長程特別行動，宣稱在俄羅斯境內 5 座空軍基地同時出擊，擊毀或重創 41 架軍機，包含 Tu-95 戰略轟炸機 (蘇聯解體後，烏克蘭曾接收約 70 架原屬蘇聯空軍的 Tu-95 系列機，現已全部退役，而俄羅斯空軍接收的 Tu-95 系列機迄今仍在服役)、Tu-22M3 長程轟炸機 (蘇聯解體時該機種約有 370 架，於 1993 年停產，烏克蘭曾保有此機，現已退役) 與 A-50 空中預警機，估計損失逾 70 億美元。此舉被視為俄烏戰爭爆發以來最深入、最具規模的遠程打擊。
據稱，「蜘蛛網」行動耗時 18 個月籌畫，由烏克蘭總統澤倫斯基親自監督，烏克蘭安全局 (SBU) 局長 Vasyl Maliuk 與特種部隊主導執行。特戰人員先在境內博爾塔瓦博物館以舊蘇聯 Tu-95MS 與 Tu-22M3 實機進行 3D 掃描，建立 AI 訓練模型，再以 117 架 FPV 無人機分別由專屬操作員操控。無人機與彈藥被藏於偽裝成貨物的木製貨櫃，搭載在俄羅斯籍民用卡車中偷渡入境；車輛抵達預定位置後即作為臨時發射平台，直接在俄羅斯腹地放飛無人機。
遭到攻擊的基地分別位於伊爾庫茨克州貝拉亞、梁贊州季亞吉列沃、摩爾曼斯克州奧列尼亞、伊萬諾沃州伊萬諾沃，以及莫斯科州沃斯克列森斯克，最東端的貝拉亞距烏克蘭本土約 4300 公里，整體作戰範圍橫跨 5 個時區。SBU 指出，此次行動癱瘓俄軍約 34% 的戰略巡弋飛彈載具。
俄軍早前嘗試以輪胎覆蓋機身以干擾影像辨識，但烏克蘭 AI 仍能鎖定目標並精準攻擊。「蜘蛛網」行動顯示，低成本、高機動性的 AI 無人機足以對深層戰略目標造成實質威脅，而俄羅斯、美國乃至台灣等國的軍事與關鍵基礎設施防護思維，尚未跟上無人機戰術革新的速度。
消息人士稱，美國事前並未掌握此行動細節；美國總統川普第一時間亦聲稱毫不知情。由於無人機完全透過當地網路與 FPV 方式操控，再加上俄籍司機可能對載運內容一無所悉，此案無疑為無人機滲透作戰提供教材級示範，勢必在未來的軍事與 AI 發展史中佔有一席之地。
$\to$ [俄烏戰爭：可怕的新武器 —— 從無人機到光纖無人機，他們在頭頂盤旋](https://www.bbc.com/zhongwen/articles/c780v7mgpryo/trad)
$\to$ [淺談 Microkernel 設計和真實世界中的應用](https://hackmd.io/@sysprog/microkernel-design)
> 波音公司開發的 Unmanned Little Bird (ULB) 戰鬥直昇機
然而，對台灣防衛而言，無人飛行器的應用也難以忽視。光纖遙控無人機並非新創概念。數十年前拖式飛彈便採用線控方式，可靠度高，台灣今天仍在採購。2024 年底烏克蘭曾俘獲數架俄軍改裝機型，顯示這項技術正重新受到重視。纖細訊號線能避開無線電干擾，只要將發射車隱蔽在目標三到五公里內，再結合 AI 影像辨識，無人機即可低空自動突入並摧毀預設目標。
台灣軍事設施普遍座落於人口稠密區域，周遭道路與工業區密布。敵方若租用小貨車或物流車，在距基地三公里左右部署，防不勝防。中國籍可疑人士頻繁滲透、直播街景的現象，或許正是為尋找沒有高大障礙物的理想發射點。相較於烏克蘭必須偷渡無人機入俄境，台灣本地眾多中資企業即可協助寄送拆件，滲透門檻更低。
光纖無人機不依賴長距離飛行，而是暗中滲透後一次性攻擊。若敵方在我各大軍事基地周邊預藏小型自殺式無人機，屆時只需遠端發送命令便可齊發，低空慢速飛行也難以即時攔截，足以重創空軍基地與防空系統，為後續攻勢鋪路。
烏克蘭的「蜘蛛網」行動不僅改寫軍事史，也為全球敲響警鐘。低成本、抗干擾的光纖無人機正在重塑戰爭型態。台灣若不及時調整防禦邏輯，敵後潛伏的致命威脅恐在毫無預警下顯現。
---
### HBM4 邏輯晶片對人工智慧運算的關鍵影響
[JEDEC](https://www.jedec.org/) 於 2024 年中發布的 HBM4 初步規範，預示著記憶體介面寬度將倍增至 2048 位元，單堆疊頻寬有望達到每秒 1.6 TB，同時維持每秒 6.4 Gb 的 I/O 速率。這項技術的突破，也促成 SK 海力士與 NVIDIA 就第六代高頻寬記憶體 ([HBM4](https://en.wikipedia.org/wiki/High_Bandwidth_Memory)) 12 層堆疊的供應協商，預計 HBM4 產品將首次搭載於 NVIDIA 的 [Rubin 晶片](https://en.wikipedia.org/wiki/Rubin_(microarchitecture))。
然而，傳統僅負責實體層 (PHY) 和走線的 HBM 基底晶片 (base die) 已無法滿足如此高速運作下的時序裕度和訊號完整性要求。更甚者，HBM4 的設計變化，使其首度將部分對時序最敏感的記憶體控制功能，例如時脈同步、[錯誤校正碼](https://hackmd.io/@sysprog/r1wrjOp6a) (ECC) 前端處理和命令佇列管理，移轉到基底晶片上，並將資料傳輸 I/O 通道量增加一倍。
此舉使得資料往返路徑大幅縮短，有效降低抖動和串擾。同時，這項改變也明確要求導入先進邏輯製程才能提供的細緻金屬層和低 RC (電阻-電容) 佈線技術。由於 SK 海力士並無晶圓代工業務，這顆「邏輯化」的基底晶片，已確認將由台積電負責代工，採用其 7 奈米乃至更先進的 5 奈米以上製程節點。它將在台積電的 CoWoS (Chip-on-Wafer-on-Substrate) 矽中介層上，與 GPU 或 CPU 共同佈局，藉此由台積電協同改進整體佈線、供電與熱設計。
SK 海力士 2025 年第一季度在全球 DRAM 市場的占有率達 36%，略高於三星電子與美光的 34% 和 25%。這是 SK 海力士自 1983 年成立以來，首次在全球記憶體市場佔據主導地位。
> [SK海力士超越英特爾 登全球第三大半導體商](https://www.ctee.com.tw/news/20241011700175-439901)
將基底晶片從傳統的 DRAM 製程升級至先進邏輯製程，預計使其約佔整體 HBM4 模組成本的兩成。加上 2048 條矽穿孔 (TSV)、更多金凸塊及更為複雜的先進封裝技術，TrendForce 預估 HBM4 的每 Gb 價格將比 HBM3E 再上漲逾 30%，落在 2 至 2.5 美元區間。
鑑於台積電在高階邏輯製程領域近乎獨佔的地位，議價空間有限，這可能會壓縮 SK 海力士的毛利空間。然而，此舉也確保 HBM4 模組的性能與良率，以滿足 NVIDIA 和 AMD 等人工智慧客戶對高性能記憶體日益嚴苛的時程與標準。為鞏固其在 HBM 市場的領先地位 (市占率近 70%) ，並拉大與美光、三星在 HBM3E 競爭後的差距，SK 海力士正積極擴充 HBM4 產能，包括加速在南韓清州市 M15x 晶圓廠的 HBM4 產線建置。SK 海力士已於三月向主要客戶送樣 HBM4 並順利通過測試，儘管 NVIDIA Rubin 平台推出時程仍待最終確認，但其對 HBM4 12 層堆疊的市場前景充滿信心。
> [與台積電合作 HBM4 成本增 30%，SK 海力士獲利空間遭壓縮](https://technews.tw/2025/06/01/collaboration-with-tsmc-hbm4-costs-increased-by-30/)
大型語言模型 (LLM) 和生成式人工智慧 (Generative AI) 的運算瓶頸，已不再僅限於純粹的浮點運算能力 (FLOPS)，而是更顯著地轉向對記憶體頻寬與容量的需求。
例如， NVIDIA 的 [Blackwell B200 晶片](https://www.nvidia.com/zh-tw/data-center/dgx-b200/)搭配六顆 HBM3E 記憶體，便已能提供每秒 1.6 TB 的總頻寬。若未來 Rubin 等新一代 AI 晶片搭載 8 個 HBM4 堆疊，則單一 GPU 有望獲得超過每秒 13 TB 的聚合記憶體頻寬，這將是前所未有的飛躍。這將有效推動每秒產生單詞數 (token/s) 和模型訓練吞吐量的倍數成長，同時降低每瓦效能成本。
更重要的是，HBM4 的邏輯化基底晶片設計，使得高性能記憶體和邏輯半導體之間的界線日益模糊，因為其製造流程與前幾代不同，充當 HBM 晶片大腦的邏輯晶片必須交由晶圓代工公司而非記憶體製造商生產，從而可以整合更強大的運算功能。這也為[近記憶體運算](https://en.wikipedia.org/wiki/In-memory_processing) (Processing-in-Memory, PIM) 鋪平道路。未來，HBM 堆疊內部有望直接整合資料壓縮、簡易張量運算或 PIM 單元等功能，進一步緩解資料在處理器和記憶體之間搬移所耗費的巨大能耗，實現更高效的 AI 運算。此外，HBM4 也標誌著 HBM 技術朝向客製化市場發展的趨勢。
HBM 技術自推出以來持續演進，各代記憶體控制職責的分布與基底晶片製程如下表所示：
| 代別 | Pin 速率 (Gb/s) | 介面寬度 (bit) | 單一堆疊頻寬 (GB/s) | 記憶體控制職責 | 基底晶片製程 |
| --------- | ------------- | ---------- | ------------ | ----------------------------- | ----------------------- |
| HBM1 | 1.0 | 1024 | 128 | 記憶體控制器 (MCU) 全置於 GPU/CPU | DRAM 製程 |
| HBM2 | 2.4 | 1024 | 307 | 同上 | DRAM 製程 |
| HBM3 / 3E | 6.4 / 9.8 | 1024 | 819 / 1229 | 同上 | DRAM 製程 |
| HBM4 | 6.4 (草案) | 2048 | 約 1600 | PHY、時序敏感邏輯、部分ECC下放基底晶片 | 台積電 7 / 5 / 3 奈米 |
## 在台灣文學館看到電路圖
> [1990 年 11 月，陳之藩於波士頓大學電機工程學系為學生出的作業](https://cws.nmtl.gov.tw/home/zh-tw/083/2220346)
電路背景: 使用 二顆 74189 TTL RAM (每顆 16 × 4 bit，合計 128 bit) ，共用四條地址線 A0–A3 形成 8-bit 資料匯流排 D0–D7。
* WE、CE 皆低電位有效，輸出為反相信號 ($\bar Q$)
* 相關資料可參考 [74F189/74LS189 型錄](https://eater.net/datasheets/74189.pdf): 74F189 64-Bit Random Access Memory with 3-STATE Outputs"
記憶體預載資料
| Address | Data | Address | Data |
| ------- | ---- | ------- | ---- |
| 0H | EEH | 4H | FDH |
| 1H | 5CH | 5H | 15H |
| 2H | 26H | 6H | 94H |
| 3H | 6AH | 7H | C3H |
程式設計
* 於 8085 微處理器系統中，將 $5 + 4 - 6$ 之結果輸出至 I/O 埠 01H。
* 常數 $5, 4, 6$ 分別存放於記憶體地址 0DH、0EH、0FH。
機器碼對照
| Addr | Hex | Binary | 助憶碼 | 說明 |
| ---- | --- | -------- | ------- | ---- |
| 0000 | 3A | 00111010 | LDA 0DH | |
| 0001 | 0D | 00001101 | | Low |
| 0002 | 00 | 00000000 | | High |
| 0003 | 47 | 01000111 | MOV B,A | |
| 0004 | 3A | 00111010 | LDA 0EH | |
| 0005 | 0E | 00001110 | | Low |
| 0006 | 00 | 00000000 | | High |
| 0007 | 80 | 10000000 | ADD B | |
| 0008 | 47 | 01000111 | MOV B,A | |
| 0009 | 3A | 00111010 | LDA 0FH | |
| 000A | 0F | 00001111 | | Low |
| 000B | 00 | 00000000 | | High |
| 000C | 4F | 01001111 | MOV C,A | |
| 000D | 78 | 01111000 | MOV A,B | |
| 000E | 91 | 10010001 | SUB C | |
| 000F | D3 | 11010011 | OUT 01H | |
| 0010 | 01 | 00000001 | | 埠號 |
| 0011 | 76 | 01110110 | HLT | |
$\to$ [你我都是讀陳之藩長大的](https://www.cw.com.tw/article/5030920)
> 成大在 2009 年，發起「搶救陳之藩文物」行動，由中文系教授張高評負責，將其畢生文物做了博物館式的總整理之外，並請他在六十七歲到七十七歲這十年間，到成大擔任了十年的客座教授。
> [Wikipedia](https://zh.wikipedia.org/zh-tw/%E9%99%B3%E4%B9%8B%E8%97%A9)
---
## 與 LLM 對話：低階資料結構思維的較量
> [Human coders are still better than LLMs](https://antirez.com/news/153)
Salvatore Sanfilippo (社群暱稱 Antirez) 靠着直接操作 linked list、hash table、set 等底層結構，打造出以記憶體為核心、延遲毫秒級的 Redis。這種對低階資料結構的執着，源自他對傳統「表格／文件」資料模型的不適應；也正因如此，Redis 在資料庫領域開闢全新道路。
> 參見 [Redis 與作者 antirez 的故事](https://blog.brachiosoft.com/posts/redis/)
> $\to$ [高度並行的 Redis/Valkey 實作](https://hackmd.io/@sysprog/HyqlsB7Zxe)
近期他為 Redis 的 Vector Sets 修復錯誤：為加速 HNSW 圖的 RDB 序列化／反序列化，他把連結以整數 ID 存檔，於載入時解析為指標。資料若受損，可能留下「A 指向 B，但 B 不回指 A」的孤立邊 (orphan edge)，導致 use-after-free (UAF)。若要全面檢查互惠邊 (reciprocal edges) 的完整性，一個簡單的方法會需要 $O(N^2)$ 的時間複雜度，這對於大規模資料集不可行。在 2000 萬向量資料集的測試中，僅新增的邊檢查功能就使 RDB 載入時間從原先的 45 秒增長至總共 90 秒。
他詢問 Gemini 2.5 PRO：
* LLM 建議將鄰接指標排序後二分搜尋，但在 16 到 32 筆的小陣列上收益有限
* 他提出雜湊表方案：遇到連結 (A,B,level) 就插入，第二次見到即刪除，最後只要雜湊表非空就代表非對稱
* 進一步捨棄雜湊表，改用 128 位元暫存器，把 murmur128(seed‖A‖B‖level) 逐筆 XOR；互惠連結兩次抵消，暫存器若非零即有問題，碰撞機率極低且速度勝過先前方案
LLM 在過程中能充當「智慧自動完成功能」，快速驗證概念；真正突破瓶頸、跳脫常規的靈光，仍來自人腦。這也呼應開發者社群的隱憂：倘若新手僅複製 LLM 產生的程式碼而缺乏驗證、除錯與效能權衡的經驗，未來可能缺乏能晉升資深層級的人才，系統將更容易重演 [CrowdStrike 類型的災難](https://zh.wikipedia.org/zh-tw/2024%E5%B9%B4CrowdStrike%E5%A4%A7%E8%A7%84%E6%A8%A1%E8%93%9D%E5%B1%8F%E4%BA%8B%E4%BB%B6)。LLM 取代的不是具備深厚心智模型的工程師，而是重複性例行工作；真正的系統責任，也就是「從問題定義到創新演算法設計」，仍需工程師親自扛起。
向量資料集通常指把各種實體 (文字段落、圖片、聲音、使用者行為等) 轉換成位於 $\mathbb R^{d}$ 的高維向量後，集中儲存在記憶體或專門的向量資料庫，以便進行[近似最近鄰項目](https://scikit-learn.org/stable/modules/neighbors.html) (ANN) 查詢。當維度 $d$ 幾十到數百、總量動輒上億時，傳統掃描無法滿足延遲要求，因而催生 HNSW、IVF、PQ 等加速演算法。應用場景包括：
* 以語意相似度而非字面比對的全文檢索 (semantic search)
* 即時推薦與個人化：把使用者與商品投影到同一嵌入空間，快速取得「最相近的 $k$ 項」
* 多媒體去重、相似影像檢索、語音片段比對
* 監控資料的異常偵測或快速分群 —— 向量距離越大越可疑
* 隱私或安全需求下的「端側」推論，把模型執行濃縮到向量比對而非完整雲端推論
與 LLM 的關係相當密切。大型語言模型在推理時會把句子映射至長度數百的「語意嵌入」(embedding) 向量；若把文件庫先離線嵌入並存入向量資料集，推理階段即可用 ANN 查詢找出最相關段落，再把這些段落提供給 LLM 進行[檢索強化生成](https://en.wikipedia.org/wiki/Retrieval-augmented_generation) (RAG)。此外，LLM 也能當作特徵生成器：例如先用 LLM 判斷開發票據、醫療紀錄或程式碼片段的語意，再以向量搜尋翻譯對應規範、法律條文或範例程式。
在未損毀的 HNSW 圖中，每條無向邊 $(A,B,\text{level})$ 於序列化後必然以兩種方向存放，故載入時會掃到兩次。若我們把方向統一（較大指標在前），並計算
$$
H_S(A,B,\text{level}) \;=\; \text{Murmur128}\bigl(S\Vert A\Vert B\Vert \text{level}\bigr),
$$
再把所有雜湊值 XOR 累積到暫存器 $\Sigma$，則互惠完整時必有 $\Sigma=0$；若存在非互惠邊 (non-reciprocal edges) 的集合 $E_{orphan} \ne\varnothing$，就得到
$$
\Sigma'\;=\;\bigoplus_{e\in E_{orphan}} H_S(e).
$$
由於 $H_S$ 對未知種子 $S$ 近似均勻，固定非空 $E_{orphan}$ 滿足 $\Sigma'=0$ 的機率為 $2^{-128}$。即便邊數 $E\le 2^{32}$，使用聯集界估算全域誤判機率也僅 $2^{-96}$。對一般載入工作而言，單暫存器已充足；若仍需更嚴格保證，可用多個獨立種子並在 $k$ 個暫存器上累積，將誤判機率降至 $2^{-128k}$。
下方 C 程式碼僅依序掃描所有邊，不使用動態雜湊表:
```c
#include <stdint.h>
#include <stddef.h>
#include <string.h>
#include <stdio.h>
#include <inttypes.h>
/* 128-bit unsigned value */
struct u128 { uint64_t lo, hi; };
/* XOR two u128 values */
static inline struct u128 u128_xor(struct u128 a, struct u128 b)
{
a.lo ^= b.lo;
a.hi ^= b.hi;
return a;
}
/* Minimal MurmurHash3 (x64, 128-bit) specialized for 20-byte keys */
static struct u128 murmur128(const void *key, uint64_t seed)
{
const uint64_t c1 = 0x87c37b91114253d5ULL;
const uint64_t c2 = 0x4cf5ad432745937fULL;
uint64_t h1 = seed, h2 = seed;
const uint64_t *k = key; /* first 16 bytes */
uint64_t k1 = k * c1; k1 = (k1 << 31) | (k1 >> 33); k1 *= c2; h1 ^= k1;
h1 = (h1 << 27) | (h1 >> 37); h1 += h2; h1 = h1 * 5 + 0x52dce729;
uint64_t k2 = k * c2; k2 = (k2 << 33) | (k2 >> 31); k2 *= c1; h2 ^= k2; // Corrected: uint66_t -> uint64_t
h2 = (h2 << 31) | (h2 >> 33); h2 += h1; h2 = h2 * 5 + 0x38495ab5;
/* last 4 bytes: level */
uint32_t k3;
memcpy(&k3, (const uint8_t *)key + 16, 4);
uint64_t t = k3 * c1; t = (t << 31) | (t >> 33); t *= c2; h1 ^= t;
h1 ^= 20; h2 ^= 20;
h1 += h2; h2 += h1;
/* final mix */
h1 ^= h1 >> 33; h1 *= 0xff51afd7ed558ccdULL; h1 ^= h1 >> 33;
h1 *= 0xc4ceb9fe1a85ec53ULL; h1 ^= h1 >> 33;
h2 ^= h2 >> 33; h2 *= 0xff51afd7ed558ccdULL; h2 ^= h2 >> 33;
h2 *= 0xc4ceb9fe1a85ec53ULL; h2 ^= h2 >> 33;
h1 += h2; h2 += h1;
return (struct u128){h1, h2};
}
/* order the pair so that A >= B, making direction irrelevant */
static inline void normalize(uintptr_t *a, uintptr_t *b)
{
if (*a < *b) { uintptr_t tmp = *a; *a = *b; *b = tmp; }
}
/* return 0 if every edge is reciprocal, −1 otherwise */
int check_edges(const uintptr_t *from,
const uintptr_t *to,
const uint32_t *level,
size_t n, uint64_t seed)
{
struct u128 acc = {0, 0};
for (size_t i = 0; i < n; ++i) {
uintptr_t a = from[i], b = to[i];
normalize(&a, &b);
uint8_t buf; /* 8 B A, 8 B B, 4 B level */
memcpy(buf, &a, 8);
memcpy(buf + 8, &b, 8);
memcpy(buf + 16, &level[i], 4);
acc = u128_xor(acc, murmur128(buf, seed));
}
return (acc.lo || acc.hi) ? -1 : 0;
}
int main(void)
{
uintptr_t from[] = {0x1000, 0x2000, 0x2000, 0x1000};
uintptr_t to[] = {0x2000, 0x1000, 0x1000, 0x2000};
uint32_t lvl[] = {0, 0, 0, 0};
puts(check_edges(from, to, lvl, 4, 0xdeadbeef) ? "FAIL" : "PASS");
return 0;
}
```
藉此，載入 Redis RDB 時僅需一次線性走訪即可驗證所有連結。與傳統雜湊表法相比，時間複雜度相同為 $O(E)$，但常數係數更小；空間需求固定為 128 位元，加上用於處理單條邊的 20 位元組暫存緩衝區，不再受邊數影響。碰撞推估顯示，誤判機率已低至可忽略，且可透過多重種子再進一步降低。這使得 XOR 累積法成為高節點數、載入時間敏感場景的實用替代方案。
---
## tsaiiuo
```
(gdb) bt
#0 thread (ptr=0x1) at thread.c:8
#1 0x0000fffff7e7595c in start_thread (arg=0xfffff7ff8640) at ./nptl/pthread_create.c:447
#2 0x0000fffff7edba4c in thread_start () at ../sysdeps/unix/sysv/linux/aarch64/clone3.S:76
```
> 停在 glibc
threads/process 會遇到哪些相互影響執行 (順序) 的機制
- semaphore
- pthread_barrier，範例: https://gist.github.com/shelterz/4b13459668eec743f15be6c200aa91b2
- spinlock ==> 針對 shared lock / resource
- pthread_kill
- kill
- signal: 當呼叫 alarm(n) 後，等待 n 秒後，會觸發 SIGALRM 這個 signal，若 alarm 的參數為 0，則之前設置的 Timer 會被取消，並將剩下的時間返回。
- ... ?
- race condition (通常指「結果」)
```
gcc -o b pthread_barrier.c
watch -n 1 ./b
```
### TODO: 確保 `all sub threads ready, go!` 訊息總是最後面顯示
給定 ThreadA, ThreadB, ThreadC (或更多)，確保 ==執行順序== (結果！) 是 A -> B -> C
```c
// 不使用 barrier -> n+1 怎麼處理? 測驗對於同步處理的認知、用 barrier 但當通用時怎半
int stage =0; // turn
void *aa(){
// lock
while (stage != 0 )
wait;
stage = 1;
// unlock
}
void *bb(){
// lock
while (stage != 1 )
wait;
stage = 2;
// unlock
}
void *cc(){
// lock
while (stage != 2)
wait;
stage = 0;
// unlock
}
func()
{
// startup()
printf("A\n");
}
```
> EricccTaiwan
> TODO: 通用
更改後程式碼：
我最直觀的想法是新增一個 barrier 去讓 main 等待其他 threads 執行完成
```cpp
#include <stdio.h>
#include <pthread.h>
#define THREAD_NUMS 4
pthread_barrier_t start_barrier, print_barrier;
void *t0(void *param) {
pthread_barrier_wait(&start_barrier);
printf("t0 ready\n");
pthread_barrier_wait(&print_barrier);
}
void *t1(void *param) {
pthread_barrier_wait(&start_barrier);
printf("t1 ready\n");
pthread_barrier_wait(&print_barrier);
}
void *t2(void *param) {
pthread_barrier_wait(&start_barrier);
printf("t2 ready\n");
pthread_barrier_wait(&print_barrier);
}
int main(void) {
pthread_t t[3];
pthread_barrier_init(&start_barrier, NULL, 4);
pthread_barrier_init(&print_barrier, NULL, 4);
pthread_create(&t[0], NULL, t0, NULL);
pthread_create(&t[1], NULL, t1, NULL);
pthread_create(&t[2], NULL, t2, NULL);
pthread_barrier_wait(&start_barrier);
pthread_barrier_wait(&print_barrier);
printf("all sub threads ready, go!\n");
pthread_barrier_destroy(&start_barrier);
pthread_barrier_destroy(&print_barrier);
return 0;
}
```
Cracking the Coding Interview
### TODO: 考慮到 N + 1 個執行緒 (含 main thread)，要如何運用 pthread_barrier 達到特定順序？
以下是運用 pthread_barrier 在原先程式碼達到特定順序，主要是利用 Mutex Lock 的思路去撰寫程式碼，讓每個 pthread_barrier 的放行條件，設置成執行序本身前一個執行序和自己，這樣就能保證執行順序是正確的，並且每個 pthread_barrier 只需大小為 2 即可。
```c++
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define NUM_CHILDREN 3
pthread_barrier_t barrierA;
pthread_barrier_t barrierB;
pthread_barrier_t barrierC;
void *t0(void *arg) {
printf("t0 ready\n");
pthread_barrier_wait(&barrierA);
return NULL;
}
void *t1(void *arg) {
pthread_barrier_wait(&barrierA);
printf("t1 ready\n");
pthread_barrier_wait(&barrierB);
return NULL;
}
void *t2(void *arg) {
pthread_barrier_wait(&barrierB);
printf("t2 ready\n");
pthread_barrier_wait(&barrierC);
return NULL;
}
int main(void) {
pthread_t tid[NUM_CHILDREN];
int i;
// init three barriers
// barrierA wait for t0 + t1
// barrierB wait for t1 + t2
// barrierC wait for t2 + main
pthread_barrier_init(&barrierA, NULL, 2);
pthread_barrier_init(&barrierB, NULL, 2);
pthread_barrier_init(&barrierC, NULL, 2);
pthread_create(&tid[0], NULL, t0, NULL);
pthread_create(&tid[1], NULL, t1, NULL);
pthread_create(&tid[2], NULL, t2, NULL);
// last lock
pthread_barrier_wait(&barrierC);
printf("all sub threads ready, go!\n");
// wait for whole threads end
for (i = 0; i < NUM_CHILDREN; i++) {
pthread_join(tid[i], NULL);
}
// clean all barriers
pthread_barrier_destroy(&barrierA);
pthread_barrier_destroy(&barrierB);
pthread_barrier_destroy(&barrierC);
return 0;
}
```
那可以延伸到 N + 1 個執行緒的情境：
```cpp
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define NUM_CHILDREN N + 1
static pthread_barrier_t barriers[NUM_CHILDREN];
/*
barriers[0] for t0 and t1
barriers[1] for t1 and t2
…
barriers[N-1] for t(N-1) and t(N)
barriers[N] for t(N) and main
*/
static void *thread_func(void *arg) {
int idx = *(int*)arg;
free(arg);
if (idx > 0) {
pthread_barrier_wait(&barriers[idx-1]);
}
printf("t%d ready\n", idx);
pthread_barrier_wait(&barriers[idx]);
return NULL;
}
int main(void) {
pthread_t tids[NUM_CHILDREN];
int i;
for (i = 0; i < NUM_CHILDREN; i++) {
if (pthread_barrier_init(&barriers[i], NULL, 2) != 0) {
perror("pthread_barrier_init");
exit(1);
}
}
for (i = 0; i < NUM_CHILDREN; i++) {
int *pidx = malloc(sizeof(int));
if (!pidx) {
perror("malloc");
exit(1);
}
*pidx = i;
if (pthread_create(&tids[i], NULL, thread_func, pidx) != 0) {
perror("pthread_create");
exit(1);
}
}
pthread_barrier_wait(&barriers[NUM_CHILDREN - 1]);
printf("all %d sub threads ready, go!\n", NUM_CHILDREN);
for (i = 0; i < NUM_CHILDREN; i++) {
pthread_join(tids[i], NULL);
}
for (i = 0; i < NUM_CHILDREN; i++) {
pthread_barrier_destroy(&barriers[i]);
}
return 0;
}
```
但以上方法沒有考慮老師上課所講的情境：若有執行序被中途 kill 掉的話會導致後面的執行序無法順利執行，這部分尚未補充我的見解和尚未閱讀資料理解解決方法。
Peterson's algorithm
> Most modern CPUs reorder memory accesses to improve execution efficiency (see memory ordering for types of reordering allowed). Such processors invariably give some way to force ordering in a stream of memory accesses, typically through a memory barrier instruction. Implementation of Peterson's and related algorithms on processors that reorder memory accesses generally requires use of such operations to work correctly to keep sequential operations from happening in an incorrect order.
## EricccTaiwan (6/3)
給定 ThreadA, ThreadB, ThreadC (或更多)，確保 ==執行順序== (結果！) 是 A -> B -> C
```c
// 不使用 barrier -> n+1 怎麼處理? 測驗對於同步處理的認知、用 barrier 但當通用時怎半
int stage =0; // turn
void *aa(){
// lock
while (stage != 0 )
wait;
stage = 1;
// unlock
}
void *bb(){
// lock
while (stage != 1 )
wait;
stage = 2;
// unlock
}
void *cc(){
// lock
while (stage != 2)
wait;
stage = 0;
// unlock
}
func()
{
// startup()
printf("A\n");
}
```
> TODO: 通用
## Hande1004
lab0-c 用到 [alarm](https://man7.org/linux/man-pages/man2/alarm.2.html) 和對應的 signal handler 進行程式執行時間的檢查
TODO: 重新檢視程式碼流程 and 列出改進
## HenryChaing
以下是使用 Mutex Lock 這個機制達到執行緒之間預期的結果，可以看到每個執行緒都會等到上個事件發生才繼續執行，因此可以達到預期結果，但是未考量的點有二:
1. Memory Ordering (包含編譯器以及處理器的重排)
2. 若有執行緒被 kill (中止) ，則後續執行緒不會有進展。
```c
#include <stdio.h>
#include <pthread.h>
#define THREAD_NUMS 4
pthread_barrier_t start_barrier, print_barrier;
pthread_mutex_t a_lock, b_lock, c_lock;
void *t0(void *param) {
printf("t0 ready\n");
pthread_mutex_unlock(&a_lock);
}
void *t1(void *param) {
pthread_mutex_lock(&a_lock);
printf("t1 ready\n");
pthread_mutex_unlock(&b_lock);
}
void *t2(void *param) {
pthread_mutex_lock(&b_lock);
printf("t2 ready\n");
pthread_mutex_unlock(&c_lock);
}
int main(void) {
pthread_t t[3];
pthread_mutex_lock(&a_lock);
pthread_mutex_lock(&b_lock);
pthread_mutex_lock(&c_lock);
pthread_create(&t[0], NULL, t0, NULL);
pthread_create(&t[1], NULL, t1, NULL);
pthread_create(&t[2], NULL, t2, NULL);
pthread_mutex_lock(&c_lock);
printf("all sub threads ready, go!\n");
return 0;
}
```
編譯後即可執行 (未使用最佳化)
```
$ gcc test.c -o test
$ watch -n 1 ./test
```
---
## EricccTaiwan (6/5)
O(1) 的作法是建立 prio -> timeslice 數學嚴格定義 (X)
scx: sched_ext = scheduler extension
針對 gaming/entertainment (AR/VR): (tail) latency-sensitive
並非以 throughput 為主要考量: CFS/EEVDF (還要考慮到 fairness)
best-effort (盡力為之)
在 CFS/EEVDF 只是提高任務的 prio，只能變更 cgroup weight <--> timeslice
https://github.com/firelzrd/bore-scheduler
scx_lavd 分類 latency-sensitive vs. normal
Redis/Valkey (K/V store) 也是 latency-sentitive application
1. taskset 達到 CPU isolation，降低干擾
2. 降低同步處理帶來的開銷
有時不想用 isolcpu ? ==> 嚴重犧牲 throughput
https://wiki.linuxfoundation.org/realtime/documentation/howto/tools/cpu-partitioning/isolcpus
「快」是很含糊的概念
scx 有自己的 [scheduling class](https://elixir.bootlin.com/linux/v6.14.5/source/include/asm-generic/vmlinux.lds.h#L131)
scx: timeslice
scx 允許開發者決定 timeslice => 直接改變排程行為
FIFO scheduler
A B C
----------->| |------------->| |-------------->
將 timeslice 改為 UINT64_MAX
RR
|A|B|C||A|B|C|A|B|C|A|B|C|A|B|C|A|B|C|A|B|C
NVIDIA, Meta, Google, Alibaba, ...
https://hackmd.io/@sysprog/H1Eh3clIp
> 用統計的角度來分析 tail latency
用 scx 設定 affinity --> load balancing
```c
SCX_OPS_DEFINE(lavd_ops,
.select_cpu = (void *)lavd_select_cpu, // cpu
.enqueue = (void *)lavd_enqueue,
.dispatch = (void *)lavd_dispatch, // 裡面設 time slice
/* 省略 */
```
## HenryChaing
* Chain-of-trust （bois 檢查 bootloader, bootloader 檢查 Linux, Linux 檢查 File System）
* ioremap , mmap 需要 ==page alignment==. 讓 User space 可以存取需要 align !
* read, write 由核心實作，不一定與 mapping 相關。
Google Drive
Gist
Clipboard
Sign in with Wallet
