Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Cluster Computing
Erschienen in: Cluster Computing 3/2013

01.09.2013

A two-phase heuristic for the energy-efficient scheduling of independent tasks on computational grids

verfasst von: Frédéric Pinel, Bernabé Dorronsoro, Johnatan E. Pecero, Pascal Bouvry, Samee U. Khan

Erschienen in: Cluster Computing | Ausgabe 3/2013

Einloggen

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

search-config
loading …

Abstract

The sensitivity analysis of a Cellular Genetic Algorithm (CGA) with local search is used to design a new and faster heuristic for the problem of mapping independent tasks to a distributed system (such as a computer cluster or grid) in order to minimize makespan (the time when the last task finishes). The proposed heuristic improves the previously known Min-Min heuristic. Moreover, the heuristic finds mappings of similar quality to the original CGA but in a significantly reduced runtime (1,000 faster). The proposed heuristic is evaluated across twelve different classes of scheduling instances. In addition, a proof of the energy-efficiency of the algorithm is provided. This convergence study suggests how additional energy reduction can be achieved by inserting low power computing nodes to the distributed computer system. Simulation results show that this approach reduces both energy consumption and makespan.
Vorheriger Artikel Enabling greener DSL access networks by their stabilization with artificial noise and SNR margin
Nächster Artikel Fast energy-aware OLSR routing in VANETs by means of a parallel evolutionary algorithm

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
Literatur
1.
Alba, E., Dorronsoro, B.: Cellular Genetic Algorithms. Operations Research/Computer Science Interfaces. Springer, Heidelberg (2008) MATH
2.
Ali, S., Siegel, H.J., Maheswaran, M., Hensgen, D., Ali, S.: Representing task and machine heterogeneities for heterogeneous. J. Sci. Eng. 3, 195–207 (2000). Special 50th Anniversary Issue
3.
4.
Braun, T.D., Siegel, H.J., Beck, N., Bölöni, L.L., Maheswaran, M., Reuther, A.I., Robertson, J.P., Theys, M.D., Yao, B., Hengsen, D., Freund, R.F.: A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J. Parallel Distrib. Comput. 61(6), 810–837 (2001) CrossRef
5.
6.
7.
Casanova, H., Legrand, A., Zagorodnov, D., Berman, F.: Heuristics for scheduling parameter sweep applications in grid environments. In: Heterogeneous Computing Workshop, pp. 349–363 (2000)
8.
Casanova, H., Zagorodnov, D., Berman, F., Legrand, A.: Heuristics for scheduling parameter sweep applications in grid environments. In: Proceedings of the 9th Heterogeneous Computing Workshop, HCW ’00, pp. 349–363. IEEE Computer Society, Washington (2000)
9.
Cockcroft, A.N.: Millicomputing: the coolest computers and the flashiest storage. In: Int. CMG Conference, pp. 407–414. Computer Measurement Group (2007)
10.
Coello, C., Van Veldhuizen, D., Lamont, G.: Evolutionary Algorithms for Solving Multi-Objective Problems. Genetic Algorithms and Evolutionary Computation. Kluwer Academic, Dordrecht (2002) MATHCrossRef
11.
Deb, K.: Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, New York (2001) MATH
12.
Diaz, C.O., Guzek, M., Pecero, J.E., Danoy, G., Bouvry, P., Khan, S.U.: Energy-aware fast scheduling heuristics in heterogeneous computing systems. In: Proceedings of the 2011 International Conference on High Performance Computing & Simulation (HPCS 2011), Istanbul, Turkey, pp. 478–484 (2011) CrossRef
13.
Freund, R.F., Gherrity, M., Ambrosius, S., Campbell, M., Halderman, M., Hensgen, D., Keith, E., Kidd, T., Kussow, M., Lima, J.D., Mirabile, F., Moore, L., Rust, B., Siegel, H.J.: Scheduling resources in multi-user, heterogeneous, computing environments with smartnet. In: Proceedings of the Seventh Heterogeneous Computing Workshop, HCW ’98. IEEE Computer Society, Washington (1998)
14.
García, S., Fernández, A., Luengo, J., Herrera, F.: Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data mining: experimental analysis of power. Inf. Sci. 180(10), 2044–2064 (2010) CrossRef
15.
Ghafoor, A., Yang, J.: Distributed heterogeneous supercomputing management system. IEEE Comput. 26(6), 78–86 (1993) CrossRef
16.
Ibarra, O.H., Kim, C.E.: Heuristic algorithms for scheduling independent tasks on nonidentical processors. J. ACM 24(2), 280–289 (1977) MathSciNetMATHCrossRef
17.
18.
Khan, S.U., Ahmad, I.: Heuristics-based replication schemas for fast information retrieval over the internet. In: ISCA PDCS’04, pp. 278–283 (2004)
19.
Khan, S.U., Ahmad, I.: Comparison and analysis of ten static heuristics-based internet data replication techniques. J. Parallel Distrib. Comput. 68(2), 113–136 (2008) MATHCrossRef
20.
Kim, J., Siegel, H.J., Maciejewski, A.A., Eigenmann, R.: Dynamic resource management in energy constrained heterogeneous computing systems using voltage scaling. IEEE Trans. Parallel Distrib. Syst. 19(11), 1445–1457 (2008). doi:10.​1109/​TPDS.​2008.​113 CrossRef
21.
Li, Y., Liu, Y., Qian, D.: A heuristic energy-aware scheduling algorithm for heterogeneous clusters. In: 2009 15th International Conference on Parallel and Distributed Systems (ICPADS), pp. 407–413. IEEE, Shenzhen (2009). doi:10.​1007/​s10586-012-0207-x CrossRef
22.
Luo, P., Lü, K., Shi, Z.: A revisit of fast greedy heuristics for mapping a class of independent tasks onto heterogeneous computing systems. J. Parallel Distrib. Comput. 67, 695–714 (2007) MATHCrossRef
23.
Maheswaran, M., Ali, S., Siegel, H.J., Hensgen, D., Freund, R.F.: Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems. In: Proceedings of the Eighth Heterogeneous Computing Workshop, HCW ’99. IEEE Computer Society, Washington (1999)
24.
25.
Moscato, P., Cotta, C.: A gentle introduction to memetic algorithms. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics, International Series in Operations Research and Management Science, vol. 57, pp. 105–144. Springer, New York (2003) CrossRef
26.
Munir, E., Li, J.Z., Shi, S.F., Zou, Z.N., Rasool, Q.: A new heuristic for task scheduling in heterogeneous computing environment. J. Zhejiang Univ. Sci. A 9, 1715–1723 (2008) MATHCrossRef
27.
Nesmachnow, S., Cancela, H., Alba, E.: Heterogeneous computing scheduling with evolutionary algorithms. Soft computing—A fusion of foundations. Methodol. Appl. 15, 685–701 (2010)
28.
Pinel, F., Danoy, G., Bouvry, P.: Evolutionary algorithm parameter tuning with sensitivity analysis. In: Bouvry, P., Klopotek, M., Leprévost, F., Marciniak, M., Mykowiecka, A., Rybinski, H. (eds.) Security and Intelligent Information Systems. Lecture Notes in Computer Science, vol. 7053, pp. 204–216. Springer, Berlin (2012) CrossRef
29.
Pinel, F., Dorronsoro, B., Bouvry, P.: A new parallel asynchronous cellular genetic algorithm for de novo genomic sequencing. In: Proceedings of the IEEE International Conference on Soft Computing and Pattern Recognition (SOCPAR09), pp. 178–183 (2009) CrossRef
30.
Pinel, F., Dorronsoro, B., Bouvry, P.: A new parallel asynchronous cellular genetic algorithm for scheduling in grids. In: Proceedings of the 2010 IEEE International Symposium on Parallel and Distributed Processing, Workshops and Phd Forum, IPDPSW 2010, p. 206b (2010)
31.
Pinel, F., Pecero, J., Bouvry, P., Khan, S.: A two-phase heuristic for the scheduling of independent tasks on computational grids. In: International Conference on High Performance Computing and Simulation (HPCS), pp. 471–477 (2011)
32.
Pinel, F., Pecero, J., Khan, U.S., Bouvry, P.: Memory-aware green scheduling on multi-core processors. In: Proceedings of the Second International Workshop on Green Computing, ICPP (2010)
33.
Russell, S.J., Norvig, P.: Artificial Intelligence: A Modern Approach, 2nd edn. Prentice Hall, Englewood Cliffs (2002)
34.
Saltelli, A., Tarantola, S., Campolongo, F., Ratto, M.: Sensitivity Analysis in Practice: A Guide to Assessing Scientific Models. Wiley, New York (2004)
35.
Saltelli, A., Tarantola, S., Chan, K.: A quantitative, model independent method for global sensitivity analysis of model output. Technometrics 41, 39–56 (1999) CrossRef
36.
Siegel, H.J., Ali, S.: Techniques for mapping tasks to machines in heterogeneous computing systems. J. Syst. Archit. 46, 627–639 (2000) CrossRef
37.
Xhafa, F.: A hybrid evolutionary heuristic for job scheduling on computational grids. In: Abraham, A., Grosan, C., Ishibuchi, H. (eds.) Hybrid Evolutionary Algorithms. Studies in Computational Intelligence, vol. 75, pp. 269–311. Springer, Berlin (2007) CrossRef
38.
Xhafa, F., Alba, E., Dorronsoro, B., Duran, B.: Efficient batch job scheduling in grids using cellular memetic algorithms. J. Math. Model. Algorithms 7, 217–236 (2008) MathSciNetMATHCrossRef
Metadaten
Titel
A two-phase heuristic for the energy-efficient scheduling of independent tasks on computational grids
verfasst von
Frédéric Pinel
Bernabé Dorronsoro
Johnatan E. Pecero
Pascal Bouvry
Samee U. Khan
Publikationsdatum
01.09.2013
Verlag
Springer US
Erschienen in
Cluster Computing / Ausgabe 3/2013
Print ISSN: 1386-7857
Elektronische ISSN: 1573-7543
DOI
https://doi.org/10.1007/s10586-012-0207-x

Weitere Artikel der Ausgabe 3/2013

Cluster Computing 3/2013 Zur Ausgabe

OriginalPaper

Finding scalable configurations for AEDB broadcasting protocol using multi-objective evolutionary algorithms

OriginalPaper

Evaluating application performance and energy consumption on hybrid CPU+GPU architecture

OriginalPaper

A dynamic approach to tolerate soft errors

OriginalPaper

Green flexible opportunistic computing with task consolidation and virtualization

OriginalPaper

Energy-efficient execution of dense linear algebra algorithms on multi-core processors

OriginalPaper

Lifetime extension based on residual energy for receiver-driven multi-hop wireless network