• / 20
  • 下載費用:30 金幣  

程序指令序列中的分支匯聚的確定.pdf

摘要
申請專利號:

CN201610406030.1

申請日:

2016.06.08

公開號:

CN106257412A

公開日:

2016.12.28

當前法律狀態:

實審

有效性:

審中

法律詳情: 實質審查的生效IPC(主分類):G06F 9/38申請日:20160608|||公開
IPC分類號: G06F9/38 主分類號: G06F9/38
申請人: ARM 有限公司
發明人: 默罕默德·賈韋德·阿布沙; 馬爾科·柯尼路; 喬治亞·科韋利; 卡爾·艾瑞克·休伯特·文·普拉滕
地址: 英國劍橋
優先權: 2015.06.18 EP 15386020.0
專利代理機構: 北京東方億思知識產權代理有限責任公司 11258 代理人: 林強
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201610406030.1

授權公告號:

|||

法律狀態公告日:

2018.07.06|||2016.12.28

法律狀態類型:

實質審查的生效|||公開

摘要

本申請涉及程序指令序列中的分支匯聚的確定。公開了一種對程序指令序列進行編譯的方法、對程序指令序列進行并行運行的方法、以及支持這些方法的裝置和軟件。程序指令序列以形成控制流圖的基本塊為單位被分析,并且穿越該控制流圖的運行路徑被識別。當不止一個運行路徑導向給定基本塊時或者循環路徑被發現從給定基本塊導向返回同一基本塊時,潛在匯聚點可以被識別出。匯聚標記與按照這種方式識別出的基本塊相關聯地被添加到計算機程序,于是當該程序被運行時,所發現的匯聚標記被用于觸發對多個運行線程中在匯聚標記后運行的子集的確定。

權利要求書

1.一種對程序指令序列進行編譯以生成被編譯的程序的方法,包括:
識別程序指令的基本塊,其中每個基本塊只具有一個入口點和一個出口點;
確定導向每個基本塊的至少一個運行路徑;
當不止一個運行路徑導向選定基本塊時,向所述被編譯的程序添加與所述選定基本塊
相關聯的匯聚標記;以及
當存在從另一選定基本塊到該另一選定基本塊的循環路徑時,向所述被編譯的程序添
加與所述循環路徑的各個出口基本塊相關聯的匯聚標記。
2.根據權利要求1所述的方法,其中確定步驟包括:
迭代地處理路徑項目的隊列,其中每個路徑項目包括至少一個基本塊的標志,并且每
個迭代步驟包括:
從所述隊列中的第一位置移除先有路徑項目;以及
生成包括被附加有另一基本塊的標志的先有路徑項目的路徑項目,其中運行路徑從所
述至少一個基本塊導向所述另一基本塊。
3.根據權利要求2所述的方法,還包括:
將所述路徑項目添加到所述隊列中的選定位置,從而使得所述隊列中的路徑項目是相
對于每個路徑項目中的最后的基本塊而按照程序計數器次序被排序的。
4.根據權利要求3所述的方法,其中當所述路徑項目被添加為不是所述排序中的第一
路徑項目時,與所述另一基本塊相關聯的匯聚標記被添加到所述被編譯的程序。
5.根據權利要求2所述的方法,其中每個迭代步驟包括:
當另一運行路徑從所述至少一個基本塊導向第二另一基本塊時,向所述隊列添加另一
路徑項目,
其中,所述另一路徑項目包括被附加有所述第二另一基本塊的標志的先有路徑項目。
6.根據權利要求2所述的方法,還包括:
當所述隊列中的另一先有路徑項目包括所述另一基本塊的標志時,將所述另一先有路
徑項目修改為指示到所述另一基本塊的替代路徑;以及
向所述被編譯的程序添加與所述另一基本塊相關聯的匯聚標記。
7.根據權利要求2所述的方法,其中當所述先有路徑項目包括所述另一基本塊的標志
時,所述路徑項目為循環路徑。
8.根據權利要求7所述的方法,還包括:
當所述先有路徑項目包括所述另一基本塊的標志時,迭代地處理此路徑項目中的每個
基本塊,并且在每個迭代步驟中,當路徑從正被處理的、退出所述循環路徑的基本塊導出
時,向所述被編譯的程序添加與所述正被處理的基本塊相關聯的匯聚標記。
9.根據權利要求1所述的方法,其中向所述被編譯的程序添加與所述選定基本塊相關
聯的匯聚標記包括:將所述匯聚標記添加在緊接在所述選定基本塊之前。
10.根據權利要求1所述的方法,其中向所述被編譯的程序添加與所述循環路徑的各個
出口基本塊相關聯的匯聚標記包括:將所述匯聚標記添加在緊接在每個出口基本塊之前。
11.一種對程序指令序列進行編譯以生成被編譯的程序的裝置,其中所述裝置具有用
于執行權利要求1所述的方法的配置。
12.一種存儲有計算機程序的計算機可讀存儲介質,該計算機程序當在計算機上運行
時使得所述計算機執行權利要求1所述的方法。
13.一種當在計算機上運行時使得所述計算機執行權利要求1所述的方法的軟件。
14.一種利用多個運行線程并行運行計算機程序的方法,其中所述計算機程序包括程
序指令序列,所述方法包括:
識別程序指令的基本塊,其中每個基本塊只具有一個入口點和一個出口點;
確定導向每個基本塊的至少一個運行路徑;
當不止一個運行路徑導向選定基本塊時,向所述計算機程序添加與所述選定基本塊相
關聯的匯聚標記;以及
當存在從另一選定基本塊到該另一限定基本塊的循環路徑時,向所述計算機程序添加
與所述循環路徑的各個出口基本塊相關聯的匯聚標記;以及
運行所述多個運行線程,其中,運行所述多個運行線程包括:
當所述多個運行線程的第一子集從分叉基本塊采取第一運行路徑并且所述多個運行
線程的第二子集從所述分叉基本塊采取第二運行路徑時,使得所述第二子集等待;并且
當遇到所述匯聚標記時,根據預定并行運行規則來選擇所述多個運行線程中的至少一
個線程以供運行。
15.根據權利要求14所述的方法,其中根據預定并行運行規則來選擇所述多個運行線
程中的至少一個線程以供運行包括:選擇這樣的一組線程,其中針對該組線程中的線程要
執行的下一指令在程序計數器順序中是最早的。
16.一種并行運行計算機程序的裝置,其中,所述裝置具有用于執行權利要求14所述的
方法的配置。
17.根據權利要求16所述的裝置,其中所述裝置是圖形處理單元。
18.一種存儲有計算機程序的計算機可讀存儲介質,該計算機程序當在計算機上運行
時使得所述計算機執行權利要求14所述的方法。

