Algorithm 版 (精华区)

发信人: sigmod (sigmod), 信区: Algorithm
标  题: 曙光1000A上的共享存储并行环境
发信站: 哈工大紫丁香 (2001年11月14日12:32:09 星期三), 站内信件

曙光1000A上的共享存储并行环境
胡伟武     施巍松     唐志敏
中国科学院计算技术研究所    北京2704信箱25分箱(100080)
Email:{hww,wsshi,tang}@water.chpc.ict.ac.cn
摘  要  本文介绍了曙光1000A上的一个共享虚拟存储系统JIAJIA。JIAJIA为曙光
1000A提供了除PVM和MPI之外的另一并行编程环境，并且是第一个共享存储编程环
境。与目前国际上具有代表性的共享虚拟存储系统如TreadMarks、CVM和Quarks等
比较， JIAJIA系统能充分利用多个机器的物理存储器来组成一个更大的共享虚拟
空间，因此程序员可以利用的共享地址空间可以是所有机器的物理空间的总和。此
外，JIAJIA采用一种基于锁的新型CACHE一致性协议来实现数据一致性，避免了传
统的基于目录的CACHE一致性协议中目录引起的存储开销和系统复杂度。我们用一
些典型的应用程序对JIAJIA系统的性能进行了分析。计算结果表明，同近期实现的
共享虚拟存储系统如CVM比较，JIAJIA不仅具有更高的性能， 而且可以解决更大规
模的问题。
关键词：曙光1000A，共享虚拟存储系统，基于锁的一致性协议，域存储一致性模
型
1. 引言
从用户界面和存储管理的角度看，并行计算机系统可分为共享存储多处理机系统和
消息传递多计算机系统两类。在多处理机系统中，所有处理机共享主存储器。而在
消息传递的多计算机系统中，每个处理机都有一个只有它自己才能访问的局部存储
器，处理机之间的通信必须通过显式的消息传递来进行。消息传递多计算机和共享
存储多处理机的结构原理如下图 1所示，从图中可以看出，在消息传递的多计算机
系统中，每个处理机的存储器是单独编址的；而在共享存储多处理机中，所有存储
器统一编址。
与消息传递系统相比，共享存储系统由于支持传统计算机的单地址编程空间，从而
减轻了程序员的负担，因此具有较强的通用性，且可以方便地移植现有的应用软件
。但共享存储系统需要复杂的硬件来维护全局的地址空间以及CACHE一致性，因而
系统可伸缩性较差。针对消息传递系统和共享存储系统各自的问题，人们提出了共
享虚拟存储(Shared Virtual Memory，简称SVM，又称软件DSM)系统的概念，即在
消息传递系统上通过软件或软硬结合的办法实现共享存储的编程界面。在过去的十
年中，SVM系统由于结合了共享存储系统的易编程性和消息传递系统的易扩展性而
引起了广泛研究。自从第一个SVM系统Ivy[12]诞生以来，人们已经在消息传递的
MPP系统或工作站网络上实现了若干SVM系统，如Midway[2]，Munin[3]，
TreadMarks[8]，Quarks[10]，CVM[9]，和Brazos[15]等。
目前，曙光1000A上的主要并行环境为消息传递的编程环境PVM和MPI。本文介绍曙
光1000A上的一个共享虚拟存储系统JIAJIA。该系统为曙光1000A提供了一个除了
PVM和MPI之外的另一并行编程环境，同时也是曙光1000A上的第一个共享存储编程
环境。与其它流行的共享虚拟存储系统相比，JIAJIA在虚拟共享存储器的组织以及
CACHE一致性的维护等方面都有自己的特点。
    JIAJIA系统采用一种基于锁的新型Cache一致性协议[5]来实现域存储一致性模
型(Scope Consistency, 简称ScC)[6]。同传统的基于目录的协议相比较，基于锁
的协议使处理机通过访问附带在锁上的write-notice(write-notice 记录一个页面
是否被修改过)来维护一致性，从而避免由目录引起的存储开销和系统复杂度。为
了降低系统开销，基于锁的协议的设计本着简单实用的原则, 只支持一种存储一致
性模型和一种写传播策略(写无效策略)。同时，采用多写(Multiple-Writer)协议
[3]来避免假共享。
JIAJIA系统的另一显著特征是它能够把多个机器的存储器组织起来形成一个更大的
存储空间，其最大容量等于每个机器的局部存储器之和。而在近期实现的系统如
TreadMarks、CVM和Quarks中共享地址空间受到一台机器内存空间的限制。由于采
用了基于锁的有固定Home的一致性协议，JIAJIA系统避免了twin和diff[3]的保存
、存储空间的释放和收集、局部地址和全局地址之间的转化、以及矢量时间戳维护
等系统开销。
    我们采用了一些有代表性的应用程序，如多体问题、LU分解、排序等，对
JIAJIA系统的性能进行了分析。结果表明，同近期实现的SVM系统（如CVM）比较，
JIAJIA不仅具有更高的绝对性能和加速比，而且可以解决更大规模的问题。
2.存储器组织
    多数近期的SVM系统都采用类似于COMA的存储器组织方式。例如在TreadMarks
，CVM，和Quarks等系统中，共享内存通常初始化分配在结点0上。当其他处理机访
问共享数据时，此数据所在页面的owner会动态漂移到其他的处理机。发生缺页中
断时，利用较复杂的目录结构如Probowner[12]或write-notice近似拷贝集[8]等来
确定该页的最后修改者。在这些系统中，同一共享页在不同的处理机中所处的位置
可以不同。每一处理机保存着所有页面的局部地址和全局地址转换表进行不同处理
机间的地址转换。由于下述原因，这些系统所支持的共享空间受限于单机的内存空
间：
l 这些系统初始化时, 共享存储空间通常都被分配在一个结点上，这决定了它的容
量必然会受到一台机器物理内存空间的限制。
2 为解决一致性问题，每个结点都需要维护一张页表保存大量的信息，如目录、保
护状态、局部与全局地址、twin、diff等。页表的大小随着共享页面数量的增多而
线性增加。
    图 2(a)给出了JIAJIA的共享存储器组织方式。与其他系统不同，JIAJIA采用
类似于NUMA的结构，把共享存储空间分布在所有结点上，每一页面都有一个固定的
Home结点。当处理机访问分布在本地的那一部分共享页面时，只进行本地访问操作
；当处理机访问分布在其他结点上的共享页面时，发生缺页中断，缺页中断服务程
序把该页从相应的Home结点取来，并放在缺页结点的"Cache"中。由于共享空间分
布在所有处理机上，且每个结点的页表不用记录所有共享页面的信息，只记录那些
存放在Cache中的页面的有关信息，JIAJIA系统的共享存储容量不受单机内存空间
的限制。
   在JIAJIA中，共享页面的分配是通过系统调用mmap()实现的。当处理机访问到
没有分配在本地的共享页面时，会产生SIGSEGV信号，相应的SIGSEGV的处理程序把
此共享页面取来并映射到本地结点相同地址的用户空间中, 如图 2(b)所示。由于
被缓存页面的地址与它在Home结点中的地址一致，因此发生远程访问时不需进行地
址转换。因为共享空间有时会远远超过一台机器的内存空间，所以如果不加限制的
把共享页面映射到本地结点上，会使内存空间越界，导致系统崩溃。为了避免这种
现象的发生，每一台处理机都建立一个"Cache"数据结构用于记录那些非本地的共
享页面。当需要映射新的一页到本地时，首先要判断Cache是否已满, 若是，则把
一些页面替换出去。
3.基于锁的一致性协议
    如前所述，JIAJIA把共享空间分布在所有处理机中，当处理机访问分布在其他
结点上的共享页面时，就把该页从相应的Home结点取来，并放在缺页结点的
"Cache"中。Cache在SVM系统中可以大大地隐藏处理机和远程共享存储器之间的延
迟，从而提高性能。但Cache在多处理机中也会引起Cache一致性问题，即如何使同
一单元在不同Cache以及主存中的多个备份保持数据一致的问题。人们已经提出了
若干Cache一致性协议来解决这个问题。分布式共享存储系统通常采用基于目录的
Cache一致性协议来维护数据一致性。其的主要思想是：为每一存储行维持一目录
项，该目录项记录所有当前持有此行备份的处理机号以及此行是否已被改写等信息
。当一个处理机欲往某一存储行写数且可能引起数据不一致时, 它就可以根据目录
的内容向持有此行的备份的那些处理机发出使无效/更新信号以保证某一存储行的
所有共享者都能读到一致的数据。目录协议具有一定的可伸缩性，但目录协议的复
杂性随着系统规模的增加而迅速增加，从而阻碍了系统的进一步扩展。
    JIAJIA系统实现一个基于锁的新型Cache一致性协议以避免由目录引起的存储
