TW201403470A

TW201403470A - 向量分割迴圈之效能改良

Info

Publication number: TW201403470A
Application number: TW102111747A
Authority: TW
Inventors: Jeffry E Gonion
Original assignee: Apple Inc
Priority date: 2012-04-02
Filing date: 2013-04-01
Publication date: 2014-01-16
Also published as: KR20130112009A; CN103383640A; EP2648090A2; WO2013151861A1; US20130262833A1; KR101511837B1; JP2013254484A; EP2648090A3; US9116686B2; TWI512617B; BR102013007865A2; CN103383640B

Abstract

一種用於抑制對用於一向量分割迴圈中之一反向分支指令之預測的方法包括偵測在一述詞產生指令之後發生的該第一反向分支指令。該述詞產生指令產生取決於一相依性向量的一述詞向量，其中該相依性向量中之每一元素指示一資料相依性是否存在於一向量指令之元素之間。該方法亦包括接收該反向分支指令之一預測的一預測準確度之一指示。若該預測準確度不滿足一臨限值，則抑制對該反向分支指令之該預測直至該述詞產生指令所取決於的該相依性向量可用為止。

Description

向量分割迴圈之效能改良

本發明係關於處理器，且更特定言之係關於在向量分割迴圈之執行期間某些分支指令之預測。

分支預測已在大多數現代處理器中變得常見。雖然反向分支在許多狀況下可為十分易於預測的，但一些反向分支可能被習知分支預測器不良地預測。更特定言之，例如，Macroscalar(巨集純量)處理器及編譯器依賴於向量分割迴圈來正確地處置可能的迴圈帶有之相依性，諸如記憶體危障(memory hazard)。向量分割迴圈使用反向分支以在迴圈上反覆。在向量被頻繁地分割之狀況下，習知分支預測器之效能可能不良，此可不利地影響處理器效能。

揭示用於抑制對用於向量分割迴圈中的反向分支指令之預測的方法之各種實施例。一般而言，考量一種方法，在該方法中偵測在一述詞產生指令之後發生的第一反向分支指令。該述詞產生指令產生取決於一相依性向量的一述詞向量，其中該相依性向量中之每一元素指示資料相依性是否存在於向量指令之元素之間。若反向分支指令之預測之預測準確度的所接收指示不滿足臨限值，則可抑制對反向分支指令之預測直至述詞產生指令所取決於的相依性向量可用為止。

在一實施例中，該方法包括偵測在述詞產生指令之後的一第一條件分支指令。述詞產生指令在被執行時產生取決於相依性向量之一述詞向量。相依性向量之每一元素包括指示資料相依性是否存在於向量指令之元素之間的一索引。另外，該方法可包括接收第一條件分支指令之預測準確度之一指示。回應於判定第一條件分支指令之預測準確度不滿足一臨限值，可抑制對第一條件分支指令之預測直至述詞產生指令所取決於的相依性向量可用為止。

在一特定實施中，該方法亦可包括回應於偵測到相依性向量可用而使用相依性向量中指示的資料相依性資訊來預測第一條件分支指令。

100‧‧‧電腦系統

102‧‧‧處理器

104‧‧‧一級(L1)快取記憶體

106‧‧‧二級(L2)快取記憶體

108‧‧‧記憶體

110‧‧‧大容量儲存器件

201‧‧‧指令提取單元

202‧‧‧整數執行單元

204‧‧‧向量執行單元

206‧‧‧浮點執行單元

210‧‧‧分支預測單元

212‧‧‧錯誤預測單元

圖1為電腦系統之一項實施例之方塊圖。

圖2為說明圖1中所展示之處理器之實施例的額外細節之方塊圖。

圖3為說明程式碼迴圈之實例平行化的圖。

圖4A為說明在實例1中所展示的迴圈之純量執行期間的變數狀態之序列的圖。

圖4B為說明實例1之迴圈的Macroscalar向量化程式碼之執行的進展之圖。

圖5A及圖5B為說明原始程式碼之向量化之一項實施例的圖。

圖6A為說明非推測性向量化程式碼之一項實施例的圖。

圖6B為說明推測性向量化程式碼之另一實施例的圖。

圖7為說明向量化程式碼之一項實施例的圖。

圖8為說明向量化程式碼之另一實施例的圖。

圖9為描繪在形成一向量分割迴圈之程式指令之執行期間圖2之處理器之一項實施例的操作的流程圖。

特定實施例在圖式中藉由實例展示且將在本文中詳細描述。然而，應理解，圖式及「實施方式」不意欲將申請專利範圍限於所揭示之特定實施例，甚至在關於特定特徵僅描述了單一實施例之狀況下亦為如此。相反，意欲涵蓋將對受益於本發明之熟習此項技術者顯而易見之所有修改、等效物及替代物。除非另外陳述，否則本發明中所提供之特徵之實例意欲為說明性的而非為限制性的。

如貫穿本申請案所使用，詞「可」係以許可之意義(亦即，意謂有可能)而非強制性之意義(亦即，意謂必須)來使用。類似地，詞「包括」意謂包括但不限於。

各種單元、電路或其他組件可被描述為「經組態以」執行一或多項任務。在此等上下文中，「經組態以」為廣泛的結構闡述，其一般意謂「具有」在操作期間執行該一或多項任務之「電路」。因而，單元/電路/組件可經組態以甚至在單元/電路/組件當前未接通時仍執行任務。一般而言，形成對應於「經組態以」之結構的電路可包括硬體電路。類似地，為了描述之方便起見，可將各種單元/電路/組件描述為執行一或多項任務。此等描述應被解譯為包括片語「經組態以」。闡述經組態以執行一或多項任務之單元/電路/組件明確地意欲不援引35 U.S.C.§112第六段之對該單元/電路/組件之解譯。

本發明之範疇包括本文中所揭示之特徵中的任何特徵或組合(明顯地或隱含地)，或其任何一般化，而不管其是否減輕本文中所陳述之問題中之任一者或全部。因此，可在此申請案(或主張其優先權之申請案)之審查期間針對任何此特徵組合制訂新請求項。詳言之，參考隨附申請專利範圍，來自附屬請求項之特徵可與獨立請求項之彼等特徵組合，且來自各別獨立請求項之特徵可以任何適當方式組合，而非僅以隨附申請專利範圍中所列舉之特定組合來組合。

電腦系統概述

現轉向圖1，展示電腦系統之一項實施例的方塊圖。電腦系統100包括處理器102、二級(L2)快取記憶體106、記憶體108及大容量儲存器件110。如所展示，處理器102包括一級(L1)快取記憶體104。應注意，儘管在電腦系統100中展示及描述了多個特定組件，但在替代實施例中，不同組件及不同數目個組件可存在於電腦系統100中。舉例而言，電腦系統100可能不包括記憶體階層架構中之一些組件(例如，記憶體108及/或大容量儲存器件110)。或者，儘管將L2快取記憶體106展示為在處理器102外部，但已考量到在其他實施例中，L2快取記憶體106可在處理器102內部。應進一步注意，在此等實施例中，可使用三級(L3)快取記憶體(未圖示)。另外，電腦系統100可包括圖形處理器、視訊卡、視訊俘獲器件、使用者介面器件、網路卡、光碟機，及/或使用匯流排、網路或另一合適通信頻道耦接至處理器102之其他周邊器件(為簡單起見而皆未圖示)。

在各種實施例中，處理器102可代表執行計算運算之通用處理器。舉例而言，處理器102可為中央處理單元(CPU)，諸如微處理器、微控制器、特殊應用積體電路(ASIC)或場可程式化閘陣列(FPGA)。然而，如下文進一步描述，處理器102可包括用於向量處理之一或多個機構(例如，向量執行單元)。下文結合圖2之描述更詳細地描述處理器102之實例向量執行單元。

