Приближённый алгоритм распределения заданий по неоднородным процессорам с задержками при передаче данных

Приближённый алгоритм распределения заданий по неоднородным процессорам с задержками при передаче данных

Демаков А. В., Кононов А. В.
Дискретный анализ и исследование операций, 32, 4, 118-137 (2025)
Скачать статью

УДК 519.8 
DOI: 10.33048/daio.2025.32.816

Аннотация:

Изучается задача распределения заданий по вычислительным серверам с учётом начальной загрузки данных для их выполнения. Назначение задания на сервер, который не содержит нужного блока данных, ведёт к расходам времени на передачу блока по сети. Чем больше блоков передаётся по сети, тем больше добавка к длительности задания. Требуется минимизировать общее время выполнения всех заданий. 

Для рассматриваемой задачи предложен 2-приближённый алгоритм, который использует решение задачи линейного программирования и достройку дробного решения до целого. Для вычислительных экспериментов рассмотрена ускоренная версия алгоритма. Проведены вычислительные эксперименты, которые показали, что алгоритм по качеству ответов сопоставим с известными алгоритмами. 

Ил. 7, библиогр. 16.

Литература:
  1. Garey M. R., Johnson D. S. “Strong” NP-completeness results: Motivation, examples, and implication // J. ACM. 1978. V. 25, No. 3. P. 499–508.
     
  2. Potts C. N. Analysis of a linear programming heuristic for scheduling unrelated parallel machines // Discrete Appl. Math. 1985. V. 10, No. 2. P. 155–164.
     
  3. Lenstra J. K., Shmoys D. B., Tardos É. Approximation algorithms for scheduling unrelated parallel machines // Math. Program. 1990. V. 46. P. 259–271.
     
  4. Fischer M. J., Su X., Yin Y. Assigning tasks for efficiency in Hadoop: Extended abstract // Proc. 22nd Annu. ACM Symp. Parallelism in Algorithms and Architectures (Thira Santorini, Greece, June 13–15, 2010). New York: ACM, 2010. P. 30–39. DOI: 10.1145/1810479.1810484.
     
  5. Jin J., Luo J., Song A., Dong F., Xiong R. BAR: An efficient data locality driven task scheduling algorithm for cloud computing // Proc. 11th IEEE/ACM Int. Symp. Cluster, Cloud and Grid Computing (Newport Beach, USA, May 23–26, 2011). Washington: IEEE Comput. Soc., 2011. P. 295–304. DOI: 10.1109/CCGrid.2011.55.
     
  6. Kwon Y., Balazinska M., Howe B., Rolia J. A study of skew in MapReduce applications // Proc. Open Cirrus Summit 2011 (Moscow, Russia, June 1–3, 2011). Piscataway: IEEE, 2011. P. 1–5.
     
  7. Brin S., Page L. The anatomy of a large-scale hypertextual Web search engine // Comput. Netw. ISDN Syst. 1998. V. 30, No. 1–7. P. 107–117.
     
  8. Gates A. F., Natkovich O., Chorpa S. [et al.]. Building a high-level dataflow system on top of Map-Reduce: The Pig experience // Proc. VLDB Endow. 2009. V. 2, No. 2. P. 1414–1425.
     
  9. Moseley B., Dasgupta A., Kumar R., Sarlós T. On scheduling in mapreduce and flow-shops // Proc. 23rd Annu. ACM Symp. Parallelism in Algorithms and Architectures (San Jose, CA, USA, June 4–6, 2011). New York: ACM, 2011. P. 289–298. DOI: 10.1145/1989493.1989540.
     
  10. Dean J., Ghemawat S. MapReduce: Simplified data processing on large clusters // Commun. ACM. 2008. V. 51, No. 1. P. 107–113. DOI: 10.1145/1327452.1327492.
     
  11. Танаев В. С., Гордон В. С., Шафранский Я. М. Теория расписаний: Одностадийные системы. М.: Наука, 1984. 384 с.
     
  12. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
     
  13. Vazirani V. V. Approximation algorithms. Heidelberg: Springer, 2001. 396 p.
     
  14. Хачиян Л. Г. Полиномиальные алгоритмы в линейном программировании // Журн. вычисл. математики и мат. физики. 1980. Т. 20, № 1. С. 51–68.
     
  15. Bestuzheva K., Besançon M., Chen W.-K. [et al.]. Enabling research through the SCIP Optimization Suite 8.0 // ACM Trans. Math. Softw. 2023. V. 49, No. 2. Article ID 22. 21 p. DOI: 10.1145/3585516.
     
  16. White T. Hadoop: The definitive guide. Sebastopol, CA: O’Reilly Media, 2015. 756 p.

