nach oben

Cluster Computing

Erschienen in:

01.12.2014

Towards a systematic approach to the dynamic adaptation of structured parallel computations using model predictive control

verfasst von: Gabriele Mencagli, Marco Vanneschi

Erschienen in: Cluster Computing | Ausgabe 4/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Adaptiveness is an essential feature for distributed parallel applications executed on dynamic environments like Grids and Clouds. Being adaptive means that parallel components can change their configuration at run-time (by modifying their parallelism degree or switching to a different parallel variant) to face irregular workload or to react to uncontrollable changes of the execution platform. A critical problem consists in the definition of adaptation strategies able to select optimal reconfigurations (minimizing operating costs and reconfiguration overhead) and achieve the stability of control decisions (avoiding unnecessary reconfigurations). This paper presents an approach to apply Model Predictive Control (a form of optimal control studied in Control Theory) to adaptive parallel computations expressed according to the Structured Parallel Programming methodology. We show that predictive control is amenable to achieve stability and optimality by relying on the predictability of structured parallelism patterns and the possibility to express analytical cost models of their QoS metrics. The approach has been exemplified on two case-studies, providing a first assessment of its potential and feasibility.

Vorheriger Artikel Reexamining anomaly temporal behaviors in SPEC CPU workloads: self-similar or not?

Nächster Artikel DF++ : an adaptive buffer-aware probabilistic delegation forwarding protocol for Delay Tolerant Network

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Abdelwahed, S., Kandasamy, N., Neema, S.: Online control for self-management in computing systems. In: Real-Time and Embedded Technology and Applications Symposium, 2004. Proceedings. RTAS 2004. 10th IEEE, pp. 368–375 (2004)

Aldinucci, M., Danelutto, M., Kilpatrick, P.: Towards hierarchical management of autonomic components: a case study. In: 2009 17th Euromicro International Conference on Parallel, Distributed and Network-based Processing, pp. 3–10 (2009). doi:10.1109/PDP.2009.48

Aldinucci, M., Danelutto, M., Teti, P.: An advanced environment supporting structured parallel programming in java. In: Future Generation Computer Systems 19(5), pp. 611–626 (2003). Tools for Program Development and Analysis. Best papers from two Technical Sessions, at ICCS2001, San Francisco, CA, USA, and ICCS2002, Amsterdam, The Netherlands (2003)

Arshad, N., Heimbigner, D., Wolf, A.L.: Deployment and dynamic reconfiguration planning for distributed software systems. Softw. Qual. Control 15(3), 265–281 (2007)CrossRef

Bacci, B., Danelutto, M., Orlando, S., Pelagatti, S., Vanneschi, M.: P3l: a structured high-level parallel language, and its structured support. Concurrency 7(3), 225–255 (1995)CrossRef

Bacci, B., Danelutto, M., Pelagatti, S., Vanneschi, M.: A heterogeneous environment for hpc applications. Parallel Comput. 25(13–14), 1827–1852 (1999)CrossRef

Beloglazov, A., Abawajy, J., Buyya, R.: Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing. Fut. Gener. Comput. Syst. 28(5), 755–768 (2012). Special Section: Energy efficiency in large-scale distributed systemsCrossRef

Bernini, D., Micucci, D., Tisato, F.: Space integration services: a platform for space-aware communication. In: IWCMC ’10: Proceedings of the 6th International Wireless Communications and Mobile Computing Conference, pp. 489–493. ACM, New York, NY, USA (2010). http://doi.acm.org/10.1145/1815396.1815510

Bertolli, C., Buono, D., Lametti, S., Mencagli, G., Meneghin, M., Pascucci, A., Vanneschi, M.: A programming model for high-performance adaptive applications on pervasive mobile grids. In: Proceeding of the 21st IASTED International Conference on Parallel and Distributed Computing and Systems, pp. 38–54 (2009)

10.

Bertolli, C., Buono, D., Mencagli, G., Vanneschi, M.: Expressing adaptivity and context-awareness in the assistant programming model. In: Proceedings of the Third International ICST Conference on Autonomic Computing and Communication Systems, pp. 38–54 (2009)

11.

