[Paraview-developers] MPI Parallel Sorting

[burlen]

Hi Utkarsh,

One way to do it would be: 

Assume the resulting sorted array were to be distributed equally amongst 
the processes in process order. Each process sorts his portion of the 
input array locally, and instantiates a custom stack type containing the 
sorted array where the "Top" operation returns the smallest value or 
TYPE_MAX when his stack is empty. For each element of the resulting 
sorted array MPI_Allreduce is called with the operation type set to 
MPI_MINLOC, and with each processes providing the Top of it's local 
stack (smallest local elem. or TYPE_MAX).  The result of the reduction 
is the next smallest value in the sorted array, and the rank of the 
process who currently owns this value. The process who currently owns 
the next smallest value Pops his stack, and the new owner places the 
value into his local result array.

For fun I coded up simple example, attached. There must be a better way.

Burlen

Utkarsh Ayachit wrote:
> Folks,
>
> I am looking at the long standing feature request to add support for
> sorting in the spreadsheet view. Our use case is that we have a large
> array is distributed among N processes.
> We want to end up with that array sorted but still distributed among
> all processes. Most implementations I am looking at end up creating
> one large sorted array on one of nodes. Does anyone know any approach
> that avoids this generation of a large array on the root node?
>
> Utkarsh
> _______________________________________________
> Paraview-developers mailing list
> Paraview-developers at paraview.org
> http://public.kitware.com/mailman/listinfo/paraview-developers
>   

-------------- next part --------------
A non-text attachment was scrubbed...
Name: DistSort.cpp
Type: text/x-c++src
Size: 4271 bytes
Desc: not available
URL: <http://public.kitware.com/pipermail/paraview-developers/attachments/20100809/37412428/attachment-0001.cpp>