###### tags: `Linux`
# 2023q1 Homework3 (fibdrv)
contributed by < [`shhung`](https://github.com/shhung) >

## 實驗環境

shhung@shhung-MSI:~$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

shhung@shhung-MSI:~$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            12
    CPU max MHz:         4200.0000
    CPU min MHz:         400.0000
    BogoMIPS:            4199.88
    Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush 
                         dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_ts
                         c art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf
                          pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm p
                         cid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdra
                         nd lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single ssbd ibrs ibpb stibp
                          ibrs_enhanced tpr_shadow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adjust 
                         bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt intel_pt xsaveop
                         t xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hw
                         p_epp md_clear flush_l1d arch_capabilities
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   128 KiB (4 instances)
  L1i:                   128 KiB (4 instances)
  L2:                    1 MiB (4 instances)
  L3:                    6 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-7
Vulnerabilities:         
  Itlb multihit:         KVM: Mitigation: VMX disabled
  L1tf:                  Not affected
  Mds:                   Not affected
  Meltdown:              Not affected
  Mmio stale data:       Mitigation; Clear CPU buffers; SMT vulnerable
  Retbleed:              Mitigation; Enhanced IBRS
  Spec store bypass:     Mitigation; Speculative Store Bypass disabled via prctl
  Spectre v1:            Mitigation; usercopy/swapgs barriers and __user pointer sanitization
  Spectre v2:            Mitigation; Enhanced IBRS, IBPB conditional, RSB filling, PBRSB-eIBRS SW sequenc
                         e
  Srbds:                 Mitigation; Microcode
  Tsx async abort:       Not affected

## 開發紀錄
- [x] fibonacci 初步支援大數運算
- [ ] 初步分析計算效率
- [ ] 改進 Fibonacci
- [ ] 比較改進後之算法
- [ ] 完善大數運算以支援改進後的 Fibonacci

## 開發過程

### fibonacci 支援大數

參考 [數字字串](https://github.com/AdrianHuang/fibdrv/tree/big_number) 的作法，以字元陣列的方式表示大數，使 Fibonacci 在 $Fibonacci(92)$ 之後也能正確運算

typedef struct {
    char *number; 
    unsigned int size; // digits of number
} stringNum;

結構中包含指向數字的指標並紀錄目前位數

#### 加法實作
- 確保 a 字串長度大於 b 字串
- 將 a 與 b 字串反轉
- 逐字對數字字元做加法運算
- 將得出字串反轉，即得出最終結果

改進後可正確計算到 $Fibonacci(500)$

shhung@shhung-MSI:~/linux2023/fibdrv$ sudo ./client 
...
Reading from /dev/fibonacci at offset 497, returned the sequence 32913358638779021325852241460922292241811880064424459384950843991972540608783894735358997476926373114877.
Reading from /dev/fibonacci at offset 498, returned the sequence 53254932961459429406936070704742495854129188261636423939579059478176515507039697978099330699648074089624.
Reading from /dev/fibonacci at offset 499, returned the sequence 86168291600238450732788312165664788095941068326060883324529903470149056115823592713458328176574447204501.
Reading from /dev/fibonacci at offset 500, returned the sequence 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125.

---

### 初步分析計算效率
首先將作業中提到的三種方法做效能分析，分析方法主要為量測 Fibonacci 在 kernel 的計算效率，並以作業說明中提到的統計方法去除 95% 區間之外的值
- 透過 python scripts 執行50次並去除異常值後再取平均

#### 觀察
- naive 的做法在某些特定值震盪得大，其餘時候則循序上升
- fast doubling 則是固定的反覆震盪，推測跟奇偶數的計算有關，需要再深入研究
- 優化後的 iterative fast doubling 則有穩定的執行時間

#### 統計手法去除極端值
使用 [作業說明](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-c) 提到的方法來做處理

`datas` 的資料為計算某個 fibonacci number 的時間，並用此手法去除 95% 區間之外的值
- 其中 `z` 代表某個 sample 距離 mean 幾個標準差

def outlier_filter(datas, threshold = 2):
    datas = np.array(datas)
    z = np.abs((datas - datas.mean()) / datas.std())
    return datas[z < threshold]

處理計算每個 Fibonacci number 的時間，最後返回處理好資料 (去除 outlier 再取平均)

def data_processing(data_set, n):
    catgories = data_set[0].shape[0]
    samples = data_set[0].shape[1]
    final = np.zeros((catgories, samples))

    for c in range(catgories):        
        for s in range(samples):
            final[c][s] =                                                    \
                outlier_filter([data_set[i][c][s] for i in range(n)]).mean()
    return final

#### 限定 CPU 給特定的程式使用
依照 [隔離 cpu](https://blog.csdn.net/tang05505622334/article/details/96477552)的步驟將 cpu 0 保留作為實驗

使用 `taskset` 查看 affinity mask

shhung@shhung-MSI:~$ taskset -p 1
pid 1's current affinity mask: fe

輸出結果為 `fe` 轉換成二進位為 `1111 1110`，而我在 GRUB 設定檔中設定為 `isolcpus=0`，也就是保留第 0 個 cpu，因此輸出結果符合預期。

接下來就可以透過 `taskset` 來使用特定核心執行指定的程式

$taskset COREMASK EXECUTABLE

---