地理計算第二章

1、,,地理計算,GeoComputation,,地理計算,主講： 李 霖 教授,第二章 計算技術(shù),首先區(qū)分計算科學和計算機科學。盡管他們相關，但是計算學是致力于計算機技術(shù)在特殊領域中應用和解決問題。,按照最傳統(tǒng)的理論——實驗的二值觀點，計算學擴展為包括實驗、模擬、建模的三部分。,,計算是關鍵的、核心的、一般的、廣泛被應用的、不斷革新的科學，地理計算是計算的地理版本，當前最迫切的是該方面的研究很少，進展更是緩慢，可以說該領域中絕大多數(shù)地

2、方還是未涉足的空白區(qū)這就給地理計算學者們豐富的空間來研究、討論。,,地理分析的計算復雜度主要來自兩個方面：地理數(shù)據(jù)的增長和模型的復雜性。地理學者已經(jīng)見證了地理信息量的快速增長。特別是遙感影象精度的增加，是數(shù)據(jù)呈指數(shù)上升。許多地理模型都是需要一定計算強度的，包括各種優(yōu)化搜索策略。在應用很多模型來進行科學實驗和決策時卻因計算的復雜度和低性能而受到影響。,,摩爾定律預測，每18個月微處理器的性能將翻倍，這個規(guī)則在過去的一段時間里得到驗證，并且

3、還會持續(xù)一段時間。但是，盡管有這種顯著的性能增加，計算機工藝設計在不久的將來會達到它們的處理器材料的限制極限，再加之費用的大幅提高，使人們轉(zhuǎn)而投向采用其他方法來提高計算性能。,,GC試圖為新一代高性能技術(shù)發(fā)掘新的應用?，F(xiàn)在的微處理器性能還在繼續(xù)提高，但是一旦其接近了其最大值，再想增加速度和性能，只有依靠大規(guī)模并行及硬件了。各種計算技術(shù)在地理學中不再局限于模型應用和科學研究了，已經(jīng)開始應用到大規(guī)模的分析和決策系統(tǒng)中。新的技術(shù)技

4、術(shù)的發(fā)展，地理計算提供了無限可能，如并行計算、移動計算、網(wǎng)絡計算、網(wǎng)格計算、對等計算、公用計算。,內(nèi)容,§2.1高性能計算§2.2并行計算§2.3網(wǎng)絡計算§2.4網(wǎng)格計算,§2.1高性能計算,高性能計算是利用基于向量或并行處理器為基礎的超級計算機硬件對大容量資料，對需要進行實時分析與控制的系統(tǒng)，對那些復雜而又不能用其他手段來處理的現(xiàn)實世界（包括地理的時間、空間世界）所實施的計算。,

5、§2.1高性能計算,超級計算機的容量與運算速度是地理學60年代“計量革命”時期所用計算機的109倍，是70年代初期“數(shù)學模型革命”時期的108倍，比80年代中期“GIS革命”時期高106 倍，比基于Pentium處理器的工作站快103倍。正是以這種高性能為基礎的地理環(huán)境中具有全球性或大區(qū)域性時、空演變特征的地理現(xiàn)象（數(shù)值天氣預報、全球氣侯變化、GIS和RS圖像解譯等）模擬才有可能真正實現(xiàn)。基于高性能計算的模擬成為創(chuàng)新、認知

6、的工具；高性能計算成為與理論、實驗具有同樣重要性的科學工具，在或是理論模型復雜、甚至尚未建立，或是因費用昂貴而使實驗無法進行的情況下，高性能計算成為求解問題的唯一有效手段。,地球模擬,§2.1高性能計算,高性能計算的實現(xiàn)依賴于迅速發(fā)展的并行硬件及其相應的軟件系統(tǒng)。前者以Cray T3D及其的新一代產(chǎn)品、并行虛擬計算機為代表的并行超級計算機，后者除一些常規(guī)并行編程語言外，地理學家們實施地理計算，更多地可望借助信息通道界面利用各種

7、語言編寫的軟件編碼系統(tǒng)。其首要任務是要研究并實施將現(xiàn)存的向量和串行的地理代碼，轉(zhuǎn)換成能為像由512個并行處理器組成的CRAY T3D這樣的超級計算機所接受的編碼系統(tǒng)。,§2.1高性能計算,高性能計算以并行高速計算為特征，以多處理器、多計算機或分布式系統(tǒng)為并行計算機的互聯(lián)形式。在系統(tǒng)的組成上，當今流行的主流并行計算機都是并行機，包括共享存儲的對稱多處理器、分布存儲的大規(guī)模并行機和工作站機群。整個高性能并行運算，其應用分為計算密集

8、型、數(shù)據(jù)密集型和網(wǎng)絡密集型3大類。在地理現(xiàn)象研究中，像數(shù)值天氣預報這樣的大數(shù)據(jù)處理當屬計算密集型的高性能計算應用，而像GIS的可視化計算應是數(shù)據(jù)密集型的高性能計算，至于現(xiàn)在正在研究發(fā)展中的3S集成技術(shù)和應用中所涉及到的，將是計算、數(shù)據(jù)和網(wǎng)絡3種密集型高性能運算的綜合，其真正意義上的實現(xiàn)還需作很大努力。,§2.1高性能計算-超級計算機,英國，2000年HPC的性能達到0.5個萬億次（TF）。美國HPC性能達到10-100個TF

9、，2001年IBM的White ASCI超級計算機配置了8192個IBM Power3處理器和160TB字節(jié)的磁盤存儲器，能夠達到每秒12.3萬億次的運算速度。2002年11月，美國IBM負責開發(fā)一款名為“ASCI Purple”的超級計算機。該系統(tǒng)運算速度最高可達每秒100萬億次浮點運算。,加速戰(zhàn)略計算創(chuàng)新（ASCI）,美國克林頓總統(tǒng)在1995年8月11日宣布：“美國決定謀求真正的“零當量”全面禁止試驗核武器條約”。通過逼真的建模和

