(3.238.186.43) 您好!臺灣時間:2021/03/05 22:22
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:廖育昇
研究生(外文):Yu-Sheng Liao
論文名稱:即時微核心系統之多核執行緒排程機制
論文名稱(外文):Real-Time Thread Level Load Sharing on Non-MMU Multi-Core Platforms
指導教授:施吉昇
指導教授(外文):Chi-Sheng Shih
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊網路與多媒體研究所
學門:電算機學門
學類:網路學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:英文
論文頁數:69
中文關鍵詞:管線排程異質多核心平台多核心負載共享策略負載共享負載平衡負載搬移即時排程過載狀況
外文關鍵詞:pipelined scheduleheterogeneous multi-core platformMCLSPLoad sharing/balancingWorkload migrationSoft-real timeOverload situation
相關次數:
  • 被引用被引用:0
  • 點閱點閱:158
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
異質多核心平台在嵌入式系統的領域裡面被廣泛的應用著,例如行動通訊設備或者娛樂系統等等。針對異質多核心平台的特性,許多研究人員試著將管線排程技術(pipelined schedule technology)移植到這個平台上以增進此平台的系統效能。然而,靜態的管線排程演算法以及對執行時間的估計並無法滿足系統實際執行時的需求。因此,本篇論文提出了一個多核心工作負載共享策略(MCLSP)來解決這個問題。 而在最後的效能評估結果中,我們可以證明利用這個策,系統將可有效的降低具有即時性工作的最後期限缺失率(deadline miss rate)以及有效的平衡各核心間的工作負載。
此外,本篇論文還提出了一個工作負載搬移機制(thread
migration mechanism)來實現在上述異質多核心平台中工作負載共享
的目的,此機制並解決了工作負載搬移時可能發生的資料不一致的
問題。

Heterogeneous multi-core platforms are now well accepted for designing embedded systems including mobile devices and entertainment system. Many researchers proposed to execute the computation tasks in pipelined manner so as to improve system performance. However, the assumption on worst case execution time and pre-defined schedule make it not feasible to apply pipelined scheduling on open and complex embedded systems. In this thesis, we propose a multi-core load sharing policy, MCLSP, to solve this problem. The performance evaluation results prove the proposed MCLSP could reduce deadline miss rate of real-time tasks and balance the utilization rate of the processing cores as well.

After MCLSP decides the target migration workload and the timing of load sharing, a workload migration mechanism should be applied in the system. Therefore, in this thesis, we also propose a workload migration mechanism for the heterogeneous multi-core platforms. And this mechanism can handle the data consistency problem on non-MMU multi-core architecture of this platform.

List of Figures . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . ix

Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Objective and Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Chapter 2 Background and Related Work . . . . . . . . . . . . . . . . . . . . . . 6
2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Chapter 3 Workload Model and Problem De?nition . . . . . . . . . . . . . . . 11
3.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Application Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Pipelined Schedule Workload Model . . . . . . . . . . . . . . . . . . . . . 15
3.4 Problem De?nition and Challenge . . . . . . . . . . . . . . . . . . . . . . 19
Chapter 4 Multi-Core Load Sharing Policy (MCLSP) . . . . . . . . . . . . . . . 21
4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 Core Grouping of Heterogeneous Multi-Core System . . . . . . . . . . . 22
4.3 Slack Budget for Different Runtime Scheduling Approach . . . . . . . . 23
4.4 Idea of Load Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.5 Multi-Core Load Sharing Policy (MCLSP) . . . . . . . . . . . . . . . . . . 27
4.5.1 Signal-Based Inter-Core Communication Protocol . . . . . . . . . 28
4.5.2 Migration Conditions Checking Process . . . . . . . . . . . . . . . 32
Chapter 5 Thread Migration Mechanism . . . . . . . . . . . . . . . . . . . . . . 39
5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.2 Thread Migraiton Mechanism on Non-MMU Multi-Core Platforms . . . 39
Chapter 6 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.1 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.2 Experiment Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Chapter 7 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . . . 65
7.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

