2

LCS の並列計算は、波面パターンに従います。これは、シリアル実装より遅い並列関数です。（対角線の数（並列）と行数（直列）が関係していると思います）

void parallelLCS(char * sequence_a, char * sequence_b, size_t size_a, size_t size_b) {
double start, end;

int ** dp_table = new int*[size_a + 1];

for (int i = 0; i <= size_a; i++)
    dp_table[i] = new int[size_b + 1];

for (int i = 1; i <= size_a; i++)
    dp_table[i][0] = 0;
for (int j = 0; j <= size_b; j++)
    dp_table[0][j] = 0;

int p_threads = 2;
int diagonals = size_a + size_b;

start = omp_get_wtime();
#pragma omp parallel num_threads(p_threads) default(none) firstprivate(p_threads,size_a,size_b,sequence_a,sequence_b) shared(dp_table,diagonals)
{
    for (int curr_diagonal = 1; curr_diagonal <= (diagonals - 1);) {
        int j = omp_get_thread_num() + 1;   //column index
        int i = curr_diagonal - j + 1;      //row index
        for (; j <= curr_diagonal; j += p_threads, i = i - p_threads) {
            if (i <= size_a && j <= size_b) {
                if (sequence_a[i] == sequence_b[j]) {
                    dp_table[i][j] = dp_table[i - 1][j - 1] + 1;
                } else if (dp_table[i - 1][j] >= dp_table[i][j - 1]) {
                    dp_table[i][j] = dp_table[i - 1][j];
                } else {
                    dp_table[i][j] = dp_table[i][j - 1];
                }
            }
        }
        curr_diagonal++;
#pragma omp barrier
    }
}
end = omp_get_wtime();

printf("\nParallel - Final answer: %d\n", dp_table[size_a][size_b]);
printf("Time: %f\n", end - start);

//Delete dp_table
for (int i = 0; i <= size_a; i++)
    delete [] dp_table[i];
delete [] dp_table;
}

ここにシリアル関数があります

void serialLCS(char * sequence_a, char * sequence_b, size_t size_a, size_t size_b) {
double start, end;
int ** dp_table = new int*[size_a + 1];
for (int i = 0; i <= size_a; i++)
    dp_table[i] = new int[size_b + 1];

for (int i = 1; i <= size_a; i++)
    dp_table[i][0] = 0;
for (int j = 0; j <= size_b; j++)
    dp_table[0][j] = 0;

start = omp_get_wtime();
for (int i = 1; i <= size_a; i++) {
    for (int j = 1; j <= size_b; j++) {
        if (sequence_a[i] == sequence_b[j]) {
            dp_table[i][j] = dp_table[i - 1][j - 1] + 1;
        } else if (dp_table[i - 1][j] >= dp_table[i][j - 1]) {
            dp_table[i][j] = dp_table[i - 1][j];
        } else {
            dp_table[i][j] = dp_table[i][j - 1];
        }
    }
}
end = omp_get_wtime();
printf("\nSerial - Final answer: %d\n", dp_table[size_a][size_b]);
printf("Time: %f\n", end - start);

//Delete dp_table
for (int i = 0; i <= size_a; i++)
    delete [] dp_table[i];
delete [] dp_table;
}

...テスト機能を追加すると思いました

#include <cstdlib>
#include <stdio.h>

#include <omp.h>

void serialLCS(char * sequence_a, char * sequence_b, size_t size_a, size_t size_b);
void parallelLCS(char * sequence_a, char * sequence_b, size_t size_a, size_t size_b);

int main() {

size_t size_a;
size_t size_b;

printf("Enter size of sequence A: ");
scanf("%zd",&size_a);
printf("Enter size of sequence B: ");
scanf("%zd",&size_b);

//keep larger sequence in sequence_a
if (size_b > size_a) size_a ^= size_b ^= size_a ^= size_b;

char * sequence_a = new char[size_a + 1];
char * sequence_b = new char[size_b + 1];
sequence_a[0] = sequence_b[0] = '0';

const size_t alphabet_size = 12;
char A[alphabet_size] = {'A', 'T', 'G', 'C', 'Q', 'W', 'E', 'R', 'Y', 'U', 'I', 'O'};
char AA[alphabet_size] = {'T', 'C', 'A', 'G', 'R', 'E', 'W', 'Q', 'O', 'I', 'U', 'Y'};

for (size_t i = 1; i < size_a; i++) {
    sequence_a[i] = A[rand() % alphabet_size];
}
for (size_t i = 1; i < size_b; i++) {
    sequence_b[i] = AA[rand() % alphabet_size];
}

serialLCS(sequence_a, sequence_b, size_a, size_b);
parallelLCS(sequence_a, sequence_b, size_a, size_b);

delete [] sequence_a;
delete [] sequence_b;

return 0;
}
4

1 に答える 1

8

問題はOpenMPにあるのではなく、並列実装でデータにアクセスする方法にあります。1つのスレッドのみで並列バージョンを実行した場合でも、約2倍遅くなります。

さて、キャッシュに適さないデータ構造の世界へようこそ。対角依存性があるため、行列を対角線で歩きますが、それでも通常の方法で格納します。その場合、データアクセスパターンは非常に非線形であるため、キャッシュに非常に適していません。古い16コアXeonX7350システムでシングルスレッドモードでコードを実行する場合は、L1およびL2キャッシュミスの量を確認してください。

L1およびL2キャッシュミス

プロセスタイムラインの緑色の部分は、コードのシリアル部分を表しています。オレンジ色の部分は、（シングルスレッド実行のために非アクティブな）OpenMPparallel領域です。シリアルコードが非常にキャッシュフレンドリーであることがはっきりとわかります。L2キャッシュミスの量が比較的少ないだけでなく、L1キャッシュミスの量も比較的少ないです。しかし、コードの並列セクションでは、マトリックスを斜めに歩くときのストライドが非常に大きいため、キャッシュは常にゴミ箱に捨てられ、ミスの量は非常に多くなっています。

2つのスレッドを使用すると、事態はさらに悪化します。同じ行列行に属する2つの隣接する対角線からの要素は、同じキャッシュラインに分類される可能性があります。ただし、対角線の1つは1つのスレッドによって処理され、もう1つは別のスレッドによって処理されます。したがって、コードは大量の偽共有に遭遇します。最新のマルチソケットAMD64または（ポスト）NehalemシステムでのNUMAの問題は言うまでもありません。

解決策は、単純に対角線で行列を歩くだけでなく、各対角線がメモリ内の連続したセクションを占めるように、行列を斜めの形式で格納することです。

于 2012-11-14T09:39:27.187 に答える