Automatically assigned DDC number: 00435

Manually assigned DDC number: 00435

Number of references: 4

Title: Efficient Oblivious Parallel Sorting on the MasPar MP-1

Author:

Author:

Author:

Subject: Klaus Brockmann,Heinz Nixdorf,Rolf Wanka Efficient Oblivious Parallel Sorting on the MasPar MP-1

Description: We address the problem of sorting a large number N of keys on a MasPar MP-1 parallel SIMD machine of moderate size P where the processing elements (PEs) are interconnected as a toroidal mesh and have 16KB local storage each. We present a comparative study of implementations of the following deterministic oblivious sorting methods: Bitonic Sort, Odd-Even Merge Sort, and FastSort. We successfully use the guarded split&merge operation introduced by Ršub. The experiments and investigations in a simple, parameterized, analytical model show that, with this operation, from a certain ratio N=P upwards both Odd-Even Merge Sort and FastSort become faster on average than the up to the present fastest, sophisticated implementation of Bitonic Sort by Prins. Though it is not as efficient as Odd-Even Merge Sort, FastSort is to our knowledge the first method specially tailored to the mesh architecture that can be, when implemented, competitive on average with a mesh-adaptation of Bitonic Sort for larg...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1997-11-26

Pubyear: 1997

Format: ps

Identifier: http://citeseer.ist.psu.edu/149334.html

Source: ftp://ftp.uni-paderborn.de/doc/techreports/Informatik/tr-rsfb-96-031.ps.Z

