馬震太，張曉梅，孫功星

1.中國科學(xué)院 高能物理研究所，北京 100049

2.中國科學(xué)院大學(xué)，北京 100049

近年來隨著高能物理作業(yè)所需資源的不斷增長，通過不斷增加時鐘頻率和分配更多物理機的時代將趨于終結(jié)，未來硬件的特點是更專業(yè)和更多的內(nèi)核，尤其是異構(gòu)資源，為充分利用多核的潛力，并行技術(shù)在高能物理領(lǐng)域勢必得到廣泛的應(yīng)用。

并行計算以充分發(fā)揮硬件的計算能力為首要目標(biāo)，具體實現(xiàn)時需結(jié)合體系結(jié)構(gòu)選擇相應(yīng)的解決方案，常見的并行方法有：（1）區(qū)域分解法，把原問題的求解轉(zhuǎn)化為若干子問題的求解。（2）功能分解法，將由不同功能組成的問題，按照其功能進行分解，并行求解。（3）流水線技術(shù)，常用的時間并行技術(shù)。（4）分而治之，把復(fù)雜問題劃分為等價的小問題。按處理器處理數(shù)據(jù)的方式，又分為：（1）同步并行，在某一刻需要與其他處理器進行數(shù)據(jù)交換，才能繼續(xù)執(zhí)行。（2）異步并行，不需要處理器之間相互等待，充分發(fā)揮CPU效率[1]。

國內(nèi)外常見的并行編程模型主要有以下幾類：（1）共享內(nèi)存模型，如OpenMP[2]、pthreads[3]；（2）消息傳遞模型，MPI[4]、虛擬并行機[5]；（3）數(shù)據(jù)并行模型，CUDA[6]、OpenCL[7]、MapReduce[8]；（4）混合模型，如MPI+OpenMP模型[9]、MPI+CUDA模型[10]、大規(guī)模并行編程模型[11]；（5）基于共享存儲的任務(wù)并行編程模型，如fork-join框架、Cilk++、TPL[12]、TBB[13]。

北京譜儀（BESIII）是北京正負(fù)電子對撞機上的大型通用譜儀，BESIII離線軟件是一個相當(dāng)復(fù)雜的系統(tǒng)，包含了離線數(shù)據(jù)處理框架，模擬、重建、刻度等算法模塊，使用了大量的外部庫，涉及到多種編程語言；需要處理PB級別的數(shù)據(jù)量，所以并行方案的改善已迫在眉睫。

本文對BESIII實驗軟件的并行化展開研究，首先分析了作業(yè)級并行和序列級并行的弊端，從而得到內(nèi)存消耗嚴(yán)重和性能損失的根本原因，并由此提出了事例級并行的解決方案，主要創(chuàng)新點表現(xiàn)在：

（1）設(shè)立全局緩沖區(qū)，提出了事例組的定義，采用分而治之的并行方法，揭示了數(shù)據(jù)粒度是制約并行計算性能的主要因素。

（2）設(shè)計了事例級并行的框架，核心思想是：采用最佳粒度，在保證并行度的同時，減少通信次數(shù)和通信量，從而使性能加速比接近線性?？蚣苤械年P(guān)鍵技術(shù)有信號量交互機制、映射表機制、信號的發(fā)射與接收、延遲加載技術(shù)、三層映射表。

（3）結(jié)合實驗數(shù)據(jù)，分析事例級并行相較于作業(yè)級并行和序列級并行的性能優(yōu)勢。

按操作系統(tǒng)切換上下文環(huán)境的方式，作業(yè)級并行和序列級并行皆屬于進程級并行；而事例級并行則屬于線程級并行。從處理器處理數(shù)據(jù)的方式，作業(yè)級并行和序列級并行屬于同步并行，事例級并行屬于異步并行。從編程模型的角度，序列級并行和事例級并行雖然都選用了任務(wù)并行編程模型，但序列級并行采用fork-join框架，而事例級并行則選用TBB。

1 高能物理傳統(tǒng)并行化方案

