###### tags: `os2020`

# OS2020 HW1 - Benchmark Computer Black Box

> 學號：E14056431
> 姓名：趙珈葦
> 系級：機械109

## 開發環境

* OS: Ubuntu 16.04 LTS
* CPU: Intel® Core™ i7-6700 CPU @ 3.40GHz × 8
* Memory: 16 GB
* Programming Language(version): C (GCC-5.5.0)

## 程式執行時間

1e8 筆資料排序(0.4G)：37.754134 秒
2e8 筆資料排序(0.8G)：87.050632 秒

## 程式開發與使用說明

### 開發功能

#### External Sorting
由於輸入資料可能大於記憶體容量，因此本支程式採用 External Sorting 進行排序。

簡單說明其原理，當檔案大小超過記憶體容量時，由於無法單次將所有內容寫入記憶體，因此先將原檔案拆分成數份記憶體可容納大小，依序把每一份讀入並排序完，再將其先寫入硬碟中儲存，待所有數據皆處理完成後再行合併。

#### Merge Sort
External Sort 中的單筆資料排序並沒有指定排序方式，考量若欲提高執行效率，單筆分割資料中的數據數量亦可能仍非常大，因此選擇時間複雜度 $O(nlogn)$ 的 Merge Sort。

#### K-Merge & Heap Sort
External Sort 最後的檔案合併以 K-Merge 演算法處理，即以多通道已排序數列，不斷取最小值更新目標數列來完成數列合併，程式中便是以各檔案的輸入取代上述已排序數列。

並且在未知記憶體上限及輸入資料數量的情況下，須合併的檔案數量可以非常大，因此仍須一有效率的演算法比較每個檔案最新輸入值的大小。程式中使用 Heap Sort，首先將各輸入第一數排序完成，取完最小數後讀取新值取代 root，並重新排序更新數列，重複動作至每一檔案讀完為止。

#### 執行流程圖：

digraph progress{
    rankdir=LR;
    input [label="input.txt" shape="box"];
    sort [label="Partition & Merge Sort"];
    "part_1.txt" [shape="box"]
    "part_2.txt" [shape="box"]
    "..." [shape="box"]
    merge [label="K-Merge"];
    output [label="output.txt" shape="box"];
    
    input -> sort;
    sort -> "part_1.txt";
    sort -> "part_2.txt";
    sort -> "...";
    "part_1.txt" -> merge;
    "part_2.txt" -> merge;
    "..." -> merge;
    merge -> output
}

### 執行方式

#### Build with `build.sh`

# At root directory of benchmark
$ bash ./build.sh

# It'll generate two executable files at current directory - sort & datagen

#### Build single program

# At root directory of benchmark

# Data generator
$ cd data_generator && make && cd ..

# Sorting program
$ cd sorting && make && cd ..

#### Implement
產生測試資料：

# Generate input data
$ ./datagen [number_of_data] [target_file]

# ex. 
# ./datagen 1000 input.txt
# It'll generate a file "input.txt" which contains 1000 random numbers

排序資料：

# Sort
$ ./sort [input_file]

# ex.
# ./sort input.txt

## 效能分析報告

### 單一執行工作最佳化

#### 檔案讀寫
由於輸入數據量龐大，且 External Sort 演算法的讀寫需求次數亦高，若選擇較具效率的方式執行應能降低一定程度的執行時間，因此在此針對檔案讀寫個別撰寫三種方式測試。

* 寫出：寫出 $5*10^6$ 個 32-bit 整數至一輸出檔 ([Github](https://github.com/chwchao/Course-OS2020/tree/master/benchmark/measurement/write_file))
* `fprintf`：0.302281 秒
* `sprintf` + `fputs`：380.977516 秒（1.3e6 * 8-bit char buffer）
* `fwrite`：0.007645 秒 （1e6 * 32-bit int buffer）

前兩項測試輸出檔為 txt 文字檔，可看出僅使用 `fprintf` 在此處效果較佳。
論純字串寫入速度理應 `fputs` 較 `fprintf` 佳，但由於寫入內容為數字，須先經由 `sprintf` 轉換，反而拖慢整體速度，因此在程式最終輸出 `output.txt` 的實作使用 `fprintf` 輸出。

而 `fwrite` 表現效率較其餘兩者高出許多，但輸出格式為 binary 檔，並不符合程式功能要求的文字格式，然而在 External Sort 中仍有分割檔案儲存的需求，此時並不限輸出格式，因此本實作利用 `fwrite` 作為中間運算的加速手法。

* 讀入：讀入 $5*10^6$ 個 32-bit 整數至一輸出檔 ([Github](https://github.com/chwchao/Course-OS2020/tree/master/benchmark/measurement/read_file))
* `fscanf`：0.513792 秒
* `fgets` + `atoi`：0.230732 秒
* `fread`：0.003187 秒（ 1e6 * 32-bit int buffer）

前兩項測試輸入檔為 txt 文字檔，由於 `fscanf` 內部做較多 formatting 處理，因此速度較慢，因此程式中使用 `fgets` 和 `atoi` 的組合實作輸入檔案的讀取。

而 `fread` 為 binary 檔的讀取函式，速度最快，上述提到 External Sort 的分割檔案可以 `fwrite` 儲存為二進位檔加速，並可再利用此方式將值讀回，因此分割檔的讀取以 `fread` 進行實作。

### 整體效能觀察

此為單一執行緒的執行狀況 (perf)：


可以看到除此排序程式中的遞迴函式 `merge` 所佔比例最高，其餘占比較高的另有字串轉換數字 (`strtoll`) 及寫檔 (`fprintf` & `vfprintf`)，另外演算法中亦有 `heapify` 函式佔至 6%。

對於內容的讀寫在上方已經由測試程式驗證過，程式中已是使用較具效率的方式執行，這部份已是優化完結果，因此將優化目標著重於 `merge` ，即數據排序的動作。

在單一執行緒執行時，由於各分割檔是讀取完成、排序、最後儲存，然而若每個檔案內容在記憶體中儲存空間各自獨立，事實是可以同時進行處理的。因此程式被改寫為，當一個檔案中所需數量內容讀取完成後，該陣列將被送進額外執行緒，原執行緒則會再次重複動作。

由於使用裝置為八核心 CPU，因此程式中設定執行緒上限為 8，避免單核心同時處理多執行緒會造成效率降低，若同時 8 個執行緒皆工作中，主執行緒則會停等其一結束後再繼續執行。但目前的實驗結果中，由於單一 buffer 設定僅 125e6 個數字，數據處理過快導致程式最多只能同時跑 3 個執行緒，未來應可再針對這部分進行調整。

此圖為系統監控產生的 CPU 及記憶體運行狀況：