針對異質多核心系統之分析式的程序排程最佳化

在本論文中，目前廣泛流行的異質多核心系統，普遍由高效能的大核心及高效能功耗比的小核心組成。針對該系統，作者提出「最佳化演算法」以解決程序排程問題。然而，針對異質多核心系統，在目前現存的演算法中，皆為啟發式演算法，以目前公認最有效的單位週期指令數驅動演算法為例，該演算法本質上安排高加速倍率的程序至大核心上執行，試圖貪婪地最大化大核心的執行效率且最小化執行時間。然而，事實上，我們在本篇論文的分析中發現，為了達到最佳的排程，考慮安排執行時間長的程序到大核心上執行是非常重要的，而不光只考量到最大化大核心的執行效率。在組合實驗測試中，我們窮盡各種大/小核心數量的異質多核心組態，結果顯示單位週期指令數驅動演算法和我們提出的「最佳化演算法」相比，在某些測試上多出百分之三十四的執行時間成本。我們所提出的「最佳化演算法」能在O(NlogN) 的時間複雜度內找出最佳解，N 代表給定之程序總數量，因此，此演算法能夠被實際應用於系統排程中。

關鍵字

異質多核心系統；系統排程；執行序對應

並列摘要

In this thesis we propose the first optimum process scheduling algorithm for the fast becoming prevalent Heterogeneous multicore (HEMC) systems embedded with high-performance big cores and energy-efficient small cores of same instruction-set architecture (ISA). Existing algorithms are all heuristics-based and the well-known IPC-driven approach essentially tries to schedule high scaling factor processes on big cores. Our analysis shows that in fact it is also critical to consider placing long running processes on big cores for optimum solutions. Tests of SPEC 2006 cases on various big-small cores combinations show that the IPC-driven heuristic results can take up to 34% longer runtime than our optimum results. The complexity of our algorithm is O(NlogN) where N is the number of processes. Therefore the proposed optimum algorithm is practical for use.

並列關鍵字

Heterogeneous Multicore Systmes ； Scheduling ； Thread mapping

參考文獻

[1] Kumar, Rakesh, et al. "Single-ISA heterogeneous multi-core architectures: The potential for processor power reduction." Microarchitecture, 2003. MICRO-36. Proceedings. 36th Annual IEEE/ACM International Symposium on. IEEE, 2003.

[2] Kumar, Rakesh, et al. "Single-ISA heterogeneous multi-core architectures for multithreaded workload performance." ACM SIGARCH Computer Architecture News. Vol. 32. No. 2. IEEE Computer Society, 2004.

[9] Sawalha, Lina, and Ronald D. Barnes. "Energy-efficient phase-aware scheduling for heterogeneous multicore processors." Green Technologies Conference, 2012 IEEE. IEEE, 2012.

[11] Isci, Canturk, et al. "An analysis of efficient multi-core global power management policies: Maximizing performance for a given power budget." Proceedings of the 39th annual IEEE/ACM international symposium on microarchitecture. IEEE Computer Society, 2006.

[12] Teodorescu, Radu, and Josep Torrellas. "Variation-aware application scheduling and power management for chip multiprocessors." ACM SIGARCH Computer Architecture News. Vol. 36. No. 3. IEEE Computer Society, 2008.

國際替代計量

針對異質多核心系統之分析式的程序排程最佳化

全文下載

主題瀏覽