國立成功大學資訊工程學系特殊選才乙組

概述

平行運算 (parallel computing) 是指許多行程（processes）得以同時進行的計算模式。透過將問題拆解成諸多不同的小問題，使得多個行程得以同時解決這些小問題，來加速程式的運行。舉例來說，矩陣相乘的運算就很適合使用平行運算來處理，因為中間的運算都是獨立的過程：

\begin{matrix} (1) & [\begin{matrix} a & b \\ c & d \end{matrix}] [\begin{matrix} e & f \\ g & h \end{matrix}] = [\begin{matrix} a e + b g & a f + b h \\ c e + d g & c f + d h \end{matrix}] \end{matrix}

影像處理的領域中也常常見到平行處理的應用。在影像處理的領域中，我們常常用一個較小的矩陣 —— kernel（或者稱做 mask）—— 與影像進行 二維卷積2D convolution (請參考 [相關資料] 章節) 處理。經由與不同的核進行 convolution，來完成影像的邊緣偵測或是使影像邊緣模糊化。

然而，大尺寸的影像在進行 2D convolution 時，需要花費大量的運算時間，造成效能瓶頸。因此，在這次考試中，希望妳/你能在給定的架構下，平行化處理影像的二維卷積。

考試要求

請在閱讀完文件後，依照其中軟體架構的說明建立系統。考生需：

排除程式內部的錯誤，使得系統能正常運行
成功建立系統後，透過參數的調整或是程式優化的技巧來加速運算。

成績採計方式

系統啟動（系統無法啟動者，即不列入備取）
$PSNR$ 高者排名較高
- $PSNR$ 的計算公式如下（單位為分貝）：
$\begin{matrix} (2) & P S N R = 20 l o g_{10} (M A X_{I}) - 10 l o g_{10} (M S E) \end{matrix}$
$MSE$ $MAX_I$ 在此處則為一定值表示像素點的最大數值。
- 若完成convolution圖片與原圖大小不一至，成績則不予採計
- PSNR 值小於 40 dB 者不予採計
- PSRN $dB$ $dB$ 作為成績登入
$PSNR$ 相同者，以計算時間最短者排名較高

備註1：考試期間可以任意次數提交程式碼（取成績最高者）

備註2：請記得在伺服器端上傳程式碼，在 gitlab 上無執行紀錄者成績不予採計

軟體說明

系統流程

考生可以對照圖（一）的架構，或圖（二）的 sequence diagram，逐步了解系統流程。

Producer 傳送開始訊號(s)給 System
- 開始訊息：[userID] s
System 回傳待處理的圖片路徑給 Producer，並同時開始計時
Producer 發送任務給一至多個 Consumer(s)
Consumer 各自完成任務後傳送結果給 ResultCollector
ResultCollector 接收完所有子任務後將其統整，再傳送結束訊息(e)給 System。System 結束計時。
- 結束訊息：[userID] e [image_saved_path]
System 驗證答案正確性，回傳本次任務狀態給 ResultCollector

程式內部流程

在本次考試中，考生須要對系統中的三支程式進行改進與改正，包括 Producer.py、Consumer.c 以及 ResultCollector.py，另外也可以透過調整 SystemParameters.json 來進行改變系統參數。前三者分別對應到圖 (一)的 Producer,Consumer 和 Result Collector。本節將對這三支程式的細節與流程進行解說。

Producer

系統參數設定
參數說明
socket_system_server Producer 與 System 連接的 socket port
socket_producer_consumer Producer 與 Consumer 連接的 socket port
num_to_split 分派的子任務數量
說明
- Producer 會與 System 和 Consumer 進行連線，並分別以 Request/Reply 和 Pull/Push 的模式溝通 (模式說明請參閱 [相關資料] 章節)。
  Producer 與 System間以 Request/Reply 的模式連接，兩者綁定在系統參數 socket_system_server 所指定的 port。Producer 會從System 得到一組圖片路徑 image_path，作為本次處理的任務。
  另一方面， Producer 與 Consumer 則是以 Pull/Push 的模式連接，兩者綁定在系統參數中 socket_producer_consumer 所指定的 port。系統運行中，Consumer 會不斷地去 pull 由Producer push 的任務來進行處理。
  我們可以在 圖 (三) 的流程圖中了解 Producer 這支程式執行的邏輯：

參數	說明
`socket_system_server`	`Producer` 與 `System` 連接的 socket port
`socket_producer_consumer`	`Producer` 與 `Consumer` 連接的 socket port
`num_to_split`	分派的子任務數量

圖 (三) Producer 運行的流程圖	說明
	1. 生產者會先設定與消費者及伺服器之連線 2. 送出開始訊號 3. 等待伺服器端給予回覆，直至收到伺服器端回覆的圖片路徑 4. 生產者讀取該位置的圖片，並根據系統參數設定檔中 `num_to_split` 來設定拆分的子任務的數量 5. 傳送任務給消費者 6. 傳送完成後，關閉開啟的 socket 埠

Consumer

