Thuật toán song song - Mô hình

Mô hình thuật toán song song được phát triển bằng cách xem xét chiến lược phân chia dữ liệu và phương pháp xử lý, đồng thời áp dụng chiến lược phù hợp để giảm tương tác. Trong chương này, chúng ta sẽ thảo luận về các Mô hình Thuật toán Song song sau:

Mô hình song song dữ liệu
Mô hình biểu đồ nhiệm vụ
Mô hình hồ bơi làm việc
Mô hình nô lệ chủ
Người tiêu dùng hoặc mô hình đường ống của nhà sản xuất
Mô hình lai

Dữ liệu song song

Trong mô hình song song dữ liệu, các tác vụ được gán cho các tiến trình và mỗi tác vụ thực hiện các kiểu hoạt động tương tự trên các dữ liệu khác nhau. Data parallelism là hệ quả của các hoạt động đơn lẻ đang được áp dụng trên nhiều mục dữ liệu.

Mô hình song song dữ liệu có thể được áp dụng trên không gian địa chỉ dùng chung và mô hình truyền thông điệp. Trong mô hình song song dữ liệu, chi phí tương tác có thể được giảm thiểu bằng cách chọn một khu vực duy trì sự phân hủy, bằng cách sử dụng các quy trình tương tác tập thể được tối ưu hóa hoặc bằng cách tính toán và tương tác chồng chéo.

Đặc điểm cơ bản của các bài toán mô hình song song dữ liệu là cường độ của tính song song dữ liệu tăng theo quy mô của bài toán, do đó có thể sử dụng nhiều quy trình hơn để giải quyết các vấn đề lớn hơn.

Example - Phép nhân ma trận dày đặc.

Mô hình biểu đồ nhiệm vụ

Trong mô hình biểu đồ nhiệm vụ, tính song song được biểu thị bằng một task graph. Một biểu đồ nhiệm vụ có thể tầm thường hoặc không tầm thường. Trong mô hình này, mối tương quan giữa các nhiệm vụ được sử dụng để thúc đẩy địa phương hoặc để giảm thiểu chi phí tương tác. Mô hình này được thực thi để giải quyết các vấn đề trong đó số lượng dữ liệu liên quan đến các nhiệm vụ là rất lớn so với số lượng tính toán liên quan đến chúng. Các nhiệm vụ được giao để giúp cải thiện chi phí di chuyển dữ liệu giữa các nhiệm vụ.

Examples - Sắp xếp nhanh song song, phân tích nhân tử ma trận thưa thớt và các thuật toán song song xuất phát từ phương pháp chia để trị.

Ở đây, các bài toán được chia thành các nhiệm vụ nguyên tử và được thực hiện dưới dạng đồ thị. Mỗi nhiệm vụ là một đơn vị công việc độc lập có sự phụ thuộc vào một hoặc nhiều nhiệm vụ tiền nhiệm. Sau khi hoàn thành một nhiệm vụ, đầu ra của một nhiệm vụ trước đó được chuyển cho tác vụ phụ thuộc. Một tác vụ với tác vụ tiền trước chỉ bắt đầu thực thi khi toàn bộ tác vụ tiền trước của nó được hoàn thành. Đầu ra cuối cùng của đồ thị nhận được khi hoàn thành nhiệm vụ phụ thuộc cuối cùng (Nhiệm vụ 6 trong hình trên).

Mô hình Work Pool

Trong mô hình nhóm làm việc, các nhiệm vụ được gán động cho các quy trình để cân bằng tải. Do đó, bất kỳ quy trình nào cũng có thể thực thi bất kỳ tác vụ nào. Mô hình này được sử dụng khi số lượng dữ liệu được liên kết với các tác vụ tương đối nhỏ hơn so với phép tính liên quan đến các tác vụ.

Không có sự giao trước nhiệm vụ mong muốn cho các quy trình. Việc phân công nhiệm vụ mang tính tập trung hoặc phân cấp. Con trỏ đến các nhiệm vụ được lưu trong danh sách chia sẻ vật lý, trong hàng đợi ưu tiên, hoặc trong bảng băm hoặc cây, hoặc chúng có thể được lưu trong cấu trúc dữ liệu phân tán vật lý.

Nhiệm vụ có thể có sẵn ngay từ đầu hoặc có thể được tạo động. Nếu nhiệm vụ được tạo động và việc phân công nhiệm vụ được phân cấp được thực hiện, thì thuật toán phát hiện kết thúc là cần thiết để tất cả các quy trình thực sự có thể phát hiện việc hoàn thành toàn bộ chương trình và ngừng tìm kiếm nhiệm vụ khác.

Example - Tìm kiếm cây song song

Mô hình Master-Slave

Trong mô hình chủ-tớ, một hoặc nhiều quy trình chính tạo ra nhiệm vụ và phân bổ nó cho các quy trình phụ. Các nhiệm vụ có thể được phân bổ trước nếu -

bậc thầy có thể ước tính khối lượng của các nhiệm vụ, hoặc
một chỉ định ngẫu nhiên có thể thực hiện công việc cân bằng tải một cách thỏa đáng, hoặc
nô lệ được giao những nhiệm vụ nhỏ hơn vào những thời điểm khác nhau.

Mô hình này thường phù hợp với shared-address-space hoặc là message-passing paradigms, vì tương tác tự nhiên là hai cách.

Trong một số trường hợp, một nhiệm vụ có thể cần được hoàn thành trong các giai đoạn và nhiệm vụ trong mỗi giai đoạn phải được hoàn thành trước khi nhiệm vụ trong các giai đoạn tiếp theo có thể được tạo ra. Mô hình chủ-tớ có thể được khái quát thànhhierarchical hoặc là multi-level master-slave model trong đó bậc thầy cấp cao nhất cung cấp phần lớn nhiệm vụ cho bậc thầy cấp hai, người này sẽ chia nhỏ các nhiệm vụ cho các nô lệ của chính nó và có thể tự thực hiện một phần nhiệm vụ.

Các lưu ý khi sử dụng mô hình chủ-tớ

Cần cẩn thận để đảm bảo rằng bản gốc không trở thành điểm tắc nghẽn. Nó có thể xảy ra nếu các nhiệm vụ quá nhỏ hoặc công nhân tương đối nhanh.

Các nhiệm vụ nên được lựa chọn theo cách mà chi phí thực hiện một nhiệm vụ chi phối chi phí truyền thông và chi phí đồng bộ hóa.

Tương tác không đồng bộ có thể giúp tương tác chồng chéo và tính toán liên quan đến việc tạo công việc của chủ.

Mô hình đường ống

Nó còn được gọi là producer-consumer model. Tại đây, một tập hợp dữ liệu được chuyển qua một loạt các quy trình, mỗi quy trình thực hiện một số nhiệm vụ trên đó. Ở đây, sự xuất hiện của dữ liệu mới tạo ra việc thực thi một tác vụ mới bởi một quá trình trong hàng đợi. Các quy trình có thể tạo thành một hàng đợi ở dạng mảng tuyến tính hoặc đa chiều, cây hoặc đồ thị tổng quát có hoặc không có chu trình.

Mô hình này là một chuỗi giữa người sản xuất và người tiêu dùng. Mỗi quá trình trong hàng đợi có thể được coi là người sử dụng một chuỗi các mục dữ liệu cho quá trình trước nó trong hàng đợi và như một nhà sản xuất dữ liệu cho quá trình theo sau nó trong hàng đợi. Hàng đợi không cần phải là một chuỗi tuyến tính; nó có thể là một đồ thị có hướng. Kỹ thuật giảm thiểu tương tác phổ biến nhất áp dụng cho mô hình này là tương tác chồng chéo với tính toán.

Example - Thuật toán phân tích nhân tử LU song song.

Mô hình kết hợp

Mô hình thuật toán kết hợp được yêu cầu khi có thể cần nhiều hơn một mô hình để giải quyết một vấn đề.

Một mô hình kết hợp có thể bao gồm nhiều mô hình được áp dụng phân cấp hoặc nhiều mô hình được áp dụng tuần tự cho các giai đoạn khác nhau của một thuật toán song song.

Example - Sắp xếp nhanh song song