Inhalt

Links

Teilprojekt L1: Paralleles Data-Mining

Folienpräsentation bei der Begehung durch die DFG 1999
Folienpräsentation bei der Begehung durch die DFG 2002

Ausgangssituation

Allgemeines

OLTP geht von hohen Lasten einfacher, sog.  Debit-/Credit-Transaktionen aus, die mit ihrer kurzen Dauer, einfachen Verarbeitungsvorgängen und dem vergleichweise geringen Datenvolumen dem ACID-Paradigma unterliegen. OLAP stellt demgegenüber nicht mehr die Transaktion in den Mittelpunkt der Betrachtung, sondern das Durchforsten umfangreicher Datenbestände, die sich über lange Zeit oder im Rahmen datenintensiver Erfassungen und Experimente angesammelt haben und als wertvolle "Goldmine" von Langzeitwissen angesehen werden, die es nach vielfältigen, oftmals zunächst nur vage umrissenen Kriterien zu Zwecken der Entscheidungsunterstützung auszuschlachten gilt.  Moderne Schlagworte wie "Data-Warehousing", "Data-Mining" oder "Knowledge Discovery in Databases" begleiten diese Entwicklung.

Um die Leistungsengpässe beim OLTP zu beheben, wurden bereits frühzeitig verschiedene Maßnahmen der Parallelisierung von Datenverwaltung und Datenzugriff ergriffen. Dabei entstanden unterschiedlichste Architekturen, die von hohen Zugriffsbreiten auf den Hintergrundspeicher mittels sog.  Disk Arrays bis hin zur Intertransaktionsparallelität (gleichzeitige Bearbeitung ganzer Transaktionen auf verschiedenen Prozessoren) und Intratransaktionsparallelität (parallele Bearbeitung der Operatoren innerhalb einer Transaktion) durch Vervielfachung von Prozessoren sowie der Kombination all dieser Techniken reichen.
Charakteristisch für all diese Ansätze ist eine hohe Grobkörnigkeit der Parallelverarbeitung: Auf jedem Knoten wird (zumindest zeitweilig) ein umfangreicher Datenbestand vorgehalten, der von einem abgeschlossenen, meist umfangreichen Programm lokal abgearbeitet wird, während sich der Nachrichten- und Datenaustausch zwischen den Knoten auf vergleichsweise wenige Zeitpunkte beschränkt. Die Referenzarchitektur für diese Vorgehensweise ist die verteilte Datenbank.

OLAP geht von ganz anderen Voraussetzungen aus.  OLAP rechnet nur mit niedrigen Raten gleichzeitig zu bearbeitender Aufträge an das Datenbanksystem, erwartet aber umgekehrt von diesen Aufträgen sehr hohe Anforderungen an das zu  untersuchende Datenvolumen bei hoher Rechenintensität der Analyseprozesse. Gleichzeitig ist aufgrund des experimentellen Charakters des Wissensgewinnungsprozesses eine möglichst interaktive Arbeitsweise wünschenswert.

Darüberhinaus gehorchen die Aufträge nicht wie bei OLTP einer beschränkten Zahl vordefinierter Anfragemuster, sondern variieren mit dem Fortschritt der Entscheidungsprozesse der Anwender und sind damit schlecht vorhersagbar. Es stellt sich daher die Frage, ob unter diesen Umständen nicht eine grobkörnige Parallelität, die von vorgegebenen Anfragemustern ausgeht, ihren Zweck einbüßt und stattdessen feinkörnigere Parallelität auch für den Datenbankbereich an Bedeutung gewinnt.

Mit der ParaStation2 wird die Lücke zwischen Prozessor- und Datenaustauschgeschwindigkeit um Größenordnungen verringert, so daß die klassischen Optimierungstechniken zur Anfragebearbeitung, Zugriffspfaden und Speicherorganisation aus den verteilten Datenbanken ihren Wert einzubüßen drohen.  Da deren Bedeutung aber, wie erwähnt, für OLAP sowieso in Frage gestellt werden muß, liegt mit ParaStation2 eine ideale Plattform vor, um das Parallelisierungspotential von OLAP auszuloten.
 

Spezielle Ausgangssituation des Teilprojekts

Die Bedeutung der Vorverarbeitung ergibt sich aus der Berechnungskomplexität der eigentlichen Data-Mining-Verfahren, die auf statistischen Analysen oder auf Techniken des maschinellen Lernens beruhen und nur mit recht kleinen Datenmengen umzugehen vermögen. Die Vorverarbeitung, welche die Reduktion des ungeheuren Datenvolumens, wie es in den Quelldatenbasen vorliegt, auf handhabbare Mengen sowie die Säuberung und Verdichtung der Daten übernimmt, macht daher einen wesentlichen Teil des KDD-Prozesses aus. Ausgehend von den Vorverarbeitungsoperatoren bis hin zu den eigentlichen Lernverfahren sind in einem iterativen Prozeß viele Parametereinstellungen und Verfahren geeignet zu kombinieren, um letztlich interessante Information aus den Daten zu extrahieren. Dieser Vorgang ist hochgradig interaktiv, da laufend Entscheidungen eines menschlichen Analytikers über die Fortführung der Verarbeitung anfallen. Um trotz großer Datenvolumina Antwortzeiten im Bereich menschlichen Entscheidungsverhaltens zu erreichen, sind gegenüber dem derzeitigen Stand massive Leistungssteigerungen erforderlich.

Als Ausgangspunkt des Teilprojekts ist ein Modell notwendig, in dem die Vorverarbeitung einschließlich ihres iterativen, auf früheren Ergebnissen aufbauenden Vorgehens beschrieben werden kann. Dazu stützt sich das Vorhaben auf ein objektorientiertes Datenmodell, das am Institut entwickelte Informationsmodell (IM). Sein besonderes Kennzeichen ist, daß es Ausgangs- und Zwischenergebnisobjektmengen als Knoten eines Graphen erfaßt, die auf mannigfache Weise über Beziehungen verbunden sind, wobei die Art der Beziehung dem angewandten (objektalgebraischen) Operator entspricht. Da der Graph schrittweise mit jeder Anfrage erweitert wird, spiegelt er zugleich die Prozeßhistorie wider. Als solcher hat er Datenflußcharakter: Man kann sich vorstellen, daß die Objektmengen entlang der Kanten weiterlaufen und dabei in neue Objektmengen transformiert werden.

Das IM kann insbesondere auch dazu verwendet werden, eine neuerliche Anfrage des Analytikers darauf zu prüfen, inwieweit sie mit Teilen des Graphen zur Deckung gebracht werden kann, um früher erzielte Ergebnisse wiederverwenden zu können. Diese Art der Anfrageoptimierung unterscheidet sich drastisch von der klassischen Anfrageoptimierung. Natürlich kann man der Transformation der Anfrage noch eine klassische Anfrageoptimierung nachschalten, doch wird deren Nutzen anteilmäßig nur noch beschränkt ins Gewicht fallen. In einer zweiten, kürzlich abgeschlossenen Dissertation wurden beide Stoßrichtungen verfolgt: Zum einen wurden Techniken entwickelt, mit denen beim Abgleich von Anfrage und IM bestimmt wird, auf welchen materialisierten Mengen die Anfrage aufbauen kann - eine Frage der Anfragereduktion und -erweiterung und im allgemeinen selbst ein Optimierungsproblem - und welche Zwischenergebnisse überhaupt zu materialisieren sind. Zum zweiten geht die Arbeit davon aus, daß die Daten in einer relationalen Datenbank gehalten werden, so daß die im IM konstruierten Anfragen in SQL-Anfragen zu übersetzen sind. Die klassische Anfrageoptimierung bleibt dann dem relationalen Datenbanksystem überlassen (sog. Query Shipping). Die Arbeit beschränkt sich auf den zentralen Fall. Die gemessenen Performanzsteigerungen liegen über alle Maßnahmen vereint in der Größenordnung von 10, sind also durchaus beeindruckend, aber für praktische Erfordernisse noch unzureichend.

Bisherige Lösungen bieten also noch nicht die notwendige Performanz für die komplexen Analyseverfahren und großen Datenmengen eines interaktiven KDD-Prozesses. Leistungssteigerung durch Parallelität ist somit ein naheliegender Gedanke. Anfrageparallelisierung im Datenbankbereich hat ja auch durchaus eine lange Geschichte. Der klassische Ansatz der Parallelisierung sieht den Engpaß vorrangig beim Hintergrundspeicherzugriff und strebt daher als erstes eine Erhöhung der E/A-Bandbreite durch Verteilung der Daten (Datenpartitionierung) auf mehrere Knoten an. Liegt erst einmal eine solche Verteilung vor, so wird die hohe E/A-Bandbreite mit der erhöhten Verarbeitungsleistung mehrerer Knoten kombiniert (datenparallele Verarbeitung). Da von immer noch vergleichsweise schmalbandigen Verbindungswegen zwischen den Knoten ausgegangen wird, muß das Übertragungsvolumen zwischen den Knoten durch eine geschickte Datenpartitionierung gering gehalten werden, die Parallelisierung ist daher sehr grobkörnig. Daher versagen Parallelisierungen sehr schnell, wenn die Datenverteilung nicht den Bedürfnissen der Anfrage entspricht.
 

