擁抱多核時代

1、告別免費午餐擁抱多核時代Written by:Objects2013-3-12 11:20:00SuperMap空間分析并行計算實踐SuperMap空間分析并行計算實踐信息技術(shù)(InformationTechnologies，簡稱IT)領(lǐng)域，絕大多數(shù)定律 都會隨著技術(shù)的進步被人們淡忘，但有一些卻可以經(jīng)受住時間的考驗， 對信息技術(shù)發(fā)展帶來持久而深遠的影響，“摩爾定律”便是其中典型代表。 “摩爾定律”支配下的信息技術(shù)，64位系統(tǒng)和多核計算日益普及，如何充 分利用64位系統(tǒng)和多核環(huán)境下的計算資源成為系統(tǒng)設(shè)計和開發(fā)人員必 須面對的問題。地理信息系統(tǒng)(Geographic InformationSyst

2、em，簡稱GIS) 中的空間分析服務(wù)具有算法邏輯復(fù)雜、數(shù)據(jù)規(guī)模龐大的特點，屬于一種 計算密集型服務(wù)。針對該特點，我們將并行計算技術(shù)引入傳統(tǒng)空間分析 計算過程，充分利用64位大內(nèi)存和多核計算資源，大幅提升空間分析 計算性能。一、摩爾定律下的免費午餐摩爾定律是由英特爾創(chuàng)始人之一戈登摩爾(Gordon Moore)提出。 其內(nèi)容為：當價格不變時，集成電路上可容納的電子元件數(shù)目，約每隔 24個月(現(xiàn)在普遍流行的說法是每隔18個月)便會增加一倍，性能也 將提升一倍。換言之，相同性能的芯片產(chǎn)品，每隔18個月價錢就會降 低一半。該定律自1965年提出以來，始終較好的預(yù)測了半導(dǎo)體產(chǎn)業(yè)的發(fā)展趨勢，又由于半導(dǎo)體產(chǎn)

3、業(yè)的巨大影響力，該定律輻射到包括微處理 器、移動電話、個人電腦、互聯(lián)網(wǎng)等在內(nèi)的眾多IT領(lǐng)域。幾十年來， 包括處理器速度、內(nèi)存容量、網(wǎng)絡(luò)傳播速度等關(guān)鍵IT指標的發(fā)展大都 符合摩爾定律的描述。我們有理由認為，摩爾定律在一定程度上揭示與 展現(xiàn)了信息技術(shù)令人驚訝的進步速度。誕生于1946年的世界上第一臺 電子計算機，其計算速度是每秒5000次加減法運算，而今天個人電腦 的計算速度是每秒500億次浮點運算。三十五年前的英特爾8086處理 器僅有三萬個晶體管，而今天一個基于Nehalem架構(gòu)的英特爾酷睿i7 處理器集成了 7.74億個晶體管。Microprocessor Transistor Counts

