探索确定性的共享内存并行编程模型

摘要

多核处理器的兴起使得并行软件变得越来越重要，但是目前并行软件的发展远远落后于并行硬件。作为一种主流的并行编程环境，共享内存并行编程中存在大量的不确定性，这些不确定性增加了并行编程的复杂性，严重阻碍了并行程序的发展。
　　 共享内存并行编程中的不确定性大多数是由于编程模型的不确定性导致的，为此本文探索一个确定性共享内存编程模型，目标是在保证确定性的同时保持较好的性能。本文探讨并完成了以下工作：
　　 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能使并行程序的编写、调试和测试变得容易，从而可以促进并行程序的发展。

目录

声明

摘要

第1章 绪论

1．1 问题描述

1．2 相关工作与研究现状

1．2．1 “共享存储器编程模型”的现状和问题

1．2．2 并行程序确定性研究现状

1．3 研究内容

1．4 论文组织

第2章 基础知识

2．1 基本框架

2．2 Determinator

2．3 SPMC虚拟内存基础

2．4 DetMP

2．4．1 接口

2．4．2 实现

2．5 Lazy Page Mapping

2．6 Space Extension

2．7 研究思路

2．8 本章小结

第3章 dedup案例分析

3．1 dedup

3．1．1 程序结构

3．1．2 全局数据流关系

3．2 共享资源使用模式

3．2．1 IR：只读共享

3．2．2 IWR：仅写一次

3．2．3 IWRWR：被多次写入

3．3 本章小结

第4章 DetSM的设计与实现

4．1设计思路

4．2 DetSM

4．3 接口

4．3．1 确定性的内存分配

4．3．2 权限传递

4．3．3 确定性的读写

4．3．4 程序实例

4．4 实现

4．4．1 SMU元数据

4．4．2 权限传递的实现

4．5 讨论

4．5．1 全局数据在DetSM中的解决方案

4．5．2 DetSM的确定性

4．5．3 DetSM VS．Pthreads

4．5．4 权限传递：DetSM vs．Lock

4．5．5 额外开销分析

4．5．6 Fix粒度

4．5．7 空间拓展

4．6 本章小结

第5章 实验结果和分析

5．1 重写dedup

5．1．1 线程间通信——对全局变量的处理

5．1．2 调度策略

5．1．3 实验测试结果及其分析

5．1．4 讨论

5．2 快速排序

5．2．1 算法描述

5．2．2 实验测试结果及其分析

5．3 本章小结

第6章 DetArray的设计与实现

6．1 设计思路

6．2 DetArray的接口和实现

6．2．1 DetArray的一个应用实例

6．2．2 DetArray vs．DetSM

6．3 实验结果和分析

6．4 本章小结

第7章 结束语

7．1 主要贡献

7．2 不足和将来的工作

参考文献

图目录

表目录

致谢

在读期间发表的学术论文与取得的研究成果