Home

Arbeitsbereich
Personen
Workshops

Mitgliederbereich

Impressum


SVLR'97 Abstracts

Kurzzusammenfassungen der Vorträge

Martin Backschat
TU München,
Gabelbergerstr. 39, 80290 München
E-Mail: Martin.Backschat@informatik.tu-muenchen.de

In this talk we present the concept, implementation, and evaluation of DYNASTY II, a novel economic-based dynamic load distribution system for parallel applications in large heterogeneous workstation networks and parallel computers. Its main goal is to distribute tasks to idle/underloaded computing resources with dynamic migrations on demand. This is accomplished by implementing a computational service economy based on a price and brokering mechanism for regulating supply and demand of computational power.

In DYNASTY II we incorporate such economic mechanisms. Computing resources dynamically fix local execution costs (i.e. rent) depending on, for example, current performance, demand, and global average rent. The price mechanism and rent, as an abstraction for conventional load indices, allow machines and computational services with different capabilities resp. quality of service (QoS) to have different values, enabling tasks to flexibly devote their currency to the resources most important to them. A hierarchical organized broker system assigns tasks to computational resources. The tasks simply specify their target requirements and selection preferences. The query range depends on the task's budget. We also consider data exchange and migrations as priced services. This yields locality of data and communication as it is imposed by market forces.

The design and implementation of the DYNASTY II system is based on the following principles: SCALABILITY w.r.t. network size as well as number of market participants and NON-INTRUSIVENESS in allocating computing resources that are used otherwise (e.g. by its owner). We also focus on TRANSPARENCY of the layered economic system to the application programmer (by providing frontends) and the REUSEABILITY of frontends and agent code in order to ease the adaption of existing parallel programs to DYNASTY II.

We have implemented DYNASTY II on several operating systems like HPUX, SGI Irix, Linux, and Windows NT. The portable source code of the lower two layers is written in C++. All market and system agents are multi-threaded in order to allow servicing requests and internal reasoning simultaneously.

In the current implementation we provide frontends to parallel environments (PEs) like PVM, which allows the integration of exisiting parallel applications without modifying of their source code.

The talk also presents experiences with the load distribution in modern parallel numerical applications like the finite element algorithm ARESO.


Frank Bellosa
University of Erlangen-Nuernberg
Department of Computer Science IV
Martensstrasse 1
D-91058 Erlangen
E-Mail: bellosa@informatik.uni-erlangen.de

Memory Access: The Third Dimension of Scheduling

Up to now, two internal events influence scheduling decisions of contemporary operating systems: timer events and I/O-related interrupts. Timing information supports preemption and priority adjustment. Knowledge about issued or completed I/O operations helps to wake-up sleeping processes and to boost their priority. Preferring deblocked processes at the end of I/O operations improves the interactive performance and saves buffer space because available data is consumed short after its availability.

With the upcoming of processors clocked with hundreds of megahertz, the processor speed exceeds the speed of affordable memory by factors. If it is accepted to influence execution priorities by slow I/O events, why should scheduling neglect events related to other slow devices like main memory and memory data paths?

Our novel approach to scheduling is based on knowledge derived from counters in the memory subsystem. We demonstrate that the usage of information related to cache- and main-memory access opens new dimensions in real-time and time-slice scheduling of shared-memory architectures. Advanced cache-affinity scheduling, memory-bandwidth guarantees for real-time jobs, and new processor assignment strategies are three basic concepts of a new scheduling philosophy focusing more on memory access than on CPU cycles as the performance determinant factor.


Marc Gehrke
Ritterbrunnen 6,
38100 Braunschweig
E-Mail: gehrke@ibr.cs.tu-bs.de

Bettina Schnor
MU Lübeck
Medizinische Universität Lübeck
Ratzeburger Allee 160, 23538 Lübeck
E-Mail: schnor@itm.mu-luebeck.de

Dynamic-SED: Ein Schedulingverfahren für parallele Anwendungen in Workstation-Clustern