4、 1971-2011 & Moores Law一與00alnwcmJJ.2.GOQI00014M)Dl.oOO.OOO.OOo-100,000,000 -10,000,000-1,000,000-100,000-T0,000Z300-ahewii (rarmior guM 曲訕際p ervej two 忡gC-bte5lK3f0fiXjnn 740：-EAinJ-Ctim honiiEAMDK19摩爾定律曲線(, 2012)伴隨著硬件技術(shù)的飛速發(fā)展，操作系統(tǒng)和各種應(yīng)用軟件無償享用 著硬件提升帶來的“免費午餐”。由于處理器生產(chǎn)廠商致力于摩爾定律描 述下的時鐘頻率提升，單

5、線程的應(yīng)用程序無需進行任何修改就可以在新 的處理器上獲得更高的性能，而功能更為強大，計算資源需求更多的操 作系統(tǒng)和應(yīng)用軟件又刺激著消費者進行硬件升級，從而構(gòu)成了個人電腦 工業(yè)的生態(tài)鏈。另一方面，Google（谷歌）公司的前CEO埃里克施密 特在一次采訪中指出，如果你反過來看摩爾定律，一個IT公司如果今 天和十八個月前賣掉同樣多的、同樣的產(chǎn)品，它的營業(yè)額就要降低一半。 IT界把它稱為反摩爾定律(Reverse Moores Law)。這個帶著悲情色彩 的反摩爾定律使得IT行業(yè)不可能像傳統(tǒng)行業(yè)那樣只追求量變，而必須 不斷尋找革命性的創(chuàng)造發(fā)明，不斷追趕技術(shù)的前進腳步。那些技術(shù)發(fā)展 趕不上摩爾定律要求

6、的公司，只能被市場無情的淘汰，任何一個大公司 都要保持足夠的警惕和研發(fā)投入，而任何一個小公司都有可能遇到讓自 己成長為下一個IT巨人的技術(shù)變革，這是一個最好的時代，也是一個 最壞的時代。二、多核時代的計算要求在單核CPU時代，處理器生產(chǎn)廠商提升CPU運算能力的主要途徑 是提高主頻。作為CPU的主要性能指標，主頻標志著每單位時間內(nèi)CPU 能夠執(zhí)行運算指令的數(shù)量。實際上，在單核CPU時代，處理器已經(jīng)實 現(xiàn)了多線程運算，通過在邏輯上模擬出多個CPU內(nèi)核，以實現(xiàn)多任務(wù) 調(diào)度和并發(fā)處理。然而，這些處理過程始終由單個CPU以線程切換方 式完成，運算負載由單個CPU承擔。而多核CPU則在真正意義上實現(xiàn) 了內(nèi)

7、核級別并行，與傳統(tǒng)的單核CPU相比，多核CPU帶來了更強的并 行處理能力和更高的計算密度，同時大大減少了散熱和功耗。而多核時 代的到來這也迫使應(yīng)用系統(tǒng)告別“免費午餐”，使用多線程(或多進程) 方式來充分利用多核環(huán)境下的計算資源。CPVUwmOHHi!圖2 256核服務(wù)器的CPU任務(wù)管理器(George Chu, 2010)當前，雙核和四核的個人電腦已經(jīng)非常普及，而服務(wù)器的內(nèi)核數(shù)量 更是被不斷刷新，但另一方面，由于目前針對多核開發(fā)和優(yōu)化的應(yīng)用程 序還相對較少，使得用戶無法切身感受多核計算環(huán)境下的性能提升。根 本原因是并行程序的開發(fā)難度非常之大，程序設(shè)計與開發(fā)人員需要面對 包括任務(wù)并行化、內(nèi)存管理

8、與使用、線程競爭與死鎖、多線程程序調(diào)試 等諸多技術(shù)問題。為了解決這些問題，眾多并行計算模型和框架應(yīng)運而 生，粉墨登場?？缙脚_的并行框架由于SuperMap軟件產(chǎn)品需要具有跨平臺的特性，因此我們在進行并 行計算框架的選擇時，需要考慮其不同平臺間的支持能力。當前業(yè)界應(yīng) 用較為廣泛的跨平臺并行計算框架，主要包括面向線程并行的OpenMP 框架和TBB框架，面向進程并行的MPI框架，以及OpenMP與MPI 的混合模式(Hybrid)0OpenMP (Open Multiprocessing):是一 一個支持多種平臺的共享內(nèi) 存并行計算API，支持平臺包括Solaris AIX、HP-UX、GNU/L

9、inux、 Mac OS X和Windows，支持語言包括C、C+和Fortran。它由一組編 譯器指令、API和環(huán)境變量構(gòu)成，適合于將已有代碼進行并行化改進。Parallel Task I Parallel Task II Parallel Task 111Master ThreadParall&l Task IParallel Task IIParallel Task III圖 3 OpenMP 并行計算示意圖(， 2012)TBB (Intel Threading Building Blocks):是一個由英特爾公司開發(fā) 的C+模板庫，主要目的是使得軟件開發(fā)者更

10、好的利用多核處理器。該 庫為開發(fā)者提供了一些線程安全的容器和算法，使得開發(fā)者無需過多關(guān) 注系統(tǒng)線程的創(chuàng)建、同步、銷毀等操作，將精力集中于業(yè)務(wù)邏輯的并行 化，可以與OpenMP互為補充。MPI (Message Passing Interface)：是- -個有著廣泛使用基礎(chǔ)以及專 業(yè)審查委員會管理的并行計算標準，其設(shè)計主要面向大規(guī)模機器和群集 系統(tǒng)的并行計算，其具體實現(xiàn)包括OpenMPI、MPICH和LAM-MPI等。Hybrid：即混合并行計算模式，主要是指在單機環(huán)境中使用OpenMP 進行線程級別的并行，并同時在由單機組成的群集環(huán)境中通過MPI進 行任務(wù)間的消息傳遞和并行計算，使用難度較高

11、。表1并行計算框架對比比較項目 OpenMP TBB MPI并行粒度線程 線程 進程內(nèi)存模式共享內(nèi)存共享內(nèi) 存分布式 內(nèi)存適用環(huán)境單機單機多機/群 集通訊機制*消息傳 遞易用性高中低跨平臺性是是是并發(fā)數(shù)據(jù)結(jié) 構(gòu)不支持支持不支持可擴展不支持 支持 不支持內(nèi)存分配總體來說，并沒有哪種并行計算框架可以適用于各種應(yīng)用開發(fā)，較 為合理的方案是根據(jù)應(yīng)用程序特點選擇適合自身的技術(shù)框架。當你需要 將已有程序進行并行化改進，而且希望快速看到改進效果時，OpenMP 是一個較理想的選擇。當你希望從零開始，完成一個并行化程序的開發(fā) 時，可能需要更多的關(guān)注TBB和MPI。而當你希望應(yīng)用程序既實現(xiàn)單 機線程級別的并行，

12、又可以在多機群集環(huán)境中發(fā)揮并行計算優(yōu)勢時，就 需要使用較為復(fù)雜的混合模式進行設(shè)計和開發(fā)。四、并行計算下的空間分析GIS空間數(shù)據(jù)隨著采集、傳輸、處理技術(shù)的進步，其規(guī)模不斷膨脹， 導(dǎo)致傳統(tǒng)串行空間分析方法面臨巨大壓力。而并行計算技術(shù)憑借其對于 多核計算資源的充分利用，以及可擴展的計算能力為海量空間數(shù)據(jù)的分 析提供了一種解決方案。本文中，我們主要以GIS空間分析中的水文分 析為代表，分享SuperMap水文分析模塊在并行計算方面的相關(guān)研究和 實踐工作。水文分析是水文科學(xué)、地理信息科學(xué)與計算機科學(xué)的交叉結(jié)合產(chǎn)物， 主要利用DEM柵格數(shù)據(jù)構(gòu)建水系模型，利用水系模型進行水流方向、 累積匯水量、流域、河網(wǎng)等

13、水文要素的計算與提取，實現(xiàn)DEM表面水 流過程的模擬和重現(xiàn)?？蓮V泛應(yīng)用于農(nóng)林業(yè)、區(qū)域規(guī)劃、災(zāi)害預(yù)測等諸 多領(lǐng)域，是GIS空間分析中的重要組成部分。由于水文分析是一個完整 的工作流程與分析體系，因此涉及較多分析方法，主要包括：填充偽洼 地、計算流向、計算累積匯水量、劃分流域（包括計算流域盆地、提取 匯水點和流域分割）、提取水系網(wǎng)絡(luò)（包括提取柵格水系、河流分析、 連接水系和提取矢量水系）圖4水文分析流程圖(SuperMap, 2012)由于水文分析模塊涉及分析功能較多，而應(yīng)用最為廣泛的是基于 DEM提取矢量水系，因此我們針對該流程進行并行計算實踐，主要涉 及填充偽洼地、計算流向、計算累積匯水量、計

14、算流域盆地和水系矢量 化功能。我們主要使用OpenMP并行計算框架，并根據(jù)具體算法使用非 連續(xù)內(nèi)存管理、線程池、線程任務(wù)分配等技術(shù)手段，進行水文分析相關(guān) 功能的并行計算改進，以期達到充分利用多核計算資源，提升水文分析 性能的目的。為了驗證改進算法的有效性，我們選取了三組不同規(guī)模的 DEM數(shù)據(jù)進行測試和分析。表2 DEM數(shù)據(jù)列表數(shù)據(jù)編 號行數(shù)目列數(shù)目數(shù)據(jù)量A3601360135 MBB1081411300320 MB5 GB為了保證測試效果，我們使用Dell PowerEdge 服務(wù)器進行測試， 其處理器為2個英特爾至強八核處理器，單核主頻為2.0 GHz，內(nèi)存 為 3

15、2 GB，操作系統(tǒng)為 64 位 Red Hat Enterprise Linux Server。首先使 用雙線程并行與原串行算法進行比較，測試結(jié)果如表3所示。表3雙線程并行計算性能統(tǒng)計功能點數(shù)據(jù)A數(shù)據(jù)B數(shù)據(jù)C串行并行串行并行串行并行填充偽洼地1411226184797551計算流向424024228126累積匯水量1589245421261流域計算744825225149提取水系211296553總時間422641828717361140加速比1.621.461.52時間單位：秒 )在辱中圖5數(shù)據(jù)C雙線程并行測試結(jié)果從測試結(jié)果中可以看出，雙線程并行算法相對于傳統(tǒng)串行算法有較 為明顯的性能提升。