高能物理作業(yè)通常為批處理作業(yè)，這些作業(yè)在指定的數(shù)據(jù)集合上，運行特定的物理計算過程，最終產(chǎn)生科學(xué)家們需要的數(shù)據(jù)結(jié)果；包括模擬、重建、刻度、分析等過程，數(shù)據(jù)文件相互獨立，每個文件包含若干個事例，各個事例數(shù)據(jù)之間相互獨立。作業(yè)的執(zhí)行過程依次為：讀取待處理數(shù)據(jù)，創(chuàng)建并初始化消息服務(wù)、作業(yè)配置服務(wù)、其他必須服務(wù)，啟動作業(yè)配置選項的頂級算法，事例處理循環(huán)，停止相關(guān)算法和服務(wù)，析構(gòu)并釋放資源，作業(yè)結(jié)束；在初始化階段，應(yīng)用軟件會將大量的庫文件、通用配置文件、幾何數(shù)據(jù)裝入內(nèi)存[14]。根據(jù)庫文件和幾何數(shù)據(jù)是否被各個進程所共享，高能物理傳統(tǒng)并行化方案可分為作業(yè)級并行和序列級并行。

高能物理作業(yè)級并行，對每個作業(yè)創(chuàng)建一個處理進程，各個作業(yè)進程之間相互獨立；每個作業(yè)進程初始化階段都會向內(nèi)存中讀入大量的庫文件和幾何數(shù)據(jù)，導(dǎo)致內(nèi)存消耗嚴(yán)重；各個作業(yè)請求的資源直到作業(yè)結(jié)束階段才釋放，致使資源閑置，無法高效利用；輸出文件由各個作業(yè)單獨負(fù)責(zé)，得不到統(tǒng)一的管理。作業(yè)級并行示意圖如圖1所示。

圖1 作業(yè)級并行原理Fig.1 Principle of job level parallel

如圖2所示，為避免作業(yè)級并行時庫文件和幾何數(shù)據(jù)無法共享所帶來的內(nèi)存浪費問題，序列級并行采用了fork-join框架：父進程將庫文件、幾何數(shù)據(jù)、通用文件裝入內(nèi)存，根據(jù)用戶指定的參數(shù)調(diào)用fork系統(tǒng)啟動多個子進程；將多個文件對應(yīng)的大量事例數(shù)據(jù)集合，分解成若干事例子集；每個事例子集對應(yīng)一個子進程，每個子進程在事例循環(huán)結(jié)束后生成對應(yīng)的臨時數(shù)據(jù)文件；父進程將所有的臨時文件排序，形成輸出文件。

圖2 序列級并行原理Fig.2 Principle of sequence level parallel

序列級并行有助于節(jié)約內(nèi)存，但文件合并階段需要排序工作，資源得不到高效配置；由于臨時數(shù)據(jù)文件存儲在磁盤中，屬于外部排序。因臨時數(shù)據(jù)文件中的事例數(shù)據(jù)已經(jīng)是非遞減有序的，所以外部排序算法采用選擇樹進行多路合并[15]：假設(shè)事例總數(shù)為m，共存儲在n個臨時文件中，查看每個臨時文件的第一個事例，將這n個首位事例作為n個終端節(jié)點構(gòu)造二叉樹，自下而上選擇次序小的事例，樹的根部即為次序最小的事例，將這個事例寫到輸出文件；接著將樹中相應(yīng)的事例替換為該臨時數(shù)據(jù)文件的下一個事例，重復(fù)選擇過程，直到所有事例全部輸出到結(jié)果數(shù)據(jù)；每次選擇需要lgn次比較，故時間復(fù)雜度為O(mlgn)。因每個事例開始執(zhí)行時需讀取磁盤1次，執(zhí)行結(jié)束寫至臨時文件需要寫磁盤1次，合并過程需要從磁盤讀取臨時文件1次，生成最終文件需寫磁盤1次；整個過程m個事例共需要I/O操作4m次。圖3展示了兩級選擇樹進行四路合并的樣例，即n=4,m=16 000，共需要32 000次比較操作，64 000次I/O操作。

