研究生: |
白俊德 Cheng-Te Bai |
---|---|
論文名稱: |
異質雙核心即時排程器之實作與分析 Implementation and Comparison of Real-time Schedulers on a Heterogeneous Dual-core System-on-chip |
指導教授: |
陳雅淑
Ya-Shu Chen |
口試委員: |
張立平
Li-Pin Chang 謝仁偉 Jen-Wei Hsieh 吳晉賢 Chin-Hsien Wu |
學位類別: |
碩士 Master |
系所名稱: |
電資學院 - 電機工程系 Department of Electrical Engineering |
論文出版年: | 2011 |
畢業學年度: | 99 |
語文別: | 中文 |
論文頁數: | 63 |
中文關鍵詞: | 異質多核心處理器 、排程器 、即時系統 |
外文關鍵詞: | Heterogeneous multi-core processor, scheduler, real-time system |
相關次數: | 點閱:1066 下載:4 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
在異質雙核心的嵌入式系統中, 行程交錯執行在汎用型處理器及特殊型處理器, 造成
(1) 子行程具有優先順序限制(2) 特殊型處理器的子行程為不可搶先式排程。此兩項特徵
大幅提高排程困難度。有別於以往的研究, 本研究將探討與分析異質雙核心處理器架構中,
如何評估排程器的實作成本, 如何以最低成本於核心間交換資料, 並探討行程的即時需求
與執行時間評估之技術問題。我們於Micrium uC/OS-II實現靜態與動態排程演算法, 以及
資源管理協定, 並將作業系統移植到異質雙核心的系統晶片(TI Davinci dm6446) 上, 增
加核心溝通模組, 使行程於雙處理器間進行溝通, 且於特殊型處理器中加入可搶先點概念
減少高優先權行程被阻擋時間。最後, 利用Motion JPEG的解碼實驗, 評估即時排程演算
法的可排程性, 以及執行時間量測之技術方法。
In heterogeneous dual-core embedded systems, subtasks of a task is executed interleaving
between a general purpose processor and a specific purpose processor, which
make (1) subtasks have precedence constraints, and (2) the subtask execution on a specific
purpose processor is non-preemptive. These two characters highly increase the difficulty
of scheduling problem. With a very different goal, this research presents the way to evaluate
the implementation cost of a scheduler and to exchange data with low cost between
cores on the heterogeneous dual-core processor architecture.
We implement resource synchronization protocols and static/dynamic priority scheduling
algorithms onMicrium uC/OS-II, and then port the uC/OS-II to a heterogeneous dualcore
System-on-Chip (TI Davinci DM6446). Tasks can communication with each other
between the two cores via the implemented inter-processor communication module. Furthermore,
we reduce blocking time of the high priority task by inserting preemption points
into tasks. Finally, we study the Motion JPEG decoder to evaluate the schedulability of
real-time scheduling algorithms, and to show the method of execution time measurement.
[1] Qualcomm. http://www.qualcomm.com/.
[2] T. P. Baker. A comparison of global and partitioned edf schedulability tests for
multiprocessors. Technical report, In International Conf. on Real-Time and Network
Systems, 2005.
[3] R. Bettati and J. Liu. Algorithms for end-to-end scheduling to meet deadlines. In
Parallel and Distributed Processing, 1990. Proceedings of the Second IEEE Symposium
on, pages 62 –67, Dec. 1990.
[4] R. Bettati and J.-S. Liu. End-to-end scheduling to meet deadlines in distributed
systems. In Distributed Computing Systems, 1992., Proceedings of the 12th International
Conference on, pages 452 –459, June 1992.
[5] J. M. Calandrino, D. Baumberger, T. Li, S. Hahn, and J. H. Anderson. Soft realtime
scheduling on performance asymmetric multicore platforms. In Proceedings of
the 13th IEEE Real Time and Embedded Technology and Applications Symposium,
pages 101–112. IEEE Computer Society, 2007.
[6] Y.-S. Chen, L.-P. Chang, and C.-M. Cheng. On-line task scheduling for dual-core
real-time embedded systems. In Industrial Informatics, 2009. INDIN 2009. 7th IEEE
International Conference on, pages 182 –187, 2009.
[7] Z. Deng, J.-S. Liu, and J. Sun. A scheme for scheduling hard real-time applications
in open system environment. In Real-Time Systems, 1997. Proceedings., Ninth
Euromicro Workshop on, pages 191 –199, June 1997.
[8] J. Eyre and J. Bier. The evolution of dsp processors. Signal Processing Magazine,
IEEE, 17(2):43–51, Mar 2000.
[9] H. Francis. Arm dsp-enhanced extensions. Technical report, ARM Ltd., May 2001.
ARM white paper.
[10] P. Gai, L. Abeni, and G. Buttazzo. Multiprocessor dsp scheduling in system-on-achip
architectures. Real-Time Systems, Euromicro Conference on, 0:231, 2002.
[11] J. Gustafsson and A. Ermedahl. Experiences from applying wcet analysis in industrial
settings. Object-Oriented Real-Time Distributed Computing, IEEE International
Symposium on, 0:382–392, 2007.
[12] L. Hammond, B. Nayfeb, and K. Olukotun. A single-chip multiprocessor. Computer,
30(9):79–85, 1997.
[13] J. D. D. G. J.M. L, M. G. Worst-case utilization bound for edf scheduling on realtime
multiprocessor systems. Real-Time Systems, Euromicro Conference on, 0:25,
2000.
[14] B. Kao and H. Garcia-Molina. Subtask deadline assignment for complex distributed
soft real-time tasks. In Distributed Computing Systems, 1994., Proceedings of the
14th International Conference on, pages 172 –181, June 1994.
[15] B. Kao and H. Garcia-Molina. Deadline assignment in a distributed soft real-time
system. IEEE Transactions on Parallel and Distributed Systems, 8:1268–1274,
1997.
[16] K. Kim, D. Kim, and C. Park. Real-time scheduling in heterogeneous dual-core
architectures. Parallel and Distributed Systems, International Conference on, 2:91–
96, 2006.
[17] C.-F. Kuo and Y.-C. Hai. Real-time task scheduling on heterogeneous two-processor
systems. Algorithms and Architectures for Parallel Processing, pages 68–78, 2010.
[18] C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in a
hard-real-time environment. J. ACM, 20:46–61, January 1973.
[19] G. McNutt and T. Fischer. Using linux to control dsp processes in mixed-processor
systems. October 2001.
[20] R. Oshana. DSP Software Development Techniques for Embedded and Real-Time
System. Newnes, 2006.
[21] Philip. Home Entertainment Engine Nexperia pnx8500, October 2000.
[22] R. M. Ramanathan. Intel multi-core processow white paper. Technical report,
http://www.intel.com/technology/architecture/downloads/quad-core-06.pdf, 2006.
[23] S. Saewong and R. Rajkumar. Cooperative scheduling of multiple resources. In
Real-Time Systems Symposium, 1999. Proceedings. The 20th IEEE, pages 90 –101,
1999.
[24] L. Sha, R. Rajkumar, and J. Lehoczky. Priority inheritance protocols: An approach
to real-time synchronization. IEEE Transactions on Computers, 39:1175–1185,
1990.
[25] S. Shee, A. Erdos, and S. Paraeswarant. Heterogeneous multiprocessor implementations
for jpeg: a case study. In CODES and ISSS ’06. Proceedings of the 4th
International Conference, Oct 2006.
[26] D. Shelepov, J. C. Saez Alcaide, S. Jeffery, A. Fedorova, N. Perez, Z. F. Huang,
S. Blagodurov, and V. Kumar. Hass: a scheduler for heterogeneous multicore systems.
SIGOPS Oper. Syst. Rev., 43:66–75, April 2009.
[27] Spectrum Digital. DaVinci-DM644x Evaluation Module Technical Reference,
March 2007.
[28] Texas Instruments. DVEVM Getting Started Guide, March 2007.
[29] Texas Instruments. TMS320C64x/c64x+ DSP CPU and Instruction Set Reference
Guide, Oct 2008.
[30] Texas Instruments. TMS320DM6446 Digital Media System-on-Chip, March 2008.
[31] Texas Instruments. OMAP3530/25 Applications Processor, October 2009.
[32] B. TP. A stack-based resource allocation policy for real-time process. In: IEEE 11th
real-time system symposium, 1990.
[33] T. Trawick. Multicore communication: today and the future. Embedded Computing
Design, 2007.
[34] K.Williston. Microprocessors vs. dsps. Technical report, Berkeley Design Technology,
Inc, 2006.
[35] O. U. P. Zapata and P.M. Alvarez. Edf and rm multiprocessor scheduling algorithms:
Survey and performance evaluation, 2004.