大容量儲存器件110、記憶體108、L2快取記憶體106及L1快取記憶體104為共同形成記憶體階層架構之儲存器件，該記憶體階層架構儲存用於處理器102之資料及指令。更特定而言，大容量儲存器件110可為高容量、非揮發性記憶體，諸如具有長存取時間之磁碟機或大快閃記憶體單元，而L1快取記憶體104、L2快取記憶體106及記憶體108可較小，具有較短存取時間。此等較快半導體記憶體儲存頻繁使用之資料的複本。記憶體108可代表記憶體器件之動態隨機存取記憶體(DRAM)系列中之記憶體器件。記憶體108之大小通常大於L1快取記憶體104及L2快取記憶體106，而L1快取記憶體104及L2快取記憶體106通常係使用器件之靜態隨機存取記憶體(SRAM)系列中的較小器件來實施。在一些實施例中，在電腦系統100中之一或多個處理器之間共用L2快取記憶體106、記憶體108及大容量儲存器件110。

在一些實施例中，記憶體階層架構中之器件(亦即，L1快取記憶體104等)可每循環存取(亦即，讀取及/或寫入)多個快取行。此等實施例可實現對記憶體存取之更有效處理，該等記憶體存取基於指向非連續記憶體位址之指標或陣列索引之向量而發生。

應注意，下文描述之資料結構及程式指令(亦即，程式碼)可儲存於非暫時性電腦可讀儲存器件上，該非暫時性電腦可讀儲存器件可為可儲存程式碼及/或資料以供電腦系統(例如，電腦系統100)使用的任何器件或儲存媒體。一般而言，非暫時性電腦可讀儲存器件包括(但不限於)揮發性記憶體、非揮發性記憶體、磁性及光學儲存器件(諸如，磁碟機、磁帶、光碟(CD)、數位多功能光碟或數位影音光碟(DVD))，或現在已知或稍後開發之能夠儲存電腦可讀媒體之其他媒體。因而，大容量儲存器件110、記憶體108、L2快取記憶體106及L1快取記憶體104皆為非暫時性電腦可讀儲存器件之實例。

處理器

參看圖2，展示說明圖1之處理器的實施例之額外細節的方塊圖。在圖2中所展示之實施例中，處理器102可包括數個管線級，但為簡潔起見而未將所有管線級展示於圖2中。因此，如所展示，處理器102包括L1快取記憶體104、指令提取單元201、分支預測單元210、錯誤預測單元212、整數執行單元202、浮點執行單元206，及向量執行單元204。應注意，可將整數執行單元202、浮點執行單元206及向量執行單元204作為群組而互換地稱為「執行單元」。

在各種實施例中，執行單元可(例如)對相關聯類型之運算元執行計算運算，諸如邏輯運算、數學運算或逐位元運算。更具體而言，整數執行單元202可執行涉及整數運算元之計算運算，浮點執行單元206可執行涉及浮點運算元之計算運算，且向量執行單元204可執行涉及向量運算元之計算運算。整數執行單元及浮點執行單元在此項技術中為公知的，且為簡潔起見而不進行進一步描述。如上文所提及，儘管圖2中所展示之處理器102的實施例包括組件之特定集合，但考量到在替代實施例中，處理器102可包括不同數目個或不同類型之執行單元、功能單元及管線級，諸如可耦接至執行單元之指令解碼單元、排程器或保留站(reservations station)、重新排序緩衝器、記憶體管理單元、I/O介面等。

向量執行單元204可代表傳統意義上之單指令多資料(SIMD)執行單元，此係因為其可平行地對多個資料元素執行同一運算。然而應注意，在一些實施例中，此處描述之向量指令可不同於SIMD指令之其他實施。舉例而言，在一實施例中，藉由向量指令進行運算之向量的元素可具有不隨向量中元素之數目而變化的大小。相對照地，在一些SIMD實施中，資料元素大小隨進行運算之資料元素之數目而變化(例如，SIMD架構可能支援對八個8位元元素、但僅四個16位元元素、兩個32位元元素等之運算)。在一項實施例中，向量執行單元204可對包括於運算元向量中之資料元素中的一些或全部進行運算。更特定而言，向量執行單元204可經組態以同時對向量程式指令之向量運算元的不同元素進行運算。

在一項實施例中，向量執行單元204可包括向量暫存器組(未圖示)，該向量暫存器組可包括可保存向量執行單元204之運算元向量及結果向量的向量暫存器。在一些實施例中，向量暫存器組中可存在32 個向量暫存器，且每一向量暫存器可包括128個位元。然而，在替代實施例中，可存在不同數目個向量暫存器及/或每暫存器可存在不同數目個位元。

向量執行單元204可經組態以自向量暫存器擷取運算元，且執行向量指令，該等向量指令使向量執行單元204對運算元向量中之資料元素中的一些或全部平行地執行運算。舉例而言，向量執行單元204可對向量中之元素執行邏輯運算、數學運算或逐位元運算。向量執行單元204可每指令循環執行一個向量運算(但如上文所描述，一「循環」可包括可用以觸發、同步及/或控制向量執行單元204之計算運算的一個以上時脈循環)。

在一項實施例中，向量執行單元204可支援保存N個資料元素(例如，位元組、字組、雙字組等)之向量，其中N可為任何正整數。在此等實施例中，向量執行單元204可對運算元向量中之N個或N個以下資料元素平行地執行運算。舉例而言，在向量長度為256個位元之實施例中，正進行運算之資料元素為四位元組元素，且該運算為將一值加至該等資料元素，此等實施例可將該值加至向量中之任何數目個元素。應注意，對於處理器102之不同實施而言，N可不同。

在各種實施例中，向量執行單元204可包括至少一個控制信號，該至少一個控制信號允許實現對運算元向量中向量執行單元204進行運算之資料元素的動態限制。具體而言，取決於控制信號之狀態，向量執行單元204可選擇性地對向量中之資料元素中的任一者或全部進行運算。舉例而言，在向量長度為512個位元且正進行運算之資料元素為四位元組元素的實施例中，可確證控制信號以防止對運算元向量中之16個資料元素中之一些或全部執行運算。應注意，「動態地」限制運算元向量中執行運算之資料元素可涉及在執行階段針對每一循環單獨地確證控制信號。

在一些實施例中，如下文更詳細地描述，基於述詞或一或多個純量述詞之向量中所含有之值，向量執行單元204僅將向量運算應用於選定向量資料元素。在一些實施例中，結果向量中之剩餘資料元素保持不受影響(此亦可稱為「述詞化」)或被迫為零(此亦可稱為「調零」或「調零述詞化」)。在一些實施例中，在向量執行單元204中歸因於述詞化或調零而未使用的資料元素處理子系統「單向通道(lane)」之時脈可受功率及/或時脈閘控，藉此減少向量執行單元204中之動態功率消耗。

在各種實施例中，該架構中之向量長度可能無從驗證以允許該架構在執行階段調適平行性。更特定而言，當指令或運算之向量長度無從驗證時，可使用任何長度(高達由支援硬體強加之限制)之向量來執行運算(亦即，指令等)。舉例而言，在向量執行硬體支援可包括八個單獨的四位元組元素(因此具有八個元素之向量長度)之向量的實施例中，向量長度無從驗證之運算可對向量中之八個元素中的任何數目個元素進行運算。關於支援不同向量長度(例如，四個元素)之不同硬體實施，向量長度無從驗證之運算可對由基礎硬體提供之不同數目個元素進行運算。因此，編譯器或程式設計師無需明確地知曉由基礎硬體(例如，向量執行單元204)支援之向量長度。在此等實施例中，編譯器產生或程式設計師撰寫無需依賴於(或使用)特定向量長度之程式碼。在一些實施例中，可能禁止在程式碼中指定特定向量大小。因此，在此等實施例中之已編譯程式碼(亦即，二進位碼)在可具有不同向量長度之其他執行單元上執行，同時可能實現來自支援較長向量之處理器的效能增益。在此等實施例中，可在執行階段期間自系統暫存器讀取用於給定硬體單元(諸如，處理器)之向量長度。因此，當處理技術允許較長向量時，容易地加速舊版二進位碼之執行而不用軟體開發者付出任何努力。

