pthread가있는 실제 가속이 없음

Question

몬테카를로 알고리즘의 멀티 스레드 버전을 구현하려고합니다.

#define _POSIX_C_SOURCE 200112L 

#include <stdio.h> 
#include <stdlib.h> 
#include <pthread.h> 
#include <time.h> 
#include <math.h> 
#include <semaphore.h> 
#include <errno.h> 
#include <stdbool.h> 
#include <string.h> 

#define MAX_THREADS 12 
#define MAX_DOTS 10000000 

double sum = 0.0; 
sem_t sem; 

void reset() { 
    sum = 0.0; 
} 

void* check_dot(void* _iterations) { 
    int* iterations = (int*)_iterations; 
    for(int i = 0; i < *iterations; ++i) { 
     double x = (double)(rand() % 314)/100; 
     double y = (double)(rand() % 100)/100; 
     if(y <= sin(x)) { 
      sem_wait(&sem); 
      sum += x * y; 
      sem_post(&sem); 
     } 
    } 
    return NULL; 
} 

void* check_dots_advanced(void* _iterations) { 
    int* iterations = (int*)_iterations; 
    double* res = (double*)malloc(sizeof(double)); 
    for(int i = 0; i < *iterations; ++i) { 
     double x = (double)(rand() % 314)/100; 
     double y = (double)(rand() % 100)/100; 
     if(y <= sin(x)) *res += x * y; 
    } 
    pthread_exit((void*)res); 
} 

double run(int threads_num, bool advanced) { 
    if(!advanced) sem_init(&sem, 0, 1); 
    struct timespec begin, end; 
    double elapsed; 
    pthread_t threads[threads_num]; 
    int iters = MAX_DOTS/threads_num; 
    for(int i = 0; i < threads_num; ++i) { 
     if(!advanced) pthread_create(&threads[i], NULL, &check_dot, (void*)&iters); 
     else pthread_create(&threads[i], NULL, &check_dots_advanced, (void*)&iters); 
    } 
    if(clock_gettime(CLOCK_REALTIME, &begin) == -1) { 
     perror("Unable to get time"); 
     exit(-1); 
    } 
    for(int i = 0; i < threads_num; ++i) { 
     if(!advanced) pthread_join(threads[i], NULL); 
     else { 
      void* tmp; 
      pthread_join(threads[i], &tmp); 
      sum += *((double*)tmp); 
      free(tmp); 
     } 
    } 
    if(clock_gettime(CLOCK_REALTIME, &end) == -1) { 
     perror("Unable to get time"); 
     exit(-1); 
    } 
    if(!advanced) sem_destroy(&sem); 
    elapsed = end.tv_sec - begin.tv_sec; 
    elapsed += (end.tv_nsec - begin.tv_nsec)/1000000000.0; 
    return elapsed; 
} 

int main(int argc, char** argv) { 
    bool advanced = false; 
    char* filename = NULL; 
    for(int i = 1; i < argc; ++i) { 
     if(strcmp(argv[i], "-o") == 0 && argc > i + 1) { 
      filename = argv[i + 1]; 
      ++i; 
     } 
     else if(strcmp(argv[i], "-a") == 0 || strcmp(argv[i], "--advanced") == 0) { 
      advanced = true; 
     } 
    } 
    if(!filename) { 
     fprintf(stderr, "You should provide the name of the output file.\n"); 
     exit(-1); 
    } 
    FILE* fd = fopen(filename, "w"); 
    if(!fd) { 
     perror("Unable to open file"); 
     exit(-1); 
    } 
    srand(time(NULL)); 
    double worst_time = run(1, advanced); 
    double result = (3.14/MAX_DOTS) * sum; 
    reset(); 
    fprintf(fd, "Result: %f\n", result); 
    for(int i = 2; i <= MAX_THREADS; ++i) { 
     double time = run(i, advanced); 
     double accel = time/worst_time; 
     fprintf(fd, "%d:%f\n", i, accel); 
     reset(); 
    } 
    fclose(fd); 
    return 0; 
} 

그러나, 나는 스레드의 수를 증가와 함께 실제 가속을 볼 수 없습니다 (그리고 내가 사용하고 무엇을 check_dot() 함수를 중요하지 않습니다) : 여기 내 코드입니다. 내가 인텔 코어 i7-3517u 내 노트북에이 코드를 실행하기 위해 노력했다 (lscpu는 4 개 독립적 인 CPU가 있다고 말한다) 그리고 스레드의 수처럼 보이는 정말 내 프로그램의 실행 시간에 영향을 미친다 :

