论文部分内容阅读
多核处理器的兴起使得并行软件变得越来越重要，但是目前并行软件的发展远远落后于并行硬件。作为一种主流的并行编程环境，共享内存并行编程中存在大量的不确定性，这些不确定性增加了并行编程的复杂性，严重阻碍了并行程序的发展。
共享内存并行编程中的不确定性大多数是由于编程模型的不确定性导致的，为此本文探索一个确定性共享内存编程模型，目标是在保证确定性的同时保持较好的性能。本文探讨并完成了以下工作：
1、设计了一个确定性的共享内存编程模型—DetSM。
本文首先以dedup为例分析、总结共享内存并行编程中共享资源的访问模式。然后根据总结的访问模式，本文提出了一个确定性共享内存并行编程模型——DetSM（deterministic shared memory programming model）。DetSM提供了一个特殊的抽象数据结构——SMU(Shared Memorv Unit)，用于进程间通信。SMU的特点是：多期和权限传递。一个SMU的生命期可以分为多个期——periods，为了保证确定性，每个期最多只能有一个写者。当某个SMU的一个期结束以后，该SMU的写权限就可以被传递给下一个期的写者进程。
2、在SMU上拓展了一个确定性的并行数组数据结构DetArray。
为了支持这种数组访问模式——不同进程能够并行地访问数组的不相交部分，笔者对SMU进行了拓展，提出了一种适合于这种特殊应用的数组类型DetArray（deterministic array data structure）。DetArray的特点是：可以被确定性地并行操作。DetArray在物理内存上不一定连续，不能用逻辑索引来计算其物理地址。一个DetArray可以被分为多个部分(sections)，每个部分都有自己的读者和写者。不同写者进程可以并行地操作一个DetArray的不同部分。
3、在Determinator上对DetSM和DetArray进行了实现和实验测试。
笔者在Determinator上利用SPMC（single-producer multiple-consumer）虚拟内存基础实现了DetSM和DetArray，然后用DetSM重写了dedup，用DetArray改写了归并排序。dedup的实验结果表明：在较大输入集上，DetSM的性能和Pthreads相当，甚至好于Pthreads。DetArray的例子表明：DetArray不仅能为并行编程提供方便，而且还具有较好的性能，它具有非常好的可扩展性。
DetSM和DetArray能使并行程序的编写、调试和测试变得容易，从而可以促进并行程序的发展。