Giải thuật tính xấp xỉ số PI sử dụng thư viện pThread trong C Linux

#1

Em sử dụng giải thuật Monte Carlo để tính số pi.
Em làm theo 2 cách : đơn luồng và đa luồng. (Em để code ở cuối bài post)

Code của em chạy đúng và trả về số Pi xấp xỉ 3,14.

Nhưng có một vấn đề là đoạn code đa luồng chạy rất chậm
Cụ thể là với 100 000 000(1 trăm triệu) lần lặp thì

  • Đơn luồng là 3s :smile: :smile: :smile:
  • Đa luồng là 21s :sob: :sob: :sob:

Mọi người cho em hỏi là vì sao lại như vậy ạ ??? :crying_cat_face:

Hiện thực theo C (Đơn luồng)

#include <stdio.h>
#include <stdint.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>

//#define PI 3.1415926535897

void calPI();

uint64_t  count = 0, range;        // Shared data
time_t    start = 0, end = 0;      // Time variables

int main(int argc, char const *argv[])
{
    assert(argc == 2    && "TheNumberOfArgumentsIsWrong");
    assert(atoll(argv[1]) > 0 && "Argument must be >= 0");

    // Set test range
    range = atoll(argv[1]);

    //*---------------------------------------*//
    time(&start); // Start counting time

    calPI();

    time(&end); // End counting time
    //*---------------------------------------*//

    double pi = 4.0*(double)count/(double)range;
    printf("%.1lf\n", pi);          // Print PI Number
    
    double time = difftime(end, start);
    printf("%.1lf(s)\n", time);    // Print time to excute

    return EXIT_SUCCESS;
}

void calPI() {
    // Initialize the pseudo number
    srand(time(NULL));
    // Monte Carlo technique

    for(uint64_t i = 0; i < range; ++i) {
        // Create point
        double x = (double)rand()/(double)RAND_MAX;
        double y = (double)rand()/(double)RAND_MAX;
        // Calculator radius
        double r = sqrt(x*x + y*y);
        // Is it in a circle
        if(r <= 1) count = count + 1;
    }
} 
/******************************************************************************
 * * FILE: pi_serial.c
 * * DESCRIPTION:
 * *   Calculates the value of pi using a parallel implementation using pthreads
 * *
 * * HOW TO COMPILE:
 * *   gcc -lm pi_serial.c
 * * HOW TO RUN:
 * *    ./a.out 100000000
 * *
 * * AUTHOR: Đỗ Đăng Khôi
 * ******************************************************************************/

Hiện thực theo C (Đa luồng)

Em sử dụng thư viện pthread.h của C trong Linux

#include <stdio.h>
#include <stdint.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
#include <pthread.h>
#include <assert.h>

#define NUM_THREAD 10
//#define PI 3.1415926535897

void* calPI(void *param);

pthread_t thdIDs[NUM_THREAD] = {}; // Thread IDs 
uint64_t  counts[NUM_THREAD] = {}; // Points in circle
uint64_t  count = 0, range;        // Shared data
time_t    start = 0, end = 0;      // Time variables

int main(int argc, char const *argv[])
{
    assert(argc == 2   &&  "TheNumberOfArgumentsIsWrong");
    assert(atoll(argv[1]) > 0 && "Argument must be >= 0");

    // Set test range
    range = atoll(argv[1])/NUM_THREAD;

    //*---------------------------------------*//
    time(&start); // Start counting time

    for(int8_t i = 0; i < NUM_THREAD; ++i)
        pthread_create(&thdIDs[i], NULL, calPI, &counts[i]);

    for(int8_t i = 0; i < NUM_THREAD; ++i) {
        pthread_join(thdIDs[i], NULL);
        count += counts[i]; // The number of points in the circle
    }

    time(&end); // End counting time
    //*---------------------------------------*//

    double pi = 4.0*(double)count/(double)range/(double)NUM_THREAD;
    printf("%.1lf\n", pi);          // Print PI Number
    
    double time = difftime(end, start);
    printf("%.1lf(s)\n", time);    // Print time to excute

    pthread_exit(EXIT_SUCCESS);
}

void* calPI(void *arg) {
    // Initialize the pseudo number
    // srand(time(NULL));
    // Monte Carlo technique
    uint64_t* pcount = (uint64_t*)arg;

    for(uint64_t i = 0; i < range; ++i) {
        // Create point
        double x = (double)rand()/(double)RAND_MAX;
        double y = (double)rand()/(double)RAND_MAX;
        // Calculator radius
        double r = sqrt(x*x + y*y);
        // Is it in a circle
        if(r <= 1) *pcount = *pcount + 1;
    }

    // End thread
    pthread_exit(EXIT_SUCCESS);
}
/******************************************************************************
 * * FILE: pi_multi_thread.c
 * * DESCRIPTION:
 * *   Calculates the value of pi using a parallel implementation using pthreads
 * *
 * * HOW TO COMPILE:
 * *   gcc -lm -pthread pi_multi_thread.c
 * * HOW TO RUN:
 * *    ./a.out 100000000
 * *
 * * AUTHOR: Đỗ Đăng Khôi
 * ******************************************************************************/
1 Like
#2

8 luồng đó làm chung 1 việc. Công việc không được phân chia rõ.
Chú ý đến biến range nhé. Không chia nhỏ nó thì chẳng khác nào yêu cầu 8 luồng làm lại cùng 1 việc 8 lần (range * 8).

3 Likes
#3

Mình có chia biến range cho số thread(NUM_THREAD) rồi. Mình cũng tạo 1 mảng count[NUM_THREAD] để mỗi luồng đếm số điểm thuộc hình tròn lưu vào mỗi biến khác nhau(không tranh chấp vùng nhớ). Nhưng mà vẫn chậm hơn rất nhiều so với đơn luồng !!! :sweat_smile::sweat_smile::sweat_smile:

1 Like
#4

Xin lỗi, mình không để ý.

Có thể do rand() gây ra. Thử dùng rand_r():

5 Likes
#5

Cám ơn bạn rất nhiều
Đúng chính xác là do rand() gây ra

Mình tìm hiểu và biết hàm rand() được hiện thực gần giống như sau :

static unsigned long next = 1;
int myrand(void)  /* RAND_MAX assumed to be 32767. */
{
    next = next * 1103515245 + 12345;
    return((unsigned)(next/65536) % 32768);
}

void mysrand(unsigned seed)
{
    next = seed;
}

=> Như vậy hàm rand() sử dụng 1 biến toàn cục để tạo số ngẫu nhiên, nên dù tạo 100 luồng thì các luồng vẫn phải chờ nhau để thay phiên sử dụng biến toàn cục đó

Giải pháp sử dụng rand_r() của mình

#include <stdint.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
#include <pthread.h>
#include <assert.h>

#define NUM_THREAD 4
//#define PI 3.1415926535897

void* calPI(void *param);

pthread_t thdIDs[NUM_THREAD] = {0}; // Thread IDs
uint64_t  counts[NUM_THREAD] = {0}; // Points count
uint64_t  sumPoint = 0, range;      // Shared data
time_t    start = 0, end = 0;       // Time variables

int main(int argc, char const *argv[])
{
    assert(argc == 2   &&  "TheNumberOfArgumentsIsWrong");
    assert(atoll(argv[1]) > 0 && "Argument must be >= 0");

    // Set test range
    range = atoll(argv[1])/NUM_THREAD;

    //*---------------------------------------*//
    time(&start); // Start counting time
    srand(time(NULL));

    for(int8_t i = 0; i < NUM_THREAD; ++i)
        pthread_create(&thdIDs[i], NULL, calPI, &counts[i]);

    for(int8_t i = 0; i < NUM_THREAD; ++i) {
        pthread_join(thdIDs[i], NULL);
        sumPoint += counts[i]; ; // The number of points in the circle
    }

    time(&end); // End counting time
    //*---------------------------------------*//

    double pi = 4.0*(double)sumPoint/(double)range/(double)NUM_THREAD;
    printf("%.5lf\n", pi);          // Print PI Number
    
    double time = difftime(end, start);
    printf("%.5lf(s)\n", time);    // Print time to excute

    pthread_exit(EXIT_SUCCESS);
}

void* calPI(void *arg) {
    // Initialize the pseudo number
    // Monte Carlo technique
    uint64_t* pcount = (uint64_t*)arg;
    unsigned int seed = rand()%30000;

    for(uint64_t i = 0; i < range; ++i) {
        // Create point
        double x = (double)rand_r(&seed)/(double)RAND_MAX;
        double y = (double)rand_r(&seed)/(double)RAND_MAX;
        // Calculator radius
        double r = sqrt(x*x + y*y);
        // Is it in a circle
        if(r <= 1) *pcount = *pcount + 1;
    }

    // End thread
    pthread_exit(EXIT_SUCCESS);
}

Chương trình chạy thử với 1 trăm triệu điểm chỉ còn 1 giây (ngày trước là 21s kkk)

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?