使用OpenMP进行并行加速

Question

我有两种测量指标的方案,如计算时间和并行加速(sequential_time/parallel_time).

场景1:

顺序时间测量:

startTime=omp_get_wtime();  
for loop computation  
endTime=omp_get_wtime();  
seq_time = endTime-startTime;

并行时间测量:

startTime = omp_get_wtime();  
for loop computation (#pragma omp parallel for reduction (+:pi) private (i)  
for (blah blah) {   
    computation;   
}  
endTime=omp_get_wtime();  
paralleltime = endTime-startTime; 

speedup = seq_time/paralleltime;

场景2:

顺序时间测量:

for loop{  
startTime=omp_get_wtime();  
   computation;  
endTime=omp_get_wtime();  
seq_time += endTime-startTime;  
}

并行时间测量:

for loop computation (#pragma omp parallel for reduction (+:pi, paralleltime) private (i,startTime,endTime)  
for (blah blah) {  
    startTime=omp_get_wtime();  
    computation;  
    endTime=omp_get_wtime();  
    paralleltime = endTime-startTime;  
}  

speedup = seq_time/paralleltime;

我知道场景2不是最好的生产代码,但我认为它通过忽略openmp生成和管理(线程上下文切换)几个线程所涉及的开销来衡量实际的理论性能.所以它会给我们一个线性加速.但是场景1考虑了产生和管理线程所涉及的开销.

我的疑问是这样的:在场景1中,我得到一个开始线性的加速,但随着我们移动到更高的迭代次数逐渐减少.在场景2中,无论迭代次数如何,我都会获得完整的线性加速.我被告知,实际上,无论迭代次数如何,场景1都会给我一个线性加速.但我认为它不会因为线程管理导致的高过载.有人可以向我解释为什么我错了吗？

谢谢!对于相当长的帖子感到抱歉.

Answer 1

在很多情况下,方案2也不会给你线性加速 - 线程之间的错误共享(或者,就此而言,真正共享被修改的共享变量),内存带宽争用等.子线性加速通常是真实的,不是测量神器.

更一般地说,一旦你达到了将计时器放入循环的程度,你就会考虑使用更精细的计时信息而不是使用这样的计时器进行测量.您可能希望能够将线程管理开销从实际工作中解脱出来,原因有多种,但是在这里您要尝试通过插入N个额外函数调用来实现omp_get_wtime(),以及算术和减少操作,所有这些操作都会产生不可忽视的开销.

如果你真的想要准确计算computation;在线上花费多少时间,你真的想要使用像采样而不是手动仪器这样的东西(我们在这里谈一下这里的区别).使用gprof或scalasca或openspeedshop(所有免费软件)或英特尔的VTune或其他东西(商业软件包)将为您提供有关在该行上花费多少时间的信息 - 通常甚至通过线程 - 以更低的开销.

Answer 2

首先,通过加速的定义,您应该使用方案1,其中包括并行开销.

在方案2中,测量中的代码错误paralleltime.为了满足方案2中的目标,您需要paralleltime通过分配int paralleltime[NUM_THREADS]和访问它们来获得每个线程omp_get_thread_num()(请注意,此代码将具有错误共享,因此您最好使用填充分配64字节结构).然后,测量每线程计算时间,最后用最长的计算一个不同类型的加速(我说的是一种并行性).

不,你甚至可以看到场景2的亚线性加速,甚至可以获得超线性加速.潜在原因(即排除并行开销)是:

1. 负载不平衡:compuation迭代时工作负载长度不同.这将是低速加速的最常见原因(但是,你说负载不平衡并非如此).
2. 同步成本:如果存在任何类型的同步(例如,互斥,事件,屏障),则可能需要等待/阻止时间.
3. computation高速缓存和内存成本:当需要大带宽和高工作集时,并行代码可能会受到带宽限制(尽管实际上很少见)和高速缓存冲突.此外,虚假共享是一个重要原因,但很容易避免它.还可以观察到超线性效应,因为使用多核可以具有更多高速缓存(即,私有L1/L2高速缓存).

在场景1中,它将包括并行库的开销:

1. 分叉/连接线程:尽管大多数并行库实现不会在每个并行构造上进行物理线程创建/终止.
2. 调度/加入逻辑任务:即使已经创建了物理线程,您也需要将逻辑任务分派给每个线程(通常是M任务到N线程),并且还在最后执行一种连接操作(例如,隐式屏障) .
3. 调度开销:对于静态调度(如您的代码所示,它使用OpenMP的静态调度),开销很小.当工作负载足够时(例如0.1秒),您可以安全地忽略开销.但是,动态调度(例如TBB中的工作窃取)会产生一些开销,但是一旦您的工作负载足够,它就不重要了.

我不认为您的代码(1级静态调度并行循环)由于线程管理而确实具有高并行开销,除非此代码每秒被调用数百万次.所以,可能是我在上面提到的其他原因.

请记住,有许多因素会决定加速; 从固有的并行性(=负载不平衡和同步)到并行库的开销(例如,调度开销).