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