考慮分支指令行為的迴圈排班方法

Abstract

隨著個人攜帶式應用產品的普及，數位訊號處理機的應用也隨之廣泛，且性能迅速改進，使得攜帶式的應用程式日益複雜。在數位訊號處理機中，巢狀迴圈經常佔去大部分的計算時間，所以需要探討針對巢狀迴圈中包含分支指令的排班方法。在過去已經完成的研究中，Push-Up Scheduling Method 與 Bottom Up Scheduling Method 皆是基於Retiming且可以處理巢狀迴圈的指令排班的排班方法，目的在得到最短的Schedule Length，但是不能處理分支指令。Multidimensional Branch Anticipation 可以處理含分支指令的巢狀迴圈問題但是不考慮分支指令的行為。當迴圈中的分支指令越多，分支指令的行為將會對應用程式的產能影響越大。由於分支指令的影響，迴圈中的某些指令不會被執行，所以傳統的Schedule Length無法完全反應排班結果的優劣。我們提出Expected Value of Schedule Length用來評估含有分支指令的巢狀迴圈排班結果的優劣。之後我們基於Retiming的觀念，並考慮分支指令的行為發展出Probabilistic Loop Scheduling Method (PLSM)，可以達到相當短的Expected Value of Schedule Length。最後利用實驗，可以看出 PLSM 的優勢與效果。

Multidimensional systems containing nested loop are widely used to model scientific computations such as image processing and signal processing programs. They are usually executed on VLIW DSP architecture. The instruction scheduling is an important step through the while process. However, branch instructions within loop may cause low utilization of a VLIW instruction word. The Multidimensional Branch Anticipation can get a minimum schedule length, however it can not consider the behavior of branch instructions. Because of the branch instruction, some instruction may not be executed and the schedule length can not present the performance perfectly. We will propose a method to evaluate its Expected Value of Schedule Length and show it is more closed to realistic performance than static schedule length. We also propose a retiming based scheduling method, Probabilistic Loop Scheduling Method, to get a better Expected Value of Schedule Length. The experimental results show the effectiveness of our method.