楊昌和，李彥達(dá)，張江，王昉，袁曉如,*

1.北京大學(xué) 信息科學(xué)技術(shù)學(xué)院 機(jī)器感知與智能教育部重點(diǎn)實(shí)驗(yàn)室，北京 100871

2.北京大學(xué) 大數(shù)據(jù)分析與應(yīng)用技術(shù)國(guó)家工程實(shí)驗(yàn)室，北京 100871

3. 北京大學(xué)，北京 100871

4. 中國(guó)空氣動(dòng)力研究與發(fā)展中心 計(jì)算空氣動(dòng)力研究所，綿陽(yáng) 621000

隨著科學(xué)、工程、生物醫(yī)學(xué)等領(lǐng)域的不斷發(fā)展，研究者們往往需要面對(duì)大量基于模擬和觀測(cè)的科學(xué)數(shù)據(jù)，尤其在空氣動(dòng)力學(xué)領(lǐng)域，需要從中發(fā)現(xiàn)有意義的規(guī)律?？茖W(xué)數(shù)據(jù)包括標(biāo)量場(chǎng)數(shù)據(jù)和矢量場(chǎng)數(shù)據(jù)，通常具有時(shí)變、多變量等特性，且體量龐大，特征復(fù)雜多變，因而用戶(hù)直接對(duì)于數(shù)據(jù)本身進(jìn)行演算和觀測(cè)十分困難，需要十分龐大的理解代價(jià)。在此背景下，科學(xué)可視化方法應(yīng)運(yùn)而生?？茖W(xué)可視化是可視化研究領(lǐng)域中十分重要的組成部分，該技術(shù)賦予了科學(xué)數(shù)據(jù)具體又可操作的直觀形態(tài)，幫助科學(xué)家們?cè)趫D形世界中直接對(duì)信息進(jìn)行操作和處理，賦予科學(xué)家們一種仿真的實(shí)時(shí)交互能力?？茖W(xué)家們通過(guò)對(duì)數(shù)據(jù)進(jìn)行有效的可視化并分析出其中存在的特征，從而解釋現(xiàn)象或者驗(yàn)證假設(shè)。

流場(chǎng)可視化是科學(xué)可視化中的重要組成部分，能夠有效地幫助人們理解現(xiàn)實(shí)世界流場(chǎng)數(shù)據(jù)的復(fù)雜現(xiàn)象和動(dòng)態(tài)演變的復(fù)雜現(xiàn)象和動(dòng)態(tài)演變，是近年來(lái)科學(xué)研究中的重點(diǎn)問(wèn)題，被廣泛應(yīng)用于燃燒、氣候、航空等科學(xué)模擬和分析。國(guó)家數(shù)值風(fēng)洞(NNW)工程[1]針對(duì)該方面進(jìn)行了深入的研究。流場(chǎng)數(shù)據(jù)可視化方法可以分為4類(lèi)，即直接可視化方法、基于紋理的可視化方法[2]、基于幾何的可視化方法[3]以及特征提取方法[4]。其中，直接可視化和基于紋理的可視化方法分別通過(guò)使用箭頭等符號(hào)形式和條紋狀紋理來(lái)表示流場(chǎng)，基于幾何的可視化方法使用點(diǎn)線面等幾何形式對(duì)流場(chǎng)進(jìn)行可視化，特征提取方法則通過(guò)提取流場(chǎng)中的重要特征對(duì)流場(chǎng)進(jìn)行探索。在這些方法中，通過(guò)粒子追蹤生成場(chǎng)線又是一種最基本的技術(shù)，其在各種各樣的流場(chǎng)可視化和分析任務(wù)，特別是基于幾何和特征提取的可視化方法中，得到了廣泛的應(yīng)用。

隨著科學(xué)家通過(guò)計(jì)算流體學(xué)(CFD)等數(shù)值模擬方法得到的流場(chǎng)數(shù)據(jù)愈加復(fù)雜多變，傳統(tǒng)的流場(chǎng)可視化方法遇到了越來(lái)越多的挑戰(zhàn)，先進(jìn)的流場(chǎng)可視化系統(tǒng)的提出成為了十分迫切的需求?？v觀流場(chǎng)可視化框架的發(fā)展方向，該工作總結(jié)出如下兩個(gè)趨勢(shì)。一方面，科學(xué)家通過(guò)數(shù)值模擬等方式得到的流場(chǎng)數(shù)據(jù)規(guī)模越來(lái)越大，其內(nèi)部結(jié)構(gòu)也越來(lái)越復(fù)雜，甚至以幾何級(jí)數(shù)的速度增長(zhǎng)，這給流場(chǎng)可視化的計(jì)算性能提出了新的考驗(yàn)?，F(xiàn)實(shí)應(yīng)用中單臺(tái)處理機(jī)由于內(nèi)存和計(jì)算能力等的限制，很難滿(mǎn)足這種大規(guī)模粒子追蹤的計(jì)算需求。而早前研究者所使用的核外(Out-of-core)技術(shù)[5-6]，也因其I/O瓶頸在大規(guī)模流場(chǎng)數(shù)據(jù)中變得越來(lái)越不適用。研究者們考慮粒子追蹤生成場(chǎng)線中任務(wù)的高度可并行性，采用并行計(jì)算模式提升性能，成為了一種十分行之有效的解決方案，基于并行粒子追蹤的大規(guī)模場(chǎng)線可視化逐漸成為流場(chǎng)可視化的主流趨勢(shì)。尤其是近年來(lái)隨著高性能計(jì)算技術(shù)的發(fā)展，研究者可以更多地利用超級(jí)計(jì)算機(jī)或者并行計(jì)算集群等強(qiáng)大的計(jì)算資源來(lái)進(jìn)行并行計(jì)算，有效地提升了計(jì)算結(jié)果產(chǎn)出的效率。另一方面，流場(chǎng)本身相關(guān)的分析任務(wù)也呈現(xiàn)出越來(lái)越復(fù)雜的趨勢(shì)，這給流場(chǎng)可視化技術(shù)提出了新的設(shè)計(jì)要求。例如在一些諸如線積分卷積[7-8]、基于有限時(shí)間李雅普諾夫指數(shù)計(jì)算的拉格朗日擬序結(jié)構(gòu)提取[9-10]以及流場(chǎng)曲面計(jì)算[11]、源匯查詢(xún)[12]等基于場(chǎng)線的應(yīng)用中，需要進(jìn)行復(fù)雜的粒子追蹤計(jì)算，也引發(fā)了更加復(fù)雜多變的數(shù)據(jù)分析任務(wù)。

然而，當(dāng)下的流場(chǎng)可視化系統(tǒng)框架下仍然存在一些問(wèn)題。首先，基于并行粒子追蹤性能優(yōu)化的大規(guī)模流場(chǎng)可視化引發(fā)了新的困難和問(wèn)題討論。具體地說(shuō)，即傳統(tǒng)并行計(jì)算框架下的任務(wù)優(yōu)化和數(shù)據(jù)管理策略如何較好地遷移至流場(chǎng)可視化應(yīng)用中。例如，在并行計(jì)算的過(guò)程中，負(fù)載均衡問(wèn)題顯得尤為重要，需要設(shè)計(jì)精細(xì)的任務(wù)分配和調(diào)度策略，每個(gè)計(jì)算節(jié)點(diǎn)都始終被分配有較為均衡的任務(wù)量，才能最大化地利用計(jì)算資源，達(dá)到效率的最優(yōu)化。但是，粒子追蹤的并行化本身存在著粒子的運(yùn)行時(shí)間和軌跡難以預(yù)測(cè)的復(fù)雜問(wèn)題，對(duì)粒子的初始劃分很難保證進(jìn)程的負(fù)載均衡，需要合理而精細(xì)的預(yù)估模型。其次，現(xiàn)有的流場(chǎng)可視化系統(tǒng)下，粒子追蹤過(guò)程對(duì)于用戶(hù)難以理解和干預(yù)，因而對(duì)于已有算法難以進(jìn)行評(píng)估、校驗(yàn)和診斷優(yōu)化，這也對(duì)新方法的試驗(yàn)、應(yīng)用帶來(lái)了一定困難。用戶(hù)對(duì)于粒子追蹤的過(guò)程難以顯示地獲得理解，難以獲取過(guò)程中數(shù)據(jù)塊、任務(wù)調(diào)度和進(jìn)程負(fù)載變化等核心信息，這使得占據(jù)整個(gè)流場(chǎng)可視化應(yīng)用中巨大時(shí)間、存儲(chǔ)消耗的過(guò)程難以進(jìn)行合理地優(yōu)化。流場(chǎng)可視化系統(tǒng)同樣需要對(duì)這一過(guò)程采用系統(tǒng)化的可視化技術(shù)動(dòng)態(tài)展現(xiàn)，提升系統(tǒng)運(yùn)行效率，以增加流場(chǎng)可視化系統(tǒng)的可用性。

針對(duì)這些問(wèn)題，結(jié)合在流場(chǎng)可視化領(lǐng)域的研究、應(yīng)用和實(shí)踐，本文研究團(tuán)隊(duì)主導(dǎo)設(shè)計(jì)并開(kāi)發(fā)了高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)，幫助領(lǐng)域用戶(hù)使用最新發(fā)展的可視化方法和技術(shù)理解、分析和探索流場(chǎng)數(shù)據(jù)，同時(shí)促進(jìn)可視化和領(lǐng)域研究的發(fā)展。和現(xiàn)有的可視化系統(tǒng)相比，本文研究的系統(tǒng)關(guān)注于采用先進(jìn)科學(xué)的并行數(shù)據(jù)管理方法提升流場(chǎng)可視化應(yīng)用中粒子追蹤的效率，同時(shí)支持先進(jìn)的流場(chǎng)數(shù)據(jù)可視化算法的診斷和分析,能夠有效地應(yīng)用于不同的流場(chǎng)數(shù)據(jù)，并廣泛地支持流場(chǎng)中的分析任務(wù)。

1 相關(guān)工作概述

