BESIII實驗軟件事例級并行化研究

馬震太，張曉梅，孫功星

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

2.中國科學院大學，北京 100049

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

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

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

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

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

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

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

（3）結合實驗數據，分析事例級并行相較于作業級并行和序列級并行的性能優勢。

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

1 高能物理傳統并行化方案

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

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

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

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

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

序列級并行有助于節約內存，但文件合并階段需要排序工作，資源得不到高效配置；由于臨時數據文件存儲在磁盤中，屬于外部排序。因臨時數據文件中的事例數據已經是非遞減有序的，所以外部排序算法采用選擇樹進行多路合并[15]：假設事例總數為m，共存儲在n個臨時文件中，查看每個臨時文件的第一個事例，將這n個首位事例作為n個終端節點構造二叉樹，自下而上選擇次序小的事例，樹的根部即為次序最小的事例，將這個事例寫到輸出文件；接著將樹中相應的事例替換為該臨時數據文件的下一個事例，重復選擇過程，直到所有事例全部輸出到結果數據；每次選擇需要lgn次比較，故時間復雜度為O(mlgn)。因每個事例開始執行時需讀取磁盤1次，執行結束寫至臨時文件需要寫磁盤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 事例級并行框架設計

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

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

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

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

2.1 事例組

緩沖區中事例數據在內存中的邏輯層次自上而下為：{事例組先進先出隊列、事例組、事例}。

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

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

圖5 事例組數據結構圖Fig.5 Data structure of event group

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

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

2.2 運轉機制

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

圖6 事例組狀態機Fig.6 State machine of event group

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

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

（1）文件輸入線程對EmptyStateSemaphore執行P操作以檢查是否存在空閑狀態的事例組：如存在則讀入新的事例數據，事例讀入結束后，轉換狀態{空閑→數據就緒}，然后對ReadyStateSemaphore執行V操作；否則等待。

（2）每個事例循環處理線程都會向全局緩沖區發出請求，緩沖區查詢映射表：若為新的線程，對ReadyState-Semaphore執行P操作，將分配的事例組轉換狀態{數據就緒→處理中}，并更新映射表和文件上下文；若為映射表中已存在的線程，則返回對應事例組中下個事例。

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

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

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

2.3 數據訪問

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

每個事例循環線程請求事例數據的流程如圖8所示，全局緩沖區首先查詢線程與事例組映射表：

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

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

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

（3）如果事例組的事例數據已經全部處理完成，則更新事例組的狀態為處理完成；向全局緩沖區請求新的事例組，如果當前沒有處于數據就緒狀態的事例組，則線程進入阻塞狀態，直到有數據就緒狀態的事例組出現。

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

（5）如果文件發生變更，則調用文件只讀服務更新文件上下文環境。

3 文件I/O

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

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

圖9 事例級并行數據服務圖Fig.9 Data service diagram of event level parallel

原始數據一般以字節流形式存儲于文件中，由文件輸入服務線程將字節流數據讀入到內存，內存中的字節流形成一個完整邏輯事例單元；字節流解包服務可以很方便地獲得各部分數據，文件輸出服務線程則按順序將邏輯事例單元寫入到指定的字節流文件中[18]。如圖10所示，在數據存儲管理器初始化后，當每個事例循環執行時，向信號管理器發送“事例開始”信號，信號管理器通過信號句柄請求事例，進而訪問全局緩沖區獲得下個事例。每個事例循環處理線程都會設置一個監視器，用于控制事例執行過程中的各個步驟，以便在事例發生錯誤和異常時及時做出響應，避免造成硬件資源的浪費。

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

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

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

4 實驗結果

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

表1 實驗環境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事例類型包括模擬、重建、物理分析，模擬用于研究高能物理實驗中各種隨機物理過程，以及物理量的統計分布，全面地反映相關物理量的統計性質。模擬作業熱點過程的實驗數據如圖12～17所示，相較于作業級并行，隨機數生成過程的序列級并行性能提升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 隨機數生成過程性能對比Fig.12 Performance contrast of random number generation

事例重建是利用相應的刻度常數對原始數據進行修正，將原始數據中的數字信號還原為粒子的位置、能量、動量等物理量，最終形成重建數據交給物理分析人員。重建作業熱點過程如圖18～21所示，相較于作業級并行，磁場求解過程的序列級并行性能提升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

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

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

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

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

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

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

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

5 結束語

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