說明書

程序指令序列中的分支匯聚的確定

技術領域

本公開涉及數據處理領域。更具體地,本公開涉及程序指令序列中的分支匯聚的
確定。

背景技術

供數據處理裝置運行的一組程序指令可能不只導致以簡單線性的方式運行,即,
其中程序指令按照順序次序從序列中的第一指令運行到序列中的最后一個指令。這是因為
各程序指令中設置的條件可能使得程序流從序列中的給定程序指令發生到另一程序指令
的分支,或者在序列中跳躍前進,或者后退到序列中的在前程序指令。在程序指令序列的運
行中的這些可能分支或循環在能夠執行多個線程(這多個線程運行相同的核)的數據處理
裝置的環境中是特別重要的,因為以鎖步的方式執行這些并行的線程可以得到性能益處,
從而使得數據處理裝置的資源得以更有效地利用。然而,當這些線程由于各個線程的不同
條件導致這些線程采用不同分支而發生分叉時,會失去這種并行性。然而,可能存在分開的
線程再次會聚到一起的點,從而再次獲得通過并行鎖步運行而改善性能的機會。本公開涉
及對這種匯聚點的識別。

發明內容

本技術的至少一些實施例提供了一種對程序指令序列進行編譯以生成經編譯的
程序的方法,包括:識別程序指令的基本塊,其中每個基本塊只具有一個入口點和一個出口
點;確定導向每個基本塊的至少一個運行路徑;當不止一個運行路徑導向選定基本塊時,向
該被編譯的程序添加與選定基本塊相關聯的匯聚標記;以及當存在從另一選定基本塊到該
另一選定基本塊的循環路徑時,向該被編譯的程序添加與循環路徑的各個出口基本塊相關
聯的匯聚標記。

本技術的至少一些實施例提供了一種對程序指令序列進行編譯以生成經編譯的
程序的裝置,其中該裝置具有用于執行上述對程序指令序列進行編譯的方法的配置。

本技術的至少一些實施例提供了一種計算機可讀存儲介質,該算機可讀存儲介質
存儲有計算機程序,該計算機程序當在計算機上運行時使得計算機執行上述對程序指令序
列進行編譯的方法。

本技術的至少一些實施例提供了一種軟件,該軟件當在計算機上運行時使得計算
機執行上述對程序指令序列進行編譯的方法。

本技術的至少一些實施例提供了一種利用多個運行線程并行運行計算機程序的
方法,其中計算機程序包括程序指令序列,所述方法包括:識別程序指令的基本塊,其中每
個基本塊只具有一個入口點和一個出口點;確定導向每個基本塊的至少一個運行路徑;當
不止一個運行路徑導向選定基本塊時,向所述計算機程序添加與選定基本塊相關聯的匯聚
標記;以及當存在從另一選定基本塊到該另一選定基本塊的循環路徑時,向所述計算機程
序添加與循環路徑的每個出口基本塊相關聯的匯聚標記;以及運行所述多個運行線程,其
中,運行所述多個運行線程包括:當多個運行線程的第一子集從分叉基本塊采取第一運行
路徑并且多個運行線程的第二子集從所述分叉基本塊采取第二運行路徑時,使得第二子集
等待;并且當遇到匯聚標記時,根據預定并行運行規則來選擇多個運行線程中的至少一個
線程以供運行。

本技術的至少一些實施例提供了一種并行運行計算機程序的裝置,其中,所述裝
置具有用于執行上述利用多個運行線程并行運行計算機程序的方法的配置。

本技術的至少一些實施例提供了一種計算機可讀存儲介質,所述計算機可讀存儲
介質存儲有計算機程序,該計算機程序當在計算機上運行時使得所述計算機執行上述利用
多個運行線程并行運行計算機程序的方法。

本技術的至少一些實施例提供了一種軟件,該軟件當在計算機上運行時使得計算
機執行上述利用多個運行線程并行運行計算機程序的方法。

附圖說明

將參考附圖中示出的那些實施例僅通過示例的方式進一步描述本技術,其中:

圖1示意性地示出一個實施例中包括CPU和GPU的裝置;

圖2是示出在一個實施例中當CPU被用于對源程序進行編譯以供以并行運行的方
式被GPU運行時所執行的步驟序列的流程圖;

圖3A示出示例程序指令序列的結構;

圖3B示出圖3A中所示程序指令序列的控制流圖(CFG);