在科學(xué)可視化針對(duì)大規(guī)模流場(chǎng)的可視化任務(wù)中，基于粒子追蹤的流場(chǎng)可視化需要從原始數(shù)據(jù)出發(fā)生成場(chǎng)線。流場(chǎng)可視化粒子追蹤的計(jì)算過(guò)程十分復(fù)雜，涉及大量的數(shù)據(jù)讀取訪問(wèn)、密集型積分計(jì)算。而通過(guò)采用并行計(jì)算的模式，將工作負(fù)載分布到成百上千上萬(wàn)甚至更多的計(jì)算節(jié)點(diǎn)單元，由這些節(jié)點(diǎn)單元協(xié)作計(jì)算大規(guī)模粒子的軌跡，粒子追蹤的效率會(huì)大大提高。這也使得并行粒子追蹤成為了目前基于場(chǎng)線的大規(guī)模流場(chǎng)可視化的主流趨勢(shì)。其主要工作流程包括基于分析任務(wù)需要生成初始粒子的分布和基于初始粒子分布進(jìn)行積分跡線生成。初始粒子的數(shù)目由流場(chǎng)規(guī)模、局部特征和性能的平衡綜合決定。針對(duì)大規(guī)模流場(chǎng)數(shù)據(jù)可視化的并行粒子追蹤方法主要分為兩類(lèi)，即任務(wù)并行和數(shù)據(jù)并行。最近也有一些將兩者進(jìn)行結(jié)合的并行方法，即混合并行方法。不同類(lèi)別的并行計(jì)算方式如下:

1) 任務(wù)并行：初始粒子種子被靜態(tài)劃分為若干組并被分配給不同的進(jìn)程，每個(gè)進(jìn)程負(fù)責(zé)其所分配到的粒子的追蹤計(jì)算。

2) 數(shù)據(jù)并行：流場(chǎng)數(shù)據(jù)被靜態(tài)劃分為若干數(shù)據(jù)塊并分配給不同的進(jìn)程，每個(gè)進(jìn)程負(fù)責(zé)在其所分配到的數(shù)據(jù)塊內(nèi)進(jìn)行粒子追蹤計(jì)算。

基于不同類(lèi)別的并行計(jì)算策略，多種先進(jìn)的數(shù)據(jù)管理策略被應(yīng)用以提升計(jì)算效率，包括數(shù)據(jù)預(yù)取策略、負(fù)載均衡化策略和數(shù)據(jù)約減策略等。已有工作中主要關(guān)注于如何使用有效的數(shù)據(jù)劃分、分配和移動(dòng)等數(shù)據(jù)管理策略，盡量使進(jìn)程負(fù)載均衡并減小通信和I/O等方面的開(kāi)銷(xiāo)，優(yōu)化數(shù)據(jù)訪問(wèn)性能，以下部分將簡(jiǎn)述已有工作中針對(duì)不同并行計(jì)算策略采取的數(shù)據(jù)管理優(yōu)化策略。

1.1 任務(wù)并行的粒子追蹤算法中的數(shù)據(jù)管理策略

任務(wù)并行的粒子追蹤算法將每個(gè)粒子的追蹤計(jì)算看成是一個(gè)任務(wù)，其在初始時(shí)將所有種子靜態(tài)地分配給所有的進(jìn)程，同時(shí)在粒子追蹤過(guò)程中由進(jìn)程按需載入數(shù)據(jù)。為了保證負(fù)載均衡性，任務(wù)并行算法需要在初始時(shí)給每個(gè)進(jìn)程預(yù)估并分配較為均衡的負(fù)載，或者在多輪運(yùn)行的過(guò)程中實(shí)現(xiàn)動(dòng)態(tài)任務(wù)重分配。在已有方法中，動(dòng)態(tài)任務(wù)重分配主要通過(guò)工作竊取(Work Stealing)、工作請(qǐng)求(Work Requesting)或者k-d樹(shù)分解來(lái)完成。工作竊取是一種常見(jiàn)的動(dòng)態(tài)平衡負(fù)載方法，其原理是當(dāng)某一個(gè)工作進(jìn)程(稱(chēng)為竊取進(jìn)程)完成所負(fù)責(zé)的任務(wù)時(shí)，會(huì)從其他繁忙進(jìn)程(稱(chēng)為被竊取進(jìn)程)處“偷取”一部分任務(wù)給自己執(zhí)行。竊取目標(biāo)的選擇可以基于隨機(jī)選擇[13]，然后從被竊取進(jìn)程的任務(wù)隊(duì)列末端開(kāi)始轉(zhuǎn)移任務(wù)，該方法被證明具有良好的效率[14]。Pugmire等[15]提出一種基于主-輔(Master-slave)模式的混合調(diào)度方法，也是基于這個(gè)思想。Lu等[16]針對(duì)流面計(jì)算也使用了工作竊取來(lái)平衡動(dòng)態(tài)過(guò)程中的任務(wù)負(fù)載。Müller等[17]提出了一種類(lèi)似工作竊取的方法，稱(chēng)作工作請(qǐng)求，該方法會(huì)帶來(lái)更多的通信，但是更易于實(shí)現(xiàn)，更適合于分布式內(nèi)存系統(tǒng)?；趉-d樹(shù)分解的負(fù)載均衡思想被成功地運(yùn)用到了針對(duì)Delaunay曲面細(xì)分(Delaunay Tessellation)的負(fù)載平衡中[18]。Zhang等提出了一種新穎的基于帶有約束的k-d樹(shù)分解的方法[19]，可以在可用內(nèi)存限制下盡量對(duì)未完成粒子進(jìn)行重分配。

任務(wù)并行的粒子追蹤算法中通常采用按需載入的數(shù)據(jù)訪問(wèn)策略，I/O問(wèn)題是制約并行粒子追蹤計(jì)算性能的一個(gè)非常重要的瓶頸。數(shù)據(jù)預(yù)取的思想是在載入所需要的數(shù)據(jù)時(shí)，將之后粒子追蹤可能訪問(wèn)到的數(shù)據(jù)也一并提前載入，這樣可以降低I/O操作次數(shù)，減少進(jìn)程因?yàn)閿?shù)據(jù)不在內(nèi)存中而必須等待的時(shí)間。早在2005年，Rhodes等[20]就將訪問(wèn)模式作為先驗(yàn)知識(shí)，使用緩存和預(yù)取機(jī)制來(lái)動(dòng)態(tài)提高I/O性能。近年來(lái)，俄亥俄州立大學(xué)的可視化小組針對(duì)流場(chǎng)可視化中流線和跡線等的計(jì)算，提出了一系列基于數(shù)據(jù)訪問(wèn)依賴(lài)的數(shù)據(jù)預(yù)取方法[21-22]。在預(yù)處理階段，他們將數(shù)據(jù)劃分為小塊形式，然后根據(jù)粒子追蹤的數(shù)據(jù)訪問(wèn)關(guān)系生成數(shù)據(jù)塊之間的訪問(wèn)依賴(lài)圖。需要注意的是，數(shù)據(jù)預(yù)取應(yīng)該適度進(jìn)行，過(guò)度的預(yù)取不僅會(huì)降低預(yù)測(cè)的準(zhǔn)確性，還會(huì)飽和系統(tǒng)的帶寬[23]，造成適得其反的效果。

1.2 數(shù)據(jù)并行的粒子追蹤算法中的數(shù)據(jù)管理策略

數(shù)據(jù)并行的粒子追蹤算法在初始時(shí)將整個(gè)數(shù)據(jù)劃分為若干數(shù)據(jù)塊，并將這些數(shù)據(jù)塊分配給各個(gè)進(jìn)程。在粒子追蹤的過(guò)程中，當(dāng)粒子離開(kāi)對(duì)應(yīng)進(jìn)程負(fù)責(zé)的數(shù)據(jù)塊時(shí)，會(huì)被發(fā)送給目標(biāo)數(shù)據(jù)塊對(duì)應(yīng)的進(jìn)程繼續(xù)追蹤計(jì)算。一般情況下，該方法假設(shè)數(shù)據(jù)可以被所有進(jìn)程一次性載入到內(nèi)存中，所以具有較小的I/O開(kāi)銷(xiāo)。但由于需要頻繁地在進(jìn)程之間交換粒子，密集的通信帶來(lái)的耗費(fèi)對(duì)性能也具有較大的影響。相關(guān)的數(shù)據(jù)管理策略主要包括兩類(lèi)：靜態(tài)負(fù)載平衡方法(例如根據(jù)某些劃分規(guī)則的數(shù)據(jù)靜態(tài)分配策略)以及動(dòng)態(tài)負(fù)載平衡方法。

一種最直接的靜態(tài)數(shù)據(jù)劃分方法為規(guī)則數(shù)據(jù)劃分，其中最直接的劃分方法是靜態(tài)輪轉(zhuǎn)(Round-robin)法[24]。對(duì)于n個(gè)進(jìn)程和m個(gè)數(shù)據(jù)塊，該方法中第i個(gè)進(jìn)程被分配到編號(hào)為i,i+m/n,i+2m/n,…的這些數(shù)據(jù)塊。輪轉(zhuǎn)法可以確保每個(gè)進(jìn)程被分到空間位置不連續(xù)的相等數(shù)量的數(shù)據(jù)塊。該方法的一個(gè)典型應(yīng)用是在Nouanesengsy等[25]提出的基于有限時(shí)間李雅普諾夫指數(shù)(Finite-Time Lyapunov Exponents，F(xiàn)TLE)計(jì)算方法中。為了更進(jìn)一步地解決負(fù)載不平衡的瓶頸， Nouanesengsy等[26]提出了一種負(fù)載感知的方法，即靜態(tài)評(píng)估每個(gè)數(shù)據(jù)塊的負(fù)載，并據(jù)此對(duì)數(shù)據(jù)塊進(jìn)行分配。該方法允許同一數(shù)據(jù)塊被重復(fù)分配給多個(gè)進(jìn)程，每個(gè)進(jìn)程只負(fù)責(zé)重復(fù)數(shù)據(jù)塊中一部分的粒子追蹤工作量，但總的負(fù)載比較均等。另一類(lèi)數(shù)據(jù)劃分方法即不規(guī)則的數(shù)據(jù)劃分。Chen和Fujishiro[27]提出了一種根據(jù)流場(chǎng)方向的數(shù)據(jù)劃分方法，考慮了種子的分布和諸如漩渦等流場(chǎng)的局部特征。另一種不規(guī)則的劃分是利用層次聚類(lèi)進(jìn)行自適應(yīng)網(wǎng)格區(qū)域劃分[28]。數(shù)據(jù)首先被分解成單位網(wǎng)格，即最小的簇，然后具有類(lèi)似模式的相鄰網(wǎng)格會(huì)被兩兩合并，自下而上迭代地形成二叉樹(shù)的層次結(jié)構(gòu)。

