Sorting on defective VLSI-arrays

Josef G. Krammer, Ernst G. Bernard, Matthias Sauer, Josef A. Nossek

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

1 Zitat (Scopus)

Abstract

A method for adapting shortperiodic sorting algorithms to defective arrays is presented. The approach is based on nearest neighbor interconnections and thus requires no additional wiring and switches for bypassing defective cells. The algorithm is adapted by reindexing, i.e., by modifying the ordering of the sorted sequence (indexing scheme). An efficient strategy for determining an indexing scheme is presented. A worst case sorting time of O( N ) is proved for these sorters. Simulation results show thatthe typical sorting time is only slightly higher than O(√N) and thus all advantages of the two-dimensional sorter are preserved. A sorting network implementing the adapted algorithm has the same topology as that for the algorithm in the fault-free case. The only modification is the programmability of the exchange operation of the cells. A simple and efficient method for testing the array is presented.

OriginalspracheEnglisch
Seiten (von - bis)33-48
Seitenumfang16
FachzeitschriftIntegration, the VLSI Journal
Jahrgang12
Ausgabenummer1
DOIs
PublikationsstatusVeröffentlicht - Nov. 1991

Fingerprint

Untersuchen Sie die Forschungsthemen von „Sorting on defective VLSI-arrays“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren