分布存储并行系统中的共享存储编程环境.ppt

分布存储并行系统中的共享存储编程环境,唐志敏tang中国科学院计算技术研究所,提纲,什么是分布式共享存储JIAJIA分布式共享存储系统JIAJIA系统的性能JIAJIA系统的应用JIAJIA的编程界面和性能优化lssc机群上的JIAJIA,几种常见的并行计算系统,对称多处理(SMP)工作站和服务器集中式共享内存，处理机数一般不多大规模并行机(MPP)与机群系统(Cluster)分布式存储，处理机数可以较多一般采用PVM，MPI等消息传递编程环境也可以实现分布式共享存储（或虚拟共享存储）每个结点可以是一个SMP系统由工作站、服务器构成的网络并行计算环境分布式存储，可能是异构的可以用消息传递，可以用虚拟共享存储,体系结构：分布存储与集中存储,多地址空间消息传递通信编程、移植困难可伸缩性好,单地址空间共享存储通信编程容易、程序易移植可伸缩性一般,编程模型：共享存储与消息传递,并行计算机程序设计的两种主要方式并行意味着计算过程的划分：子任务、子问题同一问题的各子任务间有联系：同步、数据交换共享存储与消息传递提供了不同的数据交换方式共享存储数据不必划分，每个子任务都能看到完整的数据需要同步，不同子任务都按确定的次序访问数据消息传递数据也要划分，每个子任务只能看到一部分数据任务通过发送或接收消息来交换数据、保持同步,分布式共享存储系统,在分布存储系统上提供共享存储抽象,分布式共享存储（DSM）系统,结合共享存储的易编程和分布式存储的易扩展在分布式系统的基础上通过软件或软硬结合的方法提供共享存储的编程环境硬件DSM系统：DASH,FLASH,Alewife,DDM商品化系统：KSR-1，Origin2000，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机群、IBMSP2、曙光系列、Pentium微机机群等平台支持C和FORTRAN编程接口可方便地移植已有的共享存储应用程序SPLASH2,NASParallelBenchmark一批实际应用程序可以根据用户的需要，增加新的功能提供适当的消息传递函数jia_send,jia_recv,JIAJIA共享空间的组织CC-NUMA结构,Non-UniformMemoryAccess,JIAJIA共享空间的组织-地址映射,home,0m-1,home,m2m-1,home,(n-1)mnm-1,P1,P2,Pn,cache,cache,cache,cache,cache,cache,基于锁的Cache一致性协议,支持域存储一致性(ScopeConsistency)模型对程序员的“额外”要求用临界区或其它同步机制保护对共享数据的冲突访问(即对同一共享单元的两个访问且其中至少有一个是写访问)对同一个共享数据的冲突访问需用同一把锁保护采用写无效(Write-Invalidate)协议采用多写(Multiple-Writer)协议,JIAJIA系统的性能(1),性能测试程序Water：水分子模拟程序，来自SPLASHBarnes：解决天体物理中的N-body问题，SPLASHLU(blocked)：用分块算法作LU分解，SPLASH2IS：桶算法整数排序，来自NASParallelBenchmarkEP：EmbarrassinglyParallel程序，来自NASTSP：货郎担问题，来自TreadMarksBenchmarksSOR：逐次超松弛法，来自TreadMarksILINK：一个遗传链分析的实际应用问题，来自RiceMM：矩阵乘法,JIAJIA系统的性能(2),测试环境SPARCstation工作站网络IBMSP2Dawning1000A，2000太极和清华的Ultra工作站机群性能比较的对象CVM,TreadMarksPVM测试语言C，优化选项:gcc-O2FORTRAN，优化选项：xlf-O3,曙光1000A上的8机加速比,太极工作站机群上的加速比,PVM与JIAJIA的性能比较(曙光1000A，8个结点),性能小结,JIAJIA可以把多个结点的内存连成大共享空间，解决单机无法解决的大问题JIAJIA的性能与消息传递系统相当JIAJIA是可扩展的吗？最近在曙光2000-II上做了128个CPU的试算实验,利用JIAJIA移植的应用程序,FDTD,电磁场模拟串行程序来自中科院电子所，需要大内存相关工作在HPCNEurope99上作了报告遥感图像处理：非监督分类和几何精纠正来自中科院地理所IAP18,全球气候模拟来自中科院大气物理研究所有SGIPowerChallenge上的并行版本胶体质量计算程序来自中科院高能物理研究所,电磁场模拟：FDTD,来自中国科学院电子学研究所用FDTD计算加载波导的谐振频率问题时域有限差分算法：FDTDFiniteDifferenceTimeDomain用于电磁场辐射和散射、微波和毫米波电路以及电磁兼容和电磁剂量学等方面的计算FDTD的特点较大的内存容量、较长的计算时间适合分布式共享存储环境下的并行计算,FDTD分块并行算法,块边界，易于平衡负载，计算/通信比高,FDTD在JIAJIA系统上的并行化,串行程序中:DOk=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)消息传递系统中:DOk=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系统中：DOk=N/4,N/2Ey(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的Origin2000上需要2分钟图像分类7个6546*5728的图像串行时间：21:25.70(1285.70秒)8机并行时间：114秒；加速比为11.3,JIAJIA的程序设计接口(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函数voidjia_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;printfpi;,JIAJIA积分求pMPI,jia_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);printfpi;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.);printfpi;MPI_Finalize();,并行处理的过程：矩阵乘法,AB=C的过程可分为四个独立的部分：AiB=Ci，i=1,2,3,4每部分包含的运算可由一台处理机单独完成矩阵较大时，需分开存放，即Ai,Bi,Ci放在结点i上每结点的工作分为AiB1,AiB2,AiB3,AiB4四个部分,矩阵乘法的共享存储程序,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;i<end;i+)for(j=0;j<N;j+)for(k=0;k<N;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*8a(N,N)pa=jia_alloc2(N*N*8,N*N*8/jiahosts),JIAJIA的内存分配方法,灵活的共享空间分配功能：允许用户控制数据分布,均匀地分段分配,不在P2上分配,仅在后两个结点上分配,提高性能的方法,提高性能的方法增加HOME的局部性增加Cache的局部性例：矩阵乘法共享内存的分配：按行平均分配，按块平均分配算法；中积法，内积法Cache大小的影响,对共享数据的互斥访问,互斥的要求：修改共享数据时不能被打断任一时刻只有一个结点（进程）修改共享数据为什么需要保证互斥？设x=0为共享变量Proc1Proc2语句x=x+5x=x+6代码LoadR1,xLoadR1,xAddR1,#5AddR1,#6StoreR1,xStoreR1,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=0,JIAJIA的程序设计接口(5),锁同步机制值的传播,JIAJIA的程序设计接口(6),Barrier同步机制值的传播,其它需要注意的问题,冲突访问：多个结点修改同一个变量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,HongKong,Iran,Israel,Italy,Japan,Korea,Mexico,Netherlands,Norway,Singapore,Spain,Sweden,Taiwan,UK,USAPrincetonUniv.,UCDavis,USCNationalAutonomousUniversityofMexicoUniversityofHongKong国内,在曙光系列并行机、太极Ultra工作站机群、国防科大Alpha工作站机群得到应用,未来的工作,实现专用的快速远程存储访问网络目标：远程访问延迟不超过本地延迟的3-4倍支持通用的共享存储编程环境如CRAY，Origin2000，OpenMP等DSM系统的高可用性并行程序在单结点出错时，自动进行负载重分配基于JIAJIA的遥感图像快速处理实用系统快速处理能力、大内存、友好的界面为灾害的实时监测与快速预报作出贡献,有关文档,在,