TW200813824A - Selective branch target buffer (BTB) allocation - Google Patents

Description

200813824 九、發明說明·· 【發明所屏之技術領域】 本發明一般係關於資料處理系統，且更明確而言，儀關 於貝料處理系統中的選擇性分支目標緩衝器（btb)分配。 【先前技術】 許义貝料處理系統如今利用分支目標缓衝:器（ΒΤΒ)以藉 由減小執订分支指令中所花費;的週期之數目而改良處理器 性能。ΒΤΒ作為最近分支的快取記憶體並可以藉由提供一 分支目標位址(分支目的地之位址）或在執行分支指令之前 分支目標中的-或多個指令而使分支加速，此舉允許一處 理器更迅速地開始執行分支.目標位址冲的指令。通常而 言，為所取得之每-個執行的分支指令分配一 ΒτΒ項目。 此舉對於某些ΒΤΒ(例如具大量項目的ΒΤΒ)係合理的，麸 而，對於其他應用（例如其中成本或逨度可能會限制βτβ: 大小的應用），此錄、、表古斗、1 . /解决方式可能不會達到足夠的性能改 良0 【發明内容】 本文所用的術語”匯流排”伤 … 甘徘係用以私禝數個信號或導體.， 叫…t 的貝訊，例如資料、位址、控 恶°如本文中論述的導體可在參考中加以解^ 說明為-翠-導體、複數個導體^ 體。然而，不同呈體垂浐" ^ 或雙向導 如’可使甩分離的單向導體而非㈣導體以/木。例 ^ ^ ^ ^ ^ ^ ^ ^ ^ 4 # fsT1 ^ ^ ^ ^ ^ ° ^ 專輪夕個信.號的單. 121393 .doc 200813824 組耒取代硬數個導體:。同樣地 導體可分忐14 η戰多個意號的單一 ¥版了刀成承載此等 干 此，在力田认 b的于杲之各種不同的導體。因 存在用於傳輪信號的許多選項。 在致使—信號、狀態位元、或相似裝人较 真或邏輯假狀懇時，使用術語..判定”或„二:二 輯假狀恶係·邏輯位韋焚. 、思 ^ 铒位旱零而且右邏舞真狀態係邏輯位準 夺，則邏輯假狀態係邏輯位準一。 -^ ^ n ώ τ ^ ^ ^ Jt g ^ (岡之改良性能：提供根據-BTB分配說明符而選㈣ 地/刀配BTB項目之能力，該說明符可與每—個分支指令相 、中此等分支指令可以係有條件或無條件分支指 令）。根據此BTB分配說明符，當取得—特定分支指令時， 可以或可以不在BTB中分配一項目。例如，在某些應用 中’可能存在大量分支指令（包含有條件及無條件分支指 令）’其得到不頻繁地執行或並不在BTB中保持足夠長的時 間以重新使用，因而在快取分支目標時降低一 btb之性 能。因此，提供用以避免為此等類型的分支指令分配項目 之能办，可獲得改良處理器性能。另外，在許多低成本應 用中’必須最小化ΒΤΒ之大小，因而需要具有對btb分配 的改良控制以便不浪費有限數目的BTB項目之任一者。 【實施方式】 參見圖1，在一項具體實施例中，一資料處'理系統i 〇包 含一積儒電路12、一系統記憶體14以及一或多個其他系統 121393.doc 200813824 模組積體電路】2、系統記憶體14.以及_或多個其他系 、充輪、、且16係經由一多導體系統匯流排而連接。在積體電 =内具！ 一處理器20，其係與-多導體内部匯流排 二亦可稱為通信匯流排)耦合。其他内部模組則及一 ，流排介面單元28亦係.與内部匯流排26連接。匯流排介面 屮山有，、内匯流排26連接的一第—多導體輸入/輸 =以及與系統匯流:排18連接的一第二多導心 杂二%瞭解’資料處理系統10係示範性的。其他具體 2合—單—積體電路或其變化上的所有解說之元 甘、他具體實施例中，僅處理器2〇可能會出現。此 — 具體實_令，彳使用任何數目的積體電路而 實施資料處理系統1〇β 槓“路而 理二tr、積體電路12執行預定資料處理功能，其中處 並^用器指令（包含有條件及無條件分支指令）， 二具，令之性能的其他解說之元件。如以下更詳細 地’ t，處理器20包含—甘士此 符而選擇性地分配項目。 x Βτβ分配气明 部^解說^t本發明之一項具體實施例的處理器20之一 刀處理盗20(其亦可稱為一處理單元）包含一指令解碼 -二、-條件碼暫存器(咖)33、與指令解碼器 一執行單元34、與指令 1知 及#；r抑乂 兀29、指令解碼器32以 生翠—Τ = 34W °㈣單元29包含-揭取位址(a㈣產 ^7、一指令暫存器（寧、—指令緩衝器·23、一. 12I393.doc 200813824 31、BTB控制電路44以及擷取及分支電路‘21。擷取位 址產生單元27提供撖取位址給内部匯流排26且係與擷取及 分支控制電路21以及BTB控制電路44耦合。指令緩衝器23 級輪合用以從内部匯流排26接收擷取的指令且經耦合用以 提供指令給IR 25。指令缓衝器23以及IR 25係與擷取及分 支控制電路21耦合，並且IR25提供指令給指·令解碼器 32。擷，取及分支電路21亦係與4指‘令解碼器“耦合。控 制电路44係與擷取及分支控制電路21以及丑7]5 31耦合，並 ΤΒ|工制電路44經搞合用、以接^ΒΤΒ分配控制信號， /、在項具體貫施例中係由指令解碼器32提供。 控制電路3 6包含按需要用以協調指令的擷取、解碼以及 執仃，且用以讀取及更新〇(：：玟33的電路。通常而言， 33儲存邏輯、算術或比較函數之結果。例如，CCR 33可以 係一傳統條件碼暫存器，其儲存條件碼值，例如-指令的 承载中的結果。或者，CCR 33可以係一傳統條件媽暫存 Ϊ i其二2藉由引起二個數值（或二個運算元）之比較的一 數值係相等或不相等，π 可指㈣二個 個數值…相4或“-個數值係大於或小於另- 擷取單元29&供擁取位址給一 彳 14) … °己隱體（例如系統記憶體 w义一人妾收貧料（例如擷取的指士 存於指令緩衝.器23中1桩基士 4 ^，亥貝枓可加以儲 中並接者加以提供給IR 25。 提供指令給指令鲧派⑽μ 25接者 ι解心32以進行解碼。在解碼之後，暮由 I21393.doc 200813824 =元Γ1Τ執行每一個指令， 全部，以2單元34設定⑽33之條件健之某些或 二回應母一個執行的指令之比較結果。某些指令的 響⑽33之條件碼值之任何者，而其他指令的 订之=料⑽33之條件碼值之某些或全部。執行單 此將^ CR33之更新在該技财已為人所知且因

一、本文中進—步加以論述'此外，擷取位址產生單: ⑽、指令緩衝器23、IR 25以及擷取及分支控制電㈣ ^呆作在該技術中已為人射"此外，任何類型的組態或 =施方案均可用卩實施擷取單元2 9、指令解碼器3 2、執行 單兀34、控制電路36以及CCR %之每一個。 此外’應注意關於偵測BTB命中/錯過、實施並提供分支 預測以及提供分支目標位址的ΒΤβ 3丨及BTB控制電路料之 喿乍亦已為人所知且僅加以論述到幫助說明本文具體實施 例的程度。在一項具體實施例中，BTB 31可儲存分支指令 位址、對應分支目標以及對應分支預測指示器。在一項具 體貝％例中’分支目標可以指示一分支目標位址。其亦可 指示位於該分支目標位址的下一指令。分支預測指示器可 提供一預測值，其指示對應分支指令位址中的分支指令是 否將預測為取得或未取得。在一項具體實施例中，此分支 預測指示裔可以係二位元計數器值，其得以增量至一較高 數值以指示一較強取得預測或減量至一較低數值以指示一 較弱取得預測或指示一未取得預測。可使用分支預測器指 示器之任何其他實，施方案。在一:替代性具體實施例中，，分 I21393.doc 11 · 200813824 支預測為扣示益可能不會出現，其中（例如）在STB 44命中 的分支可始終加以預測為取得。 在一項具體實施例中，藉由BTB控制電路44將由擷取位 址產生單元27產生的每一個擷取位址與btb 3〗之項目比較 以決定擷取位址是否在BTB 31中命中或錯過。若該比較產 生中令，則‘可假定擷取位址對應於欲加以擷取的分支指 令。在此h況下，假定分支係預,測為取得，BTB 3 1經由 BTB控制電路44提供對應分支目標給擷取位址產生單元 27 ’因此可以擷取位於該分支目標位址的指令。若讓比較 產生一錯過，則BTB 3 1無法用以迅速地提供預測的分支目 裇。在一項具體實施例中，即使該比較產生一錯過，仍可 以提供一分支預測，但是分支目標並非如由Btb 3丨加以提 供一樣迅速地加以提供。最終，實際上分辨分支指令（藉 由（例如）指令解碼器32或執行單元34)以決定在分支指令之 後欲加以處理的下一指令。在加以分辨時，若該分支指令 原来係已得到錯誤預測，則已知處理技術可用以操縱錯誤 預測。 參考指令解碼器32，在一項具體實施例中，若指令解碼 器32係在解碼一分支指令，則指令解碼器32提供一 BTB分 配控制信號22給BTB控制電路44，該電路將用以幫助決定 目前解碼的分支指令是否欲在一 BTB錯過之後加以儲存在 BTB 31中。即，控制信號22係用以幫助決定是否為該分支 指令分配BTB 31中的一項目。在一項具體實施例中，所解 碼的分支指令包含指呤解碼器32用以產生BTB分.配·控制信 121393.doc -12- 200813824 號22的BTB分配說明符。例如，BTB分，配說明符可以係一 分支指令之一位元欄位，該分支指令在加以設定為一，第一 值時指示在該分支指令係決定為取得之情況下ΒΤΒ 3 1中的 一項目欲在一 ΒΤΒ錯過之壤而加以分配，並且在加以設定 為一第二值時指示ΒΤΒ 3 1中的一項目並非欲在一 ΒΤΒ錯過 之後加以分配，即使該分支指令係決定為取得亦如此。 即，該第二值將:指示無·βτβ分配將出現'。可以相應地產生 ΒΤΒ分配控制信號22，其中（例如）信號22可以係一位元之 · - - ' . 4吕號’其在加以設定為一第一值時向ΒΤΒ控制電路44指示 在對應分支指令係決定為取得之情況下ΒΤΒ 3 1中的一項目 欲在一 ΒΤΒ錯過後加以分|，並且在加以設定為一第二值 時指示無ΒΤΒ分配將為該分支指令而出現。因此，可以設 定一碼之段內的每一個特定分支指令，從而以每個指令為 基礎產.生ΒΤΒ分配或產生無ΒΤΒ分配。 例如，參考圖3，提供一樣本分支指令，其包含一運算 碼42(其指任何類型的有條件或無條件分支）、一條件說明 符48(其指示應在何條件或何等條件下取得該分支）、一 BTB分配說明符50(如以上說明，其指示在取得該分支指令 的情況下BTB分配是否欲在一 BTB錯過之後出現）以及一置 換52(其係用以產生分支目標位址）。置換52可以係一正或 負值，其係添加至程式計數器以提供分支目標位址。應注 思’在其他具體實施例中，可使用其他分支指令格式。例 如，一中間欄位可用以提供目標位址而非置換或偏移。或 者 子運异碼亦可出現以進一步定義分支類型。該條件 I21393.doc 200813824 說明符可包含:一或多個涖元，其指一或多個條件碼或條件 碼的組合，因此當滿足該條件說明符時將分支指令評估為 α 真（因而係一取得分支）。應注意，用以評估分支指令並決 定是否滿足條件說明符的CCR 33之條件值可由另一指令 (例如分支指令之前一指令）加以設定，該指令可（例如)實 施邏輯、算術或比較運算，或可由分支指令本身加以設定 (例如，在運算碼42指定”比較及分支”指令的情況下）。此 外，運算碼42可指示始終取得的一無條件分支，且因此條 件說明符48可以不出現，或可加以設定成指示”始終分支”。 在另一替代性具體實施例中，ΒΤΒ分配說明符50可加以包 含或編碼為分支運算碼42之部分。例如，除具有擁有一特 定運算碼及可加以設定成指示分配或無分配的一 ΒΤΒ分配 說明符之一特定分支指令（例如等於零的分支）以外，二個 分離的分支指令（即二個分離的運算碼）可用以區分具有分 配的分支（例如具有ΒΤΒ分麗且等於零的分支）與沒有分配 的分支（例如沒有ΒΤΒ分配且等於零的分支）。 在另一具體實施例中，ΒΤΒ分配說明符50可不加以包含 為分支指令本身之部分。例如，在一項具體實施例中，可 提供對應於分支指令的分配說明符之一分離表格。可藉由 (例如）ΒΤΒ控制電路44從記憶體（例如從系統記憶體14或由 資料處理器12提供的區域記憶體）讀取此表格或位元映射 以用於每一個分支指令。在此情況下，Β ΤΒ分配控制信號 22可由指令解碼器32加以提售，但可改為由ΒΤΒ控制電.路 44加以暗示或明碟地產.生，以決定是否分配ΒΤΒ 31中的一 121393. doc - 14- 200813824 項目。因此，一btb分配說明符可採用各種不同方式按需 要為每一個分支指令而加以提供，且不限於加以包含為分 支指令本身之某部分，但改為可常駐於位於資料處理系統 10内之任何類型的資料結構中。 將荟考圖4之流程60進一步論述]3TB分配說明符、訂]5控 制電路44以及BTB 31之操作。流程6〇始於起點61並進行至 步驟62，其中解碼具有心ΒΤΒ分配說明符的一分支指令。 (應注意，如上所述，ΒΤΒ分配說明符可加以包含為該指令 之部分，例如圖3中的部分，其中該部分可加以編碼為運 算碼之部分，或可由記憶體中的表格分離地加以提供。此 外，應注意，該分支指令可以係一有條件或無條件分支，: 其中一無條件分支係一始終取得分支。）流程進行至步驟 64，其中根據该ΒΤΒ分配說明符產生—分配控制信號（例如 ΒΤΒ分配控制信號22)。流程進行至決策菱形％，其中決定 該分支指令是否產生一 ΒΤΒ錯過。若未產生，則流程進行 至步驟68，其中如以上說明，為回應ΒΤβ幻中的命中， ΒΤΒ 31提供-分支目標給擷取位址產生單元^且可能亦提 供一分支預測。即，為回應一ΒΤΒ命中而由ΒΤΒ Μ提供的 資訊係接著用以處理該分支指令，此在該技術中已為人所 知。流程接著在終點80處結束。 然而，在決策菱形66中，若該分支指令並未產生一錯過 (即，該指令或其指令位址並非位於BTB 中），則流程進 行至決策菱形7G，纟中接.著.決定是否已取得該分支^。 在分辨分支條.件以決定.其是否係一取得分支後做出此決 12I393.doc -15· 200813824 策。可執行此分支分辨，此在該技財已為人所知。若該 分支最終未加以取得，則流程進行至終點8〇，其中序列指 +處理可從該分支指令繼續進行。然而，若該分支最終加 以取得，則流程進行至決策菱形72，其中將該分配控制信 • 號用以決定BTB分配是否將出現。若該分配控制信號指示 - 77配則在步驟料中為該分支指令分配一 B TB項目。即， 例ά BTB乙制私路44分配’BTB 31中的一項目以儲存該分 翁支指令之位址、用於該分支指令的分支目標、以及一項具 體貝^例中用於該分支指令的—分支預測器。應注意在執 行此步驟時，ΒΤΒ控制電路44需要接收甩於分支指令以及 分支目標的位址值。此等數值可由處理器2〇之不同部分加 以提供，此取決於如何實施處理器2〇之電路及管線。在一 項fe例中，擷取單元29内的電路（例如擷取及分支控制電 路21)記錄每一個分支指令之位址以及分支目標位址。或 者，位於擷取單元29或處理器2〇別處的其他電路（例如管 • 線狀電路）可維持在分配BTB 31中的一BTB項目時所需要 的此更新資訊。 • 於在步驟74中分配一BTB項目之後，流程進行至步驟 76 ’其中處理分支指令，此在該技術中已為人所知。在決 策菱开^ 72中’若該分配控制信號指示無分配，則流程進行 至步私78，其中BTB項目之分配未出現。即，即使分支指 令係決定為取得（在決策菱形70中），BTB分配說明符係仍 用以扎不此時並沒有為此分支指令而分配BTB 3 1中的項 目。因此，流程，進行至步驟76，其中處理該分支指令，此 121393.doc -16- 200813824 在,玄技術中已為人所知，但該分支指令尚未加以儲存在 BTB 31申。流程接著在終點8〇處結束。 圖5解說甩於關於依據本發明之一項具體實施例的一第 一及第二分支指令的選擇性BTB分配之方法，每一個分支 • #令具有—BTB分配說明符。即’圖5之方法解說如何可 . M將BTB.分配說日月符用於*支指令，從而以每個指令為 基礎以—BTB項目之分配是否會出現”流程始於起182 籲 亚進仃至步驟84 ’解碼（例如藉由指令解碼器32) —第一分 支指令’其中該第—分支指令具有由—條件碼暫存器(例 如CCR 33)中的—或多個條件值所表示的一預定條件。例 如’可由該第-指令内的—條件說明符（例如參考圖3論述 ㈣件㈣㈣)來指定㈣定條件1狀條件指示在 何^条件或何等條件（如由該CCR内的條件值所表示）下取得 分支指令。該第—分支指令亦具有設定成指示咖 、·的對應BTB分配δ兒明符（其可暗示或明確地加以提供 • 為該第—分支指令之部分，如上所述，或可由-表格或另、 一電路加以提供）。 . ，程接著進行至步驟86，其中，若該第一分支係決定為 取侍（根據該預定條件之評估)，則在一 βτβ錯過之後分配 ' 該㈣中的一 ΒΤΒ項目（因為’如以上陳述，對應於此第— 分支指令的該BTB分配說明符指示ΒΤβ分配）。流程進行至 义驟88，其中完成該第一分支指令的執行。 ^ ^ a ^ ^ ^ # ^ 90, # ^ ^ ^ ^ ^ ^ •17· 200813824 暫=态中的一或多個條件所表示的一預定條件。應注意該 等第一及第二分支指令可以指同一或不同預定條件。然 而對應於叆第二指令的_ BTB分配說明符係設定成指示 無BTB分配。因此，在_項具體實施射，該等第一及第 二分支指令可以係同一類型的分支指令（因為其具有同一 運开碼，例如運算碼攔位42)，但具有不同的分配說明 付（例如ΒΤΒ分配說明符50)。或者，該等第一及第二分支 指令可以係不同類型的分支指令，其中該第一分支指令對 應於具有分配的分支指令’而該第二分支指令對應於沒有 分配的分支指令。 =程接著進行至步驟92,其中，若該第二分支係決定為 取知·（根據該預定條件之評估），則在一 ΒΤΒ錯過之後不分 配忒ΒΤΒ中的一 βτβ項目（因為，如以上陳述，對應於此第 二分支指令的該ΒΤΒ分配說明符指示無ΒΤΒ分配）。流程接 著進打至步驟94，其中完成該第二分支措令的執行。流程 接著在終點96處結束。 圖6至9 σ兒明如何標記或編碼用於β τβ分配的分支指令之 方法。即，參考圖6至9說明的具體實施例允許決定何分支 才曰令應產生ΒΤΒ分配以及何分支指令不應產生該分配。一 旦決定此點，則可以相應地設定用於每一個分支指令的一 ΒΤΒ分配說明符，其中此ΒΤΒ分配說明符可以係如以上說 明。例如，其可以係該分支指令内的一隱含攔位，在該指 令内加以明確編碼，可加以儲存在從記憶體讀取的一分離 表袼中，可加以提供在用於每一個指令的一位/元映射格式 -1S .· 121393.doc 200813824 中，該格式允許進行—分配/無分配選擇等。因此，在解 碼或執π已，以决疋會產生BTB分配或無分配的此等 刀支I"之後可以產生_適當的ΒΤβ分配控制信號(例如 以上說明的ΒΤΒ分配控制信號22)。在其他具體實施例中， -旦將特定分支指令標記為分配或無分配型分支指令，射 可將任何機制用以儲存輕配/無分配資訊並且可將任何 機射用以在碼執行期間按需要適當地提供此資.訊。 碼剖析可用以獲得關於说+ 备 關於碼或碼之段的資訊。此資訊可接 著用以（例如）更有效率祕姐w 構ie亚編譯碼以用於其最，终廖 用。在一項具體實施例中，碼剖析係用以控制用於取得: 支的BTB項目之分配策略（例如藉由適當地設定BTB分配說 明：以指示對特定分支指令的分配或無分配卜 體貫施例中，採用啟發方式 A 万式組合特定因數以找到用以分配 分支的近似最佳分配策略。_個因數可以係取得—分支的 絕對次數(例如很可能如何頻繁地取得-分支)，並且另— 個因數可以係在隨後分支之臨界值⑽數目内未取得 β玄分支的次數之相對百分比（例如，此因數可反映一特定 分支很可能在ΒΤΒ中保持多長時間)。在且者施 中，Tthresh之數值俜 士 貝…版貝細例 W值係以啟發方式得▲的 到BTB項目之數目的限制 …在低知文 數目的限制。在—項且體端受到二倍咖項目之 在執行μ、 Tthresh之數值係用以 支二:二牛時約計BTB之容量，為並非所有取^ 、、須在一B 丁B錯過.之後分配該βΤΒ中的—目 該则之”有效.，，容㈣大於實際β 目，所以 貝㈢之數目。該BTB · 121393.doe •19- 200813824 中一^吾貫際項目之蠢曰的料 上，此上限係通常足%的分配率。實務 多分支並非在分5:;!广任何較大上限均暗示許 ^ ·此可此會降低性能。對於某此胜〜 析範例而言’].2至】.5的數值會產生近似最佳的r果二 而，其他剖析範例採用不同數值可能會執行得^果。然 在一項具'體實施例中，芸八士此人 .支的絕對次教α值、 令並未滿足取得該分 得該分支的次口值百::其超過臨界〜 的情況下她二 則該分支指令在加叫 于知σ己為不分配一 Β ΤΒ項目〇 刀析的碼之區段中的每一個分支指令設立四個計數 器。此等計數器係解說在圖6中。例如，圖6解說用於碼段 =0中的母一個分支指令之一組四個計數器。例如，計數 裔101至m對應於branch—A指令，計數器1〇5至 branch—B指令，以及計數器1〇9至ιΐ2對應於^祕—€指 令。碼段100解說欲加以剖析的一碼之段（其可包含在 INSTi之前或在branch一c指令之後的多個指令，如由各圓 點所指示）。此段可以按需要為較小或較大，其中每一個 剖析的分支指令將包含對應的：四個計數器。該四個計數器 將麥考branch一A指令以及計數器1〇1至1〇4加以說明。計數 态101係一 branch一A執行計數，其保存在碼段1〇〇的執行期 間（例如在一特定時間框架内）執行branch一A的絕對次數之 計數。計數器102係branch—A取得計數，其保存取得 branch—A指令（例如在一特定時間框架内）的次數之計數。 121393.doc •20- 200813824 計數器1〇3係一，，其他取得分支計數I，，其保存在b_Ch A 指令的取得出現之間出現的其他取得分支之數目的計數―。 f數..104係-超過臨界值計&，其在每—次取得 時得到更新並記錄計數器⑻是否超過—預定臨 二值此專计數器的操作將參考圖8之流程更詳細地加以 =。此外，計數器⑻至刚之說明亦分別適用 branch—C指令。 - 圖？一說操作以模擬該BTB的最後n個取得分支之一列 ΒΤΒ中的；cr日丁列）’其中Ν可以大於或等於該 個取『八1之數目。圖7解說在不同時間點取得的最後Ν ==列表的，照。灿 取彳的取彳于分支係由較大 _ 10〇t ^ ^^^^#branch A, 〇 新最後N個取得分支之列表，/中^圖所示採用列表⑽ 支項目⑽為該列表在此範财 列表122中，最新的取得分^： h—FIF〇)。因此，在 所指示。若接著決定取得branch A，如由較大箭頭 124更新最❹個取得分支之列-=如圖所示採用列表 最舊的分支項目，其係分支h因;；、中代替當時 的取得分支係branch B，如’在列表124中，最新 若接著·決定取得一h_c，則= 、圖所不採用列表126更新 I2II93.doc 200813824 最後N個取得分支之列 J表，其中brancii—C取代當時最舊的 分支項目，其係分支2。 文2因此，在列表126中，最新的取得 分支係branch-c，如由較大箭頭所指示。最後_取得分 支之列表的更新亦將參相8之流程加以更詳細地論述。 應注意’在—項具體實施财，計數if mm以及最 後N個取得分支之列丰 — 、 、了加U霄施為一碼剖析器之軟艎：組, 或者’、可在硬體或韌體，或硬體、韌體以及軟體之 組合中加以實施。 圖8之流程解說用以更新以上參考圖6說明的計數器之方 β ° ^㈣心13()並進行至步驟132,其中初始化用於 欲加以剖析的碼之段之資料結構。例如，欲加㈣析㈣ 之段可指碼段1 〇〇，#日兮黎次"t 抑 並且δ亥專為料結構可包含（例如）計數 益、界值等、或執行圖8之流程所需要的任何其他資料 結構。例如’計數器可加以清除（即初始化為零），而臨界 值可加以設定為預定值。流程接著進行至決策菱形134, 其中決定在剩餘的碼段中是否存在多個指令要執行。若不 存在，則流程於終點136處結束。若存在，則流程進行至 步驟138 ’其中將下一指令執行為當前指令。 流程接著進行至決策菱形14〇，其中決定該當前指令是 否係-分支指令(例如branch_A)。若並非一分支指令，則 流程返回至決策菱形134。㈣-分支指令，則流程進行 至步驟U2，其中為該當前分支指令而使分支執行計數(例 如計數器101)增量。流程進行至決策菱形144，其中決定 疋否取侍當則分支指令。若未取得，則流程返回至決策菱 121393.doc 200813824 形m(其中.未更新其他計數器）。若已取得，則流程進行至 步驟146 ’其十為該當前分支指令而使分支取得計數器(例 如計數器102)增量。 流程接著進行至㈣148，其中耗μ分支指令並非 在最後Ν個取得分支之一列表中（例如參考圖7說明的列 表），則使.碼之段中的分支指令而非#前分支指令之宜他 料分支計軸如特諸7及丨】υ增量1接著將該當 前分支指令放置於最後N個取得分支之列表中。因此，應 ”，當正在執行該當前,分支指令時’並不更新用於該； 雨分支指令的其他取得分支計數（例如計數器103)，但是當 正在將該碼段内的—不同分支指令執行為該當前分支指: 時，可更新該計數。 7 流程接著進行至決策菱形15〇,其中決定用於該當前分 支指令的其他取得分支計數（例如計數器1〇3)是否大於計數 更新臨界值(Tthresh ’其亦在以上加以說明)。若係大於， 則流程進行至步驟152 ’其中使用於該當前分支指令的超 過臣品界值計數（例如計數器1〇4)增量。流程接著進行至步驟 154〇 則流程進行至步驟154(無需使得用於該當前分支指令 用於該當前分支指令的其他取得分支計數（例如計數^ ，。流程接著返回至決策菱形134以決定在該碼之段; 是否存在多個指令要執行。 由1玄等外數器（.例如計數器101至！ 12)隨,圖8之流程所收 12I393.doc -23. 200813824 的貢訊接著可用以標1己何分支指令應產生BTB.分配以及何 刀支和令不應產生BTB分配。例如，圖9解說一流程，其. 可用以分析每一個分支指令，其中其對應計數器之計數器 值可用以決定對應於該分支指令的—BTB分配說明符是否 應指示BTB分配或無BTB分配。 圖9之流私始於起點159並進行至決策菱形丨6〇，其中決 定是否存在多個分支指令要分析。若不存在’則流程於終 -占171處結束。若存在’則流程進行至步驟丨以’其中將下 刀支4曰令選擇為該當丽分支指令（例如該當前分支指令 可以係branch—A指令）。流程接著進行至決策菱形““其 中決定用於該當前分支指令的分支取得計數（例如計數器 ⑽的最終值)是否小於一分支取得臨界值(其可以係由使用 者進行該碼剖析㈣定的-敎臨界值，取決於欲執行該 之性能需求）。若小於，則.流程進行至步驟166, /、中决疋對應於該當前分支指令 7的BTB分配說明符應指 ^ 一 BTB錯過之後無BTB分配。即，因為該分支並非很 此加以取得足夠的次數’所以其不必佔用該訂B 一 在該B TB中提供許多數值。可針對所剖析的碼之=個转 定實例而採用實驗方式或啟發方式決“分支 = 值。對於某些碼剖析範例而言， 侍臨界 數值一或二可以產生近似最佳的分配二年::臨界值的 析範例採用不同數值可能會執行得更好。“、、，其他剖 在決策菱形164中，若該分支取 121393.doc • 24. 200813824 分支取得臨界值，則流程進行至決策菱形⑽，i中決定 用㈣當前分支指令的該超過臨界值計數（例如計數器'1〇4 之隶終值’鱗數⑸㈣最終值除㈣分支計 數器102值）’從而表示當取得該分支時超過該臨界值的次 數之相對百分比）是否大於—刚容量臨界值。若大於，則 流程進行至步驟166，盆φ介4 a -— 其中亦決定對應於該當前分支指令 的一 Β ΤΒ分配說明符岸.，指 ^ 應和不在一 ΒΤΒ錯過之後無ΒΤΒ分 配。即，在此情況下，該者箭 … 乂田則刀支指令將报可能不於該 存在足夠長料心具有數值，由於藉❹ΤΒ分配 且藉由在所取得的此分支之實例之間執行的其他取得分支 所取代’並因而較佳的係不為該當前分支指令分配一項目 且可移除一更有用的項目。 在決策菱形1 68中，若該分古兩ρ >丄& ^ 刀支取侍计數係小於或等於該 避容量臨界值）則流程進行至步驟17〇，其中決定對庫 於該當前分支指令的-跑分配說明符應指示㈣分配^ 在-ΒΤΒ錯過之後出現。即’因為該當前分支指令报可能 加以取得足夠的次數，且很可能保持在該βτβ中足夠長的 時間以重新使用，所以對該當前分支指令進行標記以便在 其加以取得並且一ΒΤΒ錯過出現聘為其分配一 ΒΤΒ項目。 在步驟166及170之後’流程返回至決策菱形16〇，其中分 析下一分支指令（若更多分支指令存在）。 刀 決策菱形168之ΒΤΒ容量係—般設定為表示超過臨界叶 Μ允許次數的-較小數值，或者當將相對百分比用作度 量聘，設定為表、示超過該臨界計數的次數之最大允許百分 121393.doc -25^ 200813824

比的-較小百分比，其.中在—項具.體實施例中，該等數值 範圍係從㈣至鄕，儘管用於此參數的最佳數值可採用 貫驗方式加以決定以用於剖析所需要的每一個碼段。在一 項具體實施例中，計數器102及!04之使用、如圖7所示的 最後N個取得分支之列表、以及該㈣容量臨界值允許模 型化BTB.活動性’其中項目之足夠的新分配可在該當前分 支的取得出現之間出.現以便即使該當前分支分配一btb項 目’其仍將藉由項目之分配且藉由其他分支所置換，然後 再次取得當前分支。在此情形下，更有利的可能係根本不 為該當前分支分配-項目，因為一 ΒΤΒ錯過报可能在下一 -人取得該當前分支時無論如何都將出現。此係由決策菱形 ⑽執行的決策程序’纟中此決策程序提供關於在隨後分 支之-臨界值（例如Tthresh)數目内未取得分支的次數之相 對百分比的資訊。 在分析+每一個分支指令且為每—個分析的分支指令設定 btb刀配策略之後m相應地構造並編譯獲得的碼段。 2舉提供將執行獲得的碼段之處理器中的該btb之改良性 f則其可由處理器20加以執行，該處理器使用]8丁；8分配 策略說明符（如以上說明）以產生β Τβ 3 i之改良執行及改良 使用，在BTB空間受到限制的情況下尤其如此。 ，注，，此等計數器的使用簡單地提供一啟發以决定分 支指令是否應或不應產生BTB分配。~，並不衫滿足或 不滿足以上臨界值的指令在其最終應甩中於碼段（例如碼 121393.doc -26- 200813824 段100)之實際執行（例如由 期門θ不-Γ— 上說明的處.理器20執行碼段） 期間笮否可在ΒΤΒ令使用。 支將#可处4 / ，、、、而，可以瞭解如何監視一分 克將很可此如何頻繁地加以執 丄 代f ‘作 Α 及一分支指令在被取 代之則很可靶將保持在ΒΤΒ争 ，物在下一次該::時間之因數，從而表示 + 支心令得以執行並決定為取得 時出現:的機率，—改良分配第政 决疋為取付 朿略可加以決定並透過使甩 /主思’以上流程圖之實施方案可根據應用而不同。此 ㈣中的許多㈣可加題合並同時進行或可擴大 ’’、、夕個私序。因此’本文說明的流程圖僅係示範性的。例 如’在，之決策菱形164中’除使用取得該當前分支的次 數之絕對計數料’改為可❹取得該分支的次數之百分 比’並且此數值可藉由下列方式加以計算：將分支取得計 數（例如計數器102、106或11 〇)之數值除以用於-對應分支 指令（例如分別為branch_A、branch一B或braneh_c)的分支 執行計數（例如分別為計數器101、1〇5或1〇9)之數值。在另 —具體實施例令，可使用未取得該分支的次數之百分比， 其中-計數器（與計數器102、1〇6及11〇相似）可用以記錄未 取知對應分支指令的次數。流程程序的其他延伸部分亦預 計由本發明之範疇所涵蓋。 在一項具體實施例中，一種處理其中執行分支指令之一 資料處理系統中的資訊之方法包含：接收並解碼一指令， 根據籍由另一指令的執行或該指令的執行之一比較結果所 设定的’一條件碼值而決定該指令係一取得分支指令，以及 121393.doc -27- 200813824 決定使用與該取得分支指令相關聯的一指令說明符以決定 是否分配一分支目標緩衝器之一項目以儲存該取得分^指 令之一分支目標。 在另一具體實施例_，該方法包含將該指令解碼為一比 較及分支指令。 ^

