Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: Giải thuật song song | Thảo luận về các giải thuật song song

  1. #1
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Mặc định Giải thuật song song | Thảo luận về các giải thuật song song

    Thân chào các bạn! Trong topic này mình đưa ra ý tưởng cùng thảo luận và trao đổi với nhau về giải thuật song song với nội dung như sau:

    1. Tổng quan về tính toán song song
    2. Một số giải thuật song song cho các bài toán cụ thể.

    trước hết mình đi vào phần 1 với các giới thiệu cơ bản:

    1. Khái niệm tính toán song song và phân tán (parallel and distributed computing): tính toán song song và phân tán là một dạng tính toán hiệu năng cao (high performance computing) bằng cách tận dụng sức mạnh tính toán của một tập các máy tính hoặc bộ xử lý được kết nối thông qua các hệ thống mạng chuyên dụng (tốc độ rất cao) hoặc mạng thông thường (TCP/IP chẳng hạn).

    2. Các hệ thống song song: có rất nhiều các hệ thống song song khác nhau được phân loại theo cấu trúc, theo chức năng hoặc theo sức mạnh tính toán. Sau đây là một số ví dụ về các hệ thống tính toán song song:
    - Cray T3E (massively parallel processors)
    - IBM RS/6000 SP2 (distributed memory system)
    - Sun Fire 15000 (shared memory system)
    - Cray SV1 (massively parallel processors)
    - PC-Cluster (một tập các máy PC được kết nối lại với nhau thông qua mạng chuyên dụng hoặc mạng thông thường). Cái này ở Bộ môn CHTTT cũng có, nếu em muốn thử nghiệm, em hãy liên lạc với thầy giáo Hà Quang Thụy (hqthuy@hn.vnn.vn)

    3. Môi trường lập trình: môi trường lập trình song song được chia làm hai mức như sau:
    - Mức hệ thống: thường là một phần mềm hệ thống chạy ở background nhằm thực hiện các chức năng trong tính toán song song như quản lý tiến trình (task management), truyền thông (communication), đồng bộ hóa (synchronization), .v.v. Mức này còn cung cấp thư viện bao gồm các hàm về truyền thông, đồng bộ hóa, .v.v. Em có thể liên kết các hàm thư viện này vào trong chương trình của em khi viết các chương trình song song. Hiện nay có khá nhiều phần mềm hỗ trợ tính toán song song như MPI (Message Passing Interface), PVM (Parallel Virtual Machine), .v.v. Em có thể vào google.com để search và download các phần mềm này về vì chúng được cung cấp miễn phí và lại có cả mã nguồn mở.
    - Mức thứ hai không thể thiếu được là ngôn ngữ lập trình song song: Em có thể sử dụng C/C++ để lập trình song song, tất nhiên khi biên dịch thì em phải thông qua một tiện ích biên dịch do MPI hoặc PVM cung cấp. Em cũng có thể dịch theo cách thông thường miễn là em liên kết thành công các hàm thư viện song song của MPI hoặc PVM là được. Em cũng có thể sử dụng ngôn ngữ FORTRAN (fortran 77 hoặc fortran 90) hoặc HPF (High Performance Fortran) để lập trình song song.

    4. Ứng dụng của tính toán song song: Hầu hết các ứng dụng của tính toán song song là nhằm giải quyết các bài toán có độ phức tạp thời gian lớn hoặc những bài toán thời gian thực (real-time applications). Sau đây là một số ví dụ:
    - Tính toán trong vật lý và hóa học: mô phỏng các quá trình nhiệt học, mô phỏng chuyển động các hạt cơ bản trong vật lý, mô phỏng các quá trình hóa học, .v.v.
    - Tính toán trong sinh học: hiện nay có một lĩnh vực đang được giới nghiên cứu focus, đó là tin sinh (bioinformatics). Bài toán này chủ yếu phân tích thông tin di truyền ADN. Bài toán phân tích và mô hình hóa bản đồ gen người cũng không thể không sử dụng các máy tính hiệu năng cao, trong đó có các hệ thống tính toán song song rất mạnh.
    - Trò chơi: Chăc em cũng biết máy tính DeepBlue của IBM? Máy tính này có khả năng tính toán hàng triệu nước cờ trong một giây và đây là một hệ thống song song sử dụng môi trường lập trình MPI đấy.
    - Tính toán song song áp dụng trong khám phá tri thức từ cơ sở dữ liệu (Knowledge Discovery from Databases - KDD & Data Mining)
    - .v.v. Còn rất nhiều ứng cụng khác của tính toán song song mà anh không thể kể hết ra đây được.

    5. Các mô hình và thuật toán song song:
    - Về mô hình song song thì người ta chia ra các dạng chính sau đây: SIMD (Đơn dòng lệnh, đa dữ liệu - Single Instruction Multiple Data); MISD (Đa dòng lệnh, đơn dữ liệu - Multiple Instruction Single Data); MIMD (Đa dòng lệnh, đa dữ liệu - Multiple Instructions Multiple Data).
    - Thuật toán song song thì rất đa dạng, mỗi bài toán có một chiến lược song song riêng. Tuy nhiên, người ta khái quát hóa được hai chiến lược chính là song song theo chức năng và song song theo dữ liệu.

    Thời gian có hạn nên mình chỉ giới thiệu được chừng này, các bạn có thể vào các tạp chí hàng đầu về tính toán song song và phân tán sau đây để nghiên cứu thêm.

    Ref Links Code:

  2. #2
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Bây giờ mình đưa ra thảo luận về các giải pháp song song hóa các giải thuật tuần tự
    mong các bạn quan tâm thảo luận

    Mở đầu
    Trong rất nhiều chiến lược khác nhau để song song hoá thuật toán tuần tự có ba
    chiến lược thiết kế chương trình song song tương đối phổ biến là song song hoá kết quả, song song hoá đại diện và song song hoá chuyên biệt. Mặc dù, trong từng bài toán cụ thể việc kết hợp các chiến lược thiết kế có thể cho ta kết quả thú vị, song thông thường tuỳ thuộc tính chất bài toán chỉ một chiến lược thiết kế thuật toán song song được chọn nhằm đạt hiệu quả cao nhất. Trong phần đầu chúng tôi trình bày ba chiến lược thiết kế nêu trên. Phần thứ hai chúng tôi trình bày môi trường Parallel Virtual
    Machine (PVM) được dùng trong quá trình thử nghiệm bài toán sinh ra số nguyên tố trong thuật toán mã hoá RSA . Tiếp theo chúng tôi trình bày một số thử nghiệm và kết quả của nó.
    1. Các chiến lược song song hoá phổ biến
    1.1 Song song hoá kết quảViệc phân loại các chiến lược thiết kế thuật toán song song phụ thuộc vào tính
    chất bài toán. Song song hoá kết quả (xem [1]) là cơ chế tính toán song song tập trung trên toàn bộ dữ liệu của bài toán. Mỗi bộ xử lý sẽ cho một phần kết quả của bài toán và các bộ xử lý hoạt động song song sao cho các phần việc được thực hiện độc lập tối đa có thể. Sau khi các phần việc hoàn thành, công đoạn cuối cùng là kết hợp các thành phần để được kết quả hoàn chỉnh. Các lớp bài toán chia - để - trị, bảng đen (trong hệ chuyên gia) và lơi - lặp (iterative relaxtion) thường sử dụng chiến lược song song hoá kết quả để thiết kế chương trình song song.
    Mỗi bài toán trong lớp các bài toán chia-để -trị (xem [2]) thường được chia thành
    các bài toán thành phần. Mỗi bài toán thành phần được giải quyết độc lập và kết quả cuối cùng là sự kết hợp các kết quả của bài toán thành phần.
    Trong hệ thống bảng đen (xem [3]) cấu trúc dữ liệu thể hiện mô hình tính toán.
    Mỗi bộ xử lý độc lập có trách nhiệm quản lý, kiểm tra trạng thái hiện thời và cập nhật nó nếu cần.
    Trong lơi - lặp (xem [4]) người ta chia không gian dữ liệu thành các vùng có
    quan hệ láng giềng, mỗi vùng này được một hay nhiều bộ vi xử lý đảm nhiệm. Mỗi bộ vi xử lý này đảm trách công việc theo từng vùng song song và khi cần có sự truyền thông điệp với các láng giềng.
    Việc thiết kế chương trình theo chiến lược song song hoá kết quả thông qua năm
    giai đoạn. Giai đoạn đầu cần phải mô hình kết qủa dưới dạng cấu trúc dữ liệu gồm
    nhiều thành phần, đồng thời xác định được sự phụ thuộc giữa chúng. Giai đoạn hai, phân mỗi bộ xử lý đảm nhiệm công việc cho một hay nhiều thành phần và việc phân chia này phải bảo đảm vấn đề hiệu suất của các bộ xử lý. Giai đoạn ba, xác định nguồn tài nguyên cần thiết để thực hiện việc tính toán các thành phần. Bước tiếp theo xác định cách lấy các giá trị kết quả của các thành phần khi thực hiện xử lý song song.
    Cuối cùng, là giai đoạn kết hợp các kết quả thành phần để được kết quả bài toán và kết thúc các xử lý.

    1.2 Song song hoá đại diện
    Thiết kế chương trình theo cơ chế song song hoá đại diện xác định cụ thể công
    việc phải thực hiện để song song hoá. Như vậy, để giải quyết một bài toán có nhiều công đoạn, mỗi công đoạn của bài toán được giải quyết song song cho đến khi hoàn thành công đoạn đó và các công đoạn tiếp theo cũng được thực hiện tương tự cho đến khi bài toán được giải quyết. Các mô hình của chiến lược này là chủ - tớ, tính toán -
    tổng hợp - truyền thông.
    Trong mô hình chủ - tớ (xem [4]) bài toán cần giải được chia thành các vấn đề
    phụ thuộc lẫn nhau. Các bộ xử lý đóng vai trò tớ trong mô hình có nhiệm vụ xử lý các vấn đề này và giữa chúng được điều phối bởi bộ xử __________lý đóng vai trò chủ. Khác với phương pháp chia - để - trị, các vấn đề ở đây không nhất thiết cùng được tiến hành giải quyết, mà có thể được giải quyết song song một cách tuần tự.
    Trong mô hình tính toán - tổng hợp - truyền thông (xem [2]) thiết kế bao gồm ba
    giai đoạn. Giai đoạn tính toán thực hiện các tính toán cơ bản có tính chất cục bộ, giai đoạn tổng hợp kết hợp các dữ liệu cục bộ thành dữ liệu toàn cục, giai đoạn truyền thông trả lại các thông tin toàn cục cho các bộ xử lý.
    Việc thiết kế chương trình theo chiến lược song song hoá đại diện được thực hiện
    thông qua ba giai đoạn. Giai đoạn đầu xác định các công việc cần phải thực hiện bởi các bộ xử lý. Trong giai đoạn tiếp theo cần phải xác định bộ xử lý đóng vai trò điều khiển các công việc.Cuối cùng cần phải nhận biết được kết quả công việc.
    1.3 Song song hoá chuyên biệt

    Trong chiến lược song song hoá chuyên biệt, bài toán cần giải quyết bao gồm
    nhiều công việc, mỗi công việc có đặc thù riêng được giao cho một bộ xử lý chuyên dụng. Ngoài ra hệ thống cần một bộ xử lý giữ vai trò agent, điều phối quá trình thực hiện công việc. Trong mỗi công việc đặc thù, các phần việc nhỏ hơn được thực hiện
    song song. Sau khi các phần việc này hoàn thành, cần tiến hành “phối hợp” các kết quả để hoàn thành công việc.
    Một số mô hình thường gặp trong chiến lược thiết kế này là: ống dẫn và bộ lọc,
    khách -phục vụ.
    Trong mô hình ống dẫn và bộ lọc (xem [3]) dòng dữ liệu kết quả ra của quá trình
    xử lý A là dữ liệu vào của quá trình xử lý B.
    Trong mô hình khách - phục vụ (xem [4]) các yêu cầu từ các bộ xử lý đóng vai
    trò khách được gửi đến các bộ xử lý đóng vai trò phục vụ để xử lý.
    2. Parallel Virtual Machine (PVM)
    PVM là tập hợp phần mềm công cụ và thư viện kết hợp các máy tính khác nhau
    về cấu hình như một máy ảo. Mục tiêu chính của hệ thống PVM là tăng hiệu suất tính toán bằng cách kết hợp các máy tính thông qua xử lý song song trên các máy tính.
    Hệ thống PVM gồm hai thành phần chính. Thứ nhất là tiến trình thường chú
    (daemon) thường gọi là pvmd3 hay pvmd chạy trên tất cả các máy tính thành viên của máy tính song song ảo. Để thực hiện ứng dụng PVM, trước hết tạo ra một máy ảo bằng cách chạy PVM. Khi đó ứng dụng PVM sẽ được khởi động trên tất cả các máy tính thành viên. Thứ hai là thư viện các hàm giao diện PVM thường gọi là libPVM3.a.
    Thư viện gồm các hàm phục vụ cho việc truyền thông điệp, sinh tiến trình, phối hợp công việc v…v.
    Mô hình tính toán PVM dựa trên khái niệm một ứng dụng bao gồm nhiều công
    việc. Hai phương pháp thường được PVM sử dụng là song song hoá chức năng và
    song song hoá dữ liệu. Phương pháp song song các chức năng, ứng dụng bao gồm
    nhiều chức năng, các chức năng được thực hiện song song. Phương pháp song song hoá dữ liệu các tiến trình xử lý như nhau nhưng mỗi tiến trình chỉ xử lý một phần dữ liệu của ứng dụng.
    Hệ thống PVM hỗ trợ ngôn ngữ lập trình C, Fortran và C++. Trong đó ngôn ngữ
    C++ được sử dụng phổ biến nhất. Các thử nghiệm của chúng tôi cũng sử dụng ngôn ngữ C++.
    2.1 Đặc điểm môi trường PVM• Khả năng cấu hình các máy: Các công việc thực hiện trên các máy được lựa
    chọn bởi chính người dùng khi thực hiện PVM. Trong quá trình tính toán,
    việc thêm hay bớt các máy thành viên thực hiện rất dễ dàng.
    • Khả năng truy nhập đến cấu hình phần cứng cho phép người dùng có thể chọn
    các máy thành viên phù hợp trong quá trình tính toán.
    • Tính toán dựa trên bộ xử lý: Đơn vị của PVM là công việc, nhiều công việc
    có thể thực hiện trên một bộ xử lý,có một luồng điều khiển tuần tự độc lập
    thực hiện việc chuyển đổi giữa quá trình truyền thông và tính toán.
    • Sử dụng mô hình truyền thông điệp: Điều phối việc truyền thông giữa các
    máy thành viên qua việc gửi/nhận thông điệp.
    • Hỗ trợ mạng hỗn tạp: Cho phép các máy thành viên có cấu hình khác nhau,
    hỗ trợ nhiều bộ xử lý.
    2.2 Nguyên lý hoạt động
    Thông thường chương trình được viết trên PVM qua các bước khởi tạo các tiến
    trình, quản lý truyền thông điệp, tính toán, tổng hợp kết quả và hiện thị chúng, kết
    thúc các tiến trình.
    • Khởi tạo tiến trình
    Mỗi tiến trình trong hệ thống PVM được định danh bởi một số nguyên do pvmd
    cung cấp. Hàm pvm_mytid() thực hiện công việc này. Nó kết nạp tiến trình vào hệ thống PVM nếu chúng chưa được kết nạ__________p. Hàm pvm_spawn(char *task, char
    **argv, int flag, char *where, int intask, int *tids) sinh ra các bản sao của tiến trình cho bởi tham số task trên máy ảo. Danh sách các đối số của tiến trình đó thông qua tham số argv. Cờ flag cho một số tuỳ chọn đặc biệt, thường sử dụng giá trị mặc định cho phép PVM tự xác định nơi khởi tạo tiến trình.Hàm trả về số nguyên cho biết số lượng các tiến trình được khởi tạo thành công, hoặc mã lỗi trong trường hợp ngược
    lại.Nếu thành công tham số tids danh sách các số nguyên định danh tiến trình.
    • Quản lý truyền thông điệp
    Quá trình gửi thông điệp trong hệ thống PVM gồm ba giai đoạn. Đầu tiên một
    vùng đệm được khởi tạo thông qua hàm pvm_initsend(int encoding) sẽ tạo ra vùng đệm dành cho dữ liệu mới. Giai đoạn tiếp theo thông điệp được nạp vào vùng đệm thông qua hàm pvm_pk*(). Tùy vào kiểu dữ liệu nạp vào vùng đệm, PVM xây dựng hàm tương ứng, ví dụ pvm_pkint() dành cho dữ liệu kiểu nguyên, pvm_pkfloat() dành cho kiểu thực. Công đoạn cuối cùng là việc thực hiện gửi thông điệp đến tiến trình khác thông qua hàm pvm_send(int tid, int msgtag) gửi thông điệp định danh bởi msgtag đến tiến trình định danh bởi tid.
    Quá trình nhận thông điệp được thực hiện thông qua hàm pvm_recv(int tid, int
    msgtag). Sau khi nhận thông điệp, dữ liệu được lấy ra từ vùng đệm thông qua hàm
    pvm_upk*(). Cần phải sử dụng hàm phù hợp với kiểu dữ liệu, ví dụ pvm_upkint() dùng cho kiểu dữ liệu kiểu nguyên, pvm_upkfloat() dùng cho dữ liệu kiểu thực.
    • Kết thúc tiến trình
    Trong quá trình hoạt động PVM cho phép loại bỏ tiến trình khi tiến trình đã thực
    hiện xong công việc hoặc không cần thiết nữa thông qua hàm pvm_exit(), cho tiến
    trình thường trú pvmd biết rằng tiến trình đó được loại khỏi hệ thống PVM.
    3. Thử nghiệm, so sánh các chiến lược song song hoáTrong quá trình thực hiện đề tài “Xử lý song song trên PVM ứng dụng trong bài
    toán bảo mật”. Chúng tôi có sử dụng thuật toán RSA để mã hoá. Vấn đề mấu chốt của thuật toán RSA là việc sinh ra các số nguyên tố. Trong quá trình thử nghiệm chúng tôi thực hiện cài đặt bài toán tìm số nguyên tố theo ba chiến lược trên. Giải thuật mà chúng tôi dùng là giải thuật “sàng Eratosthenes”.
    Giải thuật sàng Eratosthenes:
    Bước 1: Nhập 1.. n
    Bước 2 : Loại bỏ 1
    Bước 3: Lặp các bước sau đây cho đến căn bậc hai của n
    Bước 3.1: Tìm tiếp số đầu chưa loại bỏ, kí hiệu p, nếu tìm được p là số
    nguyên tố
    Bước 3.2: Loại bỏ các số là bội của p kể từ p2
    3.1 Sử dụng chiến lược song song hoá kết quả
    Chúng tôi dùng mảng logic để kiểm tra số nguyên tố. Phần tử đầu tiên của mảng
    biểu diễn cho số 1, phần tử thứ 2 biểu diễn cho số 2, tiếp tục như vậy. Nếu phần tử có giá trị là true thì số ứng với phần tử đó là số nguyên tố và ngược lại.
    Tiến trình cha khởi tạo mảng, sinh các tiến trình con xử lý mỗi phần tử của mảng,
    các tiến trình con này có nhiệm vụ kiểm tra số ứng với vị trí của phần tử đó có phải là số nguyên tố hay không, sau đó tiến trình cha có nhiệm vụ tập hợp kết quả để hiển thị.
    C Code:
    1. #define MAX 100000
    2. #define TRUE 1
    3. #define FALSE 0
    4. void main(){
    5.     int kq[MAX],tid,tids[MAX-2],i,num,res;
    6.     (void) pvm_mytid() // Khởi tạo tiến trình
    7.     kq[0]=FALSE;kq[1]=TRUE;
    8.     //Sinh tiến trình con
    9.     (void) pvm_spawn(“nguyento”,(char**)0,0,””,MAX-2,tids);
    10.     //Gửi cho các tiến trình con để kiểm tra
    11.     for(i=2;i<MAX;i++){
    12.         pvm_intsend(PvmDataRaw);
    13.         pvm_pkint(&i,1,1);
    14.         pvm_send(tids[i],1);
    15.     }
    16.     //Nhận kết quả
    17.     for(i=2;i<MAX;i++){
    18.         pvm_recv(-1,2);
    19.         pvm_upkint(&num,1,1); pvm_upkint(&res,1,1);
    20.         kq[num]=res;
    21.     }
    22.     //Hiển thị kết quả
    23.     for(i=0;i<MAX;i++)
    24.         if(kq[i]) printf(%d”,i);
    25.         pvm_exit()// Kết thúc tiển trình
    26.     exit(0);
    27. }
    Mỗi tiến trình con sẽ là nhiệm vụ kiểm tra và trả lại giá trị TRUE nếu đúng là số
    nguyên tố và ngược lại.
    C Code:
    1. #define TRUE 1
    2. #define FALSE 0
    3. void main(){
    4.     int p_tid,i,num,res;
    5.     p_tid=pvm_parent(); //Nhận số định danh tiến trình
    6.     //Nhận dữ liệu
    7.     pvm_recv(p_tid,1);pvm_upkint(&num,1,1);
    8.     //Kiểm tra số nguyên tố
    9.     res=TRUE;i=2;
    10.     while(res &&(i<sqrt(num)){
    11.         res &&=((num %i)!=0);
    12.         i++;
    13.     }
    14.     //Gửi kết quả
    15.     pvm_initsend(PvmDataRaw);
    16.     pvm_pkint(&num,1,1);pvm_pkint(&res,1,1);
    17.     pvm_send(p_tid,2);
    18.     pvm_exit();
    19.     exit(0);
    20. }
    3.2 Sử dụng chiến lược song song hoá đại diện
    Cũng giống như chiến lược trên, chúng tôi cũng dùng mảng logic để kiểm tra số
    nguyên tố.Phần tử đầu tiên của mảng biểu diễn cho số 1, phần tử thứ 2 biểu diễn cho số 2, tiếp tục như vậy. Nếu phần tử có giá trị là true thì số ứng với phần tử đó là số nguyên tố và ngược lại. Tuy nhiên chỉ có một số lượng nhỏ các tiến trình kiểm thực hiện công việc kiểm tra, sau khi kiểm tra xong, các tiến trình này tiếp tục kiểm tra các
    phần tử khác.
    C Code:
    1. #define MAX 100000
    2. #define NPROCS 3
    3. #define TRUE 1
    4. #define FALSE 0
    5. void main()
    6. {
    7.     int kq[MAX],tids[NPROCS],bufid,msgtag,msglength,msgsrc,from,upto;
    8.     int allocated=2,halt=0;
    9.     (void) pvm_mytid();//Khởi tạo tiến trình
    10.     kq[0] = FALSE; kq[1] = TRUE;
    11.     //Sinh tiến trình
    12.     (void) pvm_spawn (“nguyento”,(char **) 0,0,””,NPROCS,tids);
    13.     while(NPROCS>0)
    14.     {
    15.         bufid = pvm_recv (-1,-1);
    16.         pvm_bufinfo(bufid,&msglength,&msgtag,&msgsrc);
    17.         switch(msgtag)
    18.         {
    19.             case REQUESTTAG :
    20.             pvm_initsend(PvmDataRaw);
    21.             pvm_pkint(&allocated, 1, 1);
    22.             pvm_send(msgsrc,2);
    23.             if (allocated < MAX)
    24.             allocated += 100;
    25.             else
    26.             halted++;
    27.             break;
    28.             case RESULTTAG :
    29.             // Nhận dữ liệu
    30.             pvm_unpkint(&from, 1, 1);
    31.             pvm_unpkint(&upto, 1, 1);
    32.             if ((from < upto) && (upto < MAX))
    33.             pvm_unpkint((&kq) + from, from - upto + 1, 1);
    34.             break;
    35.         };
    36.     }
    37.     // Hiển thị kết quả
    38.     for(int i = 0; i < MAX; i++)
    39.     if(kq[i])
    40.     printf ("%d ", i);
    41.     pvm_exit();
    42.     exit(0);
    43. }
    Đối với các tiến trình con, thực hiện kiểm tra số nguyên tố, sau khi kiểm tra xong
    gửi kết quả cho tiến trình cha và nhận các phần tử tiếp theo để thực hiện.
    C Code:
    1. #define TRUE 1
    2. #define FALSE 0
    3. void main()
    4. {
    5.     int ptid,num,kq[100],dum,task_end,i;
    6.     int task_start=0;
    7.     ptid = pvm_parent();
    8.     while(task_start < MAX)
    9.     {
    10.         // Gửi yêu cầu nhận số mới để kiểm tra
    11.         pvm_initsend(PvmDataRaw);
    12.         pvm_pkint(&dum,1, 1);
    13.         pvm_send(ptid, 1);
    14.         pvm_recv(ptid,2);
    15.         pvm_upkint(&task_start,1, 1);
    16.         if (task_start<MAX)
    17.         {
    18.             task_end = task_start + 100;
    19.             if (task_end > MAX)
    20.             task_end = MAX;
    21.             for (num= task_start; num < task_end; num++)
    22.             {
    23.                 kq[num - task_start] = TRUE;
    24.                 i = 2;
    25.                 while(kq[num - task_start] && (i < sqrt (num)))
    26.                 {
    27.                     kq[num - task_start] &&= ((num % i) != 0);
    28.                     i++;
    29.                 }
    30.             }
    31.             // Gửi kết quả cho tiến trình cha
    32.             pvm_initsend (PvmDataRaw);
    33.             pvm_pkint (&task_start, 1, 1);
    34.             pvm_pkint (&task_end, 1, 1);
    35.             pvm_pkint (kq, task_end - task_start + 1, 1);
    36.             pvm_send (ptid, 3);
    37.         }
    38.     }
    39.     pvm_exit();
    40.     exit(0);
    41. }
    3.3 Sử dụng chiến lược song song hoá chuyên biệt
    Trong chiến lược này, chúng tôi khởi tạo các tiến trình kiểm tra số nguyên tố.
    Các số được tiến trình chính chuyển cho các tiến trình con để kiểm tra. Nếu số đó
    không phải là số nguyên tố, tiến trình tiếp tục kiểm tra số tiếp theo, nếu số đó là số
    nguyên tố và tiến trình khác chưa kiểm tra số đó thì sẽ kết nạp số đó vào tập kết quả.Nếu đã có tiến trình khác đã chọn số đó, tiến trình này sẽ tiếp tục kiểm tra như đã làm với tiến trình trước.
    C Code:
    1. #define MAX 100000
    2. #define TRUE 1
    3. #define FALSE 0
    4. void main()
    5. {
    6.     int kq[MAX],tid,num,i;
    7.     (void) pvm_mytid();//Khởi tạo tiến trình
    8.     (void) pvm_spawn (“nguyento”,(char**)0,0,””,1, &tid);
    9.     for (num = 2; number <= MAX; num++)
    10.     {
    11.         pvm_initsend (PvmDataRaw);
    12.         pvm_pkint (&num, 1, 1);
    13.         pvm_send (tid,1);
    14.     }
    15.     // Nhận kết quả
    16.     pvm_recv (tid,2);
    17.     pvm_unpkint (&num,1,1);
    18.     pvm_unpkint (kq,num + 1, 1);
    19.     kq[0] = FALSE;
    20.     //Hiển thị kết quả
    21.     for (i = 0; i < (num + 1), i++)
    22.         printf ("%d ", kq[i]);
    23.     pvm_exit();
    24.     exit(0);
    25. }
    Các tiến trình con thực hiện việc kiểm tra, đồng thời các tiến trình động được
    PVM được tạo ra khi có yêu cầu.
    C Code:
    1. #define MAX 100000
    2. #define TRUE 1
    3. #define FALSE 0
    4. void main()
    5. {
    6.     int ptid,ngto,n,kq[MAX];
    7.     int next_tid = 0;
    8.     int length = 0;
    9.     ptid = pvm_parent();
    10.     pvm_recv(ptid,1);
    11.     pvm_unpkint(&ngto, 1, 1);
    12.     while (n < MAX)
    13.     {
    14.         //Nhận số nguyên mới để kiểm tra
    15.         pvm_recv (ptid,1);
    16.         pvm_unpkint(&n, 1, 1);
    17.         if (n < MAX)
    18.         {
    19.             if ((n % ngto) != 0)
    20.             {
    21.                 if (!next_tid)
    22.                 //Tạo tiến trình mới
    23.                 pvm_spawn(“nguyento”,(char**)0,0,””,1,&next_tid);
    24.                 pvm_initsend(PvmDataRaw);
    25.                 pvm_pkint(&n,1, 1);
    26.                 pvm_send(next_tid, 1);
    27.             }
    28.         }
    29.     }
    30.     if (next_tid)
    31.     {
    32.         pvm_initsend(PvmDataRaw);
    33.         pvm_pkint(&n, 1, 1);
    34.         pvm_send(next_tid,1);
    35.         pvm_recv(next_tid, 2);
    36.         pvm_unpkint(&length, 1, 1);
    37.         pvm_unpkint((kq + 1), length, 1);
    38.     }
    39.     kq[0] = ngto;
    40.     length++;
    41.     pvm_initsend(PvmDataRaw);
    42.     pvm_pkint(&length, 1, 1);
    43.     pvm_pkint(kq,length, 1);
    44.     pvm_send(ptid,2);
    45.     pvm_exit();
    46.     exit(0);
    47. }
    3.d Nhận xét
    Chúng tôi tiến hành thử nghiệm trên ba máy tính Với các cấu hình Pentium IV
    2.4 Mhz bộ nhớ 512MB, Pentium III 750 Mhz bộ nhớ 256 MB và Xeron 1.7Mhz bộ
    nhớ 128MB. Sử dụng chiến lược song song hoá kết quả, chương trình thực hiện hiệu
    quả nhất. Tuy nhiên do dữ liệu chương trình nhỏ nên sử dụng các chiến lược này
    chưa cho hiệu quả chênh lệch rõ rệt. Về phương diện cài đặt, cài đặt chương trình theo
    chiến lược song song hoá kết quả dễ dàng hơn so với song song hoá đại diện và song
    song hoá chuyên biệt.

    4. Kết luậnĐể song song hóa thuật toán tuần tự có rất nhiều chiến lược, để cho hiệu quả cần
    phải chọn chiến lược phù hợp với thuật toán. Trong quá trình thực hiện thực hiện đề tài
    “Xử lý song song trên PVM ứng dụng trong bài toán bảo mật” chúng tôi đã thử
    nghiệm một số chiến lược tiếp cận khác nhau để tìm ra chiến lược phù hợp nhất bài
    toán của mình.
    Đã được chỉnh sửa lần cuối bởi Kevin Hoang : 10-09-2011 lúc 11:21 AM.

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    tiếp theo là một vài thảo luận để song song hóa bài toán nhân ma trận

    Bài toán yêu cầu thực hiện phép nhân hai ma trận A=lxm và B=mxn để thu được ma trận kết quả C=lxn. Cách giải quyết trực tiếp trên một máy tính là dùng các vòng lặp:
    C Code:
    1. for (i=0; i<l; i++)
    2.     for (j=0; j<m; j++)
    3.     for (k=0; k<n; k++)
    4.         C[i][j] += a[i][k] * b[k][j]
    Với đầu vào l, m, n rất lớn, dữ liệu cần cho việc tính toán có thể vượt quá dung lượng của cache, khi đó tốc độ thực hiện phép nhân sẽ giảm đi rất nhiều. Chúng ta có thể cải thiện phương pháp trên bằng cách thực hiện phép nhân với từng phần của ma trận, sau đó gộp kết quả lại để thu được kết quả cuối cùng. Việc này giúp cho khối lượng dữ liệu trong một lần tính toán vừa với kích thước của cache. Trong đoạn mã dưới đây, chúng ta giới hạn kích thước của một lần thực hiện phép nhân ma trận bằng hằng số THRESHOLD.

    Giải thuật mm
    Mã nguồn của phương thức nhân ma trận dùng giải thuật mm như sau:
    C Code:
    1. /* Matrix multiplication */
    2. /* source code from Quinn's book */
    3. #define N 10000
    4. #define THRESHOLD 65535
    5.  
    6. double a[N][N], b[N][N], c[N][N];
    7.  
    8.  
    9. void mm(int crow, int ccol , /* góc của block C*/
    10.         int arow, int acol , /* góc of A block*/
    11.         int brow, int bcol , /* góc of B block*/
    12.         int l,          /* block A is l x m*/
    13.         int m,          /* block B is m x n*/
    14.         int n)          /* block C is l x n*/
    15. {
    16.  
    17.         int lhalf[3], mhalf[3], nhalf[3]; /*kích thước của khối 1/4*/
    18.         int i,j,k;
    19.         double *aptr, *bptr, *cptr;
    20.  
    21.         if (m*n > THRESHOLD) {
    22.  
    23.                 /* Nếu B không vừa vào cache thì giảm kích thước của mỗi khối đi một nửa để tính */
    24.                 lhalf[0] = 0; lhalf[1] = l/2; lhalf[2] = l - l/2;                                
    25.                 mhalf[0] = 0; mhalf[1] = m/2; mhalf[2] = m - m/2;
    26.                 nhalf[0] = 0; nhalf[1] = n/2; nhalf[2] = n - n/2;
    27.                
    28.                 for (i=0; i<2; i++)
    29.                     for (j=0;j<2;j++)
    30.                         for (k=0;k<2;k++)
    31.                             mm( crow + lhalf[i], ccol + mhalf[j],
    32.                                 arow + lhalf[i], acol + mhalf[k],
    33.                                 brow + mhalf[k], bcol + nhalf[j],
    34.                                 lhalf[i+1], mhalf[k+1], nhalf[j+1] );
    35.         }else {
    36.             /* B fits in cache -- do standard multiply */
    37.                 for (i=0; i<l ; i++)
    38.                     for (j=0;j<n;j++) {
    39.                         cptr = &c [crow+i] [ccol + j];
    40.                         aptr = &a [arow+i] [acol];                         
    41.                     bptr = &b [brow] [bcol + j];
    42.                        
    43.                     for (k=0; k<m; k++) {
    44.                         *cptr += *(aptr++) * *bptr;
    45.                         bptr += N;
    46.                     }
    47.                     }
    48.         }
    49. }
    Chương trình nhân ma trận song song dùng MPI
    Có nhiều phương án song song hóa bài toán nhân ma trận, trong đó có phương pháp phân chia dữ liệu cho các tác vụ theo dòng hoặc theo cột, phương pháp sử dụng giải thuật Cannon (phân chia dữ liệu theo khối).
    Dưới đây là một phương pháp song song hóa đơn giản. Trong phương pháp này, chúng ta truyền ma trận B và một phần ma trận A cho mỗi tác vụ. Ma trận A được chia thành các dòng, mỗi tác vụ sẽ thao tác trên một số dòng của A, toàn bộ ma trận B và tính toán một số dòng tương ứng của ma trận C so với A. Kết quả từng phần của mỗi tác vụ sẽ được tập hợp lại để thu được kết quả trọn vẹn. Phương án này tuy đơn giản nhưng hiệu quả không cao bằng việc phân chia cả A và B theo dòng hoặc sử dụng giải thuật Cannon.
    Mã nguồn chương trình như sau:

    C Code:
    1. /* Nhan ma tran dung MPI */
    2.  
    3.  
    4. #include <stdio.h>
    5. #include <stdlib.h>
    6. #include <mpi.h>
    7.  
    8. #define ROW_LOW(id,p,n)         ((id)*(n)/(p))
    9. #define ROW_HIGH(id,p,n)        (ROW_LOW((id)+1,p,n)-1)
    10. #define ROW_SIZE(id,p,n)        (ROW_HIGH(id,p,n)-ROW_LOW(id,p,n)+1)
    11. #define ROW_OWNER(j,p,n)        (((p)*((j)+1)-1)/(n))
    12. #define THRESHOLD 65535
    13.  
    14. static double *A,*B,*C;
    15.  
    16. void MM(int L, int M, int N,
    17.                 double *A, double *B, double *C,
    18.                 int crow, int ccol , /*corner of C block*/
    19.                 int arow, int acol , /* corner of A block*/
    20.                 int brow, int bcol , /* corner of B block*/
    21.                 int l,
    22.                 int m,          /* block B is m x n*/
    23.                 int n)          /* block C is l x n*/
    24. {
    25.         int lhalf[3], mhalf[3], nhalf[3];
    26.         int i,j,k;
    27.         double *aptr,*bptr,*cptr;
    28.  
    29.         if (m*n > THRESHOLD) {
    30.         lhalf[0] = 0; lhalf[1] = l/2; lhalf[2] = l - l/2;
    31.         mhalf[0] = 0; mhalf[1] = m/2; mhalf[2] = m - m/2;
    32.         nhalf[0] = 0; nhalf[1] = n/2; nhalf[2] = n - n/2;
    33.  
    34.         for (i=0; i<2; i++)
    35.                 for (j=0;j<2;j++)
    36.                 for (k=0;k<2;k++)
    37.                         MM(L,M,N, A, B, C,
    38.                         crow + lhalf[i], ccol + mhalf[j],
    39.                         arow + lhalf[i], acol + mhalf[k],
    40.                         brow + mhalf[k], bcol + nhalf[j],
    41.                         lhalf[i+1], mhalf[k+1], nhalf[j+1] );
    42.         }else {
    43.  
    44.  
    45.                 for (i=0; i<l ; i++)
    46.                         for (j=0; j<n; j++) {
    47.                                 cptr = C +(crow+i)*N + ccol + j;
    48.                                 aptr = A + (arow+i)*M + acol;
    49.                                 bptr = B + brow*N + bcol + j;
    50.                                 for (k=0; k<m; k++) {
    51.                                         *cptr += *(aptr++) * *bptr;
    52.                                         bptr += N;
    53.                                 }
    54.                         }
    55.         }
    56. }
    57.  
    58. void print_usage(char *s) {
    59.         printf("Usage: mpirun -np <N> %s <l> <m> <n> \n",s);
    60.         printf("\t <N>: number of processes\n");
    61.         printf("\t Matrix size: A=lxm, B=mxn, C=lxn\n");
    62. }
    63.  
    64. void print_to_file(double *mt, int row, int col, char *name) {
    65.         FILE *f;
    66.         f= fopen(name,"w");
    67.         if (f == NULL){
    68.                 printf("Cannot write to file %s\n",name);
    69.                 exit(1);
    70.         }
    71.         int i,j;
    72.         for (i=0;i<row;i++) {
    73.                 for (j=0;j<col;j++)
    74.                         fprintf(f,"%6.0f ", *(mt + i*col +j));
    75.                 fprintf(f,"\n");
    76.         }
    77.         fclose(f);
    78. }
    79. void print(double *mt, int row, int col) {
    80.         int i,j;
    81.         for (i=0;i<row;i++) {
    82.                 for (j=0;j<col;j++)
    83.                         printf("%6.0f ", *(mt + i*col +j));
    84.                         printf("\n");
    85.         }
    86. }
    87.  
    88. void init_matrix(double *MT, int row, int col,int seed) {
    89.         int i,j;
    90.         for (i=0;i<row;i++) {
    91.                 for (j=0;j<col;j++) {
    92.                         MT[i*col+j] = 1;
    93.                 }
    94.         }
    95. }
    96.  
    97. int main(int argc, char **argv) {
    98.         int i,j;
    99.         int id; /* process id */
    100.         int p; /* number of processes */
    101.  
    102.         int localL; /* number of rows each node does the computation*/
    103.         MPI_Status status;
    104.         MPI_Init(&argc, &argv);
    105.         MPI_Barrier(MPI_COMM_WORLD);
    106.         double elapsed_time = -MPI_Wtime();
    107.  
    108.         MPI_Comm_rank(MPI_COMM_WORLD, &id);
    109.         MPI_Comm_size(MPI_COMM_WORLD, &p);
    110.  
    111.         if (argc !=4) {
    112.                 print_usage(argv[0]);
    113.                 exit(1);
    114.         }
    115.  
    116.         int L,M,N;
    117.         L=atoi(argv[1]);
    118.         M=atoi(argv[2]);
    119.         N=atoi(argv[3]);
    120.  
    121.         /*compute the number of rows each one has*/
    122.         localL = ROW_SIZE(id,p,L);
    123.         B=(double *) malloc(sizeof(double)*M*N);
    124.         if (id==0)
    125.                 init_matrix(B,M,N,0);
    126.  
    127.         MPI_Barrier(MPI_COMM_WORLD);
    128.         /* send B */
    129.         MPI_Bcast(B,
    130.                         M * N,
    131.                         MPI_DOUBLE,
    132.                         0,
    133.                         MPI_COMM_WORLD);
    134.         /* on root node */
    135.         if (id==0) {
    136.  
    137.                 A=(double *) malloc(sizeof(double)*L*M);
    138.                 C=(double *) malloc(sizeof(double)*L*N);
    139.  
    140.                 /* initialize A,B */
    141.                 init_matrix(A,L,M,1);
    142.                 /*
    143.                 printf("A=\n");
    144.                 print (A,L,M);
    145.                 printf("B=\n");
    146.                 print (B, M, N);        
    147.                 */
    148.                 /* send A, B to other nodes */
    149.                 /* each node will receive:
    150.                  * - entire matrix B
    151.                  * - L/p rows of matrix A
    152.                  * and generate:
    153.                  * - L/p rows of C
    154.                  */
    155.  
    156.                  /* SEND DATA TO OTHER NODES */
    157.                  for (i=1; i<p;i++) {
    158.                         int size = ROW_SIZE(i,p,L);
    159.                         int low = ROW_LOW(i,p,L);
    160.                         //printf(" send %d to %d \n",size,i);
    161.                         fflush(stdout);
    162.                         /* send rows of A */
    163.                         //printf("first data should be %2.0f\n", *(A+(i)*M));
    164.                         MPI_Send( A + low* M, /*pointer to the beginning of the buffer to send */
    165.                                                 size * M, /* size of the buffer */
    166.                                                 MPI_DOUBLE , /*data type*/
    167.                                                 i, /* send to process number i */
    168.                                                 100,
    169.                                                 MPI_COMM_WORLD);
    170.  
    171.                  }
    172.                  /* DOES ITS OWN COMPUTATION */
    173.                  MM(L,M,N,A,B,C,0,0,0,0,0,0,localL,M,N);
    174.                  /* RECEIVE DATA FROM OTHER NODES */
    175.  
    176.                  for (i=1; i<p;i++) {
    177.                          int coffset = ROW_LOW(i,p,L);
    178.                          int size = ROW_SIZE(i,p,L);
    179.                          MPI_Recv(      C + coffset*N ,       /* pointer to receiving buffer */
    180.                                         size * N, /*buffer size */
    181.                                         MPI_DOUBLE,
    182.                                         i, /*send to root node */
    183.                                         200, /* message tag */
    184.                                         MPI_COMM_WORLD,
    185.                                         &status);
    186.                 }
    187.  
    188.                 /* PRINT RESULTS */
    189.                 printf("C=\n");
    190.                 print(C, L, N);    
    191.  
    192.  
    193.         }
    194.  
    195.         if (id !=0) {
    196.                 A=(double *) malloc(sizeof(double)*localL*M);
    197.                 C=(double *) malloc(sizeof(double)*localL*N);
    198.  
    199.                 memset( (double *)C, 0, localL*N);
    200.  
    201.                 MPI_Recv(       A,       /* pointer to receiving buffer */
    202.                                         localL * M, /*buffer size */
    203.                                         MPI_DOUBLE,
    204.                                         0, /*receive from root node */
    205.                                         100,
    206.                                         MPI_COMM_WORLD,
    207.                                         &status);
    208.  
    209.                 MM(L,M,N,A,B,C,0,0,0,0,0,0,localL,M,N);
    210.  
    211.                 //printf("finish computing  on node %d\n", id);
    212.                 //fflush(stdout);
    213.                 /* send C back to root */
    214.                 MPI_Send(       C,       /* pointer to receiving buffer */
    215.                                         localL * N, /*buffer size */
    216.                                         MPI_DOUBLE,
    217.                                         0, /*send to root node */
    218.                                         200, /* message tag */
    219.                                         MPI_COMM_WORLD);
    220.  
    221.         }
    222.  
    223.         free(A);
    224.         free(B);
    225.         free(C);
    226.  
    227.         elapsed_time += MPI_Wtime();
    228.         if (id==0)
    229.                 printf("Elapsed time: %10.6f\n",elapsed_time);
    230.         MPI_Finalize();
    231.         return EXIT_SUCCESS;
    232. }

    Cái bài này là mình sưu tầm, mà bản thân đọc cũng chưa hiểu hết, do đó post lên để cùng thảo luận

  4. #4
    Ngày gia nhập
    03 2008
    Bài viết
    2

    Mặc định Một tài liệu tham khảo về lập trình song song

    Dear my friends,
    Đây là tài liệu mình ngâm cứu trong khóa luận tốt nghiệp đại học. Trong đó có hướng dẫn về lập trình song song trên Windows và Linux.
    Với tinh thần "Một viên gạch chung tay vì cộng đồng C".
    Chúc my friends vui vẻ.

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

  1. Lập trình C++ Sử dụng OpenMP để song song giải thuật đệ quy tháp Hà Nội
    Gửi bởi tuyen12a trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 07-03-2013, 04:54 PM
  2. Một số phương pháp tính tích phân, sử dụng kĩ thuật lập trình song song[Chuyên đề]
    Gửi bởi mp121209 trong diễn đàn Thủ thuật, Tutorials và Mã nguồn
    Trả lời: 2
    Bài viết cuối: 25-04-2011, 02:40 PM
  3. Giải thuật song song cho bài toán quy hoạch động và quay lui
    Gửi bởi chuong01 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 4
    Bài viết cuối: 25-06-2010, 09:20 PM
  4. Xin tài liệu về Giải thuật song song
    Gửi bởi Caonguyen12G trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 1
    Bài viết cuối: 11-05-2010, 11:15 AM
  5. giao tiếp máy tính qua cổng song song
    Gửi bởi gold1110 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 14-03-2008, 09:56 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