Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25799
Titel: A parametrized sorting System for a large set of k-bit elements
Verfasser: Gamkrelidze, Alexander
Burch, Thomas
Sprache: Englisch
Erscheinungsjahr: 1998
SWD-Schlagwörter: Technische Informatik
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: In this paper, we describe a parametrized sorting system for a large set of k-bit elements. The structure of the system is independent from the problem size (the number of elements to be sorted) and the type of the sorting set (for example, a set of k-bit numbers, an alphabetical list of k-bit words etc.), as well as from the ordering relation defined on the set of the elements (such as ascending or descending order of k-bit numbers, or a specific order of alphabetical words). The general structure of the underlying parallel network is based on the n- dimensional hypercube. The node circuit construction defines the type of the sorting elements, thus defining the semantics of the system. The structure of the circuit implements the Columnsort algorithm introduced by Leighton in [Lei85]. By changing only one subcircuit of the size O(k) in the node, we can define different ordering relations of the sorted elements. The system is based on specific VLSI chips that were developed in [Gam96] with the CAD system Cadic [Bur95], that has been developed in the project B1 "VLSI design systems and parallelity" under guidance of Prof. G. Hotz. The result is a fast system that sorts the sets of up to 2^28 64-bit numbers. The maximal sorting time is less than 43.6 seconds that is better than some of the fastest software realizations implemented at 32-processor Paragon ([Hard96]), Cray Y-MP ([ZagBlel91]) and MasPar MP-1 ([BrockWan97]).
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-3528
hdl:20.500.11880/25855
http://dx.doi.org/10.22028/D291-25799
Schriftenreihe: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Band: 1998/04
SciDok-Publikation: 23-Jun-2005
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
fb14-98-04.pdf1 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.