[發(fā)明專利]基于歷史運(yùn)行數(shù)據(jù)預(yù)測并行程序運(yùn)行時(shí)間的方法

有效

• 申請?zhí)枺?/td>: 202010323618.7
• 申請日: 2020-04-22
• 公開（公告）號: CN111522644B
• 公開（公告）日: 2023-04-07
• 發(fā)明（設(shè)計(jì)）人: 孫廣中;周文舉;孫經(jīng)緯
• 申請（專利權(quán)）人: 中國科學(xué)技術(shù)大學(xué)
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F17/17;G06F17/18;G06F18/2431;G06F18/23213;G06N20/20
• 代理公司: 北京凱特來知識產(chǎn)權(quán)代理有限公司 11260
• 代理人: 鄭立明;韓珂

1.一種基于歷史運(yùn)行數(shù)據(jù)預(yù)測并行程序運(yùn)行時(shí)間的方法，其特征在于，包括：

根據(jù)小規(guī)模歷史運(yùn)行數(shù)據(jù)使用隨機(jī)森林算法建立內(nèi)推模型，歷史運(yùn)行數(shù)據(jù)包含訓(xùn)練數(shù)據(jù)及其標(biāo)簽，其中每一個(gè)訓(xùn)練數(shù)據(jù)都包含程序輸入?yún)?shù)與對應(yīng)的處理器數(shù)目，標(biāo)簽為程序運(yùn)行時(shí)間；

對于包含了程序輸入?yún)?shù)與對應(yīng)的處理器數(shù)目的大規(guī)模待預(yù)測數(shù)據(jù)，將其中的程序輸入?yún)?shù)與內(nèi)推模型的處理器數(shù)量列表中每一組處理器組合構(gòu)成若干小規(guī)模數(shù)據(jù)，并通過內(nèi)推模型預(yù)測每個(gè)小規(guī)模數(shù)據(jù)的運(yùn)行時(shí)間；其中，訓(xùn)練數(shù)據(jù)的處理器數(shù)目的取值范圍為[a,b]，處理器數(shù)目在范圍[a,b]內(nèi)時(shí)屬于小規(guī)模數(shù)據(jù)，處理器數(shù)目在范圍(b,+∞)內(nèi)屬于大規(guī)模數(shù)據(jù)；其中，a與b分別為小規(guī)模數(shù)據(jù)中處理器數(shù)目的最小值與最大值；

根據(jù)預(yù)測得到的每個(gè)小規(guī)模數(shù)據(jù)的運(yùn)行時(shí)間，使用多任務(wù)套索回歸建立外推模型，最終預(yù)測大規(guī)模待預(yù)測數(shù)據(jù)的運(yùn)行時(shí)間；

其中，根據(jù)小規(guī)模歷史運(yùn)行數(shù)據(jù)使用隨機(jī)森林算法建立內(nèi)推模型包括：

隨機(jī)森林模型是包含多棵決策樹的模型，通過使用集成學(xué)習(xí)的方法訓(xùn)練多棵決策樹，在訓(xùn)練每棵決策樹時(shí)，從小規(guī)模歷史運(yùn)行數(shù)據(jù)中有放回的采樣，從而訓(xùn)練出隨機(jī)森林模型及參數(shù)權(quán)重W，構(gòu)成內(nèi)推模型；

根據(jù)預(yù)測得到的每個(gè)小規(guī)模數(shù)據(jù)的運(yùn)行時(shí)間，使用多任務(wù)套索回歸建立外推模型，最終預(yù)測大規(guī)模待預(yù)測數(shù)據(jù)的運(yùn)行時(shí)間包括：

對隨機(jī)森林模型的參數(shù)權(quán)重W進(jìn)行處理：參數(shù)權(quán)重W包含程序輸入?yún)?shù)和處理器數(shù)量的權(quán)重，提取其中的程序輸入?yún)?shù)的權(quán)重進(jìn)行歸一化處理得到W'，并作為聚類的距離權(quán)重；

待預(yù)測數(shù)據(jù)X_test中的每個(gè)數(shù)據(jù)都對應(yīng)一個(gè)任務(wù)，每個(gè)數(shù)據(jù)包含程序輸入?yún)?shù)與對應(yīng)的處理器數(shù)目，且每個(gè)數(shù)據(jù)都有一系列對應(yīng)的小規(guī)模數(shù)據(jù)，小規(guī)模數(shù)據(jù)的數(shù)目為處理器數(shù)量列表的大小；根據(jù)程序輸入?yún)?shù)及其權(quán)重W'對所有的任務(wù)進(jìn)行聚類，得到任務(wù)簇集合(X_c,Y_c)＝{(X_c1,Y_c1),...,(X_cK,Y_cK)}，其中，K表示聚類得到的任務(wù)簇的數(shù)目，X_ci表示第i個(gè)任務(wù)簇所包含的待預(yù)測數(shù)據(jù)X_test中的一個(gè)或多個(gè)數(shù)據(jù)，Y_ci為第i個(gè)任務(wù)簇中各個(gè)數(shù)據(jù)對應(yīng)的小規(guī)模數(shù)據(jù)的運(yùn)行時(shí)間，i＝1,...,K；

對內(nèi)推模型的處理器數(shù)量列表p-list進(jìn)行PMNF展開得到X_MTL-train作為特征，對于第i個(gè)任務(wù)簇，根據(jù)任務(wù)簇中數(shù)據(jù)對應(yīng)的小規(guī)模數(shù)據(jù)使用多任務(wù)套索回歸建立回歸模型包含了第i個(gè)任務(wù)簇所包含的每一數(shù)據(jù)中程序輸入?yún)?shù)下運(yùn)行時(shí)間和處理器數(shù)量的關(guān)系；

對任務(wù)簇集合中所有任務(wù)簇所包含數(shù)據(jù)中的處理器數(shù)目進(jìn)行PMNF展開，再結(jié)合相應(yīng)的回歸模型預(yù)測得到運(yùn)行時(shí)間y_ci，將所有任務(wù)簇的預(yù)測結(jié)果按照與大規(guī)模待預(yù)測數(shù)據(jù)X_test中程序輸入?yún)?shù)的對應(yīng)關(guān)系，重新排列，得到運(yùn)行時(shí)間的最終預(yù)測結(jié)果y_test。

2.根據(jù)權(quán)利要求1所述的一種基于歷史運(yùn)行數(shù)據(jù)預(yù)測并行程序運(yùn)行時(shí)間的方法，其特征在于，

對于大規(guī)模待預(yù)測數(shù)據(jù)X_test，將其程序輸入?yún)?shù)與內(nèi)推模型的處理器數(shù)量列表p-list中每一組處理器組合，獲得多組小規(guī)模數(shù)據(jù)X_test-exp，并通過內(nèi)推模型預(yù)測其運(yùn)行時(shí)間Y_test-exp。