系統參數設定

參數	說明
`socket_producer_consumer`	`Consumer` 與 `Producer` 連接的 socket port
`socket_consumer_collector`	`Consumer` 與 `Collector` 連接的 socket port
`num_of_consumers`	指派系統使用的 `Consumer` 數量

說明
- Consumer 會與 Producer 和 Collector 進行連線，其模式可以比照 圖 (一) 所示，並以 Pull/Push 的模式溝通 (模式說明請參閱 [相關資料] 章節)。此兩者綁定的 port 亦可在系統參數設定檔進行設定，分別是 socket_producer_consumer 與 socket_consumer_collector 這兩個參數。另外，透過設定系統參數中的 num_of_consumers 可以指定系統執行 Consumer 的 process 數量。
  我們可以在 圖 (四) 的流程圖中了解 Consumer 這支程式執行的邏輯：

圖 (四) Consumer 運行的流程圖	說明
	1. 設定與生產者與結果收集器之連線設定 2. 等待任務 3. 當接收到任務後由 Worker 進行任務處理 4. 將結果傳送到結果收集器 5. 若無中斷則回到步驟二，等待接收新的任務 6. 若被中斷則結束程式

ResultCollector

系統參數設定
參數說明
socket_system_server Collector 與 System 連接的 socket port
socket_consumer_collector Collector 與 Consumer 連接的 socket port
說明
- Collector 會與 System 和 Consumer 進行連線，並分別以 Request/Reply 和 Pull/Push 的模式溝通 (模式說明請參閱 [相關資料] 章節)。
  Collector 與 System間以 Request/Reply 的模式連接，兩者綁定在系統參數 socket_system_server 所指定的 port。Collector 會從 System 得到該次任務處理完成的狀態。
  另一方面， Collector 與 Consumer 則是以 Pull/Push 的模式連接，兩者綁定在系統參數中 socket_consumer_collector 所指定的 port。系統運行中，Collector 會不斷地去接收由Consumer 運算完成的子任務。
  我們可以在 圖 (五) 的流程圖中了解 Collector 這支程式執行的邏輯：

參數	說明
`socket_system_server`	`Collector` 與 `System` 連接的 socket port
`socket_consumer_collector`	`Collector` 與 `Consumer` 連接的 socket port

圖 (五) ResultCollector 運行的流程圖	說明
	1. 設定與消費者與伺服器之連線 2. Pull 來自消費者的任務 3. 若任務尚未收集完成，回到步驟二。否則繼續。 4. 重組影像 5. 儲存影像 6. 顯示結果

資料結構

資料傳輸的 MessageBuffer 是以 JSON 的格式進行編碼，其中資訊如下表所示。

KEY	資料型態	說明
image	2 dimentional array
mask	2 dimentional array
point	1 dimentional array	左上角之座標
total_buffer_num	Number	子任務總數
src_path	String	圖片路徑

檔案結構說明


.
+-- lib/
|   +-- FFT/
+-- src/
|   +-- System/
|   |   +-- test
|   +-- SystemParameter.json
|   +-- Producer.py
|   +-- Consumer.c
|   +-- ResultCollector.py
|   +-- makefile
+-- requirements.txt
+-- README.md

檔案/目錄	說明
`src/SystemParameter.json`	系統參數設定檔，其中定義了 1. `userID`：請自行輸入准考證號碼 2. `num_of_consumer`：指派系統開啟的 Consumer 數量 3. `num_to_split`：分派的子任務數量 4. `socket_producer_consumer`：Producer 與 Consumer 間溝通的 port 5. `socket_consumer_collector`：Consumer 與 Collector 間溝通的 port 6. `socket_system_server`：Producer/Collector 與 System 溝通的 port
`src/Producer.py`	Producer
`src/Consumer.c`	Consumer
`src/Resultcollector.py`	Collector
`src/makefile`	Consumer.c 的 makefile
`System/test`	考生本地端系統測試執行檔
`requirements.txt`	Python 的環境需求
`lib/FFT`	內附簡單的 FFT 範例

執行方式

本地端

本地端僅提供測試，實際驗證與成績登入請上傳至伺服器，在雲端伺服器上無執行紀錄者成績不予採計。（不保證執行效率與雲端相同，建議使用較少的 processes 進行運算）

在 src/ 底下執行

確認系統正常運作，執行 System/test
```
$ cd src
$ ./System/test
```
- 若執行成功，可以在終端機看到如下結果，若顯示 [System] Congratulation! System establish successfully!! 即代表系統建置完成
- 接著，考生可以對比 img/test.jpeg 與 results/test.jpeg 兩張圖片之差異，來確認是否成功進行影像之 2D convolution。
  - 備註1：若 PSNR 值小於 0，代表影像大小與原圖不一致
  - 備註2：當 PSNR 值大於 1000 dB 系統即以 1000 dB 進行成績登入
  原圖 ([project root]/img/test.jpeg) 做完2D Conv. 完之圖片 ([project root]/results/test.jpeg)