10、模擬計算來取代傳統(tǒng)的反復試驗的工程處理方法,1976年,大規(guī)模并行計算機，強調(diào)處理器數(shù)目極多ASIC White該系統(tǒng)硬件環(huán)境由一個IBM RS/6000 SP系統(tǒng)構(gòu)成，含有512個SMP節(jié)點。每個節(jié)點含有16個處理器(512*16=8192)，系統(tǒng)總共有8192個CPU，峰值速度達到12.3Tflops。所有節(jié)點都經(jīng)過內(nèi)部SP開關網(wǎng)絡互連。,ASIC Q374個32（374×32=11968)路AlphaServer&

11、#160;GS320 系統(tǒng)構(gòu)成，采用英國QSW公司的QsNet開關網(wǎng)互連，帶寬最高可達340MB/s。占用5個籃球場的面積（約2000平方米） 目前完成兩臺10Tflops巨型機。,ASCI Blue Mountain （第28名）系統(tǒng)由48個Origin2000（128CPU的共享存儲器多處理機， 48×128＝6144）構(gòu)成，采用HIPPI-800組成三維環(huán)網(wǎng)完成其間的互連。,ASCI Blue-PacificIBM

12、3.89 TeraOPs Peak 4*5856 =23424處理器2.6 Terabyte Memory52.5 Terabyte Storage,ASCI RedIntel 3.15 萬億次 ，2 ×9360＝18720 1.2 Terabyte Memory 12.5 Terabyte Storage,地球模擬器（向量并行計算機）節(jié)點：由8個8Gflops的向量處理器共享16GB高速存儲器構(gòu)成全系統(tǒng)640

13、個節(jié)點，專用交叉開關網(wǎng)絡互連8×640＝5120處理器,,§2.1高性能計算-超級計算機,我國對高性能計算技術(shù)的發(fā)展給予了高度的重視。相繼研制出曙光-1全對稱（SMP）并行機、曙光- 1000 大規(guī)模并行處理（MPP）系統(tǒng)和基于機群結(jié)構(gòu)的曙光-1000A及曙光-2000系列百億次高性能計算機。國防科技大學83年研制成功我國第一臺銀河-Ⅰ億次巨型計算機起，先后研制成功銀河-Ⅱ十億次巨型計算機、銀河- Ⅲ百億次巨型

14、計算機和銀河-Ⅰ、銀河-Ⅱ型全數(shù)字仿真計算機、銀河小型巨型計算機。曙光和銀河系列百億次并行計算機的商品化，高性能計算機基礎研究和關鍵技術(shù)的突破，以及更高性能并行機的相繼研制成功，縮小了我國高性能計算技術(shù)研究與世界水平的差距，為我國信息化建設和國防現(xiàn)代化提供了強有力的工具。經(jīng)過50多年的發(fā)展，我國在計算技術(shù)方面確實有了巨大進步，但是同國際先進水平的差距反而比50多年前增大?！斑@種差距仍有著繼續(xù)增加的趨勢?！?§2.1高性能計

15、算-超級計算機,新華網(wǎng)天津2010年６月１日電（記者周潤?。翟拢常比照桨l(fā)布的第３５屆全球超級計算機前５００強排行榜上，中國首臺實測性能超過千萬億次的高性能計算機曙光“星云”躋身世界超級計算機第二位，我國首臺千萬億次高性能計算機“天河一號”位列第七位。據(jù)曙光資料，星云系統(tǒng)運算峰值達到每秒3000萬億次（3PFlops），實現(xiàn)Linpack值每秒1271萬億次（1.271PFlops），是中國第一臺、世界第三臺實現(xiàn)雙精度浮點計算超千萬

16、次的超級計算機，且其單位耗能所提供的性能達到了4.98億次/瓦?！∈锕赓Y料還顯示，星云超級計算機采用自主涉及的HPP體系結(jié)構(gòu)，由4640個計算單元組成，采用了高效異構(gòu)協(xié)同計算技術(shù)，系統(tǒng)包括了9280顆通用CPU和4640顆專用GPU組成。計算網(wǎng)絡采用了單向40Gbps QDR Infiniband技術(shù)，核心存儲采用了自主涉及的Parastor高速IO系統(tǒng)。,§2.1高性能計算,但是對GC來說，如果它是為了解決各種困難的、感興趣

17、的或重要的問題而尋找各種計算方法，或者限制在機器速度能承擔的上面來，那么過不久，GC真正的發(fā)展限制就會出現(xiàn)。,§2.2并行計算,§2.2.1 什么是并行計算§2.2.2 并行計算機的類型§2.2.3 并行的方法和分解策略§2.2.4 何時使用并行計算§2.2.5 怎樣使用并行編程§2.2.6 并行計算的體系結(jié)構(gòu)§2.2.7 網(wǎng)絡并行系統(tǒng)

18、7;2.2.8 并行算法和并行效率評測§2.2.9 地理學中的超級計算：巨大的挑戰(zhàn)§2.2.10 并行可視計算,§2.2并行計算,計算機系統(tǒng)性能增長的根本因素有兩個：一個是微電子技術(shù)，另一個是計算機體系結(jié)構(gòu)技術(shù)。制造大規(guī)模集成電路的工藝在實驗室已經(jīng)達到0.3微米，但是，極限無疑是存在的，因為晶體管的形體尺寸最終受到氫原子（最小的原子）直徑尺寸的限制，同時電信號的傳輸速度終將受到光速（宇宙最高速度）的

19、限制。因而要想進一步提高計算機的運算速度和性能必須從體系結(jié)構(gòu)技術(shù)上找出路，由此產(chǎn)生了并行處理技術(shù)。,§2.2并行計算,并行處理技術(shù)已成為計算機界最熱門研究課題之一。高性能計算機是國家國力和科技水平的標志。像中長期天氣預報，全球氣候變化，地球物理勘探，空氣動力學模擬，原子、粒子結(jié)構(gòu)探索，生物大分子結(jié)構(gòu)解釋，大氣污染研究，新飛機和武器系統(tǒng)的研制，新材料的設計和新藥劑的研制等學科和領域，都迫切要求計算機有每秒千億次萬億次甚至更高