Parallele Anwendungen gewinnen zunehmend an Bedeutung. Sie können auf heterogenen Rechnernetzen so gestartet werden, daß sie freie Rechenkapazitäten, zum Beispiel nachts, ausnutzen. Dabei stehen sie jedoch in Konkurrenz zu den Benutzern, die die Rechner interaktiv für ihre Zwecke nutzen wollen. Es ist das Ziel, einen guten Kompromiß zwischen der Beeinträchtigung der Benutzer und der Laufzeit der Anwendung zu finden, wobei die Benutzer im Vordergrund stehen.

Das Mapping-Verfahren SED verteilt Anwendungen mit strenger Synchronisation in einem heterogenen Rechnernetz, indem es die zu erwartende Verzögerung minimiert. Dazu werden die Rechner in verschiedene Geschwindigkeitsklassen eingeteilt. Die Anwendung kann dann auf virtuell homogenen, d.h. auf virtuell gleichschnellen Rechnern gestartet werden. SED wird nun so erweitert, daß interaktive Benutzer durch Reservierung von Systemressourcen wie freier Speicher und Rechenkapazität berücksichtigt werden. Um auf Änderungen der Systemlast während der Laufzeit der Anwendung reagieren zu können, werden Migrationsregeln formuliert. Dabei werden Rechner gesucht, die längere Zeit als nicht mehr geeignet für die Anwendung gelten, oder auf denen Benutzer zu stark beeinträchtigt werden. Wenn ein Prozeß der Anwendung auf einem dieser Rechner läuft, wird für diesen ein geeigneter Zielrechner gesucht. Ist das System insgesamt stark belastet, kann dieser Zielrechner für die Anwendung erhebliche Geschwindigkeitseinbußen bedeuten. Dies wird jedoch akzeptiert, da die Benutzer Vorrang vor der Anwendung haben.

Das erweiterte SED Mapping wurde in einem Scheduler, welcher unter PVM läuft, integriert. Bei diesem neuen System S-PVM kann eine Prozeßgruppe unter Berücksichtigung der aktuellen Lasten im System gestartet werden. Sind nicht ausreichend Kapazitäten vorhanden, wird die Prozeßgruppe in eine Warteschlange eingetragen. Unter PVM und auch unter S-PVM sind keine Migrationen möglich. Um die Migrationsregeln dennoch untersuchen zu können, wurde ein Testsystem entwickelt, welches virtuell Prozeßgruppen über einem längeren Zeitraum im System beobachtet. Dabei hat sich ergeben, daß die Laufzeit der Anwendung, auch bei stark belastetem System, zu 60 Prozent garantiert werden kann, ohne daß Benutzer entscheidend gestört werden. Ferner hat sich herausgestellt, daß ein genereller Verzicht auf 30 Prozent der insgesamt vorhandenen Ressourcen zu erheblich weniger Migrationen und zu deutlich geringeren Beeinträchtigungen der Benutzer führen.


Claudia Gold
TU München
Institut für Informatik
Orleansstr. 34, D-81667 Müchen
E-Mail: gold@informatik.tu-muenchen.de

Adaptive Lastverteilung mit ALDY

ALDY steht für Adaptive Load Distribution System. Adaptiv drückt dabei aus, daß die Lastverteilung innerhalb einer Anwendung dynamisch an die aktuelle Rechnerauslastung angepaßt wird. Dafür wird sowohl Objektzuweisung als auch Objektmigration eingesetzt.

Beim Entwurf von ALDY wurde besonderer Augenmerk auf die Portierbarkeit und Flexibilität in Hinblick auf heterogene Umgebungen und unterschiedliche Objektimplementierungen gelegt. Diese Ziele werden zum einen durch die Verwendung von virtuellen Objekten erreicht. Zum anderen ist ALDY nicht an eine bestimmte Kommunikationsplattform gebunden.

Im Vortrag werden zunächst Design und Konzepte von ALDY vorgestellt. Wie ALDY in parallele Anwendungen integriert werden kann, wird am Beispiel eines Relaxationsalgorithmus gezeigt. ALDY kann aber nicht nur für die Lastverteilung in parallelen Anwendungen eingesetzt werden sondern auch in Laufzeitsystemen paralleler Prommierumgebungen, die noch keine Unterstützung von Lastverteilung bieten. Überlegungen zur Integration von ALDY in CORBA-Laufzeitsysteme schließen den Vortrag ab. CORBA ist ein immer mehr - vor allem auch im kommerziellen Bereich - an Bedeutung gewinnender Standard für verteilte objektorientierte Anwendungen.