Number of threads: 1, working time: 0.847277 s 
Number of threads: 2, working time: 3.133838 s 
Number of threads: 3, working time: 2.331216 s 
Number of threads: 4, working time: 3.011819 s 
Number of threads: 5, working time: 3.086003 s 
Number of threads: 6, working time: 3.118296 s 
Number of threads: 7, working time: 3.058180 s 
Number of threads: 8, working time: 3.114867 s 
Number of threads: 9, working time: 3.179515 s 
Number of threads: 10, working time: 3.025266 s 
Number of threads: 11, working time: 3.142141 s 
Number of threads: 12, working time: 3.064318 s 

을

적어도 4 개의 첫 번째 값 (실행되는 스레드가 적을수록 스레드가 많을수록)이 실행 시간과 작업 스레드 수 사이에 일종의 선형 의존성이 있어야한다고 생각합니다. 그러나 여기에는 꽤 동일한 시간 값이 있습니다. . 그것은 내 코드에서 실제 문제입니까 아니면 너무 까다 롭습니다.

Answer 1

코드에 두 가지 변경 사항을 적용하여 원하는 타이밍/스케일링 측정 값을 수집 할 수있었습니다.

먼저 rand()은 스레드로부터 안전하지 않습니다. 고급 check_dots에서 rand_r (seed) 호출로 호출을 대체하면 스레드가 증가함에 따라 지속적인 확장이 나타납니다. 나는 rand가 실행을 직렬화하고 속도 향상을 막는 내부 잠금을 가지고 있다고 생각한다. 이러한 변화만으로도 1.23 초 -> 0.55 초 (5 스레드)의 확장이 가능합니다.

둘째, 스레드와 malloc 호출을 직렬로 생성/결합하는 비용이 포함되지 않도록 코어 실행 영역 주위에 장벽을 도입했습니다. 코어 실행 영역은 1.23 초 -> 0.18 초 (8 스레드)에서 우수한 확장 성을 나타냅니다.

코드는 Intel E3-1240 v5 (4 코어, HT), Linux 3.19.0-68-generic에서 실행되는 gcc -O3 -pthread mcp.c -std=c11 -lm으로 컴파일되었습니다. 단일 측정 값이보고되었습니다.

pthread_barrier_t bar; 

void* check_dots_advanced(void* _iterations) { 
    int* iterations = (int*)_iterations; 
    double* res = (double*)malloc(sizeof(double)); 
    sem_wait(&sem); 
    unsigned int seed = rand(); 
    sem_post(&sem); 
    pthread_barrier_wait(&bar); 
    for(int i = 0; i < *iterations; ++i) { 
     double x = (double)(rand_r(&seed) % 314)/100; 
     double y = (double)(rand_r(&seed) % 100)/100; 
     if(y <= sin(x)) *res += x * y; 
    } 
    pthread_barrier_wait(&bar); 
    pthread_exit((void*)res); 
} 

double run(int threads_num, bool advanced) { 
    sem_init(&sem, 0, 1); 
    struct timespec begin, end; 
    double elapsed; 
    pthread_t threads[threads_num]; 
    int iters = MAX_DOTS/threads_num; 
    pthread_barrier_init(&bar, NULL, threads_num + 1); // barrier init 
    for(int i = 0; i < threads_num; ++i) { 
     if(!advanced) pthread_create(&threads[i], NULL, &check_dot, (void*)&iters); 
     else pthread_create(&threads[i], NULL, &check_dots_advanced, (void*)&iters); 
    } 
    pthread_barrier_wait(&bar); // wait until threads are ready 
    if(clock_gettime(CLOCK_REALTIME, &begin) == -1) { // begin time 
     perror("Unable to get time"); 
     exit(-1); 
    } 

    pthread_barrier_wait(&bar); // wait until threads finish 
    if(clock_gettime(CLOCK_REALTIME, &end) == -1) { // end time 
     perror("Unable to get time"); 
     exit(-1); 
    } 
    for(int i = 0; i < threads_num; ++i) { 
     if(!advanced) pthread_join(threads[i], NULL); 
     else { 
      void* tmp; 
      pthread_join(threads[i], &tmp); 
      sum += *((double*)tmp); 
      free(tmp); 
     } 
    } 
    pthread_barrier_destroy(&bar); 

Answer 2

발생한 문제는 rand()의 내부 상태가 모든 스레드 사이에 공유 자원임을, 그래서 스레드 rand()에 대한 액세스에에는 직렬화 할 것입니다.

스레드 당 상태가있는 의사 난수 생성기를 사용해야합니다. 즉, rand_r() 함수 (POSIX의 최신 버전에서 사용되지 않음)를 그대로 사용할 수 있습니다. 진지한 작업을 위해서는 Mersenne Twister와 같은 특정 PRNG 알고리즘의 구현을 가져 오는 것이 가장 좋습니다.