- 作者: 趙玉
- 作者服務機構: 國立政治大學資訊管理學系
- 中文摘要: 尋找「單比率資料流程圖」之週期限的技術早已存在於文獻中。李等指出單比率資料流程圖太多限制,而提出經驗法則去作「多比率資料流程圖」之排程。培西建議由「多比率資料流程圖」轉換成對等之「單比率資料流程圖」以尋找週期限,且提出一個轉換的程序。為了成功轉換,他經由消除多餘的節點及線而縮短了尋找對等之「單比率資料流程圖」之週期限所需要的時問。基於此一結果,我們指出特殊案例的週期限的下界可由而實現。此外,一個單比率資料流程圖演算法可以應用於「辨別臨界迴圈」,排程範圍,初始排程去避免過度現象及位於穩定狀態中靜態的排程,而無需要去使用經驗法則。
- 英文摘要: Techniques for finding iteration bounds (IB;i.e.,minimum iteration period) of single rate data flowgraphs (SRDFG; i.e.,sampling input data at a single rate) have been well documented in the literature.Lee et al. pointed out that SRDFG is too restricted and proposed heuristics for scheduling multi-rate DFGs(MRDFG;i.e.,sampling input data at multiple rates).Parhi suggested converting an MRDFG into anequivalent SRDFG to find the IB and presented an explicit. procedure to convert an MRDFG into itsequivalent SRDFG.He reduced the time required for computing the iteration bound of the equivalentSRDFG by eliminating node and edge redundancies. Based on this result, we show that the lower boundof the iteration bound can be achieved for certain special cases. In addition, the algorithm for SRDFGcan be applied to identify critical loops (CL),scheduling ranges, initial scheduling to avoid transientsand static scheduling under steady state.There is no need for heuristics.
- 中文關鍵字: concurrent processing; Data Flow Graph(DFG); General Petri Net(GPN); Weighted T-Graph(WTG); P-semiflow; T-semiflow; liveness; boundedness; single-rate DFG; multi-ate DFG; iteration bound; loop bound; loop-combination; system performance; critical loop and scheduling
- 英文關鍵字: --