20、的速度。唯有大規(guī)模并行處理系統(tǒng)（MPP系統(tǒng)）才可能實現(xiàn)這一要求。分布式可擴展計算并行由于其良好的可擴展性和可移植性，正逐漸成為并行計算發(fā)展的主流?，F(xiàn)在科學家正用并行計算構(gòu)建一個虛擬太空（Nature，2005），預計2010年能完成。,§2.2并行計算,本節(jié)將討論并行計算技術(shù)（也稱并行處理），首先討論什么是并行計算，地理學者為什么關心地理計算，并簡要回顧超級計算的歷史以及并行計算機的出現(xiàn)，然后論述并行計算的優(yōu)缺點，描述如何

21、進行并行計算。,§2.2.1 什么是并行計算,最簡單的描述并行就是，為加速完成一個費時計算的任務而在同一時間采用多個處理器或處理單元。這和單處理器多線程是不同的概念，單處理器多線程是將處理器的時間進行分段來處理多個任務。同時這里還要和特殊的單處理器并行工作分開（如圖形控制和磁盤管理）。,§2.2.1 什么是并行計算,Almasi給出這樣的定義：并行處理系統(tǒng)是一個由若干處理單元構(gòu)成的集合，集合中的處理單元能夠互相通信并

22、互相協(xié)同以快速解算大題目。這是一個準確的定義，它刻畫了并行處理系統(tǒng)的基本特征——由若干個能互相通信的處理單元構(gòu)成的處理機集合，和基本功能——互相協(xié)同以快速解算大題目；這又是一個“朦朧”的定義，對于并行處理系統(tǒng)的諸要素，它沒有給出明確的界定。,§2.2.1 什么是并行計算,對各種任務其并行處理的適應性也不同。有些任務很容易進行并行處理。如，假設砌墻蓋房一個人的話需要16天，那么四個人同時進行的話只需4天。加速度是用來描述并行

23、處理效果的，可以定義為一個處理器使用的時間除以N個處理器運行的時間，加速度值越接近N說明并行處理性能越好。,§2.2.1 并行計算--并行性,并行性是問題中具有可以同時進行運算或操作的特性。在同一時刻或是同一時間間隔內(nèi)完成兩種或兩種以上性質(zhì)相同或不同的工作，它們在時間上能互相重疊，都體現(xiàn)了并行性。并行性實際上包含了同時性和并發(fā)性二重含義。同時性指的是兩個或多個事件在同一時刻發(fā)生；并發(fā)性指的是兩個或多個事件在同一時間間隔內(nèi)發(fā)

24、生。,§2.2.1 并行計算--并行性,時間重疊是在并行性概念中引入時間因素，讓多個處理過程在時間上相互錯開，輪流重疊的使用同一套硬件設備的各個部分，以加快硬件周轉(zhuǎn)而贏得速度。資源重復是在并行性概念中引入空間因素。通過重復設置硬件資源來提高可靠性或并行性能。資源共享是利用軟件的方法讓多個用戶按一定時間順序輪流地使用同一套資源，包括CPU、主存、外設等硬件資源和軟件、信息資源，以提高其利用率，從而提高整個系統(tǒng)的性能。例如

25、，多道程序分時系統(tǒng)等。,§2.2.2 并行計算機的類型,Flynn（1972）基于指令程序和數(shù)據(jù)適應的不同把計算機分為4類。,§2.2.2 并行計算機的類型,SISD處理器是一個時間對一個數(shù)據(jù)塊進行一個指令，典型的von Neuman計算機就是這樣的處理器。它有兩個非常重要的特征：串行和確定性。因這種操作按順序進行，易于跟蹤和理解。MISD能對某數(shù)據(jù)塊同時進行多指令，很明顯它在現(xiàn)實中沒有應用，是個不存在的類型。,

26、§2.2.2 并行計算機的類型,SIMD機器具有一系列前后銜接，步調(diào)一致的處理器，同時對不同的數(shù)據(jù)塊進行相同的操作，但在任何時間點上只有一個指令在執(zhí)行。該類型計算機的主要特征是：同步的、確定的、指令或操作并行的。這種類型的機器局限于一定類型的任務，對許多實際的任務還不實用。陣列處理機、流水線處理機、關聯(lián)處理機等均屬于該類計算機。MIMD機器能同時對不同的數(shù)據(jù)塊進行不同的指令操作。能讓程序員更靈活地編寫程序，使算法適應機器來

27、完成各種任務。該類型計算機的特征是：指令可同步或異步、指令的執(zhí)行可確定的和不確定的、適合塊、回路和子程序級的并行。多處理機和多計算機都屬于此類計算機。,§2.2.2 并行計算機的類型,并行機器也可根據(jù)內(nèi)存使用情況分為共享內(nèi)存并行和分布式內(nèi)存并行。在共享內(nèi)存并行機中，所有的處理器都連通到機器的同一內(nèi)存上，這可能產(chǎn)生問題：如果多個處理器多想對同一變量同時進行賦值，第一個能成功還是最后一個，該如何是好？即使能讓你寫代碼來處理這種爭奪

28、問題的排序，但因不同的處理器的不同運行，讓你也很難來跟蹤這個問題。同時因不同處理器都試圖讀寫內(nèi)存，也使內(nèi)存的開辟、分配、管理亂為一團。,§2.2.2 并行計算機的類型,分布式內(nèi)存并行機器中就克服了上述問題，它由處理單元構(gòu)成，每個處理單元包括一個處理器和一定的內(nèi)存，每個處理器進能處理與之關聯(lián)的內(nèi)存，另外一個處理器需要它的數(shù)據(jù)值可以通過明確的消息來處理?，F(xiàn)在計算機已經(jīng)可以通過虛擬內(nèi)存來達到分布式內(nèi)存。,§2.2.3并行的

