BSP并行库及其回卷恢复机制在SMP集群系统上的实现

摘要

该文主要介绍我们开发的BSP并行环境库系统SHUBSP(Shanghai University BSP Library)及其回卷恢复机制的设计与实现.和其他并行环境相比,SHUBSP针对SMP集群系统的结构特点,在实现上采用了一些新的方法,更能充分发挥出SMP集群系统的性能.采用自动线程化的方法,使传统意义上BSP计算进程作为线程运行,大大减少了计算进程产生、终止和切换的系统开销,而且使相同SMP结点上的计算进程可通过直接内存与通信;采用变量地址本地注册的方法,避免了由变量地址注册而引起的巨大通信开销;提出结点配对的算法安排网络传输,实现了结点间并发无冲突的高效通信;采用结点同步和微同步两层同步实现全局同步.最后,我们还对SHUBSP库进行性能测试和结果分析,并和其他BSP库如PUB7.0进行比较.在实现BSP并行库系统的基础上,考虑到容错功能对集群系统的重要性,我们为SHUBSP系统实现了基于检查点设置和回卷恢复的容错机制.结合BSP模型的结构特点,我们提出的检查点算法:时钟和超步驱动的检查点算法,实现了无多米诺效应、无回卷距离的同步一致检查点算法.通过对linux线程库和linux内核源代码的细致分析,我们首次为并行库系统实现了线程级的容错,为线程容错问题的探讨提供了一些参考的方法.

目录

文摘

英文文摘

第一章绪论

1.1研究背景

1.2本文的研究工作

1.3本文的结构

第二章SHUBSP的实现

2.1 BSP计算模型概论

2.1.1 BSP模型的组成与特征

2.1.2 BSP模型的程序设计方法

2.1.3 BSP模型的开销计算

2.2并行环境的研究动态

2.3设计与实现

2.3.1 BSP进程线程化的方法

2.3.2变量地址本地注册

2.3.3 BSP通信函数接口的实现

2.3.4 BSP通信和同步

2.4实验环境和测试数据

2.4.1基准测试程序

2.4.2测试结果和性能比较

第三章回卷恢复机制的实现

3.1容错技术介绍

3.2 LINUX线程库的实现机制

3.2.1线程的实现方式与API标准

3.2.2 Linux内核级线程的实现机制

3.2.3 Linuxthreads库中多线程的实现

3.3检查点算法

3.3.1基本概念

3.3.2系统模型

3.3.3单进程检查点算法

3.3.4分布式检查点算法

3.3.5时钟和超步共同驱动的检查点算法

3.4回卷恢复的实现

3.4.1进程状态

3.4.2进程状态的保存

3.4.3进程状态的恢复

第四章结论和进一步工作

5.1结论

5.2进一步的工作

参考文献

作者攻读学位论文期间公开发表的论文

致 谢