在另-具體實施例中，藉由另一指令的執行或該指令的 執行之一比較結果所設定的該條件碼值進一步包含比較二 個運异元是否相等以提供該比較結果。 在另一具體實施例中，藉由另一指令或該指令之一比較 結果所設定的該條件碼值進一步包含比較二個數值。 在另-具體實施例中，該方法包含將該指令說明符實施 為該指令之一預定攔位。 在另-具體實施财，該條件碼值表示—承載值、一零 值、一負數值或一溢位值之一。 在另-具體實施财方法包含接收並解碼係—有條 件分支或-無條件分支的〜第_分支指令，該第—分支指 令具有一第一分支目標緩衝器分配說明符，若取得盥該第 -分支指令相關聯的一分支，則分配一第一分支目標緩衝 ，以根據該第一分支目標緩衝器分配說明符而儲存該 第-分支指令之一分支目標’完成該第一分支指令的執 行;接收並解碼係-有條件分支或_無條件分支的—第二 分支指令，該第二分支指令具有―第二分支目標緩衝器分 配㈣符’若取得與該I二分支指令相關聯的—分支，則 决疋不刀配一第—分支目，標緩衝器項目以根據該第二分支 121393.doc -28- 200813824 目標緩衝器分配說明符而儲存該第二分支指令之一分支目 標，以及完成該第二分支指令的執行。 在=另一具體實施例之另—具體實施例中，該方法包含 將該第二分支指令解碼為一無條件分支指令。 在該另-具體實施例之另_具體實施例中，該方法包含 將該第-分支目.標缓衝器分配說明符以及該第二分支目_