29、方法和分解策略,在并行計算中，計算是在多個數(shù)據(jù)塊上同時進行，或者問題是通過多個處理機同時處理解決。根據(jù)并行的體系不同并行可以在不同的層次上進行。主要有三種類型的并行：任務或事件并行、數(shù)據(jù)或幾何并行、算法或過程并行。過程并行是處理機有特殊的任務并且數(shù)據(jù)塊要按一定的順序的通過，更簡單的理解就是串行后的并行。,數(shù)據(jù)并行,數(shù)據(jù)并行把要處理的數(shù)據(jù)集做合理劃分，分配到可用的處理器上，各處理器并行執(zhí)行各自的數(shù)據(jù)。 數(shù)據(jù)并行有基于記錄（Re

30、cord）的數(shù)據(jù)并行和基于屬性（Attribute）的數(shù)據(jù)并行兩種主要途徑。,任務并行,任務并行是把解決問題的整個過程分成若干個子過程，將它們分派到不同的處理器上并行執(zhí)行。兩種途徑。第一種基于分而治之策略，這種策略首先對任務進行劃分，然后分派子任務到指定的處理器。第二種基于任務隊列，就是動態(tài)的把子任務分派到目前可用的處理器上。對于任務并行，所有的數(shù)據(jù)都是共享的，任何處理器都可以操作它們。所以，無論采用任務并行的哪種方式，都要仔細

31、考慮負載平衡的問題。任務并行的成功執(zhí)行在很大程度上依賴于對應數(shù)據(jù)集的結(jié)構(gòu)。,數(shù)據(jù)并行與任務并行相結(jié)合,當任務并行和數(shù)據(jù)并行結(jié)合起來考慮時，一種有效的方法就是先對數(shù)據(jù)合理劃分，把數(shù)據(jù)子集分配到各個處理器上。然后采用基于劃分和征用策略的任務并行方法，根據(jù)各個處理器上數(shù)據(jù)集的結(jié)構(gòu)特點，把子任務分配到指定的處理器上。最后，當每個處理器上的任務都執(zhí)行完畢后，再合并執(zhí)行結(jié)果。這樣做的好處就是，只在任務執(zhí)行的前后進行數(shù)據(jù)交換，任務可以不被打斷的執(zhí)行下

32、去，大大降低了任務執(zhí)行過程中進行同步和通信的開銷。因此在進行并行處理時應考慮以下一些問題：1）整個體系結(jié)構(gòu)的可伸縮性； 2）數(shù)據(jù)的分割；3）任務的劃分；4）通信花費；5）結(jié)果集成。,分解策略,完全并行分解、域分解和控制分解完全分解將問題分解成過程集合，它只需要附加初始化各過程和收集結(jié)果的通信負載。域分解是將構(gòu)成問題的目標或數(shù)據(jù)按一定的大小或粒度分配到每個處理機上，以達到高度的并發(fā)?？刂品纸怅P注于對應用控制的流程，主要有兩

33、種方法：功能分解和管理員/工人分解。功能分解是將問題分解成操作集，其中需要建立各處理機間的通信。管理員/工人分解使用一個主處理機來控制，動態(tài)的控制各處理機（工人），這種動態(tài)的任務處理更有效。,§2.2.4 何時使用并行計算,何時使用用并行計算能使我們節(jié)省時間，而不是冒然地就使用它。比如：代碼的運行頻率是多少？運行時間多久？如果說代碼運行重復度不高、時間不久那就根本別想用并行處理，因為采用并行處理時的費時可能比順序代碼要慢上2倍

34、還要多。如果該程序需要運行一兩次，且運行時間達一兩周，那它通常仍比采用并行處理要快。如果你的程序要運行一月或更久，那么并行處理可以考慮；如果該模型要運行成千上萬次，那并行計算就是必需的了。同時你還要考慮并行處理的規(guī)模，如果問題的核心很小且依賴前期的結(jié)果，則并行處理就不合適。如果考慮上述各問題，那你就可以使用并行技術(shù)，當然你還要考慮并行計算的類別、語言選擇問題等等。,§2.2.5 怎樣使用并行編程,要進行并行計算那么就需要并行

35、設備——并行計算機。如果沒有，也可以通過軟件（如PVM）使多個工作站連起來形成虛擬并行計算機，當然它沒有真正的并行計算機快，但比較便宜，并且可以給你足夠的時間來完善和發(fā)展你的并行軟件。,2.2.6 并行計算的體系結(jié)構(gòu),并行體系結(jié)構(gòu)是并行計算的基礎，各種并行程序設計機智也都是針對不同的并行體系結(jié)構(gòu)的。并行體系結(jié)構(gòu)大致可分為多處理共享內(nèi)存存儲并行機（SMP）、多處理分布共享存儲并行機（DSM）、大規(guī)模并行機（MPP）和機群，他們都屬于多指令

36、多數(shù)據(jù)流（MIMD）機器。并行計算體系結(jié)構(gòu)有許多種，其中最具代表性的四種體系結(jié)構(gòu)是：SMP、MPP、DSM以及COW 這四種體系結(jié)構(gòu)的結(jié)構(gòu)特征 系統(tǒng)特點和應用領域都存在較大的差異。,SMP 系統(tǒng) （Symmetic Multi-processor）,多處理系統(tǒng)是一種多處理機系統(tǒng)，在結(jié)構(gòu)上它一般是用總線將多個處理機連接而成的。在這種系統(tǒng)中硬件和軟件都是對稱的，在硬件方面每一個CPU的能力完全相等，它們共享主存，對存儲器的操作是對稱的，I/

37、O操作也是對稱的；在系統(tǒng)軟件方面（主要是操作系統(tǒng)），各處理機沒有主次之分，共享存儲器中只有一份操作系統(tǒng)代碼，每個處理器可以同時執(zhí)行操作系統(tǒng)的核心代碼。SMP（對稱多處理機）系統(tǒng)采用商品化微處理器，帶有片內(nèi)和片外高速緩存，這些處理器通過高速監(jiān)聽總線連接到共享存儲器，在某些SMP中，除了總線外還使用了縱橫交叉開關，下圖是SMP的體系結(jié)構(gòu)。,SMP,SMP系統(tǒng)相對于非對稱對處理機系統(tǒng)有更高的并行性。但是SMP系統(tǒng)的最大局限就是它的擴展性，

