---
# System prepended metadata

title: Final Project

---

<style>
  pre, code {
    white-space: pre-wrap !important;       /* 強制換行 */
    word-wrap: break-word !important;       /* 強制斷詞 */
    max-width: 100% !important;             /* 限制寬度 */
    overflow-x: hidden !important;          /* 隱藏超出部分 */
    width: 100% !important;                 /* 強制適應頁寬 */
  }
  table {
    max-width: 100% !important;             /* 限制表格寬度 */
    width: 100% !important;                 /* 適應頁面寬度 */
    table-layout: auto !important;          /* 自動調整欄寬 */
    border-collapse: collapse !important;   /* 確保表格邊框正常 */
  }
  th, td {
    white-space: normal !important;         /* 允許內容自動換行 */
    word-wrap: break-word !important;       /* 強制斷詞 */
    overflow-wrap: break-word !important;   /* 支援現代瀏覽器斷詞 */
    padding: 5px !important;                /* 確保內容不貼邊 */
  }
</style>

學號: 113065507
姓名: 彭星樺
[GitHub repo](https://github.com/ktpss97094/ESL_Final)

# Introduction

此 Final Project 分為兩部分:
* Part 1
    * 使用 HLS 合成 Color Image Histogram Equalization 電路
    * 分為 baseline (完全依照原始 Historgram Equalization 公式計算) 及 optimize (修改演算法並減少 bit width) 兩種版本。可使用 `utils.h` 的 `HLS_BASELINE` 做切換
        * optimize 版可使用不同的 config 測試透過不同 Stratus directive 優化後的結果
* Part 2
    * 在 RISC-V VP 平台上模擬 multi-core、multi-PE，並支援 DMA 的 Color Image Histogram Equalization micro-architecture
    * 支援僅調整兩個參數即可控制 core/PE 的數量

兩部分皆支援:
* RGB/grayscale bmp 圖片輸入
* 正方形、非正方形的圖片

# 環境建置

使用電機系工作站

## Part 1

```sh
ssh ee647012@daisy.ee.nthu.edu.tw
ssh ws26  # ws25 - ws47 皆可 (但有些可能有問題)

vim ~/ee6470/stratus_env.sh
# 貼上以下指令
source /usr/cadtool/user_setup/01-cadence_license_set.cshset
source /usr/cadtool/user_setup/03-stratus.csh
source /usr/cadtool/user_setup/03-xcelium.csh
setenv STRATUS_EXAMPLE /usr/cad/cadence/STRATUS/cur/share/stratus/collateral/examples

# 設定啟動自動 source
vim ~/.tcshrc
# 貼上以下指令
source ~/ee6470/stratus_env.sh
```

## [Part 2 (`cd $EE6470` 前的)](https://hackmd.io/Q8ufcAVNQPCa9uCvaAT6IA?both#%E7%92%B0%E5%A2%83%E8%A8%AD%E5%AE%9A)

# Block Diagram

## Part 1

![block diagram](https://hackmd.io/_uploads/By3h1GJQex.png)

## Part 2

![block diagram](https://hackmd.io/_uploads/H1P_gMJ7eg.png)

# Implementation Details

## Part1

### baseline

![9](https://hackmd.io/_uploads/ryzlzz1mex.png)
![10](https://hackmd.io/_uploads/ByHezM1mgg.png)

1. Testbench 先傳送整個圖片的 pixel intensity 至 PE
2. PE 接收 intensity，並統計 $n_k \forall k \in [0, 255]$
    :::info
    若為 RGB image，則將 RGB 以以下公式轉至 **YCbCr** 色彩空間，並使用 Y 值做 Historgram Equalization:
    
    $Y = 0.257 * R + 0.564 * G + 0.098 * B + 16$
    $Cb = -0.148 * R - 0.291 * G + 0.439 * B + 128$
    $Cr = 0.439 * R - 0.368 * G - 0.071 * B + 128$
    
    > reference: {%preview https://blog.csdn.net/liulianfanjianshi/article/details/11723237 %}
    :::
3. PE 傳送 $n_k$ 至 Testbench $\forall k \in [0, 255]$
4. Testbench 累加 PE 傳送的 $n_k \forall k \in [0, 255]$
5. Testbench 計算 $p_r$
6. 
    * Testbench 傳送 $p_r$ 的每一個數值，並再次傳送整個圖片的 pixel intensity 至 PE，同時接收 PE 輸出的處理後的 pixel 值
        :::info
        傳送兩次的原因是因為 PE 無法成功合成出夠大的 buffer 暫存圖片
        :::
    * PE 讀取 $p_r$，並 **依照公式上的算法，每個 pixel 計算 $p_r$ 的 summation 並做乘法**，並傳給 Testbench

### optimize

* baseline 的第 5 步改為 **直接預先算好所有可能的 intensity 被 mapping 後的值 $T$ (最多只有 256 個值)**，並且第 6 步 Testbench 改為傳送 $T$ 的每一個數值、PE 改為接收 $T$ 的值，並可直接透過 $T$ 傳送 pixel mapping 後的值給 Testbench
* 減少變數 bit width

## Part 2

1. 先讓 core 0 讀取圖片到各個 core 共用的 CPU memory (在程式內即為 global variable)，其他 core 使用 barrier 等待 core 0 完成讀取
2. 每個 core 發送 metadata (各個 PE 總共要處理的圖片 byte 數、bytes per pixel) 給各自對應的 PE
3. 每個 core 呼叫 DMA 將各自需要處理的圖片傳送到對應的 PE
    :::info
    圖片 partition 方式為橫切等分
    :::
4. PE 會直接將圖片暫存在自己的 buffer 避免需要二次傳送。並統計 $n_k$。統計完成後 interrupt 對應的 core。core 呼叫 DMA 累加收到的 $n_k$ 數值
5. 讓 core 0 計算 intensity mapping 後的值 $T$。其他 core 用 barrier 等待 core 0 算完
6. 每個 core 呼叫 DMA 將 $T$ 傳送到對應的 PE，PE 將在步驟 6 收到的圖片的 pixel 做 mapping。Mapping 完成後 interrupt 對應的 core
7. 每個 core 呼叫 DMA 寫回處理後的圖片到 CPU memory。寫回完成後，持續檢查 PE 內的 status register 看 PE 是否完成工作
8. 設置一 barrier 等待所有 core 皆完成檢查
9. 讓 core 0 輸出處理後的圖片

# Special Features

## `utils.h` 的 soft link

我將原始的 `utils.h` 放在 `vp/src/platform/histogram-equalization/`，software 端的 `utils.h` (在 `sw/histogram-equalization/`) 是一 soft link 指向原始的 `utils.h` 路徑，這樣可以避免同樣的參數 (例如: core/PE 數量、TLM address) 要定義在兩個地方

## 僅調整兩個參數即可控制 core/PE 的數量

只要調整:
1. `utils.h` 內的 `N`
2. software `bootstrap.S` 內的 `N`

即可控制 core/PE 的數量。目前 `N` 最大支援到 16，但也可自行修改程式以增加上限

> 增加 `N` 上限的方法:
> 1. 修改 `bootstrap.S` 內所有註解 CHANGE 的地方
> 2. `main.cpp` 新增更多 IRQ handler function，並在 `init_acc_irq_handler()` 填寫這些新增的 function 名稱

# Experimental Result

皆以 `lena_color_256.bmp` (256*256 pixels、RGB) 圖片作為輸入圖片

## Part 1

可試各種 optimize 版本:
* `sim_V_UNROLL_INITIALIZE_LOOP`: unroll 初始化 n_k array 為全 0 的 loop
* `sim_V_FLATTEN_ARRAY`: flatten n_k array
* `sim_V_PIPE_RECV_PIXEL_LOOP`: pipeline 接收 pixel 值的 loop
* `sim_V_PIPE_SEND_N_K_LOOP`: pipeline 傳送 n_k 的 loop
* `sim_V_PIPE_RECV_MAPPING_LOOPS`: pipeline 接收 mapping 值的 loop
* `sim_V_PIPE_RECV_PIXEL_AND_SEND_RESULT_LOOP`: pipeline 最後接收 pixel 值並傳送處理後的 pixel 值的 loop
* `sim_V_OPTIMIZE`: 最終版本的優化 (包含 pipeline 接收 pixel 值的 loop 及做 dpopt)

| version / command | Area | Average Latency (cycle/pixel) | Average Throughput (pixel/cycle) |
| -------------- | -------- | -------- | -------- |
| baseline / `make sim_V_BASIC` | 21862.9 | 9576427 | 0.003340 |
| optimize / `make sim_V_BASIC` | 21683.1 | 1344584 | 0.024376 |
| optimize / `make sim_V_UNROLL_INITIALIZE_LOOP` | 23779.5 | 1344584 | 0.024379 |
| optimize / `make sim_V_FLATTEN_ARRAY` | 199086.4 | 1278779 | 0.025631 |
| optimize / `make sim_V_PIPE_RECV_PIXEL_LOOP` | 29366.9 | 1082409 | 0.030281 |
| optimize / `make sim_V_PIPE_SEND_N_K_LOOP` | 22452.1 | 1344330 | 0.024379 |
| optimize / `make sim_V_PIPE_RECV_MAPPING_LOOP` | 21949.7 | 1344330 | 0.024379 |
| optimize / `make sim_V_PIPE_RECV_PIXEL_AND_SEND_RESULT_LOOP` | 58172.4  | 558117 | 0.058743 |
| optimize / `make sim_V_OPTIMIZE` | 22452.1 | 656413 | 0.049941 |

### Unroll Loop

`sim_V_UNROLL_INITIALIZE_LOOP` 增加的 average throughput 只比 `make sim_V_BASIC` 多 0.000003，故不考慮 unroll initialize loop

### Flatten Array

`sim_V_FLATTEN_ARRAY` 能稍微改進 average latency 及 throughput，但增加的 area 太多 (增加近 9 倍)，故不考慮 flatten array

### Pipeline Loop

PE 內共有 4 個主要的 loop:

1. `sim_V_PIPE_RECV_PIXEL_LOOP`
    average latency 減少了 20%，area 增加了 35%，我覺得算在合理範圍內，故考慮此 pipeline
2. `sim_V_PIPE_SEND_N_K_LOOP` 及 `sim_V_PIPE_RECV_MAPPING_LOOP` 的 average latency 減少數量過低，故不納入考慮
3. `sim_V_PIPE_RECV_PIXEL_AND_SEND_RESULT_LOOP` 即使可以減少近 60% 的 average latency，但 area 增加近 168%，故也不考慮

## Part 2

### 使用 HLS 實際的 latency (170 ns)

| Core/PE 數量 | DMA data amount | Total DMA cycles | Max PE computation cycles | Total application cycles | Simulation Time (所有 core 皆相同) | Number of Instructions (每個 core) |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| 16 | 413824 | 6544 | 6731930 | 6738474 | 67722220 | 2078118 / 2693344 / 2693289 / 2693230 / 2693338 / 2693357 / 2693302 / 2693280 / 2693243 / 2693262 / 2693311 / 2693218 / 2693330 / 2693321 / 2693033 / 2693275 |
| 8 | 403520 | 6344 | 6399686 | 6406030 | 64389580  | 1947357 / 2560773 / 2560761 / 2560724 / 2560755 / 2560746 / 2560711 / 2560737 |
| 4 | 398368 | 6244 | 6234347 | 6240591 | 62722650 | 1883277 / 2515965 / 2495603 / 2495580 |
| 2 | 395792 | 6194 | 6111754 | 6117948 | 61496860 | 1837964 / 2449855 |
| 1 | 394504 | 6169 | 6111473 | 6117642 | 61491700 | 1844508 |

可以發現 core/PE 越多，消耗的時間反而越長，與想像中不同。以下再做將每個 pixel 的 latency 設較大

### 使用較長的 latency (10000 ns)

(因為 DMA 部分沒有變動，所以 DMA data amount 及 Total DMA cycles 不變)

| Core/PE 數量 | Max PE computation cycles | Total application cycles | Simulation Time (所有 core 皆相同) | Number of Instructions (每個 core) |
| -------- | -------- | -------- | -------- | -------- |
| 16 | 71068351 | 71074895 | 711097280 | 27811078 / 28475672 / 28475586 / 28475632 / 28475604 / 28475654 / 28475626 / 28475564 / 28475617 / 28475682 / 28475622 / 28475596 / 28475645 / 28475695 / 28475667 / 28475604 |
| 8 | 70747746 | 70754090 | 707873240 | 27731952 / 28394683 / 28394724 / 28394785 / 28394702 / 28394696 / 28394715 / 28394793 |
| 4 | 70519686 | 70525930 | 705577110 | 27737224 / 28399144 / 28399109 / 28399067 |
| 2 | 70531575 | 70537769 | 705693530 | 27934063 / 28596565 |
| 1 | 70532540 | 70538709 | 705700910 | 28318337 |

core/PE 數量由 1 到 4 會逐漸減少執行時間，而由 4 到 16 則會和原始 latency 一樣逐漸增加時間。總結來看，我認為 Histogram Equalization 是一個 I/O-bound 程式，將 core/PE 數量增大有機會減少執行時間，但如果太大的話反而會大幅增加 thread 數量，software 中的 mutex lock 也會有更多 core 同時在等待，造成多個 PE 的效果不理想。

# Discussions and Conclusions

## DMA Status Register

似乎是因為原本 [Lab 8 LeNet](https://hackmd.io/Q8ufcAVNQPCa9uCvaAT6IA?view#riscv-vp-acc-lenet) 的 DMA 寫入/讀取函式 `write_data_to_acc()/read_data_from_acc()` 沒有判斷目前 DMA 的工作是否已完成，就會呼叫下一個 DMA 寫入/讀取函式，造成 DMA 並沒有完整完成工作而讓結果錯誤，我有修改了 platform 中的 `dma.h`，讓 DMA 多一個 **status register**，當 DMA 完成工作時此 status register 會設為 0 表示 idle。而 core 每次執行 DMA 寫入/讀取函式後，會 polling 檢查此 status register 的值直到值變為 0。加入此 polling 機制就能讓輸出結果正確。

## 多 core/PE 結果不理想

也有可能是因為程式有 bug 才造成此結果，如果有更多時間的話我希望能找出可能的原因。