跳到主要內容

臺灣博碩士論文加值系統

(44.222.189.51) 您好!臺灣時間:2024/05/24 17:58
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:洪旭嘉
研究生(外文):HONG, XU-JIA
論文名稱:應用在多核心處理器環境的即時工作之切割方法與節能效益驗證
論文名稱(外文):Performance Evaluation of Task Partition and Energy-Efficient Scheduling Algorithm for Multicore Real-Time Systems
指導教授:吳卓俊
指導教授(外文):WU, JUN
口試委員:莊作彬郭錦福
口試委員(外文):JUANG, TSO-BINGKUO, CHIN-FU
口試日期:2017-06-06
學位類別:碩士
校院名稱:國立屏東大學
系所名稱:資訊工程學系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2017
畢業學年度:105
語文別:英文
論文頁數:48
中文關鍵詞:即時系統動態電壓調整即時工作排程共享資源同步控制多核心處理器
外文關鍵詞:Multi-core processorReal-Time SystemDynamic Voltage/Frequency ScalingTask SchedulingTask Synchronization
相關次數:
  • 被引用被引用:0
  • 點閱點閱:182
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
近年來,學者們針對多核心平台提出了許多相關節能的即時工作排程演算法。然而, 大多數的節能方法主要都是針對獨立性的工作,反觀針對工作同步情況的研究成果相 對較少。本論文主要關注在即時工作的節能排程,而這些工作可能在執行過程中需要 存取共享資源。我們提出了一個以相似度為基礎的工作分割演算法稱為Similarity-Based Partitioning(SBP),其方法主要是將存取共享資源相似性高的工作盡量分配給同一顆核 心,避免產生大量的遠端阻擋,進而達到節能效益。此外,我們也提出了一個速度調節方 法,其方法針對工作在full-chip與per-core兩種DVFS處理器上,在保證工作可排程性的前 提下,以適當的處理器速度執行,進而減少能源消耗。最後我們透過一系列的實驗來驗證 我們方法的可排程性分析及效能驗證。
In the recent years, many energy-efficient real-time task scheduling algorithms have been proposed for multi-core platforms. Most of them focus on independent tasks, however, relatively little work has been done in the presence of task synchronization. In this thesis, we are interested in scheduling of real-time tasks which may make requests for accessing shared resources at the run time. A similarity-based task-to-core partitioning algorithm is proposed to allocate the tasks which may access a similar set of shared resources to the same core so that a large number of blockings can be avoided. Furthermore, we also propose speed assignment methods to assign proper processor speed for tasks’ executions with full-chip and per-core DVFS techniques so that the energy consumption can be reduced. The schedulability analysis and the properties of our proposed approach are provided in this thesis. The capabilities of our proposed approach were evaluated by a series of experiments for which we have some encouraging results.
Acknowledgements i

摘要 ii

Abstract iii

Contents iv

List of Figures vi

List of Tables vii

1 Introduction 1
1.1 Background...................................... 1
1.2 Motivation....................................... 3
1.3 Objectives....................................... 4
1.4 Methodology ..................................... 5
1.5 Contributions ..................................... 5
1.6 Organization...................................... 6

2 Related Work 7

3 System Model and Problem Definitions 10
3.1 SystemModel..................................... 10
3.1.1 Multi-coreDVFSProcessors......................... 10
3.1.2 TaskandResourceModels.......................... 11
3.2 ProblemDefinitions.................................. 12

4 Our Approach 14
4.1 TaskScheduling.................................... 14
4.2 Similarity-BasedPartitioning(SBP)Algorithm . . . . . . . . . . . . . . . . . . . 15
4.3 TaskSynchronization................................. 22
4.4 SchedulabilityAnalysis................................ 25
4.5 SpeedAssignment .................................. 28

5 Performance Evaluation 30

6 Conclusion 38

Bibliography 39
[1] C. L. Liu and J. W. Layland, “Scheduling algorithms for multiprogramming in a hard real- time environment,” Journal of the Association for Computing Machinery (JACM), vol. 20, pp. 46–61, January 1973.

[2] L. Sha, R. Rajkumar, and J. P. Lehoczky, “Priority inheritance protocols: An approach to real-time synchronization,” IEEE Transactions on Computers (TC), vol. 39, pp. 1175–1185, Sepember 1990.

