Những hạn chế nào đối với người dùng sử dụng các thuật toán song song của STL?

Question

Tại cuộc họp Jacksonville, đề nghị P0024r2 áp dụng hiệu quả các thông số kỹ thuật từ Parallelism TS đã được chấp nhận vào C++17 (draft). Đề xuất này thêm quá tải cho nhiều thuật toán tham số chính sách thực thi đối số để cho biết loại song song nào cần được xem xét. Có ba chính sách thực hiện đã được xác định trong <execution> (20.19.2 [thực hiện]):

• std::execution::sequenced_policy (20.19.4 [execpol.seq]) với một đối tượng constexprstd::execution::seq (20.19.7 [parallel.execpol.objects ]) để chỉ ra việc thực thi tuần tự tương tự như gọi các thuật toán mà không có chính sách thực thi.
• std::execution::parallel_policy (20.19.5 [execpol.par]) với đối tượng constexprstd::execution::par (20.19.7 [parallel.execpol.objects]) để chỉ ra việc thực hiện các thuật toán có khả năng sử dụng nhiều chuỗi.
• std::execution::parallel_unsequenced_policy (20.19.6 [execpol.vec]) với đối tượng constexprstd::execution::par_unseq (20.19.7 [parallel.execpol.objects]) để chỉ ra việc thực hiện các thuật toán có khả năng sử dụng thực thi vectơ và/hoặc nhiều luồng.

Thuật toán STL thường lấy các đối tượng do người dùng xác định (trình lặp, đối tượng hàm) làm đối số. Những ràng buộc nào đối với các đối tượng do người dùng định nghĩa để làm cho chúng có thể sử dụng được với các thuật toán song song sử dụng các chính sách thực thi chuẩn?

Ví dụ: khi sử dụng một thuật toán như trong ví dụ bên dưới, hàm ý cho FwdIt và Predicate là gì?

template <typename FwdIt, typename Predicate> 
FwdIt call_remove_if(FwdIt begin, FwdIt end, Predicate predicate) { 
    return std::remove_if(std::execution::par, begin, end, predicate); 
} 

Answer 1

Câu trả lời ngắn gọn là các chức năng truy cập yếu tố (thực chất là các hoạt động theo yêu cầu của các thuật toán trên các đối số khác nhau, xem dưới đây để biết chi tiết) được sử dụng với các thuật toán sử dụng chính sách thực thi std::execution::parallel không được phép gây ra dữ liệu chủng tộc hoặc khóa chết. Các hàm truy cập phần tử được sử dụng với các thuật toán sử dụng chính sách thực hiện std::execution::parallel_unsequenced_policy cũng không thể sử dụng bất kỳ đồng bộ hóa chặn nào.

Chi tiết

Mô tả được dựa trên tài liệu lá phiếu N4604. Tôi đã không xác minh nếu một số điều khoản đã được sửa đổi để đáp ứng với ý kiến ​​cơ thể quốc gia (một kiểm tra cursory dường như ngụ ý rằng không có chỉnh sửa cho đến nay).

Phần 25.2 [thuật toán song song] chỉ định ngữ nghĩa của các thuật toán song song. Có rất nhiều khó khăn mà không áp dụng cho các thuật toán không dùng một chính sách thực thi, bị phá vỡ trong nhiều phần:

1. Trong 25.2.2 [algorithms.parallel.user] làm hạn chế những gì chức năng vị có thể làm để lập luận của họ : Tác phẩm

   Chức năng truyền vào các thuật toán song song như các đối tượng của loại Predicate, BinaryPredicate, Compare, và BinaryOperation sẽ không trực tiếp hoặc gián tiếp sửa đổi đối tượng thông qua lập luận của họ.

   Cách mệnh đề được viết có vẻ như các đối tượng tự thể được sửa đổi chừng nào những hạn chế khác (xem bên dưới) đều vâng lời. Lưu ý rằng ràng buộc này độc lập với chính sách thực thi và do đó, áp dụng ngay cả khi sử dụng std::execution::sequenced_policy. Câu trả lời đầy đủ phức tạp hơn và có vẻ như đặc điểm kỹ thuật hiện không chủ ý bị ràng buộc (xem đoạn cuối cùng bên dưới).

