W I L L K O M M E N
Universität Freiburg - Institut für Informatik
Lehrstuhl für Mustererkennung und Bildverarbeitung (LMB)
[-]LMB
   [+]Mitarbeiter
   [-]Forschung
    |  | Gebiete:
    |  |-Invariant theory ()
    |  |-Design of Classifiers ()
    |  |-Computer Vision ()
    |  |-Motion and Depth Estimation ()
    |  |-Digital Image Filtering  ()
    |  |-Multi Spectral Image Analysis ()
    |  |-Fast and Parallel Algorithms ()
    |  | Laufende Projekte
    |  |-Computer Vision ()
    |  |-Invariance in Kernel Methods ()
    | [+]I-search ()
    |  |-OMIB ()
    |  |-OMNIBUSS ()
    |  | Abgeschl. Projekte
    |  |-NOBLESSE ()
    |  |-MOVIS
    |  |-SFB-238
    |  |-Parallelisierung
    |  |-Automatische Sichtprüfung...
    |     ()
   [+]Studien-, Diplom- und Bachelor...
   [+]Lehrveranstaltungen
    |-Veranstaltungen
    |-Publikationen
   [+]Awards ()
   [+]Stellenangebote
    |-TILDA
   [+]Software ()
   [+]Interna


 Diese Seite optimiert für Ausdruck

[No english page available]

Methoden zur Parallelisierung von
statischen Algorithmen der digitalen
Bildverarbeitung und Mustererkennung

Projektmitglieder


Einführung

Bei der Algorithmenentwicklung und Programmierung von sequentiellen Rechnern ist es heute gelungen, eine weitestgehende Unabhängigkeit von der Zielhardware zu erreichen. Ein wesentlicher Grund hierfür ist die relativ einheitliche von-Neumann-Architektur der meisten sequentiellen Rechner.

Die Eigenschaften eines Parallelrechners hingegen werden, außer von dem Aufbau der einzelnen Rechnerknoten, ganz wesentlich von der Struktur des sie verbindenden Netzwerks geprägt. Für diese oft als Graphen aufgefaßten Verbindungsnetzwerke wird eine Vielzahl unterschiedlichster Varianten diskutiert und eingesetzt. In der Bildverarbeitung sind das z.B. de Bruijn-Graph, Torus oder Hypercube.

Die Parallelisierung eines Algorithmus kann daher in den meisten Fällen nicht unabhängig vom zugrundeliegenden Graphen des Zielrechners erfolgen. Vielmehr muß für eine effiziente Implementierung das Kommunikationsverhalten des Algorithmus möglichst gut an den Graphen angepaßt werden. Daraus ergeben sich erhebliche Probleme für die Portierung von parallelen Algorithmen und deren Implementierung.

Ziel dieses Forschungsprojektes ist es, Methoden bereitzustellen, die eine hardwareunabhängige Implementierung von parallelen Algorithmen er mög li ch en. Da zu sol len zum einen Abbildungen des gewünschten Kommunikationsgraphen auf gegebene Hardwarearchitekturen geschaffen werden. Im vergangenen Projektzeitraum wurden Einbettungen von Gittern, Hypercubes und einer weiten Klasse von Produktgraphen in de Bruijn-Graphen entwickelt, die bestehende Verfahren in den Gütekriterien Dilation und Kongestion deutlich verbessern [1].

Darüber hinaus werden neuartige Kommunikationsnetzwerke für Parallelrechner dergestalt entwickelt, daß auf sie mög lichst eine Vielzahl der in der digitalen Bildverarbeitung und Mustererkennung vorkommenden Algorithmen gut abgebildet werden können. Im Mittelpunkt des Interesses stehen hier der Xtree bzw. Pyramidale Strukturen, für die derzeit keine effizienten Einbettungen in de Bruijn Graphen oder verwandte Netzwerke bekannt sind. Im weiteren Verlauf des Projektes soll der in Abbildung 1 gezeigte Shuffle-Ring Graph hinsichtlich seiner Eignung als Kommunikationsnetzwerk für die digitale Bildverarbeitung und Mustererkennung untersucht werden [2]. Bei weitgehender Übertragbarkeit der bekannten Einbettungen in den de Bruijn Graphen kann zusätzlich der Xtree mit konstanter Dilation in den Shuffle-Ring Graphen eingebettet werden (Siehe Abbildung 2).

Publikationen

  1. [andrnoeschrWG94]
    T. Andreae, M. Nölle und G. Schreiber. Cartesian Products of Graphs as Spanning Subgraphs of de Bruijn Graphs. In Proceedings of the 20. Workshop on Graph-Theoretic Concepts in Computer Science (WG94). Lecture Notes in Computer Science, Springer, Juni 1994.
    2. [bienoeschrIWPIA95] A. Bieniek, M. Nölle und G. Schreiber. A regular N-node bounded degree network for sorting n*n items with optimal speedup. In 4. International Workshop on Parallel Image Analysis, Lyon, Dezember 1995.