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

有效

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

本發(fā)明公開了一種基于歷史運行數(shù)據(jù)預測并行程序運行時間的方法，針對小規(guī)模歷史運行數(shù)據(jù)預測大規(guī)模運行時間的問題，建立了使用隨機森林和多任務套索回歸的兩層模型，隨機森林可以擬合復雜的模型，而使用多任務套索回歸，將相關性強的任務放在一起訓練，可以降低內(nèi)推模型預測的隨機誤差帶來的影響。本發(fā)明提出的兩層模型相較于之前已有的簡單模型，在運行時間和程序輸入?yún)?shù)之間的關系比較復雜時不會失效，可以得到準確的預測結果。同時，兩層模型的訓練和預測不需要任何專家知識，也無需對特征進行處理，可以對整個訓練預測流程進行自動化。

技術領域

本發(fā)明涉及程序運行時間預測技術領域，尤其涉及一種基于歷史運行數(shù)據(jù)預測并行程序運行時間的方法。

背景技術

并行程序的運行時間預測在高性能計算領域發(fā)揮著重要作用。準確的預測模型可以幫助用戶更合理的申請計算資源，幫助超級計算機系統(tǒng)更高效的進行任務調(diào)度和資源分配。如何對并行程序的運行時間進行準確的預測一直是高性能計算領域的關注熱點。

目前對于并行程序運行時間的預測方法主要有以下三種：

1)基于模擬的方法通過模擬器模擬并行程序的執(zhí)行預測其運行時間。這種方法一般需要在較小規(guī)模的機器上模擬較大規(guī)模的運行情況，因此時間的開銷相對較大。雖然一些研究人員提出了如確定性重放、骨架程序等降低模擬時間開銷的技術，但是該方法的適用范圍依然受到很大限制。其主要原因是每當需要預測一個新任務時，都要對其運行情況進行模擬。因此該方法一般用于目標機器不存在的情況。

2)基于解析的方法通過對并行程序本身以及一些運行時特征進行人工分析，建立程序運行時間的解析模型。這種方法得到的模型在一定程度上兼顧了準確性和可移植性，但是這種方法對建模人員的要求非常高，為了建立一個并行程序的解析模型，通常需要數(shù)學、并行計算及并行程序本身涉及的領域等相關的專業(yè)知識。在并行計算系統(tǒng)和并行程序都越來越復雜的情況下，解析方法只適用于使用范圍較廣和使用頻率較高的特定計算核心部分。

3)基于統(tǒng)計的方法通過對并行程序的運行數(shù)據(jù)進行分析，來建立程序運行時間的模型。運行數(shù)據(jù)可以是待預測任務程序的歷史運行數(shù)據(jù)，也可以是從待預測任務程序中抽取的骨架程序，對待預測任務程序進行插樁得到的程序，基準測試程序等等的運行數(shù)據(jù)。基于統(tǒng)計的方法一般需要大量的數(shù)據(jù)，其主要開銷來自于采集合適足夠的運行數(shù)據(jù)。統(tǒng)計方法一般不需要并行程序本身涉及的相關領域的專家知識，并且模型構建后，對并行程序運行時間的預測開銷很小。

由于在實際系統(tǒng)中，用戶通常不會對運行的并行程序進行骨架程序抽取、插樁等操作，因此基于歷史運行數(shù)據(jù)的運行時間預測十分重要。在某些情況下，例如機器需要擴展，我們只有并行程序在較小規(guī)模情形下的歷史運行數(shù)據(jù)，而需要預測其在較大規(guī)模下的運行時間。目前針對這個問題一般建立一些例如線性回歸、對數(shù)回歸等較為簡單的模型，保證模型在只有小規(guī)模數(shù)據(jù)的外推(extrapolation)能力，可以對大規(guī)模的運行時間進行一定程度上的預測。其主要原因是過于復雜的模型如隨機森林，神經(jīng)網(wǎng)絡等模型在歷史運行數(shù)據(jù)樣本空間內(nèi)擬合較為復雜的函數(shù)，導致其在內(nèi)推(interpolation)即預測程序輸入在歷史運行數(shù)據(jù)樣本空間內(nèi)的運行時間時，一般可以取得很好的效果，但是當程序進行外推即輸入超出了歷史運行的數(shù)據(jù)樣本空間時，其預測準確度會很低。然而并行程序實際的運行時間和輸入之間的關系一般比較復雜，導致較為簡單的模型一般難以得到較為準確的預測結果。因此需要一種可以通過小規(guī)模歷史運行數(shù)據(jù)對大規(guī)模運行數(shù)據(jù)進行更準確地預測的模型。

發(fā)明內(nèi)容

本發(fā)明的目的是提供一種基于歷史運行數(shù)據(jù)預測并行程序運行時間的方法，可以通過小規(guī)模機器上歷史運行數(shù)據(jù)對大規(guī)模機器上運行數(shù)據(jù)進行準確地預測。

本發(fā)明的目的是通過以下技術方案實現(xiàn)的：

一種基于歷史運行數(shù)據(jù)預測并行程序運行時間的方法，包括：