C. Grewe, W. Obelöer
Medizinische Universität zu Lübeck
Institut für Technische Informatik
Ratzeburger Allee 160
D-23538 Lübeck
E-Mail: [grewe,obeloeer]@iti.mu-luebeck.de

Im Beitrag wird ein LV-Werkzeug vorgestellt, welches sehr flexibel an unterschiedliche Rechensysteme und Algorithmen anpassbar ist. Um einen Überblick zu geben, werden zunächst die Ziele, das Konzept und die Struktur des LV-Werkzeugs vorgestellt. Hier wird auch auf die Gemeinsamkeiten von Werkzeugen zur Fehlertoleranz und Lastverwaltung eingegangen.

Angesichts der angestrebten Flexibilität, Erweiterbarkeit und Wiederverwendbarkeit hinsichtlich verschiedener LV-Algorithmen, sind klare Schnittstellen und gute Beschreibungsmöglichkeiten für Algorithmen notwendig. Die Beschreibung der LV-Algorithmen kann durch normale'' Programmierung oder wissensbasiert erfolgen. Bei den Schnittstellen sind die vom Werkzeug zur Verfügung gestellten lastcharakterisierenden Systemmerkmale von grosser Bedeutung. In diesem Zusammenhang werden neben einer Klassifikation von Lastindizes zwei auf On-line-Messungen basierende Verfahren zur Prognose von zukünftigen Lastsituationen aufgezeigt. Abschliessend wird die Realisierung des Werkzeugs unter PVM beschrieben, wobei ein eigenes Migrationskonzept zur Anwendung kommt.


Stefan Petri
TU Braunschweig
Bültenweg 74/75
38102 Braunschweig
E-Mail: petri@ibr.cs.tu-bs.de

Da das Preis-Leistungs-Verhältnis der Workstation-Cluster deutlich besser ist als das von ``Superrechnern'', erfreuen sie sich steigender Beliebtheit als Plattform für ressourcenintensive verteilte und parallele Anwendungen. Dabei müssen jedoch ungleichmäßige Auslastung, Konflikte mit interaktiven Benutzern und eine höhere Ausfallrate berücksichtigt werden. Geeignete Mittel zur Lösung dieser Probleme sind Prozeßmigration und Sicherungspunkte (Checkpointing/Rollback). In der Literatur werden verschiedene Mechanismen dafür beschrieben, sie alle weisen jedoch gewisse Schwächen auf und fordern Einschränkungen von den Anwendungen.

In dieser Arbeit wird ein neues Konzept für einen anwendungstransparenten Migrations- und Checkpointingmechanismus entwickelt, das einige wesentliche Einschränkungen überwindet. Es unterstützt Migrations- und Fehlertransparenz für parallele und verteilte Anwendungen, d.h. Gruppen kommunizierender Prozesse, in Workstation-Clustern. Weder der Systemkern noch die Anwendungsprogramme brauchen modifiziert werden, und die Anwendungen müssen nicht für eine spezielle Laufzeitumgebung geschrieben sein. Für bessere Effizienz können sie mit einer modifizierten Systembibliothek gebunden werden. Aus dem Konzept wird die Architektur der Beispiel-Implementation PBeam abgeleitet, und über erste Meßergebnisse und Erfahrungen mit der Implementation berichtet.


Friedhelm Ramme
Paderborn Center for Parallel Computing
Fürstenallee 11
33095 Paderborn

In diesem Vortrag werde ich mich mit dem Problem einer transparenten und gleichzeitig effizienten Nutzung von partitionierbaren Parallelrechnern mit einer exklusiven Ressourcen-Vergabe auseinandersetzen. Der Term 'partitionierbare Parallelrechner' schließt hierbei die frei konfigurierbaren Transputer-System (wie den SC320 am PC2) ebenso wie die dynamisch partitionierbaren MPP-Rechner (IBM SP2, Intel Paragon, Cray T3E, Parsytec GCPP und GCel) und die dedizierten Workstation-Cluster (wie das CC-System am PC2) mit ein.

