[發明專利]一種基于Fork/Join框架的梯級水庫群優化調度多核并行計算設計方法

在審

• 申請號: 201611005315.0
• 申請日: 2016-11-07
• 公開（公告）號: CN107015861A
• 公開（公告）日: 2017-08-04
• 發明（設計）人: 王森;馬志鵬;李善綜;張康;石赟赟;黃燕;嚴黎;陳娟;朱秋菊;鄭江麗;熊靜;劉學明;陳麗
• 申請（專利權）人: 珠江水利委員會珠江水利科學研究院
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F17/50
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于Fork/Join框架的梯級水庫群優化調度多核并行計算設計方法，其特征在于，包括以下步驟：

(1)構建Fork/Join并行框架：Fork/Join并行框架的核心繼承了“分治法”的特性，通過遞歸分割原問題，形成若干個規模更小、相互獨立且可并行計算的子問題；當各子問題進行獨立并行計算后，組合各子問題的子結果即可輸出原問題的最終結果；Fork/Join框架設計了獨特的線程池技術，當程序開始執行時，默認創建與可用的處理器數目相同的活動線程數；在“分治法”執行過程中，定義了一個可自由設置的控制子問題規模大小的閾值作為子問題規模的上限值，即當子問題規模小于或等于閾值時，“分治法”執行結束，各子問題被平均分配到不同線程中開始并行計算；另外，在子問題并行計算過程中，Fork/Join設計了獨特的雙端隊列排序模式，并采用了“工作竊取”算法，即當一個線程的隊列計算任務為空時，將從其它處于工作狀態的線程隊列尾部“竊取”計算任務；

(2)實現Fork/Join并行框架：1)算法實現的代碼類需繼承Fork/Join應用接口類java.util.concurrent.RecursiveAction或者java.util.concurrent.RecursiveTask；2)選擇閾值劃分任務；3)實現Fork/Join接口類的void compute()方法；4)設置任務劃分方式；

(3)粗粒度模式下典型智能方法并行化設計：1)并行自適應混沌整體退火遺傳算法：

Step 1參數初始化。設定種群規模m、混沌序列個數d、種群最大迭代次數Kmax、初始溫度T0以及自適應參數Pc1、Pc2、Pm1、Pm2；

Step 2種群初始化。根據Logistic映射公式，在混沌空間隨機生成n組混沌序列，映射到解空間內生成m個不同的個體構成種群，種群個體由各電站不同時段的水位值(zi1，zi2，…，zin)構成；

Step 3創建線程池，默認生成的線程池的工作線程數目與CPU邏輯線程數目相同，同時設置Fork/Join的計算閾值；

Step 4啟動并行計算流程；

Parallel Step①根據設置的計算閾值將父種群按遞歸模式劃分為多個規模更小的子種群；

Parallel Step②劃分的子種群集合平均分配到不同邏輯線程。為了保持CPU負載平衡，確保每個邏輯線程分配的子任務數相同；

Parallel Step③每個線程分配到的子種群獨立運行計算，主要計算步驟如下：

A評價個體適應度；

B選擇運算：采用整體退火選擇機制，允許父代參與競爭，并篩選出下一代個體；

C交叉運算：采用算術交叉方法執行交叉操作；

D變異運算：采用非均勻變異方式執行變異操作；

E計算父代和子代個體適應度：當父代個體Xi經過交叉、變異生成子代X′_i，若f(X′_i)＞f(X_i)，則用X′_i代替Xi；否則，以概率exp[(f(X′_i)-f(X_i))/T_k]保留Xi；

F參數更新。迭代次數k＝k+1，溫度Tk＝1/ln(k/T0+1)。

G判斷子種群迭代是否結束；根據退火溫度Tk或最大迭代次數作為收斂條件，當兩者任意其一達到初始設置的收斂條件時，返回A；否則，子種群計算收斂結束；

Parallel Step④匯總合并各子種群的優化解作為結果集，返回主線程。

Step 5從結果集中篩選出最優解，計算結束并銷毀線程池。

2)并行自適應混合粒子群算法(PAHPSO)

Step1參數初始化；

Step2種群初始化；

Step3創建線程池，默認生成的線程池的工作線程數目與CPU邏輯線程數目相同，同時設置Fork/Join的計算閾值；

Step4啟動并行計算流程；

Parallel Step①根據設置的計算閾值將父種群按遞歸模式劃分為多個規模更小的子種群；

Parallel Step②劃分的子種群集合平均分配到不同邏輯線程。為了保持CPU負載平衡，確保每個邏輯線程分配的子任務數相同；

Parallel Step③每個線程分配到的子種群獨立運行計算，主要計算步驟如下：

A計算粒子適應度、粒子個體最優解以及種群全局最優解；粒子適應度與其個體最優解比較，若粒子適應度比其個體最優解更優，則當前粒子位置作為個體最優位置；粒子適應度與種群全局最優解比較，若粒子適應度比種群全局最優解更優，則當前粒子位置作為種群全局最優位置；

B計算粒子能量以及粒子能量閾值；若粒子能量低于當前粒子能量閾值，對粒子當前位置與速度執行變異操作；

C計算粒子相似度以及粒子相似度閾值；若兩相鄰粒子相似度小于當前粒子相似度閾值，則對較差粒子的歷史最優位置執行變異操作；