38、使用集中式共享存儲器和總線或縱橫交叉開關會限制處理器數(shù)量上的擴充，SMP 系統(tǒng)一旦建成就再難予以擴展。,SMP,這里需要特別指出的是SMP本身并不意味著并行處理，許多SMP的應用并不采用并行處理技術(shù)，其上也不運行任何并行程序，而只是利用其所具有的對稱多處理方式獲得系統(tǒng)對用戶作業(yè)的大吞吐量和I/O的大吞吐量，很多將SMP系統(tǒng)作為服務器的應用都屬于這種情況。,MPP 系統(tǒng) （Massively Parallel Processor）,大規(guī)模

39、并行機(MPP)是一種由大量處理機構(gòu)成的并行處理系統(tǒng)，一般認為MPP系統(tǒng)中處理單元的數(shù)目應當在100以上，或能支持100個以上的結(jié)點并行。所有的MPP系統(tǒng)都使用物理分布的主存，并且越來越多的MPP 正使用分布式I/O。每個結(jié)點有一個或多個處理器和高速緩存（P/C）、一個本地主存、以及數(shù)量不等的磁盤。結(jié)點內(nèi)使用總線或是更高帶寬的交叉網(wǎng)絡開關、連接處理器、主存和I/O設備。每個結(jié)點通過網(wǎng)絡接口電路與網(wǎng)絡相連，結(jié)點間是緊密耦合的。,MPP

40、,MPP主要有三部分組成： 1）結(jié)點結(jié)構(gòu)。 2）高速互連網(wǎng)絡。 3）并行程序開發(fā)環(huán)境。,DSM系統(tǒng),分布式共享存儲器系統(tǒng)（Distributed Share Memory，DSM）主要有兩種設計方法。第一種設計方法是采用高速緩存目錄用來支持分布式一致高速緩存。另外一種設計方法是利用特殊的硬件和軟件擴展實現(xiàn)DSM的。在DSM中存儲器是物理分布在不同結(jié)點中的，但是系統(tǒng)的硬件和軟件為用戶建立了一個單地址空間的幻覺。,D

41、SM,,機群Cluster of workstation, COW,對機群（Cluster）有許多稱呼，如計算機群、工作站群（COW）、個人工作站網(wǎng)絡（NOW）等。群機系統(tǒng)是將一組工作站、服務器、小型機甚至巨型機或MPP系統(tǒng)用互連網(wǎng)絡（目前一般用局域網(wǎng)）連在一起，構(gòu)成并行處理系統(tǒng)。因為通常用工作站實現(xiàn)，因此也稱為工作站群機系統(tǒng)。COW是全體計算機（結(jié)點）的集合，這些計算機由高性能網(wǎng)絡或局域網(wǎng)（LAN）物理互連。一般情況下，每個結(jié)點

42、是一臺SMP服務器、一臺工作站或是一臺PC計算機。除了滿足用戶單獨使用某個結(jié)點完成協(xié)定的任務之外，所有COW的結(jié)點必須能夠一起集體工作，如同一個單一集成的計算資源。,機群COW,COW的每個結(jié)點是一臺完整的計算機，有自己的處理器、存儲器、磁盤、高速緩存、I/O適配器。每個結(jié)點上駐留有完整、標準的操作系統(tǒng)。每個結(jié)點可以有多個處理器，但是只有一份操作系統(tǒng)的映像。網(wǎng)絡接口與結(jié)點中的I/O總線是松藕合相連的。結(jié)點之間通常使用商品化網(wǎng)絡互連，并且

43、可以使用標準的網(wǎng)絡通信協(xié)議（如TCP/IP）。整個COW體現(xiàn)的是一個單一的系統(tǒng)映像，這可以通過單一系統(tǒng)映像基礎設施來完成。機群系統(tǒng)主要由以下一些重要部件組成：多個高性能計算機（工作站、PC或SMP）；優(yōu)秀的操作系統(tǒng)（分層或基于微內(nèi)核）；高性能網(wǎng)絡/開關（如千兆位以太網(wǎng)）；網(wǎng)絡接口卡（NIC）；快速通信協(xié)議和服務（如活動消息和快速消息）；機群中間件（單一映象系統(tǒng)和系統(tǒng)可用性基礎）；并行編程環(huán)境和工具（如編譯器、PVM、MPI）；應用程序。

44、,機群COW,注：OS-操作系統(tǒng)；P/C-處理器和高速緩存；M-存儲器；Bridge-橋關；LD-本地磁盤；IOB-I/O總線；NIC-網(wǎng)絡接口電路；MB-存儲器總線,§2.2.7網(wǎng)絡并行系統(tǒng) （Network Computing，NC）,繼傳統(tǒng)Internet與萬維網(wǎng)之后，網(wǎng)絡計算被視作Internet的第三次浪潮。 對某些并行計算和高性能計算問題，網(wǎng)絡計算完全可以取代巨型并行機，并在下面三個方面具有優(yōu)勢：1）在保證性能

45、與并行機相當?shù)那闆r下，費用較??；2）工作站可升級，便于提高系統(tǒng)性能；3）允許部分工作站失敗，可靠性上更高。,§2.2.7網(wǎng)絡并行系統(tǒng),網(wǎng)絡并行計算需要網(wǎng)絡并行化環(huán)境，在這個環(huán)境下構(gòu)建一種并行虛擬機，虛擬機的成員可以是網(wǎng)絡連接的所有機器資源，也可以只使用其中的單機。依據(jù)用戶不同的要求，以及不同的并行計算機系統(tǒng)，決定使用不同的并行編程環(huán)境。在不同的編程環(huán)境下，應用程序會有不同。而可移植性好的并行編程環(huán)境會做到，用戶在該環(huán)境下寫的程

46、序不必作大的修改，就能夠在其他可移植的編程環(huán)境下運行。目前，國內(nèi)外在網(wǎng)絡并行計算的編程環(huán)境方面己經(jīng)做了大量研究，并行程序開發(fā)環(huán)境主要包括并行語言及其編譯系統(tǒng)、程序優(yōu)化重構(gòu)工具、圖形可視化工具、編輯工具及智能性工具等，較流行的并行程序開發(fā)環(huán)境有PVM、MPI、Express、Linda 等。,§2.2.7網(wǎng)絡并行系統(tǒng),網(wǎng)絡并行計算則是以網(wǎng)絡連接工作節(jié)點，即通過網(wǎng)絡的數(shù)據(jù)傳輸完成CPU的耦合?？梢哉f這個分支在某種意義上說是繼承

