sorting - pseudocódigo - radix sort tiempo de ejecucion

qué tan rápido es thrust:: sort y cuál es la implementación más rápida de ordenar radix

Question

Soy un novato en la programación de GPU. Recientemente, estoy tratando de implementar el algoritmo de construcción gpu bvh basado en un tutorial: http://devblogs.nvidia.com/parallelforall/thinking-parallel-part-iii-tree-construction-gpu/ . En el primer paso de este algoritmo, el código Morton (unsigned int) de cada primitiva se calcula y ordena. El tutorial proporciona un costo de tiempo de referencia de la computación y clasificación del código morton para objetos de 12K:

1. 0.02 ms, un hilo por objeto: calcula el cuadro delimitador y asigna el código Morton.
2. 0.18 ms, orden de radix paralela: ordena los objetos de acuerdo con sus códigos Morton. ...

En mi implementación, el primer paso cuesta 0.1ms y el paso de clasificación cuesta 1.8ms. Estoy usando empuje para hacer la clasificación. Entonces, ¿cuál es la implementación más rápida de ordenación de radix en la GPU?

Estoy usando una GPU Geforce Titan que debería ser más rápida que la Geforce GTX690 utilizada por el autor del tutorial. Este es mi código de prueba para ordenar, cuesta alrededor de 1.5ms incluso cuando el tamaño es 10.

void testSort()
{
    int sz = 10;
    thrust::host_vector<unsigned int> h_keys(sz);
    for(int i=0; i<sz; i++)
        h_keys[i] = rand();
    thrust::device_ptr<unsigned int> keys = thrust::device_malloc<unsigned int>(sz);
    thrust::copy(h_keys.begin(),h_keys.end(),keys);
    cudaEvent_t estart, estop;
    cudaEventCreate( &estart );
    cudaEventCreate( &estop );
    cudaEventRecord( estart, 0 );
    thrust::stable_sort(keys,keys+sz);
    cudaEventRecord( estop, 0 ) ;
    cudaEventSynchronize( estop );
    float elapsedTime;
    cudaEventElapsedTime( &elapsedTime,
        estart, estop ) ;
    printf( "Time to sort: %3.1f ms/n", elapsedTime );
    cudaEventDestroy( estart ) ;
    cudaEventDestroy( estop ) ;
}

Answer 1

Hay una implementación de ordenamiento de Radix para GPGPU mediante back40computing . Proporcionan un cuadro de comparación de rendimiento con el que afirman que su implementación es la más rápida.