復(fù)雜地理計(jì)算并行算法性能評(píng)估技術(shù)研究

方金云，閔偉，陳翠婷，李棟賓

（1.中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京 100190；2.重慶大學(xué)軟件學(xué)院，重慶 401331）

0 引言

隨著對(duì)地觀測(cè)技術(shù)的飛速發(fā)展，地理信息系統(tǒng)（GIS）正呈現(xiàn)出數(shù)據(jù)海量化、應(yīng)用廣泛化、處理實(shí)時(shí)化的特點(diǎn)。為滿足這些需求，必然需要更強(qiáng)大的數(shù)據(jù)存儲(chǔ)和計(jì)算能力，因此，需要借助于高性能計(jì)算來解決這類問題［1］。地理計(jì)算既是數(shù)據(jù)密集型計(jì)算又是計(jì)算密集型計(jì)算，同時(shí)地理數(shù)據(jù)具有空間相關(guān)性的特點(diǎn)。因此，高性能地理計(jì)算與面向計(jì)算密集型的并行計(jì)算和面向數(shù)據(jù)密集型的分布式計(jì)算既有區(qū)別又有聯(lián)系。同一地理計(jì)算算法從設(shè)計(jì)到實(shí)現(xiàn)，依賴程序設(shè)計(jì)和實(shí)現(xiàn)者的能力，程序的性能千差萬別；同時(shí)由于并行程序在執(zhí)行過程中的復(fù)雜性及不可預(yù)見性，給并行程序的調(diào)試和優(yōu)化帶來了困難。因此并行程序開發(fā)人員迫切需要一套調(diào)試評(píng)測(cè)工具，以發(fā)現(xiàn)并行程序性能的瓶頸和熱點(diǎn)，為地理計(jì)算算法并行開發(fā)提供程序設(shè)計(jì)、實(shí)現(xiàn)和優(yōu)化指導(dǎo)。

國(guó)內(nèi)外已經(jīng)開發(fā)出一批用于并行程序進(jìn)行分析及調(diào)試的性能評(píng)估工具，這些工具各有優(yōu)勢(shì)和不足［2］，有些關(guān)注于工具的可擴(kuò)展性［3］，有些關(guān)注于更快的性能分析［4］。例如美國(guó)伊利諾斯大學(xué)開發(fā)的ParaGraph［5］，提供了20多種通用視圖，包括餅狀圖、柱狀圖和通訊流量圖等；美國(guó)威斯康星大學(xué)麥迪遜分校開發(fā)的Paradyn［6］通過W3模型實(shí)現(xiàn)，可以提供對(duì)性能問題的自動(dòng)查找，通過預(yù)設(shè)的可能性能問題，逐一判斷并驗(yàn)證定位性能問題；Scalasca［7］的一個(gè)明顯優(yōu)點(diǎn)就是具有良好的可擴(kuò)展性；HPCToolkit［8］是一個(gè)可以對(duì)串行程序和并行程序進(jìn)行性能評(píng)估的工具。國(guó)內(nèi)在性能可視化方面做了一些工作［9，10］。以上都是針對(duì)高性能計(jì)算的性能評(píng)估工具，主要面向計(jì)算密集型的計(jì)算，而地理計(jì)算既是計(jì)算密集型又是數(shù)據(jù)密集型的計(jì)算，因此本文主要對(duì)復(fù)雜地理計(jì)算并行算法性能評(píng)估工具中涉及的關(guān)鍵技術(shù)進(jìn)行研究。

1 性能評(píng)估工具技術(shù)架構(gòu)

1.1 性能評(píng)估工具架構(gòu)

本文性能評(píng)估工具架構(gòu)（表1）主要由代碼插樁模塊、事件搜集（監(jiān)測(cè)）模塊及展示模塊組成。MPI［11］程序源代碼在經(jīng)過編譯插樁和PMPI庫(kù)鏈接后生成可執(zhí)行程序，在程序運(yùn)行過程中會(huì)對(duì)事件信息進(jìn)行管理，同時(shí)收集每個(gè)進(jìn)程及線程的信息，每個(gè)事件的定義將會(huì)在主進(jìn)程中統(tǒng)一。在事件分析過程中，采用并行模式搜索和串行模式搜索同時(shí)進(jìn)行的方式可減少事件分析的時(shí)間，通過預(yù)先定義的事件模式計(jì)算性能信息，如通信時(shí)間、函數(shù)運(yùn)行時(shí)間、通信量等。最后評(píng)估工具讀取性能分析文件，可視化性能信息、性能指標(biāo)提供交互操作的瀏覽方式，選擇某一性能問題，可以展示該問題出現(xiàn)的代碼位置、函數(shù)調(diào)用層次結(jié)構(gòu)、所屬進(jìn)程，整個(gè)系統(tǒng)運(yùn)行的流程如圖1所示。

表1 評(píng)估工具架構(gòu)Table 1 Architecture of the evaluation tools

圖1 性能評(píng)估流程Fig.1 Flow diagram of performance evaluation

1.2 代碼自動(dòng)插樁

本性能評(píng)估工具采用事件跟蹤的方法，即靜態(tài)地插入事件監(jiān)測(cè)函數(shù)到應(yīng)用程序源代碼中，運(yùn)行時(shí)采集關(guān)心的事件，運(yùn)行后根據(jù)產(chǎn)生的事件跟蹤文件進(jìn)行性能分析。它可以自動(dòng)對(duì)所評(píng)估的程序結(jié)構(gòu)插入性能檢測(cè)庫(kù)函數(shù)，通過編譯、鏈接，生成可執(zhí)行文件，性能監(jiān)測(cè)函數(shù)記錄程序執(zhí)行的事件，最后根據(jù)這些事件跟蹤文件進(jìn)行性能數(shù)據(jù)分析。

1.3 運(yùn)行監(jiān)測(cè)及事件收集

被評(píng)測(cè)的程序和測(cè)量庫(kù)編譯在一起，形成可執(zhí)行文件。在程序運(yùn)行過程中，產(chǎn)生本地事件日志，此時(shí)分為2個(gè)步驟，一方面在機(jī)器本地進(jìn)行并行模式搜索，尋找程序熱點(diǎn)，生成模式分析報(bào)告；另一方面本地事件日志在主節(jié)點(diǎn)進(jìn)行合并，生成全局事件日志，再對(duì)其進(jìn)行模式搜索，生成模式報(bào)告。最后對(duì)兩份模式分析報(bào)告進(jìn)行合并，通過評(píng)測(cè)工具展示，生成的報(bào)告指導(dǎo)原程序進(jìn)行優(yōu)化。評(píng)測(cè)工具生成的事件日志還可以經(jīng)過轉(zhuǎn)化，以便第三方事件查看軟件查看。

1.4 性能日志數(shù)據(jù)分析展示

對(duì)生成的性能日志數(shù)據(jù)進(jìn)行可視化展示，顯示被評(píng)估程序的性能特征，例如：執(zhí)行時(shí)間、通信操作數(shù)、同步操作數(shù)、通信量、負(fù)載平衡指數(shù)等。同時(shí)對(duì)每個(gè)被選中的性能特征，展示更加精細(xì)化的特征，如選擇可執(zhí)行時(shí)間，展示該可執(zhí)行時(shí)間由哪些函數(shù)及操作構(gòu)成，每個(gè)函數(shù)和操作各占用多長(zhǎng)時(shí)間。通過這種方法可以找出程序哪部分執(zhí)行時(shí)間最長(zhǎng)，哪部分是性能瓶頸。性能特征采用樹狀圖的展示方式，如通訊這一指標(biāo)下面有點(diǎn)到點(diǎn)通訊、搜集通訊，點(diǎn)到點(diǎn)通訊下面有發(fā)送操作和接收操作，搜集通訊下面有交換操作，作為源操作和目的操作。樹狀圖把性能問題表現(xiàn)得更加直觀。

2 性能評(píng)估工具關(guān)鍵技術(shù)

2.1 性能數(shù)據(jù)采集技術(shù)

性能數(shù)據(jù)采集是性能評(píng)估的第一步，它通過采集、事件跟蹤等方法收集有關(guān)的性能數(shù)據(jù)，作為分析的依據(jù)。采樣是以一定的采樣周期對(duì)所關(guān)心的系統(tǒng)性能數(shù)據(jù)進(jìn)行記錄，事件跟蹤是由所關(guān)心的系統(tǒng)事件觸發(fā)跟蹤機(jī)制，記錄事件發(fā)生時(shí)的性能數(shù)據(jù)。采樣法容易產(chǎn)生大量的性能數(shù)據(jù)，適合用硬件實(shí)現(xiàn)。事件追蹤可以只記錄敏感事件的有關(guān)性能信息，數(shù)據(jù)量小于采樣法，使用更加靈活，故本文采用事件跟蹤法。

通過gcc的finstrument－functions編譯選項(xiàng)完成對(duì)函數(shù)的插樁，從而在進(jìn)入函數(shù)時(shí)調(diào)用：void＿＿cyg＿profile＿func＿enter（void＊this＿fn，void＊call＿site）；在函數(shù)退出時(shí)調(diào)用：void＿＿cyg＿profile＿func＿exit（void＊this＿fn，void＊call＿site）；獲取函數(shù)執(zhí)行時(shí)間、函數(shù)調(diào)用關(guān)系；對(duì)于MPI程序，利用MPI庫(kù)的包裝器PMPI獲取MPI操作的通訊數(shù)、通訊量等信息。