緩衝器分配說明符分別實施為該第-分支指令以及該第I 分支指令之一部分。 在該另一具體實施例之另一 一 力 具體貝灰例中，該方法包含 =括一有條件分支指令的該第一分支指令或該第二分支指 7 m項’其中根據—條件碼暫存器中的—條件碼值 而取得指令執行期間的_分# θ· ^ 丄 刀支在另一具體貫施例中，該 方法包含從該第一分支指今 又？日7、该弟二分支指令或另一指令 之一的執行之一比鮫结果，Μ 、果稭由比較二個運算元是否相等 以提供該比較結果來決㈣條件碼值。在另—具體實施例 X方法3根據實把—邏輯、算術或比較運算的—額 外才曰令而決定該條件碼值。 在另一具體實施例中，該方法 包含將該條件碼值實施為一 Κ 承载值、——零值、一負數值或 一溢位值之一。 在一項具體實施例中，—資料處理系統包含一通信匯流 排，以及與該通錄崎耦合的—處理單元。該處理單元 包含用以接收並解碼指令的一 心令解碼器、與該指令解碼 器耦合的一執行單元、盥哕扣 抑一 令解碼器耦合的一指令擷取 卓元，遠指令揭取單元包接m 用Μ儲存分支指令之分支目標 12l393.doc -29 - 200813824 單元使用舆二 ==控制電路，其_ ^ δε m - 、π支寺曰令相關聯的一分支目標緩衝器 刀配呪明仲以決金Β 借存#接你、疋否刀配該分支目標缓衝器之一項目以 _接收的分支指令之一分支目標。 在另一具體實施例中，访次Αί # 流排輕合的體.以貝科處理系統包含與該通信匯 系統模組：體’…與該通信匯她合w -二:::施例’，該接收的分支指令係根據藉由另 # 7或该接收的分 -或多個條件碼值而决:： 之—比較結果所設定的 r 值而決定為一取得分支指令。 在另-具體實施料，該接收的分 轉 支亚且該指令擷取單元並不 支缓衝 項目以回應該分支目以^、刀支目^衝4的一 又曰铋綾衝态分配說明符。 在另一具體實施例中 指令，並衫在-單元接收—第—分支 目標緩衝器中產生—錯過巧…疋為取传且於該分支 日1^守為5亥弟一分去#人八 目標緩衝器項…應用於該第一分心^ 缓衝器分配說明符。兹指令操取單^ 指令，並在該第二分j h後第二分支 V 支指令係決定為取得且於兮八士 緩衝器中產生-錯過時，彻 目標緩衝器項目以回應用於該第二錢ϋ:—分支 緩衝器分配說明符。 ^ 7的分支目標 在另一具體.實施例中，對 對於稭.由_碼暫存器指示的 121393.doc ‘30· 200813824 同一條件而言’該指令擷取單元在—第―分支指令係取得 且於該分支目標緩衝器中產生一錯過時為該第一分支指令 分配-分支目標緩街器項目，並在一第二分支指令係取二 且於該分支目標緩衝器中產生—錯過時不為該第二分支指 令分配一分支目標缓衝器項目。 在另—具體實施例中，該條件碼暫存器根據崎令而儲 存數值，其中該指令實施一邏輯、一算術或一比較運算之 — Ο 在以上說明書中’已參考特定具I實施例而說明本發 明。然而，熟習技術人士應明白可進行各種修改與改變ς 不脫離如以下申請專利範圍中所提出的本發明之範嘴。例 如，方塊圖可包含不同於所解說的方塊之方塊並且可 或多或少的方塊或加以不同地配置。此外，流程圖亦; ::二也配置，包含或多或少的步驟，或可具有可加以分 成户固乂驟的步驟或可彼此同時加以執行的步驟。亦應瞭 本文說明的所有電路可在m半導體材料中或者 牛V版材枓之軟體碼表示加以實施。

