Institute of Computing Technology, CAS分布存储并行系统中的共享存储编程环境唐志敏tangict.ac.cn中国科学院计算技术研究所提纲什么是分布式共享存储JIAJIA分布式共享存储系统JIAJIA系统的性能JIAJIA系统的应用JIAJIA的编程界面和性能优化lssc机群上的JIAJIA几种常见的并行计算系统对称多处理(SMP)工作站和服务器集中式共享内存，处理机数一般不多大规模并行机(MPP)与机群系统(Cluster)分布式存储，处理机数可以较多一般采用PVM，MPI等消息传递编程环境也可以实现分布式共享存储（或虚拟共享存储）每个结点可以是一个SMP系统由工作站、服务器构成的网络并行计算环境分布式存储，可能是异构的可以用消息传递，可以用虚拟共享存储体系结构：分布存储与集中存储u多地址空间u消息传递通信u编程、移植困难u可伸缩性好l单地址空间l共享存储通信l编程容易、程序易移植l可伸缩性一般编程模型：共享存储与消息传递并行计算机程序设计的两种主要方式并行意味着计算过程的划分：子任务、子问题同一问题的各子任务间有联系：同步、数据交换共享存储与消息传递提供了不同的数据交换方式共享存储数据不必划分，每个子任务都能看到完整的数据需要同步，不同子任务都按确定的次序访问数据消息传递数据也要划分，每个子任务只能看到一部分数据任务通过发送或接收消息来交换数据、保持同步分布式共享存储系统在分布存储系统上提供共享存储抽象分布式共享存储（DSM）系统u结合共享存储的易编程和分布式存储的易扩展u在分布式系统的基础上通过软件或软硬结合的方法提供共享存储的编程环境硬件DSM系统：DASH, FLASH, Alewife, DDM商品化系统：KSR-1，Origin 2000，NUMA-Q软件DSM系统：IVY, Midway, Munin, Quarks, TreadMarks, CVM, JIAJIA, 又称为虚拟共享存储系统、共享虚拟存储系统硬软件结合的DSM系统：Shrimp, Typhoon, Simple-COMA, .软件DSM系统与消息传递系统硬件平台相同，都是分布式存储的并行系统最低层的数据交换手段只能是消息传递数据在物理上仍然分布在各个结点的存储器内软件分布式共享存储提供一个逻辑上统一的虚拟地址空间自动识别非本地存储访问，并转换为消息传递性能：与消息传递相当与精雕细刻的消息传递相比，可能会多送消息自动地缓存远程数据，有效地利用访存局部性软件DSM系统JIAJIA建立在分布存储并行系统上的共享存储环境把用户从繁琐的数据划分和通信组织中解放出来使多台工作站的存储器真正联接成了一个大容量的共享空间在国外的同类系统（如CVM, TreadMarks等）系统中，共享内存容量受限于单机内存的容量简单精巧、开销小、效率高新颖的cache一致性协议能有效地缓存远程数据以运行库的方式支持共享存储和并行计算JIAJIA的主要特点基于主流的操作系统平台，系统移植方便是一个纯用户级软件系统，不修改操作系统Solaris, AIX, Linux, SUNOS, IRIX, WinNT/9x已运行于：SPARC机群、Alpha机群、IBM SP2、曙光系列、Pentium 微机机群等平台支持C 和 FORTRAN 编程接口可方便地移植已有的共享存储应用程序SPLASH2, NAS Parallel Benchmark一批实际应用程序可以根据用户的需要，增加新的功能提供适当的消息传递函数jia_send,jia_recvJIAJIA共享空间的组织CC-NUMA结构P1P3P4P2CacheHomeHomeHomeHomeCacheCacheCache0m-1m2m-12m3m-13m4m-1Non-Uniform Memory AccessJIAJIA共享空间的组织-地址映射home0m-1homem2m-1home(n-1)mnm-1P1P2Pncachecachecachecachecachecache基于锁的Cache一致性协议支持域存储一致性(Scope Consistency)模型对程序员的“额外”要求用临界区或其它同步机制保护对共享数据的冲突访问(即对同一共享单元的两个访问且其中至少有一个是写访问)对同一个共享数据的冲突访问需用同一把锁保护采用写无效(Write-Invalidate)协议采用多写(Multiple-Writer)协议JIAJIA系统的性能(1)性能测试程序Water：水分子模拟程序，来自SPLASHBarnes：解决天体物理中的N-body问题，SPLASHLU(blocked)：用分块算法作LU分解，SPLASH2IS：桶算法整数排序，来自NAS Parallel BenchmarkEP：Embarrassingly Parallel程序，来自NAS TSP：货郎担问题，来自TreadMarks BenchmarksSOR：逐次超松弛法，来自TreadMarksILINK：一个遗传链分析的实际应用问题，来自RiceMM：矩阵乘法JIAJIA系统的性能(2)测试环境SPARCstation工作站网络IBM SP2Dawning 1000A，2000太极和清华的Ultra工作站机群性能比较的对象CVM, TreadMarksPVM测试语言C，优化选项: gcc -O2FORTRAN，优化选项：xlf -O3曙光1000A上的8机加速比太极工作站机群上的加速比PVM与JIAJIA的性能比较(曙光1000A，8个结点)性能小结JIAJIA可以把多个结点的内存连成大共享空间，解决单机无法解决的大问题JIAJIA的性能与消息传递系统相当JIAJIA是可扩展的吗？最近在曙光2000-II上做了128个CPU的试算实验利用JIAJIA移植的应用程序FDTD, 电磁场模拟串行程序来自中科院电子所，需要大内存相关工作在HPCN Europe99上作了报告遥感图像处理：非监督分类和几何精纠正来自中科院地理所IAP18, 全球气候模拟来自中科院大气物理研究所有SGI Power Challenge上的并行版本胶体质量计算程序来自中科院高能物理研究所电磁场模拟：FDTD来自中国科学院电子学研究所用FDTD计算加载波导的谐振频率问题时域有限差分算法：FDTDFinite Difference Time Domain用于电磁场辐射和散射、微波和毫米波电路以及电磁兼容和电磁剂量学等方面的计算FDTD的特点较大的内存容量、较长的计算时间适合分布式共享存储环境下的并行计算FDTD分块并行算法块边界，易于平衡负载，计算块边界，易于平衡负载，计算/ /通信比高通信比高FDTD在JIAJIA系统上的并行化串行程序中串行程序中:DO k = 1，NEy(i,j,k) = cey(i,j,k)*(-dey(i,j,k)*Ey(i,j,k)+(Hx(i,j,k)-Hx(i,j,k-1)/dlz-(Hz(i,j,k)-Hz(i-1,j,k)/dlx)消息传递系统中消息传递系统中:DO k = 1，N/4Ey2(i,j,k)=cey2(i,j,k)*(-dey2(i,j,k)*Ey2(i,j,k)+(Hx2(i,j,k)-Hx2(i,j,k-1)/dlz-(Hz2(i,j,k)-Hz2(i-1,j,k)/dlx)JIAJIA系统中：系统中：DO k=N/4, N/2 Ey(i,j,k)=cey(i,j,k)*(-dey(i,j,k)*Ey(i,j,k)+(Hx(i,j,k)-Hx(i,j,k-1)/dlz-(Hz(i,j,k)-Hz(i-1,j,k)/dlx)Hx1(I,j,N/4)Receive_from_Proc1, Send-to-Proc3曙光1000A上FDTD试算结果遥感图像处理集成环境硬件平台：微机机群(百兆交换式以太网)8台PII400，内存容量256MB软件平台：Linux操作系统, JIAJIA系统主要特点利用分布式并行处理及大内存的优势，提高图像处理的速度，性能价格比高针对遥感图像处理的特殊要求，提供了一组图象操作“指令”供用户选用可利用多条指令批处理，如纠正、分类、水体提取等性能优势举例基于3次多项式的图像纠正皤阳湖的图像数据：13200*15000串行时间：25:08.73 (1508.73秒)8机并行时间：94秒；加速比为168CPU的Origin 2000上需要2分钟图像分类7个6546*5728的图像串行时间：21:25.70 (1285.70秒)8机并行时间：114秒；加速比为11.3JIAJIA的程序设计接口(1)基本函数调用jia_init(argc, argv), jia_exit()jia_alloc(size)，jia_alloc2(size,blocksize), jia_alloc2p(size,proc), jia_alloc3(size,block,startp)jia_lock(lockid), jia_unlock(lockid)jia_barrier()JIAJIA的程序设计接口(2)辅助函数调用jia_setcv(condv),jia_resetcv(), jia_waitcv()jia_wait()jia_error(errinfo), jia_clock()jia_send(buf,len,topid,tag)jia_recv(buf,len,frompid,tag)jia_reduce(send,recv,c,op,root)jia_bcast(buf,len,root)JIAJIA的程序设计接口(3)使用多少个结点？系统配置文件.jiahosts指示用哪些结点全局共享变量jiahosts给出参与运算的结点数本结点的序号每个结点都有一个私有变量jiapid指示结点号并行编程模式：SPMD用jiapid控制计算任务在各结点间的划分JIAJIA的程序设计接口(4)系统参数配置：.jiaconfig文件Pagesize = Cachepages = 系统功能配置：jia_config函数void jia_config(func, value)HMIG：Home迁移功能PREFETCH：预取功能WVEC：写向量功能例子：积分求p串行程序h = 1.0/N; pi = 0;for(i=1; i=N; i+)temp = (i-0.5)*h;pi = pi + 4/(1+temp*temp);pi = pi * h;printf pi;JIAJIA 积分求p MPIjia_init(argc,argv);pi=jia_alloc(8);h = 1.0/N; pi = 0;for(i=jiapid+1;i=N; i+=jiahosts) mypi = . jia_lock(1);pi += mypi;jia_unlock(1);printf pi;jia_exit();MPI_Init(argc,argv);MPI_Comm_size();MPI_Comm_rand();h = 1.0/N;for (i=myid+1;i=N; i+=numprocs) mypi = . MPI_Reduce(mypi,pi,1. );printf pi;MPI_Finalize();并行处理的过程：矩阵乘法A B = C的过程可分为四个独立的部分：Ai B = Ci，i = 1, 2, 3, 4每部分包含的运算可由一台处理机单独完成矩阵较大时，需分开存放，即Ai,Bi,Ci放在结点i上每结点的工作分为AiB1,AiB2,AiB3,AiB4四个部分ABCX=A1A2A3A4C1C2C3C4B1 B2 B3 B4矩阵乘法的共享存储程序double (*a)N,(*b)N,(*c)N;a=jia_alloc2(N*N*8,N*N*8/jiahosts);b=jia_alloc2(.); c=jia_alloc(.);begin=N*jiapid/jiahosts;end=N*(jiapid+1)/jiahosts;for (i=begin; iend; i+)for (j=0; jN; j+)for (k=0; kN; k+) cij+=aik*bkj;计算的组织与数据的组织是分离的而在消息传递程序中，Bi需要传送共享数据与私有数据只有通过jia_alloc分配空间的数据才是共享的共享数据本质上是通过指针访问的在C和Fortran中可以将指针访问转换为常规访问其它数据，C外部量、Fortran公共块，是私有的如何定义Fortran公共块为共享数据？原公共块：Common /c1/ array(n,n)可重写为：Common /c1/ parray增加说明：Pointer (parray, array) 分配空间：parray = jia_alloc(n*n*8)后续访问仍可通过array(i,j)进行共享内存的分配最简单的方式：不管它的具体位置jia_alloc(size_in_byte)，以页为单位轮流分配系统会自动将页面移动到使用最多的结点处用户也可以自行控制共享数据的具体位置jia_alloc2(size,block)，以block为单位轮流分配jia_alloc3(size,block,startp)，指定起始结点如能做到拥有者计算，有可能达到更好的性能例：按行块均匀地分布NN矩阵Apointer(pa, a) / / real*8 a(N,N)pa =jia_alloc2(N*N*8,N*N*8/jiahosts)JIAJIA的内存分配方法灵活的共享空间分配功能：允许用户控制数据分布P0P2P3P1jia_alloc3(0x1800000, 0x600000, 0)均匀地分段分配P0P2P3P1jia_alloc3(0x1800000, 0x300000, 0)不在P2上分配P0P2P3P1jia_alloc3(0x1800000, 0x800000, 3)仅在后两个结点上分配P0P2P3P1jia_alloc3(0x1800000, 0xc00000, 2)提高性能的方法提高性能的方法增加 HOME 的局部性增加 Cache 的局部性例：矩阵乘法共享内存的分配：按行平均分配，按块平均分配算法；中积法，内积法Cache大小的影响对共享数据的互斥访问互斥的要求：修改共享数据时不能被打断任一时刻只有一个结点（进程）修改共享数据为什么需要保证互斥？设x=0为共享变量Proc 1Proc 2语句x = x + 5x = x + 6代码Load R1, xLoad R1, xAdd R1, #5Add R1, #6Store R1, xStore R1, x若先执行P1的3条指令后执行P2的指令，x=11若P1与P2的指令交替执行，则x=6，结果不正确同步操作的两种基本形式通过加锁和开锁操作构成临界区P1和P2修改共享数据的语句都改成： jia_lock(i); x = x + .;jia_unlock(i);其中i为锁的编号，一把锁通常保护一组数据另外一种常用的同步方式：栅障(barrier)所有参与计算的结点在某一点取齐，先到达栅障的结点等待其余结点，全到后再执行后续语句例如，结点0为共享变量x赋初值，其它结点等待if (jiapid=0) x=0;jia_barrier(); / 经后，所有结点都看到x=0JIAJIA的程序设计接口(5)锁同步机制值的传播P1P1jia_lock(0)x=1jia_unlock(0)jia_lock(1)y=1jia_unlock(1)P2P2jia_lock(1)a=xb=yjia_unlock(1)P3P3jia_lock(0)a=xb=yjia_unlock(0)执行后：执行后：P2: a=0,b=1; P3: a=1,b=0x=1y=1JIAJIA的程序设计接口(6)Barrier同步机制值的传播P1P1x=1jia_barrier()a=xb=yc=zP2P2y=1jia_barrier()a=xb=yc=z执行后：执行后：P1,P2,P3: a=b=c=1x=1,y=1,z=1P3P3z=1jia_barrier()a=xb=yc=z其它需要注意的问题冲突访问：多个结点修改同一个变量x = 1;y = 2;jia_barrier();jia_barrier();a = y;b = x;jia_barrier();jia_barrier();x = 3;y = 4;输入输出和文件操作控制台输入只能由0号结点上的进程接收其它结点的标准输出被重定向到apps-?.log中一个文件只能由一个结点打开和读写LSSC机群上的JIAJIA位置：/usr/local/jiajiainclude, lib, Makefile.sample作业提交bsub -n 处理器数 “jiajia 程序名 参数表”JIAJIA系统成果应用及影响在20多个国家或地区的80多所大学或研究机构得到试用Brazil, Canada, Croatia, France, Germany, Hong Kong, Iran, Israel, Italy, Japan, Korea, Mexico, Netherlands, Norway, Singapore, Spain, Sweden, Taiwan, UK, USAPrinceton Univ., UC Davis, USCNational Autonomous University of MexicoUniversity of Hong Kong国内, 在曙光系列并行机、太极Ultra工作站机群、国防科大Alpha工作站机群得到应用未来的工作实现专用的快速远程存储访问网络目标：远程访问延迟不超过本地延迟的3-4倍支持通用的共享存储编程环境如CRAY，Origin 2000，OpenMP等DSM系统的高可用性并行程序在单结点出错时，自动进行负载重分配基于JIAJIA的遥感图像快速处理实用系统快速处理能力、大内存、友好的界面为灾害的实时监测与快速预报作出贡献有关文档在http:/www.ict.ac.cn/chpc/index.html有各版本JIAJIA的源代码JIAJIA的用户手册JIAJIA研制报告(包括流程图等)有关论文(包括与基于锁的协议基本原理、与其它系统的比较、性能分析、改进措施等)报告胶片我们的 Homepage 最近被 www.links2go.com 授予 Links2Go Key Resource Award