[發明專利]多網絡環境下基于強化學習的MPI消息調度方法

有效

• 申請號: 201010148647.0
• 申請日: 2010-04-16
• 公開（公告）號: CN101833479A
• 公開（公告）日: 2010-09-15
• 發明（設計）人: 蔣艷凰;盧宇彤;趙強利;謝旻;周恩強;曹宏嘉;陳海濤;董勇;所光
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06F9/54
• 分類號: G06F9/54
• 代理公司: 國防科技大學專利服務中心 43202
• 代理人: 郭敏

1.一種多網絡環境下基于強化學習的MPI消息調度方法，其特征在于包括以下步驟：

第一步：初始化，在MPI系統啟動過程中，完成如下初始化的工作：

1.1設置消息段的最大長度seg_max：seg_max的取值范圍為1MB～64MB；

1.2設置初次發送消息段標識FIRST_SIGN＝1；

1.3設置學習率β：0≤β≤1；

1.4設置延遲回報的折扣因子γ：0≤γ≤1；

1.5構造并初始化消息段計數器：為每套網絡設置一個消息段計數器，用于記錄當前該網絡的發送隊列中的消息段數目，第i套網絡的消息段計數器數值用counter[i]表示，初始值為0；

1.6構造并初始化等待時間變量：為每套網絡設置一個變量，用于記錄當前發送至該網絡接口控制器上的消息段在發送隊列中的等待時間，第i套網絡的等待時間用wait_time[i]表示，初始值為0；為每個消息段設置一個變量用于記錄其進入某通信網絡發送隊列中的時間，消息段j的進入時間用enter_time[j]表示，用于更新等待時間的值；

1.7設置單套通信網絡的狀態數k：通信網絡的狀態用于反映該網絡的繁忙程度，取值為[0，k-1]中的整數，設置單套通信網絡的狀態數k為區間[8，32]內的整數；

1.8構造并初始化Q表：每兩套網絡生成一個Q表，第i套網絡和第j(0≤i，j≤m-1且i＜j)套網絡生成的Q表用Q_(i，j)表示，每個Q表用一個三維數組表示，前兩維分別表示兩套網絡的狀態，第三維表示可能的動作，將各Q表中的所有Q值初始化為

1.9設置并啟動發送計時器timer：設置timer＝0，并啟動該計時器；

第二步、計算隊列間隔queue_interval和時間間隔time_interval的值：

2.1根據網絡的個數m、各網絡發送隊列的最大長度queue_max和單套通信網絡的狀態數k，按如下公式確定隊列間隔queue_interval的大小：

2.2根據單套網絡的理論帶寬bandwidth和MPI系統設定的最大消息段長度seg_max，按如下公式計算時間間隔time_interval的值：

第三步、等待并行應用程序的消息發送請求：如果有未處理的消息發送請求，取出最先到達的消息請求，獲取該請求需要發送的MPI消息，將MPI消息的未發送部分的長度message_length設置為該MPI消息的長度，并設置調度結束標識FINISHED＝0，轉第四步，否則繼續等待；

第四步、獲取當前消息段：根據seg_max的值獲取當前消息段，具體如下：

4.1如果FINISHED＝1，說明該MPI消息已調度完畢，轉第三步；

4.2如果MPI消息的未發送部分的長度message_length大于seg_max，則從前至后取出長度為seg_max的一段作為當前消息段，并按如下公式更新message_length：

message_length＝message_length-seg_max

轉第4.4步；

4.3如果MPI消息的未發送部分的長度message_length小于等于seg_max，則直接將未發送部分作為當前消息段，設置調度結束標識FINISHED＝1，轉第4.4步；

4.4如果FIRST_SIGN＝1，則設置FIRST_SIGN＝0，轉第五步；否則轉第六步；

第五步、按如下方式設置當前環境狀態s_current和當前動作a_current，動作是指將當前消息段調度至m套網絡中的某一套，具體動作用所選的調度網絡的標識表示：

5.1s_current＝(0，0，…，0)；

5.2從m套通信網絡中隨機選擇一套網絡作為調度網絡，記當前動作a_current為該網絡的標識號；

5.3轉第八步；

第六步、按如下方式獲取當前環境狀態s_current和當前動作a_current：

6.1對于網絡i，0≤i≤m-1，獲取其消息段計數器counter[i]和等待時間wait_time[i]的值；

6.2令當前環境狀態為s_current＝(k₀，k₂，…，k_m-1)，其中網絡i的狀態k_i按如下公式得到：

6.3獲得當前動作a_current：對于每個可能的動作a，按如下公式計算該動作的總Q值：

Qtotal(scurrent,a)=Σ0≤i<m-10<j≤m-1i<jQ(i,j)(scurrent,a)=Σ0≤i<m-10<j≤m-1i<jQ(i,j)[ki][kj][a]]]>

其中Q_total(s_current，a)表示在當前環境狀態s_current下選擇第a套網絡作為調度網絡的總Q值，Q_(i，j)(s_current，a)表示在當前環境狀態s_current下選擇第a套網絡作為調度網絡時，Q_(i，j)表中的Q值，其對應在表中的具體值為Q_(i，j)[k_i][k_j][a]的值；當前動作a_current是所有動作中總Q值最大的動作，即：其中函數arg表示返回總Q值最大的通信網絡的標識；

第七步、更新Q值：對于表Q_(i，j)，0≤i，j≤m-1且i＜j，按如下公式更新表中“環境狀態-動作”對(s_prev，a_prev)對應的Q值：

Q_(i，j)(s_prev，a_prev)＝(1-β)·Q_(i，j)(s_prev，a_prev)+β·(r+γ·Q_(i，j)(s_current，a_current))；

第八步、將當前消息段調度至網絡a_current的發送隊列中：

8.1判定邊界條件：如果counter[a_current]≥queue_max，說明所選網絡a_current的發送隊列已滿，則持續等待，直到counter[a_current]＜queue_max；

8.2設置當前消息段的enter_time值為當前系統時間，然后將消息段調度至網絡a_current的發送隊列中；

8.3按如下方式更新網絡a_current的消息段計數器的值：

counter[a_current]＝counter[a_current]+1；

第九步、按如下公式計算當前動作a_current產生的瞬時獎賞值r，瞬時獎賞值為執行動作a_current后從環境獲得的立即回報：

r=1wait_time[acurrent]+1-4k;]]>

第十步、更新前一次的環境狀態s_prev和前一次的動作a_prev：

s_prev＝s_current；a_prev＝a_current

并轉第四步；

第十一步、如果發送計時器timer的值超過預設的值，則觸發消息段發送處理，依次檢測每套通信網絡的發送隊列，并負責將發送隊列中的消息段發送至相應的網絡接口控制器，所述預設的值為10ms～1s，具體步驟如下：

11.1設置待檢測網絡的標識為i₁＝0；

11.2檢測第i₁套網絡的發送隊列，如果發送隊列中有消息段，則轉步驟11.3，否則轉步驟11.4；

11.3如果第i₁套網絡接口控制器有可用資源，可以發送新的消息段，則按先來先服的策略取出該網絡發送隊列中最前面的消息段j，將其發送至相應的網絡接口控制器，并按如下公式更新該網絡的消息段計數器和等待時間的值：

counter[i]＝counter[i]-1

wait_time[i]=current_time-enter_time[j]time_interval]]>

然后轉步驟11.2：如果第i₁套網絡接口控制器無可用資源，則說明該網絡目前繁忙，無法發送新的消息段，轉步驟11.4；

11.4如果i₁＜m-1，則i₁＝i₁+1，轉步驟11.2，繼續檢測下一套網絡的發送隊列；否則設置發送計時器timer＝0，并啟動新一輪計時。