Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 16 kết quả

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

  1. #1
    Ngày gia nhập
    07 2008
    Nơi ở
    /media/Anime
    Bài viết
    2,288

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

    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 :

    C++ Code:
    1. #include <windows.h>
    2. #include <math.h>
    3. #include <stdio.h>
    4. #include <conio.h>
    5.  
    6. typedef struct _THREADSHAREDDATA
    7. {
    8.     unsigned long ThreadCounter;  
    9.     unsigned long ThreadCounterMax; // tổng số thread
    10.     HANDLE hCallerThread;           // handler của thread gọi              
    11.     unsigned long Num;              // số cần kiểm tra
    12.     bool Ans;                       // kết quả trả về      
    13. } THREADSHAREDDATA;
    14.  
    15. typedef struct _THREADPARAM
    16. {
    17.     unsigned long Min,Max;
    18.     THREADSHAREDDATA *pSharedData;
    19. } THREADPARAM;
    20.  
    21. DWORD WINAPI ThreadProc(LPVOID lpParameter)
    22. {
    23.     THREADPARAM *pThreadParam = (THREADPARAM *)lpParameter;
    24.     unsigned long i, min = pThreadParam->Min, max = pThreadParam->Max;
    25.     unsigned long num = pThreadParam->pSharedData->Num;
    26.     bool *pAns = &(pThreadParam->pSharedData->Ans);
    27.  
    28.     // kiểm tra số nguyên tố
    29.     for (i=min;i<=max;i++)         
    30.     {
    31.         if (((num % i) == 0) || !(*pAns))
    32.         {
    33.             (*pAns) &= false;
    34.             break;
    35.         }
    36.     }
    37.  
    38.     // nếu thread cuối cùng kết thúc thì resume lại main thread
    39.     (pThreadParam->pSharedData->ThreadCounter)++;
    40.     if (pThreadParam->pSharedData->ThreadCounter == pThreadParam->pSharedData->ThreadCounterMax)
    41.     {
    42.         ResumeThread(pThreadParam->pSharedData->hCallerThread);
    43.     }
    44.  
    45.     return 0;
    46. }
    47.  
    48. bool IsPrimeNum(unsigned long num)
    49. {
    50.     unsigned long k = (unsigned long)sqrt(num) + 1;
    51.     HANDLE hThread = OpenThread(THREAD_ALL_ACCESS,0,GetCurrentThreadId());
    52.     THREADSHAREDDATA ThreadSharedData;
    53.     THREADPARAM ThreadParam1, ThreadParam2;
    54.  
    55.     ThreadSharedData.ThreadCounter = 0;
    56.     ThreadSharedData.ThreadCounterMax = 2;      // sẽ tạo ra 2 thread
    57.     ThreadSharedData.hCallerThread = hThread;
    58.     ThreadSharedData.Num = num;
    59.     ThreadSharedData.Ans = true;
    60.  
    61.     ThreadParam1.Min = 2;
    62.     ThreadParam1.Max = k / 2;
    63.     ThreadParam1.pSharedData = &ThreadSharedData;
    64.     HANDLE hThread1 = CreateThread(NULL,0,ThreadProc,&ThreadParam1,0,NULL);
    65.  
    66.     ThreadParam2.Min = ThreadParam1.Max + 1;
    67.     ThreadParam2.Max = k;
    68.     ThreadParam2.pSharedData = &ThreadSharedData;
    69.     HANDLE hThread2 = CreateThread(NULL,0,ThreadProc,&ThreadParam2,0,NULL);
    70.  
    71.     SuspendThread(hThread);
    72.  
    73.     CloseHandle(hThread1);
    74.     CloseHandle(hThread2);
    75.     CloseHandle(hThread);  
    76.  
    77.     return ThreadSharedData.Ans;
    78. }
    79.  
    80. int main(int argc, char* argv[])
    81. {
    82.     unsigned long num;
    83.    
    84.     printf("Nhap so can kiem tra : ");
    85.     scanf("%lu",&num);
    86.  
    87.  
    88.     if (IsPrimeNum(num))
    89.         printf("%lu la so nguyen to.\n",num);
    90.     else
    91.         printf("%lu khong phai la so nguyen to.\n",num);
    92.  
    93.     getch();
    94.     return 0;
    95. }
    Đã được chỉnh sửa lần cuối bởi meoconlongvang : 19-11-2008 lúc 10:18 PM.
    Càng yêu mèo thì mèo càng mập. Mèo càng mập ta lại càng yêu.

  2. #2
    Ngày gia nhập
    01 2008
    Nơi ở
    Gameloft Studio
    Bài viết
    294

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

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    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
    À mà cái vụ share thread với tạo 2 thread riêng biệt có gì khác nhau ko Mèo ?

  4. #4
    Ngày gia nhập
    07 2008
    Nơi ở
    /media/Anime
    Bài viết
    2,288

    @Zcoder : uhm, đề mèo comment lại
    @kid : có chậm một tí nhưng cũng ko đáng kể lắm
    Càng yêu mèo thì mèo càng mập. Mèo càng mập ta lại càng yêu.

  5. #5
    Ngày gia nhập
    05 2008
    Bài viết
    5

    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ỉ?

  6. #6
    Ngày gia nhập
    07 2008
    Nơi ở
    /media/Anime
    Bài viết
    2,288

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

    VC6 thì cần phải khai báo thêm hàm OpenThread, còn vc2k5 thì ok.
    Càng yêu mèo thì mèo càng mập. Mèo càng mập ta lại càng yêu.

  7. #7
    Ngày gia nhập
    08 2006
    Nơi ở
    TpHCM
    Bài viết
    202

    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 . 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

  8. #8
    Ngày gia nhập
    07 2008
    Nơi ở
    /media/Anime
    Bài viết
    2,288

    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.
    Càng yêu mèo thì mèo càng mập. Mèo càng mập ta lại càng yêu.

  9. #9
    Ngày gia nhập
    07 2007
    Nơi ở
    TP.HCM
    Bài viết
    199

    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.

  10. #10
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    [Math] Hơi khó giải thích.

    Cậu tưởng tượng thế này, trong 1 chu kì, OS sẽ cho chạy lần lượt các process ( và các thread tách biệt của process đó ).

    Nếu 1 thread thì trong 1 chu kì nó chỉ chạy 1 lần.
    Nếu n thread thì trong 1 chu kì nó chạy được n lần.

    Có thể hiểu vậy, dù không hoàn toàn đúng.

Các đề tài tương tự

  1. Xin tài liệu Multi Thread
    Gửi bởi mrarsenal10 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 14-04-2013, 11:30 PM
  2. Tài liệu về multi thread trong C/C++?
    Gửi bởi thansautk trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 7
    Bài viết cuối: 19-03-2013, 01:21 PM
  3. Giới thiệu thread và multi thread trong lập trình C#
    Gửi bởi dieucay555 trong diễn đàn Tutorials và Thủ thuật lập trình C#, ASP.NET
    Trả lời: 2
    Bài viết cuối: 26-07-2011, 06:16 PM
  4. Rắc rối với multi thread trong việc thu/phát âm.
    Gửi bởi Joker trong diễn đàn Thắc mắc chung
    Trả lời: 1
    Bài viết cuối: 29-03-2011, 10:14 PM
  5. Xử lý Multi Thread trên C#?
    Gửi bởi vodanh1369 trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 10
    Bài viết cuối: 15-04-2010, 08:01 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn