[發(fā)明專利]用于將非串并行控制流圖轉(zhuǎn)換為數(shù)據(jù)流的方法和設(shè)備

在審

• 申請(qǐng)?zhí)枺?/td>: 201811344350.4
• 申請(qǐng)日: 2018-11-13
• 公開(kāi)（公告）號(hào): CN109947427A
• 公開(kāi)（公告）日: 2019-06-28
• 發(fā)明（設(shè)計(jì)）人: Y·張
• 申請(qǐng)（專利權(quán)）人: 英特爾公司
• 主分類號(hào): G06F8/41
• 分類號(hào): G06F8/41
• 代理公司: 上海專利商標(biāo)事務(wù)所有限公司 31100
• 代理人: 李煒;黃嵩泉

本申請(qǐng)?zhí)峁┝擞糜趯⒎谴⑿锌刂屏鲌D轉(zhuǎn)換為數(shù)據(jù)流的方法和設(shè)備。用于將非串并行控制流圖轉(zhuǎn)換為數(shù)據(jù)流的方法和設(shè)備示例設(shè)備包括：節(jié)點(diǎn)分析器，該節(jié)點(diǎn)分析器用于檢測(cè)序列化代碼中的非串并行節(jié)點(diǎn)；以及指令生成器，該指令生成器用于：生成包括消耗操作數(shù)的、針對(duì)與檢測(cè)到的非串并行節(jié)點(diǎn)相關(guān)聯(lián)的在先節(jié)點(diǎn)的指令；生成用于組合針對(duì)在先節(jié)點(diǎn)生成的指令的結(jié)果的組合指令；并且輸出組合指令和針對(duì)在先節(jié)點(diǎn)生成的指令，以便生成數(shù)據(jù)流代碼。

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

本公開(kāi)總體上涉及計(jì)算系統(tǒng)中的編譯器，并且更具體地，涉及通過(guò)將非串并行控制流圖轉(zhuǎn)換為數(shù)據(jù)流來(lái)提高計(jì)算系統(tǒng)中的編譯器效率的方法和設(shè)備。

背景技術(shù)

許多計(jì)算系統(tǒng)根據(jù)控制流架構(gòu)來(lái)操作。在控制流架構(gòu)中，程序的指令的執(zhí)行由程序計(jì)數(shù)器驅(qū)動(dòng)，該程序計(jì)數(shù)器逐步遍歷程序的指令。換句話說(shuō)，程序的指令的執(zhí)行順序由程序本身的結(jié)構(gòu)限定。在一些情況下，當(dāng)試圖實(shí)現(xiàn)并行處理時(shí)，控制流架構(gòu)可能不恰當(dāng)?shù)夭僮?。例如，即使指令的輸?例如，操作數(shù))尚未由并行操作指令更新，程序也可以聲明要執(zhí)行該指令。

一些計(jì)算系統(tǒng)利用數(shù)據(jù)流架構(gòu)。數(shù)據(jù)流架構(gòu)不是由程序限定的指令執(zhí)行順序驅(qū)動(dòng)的。替代地，數(shù)據(jù)流架構(gòu)根據(jù)指令的輸入(例如，操作數(shù))的可用性來(lái)執(zhí)行指令。例如，如果指令具有三個(gè)操作數(shù)，則一旦通過(guò)該指令所依賴的其他(多條)指令將這三個(gè)操作數(shù)提供給該指令，則利用數(shù)據(jù)流架構(gòu)的計(jì)算系統(tǒng)將執(zhí)行該指令。因此，數(shù)據(jù)流架構(gòu)可以在高度并行的環(huán)境中執(zhí)行，而不用擔(dān)心指令將在該指令的數(shù)據(jù)依賴性被更新/滿足之前執(zhí)行。例如，數(shù)據(jù)流架構(gòu)可以用在大規(guī)模計(jì)算系統(tǒng)中，該大規(guī)模計(jì)算系統(tǒng)使用大量處理元件使處理高度并行化。

附圖說(shuō)明

圖1是用于將控制流代碼轉(zhuǎn)換為數(shù)據(jù)流代碼的示例系統(tǒng)的框圖。

圖2是圖1的非串并行轉(zhuǎn)換器的示例實(shí)現(xiàn)的框圖。

圖3圖示了串并行的示例控制流圖。

圖4圖示了包括非串并行的節(jié)點(diǎn)的示例控制流圖。

圖5是表示用于實(shí)現(xiàn)圖3和/或圖4的非串并行轉(zhuǎn)換器的示例機(jī)器可讀指令的流程圖。

圖6是可以執(zhí)行圖5的指令來(lái)實(shí)現(xiàn)圖3和/或圖4的非串并行轉(zhuǎn)換器的示例處理設(shè)備的框圖。

附圖不按比例繪制。如在本專利中所使用，記載任何部件(例如，層、膜、區(qū)域或板)以任何方式定位在(例如，定位在、位于、設(shè)置在或形成在等)另一部件上指示被引用部件與該另一部件接觸，或者被引用部件在該另一部件上方并且一個(gè)或多個(gè)中間部件位于該被引用部件與該另一部件之間。記載任何部件與另一部件接觸意味著這兩個(gè)部件之間沒(méi)有中間部件。

具體實(shí)施方式

串并行圖廣泛用于應(yīng)用工程和算法研究理論。如果圖是串并行圖，則能在線性時(shí)間內(nèi)解決一般是NP完全問(wèn)題(NP-Complete)的一些圖問(wèn)題。已經(jīng)開(kāi)發(fā)了高度高效的算法來(lái)生成用于作為串并行圖的控制流圖的高度并行的數(shù)據(jù)流代碼。

如果有向圖G可以通過(guò)以下操作的順序產(chǎn)生，則該有向圖G是兩端串并行的，且具有端點(diǎn)s和t：

1.創(chuàng)建新圖，該新圖由從s指向t的單個(gè)邊組成。

2.給定兩個(gè)兩端串并行圖X和Y，具有端點(diǎn)sX、tX、sY和tY，通過(guò)標(biāo)識(shí)s＝sX＝sY和t＝tX＝tY來(lái)形成新圖G＝P(X，Y)。這被稱為X和Y的并行組合。

3.給定兩個(gè)兩端串并行圖X和Y，具有端點(diǎn)sX、tX、sY和tY，通過(guò)標(biāo)識(shí)s＝sX、tX＝sY和t＝tY來(lái)形成新圖G＝S(X，Y)。這被稱為X和Y的串行組合。

如果對(duì)于無(wú)向圖的邊緣的一些取向，該無(wú)向圖形成具有端點(diǎn)s和t的有向的兩端串并行圖，則該無(wú)向圖是具有端點(diǎn)s和t的兩端串并行。如果對(duì)于某兩個(gè)頂點(diǎn)s和t，有向或無(wú)向是具有這兩個(gè)那些端點(diǎn)的兩端串并行，則該有向圖或無(wú)向圖是串并行的。