A parametrized sorting System for a large set of k-bit elements

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]).