스레드 안전 비트 배열?

Question

질문에 편집 : 비트 배열에 스레드로부터 안전하게 액세스 할 수 있습니까? 아래의 구현은 병렬 처리의 목적을 무효화시키는 뮤텍스 잠금을 필요로한다.

필자는 pthreads를 사용하여 트윈 프라임 생성기의 병렬 구현을 생성해야했습니다. 나는 에라 토 스테 네스 체를 사용하고 알려진 소수의 요소를 표시하는 작업을 나누기로 결정했습니다. 스레드가 얻는 요인을 비틀 거리게합니다. , 스레드 일마르크 배수로 3, 11, 19, 27 ... 스레드 이마르크 배수로 5, 13, 21, 29 ... 두 번째 쓰레드 마크 배수로 7

는 예를 들어, 스레드가 4 15, 23, 31 ... 스레드 두 기호 배수 9, 17, 25, 33 ...

짝수 배수와 짝수 수를 건너 뛰었습니다. 저는 bitarray를 사용했기 때문에 INT_MAX까지 실행했습니다. 내가 가진 문제는 최대 값이 1,000 만 개에 이르며 결과는 알려진 파일과 비교하여 얼마나 많은 오류가 있는지를 나타내는 약 5 개의 숫자에 따라 다릅니다. 결과는 약 10000의 최대 값까지 1 단계 씩 변합니다. 그 아래의 모든 것은 오류가 없습니다.

처음에는 프로세스 간의 통신이 필요하다고 생각하지 않았습니다. 결과를 보았을 때 모든 스레드가 각 배수를 따라 잡을 수 있도록 pthread 장벽을 추가했습니다. 이것은 아무런 변화도 없었습니다. mark() 함수 주위에 뮤텍스 잠금을 추가하면 트릭을 만들었지 만 모든 것이 느려집니다.

여기 내 코드입니다. 누군가를 바라보며 명백한 것을 볼 수 있습니다.

#include <pthread.h> 
#include <stdio.h> 
#include <sys/times.h> 
#include <stdlib.h> 
#include <unistd.h> 
#include <math.h> 
#include <string.h> 
#include <limits.h> 
#include <getopt.h> 

#define WORDSIZE 32 

struct t_data{ 
    int *ba; 
    unsigned int val; 
    int num_threads; 
    int thread_id; 
}; 

pthread_mutex_t mutex_mark; 

void mark(int *ba, unsigned int k) 
{ 
    ba[k/32] |= 1 << (k%32); 
} 

void mark(int *ba, unsigned int k) 
{ 
    pthread_mutex_lock(&mutex_mark); 
    ba[k/32] |= 1 << (k%32); 
    pthread_mutex_unlock(&mutex_mark); 
} 

void initBa(int **ba, unsigned int val) 
{ 
    *ba = calloc((val/WORDSIZE)+1, sizeof(int)); 
} 

void getPrimes(int *ba, unsigned int val) 
{ 
    int i, p; 
    p = -1; 

    for(i = 3; i<=val; i+=2){ 
      if(!isMarked(ba, i)){ 
        if(++p == 8){ 
         printf(" \n"); 
         p = 0; 
        } 
        printf("%9d", i); 
      } 
    } 
    printf("\n"); 
} 

void markTwins(int *ba, unsigned int val) 
{ 
    int i; 
    for(i=3; i<=val; i+=2){ 
     if(!isMarked(ba, i)){ 
      if(isMarked(ba, i+2)){ 
       mark(ba, i); 
      } 

     } 
    } 
} 

void *setPrimes(void *arg) 
{ 
    int *ba, thread_id, num_threads, status; 
    unsigned int val, i, p, start; 
    struct t_data *data = (struct t_data*)arg; 
    ba = data->ba; 
    thread_id = data->thread_id; 
    num_threads = data->num_threads; 
    val = data->val; 

    start = (2*(thread_id+2))-1; // stagger threads 

    i=3; 
    for(i=3; i<=sqrt(val); i+=2){ 
     if(!isMarked(ba, i)){ 
      p=start; 
      while(i*p <= val){ 
        mark(ba, (i*p)); 
       p += (2*num_threads); 
      }  
     }  
    } 
    return 0; 
} 

void usage(char *filename) 
{ 
    printf("Usage: \t%s [option] [arg]\n", filename); 
    printf("\t-q generate #'s internally only\n"); 
    printf("\t-m [size] maximum size twin prime to calculate\n"); 
    printf("\t-c [threads] number of threads\n"); 
    printf("Defaults:\n\toutput results\n\tsize = INT_MAX\n\tthreads = 1\n"); 
} 

