Go to page
 

Bibliographic Metadata

Title
Multi-objective scheduling for scientific workflow applications in grid and cloud infrastructures / by Hamid Mohammadi Fard
AuthorMohammadi Fard, Hamid
Thesis advisorFahringer, Thomas
Published2015
DescriptionX, 198 S. : Ill., graph. Darst.
Institutional NoteInnsbruck, Univ., Diss., 2015
Date of SubmissionSeptember 2015
LanguageEnglish
Bibl. ReferenceOeBB
Document typeDissertation (PhD)
Keywords (DE)Ressourcenbereitstellung / Workflow Scheduling / Cloud computing / Grid computing / Resource provisioning
Keywords (GND)Prozessmanagement / Cloud Computing / Grid Computing / Betriebsmittelverwaltung
URNurn:nbn:at:at-ubi:1-3294 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Multi-objective scheduling for scientific workflow applications in grid and cloud infrastructures [4.16 mb]
Links
Reference
Classification
Abstract (German)

In den letzten Jahrzehnten werden vermehrt heterogene parallele und verteilte Systeme wie Grid und Clouds als Umgebungen zur Ausführung von umfangreichen Anwendungen gewählt. Workflows haben sich als attraktives Paradigma entwickelt um umfangreiche wissenschaftliche Anwendungen in solchen Systemen zu modellieren. Wissenschaftliche Workflows können als parallele Berechnungstechnik herangezogen werden um komplexe und riesige Berechnungen zur Datenanalyse und Simulation in vielen Bereichen der Wissenschaft zu instrumentieren. Ein Hauptproblem ist die effiziente Ausführung von Workflows in verteilten heterogenen Systemen, Scheduling von Tasks und der Datentransfer. Die Ablaufplanung kann für gewöhnlich aus zwei verschiedenen Perspektiven gesehen werden: Lokale und Globale Ablaufplanung. Lokale Ablaufplanung beschäftigt sich mit der Verteilung von Aufgaben auf einzelnen Systemen während sich globale Ablaufplanung mit der Verteilung von Aufgaben über das gesamte verteilte System beschäftigt. In dieser Arbeit konzentrieren wir uns auf globale Ablaufplanung, die auch Meta-Scheduling genannt wird. Abhängig von den Zielfunktionen wie zum Beispiel die Zeit bis zur Fertigstellung (Ausführungszeit), kann das Scheduling Problem NP-vollständig sein. Aufgrund ihrer Komplexität verwenden wir zur Lösung solcher Probleme beinahe optimale Lösungen, welche sich mit Hilfe von Heuristiken der optimalen Lösung annähern. Für gewöhnlich gibt es in dezentralen heterogenen Umgebungen verschiedene Rollen, die das Problem aus jeweils anderen Perspektiven sehen. Während Wissenschaftler meist an der Minimierung der Ausführungszeit ihrer Anwendung interessiert sind, konzentrieren sich Systemadministratoren oft auf die Maximierung der Ressourcen Ausnutzung, des Job Durchsatzes oder der User Fairness. Bei realen Scheduling Problemen kommt es deshalb häufig zu Szenarien mit bei denen viele dieser wichtigen Ziele in Konflikt zueinander stehen. Leistungsstarke Prozessoren zum Beispiel werden typischerweise von Cloud Computing anbietern zu höheren Preisen vermietet und verbrauchen mehr Energie, könnten jedoch aufgrund der großen Anzahl von Benutzeranfragen unzuverlässig werden. Ähnliche Arbeiten zum Thema Scheduling sind üblicherweise auf die Optimierung eines Ziels (meist Ausführungszeit) beschränkt, wobei manche isolierte Ansätze versuchen auf Zwei ziele zu optimieren. Ein generisches Framework für Scheduling und Heuristik basierte Algorithmen zur Optimisierung multipler wiedersprüchlicher Kriterien fehlt jedoch bisher. Der Fokus dieser Dissertation liegt auf dem Vorschlag Multi-Objektiver Polynomieller Scheduling Algorithmen um wissenschaftliche Workflow Anwendungen in Clouds und Grids auszuführen. Das Ziel ist es Workflow Aufgaben und Datentransfers effizient zu planen (sowohl statische und dynamische Ansätze) um Problemziele zu erreichen. Mehrere wichtige Faktoren wie die Ausführungszeit der Anwendung, wirtschaftliche Kosten der Ausführung, Energieverbrauch, Ressourcenverwendung und Verlässlichkeit der Ausführung werden als Ziele für die Optimierung herangezogen. In Grid Umgebungen sind die größten Herausforderungen die Zuverlässigkeit und dynamische Last auf Ressourcen. Grid Standorte werden für gewöhnlich von verschiedenen Administratoren gewartet, und die Verfügbarkeit von Ressourcen kann sich während der Laufzeit verändern. Außerdem gibt es aufgrund der Autonomie von Grids immer unvorhersehbare Last auf den Ressourcen. In IaaS (Infrastructure as a Service) Clouds wie zum Beispiel Amazons EC2 können wir die Zuverlässigkeit und externe Lasten auf Ressourcen ignorieren. Die Bereitstellung von Ressourcen bei Bedarf stellt jedoch eine grose Herausforderung dar. In kommerziellen IaaS Clouds haben die Computersysteme keine vordefinierte Topologie und Benutzer können sich ihre Ressourcen bei Bedarf zusammenstellen wie sie möchten. Das Preismodel solcher Clouds und Beschränkungen bei Problemen erhöhen die Komplexität der Ablaufplanung in solchen Umgebungen.