在動(dòng)態(tài)負(fù)載平衡優(yōu)化算法中，Peterka等[24]提出了一種基于遞歸坐標(biāo)二分(Recursive Coordinate Bisection, RCB)[29]動(dòng)態(tài)數(shù)據(jù)重劃分方法。在他們的方法中，每個(gè)數(shù)據(jù)塊中追蹤的積分步數(shù)被記錄為其歷史負(fù)載，這種歷史負(fù)載信息被用做數(shù)據(jù)重劃分的依據(jù)。該方法的理論假設(shè)是，相鄰時(shí)間步相同空間位置上每個(gè)數(shù)據(jù)塊的負(fù)載可以認(rèn)為是相似的。因此在數(shù)據(jù)重劃分后，進(jìn)程可以被重新分配到負(fù)載近似相等的數(shù)據(jù)塊，然后在下一階段進(jìn)行計(jì)算。這里數(shù)據(jù)重劃分通過(guò)RCB算法[29]實(shí)現(xiàn)。除了RCB，類(lèi)似的算法包括遞歸慣性二分(Recursive Inertial Bisection, RIB)[30]以及基于圖拓?fù)涞膭澐諿31-32]。

2 系統(tǒng)特性和功能設(shè)計(jì)支持

高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)具有以下特性：

1) 對(duì)于數(shù)據(jù)的支持

系統(tǒng)支持定義在線性網(wǎng)格上的二維、三維定常和時(shí)變的矢量場(chǎng)數(shù)據(jù)形式，并支持多種不同的常見(jiàn)數(shù)據(jù)格式，例如NetCDF、HDF5以及系統(tǒng)定義的XML數(shù)據(jù)描述等。系統(tǒng)提供不同體量的撒種規(guī)模，支持遠(yuǎn)超內(nèi)存量的流場(chǎng)數(shù)據(jù)。系統(tǒng)支持多種典型的流場(chǎng)數(shù)據(jù)分析，包括Geos5全球風(fēng)場(chǎng)數(shù)據(jù)、Isabel颶風(fēng)數(shù)據(jù)、Nek5000熱力水工數(shù)據(jù)等。

2) 對(duì)于常用分析任務(wù)的支持

系統(tǒng)支持流場(chǎng)數(shù)據(jù)的通用分析任務(wù)，包括流場(chǎng)中源匯查詢(xún)、線積分卷積、基于有限時(shí)間李雅普諾夫指數(shù)計(jì)算的拉格朗日擬序結(jié)構(gòu)提取、流場(chǎng)曲面計(jì)算等典型分析任務(wù)，為流場(chǎng)數(shù)據(jù)分析提供有力的支持。

3) 對(duì)于高性能的支持

系統(tǒng)支持高性能的流場(chǎng)可視化應(yīng)用，支持針對(duì)大規(guī)模數(shù)據(jù)和任務(wù)，能夠在不同的計(jì)算平臺(tái)上針對(duì)并行粒子追蹤算法進(jìn)行并行計(jì)算效率加速。

4) 對(duì)于高可擴(kuò)展性的支持

該系統(tǒng)在小型并行集群及超算平臺(tái)上均具有良好的適應(yīng)性，能夠支持高度可擴(kuò)展的并行加速，最高對(duì)于1 K核規(guī)模的并行集群仍然表現(xiàn)出良好的可擴(kuò)展性。

5) 對(duì)于可視分析進(jìn)行性能診斷方法的支持

系統(tǒng)支持對(duì)于先進(jìn)的粒子追蹤算法性能數(shù)據(jù)的可視分析技術(shù)，能夠針對(duì)算法在運(yùn)行過(guò)程中的數(shù)據(jù)、任務(wù)交換的行為模式進(jìn)行比較和分析，幫助用戶(hù)深入理解該復(fù)雜的計(jì)算過(guò)程。同時(shí)支持定位并行粒子追蹤算法在計(jì)算過(guò)程中的性能桎梏，尤其針對(duì)負(fù)載不平衡的原因的探究，實(shí)現(xiàn)對(duì)于算法性能的診斷，以幫助專(zhuān)家學(xué)者進(jìn)一步優(yōu)化和改良已有的算法。

3 系統(tǒng)軟件架構(gòu)與實(shí)現(xiàn)

3.1 系統(tǒng)概覽

高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)的整體工作流水線如圖1所示。該系統(tǒng)支持的計(jì)算和操作流程依據(jù)其部署的不同操作平臺(tái)和計(jì)算任務(wù)目標(biāo)可拆分為在超算平臺(tái)與本地平臺(tái)運(yùn)行的兩個(gè)相互分離的階段，共同支持大規(guī)模流場(chǎng)數(shù)據(jù)可視化的構(gòu)建和優(yōu)化分析。

圖1 高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)工作流水線 Fig.1 Workflow of high-performance flow parallel particle tracing data management system

部署在超算平臺(tái)上的高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)主要支持高性能流場(chǎng)并行粒子追蹤算法的實(shí)現(xiàn)和基于大規(guī)?？茖W(xué)數(shù)據(jù)管理的優(yōu)化策略。該過(guò)程中，系統(tǒng)根據(jù)用戶(hù)設(shè)定的分析任務(wù)目標(biāo)和撒種初始化，使用一些諸如四階龍格-庫(kù)塔(Fourth-order Runge-Kutta, RK4)等數(shù)值積分算法計(jì)算追蹤這些粒子在流場(chǎng)中的運(yùn)行軌跡。為了進(jìn)一步提升計(jì)算效率，系統(tǒng)關(guān)注于粒子積分算法中固有的天然可并行性，采用多進(jìn)程并行優(yōu)化計(jì)算的方式提升計(jì)算的效率，以適應(yīng)粒子追蹤本身的計(jì)算復(fù)雜性帶來(lái)的挑戰(zhàn)。引入并行計(jì)算機(jī)制在潛在提升計(jì)算效率的同時(shí)，使得算法具有更加復(fù)雜的流程，也使得負(fù)載均衡問(wèn)題成為效率提升的關(guān)鍵所在。由于并行粒子追蹤問(wèn)題中，粒子的軌跡和粒子的運(yùn)行時(shí)間難以預(yù)測(cè)，如何預(yù)估不同計(jì)算進(jìn)程的負(fù)載情況，合理設(shè)計(jì)和實(shí)現(xiàn)負(fù)載均衡算法成為了十分重要的問(wèn)題。而隨著大規(guī)模流場(chǎng)數(shù)據(jù)對(duì)粒子追蹤過(guò)程提出的更高要求，由于實(shí)際應(yīng)用中有限的計(jì)算資源，并行粒子追蹤過(guò)程中內(nèi)存和I/O帶寬的限制被進(jìn)一步放大。如何有效地利用有限的計(jì)算資源并設(shè)計(jì)出合理的數(shù)據(jù)管理策略來(lái)改善內(nèi)存和I/O帶寬等資源的使用成為了另一個(gè)亟待解決的問(wèn)題，這同樣有助于提升計(jì)算的整體效率。

面對(duì)上述挑戰(zhàn)和問(wèn)題，高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)在優(yōu)化策略上通過(guò)設(shè)計(jì)高效的數(shù)據(jù)管理策略，結(jié)合大規(guī)模流場(chǎng)可視化的特點(diǎn)，充分利用計(jì)算資源，從數(shù)據(jù)存儲(chǔ)組織方式、數(shù)據(jù)訪問(wèn)以及在并行粒子追蹤過(guò)程中對(duì)數(shù)據(jù)的劃分和調(diào)度管理等方面進(jìn)行考慮。在優(yōu)化目標(biāo)方面，高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)關(guān)注于并行粒子追蹤流程中的兩大性能桎梏，即負(fù)載均衡問(wèn)題和大規(guī)模I/O問(wèn)題。負(fù)載均衡問(wèn)題和大規(guī)模I/O問(wèn)題兩者相互聯(lián)系，相互制約。該系統(tǒng)通過(guò)先進(jìn)的評(píng)估和劃分算法，同時(shí)權(quán)衡優(yōu)化兩大目標(biāo)，以達(dá)到實(shí)際性能的最大化。

支持本地平臺(tái)運(yùn)行的高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)能對(duì)并行粒子追蹤過(guò)程產(chǎn)生跡線數(shù)據(jù)，系統(tǒng)支持靈活多變的本地端多種跡線可視化與可視分析方法，用于幫助用戶(hù)理解與探索原始流場(chǎng)的特性。進(jìn)一步地，高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)能對(duì)并行粒子追蹤過(guò)程中產(chǎn)生的進(jìn)程工作記錄數(shù)據(jù)，系統(tǒng)支持用戶(hù)對(duì)該過(guò)程中進(jìn)程的負(fù)載與進(jìn)程間數(shù)據(jù)塊轉(zhuǎn)移情況進(jìn)行可視分析，在有效增強(qiáng)過(guò)程理解的同時(shí)，用戶(hù)據(jù)此可對(duì)并行計(jì)算過(guò)程做出診斷。

3.2 流場(chǎng)并行粒子追蹤數(shù)據(jù)管理模塊構(gòu)建

3.2.1 基于鍵值對(duì)存儲(chǔ)的并行粒子追蹤框架實(shí)現(xiàn)

