Ý nghĩa khoa họ c và th ự c ti ễ n c a đề tài
Ki ế n trúc máy tính song song
Mỗi bộ xử lý trong hệ thống MIMD có khả năng thực hiện các luồng lệnh khác nhau trên các luồng dữ liệu riêng biệt Đặc biệt, hầu hết các hệ thống MIMD đều được trang bị bộ nhớ riêng cho từng bộ xử lý.
Máy tính SISD (Single Instruction Single Data) chỉ sử dụng một CPU, thực hiện một chỉ lệnh tại một thời điểm và chỉ đọc hoặc ghi một mục dữ liệu Tất cả các máy tính SISD đều có một thanh ghi duy nhất, được gọi là bộ đếm chương trình, dùng để nạp địa chỉ của lệnh tiếp theo, từ đó thực hiện các câu lệnh theo một thứ tự xác định Hình 1.2 minh họa hoạt động của máy tính theo mô hình SISD.
Hình 1.2 Mô hình ki ế n trúc song SISD
Mô hình SISD còn được gọi là SPSD (Simple Program Simple Data), đơn chương trình và đơn dữ liệu Đây chính là mô hình máy tính kiểu Von Neumann
1.2.2 Ki ế n trúc song song SIMD
Máy tính SISD chỉ có một CPU và thực hiện nhiều đơn vị xử lý đồng thời, với tất cả các đơn vị này nhận cùng một mệnh lệnh nhưng có luồng dữ liệu riêng Ngược lại, máy tính SIMD có khả năng xử lý phân tán trên nhiều phần tử, thực hiện đồng thời trên các thành phần dữ liệu khác nhau và áp dụng cùng một lệnh cho tất cả các thành phần này.
Mô hình kiến trúc song song SIMD được Seyed H Roosta trình bày như trong Hình 1.3
Hình 1.3 Mô hình ki ế n trúc MIMD
Máy tính SIMD có thể hỗ trợ xử lý kiểu vector, trong đó có thể gán các phần tử c a vector cho các phần tử xửlý đểtính toán đồng th i
1.2.3 Ki ế n trúc song song MISD
Máy tính MISD có khả năng thực hiện nhiều chương trình (nhiều lệnh) trên cùng một mục dữ liệu, do đó còn được gọi là MPSD (đa chương trình, đơn luồng dữ liệu).
Kiến trúc kiểu này có thể chia thành 2 nhóm:
Lớp các máy tính yêu cầu các đơn vị xử lý khác nhau có khả năng nhận và thực hiện những chỉ lệnh khác nhau trên cùng một mục dữ liệu Kiến trúc này hiện vẫn chưa được sản xuất thành công trên bất kỳ loại máy tính nào.
Lớp máy tính sử dụng kiến trúc hình ống để xử lý dữ liệu theo vector, trong đó các luồng dữ liệu được chuyển tiếp qua các CPU liên tiếp Mỗi bước trong quy trình này thực hiện một chức năng cụ thể và chuyển kết quả cho CPU tiếp theo, tạo ra một hệ thống hoạt động tương tự như hệ tuần hoàn, do đó còn được gọi là hệ tâm thu Hình 1.4 minh họa hoạt động của máy tính theo mô hình MISD.
Hình 1.4 Mô hình MISD chi s ẽ b ộ nh ớ
1.2.4 Mô hình máy tính MIMD
Máy tính MIMD, hay còn gọi là đa bộ xử lý, cho phép mỗi bộ xử lý thực hiện các luồng lệnh khác nhau trên các luồng dữ liệu riêng biệt.
Hệ thống MIMD thường có bộ nhớ riêng và khả năng truy cập bộ nhớ chung, giúp giảm thiểu sự trao đổi giữa các bộ xử lý Đây là kiến trúc phức tạp nhất, nhưng đồng thời cũng là mô hình hỗ trợ xử lý song song cao nhất Nhiều máy tính đã được sản xuất theo kiến trúc này, như BBN Butterfly, Alliant FX và iSPC của Intel.
Mô hình MIMD bao gồm hai loại chính: loại có các bộ kết nối chặt chẽ và loại có các bộ kết nối rời rạc, tùy thuộc vào cách thức truy cập của các bộ xử lý vào bộ nhớ Các bộ xử lý kết nối chặt chẽ chia sẻ từ một hệ thống bộ nhớ chung, được gọi là hệ thống chia sẻ bộ nhớ.
Mô hình này được Seyed H Roosta trình bày như trong Hình 1.5
Hình 1.5 Mô hình MIMD chia s ẽ b ộ nh ớ
Thu ậ t toán song song
Xử lý có một bộ nhớ riêng được hiểu như hệ thống truyền thông điệp, trong đó các máy tính gửi thông điệp đến nhiều máy tính khác nhau Mỗi bộ xử lý có bộ nhớ riêng và chỉ truy cập vào bộ xử lý đó Mô hình này được Seyed H Roosta trình bày như trong Hình 1.6.
Hình 1.6 Mô hình MIMD truy ền thông điệ p 1.3 Thu t toán song song
1.3.1 Quy trình thi ế t k ế thu ậ t toán song song
Song song hóa thuật toán là quá trình chuyển đổi một thuật toán tuần tự thành thuật toán song song Quy trình này bao gồm bốn bước chính: phân rã, truyền thông, tích tụ và ánh xạ.
Phân rã bài toán là quá trình chia nhỏ công việc tính toán và dữ liệu thành nhiều tác vụ độc lập, nhằm tối ưu hóa khả năng thực hiện song song Việc xác định càng nhiều tác vụ càng tốt giúp linh hoạt hơn khi áp dụng vào mô hình thực tế, với số lượng tác vụ có thể vượt xa số bộ xử lý hiện có Trong giai đoạn này, chúng ta tập trung vào khả năng thực hiện song song mà chưa xem xét vấn đề truyền thông hay cấu trúc máy tính Mục tiêu chính là tìm ra các tác vụ độc lập và xác định cách kết hợp dữ liệu với các tác vụ tính toán hiệu quả.
Trong công đoạn truyền thông, thông tin được truyền tải một cách đồng bộ, đảm bảo rằng tất cả các tác vụ được thực hiện một cách hiệu quả và liên tục.
Trong một tác vụ thư, việc tính toán yêu cầu kết hợp dữ liệu với các nguồn dữ liệu khác Để thực hiện các phép tính, dữ liệu cần được truyền giữa các tác vụ một cách hiệu quả.
Tích tụ là quá trình gộp các tác vụ nhỏ trong công đoạn phân rã thành các tác vụ lớn hơn Việc này giúp giảm chi phí truyền thông, nhưng đồng thời cũng làm giảm tiềm năng thực hiện đồng thời các tác vụ.
- Ánh xạ: Đây là công đoạn cuối cùng, mỗi tác vụ sẽ được ấn định vào một bộ xửlý nào đó.
1.3.2 Nguyên lý thi ế t k ế thu ậ t toán song song
Thuật toán song song là những thuật toán cho phép thực hiện nhiều thao tác đồng thời Để thiết kế các thuật toán này, cần phải tuân thủ một số nguyên tắc và phương pháp nhất định.
- Phân chia dữ liệu cho các tác vụ
- Chỉ ra cách truy cập và chia sẻ dữ liệu
- Phân các tác vụ cho các tiến trình (bộ xử lý)
- Các tiến trình được đồng bộ ra sao
Có năm nguyên lý chính trong thiết kế thuật toán song song [1]:
1 Các nguyên lý lập lịch: Tạo lịch trình để giảm tối thiểu các bộ xử lý sử dụng trong thuật toán sao cho th i gian tính toán là không tăng (xét theo khía cạnh độ ph c tạp)
2 Nguyên lý hình ống: Nguyên lý này được áp dụng khi bài toán xuất hiện một dãy các thao tác {T1, T2, , Tn}, trong đó Ti+1 thực hiện sau khi Ti kết thúc
3 Nguyên lý chia để trị: Chia bài toán thành những phần nhỏhơn tương đối độc lập với nhau và giải quyết chúng một cách song song
4 Nguyên lý đồ thị phụ thuộc dữ liệu: Phân tích mối quan hệ dữ liệu trong tính toán để xây dựng đồ thị phụ thuộc dữ liệu và dựa vào đó để ng dụng thuật toán song song
5 Nguyên lý điều kiện tương tranh: Nếu hai tiến trình cùng muốn truy cập vào cùng một mục dữ liệu chia sẻ thì chúng phải tương tranh với nhau, nghĩa là chúng có thể cản tr lẫn nhau
Ngoài những nguyên lý nêu trên, khi thiết kế thuật toán song song còn một số điểm cần quan tâm:
1 Hiệu quả thực hiện c a thuật toán song song có thể rất khác nhau, mà yếu tố quan trọng nhất ảnh hư ng tới độ ph c tạp tính toán là cấu hình tô pô liên kết mạng
2 Thuật toán song song phải được thiết kế dựa trên những kiến th c về kiến trúc máy tính, ngôn ngữ lập trình song song và các phương pháp tính toán.
1.3.3 Các cách ti ế p c ậ n trong thi ế t k ế
Song song hóa các thuật toán tuần tự giúp chuyển đổi các cấu trúc tuần tự, tận dụng khả năng song song tự nhiên của tất cả các thành phần trong hệ thống xử lý.
Thiết kế thuật toán song song hoàn toàn mới
Thiết kế thuật toán song song từ những thuật toán song song đã được xây dựng
1.3.4 Phân tích đánh giá thuậ t toán song song
Trong thuật toán song song, ngoài việc chú trọng đến độ phức tạp về thời gian và không gian như trong thuật toán tuần tự, còn cần xem xét thêm các đại lượng đo lường khác Độ phức tạp thời gian của thuật toán song song không chỉ đơn giản là đếm số câu lệnh cơ bản mà còn phụ thuộc vào cách thức các phép toán này được thực hiện trên nhiều bộ xử lý Hơn nữa, độ phức tạp về số lượng bộ xử lý cũng là một yếu tố quan trọng trong việc phân tích và thiết kế thuật toán song song.
Các mô hình l ậ p trình song song
Trong mô hình này, các nhiệm vụ chia sẻ một không gian địa chỉ chung, cho phép truy cập đọc và ghi theo phương thức không đồng bộ Để quản lý việc truy cập vào bộ nhớ toàn cục, các cơ chế như khóa (locks) và semaphore được sử dụng.
Nhược điểm c a mô hình này là khó giữ lại được tính nguyên th y c a dữ liệu khi mà nhiều bộ xửlý dùng cũng dữ liệu này
Mô hình này mang lại lợi thế lớn cho lập trình viên, vì họ không cần phải chỉ định việc truyền dữ liệu giữa các tác vụ, từ đó giúp đơn giản hóa quá trình phát triển chương trình.
Trong mô hình luồng chương trình, các nhiệm vụ được phân chia và thực hiện đồng thời bởi các luồng Mỗi luồng có dữ liệu riêng và chia sẻ dữ liệu toàn cục của chương trình chính Các nhiệm vụ mà mỗi luồng thực hiện là các thủ tục con của chương trình Bất kỳ luồng nào cũng có thể thực hiện bất kỳ thủ tục con nào tại cùng một thời điểm với các luồng khác Để các luồng kết nối với nhau qua bộ nhớ toàn cục, chương trình cần được xây dựng đồng bộ nhằm tránh tình trạng nhiều luồng cùng cập nhật một vị trí trong bộ nhớ.
1.4.3 Mô hình truy ền thông điệ p
Trong mô hình truyền thông điệp, chương trình song song được chia thành các tác nhiệm riêng biệt Mỗi tác nhiệm sử dụng bộ nhớ cục bộ riêng trong quá trình tính toán, cho phép nhiều tác nhiệm hoạt động đồng thời trên cùng một máy hoặc trên nhiều máy khác nhau.
Các tác nhiệm trao đổi dữ liệu thông qua truyền thông bằng cách gửi và nhận các thông điệp
Có nhiều thư viện truyền thông điệp khác nhau, điều này gây khó khăn cho các lập trình viên trong việc phát triển ứng dụng di động Để giải quyết vấn đề này, MPI Forum đã được thành lập nhằm thiết lập một chuẩn cho việc triển khai mô hình truyền thông điệp Hiện nay, MPI đã trở thành chuẩn mực cho mô hình truyền thông điệp.
L ập trình song song trong môi trư ng MPI
Mô hình lập trình song song dữ liệu cho phép phát triển các chương trình thực hiện song song trên tập dữ liệu lớn, thường được tổ chức theo cấu trúc như mảng hoặc khối Trong mô hình này, các nhiệm vụ của chương trình tương tác với cùng một cấu trúc dữ liệu, nhưng mỗi nhiệm vụ sẽ xử lý các phân vùng khác nhau của dữ liệu, đồng thời thực hiện các thao tác tương tự nhau.
Hình 1.9 Mô t ả l ậ p trình phân ho ạ ch d ữ li ệ u
Trong kiến trúc chia sẻ bộ nhớ chung, mọi nhiệm vụ truy cập dữ liệu đều diễn ra qua bộ nhớ toàn cục Ngược lại, trong kiến trúc bộ nhớ phân tán, dữ liệu được phân chia và lưu trữ trên các bộ nhớ cục bộ của từng bộ xử lý.
1.2 L p trình song song trongămôiătr ng MPI
Message Passing Interface - MPI là một chuẩn mới được sử dụng rộng rãi nhất
Đây không phải là một ngôn ngữ lập trình mới, mà là một thư viện con có thể được gọi từ các chương trình C và Fortran 77.
MPI được phát triển bởi một diễn đàn quốc tế với sự tham gia của các đại diện từ ngành công nghiệp, học viện và phòng thí nghiệm của chính phủ Nó nhanh chóng được chấp nhận rộng rãi nhờ vào thiết kế cẩn thận, cho phép tối ưu hóa hiệu suất trên nhiều hệ thống khác nhau MPI dựa trên mô hình truyền thông điệp, một trong những phương pháp mạnh mẽ và phổ biến nhất trong lập trình các hệ thống song song.
Nỗ lực cho MPI khởi đầu vào mùa hè năm 1991, khi một nhóm nhỏ các nhà nghiên cứu bắt đầu thảo luận tại một địa điểm hẻo lánh trên núi Úc.
Hội thảo "Tiêu chuẩn cho truyền thông điệp trong một môi trường bộ nhớ phân tán" diễn ra từ ngày 29 - 30 tháng 4 năm 1992 tại Williamsburg, Virginia đã thảo luận về các tính năng cơ bản cần thiết cho một tiêu chuẩn MPI Tại đây, một nhóm cộng tác được thành lập nhằm tiếp tục quá trình tiêu chuẩn hóa Vào tháng 11 năm 1992, Jack Dongarra, Rolf Hempel, Tony Hey và David W Walker đã trình bày một bản dự thảo sơ bộ được gọi là MPI-1.
Vào tháng 11 năm 1992, nhóm cộng tác MPI đã tổ chức một cuộc họp tại Minneapolis, nơi quyết định đặt các quá trình tiêu chuẩn hóa trên một cơ sở chính thức hơn Nhóm đã gặp nhau 6 tuần một lần trong 9 tháng đầu năm 1993, và bản dự thảo chuẩn MPI được trình bày tại hội nghị Siêu máy tính năm 93 vào tháng 11 năm 1993.
Sau khi tiếp nhận ý kiến đóng góp từ cộng đồng, một số kết quả đã được điều chỉnh trong MPI Phiên bản 1.0 của MPI đã được phát hành vào tháng 6 năm nay.
Năm 1994, thông qua các cuộc gặp gỡ và thư điện tử, các nhà nghiên cứu đã thảo luận và quyết định thành lập diễn đàn MPI Diễn đàn này cho phép tất cả các thành viên trong cộng đồng điện toán hiệu suất cao đăng ký tham gia, tạo cơ hội giao lưu và chia sẻ kiến thức.
MPI đã thu hút khoảng 80 người tham gia từ 40 tổ chức, chủ yếu đến từ Mỹ và Châu Âu Hầu hết các nhà cung cấp máy tính hàng đầu cùng với các nhà nghiên cứu từ các trường đại học, phòng thí nghiệm chính phủ và ngành công nghiệp đều tham gia vào MPI.
MPI, viết tắt của Message Passing Interface, là một thư viện các hàm và macro được thiết kế để hỗ trợ giao tiếp giữa các bộ xử lý trong các chương trình Nó cho phép việc truyền thông điệp trong các ngôn ngữ lập trình như C, Fortran và C++, giúp tối ưu hóa hiệu suất của hệ thống xử lý song song.
MPI là một giao thức truyền thông độc lập với ngôn ngữ lập trình máy tính song song, hỗ trợ cả giao tiếp điểm - điểm và giao tiếp tập thể Mục tiêu chính của MPI là đạt được hiệu suất cao, khả năng mở rộng và tính di động tốt.
MPI hoạt động trên các máy tính có bộ nhớ chia sẻ Dù MPI thuộc lớp 5 và các lớp cao hơn trong mô hình OSI, nhưng các triển khai của nó có thể bao gồm hầu hết các lớp, với socket và TCP (Giao thức điều khiển truyền tải) được sử dụng trong tầng vận chuyển.
Hầu hết các triển khai MPI đều có thiết lập định tuyến riêng, cho phép gọi trực tiếp từ các ngôn ngữ lập trình như C, C++, Fortran, và các ngôn ngữ khác như C#, Java hoặc Python Ưu điểm của MPI so với các thư viện truyền thông điệp cũ bao gồm tính di động, vì MPI có thể được triển khai trên hầu hết các kiến trúc bộ nhớ phân tán, cùng với tốc độ vượt trội nhờ vào nguyên tắc tối ưu hóa cho phần c mà nó thực thi.
MPI sử dụng LIS (Language Independent Specifications) để gọi và ràng buộc ngôn ngữ Phiên bản đầu tiên được phát hành chỉ định ràng buộc ANSI C và Fortran
77 cùng với LIS Năm 2008, chuẩn MPI-1.3 ch a khoảng 128 ch c năng, đây cũng là phát hành cuối cùng c a seri MPI-1 trong năm 2008.
Phiên bản MPI-2.2 giới thiệu nhiều tính năng mới như I/O song song, quản lý tiến trình động và điều hành bộ nhớ từ xa Nó cung cấp hơn 500 hàm và ràng buộc ngôn ngữ cho ANSI C, ANSI C++ và ANSI Fortran (Fortran 90) Thêm vào đó, khả năng tương tác đối tượng được cải thiện, giúp lập trình truyền thông điệp bằng ngôn ngữ hỗn hợp trở nên dễ dàng hơn.
Tìm hi ể u t ậ p l ệ nh c a thư việ n MPI
- Ngăn cấm không để xảy ra điều kiện th 4 trong các điều kiện trên.
1.3 Tìm hi u t p l nh c aăth ăvi n MPI
1.3.1 Các l ệ nh qu ản lý môi trườ ng MPI
Các lệnh này có nhiệm vụ thiết lập môi trư ng cho các lệnh thực thi MPI, truy vấn chỉ số c a tác vụ, các thư viện MPI,
- MPI Init kh i động môi trư ng MPI
- MPI Comm size trả về tổng số tác vụ MPI đang được thực hiện trong communicator (chẳng hạn như trong MPI_COMM_WORLD)
MPI_Comm_size (comm,&size)
MPI Comm rank trả về chỉ số (rank) của tác vụ trong communicator Mỗi tác vụ được gán một số nguyên từ 0 đến N-1, trong đó N là tổng số tác vụ trong communicator.
MPI_Comm_rank (comm, &rank)
- MPI Abort kết thúc tất cả các tiến trình MPI
- MPI Get processor name trả về tên c a bộ xử lý
MPI_Get_processor_name(&name, &resultl)
Get_processor_name(&name, resultlen)
- MPI Initialized trả về giá trị 1 nếu MPI_Init() đã được gọi, 0 trong trư ng hợp ngược lại
- MPI Wtime trả về th i gian chạy (tính theo giây) c a bộ xử lý
- MPI Wtick trả về độ phân giải th i gian (tính theo giây) c a MPI_Wtime()
- MPI _ Finalize kết thúc môi trư ng MPI
#include int main(int argc, char **argv)
{ int numtasks, rank, len, rc; char hostname[MPI_MAX_PROCESSOR_NAME]; rc = MPI_Init (&argc,&argv); if (rc != MPI_SUCCESS) { printf ("Loi khoi tao chuong trinh MPI Ket thuc.\n");
MPI_Abort(MPI_COMM_WORLD, rc);
MPI_Comm_size(MPI_COMM_WORLD ,&numtasks) ;
MPI_Comm_rank(MPI_COMM_WORLD ,&rank) ;
MPI_Get_processor_name(hostname, &len) ; printf ("Number of tasks= %d My rank= %d Running on %s\n" , numtasks , rank,hostname);
- Kết quả chạy chương trình:
Chương trình bình thư ng giá trị My rank sẽ hoạt động tuần tự từ 0 đến 3 Tuy nhiên, khi chạy song song, chương trình sẽ được chia thành 2 phần, dẫn đến kết quả My rank không theo thứ tự 0-3.
Một số kiểu dữ liệu cơ bản c a MPI được liệt kê trong bảng sau:
B ả ng 1.1 M ộ t s ố ki ể u d ữ li ệu cơ bả n c ủ a MPI
Tên Kiểu dữ liệu Tên Kiểu dữ liệu
MPI_SHORT signed short MPI_C_DOUBLE_CO
MPI_INT signed int MPI_INT8_T int8_t
MPI_LONG signed long MPI_INT16_T int16_t
MPI_LONG_LONG signed long long
MPI_UNSIGNED_CHAR unsigned character
MPI_UNSIGNED_SHORT unsigned short
MPI_UNSIGNED unsigned int MPI_UINT16_T uint16_t
MPI_UNSIGNED_LONG unsigned long
MPI_FLOAT Float MPI_UINT64_T uint64_t
MPI_DOUBLE Double MPI_BYTE byte
MPI_LONG_DOUBLE long double MPI_PACKED data packed
Người dùng có khả năng tạo ra các cấu trúc dữ liệu riêng dựa trên các kiểu dữ liệu cơ bản Những kiểu dữ liệu được định nghĩa bởi người dùng được gọi là loại dữ liệu kế thừa (derived data types) Để định nghĩa các cấu trúc dữ liệu mới, người dùng cần sử dụng các lệnh phù hợp.
- MPI Type contiguous tạo ra kiểu dữ liệu mới bằng cách lặp count lần kiểu dữ liệu cũ.
MPI_Type_contiguous (count,oldtype,&newtype)
MPI Type vector tương tự như kiểu contiguous, nhưng với các phân đoạn cố định (stride) Kiểu dữ liệu mới được tạo ra bằng cách lặp lại một dãy các khối (block) của kiểu dữ liệu cũ có kích thước đồng nhất tại các vị trí có tính tuần hoàn.
MPI_Type_vector(count,blocklength,stride,oldtype,&newtype)
Datatype::Create_vector(count,blocklength,stride)
MPI Type indexed là kiểu dữ liệu mới được tạo ra từ việc xây dựng một dãy các khối c a của kiểu dữ liệu cũ, trong đó mỗi khối có thể chứa một số lượng bản sao khác nhau của kiểu dữ liệu cũ.
MPI_Type_indexed(count,blocklens[] ,offsets[],oldtype,&newtype)
Datatype::Create_hindexed(count,blocklens[] ,offsets[] )
- MPI Type struct tương tự như trên nhưng mỗi khối có thể được tạo thành b i các kiểu dữ liệu cũ khác nhau.
MPI_Type_struct (count,blocklens[] ,offsets[] ,oldtypes,&newtype)
Datatype::Create_struct(count, blocklens[] ,offsets[] ,oldtypes[] )
- MPI Type extent trả về kích thước (tính theo byte) c a kiểu dữ liệu
MPI_Type_extent (datatype,&extent)
Datatype::Get_extent(lb,extent)
- MPI Type commit đưa kiểu dữ liệu mới định nghĩa vào trong hệ thống
- MPI Type free bỏ kiểu dữ liệu
MPI_Type_free (&datatype) Datatype::Free()
1.3.3 Cơ chế truy ền thông điệ p
Các cơ chế giao tiếp trong MPI gồm có:
Cơ chế giao tiếp point-to-point là hình thức tương tác giữa các cặp tác vụ, trong đó một tác vụ gửi thông điệp và tác vụ còn lại nhận thông điệp tương ứng Thông điệp được phân biệt bằng chỉ số của tác vụ và nhãn (tag) của thông điệp, cho phép nhiều kiểu giao tiếp khác nhau diễn ra giữa các tác vụ.
- Blocking: các lệnh gửi/nhận dữ liệu sẽ kết thúc khi việc gửi/nhận dữ liệu hoàn tất.
Non-blocking trong MPI cho phép các lệnh gửi và nhận dữ liệu hoàn tất ngay lập tức mà không cần chờ đợi việc dữ liệu đã được gửi đi hoặc nhận về hoàn toàn Việc xác nhận dữ liệu đã được truyền đi hay nhận lại sẽ được thực hiện thông qua các lệnh khác trong thư viện MPI.
- Synchr onous: gửi dữ liệu đồng bộ, quá trình gửi dữ liệu chỉ có thể được kết thúc khi quá trình nhận dữ liệu được bắt đầu.
Buffer là một vùng nhớ đệm được tạo ra để lưu trữ dữ liệu trước khi gửi đi, giúp người dùng ghi đè lên vùng bộ nhớ mà không lo mất dữ liệu chuẩn bị gửi.
- Rea dy: quá trình gửi dữ liệu chỉ có thể được bắt đầu khi quá trình nhận dữ liệu đã sẵn sàng.
Bảng dưới đây tổng hợp các chế độ giao tiếp điểm-điểm cùng với các lệnh thông điệp tương ứng, chi tiết về các lệnh này sẽ được trình bày ở những phần sau.
B ả ng 1.2 Cơ chế giao ti ế p Point-to-point
Chế độ Điều kiện kết thúc Blocking Non-Blocking
Send Thông điệp đã được gửi MPI_Send MPI_Isend
Receive Thông điệp đã được nhận MPI_Recv MPI_Irecv
Synchronous send Khi quá trình nhận bắt đầu MPI_Ssend MPI_Issend
Buffer send Luôn kết thúc, không quan tâm quá trình nhận đã bắt đầu hay chưa
Ready send Luôn kết thúc, không quan tâm quá trình nhận đã kết thúc hay chưa
Giao tiếp tập thể, hay còn gọi là collective communication, là cơ chế giao tiếp bao gồm tất cả các tác vụ trong phạm vi của người giao tiếp Các hình thức giao tiếp trong cơ chế này rất đa dạng và phong phú.
- Br oa dca st : dữ liệu giống nhau được gửi từ tác vụ gốc (r oot) đến tất cả các tác vụ khác trong communicator.
- Sca tter : các dữ liệu khác nhau được gửi từ tác vụ gốc đến tất cả các tác vụ khác trong communicator
- Ga ther : các dữ liệu khác nhau được thu thập b i tác vụ gốc từ tất cả các tác vụ khác trong communicator
Phương thức giảm thiểu (Reduce) cho phép thu thập và rút gọn dữ liệu từ mỗi tác vụ, đồng thời lưu trữ dữ liệu vào một tác vụ gốc hoặc trong tất cả các tác vụ liên quan.
Hình 1.12 Cơ chế giao ti ế p t ậ p th ể
1.3.4 Các l ệ nh truy ền thông điệ p blocking
Một số lệnh thông dụng cho chế độ truyền thông điệp blocking gồm có:
- MPI Send gửi các thông tin cơ bản
MPI_Send(&buf,count,datatype,dest,tag,comm)
Comm::Send(&buf,count,datatype,dest,tag)
- MPI Recv nhận các thông tin cơ bản
MPI_Recv(&buf,count,datatype,source,tag,comm,&status)
Comm::Recv(&buf,count,datatype,source,tag,status)
MPI Ssend là lệnh gửi đồng bộ, đảm bảo rằng thông tin chỉ được gửi đi khi đã được nhận thành công Dữ liệu sẽ được giữ lại cho đến khi bộ đệm của tác vụ gửi được giải phóng, cho phép thông tin được sử dụng lại và tác vụ đích bắt đầu nhận dữ liệu.
MPI_Ssend (&buf,count,datatype,dest,tag,comm)
Comm::Ssend(&buf,count,datatype,dest,tag)
MPI Bsend tạo ra một bộ nhớ đệm để lưu trữ dữ liệu cho đến khi nó được gửi đi Lệnh này sẽ hoàn tất khi quá trình lưu dữ liệu vào bộ nhớ đệm đã hoàn thành.
MPI_Bsend (&buf,count,datatype,dest,tag,comm)
Comm::Bsend(&buf,count,datatype,dest,tag)
- MPI Buffer attach cấp phát dung lượng bộ nhớ đệm cho thông tin được sử dụng b i lệnh MPI_Bsend()
MPI_Buffer_attach (&buffer,size)
- MPI Buffer detach bỏ cấp phát dung lượng bộ nhớ đệm cho thông tin được sử dụng b i lệnh MPI_Bsend()
MPI_Buffer_detach (&buffer,size)
- MPI Rsend gửi thông tin theo chế độ r ea dy, chỉ nên sử dụng khi ngư i lập trình chắc chắn rằng quá trình nhận thông tin đã sẵn sàng.
MPI_Rsend (&buf,count,datatype,dest,tag,comm)
Comm::Rsend(&buf,count,datatype,dest,tag)
- MPI Sendrecv gửi thông tin đi và sẵn sàng cho việc nhận thông tin từ tác vụ khác MPI_Sendrecv (&sendbuf,sendcount,sendtype,dest,sendtag,
&recvbuf,recvcount,recvtype,source,recvtag,comm,&status)
Comm::Sendrecv(&sendbuf,sendcount,sendtype,dest,sendtag,
&recvbuf,recvcount,recvtype,source,recvtag,status)
- MPI Wait ch cho đến khi các tác vụ gửi và nhận thông tin đã hoàn thành
- MPI Probe kiểm tra tính blocking c a thông tin
MPI_Probe (source,tag,comm,&status) Comm::Probe(source,tag,status)
# include int main(int argc, char **argv)
{ int numtasks, rank, dest, source, rc , count, tag = 1; char inmsg, outmsg= 'x ' ;
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
In an MPI (Message Passing Interface) program, the rank of each process is determined using MPI_Comm_rank When the rank is 0, the process sends a message to rank 1 using MPI_Send, while simultaneously preparing to receive a message from rank 1 with MPI_Recv Conversely, if the rank is 1, the process is set to receive a message from rank 0 using MPI_Recv This demonstrates a basic communication pattern between two processes in a parallel computing environment.
; rc = MPI_Send(&outmsg,1, MPI_CHAR, dest, tag, MPI_COMM_WORLD);
} rc = MPI_Get_count(&Stat, MPI_CHAR, &count); printf ("Task %d : Received %d char(s) from task %d with tag %d \n" , rank, count, Stat.MPI_SOURCE, Stat.MPI_TAG);
- Kết quả: Thực hiện truyền thông có khóa gửi message ‘x’, ‘y’ từ tác vụ có id = 0 tới tác vụ id = ‘1’
1.3.5 Các l ệ nh truy ền thông điệ p non-blocking
Một số lệnh phổ biến trong chế độ truyền thông điệp non-blocking bao gồm MPI Isend, cho phép gửi thông điệp mà không làm chặn quá trình thực thi Lệnh này xác định một khu vực bộ nhớ để thực hiện nhiệm vụ như bộ đệm gửi thông tin.
MPI_Isend (&buf,count,datatype,dest,tag,comm,&request)
Request Comm::Isend(&buf,count,datatype,dest,tag)
- MPI Irecv nhận thông điệp non-blocking, xác định một khu vực c a bộ nhớ thực hiện nhiệm vụ như là một bộ đệm nhận thông tin.
MPI_Irecv (&buf,count,datatype,source,tag,comm,&request)
Request Comm::Irecv(&buf,count,datatype,source,tag)
- MPI Issend gửi thông điệp non-blocking đồng bộ (synchr onous)
MPI_Issend (&buf,count,datatype,dest,tag,comm,&request)
Request Comm::Issend(&buf,count,datatype,dest,tag)
- MPI Ibsend gửi thông điệp non-blocking theo cơ chế buffer
MPI_Ibsend (&buf,count,datatype,dest,tag,comm,&request)
Request Comm::Ibsend(&buf,count,datatype,dest,tag)
- MPI Irsend gửi thông điệp non-blocking theo cơ chế r ea dy
MPI_Irsend (&buf,count,datatype,dest,tag,comm,&request)
Request Comm::Irsend(&buf,count,datatype,dest,tag)
Thu ật toán Dijkstra tìm đư ng đi ngắ n nh ấ t
Thuật toán Dijkstra [3], mang tên c a nhà khoa học máy tính ngư i Hà Lan
Edsger Dijkstra là một thuật toán nổi bật dùng để tìm đường đi ngắn nhất từ một nguồn đơn trong đồ thị có hướng, với điều kiện là không có cạnh nào mang trọng số âm.
Trong bài toán này, chúng ta có một đồ thị liên thông có trọng số G=(V,E) và mục tiêu là tìm khoảng cách d(u0, v) từ một đỉnh u0 đã cho đến một đỉnh v bất kỳ trong đồ thị G Đồng thời, chúng ta cũng cần xác định đường đi ngắn nhất từ u0 đến v.
Phương pháp c a thuật toán Dijkstra là: xác định tuần tự đỉnh có khoảng cách đến u 0 từ nhỏđến lớn
Đỉnh có khoảng cách nhỏ nhất đến a là a, với d(u₀, u₀) = 0 Trong số các đỉnh khác với u₀, ta tìm đỉnh có khoảng cách k₁ đến u₀ là nhỏ nhất, và đỉnh này phải là một trong các đỉnh kề với u₀ Giả sử đỉnh đó là u₁, với d(u₀, u₁) = k₁.
Trong các đỉnh v # u 0 và v # u 1 , tìm đỉnh có khoảng cách k 2 đến u 0 là nhỏ nhất Đỉnh này phải là một trong các đỉnh kề với u 0 hoặc với u 1 Giả sửđó là u2: d(u 0 ,u 2 ) = k 2
Tiếp tục như trên, cho đến bao gi tìm được khoảng cách từ u 0 đến mọi đỉnh v c a G Nếu V={u 0 , u 1 ,…, un} thì:
+ Đầu vào: Đồ thị liên thông G(V,E,w), w(i,j) > 0 (i,j) E, đỉnh nguồn a
+ Đầu ra : Chiều dài đư ng đi ngắn nhất và đư ng đi ngắn nhất từ đỉnh a đến các đỉnh c a đồ thị
B c 1: Gán L(a):= 0 Với mọi đỉnh x a gán L(x) = Đặt T:=V
B c 2: Chọn v T, v chưa xét sao cho L(v) có giá trị nhỏ nhất Đặt T := T - {v}, đánh dấu đỉnh v đã xét.
Nếu T = , kết thúc L(z), với z thuộc V và z a, là chiều dài đường đi ngắn nhất từ a đến z Từ z, ta có thể lần ngược theo đỉnh đã được ghi nhớ để tìm đường đi ngắn nhất Nếu L(z) không thay đổi và L(z) = thì không tồn tại đường đi.
B c 4: Với mỗi x T kề v gán L(x) := min {L(x), L(v) + w(v,x)} Nếu L(x) thay đổi thì ghi nhớđỉnh v cạnh đỉnh x bằng mảng truoc[] (với truoc[] c a đỉnh 1 = 0) để sau này xây dựng đư ng đi ngắn nhất
Thuật toán Dijkstra có độ phức tạp tính toán không quá n-1 bước lặp, trong đó mỗi bước lặp sử dụng tối đa 2(n-1) phép cộng và phép so sánh để cập nhật nhãn của các đỉnh Đặc biệt, một đỉnh thuộc tập S k có nhãn nhỏ nhất chỉ cần không quá n – 1 phép so sánh Vì vậy, độ phức tạp của thuật toán được xác định là O(n²).
Dùng thuật toán Dijkstra, tìm đư ng đi ngắn nhất từa đến z trong đồ thị sau:
+ Bước 1: ta gán 0 cho đỉnh a và gán cho các đỉnh còn lại L(a) = 0
+ Trong các đỉnh không thuộc S = {a} và kề với a có 2 đỉnh b,c Ta có:
Ta có: L(c) nhỏ nhất nên c S, S = {a, c}
+ Trong các đỉnh không thuộc S mà kề với c có 3 đỉnh b, d, e Ta có:
Ta có: L(b) nhỏ nhất nên b S, S = {a, b, c}
+ Trong các đỉnh không thuộc S mà kề với b có đỉnh d Ta có: L(d) = min {10, L(b) + w(bd)} = min {10, 3 + 5} = 8 d S, S = {a, b, c, d}
+ Trong các đỉnh không thuộc S mà kề với d có đỉnh e, z Ta có: L(e) = min {12, L(d) + w(de)} = min{12, 2+8} = 10
Ta có: L(e) nhỏ nhất nên e S, S = {a, b, c, d, e}
+ Trong các đỉnh không thuộc S mà kề với e có đỉnh z Ta có: L(z) = min {14, L(e) + w(ez)} = min{14, 10+3} = 13
Vậy đư ng đi ngắn nhất từa đến z là: a, c, b, d, e, z với độ dài 13
Ví d ụ 2: Cho đồ thị được biểu diễn sau đây, sau khi thuật toán thực hiện xong thì kết quảđược ghi nhớ lên các nhãn đỉnh tương ng
Hình 2.1 Ghi nh ớ k ế t qu ả tính được trên đồ th ị
Mảng truoc[]=0 1 1 2 3 3 6 4 8 11 7 11 (Mảng ghi nhớ truoc [] dùng để tìm đư ng đi, với truoc[1]=0)
Vậy kết quả từđỉnh 1 đến tất cảcác đỉnh là: đến 2=7 (12) đến 3=5 (13) đến 4 (124) đến 5 (135) đến 6 (136) đến 7 (1367) đến 8 (1248) đến 98 (1248) đến 109 (13671110) đến 11= 24 (136711) đến 12) (13671112)
Thu ậ t toán tu ầ n t ự Prim tìm cây khung c ự c ti ể u
2.2.1.Mô t ả thu ậ t toán Đầ u vào: Đồ thị G=(V,E) với trọng số Các đỉnh ký hiệu là 1,2,3,…,n
Trọng số cạnh (i,j), với (i,j) thuộc tập E, được ký hiệu là c ij, bao gồm một đỉnh nguồn a, một bộ xử lý chính và m-1 bộ xử lý phụ Đầu ra của quá trình này có thể là cây phủ nhỏ nhất T hoặc kết luận rằng đồ thị không liên thông.
(1) Kh i tạo: T là đồ thị gồm một đỉnh 1 và không có cạnh
(2) Kiểm tra điều kiện kết thúc:
Nếu T có n-1 cạnh, kết thúc, kết luận: T là cây ph nhỏ nhất Ngược lại sang bước (3)
Ký hiệu M là tập M ={ (i,j) E| i T&j T} Tìm cạnh (k,h) M sao cho : c kh =min{c ij |(i,j) M}
Nếu c kh