[3] T.P.Baker,“Astack-basedresourceallocationpolicyforreal-timeprocesses,”inProceedings of the IEEE 11th Real-Time Systems Symposium (RTSS), (Lake Buena Vista, Florida, USA), pp. 191–200, December 4-7 1990.

[4] J.-J. Chen and T.-W. Kuo, “Procrastination determination for periodic real-time tasks in leakage-aware dynamic voltage scaling systems,” in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pp. 284–294, November 2007.

[5] T. A. Alenawy and H. Aydin, “Energy-aware task allocation for rate monotonic scheduling,” in Proceedings of the 11th IEEE Real-time and Embedded Technology and Applications Symposium (RTAS 2005), pp. 213–223, 2005.

[6] H. Aydin and Q. Yang, “Energy-Aware Partitioning for Multiprocessor Real-Time Systems,” in Proceedings of the 17th International Symposium on Parallel and Distributed Processing (IPDPS 2003), pp. 113–121, April 2003.

[7] B. Andersson and E. Tovar, “Competitive analysis of partitioned scheduling on uniform multiprocessors,” in Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1–8, March 2007.

[8] J.-J. Chen, H.-R. Hsu, and T.-W. Kuo, “Leakage-aware energy-efficient scheduling of real- time tasks in multiprocessor systems,” in Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pp. 408–417, April 2006.

[9] J.-J.Chen,H.-R.Hsu,andT.-W.Kuo,“Energy-efficient scheduling of periodic real-time tasks over homogeneous multiprocessors,” in Proceedings of the 2nd Intl. Workshop on Power-Aware Real-Time Computing (PARC), pp. 30–35, 2005.

[10] J. H. Anderson and S. K. Baruah, “Energy-efficient synthesis of periodic task systems upon identical multiprocessor platforms,” in Proceedings of the 24th IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 428–435, 2004.

[11] D. Zhu, R. Melhem, and B. Childers, “Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor real-time systems,” in Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS), pp. 84–94, December 2001.

[12] J.-J. Chen, C.-Y. Yang, and T.-W. Kuo, “Slack reclamation for real-time task scheduling over dynamic voltage scaling multiprocessors,” in Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trust-worthy Computing (SUTC), pp. 358– 367, June 2006.

[13] J. Liu and J. Guo, “Voltage island aware energy efficient scheduling of real-time tasks on multi-core processors,” in Proceedings of the 11th IEEE International Conference on Embedded Software and Systems (ICESS), pp. 645–652, August 2014.

[14] C.-F. Kuo, “Energy-efficient scheduling for periodic tasks on uniform multiprocessors,” in
Proceedings of the 12th IEEE International Conference on Embedded Computing (EmbeddedCom), 2014.

[15] T. P. Baker, “A comparison of global and partitioned edf schedulability tests for multiprocessors,” Tech. Rep. TR-051101, Department of Computer Science, Florida State University, 2005.

[16] P. Gai, G. Lipari, and M. D. Natale, “Minimizing memory utilization of real-time task sets in single and multi-processor systems-on-a-chip,” in Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS), pp. 73–83, December 2001.

[17] J. Wu and Y.-C. Huang, “MCRTsim: A Simulation Tool for Multi-Core Real-Time Systems,” in Proceedings of the 2017 IEEE International Conference on Applied System and Innovation (IEEE ICASI 2017), 2017.

[18] J.-J. Chen and C.-F. Kuo, “Energy-efficient scheduling for real-time systems on dynamic voltage scheduling (dvs) platforms,” in Proceedings of the 13th IEEE Embedded and Real-Time Computing Systems and Applications (RTCSA 2007), pp. 28–38, August 2007.

[19] S. Zhuravlev, J. C. Saez, S. Blagodurov, A. Fedorova, and M. Prieto, “Survey of energy-cognizant scheduling techniques,” IEEE Transactions on Parallel and Distributed Systems (TPDS), vol. 24, no. 7, pp. 1447–1464, 2013.

[20] F.Yao,A.Demers,andS.Shenker,“Aschedulingmodelforreducedcpuenergy,”in Proceedings of the 36th IEEE Annual Symposium on Foundations of Computer Science (FOCS’95), pp. 374–382, October 1995.

[21] G. Quan and X. Hu, “Minimum energy fixed-priority scheduling for variable voltage processor,” in Proceedings of the IEEE Design Automation and Test in Europe Conference and Exhibition (DATE), pp. 782–787, 2002.