圖3 兩級選擇樹進行四路合并Fig.3 Two level selection tree for merge

2 事例級并行框架設(shè)計

為了提高并行度，需要將一個錯綜復(fù)雜的大任務(wù)拆分成大量可以并行執(zhí)行的子任務(wù)，由于各個事例數(shù)據(jù)之間相互獨立，故這些子任務(wù)的并行類型為數(shù)據(jù)并行；作業(yè)級并行選擇以單個文件全體事例組成的數(shù)據(jù)流作為基本單元，序列級并行選擇以區(qū)間有序但全部事例失序的子數(shù)據(jù)流作為基本單元，這兩者都不能對內(nèi)存進行統(tǒng)一高效的管理；為解決這一難題，需要重新選擇數(shù)據(jù)并行的粒度。如果以單個事例作為基本處理單元，便可以產(chǎn)生數(shù)量最多的子任務(wù)，取得最高的線程并行度，但同時也會產(chǎn)生最高的線程交互開銷；一個好的粒度應(yīng)該在子任務(wù)并行帶來的性能提升與線程交互的性能開銷中取得最佳平衡點。因此本文提出了事例組的概念，將特定數(shù)目連續(xù)有序的事例視為一個事例組，選取事例組作為數(shù)據(jù)并行的基本邏輯單元；將若干連續(xù)且按原始順序流動的事例組視為隊列；故而在內(nèi)存中創(chuàng)建全局緩沖區(qū)，用于緩存事例數(shù)據(jù)，緩沖區(qū)將事例數(shù)據(jù)從輸入文件讀入，在數(shù)據(jù)處理完成后按輸入順序?qū)懙捷敵鑫募小?/p>

考慮到線程并行共享堆內(nèi)存，可大幅降低內(nèi)存消耗，同時共享資源可以得到高效管理，故基于事例組創(chuàng)建的各個子任務(wù)均采用線程實現(xiàn)，這些線程被稱為事例循環(huán)處理線程，線程啟動后會統(tǒng)一提交到TBB并行執(zhí)行。之所以選擇任務(wù)并行編程模型TBB，是因為TBB從邏輯任務(wù)而非物理線程的角度指定線程功能[16]，不用考慮線程的細(xì)節(jié)問題；只需從庫中選擇高效并行的算法模板，即可得益于處理器高效的多路執(zhí)行而獲得性能提升[2，5]。

根據(jù)上述思想設(shè)計的事例級并行框架如圖4所示，由圖可知，全局緩沖區(qū)中的邏輯單元可以保存任何類型的事例數(shù)據(jù)，而各個并行子任務(wù)為邏輯子任務(wù)，框架中只有文件輸入服務(wù)和文件輸出服務(wù)線程與具體文件數(shù)據(jù)相關(guān)，故只需創(chuàng)建文件輸入服務(wù)和文件輸出服務(wù)的子類對象并實現(xiàn)相關(guān)代碼邏輯，本框架便可推廣到其他物理實驗?，F(xiàn)本章將從事例組的定義、事例組的運轉(zhuǎn)機制、如何訪問事例組中的事例數(shù)據(jù)三個方面對框架展開闡述。

圖4 事例級并行框架設(shè)計圖Fig.4 Architecture of event level parallel

2.1 事例組

緩沖區(qū)中事例數(shù)據(jù)在內(nèi)存中的邏輯層次自上而下為：{事例組先進先出隊列、事例組、事例}。

（1）事例。由事例頭和事例數(shù)據(jù)組成，事例頭記錄了事例大小、Run號、事例號、事例類型、探測器名，以及各個子探測器數(shù)據(jù)位置的偏移地址表；事例數(shù)據(jù)部分由各個子探測器的數(shù)據(jù)頭和數(shù)據(jù)部分組成，子探測器的數(shù)據(jù)頭用于記錄子探測器標(biāo)識、數(shù)據(jù)大小、數(shù)據(jù)狀態(tài)。

