并行编程中同步机制的设计、实现与验证

(英文版)

多核多处理器等以共享存储为特征的新一代系统结构的出现,加速了对快速研发基于共享资源的并行软件的需求。在基于共享资源的并行软件构造中,对共享资源访问的同步控制是其中的关键之一。共享资源在源语言级主要是共享变量,而在机器语言级则是寄存器、内存单元、状态标志等。为提高并行软件的生产率和可信度,源语言需要提供易于编程的高级同步抽象(而不是简单提供低级的锁等) ;编译运行系统则需要提供对这种高级同步抽象的正确且有效的实现。

现在流行的并行编程实践大都采用锁等较低级的同步设施用于共享变量的访问控制,编程难、易出错且不易组织能发挥多核多处理优势的编程。正在完善或研究的新型并行编程语言X10ChapelFortress等都通过引入原子代码区这种高级同步结构以使基于共享资源的并行编程没有显式的低级同步,但是尚存在一些相关的设计和实现上的问题有待解决。

在共享变量访问控制的实现方面,除使用锁等低级方式外,近年来主要研究的是事务内存技术。事务内存是一种编程抽象,它试图通过允许一组存取共享内存的指令(称为事务)原子且隔离地执行来简化并行编程。它是一种允许事务乐观地投机并行执行并在发现冲突时部分事务回滚到初始状态的、类似数据库事务的并发控制机制。事务虽具有其代码全都执行或全不执行的原子性和不受其他事务干扰的隔离性,但是事务的概念及其语义的具体设计必须考虑与现有操作系统、编程语言和程序代码等构成的丰富且复杂的开放世界的衔接,因此尚存一些问题有待解决。

一些特殊的共享变量访问控制可以通过无锁编程来实现。低级代码上无锁编程的主要实现基础是CAS(compare and swap)指令或者LL/SC(Load-Link/Store-Conditional)指令,无锁代码虽效率高但很难编写和维护。

本项目围绕基于共享资源的高生产率、高可信并行编程中同步机制的设计、实现和验证。研究分以下几个子项目展开: