ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA TOÁN - CƠ - TIN HỌC Nguyễn Thị Xuyên ỨNG DỤNG KỸ THUẬT PHÂN HOẠCH VÀ CHIA ĐỂ TRỊ TRONG THUẬT TOÁN SONG SONG KHÓA LUẬN TỐT NGHIỆP HỆ ĐẠI HỌC CHÍNH QUY Ngành: Toán - Tin ứng dụng Người hướng dẫn: TS. Nguyễn Hữu Điển Hà Nội - 2008 LỜI CẢM ƠN Lời đầu tiên của khóa luận này em xin gửi lời cảm ơn sâu sắc tới thầy giáo hướng dẫn TS.Nguyễn Hữu Điển. Thầy đã giao đề tài và tận tình hướng dẫn em trong quá trình hoàn thành khóa luận này. Nhân dịp này em xin gửi lời cám ơn của mình tời toàn bộ các thầy cô giáo trong khoa Toán-Cơ-Tin học đã giảng dạy và giúp đỡ chúng em trong suốt quá trình học tập tại khoa. Đồng thời, tôi xin cảm ơn các bạn trong lớp K49A2 nghành Toán-Tin ứng dụng, khoa Toán-Cơ-Tin học đã nhiệt tình giúp đỡ tôi trong quá trình học tập tại lớp. Hà nội, ngày 10 tháng 05 năm 2008 Sinh viên Nguyễn Thị Xuyên Mục lục LỜI NÓI ĐẦU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Chương 1. Tính toán song song . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1. Giới thiệu chung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.1. Nhu cầu về tốc độ tính toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2. Khái niệm chung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.3. Phạm vi của tính toán song song . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 6 1.2. Các loại máy tính song song . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.1. Phân loại máy tính của Flynn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.2. Kiến trúc bộ nhớ của máy tính song song . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3. Các mô hình lập trình song song . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3.1. Lập trình chia sẻ bộ nhớ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2. Mô hình truyền thông điệp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 17 1.4. Thuật toán song song . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.4.1. Nguyên lý thiết kế thuật toán song song . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.2. Đánh giá các thuật toán song song . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 20 1.5. Lập trình song song với MPI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.5.1. Giới thiệu về MPI(Message Passing Interface) . . . . . . . . . . . . . . . . . . . . . . 1.5.2. Các hàm cơ bản trong chuẩn MPI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 25 Chương 2. Kĩ thuật phân hoạch, chia để trị và một số ứng dụng . . . . . . . 29 2.1. Các chiến lược phân hoạch, chia để trị . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.1.1. Kĩ thuật phân hoạch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2. Chia để trị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3. Chia để trị m-nhánh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 32 35 2.2. Một số ứng dụng trong thuật toán song song . . . . . . . . . . . . . . . . . . . . 37 2.2.1. Nhân ma trận với vecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2. Thuật toán sắp xếp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3. Bài toán N-body . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 41 46 2 Chương 3. Chương trình ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3 LỜI NÓI ĐẦU Tính toán song song là công cụ được xem như là "kết thúc cao của tính toán" đang thu hút được sự quan tâm của những nhà lập trình nói riêng và những người có nhu cầu tính toán hiệu năng nói chung bởi những ứng dụng đa dạng và to lớn của nó. Tính toán song song tạo cơ hội trong việc giải quyết các bài toán tính toán trên các khối lượng dữ liệu lớn hoặc đòi hỏi số lần lặp lớn mà tính toán thông thường không đáp ứng được. Đặc biệt, nó cho phép chúng ta khai thác hiệu quả các tài nguyên tính toán thông thường mà không đòi hỏi quá nhiều chi phí như các siêu máy tính. Song song hóa các thuật toán tuần tự là một hướng tiếp cận thông dụng để thiết kế các thuật toán song song. Trong đó, phân hoạch và chia để trị là hai kĩ thuật cơ bản để thiết lập tính song song cho bài toán một cách có hiệu quả. Khóa luận của em xin trình bày cơ bản về kĩ thuật phân hoạch và chia để trị cùng một số ứng dụng của nó để xây dựng thuật toán song song. Khóa luận của em gồm 3 chương: Chương 1: Trình bày tổng quan về tính toán song song, nhu cầu, phạm vi của tính toán song song, các loại máy tính song song và kiến trúc bộ nhớ, mô hình lập trình, nguyên lý thiết kế và thời gian thực hiện của thuật toán song song, phần cuối chương giới thiệu về thư viện truyền thông chuẩn MPI. Chương 2: Trình bày kĩ thuật phân hoạch và chia để trị. Ứng dụng của kĩ thuật vào bài toán nhân ma trận-vecto, thuật toán song song bucket sort và quick sort, cuối cùng là bài toán N-body với việc song song hóa thuật toán Barnes-Hut. Chương 3: Chương trình ví dụ Tuy đã có nhiều cố gắng nhưng do thời gian và khả năng có hạn nên các vấn đề trong khóa luận vẫn chưa được trình bày sâu sắc và không thể tránh khỏi có những sai sót trong cách trình bày. Mong được sự góp ý xây dựng của thầy cô và các bạn. Em xin chân thành cảm ơn! 4 Chương 1 Tính toán song song 1.1. Giới thiệu chung 1.1.1. Nhu cầu về tốc độ tính toán Ngày nay, với các bài toán yêu cầu xử lý trên một số lượng dữ liệu lớn và phức tạp như sự mô phỏng những hệ thống phức tạp và "những vấn đề thách thức lớn" như: dự báo thời tiết và khí hậu, những phản ứng hóa học và hạt nhân, hệ gen sinh học,...đặt ra một nhu cầu lớn về tốc độ tính toán. Những bài toán này thường yêu cầu một lượng lớn các phép tính lặp lại trên một khối lượng lớn dữ liệu để đưa ra một kết quả đúng đắn, và các phép tính này cần hoàn thành trong một khoảng thời gian hợp lý. Ví dụ như bài toán dự báo thời tiết không thể xử lý được bằng các máy tính thông thường vì thời gian xử lý là khoảng 10 năm, điều này hoàn toàn không phù hợp. Để giải quyết được các bài toán trên ta cần phải tăng tốc độ tính toán. Mặc dù trong những thập kỉ vừa qua chúng ta đã được chứng kiến những thành tựu to lớn về công nghệ vi xử lý. Tốc độ đồng hồ của các bộ xử lý đã tăng từ khoảng 40MHz (MIPS R3000, circa 1988) tới trên 2,0 GHz (Pentium 4, circa 2002); cùng một lúc, các bộ xử lý có khả năng thực hiện đa chỉ lệnh trong cùng một chu kỳ...Nhưng do giới hạn về vật lý nên khả năng tính toán của các bộ xử lý không thể tăng mãi được. Một cách để tăng tốc độ tính toán đó là sử dụng tính toán song song. 1.1.2. Khái niệm chung Thông thường, phần mềm được viết trên máy tính tuần tự có đặc điểm: • Được chạy trên một máy tính đơn với một bộ xử lý(CPU). 5 • Một bài toán được thực hiện bằng một chuỗi các dòng lệnh rời rạc, các dòng lệnh này được thực hiện nối tiếp nhau. • Tại mỗi thời điểm chỉ có một dòng lệnh được thực hiện. Hình 1.1: Mô hình tính toán tuần tự Theo nghĩa đơn giản nhất, tính toán song song là sử dụng đồng thời nhiều tài nguyên tính toán để giải quyết một bài toán tính toán. Có đặc điểm sau: • Được thực hiện trên nhiều bộ xử lý. • Một bài toán được chia thành các phần rời rạc, các phần này có thể được giải quyết đồng thời. • Từng phần nhỏ được giải quyết theo mô hình tuần tự. • Các dòng lệnh của mỗi phần thực thi một cách đồng thời trên các bộ xử lý khác nhau. Các tài nguyên tính toán ở đây có thể là: một máy tính đơn với nhiều bộ xử lý, một số lượng máy tính tùy ý được nối với nhau bằng đường mạng hoặc có thể là sự kết hợp của hai mô hình trên. 1.1.3. Phạm vi của tính toán song song Tính toán song song đã làm nên những tác động to lớn trong nhiều lĩnh vực đang còn hạn chế từ việc mô phỏng tính toán cho các ứng dụng kĩ thuật và khoa học cho tới các ứng dụng thương mại trong vấn đề khai mỏ dữ liệu và xử lý giao dịch. Dưới đây là một số các ứng dụng đa dạng của tính toán song song. 6 Hình 1.2: Mô hình tính toán song song Các ứng dụng trong kĩ thuật và thiết kế Tính toán song song đã được sử dụng và đã mang lại những thành công lớn trong việc thiết kế cánh máy bay (tối ưu hóa sự nâng, sự kéo và tính bền vững), động cơ đốt trong (tối ưu hóa sự phân phối điện và sự cháy), các mạch tốc độ cao và các cấu trúc khác. Các ứng dụng khác trong thiết kế và kĩ thuật tập trung vào sự tối ưu hóa nhiều quá trình. Các máy tính đã được dùng để giải nhiều bài toán tối ưu hóa liên tục và rời rạc. Các thuật toán đơn hình, phương pháp điểm trong việc tối ưu đường thẳng, phân nhánh và giới hạn (Branch and bound), lập trình di truyền cho tối ưu rời rạc đã được song song hóa một cách hiệu quả và được sử dụng thường xuyên. Các ứng dụng trong khoa học Trong những năm qua chúng ta đã được chứng kiến cuộc cách mạng trong việc ứng dụng tính toán khoa học hiệu năng cao. Việc sắp xếp có thứ tự bộ gen người đã mở ra những biên giới mới thú vị trong nghành tin sinh học. Sự đặc trưng cấu trúc, chức năng của gen và protein nắm giữ sự hứa hẹn về kiến thức và uy thế căn bản của các quá trình sinh học. Việc phân tích các chuỗi sinh học theo hướng phát triển những loại thuốc và cách điều trị mới đối với bệnh tật và các điều kiện y học yêu cầu những thuật toán có tính đổi mới là một lĩnh vực yêu cầu khả năng tính toán quy mô lớn. Hơn thế nữa, những kỹ thuật tính toán song song mới nhất được mục tiêu hóa đặc biệt theo hướng ứng dụng trong tin sinh học. Những thành tựu trong hóa học và vật lý học tính toán tập trung vào các nghiên cứu được xếp theo quy mô từ các hiện tượng lượng tử cho tới các cấu trúc phân 7 tử lớn. Những nghiên cứu này đã cho kết quả trong việc thiết kế nguyên liệu mới và những quy trình hiệu quả hơn. Các ứng dụng trong vật lý học thiên thể đã được khám phá đó là sự nở giãn của thiên hà, các quy trình nhiệt hạch, và phân tích kho dữ liệu khổng lồ từ các kính thiên văn. Việc mô phỏng thời tiết, khai thác khoáng sản, dự báo lũ lụt,.v.v dựa chủ yếu vào máy tính song song và có tác động quan trọng tới cuộc sống hàng ngày. Các ứng dụng trong thương mại Với hiệu ích lan rộng của web được tích hợp các nôi dung động và tĩnh đang gia tăng nhấn mạnh tời nhu cầu về các máy chủ chi phí thấp có khả năng cung cấp thể hiện có thể biến đổi được. Các mô hình song song từ đa bộ xử lý tới máy cụm linux được sử dụng như là các máy chủ cơ sở dữ liệu và web. Tính sẵn sàng của dữ liệu giao dịch quy mô lớn đóng vai trò đáng kể trong việc khai mỏ dữ liệu, phân tích tối ưu hóa công việc kinh doanh và các quyết định marketing. Khối lượng lớn và sự phân bố theo địa lý của những dữ liệu đòi hỏi sử dụng các thuật toán song song hiệu quả đối với những bài toán như khai mỏ quy tắc kết hợp, phân nhóm, phân lớp và phân tích chuỗi thời gian. Các ứng dụng trong hệ thống máy tính Khi các hệ thống máy tính trở nên rộng khắp và sự tính toán trải rộng trên toàn mạng, thì các vấn đề xử lý song song cũng được ứng dụng nhiều hơn. Trong việc bảo mật máy tính, việc phát hiện xâm phạm là một thử thách đáng kể. Trong trường hợp phát hiện xâm phạm mạng, dữ liệu được thu thập từ các trang phân tán và phải được phân tích một cách nhanh chóng. Việc không thể thu thập được dữ liệu này tại một vị trí trung tâm để phân tích đòi hỏi các thuật giải song song và phân tán. Trong lĩnh vực mật mã, ứng dụng đặc biệt nhất của tính toán song song trên Internet tập trung vào việc phân tích các số nguyên cực lớn. Các hệ thống nhúng tăng dựa trên các thuật toán điều khiển phân tán để hoàn thành một số tác vụ. Một ô tô hiện đại gồm mười bộ xử lý liên lạc với nhau để thực hiện các tác vụ phức tạp trong việc tối ưu hóa quá trình tiến hành và sự thực hiện. Trong các hệ thống này, các thuật toán phân tán và song song truyền thống để lựa chọn vật dẫn đầu và tập độc lập lớn nhât, vv...thường được sử dụng. 1.2. Các loại máy tính song song 1.2.1. Phân loại máy tính của Flynn Dù là máy tính tuần tự hay song song đều phải thực hiện bằng cách thực thi các chỉ lệnh trên dữ liệu. 8 Dòng chỉ lệnh nói cho máy tính biết phải làm gì. Dòng dữ liệu bị ảnh hưởng bởi các chỉ lệnh. Dựa vào số lượng dòng lệnh và số lượng dòng dữ liệu thực hiện tại cùng một thời điểm Micheal Flynn đã phân các máy tính thành 4 loại. • Máy tính SISD: đơn dòng lệnh-đơn dòng dữ liệu (Single Instruction StreamSingle Data Stream) Máy tính SISD chỉ có một bộ xử lý, ở mỗi thời điểm thực hiện một chỉ lệnh và chỉ đọc, ghi một mục dữ liệu. Máy tính SISD còn được gọi là đơn chương trình-đơn dòng dữ liệu, SPSD (Single Program Stream-Single Data Stream). Vì chỉ có một bộ xử lý nên các thuật toán cho máy tính SISD không bao hàm tính song song. Hình 1.3: Mô hình máy tính SISD • Máy tính MISD: đa dòng lệnh - đơn dòng dữ liệu (Multiple Instruction Stream - Single Data Stream) Máy tính MISD có nhiều bộ xử lý, mỗi bộ xử lý có đơn vị điều khiển (Control Hình 1.4: Mô hình máy tính MISD Unit) riêng, chia sẻ một bộ nhớ chung. Máy tính MISD còn được gọi là MPSD (Multiple Program Stream - Single Data Stream, đa chương trình - đơn dòng dữ liệu). Tính song song có thể đạt được trong hệ thống máy MISD bằng cách cho các bộ xử lý thực hiện các công việc khác nhau tại cùng một thời điểm trên cùng một tập dữ liệu. 9 • Máy tính SIMD: đơn dòng lệnh-đa dòng dữ liệu (Single Instruction streamMultiple Data Stream) Máy tính SIMD có một đơn vị điều khiển để điều khiển nhiều bộ xử lý thực Hình 1.5: Mô hình máy tính SIMD hiện theo một dòng lệnh đơn. Tức là các bộ xử lý này thực hiện cùng một câu lệnh trên các mục dữ liệu khác nhau. Máy tính SIMD còn được gọi là máy tính SPMD, đơn chương trình - đa dòng dữ liệu. Các bài toán giải quyết được SIMD yêu cầu các bộ xử lý giao tiếp với nhau để trao đổi dữ liệu hay kết quả. Việc này có thể được thực hiện theo hai cách: – Sử dụng bộ nhớ chia sẻ và các biến chia sẻ. – Sử dụng một số dạng liên kết mạng và truyền thông điệp(bộ nhớ phân tán). • Máy tính MIMD: đa dòng lệnh - đa dòng dữ liệu (Multiple Instruction StreamMultiple Data Stream) Máy tính MIMD có N bộ xử lý, N dòng lệnh, và N dòng dữ liệu. Mỗi bộ xử lý có thể thực hiện chỉ lệnh từ đơn vị điều khiển riêng của nó. Tức là các bộ xử lý có thể làm các việc khác nhau trên các dữ liệu khác nhau tại cùng một thời điểm. Đây là loại máy tổng quan và mạnh nhất trong các loại máy song song. Hai loại máy tính song song cơ bản nhất là hệ thống đa bộ xử lý bộ nhớ chia sẻ và hệ thống đa máy tính bộ nhớ phân tán đều thuộc loại máy MIMD. Máy tính MIMD với bộ nhớ chia sẻ được gọi là multiprocessors (máy đa bộ xử lý). Ví dụ các máy ENCORE, MULTIMAX, SEQUENT và BALANCE. Máy tính MIMD với một mạng liên kết được gọi là multicomputers (hệ đa máy tính), đôi khi được gọi là hệ thống phân tán. Ví dụ INTEL iPSC, NCUBE/7 và các mạng transputer. Ta có thể tổng quát khả năng của 4 loại máy tính theo nguyên tắc Flynn như sau: 10 Hình 1.6: Mô hình máy tính MIMD 1.2.2. Kiến trúc bộ nhớ của máy tính song song Hệ thống đa bộ xử lý bộ nhớ chia sẻ • Đặc điểm chung: – Một máy tính thông thường chứa một bộ xử lý để thực thi chương trình được lưu trong bộ nhớ chính. Mỗi vùng trong bộ nhớ chính được xác định bằng các số gọi là địa chỉ của nó. Địa chỉ được đánh số bắt đầu từ 0 cho tới 2n − 1 nếu có n bit trong địa chỉ. – Mô hình bộ nhớ chia sẻ được mở rộng từ mô hình bộ xử lý đơn. Mô hình bộ nhớ chia sẻ có đa bộ xử lý được kết nối tới các module của bộ nhớ đa. các bộ xử lý kết nối tới bộ nhớ có thể qua một số dạng mạng liên kết. – Hệ thống đa bộ xử lý bộ nhớ chia sẻ làm việc với một không gian địa chỉ đơn, tức là mỗi vùng trong toàn bộ hệ thống bộ nhớ chính có một địa chỉ duy nhất, tất cả các bộ xử lý truy cập tới vùng nhớ đó theo địa chỉ này. – Máy tính chia sẻ bộ nhớ được chia thành 2 loại dựa trên thời gian truy cập bộ nhớ, đó là : truy cập bộ nhớ đồng dạng (Uniform Memory Access, UMA) và truy cập bộ nhớ không đồng dạng (Nonuniform Memory Access, NUMA). ∗ Truy cập bộ nhớ đồng dạng: Thời gian và mức độ truy cập tới bộ nhớ là như nhau đối với mỗi bộ xử lý. Khi kiến trúc bộ nhớ có gắn thêm bộ đệm nhất quán thì sự truy cập của một bộ xử lý tới bộ nhớ chia sẻ là rõ ràng đối với các bộ xử lý còn lại, được gọi là bộ 11 Hình 1.7: Chức năng của 4 mô hình máy tính đệm gắn kết nhất quán truy cập đồng dạng(Cache coherent UMA, CC-UMA). ∗ Truy cập bộ nhớ không đồng dạng: Bộ nhớ chia sẻ được phân tán cho các bộ xử lý thành bộ nhớ cục bộ và tuyển tập tất cả các đơn thể bộ nhớ tạo ra bộ nhớ chung cho các bộ xử lý. Thời gian truy cập tới bộ nhớ cục bộ nhanh hơn thời gian truy cập tới bộ nhớ không cục bộ. Khi được gắn thêm bộ đêm nhất quán ta có khái niệm bộ đệm nhất quán truy cập không đồng dạng (CC-NUMA) • Ưu điểm – Không gian địa chỉ chung được cung cấp cho người sử dụng một cách thân thiện bởi một chương trình tương thích với bộ nhớ. – Sự phân chia dữ liệu giữa các tác vụ nhanh và đồng dạng do bộ nhớ gần với các bộ xử lý. • Nhược điểm – Khó thể hiện phần cứng để tất cả các bộ xử lý đạt được tốc độ truy cập nhanh tới tất cả bộ nhớ chia sẻ. – Vì các bộ xử lý được kết nối với bộ nhớ nên khi muốn tăng thêm bộ xử lý sẽ gặp nhiều khó khăn về thiết kế và sản xuất vì sẽ làm tăng các giao tiếp trên bộ nhớ chung, đối với hệ thống bộ đệm nhất quán, giao tiếp tăng sẽ đặt ra đòi hỏi quản lý bộ nhớ/bộ đệm. 12 Hình 1.8: Máy tính bộ nhớ chia sẻ Hình 1.9: Máy tính bộ nhớ phân tán Hệ thống đa máy tính bộ nhớ phân tán • Đặc điểm chung Hệ thống được tạo thành bằng cách kết nối các máy tính hoàn chỉnh qua một mạng liên kết. Mỗi máy tính có một bộ xử lý và bộ nhớ cục bộ không thể bị truy cập từ các bộ xử lý khác trong hệ thống. Bộ nhớ được phân tán giữa các máy tính và mỗi bộ nhớ có không gian địa chỉ riêng. Mỗi bộ xử lý chỉ có thể truy cập vào vùng bộ nhớ riêng của nó. Một bộ xử lý muốn truy cập vào vùng dữ liệu của một máy tính cần gửi thông điệp (message)qua mạng liên kết. Thông điệp này có thể là dữ liệu mà các bộ xử lý khác yêu cầu cho tính toán của chúng. • Ưu điểm Kiến trúc vật lý của hệ thống phân tán bộ nhớ đơn giản hơn hệ thống bộ nhớ chia sẻ nên dễ dàng để làm lớn hệ thống. Mỗi bộ xử lý có thể nhanh chóng truy cập vào bộ nhớ riêng của mình mà không có giao thoa hay cố gắng duy trì sức kết dính bộ đệm. Do có thể sử dụng các bộ xử lý và các mạng thông thường nên chi phí không quá cao. • Nhược điểm Đòi hỏi người lập trình phải xác lập một số lượng lớn các giao tiếp dữ liệu giữa các bộ xử lý. Dữ liệu không được chia sẻ, nên phải được sao lại. Đây có thể là khó khăn trong các ứng dụng yêu cầu nhiều thao tác trên một lượng lớn dữ liệu. Thời gian truy cập bộ nhớ không đồng dạng (NUMA) 13 Hình 1.10: Máy tính bộ nhớ chia sẻ-phân tán Hệ thống bộ nhớ chia sẻ-phân tán • Đặc điểm chung – Hệ thống được kết hợp từ hai mô hình trên. Trong mô hình này mỗi bộ xử lý có thể truy cập tới toàn bộ bộ nhớ sử dụng một không gian địa chỉ đơn. – Khi một bộ xử lý truy cập tới một vùng nhớ không phải là vùng nhớ cục bộ của mình, thì việc truyền thông điệp diễn ra để chuyển dữ liệu từ bộ xử lý đó tới vùng nhớ hoặc từ vùng nhớ tới bộ xử lý bằng một số phương thức được tự động điều này đã dấu đi sự thật là bộ nhớ được phân tán. – Đối với một hệ thống bộ nhớ được phân tán một cách vật lý, người ta sử dụng bộ nhớ cache cục bộ tới mỗi bộ xử lý để có được bộ nhớ chia sẻ giữa các bộ xử lý. Khi cần giao tiếp, dữ liệu được copy từ các bộ nhớ cache. – Những máy tính nhanh nhất và lớn nhất sử dụng kiến trúc bộ nhớ chia sẻ-phân tán. Xu hướng phát triển hiện nay dự báo rằng kiến trúc bộ nhớ này sẽ tiếp tục lân áp và tăng nhanh về cả số lượng và phạm vi sử dụng. • Ưu điểm và nhược điểm: là bất kì điểm chung nào cuả hai loại kiến trúc bộ nhớ trên. 14 1.3. Các mô hình lập trình song song Ở trên chúng ta đã xem xét các thể hiện phần cứng cho tính toán song song, các mô hình máy tính song song. Vấn đề quan trọng đặt ra là phải viết một chương trình bằng một ngôn ngữ lập trình bậc cao và chạy trên một môi trường xác định sao cho tận dụng hết được khả năng của máy tính. Mô hình lập trình song song là sự trừu tượng hóa trên các kiến trúc phần cứng và bộ nhớ của máy tính song song. Mô hình lập trình song song không đặc tả riêng cho một loại kiến trúc bộ nhớ hay máy tính cụ thể. Một cách lý thuyết thì môt loại mô hình lập trình song song có thể được thể hiện dưới một phần cứng bất kì. Dưới đây là hai mô hinh lập trình song song phổ biến. 1.3.1. Lập trình chia sẻ bộ nhớ Trong mô hình lập trình chia sẻ bộ nhớ, các tác vụ chia sẻ một không gian địa chỉ chung nơi các tác vụ đọc và ghi dữ liệu. Các cơ chế khác nhau như locks/semaphores có thể được dùng để điều khiển việc truy cập tới bộ nhớ chia sẻ. Một ưu điểm của mô hình này theo quan điểm của người lập trình đó là không có quyền sở hữu dữ liệu riêng nên không cần phải đặc tả việc truyền thông dữ liệu hiển giữa các tác vụ. Việc phát triển chương trình có thể được đơn giản hóa. Nhược điểm quan trọng của mô hình là các ngôn ngữ của việc thực hiện, nó trở nên khó hiểu và khó quản lý vùng dữ liệu hơn. Lập trình chia sẻ bộ nhớ dựa vào tiến trình • Tiến trình (processes) là một bản thể của chương trình đang thực thi. Yêu cầu của xử lý song song là khả năng tạo ra một số tiến trình cần thiết cho bài toán và khả năng hủy bỏ tiến trình khi phần việc xử lý song song kết thúc để giải phóng các tài nguyên mà tiến trình đã chiếm giữ và không cản trở hoạt động của những tiến trình khác. • Các hệ điều hành như Linux, Unix hay Windows đều phải điều phối sự hoạt động đồng bộ của các tiến trình. Khi muốn sử dụng bộ nhớ chung, ta cần phải xin cấp phát bộ nhớ và sau đó khi sử dụng xong phải giải phóng chúng. • Khi có một tiến trình truy cập vào một bộ nhớ với mục đích cập nhật thì nó phải được đảm bảo rằng không một tiến trình dữ liệu nào khác đọc dữ liệu ở vùng nhớ đó cho tới khi việc cập nhật đó kết thúc. 15 Lập trình chia sẻ bộ nhớ dựa vào luồng • Khái niệm luồng – Luồng (thread) cũng giống như các tiến trình là kĩ thuật cho phép một chương trình có thể thực hiện nhiều công việc tại một thời điểm, thực hiện công việc tại một khoảng thời gian cho trước. Các luồng tồn tại bên trong các tiến trình. – Các luồng của một tiến trình có thể chia sẻ với nhau về không gian địa chỉ chương trình, các đoạn dữ liệu và môi trường xử lý, đồng thời cũng có những vùng dữ liệu riêng để thao tác. – Công việc của một luồng có thể được miêu tả như là một chương trình con của một chương trình chính. Một luồng bất kì có thể thực thi một chương trình con bất kì cùng lúc với các luồng khác. – Các luồng giao tiếp với các luồng khác qua bộ nhớ toàn cục (global memory). Việc này yêu cầu xây dựng việc đồng bộ để đảm bảo rằng chỉ có một luồng cập nhật một địa chỉ chung tại một thời điểm. Việc đồng bộ các luồng thực hiện hiệu quả hơn đối với các tiến trình vì đồng bộ luồng chủ yếu tập trung vào sự truy cập các biến chung của chương trình. • Các thể hiện của luồng Có nhiều hệ điều hành hỗ trợ đa luồng như: SUN Solaris, Windows NT v.v. những nỗ lực tiêu chuẩn hóa không giống nhau đã đưa tới hai thể hiện rất khác nhau của luồng đó là: POSIX Threads và OpenMP. POSIX Threads: Thường được gọi là Pthreads – Thư viện cơ sở yêu cầu sự mã hóa song song. – Được chỉ rõ bởi tiêu chuẩn IEEE POSIX 1003.1c (1995) – Chỉ sử dụng ngôn ngữ C – Hầu hết các nhà cung cấp phần cứng hiện này đều đề xuất Pthreads ngoài các thể hiện luồng riêng của họ. – Tính song song rất rõ ràng, yêu cầu người lập trình chú ý tới chi tiết OpenMP – Cơ sở chỉ thị biên dịch có thể sử dụng mã tuần tự. – Được định nghĩa và chứng thực bởi một nhóm các nhà cung cấp phần cứng và phần mềm chủ yếu. OpenMP Fortran API được phát hành ngày 28 tháng 10 năm 1997. C/C++ được phát hành muộn hơn vào năm 1998. – Các nền lập trình bao gồm Unix và Windows NT. – Có sẵn trong các thể hiện của C/C++ và Fortran. 16 – Có thể được sử dụng để cung cấp cho các bài toán có tính song song gia tăng dễ dàng và đơn giản. 1.3.2. Mô hình truyền thông điệp Giống như mô hình chia sẻ bộ nhớ, các đơn vị xử lý song trong mô hình truyền thông điệp là các tiến trình. Trong mô hình truyền thông điệp: • Các tiến trình có thể thực hiện trên những bộ xử lý khác nhau và không được truy cập vào không gian bộ nhớ chia sẻ. • Việc truyền thông giữa các tiến trình thông qua việc gửi và nhận thông điệp. • Việc đồng bộ hóa các tiến trình của một chương trình song song được thực hiện theo cơ chế truyền thông điệp. Khi một tiến trình muốn gửi một thông điệp thì nó phải chờ cho đến khi tiến trình nhận sẵn sàng nhận thông điệp đó và ngược lại, cũng tương tự. Các thể hiện của mô hình truyền thông điệp • Các thể hiện của mô hình truyền thông điệp thường chứa một thư viện các hàm con được nhúng trong mã nguồn. Người lập trình có nhiệm vụ xác định tất cả các khả năng song song. • Trong những năm 1980 có nhiều thư viện truyền thông điệp khác nhau. Điều này dẫn đến khó khăn cho những người lập trình khi muốn phát triển một ứng dụng hiện có. • Năm 1992, một thư viện chuẩn của mô hình truyền thông điệp đã được thiết lập, đó là chuẩn MPI(Message Passing Interface). Ngoài ra còn một số mô hình lập trình song song thường dùng khác như song song dữ liệu, Hybrid, SPMD, MPMD... 1.4. Thuật toán song song 1.4.1. Nguyên lý thiết kế thuật toán song song Phát triển thuật toán là một phần cơ bản của việc giải quyết bài toán sử dụng máy tính. Một thuật toán tuần tự về bản chất là một cách làm hay một số tuần tự các bước để giải quyết bài toán đưa ra bằng một máy tính tuần tự. Một cách tương tự, một thuật toán song song là một cách làm chỉ cho chúng ta làm thế nào để giải quyết bài toán đưa ra bằng các máy tính song song. Tuy nhiên, việc đặc tả một thuật toán song song liên quan tới nhiều hơn là việc 17 đặc tả các bước. Ít nhất thì một thuật toán song song có thêm kích thước tương tranh và người thiết kế thuật toán phải chỉ rõ các bước nào có thể thực hiện một cách đồng thời. Đây cũng chính là nguyên nhân để có thể đạt được bất cứ lợi ích nào từ việc sử dụng các máy tính song song. Trong thực tế, việc xây dựng một thuật toán song song có thể gồm một số hoặc tất cả các bước sau: • Xác định các phần công việc có thể thực hiện đồng thời. • Gán các công việc có thể thực hiện đồng thời vào nhiều tiến trình chạy song song. • Phân tán dữ liệu đầu vào, đầu ra, và trung gian. • Quản lý việc truy cập tơi dữ liệu chia sẻ. • Đồng bộ các bộ xử lý ở các giai đoạn khác nhau của việc thực thi chương trình song song. Có năm nguyên lý chính trong thiết kế thuật toán song song: Các nguyên lý lập lịch Giảm tối thiểu các bộ xử lý sử dụng trong thuật toán song song sao cho thời gian tính toán không tăng(Xét theo khía cạnh độ phức tạp). Nguyên lý hình ống Nguyên lý áp dụng khi bài toán xuất hiện một dãy các thao tác {T0 , T1 , . . . , Tn−1 }, trong đó Ti+1 được thực hiện sau khi Ti kết thúc. Nguyên lý chia để trị Chia bài toán thành những phần nhỏ hơn có dạng giống với bài toán ban đầu và giải quyết chúng một cách song song. 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 đồ thị phụ thuộc để xây dựng thuật toán song song. Nguyên lý điều kiện ganh đua 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 có thể cản trở lẫn nhau. Hai tiến trình ở trong trạng thái ganh đua nếu đầu ra của việc tính toán phụ thuộc hoàn toàn vào việc tiến trình nào truy cập dữ liệu chia sẻ trước nhất. Trên những kiến trúc máy tính khác nhau thì hiệu quả của thuật toán có thể rất khác nhau. Việc thiết kế thuật toán song song phải được 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. 18 Một số khái niệm Tác vụ (Task) là đơn vị do người dùng định nghĩa, trong đó việc tính toán chính được chia nhỏ bằng các kĩ thuật phân chia. Các tác vụ có thể được phân chia với cùng kích cỡ hoặc không cùng kích cỡ, có thể được sinh tĩnh, tức là các tác vụ được xác định trước khi thực hiện thuật toán, và sinh động ngược lại với sinh tĩnh, các tác vụ không được biết trước. Một tác vụ không thể chia nhỏ được nữa gọi là tác vụ nguyên tử. Tiến trình(process) là các tác nhân tính toán logic thực hiện các tác vụ. Thực hiện tuần tự là việc thực hiện chương trình một cách tuần tự trên máy một bộ xử lý, một câu lệnh tại một thời điểm. Thực hiện song song là việc thực hiện chương trình bằng nhiều hơn một tác vụ, mỗi tác vụ có thể được thực thi với cùng hoặc không cùng một câu lệnh tại cùng một thời điểm. Phương pháp luận để thiết kế thuật toán song song nhau như sau: gồm bốn giai đoạn khác 1. Sự chia nhỏ bài toán (partitioning): Sự tính toán và dữ liệu được chia thành các phần nhỏ. Ta không quan tâm tới có bao nhiêu bộ xử lý mà chỉ tập trung vào khả năng thực hiện song song của các phần nhỏ. 2. Thiết lập kênh truyền(communication): Thiết lập kênh truyền đòi hỏi tọa độ của các tác vụ thực hiện, cấu trúc kênh truyền và cấu trúc truyền thông điệp(đặc tả các thông điệp được gửi). Tối ưu hóa việc thực hiện bằng cách phân bố truyền thông trên nhiều tác vụ và thực hiện một cách đồng thời. 3. Nhóm gom các tác vụ(agglomeration): Ta đánh giá cấu trúc tác vụ và sự truyền thông ở các bước trên quan tâm tới việc thể hiện. Sau đó, xử lý độ hạt tác vụ và tối ưu hóa kênh truyền thông. 4. Gán vào hệ thống(mapping): Mỗi tác vụ được gán vào một bộ xử lý sao cho sử dụng hiệu quả các bộ xử lý và giảm truyền thông tới mức tối thiểu. Các cách tiếp cận trong thiết kế Có ba cách tiếp cận để thiết kế thuật toán song song: 1. Thực hiện song song hóa những thuật toán tuần tự, biến đổi những cấu trúc tuần tự để tận dụng được nhữ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ý. 2. Thiết kế những thuật toán song song mới phù hợp với kiến trúc song song. 19 Hình 1.11: Phương pháp luận thiết kế thuật toán song song 3. Thiết kế những thuật toán song song mới từ những thuật toán song song đã có sao cho phù hợp với cấu hình tôpô và môi trường song song trong thực tế. Trong các cách tiếp cận trên thì cách tiếp cận thông dụng là song song hóa các thuật toán tuần tự hoặc là chuyển một dạng song song về một dạng song song phù hợp hơn sao cho vẫn bảo toàn được tính tương đương trong tính toán. Trong thiết kế thuật toán song song, chúng ta cần trả lời được hai câu hỏi sau: ◦ Kiến trúc nào là phù hợp nhất với bài toán chúng ta đang giải quyết? ◦ Bài toán có thể đạt được hiệu quả gì trên một kiến trúc song song cho trước? 1.4.2. Đánh giá các thuật toán song song Để đánh giá được độ phức tạp của thuật toán song song chúng ta cần đánh giá số các bước tính và đánh giá thời gian truyền thông giữa các tiến trình. 20 Thời gian thực hiện song song Thời gian thực hiện song song, kí hiệu là t p gồm có hai phần thời gian thực hiện các phép tính, kí hiệu là tcomp và thời gian thực hiện truyền thông, kí hiệu là tcomm . Ta có, t p = tcomp + tcomm Thời gian tính toán tcomp được xác định giống như thuật toán tuần tự. Khi có nhiều tiến trình thực hiện đồng thời thì chỉ cần tính thời gian thực hiện của tiến trình phức tạp nhất (thực hiện lâu nhất). Trong việc phân tích thời gian tính toán, chúng ta luôn giả thiết rằng các bộ xử lý là giống nhau và thực hiện với một tốc độ giống nhau. Thời gian truyền thông tcomm phụ thuộc vào vào kích cỡ các thông điệp, cấu trúc kết nối mạng đường truyền và cách thức truyền tải thông điệp,v.v. Công thức ước lượng thời gian truyền thông được tính như sau: tcomm = tstartup + n ∗ tdata Trong đó, ◦ tstartup là thời gian cần thiết để gửi thông điệp không phải là dữ liệu. Nó bao gồm thời gian để đóng gói thông điệp ở nơi gửi và thời gian mở gói thông điệp ở nơi nhận. Để đơn giản chúng ta giả thiết thời gian này là hằng số. ◦ tdata là thời gian cần thiết chuyển một từ dữ liệu từ nơi gửi tới nơi nhận, được giả thiết là hằng số và n là số từ dữ liệu được trao đổi trong hệ thống. Độ phức tạp thời gian của thuật toán song song Độ phức tạp thời gian của việc thực hiện song song, t p , là tổng độ phức tạp của các phép toán và sự truyền thông. Ví dụ Giả sử cần thực hiện cộng n số trên hai máy tính, trong đó mỗi máy cộng n/2 số với nhau và tất cả các số đó được lưu ở máy thứ nhất. Máy thứ hai phải gửi kết quả của mình cho máy thứ nhất để cộng hai tổng thành phần với nhau. Bài toán có các bước sau: 1. Máy một gửi n/2 số cho máy hai. 2. Cả hai máy thực hiện cộng n/2 số một cách đồng thời. 3. Máy hai gửi kết quả tính được cho máy một. 4. Máy một cộng hai tổng thành phần để đưa ra kết quả cuối cùng. Thời gian tính toán (ở bước 2 và 4): tcomp = n/2 + 1 21 Thời gian truyền thông (ở bước 1 và 3): tcomm = (tstartup + n/2tdata ) + (tstartup + 1tdata ) = 2tstartup + (n/2 + 1)tdata Độ phức tạp tính toán là O(n). Độ phức tạp truyền thông là O(n). Vậy độ phức tạp thời gian của thuật toán nói trên là O(n) Tỉ số giữa thời gian tính toán và truyền thông Thường thì thời gian truyền thông rất đắt. Nếu sự tính toán và truyền thông có cùng độ phức tạp thì việc thực hiện khi tăng n sẽ không mang lại hiệu quả tốt hơn. Do vậy độ phức tạp thời gian của việc tính toán nên lớn hơn độ phức tạp thời gian truyền thông, khi đó việc tăng n sẽ cải thiện được rất nhiều việc thực hiện. Giả sử, một bài toán có độ phức tạp thời gian truyền thông là O(n), độ phức tạp thời gian tính toán là O(n2 ). Việc tăng n cuối cùng sẽ có một giá trị n mà tại đó thời gian tính toán lớn hơn rất nhiều so với thời gian thực thi. Thuật toán có chi phí tốt Một thuật toán có chi phí tốt nhất nếu chi phí để giải quyết bài toán tỉ lệ với thời gian thực hiện trên hệ thống một bộ xử lý đơn (sử dụng thuật toán tuần tự tốt nhất). Tức là, Cost = t p × n = k × ts trong đó, Cost là chi phí thực hiện, k là hằng số. Một thuật toán song song là thuật toán có chi phí tốt nhất nếu (độ phức tạp thời gian song song)×(số bộ xử lý)=(độ phức tạp thời gian tuần tự) Ví dụ Giả sử một thuật toán tuần tự tốt nhất để giải một bài toán có độ phức tạp thời gian là O(nlogn). Thì một thuật toán song song để giải bài toán trên sử dụng n bộ xử lý có độ phức tap thời gian là O(logn) là tốt nhất, trái lại nếu thuật toán đó sử dụng n2 bộ xử lý và có độ phức tạp thời gian là O(1) lại là thuật toán không có chi phí tốt nhất. Ngoài ra để đánh giá một thuật toán song song ta phải xét đến hệ số gia tốc của thuật toán. Hệ số gia tốc của thuật toán song song sử dụng p bộ xử lý được xác định như sau: S p = Ts /Tp trong đó, + Ts là thời gian thực hiện tính toán trên một bộ xử lý. + Tp là thời gian thực hiện trên p bộ xử lý. 22 1.5. Lập trình song song với MPI Lập trình song song cũng giống với lập trình tuần tự, có nhiều ngôn ngữ và công cụ lập trình song song khác nhau. Lập trình theo mô hình truyền thông điệp trong hệ thống máy tính có thể thực hiện theo 3 cách: 1. Sử dụng ngôn ngữ lập trình song song đặc biệt, ví dụ Occam được thiết kế để sử dụng với các Transputer (Inmos 1986). 2. Sử dụng ngôn ngữ lập trình bậc cao (tuần tự) truyền thống được mở rộng bằng cách bổ sung thêm các từ khóa và mở rộng một cú pháp để xử lý việc trao đổi thông điệp, gồm có CC+ (mở rộng từ C++)và Fortran M (mở rộng từ Fortran). 3. Sử dụng những ngôn ngữ lập trình bậc cao như là ngôn ngữ C và cung cấp một thư viện các thủ tục bên ngoài để thực hiện truyền thông điệp. Lập trình song song với MPI là lập trình theo mô hình truyền thông điệp trong hệ thống máy tính sử dụng cách tiếp cận thứ ba. 1.5.1. Giới thiệu về MPI(Message Passing Interface) Với mục đích xây dựng một thư viện truyền thông điệp chuẩn, MPI đã ra đời và hoàn thành lần đầu tiên vào tháng 6 năm 1994, MPI đã được chấp nhận và sử dụng rộng rãi trên các hệ thống phân cấp (Scalable Parallel Computers - SPCs) và các hệ thống máy trạm (Networks Of Workstations - NOWs). MPI không phải là một ngôn ngữ lập trình mới mà là một thư viện gồm các định nghĩa và các hàm được gọi vào từ chương trình C hoặc Fortran. Ưu điểm • Chuẩn MPI được thiết kế để phục vụ tất cả các đối tượng có nhu cầu lập trình song song sử dụng mô hình truyền thông điệp trên Fortran 77 hoặc C. Để đạt được mục đích ấy, chuẩn MPI cung cấp một giao diện đơn giản, dễ sử dụng cho đa số người dùng song vẫn đảm bảo hiệu năng cao trên các máy tính tiên tiến. • MPI phát triển một cách rộng rãi các tiêu chuẩn để viết các chương trình có sử dụng truyền thông điệp. Những tiêu chuẩn này phải đảm bảo yêu cầu cần thực hành hiệu quả và linh hoạt, bao gồm: – Thiết kế giao diện lập trình ứng dụng (không phải là thư viện bắt buộc để dịch và thực thi chương trình) 23 – Đảm bảo truyền thông hiệu quả, tránh sao chép bộ nhớ, đồng thời cho phép gối lên nhau giữa tính toán và truyền thông. – Cho phép thực thi trên một môi trường hỗn hợp. – Cho phép liên kết với các tiện ích của C và Fortran 77. – Cung cấp một giao diện truyền thông đáng tin cậy: người sử dụng không phải đối mặt với các lỗi truyền thông, các lỗi này sẽ được xử lý bởi các hệ thống con bên dưới. – Không khác quá nhiều so với các giao diện đã có như PVM, NX, Express, p4,..., song lại cung cấp các mở rộng linh hoạt hơn. – Có ngôn ngữ riêng. – Giao diện đảm bảo an toàn luồng. Với những ưu điểm của mình chuẩn MPI đang trở thành lựa chọn ưu tiên của các nhà lập trình song song trên mô hình truyền thông điệp. Hạn chế Chuẩn MPI không cung cấp: • Những thao tác phân tán bộ nhớ rõ ràng. • Những thao tác đòi hỏi nhiều hệ điều hành hỗ trợ hơn chuẩn hiện thời, ví dụ thao tác nhận tự ngắt, thực hiện từ xa hoặc những thông điệp hoạt động. • Lập trình các công cụ cấu trúc. • Các công cụ gỡ lỗi. • Hỗ trợ quản lý tác vụ. • Hỗ trợ luồng một cách rõ ràng. • Các hàm vào/ra (I/O) Những đặc tính trên luôn được xem xét như những mở rộng của chuẩn trong những thực thi xác định cụ thể và các phiên bản sau của MPI cố gắng tích hợp thêm nhiều tính năng mới. Hiện nay, MPI đã có phiên bản 2.0 với các ưu điểm nổi bật: • Cho phép sinh tiến trình động (số lượng tiến trình có thể thay đổi trong suốt quá trình thực thi chương trình). • Cho phép truyền thông một phía (tức là việc truyền thông được phát sinh và thực hiện ngay trong một bộ xử lý). • Mở rộng thêm các thao tác truyền thông tập hợp (cho phép truyền thông giữa các nhóm tiến trình với nhau, mỗi nhóm tạo thành một bộ truyền thông). • Mở rộng giao diện, hỗ trợ I/O, hỗ trợ C++ và Fortran 90,... 24 1.5.2. Các hàm cơ bản trong chuẩn MPI Trong mô hình lập trình MPI, việc tính toán bao gồm một hoặc nhiều tiến trình truyền thông với nhau bằng cách goi thư viện hàm để gửi và nhận thông điệp từ những tiến trình khác. Trong hầu hết các thể hiện MPI, một tập hợp cố định các tiến trình được tạo ra khi khởi tạo chương trình, và một tiến trình được tạo bởi một bộ xử lý. Hai phương thức chính cần thiết cho mô hình lập trình truyền thông điệp dạng này là: • Phương thức tạo các tiến trình riêng biệt để thực thi trên các máy tính khác nhau. • Phương thức gửi và nhận thông điệp. Việc tạo lập tiến trình Phiên bản 1 của MPI chỉ hỗ trợ việc tạo lập tiến trình tĩnh. Tức là, tất cả các tiến trình được xác định trước khi thực hiện và bắt đầu cùng với nhau. Phiên bản 2 của MPI đã hỗ trợ việc tạo lập tiến trình động nhưng nó thường không được sử dụng vì tổng phí của việc tạo lập tiến trình động. Trong mô hình lập trình MPI thường sử dụng mô hình tính toán SPMD. Trong hệ thống thường có một tiến trình chủ (master) điều khiển các tiến trình khác được gọi là tiến trình tớ (slave) Các tiến trình được đánh số từ 0 đến (p − 1) dùng để định danh các tiến trình, các số này gọi là hạng của tiến trình, p là số tiến trình được sử dụng. Số lượng các hàm trong MPI rất nhiều, tuy nhiên chúng ta có thể xây dựng chương trình dựa trên các hàm cơ bản sau: Các hàm quản lý môi trường • Hàm khởi tạo MPI int MPI_Init(Int∗ argc, char∗ argv) Ý nghĩa: hàm này dùng để khởi tạo môi trường truyền thông điệp MPI. Nó phải được gọi trước bất cứ hàm MPI nào. Tham số của nó là con trỏ trỏ tới các tham số của hàm main( ). • Hàm kết thúc MPI int MPI_Finalize(void) Ý nghĩa: đây là hàm đóng môi trường MPI. Sau lời gọi hàm này không còn lời gọi hàm MPI nào có hiệu lực. 25 Các hàm truyền thông điệp điểm-điểm • Hàm gửi thông điệp int MPI_Send(void ∗ buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm) Trong đó, – buf: địa chỉ bắt đầu của bộ đệm gửi – count: số các thành phần trong bộ đệm – datatype: kiểu dữ liệu của mỗi thành phần trong bộ đệm – dest: hạng của tiến trình nhận – tag: nhãn của thông điệp được gửi – comm: bộ truyền thông điệp, đó là tập hợp của các tiến trình mà các tiến trình có thể gửi và nhận thông điệp. Ý nghĩa: hàm này dùng để gửi thông điệp có nhãn là tag và chứa dữ liệu ở bộ đệm buf với số lượng count phần tử kiểu datatype tới tiến trình có số hiệu dest. Một thông điệp được gửi tới một tiến trình cụ thể và được đánh dấu bởi một nhãn (giá trị là số nguyên) do người sử dụng xác định. Các nhãn được dùng để phân biệt những kiểu thông điệp khác nhau mà một tiến trình gửi (hoặc nhận). Nhãn thông điệp có thể dùng MPI_ANY_TAG khi thông điệp được gửi (hoặc nhận) có thể ở bất kỳ định dạng nào. Tương tự, ta có thể dùng MPI_ANY_SOURCE để nhận thông điệp từ bất kỳ tiến trình nào. • Hàm nhận thông điệp int MPI_Recv(void ∗ buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Status status) Ý nghĩa: hàm này dùng để nhận thông điệp từ tiến trình có số hiệu source với nhãn là tag dữ liệu và lưu vào bộ đệm buf với số phần tử là count có kiểu dữ liệu datatype và trả lại thông tin về dữ liệu thật sự nhận được trong biến trạng thái status. status là kiểu dữ liệu có cấu trúc, chứa ít nhất 3 thành phần là số hiệu tiến trình gửi (source), nhãn (tag) và mã lỗi. Nhãn thông báo nhận được là status.MPI_TAG và hạng của tiến trình gửi là status.MPI_SOURCE. Khi số lượng phần tử nhận được có thể nhỏ hơn count, hàm sau đây có chức năng trả lại số lượng các phần tử nhận được MPI_Get_count(&status, datatype, &nelements). Các hàm truyền thông tập thể • Hàm quảng bá thông điệp (loan tin) int MPI_Bcast(void ∗ buf, int count, MPI_Datatype datatype, 26 Hình 1.12: Hàm giao tiếp tập thể của MPI int root, MPI_Comm comm) Trong đó, các tham số buf, count, datatype, comm tương tự như trong hàm MPI_Send. Tham biến root chính là hạng của tiến trình tiến hành loan tin. Ý nghĩa: hàm này dùng để gửi một nội dung buf từ tiến trình có hạng root tới tất cả các tiến trình trong bộ truyền thông. • Hàm tổng hợp dữ liệu int MPI_Gather(void ∗ sendbuf, int sendcount, MPI_Datatype sendtype, void ∗ recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_comm comm) Ý nghĩa: tiến trình có số hiệu root thu thập dữ liệu trong bộ đệm sendbuf từ tất cả các tiến trình trong bộ truyền thông và lưu vào trong bộ đệm recvbuf theo thứ tự hạng của các tiến trình. • Hàm phân phối dữ liệu MPI_Scatter(void ∗ sendbuf, int sendcount, MPI_Datatype 27 sendtype, void ∗ recvbuf, int recvcount, MPI_Datatype recvtype, MPI_comm comm) Ý nghĩa: tiến trình có số hiệu root phân phối dữ liệu từ sendbuf tới tất cả các tiến trình trong bộ truyền thông theo thứ tự hạng của tiến trình. • Hàm tổng hợp toàn bộ dữ liệu MPI_allGather(void ∗ sendbuf, int sendcount, MPI_Datatype sendtype, void ∗ recvbuf, int recvcount, MPI_Datatype recvtype, MPI_comm comm) Ý nghĩa: các tiến trình thu thập dữ liệu trong bộ đệm sendbuf từ tất cả các tiến trình trong bộ truyền thông và lưu vào trong bộ đệm recvbuf theo thứ tự hạng của tiến trình. Các hàm quản lý nhóm • Hàm lấy hạng của tiến trình int MPI_Comm_rank(MPI_Comm comm, int ∗ rank) Ý nghĩa: hàm này trả lại giá trị hạng của tiến trình trong bộ truyền thông đang gọi hàm. • Hàm lấy số tiến trình int MPI_Comm_size(MPI_Comm com, int ∗ size) Ý nghĩa: hàm này trả lại giá trị là số lượng các tiến trình trong bộ truyền thông com. Ví dụ về một chương trình MPI đơn giản Viết chương trình in ra tên máy và chỉ số rank của process MPI đang thực thi tên máy. #include< stdio.h > #include< mpi.h > int main(int argc, char∗ argv[]) { int length; char name[BUFSIZ]; MPI_Init(&argc, &argv); MPI_Get_processor_name(name, &length); printf("%s Hello world \n", name); MPI_Finalize(); } 28 Chương 2 Kĩ thuật phân hoạch, chia để trị và một số ứng dụng Phân hoạch(partitioning) và chia để trị(divide-and-conquer) là hai kỹ thuật cơ bản để xây dựng một chương trình song song. Hai kĩ thuật này có liên quan tới nhau. Trong kĩ thuật phân hoạch, bài toán được chia thành các phần riêng lẻ và mỗi phần được tính toán riêng. Kĩ thuật chia để trị thường áp dụng kĩ thuật phân hoạch trong phép đệ quy để chia liên tục bài toán thành các phần nhỏ hơn trước khi giải quyết các phần nhỏ hơn và hợp các kết quả lại. 2.1. Các chiến lược phân hoạch, chia để trị 2.1.1. Kĩ thuật phân hoạch Phân hoạch đơn giản là chia bài toán thành các phần nhỏ. Tuy nhiên, các công thức phân hoạch đều yêu cầu kết quả của các phần nhỏ hợp lại để đạt được kết quả mong muốn. Kĩ thuật phân hoạch có thể được áp dụng trong dữ liệu của chương trình, tức là chia nhỏ dữ liệu và thao tác trên các dữ liệu đã chia một cách đồng thời. Việc này được gọi là chia nhỏ dữ liệu(data partitioning) hay sự phân nhỏ miền(domain decomposition). Kĩ thuật phân hoạch cũng có thể được áp dụng trong các chức năng của chương trình, tức là chia bài toán thành các chức năng độc lập và thực hiện các chức năng một cách đồng thời. Việc này được gọi là phân nhỏ chức năng(functional decomposition) 29 Chia nhỏ dữ liệu Chia nhỏ dữ liệu là một phương pháp được dùng phổ biến và rộng rãi trong viêc tạo sự thực hiện cùng nhau trong một thuật toán thao tác trên một cấu trúc dữ liệu lớn. Ta chia dữ liệu thành các phần nhỏ, nếu được cố gắng chia thành các phần bằng nhau. • Dữ liệu của bài toán có thể chia nhỏ theo nhiều cách khác nhau: theo các khối 1-chiều, 2-chiều hoặc 3-chiều. • Dữ liệu chia nhỏ có thể là dữ liệu đầu vào, đầu ra, hoặc dữ liệu trung gian của bài toán: – Chia nhỏ dữ liệu đầu ra: áp dụng cho các bài toán mà dữ liệu ra(kết quả) có thể được tính độc lập với nhau theo một hàm đầu vào. – Chia nhỏ dữ liệu vào: Mỗi tác vụ được tạo ra cho một phần dữ liệu vào và thực hiện các phép toán có thể trên dữ liệu cục bộ này. Khi kết quả của mỗi tác vụ không phải là kết quả cuối cùng của bài toán thì ta cần kết hợp lại. – Một bài toán có thể được giải quyết bằng nhiều bước và dữ liệu vào của bước này có thể là dữ liệu ra của bước tính trước đó. Việc chia nhỏ dữ liệu có thể được thực hiện ở bước trung gian. Ví dụ: Sự phân chia miền xác định của một bài toán đơn giản liên quan tới lưới điểm 3-chiều. Việc tính toán được thực hiện bằng cách lặp lại trên mỗi điểm lưới. Trong mỗi trường hợp dữ liệu được liên quan tới một tác vụ đơn thì bôi đen. Hình 2.1: Các cách chia miền xác định của một bài toán liên quan tới lưới điểm 3-chiều. 30 Hình 2.2: Chia nhỏ theo chức năng Chia nhỏ theo chức năng Chia nhỏ theo chức năng ta tập trung vào việc tính toán hơn là dữ liệu đòi hỏi tính toán, nếu được thì cố gắng chia thành các tác vụ không giao nhau. Chia nhỏ bài toán theo chức năng thường được áp dụng cho những bài toán phức tạp mà nó là tập hợp những mô hình nối nhau về mặt hình thức. Có nhiều cách để chia nhỏ một bài toán, vì vậy ta cần khảo sát tất cả các cách chia có thể để có thể đưa ra cách phân chia tốt. Ta cũng có thể sử dụng kết hợp cả hai cách chia trên để có thể có cách chia nhỏ tốt hơn. Ví dụ: Khí hậu trái đất bao gồm mô hính khí quyển, biển, thủy học, bề mặt trái đất. Ta có thể mô phỏng khí hậu trái đất trong mô hình máy tính sử dụng phân chia miền theo chức năng. Mỗi thành phần mô hình có thể coi như là một tác vụ tách biệt và có thể song song hóa theo cách phân chia dữ liệu. Việc tìm ra các chức năng có thể thực hiện đồng thời trong một bài toán ít phổ biến hơn, nhưng chia nhỏ dữ liệu lại là chiến lược chính trong việc lập trình song song. Kĩ thuật chia nhỏ bài toán được áp dụng trực tiếp và hiệu quả(không phải là tối ưu) với các bài toán tính toán song song lý tưởng, tức là bài toán được chia thành các phần nhỏ hoàn toàn độc lập và có thể được thực hiện một cách đồng thời mà không yêu cầu sự truyền thông của các tiến trình riêng biệt, hoặc với các bài toán mà ở đó sự tương tác giữa các tiến trình tớ là nhỏ nhất. Với các bài toán yêu cầu sự giao tiếp của các tiến trình thì việc áp dụng trực tiếp kĩ thuật chia nhỏ không mang lại hiệu quả. Ví dụ: Tính tổng của một dãy số gồm n phần tử x0 , x1 , ..., x( n − 1). Thời gian thực hiện tuần tự của bài toán là O(n). Chúng ta thực hiện tính toán song song áp dụng kĩ thuật phân hoạch đơn giản bằng cách chia dãy thành m phần, mỗi phần có n/m phần tử, (x0 , . . . , xn/m−1 ), (xn /m, . . . , x2n/m−1 ), ..., (x(m−1)n/m , . . . , xn−1 ) và sử dụng m bộ xử lý (hoặc m) tiến trình để cộng các số của mỗi phần để tạo ra các 31 Hình 2.3: Phân chia theo chức năng trong một mô hình tính toán của khí hậu tổng thành phần. Cuối cùng m tổng thành phần này cần được cộng lại để đưa ra tổng của dãy.(Hình...) Thời gian thực hiện song song của bài toán trên, t p = O(n + m). Hình 2.4: Chia nhỏ một dãy các số thành nhiều phần và tính tổng các phần Thời gian thực hiện song song tồi hơn so với thuật toán tuần tự. 2.1.2. Chia để trị Cách tiếp cận chia để trị(divide-and-conquer) được đặc trưng bằng việc chia một bài toán thành các bài toán nhỏ hơn có cùng dạng với bài toán lớn sử dụng phương pháp đệ quy. Phương pháp đệ quy sẽ tiếp tục chia bài toán thành các tác vụ nhỏ hơn cho tới khi các tác vụ không thể nhỏ hơn được nữa. Sau đó các tác vụ đơn giản nhất được thực hiện và nối các kết quả với nhau để thực các tác vụ lớn hơn, cho 32 đến khi thu được kết quả cuối cùng. JaJa(1992) đã phân biệt giữa phương pháp chia để trị và phân hoạch dựa vào công việc chính của mỗi phương pháp. Ông gọi là phương pháp chia để trị khi công việc chính là việc tổng hợp các kết quả, và gọi là phân hoạch khi công việc chính là chia nhỏ bài toán. Ở đây, chúng ta sẽ sử dụng thuật ngữ chia để trị bất cứ khi nào việc chia nhỏ còn được tiếp tục trên các bài toán nhỏ hơn. Ví dụ Tính tổng S của dãy gồm n số: S = ∑n−1 i=0 xi . Một định nghĩa đệ quy để cộng danh sách số(s) gồm n phần tử được thể hiện như sau: Int add(int ∗ s) { if (number(s) =< 2) return (n1+n2); else { divide(s, s1, s2); /∗ Chia s thành 2 phần s1, s2 ∗ / part_sum1 = add(s1); /∗ Các lời gọi đệ quy để cộng các danh sách con∗ / part_sum2 = add(s2); return (part_sum1+part_sum2); } } Trong tất cả các định nghĩa đệ quy, một phương thức phải kết thúc được lời gọi đệ quy khi việc chia nhỏ không thể thực hiện được nữa. Trong mã lệnh trên, number(s) trả lại số các số trong danh sách s. Nếu có 2 số trong danh sách, hai số đó được gọi là n1 và n2. Nếu có 1 số trong danh sách thì số đó được gọi là n1, n2=0. Nếu không có số nào trong danh sách, thì n1=n2=0. Lời gọi đệ quy trong mã lệnh trên sẽ kết thúc trong các trường hợp có 0, 1 hoặc 2 số trong danh sách. Khi mỗi phép chia tạo thành 2 phần, thì kĩ thuật chia để trị đệ quy sẽ có dạng một cây nhi phân hoàn chỉnh. Với các thể hiện tuần tự, tại mỗi thời điểm ta chỉ thăm được một node của cây. Nhưng với thể hiện song song, tại một thời điểm ta có thể thăm nhiều node của cây một cách đồng thời bằng cách thực hiện như sau: • Thực hiện việc chia dữ liệu trong bài toán tính tổng dãy số x0 , x1 , . . . , xn−1 , và sử dụng 8 bộ xử lý P0 , P1 , . . . , P8 . Tại mỗi giai đoạn, mỗi bộ xử lý sẽ giữ một nửa danh sách và gửi nửa còn lại cho bộ xử lý khác. Đầu tiên, P0 giao tiếp với P4 , gửi một nửa dữ liệu tới P4 . Sau đó, P0 và P4 lại gửi một nửa dữ liệu của mình cho P2 và P6 một cách tương tự. Cuối cùng, P0 , P2 , P4 và P6 gửi một nửa dữ liệu của mình cho P1 , P3 , P5 và P7 một cách tương tự. Mỗi danh sách trong giai đoạn cuối sẽ có n/8 số hoặc n/p số trong trường hợp sử dụng p bộ xử lý. • Việc liên kết để tính tổng của các tổng thành phần có thể được thực hiện như 33 Hình 2.5: Chia nhỏ một danh sách thành các phần hình...Khi các tổng thành phần đã được tính, mỗi tiến trình được đánh số lẻ sẽ gửi kết quả của mình cho các tiến trình được đánh số chẵn liền kề nó. Đó là, P1 gửi kết quả của mình tới P0 , P3 gửi tới P2 , P5 gửi tới P4 , và P7 gửi tới P6 . Các bộ xử lý được đánh số chẵn sau đó sẽ cộng kết quả nhận được với tổng thành phần của mình và gửi kết quả lên trên. Quá trình tiếp tục cho tới khi P0 có được kết quả cuối cùng. Hình 2.6: Tính tổng thành phần 34 Phân tích thuật toán Giả thiết n là lũy thừa của 2, và sử dụng p bộ xử lý. Thời gian thiết lập truyền thông tstartup không được tính trong các bước. • Thời gian truyền thông – Trong giai đoạn chia nhỏ, ta phải thực hiện log p bước chia. Thời gian truyền thông của giai đoạn này là n n n n(p − 1) tcomm1 = tdata + tdata + · · · + tdata = tdata 2 4 p p trong đó, tdata là thời gian để chuyển một từ dữ liệu. – Trong giai đoạn hợp kết quả, thời gian truyền thông được tính tương tự nhưng mỗi thông điệp chỉ chứa một dữ liệu. tcomm2 = tdata log p Vậy tổng thời gian truyền thông của thuật toán là: tcomm = tcomm1 + tcomm1 = n(n − p) tdata + tdata log p n hay độ phức tạp thời gian là O(n) với p là hằng số. • Thời gian tính toán Khi kết thúc giai đoạn chia nhỏ, việc tính tổng của n/p số được thực hiện ở mỗi bộ xử lý. Và trong giai đoạn hợp kết quả mỗi bước chỉ thực hiện một phép cộng. Thời gian tính toán của thuật toán: tcomp = n + logp p hay độ phức tạp thời gian là O(n) khi p là hằng số. Với n lớn và p là biến thì ta sẽ lấy độ phức tạp thời gian là O(n/p). Tổng thời gian thực hiện song song của thuật toán là tp = 2.1.3. n(n − p) n tdata + tdata log p + + log p p p Chia để trị m-nhánh Kĩ thuật chia để trị cũng có thể được áp dụng vào các bài toán mà khi một tác vụ được chia nhỏ thành nhiều hơn hai phần ở mỗi bước. Ví dụ một tác vụ được chia nhỏ thành bốn phần, định nghĩa đệ quy tuần tự có thể là 35 Int add(int ∗ s) { if (number(s) =< 4) return (n1 + n2 + n3 + n4); else { divide(s, s1, s2, s3, s4); /∗ Chia s thành 2 phần s1, s2, s3, s4 ∗ / part_sum1 = add(s1); /∗ Các lời gọi đệ quy để cộng các danh sách con∗ / part_sum2 = add(s2); part_sum3 = add(s3); part_sum4 = add(s4); return (part_sum1+part_sum2+part_sum3+part_sum4); } } Cây m-nhánh được hình thành nếu phép chia là phép chia nhỏ thành m phần. Cây Hình 2.7: Quadtree và ứng dụng để chia miền 2-chiều m-nhánh có những ứng dụng cụ thể riêng. Trong cây mỗi node cha có bốn node con, gọi là quadtree được ứng dụng để chia các miền 2−chiều thành bốn miền con (Hình...); octree là cây trong đó mỗi node cha có tám node con được ứng dụng trong việc chia không gian 3−chiều đệ quy (Hình...). Thuật toán xây dựng cây quadtree(octtree được làm tương tự). Procedure Quad_Tree_Build Quad_Tree = empty for j = 1 to N . . . vòng lặp với tất cả N hạt Quad_Tree_Insert(j, root) . . . chèn hạt i vào QuadTree endfor . . . Tại điểm này, mỗi lá của Quad_Tree sẽ có 0 hoặc 1 hạt 36 Hình 2.8: Octree và ứng dụng để chia không gian 3-chiều . . . có 0 hạt nếu các node chị em ruột có 1 hạt Duyệt cây Quad_Tree xóa bỏ các lá rỗng . . . sử dụng, Breadth First Search Procedure Quad_Tree_Insert(j, n) . . . Chèn hạt thứ j vào node thứ n trong cây Quad_Tree if n là node trong . . . n có 4 node con xác định node con c của node n chứa hạt j Quad_Tree_Insert(j, c) else if n chứa 1 hạt . . . n là node lá thêm 4 node con của n vào the Quad_Tree chuyển hạt trong n tới node con chứa nó đặt c là node con của n chứa j Quad_Tree_Insert(j, c) else . . . n rỗng lưu hạt j ở node n end 2.2. Một số ứng dụng trong thuật toán song song 2.2.1. Nhân ma trận với vecto Trong phần này chúng ta sẽ ứng dụng kĩ thuật chia nhỏ dữ liệu để thiết kế thuật toán song song cho bài toán nhân ma trận vuông dày A cỡ n × n với vecto x cỡ n × 1, cho ra kết quả là vecto y. 37 Thuật toán tuần tự thông thường để nhân một ma trận với vecto: MAT_VECT(A, x, y){ for(i = 0; i < n; i + +){ y[i] = 0; for( j = 0; j < n − 1; j + +) do y[i] = y[i] + A[i, j] ∗ x[ j]; } } Độ phức tạp của thuật toán là O(n2 ). Chia nhỏ dữ liệu đầu vào theo khối 1-chiều Trong phần này trình bày thuật toán song song cho phép nhân ma trận với vecto sử dụng kĩ thuật chia nhỏ dữ liệu theo khối 1-chiều. Ta chia nhỏ ma trận A và vecto x thành các khối theo hàng. Hình 2.9: Phép nhân ma trận cỡ n × n với vecto n sử dụng kĩ thuật chia nhỏ thành các khối theo hàng trong trường hợp p = n 38 Gán mỗi hàng cho một tiến trình Trong trường hợp này, ma trận A được chia nhỏ cho p (p = n) tiến trình và một phần tử của vecto x. Tiến trình Pi sở hữu hàng A[i] và phần tử x[i] sẽ tính y[i]. Để tính y[i], tiến trình Pi cần toàn bộ vecto x nên thuật toán gồm hai bước sau: 1. Mỗi tiến trình bắt đầu chỉ có một phần tử của x, sử dụng hàm loan tin all-to-all để phân bố phần tử đó đến tất cả các tiến trình còn lại. 2. Tiến trình Pi tính y[i] = ∑n−1 j=0 (A[i, j] ∗ x[ j]). Thời gian thực hiện song song tcomm : Là toàn bộ bước 1, có tcomm = O(n) tcomp : Là thời gian thực hiện bước 2, có tcomp = O(n) Vậy độ phức tạp thời gian của thuật toán khi sử dụng n tiến trình là O(n). Sử dụng p tiến trình, p < n Mỗi tiến trình sẽ chứa n/p hàng của ma trận A, và một phần của vecto x cỡ n/p. Tương tự như trong phần trên, trong bước 1 ta sử dụng hàm loan tin all-to-all tới p tiến trình và mỗi thông điệp bao gồm n/p dữ liệu, tcomm = tstartup log b + (p − 1)(n/p)tdata , với p lớn ta có thể xấp xỉ bằng tstartup log p + ntdata . Trong bước 2, cần thực hiện tính n/p hàng của ma trận A lần lượt với vecto x tương ứng, yêu cầu n2 /p thời gian. Vậy tổng thời gian thực hiện song song khi sử dụng p tiến trình là t p = n2 /p + tstartup log b + (p − 1)(n/p)tdata Chia nhỏ thành các khối 2-chiều Trong phần này ta nghiên cứu thuật toán nhân ma trận với vecto bằng việc chia nhỏ ma trận thành các khối 2-chiều và gán vào cho các tiến trình. Hình 2.10 miêu tả thuật toán song song. Gán mỗi phần tử cho một tiến trình Ma trận được chia nhỏ thành n2 khối, ta sử dụng n2 tiến trình để gán mỗi phần từ cho một tiến trình, mỗi phần tử của vecto x được lưu ở n tiến trình ở cột cuối cùng của . Thuật toán song song được thực hiện theo 4 bước sau: 1. Các phần tử vecto chứa trong n tiến trình nằm ở cột cuối cùng được phân phối tới tiến trình trong cùng hàng nằm trên đường chéo chính sử dụng hàm loan tin one-to-one. Thời gian yêu cầu là O(log n)). 39 Hình 2.10: Phép nhân ma trận-vecto sử dụng chia nhỏ thành khối 2-chiều 2. Các tiến trình nằm trên đường chéo chính sử dụng hàm loan tin one-to-all để phân phối phần tử của x trong tới tất cả các tiến trình còn lại trong cùng một cột một cách đồng thời. Thời gian yêu cầu là O(log n). 3. Mỗi tiến trình Pi, j thực hiện phép nhân phần tử A[i, j] với x[ j] tương ứng một cách đồng thời. Thời gian yêu cầu là O(1). 4. Sử dụng hàm gộp all-to-one để tính tổng của mỗi hàng, địa chỉ đến là tiến trình nằm ở cột cuối cùng. Thời gian yêu cầu là O(log n). Vậy, tổng thời gian thực hiện song song của thuật toán t p = O(log n) Nhưng chi phí để thực hiện Cost = O(n2 log n) đây không phải là thuật toán có chi phí tốt nhất. 40 Sử dụng ít hơn n2 tiến trình √ √ Ta chia ma trận thành p khối, mỗi khối cỡ n/( p) × n/( p). Giả sử, ta sử dụng một mảng lưới hai chiều gồm p tiến trình để lưu mỗi khối của ma trận. Vecto x được √ √ chia nhỏ thành p phần, mỗi phần gồm n/( p) phần tử và được lưu tại tiến trình √ của cột cuối cùng( p − 1). Thuật toán được thực hiện như sau: 1. Gán các phần của vecto dọc theo đường chéo chính. Để làm việc này, mỗi √ tiến trình nằm trên cột bên phải nhất của lưới 2-chiều gửi n/( p) của mình tới một tiến trình trong cùng hàng nằm trên đường chéo chính. Thời gian yêu √ cầu trong bước này là tstartup + (n/( p))tdata . 2. Mỗi tiến trình trên đường chéo chính sử dụng hàm loan tin one-to-all theo √ cột để phân phối n/( p) phần tử vecto. Thời gian yêu cầu là (tstartup + √ √ (n/( p))) log p. 3. Mỗi tiến trình thực hiện n2 /p phép nhân để tính tại khối và cộng cục bộ √ √ n/( p) phân tử với nhau. Kết thúc bước này mỗi tiến trình sẽ có n/( p) tổng thành phần. √ 4. Cộng gộp n/( p) giá trị của mỗi hàng lại sử dụng hàm gộp all-to-one, địa chỉ đến là cột bên phải nhất của lưới. Thời gian yêu cầu (bỏ qua thời gian thực √ √ hiện phép cộng) là (tstartup + (n/( p))) log p. Thời gian thực hiện song song của thuật toán: √ √ √ t p = n2 /p + tstartup + (n/( p))tdata + 2(tstartup + (n/( p))) log p √ ≈ n2 /p + tstartup log p + log pn/( p)tdata 2.2.2. Thuật toán sắp xếp Sắp xếp theo giỏ(Bucket sort) Các thuật toán sắp xếp đã được nghiên cứu nhiều trong lập trình tuần tự. Hầu hết các thuật toán sắp xếp tuần tự đều dựa trên cơ sở so sánh và đổi chỗ các cặp số. Phần này chúng ta sẽ sử dụng kĩ thuật phân hoạch và chia để trị để song song hóa thuật toán sắp xếp theo giỏ(bucket sort). Thuật toán bucket sort không dựa trên cơ sở so sánh và đổi chỗ, thuật toán là một phép phân hoạch một cách tự nhiên. Thuật toán bucket sort chỉ có hiệu quả khi các số ban đầu có phân bố đều trên một khoảng cho trước, giả sử từ 0 đến a − 1. Khoảng cho trước sẽ được chia thành m khoảng nhỏ, 0 tới a/m − 1, a/m tới 2a/m − 1,. . ., và mỗi giỏ được gán để chứa các số trong khoảng đó, vậy cần có m giỏ. 41 thuật toán tuần tự • Đặt các số vào các khoảng phù hợp: Để đặt một số vào khoảng thích hợp, ta có thể so sánh số đó với các các số a/m, 2a/m, 3a/m, . . ., sẽ cần nhiều m − 1 bước so sánh để đặt được một số vào dãy thích hợp. Hoặc ta có thể chia số đó cho m, sử dụng kết quả để đặt vào các giỏ tương ứng từ 0 đến m − 1. Nếu m là lũy thừa của 2 ta có thể sử dụng các bit trên đầu của mỗi số dưới dạng nhị phân. Trong bất kì cách nào, ta giả sử để đặt một số vào giỏ cần 1 bước. Vậy để đặt tất cả các số cần n bước. Hình 2.11: Sắp xếp theo giỏ • Các số trong mỗi giỏ sẽ được sắp xếp bởi một thuật toán sắp xếp tuần tự: Giả sử thuật toán sắp xếp tuần tự sử dụng để sắp ở mỗi giỏ đòi hỏi n log n phép so sánh, mỗi phép so sánh tương đương với một bước tính toán. Vậy để sắp xếp n/m số ở mỗi giỏ cần (n/m) log (n/m) bước. • Nối các số trong giỏ đã sắp để đưa ra dãy đã sắp cuối cùng: không sử dụng tính toán. Vậy thời gian xử lý tuần tự là ts = n + m((n/m) log (n/m)) = n + n log (n/m) = O(n log (n/m)) Nếu n = km, k là hằng số thì độ phức tạp thời gian là O(n). Thuật toán song song Một cách đơn giản thuật toán bucket sort có thể được song song bằng cách gán mỗi bộ xử lý cho một giỏ. Khi đó, thời gian sắp xếp ở mỗi giỏ sẽ là (n/p) log n/p với p bộ xử lý (trong đó p = m). 42 Ta có thể cải thiện thuật toán song song trên để đạt hiệu quả hơn bằng cách phân hoạch dãy số thành m miền, và mỗi miền ứng với một bộ xử lý. Mỗi bộ xử lý giữ p giỏ nhỏ và tách các số trong miền của nó vào từng rỏ riêng của mình. Sau đó các giỏ nhỏ này sẽ được "trút" vào p giỏ cuối cùng để sắp xếp, việc này yêu cầu mỗi bộ xử lý gửi một giỏ nhỏ tới mỗi bộ xử lý khác(giỏ thứ i tới bộ xử lý thứ i). Hình 2.12: Thuật toán bucket sort song song Phân tích Thuật toán gồm 4 giai đoạn sau đây: 1. Phân các số vào p miền. Giả sử cần n bước tính toán để phân n số vào p miền. tcomp1 = n Sau khi chia nhỏ, p phần nhỏ mỗi phần chứa n/p số được gửi tới các tiến trình. tcomm1 = tstartup + tdata n 2. Sắp xếp trong các giỏ nhỏ. Chia mỗi phần của n/p số vào p giỏ nhỏ yêu cầu thời gian là tcomp2 = n/p 3. Gửi tới các giỏ lớn. Các giỏ nhỏ được phân tán. Mỗi giỏ nhỏ có khoảng n/p2 số (giả thiết là phân 43 bố đều). Mỗi tiến trình phải gửi (p − 1) giỏ nhỏ tới các tiến trình khác. Cả p tiến trình phải thực hiện phép truyền thông này, ta có tcomm3 = p(p − 1)(tstartup + (n/p2 )tdata ) nếu các phép truyền thông này không thể gối nhau về thời gian và sử dụng các hàm gửi riêng . Nếu tất cả phép truyền thông được gối đầu nhau, có tcomm3 = (p − 1)(tstartup + (n/p2 )tdata ) 4. Sắp xếp trong giỏ lớn. Trong giai đoạn này, các giỏ lớn được sắp đồng thời, do đó tcomp4 = (n/p) log (n/p) Vậy tổng thời gian thực hiện là t p = tstartup + tdata n + (p − 1)(tstartup + (n/p2 )tdata ) + (n/p) log (n/p) Công thức trên đạt được khi các số được phân bố đều. Nếu các số không có phân bố đều thì số các số trong mỗi giỏ sẽ khác nhau, điều này sẽ làm tăng tổng thời gian tính toán. Trường hợp tồi nhất của bài toán là khi tất cả các số cùng nằm trong một giỏ. Thuật toán bucket sort có thể được phát triển theo phương pháp chia để trị bằng cách chia liên tục các giỏ cho tới khi mỗi giỏ chỉ chứa một phần tử của dãy. Phương pháp này tương tự như thuật toán quick sort(sắp xếp nhanh), chỉ khác là trong quick sort sử dụng một phần tử để chia đôi miền. Sắp xếp nhanh(Quick sort) Quick sort là một thuật toán sắp xếp tuần tự nổi tiếng dựa trên phương pháp chia để trị. Độ phức tạp thời gian trung bình của thuật toán là O(n log n).Ý tưởng của thuật toán là chia đôi dãy cần sắp thành hai dãy con rời nhau sao cho chỉ cần sắp xếp trên các dãy con. Để làm được điều này ta cần chọn một phần tử hoa tiêu(pivot), so sánh các số trong dãy với phân tử này, các phần từ nhỏ hơn và phần tử chốt được đặt vào một danh sách con, phần còn lại vào một danh sách con khác. Quá trình này lặp lại cho tới khi những danh sách cuối cùng chỉ còn một phần tử. Thuật toán tuần tự Thường được miêu tả bằng một thủ tục đệ quy. Giả sử, cần sắp xếp một mảng list[ ] chứa các số, pivot là chỉ số của phần tử trong mảng được chọn làm hoa tiêu. Quicksort(list, start, end){ if(start #include< mpi.h > void sort(int ar[], int size) { int temp; int i,j; for (i=size−1; i >=1; i−−) for (j=0; j < i; j++) if (ar[j] > ar[j+1]) { temp = ar[j]; ar[j]= ar[j+1]; ar[j+1] = temp; } } int main(int argc, char ∗ argv[]) { int rank,p; int a,b; int n; int ∗ array,∗ local; 54 int ∗ counters, ∗ displs; int start, end, slice; int count,disp,i; MPI_Status status; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&p); MPI_Comm_rank(MPI_COMM_WORLD, &rank); // initialize random number generation srand(time(NULL)); if (rank==0) { printf("How big should the array be ? "); scanf("%d", &n); array = (int ∗ )malloc(sizeof(int)∗ n); printf("What is the value of a (size of the range): "); scanf("%d", &a); // fill the array with random numbers for (i=0; i < n; i++) { array[i] = rand() % a; printf(" %d ", array[i]); } printf("\n"); } // send array, a, and n MPI_Bcast(&n,1,MPI_INT, 0, MPI_COMM_WORLD); MPI_Bcast(&a,1,MPI_INT, 0, MPI_COMM_WORLD); if (rank != 0) array = (int ∗ )malloc(sizeof(int)∗ n); MPI_Bcast(array, n, MPI_INT, 0, MPI_COMM_WORLD); slice = a / p; start = rank ∗ slice; end = (rank ==p−1) ? a : start+slice; count = 0; local = (int ∗ )malloc(sizeof(int)∗ n); // create the local bucket for (i=0; i = start) local[count++] = array[i]; // local sort the bucket 55 sort(local,count); // Need to compute the displacements MPI_Scan(&count,&disp,1,MPI_INT,MPI_SUM,MPI_COMM_WORLD); // Let master Gather the counts and the displacements if (rank == 0) counters = (int ∗ )malloc(sizeof(int)∗ p); MPI_Gather(&count,1,MPI_INT, counters, 1, MPI_INT, 0, MPI_COMM_WORLD // Let master Gather the displacements if (rank == 0) { displs = (int ∗ )malloc(sizeof(int)∗ (p+1)); displs[0]=0; } MPI_Gather(&disp,1, MPI_INT, displs+1, 1, MPI_INT, 0, MPI_COMM_WORLD // gather the sorted buckets MPI_Gatherv(local, count, MPI_INT, array, counters, displs, MPI_INT, 0, MPI_COMM_WORLD); if (rank == 0) { printf("Sorted: "); for (i=0; i < n ; i++) printf(" %d ", array[i]); printf("\n"); } MPI_Finalize(); } 2. Thực hiện song song thuật toán bucket sort bằng cách chia nhỏ dãy thành m miền con, mỗi miền ứng với một bộ xử lý và mỗi bộ xử lý chứa các giỏ nhỏ hơn. Chương trình bao gồm 6 bước thực hiện như sau: • • • • • • Sinh mảng A ngẫu nhiên Phân phối A tới mỗi node Sinh các giỏ con tại mỗi nodes Sắp xếp tại mỗi giỏ trên mỗi nodes Phân phối các giỏ nhỏ tới các node phù hợp Trộn kết quả tại node gốc #include< stdio.h > #include< mpi.h > #include< stdlib.h > 56 #define root 0 #define MCW MPI_COMM_WORLD #define NODES 4 #define MATSIZE NODES∗ 10 int main(int argc, char ∗ argv[]) { int rank, size, x, y, z, tmp; int mat1[MATSIZE] = {0}; int bigbucket[MATSIZE] = {0}; int bucket[NODES][MATSIZE/NODES] = {{0}}; int mat2[MATSIZE∗ NODES] = {0}; int part[MATSIZE/NODES] = {0}; MPI_Init(&argc, &argv); MPI_Comm_rank(MCW, &rank); MPI_Comm_size(MCW, &size); if (size != NODES) { printf("Please only use 4 nodes or else modify NODES parameter\n"); MPI_Abort(MCW, -1); } if (rank == root) { for (x= 0; x bucket[x][z]) { tmp = bucket[x][y]; bucket[x][y]=bucket[x][z]; bucket[x][z] = tmp; } } } } MPI_Alltoall(bucket, MATSIZE/NODES, MPI_INT, bigbucket, MATSIZE/NODES, MPI_INT, MCW); printf("%d>Printing unsorted Big Buckets\n", rank); for (x =0; x < MATSIZE; x++) { printf("%d>Bucket[%d]=%d\n", rank, x, bigbucket[x]); } //Sorting Big Buckets internally for (y = 0; y < MATSIZE ; y++ ) { for (z = y+1; z < MATSIZE; z++ ) { if (bigbucket[y]> bigbucket[z]) { tmp = bigbucket[y]; bigbucket[y] = bigbucket[z]; bigbucket[z] = tmp; } } } printf("%d>Printing SORTED Big Buckets\n", rank); for (x = 0; x [...]... 2 Kĩ thuật phân hoạch, chia để trị và một số ứng dụng Phân hoạch( partitioning) và chia để trị( divide-and-conquer) là hai kỹ thuật cơ bản để xây dựng một chương trình song song Hai kĩ thuật này có liên quan tới nhau Trong kĩ thuật phân hoạch, bài toán được chia thành các phần riêng lẻ và mỗi phần được tính toán riêng Kĩ thuật chia để trị thường áp dụng kĩ thuật phân hoạch trong phép đệ quy để chia liên... những thuật toán song song mới từ những thuật toán song song đã có sao cho phù hợp với cấu hình tôpô và môi trường song song trong thực tế Trong các cách tiếp cận trên thì cách tiếp cận thông dụng là song song hóa các thuật toán tuần tự hoặc là chuyển một dạng song song về một dạng song song phù hợp hơn sao cho vẫn bảo toàn được tính tương đương trong tính toán Trong thiết kế thuật toán song song,... cách tiếp cận trong thiết kế Có ba cách tiếp cận để thiết kế thuật toán song song: 1 Thực hiện song song hóa những thuật toán tuần tự, biến đổi những cấu trúc tuần tự để tận dụng được nhữ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ý 2 Thiết kế những thuật toán song song mới phù hợp với kiến trúc song song 19 Hình 1.11: Phương pháp luận thiết kế thuật toán song song 3 Thiết... trình song song thường dùng khác như song song dữ liệu, Hybrid, SPMD, MPMD 1.4 Thuật toán song song 1.4.1 Nguyên lý thiết kế thuật toán song song Phát triển thuật toán là một phần cơ bản của việc giải quyết bài toán sử dụng máy tính Một thuật toán tuần tự về bản chất là một cách làm hay một số tuần tự các bước để giải quyết bài toán đưa ra bằng một máy tính tuần tự Một cách tương tự, một thuật toán song. .. chia liên tục bài toán thành các phần nhỏ hơn trước khi giải quyết các phần nhỏ hơn và hợp các kết quả lại 2.1 Các chiến lược phân hoạch, chia để trị 2.1.1 Kĩ thuật phân hoạch Phân hoạch đơn giản là chia bài toán thành các phần nhỏ Tuy nhiên, các công thức phân hoạch đều yêu cầu kết quả của các phần nhỏ hợp lại để đạt được kết quả mong muốn Kĩ thuật phân hoạch có thể được áp dụng trong dữ liệu của... tác vụ tách biệt và có thể song song hóa theo cách phân chia dữ liệu Việc tìm ra các chức năng có thể thực hiện đồng thời trong một bài toán ít phổ biến hơn, nhưng chia nhỏ dữ liệu lại là chiến lược chính trong việc lập trình song song Kĩ thuật chia nhỏ bài toán được áp dụng trực tiếp và hiệu quả(không phải là tối ưu) với các bài toán tính toán song song lý tưởng, tức là bài toán được chia thành các... lại để đưa ra tổng của dãy.(Hình ) Thời gian thực hiện song song của bài toán trên, t p = O(n + m) Hình 2.4: Chia nhỏ một dãy các số thành nhiều phần và tính tổng các phần Thời gian thực hiện song song tồi hơn so với thuật toán tuần tự 2.1.2 Chia để trị Cách tiếp cận chia để trị( divide-and-conquer) được đặc trưng bằng việc chia một bài toán thành các bài toán nhỏ hơn có cùng dạng với bài toán lớn sử dụng. .. là, Cost = t p × n = k × ts trong đó, Cost là chi phí thực hiện, k là hằng số Một thuật toán song song là thuật toán có chi phí tốt nhất nếu (độ phức tạp thời gian song song)×(số bộ xử lý)=(độ phức tạp thời gian tuần tự) Ví dụ Giả sử một thuật toán tuần tự tốt nhất để giải một bài toán có độ phức tạp thời gian là O(nlogn) Thì một thuật toán song song để giải bài toán trên sử dụng n bộ xử lý có độ phức... O(logn) là tốt nhất, trái lại nếu thuật toán đó sử dụng n2 bộ xử lý và có độ phức tạp thời gian là O(1) lại là thuật toán không có chi phí tốt nhất Ngoài ra để đánh giá một thuật toán song song ta phải xét đến hệ số gia tốc của thuật toán Hệ số gia tốc của thuật toán song song sử dụng p bộ xử lý được xác định như sau: S p = Ts /Tp trong đó, + Ts là thời gian thực hiện tính toán trên một bộ xử lý + Tp là... trình song song Có năm nguyên lý chính trong thiết kế thuật toán song song: Các nguyên lý lập lịch Giảm tối thiểu các bộ xử lý sử dụng trong thuật toán song song sao cho thời gian tính toán không tăng(Xét theo khía cạnh độ phức tạp) Nguyên lý hình ống Nguyên lý áp dụng khi bài toán xuất hiện một dãy các thao tác {T0 , T1 , , Tn−1 }, trong đó Ti+1 được thực hiện sau khi Ti kết thúc Nguyên lý chia để trị ... siêu máy tính Song song hóa thuật toán hướng tiếp cận thông dụng để thiết kế thuật toán song song Trong đó, phân hoạch chia để trị hai kĩ thuật để thiết lập tính song song cho toán cách có hiệu... Kĩ thuật phân hoạch, chia để trị số ứng dụng Phân hoạch( partitioning) chia để trị( divide-and-conquer) hai kỹ thuật để xây dựng chương trình song song Hai kĩ thuật có liên quan tới Trong kĩ thuật. .. bày kĩ thuật phân hoạch chia để trị số ứng dụng để xây dựng thuật toán song song Khóa luận em gồm chương: Chương 1: Trình bày tổng quan tính toán song song, nhu cầu, phạm vi tính toán song song,