1.7K 90 69

Đã đăng vào thg 7 2, 2023 4:40 CH 28 phút đọc

274

Tối ưu hóa stream pipelines để xử lý song song

Phần 4 của loạt bài này đã thảo luận về các yếu tố có thể ảnh hưởng đến hiệu quả của quá trình song song hóa. Các yếu tố này bao gồm các đặc điểm của vấn đề, thuật toán được sử dụng để triển khai giải pháp, runtime framework được sử dụng để lên lịch các tác vụ để thực thi song song cũng như kích thước và bố cục bộ nhớ của tập dữ liệu. Phần này áp dụng các khái niệm này cho Streams library và xem xét lý do tại sao stream pipelines tốt hơn các pipelines khác.

Parallel streams

Như chúng ta đã thấy trong Phần 3, một stream pipeline bao gồm stream source, không hoặc nhiều intermediate operations và terminal operation. Để thực thi một stream pipeline, chúng ta xây dựng một "machine" thực hiện intermediate và terminal operations, trong đó chúng ta cung cấp các phần tử từ nguồn. Để thực thi song song một stream pipeline, chúng ta phân vùng dữ liệu nguồn thành các phân đoạn thông qua phân tách đệ quy, sử dụng phương thức trySplit() của Spliterator. Hiệu quả là tạo ra một cây tính toán nhị phân có mỗi nút lá tương ứng với một phân đoạn của dữ liệu nguồn và mỗi nút bên trong tương ứng với một điểm mà vấn đề đã được chia thành các nhiệm vụ con và kết quả của hai nhiệm vụ con cần được kết hợp . Việc thực thi tuần tự xây dựng một machine cho toàn bộ tập dữ liệu; một thực thi song song xây dựng một machine cho từng phân đoạn của dữ liệu nguồn, tạo ra một phần kết quả cho mỗi nút lá. Sau đó, chúng ta tiếp tục cây lên dần, hợp nhất các kết quả từng phần thành các kết quả lớn hơn, theo chức năng hợp nhất dành riêng cho terminal operation.
Ví dụ, đối với terminal operation reduce(), binary operator được sử dụng để rút gọn cũng là hợp nhất; đối với collect(), Collector có chức năng hợp nhất được sử dụng để hợp nhất vùng chứa kết quả này với vùng chứa kết quả khác.

Phần trước đã xác định một số yếu tố có thể khiến việc thực thi song song mất hiệu quả:

Source có thể tốn nhiều chi phí để chia tách, hoặc chia tách không đều.
Hợp nhất một phần kết quả là tốn nhiều chi phí.
Bố cục của kết quả dữ liệu có khả năng truy cập kém.
Không có đủ dữ liệu để khắc phục chi phí khi thực thi song song.

Bây giờ chúng ta xem xét từng cân nhắc này, để mắt đến cách chúng biểu hiện trong các stream pipelines song song.

Source splitting

Với parallel streams, chúng ta sử dụng phương thức trySplit() của Spliterator để chia một đoạn dữ liệu nguồn thành hai. Mỗi nút trong cây tính toán tương ứng với một phép chia nhị phân, tạo thành một cây nhị phân. Lý tưởng nhất là cây này sẽ được cân bằng — với mỗi nút lá đại diện chính xác cùng một lượng công việc — và chi phí phân tách sẽ bằng không.

Lý tưởng này không thể đạt được trong thực tế, nhưng một số nguồn đến gần lý tưởng hơn nhiều so với những nguồn khác. Mảng là trường hợp tốt nhất. Chi phí phân chia đoạn này thành hai phân đoạn bằng nhau là rẻ: chúng ta tính điểm giữa của phân đoạn, tạo một bộ mô tả mới cho nửa đầu và di chuyển index bắt đầu cho phân khúc hiện tại sang phần tử đầu tiên trong nửa sau.

Ví dụ 1 hiển thị mã cho trySplit() trong ArraySpliterator. Mảng có chi phí phân chia thấp — một vài phép tính số học và tạo đối tượng; chúng cũng chia đều (dẫn đến cây tính toán cân bằng). Spliterator cho ArrayList có cùng các đặc điểm mong muốn. (Như một phần thưởng, khi tách các mảng, chúng ta cũng biết kích thước chính xác của tất cả các phần tách, điều này cho phép chúng ta tối ưu hóa các bản sao trong một số stream pipelines.)

public Spliterator<T> trySplit() {
    int lo = index, mid = (lo + fence) >>> 1;
    return (lo >= mid)
           ? null
           : new ArraySpliterator<>(array,
                                    lo, index = mid,
                                    characteristics);
}

Mặt khác, một linked list chia tách khủng khiếp. Để tìm điểm giữa, chúng ta phải duyệt qua một nửa danh sách, mỗi lần một nút. Để giảm chi phí chia tách, chúng ta có thể chấp nhận chia tách không cân bằng hơn — nhưng điều này vẫn không giúp được gì nhiều. Trong trường hợp cực đoan, chúng ta kết thúc với một cây không cân bằng bệnh lý (nặng về bên phải), trong đó mỗi phần tách ra chỉ bao gồm (first element, rest of list)(first element, rest of list) (phần tử đầu tiên, phần còn lại của danh sách). Vì vậy, thay vì các phép tách $O(log n)$ , chúng ta có các phép tách $O(n)$ , yêu cầu các bước kết hợp $O(n)$ . Chúng ta đứng trước sự lựa chọn tồi tệ giữa một cây tính toán rất tốn kém để tạo ra (hạn chế tính song song bằng cách đóng góp vào phần serial fraction của định luật Amdahl) và một cây tính toán thừa nhận tính song song tương đối ít và có chi phí kết hợp cao (vì nó quá mất cân bằng .) Điều đó nói rằng, không phải là không thể loại bỏ tính song song ra khỏi danh sách được liên kết - nếu các hoạt động được thực hiện cho mỗi nút đủ đắt. (Xem thêm phần "NQ Model.")

Cây nhị phân (chẳng hạn như TreeMap) và bộ sưu tập dựa trên hàm băm (chẳng hạn như HashSet) phân chia tốt hơn so với danh sách được liên kết, nhưng không tốt bằng mảng. Cây nhị phân khá rẻ để chia làm hai và nếu cây tương đối cân bằng, cây tính toán kết quả cũng sẽ như vậy. chúng ta triển khai HashMap dưới dạng một mảng các nhóm, trong đó mỗi nhóm là một linked list. Nếu hàm băm trải đều các phần tử trên các nhóm, thì bộ sưu tập sẽ phân chia tương đối tốt (cho đến khi chúng ta chuyển xuống một nhóm duy nhất và sau đó chúng ta quay lại linked list, lý tưởng là linked list này nhỏ). Tuy nhiên, cả collections dựa trên tree và dựa trên hash thường không phân chia dễ đoán như mảng — chúng ta không thể dự đoán kích thước của kết quả phân tách, vì vậy chúng ta mất khả năng tối ưu hóa các bản sao trong một số trường hợp.

Generators as sources

Không phải tất cả các streams đều sử dụng một collection làm source của chúng; một số sử dụng hàm tạo, chẳng hạn như IntStream.range(). Những cân nhắc áp dụng cho các collection sources cũng có thể được áp dụng trực tiếp cho các generators.

Hai ví dụ tiếp theo cho thấy hai cách để tạo luồng bao gồm các số nguyên từ 0 đến 99. Mã này sử dụng Stream.iterate() (phiên bản ba đối số của iterate() đã được thêm vào trong Java 9):

IntStream stream1 = IntStream.iterate(0, n ‑> n < 100,
                                      n ‑> n + 1);

Và mã này sử dụng IntStream.range():

IntStream stream2 = IntStream.range(0, 100);

Hai ví dụ tạo ra cùng một kết quả, nhưng có các đặc điểm phân tách khác nhau đáng kể — và do đó sẽ có hiệu suất song song khác nhau đáng kể.

Stream.iterate() nhận một giá trị ban đầu và hai functions — một để tạo ra giá trị tiếp theo và một để xác định xem có nên ngừng tạo phần tử hay không — giống như một vòng lặp for. Rõ ràng bằng trực giác rằng trình tạo này về cơ bản là tuần tự: Nó không thể tạo ra phần tử n cho đến khi nó tạo ra phần tử n-1. Do đó, việc tách một hàm tạo tuần tự có các đặc điểm giống như tách một danh sách được liên kết (lựa chọn tồi giữa chi phí tách cao và tách không đồng đều cao) và dẫn đến tính song song kém tương tự.

Mặt khác, range() generator chia tách giống như một mảng hơn - thật dễ dàng và rẻ tiền để tính toán điểm giữa của phạm vi mà không cần tính toán các phần tử xen kẽ.

Mặc dù thiết kế của thư viện Luồng bị ảnh hưởng rất lớn bởi các nguyên tắc của functional programming, nhưng sự khác biệt về đặc điểm hiệu suất song song giữa hai generator functions trong các ví dụ trước minh họa một cái bẫy tiềm ẩn đối với những người có nền tảng functional programming. Trong functional programming, việc tạo ra một phạm vi bằng cách lazily sử dụng từ một luồng vô hạn được xây dựng bởi ứng dụng iterative function là điều phổ biến và tự nhiên — nhưng thành ngữ này xuất hiện vào thời điểm mà tính song song dữ liệu là một khái niệm hoàn toàn lý thuyết. Các lập trình viên Functional có thể dễ dàng tiếp cận thành ngữ iterate quen thuộc mà không nhận ra ngay tính tuần tự vốn có của phương pháp này.

Result combination

Chia tách nguồn — hiệu quả và đồng đều, hoặc không — là một chi phí cần thiết để cho phép tính toán song song. Nếu chúng ta may mắn, chi phí chia nhỏ đủ khiêm tốn để chúng ta có thể bắt đầu thực thi song song, tránh vi phạm luật Amdahl.

Mỗi khi chúng ta phân chia nguồn, chúng ta tích lũy nghĩa vụ kết hợp các kết quả trung gian của lần phân chia đó. Sau khi các nút lá đã hoàn thành công việc trên đoạn đầu vào của chúng, chúng ta tiến hành sao lưu cây, kết hợp các kết quả sau khi chúng ta thực hiện.

Một số hoạt động kết hợp - chẳng hạn như reduction với việc cộng kết quả - là rẻ. Nhưng những thứ khác - chẳng hạn như hợp nhất hai set - đắt hơn nhiều. Lượng thời gian dành cho bước kết hợp tỷ lệ thuận với độ sâu của cây tính toán; một cây cân bằng sẽ có độ sâu là $O(log n)$ , trong khi một cây không cân bằng về mặt bệnh lý (chẳng hạn như chúng ta nhận được từ việc tách một danh sách được liên kết hoặc một hàm iterative generating) sẽ có độ sâu là $O(n)$ .

Một vấn đề khác với các phép hợp nhất tốn kém là lần hợp nhất cuối cùng — trong đó hai nửa kết quả đang được hợp nhất — sẽ được thực hiện tuần tự (vì không còn công việc nào khác phải làm). Các Stream pipelines có các bước hợp nhất là O(n)—chẳng hạn như các pipelines sử dụng terminal operations như là sorted() hoặc collect(Collectors.joining()) — có thể thấy tính song song của chúng bị giới hạn bởi hiệu ứng này.

Operation semantics

Giống như một số sources — chẳng hạn như linked list hoặc iterative generator — vốn có tính tuần tự, một số stream operations cũng có khía cạnh tuần tự vốn có, có thể đóng vai trò là trở ngại cho tính song song. Đây thường là các Operation có semantics(ngữ nghĩa) được xác định theo encounter order(thứ tự gặp phải).

