Loading…
Thumbnail Image

Grid Workflow Scheduling based on Incomplete Information

Schneider, Jörg

Das Grid ist ein loser Verbund von Ressourcen verschiedener Besitzer. Die Ressourcen können dabei sehr unterschiedlicher Art sein: Vom Parallelrechner über Netzwerkbandbreite und Speicherplatz bis zu wissenschaftlichen Instrumenten. Jede dieser Ressourcen besitzt eine Verwaltungseinheit, die nach den Regeln der jeweiligen Besitzer die Benutzung regelt. Mit Hilfe des Grids können Benutzer Aufträge über eine einheitliche Schnittstelle abschicken, die ein Grid Broker dann an die beteiligten Ressourcen weitervermittelt. Die Aufträge setzen sich dabei meistens aus mehreren Teilaufträgen zusammen, die in einer bestimmten Reihenfolge abgearbeitet werden sollen. In diesen Grid Workflows kann angegeben werden, dass bestimmte Teilaufträge auf andere warten sollen oder dass zwei Teilaufträge genau gleichzeitig ausgeführt werden sollen. Zum Beispiel könnte ein Benutzer ein wissenschaftliches Instrument buchen und gleichzeitig einen Parallelrechner, der die Ergebnisse auswertet und basierend darauf das Experiment beeinflusst. Um ohne Verzögerung die Daten auszutauschen muss auch jeweils Netzwerkkapazität zwischen den gebuchten Ressourcen reserviert werden. Damit all die Teilaufträge bei den verschiedenen Organisationen koordiniert ausgeführt werden und das Netzwerk zur Verfügung steht, benutzt der Grid Broker Vorausreservierung. Diese Arbeit betrachtet den gesamten Lebenszyklus eines Grid Workflows. Zu Beginn wird die Frage diskutiert, wie ein Grid Workflow beschrieben werden kann. Dazu wurde eine Taxonomie entwickelt um Beschreibungssprachen für Grid Workflows zu vergleichen und mit dieser dann eine Reihe von bestehenden Sprachen eingruppiert. Ein so beschriebener Grid Workflow muss dann vom Grid Broker möglichst schnell und verlässlich eingeplant werden: Schnell, da der Benutzer direkt auf die Antwort wartet, ob der Grid Workflow so möglich ist, und verlässlich, da der Grid Broker gleich eine Garantie zum Beispiel für den spätesten Fertigstellungszeitpunkt abgibt. Der Grid Broker muss also in kürzester Zeit für alle Teilaufträge eine passende freie Ressource gefunden haben ohne unnötig viele Informationen bei den Ressourcen abzufragen. In der Arbeit werden mehrere Verfahren vorgestellt um dieses Online-Scheduling- Problem zu lösen. Wird Vorausreservierung verwendet, gibt es nicht nur Fragmentierung in der Ressourcendimension, sondern auch in der Zeitdimension. In der Arbeit werden verschiedene Ansätze diskutiert, wie dieses Offline-Scheduling-Problem auf Ebene des Grid Brokers und der lokalen Verwaltungseinheiten gelöst werden kann. Außerdem sind bei Vorausreservierung auch zukünftige Aufträge von einem Ressourcenausfall betroffen. Der Grid Broker erhält allerdings keine detaillierten Informationen über den Ausfall und muss trotzdem die Teilaufträge umbuchen, die für die Zukunft auf der defekten Ressource geplant waren und möglicherweise vom Ausfall betroffen sind. Für dieses Recovery-Scheduling-Problem wurden dazu Ansätze entwickelt die ohne Kenntnis der Ausfallzeit arbeiten. Die Verfahren für die verschiedenen Scheduling-Probleme wurden mit Hilfe von ausführlichen Simulationen miteinander verglichen.
In the computational Grid, resources of various types are connected across organizational boundaries. Each of these resources has already a local resource management system each working according to the local organization’s scheduling policy. The Grid provides now a unified access interface for all these resources respecting the independence of all resource providers, e.g., by requesting as less information as possible. To make full use of the diversity of resources in the Grid, a Grid job is composed of a number of sub-jobs together with precedence dependencies. These Grid workflows can also require sub-jobs to be executed at the very same time, e.g., to use a scientific instrument together with a high performance computer to directly analyze the measured data and adapt the experiment. Thus, these dependencies also require network bandwidth to be reserved between the sub-jobs. In order to co-allocate all these sub-jobs without interfering too much with the local resource management system, advance reservations are negotiated with the local resources. In this thesis the whole life cycle of a Grid workflow is discussed. Starting with the problem to specify a Grid workflow, a taxonomy to compare Grid workflow languages was developed and is applied to a number of Grid workflow languages. Based on this description a Grid broker needs to answer the request to allocate such a Grid workflow fast and reliable. In order to guarantee a given service level, e.g., deadlines to meet, the broker has to find a valid resource allocation for each sub-jobs without requesting too much information from the local resources. In this thesis, algorithms are presented to solve this online-scheduling problem. In an advance reservation environment, fragmentation can not only happen in the resource but also in the time dimension. Based on a new fragmentation measure techniques are presented to optimize the previously negotiated schedule. This offline-scheduling problem is discussed from the viewpoint of the local resources and of the Grid broker. The last problem solved in this thesis, is the failure handling on the Grid level. When a resources breaks down, the Grid broker is unaware of the downtime but needs to rearrange the already guaranteed executions in the future. For the recovery scheduling problem downtime independent approaches were developed. All the discussed algorithms are compared using extensive simulations.