在省電考量下之週期性硬式即時程序的多處理器系統組態

Abstract

系統省電設計在硬體或軟體的實作上已經是一個很重要的問題，而在嵌入式系統上更顯得重要。這篇論文主要是針對各種異質性的多處理器系統所做的省電研究，該如何在能源限制之下去排程週期性的即時工作。在這個問題上，每個工作都必需在一個處理器上執行，而在不 同處理器上執行會有不同的執行時間和不同的能源消耗，我們的目標要將整個系統的處理器成本降到最低，而且仍要滿足能源和時間上的限制。我們證明這個問題是一個NP-hard的問>題，除非NP等於P，否則沒有常數倍的多項式時間逼近演算法，我們對於這個問題提供了一>個 (m+2) 倍的多項式時間逼近演算法，m 是可使用處理器的種類數目，實驗結果顯示由我>們提供的演算法所得到的答案非常接近最佳解。

The energy-aware design for electronic systems has been an important issue in hardware and software implementations, especially for embedded systems. This paper targets a synthesis problem for heterogeneous multiprocessor systems to schedule a set of periodic real-time tasks under a given energy consumption constraint. Each task is required to execute on a processor without migration, where tasks might have different execution times on different processor types. Our objective is to minimize the processor cost of the entire system under the given timing and energy consumption constraints. The problem is first shown being NP-hard and having no polynomial-time algorithm with a constant approximation ratio unless NP = P. We propose polynomial-time approximation algorithms with (m+2)-approximation ratios for this challenging problem, where m is the number of the available processor types. Experimental results show that the proposed algorithms could always derive solutions with system costs close to those of optimal solutions.