分布存儲并行系統(tǒng)中共享存儲編程環(huán)境

1、分布存儲并行系統(tǒng)中共享存儲編程環(huán)境提綱什么是分布式共享存儲JIAJIA分布式共享存儲系統(tǒng)JIAJIA系統(tǒng)的性能JIAJIA系統(tǒng)的應(yīng)用JIAJIA的編程界面和性能優(yōu)化lssc機群上的JIAJIA分布存儲并行系統(tǒng)中共享存儲編程環(huán)境幾種常見的并行計算系統(tǒng)對稱多處理(SMP)工作站和服務(wù)器集中式共享內(nèi)存，處理機數(shù)一般不多大規(guī)模并行機(MPP)與機群系統(tǒng)(Cluster)分布式存儲，處理機數(shù)可以較多一般采用PVM，MPI等消息傳遞編程環(huán)境也可以實現(xiàn)分布式共享存儲（或虛擬共享存儲）每個結(jié)點可以是一個SMP系統(tǒng)由工作站、服務(wù)器構(gòu)成的網(wǎng)絡(luò)并行計算環(huán)境分布式存儲，可能是異構(gòu)的可以用消息傳遞，可以用虛擬共享存儲分

2、布存儲并行系統(tǒng)中共享存儲編程環(huán)境體系結(jié)構(gòu)：分布存儲與集中存儲多地址空間消息傳遞通信編程、移植困難可伸縮性好單地址空間共享存儲通信編程容易、程序易移植可伸縮性一般分布存儲并行系統(tǒng)中共享存儲編程環(huán)境編程模型：共享存儲與消息傳遞并行計算機程序設(shè)計的兩種主要方式并行意味著計算過程的劃分：子任務(wù)、子問題同一問題的各子任務(wù)間有聯(lián)系：同步、數(shù)據(jù)交換共享存儲與消息傳遞提供了不同的數(shù)據(jù)交換方式共享存儲數(shù)據(jù)不必劃分，每個子任務(wù)都能看到完整的數(shù)據(jù)需要同步，不同子任務(wù)都按確定的次序訪問數(shù)據(jù)消息傳遞數(shù)據(jù)也要劃分，每個子任務(wù)只能看到一部分數(shù)據(jù)任務(wù)通過發(fā)送或接收消息來交換數(shù)據(jù)、保持同步分布存儲并行系統(tǒng)中共享存儲編程環(huán)境分布

3、式共享存儲系統(tǒng)在分布存儲系統(tǒng)上提供共享存儲抽象分布存儲并行系統(tǒng)中共享存儲編程環(huán)境分布式共享存儲（DSM）系統(tǒng)結(jié)合共享存儲的易編程和分布式存儲的易擴展在分布式系統(tǒng)的基礎(chǔ)上通過軟件或軟硬結(jié)合的方法提供共享存儲的編程環(huán)境硬件DSM系統(tǒng)：DASH, FLASH, Alewife, DDM商品化系統(tǒng)：KSR-1，Origin 2000，NUMA-Q軟件DSM系統(tǒng)：IVY, Midway, Munin, Quarks, TreadMarks, CVM, JIAJIA, 又稱為虛擬共享存儲系統(tǒng)、共享虛擬存儲系統(tǒng)硬軟件結(jié)合的DSM系統(tǒng)：Shrimp, Typhoon, Simple-COMA, .分布存儲并行

4、系統(tǒng)中共享存儲編程環(huán)境軟件DSM系統(tǒng)與消息傳遞系統(tǒng)硬件平臺相同，都是分布式存儲的并行系統(tǒng)最低層的數(shù)據(jù)交換手段只能是消息傳遞數(shù)據(jù)在物理上仍然分布在各個結(jié)點的存儲器內(nèi)軟件分布式共享存儲提供一個邏輯上統(tǒng)一的虛擬地址空間自動識別非本地存儲訪問，并轉(zhuǎn)換為消息傳遞性能：與消息傳遞相當(dāng)與精雕細刻的消息傳遞相比，可能會多送消息自動地緩存遠程數(shù)據(jù)，有效地利用訪存局部性分布存儲并行系統(tǒng)中共享存儲編程環(huán)境軟件DSM系統(tǒng)JIAJIA建立在分布存儲并行系統(tǒng)上的共享存儲環(huán)境把用戶從繁瑣的數(shù)據(jù)劃分和通信組織中解放出來使多臺工作站的存儲器真正聯(lián)接成了一個大容量的共享空間在國外的同類系統(tǒng)（如CVM, TreadMarks等）系

