新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

【聊聊并行計算】Embarrassingly Parallel（易并行計算問題）

1、什么是Embarrassingly Parallel（易并行計算問題）

易并行計算問題：A computation that can be divided into a number of completelyindependenttasks。在編寫并行程序過程中，首先需要將一個問題分解成若干部分，然后將每個部分分配給不同的processer（處理器）或者thread（線程）分別進行計算，如果該計算問題能夠被分解成一些完全獨立的子計算（task）、同時各個task之間數(shù)據(jù)幾乎沒有依賴，沒有通信。那這個計算問題就叫作易并行計算問題。

在奉賢等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務理念，為客戶提供成都網(wǎng)站建設、做網(wǎng)站網(wǎng)站設計制作按需策劃設計,公司網(wǎng)站建設,企業(yè)網(wǎng)站建設,品牌網(wǎng)站制作,全網(wǎng)營銷推廣,外貿(mào)網(wǎng)站制作,奉賢網(wǎng)站建設費用合理。

對于該問題一般程序處理流程如下：

對于輸入的Data，直接拆分成幾塊互相沒有依賴的Subdata,每一份Subdata具有完全相同的處理方式，最后再將subdata的處理結(jié)果合并行輸出，對于這類數(shù)據(jù)計算問題，就天然的適用于并行計算。尤其是在圖像處理方面，并行處理的情況很多。

在對圖像進行平移、旋轉(zhuǎn)、縮放過程中，對于每一個pixel(像素點)數(shù)據(jù)都是完全相同的操作，當然我們可以寫一個兩層for循環(huán)，遍歷每個pixel，然后對每個pixel進行轉(zhuǎn)換，但這樣效率很低。按照并行編程的思路，我們可以對一幅圖像不同的像素點進行拆分，送到不同processer，同時進行圖像計算，這樣就實現(xiàn)了圖像計算的加速。理想情況下，對于每個piexl，咱們都送到一個processer中進行計算，這樣效率最高。但實際情況是，往往processer或者thread開啟的數(shù)量也是有限度的，就像高速公路分流一樣，不可能無限制的擴寬車道，所以咱們需要對一整個Data進行合理的拆分，將一塊數(shù)據(jù)送入processer中進行處理。正如上圖所示，對于原始圖像的拆分可以分塊、分行、分列，不同的分割方式對最后運行效率也是有一定影響的。

2、易并行計算需要考慮的問題

對于易并行計算問題，雖然數(shù)據(jù)很容易進行拆分處理，但在實際編寫程序過程中往往會遇到兩個問題，首先我們看一下并行編程的程序框架。

對于圖像的平移處理，一般并行程序由主從結(jié)構(gòu)構(gòu)成，主程序用來對數(shù)據(jù)進行拆分，送到不同的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. 
} //數(shù)據(jù)拆分 以及發(fā)送
for(i=0; i<480; i++){
  for(j=0; j<640; j++) {
    temp_map[i][j] = 0; // initialize temp 緩沖數(shù)組
  }
}
for(i=0; i<(480*640); i++) { // for each pixel
	recv(oldrow, oldcol, newrow, newcol, PANY); // accept new coordinates 數(shù)據(jù)接收
	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
	}
}

上述程序框架就是完全按照主從結(jié)構(gòu)進行編寫的，我們可以發(fā)現(xiàn)，在master process中我們需要完成數(shù)據(jù)拆分、發(fā)送、接收。在slave process中我們需要完成數(shù)據(jù)計算（對于embarrassingly parallel來說這部分相對簡單）。

按照上述程序框架我們需要在master process中考慮：一、數(shù)據(jù)如何拆分；二、各個subdata如何合理的分配到不同的processer（ Load Balancing 負載均衡）；因為往往并行程序的執(zhí)行時間是由執(zhí)行時間最長的process決定的，所以盡量讓每個processer平均高效的完成工作才是最重要的。

3、易并行程序的優(yōu)化

在給processer分配任務過程中，主要分為兩大類： Static Load-Balancing（靜態(tài)分配）、 Dynamic Load Balancing（動態(tài)分配）。

3.1、Static Load-Balancing （靜態(tài)分配）

常見的靜態(tài)分配有 1、Round robin algorithm — selects processes in turn 2、 Randomized algorithms — selects processes randomly