int main(int argc, char **argv) 
{ 
    int *ba, i, num_threads, opt, output; 
    unsigned int val; 

    output = 1; 
    num_threads = 1; 
    val = INT_MAX; 

    while ((opt = getopt(argc, argv, "qm:c:")) != -1){ 
     switch (opt){ 
      case 'q': output = 0; 
       break; 
      case 'm': val = atoi(optarg); 
       break; 
      case 'c': num_threads = atoi(optarg); 
       break; 
      default: 
       usage(argv[0]); 
       exit(EXIT_FAILURE); 
     } 
    } 

    struct t_data data[num_threads];  
    pthread_t thread[num_threads]; 
    pthread_attr_t attr; 

    pthread_mutex_init(&mutex_mark, NULL); 

    initBa(&ba, val); 

    pthread_attr_init(&attr); 
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);  

    for(i=0; i < num_threads; i++){ 
     data[i].ba = ba; 
     data[i].thread_id = i; 
     data[i].num_threads = num_threads; 
     data[i].val = val; 
     if(0 != pthread_create(&thread[i], 
           &attr, 
           setPrimes, 
           (void*)&data[i])){ 
      perror("Cannot create thread"); 
      exit(EXIT_FAILURE); 
     } 
    } 

    for(i = 0; i < num_threads; i++){ 
     pthread_join(thread[i], NULL); 
    } 

    markTwins(ba, val); 
    if(output) 
     getPrimes(ba, val); 

    free(ba); 
    return 0; 
} 

편집 : 나는 장벽을 없애고 마크 기능에 mutex_lock을 추가했습니다. 출력이 정확하지만 지금은 두 개 이상의 스레드가 속도를 줄입니다. 과속에 대한 제안?

Answer 1

현재 마크 구현은 입니다.이지만 잠금은 매우 거칠습니다. 전체 어레이에 대해 하나의 잠금 장치 만 있습니다. 즉, 스레드가 지속적으로 해당 잠금을 위해 경합하고 있음을 의미합니다.

성능을 개선 한 가지 방법은 만드는 것입니다

미세한가 그레인 잠금 :

struct bitarray 
{ 
    int *bits; 
    pthread_mutex_t *locks; 
}; 

struct t_data 
{ 
    struct bitarray ba; 
    unsigned int val; 
    int num_threads; 
    int thread_id; 
}; 

void initBa(struct bitarray *ba, unsigned int val) 
{ 
    const size_t array_size = val/WORDSIZE + 1; 
    size_t i; 

    ba->bits = calloc(array_size, sizeof ba->bits[0]); 
    ba->locks = calloc(array_size, sizeof ba->locks[0]); 

    for (i = 0; i < array_size; i++) 
    { 
     pthread_mutex_init(&ba->locks[i], NULL); 
    } 
} 

void mark(struct bitarray ba, unsigned int k) 
{ 
    const unsigned int entry = k/32; 

    pthread_mutex_lock(&ba.locks[entry]); 
    ba.bits[entry] |= 1 << (k%32); 
    pthread_mutex_unlock(&ba.locks[entry]); 
} 

: 각 배열 항목에 대한 뮤텍스를 가질 수 있도록 각 '마크'동작은, 배열 내의 단일 정수에 단독으로 액세스해야

알고리즘에 경쟁 조건이 있음을 유의하십시오. 예를 들어 num_threads = 4을 고려하면 스레드 0은 3에서 시작하고 스레드 1은 5에서 시작하고 스레드 2는 7에서 시작합니다. 스레드 2가 완전히 실행되어 7의 배수와 15에서 다시 시작 전에 스레드 0 또는 스레드 1은 15를 3 또는 5의 배수로 15로 표시 할 수 있습니다. 스레드 2는 쓸모없는 작업을 수행합니다. 15의 배수마다메모리에 비트 마스크를 적용 할 수

void mark(int *ba, unsigned int k) 
{ 
    __sync_or_and_fetch(&ba[k/32], 1U << k % 32); 
} 

Answer 2

mark() funciton은 threadsafe가 아닙니다. 두 스레드가 같은 비트 내에서 비트를 설정하려고하면 int 위치가 다른 스레드에 의해 설정된 비트로 0으로 덮어 쓸 수 있습니다.