[發明專利]一種批量流式計算系統參數動態配置方法

有效

• 申請號: 201910050828.0
• 申請日: 2019-01-20
• 公開（公告）號: CN109828836B
• 公開（公告）日: 2021-04-30
• 發明（設計）人: 梁毅;曾紹康;蘇醒;于澤群;梁巖德;伍佳名;丁治明
• 申請（專利權）人: 北京工業大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50;G06F9/455
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 張慧

1.一種批量流式計算系統參數動態配置方法，其特征在于：主要分為六個步驟：核心參數選取、樣本收集、模型構建、最優方案生成、在線匹配和參數優化；其中，核心參數選取在應用運行之前模擬測試；樣本收集、模型構建和最優方案生成步驟在后臺階段完成；在線匹配和參數優化步驟于在線階段完成；做如下假設：1)外部數據源的數據到達符合泊松分布；2)網絡帶寬足夠，設收集樣本的批次數的閾值Nb_max、預測函數擬合次數閾值Ct_max、種群中個體數閾值Np_max、進化次數閾值Cp_max、樣本收集周期t；具體為：

(1)核心參數選取

選取對批量流式計算系統性能影響較大的參數集合；

1.1)令核心參數集合為PC，初始化在批量流式計算系統的所有參數中篩選得到備選參數集合PA，PA＝{pa_i|1≤i≤n}；

1.2)選取低、中、高三種數據到達速率，分別表示為λ_l、λ_mid、λ_h，對于每一個pa_i∈PA，執行步驟1.2.1)～1.2.4)；

1.2.1)在pa_i取值范圍內隨機選取k個值，表示為V＝{v_j|1≤j≤k}，其余參數在缺省的情況下，分別在數據到達速率為λ_l、λ_mid、λ_h下，依次選取V中的數值v_j進行k次流式應用模擬實驗，獲取相應的數據處理響應延遲集合LL＝{ll_j|1≤j≤k}、LM＝{lm_j|1≤j≤k}、LH＝{lh_j|1≤j≤k}；

1.2.2)利用公式(1)～(3)，分別計算λ_l、λ_mid、λ_h三種數據到達速率下，pa_i與批量流式計算系統性能的皮爾森相關系數r_l、r_mid、r_h；

1.2.3)利用公式(4)計算pa_i的平均皮爾森相關系數

1.2.4)若且顯著性檢驗的p值小于0.05，則設置PC←PC∪{pa_i}；

(2)樣本收集

2.1)依據步驟(1)選取的核心參數集合PC＝{pc_i|1≤i≤N}，令樣本表S表示為S＝{s_m|s_m＝(λ_m，v_1m，v_2m，...，v_Nm，tc_m)，tc_m＝l_m-tb_m，1≤m≤D}，其中，m為樣本數據編號，D為樣本數據總數，λ_m為第m個樣本的數據到達速率，v_1m，v_2m，...，v_Nm為第m個樣本對應核心參數pc₁，pc₂，...pc_N的值，tc_m為第m個樣本的數據計算時間，是由數據處理響應延遲l_m減去批次劃分間隔tb_m得到的；

2.2)令Nb為批量流式計算系統當前收集樣本的批次數，設置Nb＝0；

2.3)從批量流式計算系統既有組件采集流式應用當前批次的數據到達速率、核心參數pc₁，pc₂，...pc_N的值、數據處理響應延遲和批次劃分間隔，分別表示為λ′、v₁′，v₂′，...，v_N′、l′、tb′；

2.4)遍歷樣本表S，若滿足λ_m＝λ′，v_1m，v_2m，...，v_Nm＝v₁′，v₂′，...，v_N′，則利用公式(5)求取兩個樣本數據計算時間的均值并設置否則，設置S←S∪{(λ′，v₁′，v₂′，...，v_N′，l′-tb′)}；

2.5)Nb←Nb+1，若Nb＝Nb_max，則執行步驟(3)；否則，執行步驟2.3)；其中，Nb_max為批量流式計算系統收集樣本的批次數的閾值；

(3)模型構建

3.1)定義訓練樣本集T，初始化定義測試樣本集F，初始化對每一個s_m∈S中的λ_m、v_1m，v_2m，...，v_Nm作Z-score標準化處理，處理后得到的數值構成新的元組(λz_m，vz_1m，vz_2m，...，vz_Nm)；對于每一個元組(λz_m，vz_1m，vz_2m，...，vz_Nm)，在(0，10]內隨機生成正整數r，若r≤8，設置T←T∪{(λz_m，vz_1m，vz_2m，...，vz_Nm)，tc_m}；否則，設置F←F∪{(λ_m，v_1m，v_2m，...，v_Nm)，tc_m}；

3.2)構建的性能模型表示為f：(λ，pc₁，pc₂，...pc_N)→tc，對T中樣本(x₁，y₁)，(x₂，y₂)，...，(x_|T|，y_|T|)，x_i＝(λz_i，vz_1i，vz_2i，...，vz_Ni)(1≤i≤|T|)，y_i＝tc_i(1≤i≤|T|)，設回歸函數為式(6)；其中，w和b是待確定的參數，φ(x)表示一個非線性變換，令Ct為性能模型當前訓練次數，設置Ct←0；

f(x)＝w^Tφ(x)+b (6)

3.3)利用支持向量回歸方法解決回歸預測問題，等價于求解式(7)，

其中，C為大于0的常數，ξ_i、ξ_i^*為松弛變量；利用拉格朗日函數和對偶原理，可以得到式(8)的對偶問題，

其中，Q_i，j＝φ^T(x_i)φ(x_j)，I＝[1，...，1]^T，α、α^*為拉格朗日乘子；求解此二次型規劃可求得α的值，同時求得

