sorting - Clasificación de objetos con Thrust CUDA

cudpp

Question

¿Es posible ordenar objetos usando la biblioteca Thrust? Tengo la siguiente estructura:

struct OB{
  int N;
  Cls *C; //CLS is another struct.
}

¿Es posible usar el empuje para ordenar una matriz de OB de acuerdo con N? ¿Puedes dar un ejemplo simple sobre el uso del empuje para ordenar objetos? Si thrust no puede hacerlo, ¿hay alguna otra biblioteca CUDA que me permita hacerlo?

Answer 1

Hasta ahora no puedes ordenar objetos personalizados. Puede hacer una clasificación basada en claves pero no de objetos personalizados como la estructura que mencionó. Hay un par de otros algoritmos abiertos basados ​​en CUDA disponibles para hacer esto, pero eso también requiere alguna modificación, etc. para que funcionen para usted.

Answer 2

Todavía no he probado Thrust , pero hay una función de clasificación similar en CUDPP llamada cudppSort . No puede ordenar directamente las estructuras usando cudppSort, solo puede manejar enteros o flotantes.

Por lo tanto, una forma de ordenar la matriz de estructuras es ordenar las claves (de su estructura) y una matriz de valores de índice junto con ella. Más tarde, use la matriz de índice ordenada para mover las estructuras a sus ubicaciones ordenadas finales. He descrito cómo hacer esto para el algoritmo de compactación cudppCompact en una publicación de blog aquí . La técnica también debería ser similar para cudppSort.

Answer 3

Los documentos para thrust :: sort muestran que acepta un operador de comparación. Vea en su ejemplo cómo se definen y usan. No lo he probado, pero basado en el ejemplo, todo lo que necesitaría es una estructura que se parezca a esto:

struct OBCmp {
  __host__ __device__
  bool operator()(const OB& o1, const OB& o2) {
      return o1.N < o2.N;
  }
};

y luego solo invocar thrust::sort(obs.begin(), obs.end(), OBCmp()) .

Answer 4

Aunque puede ordenar los objetos mediante el uso de definiciones de estructuras especiales, usando una estructura como functor, hará un esfuerzo para cambiar el algoritmo de clasificación de radix-sort a merge-sort. La velocidad de radix-sort es notablemente más rápida que merge-sort. Por lo tanto, cuando use empuje, intente usar tipos enteros como valores clave como sea posible.

Puedo sugerirle que use la función "thrust :: sory_by_key (..)".

Debes cambiar tu estructura de AOS a estructura SOA.

struct OB{
  int N;
  Cls *C; //CLS is another struct.
}

a

struct OBs{
   int []Ns; -> thrust::device_vector<int> indices;
   Cls *C[]; -> thrust::device_vector<Cls> values;
}

Cuando clasifique los índices con sort_by_key, los valores ya estarán ordenados.

thrust::sort_by_key(indices.begin(), indices.end(), values.begin());

Answer 5

puede ordenar objetos sobrecargando el operador <. Por ejemplo:

__host__ __device__ struct Color{
  double blue, green, red;
  double distance;
  void dist()
  {
    distance = sqrt(blue*blue + green*green + red*red);
  }
};

__host__ __device__ bool operator<(const Color &lhs, const Color &rhs) 
{
   return lhs.distance < rhs.distance;
}

int main(void)
{
   thrust::device_vector<Color> cd;
   thrust::host_vector<Color> ch;
   for (int i = 0; i<6; i++)
   {
      Color c;
      c.blue = rand()*255;
      c.green = rand()*255;
      c.red = rand()*255;
      c.dist();
      ch.push_back(c);
   }
   cd = ch;
   thrust::sort(cd.begin(), cd.end());
   ch = cd;
   return 0;
}

los objetos serán ordenados después de la distancia.