Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Hinweis zum Urheberrecht

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URL: http://geb.uni-giessen.de/geb/volltexte/2001/607/


Fault tolerant parallel pattern recognition

Kutrib, Martin ; Löwe, Jan-Thomas


pdf-Format: Dokument 1.pdf (284 KB)
ps gepackt: class="frontdoor">Dokument1.gz (186 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
Universität Justus-Liebig-Universität Gießen
Institut: Institut für Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper (Forschungsbericht, Arbeitspapier)
Zeitschrift, Serie: IFIG Research Report ; 0001 / 2000
Sprache: Englisch
Erstellungsjahr: 2000
Publikationsdatum: 07.02.2001
Kurzfassung auf Englisch: The general capabilities of fault tolerant computations in one-way and two-way linear cellular arrays are investigated in terms of pattern recognition.


The defective processing elements (cells) that cause the misoperations are assumed to behave as follows. Dependent on the result of a self-diagnosis they store their working state locally such that it becomes visible to the neighbors. A non-working (defective) cell cannot modify information but is able to transmit it unchanged with unit speed. Arrays with static defects run the self-diagnosis once before the actual computation. Subsequently no more defects may occur.In case of dynamic defects cells may fail during the computation.
We center our attention to patterns that are recognizable very fast, i.e. in real-time, but almost all results can be generalized to arbitrary recognition times in a straightforward manner. It is shown that fault tolerant recognition capabilities of two-way arrays with static defects are characterizable by intact one-way arrays and that one-way arrays are fault tolerant per se.


For arrays with dynamic defects it is proved that the failures can be compensated as long as the number of adjacent defective cells is bounded. Arbitrary large defective regions (and thus fault tolerant computations) lead to a dramatically decrease of computing power. The recognizable patterns are those of a single processing element, the regular ones.



CR Subject Classification (1998): F.1, F.4.3, B.6.1, E.1, B.8.1, C.4