开销和系统复杂度。具体做法是：释放锁的处理机把相应临界区中所有表征某一共
享单位是否被改写过的write-notice都附带在锁上发送给锁管理器；获得锁的处理
机根据附带在锁上的write-notice把本地的备份置为无效。与目录协议相比，基于
锁的协议更加简单、有效且可伸缩性好。
   Cache一致性协议都是为实现某种存储一致性模型而设计的。JIAJIA实现的是域
存储一致性模型。它比TreadMarks等系统实现的懒惰释放一致性模型(Lazy
Release Consistency, 简称LRC)更加"懒惰"。在LRC中，当处理机P从处理机Q获得
锁l时，处理机Q所看到(Visible)的修改操作都被传给P。但在ScC中， 只有用锁l
保护起来的区域中所做的修改才会传送给P。
在基本协议中， 每一页都有固定的Home， 对于不在Home中的页面可以映射到
Cache中，在Cache中的页面可以处于三种状态: 无效(INV)， 只读(RO)， 和可读
可写(RW)。由于采用了多写协议， 同一页面可以同时在不同的Cache中处于不同的
状态。锁实质上是一种特殊的共享变量,因此每一个锁也有固定的管理器。
Release操作时， 释放锁的处理机通过比较临界区中已修改的页面和它们的twin来
产生diff， 并送到页面所在的Home结点， 同时还要给相应锁的管理器发送消息，
 通知该锁已被释放，用于记录临界区中修改页面信息的write-notice也被捎带发
送给锁管理器。
    Acquire操作时， 请求锁的处理机向相应的锁管理器发出请求后一直处于等待
状态。锁管理器在应答时把与这个锁相关的write-notice也捎带在应答消息中。发
出请求的处理机在得到响应后， 根据应答消息中的write-notice把本地Cache中的
相应页置为无效。对于处于RW状态的页面，先为它产生diff并送回Home结点， 然
后才使之无效。
    一个Barrier操作可以看作先释放锁再获得锁。到达Barrier意味着一个临界区
的结束， 离开Barrier意味着新临界区的开始。因此两个Barrier操作之间是一个
完整的临界区。在Barrier后， 全部与锁相关的write-notice都被清除。
    当处理机发生读不命中时，直接到相应的Home结点取来该页面放入本地的
Cache中，并置为RO状态。
    当处理机发生写不命中时, 若缺页的页面不在本地的Cache中,或处于INV状态,
 那么它将从相应Home结点被取来并置为RW状态；若缺页的页面在Cache中处于RO状
态, 那么直接把状态变为RW。在开始写数之前，要产生此页面的twin，并记录
write-notice。
        图 3 给出了上述基于锁的协议中页面的状态转换图。从图中可以看出，
与基于目录的协议相比较, 基于锁的协议中所有的一致性操作都是在同步点执行的
，普通的读写操作几乎没有与一致性有关的额外开销。此外，与基于目录的协议相
比，基于锁的协议还省去了普通读写操作时维护目录的开销。
4. 编程界面
4.1. 基本特性
    JIAJIA是一个基于UNIX平台的共享虚拟存储系统。目前，JIAJIA可以在
SunOS 4.1, SunOS 5.4, AIX 4.1, Linux等操作系统环境下运行 。JIAJIA提供了
C和FORTRAN两种语言接口。JIAJIA的源代码和有关文档(包括设计文档和用户手册
等)可以在http://www.ict.ac.cn/chpc/index.html得到。
    为了使用JIAJIA，需要在程序中 include 进 jia.h 头文件。JIAJIA的编程界
面与其它SVM系统如TreadMarks类似。它提供以下基本调用：
l jia_init(argc,argv),  jia_exit()---初始化和终止JIAJIA系统，它们应该分
别在应用程序开始和结束时被调用。
l jia_alloc(int size,...)---分配共享空间，size参数表示分配的字节数，其它
参数允许程序员控制共享数据在各结点间的分布。
l jia_lock(int lockid), jia_unlock(int lockid)---获得和释放编号为lockid
的锁。
l jia_barrier()---Barrier操作，所有结点在Barrier时同步。
此外，JIAJIA还提供了一些辅助调用，如 jia_clock()统计到目前为止所用的时间
，和jia_error(char *str)打印串 str中的出错信息并终止所有进程等。
    JIAJIA提供了两个变量jiapid和 jiahosts，分别表示结点号和结点数。
    在运行时，JIAJIA到当前目录下寻找 .jiahosts配置文件。此文件列出所有用
于运行应用程序的结点, 每一行由结点名称、 用户帐号、 口令3项来描述一个结
点，第一行描述的是首先启动进程的master结点。
4.2.  共享空间的分配
JIAJIA区别于其它共享虚拟存储系统的一个显著特征是它允许用户分配比单机内存
大得多得共享空间以及允许用户灵活控制共享空间在各个处理机之间的分布以提高
访存的局部性。
JIAJIA的共享空间分配的最基本函数是
jia_alloc3(size, blocksize, startproc)
该函数依次在jiapid为startproc，startproc+1，startproc+2,…的处理机中分配
空间，每次分配blocksize字节，直到一共分配了size字节。如果分配到最后一个
处理机(jiapid为jiahosts-1)还没分配完，则下一次分配又从0号处理机开始。其
中size和blocksize都是页对齐的。图 4给出了在四个处理机上分配24MB空间的各
种不同分布方案的例子。
4.2. 进程间的同步
如前所述，JIAJIA的基于锁的一致性协议支持域存储一致性模型。该模型要求用临
界区或其它同步机制保护对共享数据的冲突访问(即，对同一共享变量的访问，且
其中至少有一个是写访问)且对同一个共享数据的冲突访问需用同一把锁保护。
JIAJIA只保证满足上述条件的程序的正确执行。
JIAJIA提供了两种同步方案：锁和Barrier。这两种同步机制不仅用于处理机之间
的同步，而且也用于处理机间数据一致性的维护。具体地说，一个处理机所写的值
，只通过release-acquire对或Barrier，才能被其他处理机所访问到。图 5示范了
JIAJIA中这两种同步机制在维护一致性方面的作用。
4.3. 提高性能
在共享虚拟存储系统中，由于通讯和一致性的粒度较大(一般以页为单位)以及通讯
开销很大，访存不在本地命中的代价很高。JIAJIA除了采用基于锁的一致性协议、
多写(multiple-writer)技术、通过通讯和一致性操作的重叠来隐藏延迟、以及各
种优化措施来尽可能减少开销以外，还允许用户通过控制共享数据的分布以及改变
Cache的大小等方法提高访存的局部性。
 如前所述，JIAJIA允许用户灵活地控制共享空间在各处理机间的分布。为了得到
较好的性能，数据的初始分布应遵循"谁使用，谁拥有"的原则。使得处理机的绝大
多数访问都能在本地的Home命中，减少远程访问的次数。如在曙光1000A上进行规
模为2048*2048的LU分解，当共享数据全部分配在一个处理上时，八机需要43秒，
而当数据根据"谁使用，谁拥有"的原则分布时，八机只需25秒。
 Cache大小对JIAJIA系统的性能也有重要影响。一方面，Cache越大，可以缓存的
分布在其它结点的数据越多；另一方面，一个结点的物理存储器总是有限的，且同
步操作的系统开销随Cache增大也会稍微增加。以1024*1024的矩阵乘法C=A*B为例
，假设矩阵A、B、C都均匀地分布在所有处理机上，使得每个处理机对A和C的访问
都在本地命中。若采用内积法，即按行产生C，对于C的每一行结果，都要用到整个
B矩阵。当每个处理机Cache的大小为4MB时(放得下整个B，每个处理机矩阵计算完
C的第一行后，B就在本地的Cache中)，在四机的SPARC 20工作站上需要73秒，而当
每个处理机的Cache大小为2MB时(放不下 B，计算C的每一行都需要对B不在本地部
分进行远程访问)，则需要1164秒。若采用中积法，即按列产生矩阵C，为计算C的
一列，只需B的相应列。因此Cache大小对性能影响不大，Cache大小为2MB和4MB时
完成在四机的SPARC 20工作站上完成1024*1024的矩阵乘法都是64秒左右。
5.性能分析与比较
    我们移植了一些有代表性的并行应用程序来评测JIAJIA系统的性能。 本文列
举了其中的五个， 它们包括水分子模拟程序Water，天体物理中的多体问题
Barnes[14][16]，整数排序程序IS[1]， 美国Rice大学提供的旅行商问题TSP和逐
次超松弛法程序SOR。为了验证JIAJIA扩展共享内存的能力，SOR计算了2048*2048
和8192*8192两个规模。为了和其他软件DSM系统进行比较， 所有这些应用程序也
用美国Maryland大学研制的CVM进行了计算。
     计算在曙光1000A并行机上进行，该机包括由100Mbps交换以太网连接的八个
结点，每个结点有一个PowerPC 604处理机以及256MB内存。在计算中，所有的库和
应用程序都用gcc -O2编译。
    表1 给出了每个应用程序的特性、串行程序运行时间、以及并行程序在
JIAJIA和CVM上的八机运行时间。如表中所示，由于内存限制，8192*8192的SOR的
串行时间是根据问题规模的估计时间，而由于CVM由于不能支持大内存，上述规模
的问题在CVM上无法运行。图 6给出了JIAJIA和CVM的八机加速比。
    从表1 可以看出，对于大多数程序，JIAJIA获得了较好的绝对性能和加速比。
除了IS和Barnes，JIAJIA的性能优于CVM。
    在SOR中，系统加速比随着问题规模的增大而增大，这是因为SOR中的计算通讯
比随问题规模的增加而线性增加。SOR的每个迭代步之间都用Barrier进行同步，因
此SOR的加速比不是线性的。在分配共享空间时，JIAJIA把数组均匀分布在每一个
处理机中，使得每个处理机的绝大多数访存操作能够在本地完成，只有少数边界访
问才需要访问远程结点。而CVM把数组都分布在一个处理机上，增加了系统的冷启
动时间。其他导致SOR中JIAJIA性能优于CVM的重要原因是基于Home的结构使得
JIAJIA不用为在Home命中的写操作计算diff，以及JIAJIA在访存不命中时的一致性
开销较小。
    Water、Barnes、和TSP都是比较典型的紧密共享型的程序，它们所需的共享内
存不多，被所有处理机频繁地访问，表现出较复杂的访存行为。在Water和TSP中
JIAJIA的性能比CVM好的主要原因是对于普通的读写访问失效，JIAJIA的锁的协议
开销比CVM的懒惰释放协议要小。而在Barnes中CVM的性能略好于JIAJIA的主要原因
是JIAJIA的基于锁的协议Release同步操作的开销比CVM大。此外，在JIAJIA的基于
锁的协议中，只有在Barrier时才把与锁有关的write-notice清除，这样在主要用
锁同步的程序中，会引起write-notice的积累，导致处理机在Acquire时把一些有
效页无谓地置为无效。
在IS中，CVM的性能略优于JIAJIA。 这是因为IS的主要同步和通讯是在程序的最后
每个处理机通过临界区把局部计算的值累加到共享区中，JIAJIA在Release操作时
必须把产生的diff送到其Home上，每个处理机都要花费大量的时间顺序地进入和退
出临界区， 而CVM只需在本地保留diff， 传递消息的数量少于JIAJIA。
6. 结论和今后的工作
通过对上述应用程序的性能分析, 我们可以得出以下结论:
1. JIAJIA系统采用了类似NUMA结构的存储组织方式, 可以把多个处理机的存储空
间连接成一个更大的共享空间。
2. 对于所计算的程序JIAJIA获得了较好的绝对性能和加速比，在大多数情况下，
JIAJIA的性能比CVM好。这主要是由于在JIAJIA的基于锁的Cache一致性协议中,普
通访存操作不命中时通信的开销减少到最小。与它相比, CVM采用的懒惰释放一致
性协议在Release操作时开销小。此外，在JIAJIA中，不需要为Home中的页面产生
diff、采用简单的地址映射机制、采用域一致性协议、以及允许程序员灵活地控制
数据分布等也是JIAJIA获得较好性能的原因。
    我们今后的工作包括进一步提高JIAJIA的性能和实用性、优化基于锁的Cache
