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

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

Авторы

  • А. В. Еремеев
  • М. Ю. Сахно

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

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

Аннотация

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

Загрузки

Опубликован

2023-03-03

Выпуск

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

Раздел

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

Авторы

А. В. Еремеев

Институт математики имени С. Л. Соболева СО РАН,
Омский филиал
ул. Певцова, 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.

Лицензия

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

Лицензия Creative Commons

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