假想分支目標地址高速緩存分支的裝置、系統及方法

2023-05-14 15:21:11 4

專利名稱：：假想分支目標地址高速緩存分支的裝置、系統及方法
技術領域：
：本發明涉及微處理器(microprocessor)的分支預測(branchprediction)的
技術領域：
，尤指分支目標地址(branchtargetaddress)的快取技術，特別涉及一種假想混合分支方向預測裝置。
背景技術：
：計算機指令一般都儲存於內存內可尋址的相連位置。中央處理單元(CentralProcessingUnit，CPU)或處理器由相連的內存位置提取這些指令，並加以執行。CPU從內存每提取一個指令，其內的程序計數器(programcounter，簡稱PC)或指令指針(instructionpointer，簡稱IP)就會遞增，使其內含序列(sequence)中下個指令的地址，此即為下個循序指令指針(nextsequentialinstructionpointer，簡稱NSIP)。指令的提取、程序計數器的遞增以及指令的執行便通過內存呈線性持續進行，直到遇到程控指令(programcontrolinstruction)為止。程控指令也稱為分支指令(branchinstruction)，在執行時會改變程序計數器內的地址，並改變控制的流程。換言之，分支指令指定了改變程序計數器內容的條件。因執行一分支指令使程序計數器的值改變，會導致指令執行順序的中斷。這是數字計算機的一項重要特徵，因為它提供對程序執行流程的控制，以及分支至程序的不同部分的能力。程控指令的例子包括跳轉(jump)、條件跳轉(conditionaljump)、調用(call)以及返回(return)。跳轉指令使CPU無條件地將程序計數器的內容改變至一特定值，這個值就是程序要繼續執行的指令所在的目標地址。條件跳轉指令使CPU去測試一狀態緩存器(statusregister)的內容，或者可能比較兩個值，而後基於測試或比較的結果，不是繼續循序執行就是跳轉至一新地址，稱為目標地址。調用指令使CPU無條件地跳轉至一新目標地址，而且儲存程序計數器的值以使CPU可返回至先前離開的程序位置。返回指令使CPU去擷取程序計數器於前次調用指令執行時所存的值，並使程序流程返回至所擷取的指令地址。對早期的微處理器而言，程控指令的執行並不會造成處理上顯著的延遲，因為這些微處理器被設計為一次只執行一個指令。如果所執行的指令是程控指令，在執行完畢之前，微處理器會知道它是否要分支，而如果是的話，它會知道分支的目標地址為何。因此，不論下個指令是循序的，或是分支的結果，皆會被提取和執行。現代的微處理器則非如此單純。相反地，對現代的微處理器來說，在微處理器的不同區塊或流水線階段(pipelinestage)內同時處理數個指令乃很平常的事。Hennessy與Patterson將流水線化(pipelining)定義為「一種多個指令得以重疊執行的實作技術。」(引述自ComputerArchitectureAQuantitativeApproach，2ndedition，byJohnL.HennessyandDavidA.Patterson，MorganKaufmannPublishers，SanFrancisco，CA，1996)作者接著對流水線化做了下列精彩的說明「一個流水線就像是條裝配線。在汽車的裝配線上，有許多步驟，每個步驟對汽車的製造都有所貢獻。每個步驟與其它步驟同時並行，然而是在不同的汽車上進行。在一計算機流水線中，每個步驟完成一個指令的部分，就像裝配線，不同的步驟並行地完成不同指令的不同部分。每個這些步驟稱為一管道階段(pipestage)或管道區段(pipesegment)。這些階段一個連接著下一個，形成一個管道——指令從一端進入，歷經這些階段，然後從另一端出去，就像汽車在裝配線上一樣。」因此，當指令被提取時，就被導入流水線的一端。指令於微處理器中歷史流水線階段，直到執行完畢。在這種流水線化的微處理器中，一分支指令是否會改變程序流程，通常都得等它到達流水線的後期階段才能得知。然而在這之前，微處理器已經提取了其它指令，且正於流水線的早期階段執行。如果一分支指令改變了程序流程，所有在這分支指令之後進入流水線的指令都必須被丟棄。此外，則必須提取此分支指令的目標地址上的指令。丟棄已在執行中的指令及提取目標地址上的指令，會造成微處理器在處理上的延遲，稱為分支懲罰(branchpenalty)。為減輕這種延遲問題，許多流水線化的微處理器在流水線的一早期階段使用分支預測機制來預測分支指令。分支預測機制預測分支指令的結果或方向，即是否要進行分支。分支預測機制也預測分支指令的分支目標地址，即分支指令所要分支到的指令的地址。處理器接著就分支至所預測的分支目標地址，即依據分支預測提取後續的指令，這會比沒有分支預測時來得早，因而若確定要進行分支，因此便降低了懲罰的可能性。這種用來快取先前所執行分支指令的目標地址的分支預測機制，稱為分支目標地址高速緩存(branchtargetaddresscache，簡稱BTAC)或者分支目標緩衝器(branchtargetbuffer，簡稱BTB)。在一簡單的BTAC或BTB中，當處理器對一分支指令進行解碼後，處理器便提供分支指令的地址給BTAC。若該地址命中BTAC且預測分支會進行，處理器就可以利用BTAC中的快取目標地址開始提取目標地址的指令，而非下個循序(sequential)地址的指令。相較於只預測是否採用分支的預測裝置，像是分支歷史表(branchhistorytable，簡稱BHT)，BTAC的好處是除了確定是否遇到一分支指令所需的時間外，它節省了計算目標地址所需的時間。典型的做法是分支預測數據(例如被採用/不被採用(taken/nottaken))隨著目標地址皆儲存於BTAC。BTAC運用於流水線的指令解碼階段，這是因為處理器必須先判斷分支指令是否存在。處理器使用BTB的一個例子是IntelPentiumII與PentiumIII處理器。現請參閱圖1，其繪示PentiumII/III處理器100相關部分的方塊圖。處理器100包括一BTB134，用來快取分支目標地址。處理器100從一指令高速緩存(instructioncache)102提取指令，該指令高速緩存102快取了指令108與前解碼(pre-decoded)分支預測數據104。前解碼分支預測數據104可能包括像是指令類型或指令長度這樣的訊息。指令從指令高速緩存102提取，並送到指令解碼邏輯(instructiondecodelogic)132，由其來解碼或解譯指令。一般是從下個循序提取地址112來提取指令。該下個循序提取地址112是由遞增裝置(incrementer)118將現行指令高速緩存102的提取地址122直接加上一指令高速緩存102的快取線的大小所得。然而，如果一分支指令已由指令解碼邏輯132解碼，接著控制邏輯(controllogic)114便選擇性地控制一多工器(multiplexer)116選取BTB134所提供的分支目標地址，作為指令高速緩存102的提取地址122，而非選取下個循序提取地址112。控制邏輯114根據指令高速緩存102提供的前解碼數據104以及BTB134預測該分支指令是否會被採用(依用來檢索BTB134的指令指針138而定)，來選取指令高速緩存102的提取地址122。PentiumII/III在檢索BTB134時，並非通過分支指令本身的指令指針，而是利用先於被預測的分支指令的指令的指令指針138來進行。這使得BTB134在分支指令被解碼的時，就能查詢目標地址136。否則，在分支指令解碼後，處理器100必須再等待BTB134的查詢，才能進行分支，這樣便多了此延遲的分支懲罰。一旦分支指令被指令解碼邏輯132解碼，且處理器100知道目標地址136的產生是基於確定有分支指令的存在，處理器100才會分支到BTB134根據指令指針138索引所提供的目標地址136。另一個使用BTAC的例子是AMDAthlon處理器。現請參閱圖2，其繪示Athlon處理器200相關部分的方塊圖。處理器200包括與圖1PentiumII/III編號類似的組件。Athlon處理器200將其BTAC整合進指令高速緩存202中。也就是，指令高速緩存202除了指令資料108與前解碼分支預測數據104的外，還快取了分支目標地址206。對於每個指令字節對(instructionbytepair)，指令高速緩存202保留了兩個位作為預測分支指令的方向的用。指令高速緩存202在一快取線中，相當於每16個字節的指令即保留兩個分支目標地址的空間。從圖2可以看出，指令高速緩存202是由提取地址下個循序提取地址來作索引。因BTAC已整合進指令高速緩存202，所以也是由提取地址122來作索引。因此，指令高速緩存202的一快取線若有一命中發生，就可確定快取分支目標地址對應至存在於被檢索的指令高速緩存202快取線中一分支指令。雖然現有的方法改進了分支預測，但仍有缺點。前述兩種現有方法的一個缺點是，指令前解碼數據以及Athlon例子中的分支目標地址大幅增加了指令高速緩存的大小。據推測，對Athlon而言，分支預測數據可能使指令高速緩存的大小加倍。此外，PentiumII/IIIBTB為每個分支指令儲存了相當大量的分支歷史數據，用以預測分支方向，因而也增加了BTB的大小。Athlon的整合式BTAC的一個缺點是，將BTAC整合進指令高速緩存會使空間的使用缺乏效率。也就是，整合式的指令高速緩存/BTAC對於分支指令以及非分支指令，皆須快取其分支指令數據，因而佔用過多儲存空間。在Athlon指令高速緩存中，許多由額外的分支預測數據所使用的空間是浪費掉的，這是因為指令高速緩存中分支指令的集中度相當低。例如，一特定的指令快取線中可能未包括任何分支，因此快取線中所有儲存目標地址與其它分支預測數據的空間就沒用到而浪費掉了。Athlon整合式的BTAC的另一個缺點是，設計目標間的衝突。也就是，關於指令高速緩存的大小，除了分支預測機制的設計目標外，可能有其它不同的設計目標會對此加以規定。以快取線而論，要求BTAC的大小要與指令高速緩存相同，是Athlon架構所固有的，但可能無法理想地達到兩組設計目標。例如，可能選定了指令高速緩存的大小，以達成一特定的快取命中率(cache-hitratio)。然而，情況可能是，用比較小的BTAC，就可能達成所要的分支目標地址預測率(predictionrate)。再者，因為BTAC是整合在指令高速緩存中，獲得快取分支目標地址所需的資料存取時間必然相同於獲得快取指令字節。Athlon的例子中，指令高速緩存相當大，存取時間可能會相當長。較小的、非整合式BTAC的資料存取時間可能比整合式的指令高速緩存/BTAC要明顯減少。由於PentiumII/IIIBTB並未整合在指令高速緩存中，PentiumII/III的方法不會遭遇前述Athlon整合式指令高速緩存/BTAC的問題。然而，由於在檢索PentiumII/IIIBTB時，乃利用一已解碼指令的指令指針，而非指令高速緩存的提取地址，所以PentiumII/III的解決方案於進行分支時可能無法像Athlon解決方案那樣早，因此可能也無法那樣有效地減少分支懲罰。PentiumII/III解決方案處理這個問題的方式是，使用一先前指令或先前指令群的指令指針，而非實際的分支指令指針，來檢索BTB，如前所述。然而，PentiumII/III方法的一個缺點是，使用先前指令的指令指針而非實際的分支指令指針，會犧牲掉一些分支預測的準確度。準確度的降低，一部份是由於分支指令在程序中可能經由多個指令路徑遭遇到。也就是，多個先於分支指令的指令可能因相同的分支指令而快取於BTB中。因此，為了這樣一個分支指令，必須消耗掉BTB中多個項目(entry)，於是就減少了BTB中可快取的分支指令總數。所用的先於分支指令的指令數量愈多，可到達分支指令的路徑也愈多。除此之外，由於使用一先前的指令指針造成可能有多個路逕到達同一個分支指令，PentiumII/IIIBTB中的方向預測裝置可能需要更長的時間來「暖機」(warmup)。PentiumII/IIIBTB保持著分支歷史數據，用以預測分支的方向。當一新的分支指令被引入處理器且快取住，到達該分支指令的多個路徑可能會使分支歷史在更新時，變得比只有單路逕到達該分支指令的情形還慢，造成預測較不準確。因此，我們所需要的是，一種能有效利用晶片固有資源(chiprealestate)，又能在流水線早期就提供準確分支的分支預測裝置，以減少分支懲罰。
發明內容本發明的目的在於提供一種分支預測方法及裝置，能有效利用晶片固有資源，又能在流水線早期就提供準確的分支，以減少分支懲罰。於是，為達到前述目的，本發明的一項特徵是，在一微處理器中提供一種分支裝置，利用一提取地址選取一指令高速緩存的一快取線。該裝置亦使用該提取地址假想預測一分支指令是否將被採用(taken)。該分支指令可能潛在地(potentially)存在於該指令快取線中。該裝置包括一第一預測裝置(predictor)，對應至該提取地址，以依據該提取地址預測該分支指令是否將被採用。該裝置亦包括一邏輯，對應至該提取地址，以提供該提取地址與一全域分支歷史(globalbranchhistory)的一二進位函數(binaryfunction)於此邏輯的一輸出端。該裝置亦包括一第二預測裝置，對應至該邏輯的輸出端，以依據該邏輯輸出預測該分支指令是否將被採用。該裝置亦包括一選擇器(selector)，對應至該提取地址，以依據該提取地址選取該第一與第二預測裝置其中之一。另一方面，本發明的一項特徵是，在一具有一指令高速緩存的流水線化微處理器中提供一種假想分支預測裝置。該指令高速緩存接收一地址總線(addressbus)上的一提取地址，以選取該指令高速緩存的一快取線。一分支指令被假定存在於該快取線中。該裝置包括一假想分支歷史表(BHT)，提供該分支指令的一第一方向預測。該裝置亦包括一分支目標地址高速緩存(BTAC)，對應至該地址總線，提供該分支指令的一第二方向預測，並提供一選擇預測，用以在第一與第二方向預測間作選擇。該裝置亦包括一多工器，對應至該BHT與該BTAC，依據該選擇預測選取第一與第二方向預測其中之一。第二方向預測系響應該提取地址而提供，即使該分支指令可能並不存在於該指令快取線中。另一方面，本發明的一項特徵是，在一微處理器中提供一假想分支目標地址高速緩存(BTAC)。該BTAC包括一數組(array)，以儲存分支指令的方向預測。該BTAC亦包括一輸入，對應至該數組，接收一指令高速緩存的提取地址。該提取地址檢索該數組以選取方向預測其中之一。該BTAC亦包括一輸出，對應至該數組，提供所選取的方向預測至分支控制邏輯(branchcontrollogic)。若所選取的方向預測指定一採用方向，則不管是否有一分支指令存在於提取地址所檢索的指令高速緩存的一快取線中，該分支控制邏輯皆使微處理器進行假想分支。另一方面，本發明的一項特徵是，提供一種用於假想分支的微處理器。該微處理器包括一指令高速緩存，以提供一地址總線上的一提取地址所選取的一指令字節線(lineofinstructionbytes)。該微處理器亦包括一假想分支歷史表(BHT)，對應至該地址總線，提供一分支指令是否將被採用的一第一預測，該分支指令被假定存在於該指令快取線。該第一預測系依據該提取地址與一全域分支歷史的組合而提供。該微處理器亦包括一假想分支目標地址高速緩存(BTAC)，對應至該地址總線，以提供該假定的分支指令的一第二預測，並提供一選擇器。該微處理器亦包括控制邏輯，對應至該BHT與BTAC，若選擇器所選取的第一與第二預測其中之一預測該假定的分支指令將被採用，則使微處理器進行假想分支。另一方面，本發明的一項特徵是，提供一種在一微處理器中進行假想分支的方法。該方法包括產生一指令的數個假想分支方向預測，選取該數個假想分支方向預測的一作為一最後(final)方向預測，以及若該最後方向預測指出該指令將被採用，則使微處理器進行假想分支。該產生、選取以及假想分支的動作皆在解碼該指令之前執行。另一方面，本發明的一項特徵是，提供一種在一微處理器中進行假想分支的方法。該方法包括產生一分支指令是否將被採用的第一與第二預測，以響應於一指令高速緩存提取地址的第一與第二二進位函數。該方法亦包括選取該第一與第二預測其中之一作為一最後預測。該選取的動作是響應該提取地址的一第三二進位函數而執行。該方法亦包括若該最後預測指出該分支指令將被採用，則微處理器即進行假想分支。不論該分支指令是否存在於該提取地址所選取的一指令快取線中，該產生、選取以及假想分支的動作皆被執行。本發明的一項優點是，提供一種混合的方式，以對於混雜高度不相依(independent)與高度相依(dependent)的分支，假想地預測其分支方向，以改進假想分支的方向預測的準確性，用來降低整體的分支懲罰。本發明的其它特徵與優點，在考察本說明書其餘部分與附圖後，將可更加明白。圖1為PentiumII/III處理器先前技術的相關部分方塊圖。圖2為Athlon處理器先前技術的相關部分方塊圖。圖3為依本發明的流水線化微處理器的方塊圖。圖4為依本發明圖3處理器的假想分支預測裝置。圖5為圖4的指令高速緩存的方塊圖。圖6為依本發明圖4分支目標地址高速緩存(BTAC)的方塊圖。圖7為依本發明圖4BTAC的圖6項目的格式的方塊圖。圖8為依本發明的圖4假想分支預測裝置的運作的流程圖。圖9為依本發明的圖4假想分支預測裝置使用圖8步驟的一運作範例的方塊圖。圖10為依本發明的圖4假想分支預測裝置偵測與更正錯誤的假想分支預測的運作流程圖。圖11為依本發明列舉的程序代碼片段及一表格，為說明圖10假想分支預測錯誤的偵測與更正的一範例。圖12為依本發明的圖4分支預測裝置包括一混合假想分支方向預測裝置(hybridspeculativebranchdirectionpredictor)的另一具體實施例的方塊圖。圖13為圖4的雙調用/返回堆棧(dualcall/returnstacks)的運作流程圖。圖14為說明圖4分支預測裝置選擇性地以非假想分支預測來覆蓋(override)假想分支預測，用來改進本發明的分支預測準確度的運作流程圖。圖15為本發明用以進行圖4BTAC中目標地址置換工作裝置的方塊圖。圖16為依本發明圖15裝置的一運作方法的流程圖。圖17為本發明另一具體實施例繪示圖15裝置的一運作方式流程圖。圖18為依本發明的另一具體實施例繪示的用以進行圖4BTAC中目標地址置換動作的裝置方塊圖。圖19為依本發明的另一具體實施例繪示的用以進行圖4BTAC中目標地址置換動作的裝置方塊圖。圖號說明100PentiumII/III處理器102指令高速緩存104前解碼分支預測數據108指令資料112下個循序提取地址114控制邏輯116多工器118遞增裝置122提取地址132指令解碼邏輯134分支目標緩衝器136分支目標地址138指令指針200Athlon處理器202指令高速緩存206快取分支目標地址300流水線化微處理器302I-階段304B-階段306U-階段308V-階段312F-階段314X-階段316R-階段318A-階段322D-階段324G-階段326E-階段328S-階段332W-階段342指令緩衝器344F-階段指令序列346X-階段指令序列352假想分支目標地址353假想返回地址354非假想分支目標地址355非假想返回地址356解析目標地址400假想分支預測裝置402假想分支目標地址高速緩存(BTAC)404控制邏輯406假想調用/返回堆棧408預測檢查邏輯412非假想分支方向預測裝置414非假想調用/返回堆棧416非假想目標地址計算器418比較器422多工器424儲存多工化/緩存器426遞增裝置428比較器432指令高速緩存434加法器436指令格式化與解碼邏輯438假想分支(SB)位442更新信號444非假想分支方向預測446BEG位446AA項目的BEG位446BB項目的BEG位448LEN位452命中信號454假想分支數據(SBI)456ERR信號466下個循序指令指針(NSIP)468現行指令指針(CIP)472控制信號474比較器418的輸出476比較器428的輸出478控制信號481解析分支方向(DIR)482控制信號483控制信號484信號485比較器489的輸出486FULL信號487比較器497的輸出488返回地址489比較器491假想返回地址492指令解碼數據493指令字節494指令字節快取線495提取地址496指令字節497比較器498儲存多工化/緩存器424的輸出499下個循序提取地址502轉換參照緩衝器(TLB)504標誌數組506數據數組508比較器512實際分頁號碼514實際標誌518命中信號602BTAC402的項目602A項目602的A邊602B項目602的B邊604比較器606路選擇多工器608A/B選擇多工器612數據數組614標誌數組616標誌618控制信號622A/B選擇信號624A項目626B項目702VALID位702AA項目的VALID位702BB項目的VALID位704CALL位706RET位708WRAP位712分支方向預測數據(BDPI)714分支目標地址722T/NT欄位722AA項目的T/NT欄位722BB項目的T/NT欄位724SELECT位802-834假想分支的運作步驟1002--1054偵測與更正錯誤的假想分支預測的步驟1100依本發明列舉的程序代碼實例片段及一表格1200混合假想分支方向預測裝置1202分支歷史表(BHT)1204異或邏輯1206全域分支歷史緩存器1208多工器1212分支方向結果1214信號1216異或邏輯1204的輸出1218更新信號1222T/NT_A/B位1224T/NT位1302--1326雙調用/返回堆棧的運作步驟1402--1432BTAC402選擇性地以非假想分支預測來覆蓋假想分支預測的運作步驟1502LastWritten緩存器1504A/BLRU位1506多工器1512更新IP1514信號1516讀/寫控制信號1602--1646A/B項目置換方法的步驟1716--1726另一實施例中A/B項目置換方法的衍生步驟1812額外的數組1902含LastWritten值與LastWrittenPrev值的緩存器1928信號具體實施例方式現請參閱圖3，其繪示本發明的一流水線化微處理器300的方塊圖。處理器流水線300包括階段302至階段332。第一階段是I-階段302，或稱指令提取階段(instructionfetchstage)。在I-階段302，處理器300提供提取地址至一指令高速緩存432(見圖4)，以提取指令供處理器300執行。指令高速緩存432在關於圖4的部分時會更加詳細地說明。在一具體實施例中，此指令高速緩存432是一雙周期(two-cycle)高速緩存。B-階段304是指令高速緩存432的存取的第二階段。指令高速緩存432提供其資料至U-階段306，在此階段資料被閂鎖住(latched)。U-階段306提供指令高速緩存的資料至V-階段308。在本發明中，處理器300還包括一BTAC402(見圖4)，在其餘圖標的部分會詳細說明。BTAC402並未整合在指令高速緩存432。然而，在I-階段302，BTAC402是與指令高速緩存432通過使用指令高速緩存432的提取地址495來平行地(inparallel)存取的(見圖4)，從而致能相當快速的分支以減少分支懲罰。BTAC402提供一假想分支目標地址352，而該地址則被提供至I-階段302。處理器300選擇性地選取目標地址352作為指令高速緩存432提取地址，以達成分支至假想目標地址352，這在其餘圖標的部分會詳加說明。有利地，從圖3可以看出，在U-階段306，由BTAC402所提供的分支目標地址352能使處理器300在流水線300的相當早期就進行分支，如此僅產生一雙周期的指令泡沫(instructionbubble)。即，若處理器300分支至假想目標地址352，只有兩個階段的指令必須被清除。換言之，在兩個周期內，典型的情況下，於U-階段306就可得知分支的目標指令，即，如果這些目標指令存在於指令高速緩存432中。有利地，在多數情況下，雙周期的指令泡沫夠小，可以由一指令緩衝器342、F-階段指令序列344及/或X-階段指令序列346來加以吸收，此將說明於後。因此，在許多情形下，假想BTAC402使處理器300能達到零懲罰的分支。處理器300還包括一假想調用/返回堆棧406(見圖4)，在關於圖4、圖8與圖13的部分有詳細說明。假想調用/返回堆棧406與假想BTAC402協同運作，以產生一假想返回地址353，即，提供至I-階段302的返回指令的目標地址。處理器300選擇性地選取假想返回地址353作為指令高速緩存432提取地址，以達成分支至假想返回地址353，就如關於圖8部分所詳細說明的。在V-階段308，指令被寫入指令緩衝器342。指令緩衝器342暫存指令以提供至F-階段312。V-階段308亦包括解碼邏輯，以提供關於指令字節的數據給指令緩衝器342，像是x86前置(prefix)與modR/M數據，以及指令字節是否為分支運算碼值(branchopcodevalue)。F-階段312，或稱指令格式化階段(instructionformatstage)312，包括指令格式化與解碼邏輯436(見圖4)以格式化指令。最好(preferably)處理器300是一x86處理器，其指令集(instructionset)可容許不同長度的指令。指令格式化邏輯436從指令緩衝器342接收指令字節流(stream)，並將該指令字節流解析成分離的字節群，每個群構成一x86指令，尤其還提供每個指令的長度。F-階段312也包括分支指令目標地址計算邏輯(branchinstructiontargetaddresscalculationlogic)416，依據一指令解碼產生一非假想分支目標地址354，而不是假想地依據指令高速緩存432提取地址來產生，如在I-階段302BTAC402所作的。F-階段312亦包括一調用/返回堆棧414(見圖4)，依據一指令解碼產生一非假想返回地址355，而不是假想地依據指令高速緩存432提取地址來產生，如在I-階段302BTAC402所作的。F-階段312非假想地址354與355被送至I-階段302。處理器300選擇性地選取F-階段312非假想地址354或355作為指令高速緩存432提取地址，以達成分支至地址354或355兩者之一，就如下文所詳細說明的。F-階段指令序列344接收格式化的指令。格式化指令由F-階段指令序列344送至X-階段314中一指令轉換器(instructiontranslator)。X-階段314，或稱轉換階段314，指令轉換器將x86巨指令(macroinstruction)轉換成微指令(microinstruction)，讓其餘的流水線階段可加以執行。X-階段314將轉換過的微指令送至X-階段指令序列346。X-階段指令序列346將轉換過的微指令送至R-階段316，或稱緩存器階段316。R-階段316包括使用者可見(user-visible)的x86緩存器集合，以及非使用者可見的緩存器。微指令的指令操作數(operand)存於R-階段316緩存器，供流水線300的後續階段執行微指令。A-階段318，或稱地址階段(addressstage)318，包括地址產生邏輯(addressgenerationlogic)，從R-階段316接收操作數與微指令，並產生微指令所需的地址，像是用以加載/儲存的內存地址。D-階段322，或稱資料階段(datastage)322，包括存取資料的邏輯，該資料由A-階段318產生的地址所指定。特別是，D-階段322包括一資料高速緩存，用來快取處理器300內從系統內存而來的數據。在一具體實施例中，數據高速緩存是雙周期高速緩存。G-階段324是資料高速緩存存取的第二階段，而在E-階段326，可取得資料高速緩存的資料。E-階段326，或稱執行階段(executionstage)326，包括執行邏輯(executionlogic)，像是算數邏輯單元(arithmeticlogicunit)，依據先前階段提供的資料及操作數執行微指令。特別是，E-階段326會產生BTAC402指出一返回指令可能存在於由提取地址495指定的指令高速緩存432快取線中所有分支指令的解析(resolved)目標地址356。即，E-階段326目標地址356被認為是所有分支指令的正確目標地址，所有預測的目標地址必須與其匹配。此外，E-階段326產生一所有分支指令的解析方向(DIR)481(見圖4)。S-階段328，或稱儲存階段(storestage)328，從E-階段326接收微指令的執行結果，將其儲存至內存。此外，還將E-階段326所計算的分支指令的目標地址356在I-階段302時從S-階段328送至指令高速緩存432。再者，I-階段302的BTAC402通過從S-階段328而來的分支指令的解析目標地址來予以更新。此外，在BTAC402的其它假想分支數據(speculativebranchinformation，簡稱SBI)454(見圖4)亦從S-階段328來更新。假想分支數據454包括分支指令長度，在一指令高速緩存432快取線內的位置，分支指令是否涵蓋多條指令高速緩存432快取線，分支是否為一調用或返回指令，以及用來預測分支指令的方向的數據，如關於圖7的部分所描述的。W-階段332，或稱回寫階段(write-backstage)，將S-階段328處理的結果回寫入R-階段316緩存器，用來更新處理器300的狀態。指令緩衝器342、F-階段指令序列344以及X-階段指令序列346除了別的功能外，還能將分支對於處理器300每個指令值的脈衝所造成的衝擊減至最小。現請參閱圖4，其繪示依本發明圖3處理器300的一假想分支預測裝置400。處理器300包括指令高速緩存432，以快取來自系統內存的指令字節496。指令高速緩存432由提取地址總線上的提取地址495來尋址，對指令高速緩存432內一快取線作檢索。最好(preferably)提取地址495包括一32位的虛擬地址。即，提取地址495並非指令的物理內存地址(physicalmemoryaddress)。在一具體實施例中，虛擬提取地址495是一x86線性(linear)指令指針。在一具體實施例中，指令高速緩存432具有32個字節的寬度；因此，只用到提取地址495之前27個位來檢索指令高速緩存432。一選定的指令字節快取線494則由指令高速緩存432輸出。指令高速緩存432在接下來圖5部分會更詳細地說明。現請參照圖5，其繪示圖4指令高速緩存432的一具體實施例的方塊圖。指令高速緩存432包括用來將圖4的虛擬提取地址495轉換成實際地址的邏輯(圖上未顯示)。指令高速緩存432包括一轉換參照緩衝器(translationlookasidebuffer，簡稱TLB)502，以快取先前轉換邏輯從虛擬提取地址495轉換的實際地址。在一具體實施例中，TLB502接收虛擬提取地址495的位[3112]，當虛擬提取地址495命中TLB502時，則輸出一對應的20位的實際分頁號碼(physicalpagenumber)512。指令高速緩存432包括一快取指令字節的數據數組506。資料數組506配置成數條快取線，以虛擬提取地址495的一部份來作索引。在一具體實施例中，數據數組506儲存了64KB的指令字節，其以32個字節的快取線來配置。在一具體實施例中，指令高速緩存432是一四路集合關聯高速緩存(4-waysetassociativecache)。因此，資料數組506包括512條指令字節線，以提取地址495的位[135]來作索引。虛擬提取地址495所選取的指令字節線494，由指令高速緩存432輸出至指令緩衝器342，如圖4所示。在一具體實施例中，一次將選定的指令字節線的一半送至指令緩衝器342，即，分成兩周期，每周期送16個字節。在本說明書中，快取線或指令位線可用以指稱由提取地址495於指令高速緩存432內所選定的一快取線的部分，像是半快取線(half-cacheline)或其它再細分的部分。指令高速緩存432亦包括一快取標誌的標誌數組(tagarray)504。標誌數組504，如同數據數組506，皆由虛擬提取地址495的相同位來作索引。實際地址的位快取於標誌數組504，作為實際標誌。由提取地址495位選定的實際標誌514則送至標誌數組504的輸出端。指令高速緩存432亦包括一比較器508，將實際標誌514與TLB502所提供的實際分頁號碼512作比較，以產生一命中信號(hitsignal)518，指明虛擬提取地址495是否命中指令高速緩存432。命中信號518真正指出了是否有快取現行的工作指令(taskinstruction)，因為指令高速緩存432將虛擬提取地址495轉換為一實際地址，並用此實際地址來測定是否有命中。前述指令高速緩存432的運作與BTAC402的運作成對比，後者僅依虛擬地址，即提取地址495，來測定是否命中，而非依據實際地址。此種運作上不同所造成的結果是，虛擬別名化(virtualaliasing)可能會發生，以致於BTAC402產生錯誤的目標地址352，如下所述。請再參閱圖4，圖3的指令緩衝器342從指令高速緩存432接收快取線的指令字節494並予以緩衝，直至其被格式化與轉換為止。如前文關於圖3的V-階段308所述，指令緩衝器342也儲存了其它分支預測的相關數據，像是x86前置與modR/M數據，以及指令字節是否為分支運算碼值。此外，指令緩衝器342為其內所存的每個指令字節儲存了一假想分支(speculativelybranched，簡稱SB)位。如果處理器300假想地分支至BTAC402所提供的假想目標地址352或假想返回地址353，其由假想調用/返回堆棧406依據快取於BTAC402中的SBI454所提供，則設定SBI454所指出的指令字節的SB位438。也就是，如果處理器300進行假想分支是基於如下假設在指令高速緩存432提供的指令字節線494中有一分支指令存在，而其SBI454快取於BTAC402中，則設定存於指令緩衝器342的指令字節494其中之一的SB位438。在一具體實施例中，則是針對SBI454所指出假定的分支指令的運算碼字節，設定其SB位438。指令解碼邏輯436從指令緩衝器342接收指令字節493(包括分支指令字節)以將其解碼，產生指令解碼數據492。指令解碼數據492用來進行分支指令預測，以及偵測與更正錯誤的假想分支。指令解碼邏輯436提供指令解碼數據492至流水線300的後段。此外，指令解碼邏輯436在解碼現行指令時，會產生下個循序指令指針(NSIP)466以及現行指令指針(currentinstructionpointer，CIP)468。此外，指令解碼邏輯436提供指令解碼數據492至非假想目標地址計算器(non-speculativetargetaddresscalculator)416、非假想調用/返回堆棧414以及非假想分支方向預測裝置(non-speculativebranchdirectionpredictor)412。最好(preferably)非假想調用/返回堆棧414、非假想分支方向預測裝置412以及非假想目標地址計算器416屬於流水線300的F-階段312。非假想分支方向預測裝置412產生一分支指令方向的非假想預測444，即是否要進行分支，以響應從指令解碼邏輯436接收的指令解碼數據492。最好(preferably)非假想分支方向預測裝置412包括一個或更多分支歷史表，以儲存已執行的分支指令的解析方向的歷程。最好(preferably)分支歷史表連同由指令解碼邏輯436提供的分支指令本身的解碼數據，用於預測條件分支指令的方向。非假想分支方向預測裝置412的一個示範實施例詳述於美國專利申請序號09/434,984HYBRIDBRANCHPREDICTORWITHIMPROVEDSELECTORTABLEUPDATEMECHANISM，具有一共同申請人，通過參考此案可併入本發明。最好(preferably)最後解析出分支指令方向的邏輯屬於流水線300的E-階段326。非假想調用/返回堆棧414產生圖3的非假想返回地址355，以響應從指令解碼邏輯436接收的指令解碼數據492。除了別的以外，指令解碼數據492還指明現行解碼的指令是否為調用指令、返回指令或兩者皆否。此外，如果正由指令解碼邏輯436解碼的指令為一調用指令，指令解碼數據492還會包括一返回地址488。最好(preferably)返回地址488包括現行解碼的調用指令的指令指針加上調用指令的長度所得的值。當指令解碼數據492顯示現行解碼的指令為一調用指令時，返回地址488會被推入非假想調用/返回堆棧414，如此在指令解碼邏輯436進行後續返回指令的解碼時，返回地址488就能做為非假想返回地址355。非假想調用/返回堆棧414的一個示範實施例詳述於美國專利申請序號09/271,591METHODANDAPPARATUSFORCORRECTINGANINTERNALCALL/RETURNSTACKINAMICROPROCESSORTHATSPECULATIVELYEXECUTESCALLANDRETURNINSTRUCTIONS，具有一共同申請人，通過參考此案可併入本發明。非假想目標地址計算器416產生圖3的非假想目標地址354，以響應從指令解碼邏輯436接收的指令解碼數據492。最好(preferably)非假想目標地址計算器416包括一算數邏輯單元，以計算程序計數器相關(PC-relative，下文稱PC相關)類型或直接類型(directtype)分支指令的分支目標地址。最好(preferably)算數邏輯單元將分支指令的長度與一指令指針加到內含於分支指令的一帶正負號的位移量(signedoffset)，來計算PC相關類型分支指令的目標地址。最好(preferably)非假想目標地址計算器416包括一相當小的分支目標緩衝器(BTB)，以快取間接類型(indirecttype)分支指令的分支目標地址。非假想目標地址計算器416的一個示範實施例詳述於美國專利申請序號09/438,907APPARATUSFORPERFORMINGBRANCHTARGETADDRESSCALCULATIONBASEDONBRANCHTYPE，具有一共同申請人，通過參考此案可併入本發明。分支預測裝置400包括假想分支目標地址高速緩存(BTAC)402。BTAC402通過提取地址總線上的提取地址495進行尋址，檢索BTAC402內一快取線。BTAC402並未整合在指令高速緩存432，而是分離且不同於指令高速緩存432，如圖所示。也就是，BTAC402與指令高速緩存432在實際上與概念上皆有所區別。BTAC402與指令高速緩存432實際上的區別，在於兩者在處理器300內處於不同的空間位置。BTAC402與指令高速緩存432概念上的區別，在於兩者具有不同的大小，即在一具體實施例中，它們包括不同數量的快取線。BTAC402與指令高速緩存432概念上的區別，也在於指令高速緩存432將提取地址495轉換成實際地址，以決定指令字節線的命中與否；BTAC402卻以虛擬提取地址495作為一虛擬地址來作索引，而沒有將其轉換為實際地址。最好(preferably)BTAC402屬於流水線300的I-階段302。BTAC402快取了先前執行分支指令的目標地址。當處理器300執行一分支指令時，該分支指令的解析目標地址通過更新信號442快取於BTAC402。該分支指令的指令指針1512(見圖15)用來更新BTAC402，如下文關於圖15部分所描述的。為了產生圖3的快取分支目標地址352，BTAC402連同指令高速緩存432皆由指令高速緩存432的提取地址495平行地(inparallel)檢索。BTAC402響應提取地址495而提供假想分支目標地址352。最好(preferably)提取地址495的32個位全都用來從BTAC402選取假想目標地址352，如下文將更詳細敘述的，主要是關於圖6到圖9的部分。假想分支目標地址352被送至包括一多工器422的地址選擇邏輯422。多工器422從數個地址(包括BTAC402目標地址352)中選取提取地址495，下文將會予以討論。多工器422輸出提取地址495至指令高速緩存432與BTAC402。若多工器422選取了BTAC402目標地址352，接著處理器300便會分支到BTAC402目標地址352。也就是，處理器300將開始從指令高速緩存432提取位於BTAC402目標地址352的指令。在一具體實施例中，BTAC402比指令高速緩存432還小。特別是，BTAC402快取目標地址所用的快取線數量比指令高速緩存432所含的還少。BTAC402未整合在指令高速緩存432的結果是(雖然使用指令高速緩存432的提取地址495作為索引)，若處理器300分支至BTAC402所產生的目標地址352，它是以假想方式進行的。此分支是假想的，乃因根本無法確定在所選定的指令高速緩存432快取線中，是否有一分支指令存在，更別說是目標地址352因的而被快取的分支指令了。命中BTAC402僅表示一分支指令先前存在於提取地址495所選取的指令高速緩存432快取線中。之所以無法確定一分支指令是否存在於所選取的快取線中，至少有兩個理由。無法確定一分支指令是否在提取地址495所檢索的指令高速緩存432快取線中，其第一個理由是提取地址495是一虛擬地址；因此，虛擬別名化可能會發生。也就是，兩個不同的實際地址可能對應到相同的虛擬提取地址495。一給定的提取地址495，其為虛擬的，可能轉換成兩個不同的實際地址，這兩個地址關聯於一多工(multitasking)處理器(像是處理器300)的兩個不同行程或工作。指令高速緩存432利用圖5的轉換參照緩衝器502執行虛擬到實際的轉換工作，以提供準確的指令資料。然而，BTAC402依據虛擬提取地址495執行其查詢工作，而沒有執行虛擬到實際地址的轉換工作。通過BTAC402避免虛擬到實際地址的轉換工作是有利的，因為比起有執行虛擬到實際地址轉換工作的情形，它使假想分支能更快速地執行。執行工作轉換的作業系統，提供了虛擬別名化情形可能會發生的一個例子。在工作轉換之後，處理器300會從指令高速緩存432提取位於關聯新行程的虛擬提取地址495的指令，該關聯新行程的虛擬提取地址495等同於關聯舊行程的虛擬提取地址495，而舊行程則包括一分支指令，其目標地址快取於BTAC402。指令高速緩存432會依據從虛擬提取地址495轉換的實際地址來產生新行程的指令，如上文關於圖5部分所描述的；然而，BTAC402會只用虛擬提取地址495以產生舊行程的目標地址352，因而造成一錯誤的分支。有利的是，錯誤的假想分支只會在新行程的指令第一次執行時發生，此因在發現錯誤後，BTAC402目標地址352將變為無效，如下文關於圖10部分說明的。因此，分支到BTAC402目標地址352是假想的，乃因在有些情況下，由於分支指令並不存在於指令高速緩存432的提取地址495(例如，因為虛擬別名化的關係)，處理器300將分支至BTAC402所產生的不正確的目標地址352。相反地，從這方面來看前述圖2的Athlon整合式BTAC/指令高速緩存202以及圖1的PentiumII/III分支目標緩衝器134，就是非假想性的。尤其，Athlon的方法因為在分支指令字節108旁並列儲存了圖2的目標地址206而假設虛擬別名化並未發生，所以是非假想性的。也就是，AthlonBTAC202的查詢工作是基於實際地址來執行的。PentiumII/III的方法，則因分支目標緩衝器134隻在從指令高速緩存102提取分支指令以及指令解碼邏輯132確定有一分支指令存在後，才產生一分支目標地址136。此外，非假想目標地址計算器416、非假想調用/返回堆棧414以及非假想分支方向預測裝置412也是非假想性的，此因它們只在從指令高速緩存432提取分支指令以及由指令解碼邏輯436解碼後，才產生分支預測，如下文將要說明的。應該了解到，雖然非假想分支方向預測裝置412所產生的方向預測444是「非假想性的」，即是在一分支指令已由指令解碼邏輯436解碼並確定該分支指令存在於現行指令流的情況下產生，非假想方向預測444仍是一「預測」。也就是，如果分支指令是條件分支指令，像是x86JCC指令，則在分支指令的任何既定的執行中，分支可能會進行，也可能不會。相類似地，非假想目標地址計算器416所產生的目標地址354以及非假想調用/返回堆棧414所產生的返回地址355也是非假想性的，因為這些地址是在確定有一分支指令存在於現行指令流的情況下而產生；儘管如此，它們仍然是預測。例如，以通過內存進行的x86間接跳轉而言，自前次執行間接跳轉以來，內存內容可能已有改變。如此，目標地址可能隨的改變。因此，在本說明書中，就分支方向而言，「非假想的」不能與「無條件的」相混淆；就目標地址而言，「非假想的」則不能與「確定的」(certain)相混淆。無法確定一分支指令是否在提取地址495所檢索的指令高速緩存432快取線中，其第二個理由是自我修改碼(self-modifyingcode)的存在。自我修改碼可能會改變指令高速緩存432的內容，但這改變並不會反映在BTAC402中。因此，一先前包括分支指令的指令高速緩存432快取線可能命中了BTAC402，但此分支指令已被修改或置換為不同的指令。分支預測裝置400亦包括假想調用/返回堆棧406。假想調用/返回堆棧406儲存返回指令的假想目標地址。假想調用/返回堆棧406因應控制邏輯404產生的控制信號483，產生圖3的假想返回地址353。假想返回地址353被送至多工器422的一輸入。當多工器422選取了假想調用/返回堆棧406所產生的假想返回地址353，處理器300便分支至假想返回地址353。當BTAC402指出一返回指令可能存在於由提取地址495指定的指令高速緩存432快取線中時，控制邏輯404會產生控制信號483，以控制假想調用/返回堆棧406來提供假想返回地址353。最好(preferably)當所選取的BTAC402項目602的VALID702與RET706位(見圖7)被設定，且BTAC402命中信號452顯示已命中BTAC402標誌數組614時，則BTAC402指出一返回指令可能存在於由提取地址495指定的指令高速緩存432快取線中。BTAC402響應提取地址495而產生命中信號452以及假想分支數據(SBI)454。命中信號452顯示提取地址495命中了BTAC402的一快取標誌，此於下文關於圖6的部分說明。SBI454也會在下文關於圖6部分作更詳盡的說明。SBI454包括一BEG446信號(指令高速緩存432一快取線內的分支指令起始字節位移量(beginningbyteoffset))與一LEN448信號(分支指令長度)。BEG446的值、LEN448的值與提取地址495由加法器434予以加總，而產生返回地址491。返回地址491由加法器434輸出至假想調用/返回堆棧406，如此返回地址491就能被推入假想調用/返回堆棧406。控制邏輯404通過信號483與BTAC402協同運作，將返回地址491推入假想調用/返回堆棧406。只有在所選定的BTAC402項目602的VALID702與CALL704位(見圖7)被設定且命中信號452顯示已命中BTAC402的標誌數組614(見圖6)時，返回地址491才會被推入堆棧。假想調用/返回堆棧406的運作方式在後文關於圖8與圖13部分會更詳細地說明。分支預測裝置400也包括控制邏輯404。控制邏輯404通過控制信號478控制多工器422，以選取數個地址輸入之一，作為提取地址495。控制邏輯404也通過信號482設定指令緩衝器342中的SB位438。控制邏輯404接收命中信號452、SBI454、來自非假想分支方向預測裝置412的非假想分支方向預測444以及來自指令緩衝器342的FULL信號486。分支預測裝置400亦包括預測檢查邏輯408。預測檢查邏輯408產生一ERR信號456，其被送至控制邏輯404，以指出已依據一BTAC402的命中而執行一錯誤的假想分支，如後文關於圖10部分所描述的。預測檢查邏輯408通過信號484從指令緩衝器342接收SB位438，信號484亦被送至控制邏輯404。預測檢查邏輯408也從BTAC402接收SBI454。預測檢查邏輯408也從指令解碼邏輯436接收指令解碼數據492。預測檢查邏輯408也接收圖3E-階段326所產生的解析分支方向DIR481。預測檢查邏輯408也接收比較器489的輸出485。比較器489將BTAC402產生的假想目標地址352與圖3E-階段產生的解析目標地址356作比較。BTAC402產生的假想目標地址352被存於緩存器，並順著指令流水線300而下至比較器489。預測檢查邏輯408也接收比較器497的輸出487。比較器497將假想調用/返回堆棧406產生的假想返回地址353與解析目標地址356作比較。假想返回地址353被存於緩存器，並順著指令流水線300而下至比較器497。BTAC402的假想目標地址352被存於緩存器，並順著指令流水線300而下，由比較器428將其與非假想目標地址計算器416的目標地址354作比較。比較器428的輸出476被送至控制邏輯404。相類似地，假想調用/返回堆棧406產生的假想返回地址353也被存於緩存器，並順著指令流水線300而下，由比較器418將其與非假想返回地址355作比較。比較器418的輸出474亦被送至控制邏輯404。分支預測裝置400亦包括一儲存多工化/緩存器(savemultiplexed/register，以下簡稱savemux/reg)424。savemux/reg424由控制邏輯404所產生的控制信號472來控制。savemux/reg424的輸出498作為多工器422的一個輸入。savemux/reg424接收自己的輸出498以及BTAC402的假想目標地址352作為輸入。多工器422亦接收S-階段328的分支地址356作為其輸入。多工器422也接收提取地址495本身作為輸入。多工器422亦接收由遞增裝置426產生的下個循序提取地址499，遞增裝置426接收提取地址495，並遞增其值至指令高速緩存432的下條循序快取線。現請參照圖6，其為依本發明繪示的圖4BTAC402的方塊圖。在圖6所示的具體實施例中，BTAC402包括一四路集合關聯高速緩存。BTAC402包括一數據數組612與一標誌數組614。資料數組612包括儲存組件的數組，以儲存快取分支目標地址與假想分支數據的項目。標誌數組614包括一儲存組件的數組，以儲存地址標誌。數據數組612與標誌數組614各自皆配置成四路，圖標為路0、路1、路2以及路3。最好(preferably)數據數組612的每一路儲存兩個快取分支目標地址與假想分支數據的項目，稱為A與B。由此，每次讀取資料數組612時，就會產生八個項目602。此八個項目602被送至一八對二路選擇多工器(wayselectmux)606。數據數組612與標誌數組614皆由圖4指令高速緩存432的提取地址495來作索引。提取地址495的較低有效位(significantbit)選定了數組612與614內各一條快取線。在一具體實施例中，每個數組包括了128條快取線。因此，BTAC402能夠快取多達1024個目標地址(128條快取線的每條具四個路，每路可儲存兩個目標地址)。最好(preferably)數組612與614是通過提取地址495的位[115]來作索引。標誌數組614為每路產生一標誌616。最好(preferably)每個標誌616包括虛擬地址的20個位，且四個標誌616的每一個皆由比較器604將其與提取地址495的位[3112]作比較。比較器604產生圖4的命中信號452，其依據是否有一標誌616與提取地址495的最高有效位相匹配，以指出是否有命中BTAC。命中信號452被送至圖4的控制邏輯404。此外，比較器604產生控制信號618，以控制路選擇多工器606。路選擇多工器606因而在BTAC402產生的快取線中，選取四個路之一的A項目624與B項目626。將A項目624與B項目626送至A/B選擇多工器608以及控制邏輯404。控制邏輯404因應命中信號452、A項目624與B項目626、提取地址495及其它控制信號而產生一控制信號622，來控制A/B選擇多工器608。A/B選擇多工器608便選取A項目624或B項目626兩者之一作為圖3BTAC402的目標地址352及圖4的SBI454。BTAC402最好(preferably)是一單埠(single-ported)高速緩存。單埠高速緩存的優點是尺寸上比較小，因而比起雙埠(dual-ported)高速緩存，在同樣大小的空間中能夠快取更多的目標地址。然而，雙埠高速緩存的考慮是使同時地讀寫BTAC402變得容易。雙埠BTAC402所具備的可同時讀寫的特徵，由於更新寫入的動作不需等待讀取動作，使得BTAC402的更新能更快速地進行。一般而言更快速的更新可得到更正確的預測，此因BTAC402內的數據是更為現時的(current)。在一具體實施例中，指令高速緩存432內每條快取線包括32個字節。然而，指令高速緩存432有時會提供指令字節的半快取線494。在一具體實施例中，BTAC402的每條快取線儲存了兩個項目602，因而包括了兩個目標地址714，用於指令高速緩存432的每條半快取線。現請參閱圖7，其為依本發明繪示圖4BTAC402的圖6項目602的格式方塊圖。項目602包括了圖4的SBI(假想分支數據)454與一分支目標地址(TA)714。SBI454包括一VALID位702、圖4的BEG446與LEN448、一CALL位704、一RET位706、一WRAP位708以及分支方向預測數據(BDPI)712。在圖3的流水線300執行一分支後，該分支的解析目標地址即被快取於TA欄位(field)714，而解碼與執行分支指令所得的SBI454則被快取於BTAC402的項目602的SBI454欄位中。VALID位702指出了項目602是否可用於將處理器300假想分支至關聯的目標地址714。特別是，VALID位702最初是處於清除狀態，此因BTAC402由於未快取任何有效的目標地址而是空的。當處理器300執行一分支指令，且與該分支指令關聯的解析目標地址與假想分支數據被快取於項目602時，VALID位702就被設定。之後，如果BTAC402依據項目602作了錯誤的預測，VALID位702就被清除，如下文關於圖10部分所述。BEG欄位446指定了指令高速緩存432的一快取線內分支指令的起始字節位移量。在偵測到有一調用指令命中BTAC402時，BEG欄位446被用來計算一返回地址，以儲存於圖4的假想調用/返回堆棧406。此外，BEG欄位446被用來確定所選取BTAC402路的圖6項目A624或項目B626兩者中哪一個導致了BTAC402的命中，如下文關於圖8部分所述。最好(preferably)由項目A624與項目B626所指定的分支指令位置，在指令高速緩存432的快取線內不需有任何特定的順序。也就是，在指令高速緩存432的快取線中，項目B626的分支指令可能還早於項目A624的分支指令。LEN448欄位指出分支指令字節的長度。在偵測到一調用指令命中BTAC402時，LEN448欄位被用來計算一返回地址，以儲存於圖4的假想調用/返回堆棧406。CALL位704指出所快取的目標地址714是否關聯到一調用指令。也就是，如果一調用指令由處理器300執行，且該調用指令的目標地址快取於項目602，則CALL位704將被設定。RET位706指出所快取的目標地址714是否關聯到一返回指令。也就是，如果一返回指令由處理器300執行，且該返回指令的目標地址快取於項目602，則RET位706將被設定。WRAP位708在分支指令字節橫跨兩條指令高速緩存432的快取線時，會被設定。在一具體實施例中，WRAP位708在分支指令字節橫跨兩條指令高速緩存432的半快取線時，會被設定。BDPI(分支方向預測數據)欄位712包括一T/NT(taken/nottaken，即採用/不採用)欄位722與一SELECT位724。T/NT欄位722包括分支的方向預測，即，它指明了分支是預測會採用或不會採用。最好(preferably)T/NT欄位722包括一兩位的上/下數飽和計數器(up/downsaturatingcounter)，用以指定四種狀態極可能採用(stronglytaken)、有可能採用(weaklytaken)、有可能不採用(weaklynottaken)與極可能不採用(strongnottaken)。在另一實施例中，T/NT欄位722包括單一T/NT位。SELECT位724用來在下列兩者中作一選擇BTAC402T/NT方向預測722與由BTAC402的外的分支歷史表(BHT)(見圖12)所做的方向預測，如關於圖12部分所述。在一具體實施例中，如果在分支執行後，所選定的預測裝置(即，BTAC402或BHT1202)準確地預測了方向，SELECT位724就不會更新。然而，如果所選定的預測裝置沒有準確地預測方向而另一個預測裝置正確地預測方向，SELECT位724就會更新，以指明是非選定的預測裝置，而不是所選定的預測裝置。在一具體實施例中，SELECT位724包括一兩位的上/下數飽和計數器，用以指定四種狀態極可能是BTAC(stronglyBTAC)、有可能是BTAC(weaklyBTAC)、有可能是BHT(weaklyBHT)與極可能是BHT(strongBHT)。在此實施例中，如果在分支執行後，所選定的預測裝置(即，BTAC402或BHT1202)準確地預測了方向，飽和計數器即朝所選定的預測裝置來計數。如果所選定的預測裝置沒有準確地預測方向而另一個預測裝置正確地預測方向，飽和計數器即朝非選定的預測裝置來計數。現請參照圖8，其為依本發明繪示的圖4假想分支預測裝置400的運作流程圖。圖4的BTAC402由圖4的提取地址495作索引。因此，圖6的BTAC402比較器604響應圖6的BTAC402標誌數組614的虛擬標誌616，以產生圖4的命中信號452。在步驟802中，圖4的控制邏輯404檢查命中信號452，以確定提取地址495是否命中BTAC402。如果BTAC402的命中並未發生，則在步驟822中控制邏輯404便不進行假想分支。也就是，控制邏輯404通過圖4的控制信號478控制多工器422，以選取除了BTAC402的目標地址352與假想調用/返回堆棧406的返回地址353外的一個輸入。然而，如果BTAC402的命中確實發生，在步驟804中，控制邏輯404便會確定圖6的A項目624是否有效，被看見(seen)與被採用(taken)。若圖7VALID位702被設定，控制邏輯404便確定項目624為「有效的」。如果VALID位702被設定，由提取地址495所選取的指令高速緩存432快取線就被假定為包括一分支指令，而該分支指令的分支預測數據則已先快取於A項目624；然而，如上文所討論的，並不確定所選取的指令高速緩存432快取線包括有分支指令。若項目A624的T/NT欄位722指出，所假定的分支指令方向預期會被採用，則控制邏輯404便確定項目624「被採用」(taken)。在下述圖12的具體實施例中，若所選取的方向指示裝置(directionindicator)指出，所假定的分支指令方向預期會被採用，則控制邏輯404便確定項目624「被採用」。若圖7的BEG欄位446大於或等於提取地址495相對應的最低有效位(leastsignificantbits)，則控制邏輯404便確定項目624「被看見」(seen)。也就是，BEG欄位446與提取地址495相對應的最低有效位作比較，以決定下個指令提取的位置是否位在指令高速緩存432中對應於A項目624的分支指令位置之前。例如，假設A項目624的BEG欄位446包括一數值3，而提取地址495的較低位值為8。在這種情況下，可能就不會因此提取地址495分支至A項目624的分支指令。因此，控制邏輯404將不會假想分支至A項目624的目標地址714。這在提取地址495是分支指令的目標地址時特別有關係。若A項目624是有效的、預期會被採用且被看見，在步驟806中，控制邏輯404會檢查圖6的B項目626是否為有效、被看見與採用。控制邏輯404是以類似於步驟804對A項目624所用的方式，來決定B項目626是否為有效、被看見與採用。若A項目624是有效的、預期會被採用且被看見，但B項目626不是有效的、預期不被採用或者不被看見，則在步驟812中，控制邏輯404檢查圖7的RET欄位706，以決定A項目624是否已快取返回指令的數據。若RET位706未被設定，則在步驟814中，控制邏輯404控制圖6的A/B多工器608以選取項目A624，並通過控制信號48控制多工器422，以假想分支至目標地址信號352所提供的BTAC402項目A624的目標地址714。相反地，若RET位706指出，在提取地址495所選取的指令高速緩存432快取線中，可能存在一返回指令，則在步驟818中，控制邏輯404通過控制信號478控制多工器422，以假想分支至圖4假想調用/返回堆棧406的返回地址353。在步驟814或步驟818進行假想分支後，於步驟816中，控制邏輯404產生一指示於控制信號482中，表示已響應BTAC402而執行一假想分支。也就是，不論處理器300假想分支至假想調用/返回堆棧406的返回地址353，或是BTAC402項目A624的目標地址352，控制邏輯404皆會於控制信號482中，顯示已執行一假想分支。當一指令字節從指令高速緩存432進行至圖3的指令緩衝器342時，控制信號482會用來設定SB位438。在一具體實施例中，控制邏輯404利用項目602的BEG446欄位，來設定指令緩衝器342內關聯於分支指令的運算碼字節的SB位438。此分支指令的SBI454在提取地址495命中BTAC402時，是假定已快取於BTAC402中。若A項目624是無效的，或預期不被採用，或不被看見，如步驟804中所確定的，則控制邏輯404在步驟824中便會確定B項目626是否為有效、被看見與被採用。控制邏輯404是以類似於步驟804對A項目624所用的方式，來決定B項目626是否為有效、被看見與採用。若B項目626是有效的、預期會被採用且被看見，則在步驟832中，控制邏輯404檢查RET欄位706，以決定B項目626是否已快取返回指令的數據。若RET位706未被設定，則在步驟834中，控制邏輯404控制圖6的A/B多工器608以選取項目B626，並通過控制信號478控制多工器422，以假想分支至目標地址信號352所提供的BTAC402項目B626的目標地址714。相反地，若RET位706指出，在提取地址495所選取的指令高速緩存432快取線中，可能存在一返回指令，則在步驟818中，控制邏輯404通過控制信號478控制多工器422，以假想分支至假想調用/返回堆棧406的返回地址353。在步驟834或步驟818進行假想分支後，於步驟816中，控制邏輯404產生一指示於控制信號482中，表示已響應BTAC402而執行一假想分支。若A項目624與B項目626皆是無效的，預期不被採用，或不被看見，則在步驟822中，控制邏輯404便不會進行假想分支。若A項目624與B項目626兩者皆為有效的，預期被採用，且被看見，則在步驟808中，控制邏輯404便會去確定，在假定的分支指令(其數據快取於A項目624與B項目626)中，哪一個是指令高速緩存432的快取線指令字節494內，最先被看見的有效且被採用的分支指令。也就是，如果兩個假定的分支指令都被看見、有效且被採用，控制邏輯404便通過比較A項目624與B項目626的BEG446欄位，來決定哪一個假定的分支指令具有較小的內存地址。若B項目626的BEG446的值比A項目624的BEG446的值還小，則控制邏輯404便進行至步驟832，依據B項目626進行假想分支。否則，控制邏輯404便進行至步驟812，依據A項目624進行假想分支。在一具體實施例中，假想調用/返回堆棧406並不存在。所以，步驟812、818與832皆未執行。從圖8可以看出，本發明有利地提供一裝置，用以將多個分支指令的目標地址與假想分支數據快取於一分支目標地址高速緩存中一特定的指令快取線，而該分支目標地址高速緩存並未整合在指令高速緩存內。特別是，分支指令的位置數據快取於快取線內的BEG欄位446，有利地使控制邏輯404無需前解碼快取線，就能夠從快取線內可能的多個分支指令中，決定要假想分支至哪一個。也就是，BTAC402在慮及可能有兩個或更多分支指令存在於所選取快取線的情況下，決定目標地址，而不用知道有多少分支指令(假若有的話)存在於快取線中。現請參閱圖9，其為依本發明繪示的圖4假想分支預測裝置400使用圖8步驟選取圖4目標地址352的一運作範例的方塊圖。此範例顯示一值為0x10000009的提取地址495進行指令高速緩存432與BTAC402的檢索，且該提取地址495也被送至圖4的控制邏輯404。為了簡明起見，關於指令高速緩存432與BTAC402的多路關聯性(multi-wayassociativity)的數據，像是圖6的多個路與路多工器606，並未顯示出來。指令高速緩存432的一快取線494由提取地址495選取。快取線494包括快取於地址0x10000002的一x86條件跳轉指令(JCC)與快取於地址0x1000000C的一x86CALL指令。此範例也顯示了提取地址495所選取的BTAC402快取線內A項目602A與B項目602B的一些組成部份。項目A602A包括CALL指令的快取數據，而項目B602B包括JCC指令的快取數據。項目A602A顯示其VALID位702A被設為1，表示其為一有效的項目A602A，即，圖7相關聯的目標地址714與SBI454是有效的。項目A602A也顯示出一值為0x0C的BEG欄位446A，對應於該CALL指令的指令指針地址的最低有效位。項目A602A也顯示了一值為「被採用」的T/NT欄位722A，表示該CALL指令預期會被採用。響應提取地址495，A項目602A通過圖6的信號624送至控制邏輯404。項目B602B顯示其VALID位702B被設為1，表示其為一有效的項目B602B。項目B602B也顯示出一值為0x02的BEG欄位446B，對應於該JCC指令的指令指針地址的最低有效位。項目B602B也顯示了一值為「被採用」的T/NT欄位722B，表示該JCC指令預期會被採用。響應提取地址495，B項目602B通過圖6的信號626送至控制邏輯404。此外，BTAC402將命中信號452設定為真，以顯示提取地址495命中了BTAC402。控制邏輯404接收項目A602A與項目B602B，並依照圖8所述的方法，根據命中信號452、提取地址495的值以及602A與602B兩個項目，產生圖6的A/B選擇信號622。在步驟802中，控制邏輯404依據命中信號452被設定為真，而確定BTAC402有一命中發生。接著於步驟804中，控制邏輯404依據VALID位702A被設定，而確定項目A602A是有效的。而因T/NT欄位722A顯示為被採用，控制邏輯404也於步驟804確定項目A602A是被採用的。由於BEG欄位446A的值0x0C大於或等於提取地址195的值0x09對應的較低位，控制邏輯404亦於步驟804確定項目A602A被看見。既然項目A602A是有效的、被採用與被看見，控制邏輯404便進行至步驟806。於步驟806中，控制邏輯404依據VALID位702B被設定，而確定項目B602B是有效的。而因T/NT欄位722B顯示為被採用，控制邏輯404也於步驟806確定項目B602B是被採用的。由於BEG欄位446B的值0x02小於提取地址495的值0x09對應的較低位，控制邏輯404亦於步驟806確定項目B602B未被看見。既然項目B602B未被看見，控制邏輯404便進行至步驟812。在步驟812中，控制邏輯404通過圖7被清除的RET位706而確定關聯於項目A602A所快取的指令不是返回指令，並進行至步驟814。在步驟814中，控制邏輯404產生一A/B選擇信號622的值，以驅使圖6的A/B多工器608選取信號624上的項目A602A。這個選擇的動作導致項目A602A的圖7目標地址714被選為圖3的目標地址352，送至圖4的提取地址495選擇多工器422。因此，從圖9的範例可以看出，圖4的分支預測裝置400有利地運作，以選取最先、有效、被看見、被採用的所選定BTAC402快取線的項目602，將處理器300假想分支至其中關聯的目標地址714。有利的是，即使有多個分支指令存在於對應的選定的指令高速緩存432快取線494，裝置400仍能在不知快取線494內容的情況下，完成假想分支的動作。現請參閱圖10，其為依本發明繪示的圖4假想分支預測裝置400偵測與更正錯誤的假想分支預測的運作流程圖。從指令緩衝器342接收一指令後，在步驟1002中，圖4的指令解碼邏輯436便解碼該指令。尤其，指令解碼邏輯436將指令字節流(streamofinstructionbytes)格式化成一不同的x86巨指令，並確定該指令的長度以及是否為分支指令。接著，在步驟1004中，圖4的預測檢查邏輯408測定所解碼指令中，是否有任何指令字節的SB位438被設定。也就是，預測檢查邏輯408測定是否先前已基於現行解碼的指令命中BTAC402，而執行一假想分支。若沒有執行任何假想分支，則不會採取行動去更正。若有執行一假想分支，則在步驟1012中，預測檢查邏輯408會檢查現行解碼的指令，以確定該指令是否為非分支指令。最好(preferably)預測檢查邏輯408會測定該指令是否為x86指令集的非分支指令。如果該指令不是分支指令，則在步驟1022中，預測檢查邏輯408將圖4的ERR信號456設定為真，以表示偵測到一錯誤的假想分支。此外，通過圖4的更新信號442，BTAC402得以更新，而清除圖6對應的BTAC402項目602的圖7VALID位702。再者，圖3的指令緩衝器342會清除掉因此一錯誤的假想分支而從指令高速緩存432誤取的指令。如果該指令不是分支指令，則在步驟1024中，控制邏輯404接著控制圖4的多工器422，以分支至指令解碼邏輯436所產生的CIP468，更正該錯誤的假想分支。步驟1024中所進行的分支，將使得包括該指令的指令高速緩存432快取線重新被提取與作假想預測。然而，這次該指令的VALID位702將被清除；因此，該指令將不執行任何假想分支，用來更正先前錯誤的假想分支。若在步驟1012中已確定該指令為一有效的分支指令，則在步驟1014中，預測檢查邏輯408會確定在所解碼指令的指令字節內，位於非運算碼(non-opcode)字節位置的指令，有否任何字節的SB位438被設定。也就是，雖然一字節可能包括一處理器300指令集的有效運算碼值，該有效運算碼值卻可能位於一個就指令格式而言是無效的字節位置。對一x86指令而言，除了前置字節外，運算碼字節應該是指令的第一個字節。例如，對於在指令的立即資料(immediatedata)或位移欄位(displacementfield)中，或者因虛擬別名化而在一x86指令modR/M或SIB(ScaleIndexBase，比例-索引-基底)字節中所含的分支運算碼值，SB位438可能因的而錯誤地被設定。若分支運算碼字節位於非運算碼字節位置，則執行步驟1022與1024以更正錯誤的假想預測。若在步驟1012中，預測檢查邏輯408確定該指令為一有效的分支指令，且在步驟1014中，確定沒有非運算碼字節的SB位438被設定，則在步驟1016中，預測檢查邏輯408會確定是否有假想與非假想指令長度上的不匹配。也就是，預測檢查邏輯408將步驟1002中指令解碼邏輯436產生的非假想指令的長度與BTAC402產生的圖7假想LEN448欄位作一比較。若指令長度不匹配，則執行步驟1022與1024以更正錯誤的假想預測。若在步驟1012中，預測檢查邏輯408確定該指令為一有效的分支指令，且在步驟1014中，確定只有運算碼字節的SB位438被設定，以及在步驟1016確定指令長度匹配，則該指令便順著流水線300而下，直至抵達圖3的E-階段326。在步驟1032中，E-階段326解析出圖3的正確的分支指令目標地址356，並確定圖4的正確的分支方向DIR481。接著，在步驟1034中，預測檢查邏輯408確定BTAC402是否錯誤預測了分支指令的方向。也就是，預測檢查邏輯408將E-階段326所解析的正確方向DIR481與BTAC402產生的圖7預測722作比較，以確定是否已執行一錯誤的假想分支。若BTAC402預測了一錯誤的方向，則在步驟1042中，預測檢查邏輯408將ERR信號456設定為真，以告知控制邏輯404此錯誤。因此，控制邏輯404便通過圖4的更新信號442，來更新圖6對應的BTAC402項目602的BTAC402方向預測722。最後，在步驟1042中，控制邏輯404會清除掉流水線300中因該錯誤的假想分支而從指令高速緩存432誤取的指令。接著，在步驟1044中，控制邏輯404驅使多工器422選取圖4的NSIP466，使處理器300分支至分支指令的下個指令，以更正該錯誤的假想分支。若在步驟1034中無方向的錯誤，則在步驟1036中，預測檢查邏輯408會確定是否BTAC402或假想調用/返回堆棧406錯誤地預測了分支指令的目標地址。也就是，若處理器300假想分支至BTAC402目標地址352，則預測檢查邏輯408會檢查圖4比較器489的結果485，以確定是否假想目標地址352不匹配所解析的正確目標地址356。另一種情況是，若處理器300假想分支至假想調用/返回堆棧406返回地址353，則預測檢查邏輯408會檢查圖4比較器497的結果487，以確定是否假想返回地址353不匹配所解析的正確目標地址356。若在步驟1036偵測到一目標地址的錯誤，則在步驟1052中，預測檢查邏輯408將ERR信號456設定為真，以顯示偵測到一錯誤的假想分支。此外，控制邏輯404通過更新信號442，以步驟1032產生的解析目標地址356來更新圖6對應的BTAC402項目602。再者，會清除掉流水線300中因該錯誤的假想分支而從指令高速緩存432誤取的指令。接著，在步驟1054中，控制邏輯404控制圖4的多工器422，以分支至解析目標地址356，用來更正先前錯誤的假想分支。現請參照圖11，為依本發明列舉的程序代碼實例片段及一表格1100，為說明圖10假想分支預測錯誤的偵測與更正的一範例。程序代碼片段包括一先前程序代碼片段與一現行程序代碼片段。例如，該先前程序代碼片段圖標了在圖3處理器300進行工作交換(taskswitch)前，圖4指令高速緩存432中位於虛擬地址0x00000010的程序代碼。該現行程序代碼片段則圖標了在工作交換後，指令高速緩存432中位於虛擬地址0x00000010的程序代碼，就像在虛擬別名化情形所可能發生的。該先前程序代碼序列(codesequence)包括一在0x00000010地址位置的x86JMP(無條件跳轉)指令。該JMP指令的目標地址為0x00001234。該JMP指令已執行；所以，在現行程序代碼序列執行時，目標地址0x00001234已因應地址0x00000010而快取於圖4的BTAC402。也就是，目標地址714已被快取，VALID位702被設定，BEG446、LEN448與WRAP708欄位寫入適當的值，圖7的CALL704與RET706位則被清除。在此範例中，假定T/NT欄位722顯示出所快取的分支將被採用，且JMP快取於BTAC402快取線的A項目624中。現行程序代碼序列包括一位於0x00000010的ADD(算術加)指令，與先前程序代碼序列中的JMP指令的虛擬地址相同。現行程序代碼序列中位置0x00001234是SUB(算術減)指令，位置0x00001236則是INC(算術遞增)指令。表格1100包括八行(column)與六列(row)。第一列之後七行代表七個脈衝周期(clockcycle)，從1至7。第一行之後五列代表流水線300最先的五個階段，即I-階段302、B-階段304、U-階段306、V-階段308與F-階段312。表格1100的其它方格則顯示當執行現行程序代碼序列時，在不同脈衝周期中每個階段的內容。在脈衝周期1期間，BTAC402與指令高速緩存432被存取。ADD指令顯示於I-階段302。圖4值為0x00000010的提取地址495檢索BTAC402與指令高速緩存432，依據圖8的流程決定是否需要進行一假想分支。在圖11的範例中，一值為0x00000010的提取地址495會命中BTAC402，如下所述。在脈衝周期2期間，ADD指令顯示於B-階段304。這是指令高速緩存432提取周期(fetchcycle)的第二個脈衝。標誌數組614提供標誌616，而資料數組612提供圖6的項目602，每個項目602包括圖7的目標地址714與SBI454。因為先前程序代碼序列的JMP指令在執行後已被快取，圖6的比較器604便根據圖8的步驟802產生一標誌命中(taghit)於信號452上。比較器604也通過信號618控制路多工器606去選取適當的路。控制邏輯404檢查A項目624與B項目626的SBI454，在此例中並選擇A項目624以提供目標地址352與SBI454。在此例中，控制邏輯404也依據步驟804與812來決定項目是有效、被採用、被看見且不是返回指令。在脈衝周期3期間，ADD指令顯示於U-階段306。ADD指令由指令高速緩存432提供，並閂鎖於U-階段306。因為圖8的步驟802至814是在脈衝周期2中執行，控制邏輯404便通過控制信號478控制圖4的多工器422，以選取BTAC402所提供的目標地址352。在脈衝周期4期間，ADD指令進行至V-階段308，在此階段被寫入指令緩衝器342。脈衝周期4是假想分支周期。也就是，處理器300依據圖8的步驟814，開始提取位於值為0x00001234的快取目標地址352的指令。即，根據圖8，提取地址495被改為地址0x00001234，以完成假想分支至該地址的動作。因此，位於地址0x00001234的SUB指令，在脈衝周期4是顯示於I-階段302。此外，控制邏輯404通過圖4的信號482指出，已執行一假想分支。所以，根據圖8的步驟816，指令緩衝器342中一SB位438對應於ADD指令被設定。在脈衝周期5期間，偵測到假想分支中的錯誤。ADD指令進行到F-階段312。SUB指令進行至B-階段304。位於下個循序指令指針的INC指令，則顯示於I-階段302。圖4的F-階段312指令解碼邏輯436解碼ADD指令，並產生圖4的CIP468。預測檢查邏輯408依據步驟1004，通過信號484偵測到關聯於ADD指令的SB位438被設定。預測檢查邏輯408依據步驟1012，也偵測到ADD指令是一非分支指令，並接著依據步驟1022將圖4的ERR信號456設為真，以表示在周期4中已執行錯誤的假想分支。在脈衝周期6期間，使錯誤的假想分支無效。依據步驟1022，指令緩衝器342被清空。尤其，ADD指令從指令緩衝器342中清除。此外，依據步驟1022，導致錯誤假想分支的項目602所關聯的VALID位702則被清除，以更新BTAC402。再者，控制邏輯404控制多工器422，以選取CIP468作為下個周期的提取地址495。在脈衝周期7期間，更正錯誤的假想分支。處理器300開始從指令高速緩存432提取位於ADD指令的指令指針的指令，該ADD指令是在脈衝周期5偵測到錯誤時，由指令解碼邏輯436所解碼的。也就是，處理器300依據步驟1024分支至對應於ADD指令的CIP468，用來更正在脈衝周期5所執行的錯誤的假想分支。因此，ADD指令在脈衝周期7是顯示於I-階段302。這次，ADD指令將順著流水線300而下並執行。現請參閱圖12，其為依本發明繪示的圖4分支預測裝置400包括一混合假想分支方向預測裝置1200的另一具體實施例的方塊圖。簡單就可以看出，BTAC402的分支方向預測愈準確，假想分支至BTAC402產生的假想目標地址352就愈能有效地減少分支延遲懲罰。反過來說，錯誤的假想分支愈不常被更正，如關於圖10部分所述，假想分支至BTAC402產生的假想目標地址352就愈能有效地減少處理器300的平均分支延遲懲罰。方向預測裝置1200包括圖4的BTAC402、一分支歷史表(BHT)1202、異或邏輯(exclusive0Rlogic)1204、全域分支歷史緩存器(globalbranchhistoryregisters)1206與一多工器1208。全域分支歷史緩存器1206包括一移位緩存器(shiftregister)，對於處理器300所執行的所有分支指令，全域分支歷史緩存器1206接收其分支指令方向結果(branchinstructiondirectionoutcomes)1212，而該移位緩存器則儲存分支指令方向結果1212的全域歷史。每次處理器300執行一分支指令，圖4的DIR位481就被寫入移位緩存器1206，若分支方向被採用，該位值為「設定」；若分支方向不被採用，該位值為「清除」。由此，最早的(oldest)位就被移出移位緩存器1206。在一具體實施例中，移位緩存器1206儲存了全域歷史的13個位。全域分支歷史的儲存，在分支預測的
技術領域：
中是為人熟知的，對於程序中高度依存於其它分支指令的分支指令，可改良其結果的預測。全域分支歷史1206通過信號1214送至異或邏輯1204，以與圖4的提取地址495進行一邏輯的異或運算。異或邏輯1204的輸出1216作為分支歷史表1202的索引。在分支預測的
技術領域：
中，異或邏輯1204所執行的功能一般都稱為gshare運算。分支歷史表1202包括一儲存組件的數組，以儲存數個分支指令的分支方向結果的歷史。該數組由異或邏輯1204的輸出1216作為索引。當處理器300執行一分支指令，由異或邏輯1204的輸出1216所檢索的分支歷史表1202的數組組件便通過信號1218選擇性地加以更新，而信號1218的內容則視解析分支方向DIR481而定。在一具體實施例中，分支歷史表1202數組中的每個儲存組件包括兩個方向預測A與B方向預測。最好(preferably)，如圖所示，分支歷史表1202產生A與B方向預測於T/NT_A/B1222信號上，針對BTAC402產生的圖6A項目624與B項目626各指定一方向預測以供選取。在一具體實施例中，分支歷史表1202的儲存組件數組包括4096個項目，每個可儲存兩個方向預測。在一具體實施例中，A與B預測各包括單一T/NT(taken/nottaken，即採用/不採用)位。在此實施例中，該T/NT位更新為DIR位481的值。在另一具體實施例中，A與B預測各包括一兩位的上/下數飽和計數器，指定了四種狀態極可能採用(stronglytaken)、有可能採用(weaklytaken)、有可能不採用(weaklynottaken)與極可能不採用(strongnottaken)。在此實施例中，飽和計數器朝DIR位481指出的方向來計數。多工器1208從分支歷史表1202接收兩個方向預測位T/NT_A/B1222，並從BTAC402接收A項目624與B項目626各自的圖7T/NT方向預測722。多工器1208亦從BTAC402接收A項目624與B項目626各自的SELECT位724，作為選擇控制信號。A項目624的SELECT位724從兩個A輸入中選取一T/NT給A項目624。B項目626的SELECT位724從兩個B輸入中選取一T/NT給B項目626。所選取的兩個T/NT位1224被送至控制邏輯404，通過圖4的信號478，用於控制多工器422。在圖12的實施例中，所選取的兩個T/NT位1224分別包括於項目A624與項目B626，被送至控制邏輯404，如圖6所示。可以看出，若處理器300分支至目標地址352，且該地址352是BTAC402依據(至少部分是)分支歷史表1202所提供的方向預測1222而產生，則該分支是以假想的方式進行。該分支是假想的，此因雖然命中BTAC402已指出一分支指令先前存在於提取地址495所選取的指令高速緩存432快取線中，但仍無法確定一分支指令位於所選取的指令高速緩存432快取線中，如上所討論的。也可以看出，比起單單只有BTAC402方向預測722，圖12的混合分支方向預測裝置1200可能有利地提供一更準確的分支方向預測。尤其，一般而言，對於高度依存於其它分支歷史的分支而言，分支歷史表1202提供了較準確的預測；反的，對於並非高度依存於其它分支歷史的分支而言，則是BTAC402提供了較準確的預測。就一既定的分支而言，通過SELECT位724能選擇較準確的預測裝置。因此，可以看出，圖12的方向預測裝置1200能有利地與BTAC402協同運作，以使用BTAC402所提供的目標地址352進行更準確的假想分支。現請參閱圖13，其為圖4的雙調用/返回堆棧406與414的運作流程圖。電腦程式的一項特性是，可能從程序內多個位置來調用子程序(subroutine)。所以，子程序內—返回指令的返回地址可能變來變去。因此，可以看出，利用分支目標地址高速緩存去預測返回地址通常很不容易，從而調用/返回堆棧的出現，實有其必要。本發明的雙調用/返回地址堆棧的架構提供了本發明的假想BTAC的好處，像是在流水線300早期即預測分支目標地址，以減少分支懲罰。除此之外，還廣泛提供了調用/返回堆棧的優點，即，比一簡單的BTAC402更準確地預測返回地址。在步驟1302中，圖4的BTAC402由圖4的提取地址495作索引，而圖4的控制邏輯404檢查命中信號452，以確定提取地址495是否命中BTAC402，還檢查SBI454的VALID位702，以確定所選取的BTAC402項目602是否有效。若BTAC402的命中未發生或VALID位702未被設定，則控制邏輯404並不會使處理器300進行假想分支。若在步驟1302期間一有效的BTAC402命中發生，則在步驟1304中，控制邏輯404會檢查圖4SBI454的圖7CALL位704，以確定所快取的分支指令假想地或大概地是否為一調用指令。若CALL位704被設定，則在步驟1306中，控制邏輯404控制假想調用/返回堆棧406，以將假想返回地址491推入其中。也就是，該假定的調用指令的假想返回地址491，其為圖4的提取地址495、BEG446與LEN448的總和，儲存於假想調用/返回堆棧406。假想返回地址491之所以為假想的，乃因在命中BTAC402的提取地址495所關聯的指令高速緩存432快取線中，並不確定真有包括一調用指令，更別說是BEG446與LEN448因的而被快取於BTAC402的調用指令了。假想返回地址491，或目標地址，在下一次執行返回指令時，可由返回地址信號353提供，以便假想分支至此返回地址491，就如下文關於步驟1312至1318所述。若Call位704被設定，則在步驟1308中，控制邏輯404接著控制多工器422去選取圖3的BTAC402目標地址352，以假想分支至目標地址352。若控制邏輯404在步驟1304確定CALL位704未被設定，則在步驟1312中，控制邏輯404會檢查SBI454的圖7RET位706，以確定所快取的分支指令假想地或大概地是否為一返回指令。若RET位706被設定，則在步驟1314中，控制邏輯404控制假想調用/返回堆棧406，以將圖3的假想返回地址353從堆棧頂端取出。在取出假想返回地址353後，則在步驟1316中，控制邏輯接著控制多工器422去選取從假想調用/返回堆棧406取出的假想返回地址353，以假想分支至返回地址353。返回指令順著流水線300而下，直至抵達圖3的F-階段312，圖4的指令解碼邏輯436則解碼此假定的返回指令。若此假定的返回指令的確是一返回指令，則圖4的非假想調用/返回堆棧414產生此返回指令的圖3非假想返回地址355。在步驟1318中，圖4的比較器418將假想返回地址353與非假想返回地址355作比較，並將結果714送至控制邏輯404。在步驟1318中，控制邏輯404檢查比較器418的結果474，以確定是否有不匹配發生。若假想返回地址353與非假想返回地址355不相匹配，則在步驟1326中，控制邏輯404會控制多工器422選取非假想返回地址355，以使處理器300分支至非假想返回地址355。若控制邏輯404於步驟1304中確定CALL位704並未設定，且於步驟1312中確定RET位706也未設定，則在步驟1322中，控制邏輯404會控制多工器422假想分支至圖3的BTAC402目標地址352，如圖8步驟814或834所描述的。因此，從圖13可看出，圖4的雙重調用/返回堆棧的運作可減少調用與返回指令的分支懲罰。這種分支懲罰的減少，是通過將處理器300結合BTAC402，使調用與返回指令在流水線更早期就進行分支，同時也克服以下現象由於子程序一般都從一些不同的程序位置來調用，返回指令因而會返回至多個不同的返回地址。現請參照圖14，為說明圖4的分支預測裝置400以非假想分支預測來選擇性地覆蓋(override)假想分支預測，用來改進本發明的分支預測準確度的運作流程圖。在從指令緩衝器342接收一指令後，在步驟1402中，圖4的指令解碼邏輯436便解碼該指令，圖4的非假想目標地址計算器416、非假想調用/返回堆棧414以及非假想分支方向預測裝置412則依圖4的指令解碼數據492產生非假想分支預測。指令解碼邏輯436在步驟1402中，產生該指令的類型數據於指令解碼數據492中。尤其，指令解碼邏輯436會確定該指令是否為分支指令、指令的長度以及分支指令的類型。最好(preferably)指令解碼邏輯436會確定分支指令是否為條件或無條件類型分支指令、PC相關類型分支指令、返回指令、直接類型分支指令或間接類型分支指令。若該指令為一分支指令，非假想分支方向預測裝置412會產生圖4的非假想方向預測444。此外，非假想目標地址計算器416則計算圖3的非假想目標地址354。最後，若該指令為一返回指令，則非假想調用/返回堆棧414產生圖3的非假想返回地址355。在步驟1404中，控制邏輯404會確定分支指令是否為條件分支指令。也就是，控制邏輯404會確定該指令是否依靠一條件而被採用或不被採用，該條件像是旗標(flag)位是否設定，如零旗標(zeroflag)、進位旗標(carryflag)等等。在x86指令集中，JCC指令是條件類型的分支指令。相對地，RET、CALL與JUMP指令，則是無條件分支指令，因為這些指令總會有一被採用的方向。若該指令為條件類型的分支指令，則在步驟1412中，控制邏輯404會確定非假想分支方向預測裝置412所預測的非假想方向預測444以及BTAC402所預測SBI454中圖7的假想方向722兩者間，是否不相匹配。若有方向預測上的不匹配，則在步驟1414中，控制邏輯404會確定非假想方向預測444是否要被採用。若非假想方向預測444不被採用，則在步驟1414中，控制邏輯404會控制多工器422選取圖4的NSIP466，以分支至現行分支指令後的指令。也就是，控制邏輯404選擇性地覆蓋假想的BTAC402方向預測。假想方向預測722之所以被覆蓋，是因非假想方向預測444一般比較準確。若非假想方向預測444被採用，則在步驟1432中，控制邏輯404會控制多工器422分支至非假想目標地址354。同樣地，假想方向預測722之所以被覆蓋，是因非假想方向預測444一般比較準確。若控制邏輯404於步驟1412確定並無方向預測上的不匹配，且已執行分支指令的假想分支(即，若SB位438被設定)，則在步驟1428中，控制邏輯404會確定假想目標地址352與非假想目標地址354間是否不相匹配。若有一條件類型分支的目標地址的不匹配，則在步驟1432中，控制邏輯404會控制多工器422分支至非假想目標地址354。假想目標地址預測352會被覆蓋，此因非假想目標地址預測354一般更為準確。若沒有一條件類型分支的目標地址的不匹配，則不會採取任何行動。也就是，允許進行假想分支，並接受錯誤更正的管制，如關於圖10部分所述。若在步驟1404中，控制邏輯404確定該分支指令不是條件類型的分支，則於步驟1406控制邏輯404會確定該分支指令是否為返回指令。若該分支指令是返回指令，則在步驟1418中，控制邏輯404會確定假想調用/返回堆棧406產生的假想返回地址353與非假想調用/返回堆棧414產生的非假想返回地址355兩者間，是否不相匹配。若假想返回地址353與非假想返回地址355兩者不相匹配，則在步驟1422中，控制邏輯404會控制多工器422分支至非假想返回地址355。也就是，控制邏輯404選擇性地覆蓋假想返回地址353。假想返回地址353之所以被覆蓋，是因非假想返回地址355一般比較準確。若沒有一直接類型分支的目標地址的不匹配，則不會採取任何行動。也就是，允許進行假想分支，並接受錯誤更正的管制，如關於圖10部分所述。請注意步驟1418與1422分別對應到圖13的步驟1324與1326。若在步驟1406中，控制邏輯404確定該分支指令不是返回指令，則於步驟1408控制邏輯404會確定該分支指令是否為PC相關類型的分支指令。在x86指令集中，PC相關類型的分支指令所指定的帶正負號的位移量會加上現行程序計數器的值，以計算目標地址。在另一具體實施例中，控制邏輯404於步驟1408也會確定該分支指令是否為直接類型的分支指令。在x86指令集中，直接類型的分支指令於自身內即指定目標地址。直接類型的分支指令也被稱為立即類型(immediatetype)的分支指令，因為目標地址被指定於指令的立即欄位(immediatefield)。若該分支指令為PC相關類型的分支指令，則在步驟1424中，控制邏輯404會確定假想目標地址352與非假想目標地址354間是否不相匹配。若有一PC相關類型分支的目標地址的不匹配，則在步驟1426中，控制邏輯404會控制多工器422分支至非假想目標地址354。假想目標地址預測352會被覆蓋，此因非假想目標地址預測354對PC相關類型的分支而言一般更為準確。若沒有一PC相關類型分支的目標地址的不匹配，則不會採取任何行動。也就是，允許進行假想分支，並接受錯誤更正的管制，如關於圖10部分所述。若在步驟1408中，控制邏輯404確定該分支指令不是PC相關類型的分支指令，則不會採取任何行動。也就是，允許進行假想分支，並接受錯誤更正的管制，如關於圖10部分所述。在一具體實施例中，非假想目標地址計算器416在F-階段312包括一相當小的分支目標緩衝器(branchtargetbuffer，BTB)，僅用來快取間接類型分支指令的分支目標地址，如前面關於圖4部分所述。可以看出，對間接類型的分支指令而言，BTAC402的預測一般是比相當小的F-階段312BTB更為準確。所以，若確定該分支為一間接類型的分支指令，控制邏輯404不會覆蓋BTAC402的假想預測。也就是，若一間接類型分支指令的假想分支因圖8所述的BTAC402命中而執行，則控制邏輯404會通過分支至間接類型的BTB目標地址，而不覆蓋該假想分支。然而，即使在此間接類型的分支中，BTAC402所產生的假想目標地址352未被非假想目標地址354給覆蓋，在流水線300稍後仍會於假想目標地址352與圖3從S-階段328接收的非假想目標地址356兩者間，做一目標地址的比較，以執行圖10的步驟1036，偵測錯誤的假想分支。現請參照圖15，其為依本發明繪示的用來置換圖4BTAC402中目標地址的裝置的方塊圖。為了簡明起見，關於BTAC402的多路關聯性的數據，像是圖6的多路與路多工器606，並未顯示。圖6BTAC402的數據數組612顯示其包括了一選定的BTAC402快取線，其中具有項目A602A與項目B602B，分別通過圖6的信號624與626送至控制邏輯404。項目A602A與項目B602B各包括其相關的圖7VALID位702。該選定的BTAC402快取線亦包括一A/BLRU(leastrecentlyused)位1504，以指出項目A602A與項目B602B兩者中，哪一個最近最少被使用到。在一具體實施例中，每次一發生命中BTAC402的一既定目標地址714，A/BLRU位1504就被更新，以指定發生命中項目的相對項目。也就是，若控制邏輯404因項目A602A發生命中而進行至圖8的步驟812，則A/BLRU位1504就被更新成顯示項目B602B。相反地，若控制邏輯404因項目B602B發生命中而進行至圖8的步驟832，則A/BLRU位1504就被更新成顯示項目A602A。A/BLRU位1504也被送至控制邏輯404。此置換裝置也包括一多工器1506。多工器1506接收圖4提取地址495與一更新指令指針(IP)作為輸入。多工器1506依據控制邏輯404提供的讀/寫控制信號1516來選取其中一輸入。讀/寫控制信號1516亦被送至BTAC402。當讀/寫控制信號1516顯示為「讀」，則多工器1506選取提取地址495，經由信號1514送至BTAC402，以讀取BTAC402。當讀/寫控制信號1516顯示為「寫」，則多工器1506選取更新IP1512，經由信號1514送至BTAC402，以通過圖4信號442將一更新目標地址714與/或SBI454與/或A/BLRU位1504寫入BTAC402。當一分支指令執行且被採用，該分支指令的目標地址714以及相關聯的SBI454會被寫入，或快取於，一BTAC402項目602。也就是，用已執行的分支指令的新目標地址714及相關聯的SBI454來更新BTAC402。控制邏輯404必須決定在BTAC402的哪一邊，A或B，來更新由更新IP1512選取的BTAC402快取線與路。也就是，控制邏輯404必須決定是否要置換所選取的快取線與路的項目A602A或項目B602B。控制邏輯404如下表一所示來決定置換哪一邊。ValidAValidBReplace00--LastWritten01A10B11LRU表一表一為具有兩個輸入的真值表(truthtable)，兩個輸入為項目A602A的VALID位702與項目B602B的VALID位702。該真值表的輸出用以決定要置換BTAC402的哪一邊。如表一所示，若A項目602A無效且B項目602B有效，則控制邏輯404將A項目602A置換掉。若A項目602A有效且B項目602B無效，則控制邏輯404將B項目602B置換掉。若A項目602A與B項目602B皆有效，則控制邏輯404將最近較少被使用的項目置換掉，而此項目是由更新IP1512所選取BTAC402快取線與路中的A/BLRU位1504來指定。若A項目602A與B項目602B皆無效，則控制邏輯404必須決定要置換哪一邊。一種解決方式是總是寫到某一邊，如A。然而，這種解決方式會造成如下程序代碼序列1所示的問題。0x00000010JMP0X000000140x00000014ADDBX，10x00000016CALL0x12345678程序代碼序列1在程序代碼序列1中，此三個指令都位在相同的指令高速緩存432的快取線內，因為其指令指針地址除了較低的四個地址位外餘皆相同；因此，JMP與CALL指令選取相同的BTAC402快取線與路。假設此範例中，當指令執行時，由JMP與CALL指令所選取BTAC402快取線與路內的A項目602A與B項目602B皆無效。使用「當兩個項目皆無效時，總是更新A這一邊」的解決方式，JMP指令將見到兩邊皆為無效，且將更新A項目602A。然而，由於在程序序列中CALL指令相當接近JMP指令，若流水線相當長，如處理器300，則在A項目602A的VALID位702被更新前，有相當多數量的周期可能會通過。因此，在BTAC402被已執行的JMP指令更新前，特別是在A項目602A的VALID位702與所選取BTAC402快取線的BTAC402路置換狀態被JMP指令更新之前，CALL指令非常有可能會選取BTAC402。所以，CALL指令將見到兩邊皆為無效，而且也將依「當兩個項目皆無效時，總是更新A這一邊」的解決方式，來更新A項目602A。這樣做是有問題的，因為JMP指令的目標地址714將由於一空的即無效的B項目602B可用來快取CALL指令的目標地址714而不必要地被取代。為解決如表一所示的問題，若A項目602A與B項目602B皆無效，則控制邏輯404最好選取存於一全域置換狀態旗標緩存器即LastWritten1502的一邊或其相反邊。LastWritten緩存器1502包括於置換裝置，並由其來更新。LastWritten緩存器1502儲存一指示，其顯示就BTAC402整體而言，其A邊或B邊是否為最後被寫到一無效的BTAC402項目602。有利地，此方法使用LastWritten緩存器1502以避免前面程序代碼序列1所示的問題，如現在關於圖16與17部分所要敘述的。現請參照圖16，其為依本發明圖15裝置的一運作方法的流程圖。圖16闡明了上述表一的一具體實施例。當控制邏輯404需要去更新BTAC402的項目602時，控制邏輯404會分別檢查所選取的A項目602A與B項目602B的VALID位702。在步驟1602中，控制邏輯404會確定是否A項目602A與B項目602B兩者皆為有效。若兩個項目皆有效，則在步驟1604中，控制邏輯404會檢查A/BLRU位1504以確定A項目602A或B項目602B為最近最少被使用者。若A項目602A為最近最少被使用者，則控制邏輯404於步驟1606將A項目602A置換掉。若B項目602B為最近最少被使用者，則控制邏輯404於步驟1608將B項目602B置換掉。若控制邏輯404於步驟1602中確定並非兩個項目都無效，則在步驟1612中，控制邏輯404會確定是否為A項目602A有效而B項目602B無效。若是，則控制邏輯404於步驟1614將B項目602B置換掉。不然，在步驟1622中，控制邏輯404會確定是否為A項目602A無效而B項目602B有效。若是，則控制邏輯404於步驟1624將A項目602A置換掉。否則，在步驟1632中，控制邏輯404會檢查LastWritten緩存器1502。若LastWritten緩存器1502顯示BTAC402的A邊並非最後被寫到一選定的快取線與路中，而在此選定的快取線與路中A項目602A與B項目602B皆為無效，則控制邏輯404於步驟1634將A項目602A置換掉。控制邏輯404接著於步驟1636更新LastWritten緩存器1502，以指定BTAC402的A邊為最後被寫到一選定快取線與路的邊，而在此選定的快取線與路中A項目602A與B項目602B皆為無效。若LastWritten緩存器1502顯示BTAC402的B邊並非最後被寫到一選定的快取線與路中，而在此選定的快取線與路中A項目602A與B項目602B皆為無效，則控制邏輯404於步驟1644將B項目602B置換掉。控制邏輯404接著於步驟1646更新LastWritten緩存器1502，以指定BTAC402的B邊為最後被寫到一選定快取線與路的邊，而在此選定的快取線與路中A項目602A與B項目602B皆為無效。可以看出，圖16的方法可避免在上述程序代碼序列1中，以CALL指令的目標地址覆寫掉JMP指令的目標地址。假設當JMP指令執行時，LastWritten緩存器1502指定了A邊。既然B邊並不是最後被寫的，控制邏輯404將依據圖16與表一來更新B項目602B。此外，控制邏輯404將更新LastWritten緩存器1502以指定B邊。因此，當CALL指令執行時，控制邏輯404將依據圖16更新A項目602A，此因當BTAC402被選取時，兩個項目皆無效，且LastWritten緩存器1502指明了A邊並不是最後被寫到。因此，有利地，JMP與CALL指令兩者的目標地址將快取於BTAC402，供後續的假想分支使用。現請參照圖17，其為依本發明的另一具體實施例繪示圖15裝置的一運作方法的流程圖。圖17的步驟除了兩個額外步驟外，其餘皆與圖16的步驟相同。在此另一具體實施例中，控制邏輯404在置換一無效的項目後，會更新LastWritten緩存器1502，即使另一項目為有效的。因此，在圖17，於步驟1614置換了B項目602B後，在步驟1716中，控制邏輯404將更新LastWritten緩存器1502以指定B邊。此外，於步驟1624置換了A項目602A後，在步驟1726中，控制邏輯404將更新LastWritten緩存器1502以指定A邊。雖然實際的仿真並未看到圖16與17的實施例在效能上有顯著差別，但可看出圖16實施例解決了圖17實施例所無法處理的一個問題。此問題以下述程序代碼序列2來解說。0x00000010JMP0x123456780x12345678JMP0x000000140x00000014JMP0x20000000程序代碼序列2位於指令指針0x00000010與0x00000014的兩個JMP指令都在同一條指令高速緩存432快取線中，並選取BTAC402內相同的快取線。位於指令指針0x12345678的JMP指令則在另一條指令高速緩存432快取線中，並選取BTAC402內另一條不同的快取線。當JMP0x12345678指令執行時，假設有下列情況存在。LastWritten緩存器152指定了B邊。由JMP0x12345678指令與JMP0x20000000指令的指令指針所選取BTAC402快取線與路中的A項目602A與B項目602B兩者皆為無效。由JMP0x00000014指令的指令指針所選取的BTAC402快取線與路則顯示A項目602A有效而B項目602B無效。假設在JMP0x12345678指令更新BTAC402前，執行JMP0x20000000指令。因此，JMP0x12345678與JMP0x20000000指令的指令指針在相同BTAC402快取線中選取相同的路。依據圖16與17，當JMP0x12345678執行時，控制邏輯404將於步驟1634以JMP0x12345678的目標地址來置換A項目602A，並在步驟1636更新LastWritten緩存器1502以指定A邊。依據圖16與17，當JMP0x00000014執行時，控制邏輯404將於步驟1614以JMP0x00000014的目標地址來置換B項目602B。依據圖17，控制邏輯404將於步驟1716更新LastWritten緩存器1502以指定B邊。然而，依據圖16，控制邏輯404將不會更新LastWritten緩存器1502；而是，LastWritten緩存器1502將繼續指定A邊。因此，當JMP0x00000020執行時，依據圖17，控制邏輯404將於步驟1634以JMP0x00000020的目標地址來置換A項目602A，用來needlesslyclobberingJMP0x12345678的目標地址。相反地，依據圖16，當JMP0x00000020執行時，控制邏輯404將於步驟1644置換B項目602B，用來有利地使A項目602A中JMP0x12345678的目標地址保持不變。現請參照圖18，其為依本發明的另一具體實施例繪示的用以進行圖4BTAC402中目標地址置換動作的裝置方塊圖。圖18的實施例類似於圖15的實施例。然而，在圖18的實施例中，A/BLRU位1504與兩個項目的T/NT位722，顯示為T/NTA722A與T/NTB722B，儲存於一另外的數組1812，而非數據數組612。此額外的數組1812是雙埠的；而數據數組612卻是單埠。因為A/BLRU位1504與T/NT位722比起項目602的其它欄位更常被更新，對較常被更新的欄位提供雙埠的存取，可減低在高存取量期間於BTAC402形成瓶頸的可能性。然而，由於雙埠的高速緩存數組比單埠的高速緩存數組來得大，且消耗更多功率，較少被存取的欄位就儲存在單埠的資料數組612。現請參照圖19，其為依本發明的另一具體實施例繪示的用以進行圖4BTAC402中目標地址置換動作的裝置方塊圖。圖19的實施例類似於圖15的實施例。然而，圖19的實施例中，每一BTAC402快取線與路皆包括一第三項目，項目C602C。項目C602C通過信號1928送至控制邏輯404。有利地，圖19的實施例支持假想分支至三個分支指令中任一個的能力，而此三個分支指令快取由提取地址495所選取的一對應的指令高速緩存432快取線中；或者，在一實施例中，支持假想分支至快取於一對應的指令高速緩存432半快取線的三個分支指令中的任一個。除此之外，圖19的實施例不使用LastWritten緩存器1502，取而代之的是一緩存器1902，其包括一LastWritten值與一LastWrittenPrev值。當LastWritten值要更新時，控制邏輯404在更新LastWritten值之前，便將LastWritten值的內容複製到LastWrittenPrev值。LastWritten值與LastWrittenPrev值這兩個值一起使得控制邏輯404得以確定三個項目中哪一個是最近最少被寫到的，如現在於表二及其後的等式所描述的。表二類似於表一，除了表二有三個輸入，包括項目C602C的附加的VALID位702。在等式中，「lw」對應至LastWritten值，「lwp」LastWrittenPrev值。在一具體實施例中，只有當所有三個項目皆為無效時，才更新LastWritten與LastWrittenPrev的值，類似於圖16的方法。在另一具體實施例中，任何時候控制邏輯404更新了一無效的項目，LastWritten與LastWrittenPrev的值就會更新，類似於圖17的方法。表二LRW＝AOlderThanB？LRWofAandCLRWofBandCLRWofAandB＝AOlderThanB？ABLRWofAandC＝AOlderThanC？ACLRWofBandC＝BOlderThanC？BCAOlderThanB＝(lw＝＝B)|((lwp＝＝B(lw！＝A))BOlderThanC＝(lw＝＝C)|((lwp＝＝C(lw！＝B))AOlderThanC＝(lw＝＝C)|((lwp＝＝C(lw！＝A))雖然本發明及其目的、特徵與優點已詳細敘述了，其它具體實施例仍涵蓋在本發明的範圍內。例如，BTAC可用任何數量的高速緩存來配置，包括直接映像(direct-mapped)、完全關聯(fullyassociative)或不同數目的路高速緩存。再者，BTAC的大小可增或減。而且，一提取地址，而不是位於實際包括被預測分支指令的快取線的提取地址，可用來檢索BTAC與分支歷史表。例如，先前提取指令的提取地址可用來在分支前減低指令泡沫的大小。此外，儲存於高速緩存的每一路的目標地址數量可能改變。另外，分支歷史表的大小可能改變，且存於其中的位的數目與方向預測數據的形式，以及檢索分支歷史表的算法(algorithm)也可能改變。再者，指令高速緩存的大小可能改變，且用以檢索指令高速緩存與BTAC的虛擬提取地址的類型也可能改變。總之，以上所述僅為本發明的較佳實施例而已，當不能限定本發明所實施的範圍。凡是依本發明權利要求所作的等效變化與修飾，皆應仍屬於本發明專利涵蓋的範圍內。LRWofAandC＝AOlderThanC？ACLRWofBandC＝BOlderThanC？BCAOlderThanB＝(lw＝＝B)|((lwp＝＝B(lw！＝A))BOlderThanC＝(lw＝＝C)|((lwp＝＝C(lw！＝B))AOlderThanC＝(lw＝＝C)|((lwp＝＝C(lw！＝A))238表二類似於表一，除了表二有三個輸入，包括項目C702C的附加的VALID位702。在等式中，「lw」對應至LastWritten值，「lwp」LastWrittenPrev值。在一具體實施例中，只有當所有三個項目皆為無效時，才更新LastWritten與LastWrittenPrev的值，類似於圖16的方法。在另一具體實施例中，任何時候控制邏輯404更新了一無效的項目，LastWritten與LastWrittenPrev的值就會更新，類似於圖17的方法。239雖然本發明及其目的、特徵與優點已詳細敘述了，其它具體實施例仍涵蓋在本發明的範圍內。例如，BTAC可用任何數量的高速緩存來配置，包括直接映像(direct-mapped)、完全關聯(fullyassociative)或不同數目的路高速緩存。再者，BTAC的大小可增或減。而且，一提取地址，而不是位於物理包括被預測分支指令的快取線的提取地址，可用來檢索BTAC與分支歷史表。例如，先前提取指令的提取地址可用來在分支前減低指令泡沫的大小。此外，儲存於高速緩存的每一路的目標地址數量可能改變。另外，分支歷史表的大小可能改變，且存於其中的位的數目與方向預測數據的形式，以及檢索分支歷史表的算法(algorithm)也可能改變。再者，指令高速緩存的大小可能改變，且用以檢索指令高速緩存與BTAC的虛擬提取地址的類型也可能改變。240總之，以上所述僅為本發明的較佳實施例而已，當不能以的限定本發明所實施的範圍。凡是依本發明權利要求所作的均等變化與修飾，皆應仍屬於本發明專利涵蓋的範圍內。權利要求1.一種用於一微處理器內的分支裝置，該裝置利用一提取地址選取一指令高速緩存中的一快取線，該裝置亦使用該提取地址來假想預測一分支指令是否將被採用，該分支指令可能潛在地(potentially)存在於該指令快取線中，其特徵在於，該裝置包括一第一預測裝置，對應至該提取地址，依據該提取地址預測該分支指令是否將被採用；一邏輯，對應至該提取地址，提供該提取地址與一全域分支歷史的一二進位函數於該邏輯的一輸出端；一第二預測裝置，對應至該邏輯的輸出端，依據該輸出預測該分支指令是否將被採用；一選擇器，對應至該提取地址，依據該提取地址選取該第一與第二預測裝置其中之一。2.如權利要求1所述的裝置，其特徵在於，該二進位函數包括至少一部份該提取地址與該全域分支歷史的一異或運算。3.如權利要求1所述的裝置，其特徵在於，該第一預測裝置由該提取地址所檢索的一分支目標地址高速緩存所提供。4.如權利要求1所述的裝置，其特徵在於，該第二預測裝置由提取地址與該全域分支歷史的該二進位函數所檢索的一分支歷史表所提供。5.如權利要求1所述的裝置，其特徵在於，該選擇器由該提取地址所檢索的一分支目標地址高速緩存所提供。6.如權利要求1所述的裝置，其特徵在於，該選擇器包括一位，用以在該第一與第二預測間做選擇。7.如權利要求1所述的裝置，其特徵在於，每一該第一與第二預測裝置包括數個預測該分支指令是否將被採用的預測器，其中該選擇器包括數個對應於該數個預測器的位，用以在所對應的該數個第一與第二預測器間做選擇。8.如權利要求1所述的裝置，其特徵在於，該選擇器包括一飽和上/下數計數器。9.如權利要求8所述的裝置，其特徵在於，該飽和上/下數計數器從下列情形的一儲存一選取值(selectionvalue)極可能是第一預測裝置(stronglyfirstpredictor)、有可能是第一預測裝置(weaklyfirstpredictor)、有可能是第二預測裝置(weaklysecondpredictor)以及極可能是第二預測裝置(stronglysecondpredictor)。10.如權利要求1所述的裝置，其特徵在於，還包括一緩存器，對應至該第二預測裝置，儲存該全域分支歷史。11.如權利要求10所述的裝置，其特徵在於，該緩存器包括一N位移位緩存器，以儲存微處理器所執行的分支指令是否被採用的N個先前結果。12.一種假想分支預測裝置，位在具有一指令高速緩存的一流水線化微處理器中，該指令高速緩存接收一地址總線上的一提取地址，以選取該指令高速緩存的一快取線，一分支指令被假定存在於該快取線中，其特徵在於，該裝置包括一假想分支歷史表(BHT)，提供該分支指令的一第一方向預測；一分支目標地址高速緩存(BTAC)，對應至該地址總線，提供該分支指令的一第二方向預測，並提供一選擇預測，用以在該第一與第二方向預測間作選擇；以及一多工器，對應至該BHT與該BTAC，依據該選擇預測選取該第一與第二方向預測其中之一；其中該第二方向預測系響應該提取地址而提供，即使該分支指令可能並不存在於該指令快取線中。13.如權利要求12所述的裝置，其特徵在於，還包括一全域分支歷史緩存器，對應至該BHT，儲存微處理器先前所執行數個分支指令的方向的一全域歷史。14.如權利要求13所述的裝置，其特徵在於，BHT響應該指令高速緩存提取地址與存於該全域分支歷史緩存器的全域歷史的一函數，而提供該第一方向預測。15.如權利要求14所述的裝置，其特徵在於，該函數包括存於該全域分支歷史緩存器的全域歷史與一部份該指令高速緩存提取地址的一邏輯的異或運算。16.如權利要求14所述的裝置，其特徵在於，BHT包括一具數個儲存組件的數組，以儲存數個方向預測，其中該數組由指令高速緩存提取地址與該全域歷史的該函數作索引。17.如權利要求16所述的裝置，其特徵在於，每一該些儲存組件被組態為儲存數個方向預測，以供選取作為該第一方向預測。18.如權利要求12所述的裝置，其特徵在於，該第一方向預測、該第二方向預測以及該選擇預測的每一個皆包括數個預測。19.如權利要求18所述的裝置，其特徵在於，該多工器為每一該第一與第二方向預測選取該數個預測之一，以響應一對應的其中一該數個選擇預測。20.在如權利要求19所述的裝置，其特徵在於，還包括一控制邏輯，對應至該多工器，從該多工器接收每一該第一與第二方向預測的所選取的其中一該數個預測，該控制邏輯組態為依據所選取的其中一該數個預測，使微處理器選擇性地進行假想分支或不分支。21.如權利要求20所述的裝置，其特徵在於，該控制邏輯被組態為使微處理器選擇性地假想分支至該BTAC響應提取地址所提供的一假想分支目標地址。22.一種用在一微處理器中的假想分支目標地址高速緩存(BTAC)，其特徵在於，該BTAC包括一數組，組態為儲存數個分支指令的方向預測；一輸入，對應至該數組，組態為接收一指令高速緩存的提取地址，該提取地址檢索該數組，以選取該數個方向預測其中之一；以及一輸出，對應至該數組，提供所選取的方向預測至一分支控制邏輯；其中若所選取的方向預測指定一採用方向，則不管是否有一分支指令存在於該提取地址所檢索的指令高速緩存的一快取線中，該分支控制邏輯皆使微處理器進行假想分支。23.一種用於假想分支的微處理器，其特徵在於，包括一指令高速緩存，提供一地址總線上的一提取地址所選取的一指令字節線；一假想分支歷史表(BHT)，對應至該地址總線，提供一分支指令是否將被採用的一第一預測，該分支指令被假定存在於該指令快取線，該第一預測系依據該提取地址與一全域分支歷史的一組合而提供；一假想分支目標地址高速緩存(BTAC)，對應至該地址總線，提供該假定的分支指令的一第二預測，並提供一選擇器；以及一控制邏輯，對應至該BHT與BTAC，若該選擇器所選取的該第一與第二預測其中之一預測該假定的分支指令將被採用，則該控制邏輯使微處理器進行假想分支。24.如權利要求23所述的微處理器，其特徵在於，該控制邏輯使微處理器假想分支至BTAC依據該提取地址而提供的一假想分支目標地址。25.如權利要求23所述的微處理器，其特徵在於，還包括一假想調用/返回堆棧，對應至BTAC，儲存數個假想返回地址；其中該控制邏輯使微處理器假想分支至該假想調用/返回堆棧依據該提取地址而提供的其中一該數個假想返回地址。26.如權利要求25所述的微處理器，其特徵在於，BTAC被組態為提供一指示，以指出該假定的分支指令是否為返回指令。27.如權利要求26所述的微處理器，其特徵在於，只有在該指示指出該假定的分支指令是返回指令時，該控制邏輯才使微處理器假想分支至該假想調用/返回堆棧所提供的假想返回地址。28.如權利要求27所述的微處理器，其特徵在於，BTAC被組態為提供一指示，以指出該假定的分支指令是否為調用指令。29.如權利要求28所述的微處理器，其特徵在於，若該指示指出該假定的分支指令是調用指令，則該控制邏輯使該假想調用/返回堆棧所提供的假想返回地址被推入該假想調用/返回堆棧中。30.如權利要求23所述的微處理器，其特徵在於，該選擇器系響應該假定分支指令是否會被採用的一解析方向而更新。31.如權利要求30所述的微處理器，其特徵在於，若該第一與第二預測中一被選取的預測是不正確的，且若該第一與第二預測中一未被選取的預測是正確的，則該選擇器系響應該解析方向而更新。32.如權利要求31所述的微處理器，其特徵在於，該選擇器系通過切換(toggling)該選擇器而更新。33.如權利要求31所述的微處理器，其特徵在於，該選擇器系通過使選擇器朝該未被選取的預測計數而更新。34.如權利要求23所述的微處理器，其特徵在於，該BHT包括一具數個儲存組件的數組，用來為數個分支指令的每一個儲存一分支歷史。35.如權利要求34所述的微處理器，其特徵在於，為該數個分支指令的每一個所儲存的該分支歷史包括一被採用/不被採用(taken/nottaken)位。36.如權利要求34所述的微處理器，其特徵在於，為該數個分支指令的每一個所儲存的該分支歷史包括一飽和上/下數計數器。37.一種在一微處理器中進行假想分支的方法，其特徵在於，該方法包括產生一指令的數個假想分支方向預測；選取該數個假想分支方向預測的一作為一最後方向預測；以及若該最後方向預測指出該指令將被採用，則使微處理器進行假想分支；其中該產生、選取以及假想分支的動作皆在解碼該指令之前執行。38.如權利要求37所述的方法，其特徵在於，還包括在該假想分支的動作之後，偵測該最後方向錯誤地指出該指令將被採用。39.如權利要求38所述的方法，其特徵在於，還包括因應該偵測動作，分支至一正確目標地址。40.一種在一微處理器中進行假想分支的方法，其特徵在於，該方法包括產生一分支指令是否將被採用的第一與第二預測，以響應於一指令高速緩存提取地址的第一與第二二進位函數；選取該第一與第二預測其中之一作為一最後預測，該選取的動作系響應該提取地址的一第三二進位函數而執行；以及若該最後預測指出該分支指令將被採用，則微處理器進行假想分支其中不論該分支指令是否存在於該提取地址所選取的一指令快取線中，該產生、選取以及假想分支的動作皆被執行。41.如權利要求40所述的方法，其特徵在於，該第一與第二函數系不同的函數。42.如權利要求40所述的方法，其特徵在於，該第二二進位函數包括該提取地址與一全域分支歷史的一二進位函數。43.如權利要求42所述的方法，其特徵在於，該第二二進位函數包括至少一部分該提取地址與該全域分支歷史的一異或運算。44.如權利要求40所述的方法，其特徵在於，該第一與第三二進位函數系相同的函數。45.如權利要求44所述的方法，其特徵在於，該第一與第三二進位函數包括一預先決定(predetermined)數量的該提取地址的最低有效位。45.如權利要求16所述的微處理器，其特徵在於，該假想BTAC與該指令高速緩存實質上被並行存取。46.一種用以從錯誤地分支至一假想目標地址的情況回復的方法，其特徵在於，包括為一分支指令產生一假想目標地址，該分支指令被假定存在於一提取地址所選取的一指令快取線中；分支至該假想目標地址，不論該假定的分支指令是否存在於該指令快取線中；在產生該假想目標地址後，產生該假定的分支指令的一正確目標地址；確定該假想目標地址是否匹配該正確目標地址；以及若假想目標地址不匹配該正確目標地址，則分支至該正確目標地址。47.如權利要求46所述的方法，其特徵在於，還包括在該確定動作之前，儲存一指示，以指出該分支至假想目標地址的動作是否發生；以及只有在該指示指出該分支至假想目標地址的動作發生時，才進行該分支至該正確目標地址的動作。48.如權利要求46所述的方法，其特徵在於，該產生正確目標地址的動作包括使用假定的分支指令的數個指令字節來計算該正確目標地址。49.如權利要求46所述的方法，其特徵在於，還包括若該假想目標地址不匹配該正確目標地址，則以該正確目標地址更新一分支目標地址高速緩存中的一包括該假想目標地址的項目。50.一種用以從錯誤地分支至一分支指令的一假想目標地址的情況回復的方法，該分支指令被假定存在於一指令快取線中，該指令快取線由一指令高速緩存響應一提取地址而提供，該假想目標地址由一分支目標地址高速緩存(BTAC)響應該提取地址而假想地產生，其特徵在於，該方法包括在BTAC假想地產生該假想目標地址後，解碼該假定的分支指令；因應該解碼動作，確定該假定的分支指令是否為一非分支指令；以及若該假定的分支指令為一非分支指令，則分支至該假定的分支指令的一指令指針。51.如權利要求50所述的方法，其特徵在於，還包括因應該解碼動作，計算該假定的分支指令的該指令指針。52.如權利要求50所述的方法，其特徵在於，還包括若該假定的分支指令為一非分支指令，則使BTAC中一包括該假想目標地址的項目無效。53.如權利要求52所述的方法，其特徵在於，使該項目無效的動作先於該分支至該指令指針的動作而執行。54.一種用以從錯誤地分支至一假想目標地址的情況回復的方法，該假想目標地址關聯於假定存在於一提取地址所選取一快取線中的一分支指令，該假想目標地址由一分支目標地址高速緩存(BTAC)響應該提取地址而提供，其特徵在於，該方法包括在BTAC提供該假想目標地址後，解碼該假定的分支指令；確定該假定的分支指令的一長度；以及若假定的分支指令的該長度與分支目標地址高速緩存所假想提供的一指令長度不相匹配，則分支至該假定的分支指令的一指令指針。55.如權利要求54所述的方法，其特徵在於，還包括若假定的分支指令的該長度與分支目標地址高速緩存所假想提供的該指令長度不相匹配，則使BTAC中一包括該假想目標地址的項目無效。56.如權利要求55所述的方法，其特徵在於，使該項目無效的動作先於該分支至該指令指針的動作而執行。57.一種用以從錯誤地分支至一假想目標地址的情況回復的方法，其特徵在於，包括產生一分支指令的一假想目標地址，該分支指令被假定存在於一提取地址所選取一指令快取線中；產生該假定的分支指令的一假想方向預測；分支至該假想目標地址，不論該假定的分支指令是否存在於該指令快取線中；在產生該假想方向預測後，產生該假定的分支指令的一正確方向；確定該正確方向是否不被採用；以及若該正確方向不被採用，則分支至假定的分支指令的下個指令的一指令指針。58.如權利要求57所述的方法，其特徵在於，還包括若該正確方向不被採用，則響應該正確方向而更新一分支目標地址高速緩存中的該假想方向預測。59.一種用於一微處理器中的裝置，用以偵測是否錯誤地分支至一假想調用/返回堆棧所提供的一假想返回地址，其特徵在於，該裝置包括一儲存組件，儲存一指示，以指出該微處理器是否在不知關聯於該指示的一指令是否為分支指令的情況下，分支至該假想返回地址；一指令解碼邏輯，組態為在微處理器分支至該假想返回地址後接收並解碼該指令；一預測檢查邏輯，對應至該指令解碼邏輯，用以告知分支控制邏輯，若指令解碼邏輯指出該指令不是分支指令且該指示顯示微處理器分支至假想返回地址，則微處理器已錯誤地分支至假想返回地址。60.一種微處理器，用以偵測及更正一錯誤的假想分支，其特徵在於，包括一指令高速緩存，提供一提取地址所選取的一指令字節線；一假想調用/返回堆棧，因應該提取地址而提供一先前執行的分支指令的一假想返回地址，不論該先前執行的分支指令是否存在於該指令字節線中；一控制邏輯，對應至該假想調用/返回堆棧，組態為控制一多工器在一第一周期選取該假想返回地址作為提取地址；以及一預測檢查邏輯，對應至該控制邏輯，用以偵測控制邏輯是否控制該多工器錯誤地選取了該假想返回地址；其中該控制邏輯更組態為控制該多工器在一第二周期選取一正確地址作為提取地址，控制邏輯選取該正確地址，以響應預測檢查邏輯偵測到控制邏輯控制該多工器錯誤地選取了該假想返回地址。61.一種用於一微處理器中的方法，用以從錯誤地分支至一假定分支指令的一假想目標地址的情況回復，其特徵在於，該方法包括因應一指令高速緩存的提取地址而提供一假想目標地址；因應該指令高速緩存的提取地址而產生一指令快取線；在提供該假想目標地址後從該指令快取線解碼一指令；其中該微處理器為第一次執行該指令的解碼；在該解碼動作前分支至該假想目標地址；以及在該分支至假想目標地址的動作後，響應該解碼動作分支至該指令的一正確的目標地址。62.一種用以從錯誤地分支至一假想目標地址的情況回復的方法，其特徵在於，包括提供一分支指令的一假想目標地址，該分支指令被假定存在於一提取地址所選取一指令快取線中；分支至該假想目標地址，不論該假定的分支指令是否存在於該指令快取線中；以及若該假定的分支指令不存在於該指令快取線中，則更正一錯誤的分支。63.一種用於一微處理器中的分支裝置，用以偵測該微處理器何時錯誤地分支至一假想目標地址，該假想目標地址由一分支目標地址高速緩存(BTAC)所提供，其特徵在於，該裝置包括一分支命中指示，用以指出該微處理器何時分支至該假想目標地址，不論關聯於該分支命中指示的一指令是否為分支指令，皆提供該分支命中指示；一指令解碼邏輯，組態為接收及解碼該指令，並指出該指令是否為分支指令；一預測檢查邏輯，對應至該指令解碼邏輯，用以確定該微處理器錯誤地分支至該假想目標地址；其中當指令解碼邏輯指出該指令不是分支指令，以及該分支命中指示顯示該微處理器分支至該假想目標地址時，該微理器即為錯誤地分支至該假想目標地址。全文摘要本發明涉及一種裝置，用以偵測由一流水線化微處理器所作的錯誤的假想分支，以及更正該錯誤的假想分支。一分支目標地址高速緩存(BTAC)快取已執行的分支指令的目標地址。在流水線初期，於解碼一指令前，基於一指令高速緩存的提取地址命中BTAC而執行一假想分支至一快取目標地址。當該假想分支執行時，一命中位被設定。稍後在流水線中，該假定的分支指令被解碼和執行。若該命中位因該指令而被設定，則檢查該已解碼的指令，並將正確的目標地址及方向與假想的版本做一比較，以確定該假想分支是否錯誤。若偵測到錯誤，該分支目標地址高速緩存就會更新或無效化，且處理器會分支至適當地址以更正錯誤。文檔編號G06F9/38GK1397879SQ0211855公開日2003年2月19日申請日期2002年4月27日優先權日2001年5月4日發明者葛蘭·亨利,湯瑪斯·麥當勞,泰瑞·派克斯申請人:智慧第一公司