一致性协议、并用硬件来实现或支持该协议。关于JIAJIA的更多的信息可以从
http://www.ict.ac.cn/chpc/index.html获得。
参考文献
[1]. D. Bailey, J.Barton, T. Lasinski, and H. Simon, "The NAS Parallel
Benchmarks",  Technical Report 103863, NASA, July 1993.
[2]. B. Bershad, M. Zekauskas and W. Sawdon, "The Midway Distributed
Shared Memory System", in  Proceedings of the 38th IEEE International
Computer Conference, pp. 528--537, February 1993.
[3].  J. Carter, J. Bennett, and W. Zwaenepoel, "Implementation and
Performance of Munin", in  Proceedings of the 13th ACM Symposium on
Operating Systems Principles, pp. 152--164, October 1991.
[4].  K. Gharachorloo, D. Lenoski, J. Laudon, P. Gibbons, A. Gupta,
and J. Hennessy, "Memory Consistency and Event Ordering in Scalable
Shared Memory Multiprocessors", in Proceedings of the 17th Annual
International Symposium on Computer Architecture, pp. 15--26, May 1990.
[5]. W. Hu, W. Shi, Z. Tang, and M. Li, "A Lock-based Cache Coherence
Protocol for Scope Consistency", Journal of Computer Science and
Technology, Vol. 13, No. 2, pp. 97--109, March 1998.
[6].  L. Iftode, J. Singh and K. Li, "Scope Consistency: A Bridge
Between Release Consistency and Entry Consistency", in Proceedings of
the 8th Annual ACM Symposium on Parallel Algorithms and Architectures,
pp. 277--287, June 1996.
[7].  P. Keleher, A. Cox, and W. Zwaenepoel, " Lazy Release
Consistency for Software Distributed Shared Memory", in Proceedings of
the 19th Annual Symposium on Computer Architecture, pp. 13--21, 1992.
[8].  P. Keleher, A. Cox, S. Dwarkadas, and W. Zwaenepoel, "TreadMarks
Distributed Shared Memory on Standard Workstations and Operating
Systems", in Proceedings of the 1994 Winter Usenix Conference, pp.
115--131, January 1994.
[9].  P. Keleher, "CVM: The Coherent Virtual Machine",  CVM Version 0.2,
 University of Maryland, available at URL:  http://www.cs.umd.
edu/~keleher/dsm.html, May 1997,
[10].  D. Khandekar，"Quarks: Distributed Shared Memory as a Building
Block for Complex Parallel and Distributed Systems", Master's thesis,
Department of Computer Science, The University of Utah, March 1996.
 Performance Differences Between PVM and Treadmarks",
Journal of Parallel and Distributed Computing, Vol. 43, No. 2, pp. 65--78, J
une,
1997
D. Lenoski, J. Laudon, K. Gharachorloo, P. Gibbons, A. Gupta, and J.
Hennessy, "The Directory-Based Cache Coherence Protocol for the DASH
Multiprocessors", in Proceedings of the 17th Annual International
Symposium on Computer Architecture, pp. 148--158, June 1990.
[12].  K.Li, "IVY: A Shared Virtual Memory System for Parallel
Computing", in Proceedings of the 1988 International conference on
Parallel Processing, Vol. 2, pp. 94--101, August 1988.
[13].  H. Lu, S. Dwarkadas, A. Cox, and W. Zwaenepoel, "Quantifying
the Performance Differences Between PVM and Treadmarks", Journal of
Parallel and Distributed Computing, Vol. 43, No. 2, pp. 65--78, June,
1997
[14].  J. Singh, W. Weber, and A. Gupta, "SPLASH: Stanford Parallel
Applications for Shared Memory", Computer Architecture News, 20(1):
5--44, March 1992.
[15].  W. Speight and J. Bennett, "Brazos: A third generation DSM
system", in Proceedings of the 1997 USENIX Windows/NT Workshop, December
 1997 

--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]