[發明專利]推測性吞吐量計算

無效

• 申請號: 200880003160.4
• 申請日: 2008-01-30
• 公開（公告）號: CN101611380A
• 公開（公告）日: 2009-12-23
• 發明（設計）人: 亞歷山大·布斯克;米卡埃爾·恩布姆;佩爾·斯坦特斯特倫;弗雷德里克·沃格
• 申請（專利權）人: 尼瑪實驗室公司
• 主分類號: G06F9/46
• 分類號: G06F9/46;G06F9/38;G06F9/45
• 代理公司: 中原信達知識產權代理有限責任公司
• 代理人: 張煥生;安 翔

相關申請的交叉引用

[0001]本申請要求于2007年1月30日提交的題為“System，methods，and?business?ideas?for?speculative?execution?of?programsegments?in?multiprocessors”的序列號為60/897,969的美國臨時專利申請的優先權，通過引用的方式將該臨時專利申請全部合并于此。

技術領域

[0002]本主題總體上涉及吞吐量計算。

背景技術

[0003]程序(例如，計算機應用程序)可以劃分成多個程序段。例如，程序可以劃分成程序段P₁、P₂、……、P_N，其中，N是程序段的數目。常規計算系統可以以枚舉順序相繼地執行程序段。例如，單個處理器計算系統可以在執行P₂之前執行P₁、在執行P₃之前執行P₂、并且在執行P_N之前執行P_N-1。以此順序執行程序段遵守順序語義(例如，具有較高枚舉順序x的程序段在具有較低枚舉順序y的程序段向存儲器位置寫入之前從存儲器位置讀取，其中x＞y)。

[0004]例如，第一程序段可以具有枚舉順序i，且第二程序段可以具有枚舉順序j，其中i＜j。如果程序段沒有訪問相同存儲器位置，則可以在不違反順序語義的情況下并行地執行第一程序段和第二程序段。此外，如果第一程序段在第二程序段從存儲器位置讀取之后沒有向該存儲器位置寫入，則不違反順序語義。

[0005]多處理器、多核或多線程計算系統可以在多個處理器、處理器核或線程上并行地執行程序段(例如，基本上同時執行程序段)。并行地執行原來未被設計成并行執行的程序段可以被稱為“推測性執行”。

[0006]常規編譯器可以通過確定哪些程序段訪問相同存儲器位置將程序劃分成程序段。由于常規分析方法的限制，或者因為訪問的存儲器位置在編譯時是未知的，所以許多程序無法由常規編譯器來劃分以允許程序段的并行執行。

[0007]例如，一些常規分析方法在臨時存儲器位置處執行程序段的寫指令。這些常規分析方法創建與使用臨時存儲器位置相關聯的執行開銷(例如，存儲數據并從臨時存儲器位置移動數據)。其它常規分析方法使用集中式數據結構來存儲程序段的寫指令所寫入的存儲器位置的原始數據，使得可以恢復該原始數據。更新集中式結構可以造成過度開銷，尤其是在使用專用數據結構在軟件中實現寫日志的情況下。此外，如果發生推測未命中(miss-speculation)(例如，當具有枚舉順序i的程序段已向具有枚舉順序j的程序段已經讀取的位置寫入時，其中i＜j)，則具有比j更高(例如，更大)的枚舉順序的程序段停止并重做它們的執行。停止和重做執行導致可能使推測性執行效率低的執行開銷。

[0008]此外，常規分析方法的典型硬件和軟件實現使用復雜的機制并且效率低。例如，典型軟件實現造成執行開銷，因為它們使用額外的指令，并通過降低存儲器局部性(locality)而導致較差的存儲系統性能，這可以引起高速緩存未命中(cache?miss)。

[0009]一些實現監視存儲器的固定區域(例如，一個或多個連續存儲器位置的固定范圍)以跟蹤該區域是否被修改。過大的區域尺寸可能導致違反順序語義的錯誤確定。例如，如果程序段與具有較低枚舉順序的另一程序段訪問相同區域，則可以迫使該程序段停止并重做它的執行，即使沒有程序段訪問相同位置。替代地，過小的區域尺寸增加了監視讀和寫指令的開銷。

[0010]另外，常規剖析方法(例如，確定程序的屬性以根據程序的推測性執行來預測增益的程序測試執行)采用用于推測性執行的單個方法。用于推測性執行的方法還被稱為“推測性方法”或“用于推測性吞吐量計算的過程”。此外，常規依賴分析器常常不能確定是否可以并行地執行程序段。

發明內容

[0011]本發明公開了用于推測性吞吐量計算的系統、方法以及裝置。