Ví dụ: terminal operation findFirst() mang lại phần tử đầu tiên trong stream. (Thao tác này thường được kết hợp với filtering, do đó, nó thường có nghĩa là "tìm phần tử đầu tiên thỏa mãn một số điều kiện.") Việc triển khai findFirst() tuần tự cực kỳ rẻ: Đẩy dữ liệu qua pipeline cho đến khi tạo ra một số kết quả rồi dừng. Khi thực thi song song, chúng ta có thể dễ dàng song song hóa các operations, nhưng khi một kết quả được tạo ra bởi một số nhiệm vụ con, chúng ta vẫn chưa hoàn thành. Chúng ta vẫn phải đợi tất cả các nhiệm vụ phụ xuất hiện trước đó trong thứ tự encounter order cho tới khi kết thúc. (Ít nhất chúng ta có thể hủy bất kỳ nhiệm vụ phụ nào xuất hiện sau encounter order.) Việc thực thi song song trả tất cả các chi phí cho việc phân tách và quản lý tác vụ, nhưng ít có khả năng thu được lợi ích. Mặt khác, hoạt động của thiết bị đầu cuối findAny() có nhiều khả năng đạt được tốc độ tăng tốc song song hơn, bởi vì nó giữ cho tất cả các lõi bận rộn tìm kiếm kết quả phù hợp và có thể kết thúc ngay lập tức khi tìm thấy.

Một terminal operation khác có ngữ nghĩa được gắn với encounter order là forEachOrdered(). Một lần nữa, mặc dù thường có thể song song hóa hoàn toàn việc thực hiện các hoạt động trung gian, bước áp dụng cuối cùng được tuần tự hóa. Mặt khác, hoạt động của terminal operation forEach() không bị hạn chế bởi thứ tự gặp phải. Nó có thể được thực thi cho từng phần tử bất cứ lúc nào và trong bất kỳ luồng nào mà phần tử đó được cung cấp.

Các Intermediate operations, chẳng hạn như limit() và skip(), cũng có thể bị hạn chế bởi thứ tự gặp phải. limit(n) operation cắt bớt stream đầu vào sau n phần tử đầu tiên. Giống như findFirst(), khi các phần tử được tạo bởi một số tác vụ, limit(n) phải đợi tất cả các tác vụ trước nó theo thứ tự gặp phải kết thúc trước khi biết liệu có đẩy các phần tử đó sang phần còn lại của đường ống hay không — và nó phải đệm các phần tử được tạo cho đến khi nó biết liệu chúng có cần thiết hay không. (Đối với stream không có thứ tự, limit(n) được phép chọn n phần tử bất kỳ — và giống như findAny(), thân thiện với song song hơn nhiều.)

chúng ta có thể ngạc nhiên bởi chi phí thời gian và không gian của việc thực hiện song song trong đó các operations được gắn với encounter order. Việc triển khai tuần tự rõ ràng của findFirst() và limit() là đơn giản, hiệu quả và hầu như không yêu cầu chi phí không gian, nhưng việc triển khai song song rất phức tạp và thường liên quan đến việc chờ đợi và lưu vào bộ đệm đáng kể. Với thực thi tuần tự, việc triển khai rõ ràng thường là một trong đó chúng ta duyệt qua đầu vào theo thứ tự gặp phải, do đó, sự phụ thuộc vào thứ tự gặp phải hiếm khi hiển thị hoặc tốn kém. Trong thực thi song song, sự phụ thuộc như vậy có thể rất tốn kém.

May mắn thay, những phụ thuộc này vào encounter order thường có thể được loại bỏ thông qua những thay đổi nhỏ đối với pipeline. Thông thường, chúng ta có thể thay thế findFirst() bằng findAny() mà không làm mất đi tính chính xác. Tương tự, như chúng ta đã thấy trong Phần 3, bằng cách làm cho stream không có thứ tự thông qua unordered() operation, chúng ta thường có thể loại bỏ sự phụ thuộc encounter-order vốn có trong limit(), distinct(), sorted() và collect() mà không cần mất tính đúng đắn.