（2）事例組。由特定數(shù)目事例構(gòu)成的有序序列；其結(jié)構(gòu)如圖5所示，其中FileID字段標(biāo)識文件ID，用于標(biāo)記事例組所屬文件上下文環(huán)境；GroupState字段標(biāo)記事例組當(dāng)前狀態(tài)，具體狀態(tài)包括：空閑、數(shù)據(jù)準(zhǔn)備就緒、事例循環(huán)正在處理數(shù)據(jù)、數(shù)據(jù)處理完成等待輸出、數(shù)據(jù)占用內(nèi)存可釋放、數(shù)據(jù)錯誤。EventCount字段記錄該事例組包含的事例數(shù)目；EventProcessedCount字段用于記錄已處理的事例數(shù)目；CurrentIndex字段用于記錄當(dāng)前正在處理的事例對應(yīng)的索引位置；EventPtr[n]為一組指向若干事例數(shù)據(jù)入口地址的指針。事例組支持對應(yīng)線程存取數(shù)據(jù)。

圖5 事例組數(shù)據(jù)結(jié)構(gòu)圖Fig.5 Data structure of event group

（3）事例組先進先出隊列。由若干事例組按先進先出原則構(gòu)成的有序隊列，隊列尾端只允許插入操作，首端只允許刪除操作。

由于輸入文件包含的事例數(shù)目一定，故事例組數(shù)目和事例組大小成反比關(guān)系。當(dāng)事例組包含的事例數(shù)目太多時，則事例組分配給事例循環(huán)線程后，需要較多的計算時間才能處理完畢，在程序運行前期，由于事例組數(shù)目較多，每個線程都能分配到自己所屬的事例組，但在程序運行后期，由于事例組數(shù)目逐漸減少，只有部分線程分配到事例組，其他線程則處于閑置狀態(tài)，極端的情況就是整個事例組先進先出隊列只有一個事例組，此時整個程序運行期間只有一個事例循環(huán)處理線程執(zhí)行全部事例的計算工作，導(dǎo)致CPU時間得不到充分利用，造成性能低下。當(dāng)事例組包含的事例數(shù)目太少時，則事例循環(huán)處理線程只用少量時間即可完成事例組的計算量，極端情況是一個事例組只包含一個事例，這樣每處理一個事例都要請求一次事例組，事例循環(huán)處理線程需要頻繁請求事例組，大量的時間被浪費在事例組調(diào)度方面，事例計算時間所占比重嚴(yán)重下滑，同樣會造成性能低下。事例的計算時間和事例組的大小，與框架性能有著緊密的關(guān)系。對于真實的BESIII實驗數(shù)據(jù)處理中，由于作業(yè)的各種參數(shù)很難做出正確的預(yù)估，故對大量有代表性的作業(yè)，選用不同的事例組尺寸進行實驗，得出該作業(yè)的事例組大小取值區(qū)間；將作業(yè)類型與事例組大小的取值區(qū)間錄入作為訓(xùn)練集，建立線性模型，采用最小二乘法進行學(xué)習(xí)，取得了優(yōu)良的效果。

2.2 運轉(zhuǎn)機制

為了讓事例組和各個工作線程正常交互，需要追蹤事例組的狀態(tài)并設(shè)置狀態(tài)機，如圖6所示，事例組的狀態(tài)有：空閑、數(shù)據(jù)就緒、處理中、處理完成。文件輸入線程在初始化文件上下文環(huán)境后，向全局緩沖區(qū)請求分配處于空閑狀態(tài)的事例組，將原始文件中的事例數(shù)據(jù)按序讀入事例組，在數(shù)據(jù)輸入完成后置事例組為數(shù)據(jù)就緒狀態(tài)；各個事例循環(huán)處理線程向全局緩沖區(qū)申請分配數(shù)據(jù)就緒狀態(tài)的事例組，分配成功后置事例組狀態(tài)為處理中，在事例組中的全部事例處理完成后，置事例組狀態(tài)為處理完成；文件輸出線程按事例組的輸入順序，依次將處理完成狀態(tài)事例組的數(shù)據(jù)寫到磁盤文件后，重置事例組為空閑狀態(tài)。