Hypothese

Die Weitergabe in Paketen hängt ebenfalls mit der Schmalbandigkeit der Verbindungswege zusammen und steht sowohl der Erzielung eines höheren Grades an Pipelining durch feingranulare Realisierungen von Vorverarbeitungsoperatoren als auch kommunikationsintensiven parallelen Lernverfahren im Wege. Hier bieten vor allem die kurzen Latenzzeiten der ParaStation neue Möglichkeiten.

Wir haben daher unserem Teilprojekt die Hypothese zugrunde gelegt, daß die Begründung der Ausführung von Anfragen im Rahmen des KDD-Prozesses auf dem Datenflußprinzip und ihre Parallelisierung nach dem Pipelineprinzip als dominierender Strategie besonders hohe Performanzgewinne verspricht. Dies hat mehrere Konsequenzen:
 

• Es ist eine geeignete Suite von Operatoren zu entwickeln, die möglichst durchgängiges Pipelining ermöglichen und zugleich die Möglichkeit der Feinkörnigkeit besonders nutzen.
• Eine Kombination mit der Materialisierungsstrategie nach Schloesser muß möglich sein, d.h., die Pipeline muß an geeigneten Punkten unterbrochen werden können.
• Eine Vorgehensweise, die Pipelining und Materialisierung in einer verteilten Umgebung optimal verbindet, ist zu entwickeln.
• Die Parallelisierung muß robust sein gegen statische Ungleichverteilungen in den Daten.
• Der nahtlose Übergang von einem feinkörnigen Pipelining zu den feingranularen Lernverfahren ist sicherzustellen.

Wissenschaftliches Ziel unserer Arbeit ist damit die Einbettung von Vorverarbeitungs- und speziell entwickelten Data-Mining-Operatoren in gemeinsam optimierte Anfragegraphen und die Erzielung eines Höchstmaßes an Pipelining. Dabei setzen wir auf die dem Projekt zugrundeliegende ParaStation-Plattform. Die hohe Bandbreite und die kurzen Latenzzeiten verbunden mit der vollständigen Ausstattung eines jeden Knotens bilden ideale Voraussetzungen, um das volle Spektrum an Parallelisierungsmöglichkeiten auszuloten. Am Ende dieser Arbeit steht eine preiswerte und skalierbare Plattform für paralleles Data-Mining in Workstation-Clustern, die durch eine an die Bedürfnisse des KDD-Prozesses angepaßte Parallelisierung von parallelen Lernverfahren und paralleler Datenbanktechnik eine optimierte Unterstützung des kompletten
KDD-Prozesses bietet.
 

Stand des Teilprojekts

• Auswahl und Implementierung einer verteilten Datenbank auf der ParaStation-Plattform
• Abschätzung des Verhaltens bei Pipelining und feingranularer Parallelität
• Analyse von Data-Mining-Verfahren und -Methoden auf ihr Parallelisierungspotential

Auswahl und Implementierung einer verteilten Datenbank auf der ParaStation-Plattform.

Wie beabsichtigt, haben wir uns zunächst auf den Bereich der Vorverarbeitung konzentriert. Als erste Aufgabe stand die Auswahl eines verteilten/parallelen Datenbanksystems als erweiterbare technische Plattform und Ausgangsbasis für die weiteren Arbeiten im Teilprojekt an. Die schnelle Verfügbarkeit einer initialen Implementierung sollte uns einerseits eine Basis für die Abschätzung der Erfüllbarkeit unserer Hypothese bieten, andererseits aber auch den Projektpartnern, die die Basistechnik zur Verfügung stellen, frühzeitige Rückkopplung über die Bedürfnisse und Anforderungen von Datenbankanwendungen geben. Von diesem Prototypen versprachen wir uns erste Antworten auf die folgenden Fragen:
 