圖3C以并行運行的四個線程的示例運行路徑示出圖3B的CFG;

圖4A示出圖3B的CFG;

圖4B示出一個實施例中當確定圖3A的程序指令序列中的匯聚點時使用的優先級
隊列的演變;

圖5示出一個實施例中當利用優先級隊列來確定程序指令隊列中的匯聚點時在方
法中所采取的步驟序列;

圖6示出一個實施例中當運行已經在一個實施例的編譯階段添加了匯聚標記的經
編譯的程序時所采取的步驟序列;以及

圖7示意性地示出一個實施例中既支持編譯又支持運行的通用計算設備。

具體實施方式

至少一些實施例提供了一種對程序指令序列進行編譯以生成經編譯的程序的方
法,包括:識別程序指令的基本塊,其中每個基本塊只具有一個入口點和一個出口點;確定
導向每個基本塊的至少一個運行路徑;當不止一個運行路徑導向所選基本塊時,向該被編
譯的程序添加與所選基本塊相關聯的匯聚標記;以及當存在從另一所選基本塊到該另一所
選基本塊的循環路徑時,向該被編譯的程序添加與循環路徑的各個出口基本塊(exit
basic block)相關聯的匯聚標記。

一種用于找到程序指令序列中的匯聚點的技術利用了直接后支配者(immediate
post-dominator)技術,藉由該技術,程序指令的基本塊(即,不包含分支可能性的指令集)
首先被識別出,因為這些基本塊只具有一個入口點和一個出口點,從而這些基本塊被表示
在控制流圖中。于是,直到存在與后續指令運行偏離的機會的指令的指令序列可以被分組
到一起,隨后新的基本塊必須開始。如果從控制流圖中的節點N到該圖的出口節點的所有路
徑必須經過Z,那么稱為節點Z后支配節點N。節點N的直接后支配者是節點N的不對N的任何
其他嚴格后支配者進行嚴格后支配的后支配者。本技術認識到雖然這樣的直接后支配者表
示該控制流圖中的可能匯聚點,實際上直接后支配者方法是一種可能忽略了產生于不規則
嵌套(nesting)和控制流的一些匯聚點的方法,因此可能失去對執行程序指令的多個線程
進行有效并行運行的機會。本技術通過識別不止一個運行路徑導向到的基本塊并且在控制
流內向該點添加匯聚標記而解決了此問題。此外,形成循環的那些運行路徑被識別出,并且
匯聚標記被添加到沿著該循環路徑的存在退出該循環路徑的可能性的每個基本塊。本技術
識別出了可能被直接后支配者技術遺漏的匯聚點,因此支持多個線程的改進的并行運行,
其中匯聚點在運行中被用以再評估哪些線程應與另一線程并行運行,從而以便使得數據處
理裝置的資源得以有效利用。應注意,與基本塊相關聯的匯聚標記的添加可以按照許多方
式來實現:標記可以被添加在基本塊內;被添加在基本塊之前的位置,等等,只要運行經編
譯的程序的裝置理解標記與哪個基本塊相關聯即可。

上述識別與程序指令序列相關聯的控制流圖中的匯聚點可以以多種方式來提供,
但是在一些實施例中,確定步驟包括:迭代地處理路徑項目的隊列,其中每個路徑項目包括
關于至少一個基本塊的標志(indication),并且每個迭代步驟包括:從隊列中的第一位置
移除先有路徑項目;以及生成包括被附加了關于另一基本塊的標志的先有路徑項目的路徑
項目,其中運行路徑從至少一個基本塊導向另一基本塊。

因此,為了處理程序指令的基本塊,即相應控制流圖的節點,本技術提出利用路徑
項目的隊列(有時被稱為優先級隊列),該隊列根據基本塊的標志進行構建的。一種迭代處
理過程被提供,其中,從控制流圖的第一入口點起,路徑項目被添加到隊列,其中路徑項目
最初包括關于控制流圖的入口基本塊(entry basic block)的簡單標志,并且被附加了控
制流圖內運行路徑從隊列中已經存在的路徑項目導向到的另外的基本塊的標志。因此,一
種迭代處理被建立,其中隊列中的路徑項目通過添加形成運行路徑的基本塊的標志而生
長。當來自某基本塊的分支導向不止一個基本塊時,即該基本塊后有不止一個運行路徑時,
另外的路徑項目可以添加到隊列。在每次迭代中,現存路徑項目被從優先級隊列取出,特別
是從隊列中的“第一位置”取出,其中應理解此“第一位置”可以通過隊列的任何預定排序給
定,只要這種排序被保持,并且基于剛從隊列移除的路徑項目(通過在此路徑項目上附加關
于運行路徑從該移除的路徑項目導向到的基本塊的標志),來生成新的路徑項目。因此,這
使得路徑項目隊列得以發展,從而表示程序指令序列中的每個可能運行路徑。

在一些實施例中,該方法還包括:將路徑項目添加到隊列中的所選位置,使得隊列
中的路徑項目按照相對于每個路徑項目中的最后的基本塊的程序計數器順序進行排序。因
此,這使得隊列按優先級排序,從而使得表示穿過程序指令序列間的運行路徑的路徑項目
被排序,進而使得程序計數器順序被遵照。這還對應于由運行經編譯的程序的裝置用來在
線程間選擇要運行的線程的優先級排序。