2.2 降低采樣干擾技術(shù)

事件追蹤法采用代碼插樁的方法，但代碼插樁會(huì)改變程序原有的行為特征，干擾程序的正常運(yùn)行。目前降低干擾的方法有：1）對(duì)干擾量進(jìn)行控制，在干擾插入和記錄事件信息時(shí)，根據(jù)干擾量對(duì)插入代碼進(jìn)行動(dòng)態(tài)調(diào)整，盡量減少對(duì)程序的影響；2）用硬件實(shí)現(xiàn)對(duì)性能數(shù)據(jù)的搜集，這種方法可以顯著減少對(duì)程序的干擾，但是受制于硬件條件。本文主要采用第一種方法，同時(shí)通過補(bǔ)償機(jī)制減少代碼插樁對(duì)原程序的影響。

2.3 性能日志并行分析技術(shù)

性能日志數(shù)據(jù)經(jīng)常達(dá)到幾個(gè)G甚至幾十G［12］，產(chǎn)生如此巨大的性能日志數(shù)據(jù)的原因可以歸結(jié)為：1）進(jìn)程數(shù)。隨著進(jìn)程數(shù)的增加，性能日志數(shù)據(jù)總量隨之增加，同時(shí)通訊操作數(shù)及同步操作也隨之增加。2）粒度。事件的多少取決于單位時(shí)間內(nèi)事件被產(chǎn)生的頻率。3）事件參數(shù)。一個(gè)事件的典型參數(shù)是進(jìn)程ID、時(shí)間戳、類型ID，此外還有很多特定參數(shù)。4）問題規(guī)模。一個(gè)典型的例子就是迭代數(shù)，隨著迭代數(shù)的增加，問題的執(zhí)行時(shí)間和事件數(shù)也隨之增加。

事件跟蹤數(shù)據(jù)指向源代碼區(qū)間、調(diào)用路徑和通訊操作等。為了減小跟蹤數(shù)據(jù)的存儲(chǔ)空間以及減少冗余事件，用標(biāo)示符ID表示對(duì)象。為了避免不同進(jìn)程之間的額外通訊，每個(gè)進(jìn)程可能使用不同的標(biāo)示符ID表示相同的對(duì)象。然而，在對(duì)程序行為進(jìn)行全局分析時(shí)，必須使用全局的對(duì)象ID，具有不同ID的相同本地對(duì)象必須被同一個(gè)全局對(duì)象ID替代，這個(gè)過程稱為歸一化。

每個(gè)進(jìn)程都有獨(dú)立的收集緩沖區(qū)用來存儲(chǔ)本地的事件跟蹤數(shù)據(jù)以及本地對(duì)象定義，這樣可以避免合并事件跟蹤數(shù)據(jù)之后再重新提取上述信息。當(dāng)程序的測(cè)量階段結(jié)束之后，每個(gè)進(jìn)程輪流發(fā)送自己的本地對(duì)象定義以及相應(yīng)的對(duì)象ID映射信息表給主進(jìn)程，主進(jìn)程把本地對(duì)象定義歸一合并成一個(gè)全局對(duì)象定義。主進(jìn)程把合并之后的ID映射信息表再發(fā)回給每個(gè)子進(jìn)程，子進(jìn)程利用全局ID映射信息表生成本地分析報(bào)告。

被評(píng)估程序在運(yùn)行過程中在本地產(chǎn)生性能數(shù)據(jù)，存放在本地內(nèi)存中，當(dāng)本地計(jì)算任務(wù)完成時(shí)，可以利用該進(jìn)程對(duì)本地內(nèi)存中的性能數(shù)據(jù)進(jìn)行分析，生成的結(jié)果發(fā)送給主進(jìn)程，減少主進(jìn)程對(duì)該部分性能數(shù)據(jù)進(jìn)行分析的工作量。同時(shí)有些分析必須等本地性能數(shù)據(jù)被合并成一個(gè)全局性能數(shù)據(jù)后才能進(jìn)行分析，所以每個(gè)進(jìn)程還要完成本地性能數(shù)據(jù)發(fā)送給主進(jìn)程的任務(wù)。主節(jié)點(diǎn)在等到所有從節(jié)點(diǎn)的性能數(shù)據(jù)后，將所有性能數(shù)據(jù)合并，然后進(jìn)行性能數(shù)據(jù)的串行分析。通過每個(gè)從進(jìn)程并行分析本地性能數(shù)據(jù)的方法，可極大減少主進(jìn)程的工作量，從而減少性能分析時(shí)間。