• Wie verhält sich Pipelining im Vergleich zu klassischen Parallelisierungstechniken?
• Welches Potential bietet die ParaStation-Plattform für feingranulare Parallelität?
• Wie gut eignet sich die verwendete Plattform für große Datenbankanwendungen?

Hinsichtlich der Auswahl eines verteilten/parallelen Datenbanksystems wurden die folgenden Alternativen untersucht und bewertet:
 

• Verwendung eines kommerziellen DBMS, eigene Erweiterungen erst oberhalb der SQL-Schnittstelle: Diese Variante bietet den Vorteil, sofort zu kommerziell akzeptierten Lösungen zu führen. Jedoch fand sichkein System, das auf der vorhandenen Hardware direkt aufsetzen kann. Für die Portierung wäre man also auf die Zusammenarbeit mit einem Hersteller angewiesen gewesen. Keine Einflußnahme wäre auch bei der Wahl der Parallelisierungsstrategie möglich: Die angebotene SQL-Schnittstelle beschneidet sowohl die Möglichkeiten zum Übergang von mengenorientiertem zu navigierendem Zugriff als auch den Spielraum zur Integration neuer Data-Mining-spezifischer Operatoren.
• Frei verfügbare DB mit erweiterbarem Optimierer: Die Wahl eines im Quellcode verfügbaren DBMS mit erweiterbarem Optimierer hätte die gewünschten Einflußmöglichkeiten eröffnet. Hierbei handelt es sich aber im allgemeinen um sehr komplexe Systeme, die für Data-Mining-Zwecke viel unnötige Funktionalität mitbringen (z.B. Locking, Logging, Transaktionsmechanismen), was eine Anpassung nicht einfach macht und daher das Erreichen der eigentlichen Ziele des Projekts unnötig verzögert hätte.
• Eigenentwicklung: Der dritte und schließlich von uns beschrittene Weg ist eine Eigenentwicklung. Sie bietet alle gewünschten Einflußmöglichkeiten (Parallelisierung, Operatoren) und verzichtet auf überflüssige Funktionalität. Diesen Vorteilen steht allerdings ein etwas höherer Aufwand bei der Konzeption und Umsetzung gegenüber. Allerdings konnten wir auf Vorarbeiten aus der Dissertation Herzog zurückgreifen.

Es wurde also eine erweiterbare parallele Algebramaschine für Workstation-Cluster entworfen und implementiert. Besonderes Augenmerk wurde dabei auf die Nutzbarkeit verschiedener Parallelisierungsstrategien und Kommunikationsparameter gelegt. Um in hohem Maße Pipelining nutzen zu können, wurde der Pipelined-Hash-Join aus der am Institut entwickelten Algebramaschine CEE eingesetzt.

Besonders verlockend für die Realisierung der Algebramaschine erschien das im Teilprojekt T2 entwickelte JavaParty. Diese Plattform bietet eine einfache Programmierung verteilter Umgebungen kombiniert mit den Vorteilen von Java als sicherer und komfortabler Programmiersprache. Sie hat auch tatsächlich den Aufwand für Implementierung und Umsetzung in Grenzen gehalten. Darüberhinaus wird aufgrund der Portabilität von Java auch eine Unterstützung heterogener Cluster (also Cluster mit unterschiedlichen Architekturen und Betriebssystemen) möglich. Als zusätzlicher Gegenstand der Untersuchung kam nach der Entscheidung für JavaParty allerdings auch die Frage der Performanz und Eignung dieser Plattform für datenintensive Anwendungen hinzu, womit gleichzeitig auch die Arbeiten an einem für Cluster-Computing optimierten JavaParty im Teilprojekt T2 validiert werden konnten.

Im Rahmen der Umsetzung unserer Algebramaschine stießen wir zunächst auf umfangreiche Probleme mit der Synchronisation (die inzwischen in Zusammenarbeit mit dem Teilprojekt T1 behoben werden konnten) und dem Scheduling von Multi-Threaded-Anwendungen auf der ParaStation (siehe Erläuterungen zu Projekt T1). Unsere Arbeit konnte damit dazu beitragen, die Stabilität der Plattform weiter zu erhöhen und gleichzeitig ein allgemeines und für Cluster-Computing in der Zukunft (mit der wachsenden Verbreitung von SMP-Systemen als Bausteinen von Clustern) immer wichtigeres Problemfeld frühzeitig zu erkennen und anzugehen.
 

Abschätzung des Verhaltens bei Pipelining und feingranularer Parallelität.