一般而言，可將向量長度實施為二的冪(例如，二、四、八等)。然而，在一些實施例中，向量長度無需為二的冪。具體而言，可以與具有二的冪之數目個資料元素之向量相同的方式使用具有三個、七個或另一數目個資料元素之向量。

在各種實施例中，向量中之每一資料元素可含有一位址，該位址由向量執行單元204用於平行地執行一組記憶體存取。在此等實施例中，若向量中之一或多個元素含有無效記憶體位址，則可發生無效記憶體讀取操作。因此，原本將導致程式終止之無效記憶體讀取操作可替代地引起具有有效位址之任何元素被讀取，且具有無效位址之元素被加上旗標，從而儘管為推測性及事後確認為非法(hindsight illegal)之讀取操作，仍允許程式執行繼續。

在一些實施例中，處理器102(及因此向量執行單元204)能夠對指標向量進行運算且使用指標向量。在此等實施例中，無關於資料類型之大小，每一向量之資料元素的數目與每一向量之指標的數目相同。對記憶體進行操作之指令可具有指示記憶體存取之大小的變體，但處理器暫存器中之元素應與指標大小相同。在此等實施例中，支援32位元定址模式及64位元定址模式兩者之處理器可選擇在32位元模式中允許每一向量兩倍的元素，藉此達成較大輸貫量。在假定相同寬度之資料路徑時，此情形暗示相對於32位元定址之明顯輸貫量優勢。可將實施特定技術用以放寬要求。舉例而言，可經由暫存器配對或某一其他專用機制來在32位元模式中支援雙精度浮點數。

在一項實施例中，分支預測單元210可經組態以針對條件分支指令產生分支目標程式計數器位址(PC)以用於提取單元201。更特定而言，對於條件分支指令，分支預測單元210可預測將選取抑或不選取分支，且控制邏輯(未圖示)可基於該預測產生PC以用於提取單元201。接著可取決於分支之預測結果而以推測方式提取、發出及執行指令。在各種實施例中，分支預測單元210可使用多種預測機制中之任一者來產生預測。舉例而言，分支預測單元210可使用以下各者：區域預測器，其維持個別分支之預測狀態(例如，狀態機、表、計數器或其他資料結構)；全域預測器，其跨越總體考慮之多個分支執行預測；混合預測器，其組合區域預測器及全域預測器之元素；或其他合適方法。在一些實施例中，分支預測單元210可使用動態地調適於在執行期間變化之分支行為的預測器(例如，偵測根據一種技術進行預測較好之分支變得根據不同技術進行預測較好的情況，並進行調適)。

在一項實施例中，錯誤預測單元212經組態以偵測分支預測為不正確的情況(例如，在執行分支時該分支之實際行為不同於該分支之所預測行為，從而指示錯誤預測了分支)。另外，錯誤預測單元212可經組態以將錯誤預測之指示提供至執行單元202、206及204，以及提供至分支預測單元210。應注意，儘管將錯誤預測單元212展示為單獨單元，但考量到在其他實施例中，錯誤預測單元212可為分支預測單元210之部分，或其可為提取單元201之部分，或其可為各種執行單元(例如，202、204及206)中之任一者或全部的部分。

如上文所描述，當習知處理器錯誤預測分支指令時，自管線清除在錯誤預測路徑中之指令，此係因為：鑒於不正確的推測，不應允許此等以推測方式發出之指令修改處理器之狀態。提取單元201接著可提取正確、非推測路徑之指令。然而，存在進行此清除及填充操作所造成之不利結果：在可重新繼續有用工作之前可需要數百個執行循環。

因此，如下文結合圖7之描述更詳細地描述，在一實施例中，分支預測單元210可維持各種預測之預測準確度資訊。可基於分支指令之實際行為(一旦分支指令被執行)，與分支指令被預測會有的行為方式相比較地調適給定分支指令之準確度資訊。為了避免與用於向量分割迴圈中之錯誤預測反向分支相關聯的一些不利結果，當預測準確度不良時，分支預測單元210可經組態以抑制預測，並等待對應於迴圈之反覆的數目之資訊變得可用。

Macroscalar架構概述

指令集架構(稱為Macroscalar架構)及支援硬體可允許編譯器產生用於迴圈之程式碼，而不必在編譯階段完全判定平行性且不捨棄有用的靜態分析資訊。現將描述Macroscalar架構之各種實施例。具體而言，如下文進一步描述，提供如下指令集：其不強制迴圈之平行性，而是改為在動態條件准許之情況下允許在執行階段利用平行性。因此，該架構包括使得由編譯器產生之程式碼能夠執行以下操作的指令：取決於執行階段之條件，藉由切換所使用平行性之量，在迴圈反覆之非平行(純量)執行與平行(向量)執行之間動態地切換。

因此，該架構提供如下指令：其允許實現用於迴圈反覆之未判定量之向量平行性，但不要求在執行階段使用平行性。更具體而言，該架構包括向量長度無從驗證之指令的集合，該等指令之有效向量長度可取決於執行階段條件而變化。因此，若執行階段相依性要求程式碼之非平行執行，則執行以有效向量長度為一個元素之方式發生。同樣地，若執行階段條件准許平行執行，則在由執行階段相依性(及基礎硬體之向量長度)允許的程度下，以向量平行方式執行同一程式碼。舉例而言，若向量之八個元素中的兩個可安全地平行執行，則處理器(諸如，處理器102)可平行地執行該兩個元素。在此等實施例中，以向量長度無從驗證之格式表達程式碼允許實現廣泛範圍的向量化機會，該等機會在現有系統中是不存在的。

在各種實施例中，在編譯期間，編譯器首先分析程式碼中之給定迴圈的迴圈結構，且執行靜態相依性分析。編譯器接著產生執行以下操作之程式碼：保持靜態分析資訊，且指示諸如處理器102之處理器(例如)如何解析執行階段相依性並以最大可能量之平行性來處理程式碼。更具體而言，編譯器可提供用於平行地執行迴圈反覆之相應集合的向量指令，且可提供向量控制指令，該等向量控制指令用於動態地限制向量指令之執行，以防止在迴圈的反覆之間的資料相依性引起錯誤。此方法將平行性之判定延後至執行階段，在執行階段，關於執行階段相依性之資訊可用，從而允許軟體及處理器調適平行性以適應動態改變之條件。圖3中展示程式碼迴圈平行化之實例。

參看圖3之左側，展示具有迴圈之四個反覆(例如，反覆1至4)的執行型樣，該四個反覆尚未被平行化，其中每一迴圈包括指令A至G。展示了串行操作，其中垂直地堆疊多個指令。已平行化之迴圈之版本在圖3之右側。在此實例中，反覆內之每一指令取決於在其之前的至少一個指令，使得在給定反覆之該等指令之間存在靜態相依性鏈結(chain)。因此，無法將給定反覆內之該等指令平行化(亦即，給定反覆內之指令A至G始終被相對於該反覆內之其他指令串行地執行)。然而，在替代實施例中，給定反覆內之指令可為可平行化的。

如圖3中之迴圈之該等反覆之間的箭頭所展示，在給定反覆中之指令E與後續反覆之指令D之間可能存在執行階段資料相依性。然而，在編譯期間，編譯器可僅判定在此等指令之間可能存在資料相依性，但編譯器無法分辨相依性實際上將體現在哪些反覆中，此係因為此資訊僅在執行階段可用。在此實例中，藉由自1E至2D及自3E至4D之實線箭頭來展示實際上在執行階段體現之資料相依性，而使用自2E至3D之虛線箭頭來展示未在執行階段體現之資料相依性。因此，如所展示，執行階段資料相依性實際上發生在第一反覆/第二反覆與第三反覆/第四反覆之間。

