Please use this identifier to cite or link to this item: doi:10.22028/D291-25799
Title: A parametrized sorting System for a large set of k-bit elements
Author(s): Gamkrelidze, Alexander
Burch, Thomas
Language: English
Year of Publication: 1998
SWD key words: Technische Informatik
DDC notations: 004 Computer science, internet
Publikation type: Report
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 to this record: urn:nbn:de:bsz:291-scidok-3528
Series name: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Series volume: 1998/04
Date of registration: 23-Jun-2005
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
fb14-98-04.pdf1 MBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.