47、了大型機中央處理方式卓越的性能以及穩(wěn)定性等優(yōu)越性的同時又吸收了分布式處理技術(shù)中網(wǎng)絡和計算機的組合優(yōu)勢。換句話說，網(wǎng)絡并行計算技術(shù)是用廉價的高速網(wǎng)絡通信技術(shù)取代了昂貴的多CPU技術(shù)并具有高性能的同時又獲得了良好的可擴展性和靈活性，這些因素都使得網(wǎng)絡并行計算技術(shù)在高性能計算領域倍受關注。,§2.2.7網(wǎng)絡并行系統(tǒng),網(wǎng)絡并行計算環(huán)境指的是由底層結(jié)構(gòu)、網(wǎng)絡并行計算系統(tǒng)兩大模塊構(gòu)成的一個計算環(huán)境。首先，整個計算環(huán)境的基礎是由局域網(wǎng)絡和操

48、作系統(tǒng)構(gòu)成的底層結(jié)構(gòu)。操作系統(tǒng)可以是任何一種多任務的操作系統(tǒng)。其次，在底層結(jié)構(gòu)的上一層是網(wǎng)絡并行計算系統(tǒng)，這一層是整個計算環(huán)境的核心，它賦予該環(huán)境并行計算能力，該系統(tǒng)的功能是屏蔽底層平臺相關細節(jié)并向上一層的用戶并行程序提供并行計算服務。,PVM,PVM（Parallel Virtual Machine）的開發(fā)最早開始于1989年夏天，目前它的開發(fā)隊伍包括美國橡樹嶺國家實驗室，Tennessee大學等單位，并得到美國能源部、國家科學基金以

49、及田納西州的資助。PVM是一種計算機網(wǎng)絡的并行實驗系統(tǒng)，具有適應性強的特點，能夠在多種流行的工作站機群及MPP機上運行。PVM 系統(tǒng)通過計算機網(wǎng)絡將計算機連接成一個邏輯上虛擬的并行計算機系統(tǒng)，PVM可視為一個工作站機群上的并行程序工作環(huán)境，提供支持并行計算機的并行程序函數(shù)庫。PVM的主要目標是：提供一個異構(gòu)型應用開發(fā)模型和相聯(lián)編程框架，以實現(xiàn)應用程序子任務向機器的最佳映射，并提供充分的異構(gòu)型跟蹤調(diào)試、可視化、監(jiān)控手段。,MP

50、I （Message Passing Interface）,消息傳遞并行編程環(huán)境 （MPI）是目前國際上最流行、可移植性和可擴展性很好的并行程序設計平臺，并被當前流行的所有高性能并行機所支持。MPI由MPI論壇開發(fā)，該論壇是一個有廣泛基礎的由并行計算機供應商、庫編寫者以及應用專家組成的聯(lián)盟。1992年在美國成立了MPI 委員會，由歐美的40個主要機構(gòu)60名代表組成。MPI是一個功能強大且較為完整的MPI并行庫規(guī)范。通過提供一個消息傳

51、遞庫的標準來實現(xiàn)它的可移植性。MPI用與具體編程語言無關的形式來說明庫。并提供了與Fortran和C語言的捆綁，并提供一套工具用于測試和改善并行程序的性能。MPI的目標是要開發(fā)一個廣泛用于編寫消息傳遞程序的標準，要求用戶界面實用、可移植、高效、靈活，同時它具有完備的異步通信功能和對COW工作站群并行機的內(nèi)在適用性。能用于各類并行機，尤其適用于分布式存儲的并行機。用MPI編寫的應用程序經(jīng)過重新編譯，可以在任何供應商提供的PC機、工作站、

52、MPP上相互移植。MPI已經(jīng)在IBM PC機、UNIX工作站和主要并行計算機上得到實現(xiàn)。尤其是它可以應用于Windows NT，并與C語言和Fortran77有著上百個函數(shù)調(diào)用接口，使得借助于普通網(wǎng)絡就能組建“個人超級并行計算機”。,PVM與MPI的比較,PVM和MPI的設計目的與側(cè)重點是不同的，PVM的研制工作是圍繞“虛擬機”的中心思想展開的，可移植性比速度得到了更多的重視，可伸縮性、容錯能力和異構(gòu)性也是研究的重點。而MPI旨在創(chuàng)建

53、一種標準的消息傳遞界面，速度是MPI設計中的焦點問題，因此在大型并行機系統(tǒng)MPP上，MPI被認為要比PVM速度快?？傮w上MPI程序可以在任何單機上運行，并在此意義上滿足可移植性，而PVM 程序可以在不同組成的一群機器之間進行移植（互協(xié)性）。MPI缺少較大的靈活性的原因是設計時優(yōu)先考慮了速度。PVM則犧牲了一些速度而換取了靈活性的增加。PVM 在資源與任務管理方面有一個較豐富的資源控制函數(shù)集可供使用。PVM可根據(jù)用戶的需要，隨時增加刪

54、除節(jié)點機，既可從虛擬機命令行也可從用戶的應用程序中進行。MPI就缺少這樣的動態(tài)特征，MPI標準不提供資源抽象，它是由每個MPI的具體實現(xiàn)和用戶自己去制定資源管理的方案。,§2.2.8 并行算法和并行效率評測,并行算法是適合于在各種并行機上求解問題和處理數(shù)據(jù)的算法。其嚴格定義為：一些可同時執(zhí)行的進程集合，這些進程互相作用、協(xié)調(diào)動作，從而達到對給定問題的求解。高效的并行算法是設計高質(zhì)量并行程序的基礎。并行算法主要來源于兩個方面：一