Bertolli, C., Mencagli, G., Vanneschi, M.: Adaptivity in risk and emergency management applications on pervasive grids. In: Proceeding of the 10th International Symposium on Pervasive Systems, Algorithms, and Networks, p. to appear (2009)

12.

Bertolli, C., Mencagli, G., Vanneschi, M.: Analyzing memory requirements for pervasive grid applications. In: Parallel, Distributed, and Network-Based Processing, Euromicro Conference on pp. 297–301 (2010)

13.

Bhavanishankar, R., Subramaniam, C., Kumar, M., Dugar, D.: A context aware approach to emergency management systems. In: IWCMC ’09: Proceedings of the 2009 International Conference on Wireless Communications and Mobile Computing, pp. 1350–1354. ACM, New York, NY, USA (2009). http://doi.acm.org/10.1145/1582379.1582675

14.

Botorog, G.H., Kuchen, H.: Efficient high-level parallel programming. Theor. Comput. Sci. 196(1G2), 71–107 (1998)CrossRefMATH

15.

Charteris, A., Syme, W., Walden, W.: Urban flood modelling and mapping 2d or not 2d. In: Proceedings of the 6th Conference on Hydraulics in Civil Engineering: The State of Hydraulics, pp. 355–363. Barton A.C.T: Institution of Engineers, Barton, Australia (2001)

16.

Chatfield, C., Yar, M.: Holt-Winters forecasting: some practical issues. J. R. Stat. Soc. 37(2), 129–140 (1988)

17.

Cole, M.: Bringing skeletons out of the closet: a pragmatic manifesto for skeletal parallel programming. Parallel Comput. 30(3), 389–406 (2004)CrossRef

18.

D-ITG: Distributed internet traffic generator. http://www.grid.unina.it/software/ITG/papers.php. Accessed 2 March 2013

19.

Fantacci, R., Vanneschi, M., Bertolli, C., Mencagli, G., Tarchi, D.: Next generation grids and wireless communication networks: towards a novel integrated approach. Wirel. Commun. Mob. Comput. 9(4), 445–467 (2009)CrossRef

20.

Garcia, C.E., Prett, D.M., Morari, M.: Model predictive control: theory and practice a survey. Automatica 25, 335–348 (1989)CrossRefMATH

21.

Gholami, M., Salahshoor, K., Tabatabaei-pour, M., Shaker, H., Alizadeh, T.: Improved model predictive control of discrete-time hybrid systems with mixed inputs. In: 33rd Annual Conference of the IEEE Industrial Electronics Society, 2007 (IECON 2007), pp. 744–749 (2007)

22.

Gomes, A.T.A., Batista, T.V., Joolia, A., Coulson, G.: Architecting dynamic reconfiguration in dependable systems. Lect. Notes Comput. Sci. 4615, 237–261 (2007)CrossRef

23.

González-Vélez, H., Leyton, M.: A survey of algorithmic skeleton frameworks: high-level structured parallel programming enablers. Softw. Prac. Exp. 40(12), 1135–1160 (2010). doi:10.1002/spe.1026 CrossRef

24.

He, Q., Dovrolis, C., Ammar, M.: On the predictability of large transfer TCP throughput. Comput. Netw. 51, 3959–3977 (2007)CrossRefMATH

25.

Heemels, W.P.M.H., Sandee, J.H.: Analysis of event-driven controllers for linear systems. Int. J. Control 81(4), 571–590 (2008)CrossRefMATHMathSciNet

26.

Hellerstein, J.L., Diao, Y., Parekh, S., Tilbury, D.M.: Feedback Control of Computing Systems. Wiley, Hoboken (2004)CrossRef

27.

Horvath, T., Abdelzaher, T., Skadron, K., Liu, X.: Dynamic voltage scaling in multitier web servers with end-to-end delay control. IEEE Trans. Comput. 56(4), 444–458 (2007). doi:10.1109/TC.2007.1003 CrossRefMathSciNet

28.

Huebscher, M.C., McCann, J.A.: A survey of autonomic computing—degrees, models, and applications. ACM Comput. Surv. 40(3), 1–28 (2008)CrossRef

29.

Kephart, J., Walsh, W.: An artificial intelligence perspective on autonomic computing policies. In: Policies for Distributed Systems and Networks, 2004. POLICY 2004. Proceedings. Fifth IEEE International Workshop on, pp. 3–12 (2004)

