Affinity-Based Task Scheduling on Heterogeneous Multicore Systems Using CBS and QBICTM
Source abstract
Abstract
This work presents the grouping of dependent tasks into a cluster using the Bayesian analysis model to solve the affinity scheduling problem in heterogeneous multicore systems. The non-affinity scheduling of tasks has a negative impact as the overall execution time for the tasks increases. Furthermore, non-affinity-based scheduling also limits the potential for data reuse in the caches so it becomes necessary to bring the same data into the caches multiple times. In heterogeneous multicore systems, it is essential to address the load balancing problem as all cores are operating at varying frequencies. We propose two techniques to solve the load balancing issue, one being designated “chunk-based scheduler” (CBS) which is applied to the heterogeneous systems while the other system is “quantum-based intra-core task migration” (QBICTM) where each task is given a fair and equal chance to run on the fastest core. Results show 30–55% improvement in the average execution time of the tasks by applying our CBS or QBICTM scheduler compare to other traditional schedulers when compared using the same operating system.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Cloud Computing and Resource Management · Distributed and Parallel Computing Systems · Parallel Computing and Optimization Techniques
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Computer Science, Air University, Islamabad 44200, Pakistan
Department of Computer Science and Software Engineering, United Arab Emirates University, Al Ain 15551, United Arab Emirates
Department of Human-Computer Interaction, Hanyang University, Ansan 15588, Korea
References (43)
Show source-provided references
1. Li, M., Chen, C., Zhu, G., and Savaria, Y. (2018, January 5–8). Local Queueing-Based Data-Driven Task Scheduling for Multicore Systems. Proceedings of the 2018 IEEE 61st International Midwest Symposium on Circuits and Systems (MWSCAS), Windsor, ON, Canada.10.1109/MWSCAS.2018.8623930 ↗
2. Akram, N., Zhang, Y., Ali, S., and Amjad, H.M. (2019, January 8–12). Efficient Task Allocation for Real-Time Partitioned Scheduling on Multi-Core Systems. Proceedings of the 2019 16th International Bhurban Conference on Applied Sciences and Technology (IBCAST), Islamabad, Pakistan.10.1109/IBCAST.2019.8667139 ↗
3. Work-in-Progress: Cache-Aware Partitioned EDF Scheduling for Multi-Core Real-Time Systems
4. Xu, M., Phan, L.T.X., Choi, H.-Y., and Lee, I. (2016, January 11–14). Analysis and Implementation of Global Preemptive Fixed-Priority Scheduling with Dynamic Cache Allocation. Proceedings of the 2016 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), Vienna, Austria.10.1109/RTAS.2016.7461322 ↗
5. Song, F., Moore, S., and Dongarra, J. (September, January 31). Analytical Modeling for Affinity-Based Thread Scheduling on Multicore Platforms. Proceedings of the 2009 IEEE International Conference on Cluster Computing and Workshops, New Orleans, LA, USA.10.1109/CLUSTR.2009.5289173 ↗
6. Sibai, F.N. (2007, January 18–20). Performance Effect of Localized Thread Schedules in Heterogeneous Multi-Core Processors. Proceedings of the 2007 Innovations in Information Technologies (IIT), Dubai, United Arab Emirates.10.1109/IIT.2007.4430377 ↗
7. Sharma, R., and Kanungo, P. (2014, January 7–9). Dynamic Load Balancing Algorithm for Heterogeneous Multi-Core Processors Cluster. Proceedings of the Proceedings—2014 4th International Conference on Communication Systems and Network Technologies—CSNT 2014, Bhopal, India.10.1109/CSNT.2014.63 ↗
8. Using Processor Affinity in Loop Scheduling on Shared-Memory Multiprocessors10.1109/71.273046 ↗
9. Shende, S., Malony, A.D., Morris, A., Spear, W., and Biersdorff, S. (2011). Encyclopedia of Parallel Computing. Encyclopedia of Parallel Computing, Springer.
10. Gollapudi, R.T., Yuksek, G., and Ghose, K. (2019, January 17–19). Cache-Aware Dynamic Classification and Scheduling for Linux. Proceedings of the 2019 IEEE Symposium in Low-Power and High-Speed Chips (COOL CHIPS), Yokohama, Japan.10.1109/CoolChips.2019.8721355 ↗
11. Anderson, J.H., and Calandrino, J.M. (2006). Parallel Real-Time Task Scheduling on Multicore Platforms, IEEE.10.1109/RTSS.2006.32 ↗
12. Calandrino, J.M., and Anderson, J.H. (2008, January 2–4). Cache-Aware Real-Time Scheduling on Multicore Platforms: Heuristics and a Case Study. Proceedings of the Euromicro Conference on Real-Time Systems, Prague, Czech Republic.10.1109/ECRTS.2008.10 ↗
13. Chattopadhyay, S., Kee, C.L., Roychoudhury, A., Kelter, T., Marwedel, P., and Falk, H. (2012, January 16–19). A Unified WCET Analysis Framework for Multi-Core Platforms. Proceedings of the 2012 IEEE 18th Real Time and Embedded Technology and Applications Symposium, Beijing, China.10.1109/RTAS.2012.26 ↗
14. Kim, N., Ward, B.C., Chisholm, M., Fu, C.-Y., Anderson, J.H., and Smith, F.D. (2016, January 11–14). Attacking the One-Out-Of-m Multicore Problem by Combining Hardware Management with Mixed-Criticality Provisioning. Proceedings of the 2016 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), Vienna, Austria.10.1109/RTAS.2016.7461323 ↗
15. Berna, B., and Puaut, I. (2012, January 8–9). PDPA: Period Driven Task and Cache Partitioning Algorithm for Multi-Core Systems. Proceedings of the RTNS’12: 20th International Conference on Real-Time and Network Systems, Pont-à-Mousson, France.10.1145/2392987.2393010 ↗
16. Deep Learning Approach for Microarray Cancer Data Classification10.1049/trit.2019.0028 ↗
17. Efficient Algorithm for Big Data Clustering on Single Machine10.1049/trit.2019.0048 ↗
18. Object Tracking on Event Cameras with Offline-Online Learning10.1049/trit.2019.0107 ↗
19. Machine Learning Model for Dynamical Response of Nano-Composite Pipe Conveying Fluid under Seismic Loading Machine Learning Model for Dynamical Response10.1504/IJHM.2020.105499 ↗
20. The Effects of Particle Swarm Optimisation and Genetic Algorithm on ANN Results in Predicting Pile Bearing Capacity the Effects of Particle Swarm Optimisation and Genetic Algorithm10.1504/IJHM.2020.105484 ↗
21. Human Activity Recognition via Recognized Body Parts of Human Depth Silhouettes for Residents Monitoring Services at Smart Home10.1177/1420326X12469714 ↗
22. Jalal, A., Khalid, N., and Kim, K. (2020). Automatic Recognition of Human Interaction via Hybrid Descriptors and Maximum Entropy Markov Model Using Depth Sensors. Entropy, 22.10.3390/e22080817 ↗
23. Jalal, A., Batool, M., and Kim, K. (2020). Stochastic Recognition of Physical Activity and Healthcare Using Tri-Axial Inertial Wearable Sensors. Appl. Sci., 10.10.3390/app10207122 ↗
24. Cache Hierarchy-Aware Query Mapping on Emerging Multicore Architectures10.1109/TC.2016.2605682 ↗
25. Markatos, E.P., and Leblanc, T.J. (1992, January 16–20). Using Processor Affinity in Loop Scheduling on Shared-Memory Multiprocessors. Proceedings of the Supercomputing’92: 1992 ACM/IEEE Conference on Supercomputing, Minneapolis, MN, USA.
26. Gochoo, M., Akhter, I., Jalal, A., and Kim, K. (2021). Stochastic Remote Sensing Event Classification over Adaptive Posture Estimation via Multifused Data and Deep Belief Network. Remote. Sens., 13.10.3390/rs13050912 ↗
27. Jalal, A., Ahmed, A., Rafique, A.A., and Kim, K. (2021). Scene Semantic Recognition Based on Modified Fuzzy C-Mean and Maximum Entropy Using Object-to-Object Relations. IEEE Access, 1.10.1109/ACCESS.2021.3058986 ↗
28. WHITE STAG Model: Wise Human Interaction Tracking and Estimation (WHITE) Using Spatio-Temporal and Angular-Geometric (STAG) Descriptors10.1007/s11042-019-08527-8 ↗
29. Ahmed, A., Jalal, A., and Kim, K. (2020). A Novel Statistical Method for Scene Classification Based on Multi-Object Categorization and Logistic Regression. Sensors, 20.10.3390/s20143871 ↗
30. Optimization of the Load Balancing Policy for Tiled Many-Core Processors10.1109/ACCESS.2018.2883415 ↗
31. Muraraşu, A., and Weidendorfer, J. (2012, January 5–7). Building Input Adaptive Parallel Applications: A Case Study of Sparse Grid Interpolation. Proceedings of the 15th IEEE International Conference on Computational Science and Engineering, Paphos, Cyprus.10.1109/ICCSE.2012.11 ↗
32. Jalal, A., Quaid, M.A.K., Ud Din Tahir, S.B., and Kim, K. (2020). A Study of Accelerometer and Gyroscope Measurements in Physical Life-Log Activities Detection Systems. Sensors, 20.10.3390/s20226670 ↗
33. Jalal, A., Akhtar, I., and Kim, K. (2020). Human Posture Estimation and Sustainable Events Classification via Pseudo-2D Stick Model and K-Ary Tree Hashing. Sustainability, 12.10.3390/su12239814 ↗
34. Jalal, A., Batool, M., and Kim, K. (2020). Sustainable Wearable System: Human Behavior Modeling for Life-Logging Activities Using K-Ary Tree Hashing Classifier. Sustainability, 12.10.3390/su122410324 ↗
35. Evaluating the Performance of Cache-Affinity Scheduling in Shared-Memory Multiprocessors10.1006/jpdc.1995.1014 ↗
36. Jia, G., Li, X., Wang, C., Zhou, X., and Zhu, Z. (2012, January 24–28). Memory Affinity: Balancing Performance, Power, Thermal and Fairness for Multi-Core Systems. Proceedings of the 2012 IEEE International Conference on Cluster Computing, 2012, Beijing, China.10.1109/CLUSTER.2012.33 ↗
37. Barrios Hernández, C.J., Gitler, I., and Klapp, J. (2017). High Performance Computing, Springer International Publishing.10.1007/978-3-319-57972-6 ↗
38. Johari, S., and Kumar, A. (2014, January 11–13). Algorithmic Approach for Applying Load Balancing during Task Migration in Multi-Core System. Proceedings of the 2014 International Conference on Parallel, Distributed and Grid Computing, Solan, India.10.1109/PDGC.2014.7030710 ↗
39. Agent Based Load Balancing Scheme Using Affinity Processor Scheduling for Multicore Architectures
40. Holmbacka, S., Lund, W., Lafond, S., and Lilius, J. (March, January 27). Task Migration for Dynamic Power and Performance Characteristics on Many-Core Distributed Operating Systems. Proceedings of the 2013 21st Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, 2013, Belfast, UK.10.1109/PDP.2013.52 ↗
41. Gantel, L., Layouni, S., Benkhelifa, M.E.A., Verdier, F., and Chauvet, S. (2009, January 9–11). Multiprocessor Task Migration Implementation in a Reconfigurable Platform. Proceedings of the ReConFig’09—2009 International Conference on ReConFigurable Computing and FPGAs, Cancun, Mexico.10.1109/ReConFig.2009.37 ↗
42. Prior Specification in Bayesian Statistics: Three Cautionary Tales10.1016/j.jtbi.2006.02.002 ↗
43. Barrios Hernández, C.J., Gitler, I., and Klapp, J. (2017). Communication-Aware Affinity Scheduling Heuristics in Multicore Systems, Communications in Computer and Information Science; Springer International Publishing.