5、統(tǒng)中，共享內(nèi)存容量受限于單機內(nèi)存的容量簡單精巧、開銷小、效率高新穎的cache一致性協(xié)議能有效地緩存遠程數(shù)據(jù)以運行庫的方式支持共享存儲和并行計算分布存儲并行系統(tǒng)中共享存儲編程環(huán)境JIAJIA的主要特點基于主流的操作系統(tǒng)平臺，系統(tǒng)移植方便是一個純用戶級軟件系統(tǒng)，不修改操作系統(tǒng)Solaris, AIX, Linux, SUNOS, IRIX, WinNT/9x已運行于：SPARC機群、Alpha機群、IBM SP2、曙光系列、Pentium 微機機群等平臺支持C 和 FORTRAN 編程接口可方便地移植已有的共享存儲應(yīng)用程序SPLASH2, NAS Parallel Benchmark一批實際應(yīng)用

6、程序可以根據(jù)用戶的需要，增加新的功能提供適當(dāng)?shù)南鬟f函數(shù)jia_send,jia_recv分布存儲并行系統(tǒng)中共享存儲編程環(huán)境JIAJIA共享空間的組織CC-NUMA結(jié)構(gòu)P1P3P4P2CacheHomeHomeHomeHomeCacheCacheCache0m-1m2m-12m3m-13m4m-1Non-Uniform Memory Access分布存儲并行系統(tǒng)中共享存儲編程環(huán)境JIAJIA共享空間的組織地址映射home0m-1homem2m-1home(n-1)mnm-1P1P2Pncachecachecachecachecachecache分布存儲并行系統(tǒng)中共享存儲編程環(huán)境基于鎖的Cac

7、he一致性協(xié)議支持域存儲一致性(Scope Consistency)模型對程序員的“額外”要求用臨界區(qū)或其它同步機制保護對共享數(shù)據(jù)的沖突訪問(即對同一共享單元的兩個訪問且其中至少有一個是寫訪問)對同一個共享數(shù)據(jù)的沖突訪問需用同一把鎖保護采用寫無效(Write-Invalidate)協(xié)議采用多寫(Multiple-Writer)協(xié)議分布存儲并行系統(tǒng)中共享存儲編程環(huán)境JIAJIA系統(tǒng)的性能(1)性能測試程序Water：水分子模擬程序，來自SPLASHBarnes：解決天體物理中的N-body問題，SPLASHLU(blocked)：用分塊算法作LU分解，SPLASH2IS：桶算法整數(shù)排序，來自NA

8、S Parallel BenchmarkEP：Embarrassingly Parallel程序，來自NAS TSP：貨郎擔(dān)問題，來自TreadMarks BenchmarksSOR：逐次超松弛法，來自TreadMarksILINK：一個遺傳鏈分析的實際應(yīng)用問題，來自RiceMM：矩陣乘法分布存儲并行系統(tǒng)中共享存儲編程環(huán)境JIAJIA系統(tǒng)的性能(2)測試環(huán)境SPARCstation工作站網(wǎng)絡(luò)IBM SP2Dawning 1000A，2000太極和清華的Ultra工作站機群性能比較的對象CVM, TreadMarksPVM測試語言C，優(yōu)化選項: gcc -O2FORTRAN，優(yōu)化選項：xlf -

9、O3分布存儲并行系統(tǒng)中共享存儲編程環(huán)境曙光1000A上的8機加速比分布存儲并行系統(tǒng)中共享存儲編程環(huán)境太極工作站機群上的加速比分布存儲并行系統(tǒng)中共享存儲編程環(huán)境PVM與JIAJIA的性能比較(曙光1000A，8個結(jié)點)分布存儲并行系統(tǒng)中共享存儲編程環(huán)境性能小結(jié)JIAJIA可以把多個結(jié)點的內(nèi)存連成大共享空間，解決單機無法解決的大問題JIAJIA的性能與消息傳遞系統(tǒng)相當(dāng)JIAJIA是可擴展的嗎？最近在曙光2000-II上做了128個CPU的試算實驗分布存儲并行系統(tǒng)中共享存儲編程環(huán)境利用JIAJIA移植的應(yīng)用程序FDTD, 電磁場模擬串行程序來自中科院電子所，需要大內(nèi)存相關(guān)工作在HPCN Europe

10、99上作了報告遙感圖像處理：非監(jiān)督分類和幾何精糾正來自中科院地理所IAP18, 全球氣候模擬來自中科院大氣物理研究所有SGI Power Challenge上的并行版本膠體質(zhì)量計算程序來自中科院高能物理研究所分布存儲并行系統(tǒng)中共享存儲編程環(huán)境電磁場模擬：FDTD來自中國科學(xué)院電子學(xué)研究所用FDTD計算加載波導(dǎo)的諧振頻率問題時域有限差分算法：FDTDFinite Difference Time Domain用于電磁場輻射和散射、微波和毫米波電路以及電磁兼容和電磁劑量學(xué)等方面的計算FDTD的特點較大的內(nèi)存容量、較長的計算時間適合分布式共享存儲環(huán)境下的并行計算分布存儲并行系統(tǒng)中共享存儲編程環(huán)境FDT

