Kiểm tra số nguyên tố bằng cách tạo nhiều luồng(Multi Thread)

[honganh]

Vừa rồi mình thấy có rất nhiều bạn hỏi về việc phân rã hàm kiểm tra số nguyên tố ra thành nhiều luồng để tận dụng tối đa khả năng của bộ xử lý nhiều nhân. Mình thấy đây là một câu hỏi cũng khá hay và cũng có thể ứng dụng được trong thực tế nên quyết định làm một tút nhỏ về việc này.

Ý tưởng là ta phân rã phạm vi tìm số nguyên tố ra làm nhiều khoảng nhỏ và giao cho nhiều luồng xử lý song song. Nếu máy chỉ có 1 nhân thì việc này thậm chí còn tốn thời gian hơn bình thường vì chi phí chuyển đổi ngữ cảnh giữa các luồng. Nhưng nếu máy có nhiều vi xử lý thì tốc độ sẽ được cải thiện đáng kể.

Để tạo thread bạn dùng hàm CreateThread, tham số lpParameter bạn nên truyền vào con trỏ tới cấu trúc gồm có 2 phần tử là min và max, đó chính là cấu trúc lưu trữ 2 biên để tìm kiếm. Ngoài ra còn phải có một biến kết quả dùng chung để sau khi các thread kết thúc ta sẽ and các kết quả lại với nhau để ra kết quả tổng hợp.

Cuối cùng là code minh họa :

#include <windows.h>#include <math.h>#include <stdio.h>#include <conio.h> typedef struct _THREADSHAREDDATA{    unsigned long ThreadCounter;       unsigned long ThreadCounterMax; // tổng số thread    HANDLE hCallerThread;           // handler của thread gọi                   unsigned long Num;              // số cần kiểm tra     bool Ans;                       // kết quả trả về      } THREADSHAREDDATA; typedef struct _THREADPARAM{    unsigned long Min,Max;    THREADSHAREDDATA *pSharedData;} THREADPARAM; DWORD WINAPI ThreadProc(LPVOID lpParameter){    THREADPARAM *pThreadParam = (THREADPARAM *)lpParameter;    unsigned long i, min = pThreadParam->Min, max = pThreadParam->Max;    unsigned long num = pThreadParam->pSharedData->Num;    bool *pAns = &(pThreadParam->pSharedData->Ans);     // kiểm tra số nguyên tố    for (i=min;i<=max;i++)              {        if (((num % i) == 0) || !(*pAns))        {            (*pAns) &= false;            break;        }    }     // nếu thread cuối cùng kết thúc thì resume lại main thread    (pThreadParam->pSharedData->ThreadCounter)++;    if (pThreadParam->pSharedData->ThreadCounter == pThreadParam->pSharedData->ThreadCounterMax)    {        ResumeThread(pThreadParam->pSharedData->hCallerThread);    }     return 0;} bool IsPrimeNum(unsigned long num){    unsigned long k = (unsigned long)sqrt(num) + 1;    HANDLE hThread = OpenThread(THREAD_ALL_ACCESS,0,GetCurrentThreadId());    THREADSHAREDDATA ThreadSharedData;    THREADPARAM ThreadParam1, ThreadParam2;     ThreadSharedData.ThreadCounter = 0;    ThreadSharedData.ThreadCounterMax = 2;      // sẽ tạo ra 2 thread    ThreadSharedData.hCallerThread = hThread;    ThreadSharedData.Num = num;    ThreadSharedData.Ans = true;     ThreadParam1.Min = 2;    ThreadParam1.Max = k / 2;    ThreadParam1.pSharedData = &ThreadSharedData;    HANDLE hThread1 = CreateThread(NULL,0,ThreadProc,&ThreadParam1,0,NULL);     ThreadParam2.Min = ThreadParam1.Max + 1;    ThreadParam2.Max = k;    ThreadParam2.pSharedData = &ThreadSharedData;    HANDLE hThread2 = CreateThread(NULL,0,ThreadProc,&ThreadParam2,0,NULL);     SuspendThread(hThread);     CloseHandle(hThread1);     CloseHandle(hThread2);     CloseHandle(hThread);        return ThreadSharedData.Ans;} int main(int argc, char* argv[]){    unsigned long num;       printf("Nhap so can kiem tra : ");    scanf("%lu",&num);      if (IsPrimeNum(num))        printf("%lu la so nguyen to.
",num);    else        printf("%lu khong phai la so nguyen to.
",num);     getch();    return 0;}