Language: en

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="/40374.html"   Type="inproceedings"   CiteSeer_Book="ACM   Symposium   on   Parallel   Algorithms   and   Architectures"   CiteSeer_Volume=""   Title="A   Comparison   of   Sorting   Algorithms   for   the   Connection   Machine   {CM}-2,">

            <identifier   Org="ISBN:0070730202"   Paper_ID="/40374.html"   Extracted="0070730202"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0387986804"   Paper_ID="/40374.html"   Extracted="0387986804"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0792369572"   Paper_ID="/40374.html"   Extracted="0792369572"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0818643706"   Paper_ID="/40374.html"   Extracted="0818643706"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0818680679"   Paper_ID="/40374.html"   Extracted="0818680679"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0821804472"   Paper_ID="/40374.html"   Extracted="0821804472"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:089791483X"   Paper_ID="/40374.html"   Extracted="089791483X"   DDC="005.13/3"   Normalized_DDC="005133"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0897916719"   Paper_ID="/40374.html"   Extracted="0897916719"   />

            <identifier   Org="ISBN:0897917855"   Paper_ID="/40374.html"   Extracted="0897917855"   />

            <identifier   Org="ISBN:0897918096"   Paper_ID="/40374.html"   Extracted="0897918096"   DDC="004.35"   Normalized_DDC="00435"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:158488360X"   Paper_ID="/40374.html"   Extracted="158488360X"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:1584886234"   Paper_ID="/40374.html"   Extracted="1584886234"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540008837"   Paper_ID="/40374.html"   Extracted="3540008837"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540275800"   Paper_ID="/40374.html"   Extracted="3540275800"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:354041004X"   Paper_ID="/40374.html"   Extracted="354041004X"   DDC="004/.01/5118"   Normalized_DDC="004015118"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540419446"   Paper_ID="/40374.html"   Extracted="3540419446"   DDC="005.2/75"   Normalized_DDC="005275"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540552707"   Paper_ID="/40374.html"   Extracted="3540552707"   DDC="005.74"   Normalized_DDC="00574"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540603131"   Paper_ID="/40374.html"   Extracted="3540603131"   DDC="004/.01/5118"   Normalized_DDC="004015118"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540631380"   Paper_ID="/40374.html"   Extracted="3540631380"   DDC="005.2/75"   Normalized_DDC="005275"   Normalized_Weight="0.058823529411764705"   />

      </rec>

      <rec   ID="/402546.html"   Type="inproceedings"   CiteSeer_Book="SPDP   6th   IEEE   Symposium   on   Parallel   and   Distributed   Processing"   CiteSeer_Volume=""   Title="Sorting   Large   Data   Sets   on   a   Massively   Parallel   System,">

            <identifier   Org="ISBN:0769511538"   Paper_ID="/402546.html"   Extracted="0769511538"   />

            <identifier   Org="ISBN:0818664274"   Paper_ID="/402546.html"   Extracted="0818664274"   DDC="004.35"   Normalized_DDC="00435"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:0818676833"   Paper_ID="/402546.html"   Extracted="0818676833"   DDC="004.35"   Normalized_DDC="00435"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:0818677430"   Paper_ID="/402546.html"   Extracted="0818677430"   />

            <identifier   Org="ISBN:1581131240"   Paper_ID="/402546.html"   Extracted="1581131240"   />

            <identifier   Org="ISBN:1581134096"   Paper_ID="/402546.html"   Extracted="1581134096"   />

            <identifier   Org="ISBN:3540590420"   Paper_ID="/402546.html"   Extracted="3540590420"   DDC="004/.01/511"   Normalized_DDC="00401511"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:3540631380"   Paper_ID="/402546.html"   Extracted="3540631380"   DDC="005.2/75"   Normalized_DDC="005275"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:3540643591"   Paper_ID="/402546.html"   Extracted="3540643591"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.2"   />

      </rec>

      <rec   ID="/91922.html"   Type="inproceedings"   CiteSeer_Book="ACM   Symposium   on   Parallel   Algorithms   and   Architectures"   CiteSeer_Volume=""   Title="Implementations   of   Randomized   Sorting   on   Large   Parallel   Machines,">

            <identifier   Org="ISBN:0818643706"   Paper_ID="/91922.html"   Extracted="0818643706"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:0818675519"   Paper_ID="/91922.html"   Extracted="0818675519"   DDC="004.35"   Normalized_DDC="00435"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:0818676833"   Paper_ID="/91922.html"   Extracted="0818676833"   DDC="004.35"   Normalized_DDC="00435"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:0821804472"   Paper_ID="/91922.html"   Extracted="0821804472"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:089791483X"   Paper_ID="/91922.html"   Extracted="089791483X"   DDC="005.13/3"   Normalized_DDC="005133"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:3540590420"   Paper_ID="/91922.html"   Extracted="3540590420"   DDC="004/.01/511"   Normalized_DDC="00401511"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:3540631380"   Paper_ID="/91922.html"   Extracted="3540631380"   DDC="005.2/75"   Normalized_DDC="005275"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:3540643591"   Paper_ID="/91922.html"   Extracted="3540643591"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.125"   />

      </rec>

      <rec   ID="/95065.html"   Type="inproceedings"   CiteSeer_Book="European   Conference   on   Parallel   Processing"   CiteSeer_Volume=""   Title="Sorting   on   a   Massively   Parallel   System   Using   a   Library   of   Basic   Primitives:   Modeling   and   Experimental   Results,">

            <identifier   Org="ISBN:0818677430"   Paper_ID="/95065.html"   Extracted="0818677430"   />

            <identifier   Org="ISBN:1581131240"   Paper_ID="/95065.html"   Extracted="1581131240"   />

            <identifier   Org="ISBN:3540642307"   Paper_ID="/95065.html"   Extracted="3540642307"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="1.0"   />

      </rec>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="Efficient   Oblivious   Parallel   Sorting   on   the   MasPar   MP-1">

            <identifier   Org="ISBN:0818677430"   Paper_ID="SELF"   Extracted="0818677430"   />

            <identifier   Org="ISBN:0818677929"   Paper_ID="SELF"   Extracted="0818677929"   DDC="004.35"   Normalized_DDC="00435"   Normalized_Weight="0.5"   />

            <identifier   Org="ISBN:3540642307"   Paper_ID="SELF"   Extracted="3540642307"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.5"   />

      </rec>

</references_metadata>