[1] Texas Instruments, “Omap applications processors devices from texas instru-
ments.” at http://focus.ti.com/dsp/docs/dsphome.tsp?sectionId=
46, May 2010.
[2] Renesas Electronics Corporation, “Naviengine.” at http://www2.renesas.
com/automotive/en/assp/naviengine.html, May 2010.
[3] nVidia Corporation, “Tesla computing solutions.” at http://www.nvidia.
com/object/tesla_computing_solutions.html, May 2010.
[4] Hua Heng Technology, “Pac duo.” at http://www.hhnet.com.tw/
product-1-show.php?cat=3&no=84, May 2010.
[5] Texas Instruments, “TMS320DM6446 Digital Media System-on-Chip,” March
2007. Literature Number SPRS238E.
[6] Texas Instruments, “DVEVM Getting Started Guide,” March 2007. Literature
Number SPRUE66C.
[7] H. Rong, Z. Tang, R. Govindarajan, A. Douillet, and G. R. Gao, “Single-dimension
software pipelining for multidimensional loops,” ACMTrans. Archit. Code Optim.,
vol. 4, no. 1, p. 7, 2007.
[8] A. Douillet and G. R. Gao, “Software-pipelining on multi-core architectures,” in
PACT ’07: Proceedings of the 16th International Conference on Parallel Architecture
and Compilation Techniques, (Washington, DC, USA), pp. 39–48, IEEE Computer
Society, 2007.
[9] Yi-Sheng CHIU, Yu-Sheng LIAO, and Chi-Sheng SHIH, “Periodic pipeline sched-
ule synthesis for data dependent conditional data ?ows,” The 16th Workshop on
Compiler Techniques for High-Performance and Embedded Computing, May 2010.
[10] D. R. Steven Pope, “Virtualization and multicore x86 cpus,” 2008. Last accessed
at May 2009.
[11] S. J. Vaughan-Nichols, “New approach to virtualization is a lightweight,” Com-
puter, vol. 39, no. 11, pp. 12–14, 2006.
[12] N. Kiyanclar, G. A. Koenig, and W. Yurcik, “Maestro-vc: A paravirtualized exe-
cution environment for secure on-demand cluster computing,” Cluster Computing
and the Grid, IEEE International Symposium on, vol. 2, p. 28, 2006.
[13] NewsLab, “Multimedia embedded operating system.” at http://newslab.
csie.ntu.edu.tw/meos. Last accessed at May 2009.
[14] NewsLab, “National taiwan university embedded system and wireless netowk-
ing (news) laboratory.” at http://newslab.csie.ntu.edu.tw/. Last ac-
cessed at May 2009.
[15] J. Liedtke, “On microkernel construction,” in Proceedings of the 15th ACM Sym-
posium on Operating System Principles (SOSP-15), (Copper Mountain Resort, CO),
Dec. 1995.
[16] P. Hoang and J. Rabaey, “Scheduling of dsp programs onto multiprocessors for
maximum throughput,” Signal Processing, IEEE Transactions on, vol. 41, pp. 2225–
2235, Jun 1993.
[17] S. Bakshi and D. D. Gajski, “A scheduling and pipelining algorithm for hard-
ware/software systems,” in ISSS ’97: Proceedings of the 10th international sympo-
sium on System synthesis, (Washington, DC, USA), pp. 113–118, IEEE Computer
Society, 1997.
[18] R. Govindarajan, E. R. Altman, and G. R. Gao, “Co-scheduling hardware and soft-
ware pipelines,” High-Performance Computer Architecture, International Symposium
on, vol. 0, p. 52, 1996.
[19] J.-Y. C. Wonjong Kim and H. Cho, “Pipelined scheduling of functional hw/sw
modules for platform-based soc design,” ETRI Journal, vol. 27, no. 5, pp. 533–538,
2005.
[20] K. S. Chatha and R. Vemuri, “Hardware-software partitioning and pipelined
scheduling of transformative applications,” IEEE Trans. Very Large Scale Integr.
Syst., vol. 10, no. 3, pp. 193–208, 2002.
[21] S.-R. Kuang, C.-Y. Chen, and R.-Z. Liao, “Partitioning and pipelined scheduling of
embedded system using integer linear programming,” in Parallel and Distributed
Systems, 2005. Proceedings. 11th International Conference on, vol. 2, pp. 37–41, July
2005.
[22] Luca Abeni, Giorgio Buttazzo, Scuola Superiore, and S. Anna, “Integrating mul-
timedia applications in hard real-time systems,” Proceedings of the 19th IEEE Real-
time Systems Symposium, 1998.
[23] S. A. Brandt, S. Banachowski, C. Lin, and T. Bisson, “Dynamic integrated schedul-
ing of hard real-time, soft real-time and non-real-time processes,” RTSS ’03: Pro-
ceedings of the 24th IEEE International Real-Time Systems Symposium, 2003.
[24] R. Rajkumar, K. Juvva, A. Molano, and S. Oikawa, “Resource kernels: a resource
centric approach to real-time and multimedia systems,” 2001.
[25] Tong Li, Dan Baumberger, David A. Koufaty, and Scott Hahn, “Efcient oper-
ating system scheduling for performance-asymmetric multi-core architectures,”
Proceedings of the 2007 ACM/IEEE conference on Supercomputing, 2007.
[26] Michela Becchi and Patrick Crowley , “Dynamic thread assignment on hetero-
geneous multiprocessor architectures,” Proceedings of the Conference on Computing
Frontiers, 2006.
[27] Stefano Bertozzi, Andrea Acquaviva1, Davide Bertozzi, and Antonio Pog-
giali, “Supporting task migration in multi-processor systems-on-chip:a feasibility
study,” Proceedings of the conference on Design, automation and test in Europe, 2006.
[28] Michael Litzkow and Marvin Solomon, “Supporting checkpointing and process
migration outside the unix kernel,” Usenix Winter Conference, 1992.
[29] Yuanfang Zhang, Christopher Gill, and Chenyang Lu, “Real-time performance
and middleware for multiprocessor and multicore linux platforms,” Proceedings
of the 2009 15th IEEE International Conference on Embedded and Real-Time Computing
Systems and Applications, 2009.
[30] Shih-Jie Zhuo and Chi-Sheng SHIH, “Slack reclamation in pipelined schedule,”
2009.
[31] S. Liu and L. Gaudiot, “Synchronization mechanisms on modern multi-core ar-
chitectures,” Proceedings of the 12th Asia-Paci?c Computer Systems Architecture Con-
ference, 2007.
[32] M. A. Rivas and M. G. Harbour, “Evaluation of new posix real-time operating
systems services for small embedded platforms,” Proceedings of the 15th Euromicro
Conference on Real-Time Systems, 2003.
[33] G. Marsaglia and T. A. Bray, “A convenient method for generating normal vari-
ables,” SIAM Review, 1964.



QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