Die Algebramaschine konnte nun benutzt werden, um erste Antworten auf die bisher gestellten Fragen zu erhalten. Als Grundlage wurde der 1GB-TPC-D Datenbestand genutzt. Nähere Erläuterungen finden sich HPCN99 und DMDW99.

Um die Nutzbarkeit von Pipelining zu untersuchen, wurden auf der ParaStation-Plattform dieselben Anfragen einmal mit einer datenparallelen und einmal mit einer Pipelining-Strategie ausgeführt. Um nur den Einfluß der Übertragungskosten zu ermitteln, wurden in beiden Fällen keine Zwischenergebnisse angelegt. Anfragen, die bei datenparallelem Vorgehen nicht optimal skalierten, konnten bereits auf 8 Knoten mit Pipelining um bis zu 25% beschleunigt werden, obwohl die doppelte Menge an Daten über das Netz übertragen wurde. Vergleichsmessungen auf normalem Fast Ethernet zeigten, daß eine solche Verbesserung dort nicht nicht möglich wäre, da die Bandbreite des Netzes zum limitierenden Faktor wird. Diese Messungen zeigen, daß die Nutzung von Pipelining in verteilten Umgebungen durch die ParaStation überhaupt erst möglich wird und damit auch unter Bedingungen, die bei datenparallelem Vorgehen zu Problemen führen, noch eine gut skalierende Parallelisierung erreicht werden kann.

Des weiteren wurde untersucht, wie teuer feingranulare Parallelität auf dieser Plattform ist. Dazu haben wir eine Anfrage mit unterschiedlichen Paketgrößen für den Datentransport zwischen den Knoten ausgeführt. Dabei wurden die Werte für Standard-JavaParty sowie verschiedene, im Teilprojekt T2 durchgeführten Optimierungen, die schnelle Serialisierung (fastSt) und das optimierte RMI (KaRMI) einander gegenübergestellt. Abbildung 2 zeigt, daß die Verwendung der ParaStation-Plattform zusammen mit dem optimierten JavaParty Verbesserungen um den Faktor 2 bei kleinen Paketgrößen bringt.

 Die Ergebnisse zeigen, daß die Nutzung extrem kleiner Paketgrößen zwar durch die Nutzung der ParaStation-Plattform sowie die Anstrengungen im Projekt T2 zu schneller Serialisierung und optimiertem RMI (KaRMI) deutlich günstiger wurde. Doch zeigen die Ergebnisse auch, daß die eingangs erwähnte Möglichkeit der Bündelung von Daten in Paketen (soweit die Algorithmen dies erlauben) nach wie vor empfehlenswert erscheint. Hier versprechen wir uns allerdings auch von laufenden Optimierungen der ParaStation- und JavaParty-Plattform weitere Verbesserungen.

Um eine grobe Schätzung der Leistungsfähigkeit der JavaParty-Plattform im Vergleich zu anderen Lösungen zu ermöglichen, wurden ferner einige Anfragen aus der TPC-D-Suite auf dem 1-GB-Datenbestand (SF1) mit unserer Algebramaschine ausgeführt. Der Vergleich der Ergebnisse mit anderen veröffentlichten Ergebnissen zeigte, daß hinsichtlich der Performanz dieser Plattform noch Verbesserungen um etwa einen Faktor von 8 gegenüber einer in C realisierten Lösung notwendig sind. Allerdings läßt die Entwicklung im vergangenen Jahr, die sowohl im Bereich der virtuellen Maschinen als auch im Bereich optimiertes JavaParty jeweils eine Verbesserung um mehr als den Faktor 2 brachte, auf weitere Verbesserungen in der Zukunft schließen.
 

Analyse von Data-Mining-Verfahren und -Methoden auf ihr Parallelisierungspotential.

