es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

¿Cómo acelerar estas funciones?

11 Jun, 2023 Programación

Tengo dos funciones con las que estoy trabajando y estoy intentando hacerlas funcionar hasta 4 veces más rápido.

void get_each_fifth(const matrix_t *matrix, long results[RESULTS_LEN]) {
    for (int i = 0; i < matrix->rows; i++) {
        for (int j = 0; j < matrix->cols; j++) {
            int q = j % RESULTS_LEN;
            results[q] += MGET(matrix, i, j);
        }
    }
}

La función anterior necesitará ser optimizada para que sea 4 veces más rápida. En esta función, estoy encontrando la suma de enteros en función de su ubicación en la matriz. Los elementos en la columna 0, 5, 10, etc., van al primer elemento del array de resultados. Los elementos en la columna 1, 6, 11, etc. van a la segunda columna del array. Este patrón continúa para las columnas restantes. En resumen, los números en la columna i van al elemento i%5 del array de resultados.

long get_each(const matrix_t *matrix) {
    long sum = 0;
    for (int i = 0; i < matrix->rows; i++) {
        for (int j = 0; j < matrix->cols; j++) {
            sum += MGET(matrix, i, j);
        }
    }
    return sum;
}

Esta necesitará ser 2 veces más rápida; es decir, suma todos los elementos de la matriz y devuelve el resultado.

MGET y MSET están definidos como:

#define MGET(mat, i, j) ((mat)->data[((i)*((mat)->cols)) + (j)])
#define MSET(mat, i, j, x) ((mat)->data[((i)*((mat)->cols)) + (j)] = (x))

La estructura matrix_t está definida como:

typedef struct {
    long rows;
    long cols;
    int *data;
} matrix_t;

y se asigna con esta función:

void set_up_matrix(matrix_t *matrix, int rows, int cols) {
    if (matrix == NULL) {
        return;
    }
    matrix->rows = rows;
    matrix->cols = cols;
    matrix->data = malloc(sizeof(int) * rows * cols);
    srand(2021);
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            MSET(matrix, i, j, rand() % 100);
        }
    }
}

y RESULTS_LEN está definido como:

#define RESULTS_LEN 5

¡Cualquier ayuda sería apreciada!

Tags:  , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para optimizar la primera función get_each_fifth, podemos aprovechar el hecho de que los elementos de la matriz se están sumando en función de su ubicación. En lugar de recorrer todos los elementos de la matriz y utilizar el módulo para determinar qué elemento del array resultados actualizar, podemos recorrer directamente los elementos que corresponden a cada elemento del array resultados. Por ejemplo, para actualizar el primer elemento del array resultados, solo necesitamos recorrer los elementos en la columna 0, 5, 10, etc.

    void get_each_fifth_optimized(const matrix_t *matrix, long results[RESULTS_LEN]) {
    for (int j = 0; j < matrix->cols; j += RESULTS_LEN) {
        for (int i = 0; i < matrix->rows; i++) {
            results[j % RESULTS_LEN] += MGET(matrix, i, j);
        }
    }
}

    Esta nueva versión de la función recorre las columnas de la matriz que corresponden a cada elemento del array resultados. Dentro de cada bucle de columna, recorremos las filas y agregamos el elemento al elemento de resultado correspondiente.

    Para la segunda función get_each, la única optimización que podemos hacer es utilizar instrucciones SIMD para sumar varios elementos de una vez. Podemos utilizar las funciones _mm256_loadu_si256 y _mm256_add_epi32 de la biblioteca immintrin.h para sumar 8 enteros a la vez.

    long get_each_optimized(const matrix_t *matrix) {
    __m256i sum_vector = _mm256_setzero_si256();
    int* matrix_data = matrix->data;

    for (int i = 0; i < matrix->rows * matrix->cols; i += 8) {
        __m256i matrix_vector = _mm256_loadu_si256((__m256i *) (matrix_data + i));
        sum_vector = _mm256_add_epi32(sum_vector, matrix_vector);
    }

    int32_t sum_array[8];
    _mm256_storeu_si256((__m256i*)sum_array, sum_vector);
    long sum = sum_array[0] + sum_array[1] + sum_array[2] + sum_array[3] + sum_array[4] + sum_array[5] + sum_array[6] + sum_array[7];

    return sum;
}

    Esta versión de la función recorre los elementos de la matriz, cargando 8 enteros a la vez en un vector. Luego utilizamos _mm256_add_epi32 para agregar el vector a un vector de suma en ejecución. Después del bucle, almacenamos el vector de suma en un array de 8 enteros y los sumamos para obtener el resultado final.

    Tenga en cuenta que para utilizar estas optimizaciones, debemos asegurarnos de compilar con las banderas adecuadas, como -march=native para la segunda optimización.

Comments are closed.