本技術還認識到路徑項目在隊列中被構建的順序對于識別被編譯的程序內的匯
聚點是很重要的,并且在一些實施例中,當該路徑項目被添加為不是排序中的第一路徑項
目時,與另一基本塊相關聯地匯聚標記被添加到該被編譯的程序。因此,路徑項目以使得其
不被放置于該隊列的排序中的第一位置的基本塊結束,因為隊列中的另一路徑項目具有在
程序計數器順序中來得較早的基本塊(例如,如通過參考每個基本塊的最后程序指令所確
定的),于是本技術認識到正被添加的路徑項目(不在第一位置)表示潛在的匯聚,因為跟隨
另一運行路徑的線程可能在跟隨此運行路徑的線程之前運行,因此這些線程之間可能匯
聚。因此,匯聚標記還與此另一基本塊(即,在此次迭代中被附加到該路徑項目的基本塊)相
關聯,從而使得這里的可能匯聚能夠被利用。

在一些實施例中,每個迭代步驟包括:當另一運行路徑從至少一個基本塊導向第
二另一基本塊時,向隊列添加另一路徑項目,其中另一路徑項目包括被附加有關于第二另
一基本塊的標志的先有路徑項目。因此,當不止一個運行路徑從基本塊導出(例如,導向該
另一基本塊以及導向第二另一基本塊)時,迭代步驟向隊列添加與此另一運行路徑相應的
另外的(另一)路徑項目。因為在第一路徑項目的情況中,此另一路徑項目于是表示一連串
基本塊導向正被考慮的基本塊,并然后導向此另一運行路徑導向到的第二另一基本塊。換
句話說,該方法當迭代地處理隊列時遇到基本塊的情況中(其中該基本塊(通過分支)具有
可能導向到不止一個另一基本塊的運行路徑),相應路徑項目于是被添加到隊列,相應路徑
項目表示程序指令序列中到分支的每個可能目標的運行路徑。

在一些實施例中,該方法還包括:當隊列中的另一先有路徑項目包括另一基本塊
的標志時,將另一先有路徑項目修改為指示到該另一基本塊的替代路徑;以及向被編譯的
程序添加與該另一基本塊相關聯的匯聚標記。因此,處理隊列的迭代過程可以識別隊列中
已有的另一路徑項目(另一先有路徑項目),該另一先有路徑項目已經表示出到另一基本塊
(即,到通過此迭代步驟當前正構建的運行路徑所到達的基本塊)的可能運行路徑。換句話
說,在此迭代步驟,該方法已經識別出導向同一基本塊的兩個可能運行路徑。在此情形中,
隊列中現存的路徑項目(另一先有路徑項目)于是被修改為指示到該另一基本塊的替代路
徑,此外本文中認識到此另一基本塊于是表示控制流圖中的匯聚點,因此與此另一基本塊
相關聯地匯聚標記被添加到被編譯的程序。如上所示,匯聚標記可以被添加到另一基本塊
本身,或者例如被添加到該另一基本塊前面的基本塊的末端,或者被添加到適于所意欲的
對此被編譯的程序的運行的另一位置,從而使得于是可以由運行電路執行對多個運行線程
中的哪些群組此時應當彼此并行運行的適當的重新評估。

可能存在從給定基本塊識別出導向已經存在于隊列中已有的另一路徑項目中的
基本塊的運行路徑的情況,換句話說可能識別出循環。因此,在一些實施例中,當先有路徑
項目包括該另一基本塊的標志時,該路徑項目為循環路徑。因此,在迭代處理中可以通過此
機制來識別循環路徑,并且如上所述,于是可以向被編譯的程序添加與此循環路徑的各個
出口基本塊相關聯的匯聚標記。

在這些實施例中,從循環路徑中識別出口基本塊可以通過各種方式來提供,但是
在一些實施例中,該方法還包括:當先有路徑項目包括另一基本塊的標志時,迭代地處理此
路徑項目中的每個基本塊,并且在每個迭代步驟中,當路徑從正被處理的退出循環路徑的
基本塊導出時,向被編譯的程序添加與正被處理的基本塊相關聯的匯聚標記。此循環路徑
的出口點因此得以有效地被識別出并且被標記以匯聚標記。

如上所示,向被編譯的程序添加匯聚標記可以包括在不同的具體位置添加匯聚標
記,這依賴于將執行被編譯的程序的裝置如何使用匯聚標記的具體要求,但是在一些實施
例中,向被編譯的程序添加與所選基本塊相關聯的匯聚標記包括將匯聚標記添加于緊接在
所選基本塊之前。因此,運行被編譯的程序的裝置于是會緊接在運行(被編譯的)程序指令
的所選基本塊前遇到匯聚點(本發明已經認識到此處很可能發生匯聚)。因此,這表示運行
裝置再評估哪些線程現在應當并行運行的有利點,從而有效利用裝置資源。

類似地,在響應于某些實施例中識別出循環路徑而添加匯聚標記的情形中,向被
編譯的程序添加與循環路徑的各個出口基本塊相關聯的匯聚標記包括將匯聚標記添加在
緊接在每個出口基本塊之前。

至少一些實施例提供了一種對程序指令序列進行編譯以生成經編譯的程序的裝
置,其中該裝置具有用于執行上述任意描述的方法示例的方法的配置。

至少一些實施例提供了一種計算機可讀存儲介質,該計算機可讀存儲介質存儲有
計算機程序,該計算機程序當在計算機上運行時使得計算機執行上述任意描述的方法示例
的方法。

至少一些實施例提供了一種軟件,該軟件當在計算機上運行時使得計算機執行上
述任意描述的方法示例的方法。