說明書及圖式應視A經啕立#二4 C _ Λ職為解“義而非限制㈣， 修改係預計包含在本發明之範疇内。 有匕類 二ΐ方ΤΓ體實施例而說明益處、其他優點及問題 的解决方式。然而，益虛 ^ 佶任付/考 I，、、問題解決方式以及可能 可i處、優點或解決方式出現或變得更明 件均不應視為任何咬ϋ ^ ”、、可元 或元件。本文中關鍵、必要或基本特徵 本文中所用的術語"包.含"、”包括”或其任何其他 I21393.doc -31 - 200813824 變化係預計涵蓋一非專 。 ,内3物，使仟包括一元件列表的 法、物品或裝置不僅包括該等元件，而且可包枯 未明確列出的或此類程序、 。 元件。 乃忐、物口口或裝置固有的其他 【圖式簡單說明】 =明係經由範例而解說以受附圖..的限制，其中相 參考扣示相似元件，並且其中： 圖1以方塊圖形式解說依據本發明之一項具體實施例的 一貧料處理系統； 項具體實施例白< 圖2以方塊圖形式解說依據本發明之 圖1之一處理器的一部分； 圖3解說藉由依據本發明之一 + ^ ^ ^ 項具體貫施例的圖2之處王! 器所執行的一分支指令； … 圖4以流程圖形式解說用於依據本發明之一項具體實坡 例的選擇性BTB分配之方法； 圖5以流程圖形式解說用於關於依據本發明之一項呈體 實施例m第二分支指令的選擇性btb分配之方 法； 圖6解說與依據本發明之一項呈，參 + ^ ^ 項具體霄施例之碼之段内的 每一個分支指令相關聯的複數個計數器； 圖7解說依據本發明之一須且辦眚念 '乃I項具體只轭例之一碼段的最後Ν 個取得分支之一列表的各種時間快照； 圖8以流程圖形式解‘說用於更新依據本發明之一項具體 實施例的圖.6之計數器以及圖7之最後Ν個取得分支的列表 12l393.doc •32- 200813824 之方法；以及 明之一 而分析 圖9以流程圖形式解說用以使用決定為依據本發 項具體實施例的圖8之流程的結果之獲得的計數值 分支指令之方法。 熟習技術人士應動，該㈣式中h件m ^ 清楚而解說且不必按比例㈣1例如 ^ “早 明