30.

Kephart, J.O., Chess, D.M.: The vision of autonomic computing. Computer 36(1), 41–50 (2003)CrossRefMathSciNet

31.

Kieran, D., Yan, W.: A framework for an event driven video surveillance system. In: Advanced Video and Signal Based Surveillance (AVSS), 2010 Seventh IEEE International Conference on, pp. 97–102 (2010). doi:10.1109/AVSS.2010.57

32.

Kuchen, H., Ernsting, S.: Data parallel skeletons in java. In: Procedia Computer Science, Proceedings of the International Conference on Computational Science, ICCS 2012 9(0), pp. 1817–1826 (2012)

33.

Kusic, D., Kandasamy, N.: Risk-aware limited lookahead control for dynamic resource provisioning in enterprise computing systems. Clust. Comput. 10(4), 395–408 (2007). doi:10.1007/s10586-007-0022-y CrossRef

34.

Kusic, D., Kandasamy, N., Jiang, G.: Combined power and performance management of virtualized computing environments serving session-based workloads. Netw. Serv. Manag. IEEE Trans. 8(3), 245–258 (2011). doi:10.1109/TNSM.2011.0726.100045 CrossRef

35.

Legaux, J., Loulergue, F., Jubertie, S.: Osl: An algorithmic skeleton library with exceptions. In: 2013 International Conference on Computational Science, Procedia Computer Science 18(0), 260–269 (2013)

36.

Liu, H., Parashar, M.: Accord: a programming framework for autonomic applications. Syst. Man Cybernet. C 36(3), 341–352 (2006). doi:10.1109/TSMCC.2006.871577 CrossRef

37.

Santambrogio, M.D., Agarwal, A., Leva, A.: Comparison of decision-making strategies for self-optimization in autonomic computing systems. ACM Trans. Autonom. Adapt. Syst. 7(4), 36 (2012). doi:10.1145/2382570.2382572

38.

Maheshwari, N., Nanduri, R., Varma, V.: Dynamic energy efficient data placement and cluster reconfiguration algorithm for mapreduce framework. Fut. Gener. Comput. Syst. 28(1), 119–127 (2012)CrossRef

39.

Mencagli, G., Vanneschi, M.: QoS-control of structured parallel computations: a predictive control approach. In: Cloud Computing Technology and Science (CloudCom), 2011 IEEE Third International Conference on, pp. 296–303 (2011). doi:10.1109/CloudCom.47

40.

NCTUNS: Network simulator and emulator. http://nsl.csie.nctu.edu.tw/nctuns.html/. Accessed 8 April 2013

41.

Parashar, M., Liu, H., Li, Z., Matossian, V., Schmidt, C., Zhang, G., Hariri, S.: Automate: enabling autonomic applications on the grid. Clust. Comput. 9, 161–174 (2006). doi:10.1007/s10586-006-7561-5. http://dl.acm.org/citation.cfm?id=1127683.1127688

42.

Park, S.M., Humphrey, M.: Predictable high-performance computing using feedback control and admission control. Parallel Distrib. Syst. IEEE Trans. 22(3), 396–411 (2011). doi:10.1109/TPDS.2010.100 CrossRef

43.

Patikirikorala, T., Colman, A., Han, J., Wang, L.: An evaluation of multi-model self-managing control schemes for adaptive performance management of software systems. J. Syst. Softw. 85(12), 2678–2696 (2012). Self-adaptive systemsCrossRef

44.

Pellegrini, M.C., Riveill, M.: Component management in a dynamic architecture. J. Supercomput. 24(2), 151–159 (2003). doi:10.1023/A:1021798709301 CrossRefMATH

45.

Potocnik, B., Music, G., Zupancic, B.: Model predictive control systems with discrete inputs. In: Electrotechnical Conference, 2004. MELECON 2004. Proceedings of the 12th IEEE Mediterranean, 1, pp. 383–386 (2004)

46.

Reiff-Marganiec, S., Turner, K.J.: Feature interaction in policies. Comput. Netw. 45, 569–584 (2004). doi:10.1016/j.comnet.2004.03.004. http://portal.acm.org/citation.cfm?id=1031816.1031818

47.

Rossiter, J.A.: Model-based Predictive Control: A Practical Approach. Control Series. CRC Press, Boca Raton (2003)

