Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Two-phase colour-aware multicore real-time scheduler

© The Institution of Engineering and Technology
Received 02/08/2016, Accepted 01/01/2017, Revised 23/11/2016, Published 18/01/2017

A two-phase colour-aware real-time scheduler to reduce the contention caused by the cache coherence protocol due to accesses to shared cache partitions in a multicore processor is proposed. The first phase is a colour-aware task partitioning (CAP) algorithm that assigns tasks that share colours to a common processor whenever possible. The second phase is a dynamic colour-aware scheduler that detects cache coherence activities at run-time, preventing the execution of tasks that interfere with each other and thus reducing the contention caused by the cache coherence protocol. The authors compare the proposed scheduler with a CAP without run-time optimisation and with the best-fit decreasing heuristic in terms of deadline misses and tardiness of several task sets using a real-time operating system and a modern 8-core processor. The results indicate that the proposed scheduler improves deadline tardiness and provides hard real-time guarantees by combining cache and task partitioning with scheduling optimisations.

Inspec keywords: optimisation; processor scheduling

Other keywords: colour-aware task partitioning algorithm; real-time operating system; dynamic colour-aware scheduler; two-phase colour-aware multicore real-time scheduler; cache coherence protocol

Subjects: Multiprocessing systems; Optimisation techniques

References

    1. 1)
      • 10. Claraz, D., Kuntz, S., Margull, U., et al: ‘Deterministic execution sequence in component based multi-contributor powertrain control systems’. Embedded Real Time Software and Systems Conf. (ERTS), 2012, pp. 1–7.
    2. 2)
      • 11. Niz, D.D., Wrage, L., Storer, N., et al: ‘On resource overbooking in an unmanned aerial vehicle’. Proc. of the 2012 IEEE/ACM Third Int. Conf. on Cyber-Physical Systems, ICCPS ‘12, Washington, DC, USA, 2012, pp. 97–106.
    3. 3)
      • 17. Guan, N., Stigge, M., Yi, W., et al: ‘Cache-aware scheduling and analysis for multicores’. Proc. of the EMSOFT, 2009, pp. 245–254.
    4. 4)
      • 13. Lindsay, C.: ‘LWFG: A cache-aware multi-core real-time scheduling algorithm’. Master's thesis, Virginia Polytechnic Institute and State University, 2012.
    5. 5)
      • 9. Liu, J.: ‘Real-time systems’ (Prentice Hall PTR, Upper Saddle River, NJ, USA, 2000, 1st edn.).
    6. 6)
      • 8. Bastoni, A., Brandenburg, B.B., Anderson, J.H.: ‘An empirical comparison of global, partitioned, and clustered multiprocessor edf schedulers’. Proc. of the 31st RTSS, 2010, pp. 14–24.
    7. 7)
      • 14. Wolfe, A.: ‘Software-based cache partitioning for real-time applications’, J. Comput. Sofw. Eng., 1994, 2, (3), pp. 315–327.
    8. 8)
      • 2. Mancuso, R., Dudko, R., Betti, E., et al: ‘Real-time cache management framework for multi-core architectures’. Proc. of the 19th IEEE RTAS, 2013, pp. 45–54.
    9. 9)
      • 7. Gracioli, G., Fröhlich, A.A., Pellizzoni, R., et al: ‘Implementation and evaluation of global and partitioned scheduling in a real-time OS’, Real-Time Syst., 2013, 49, (6), pp. 669–714.
    10. 10)
      • 6. Gracioli, G., Fröhlich, A.A.: ‘An experimental evaluation of the cache partitioning impact on multicore real-time schedulers’. Proc. of the 19th RTCSA, August 2013, pp. 72–81.
    11. 11)
      • 1. Gracioli, G., Fröhlich, A.A.: ‘CAP: color-aware task partitioning for multicore real-time applications’. Proc. of 19th ETFA, September 2014, pp. 1–8.
    12. 12)
      • 16. Calandrino, J.M., Anderson, J.H.: ‘On the design and implementation of a cacheaware multicore real-time scheduler’. Proc. of the ECRTS ‘09, 2009, pp. 194–204.
    13. 13)
      • 15. Vera, X., Lisper, B., Xue, J.: ‘Data cache locking for higher program predictability’, SIGMETRICS Perform. Eval. Rev., 2003, 31, (1), pp. 272–282.
    14. 14)
      • 18. EPOS. Website, July 2016.
    15. 15)
      • 12. Kramer, S., Ziegenbein, D., Hamann, A.: ‘Real world automotive benchmarks for free’. 6th Int. Workshop on Analysis Tools and Methodologies for Embedded and Realtime Systems (WATERS), 2015.
    16. 16)
      • 5. Liedtke, J., Haertig, H., Hohmuth, M.: ‘Os-controlled cache predictability for real-time systems’. Proc. of the 3rd RTAS, 1997, pp. 213–224.
    17. 17)
      • 3. Kim, H., Kandhalu, A., Rajkumar, R.: ‘A coordinated approach for practical OS-level cache management in multi-core real-time systems’. Proc. of the 25th ECRTS, 2013, pp. 80–89.
    18. 18)
      • 4. Kenna, C., Herman, J., Ward, B., et al: ‘Making shared caches more predictable on multicore platforms’. Proc. of the 25th ECRTS, 2013, pp. 157–167.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2016.0114
Loading

Related content

content/journals/10.1049/iet-cdt.2016.0114
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address