我撰寫了一個帶有以下 5 個引數的函式：
- 文本行陣列；
- 一些單詞的陣列；
- 行數（大約 40k）；
- 字數（約 4-5）；
- 要創建的執行緒數（k，嘗試了許多值，例如 2<k<20）。
該函式在for回圈中搜索給定的單詞，在每次迭代中掃描每一行以查找一個單詞（outer for）。
內for回圈：
- 回圈通過線；
- 檢查該行是否包含給定的單詞；
- 計算該單詞在該行中的出現次數；
- 如果在該行中找到該單詞，則列印一條訊息；
- 增加該單詞在整個文本中的出現次數及其在該行中的出現次數。
我先將其撰寫為串行程式，然后嘗試使用 OpenMP 將其并行化，并比較每個分析整個文本所需的時間。不幸的是，與串行版本相比，我無法提高并行程式的時間。
為了測量時間，我使用以下功能：
double ClockCounter;
void start()
{
ClockCounter = omp_get_wtime();
}
void stop()
{
ClockCounter = omp_get_wtime() - ClockCounter;
printf("Elapsed time: %f\n", ClockCounter);
}
以及文本分析功能：
void analyze_text(char **lines, char *words[], size_t nr_lines, int nr_words, int k) {
int i, total_word_count, word_occurence;
start();
# pragma omp parallel for num_threads(k) \
default(none) shared(total_word_count, word_occurence) private(i, j, nr_words, nr_lines, word_occurence, counter)
for (i=0; i<nr_words; i ) {
total_word_count = 0;
size_t j;
printf("The word is: %s.\nSEARCHING...\n", words[i]);
//# pragma omp parallel for num_threads(k) \
// default(none) shared(total_word_count) private(j, nr_lines, word_occurence, counter)
for (j=0; j<nr_lines; j ) {
char *line = NULL;
line = (char *) malloc (strlen(lines[j]) 1);
strcpy(line, lines[j]);
word_occurence = 0;
if (strstr(line, words[i]) != NULL) {
printf("Word found at line %ld, position(s): ", j);
char *found_word = NULL;
found_word = (char *) malloc (strlen(words[i]) 1);
char delim[] = " -";
char *ptr = strtok(line, delim);
int counter = 0;
while (ptr != NULL) {
counter ;
strncpy(found_word, ptr, strlen(words[i]));
found_word[strlen(found_word)] = '\0';
if (strcmp(words[i], found_word) == 0) {
word_occurence ;
printf("%d ", counter);
}
ptr = strtok(NULL, delim);
}
printf("\nline[%3zu]: %s\n", j, lines[j]);
}
total_word_count = word_occurence;
}
printf("The word appears %d times in the text in total.\n\n", total_word_count);
}
stop();
}
正如你所看到的，我也只嘗試并行化內部for回圈，但我也沒有得到任何改進。由于嵌套for回圈有點混亂，我不確定在哪里以及如何宣告并行 for 指令，也不知道如何正確地將變數設定為共享或私有。
順序版本看起來完全相同，但沒有宣告 omp 指令。
順序版本的時間（~=）：
Elapsed time: 0.025583
Time (~=) with the parallel version (k=2, 4, 6, 8, always the same):
Elapsed time: 0.025690
Can somebody please explain to me what I am missing here?
uj5u.com熱心網友回復：
TL;DR 答案：您的代碼受記憶體限制（大量或記憶體讀取或寫入，實際上沒有 CPU 密集型計算）。CPU 很容易超過可用記憶體帶寬，增加執行緒數不會提高性能。這可能發生在您的硬體上，令人驚訝的是，這也發生在 Compiler Explorer 上，但不會發生在我的計算機上。我真的很困惑。
詳細解答：
您的代碼存在一些問題（資料爭用、記憶體泄漏、變數在資料子句中出現多次等），因此我執行了以下操作來修復這些錯誤并使您的代碼更快：
- 在最小要求范圍內使用變數。它有助于避免資料競爭并幫助編譯器進行更好的優化。
- 更正了 OpenMP 指令。在
i回圈之前，您必須添加以下行：
#pragma omp parallel for num_threads(k) default(none) shared(lines, words, nr_words, nr_lines)
另一種選擇是并行化j回圈。為避免競爭條件，您必須使用歸約 ( reduction( :total_word_count))：
#pragma omp parallel for num_threads(k) default(none) shared(i,lines, words, nr_words, nr_lines) reduction( :total_word_count)
- 去掉了耗時
malloc，換成靜態分配：
//Maximum length of a line - modify it as necessary and make sure that no lines are longer than this value
#define MAX_LINE_LEN 1000
...
char line[MAX_LINE_LEN];
....
char found_word[MAX_LINE_LEN]; //it may be smaller
strcpy(line, lines[j]);在隨后的if宣告之后被移動。這非常耗時，并且僅在找到單詞時才需要。所以
char *line = NULL;
line = (char *) malloc (strlen(lines[j]) 1);
strcpy(line, lines[j]);
word_occurence = 0;
if (strstr(line, words[i]) != NULL) {
改為
int word_occurence = 0;
if (strstr(lines[j], words[i]) != NULL) {
char line[MAX_LINE_LEN];
strcpy(line, lines[j]);
...
//Note that the code below is not critical (rarely executed)...
- 將所有
printf功能更改為
#ifdef USE_PRINTF
printf(...);
#endif
因此很容易打開/關閉列印輸出，也更容易測驗其性能。請注意，如果使用更多執行緒，列印輸出將混合在一起，因此您必須先收集輸出并稍后列印。
請注意，最好重寫代碼并首先遍歷文本行并在一行中搜索每個單詞。在這種情況下，快取利用率會更好，這將提高性能。
添加了一個主要功能來創建文本（通過從 5 個預定義的行中隨機添加行）來測驗其性能
代碼如下：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <omp.h>
//Maximum length of a line - modify it as necessary and make sure that no lines are longer than this value
#define MAX_LINE_LEN 1000
//Uncomment this line to see printout
//#define USE_PRINTF
double ClockCounter;
void start()
{
ClockCounter = omp_get_wtime();
}
void stop()
{
ClockCounter = omp_get_wtime() - ClockCounter;
printf("Elapsed time: %f\n", ClockCounter);
}
void analyze_text(char **lines, const char *words[], const size_t nr_lines, const int nr_words, const int k) {
start();
#pragma omp parallel for num_threads(k) default(none) shared(lines, words, nr_words, nr_lines)
for (int i=0; i<nr_words; i ) {
int total_word_count = 0;
#ifdef USE_PRINTF
printf("The word is: %s.\nSEARCHING...\n", words[i]);
#endif
//#pragma omp parallel for num_threads(k) default(none) shared(i,lines, words, nr_words, nr_lines) reduction( :total_word_count)
for (size_t j=0; j<nr_lines; j ) {
int word_occurence = 0;
if (strstr(lines[j], words[i]) != NULL) {
char line[MAX_LINE_LEN];
strcpy(line, lines[j]);
#ifdef USE_PRINTF
printf("Word found at line %ld, position(s): ", j);
#endif
char found_word[MAX_LINE_LEN];
char delim[] = " -";
char *ptr = strtok(line, delim);
int counter = 0;
while (ptr != NULL) {
counter ;
strncpy(found_word, ptr, strlen(words[i]));
found_word[strlen(found_word)] = '\0';
if (strcmp(words[i], found_word) == 0) {
word_occurence ;
#ifdef USE_PRINTF
printf("%d ", counter);
#endif
}
ptr = strtok(NULL, delim);
}
#ifdef USE_PRINTF
printf("\nline[%3zu]: %s\n", j, lines[j]);
#endif
}
total_word_count = word_occurence;
}
#ifdef USE_PRINTF
printf("The word appears %d times in the text in total.\n\n", total_word_count);
#endif
}
stop();
}
int main(){
const size_t nr_lines=40000;
char* lines[nr_lines];
//sample lines, the text have these lines in a random order
const char* samples[]={
"xxx yyy zzz qqq sss dddd aaaaa bbbbb cccc dd eeee fff ggg hh iii jjj kkkk llll mmm nnn oo pppp qqq rrrr ssss ttt",
"one yyy zzz qqq sss dddd aaaaa bbbbb cccc dd eeee fff ggg hh iii jjj kkkk llll mmm nnn oo pppp qqq rrrr ssss ttt",
"xxx two zzz qqq sss dddd aaaaa bbbbb cccc dd eeee fff ggg hh iii jjj kkkk llll mmm nnn oo pppp qqq rrrr ssss ttt",
"xxx yyy three qqq sss dddd aaaaa bbbbb cccc dd eeee fff ggg hh iii jjj kkkk llll mmm nnn oo pppp qqq rrrr ssss ttt",
"xxx yyy zzz four sss dddd aaaaa bbbbb cccc dd eeee fff ggg hh iii jjj kkkk llll mmm nnn oo pppp qqq rrrr ssss ttt",
"xxx yyy zzz qqq five dddd aaaaa bbbbb cccc dd eeee fff ggg hh iii jjj kkkk llll mmm nnn oo pppp qqq rrrr ssss ttt"
};
for(size_t i=0;i<nr_lines; i){
unsigned long int rnd=rand()%1000;
rnd = rnd >= sizeof(samples)/sizeof(samples[0]) ? 0 : rnd;
lines[i]=(char*) malloc(strlen(samples[rnd]) 1);
strcpy(lines[i],samples[rnd]);
}
printf("nr_lines=%ld\n",nr_lines);
const char* words[]={"one", "two", "three", "four","five"};
const size_t nr_words=sizeof(words)/sizeof(words[0]);
printf("nr_words=%ld\n",nr_words);
for(int i=1;i<6;i )
{
printf("Threads used=%d --- ",i);
analyze_text(lines, words, nr_lines, nr_words, i);
}
// You should free allocated memory here.
return 0;
}
我已經測驗了代碼首先i使用 400000 行（注意 40000 實在是太快了，所以我使用的行數比你多 10 倍）和Compiler Explorer上的 5 個單詞并行化了第一個 ( ) 回圈，結果是：
nr_lines=400000
nr_words=5
Threads used=1 --- Elapsed time: 0.032551
Threads used=2 --- Elapsed time: 0.028461
Threads used=3 --- Elapsed time: 0.029304
Threads used=4 --- Elapsed time: 0.027002
Threads used=5 --- Elapsed time: 0.026587
在我的筆記本電腦上，使用內核進行縮放要好得多：
gcc 5.c -fopenmp -O3 -mavx2 && ./a.out
nr_lines=400000
nr_words=5
Threads used=1 --- Elapsed time: 0.046173
Threads used=2 --- Elapsed time: 0.028958
Threads used=3 --- Elapsed time: 0.019951
Threads used=4 --- Elapsed time: 0.015462
Threads used=5 --- Elapsed time: 0.020994
我還并行化了第二個回圈（在這種情況下，第一個回圈沒有并行化以避免嵌套并行）。編譯器資源管理器上的結果：
nr_lines=400000
nr_words=5
Threads used=1 --- Elapsed time: 0.032781
Threads used=2 --- Elapsed time: 0.026288
Threads used=3 --- Elapsed time: 0.026601
Threads used=4 --- Elapsed time: 0.027013
Threads used=5 --- Elapsed time: 0.027567
在我的筆記本電腦上：
gcc 5.c -fopenmp -O3 -mavx2 && ./a.out
nr_lines=400000
nr_words=5
Threads used=1 --- Elapsed time: 0.047092
Threads used=2 --- Elapsed time: 0.024240
Threads used=3 --- Elapsed time: 0.016849
Threads used=4 --- Elapsed time: 0.014475
Threads used=5 --- Elapsed time: 0.012770
Threads used=6 --- Elapsed time: 0.011703
Threads used=7 --- Elapsed time: 0.009543
Threads used=8 --- Elapsed time: 0.012953
你可以看到
在 Compiler Explorer 上獲得的結果令人失望。我根本不知道它的原因是什么。很可能它與記憶體帶寬/記憶體訪問的可用通道有關，但我想高端處理器用于托管 Compiler Explorer。
在我的筆記本電腦上，縮放要好得多，特別是如果第二個回圈是并行的。這并不奇怪，因為在這種情況下快取利用率要好得多。因此我建議你重寫你的代碼并首先遍歷行并在一行中搜索所有單詞。
最后說明：如果性能很關鍵，很可能您可以找到一個并行庫，該庫旨在盡可能高效地執行此類搜索。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/409608.html
標籤：