View more random threads:

• Tìm hiểu về âm thanh và âm nhạc trong lập trình C ( Win32API)
• IAT Hooking
• GF GameFrameWork đơn giản cho dân gà.
• Một số kĩ thuật cơ bản với Irrlicht
• [Game Advanced Tetris và mã nguồn] - Những vấn đề xoay quanh CFW, API, MFC, CLR
• Tạo Thread và đa xử lý trong 1 chương trình
• Hỏi về hướng lập trình c++
• Các kỹ thuật optimize code của VC++ 200x Compiler
• Cách tạo và sử dụng Tab Control trong ứng dụng Dialog-Based
• Hướng dẫn viết một chương trình Sniffer

[datnguyen0312]

Mèo giải thích đi chớ. Chứ post code kiểu này ai hiểu???

[boybanhbeo]

Mèo tạo 2 thread, mỗi thread đưa vào threadParam.
struct này chưa min max để kiểm tra trong khoảng min max này có số nào là số nguyên tố hay không đó mà.

Về ý tưởng chính là thế.

Nhưng cũng rắc rồi quá, viết gì mà ko có comment [IMG]images/smilies/smile.png[/IMG]
À mà cái vụ share thread với tạo 2 thread riêng biệt có gì khác nhau ko Mèo ?

[vietkanpy]

@Zcoder : uhm, đề mèo comment lại
@kid : có chậm một tí nhưng cũng ko đáng kể lắm

[hongphuc]

Tớ chạy thử code của mèo thì bị báo 2 lỗi
OpenThread' : undeclared identifier
'initializing' : cannot convert from 'int' to 'void *'
vậy là sao nhỉ?[IMG]images/smilies/smile.png[/IMG]

[phongkhamkt1]

VC6 thì cần phải khai báo thêm hàm OpenThread, còn vc2k5 thì ok.

[minhhung211093]

bài viết hay lắm, đấy là tư duy của lập trình song song (parallel programming)
Chỉ có một chút xíu mình có ý kiến:
Trong system có 1 CPu thì giải thuật này vẫn nhanh hơn nhiều so với chỉ dùng 1 thread.
Còn đối với system có nhiều CPu thì giải thuật này gọi là tốt chứ chưa phải là rất tốt [IMG]images/smilies/smile.png[/IMG] . Lấy ví dụ có system 1 CPU 3GHz với system có 3 CPu 1GHz cùng chạy giải thuật này thì system có 3 CPu 1GHz vẫn chạy nhanh hơn nhưng chênh lệch thời gian không lớn, như vậy là vẫn chưa tận dụng được tốt 3 con Cpu song hành

Vài mạn bàn nho nhỏ,
Chúc các cậu học tập tốt

[vthao93hp]

Cám ơn anh đã góp ý. Bài nay em chỉ trình bày dưới dạng ý tưởng là chính thôi, còn việc áp dụng cụ thể thì tùy vào cấu hình máy. Nhiều cpu song song muốn khai thác hết cũng phải có ram riêng và bus riêng cho chúng nữa.

[hoahongden2525]

Kid nói đúng rồi đó Math. Mình chỉ bổ sung thêm là số luồng nếu quá nhiều trên 1 cpu thì lại chạy chậm đi vì thời gian đổi ngữ cảnh là lớn. Nếu số luồng hợp lý thì tổng thời gian process có được sẽ là nhiều nhất và process mau chạy tới kết quả nhất.

[caohoangnam114]

Tại sao chia ra nhiều thread mà chạy trên 1 cpu vẫn nhanh hơn chỉ chạy trên 1 thread.