嵌入式多核心系統中具有動態偵測同步機制以提升效能與降低耗電之執行緒排程演算法

近年來多處理器晶片(Chip Multi-Processors, CMP)已被廣泛應用於嵌入式系統當中，透過平行處理運算以提供較高的系統效能。然而，它們的使用亦存在大量耗電的問題。為了解決此問題，嵌入式作業系統的設計者必須提供一套有效率的執行緒排程演算法，使排程器在排程的過程中不只能夠最大化系統效能，同時也能最小化電量消耗。但若是排程器在做排程的決策時沒有顧慮到執行緒之間的先後關係，其所作出的決策可能會因為違反了執行緒的真實行為而導致低效能與高耗電的排程結果。本篇論文提出了一套啟發式演算法，稱作「具有動態針測同步機制之執行緒排程演算法(Synchronization-Aware dynamic thread scheduling algorithm，簡稱SA)」，其透過降低忙碌等待的時間來達到提升效能與降低耗電的效果。SA演算法有兩個主要的目標，分別為(1)對於所有的執行緒達成高效能，即減少完成時間(Completion time)，往返時間(Turnaround time)，與忙碌等待時間(Busy-waiting time)與(2)降低排程過程中的電量消耗。實驗結果顯示SA確實比Linux作業系統的核心版本2.6排程演算法達到更高的效能與更低的電量消耗。在50個執行緒於二到八個核心的實驗中，SA最多可達到2.63倍的效能加速，同時也降低最多50.98% 的電量消耗。而在一個真實的應用程式例子中，即數位影像擷取系統(Digital Video Recording，簡稱DVR)，SA可達到至多1.21倍的效能加速與降低至多28.6% 的電量消耗。

關鍵字

效能分析；動態執行緒排程；嵌入式系統；電量消耗；同步機制

並列摘要

Nowadays, Chip Multi-Processors (CMP) are being widely used in embedded sys- tems because they provide superior performance via parallel computing. However, they also incur a significantly large power consumption. To solve this issue, de- signers of embedded operating system must provide an efficient thread scheduling algorithm, which not only maximizes the system performance, but also minimizes the energy consumption. Further, if the scheduler makes decisions without considering the precedence relationships among threads, the decisions could conflict with the thread behavior which could result in poor performance and large energy consumption. In this Thesis, we propose a Synchronization-Aware Dynamic Thread Scheduling Algorithm (SA), which reduces the busy-waiting time caused by spinlock, and with performance improvement and energy saving. SA has two major objectives, including (1) overall high performance, in terms of less completion time, less turnaround time, less busy-waiting time, and (2) low energy consumption for all threads. The experimental results show that SA indeed improves at most performance and reduces energy consumption compared to the original scheduling algorithm in the Linux kernel version 2.6. The speedup of SA is at most 2.63 for 50 threads running on two to wight cores, and it can also saves the energy consumption by at most 50.98%. In the real-world case, that is, the Digital Video Recording (DVR) system, SA achieves at most 1.21 speedup and saves the energy consumption by at most 28.6%.

並列關鍵字

energy consumption ； performance analysis ； dynamic thread scheduling ； embedded systems ； synchronization

參考文獻

[2] I. Ahmad, S. Ranka, and S.U. Khan. Using Game Theory for Scheduling Tasks on Multi-Core Processors for Simultaneous Optimization of Performance and Energy. In Proceedings of the IEEE International Symposium on Parallel and

[7] A. Archer and E. Tardos. Truthful Mechanisms for One-Parameter Agents. In Proceedings of the IEEE Symposium on Foundations of Computer Science, pages 482–491, October 2001.

[9] L. Benini, A. Bogliolo, and G. DeMicheli. A Survey of Design Techniques for System-Level Dynamic Power Management. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 8:299–316, June 2000.

[11] W. Fernandez de la Vega and G.S. Lueker. Bin Packing Can be Solved within 1 + " in Linear Time. Combinatorica, 1(4):349–355, May 1981.

[12] G.K. Dorai and D. Yeung. Transparent Threads: Resource Sharing in SMT Processors for High Single-Thread Performance. International Conference on Parallel Architectures and Compilation Techniques, 0:30, September 2002.

國際替代計量

嵌入式多核心系統中具有動態偵測同步機制以提升效能與降低耗電之執行緒排程演算法

未授權

主題瀏覽