2023-01-13

平行程式設計

青蛙過河

任務

實現青蛙過河的小遊戲。爲了增加趣味性，對作業任務有所擴展，場景上佈置了兩個堡壘發射子彈，青蛙需要躲避三類子彈(一類是跟蹤彈，一類是正弦波子彈)、經木板穿過河流到達右下角(場景開始時會有箭頭標誌指示終點的位置)。之後遊戲會變難，即堡壘生產子彈的速度加快，新產生子彈的速度也會變快。

使用說明

依賴

gtkmm
cairomm

構建

程式依賴 gtkmm，兼容 2 和 3 兩類版本，在 gtkmm-3.4.0 及 gtkmm-2.24.2 上構建通過。

使用命令

1 2	./configure --prefix=/tmp/ins make install

生成依賴 gtkmm-3 的程式 /tmp/ins/bin/frog-river。

使用命令

1 2	./configure --prefix=/tmp/ins --with-gtkmm2 make install

生成依賴 gtkmm-2 的程式 /tmp/ins/bin/frog-river。

autotools 生成的 Makefile 爲 GNU Make 格式，如果是 FreeBSD、SunOS 之類的系統需要使用 gmake 代替 make。

程式運行時使用到的圖片位於 $(pkgdatadir)/img ，所以要 make install 後才能正常執行程式。

本報告位於 report/report.pdf ，可以用 make -C report report.pdf 根據 report/report.org 生成。

運行

程式的可定製性非常強，提供了豐富的命令行選項用以控制運行時行爲，幫助中提供了一些有趣的用例，比如修改河流寬度、位置，如果 river-y 超過 100 就會從場景上消失。下面有幾個用例讓河流消失來產生更好的效果。又如 -f 可以指定堡壘位置，結合其他三類子彈就可以實現各類奇異效果，比如彈幕遊戲，寫字等等。

可以試試看：

FrogRiver 0.1