在大規(guī)模流場(chǎng)可視化并行粒子追蹤計(jì)算過(guò)程中，數(shù)據(jù)訪問(wèn)的效率是提升計(jì)算性能、可擴(kuò)展性和存儲(chǔ)空間效率的已知最大瓶頸。因而高效的數(shù)據(jù)存儲(chǔ)管理、計(jì)算框架、底層架構(gòu)實(shí)現(xiàn)成為十分重要的部分，是高效、高可擴(kuò)展性計(jì)算性能的有力保證。究其原因，是因?yàn)榇笠?guī)模科學(xué)可視化構(gòu)建所需要的可用計(jì)算資源十分有限，遠(yuǎn)遠(yuǎn)小于原始模擬的計(jì)算和數(shù)據(jù)規(guī)模，需要在有限地條件下平衡諸方面的因素，實(shí)現(xiàn)性能的提升。

高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)基于一種鍵值對(duì)(Key-value)存儲(chǔ)的并行粒子追蹤框架底層實(shí)現(xiàn)[33]，旨在提升數(shù)據(jù)訪問(wèn)的效率。在流場(chǎng)可視化并行粒子追蹤過(guò)程中，盡管流場(chǎng)可視化整體數(shù)據(jù)集十分龐大，但單次使用的工作集卻非常小，因此從粗粒度分區(qū)到細(xì)粒度劃分和調(diào)用是可行的。由于粒子追蹤過(guò)程中粒子的軌跡難以預(yù)測(cè)性，基于按需載入的存儲(chǔ)操作基本方法能夠最有效地適應(yīng)數(shù)據(jù)訪問(wèn)的實(shí)現(xiàn)模式。同時(shí)先進(jìn)的粒子追蹤方式越來(lái)越多地采用本地任務(wù)隊(duì)列來(lái)管理局部粒子追蹤任務(wù)的啟動(dòng)、停止和通信狀態(tài)?；谙冗M(jìn)的并行粒子追蹤技術(shù)現(xiàn)狀，該工作發(fā)現(xiàn)基于鍵值對(duì)存儲(chǔ)的稀疏數(shù)據(jù)管理可以大大減少并行粒子追蹤運(yùn)行的內(nèi)存占用，很好地適應(yīng)按需數(shù)據(jù)訪問(wèn)需求，并且可以在不妨礙性能和擴(kuò)展性的前提下進(jìn)行高效管理。

在該方法的實(shí)現(xiàn)中，運(yùn)行時(shí)的數(shù)據(jù)以初始劃分的多個(gè)數(shù)據(jù)小塊為基本的管理粒度，包含單個(gè)單元或更細(xì)粒度的單元塊。該方法同時(shí)包含兩個(gè)模塊的組件：① 一個(gè)并行的鍵值對(duì)存儲(chǔ)模塊，支持統(tǒng)籌集中地進(jìn)行數(shù)據(jù)塊的I/O操作，以最大限度地將I/O延遲隱藏在并行粒子追蹤積分計(jì)算的過(guò)程背后；② 一組完全獨(dú)立的任務(wù)并行的追蹤器。每個(gè)并行粒子追蹤計(jì)算任務(wù)都被分配到一個(gè)追蹤器，而每個(gè)追蹤器擁有并管理著大量的追蹤任務(wù)，通過(guò)任務(wù)隊(duì)列的管理方式執(zhí)行和管理待處理的任務(wù)集。追蹤器通過(guò)訪問(wèn)和查詢(xún)并行鍵值對(duì)存儲(chǔ)的方式來(lái)請(qǐng)求計(jì)算過(guò)程中的數(shù)據(jù)，并將收到的數(shù)據(jù)塊保存在本地基于最近最少使用(Least Recently Used, LRU)策略的緩存中，該緩存機(jī)制采用一個(gè)簡(jiǎn)單的隨機(jī)存取存儲(chǔ)器(Random Access Memory, RAM)鍵值存儲(chǔ)實(shí)現(xiàn)。為了實(shí)現(xiàn)上述并行化模塊組件，任務(wù)管理中包含兩種不同的進(jìn)程，即鍵值對(duì)存儲(chǔ)進(jìn)程和粒子追蹤進(jìn)程，分別處理不同的任務(wù)，數(shù)據(jù)主要從鍵值對(duì)存儲(chǔ)流向粒子追蹤進(jìn)程。鍵值對(duì)存儲(chǔ)進(jìn)程負(fù)責(zé)數(shù)據(jù)請(qǐng)求的通信接收和載入處理，粒子追蹤進(jìn)程的任務(wù)則不涉及數(shù)據(jù)的訪問(wèn)，僅進(jìn)行數(shù)值計(jì)算的過(guò)程。

在當(dāng)前的實(shí)現(xiàn)中，由粒子追蹤進(jìn)程進(jìn)行數(shù)據(jù)訪問(wèn)的過(guò)程與具有多層高速緩存的CPU上的數(shù)據(jù)訪問(wèn)非常相似。粒子追蹤進(jìn)程首先檢查所需的數(shù)據(jù)是否緩存在本地，若本地緩存未命中，則粒子追蹤進(jìn)程向?qū)?yīng)的并行鍵值對(duì)存儲(chǔ)請(qǐng)求，若并行鍵值對(duì)存儲(chǔ)仍然沒(méi)有所需要的數(shù)據(jù)，則將花費(fèi)更長(zhǎng)的時(shí)間從文件系統(tǒng)中載入所需的數(shù)據(jù)并返回。并行鍵值對(duì)存儲(chǔ)系統(tǒng)可以依據(jù)一定的數(shù)據(jù)預(yù)取策略，利用已有的信息積極地進(jìn)行數(shù)據(jù)預(yù)取以避免緩存丟失，同時(shí)實(shí)現(xiàn)流控制以避免I/O系統(tǒng)的擁塞?；谌?jí)緩存機(jī)制實(shí)現(xiàn)的數(shù)據(jù)訪問(wèn)過(guò)程和所需時(shí)間如圖2所示。

圖2 流場(chǎng)并行粒子追蹤數(shù)據(jù)管理模塊軟件邏輯架構(gòu)Fig.2 Software logic architecture of flow field parallel particle tracing data management module

每個(gè)鍵值對(duì)存儲(chǔ)進(jìn)程負(fù)責(zé)一系列粒子追蹤計(jì)算進(jìn)程的數(shù)據(jù)訪問(wèn)請(qǐng)求。為了實(shí)現(xiàn)負(fù)載平衡，需要合理設(shè)計(jì)進(jìn)程間任務(wù)負(fù)責(zé)的映射方法。該實(shí)現(xiàn)中通過(guò)散列的方法來(lái)劃分整體的索引空間，并通過(guò)輪轉(zhuǎn)法[24]來(lái)進(jìn)行負(fù)責(zé)進(jìn)程的分配。一個(gè)密鑰k根據(jù)公式i=hash(k)modn，被分配給一個(gè)鍵值對(duì)存儲(chǔ)進(jìn)程，其中n為鍵值對(duì)存儲(chǔ)進(jìn)程數(shù)。粒子追蹤進(jìn)程發(fā)出的數(shù)據(jù)請(qǐng)求通過(guò)點(diǎn)對(duì)點(diǎn)通信，直接發(fā)送到相應(yīng)的鍵值對(duì)進(jìn)程實(shí)現(xiàn)交流。

該系統(tǒng)開(kāi)發(fā)基于C++語(yǔ)言，混合了MPI/線程并行。所有的數(shù)據(jù)通信都是通過(guò)消息傳遞，同時(shí)粒子追蹤進(jìn)程和鍵值對(duì)存儲(chǔ)進(jìn)程被劃分在同一個(gè)MPI通信組中。在該方法實(shí)現(xiàn)的框架中，有3種類(lèi)型的進(jìn)程間通信，即粒子追蹤和鍵值對(duì)存儲(chǔ)進(jìn)程間通信,鍵值對(duì)存儲(chǔ)和粒子追蹤進(jìn)程之間通信，鍵值對(duì)存儲(chǔ)進(jìn)程之間的通信，粒子追蹤進(jìn)程之間不支持建立通信。一般情況下，粒子追蹤進(jìn)程向相應(yīng)的鍵值對(duì)存儲(chǔ)進(jìn)程發(fā)送請(qǐng)求，然后將數(shù)據(jù)條目發(fā)回給粒子追蹤進(jìn)程。數(shù)據(jù)預(yù)取是通過(guò)存儲(chǔ)到存儲(chǔ)的通信來(lái)完成的。實(shí)現(xiàn)中預(yù)定義了一系列運(yùn)行時(shí)程序應(yīng)用接口(Application Programming Interface, API)，以及其他消息用于傳遞數(shù)據(jù)條目、處理狀態(tài)和統(tǒng)計(jì)。所有的消息都會(huì)被入隊(duì)，使用谷歌protobuf庫(kù)序列化后發(fā)送至目的地進(jìn)程。目的地進(jìn)程在接收到消息后，將消息反序列化后進(jìn)行后續(xù)處理。該系統(tǒng)利用異步通信來(lái)降低延遲。

3.2.2 基于訪問(wèn)依賴(lài)的大規(guī)模數(shù)據(jù)訪問(wèn)模式建模

流場(chǎng)可視化并行粒子追蹤技術(shù)中數(shù)據(jù)I/O的代價(jià)十分龐大，減輕I/O負(fù)擔(dān)的關(guān)鍵在于提高數(shù)據(jù)計(jì)算和利用中的局部性。其中主要的解決方案是將數(shù)據(jù)訪問(wèn)模式結(jié)合到粒子追蹤中。但是，在流場(chǎng)可視化中，由于數(shù)據(jù)訪問(wèn)模式是由流場(chǎng)特性隱式?jīng)Q定的，對(duì)其進(jìn)行建模十分具有挑戰(zhàn)性。究其原因，粒子的軌跡難以預(yù)測(cè)?；谏鲜龅奶攸c(diǎn)，建立數(shù)據(jù)訪問(wèn)模式模型的一種方法是使用馬爾可夫鏈。在隨機(jī)模型中，訪問(wèn)下一個(gè)數(shù)據(jù)塊的概率只建立在剛被訪問(wèn)過(guò)的那個(gè)數(shù)據(jù)塊上。通過(guò)計(jì)算每對(duì)數(shù)據(jù)塊的狀態(tài)轉(zhuǎn)移概率，一階訪問(wèn)模式可以被記錄下來(lái)。然后在場(chǎng)線追蹤的過(guò)程中，根據(jù)粒子當(dāng)前所在的數(shù)據(jù)塊位置，可以提前評(píng)估下一個(gè)可能訪問(wèn)到的數(shù)據(jù)塊。這種一階的馬爾可夫模型已經(jīng)被有效地應(yīng)用在了計(jì)算流體動(dòng)力學(xué)和流場(chǎng)可視化的應(yīng)用和分析之中[34]，但仍然存在一定缺陷。由于狀態(tài)(數(shù)據(jù)訪問(wèn))從一個(gè)數(shù)據(jù)塊可能會(huì)轉(zhuǎn)移到多種不同的數(shù)據(jù)塊，隨著一階馬爾可夫鏈的增長(zhǎng)，算法難以進(jìn)行準(zhǔn)確的預(yù)測(cè)。

