Inhalt

Programm
 
Projekt T1
Projekt T2
Projekt L1
Projekt N1
Projekt N2
Projekt LS1
 
Mitarbeiter
 
Veröffentlichungen
 
Projekte für Studenten
 

Links

 

ParaStation

Cluster OS

JavaParty

 

Teilprojekt N1: Parallele Bildfolgenauswertung

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


Ausgangssituation

Die Bildauswertung transformiert ein Bild oder eine Bildfolge in eine Aussage oder in eine zusammenhängende Folge von Aussagen, z.B. einen natürlichsprachlichen Text.  Bildauswertung, insbesondere Bildfolgenauswertung, ist daher zwangsläufig nichtlokal, mit entsprechend sehr viel höheren Anforderungen an die für Zugriffe verfügbar zu haltenden Daten sowie an die eigentlichen Berechnungsprozesse.  Dabei spielt es eine zusätzliche Rolle, ob man das Auswertungsergebnis für eine unter Echtzeitbedingungen erfolgende Entscheidung heranzieht oder nicht.

Die Bildauswertung benötigt im Grunde Rechenkapazitäten, die noch weit über das zur Zeit sinnvoll Verfügbare und Bezahlbare hinausgehen.  Dies beruht einerseits auf Komplexität und Umfang der durchzuführenden Berechnungen, andererseits auf dem Umfang des Bilddatenmaterials, das für praktisch relevante Anwendungen auszuwerten ist.  Eine zusätzliche, in der Praxis der Forschung wesentliche Randbedingung ergibt sich aus der Forderung nach einem möglichst umfassenden interaktiven Zugang zu allen Teilschritten der Auswertungsprozesse, um unerwartete Teilresultate oder Fehler direkt und detailliert abklären zu können.  Im Prinzip hohe Rechenleistungen, die aber mit langen Umlaufzeiten und nur begrenztem Zugang zu Zwischenergebnissen verbunden sind, helfen nur sehr beschränkt oder überhaupt nicht weiter.

Vor diesem Hintergrund besteht ein fundamentales Interesse daran, zumindest für Schlüsselexperimente der Bild(folgen)auswertung mehr Rechenkapazität unter Laborbedingungen - d.h. bei auch interaktiver Nutzungsmöglichkeit - mobilisieren zu können.  Die Verkoppelung von Arbeitsstationen ohne prohibitiven Parallelisierungsaufwand zur Bearbeitung von experimentellen Programmsystemen verspricht einen gangbaren Ausweg aus dem skizzierten Engpaß.

Lange vor Beginn und auch noch parallel zur Bearbeitung des RESH-Projektes war die Entwicklung von Xtrack zunächst darauf ausgerichtet, sukzessive Schwierigkeiten aufzuspüren und zu beseitigen, die bei der modellgestützten Verfolgung einzelner Fahrzeuge diagnostiziert werden konnten. In diesem Zusammenhang entwickelte sich die Verfolgung eines Fahrzeuges in einem Halbbild - im folgenden auch als Verfolgungsauftrag bezeichnet - zur elementaren Komponente der Systemkonzeption: die zwangsläufig überwiegend interaktiv erfolgende Untersuchung von Verfolgungsaufträgen legte deren weitere Untergliederung und Parallelisierung weder nahe noch bot sich eine einfache Möglichkeit dazu an. Dies spiegelt sich auch in der im Laufe der Zeit schrittweise entstandenen Programmstruktur von Xtrack wider.

Inzwischen wurde allerdings ein Stadium erreicht, in dem umfangreichere Bildfolgen mit zahlreichen Fahrzeugen in zunehmend länger dauernden Versuchen auszuwerten sind, um seltener auftretenden Schwierigkeiten auf die Spur zu kommen (vgl. [36, 23]). Dadurch verschiebt sich der Blickwinkel, unter dem das Experimentalsystem Xtrack wahrgenommen wird.

Bisher werden alle zur Verfolgung eines einzelnen Fahrzeuges erforderlichen Berechnungen lokal sequentiell ausgeführt. Darüber hinaus wurde ursprünglich ein einzelnes Fahrzeug im Anschluß an die Initialisierung der Verfolgungsprozesses von Halbbild zu Halbbild so lange weiterverfolgt, bis es entweder das Gesichtsfeld der Kamera verlassen hatte, die Bildfolge abgearbeitet oder der Verfolgungsprozeß als endgültig gescheitert zu betrachten war. Mit wachsender Zuverlässigkeit des Verfolgungsprozesses bietet es sich nunmehr an, die umfangreichen Rohdaten einer digitisierten Video-Aufnahme nur einmal einzulesen und alle in einer Aufnahme sichtbaren Fahrzeuge gleichzeitig zu verfolgen. Dadurch kann es vorteilhaft werden, bestimmte 'elementare' Berechnungen wie beispielsweise von Kantenelementen oder von Optischer-Fluß-Vektoren für das ganze Bild in einem einzigen Arbeitsschritt durchzuführen: Unter bestimmten Umständen lassen sich die zu verwaltenden Datenstrukturen erheblich vereinfachen, was die weitergehende Parallelisierung eines solchen Arbeitsschrittes erleichtern kann.

Die auf zahlreiche methodische Verbesserungen zurückzuführende wachsende Robustheit der modellgestützten Bildfolgenauswertung in Xtrack ermöglicht und erzwingt zugleich umfangreichere Experimente, was den Wunsch nach einer Verkürzung der Auswertungszeiten durch Parallelisierung verstärkt. Dieser - durch Entwicklungen im Anwendungsbereich bedingte - Wunsch nach Parallelisierung von Xtrack trifft auf die im Rahmen des RESH-Projektes gebotenen programm- und gerätetechnischen Möglichkeiten, die dabei auftretenden Fragen eingehender zu untersuchen.
 

Stand des Teilprojekts:

Überprüfung von Xtrack als Werkzeug für quantitative Untersuchungen.
Mit der im ersten Abschnitt des RESH Projekts entstandenen Systemversion konnte in umfangreichen Voruntersuchungen nachgewiesen werden, daß die mittlere Rate, mit der ein Verfolgungsauftrag durch einen Rechner abgearbeitet werden kann, in guter Näherung proportional zur Prozessor-Taktfrequenz steigt. Erstaunlicherweise ist der Proportionalitätsfaktor für mehrere aufeinander folgende Prozessorarchitekturen der Firma Sun (SPARC, SuperSPARC, UltraSPARC-I, UltraSPARC-II) praktisch gleich.

Um sich gegen eine Fehldeutung der Messungen abzusichern, wurde der Versuch auf einer AlphaStation der Forschungsgruppe Tichy wiederholt, die über einen mit 500 MHz getakteten Prozessor des Typs 21164A verfügt. Dazu mußte der Quelltext der Xtrack-Version geringfügig an die speziellen Konventionen des auf der AlphaStation zur Verfügung stehenden C++-Übersetzers adaptiert werden. Die Messung auf dieser AlphaStation ergab eine Rate von ca. 0,7 Verfolgungsaufträgen pro Sekunde, also überproportional schneller als auf dem schnellsten (300 MHz) zur Verfügung stehenden Sun UltraSPARC-II Prozessor. Die Messungen wurden daraufhin auf einer AlphaStation des Typs 21164A wiederholt, deren Prozessor mit 600 MHz getaktet wird. Die entsprechenden Meßergebnisse zeigen, daß die Steigung der Auswertungsrate als Funktion der Frequenz signifikant steiler verläuft als auf den verfügbaren Sun-Anlagen.

Da der 'Hebelarm' zur Bestimmung dieser Steigung mit 100 MHz deutlich kleiner als bei den Sun-Anlagen ist, wurde die Messung auch noch auf einer AlphaStation vom Typ 21064 wiederholt, deren Prozessor nur mit 200 MHz getaktet wird. Der so erhaltene Meßwert liegt unter demjenigen einer mit 200 MHz getakteten UltraSPARC-II. Auch im Fall der DEC AlphaStationen, bei denen die Prozessortaktfrequenzen immerhin über einen Bereich von 400 MHz variieren, kann man die gemessenen Auswertungsraten in guter Näherung als lineare Funktion der Prozessortaktfrequenz beschreiben, wobei allerdings die Steigung der Geraden deutlich größer als für die Sun-Anlagen ist.

Ein Leistungsvorsprung der AlphaStationen war in solcher Deutlichkeit nicht erwartet worden. Es wurde daher die Hypothese überprüft, daß zumindest ein Teil der für diese Xtrack-Version auf den AlphaStationen gemessenen größeren Rechnerleistung auf den proprietären C/C++-Übersetzer der Firma DEC zurückzuführen sei. Dazu wurde die neueste Version des Sun-C/C++-Übersetzers (4.2) besorgt, um den Versuch auf den UltraSPARC-II Arbeitsplatzstationen nach Übersetzung von Xtrack mit diesem Übersetzer zu wiederholen. Es stellte sich heraus, daß der Sun-4.2 Übersetzer ebenfalls eine in Details von den übrigen Übersetzern abweichende Sprachversion von C/C++ akzeptiert, was einen nicht unbeträchtlichen Adaptationsaufwand erforderte. Nach Übersetzung mit dem proprietären Übersetzer von Sun wurde auf den 200 MHz UltraSPARC-II Arbeitsplatzstationen nur noch 75 % der Rechenzeit benötigt wie nach einer Übersetzung mit dem gnu-2.7.2.1 Übersetzer. Die in Abbildung 3 durch Dreiecke repräsentierten Meßwerte für 200 MHz und 300 MHz Taktfrequenz sind kompatibel mit demselben Proportionalitätsfaktor, der sich aus den Messungen für den gnu-Übersetzer ergibt. Allerdings liegt die entsprechende Gerade für den Sun-Übersetzer 4.2 deutlich über derjenigen, die man für die mit dem gnu-Übersetzer übersetzte Xtrack-Version erhält.
 

Randbedingungen für eine Parallelisierung von Xtrack.
Mit der so entstandenen Xtrack-Version steht nunmehr ein Werkzeug zur Verfügung, das in Kombination mit einer - im Hinblick auf Dauer, Art, Größe und Bewegungsverhalten von Fahrzeugen geeignet ausgesuchten - Bildfolge die quantitative Untersuchung zahlreicher Detailfragen zur Parallelisierung erlaubt. Allerdings lassen die folgenden Randbedingungen nur eine relativ grobkörnige Parallelisierung zu:
 
  • Verdeckungen zwischen Fahrzeugen können eine Auswertungsreihenfolge bedingen und damit eine parallele Auswertung bestimmter Fahrzeuge unmöglich machen (die Position des verdeckenden Fahrzeuges muß bei der Positionsschätzung des verdeckten Fahrzeuges bekannt sein).
  • Der Videostrom ist inhärent sequentiell, d.h., zeitlich geordnet (alle 20 msec ein Halbbild). Eine parallele Auswertung von Halbbildern, die zu unterschiedlichen Zeitpunkten aufgenommen wurden, ist nicht sinnvoll, wenn die Auswertung Videoechtzeit erreichen, also ein Bild direkt nach seiner Aufnahme so schnell wie möglich ausgewertet werden soll.
  • Werden in der Entwicklung befindliche Algorithmen und Verfahren ,,zu stark`` parallelisiert, ist zu erwarten, daß der Änderungsaufwand für eine eventuell nötige Rückbildung der Parallelisierung sehr hoch wird. Eine Optimierung auf eine spezielle parallele Rechnerkonfiguration durch eine überangepaßte feinkörnige Parallelisierung soll daher vermieden werden.


Die folgende Abbildung skizziert die bei den anschließenden Untersuchungen verwendete Prozeßstruktur.

Abbildung:   Kommunikationsstruktur und Aufgabenverteilung des Systems bei paralleler Verfolgung mehrerer Fahrzeuge. Der Anwender spezifiziert die vorzunehmenden Verfolgungsprozesse durch Interaktion mit dem Steuer-Prozeß. Die Rechtecke stellen Prozesse dar, die i.a. jeweils auf einem eigenen Prozessor ausgeführt werden. Die Kommunikation zwischen den Prozessen ist durch die unterschiedlichen Linien angegeben. Die gepunkteten Linien repräsentieren die Kommunikationsverbindungen für Steuerbefehle. Die durchgezogenen Linien stellen die Kommunikationsverbindungen für Bilddaten oder Verfolgungsergebnisse dar, wobei die Pfeile die Kommunikationsrichtung angeben.
Kleine Quadrate am Anfang einer Linie deuten die Nutzung der Sockel-Programmierschnittstelle (engl. Socket) auf Anwendungsebene an. Die dicken gestrichelten horizontalen Linien sollen darauf hinweisen, daß die so separierten Teile des parallelen Systems auch räumlich weit voneinander entfernt sein können.

Mit dieser parallelen Programmversion wurden umfangreiche Experimente bei unterschiedlichen Parametrierungen durchgeführt. Sie sollten die durchschnittliche und maximale Leistungsfähigkeit einer Parallelisierung herausarbeiten, der ein Verfolgungsauftrag als 'feinstes Korn' zu Grunde liegt. In Absprache mit Teilprojekten T1 wurde das 'Message Passing Interface' (MPI) zur Unterstützung der Interprozeßkommunikation verwendet, das sowohl auf den Sun-Rechnern als auch auf der ParaStation verwendet werden kann.
 
 

