Die Anschaulichkeit der Netz-Konzepte erleichtert den Übergang von einer verbalen Systembeschreibung bzw. Anforderungscharakteristik zu einer formalen Systemspezifikation als (eventuell zusätzlich beschriftetes) Petrinetz-Modell. Die Analysierbarkeit des Petrinetz-Modells gewährleistet seine Verifizierbarkeit, nämlich die Möglichkeit, die Erfülltheit der Spezifikation nicht nur durch Simulation des Modells zu widerlegen (d. h. Entwurfsfehler oder Widersprüche in der Spezifikation zu finden), sondern auch durch Analyse zu beweisen. Hierbei kommt die Theorie der Petrinetze zum Tragen, soweit sie in Form rechnergestützter Werkzeuge zur Analyse von Petrinetzen materialisiert vorliegt.
Das Anliegen der Lehr- und Forschungseinheit besteht darin, die Anwendungen der Netztheorie in den verschiedenen Zweigen der Volkswirtschaft dadurch zu verbreitern und zu befördern, daß Werkzeuge zur Arbeit mit Netzen, insbesondere zur Analyse, zur Verfügung gestellt werden und daß Forschungen betrieben werden, deren Resultate die Analysemöglichkeiten erweitern. Darunter fallen neben der Effektivierung bekannter Verfahren auch die Untersuchung neuer Klassen von Netz-Modellen (wie der Algebraischen Petri-Netze) und zugehöriger Analysemethoden bis zur (mindestens) versuchsweisen Implementation. Dazu gehört auch, daß die Forschungseinheit sich solcher Netzbegriffe annimmt, die in den Ingenieurwissenschaften ad hoc verwendet werden (z. B. zeitbewertete Petri-Netze), und sie theoretisch fundiert und damit einer systematischen Analyse zugänglich macht.
Beteiligte Mitarbeiter:
Die Arbeit des Werkzeuges wird durch einen Kommandointerpreter gesteuert. Der Befehlssatz umfaßt die Erzeugung und Manipulation von Daten, die Generierung von Ausgaben auf Bildschirm und Dateien, die Definition eigener, komplexer Kommandos unter Verwendung von Strukturierungskonzepten (IF, WHILE, sowie natürlich die Aufrufe von Analysealgorithmen.
Die Kommandosprache ist leicht erweiterbar, so daß auch künftig Analyseverfahren leicht ergänzt werden können. Derzeitig werden folgende Analysemethoden unterstützt:
Die Erzeugung eines zum gegebenen algebraischen Netzmodell äquivalenten Platz-Transitions-Netzes. Damit sind alle für letztere Netzklasse verfügbaren Analysemethoden auch für algebraische Netze zugänglich.
Die Verifikation gegebener Platz- und Transitionsvektoren daraufhin, ob sie Systeminvarianten beschreiben. Invarianten gestatten einige Rückschlüsse auf Systemeigenschaften und gelten als eine der wichtigsten Analysemethoden der Petrinetz-Theorie.
Ein Nichterreichbarkeitstest mit P-Invarianten. P-Invarianten haben die Eigenschaft, daß ihr Produkt mit allen erreichbaren Systemzuständen immer denselben Wert liefert. Daher können alle Zustände, die einen anderen Wert bei der Multiplikation mit einer P-Invariante liefern als der Anfangszustand, als nicht erreichbar klassifiziert werden. Umgekehrt kann es aber passieren, daß ein Zustand nicht erreichbar ist, obwohl er denselben Wert bei Multiplikation mit einer P-Invariante hat wie der Anfangszustand.
Gegenwärtig wird an der Implementation parametrisierter Erreichbarkeitsanalyse sowie an der Berechnung von Invarianten gearbeitet. Die wesentlichen theoretischen Grundlagen für diese Methoden stehen dafür zur Verfügung (siehe Veröffentlichungen). An der Implementation beteiligen sich zwei studentische Hilfskräfte.
Beteiligte Mitarbeiter:
Beteiligte Mitarbeiter:
Einige neuentwickelte Algorithmen sind bereits implementiert: ein Transformationsprogramm simuliert die neudefinierten Dauer-Intervall-Petrinetze durch Intervall- Petrinetze (Time PN) und übergibt die Netzinformation an den PN-Analysator INA. Hier wird die qualitative und quantitative Analyse ausgeführt.
Beteiligte Mitarbeiter:
Analyse von P/T-Netzen, gefärbten Netzen und zeitbewerteten Netzen
Ansprechpartner:
Zentrale Forschungsgegenstände am Lehrstuhl für Algorithmen und Komplexität sind der Entwurf und die Analyse effizienter Algorithmen. In der Komplexitätstheorie werden Probleme hinsichtlich verschiedener Komplexitätsmaße wie Laufzeit oder Speicherplatz klassifiziert. Algorithmen zur Lösung von Problemen, die sich durch eine besonders kurze Laufzeit bzw. einen besonders geringen Speicherplatz auszeichnen, werden effizient genannt. Eine wichtige Grundlage für die Entwicklung eines effizienten Algorithmus ist ein genaues Verständnis der dem Problem zugrundeliegenden Struktur. Es hat sich gezeigt, daß diese Strukturen sehr häufig als Graphen oder Hypergraphen modelliert werden können. Ein Schwerpunkt der Forschung am Lehrstuhl ist die Untersuchung zufälliger Graphen und Hypergraphen und die Anwendung der dabei erzielten probabilistischen und asymptotischen Resultate beim Entwurf und der Analyse von Graphenalgorithmen. Des weiteren werden in diesem Zusammenhang randomisierte und approximative Algorithmen systematisch studiert.
Eine Umsetzung der theoretischen Erkenntnisse in Algorithmen für praxisrelevante Probleme findet derzeit beim Verifizieren von VLSI-Schaltkreisen und im Rahmen eines weiteren Drittmittelprojektes bei der Lösung großer kombinatorischer Optimierungsprobleme im Bereich der Luftfahrtindustrie statt. Bei letzterem Vorhaben steht die Entwicklung paralleler Algorithmen im Vordergrund.
Projektförderung: Bundesministerium für Bildung und Forschung
Die Lösung kombinatorischer Optimierungsprobleme ist in vielen Bereichen von Wirtschaft und Technik der Schlüssel zur Steigerung der Effizienz technischer Abläufe, Verbesserung der Produktqualität und Verringerung von Produktions- und Materialkosten. In diesem Verbundprojekt, das gemeinsam mit der Universität Paderborn, der Universität Köln und der Deutschen Lufthansa durchgeführt wird, werden Verfahren zur Flugplanoptimierung entwickelt bzw. weiterentwickelt und auf Parallelrechnern implementiert.
Zur Lösung der dabei auftretenden kombinatorischen Optimierungsprobleme wird eine Reihe unterschiedlicher Verfahren auf ihre Effizienz hin untersucht. Durch die enge Kooperation mit der Lufthansa ist eine direkte Überprüfung der praktischen Einsetzbarkeit der entwickelten Verfahren gewährleistet.
Projektförderung: Deutsche Forschungsgemeinschaft (Projekt im DFG-Schwerpunktprogramm Effiziente Algorithmen für Diskrete Probleme und ihre Anwendungen)
Heutzutage werden komplexe VLSI-Chips zunehmend an sicherheitskritischen Stellen eingesetzt, wie zur Kontrollsteuerung von lebenserhaltenden Systemen in der Medizin, bei Automobilen, in Flugzeugen und als Verkehrsleitsysteme. Die Logik solcher Schaltkreise muß daher mit größtmöglicher Sicherheit die von ihr erwarteten Funktionen erfüllen. Absolute Sicherheit kann nur ein mathematischer Beweis bieten. Die enorme Komplexität von VLSI-Schaltkreisen und die damit verbundene Explosion der kombinatorischen Möglichkeiten machen aber einen Beweis von Hand praktisch unmöglich. Vielmehr kommt es darauf an, einen Algorithmus zu entwerfen, der die Realisierung eines Schaltkreises gegen die vorgegebene Spezifikation effizient testet.
In der industriellen Praxis ist die Simulation des Schaltkreises das zur Zeit dominierende Verifikations- Verfahren. Während die Logiksynthese und das physikalische Layout mit Hilfe kombinatorischer Algorithmen, die in den letzten 10 Jahren entwickelt wurden, schnell und effizient durchgeführt werden können, ist die Simulation einzelner Chips und erst recht eines Prozessors absolut zeitkritisch und beansprucht ca. 30 - 40% des Designprozesses.
Das Ziel des Forschungsprojekts ist es, mit Methoden der Algorithmischen Diskreten Mathematik, insbesondere der Kombinatorischen Optimierung, und probabilistischen Ansätzen neue Verfahren für die Verifikation von VLSI-Designs aufzuzeigen und diese an konkreten VLSI-Chips aus der Industriepraxis zu erproben.
Projektförderung: Deutsche Forschungsgemeinschaft
Nachdem probabilistische Argumente seit langem erfolgreich in der Graphentheorie benutzt werden, um die Existenz von Strukturen mit bestimmten Eigenschaften nachzuweisen, hat sich das Interesse in den letzten Jahren zunehmend den algorithmischen Möglichkeiten dieser Methoden zugewendet.
Das Ziel des Forschungsprojekts ist es, Untersuchungen über Existenz- und Abzählprobleme in Graphen und Hypergraphen weiterzutreiben und die gewonnenen Ergebnisse auf algorithmische Fragestellungen anzuwenden. Im Vordergrund steht hierbei insbesondere die Anwendung von probabilistischen und asymptotischen Resultaten bei dem Entwurf und der Analyse von Färbungsalgorithmen.
Projektförderung: Deutscher Akademischer Austauschdienst
Zusammenarbeit: University of Oxford
Im Rahmen des Projektes wird die Zusammenarbeit auf dem Gebiet der zufälligen Graphen und Algorithmen zwischen der Humboldt-Universität zu Berlin und der University of Oxford fortgesetzt und intensiviert. Hierbei steht die chromatische Zahl im Mittelpunkt des Forschungsinteresses.
Ziel ist es, ein besseres Verständnis für diesen Graphenparameter zu gewinnen, effiziente Algorithmen zur Berechnung der chromatischen Zahl unter bestimmten Nebenbedingungen zu entwickeln und das erworbene Wissen insbesondere auch zur Lösung verschiedener Probleme der Informatik und des Operations Research einzusetzen.
Zusammenarbeit: Adam-Mickiewicz-Universität Poznan
Seit Oktober 1995 findet regelmäßig ein gemeinsames Forschungsseminar mit einer Gruppe von Wissenschaftlern der Adam-Mickiewicz-Universität Poznan statt. Das Seminar wird abwechselnd in Poznan und Berlin abgehalten. Ziel dieses Seminars ist es, die Zusammenarbeit beider Gruppen auf den Gebieten zufällige Graphen, Ramsey-Theorie und randomisierte Algorithmen zu intensivieren.
Beteiligte Mitarbeiter: Petra Knieper
Projektförderung: Deutsche Forschungsgemeinschaft
Zusammenarbeit: Graduiertenkolleg an der Freien Universität. Es wird gemeinsam getragen von der Freien Universität Berlin, der Humboldt-Universität zu Berlin, der Technischen Universität Berlin und dem Konrad-Zuse-Zentrum Berlin.
Aus den klassischen Gebieten wie Kombinatorik oder Graphentheorie hat sich die Diskrete Mathematik unter Einbeziehung des algorithmischen Standpunktes zu einem Themenkreis entwickelt, der Aspekte der Grundlagen, wie auch der angewandten Wissenschaften vereint. Im Zentrum des Graduiertenkollegs stehen Themen, die in integraler Weise Fragen und Methoden aus Mathematik und Informatik verknüpfen, wie z. B. Bewegungsplanung, Mustererkennung, algorithmische Geometrie. Flankiert werden sie durch Grundlagengebiete wie Kombinatorik, Graphenalgorithmen und Graphentheorie, Geometrie und anwendungsorientierte Themen wie Numerik und Optimierung.
Ernst-Günter Giessmann
Dissertationen
Diplomarbeiten
Beteiligte Mitarbeiter:
Die technologische Basis aller Simulationswerkzeuge am Lehrstuhl bildet eine (vom PC bis zur Workstation) portable Kernbibliothek von Leichtgewichtsprozessen in C++. Diese ermöglicht einen konsequent objektorientierten Aufbau aller darauf aufsetzenden Anwendungen in den verschiedenen Projekten des Lehrstuhls. Gegenwärtig wird an einer neuen Version der Basisbibliothek gearbeitet, um bei Einhaltung der bisher definierten Schnittstellen die Effizienz und Robustheit des Kerns (Speicher- und Prozeßverwaltung) weiter zu verbessern. Auf der Basis einer Analyse von Simulationssystemen mit ähnlichen Grundansätzen ist die Kernbibliothek weiter zu konsolidieren, wobei die Grundfunktionalität beibehalten werden soll. Darüber hinaus werden ein hierachischer Prozeßverwaltungsapparat implementiert und Kombinationen mit kommerziellen Simulationswerkzeugen (z. B. SES Workbench) untersucht.
Beteiligte Mitarbeiter:
Eine Anwendung der Prozeßkernbibliothek besteht in der Implementation von sogenannten allgemeinen universellen Simulationssystemen in C++. Hier werden am Lehrstuhl sowohl rein diskrete (ODEM) und rein kontinuierliche (CADSIM), als auch kombinierte allgemeine Simulationssysteme entwickelt (COMBINEDSIM). Die Quellen der Systeme ODEM und CADSIM und der Prozeßkernbibliothek sind auf dem ftp-Server des Instituts unter ftp.informatik.hu-berlin.de: /pub/local/simulant/odem frei verfügbar. Neben dem Einsatz in der Lehre sind diese Bibliotheken vorrangig für eine Adaption im Kontext verschiedener Projekte einsetzbar, bei denen insbesondere auch der Aspekt kontinuierlicher Vorgänge eine wesentliche Rolle spielt. Die Arbeiten sollen künftig auf die Stream-Modellierung im Multi-Media-Bereich orientiert werden.
Beteiligte Mitarbeiter:
OpenSITE (Open SDL Integrated Tool Environment) ist eine Entwurfs-, Analyse- und Transformationsumgebung für Spezifikationen in SDL92 in Kombination mit unterschiedlichen Datentypspezifikationstechniken. Basis dieser Werkzeugumgebung ist ein Austauschformat (Common Representation), das mit der Eingabesprache des Meta-Werkzeugs Kimwitu definiert ist. Kimwitu stellt Funktionen für den transparenten Austausch von Informationen über die Spezifikation zwischen verschiedenen (Front-End/Back-End-) Programmen bereit. Diese Informationen sind unabhängig von der konkreten syntaktischen Repräsentation der Spezifikation, die in grafisch- oder programmiersprachlich- orientierter Form vorliegen kann. Damit sind sowohl die Anwendungen verschiedener SITE-Komponenten als auch ihre Weiterentwicklung unabhängig von der bisher realisierten Ausbaustufe. Die SITE-Umgebung ist damit insbesondere offen für ihrer Anbindung und Benutzung durch Werkzeuge anderer Hersteller.
Implementiert sind bisher folgende Komponenten:
Petrinetzbasierte Analysemethoden stellen einen wichtigen Beitrag für den Nachweis allgemeiner dynamischer Eigenschaften von SDL-Spezifikationen verteilter Systeme aus dem Telekommunikationsbereich, wie Verklemmungsfreiheit, dar. Auf Grund der Mächtigkeit der SDL-Semantik wurden Erweiterungen gegenüber den klassischen Petrinetzen vorgenommen: Zuordnung von Datenstrukturen zu Plätzen und von Zeitangaben und Guard-Funktionen zu Transitionen. Dadurch können solche Aspekte von SDL, wie Signalparameter und lokale Prozeßvariablen, die dynamische Erzeugung von Prozessen sowie das Verhalten von Signaleingabepuffern, lokalen Uhren und Übertragungskanälen adäquat zur SDL-Semantik und kompakt auf Netzebene modelliert werden. Die Realisierung dieses Ansatzes basiert auf einer automatischen Transformation der Ausgangsspezifikation in ein Netzmodell, einer Generierung und Analyse des Erreichbarkeitsgraphen des Netzes und einer Rücktransformation der Ergebnisse auf SDL- Niveau. Die entsprechenden Software-Komponenten sind im Rahmen der Entwicklungsumgebung OpenSITE integriert worden. Erste Untersuchungen von zwei Anwendungsbeispielen (INRES- und Sliding- Window-Protokoll) haben die praktische Relevanz dieses Ansatzes bestätigt.
Beteiligte Mitarbeiter: Dr. Reneé Mundstock
Projektförderung:
Beteiligte Mitarbeiter:
Beteiligte Mitarbeiter:
Weitere Forschungsprojekte in Fortsetzung von TERMO, bei denen insbesondere eine Orientierung auf die Architekturen CORBA, TINA und ODP von vorrangiger Bedeutung ist, sind in Vorbereitung.
Beteiligte Mitarbeiter: W. Dietmar Gellermann
Projektförderung:
Technologie zur Transformation zu entwickeln und deren Funktionstüchtigkeit an einem Prototyp zu demonstrieren. Auf der Basis von angestrebten struktur- und funktions- äquivalenten Klassenbibliotheken spezifischer Anwendungsbereiche des Auftraggebers soll eine Programmiermethodik entwickelt werden, die insbesondere Vorzüge von Smalltalk und C++ zu kombinieren gestattet. Eine Fortsetzung der Arbeiten in Richtung automatischer Sprachtransformationen wird gegenwärtig geprüft.
Beteiligte Mitarbeiter:
Beteiligte Mitarbeiter:
Bild 3.3 gibt einen schematischen Überblick über die einzelnen Phasen der Entwicklung und Validierung hybrider Hardware-Software-Systeme mit INSYDE.
Beteiligte Mitarbeiter:
In diesem Projekt werden Probleme im Zusammenhang mit dem Management flexibler, verteilter Telekommunikationsanwendungen untersucht. Solche Anwendungen bestehen aus interagierenden Objekten und zeichnen sich vor allem dadurch aus, daß erst zur Laufzeit bestimmt wird, welche Objekte auf welchen Systemen zu einer gewünschten Anwendung konfiguriert werden (late binding). Wir entwickeln eine Managementarchitektur, die dem Rechnung trägt und außerdem verschiedene Sichten (Views) auf eine Anwendung bzgl. Management unterstützt. Als Entwicklungsgrundlage benutzen wir eine SMALLTALK- basierte Verteilte Umgebung (FOCS - Flexible Objectoriented teleCommunication Services), die am Lehrstuhl entwickelt und implementiert wurde.
Zur Zeit werden im Rahmen von Studienarbeiten folgende Teilprobleme behandelt:
Projektförderung: Humboldt-Forschungsfonds
Das Projekt Flexible Objectoriented teleCommunication System (FOCS) wurde im Juli 1995 erfolgreich abgeschlossen. Ziel des Projektes war es, eine Technologie für die Programmierung verteilter objektorientierter Systeme zu entwickeln, die es den Applikationen gestattet, sich dynamisch an mit unterschiedlichen Ressourcen ausgestattete Einsatzumgebungen anzupasssen. Eine prototypisch hergestellte Entwicklungsumgebung ermöglicht experimentelle Analysen von FOCS-Konzepten und die Implementation von Beispielanwendungen. Die Leistungsfähigkeit von FOCS-basierten Anwendungen wurde verschiedenen Interessentenkreisen in mehreren Demos vorgeführt. Die im Rahmen dieses Projektes entwickelten Konzepte bilden die Grundlage für das Ende 1995 begonnene Nachfolgeprojekt MINT (Mobile Intelligent Network Terminal).
Aufbauend auf dem in den Vorjahren entwickelten System FOCS (Flexible Object-oriented teleCommunication Services) wird im Rahmen des Projektes MINT eine Architektur für verteilte Systeme entwickelt, die es dem Endnutzer erlauben soll, sich ein beliebiges Endgerät auszusuchen, sich mit diesem an einen (fast) beliebigen Ort der Erde zu begeben und dort seine gewohnte Arbeitsumgebung bereitgestellt zu bekommen. In Abhängigkeit vom ausgewählten Endgerät und von den am jeweiligen Einsatzort real vorhandenen Ressourcen (z. B. Netzwerkzugänge, Displays, Tastaturen, Drucker) wird diese eine jeweils andere konkrete Gestalt annehmen müssen. Die von ihr bereitgestellte Funktionalität, d. h. die Menge der angebotenen Teledienste, soll jedoch stets dieselbe bleiben. Um dies zu erreichen, definiert der Nutzer seine Arbeitsumgebung abstrakt, ohne dabei auf konkrete Endgeräte oder auf Ressourcen aus der Einsatzumgebung Bezug zu nehmen. Technologische Grundlage dafür bildet die Spezifikation von Dienstanbietern über sogenannte ServiceIDs, die im Rahmen des Vorgängerprojektes FOCS entwickelt wurde. Später, d. h. mit einem konkreten Endgerät und in einer konkreten Einsatzumgebung, wird vermöge einer Dienstvermittlungskomponente nach dem Vorbild des FOCS-Brokers bzw. des ODP-Traders für jedes abstrakte Element der virtuellen Arbeitsumgebung eine reale Entsprechung gefunden. Dabei kann es notwendig werden, daß Datenströme konvertiert werden müssen, natürlich ohne dabei die Semantik der Daten zu verändern. Ein Beispiel dafür ist der Teledienst "Email", wenn diesem kein Display, sondern lediglich ein Telefon zur Verfügung steht. In diesem Fall müssen dem Nutzer die für ihn eingegangenen Nachrichten vorgelesen werden. Das Projekt befindet sich noch in der Aufbauphase. Durch Bereitstellung eines Prototypen soll jedoch innerhalb kurzer Zeit das experimentelle Verifizieren der entwickelten Architekturkonzepte möglich sein.
1. Ablösung des MX500 durch einen Workstationpool
Im Wintersemester 1994/95 wurde der seit 1990 benutzte Siemensrechner MX500, der nur mit alphanumerischen Terminals ausgerüstet war, durch einen Pool moderner grafikfähiger Workstations ersetzt. Im einzelnen wurde dafür folgende Technik installiert:
Zum Wintersemester 1995/96 wurde ein neuer Fileserver für studentische Daten in Betrieb genommen. Dadurch wurde sowohl die Kapazität als auch der Netzwerkdurchsatz erhöht. Die Daten sind in den automatischen Back-up-service des Rechenzentrums einbezogen.
Zu Beginn des Wintersemesters 1995/96 konnte ein PC-Pool für LINUX in Betrieb genommen werden. Dieser gibt den Studenten die Möglichkeit, das häufig zu Hause genutzte Betriebssystem LINUX auch am Institut zu nutzen und notwendige Tests durchzuführen. Der Pool besteht aus folgenden Geräten:
Der PC-Pool des Instituts bestand aus 20 Siemens-PCs 386SX aus dem Jahre 1990. Davon konnten im Laufe des Jahres 1995 zehn modernisiert werden. Im einzelnen wurden folgende Komponenten modernisiert: Prozessor auf AMD486DX4 100 MHz, Hauptspeicher auf 8-MB-RAM, moderne Grafikkarte und neuer 17"- Farbmonitor. Damit sind alle für die Ausbildung genutzten Programme wieder lauffähig.
5. Datenprojektor
Zur Verbesserung der Projektionsmöglichkeiten von Daten wurde im Raum 427 ein Datenprojektor Typ Liesegang 1024 installiert. Der Projektor erlaubt die Projektion von Daten on-line. Ein PC ist ständig angeschlossen. SUN-Rechner und MAC-Rechner sind anschließbar. Das Gerät ist auch für die Projektion von Videos geeignet.
6. Terminalserver
Im Wintersemester 1994/95 wurde mit dem Aufbau eines Terminalservers begonnen, der den Studenten und Mitarbeitern die Möglichkeit gibt, die Rechner des Instituts via Telefon zu benutzen. Im Laufe des Jahres wurden insgesamt 6 ZyXEL-Modems Type U-1496EG+ und 6 ELSA-Modems Type MicroLink 28.8TQV installiert. Für die einzelnen Modemtypen wurden Sammelnummern geschaltet.
Folgende Dienste werden z. Z. angeboten: Telnet, Login, SLIP, PPP.
Das Gerät wird von Mitarbeitern und Studenten intensiv genutzt.
Nutzung des Terminalservers: Zeitraum Nutzer Verbindungen Dauer 4/95 81 342 138 h 5/95 151 3015 1215 h 6/95 165 2755 1161 h 7/95 166 2890 1249 h 8/95 160 3136 1249 h 9/95 187 3858 1077 h 10/95 199 3781 1193 h
7. Erneuerung des FTP-Servers
Der aus dem Jahre 1991 stammende FTP-Server wurde ständig erweitert und damit zunehmend technisch unzuverlässiger. Im Sommer 1995 wurde der neue FTP-Server SUNsparc5/110 mit 32-MB-Hauptspeicher, 8-GB-Festplatte und DAT-Laufwerk in Betrieb genommen. Er hatte noch 1995 eine Auslastung von:
Zeitraum Files Mbyte Systeme täglich Files Mbyte 4/95 13 683 3 415 546 441 110 5/95 11 524 2 485 708 360 77 6/95 17 415 4 673 1078 562 150 7/95 22 999 5 002 2284 852 185 8-11/95 62 054 16 141 7482 660 171
8. Erneuerung des NEWS-Servers
Im Sommer 1995 konnte der veraltete NEWS-Server durch einen neuen NEWS- Server des Typs SUNsparc5/110 (32-MB-Hauptspeicher, 4-GM-Festplatte) ersetzt werden. Durch den neuen Rechner konnten die Verweilzeiten für wichtige News-Gruppen verlängert werden. Z. Z. werden ca. 6300 Gruppen angeboten. Der NEWS-Server versorgt 150 Workstations mit NEWS. Täglich werden ca. 800 Artikel ge- lesen.
9. Aufbau des WWW-Servers
Der WWW-Server ist zu einem festen Bestandteil des Instituts geworden. Er erlaubt den Zugriff auf viele Datenbestände des Instituts und anderer Server in der Welt. Nutzung des WWW-Servers:
Zeitraum Dateien Mbyte Systeme täglich Dateien Mbyte 5/95 296 306 1 093 4 923 10 217 37 6/95 336 319 1 376 6 956 11 211 45 7/95 301 816 1 278 8 582 9 736 41 8/95 312 252 1 133 10 022 9 785 35 9/95 382 769 1 486 12 553 12 759 49 10/95 420 720 1 765 15 497 13 573 56
10. Netzwerkinfrastruktur
Die Netzinfrastruktur wurde vervollständigt, drei Server an den FDDI-Ring angeschlossen. Beide zentralen Router wurden mit FDDI-Adaptern ausgestattet, so daß der Durchsatz zwischen den einzelnen Netzsegmenten verbessert werden konnte. Weiterhin wurden fünf FDDI-Adapter für Workstations beschafft, die die Anbindung weiterer Lehrstühle an den FDDI-Ring ermöglichen.
Eine ATM-Teststrecke zum Hauptgebäude wurde in Betrieb genommen. Der ATM-Switch wurde auf 12 155-MBit/sec-Ports aufgerüstet, so daß dem weiteren ATM-Ausbau nichts im Wege steht. Weiterhin wurden 2 ATM-Adapter für Workstations beschafft. Damit kann ein lokaler ATM-Pool für Testzwecke eingerichtet werden.
11. Modernisierungen und Erweiterungen in den Lehrstühlen
Die rechentechnische Ausrüstung der einzelnen Lehrstühle konnte im Jahre 1995 verbessert werden. Am Lehrstuhl Automaten- und Systemtheorie wurde ein Workstationpool mit 10 SUN-Workstations in Betrieb genommen werden. Am Lehrstuhl Rechnerorganisation und -kommunikation konnte das ATM-Testfeld eingeweiht werden. Die Beschaffung eines weiteren Workstationpools für den Lehrstuhl Künstliche Intelligenz steht unmittelbar vor dem Abschluß. Außerdem wurden an einzelnen Lehrstühlen Workstations und PCs gekauft.
Dissertationen
Beteiligte Mitarbeiter:
Verteilte Algorithmen werden in der Literatur im wesentlichen programmiersprachlich beschrieben und informell verifiziert. Konzepte und Methoden zur formalen Darstellung und zur formalen Verifikation verteilter Algorithmen werden in diesem Projekt entwickelt.
Konzepte zur Modellierung verteilter Algorithmen sind nur zusammen mit angepaßten, einfachen, intuitiven Beweistechniken erfolgreich. Solche Techniken wurden und werden in diesem Projekt entwickelt. Dabei wird nicht ein möglichst ausdrucksstarker Formalismus angestrebt, sondern wenige einfache Konzepte mit einer Ausdruckskraft, die für die üblichen verteilten Algorithmen ausreichen. In der Literatur vorhandene Techniken, verteilte Algorithmen zu verifizieren, werden auf Petrinetze übertragen, dort untersucht und gegebenenfalls spezialisiert.
Erste Ergebnisse des Projektes zeigen, daß die formale Strenge des Ansatzes die intuitive Verständlichkeit der so formulierten Algorithmen nicht beeinträchtigt, sondern im Gegenteil erhöht: Sicherheits- und Lebendigkeitseigenschaften sind für verteilte Algorithmen klassische theoretische Konzepte, die der partiellen bzw. totalen Korrektheit in sequentiellen Algorithmen entsprechen. Diese Konzepte wurden für nichtsequentielle Abläufe verallgemeinert, Übertragbares wurde festgehalten und Grenzen aufgezeigt [Kindler 95c].
Nichtsequentielle Abläufe sind wesentlich, um intuitiv einfache Begriffe zu formalisieren. So wurde ein "Rundenbegriff" gebildet [Walter 95a, Reisig 95a], der intuitiv einfach ist, die wesentliche Idee eines Algorithmus verdeutlicht und die Verifikation unterstützt. In [Kindler et al. 95a] wurde ein spezielles Fairness-Konzept eingeführt und gezeigt, wie verschiedene Mutex-Algorithmen sich einheitlich unter Verwendung von Ableseregeln und Beweisgraphen korrekt beweisen lassen.
In [Desel et al. 95c] wurde vorgeführt, wie durch den Wechsel zwischen verschiedenen ungewöhnlichen Sichtweisen auf einen verteilten Algorithmus ein existierender Korrektheitsbeweis wesentlich vereinfacht werden kann. In [Walter 95a] wurde eine Reihe von nichttrivialen, aber kleinen verteilten Algorithmen untersucht und mit einem zusammenhängenden Verifikationsformalismus korrekt bewiesen. Vergleichbare Konzepte sind in [Reisig 95a] zusammengefaßt. Erste Fallstudien [Völzer 95a] zeigen, daß die vorgeschlagenen Konzepte auch auf High-level-Petrinetzmodelle übertragbar sind und welche neuen Verifikationstechniken für große Algorithmen vielversprechend sind.
Ausblick: Grössere verteilte Algorithmen müssen mit High-level-Petrinetzmodellen modelliert werden. In diesem Projekt wird nach weiteren, speziellen High-level-Konzepten gesucht, die die Modellierung und Verifikation von Netzwerkalgorithmen unterstützen. Eine Reihe von Algorithmen (Mutex-, Cross-talk-, Echo-Algorithmus) bilden die Basis für komplexere Algorithmen. Weitere solche Basisalgorithmen zu benennen, die typische Teilaufgaben klassischer verteilter Algorithmen lösen, ist ein Forschungsproblem.
Beteiligte Mitarbeiter: Hagen Völzer
Projektförderung: DFG-Projekt "Konsens-Algorithmen".
Zusammenarbeit: Lehrstuhl Rechnerorganisation und Kommunikation, Prof. Dr. Miroslaw Malek
Die zunehmende Verfügbarkeit preiswerter Kommunikationstechniken beschleunigt den Übergang von zentralen zu verteilten Rechnerkonfigurationen. Dabei bildet Konsens ein herausragendes Paradigma. Ziel des Projektes ist es, Konsenstechniken weiterzuentwickeln. Anhand von Fallstudien werden Prinzipien herausgearbeitet, die typischerweise in den Algorithmen vorkommen und Techniken zum Beweis der Korrektheit von Konsensalgorithmen entwickelt.
Zusammenarbeit: TU München, Sonderforschungsbereich 342, Gruppe des Teilprojekts A3
Verteilte Systeme sind häufig in eine Umgebung eingebettet, auf deren Ereignisse bzw. Eingabe das verteilte System reagiert. Solche Systeme nennt man reaktiv. Das Verhalten von reaktiven Systemen kann meist nur in Abhängigkeit von bestimmten Anforderungen an das Verhalten der Umgebung erfüllt werden und wird auch deshalb häufig in der Form "wenn die Umgebung erwartetes Verhalten zeigt, dann gewährleistet das System gewünschte Eigenschaften" beschrieben. Diese Art der Verhaltensbeschreibung nennt man Rely-guarantee-Spezifikation. Damit ist es auch möglich, verteilte Systeme aus Komponenten zusammenzusetzen und aus ihren Verhältnisbeschreibungen das Verhalten des Gesamtsystems zu gewinnen (Kompositionalität).
Bisher wurden überwiegend die theoretischen Grundlagen für kompositionale Beweismethoden untersucht. In [Kindler 95b] wurde das Zusammenspiel einer einfachen Kompositionsregel mit einer anderen Beweisregel, der Substitutionsregel, untersucht. Es zeigt sich, daß die Kombination beider Regeln große Sorgfalt erfordert. In der Dissertation [Kindler 95c] wurde ein kompositionales Petrinetzmodell eingeführt. Aufbauend auf diesem Modell lassen sich Systemkomponenten im Rely-Guarantee-Stil spezifizieren. Eine Spezifikation kann in Spezifikationen für Teilkomponenten zerlegt werden, die dann unabhängig voneinander implementiert werden können.
Werkzeuge können ebenfalls von einer Zerlegung in Komponenten profitieren. Untersucht wird eine Möglichkeit, die Komplexität der Analysealgorithmen dadurch zu verringern, daß der wesentliche Teil der Analyse in einem ersten Schritt getrennt für die Komponenten ausgeführt wird. Der erste Schritt liefert für die Komponenten Verhaltensbeschreibungen, die kompositional sind. Bei einer Wiederverwendung muß der erste Schritt nicht wiederholt werden.
Zusammenarbeit:
Zusammenarbeit:
In den letzten Jahren konnten zunehmend weitere, tieferliegende Konzepte der linearen Algebra zur Analyse von Petrinetzen nutzbar gemacht werden. Dazu gehören lineare Ungleichungssysteme, Gleichungssysteme über Mod-n-Körpern und auf dem Rang von Matrizen aufbauende Eigenschaften.
In diesem Projekt werden linear-algebraische Methoden zusammengestellt und auf verschiedenartige Fragestellungen beliebiger und spezieller Petri-Netze angewendet. Insbesondere wird untersucht, wie sich die Eigenschaften verteilter Algorithmen in linear algebraischer Form darstellen und beweisen lassen. Dies betrifft nicht nur die Verwendung von Invarianten zum Beweis von Sicherheitseigenschaften sondern auch linear algebraisch basierte Konzepte zur Untersuchung von Progress- und Lebendigkeitseigenschaften. Diese Forschungsansätze sind insbesondere im Rahmen der ESPRIT-Working-Group CALIBAN verfolgt worden. Eine Zusammenfassung findet sich im Tagungsband der an der Humboldt-Universität organisierten Abschlußtagung des Projektes [Desel 95b].
Projektförderung: DFG-Projekt Verifikation von Informationssystemen durch Auswertung halbgeordneter Petrinetzabläufe
Zusammenarbeit: Universität Karlsruhe (TH): Dr. Andreas Oberweis
Die Verifikation von Informationssystemen bzw. ihrer formalen Modelle durch Simulation scheitert oft an der großen Anzahl verschiedener Ausführungsfolgen. Dies giltverstärkt für verteilte Informationssysteme: Die Anzahl der Abläufe wächst dort exponentiell mit dem Grad der Nebenläufigkeit. Die systematische Konstruktion und Analyse der entsprechend den Kausalitätsbeziehungen halbgeordneten Abläufe überwindet dieses Problem. In diesem Projekt werden Modelle von Informationssystemen und ihre Abläufe durch höhere Petrinetze beschrieben. Für die Formulierung von dynamischen Systemeigenschaften wird eine anschauliche graphische Spezifikationssprache verwendet, deren Ausdrücke im Netzmodell integriert sind und die ohne Verwendung eines zusätzlichen Formalismus der temporalen Logik auskommt. Es werden Spezifikationen unterstützt, die kausal aufeinanderfolgende Ereignisse (bzw. lokale Zustände) fordern oder verbieten, was in herkömmlichen, auf Sequenzen und globalen Zuständen basierenden Spezifikationsmethoden nicht möglich ist. Ziel des Projekts wird sein, im Rahmen einer Methodik zur evolutionären Informationssystementwicklung werkzeugunterstützt Systemeigenschaften formulieren zu können und diese (halb-) automatisch durch Simulation und Analyse der Abläufe zu verifizieren.
Beteiligte Mitarbeiter: Dr. Jörg Desel
Projektförderung: Bundesministerium für Bildung, Wissenschaft, Forschung und Technologie
Zusammenarbeit: Technical University Santiago, Chile, Prof. César Fernandez, Dr. Mauricio Solar
Verteilte Algorithmen werden in der Literatur im wesentlichen programmiersprachlich beschrieben. Es wird an Hand von Fallstudien untersucht, wie der Entwurf verteilter Algorithmen für massiv parallele Rechnersysteme durch die Verwendung von Petrinetzen verbessert werden kann. Weiter wird die anschließende Implementation betrachtet. Ziel ist es, eine Entwurfstechnik herauszuarbeiten und ihre Adäquatheit durch die Fallstudien zu belegen.
Beteiligte Mitarbeiter:
Zusammenarbeit:
Zusammenarbeit: TU München, Prof. Dr. Javier Esparza
Free-Choice-Petrinetze stellen einen besonders guten Kompromiß zwischen Ausdruckskraft und Komplexität der Analyse dar. Während für Free-Choice-Petrinetze eine Vielzahl nichttrivialer Charakterisierungen dynamischer Eigenschaften gezeigt werden konnte, gelten nur wenige dieser Eigenschaften noch für leichte Verallgemeinerungen dieser Klasse. Die Forschungsarbeiten an diesem Projekt fanden ihren Abschluß mit dem unter [Desel et al. 95a] angegebenen Buch.
Mitglied in Programmkomitees
Gutachter für Konferenzen
Dissertationen
Beteiligte Mitarbeiter: Dragan Macos
Projektförderung: Senat, nach dem Nachwuchsförderungsgesetz (NaFöG)
Das Projekt zielt auf die Auswertung, den Vergleich und die Verallgemeinerung von Untersuchungen zu Quelltextcompilern. Quelltextcompiler sind spezielle Compiler, die Programme einer höheren Programmiersprache in Programme einer anderen höheren Programmiersprache überführen.
Seit Ende der 80er Jahre werden Quelltextcompiler in einer Vielzahl von Einzelprojekten untersucht, wobei folgende offene Probleme auftreten, auf deren Lösung unsere Aktivitäten gerichtet sind:
Durch die Konzentration auf Einzelentwicklungen existieren keine verallgemeinernden Untersuchungen zur Bewertung und zum Vergleich von Quelltextcompilern. Somit fehlt auch jede Orientierung für Nutzer von Quelltextcompilern, insbesondere dann, wenn mehrere Produkte zur Auswahl stehen.
Ebensowenig wurden Forschungsaktivitäten zur systematischen Entwicklung eines Quelltextcompilers von seiner Spezifikation bis hin zu seiner Implementation (u. U. über allgemeine bzw. spezielle Softwarewerkzeuge) geleistet. So fehlen beispielsweise weitestgehend Versuche, die realisierte Transformation nutzergerecht und vollständig zu spezifizieren.
Das Potential von Quelltextcompilern über den compilertechnischen Aspekt hinaus bleibt weitestgehend unerschlossen (z. B. für das Reverse Engineering, für Tutorsysteme zur Unterstützung des Umstiegs zwischen höheren Programmiersprachen).
Gegenwärtige Aktivitäten der Gruppe in diesem Projekt sind:
Quelltexttransformation (Dragan Macos).
Programme.
Teilprojekt 1: Methoden der Codeduplizierung
Das Projekt untersucht Methoden zur Vermeidung von (a) bedingten und (b) unbedingten Sprüngen mittels Codeduplizierung. Die Konzepte wurden erarbeitet, implementiert und ausgewertet bzgl. der Anzahl der ausgeführten Instruktionen und des Cache-Verhaltens (siehe Publikationen). Derzeit wird untersucht, wie sich die Methoden zu (a) und (b) gegenseitig beeinflussen und kombinieren lassen.
Teilprojekt 2: Portables Instruktionsscheduling für optimierende Compiler auf modernen Rechnerarchitekturen (RISC und superskalar)
Ein optimierendes Compiler-Back-End soll durch eine Spezifikation von Prozessoreigenschaften ergänzt werden, die eine portable Implementation von Varianten des Instruktionsscheduling erlaubt. Das Instruktionsscheduling wird im Hinblick auf Caches und superskalare Architekturen durchgeführt, d.h., für Caches wird eine Reduzierung der Cache-Miss-Rate und für superskalare Architekturen die parallele Nutzung aller funktionalen Einheiten angestrebt. Das Projekt befindet sich in der Planungsphase.
Teilprojekt 1: Programmierkonzepte für parallele und verteilte Umgebungen
Es werden Konzepte des Shared-memory-Modells zur Synchronisation in parallelen Systemen sowie deren Abbildung auf verteilte Systeme untersucht. Dazu wurde eine POSIX-Threads-Bibliothek (Pthreads) konzipiert und implementiert. Die Pthreads-Bibliothek wird von ca. 300 Anwendern weltweit genutzt. Weiterhin wurde sie bereits zur Unterstützung von Ada 95 Tasks im Rahmen des Gnu-Ada-Translators (GNAT) eingesetzt und wird z. Z. noch weiterentwickelt. In diesem Zusammenhang soll untersucht werden, ob eine hinreichend effiziente Implementierung von Ada 95 Tasks (d. h. einem shared-memory Modell) in einer verteilten Umgebung möglich ist.
Teilprojekt 2: Echtzeitsysteme: Analytische Bestimmung der Laufzeiten und Betriebs- systemunterstützung für responsive Systeme und Realzeitsysteme
Das Projekt konzentriert sich auf zwei Schwerpunkte. Erstens werden Methoden zur analytischen Bestimmung der Worst-case-Laufzeit von Echtzeit-Tasks untersucht, insbesondere für moderne RISC- Architekturen mit Pipelines und Caches. Die Laufzeiten dienen als Grundlage zum Scheduling der Tasks in einem Echtzeitsystem. Zweitens ist ein Echtzeit-Micro-Kernel (aus der Pthreads-Bibliothek für Sun SPARC VME Boards, siehe vorheriges Projekt) entwickelt worden, der ein deterministischeres Zeitverhalten als ein UNIX-Kernel aufweist. Dieser Kernel kann sowohl als Testumgebung zur Bewertung der Zeitanalysen benutzt werden als auch für Weiterentwicklungen zur spezifischen Unterstützung von Echtzeit- Betriebssystemen. Die Untersuchung beider Schwerpunkte wird im Hinblick auf responsive Systeme erweitert.
Lehr- und Forschungseinheit
Beteiligte Mitarbeiter:
Relationale Datenbanksysteme haben sich in den vergangenen zehn Jahren zur Datenverwaltung durchgesetzt. Mit ihrem vermehrten Einsatz wird auch der Bedarf nach Steigerung ihrer Leistungsfähigkeit immer wichtiger. Ursachen hierfür sind sowohl die immer umfangreicheren Datenmengen, die in einem Datenbanksystem zu verwalten sind, als auch die komplexeren Anfragen über diese Daten und die erweiterte Funktionalität der DB-Schnittstelle.
Der Optimierer in einem Datenbanksystem erzeugt aus einer deklarativen Anfrage einen effizienten prozeduralen Anfrageausführungsplan. Unter Berücksichtigung der Parallelität nimmt die Komplexität des Lösungssuchraums drastisch zu. Optimiereransätze aus nichtparallelen Datenbanksystemen sind deshalb nur eingeschränkt bertragbar. Im Rahmen von EXPLORE (EXtensible ParalleL Optimization REsearch) sollen grundsätzliche Fragestellungen zur Optimierung in parallelen Datenbanksystemen untersucht werden.
In EXPLORE wird ein erweiterbarer und adaptiver Optimiereransatz verfolgt: Der Optimierer soll an veränderten oder neuen, sich möglicherweise verndernde Ausührungsumgebungen einfach angepaßt werden können. Weiterhin soll es möglich sein, ihn um neue logische Operationen und verschiedene Algorithmen dafür erweitern zu können. Ebenso wichtig ist es auch, zusätzliche Optimierungsverfahren einfügen zu können sowie eine Auswahlstrategie zur Verfügung zu stellen, die zwischen diesen unterschiedlichen Verfahren auswählen kann.
Zwei Aspekte werden in EXPLORE besonders betrachtet: Optimierung als Bestandteil der Abarbeitung, d. h. dynamische Optimierung und Parallelisierungsmöglichkeiten des Optimierungsvorgangs selbst.
Teilbereich exSPECt: Spezifikationsmethoden für parallele Anfragebearbeitung: Um mögliche Ansatzpunkte für die Optimierung von Anfragen an parallele DBS finden und bewerten zu können, ist zunächst eine Analyse der Abarbeitung in Form einer formalen Spezifikation nötig. Im Fall einer sequentiellen Verarbeitung kann die benötigte Komponentenspezifikation durch sog. relationen-algebraische Ausdrücke formuliert werden, die das Eingabe-Ausgabe-Verhalten definieren. Bei einer Abarbeitung in einer parallelen Umgebung kommen jedoch weitere Aspekte hinzu, die durch die relationale Algebra nicht mehr abgedeckt werden können: Die Gruppierung von Operatoren zu Prozessen sowie die Organisation der jeweils erforderlichen Interprozeßkommunikation.
Teilbereich Kostenmodellierung: Der Einfluß gegebener System-Parameter wie Architektur, Hardwaredaten, Datenvolumen und -verteilung, Komplexität der Anfrage auf die Effizienz der Anfragebearbeitung soll untersucht werden. Ziel ist es, die gegebenen Parameter bezüglich ihres Einflusses zu klassifizieren und für jede Klasse Regeln für die Anwendung statischer wie auch dynamischer Optimierungsstrategien zu finden. Ausgangspunkt hierfür ist ein einheitlicher Rahmen bestehend aus Ausführungs- und Kostenmodell. Das Ausführungsmodell soll unabhängig von der Systemarchitektur sein. Das Kostenmodell soll alle relevanten Kostenfaktoren beachten und somit die Kosten, die bei der Abarbeitung eines Anfrageplanes anfallen, adäquat vorhersagen. Durch Anwendung auf bereits in der Literatur untersuchte Spezialfälle sowie durch Simulation sind diese Vorhersagen zu verifizieren.
Teilbereich Suchstrategien: Ein weiterer Teilbereich ist die Konzeption und die Implementierung von neuen Suchstrategien aus dem Bereich des "evolutional computation". In dieser Arbeit soll ein Vergleich zu den bekannten Algorithmen Iterativ Improvement, Simulated Annealing und Treshold Accepting gezogen werden, die in einem prototypisch implementierten, parallelen Optimierer für Join-Ordnungen vorhanden sind. Die Flexibilität und der systeminhärente parallele Charakter der Genetischen Algorithmen läßt diesen Ansatz vielversprechend aussehen.
Das Projekt AIMS (Aktives Informations Management System) befaßt sich mit Techniken zur effizienten Situationserkennung in aktiven Datenbanken.
In den letzten Jahren ist zu beobachten, daß Anwendungen und Basissysteme sich von monolithischen Implementierung zu einem modularen Ansatz entwickeln. Immer komplexer werdende Systeme werden als eine Menge modularer Aufgaben verstanden, die eine explizite Steuerung und Kooperation benötigen. Erweiterte Transaktionskonzepte und Workflow-Management-Systeme bieten interessante Ansätze zur Spezifikation und Implementation komplexer Anwendungen. In diesem Zusammenhang können Sprachmächtigkeit und Techniken aktiver Datenbankmanagementsysteme (DBMS) eingesetzt werden. Sie erlauben die Definition von Regeln der Form "IF Situation THEN Action". Wurden sie ursprünglich hauptsächlich für transaktionsgebundene Integritätsüberwachung entwickelt, erlauben neuere Konzepte die Implementierung von Reaktionen auf transaktionsübergreifende und komplexe Situationen.
Besonders interessant sind Anwendungen, in denen weniger der reguläre Ablauf, sondern vielmehr die Reaktion auf komplexe, seltener auftretende Ausnahmesituationen in langlebigen Prozessen mit Hilfe aktiver DBMS implementiert werden sollen. Eine komplexe Situation wird in aktiven Datenbanken spezifiziert als ein algebraischer Ausdruck über einfache und kombinierte Ereignis- und Kontextinformation. Zur Laufzeit werden Ereignis- und Situationsinformationen nicht nur über Transaktionsgrenzen, sondern über die gesamte Lebensdauer der Anwendung aufgehoben und verarbeitet.
Die Komplexität der Situationserkennung ergibt sich daher einerseits aus der Anwendung selbst, die sich auf komplexe Ausnahmesituationen spezialisiert, andererseits aus der bei langlebigen Prozessen auftretenden großen Informationsmenge, die beobachtet und verarbeitet werden muß. Die Zuverlässigkeit der Situationserkennung hängt davon ab, daß keine der gesuchten Situationen übersehen wird. Über längere Zeiträume hinweg entstehen dadurch große Mengen von unvollständigen Situationsinformationen, die vielleicht niemals in die spezifiziertkritische Situation einmünden. Gleichzeitig wird gefordert, daß keine irrelevanten Informationen mitverarbeitet werden, insbesondere keine irrelevanten Situationen, die Regel-Aktionen auslösen. Deshalb ist es für die Effizienz der Situationserkennung von entscheidender Wichtigkeit, die relevante Informationsmenge und damit auch die Relevanzprüfungen auf ein handhabbares Maß einzuschränken und den Zugriff durch speziell geeignete Datenstrukturen zu erleichtern.
In dieses Projekt werden Methoden und Kozepte zur systematischen Evaluierung von Anfrageoptimierern in relationalen Datenbanksystemen entwickelt und implementiert. Im Gegensatz zur Nutzung von Benchmarkmethoden, bei denen Anfragen bzw. Relationen zur Überprüfung statisch vorgegeben werden, sollen in diesem Projekt die Möglichkeiten geschaffen werden, den Entwicklern von Datenbanksystemen bzw. Datenbankadministratoren ein flexibles "Werkzeug" zu schaffen, mit dessen Hilfe Testumgebungen erzeugt werden können, die den individuellen Bedrfnissen der Anwendungsumgebung entsprechen. Diese Testumgebung kann individuell spezifiziert und nach Kritierien generisch aufgebaut werden, die sowohl optimiererspezifische als auch anwendungsrelevante Parameter widerspiegeln.
In diesem Projekt werden zur Umsetzung dieser Ziele im wesentlichen drei Komponenten entwickelt, die den Grundstein einer Testumgebung legen sollen:
Beteiligte Mitarbeiter:
Dipl -Phys. Volker Gaede
Anhand konkreter Anwendungen soll in diesem Projekt untersucht werden, welche zusätzlichen Konzepte und Datenbankkomponenten für eine bessere Unterstützung der Anwendungen notwendig sind. Dabei stand im vergangenen Jahr exemplarisch das Anwendungsgebiet der "Geo-Informationssysteme" im Vordergrund. Insbesondere werden für Probleme der Anfragebearbeitung und -optimierung mit der Entwicklung von Approximationsverfahren und mit einer erweiterten Geo-Algebra neue Lösungen angeboten.
Weiterhin werden existierende Datenbanksysteme mit neuen Funktionalitten auf ihre Einsatzmöglichkeiten hin untersucht. Die Datenbankgruppe ist in diesem Zusammenhang einer der weltweiten Beta-Test-Site für das neue IBM-Datenbankprodukt DB2/Solaris, bei dem sowohl seine Stabilität als auch der Umgang mit großen Datenmengen und die Verwendung von benutzerdefinierten Datentypen und -funktionen im Vordergrund stehen.
Projektförderung: ESPRIT Working Group 8666
Zusammenarbeit:
Lehr- und Forschungseinheit
Zusammenarbeit:
Existierende Techniken zur Fehlerdiagnose an technischen Systemen beruhen im wesentlichen auf einer adäquaten Modellierung des technischen Systems oder - im Falle von regelbasierten Expertensystemen - auf einem konsolidierten Erfahrungsschatz. Für komplexe und heterogene Anlagen sind solche Diagnoseverfahren nicht immer möglich oder sinnvoll. Hier bietet eine Sammlung konkreter Fehlerfälle die Alternative der fallbasierten Diagnose.
Im Projekt werden Grundlagen zur fallbasierten Fehlerdiagnose an technischen Systemen untersucht. Falldaten über Fehler und ihre Ursachen werden durch menschliche Experten rechnergestützt erfaßt. Eine Diagnose erfolgt dann durch Auswertung dieser Falldaten, z. B. durch Verallgemeinerung und Vergleich.
Die Untersuchungen konzentrieren sich auf Methoden zur strukturierten Repräsentation von Falldaten und auf Grundlagen fallbasierten Schließens (räumliches und zeitliches Schließen, Repräsentation elektrischer Domänen). Zur Erfassung von Fällen wurde das System "Fallexperte-D" entwickelt. Die aktuelle Arbeit untersucht Diagnosefälle und ihre Modellierung für Störungen und Probleme in Rechnernetzen. Die Modellierung zeitlicher Zusammenhänge erfolgt im Rahmen mehrwertiger Logiken.
Die Kommunikation innerhalb eines Krankenhauses (Charité) soll von Agenten gesteuert werden. Agenten sind für die Verteilung der Informationen an die relevanten Stellen zuständig. Ein Informationsnetz verbindet zunächst das Rechenzentrum (Agentenzentrale), eine diagnostische Einrichtung und eine Station. Folgende Aufgaben sind z. B. durch Agenten auszuführen:
Anwendungen des Fallbasierten Schließens erscheinen kognitiv adäquat gerade im Bereich der Medizin. Kernpunkt sind Untersuchungen zur Fallmodellierung über medizinische Domänen, die Definition der Ähnlichkeit von medizinischen Fällen, der Aufbau einer Falldatenbasis (vorerst Urologie), die sich an assoziativen Speicherstrukturen orientiert, um insbesondere ein schnelles Fallretrieval und die Adaption von Fällen zur Diagnoseunterstützung zu realisieren. Im Rahmen einer Studie zu effektiven Speicherstrukturen, die von Datenbanken zu konnektionischen Ansätzen (Neuronale Netze) reicht, wurden Möglichkeiten einer Fallrepräsentation mit schnellem Zugriff untersucht. Die Einbettung eines Fallbasierten Systems zur Diagnoseunterstützung in der Urologie soll in das Rechnernetz der Charit durch den agenten-orientierten Ansatz realisiert werden.
Retrievaltechniken
Das fallbasierte Schließen orientiert sich an der Arbeitsweise von Experten auf vielen Gebieten: Ärzte, Rechtsanwälte, Mechaniker arbeiten häufig "kasuistisch": Zwar ist für die Bewertung von Problemsituationen auch Hintergrundwissen z. B. in Form von Modellen, Regeln etc. notwendig, jedoch kommt dies nur im Kontext eines bestimmten Problemfalles zur Anwendung. Ein Schwerpunkt der Forschungstätigkeit stellt die Entwicklung von Retrievaltechniken dar, die die Effizienz von Datenbankanfragen mit der Flexibilität von Assoziativspeichern verbinden. Dabei werden netzartige bottom-up-Techniken entwickelt, implementiert und erprobt (Case-Retrieval-Netze). Weitere Ansätze basieren auf Techniken des Lernens und des effektiven Aufbaus von Suchbäumen.
Anwendungen
Fallbasierte Reiseberatungssysteme: Ziel ist die Reaktion mit konkreten Angeboten auf nur vage und unvollständig formulierte Zielvorstellungen. Die Antworten erfolgen in der Reihenfolge der höchsten Ähnlichkeit zwischen der Anfrage und den gespeicherten Datensätzen. Falls bestimmte Wünsche nicht realisierbar sind, macht das System entsprechende Ersatz-Vorschläge nach der gleichen Strategie. Die eingesetzen Case-Retrieval-Netze erlauben prinzipiell die Variation von Ähnlichkeit und Relevanz sogar zur Laufzeit.
Fallbasierte Unterstützung der Immobilienbewertung: In Zusammenarbeit mit der Hypo-Bank wird ein Projekt durchgeführt, das die Anwendbarkeit fallbasierter Techniken bei der Bewertung von Immobilien überprüfen soll. Hintergrund dieses Ansatzes ist das sogenannte "Vergleichswertverfahren", das auf diesem Gebiet Anwendung findet und in Form eines prototypischen fallbasierten Systems implementiert werden soll.
CBB: Mit dem System CBB wird ein Mittel zur Programmierung von Agenten bereitgestellt. Damit soll man Anwendungen im Bereich von wissensbasierten offenen Systemen, also Systemen mit dynamischer Struktur, dezentraler Steuerung, lokaler Information (Wissensbasis), asynchroner Kommunikation und kontinuierlicher Bereitschaft programmieren können.
Bedienung mathematischer Software für Modellierung chemischer Prozeße: Ziel ist die Bestimmung zutreffender Modelle und Parameter für die Beschreibung chemischer Prozesse passend zu experimentell gewonnenen Daten. Der aufwendige Prozeß soll durch programmierbare Agenten (Spezialisten und Operatoren) automatisiert werden.
Modelle für Multi-Agenten-Systeme
Während Zustandsbetrachtungen für die Beschreibung einzelner Agenten bevorzugt werden, spielen Aktionen und Ereignisse eine vorrangige Rolle bei der Untersuchung von Beziehungen zwischen den Agenten. Die mentalen Begriffe (z. B. belief, desire, intention) lassen sich auch auf dieser Ebene formalisieren. Damit ergeben sich Zusammenhänge zwischen den mentalen Begriffen unter den verschiedenen Gesichtspunkten (global, lokal, individuell) einerseits und dem Verhalten des gesamten System bzw. der einzelnen Agenten andererseits. Unser Ansatz stellt die Ereignisfolgen (histories) in den Mittelpunkt. Systembeschreibungen und Agentenbeschreibungen erfolgen im Rahmen formaler Sprachen. Dabei wird die Technik des nondeterministic interleaving zugrunde gelegt, und es ergibt sich ein vergleichsweise einfacher Formalismus.
Wissensrepräsentation und Inferenz für Agenten
Bezogen auf sein Anwendungsgebiet muß der Agent Bereichs- und Handlungswissen verwalten. Verfolgt werden Ansätze auf Grundlage der Prädikatenlogik erster Stufe sowie einer mehrwertigen Logik.
Implementiert wurde ein auf dem widerlegungsvollständigen Tableaukalkül basierender Theorembeweiser (in PROLOG). Modifikationen dienen der effizienteren Verarbeitung und der Implementierung von nichtmonotonen Logiken. Im Falle der Wissensrepräsentation in der minimalen terminologischen Logik arbeitet der Theorembeweiser als Entscheidungsalgorithmus. Um Inferenzprobleme in einem einheitlichen Rahmen zu untersuchen, wird eine mehrwertige Logik unter Verwendung der mathematischen Struktur des Zweifachverbandes aufgebaut. Zweifachverbände werden zur semantischen Begründung logischen Schließens herangezogen. An einer entsprechenden Inferenzprozedur für mehrwertige Logiken wird gearbeitet.
Es werden randomisierte Algorithmen zur Lösung komplexer Optimierungsaufgaben entwickelt, getestet und miteinander verglichen. Insbesondere wurden adaptive randomisierte Such-Algorithmen untersucht, d. h. Algorithmen, bei denen man mit jeder Näherung den Zielfunktionswert fast sicher verbessert. Diese Algorithmen sind besonders wichtig, da ihre Komplexität lediglich linear von den Problemdimensionen abhängt. Es zeigt sich jedoch, daß ihre numerische Implementation außerordentlich schwierig ist. Obwohl diese Algorithmen fast sicher gegen das Optimum konvergieren, kann die Konvergenzgeschwindigkeit in konkreten, im allgemeinen ungünstig konfigurierten Problemstellungen sehr langsam sein. Ein typisches Beispiel hierzu illustrieren die Diagramme für ein konvexes Optimierungsproblem.
Beim Simulated Annealing-Algorithmus handelt es sich um ein einfach zu implementierendes stochastisches Approximationsverfahren zur Lösung umfangreicher kombinatorischer Optimierungsprobleme, die u. a. im VLSI-Design und in der Bildverarbeitung auftreten.
Neben praktischen Aspekten wie dem Implementieren von Programmen und dem statistischen Auswerten von Programmabläufen stehen theoretische Fragen, etwa nach der Konvergenz des Algorithmus und den Beziehungen zur Mathematischen Physik, im Mittelpunkt des Interesses. Grundlage hierfür ist die Theorie der Markoffschen Ketten.
Lehr- und Forschungseinheit
Prof. Dr. Miroslaw Malek
Team Berlin
Mitarbeiter:
Mitarbeiter:
Die Gruppe besteht aus Wissenschaftlern und Mitarbeitern des Instituts für Informatik an der Humboldt-Universität zu Berlin und des Department of Electrical and Computer Engineering an der University of Texas at Austin.
(Bild 3.5: Wurzeln unserer Forschungsprojekte)
1. Responsive Systeme
Responsive Systeme sind Einzel- oder Multiprozessorsysteme, die bei Einhaltung definierter Fehler- und Lastannahmen den gewünschten Service innerhalb eines definierten Zeitraumes liefern, d. h. fehlertolerante und echtzeitfähige Systeme. Unser Ziel ist Forschung auf dem Gebiet des responsiven Rechnens mit realitätsnahen Anwendungen, wie Prozeßsteuerungen, Transportsystemen und anderen Gebieten mit signifikantem ökonomischen Einfluß und entsprechender Relevanz.
Schwerpunkte
Analyse, Modellierung, Simulation von responsiven Systemen.
(Bild 3.6: Struktur unserer High-Performance Responsive Computing Umgebung)
Konsens ist ein zentrales Paradigma innerhalb unserers Ansatzes zum Entwurf responsiver Systeme: Synchronisation, Scheduling, Initialisierung, Terminierung und Konsistenz können als Konsensprobleme betrachtet werden. Deshalb ist Konsens die Grundlage des CORE-Projekts (COnsensus for REsponsiveness) das von der ROK-Gruppe entwickelt wird. Um Konsens unter einer Gruppe von teilweise redundant arbeitenden Rechnern zu erzielen, führen die Rechner, die einer Problemlösungsgruppe zugeordnet sind, Konsensprotokolle durch, wie z. B. Mehrheitsabstimmungen oder Byzantinisches Agreement. Diese Protokolle führen entweder dazu, daß das Ergebnis eines fehlerhaften Knotens maskiert oder der fehlerhafte Knoten diagnostiziert wird. Beides ist äquivalent.
Alle diese Protokolle haben eine Eigenschaft, die sich negativ auf ihren Einsatz in Echtzeitsystemen auswirkt: sie brauchen relativ viel Zeit. Deshalb entwickelten wir in diesem Jahr das Prinzip der "frühen Entscheidung" (early decision) und wendeten es auf Konsensprotokolle an. Eine "frühe Entscheidung" erhöht die Performance dadurch, daß ein Ergebnis geliefert wird, auch wenn das Protokoll noch nicht vollständig abgearbeitet ist oder sich noch nicht alle Gruppenmitglieder beteiligt haben. Dieser Ansatz unterscheidet sich vom Prinzip der "ungenauen Berechnung" (imprecise computation): es besteht keine Einschränkung auf lineare Berechnungen; auch ist ein Ergebnis nicht "ungefähr" richtig, sondern entweder (im Rahmen des benutzten Algorithmus) korrekt oder aber falsch. Einem Ergebnis, welches aufgrund eines Early-Decision-Protokolls ausgegeben wird, ist dabei ein Wert zugeordnet, der aussagt, mit welcher Wahrscheinlichkeit ein korrektes Resultat vorliegt. Die empfangende Instanz kann dann entscheiden, ob dieses Resultat verarbeitet wird, oder ob sie auf ein nächstes Resultat, das eine höhere Korrektheitswahrscheinlichkeit hat, wartet.
Um die Eigenschaft der Responsivtät nicht nur abstrakt zu postulieren und auf Betriebssystemebene zu implementieren, sondern auch konkret auschaulich zu machen und Erfahrungen mit Anwendungen zu sammeln, haben wir uns die Aufgabe gestellt, eine responsive Beispielapplikation zu implementieren. Unsere Wahl fiel auf die Implementieren eines "Robusten Orchesters", bei dem jedes Mitglied (Computer) ein Instrument eines Musikstückes spielt. Bei Ausfall eines Rechners soll sein Part online von einem anderen übernommen werden. Die Probleme der Responsivität - Fehlertoleranz und Echtzeitverhalten - lassen sich an diesem Beispiel sehr gut demonstrieren. Es liegt eine Vorimplementation des "Robusten Orchesters" vor, die zwar schon die meisten Grundprinzipien verwendet, jedoch noch an das CORE-System angebunden ist.
Responsivität beinhaltet sowohl die Eigenschaft der Fehlertoleranz, als auch die der Echtzeitfähigkeit, also der Möglichkeit, unter bestimmten Lastannahmen Garantien über Laufzeiten geben zu können. Gängige Betriebssysteme sind in der Regel nicht echtzeitfähig. Die Grundlage jedes Echtzeit-Rechnens ist Scheduling. Um bekannte und bewiesene Scheduling-Strategien wie EDF (Earliest Deadline First) oder RMS (Rate Monotonic Scheduling) in unserer responsiven Umgebung einsetzen zu können, entwickeln wir einen Scheduling-Server, der solche Strategien realisiert.
(Bild 3.7: Phasenmodell der Programmausführung)
Als Grundlage dient die Fixed Priority Policy, die der MACH-Betreibssystemkernel zu Verfügung stellt. Der Scheduling-Server läuft mit einer sehr hohen Priorität. Er ermittelt die nach der jeweiligen Echtzeit- Strategie auszuführende Task. Deren Priorität wird stark angehoben (bis knapp unter die Server-Priorität). Anschließend geht der Server für eine bestimmte Zeit "schlafen". In dieser Zeit steht der geschedulten Echtzeit-Task die Rechenressourcen zur Verfügung. Nach Ablauf der Zeit (oder bei Beendigung der Task) wird der Scheduling Server wieder aktiv. Er senkt angehobene Prioritäten wieder und geht erneut "schlafen". Jetzt können Betriebssystemtasks und nichtechtzeitkritische Anwendungstask entsprechend der üblichen Strategie des MACH-Schedulers abgearbeitet werden. Durch diese Maßnahme wird gewährleistet, daß ohne direkten Eingriff ins Betriebssystem alle Betriebssystemfunktionen ausgeführt werden können, aber gleichzeitig für zeitkritische Anwenderprogramme bestimmte Garantien abgegeben werden können. Da auf diese Weise nur ein Teil der Rechenzeit als Echtzeit-Rechenzeit zur Verfügung gestellt wird, hat das Verhältnis von Systemzeit zu Echtzeit-Zeit einen entscheidenden Einfluß auf die Effektivität des Verfahrens. Daher wird sowohl durch umfangreiche Experimente als auch durch theoretische Betrachtungen versucht, optimale Parameter für dieses Schedulingverfahren zu finden.
2. Paralleles Rechnen in verteilten Umgebungen
Parallele Architekturen haben sich bisher nur in wenigen, speziellen Anwendungsfällen durchsetzen können. Gründe dafür sind die schwierige Programmierbarkeit und schlechte Softwareunterstützung für Parallelrechner sowie deren hohe Kosten. Zudem veraltet die spezielle Hardware paralleler Systeme schnell. Beachtliche Rechenleistungen können auch von vernetzten, kooperierenden Workstations erbracht werden, die heute schon in großer Zahl installiert sind. Wir beschäftigen uns mit netzwerkbasierten Parallelrechnern, die als Multicomputer-Systeme Workstations unter Benutzung schneller lokaler Netze integrieren.
Schwerpunkte
Unter dem Titel "Shared Objects Net-interconnected Computer (SONiC)" werden neue Ansätze zum parallelen Rechnen in verteilten Umgebungen untersucht. Als Zielumgebung betrachten wir netzwerkbasierte Parallelrechner, die als Multicomputersysteme moderne PCs und Workstations unter Benutzung schneller Netze (ATM) integrieren. Solche Systeme können heutzutage hohe Rechenleistungen erbringen, sie erfordern allerdings neue Ansätze zur Programmierung und zur Speicherverwaltung.
Wir untersuchen Replicated Shared Objects als Programmierparadigma im Umfeld von SONiC. Auf Basis unserer Implementation eines objektbasierenden distributed shared memory lassen sich task-parallele Programme in Workstation-Netzen einfach realisieren. Unser Ansatz gestattet es, Kommunikations- und Synchronisationsoperationen innerhalb der replizierten Objekte zu kapseln. Damit bieten Replicated Shared Objects dem Anwendungsprogrammierer eine einfach benutzbare Schnittstelle.
Schwache Konsistenzprotokolle (entry consistency, release consistency) bilden die Grundlage für die Realisierung unserer Replicated Shared Objects. Damit wird in unserem System der Kommunikationsaufwand für die objektbasierte Speicherverwaltung minimiert. Nach unserem Ansatz übernehmen Objekte die Rolle von Speicherseiten in einer herkömmlichen Speicherverwaltung. Das Problem von false sharing unabhängiger Seiten kann dadurch eliminiert werden. Experimente in unser prototypischen Implementation des SONiC-Systems auf Basis des Betriebssystems Mach und Ethernet als Kommunikationsmedium zeigten ähnliche Resultate auf einem aus vier Workstations bestehenden SONiC- System wie auf einem Vier-Prozessor shared memory-Multicomputer (Sequent Balance). Dem Programmierer paralleler Anwendungen stellt SONiC eine Klassenbibliothek für shared Datenstrukturen und Synchronisationskonstrukte wie locks und barriers bereit. Ein remote execution service gestattet die Erzeugung paralleler Aktivitäten auf verschiedenen Knoten eines netzwerk-basierenden Multicomputers. Eine mit NeXTSTEP implementierte grafische Benutzeroberfläche gestattet auf einfache Weise die Konfiguration des SONiC-Systems auf einer Reihe von Workstations.
3. Modellierung und Simulation
Die Modellierung und Simulation paralleler/verteilter Rechnersysteme konzentriert sich auf die Schwerpunkte Fehlertoleranz, Echtzeitfähigkeit, Effektivität von Konfigurierungen und Last-/Kapazitäts- Untersuchungen. Dabei werden folgende Forschungsschwerpunkte bearbeitet:
Unter dem Titel "SPIDER" wurde ein Konsistenzmodell, genannt address consistency model, für skalierbare distributed shared memory-Parallelrechner entwickelt und in einem Softwaresimulator implementiert.
(Bild 3.8: Klassenbibliothek von SONiC und CORE)
Konsistenzmodelle für die Speicherverwaltung spielen eine große Rolle in Bezug auf die Leistungsfähigkeit skalierbarer Shared-memory-Multiprozessorsysteme. Das Sequential-consistency-Modell erweitert den in Uniprozessorsystemen verwandten Ansatz atomarer Speicherzugriffe auf Multiprozessorsysteme. Dieses Modell ist klar und einfach benutzbar, es erweist sich jedoch als zu strikt für eine Reihe von Optimierungsansätzen. Es entstanden daher einige schwacher Konsistenzprotokolle, wie processor consistency, weak consistency und release consistency.
Das address consistency-Modell verringert die vom release consistency-Modell an die Reihenfolge von Zugriffen auf gemeinsamen Speicher gestellten Anforderungen weiter. Unter diesem Modell werden Synchronisationsoperationen stets mit einer Menge von virtuellen Speicheradressen assoziiert. Synchronisationsoperationen beziehen sich nur auf diese Adresse, nicht aber auf den gesamten Adreßraum. Anforderungen an die Ordnung von Speicherzugriffen gelten daher stets nur für eine spezielle Adresse.
Address consistency wurde im Hinblick auf eine einfache Realisierung in Hardware entwickelt. Gleichzeitig entstand ein Simulator, der zur Bewertung unseres Konsistenzmodells im Vergleich zu anderen Modellen bezüglich einer Reihe von parallelen Anwendungen herangezogen werden soll.
Dynamische Systeme sind Systeme deren beobachtbarer Status sich mit der Zeit ändert. Typischerweise produzieren solche Systeme Ausgaben, die in Form von Signalen gemessen werden können. Ein fundamentales Problem besteht darin, diese Signale in Form eines Modells zu charakterisieren, insbesondere dann, wenn nur wenig oder kein a priori Wissen über die Dynamik des Systems vorhanden ist. Zur Zeit werden vor allem netzwerkbasierte-Multicomputersysteme und Finanzmärkte als Vertreter dynamischer Systeme untersucht.
Schwerpunkte
Zur Zeit wird der Einsatz von RBF und HMM zur Modellierung und Prognose von Lastverteilungen und optimalen Frequenzverhältnissen für Scheduling Server unter CORE als Anwendung im Bereich verteilte Kontrolle (Distributed Control) und netzwerkbasierte Multi-Computersysteme überprüft. Aufbauend auf bereits vorliegenden ermutigenden Forschungsergebnissen im Bereich der quantitativen Finanzanalyse sollen diese neuen probabilistischen Modellierungsmethoden auch in der Finanzmarktmodelierung und Prognose verifiziert werden.
Simulation spezifischer Aspekte ausgewählter Systeme: Die verteilte und parallele Verarbeitung von Daten erzeugt komplexe Abhängigkeiten der Systemkomponenten untereinander. Eine zentrale Kontrolle des Gesamtverhaltens ist aus unterschiedlichsten Gründen meist nicht akzeptabel oder einfach inpraktikabel. Ein Lösungsansatz besteht darin die Kontrolle des Systems auf die Einzelkomponenten zu verteilen. Die Einzelkomponenten konkurrieren und/oder kooperieren untereinander um Services und Resourcen, so da (z. B. Systemstabilität und Fehlertoleranz gewährleistet wird. Ein solcher Ansatz wird in der Literatur auch als Autonomes System bezeichnet. In diesem Kontext spricht man dann von interagierenden Agenten. Bei der Konzeption eines solchen Systems stellen sich Fragen von fundamentaler Bedeutung bezüglich Verhalten und Design.
In dieser Phase des Projektes soll die Theorie autonomer Systeme zur Simulation spezifischer Interaktionsmuster eingesetzt werden. Insbesondere sollen hier konsensbasierte Interaktion von Agenten und deren Auswirkung auf Systemstabilität und Auktionsmechanismen zur Preisformation untersucht werden. Es wird erwartet, da (Ergebisse aus dieser Arbeit im Bereich des Designs von effizienten Trading Procedures, automatisierter Trade Execution Systeme und im Bereich der netzwerkbasierten- Multicomputersysteme zur optimalen Verteilung von Resourcen eingesetzt werden können.
4. Testumgebungen
(Bild 3.9: MAST - ein Prüfstand für Meß-, Analyse- und Simulationsexperimente)
Die Forschungsschwerpunkte des Lehrstuhls für Rechnerorganisation und Kommunikation erfordern eine eigenständige experimentelle Testumgebung im Rechnernetzwerkbereich. Die auf der ATM-Technologie basierende Kommunikationsplattform stellt die Installationsumgebung der Forschungsmodelle des High- Performance Responsive Computing. Die Verifikation der Forschungsansätze erfolgt durch Meß-, Analyse- und Simulationsexperimente im Testbed. Die erforderliche Variabilität des Hard- und Softwareprofils der Testumgebung wird über die installierten aktiven Komponenten des integrierten Netz- und Systemmanagement erzielt. Zusätzlich kann die Virtualität der Kommunikationsstruktur durch Parameter der Service-Semantik des ATM-Management gesteuert werden.
Beteiligte Mitarbeiter:
Projektaktivitäten 1995: Bestimmend war die Testkonzeption und Durchführung von Arbeiten zur Durchsatzbestimmung für CLNS-Backbone-Router im WIN. In einer LAN/WAN Testumgebung wurden Durchsatzmessungen an Routern der Hersteller 3Com, Cisco, TeleBit und Wellflett vorgenommen. Die ermittelten Resultate wurden im Rahmen des Projektes als DFN-Report vorgelegt. Die Informationsdienste im Rahmen des CLNS-Referenzzentrums wurden durch Installation eines projektgebundenen WWW- Servers verbessert. Der Abschluß des Projektes wird dem DFN-Verein im Jahresbericht für 1995 vorgelegt. Perspektivisch werden mit dem Auftraggeber fortführende Projektanträge zu IPv6 Security diskutiert, die eine zukünftige Projekttätigkeit in Rahmen des DFN vorbereiten sollen.
Diplomarbeiten
Beteiligte Mitarbeiter:
Innerhalb des vorgeschlagenen Projektes soll jeweils eine Softwarebibliothek (Standardmikroprozessor, Mikrocontroller, Signal- und Grafikprozessor) für die Anforderungen einer extrem schnellen, industriellen Bildverarbeitung geschaffen und an typischen Applikationen getestet werden.
Ansprechpartner: Prof. Dr.-Ing. Beate Meffert
Beteiligte Mitarbeiter:
An die Atemfunktionsdiagnostik im Neugeborenenalter werden seitens der Klinik hohe Anforderungen gestellt, die mit der verfügbaren Meßtechnik aber nicht erfüllbar sind. Neben den noch vorhandenen meßtechnischen Grenzen (Empfindlichkeit, Rückwirkungen auf den Gasaustausch, Einsatz unter Beatmung) versagen bisher übliche Untersuchungsmethoden häufig, da sie auf sehr einschränkenden Voraussetzungen aufbauen.
Mit der Impulsoszillometrie soll eine neue, nichtinvasive Methode zur Untersuchung der Atemmechanik entwickelt werden, die bei Kombination mit der Flow-Through-Technik weitgehend rückwirkungsfrei ist. Die Impulsoszillometrie kann bei pulmonalen Inhomogenitäten und Nichtlinearitäten eingesetzt werden. Infolge ihrer hohen zeitlichen Auflösung lassen sich auch Veränderungen der Atemmechanik während eines Atemzuges erfassen. Die bisher nur bei Erwachsenen verwendete Impulsoszillometrie läßt sich nicht unmittelbar auf Neugeborene übertragen. Die Besonderheiten der Atemfunktionsdiagnostik in dieser Altersgruppe erfordern neue systemtheoretische und meßtechnische Lösungen.
Beteiligte Mitarbeiter:
Zusammenarbeit:
Deutsches Forschungsinstitut für Luft- und Raumfahrt (DLR), Köln;
Das Temperatur- und Gravitationsmeßgerät TEGRA ist Bestandteil einer neuen Kristallzüchtungsanlage CSK 4 der Firma BBT und wird im Rahmen des Raumflugprojektes EUROMIR 95 eingesetzt. Besonderheiten sind die hochgenaue Temperaturmessung bis 1400 C, die Programmierbarkeit und eine flexible Konfigurierbarkeit. Durch spezielle Algorithmen können ortsbezogene Temperaturmessungen für eine differentialkalorimetrische Auswertung des Experimentverlaufes herangezogen werden. Die wesentliche wissenschaftliche Leistung bei der Entwicklung von TEGRA besteht in der Herbeiführung eines Synergieeffektes, der durch das Zusammenspiel einer speziellen, überwiegend analog arbeitenden Hardware mit Softwarekomponenten zur Signalverarbeitung möglich wird. Aus der gezielten Eliminierung differentieller Linearitässfehler werden auch unter elektromagnetisch stark gestörten Umgebungsbedingungen extrem hohe Temperaturauflösungen (bis 2,5 mK) möglich.
Das Gerät befindet sich seit September 1995 im Kristall-Labor der russischen Raumstation MIR. Erste Experimente wurden bereits erfolgreich durchgeführt. Weitere Experimente zur Untersuchung unterkühlter Schmelzen und zu Materialverteilungen in Mischkristallen sind geplant.
Beteiligte Mitarbeiter:
Zusammenarbeit:
Beteiligte Mitarbeiter:
In der dermatologischen Diagnostik findet die Messung der akralen Wiedererwärmung und -durchblutung zunehmend Anwendung. Hierbei werden nach einer kontrollierten Abkühlung des Zeigefingers Temperatur und Durchblutung während seiner Wiedererwärmung registriert. Aus dem zeitlichen Verlauf dieser Daten können Erkenntnisse beispielsweise über Durchblutungsstörungen oder die Hautdicke gewonnen werden.
Das neu entwickelte Meßgerät Duosensor ermöglicht die gleichzeitige Erfassung von Oberflächentemperatur und Durchblutungszustand. Zur Bestimmung der Hauttemperatur wurde ein Infrarot-Thermoelement eingesetzt. Für die Durchblutungsmessung wurde ein Sensor verwendet, der auf dem Prinzip der Photoplethysmographie beruht. Zur Verlaufskontrolle einer Behandlung ist es notwendig, die Ergebnisse einzelner Messungen zu vergleichen, was hohe Anforderungen an die Reproduzierbarkeit der Messungen stellt. In diesem Zusammenhang ist es wichtig, daß die Steuerung der etwa 4 bis 5 Minuten dauernden Untersuchung vom Meßgerät selbst vorgenommen wird. Nach der Messung erfolgt die Berechnung zweier wichtiger Kennwerte für die akrale Wiedererwärmung und -durchblutung. Der zeitliche Verlauf beider Messungen wird auf einem Drucker ausgegeben.
Beteiligte Mitarbeiter:
Für unterschiedliche Anwendungsfälle (z. B. mobile Umweltregistrierungen, Speditions- und Frachtgutüberwachung, Warenkennzeichnung und -identifikation, Erläuterung von Ausstellungsstücken, Statusfeststellungen und -abfragen) besteht die Notwendigkeit, durch miniaturisierte Systeme neben aktuellen Meßwerten Daten über gegenstandsspezifische Eigenschaften am Objekt zu registrieren und drahtlos mit unterschiedlichen Distanzen auszulesen und zu übermitteln. Derartige Lösungen gestatten es, bisher übliches manuelles Ablesen zu automatisieren. Bei der Entwicklung muß die Anwendung neuester Erkenntnisse des Schaltkreisentwurfs, der HF- und Funktechnik sowie energiesparender Schaltungen eine wesentliche Rolle spielen, um die zu entwickelnden Systeme in Miniaturausführung gestalten und auch für Langzeitaufgaben verwenden zu können. Ziel des Projektes ist es, für eine Vielfalt möglicher Anwendungen ein modulares elektronisches System zu entwickeln, welches Informationen zum gewünschten Zeitpunkt von definierten Stellen abruft, drahtlos oder/und über verschiedene Dienste und Netze (insbesondere ISDN) zum Zielpunkt überträgt und zentral eine Auswertung gestattet.
Beteiligte Mitarbeiter:
Die umfassende Zielstellung des Projektes läßt sich mit dem Entwurf elektronischer Komponenten umschreiben, die für eine Untersuchung solcher physikalischen Vorgänge geeignet sind, die in der Wechselwirkung von materiellen Strukturen mit einzelnen Photonen auftreten (beispielsweise in materialwissenschaftlichen oder quanten- mechanischen Arbeitsgebieten). Derartige Vorgänge laufen in aller Regel im Zeitbereich weniger Pikosekunden ab, wobei innerhalb kürzester Zeit eine enorme Menge an auszuwertenden Daten anfallen kann. Die elektronischen Komponenten müssen dieser Forderung Rechnung tragen, wobei neben der großen Datenverarbeitungs- geschwindigkeit auch extrem zeitstabile Sensor- und Aktorfunktionen eine Rolle spielen. Konkrete Ergebnisse der Kooperation können sowohl in der Konzeption sehr schneller Lasersysteme als auch in der Erfassung von Daten nach dem Prinzip der Einzelphotonenzählung, der zeitlichen Quantisierung und der Datenkompression bestehen. Ein erstes Beispiel befaßt sich mit dem Entwurf eines Schaltkreises zur zeitlichen Digitalisierung im Pikosekundenbereich.
Beteiligte Mitarbeiter:
Beteiligte Mitarbeiter:
Schwerpunkte jeder Klassifikationsaufgabe bestehen in der Definition von geeigneten Merkmalen zur numerischen Abbildung der Bildinformation und der Auswahl eines leistungsfähigen Klassifikationsalgorithmus. Da allgemeingültige Aussagen zur Realisierung der Merkmalsauswahl und zum Klassifikatorentwurf nur begrenzt ableitbar sind, werden oft empirische Verfahren angewendet.
Ziel der Untersuchungen ist es, ein nahezu universelles Werkzeug zu schaffen, das für eine beliebige Klassifikationsaufgabe aus einer umfangreichen Menge "potentieller" Merkmale und Klassifikatoren die jeweils geeignetsten selektiert, die dann für die eigentliche Implementation der Erkennungssoftware verfügbar sind. Das stark problemorientierte Software-Design soll hohe Erkennungsraten bei effektiver Nutzung der jeweils verfügbaren Rechenkapazität gewährleisten.
Teilaufgaben der Untersuchungen:
Beteiligte Mitarbeiter: Dipl.-Ing. Olaf Jaeckel
Zusammenarbeit: Fraunhofer-Institut für Zuverlässigkeit und Mikrointegration, Berlin
Probleme der statistischen Qualitätssicherung erfordern häufig ein mathematisches Modell der Abhängigkeit relevanter Zielgrößen von einer Vielzahl quantitativer Prozeßparameter. Eine deduktive Modellbildung auf der Basis einer theoretischen Systemanalyse ist häufig nicht durchführbar. Methoden der unvollständigen Induktion zur Gewinnung einer systemadquaten Modellstruktur gelten im Rahmen der experimentellen Prozeßanalyse als m&oml;gliche Alternative. Die interessierenden GMDH-Algorithmen (Group Method of Data Handling) erstellen iterativ Polynom-Modelle von Prozessen auf alleiniger Grundlage beobachteter Ein- und Ausgangsdaten sowie aufgabenabhängiger Selektionskriterien.
Schwerpunkte der Projektuntersuchungen sind:
Beteiligte Mitarbeiter:
Untersuchungsschwerpunkte sind:
Beteiligte Mitarbeiter: Prof. Dr.-Ing. habil. Wolfgang Glaser (Institut für Elektrotechnik)
Zusammenarbeit: Forschungs- und Technologiezentrum der Deutschen Telekom
Nichtlineare Effekte im Übertragungsmedium Lichtwellenleiter (LWL) beeinflussen die Signalübertragung in optischen Vielkanalsystemen zur Breitbandkommunikation, beson- ders bei hoher optischer Leistung und hoher Übertragungsrate. Nichtlineare Effekte im LWL werden auch gezielt zur optischen Frequenzumsetzung genutzt, um Vermitt- lungsfunktionen für optische Signale zu realisieren.
Schwerpunkt der Untersuchungen war die Bestimmung des Polarisationseinflusses auf die Vierwellenmischung im nichtlinearen Einmoden-LWL auch bei Kopplung der Polarisationsmoden. Nach einem allgemeinen Modell der Übertragungsstrecke wurde ein Simulationsprogramm erarbeitet, das die auftretenden Effekte in Abhängigkeit von einer Vielzahl von technischen Parametern zu untersuchen gestattet. Parallel zu diesen Rechnungen wurden Experimente im Forschungsinstitut der Telekom durchgeführt.
Beteiligte Mitarbeiter:
Betriebsdatenerfassungssysteme (BDE-Systeme) stellen im Zusammenwirken mit der Produktionsplanung und Steuerung (PPS) einen wesentlichen Bestandteil von Konzepten des Computer Integrated Manufacturing dar, kommen aber auch in vielen anderen Bereichen zum Einsatz. Daraus ergeben sich hohe Anforderungen für diese Systeme hinsichtlich der Anpassungsfähigkeit an vorgegebene Systemstrukturen. Konsequent modularer Aufbau, Programmierbarkeit bzw Parametrierbarkeit der Datenerfassungs- und übertragungstechnik sowie eine leistungsfähige Datenauswertesoftware sind unerläßlich. Ziel des Projektes ist die Schaffung einer modularen und nutzerfreundlichen Entwicklungsumgebung (Programmbibliothek), die eine schnelle Anpassung sowohl der technischen Einrichtungen (Terminals, Controller, Anzeigeelemente usw.) als auch der Datenauswertesoftware für konkrete Einsatzfälle ermöglicht.
Beteiligte Mitarbeiter:
Ingo Drogi
Die Vielzahl der auf dem Markt verfügbaren Simulatoren erfordert vom Anwender ausführliche Studien, bevor er sich für die Nutzung eines bestimmten Simulators zur Lösung seiner Problemstellung entscheiden kann. Üblich ist die Aufstellung einer problemspezifischen Chekliste, auf deren Basis eine Bewertung und Auswahl anhand qualitativer Merkmale erfolgt. Die Zielstellung des Projektes besteht darin, für die Klasse der diskreten Simulatoren eine Methodik zu entwickeln, die den Vergleich der mit ausgewählten Referenzmodellen erzielten Simulationsergebnisse erlaubt und damit auch quantitative Aussagen ermöglicht.
Beteiligte Mitarbeiter:
Das spinovestibulookuläre System ist für die Orientierung im Raum, zur Empfindung der Lage und der Bewegungen ausgelegt. Experimentelle Provokationen dieses Systems führen zu einer zwanghaften Augenbewegung (dem Nystagmus) und damit zu einer Scheinbewegung der Umgebung. Nystagmusformen treten bei verschiedenen Krankheiten auf und belasten die Patienten durch Schwindelerscheinungen und Übelkeitsgefühl sehr (insbesondere bei Ohrenerkrankungen). Es soll nun mittels einer zu entwickelnden Versuchsanlage geklärt werden, ob die Mitführung des Bildes der Umgebung entsprechend der Augenbewegung zu einer Aufhebung der Scheinbewegung der Umgebung und damit zu einer Entlastung der Patienten führt. In der Versuchsanlage wird die Augenbewegung mit Hilfe der Elektronystagmographie analysiert und das Ausgangssignal zur Steuerung eines Bildmusters vor dem Auge ausgenutzt.