高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)中集成了一種新穎的基于高階馬爾可夫鏈[35]的訪問(wèn)依賴(lài)模型[36]。這種高階的訪問(wèn)依賴(lài)將歷史訪問(wèn)信息也考慮進(jìn)去，計(jì)算下一步的數(shù)據(jù)塊訪問(wèn)是建立在當(dāng)前的數(shù)據(jù)塊和一系列過(guò)去已經(jīng)被訪問(wèn)的數(shù)據(jù)塊之上，可以更加準(zhǔn)確地對(duì)數(shù)據(jù)訪問(wèn)進(jìn)行預(yù)測(cè)性，從而相比于一階訪問(wèn)模式的建模方法[21-34]，進(jìn)一步提高了數(shù)據(jù)局部性以提升流場(chǎng)可視化粒子追蹤場(chǎng)線計(jì)算的效率。

高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)基于不同的用戶(hù)任務(wù)設(shè)計(jì)和實(shí)際需求針對(duì)該數(shù)據(jù)訪問(wèn)依賴(lài)的建模形式設(shè)計(jì)了兩種不同的實(shí)現(xiàn)方式，即一種基于預(yù)處理統(tǒng)計(jì)建模鍵值對(duì)存儲(chǔ)查詢(xún)的實(shí)現(xiàn)方式和基于機(jī)器學(xué)習(xí)進(jìn)行訪問(wèn)序列建模預(yù)測(cè)的實(shí)現(xiàn)方式。

基于預(yù)處理統(tǒng)計(jì)建模鍵值對(duì)存儲(chǔ)查詢(xún)的實(shí)現(xiàn)方式通過(guò)進(jìn)行一次預(yù)處理化得全局撒種并行粒子追蹤過(guò)程，產(chǎn)生高度可重用的數(shù)據(jù)記錄，為后續(xù)并行粒子追蹤應(yīng)用提供有效的輔助建模。整個(gè)數(shù)據(jù)全域被均勻劃分為若干數(shù)據(jù)塊，每個(gè)塊都包含各個(gè)維度上相等大小的范圍，并且使用均勻撒種的方式在不同位置上放置粒子。由于高階訪問(wèn)對(duì)于依賴(lài)歷史訪問(wèn)信息的需求，該方法從起始位置開(kāi)始同時(shí)正向和反向進(jìn)行追蹤計(jì)算。對(duì)應(yīng)生成的跡線分別叫做正向跡線和反向跡線，其區(qū)別在于在跡線追蹤過(guò)程中前者每一步增加時(shí)間，而后者每一步減少時(shí)間。始于同一個(gè)位置的正向和反向跡線可以看成是一條完整的同時(shí)包含歷史和下一步訪問(wèn)信息的跡線。在跡線追蹤過(guò)程中，該方法使用一階龍格-庫(kù)塔(RK1)數(shù)值積分算法，并設(shè)置了較大的積分步長(zhǎng)來(lái)優(yōu)化預(yù)處理性能。為了生成指定m階的訪問(wèn)依賴(lài)數(shù)據(jù)，該方法考慮歷史訪問(wèn)數(shù)據(jù)塊序列長(zhǎng)度為m-1的所有合并跡線。該方法針對(duì)這些歷史訪問(wèn)信息有所不同將跡線進(jìn)行分組。算法進(jìn)一步計(jì)算下一個(gè)訪問(wèn)包含每個(gè)數(shù)據(jù)塊的所有跡線數(shù)量與訪問(wèn)所有可能數(shù)據(jù)塊的跡線總數(shù)的比值，作為訪問(wèn)轉(zhuǎn)移概率。其計(jì)算公式為

(1)

式中：Bp為訪問(wèn)歷史數(shù)據(jù)塊序列；Bc為當(dāng)前訪問(wèn)數(shù)據(jù)塊；Bfi為下一步可能訪問(wèn)的數(shù)據(jù)塊;N為對(duì)應(yīng)跡線支持的數(shù)量。

該算法的偽代碼如算法1所示。通過(guò)該方法，只要一輪預(yù)處理計(jì)算，就可以得到不同階數(shù)訪問(wèn)依賴(lài)結(jié)果。例如，如果階數(shù)設(shè)為m，階數(shù)為m,m-1,…,1的依賴(lài)都會(huì)被計(jì)算出來(lái)。為了高性能的數(shù)據(jù)訪問(wèn)模式和存儲(chǔ)，高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)使用谷歌protobuf庫(kù)所提供的數(shù)據(jù)結(jié)構(gòu)。圖3為高階訪問(wèn)依賴(lài)計(jì)算過(guò)程的示意圖。

圖3 高階訪問(wèn)依賴(lài)計(jì)算過(guò)程示意圖Fig.3 Computation process of high-order access dependency

隨著機(jī)器學(xué)習(xí)技術(shù)的飛速發(fā)展，深度學(xué)習(xí)和可視化領(lǐng)域的結(jié)合日漸成為了研究熱點(diǎn)。高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)關(guān)注于基于機(jī)器學(xué)習(xí)進(jìn)行數(shù)據(jù)管理策略的研究領(lǐng)域下的潛力，提出了一種基于深度學(xué)習(xí)模型進(jìn)行流場(chǎng)數(shù)據(jù)訪問(wèn)模式的分析、提取和建模預(yù)測(cè)的新方法[37]，并據(jù)此采用先進(jìn)的數(shù)據(jù)管理策略?xún)?yōu)化過(guò)程，支持靈活地嵌入流場(chǎng)可視化并行粒子追蹤的框架中。該方法提出了一種新的使用泛化能力更強(qiáng)的長(zhǎng)短時(shí)記憶模型[38]來(lái)對(duì)數(shù)據(jù)訪問(wèn)模式進(jìn)行建模。通過(guò)在數(shù)據(jù)空間域中放置若干粒子，積分計(jì)算它們的軌跡，并將它們作為訓(xùn)練數(shù)據(jù)來(lái)訓(xùn)練模型，學(xué)習(xí)數(shù)據(jù)塊之間的訪問(wèn)模式。首先將數(shù)據(jù)塊索引序列轉(zhuǎn)化為粒子移動(dòng)方向的序列，圖4為由粒子軌跡轉(zhuǎn)化為數(shù)據(jù)塊訪問(wèn)模式序列的過(guò)程示意圖。高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)進(jìn)一步集成了一個(gè)先進(jìn)的機(jī)器學(xué)習(xí)模型，通過(guò)接受一個(gè)基于移動(dòng)表示的序列，輸出一個(gè)概率分布的序列，表示為考慮粒子所有之前移動(dòng)和起始數(shù)據(jù)塊后，預(yù)測(cè)得到下次移動(dòng)的分布情況。

圖4 粒子軌跡轉(zhuǎn)化為數(shù)據(jù)塊訪問(wèn)模式序列示意圖Fig.4 Process of transferring pathline into sequence of data block access pattern

算法1 高階訪問(wèn)依賴(lài)的提取算法MPI_Init()if RankID in tracer_list then local_db_initialize() ∥初始化本地記錄 data_initialize()∥根據(jù)初始均勻劃分載入數(shù)據(jù) seed_placing() ∥根據(jù)初始均勻撒種獲取任務(wù) tracing_particle(); ∥正向粒子追蹤 inverse_tracing_particle() ∥反向粒子追蹤 if pathline in local_db then increase_record_num(pathline)∥增加對(duì)應(yīng)記錄的數(shù)量 else new_record(pathline) ∥添加新記錄 end ifend ifglobal_db_initialize()gather_stastics(global_db, local_db)∥收集各個(gè)進(jìn)程流線記錄信息while order ≤ max_order do calculate_frequency(order, global_db)∥迭代計(jì)算各種流線模式頻率end whileMPI_Finalize()

圖5展示了該方法中進(jìn)行數(shù)據(jù)訪問(wèn)模式建模采用的機(jī)器學(xué)習(xí)模型結(jié)構(gòu),其中D為粒子所有可能移動(dòng)到的數(shù)據(jù)塊運(yùn)動(dòng)方向。其輸入是一個(gè)長(zhǎng)度為n的移動(dòng)序列s={s0,s1,…,sn-1}，代表數(shù)據(jù)塊訪問(wèn)的歷史和當(dāng)前信息。序列中每一項(xiàng)被嵌入層轉(zhuǎn)化為一個(gè)實(shí)值向量。在嵌入層中，所有元素都被投影嵌入到另一個(gè)空間中。在嵌入層之后，高維向量的序列作為輸入，進(jìn)入到LSTM層。LSTM層輸出一個(gè)由hidden_size維向量構(gòu)成的序列。為了讓LSTM層的輸出能支持在待處理集合上的分類(lèi)任務(wù)，網(wǎng)絡(luò)結(jié)構(gòu)中還添加了一個(gè)全連接層將輸出序列的每一項(xiàng)轉(zhuǎn)化為向量，并通過(guò)一個(gè)ReLU激活層將向量中的負(fù)數(shù)值整流為0。最后通過(guò)一個(gè)softmax層對(duì)這些權(quán)重進(jìn)行重新調(diào)整，使得同一個(gè)向量里的值全部變換到(0, 1)之間并且和為1。對(duì)于每個(gè)輸入項(xiàng)，其對(duì)應(yīng)的輸出向量可以看作一個(gè)所有元素的概率分布Pi，作為預(yù)測(cè)下一步數(shù)據(jù)訪問(wèn)數(shù)據(jù)塊訪問(wèn)模式方向的概率分布。該模型使用負(fù)對(duì)數(shù)概率函數(shù)來(lái)作為損失函數(shù)支持訓(xùn)練，具體計(jì)算公式為