Quantitative Charakterisierung der Xtrack-Parallelisierung auf den Sun-Anlagen.
Nach Vorlaufmessungen auf einem inhomogenen Netzwerk aus Sun-Rechnern mit UltraSPARC-I und UltraSPARC-II Prozessoren zur Abklärung von Detailfragen wurden die Versuchsreihen zunächst auf einem Verbund aus zwei Sun UltraSPARC-II Doppelprozessor-Rechnern (200 MHz UltraSPARC-II Prozessoren) vorbereitet, wobei die Sun-Rechner über Ethernet mit ca. 10 MBit/s maximaler Übertragungsleistung verbunden waren. Die wichtigsten Ergebnisse sind:
  1. Das Einlesen der digitisierten Video-Aufnahmen von einer Festplatte durch einen Verteiler-Prozeß sowie insbesondere die anschließende Verteilung dieser Daten auf verschiedene Rechner des Sun-Verbundes resultieren in einem nachweisbaren Zeitverlust. Dieser Zeitverlust läßt sich verringern, wenn der Verteilerprozeß auf einem der Knotenrechner läuft, auf dem auch Verfolgungsprozesse abgewickelt werden, da dann wenigstens teilweise die schnelle Kommunikation über gemeinsam zugreifbaren Arbeitsspeicher genutzt werden kann.
  2. Der Zeitbedarf pro Verfolgungsauftrag wird mitbestimmt durch Effekte, die im allgemeinen vor Beginn der Auswertung einer neuen Bildfolge nicht bekannt oder beeinflußbar sind:

  3. - Die Zahl der zu einem bestimmten Zeitpunkt im Gesichtsfeld der Video-Kamera erfaßbaren Fahrzeuge läßt sich unter realen Einsatzbedingungen nicht voraussagen, ebensowenig wie der Zeitpunkt, zu dem die Verfolgung eines Fahrzeuges aufgenommen werden sollte. Folgende Abbildung  illustriert die starke Variation der Zahl von Fahrzeugen im Laufe einer Bildfolge.
    - Die Zahl der Iterationen des Iterativen Erweiterten Kalman-Filters (IEKF) während der Aktualisierungsphase eines Verfolgungsauftrages hängt von nicht vorhersehbaren numerischen Verhältnissen ab (vgl. hierzu ebenfalls folgende Abbildung).
    - Die Größe eines Fahrzeugabbildes - und damit die zur Bearbeitung erforderliche Rechenkapazität - hängt vom Typ des Fahrzeuges (PKW, Kleinlaster, Bus, LKW, etc.) sowie von dessen Position in der Szene ab. Letztere ändert sich außerdem im allgemeinen während einer Bildfolge.
    - Der Zeitbedarf zur Berücksichtigung der Verdeckung eines Fahrzeuges durch stationäre oder bewegliche Objekte läßt sich ebenfalls nicht so vorausberechnen, daß man eine brauchbare Verteilung von Verfolgungsaufträgen darauf abstützen kann.
  4. Falls die Größe des Fahrzeugabbildes von Fahrzeug zu Fahrzeug sehr schwankt, wirkt sich bereits die Reihenfolge, in der die Verfolgungsaufträge auf die einzelnen Knoten verteilt werden, erheblich auf die Effizienz der Parallelisierung aus.


Abbildung:   Zahl der gleichzeitig pro Aufnahme verfolgten Fahrzeuge (punktierte Linie) sowie mittlere Berechnungszeit pro Verfolgungsauftrag als Funktion der (Halb-)Bildnummer in der Bildfolge stau05. Die Spitzenwerte für die mittlere Dauer eines Verfolgungsauftrages werden durch mehrfache Iterationen des Iterativen Erweiterten Kalman-Filters (IEKF) verursacht, insbesondere wenn ein Fahrzeug in das Gesichtsfeld der Video-Kamera eintritt. Darüber hinaus treten Spitzenwerte auch auf, wenn Zwischenergebnisse alle 50 (Halb-)Bildnummern auf der Festplatte gerettet werden.


Als Konsequenz ergibt sich, daß man von einer beträchtlichen Fluktuation der Berechnungszeiten pro Verfolgungsauftrag ausgehen muß, die in einer stark schwankenden Effizienz der Parallelisierung resultieren kann. Ein Verfolgungsauftrag stellt demnach im Hinblick auf die weiteren zu beachtenden Randbedingungen (vgl. oben) ein 'zu grobes Korn' für eine Parallelisierung auf dem hier verfügbaren Bündel von Sun UltraSPARC-II Arbeitsstationen mit Ethernet-Kopplung dar. Auf der anderen Seite haben diese Untersuchungen es erlaubt, eine Fülle von Detailproblemen, die sich erst während der Messungen bemerkbar machten, in der unserer Arbeitsgruppe ständig zur Verfügung stehenden und vertrauten Umgebung zu klären, bevor Messungen zur Parallelisierung von Xtrack auf der ParaStation gestartet wurden.
 

Quantitative Charakterisierung der Xtrack-Parallelisierung auf der ParaStation.

