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/609/


Massively parallel pattern recognition with link failures

Löwe, Jan-Thomas ; Kutrib, Martin


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

Bookmark bei Connotea Bookmark bei del.icio.us
Freie Schlagwörter (Deutsch): parallel pattern recognition
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 ; 0003 / 2000
Sprache: Englisch
Erstellungsjahr: 2000
Publikationsdatum: 08.02.2001
Kurzfassung auf Englisch: The capabilities of reliable computations in linear cellular arrays with communication failures 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 of their communication links they store their working state locally such that it becomes visible to the neighbors. A defective cell is not able to receive information via one of its both links to adjacent cells. The self-diagnosis is run once before the actual computation. Subsequently no more failures may occur in order to obtain a valid computation.


We center our attention to patterns that are recognizable very fast, i.e. in real-time. It is well-known that real-time one-way arrays are strictly less powerful than real-time two-way arrays, but there is only little known on the range between these two devices. Here it is shown that the sets of patterns reliably recognizable by real-time arrays with link failures are strictly in between the sets of (intact) one-way and (intact) two-way arrays. Hence, the failures cannot be compensated in general but, on the other hand, do not decrease the computing power to that one of one-way arrays.



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