Two-dimensional packing problems and optimization in distributed computing systems
https://doi.org/10.15514/ISPRAS-2014-26(1)-21
Abstract
In this paper the problem of scheduling parallel tasks on a group of clusters and formalization of this process as an optimization of packing rectangles in a set of strips of different widths is considered (Multiple Strip Packing). Some modern results concerning this problem and some open problems are presented. Practical aspects of optimization of scheduling parallel tasks process with different criteria of its quality are considered. The description of modeling system developed in the ISP RAS for experimental investigation of scheduling algorithms is presented and its properties are described.
About the Authors
N. N. Kuzyurin
Institute for System Programming of RAS
Russian Federation
Russian Federation
D. A. Grushin
Institute for System Programming of RAS
Russian Federation
Russian Federation
S. A. Fomin
Institute for System Programming of RAS
Russian Federation
Russian Federation
References
1. [1]. Graham R. L., Bounds for certain multiprocessor anomalies, Bell System Technical Journal, 1966, vol. 45, p. 1563–1581.
2. [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. [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. [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. [5]. Albers S., Better bounds for online scheduling, Proc. of the 29th ACM Symp. on Theory of Computing, 1997, p. 130-139.
6. [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. [7]. Baker B.S., Schwarz J.S., Shelf algorithms for two dimensional packing problems, SIAM J. Computing, 1983, V. 12, P. 508-525.
8. [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. [9]. Van Vliet A. An improved lower bound for on-line bin packing algorithms, Inf. Process. Lett., 1992, V. 43, P. 277–284.
10. [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. [11]. Pospelov А.I., Аnaliz odnogo algoritma upakovki pryamougol'nikov, svyazannogo s postroeniem raspisanij dlya klasterov [Analysis of cluster scheduling packing algorithm], Trudy ISP RАN [The Proceedings of ISP RAS], M., 2004, vol. 6, p. 7-12. (in Russian)
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. [13]. Zhuk S.N., Аnaliz nekotorykh ehvristik v zadache upakovki pryamougol'nikov v neskol'ko polos [Analysis of some heuristics in multiple rectangle packing problem], Trudy ISP RАN [The Proceedings of ISP RAS], M., 2004, vol. 6, p. 7-12. (in Russian)
14. [14]. S.N. Zhuk. Priblizhennye algoritmy upakovki pryamougol'nikov v neskol'ko polos [Approximate algorithms of packing rectangles into several stripes], Diskretnaya matematika [Discrete mathematics], vol.18, 2006, p. 91-105 (in Russian).
15. [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. [16]. S.N. Zhuk. Ob onlajn algoritmakh upakovki pryamougol'nikov v neskol'ko polos [Online algorithms for packing rectangles into several stripes], Diskretnaya matematika [Discrete mathematics], vol.19, 2007, N 4, p. 117-131 (in Russian).
17. [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. [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. [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. [20]. D. Ye, X. Han, G. Zhang, Online multiple strip packing, Theor. Comp. Sci., 2011, V. 412, N 3, P. 233-239.
21. [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. [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. [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. [24]. P. W. Shor, The average-case analysis of some on-line algorithms for bin packing. Combinatorica, 1986, v. 6, 179-200.
25. [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. [26]. Kuzyurin N.N., Pospelov А.I., Veroyatnostnyj analiz shel'fovykh algoritmov upakovki pryamougol'nikov v polosu [Probability analysis of shelf algorithms packing rectangles into several stripes], Diskretnaya matematika [Discrete mathematics], 2006, vol. 18, N 1, p. 76–90. (in Russian)
27. [27]. N.N. Kuzyurin, А.I. Pospelov. Veroyatnostnyj analiz odnogo algoritma upakovki pryamougol'nikov v polosu [Probability analysis of multiple rectangle packing problem]. Trudy Instituta sistemnogo programmirovaniya RАN [The Proceedings of ISP RAS], vol 19, 2010 g. p. 157-164. (in Russian)
28. [28]. N. N. Kuzyurin, А.I. Pospelov, Veroyatnostnyj analiz odnogo klassa algoritmov upakovki pryamougol'nikov v polosu [Probability analysis of one class of algorithms for packing rectangles into several stripes], ZHurnal vychislitel'noj matematiki i matematicheskoj fiziki [Journal of computational mathematics], (ISSN 0044- 4669), 2011, vol. 51, N 10, p. 1931-1936. (in Russian)
29. [29]. M.А. Trushnikov. Ob odnoj zadache Koffmana-SHora, svyazannoj s upakovkoj pryamougol'nikov v polosu [About one Koffman-Shore problem of packing rectangle into stripe], Trudy Instituta sistemnogo programmirovaniya RАN [The Proceedings of ISP RAS], vol 22, 2012 g. ISSN 2220-6426 (Online), ISSN 2079-8156 (Print), p. 456-462. DOI: 10.15514/ISPRAS-2012-22-24. (in Russian)
30. [30]. M.А. Trushnikov. Veroyatnostnyj analiz novogo algoritma upakovki pryamougol'nikov v polosu [Probability analysis of new algorithm for packing rectangles into stripe]. Trudy Instituta sistemnogo programmirovanya RАN [The Proceedings of ISP RAS], vol 24, 2013 g. ISSN 2220-6426 (Online), ISSN 2079-8156 (Print), DOI: 10.15514/ISPRAS-2013-24-21, p. 457-468. (in Russian)
31. [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. [32]. S.N. Zhuk. O postroenii raspisanij vypolneniya parallel'nykh zadach na gruppakh klasterov s razlichnoj proizvoditel'nost'yu [About building schedule for parallel tasks on a group of clusters with different performance], Trudy Instituta sistemnogo programmirovaniya RАN [The Proceedings of ISP RAS], vol 23, 2012 g. ISSN 2220-6426 (Online), ISSN 2079-8156 (Print), DOI: 10.15514/ISPRAS-2012-23-27, p. 447-454. (in Russian)
33. [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. [34]. D.А. Grushin, А.I. Pospelov. Sistema modelirovaniya Grid: realizatsiya i vozmozhnosti primeneniya [Grid modelling system: implementation and application]. Trudy Instituta sistemnogo programmirovaniya RАN [The Proceedings of ISP RAS], vol 18, 2010 g. p. 243-260. (in Russian)
35. [35]. D.G. Feitelson, L. Rudolph, Metrics and Benchmarking for Parallel Job Scheduling, Lecture Notes in Computer Science, 1998, v. 1459
36. [36]. warchive, Parallel Workloads Archive, http://www.cs.huji.ac.il/labs/parallel/workload/, dim, 2007.10.26
37. [37]. garchive, The Grid Workloads Archive, http://gwa.ewi.tudelft.nl/pmwiki/, dim, 2007.10.26
38. [38]. sharcnet, The Shared Hierarchical Academic Research Computing Network, www.sharcnet.ca
39. [39]. D. G. Feitelson, Workload Modeling for Computer Systems Performance Evaluation Book draft, 2005
40. [40]. V. P. Ivannikov, D. А. Grushin, N. N. Kuzyurin, А. I. Pospelov, А. V. SHokurov. Programmnaya sistema uvelicheniya ehnergoehffektivnosti vychislitel'nogo klastera [Software system for enhancing energy efficiency of a cluster]. Programmirovanie [Programming and ComputerSoftware], 2010, No 6, p. 28–40
41. [41]. Grushin D.A., Kuzjurin N.N., Jenergo-jeffektivnye vychislenija na gruppe klasterov [Energy-efficient computations on a group of clusters], Trudy ISP RAN [The Proceedings of ISP RAS], tom 23, 2012. DOI: 10.15514/ISPRAS-2012-23-26.
42. [42]. A. Grushin and N. N. Kuzyurin, Energy-Efficient Computing for a Group of Clusters, Programming and Computer Software, vol. 40, #6, 2013
43. [43]. M. A. Trushnikov. On one problem of construction of energy-saving schedules. Programming and Computer Software, November 2010, Volume 36, Issue 6, pp 337-342.
44. [44]. Y. Sverdlik. Microsoft gets wind power for Dublin data center, http://www.datacenterdynamics.com. — 2011.
45. [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. [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. [47]. D.A. Grushin, N.N. Kuzyurin. Energy-efficient computations on a group of clusters. The Proceedings of ISP RAS, volume 23, 2012, pp. 433-446.
48. [48]. Y. Azar, N. Ben-Aroya, N.R. Devanur, N. Jain, Cloud Scheduling with Setup Cost, SPAA'13, June 23-25, 2013, Montreal, Canada.
Review
For citations:
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
Email this article 