55、是將串行算法改寫成并行算法，二是從數(shù)學模型出發(fā)直接構(gòu)造并行算法。前者較容易實現(xiàn)，但由于受串行構(gòu)架的限制，難以取得較高并行度的算法。后者實現(xiàn)有一定難度，但深入研究將會使并行算法的設計有所突破，現(xiàn)已形成了一些理論和技術(shù)：NC 理淪、并行復雜度理論、下界技術(shù)、平衡樹法、倍增技術(shù)、分治策略、切分原理、流水線技術(shù)及對稱技術(shù)等。,§2.2.9 地理學中的超級計算：巨大的挑戰(zhàn),地理的多樣性給高性能計算帶來了發(fā)揮的空間。 高性能計算和并行計

56、算可為GIS提供多種服務，主要體現(xiàn)兩個方面：1）地理空間信息的存儲和獲取服務，指存儲空間信息到并行數(shù)據(jù)庫、數(shù)據(jù)結(jié)構(gòu)或格式的轉(zhuǎn)換等。2）地理分析和計算。3）實時可視化?，F(xiàn)在的可視化應用（如飛行模擬、分布式交互模擬DIS、虛擬現(xiàn)實）都需要計算機提供高性能的數(shù)據(jù)處理能力，這些應用都有性能和反應時間限制，而GIS的并行化能有效地解決這些問題，其中最合適的是SMP。,§2.2.9 地理學中的超級計算：巨大的挑戰(zhàn),并行技術(shù)給地理計算帶來兩

57、個好處：為我們表達、處理、分析和揭示地理空間及空間關系提供了新的方法和技術(shù)手段；同時大大提高地理計算的速度。目前來說，主要有兩個方面阻礙并行GIS的發(fā)展，一是基于internet的服務導向和基礎設施還不夠，HPC還不可接近，GIS和數(shù)據(jù)缺少互操作，OGC的開發(fā)網(wǎng)格服務體系（OGSA）正將WEB服務和網(wǎng)格服務聚集在一起，希望不久的將來能為HPC提出新的機遇。二是基礎性的問題，也就是創(chuàng)建并行GIS不是件容易的事情，還缺乏有效的算法、應用庫和

58、工具。,§2.2.10 并行可視計算,在實際應用時采用并行LOS可視算法來確定目標的可視度，這些目標可以是地形上的高程點、建筑物、道路線等。這也是有關站點選址規(guī)劃時在進行可視影響和分析時要考慮的。由于越來越多的海量空間數(shù)據(jù)可用，特別是高精度的DEM數(shù)據(jù)，對并行處理的要求逐漸增加。,可視分析,并行可視計算,并行可視處理的關鍵是定義應用問題和每個處理機/器的工作量，這樣系統(tǒng)才能在較優(yōu)化的性能下運行。對實行可視分析并行群的構(gòu)建，可采

59、用100Mhz Pentium的PC機，NT系統(tǒng)，10M網(wǎng)絡，采用PVM和C編程。PVM提供了任務管理。并行方法上采用管理員/工人的策略，主結(jié)點負責創(chuàng)建其他結(jié)點和通信，包括初始化、分配任務和收集結(jié)果。這種模型比較簡單，但其有個固有的缺點，就是和主結(jié)點的通信會存在瓶頸，但可以通過增加次主結(jié)點來改善此問題。,并行可視計算,在數(shù)據(jù)管理上，最簡單的形式是所有的結(jié)點都獲取整個DEM或其拷貝，或者通過等級結(jié)構(gòu)或虛擬共享內(nèi)存來處理。對可視分析來說，需

60、要所有的結(jié)點都獲得整個DEM，其他的管理還包括發(fā)送、配置參數(shù)和收集結(jié)果。,§2.3網(wǎng)絡計算,§2.3.1 網(wǎng)絡計算的含義§2.3.2 網(wǎng)絡計算機§2.3.3網(wǎng)絡計算結(jié)構(gòu)模式：集中式和分布式§2.3.4網(wǎng)絡計算的特點和優(yōu)點§2.3.5網(wǎng)格計算§2.3.6網(wǎng)絡計算與GIS,§2.3.1網(wǎng)絡計算的含義,“網(wǎng)絡計算”實際上是指以網(wǎng)絡為中心的計算，或是基于網(wǎng)

61、絡的計算，它將是21世紀初科學計算和開發(fā)信息應用系統(tǒng)的主要趨勢。我們也可以把現(xiàn)階段的“網(wǎng)絡計算”在技術(shù)層次上作這樣的定義：把計算功能和負荷合理地分配到聯(lián)網(wǎng)的客戶機和服務器上，這些開放的聯(lián)網(wǎng)計算機應具有的功能是其用戶界面應該是web/browser 型的，應用軟件的內(nèi)容應該是用HTML或XML編寫的，在運行系統(tǒng)中具有Java和CORBA的功能。實現(xiàn)網(wǎng)絡計算最必需的支撐技術(shù)就是建立與平臺無關的、以網(wǎng)絡為中心的計算環(huán)境。,§2.3.

62、2 網(wǎng)絡計算機,1995年，ORACLE公司提出網(wǎng)絡計算機（network computer）的概念，引起了極大反向。NC沒有硬盤、光驅(qū)、軟驅(qū)，所有數(shù)據(jù)存儲運算都通過網(wǎng)絡繼續(xù)，并且有人預言“NC將無處不在”，但事實的發(fā)展卻大出他們意外，主要由于標準未成熟、網(wǎng)絡速度的問題。隨著相關技術(shù)的不斷發(fā)展，網(wǎng)絡計算機概念也在不斷變化，網(wǎng)絡計算機技術(shù)也逐步成熟，NC再次受到人們的高度重視。主要原因有：網(wǎng)絡計算的發(fā)展；Linux操作系統(tǒng)流行并為人們所接

63、受；網(wǎng)絡安全重視度增加。網(wǎng)絡計算機主要有三個類型：真NC，完全符合NC規(guī)范，非wintel結(jié)構(gòu)；類NC，客戶端采用windows終端；反NC，也稱NETPC，是Microsoft和Intel對抗NC的產(chǎn)品，該計算機有硬盤，但整機是密封的。,§2.3.3結(jié)構(gòu)模式：集中式和分布式,集中式結(jié)構(gòu)的優(yōu)點是計算環(huán)境和資源都集中于同一部機器內(nèi)，在程序開發(fā)和使用管理上很簡單，但它的購置、安裝和維護費用高；多用戶分享同一資源時服務質(zhì)量受影響