Abstract (English)

In recent decades, heterogeneous parallel and distributed systems such as Grids and Clouds are commonly used environments for the execution of large-scale applications. The concept of the workflow has emerged as an attractive paradigm to model large-scale scientific applications in such systems. Scientific workflows can be viewed as a parallel computing technique for orchestrating complex and huge computations for data analysis and simulation across many scientific domains. To execute workflow applications efficiently in distributed heterogeneous systems, the scheduling of activities and data transfers is a key problem. Scheduling usually could be viewed in two different perspectives: local and global schedules. Local scheduling is the scheduling of activities within a site or resource, while global scheduling considers the scheduling of activities across the whole distributed system. The concentration of the present research is on global scheduling. When considering some set of objective functions, such as the overall completion time (makespan), the scheduling problem is NP-complete. Due to the problem complexity, we rely on near-optimal solutions that are attained by heuristics which we propose in order to approximate optimal solutions. Typically, different actors within decentralized heterogeneous environments (e.g. users and providers) view the problem from different perspectives. Scientists are usually interested in minimizing the execution time of their application, whereas system administrators are often interested in maximizing the resource utilization, job throughput, or user fairness. Real-world scheduling problems are therefore frequently confronted with a multi-objective scenario in which many of these important objectives are conflicting. For example, powerful processors are typically rented by Cloud computing providers at a higher price, consume more energy, and may become unreliable due to the large number of requests and due to user contention. Nowadays, related scheduling work is typically restricted to optimizing one objective (usually makespan), while some isolated approaches tried to optimize across two criteria. A generic scheduling framework and heuristic-based algorithms for optimizing multiple conflicting criteria are still missing. For example in a particular Grid environment, the main challenges might be reliability and load. Grid sites are usually managed by different administrations, and its resource availability might change at runtime. Moreover, due to the autonomous and decentralized nature of Grids, resources available to a given user in the near future are unpredictable. In IaaS (Infrastructure as a Service) Clouds, e.g. Amazon EC2, we may ignore the reliability and external loads of resources; rather, we are face the challenge of on-demand resource provisioning. In commercial IaaS Clouds, the computing system has no predefined topology, thus users are allowed to arrange the computing resources on-demand, as they wish. The pricing model of such Clouds amidst the set of scheduling constraints will increase the complexity of scheduling applications in such environments. In this dissertation, the focus is on the proposal of polynomial-time, multi-objective scheduling algorithms, specifically in their use with the execution of scientific workflow applications within heterogeneous distributed systems, and particularly within Clouds. The goal is to schedule workflow activities and data transfers in an efficient way, employing both static and dynamic approaches to fulfill the set of scheduling objectives. Several important objectives, including application-makespan, economic costs of execution, energy costs of execution, and reliability of execution, will be considered as the optimization goals. Our approaches to deal with the problem leverage various theories such as multi-objective optimization and game theory.