3 實(shí)驗(yàn)分析

圖2 緩沖區(qū)分析的性能評(píng)測(cè)局部視圖Fig.2 The local view of performance evaluation of the buffer analysis

對(duì)超過40M的中國(guó)城市點(diǎn)數(shù)據(jù)集進(jìn)行并行緩沖區(qū)分析，運(yùn)行4個(gè)MPI進(jìn)程，生成的性能數(shù)據(jù)展示圖如圖2所示。通過查看圖2緩沖分析的性能評(píng)測(cè)結(jié)果可知程序運(yùn)行過程中的詳細(xì)情況。首先需要說明的是，該性能指標(biāo)樹中的時(shí)間是程序運(yùn)行過程中MPI使用的所有進(jìn)程的時(shí)間總和。例如該緩沖分析程序非MPI操作部分耗費(fèi)了0.74s，但4個(gè)進(jìn)程每個(gè)使用的時(shí)間分別為0.25s、0.22s、0.19s、0.08s。通過該圖可知MPI的點(diǎn)到點(diǎn)通訊操作耗費(fèi)了0.37s，初始化耗費(fèi)了5.14s，總共有38次通訊操作，傳輸了371 000的字節(jié)數(shù)。實(shí)驗(yàn)證明該性能評(píng)測(cè)工具可以有效評(píng)測(cè)地理計(jì)算。

4 結(jié)論

本文介紹了針對(duì)復(fù)雜地理計(jì)算并行算法的性能評(píng)估工具及關(guān)鍵技術(shù)。通過在程序編譯期間對(duì)函數(shù)進(jìn)行插樁并鏈接監(jiān)視庫(kù)，對(duì)并行程序多進(jìn)程之間的通訊信息及函數(shù)調(diào)用依賴關(guān)系進(jìn)行捕獲分析，形成性能評(píng)估報(bào)告幫助開發(fā)者分析和優(yōu)化并行程序。目前基于編譯器選項(xiàng)及PMPI性能檢測(cè)庫(kù)獲取程序信息，通過并行技術(shù)分析大規(guī)模的性能日志。下一步要做的工作是進(jìn)一步優(yōu)化分析模塊性能、進(jìn)一步研究合適的評(píng)估模型及豐富性能數(shù)據(jù)可視化。

［1］ 蔡蕾.地理計(jì)算并行處理技術(shù)及性能評(píng)價(jià)模型研究［D］.國(guó)防科技大學(xué)，2011.

［2］ MOORE S，CRONK D，LONDON K，et al.Review of Performance Analysis Tools for MPI Parallel Programs［M］.Springer，2001.

［3］ GEIMER M，WOLF F：Scalable parallel trace－based performance analysis［A］.Proc.13th European PVM／MPI Conference［C］.Springer，Heidelberg，2006.

［4］ WOLF F，MOHR B，DONGARRA J，et al.Efficient pattern search in large traces through successive refinement［A］.Proc.of the European Conference on Parallel Computing［C］.2004.

［5］ HEATH M，F(xiàn)INGER J.ParaGraph：A Performance Visualization Tool for MPI［D］.University of Illinois，University of Tennessee，2003.

［6］ MILLER B P，CALLAGHAN M D，CARGILLE J M.The Paradyn Parallel Performance Measurement Tool［S］.IEEE Computer，1995.

［7］ JULICH SUPERCOMPUTING CENTRE.Scalasca toolset for scalable performance analysis of large－scale parallel applications，http：／／www.scalasca.org／.2012－06－30.

［8］ ADHIANTO L，BANERJEE S，F(xiàn)AGAN M，et al.HPCTOOLKIT：Tools for performance analysis of optimized parallel programs［A］.Concurrency and Computation：Practice And Experence［C］.2010.

［9］ 林貽珀.可視化并行性能調(diào)試環(huán)境的設(shè)計(jì)與實(shí)現(xiàn)［D］.清華大學(xué)，2005.

［10］ 劉華.并行程序性能可視化工具及集成開發(fā)環(huán)境［D］.上海大學(xué)，2003.

［11］ Message Passing Interface Forum，MPI：a message passing interface standard，June 1995.http：／／www.mpi－forum.org.2012－06－30.

［12］ WOLF F，F(xiàn)REITAG F，MOHR B，et al.Large event traces in parallel performance analysis［A］.8th Workshop Parallel Systems and Algorithms（PASA），Lecture Notes in Informatics，2006.