至少一些實施例提供了一種利用多個運行線程并行運行計算機程序的方法,其中
計算機程序包括程序指令序列,該方法包括:識別程序指令的基本塊,其中每個基本塊只具
有一個入口點和一個出口點;確定導向每個基本塊的至少一個運行路徑;當不止一個運行
路徑導向所選基本塊時,向計算機程序添加與所選基本塊相關聯的匯聚標記;以及當存在
從另一所選基本塊到該另一所選基本塊的循環路徑時,向計算機程序添加與循環路徑的每
個出口基本塊相關聯的匯聚標記;以及運行多個運行線程,其中,運行多個運行線程包括:
當多個運行線程的第一子集從分叉基本塊(divergent basic block)采取第一運行路徑并
且多個運行線程的第二子集從所述分叉基本塊采取第二運行路徑時,使得第二子集等待;
并且當遇到匯聚標記時,根據預定并行運行規則來選擇多個運行線程中的至少一個線程以
供運行。

運行計算機程序因此可以包括以與上面針對編譯方法描述的類似方式分析程序
指令的基本塊的初始化階段,其中,程序內的潛在匯聚點被識別出并被標記以匯聚標記。之
后,當運行多個運行線程時,該方法包括識別分叉基本塊,在分叉基本塊處有不止一個運行
路徑從該基本塊導出,并且此時識別采用這些路徑的多個運行線程的子集,并且使得至少
一個子集等待,而另一子集繼續運行,因為這些運行線程的子集采用不同路徑,從而不會發
生并行運行這二者子集的益處并且允許這些子集串行方式運行比并行方式運行更有效。之
后,當遇到添加到計算機程序的匯聚點時,定義適合并行運行所選多個運行線程的時點的
預定并行運行規則可被用來確定多個運行線程中的哪些線程現在應當彼此并行運行(直到
遇到另一分叉基本塊)。

在一些實施例中,根據預定并行運行規則來選擇多個運行線程中的至少一個線程
以供運行包括:選擇要執行的下一指令在程序計數器順序中是最早的一組線程。基于程序
計數器順序對一組線程進行優先級排序于是可以對應于上文在描述的本公開技術的編譯
方法時所采用的對路徑項目排序并在隊列中處理路徑項目的方式。

至少一些實施例提供了一種并行運行計算機程序的裝置,其中,該裝置具有用于
執行上述任意描述的利用多個運行線程并行運行計算機程序的方法的配置。

該運行裝置可以采取各種形式,但是在一些實施例中,該裝置是圖形處理單元。圖
形處理單元可被要求用于并行地運行大量運行線程,并能從這樣的并行性中獲得處理效
率,并且在支持對運行處理中要執行哪些線程應當彼此并行運行的識別(以及再識別)的時
間點的選擇方面,本公開的技術支持對這樣的裝置的高效使用。這是值得注意的,因為對哪
些線程并行操作的這種評估和再評估本身代表運行裝置的并非不重要的處理任務,如果執
行得過于頻繁,可能降低處理效率,然而如果執行得過于不頻繁,這種并行性獲得的益處就
如沒有被充分利用那樣。本公開的技術允許這些位置之間的有利平衡被實現。

至少一些實施例提供了一種計算機可讀存儲介質,該計算機可讀存儲介質存儲有
計算機程序,該計算機程序當在計算機上運行時使得計算機執行上述任意描述的利用多個
運行線程并行運行計算機程序的方法。

至少一些實施例提供了一種軟件,該軟件當在計算機上運行時使得計算機執行上
述任意描述的利用多個運行線程并行運行計算機程序的方法。

現在將參考附圖來描述一些具體實施例。

圖1示意性地示出了一個實施例中的數據處理裝置10。數據處理裝置10包括中央
處理單元(CPU)12和圖形處理單元(GPU)14。CPU 12和GPU 14中的每個可以執行數據處理操
作,這些操作通過從存儲器16取回要被處理的數據以及數據處理指令來執行,并且適當情
況,還通過向存儲器16寫回數據來執行。CPU 12和GPU 14中的每個被提供有各自的緩存18、
20以便減少與從存儲器16取回指令或數據相關的延時。將會認識到CPU 12和GPU 14都可以
執行大量數據處理操作,但是與本公開的技術的討論特別有關的是GPU 14利用多個運行線
程執行計算機程序的并行運行的能力和CPU 12把來自存儲于存儲器16中的源程序的計算
機程序編譯成可執行程序的能力,可執行程序也被存儲在存儲器16中,GPU 14可以取回該
可執行程序并且然后按照并行化方式運行。此外,圖1中所示的CPU12和GPU 14的具體特征
是CPU 12向其編譯的計算機程序添加“匯聚標記”的能力,這些匯聚標記表示CPU已經確定
當GPU 14運行CPU 12編譯后的程序時對于GPU 14檢查其運行的多個運行線程間的匯聚來
說有益的點。如上所述,GPU 14在當利用多個運行線程執行程序的并行運行時,通過在任何
給定時點選擇這多個運行線程中適當子集供并行運行,GPU 14可以獲得對數據處理裝置的
資源的更有效利用。然而,由于確定這種子集本身也消耗數據處理系統的處理資源,如果這
種判定執行得過于頻繁,則會失去這樣的有效性。如上所述,本公開的技術通過選擇被編譯
的計算機程序內應當添加匯聚標記的點(例如由圖1的示例中的CPU 12執行)解決了此問
題。最后,注意,不要求CPU 12和GPU 14形成同一數據處理裝置的部分,并且包括CPU 12和
GPU 14的數據處理系統10僅是一個示例。在其他實施例中,CPU和GPU可以分別形成完全分
開的數據處理裝置的部分。實際上,本公開的技術涉及對計算機程序的編譯和運行,并且可
以等同地被應用于不具有諸如圖1的實施例的CPU 12和GPU14的特別處理單元的數據處理
裝置。

