c++ - usadas - tecnicas de recoleccion de datos pdf

Diseño eficiente y reducción de datos 2D virtuales(resumen)

Question

Uso C ++ y CUDA / C y quiero escribir el código para un problema específico y me encontré con un problema de reducción bastante complicado.

Mi experiencia en programación paralela no es insignificante, pero es bastante limitada y no puedo evitar totalmente la especificidad de este problema. Dudo que haya una manera conveniente o incluso "fácil" de manejar los problemas que estoy enfrentando, pero quizás estoy equivocado. Si hay algún recurso (es decir, artículos, libros, enlaces web, ...) o palabras clave que cubran este o problemas similares, háganmelo saber.

Traté de generalizar todo el caso lo mejor posible y mantenerlo abstracto en lugar de publicar demasiado código.

El diseño ...

Tengo un sistema de N elementos iniciales y N elementos de resultado. (Usaré N = 8 por ejemplo, pero N puede tener un valor integral superior a tres).

static size_t const N = 8;
double init_values[N], result[N];

Necesito calcular casi todas (no todas temo) la permutación única de los valores init sin autointerferencia.

Esto significa el cálculo f(init_values[0],init_values[1]) , f(init_values[0],init_values[2]) , ..., f(init_values[0],init_values[N-1]) , f(init_values[1],init_values[2]) , ..., f(init_values[1],init_values[N-1]) , ... y así sucesivamente.

Esta es, de hecho, una matriz triangular virtual que tiene la forma que se ve en la siguiente ilustración.

 P     0    1    2    3    4    5    6    7
   |---------------------------------------
  0|   x 
   |
  1|   0    x
   |
  2|   1    2    x 
   |
  3|   3    4    5    x
   |
  4|   6    7    8    9    x
   |
  5|  10   11   12   13   14    x
   |
  6|  15   16   17   18   19   20    x
   |
  7|  21   22   23   24   25   26   27    x

Cada elemento es una función de los elementos de columna y fila respectivos en init_values .