之尺寸可相對於其他元件而加以詩大以。中的㈣ 之具體實施例的瞭解。 助改良對本發 【主要元件符號說明】 10 資料處理系統 12 積體電路/資料處理器 14 系統記憶體 16 其他系統模組 18 系統匯流排 20 處理器 21 擷取及分支控制電路 22 BTB分配控制信號 23 指令緩衝器 24 其他内部模組 25 指令暫存器（IR) 26 内部匯流排 27 擷取位址產生單元 28 匯流排介面單元’ 29 擷取單元 121393.doc -33- 200813824

30 指令擷取單元 31 分支目標緩衝器（BTB) 32 指令解碼器 33 條件碼暫存器（CCR) 34 執行單元 36 控制電路 42 運算:、碼 44 BTB控制電路 48 條件說明符 50 BTB分配說明符 52 置換 100 碼段 101 計數器 102 計數器 103 計數器 104 計數器 105 計數器 106 計數器 107 計數器 108 計數器 109 計數器 110 計數器 111 計數器 112 計數器 121393.doc - 34 · 200813824 120 列表 122 列表 124 列表 126 列表 121393.doc -35

Claims (1)

1. 200813824 十、申請專利範圍： 1· 一種處理其中執行分支指令之一資料處理系統中的資訊 之方法，其包括： 接收並解碼一指令； 根據藉由另一指令的執行或該指令的執行之一比較結 果所設定的一條件碼值而決定該指令係一取得分支指 令；以及 便用興該取得 決定是否分配一分支目標緩衝器之—項目以儲存該取4 分支指令之一分支目標。 t如凊求項1之方法，其進一步包括將該指令解碼為一 t 較及分支指令。 月长員1之方法，其中藉由另一指令的執行或該指d 的執行之一比較結果所設定的該條件碼值進-步包含t 車又—個運异兀是否相等以提供該比較結果。 乂：：所设定的該條件碼值進一步包括比較二個數值。 如凊求項1之方法，其進-步包括： 將該指令說明符實絲么二 6. 、施為该扣令之一預定攔位。 文^'1之方法’其中該條件碼值表示-承載值、、 零值、—負數值或一溢位值之_。 7. 一種方法，其包括： 分t =解碼係一有條件分支或一無條件分支的―第-…該第—分支指令具有-第-分支目標緩衝〗 121393.doc 200813824 分配說明符：； 斤右取付與該第—分支指令相關聯的一分支，則分配一 第一分支目標綉板w = ^ ♦衝益項目以根據該第一分支目標缓衝器 分配說明符而儲在 居存漆弟一分支指令之一分支目標； 完成該第一分去4t人 支扣令的執行； 接，收並解碼係— ’、 有條件分支或一無條件分支的一第二 为支指令，該窠_ 、 7刀支指令具有一第二分支目標緩衝器 分配說明符.； 古取得鱼兮宽一 \ 〃 μ 矢支指令相關聯的一分支，則決定不 釦配一第二分支 經你抑、 又3‘緩衝器項目以根據該第二分支目標 硬W态分配銳明 ,a. r; 月付而儲存該第二分支指令之一分支目 ，以及 令的執行。 •如研求項7之方法，复、隹一本 碼為-無條件分^令進—步包括將該第二分支指令解 9 ·如請求項7之方法 衝器分配說明符:及其，進r步包括將該第-分支目標緩 分別實施為該第一八：弟一分支目標緩衝器分配說明符 分。刀支指令以及該第二分支指令之一部 ίο.如請求項7之方法，直牛 令的該第-分支指“該第：=括—有條件分支指 I條件碼暫存器令的1 /項，其 期間的— 分支。—條件碼值而取得指令執行 11 ·如請来，a 尺項10之方法，直 其’進…步包括從 該第 12J393.doc 分支指令 200813824 該第二分支指令或另一 A 的執行之一比較結.果， 猎由比較二個運算元是否相担 該條件瑪值。. 4叫供該比較結果來決定 长項1G之H其進_步包括根據實施—邏輯、算 較運算的一額外指令而決定該條件碼值。 一 ^㈣之方| ’其進—步包括將該條件碼值賞施為 、值、一零後、一負數值或一溢位值之一。 14· 一種資料處理系統，其包括： 一通信匯流排；以及 里# 7G纟係、與‘通信匯流排耦合，言亥處理單元 包括： 才曰7解碼器，其用以接收並解碼指令； 執行單70，其係與該指令解碼器耦合； 八礼7擷取單元，其係與該指令解碼器耦合，該指 擷取單元包括用以儲存分支指令之分支目標的一分 支目標緩衝器； 一條件碼暫存器；以及 控制電路，其係與該指令解碼器以及該指令擷取單 元耦合， 為扣令擷取單元使用與一接收的分支指令相關聯的 刀支目標緩衝器分配說明符以決定是否分配該分支 目標緩衝器之一項目以儲存該接收的分支指令之一分 支目標。 15.如明求項14之資料處理系統，其進一步包括： 121393.doc 200813824 5己憶體，其係與該通信匯流排耦合；以及 或多個系統模組，其係與該通信匯流排耦合。 如請，項14之資料處理系統，其t該接收的分支指令係 =據猎由另-指令或該接收的分支指令的執行之一比較 結果所設定的一或多個條件碼值而決定為一取得之分支 指令。 1 7· t明求項14之資料處理系統，其中該接收的分支指令係 :钛件分支，並且該指令擷取單元並不分配該分支目 中的項目以回應該分支目標緩衝器分配說明 付0 一:求項14之請處理系統，其中該指令擷取單元接收 ;刀支扣7，亚決定在該第一分支指令係決定為取 :且於4分支目標緩衝器中產生—錯過時為該第-分支 =分配一分支目標緩衝器項目以回應用於該第一分支 才曰7的一分支目標緩衝器分配說明符，該指令擷取單元 隨後第二分支指令並在該第二分支指令㈣定為 八仔^於錢支目標緩衝器中產生-錯過時不為該第二 :支心"配一分支目標緩衝器項目以回應用於該第二 刀支扣 '的一分支目標緩衝器分配說明符。 二咕求項14之貧料處理系統，其中對於藉由該條件碼暫 存=指示的同一條件而言，該指令擷取單元在一第一分 2令#、取得且於該分支目標緩衝器中產生—錯過時為 =一分支指令分配-分支目標緩衝器項目，並在一第 ”支#取得且於該分支目標緩衝m生一錯過 121393.doc 200813824 時不為該第二分支指令分配一分支.目樣緩衝器項目。 20.如請求項14之資料處理系統，其中該條件碼暫存器根據 一指令而儲存數值，其中該指令實施一邏輯、一算術或 一比較運算之一。 121393.doc