因為在第二反覆與第三反覆之間不存在資料相依性，所以可安全地平行處理第二反覆及第三反覆。此外，給定反覆之指令A至指令C及指令F至指令G僅在反覆內具有相依性，且因此給定反覆之指令A能夠與所有其他反覆之指令A平行地執行，指令B亦可與所有其他反覆之指令B平行地執行，等等。然而，因為第二反覆中之指令D取決於第一反覆中之指令E，所以第一反覆中之指令D及E必須在第二反覆之指令D可被執行之前予以執行。

因此，在右側之平行化迴圈中，執行此迴圈之反覆以適應靜態資料相依性及執行階段資料相依性兩者，同時達成最大平行性。更特定而言，平行地執行所有四個反覆之指令A至C及指令F至G。但因為第二反覆中之指令D取決於第一反覆中之指令E，所以第一反覆中之指令D及E必須在第二反覆之指令D可被執行之前予以執行。然而，因為在第二反覆與第三反覆之間不存在資料相依性，所以可平行地執行此等反覆之指令D及E。

Macroscalar架構之實例

以下實例介紹Macroscalar操作且示範其在將迴圈(諸如，圖3中所展示且上文在平行化迴圈實例中描述之迴圈)向量化的過程中的用途。為了易於理解，使用呈C++格式之偽碼來呈現此等實例。

應注意，以下實例實施例係出於論述之目的。實際指令及操作僅意欲輔助對架構之理解。然而，在替代實施例中，可(例如)使用較原始操作之微碼序列或使用子操作之不同序列以不同方式實施指令或操作。應注意，避免了對指令之進一步分解，使得不會使關於巨集操作及對應使用模型之資訊晦澀不清。

標記法

在描述下文實例時，將以下格式用於變數，除非另外提及，否則該等變數為向量：p5=a<b；取決於測試a<b之結果，將向量p5之元素設定為0或1。應注意，向量p5可為如下文更詳細描述之「述詞向量」。產生述詞向量之一些指令亦設定處理器狀態旗標，以反映所得述詞。舉例而言，處理器狀態旗標或條件碼可包括FIRST、LAST、NONE及/或ALL旗標。

^~p5；a=b+c；在向量「a」中僅由述詞向量p5中之作用中(亦即，非零)元素表示之元素接收b+c之結果。a中之剩餘元素未改變。此操作被稱作「述詞化」，且在述詞向量之前使用波狀(「^~」)符號來表示。

！p5；a=b+c；在向量「a」中僅由述詞向量p5中之作用中(亦即，非零)元素表示的元素接收b+c之結果。將a中之剩餘元素設定為零。此操作被稱作「調零」，且在述詞向量之前使用驚嘆號(「！」)符號來表示。

if(FIRST())goto...；//同樣地，LAST(),ANY(),ALL(),CARRY(),ABOVE()，或NONE()，(其中ANY()==！NONE())

以下指令相應地測試處理器狀態旗標及分支。

x+=VECLEN；VECLEN為傳達每一向量之元素數目的機器值。該值係由執行程式碼之處理器在執行階段判定，而非由組譯器判定。

//註解

以類似於許多通用程式設計語言的方式，以下實例使用雙正斜線來指示註解。此等註解可提供關於所指示向量中含有之值的資訊或正在對應實例中執行之操作的解釋。

在此等實例中，其他C++格式的運算子保持其習知含義，但在逐元素基礎上應用於整個向量上。在使用函式呼叫之情況下，函式呼叫暗示將所傳回之任何值置放至目的地暫存器中的單一指令。為了理解簡單起見，所有向量為整數向量，但替代實施例支援其他資料格式。

結構式迴圈帶有之相依性

在下文之程式碼實例1中，展示使用習知向量架構而「不可向量化」之程式碼迴圈。(應注意，除不可向量化之外，此迴圈亦歸因於資料相依性之細粒度性質而不可在習知多執行緒架構上多執行緒化。)為了清楚起見，已將此迴圈精簡(distill)為使迴圈不可向量化之基本迴圈帶有之相依性。

在此實例中，變數r及s具有防止使用習知架構之向量化的迴圈帶有之相依性。然而注意到，只要條件(A[x]<FACTOR)已知始終為真或始終為假，迴圈便可向量化。在允許該條件在執行期間變化(常見狀況)時，此等假定會改變。為了簡單起見，在此實例中，吾人假設在A[ ]與B[ ]之間不存在混淆(aliasing)。

實例1：程式碼迴圈

r=0； s=0； for(x=0；x<KSIZE；++x) { if(A[x]<FACTOR) { r=A[x+s]； } else { s=A[x+r]； } B[x]=r+s； }

在使用Macroscalar架構之情況下，可藉由將向量分割成多個區段而使實例1中之迴圈向量化，對於該等區段，條件(A[x]<FACTOR)不改變。在下文中呈現用於分割此等向量之程序的實例以及允許實現該分割之指令的實例。應注意，對於此實例，僅需要將所描述分割應用於條件子句內之指令。除了可能在最後迴圈反覆中以外，可始終跨越整個向量平行地執行A[x]之第一次讀取及最終運算B[x]=r+s。

結合Macroscalar架構來展示及描述向量化程式碼之指令及實例，以解釋向量處理器(諸如，圖2之處理器102)之操作。大體上組織以下描述，使得描述數個指令且接著呈現使用該等指令之一或多個向量化程式碼樣本。在一些狀況下，在給定實例中探究特定類型之向量化問題。

dest=VectorReadInt(Base,Offset)

VectorReadInt為用於執行記憶體讀取操作之指令。將按資料大小縮放之偏移向量Offset(在此狀況下為整數)加至純量基底位址Base，以形成接著被讀取至目的地向量中之記憶體位址的向量。若將指令述詞化或調零，則僅讀取對應於作用中元素之位址。在所描述之實施例中，允許對無效位址之讀取發生錯誤，但此等錯誤僅在第一作用中位址無效的情況下導致程式終止。

VectorWriteInt(Base,Offset,Value)

VectorWriteInt為用於執行記憶體寫入操作之指令。將按資料大小縮放之偏移向量Offset(在此狀況下為整數)加至純量基底位址Base，以形成記憶體位址之向量。將值之向量Value寫入至此等記憶體位址。若將此指令述詞化或調零，則僅將資料寫入至作用中位址。在所描述之實施例中，對非法位址之寫入始終產生錯誤。

dest=VectorIndex(Start,Increment)

VectorIndex為用於產生以單調方式調整之值之向量的指令，該調整係藉由從由Start指定之純量開始值起遞增來進行。當索引調整恆定時，此指令可用於初始化迴圈索引變數。當應用述詞化或調零時，第一作用中元素接收開始值，且遞增僅應用於後續的作用中元素。舉例而言：x=VectorIndex(0,1)；//x={0 1 2 3 4 5 6 7}

dest=PropagatePostT(dest,src,pred)

PropagatePostT指令將src中之作用中元素(如由pred判定)的值傳播至dest之後續非作用中元素。作用中元素及在第一作用中元素之前的任何非作用中元素在dest中保持不變。此指令之目的為選取有條件地計算之值，且將有條件地計算之值傳播至如在等效純量程式碼中出現之後續迴圈反覆。舉例而言：入口：dest={8 9 A B C D E F}

src={1 2 3 4 5 6 7 8}

pred={0 0 1 1 0 0 1 0}

出口：dest={8 9 A B 4 4 E 7}

dest=PropagatePriorF(src,pred)

PropagatePriorF指令將src之非作用中元素(如由pred判定)的值傳播至dest中之後續作用中元素中。將非作用中元素自src複製至dest。若述詞之第一元素為作用中的，則將src之最後元素傳播至該位置。舉例而言：入口：src={1 2 3 4 5 6 7 8}

pred={1 0 1 1 0 0 1 0}

出口：dest={8 2 2 2 5 6 6 8}

dest=ConditionalStop(pred,deps)

