[發明專利]多核分片XML并行解析方法

無效

• 申請號: 201110317045.8
• 申請日: 2011-10-18
• 公開（公告）號: CN102495722A
• 公開（公告）日: 2012-06-13
• 發明（設計）人: 唐雪飛;陳科;汪海良;李應洪
• 申請（專利權）人: 成都康賽電子科大信息技術有限責任公司
• 主分類號: G06F9/38
• 分類號: G06F9/38;G06F9/50;G06F17/30
• 代理公司: 電子科技大學專利中心 51203
• 代理人: 周永宏

1.一種多核分片XML并行解析方法，其特征在于：包括如下步驟：

第一步、構造多線程并行：

1)使用FORK-JOIN結構來描述如何創建并發線程；

2)將FORK出來的線程放入線程池，由線程池負責線程的生命周期管理；

3)在多線程環境下，采用mutex變量作為互斥信號量，實現多線程環境下的資源訪問的同步和互斥；

第二步、創建主線程，由主線程初始化全局變量，用于進行子線程同步及記錄查詢結果；

第三步、多核并行處理器分配，用于完成進程和線程到處理器節點的分配：

1)任務分配模型的建立：

設多核并行處理器包含N_node個處理節點每個處理器包含N_core個處理器核待分配的并行程序有N_proc個進程進程P_i包含M_i個線程并行程序的總線程個數

設待分配的并行程序為一個無向圖G＝(V，E)，其中V是節點的集合{V_i}，節點V_i對應一個二元組<T_i，P_i>，其中T_i是節點對應的線程號，P_i為該線程所屬的進程號；E是無向邊的集合{E_ij}；連接節點V_i和V_j的邊E_ij∈E，表示線程T_i和T_j間的通信或共享數據，邊的權值W_ij表示兩個線程通信或共享數據的頻繁程度；

2)進行兩輪操作，第一輪操作完成進程到處理節點的分配，第二輪操作完成處理節點內線程到處理器核的分配，每一輪操作包含多次迭代過程：

a)對第一輪操作，初始的任務關系圖以進程為單位進行初步劃分，第一輪操作的結束條件是圖中復合節點個數≤處理節點個數，結束時圖中每個復合節點為一個子圖，對應一個處理節點，包含在子圖中的線程分配給該處理節點；

b)對第一輪操作劃分出的每個子圖進行第二輪操作，第二輪操作的結束條件是圖中復合節點個數≤處理器核個數，結束時圖中每個復合節點對應一個處理器核，包含在其中的線程分配給該處理器核；

第四步、多核XML分片：

1)使用DOM將XML文檔載入到內存，得到XML的樹型結構；

2)對XML進行子片劃分：

采用(x，y)表示一個XML子片，其中x代表子片的起點，y代表子片的終點，定義一個空閑子片為未被處理器占用的XML子片，其中該子片中的所有結點都未被任何一個處理器或子線程處理；

3)一個子片S(x，y)和另一子片S′(x′，y′)采用以下公式進行分配：

FP(S，S′)＝max((x-x′)g(x-y)g(y-y′)g(x′-y′))

第五步、分片XML解析結果歸并：

1)分片XML解析結果統一存放：

設XML分片數為n，則采用數組part[n]對各個XML片進行存放，其中：part[i]＝第i個XML分片解析結果，0≤i＜n

2)對part[n]進行歸并。

2.根據權利要求1所述的多核分片XML并行解析方法，其特征在于：在所述FORK-JOIN結構中，一個FORK語句產生一個新的并發線程路徑，并且并發線程在其結尾使用JOIN語句；當原線程和新產生的線程都達到JOIN語句后，代碼繼續以順序的方式執行。

3.根據權利要求1所述的多核分片XML并行解析方法，其特征在于：所述互斥信號量的工作原理為：當請求一個使用mutex來表示的資源時，進程需要先讀取mutex的值，以判斷相應的資源是否可用：當mutex的值大于0時，表明有資源可以請求；等于0時，說明現在無可用資源，進程會進入睡眠狀態直至有可用資源時，當進程不再使用一個互斥信號量控制的共享資源時，mutex的值增1。

4.根據權利要求3所述的多核分片XML并行解析方法，其特征在于：對所述mutex的值進行的增減操作均為原子操作。

5.根據權利要求1所述的多核分片XML并行解析方法，其特征在于：所述全局變量至少包括信號量、子線程狀態集和結果集。