周知編譯原理龍書闡述的基本塊指令調度算法，它所使用的空的資源預約表RTD與每個指令的資源預約表RT，可以看作二維矩陣，行表示時鐘周期、列表示cpu資源，其定位的元素值1表示占用/預約，0表示空閑/非預約。前者是隨周期遞增而動態擴大的矩陣，后者是固定尺寸(維數)的矩陣（指令花費周期與每周期預約資源皆已知）。在調度時，按帶優先級比如關鍵路徑的拓撲排序基本塊內的指令，順序選取一條指令Inst，計算每前驅發射周期加延遲的結果tmp，取所有tmp的最大值tmax作為Inst的發射周期，再判斷處理器資源是否可用，即RTD和RT作
與運算，得到一個新矩陣RTN，若RTN為
全零矩陣則tmax為Inst的最終發射周期，否則遞增tmax再做矩陣與運算，直至得到全零矩陣。最后更新RTD，即RTD與RT作
或運算結果存于RTD。重復上述過程直到基本塊末尾。
綜上不難看出，如果一個基本塊很大比如有1000條指令，平均每指令花2個周期，則RTD需要2000個條目，若一條目即矩陣每行占用32字節（256種資源數），則總量約64k。當然這對于現代內存體量來說不算什么，但可以有更好的節省內存的做法：RTD尺寸其實可以相對固定，其上限為基本塊中耗費周期最多指令的周期的一個大于1常數因子倍（為兼顧指令并行性），這樣一來就要增加當指令完成時（當前指令發射周期大于前一條的終止周期時復位前一條指令的RTD）從發射周期處復位RTD即作一個矩陣反運算的操作，其它步驟對應的矩陣與、矩陣或運算的操作保留不變。另由于RTD固定了尺寸，因此發射周期遞增后要取模
【備注】以上是我針對簡單機器模型（每種資源數量僅一個，比如整數運算單元1個，內存訪問單元1個，浮點運算單元1個）用布爾矩陣作的優化。如果是復雜的超標量機器即每種資源數有多個，那么只需修改如下：布爾矩陣換成整數矩陣；新增一個機器資源可用總數整數矩陣RDA（單列資源數同值），布爾矩陣與運算換成加法并與RDA比較，若大于RDA則遞增tmax；布爾矩陣或運算換成加法；布爾矩陣反運算換成減法，RTD減RT存于RTD
posted on 2023-09-23 12:14
春秋十二月 閱讀(365)
評論(0) 編輯 收藏 引用 所屬分類:
Compiler