Построение расписания для многоядерного процессора с учетом взаимного влияния работ
DOI:
https://doi.org/10.26089/NumMet.v24r108Ключевые слова:
многоядерный процессор, построение расписаний, частично целочисленное линейное программированиеАннотация
В статье рассматривается задача планирования работ на многоядерном процессоре с учетом их замедления при совместном выполнении. Предложена постановка задачи и модель частично целочисленного линейного программирования, доказана NP-трудность задачи при числе ядер, ограниченном константой. Результаты планировщика Intel TBB и жадного алгоритма сравниваются с результатами, полученными в соответствии с предложенной моделью с помощью пакета CPLEX. Проведенный эксперимент показал преимущества предложенного подхода по времени завершения всех работ.
Библиографические ссылки
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.
S. Zhuravlev, S. Blagodurov, and A. Fedorova, “Addressing Shared Resource Contention in Multicore Processors via Scheduling,” Comput. Archit. News 38 (1), 129-142.
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.
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.
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).
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.
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.
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.
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.
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.
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.
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
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, San Francisco, 1979).
Intel TBB Library.
https://github.com/oneapi-src/oneTBB . Cited February 9, 2023.
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Copyright (c) 2023 А. В. Еремеев, М. Ю. Сахно
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
