# 2024q1 Homework5 (assessment)
contributed by < `ICARUSHERALD96500` >
## 參照 2023 年期末專題，簡述你想投入的專案 (亦可建立新專案)，至少選出 (或訂出) 二個。
>參照 2023 年期末專題，簡述你想投入的專案 (亦可建立新專案)，至少選出 (或訂出) 二個。
:::danger
algorithm 是「演算法」，而非「算法」(the way you calculate)
>已訂正，會特別注意區別兩者
:::
因為實驗室相關的研究是機器人運動控制以及系統整合，演算法偏向深度學習、強化學習、啟發式演算法，所以這堂課的期末專題傾向和研究方向相關，在感測器與運動控制演算法間的並行程式設計是比較貼近目前實驗室需求，但礙於目前的能力還不足以處理相關的專案，因為根本看不出哪裡有地方需要改進。因此傾向先把上課所指派的作業完成以及閱讀指定教材，畢竟以學士班為機械背景修習這門課屬實是先備知識落差巨大。
1. 完成來不及做的作業 3
2. [bitwise operation](https://hackmd.io/@sysprog/BJBQgOZI2)
3. 紅黑樹改進
4. 並行程式設計
參照 2023年 的方式，回顧〈並行和多執行緒程式設計〉教材和相關測驗題，強化對延伸問題的掌握。
4. 有興趣但可能會眼高手低做不出來的酷東西-> [RTOS](https://wiki.csie.ncku.edu.tw/embedded/team2014-3)
## 閱讀〈因為自動飲料機而延畢的那一年〉與課程啟發
>資工系的學生不會寫程式，機械系的學生不會做機械
大學修過許多自動控制相關課程，大多為運動控制，許多課程在現行大學評分機制下都拿到不錯的成績。直到開始進行專題後發現，要將這些演算法透過電腦或是嵌入式系統實作出來我還缺少太多技能，甚至我控制演算法在離散狀態下的控制律在嵌入式系統運算時，是否符合當時離散化所開出來的取樣時間規格都無法確定。這也是一部分我來修這門課的原因。想當初驗證控制律時，總覺得用 matlab 輕鬆帶過，了解電腦底層的運行原理似乎與我無關，但當需要從底層開始驗證時卻自食苦果。因此我認為執行一個專題可以實際檢驗出自己還缺少那些能力，是檢查技能缺口很好的方法。
## 檢視前六周學習狀況
homework1: [M01: lab0](https://hackmd.io/@icarusherald/linux2024-homework1)
homework2: 重作並理解 quiz 1 ＆ quiz2 [M02: quiz 1+2](https://hackmd.io/@icarusherald/linux2024-homework2)
homework3:
homework4: [M04: quiz 3+4](https://hackmd.io/@icarusherald/linux2024-homework4)
## 問題
---
交互看 (X)
TODO: 紀錄 CPU sched book 閱讀過程中的問題
:::info
**問題**
>If a process does not complete its full timeslice before it is preempted, then
it goes back in the ready queue. If it does run to the end of the timeslice, it
is placed in the expired array instead.-> chap. 2.2.3
**為什麼會發生還沒到時間中斷而 process 就被搶佔?**
Linus $O(1) scheduler$ : active 與 expire array，當 process 進入 CPU 執行後，分為兩種情況:1.'If it does run to the end of the timeslice, it is placed in the expired array instead.'，該 process 在使用完被分配到的 CPU 時長後，遭到時間中斷，接著被放到 expire array 等待 priority 被重新調整。 2. 'process does not complete its full timeslice before it is preempted' ，此時 process 尚未完全使用所被分配到的 CPU 時長就遭到搶佔，但我目前不清楚有甚麼情況會發生還沒到時間中斷就被搶占。是 hardware 或 Exception Interrupt 嗎?
```graphviz
digraph ProcessState {
node [shape=ellipse];
// Define the nodes
New [label="New"];
Ready [label="Ready Queue"];
CPU [label="CPU"];
Expire [label="expire array"];
// Define the edges
New -> Ready [label="admit"];
Ready -> CPU [label="dispatch"];
CPU -> Expire [label="time Interrupt"]
CPU -> Ready [label="??preempted before time slice??"];
Expire -> Ready [label="A new priority is given"]
}
```
:::
:::info
**問題**
在閱讀[並行程式設計: Atomics 操作](/OVPTyhEPTwSHumO28EpJnQ)，關於 MESI 與 MOESI 兩種協定的差異，MOESI 相對於 MESI，將資料狀態 `shared` 拆解為，`Owner` 與 `Shared` 兩種。旨在避免每次發送 Probe read 讀到一個狀態為 Modified 的 cacheline 時，就要將資料更新回主記憶體，但將資料寫回主記憶體非常浪費時間。因此 MOESI 更改為發送 Probe read 並且 hit 之後，將 CPU0 cacheline 由 Modified 變為 Owner。
既然是要避免在 Probe read 遇到 `Modified` 時，將資料更新回主記憶體。為什麼不直接在 MESI 協議上直接取消該機制就好，反而需要新增一個 `Owner` 狀態。並且由 MOESI 協議的作法似乎不同 CPU 之間的 cacheline 可以互相存取，無須透過主記憶體。因此想請問若在 MESI protocol 當中直接取消每次發送 Probe read 讀到一個狀態為 Modified 的 cacheline 時，就要將資料更新回主記憶體的機制的影響是什麼？因為在教材舉例 MOESI protocol 中，就沒有寫回主記憶體。
>5. CPU1 想對 Block 0 進行讀取，它會發 Probe read 給 CPU0，接著 CPU0 會收到 Probe read hit，因為其 cache 中有 Block 0 的資料，CPU1 直接從 CPU0 讀取資料，並將其 cacheline 狀態設定成 Shared，而 CPU0 上的 cacheline 狀態則會從 Modified 變為 Owner。
>透過上述案例我們可發現，整個過程中並沒有涉及到任何將 cache 中資料更新回主記憶體的動作，因此，MOESI protocol 成功解決要將資料寫回主記憶體的問題。
:::
:::info
問題
在[並行程式設計: Hazard pointer](/1qjBY-JZR8GHCjQADDJdcQ) 當中提到下列程式碼，旨在取得non-active 狀態的 hazard pointer，但為什麼在 `if(p->active_||!CAS(&p->active_,0,1))` 會需要使用`p->active`、`!CAS(&p->active_,0,1)`兩種判斷式? 但其判斷的最終條件都是 `active==1`。
```c
// Acquires one hazard pointer
static HPRecType * Acquire() {
// Try to reuse a retired HP record
HPRecType * p = pHead_;
for (; p; p = p->pNext_) {
if (p->active_ ||
!CAS(&p->active_, 0, 1))
continue;
return p;
}
```
:::
Q-Learning 限制？
離散狀態空間
四元數可用來解決什麼問題？
解決尤拉角中兩座標軸重合導致歧異點
```c
#define FasI(f) (*((int *) &(f)))
[-----]
[----]
float *
|
dereference (value of, 針對 pointer type 進行操作)
```
> https://hackmd.io/@sysprog/c-pointer 記得看錄影
sizeof(int) = 4, sizeof(float) = 4 (常見狀況)
TODO: 閱讀 IEEE 754 規格書並找到 float/double 空間佔用的說法
> https://numeral-systems.com/ieee-754-converter/
In C, everything is a value.
float x = 7.5;
int y = (int) x; // rounding! y 變成 (int) 7.0
誠實面對自己
動手！
```c
#include <stdio.h>
#define FasI(f) (*((int *) &(f)))
int main()
{
float x = 7.5;
int y1 = (int) x, y2;
y2 = FasI(x);
printf("%d | %d", y1, y2);
}
```
float 7.0 => 01000000111000000000000000000000
int 7.0. => 00000000000000000000000000000111
https://godbolt.org/
TODO: 抱團取暖，通知授課教師關於二人同組的決定
>[XTree 改進與和紅黑樹及 AVL Tree 比較結果](https://hackmd.io/@icarusherald/linux2024-homework4)
## 實作浮點數乘法
由 IEEE 754 float/double 空間佔用的說明如下：
分為 1.Sign bit, 2.Exponent, 3.Mantissa 共三個部份
並且有三種模式：
1. Normalize: 1.x $\times 2{exp}$
可表示正數最接近 0 的範圍：$1.0 \times 2^{-126}$ $\approx$ $1.17549435\times10^{−38}$
可表示正數最大值：$1.0+(1−2^{−23}))\times2^{127}$ $\approx$ $3.4028235×10^{38}$
2. Denormalize: 0.x $\times 2{exp}$
可表示正數最接近 0 的範圍：$1.0 \times 2^{-126}$ $\approx$ $1.0\times10^{−45}$
可以表示的最小數值較 Nomalize 還小，用以解決 underflow 的情形
>underflow 指浮點數計算的結果小於可以表示的最小數。underflow 出現在計算結果很接近零，使得計算結果小於浮點數可以表示的最小數字。算術下溢也可以視為是浮點數指數在負值時的溢位。例如，浮點數指數範圍為 -128 至 127，一個絕對值小於 $2^{−127}$ 的浮點數就會造成下溢（假設 -128 用於表示負無窮
3. NaN & INF:
當無法用兩種標示方法時，如未定義的況下使用
依照浮點數表達方式分三種方法處理任意浮點數值 $\times 10$ 的問題
* Normalize
拆成 $\times2$ 與 $\times8$，所以僅須在指數部份，分別加 1 與加 3 的結果相加總
* Denormalize
`<<1` 變得以成兩倍。若 matissa 向左溢位到 exponent，後再將 sign bit 放。再`<<3` 變得$\times8$。最後再相加
* NaN & Inf
直接回傳即可
```c
float float_mul10(float x)
{
// using bitwise operation; No mul/div
unsigned uf = *(unsigned *)&x;
unsigned uf_sgn = (uf >> 31) & 0x01;
unsigned uf_exp = (uf >> 23) & 0xff;
if(uf_exp == 0){
unsigned uf_mul2 = (uf << 1) + (uf_sgn << 31);
unsigned uf_mul8 = (uf << 3) + (uf_sgn << 31);
float ans = *(float*) &uf_mul8 + *(float*) &uf_mul2;
return ans;
} else if(uf_exp != 0xff){
unsigned uf_exp_2 = uf_exp + 1;
unsigned uf_exp_8 = uf_exp + 3;
uf &= 0x807fffff;
unsigned uf_mul8 = uf + (uf_exp_8 << 23);
unsigned uf_mul2 = uf + (uf_exp_2 << 23);
float ans = *(float*) &uf_mul8 + *(float*) &uf_mul2;
printf("result: %f", ans);
return ans;
}
printf("%f", x);
return x;
}
```
參考 [youri1017](https://hackmd.io/@Yourui/linux2024-homework5) 的測試方法，設立 10000 筆資料，將自己實作的 float_mul10 和內建的浮點數乘法使用 perf stat 進行比較，並將浮點數的三種不同表示方法分開進行比較
Sign in with Wallet
Connect another wallet