1.5 无锁编程
互斥锁是用于同步进程或线程的常用机制,这些进程或线程需要访问并行程序中的一些共享资源。互斥锁就像它们名字所说的:如果一个线程锁住了资源,另一个线程希望访问它需要等待第一个线程解锁这个资源。一旦资源被解锁,第二个线程在处理这个资源时会一直锁住它。程序的线程必须遵守:一旦使用完共享资源尽快解锁,以保持程序执行流程。
由于OpenACC中没有锁,编程人员需要熟悉无锁编程和数据结构的概念。无锁方法保证至少一个执行该方法的线程的进展。可能存在某些线程可以被延迟的情况,但是保证至少一个线程在按步执行。从统计数据来看,所有线程随着时间的推移将在无锁方法上取得进展。根据Blechmann(2016)的研究,如果保证在一定数量的步骤中完成一些并发操作,则认为数据结构是无锁的。
强烈鼓励读者深入探索无锁编程和无锁数据结构,更多信息可以参考《多核编程的艺术》(Herlihy & Shavit, 2012)。
相比简单地使用锁来保护临界区域(OpenMP为例,#pragma omp critical),无锁编程更有挑战性。然而,基于锁的程序性能比无锁方法更差。实践中,锁是限制或阻止扩展的常见罪魁祸首。无锁编程也需要避免死锁问题。死锁可能发生在两个线程停滞等待另一个线程释放共享资源时。
一个增加计数器问题扩展性的简单解决方法是减少一个或多个线程需要排队执行原子操作的概率。如图1-21所示,这可以通过accParaCounter.cpp中的一对嵌套循环实现。
上述accParaCounter.cpp的源码很不起眼,但是在下一节中将用于实现更有趣的并行随机数生成器(PRNG)代码。蒙特卡罗方法是科学和金融计算的关键部分,随机生成数是这个方法的关键。鼓励读者深入地研究随机生成数和蒙特卡罗方法。
从accParaCounter.cpp源码可以看到,并行for循环拆分为两个嵌套循环:(1)外层循环使用nPartial增量,(2)内层循环利用工作项并行来增加局部变量nPartial次。
下面是改进的扩展图,显示了嵌套内层循环1000次的accParaCounter.cpp性能。并行性能更好,超过了串行版本(见图1-22)。