A note on the complexity of scheduling of communication-aware directed acyclic graph

• Autorzy: Musial J. , Guzek M. , Bouvry P. , Blazewicz J.

Identyfikatory

DOI

10.24425/122099

• Języki publikacji: EN

Abstrakty

EN

The most recent incarnation of distributed paradigm is cloud computing. It can be seen as the first widely accepted business model of mass consumption of the distributed computing resources. Despite the differences in business models and technical details regarding cloud platforms, the distributed computing underlies cloud. Communications in cloud systems include transmissions of the results of cloud applications, users interactions, and exchange of data between different services that compose applications. The latter becomes more critical as applications become richer as well as more complex, and may consist of services operated by various providers. The effective communication between components of cloud systems is thus critical to the end user satisfaction and to the success of cloud services. We will discuss different cloud computing models (communication aware and unaware). Main focus will be placed on communication-aware directed acyclic graph (CA-DAG), which extends the classical DAG model by explicitly modeling communication tasks. Moreover, we will analyze and consult computational complexity of this innovative distributed computation model inspired by the characteristics of cloud computing. Providing a proof of strong NP-hardness of the problem allows for a future implementation and evolution of the communication-aware DAG models.

Słowa kluczowe

EN

computational complexity; cloud computing; communication-aware cloud computing; directed acyclic graph; NP-hardness in cloud computing

PL

złożoność obliczeniowa; chmura obliczeniowa; skierowany graf acykliczny

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2018
• Tom: Vol. 66, nr 2
• Strony: 187--191
• Opis fizyczny: Bibliogr. 26 poz., rys.

Twórcy

autor

Musial J.

• Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965 Poznan, Poland

autor

Guzek M.

• Comp. Sci. and Commun. Res. Unit, University of Luxembourg, 6 Avenue de la Fonte, L-4364 Esch-sur-Alzette, Luxembourg

autor

Bouvry P.

• Comp. Sci. and Commun. Res. Unit, University of Luxembourg, 6 Avenue de la Fonte, L-4364 Esch-sur-Alzette, Luxembourg

autor

Blazewicz J.

• Institute of Bioorganic Chemistry, Polish Academy of Sciences, Z. Noskowskiego 12/14, 61-704 Poznan, Poland
• Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965 Poznan, Poland

Bibliografia

• [1] J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt, and J. Weglarz, Handbook on Scheduling – From Theory to Applications, Springer Verlag, Berlin, New York (2007).
• [2] M. Drozdowski, Scheduling for Parallel Processing, Springer London (2009).
• [3] N. Christofides, Graph Theory: An Algorithmic Approach (Computer Science and Applied Mathematics), Academic Press, Inc., Orlando, FL, USA (1975).
• [4] P. Mell and T. Grance, “The NIST definition of cloud computing”, National Institute of Standards and Technology 53 (6), 50 (2009).
• [5] M. Armbrust, A. Fox, R. Griffith, A. Joseph, R. Katz, A. Konwinski, G. Lee, D. Patterson, A. Rabkin, I. Stoica, and M. Zaharia, “A view of cloud computing”, Communications of the ACM 53 (4), 50–58 (2010).
• [6] L. Columbus, “Roundup Of Cloud Computing Forecasts And Market Estimates, 2016”, www.forbes.com/sites/louiscolumbus/2016/03/13/roundupof-cloud-computing-forecasts-and-market-estimates-2016, accessed: 2016‒06‒16.
• [7] D. Kliazovich, J.E. Pecero, A. Tchernykh, P. Bouvry, S.U. Khan, and A. Y. Zomaya, “CA-DAG: Modeling Communication-Aware Applications for Scheduling in Cloud Computing”, Journal of Grid Computing 14 (1), 23–39 (2016).
• [8] M. Guzek, P. Bouvry, and E.-G. Talbi, “A Survey of Evolutionary Computation for Resource Management of Processing in Cloud Computing [Review Article]”, IEEE Computational Intelligence Magazine 10 (2), 53–67 (2015).
• [9] M. Guzek, A. Gniewek, P. Bouvry, J. Musial, and J. Blazewicz, “Cloud Brokering: Current Practices and Upcoming Challenges”, IEEE Cloud Computing 2 (2), 40–47 (2015).
• [10] J. Blazewicz, N. Cheriere, P.-F. Dutot, J. Musial, and D. Trystram, “Novel dual discounting functions for the Internet shopping optimization problem: new algorithms”, Journal of Scheduling 19 (3), 245–255 (2016).
• [11] J. Blazewicz, P. Bouvry, M.Y. Kovalyov, and J. Musial, “Internet shopping with price sensitive discounts”, 4OR – A Quarterly Journal of Operations Research 12 (1), 35–48 (2014).
• [12] J. Blazewicz, P. Bouvry, M.Y. Kovalyov, and J. Musial, “Erratum to: Internet shopping with price-sensitive discounts”, 4ORA Quarterly Journal of Operations Research 12 (4), 403–406 (2014).
• [13] J. Blazewicz and J. Musial, “E-Commerce Evaluation – Multi-Item Internet Shopping. Optimization and Heuristic Algorithms”, in Operations Research Proceedings 2010 (edited by B. Hu, K. Morasch, S. Pickl, and M. Siegle), Springer- Verlag, Berlin, 149–154 (2011).
• [14] M. Zotkiewicz, M. Guzek, D. Kliazovich, and P. Bouvry, “Minimum Dependencies Energy-Efficient Scheduling in Data Centers”, IEEE Transactions on Parallel and Distributed Systems PP (99) (2016).
• [15] J. Leung, L. Kelly, and J. H. Anderson, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, Inc., Boca Raton, FL, USA (2004).
• [16] H. El-Rewini and T.G. Lewis, “Scheduling Parallel Program Tasks Onto Arbitrary Target Machines”, J. Parallel Distrib. Comput. 9 (2), 138–153 (1990).
• [17] C.H. Papadimitriou and M. Yannakakis, “Towards an Architecture-independent Analysis of Parallel Algorithms”, SIAM J. Comput. 19 (2), 322–328 (1990).
• [18] O. Sinnen and L.A. Sousa, “Communication contention in task scheduling”, IEEE Transactions on Parallel and Distributed Systems 16 (6), 503–515 (2005).
• [19] D.E. Culler, R.M. Karp, D. Patterson, A. Sahay, E.E. Santos, K.E. Schauser, R. Subramonian, and T. von Eicken, “LogP: A Practical Model of Parallel Computation”, Commun. ACM 39 (11), 78–85 (1996).
• [20] G. Srikanth, A. Shanthi, V. Maheswari, and A. Siromoney, “A Survey on Real Time Task Scheduling”, Eur. J. Sci. Res. 69 (1), 33–41 (2012).
• [21] P. Choudhury, P.P. Chakrabarti, and R. Kumar, “Online Scheduling of Dynamic Task Graphs with Communication and Contention for Multiprocessors”, IEEE Transactions on Parallel and Distributed Systems 23 (1), 126–133 (2012).
• [22] R. Graham, E. Lawler, J. Lenstra, and A. Rinnooy Kan, “Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey”, in Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium co-sponsored by IBM Canada and SIAM Banff, Aha. and Vancouver (edited by E. J.P.L. Hammer and B. Korte), volume 5 of Annals of Discrete Mathematics, Elsevier, 287–326 (1979).
• [23] J. Blazewicz, J. Lenstra, and A. Rinnooy Kan, “Scheduling subject to resource constraints: classification and complexity”, Discrete Applied Mathematics 5 (1), 11 – 24 (1983).
• [24] M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, New York, Freeman (1979).
• [25] M.C. Lopez-Loces, J. Musial, J. E. Pecero, H.J. Fraire-Huacuja, J. Blazewicz, and P. Bouvry, “Exact and heuristic approaches to solve the Internet shopping optimization problem with delivery costs”, International Journal of Applied Mathematics and Computer Science 26 (2), 391–406 (2016).
• [26] J. Musial, J.E. Pecero, M.C. Lopez-Loces, H.J. Fraire-Huacuja, P. Bouvry, and J. Blazewicz, “Algorithms solving the Internet shopping optimization problem with price discounts”, Bull. Pol. Ac.: Tech. 64 (3), 505–516 (2016).

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).