1、什么是Embarrassingly Parallel（易并行計算問題）
易并行計算問題：A computation that can be divided into a number of completely independent tasks，在撰寫并行程式程序中，首先需要將一個問題分解成若干部分，然后將每個部分分配給不同的processer（處理器）或者thread（執行緒）分別進行計算，如果該計算問題能夠被分解成一些完全獨立的子計算（task）、同時各個task之間資料幾乎沒有依賴，沒有通信，那這個計算問題就叫作易并行計算問題，
對于該問題一般程式處理流程如下：
對于輸入的Data，直接拆分成幾塊互相沒有依賴的Subdata,每一份Subdata具有完全相同的處理方式，最后再將subdata的處理結果合并行輸出，對于這類資料計算問題，就天然的適用于并行計算，尤其是在影像處理方面，并行處理的情況很多，
在對影像進行平移、旋轉、縮放程序中，對于每一個pixel(像素點)資料都是完全相同的操作，當然我們可以寫一個兩層for回圈，遍歷每個pixel，然后對每個pixel進行轉換，但這樣效率很低，按照并行編程的思路，我們可以對一幅影像不同的像素點進行拆分，送到不同processer，同時進行影像計算，這樣就實作了影像計算的加速，理想情況下，對于每個piexl，咱們都送到一個processer中進行計算，這樣效率最高，但實際情況是，往往processer或者thread開啟的數量也是有限度的，就像高速公路分流一樣，不可能無限制的擴寬車道，所以咱們需要對一整個Data進行合理的拆分，將一塊資料送入processer中進行處理，正如上圖所示，對于原始影像的拆分可以分塊、分行、分列，不同的分割方式對最后運行效率也是有一定影響的，
2、易并行計算需要考慮的問題
對于易并行計算問題，雖然資料很容易進行拆分處理，但在實際撰寫程式程序中往往會遇到兩個問題，首先我們看一下并行編程的程式框架，
對于影像的平移處理，一般并行程式由主從結構構成，主程式用來對資料進行拆分，送到不同的process中，并接受不同process的回傳值，
??主程式
//master process 對于480*640的影像
for(i=0, row=0; i<48; i++, row+=10) // for each of 48 processes 按行拆分
{
send(row, Pi); // send row no.
} //資料拆分 以及發送
for(i=0; i<480; i++){
for(j=0; j<640; j++) {
temp_map[i][j] = 0; // initialize temp 緩沖陣列
}
}
for(i=0; i<(480*640); i++) { // for each pixel
recv(oldrow, oldcol, newrow, newcol, PANY); // accept new coordinates 資料接收
if !((newrow<0)||((newrow>=480)||(newcol<0)||((newcol>=640)){
temp_map[newrow][newcol] = map[oldrow][oldcol];
}
}
for(i=0; i<480; i++){
for(j=0; j<640; j++) {
map[i][j] = temp_map[i][j]; // update map 更新影像
}
}??子程式
// slave process
recv (row, Pmaster);
for (oldrow = row; oldrow < (row+10); oldrow++) // for each row in the partition 區域線性處理
{
for (oldcol = 0; oldcol < 640; oldcol++) { // for each column in the row
newrow = oldrow + delta_x; // shift along x-dimension
newcol = oldcol + delta_y; // shift along y-dimension
send(oldrow, oldcol, newrow, newcol, Pmaster); // send out new coordinates
}
}上述程式框架就是完全按照主從結構進行撰寫的，我們可以發現，在master process中我們需要完成資料拆分、發送、接收，在slave process中我們需要完成資料計算（對于embarrassingly parallel來說這部分相對簡單），
按照上述程式框架我們需要在master process中考慮：一、資料如何拆分；二、各個subdata如何合理的分配到不同的processer（ Load Balancing 負載均衡）；因為往往并行程式的執行時間是由執行時間最長的process決定的，所以盡量讓每個processer平均高效的完成作業才是最重要的，
3、易并行程式的優化
在給processer分配任務程序中，主要分為兩大類： Static Load-Balancing （靜態分配）、 Dynamic Load Balancing （動態分配），
3.1、Static Load-Balancing （靜態分配）
常見的靜態分配有 1、Round robin algorithm — selects processes in turn 2、 Randomized algorithms — selects processes randomly
靜態分配就如上面這個程式處理邏輯一樣，在master中就將subdata分割好，每個processer中傳入的subdata是可以確定的，對于簡單的問題這樣分配任務是沒問題的，但是對于復雜的問題（尤其是不同的subdata執行的時間不同），那這樣靜態分配會導致有些processer特別忙、有些processer又處于空閑，導致如下的時間分配問題：
就像單位用人一樣，相同的任務量不同的人完成的時間不同，需要根據能力分配任務，能者多勞，照顧新人，
3.2、Dynamic Load Balancing （動態分配）
一般來說對于復雜并行處理問題，尤其是無法確定slave process處理時間的問題，都需要用到動態分配，常見的動態分配演算法有：1、 Centralized Work Pool ；2、 Decentralized Work Pool ；3、Fully Distributed Work Pool ，
3.2.1 Centralized Work Pool（作業池）
先上程式框架：
??主程式
//master process
count = 0; // # of active processes
row = 0; // row being sent
for (i=0; i<num_proc; i++) { // send initial row to each processes
send(row, Pi , data_tag); //先輪流送給每一個processer
count++;
row++;
}
do {
recv(&slave, &r, color, PANY , result_tag); //收到某個執行緒完成的作業結果
count--;
if (row < num_row) { // keep sending until no new task 如果row還沒完成
send(row, Pslave , data_tag); // send next row 發送下一行資料
count++;
row++;
}
else {
send(row, Pslave , terminate_tag); // terminate 讓這個process終止
}
display(r, color); // display row
} while(count > 0);??從程式
//slave process P ( i )
recv(&row, Pmaster , source_tag);
while (source_tag == data_tag) { // keep receiving new task
c.imag = min_imag + (row * scale_image);
for (x=0; x<640; x++) {
c.real = min_real + (x * scale_real);
color[x] = cal_pixel (c); // compute color of a single row
}
send(i, row, color, Pmaster , result_tag); // send process id and results
recv(&row, Pmaster , source_tag);
}上述程式其實是用來計算曼德勃羅數集的一部分，首先master連續的給所有processer分配任務，誰先做完任務則回來取下一個任務，這樣就實作了基本的動態平衡，
3.2.2 Decentralized Work Pool （分散的作業池）
這個動態分配演算法，是在 Centralized Work Pool（作業池）上進行的改進，前者完全依賴master來分配任務，這里在每個processer中可以再進行一次任務的分配，
3.3.3 Fully Distributed Work Pool （完全分布式的作業池）
特點： 每個process擁有或生成自己的任務，而且process之間互相通信可以互相傳遞任務（偷任務），很明顯這種結構程式邏輯撰寫難度較大、而且processer之間的通信壓力也很大，但是任務分配的更加平均，
4、易并行程式舉例
CS542200 Parallel Programming 中的 Homework 2:要求計算Mandelbrot Set（曼德勃羅數集），等啥時候寫完啥時候上傳吧，先貼一張Mandelbrot Set圖，曼德勃羅數集一般用于影像分形學，而且每個像素點的迭代時間無法確定（屬于易并行編程問題，但需要動態分配任務），
-----------------------------------------------------------------------------
上述圖片摘自《CS542200 Parallel Programming 》、《并行程式設計》
該文章為原創，轉載請注明出處，
-----------------------------------------------------------------------------
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/378084.html
標籤：C++