靜態(tài)分配就如上面這個程序處理邏輯一樣，在master中就將subdata分割好，每個processer中傳入的subdata是可以確定的，對于簡單的問題這樣分配任務是沒問題的，但是對于復雜的問題（尤其是不同的subdata執(zhí)行的時間不同），那這樣靜態(tài)分配會導致有些processer特別忙、有些processer又處于空閑，導致如下的時間分配問題：

就像單位用人一樣，相同的任務量不同的人完成的時間不同，需要根據(jù)能力分配任務，能者多勞，照顧新人。

3.2、Dynamic Load Balancing （動態(tài)分配）

一般來說對于復雜并行處理問題，尤其是無法確定slave process處理時間的問題，都需要用到動態(tài)分配。常見的動態(tài)分配算法有：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 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);
}

上述程序其實是用來計算曼德勃羅數(shù)集的一部分，首先master連續(xù)的給所有processer分配任務，誰先做完任務則回來取下一個任務，這樣就實現(xiàn)了基本的動態(tài)平衡。

3.2.2 Decentralized Work Pool （分散的工作池）

這個動態(tài)分配算法，是在Centralized Work Pool（工作池）上進行的改進，前者完全依賴master來分配任務，這里在每個processer中可以再進行一次任務的分配。

3.3.3 Fully Distributed Work Pool（完全分布式的工作池）

特點：每個process擁有或生成自己的任務，而且process之間互相通信可以互相傳遞任務（偷任務），很明顯這種結(jié)構(gòu)程序邏輯編寫難度較大、而且processer之間的通信壓力也很大，但是任務分配的更加平均。

4、易并行程序舉例

CS Parallel Programming中的 Homework 2:要求計算Mandelbrot Set（曼德勃羅數(shù)集),曼德勃羅數(shù)集一般用于圖像分形學，而且每個像素點的迭代時間無法確定（屬于易并行編程問題，但需要動態(tài)分配任務）。

OpenMP版本（開啟16個子線程，動態(tài)分配任務，哪個thread算完，就回work pool取出新值）

// 程序名稱：分形學 - Mandelbrot Set (曼德布洛特集)
// 編譯環(huán)境：vs2019
// 最后更新：2021-12-11
// author ：aalan
#include 
#include 
#include 
#include 
// 定義復數(shù)及乘、加運算
// 定義復數(shù)
struct COMPLEX
{
	double re;
	double im;
};
// 定義復數(shù)“乘”運算
COMPLEX operator * (COMPLEX a, COMPLEX b)
{
	COMPLEX c;
	c.re = a.re * b.re - a.im * b.im;
	c.im = a.im * b.re + a.re * b.im;
	return c;
}
// 定義復數(shù)“加”運算
COMPLEX operator + (COMPLEX a, COMPLEX b)
{
	COMPLEX c;
	c.re = a.re + b.re;
	c.im = a.im + b.im;
	return c;
}
// 主函數(shù)
int main()
{
	// 初始化繪圖新窗口 
	initgraph(640, 480,1);
	// 繪制 Mandelbrot Set (曼德布洛特集)
	COMPLEX z, c;
	int index,x, y, k;	// 定義循環(huán)變量
#pragma omp parallel num_threads(16)
	{
	#pragma omp for schedule(dynamic)private(x,y,k,z,c) //誰先算完誰去取下一次計算
		for (index = 0; index < 64; index++)
		{
			printf("index=%d thread = %d\n", index,omp_get_thread_num());
			for (x = index*10; x < index*10 + 10; x++) {
				c.re = -2.1 + (1.1 - -2.1) * (x / 640.0);
				for (y = 0; y < 480; y++)
				{
					c.im = -1.2 + (1.2 - -1.2) * (y / 480.0);
					z.re = z.im = 0;

					for (k = 0; k < 180; k++)
					{
						if (z.re * z.re + z.im * z.im > 4.0)	break;
						z = z * z + c;
					}
					putpixel(x, y, (k >= 180) ? 0 : HSLtoRGB((float)((k << 5) % 360), 1.0, 0.5));
				}
			}
		}
	}
	// 按任意鍵退出
	_getch();
	closegraph();
	return 0;
}

-----------------------------------------------------------------------------

上述圖片摘自《CS Parallel Programming》、《并行程序設計》

該文章為原創(chuàng)，轉(zhuǎn)載請注明出處。