2. Trong 25.2.3 [algorithms.parallel.exec] thêm những hạn chế về chức năng truy cập yếu tố (xem dưới đây) mà là đặc trưng cho các chính sách thực hiện khác nhau:

   • Khi sử dụng std::execution::sequenced_policy các chức năng truy cập yếu tố tất cả được gọi từ cùng một luồng, nghĩa là, việc thực hiện không bị xen kẽ dưới bất kỳ hình thức nào.
   • Khi sử dụng std::execution::parallel_policy các luồng khác nhau có thể gọi hàm truy cập phần tử đồng thời từ các luồng khác nhau. Việc gọi các hàm truy cập phần tử từ các luồng khác nhau không được phép gây ra các cuộc đua dữ liệu hoặc gây ra các khóa chết. Tuy nhiên, các truy vấn truy cập phần tử từ cùng một luồng là chuỗi [không xác định], tức là, không có lời gọi xen kẽ nào của hàm truy cập phần tử từ cùng một luồng. Ví dụ: nếu một số Predicate được sử dụng với số std::execution::par đếm tần số được gọi, số lượng tương ứng sẽ cần phải được đồng bộ hóa một cách thích hợp.

   • Khi sử dụng std::execution::parallel_unsequenced_policy việc gọi hàm truy cập phần tử có thể được xen kẽ giữa cả hai luồng khác nhau cũng như trong một chuỗi thực thi. Nghĩa là, việc sử dụng nguyên gốc đồng bộ hóa chặn (như std::mutex) có thể gây ra khóa chết vì cùng một chuỗi có thể cố gắng đồng bộ hóa nhiều lần (và, ví dụ: cố gắng khóa cùng một lần nhiều lần). Khi sử dụng các hàm thư viện chuẩn cho các hàm truy cập phần tử, ràng buộc trong tiêu chuẩn là (25.2.3 [algorithm.parallel.exec] đoạn 4):

     Chức năng thư viện chuẩn là vector-không an toàn nếu được chỉ định để đồng bộ hóa với một lời gọi hàm khác, hoặc một lời gọi hàm khác được xác định để đồng bộ hóa với nó, và nếu nó không phải là cấp phát bộ nhớ hoặc chức năng deallocation. Chức năng thư viện chuẩn không chuẩn hóa có thể không được gọi bởi mã người dùng được gọi từ các thuật toán execution::parallel_unsequenced_policy.

   • Điều gì sẽ xảy ra khi sử dụng các chính sách thực thi được xác định thực hiện, không ngạc nhiên, việc triển khai được xác định.

3. Trong 25.2.4 [algorithm.parallel.exception] việc sử dụng các ngoại lệ ném từ chức năng truy cập phần tử được loại hạn chế: khi một chức năng truy cập yếu tố ném một ngoại lệ, std::terminate() được gọi. Đó là, nó là hợp pháp để ném một ngoại lệ nhưng nó không chắc rằng kết quả là mong muốn. Lưu ý rằng std::terminate() sẽ được gọi ngay cả khi sử dụng std::execution::sequenced_policy.

tử truy cập Chức năng

Các trở ngại trên sử dụng thuật ngữ yếu tố truy cập chức năng. Thuật ngữ này được định nghĩa trong 25.2.1 [algorithm.parallel.defns] đoạn 2.Có bốn nhóm chức năng được phân loại như các chức năng truy cập phần tử:

• Tất cả các hoạt động của các loại của vòng lặp rằng các thuật toán được khởi tạo với.
• Hoạt động trên các phần tử chuỗi được yêu cầu theo đặc điểm kỹ thuật của nó.
• Các đối tượng hàm do người dùng cung cấp sẽ được áp dụng trong quá trình thực hiện thuật toán, nếu được yêu cầu theo đặc điểm kỹ thuật.
• Hoạt động trên các đối tượng chức năng theo yêu cầu của đặc điểm kỹ thuật.

Về cơ bản, chức năng truy cập yếu tố là tất cả các hoạt động mà tiêu chuẩn đề cập rõ đến trong đặc tả của thuật toán hoặc các khái niệm sử dụng với các thuật toán. Các chức năng không được đề cập và, ví dụ, được phát hiện là có mặt (ví dụ: sử dụng SFINAE) không bị hạn chế và hiệu quả, không thể được gọi từ các thuật toán song song áp đặt các ràng buộc đồng bộ hóa khi sử dụng chúng.

Vấn đề

Nó là hơi liên quan mà có vẻ là không đảm bảo rằng các đối tượng chức năng truy cập [đột biến] phần tử được áp dụng cho rất khác nhau giữa các chủ đề khác nhau. Đặc biệt, tôi không thể thấy bất kỳ sự bảo đảm nào mà các phép toán vòng lặp được áp dụng cho một đối tượng iterator không thể được áp dụng cho cùng một đối tượng iterator từ hai luồng khác nhau! Hàm ý là, ví dụ: operator++() trên đối tượng trình lặp sẽ cần phải đồng bộ hóa trạng thái của nó bằng cách nào đó. Tôi không thể thấy cách, ví dụ: operator==() có thể làm điều gì đó hữu ích nếu đối tượng được sửa đổi trong một chuỗi khác. Dường như không chủ ý các hoạt động trên cùng một đối tượng cần phải được đồng bộ vì nó không có ý nghĩa gì khi áp dụng đồng thời các hàm truy cập phần tử [mutating] cho một đối tượng. Tuy nhiên, tôi không thể nhìn thấy bất kỳ văn bản nào nói rằng các đối tượng khác nhau được sử dụng (tôi đoán, tôi cần phải nâng cao một lỗi cho điều này).