P[i] (= P[row(i)][col(i]) = f(init_values[col(i)], init_values[row(i)])

es decir

P[11] (= P[5][1]) = f(init_values[1], init_values[5])

Hay (N*NN)/2 = 28 combinaciones posibles, únicas (Nota: P[1][5]==P[5][1] , por lo que solo tenemos una matriz triangular inferior (o superior) usando el ejemplo N = 8 .

El problema básico

La matriz de resultados se calcula a partir de P como una suma de los elementos de la fila menos la suma de los elementos de columna respectivos. Por ejemplo, el resultado en la posición 3 se calculará como una suma de la fila 3 menos la suma de la columna tres.

result[3] = (P[3]+P[4]+P[5]) - (P[9]+P[13]+P[18]+P[24])
result[3] = sum_elements_row(3) - sum_elements_column(3)

Traté de ilustrarlo en una imagen con N = 4.

Como consecuencia, lo siguiente es cierto:

• N-1 operaciones N-1 (posibles escrituras concurrentes) en cada result[i]
• result[i] tendrá N-(i+1) escrituras de restas y adiciones i
• Saliente de cada P[i][j] habrá una resta a r[j] y una adición a r[i]

Aquí es donde entran en juego los principales problemas:

• Usar un hilo para calcular cada P y actualizar el resultado directamente dará como resultado que varios núcleos intenten escribir en la misma ubicación de resultados (N-1 hilos cada uno).
• Por otro lado, almacenar toda la matriz P para un paso de reducción posterior es muy costoso en términos de consumo de memoria y, por lo tanto, imposible para sistemas muy grandes.

La idea de tener un vector de resultados compartido y único para cada bloque de hilos también es imposible. (N de 50k crea 2.5 billones de elementos P y por lo tanto [suponiendo un número máximo de 1024 hilos por bloque] un número mínimo de 2.4 millones de bloques que consumen más de 900GiB de memoria si cada bloque tiene su propia matriz de resultados con 50k elementos dobles).

Creo que podría manejar la reducción para un comportamiento más estático, pero este problema es bastante dinámico en términos de potencial de escritura de memoria simultánea. (¿O es posible manejarlo mediante algún tipo de reducción "básica"?)

Agregando algunas complicaciones ...

Desafortunadamente, dependiendo de la entrada (usuario arbitrario), que es independiente de los valores iniciales, algunos elementos de P deben omitirse. Supongamos que necesitamos omitir las permutaciones P [6], P [14] y P [18]. Por lo tanto, nos quedan 24 combinaciones, que deben calcularse.

¿Cómo decirle al kernel qué valores se deben omitir? Se me ocurrieron tres enfoques, cada uno con desventajas notables si N es muy grande (como varios diez miles de elementos).

1. Almacenar todas las combinaciones ...

... con sus respectivas struct combo { size_t row,col; }; índice de fila y columna struct combo { size_t row,col; }; struct combo { size_t row,col; }; , que deben calcularse en un vector<combo> y operar en este vector. (utilizado por la implementación actual)

std::vector<combo> elements;
// somehow fill
size_t const M = elements.size();
for (size_t i=0; i<M; ++i)
{
    // do the necessary computations using elements[i].row and elements[i].col  
}

Esta solución consume consumir mucha memoria ya que solo "varios" (incluso pueden ser diez mil elementos pero eso no contrasta mucho con varios miles de millones en total) pero evita

• cálculos de indexación
• hallazgo de elementos eliminados

para cada elemento de P que es la desventaja del segundo enfoque.

2. Operar en todos los elementos de P y encontrar elementos eliminados

Si quiero operar en cada elemento de P y evitar bucles anidados (que no pude reproducir muy bien en cuda) tengo que hacer algo como esto:

size_t M = (N*N-N)/2;
for (size_t i=0; i<M; ++i)
{
   // calculate row indices from `i`
   double tmp = sqrt(8.0*double(i+1))/2.0 + 0.5;
   double row_d = floor(tmp);
   size_t current_row = size_t(row_d);
   size_t current_col = size_t(floor(row_d*(ict-row_d)-0.5));
   // check whether the current combo of row and col is not to be removed
   if (!removes[current_row].exists(current_col))
   {
     // do the necessary computations using current_row and current_col
   }
}

El vector removes es muy pequeño en contraste con el vector de elements en el primer ejemplo, pero los cálculos adicionales para obtener current_row , current_col y if-branch son muy ineficientes. (Recuerde que todavía estamos hablando de miles de millones de evaluaciones).

3. Operar en todos los elementos de P y eliminar elementos después

Otra idea que tuve fue calcular todas las combinaciones válidas e inválidas de forma independiente. Pero desafortunadamente, debido a errores de suma, la siguiente afirmación es verdadera:

calc_non_skipped() != calc_all() - calc_skipped()

¿Existe una forma conveniente, conocida y de alto rendimiento para obtener los resultados deseados a partir de los valores iniciales?

Sé que esta pregunta es bastante complicada y quizás de relevancia limitada. Sin embargo, espero que algunas respuestas iluminadoras me ayuden a resolver mis problemas.

La implementación actual

Actualmente esto se implementa como código de CPU con OpenMP. Primero configuré un vector de los combo antes mencionados que almacena cada P que necesita ser computado y lo pasa a un bucle for paralelo. Cada hilo se proporciona con un vector de resultado privado y una sección crítica al final de la región paralela se usa para una suma adecuada.

Answer 1

Primero, me quedé perplejo por un momento por qué (N**2 - N)/2 arrojó 27 para N = 7 ... pero para los índices 0-7, N = 8, y hay 28 elementos en P. No debería Intente responder preguntas como esta tan tarde en el día. :-)

Pero a una posible solución: ¿ necesita mantener la matriz P para cualquier otro propósito? Si no, creo que puede obtener el resultado que desea con solo dos matrices intermedias, cada una de longitud N: una para la suma de las filas y otra para la suma de las columnas.

Aquí hay un ejemplo rápido y sucio de lo que creo que estás tratando de hacer (subrutina direct_approach() ) y cómo lograr el mismo resultado usando las matrices intermedias (subroutine refined_approach() ):

#include <cstdlib>
#include <cstdio>

const int N = 7;
const float input_values[N] = { 3.0F, 5.0F, 7.0F, 11.0F, 13.0F, 17.0F, 23.0F };
float P[N][N];      // Yes, I''m wasting half the array.  This way I don''t have to fuss with mapping the indices.
float result1[N] = { 0.0F, 0.0F, 0.0F, 0.0F, 0.0F, 0.0F, 0.0F };
float result2[N] = { 0.0F, 0.0F, 0.0F, 0.0F, 0.0F, 0.0F, 0.0F };

float f(float arg1, float arg2)
{
    // Arbitrary computation
    return (arg1 * arg2);
}

float compute_result(int index)
{
    float row_sum = 0.0F;
    float col_sum = 0.0F;
    int row;
    int col;

    // Compute the row sum
    for (col = (index + 1); col < N; col++)
    {
        row_sum += P[index][col];
    }

    // Compute the column sum
    for (row = 0; row < index; row++)
    {
        col_sum += P[row][index];
    }

    return (row_sum - col_sum);
}

void direct_approach()
{
    int row;
    int col;

    for (row = 0; row < N; row++)
    {
        for (col = (row + 1); col < N; col++)
        {
            P[row][col] = f(input_values[row], input_values[col]);
        }
    }

    int index;

    for (index = 0; index < N; index++)
    {
        result1[index] = compute_result(index);
    }
}

void refined_approach()
{
    float row_sums[N];
    float col_sums[N];
    int index;

    // Initialize intermediate arrays
    for (index = 0; index < N; index++)
    {
        row_sums[index] = 0.0F;
        col_sums[index] = 0.0F;
    }

    // Compute the row and column sums
    // This can be parallelized by computing row and column sums
    //  independently, instead of in nested loops.
    int row;
    int col;

    for (row = 0; row < N; row++)
    {
        for (col = (row + 1); col < N; col++)
        {
            float computed = f(input_values[row], input_values[col]);
            row_sums[row] += computed;
            col_sums[col] += computed;
        }
    }

    // Compute the result
    for (index = 0; index < N; index++)
    {
        result2[index] = row_sums[index] - col_sums[index];
    }
}

void print_result(int n, float * result)
{
    int index;

    for (index = 0; index < n; index++)
    {
        printf("  [%d]=%f/n", index, result[index]);
    }
}

int main(int argc, char * * argv)
{
    printf("Data reduction test/n");

    direct_approach();

    printf("Result 1:/n");
    print_result(N, result1);

    refined_approach();

    printf("Result 2:/n");
    print_result(N, result2);

    return (0);
}

Paralelizar el cálculo no es tan fácil, ya que cada valor intermedio es una función de la mayoría de las entradas. Puede calcular las sumas individualmente, pero eso significaría realizar f (...) varias veces. La mejor sugerencia que se me ocurre para valores muy grandes de N es usar más matrices intermedias, calcular subconjuntos de los resultados y luego sumar las matrices parciales para obtener las sumas finales. Tendría que pensar en eso cuando no estoy tan cansado.

Para lidiar con el problema de omisión: si se trata simplemente de "no usar los valores de entrada x, y y z", puede almacenar x, y y z en una matriz do_not_use y verificar esos valores cuando se repite para calcular las sumas Si los valores que se omiten son alguna función de fila y columna, puede almacenarlos como pares y verificar los pares.

Espero que esto te de ideas para tu solución!

Actualización, ahora que estoy despierto: lidiar con "omisión" depende mucho de qué datos se deben omitir. Otra posibilidad para el primer caso - "no use valores de entrada x, y, y z" - una solución mucho más rápida para conjuntos de datos grandes sería agregar un nivel de indirección: crear otro conjunto más, este de índices enteros, y almacenar solo los índices de las buenas entradas. Por ejemplo, si los datos no válidos están en las entradas 2 y 5, la matriz válida sería:

int valid_indices[] = { 0, 1, 3, 4, 6 };

Interacciona con la matriz valid_indices , y utiliza esos índices para recuperar los datos de tu matriz de entrada para calcular el resultado. En la otra pata, si los valores a omitir dependen de ambos índices de la matriz P, no veo cómo se puede evitar algún tipo de búsqueda.

Regresar a la paralelización. Pase lo que pase, tratará con (N ** 2 - N) / 2 cálculos de f (). Una posibilidad es simplemente aceptar que habrá contención para las matrices de suma, lo que no sería un gran problema si el cálculo de f () lleva mucho más tiempo que las dos adiciones. Cuando llegue a un número muy grande de rutas paralelas, la disputa volverá a ser un problema, pero debería haber un "punto óptimo" que equilibre el número de rutas paralelas con el tiempo requerido para calcular f ().

Si la contención sigue siendo un problema, puede dividir el problema de varias maneras. Una forma es calcular una fila o columna a la vez: para una fila a la vez, cada suma de columna se puede calcular de manera independiente y se puede mantener un total acumulado para cada suma de fila.

Otro enfoque sería dividir el espacio de datos y, por lo tanto, el cálculo en subconjuntos, donde cada subconjunto tiene sus propias matrices de suma de filas y columnas. Después de calcular cada bloque, los conjuntos independientes se pueden sumar para generar los valores que necesita para calcular el resultado.

Answer 2

Esta probablemente sea una de esas respuestas ingenuas e inútiles, pero también podría ser útil. Siéntete libre de decirme que estoy total y completamente equivocado y que he entendido mal todo el asunto.

¡Así que, aquí vamos!

El problema básico

Me parece que puede definir su función de resultado de forma un poco diferente y que al menos eliminará algo de sus valores intermedios. Supongamos que su matriz P es triangular inferior. Si (virtualmente) llena el triángulo superior con el negativo de los valores más bajos (y la diagonal principal con todos los ceros), entonces puede redefinir cada elemento de su resultado como la suma de una sola fila: (aquí se muestra para N = 4 , y donde -i significa el valor negativo del valor en la celda marcada como i )

 P     0    1    2    3 
   |--------------------
  0|   x   -0   -1   -3
   |
  1|   0    x   -2   -4
   |
  2|   1    2    x   -5
   |
  3|   3    4    5    x

Si lanza subprocesos independientes (que ejecutan el mismo kernel) para calcular la suma de cada fila de esta matriz, cada subproceso escribirá un único elemento de resultado. Parece que el tamaño de su problema es lo suficientemente grande como para saturar sus hilos de hardware y mantenerlos ocupados.

La advertencia, por supuesto, es que calcularás cada f(x, y) dos veces. No sé qué tan caro es, o cuánto le costaba antes la contención de la memoria, así que no puedo juzgar si vale la pena o no hacer una transacción. Pero a menos que f sea ​​realmente muy caro, creo que podría ser.

Saltar valores

Menciona que puede tener decenas de miles de elementos de la matriz P que debe ignorar en sus cálculos ( omitirlos de manera efectiva).

Para trabajar con el esquema que he propuesto más arriba, creo que debes guardar los elementos omitidos como pares (row, col) y también debes agregar la transpuesta de cada par de coordenadas (para que tengas el doble de la cantidad omitida valores.) Así que su lista de saltos de ejemplo de P[6], P[14] and P[18] convierte en P(4,0), P(5,4), P(6,3) que luego se convierte en P(4,0), P(5,4), P(6,3), P(0,4), P(4,5), P(3,6) .

Luego ordena esta lista, primero basada en la fila y luego en la columna. Esto hace que nuestra lista sea P(0,4), P(3,6), P(4,0), P(4,5), P(5,4), P(6,3) .

Si cada fila de su matriz P virtual es procesada por un hilo (o una sola instancia de su kernel o lo que sea), puede pasarle los valores que necesita para omitir. Personalmente, almacenaba todo esto en una gran matriz 1D y simplemente pasaba el primer y último índice que cada hilo debería mirar (tampoco almacenaba los índices de fila en la matriz final que pasé, ya que puede se deduce implícitamente, pero creo que es obvio). En el ejemplo anterior, para N = 8, los pares de inicio y final pasados ​​a cada hilo serán: (tenga en cuenta que el final es uno más allá del valor final necesario para ser procesado, solo como STL, por lo que una lista vacía se denota por begin == end)

Thread 0: 0..1
Thread 1: 1..1 (or 0..0 or whatever)
Thread 2: 1..1
Thread 3: 1..2
Thread 4: 2..4
Thread 5: 4..5
Thread 6: 5..6
Thread 7: 6..6

Ahora, cada hilo continúa calculando y sumando todos los valores intermedios en una fila. Mientras recorre los índices de las columnas, también avanza por esta lista de valores omitidos y omite cualquier número de columna que aparezca en la lista. Obviamente, esta es una operación eficiente y simple (ya que la lista también está ordenada por columna. Es como fusionarse).

Pseudo-Implementación

No conozco CUDA, pero tengo cierta experiencia trabajando con OpenCL, e imagino que las interfaces son similares (ya que el hardware al que apuntan es el mismo). Aquí hay una implementación del kernel que procesa una fila (es decir, calcula una entrada de result ) en pseudo-C ++:

double calc_one_result (
    unsigned my_id, unsigned N, double const init_values [],
    unsigned skip_indices [], unsigned skip_begin, unsigned skip_end
)
{
    double res = 0;
    for (unsigned col = 0; col < my_id; ++col)
        // "f" seems to take init_values[column] as its first arg
        res += f (init_values[col], init_values[my_id]);
    for (unsigned row = my_id + 1; row < N; ++row)
        res -= f (init_values[my_id], init_values[row]);
    // At this point, "res" is holding "result[my_id]",
    // including the values that should have been skipped

    unsigned i = skip_begin;
    // The second condition is to check whether we have reached the
    // middle of the virtual matrix or not
    for (; i < skip_end && skip_indices[i] < my_id; ++i)
    {
        unsigned col = skip_indices[i];
        res -= f (init_values[col], init_values[my_id]);
    }
    for (; i < skip_end; ++i)
    {
        unsigned row = skip_indices[i];
        res += f (init_values[my_id], init_values[row]);
    }

    return res;
}

Tenga en cuenta lo siguiente:

1. La semántica de init_values y la función f son como se describe en la pregunta.
2. Esta función calcula una entrada en la matriz de result ; específicamente, calcula el result[my_id] , por lo que debe iniciar N instancias de esto.
3. La única variable compartida en la que escribe es result[my_id] . Bueno, la función anterior no escribe nada, pero si la traduces a CUDA, imagino que tendrás que escribir sobre eso al final. Sin embargo, nadie más escribe a ese elemento particular de result , por lo que esta escritura no causará ninguna contención de la raza de datos.
4. Las dos matrices de entrada, init_values e skipped_indices se comparten entre todas las instancias en ejecución de esta función.
5. Todos los accesos a los datos son lineales y secuenciales, a excepción de los valores omitidos, que creo que son inevitables.

6. skipped_indices contiene una lista de índices que se deben omitir en cada fila. Sus contenidos y estructura son como se describió anteriormente, con una pequeña optimización. Como no era necesario, eliminé los números de las filas y dejé solo las columnas. El número de fila se pasará a la función como my_id todos modos y la porción de la matriz skipped_indices que se debe usar en cada invocación se determina usando skip_begin y skip_end .

   Para el ejemplo anterior, la matriz que se pasa a todas las invocaciones de calc_one_result se verá así: [4, 6, 0, 5, 4, 3] .

7. Como puede ver, aparte de los bucles, la única rama condicional en este código es skip_indices[i] < my_id en el tercer for-loop. Aunque creo que esto es inofensivo y totalmente predecible, incluso esta rama se puede evitar fácilmente en el código. Solo necesitamos pasar otro parámetro llamado skip_middle que nos diga dónde los elementos omitidos cruzan la diagonal principal (es decir, para la fila # my_id , el índice en skipped_indices[skip_middle] es el primero que es más grande que my_id ).

En conclusión

De ninguna manera soy un experto en CUDA y HPC. Pero si he entendido bien tu problema, creo que este método podría eliminar todas las contenciones para la memoria. Además, no creo que esto cause ningún (más) problemas de estabilidad numérica.

El costo de implementar esto es:

• Llamar f doble de veces en total (y mantener un registro de cuándo se llama para row < col para que pueda multiplicar el resultado por -1 ).
• Almacena el doble de elementos en la lista de valores omitidos . Dado que el tamaño de esta lista es de miles (¡y no de miles de millones!), No debería ser un gran problema.
• Ordenando la lista de valores omitidos; que de nuevo debido a su tamaño, no debería ser un problema.

( ACTUALIZACIÓN : se agregó la sección Pseudo-Implementación).