Đề tài Tìm hiểu tính toán song song hóa thuật toán và ứng dụng song song bài toán sắp xếp theo giỏ (Bucket Sort)

Nội dung: Tìm hiểu tính toán song song hóa thuật toán và ứng dụng song song bài toán sắp xếp theo giỏ (bucket sort) MỤC LỤC Phần I: MỞ ĐẦU Bốn thập kỷ qua chứng kiến sự phát triển bùng nổ về sức mạnh máy tính, tạo tiền đề cho những bước tiến chưa từng thấy về phát minh, năng suất lao động và phúc lợi cho con người. Nhưng quá trình đó giờ đây đứng trước một trở ngại mà ít ai nghĩ đến: sự kết thúc của quá trình mở rộng sức mạnh điện toán. Ngành tin học đã đạt đến giới hạn của những gì từng khả thi với một hay hai vi xử lý trung tâm hoạt động theo chuỗi truyền thống (serial processing). Ngành nào vẫn dựa vào mô hình đó để tiếp tục phát triển năng suất, tăng trưởng kinh tế và phát triển xã hội thì cần phải bắt đầu một bước nhảy mới vào điện toán xử lý song song (parallel processing). 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 hoá 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 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ý 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. Minh họa một cách đơn giản, tính toán truyền thống giống như việc một người đọc bài văn theo kiểu tuần tự từ đầu đến cuối, còn tính toán song song thì giống như tách bài văn đó thành các phần và cho nhiều người khác nhau cùng đọc một lúc để có kết quả nhanh hơn. Tính toán song song mang lại một nền tảng mới cho sự phát triển của công nghệ xử lý. Đây là một hướng đi mới, đúng đắn và hiệu quả cho công nghệ điện toán trong tương lai. Bài viết sau đây về đề tài “Tìm hiểu về tính toán song song , áp dụng giải quyết một số bài toán” phần nào thể hiện được những kiến thức cơ bản đầu tiên về tính toán song song, tính đúng đắn và ứng dụng của nó. Phần II: NỘI DUNG I. Những khái niệm cơ bản về tính toán song song 1. Nhu cầu tính toán hiệu năng cao và tính khả dụng của tính toán song song. a. Nhu cầu tính toán song song Ví dụ 1: Oregon State University: Mô phỏng các dòng chảy lưu thông của đại dương --> xác định nguyên nhân gây trái đất đang nóng dần lên. - Phân chia đại dương thành: • 4096 vùng từ đông sang tây. • 1024 vùng từ bắc sang nam. • 12 tầng biển. • Xấp sỉ 50 triệu khối trong không gian 3 chiều. - Mô phỏng lưu thông thực hiện ~ 30 tỷ phép tính trong 10 phút. Công việc này thực hiện liên tục trong năm. Ví dụ 2: Dự báo thời tiết (weather forecasting): - Chia bầu khí quyển theo không gian 3 chiều, mỗi khối kích thước 1mile x 1mile x 1mile. - Ước tính khoảng 5x10^8 khối (cells). - Trên mỗi khối cần thực hiện ~ 200 phép toán -> cần thực hiện ~ 10^11 phép toán. - Nếu cần dự báo cho 1 tuần, chu kỳ 1 phút -> cần thực hiện 10^4 lần, mỗi lần 10^11phép toán. - Siêu máy tính có thể thực hiện: 10^9 phép toán trên 1 giây -> cần 10^6 giây ~ 10 ngày để thực hiện. Ví dụ 3: Mô phỏng tương tác của các protein với phân tử nước (Levin 1990): - Thực hiện trên máy Cray X/MP (~800 triệu phép toán / 1 giây): để mô phỏng 10^-12 giây phản ứng protein cần 1 giờ thực hiện. - Nếu mô phỏng một phản ứng thực sự trên cùng máy Cray X/MP cần 31,688 năm. TÓM LẠI: Yêu cầu về thực nghiệm nghiên cứu, mô phỏng -> giải quyết những bài toán có khối lượng tính toán lớn trong một khoảng thời gian chấp nhận được. Phương hướng giải quyết vấn đề: - Thực hiện trên các siêu máy tính mạnh. - Thực hiện phân chia công việc thực hiện song song trên hệ thống các máy tính Tính khả dụng của tính toán song song SIÊU MÁY TÍNH: Khả năng tính toán phụ thuộc nhiều vào tốc độ xử lý của CPU -> phụ thuộc vào cấu trúc và số lượng transistors chứa trong CPU –> Có những giới hạn nhất định về kích thước, nhiệt độ -> không thể tăng số transistors lên mãi được THỰC HIỆN SONG SONG: Nguyên tắc: thực hiện phân chia công việc chính thành các công việc con, có thể thực hiện song song với nhau. Xây dựng hệ thống song song từ nhiều bộ xử lý riêng biệt. Thực hiện các công việc song song trên các bộ xử lý đó. Vấn đề: - Phương pháp phân chia công việc. - Môi trường hỗ trợ thực hiện song song. Ví dụ: Xếp sách trong thư viện Sách trong thư viện được phân loại theo chữ cái đầu tiên và sắp xếp theo thứ tự. Sách cùng nhóm được xếp trên cùng một giá. Các giá đặt trong các tủ sách. Thư viện nhập một số lượng sách lớn -> yêu cầu thủ thư phải sắp xếp sách theo đúng nguyên tắc. Cách giải quyết hiệu quả nhất? + Nếu chỉ có 1 thủ thư - Cách thứ nhất: Lấy từng cuốn sách rồi sắp xếp vào vị trí thích hợp -> không hiệu quả. - Cách thứ hai: Sắp xếp các cuốn sách theo thứ tự trước rồi mang từng chồng sách cùng vị trí đi sắp xếp. Rõ ràng cách thứ 2 hiệu quả hơn. Muốn hiệu quả hơn nữa thì cần có nhiều người làm hơn. + Nhiều thủ thư hơn Cách thứ nhất: Mỗi người lấy 1 cuốn rồi đi sắp đặt vị trí -> không hiệu quả. Cách thứ hai: Phân chia mỗi người một nhóm ký tự, khi đó mỗi người chỉ mang sách thuộc nhóm mình đi sắp xếp. Cách thứ ba: Sắp xếp sách trước khi mang đi đặt vị trí. Mỗi người đảm nhận một số ký tự: Nếu cuốn sách đang cầm của mình thì đặt vào chồng sách của mình. Nếu của người khác thì chuyển cho người đấy. Sau đó mang sách đi sắp xếp. -> cách thứ ba hiệu quả nhất. Ý nghĩa của tính toán song song Thực hiện công việc trong khoảng thời gian ngắn hơn -> tiết kiệm thời gian. Thực hiện được với số lượng phép toán lớn hơn -> giải quyết được bài toán lớn. Hỗ trợ giải quyết nhiều công việc đồng thời. 2. 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ệ 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 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 hợp trong việc tối ưu hoá 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. 3. Các loại máy tính song song 3.1. Phân loại theo 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 Dựa vào số lượng dòng lệnh và số lượng dòng dữ liệu thực thi cùng tại một thời điểm 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 - Máy tính MISD: Đa dòng lệnh – đơn dòng dữ liệu - Máy tính SIMD: Đơn dòng lệnh – đa dòng dữ liệu - Máy tính MIMD: Đa dòng lệnh – đa dòng dữ liệu 3.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ẻ - Hệ thống đa máy tính bộ nhớ phân tán - Hệ thống bộ nhớ chia sẻ phân tán 4. Các mô hình lập trình song song Lập trình song song là sự trừu tượng hoá 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ác lý thuyết thì một loại mô hình lậo trình song song có thể được thể hiện dưới một phần cứng bất kỳ. 4.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ẻ 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 giữa các tác vụ. Việc phát triển chương trình có thể được đơn giản hoá. 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. 4.2. 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 huỷ 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 Linux, Unix hay Windows đều phải điều phối sự hoạt động đồng bộ của 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. 4.3. Lập trình chia sẻ bộ nhớ dựa vào luồng 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 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 hoá 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. 4.4. 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 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ộ hoá 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ự. 5. Thuật toán song song 5.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ác 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 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à 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 xử lý ở các giai đoạn khác nhau của việc thực thi chương trình. 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. - Nguyên lý hình ống. - Nguyên lý chia để trị. - Nguyên lý đồ thị phụ thuộc dữ liệu. - Nguyên lý điều kiện ganh đua. 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. - Tác vụ (Task) - Tiến trình (process) - Thực hiện tuần tự - Thực hiện song song Phương pháp luận để thiết kế thuật toán song song gồm bốn giai đoạn khác nhau: - Sự chia nhỏ bài toán (partitioning) - Thiết lậo kênh truyền (communication) - Nhóm gom các tác vụ (agglomeration) - Gán vào hệ thống (mapping) II. Lập trình song song với MPI Lập trình song song cũng giống như 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 thực hiện theo 3 cách: - 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). - 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ừ khoá và mở rộng một cú phát để xử lý việc trao đổi thông điệp, gồm có CC+ (mở rộng từ C++) và Fortram M ( mở rộng từ Rortran) - Sủ dụ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. III. Thuật toán sắp xếp 1. 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 soag hoá 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 bụcket 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ừ o đế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ỏ. 2. 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 cách thích hợp, ta có thể so sánh số đó với 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ỏi tương ứng từ 0 đến m - 1. Nếu m là luỹ 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ỏi cần 1 bước. Vậy để đặt tất cả các số cần n bước. Hình 1: 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 nlogn 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 xếp để đưa ra dãy đã sắp cuối cù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+nlog(n/m) = O(nlog(n/m)) Nếu n = km, k là hằng số thì độ phức tạp thời gian là O(n) 3. Thuật toán song song Một các đơ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ỏi sẽ là (n/p)log(n/p) với p bộ xử lý (trong đó p=m). 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ỗĩ 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 giỏ riêng của mình. Sau đó các giỏ 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ỏi thứ i tới bộ xử lý thứ i). Hình 2: 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: tcomp1 = tsrartup + tdatan 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 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ó: tcomp3 = p(p - 1)(tsrartup + (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ó tcomp3 = (p - 1)(tsrartup + (n/p2) tdata) 4. Sắp xếp trong giỏ lớn Tron giai đoạn này, các giỏ lớn được sắp xếp đồng thời, do đó: tcomp4 = (n/p)log(n/p) Vậy tổng thời gian thực hiện là" tp = tsrartup + tdatan + (p-1)(tsrartup + (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ì 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 hướng 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. Phần III: MÃ NGUỒN 1. Mã code thực hiện song song thuật toán bucket sort bằng cách gán cho mỗi tiến trình một giỏ. #include #include #include int 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; int *counters, *displs; int start, end, slice; int count, disp,i; double tstart,tend; MPI_Status status; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&p);//p la so tien trinh MPI_Comm_rank(MPI_COMM_WORLD,&rank); // khoi tao so ngau nhien // Cấp phát bộ nhớ cho mảng, gửi thông tin đến các tiến trình con bằng hàm MPI_Bcast srand(time(NULL)); if(rank==0) { printf("Nhap vao so phan tu cua mang "); scanf("%d", &n); array = (int *)malloc(sizeof(int)*n);//cap phat bo nho dong cho mang printf("Nhap vao gia tri cua a (gia tri cua mang) :"); scanf("%d",&a); // dien cac so ngau nhien vao mang printf("Dien cac so ngau nhien vao mang :"); for(i=0; i<n; i++) { array[i] = rand() % a; printf("a[%d] = %d ",i, array [i]); } printf("\n"); } tstart = MPI_Wtime(); //gui cac thong so mang,a,n vao cac tien trinh 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); tend = MPI_Wtime(); printf("Thoi gian may chu Broadcast toi cac tien trinh %d : %lf \n",rank,tend-tstart); tstart=MPI_Wtime(); slice=a/p; start=rank*slice; end=(rank==p-1)?a:start+slice; // Tính toán thời gian xử lý trong các tiến trình con, trả về kết quả cho máy chủ xử lý count=0; local=(int*)malloc(sizeof(int)*n); //ghep mot cua mang thanh mot nhom for(i=0; i<n; i++) if(array[i]=start) local[count++]=array[i]; //sap xep cac so trong nhom sort(local, count); //scan tat ca cac phan tu MPI_Scan(&count,&disp,1,MPI_INT,MPI_SUM,MPI_COMM_WORLD); //Master se tap hop va tinh toan ket qua if(rank==0) counters=(int*)malloc(sizeof(int)*p); MPI_Gather(&count,1,MPI_INT,counters,1,MPI_INT,0,MPI_COMM_WORLD); if(rank==0) { displs=(int*)malloc(sizeof(int)*(p+1)); displs[0]=0; } MPI_Gather(&disp,1,MPI_INT,d