Um einen Verbund dieser Parallelrechner einer großen, heterogenen Menge von Benutzern kontinuierlich und möglichst störungsfrei zugänglich machen zu können, wird eine flexible und leistungsfähige MPP Management-Software benötigt. Das erste Ziel einer solchen Software sollte das Starten von Jobs (resp. von parallelen Programmen) auf den dafür benötigten Ressourcen (resp. Rechenknoten mit den geforderten Eigenschaften) sein. Eine MPP Management-Software ist ferner für geordnete Betriebsbedingungen auf zentral gewarteten und von vielen Benutzern gemeinsam und gleichzeitig genutzten Maschinen zuständig. Sie sollte darum in der Lage sein, den Konflikt zwischen Einzel- und Gruppennutzen soweit wie möglich zu entschärfen. Diese Forderung impliziert damit bereits eine faire Behandlung aller Jobs und eine möglichst effiziente Ausnutzung der verfügbaren Parallelrechner-Kapazität.

Der technische Prozeß des Startens paralleler Anwendungen ist heute auf nahezu allen Parallelrechnern schon mit einfachen Mechanismen durchführbar. Sollen jedoch keine Einschränkungen an die zu benutzenden Programmiersprachen, Programmiermodelle, Laufzeit- oder Betriebssysteme der Parallelrechner sowie bzgl. der Art der parallelen Anwendungen (batch oder interaktiv) vorgenommen werden, dann kann die Terminierung paralleler Programme und die Re-Initialisierung verteilter Services nur sichergestellt werden, wenn in der Architektur des Management-Systems bereits Mechanismen zur Koordinierung und zur Kontrolle verteilter Anwendungen vorgesehen wurden. Die effiziente Ausnutzung der MPP-Ressourcen, die insbesondere beim Multi-User Betrieb partitionierbarer Parallelrechner mit einer exklusiven Knotenvergabe eine große Bedeutung hat, darf das vordringliche Ziel, das Starten von Jobs, nicht behindern. Diese trivial anmutende Forderung kann leider von vielen heute genutzten MPP Management-Systemen unter Produktionsbedingungen nicht immer erfüllt werden.

Will man sich nicht auf das 'Weltbild' eines bestimmten Rechner-Herstellers festlegen, sondern offen für verschiedene Parallelrechner-Architekturen unterschiedlicher Hersteller bleiben, dann war bislang noch kein Lösungsansatz bekannt, der die Problematik einer für die Anwender transparenten und gleichzeitig auch effizienten Nutzung der Ressourcen bei partitionierbaren Parallelrechnern ermöglicht. In meinem Vortrag werde ich die Architektur einer verteilten MPP Management- Software entwickeln, die diese Anforderung erfüllt.

Nachdem zunächt die zu lösende Problematik anhand konkreter Beispiele von heute genutzten Parallelrechnern und deren Management-Architekturen motiviert wurde, werde ich ein vereinheitlichendes Nutzungsmodell für einen Verbund vernetzter Parallelrechner mit unterschiedlichen Architekturen, Betriebs- und Laufzeitumgebungen entwickeln. Ergänzt um betriebstechnische Aspekte eines Parallelrechenzentrums mit überregionaler Nutzerschaft, werde ich auf der Grundlage des uniformen Nutzungsmodells eine verteilte, funktional-parallele Management-Architektur entwickeln. Der erweiterbaren Spezifikation von Parallelrechner-Ressourcen, auf einer von der konkreten Management-Architektur entkoppelten Art und Weise, wird dabei eine Schlüsselrolle zukommen. Anschließend werde ich mich mit der zeitlichen Planung von Ressource- Anforderungen auseinandersetzen, da die transparente Nutzung von MPP-Ressourcen nur im Zusammenhang mit einer effizienten Nutzung der Kapazitäten erfolgreich sein kann. Hierzu werde ich das am PC2 entwickelte und eingesetzte verifizierende IVS-Scheduling vorstellen.

