[發(fā)明專利]面向非規(guī)則數(shù)據(jù)密集應(yīng)用的群組式線程預(yù)取方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710039875.6
• 申請(qǐng)日: 2017-01-19
• 公開（公告）號(hào): CN106776047B
• 公開（公告）日: 2019-08-02
• 發(fā)明（設(shè)計(jì)）人: 黃艷;谷培培;李玉華;張啟坤;朱會(huì)東;梁樹軍;范乃梅
• 申請(qǐng)（專利權(quán)）人: 鄭州輕工業(yè)學(xué)院
• 主分類號(hào): G06F9/50
• 分類號(hào): G06F9/50;G06F9/48
• 代理公司: 鄭州優(yōu)盾知識(shí)產(chǎn)權(quán)代理有限公司 41125
• 代理人: 張真真;栗改

本發(fā)明提出了一種面向非規(guī)則數(shù)據(jù)密集應(yīng)用的群組式線程預(yù)取方法，采用在線剖析技術(shù)獲取非規(guī)則數(shù)據(jù)密集應(yīng)用的執(zhí)行時(shí)特征，確定合理的預(yù)取率構(gòu)建群組式預(yù)取線程實(shí)現(xiàn)有效數(shù)據(jù)預(yù)取，包括非規(guī)則數(shù)據(jù)訪存特征剖析、群組式預(yù)取線程構(gòu)建及線程同步機(jī)制的確立。本發(fā)明基于片上多核處理器環(huán)境中面向非規(guī)則數(shù)據(jù)密集應(yīng)用執(zhí)行數(shù)據(jù)預(yù)取，能確保及時(shí)準(zhǔn)確地發(fā)出預(yù)取請(qǐng)求，減少無用數(shù)據(jù)預(yù)取和線程之間的共享資源競爭，預(yù)取線程構(gòu)建能量消耗較低，并具有較好的實(shí)用性和靈活性。

技術(shù)領(lǐng)域

本發(fā)明涉及高性能計(jì)算的技術(shù)領(lǐng)域，具體涉及一種面向非規(guī)則數(shù)據(jù)密集應(yīng)用的群組式線程預(yù)取方法，面向非規(guī)則數(shù)據(jù)密集應(yīng)用基于共享緩存實(shí)現(xiàn)線程數(shù)據(jù)的存取。

背景技術(shù)

現(xiàn)有的數(shù)據(jù)預(yù)取方法都依賴于密集數(shù)據(jù)訪問的規(guī)律性。面向非規(guī)則數(shù)據(jù)密集應(yīng)用的群組式線程預(yù)取（Group Thread Prefetching，GTP）方法設(shè)計(jì)的主要目的是為復(fù)雜的非規(guī)律密集數(shù)據(jù)訪問提供一種有效的數(shù)據(jù)預(yù)取策略，廣泛地應(yīng)用于高性能計(jì)算與分布式計(jì)算領(lǐng)域，如信號(hào)處理程序、流體力學(xué)計(jì)算、生物信息計(jì)算、社會(huì)學(xué)統(tǒng)籌問題計(jì)算等。簡單地說，GTP方法通過在線剖析技術(shù)為非規(guī)則數(shù)據(jù)密集應(yīng)用在多核處理器環(huán)境下分析出訪存和計(jì)算延遲特征，該特征決定了輔助線程能夠隱藏的訪存延遲比例。根據(jù)訪存延遲比例分配預(yù)取數(shù)據(jù)群組，避免無用數(shù)據(jù)預(yù)取和緩存污染。

