- 學位論文
異質性多處理器單電壓設定問題之最佳解
An Optimal Solution for the Heterogeneous Multi-processor Single-level Voltage Setup Problem
摘要
一個異質性多處理器系統(Heterogeneous Multi-processor System)是由多個異質性的處理器所構成，因為每一個處理器有不同的運算能力，使此種系統架構可以處理許多形式的應用，而被大量採用於嵌入式系統中。然而，大部分的嵌入式系統都有即時性與低耗能的要求，所以，在進行工作排程時，必須考慮每一個工作在不同處理器上的執行時間與耗能。目前大部分低耗能即時排程演算法，都假設處理器有數個固定的速度等級，且每一個等級的速度值為已知，此種假設，在工作量(Workload)為固定且已知的情況下，無法達到最佳的省電效果。因此，近來有一些研究開始討論如何根據已知的工作量，來決定處理器速度等級數目，及每一個等級的電壓(速度)，以達最佳省電效果，此類問題稱為電壓設定問題。在本研究中，我們根據已知的工作量，為每一個處理器設定一個最佳工作電壓(速度)，使系統可以在滿足即時性的要求下，達到最大的省電效果。據我們所知，本研究為文獻上第一個針對異質性多處理器系統單電壓設定問題提出最佳解，我們將該問題建模成一個非線性最佳化問題，並證明其為一個NP-Hard問題，同時，我們提出一個消去式演算法(Pruning-Based Algorithm)求得最佳解，並提出一個啟發式演算法(Heuristic Algorithm) 求得一個近似解。在實驗中，我們模擬了超過三十個商用的微處理器，並透過大規模的測試來評估我們的方法，結果顯示，我們的消去式演算法，比窮舉法至少減少98%的時間，同時，我們的啟發式演算法也比現有其他演算法可得更低的耗能。
並列摘要
A heterogeneous multi-processor (HeMP) system consists of several heterogeneous processors, each of which is specially designed to deliver the best energy-saving performance for a particular category of applications. A low power real-time scheduling algorithm is required to schedule tasks on such a system to minimize its energy consumption and complete all tasks by their deadlines. Existing works assume that processor speeds are known as a priori and cannot deliver the optimal energy-saving performance. The problem of determining the optimal voltage for each processor in order to minimize the total energy consumption is called the voltage setup problem. To the best of our knowledge, this study is the first work to propose the optimal solution for the HeMP single-level voltage setup problem. We first formulate the problem as a non-linear generalized assignment problem that has been proved to be NP-hard. We next develop a pruning-based algorithm to obtain the optimal solution. A heuristic algorithm is also proposed to derive an approximate solution. In our simulations, we model more than several dozen of off-the-shelf embedded processors including ARM and TI DSP processors. The results show that the pruning-based algorithm reduces the time usually needed for an exhaustive search to derive the optimal solution by at least 98%. Also, our heuristic algorithm achieves a minimum energy consumption in comparison with existing research.