Um die Auswirkungen eines Hochgeschwindigkeitskommunikationsnetzes auf das Verhalten und die Effizienz des gewählten Parallelisierungsansatzes zu untersuchen, wurden anschließend vergleichbare Experimente auf der ParaStation durchgeführt (Verbund von DEC Alpha Arbeitsplatzrechnern unter Nutzung von speziellen, auf Hochgeschwindigkeitskommunikation ausgelegten Netzwerkkarten der Firma Myrinet mit einem sehr geringen Initialisierungs-Zeitbedarf für die Kommunikation und ca. 1280 MBit/s maximaler Übertragungsleistung).
Versuchsnummer  P89 
Bildfolge  Ettlinger-Tor 
Einzelbild-Datenvolumen  512 x 512 x 1 Bytes 
Bildfolge komprimiert  nein 
Bildfolgenausschnitt  5 - 94 
Anzahl verfolgter Objekte  4
Objektart: Nr.  4x PKW: 4x 5
Xtrack-Version  Stockmar: of-edgel-lenk-autodiff
Anzahl Prozessoren 
Anzahl Prozesse 
Verteiler-Prozeß/Leerlauf  i41a5/99% 
Verfolgungs-Prozeß/Leerlauf/Nr.  i41a5/99%/5 
Verfolgungs-Prozeß/Leerlauf/Nr.  i41a6/99%/5 
Verfolgungs-Prozeß/Leerlauf/Nr.  i41a7/99%/5
Verfolgungs-Prozeß/Leerlauf/Nr.  i41a8/99%/5
Bildquelle/Leerlauf i41a5/99% 
Laufzeit (Std:Min:Sek)  1:31 
Bilder einlesen (Std:Min:Sek)  0:01 
Bilder verbreiten (Std:Min:Sek)  0:01 
Prozessorzeit (Std:Min:Sek)  1:27, 1:28, 1:29, 1:29 
Verfolgungszeit (Std:Min:Sek)  1:26, 1:27, 1:25, 1:27 
Gesamtwartezeit (Min:Sek)  0:05, 0:05, 0:06, 0:04 
Bilder empfangen (Min:Sek)  0:01, 0:02, 0:02, 0:01 
Verfolgung freigeben (Min:Sek)  0:00, 0:00, 0:00, 0:01 
Synchronisation (Min:Sek)  0:03, 0:02, 0:04, 0:02 
Ergebnis senden (Min:Sek)  0:00, 0:00, 0:00, 0:00 
abweichende Ergebnisse 

 
 Dieses tabellarische Protokoll illustriert die Art der quantitativen Erfassung verschiedener (Warte-, Transfer-, Synchronisations- und Arbeits-)Zeiten bei einem Versuch auf der ParaStation, der zum Vergleich mit einem entsprechenden Versuch (S89) auf dem Sun-Verbund mit 4 dort verfügbaren Prozessoren durchgeführt worden ist. Aus diesem Grunde wurde die Zahl der auf der ParaStation eingesetzten Prozessoren ebenfalls auf 4 begrenzt. Die hier festgehaltenen Einzelergebnisse fließen ein in die zusammenfassende Darstellung der Tabelle 3, auf die wegen eingehenderer Erläuterungen verwiesen wird. (Auf führende Nullen bei Zeitangaben wurde im Einzelfall verzichtet).
Versuch  S3  P3  S14  P14  S41  P41 
Laufzeit (Std:Min:Sek)  4:35  1:22  19:46  6:00  1:22:09  23:58 
Beschleunigung  3.3
 Vergleich von sequentiellen Laufzeiten auf einem Sun-Rechner und einem Rechner der ParaStation2. Ein Prozessor der ParaStation2 führt im Vergleich zum Sun-Rechner Versuch 3 um den Faktor 3.3, den Versuch 14 um den Faktor 3.3 und Versuch 41 um den Faktor 3.4 schneller aus.