圖2示出了諸如圖1所示的數據處理系統可執行的步驟序列,其中CPU對源程序進
行編譯以供GPU運行。在步驟20,CPU從存儲器取回源程序,并且在步驟22,通過在程序內識
別出的適當點處添加匯聚標記來對此源程序進行編譯(如后面將要參考圖示更詳細論述
的)。在步驟24,如此編譯的可執行程序然后被CPU存回存儲器。然后,在步驟26,GPU從存儲
器取回此可執行程序,并且在步驟28以單指令多數據(SIMD)方式運行此程序,即并行運行
多個線程。例如,在GPU運行這樣的可執行指令的情境中,此SIMD運行可對應于程序指令序
列被應用到圖形顯示器的多個像素,而與每個像素位置相對應的數據被相同指令序列處
理。在編譯期間由CPU在步驟22添加到可執行程序的匯聚點于是在當GPU在運行此程序時會
被GPU遇到(在步驟28),并且當GPU遇到這樣的匯聚點時,GPU檢查當前運行的多個運行線程
間的匯聚,即,其再評估當前定義的線程中的哪些線程應當活動地被彼此并行運行,以便使
得數據處理系統的資源得以更有效地利用。

圖3A示出這里被用于支持對本公開的技術的討論的示例程序指令序列。將會認識
到,僅僅圖3A的示例程序代碼中的控制流指令被示出,因為這些是與本公開的技術的應用
有關的指令,并且構成“完整”程序的其余指令的數據處理指令已經被省略(僅為了說明清
楚)。圖3B示出對應于圖3A的程序指令的控制流圖(CFG)。通過圖3B的CFG將會認識到若干不
同的運行路徑(對應于所示從第一明確表示的程序指令(BB0)到來自圖3A的最后的程序指
令(BB5)的出口的可能路徑)是可能的。圖3C示出四個示例線程(T0、T1、T2、T3)采用的具體
路徑。所有四個線程是同一核(運行圖3A中所示的指令序列)的部分,并且并行地(SIMD)開
始運行。因此,如圖3C所示,所有四個線程遵循從BB0到BB1的運行路徑。然后,在BB1,由于在
BB1測試的“如果(if)”條件的不同結果,線程T0和T1與線程T2和T3分開。由于線程T0、T1與
T2、T3采用不同的運行路徑,裝置中運行這些線程的硬件(例如圖1的GPU)選擇線程T0、T1進
一步運行,并且將線程T2、T3置于等待狀態以供后續進一步運行。線程T0、T1的運行繼續于
運行由BB2表示的程序指令。如果在BB2處匯聚標記已經添加到被編譯的程序(參見圖2的步
驟22),則GPU的硬件可在此點執行它的匯聚檢查,以確定哪些線程現在應當在運行處理中
進一步處理。正是因為這個原因(即在BB2處設置了匯聚點),等待的線程T2、T3然后被選擇
以供進一步運行,而T0、T1等待,因為按照程序計數器順序BB3在BB4前面。注意,按照被執行
的指令的程序計數器值對多個線程的運行進行優先級排序并不重要,但是這代表了在可能
被選擇的多個運行線程間進行優先級區分的一種方式(本文使用了這種方式)。一旦BB3的
運行結束,匯聚標記于是使得裝置再次判斷多個運行線程中的哪些線程的子集然后應當被
選擇以供運行,并且在圖3C的示例中,其中線程T2跟隨從BB3到BB4的運行路徑,而線程T3跟
隨從BB3到BB5的運行路徑,裝置可選擇T0、T1和T2作為多個運行線程中接下來要被并行運
行的子集,即,針對子集中的每個線程運行BB4代表的指令。同時,線程T3等待。因此,從上面
對圖3A-圖3C的討論中將會認識到,對被編譯的程序中編譯器添加匯聚標記的點的選擇代
表了通過組合線程以并行運行(其中這些線程運行程序指令的相同基本塊)而對運行裝置
資源進行高效利用的機會,然而,由于運行裝置必須執行匯聚檢測以便正確地確定要被并
行運行的這樣的線程子集,其本身還代表了運行裝置上的處理負荷。

本公開的技術解決了此問題,如現在參考圖4A和圖4B所討論的。圖4A再現了圖3B
的控制流圖,而圖4B示出了在一個實施例中本公開的技術被應用以通過編譯器利用用優先
級隊列來分析圖4A的控制流圖。優先級隊列被“路徑項目”填充,每個路徑項目代表從入口
點(E)到當前等待運行的基本塊的基本塊序列。存儲在優先級隊列中的項目按照相對布置
位的順序被存儲在基本塊的存儲器中。開始,優先級隊列被填充有僅一個項目,表示入口節
點E。在圖4B的時間演進中示出的步驟(級)中的各步驟,優先級隊列中的現存路徑項目被移
除,并且運行路徑通過向現存路徑加入后續基本塊作為后綴而被延長。例如,從圖4B所示的
第一級到第二級(處理從上到下),路徑項目E被移除并被路徑項目E0替代,路徑項目E0代表
從入口點到基本塊BB0的運行路徑。此路徑項目E0然后在下一迭代中被移除,并且因為基本
BB0有兩個后續基本塊(BB1和BB5),所以兩個路徑項目被創建以供添加到優先級隊列,這兩
個路徑項目都具有相同的E0主干,并且第一路徑項目被附加“1”以表示至BB1的運行路徑,
第二路徑項目被附加“5”以表示至BB5的運行路徑。還需注意,因為BB1是比BB5低的程序計
數器值,所以在優先級隊列中E01被置于E05之前。隨著路徑項目被添加到優先級隊列而(按
照程序計數器順序)被進行優先級劃分還意味著當E012被移除并被附加4時,得到的路徑項
目E0124在優先級隊列中被置于E013之后,因為在程序計數器順序中,基本塊BB3先于基本
塊BB4。

