0

SIMD 命令 (_mm256_add_pd、store、load など) を使用して、C で 2 次元行列の加算を最適化しようとしています。ただし、大幅な高速化はまったく見られません。いくつかのタイミングコードを使用すると、単純なソリューションの.8x-1.5xの範囲でスピードアップが見られます)。これが典型的なのかどうか疑問に思っていましたか？この場合、計算が非常に少ないように見えるため、メモリのボトルネックになる可能性があると考えていました。一度に4つの追加を行っているため、これにより速度が約4倍向上すると信じているため、ボトルネックが何であるかは完全にはわかりません.

私は何をしているのかを示すためにいくつかのコードを作成しました (並列 + SIMD と SIMD のみのテスト):

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#include <time.h>
#include <omp.h>
#include <string.h>

#if defined(_MSC_VER)
#include <intrin.h>
#elif defined(__GNUC__) && (defined(__x86_64__) || defined(__i386__))
#include <immintrin.h>
#include <x86intrin.h>
#endif

void add_matrix_naive (double **result, double **mat1, double **mat2, int rows, int cols) {
    int simdCols = cols / 4 * 4;
        if(simdCols > 0){
            for(unsigned int i = 0; i < rows; i++){
                for(unsigned int j = 0; j < simdCols; j += 4){
                    _mm256_storeu_pd(result[i] + j, _mm256_add_pd(
                        _mm256_loadu_pd(mat1[i] + j)
                        , _mm256_loadu_pd(mat2[i] + j)));
                }
            }
        }

        //Handle extra columns
        if(simdCols < cols){
            for(unsigned int i = 0; i < rows; i++){ 
                for(unsigned int j = simdCols; j < cols; j++){
                    result[i][j] = mat1[i][j] + mat2[i][j];
                }
            }
        }
}

void add_matrix(double **result, double **mat1, double **mat2, int rows, int cols) {
    int simdCols = cols / 4 * 4;
    #pragma omp parallel if (rows*cols >= 2000)
    {
        if(simdCols > 0){
            #pragma omp for collapse(2)
            for(unsigned int i = 0; i < rows; i++){
                for(unsigned int j = 0; j < simdCols; j += 4){
                    _mm256_storeu_pd(result[i] + j, _mm256_add_pd(
                        _mm256_loadu_pd(mat1[i] + j)
                        , _mm256_loadu_pd(mat2[i] + j)));
                }
            }
        }

        //Handle extra columns
        if(simdCols < cols){
            #pragma omp for collapse(2)
            for(unsigned int i = 0; i < rows; i++){ 
                for(unsigned int j = simdCols; j < cols; j++){
                    result[i][j] = mat1[i][j] + mat2[i][j];
                }
            }
        }

    }
}

int main() 
{ 
    omp_set_num_threads(8);
    //Allocate Matrices
    int rows = 200;
    int cols = 200;

    double **matrix_a = malloc(rows * sizeof(double *) + rows*cols*sizeof(double));

    double * dataStart = (double *) matrix_a + rows; //Offset row pointers
    for(unsigned int i = 0; i < rows; i++){
        matrix_a[i] = dataStart + i * cols;
        memset(matrix_a[i], 0, sizeof(double) * cols);
    }

    double **matrix_b = malloc(rows * sizeof(double *) + rows*cols*sizeof(double));

    dataStart = (double *) matrix_b + rows; //Offset row pointers
    for(unsigned int i = 0; i < rows; i++){
        matrix_b[i] = dataStart + i * cols;
        memset(matrix_b[i], 0, sizeof(double) * cols);
    }

    double **result = malloc(rows * sizeof(double *) + rows*cols*sizeof(double));

    dataStart = (double *) result + rows; //Offset row pointers
    for(unsigned int i = 0; i < rows; i++){
        result[i] = dataStart + i * cols;
        memset(result[i], 0, sizeof(double) * cols);
    }

    //Assign random values to matrices.
    for(int i = 0; i < rows; i++){
        for(int j = 0; j < cols; j++){
            matrix_a[i][j] = rand();
            matrix_b[i][j] = rand();
        }
    }

    
    int LOOP_COUNT = 4;

    double prevTime = omp_get_wtime();
    for(int i = 0; i < LOOP_COUNT; i++){
        add_matrix(result, matrix_a, matrix_b, rows, cols);
        
    }
    double endTime = omp_get_wtime();
    double firstTime = (endTime - prevTime)/LOOP_COUNT;
    printf("Took %f Seconds\n", firstTime);

    //Assign random values to matrices.
    for(int i = 0; i < rows; i++){
        for(int j = 0; j < cols; j++){
            matrix_a[i][j] = rand();
            matrix_b[i][j] = rand();
        }
    }

    prevTime = omp_get_wtime();
    for(int i = 0; i < LOOP_COUNT; i++){
        add_matrix_naive(result, matrix_a, matrix_b, rows, cols);
    }
    endTime = omp_get_wtime();
    double secondTime = (endTime - prevTime)/LOOP_COUNT;
    printf("Took %f Seconds\n", secondTime);
    printf("Naive Time: %f Faster\n", firstTime/secondTime);
}

私が気づいたことは、結果が LOOP_COUNT に大きく依存しているように見えることです。ループ数が多い場合、並列/SIMD バージョンは非常にうまく機能しますが、ループ数が少ない場合は、単純なソリューションの方がうまくいく傾向があります。

4

1 に答える 1

1

CPU は、メモリにアクセスするよりもはるかに高速に計算できます。

double の追加は非常に高速です。コアがメモリのボトルネックになっている可能性が非常に高いです。

もっとあります。

omp_set_num_threads

まれに良いアイデアです。通常はデフォルトで問題ありません。

double **結果、double **mat1、double **mat2

ダブル ポインターは、それらにアクセスするための 2 倍の RAM レイテンシを意味します。単一のポインターを使用します。マトリックスのスライスを使用する場合は、マトリックスの行間のオフセットを指定して別のパラメーターを渡すだけです。

しかし、そこで最も重要なことは、ベンチマークが完全に間違っていることです。

  1. アルゴリズムの異なる実装を比較するには、2 つの異なるプログラムをコンパイルする必要があります。1 つのプログラムで両方の実装を実行すると、多くの興味深いことが起こります。キャッシュ階層が有効になり、CPU にはデコードされた命令用の別の専用キャッシュがあり、最近の CPU はサーマル スロットリングが非常に高速です。

  2. コンパイラは愚かではありません。結果を使用せずに何かを計算していることに気付いた場合、コードを削除できます。入力データを変更せずに何かを複数回計算していることに気付いた場合、冗長なコードを削除して、一度だけ計算することができます。

于 2020-11-25T23:57:12.110 に答える