在即時的多處理器SOC系統中考慮以基因的工作排程法來達到電量的最佳使用

Abstract

隨著深次微米技術快速的進展和個人攜帶式應用產品的普及，多處理器System-on-Chip(SOC)的架構將會是未來趨勢。因此，如何減少電量的消耗和資料的即時性成了一個重要的課題。而工作的排程在整個過程中是一個很關鍵的步驟。在本論文中，我們以基因演算法為基礎在不違反時間限制的狀況下找出消耗最少電量的工作排程。然而基因演算法需要大量的計算時間，因此我們在基因演算法上加入一些限制來建構我們的Constrained Genetic Method。除此之外，我們還應用了Divided-and-Conquer的技巧將整個工作流程，切成數個小流程使得Constrained Genetic Method可以單獨的處理這些被分割的工作流程以達到減少計算時間的效果。但是這樣的步驟卻會增加電量的消耗，因此我們在合併這些小的工作流程後，將會使用Power Minimization Method來減少合併後的電量消耗。我們會在接下來的本文中介紹我們演算法的詳細內容。

With the rapid evolution of submicron technology and the popularization of portable devices, embedded multiprocessor System-On-Chip (SOC) architecture will be one of the most attractive trends. How to decrease power consumption and process data in real-time is one of the most interesting topics to be investigated. The task scheduling is an important step through the whole process. In this thesis, we schedule tasks to obtain the minimal power consumption under time constraint, which is based on Genetic Algorithm. However, Genetic Algorithm needs huge computation time and therefore we propose an effective algorithm, named Constrained Genetic Method (CGM), by adding some constraints to Genetic Algorithm. Moreover, we partition the whole tasks graphs into several subgraphs to decrease computation time. But the total power consumption will increase after mergence process. Thus, we proposed a Power Minimization Method to decrease the total power consumption. The detail descriptions of our algorithm will be given in the contents.