[go: up one dir, main page]

TWI739159B - 基於載入路徑歷史的分支預測 - Google Patents

基於載入路徑歷史的分支預測 Download PDF

Info

Publication number
TWI739159B
TWI739159B TW108133781A TW108133781A TWI739159B TW I739159 B TWI739159 B TW I739159B TW 108133781 A TW108133781 A TW 108133781A TW 108133781 A TW108133781 A TW 108133781A TW I739159 B TWI739159 B TW I739159B
Authority
TW
Taiwan
Prior art keywords
branch
prediction
value
counter
instruction
Prior art date
Application number
TW108133781A
Other languages
English (en)
Other versions
TW202036284A (zh
Inventor
拉米穆罕默德Ａ 阿謝赫
麥可史考特 麥克維
羅伯特道格拉斯 克蘭西
德瑞克 豪爾
Original Assignee
美商高通公司
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 美商高通公司 filed Critical 美商高通公司
Publication of TW202036284A publication Critical patent/TW202036284A/zh
Application granted granted Critical
Publication of TWI739159B publication Critical patent/TWI739159B/zh

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3836—Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
    • G06F9/3842—Speculative instruction execution
    • G06F9/3848—Speculative instruction execution using hybrid branch prediction, e.g. selection between prediction techniques
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3836—Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
    • G06F9/3842—Speculative instruction execution
    • G06F9/3844—Speculative instruction execution using dynamic branch prediction, e.g. using branch history tables
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/30003—Arrangements for executing specific machine instructions
    • G06F9/3005—Arrangements for executing specific machine instructions to perform operations for flow control
    • G06F9/30058—Conditional branch instructions
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/32—Address formation of the next instruction, e.g. by incrementing the instruction counter
    • G06F9/322—Address formation of the next instruction, e.g. by incrementing the instruction counter for non-sequential address
    • G06F9/323—Address formation of the next instruction, e.g. by incrementing the instruction counter for non-sequential address for indirect branch instructions

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Advance Control (AREA)

Abstract

分支預測方法和系統包括：對於由處理器提取的分支指令，基於分支指令的程式計數器（PC）值的函數來為分支標識（ID）表編制索引，其中分支ID表的每個條目至少包括標籤欄位和準確度計數器。對於在經由PC值編制索引的條目處的標籤命中，若對應的準確度計數器的值大於或等於零，則基於PC值和載入路徑歷史的函數來從預測計數器池中選擇預測計數器，其中預測計數器包括相應的置信度值和預測值。若相關聯的置信度值大於零，則將分支指令的依賴記憶體的分支預測指派為所選擇的預測計數器的預測值，而來自習知分支預測器的分支預測被覆蓋。

Description

基於載入路徑歷史的分支預測
本專利申請案主張於2018年9月19日提出申請的、題為「BRANCH PREDICTION BASED ON LOAD-PATH HISTORY」的非臨時申請案第16/136,151的優先權，該非臨時申請案已經轉讓給本案的受讓人，並且以引用方式將其明確地併入本文。
所揭示的態樣係關於處理系統中的分支預測。更具體而言，示例性態樣係關於在預測難以預測的分支指令（例如依賴記憶體的分支指令）時將載入路徑歷史用作上下文資訊。
處理系統可以使用引起控制流程改變的指令，諸如分支指令。分支指令的方向可以基於例如條件如何評估，但是直到對分支指令的處理已經深入到處理器的指令流水線為止，此種評估可能是未知的。為了避免將流水線拖延到評估已知為止，處理器可以使用分支預測機制來在流水線早期預測分支指令的方向。基於預測，處理器可以推測性地從以下兩個路徑中的一個路徑中的預測位址提取並且執行指令：在分支目標位址處開始的「採用（taken）」路徑，其具有被稱為「採用方向」的對應的方向；或者在條件分支指令之後的下一個連續位址處開始的「未採用」路徑，其具有被稱為「未採用方向」的對應方向。
當對條件進行了評估並且決定了實際分支方向時，若對分支進行了錯誤預測（亦即，執行遵循了錯誤路徑），則可以將推測性提取的指令從流水線中清除（flush），並且可以從正確的下一個位址提取正確路徑中的新的指令。因此，提高分支預測的準確度減輕了與錯誤預測和對錯誤路徑指令的執行相關聯的損失，並且相應地提高了處理系統的效能和能量利用。
因此，可以看到分支預測在高效能流水線的處理器中起著重要的作用。習知的分支預測器可以在進行分支預測時使用上下文資訊。此種上下文資訊可以包括全域及/或本端分支歷史、分支路徑歷史、分支目標歷史等。然而，習知的分支預測器被認為無法準確地預測某些類型的分支指令，包括其方向可能與上述上下文資訊不相關的分支指令。一類此種難以預測的分支指令包括依賴記憶體的分支指令，其中分支指令的方向或結果直接或間接地取決於從記憶體載入的值。
圖1圖示代碼片段，包括與對應的程式指令110共置的偽代碼100，作為難以預測的依賴記憶體的分支指令的實例。偽代碼100的圖示的部分包括用於從記憶體中的資料陣列「A」接收資料值的程式。具體而言，對於出現在偽代碼100中的針對為「i」的值的「for」循環內的偽代碼「if (a[i]>16)」，對應的程式指令可以包括：將來自記憶體中位於位址A[i]的陣列元素的值載入到暫存器R1中，並且隨後基於暫存器中載入的值是否為「R1>16」來評估分支指令「X」。換言之，分支指令「X」的結果取決於儲存在記憶體中位址A[i]處的陣列元素的資料值，並且因此分支指令「X」被稱為依賴記憶體的分支指令。分支指令「X」是使用習知分支預測器難以預測的，因為在與上述上下文資訊（例如全域及/或本端分支歷史、分支路徑歷史、分支目標歷史等）的相關性較弱的情況下，在記憶體中的位址「A[i]」處的資料值不容易預測。
在各種其他指令序列/應用程式中可能會遇到涉及依賴記憶體的分支指令的程式指令。因此，在本領域中需要克服習知分支預測器的局限並且甚至能夠準確地預測上述類型的難以預測的分支指令。
本發明的示例性態樣係關於用於對諸如依賴記憶體的分支指令的難以預測的分支指令的分支預測的系統和方法。
例如，一個示例性態樣係關於一種處理器中的分支預測的方法，方法包括以下步驟：對於由處理器提取以用於執行的分支指令，基於分支指令的程式計數器（PC）值的函數來為分支標識（ID）表編制索引，其中分支ID表包括一或多個條目，其中每個條目至少包括標籤欄位和準確度計數器。對於在經由PC值編制索引的分支ID表的條目處的、在其中條目的標籤欄位與PC值匹配的標籤命中，若準確度計數器的值大於或等於零，則方法包括以下步驟：從包括複數個預測計數器的預測計數器池中選擇預測計數器，其中預測計數器池中的複數個預測計數器之每一者預測計數器至少包括相應的置信度值和預測值，其中選擇是基於PC值和載入路徑歷史的函數的，並且其中載入路徑歷史包括來自由處理器執行的先前載入指令的資訊。方法亦包括以下步驟：若所選擇的預測計數器的置信度值大於零，則將分支指令的依賴記憶體的分支預測指派為所選擇的預測計數器的預測值。
另一個示例性態樣係關於一種裝置，該裝置包括：處理器，其被配置為執行指令，其中處理器至少包括基於載入路徑歷史的分支預測器。基於載入路徑歷史的分支預測器包括：分支標識（ID）表，其包括一或多個條目，其中每個條目至少包括標籤欄位和準確度計數器；及預測計數器池，其包括複數個預測計數器。對於由處理器提取以用於執行的分支指令，分支標識（ID）表是基於分支指令的程式計數器（PC）值的函數來編制索引的。對於在經由PC值編制索引的分支ID表的條目處的、在其中條目的標籤欄位與PC值匹配的標籤命中，若準確度計數器的值大於或等於零，則從預測計數器池中選擇預測計數器，其中預測計數器池中的複數個預測計數器之每一者預測計數器至少包括相應的置信度值和預測值，其中預測計數器是基於PC值和載入路徑歷史的函數來選擇的，其中載入路徑歷史包括來自由處理器執行的先前載入指令的資訊。基於載入路徑歷史的分支預測器被配置為：若所選擇的預測計數器的置信度值大於零，則將分支指令的依賴記憶體的分支預測指派為所選擇的預測計數器的預測值。
另一個示例性態樣係關於一種裝置，該裝置包括：用於執行指令的構件，用於儲存用於預測依賴記憶體的分支指令的一或多個條目的構件，每個條目至少包括用於儲存標籤值的構件和用於儲存針對條目的準確度值的構件，其中對於由用於執行指令的構件提取以用於執行的分支指令，用於儲存條目的構件是基於分支指令的程式計數器（PC）值的函數來編制索引的。裝置亦包括：複數個用於指示預測值和相關聯的置信度值的構件，其中對於在經由PC值編制索引的分支ID表的條目處的、在其中標籤值與PC值匹配的標籤命中，若準確度值大於或等於零，則用於基於PC值和載入路徑歷史的函數來選擇複數個用於指示的構件中的一者的構件，其中載入路徑歷史包括來自由用於執行指令的構件執行的先前載入指令的資訊。裝置亦包括：用於若相關聯的置信度值大於零，則將分支指令的依賴記憶體的分支預測指派為所選擇的用於指示的構件的預測值的構件。
另一個示例性態樣係關於一種包括代碼的非暫時性電腦可讀取儲存媒體，該代碼當由電腦執行時使得電腦在處理器中執行分支預測。非暫時性電腦可讀取儲存媒體包括：對於由處理器提取以用於執行的分支指令，用於基於分支指令的程式計數器（PC）值的函數來為分支標識（ID）表編制索引的代碼，其中分支ID表包括一或多個條目，其中每個條目至少包括標籤欄位和準確度計數器。對於在經由PC值編制索引的分支ID表的條目處的、在其中條目的標籤欄位與PC值匹配的標籤命中，若準確度計數器的值大於或等於零，則提供用於從包括複數個預測計數器的預測計數器池中選擇預測計數器的代碼，其中預測計數器池中的複數個預測計數器之每一者預測計數器至少包括相應的置信度值和預測值，其中用於選擇的代碼是基於PC值和載入路徑歷史的函數的，其中載入路徑歷史包括來自由處理器執行的先前載入指令的資訊。亦包括用於若所選擇的預測計數器的置信度值大於零，則將分支指令的依賴記憶體的分支預測指派為所選擇的預測計數器的預測值的代碼。
在關於本發明的具體態樣的下文的說明和相關附圖中揭示本發明的態樣。可以在不脫離本發明的範疇的前提下設計替代態樣。另外，將不詳細描述或將省略本發明的公知元素，以便不模糊本發明的相關細節。
本文中使用的「示例性的」一詞意指「用作示例、實例或說明」。在本文中被描述為「示例性的」的任何態樣不一定被解釋為較佳的或者比其他態樣更有優勢的。同樣地，術語「本發明的態樣」並不要求本發明的所有態樣包括所論述的特徵、優點或操作模式。
本文中使用的術語僅用於描述本發明的態樣的目的，而不是意在限制該等態樣。如本文中所使用的，單數形式「一（a）」、「一個（an）」和「該（the）」意欲亦包括複數形式，除非上下文另有明確指示。亦將理解的是，當在本文中使用時，術語「包含（comprises）」、「包含有（comprising）」、「包括」（includes）及/或「包括有（including）」指定所陳述的特徵、整體、步驟、操作、元素及/或元件的存在，但並不排除一或多個其他特徵、整體、步驟、操作、元素、元件及/或其群組的存在或添加。
另外，許多態樣是在例如由計算設備的元件執行的動作序列的態樣來描述的。將認識到的是：本文中描述的各個動作可以由特定電路（例如，特殊應用積體電路（ASIC）），被一或多個處理器執行的程式指令或由該二者的組合來執行。另外，可以認為本文中描述的該等動作序列完全體現在具有儲存在其中的電腦指令的相應集合的任意形式的電腦可讀取儲存媒體中，該等電腦指令當被執行之後會使相關聯處理器執行本文中描述的功能。因此，本發明的各個態樣可以體現為大量不同的形式，已經設想所有該等形式皆在主張保護的發明標的的範疇之內。此外，對於本文中描述的態樣之每一者態樣而言，任何此種態樣的相應形式可以在本文中描述為例如「邏輯單元，其被配置為」執行本文中描述的動作。
本案內容的態樣係關於提升與處理諸如依賴記憶體的分支指令的難以預測的分支指令有關的效能。更具體而言，示例性態樣係關於在對依賴記憶體的分支指令的分支預測時將示例性上下文資訊（在本文中被稱為「載入路徑歷史」）用作針對記憶體位址的代理（proxy）。針對載入指令的載入路徑歷史可以包括來自先前載入指令的資訊。可以經由將來自先前載入指令的程式計數器（PC）值之每一者值的最低有效的、非零的N個位元（亦即，位元2至N+1，其中N是正整數）移入示例性載入路徑歷史暫存器中，來構造示例性載入路徑歷史。經由使用載入路徑歷史，而不是記憶體位址，可以在處理器的指令流水線的早期，例如在提取階段，執行對依賴記憶體的分支指令的預測。根據本文的示例性態樣，亦揭示可以使用分支指令的PC、載入路徑歷史或該二者的散列來編制索引（indexed）和打標籤（tagged）的示例性覆蓋分支預測器。
作為背景，在本文中認識到，依賴記憶體的分支指令的分支結果可以與用於饋送該分支指令的一或多個載入指令（例如，用於載入暫存器「R5」的載入指令，其將分支指令「X」饋送到圖1的程式指令110中）的記憶體位址相關。在另一個實例中，在下文的文章中描述了具有用數值1-3枚舉的三個指令的代碼片段，其中在指令1中，載入指令將值從記憶體位址ADDR載入到暫存器R1中；在指令2中，將暫存器R1中的載入的值與值「0」進行比較；及在指令3中，不等分支（BNE）指令分支到由值LABEL設置的方向。分支指令BNE取決於從記憶體位址（ADDR）載入的值，並且因此是依賴記憶體的分支指令。 1、Load R1, MEM[ADDR] 2、CMP R1, 0x0 3、BNE LABEL
在用於預測BNE指令（一種依賴記憶體的分支指令）的已知方法中，取決於記憶體位址ADDR處的資料值，針對分支指令的預測可以基於記憶體位址ADDR。例如，分支預測器可以使用記憶體位址ADDR來為包含預測的預測表編制索引，讀出經索引的預測並且使用該經索引的預測，例如，代替由習知分支預測器提供的依賴於上述習知上下文資訊的預設分支預測。但是，由於記憶體位址ADDR被用於為預測表編制索引，因此使用該方法的分支預測程序僅能在記憶體位址ADDR變得可用之後開始，此舉在指令流水線中可能較晚（例如，在習知指令流水線的後端中的位址產生階段，「AGEN」）。此外，可能依賴於以下複雜的追蹤邏輯：偵測分支指令BNE取決於用於從記憶體位址ADDR載入資料的載入指令的特定例子。該等缺點使已知方法無法在流水線中傳遞足夠早的高效的預測來避免由執行錯誤的路徑指令造成的大量資源浪費。
為了克服上述缺點，在示例性態樣中，如前述，載入路徑歷史被用於預測依賴記憶體的分支指令（例如，BNE），而不是依賴於用於饋送依賴記憶體的分支指令的載入指令從其載入該指令的資料的記憶體位址（例如，ADDR）。
現在參考圖2，圖示將載入路徑歷史用於預測依賴記憶體的分支指令的示例性分支預測器，並且在下文中被稱為基於載入路徑歷史的預測器（LdPHistPred）200。首先將簡要地枚舉基於載入路徑歷史的預測器200的元件，隨後是該等元件的操作和互動的詳細論述。同樣地，在較高層上，基於載入路徑歷史的預測器200包括分支標識（ID）表201和預測計數器池210a-n中的N個預測計數器（其中N是正整數，並且大於或等於1）。
在一種實現方式中，分支ID表201可以是直接映射表，其中分支ID表201中的一或多個條目之每一者條目可以使用分支指令的PC來編制索引，並用利用分支指令的PC來打標籤，如分支ID表201中的標籤欄位202所示。除了標籤欄位202之外，分支ID表201的每個條目亦包括兩個時間戳記，在最後命中時間戳記204和最後預測時間戳記206欄位中圖示。每個條目亦包括帶符號的準確度計數器208，其在使用條目進行的預測正確時遞增，並且在預測不正確時遞減。在一種實現方式中，最後命中時間戳記204、最後預測時間戳記206和準確度計數器208中的每一者可以是N位元寬。
預測計數器池210a-n中的N個預測計數器均可以包括例如具有位元0和位元1的2位元的預測計數器，其中位元0指示置信度，以及位元1表示由相應的2位元的預測計數器得出的預測方向。可以使用諸如分支指令PC的散列的功能來選擇要用於被分支指令PC編制索引的條目的預測計數器池210a-n的特定預測計數器。
另外，可以利用兩個列表來增強基於載入路徑歷史的預測器200，該兩個列表追蹤基於載入路徑歷史的預測器200針對不同分支指令PC的效能。
該兩個列表中的第一個列表被稱為黃金名單，其儲存基於載入路徑歷史的預測器200據說針對其表現非常好的分支指令的PC（此情形將進一步說明）。若帶符號的準確度計數器208的值遠大於0（或「準確度>>0」），則在從分支ID表201中逐出相關聯的條目時，可以將分支指令的PC插入黃金名單中。
該兩個列表中的第二個列表（其被稱為黑名單）儲存基於載入路徑歷史的預測器200據說針對其表現較差的分支指令的PC。若帶符號的準確度計數器208的值遠小於0（或「準確度>>0」），則在從分支ID表201逐出相關聯的條目時，將分支指令插入黑名單中。
現在將參考圖2來描述預測分支指令（例如難以預測的依賴記憶體的分支指令）的方向的過程。對於由處理器提取的分支指令（將在圖3中論述此種處理器的示例性實現方式），可以將分支指令的PC（或其函數或散列）用於為分支ID表201編制索引。如前述，針對載入指令的載入路徑歷史可以包括來自先前載入指令的資訊。可以經由將來自先前載入指令的程式計數器（PC）值之每一者值的最低有效的、非零的N個位元（亦即，位元2至N+1）移入示例性載入路徑歷史暫存器220中，來構造示例性載入路徑歷史。
如前述，分支ID表201包括針對其條目之每一者條目的標籤欄位202，其中若在使用分支指令的PC的散列的經索引的條目處，例如，標籤欄位202與分支指令的PC相匹配，則稱為發生了標籤命中；否則，若存在不匹配，則稱為發生了標籤未命中。在圖2中，條目201x被代表性地示為經索引的條目，以促進下文的論述。
在針對條目201x的標籤命中的情況下，利用發生標籤命中的時間（例如，從時鐘匯出，未圖示）來更新最後命中時間戳記204。此外，查詢（consult）針對條目201x的準確度計數器208，並且若該準確度計數器208的值>=0，則讀出預測計數器池210a-n的對應預測計數器。可以使用分支指令的PC和載入路徑歷史記暫存器220的當前值的散列來選擇針對條目201x的對應預測計數器。
若在所選擇的預測計數器處的預測計數器的值是置信的（例如，設置了用於所選擇的預測計數器的置信度位元），則將從預測計數器獲得的值用於預測分支指令。就該點而言，可以覆蓋可能存在於用於習知分支預測的處理器中的預設分支預測器，並且替代地可以使用從查詢基於載入路徑歷史的預測器200的上述程序獲得的預測。在獲得了預測之後，分支ID表201中針對條目201x的最後預測時間戳記206亦利用獲得預測的時間來更新。
另一態樣，若在條目201x處存在標籤未命中，則不將基於載入路徑歷史的預測器200用於預測分支指令；可以使用預設的分支預測器。
經由以上文論述的方式使用載入路徑歷史、將從記憶體位址中載入資料值的載入指令、依賴記憶體的分支指令評估的資料值，有可能準確地預測依賴記憶體的分支指令的方向，例如，在針對依賴記憶體的分支指令在分支ID表201中存在標籤命中的情況下。下一部分論述如何訓練基於載入路徑歷史的預測器200以便為依賴記憶體的分支指令提供此種準確的預測。
在示例性態樣中，若預設分支預測器預測錯誤，或者若基於載入路徑歷史的預測器200在預測時間接收到標籤命中，則可以啟動對基於載入路徑歷史的預測器200的訓練。因此，存在兩種用於訓練基於載入路徑歷史的預測器200的場景：在分支ID表201的標籤命中的情況下或標籤未命中的情況下，此舉將在下文依次論述。
在第一訓練程序中，在分支ID表201的標籤命中的情況下，若使用基於載入路徑歷史的預測器200進行的預測（例如，從預測計數器池210a-n中的N個預測計數器中的相應一個預測計數器獲得的）是正確的（亦即，若分支指令的評估結果/方向與使用基於載入路徑歷史的預測器200進行的預測相匹配），則可以使準確度計數器208經由遞增來進行更新；否則，在錯誤預測之後，可以使準確度計數器208遞減。
預測計數器池210a-n的適當選擇的預測計數器（例如，使用分支指令的PC和載入路徑歷史的散列來選擇的）可以如下更新。若所選擇的預測計數器的預測位元（例如，其中為「1」的值指示已採用以及為「0」的值指示未採用）與分支指令的評估結果/方向匹配，則將預測計數器中的置信度位元設置為置信值（例如，設置為值「1」）；否則，若所選擇的預測計數器的預測位元與分支指令的評估結果/方向不匹配，則將置信度位元重置為非置信值（例如，重置為值「0」），並且將預測位元設置為匹配分支指令的結果。
在第二訓練程序中，在分支ID表201中的標籤未命中之後，嘗試在分支ID表201中分配條目（注意，將在以下部分中進一步詳細論述對分支ID表201中的條目的分配和替換）。若分配嘗試成功，則可以經由將對應的標籤欄位202設置為分支指令的PC，並且如前述使用相應的時間戳記適當地更新最後命中204以及最後預測時間戳記206，來更新分支ID表201的所分配的條目。準確度計數器208可以被設置為「0」，並且預測計數器池210a-n的對應預測計數器可以以與上述針對分支ID表201中的標籤命中的描述一致的方式來設置。
現在將進一步詳細論述分支ID表201的分配和替換條目。若滿足以下條件中的一個條件，則可以在某個時間點處（本端時鐘圖示的當前時間）分配分支ID表201中的條目，其中X是可選的大數量，例如，16K。 1、條件1：被分支指令的PC編制索引的分支ID表201的條目顯示低活動性，例如，如經由最後命中時間戳記204（或hitTime）+X小於當前時間（或「hitTime+1*X>currentTime」）所定義的。 2、條件2：經索引的條目顯示低獎勵，例如，如經由最後預測時間戳記206（或predTime）+8*X小於當前時間（或「predTime+8*X＜currentTime」）所定義的。 3、條件3：經索引條目顯示差的準確度，例如，如經由準確度計數器208的值小於零（或「準確度>0」）所定義的；或者 4、條件4：嘗試針對其來分配的分支指令在先前定義的黃金名單上。
應該在本文中注意的是：若分支指令在黑名單上，則不針對分支ID表201中的分支指令執行分配。上述試探法（heuristic）或條件提供了針對以下情況的保護：其中例如，指令覆蓋區（footprint）過大（因此，滿足條件1，其中特定分支指令的PC可能在指令序列中顯示低活動性），儲存在記憶體位置中的資料值正在改變（此情形意味著使用載入路徑歷史來預測資料值可能不準確），或者不再需要被分配的條目。
現在參考圖3，圖示在其中可以採用本案內容的態樣的示例性處理系統300。圖示處理系統300包括耦合到指令快取記憶體308的處理器310。儘管未在該視圖中圖示，但是亦可以存在諸如功能單元、輸入/輸出單元、介面結構、記憶體結構等的額外元件，但是由於該等額外元件與本案內容可能不密切相關，因此未對其進行明確標識或描述。如圖所示，處理器310可以被配置為：從指令快取記憶體308接收指令並且使用例如執行流水線312來執行指令。執行流水線312可以被配置為包括一或多個流水線級，用於執行指令提取（IF）、指令解碼（ID）、一或多個執行級（EX1，EX2，……）和回寫（WB）操作，如本領域中已知的。代表性地，在指令快取記憶體308中圖示分支指令並且將其標識為分支指令302。
在示例性實現方式中，分支指令302可以具有對應位址或為302pc的程式計數器（PC）值。處理器310通常被示為包括預設的習知分支預測器306，如本領域中已知的，其亦可以包括分支預測單元（例如包括先前分支指令的行為歷史的歷史表）、狀態機（例如分支預測計數器）等。換言之，分支預測器306可以使用上文論述的習知上下文資訊來預測分支指令，該等分支指令不是難以預測的分支指令。當處理器310提取分支指令302以供執行時，對於習知分支指令，諸如散列305的邏輯單元（例如，實現XOR功能）可以利用位址或PC值302pc及/或來自分支指令302的其他資訊，來存取分支預測器306和取得預測307，該預測307表示分支指令302的預設預測。
在示例性態樣，處理器310亦包括基於載入路徑歷史的預測器200，上文已經參考圖2描述了其示例性實現方式。如參考圖2所論述的，可以使用分支指令302的PC值302pc和來自載入路徑歷史暫存器220的載入路徑歷史的散列（例如，從諸如散列304的邏輯單元獲得的）來為基於載入路徑歷史的預測器200的分支ID表201編制索引。使用上述程序獲得的、基於載入路徑歷史的預測器200的輸出被示為依賴記憶體的分支預測322，但是通常可以表示分支預測器306針對其被覆蓋的任何難以預測的分支指令的分支預測。例如，若將基於載入路徑歷史的預測器200用於預測分支指令，則依賴記憶體的分支預測322可以代替由分支預測器306提供的預測307，來用作針對分支指令302的預測。可以理解，由於可以基於載入路徑歷史暫存器220和分支指令PC 302pc來獲得依賴記憶體的分支預測322，因此依賴記憶體的分支預測322可以在執行流水線312中非常早地（例如在指令提取IF階段）可以用。
繼續圖3的描述，可以在執行流水線312中推測地執行分支指令302（基於根據預測307或依賴記憶體的分支預測322推導出的方向）。在遍歷一或多個流水線狀態後，將知曉對分支指令302的實際評估，並且將此舉示為評估313。在預測檢查區塊314中，將評估313與針對其推測地執行分支指令302的預測（亦即，根據情況，可能是預測307或依賴記憶體的分支預測322）進行比較，以決定評估313是否與推測地執行的方向相匹配，或者換言之，是正確預測還是錯誤預測了分支指令302。在示例性實現方式中，匯流排315包括資訊，該資訊包括正確的評估313（被採用/不被採用）以及分支指令302是被正確地預測還是被錯誤地預測。可以將匯流排315上的資訊提供給基於載入路徑歷史的預測器200和預設分支預測器306。例如，在分支ID表201的上述訓練程序期間更新準確度計數器208可以使用匯流排315上的資訊來決定分支指令的評估結果/方向（亦即，正確評估313）是否與使用基於載入路徑歷史的預測器200做出的預測（亦即，依賴記憶體的分支預測322）相匹配。因此，可以以與參考圖2對基於載入路徑歷史的預測器200的描述一致的方式將基於載入路徑歷史的預測器200併入處理系統300。
因此，將明白的是：示例性態樣包括用於執行在本文中揭示的程序、功能及/或演算法的各種方法。例如，圖4（下文結合參考圖2-圖3）圖示處理器（例如，處理器310）中的分支預測的方法400。
在方塊402中，對於由處理器提取以用於執行的分支指令（例如，分支指令302），基於分支指令的程式計數器（PC）值（例如，302pc）的函數來為分支標識（ID）表（例如，分支ID表201）編制索引，其中分支ID表包括一或多個條目，其中每個條目（例如，條目201x）至少包括標籤欄位（例如，標籤欄位202）和準確度計數器（例如，準確度計數器208）。
在方塊404中，對於其中在分支ID表的與索引相對應的條目（例如，條目201x）處的標籤欄位與PC值相匹配的標籤命中，並且若準確度計數器的值大於或等於零，從包括複數個預測計數器的預測計數器池（例如，預測計數器池210a-n）中選擇預測計數器，其中預測計數器池中的複數個預測計數器之每一者預測計數器至少包括相應的置信度值（例如，位元0）和預測值（例如，位元1），其中該選擇基於PC值和（例如，來自載入路徑歷史暫存器220的）載入路徑歷史的函數，其中載入路徑歷史包括來自由處理器執行的先前載入指令的資訊。
方塊406包括：若所選擇的預測計數器的置信度值大於零，則將分支指令的依賴記憶體的分支預測（例如，預測322）指派為所選擇的預測計數器的預測值。
現在將結合圖5論述在其中可以使用本案內容的示例性態樣的示例性裝置。圖5圖示計算設備500的方塊圖。計算設備500可以與圖3的處理系統300的示例性實現方式相對應，其中處理器310可以包括圖2的基於載入路徑歷史的預測器200，圖示為在此視圖中的具有分支ID表201、預測計數器池210a-n和載入路徑歷史暫存器220，而為了清楚起見，已經省略了參照圖2-圖3圖示和描述的其他細節。亦圖示與處理器310通訊的記憶體510。
圖5亦圖示耦合到處理器310和顯示器528的顯示控制器526。在一些情況下，計算設備500可以用於無線通訊，並且圖5亦用虛線圖示可選方塊，諸如耦合到處理器310的編碼器/解碼器（CODEC）534（例如，音訊及/或語音CODEC），並且揚聲器536和麥克風538可以耦合到CODEC 534；及耦合到無線控制器540的無線天線542，該無線控制器540耦合到處理器310。在存在該等可選方塊中的一或多個可選方塊的情況下，在特定態樣中，處理器310、顯示器控制器526、記憶體510和無線控制器540包括在系統級封裝或晶片上系統設備522中。
因此，在特定態樣中，輸入設備530和電源544耦合到晶片上系統設備522。此外，在特定態樣中，如圖5所示，在存在一或多個可選方塊的情況下，顯示器528、輸入設備530、揚聲器536、麥克風538、無線天線542和電源544在晶片上系統設備522外部。然而，顯示器528、輸入設備530、揚聲器536、麥克風538、無線天線542以及電源544中的每一者可以耦合到晶片上系統設備522的元件（諸如介面或控制器）。
應該指出的是：儘管圖5概括地圖示了計算設備，但處理器310和記憶體510亦可以整合到機上盒、伺服器、音樂播放機、視訊播放機、娛樂單元、導航設備、個人數位助理（PDA）、固定位置資料單元、電腦、膝上型電腦、平板電腦、通訊設備、行動電話或其他類似設備。
另外，亦將理解的是：本案內容的態樣亦可以包括：包括下列各項的裝置（例如，處理系統300）：用於執行指令的構件（例如，處理器310），用於儲存用於預測依賴記憶體的分支指令的一或多個條目的構件（例如，分支ID表201），每個條目至少包括：用於儲存標籤值的構件（例如，標籤欄位），以及用於儲存針對條目的準確度值的構件（例如，準確度計數器208），其中對於由用於執行指令的構件提取以用於執行的分支指令，基於分支指令的程式計數器（PC）值（例如，分支指令302的PC值302pc）的函數來對用於儲存條目的構件編制索引。該裝置亦可以包括複數個用於指示的構件（例如，預測計數器池210a-n）預測值（例如，位元0）和相關聯的置信度值（例如，位元1）；其中對於在經由PC值編制索引的分支ID表的條目處的、在其中條目的標籤值與PC值匹配的標籤命中，若準確度值大於或等於零，用於基於PC值和（例如，來自載入路徑歷史暫存器220的）載入路徑歷史的函數（例如，散列304），選擇複數個用於指示的構件中的一者的構件，其中載入路徑歷史包括來自由用於執行的構件執行的先前載入指令的資訊。該裝置亦包括：用於若相關聯的置信度值大於零，則將分支指令的依賴記憶體的分支預測（例如，基於載入路徑歷史的預測器200）指派為所選擇的用於指示的構件的預測值的構件。
熟習此項技術者將明白的是，可以使用各種不同的技術和方法中的任意技術和方法來表示資訊和信號。例如，在貫穿上文的描述中提及的資料、指令、命令、資訊、信號、位元、符號和碼片可以由電壓、電流、電磁波、磁場或磁性粒子、光場或光粒子，或者其任意組合來表示。
此外，熟習此項技術者將明白的是，結合本文中揭示的各個態樣所描述的各個說明性的邏輯區塊、模組、電路和演算法步驟均可以實現成電子硬體、電腦軟體或其組合。為了清楚地說明硬體和軟體之間的該可交換性，上文已經對各個說明性的元件、方塊、模組、電路和步驟圍繞其功能進行了整體描述。至於此種功能是實現為硬體還是實現為軟體，依賴特定的應用和對整體系統所施加的設計約束。熟習此項技術者可以針對每個特定應用，以變通的方式實現所描述的功能，但是此種實現方式決策不應解釋為造成對本發明的範疇的背離。
結合本文中揭示的各個態樣所描述的方法、順序及/或演算法可以直接實現在硬體中、由處理器執行的軟體模組中或者該二者的組合中。軟體模組可以位於RAM記憶體、快閃記憶體、ROM記憶體、EPROM記憶體、EEPROM記憶體、暫存器、硬碟、抽取式磁碟、CD-ROM，或者本領已知的任何其他形式的儲存媒體中。示例性的儲存媒體耦合到處理器，使處理器能夠從該儲存媒體讀取資訊以及向該儲存媒體寫入資訊。在替代方式中，儲存媒體可以整合到處理器。
因此，本發明的態樣可以包括體現用於預測依賴記憶體的分支指令的方法的電腦可讀取媒體。因此，本發明不局限於圖示實例，並且用於執行本文中描述的功能的任何構件包括在本發明的態樣中。
儘管前面的揭示內容圖示本發明的說明性態樣，但應當指出的是，在不脫離由所附的請求項所定義的本發明的範疇的情況下，在本文中可以進行各種變化和修改。根據本文中描述的本發明的態樣的方法請求項的功能、步驟及/或動作不需要以任何特定的順序來執行。此外，儘管可以以單數形式描述或主張本發明的元素，但除非明確聲明限於單數形式，否則複數亦是預期的。
100:偽代碼 110:程式指令 200:基於載入路徑歷史的預測器 201:分支標識（ID）表 201x:條目 202:標籤欄位 204:最後命中時間戳記 206:最後預測時間戳記 208:準確度計數器 210a:預測計數器池 210a-n:預測計數器池 210n:預測計數器池 220:載入路徑歷史暫存器 300:處理系統 302:分支指令 302pc:PC值 304:散列 305:散列 306:分支預測器 307:預測 308:指令快取記憶體 310:處理器 312:執行流水線 313:評估 314:預測檢查區塊 315:匯流排 322:依賴記憶體的分支預測 400:方法 402:方塊 404:方塊 406:方塊 500:計算設備 510:記憶體 522:晶片上系統設備 526:顯示控制器 528:顯示器 530:輸入設備 534:CODEC 536:揚聲器 538:麥克風 540:無線控制器 542:無線天線 544:電源
提供附圖以幫助描述本發明的各個態樣，並且提供附圖僅為了說明而不是限制各個態樣。
圖1圖示說明依賴記憶體的分支指令的示例性指令序列。
圖2根據本案內容的態樣圖示基於載入路徑歷史的分支預測器。
圖3根據本案內容的態樣圖示併入示例性的基於載入路徑歷史的分支預測器的處理系統。
圖4根據本案內容的態樣圖示使用示例性的基於載入路徑歷史的分支預測器的分支預測的方法。
圖5圖示了在其中可以有優勢地使用本案內容的態樣的示例性計算設備。
國內寄存資訊 (請依寄存機構、日期、號碼順序註記) 無
國外寄存資訊 (請依寄存國家、機構、日期、號碼順序註記) 無
200:基於載入路徑歷史的預測器
220:載入路徑歷史暫存器
300:處理系統
302:分支指令
302pc:PC值
304:散列
305:散列
306:分支預測器
307:預測
308:指令快取記憶體
310:處理器
312:執行流水線
313:評估
314:預測檢查區塊
315:匯流排
322:依賴記憶體的分支預測

Claims (33)

  1. 一種一處理器中的分支預測的方法，該方法包括以下步驟：對於由該處理器提取以用於執行的一分支指令，基於該分支指令的一程式計數器(PC)值的一函數來為一分支標識(ID)表編制索引，其中該分支ID表包括一或多個條目，其中每個條目至少包括一標籤欄位和一準確度計數器；對於在經由該PC值編制索引的該分支ID表的一條目處的、在其中該條目的該標籤欄位與該PC值匹配的一標籤命中，若該準確度計數器的一值大於或等於零，則從包括複數個預測計數器的一預測計數器池中選擇一預測計數器，其中該預測計數器池中的該複數個預測計數器之每一者預測計數器至少包括一相應的置信度值和一預測值，其中該選擇是基於該PC值和一載入路徑歷史的一函數的，其中該載入路徑歷史包括來自由該處理器執行的先前載入指令的資訊；及若所選擇的該預測計數器的該置信度值大於零，則將該分支指令的一依賴記憶體的分支預測指派為所選 擇的該預測計數器的該預測值。
  2. 根據請求項1之方法，亦包括以下步驟：基於該依賴記憶體的分支預測來推測地執行該分支指令。
  3. 根據請求項2之方法，包括以下步驟：覆蓋來自該處理器的一分支預測器的一分支預測，該分支預測器基於包括以下各項中的一項或多項的上下文資訊來提供分支預測：一全域分支歷史、一本端分支歷史、分支路徑歷史或一分支目標歷史。
  4. 根據請求項1之方法，其中該分支指令是一依賴記憶體的分支指令，該依賴記憶體的分支指令的方向是取決於由一先前載入指令從一記憶體位址載入的一值的。
  5. 根據請求項1之方法，包括以下步驟：從一載入路徑暫存器決定該載入路徑歷史，該載入路徑暫存器經由移入先前載入指令的PC值的一或多個最低有效位元來形成。
  6. 根據請求項1之方法，其中該預測計數器池中的該複數個預測計數器之每一者預測計數器是2位元的計數器，其中一第一位元包括該置信度值，以及一第二位元包括該預測值。
  7. 根據請求項1之方法，其中該分支ID表的每 個條目亦包括一最後命中時間戳記和一最後預測時間戳記，並且其中對於該標籤命中，利用發生該標籤命中的一時間來更新該最後命中時間戳記。
  8. 根據請求項7之方法，其中在獲得所選擇的該預測計數器的該預測值以用於將該分支指令的該依賴記憶體的分支預測指派為所選擇的該預測計數器的該預測值之後，利用獲得所選擇的該預測計數器的該預測值的一時間來更新該最後預測時間戳記。
  9. 根據請求項8之方法，亦包括以下步驟：對於該標籤命中，若該分支指令的該依賴記憶體的分支預測與該分支指令的一隨後評估的正確方向匹配，則將該準確度計數器遞增，以及將所選擇的該預測計數器的該置信度值設置為一置信值。
  10. 根據請求項9之方法，亦包括以下步驟：對於該標籤命中，若該分支指令的該依賴記憶體的分支預測與該分支指令的一隨後評估的正確方向不匹配，則將該準確度計數器遞減，將所選擇的該預測計數器的該置信度值重置為一非置信值，以及將所選擇的該預測計數器的該預測值更新為匹配該正確方向。
  11. 根據請求項8之方法，其中對於在其中在該分支ID表的與該索引相對應的該條目處的該標籤欄位與該分支指令的該PC值不匹配的一標籤未命中， 基於從該處理器的一分支預測器獲得的一分支預測來預測該分支指令，該分支預測器基於包括以下各項中的一項或多項的上下文資訊來提供分支預測：一全域分支歷史、一本端分支歷史、分支路徑歷史或一分支目標歷史。
  12. 根據請求項11之方法，亦包括以下步驟：基於用於決定該分支ID表中的分配的一或多個試探法來為該分支指令分配該分支ID表的相同或一不同條目。
  13. 根據請求項12之方法，其中該一或多個試探法是基於以下各項中的一項或多項的：該處理器正在執行的指令的一覆蓋區大小，作為一依賴記憶體的分支指令的該分支指令取決於的一資料值，或者該分支ID表中的條目的當前使用。
  14. 根據請求項13之方法，其中至少一黃金名單和一黑名單是與該分支ID表相關聯的，其中其依賴記憶體的分支預測具有高效能的分支指令的PC被插入到該黃金名單中，以及其依賴記憶體的分支預測具有低效能的分支指令的PC在從該分支ID表中逐出之後被插入到該黑名單中。
  15. 根據請求項14之方法，其中該一或多個試探法是根據以下各項中的一項或多項來決定的：該最 後命中時間戳記、該最後預測時間戳記、該準確度計數器值以及該PC值在該黑名單或該黃金名單中的存在性。
  16. 一種用於分支預測的裝置，其包括：一處理器，其被配置為執行指令，其中該處理器至少包括一基於載入路徑歷史的分支預測器，其中該基於載入路徑歷史的分支預測器包括：一分支標識(ID)表，其包括一或多個條目，其中每個條目至少包括一標籤欄位和一準確度計數器；及一預測計數器池，其包括複數個預測計數器；其中對於由該處理器提取以用於執行的一分支指令，該分支標識(ID)表是基於該分支指令的一程式計數器(PC)值的一函數來編制索引的；對於在經由該PC值編制索引的該分支ID表的一條目處的、在其中該條目的該標籤欄位與該PC值匹配的一標籤命中，若該準確度計數器的一值大於或等於零，則從該預測計數器池中選擇一預測計數器，其中該預測計數器池中的該複數個預測計數器之每一者預測計數器至少包括一相應的置信度值和一預測值，其中該預測計數器是基於該PC值和一載入路徑 歷史的一函數來選擇的，其中該載入路徑歷史包括來自由該處理器執行的先前載入指令的資訊；及該基於載入路徑歷史的分支預測器被配置為：若所選擇的該預測計數器的該置信度值大於零，則將該分支指令的一依賴記憶體的分支預測指派為所選擇的該預測計數器的該預測值。
  17. 根據請求項16之裝置，其中該處理器被配置為：基於該依賴記憶體的分支預測來推測地執行該分支指令。
  18. 根據請求項17之裝置，其中該處理器亦包括一分支預測器，該分支預測器被配置為：基於包括以下各項中的一項或多項的上下文資訊來提供分支預測：一全域分支歷史、一本端分支歷史、分支路徑歷史或一分支目標歷史，並且其中該處理器被配置為：覆蓋來自該分支預測器的一分支預測，以基於該依賴記憶體的分支預測來推測地執行該分支指令。
  19. 根據請求項16之裝置，其中該分支指令是一依賴記憶體的分支指令，該依賴記憶體的分支指令的方向是取決於由一先前載入指令從一記憶體位址載入的一值的。
  20. 根據請求項16之裝置，其中該基於載入路徑歷史的分支預測器亦包括：一載入路徑暫存器，該載入路徑暫存器包括先前載入指令的PC值的一或多個最低有效位元，其中該載入路徑暫存器被配置為提供該載入路徑歷史。
  21. 根據請求項16之裝置，其中該預測計數器池中的該複數個預測計數器之每一者預測計數器是2位元的計數器，其中一第一位元包括該置信度值，以及一第二位元包括該預測值。
  22. 根據請求項16之裝置，其中該分支ID表的每個條目亦包括一最後命中時間戳記和一最後預測時間戳記，並且其中對於該標籤命中，該最後命中時間戳記是利用發生該標籤命中的一時間來更新的。
  23. 根據請求項22之裝置，其中該最後預測時間戳記是利用所選擇的該預測計數器的該預測值被獲取以被指派為該分支指令的該依賴記憶體的分支預測的一時間來更新的。
  24. 根據請求項22之裝置，其中對於該標籤命中，若該分支指令的該依賴記憶體的分支預測與該分支指令的一隨後評估的正確方向匹配，則將該準確度計數器遞增，以及將所選擇的該預測計數器的該置信度值設置為一置信值。
  25. 根據請求項24之裝置，其中對於該標籤命中，若該分支指令的該依賴記憶體的分支預測與該分支指令的一隨後評估的正確方向不匹配，則將該準確度計數器遞減，將所選擇的該預測計數器的該置信度值重置為一非置信值，以及將所選擇的該預測計數器的該預測值更新為匹配該正確方向。
  26. 根據請求項22之裝置，其中該處理器亦包括一分支預測器，該分支預測器被配置為：基於包括以下各項中的一項或多項的上下文資訊來提供分支預測：一全域分支歷史、一本端分支歷史、分支路徑歷史或一分支目標歷史，其中對於在其中在該分支ID表的與該索引相對應的該條目處的該標籤欄位與該分支指令的該PC值不匹配的一標籤未命中，該處理器被配置為：基於從該分支預測器獲得的一分支預測來預測該分支指令。
  27. 根據請求項26之裝置，其中該分支ID表的相同或一不同條目是基於用於決定該分支ID表中的分配的一或多個試探法來為該分支指令分配的。
  28. 根據請求項27之裝置，其中該一或多個試探法是基於以下各項中的一項或多項的：該處理器正在執行的指令的一覆蓋區大小，作為一依賴記憶體的分支指令的該分支指令取決於的一資料值，或者該分 支ID表中的條目的當前使用。
  29. 根據請求項28之裝置，其中該基於載入路徑歷史的分支預測器亦至少包括與該分支ID表相關聯的一黃金名單和一黑名單，其中其依賴記憶體的分支預測具有高效能的分支指令的PC被插入到該黃金名單中，以及其依賴記憶體的分支預測具有低效能的分支指令的PC在從該分支ID表中逐出之後被插入到該黑名單中。
  30. 根據請求項29之裝置，其中該一或多個試探法是根據以下各項中的一項或多項來決定的：該最後命中時間戳記、該最後預測時間戳記、該準確度計數器值以及該PC值在該黑名單或該黃金名單中的存在性。
  31. 根據請求項16之裝置，其被整合到從由下列各項組成的群組中選擇的一設備中：一機上盒、一伺服器、一音樂播放機、一視訊播放機、一娛樂單元、一導航設備、一個人數位助理(PDA)、一固定位置資料單元、一電腦、一膝上型電腦、一平板電腦、一通訊設備以及一行動電話。
  32. 一種用於分支預測的裝置，其包括：用於執行指令的構件；用於儲存用於預測依賴記憶體的分支指令的一或多 個條目的構件，每個條目至少包括用於儲存一標籤值的構件和用於儲存針對該條目的一準確度值的構件，其中對於由該用於執行指令的構件提取以用於執行的一分支指令，用於儲存該一或多個條目的該構件是基於該分支指令的一程式計數器(PC)值的一函數來編制索引的；複數個用於指示預測值和相關聯的置信度值的構件；其中對於在經由該PC值編制索引的該分支ID表的一條目處的、在其中該標籤值與該PC值匹配的一標籤命中，若該準確度值大於或等於零，則用於基於該PC值和一載入路徑歷史的一函數來選擇複數個用於指示的該構件中的一者的構件，其中該載入路徑歷史包括來自由該用於執行指令的構件執行的先前載入指令的資訊；及用於若該相關聯的置信度值大於零，則將該分支指令的一依賴記憶體的分支預測指派為所選擇的該用於指示的構件的該預測值的構件。
  33. 一種包括代碼的非暫時性電腦可讀取儲存媒體，該代碼當由一電腦執行時使得該電腦在一處理器中執行分支預測，該非暫時性電腦可讀取儲存媒體包括： 對於由該處理器提取以用於執行的一分支指令，用於基於該分支指令的一程式計數器(PC)值的一函數來為一分支標識(ID)表編制索引的代碼，其中該分支ID表包括一或多個條目，其中每個條目至少包括一標籤欄位和一準確度計數器；對於在經由該PC值編制索引的該分支ID表的一條目處的、在其中該條目的該標籤欄位與該PC值匹配的一標籤命中，若該準確度計數器的一值大於或等於零，則用於從包括複數個預測計數器的一預測計數器池中選擇一預測計數器的代碼，其中該預測計數器池中的該複數個預測計數器之每一者預測計數器至少包括一相應的置信度值和一預測值，其中用於選擇的該代碼是基於該PC值和一載入路徑歷史的一函數的，其中該載入路徑歷史包括來自由該處理器執行的先前載入指令的資訊；及用於若所選擇的該預測計數器的該置信度值大於零，則將該分支指令的一依賴記憶體的分支預測指派為所選擇的該預測計數器的該預測值的代碼。
TW108133781A 2018-09-19 2019-09-19 基於載入路徑歷史的分支預測 TWI739159B (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US16/136,151 2018-09-19
US16/136,151 US10838731B2 (en) 2018-09-19 2018-09-19 Branch prediction based on load-path history

Publications (2)

Publication Number Publication Date
TW202036284A TW202036284A (zh) 2020-10-01
TWI739159B true TWI739159B (zh) 2021-09-11

Family

ID=68104789

Family Applications (1)

Application Number Title Priority Date Filing Date
TW108133781A TWI739159B (zh) 2018-09-19 2019-09-19 基於載入路徑歷史的分支預測

Country Status (5)

Country Link
US (1) US10838731B2 (zh)
EP (1) EP3853718B1 (zh)
CN (1) CN112740175B (zh)
TW (1) TWI739159B (zh)
WO (1) WO2020061220A1 (zh)

Families Citing this family (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20220091852A1 (en) * 2020-09-22 2022-03-24 Intel Corporation Instruction Set Architecture and Microarchitecture for Early Pipeline Re-steering Using Load Address Prediction to Mitigate Branch Misprediction Penalties
US11928472B2 (en) 2020-09-26 2024-03-12 Intel Corporation Branch prefetch mechanisms for mitigating frontend branch resteers
US12182317B2 (en) 2021-02-13 2024-12-31 Intel Corporation Region-based deterministic memory safety
US12504891B2 (en) 2021-06-24 2025-12-23 Intel Corporation Zero-redundancy tag storage for bucketed allocators
US12235791B2 (en) 2021-08-23 2025-02-25 Intel Corporation Loop driven region based frontend translation control for performant and secure data-space guided micro-sequencing
CN114816534B (zh) * 2022-04-29 2025-09-26 深圳大学 一种分支指令的分支预测方法及相关装置
CN115686639B (zh) * 2022-10-21 2025-08-29 中国科学院计算技术研究所 一种应用于处理器的分支预测方法以及分支预测器
US12164523B2 (en) * 2022-11-22 2024-12-10 Sap Se Media attribute inference service in data warehouse system
CN115934169A (zh) * 2022-12-01 2023-04-07 杭州嘉楠耘智信息科技有限公司 一种程序自适应的tage预测器及预测方法
CN119127311A (zh) * 2023-12-15 2024-12-13 腾讯科技（深圳）有限公司 指令获取方法、中央处理器、设备、介质和程序产品
CN117632262B (zh) * 2023-12-29 2025-03-21 飞腾信息技术有限公司 分支预测方法及系统、分支预测器、处理器和存储介质
US12405800B2 (en) * 2024-01-31 2025-09-02 Arm Limited Branch prediction based on a predicted confidence that a corresponding function of sampled register state correlates to a later branch instruction outcome
US12468536B1 (en) * 2024-07-02 2025-11-11 Arm Limited Branch prediction
CN119473400B (zh) * 2024-10-25 2025-11-28 海光信息技术股份有限公司 分支预测方法、分支预测器及相关设备
CN120010927B (zh) * 2025-04-22 2025-07-18 山东云海国创云计算装备产业创新中心有限公司 分支指令预测器中的新表项分配方法、装置、设备及介质

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20060095750A1 (en) * 2004-08-30 2006-05-04 Nye Jeffrey L Processes, circuits, devices, and systems for branch prediction and other processor improvements
US20150046690A1 (en) * 2013-08-08 2015-02-12 International Business Machines Corporation Techinques for selecting a predicted indirect branch address from global and local caches
TW201702888A (zh) * 2015-02-03 2017-01-16 英特爾股份有限公司 用於虛擬化之細粒度位址重新映射
US20170286119A1 (en) * 2016-03-31 2017-10-05 Qualcomm Incorporated Providing load address predictions using address prediction tables based on load path history in processor-based systems

Family Cites Families (20)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5758142A (en) 1994-05-31 1998-05-26 Digital Equipment Corporation Trainable apparatus for predicting instruction outcomes in pipelined processors
US6438673B1 (en) 1999-12-30 2002-08-20 Intel Corporation Correlated address prediction
US6721875B1 (en) * 2000-02-22 2004-04-13 Hewlett-Packard Development Company, L.P. Method and apparatus for implementing a single-syllable IP-relative branch instruction and a long IP-relative branch instruction in a processor which fetches instructions in bundle form
US6779108B2 (en) 2000-12-15 2004-08-17 Intel Corporation Incorporating trigger loads in branch histories for branch prediction
US20060248319A1 (en) * 2002-02-05 2006-11-02 Sun Microsystems, Inc. Validating branch resolution to avoid mis-steering instruction fetch
US7890738B2 (en) * 2005-01-20 2011-02-15 International Business Machines Corporation Method and logical apparatus for managing processing system resource use for speculative execution
US7434037B2 (en) * 2006-04-07 2008-10-07 International Business Machines Corporation System for target branch prediction using correlation of local target histories including update inhibition for inefficient entries
US8301871B2 (en) * 2006-06-08 2012-10-30 International Business Machines Corporation Predicated issue for conditional branch instructions
US7788473B1 (en) * 2006-12-26 2010-08-31 Oracle America, Inc. Prediction of data values read from memory by a microprocessor using the storage destination of a load operation
US7707398B2 (en) * 2007-11-13 2010-04-27 Applied Micro Circuits Corporation System and method for speculative global history prediction updating
US20110093658A1 (en) * 2009-10-19 2011-04-21 Zuraski Jr Gerald D Classifying and segregating branch targets
US9389860B2 (en) * 2012-04-02 2016-07-12 Apple Inc. Prediction optimizations for Macroscalar vector partitioning loops
US9477478B2 (en) 2012-05-16 2016-10-25 Qualcomm Incorporated Multi level indirect predictor using confidence counter and program counter address filter scheme
US9311100B2 (en) 2013-01-07 2016-04-12 Apple Inc. Usefulness indication for indirect branch prediction training
GB2506462B (en) * 2013-03-13 2014-08-13 Imagination Tech Ltd Indirect branch prediction
WO2015061648A1 (en) * 2013-10-25 2015-04-30 Advanced Micro Devices, Inc. Bandwidth increase in branch prediction unit and level 1 instruction cache
US10001998B2 (en) * 2014-04-18 2018-06-19 Oracle International Corporation Dynamically enabled branch prediction
US10664280B2 (en) 2015-11-09 2020-05-26 MIPS Tech, LLC Fetch ahead branch target buffer
US11113066B2 (en) * 2018-01-09 2021-09-07 International Business Machines Corporation Predicting a branch instruction classified as simple or hard to predict based on a confidence counter in a branch type table
US10776119B2 (en) * 2018-06-15 2020-09-15 Marvell Asia Pte, Ltd. Combined conditional branch and indirect branch target predictor

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20060095750A1 (en) * 2004-08-30 2006-05-04 Nye Jeffrey L Processes, circuits, devices, and systems for branch prediction and other processor improvements
US20150046690A1 (en) * 2013-08-08 2015-02-12 International Business Machines Corporation Techinques for selecting a predicted indirect branch address from global and local caches
TW201702888A (zh) * 2015-02-03 2017-01-16 英特爾股份有限公司 用於虛擬化之細粒度位址重新映射
US20170286119A1 (en) * 2016-03-31 2017-10-05 Qualcomm Incorporated Providing load address predictions using address prediction tables based on load path history in processor-based systems

Also Published As

Publication number Publication date
US10838731B2 (en) 2020-11-17
WO2020061220A1 (en) 2020-03-26
CN112740175A (zh) 2021-04-30
US20200089504A1 (en) 2020-03-19
TW202036284A (zh) 2020-10-01
EP3853718B1 (en) 2026-01-28
EP3853718A1 (en) 2021-07-28
CN112740175B (zh) 2025-04-15

Similar Documents

Publication Publication Date Title
TWI739159B (zh) 基於載入路徑歷史的分支預測
CN104471529B (zh) 用以扩展软件分支目标提示的方法及设备
US20120079255A1 (en) Indirect branch prediction based on branch target buffer hysteresis
CN106681695B (zh) 提前取出分支目标缓冲器
JP5745638B2 (ja) 分岐命令の中に符号化されたバイモーダル分岐予測子
US20190004803A1 (en) Statistical correction for branch prediction mechanisms
TW201905683A (zh) 多標籤分支預測表
EP3335109A1 (en) Determining prefetch instructions based on instruction encoding
JP2018523239A (ja) 電力効率的なフェッチ適合
US20200201644A1 (en) System, Apparatus And Method For Focused Data Value Prediction To Accelerate Focused Instructions
US20080072024A1 (en) Predicting instruction branches with bimodal, little global, big global, and loop (BgGL) branch predictors
CN110741345A (zh) 对固定方向分支指令的分支预测
US20210240477A1 (en) Indirect Branch Predictor Based on Register Operands
US20170083333A1 (en) Branch target instruction cache (btic) to store a conditional branch instruction
US9489204B2 (en) Method and apparatus for precalculating a direct branch partial target address during a misprediction correction process
US20190073223A1 (en) Hybrid fast path filter branch predictor
TWI792546B (zh) 用於管線化控制的設備以及方法
CN115826842A (zh) 用于流水线控制的装置以及方法