Bài giảng Tính toán song song (Parallel computing) - Phần 2: Giới thiệu về tính toán song song - Phan Trọng Tiến

Nội dung text: Bài giảng Tính toán song song (Parallel computing) - Phần 2: Giới thiệu về tính toán song song - Phan Trọng Tiến

1. 5/11/16 Thực thi mô hình Message Passing: MPI q Hiện nay MPI là một chuẩn công nghiêp, nằm trong chuẩn "de facto” cho kết nối giữa các nút chạy một chương trình song song trên bộ nhớ phân tán. q Với kiến trúc bộ nhớ chia sẻ, thực thi MPI thường không sử dụng giao tiếp các tác vụ qua mạng mà thay vào đó chúng sử dụng bộ nhớ chia sẻ (bản sao bộ nhớ) vì các lý do hiệu năng. q Tập MPI thực thi bao gồm thư viện các thủ tục sao cho có thể gọi được từ các chương trình Fortran, C, C++ hay Ada 1/1/2015 Tính toán song song 57 Mô hình song song dữ liệu - Data Parallel q Mô hình song song dữ liệu thể hiện qua các đặc điểm sau: q Hầu hết các công việc song song tập trung vào thực hiện các thao tác trên một bộ dữ liệu. Bộ dữ liệu này thường được tổ chức thành một cấu trúc chung như mảng hoặc khối (block). q Một tập các tác vụ làm việc trên cùng cấu trúc dữ liệu, tuy nhiên mỗi tác vụ làm việc trên các phần khác nhau của cùng cấu trúc dữ liệu. q Các tác vụ thực hiện cùng hành động trên phân vùng công việc của chúng, ví du “thêm 4 tới mỗi phần tử của mảng”. q Trong kiến trúc chia sẻ bộ nhớ, tất cả các tác vụ phải truy cập tới cấu trúc dữ liệu thông qua bộ nhớ toàn cục. Trên kiến trúc phân tán, cấu trúc dữ liệu được chia nhỏ và cứ trú như các “khối” trong bộ nhớ cục bộ của mỗi tác vụ. 1/1/2015 Tính toán song song 58 29
2. 5/11/16 Các mô hình khác q Có các mô hình lập trình song song khác vẫn đang tiếp tục phát triển dù cho thế giới có sự thay đổi phần cứng và phần mềm máy tính. q Có ba mô hình khác thông dụng được đề cập ở đây. q Dạng lai - Hybrid qSingle Program Multiple Data qMultiple Program Multiple Data 1/1/2015 Tính toán song song 61 Hybryd q Trong mô hình này, hai hay nhiều mô hình lập trình song song được kết hợp với nhau. q Hiện nay, một ví dụ phổ biến của mô hình hybrid là kết hợp của mô hình MPI với mô hình thread (POSIX threads) hoặc mô hình chia sẻ bộ nhớ (OpenMP). Mô hình hybrid tận dựng môi trường phần cứng ngày càng phổ biến của các mạng máy tính được kết nối theo chuẩn SMP q Một ví dụ phổ biến khác của mô hình hybrid là kết hợp dữ liệu song song với MPI. Như đã đề cập trong mô hình dữ liệu song song phần trước, thực thi dữ liệu song song (F90, HPF) trên kiến trúc bộ nhớ phân tán sử dụng MPI để truyền dữ liệu dữa các tác vụ và trong suốt với lập trình viên 1/1/2015 Tính toán song song 62 31
3. 5/11/16 THIẾT KẾ CHƯƠNG TRÌNH SONG SONG Designing Parallel Programs 1/1/2015 Tính toán song song 65 Nội dung q Song song hoá tự động và thủ công q Hiểu bài toán và chương trình q Phân rã (Partitioning) q Truyền thông (Communicatiion) q Đồng bộ (Synchronization) q Các phụ thuộc dữ liệu (Data Dependencies) q Cân bằng tải (Load Balancing) q Tính hạt (Granularity) q Đầu vào/Đầu ra (I/O) q Các giới hạn và chi phí của lập trình song song q Phân tích hiệu suất và hiệu chỉnh 1/1/2015 Tính toán song song 66 33
4. 5/11/16 q Một trình biên dịch song song hoá thường làm việc theo 2 cách khác nhau: q Tự động toàn bộ q Trình biên dịch phân tích mã nguồn và nhận diện các thành phần cho sự song song. q Phân tích này bao gồm nhận diện các yếu tố cản trở sự song song và có thể là cả chi phí mà trong đó có hoặc không song song sẽ cải thiện hiệu năng tính toán. q Vòng lặp (do, for) là mục tiêu thường xuyên nhất cho song song hoá tự động. q Điều hướng bởi lập trình viên q Sử dụng “trình biên dịch điều hướng" hoặc các cờ biên dịch, lập trình viên có thể yêu cầu tường mình trình biên dịch thực hiện song song code. q Cũng có thể sử dụng kết hợp ở một mức độ nhất định với song song hoá tự động. 1/1/2015 Tính toán song song 69 q Nếu bạn đang bắt đầu với code tuần tự đang có và có thời gian hoặc ngân sách hạn chế thì song song hoá tự động có thể là một phương án. Tuy nhiên, có một số cảnh báo quan trọng khi áp dụng song song tự động: q Đưa ra kết quả sai q Hiệu năng thự sự có thể suy giảm q Ít linh hoạt hơn so với song song hoá thủ công q Giới hạn trong phần nhỏ của code (chủ yếu là các vòng lặp) q Có thể không thực hiện song song nếu phân tích bài toán có nhiều trở ngại hoặc code quá phức tạp q Hầu hết các công cụ tính toán song song tự động là cho Fortran q Phần này áp dụng các phương pháp thủ công để viết mã song song. 1/1/2015 Tính toán song song 70 35
5. 5/11/16 Ví dụ về bài toán song song Tính toán năng lượng tiềm năng cho mỗi cấu trúc độc lập của một phân tử. Khi hoàn thành, tìm năng lượng tối thiểu cho mỗi cấu trúc đó. q Bài toán này có thể được giải bằng song song. Mỗi phân tử được xác định là độc lập. Tính toán năng lượng tối thiểu cho mỗi cấu trúc cũng là một bài toán song song. 1/1/2015 Tính toán song song 73 Ví dụ về bài toán không song song Tính dãy Fibonacci (1,1,2,3,5,8,13,21, ) theo công thức: F(k + 2) = F(k + 1) + F(k) q Đây là bài toán không thể song song vì việc tính toán dãy Fibonacci như trên đòi hỏi các tính toán phụ thuộc hơn là chỉ động lập trên một biểu thức.Tính toán giá trị của k+2 phụ thuộc vào k+1 và k. Ba biểu thức này không thể được tính toán độc lập và do đó nó không thể song song 1/1/2015 Tính toán song song 74 37
6. 5/11/16 Các mối quan tâm khác q Xác định những cản trở cho xử lý song song. Một cản trở phổ biến là sự phụ thuộc dữ liệu như ví dụ dãy Fibonacci ở trên. q Nghiên cứu các thuật toán khác nếu có thể. Đây có thể là mối quan tâm quan trọng nhất khi thiết kế một ứng dụng song song. 1/1/2015 Tính toán song song 77 Nội dung q Song song hoá tự động và thủ công q Hiểu bài toán và chương trình q Phân rã (Partitioning) q Truyền thông (Communicatiion) q Đồng bộ (Synchronization) q Các phụ thuộc dữ liệu (Data Dependencies) q Cân bằng tải (Load Balancing) q Tính hạt (Granularity) q Đầu vào / Đầu ra q Các giới hạn và chi phí của lập trình song song q Phân tích hiệu suất và hiệu chỉnh 1/1/2015 Tính toán song song 78 39
7. 5/11/16 Phân vùng dữ liệu q Có nhiều cách khác nhau để phân vùng dữ liệu 1/1/2015 Tính toán song song 81 Phân rã theo chức năng q Trong cách tiếp cận này, tập trung vào tính toán sẽ được thực hiện, không quan tâm dữ liệu được thao tác. Bài toán được phân rã theo công việc phải được thực hiện. Mỗi tác vụ sau đó sẽ thực thi một phần của công việc tổng thể. q Phân rã chức năng có thể thực thi tốt cho các bài toán có phân chia các tác vụ rõ ràng. Ví dụ như: q Mô hình hệ sinh thái - Ecosystem Modeling q Xử lý tính hiệu số - Signal Processing q Mô hình khí hậu - Climate Modeling 1/1/2015 Tính toán song song 82 41
8. 5/11/16 Mô hình khí hậu q Mỗi thành phần của mô hình có thể chia thành các tác vụ riêng. Dấu mũi tên miêu tả cách trao đổi dữ liệu giữa các thành phần khi tính toán. Mô hình khí quyển tạo ra tốc độ gió được sử dụng trong mô hình đại dương, mô hình đại dương lại tạo ra dữ liệu nhiệt độ bề mặt biển mà được sử dụng trong mô hình khí quyển và tiếp tục như vậy q Kết hợp hai kiểu phân rã bài toán là phổ biến và tự nhiên. 1/1/2015 Tính toán song song 85 Nội dung q Song song hoá tự động và thủ công q Hiểu bài toán và chương trình q Phân rã (Partitioning) q Truyền thông (Communicatiion) q Đồng bộ (Synchronization) q Các phụ thuộc dữ liệu (Data Dependencies) q Cân bằng tải (Load Balancing) q Tính hạt (Granularity) q Đầu vào / Đầu ra q Các giới hạn và chi phí của lập trình song song q Phân tích hiệu suất và hiệu chỉnh 1/1/2015 Tính toán song song 86 43
9. 5/11/16 Các hệ số cần xem xét (2) q Độ trễ và Băng thông qĐộ trễ là thời gian cần thiết để gửi một tin nhắn tối thiểu (0 byte) từ điểm A tới điểm B. Thường theo đơn vị micro giây. qB ăng thông là số lượng dữ liệu có thể truyền trên đơn vị thời gian. Thường biểu diễn bằng MB/giây. qG ửi nhiều tin nhắn nhỏ có thể gây ra độ trễ chi phối chi phí truyền thông. Thường hiệu quả hơn đóng gói các gói tin nhỏ thành gói tin lớn hơn như vậy sẽ tăng hiệu quả băng thông truyền thông. 1/1/2015 Tính toán song song 89 Các hệ số cần xem xét (3) q Mức độ nhìn thấy của truyền thông qV ới mô hình Message Passing, các giao tiếp là rõ ràng và thường “nhìn thấy” và dưới điều khiển của lập trình viên. qV ới mô hình Data Parallel, các giao tiếp thường xảy ra trong suốt với lập trình viên, đặc biệt trên kiến trúc bộ nhớ phân tán. Lập trình viên thậm trí còn không thể biết chính xác cách nào giữa các tác vụ thực hiện giao tiếp với nhau như thế nào. 1/1/2015 Tính toán song song 90 45
10. 5/11/16 Các hệ số cần xem xét (5) q Phạm vi truyền thông qBi ết được tác vụ nào phải giao tiếp với nhau là rất quan trọng trong thiết kế chương trình song song. Cả hai kiểu truyền thông mô tả bên dưới đều có thể thực thi đồng bộ hoặc không đồng bộ. qĐ iểm tới điểm (Point-to-point) – liên quan đến hai tác vụ với một tác vụ đóng vai trò người gửi/sản xuất dữ liệu, và tác vụ kia đóng vai trò là người nhận/người tiêu thụ. qT ập hơp (Collective) – liên quan đến chia sẻ giữa các tác vụ (nhiều hơn 2 tác vụ) mà thường được đặc tả như các thành viên trong một nhóm chung hay tập hợp. 1/1/2015 Tính toán song song 93 Các truyền thông dạng tập hợp q Ví dụ 1/1/2015 Tính toán song song 94 47
11. 5/11/16 Các hệ số cần xem xét (8) q Cuối cùng, nhận ra rằng đây chỉ là một phần danh sách những điều cần xem xét !!! J 1/1/2015 Tính toán song song 97 Nội dung q Song song hoá tự động và thủ công q Hiểu bài toán và chương trình q Phân rã (Partitioning) q Truyền thông (Communicatiion) q Đồng bộ (Synchronization) q Các phụ thuộc dữ liệu (Data Dependencies) q Cân bằng tải (Load Balancing) q Tính hạt (Granularity) q Đầu vào / Đầu ra q Các giới hạn và chi phí của lập trình song song q Phân tích hiệu suất và hiệu chỉnh 1/1/2015 Tính toán song song 98 49
12. 5/11/16 Định nghĩa q Sự phụ thuộc tồn tại giữa các câu lệnh chương trình khi thứ tự các câu lệnh thực thi ảnh hưởng tới kết quả chương trình. q Phụ thuộc dữ liệu (data dependence) xảy ra khi các tác vụ khác nhau sử dụng cùng một hoặc nhiều vị trí lưu trữ. q Tính phụ thuộc là rất quan trọng trong lập trình song song bởi vì chúng là một trong những cản trở chính trong xử lý song song. 1/1/2015 Tính toán song song 101 Ví dụ 1: Vòng lặp mang phụ thuộc dữ liệu DO 500 J = MYSTART,MYEND A(J) = A(J-1) * 2.0500 CONTINUE q Giá trị A(J-1) phải được tính trước khi tính giá trị A(J), do đó A(J) thể hiện sự phụ thuộc dữ liệu vào A(J-1). Xử lý song song bị ngăn cản. q Nếu tác vụ 2 có A(J) và tác vụ 1 có A(J-1), tính toán đúng giá trị A(j) cần thiết phải: qKi ến trúc bộ nhớ phân tán – tác vụ 2 phải chứa giá trị giá trị của A(J-1) từ tác vụ 1 sau khi tác vụ 1 kết thúc tính toán của mình. qKi ến trúc bộ nhớ chia sẻ: tác vụ 2 phải đọc A(J-1) sau khi tác vụ 1 cập nhật nó. 1/1/2015 Tính toán song song 102 51
13. 5/11/16 Nội dung q Song song hoá tự động và thủ công q Hiểu bài toán và chương trình q Phân rã (Partitioning) q Truyền thông (Communicatiion) q Đồng bộ (Synchronization) q Các phụ thuộc dữ liệu (Data Dependencies) q Cân bằng tải (Load Balancing) q Tính hạt (Granularity) q Đầu vào / Đầu ra q Các giới hạn và chi phí của lập trình song song q Phân tích hiệu suất và hiệu chỉnh 1/1/2015 Tính toán song song 105 Định nghĩa q Cân bằng tải đề cập đến việc thực hiện phân phối công việc giữa các tác vụ để tất cả các tác vụ luôn “bận” trong tất cả thời gian. Nói cách khác là giảm thiểu thời gian rảnh rỗi giữa các tác vụ. q Cân bằng tải rất quan trọng trong chương trình song song vì lý do hiệu suất. Ví dụ nếu các tác vụ phải chịu dừng lại ở một điểm đồng bộ, tác vụ chậm nhất sẽ xác định hiệu suất tổng thể. 1/1/2015 Tính toán song song 106 53
14. 5/11/16 Nội dung q Song song hoá tự động và thủ công q Hiểu bài toán và chương trình q Phân rã (Partitioning) q Truyền thông (Communicatiion) q Đồng bộ (Synchronization) q Các phụ thuộc dữ liệu (Data Dependencies) q Cân bằng tải (Load Balancing) q Tính hạt (Granularity) q Đầu vào / Đầu ra q Các giới hạn và chi phí của lập trình song song q Phân tích hiệu suất và hiệu chỉnh 1/1/2015 Tính toán song song 109 Định nghĩa q Tỉ lệ tính toán/truyền thông: qTrong tính toán song song, tính hạt là đại lượng đo chất lượng của tỉ lệ tính toán/truyền thông. qGiai đoạn tính toán thường tách biệt với giai đoạn truyền thông bằng các sự kiện đồng bộ. q Song song hạt mịn q Song song hạt thô 1/1/2015 Tính toán song song 110 55
15. 5/11/16 Cái nào là tốt nhất? q Tỉ lệ hạt hiệu quả nhất là phụ thuộc vào thuật toán và môi trường phần cứng mà nó chạy trên đó. q Trong hầu hết các trường hợp, chi phí gắn với các truyền thông và đồng bộ là cao hơn so với tốc độ thực hiện thì sẽ rất thuận lợi để có được tính hạt thô. q Song song hạt mịn có thể giúp giảm các chi phí do tải không cân bằng. 1/1/2015 Tính toán song song 113 Nội dung q Song song hoá tự động và thủ công q Hiểu bài toán và chương trình q Phân rã (Partitioning) q Truyền thông (Communicatiion) q Đồng bộ (Synchronization) q Các phụ thuộc dữ liệu (Data Dependencies) q Cân bằng tải (Load Balancing) q Tính hạt (Granularity) q Đầu vào/Đầu ra (I/O) q Các giới hạn và chi phí của lập trình song song q Phân tích hiệu suất và hiệu chỉnh 1/1/2015 Tính toán song song 114 57
16. 5/11/16 Một vài tuỳ chọn q Quy luật #1: Giảm tổng thế truy cập I/O càng nhiều càng tốt q Cô lập I/O trong những phần công việc tuần tự, và rồi sử dụng các giao tiếp song song để phân phối dữ liệu cho các tác vụ song song. Ví dụ 1, tác vụ 1 có thể đọc một tệp tin đầu vào và sau đó truyền dữ liệu cần thiết cho các tác vụ khác. Tương tự như vậy, tác vụ 1 cũng có thể thực thi thao tác ghi dữ liệu cần thiết từ tất cả các tác vụ khác. q Với bộ nhớ phân tán chia sẻ không gian tệp, thực thi I/O ở cục bộ, không chia sẻ không gian tệp. Ví dụ mỗi bộ xử lý có thể có không gian tệp /tmp. Điều này thường hiệu quả hơn nhiều thực thi I/O thông qua mạng của một thư mục dùng chung. q Tạo các tên tệp duy nhất cho mỗi tác vụ vào/ra tệp 1/1/2015 Tính toán song song 117 Nội dung q Song song hoá tự động và thủ công q Hiểu bài toán và chương trình q Phân rã (Partitioning) q Truyền thông (Communicatiion) q Đồng bộ (Synchronization) q Các phụ thuộc dữ liệu (Data Dependencies) q Cân bằng tải (Load Balancing) q Tính hạt (Granularity) q Đầu vào / Đầu ra q Các giới hạn và chi phí của lập trình song song q Phân tích hiệu suất và hiệu chỉnh 1/1/2015 Tính toán song song 118 59
17. 5/11/16 Luật Amdahl q Rõ ràng có những giới hạn khi mở rộng song song, ví dụ với P = .50, .90 và .99 (tỉ lệ 50%, 90% và 99% của phần code song song), thực nghiệm cho kết quả: speedup N P = .50 P = .90 P = .99 10 1.82 5.26 9.17 100 1.98 9.17 50.25 1000 1.99 9.91 90.99 10000 1.99 9.91 99.02 1/1/2015 Tính toán song song 121 Luật Amdahl q Tuy nhiên một vài bài toán chứng minh việc tăng hiệu suất khi tăng kích thước bài toán, ví dụ: q Các tính toán lưới 2D mất 85 giây chiếm 85% q Phần tuần tự mất 15 giây chiếm 15% q Chúng ta có thể tăng kích thước bài toán bằng việc tăng gấp đôi kích thước lưới. Thời gian thực thi: q Các tính toán lưới 2D mất 680 giây chiếm 97.84% q Phần tuần tự mất 15 seconds chiếm 2.16% q Các bài toán tăng tỉ lệ phần trăm song song với kích thước của chúng có nhiều khả năng mở rộng hơn những bài toán cố định phần trăm thời gian song song. 1/1/2015 Tính toán song song 122 61
18. 5/11/16 Yêu cầu tài nguyên q Mục đích chính của chương trình song song là giảm thời gian thực thi, tuy nhiên để thực hiện điều này, yêu cầu nhiều thời gian của CPU. Ví dụ code song song chạy 1 giờ trên 8 bộ xử lý thực chất nó sử dụng 8 giờ thời gian của CPU. q Số lượng bộ nhớ đòi hỏi cho code song song có thể lớn hơn code tuần tự, do cần tái tạo dữ liệu và cho các chi phí kết hợp của các thư viện hỗ trợ song song và các hệ thống phụ trợ. q Đối với các chương trình song song nhỏ, có thể về mặt hiệu suất nó kém hơn thực thi bằng tuần tự tương tự. Chi phí trên liên quan đến việc thiết lập môi trường song song, khởi tạo tác vụ, các truyền thông và kết thúc tác vụ có thể bao gồm một phần đáng kể thời gian thực thi 1/1/2015 Tính toán song song 125 Khả năng mở rộng q Khả năng mở rộng hiệu năng của một chương trình tính toán song song phụ thuộc vào nhiều yếu tố liên quan đến nhau. Không đơn giản là việc thêm nhiều máy tính thì sẽ cho kết quả tốt hơn. q Một thuật toán có thể có những giới hạn vốn có để mở rộng. Ở một vài điểm, việc thêm tài nguyên gây ra hiệu suất giảm. q Các yếu tố phần cứng đóng một vai trò quan trọng trong khả năng mở rộng, ví dụ: q Băng thông bus của bộ nhớ và CPU trên các máy SMP q Băng thông mạng truyền thông q Số lượng bộ nhớ có sẵn trên các máy hoặc thiết lập trên các máy q Tốc dộ xử lý đồng hồ q Các thư viện hỗ trợ song song và các phần mềm hệ thống phụ trợ có thể giới hạn khả năng mở rộng độc lập của ứng dụng. 1/1/2015 Tính toán song song 126 63
19. 5/11/16 CÁC VÍ DỤ SONG SONG Parallel Examples 1/1/2015 Tính toán song song 129 Nội dung q Xử lý mảng q Tính toán số PI q Phương trình nhiệt đơn giản (Simple Heat Equation) q Phương trình sóng 1-D (1-D Wave Equation) 1/1/2015 Tính toán song song 130 65
20. 5/11/16 Xử lý mảng: giải pháp 1 Phương pháp triển khai khả thi q Thực thi theo mô hình SPMD. q Tiến trình chủ (Master) khởi tạo mảng, gửi dữ liệu tới các tiến trình con (worker) và nhận kết quả. q Các tiến trình worker nhận thông tin, thực thi dữ liệu chia sẻ tính toán và gửi kết quả về master. q Thuật toán: màu đỏ là những phần thay đổi cho xử lý song song 1/1/2015 Tính toán song song 133 Xử lý mảng: giải pháp 1 Phương pháp triển khai khả thi 1/1/2015 Tính toán song song 134 67
21. 5/11/16 Xử lý mảng: Giải pháp 2 cho chiến lược Pool of Tasks 1/1/2015 Tính toán song song 137 Tính toán số PI q Giá trị của PI có thể được tính theo các cách khác nhau. Hay xem xét một phương pháp sau để tính xấp xỉ số PI: qM ột vòng tròn nội tiếp trong một hình vuông qPhát sinh ngẫu nhiên các điểm trong hình vuông qXác định số điểm rơi trong hình vuông và các điểm rơi vào trong hình tròn qĐặ t r bằng số điểm trong hình tròn chia cho số điểm trong hình vuông qPI ~ 4*r q Chú ý rằng càng phát sinh nhiều điểm, độ chính xác của số PI càng cao 1/1/2015 Tính toán song song 138 69
22. 5/11/16 Tính toán số PI Giải pháp song song q Chiến thuật song song: ngắt vòng lặp thành các phần mà có thể được thực thi bởi các tác vụ khác nhau. q Với tác vụ này số PI xấp xỉ: q Mỗi tác vụ thực hiện phần công việc lặp trong vòng một số lần q Mỗi tác vụ có thể làm phần việc của mình mà không cần yêu cầu thông tin từ các tác vụ khác. q Sử dụng mô hình SPMD. Một tác vụ đóng vai trò là master và thu thập kết quả. q Thuật giải: màu đỏ là những thay đổi cho xử lý song song 1/1/2015 Tính toán song song 141 Tính toán số PI Giải pháp song song 1/1/2015 Tính toán song song 142 71
23. 5/11/16 Giải pháp 1 q Thực hiện theo mô hình SPMD q Toàn bộ mảng được phân chia và phân phối như một mảng con tới tất cả các tác vụ.Mỗi tác vụ sở hữu riêng một phần của mảng toàn cục q Xác định phụ thuộc dữ liệu q Các phần tử nội tại thuộc một tác vụ là độc lập với các tác vụ khác q Các phần tử biên là phụ thuộc vào dữ liệu của các tác vụ hàng xóm, đòi hỏi phải giao tiếp q Tiến trình Master gửi thông tin khởi tạo cho các worker, kiểm tra độ hội tụ và thu thập dữ liệu q Các tiến trình worker tính toán giải pháp, giao tiếp với các tiến trình hàng xóm nếu cần thiết q Thuật giải: màu đỏ là những thay đổi cho xử lý song song 1/1/2015 Tính toán song song 145 Parallel Solution 1 1/1/2015 Tính toán song song 146 73
24. 5/11/16 Phương trình sóng 1-D 1-D Wave Equation q Trong ví dụ này, biên độ là đồng nhất, chuỗi đồ thị được tính sau một khoảng thời gian xác định. q Việc tính toán liên quan tới: qBiên độ trên trục y qi như là chỉ số vị trí theo truc x qCác điểm nút đặt dọc theo đồ thị qC ập nhật biên độ theo thời gian không liên tục 1/1/2015 Tính toán song song 149 Phương trình sóng 1-D q Biểu thức này giải quyết bài toán phương trình sóng 1-D, ở đây c là hằng số: q Chú ý: biên độ sẽ phụ thuộc vào bước thời gian trước đó (t, t-1) và các điểm hàng xóm (i-1, i+1). Sự phụ thuộc dữ liệu sẽ đòi hỏi một giải pháp song song sẽ liên quan đến các giao tiếp giữa các tác vụ. 1/1/2015 Tính toán song song 150 75
25. 5/11/16 Tài liệu tham khảo q Seyed H. Roosta (2000). Parallel Processing and Parallel Algorithms Theory and Computation. q Introduction to Parallel Computing, q Message Passing Interface (MPI), q POSIX Threads Programming, q Các nội dung khác 1/1/2015 Tính toán song song 153 77