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 |
VerfasserIn: | Gamkrelidze, Alexander Burch, Thomas |
Sprache: | Englisch |
Erscheinungsjahr: | 1998 |
Kontrollierte Schlagwörter: | Technische Informatik |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Forschungsbericht (Report zu Forschungsprojekten) |
Abstract: | 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 |
Datum des Eintrags: | 23-Jun-2005 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Informatik |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
fb14-98-04.pdf | 1 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.