Работа первого автора выполнена в рамках подготовки ВКР магистра под руководством второго автора в Новосибирском гос. университете. Работа второго автора выполнена в рамках гос. задания Института математики им. С. Л. Соболева (проект № FWNF–2022–0019). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Демаков Алексей Владимирович
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: a.demakov@g.nsu.ru 

Кононов Александр Вениаминович
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: alvenko@math.nsc.ru 

Статья поступила 22 октября 2024 г.
После доработки — 20 августа 2025 г.
Принята к публикации 22 сентября 2025 г.

Abstract:

We consider a problem of assigning tasks to computing servers taking into account the initial download of data for their execution. Assigning a task to a server that does not contain a required data block will take time to pass the block over the network. The more blocks are transmitted over the network, the more time is added to the task. The total time of all tasks is to be minimized. 

For the problem under consideration, we propose a 2-approximate algorithm. Using a solution of some linear programming problem, this algorithm completes a fractional solution to an integer one. For computational experiments an enhanced version of the algorithm is considered. The computational experiments showed that the algorithm is comparable with some known algorithms in the quality of solution obtained. 

Illustr. 7, bibliogr. 16.

References:
  1. S. Brin and L. Page, The anatomy of a large-scale hypertextual Web search engine, Comput. Netw. ISDN Syst. 30 (1–7), 107–117 (1998).
     
  2. M. R. Garey and D. S. Johnson, “Strong” NP-completeness results: Motivation, examples, and implication, J. ACM 25 (3), 499–508 (1978).
     
  3. A. F. Gates, O. Natkovich, S. Chorpa, [et al.], Building a high-level dataflow system on top of Map-Reduce: The Pig experience, Proc. VLDB Endow. 2 (2), 1414–1425 (2009).
     
  4. J. Dean and S. Ghemawat, MapReduce: Simplified data processing on large clusters, Commun. ACM 51 (1), 107–113 (2008), DOI: 10.1145/1327452. 1327492.
     
  5. M. J. Fischer, X. Su, and Y. Yin, Assigning tasks for efficiency in Hadoop: Extended abstract, in Proc. 22nd Annu. ACM Symp. Parallelism in Algorithms and Architectures (Thira Santorini, Greece, June 13–15, 2010) (ACM, New York, 2010), pp. 30–39, DOI: 10.1145/1810479.1810484.
     
  6. J. Jin, J. Luo, A. Song, F. Dong, and R. Xiong, BAR: An efficient data locality driven task scheduling algorithm for cloud computing, in Proc. 11th IEEE/ACM Int. Symp. Cluster, Cloud and Grid Computing (Newport Beach, USA, May 23–26, 2011) (IEEE Comput. Soc., Washington, 2011), pp. 295–304, DOI: 10.1109/CCGrid.2011.55.
     
  7. Y. Kwon, M. Balazinska, B. Howe, and J. Rolia, A study of skew in MapReduce applications, in Proc. Open Cirrus Summit 2011 (Moscow, Russia, June 1–3, 2011) (IEEE, Piscataway, 2011), pp. 1–5.
     
  8. B. Moseley, A. Dasgupta, R. Kumar, and T. Sarlós, On scheduling in map-reduce and flow-shops, in Proc. 23rd Annu. ACM Symp. Parallelism in Algorithms and Architectures (San Jose, CA, USA, June 4–6, 2011) (ACM, New York, 2011), pp. 289–298, DOI: 10.1145/1989493.1989540.
     
  9. J. K. Lenstra, D. B. Shmoys, and É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Math. Program. 46, 259–271 (1990).
     
  10. C. N. Potts, Analysis of a linear programming heuristic for scheduling unrelated parallel machines, Discrete Appl. Math. 10 (2), 155–164 (1985).
     
  11. V. S. Tanaev, V. S. Gordon, and Ya. M. Shafranskii, Scheduling Theory: Single-Stage Systems (Nauka, Moscow, 1984) [Russian].
     
  12. M. R. Garey and D. S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]).
     
  13. V. V. Vazirani, Approximation Algorithms (Springer, Heidelberg, 2001).
     
  14. L. G. Khachiyan, Polynomial algorithms in linear programming, Zh. Vychisl. Mat. Mat. Fiz. 20 (1), 51–68 (1980) [Russian] [USSR Comput. Math. Math. Phys. 20 (1), 53–72 (1980), DOI: 10.1016/0041-5553(80)90061-0].
     
  15. K. Bestuzheva, M. Besançon, W.-K. Chen, [et al.], Enabling research through the SCIP Optimization Suite 8.0, ACM Trans. Math. Softw. 49 (2), ID 22 (2023), DOI: 10.1145/3585516.
     
  16. T. White, Hadoop: The Definitive Guide (O’Reilly Media, Sebastopol, CA, 2015).