11、D分塊并行算法塊邊界，易于平衡負載，計算/通信比高分布存儲并行系統(tǒng)中共享存儲編程環(huán)境FDTD在JIAJIA系統(tǒng)上的并行化串行程序中: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)消息傳遞系統(tǒng)中: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)/dl

12、x)JIAJIA系統(tǒng)中：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分布存儲并行系統(tǒng)中共享存儲編程環(huán)境曙光1000A上FDTD試算結(jié)果分布存儲并行系統(tǒng)中共享存儲編程環(huán)境遙感圖像處理集成環(huán)境硬件平臺：微機機群(百兆交換式以太網(wǎng))8臺PII400，內(nèi)存容量256MB軟件平臺：Linux操作系統(tǒng), JIAJIA系統(tǒng)主要特點利用分布式并

13、行處理及大內(nèi)存的優(yōu)勢，提高圖像處理的速度，性能價格比高針對遙感圖像處理的特殊要求，提供了一組圖象操作“指令”供用戶選用可利用多條指令批處理，如糾正、分類、水體提取等分布存儲并行系統(tǒng)中共享存儲編程環(huán)境性能優(yōu)勢舉例基于3次多項式的圖像糾正皤陽湖的圖像數(shù)據(jù)：13200*15000串行時間：秒)8機并行時間：94秒；加速比為168CPU的Origin 2000上需要2分鐘圖像分類7個6546*5728的圖像串行時間：秒)8機并行時間：114秒；加速比為分布存儲并行系統(tǒng)中共享存儲編程環(huán)境JIAJIA的程序設(shè)計接口(1)基本函數(shù)調(diào)用jia_init(argc, argv), jia_exit()jia_a

14、lloc(size)，jia_alloc2(size,blocksize), jia_alloc2p(size,proc), jia_alloc3(size,block,startp)jia_lock(lockid), jia_unlock(lockid)jia_barrier()分布存儲并行系統(tǒng)中共享存儲編程環(huán)境JIAJIA的程序設(shè)計接口(2)輔助函數(shù)調(diào)用jia_setcv(condv),jia_resetcv(), jia_waitcv()jia_wait()jia_error(errinfo), jia_clock()jia_send(buf,len,topid,tag)jia_recv

15、(buf,len,frompid,tag)jia_reduce(send,recv,c,op,root)jia_bcast(buf,len,root)分布存儲并行系統(tǒng)中共享存儲編程環(huán)境JIAJIA的程序設(shè)計接口(3)使用多少個結(jié)點？系統(tǒng)配置文件.jiahosts指示用哪些結(jié)點全局共享變量jiahosts給出參與運算的結(jié)點數(shù)本結(jié)點的序號每個結(jié)點都有一個私有變量jiapid指示結(jié)點號并行編程模式：SPMD用jiapid控制計算任務(wù)在各結(jié)點間的劃分分布存儲并行系統(tǒng)中共享存儲編程環(huán)境JIAJIA的程序設(shè)計接口(4)系統(tǒng)參數(shù)配置：.jiaconfig文件Pagesize = Cachepages = 系

