本篇論文探討異質多核心系統的即時排程問題,在工作相依性限制的複雜度之下,一
對一雙核心系統中測試不同的排程跟協定方法對各種系統效率的影響,各種不同搶佔設
計對其系統效率的影響,測試搶佔行為的次數及不同的上下文切換的開銷量的影響。
在多核心系統中,探討不同的工作結構在 Partition 與 Global 系統效率,並探討不同
核心上遷移的開銷與上下文切換的開銷問題,測試並討論對各種調配方法對系統效率的
影響,進一步比較在 Partition 加入本論文的方法之後,可以減少多少次的搶佔行為。

This paper explores the real-time scheduling problems for heterogeneous multi-core systems. With the precedence constraint consideration, we test the performance of heterogeneous dual-core systems under varying schedulers, protocols, preemption point and context switch overhead. In heterogeneous multi-core systems, we discuss the performance of system under varying dispatchers, migration cost and task structures. We also propose an efficient algorithm to reduce the number of preemption in heterogeneous multi-core systems.

[1] J. G. Proakis and D. G. Manolakis, “Introduction to digital signal processing,” Pren-
tice Hall Professional Technical Reference, 1988.
[2] E. A. Paulo S and S. L, “Digital signal processing system analysis and design,”
United Kingdom at the University Press,Cambridge, 2010.
[3] S. Zhang and K. S. Chatha, “Automated techniques for energy efficient schedul-
ing on homogeneous and heterogeneous chip multi-processor architectures,” in Pro-
ceedings of the 2008 Asia and South Pacific Design Automation Conference, ASP-
DAC08, (LosAlamitos,CA, USA),pp.61–66, IEEEComputerSocietyPress, 2008.
[4] A. Plaza, D. Valencia, and J. Plaza, “An experimental comparison of parallel algo-
rithms for hyperspectral analysis using heterogeneous and homogeneous networks
of workstations,” Parallel Computing, vol. 34, no. 2, pp. 92 – 114, 2008.
[5] S. Browne and U. Yechiali, “Scheduling deteriorating jobs on a single processor,”
vol. 38, pp. 495–498, in INFORMS, May 1990.
[6] R. Ravi, A. Agrawal, and P. Klein, “Ordering problems approximated: single-
processor scheduling and interval graph completion,” vol. 510, pp. 751–762,
Springer Berlin Heidelberg, 1991.
[7] A. Bar-Noy, R. Bhatia, J. Naor, and B. Schieber, “Minimizing service and operation
costs of periodic scheduling,” Mathematics of Operations Research, vol. 27, no. 3,
pp. pp. 518–544, 2002.
[8] B. Sprunt, L. Sha, and J. Lehoczky, “Aperiodic task scheduling for hard-real-time
systems,” Real-Time Systems, vol. 1, pp. 27–60, 1989.
[9] L. Cucu and J. Goossens, “Feasibility intervals for fixed-priority real-time schedul-
ing on uniform multiprocessors,” in Proceedings of the IEEE Conference on Emerg-
ing Technologies and Factory Automation, 2006. ETFA ’06., pp. 397 –404, sept.
2006.
[10] B. Andersson and J. Jonsson, “Fixed-prioritypreemptivemultiprocessorscheduling:
to partition or not to partition,” in Proceedings of the Seventh International Confer-
ence on Real-Time Computing Systems and Applications, pp. 337 –346, 2000.
[11] D. Tsafrir, “The context-switch overhead inflicted by hardware interrupts (and the
enigmaofdo-nothingloops),”inProceedingsofthe2007workshoponExperimental
computer science, ExpCS ’07, (New York, NY, USA), ACM, 2007.
[12] M. Behnam, I. Shin, T. Nolte, and M. Nolin, “SIRAP: a synchronization protocol
for hierarchical resource sharingin real-time open systems,” in Proceedings of the
7th ACM & IEEE international conference on Embedded software, EMSOFT
’07, (New York, NY, USA), pp. 279–288, ACM, 2007.
[19] J. Y. T. Leung and J. Whitehead, “On the complexity of fixed-priority scheduling
of periodic, real-time tasks,” Performance Evaluation, vol. 2, no. 4, pp. 237 – 250,
1982.
[20] J. Haritsa, M. Livny, and M. Carey, “Earliest deadline scheduling for real-time
database systems,” in Real-Time Systems Symposium, 1991. Proceedings., Twelfth,
pp. 232 –242, dec 1991.
[21] M. Spuri and J. Stankovic, “How to integrate precedence constraints and shared
resources in real-time scheduling,” Computers, IEEE Transactions on, vol. 43,
pp. 1407 –1412, dec 1994.
[22] H. Chetto, M. Silly, and T. Bouchentouf, “Dynamic scheduling of real-time tasks
under precedence constraints,” Real-Time Systems, vol. 2, pp. 181–194, 1990.
[23] S. Baruah andN. Fisher, “Thepartitionedmultiprocessorschedulingofsporadictask
systems,” Real-Time Systems Symposium, IEEE International, vol. 0, pp. 321–329,
2005.
[24] N. Fisher, S. Baruah, and T. P. Baker, “The partitioned scheduling of sporadic tasks
according to static-priorities,” Real-Time Systems, Euromicro Conference on, vol. 0,
pp. 118–127, 2006.
[25] S. Lauzac, R. Melhem, and D. Mosse, “Comparison of global and partitioning
schemes for scheduling rate monotonic tasks on a multiprocessor,” in Real-Time
Systems, 1998. Proceedings. 10th Euromicro Workshop on, pp. 188 –195, jun 1998.
[26] B. Andersson, S. Baruah, and J. Jonsson, “Static-priority scheduling on multipro-
cessors,” in Real-Time Systems Symposium, 2001. (RTSS 2001). Proceedings. 22nd
IEEE, pp. 193 – 202, dec. 2001.
[27] J. Simonson and J. Patel, “Use of preferred preemption points in cache-based real-
time systems,”in Computer Performanceand DependabilitySymposium, 1995. Pro-
ceedings., International, pp. 316 –325, Apr. 1995.
[28] C.-M. Cheng, “Real-time on-line task scheduling for dual-core embedded systems,”
Master’s thesis, National Chiao Tung University.
[29] R. Rajkumar, “Real-time synchronization protocols for shared memory multipro-
cessors,” in Distributed Computing Systems, 1990. Proceedings., 10th International
Conference on, pp. 116 –123, may-1 jun 1990.
[13] O. Zapata and P. Alvarez, “EDF and RM multiprocessor scheduling algorithms:
survey and performance evaluation,” CINVESTAV-IPN, Seccion de Computacion,
Oct 2005.
[14] G. C. Buttazzo, “Rate monotonic vs. EDF: judgment day,” Real-Time Systems,
vol. 29, pp. 5–26, 2005.
[15] B. Dutertre, “Formal analysis of the priority ceiling protocol,” in Proceedings of the
Real-Time Systems Symposium, 2000. Proceedings. The 21st IEEE, pp. 151 –160,
2000.
[16] T. Baker, “A stack-based resource allocation policy for realtime processes,” in Pro-
ceedings of the Real-Time Systems Symposium, 1990. 11th, pp. 191 –200, dec 1990.
[17] G. Buttazzo and E. Bini, “Optimal dimensioning of a constant bandwidth server,”
Real-Time Systems Symposium, IEEE International, vol. 0, pp. 169–177, 2006.
[18] G. Fohler, T. Lennvall, and G. Buttazzo, “Improved handling of soft aperiodic tasks
in offline scheduled real-time systems using total bandwidth server,” in Emerging
Technologies and Factory Automation, 2001. Proceedings. 2001 8th IEEE Interna-
tional Conference on, pp. 151 –157 vol.1, 2001.