[22] H.-S. Yun and J. Kim, “On energy-optimal voltage scheduling for fixed-priority hard real- time systems,” ACM Transactions on Embedded Computing Systems (TECS), vol. 2, pp. 393– 430, August 2003.

[23] M. Li and F. Yao, “An efficient algorithm for computing optimal discrete voltage schedules,” SIAM Journal on Computing, vol. 35, no. 3, pp. 658–671, 2005.

[24] H. Aydin, R. Melhem, D. Mosse ́, and P. Mej ́ıa-Alvarez, “Determining optimal processor speeds for periodic real-time tasks with different power characteristics,” in Proceedings of the 13th IEEE EuroMicro Conference on Real-Time Systems (ECRTS), pp. 225–232, 2001.

[25] H. Aydin, R. Melhem, D. Mosse ́, and P. Mej ́ıa-Alvarez, “Dynamic and aggressive scheduling techniques for power-aware real-time systems,” in Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS 2001), pp. 95–105, December 2001.

[26] P. Mej ́ıa-Alvarez, E. Levner, and D. Mosse ́, “Adaptive scheduling server for power-aware real-time tasks,” ACM Transactions on Embedded Computing Systems (TECS), vol. 3, no. 2, pp. 284–306, 2004.

[27] J.-J.Chen,T.-W.Kuo,andC.-S.Shih,“1+ǫapproximationclockrateassignmentforperiodic real-time tasks on a voltage-scaling processor,” in Proceedings of the 5th ACM International conference on Embedded Software (EMSOFT), pp. 247–250, 2005.

[28] S. Saewong and R. Rajkumar, “Practical voltage-scaling for fixed-priority-systems,” in Pro- ceedings of the 9th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pp. 106–114, May 2003.

[29] F. Zhang and S. T. Chanson, “Blocking-aware processor voltage scheduling for real-time tasks,” ACM Transactions on Embedded Computing Systems (TECS), vol. 3, pp. 307–335, May 2004.

[30] J. Lee, K. Koh, and C.-g. Lee, “Multi-Speed DVS Algorithms for Periodic Tasks with Non-Preemptible Sections,” in Proceedings of the 13th IEEE Embedded and Real-Time Computing Systems and Applications (RTCSA 2007), pp. 459–468, August 2007.

[31] A.M.Elewi,M.H.A.Awadalla,andM.I.Eladawy,“Energy-efficientmulti-speedalgorithm for scheduling dependent real-time tasks,” in Proceedings of the 2008 IEEE International Conference on Communication and Electronics Systems (ICCES), (Cairo, Egypt), pp. 237– 242, November 2008.

[32] R. Jejurikar and R. Gupta, “Energy aware task scheduling with task synchronization for embedded real time systems,” IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, vol. 25, no. 6, pp. 1024–1037, 2006.

[33] J. Wu, “Energy-efficient scheduling of real-time tasks with shared resources,” Future Generation Computer Systems, vol. 56, pp. 179–191, 2016.

[34] J. Wu, “Energy-efficient scheduling of real-time tasks with shared resources,” International Journal of Computer Systems Science and Engineering, vol. 3, pp. 239–253, 2016.

[35] R. Jejurikar and R. K. Gupta, “Energy aware task scheduling with task synchronization for embedded real-time systems,” Tech. Rep. 02-12, Center for Embedded Computer Systems, Department of Information and Computer Science, University of California at Irvine, June 21 2002.

[36] R. Jejurikar and R. K. Gupta, “Energy aware EDF scheduling with task synchronization for embedded real-time operating systems,” Tech. Rep. 02-24, University of California at Irvine, August 2002.

[37] Chen and Lin, “Dynamic priority ceilings: A concurrency control protocol for real-time systems,” Tech. Rep. UIUCDCS-R-89-1511, Department of Computer Science, University of Illinois at Urbana-Champaign, 1989.

[38] R. Jejurikar, C. Pereira, and R. K. Gupta, “Dual-mode frequency inheritance algorithm for energy aware task scheduling with task synchronization,” Tech. Rep. 03-07, University of California at Irvine, Feburary 28 2003.

[39] Y.-S. Chen, C.-Y. Yang, and T.-W. Kuo, “Fl-pcp: Frequency locking for energy-efficient real-time task synchronization,” in Proceedings of the 13th IEEE Embedded and Real-Time Computing Systems and Applications (RTCSA 2007), (Daegu), pp. 451–458, August 2007.