圖6 事例組狀態(tài)機Fig.6 State machine of event group

為同步處于不同狀態(tài)事例組的數(shù)目，本文設(shè)計了三個信號量：記錄處于空閑狀態(tài)事例組數(shù)目的信號量EmptyStateSemaphore，記錄處于數(shù)據(jù)就緒狀態(tài)事例組數(shù)目的信號量ReadyStateSemaphore，記錄處于處理完成狀態(tài)事例組數(shù)目的信號量ProcessedStateSemaphore。圖7中的P、V操作[17]為信號量操作原語：（1）P操作，當(dāng)該信號量大于零時，將信號量減一，否則調(diào)用P操作的線程等待，直至該信號量大于零；（2）V操作，將對應(yīng)信號量加一。信號量變化過程詳述如下：

圖7 事例組信號量變化圖Fig.7 Semaphore variation diagram of event group

（1）文件輸入線程對EmptyStateSemaphore執(zhí)行P操作以檢查是否存在空閑狀態(tài)的事例組：如存在則讀入新的事例數(shù)據(jù)，事例讀入結(jié)束后，轉(zhuǎn)換狀態(tài){空閑→數(shù)據(jù)就緒}，然后對ReadyStateSemaphore執(zhí)行V操作；否則等待。

（2）每個事例循環(huán)處理線程都會向全局緩沖區(qū)發(fā)出請求，緩沖區(qū)查詢映射表：若為新的線程，對ReadyState-Semaphore執(zhí)行P操作，將分配的事例組轉(zhuǎn)換狀態(tài){數(shù)據(jù)就緒→處理中}，并更新映射表和文件上下文；若為映射表中已存在的線程，則返回對應(yīng)事例組中下個事例。

（3）當(dāng)事例組中的事例全部處理完成，則將該事例組轉(zhuǎn)換狀態(tài){處理中→處理完成}，對ProcessedState-Semaphore執(zhí)行V操作；然后尋找新的事例組，并檢查文件上下文根據(jù)需要進行更新。由于所有事例循環(huán)處理線程對事例組的競爭全部集中在{數(shù)據(jù)就緒→處理中}這一狀態(tài)轉(zhuǎn)換，選擇事例組為粒度顯著降低了加鎖的開銷。

（4）文件輸出線程對ProcessedStateSemaphore執(zhí)行P操作，將狀態(tài)為處理完成的事例組輸出到磁盤，轉(zhuǎn)換狀態(tài){處理完成→空閑}，對EmptyStateSemaphore執(zhí)行V操作。

狀態(tài)機和信號量的設(shè)置，保證了事例數(shù)據(jù)自始至終按原序存儲，不再發(fā)生任何變更，避免了復(fù)雜的合并排序工作；由于文件輸入輸出線程以事例組為單位與磁盤交互，假設(shè)一個事例組包含1 000個事例，則與圖3相比，不需要比較操作，只需32次I/O操作；與序列級并行相比，I/O性能有了質(zhì)的飛躍。

2.3 數(shù)據(jù)訪問

至此，本文確定了事例組的運轉(zhuǎn)機制，現(xiàn)在只需將不同的事例組以特定模式分派到處理器上，即可支持各個事例循環(huán)處理線程訪問事例數(shù)據(jù)；事例組的調(diào)度策略由TBB負(fù)責(zé)執(zhí)行，采用寬度優(yōu)先和深度優(yōu)相結(jié)合的方法：寬度優(yōu)先用于提高并行度，保持CPU繁忙，深度優(yōu)先則促使線程高效執(zhí)行。為了按特定事例組中的原始順序訪問事例數(shù)據(jù)，需建立兩張映射表，一張為每個事例循環(huán)處理線程與對應(yīng)事例組的映射表，用于分配事例數(shù)據(jù)；另一張為每個事例循環(huán)處理線程與對應(yīng)文件上下文環(huán)境的映射表，用于更新文件上下文環(huán)境。