64、；風險大，服務器死機整體癱瘓；擴展性差。主要有主機/終端、工作站/文件服務器兩種類型。分布性主要指數(shù)據(jù)分布和計算分布，數(shù)據(jù)分布是指數(shù)據(jù)可分散存儲在網(wǎng)絡上的不同計算機中；計算分布則是把操作計算分散給不同的機器進行處理。在物理上，分布式數(shù)據(jù)庫的資源結(jié)構(gòu)與分布式的組織結(jié)構(gòu)相吻合；而邏輯上的相關性，又使它們可以利用計算機網(wǎng)絡集成為功能強大的系統(tǒng)。,§2.3.4 網(wǎng)絡計算的主要優(yōu)點：,1）充分利用資源。計算機可自由地、主動地訪問各種

65、資源。避免了資源的重復和浪費，提高了資源的利用效率。2）網(wǎng)絡計算具有獨特的優(yōu)勢：計算資源可方便地任意擴展；采用備份、冗余和任務轉(zhuǎn)移等技術(shù)使系統(tǒng)具有更高的可靠性。3）較強的計算能力。當連接到網(wǎng)絡里的計算機達到一定數(shù)量，其協(xié)同計算的能力則會呈級數(shù)方式增強，使更迅速開發(fā)和部署新的計算應用成為可能。4）管理和控制的集中化和簡化。網(wǎng)絡計算環(huán)境是一個有機的整體，更容易管理和控制。同時大大簡化了管理的方法、減少了管理所需的人員。5）降低計算的

66、成本。由于網(wǎng)絡計算的能力較強、能充分利用資源、可擴展性強、管理和控制的簡化、不用拋棄原有的計算設備購置新的設備，就能獲得更強的計算功能等優(yōu)點，大大提高了計算的性能價格比，降低了大型科學計算和企業(yè)計算的成本。,§2.3.5 網(wǎng)格計算,高性能計算的應用需求使計算能力不可能在單一計算機上獲得，因此，必須通過構(gòu)建“網(wǎng)絡虛擬超級計算機”或“元計算機”來獲得超強的計算能力。元計算被定義為“通過網(wǎng)絡連接強力計算資源，形成對用戶透明的超級

67、計算環(huán)境”，而“網(wǎng)格計算”更系統(tǒng)化地發(fā)展了最初元計算機的概念，它通過網(wǎng)絡連接地理上分布的各類計算機（包括機群）、數(shù)據(jù)庫、各類設備和存儲設備等，形成對用戶相對透明的虛擬的高性能計算環(huán)境，應用包括了分布式計算、高吞吐量計算、協(xié)同工程和數(shù)據(jù)查詢等諸多功能。網(wǎng)格計算被定義為一個廣域范圍的“無縫的集成和協(xié)同計算環(huán)境”，它已經(jīng)發(fā)展為連接和統(tǒng)一各類不同遠程資源的一種基礎結(jié)構(gòu)。,網(wǎng)格計算,網(wǎng)格技術(shù)采用新型技術(shù)通過高速網(wǎng)絡連接并集成地理上分布的、異構(gòu)

68、的各種高性能計算機系統(tǒng)、軟件系統(tǒng)、大型數(shù)據(jù)存儲系統(tǒng)、數(shù)字化儀器設備和控制系統(tǒng)等各種資源聯(lián)為一體，實現(xiàn)跨地域的、分布式的高性能聯(lián)合、協(xié)同計算，為用戶提供一體化的高性能計算服務、信息處理服務和決策支持服務，充分發(fā)揮網(wǎng)絡資源的綜合效能。網(wǎng)格計算的構(gòu)想來源于電力供應網(wǎng)，所以其基本思想也常被表述為：“就像人們?nèi)粘Ｉ钪袕碾娋W(wǎng)中獲取電能一樣獲取高性能的計算能力”。作為一個長期的設想，網(wǎng)格計算被劃分為四個階段，分別解決容量、數(shù)據(jù)、高對用性和安全公

69、用等問題。,網(wǎng)格計算,對網(wǎng)格技術(shù)的研究可按層次劃分為網(wǎng)格應用技術(shù)、網(wǎng)格編程技術(shù)、網(wǎng)格核心管理技術(shù)和網(wǎng)格底層支撐技術(shù)，其中對網(wǎng)格核心管理技術(shù)的研究又分為高性能調(diào)度技術(shù)、高吞吐率資源管理技術(shù)、性能數(shù)據(jù)收集分析技術(shù)和安全技術(shù)等幾個方面。,§2.3.6 網(wǎng)絡計算與GIS,目前處于試驗階段，網(wǎng)格GIS 還有一定的特殊性：1）元數(shù)據(jù)管理和信息服務：良好地表示、存儲、訪問和使用大量資源信息是數(shù)據(jù)網(wǎng)格運行的基本前提。元數(shù)據(jù)用于管理、描述、收

70、集、組織網(wǎng)格中的資源信息，用于描述資源、方法、數(shù)據(jù)集和用戶等信息。信息服務是元數(shù)據(jù)管理對外提供的基本服務，它實現(xiàn)資源實體的注冊和發(fā)布，支持資源相關性的發(fā)布，可以注冊與已注冊實體間的相互約束和相互聯(lián)系信息。網(wǎng)格GIS 中，需建立靈活的、可擴展的信息服務體系結(jié)構(gòu)。該體系結(jié)構(gòu)應當保證資源信息提供者的廣泛分布性和信息服務的分布特性，還應保證其安全性。2）數(shù)據(jù)訪問服務：網(wǎng)格中的所有元數(shù)據(jù)構(gòu)成元數(shù)據(jù)目錄，它采用統(tǒng)一的方式來描述元數(shù)據(jù)。元數(shù)據(jù)目錄應