16、由于各功能實現(xiàn)算法不同，內(nèi)部并行化所使用的技 術(shù)手段也存在差異，因此各算法性能提升幅度不同。但從總時間來看， 三組數(shù)據(jù)的加速比分別達到了 1.62、1.46和1.52,即水文分析各功能均 可以通過并行計算技術(shù)大幅提升原算法性能。為了進一步測試不同線程數(shù)目下并行算法的性能提升幅度，我們選 擇了填充偽洼地和流向分析兩個功能，分別使用不同的線程數(shù)目進行分析性能測試。填充偽洼地（數(shù)據(jù)c）800900串行并行”線程）井行3線程）并行（6線程） 并行（日線程）圖6數(shù)據(jù)C填充偽洼地功能測試結(jié)果流向分析（數(shù)據(jù)C(43圖7數(shù)據(jù)C流向分析功能測試結(jié)果從圖6和圖7可以看出，改進后的并行算法性能隨著線程數(shù)目的增 加而提升，但由于算法內(nèi)部無法實現(xiàn)完全的并行化，在線程數(shù)目增大到 8時，算法性能提升幅度減小，算法時間趨于平穩(wěn)。流向分析功能由于 算法結(jié)構(gòu)較適宜進行并行化處理，計算任務(wù)可以較均勻的分配到多個線 程上，因此分析