分布式硬件路障结构实现模糊同步的方法

摘要

同步对并行多处理机的性能有很大的影响。并行程序通常使用路障对并行进程达成同步。在到达路障时，处理机必须进行空闲等待直到所有的处理机都到达路障。用软件方法实现路障需要执行一些多余的同步指令，会产生不必要的开销或引起热点访问的问题。处理机到达路障后等待其它处理机时处于空闲状态不能做其它的工作。模糊同步的提出扩展了路障的概念，处理机在等待同步时能够在一个构造的区域内继续执行，而不需要软件路障同步那样的空闲等待。由编译器构造的路障区包括一些指令，当处理机到达这个区域时发出准备同步信号，在退出这个区域时必须实现同步。在达成同步的时候，处理机可能执行到这个区域内的任意一点。这个区域构造的越大，越不会产生空闲等待。本文提出了一种分布式的硬件路障结构，可以用于构建大规模的机群多处理机实现快速同步。以这种机群结构为基础可以构建阶层式大规模并行多处理机系统。提出了一组用于实现模糊路障同步的原语。这种结构的多功能性，可扩展性，可编程性和低开销可以很好地适用于细粒度的大规模MIMD系统。 关健词：同步，模糊路障，硬件路障

目录

文摘

英文文摘

南开大学学位论文版权使用授权书及南开大学学位论文原创性声明

第一章引言

第二章同步基本原理

第一节同步的几个基本概念

2.1.1原子操作

2.1.2 临界区(critical region)

2.1.3互斥和原子操作的区别

第二节多处理机系统同步原理

2.2.1同步概述

2.2.2等待算法

2.2.3公平策略

2.2.4单独访问协议

2.2.5同步的环境

第三节并行多处理机中的同步结构

2.3.1高级同步结构

2.3.2低级同步结构

2.3.3改进的锁算法

第三章模糊路障(Fuzzy barrier)同步问题

第一节Fuzzy barrier概述

3.1.1路障同步存在的问题

3.1.2解决路障同步中存在的问题

3.1.3模糊同步与路障同步

第二节模糊同步的语义

3.2.1模糊同步的定义

3.2.2模糊同步中的死锁

第三节路障区构造过程

3.3.1并行结构的实现

3.3.2并行优化编译器

3.3.3构造非路障区

3.3.4码重排技术(code reordering)

3.3.5扩大路障区

3.3.6多重路障

3.3.7模糊路障同步的实现

第四节模糊路障同步的其它应用

3.4.1分支结构路障区的构造

3.4.2循环迭代的静态调度

3.4.3循环迭代的动态调度

第四章路障同步的硬件实现及算法

第一节简单路障同步硬件实现

第二节快速路障同步硬件实现及算法

4.2.1概述

4.2.2单一路障硬件

4.2.3多重并发路障硬件

4.2.4路障模型的扩展

4.2.5路障同步算法

4.2.6仿真结果

第五章分布式硬件路障同步结构

第一节简述

第二节构成原理

第三节分布式硬件路障同步开销

第四节模糊路障同步原语

第六章结束语

致谢

参考文献