ConditionalStop指令評估述詞向量pred，且識別相鄰述詞元素之間的轉變，該等轉變暗示如由deps所指定的資料相依性。可將純量值deps視為四個位元之陣列，其中之每一位元表示pred中之真/假元素(如自左向右處理)之間的可能轉變。若設定，則此等位元傳遞所指示相依性之存在，且若未設定，則此等位元保證不存在相依性。該等位元為以下各者：kTF-暗示自述詞為真的反覆至述詞之值為假的後續反覆的迴圈帶有之相依性。

kFF-暗示自述詞為假的反覆至述詞之值為假的後續反覆的迴圈帶有之相依性。

kFT-暗示自述詞為假的反覆至述詞之值為真的後續反覆的迴圈帶有之相依性。

kTT-暗示自述詞為真的反覆至述詞之值為真的後續反覆的迴圈帶有之相依性。

將對應於產生被取決於之資料之反覆的元素位置儲存於目的地向量中的對應於取決於該資料之反覆的元素位置處。若不存在資料相依性，則將值0儲存於目的地向量中的該元素處。所得相依性索引向量(或DIV)含有表示相依性之元素位置索引的向量。出於下文所描述之原因，向量之第一元素為元素編號1(而非0)。

作為一實例，考慮上文實例1之迴圈中的相依性。在此迴圈中，條件子句之真反覆與假反覆之間的轉變表示迴圈帶有之相依性，其要求中斷平行性。可使用以下指令來處置此情形：p1=(t<FACTOR)；//p1={00001100}

p2=ConditionalStop(p1,kTF|kFT)；//p2={00004060}

因為第4反覆產生所需資料，且第5反覆取決於該資料，所以將4儲存於輸出向量p2(其為DIV)之位置5中。相同情形適用於第7反覆，第7反覆取決於來自第6反覆之資料。將DIV之其他元素設定為0以指示不存在相依性。(應注意，在此實例中，向量之第一元素為元素編號1。)

dest=GeneratePredicates(Pred,DIV)

GeneratePredicates取得相依性索引向量DIV，且考慮到已處理的前一群組(由pred指示)，產生對應於可安全地平行處理之元素之下一群組的述詞。若pred之元素皆不在作用中，則針對可安全地平行處理之元素之第一群組產生述詞。若Pred指示已處理向量之最終元素，則該指令產生非作用中述詞之結果向量，其指示不應處理任何元素，且設定ZF旗標。設定CF旗標以指示結果之最後元素為作用中的。使用第一實例中之值，GeneratePredicates進行如下操作：入口條件：//i2={0 0 0 0 4 0 6 0}

p2=0；//p2={0 0 0 0 0 0 0 0}

Loop2： p2=GeneratePredicates(p2,i2)；//p2'={1 1 1 1 0 0 0 0}

CF=0,ZF=0

if(！PLAST())goto Loop2//p2"={0 0 0 0 1 1 0 0}

CF=0,ZF=0

//p2'''={0 0 0 0 0 0 1 1}

CF=1,ZF=0

自全零之經初始化述詞p2，GeneratePredicates產生p2之新例項，該等新例項將後續向量計算分割成三個子向量(亦即，p'、p"及p''')。此分割使得硬體能夠按群組來處理向量，從而避免違反迴圈之資料相依性。

在圖4A中，展示了說明在實例1中之迴圈之純量執行期間的變數狀態之序列的圖。更特定而言，使用條件運算式之方向的隨機化50/50分佈，展示實例1之迴圈之變數狀態的進展。在圖4B中，展示了說明實例1之迴圈之Macroscalar向量化程式碼的執行之進展的圖。在圖4A及圖4B中，使用陰影背景來展示自A[ ]讀取及寫入至B[ ]之值，且使用傾斜之雜湊標記來展示「r」或「s」之值(取決於哪一者在給定反覆中改變)。觀察到，在「s」改變時「r」從不改變，且在「r」改變時「s」從不改變。

沒有什麼會防止自A[ ]平行地讀取所有值或將所有值平行地寫入至B[ ]，此係因為值集合皆不參與迴圈帶有之相依性鏈結。然而，對於r及s之計算，僅可在條件運算式之值保持相同(亦即，一連串真或假)時平行地處理多個元素。圖4B中展示此迴圈之程式碼的此執行型樣。應注意，該實例使用長度上具有八個元素之向量。當處理第一向量指令時，單獨地執行第一反覆(亦即，向量執行單元204僅處理第一向量元素)，而藉由向量執行單元204平行地處理反覆1至5，且接著藉由向量執行單元204平行地處理反覆6至7。

參看圖5A及圖5B，展示說明程式碼之向量化之一項實施例的圖。圖5A描繪原先的原始程式碼，而圖5B說明向量化程式碼，其表示可使用Macroscalar架構執行之操作。在圖5B之向量化程式碼中，迴圈1為來自原始程式碼之迴圈，而迴圈2為處理子向量分割之向量分割迴圈。

在該實例中，以全長向量來讀取及比較陣列A[ ](亦即，對於具有N個元素之向量，一次性讀取陣列A[ ]之N個位置)。向量i2為控制向量之分割的DIV。藉由監視針對假與真之間的轉變之述詞p1來判定分割，該等轉變指示應遵守之迴圈帶有之相依性。述詞向量p2判定在任何時間將對哪些元素起作用。在此特定迴圈中，p1在任何子向量分割之所有元素中具有相同值；因此，僅需要檢查分割之第一元素來判定要更新哪一變數。

在變數「s」被更新之後，PropagatePostT指令將作用中分割中之最終值傳播至向量中之後續元素。在迴圈頂部，PropagatePriorF指令跨越向量之所有元素複製來自最終向量位置之「s」的最後值，從而為下一遍次作準備。應注意，使用不同方法傳播變數「r」，從而說明在某些狀況下使用PropagatePriorF指令之效率。

軟體推測

在先前實例中，因為控制流程決策與迴圈帶有之相依性無關，所以可判定在向量分割迴圈的開始之前的向量分割。然而，情況並非始終如此。考慮實例2A及實例2B中所展示之以下兩個迴圈：實例2A：程式碼迴圈1

j=0； for(x=0；x<KSIZE；++x) { if(A[x]<FACTOR) { j=A[x+j]； } B[x]=j； }

實例2B：程式碼迴圈2

j=0； for(x=0；x<KSIZE；++x) { if(A[x+j]<FACTOR) { j=A[x]； } B[x]=j； }

在實例2A中，控制流程決策與迴圈帶有之相依性鏈結無關，而在實例2B中，控制流程決策為迴圈帶有之相依性鏈結之部分。在一些實施例中，實例2B中之迴圈可造成以下推測：「j」之值將保持不變，且若此預測證明為不正確的，則稍後進行補償。在此等實施例中，對「j」之值的推測不會顯著地改變迴圈之向量化。

在一些實施例中，編譯器可經組態以始終預測在迴圈之多個反覆之間不存在資料相依性。在此等實施例中，在存在執行階段資料相依性之狀況下，可減少平行處理之作用中元素之群組，以表示可在此時安全地平行處理之元素之群組。在此等實施例中，錯誤預測比實際存在之平行性多之平行性所造成的不利結果很少，此係因為實際上沒有損失平行性(亦即，必要時，可按非平行方式一次一個元素地處理反覆)。在此等實施例中，簡單地在稍後階段辨識平行性之實際量。

dest=VectorReadIntFF(Base,Offset,pf)

VectorReadIntFF為VectorReadInt之第一出錯變體。若至少第一作用中元素為有效位址，則此指令不產生錯誤。迫使對應於無效位址之結果為零，且傳回旗標pf，該旗標可用以向使用此資料之稍後指令遮蔽述詞。若位址之第一作用中元素未被映射，則此指令發生錯誤，以允許電腦系統100中之虛擬記憶體系統(未圖示)填入對應頁，藉此確保處理器102可繼續向前進展。

dest=Remaining(Pred)

