在X86微處理機中用語意為基礎之迴圈展開機制來提昇指令平行度

Abstract

要提昇程式的執行速度，應該把所有的努力放在程式中可以獲得最大效益的部分，這是眾所皆知的事。而在程式中的迴圈結構就是代表了這個部分。因為迴圈中相同的指令會被反覆地抓取與解碼，這也導致浪費很多時間去反覆地做這些動作。 在論文中，我們提出一個以語意為基礎的迴圈展開機制，此機制可藉由分析指令的語意與收集迴圈展開所需的資訊，來達到迴圈展開的效能，進一步地，增進迴圈中指令的平行度。此機制有動態地建構與維護資料流圖的功能，而且儲存這些資料流圖在處理器中。當迴圈發生時，我們可以利用此機制去解決反覆地抓取與解碼迴圈中的指令的問題，甚至去克服檢查資料相依性的瓶頸。 我們針對我們的機制中的參數進行模擬並選定合理值，然後用此設定值跟其它微處理器的派發率作比較。模擬結果建議在效能/花費的考量下，每個指令佇列(inst-queue)有64個表格條目(entry)且每個函數骨架(function frame)有3個迴圈骨架(loop frame) 為適當的選擇。

It is well known that, to optimize the execution of a program for speedup, efforts should be focused on the regions where the payoff is the greatest. Loop structures in a program represent such regions because the instructions in a loop will be fetched from the instruction cache and then decoded repeatedly. In other words, it wastes much time for fetching and decoding the same instructions in a loop. In this thesis, we propose an approach, called semantic-based loop unrolling mechanism, which can increase ILP of loops by parsing the semantics of instructions for collecting the required information of loop unrolling. The mechanism has the functions to construct and maintain data flow graphs dynamically, and stores these graphs inside the processor. When loops occur, we can use this mechanism to solve the repeated fetching and decoding of instructions, and even to overcome the bottleneck of data dependence checking. We do the simulation to decide the parameters of our mechanism and compare the issue rate of our mechanism to that of other microprocessors. Simulation results suggest that 64-entry inst-queue and a function frame with 3 loop frames are the proper choices under performance/cost consideration.