Partitioned parallel radix sort

Shin Jae Lee, Minsoo Jeon, Andrew Sohn, Dongseung Kim

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    2 Citations (Scopus)

    Abstract

    Load balanced parallel radix sort solved the load imbalance problem present in parallel radix sort. Redistributing the keys in each round of radix, each processor has exactly the same number of keys, thereby reducing the overall sorting time. Load balanced radix sort is currently known the fastest internal sorting method for distributed-memory multiprocessors. However, as the computation time is balanced, the communication time emerges as the bottleneck of the overall sorting performance due to key redistribution. We present in this report a new parallel radix sorter that solves the communication problem of balanced radix sort, called partitioned parallel radix sort. The new method reduces the communication time by eliminating the redistribution steps. The keys are first sorted in a top-down fashion (left-to-right as opposed to rightto-left) by using some most significant bits. Once the keys are localized to each processor, the rest of sorting is confined within each processor, hence eliminating the need for global redistribution of keys. It enables well balanced communication and computation across processors. The proposed method has been implemented in three different distributedmemory platforms, including IBM SP2, CRAY T3E, and PC Cluster. Experimental results with various key distributions indicate that partitioned parallel radix sort indeed shows significant improvements over balanced radix sort. IBM SP2 shows 13% to 30% improvement while Cray/SGIT3E does 20% to 100% in execution time. PC cluster shows over 2. 5 fold improvement in execution time.

    Original languageEnglish
    Title of host publicationHigh Performance Computing - 3rd International Symposium, ISHPC 2000, Proceedings
    EditorsMateo Valero, Kazuki Joe, Masaru Kitsuregawa, Hidehiko Tanaka
    PublisherSpringer Verlag
    Pages160-171
    Number of pages12
    ISBN (Print)9783540411284
    DOIs
    Publication statusPublished - 2000
    Event3rd International Symposium on High Performance Computing, ISHPC 2000 - Tokyo, Japan
    Duration: 2000 Oct 162000 Oct 18

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume1940
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other3rd International Symposium on High Performance Computing, ISHPC 2000
    Country/TerritoryJapan
    CityTokyo
    Period00/10/1600/10/18

    Bibliographical note

    Publisher Copyright:
    © Springer-Verlag Berlin Heidelberg 2000.

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science

    Fingerprint

    Dive into the research topics of 'Partitioned parallel radix sort'. Together they form a unique fingerprint.

    Cite this