(2)

圖5 數(shù)據(jù)訪問(wèn)模式建模采用的機(jī)器學(xué)習(xí)模型結(jié)構(gòu)Fig.5 Machine learning model structure applied in data access pattern modeling

對(duì)于優(yōu)化器的合理選擇問(wèn)題，該工作選擇了小批量梯度下降算法，也就是每次更新模型只計(jì)算并考慮在一個(gè)小訓(xùn)練集上的損失函數(shù)之和。小批量梯度下降算法可以看作是隨機(jī)梯度下降和全批量隨機(jī)梯度的折中方案，具有更新次數(shù)更少，計(jì)算效率更高，模型更新頻率更高，收斂過(guò)程也更加聯(lián)邦魯棒，更容易避免局部最小值的優(yōu)勢(shì)。RMSProp因?yàn)樵谝延泄ぷ髦械膬?yōu)異性能，而被選擇為模型參數(shù)的學(xué)習(xí)器。它能夠自適應(yīng)地調(diào)節(jié)學(xué)習(xí)率，使其在梯度的同一個(gè)量級(jí)上。該機(jī)器學(xué)習(xí)方法可以?xún)?nèi)嵌于并行粒子追蹤的流程中，實(shí)現(xiàn)數(shù)據(jù)塊預(yù)取技術(shù)，實(shí)現(xiàn)一種嶄新的、具有潛力的CPU/GPU合作進(jìn)行粒子追蹤任務(wù)的形式，僅需要很少量的數(shù)據(jù)在主存和顯存中傳輸。

高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)基于上述基于訪問(wèn)依賴(lài)的大規(guī)模數(shù)據(jù)訪問(wèn)模式建模實(shí)現(xiàn)，能夠高效地支持并行粒子追蹤流程中的數(shù)據(jù)局部性，結(jié)合大規(guī)模數(shù)據(jù)預(yù)取的有效數(shù)據(jù)管理策略，能夠有效提升數(shù)據(jù)I/O過(guò)程中的性能指標(biāo)，為實(shí)現(xiàn)高性能并行粒子追蹤流程構(gòu)建流場(chǎng)可視化提供有力的技術(shù)模塊支持。

3.2.3 基于訪問(wèn)模式的負(fù)載動(dòng)態(tài)負(fù)載評(píng)估策略

為了進(jìn)一步提升計(jì)算效率，現(xiàn)有算法關(guān)注于粒子追蹤算法中固有的天然可并行性，采用多進(jìn)程并行優(yōu)化計(jì)算的方式提升效率，以適應(yīng)粒子追蹤本身的計(jì)算復(fù)雜性帶來(lái)的挑戰(zhàn)。引入并行計(jì)算的機(jī)制在潛在提升計(jì)算效率的同時(shí)，使得算法具有更加復(fù)雜的流程，使得并行計(jì)算中負(fù)載均衡問(wèn)題成為效率提升的關(guān)鍵所在。由于并行粒子追蹤計(jì)算過(guò)程的復(fù)雜性中，粒子的軌跡和粒子的運(yùn)行時(shí)間難以預(yù)測(cè)，如何預(yù)估不同計(jì)算進(jìn)程的負(fù)載情況，從而合理設(shè)計(jì)和實(shí)現(xiàn)負(fù)載均衡算法成為了十分重要的問(wèn)題。

高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)集成了一種基于訪問(wèn)模式的負(fù)載動(dòng)態(tài)負(fù)載評(píng)估策略[39]。該策略使用粒子追蹤的積分步數(shù)來(lái)衡量不同進(jìn)程的工作負(fù)載。在每一輪粒子追蹤計(jì)算過(guò)程中，數(shù)據(jù)塊的負(fù)載被定義為所有粒子在該輪中在此數(shù)據(jù)塊內(nèi)被追蹤的步數(shù)總和。由于不同進(jìn)程基于劃分的策略負(fù)責(zé)多個(gè)不同的數(shù)據(jù)塊中包含的粒子計(jì)算任務(wù)，因此其負(fù)載也是這些數(shù)據(jù)塊的負(fù)載之和。該方法同時(shí)將粒子數(shù)目和其歷史負(fù)載進(jìn)行考慮，用于預(yù)估數(shù)據(jù)塊在一輪中的負(fù)載。

首先記錄在每個(gè)數(shù)據(jù)塊中追蹤過(guò)的粒子數(shù)目和積分步數(shù)，并將其作為歷史追蹤信息附加在這個(gè)數(shù)據(jù)塊中。當(dāng)一輪粒子追蹤結(jié)束時(shí)，算法可以計(jì)算每個(gè)數(shù)據(jù)塊中粒子的平均負(fù)載。同時(shí)，根據(jù)未完成粒子的坐標(biāo)，算法可以獲知它們接下來(lái)在所有數(shù)據(jù)塊中的分布數(shù)量。因此，每個(gè)數(shù)據(jù)塊將來(lái)包含的負(fù)載可以用如下方法評(píng)估得到。假設(shè)在第j-1輪追蹤結(jié)束之后，對(duì)于每一個(gè)數(shù)據(jù)塊k，如果在第j輪有nk,j個(gè)粒子以它為起始?jí)K，那么第j輪預(yù)估負(fù)載可以使用如下公式進(jìn)行計(jì)算：

(3)

式中：wk,i是數(shù)據(jù)塊k在前面的第i輪中的實(shí)際負(fù)載;nk,i是在前面的第i輪中經(jīng)過(guò)數(shù)據(jù)塊k的實(shí)際粒子數(shù)目(i

算法在運(yùn)行時(shí)動(dòng)態(tài)地建立了一個(gè)一階訪問(wèn)依賴(lài)圖的數(shù)據(jù)結(jié)構(gòu)，來(lái)便捷地表達(dá)粒子在多個(gè)數(shù)據(jù)塊之間的轉(zhuǎn)移概率。每個(gè)數(shù)據(jù)塊以多個(gè)鍵值對(duì)的形式保有訪問(wèn)依賴(lài)圖的一部分，其中key是該數(shù)據(jù)塊的鄰接塊索引，value是對(duì)應(yīng)的訪問(wèn)轉(zhuǎn)移概率，用來(lái)提升查詢(xún)的效率。該方法根據(jù)從初始數(shù)據(jù)塊的訪問(wèn)轉(zhuǎn)移關(guān)系，可以預(yù)測(cè)在第2級(jí)追蹤深度層次上要訪問(wèn)的數(shù)據(jù)塊?；谠L問(wèn)轉(zhuǎn)移概率，算法可以預(yù)測(cè)粒子在這些數(shù)據(jù)塊中的粒子分布數(shù)量。之后，根據(jù)式(3)可以計(jì)算得到在每個(gè)數(shù)據(jù)塊中的負(fù)載。從這些數(shù)據(jù)塊出發(fā)，算法可以進(jìn)一步預(yù)測(cè)在下一級(jí)追蹤深度層次上要訪問(wèn)的數(shù)據(jù)塊，直至追蹤到第N級(jí)追蹤深度層次。圖6展示了追蹤深度為3時(shí)的負(fù)載評(píng)估流程。

圖6 基于訪問(wèn)模式的負(fù)載動(dòng)態(tài)負(fù)載評(píng)估策略Fig.6 Dynamic data block load estimation strategy based on access pattern

高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)采用基于訪問(wèn)模式的負(fù)載動(dòng)態(tài)負(fù)載評(píng)估策略實(shí)現(xiàn)對(duì)不同計(jì)算進(jìn)程的準(zhǔn)確負(fù)載預(yù)估，結(jié)合后續(xù)提出的負(fù)載均衡化調(diào)度算法實(shí)現(xiàn)數(shù)據(jù)和任務(wù)的合理分配，能夠有效地改善并行粒子追蹤流程中計(jì)算效率，減少空閑進(jìn)程的占比，為實(shí)現(xiàn)高性能并行粒子追蹤流程構(gòu)建流場(chǎng)可視化提供有力的技術(shù)模塊支持。

3.3 高性能并行粒子追蹤全流程

3.3.1 基于圖劃分算法整合實(shí)現(xiàn)的靜態(tài)高性能

并行粒子追蹤優(yōu)化高性能并行粒子追蹤器為了實(shí)現(xiàn)并行粒子追蹤計(jì)算效率的最優(yōu)化，復(fù)用了上述已有工作中多樣化的流場(chǎng)并行粒子追蹤數(shù)據(jù)管理模塊化的技術(shù)，并加以合理應(yīng)用、集成和精簡(jiǎn)，提出一種新穎的高性能并行粒子追蹤優(yōu)化算法框架。算法框架基于靜態(tài)任務(wù)劃分的并行優(yōu)化方法。靜態(tài)的任務(wù)劃分方法僅在初始的輪次對(duì)于任務(wù)生成初始的劃分，能夠最小化地減少算法的額外計(jì)算和開(kāi)銷(xiāo)，使得并行粒子追蹤過(guò)程更加簡(jiǎn)潔可控，也為進(jìn)一步的算法優(yōu)化提供了便利。該方法提出的框架仍在優(yōu)化和迭代過(guò)程中。

算法構(gòu)建了一個(gè)基于圖的數(shù)據(jù)結(jié)構(gòu)，用以描述并行粒子追蹤任務(wù)的分配信息，并通過(guò)圖劃分的算法實(shí)現(xiàn)各個(gè)進(jìn)程的數(shù)據(jù)和任務(wù)的分配。算法框架的主要流程包括兩個(gè)部分：預(yù)處理階段和運(yùn)行時(shí)階段。其中，運(yùn)行階段又由兩個(gè)子階段組成，分別是任務(wù)劃分和隨后的任務(wù)并行粒子追蹤。