關于圖4B中所示對優先級隊列的處理,需要注意的另一點是路徑項目E013的擴展
表示導向BB4的運行路徑。當E013被從優先級隊列中移除時并且應當被附加“4”以表示運行
路徑從BB3到BB4的擴展,現存的導向BB4的另一運行路徑通過優先級隊列中在先存在的路
徑項目E0124被識別出。結果,現存路徑項目E0124和建議的路徑項目E0134被組合以給出組
合的路徑E01{2,3}4,該組合的路徑被添加到優先級隊列。因為此步驟的分析明確地識別出
兩個分開的運行路徑匯聚到一個基本塊(在BB4),所以匯聚標記于是被添加到此點。注意,
匯聚標記在程序中的具體布置可以不同,只要認識到其與運行路徑在BB4處的匯聚相關聯
即可。例如,匯聚標記可以作為新的第一程序指令被布置在基本塊B4內,或者例如,匯聚標
記可以被布置在基本塊BB2和BB3中各基本塊的末端,只要對運行裝置的影響為匯聚分析在
BB4處的線程運行之前執行,以便發揮向可以在BB4并行運行的許多線程進行可能添加的優
勢。類似地,當E013被從優先級隊列移除時,應當附加“5”,以便表示從BB3到BB5的運行路
徑,隊列中導向BB5的現存路徑(即E05)被識別出,從而組合的路徑也在此形成,在圖4中被
表示為E0{13,NULL}5,表示了這兩個可能路徑。

此外,來自BB4的運行路徑導向BB0,因此當路徑項目E01{2,3}4被擴展以“0”以便
表示此時,此運行路徑被識別為循環,因為可能的運行路徑從BB0導向回BB0。因此,此路徑
項目不被添加回優先級隊列,并且此外,通過沿著該循環進行迭代處理以及判斷如此遇到
的每個基本塊是否給出了退出該循環的可能性,來自此循環的可能出口(在本示例中從BB0
退出和從BB3退出)被識別。如此找到的相應“循環出口”基本塊被標記聚合標記。對優先級
隊列的處理繼續,直到優先級隊列為空,這在圖4A和圖4B的示例中對應于已經構建的表示
導向BB5并進而導向出口節點的可能路徑的路徑項目的移除。

圖5示出一個實施例中當在編譯過程中執行上述添加匯聚標記時采取的步驟序
列。流程開始于步驟100,其中優先級隊列被以入口基本塊(E)被初始化。然后,在步驟102,
判斷優先級隊列是否為空。當然在步驟100后緊接的第一次迭代中,優先級隊列并不為空,
但是當優先級隊列為空(下面會更詳細描述)時,流程進行到步驟104,此處步驟結束。然而,
當優先級隊列不為空時,流程進行到步驟106,此處路徑P(這里也稱為“路徑項目”)被從優
先級隊列的最前面移除。然后,在此之后,在步驟108,為P的最后的基本塊(BB)的一個或多
個后續基本塊的每個基本塊創建路徑P’。如果對于P沒有后續基本塊,則流程(參見步驟
110)返回步驟102。當存在這樣的一個或多個后續基本塊時,流程于是進行到步驟112,此處
判斷此后續基本塊(或者在多個后續基本塊的情況中正被考慮的后續基本塊)是否已經存
在與路徑P中,這意味著循環被識別。如果識別出循環,則流程進行到步驟114,此處該循環
所有出口基本塊被標記為匯聚點(即,匯聚標記添加為與這些基本塊中的每個基本塊相關
聯)。如上所述,這些“循環出口”通過沿著循環迭代地進行處理以及判斷如此遇到的每個基
本塊是否給出了退出循環的可能性而被識別。然后,從步驟116,如果對于P存在另一后續基
本塊,則流程返回步驟112。當沒有另外的后續基本塊時,流程從步驟116返回步驟102。

如果在步驟112處沒有識別出循環,則流程進行到步驟118,此處判斷所考慮的后
續基本塊S是否已經存在于優先級隊列中的另一路徑Q。如果所考慮的后續基本塊S已經存
在于優先級隊列中的另一路徑Q,則流程進行到步驟120,此處路徑Q和路徑P被合并,后續基
本塊S被標記為匯聚點并且合并路徑被重布置到優先級隊列中。流程然后進行到步驟122,
此處判斷是否有路徑P的另一后續基本塊要被考慮。如果有,則流程返回步驟112,然而如果
沒有,則流程返回步驟102。返回考慮步驟118,如果當前所考慮的后續基本塊S沒有存在于
優先級隊列中已有的另一路徑Q上,則流程進行到步驟124,此處根據程序計數器順序P’被
添加優先級隊列,以使得優先級隊列中存在的路徑項目被排序,從而使得與該路徑項目中
的最后的基本塊相關聯(例如,與最后的基本塊的最后的指令相關聯)的程序計數器值確定
其在隊列中的位置。流程然后進行到步驟126,此處判斷P’是否未被添加到優先級隊列的最
前面。如果是這種情形,則流程經由步驟128前進,在步驟128處,基本塊S被標記為匯聚點
(即,匯聚標記被與此基本塊相關聯地添加到程序)。流程然后進行到步驟122,此處(如上所
述),判斷對于路徑P’是否有另一后續基本塊要被考慮。如前所述,當對于路徑P’沒有另一
后續基本塊要被考慮時,流程進行到步驟102,而當對于路徑P有另一后續基本塊要被考慮
時,流程進行到步驟112。因此,通過跟隨圖5給出的步驟,從優先級隊列中對應于入口基本
塊的路徑項目開始,從優先級隊列中移除路徑項目并對這些路徑項目以另外的基本塊添加
后綴以表示程序中的運行路徑并且在某些情況中還將路徑項目添加回優先級隊列,之后是
優先級隊列被構建并被騰空的處理,并且當優先級隊列為空時,過程在步驟104結束。