非規(guī)則數(shù)據(jù)密集應(yīng)用中通常采用復(fù)雜的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，例如鏈?zhǔn)綌?shù)據(jù)存儲(chǔ)結(jié)構(gòu)。一方面，復(fù)雜的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)使得數(shù)據(jù)訪問不具備時(shí)間局部性特征和空間局部性特征，傳統(tǒng)的硬件預(yù)取技術(shù)無法準(zhǔn)確預(yù)測預(yù)取數(shù)據(jù)地址，其有效性難以保證。另一方面，復(fù)雜的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)中，數(shù)據(jù)間常存在依賴和約束關(guān)系，傳統(tǒng)的軟件預(yù)取技術(shù)無法提前發(fā)出數(shù)據(jù)預(yù)取請(qǐng)求，難以做到及時(shí)預(yù)取。面向非規(guī)則數(shù)據(jù)密集應(yīng)用的預(yù)取技術(shù)能夠有效解除數(shù)據(jù)間的依賴和約束關(guān)系，達(dá)到有效地預(yù)取。

線程預(yù)取技術(shù)是用來隱藏多核平臺(tái)中訪存延遲的有效方法，目前已經(jīng)在數(shù)據(jù)密集應(yīng)用程序中得到了廣泛應(yīng)用。線程預(yù)取技術(shù)使用一個(gè)專門線程輔助主線程提前把數(shù)據(jù)取到高速緩存中。目前，輔助線程預(yù)取技術(shù)以提高預(yù)取準(zhǔn)確率和時(shí)效性為目的，研究的著重點(diǎn)主要集中在輔助線程構(gòu)造、輔助線程啟動(dòng)和觸發(fā)、輔助線程與主線程間的同步機(jī)制幾個(gè)方面。在面向非規(guī)則數(shù)據(jù)密集應(yīng)用時(shí)，輔助線程不能總是領(lǐng)先于主線程執(zhí)行或輔助線程領(lǐng)先于主線程執(zhí)行的太多，導(dǎo)致輔助線程不能及時(shí)地給主線程提供有用的數(shù)據(jù)。GTP方法根據(jù)輔助線程能夠隱藏的訪存延遲比例分配預(yù)取數(shù)據(jù)群組，達(dá)到盡早發(fā)出預(yù)取請(qǐng)求、避免無用數(shù)據(jù)預(yù)取和提高預(yù)取時(shí)效性的目的。

鑒于目前研究的線程預(yù)取技術(shù)，其輔助線程構(gòu)造方式不適合用于訪問依賴的非規(guī)則數(shù)據(jù)密集應(yīng)用，在現(xiàn)有的技術(shù)中還沒有面向非規(guī)則數(shù)據(jù)密集應(yīng)用的群組式線程預(yù)取方法。

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

為了解決現(xiàn)有非規(guī)則數(shù)據(jù)密集應(yīng)用中數(shù)據(jù)間的依賴性和約束性，本發(fā)明提出一種面向非規(guī)則數(shù)據(jù)密集應(yīng)用的群組式線程預(yù)取方法，基于共享緩存為非規(guī)則數(shù)據(jù)密集應(yīng)用構(gòu)建群組式預(yù)取線程，保障數(shù)據(jù)預(yù)取的有效性。

為了解決上述技術(shù)問題，本發(fā)明的技術(shù)方案是：一種面向非規(guī)則數(shù)據(jù)密集應(yīng)用的群組式線程預(yù)取方法，采用在線剖析技術(shù)獲取非規(guī)則數(shù)據(jù)密集應(yīng)用的執(zhí)行時(shí)特征，確定合理的預(yù)取率構(gòu)建群組式預(yù)取線程實(shí)現(xiàn)有效數(shù)據(jù)預(yù)取，其步驟如下：包括非規(guī)則數(shù)據(jù)訪存特征剖析、群組式預(yù)取線程構(gòu)建及線程預(yù)取中同步機(jī)制的確立；

所述非規(guī)則數(shù)據(jù)訪存特征剖析包括：

A）使用VTUNE性能分析器獲取非規(guī)則數(shù)據(jù)密集應(yīng)用的執(zhí)行行為特征；

B）使用VTUNE性能分析器獲取熱點(diǎn)循環(huán)相對(duì)延遲的計(jì)算延遲T_C、循環(huán)依賴數(shù)據(jù)訪問延遲T_dm和非循環(huán)依賴數(shù)據(jù)訪問延遲T_im值；

所述群組式預(yù)取線程構(gòu)建包括：