D引入基于鄰域的貪心隨機搜索策略對粒子的個體最優位置進行更新；若在鄰域搜索到的當前位置比搜索前粒子適應度更大，則代替搜索前粒子個體位置，再用搜索后粒子個體位置與粒子歷史最優位置以及種群全局最優位置作比較，更新粒子歷史最優位置以及種群最優位置；

E更新粒子種群的速度和位置；

F判斷子種群迭代是否結束；若當前迭代次數小于最大迭代次數，返回(1)；否則，子種群計算收斂結束；

Parallel Step④匯總合并各子種群的計算結果作為結果集，返回主線程；

Step5從結果集中篩選出最優解，計算結束并銷毀線程池；

3)Fork/Join框架粗粒度并行設計模式及方法

根據PSCWAGA和PAHPSO方法計算流程，歸納總結Fork/Join框架粗粒度并行設計模式及方法：

Step1初始化算法參數及種群規模；

Step2創建線程池以及設置計算閾值；

Step3利用Fork/Join并行框架按遞歸模式將父種群劃分為多個子種群，并平均分配到各子線程；

Step4各子種群按原串行方法流程優化計算，直至各子種群迭代結束；

Step5匯總合并各子種群的計算結果作為結果集，返回主線程；

Step6從結果集中篩選出最優解，計算結束并銷毀線程池；

(4)細粒度模式下典型動態規劃方法并行化設計：1)并行動態規劃方法：

Step1數據準備；獲取計算所需的電站基礎屬性特征值及特征曲線，包括電站特征水位、出力系數、水位-庫容曲線、泄流-尾水位曲線等，并根據水庫各時段蓄水上下限、離散個數確定離散狀態變量St；

Step2創建線程池，默認生成的線程池的工作線程數目與CPU邏輯線程數目相同，同時設置Fork/Join的計算閾值；

Step3啟動并行計算流程；

Parallel Step①構建并行計算的父任務；將迭代周期內所有蓄水狀態變量組合在Bt(St，It，Nt)中的求解計算作為父任務，并為計算過程中水位、出力、發電量等指標創建存儲空間；

Parallel Step②根據設置的計算閾值將父任務按遞歸模式劃分為多個規模更小的子任務；

Parallel Step③劃分的子任務集合平均分配到不同邏輯線程。為了保持CPU負載平衡，確保每個邏輯線程分配的子任務數相同；

Parallel Step④每個線程分配到的子任務獨立運行計算，即子任務中的所有狀態離散組合在遞推公式中求解計算；

Parallel Step⑤匯總合并各子任務的計算結果作為結果集，返回主線程；

Step4從結果集中篩選出最優解，計算結束并銷毀線程池；

2)并行離散微分動態規劃方法：

Step1數據準備；獲取計算所需的電站基礎屬性特征值及特征曲線，包括電站特征水位、出力系數、水位-庫容曲線、泄流-尾水位曲線等，并根據水庫各時段蓄水上下限、離散個數確定離散狀態變量St；

Step2設置迭代廊道個數，并生成初始可行解作為計算初始軌跡；

Step3創建線程池，默認生成的線程池的工作線程數目與CPU邏輯線程數目相同，同時設置Fork/Join的計算閾值；

Step4選取最大廊道寬度作為當前廊道；

Step5啟動并行計算流程；

Parallel Step①在當前廊道內構建并行計算的父任務；將廊道內所有蓄水狀態變量組合在Bt(St，It，Nt)中的求解計算作為父任務，并為計算過程中水位、出力、發電量等指標創建存儲空間；

Parallel Step②根據設置的計算閾值將父任務按遞歸模式劃分為多個規模更小的子任務；

Parallel Step③劃分的子任務集合平均分配到不同邏輯線程；為了保持CPU負載平衡，確保每個邏輯線程分配的子任務數相同；

Parallel Step④每個線程分配到的子任務獨立運行計算，即子任務中的所有狀態離散組合在遞推公式中求解計算；

Parallel Step⑤匯總合并各子任務的計算結果作為結果集，返回主線程；

Step 5根據結果集輸出當前最優軌跡，并判斷當前最優軌跡是否與初始軌跡相同；若相同，則進入Step 6；若不相同，進入Step 7；

Step 6判斷當前廊道是否為最后一個廊道；若不是，設置下一個更小的廊道寬度作為當前廊道寬度，進入Step 7；若是，計算終止，輸出最優軌跡作為計算最優解并銷毀線程池；

Step 7設置當前最優軌跡作為下一次迭代的初始軌跡，返回Step 5；

3)Fork/Join框架細粒度并行設計模式及方法：

根據PDP和PDDDP方法計算流程，歸納總結Fork/Join框架細粒度并行設計模式及方法：

Step1數據準備。包括初始化參數以及設置狀態離散點數；

Step2創建線程池以及設置計算閾值；

Step3按串行流程執行直至開始計算狀態離散點組合的返回值，進入并行計算；

Step4利用Fork/Join并行框架按遞歸模式將父任務劃分為多個子任務，并平均分配到各子線程；

Step5各子任務中的狀態離散點組合按動態規劃遞推公式求解運算，直至各子任務計算結束；

Step6匯總合并各子任務的計算結果作為結果集，返回主線程；

Step7從結果集中篩選出當前最優解，并繼續按方法串行流程執行直至計算結束，并銷毀線程池。