Алгоритм построения расписаний выполнения параллельных задач на группах кластеров с процессорами различной производительности и его анализ в среднем

В работе рассмотрена задача построения расписаний выполнения параллельных вычислительных задач на группах кластеров с одинаковым числом w одинаковых процессоров, производительность которых для разных кластеров различная. Проведён вероятностный анализ задачи. Получены нижние оценки. Показано, что если число процессоров, необходимых для решения любой задачи имеет равномерное распределение на отрезке [o,w] для любого алгоритма составления расписаний величина математического ожидания свободного объёма вычислений равна Ω(w√N). Получены верхние оценки. Был предложен онлайновый алгоритм построения расписаний с распределением задач в ограниченные области Limited Hash Scheduling для задачи построения расписаний, работающий в режиме closed-end, с математическим ожиданием свободного объёма вычислений, равным O(w√(N ln N)).

построение расписаний, онлайновый алгоритм, режим closed-end, вероятностный анализ, процессоры различной производительности, алгоритм размещения задач в ограниченные области

1. . Aspens J., Azar Y., Fiat A., Plotkin S., Waarts O. On - line load balancing with applications to machine scheduling and virtual circuit routing. In Proc. of the 25th ACM STOC. 1993. pp. 623 - 631, DOI: 10.1145/167088.167248

2. . Berman P., Charikar M., Karpinski M. On-line load balancing for related machines. LNCS, v. 1272, 1997, pp. 116-125, DOI: https://doi.org/10.1007/3-540-63307-3_52

3. . С.Н. Жук. О построении расписаний выполнения параллельных задач на гуппах кластеров с различной производительностью. Труды ИСП РАН, том 23, 2012, стр. 447-454, DOI: 10.15514/ISPRAS-2012-23-27

4. . S.N. Zhuk. Approximate algorithms for packing rectangles into several strips. Discrete Mathematics and Applications, vol 18, issue 1, 2006, pp. 91-105, DOI: https://doi.org/10.1515/156939206776241264

5. . М.А. Трушников. Об одной задаче Коффмана-Шора, связанной с упаковкой прямоугольников в полосу. Труды ИСП РАН, том 22, 2012, стр. 456-462, DOI: 10.15514/ISPRAS-2012-22-24

6. . Лазарев Д. О., Кузюрин Н. Н. Алгоритм упаковки прямоугольников в несколько полос и анализ его точности в среднем. Труды ИСП РАН, том 29, вып. 6, 2017 г., стр. 221-228, DOI: 10.15514/ ISPRAS-2017-29(6)-13

7. . Трушников М. А. Вероятностный анализ нового алгоритма упаковки прямоугольников в полосу., Труды ИСП РАН, том 24, 2013, стр. 457-468, DOI: 10.15514/ISPRAS-2013-24-21

8. . Лазарев Д.О., Кузюрин Н.Н. Об онлайновых алгоритмах для задач упаковки в контейнеры и полосы, их анализе в худшем случае и в среднем. Труды ИСП РАН, том 30, вып. 4, 2018 г., стр. 209-230. DOI:10.15514/ISPRAS-2018-30(4)-14

9. . E. G. Coffman, C. Courcoubetis, M. R. Garey, D. S. Johnson, L. A. McGeoch, P. W. Shor, R. R. Weber, M. Yannakakis. Fundamental discrepancies between average-case analyses under discrete and continuous distributions: a bin packing case study. In Proc. of the twenty-third annual ACM Symposium on Theory of computing, 1991, pp. 230-240, doi:10.1145/103418.103446

10. . Кузюрин Н., Грушин Д., Фомин С. Проблемы двумерной упаковки и задачи оптимизации в распределенных вычислительных системах. Труды ИСП РАН, том 26, вып. 1, 2014 г., стр. 483–502, DOI: 10.15514/ISPRAS-2014-26(1)-21

11. . Ye D., Han X., Zhang G. Online multiple-strip packing. Theoretical Computer Science, Volume 412, Issue 3, 2011, pp. 233-239. DOI: https://doi.org/10.1016/j.tcs.2009.09.29

12. . Жук С.Н. Онлайновый алгоритм упаковки прямоугольников в несколько полос с гарантированными оценками точности. Труды ИСП РАН, том 12, 2007 г., стр. 7-16, ISSN 2079-8056

13. . Zhuk S.N. On-line algorithms for packing rectangles into several strips. Discrete Mathematics and Applications, vol. 17, issue 5, 2007, pp. 517-531. DOI: https://doi.org/10.1515/dma.2007.040

14. . Жук С.Н. О построении расписаний выполнения параллельных задач на группах кластеров с различной производительностью. Труды ИСП РАН, том 23, 2012 г., стр. 447-454. DOI: https://doi.org/10.15514/ISPRAS-2012-23-27

15. . Foster I., Kesselman C. The grid: Blueprint for a new computing infrastructure. Morgan Kaufmann Publishers Inc., 1999, 748 p.