Den Abschluß meines Vortrags bildet ein Ausblick auf die verschiedenen Erweitungsmöglichkeiten der Software-Architektur, um auch Metacomputer Anwendungsszenarien integrieren zu können. Einige dieser Erweiterungen werden bereits im Kontext des Forschungsverbundes 'NRW-Metacomputing' weiter verfolgt.


Niels Reimer
Technische Universität München
Institut für Informatik
Lehrstuhl für Systemarchitektur
Barer Str. 38-42
80290 München

Im Rahmen des Thema des SFB342 (Werkzeuge und Methoden zur Nutzung paralleler Rechnerarchitekturen) entwickeln wir ein sprachbasiertes verteiltes Gesamtsystem, das sich unter anderem durch folgende Eigen- schaften auszeichnet: DSM, transparente Nutzung des HW-Pools, Informationsgewinn für das Ressourcenmanagement aus den struktur- bildenden Sprachkonzepten, integriertes skalierbares objekt- und anwendungsbezogenes Ressourcenmanagement. Der verfolgte Ein-Programm- Ansatz erlaubt es insbesondere Abhängigkeiten zwischen den verschiedenen Anwendungen zu erkennen und zu nutzen.

Zur Einordnung unseres Arbeitstandes seien hier die abgeschlossenen Vorarbeiten (EVA und AdaM) skizziert. In EVA (Experimentalsystem für Verteilte Anwendungen) wurden lediglich reine Lastplazierungsstrategien für Threads untersucht. Diese wurden in verteilte Stellenkerne integriert und auf einem UNIX-basierten Workstation-Cluster mittels Benchmarks bewertet. Die Abhängigkeiten der realisierten Objekte untereinander wurde dabei nicht berücksichtigt, trotzdem lässt sich bei hinreichendem Lastangebot eine 90(ADAptives Ressourcenmanagement unter Mach3.0) wurden Strategien zur Auswahl von Realisierungsalternativen für Datenobjekte (dynamische Replikate / Migration) in stellen- und objektgebundene adaptive Manager integriert. Dadurch ergeben sich deutliche Zugriffskosteneinsparungen gegenüber Lösungen, bei denen nicht repliziert bzw. migriert wird.

Wesentlich für die Weiterentwicklung des integrierten Last- und Ressourcenmanagements sind jedoch Erfahrungen aus eigenen Arbeiten, in denen ich mich mit reflexiven Strategien zur Anpassung des Parallelitäts- grades zur Laufzeit einer Anwendung auf einem shared-memory Parallel- rechner mit 16 CPUs beschäftigte. Dabei ähnelt das Umfeld sich trotz prinzipieller Unterschiede: SM, geringe Prozessoranzahlen, mächtige CPUs, transparente Nutzung eines Hardwarepools. Das anwendungs- und lastbezogene Ressourcenmanagement erfolgte dabei als anwendungsintegrierte Lösung, die ich im Rahmen unserer Entwicklungsarbeiten ins System integrieren werde. Das Verfahren erlaubt eine benutzerdefinierbare Balance zwischen effizienter Auslastung der Ressourcen und schneller Berechnung. Führte zu einer Rechenkostenreduktion auf 50mit maximal verfügbarem Parallelitätsgrad (16 CPUs) auf Kosten einer um 25AdaM Experimentalsysteme sind, jedoch die Ergebnisse der reflexiven Anpassung mit einer realen Anwendung (Moleküldynamik-Simulation) erzielt wurden.

Für die Zukunft zeichnen sich folgende Ziele ab: Entwicklung eines systemintegrierten reflexiven Ressourcenmanagements mit sich dynamisch anpassenden Managern (auch hinsichtlich der von ihnen benutzten Strategien und Heuristiken); Untersuchung der Wechselwirkungen der verschiedenen zu regelnden Bereiche / Strategien, um sie zu koordinieren, Synergieeffekte und Abhängigkeiten zwischen den Managementmassnahmen zu nutzen. Ferner sind dafür grundlegendere Fragen bzgl. der Art, Menge, Güte, Aktualität usw. der benötigten Last- und Ressourceninformationen zu klären.