Usage: frogriver [OPTIONS]...


  -h, --help                    Print help and exit
  -V, --version                 Print version and exit
  -t, --nthreads=INT            number of threads  (default=`1')
  -u, --update-interval=INT     milliseconds between two consecutive frames
                                  (default=`100')
      --size=DOUBLE             internal size of scene (NO CHANGING FOR GENERAL
                                  USE)  (default=`100')
  -c, --ncols=INT               number of tiles in a row  (default=`16')
  -r, --nrows=INT               number of rows in river  (default=`7')
      --frog-size=DOUBLE        frog size  (default=`5')
      --frog-spd=DOUBLE         frog speed  (default=`4')
      --river-y=DOUBLE          y coordinate of the top left corner of river
                                  (default=`24')
      --river-h=DOUBLE          river height  (default=`52')
      --bullet-size=DOUBLE      frog size  (default=`0.3')
      --tracer-bullet-lifetime=DOUBLE
                                tracer bullet lifetime  (default=`10')
      --fort-size=DOUBLE        fort size  (default=`10')
      --bullet-spawn-time=DOUBLE
                                normal bullet spawn time  (default=`2')
      --bullet-spd=DOUBLE       normal bullet speed  (default=`4')
      --tracer-spawn-time=DOUBLE
                                tracer bullet spawn time  (default=`8')
      --tracer-spd=DOUBLE       tracer bullet speed  (default=`3.2')
      --sine-spawn-time=DOUBLE  sine bullet spawn time  (default=`6')
      --sine-spd=DOUBLE         sine bullet speed  (default=`4')
  -f, --fort-pos=STRING         positions of forts


Example


Three Forts
frog-river -f 30:70 -f 50:50 -f 70:30


Big Bullet (NB. virtual hitbox of bullet will not be expanded)
frog-river --frog-spd 6


Big Frog (NB. virtual hitbox of frog will get expanded)
frog-river --frog-size 10


Water World
frog-river --river-y=10 --river-h=80


Water World Advanced
frog-river --river-y=10 --river-h=80 --nrows=12


No Forts
frog-river -f meow


Barrage
frog-river -f 10:90 -f 30:70 -f 50:50 -f 70:30 -f 90:10 --bullet-spd 7
--fort-spawn-time 0.1 --frog-size 0.5 --frog-spd 2


Shock Wave
frog-river -f 90:90 -f 90:70 -f 90:50 -f 90:30 -f 90:10 --river-y 999
--bullet-spawn-time 9999 --tracer-spawn-time 9999 --sine-spawn-time
0.1--river-y 999 is used to move the river outside the scene


DA
frog-river -f 50:0 -f 0:40 -f 100:40 -f 20:95 -f 80:95 --river-y 999
--bullet-spawn-time 9999 --tracer-spawn-time 0.1 --tracer-spd 0.11
--sine-spawn-time 0.1 --frog-spd 47

演示

data/demo.avi是示例視頻。

程式設計

下面逐一介紹各個類別的作用：

Core

存放公共的實用函數以及程式需要用到的簡單幾何庫，描述點、線段，可以處理線段與多邊形的相交。

Config

有一個實例 cfg，記錄虛擬畫布大小、河流位置大小、青蛙大小、青蛙移動速度等，下面諸類別大多都用了這個物件的資料。使用 gengetopt 生成 Cmdline.h 用於命令行選項的解析。

Frog

Frog 類別繼承自 Point，提供了 move 方法相應鍵盤事件，以及 draw 方法用於在Cairo::Context 上繪出青蛙的圖像。以下諸類別很多都有這個 draw 方法。

Board

表示木板類別，該類別處理碰撞、移動事件。移動時會考慮青蛙是否搭載在上面，是則把青蛙也一併移動了。碰撞爲彈性碰撞，動能不損耗。提供方法用於計算和另一塊木板的相撞時刻。

BoardLine

Board 的聚合(aggregate)。提供 init 靜態方法生成初始場景的木板，位置、長度都是隨機的，但質量相同。

BoardLine 記錄的是某一時刻某行的木板狀態，當用 advanceTo 方法要求把時刻移動至將來的另一個時刻時，它會枚舉兩個時刻間發生的所有碰撞事件並一一處理。

Bullet

Bullet 類別表示的是方向固定的點狀子彈，有 inCanvas 方法用於判斷是否還在場景上，以及 advance 方法表示移動一段時間，報告是否擊中了青蛙。擊中的判斷方式爲算是開始時刻和目標時刻子彈的運動軌跡(線段)，判斷是否和青蛙的 hitbox 相交。爲了使用 heterogenuous 列表實現多型，Bullet 中一些方法用了虛函數。

TracerBullet 類別代表一種跟蹤彈，繼承自 Bullet，覆蓋了 advance，移動方式變爲速度方向始終指向青蛙的當前位置。inCanvas 方法則變爲超過一定時限則判定追蹤彈消失。

Fort

表示堡壘，會源源不斷地射出子彈，給青蛙的移動造成困擾。它和 Bullet 的關係就像是 Board 和 BoardLine 的關係，同樣也是記錄當前描述狀態(包含時刻)，呼叫 advanceTo 方法時則轉發給 heterogenuous 的 Bullet 列表。如果離賞賜發射子彈的事件超過了某一閾值則產生出一顆新子彈。對於不同的子彈，可以用工廠函數，但我覺得在這裏用有殺雞用牛刀的感覺，因而未予使用。

FrogRiver

將之前的物件聚合起來搭成的場景，繼承自 Gtk::DrawingArea，程式邏輯等都在這個物件裏判斷。根據 cfg.update_interval 設置觸發 on_draw 用於重繪場景的間隔。觸發 on_draw 事件後，依次繪製河流、木板、堡壘、子彈、青蛙。其中繪製木板時會涉及到碰撞模擬，河流上不同行的木板間是不會相互干擾的，所以可以由不同的線程處理不同的行，工作線程間不會有通信。線程將會處理第行木板的碰撞情況。由主線程用 pthread_condt 將任務下達各工作線程。各線程用 pthread_barrierwait 同步後主線程再開始繪製堡壘。因爲繪製順序保證了顯示時的層次關係。後繪製的會覆蓋之前繪製的，所以要保證木板全部繪製完後再處理堡壘。

Main.cc

最後在 Main.cc 中展示出界面。

心得體會

這次作業是對 pthreads 的實踐機會，但更多的是培養了寫 gui 程式的能力。寫程式的過程中深深體會到 C++ 的樣本(boilerplate)代碼太多，表現能力有限，以及感受到物件導向程式設計的種種限制。

比如 Fort 中我本來打算用工廠函數產生各種類型子彈(當然現在子彈型別不是很多，沒有必要這樣寫)，工廠函數繞不過去的原因和 C++ 是 static 加 nominative typing system 有很大關係，無法方便地使用 heterogenuous 列表，而要用指針或引用以基類比表示多個類別的共同聯繫。如果在 Ruby 這類 duck typing system 離就可方便地儲存 heterogenuous 列表，OCaml 這類 structural typing system 中也可以，或者用包含函數的 algebraic data type 或着相應的existential data type 表示，這樣產生的樣本代碼 (boilerplate) 就更少了。一種類型不安全的解決方式有用一個標誌用於表示子彈型別，另用一個 void* 的數據供強制類型轉化爲相應型別。

Config 單獨提取出來提供了很大的靈活行，本來每個類維護自己的 static const 變量表示配置也是可以的，但不利於集中式管理。如果項目複雜 Config 可能還得展現層次化的結構。其實說到集中式我就聯想起 git，以及和它的模式對應的 subversion，這個有點扯遠了，但可以看出來概念之間的融會貫通相當重要。

物件導向程式設計時門博大精深的藝術。撇開型別的選取與設計，假設型別間的認識關係確定了，那麼問題可以部分看爲添加一些有向邊滿足型別之間的認識關係。而那些千變萬化的設計模式，不少是以增加新類來達到的，可願意部分看作一個 minimum Steiner tree 問題，如果讓型別聯繫起來。設計模式往往強調減小耦合，又可以部分看作是minimum spanning tree with restricted degrees。這些是我對物件導向程式設計的窺豹一斑，可惜未能見全貌。

程式原始碼

位於 src/ 目錄。

Mandelbrot set

任務

實現三種並行的Mandelbrot set實現，分別使用MPI、OpenMP和Pthreads。

使用說明

構建

程式採用 autotools 管理，./configure提供了大量選項，除了產生 MPI/OpenMP/Pthreads 三種並行庫的程式外，還有其他用於性能調優的選項。程式有如下選項：

MPI

生成使用 MPI 庫的版本。

1	./configure --with-mpi

OpenMP

生成使用 OpenMP 的版本。

1	./configure --with-openmp

Pthreads

生成使用 Pthreads 的版本。

1	./configure --with-pthread

無輸出模式

選項 --without-output ，用於提示程式不要產生輸出，將無法產生 PGM 或是顯示圖片，該選項用於基準測試時使用，性能會有少許提升。

float

複數計算時使用 float 而非 double，性能會有少許提升。

SSE2

選項 --without-sse2 ，同時計算兩個點，性能有大幅提升。

下面是和 MPI 配合使用的例子：

1	./configure --with-sse2 --with-mpi

命令行選項

src/mandelbrot -h Mandelbrot 0.1

Usage: mandelbrot [OPTIONS]...

-h, --help Print help and exit -V, --version Print version and exit -t,
--nthreads=DOUBLE number of threads (0 for auto detecting)
(default=\`0') -x, --x=DOUBLE xmin (default=\`-1.5') -y, --y=DOUBLE ymin
(default=\`-1') --xx=DOUBLE xmax (default=\`0.5') --yy=DOUBLE ymax
(default=\`1') --xr=DOUBLE x resolution (default=\`800') --yr=DOUBLE y
resolution (default=\`600') -i, --i=INT max iteration count
(default=\`255') -o, --o=STRING output format (default=\`x')

圖形使用者介面設計

輸出模式 -o x 提供了如下鍵綁定：

u: scale top-left by ratio 2 j: scale bottom-left by ratio 2 k: scale bottom-right by ratio 2 i: scale top-right by ratio 2 Space: scale center by ratio 1/2 Enter: restore to original range Button1 click: scale pointer center by ratio 4 Button3 click: scale pointer center by ratio 1/4 Button1 drag: scale up by (width/regionwidth, height/regionheight) Button3 drag: scale down by (regionwidth/width, regionheight/height)

Button1 單擊放大，Button3 單擊縮小。 Button1 拖曳放大查看指定區域，Button3 拖曳按比例縮小指定區域。 Enter 換原到命令行選項指定區域。

程式設計

爲了可以使用 MPI+Pthreads 或者 MPI+OpenMP，程序分爲三個層級，執行續層建立在串行層之上，程序層建立在執行續層之上，類似 TCP/IP 協議棧，

Core

串行層。包含主要計算模塊和 SSE2 優化過的版本。

實現了一個名喚 Callable<T,R> 的函數對象，相當於函數。後面一些回調函數會用到這一類型。

還描述了 Task 這一數據類型，表示任務的座標範圍、解析度，同時提供了計算成的點的儲存位置，以及一個行通知器，任務的執行者計算完一行後會通過這個通知器告知呼叫者。

比如1程序數時1執行緒時，任務從processSchedule轉交給threadSchedule再轉交給mandelbrot，它計算完一行後通過這個回調函數執行XPutImage往屏幕上繪製一行。當執行緒數大於1時，任務從processSchedule轉交給threadSchedule後，threadSchedule會給這個回調函數包裝一個mutex成爲MutexCallable，防止回調函數同時被多個執行續執行產生錯誤。當程序數大於1時，實際計算任務不是由主程序執行的，而 X 窗口是由主程序打開的，所以這些程序不能往屏幕上繪製一行，此時的回調函數是空的。

ThreadSchedule

執行續層。OpenMP 和 Pthreads 的實現在這裏，建立在 Core 中串行實現 mandelbrot 函數之上，提供了多執行緒的調度。採用 thread pool 模式，由主執行緒實施任務的調度。

Channel

被 ThreadSchedule 依賴用於實現不同執行續間的通信，Channel 是一個執行續安全的隊列，主執行續往裏面塞任務，工作執行續從中讀取任務進行處理。

ProcessSchedule

程序層。MPI 的實現在這裏，建立在 ThreadSchedule 之上，提供了多程序的調度。實現和 ThreadSchedule 非常像，也是採用 producer/consumer 模型，由主程序進行任務的調度，採取自定義的協議進行通信。

Master

Format 類型的一個成員，負責主程序的調度。如果未啟用 MPI，那麽 Master::run 只是簡單地把任務轉交給 ThreadSchedule，否則就指派任務給個工作程序并收集工作程序生成的資料。這個模塊的出現源於我需要讓用戶能和 Xlib 窗口交互， MPI 的工作程序不能立刻結束，所以單獨寫了這個 Master 類別負責把任務指派給工作程序。

Format

表示輸出的各種後端，類似 Gnuplot 中的 terminal，輸出的數據來自迭代時的 escape count。採用 XFormat 輸出時，會顯示顏色，顏色是根據 HSV 顏色模型中飽和度0.6，亮度1，色相根據 escape count　選取而來。

這裏的 Format 的任務不只是產生輸出而已，它也涉及數據的產生。因爲不同的輸出往往需要不同的數據處理方式，Core 中的 mandelbrot 函數會把數值寫到一個數組裏去，寫完一行後還會通過一個回調函數告知已經處理完一行。這裏這個數組就是由 Format 提供的，比如對于 PGM 圖片格式，提供的數組就是一個大小為 width * height 的數組，而對于 Xlib 圖形顯示，數組是 XImage 中的 data。

這裏具體講 Format 的一個子類型 XFormat，XFormat 物件會做一些 Xlib 的初始化工作產生一個圖形界面，生成一個位圖數組供 mandelbrot 函數寫入。當某個 ThreadSchedule 管理的執行續執行的 mandelbrot 計算完一行後，通過回調函數(Callable<int> Task.notifier)告知呼叫者，呼叫者會考慮當前是否工作在 MPI 多程序模式下，如果不是那麽就用 XPutImage 顯示出這一行。如果使用了 Pthreads，threadSchedule 會包裝 Callable<int> 產生執行續安全的 MutexCallable<int> 作為回調函數。

其實 Task.data 字段也可以替換成回調函數以提供更大的靈活性，但我為了性能考慮還是決定使用數組，而一行執行一次回調函數的開銷還是可以忍受的。

這裏由 Format 管理 Master 的意圖是 Xlib 圖形界面在初次顯示後還會有放大、縮小的需求，工作程序不能產生完第一幅位圖後就退出，需要繼續等待主程序的調度，為了統一接口，幹脆讓 Format 內置一個 Master fsm 字段，對于一次性輸出的 Format 比如 PGM，PGM::render 做的事就是先用 fsm.run(tk) 產生數據再輸出，而 XFormat 則會等待用戶指令。

另外有一個 TimeFormat，繼承自 NullFormat，會調用 gettimeofday 顯示主程序的運行時間。

分析

設串行程序的計算量爲，即每個像素都被迭代至逃逸設定半徑或者達到最大迭代次數。分別表示x座標解析度、y座標解析度，這裏不考慮初始化輸出用數組等與計算無關步驟的時間。

OpenMP 版本

令爲執行續數。

每個執行續的工作量爲。

總共，其中是執行續創建開銷。

Pthreads 版本

令爲工作執行續數。

共有個行繪製任務，使用 Channel 進行通信，平均每個工作執行續分得個，，主執行續。

每個工作執行續的計算量平均爲。

總共。

MPI 版本

令爲工作程序數。

主程序用廣播通知各程序座標解析度等信息，這一過程可以用 binomial tree 等方式優化至　，通信量爲。
平均每個工作程序分得的計算任務，通信量爲，而主程序的通信量爲。
每個工作程序要把結果傳給主程序，通信量，主程序的通信量。
主程序用廣播通知各程序退出，通信量應爲。
總共。
基準測試

以下所有測試中y座標解析度 --yr 的值都統一為了 10000，最大escape count都爲255。

MPI

我測試了三種版本，除了普通版本外，還有一種是用float替換double，另一種是用 SSE2 指令同時處理兩個 double。三個版本的構建方式有略微區別，後面會給出 configure 時的選項。但它們的運行方式都是

1	mpirun -n ? src/mandelbrot -o time --xr ? --yr 10000

其中問號處分別填寫程序數、x坐標解析度、y坐標解析度。主程序會輸出計算部分的執行時間。程式運行在 FIT 集羣上。

--without-output CXXFLAGS=-O3 --with-mpi

可以觀察到執行時間大致是關於x座標解析度的一次函數，和時間複雜度相吻合。注意到1程序數和2程序數的執行時間沒有太大區別。這是因爲程序數時只有的爲工作程序，再算上程序通信、主程序調度時間，就會比1程序數時慢些。

--without-output CXXFLAGS=-O3 --with-mpi --with-float

執行時間比 mpi-normal 略少。

--without-output CXXFLAGS=-O3 --with-mpi --with-sse2

執行時間大致是 mpi-normal 的一半。

極限測資

我還對96、112、128程序數，進行了測試：

sse2 最快，其次是 float，normal 最慢。

OpenMP

和 MPI 一樣，有三種版本，把 --with-mpi 改成 --with-openmp 即可。執行方式爲

1	src/mandelbrot -o time --xr ? --yr 10000 -t ?

其中 -t 參數爲執行緒數，執行期會調用 omp_set_num_threads 修改執行緒數。採用動態調度方式，因爲不同行的計算量不同，靜態調度會導致先執行完的執行緒等待後執行完的，不能充分利用計算能力。程式運行在集羣中的一臺機器上。

--without-output CXXFLAGS=-O3 --with-openmp --with-sse2

Pthreads

和 OpenMP 一樣，有三種版本，把 --with-mpi 改成 --with-pthread 即可。執行方式和 OpenMP 版本相同。用

1	./configure --without-output CXXFLAGS=-O3 --with-pthread

構建程式。程式運行在集羣中的一臺機器上。

--without-output CXXFLAGS=-O3 --with-pthread

--without-output CXXFLAGS=-O3 --with-pthread --with-float

執行時間比 pthread-normal 略少。

--without-output CXXFLAGS=-O3 --with-pthread --with-sse2

執行時間大致是 pthread-normal 的一半。

三種庫的性能比較

在程序/執行續數在時，三種庫的性能提升都是線性的。OpenMP 的表現比較奇怪，可能是因爲 omp_{setnumthreads} 沒有起效。 MPI 的初始開銷比其他兩個庫大，但是提速效果是最爲明顯的。採取 thread pool 模式的 Pthreads 版本效率比 OpenMP 略高一點。除了並行庫外，串行計算程式的改進對執行效率的提升也有非常大的效果。本例中 SSE2 就達到了近乎2倍的性能。

爲了考察並行程式提速效果，我還分別對它們相對於單工作程序/執行續的效率進行了測試，使用了公式計算相對於單工作程序的效能。其中爲單工作程序(算上主程序，程序數爲2)的執行時間，爲多工作程序的執行時間，爲工作程序數。直觀上，越大代表加速效果越明顯，單位用百分比表示。

上圖中是對 mpi-sse2 的測試，2程序數對應了單工作程序情形，效率爲100%，更多程序數時計算的是相對於單工作程序而言的。

可以看出執行緒數時效率爲100%上下，超過12時就下降了，這是由於測試機器 c01b04 爲12執行緒數。

執行緒數時效率就有明顯下降。

心得體會

這次作業需要用三种并行库，是對並行程序設計的一次絕佳實踐機會。我不希望寫成三個不同程序，把計算模塊復制三份，所以就考慮用預處理指令。這樣很快就碰到代碼難以管理的地步，就仔細設計了這麽一個工作模型，讓 MPI、Pthreads、OpenMP 三者可以同時開啟。 OpenMP 和 Pthreads 工作在執行續層面，用 ThreadSchedule 管理。MPI 在程序層面，由 ProcessSchedule 處理。兩者都是動態分配任務的，使用了 thread pool 模式，但差异還是比較大的，代碼不能實現有效的重復利用。

OpenMP 在項目中有效的行數只有1，就是 Core.cc:mandelbrot 中的一個循環前的預處理器指令，但是效果驚人。Pthreads 則需要手寫 Channel，考慮任務的調度等，代碼量很大，但得到的效能和 OpenMP 差不多，OpenMP 以如此少的額外代碼做到如此高效很讓人吃驚。MPI 的代碼量就更大了，資料在程序間的遞送很麻煩，但可以方便地跨機器使用，還是有很大的價值。

程式開發過程中感受到並行程式調試的麻煩，OpenMP雖然指令不透明，但因爲操作簡單，只需注意串行實現的變量共用等問題即可。而 Pthreads 程式就要用 gdb 的 thread 功能，MPI 我沒找到非常有效的調試方法。目前是採用的方式是讓個程序輸出 PID 後while(i==0)sleep(1) 停下，用 gdb -p $PID 跟蹤進去。

C++ 使用多型的方式過於麻煩。subtype polymorphism必須保證類型是指針或引用，開發過程中就着了這個道。在此基礎上實現 ad-hoc polymorphism(比如程式中的 MutexCallable 的特化)的樣本代碼也比較長。使用函數對象或函數作爲參數也比較麻煩。

程式原始碼

在 src/ 目錄中。

青蛙過河

任務

使用說明

依賴

構建

運行

演示

程式設計

Core

Config

Frog

Board

BoardLine

Bullet

Fort

FrogRiver

Main.cc

心得體會

程式原始碼

Mandelbrot set

任務

使用說明

構建

MPI

OpenMP

Pthreads

無輸出模式

float

SSE2

命令行選項

圖形使用者介面設計

程式設計

Core

ThreadSchedule

Channel

ProcessSchedule

Master

Format

分析

OpenMP 版本

Pthreads 版本

MPI 版本

MPI

--without-output CXXFLAGS=-O3 --with-mpi

--without-output CXXFLAGS=-O3 --with-mpi --with-float

--without-output CXXFLAGS=-O3 --with-mpi --with-sse2

極限測資

OpenMP

--without-output CXXFLAGS=-O3 --with-openmp --with-sse2

Pthreads

--without-output CXXFLAGS=-O3 --with-pthread

--without-output CXXFLAGS=-O3 --with-pthread --with-float

--without-output CXXFLAGS=-O3 --with-pthread --with-sse2

三種庫的性能比較

心得體會

程式原始碼

N-body模擬