[其他]雙向轉移的預測和優化

無效

• 申請號: 86103708
• 申請日: 1986-06-02
• 公開（公告）號: CN86103708A
• 公開（公告）日: 1986-12-24
• 發明（設計）人: 李佩露;艾倫·J·鮑姆
• 申請（專利權）人: 惠普公司
• 主分類號: G06F9/30
• 分類號: G06F9/30
• 代理公司: 中國專利代理有限公司
• 代理人: 匡少波,黃向陽

對條件轉移作出決定的能力是任何計算機系統為完成有效工作的基本要求。轉移或不轉移的決定可以基于一個或一個以上的事件。這些事件，通常稱作條件，包括：正數、負數或零，最后一次算術運算的上溢、下溢或進位，偶函數或奇函數，以及很多其它事件。在數字計算機中條件轉移是由條件轉移指令來完成的。條件轉移指令可以用來構成高級程序結構，如LOOP和IF-THEN-ELSE等語句。由于LOOP和IF-THEN-ELSE這種程序結構使用得非常普遍，因此有必要使實現轉移的條件轉移指令執行得盡可能效率高。

執行一條計算機指令要由一個或一個以上的步來完成。通常，步是首先要提取程序計數器所指的指令，其次是譯碼并完成指令所標誌的運算，最后是保存結果。一個簡單的轉移指令更改著程序計數器的內容，使程序的執行“跳”到程序中的其它步。為了加速計算機指令的執行，開發了一種叫作流水線作業技術，可以同時執行一條以上的指令。譬如，流水線作業可以使中央處理器CPU提取一條指令同時執行另一條指令，并保存第三條指令的結果。在流水線計算機結構中，轉移是昂貴的作業，因為轉移指令能使流水線上的其它指令保持暫掛以等待轉移指令的結果。當在條件為真情況下執行一個條件轉移指令時，它使CPU在屬于目標地址的新地址，繼續執行。由于在流水線計算機中指令的提取是與指令的譯碼和執行同時進行的，計算機已經提取程序中跟在轉移指令后面的指令。這是一個與位于目標地址處的指令所不同的指令。因此，CPU必須隨著轉移指令來保持指令流水線直到得出轉移指令的結果和適當的指令被提取。為了達到計算機的最大能力，計算機設計者試圖使設計的計算機必須保持指令流水線減到最小以達到最大的能力。

現有技術中使用過幾種方案，使得在條件轉移時避免保持指令流水線。第一種，一些高性能處理器使用了多種轉移預測方案來猜測會不會發生條件轉移。這種方法要求大量的硬件，由于所要求的硬件太昂貴，因此除了最高性能的計算機以外，對所有的計算機都是不能采納的。第二種，另一些結構既提取程序中跟在轉移指令后面的指令，同時又提取轉移目標地址處的指令。這個方法也是不能采納的，因為它也要求昂貴的硬件以及額外的訪問內存，以便始終提取二條指令。第三種，一些結構在指令中有一個比特用來表示計算機更可能要執行的是跟在轉移后面的指令還是在轉移目標地址處的指令。然后計算機提取更為可能的指令，并且只是在猜測錯誤時才保持流水線。這種方法要求昂貴的硬件，并且如果猜測是錯誤的，要化費額外的時間恢復流水線并提取合適的指令。第四種，另一些結構允許用二個比特來指示CPU，是始終執行轉移指令后面的指令還是永不執行，這由是否發生轉移而定。這種結構使用了指令中太多的比特，因而減小了轉移指令的最大范圍。最后，還有另一些結構在轉移進行與否之前始終執行程序中跟在轉移指令后面的指令。

執行程序中跟在轉移指令后面的指令的技術稱為延時轉移。延時轉移是需要的，因為流水線中的指令是始終被執行的，并且流水線不處于保持狀態。這是因為在流水線執行指令時延時轉移，給計算機以時間來執行轉移指令并計算下一個指令的地址。雖然這種技術避免了保持指令流水線，它就要求在轉移指令之后設一無操作指令，這樣不可能改善性能，因為額外的訪問內存否定了任何改善。

一種利用延時轉移的優點的軟件技術是合併。這里所述的合併概念在于循環轉移指令處于循環套的終點。合併利用了延時轉移的優點，它復制了循環套的第一條指令，跟在循環轉移指令的后面，而把轉移目標地址作為循環套的第二條指令。合併的一個潛在問題是，在走出循環套的時候，程序不一定要再次執行跟在轉移指令后面的合併指令。對于始終使用延時轉移的結構，這是一個問題。

在許多現有技術的計算機系統確定轉移即將執行的時候，這些計算機系統使指令流水線保持或聯鎖。流水線的聯鎖包括使計算機停止提取下一個指令和防止流水線向前執行流水線中的任何指令。聯鎖降低了由于流水線所獲得的性能上的提高，因此是要避免的。

所需要的是一種條件轉移的方法，它能使硬件的數量和性能的降低減至最小。這種方法應該盡量少使用指令中的比特，因為一個比特使轉移指令的最大范圍實際上減少一半。

按照本發明的優選實施方案，在數字計算機內為條件轉移提供一種方法和設備。本發明的優選實施方案提供一條轉移指令，它根據轉移的位移來靜態地預測是否要轉移。這種方法在可能的地方采用了延時轉移，但是在延時槽指令不能有效利用的地方還可以使跟在轉移指令后的延時槽指令舍棄。