前缀和计算在并行计算中很有用,因为在处理负载平衡问题时,经常需要将若干段数据重新平分,计算前缀和通常是一种有效的将数据平分的方法。例如在并行基数排序中,就会用到了前缀和的计算。而下面先看看单线程环境中的串行前缀和计算。
如果给定一个数列a[n],令S[k] = <?xml:namespace prefix = v ns = "urn:schemas-microsoft-com:vml" /><shapetype id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f"><stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"></path><?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" /><lock v:ext="edit" aspectratio="t"></lock></shapetype><shape id="_x0000_i1025" style="WIDTH: 33.75pt; HEIGHT: 33.75pt" type="#_x0000_t75" o:ole=""><imagedata src="file:///C:%5CDOCUME~1%5Crose%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image001.wmz" o:title=""></imagedata></shape>a[0]+a[1]+...+a[k],(k = 0, 1, 2…n-1),数列S[k]即为数列a[n]的前缀和。例如下面一列数据:
a[4] = {1, 2, 3, 4};
其前缀和为
S[0] = a[0] = 1;
S[1] = a[0] + a[1] = 1+ 2 = 3;
S[2] = a[0] + a[1] + a[2] = 1 + 2 + 3 = 6;
S[3] = a[0] + a[1] + a[2] + a[3] = 1 + 2 + 3 + 4 = 10;
前缀和的计算非常简单,一般地,可以用下面的函数来进行串行前缀和的计算:
/** 串行前缀和计算函数
@param T * pInput - 输入数据
@param T *pOutput - 输出数据(前缀和)
@param int nLen - 输入数据长度
@return void - 无
*/
template <class T>
void Sequential_PrefixSum(T * pInput, T *pOutput, int nLen)
{
int i;
pOutput[0] = pInput[0];
for ( i = 1; i < nLen; i++ )
{
pOutput[i] = pInput[i] + pOutput[i-1];
}
}
在上面的串行前缀和计算代码中可以看出,每次循环都依赖于上一次循环的结果,因此无法直接对循环进行并行化,要进行并行化则必须修改计算方法,下面就来看如何进行并行前缀和的计算。
前缀和的并行计算方法有许多种,David Callahan的论文“Recognizing and Parallelizing Bounded Recurrences”中给出了一种适合共享存储多处理器系统中的有界递归计算的通用方法,前缀和计算属于有界递归计算的一个特例。下面先以一个实例来讲解整个并行计算的过程:
例:假设有4个处理器要计算16个整数的前缀和,这16个整数如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
第1步,先将上面数据平分成4组,每个处理器各计算一组数据的前缀和,如下所示:
(1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16)
(1 3 6 10) (5 11 18 26) (9 19 30 42) (13 27 42 58)
第2步,选取每组数据的最后一个数据,对这几个数据计算前缀和,如下所示:
(1 3 6 10) (5 11 18 26) (9 19 30 42) (13 27 42 58)
(1 3 6 10) (5 11 18 36) (9 19 30 78) (13 27 42 136)
经过这步的计算后,可以很容易发现,每组的最后一个数据的值已经变成了原始数据在它所处位置之前(包含本位置)的所有数据的和。例如:
36 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8
78 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12
第3步:从第2组数开始,将每组中的数(除最后一个数外)加上它的前一组数的最后一个数,即可得到所有数的前缀和。如下所示:
(1 3 6 10) (5+10 11+10 18+10 36) (9+36 19+36 30+36 78) (13+78 27+78 42+78 136)
(1 3 6 10) (15 21 28 36) (45 55 66 78) (91 105 120 136)
从上面的计算过程可以看出,第1步和第3步都是很容易进行并行化计算,第2步中,由于计算量非常小,用串行计算即可,下面给出上面处理过程的代码实现:
#define MIN_PRARLLEL_PREFIXSUM_COUNT 8192
/** 并行前缀和计算函数
@param T * pInput - 输入数据
@param T *pOutput - 输出数据(前缀和)
@param int nLen - 输入数据长度
@return void - 无
*/
template<class T>
void Parallel_PrefixSum(T * pInput, T *pOutput, int nLen)
{
int i;
int nCore = omp_get_num_procs();
if ( nCore < 4 || nLen < MIN_PRARLLEL_PREFIXSUM_COUNT )
{
Sequential_PrefixSum(pInput, pOutput, nLen);
return;
}
int nStep = nLen / nCore;
if ( nStep * nCore < nLen )
{
nStep += 1;
}
#pragma omp parallel for num_threads(nCore)
for ( i = 0; i < nCore; i++ )
{
int k;
int nStart = i * nStep;
int nEnd = (i+1) * nStep;
if ( nEnd > nLen )
{
nEnd = nLen;
}
pOutput[nStart] = pInput[nStart];
for ( k = nStart+1; k < nEnd; k++ )
{
pOutput[k] = pInput[k] + pOutput[k-1];
}
}
for ( i = 2; i < nCore; i++ )
{
pOutput[i * nStep - 1] += pOutput[(i-1) * nStep - 1];
}
pOutput[nLen-1] += pOutput[(nCore-1)*nStep - 1];
#pragma omp parallel for num_threads(nCore-1)
for ( i = 1; i < nCore; i++ )
{
int k;
int nStart = i * nStep;
int nEnd = (i+1) * nStep - 1;
if ( nEnd >= nLen )
{
nEnd = nLen - 1;
}
for ( k = nStart; k < nEnd; k++ )
{
pOutput[k] += pOutput[nStart-1];
}
}
return;
}
从上面并行前缀和的计算过程可以看出,它的计算量比串行前缀和的计算增加了差不多一倍,如果考虑程序中的实际开销,计算增加量还不止一倍。因此在双核CPU机器上,使用并行前缀和计算没有任何意义,只有在超过4核CPU机器上,它才有实用价值。
Parallel_PrefixSum()函数中,先是判断CPU核数是否小于4,并且判断了计算量是否不足,如果两个判断条件中有任何一个满足,则调用串行前缀核计算函数进行计算,然后才进行并行前缀和的计算。在并行计算时只是简单地将计算平摊到各个CPU上,没有考虑CPU核数较多情况下计算量平摊到各个CPU核上,线程粒度过小的问题,主要是为了不使代码看起来过于繁琐。如有需要可以修改成自动计算出最合适的线程数量(可能小于CPU核数),然后并行计算时使用相应的线程数量即可。
分享到:
相关推荐
讲义简要介绍采用Fortran语言和OpenMP技术进行并行计算的知识,配有视频教程,主要内容包括: 第一讲 OpenMP基础 第二讲 并行域 第三讲 OMP指令(上) 第四讲 OMP指令(下) 第五讲 THREADPRIVATE属性 第六讲 OMP并行...
随着多核乃至众核平台的普及,面向多核的并行编程和优化已成为计算机领域研究的热点。然而,绝大多数程序员还依然延续着传统的串行编程习惯,而且目前的主流算法仍以串行为主。因此,如何有效地将串行程序并行化和...
蒙特卡洛算法背景知识,算法描述,算法步骤,算法程序,简单明了。
仅供参考.。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
用微机多核CPU并行方式运转WRF模式.pdf
多核处理器并行计算模型研究.pdf
多核计算平台中MATLAB_并行计算工具包,非常好的东东哟,值得珍藏
《基于多核的并行程序设计》大学课程课件。
CELL处理器、Intel Core 2处理器的并行计算基本原理 Cell处理器并行编程基本技术:CELL处理器 pThread并行编程技术: Intel多核处理器、AMD多核处理器、SMP服务器 MPI并行编程技术:SMP多核服务器、CLUSTER、MPP...
2. 多核环境下并行访问共享/外部存储器的性能研究和设计原则分析。多核 DSP 中存在多个主设备,包括多个 DSP 内核、多个 EDMA 设备等,它们并行访 问存储器的数据带宽,对于应用程序存储资源的安排、软件结构的设计...
一个初学者觉得有用的入门级文档。内容有多线程并行和趋势展望
并行计算简介和多核CPU编程Demo.pdf
多核(64核)系统的并行FFT运算程序
多核处理器 和并行升序设计, 课件和一些实例源代码
详细介绍多核程序设计理论以及理论模型,并提供详细编程实例
有关于多核并行计算的,中国科学技术大学陈国良教授编写
基于多核的并行编程模型.docx
多核并行计算和CVN数据库系统教学PPT课件.pptx