Multi-core processor scheduling with respect to the mutual influence of jobs

Authors

DOI:

https://doi.org/10.26089/NumMet.v24r108

Keywords:

multi-core processor, scheduling, mixed integer linear programming

Abstract

The paper deals with the problem of multi-core processor scheduling with respect to the mutual influence of jobs during their joint execution. A problem formulation and a model of mixed integer linear programming are proposed, the problem is shown to be NP-hard with the number of cores bounded by a constant. The results of the Intel TBB scheduler and the greedy algorithm are compared with the results obtained in accordance with the proposed model using the CPLEX package. The conducted experiment showed the advantages of the proposed approach in terms of the completion time of all jobs.

Author Biographies

Anton V. Eremeev

Sobolev Institute of Mathematics of SB RAS,
Omsk Department
• Chief Researcher

Maria Yu. Sakhno

Sobolev Institute of Mathematics of SB RAS,
Omsk Department
• PhD Student

References

  1. A. Merkel, J. Stoess, and F. Bellosa, “Resource-Conscious Scheduling for Energy Efficiency on Multicore Processors,” in Proc. 5th European Conf. on Computer Systems, Paris, France, April 13-16, 2010 (ACM Press, New York, 2010), pp. 153-166.
    doi 10.1145/1755913.1755930.
  2. S. Zhuravlev, S. Blagodurov, and A. Fedorova, “Addressing Shared Resource Contention in Multicore Processors via Scheduling,” Comput. Archit. News 38 (1), 129-142.
  3. Y. Jiang, X. Shen, J. Chen, and R. Tripathi, “Analysis and Approximation of Optimal Co-Scheduling on Chip Multiprocessors,” in Proc. 17th Int. Conf. on Parallel Architectures and Compilation Techniques, Toronto, Canada, October 25-29, 2008 (ACM Press, New York, 2008), pp. 220-229.
    doi 10.1145/1454115.1454146.
  4. Z. Xiao, L. Chen, B. Wang, et al., “Novel Fairness-aware Co-Scheduling for Shared Cache Contention Game on Chip Multiprocessors,” Inf. Sci. 526, 68-85 (2020).
    doi 10.1016/j.ins.2020.03.078.
  5. K. Tian, Y. Jiang, X. Shen, and W. Mao, Makespan Minimization for Job Co-Scheduling on Chip Multiprocessors , Technical Report WM-CS-2010-08 (College of William & Mary, Williamsburg, 2010).
  6. M. Liu, F. Chu, J. He, et al., “Coke Production Scheduling Problem: A Parallel Machine Scheduling with Batch Preprocessings and Location-Dependent Processing Times,” Comput. Oper. Res. 104, 37-48 (2019).
    doi 10.1016/j.cor.2018.12.002.
  7. A. Shioura, N. V. Shakhlevich, and V. A. Strusevich, “Preemptive Models of Scheduling with Controllable Processing Times and of Scheduling with Imprecise Computation: A Review of Solution Approaches,” Eur. J. Oper. Res. 266 (3), 795-818 (2018).
    doi 10.1016/j.ejor.2017.08.034.
  8. J. Jozefowska and J. Weglarz, “Scheduling with Resource Constraints -- Continuous Resources,” in Handbook of Scheduling: Algorithms, Models, and Performance Analysis (CRC Press, Boca Raton, 2004), pp. 24-1-24-15.
  9. J. Blazewicz, N. Brauner, and G. Finke, “Scheduling with Discrete Resource Constraints,” in Handbook of Scheduling: Algorithms, Models, and Performance Analysis (CRC Press, Boca Raton, 2004), pp. 23-1-23-18.
  10. A. V. Eremeev, A. A. Malakhov, M. A. Sakhno, and M. Y. Sosnovskaya, “Multi-core Processor Scheduling with Respect to Data Bus Bandwidth,” in Communications in Computer and Information Science (Springer, Cham, 2020), Vol. 1340, pp. 55-69.
    doi 10.1007/978-3-030-65739-0_5.
  11. E. Althaus, A. Brinkmann, P. Kling, et al., “Scheduling Shared Continuous Resources on Many-cores,” J. Sched. 21 (1), 77-92 (2018).
    doi 10.1007/s10951-017-0518-0.
  12. M. G. Ierapetritou and C. A. Floudas, “Effective Continuous-Time Formulation for Short-Term Scheduling: I. Multipurpose Batch Processes,” Ind. Eng. Chem. Res. 37 (11), 4341-4359 (1998).
    doi 10.1021/ie970927g
  13. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, San Francisco, 1979).
  14. Intel TBB Library.
    https://github.com/oneapi-src/oneTBB . Cited February 9, 2023.

Downloads

Published

03-03-2023

How to Cite

Еремеев А.В., Сахно М.Ю. Multi-Core Processor Scheduling With Respect to the Mutual Influence of Jobs // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2023. 24. 115-126. doi 10.26089/NumMet.v24r108

Issue

Vol. 24 (2023): Issue 1.

Section

Parallel software tools and technologies

License

Copyright (c) 2023 А. В. Еремеев, М. Ю. Сахно

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.