Giảm: Con ngựa của lập trình song song


Hoàng Xuân Nghi
4 năm trước
Hữu ích 5 Chia sẻ Viết bình luận 0
Đã xem 3074

Tất nhiên, bí mật cho dữ liệu lớn là khả năng thực hiện công việc song song. Các công cụ Dữ liệu lớn hiện đại như Hadoop không dựa vào việc phát minh ra các thuật toán mới thông minh hoặc trí tuệ nhân tạo để tạo ra kết quả ấn tượng; thay vào đó, họ dựa trên ý tưởng lấy nhiều đầu vào, làm việc trên các mảnh nhỏ của nó ở nhiều nơi cùng một lúc, sau đó mang lại kết quả cùng nhau. Thông thường, kết quả nhỏ hơn nhiều so với đầu vào, đủ nhỏ để con người có thể nhìn trực tiếp vào chúng.

Song song, tương đông

Để làm việc trên nhiều mảnh nhỏ cùng một lúc, bất kỳ nhiệm vụ nào chúng tôi thực hiện phải được cấu trúc để được chạy song song. Nhiều thuật toán chúng ta thường thấy hoạt động tốt theo tuần tự phải được điều chỉnh ít nhất một chút để hoạt động song song và một số thuật toán phải bị loại bỏ vì không thể sử dụng song song. Ví dụ, một số hàm băm mật mã không thể được thực hiện để chạy song song, điều này có ý nghĩa bởi vì hàm băm mật mã tốt là một trong đó đầu ra thay đổi theo những cách không thể đoán trước nếu đầu vào có một thay đổi nhỏ ở bất cứ đâu.

Mặt khác, một vấn đề trong đó một thuật toán song song rõ ràng có tên là "song song một cách rõ ràng". Nói chung, điều này có nghĩa là mối quan hệ của đầu vào với đầu ra rõ ràng duy trì tính độc lập của mỗi phần. Ví dụ, nhân đôi mọi số trong một dãy số nguyên dài là song song xấu hổ vì dễ thấy rằng nó có thể bị chia thành nhiều mảnh.

Mappers

Bản hùng ca đằng sau MapReduce là thực tế là nhiều vấn đề (như công cụ tìm kiếm) có thể bị chia thành hai mảnh. Trong giai đoạn bản đồ, chúng ta chỉ cần xem xét song song từng mục dữ liệu và thực hiện một số thao tác cụ thể cho nó. (Trong thực tế, chúng tôi nhóm các mục lại với nhau. Hadoop gọi đây là sự phân tách. Nhưng đó chỉ là để tối ưu hóa, không phải vì lý do toán học.) Trong giai đoạn giảm, chúng tôi kết hợp đầu ra của các trình ánh xạ để tạo ra đầu ra cuối cùng. (Hadoop có một giai đoạn khác mà nó gọi là "combiner", nhưng đây chỉ là công cụ giảm tốc cho các trình ánh xạ trên một máy duy nhất, để tiết kiệm lưu lượng mạng. Một lần nữa, chỉ để tối ưu hóa.)

Hầu hết các thuật toán bản đồ là song song. Trong ví dụ đếm từ của Hadoop, tệp văn bản đầu vào được mã hóa thành các từ riêng lẻ. Pha bản đồ lấy từ trong và đưa ra một cặp (một đối tượng hai giá trị đơn giản) với từ và số 1. Tất cả các phép đếm thực tế được thực hiện trong bộ giảm tốc. Với tìm kiếm, giai đoạn bản đồ có thể chỉ cần tính điểm cho một tài liệu cụ thể với các cụm từ tìm kiếm, trong khi đó, bộ giảm tốc sẽ làm công việc khó khăn để đưa kết quả theo thứ tự.

Giảm tốc

Vì vậy, bộ giảm tốc là nơi toán học trở nên thú vị hơn. Chúng tôi hoàn toàn phải tìm cách chạy song song bộ giảm tốc của chúng tôi. Nếu không, khả năng chạy song song trình ánh xạ sẽ bị lãng phí và tổng thời gian chạy của chúng tôi sẽ không tốt hơn là chỉ chạy một thuật toán tuần tự. Nhưng bộ giảm tốc khá rõ ràng sẽ hoạt động trên nhiều dữ liệu. Đối với ví dụ đếm từ, nó có vẻ không tệ lắm, bởi vì chúng ta có thể có một bộ giảm riêng cho mỗi từ duy nhất trong văn bản. Đó có thể là nhiều bộ giảm hơn mức chúng ta có thể tạo ra một cách hợp lý dựa trên chi phí tạo ra một cái mới, vì vậy chúng tôi hy vọng có thể tối ưu hóa để có tốc độ tốt nhất.

Tuy nhiên, những gì về tìm kiếm văn bản của chúng tôi, cần tìm "top 10" hoặc một ví dụ mà chúng tôi muốn tổng hợp tất cả các số trong một danh sách dài các số nguyên, thay vì chỉ hoạt động trên mỗi số nguyên?

Đối với những ví dụ này, chúng ta có thể thấy khá rõ rằng có một cách song song để xử lý chúng. Đối với top 10, hãy để mỗi bộ giảm tốc tìm ra top 10 cho phần dữ liệu nhỏ của nó, sau đó tìm "đỉnh của đỉnh". Bạn thậm chí có thể thêm các bước trung gian vào đó nếu bạn cần, vì vậy trong  Ký hiệu Big O,  chúng tôi sẽ nói là như vậy  O(log n). Đối với tổng của tất cả các số, mỗi bộ giảm có thể tính tổng nhóm nhỏ của riêng mình, sau đó chúng ta có thể cộng các tổng lại với nhau. Một lần nữa, đây là  O(log n).

Mặc dù điều này rất tốt cho những ví dụ cụ thể đó, nhưng thật tuyệt nếu chúng ta có một quy tắc chung để biết khi nào chúng ta có thể mong đợi bộ giảm tốc của chúng ta hoạt động song song. Nó không hoàn toàn đơn giản như người vẽ bản đồ, bởi vì chúng ta sẽ không bao giờ có sự độc lập giữa các bước song song. Nhưng có một khái niệm chúng ta có thể mang lại.

Kết hợp

Các thuộc tính kết hợp là (vẫn) được dạy trong toán cấp tiểu học. Đó là ý tưởng rằng, đối với một số thao tác, thứ tự bạn áp dụng chúng không thành vấn đề. Ngoài ra tất nhiên là kết hợp, như  (4 + 5) + 3 = 4 + (5 + 3). Nó chỉ ra rằng nếu chúng ta có thể viết một hàm có liên quan, thì chúng ta có thể tạo một bộ giảm song song từ nó. Đây là lý do tại sao ví dụ xếp hạng của chúng tôi ở trên hoạt động, bởi vì chức năng  max() này là kết hợp :  max(max(a, b), c) == max(a, max(b, c).

(Lưu ý bên lề: điều này giả định rằng các mặt hàng không thể có thứ hạng giống hệt nhau hoặc chúng tôi không quan tâm nếu các mặt hàng được xếp hạng giống hệt nhau có cùng thứ tự.)

Hóa ra, ngay cả điều này là quá nghiêm ngặt, bởi vì có những thủ thuật chúng ta có thể chơi với bộ giảm tốc của chúng ta trong trường hợp nó không hoàn toàn theo cách liên kết (nghĩa là "bán xã hội"). Chủ đề này xứng đáng với bài đăng đầy đủ của riêng mình, vì nó cần một ví dụ chi tiết hơn, vì vậy tôi sẽ lưu nó cho lần sau.

Hữu ích 5 Chia sẻ Viết bình luận 0
Đã xem 3074