Die Analyse zeigte, daß der Bedarf an Feingranularität bei den verschiedenen Verfahren unterschiedlich ausgeprägt ist. Während beispielsweise bei Association Rules die isolierte Untersuchung großer Datenmengen auf einem Knoten möglich ist, ist es bei neuronalen Netzen notwendig, das globale Modell nach jedem Schritt zu aktualisieren und daher extrem häufig kleine Datenmengen zu verschicken. Generell ist zu beobachten,daß bisher auf gängigen Plattformen hauptsächlich grobkörnig datenparallel vorgegangen wurde (und das mit unterschiedlichem Erfolg), obwohl die meisten Verfahren auch andere Möglichkeiten zulassen. Bei den alternativen Ansätzen handelt es sich um reine Einzelimplementierungen ohne Datenbankanbindung, die jeweils auf eine ganz bestimmte parallele Spezialmaschine zugeschnitten sind. In Neri95 bzw. Anglano97 ist ein genetischer Algorithmus auf einer CM-5 und in leicht abgewandelter Form auf einem Workstation-Cluster mit Standard-Ethernet realisiert. Auf der Spezialmaschine ergab sich ein linearer Speedup, auf dem Cluster eine Effizienz von lediglich 30-60%. Hier zeigt sich bereits das Potential, das von optimierter Kommunikation ausgeht.

Zur Anbindung von Lernverfahren an Datenbanksysteme findet sich in Sarawagi98 eine Gegenüberstellung von Realisierungen für Association Rules mit aktuell verfügbaren Standardtechniken. Fazit ist, daß mit Standard-SQL realisierte Verfahren reinen hauptspeicherbasierten Verfahren immer noch unterlegen sind. Daher existieren einige neue Ansätze, die eigene Erweiterungen von SQL nutzen, wie z.B. Count-by-group [Freitas96]. Bei diesen Ansätzen handelt es sich aber allesamt um Möglichkeiten, sequentielle Lernverfahren an parallele DBMS anzubinden. Verfahren zur Anbindung paralleler Lernverfahren an parallele Datenbanksysteme finden sich nicht.
 

Fazit

Mit den durchgeführten Messungen zum Pipelining konnte gezeigt werden, daß bereits bei einer vergleichweise geringen Knotenzahl herkömmliche Parallelisierungsansätze nicht mehr optimal skalieren und es lohnt, auch kommunikationsintensivere Strategien in Betracht zu ziehen. Die Messungen der Granularität (Paketgröße) zeigten, daß die Nutzbarkeit feingranularer Parallelität durch die ParaStation und die Optimierungen von JavaParty deutlich verbessert wird, wobei hier noch weitere Verbesserungen notwendig sind. Die Messungen zeigen allerdings auch, daß man für den Datenaustausch nicht zu kleine Paketgrößen anstreben darf. Mit anderen Worten: Die Körnigkeit der Parallelverarbeitung kann nicht beliebig fein werden. Dies verstärkt über den Gesichtspunkt der Vermeidung langsamer peripherer Speicherzugriffe hinaus die Argumentation für Pipelining, wenn eine breit nutzbare Datenpartitionierung nicht angegeben werden kann. Auch bei der Anbindung paralleler Lernverfahren ergibt sich noch wesentlicher Handlungsbedarf sowohl bei der Auslotung des Spektrums alternativer Parallelisierungen als auch bei der Integration mit Datenbankfunktionalität.

Ziele

Der zukünftige Schwerpunkt verbleibt bei der Parallelisierung der Vorverarbeitung. Von den klassischen Ansätzen übernehmen wir das Datenflußprinzip, das in Richtung einer stärkeren Nutzung von
Pipelining verbunden mit einer Einbettung effizienzsteigernder Materialisierungsstrategien weiterentwickelt werden soll. Als Grundlage hierfür ist das Informationsmodell (IM) zu integrieren. Die bereits
genannten Forderungen nach der Erzielung eines hohen Maßes an Pipelining und der Integration von Pipelining und paralleler Materialisierung stellen die besonderen Herausforderungen dar.

Erst in einem zweiten Schritt werden wir uns den Lernverfahren zuwenden und auf Basis der gewonnenen Erkenntnisse eine geeignete Teilmenge auswählen und in das System integrieren. Dabei wollen wir die ParaStation-Plattform nutzen, um gerade die Verfahren zu unterstützen, die sich bisher aufgrund der Beschränkungen gängiger Rechnerverbindungen einer effizienten Parallelisierung verschlossen. Aus
datenbanktechnischer Sicht ergibt sich weiteres Optimierungspotential durch die Möglichkeit, Vorverarbeitung und Lernverfahren in einem gemeinsamen Operatorgraphen als ganzes zu optimieren (eine Erweiterung dessen, was gegenwärtig unter dem neuen Schlagwort Multi-Table-Learning kursiert), sowie durch die Ausdehnung der Materialisierungstechnik auf die Operatoren der Lernalgorithmen.
 
 
 

• Teilziel A: Pipeline-Parallelität im Informationsmodell.