Remaining指令評估述詞向量Pred，且計算向量中之剩餘元素。此對應於在最後的作用中述詞之後的非作用中述詞之集合。若Pred中不存在作用中元素，則傳回所有作用中述詞之向量。同樣，若Pred為所有作用中述詞之向量，則傳回非作用中述詞之向量。舉例而言：入口：pred={0 0 1 0 1 0 0 0}

出口：dest={0 0 0 0 0 1 1 1}

圖6A及圖6B為說明實例向量化程式碼之實施例的圖。更特定而言，圖6A中所展示之程式碼樣本為實例2A(如上文所呈現)中之程式碼的向量化版本。圖6B中所展示之程式碼樣本為實例2B中之程式碼的向量化版本。參看圖6B，已將A[ ]之讀取及後續比較移至向量分割迴圈內部。因此，此等操作假設(推測)「j」之值不改變。僅在使用「j」之後，才有可能判定「j」可能在何處改變值。在更新「j」之後，在必要時重新計算剩餘向量元素以在整個向量上進行反覆。在推測性程式碼樣本中使用Remaining指令允許程式判定在向量分割迴圈中仍需要處理哪些元素，該判定係在該程式能判定可實際上安全地處理(亦即，不具有未解析之資料相依性)的此等元素的子群組之前進行。

在各種實施例中，提供容錯讀取支援。因此，在此等實施例中，處理器102可使用來自向量指令(例如，VectorReadFF)之無效元素的位址以推測方式自記憶體讀取資料，以試圖載入稍後將用於計算中之值。然而，在發現到已發生無效讀取後，此等值最終被捨棄且因此與正確的程式行為無關。因為此等讀取可參考不存在或受保護之記憶體，所以此等實施例可經組態以在存在自記憶體錯誤讀取之無效但不相關資料的情況下繼續正常執行。(應注意，在支援虛擬記憶體之實施例中，此做法可具有直至確定需要分頁時才分頁之額外益處。)

在圖6A及圖6B中所展示之程式迴圈中，在條件為真之反覆與後續反覆之間存在迴圈帶有之相依性，而無關於稍後反覆之述詞值。此情形反映於ConditionalStop指令之參數中。

圖6A及圖6B中之樣本程式碼突顯了非推測性向量分割與推測性向量分割之間的差異。更特定而言，在實例2A中，讀取記憶體，且在ConditionalStop之前計算述詞。分割迴圈在ConditionalStop指令之後開始。然而，在實例2B中，ConditionalStop指令係在分割迴圈內部執行，且用來辨識使較早操作無效之相依性。在兩種狀況下，GeneratePredicates指令計算述詞，該等述詞控制著哪些元素被用於分割迴圈之剩餘部分。

基於記憶體之迴圈帶有之相依性

在先前實例中，編譯器能夠確定在編譯時不存在位址混淆。然而，常常難以或不可能做出此等判定。下文在實例3中所展示之程式碼片段說明了在Macroscalar架構之各種實施例中如何處理在整個記憶體中發生的迴圈帶有之相依性(其可包括混淆)。

實例3：程式碼迴圈3

for(x=0；x<KSIZE；++x) { r=C[x]； s=D[x]； A[x]=A[r]+A[s]； }

在實例3之程式碼片段中，編譯器不能判定A[x]是否與A[r]或A[s]混淆。然而，在Macroscalar架構下，編譯器簡單地插入使硬體在執行階段檢查記憶體危障的指令並因此在執行階段分割向量以確保正確之程式行為。檢查記憶體危障之一種此指令為下文描述之CheckHazardP指令。

dest=CheckHazardP(first,second,pred)

CheckHazardP指令檢查對應於兩個記憶體操作之記憶體位址(或索引)的兩個向量以找到在整個記憶體中的潛在資料相依性。向量「第一」保存第一記憶體操作之位址，且向量「第二」保存第二操作之位址。述詞「pred」指示或控制「第二」中之哪些元素將被操作。當純量迴圈反覆在時間上前進時，表示順序反覆之向量元素自左至右在向量中出現。CheckHazardP指令可在此內容脈絡中評估。該指令可計算一表示相應對的第一與第二記憶體操作之間的記憶體危障的DIV。指令可正確地評估讀取後寫入、寫入後讀取以及寫入後寫入記憶體危障。

如同上文描述之ConditionalStop指令一樣，對應於產生被取決於之資料的反覆之元素位置可儲存於目的地向量中的對應於取決於該資料之反覆的元素位置處。若不存在資料相依性，則零可儲存於目的地向量中的對應於不具有相依性之反覆之元素位置處。舉例而言：入口：first={2 3 4 5 6 7 8 9}

second={8 7 6 5 4 3 2 1}

pred={1 1 1 1 1 1 1 1}

出口：dest={0 0 0 0 3 2 1 0}

如上文所展示，第一向量(「第一」)之元素5及第二向量(「第二」)之元素3皆存取陣列索引6。因此，3儲存於DIV之位置5中。同樣，第一向量之元素6及第二向量之元素2皆存取陣列索引位置7，使得將把2儲存於DIV之位置6中，等等。在不存在資料相依性的情況下，將零儲存於DIV中。

在一些實施例中，CheckHazardP指令可考慮到資料類型之各種大小。然而，為了清楚起見，吾人僅使用陣列索引類型來描述指令之功能。

上文實例中之記憶體存取具有三個記憶體危障。然而，在所描述之實施例中，可僅需要兩個分割來安全地處理相關聯之記憶體操作。更特定而言，處置元素位置3上的第一危障使後續的對較低或相同編號之元素位置之相依性無關緊要。舉例而言：入口條件：//DIV={0 0 0 0 3 2 1 0}

//p2={0 0 0 0 0 0 0 0}

p2=GeneratePredicates(p2,DIV)；//p2={1 1 1 1 0 0 0 0}

P2=GeneratePredicates(p2,DIV)//p2={0 0 0 0 1 1 1 1}

下文在偽碼中展示由所述實施例用以分析DIV以判定一向量應在何處斷開的程序。在一些實施例中，處理器102之向量執行單元204可平行地執行此計算。舉例而言：List=<empty>； for(x=STARTPOS；x<VECLEN；++x) { If(DIV[x]in List) Break from loop； Else if(DIV[x]>0) Append<x>to List； }

在區間[STARTPOS,x)內可安全地平行處理向量，其中x為其中DIV[x]>0之位置。亦即，自STARTPOS直至(但不包括)位置x，其中STARTPOS指代在先前處理之元素集合之後的第一向量元素。若先前處理之元素之集合為空，則STARTPOS在第一元素處開始。

在一些實施例中，可在程式碼中使用ConditionalStop及/或CheckHazardP指令產生多個DIV。然而，GeneratePredicates指令使用單一DIV來分割向量。存在用於處理此情形之兩種方法：(1)分割迴圈可經巢套；或(2)DIV可經組合並用於單一分割迴圈中。任一方法皆產生正確結果，但最佳方法取決於討論中之迴圈的特性。更具體而言，在預期多個DIV不具有相依性的情況下，諸如當編譯器就是不能判定輸入參數上之混淆時，此等實施例可將多個DIV組合成一個，因此減少分割額外負擔。另一方面，在預期許多已實現之記憶體危障的狀況下，此等實施例可使分割迴圈巢套，藉此提取可能的最大平行性(假定預期有額外平行性)。

在一些實施例中，可使用如下文所展示之VectorMax(A,B)指令來組合DIV。

i2=CheckHazardP(a,c,p0)；//i2={0 0 2 0 2 4 0 0}

i3=CheckHazardP(b,c,p0)；//i3={0 0 1 3 3 0 0 0}

ix=VactorMax(i2,i3)；//ix={0 0 2 3 3 4 0 0}

因為DIV之元素應僅含有小於該元素之位置的數目(其表示較早時間之相依性)，所以稍後相依性僅用來進一步約束分割，自GeneratePredicates指令之觀點來看，此使較低值為冗餘的。因此，選取所有DIV之最大值有效地使GeneratePredicates指令傳回元素集合之可安全地平行處理的交集。

圖7為一說明實例向量化程式碼之一項實施例的圖。更特定而言，圖7中所展示之程式碼樣本為實例3(如上文所呈現)中之程式碼的向量化版本。參看圖7，在C[]或D[]與A[]之間不存在混淆，但對A[]之操作可能彼此混淆。若編譯器不能夠排除與C[]或D[]之混淆，則編譯器可產生額外危障檢查。因為在此狀況下不存在混淆之危險，所以對陣列C[]及D[]之讀取操作已被定位於向量分割迴圈之外，而對A[]之操作保持在分割迴圈內。若實際上不存在與A[]之混淆，則分割保持完整向量大小，且分割迴圈簡單地通過(fall through)而不反覆。然而，對於確實發生混淆的反覆，分割迴圈分割向量以考慮到資料相依性，藉此確保正確操作。

在圖7之程式碼片段中所展示之實施例中，跨越位址之整個向量執行危障檢查。然而，在一般狀況下，常常有必要在條件執行之記憶體操作之間檢查危障。CheckHazardP指令選取指示第二記憶體操作之哪些元素為作用中的一述詞。若並非第一操作之所有元素皆為作用中的，則可用對應於第一運算元之作用中的彼等元素的調零述詞而述詞化CheckHazardP指令自身。(注意，對於第一記憶體操作經述詞化的狀況，此可產生正確結果。)

下文在實例4中之程式碼片段說明了在陣列E[]上具有記憶體危障之迴圈。該程式碼片段有條件地讀取並寫入至陣列中的不可預測位置。在圖8中，展示一說明實例向量化程式碼之一項實施例的圖。更特定而言，圖8中所展示之程式碼樣本為實例4(如上文呈現)中之程式碼的一向量化Macroscalar版本。

實例4：程式碼迴圈4

j=0； for(x=0；x<KSIZE；++x) { f=A[x]； g=B[x]； if(f<FACTOR) { h=C[x]； j=E[h]； } if(g<FACTOR) { i=D[x]； E[i]=j； } }

參看圖8，向量化迴圈包括分別指示是否要讀取或寫入陣列E[]的述詞p1及p2。CheckHazardP指令檢查位址之向量(h及i)以尋找記憶體危障。參數p2被傳遞至CheckHazardP，作為控制第二記憶體操作(寫入)的述詞。因此，CheckHazardP識別在無條件讀取與p2上述詞化的有條件寫入之間的記憶體危障。CheckHazardP之結果在p1中被零述詞化。此針對將不會自E[]讀取的元素位置而將零置於DIV(ix)中。應記得，零指示無危障。因此，儲存於ix中之結果為表示p1上述詞化之有條件讀取與p2上述詞化的有條件寫入之間的危障的DIV。此係可能的，因為非危障條件藉由DIV中之零來表示。

應注意在上述實施例中，為了檢查基於記憶體之危障，使用CheckHazardP指令。如上文所描述，CheckHazardP指令選取一述詞作為一控制第二向量中之哪些元素被操作的參數。然而，在其他實施例中，可使用其他類型之CheckHazard指令。舉例而言，如下文各種實例中所使用，視特定所要之程式碼實施而定，可使用省略述詞參數之CheckHazard指令。在一實施例中，此版本之CheckHazard指令可簡單地對兩個輸入向量無條件地操作。不管使用CheckHazard指令之哪種版本，應注意，如同支援結果述詞化及/或調零之任一Macroscalar指令一樣，是否藉由執行CheckHazard指令來修改結果向量的給定元素可透過使用述詞向量或調零向量來單獨地加以控制，如上文所描述。亦即，CheckHazardP指令之述詞參數控制著指令執行的與上文描述之一般述詞/調零向量不同之態樣。

偵測在述詞產生指令之後的第一反向分支

如上文所描述，當向量化一程式碼片段時，可在程式碼中使用執行向量化以正確地處置可能之迴圈帶有之相依性(諸如，記憶體危障)的向量分割迴圈。在此程式碼中，諸如CheckHazard指令(上文描述)之Macroscalar指令(例如)可產生一可能稍後由Macroscalar GeneratePredicates指令(其為向量分割迴圈之部分)使用的DIV。另外，向量分割迴圈使用一反向分支作為迴圈之部分。如上文所提及，若此反向分支被準確地預測，則處理器效能可得以維持。然而，若此分支被不良地預測(在許多狀況下係這樣)，則效能可受損失。因此，在某些狀況下抑制對分支之預測並等待DIV變得可用可係有益的。亦即，在一些情形中，實際上停止執行直至DIV可用的不利結果可小於錯誤預測形成向量分割迴圈之邊界的分支之不利結果。

作為可能受益於此處描述之技術的向量分割迴圈之特定實例，下文在實例5中展示產生直方圖A[]的程式碼片段之實例，該直方圖A[]代表B[]中之項。

實例5

for(x=0；x<K；++x)A[B[x]]=A[B[x]]+1；當編譯器將實例5之程式碼片段向量化時，其必須辨識B[]之向量中的任何元素是否含有相同值。若此未被執行，則程式碼將不會辨識出A[]中之哪些元素將被修改，從而影響稍後對同一向量中的A[]之修改。實例6中展示Macroscalar程式碼片段，其包括處置實例5之程式碼片段中之任何迴圈帶有之相依性的向量分割迴圈。

實例6

p1=FALSE；V0=VectorRead(B,x)； V2=CheckHazard(V0,V0)；//計算DIV

PartLoop：p1=GeneratePredicates(p1,V2)；p1：V1=VectorRead(A,V0)；p1：V1=VectorIncr(V1)；p1：VectorWrite(A,V1)；Branch on Carry-Clear to PartLoop

在實例6之程式碼片段中，CheckHazard指令評估記憶體位址以偵測記憶體危障(產生儲存於V2中之DIV)，且GeneratePredicates指令使用此資訊來計算一控制可安全地平行處理之元素之數目的述詞。若整個向量不能被安全地平行處理，則向量分割迴圈(PartLoop)反覆直至已處理一完整向量(此由諸如正被設定之進位旗標之處理器旗標中之一者表示)為止。

即使在迴圈中實際上不存在記憶體危障時，編譯器也常常不能在編譯時確實地判定此狀況。因此，整個向量常常在執行階段被平行處理，即使編譯器被迫發出一向量分割迴圈亦然。習知分支預測器在此狀況下可有效地操作，從而預測迴圈將從不反覆，且完全的效能得以維持。

然而，在向量被頻繁地分割之狀況下，習知分支預測器常常不良地預測，從而不利地影響效能。因為向量分割迴圈之性質，此可為有害的。向量分割迴圈通常將含有一串行地彼此依賴之指令鏈結。此程式碼區段的效能因此可由串行程式碼約束，即使分支預測極佳亦然。如上文所描述，對於不良地預測分支，存在效能上的不利結果，且歸因於迴圈之性質，良好的預測之好處受到限制。此外，在分割迴圈實際上不止一次地反覆之狀況下，其將僅反覆有限次數(通常僅反覆幾次)。在此等狀況下，此可導致高錯誤預測率，從而不利地影響功率及效能兩者。因此，向量分割迴圈之分支預測準確度可至關重要。因此，如下文進一步描述，視預測準確度之所接收指示而定，一偵測到在述詞產生指令之後的第一反向流程控制指令，便可抑制對該流程控制指令之預測直至DIV變得可用。

