Two Heuristic Methods of Hardware Threads Interleaving in a Time Predictable Multitasking System

Andrzej Pułka; Ernest Antolak; Bartłomiej Truś

doi:10.61822/amcs-2026-0012

Abstract

This paper presents and tests several task scheduling methods in a real-time multitasking system based on the thread interleaving mechanism. The original configurable multicore time-predictable system architecture for multitasking is briefly discussed. The essential requirement of the system is the predictability of tasks, regardless of their number and when they are initialized. The paper focuses on the appropriate configuration of core interleaving registers, which determine the order and frequency of execution of individual tasks. This study develops various heuristic algorithms based on genetic programming and task execution rate analysis, and implements these in the Python language and PROLOG. The experiments are conducted with different task scenarios and system work requirements: with minimization of resources, energy, and operating frequency. A special task analyzer is used to evaluate the quality of the resulting system configuration. The results obtained are tested on a real hardware structure implemented in an FPGA chip. The proposed approach can be a useful tool for configuring real-time multitasking systems.

References

Ahn, C.W. and Ramakrishna, R. (2003). Elitism-based compact genetic algorithms, IEEE Transactions on Evolutionary Computation 7(4): 367–385.
Search in Google Scholar Back to article
Akesson, B. and Goossens, K. (2012). Memory Controllers for Real-Time Embedded Systems, Springer, New York, DOI: 10.1007/978-1-4419-8207-0.
Search in Google Scholar Back to article
Alander, J. (1992). On optimal population size of genetic algorithms, CompEuro 1992: Proceedings Computer Systems and Software Engineering, The Hague, Netherlands, pp. 65–70.
Search in Google Scholar Back to article
AlBarakat, L.M., Gratz, P.V. and Jimenez, D.A. (2018). MTB-Fetch: Multithreading aware hardware prefetching for chip multiprocessors, IEEE Computer Architecture Letters 17(2): 175–178.
Search in Google Scholar Back to article
Alhammad, A. and Pellizzoni, R. (2014). Time-predictable execution of multithreaded applications on multicore systems, Design, Automation & Test in Europe Conference & Exhibition (DATE), 2014, Dresden, Germany, pp. 1–6.
Search in Google Scholar Back to article
Andalam, S., Roop, P.S., Girault, A. and Traulsen, C. (2014). A predictable framework for safety-critical embedded systems, IEEE Transactions on Computers 63(7): 1600–1612.
Search in Google Scholar Back to article
Antolak, E. and Pułka, A. (2021). Energy-efficient task scheduling in design of multithread time predictable real-time systems, IEEE Access 9: 121111–121127.
Search in Google Scholar Back to article
Antolak, E. and Pułka, A. (2020). Flexible hardware approach to multicore time predictable systems design based on the interleaved pipeline processing, IET Circuits, Devices & Systems 14(5): 648–659, DOI: 10.1049/iet-cds.2019.0521.
Search in Google Scholar Back to article
Antolak, E. and Pułka, A. (2022). An analysis of the impact of gating techniques on the optimization of the energy dissipated in real-time systems, Applied Sciences 12(3): 1630.
Search in Google Scholar Back to article
Antolak, E. and Pułka, A. (2023). Validation of task scheduling techniques in multithread time predictable systems, IEEE Access 11: 46979–46997.
Search in Google Scholar Back to article
Antolak, E. and Pułka, A. (2024). Power consumption prediction in real-time multitasking systems, Electronics 13(7): 1347–1366.
Search in Google Scholar Back to article
Axer, P., Ernst, R., Falk, H., Girault, A., Grund, D., Guan, N., Jonsson, B., Marwedel, P., Reineke, J., Rochange, C., Sebastian, M., Hanxleden, R.V., Wilhelm, R. and Yi, W. (2014). Building timing predictable embedded systems, ACM Transactions on Embedded Computing Systems 13(4): 1–37, DOI: 10.1145/2560033.
Search in Google Scholar Back to article
Bahn, H. and Cho, K. (2020). Evolution-based real-time job scheduling for co-optimizing processor and memory power savings, IEEE Access 8: 152805–152819.
Search in Google Scholar Back to article
Bratko, I. (2012). Prolog Programming for Artificial Intelligence, 4th Edn, Addison-Wesley, Harlow.
Search in Google Scholar Back to article
Broman, D., Zimmer, M., Kim, Y., Kim, H., Cai, J., Shrivastava, A., Edwards, S.A. and Lee, E.A. (2013). Precision timed infrastructure: Design challenges, Proceedings of the 2013 Electronic System Level Synthesis Conference (ESLsyn), Austin, USA, pp. 1–6.
Search in Google Scholar Back to article
Buttazzo, G.C. (2011). Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, Springer US, Boston, DOI: 10.1007/978-1-4614-0676-1.
Search in Google Scholar Back to article
Cazorla, F., Knijnenburg, P., Sakellariou, R., Fernandez, E., Ramirez, A. and Valero, M. (2006). Predictable performance in SMT processors: Synergy between the OS and SMTs, IEEE Transactions on Computers 55(7): 785–799.
Search in Google Scholar Back to article
Chen, J., Du, C., Han, P. and Zhang, Y. (2019). Sensitivity Analysis of strictly periodic tasks in multi-core real-time systems, IEEE Access 7: 135005–135022.
Search in Google Scholar Back to article
Chniter, H., Mosbahi, O., Khalgui, M., Zhou, M. and Li, Z. (2020). Improved multi-core real-time task scheduling of reconfigurable systems with energy constraints, IEEE Access 8: 95698–95713.
Search in Google Scholar Back to article
Clocksin, W. and Mellish, C. (2003). Programming in Prolog, Springer, Berlin/Heidelberg.
Search in Google Scholar Back to article
Edwards, S.A. and Lee, E.A. (2007). The case for the precision timed (PRET) machine, 2007 44th ACM/IEEE Design Automation Conference, San Diego, USA, pp. 264–265.
Search in Google Scholar Back to article
Fernández, M., Gioiosa, R., Quiñones, E., Fossati, L., Zulianello, M. and Cazorla, F.J. (2012). Assessing the suitability of the NGMP multi-core processor in the space domain, Proceedings of the 10th ACM International Conference on Embedded Software, Tampere, Finland, pp. 175–184, DOI: 10.1145/2380356.2380389.
Search in Google Scholar Back to article
Forsberg, B., Benini, L. and Marongiu, A. (2018). HePREM: Enabling predictable GPU execution on heterogeneous SoC, 2018 Design, Automation & Test in Europe Conference & Exhibition (DATE), Dresden, Germany, pp. 539–544.
Search in Google Scholar Back to article
Gajski, D.D., Abdi, S., Gerstlauer, A. and Schirner, G. (2009). Embedded System Design: Modeling, Synthesis and Verification, Springer US, Boston, DOI: 10.1007/978-1-4419-0504-8.
Search in Google Scholar Back to article
Glaser, F., Tagliavini, G., Rossi, D., Haugou, G., Huang, Q. and Benini, L. (2021). Energy-efficient hardware-accelerated synchronization for shared-L1-memory multiprocessor clusters, IEEE Transactions on Parallel and Distributed Systems 32(3): 633–648.
Search in Google Scholar Back to article
Goldberg, D.E. and Goldberg, D.E. (2012). Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Boston.
Search in Google Scholar Back to article
Henzinger, T.A. and Kirsch, C.M. (2002). The embedded machine: Predictable, portable real-time code, Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, Berlin, Germany, pp. 315–326, DOI: 10.1145/512529.512567.
Search in Google Scholar Back to article
Ip, N.J.H. and Edwards, S.A. (2006). A processor extension for cycle-accurate real-time software, in D. Hutchison et al. (Eds), Embedded and Ubiquitous Computing, Springer, Berlin/Heidelberg, pp. 449–458, DOI: 10.1007/1180216746.
Search in Google Scholar Back to article
Kim, D., Ko, Y.-B. and Lim, S.-H. (2020a). Energy-efficient real-time multi-core assignment scheme for asymmetric multi-core mobile devices, IEEE Access 8: 117324–117334.
Search in Google Scholar Back to article
Kim, Y., Kong, J. and Munir, A. (2020b). CPU-accelerator co-scheduling for CNN acceleration at the edge, IEEE Access 8: 211422–211433.
Search in Google Scholar Back to article
Kochenderfer, M.J. and Wheeler, T.A. (2019). Algorithms for Optimization, MIT Press, Cambridge.
Search in Google Scholar Back to article
Lamie, E.L. (2009). Real-Time Embedded Multithreading Using ThreadX, 2nd Edn, Newnes, Amsterdam.
Search in Google Scholar Back to article
Lee, E. (2005). Absolutely positively on time: What would it take?, Computer 38(7): 85–87.
Search in Google Scholar Back to article
Lee, E. (2006). The problem with threads, Computer 39(5): 33–42.
Search in Google Scholar Back to article
Lee, E. and Messerschmitt, D. (1987). Pipeline interleaved programmable DSP’s: Architecture, IEEE Transactions on Acoustics, Speech, and Signal Processing 35(9): 1320–1333.
Search in Google Scholar Back to article
Lickly, B., Liu, I., Kim, S., Patel, H.D., Edwards, S.A. and Lee, E.A. (2008). Predictable programming on a precision timed architecture, Proceedings of the 2008 International Conference on Compilers, Architectures and Synthesis for Embedded Systems, Atlanta, USA, pp. 137–146, DOI: 10.1145/1450095.1450117.
Search in Google Scholar Back to article
Liu, I., Reineke, J. and Lee, E.A. (2010). A PRET architecture supporting concurrent programs with composable timing properties, 2010 Conference Record of the 44th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, USA, pp. 2111–2115.
Search in Google Scholar Back to article
Lutz, M. (2019). Programming Python, 4th Edn, O’Reilly, Beijing.
Search in Google Scholar Back to article
Michalak, K. (2021). Evolutionary algorithm using random immigrants for the multiobjective travelling salesman problem, Procedia Computer Science 192: 1461–1470.
Search in Google Scholar Back to article
Moulik, S., Devaraj, R. and Sarkar, A. (2018). COST: A cluster-oriented scheduling technique for heterogeneous multi-cores, 2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC), Miyazaki, Japan, pp. 1951–1957.
Search in Google Scholar Back to article
Oliveira, A.S.R., Almeida, L. and Ferrari, A.D.B. (2011). The ARPA-MT embedded SMT processor and its RTOS hardware accelerator, IEEE Transactions on Industrial Electronics 58(3): 890–904.
Search in Google Scholar Back to article
Paolieri, M., Quinones, E., Cazorla, F.J., Wolf, J., Ungerer, T., Uhrig, S. and Petrov, Z. (2011). A software-pipelined approach to multicore execution of timing predictable multi-threaded hard real-time tasks, 2011 14th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing, Newport Beach, USA, pp. 233–240.
Search in Google Scholar Back to article
Pathan, R., Voudouris, P. and Stenstrom, P. (2018). Scheduling parallel real-time recurrent tasks on multicore platforms, IEEE Transactions on Parallel and Distributed Systems 29(4): 915–928.
Search in Google Scholar Back to article
Rehman, A.U., Ahmad, Z., Jehangiri, A.I., Ala’Anzy, M.A., Othman, M., Umar, A.I. and Ahmad, J. (2020). Dynamic energy efficient resource allocation strategy for load balancing in fog environment, IEEE Access 8: 199829–199839.
Search in Google Scholar Back to article
Reineke, J., Liu, I., Patel, H.D., Kim, S. and Lee, E.A. (2011). PRET DRAM controller: Bank privatization for predictability and temporal isolation, Proceedings of the 7th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, Taipei, Taiwan, pp. 99–108, DOI: 10.1145/2039370.2039388.
Search in Google Scholar Back to article
Schoeberl, M. (2008). A Java processor architecture for embedded real-time systems, Journal of Systems Architecture 54(1-2): 265–286.
Search in Google Scholar Back to article
Schoeberl, M., Abbaspour, S., Akesson, B., Audsley, N., Capasso, R., Garside, J., Goossens, K., Goossens, S., Hansen, S., Heckmann, R., Hepp, S., Huber, B., Jordan, A., Kasapaki, E., Knoop, J., Li, Y., Prokesch, D., Puffitsch, W., Puschner, P., Rocha, A., Silva, C., Sparsø, J. and Tocchi, A. (2015). T-CREST: Time-predictable multi-core architecture for embedded systems, Journal of Systems Architecture 61(9): 449–471.
Search in Google Scholar Back to article
Schoeberl, M., Schleuniger, P., Puffitsch, W., Brandner, F. and Probst, C.W. (2012). Towards a time-predictable dual-issue microprocessor: The Patmos Approach, Open Access Series in Informatics 18: 11–21.
Search in Google Scholar Back to article
Thiele, L. and Wilhelm, R. (2004). Design for timing predictability, Real-Time Systems 28(2/3): 157–177, DOI: 10.1023/B:TIME.0000045316.66276.6e.
Search in Google Scholar Back to article
Truś, B. (2023). Implementation of the Scheduling Mechanisms of Tasks in a Multicore Real Time System, Silesian University of Technology, Gliwice, (in Polish).
Search in Google Scholar Back to article
Ungerer, T., Cazorla, F., Sainrat, P., Bernat, G., Petrov, Z., Rochange, C., Quinones, E., Gerdes, M., Paolieri, M., Wolf, J., Casse, H., Uhrig, S., Guliashvili, I., Houston, M., Kluge, F., Metzlaff, S. and Mische, J. (2010). MERASA: Multicore execution of hard real-time applications supporting analyzability, IEEE Micro 30(5): 66–75.
Search in Google Scholar Back to article
Zimmer, M., Broman, D., Shaver, C. and Lee, E.A. (2014). FlexPRET: A processor platform for mixed-criticality systems, 2014 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), Berlin, Germany, pp. 101–110.
Search in Google Scholar Back to article

Two Heuristic Methods of Hardware Threads Interleaving in a Time Predictable Multitasking System

Abstract

Paradigm

My account