Đề tài Nghiên cứu tính toán lưới và thực nghiệm trên một số thuật toán lý thuyết đồ thị

hêm các tham số trong thủ tục như sau nhằm để quản lý các tiến trình gửi ht t p : / / e t r i t h u c . v n Trang 104 Request object : Kiểu dữ liệu MPI_Request Ý nghĩa : Nonblocking communication sử dụng đối tượng request để yêu cầu đối tượng nhận diện những họat động truyền thông và liên kết với những thao tác xem xét sự hoàn thành của tác vụ. Đối tượng request được định rõ vị trí trong bộ nhớ hệ thống MPI. Người dùng không biết đến cấu trúc của những đối tượng này. Chương trình ứng dụng chỉ vận dụng thẻ điều khiển (handle) đối tượng. Hệ thống có thể dùng đối tượng request này để xác định một số thuộc tính khác của những thao tác truyền thông, chẳng hạn như bộ đệm truyền thông liên quan đến nó, hay để lưu trữ thông tin về những về trạng thái chưa được giải quyết của các họat động truyền thông (gửi ,nhận). 4.3.3.1. Non-Blocking Send Tương tự các Blocking Send hay Receive của blocking communication, nhưng tên hàm còn có thêm chữ “I” phía trước. MPI_Isend(void* buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request *request) MPI_Issend (void *buf,int count,MPI_Datatype datatype,int dest,int tag,MPI_Comm comm,MPI_Request *request) Giống như MPI_Isend(), ngoại trừ hàm MPI_Wait() hoặc MPI_Test chỉ ra rằng khi nào thì xử lý đích đã nhận được thông điệp. MPI_Ibsend (void *buf,int count,MPI_Datatype datatype,int dest,int tag,MPI_Comm comm,MPI_Request *request) Giống như MPI_Bsend() ngoại trừ MPI_Wait() hay MPI_Test chỉ ra rằng xử lý đích đã nhận được thông điệp hay chưa. Hàm này phải được sử dụng với hàm MPI_Buffer_attach. MPI_Irsend(void *buf,int count,MPI_Datatype datatype,int dest, int tag,MPI_Comm comm,MPI_Request *request) ht t p : / / e t r i t h u c . v n Trang 105 Giống như MPI_Rsend() ngoại trừ MPI_Wait() hay MPI_Test() chỉ ra rằng khi nào thì xử lý chính nhận thông điệp. Chỉ nên sử dụng nếu lập trình viên chắc chắn rằng có một trình nhận thông điệp thích hợp ở xử lý đích đã được đưa lên. 4.3.3.2. Non-Blocking Receive MPI_Irecv(void* buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Request *request) thêm vào đối tượng có kiểu dữ liệu MPI_Request dùng để trả về thẻ điều khiển. Và thẻ này dùng trong các trường hợp chờ trạng thái hoàn thành của các Posting Operations, quản lý tiến trình nhận và gửi thông điệp. Lưu ý rằng bộ đệm gửi và bộ đệm nhận sẽ không được truy xuất khi các Posting Operations đã được thực hiện cho đến khi nó hoàn thành.Nếu truy xuất bộ đệm ứng dụng trong khi các thao tác gửi và nhận chưa hòan thành thì sẽ gây ra dữ liệu bị sai. Chằng hạn, khi hệ thống bắt đầu sao chép dữ liệu ra khỏi bộ đệm gửi thì không được truy xuất những phần của bộ đệm này cho đến khi nhận giá trị trả về của hệ thống thực thi gửi thông điệp, tương tự truy xuất cho thao tác nhận. 4.3.3.3. Kiểm tra sự hoàn thành của các tiến trình nhận Bởi vì các hàm trong Posting Operation không được biết trước sự hoàn thành khi được khởi chạy. Nên MPI cung cấp chức năng chờ cho đến khi thao tác Send và Receive đã hoàn thành. Nếu thao tác non blocking Send và Receive có thêm các thao tác chờ sự hoàn thành thì giống như hàm blocking. Có thể hình dung như thế này MPI_Isend()+MPI_Wait() = = MPI_Send() MPI_Irecv()+MPI_Wait() = = MPI_Recv() Phân loại kiểu kiểm sự hoàn thành trong truyền thông Blocking ht t p : / / e t r i t h u c . v n Trang 106 Kiểm tra sự hoàn thành của các tiến trình gửi hoặc nhận và dùng lại các thông tin liên quan đến các đối tượng này, chủ yếu là vùng nhớ ứng dụng dùng để gửi dữ liệu .Các hàm do MPI cung cấp có tên Wait. Non-blocking : Chỉ kiểm tra xem đã hoàn thành 1 tác vụ hay chưa, hàm này trả về ngay tại thời điểm đó. Và nếu tác vụ đã hoàn thành thì trả về thêm các thông tin liên quan đến sự hoàn thành đó ,ngược lại trả về một giá trị không định nghĩa .Các hàm này mang tên Test MPI_Wait(MPI_Request *request,MPI_Status *status) Chờ cho đến khi tiến trình nhận thông điệp nhận được thông điệp hoàn toàn ,thông qua thẻ điều khiển request liên quan đến tiến trình nhận thông điệp. Và biến status sẽ nhận được trạng thái của tiến trình nhận như định danh thông điệp v.v... MPI_Test (MPI_Request *request,int *flag,MPI_Status *status) Gọi hàm MPI_Test, flag trả về bằng true nếu thao tác gửi hoặc nhận được xác định bằng đối tượng request đã hoàn thành. Trong trường hợp này, đối tượng trạng thái status được thiết lập nội dung thông tin trên thao tác đã hoàn thành và đối tượng request sẽ được gán giá trị MPI_REQUEST_NULL. Ngược lại, flag trả về bằng false. Trong trường hợp này, giá trị của đối tượng trạng thái status là không xác định. Cả hàm MPI_Wait và MPI_Test, thông tin trả về thao tác hoàn thành đều dựa trên thông tin đối tượng trạng thái status. Nội dung của đối tượng trạng thái status. Nếu muốn chờ một tập các truyền thông giữa các tiến trình hoàn thành thì dùng các hàm sau MPI_ Waitany(int count,MPI_Request *arrayofrequest,int *index,MPI_Status *status) Khóa một thao tác truyền thông (gửi hoặc nhận), liên kết với một đối tượng request trong mảng các đối tượng Request. Nếu nhiều hơn hay bằng một thao tác ht t p : / / e t r i t h u c . v n Trang 107 đã hoàn thành, thì MPI_Waitany tùy ý lấy một đối tượng request trong mảng đó và hoàn thành nó, MPI_Waitany sẽ trả về chỉ số của phần tử request trong mảng và trả về trạng thái hoàn thành. Đối tượng request đó sẽ được giải phóng và được gán giá trị MPI_REQUEST_NULL MPI_Testany(int count,MPI_Request *array_of_requests,int *index,int *flag,MPI_Status *status) Nếu có một hay nhiều hơn một thao tác đã hoàn thành, nó trả về flag=true, và chỉ số của đối tượng request trong mảng đối tượng Request, và trạng thái của thao tác đó và đối tương trạng thái đó được giải phóng và gán giá trị MPI_REQUEST_NULL. Ngược lại, flag=false, và index=MPI_UNDEFINED và status=MPI_UNDEFINED, các giá trị này do MPI định nghĩa dùng trong trường hợp các giá trị trả về không thích hợp. MPI_ Waitall(int count,MPI_Request *arrayofrequest,MPI_Status *arrayofstatus) Chờ cho đến khi tất cả các thao thác có đối tượng request trong mảng Request hoàn thành. Chỉ số trạng thái thứ i trong mảng các trạng thái trả về trạng thái hoàn thành thứ i của thao tác. Và tất cả các đối tương trong mảng đối tượng Request được giải phóng và được gán giá trị MPI_REQUEST_NULL, MPI_Testall(int count,MPI_Request *array_of_request,int *flag,MPI_Status *array_of_statuses) Nếu tất cả các thao tác đã hoàn thành thì flag=true,và trả về trạng thái status tương ứng trong mảng các trạng thái, giải phóng toàn bộ các đối tượng request và được gán giá trị là MPI_REQUEST_NULL, MPI_ Waitsome(int incount,MPI_Request *arrayofrequest,int *outcount,int *offsets,MPI_Status*arrayofstatuses) Chờ cho đến khi nhiều hơn một truyền thông được hoàn thành ,liên kết với những đối tượng request trong mảng .MPI_Waitsome trả về số lượng đối tượng request đã hoàn thành. ht t p : / / e t r i t h u c . v n Trang 108 MPI_Testsome(int incount,MPI_Request *array_of_request,int *outcount,int *array_of_indices,MPI_Status *array_of_statuses) Cũng như hàm MPI_Waitsome,ngọai trừ nó trả về ngay lập tức. Nếu không có thao tác nào hoàn thành thì outcount=0 MPI_Iprobe(int source,int tag,MPI_Comm comm,int *flag,MPI_Status *status) Là hàm thuộc dạng non-blocking, trả về flag=true nếu có một thông điệp mà có thể được nhận với những thông tin đặc tả về source, tag,comm. Lời gọi cũng tương thích cùng thông điệp mà đã được nhận với hàm MPI_Recv(với những tham số như thế này). 4.3.3.4. Các thủ tục liên quan đến đối tượng request Giải phóng Request(Freeing Requests) Một đối tượng request có thể được giải phóng dựa vào các hàm MPI_Wait hay MPI_Test.Ngòai ra ,nó còn dược giải phóng bởi sử dụng những thao tác khác như: MPI_Request_free(MPI_Request *request) Nhưng các thao tác này không giải phóng được đối tượng request khi có một sự giao tiếp liên quan đến đối tượng này vẫn tồn tại .Vì thế MPI cung cấp thêm một hàm nữa là : MPI_Cancel(MPI_Request *request) Đánh dấu cho việc hủy bỏ thao tác truyền thông nonblocking (gửi hay nhận) đang bị treo. Nó trả về ngay lập tức, có thể trước khi sự thao tác đó bị hủy bỏ. Sau này, nó sẽ tiếp tục hoàn thành sự truyền thông mà đã đánh dấu hủy bỏ. Cũng giống như các hàm MPI_IRecv(..). Hàm này cũng có thể áp dụng các hàm liên quan đến việc chờ đợi như MPI_Wait(..) để biết hàm này đã thực hiện xong hay chưa. Nếu sự truyền thông không bị hủy bỏ (bởi vì sự truyền thông đã xảy ra trước khi hàm này tỏ ra hiệu quả ), ngược lại thì đối tượng request sẽ được giải phóng và trả về trạng thái thông tin đã bị hủy bỏ bằng cách sử dụng ht t p : / / e t r i t h u c . v n Trang 109 hàm MPI_Test_cancelled(MPI_Status *status,int *flag): status lưu thông tin của thao tác cần kiểm tra xem có phải thao tác này đã bị hủy bỏ hay chưa. flag=true nếu xảy ra điều đó, ngược lại flag=false. 4.4. Trao đổi thông tin tập hợp 4.4.1. Đồng bộ hóa MPI_Barrier (MPI_Comm comm) Tạo ra một rào cản đồng bộ trong một nhóm. Mỗi tác vụ, khi tiến tới lời gọi MPI_Barrier, thì khóa lại cho đến khi nào tất cả các tác vụ khác trong nhóm cũng tiến tới cùng một lời gọi MPI_Barrier. Chức năng này giúp tất cả các xử lý trong nhóm đã nhận hết được dữ liệu. 4.4.2. Di dời dữ liệu trong nhóm MPI_Bcast(void *buffer,int count,MPI_Datatype datatype,int root,MPI_Comm comm) Broadcast (gửi) một thông điệp từ xử lý với rank=root tới tất cả các xử lý còn lại trong cùng một communicator (trong cùng một nhóm với nhau) Các xử lý trong một communicator sẽ nhận dữ liệu của tiến trình gửi broadcast Tham số Diễn giải Buffer địa chỉ của bộ đệm ứng dụng Count Số lượng thực thể trong buffer Datatype Dạng dữ liệu của buffer Root Rank của xư lý gọi Broadcast Comm Communicator _phạm vi ảnh hường ht t p : / / e t r i t h u c . v n Trang 110 Hình 4-10 : Broadcast dữ liệu MPI_Scatter(void *sendbuff,int sendcnt,MPI_Datatype sendtype,void *recvbuf,int recvcnt,MPI_Datatype recvtype,int root,MPI_Comm comm) Phân phối và chia nhỏ thông điệp thành n phần khác nhau từ một xử lý nguồn và gửi đến mỗi xử lý còn lại trong communicator. Hàm này giống như gồm n hàm MPI_Send với n là số tiến trình và mỗi tiến trình đều thực hiện hàm MPI_Recv(...) . Tất cả các tham số đều quan trong với tiến trình gửi Broadcast, còn lại các tiến trình khác chỉ quan tâm bộ đệm nhận, communicator, tiến trình gửi, dạng dữ liệu và số dữ liêu được nhận. Cho phép một số lượng dữ liêu được gửi đến mỗi tiến trình, bởi vì sendcount là một mảng và còn có thêm một tham số nữa là mảng displs dùng để quy định các địa chỉ của sendbuf được chia ra như thế nào. ht t p : / / e t r i t h u c . v n Trang 111 Hình 4-11 : Ví dụ hàm Scatter Sự mở rộng của hàm Scatter là: MPI_Scatterv(void *sendbuf,int *sendcounts,int *displs,MPI_Datatype sendtype,void *recvbuf,int recvcount,MPI_Datatype recvtype,int root,MPI_Comm comm) Trái ngược với các hàm MPI_Scatter thì gồm các hàm sau đây MPI_Gather(void *sendbuff,int sendcnt,MPI_Datatype sendtype,void *recvbuf,int recvcount,MPI_Datatype recvtype,int root, MPI_Comm comm) Hàm này có nhiệm vụ lấy lại tất cả các thông điệp từ mỗi tác vụ trong một nhóm vào một tác vụ đích duy nhất. Mỗi xử lý (kế cả xử lý ở root) đều phải gửi thông tin về sendbuf đến tiến trình root,và tiến trình root sẽ nhận thông điệp và lưu chúng trong một danh sách có thứ tự các định danh tiến trình (rank) . ht t p : / / e t r i t h u c . v n Trang 112 Hình 4-12 : Hàm MPI_Gather MPI_Allgather(void *sendbuf,int sendcount,MPI_Datatype sendtype,void * recvbuf,int recvcount,MPI_Datatype recvtype,MPI_Comm comm) Cũng giống như hàm MPI_Gather(...) ngoại trừ là tất cả các tiến trình tham gia đều có giá trị thay vì chỉ một tiến trình root sau khi thực hiện gather. Kết qủa của hàm gọi MPI_Allgather(..) cũng như là tất cả các tiến trình thực thi hàm MPI_Gather và đều nhận được kết quả như nhau Hình 4-13 : Hàm MPI_Allgather MPI_Alltoall(void *sendbuf,int sendcount,MPI_Datatype sendtype,void *recvbuff,int *recvcount,MPI_Datatype recvtype,MPI_Comm comm) ht t p : / / e t r i t h u c . v n Trang 113 là một sự mở rộng của hàm MPI_Allgather. Mỗi xử lý sẽ gửi dữ liệu phân biệt đến mỗi trình nhận.Xử lý thứ i sẽ gửi khối thứ j đến xử lý thứ j và được thay thế trong khối thứ i của bộ nhớ lưu trữ nhận Hình 4-14 : Hàm MPI_Alltoall 4.4.3. Tính toán gộp Các hàm ở dạng này cung cấp thêm tính toán gộp trên các xử lý với nhau (ví dụ như tính tổng ,tính giá trị lớn nhất...) các gía trị thuộc về các thành viên của nhóm xử lý . Cũng giống như các hàm collective operation khác, những hàm này cũng có hai dạng, đó là kết quả tính toán trả về trên một nút hoặc kết quả tính toán trả về trên nhiều nút (nút ở đây xem như là một xử lý hay một máy trên một mạng) MPI_Reduce(void *sendbuf,void *recvbuf,int count,MPI_Datatype datatype,MPI_Op op,int root,MPI_Comm comm) ht t p : / / e t r i t h u c . v n Trang 114 Tính giá trị của tất cả các tiến trình trong communicator gửi đến và sau đó đưa giá trị tính toán đó về một tiến trình có rank=root. Hình 4-15 : Hàm MPI_Reduce ht t p : / / e t r i t h u c . v n Trang 115 4.4.3.1. Một số kiểu tính toán do MPI cung cấp CÁC THỦ TỤC TÍNH TOÁN KIỂU DỮ LIỆU ĐƯỢC SỬ DỤNG MPI_MAX Tính giá trị lớn nhất integer,float MPI_MIN Tính giá trị nhỏ nhất integer,float MPI_SUM Tính tổng integer,float MPI_PROD product integer,float MPI_LAND Toán tử luận lý AND integer MPI_BAND Toán tử dấu bit AND integer,MPI_BYTE MPI_LOR Toán tử luận lý OR integer MPI_BOR Toán tử dấu bit OR integer,MPI_BYTE MPI_LXOR Toán tử luận lý XOR integer MPI_BXOR Toán tử dấu bit XOR integer,MPI_BYTE MPI_MAXLOC Tính giá trị lớn nhất và thêm thông tin rank của tiến trình chứa giá trị lớn nhất integer,double,vaø long double MPI_MINLOC Tính giá trị nhỏ nhất và thêm thông tin rank của tiến trình chứa giá trị nhỏ nhất integer,double,vaø long double 4.4.3.2. Một số kiểu tính toán do người dùng định nghĩa Để viết một hàm với chức năng do người dùng định nghĩa dựa vào thuật toán của hàm MPI_Reduce cung cấp có thể thực hiện theo 3 bước sau : Kiểm tra phương pháp tính toán có phù thuộc vào những yêu cầu sau đây không? ht t p : / / e t r i t h u c . v n Trang 116 Bước 1: Có tính kết hợp Ví dụ a + (b+c)=(a+b)+c Có tính giao hoán Ví dụ a+b=b+a Bước 2 : bổ sung toán tử vào hàm gộp (reduction) theo quy tắc sau Hàm myfunc(void *in,void *inout,int *len,MPI_Datatype *datatype) Bước 3 : Đăng ký hàm này với MPI int commute,myop; commute=1 MPI_Op_create(myfunc,commute,&myop) MPI_Reduce(...,myop,..) Hình 4-16 : Sử dụng 8 xử lý để tính giá trị tuyệt đối Một số hàm tính toán gộp còn lại : MPI_Allreduce(void *sendbuf,void *recvbuf,int count,MPI_Datatype datatype,MPI_Op op,MPI_Comm comm) Cũng giống như hàm MPI_Reduce nhưng tất cả các xử lý trong cùng một communicator sẽ nhận giá trị tính toán được ht t p : / / e t r i t h u c . v n Trang 117 Hình 4-17 Hàm Mpi-Allreduce MPI_Reduce_scatter(void *sendbuf,void *recvbuf,int recvcount,MPI_Datatype datatype,MPI_Op op,MPI_Comm comm) MPI_Reduce_scatter thực hiện hai bước. Bước thứ nhất là dùng tính toán gộp trên mỗi giá trị từ bộ đệm gửi (và dĩ nhiên là mỗi giá trị này sẽ lưu trong một mảng). Sau đó mảng này sẽ được phân chia ra thành n đoạn (với n là số xử lý ). Đoạn thứ i sẽ chứa giá trị thứ i trong mảng đã tính toán. Và đoạn thứ i sẽ được gửi đến xử lý thứ i và lưu trong bộ đệm nhận. Hình 4-18 : Hàm MPI_Reduce_scatter MPI_Scan(void *sendbuf,void *recvbuf,int count,MPI_Datatype datatype,MPI_Op op,MPI_Comm comm) MPI_Scan(...) được sử dụng để thực hiện một dạng tính toán gộp theo kiểu Reduction ở trên nhưng với tiến trình i, kết quả sẽ là thực hiện tính toán gộp ht t p : / / e t r i t h u c . v n Trang 118 trên các tiến trình từ 0 dến i. Hình vẽ sau đây sẽ minh họa rõ hơn về điều này Hình 4-19 : Hàm MPI_Scan 4.5. Các kiểu dữ liệu 4.5.1. Những kiểu dữ liệu đã được định nghĩa Kiểu dữ liệu của MPI Kiểu dữ liệu của C MPI_CHAR signed char MPI_SHORT signed short int MPI_INT signed int MPI_LONG signed long int MPI_UNSIGNED _CHAR unsigned char MPI_UNSIGNED_SHORT unsigned short int MPI_UNSIGNED unsigned int MPI_UNSIGNED_LONG unsigned long int MPI_FLOAT float MPI_DOUBLE double MPI_LONG_DOUBLE long double MPI_BYTE MPI_PACKED Kiểu dữ liêu khác MPI_BYTE khác với MPI_CHAR, với một số máy tính thì MPI_CHAR có thể là một ký tự 8 bit (1 byte), nhưng một số máy khác thì MPI_CHAR có thể là ht t p : / / e t r i t h u c . v n Trang 119 một ký tự 2 byte (16 bit _mã Unicode chẳng hạn) còn giá trị của MPI_BYTE là số 1 byte (8 bit) trong tất cả các trường hợp. Tất cả các kiểu dữ liệu còn lại gần giống với các kiểu dữ liệu của C .Ngoài ra còn có thêm kiểu dữ liệu MPI_Packed ,một dạng dữ liệu nén mà chúng ta sẽ đề cập sau 4.5.2. Các kiểu dữ liệu bổ sung Ngoài những kiểu dữ liêu do MPI cung cấp như MPI_BYTE,MPI_DOUBLE v.v…thì MPI còn cung cấp khả năng cho việc định nghĩa chính cấu trúc dữ liệu dựa trên các dạng dữ liệu chính. Những cấu trúc do người dùng định nghĩa được gọi là dạng dữ liệu bổ sung. MPI cung cấp một số phương pháp cho việc cấu trú những kiểu dữ liệu sau đây : + Contiguous + Vector + Indexed + Struct 4.5.2.1. Contiguous Cấu trúc đơn giản nhất .Sản sinh ra một dạng dữ liệu mới bằng cách tạo một số lượng những bản sao chép của một dạng dữ liệu đã có MPI_Type_contiguous(in count,in oldtype, out *newtype) ht t p : / / e t r i t h u c . v n Trang 120 Hình 4-20 : MPI_Type_contiguous 4.5.2.2. Vector MPI_Type_vector(int count,int blocklenght,int stride, MPI_Datatype oldtype, MPI_Datatype*newtype) Cũng giống như contiguous, nhưng cho phép khoanh vùng dữ liệu muốn đăc tả .MPI_Type_hvector cũng giống như MPI_Type_vector ngoại trừ phạm vi được đặc tả ở dạng byte IN : count : số lượng block blocklenght : số lượng của những thành phần bên trong mỗi block stride : số lượng của những thành phần giữa vị trí bắt đầu của mỗi block oldtype : dạng dữ liệu cũ (handle) OUT : newtype : dạng dữ liệu mới ht t p : / / e t r i t h u c . v n Trang 121 Hình 4-21 : MPI_Type_vetor 4.5.2.3. Indexed Định nghĩa dữ liệu không liên tục ,khoảng cách không cố định và đều đặn. Hàm được sử dụng là MPI_Type_indexed(int count,int []blocklens,int []indices,MPI_Datatype old_type,MPI_Datatype *newtype) Dạng dữ liệu tạo ra theo chỉ số của mảng dữ liệu đầu vào và vùng mảng được đặc tả ht t p : / / e t r i t h u c . v n Trang 122 Hình 4-22 : MPI_Type_indexed 4.5.2.4. Struct Vấn đề đặt ra là MPI không cho truyền dữ liệu bằng kiểu cấu trúc .Do đó ,lập trình viên phải định nghĩa cấu trúc sau đó đặt tả cầu trúc đó theo dạng byte theo sự trợ giúp của các hàm MPI . MPI_Type_struct (int count,int []blocklens,int[]offsets,MPI_Datatype oldtypes,MPI_Datatype *newtype) Hình 4-23 : MPI_Type_struct ht t p : / / e t r i t h u c . v n Trang 123 Các hàm liên quan khác đến dạng dữ liệu bổ sung : MPI_Type_extent(MPI_Datatype,MPI_Aint* extent) Trả về kích thước của dạng dữ liệu được đặc tả.Trả về kích thước theo dạng BYTE. MPI_Type_commit( MPI_Datatype datatype) Đăng ký dạng dữ liệu mới với hệ thống. Đây là hàm yêu cầu cho tất cả các hàm tạo ra kiểu dữ liệu mới trước khi sử dụng 4.5.3. Pack và UnPack Cung cấp những chức năng cho việc truyền nhận dữ liệu không liên tục . Ứng dụng sẽ nén dữ liệu vào một bộ đệm liên tục trước khi gửi di .và giải nén sau khi nhận được . Hai hàm thường sử dụng cho việc nén và giải nén là MPI_Pack(void* inbuf, int incount, MPI_Datatype datatype, void *outbuf, int outsize, int *position, MPI_Comm comm) MPI_Pack nén thông điệp với nội dung thông điệp là inbuf, incount,datatype,comm vào không gian bộ đệm (với thông tin outbuf và outsize). Bộ đệm vào (inbuf) có thể là bất kỳ bộ đệm truyền thông (mà được cho phép trong giao tiếp gửi MPI_SEND) và dữ liệu ra (output buffer) là một vùng lưu trữ liên tục chứa outsize bytes, bắt đầu với địa chỉ outbuf MPI_Unpack(void* inbuf, int insize, int *position, void *outbuf, int outcount, MPI_Datatype datatype, MPI_Comm comm) Ngược lại với chức năng của hàm MPI_Pack ,MPI_Unpack giải nén một thông điệp được đặc tả thông tin ( giá trị inbuf,kích thước insize) vào bộ đệm nhận được đặt tả với thông tin (giá trị outbuf,kích thước outsize, dạng dữ liệu datatype) .Bộ đệm đầu ra thuộc bất kỳ dạng dữ liệu nào được truyền thông trong hàm nhận MPI_Recv. Bộ đệm đầu vào (input buffer) là dạng dữ liệu liên tục chứa insize bytes, bắt đầu với địa chỉ của ìnbuf ht t p : / / e t r i t h u c . v n Trang 124 Việc phân biệt ngữ nghĩa giữ kiểu dữ liệu bổ sung và kiểu dữ liệu MPI_PACKED rất khó .Tuỳ theo ngữ cảnh mà người dùng tự chọn cho mình cách biểu thị tốt nhất cho bài toán tối ưu về mặt ngữ nghĩa và truyền thông trong các thuật toán cụ thể 4.6. Quản lý nhóm và communicator 4.6.1. Tổng quan Nhắc lại, Group là một tập hợp có thứ tự các xử lý. Mỗi xử lý trong một nhóm là một sự kết hợp với một rank duy nhất. Gía trị Rank trong phạm vi từ 0 đến N-1, trong đó N là số xử lý trong nhóm. Bên trong MPI, một Nhóm đại diện bên trong bộ nhớ hệ thống như một đối tượng. Người lập trình truy xuất đó như một ‘handle’. Một nhóm luôn luôn liên kết với một đối tượng communicator. Một Communicator đặt trưng cho một nhóm các xử lý cái mà sẽ giao tiếp với các nhóm khác. Tất cả thông điệp phải đặt tả một communicator. Trong trường hợp đơn giản nhất, một communicator là một ‘tag’ mở rộng cái mà bao gồm với những lời gọi MPI. Giống như những nhóm, những communicators được thể hiện bên trong hệ thống bộ nhớ như những đối tượng và những lập trình viên chỉ truy xuất bằng các ‘handle’. Ví dụ,handle của một communicator mà quản lý tất cả các tác vụ là MPI_COMM_WORLD Mục tiêu chính của Group và những đối tượng Communicator: • Cho phép tổ chức tác vụ, dựa trên chức năng, vào trong những nhóm tác vụ. Làm cho những thao tác Collective Communication có thể thực hiện liên kết một tập các tác vụ liên quan. • Cung cấp nền tảng cho mô hình vật lý ảo do người dùng dịnh mô phỏng (virtual topology) • Cung cấp sự giao tiếp an toàn dữ liệu khi truyền nhận do sử dụng tối ưu các thuật toán liên quan trên một communicator Group và ht t p : / / e t r i t h u c . v n Trang 125 Communicator là tự động, chúng có thể được tạo và hủy bỏ trong suốt sự thực thi của chương trình Những xử lý có thể xuất hiện nhiều hơn trên một group /communicator.Chúng sẽ có một rank duy nhất trong mỗi group /communicator MPI cung cấp trên r ất nhiều hàm liên quan đến group, communicator Communicator là một đối tượng không rõ ràng, với một số thuộc tính, và một số quy tắc đơn giản. A Communicator đặc tả miền truyền thông có thể được sử dụng cho sự truyền thông point-to-point. Intracommunicator được sử dụng cho truyền thông bên trong một nhóm của những xử lý trong nhóm đó .Intracommunicator cũng được sử dụng cho những collective operations Một intercommunicator được sử dụng cho truyền thông điểm điểm (point- to-point) giữa những nhóm xử lý tách rời nhau.Những thuộc tính của môt intercommunicator là hai nhóm .Không có virtual topology nào (sẽ đề cập sau) liên kết với một intercommunicator Chức năng Intracommunicator Intercommunicator Số nhóm 1 2 An toàn giao tiếp Có Có Collecitve Communication Có Không Topologies Có Không Group Management (Sự quản lý nhóm) Mô tả sự vận dụng những nhóm xử lý bên trong MPI. Những thao tác này là local và sự thực thi của nó không yêu cầu sự giao tiếp giữa các xử lý. MPI cho phép sự vận dụng những nhóm bên ngoài những communicator nhưng những nhóm chỉ có thể được sử dụng cho truyền thông điệp bên trong một communicator Communicator management(Sự quản lý communicator) ht t p : / / e t r i t h u c . v n Trang 126 Mô tả sự vận dụng của những communicator bên trong MPI.Những thao tác này truy xuất communicators cái mà local và những sự thực thi của nó không yêu cầu sự giao tiếp giữa các xử lý .Những thao tác này tạo ra những communicator chung và có thể yêu cầu giao tiếp giữa các xử lý. Chúng ta mô tả những cư xử của những hàm này, thừa nhận rằng tham số comm là một intracommunicator 4.6.2. Nguyên tắc sử dụng 1. Mở rộng handle của nhóm cha từ MPI_COMM_WORLD bằng cách sử dụng MPI_Comm_group 2. Tạo ra một nhóm mới như một tập con của nhóm cha bằng cách sử dụng MPI_Group_incl 3. Tạo ra một communicator mới cho mỗi nhóm mới bằng cách sử dụng MPI_Comm_create 4. Xác định rank mới trong communicator mới bằng cách sử dụng MPI_Comm_rank 5. Thực hiện giao tiếp các communicator sử dụng các hàm MPI Messsage pasing 6. Khi kết thúc ,giải phóng communicator mới và group mới tạo với hàm MPI_Comm_free và MPI_Group_free Group Tạo group MPI_Comm_group (MPI_Comm comm ,*group): Xác định group liên kết với một communicator cho trước MPI_Group_excl(MPI_Group group,int n,int *rank,MPI_Group *newgroup): Phát sinh ra một nhóm bằng các sắp xếp lại một nhóm đã có và chỉ lấy những thành viên chưa được lệ kê trong danh sách ht t p : / / e t r i t h u c . v n Trang 127 MPI_Group_incl(MPI_Group group,int n,int *ranks,MPI_Group*newgroup) : Phát sinh một nhóm bằng các sắp xếp lại một nhóm sẵn có và chỉ lấy những thành viên được liệt kê trong danh sách MPI_Group_intersection(MPI_Group group1,MPI_Group group2,MPI_Group*newgroup): Phát sinh ra một nhóm là giao của hai nhóm cho trước với nhau MPI_Group_union(MPI_Group group1,MPI_Group group2,MPI_Group*newgroup):Giống như MPI_Group_intersection nhưng là hợp của hai nhóm MPI_Group_difference(MPI_Group group1,MPI_Group group2,MPI_Group *newgroup) :Tạo ra một nhóm mới từ hiệu của hai nhóm cho trước Truy xuất group MPI_Group_rank(MPI_Group group,int *rank):Trả về rank của xử lý này bên trong một group cho trước ,hay trả về MPI_UNDEFINED nếu xử lý không phải là một thành viên MPI_Group_size (MPI_Group group,int *size) : Trả về số lượng xử lý của một group Lưu ý : Mỗi rank phải là một rank hợp lệ trong group và tất cả các thành phần phải được phân biệt hay chức năng là không lỗi MPI_Group_compare(MPI_Group group1,MPI_Group group2,*result): So sánh hai nhóm và trả về một số integer ,số này là MPI_IDENT nếu trật tự và những thành viên của hai nhóm là như nhau.MPI_SIMILAR nếu chỉ những thành viên là như nhau ,và mặt khác là MPI_UNEQUAL Huỷ group MPI_Group_free(MPI_Group *group):Xác định group cho trước cần giải phóng ht t p : / / e t r i t h u c . v n Trang 128 Communicator Tạo communicator MPI_Comm_create(comm,group,*newcomm):Tạo mới một communicator từ communicator cũ và nhóm mới MPI_Comm_dup(MPI_Comm com,MPI_Comm *newcomm): Nhân đôi một communicator đã có với tất cả thông tin được liên kết Truy xuất communicator MPI_Comm_size(MPI_Comm comm, int *size): Lấy số lượng (size) các xử lý trong communicator MPI_Comm_rank(MPI_Comm comm,int *rank): Lấy định danh của xử lý bên trong một commmunicator ho trước MPI_Comm_compare(MPI_Comm comm1,MPI_Comm comm2,*result) So sánh hai communicator và trả về kết quả là một số integer. Nếu là MPI_IDENT thì ngữ cảnh và n ững nhóm là như nhau. MPI_CONGRUENT nếu có sự khác biệt về ngữ cảnh, MPI_SIMILAR nếu sự khác biệt về ngữ cảnh nhưng giống nhau về group,và còn lại là MPI_UNEQUAL Huỷ communicator MPI_Comm_free(MPI_Comm *comm): Giải phóng đối tượng communicator ht t p : / / e t r i t h u c . v n Trang 129 Chương 5. Thử nghiệm các thuật toán lý thuyết đồ thị 5.1. Các khái niệm cơ bản 5.1.1. Đồ thị Một đồ thi G=(V,E) trong đó V là tập các đỉnh của đồ thị,E là tập các cạnh của đồ thị ,mỗi cạnh sẽ là sự liên kết của hai đỉnh Chỉ đề cập đến hai loại đồ thị là : Đồ thị vô hướng :nếu những cạnh không có thứ tự hai chiều Hai đỉnh u và v trong một đồ thị vô hướng G được gọi là liền kề hay( láng giềng ) nếu u ,v là một cạnh của G .Nếu e=(u,v) thì e được gọi là cạnh liên thuộc với các đỉnh u và v . Cạnh e cũng được gọi là ạnh nối các đỉnh u và v. Các đỉnh u và v được gọi là các điểm đầu mút của cạnh (u,v) Đồ thị hữu hướng khi cạnh có hai chiều nối hai đỉnh khác nhau Khi (u,v) là cạnh của đồ thị có hướng G , thì u được gọi là nối tới v ,và v được gọi là được nối từ u . Đỉnh u gọi là đỉnh đầu , đỉnh v gọi là đỉnh cuối của cạnh (u,v). Đỉnh đầu và đỉnh cuối của khuyên là trùng nhau Một đồ thị trọng số là đồ thị có độ dài cho mỗi cạnh Ký hiệu :G(V,E, w) Ma trận liền kề : A=(ai,j) ,là một mảng 2 chiều với thông tin như sau nếu cạnh (i,j) tồn tại thì ai,j=1(hay độ dài của cạnh ) ngược lại thì ai,j=0 5.1.2. Đường đi Đường đi từ đỉnh u đến đỉnh v là một tập thứ tự các đỉnh ,trong đó v0=v và vk=v và (vi,vi+1) thuộc tập cạnh E với mọi i từ 0 đến k Chiều dài của đường đi là tổng giá trị độ dài các cạnh Đường đi (u,v): Nếu đường đi tồn tại , u tiến tới v Đơn giản nếu tất cả các đỉnh trung gian đi qua là phân biệt Là khuyên nếu vo=vk ht t p : / / e t r i t h u c . v n Trang 130 G là đồ thị liên thông nếu có một đường đi từ một đỉnh đến bất kỳ các đỉnh còn lại 5.2. Dijkstra 5.2.1. Tuần tự Thuật toàn do E.Dijkstra ,nhà toán học người Hà Lan , đề xuất vào năm 1959 . Các bước thực hiện thuật toán Dijkstra: Đầu tiên gán cho đỉnh α nhãn bằng 0 và các đỉnh khác là ∞ .Ta ký hiệu L(α)=0 và L(v)= ∞ cho tất cả các đỉnh khác ( bước lặp thứ 0 ). Các nhãn này là độ dài của đường đi ngắn nhất từ đỉnh α tới các đỉnh này., trong đó đường đi này chỉ chứa đỉnh α. (Vì không có đường đi từ α tới các đỉnh khác α nên ∞ là độ dài đường đi ngắn nhất giữa α và các đỉnh này). Theo thuật toán Dijkstra ta sẽ xây dựng tập đặc biệt các đỉnh. Gọi Sk là tập này sau bước lặp thứ k của thủ tục gán nhãn. Chúng ta bắt đầu bằng So=Φ. Tập Sk được tạo thành từ Sk-1 bằng cách thêm vào đỉnh u không thuộc Sk-1 có nhãn nhỏ nhất. Khi đỉnh u được gộp vào Sk chúng ta sửa đổi nhãn của các đỉnh không thuộc Sk sao cho Lk(v),nhãn của v tại bước k, là độ dài của đường đi ngắn nhất từ α tới v mà đường đi này chỉ chứa các đỉnh thuộc Sk (tức là các đỉnh đã thuộc tập đặc biệt các đỉnh cùng với u) Giả sử v là một đỉnh không thuộc Sk. Để sửa nhãn của v ta thấy Lk(v) là độ dài của đường đi ngắn nhất từ α tới v và chỉ chứa các đỉnh thuộc Sk. Để sửa đổi nhãn ta lưu ý rằng đường đi ngắn nhất từ α tới u ở bước k-1 cùng với cạnh (u,v). Nói cách khác ta có. L(a,v)=min(Lk-1(a,v),Lk-1(a,u)+ w(u,v)) ht t p : / / e t r i t h u c . v n Trang 131 Thủ tục này được lặp bằng cách liên tiếp thêm các đỉnh vào tập đặc biệt các đỉnh cho tới khi đạt tới đỉnh z. Khi thêm z vào tập đặc biệt các đỉnh thì nhãn của nó bằng độ dài của đường đi ngắn nhất từ α tới z. Sau đây là một minh dụ cụ thể thực hiện thuật toán Dijkstra trên một đồ thị vô hướng 6 đỉnh Hình 5-1.1. ht t p : / / e t r i t h u c . v n Trang 132 Hình 5-1.2. Hình 5-1.3. ht t p : / / e t r i t h u c . v n Trang 133 Hình 5-1.4. Hình 5-1.5 ht t p : / / e t r i t h u c . v n Trang 134 Hình 5-1.6 Hình 5-1. Thuật toán Dijkstra tuần tự 5.2.2. Song song Thuật toán Dijkstra tuần tự có rất nhiều điểm dễ song song hoá.Do đó thuật toán này đã được các nhà lập trình song song hóa rất nhiều. Cụ thể sau đây là cách song song hóa của thuật toán Dijkstra tuần tự. Lúc này chúng ta nghĩ rằng không phẩi thực thi thuật toán trên một bộ xử lý nữa mà phân phối các công việc khác nhau cho mỗi bộ xử lý khác nhau thực hiện.Mỗi bộ xử lý sẽ đảm nhận một số đỉnh của đồ thị cùng với ma trận mô tả quan hệ của các đỉnh đó với các đỉnh còn lại • Triển khai thuật toán p l à số bộ xử lý, n là số đỉnh của đồ thị Mỗi bộ xử lý quản lý n/p số đỉnh Nếu n/p dư lẻ thì P0 đến P n-2 sẽ quản lý n/p số đỉnh Số đỉnh còn lại sẽ do P n-1 quản lý ht t p : / / e t r i t h u c . v n Trang 135 Mỗi bộ xử lý sẽ lưu một ma trận với số cột là số đỉnh do chính Pi quản lý và số dòng là n (tương ứng với số đỉnh của đồ thị) liên quan đến ma trận liền kề A Tương ứng với các đỉnh đó sẽ gồm mảng mô tả độ dài trọng số của đỉnh Li[] Hình 5-2 : Thuật toán Dijkstra song song Các bước thực hiện song song hoá như sau : Bước 1: Khởi tạo tập đỉnh Vt={r},L[k]=∞ ∀k ,L[r]=0; Lấy dữ liệu từ tập tin Phân chia dữ liệu trong ma trận trọng số A[][]đến các bộ xử lý .Với mỗi bộ xử lý sẽ có một ma trận con tương đương với một ma trận con của A nhận dữ liệu Mỗi Pi ngoại trừ P0 sẽ lưu một mảng đỉnh riêng cho mình Vi Bước 2: Từ bộ xử lý master , P0 broadcast đỉnh được chọn là r đến các bộ xử lý còn lại ht t p : / / e t r i t h u c . v n Trang 136 Bước 3: Lặp cho đến khi nào đỉnh đích đã được chọn Mỗi Pi sẽ cập nhật mảng L[] với L[k]=Min[L[k],L(Selected)+ W(selectedV,k)] với mọi k thuộc về tập đỉnh Vi Mỗi Pi sẽ tính toán Min Li=Min(trong số mảng Li) Thực hiện việc tính Min trên tất cả các bộ xử lý và lấy giá trị nhỏ nhất .Sau đó chọn được đỉnh có độ dài nhỏ nhất là SelectedV P0 sẽ broadcast giá trị SelectedV đến các bộ xử lý còn lại P0 sẽ đưa đỉnh được chọn vào tập Vt 5.2.3. Thực nghiệm chương trình Phiên bản 1: Giống như hình vẽ minh họa thuật toán Dijkstra song song. Chương trình được viết dưới dạng C chuẩn trên Linux.Chương trình không bao gồm các cấu trúc đồ thị mà lưu tất cả các thông tin đều bằng mảng,mục đích cho việc truyền dữ liệu được nhanh và gọn hơn. Chương trình được chia thành các ập tin sau đây: Đọc dữ liệu từ tập tin • ReadFile.h • ReadFile.cpp Định nghĩa dạng dữ liệu được truyền giữa các tiến trình trong ứng dụng MPI • Vector.h • Vector.cpp Chương trình chính • Dijkstra.h • Dijkstra.cpp Phiên bản 2: ht t p : / / e t r i t h u c . v n Trang 137 Chương trình này được phân chia rõ ràng nhiệm vụ của các nút trên môi trường LAM. Chương trình được viết dưới dạng các đối tượng Lớp Slave quản lý công việc của các nút Lớp Smatter quản lý thông tin của đồ thị có nhiệm vụ , đọc thông tin từ tập tin và phân phối thông tin đến các nút còn lại trên mạng. Chương trình được chia thành các tập tin sau đây: Cấu trúc đồ thị: • Graph.h • Graph.cpp Quản lý công việc các nút: • Slave.h • Slave.cpp Định nghĩa dạng dữ liệu được truyền giữa các tiến trình trong ứng dụng MPI • Vector.h • Vector.cpp Chương trình chính • Dijkstra.h • Dijkstra.cpp Biên dịch chương trình: Được đóng gói thành tập tin makefile Tạo tập tin Makefile có nội dung như sau all:Dijkstra CC=mpic++ Dijkstra: Dijkstra.o Slave.o Vector.o Graph.o #(CC) -o myapp Dijkstra.o Slave.o Vector.o Graph.o Dijkstra.o: Dijkstra.cpp Dijkstra.h Slave.o Vector.o Graph.o #(CC) -c Dijkstra.cpp Dijkstra.h Slave.o Vector.o Graph.o ht t p : / / e t r i t h u c . v n Trang 138 Slave.o:Slave.cpp Slave.h Dijkstra.h #(CC) -c Slave.cpp Vector.o:Vector.cpp #(CC) -c Vector.cpp Graph.o:Graph.cpp #(CC) -c Graph.cpp Nếu đăng nhập với quyền sử dụng là root thì tập tin Makefile có nội dung như trên ,nếu đăng nhâp với quyền sử dụng khác thì thay dấu # bằng dấu $. Chuyển thư mục hiện hành sang thư mục chứa tập tin Makefile Từ dòng lệnh của màn hình Console gõ #make Thực thi chương trình Sau khi biên dịch ,tập tin thực thi là Dijkstra Đổi quyền đăng nhập khác root để sử dụng LAM.Ví dụ $user Thực thi như sau : $lamboot $mpirun –np k Dijkstra với k là số bộ xử lý của môi trường LAM 5.3. Prim 5.3.1. Tuần tự Do Robert Prim đưa ra vào năm 1957, mặc dù ý tưởng cở bản của nó đã có từ sớm hơn rất nhiều. Để thực hiện thuật toán Prim ,ta bắt đầu bằng việc chọn một cạnh bất kỳ có trọng số nhỏ nhất, đặt nó vào cây khung. Lần lượt ghép vào cây và không tạo ra chu trình trong cây. Thuật toán sẽ dừng khi n-1 cạnh đã được ghép vào cây. b1: ht t p : / / e t r i t h u c . v n Trang 139 b2: b h c i g d e f a 4 8 7 9 10 14 8 11 7 2 4 6 b3: b4: b5: ht t p : / / e t r i t h u c . v n Trang 140 b6: b7: b h i g e f a 4 8 7 9 10 14 8 11 7 2 4 6 c d b8: b h i g e f a 4 8 7 9 10 14 8 11 7 2 4 6 c d b9: ht t p : / / e t r i t h u c . v n Trang 141 b h i g e f a 4 8 7 9 10 14 8 11 7 2 4 6 c d Hình 5-3. Thuật toán Prim tuần tự 5.3.2. Song song Do hai thuật toán Dijkstra và Prim gần giống nhau về mặt bản chất đó là cùng tìm giá trị nhỏ nhất. Đối với Prim đó là cạnh có trọng số nhỏ nhất, còn đối với Dijkstra là đỉnh có độ dài từ đỉnh nguồn đến nó nhỏ nhất. Nên về mặt song song hóa thuật toán Prim cũng tương tự như thuật toán Dijkstra • Triển khai thuật toán p bộ xử lý ,n=số đỉnh của đồ thị Mỗi bộ xử lý quản lý n/p số đỉnh Nếu n/p dư lẻ thì P0 đến Pn-2 sẽ quản lý n/p số đỉnh Số đỉnh còn lại sẽ do Pn-1 quản lý Mỗi bộ xử lý sẽ lưu một ma trận với số cột là số đỉnh do chính Pi quản lý và số dòng là n (tương ứng với số đỉnh của đồ thị) của ma trận liền kề A ht t p : / / e t r i t h u c . v n Trang 142 Hình 5-3 : Thuật toán Prim song song Các bước xử lý thuật toán : Bước 1: Khởi tạo tập đỉnh Vt={r},L[k]=∞ ∀k ,L[r]=0; Lấy dữ liệu từ tập tin Phân chia dữ liệu trong ma trận trọng số A[][]đến các bộ xử lý .Với mỗi bộ xử lý sẽ có một ma trận con tương đương với một ma trận con của A nhận dữ liệu Mỗi Pi ngoại trừ P0 sẽ lưu một mảng đỉnh riêng cho mình Vi Bước 2: Từ bộ xử lý master , P0 broadcast đỉnh được chọn là r đến các bộ xử lý còn lại Bước 3: Lặp cho đến khi nào đ ã c ó n đỉnh được chọn (với n là số đỉnh của đồ thị) Mỗi Pi sẽ cập nhật mảng L[] với L[k]=Min[L[k],W(selectedV,k)] với mọi k thuộc về tập đỉnh Vi Mỗi Pi sẽ tính toán Min Li=Min(trong số mảng Li) Thực hiện việc tính Min trên tất cả các bộ xử lý và lấy giá trị nhỏ nhất .Sau đó chọn được đỉnh có độ dài nhỏ nhất là SelectedV ht t p : / / e t r i t h u c . v n Trang 143 P0 sẽ broadcast giá trị SelectedV đến các bộ xử lý còn lại P0 sẽ đưa đỉnh được chọn vào tập Vt 5.3.3. Thực nghiệm chương trình 5.4. Bellman – Ford 5.4.1. Tuần tự Thuật toán Bellman – Ford giải quyết bài toán tìm đường đi ngắn nhất trong trường hợp tổng quát hơn so với thuật toán Dijkstra , trong đó trọng số của các cạnh nối có thể là số âm. Cho một đồ thị G=(V, E) có hướng và trọng số, với đỉnh nguồn s và hàm trọng số w : E →R, thuật toán trả về giá trị kiểu boolean cho biết từ đỉnh nguồn có thể đến được mạch âm hay không. Nếu có thì thuật toán sẽ kết thúc mà không có lời giải, còn nếu không sẽ kết xuất tất cả các con đường ngắn nhất cùng với chiều dài của chúng. Giống như thuật toán Dijkstra, thuật toán Bellman – Ford cũng sử dụng kỹ thuật relaxation, bằng cách ngày càng giảm chiều dài của đường đi ngắn nhất từ đỉnh s đến các đỉnh v∈V cho đến khi đạt được giá trị ngắn nhất. Thuật toán trả về giá trị TRUE khi và chỉ khi từ đỉnh gốc không đến được mạch âm. BELLMAN-FORD(G, w, s) INITIALIZE-SINGLE-SOURCE(G, s) for i ←1 to |V[G]|-1 do for each edge (u, v) ∈E[G] do RELAX(u, v, w) for each edge (u, v) ∈E[G] do if d[v] > d[u] + w(u, v) then return FALSE return TRUE b1: ht t p : / / e t r i t h u c . v n Trang 144 Hình a b2 Hình b b3 Hình c b4 ht t p : / / e t r i t h u c . v n Trang 145 Hình d b5 Hình e Hình 5-4: Thuật toán Bellman-Ford tuần tự Hình bên trên thể hiện thuật toán Bellman-Ford với 5 đỉnh. Sau khi thực hiện phép khởi tạo thông thường, thuật toán thực hiện qua |V|-1 bước qua các cạnh của đồ thị. Hình (b) và (e) cho thấy trạng thái của thuật toán sau mỗi bước. Sauk hi thực hiện |V|-1 bước , thuật toán sẽ tiến hành kiểm tra mạch âm và trả về giá trị Boolean thích hợp. Thuật toán Bellman-Ford có chi phí là O(V,E), bởi chi phí cho việc khởi tạo là O(V), còn từng bước sẽ tốn O(E), và dòng lặp cuối cùng cũng tốn chi phí là O(E). ht t p : / / e t r i t h u c . v n Trang 146 Để chứng minh tính đúng đắn của thuật toán, chúng ta sẽ chứng minh là nếu đồ thị không chứa mạch âm thì có thể tính được đường đi ngắn nhất từ đỉnh gốc đến mọi đỉnh còn lại. Bổ đề Cho G = (V, E) là một đồ thị có hướng và trọng số với đỉnh nguồn s và hàm trọng số w : E →R, và giả sử trong G đỉnh s không tới được mạch âm. Do đó khi kết thúc thuật toán, chúng ta có d[v] = δ (s, v) với mọi đỉnh v có thể đến từ s. Chứng minh Gọi v là đỉnh có thể đến được từ s, và p = (k<=|V|-1) là đường đi ngắn nhất từ s đến v, trong đó v0 = s và vk = v. Chúng ta sẽ chứng minh baằng phương pháp quy nạp vớ i = 0, 1, …, k, chúng ta có d[vi] =δ (s, vi) sau bước thứ i, và kết quả này vẫn được duy trì về sau. Bởi vì có |V|-1 bước, chúng ta sẽ dùng kết quả này để chứng minh bổ đề Sau bước khởi gán, chúng ta có d[v0] = δ (s, v0) = 0. Trong bước quy nạp chúng ta giả sử đúng với trường hợp i-1, d[vv-1] = δ (s, vi-1) theo bổ đề ở trên chúng ta kết luận được d[vi] = δ (s, vi) sau bước thứ i, do đó bổ đề được chứng minh. Hệ quả Cho G = (V, E) là một đồ thị có hướng và trọng số với đỉnh nguồn s và hàm trọng số w : E →R. Với mỗi đỉnh v∈V, tồn tại một đường đi từ s đến v khi và chỉ khi thuật toán Bellman-Ford kết thúc với d[v]<∞ Chứng minh Chứng minh tương tự như bổ đề. Định lý (Tính đúng đắn của thuật toán Bellman-Ford) Thực hiện thuật toán Bellman-Ford trên đồ thị G = (V, E) có hướng và trọng số với đỉnh nguồn s và hàm trọng số w : E →R. Nếu từ s không đến được ht t p : / / e t r i t h u c . v n Trang 147 mạch âm trong G, thuật toán trả về giá trị TRUE, và ta có d[v] = δ (s, v) với mọi đỉnh v∈V, ngược lại trả về giá trị FALSE. Chứng minh Giả sử trong đồ thị G, từ đỉnh s không đến được mạch âm. Trước tiên chúng ta sẽ chứng minh tại thời điểm kết thúc, d[v] = δ (s, v) với mọi đỉnh v∈V. Nếu từ s đến được đỉnh v, thì định lý đã cho là đúng với bổ đề trên. Bây giờ chúng ta sẽ sử dụng phát biểu trên để chứng minh thuật toán BELLMAN-FORD trả về giá trị TRUE. Khi kết thúc chúng ta có tất cả các cạnh (u, v) ∈E. d[v] = δ (s, v) ≤ δ (s, u) + ω (u, v) = d[u] + ω (u, v) Do đó theo như mô tả trong thuật toán, giá trị trả về là TRUE. 5.4.2. Song song Mô tả chương trình Như đã đề cập ở trên ta có 2 khái niệm cần được phân biệt rõ, là xây dựng chương trình song song từ một thuật toán song song cụ thể đã được thực nghiệm và kiểm tra tính đúng đắn, còn một cách khác để cài đặt một chương trình song song là tiến hành song song hóa các phần trong chương trình tuần tự. Trong thực tế, phần lớn người ta thường sử dụng cách thứ hai do việc thiết kế ra một thuật toán song song là điều rất khó khăn và cần nhiều thời gian làm việc. Chương trình song song cài đặt thuật toán Bellman-Ford được dùng ở đây là tiến hành theo cách thứ hai như đề cập phần trên. Đặc điểm chương trình: o Số bộ xử lý tham gia là biến động tùy thuộc vào người sử dụng. o Nội dung ma trận kề của đồ thị được nhận vào từ tập tin. o Có thể thay đổi các tham số của chương trình như : đỉnh nguồn, đỉnh đích, tên tập tin nhập liệu. Thực hiện ht t p : / / e t r i t h u c . v n Trang 148 Quy ước : + ta có thể hiểu khái niệm tiến trình ở đây là trên một bộ xử lý, số lượng các tiến trình tham gia cũng là số bộ xử lý cần có (cũng là số máy trạm nếu trên một máy chỉ có một bộ xử lý). + P là ma trận gồm 2 dòng, có số cột bằng với số đỉnh của đồ thị, dùng để lưu đường đi ngắn nhất. + L là ma trận kề lưu nội dung của đồ thị. Các bước thuật toán b1: khởi tạo ma trận P và L. b2: tiến trình chính gửi cho các tiến trình con một số cột của ma trận L, tùy vào số máy để chạy chương trình. b3: tiến trình chính broadcast 1 dòng của ma trận P, rồi nhận lại P sau khi các tiến trình con thực hiện tính toán, chương trình kết thúc khi: 2 dòng của ma trận P tương tự nhau, lúc đó kết luận từ đỉnh nguồn có thể đến được mạch âm, bài toán kết thúc mà không có lời giải. Khi số lần thực thi bước 3 lớn hơn số đỉnh của đồ thị, chương trình kết xuất đường đi ngắn nhất từ đỉnh nguồn đến các đỉnh còn lại theo như trong ma trận P. ht t p : / / e t r i t h u c . v n Trang 149 Tieán trình chính Tieán trình 1 Tieán trình 2 Tieán trình chính Broadcast 1 doøng cuûa P Nhaän laïi P sau khi caùc tieán trình con tính tính toaùn Tieán trình chính Tieán trình 1 Tieán trình 2 Tieán trình chính Hình 5-5 : Thuật toán Bellman-Ford song song Thực hiện + Ma trận P được lưu theo lớp TMatrixRow (tổ chức ma trận theo mảng các phần tử được đánh số theo dòng rồi theo cột) class TMatrixRow { public: void printMatrix(); void init(unsigned int mLen, unsigned int nLen); TMatrixRow(unsigned int mLen, unsigned int nLen); void freeMatrix(); unsigned int m; //number of rows unsigned int n; //number of columns ht t p : / / e t r i t h u c . v n Trang 150 double *data; //data, ordered by row, then by column double **rows; //pointers to rows in data TMatrixRow(); virtual ~TMatrixRow(); }; + Ma trận L được lưu theo lớp TMatrixCol(tổ chức ma trận theo mảng các phần tử được đánh số theo cột rồi theo dòng) class TMatrixCol { public: void init(unsigned int len); void printMatrix(); void freeMatrix(); int read(char* filename); unsigned int n; //number of rows = number of columns double *data; //data, ordered by column, then by row double **cols; //pointers to cols in data TMatrixCol(); TMatrixCol(unsigned int len); virtual ~TMatrixCol(); }; ht t p : / / e t r i t h u c . v n Trang 151 Chương 6. Kết luận – Hướng phát triển 6.1. Kết luận Dựa trên các kiến thức đã tìm hiểu được về tính toán lưới, cách thức lập trình trên môi trường song song và phân tán, cũng như các môi trường hỗ trợ phát triển, đề tài đã đat được mục tiêu đề ra là nghiên cứu về tính toán lưới và thực nghiệm trên một số thuật toán lý thuyết đồ thị. Mặc dù thời gian thực hiện có hạn, bên cạnh đó gặp phải một số khó khăn trong việc triển khai ứng dụng, do đây là một đề tài khá mới ít được quan tâm phát triển trước đây, nhưng chúng em cũng cố gắng thực hiện để đạt được các yêu cầu đề ra. Các chương trình viết ra đều có khả năng thực hiện trên nhiều máy với số máy xử lý tùy biến và thực hiện đúng kết quả cần thiết. Chúng em hy vọng sẽ tiếp tục cải tiến chương trình, tối ưu các thuật toán để đạt được kết quả tốt nhất, tận dụng được sức mạnh của các máy con để giải quyết vấn đề. Bên cạnh đó, chúng em cũng hy vọng có thể triển khai trên các hệ thống lớn hơn. 6.2. Hướng phát triển Tương lai của tính toán song song và phân bố, và xa hơn nữa là tính toán lưới vẫn còn rất lớn. Trên thế giới hiện nay người ta vẫn đang tiếp tục nghiên cứu mạnh mẽ nhằm có thể tận dụng được khả năng của các hệ thống máy tính lớn trên thế giới, góp phần trong công tác nghiên cứu khoa học cũng như thương mại. Do trong thời hạn cho phép cũng như khả năng và kiến thức hiện nay vẫn chưa thực sự phát huy được hết khả năng của tính toán lưới, vì thế đề tài hiện còn khả năng phát triển rất lớn. • Cải tiến chương trình ht t p : / / e t r i t h u c . v n Trang 152 Tìm hiểu sâu hơn về thư viện MPI để phát huy tiềm năng rất lớn của nó, bên cạnh đó cũng cần thực hiện một số phương pháp tối ưu như giảm chi phí do tính toán, truyền tải thông tin…Bên cạnh đó nếu có điều kịện sẽ sử dụng trên môi trường hỗ trợ tính toán lưới phổ biến nhất hiện nay là Globus. • Triển khai thực tế Do hạn chế về cơ sở vật chất nên các chương trình chưa được triển khai trên các hệ thống lớn, thực tế để qua đó có thể đánh giá đúng được khả năng của chương trình. Do đó chúng em hy vọng có thể tiếp tục phát triển được đề tài để tận dụng được sức mạnh của tính toán lưới, đem lại hiệu quả cao trong công tác nghiên cứu khoa học và áp dụng vào thực tế. ht t p : / / e t r i t h u c . v n Trang 153 Tài liệu tham khảo Tài liệu viết: [1] Wolfgang Gentzsch, Grid Computing : A New Technology for the Advanced Web, Sun Microsystem Inc, 2001 [2] Ananth Gramma, Anshul Gupta, George Karypis, Vipin Kumar : Introduction to Parallel Computing 2nd, Addison Wesley, USA, 2003 [3] Behrooz Parhami, Introduction to Parallel Processing Algorithms and Architectures, Kluwer Academic, 2002 [4] Fran Berman, Anthony J.G.Hey, Geoffrey C.Fox, Grid Computing Making the Global Infrastructure a Reality, Wiley, 2003 [5] IBM RedBooks, Introduction to Grid Computing with Globus, 2003 [6] Graeme S.McHale, Parallel Programming on Linux Networks Using MPI & PVM [7] Mark Baker, Rajkumar Buyya, Domenico Laforenza, Grids and Grid technologies for wide-area distributed computing, Software – Practice and Experience, 2002 [8] 7.1.1 Lam Install ,LAM/MPI Team Open Systems LAb [9] 7.1.1 Lam User Guide,LAM/MPI Team Open Systems LAb Website: [10] Global Grid Forum, [11] Ian Foster, Designing and Building Parallel Programs, 1995, [12] [13] [14] [15] [16] Application of Parallel Computers [17]