Đề tài Một số phương pháp song song cho hệ đại số tuyến tính

cả các bộ xử lí được phép ghi vào cụng một ô nhớ nếu chúng ghi cùng một giá trị. Khi đó một bộ xử lí sẽ được chọn để thực hiện việc ghi dữ liệu đó. • Ghi đồng thời tự do (Arbitracy CW): một số bộ xử lí muốn ghi dữ liệu vào một ô nhớ nhưng chỉ một bộ xử lí được phép. Trong trường hợp này ta phải chỉ ra cách xác định bộ xử lí được chọn. • Ghi đồng thời ngẫu nhiên (Random CW): bộ xử lí được chọn để ghi dữ liệu là ngẫu nhiên. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 9 • Ghi đồng thời kết hợp (Combining CW): tất cả các giá trị mà các bộ xử lí muốn ghi đồng thời lên một ô nhớ sẽ được kết hợp lại thành một giá trị và giá trị này sẽ được ghi vào ô nhớ đó. Một số mụ hỡnh bộ nhớ cho mỏy truy cập ngẫu nhiờn song song PRAM: 1. Mụ hỡnh truy cập bộ nhớ đồng bộ UMA (Uniform Memory Access) của bộ nhớ chia sẻ: tất cả các bộ xử lí làm việc nhờ cơ chế chuyển mạch tập trung để truy cập tới bộ nhớ chia sẻ. Thời gian truy cập vào bộ nhớ là như nhau với tất cả các bộ xử lí. 2. Mụ hỡnh truy cập bộ nhớ khụng đồng bộ NUMA của bộ nhớ chia sẻ: trong mụ hỡnh này, bộ nhớ được phân tán và được chia thành một số môđun nhớ độc lập. Bộ nhớ chia sẻ được phân tán cho tất cả các bộ xử lí được gọi là các môđun nhớ địa phương và các môđun nhớ này hợp lại thành bộ nhớ chung (toàn cục) cho cỏc bộ xử lớ. 3. Kiến trúc bộ nhớ chỉ lưu trữ COMA ( Cache-Only Memory Architexture ): bộ nhớ chính được phân tán và chuyển thành các vùng lưu trữ (cache), tất cả các vùng này tạo ra không gian địa chỉ toàn cục. 4. Bộ nhớ đa máy tính: trong bộ nhớ đa máy tính mỗi nút là một máy tính có bộ nhớ địa phương không chia sẻ với những bộ xử lí khác, các bộ xử lí liên lạc với nhau thông qua giao thức truyền thông điệp. 1.3.2 Mạng liờn kết cỏc thành phần của mỏy tớnh song song. Trong hầu hết cỏc kiến trỳc song song, vấn đề quan trọng nhất trong thiết kế là xác định sự liên kết giữa các bộ xử lí với nhau. Nói chung có hai loại cấu hỡnh cho mạng liờn kết: liờn kết tĩnh và liờn kết động. - Mạng liờn kết tĩnh là mạng cỏc thành phần của một hệ thống mỏy tớnh, bộ xử lí và bộ nhớ được liên kết một cách cố định. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 10 - Mạng liên kết động là mạng các thành phần của hệ thống máy tính trong đó các liên kết giữa các bộ xử lí và bộ nhớ là có thể thay đổi được cấu hỡnh. Sau đây là một số mô hỡnh mạng liờn kết tĩnh giữa cỏc bộ xử lớ của mỏy tớnh song song. 1. Mạng liờn kết tuyến tớnh Trong mạng liên kết tuyến tính các bộ xử lí được liên kết với nhau và được sắp xếp theo thứ tự tăng dần. Trừ hai bộ xử lí đầu tiên và cuối cùng, các bộ xử lí cũn lại cú hai lỏng giềng là bộ xử lớ trước và sau nó. Dữ liệu phải truyền qua một số bộ xử lí nên sự truyền thông dữ liệu giữa các bộ xử lí bị chậm lại nhất là giữa bộ xử lí đầu và cuối. Hỡnh 1.6. Mạng liờn kết tuyến tớnh của n bộ xử lớ 2. Mạng liờn kết vũng Mạng liờn kết vũng cú thể được tổ chức như mạng tuyến tính bằng cách nối hai bộ xử lí đầu và cuối. Sự trao đổi giữa các bộ xử lí có thể theo một chiều hoặc hai chiều tuy nhiên việc truyền thông giữa các bộ xử lí đặc biệt là các bộ xử lí ở xa nhau vẫn bị trễ. Hỡnh 1.7. Mạng liờn kết vũng của n bộ xử lớ 3. Mạng liờn kết xỏo trộn P0 P1 Pn-1 P0 P1 Pn-1 THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 11 Giả sử cú N bộ xử lớ P0, P1,…, Pn với N là lũy thừa của 2. Trong mạng liên kết xáo trộn hoàn hảo, đường liên kết một chiều từ bộ xử lí Pi đến bộ xử lí Pj được xác định như sau:    −+ = N1i2 i2j 1Ni2N 12Ni0 −≤≤ −≤≤ Hỡnh 1.8. Mạng liờn kết xỏo trộn hoàn chỉnh với N=8 Hỡnh 1.8 mụ tả một mạng xỏo trộn một chiều hoàn chỉnh với N=8, trong đó các liên kết xáo trôn được biểu diễn bằng mũi tên và các liên kết trao đổi được biểu diễn bằng đoạn thẳng. Dễ thấy rằng ngoài bộ xử lí P0 và PN-1 tự liên kết với chính nó, bộ xử lí i được liên kết với bộ xử lí 2i mod (N-1). 4. Mạng liên kết lưới hai chiều Trong mạng liên kết lưới hai chiều, các bộ xử lí được sắp xếp thành một ma trận hai chiều, mỗi bộ xử lí được liên kết với bốn láng giềng: trên, dưới, trái, phải. Không có qui luật chung cho những bộ xử lí ở biên. Có hai biến thể của mạng lưới hai chiều: lưới hai chiều khụng cú kết nối vũng và lưới hai chiều có kết nối vũng. P0 P1 P2 P3 P4 P5 P6 P7 với với THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN 12 (a) Lưới không có kết nối vũng (b) Lưới có kết nối vũng Hỡnh1.9 Mạng liờn kết lưới hai chiều 5. Mạng liờn kết siờu khối Mạng liờn kết siờu khối d chiều gồm N= 2d bộ xử lí , mỗi bộ xử lí liên kết với d bộ xử lí khác trong mạng. Thông thường mạng liên kết siêu khối d+1 chiều được xây dựng bằng cách kết nối hai mạng liên kết siêu khối d chiều. Một cách hỡnh thức, mạng liờn kết N bộ xử lí được gọi là mạng siêu khối nhị phân, các bộ xử lí được gắn nhón nhị phõn cú giỏ trị từ 0 đến N-1, và hai bộ xử lí được gọi là láng giềng của nhau nếu các nhón của nú chỉ khỏc nhau một bit ( tức là khỏc nhau một lũy thừa của 2). Hỡnh 1.10. Mạng liờn kết siờu khối 3 chiều 6. Mạng liờn kết hỡnh sao Trong mạng liờn kết hỡnh sao, mỗi bộ xử lớ sẽ tương ứng với một hoán vị của n kí hiệu với n là một số tự nhiên. Mạng liên kết hỡnh sao cú n! bộ xử lớ, nhón mỗi bộ xử lớ là một hoỏn vị của n kớ hiệu. Bộ xử lớ Pi được liên kết với bộ xử lí Pj nếu j nhận được từ i bằng cách thay kí hiệu thứ k, với 2≤ k≤ n. K IL O BO O K S. CO M 13 Hỡnh 1.11: Mạng liờn kết hỡnh sao với 24 bộ xử lớ 1.4 Thiết kế và đánh giá thuật toán song song 1.4.1 Nguyờn lớ thiết kế thuật toỏn song song Thuật toán song song được định nghĩa là một tập các tiến trỡnh hoặc cỏc tỏc vụ cú thể thực hiện đồng thời và có thể trao đổi dữ liệu với nhau để kết hợp cùng giải một bài toán. Có thể có nhiều thuật toỏn song song cựng giải một bài toỏn tựy thuộc vào cỏch phõn chia dữ liệu cho cỏc tỏc vụ, cỏch truy xuất dữ liệu, cỏch phõn ró cỏc tỏc vụ và cỏch đồng bộ các tiến trỡnh. Để thiết kế một thuật toán song song tốt ta có thể sử dụng năm nguyên lí chính trong thiết kế thuật toỏn song song: P1234 P3214 P2314 P2134 P1324 P3124 P4231 P3241 P2341 P2431 P4321 P3421 P2413 P4213 P1243 P1423 P2143 P4123 P3412 P4312 P1342 P1432 P3142 P4132 THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 14 - Nguyên lí lập lịch: Giảm tối thiểu các bộ xử lí trong thuật toán mà không làm tăng thời gian tính toán. Nói chung, khi số bộ xử lí giảm thời gian thực hiện của chương trỡnh cú thể tăng và có thể tăng lên một hằng số nào đó nhưng xét theo độ phức tạp của thuật toán thỡ vẫn khụng thay đổi. - Nguyên lí đường ống: Nguyên lí này được áp dụng trong trường hợp ta muốn thực hiện một dóy cỏc thao tỏc theo trỡnh tự {P1, P2,…, Pn} trong đó một số bước của Pi+1 có thể thực hiên trước khi Pi kết thỳc. - Nguyên lí chia để trị: Chia bài toán thành các phần nhỏ tương đối độc lập và giải quyết chúng đồng thời. - Nguyên lí đồ thị phụ thuộc dữ liệu: Chúng ta xây dựng một đồ thị có hướng trong đó các nút biểu diễn các khối câu lệnh độc lập cũn cỏc cạnh biểu diễn tỡnh huống khối này phụ thuộc kết quả từ việc thực hiện của khối kia. Từ đó ta tỡm cỏch loại bỏ cỏc phụ thuộc để xây dựng thuật toán song song. - Nguyờn lớ cạnh tranh: Nếu hai tiến trỡnh cựng truy cập vào một mục dữ liệu chia sẻ thỡ chỳng cú thể cản trở lẫn nhau. 1.4.2 Các giai đoạn thiết kế thuật toán song song Có ba cách tiếp cận trong thiết kế thuật toán song song cho một bài toán, đó là: - Song song hóa các thuật toán tuần tự, biến đổi những 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. Trong thiết kế dù sử dụng hướng tiếp cận nào thỡ cũng thường bao gồm các giai đoạn sau: THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 15 1. Phõn ró (Partioning): Chia những tớnh toỏn và dữ liệu thành những tỏc vụ nhỏ. Giai đoạn này chủ yếu là để tỡm kiếm khả năng thực hiện song song và thường độc lập với kiến trúc máy tính. 2. Truyền thông (Communication): Giai đoạn này nhằm thiết lập sự phối hợp thực hiện giữa các tác vụ và xác định thuật toán và cấu trúc truyền thông thích hợp. 3. Tích hợp (Agglomeration): Mục đích của giai đoạn này là đánh giá những yêu cầu hiệu năng và chi phí thực hiện. Nếu cần thiết, những tác vụ có thể kết hợp lại thành các tác vụ lớn hơn để tăng hiệu năng và giảm chi phí thực hiện. 4. Ánh xạ (Mapping): Mỗi tác vụ sẽ được giao cho một bộ xử lí nhằm tối đa hóa sự tận dụng khả năng của các bộ xử lí và giảm thiểu chi phí truyền thông. Ánh xạ có thể được xác định tĩnh (statically) hoặc trong thời gian chạy (runtime) bằng thuật toỏn cõn bằng tải (load-balancing). 1.4.3 Đánh giá thuật toán song song 1. Thời gian thực hiện Thời gian thực hiện của một thuật toỏn bao gồm: thời gian tớnh toỏn, thời gian truyền thụng và thời gian rỗi. Thời gian tớnh toỏn Thời gian tớnh toỏn của một thuật toỏn (Tcomp) là thời gian sử dụng để tính toán (bao gồm các phép toán logic và số học). Nếu chúng ta có một chương trỡnh tuần tự mà thực hiện tớnh toỏn giống như thuật toán song song chúng ta có thể xác định Tcomp bằng việc tính thời gian chương trỡnh đó. Nếu không chúng ta có thể phải thực thi những nhân then chốt. Thời gian tính toán sẽ thường phụ thuộc vào kích thước bài toán dù nó được biểu diễn bởi một tham số N hay bởi một tập các tham số N1, N2, …, Nm.Thời gian tớnh THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 16 toỏn cũn phụ thuộc vào số cỏc tỏc vụ hoặc số bộ xử lớ. Trong mạng mỏy tớnh song song khụng đồng nhất ( như mạng các máy trạm), thời gian tính toán có thể biến thiên theo bộ xử lí mà tại đó tính toán được thực hiện. Thời gian tính toán cũng phụ thuộc vào đặc điểm của những bộ xử lí và phương thức nhớ của chúng. Thời gian truyền thụng Thời gian truyền thụng của một thuật toỏn ( Tcomm) là thời gian mà tất cả các tác vụ của nó sử dụng để gửi và nhận thông điệp.Có hai loại truyền thông: truyền thông giữa các bộ xử lí (interprocessor) và truyền thông trong bộ xử lí (intraprocessor). Trong truyền thông giữa các bộ xử lí, hai tác vụ thực hiện truyền thông với nhau thông được định vị trên những bộ xử lí khác nhau. Điều này luôn xảy ra khi thuật toán tạo một tỏc vụ trờn một bộ xử lớ. Truyền thụng trong bộ xử lớ, thỡ hai tỏc vụ thực hiện truyền thụng định vị trên một bộ xử lí. Để đơn giản ta giả sử chi phí truyền thông giữa bộ xử lí và truyền thông trong bộ xử lí là ngang nhau. Điều giả sử này không phải là không có cơ sở trong nhiều đa máy tính, trừ khi liên lạc trong bộ xử lí được tối ưu hóa cao độ. Đó là bởi vỡ chi phớ của những bản sao và chuyển ngữ cảnh từ bộ nhớ sang bộ nhớ thực hiện trong truyền thụng trong bộ xử lớ thường có thể so sánh được với chi phí của truyền thông giữa các bộ xử lí. Trong những môi trường như các máy trạm kết nối Ethernet, truyền thông trong bộ xử lí nhanh hơn rất nhiều. Trong kiến trúc đa máy tính lí tưởng, chi phí gửi thông điệp giữa hai tác vụ định vị trên những bộ xử lí khác nhau có thể biểu diễn bằng hai tham số: thời gian khởi động thông điệp ts, là thời gian cần để khởi tạo sự truyền thông, và thời gian truyền một từ ( thường là bốn byte) tw , được xác định bằng băng thông vật lí của kênh truyền thông liên kết bộ xử lí nguồn và đích. Ví dụ, thời gian gửi thông điệp L từ là: Tmsg= ts + TwL THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 17 Thời gian rỗi Thời gian tính toán và thời gian truyền thông đều được chỉ ra một cách rừ ràng trong thuật toỏn song song vỡ thế khụng khú khăn để tính tổng của chúng trong thời gian thực hiện. Thời gian rỗi (Tidle) có thể khó xác định hơn, tuy nhiên chúng thường phụ thuộc vào thứ tự các thao tác được thực hiện. Một bộ xử lớ cú thể rỗi vỡ khụng cú tớnh toỏn hoặc thiếu dữ liệu. Trong trường hợp đầu tiên, thời gian rỗi có thể tránh bằng việc sử dụng những kĩ thuật tải cân bằng. Trong trường hợp thứ hai bộ xử lí rỗi trong khi tính toán và truyền thông đợi dữ liệu ở xa được thực hiện. Thời gian rỗi này đôi khi có thể tránh bằng việc xây dựng một chương trỡnh mà những bộ xử lớ thực hiện những tính toán hoăc truyền thông khác trong khi đợi dữ liệu ở xa. 2. Hiệu suất và hệ số gia tốc Thời gian thực hiện không phải lúc nào cũng là thước đo tốt nhất để đánh giá hiệu năng thuật toán. Vỡ thời gian thực hiện cú khuynh hướng biến thiên theo kích thước bài toán, thời gian thực hiện phải được chuẩn hóa khi so sánh hiệu năng thuật toán với những kích thước khác nhau của bài toán. Hiệu suất - phần thời gian mà bộ xử lí sử dụng để làm công việc có ích- cung cấp một thước đo tốt cho chất lượng của một thuật toán song song. Nó đặc trưng hóa sự hiệu quả của một thuật toán sử dụng tài nguyên tính toán của một máy tính song song một cách độc lập với kích thước bài toán. Chúng ta định nghĩa hiệu suất tương đối như sau: E= P 1 PT T trong đó T1 là thời gian thực hiện trờn một bộ xử lớ và TP là thời gian trên P bộ xử lí. Một đại lượng liên quan nữa là hệ số gia tốc tương đối: S=PE là hệ số chỉ ra thời gian thực hiện giảm đi khi sử dụng P bộ xử lí. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 18 Những đại lượng trên được gọi là hệ số tăng tốc và hiệu suất tương đối vỡ chỳng được định nghĩa với khía cạnh thuật toán song song thực hiện trên một bộ xử lí đơn. Giả sử rằng chúng ta có một thuật toán song song mà mất 10000 giây trên một bộ xử lí và 20 giây trên 1000 bộ xử lí. Một thuật toán khác cũng mất 1000 giây trên một bộ xử lí nhưng chỉ mất 5 giây trên 1000 bộ xử lí. Rừ ràng thuật toỏn thứ hai là tốt hơn với P trong khoảng 1 đến 1000. Nó có hệ số gia tốc chỉ 200 so với 500 của thuật toán đầu. Khi so sánh hai thuật toán, sẽ hữu ích hơn nếu có một tiêu chuẩn độc lập thuật toán hơn là thời gian thực hiện. Vỡ thế chỳng ta định nghĩa hệ số tăng tốc và hiệu suất tuyệt đối sử dụng như là phép đo thời gian bộ xử lí duy nhất (T1) cho thuật toán tốt nhất. Trong nhiều trường hợp, thuật toán tốt nhất này sẽ là thuật toỏn (tuần tự) tốt nhất. 1.5 Kiến trỳc cụm mỏy tớnh Trước đây, thuật ngữ “máy tính hiệu năng cao” (High- Performance Computing - HPC) thường được dùng để chỉ những máy tính song song hoặc máy tính véc tơ với giá trị lên tới hàng triệu đôla. Nhưng với sự phát triển nhanh chóng của công nghệ phần cứng đặc biệt là những tiến bộ trong việc cải tiến hiệu năng của bộ xử lí và băng thông mạng đó làm thay đổi một cách toàn diện kiến trúc của các máy tính hiệu năng cao. Và khi các máy tính hiệu năng cao được tạo ra bằng cỏch kết nối cỏc mỏy trạm (Workstation – WS) với nhau thỡ thuật ngữ “cụm mỏy tớnh” (Computer Cluster) được sử dụng để mô tả dạng máy tính này. Cụm máy trạm (Workstation Cluster -WSC) là một nhóm các máy trạm được kết nối với nhau thông qua một mạng tốc độ cao. Các máy tính trong một WSC truyền thông qua một trong hai giao thức truyền thông phổ biến đó là: truyền thông dựa trên kết nối và truyền thông không kết nối. Mô hỡnh kết nối dựa trờn giao thức TCP (Tranmission Control Protocol) với độ tin cậy cho việc truyền thông điệp được bảo đảm. Mô hỡnh khụng kết nối dựa trờn giao thức UDP (User Datagram THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 19 Protocol), với giao thức này độ tin cậy cho việc truyền thông điệp được bảo đảm. Hiện nay có rất nhiều phần mềm hỗ trợ việc tính toán song song trên WSC tiêu biểu như MPICH. WSC có rất nhiều ưu điểm đó là: o Kĩ thuật tính toán trên các cụm máy tính có thể mở rộng từ một hệ thống nhỏ đến các hệ thống rất lớn. Điều này thể hiện tính mềm dẻo và linh hoạt của hệ thống. Hệ thống có thể chỉ gồm một máy tính hoặc nhiều máy tính ghép nối mạng với nhau. Những máy tính nối mạng Internet cũng có thể ghép cụm được. Hệ thống cũng có thể bao gồm những máy tính chuyên dụng khác nhau. o Thiết bị phần cứng dùng để xây dựng một cụm máy tính như các máy tính cá nhân và các máy trạm hiện nay được bán rộng rói trờn thị trường với giá thành thấp. Về nguyên tắc một cụm máy tính chỉ cần có một màn hỡnh và một bàn phớm nờn giảm được chi phí ban đầu. o Các bộ xử lí mới có thể dễ dàng tích hợp vào hệ thống như là chúng đó cú sẵn trong hệ thống. Đây là ưu điểm của cụm máy tính so với những hệ thống song song khác và nó nói lên tính an toàn cao của hệ thống. Kiến trúc bó IBM 1600 của trung tâm tính toán hiệu năng cao: • 5 node tớnh toỏn pSeires 655, mỗi node gồm 8 CPU Power4+16 bit RISC 1.7 GHz của IBM; cache 5.6 MB ECC L2, 128 MB ECC L3, băng thông: 72.3 GBps; 32 GB RAM, băng thông bộ nhớ 51.2 GBps; 6x36 GB HDD. Năng lực tính toán tổng cộng khoảng 240 GFlóp (mở rộng tối đa 768 GFlops/16 node). • 1 node quản lớ phần mềm CSM p630: Power4+64 bit 1.2 GHz; cache 1.5 MB ECC L2, 8 MB ECC L3, băng thông: 12.8 GBps; 1 GB RAM, băng thông: 6.4 GBps; 6x36 GB HDD, DVD ROM. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 20 • 1 node điều khiển phần cứng HCM: Intel Xeon 3.06 GHz, 1GB RAM, 40 GB HDD, DVD RAM. • Các node được kết nối với nhau thông qua HPS (High Performance Switch – Switch hiệu năng cao), băng thông 2 GBps và Gethernet. • Hệ thống lưu trữ chung: IBM DS4400 và EXP700 kết nối với cụm IBM 1600 thông qua cáp quang với băng thông 2 GBps. • Các node chạy HĐH AIX 5L phiên bản 5.2 Kiến trỳc bú IBM 1350 của trung tâm tính toán hiệu năng cao: • 8 node tính toán, mỗi node gồm 2 chip Intel Xeon Dual Core 3.2 GHz, 2 GB RAM, 1x36 GB HDD, DVD ROM. Tổng năng lực tính toán của 8 node là khoảng 51.2 Gflops. • 2 node phục vụ lưu trữ, mỗi node gồm 2 chip Intel Xeon Dual Core 3.2 GHz, 3 GB RAM, 4x72 GB HDD. • 1 node đóng vai trũ quản lớ bao gồm chip Intel Xeon Dual Core 3.2 GHz, 3 GB RAM, 2x36 GBHDD. • Năng lực lưu trữ: thiết bị lưu trữ dùng chung EXP400 với 10x73 GB HDD SCSI 320 MBps 15KRpm, dùng hệ thống chia sẻ file: GPFS cho Linux v2.3.0.5 • Các node chạy HĐH Redhat Enterprise Linux 3.0 và được kết nối với nhau thông qua mạng Gethernet. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 21 Chương 2: GIAO DIỆN TRUYỀN THÔNG ĐIỆP MPI 2.1 Giới thiệu về MPI Giao diện truyền thông điệp chuẩn MPI (Message Passing Interface) là một thư viện truyền thông chuẩn. Mục đích của MPI là thiết lập một chuẩn truyền thông điệp linh hoạt và hiệu quả được sử dụng rộng rói cho việc viết cỏc chương trỡnh THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 22 truyền thụng điệp. MPI không phải là chuẩn ISO hay IEEE nhưng trên thực tế nó đó trở thành chuẩn công nghiệp cho việc viết các chương trỡnh truyền thụng điệp trên nền HPC (Hight Performance Computing). 2.2 Mụ hỡnh lập trỡnh MPI Trong mụ hỡnh lập trỡnh MPI, cỏc tiến trỡnh truyền thụng bằng cỏch gọi cỏc hàm thư viện để gửi và nhận thông điệp với những tiến trỡnh khỏc. Trong hầu hết cỏc chương trỡnh MPI, số bộ xử lý cố định khi khởi tạo chương trỡnh, và một tiến trỡnh được tạo ra trên một bộ xử lý. Tuy nhiờn, những tiến trỡnh này cú thể chạy những chương trỡnh khỏc nhau. Vỡ thế mụ hỡnh lập trỡnh MPI đôi khi được đề cập như là đa chương trỡnh đa luồng dữ liệu (MPMD) để phân biệt với mô hỡnh SPMD (mỗi bộ xử lý thực thi cựng một chương trỡnh). Số tiến trỡnh trong một chương trỡnh MPI thường cố định. Những tiến trỡnh cú thể sử dụng thao tỏc truyền thông điểm tới điểm từ một tiến trỡnh cụ thể tới được một tiến trỡnh khỏc, những thao tỏc này cú thể sử dụng để thực thi những truyền thông cục bộ và không có cấu trúc. Một nhóm các tiến trỡnh cú thể gọi cỏc thao tỏc truyền thụng tập thể để thực hiện những thao tác toàn cục như tổng hợp và quảng bá. MPI hỗ trợ truyền thông không đồng bộ (dị bộ). Có lẽ tính năng quan trọng nhất của MPI từ quan điểm của công nghệ phần mềm là nó hỗ trợ lập trỡnh module. Một cơ chế được gọi là bộ truyền thông (communicator) cho phộp lập trỡnh viờn MPI định nghĩa module trong đó đóng gói các cấu trúc truyền thông bên trong. Những thuật toỏn mà tạo ra chỉ một tỏc vụ trờn một bộ xử lý cú thể thực hiện trực tiếp sử dụng những hàm truyền thụng tập thể hay điểm tới điểm. Những thuật toán mà tạo ra nhiều tác vụ theo một cách động hoặc phụ thuộc vào sự thực hiện đồng thời của một vài tác vụ trên 1 bộ xử lý phải được biến đổi để có thể thực thi MPI. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 23 2.3 Những hàm MPI cơ bản Mặc dự MPI là một hệ thống phức tạp chỳng ta cú thể giải những bài toán thuộc một phạm vi rộng mà chỉ sử dụng 6 hàm cơ bản. Những hàm này khởi tạo và kết thúc một chương trỡnh MPI, xỏc định nhận dạng các tiến trỡnh, gửi và nhận thụng điệp. MPI_Init khởi tạo môi trường MPI MPI_Finalize đóng môi trường MPI MPI_Comm_size xác định số các tiến trỡnh MPI_Comm_rank xác định số hạng tiến trỡnh MPI-Send gửi một thông điệp MPI-Recv nhận một thông điệp Những hàm này được mô tả chi tiết sau đây,trong đó nhón IN, OUT, và INOUT đứng trước tham số chỉ ra rằng: IN: hàm sử dụng nhưng không làm thay đổi tham số. OUT: hàm không sử dụng nhưng có thể thay đổi tham số. INOUT: hàm sử dụng và cập nhật tham số. • MPI_Init (int*arge, char ***argv); Đây là hàm khởi tạo môi trường thực thi MPI. Tham số argc, argv được sử dụng trong C như là những tham số của chương trỡnh chớnh (hàm main). Hàm này phải được gọi trong mọi chương trỡnh MPI và trước bất kỳ hàm MPI nào khác, và chỉ được gọi một lần trong một chương trỡnh MPI chương. Với những chương trỡnh C, MPI_Init cú thể được sử dụng để truyền những tham số dũng lệnh tới tất cả cỏc bộ xử lý. • MPI_Finalize( ); THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 24 Dùng để đóng môi trường thực thi MPI. Hàm này được gọi cuối cùng trong mọi chương trỡnh MPI, khụng một hàm MPI nào cú thể gọi sau nú. • MPI_Comm_size (comm, & size); Hàm lấy số tiến trỡnh IN comm bộ truyền thụng OUT size số cỏc tiến trỡnh trong nhúm comm • MPI_Comm_rank (comm, & rank); Hàm lấy hạng của tiến trỡnh. IN comm bộ truyền thụng OUT rank số của tiến trỡnh trong nhúm comm. Một bộ truyền thụng gồm một tập cỏc tiến trỡnh trong đó các tiến trỡnh cú thể thực hiện truyền thụng với nhau. Bộ truyền thụng cung cấp một cơ chế nhận dạng tập các tiến trỡnh cho việc phỏt triển những chương trỡnh module và để đảm bảo các thông điệp dành cho những mục đích khác nhau không bị nhầm lẫn. Nó cung cấp giá trị mặc định MPI_COMM_WORLD, xác định tất cả các tiến trỡnh trong chương trỡnh. Mỗi tiến trỡnh được gán một số hạng là số nguyên liên tiếp bắt đầu từ 0. Số hạng này cũn được gọi là id của tiến trỡnh. Bốn hàm trờn thuộc nhúm những hàm quản lý mụi trường. Một ví dụ nhỏ sử dụng các hàm này viết bằng ngôn ngữ C. #include #include THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 25 int main(int argc, char **argv) { int rank, size; MPI_Init( &argc, &argv ); MPI_Comm_rank(MPI_COMM_WORLD, &rank ); MPI_Comm_size(MPI_COMM_WORLD, &size ); printf("Hello! I am %d of %d \n", rank, size); MPI_Finalize(); return 0; } Nếu chương trỡnh trờn được chạy bởi 4 tiến trỡnh thỡ ta sẽ thu được kết quả có dạng như sau: Hello! I am 1 of 4 Hello! I am 3 of 4 Hello! I am 0 of 4 Hello! I am 2 of 4 • MPI_Send (void *buff, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm); Đây là hàm gửi thông điệp. IN buff địa chỉ đầu tiên của bộ nhớ đệm chứa dữ liệu để gửi. IN count số phần tử dữ liệu trong bộ đệm. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 26 IN datatype kiểu của dữ liệu trong bộ đệm. IN dest số hạng của tiến trỡnh nhận. IN tag nhón của thụng điệp gửi. IN comm bộ truyền thụng. • MPI_Recv (void *buff, int count, MPI_Datatype datatype, int sourse, int tag, MPI_Comm comm, MPI_Status status) OUT buff địa chỉ đầu tiên của bộ nhớ đệm nhận dữ liệu. IN count kích thước của bộ nhớ đệm nhận tính bằng số phần tử dữ liệu. IN datatype kiểu dữ liệu của các phần tử trong bộ nhớ đệm nhận. IN source số hạng của tiến trỡnh nguồn (gửi). IN tag nhón của thụng điệp. OUT status trạng thỏi. Hai hàm này thuộc nhóm hàm truyền thông điểm tới điểm. Các hàm này chỉ truyền thông điệp giữa hai và chỉ hai tiến trỡnh MPI. Một tiến trỡnh thực hiện thao tỏc gửi và tiến trỡnh cũn lại thực hiện thao tỏc nhận tương ứng. Với ngụn ngữ C, chỳng ta cú thể lập trỡnh MPI bằng cỏch sử dụng thư viện mpi.h. Những tên hàm giống với MPI chuẩn nhưng chỉ MPI được viết hoa và chữ cái đầu tiên của tên hàm được viết hoa. Mó trả về cho việc khởi tạo thành cụng là MPI-SUCCESS. Một tập mó lỗi cũng được định nghĩa. Những hằng số đều được viết hoa và được định nghĩa trong thư viện mpi.h. Những kiểu dữ liệu MPI được định nghĩa cho mỗi kiểu dữ liệu C: MPI_CHAR, MPI_LONG, MPI_UNSIGNED_CHAR, MII_UNSIGNED, MPI_UNSIGNED_LONG, MPI_FLOAT, MPI_DOUBLE, MPI_LONG_DOUBLE… THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 27 Những tham số của hàm số cú nhón IN được truyền theo giá trị, trong khi những tham số nhón OUT, INOUT truyền theo tham chiếu (như con trỏ). Biến status thuộc kiểu MPI_Status có trường status.MPI_SOURCE và status.MPI_TAG gồm các thông tin về souce và tag như trong ví dụ sau (số tiến trỡnh cố định bằng 2). #include #include int main(int argc,char **argv) { int size, rank, dest, source, count, tag=1; char send=’x’, recv; MPI_Status status; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD, &size); MPI_Comm_rank(MPI_COMM_WORLD, &rank); if (rank = =0) { dest = 1; source = 1; MPI_Send(&send, 1, MPI_CHAR, dest, tag, MPI_COMM_WORLD); MPI_Recv(&recv, 1, MPI_CHAR, source, tag, MPI_COMM_WORLD, &status); } THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 28 else if (rank == 1) { dest = 0; source = 0; MPI_Recv(&send, 1, MPI_CHAR, source, tag, MPI_COMM_WORLD, &status); MPI_Send(&recv, 1, MPI_CHAR, dest, tag, MPI_COMM_WORLD); } MPI_Get_count(&status, MPI_CHAR, &count); printf("Process %d received %d char(s) from process %d with tag %d \n", rank, count,status.MPI_SOURCE,status.MPI_TAG); MPI_Finalize(); } 2.3 Những hàm truyền thụng tập thể Chúng ta có thể xây dựng nhiều chương trỡnh MPI chỉ với 6 hàm cơ bản được trỡnh bày trong phần 2.2. Tuy nhiờn, để thuận tiện cho việc truyền thông với tất cả các bộ xử lý trong một lời gọi, MPI cung cấp những hàm truyền thông tập thể. Tất cả các hàm này đều được thực hiện một cách tập thể, có nghĩa là mỗi tiến trỡnh trong một nhúm tiến trỡnh gọi hàm truyền thụng này với cựng cỏc tham số. • MPI_Barrier(MPI_Comm comm); Hàm đồng bộ hoá. IN comm bộ truyền thụng. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 29 • MPI_Bcast(void *buff, int count, MPI_Datatype datatype, int root, MPI_Comm comm ) INOUT buff địa chỉ của bộ đệm. IN count số phần tử trong bộ đệm. IN datatype kiểu dữ liệu của phần tử gửi. IN root hạng của tiến trỡnh thực hiện quảng bỏ. IN comm bộ truyền thụng. • MPI_Gather(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm) Hàm tổng hợp dữ liệu. • MPI_Scatter(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm) Hàm phõn phối dữ liệu. IN sendbuf địa chỉ đầu tiên của bộ nhớ đệm chứa các phần tử. IN sendcount số phần tử gửi. IN sendtype kiểu dữ liệu của phần tử gửi. OUT recvbuf địa chỉ đầu tiên của bộ nhớ đệm nhận. IN recvcount số phần tử nhận. IN recvtype kiểu dữ liệu của phần tử nhận. IN root số hạng của tiến trỡnh thực hiện. IN comm bộ truyền thụng. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 30 • MPI_Reduce(void* sendbuf, void* recvbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm) • MPI_Allreduce(void* sendbuf, void* recvbuf, int count, MPI_Datatype datatype, MPI_Op op, MPI_Comm comm) Hàm tớnh toỏn tập thể. IN sendbuf địa chỉ của bộ đệm gửi. OUT recvbuf địa chỉ của bộ đệm nhận. IN count số phần tử trong bộ đệm gửi. IN datatype kiểu dữ liệu của phần tử gửi. IN op phộp toỏn. IN root số hạng của tiến trỡnh nhận. IN comm bộ truyền thụng. Những hàm truyền thụng tập thể cú ba loại: • Đồng bộ hoá. • Di chuyển dữ liệu. • Tớnh toỏn tập thể. 2.3.1 Hàm đồng bộ hoá MPI_Barrier được sử dụng để đồng bộ hoá sự thực thi của một nhóm các tiến trỡnh. Mỗi tiến trỡnh khi gặp lời gọi hàm này đều dừng lại cho đến khi tất cả các hàm trong bộ truyền thông đều gọi nó. Hàm này cho phép phân tách hai pha của một chương trỡnh để đảm bảo những thông điệp trong hai pha không bị lẫn lộn với nhau. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 31 2.3.2. Cỏc hàm di chuyển dữ liệu MPI_Bcast, MPI_Gather và MPI_Scatter là ba hàm di chuyển dữ liệu tập thể. Tiến trỡnh gốc (thực thi cỏc hàm này) quảng bỏ, tổng hợp hay phõn phối dữ liệu cho tất cả cỏc tiến trỡnh trong bộ truyền thụng. Hoạt động của các hàm này được minh hoạ trong hỡnh 2.1. A0 A0 A0 A0 A0 A0 A1 A2 A3 A0 A1 A2 A3 A0 A1 A2 A3 A0 A1 A2 A3 data MPI_Bcast MPI_Gather MPI_Scatter processes THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 32 Hỡnh 2.1: Cỏc hàm di chuyển dữ liệu minh hoạ cho nhúm 4 tiến trỡnh. MPI_Bcast thực hiện việc quảng bỏ dữ liệu từ một tiến trỡnh tới tất cả cỏc tiến trỡnh khỏc. Tiến trỡnh root gửi dữ liệu giống nhau cho tất cả cỏc tiến trỡnh khỏc và cỏc tiến trỡnh này nhận cựng dữ liệu đó từ tiến trỡnh root. Dữ liệu định vị ở buff của tiến trỡnh root, gồm count phần tử kiểu datatype được sao lại trong buff của tất cả cỏc tiến trỡnh. MPI_Grather thực hiện việc tổng hợp dữ liệu từ tất cả cỏc tiến trỡnh về một tiến trỡnh. Tất cả cỏc tiến trỡnh bao gồm cả tiến trỡnh root gửi dữ liệu định vị tại sendbuf tới tiến trỡnh root. Tiến trỡnh này thu thập dữ liệu lưu vào recvbuf theo thứ tự trong đó dữ liệu gửi tiến trỡnh i đứng trước dữ liệu gửi tiến trỡnh i+1. Vỡ thế recvbuf của tiến trỡnh root lớn hơn P lần sendbuf với P là số tiến trỡnh trong bộ truyền thụng. MPI_Scatter ngược lại với MPI_Gather thực hiện việc phân phối dữ liệu từ một tiến trỡnh tới tất cả cỏc tiến trỡnh. Tiến trỡnh root gửi phần tử i của dữ liệu trong sendbuf tới tiến trỡnh i. Mỗi tiến trỡnh nhận dữ liệu từ root lưu vào recvbuf. Vỡ thế, sendbuf của tiến trỡnh root lớn hơn P lần recvbuf. Ta thấy cú sự khỏc biệt giữa hàm MPI_Scatter với hàm MPI_Bcast. Với MPI_Bcast mọi tiến trỡnh nhận cựng 1 trị số từ tiến trỡnh root, cũn với MPI_Scartter mọi tiến trỡnh nhận một trị số khỏc nhau. Ví dụ chương trỡnh sử dụng hàm MPI_Scatter phõn phối dữ liờu cho cỏc bộ xử lớ: #include #include #define N 4 int main(int argc,char **argv){ THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 33 int size, rank, sendcount, recvcount, source; float sendbuf[N][N] = { {1.0, 2.0, 3.0, 4.0}, {5.0, 6.0, 7.0, 8.0}, {9.0, 10.0, 11.0, 12.0}, {13.0, 14.0, 15.0, 16.0} }; float recvbuf[N]; MPI_Init(&argc,&argv); MPI_Comm_rank(MPI_COMM_WORLD, &rank); MPI_Comm_N(MPI_COMM_WORLD, &size); if (size = = N) { source = 1; sendcount = N; recvcount = N; MPI_Scatter(sendbuf,sendcount,MPI_FLOAT,recvbuf,recvcount, MPI_FLOAT,source,MPI_COMM_WORLD); printf("rank= %d Results: %f %f %f %f\n",rank,recvbuf[0], recvbuf[1],recvbuf[2],recvbuf[3]); } else printf("Must specify %d processors. Terminating.\n",N); MPI_Finalize(); } THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 34 Nếu chạy chương trỡnh với 4 bộ xử lớ kết quả sẽ là: rank= 0 Results: 1.000000 2.000000 3.000000 4.000000 rank= 1 Results: 5.000000 6.000000 7.000000 8.000000 rank= 2 Results: 9.000000 10.000000 11.000000 12.000000 rank= 3 Results: 13.000000 14.000000 15.000000 16.000000 2.3.3. Cỏc hàm tớnh toỏn dữ liệu Hàm MPI_Reduce và MPI_Allreduce đều là hàm tính toán dữ liệu. Chúng kết hợp trị số trong sendbuf của mỗi tiến trỡnh, sử dụng phộp toỏn op rồi trả về kết quả trong recvbuf của tiến trỡnh root khi sử dụng hàm MPI_Reduce, và của tất cả cỏc tiến trỡnh khi sử dụng MPI_Allreduce. Tất cả cỏc phộp toỏn trả về count kết quả cú cựng kiểu dữ liệu với cỏc toỏn hạng. Cỏc phộp toỏn bao gồm: MPI_MAX tớnh giỏ trị lớn nhất MPI_MIN tớnh giỏ trị nhỏ nhất MPI_SUM tớnh tổng MPI_PROD nhõn MPI_LAND và MPI_BAND phộp và từng bit MPI_LOR hoặc MPI_BOR phộp hoặc từng bit MPI_LXOR xor MPI_BXOR xor từng bit MPI_MAXLOC tỡm giá trị lớn nhất và địa chỉ MPI_MINLOC tỡm giỏ trị nhỏ nhất và địa chỉ THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 35 Hỡnh 2.2. Minh hoạ cho hàm MPI_Reduce và MPI_Allreduce. Processes Initial data: 2 4 0 1 2 3 5 7 0 3 6 2 MPI_Reduce với MPI_MIN, root= 0: 0 2 - - - - - - MPI_Allreduce với MPI_MIN 0 2 0 2 0 2 0 2 MPI_Reduce với MPI_SUM, root =2 - - - - - - 13 16 THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 36 Chương 3: MỘT SỐ PHƯƠNG PHÁP LẶP GIẢI HỆ ĐẠI SỐ TUYẾN TÍNH 3.1 Giới thiệu Cho hệ phương trỡnh đại số tuyến tớnh : bAX= (3.1.1) với nnnn RXRbRA ∈∈∈ × ,,      =++ =++ ⇔ nnnnn nn bxaxa bxaxa ... ............................... ... 11 11111 Biến đổi phương trỡnh (3.2.1) về dạng: X= BX + g trong đó nnn RgRB ∈∈ × , . Khi đó phép lặp gBXX kk +=+ )()1( với X(0) nR∈ cho trước hội tụ nếu 1<B (với . là chuẩn ma trận tương thích với chuẩn véc tơ). Điều kiện cần và đủ để cho dóy lặp hội tụ với X(0) lấy bất kỡ là 1)( <Bρ với ρ là bỏn kớnh phổ của ma trận. 3.2 Một số phương pháp lặp tuần tự giải hệ phương trỡnh đại số tuyến tính 3.2.1 Phương pháp lặp Jacobi Ta cú: THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 37 ULDA ++= trong đó: D là ma trận đường chéo, L và U lần lượt là ma trận tam giác dưới và ma trận tam giác trên. Cụng thức lặp Jacobi: 32143421 g k B k bDXULDX 1)(1)1( )( −−+ ++−= (3.2.1) Phương trỡnh thứ i của cụng thức lặp: ,...1,0,)()1( =+⋅−=∑ ≠ + k a b x a a x ii ik j ij ii ijk i Ta chứng minh sự hội tụ của phộp lặp Jacobi với A là ma trận chộo trội: • Nếu A chộo trội theo hàng: { 1 1 <           =⇒ ∑ ≠ ≤≤ ∞ ii ij ij ni a a MaxB • Nếu A chộo trội theo cột: Đặt biến phụ: iiii xaz =                 =                 =⇒ nn x x D z z z . . . . . . 11 Kớ hiệu: ixaz kiiii ∀= ,)( Nhõn 2 vế (2) với aii được: THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 38 ...,1,0, )( )1( )()1( =+−= +−= ∑ ∑ ≠ + ≠ + kb a z az bxaxa i jj k j ij ij k i i ij k jij k iii Cụng thức lặp cho Z dạng: 1ˆ ˆ 1 11 )()1( <               = +⋅= < ≠ ≤≤ + ∑ 321 jj ij ij ni kk a a MaxB bZBZ 3.2.2 Phương pháp lặp JOR (Jacobi Overrelaxation) Phương pháp Jacobi Overrelaxation (JOR) có công thức: ...,1,0,)( )(1)()1( =−+= −+ kAXbDXX kkk ω (3.2.2) với tham sốω . 3.2.3 Phương pháp SOR (Successive overrelaxation) Phương pháp Successive Overrelaxation (SOR) có công thức lặp: ( 1) 1 ( 1) ( ) ( )( ) (1 )k k k kX D b LX UX Xω ω+ − += − − + − (3.2.3) với ω là tham số gión. Khi 1ω = , SOR trở thành phương pháp Gass-Seidel. Viết lại (3.2.4) dưới dạng: bDUXDLXDXX kkkk 1)(1)1(1)()1( )1( −−+−+ +−−−= ωωωω Ta cú: bDUXDXXLDI kkk 1)(1)()1(1 )1()( −−+− +−−=+ ωωωω bUXDXXLD kkk ωωωω +−−=+ + )()()1( )1()( THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 39 Với giả thiết 0)det( ≠+ LD ω ta thu được: 44 344 2144444 344444 21 g k B k bLDXUDXLDX 1)(1)1( )())1(()( −−+ ++−−+= ωωωωω Điều kiện cần để phép lặp SOR hội tụ là 1det <B với ))1(()( 1 UDXLDB ωωω −−+= − . Ta cú 11 det)det( −− =+ DLD ω và DUD n det)1())1det(( ωωω −=−− Suy ra: n n B DDB )1(det det)1.(detdet 1 ω ω −= −= − 20 11 1)1(1det <<⇔ <−⇔ <−⇔< ω ω ω nB Vậy điều kiện cần để cho phép lặp SOR hội tụ là )2,0(∈ω . 3.3 Một số thuật toán lặp song song giải hệ phương trỡnh đại số tuyến tính Cấu trỳc của cỏc bộ xử lớ trong thuật toỏn Một trong những bộ xử lí được chỉ định làm Master; bộ xử lí này điều khiển sự thi hành của thuật toán. Những bộ xử lí khác được gọi là Server và chúng thi hành khi có yêu cầu của bộ xử lí Master. Những Server chịu trách nhiệm cho những tính toán trên dữ liệu phân tán. Bộ xử lí Master cũng đóng vai trũ giống một Server, vỡ một phần dữ liệu cũng được gán cho nó. Điều này đảm bảo rằng tất cả các bộ xử lí đều làm việc hết khả năng. 3.3.1 Thuật toỏn song song Jacobi Phộp lặp Jacobi cú thể song song hoỏ sử dụng cỏch phõn chia hàng phõn tỏn dữ liệu cho cỏc bộ xử lớ: THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 40 )( )( ,*: )( ,*:: 1 ,*: )1( : k qr k qrqrqr k qr XUXLbDX pppppppppp −−= −+ (3.3.1) Chỉ số dưới pp qr : chỉ ra rằng bộ xử lớ p sẽ cập nhật những phần tử qrrix i ,...,1,, += . Dấu * biểu thị tất cả cỏc cột. Thuật toán song song Jacobi có thể phân thành các bước sau: Bước 1: Khởi tạo: Mỗi bộ xử lí nhận hàng pp qr : của ma trận U và L, nhận cỏc phần tử pp qr : của véc tơ cột b; Bước 2: Lặp: Mỗi bộ xử lí Server nhận )(kX , cập nhật nú và trả lại )1( : +k qr Pp X cho bộ xử lí Master, nơi kiểm tra sự hội tụ. 3.3.2 Thuật toỏn song song JOR Phương pháp JOR không có sự phụ thuộc dữ liệu giữa những phần tử của các véc tơ trong mỗi phép lặp; vỡ thế phộp lặp JOR cú khả năng song song hóa dễ dàng. Sử dụng cách phân chia hàng, phép lặp JOR có thể phân tán giữa P bộ xử lí theo cách sau: PpxAbDXX kqrqrqr k qr k qr pppppppppp ,...,2,1,)( )( ,*:: 1 ,*: )( : )1( : =−+= −+ ω (3.3.2) Chỉ số dưới pp qr : chỉ ra rằng bộ xử lớ p sẽ cập nhật những phần tử qrrix i ,...,1,, += . Dấu * biểu thị tất cả cỏc cột. Thuật toán song song JOR có thể chia thành các bước như sau như sau: Bước 1: Khởi tạo: mỗi bộ xử lí nhận ω và tập hợp hàng pp qr : của ma trận A và những phần tử pp qr : của véc tơ b; Bước 2: Lặp: mỗi bộ xử lí Server p nhận )(kX , cập nhật nú và trả lại )1( : +k qr Pp X cho bộ xử lí Master, nơi kiểm tra sự hội tụ. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 41 3.3.3 Thuật toỏn song song SOR Phương pháp SOR có sự phụ thuộc dữ liệu giữa )(kX và )1( +kX . Khi song song hoá thuật toán đũi hỏi một số bộ xử lớ phải đợi trong khi giá trị của )1( +kX được tính toỏn. Ta sử dụng cụng thức lặp sau: ( ) bDXRDIXLDI kk 1)(1)1(1 )1()( −−+− +−−=+ ωωωω (3.3.3) Đặt: , )1( + = kXY ( ) bDXRDIZ kk 1)(1)( )1( −− +−−= ωωω Thỡ (3.3.7) trở thành: )(1 )( kZYLDI =+ −ω ∑ − = =−= 1 1 )( ,...,1,0, i j jij ij k ii niya a zy ω (3.3.4) Thuật toán SOR được chia thành bốn bước : 1. ( ) bDXRDIZ kk 1)(1)( )1( −− +−−← ωωω ; 2. Giải hệ )(1 )( kZYLDI =+ −ω sử dụng (3.3.7); 3. ;)1( YX k ←+ 4. Lặp lại bước 1-3 cho đến khi X hội tụ. Trong cách song song hoá thuật toán ở trên, bước 1 có thể phân tán ( theo hàng) giữa những bộ xử lí theo cách tương tự như phương pháp sử dụng trong phần 3.3.1 cho phương pháp JOR. Giải pháp cho hệ tam giác dưới trong bước 2 là được thực hiện tuần tự. Sử dụng kí hiệu trong phần 3.2, chúng ta có thể viết lại bước 1 như sau: THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 42 1. ( ) bDxRDIz pppppppppp qr k qrqrqr k qr 1 ,*: )( :*, 1 ,*:,* )( : : )1( −− +−−← ωωω với p= 1, 2, …, P, dấu * biểu thị tất cả cỏc hàng hoặc cột. 3.4 Chương trỡnh thử nghiệm 3.4.1 Bài toỏn mẫu Lập trỡnh thử nghiệm thuật toỏn lặp Jacobi, JOR, SOR cho bài toỏn mẫu giải hệ phương trỡnh đại số tuyến tính dạng (3.1.1) nhận được sau khi sai phân hóa phương trỡnh Laplace với điều kiện biên Dirichlet với ma trận A và véc tơ b như sau:                   =                   − −− −− − =                   = 1 0 . . 1 0 , 41 141 ... ... 141 14 , ... ... bB BI IBI IBI IB A (3.4.5) Trong tất cả các chương trỡnh ta sai số được sử dụng để kiểm tra sự hội tụ là 10-10 . 3.4.2 Đánh giá kết quả Thuật toỏn Jacobi song song giải bài toỏn mẫu sai số là 10-10, giải với bậc của ma trận A là 104 và 4.104. Với bậc của ma trận A là 104 thời gian thực hiện thuật toán trên các node của trung tâm tính toán hiệu năng cao với số node lần lượt là 1, 2 và 4, số tiến trỡnh lần lượt là 1, 2, 4, 8, 16. Số node 1 2 4 THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 43 Số tiến trỡnh 1 15,899 s 2 13,473 s 19,129 s 4 16,328 s 17,608 s 19,122 s 8 29,966 s 25,251 s 23,526 s 16 1 m 06,535 s 44,004 s 41,709 s Hỡnh 3.1: Thời gian thực hiện của thuật toỏn Jacobi song song với bậc của ma trận A là 104 Ta nhận thấy chỉ duy nhất một lần thời gian thực hiện thuật toỏn Jacobi song song với 1 node 2 tiến trỡnh nhanh hơn thời gian thực hiện với 1 tiến trỡnh, cú hệ số gia tốc là 1,18. Lượng thời gian giảm đi do giảm được tính toán không bù đắp nổi chi phí truyền thông khi có nhiều tiến trỡnh cựng tham gia. Mặt khỏc ta cũng nhận thấy khi số tiến trỡnh càng ớt tăng số node thời gian sẽ tăng lên. Chứng tỏ thời gian truyền thông giữa các node là đáng kể và lâu hơn thời gian truyền thụng trờn một node. Khi số tiến trỡnh càng tăng thỡ sử dụng càng nhiều node thời gian sẽ giảm đi đáng kể. Bậc của ma trận A mà bằng 4.104 thỡ thời gian thực hiện như sau: Số node Số tiến trỡnh 1 2 4 1 4 m 22,930 THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 44 s 2 2 m 40,256 s 2 m 53,667 s 4 2 m 40,055 s 2 m 22,296 s 2 m 12,572 s 8 3 m 40,030 s 2 m 57,010 s 2 m 04,943 s 16 6 m 16,950 s 4 m 23,142 s 3 m 03,719 s Hỡnh 3.2: Thời gian thực hiện của thuật toỏn Jacobi song song với cỡ của ma trận A là 4.104 Số node Số tiến trỡnh 1 2 4 2 1,640 1,514 4 1,643 1,846 1,983 8 1,195 1,485 2,104 16 0,697 0.999 1,431 Hỡnh 3.2: Hệ số tăng tốc của thuật toán Jacobi song song với bậc của ma trận A là 4.104 Rừ ràng khi bậc của ma trận A tăng lên, lượng tính toán tăng lên, lúc này khi chia xẻ công việc giữa cỏc tiến trỡnh thỡ thời gian giảm đi do giảm đươc tính toán đó lớn hơn rất nhiều thời gian truyền thông giữa các bộ xử lí và với số tiến trỡnh là THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 45 8 thực hiện trờn 4 node thỡ thời gian tớnh toỏn đó giảm hơn một nửa, hệ số gia tốc đạt giá trị lớn nhất. 3.4.3 Định hướng phát triển Tiếp tục đánh giá so sánh thời gian hiệu năng thực hiện của thuật toán JOR, SOR song song với thuật toán Jacobi song song. Tỡm hiểu và thử nghiệm một số phương pháp lặp khác để đưa về song song hoá giải hệ đại số tuyến tính, như R/B SOR, JSOR, PSOR. Từ đó hoàn thiện hơn những nghiên cứu về thuật toán lặp song song giải hệ đại số tuyến tính. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 46 KẾT LUẬN Khoá luận đó trỡnh bày sơ lược một số kiến thức tổng quan về xử lí song song gồm kiến trúc song song, các thành phần chính của máy tính song song, thiết kế và đánh giá một thuật toán song song và kiến trúc cụm máy tính của trung tâm tính toán hiệu năng cao. Khoá luận cũng đó giới thiệu về giao diện truyền thụng điệp MPI nhằm mục đích áp dụng lập trỡnh MPI với ngụn ngữ C cho bài toán giải hệ đại số tuyến tính bằng phương pháp lặp. Nội dung chính của khoá luận là giới thiệu một số phương pháp lặp giải hệ phương trỡnh đại số tuyến tính, đồng thời trỡnh bày một số thuật toỏn lặp song song. Cuối cựng đưa ra được chương trỡnh thử nghiệm và đánh giá những kết quả thu được bước đầu. Định hướng phát triển tiếp theo là tiếp tục nghiên cứu các thuật toán lặp song song để hoàn thiện hơn đề tài này. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 47 TÀI LIỆU THAM KHẢO 1. Parallel overrlaxation algorithm for systems of linear equations – Rudnei dias da Cunha, Tim Hopkins – UK 2. Designing and building parallel programs – Ian Fotster , 1995 3. Xử lí song song và phân tán – Đoàn Văn Ban - 2006 4. THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 48 PHỤ LỤC Chương trỡnh thử nghiệm 1. Thuật toỏn Jacobi THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 49 Chương trỡnh: #include #include #include #define n 100 /* số điểm trong của lưới */ #define epsilon 0.0000000001 /* sai số */ int main(int argc, char **argv) { int rank,size,i,j,N,myn; double *x,*subxnew,*subx,sum,temp,total; MPI_Status status; MPI_Init(&argc,&argv); /* Khởi tạo MPI */ /* Lấy hạng của cỏc tiến trỡnh */ MPI_Comm_rank(MPI_COMM_WORLD,&rank); /* Lấy số cỏc tiến trỡnh */ MPI_Comm_size(MPI_COMM_WORLD,&size); if(rank==0) { N=n*n; /* số phần tử của véc tơ cột x */ x=(double*)malloc(N*sizeof(double)); /* kết quả */ myn=N/size; /* số phần tử x trong mỗi bộ xử lớ */ } MPI_Bcast(&myn,1,MPI_INT,0,MPI_COMM_WORLD); MPI_Bcast(&N,1,MPI_INT,0,MPI_COMM_WORLD); THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 50 /* myn+2*n phần tử x(k+1) trong cỏc bộ xử lớ khởi tạo giỏ trị =0*/ subx=(double*)malloc((myn+(2*n))*sizeof(double)); for(i=0;i<(myn+2*n);i++) subx[i]=0; /* myn phần tử x(k+1) trong cỏc bộ xử lớ khởi tạo giỏ trị =0*/ subxnew=(double*)malloc((myn)*sizeof(double)); for(i=0;i<myn;i++) subxnew[i]=0; do { /* bộ xử lớ hạng rank gửi n phần tử cho bộ xử lớ hạng rank-1 */ if(rank>0) MPI_Send(subx+n,n,MPI_DOUBLE,rank-1,rank, MPI_COMM_WORLD); /* bộ xử lớ hạng rank gửi n phần tử cho bộ xử lớ hạng rank+1 */ if(rank<size-1) MPI_Send(subx+myn,n,MPI_DOUBLE,rank+1,rank, MPI_COMM_WORLD); /* bộ xử lớ hạng rank nhận n phần tử từ bộ xử lớ hạng rank+1 */ if(rank<size-1) MPI_Recv(subx+myn+n,n,MPI_DOUBLE,rank+1,rank+1,MPI_COMM_W ORLD,&status); /* bộ xử lớ hạng rank nhận n phần tử từ bộ xử lớ hạng rank-1 */ if(rank>0) MPI_Recv(subx,n,MPI_DOUBLE,rank-1,rank-1,MPI_COMM_WORLD, &status); /* Tớnh subxnew từ subx */ THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 51 MPI_Allreduce(&sum,&total,1,MPI_DOUBLE,MPI_SUM, MPI_COMM_WORLD); /* tớnh sai số*/ } while (total>epsilon);/* lặp khi chưa thoả món sai số */ MPI_Gather(subxnew,myn,MPI_DOUBLE,x,myn,MPI_DOUBLE,0, MPI_COMM_WORLD); /* kết quả */ MPI_Finalize(); /* đóng môi trường MPI */ return 0; } 2. Thuật toỏn JOR Chương trỡnh JOR tương tự như Jacobi nhưng khác phần công thức tính toán do có thêm tham số ω . 3.Thuật toỏn SOR Chương trỡnh viết cho thuật toỏn SOR: #include #include #include #define w 1 /*khai bao tham so ω */ #define n 256 /* số điểm trong của lưới */ #define epsilon 0.0000000001 /* sai số */ int main(int argc, char **argv) { int rank,size,i,j,k,N,myn; double *x,*y,*subxnew,*subx,sum,temp,total; MPI_Status status; THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 52 MPI_Init(&argc,&argv); /* Khởi tạo MPI */ /* Lấy hạng của cỏc tiến trỡnh */ MPI_Comm_rank(MPI_COMM_WORLD,&rank); /* Lấy số cỏc tiến trỡnh */ MPI_Comm_size(MPI_COMM_WORLD,&size); if(rank==0) { N=n*n; /* số phần tử của véc tơ cột x */ x=(double*)malloc(N*sizeof(double));/* x(k+1) */ y=(double*)malloc(N*sizeof(double)); /* x(k) */ myn=N/size; /* số phần tử x trong mỗi bộ xử lớ */ } MPI_Bcast(&myn,1,MPI_INT,0,MPI_COMM_WORLD); MPI_Bcast(&N,1,MPI_INT,0,MPI_COMM_WORLD); /* myn+n phần tử x(k+1) trong cỏc bộ xử lớ khởi tạo giỏ trị =0*/ subx=(double*)malloc((myn+n)*sizeof(double)); for(i=0;i<myn;i++) subx[i]=0; /* myn phần tử x(k+1) trong cỏc bộ xử lớ */ subxnew=(double*)malloc((myn)*sizeof(double)); do { /* bộ xử lớ hạng rank gửi n phần tử cho bộ xử lớ hạng rank-1 */ if(rank>0) MPI_Send(subx+n,n,MPI_DOUBLE,rank-1,rank, MPI_COMM_WORLD); THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 53 /* bộ xử lớ hạng rank nhận n phần tử từ bộ xử lớ hạng rank+1 */ if(rank<size-1) MPI_Recv(subx+myn+n,n,MPI_DOUBLE,rank+1,rank+1,MPI_COMM_W ORLD,&status); /* tính subxnew từ subx sử dụng bước 1 thuật toán */ MPI_Gather(subxnew,myn,MPI_DOUBLE,y,myn,MPI_DOUBLE,0, MPI_COMM_WORLD); if(rank==0) /* tớnh x(k+1) từ y theo bước 2 của thuật toán */ MPI_Scatter(x,myn,MPI_DOUBLE,subxnew,myn,MPI_DOUBLE,0, MPI_COMM_WORLD); /* tớnh sai số */ MPI_Allreduce(&sum,&total,1,MPI_DOUBLE,MPI_SUM, MPI_COMM_WORLD); } while (total>epsilon); /* lặp khi chưa thoả món sai số */ MPI_Finalize(); /* đóng môi trường MPI */ return 0; } THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN K IL O BO O K S. CO M 54 BẢNG CÁC CHỮ VIẾT TẮT SISD Single Instruction Single Data SIMD Single Instruction Multiple Data MISD Multiple Instruction Single Data MIMD Multiple Instruction Multiple Data CPU Central Processing Unit UMA Uniform Memory Access NUMA NonUniform Memory Access RAM Random Access Memory PRAM Parallel Random Access Memory CR Concurent Read CW Concurent Write ER Exclusive Read EW Exclusive Write COMA Cache – Only Memory Access WS Workstation WSC Workstation Cluster HPC High Performance Computing TCP Transmission Control Protocol UDP User Datagram Protocol MPI Message Passing Interface JOR Jacobi Overrelaxation SOR Successive Overrelaxation THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN