[读综述] 确定性并行技术

发布网友 发布时间：2024-09-07 02:09

我来回答

共1个回答

热心网友 时间：2024-09-24 19:20

并行程序的不确定性来源于执行个体之间的同步、竞争和干扰，使得并行程序的执行结果变得不可预测。不确定性是目前并行程序发展的障碍，确定性并行技术的出现为解决这一问题提供了可能，它使程序的执行结果仅依赖于输入，从根本上解决了不确定性带来的问题。

多线程并行与多进程并行是并行程序的两种主要形式。这两种形式在实现并行计算的过程中均存在不确定性执行的问题。在多线程并行中，线程对于共享内存的竞争访问是导致程序不确定性的主要因素，包括数据竞争和同步竞争。同步竞争是线程通过原子指令对同步变量的竞争访问。而在多进程程序中，MPI消息传递并行模式中的异步消息传递函数和混杂消息接收函数可能导致程序执行状态的不确定性。

程序中还存在非并行因素导致的不确定性，例如对随机数发生器函数的调用。这类不确定性是人为引入的，程序逻辑本身需要这种不确定性，因此属于可控的不确定性，不在确定性并行技术的研究范畴之内。

确定性并行技术的目标是消除并行引起的不确定性，降低并行程序的开发和维护成本，提高程序的可靠性。与确定性并行技术相关的技术包括记录-回放技术、数据竞争检测技术等，它们的核心是发现并控制程序中的数据竞争，但各有不同的目标和侧重。

数据竞争检测技术能检测和自动消除部分数据竞争，但无法实现确定性。记录-回放技术虽然能实现确定性，但只能保证程序在特定输入下的确定性。确定性并行技术不需要外部日志的支持，实现的是程序内在的确定性，能够实现首次确定性，即第一次运行时就保持确定性。

确定性并行技术包括确定性编程语言、确定性运行时系统、确定性操作系统、确定性编程模型和确定性算法等。其中，确定性运行时系统是确定性并行领域最重要的一个研究分支。

轮转法是确定性并行技术的一种实现方式。DMP算法将程序分成轮，每一轮内线程执行一定数量的指令。并行阶段内线程之间的访存不冲突，可以持续执行；一旦发生冲突，则进入串行阶段解决冲突。在串行阶段，线程按ID顺序依次执行，从而以确定的方式解决了不确定性问题。然而，纯软件的DMP实现会有2~10倍的性能开销。

弱确定性算法通过牺牲一部分确定性来提高性能，Kendo算法利用逻辑时钟对线程的加锁机会进行排序，保证了程序加锁顺序的确定性。这种算法性能开销较小，仅不到16%。

CoreDet系统和RCDC系统采用Total Store Order弱内存一致性模型和Data Race Free（DRF）放松一致性模型来优化性能，通过分轮执行和本地副本操作，消除访存冲突。然而，这两种方法的性能提升有限，仍有2~8倍的性能开销。

Dthreads确定性系统采用页面保护机制隔离线程内存空间，消除访存冲突。每个线程拥有的页表，实现对共享内存的不同访问权限，并在修改共享内存时做写时复制。Dthreads的性能开销平均不超过2倍，但某些程序的开销可达到8倍。性能提升主要源于页面保护机制和指令分块粒度的优化。

全局同步问题是确定性系统引入的一种额外的同步点，它要求所有线程在该点暂停执行，以便处理不确定性。全局同步可能导致正确性和性能问题，因为它是确定性系统而非程序固有的同步策略。

稳定性是多线程程序的重要特性，然而确定性系统可能破坏程序的稳定性。相关系统包括Tern和Peregrine。确定性多进程的系统如dOS、DDOS、Determinitor等，是采用多进程并行方式的实例，例如Apache服务器和Chrome浏览器。