在圖9中，展示一描繪圖2之處理器之一項實施例在形成向量分割迴圈之程式指令之執行期間的操作的流程圖。共同地參看圖2至圖9，且從圖9之區塊901開始，分支預測單元210偵測在一述詞產生指令之後的第一條件反向分支指令。更特定而言，在一實施例中，條件反向分支指令可為一條件分支指令，其分支至在該分支指令之前的目標位址(例如，至向量分割迴圈之開始點)，且該條件分支指令在一條件陳述式評估為真時分支。在實例6中所展示之實施例中，條件陳述式取決於進位清除條件碼。另外，述詞產生指令可為一如上文所述可建立取決於一相依性向量(諸如DIV)之一述詞向量的Macroscalar GeneratePredicates指令。在一實施中，在GeneratePredicates指令之後偵測到的反向分支指令可為一基於一由Macroscalar CheckHazard指令或Macroscalar ConditionalStop指令設定之條件碼的分支指令，上文詳細描述了Macroscalar CheckHazard指令及Macroscalar ConditionalStop指令兩者。應注意，儘管結合實例6使用Macroscalar CheckHazard指令，但考量到可(例如)替代地使用Macroscalar CheckHazard指令之其他版本(諸如述詞化CheckHazardP指令)。

如上文所描述，分支預測單元210可產生並維持針對各種分支預測之預測準確度資訊。因此，分支預測單元210可經組態以產生及/或接收反向分支指令之預測準確度之指示(區塊903)。在一實施中，準確度指示可為指示準確度之準確度值，而在其他實施中，準確度指示可為指示預測準確度是否滿足一預定準確度臨限值的二進位信號。

在各種實施例中，為了抑制預測之目的判定給定分支是否被準確地預測的臨限值可為一隱含或硬編碼值、一可經由韌體或程序之測試模式操作加以修改的值，或一可由軟體自由修改之值。臨限值可以不同方式為固定的或被允許由於執行階段行為而動態改變。在一些實施例中，可針對分支之不同執行個體單獨地維持不同臨限值，(例如)作為與由分支預測單元210維持的分支歷史表中之給定分支相關聯的統計資料之部分。或者，如上文所提及，分支預測單元210可簡單地儲存關於給定分支是被準確地預測抑或未被準確地預測之二進位指示，而非明確地儲存用於不同分支之一臨限值。

在一實施例中，回應於判定反向分支指令之預測準確度不滿足預定臨限值，分支預測單元210可經組態以抑制預測直至DIV可用為止(區塊905)。更特定而言，因為DIV資訊指示迴圈將反覆的確切次數，所以在一實施例中，分支預測單元210可經組態以使用DIV資訊來預測任何將來的分支。舉例而言，DIV可指示一向量可能要求通過迴圈三遍。透過使用此資訊，分支預測單元210可避免錯誤預測反向分支，因為可自DIV確定地知曉迴圈反覆之數目。

在一實施中，分支預測單元210可在等待DIV之同時停止管線，藉此防止任何額外指令被提取。在另一實施中，分支預測單元210可使處理器102在等待DIV可用的同時切換內容脈絡。在另一實施例中，當DIV資訊可用時，分支預測單元210可發送一迴圈提取通知至提取單元201。回應於該指示，提取單元201可使用DIV資訊來載入用於向量分割迴圈之每一反覆的指令。

應注意，等待DIV變得可用可實質上等效於等待控制分支之條件碼變得可用，因為DIV及條件碼皆由同一指令產生。此允許處理器102之提取單元201基於條件碼即刻重新繼續提取，儘管其可能花費若干循環來分析DIV並相應地組態分支預測單元210。在管線被停止以等待DIV的狀況下，此可最小化管線停止。亦應注意，在一實施例中，可繼續針對此分支追蹤分支預測之準確度，即使該分支被抑制且DIV資訊被使用亦然。此可允許分支預測單元210偵測預測之準確度何時滿足臨限值，並改變其操作模式以預測分支而非等待DIV變得可用。亦即，在稍後時間若準確度改良，則基於不良準確度而抑制對給定分支之預測的決策可被推翻。

儘管上文已相當詳細地描述了實施例，但熟習此項技術者一旦完全理解以上揭示內容便將顯而易見眾多變化及修改。意欲將以下申請專利範圍解譯為涵蓋所有此等變化及修改。進一步意欲：可以任一合適組合實踐以下申請專利範圍中之相容者，且特定地意欲在本文中明確地揭示此等組合。

Claims

一種方法，其包含：偵測在一述詞產生指令之後的一第一條件分支指令，其中該第一條件分支指令在被選取時反向分支，且其中該述詞產生指令在被執行時產生取決於一相依性向量的一述詞向量，其中該相依性向量之每一元素包括指示一資料相依性是否存在於一向量指令之元素之間的一索引；接收該第一條件分支指令之一預測準確度之一指示；及回應於基於該預測準確度之該指示而判定該第一條件分支指令之該預測準確度不滿足一臨限值，抑制對該第一條件分支指令之預測直至該述詞產生指令所取決於的該相依性向量可用為止。
如請求項1之方法，其進一步包含回應於偵測到該相依性向量可用，使用該相依性向量中指示之資料相依性資訊來預測該第一條件分支指令。
如請求項1之方法，其中該述詞產生指令為一Macroscalar GeneratePredicates指令。
如請求項1之方法，其中抑制對該第一條件分支指令之預測包括：預測該第一條件分支指令及捨棄該預測。
如請求項1之方法，其中抑制對該第一條件分支指令之預測包括：防止新指令被執行直至該相依性向量可用為止。
如請求項1之方法，其中抑制對該第一條件分支指令之預測包括：捨棄程式指令執行之控制流程不被該第一條件分支指令之執行改變的一先前產生之預測。
如請求項1之方法，其進一步包含在該相依性向量變得可用時使用該相依性向量來判定回應於該第一條件分支指令之每一執行而改變程式指令執行之控制流程的一次數。
如請求項1之方法，其中抑制對該第一條件分支指令之預測包括：防止新指令被提取至一執行管線中直至該相依性向量變得可用為止。
如請求項1之方法，其中抑制對該第一條件分支指令之預測包括：防止新指令被執行直至該相依性向量可用為止。
一種處理器，其經組態以執行如請求項1至9中任一項的方法。
一種處理器，其包含：一提取單元，其經組態以選擇性地提取用於執行之指令；及一預測單元，其耦接至該提取單元並經組態以偵測在一述詞產生指令之後的一第一條件分支指令，其中該第一條件分支指令在被選取時反向分支，且其中該述詞產生指令在被執行時產生取決於一相依性向量的一述詞向量，其中該相依性向量中之每一元素包括指示一資料相依性是否存在於一向量指令之元素之間的一索引；其中該預測單元經組態以產生該第一條件分支指令之一預測準確度之一指示；且其中該預測單元經組態以回應於判定該第一條件分支指令之該預測準確度不滿足一臨限值，抑制對該第一條件分支指令之預測直至該述詞產生指令所取決於的該相依性向量可用為止。
如請求項11之處理器，其中該預測單元經組態以回應於接收到該相依性向量中所指示之資料相依性資訊而預測該第一條件分支指令。
如請求項11之處理器，其中該提取單元經組態以在等待該相依性向量可用的同時停止。
如請求項11之處理器，其進一步包含耦接至該提取單元並經組態以在等待該相依性向量可用的同時切換內容脈絡的一執行單元。
如請求項11之處理器，其中該預測單元經組態以產生對該第一條件分支之一預測，且其中為了抑制對該第一條件分支之預測，該預測單元經組態以回應於判定該第一條件分支指令之該預測準確度不滿足該臨限值而捨棄對該第一條件分支指令之該預測。
如請求項11之處理器，其中該第一條件分支指令界定一指令迴圈之一邊界，且其中該相依性向量指示該指令迴圈將被執行的一確切次數。
如請求項16之處理器，其中回應於偵測到該相依性向量可用，該預測單元經組態以提供一迴圈提取指示，且其中該提取單元經組態以回應於接收到該迴圈提取指示而提取用於該指令迴圈之每一反覆的指令。
如請求項11之處理器，其中為了抑制對該第一條件分支指令之預測，該預測單元經進一步組態以防止新指令之執行直至該相依性向量可用為止。
如請求項11之處理器，其中該述詞產生指令為一Macroscalar GeneratePredicates指令。
一種系統，其包含：一記憶體，其經組態以儲存程式指令；及如請求項11至19中任一項的處理器之一或多個例項，其耦接至該記憶體。