Построение расписания для многоядерного процессора с учетом взаимного влияния работ

Авторы

DOI:

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

Ключевые слова:

многоядерный процессор, построение расписаний, частично целочисленное линейное программирование

Аннотация

В статье рассматривается задача планирования работ на многоядерном процессоре с учетом их замедления при совместном выполнении. Предложена постановка задачи и модель частично целочисленного линейного программирования, доказана NP-трудность задачи при числе ядер, ограниченном константой. Результаты планировщика Intel TBB и жадного алгоритма сравниваются с результатами, полученными в соответствии с предложенной моделью с помощью пакета CPLEX. Проведенный эксперимент показал преимущества предложенного подхода по времени завершения всех работ.

Авторы

А. В. Еремеев

Институт математики имени С. Л. Соболева СО РАН,
Омский филиал
ул. Певцова, 13, 644043, Омск
• главный научный сотрудник

М. Ю. Сахно

Институт математики имени С. Л. Соболева СО РАН (ИМ СО РАН),
Омский филиал
ул. Певцова, 13, 644043, Омск
• аспирант

Библиографические ссылки

  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.

Загрузки

Опубликован

03-03-2023

Как цитировать

Еремеев А.В., Сахно М.Ю. Построение расписания для многоядерного процессора с учетом взаимного влияния работ // Вычислительные методы и программирование. 2023. 24. 115-126. doi 10.26089/NumMet.v24r108

Выпуск

Том 24 (2023): Выпуск 1.

Раздел

Параллельные программные средства и технологии

Лицензия

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

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.