BESIII實(shí)驗(yàn)軟件事例級(jí)并行化研究

馬震太，張曉梅，孫功星

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 兩級(jí)選擇樹進(jìn)行四路合并Fig.3 Two level selection tree for merge

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

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

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

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

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

2.1 事例組

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

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

（2）事例組。由特定數(shù)目事例構(gòu)成的有序序列；其結(jié)構(gòu)如圖5所示，其中FileID字段標(biāo)識(shí)文件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ù)錯(cuò)誤。EventCount字段記錄該事例組包含的事例數(shù)目；EventProcessedCount字段用于記錄已處理的事例數(shù)目；CurrentIndex字段用于記錄當(dāng)前正在處理的事例對(duì)應(yīng)的索引位置；EventPtr[n]為一組指向若干事例數(shù)據(jù)入口地址的指針。事例組支持對(duì)應(yīng)線程存取數(shù)據(jù)。

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

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

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

2.2 運(yùn)轉(zhuǎn)機(jī)制

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

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

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

圖7 事例組信號(hào)量變化圖Fig.7 Semaphore variation diagram of event group

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

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

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

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

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

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

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

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

圖8 線程請(qǐng)求事例流程圖Fig.8 Flow chart of requesting event

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

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

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

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

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

3 文件I/O

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果

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

表1 實(shí)驗(yàn)環(huán)境Table 1 Experimental environment

圖13 PMT信號(hào)處理過程性能對(duì)比Fig.13 Performance contrast of PMT signal processing

圖14 點(diǎn)搜索過程性能對(duì)比Fig.14 Performance contrast of locating point

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

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

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

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

圖16 Hit算法性能對(duì)比Fig.16 Performance contrast of Hit algorithm

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

圖18 磁場(chǎng)求解過程性能對(duì)比Fig.18 Performance contrast of magnetic field computing

圖19 高能物理熱點(diǎn)矢量混合運(yùn)算性能對(duì)比Fig.19 Performance contrast of hot vector operation

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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