cuda - premiere - reducción segmentada con segmentos dispersos
opencl vs cuda (1)
Tengo que resolver un problema bastante estándar en la GPU, pero soy bastante nuevo en la GPGPU práctica, así que estoy buscando ideas para abordar este problema.
Tengo muchos puntos en 3 espacios que se asignan a un número muy pequeño de grupos (cada punto pertenece a un grupo), específicamente 15 en este caso (nunca cambia). Ahora quiero calcular la media y la matriz de covarianza de todos los grupos. Entonces en la CPU es más o menos lo mismo que:
for each point p
{
mean[p.group] += p.pos;
covariance[p.group] += p.pos * p.pos;
++count[p.group];
}
for each group g
{
mean[g] /= count[g];
covariance[g] = covariance[g]/count[g] - mean[g]*mean[g];
}
Como el número de grupos es extremadamente pequeño, el último paso se puede hacer en la CPU (de todos modos, necesito esos valores en la CPU). El primer paso es en realidad solo una reducción segmentada, pero con los segmentos dispersos.
Entonces, la primera idea que se me ocurrió fue primero ordenar los puntos por sus grupos. Pensé en un tipo de clasificación simple usando atomic_inc para calcular los tamaños de los depósitos y los índices de reubicación por punto (¿obtuve una mejor idea para clasificar ?, los átomos no son la mejor idea). Después de eso, están ordenados por grupos y podría llegar a una adaptación de los algoritmos de escaneo segmentado presentados aquí .
Pero en este caso especial, obtuve una gran cantidad de datos por punto (9-10 flotantes, tal vez incluso dobles si surge la necesidad), por lo que los algoritmos estándar que utilizan un elemento de memoria compartida por hilo y un hilo por punto podrían causar problemas con respecto a los recursos por multiprocesador como memoria compartida o registros (Ok, mucho más en capacidad de cálculo 1.x que 2.x, pero aún).
Debido a la cantidad muy pequeña y constante de grupos, pensé que podría haber mejores enfoques. Quizás ya existan ideas adecuadas para estas propiedades específicas de un problema tan estándar. O tal vez mi enfoque general no es tan malo y tienes ideas para mejorar los pasos individuales, como un buen algoritmo de clasificación adecuado para un número muy pequeño de claves o algún algoritmo de reducción segmentado que minimice el uso compartido de memoria / registro.
Estoy buscando enfoques generales y no quiero usar bibliotecas externas. FWIW Estoy usando OpenCL, pero en realidad no debería importar ya que los conceptos generales de computación GPU no difieren realmente en los principales frameworks.
A pesar de que hay pocos grupos, no creo que pueda evitar la clasificación inicial en grupos, manteniendo el paso de reducción eficiente. Probablemente también desee realizar la ordenación completa, no solo ordenando índices, porque eso ayudará a mantener el acceso a la memoria eficiente en el paso de reducción.
Para clasificar, lee sobre las estrategias generales aquí:
http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter46.html
Para reducción (viejo pero bueno):
Para una implementación de ejemplo de reducción paralela:
http://developer.nvidia.com/cuda-cc-sdk-code-samples#reduction