Die generischen Operatoren des Informationsmodells sind im Hinblick auf die Parallelisierung umzusetzen. Dabei ist zunächst zu untersuchen, ob die Klassifikation der Operatoren, wie sie von Breitner  für das Informationsmodell vorgenommen wurde, auch bereits Aussagen über Parallelisierungsmöglichkeiten zuläßt, oder ob hier speziellere oder gar orthogonale Unterscheidungen getroffen werden müssen.

Bei der Umsetzung der Operatoren muß darauf geachtet werden, daß ein Höchstmaß an Pipelining erzielt wird. Dazu sind insbesondere die aufwendigen Operatoren unter Ausnutzung der günstigen Latenzzeiten der ParaStation-Plattform paketgrößenoptimal zu unterteilen. Nur wenn die angestrebte Unterteilung nicht mehr möglich ist oder zu ineffizient wird, muß dann noch auf Datenparallelität ausgewichen werden.

Pipelining ist aufgrund der Forderung nach annähernd gleichen Kosten der einzelnen Pipeline-Stufen etwas schwieriger zu beherrschen als datenparallele Ansätze und erfordert beispielsweise auch Maßnahmen zur Eindämmung von execution skew. Hier sind also auch noch Überlegungen zur dynamischen Lastverteilung erforderlich.

• Teilziel B: Kombination mit Materialisierung.

Für eine Materialisierung von Zwischenergebnissen muß die Pipeline gezielt unterbrochen werden. Dabei ist insbesondere darauf zu achten, daß eine ausreichende E/A-Bandbreite für die Ausgabe der Daten auf persistente Speichermedien zur Verfügung steht. Als preisgünstige Alternative zu einer persistenten Speicherung soll dabei auch die Nutzung freier Hauptspeicherkapazitäten im Cluster herangezogen werden. Durch das Caching im lokalen Hauptspeicher oder dem entfernter Knoten erspart man sich vergleichsweise teure Plattenzugriffe. Dabei kann teilweise auf Erfahrungen aus einer früheren Arbeit zurückgegriffen werden, die sich mit Caching im Wissensgewinnungsprozeß für den zentralen Fall beschäftigt.
 
• Teilziel C: Integration von Anfrageoptimierung und Datenverteilung für die Vorverarbeitung.

Galt bisher das Augenmerk zunächst der Untersuchung und dem Vergleich verschiedener Verfahren und Parameter, so soll nun das Gesamtsystem betrachtet werden. Dies erfordert einen Optimierer, der die Auswahl der Parallelisierungsstrategie, der Granularität und der Datenverteilungsstrategien und die Materialisierungs- und Nutzungsentscheidung für den Bereich der Vorverarbeitung selbständig übernimmt. Diese Aufgabe kann auch parallel zu den beiden vorangegangenen Arbeiten durchgeführt werden, soll aber sicherstellen, daß die weiteren Arbeiten auf einer leistungsfähigen und stabilen Grundlage aufsetzen.
 
 
• Teilziel D: Entwurf und Integration spezieller Operatoren für Lernverfahren.

Aufbauend auf den Erkenntnissen aus der anfänglichen Untersuchung und den Erfahrungen aus den vorigen Punkten ist nun die nahtlose Anbindung von Lernverfahren sicherzustellen. Dazu werden wir zunächst eine sehr beschränkte Auswahl aus den Verfahren treffen, die wir dann mittels spezieller Operatoren unterstützen. Dabei sind nun wiederum passende Parallelisierungsstrategien zu entwickeln. Aus Sicht der Vorverarbeitung besonders günstig wäre es, wenn sich dabei auf Pipelining basierende Ansätze nutzen lassen würden. Außerdem ist hier zu untersuchen, ob sich auch im Bereich der Lernverfahren ein Potential für den Einsatz von Materialisierung und Caching ergibt. Zu diesem Punkt existieren für die Optimierung der datenbankgebundenen Entscheidungsbaumkonstruktion (wiederum für den zentralen Fall) bereits erste Erfahrungen. 


• Teilziel E: Durchführung von Leistungsmessungen und Tests. 
  Am Ende einer jeden Phase sind umfangreiche Messungen und Test durchzuführen, um das Erreichte zu validieren und weiteren Optimierungsbedarf festzustellen, so daß am Ende der Gesamtlaufzeit ein stabiles und zufriedenstellendes Ergebnis präsentiert werden kann.