Versuch  S19  S89  P89  P89a 
Anzahl Prozessoren 
parallele Laufzeit (Min:Sek)  5:35  5:11  1:31  3:07 
Kommunikationszeit (Min:Sek)  57  27  2 1:35
Laufzeitanteil (%)  17  51 
seq. Laufzeit (Min:Sek)  4x 4:35  4x 4:35  4x 1:22  4x 1:22 
Beschleunigungsfaktor  3.3  3.5  3.6  1.8 
Effizienz (%)  82  88  90  44

 
Vergleich der zur Kommunikation auf dem Sun-Verbund und der ParaStation2 gemessenen absoluten und prozentualen Zeiten und deren Auswirkung auf die erzielte Leistungssteigerung. Die vierfache Verfolgung eines einzelnen Fahrzeug-Abbildes (Objekt 5) durch 4 Prozessoren - vergleiche Tabelle 1 - soll eine ideale Verfolgung von gleich großen, aber verschiedenen Fahrzeug-Abbildern simulieren. In der Simulation liegt dadurch eine optimale Lastverteilung vor. Die erreichte Effizienz von 88% (Sun-Verbund) bzw. 90% (ParaStation2) stellt in der Praxis eine Barriere für die erzielbare Effizienz dar, die bei einer parallelen PKW-Verfolgung in der Ettlinger-Tor-Bildfolge derzeit kaum überschritten werden kann. Herkömmliche Netzwerkkarten (100Base-T) wurden zur Kommunikation in Versuch P89a eingesetzt. Die Ergebnisse zeigen im Vergleich zu Versuch P89 einen starken Leistungseinbruch. Die erzielte Beschleunigung (1.8) bzw. Effizienz (44%) beträgt etwa die Hälfte der in Versuch P89 erzielten Beschleunigung (3.6) bzw. Effizienz (90%).
Versuch  S82  P82  S93  P93 
Anzahl Prozessoren 
parallele Laufzeit (Min:Sek)  06:27 01:52  12:47  03:46 
seq. Laufzeit (Min:Sek)  19:46  06:00  34:35  12:20 
Beschleunigungsfaktor  3.1  3.2  2.7  3.3 
Effizienz (%)  77  80  68  82 

 
Vergleich spezieller auf dem Sun-Verbund und der ParaStation2 erzielter Ergebnisse. In den dargestellten Versuchen lag eine gute Lastverteilung vor. Im Versuch 82 bzw. Versuch 93 wurden 4 bzw. 8 Verfolgungen von annähernd gleich großen Fahrzeug-Abbildern auf 4 Prozessoren durchgeführt. Die erzielte Effizienz fällt mit etwa 68 - 77% (Sun-Verbund) befriedigend bzw. mit 80 - 82% (ParaStation2) gut aus.
Versuch  S96  P96  S60  P60 
Anzahl Prozessoren 
par. Laufzeit (Std:Min:Sek)  39:03  10:35  1:01:10  18:19 
seq. Laufzeit (Std:Min:Sek)  1:22:09  23:58  3:13:07  54:39 
Beschleunigungsfaktor  2.1  2.3  3.2  3.0 
Effizienz (%)  53  57  79  75 
Exemplarischer Vergleich von Ergebnissen, die auf dem Sun-Verbund und der ParaStation2 erzielt worden sind. Die Ergebnisse der Versuche 96 zeigen die Auswirkung einer ungleichen Lastverteilung, die - verursacht durch eine zeitaufwendige Verfolgung (Bus-Abbild) und einen gleichzeitigen Mangel an weiteren Verfolgungs-Aufträgen - die erzielte Leistung deutlich verringert. Im Vergleich zu den in Tabelle 4 aufgeführten Leistungsdaten sinkt die erzielte Beschleunigung von 68 - 77% auf 53% (Sun-Verbund) bzw. von 80 - 82% auf 57% (ParaStation2). Eine wesentlich bessere Beschleunigung und Effizienz läßt sich in der untersuchten Bildfolge erzielen, wenn Fahrzeug-Abbilder klassifiziert werden sollen. Unter der Prämisse einer Mehrfachverfolgung von Fahrzeug-Abbildern mit jeweils 2 - 3 verschiedenen Fahrzeugmodellen ergeben sich Beschleunigungen von 3.2 (Sun-Verbund) bzw. 3.0 (ParaStation2) und Effizienzen von 79% (Sun-Verbund) bzw. 75% (ParaStation2).


Tabelle 1 illustriert an einem auf der ParaStation der Arbeitsgruppe Tichy durchgeführten Versuch die Art der Detail-Dokumentation von Messungen zur Parallelisierung. Die auf der ParaStation erarbeiteten Ergebnisse werden in den Tabellen 2 bis 5 den entsprechenden Resultaten für den Sun-Verbund gegenübergestellt. Besonders hingewiesen werden soll auf die erhebliche Verbesserung, die sich durch die effiziente Kommunikation der ParaStation (man vergleiche Versuche P89 und P89a in Tabelle 3) im Gegensatz zur konventionellen Kommunikation erzielen läßt. Die drastische Verkürzung der Kommunikationszeiten bei diesem Versuch von 1:35 Minuten (= 95 Sekunden) auf 2 Sekunden erhöht die Effizienz der ParaStation-Nutzung von 44 % auf 90 %, sofern man durch eine geeignete (für beide Versuche identische) Konfiguration der Verfolgungsaufträge der ParaStation ermöglicht, ihre Kapazität möglichst weitgehend zu nutzen.

Abbildung:  (a) Laufzeit- und (b) Effizienzverhalten bei steigender Anzahl an verfolgten Objekten. Die Anzahl der für die Verfolgungs-Prozesse verwendeten Prozessoren bestimmt die Sprungstellen. In der dargestellten Untersuchung auf der ParaStation wurden 4 Prozessoren eingesetzt, um die Ergebnisse mit denjenigen vergleichen zu können, die mit dem Sun-Verbund gewonnen worden waren. Die auf dem Sun-Verbund gemessenen Effizienzwerte unterschieden sich nur wenig von den in (b) dargestellten, während die Gesamtlaufzeit natürlich deutlich höher lag als in Teilbild (a).


