管線內加入延遲元件之研究

Abstract

在這篇論文中，我們針對管線執行中如何達到最佳效能作了一系列的 研究。一個工作一旦進入管線中執行，會按照資源的需求一步一步地做下 去。當有兩個以上的工作欲在相同時間使用同一個資源時，即會發生所謂 的衝突現象。使用傳統的方法如用移位暫存器或簡化狀態圖等都可以避免 發生衝突，但有時卻不能達到最佳效能。然而我們可藉由加入延遲元件來 達成。在本文中我們將就一些加入延遲元件以避免發生衝突的方法做介紹 ，並對這些方法進行一些改進與程式撰寫以作比較。我們利用一啟發式方 法所得到的近似結果，於branch and bound方法中以求得最佳解，如此大 大地減少產生的節點數進而減少執行時間。而對另一方法，我們擴充其單 一函數形式之管線擴充至多重函數形式之管線。同時，我們也推導出延遲 最少化之整數線性規劃。 In this thesis, we study some techniques for achieving maximum performance in pipelines. A task once initiated into a pipeline, flows from segment to segment for its execution. A collision occurs if two or more tasks attemptto use the same segment at the same time. Traditional methods like usingshift register or reduced state diagrams can avoid collisions, but they can not achieve maximum performance sometimes. By adding delays within thepipeline, it is always possible to attain maximum performance. We will describe some methods that can solve this problem. These methods areimproved and implemented. We use an approximate solution obtained by aheuristic algorithm as a bounding function in the Branch and Bound algorithmto find the optimal solution. It can drastically reduce execution time by reducing the number of generated nodes. By experiments, we will show the effects of changing bounds. For another method, we extend the applicationdomain from a single- function pipeline to a multi-function pipeline. In addition, we formulate an integer linear program to find the optimal solution.