Các mối nguy hiểm khác nhau đối với việc tăng tốc song song mà chúng ta đã xem xét cho đến nay có thể được tích lũy(kết hợp lại với nhau). Giống như iterate() ba đối số kém hơn nhiều so với range constructor, việc kết hợp nguồn iterate() hai đối số với limit() thậm chí còn tệ hơn, vì nó kết hợp bước tạo tuần tự với operation nhạy cảm encounter-order .

IntStream stream3 = IntStream.iterate(0, n ‑> n+1).limit(100);

Memory locality

Các hệ thống máy tính hiện đại sử dụng bộ đệm đa cấp tinh vi để giữ dữ liệu được sử dụng thường xuyên càng gần (theo nghĩa đen - tốc độ ánh sáng là một yếu tố hạn chế!) với CPU càng tốt. Tìm nạp dữ liệu từ bộ đệm L1 có thể dễ dàng nhanh hơn 100 lần so với tìm nạp dữ liệu từ bộ nhớ chính. CPU có thể dự đoán dữ liệu nào sẽ cần tiếp theo hiệu quả hơn, thì CPU dành nhiều chu kỳ hơn để thực hiện tính toán và thời gian chờ đợi dữ liệu càng ít.

Dữ liệu được phân trang vào bộ đệm ở mức độ chi tiết của các dòng bộ đệm; chip x86 ngày nay(2016) sử dụng kích thước dòng bộ đệm là 64 byte. Điều này thưởng cho các chương trình có memory locality tốt— xu hướng truy cập các vị trí memory locations với các vị trí bộ nhớ đã được truy cập gần đây. Truy cập tuyến tính thông qua một mảng không chỉ có vị trí tuyệt vời mà còn được thưởng thêm bằng cách prefetch(tìm nạp trước)— khi phát hiện thấy một kiểu truy cập bộ nhớ tuyến tính, phần cứng bắt đầu tìm nạp trước giá trị bộ nhớ của dòng bộ đệm tiếp theo với giả định rằng nó có thể sẽ cần thiết sớm.

Các triển khai Java chính thống sắp xếp các trường của một đối tượng và các phần tử của một mảng, liền kề nhau trong bộ nhớ (mặc dù các trường không nhất thiết phải được sắp xếp theo thứ tự được khai báo trong source file). Việc truy cập các trường hoặc phần tử mảng "gần" trường hoặc phần tử được truy cập gần đây nhất có nhiều khả năng chạm vào dữ liệu đã có trong bộ đệm. Mặt khác, các tham chiếu đến các đối tượng khác được biểu diễn dưới dạng con trỏ, do đó, việc dereferencing(có nghĩa là hành động truy cập các tính năng của một đối tượng thông qua một tham chiếu.) một tham chiếu của đối tượng có nhiều khả năng ảnh hưởng đến dữ liệu chưa có trong bộ đệm, gây ra độ trễ.

Một mảng các biến nguyên thủy cung cấp vị trí tốt nhất có thể. Sau lần dereference ban đầu của tham chiếu mảng, dữ liệu được lưu trữ liên tục trong bộ nhớ, vì vậy chúng ta có thể tối đa hóa lượng tính toán cho mỗi lần tìm nạp dữ liệu. Một mảng các object references(tham chiếu tới đối tượng) sẽ có vị trí tốt khi tìm nạp tham chiếu tiếp theo trong mảng, nhưng có nguy cơ bị miss cache(không thấy trong bộ đệm) khi dereferencing các tham chiếu đối tượng đó. Tương tự như vậy, một lớp chứa nhiều trường nguyên thủy sẽ có khả năng sắp xếp các trường gần nhau trong bộ nhớ, trong khi một lớp chứa nhiều tham chiếu đối tượng sẽ yêu cầu nhiều tham chiếu để truy cập trạng thái của nó. Cuối cùng, cấu trúc dữ liệu càng nhiều con trỏ thì càng có nhiều áp lực truyền qua cấu trúc dữ liệu như vậy đặt lên các đơn vị tìm nạp bộ nhớ, điều này có thể có tác động tiêu cực đến cả thời gian tính toán (trong khi CPU dành thời gian chờ đợi dữ liệu) và tính song song ( vì nhiều lõi tìm nạp đồng thời từ bộ nhớ sẽ gây áp lực lên băng thông khả dụng để truyền dữ liệu từ bộ nhớ sang bộ đệm).