Trotz einer Effizienz von ca. 80% bei nahezu optimaler Lastverteilung ergibt sich mit einer durchschnittlichen Effizienz von ca. 55% ein unbefriedigend niedriger Wert. Durch die mit ca. 1-2 Sekunden im Vergleich zur Kommunikationsgeschwindigkeit sehr langsamen, intern nicht weiter parallelisierten Verfolgungsaufträge kann die Leistungsfähigkeit des Hochgeschwindigkeitskommunikationsnetzes selbst bei nahezu optimaler Lastverteilung nicht annähernd ausgenutzt werden. Wie auch durch vorherige Abbildung verdeutlicht wird, läßt sich wegen nicht beeinflußbarer Faktoren eine ausgeglichene Lastverteilung im allgemeinen Fall bei der gewählten Körnigkeit nicht erreichen (wenn z.B. die Anzahl der sichtbaren Fahrzeuge kleiner wird als die Anzahl der eingesetzten Prozessoren oder ein ,,rechenintensives`` Fahrzeug mit großflächigem Abbild in das Blickfeld der Kamera eintritt).

Um eine höhere Effizienz zu erreichen, ist das bisher entwickelte Programmsystem im Hinblick auf 'bessere' Parallelisierbarkeit unter Berücksichtigung aller angeführten Nebenbedingungen völlig neu zu konzipieren, zu implementieren und zu testen. Anschließend sollten damit weitere Untersuchungen zur besseren Nutzung der durch einen Parallelrechner verfügbar gemachten Rechenkapazität geplant und durchgeführt werden. Die dafür wünschbare Installation einer direkten Verbindung von der - eine Verkehrssituation aufzeichnenden - Video-Kamera in unser Labor wurde inzwischen soweit vorbereitet, daß sie in den noch verbleibenden Monaten der ersten Projektphase in einem Probebetrieb geprüft werden könnte.

Hinweise auf detaillierte quantitative Aussagen über die Parallelisierung von Ansätzen zur modellgestützten Bildfolgen-Auswertung, die vergleichbar wären mit den in den vorangehenden Abschnitten diskutierten Messungen, wurden in der zugänglichen Fachliteratur nicht gefunden. Diese Feststellung wird darauf zurückgeführt, daß Xtrack den zur Zeit weltweit methodisch und experimentell am breitesten abgesicherten Ansatz zur modellgestützten Bildfolgen-Auswertung bei Verkehrsszenen darstellt. Charakteristisch für Xtrack ist die Kombination einer ausgefeilten signalnahen Auswertung durch Berücksichtigung von Kantenelementen und Optischer-Fluß-Vektoren, die mit zwischen Halbbildern interpolierenden Ableitungs-Operatoren bestimmt werden, und der sehr weitgehenden Nutzung von Wissen über Objekte, Beleuchtungsverhältnisse und Bewegungen im Szenenbereich, die durch entsprechende Modelle in den Auswertungsprozeß eingebracht werden. Genau diese Verschränkung von signalnahen und auf geometrischem Wissen über die dreidimensionale Struktur der Szene basierenden Auswertungsschritten ist der Grund für einerseits die Robustheit von Xtrack, andererseits aber auch für die Problematik, eine geeignete 'Korngröße' unterhalb des Verfolgungsauftrages zu finden. Andere Arbeiten bemühen sich entweder um eine Parallelisierung der signalnahen Auswertung  oder studieren vorwiegend die Repräsentation und Nutzung von abstrakterem Wissen über Geometrie und Verhalten der beobachteten Körper in der Szene. Die Bewertung eines Parallelisierungsansatzes kann nicht unabhängig von einer Berücksichtigung der jeweils herangezogenen Methoden der Bild(folgen)-Auswertung vorgenommen werden. Dabei ist zu berücksichtigen, daß die vergleichende Bewertung verschiedener methodischer Ansätze zur Bild(folgen)-Auswertung sich inzwischen zu einem eigenen Teilgebiet entwickelt.
 
 
 

Ziele:

Im Vordergrund steht das Teilziel, auch unter allgemeinen Einsatzbedingungen eine möglichst hohe Effizienz bei der Nutzung einer ParaStation zur Bildfolgenauswertung zu erreichen. Die dadurch ermöglichte Leistungssteigerung soll zweitens zu methodischen Verbesserungen genutzt werden, insbesondere um Video-Bildfolgen von Verkehrsszenen zuverlässig schritthaltend auswerten zu können. Als drittes Teilziel wird angestrebt, aus den konkret durchgeführten Maßnahmen auf allgemeingültigere Aussagen über die Beziehungen zwischen Aufwand und Gewinn bei der Parallelisierung zu schließen.

