Проблемы двумерной упаковки и задачи оптимизации в распределенных вычислительных системах
Аннотация
В статье рассмотрена задача управления потоками параллельных программ на группе вычислительных кластеров и формализации этого процесса в виде оптимизационной задачи упаковки набора прямоугольников в группу полубесконечных полос различной ширины (Multiple Strip Packing). Приводятся современные результаты по решению этой задачи и ряд открытых проблем. Рассмотрены практические аспекты оптимизации управления потоками параллельных задач с различными критериями оценки их качества, дается описание созданной в ИСП РАН системы моделирования предназначенной для экспериментального исследования алгоритмов управления, описаны ее возможности.
Список литературы
1. Graham R. L., Bounds for certain multiprocessor anomalies, Bell System Technical Journal, 1966, vol. 45, p. 1563–1581.
2. Baker B.S., Coffman E.J., Rivest R.L. Orthogonal packings in two-dimensions, SIAM J. Computing, 1980, V. 9, P. 846-855.
3. Bartal Y., Fiat A., Karloff H., Vohra R., New algorithms for an ancient scheduling problem, J. Comput. Syst. Sci., 1995, vol. 51, No 3, p. 359-366.
4. Karger D. R., Phillips S. J., Torng E., A better lower bound for on-line scheduling, Proc. of the 5th Annu. ACM-SIAM Symp. on Discrete Algorithms, 1994, p. 132–140.
5. Albers S., Better bounds for online scheduling, Proc. of the 29th ACM Symp. on Theory of Computing, 1997, p. 130-139.
6. Bartal Y., Karloff H., Rabani Y., A better algorithm for an ancient scheduling problem, Inf. Proces. Letters, 1994, vol. 50, p. 113–116.
7. Baker B.S., Schwarz J.S., Shelf algorithms for two dimensional packing problems, SIAM J. Computing, 1983, V. 12, P. 508-525.
8. Csirik J., Woeginger G.J. Shelf Algorithms for On-Line Strip Packing, Inf. Process. Lett., 1997, V. 63, N 4, P. 171-175.
9. Van Vliet A. An improved lower bound for on-line bin packing algorithms, Inf. Process. Lett., 1992, V. 43, P. 277–284.
10. X. Han, K. Iwama, D. Ye, G. Zhang, Strip Packing vs. Bin Packing, Algorithmic Aspects in Information and Management (AAIM), 2007, LNCS, 2009, V. 4508, P. 358-367.
11. Поспелов А.И., Анализ одного алгоритма упаковки прямоугольников, связанного с построением расписаний для кластеров, Труды ИСП РАН, М., 2004, т. 6, с. 7-12.
12. S. Zhuk, A. Chernykh, A. Avetisyan, S. Gaissaryan, D. Grushin, N. Kuzjurin, A. Pospelov, A. Shokurov, Comparison of scheduling heuristics for Grid resource broker, Proc. Fifth Mexican Int. Conf. in Computer Science, ENC'04, IEEE Computer Society, 2004, p. 388-392.
13. Жук С.Н., Анализ некоторых эвристик в задаче упаковки прямоугольников в несколько полос, Труды ИСП РАН, М., 2004, т. 6, с. 7-12.
14. С.Н. Жук. Приближенные алгоритмы упаковки прямоугольников в несколько полос, Дискретная математика, т.18, 2006, N , С. 91-105.
15. M. Caramia, S. Giordani, A. Iovanella, Grid scheduling by on-line rectangle packing, Networks, 2004, p. v. 44, N 2, p. 106-119.
16. С.Н. Жук. Об-онлайн алгоритмах упаковки прямоугольников в несколько полос, Дискретная математика, т.19, 2007, N 4, С. 117-131.
17. A. Tchernykh, J. Ramirez, A. Avetisyan, N. Kuzjurin, D. Grushin, S. Zhuk, Two level job-scheduling for a computational grid, PPAM, 2005, P. 774-781.
18. A. Tchernykh, U. Schwiegelshohn, R. Yahyapour, N. Kuzjurin. On-line Hierarchical Job Scheduling on Grids with Admissible Allocation, Proc. Euro-Par, 2008, LNCS, v.
19. A. Tchernykh, U. Schwiegelshohn, R. Yahyapour, N. Kuzjurin. On-line Hierarchical Job Scheduling on Grids with Admissible Allocation, Journal of Scheduling, 2010, v. 13, N 5, pp. 545-552.
20. D. Ye, X. Han, G. Zhang, Online multiple strip packing, Theor. Comp. Sci., 2011, V. 412, N 3, P. 233-239.
21. M. Bougert, P.F. Dutot, K. Jansen, C. Otte, D. Trystam, Approximation Algorithms for Multiple Strip Packing, Proc. WAOA-2009, LNCS, V. 5893, 2010, P. 37-48.
22. E. G. Coffman, Jr., P. W. Shor. Packings in two dimensions: Asymptotic average-case analysis of algorithms, Algorithmica, 1993, V. 9, P. 253-277.
23. E. G. Coffman, Jr., D. S. Johnson, P. W. Shor and G. S. Lueker. Probabilistic analysis of packing and related partitioning problems, Statistical Science, 1993, V. 8, P. 40-47.
24. P. W. Shor, The average-case analysis of some on-line algorithms for bin packing. Combinatorica, 1986, v. 6, 179-200.
25. P. W. Shor, How to pack better than Best Fit: Tight bounds for average-case on-line bin packing, Proc. 32nd Annual Symposium on Foundations of Computer Science, 1991, pp. 752-759.
26. Кузюрин Н.Н., Поспелов А.И., Вероятностный анализ шельфовых алгоритмов упаковки прямоугольников в полосу, Дискретная математика, 2006, т. 18, N 1, с. 76–90.
27. Н.Н. Кузюрин, А.И. Поспелов. Вероятностный анализ одного алгоритма упаковки прямоугольников в полосу. Труды Института системного программирования РАН, том 19, 2010 г. С. 157-164.
28. Н. Н. Кузюрин, А.И. Поспелов, Вероятностный анализ одного класса алгоритмов упаковки прямоугольников в полосу, Журнал вычислительной математики и математической физики, (ISSN 0044-4669), 2011, т. 51, N 10, C. 1931-1936.
29. М.А. Трушников. Об одной задаче Коффмана-Шора, связанной с упаковкой прямоугольников в полосу, Труды Института системного программирования РАН, том 22, 2012 г. ISSN 2220-6426 (Online), ISSN 2079-8156 (Print), С. 456-462.
30. М.А. Трушников. Вероятностный анализ нового алгоритма упаковки прямоугольников в полосу. Труды Института системного программирования РАН, том 24, 2013 г. ISSN 2220-6426 (Online), ISSN 2079-8156 (Print), С. 457-468.
31. Kuzjurin N.N., Trushnikov M.A., Average case analysis of a new class of on-line algorithms for Multiple Strip Packing, Proceedings of the 24th ECCO Conference of the European Chapter on Combinatorial Optimization, University of Amsterdam, May 30-June 1, p. 68-69.
32. С.Н. Жук. О построении расписаний выполнения параллельных задач на группах кластеров с различной производительностью, Труды Института системного программирования РАН, том 23, 2012 г. ISSN 2220-6426 (Online), ISSN 2079-8156 (Print), С. 447-454.
33. P. Berman, M. Charikar, M. Karpinski, On-line load balancing for related machines, J. of Algorithms, 2000, v. 35, N 1, p. 108-121.
34. Д.А. Грушин, А.И. Поспелов. Система моделирования Grid: реализация и возможности применения. Труды Института системного программирования РАН, том 18, 2010 г. С. 243-260.
35. D.G. Feitelson, L. Rudolph, Metrics and Benchmarking for Parallel Job Scheduling, Lecture Notes in Computer Science, 1998, v. 1459, p. 1+
36. warchive, Parallel Workloads Archive, http://www.cs.huji.ac.il/labs/parallel/workload/, dim, 2007.10.26
37. garchive, The Grid Workloads Archive, http://gwa.ewi.tudelft.nl/pmwiki/, dim, 2007.10.26
38. sharcnet, The Shared Hierarchical Academic Research Computing Network, www.sharcnet.ca
39. D. G. Feitelson, Workload Modeling for Computer Systems Performance Evaluation Book draft, 2005
40. В. П. Иванников, Д. А. Грушин, Н. Н. Кузюрин, А. И. Поспелов, А. В. Шокуров. Программная система увеличения энергоэффективности вычислительного кластера. Программирование, 2010, № 6, С. 28–40
41. Грушин Д.А., Кузюрин Н.Н., Энерго-эффективные вычисления на группе кластеров, Труды Института системного программирования РАН, том 23, 2012.
42. A. Grushin and N. N. Kuzyurin, Energy-Efficient Computing for a Group of Clusters, Programming and Computer Software, vol. 40, #6, 2013
43. М.А. Трушников. Об одной задаче построения энергосберегающих расписаний. Программирование, 2010, № 6.
44. Y. Sverdlik. Microsoft gets wind power for Dublin data center, http://www.datacenterdynamics.com. — 2011.
45. Ward Van Heddeghem, W. Vereeckena, D. Collea et al. Distributed computing for carbon footprint reduction by exploiting low-footprint energy availability, Future Generation Computer Systems. — 2012. — Vol. 28. — P. 405– 414.
46. Xu X., JiaxingWu G. Y., Wang R. Low-power task scheduling algorithm for large-scale cloud data centers, Journal of Systems Engineering and Electronics. – 2013. – Т. 24. – №. 5. – С. 870-878.
47. D.A. Grushin, N.N. Kuzyurin. Energy-efficient computations on a group of clusters. Proceedings of the Institute for System Programming of RAS, volume 23, 2012, pp. 433-446.
48. Y. Azar, N. Ben-Aroya, N.R. Devanur, N. Jain, Cloud Scheduling with Setup Cost, SPAA'13, June 23-25, 2013, Montreal, Canada.
Рецензия
Для цитирования:
Кузюрин Н.Н., Грушин Д.А., Фомин C.A. Проблемы двумерной упаковки и задачи оптимизации в распределенных вычислительных системах. Труды Института системного программирования РАН. 2014;26(1):483-502. https://doi.org/10.15514/ISPRAS-2014-26(1)-21
For citation:
Kuzyurin N.N., Grushin D.A., Fomin S.A. Two-dimensional packing problems and optimization in distributed computing systems. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(1):483-502. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(1)-21
Послать статью по эл. почте 