什麼是基本塊排程？

基本塊排程是一種簡潔但效率最低的程式碼排程技術。因此，只有基本塊內的指令才能重新排序。結果，可行的加速取決於真實的資料和控制依賴性。基本塊排程器通常用於輕度和中度並行的ILP處理器，例如流水線和早期超標量處理器。

大多數用於ILP處理器的基本塊排程器都屬於列表排程器類別，例如為MIPS處理器、Sparc處理器、RS/6000、HP精密架構和DEC α 21064開發的那些排程器（Kerns和Eggers，1993，Gibbons和Muchnick，1986）。

列表排程器可用於許多上下文，包括在運籌學中排程裝配線的任務，在計算中排程多處理器的任務，排程水平微程式機器的微程式碼，或者像在這種情況下一樣，排程ILP處理器的指令。

用於基本塊排程的列表排程器

列表排程器是基於列表的，並分步驟排程專案。在每個步驟中，它首先使用選擇規則生成可用於下一個排程的專案列表，然後使用第二個規則建立下一個排程的最佳選項，如圖所示。在每個步驟中，都會排程一個或多個元素。

就用於基本塊排程的列表排程器而言，已排程的元素是指令。關於每個步驟中各種已排程的指令，流水線和超標量處理器的程式碼排程器一次交付一條已排程的指令。

**選擇規則**選擇一組可用於排程的指令。符合條件的指令是無依賴性的，也就是說，它們在DDG中沒有前驅，並且可用的硬體資源。

**選擇“最佳排程”的規則**可以檢視最有可能與後續指令產生互鎖的指令。此規則通常是啟發式方法。

大多數排程器透過在DDG中尋找關鍵執行路徑並選擇與關鍵路徑相關的特定節點進行排程來執行這些啟發式方法。但是，**“關鍵路徑”**可以用各種方法解釋，並且可以選擇基於偏好或標準。

**基於優先順序的排程器**根據所選擇的啟發式方法為每個符合條件的指令計算優先順序值。在流水線和超標量處理器基本塊列表排程器的方法中，“符合條件節點”的“優先順序值”通常隱式地表示為從正在應用的節點到基本塊末尾的一致路徑的長度。

計算所有優先順序值後，透過選擇具有最大優先順序值的節點來做出最佳選擇。當多個節點具有相同的最高優先順序值時，需要一個打破平局的規則。

相反，**基於標準的排程器**按給定的順序對要排程的專案使用一組選定的標準。“最佳選擇”是透過發現滿足最高可用排名標準的第一個專案來構建的。排程器還必須為打破平局提供額外的標準或規則。

Ginni

更新於：2021年7月20日

2K+ 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始