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:
-
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.
-
Der Zeitbedarf pro Verfolgungsauftrag wird mitbestimmt durch Effekte, die
im allgemeinen vor Beginn der Auswertung einer neuen Bildfolge nicht bekannt
oder beeinflußbar sind:
- 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.
-
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 |
4 |
Anzahl Prozesse |
5 |
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 |
4 |
4 |
4 |
4 |
parallele Laufzeit (Min:Sek) |
5:35 |
5:11 |
1:31 |
3:07 |
Kommunikationszeit (Min:Sek) |
57 |
27 |
2 |
1:35 |
Laufzeitanteil (%) |
17 |
9 |
2 |
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 |
4 |
4 |
4 |
4 |
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 |
4 |
4 |
4 |
4 |
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.
|