每個事例循環(huán)線程請求事例數(shù)據(jù)的流程如圖8所示，全局緩沖區(qū)首先查詢線程與事例組映射表：

圖8 線程請求事例流程圖Fig.8 Flow chart of requesting event

（1）如果為新的線程，則獲取處于數(shù)據(jù)就緒狀態(tài)的事例組分配給線程，更新映射表，設(shè)置事例組狀態(tài)為處理中，根據(jù)事例組FileID字段初始化文件上下文環(huán)境，讀取事例數(shù)據(jù)開始處理。

（2）如果映射表已經(jīng)存在該線程的記錄，則獲得對應(yīng)事例組，判斷當(dāng)前事例組是否已經(jīng)處理完成，若尚未處理完成的話，直接獲取下個事例。

（3）如果事例組的事例數(shù)據(jù)已經(jīng)全部處理完成，則更新事例組的狀態(tài)為處理完成；向全局緩沖區(qū)請求新的事例組，如果當(dāng)前沒有處于數(shù)據(jù)就緒狀態(tài)的事例組，則線程進入阻塞狀態(tài)，直到有數(shù)據(jù)就緒狀態(tài)的事例組出現(xiàn)。

（4）如果全局緩沖區(qū)中存在數(shù)據(jù)就緒狀態(tài)的事例組，則更新映射表，并設(shè)置該事例組狀態(tài)為處理中，檢測事例組FileID字段與線程的文件上下文環(huán)境是否一致。

（5）如果文件發(fā)生變更，則調(diào)用文件只讀服務(wù)更新文件上下文環(huán)境。

3 文件I/O

作業(yè)級并行和序列級并行這兩種方案的事例處理過程皆是一個循環(huán)的過程，作業(yè)級并行每個作業(yè)的循環(huán)次數(shù)取決于作業(yè)輸入文件所包含的事例數(shù)目，序列級并行每個進程的循環(huán)次數(shù)取決于對應(yīng)的事例子集所包含的事例數(shù)；該循環(huán)過程分為三個階段：事例讀取、事例數(shù)據(jù)處理、事例存儲；這種循環(huán)機制既導(dǎo)致I/O操作頻繁，又容易產(chǎn)生大量內(nèi)存碎片。事例級并行由于全局緩沖區(qū)和信號量機制的支持，使得文件輸入線程、文件輸出線程、事例處理線程可以并行工作，徹底消除了循環(huán)機制所帶來的弊端，本章對事例級并行的文件I/O具體技術(shù)展開詳述。

BESIII實驗軟件數(shù)據(jù)文件自頂向下分為四層結(jié)構(gòu)：目錄、樹、分枝、葉子，但大多數(shù)情況下，用戶只需訪問其中的部分?jǐn)?shù)據(jù)。為避免讀入大量的無效數(shù)據(jù)，采用了延遲加載技術(shù)，如圖9所示，只將數(shù)據(jù)指針讀入內(nèi)存，僅當(dāng)事例處理線程訪問相應(yīng)數(shù)據(jù)時，才會請求文件只讀服務(wù)，通過事例對象指針，獲取線程對應(yīng)的分支管理器，進而調(diào)用分枝搜索算法在線程本地已知樹列表中查找所需樹的指針，最終將磁盤數(shù)據(jù)讀入內(nèi)存；延遲加載的應(yīng)用，顯著提高了內(nèi)存利用率。實驗軟件還提供了分枝選擇服務(wù)，用于篩選用戶感興趣的事例數(shù)據(jù)，進一步減少冗余的讀寫操作，提升I/O性能。

圖9 事例級并行數(shù)據(jù)服務(wù)圖Fig.9 Data service diagram of event level parallel