利用KKT(Karush-Kuhn-Tucker)條件計算出常值偏差b，即

根據上述推導可得回歸函數f(x)的表達式為式(11)，

其中，K(x，x_i)＝φ^T(x)φ(x_i)為一個核函數；利用式(12)徑向基函數核函數實現；

K(x_i，x_j)＝exp(-γ||x_i-x_j||²)，γ＞0 (12)

3.4)對F中樣本，(x₁，y₁)，(x₂，y₂)，...，(x_|F|，y_|F|)，x_l＝(λ_l，v_1l，v_2l，...，v_Nl)(1≤l≤|F|)，y_l＝tc_l(1≤l≤|F|)，利用公式(13)計算平均誤差

3.5)若則模型構建成功，執行步驟4.1)；否則，執行步驟3.7)；

3.6)Ct←Ct+1，若Ct＞Ct_max，則構建失敗，執行步驟(7)；否則，執行步驟3.7)；其中，Ct_max為預測函數擬合次數閾值；

3.7)調整核函數參數γ，設置f(x)中γ←0.9γ，執行步驟3.4)；

(4)最優方案生成

4.1)令性能預測表為R，初始化令最優參數配置方案表為B，初始化

4.2)令流式應用的數據到達速率最小值為λ_l，最大值為λ_h，選取速率步長為step_λ，則選取的離散化數據到達速率集合如式(14)；

4.3)對核心參數集合PC＝{pc_i|1≤i≤N}中每一個pc_i，令參數取值范圍為[dl_i，dh_i]，選取步長step_i，則選取的核心參數pc_i的離散化取值集合如式(15)；

4.4)對于每一個λ_i∈Λ，遍歷所有的核心參數取值的組合形如d₁，d₂，...，d_N(d_i∈D_i)，利用步驟(3)構建的性能模型求取在該核心參數設置下的數據處理時間設置

4.5)給定數據到達速率，生成最優參數配置方案的目標函數可被定義如公式(16)；其中約束條件定義為處理響應延遲限制，tb為批次劃分間隔；

min(tb+tc)

s.t.tc≤tb≤1.2tc (16)

4.6)利用遺傳算法，對于每一個選取的數據到達速率離散值λ_i∈Λ；

(5)在線匹配

5.1)定義參數配置方案為C，初始化

5.2)當批量流式計算應用的一個批次結束后，從既有組件采集數據到達速率λ_c；

5.3)令λ_c除以step_λ向下取整的值為v，令u＝λ_c％step_λ，其中step_λ為數據到達速率選取步長；利用公式(19)，將λ_c映射到離散值λ_d；

5.4)若b_i＝(λ_i，b_1i，b_2i，...，b_Ni)滿足λ_i＝λ_d，C←(b_1i，b_2i，...，b_Ni)；否則，執行步驟(7)；

(6)參數優化

6.1)依據參數配置方案C＝(b_1i，b_2i，...，b_Ni)，對元組中每一個b_ni(1≤n≤N)，從批量流式系統相應組件中更新核心參數pc_n的值為b_ni；

(7)回溯：判斷應用程序是否結束，是則跳轉至步驟(8)；否則判斷是否時間達到樣本收集周期t，是則跳轉至步驟2.2)，否則跳轉至步驟(5)；

(8)結束：中止對批量流式系統的參數動態配置。

2.如權利要求1所述批量流式計算系統參數動態配置方法，其特征在于：4.6)具體為：

4.6.1)定義種群個體p_k＝(g_1k，g_2k，...，g_Nk)，其中g_ik表示為一個基因，則每個個體即一條染色體共有N個基因，定義種群集合P，初始化定義當前種群中個體數Np，初始化Np←0，定義當前進化次數Cp，初始化Cp←0；

4.6.2)若滿足λ_m＝λ_i，編碼d_1m，d_2m，...，d_Nm為染色體ch＝(d_1m，d_2m，...，d_Nm)，設置P←P∪{ch}；

4.6.3)Np←Np+1，若Np＝Np_max，則初始化種群結束，執行步驟4.6.4)；否則，繼續添加個體，執行步驟4.6.2)；其中，Np_max為初始種群中個體數閾值；

4.6.4)對于每一個p_k∈P，遍歷性能預測表R，若滿足d_1m＝g_1k，d_2m＝g_2k，...，d_Nm＝g_Nk，定義利用公式(17)，計算該個體的適應度；

4.6.5)定義備選父母集合為PT，初始化對P按個體適應度由大到小排列，選取適應度排名前50％的個體組成P′，設置PT←P′，P←P-P′；

4.6.6)在PT中隨機選擇兩個個體ft、mt作為父母，于[1，N]內隨機生成正整數c，然后選取ft中基因下標1至c的基因，在mt中自下標c+1開始從左至右選取所有的基因，將其組合為子代sn的基因，sn表示為式(18)，其中，sg_i為sn第i位基因，fg_i為ft第i位基因，mg_i為mt第i位基因；

sn＝(sg₁，sg₂，...，sg_N)

4.6.7)在[1，N]內隨機生成正整數t，再于[1，100]內隨機生成正整數pm，若pm≤15，則對于sn的基因sg_t，將其替換為相應參數合理取值范圍的任意值μ，即設置sg_t←μ；

4.6.8)P←P∪{sn}，若|P|＝Np_max，執行步驟4.6.9)；否則，執行步驟4.6.6)；

4.6.9)Cp←Cp+1，若Cp＝Cp_max，執行步驟4.6.10)；否則，執行步驟4.6.5)；其中，Cp_max為進化次數閾值；

4.6.10)定義best為P中適應度最大的個體，設置B←B∪{(λ_i，best)}。