48.

Saini, M., Xiangyu, W., Atrey, P., Kankanhalli, M.: Dynamic workload assignment in video surveillance systems. In: Multimedia and Expo (ICME), 2011 IEEE International Conference on, pp. 1–6 (2011). doi:10.1109/ICME.2011.6012076

49.

Sandee, J.H., Heemels, W.P.M.H., Van Den Bosch, P.P.J.: Case studies in event-driven control. In: Proceedings of the 10th International Conference on Hybrid Systems: Computation and Control. HSCC’07, pp. 762–765. Springer-Verlag, Berlin, Heidelberg (2007)

50.

Shi, X., Liu, C., Wu, S., Jin, H., Wu, X., Deng, L.: A cloud service cache system based on memory template of virtual machine. In: Proceedings of the 2011 Sixth Annual ChinaGrid Conference, CHINAGRID ’11, pp. 168–173. IEEE Computer Society, Washington, DC, USA (2011). doi:10.1109/ChinaGrid.2011.20. http://dx.doi.org/10.1109/ChinaGrid.2011.20

51.

Vanneschi, M.: The programming model of assist, an environment for parallel and distributed portable applications. Parallel Comput. 28(12), 1709–1732 (2002)CrossRefMATH

52.

Vanneschi, M., Veraldi, L.: Dynamicity in distributed applications: issues, problems and the assist approach. Parallel Comput. 33(12), 822–845 (2007)CrossRef

53.

Wang, X., Du, Z., Chen, Y., Li, S., Lan, D., Wang, G., Chen, Y.: An autonomic provisioning framework for outsourcing data center based on virtual appliances. Clust. Comput. 11(3), 229–245 (2008). doi:10.1007/s10586-008-0053-z CrossRef

54.

Warneke, D., Kao, O.: Exploiting dynamic resource allocation for efficient parallel data processing in the cloud. IEEE Trans. Parallel Distrib. Syst. 22(6), 985–997 (2011). doi:10.1109/TPDS.2011.65 CrossRef

55.

Weigold, T., Aldinucci, M., Danelutto, M., Getov, V.: Process-driven biometric identification by means of autonomic grid components. Int. J. Autonom. Adapt. Commun. Syst. 5(3), 274–291 (2012). doi:10.1504/IJAACS.2012.047659

56.

Wernsing, J.R., Stitt, G.: Elastic computing: a framework for transparent, portable, and adaptive multi-core heterogeneous computing. SIGPLAN Not. 45(4), 115–124 (2010)CrossRef

57.

Wilkinson, B., Allen, M.: Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers. Prentice-Hall, Upper Saddle River (1999)

58.

Yaikhom, G., Cole, M., Gilmore, S., Hillston, J.: A structural approach for modelling performance of systems using skeletons. In: Electronic Notes in Theoretical Computer Science 190(3), pp. 167–183. Proceedings of the Fifth Workshop on Quantitative Aspects of Programming Languages (QAPL 2007) (2007)

59.

Yuan, Q., Liu, Z., Peng, J., Wu, X., Li, J., Han, F., Li, Q., Zhang, W., Fan, X., Kong, S.: A leasing instances based billing model for cloud computing. In: Proceedings of the 6th International Conference on Advances in Grid and Pervasive Computing. GPC’11, pp. 33–41. Springer-Verlag, Berlin (2011)

Titel: Towards a systematic approach to the dynamic adaptation of structured parallel computations using model predictive control
verfasst von: Gabriele Mencagli
Marco Vanneschi
Publikationsdatum: 01.12.2014
Verlag: Springer US
Erschienen in: Cluster Computing / Ausgabe 4/2014
Print ISSN: 1386-7857
Elektronische ISSN: 1573-7543
DOI: https://doi.org/10.1007/s10586-014-0346-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2014

DIRAQ: scalable in situ data- and resource-aware indexing for optimized query performance

Reexamining anomaly temporal behaviors in SPEC CPU workloads: self-similar or not?

Scalable PGAS collective operations in NUMA clusters

Adaptive Combiner for MapReduce on cloud computing

Scalable and effective peer-to-peer desktop grid system

An effective reliability-driven technique of allocating tasks on heterogeneous cluster systems