clfRadixSort.hh

// C++ class for sorting integer list in OpenCL
// copyright Philippe Helluy, University de Strasbourg, France, 2011, helluy@math.unistra.fr
// licensed under the GNU Lesser General Public License see http://www.gnu.org/copyleft/lesser.html
// if you find this software usefull you can cite the following work in your reports or articles:
// Philippe HELLUY, A portable implementation of the radix sort algorithm in OpenCL, HAL 2011.
// The algorithm is the radix sort algorithm
// Marcho Zagha and Guy E. Blelloch. "Radix Sort For Vector Multiprocessor."
// in: Conference on High Performance Networking and Computing, pp. 712-721, 1991.
// each integer is made of _TOTALBITS bits. The radix is made of _BITS bits. The sort is made of
// several passes, each consisting in sorting against a group of bits corresponding to the radix.
// _TOTALBITS/_BITS passes are needed.
// The sorting parameters can be changed in "clfRadixSortParam.hpp"
// compilation for Mac:
//g++ clfRadixSort.cpp clfRadixSortMain.cpp -framework opencl -Wall
// compilation for Linux:
//g++ clfRadixSort.cpp clfRadixSortMain.cpp -lOpenCL -Wall

#ifndef _CLFRADIXSORT_HH_
#define _CLFRADIXSORT_HH_

#include <OpenCLFramework/Algorithm/clfAlgorithm.hh>

namespace BIAS {
  class BIASOpenCLFramework_EXPORT clfRadixSort : public clfAlgorithm {
  
  public:
    clfRadixSort(clfContext *ctx = NULL, bool sharedGL = false, unsigned int device = 0);
    
    virtual ~clfRadixSort();
    
    void SetData(int num, float *data, int scale = 1);

    void SetData(int num, clfBuffer *data);

    // this function allows to change the size of the sorted vector
    void Resize(int nn);
  
    // this function treats the array d_Keys on the GPU
    // and return the sorting permutation in the array d_Permut
    void Sort();

    void ApplyPermutation(clfBuffer *in, clfBuffer *out, int elemsize, int numElems, bool hightolow = false);
  
    // get the data from the GPU (for debugging)
    void RecupGPU(void);
  
    // put the data on the host in the GPU
    void Host2GPU(void);
  
    // check that the sort is successfull (for debugging)
    void Check(void);
  
    // transpose the list for faster memeory access
    // (improve coalescence)
    void Transpose(int nbrow,int nbcol);
  
    // compute the histograms for one pass
    void Histogram(unsigned int pass);
    // scan the histograms
    void ScanHistogram(void);
    // scan the histograms
    void Reorder(unsigned int pass);
    
    unsigned int *GetPermutation(unsigned int num = 0);

  
//    unsigned int h_Histograms[_RADIX * _GROUPS * _ITEMS]; // histograms on the cpu
    unsigned int h_Histograms[5 * 16 * 16]; // histograms on the cpu
    clfBuffer* d_Histograms;                   // histograms on the GPU
  
    // sum of the local histograms
//    unsigned int h_globsum[_HISTOSPLIT];
    unsigned int h_globsum[512];
    clfBuffer* d_globsum;
    clfBuffer* d_temp;  // in case where the sum is not needed
  
    // list of keys
    unsigned int nkeys; // actual number of keys
    unsigned int nkeys_rounded; // next multiple of _ITEMS*_GROUPS
    unsigned int h_checkKeys[(1<<23)]; // a copy for check
    unsigned int h_Keys[(1<<23)];
    clfBuffer* d_inKeys;
    clfBuffer* d_outKeys;
  
    // permutation
    unsigned int h_Permut[(1<<23)];
    unsigned int h_initialPermut[(1<<23)];
    clfBuffer* d_inPermut;
    clfBuffer* d_outPermut;
  
    // timers
    float histo_time,scan_time,reorder_time,sort_time,transpose_time;
  
  };
}

#endif