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.reducción segmentada con segmentos dispersos
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. Así que 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];
}
Dado que el número de grupos es extremadamente pequeño, el último paso se puede hacer en la CPU (Necesito esos valores en la CPU, de todos modos). El primer paso es en realidad solo una reducción segmentada, pero con los segmentos dispersos.
Así que 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 here.
Pero en este caso especial, obtuve una gran cantidad de datos por punto (9-10 flotantes, tal vez incluso dobles si fuera necesario), por lo que los algoritmos estándar utilizan un elemento de memoria compartida por hilo y un hilo por un punto puede causar problemas con respecto a los recursos por multiprocesador como memoria compartida o registros (vale, mucho más en la capacidad de cómputo 1.x que en 2.x, pero aún así).
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 utilizar 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.
Este es un patrón bastante común. Usando Thrust, primero deberías 'ordenar_por_clave' para juntar los datos en cada segmento, y luego' reducir_por_clave' para calcular la media y la covarianza de cada grupo. –