基於基因演算法應用於異質性網路單晶片系統之快速任務排程方法

Abstract

網路單晶片是為了應付未來極為複雜的系統單晶片的通訊需求所提出的一種新的設計方式。在這篇論文中，我們提出一個基於基因演算法的任務排程方法，把應用排程至一個異質性網路單晶片。這個任務排程方法試著去為每一個任務找到最適合的處理器，使得系統的資料處理率提升至最大。在基因演算法中，隨著任務數目的增加，排程所需的時間也會跟著增加，而且在資料處理率的表現也會變差。所以我們提出分割的基因演算法來改良這樣的狀況。實驗結果顯示，我們提出的演算法可以有效提升基因演算法的效能，而且排程時間上也有明顯的改良。

Network-on-Chip is a new design paradigm to meet the communication requirement of future billion-transistor System-on-Chip. In this thesis, we propose a genetic algorithm based task scheduling technique to schedule the applications to the heterogeneous Network-on-Chip architecture. The task scheduling process attempts to arrange the allocation of processor for each task such that the system throughput is maximized. In genetic algorithm, with the increasing of task number, the scheduling time will increase, and the performance in system throughput will become worse. So we propose a partition genetic algorithm to improve this kind of situation. The experimental results show that proposed algorithm not only upgrade the performance of genetic algorithm, but also shorten the scheduling time obviously.