Die dazu für Teilprojekt N1 vorgesehenen Arbeitspakete umfassen folgende Punkte:

  • Arbeitspaket N1.A: Neukonzeption eines parallelen Programmsystems par-Xtrack zur Bildfolgenauswertung von Verkehrsszenen mit einer wesentlich feinkörnigeren Parallelisierbarkeit als bisher. Dabei soll mit Unterstützung durch die Teilprojekte T1 und T2 insbesondere geklärt werden, welche Vorteile sich aus einer Neuformulierung in Java/JavaParty ergeben.
  • Arbeitspaket N1.B: Zunächst schrittweiser Umbau von Xtrack zu par-Xtrack durch Einkapselung geeignet ausgewählter Teile und deren Integration in einen neu formulierten Rahmen.
  • Arbeitspaket N1.C (zeitlich verschränkt mit Arbeitspaket N1.B): Durchführung von Messungen zum Nachweis einer adäquaten Nutzung der zur Verfügung stehenden Kapazität des Rechnerbündels, zunächst auf einer der ParaStation strukturgleichen, aber kleineren Rechnerkonfiguration im Labor der Arbeitsgruppe Kognitive Systeme, anschließend Ausweitung der Messungen auf einer leistungsfähigeren Partition der durch die Arbeitsgruppe Tichy zu beschaffenden mittelgroßen ParaStation mit 16 Doppelprozessoren. In beiden Versuchsanordnungen sollen die Eingabebildfolgen zunächst von geeigneten Plattenspeichern eingelesen werden.
  • Arbeitspaket N1.D: Nutzung der dadurch gewonnenen Einsichten zur Überarbeitung der Konzeption und weitergehende Umsetzung des Konzeptes.
  • Arbeitspaket N1.E: Studium von Verbindungen verschiedener ParaStation-Rechnerbündel, die über breitbandige Netze verbunden sind (155 bzw. 620 MBit/s ATM, Gigabit Ethernet).
  • Arbeitspaket N1.F: Erprobung der neuen Implementierung auf einem kleinen ParaStation-Rechnerbündel im Labor der Arbeitsgruppe Kognitive Systeme zur unmittelbaren (Teil-)Auswertung von Bildfolgen einer Video-Kamera; eine Echtzeitübermittlung der Videodaten von Verkehrsszenen am Durlacher-Tor-Platz in Karlsruhe in unser Labor wird zur Zeit vorbereitet.
  • Arbeitspaket N1.G: Quantitativer Test der Leistungsfähigkeit der Parallelisierung auf großer ParaStation (Zugang zum gesamten, unpartitionierter Rechnerbündel im Labor der Arbeitsgruppe Tichy, gegebenenfalls auch zu einem noch größeren Bündel, soweit dieser wie geplant zugänglich werden sollte). Hierdurch soll der erreichte Grad an Skalierbarkeit durch Auswertung längerer Bildfolgen komplexerer Verkehrssituationen mit zahlreichen Fahrzeugen unter schwierigen Beleuchtungsbedingungen ermittelt werden.
  • Arbeitspaket N1.H: (parallel zu Arbeitspaketen N1.B bis N1.F): Quantitative Erfassung von Angaben zu Änderungen am Quellprogrammtext sowie zu den dadurch jeweils erreichten Verbesserungen (Durchsatzsteigerung in Zahl der verfolgten Fahrzeuge pro Halb-Bild, Senkung des Prozentsatzes unbefriedigend oder gar nicht verfolgter Fahrzeuge, Beschleunigung bei der Realisation von Folgeänderungen sowie Zeitgewinn bei der Planung und Durchführung von Experimenten durch Übergang auf günstigere Programm- und Datenstrukturen). Suche nach geeigneten Verknüpfungen solcher Angaben, um brauchbare Voraussagen über den Zusammenhang zwischen (Änderungs-)Aufwand und Leistungszuwachs bei der Parallelisierung zu gewinnen. Soweit möglich, soll dabei auf verfügbares Wissen zur quantitativen Bewertung alternativer Programm- und Systemkonstruktionen zurückgegriffen werden.
Zur Erprobung ist der unmittelbare Zugang zu einem kleineren Rechnerbündel im Bildfolgenauswertungslabor erforderlich (siehe Arbeitspakete N1.C, N1.E bis N1.G). Die Arbeitsgruppe Tichy hat dafür die (leihweise) Überlassung mindestens zweier geeignet verbundener AlphaStationen zugesagt. Gedacht wird auch an den (zeitweise exklusiven) Zugang zur bisherigen ParaStation durch die Arbeitsgruppe Kognitive Systeme, sobald die von der Arbeitsgruppe Tichy zu beschaffende neue ParaStation betriebsbereit zur Verfügung steht. Diese Rechnerbündel müssen mit einem gleich strukturierten, aber umfangreicheren und damit leistungsfähigeren Rechnerbündel über eine Breitbandverbindung kommunizieren können (siehe Arbeitspakete N1.E und N1.G), um bei Bedarf lokal vorgeprüfte Programmversionen unter größerer Last beurteilen zu können (siehe Arbeitspaket N1.G). Darüber hinaus ist in gegenseitiger Absprache die (nicht nur kurzzeitige) Reservierung einer Partition auf der geplanten neuen ParaStation im Labor der Arbeitsgruppe Tichy für Untersuchungen im Rahmen der Teilprojekte N1/N2 ins Auge gefaßt worden.

Page design & maintenance: Matthias Gimbel, Bernhard Haumacher, and Jürgen Reuter.
Last change Fri 07 May 2004 08:44:14 PM CEST.