原始數(shù)據(jù)一般以字節(jié)流形式存儲于文件中，由文件輸入服務(wù)線程將字節(jié)流數(shù)據(jù)讀入到內(nèi)存，內(nèi)存中的字節(jié)流形成一個完整邏輯事例單元；字節(jié)流解包服務(wù)可以很方便地獲得各部分?jǐn)?shù)據(jù)，文件輸出服務(wù)線程則按順序?qū)⑦壿嬍吕龁卧獙懭氲街付ǖ淖止?jié)流文件中[18]。如圖10所示，在數(shù)據(jù)存儲管理器初始化后，當(dāng)每個事例循環(huán)執(zhí)行時，向信號管理器發(fā)送“事例開始”信號，信號管理器通過信號句柄請求事例，進而訪問全局緩沖區(qū)獲得下個事例。每個事例循環(huán)處理線程都會設(shè)置一個監(jiān)視器，用于控制事例執(zhí)行過程中的各個步驟，以便在事例發(fā)生錯誤和異常時及時做出響應(yīng)，避免造成硬件資源的浪費。

圖10 事例級并行事例獲取流程圖Fig.10 Flow chart of distributing event data

元組輸出為分析作業(yè)獨有的輸出方式；針對事例級并行的元組輸出，本文建立了三層映射：在作業(yè)腳本配置時，由用戶設(shè)置第一層映射，“邏輯文件名”→“物理文件路徑”；在并行緩沖區(qū)合并服務(wù)初始化階段建立第二層映射，“邏輯文件名”→“緩存合并管理器（TBuffer-Merger）”；在用戶算法初始化階段建立第三層映射，“<線程ID，邏輯文件名>”→“臨時緩存”、“數(shù)據(jù)樹”→“臨時緩存”。在線程處理事例循環(huán)時，線程只需填充對應(yīng)的樹。最終化階段，根據(jù)線程ID和邏輯文件名，查詢映射表，獲取對應(yīng)的臨時緩存，將數(shù)據(jù)文件輸出到磁盤；原理如圖11所示。

圖11 事例級并行Tuple輸出原理圖Fig.11 Tuple output principle of event level parallel

4 實驗結(jié)果

目前BESIII軟件依賴的外部庫皆為串行版本，并行版本算法庫的開發(fā)工作尚需較多的人力物力才能完成，為預(yù)測事例級并行方案在BESIII中的性能趨勢，本實驗將真實BESIII實驗數(shù)據(jù)處理中比較耗時的熱點過程相關(guān)代碼移植為并行版本，進行測試，從而更準(zhǔn)確地預(yù)測事例級并行的優(yōu)勢所在。為了實驗數(shù)據(jù)更加精確，實驗數(shù)據(jù)取50輪測試數(shù)據(jù)的平均值，本文實驗環(huán)境詳見表1。

表1 實驗環(huán)境Table 1 Experimental environment

圖13 PMT信號處理過程性能對比Fig.13 Performance contrast of PMT signal processing

圖14 點搜索過程性能對比Fig.14 Performance contrast of locating point

圖15 截面計算過程性能對比Fig.15 Performance contrast of calculating cross sections

BESIII事例類型包括模擬、重建、物理分析，模擬用于研究高能物理實驗中各種隨機物理過程，以及物理量的統(tǒng)計分布，全面地反映相關(guān)物理量的統(tǒng)計性質(zhì)。模擬作業(yè)熱點過程的實驗數(shù)據(jù)如圖12～17所示，相較于作業(yè)級并行，隨機數(shù)生成過程的序列級并行性能提升1.6%～5.3%，事例級并行性能提升4.6%～13.9%；PMT信號處理過程的序列級并行性能提升2.5%～6.6%，事例級并行性能提升5.1%～15.4%；點搜索過程的序列級并行性能提升3%～7.2%，事例級并行性能提升5.8%～14.5%；截面計算過程的序列級并行性能提升2.5%～5.7%，事例級并行性能提升5.2%～14.2%；Hit算法的序列級并行性能提升1.1%～4.1%，事例級并行性能提升3.7%～12%；體素查找過程的序列級并行性能提升2.3%～4.1%，事例級并行性能提升3.2%～9.6%。

圖12 隨機數(shù)生成過程性能對比Fig.12 Performance contrast of random number generation