The NQ model

Để xác định xem tính song song có giúp tăng tốc hay không, các yếu tố cuối cùng cần xem xét là lượng dữ liệu có sẵn và lượng tính toán được thực hiện trên mỗi phần tử dữ liệu.

Trong mô tả ban đầu của chúng ta về phân tách song song, chúng ta đã viện dẫn khái niệm phân tách nguồn cho đến khi các phân đoạn nhỏ đến mức một cách tiếp cận tuần tự để giải quyết vấn đề trên phân đoạn đó sẽ hiệu quả hơn. Các phân đoạn phải nhỏ đến mức nào tùy thuộc vào vấn đề đang được giải quyết và cụ thể là khối lượng công việc được thực hiện trên mỗi phần tử. Ví dụ: tính toán độ dài của một chuỗi cần ít công việc hơn nhiều so với tính toán hàm băm SHA-1 của chuỗi. Càng nhiều công việc được thực hiện trên mỗi phần tử, ngưỡng "đủ lớn để trích xuất song song" càng thấp. Tương tự, chúng ta càng có nhiều dữ liệu, chúng ta càng có thể chia dữ liệu thành nhiều phân đoạn mà không vi phạm ngưỡng "quá nhỏ".

Một mô hình đơn giản nhưng hữu ích cho hiệu suất song song là mô hình NQ, trong đó N là số phần tử dữ liệu và Q là số lượng công việc được thực hiện trên mỗi phần tử. Kết quả $N*Q$ càng lớn, chúng ta càng có nhiều khả năng tăng tốc song song. Đối với các vấn đề với Q nhỏ tầm thường, chẳng hạn như cộng các số, chúng ta thường muốn thấy N > 10.000 để tăng tốc; khi Q tăng lên, kích thước dữ liệu cần thiết để tăng tốc sẽ giảm xuống.

Nhiều trở ngại đối với tính song song — chẳng hạn như chi phí phân chia, chi phí kết hợp hoặc độ nhạy của encounter order. Mặc dù các đặc điểm phân tách của LinkedList có thể rất tệ, nhưng vẫn có thể tăng tốc song song với Q đủ lớn.

Kết luận

Bởi vì tính song song chỉ cung cấp tiềm năng cho thời gian chạy nhanh hơn, chúng ta chỉ nên sử dụng nó khi nó tạo ra tốc độ tăng tốc thực tế. Phát triển và kiểm tra mã của chúng ta bằng cách sử dụng các luồng tuần tự; sau đó, nếu các yêu cầu về hiệu suất của chúng ta cho thấy cần phải cải thiện thêm, hãy xem xét tính song song như một chiến lược tối ưu hóa khả thi.

Mặc dù việc đo lường là rất quan trọng để đảm bảo rằng các nỗ lực tối ưu hóa của chúng ta không phản tác dụng, nhưng đối với nhiều stream pipelines, chúng ta có thể xác định thông qua kiểm tra rằng chúng không phải là ứng cử viên sáng giá cho quá trình song song hóa. Các yếu tố ảnh hưởng đến tốc độ tăng tốc song song tiềm năng bao gồm các nguồn phân tách kém hoặc không đồng đều, chi phí kết hợp cao, phụ thuộc vào encounter order, memory locality không tốt hoặc không đủ dữ liệu. Mặt khác, một lượng lớn tính toán $(Q)$ trên mỗi phần tử có thể bù đắp phần nào những thiếu sót này.

Java Developer