16、統(tǒng)功能配置：jia_config函數(shù)void jia_config(func, value)HMIG：Home遷移功能PREFETCH：預(yù)取功能WVEC：寫向量功能分布存儲并行系統(tǒng)中共享存儲編程環(huán)境例子：積分求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;分布存儲并行系統(tǒng)中共享存儲編程環(huán)境JIAJIA 積分求p MPIjia_init(argc,argv);pi=jia_alloc(8);h = 1.0/N; pi = 0;for(

17、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();分布存儲并行系統(tǒng)中共享存儲編程環(huán)境并行處理的過程：矩陣乘法A B = C的過程可分為四個獨立的部分：Ai

18、 B = Ci，i = 1, 2, 3, 4每部分包含的運算可由一臺處理機單獨完成矩陣較大時，需分開存放，即Ai,Bi,Ci放在結(jié)點i上每結(jié)點的工作分為AiB1,AiB2,AiB3,AiB4四個部分ABCX=A1A2A3A4C1C2C3C4B1B2B3B4分布存儲并行系統(tǒng)中共享存儲編程環(huán)境矩陣乘法的共享存儲程序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;fo

19、r (i=begin; iend; i+)for (j=0; jN; j+)for (k=0; kN; k+) cij+=aik*bkj;計算的組織與數(shù)據(jù)的組織是分離的而在消息傳遞程序中，Bi需要傳送分布存儲并行系統(tǒng)中共享存儲編程環(huán)境共享數(shù)據(jù)與私有數(shù)據(jù)只有通過jia_alloc分配空間的數(shù)據(jù)才是共享的共享數(shù)據(jù)本質(zhì)上是通過指針訪問的在C和Fortran中可以將指針訪問轉(zhuǎn)換為常規(guī)訪問其它數(shù)據(jù)，C外部量、Fortran公共塊，是私有的如何定義Fortran公共塊為共享數(shù)據(jù)？原公共塊：Common /c1/ array(n,n)可重寫為：Common /c1/ parray增加說明：Pointer (

20、parray, array) 分配空間：parray = jia_alloc(n*n*8)后續(xù)訪問仍可通過array(i,j)進行分布存儲并行系統(tǒng)中共享存儲編程環(huán)境共享內(nèi)存的分配最簡單的方式：不管它的具體位置jia_alloc(size_in_byte)，以頁為單位輪流分配系統(tǒng)會自動將頁面移動到使用最多的結(jié)點處用戶也可以自行控制共享數(shù)據(jù)的具體位置jia_alloc2(size,block)，以block為單位輪流分配jia_alloc3(size,block,startp)，指定起始結(jié)點如能做到擁有者計算，有可能達到更好的性能例：按行塊均勻地分布NN矩陣Apointer(pa, a) / re

21、al*8 a(N,N)pa =jia_alloc2(N*N*8,N*N*8/jiahosts)分布存儲并行系統(tǒng)中共享存儲編程環(huán)境JIAJIA的內(nèi)存分配方法靈活的共享空間分配功能：允許用戶控制數(shù)據(jù)分布P0P2P3P1jia_alloc3(0 x1800000, 0 x600000, 0)分布存儲并行系統(tǒng)中共享存儲編程環(huán)境均勻地分段分配P0P2P3P1jia_alloc3(0 x1800000, 0 x300000, 0)分布存儲并行系統(tǒng)中共享存儲編程環(huán)境不在P2上分配P0P2P3P1jia_alloc3(0 x1800000, 0 x800000, 3)分布存儲并行系統(tǒng)中共享存儲編程環(huán)境僅在后兩

22、個結(jié)點上分配P0P2P3P1jia_alloc3(0 x1800000, 0 xc00000, 2)分布存儲并行系統(tǒng)中共享存儲編程環(huán)境提高性能的方法提高性能的方法增加 HOME 的局部性增加 Cache 的局部性例：矩陣乘法共享內(nèi)存的分配：按行平均分配，按塊平均分配算法；中積法，內(nèi)積法Cache大小的影響分布存儲并行系統(tǒng)中共享存儲編程環(huán)境對共享數(shù)據(jù)的互斥訪問互斥的要求：修改共享數(shù)據(jù)時不能被打斷任一時刻只有一個結(jié)點（進程）修改共享數(shù)據(jù)為什么需要保證互斥？設(shè)x=0為共享變量Proc 1Proc 2語句x = x + 5x = x + 6代碼Load R1, xLoad R1, xAdd R1, #

23、5Add R1, #6Store R1, xStore R1, x若先執(zhí)行P1的3條指令后執(zhí)行P2的指令，x=11若P1與P2的指令交替執(zhí)行，則x=6，結(jié)果不正確分布存儲并行系統(tǒng)中共享存儲編程環(huán)境同步操作的兩種基本形式通過加鎖和開鎖操作構(gòu)成臨界區(qū)P1和P2修改共享數(shù)據(jù)的語句都改成： jia_lock(i); x = x + .;jia_unlock(i);其中i為鎖的編號，一把鎖通常保護一組數(shù)據(jù)另外一種常用的同步方式：柵障(barrier)所有參與計算的結(jié)點在某一點取齊，先到達柵障的結(jié)點等待其余結(jié)點，全到后再執(zhí)行后續(xù)語句例如，結(jié)點0為共享變量x賦初值，其它結(jié)點等待if (jiapid=0) x

24、=0;jia_barrier(); / 經(jīng)后，所有結(jié)點都看到x=0分布存儲并行系統(tǒng)中共享存儲編程環(huán)境JIAJIA的程序設(shè)計接口(5)鎖同步機制值的傳播P1jia_lock(0)x=1jia_unlock(0)jia_lock(1)y=1jia_unlock(1)P2jia_lock(1)a=xb=yjia_unlock(1)P3jia_lock(0)a=xb=yjia_unlock(0)執(zhí)行后：P2: a=0,b=1; P3: a=1,b=0 x=1y=1分布存儲并行系統(tǒng)中共享存儲編程環(huán)境JIAJIA的程序設(shè)計接口(6)Barrier同步機制值的傳播P1x=1jia_barrier()a=xb=yc=zP2y=1jia_barrier()a=xb=yc=z執(zhí)行后：P1,P2,P3: a=b=c=1x=1,y=1,z=1P3z=1jia_barrier()a=xb=yc=z分布存儲并行系統(tǒng)中共享存儲編程環(huán)境其它需要注意的問題沖突訪問：多個結(jié)點修改同一個變