Abstract
管線式架構處理機利用同時處理多個低階計算機指令 ( 以下簡稱指令 )，以降低平均執行一個指令所需之時鐘周期數。此外，處理機工作時鐘 速率的提高，不但縮短了處理機中功能單元的回應時間，即使連傳統管線 式架構處理機亦可享有程式執行速度提升的優點。儘管如此，在管線式計 算機架構下，指令間彼此的相依性會造成管線延遲執行指令的情形，如此 不但降低了處理機的有效利用率，同時也導致了低指令分派執行率。一般 解決指令間因相依性所造成之處理機效能偏低的情形的方法可分為兩大類 ：靜態排程以及動態排程。在本論文中，我們首先針對傳統管線式計算機 架構提出一個靜態排程的演算方法，在程式編譯期間對低階計算機指令之 執行順序作排程之處理。與本論文中所參考到其它的靜態排程方法相比較 ，我們所提出的演算方法，不但可以在相同的時間複雜度之內以較低的資 源成本，減少指指令間的資料相依性和結構相依性，同時也可藉著重疊各 指令在所屬之功能單元的執行時間以縮短整個程式所需之執行時間。此外 ，我們也將針對超級純量架構之處理機，提出一個可以在程式執行期間運 作的動態排程方法。我們的方法不僅可以保有其它主要動態排程方法之優 點，同時亦可降低在實現動態排程時所需之硬體成本。經由模擬的結果顯 示，我們可以利用低硬體成本之邏輯控制電路以及在每個時鐘周期內達成 多重指令的分派執行，來達到高程式執行速度提升比，此亦導致較佳的處 理機使用率, 以及高指令分派執行率。本論文共分五章：第一章介紹本論 文的研究背景及動機；第二章回顧不同的靜態排程方法，並提出我們的靜 態排程演算方法；第三章則介紹我們所提出之動態排程方法之架構；第四 章則說明我們的模擬環境，限制條件以及所使用之計算機效能測試程式之 特性，並比較執行測試程式後的結果；第五章結論。 In the conventional pipelined architecture, dependences between the instructions not only reduce the processor utilization, but also lead to a low instruction issued rate. In this thesis, we present an algorithm for scheduling instructions over the conventional pipelined architecture at compile time. Compared with the other approaches discussed in our study, our algorithm is able to reduce data and structural dependences at a lower cost within the same time complexity. Furthermore, we propose a cost- effective approach for superscalar processors to schedule instructions at run time. Our approach not only preserves the advantages of the other dynamic scheduling approaches but also reduces the hardware complexity needed to implement the scheduling. The simulation results show that with the simplicity of hardware and multiple instructions issued per clock cycle, we can achieve a high speedup ratio, thus a better processor utilization, and instruction issued rate.