事例重建是利用相應(yīng)的刻度常數(shù)對原始數(shù)據(jù)進行修正，將原始數(shù)據(jù)中的數(shù)字信號還原為粒子的位置、能量、動量等物理量，最終形成重建數(shù)據(jù)交給物理分析人員。重建作業(yè)熱點過程如圖18～21所示，相較于作業(yè)級并行，磁場求解過程的序列級并行性能提升2.1%～4%，事例級并行性能提升2.6%～7.9%；高能物理熱點矢量混合運算的序列級并行性能提升1.8%～5.4%，事例級并行性能提升2.9%～11.8%；軌跡追蹤算法的事例級并行性能提升1.3%～2.9%，事例級并行性能提升1.5%～5.2%；路徑求解算法的序列級并行性能提升3.2%～7.6%，事例級并行性能提升3.5%～16.2%。

圖16 Hit算法性能對比Fig.16 Performance contrast of Hit algorithm

圖17 體素查找過程性能對比Fig.17 Performance contrast of locating voxel

圖18 磁場求解過程性能對比Fig.18 Performance contrast of magnetic field computing

圖19 高能物理熱點矢量混合運算性能對比Fig.19 Performance contrast of hot vector operation

圖20 軌跡追蹤算法性能對比Fig.20 Performance contrast of trajectory tracking

圖21 路徑求解算法性能對比Fig.21 Performance contrast of calculating path

相較于作業(yè)級并行，模擬作業(yè)和重建作業(yè)熱點過程的序列級并行性能提升幅度不大，這是由于序列級并行雖然消除了重復(fù)的初始化過程且減少了冗余I/O，但引入了復(fù)雜的事例排序；事例級并行方案能獲得如此顯著的性能提升，說明事例組運轉(zhuǎn)機制是有效的。

物理分析是根據(jù)科研人員的具體需要，對不同的實驗數(shù)據(jù)進行綜合的計算和統(tǒng)計，進而獲得所需的物理結(jié)果。分析作業(yè)熱點過程如圖22～23所示：相較于作業(yè)級并行，衰變樹處理過程序列級并行性能提升4.8%～9.7%，事例級并行性能提升5.3%～19.8%；射線處理過程序列級并行性能提升2.8%～7.5%，事例級并行性能提升6.5%～26.7%。

圖22 衰變樹處理過程性能對比Fig.22 Performance contrast of Decay Tree

事例級并行以事例組為粒度，保證了事例數(shù)據(jù)在與輸入線程、輸出線程、事例處理循環(huán)線程交互時的順序流動，消除了無效的內(nèi)存浪費，最終大幅提升了分析作業(yè)的文件I/O效率；由于射線處理過程采用前文所述的三層映射，雖然有一定的內(nèi)存損耗，但性能提升顯著?，F(xiàn)對上述兩個過程的內(nèi)存消耗進行對比測試，實驗數(shù)據(jù)如圖24、25所示：相較于作業(yè)級并行，衰變樹過程序列級并行內(nèi)存用量降低5.6%～28.7%，事例級并行內(nèi)存用量降低12.9%～46.5%；射線處理過程序列級并行內(nèi)存用量降低3.5%～19.6%，事例級并行內(nèi)存用量降低9.2%～25.8%。

圖23 射線處理過程性能對比Fig.23 Performance contrast of ray processing

圖24 衰變樹內(nèi)存消耗量對比Fig.24 Performance contrast of Decay Tree memory consumption

圖25 射線處理過程內(nèi)存消耗量對比Fig.25 Performance contrast of ray processing memory consumption

5 結(jié)束語

本文實驗結(jié)果總體是令人滿意的，但實驗軟件目前并不支持異構(gòu)平臺[19]；而且當(dāng)事例中某個算法長時間占用某類資源，事例級并行將會出現(xiàn)其他資源閑置的情況；在以后的實驗中，將針對算法和數(shù)據(jù)的依賴關(guān)系建立有向無環(huán)圖[20]，將控制流信息和數(shù)據(jù)流信息集成在圖中，采用關(guān)鍵路徑和性能權(quán)重表相結(jié)合的解決方案，以期在異構(gòu)平臺上能充分利用硬件資源，取得理想的實驗效果。