Christian Röder
LRR-TUM
Institut für Informatik
TU München
D-80290 München
E-Mail: roeder@informatik.tu-muenchen.de

Strukturierte Analyse und Design einer Entscheidungskomponente zur Lastverwaltung in heterogenen Rechensystemen

In den vergangenen Jahren wurde eine Vielzahl von Lastverwaltungsmechanismen entwickelt, um die Laufzeit paralleler Anwendungen zu minimieren und die Lastschwankungen des Rechensystems zu kompensieren. Zur Ausführung paralleler Anwendungen kommen verstärkt Netze aus Arbeitsplatzrechnern zum Einsatz. Die auf dedizierten Parallelrechnern entwickelten Methoden zur Lastverwaltung unterliegen auf solchen System anderen Randbedingungen. Zusätzlich zur aktuellen Last des Systems beeinflussen diese Randbedingungen die Entscheidungen, die ein Lastverwaltungssystem (LVS) zur Erreichung seines Optimierungsziels trifft.

Ziel des Forschungsvorhabens ist die Entwicklung (und Prototyprealisierung) eines systemintegrierten LVS für Rechensysteme aus heterogenen gekoppelten Arbeitsplatzrechnern. In solchen Systemen konkurrieren sequentielle Benutzerprozesse und parallele Anwendungen um die verfügbaren Ressourcen. Als Entscheidungsgrundlage verwenden LVS zur Regelung des Systems dessen aktuelle Lastsituation. Im vorliegenden Fall sollen zur Entscheidungsfindung zusätzlich die Kosten berücksichtigt werden, die durch die tatsächliche Regelung entstehen. Der Vortrag soll einen Einblick in den aktuellen Stand der Arbeit vermitteln. In einem ersten Entwicklungsschritt werden die Randbedingungen Heterogenität und Mehrbenutzerbetrieb diskutiert und die daraus folgende Konsequenzen abgeleitet. Diese Konsequenzen bilden die Ausgangsbasis für das nachfolgende Design. Darüber hinaus sind die Komponenten des Lastverwalters zu identifizieren, die hohe Kosten verursachen. Aufgrund der Vielschichtigkeit des Problems ist eine geeignete Methodik zur Modellierung in der Designphase notwendig. Ausgewählt wurde die SADT Methodik (Structured Analysis and Design Techniques), deren Grundzüge und -techniken kurz vorgestellt und während des Designs verwendet werden. Den Abschluß des Vortrags bildet ein Überblick über den aktuellen Stand des Designs und ein Ausblick auf die noch zu verbleibenden Arbeiten.


Georg Stellner
TU München
Institut für Informatik
E-Mail: stellner@informatik.tu-muenchen.de

Last- und Ressourcenverwaltung paralleler Anwendungen mit einem Ressourcenverwaltungssystem

Ressourcenverwaltungssysteme (RVS) werden heute in Netzen aus Arbeitsplatzrechnern (NAA) eingesetzt, um sequentielle Benutzeraufträge unter Berücksichtigung der zur Berechnung notwendigen und der tatsächlich verfügbaren Ressourcen abzuarbeiten. Eine Unterstützung paralleler Anwendungen fehlt jedoch bisher.

Der Vortrag beschreibt, wie ein bereits bestehendes RVS um eine Sicherungspunktkomponente erweitert wurde, so daß neben sequentiellen Aufträgen auch parallele Aufträge unterstützt werden. Neben der Zuteilung von Rechnern zur Ausführung der Prozesse der parallelen Aufträge spielt hierbei auch die Überwachung der Last auf den einzelnen Rechnern, die einen parallelen Auftrag bearbeiten, eine wichtige Rolle. Im Falle auftretender Lastungleichheiten müssen Gegenmaßnahmen eingeleitet werden. Hierzu wird ebenfalls die neu integrierte Sicherungspunktkomponente eingesetzt, die die Verschiebung von Prozessen erlaubt. Der Vortrag schließt mit ersten Ergebnissen eines prototypischen Lastausgleichssystems mit unterschiedlichen Anwendungen.

Email an Webmaster
Last modified: Fri Jan 12 08:30:29 CET 2001