算法框架預(yù)處理階段將流場(chǎng)轉(zhuǎn)化為高階訪問(wèn)依賴(lài)和負(fù)載信息的形式進(jìn)行表達(dá)。首先將給定的流場(chǎng)數(shù)據(jù)在空間維度上均勻分塊，在各個(gè)數(shù)據(jù)分塊上均勻撒種，進(jìn)行一輪的并行粒子追蹤，并記錄下追蹤信息。該過(guò)程應(yīng)用3.2.2節(jié)中基于訪問(wèn)依賴(lài)的大規(guī)模數(shù)據(jù)訪問(wèn)模式建模技術(shù)，與其預(yù)處理步驟較為一致，同時(shí)對(duì)每個(gè)種子點(diǎn)進(jìn)行正向和反向追蹤。只要一輪預(yù)處理計(jì)算，算法就可以得到不同階數(shù)訪問(wèn)依賴(lài)結(jié)果。與上述基本技術(shù)模塊的不同之處在于，該方法不僅收集粒子的歷史訪問(wèn)信息以構(gòu)建數(shù)據(jù)塊訪問(wèn)依賴(lài)的建模關(guān)系，還記錄了粒子在數(shù)據(jù)塊內(nèi)的負(fù)載信息(即積分步數(shù))?？蚣苡诌M(jìn)一步結(jié)合3.2.3節(jié)中基于訪問(wèn)模式的負(fù)載動(dòng)態(tài)負(fù)載評(píng)估策略，計(jì)算每個(gè)數(shù)據(jù)塊內(nèi)粒子的平均負(fù)載信息。其具體計(jì)算過(guò)程與上述算法一致。新增加的這一步平均粒子負(fù)載計(jì)算直接利用了粒子追蹤的中間結(jié)果，并不會(huì)顯著提高預(yù)處理開(kāi)銷(xiāo)。基于該預(yù)處理過(guò)程中生成的每個(gè)數(shù)據(jù)塊信息，會(huì)在后續(xù)的任務(wù)劃分和運(yùn)行時(shí)并行粒子追蹤過(guò)程中得到應(yīng)用，基于上述方法生成的單個(gè)數(shù)據(jù)塊數(shù)據(jù)信息以<數(shù)據(jù)索引,平均負(fù)載,訪問(wèn)依賴(lài)>的模型結(jié)構(gòu)形式對(duì)其進(jìn)行組織。

算法框架任務(wù)劃分階段旨在通過(guò)構(gòu)建種子塊圖結(jié)構(gòu)，實(shí)現(xiàn)兼具負(fù)載均衡性和高I/O效率的任務(wù)劃分，以進(jìn)行后續(xù)的并行粒子追蹤過(guò)程。該階段首先同樣將流場(chǎng)數(shù)據(jù)在空間維度上均勻劃分為數(shù)據(jù)塊。給定基于任務(wù)定義的種子點(diǎn)分布，遵循流場(chǎng)分塊結(jié)果，算法將其組織成多個(gè)種子塊，每個(gè)種子塊和一個(gè)數(shù)據(jù)塊及其包含的種子點(diǎn)相對(duì)應(yīng)，使得粒子追蹤任務(wù)和數(shù)據(jù)更緊密地結(jié)合起來(lái)。對(duì)于每一個(gè)種子塊，算法根據(jù)預(yù)處理的結(jié)果預(yù)測(cè)其中的種子在后續(xù)粒子追蹤過(guò)程中會(huì)訪問(wèn)哪些數(shù)據(jù)塊，同時(shí)預(yù)估其負(fù)載，并據(jù)此進(jìn)行圖構(gòu)建算法。

對(duì)種子塊的數(shù)據(jù)塊訪問(wèn)進(jìn)行預(yù)測(cè)是一個(gè)遞歸的過(guò)程。從某一個(gè)種子塊出發(fā)，可以得到該對(duì)應(yīng)數(shù)據(jù)塊訪問(wèn)依賴(lài)中的一階訪問(wèn)依賴(lài)，并找出所有可能在下一步訪問(wèn)的數(shù)據(jù)塊。這個(gè)預(yù)測(cè)過(guò)程可以一直循環(huán)迭代，直至預(yù)先定義的粒子最多可以經(jīng)過(guò)的數(shù)據(jù)塊數(shù)量。上述算法可以得到種子塊中的種子點(diǎn)可能經(jīng)過(guò)的所有數(shù)據(jù)塊序列。對(duì)于不同的種子塊，算法可以計(jì)算任意兩個(gè)種子塊中的粒子跡線計(jì)算需要的數(shù)據(jù)塊的相似性。同時(shí)根據(jù)預(yù)測(cè)到的數(shù)據(jù)塊序列，該方法還可以評(píng)估初始粒子種子在這些數(shù)據(jù)塊中進(jìn)行追蹤計(jì)算時(shí)產(chǎn)生的負(fù)載,并計(jì)算出對(duì)應(yīng)種子塊中粒子的總預(yù)估負(fù)載。

算法框架構(gòu)建的圖結(jié)構(gòu)是一個(gè)無(wú)向圖G=(V,E)，節(jié)點(diǎn)和邊分別映射了種子塊的負(fù)載信息和種子塊之間數(shù)據(jù)訪問(wèn)的關(guān)聯(lián)。圖結(jié)構(gòu)中的每個(gè)節(jié)點(diǎn)表示一個(gè)種子塊，其權(quán)重表示該種子塊的負(fù)載。節(jié)點(diǎn)之間的邊表示對(duì)應(yīng)的兩個(gè)種子塊在數(shù)據(jù)訪問(wèn)路徑的相似度?；谠摫硎鞠碌牧鲌?chǎng)和初始種子數(shù)據(jù)，需要通過(guò)圖劃分的方式，將不同的種子塊節(jié)點(diǎn)分配給不同的進(jìn)程，以實(shí)現(xiàn)負(fù)載均衡和I/O效率的優(yōu)化?；谏鲜鰞?yōu)化目標(biāo)，該圖劃分的優(yōu)化任務(wù)需要將種子塊圖劃分成若干節(jié)點(diǎn)權(quán)重之和相近的子圖。每個(gè)子圖對(duì)應(yīng)一部分的種子塊并被分配給一個(gè)進(jìn)程。圖劃分的另一個(gè)目標(biāo)是確保劃分后相同子圖中的種子塊具有盡量相似的數(shù)據(jù)訪問(wèn)，同時(shí)不同子圖中種子塊訪問(wèn)的數(shù)據(jù)塊重復(fù)性最小。因此，需要在種子塊圖劃分中，最小化需要的切割代價(jià)的大小。該方法使用ParMETIS庫(kù)[40]所提供的圖劃分算法來(lái)解決上述種子塊圖的劃分和分配問(wèn)題，結(jié)果如圖7所示。

圖7 圖劃分算法結(jié)果示意圖Fig.7 Result of graph partition-based algorithm

任務(wù)劃分之后，每個(gè)進(jìn)程可以被分配到若干個(gè)種子塊中的粒子種子，并進(jìn)行任務(wù)并行的粒子追蹤。并行粒子追蹤框架的數(shù)據(jù)管理基于3.2.1節(jié)中的鍵值對(duì)存儲(chǔ)框架高效實(shí)現(xiàn)。在運(yùn)行并行粒子追蹤過(guò)程中，高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)實(shí)現(xiàn)了面向數(shù)據(jù)塊的粒子追蹤管理和高階數(shù)據(jù)預(yù)取技術(shù)，以進(jìn)一步提升計(jì)算的效率。該框架使用了數(shù)據(jù)預(yù)取來(lái)提高I/O效率。當(dāng)從外存中載入所需要的數(shù)據(jù)項(xiàng)時(shí)，根據(jù)其訪問(wèn)依賴(lài)部分，預(yù)測(cè)下一步可能訪問(wèn)的數(shù)據(jù)塊，并將其對(duì)應(yīng)的數(shù)據(jù)項(xiàng)一同載入到內(nèi)存中。

3.3.2 可視分析技術(shù)支持的并行粒子追蹤過(guò)程

理解和優(yōu)化并行粒子追蹤過(guò)程及相應(yīng)的算法十分復(fù)雜，其中涉及較大的并行計(jì)算規(guī)模和不斷變化的數(shù)據(jù)行為。為了理解這一復(fù)雜的并行計(jì)算過(guò)程，從中整合并行計(jì)算進(jìn)程間的行為模式、數(shù)據(jù)遷移、任務(wù)交換等信息十分必要，用戶(hù)可以據(jù)此提出深刻的見(jiàn)解。可視分析技術(shù)能有效地幫助用戶(hù)理解該過(guò)程，通過(guò)圖形化的高效編碼方式，降低用戶(hù)的認(rèn)知負(fù)擔(dān)。高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)集成了一套交互式的可視分析工具[41]，以幫助用戶(hù)探索和診斷流場(chǎng)可視化并行粒子跟蹤過(guò)程中動(dòng)態(tài)負(fù)載平衡過(guò)程(數(shù)據(jù)和任務(wù)劃分)。整個(gè)并行粒子追蹤的流程被通用地建模為包含多個(gè)輪次的過(guò)程，在每個(gè)輪次中，每個(gè)粒子在流場(chǎng)中分別進(jìn)行積分計(jì)算，直至達(dá)到最大步長(zhǎng)或離開(kāi)定義的流場(chǎng)邊界。

交互式可視分析工具的系統(tǒng)界面如圖8所示，共包括3個(gè)視圖：整體視圖、節(jié)點(diǎn)-鏈接圖視圖和空間視圖。這3個(gè)視圖通過(guò)交互手段鏈接在一起，供研究人員從整體到細(xì)節(jié)進(jìn)行探索。在整體視圖中，系統(tǒng)利用折線圖來(lái)顯示并行粒子追蹤中各個(gè)進(jìn)程負(fù)載平衡過(guò)程的概述。其中橫軸表示執(zhí)行時(shí)間，其上標(biāo)記出運(yùn)行的輪數(shù)。縱軸表示負(fù)載平衡指標(biāo)，該指標(biāo)按此輪中進(jìn)程最大工作負(fù)載與平均進(jìn)程工作負(fù)載之比計(jì)算得出。節(jié)點(diǎn)-鏈接圖作為該可視分析工具的主要視圖，可視化整個(gè)并行粒子追蹤流程的數(shù)據(jù)行為，包含數(shù)據(jù)塊的傳輸以及各個(gè)計(jì)算進(jìn)程之間的任務(wù)交換。其中每個(gè)節(jié)點(diǎn)代表某一個(gè)輪次中的一個(gè)計(jì)算進(jìn)程，節(jié)點(diǎn)的大小編碼了在相應(yīng)的輪次進(jìn)程中分配的數(shù)據(jù)塊的總數(shù)，同時(shí)應(yīng)用顏色對(duì)每個(gè)進(jìn)程的負(fù)載進(jìn)行編碼。節(jié)點(diǎn)之間的鏈接表示數(shù)據(jù)塊的移動(dòng)或任務(wù)從一輪中的一個(gè)進(jìn)程到下一輪中的另一個(gè)進(jìn)程的交換。系統(tǒng)還對(duì)分配給每個(gè)過(guò)程的數(shù)據(jù)塊進(jìn)行編碼以顯示詳細(xì)信息。每個(gè)數(shù)據(jù)塊都可視化為一個(gè)正方形。對(duì)于每個(gè)進(jìn)程，其分配的數(shù)據(jù)塊將在相應(yīng)節(jié)點(diǎn)上方水平顯示。節(jié)點(diǎn)-鏈接圖視圖設(shè)計(jì)采用了類(lèi)似矩陣的總體布局。視圖中從上到下顯示多行節(jié)點(diǎn)，表示連續(xù)的并行粒子追蹤輪次。每列中的節(jié)點(diǎn)表示在不同的輪次中的同一進(jìn)程?？臻g視圖用來(lái)繪制指定數(shù)據(jù)塊中的粒子跡線，以幫助用戶(hù)診斷異常。

圖8 交互式可視分析工具的系統(tǒng)界面Fig.8 System interface of interactive visual analytics tool

4 應(yīng)用實(shí)例

4.1 基于颶風(fēng)Isabel模擬數(shù)據(jù)的流場(chǎng)全局分析并行粒子追蹤性能測(cè)試

流場(chǎng)數(shù)據(jù)全局分析任務(wù)目的是研究流場(chǎng)的綜合性特征。流場(chǎng)可視化典型的全局分析應(yīng)用包括有限時(shí)間李雅普諾夫指數(shù)(FTLE)的計(jì)算，用來(lái)衡量非定常流場(chǎng)的分離特性。FTLE計(jì)算使用了全局密集撒種策略，需要追蹤大量的粒子，對(duì)流場(chǎng)并行粒子追蹤的性能提出了較高的要求。本次測(cè)試分析任務(wù)采用的颶風(fēng)Isabel數(shù)據(jù)自于美國(guó)國(guó)家大氣研究中心對(duì)颶風(fēng)的模擬結(jié)果，由若干時(shí)變的標(biāo)量和矢量變量組成。數(shù)據(jù)時(shí)空分辨率為500×500×100×48。

測(cè)試分析利用國(guó)家超算廣州中心的天河2號(hào)超級(jí)計(jì)算機(jī)平臺(tái)。該測(cè)試最多使用了512個(gè)進(jìn)程，每個(gè)進(jìn)程的緩存被設(shè)置為512 MB。采用的數(shù)據(jù)塊劃分粒度為16×16×16×1，追蹤總數(shù)為54 000個(gè)的粒子。實(shí)驗(yàn)的性能基準(zhǔn)為強(qiáng)可擴(kuò)展性測(cè)試，同時(shí)分析負(fù)載均衡性以及I/O效率。強(qiáng)可擴(kuò)展性是測(cè)量在固定數(shù)量粒子下總執(zhí)行時(shí)間如何隨進(jìn)程數(shù)的變化而變化。其通過(guò)對(duì)所有進(jìn)程上分配一個(gè)總規(guī)模大小固定的問(wèn)題來(lái)測(cè)試方法的效率。該實(shí)驗(yàn)中采用的基線方法為不施加優(yōu)化的并行粒子追蹤算法，與高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)采用的并行粒子追蹤算法形成對(duì)比。實(shí)驗(yàn)結(jié)果如圖9所示，驗(yàn)證了高性能流場(chǎng)可視化粒子追蹤器在性能、負(fù)載平衡、I/O效率上的優(yōu)勢(shì)，達(dá)到了預(yù)期的目標(biāo)。

圖9 基于Isabel數(shù)據(jù)集進(jìn)行的強(qiáng)可擴(kuò)展性測(cè)試結(jié)果Fig.9 Strong scalability test results based on Isabel dataset

4.2 可視分析技術(shù)支持的基于Nek5000熱工水力學(xué)模擬數(shù)據(jù)多種動(dòng)態(tài)負(fù)載平衡算法比較

已有的流場(chǎng)可視化并行粒子追蹤中負(fù)載均衡化算法進(jìn)行了多樣化優(yōu)化設(shè)計(jì)，從不同的角度提升負(fù)載均衡指標(biāo)。案例分析采用高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)中集成的交互式可視分析工具針對(duì)不同的負(fù)載均衡算法進(jìn)行詳細(xì)的探索，幫助理解和比較不同算法設(shè)計(jì)和對(duì)并行粒子追蹤過(guò)程的干預(yù)方式，以待研究人員進(jìn)行針對(duì)性的診斷和進(jìn)一步地改進(jìn)。測(cè)試中主要關(guān)注的是通過(guò)數(shù)據(jù)塊和任務(wù)的轉(zhuǎn)移來(lái)進(jìn)行動(dòng)態(tài)負(fù)載平衡算法。通過(guò)在這個(gè)動(dòng)態(tài)過(guò)程中嵌入中間數(shù)據(jù)提取代碼，轉(zhuǎn)儲(chǔ)相關(guān)性能信息，進(jìn)行可視化和可視分析。在每一輪并行粒子追蹤過(guò)程中，系統(tǒng)都會(huì)獲得兩種類(lèi)型的性能數(shù)據(jù)。第1種是數(shù)據(jù)塊和任務(wù)在不同進(jìn)程和運(yùn)行輪次的分布情況。第2種涉及與源/目的進(jìn)程有關(guān)的流入/流出的數(shù)據(jù)塊和任務(wù)數(shù)據(jù)。

測(cè)試中采用的熱工水力學(xué)數(shù)據(jù)是Nek5000求解器的輸出結(jié)果，來(lái)自于美國(guó)阿貢國(guó)家實(shí)驗(yàn)室開(kāi)發(fā)的大渦Navier-Stokes模擬。本次測(cè)試使用單個(gè)時(shí)間步的數(shù)據(jù)，分辨率為512×512×512，數(shù)據(jù)規(guī)模為1.5 GB。測(cè)試分析利用國(guó)家超算廣州中心的天河2號(hào)超級(jí)計(jì)算機(jī)平臺(tái)，使用32個(gè)進(jìn)程進(jìn)行并行粒子追蹤。共對(duì)比分析運(yùn)行了3種不同的算法，如圖10所示?；谪?fù)載竊取的優(yōu)化算法的基本思想是在每輪追蹤之后將任務(wù)從繁忙的進(jìn)程發(fā)送到空閑的進(jìn)程?；趧?dòng)態(tài)數(shù)據(jù)重劃分的優(yōu)化算法則定期執(zhí)行數(shù)據(jù)重劃分，然后在每輪粒子追蹤后根據(jù)劃分結(jié)果重新分配數(shù)據(jù)塊。圖10展示了使用Nek5000數(shù)據(jù)和多種優(yōu)化算法實(shí)現(xiàn)的并行粒子追蹤過(guò)程中進(jìn)程間數(shù)據(jù)行為比較可視化。

圖10 使用Nek5000數(shù)據(jù)和多種優(yōu)化算法實(shí)現(xiàn)的并行粒子追蹤過(guò)程中進(jìn)程間數(shù)據(jù)行為可視化比較Fig.10 Comparison visualization of data behavior among processes in parallel particle tracing implemented by multiple optimization methods based on Nek5000 dataset

在基線算法中，每個(gè)進(jìn)程都保持最初分配的數(shù)據(jù)塊，并且在運(yùn)行時(shí)數(shù)據(jù)不在進(jìn)程之間移動(dòng)，進(jìn)程0和進(jìn)程3始終具有很高的負(fù)載，未實(shí)現(xiàn)負(fù)載均衡化?；趧?dòng)態(tài)數(shù)據(jù)重劃分的優(yōu)化算法流程中則出現(xiàn)了頻繁的數(shù)據(jù)遷移和調(diào)度，盡管有一些進(jìn)程被分配了較多的數(shù)據(jù)塊，系統(tǒng)卻實(shí)現(xiàn)了較為良好的負(fù)載均衡，這得益于良好的負(fù)載預(yù)估和動(dòng)態(tài)數(shù)據(jù)塊重分配算法?；谪?fù)載竊取的優(yōu)化算法同樣具有較多的數(shù)據(jù)遷移行為，但數(shù)據(jù)遷移大多發(fā)生在并行粒子多輪追蹤的后期，且集中于多個(gè)固定的進(jìn)程。由于并行計(jì)算任務(wù)在初始幾輪大多難以觸發(fā)結(jié)束跳出條件，同時(shí)數(shù)據(jù)初始按空間劃分分配的相對(duì)均勻性，大多數(shù)進(jìn)程未出現(xiàn)空閑的時(shí)間，因而不符合負(fù)載竊取的觸發(fā)條件。相比于基于動(dòng)態(tài)數(shù)據(jù)重劃分的優(yōu)化算法，其負(fù)載均衡指標(biāo)略遜一籌。案例證明了基于該可視分析工具可以有效幫助用戶(hù)發(fā)現(xiàn)不同并行粒子追蹤算法的特征。

5 結(jié) 論

1) 高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)包括超算服務(wù)器平臺(tái)上部署的基于先進(jìn)數(shù)據(jù)管理策略?xún)?yōu)化的并行粒子追蹤器，能幫助用戶(hù)高效地生成流場(chǎng)中的跡線。

2) 高性能流場(chǎng)并行粒子追蹤數(shù)據(jù)管理系統(tǒng)包括在本地端的可視分析理解診斷工具，能幫助用戶(hù)理解、分析、診斷并行粒子追蹤負(fù)載均衡算法。