DHC系統之任務指派與排程的新型基因演算法

Abstract

分散式異質計算系統(distributed heterogeneous computing, DHC)是一個將大型應用程式解構成多個子程式分別計算的架構，異質是指計算機器種類不同，分散是指機器的位置不同，因此互通的資料需要傳輸時間。DHC系統有兩個重要的決策：指派(matching)、排程(scheduling)。指派決策是決定將子程式分給哪一個機器執行，排程決策是訂定子程式的執行優序。指派與排程決策的解空間很大，過去多用基因演算法來求解。本研究提出一個新的基因演算法，此演算法產生新染色體是採用本研究所獨創的共識因子(consensus operator)，共識因子是一個導引(guided)機制，可據以產生品質好的染色體，因而加速基因演算法的求解品質和時間。實驗結果顯示，在求解DHC的指派與排程決策，此新的基因演算法，求解品質和求解時間都較過去的基因演算法為佳。

A DHC (distributed heterogeneous computing) system is a computing architecture, where computing machines are heterogeneous, located sparsely and thereby need data transfer among them. A large-scale application problem can be executed on a DHC by decomposing the program into several sub-programs. This needs to make two decisions—matching and scheduling. The matching decision assigns a machine for executing each subprogram, while the scheduling decision prioritizes the execution of subprograms. The matching and scheduling problem in DHC has a huge solution space. Various genetic algorithms have been proposed to solve the problem. This research proposes a novel genetic algorithm (GA), which is distinguished in generating new chromosomes by a so-called consensus operator developed by us—a mechanism that attempts to efficiently generate quality chromosomes. Experiment results indicate that the proposed GA, while solving the DHC matching and scheduling problem, outperforms the prior GAs both in solution quality and time.