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