圖6示出了一個實施例中當運行利用本公開的技術添加匯聚標記而被編譯的計算
機程序時或者當運行程序并且還執行初始分析步驟(添加匯聚標記)時所采取的步驟序列。
首先,在步驟140,要執行計算機程序的裝置(例如圖1的GPU 14)從存儲器取回(嵌有匯聚標
記的)經編譯的可執行程序或者取回要被運行來執行預分析(諸如根據圖5的步驟)以便適
當被添加匯聚標記的程序。然后,在步驟142,多個線程(對應于可執行程序應被施加到的多
個數據項目)被初始化,以便執行對此程序的SIMD運行。然后,在步驟144,裝置選擇這些線
程中的一個或多個線程以供并行運行。這具體涉及從能被運行的所有線程中確定其中哪個
子集表示可以以鎖步方式彼此并行運行的一組線程,以便發揮從此并行化獲得的資源有效
利用的優勢。然后,在步驟146,開始運行如此選擇的線程子集,應注意此運行還可包括例如
當遇到分支時某些運行線程正被擱置并且裝置僅選擇當前運行的線程中的子集以供進一
步運行(暫時地)。在步驟148,判斷所有可能線程的運行都已結束。當并不是所有可能線程
的運行都已結束時,流程進行到步驟150,此處判斷在編譯期間所添加的匯聚標記是否已被
這些運行線程中的至少一個運行線程遇到。當匯聚標記尚未被至少一個運行線程遇到時,
流程返回步驟146以繼續進一步運行這些所選線程。否則,如果匯聚標記被遇到,則流程返
回步驟144以對此子集的線程執行關于現在哪些線程應并行執行的新評估。一旦所有線程
結束(參見步驟148),則流程在步驟152處結束(即,對此經編譯的可執行程序的運行結束)。

圖7示意性地示出可以用于實施上面描述的技術的那種類型的通用計算設備200。
通用計算設備200包括中央處理單元202、隨機存取存儲器204和只讀存儲器206,它們經由
總線222連接。該通用計算設備還包括網絡接口卡208、硬盤驅動210、顯示器驅動器212和監
視器214以及帶有鍵盤218和鼠標220的用戶輸入/輸出電路216,所有這些部件都經由公共
總線22連接。該通用計算設備還包括圖形處理單元224,圖形處理單元也連接到公共總線
222。在操作中,諸如當執行上面描述的編譯處理時,中央處理單元202將執行例如可以被存
儲在隨機存取存儲器204和/或只讀存儲器206中的計算機程序指令。替代地或者另外地,程
序指令可以從硬盤驅動210取回或者動態地經由網絡接口卡208下載。中央處理單元202的
這些操作的結果,例如,以準備好運行的經編譯的計算機程序的形式,可被本地存儲在RAM
204或HDD 210中,或者可以經由NIC 208被發送到遠程位置。這樣的經編譯的計算機程序然
后可以被GPU 224從其被CPU202存儲的位置取回出并運行。CPU 202和GPU 204執行的處理
的結果可經由所連接的顯示器驅動器212和監視器214被顯示給用戶。控制通用計算設備
200的用戶輸入可以經由所連接的輸入輸出電路216從鍵盤218或鼠標220接收。

將會認識到通用計算設備200運行(具體地由CPU 202或GPU運行)的計算機程序可
以各種不同的程序語言寫入。計算機程序可以本地存儲在記錄介質上或者可以動態下載到
通用計算設備200。當在適當計算機程序的控制下進行操作時,通用計算設備200可執行上
面描述的編譯和/或程序運行的技術,并且可被認為形成了執行上面描述的編譯和/或程序
運行的技術的裝置。通用計算設備200的架構可以有相當大的變化,并且圖7僅是一個示例。

在本申請中,詞“被配置為…”或“被布置為…”被用于指裝置的元件具有能夠執行
所定義的操作的配置。在此上下文中,“配置”指硬件或軟件的互連的布置或方式。例如,裝
置可以具有提供所定義的操作的專門的硬件,或者處理器或其他處理設備可被編程以執行
所述功能。“被配置為”或“被布置為”并不暗指裝置元件需要以任何方式被改變以便提供所
定義的操作。

雖然在此已經參考附圖詳細地描述了示意性實施例,但是應理解本發明并不限于
那些精確的實施例,而是本領域技術人員可以在不脫離由所附權利要求定義的本發明的精
神和范圍內做出各種改變、添加和修改。例如,在不脫離本發明的范圍的情況下,可以利用
獨立權利要求的特征做出對從屬權利要求的特征的各種組合。

關 鍵 詞:
程序 指令 序列 中的 分支 匯聚 確定
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:程序指令序列中的分支匯聚的確定.pdf
鏈接地址:http://www.rgyfuv.icu/p-6100715.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

copy[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
山东11选5中奖结果走势图