乱数の合計を使ったマルチスレッド実行時間

Question

プログラマで実装されたスピンロック（ビジー待機）によってシリアル化されたK個のワーカースレッドでN個の乱数[-100,100]の配列を合計するマルチスレッドプログラムを作成しようとしています。テストの目的で乱数を使用しようとする前に、自分のコードに示すように、配列全体を1で初期化しました。合計を計算する上でうまく動作しますが、実行時間に問題を提起

#include <iostream> 
#include <string.h> 
#include <pthread.h> 
#include <cstdlib> 
#include <time.h> 
#include <atomic> 
#include <chrono> 

using namespace std; 
using namespace chrono; 

struct lock { 

    long double sum = 0; 
    atomic_flag m_flag = ATOMIC_FLAG_INIT; // Inicializa com m_flag = 0 

    void acquire() { 
     while(m_flag.test_and_set()); 
    } 
    void release() { 
     m_flag.clear(); 
    } 
}; 

struct t_data{ 
    int t_id; 
    char* sumArray; 
    struct lock* spinlock; 
}; 

void* sum(void* thread_data) { 

    struct t_data *my_data; 
    long double m_sum=0; 
    my_data = (struct t_data *) thread_data; 

    for (int i=0;i<strlen(my_data->sumArray);i++) { 
     m_sum += my_data->sumArray[i]; 
    } 

    my_data->spinlock->acquire(); 
    cout << "THREAD ID: " << my_data->t_id << endl; 
    cout << "Acquired lock." << endl; 
    my_data->spinlock->sum += m_sum; 
    cout << "Releasing lock..." << endl << endl; 
    my_data->spinlock->release(); 

} 

int main(int argc, char** argv) { 

    // Inicializar cronômetro, arrays, spinlock,etc.                                                                                                                                                       , spinlock, etc. 
    system_clock::time_point starting_time = system_clock::now(); 
    int K = atoi(argv[1]); 
    int N = atoi(argv[2]); 
    int temp; 
    double expected_sum = 0; 
    pthread_t threads[K]; 
    struct t_data threads_data[K]; 
    struct lock spinlock; 
    const long int numElements = (long int) N/K; //Divisão inteira de N/K para dividir array em parcelas 

    // Criar array[K] de arrays para delegar cada sub-lista a uma thread 
    char** numArrays = new char*[K]; 
    for(int i=0;i<K;i++) 
     numArrays[i] = new char[numElements]; //Char utilizado para que seja alocado apenas 1 byte por número 

    // Inicializar seed aleatória para preenchimento de arrays 
    srand(time(NULL)); 

    //Preencher arrays que serão passados às threads criadas 
    for (int i=0;i<K;i++) { 
     for(int j=0;j<numElements;j++) { 
      temp = 1;//rand() % 201 - 100; (CHANGING THIS GIVES UNEXPECTED RESULTS) 
      numArrays[i][j] = temp; 
      expected_sum+=temp; 
     } 
     //Criar threads e passando argumentos(id,spinlock,array) 
     threads_data[i].t_id = i; 
     threads_data[i].spinlock = &spinlock; 
     threads_data[i].sumArray = numArrays[i]; 
     pthread_create(&threads[i],NULL,sum,(void*)&threads_data[i]); 
    } 

    // Parar o programa até que todas as threads terminem para imprimir soma correta 
    for (int i=0;i<K;i++){ 
     if(pthread_join(threads[i],NULL)) cout << "Error waiting for threads." << endl; 
    } 

    // Somando últimos valores restantes no caso de N%K != 0 (esta parcela torna-se irrelevante à medida que N >> K) 
    for(int i=0;i<(int)N%K;i++) { 
     temp = 1;//rand() % 201 - 100; (CHANGING THIS GIVES UNEXPECTED RESULTS) 
     spinlock.sum+=temp; 
     expected_sum+=temp; 
    } 

    // Printar resultado esperado, o calculado e tempo de execução 
    cout << "EXPECTED SUM = " << expected_sum << endl; 
    cout << "CALCULATED SUM = " << spinlock.sum << endl; 

    // Liberar memória alocada 
    for(int i=0;i<K;i++) 
     delete[] numArrays[i]; 

    delete[] numArrays; 

    auto start_ms = time_point_cast<milliseconds>(starting_time); 
    auto now = system_clock::now(); 
    auto now_ms = time_point_cast<milliseconds>(now); 
    auto value = now_ms - start_ms; 
    long execution_time = value.count(); 
    cout << "-----------------------" << endl; 
    cout << "Execution time: " << execution_time << "ms" << endl; 
    return 0; 
} 

：：私は問題がある場合には全く見当がつかないので、私は完全なコードを投稿します、直線的に拡大することになっています（Nを/ K）が、K = 10のためのテスト、N =10⁶：

EXPECTED SUM = 1e+06 
CALCULATED SUM = 1e+06 
----------------------- 
Execution time: 1310ms 

そして、K = 10、N = 2 *10⁶：

EXPECTED SUM = 2e+06 
CALCULATED SUM = 2e+06 
----------------------- 
Execution time: 7144ms 

それがなぜ起こるか私にはわかりません。それは倍増するはずです。 Kを変更すると正しく動作します。また、もし私がrand() % 201-100の代わりに1つのものを使用すると、本当にうんざりしてしまいます。 K = 10、N =10⁶について：

EXPECTED SUM = -16307 
CALCULATED SUM = 1695 
----------------------- 
Execution time: 95ms 

と実行時間の変更について、Nは固定である（直線的に比例）が、Kはもう違いはありません。これらのどれも私には意味をなさない。

ありがとうございます！

Answer 1

strlen(my_data->sumArray)は、文字配列/ c-stringで最初に0に停止し、expected_sumの値を合計してtempの値を維持します。 （これはすべての後にC++である）非ASCIIデータのvectorを使用します。

// use a vector in t_data 
struct t_data{ 
    int t_id; 
    std::vector<char> sumArray; 
    lock* spinlock; 
}; 

// adjust summing up in sum(void* thread_data) 
for (char value : my_data->sumArray) { 
    m_sum += value; 
} 

// initialise like this 
threads_data[i].sumArray.resize(numElements); 
for(size_t j = 0; j < threads_data[i].sumArray.size(); ++j) { 
    char temp = 1; //or (char)(rand() % 201 - 100); 
    threads_data[i].sumArray[j] = temp; 
    expected_sum += temp; 
} 

今、あなたはタイミングしているかを検討：タイミング領域のthreads_data[i]とexpected_sum外の初期化を移動し、rand通話のそれ以外の場合は、何百万確かにすべてを支配するでしょう。いずれにしても、並列バージョンと一緒にシーケンシャルバージョンを測定しているので、Kがタイミングに差異を見込むことは期待できません：少なくともシーケンシャルバージョン+最後のパラレルバージョン（結合時）を常に測定しています。