[40] Y.-S. Chen and T.-J. Lin, “Voltage Emergence Prevention for Energy-Efficient Real-Time Task Synchronization,” in Proceedings of the 8th IEEE International Conference on Computer and Information Technology Workshops (ICCIT), pp. 545–550, July 2008.

[41] Y.-S. Chen, C.-Y. Yang, and T.-W. Kuo, “Energy-efficient task synchronization for real-time systems,” IEEE Transactions on Industrial Informatics, vol. 6, pp. 287–301, August 2010.

[42] J. Wu, “Dual mode algorithm for energy aware fixed priority scheduling with task synchronization,” in Proceedings of the WIP session of the 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), 2011.

[43] J. Wu, “BATS : An Energy-Efficient Approach to Real-Time Scheduling and Synchronization,” in Proceeding of the 11th IEEE Internatioinal Conference on Embedded Software and Systems (ICESS), (Paris, France), pp. 669–676, August 2014.

[44] F. Zhang and S. T. Chanson, “Processor voltage scheduling for real-time tasks with non-preemptible sections.,” in Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS’02), pp. 235–245, 2002.

[45] A.M.Elewi,M.H.A.Awadalla,andM.I.Eladawy,“Energy efficient real-time scheduling of dependent tasks sharing resources,” in Proceedings of the 2008 High Performance Computing and Simulation Conference (HPCS), (Nicosia, Cyprus), pp. 107–116, June 3-6 2008.

[46] J. Wu and J.-X. Wu, “An srp-based energy-efficient scheduling algorithm for dependent real- time tasks,” International Journal of Embedded Systems, vol. 6, no. 4, pp. 335–350, 2014.

[47] F. Gruian, “System-level design methods for low-energy architectures containing variable voltage processors,” in Proceedings of the Power-Aware Computing Systems Workshop at Architectural Support for Programming Languages and Operating Systems (ASPLOS), pp. 1– 12, November 2000.

[48] D. Zhu, N. AbouGhazaleh, D. Mosse, and R. Melhem, “Power aware scheduling for and/or graphs in multi-processor real-time systems,” in Proceedings of the IEEE International Con- ference on Parallel Processing (ICPP), pp. 593–601, 2002.

[49] P. Yang, C. Wong, P. Marchal, F. Catthoor, D. Desmet, D. Kerkest, and R. Lauwereins, “Proportionate progress: A notion of fairness in resource allocation,” IEEE Design and Test of Computers, vol. 18, no. 5, 2001.

[50] L.-F. Fan, T.-H. Tsai, Y.-S. Chen, and S.-S. Shyu, “Energy-aware real-time task synchronization in multi-core embedded systems,” in Proceedings of the 28th Annual ACM Symposium on Applied Computing (SAC), pp. 1493–1498, March 2013.

[51] J.-J. Han, D. Zhu, X. Wu, L. T. Yang, and H. Jin, “Multiprocessor real-time systems with shared resources: Utilization bound and mapping,” IEEE Transactions on Parallel and Dis- tributed Systems (TPDS), vol. 25, no. 11, pp. 2981–2991, 2013.

[52] E. M. Saad, A. M. Elewi, M. Shalan, and M. H. Awadalla, “Energy and synchronization-aware mapping of real-time tasks on asymmetric multicore platforms,” International Journal of Computer Applications (IJCA), vol. 75, pp. 35–40, August 2013.

[53] A. M. Elewi, M. Shalan, M. H. Awadalla, and E. M. Saad, “Energy-efficient task allocation techniques for asymmetric multiprocessor embedded systems,” Transactions on Embedded Computing Systems (TECS), vol. 13, pp. 71:1–71:27, January 2014.

[54] M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness. New York, NY, USA: W. H. Freeman & Co., 1990.

[55] D.-I. Oh and T. Baker, “Utilization bounds for n-processor rate monotone scheduling with static processor assignment,” Real-Time Systems, vol. 15, no. 2, pp. 183–192, 1998.

[56] J. M. Lopez, J. L. Diaz, M. Garcia, and D. Gracia, “Worst-case utilization bound for EDF scheduling on real-time multiprocessor systems,” in Proceedings of the 12th IEEE Euromicro Workshop on Real-Time Systems (RTS 2000), pp. 25–33, 2000.

[57] J.M.Lopez,J.L.Diaz,andD.F.Gracia,“Utilization bound for EDF scheduling on real-time multiprocessor systems,” Real-Time Systems, vol. 28, no. 1, pp. 39–68, 2004.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