Mảng đa mảng được đa luồng?

Question

Tôi có một cấu trúc dữ liệu trong đó bao gồm 1.000 phần tử mảng, mỗi phần tử mảng là một mảng nhỏ của 8 ints:

std::array<std::array<int, 8>, 1000> 

Cấu trúc dữ liệu chứa hai "con trỏ", mà theo dõi các phần tử mảng lớn nhất và nhỏ dân cư (trong mảng "bên ngoài", 1000 phần tử). Vì vậy, ví dụ: họ có thể là:

min = 247 
max = 842 

Làm cách nào để đọc và ghi vào cấu trúc dữ liệu này từ nhiều chủ đề? Tôi lo lắng về điều kiện chủng tộc giữa các yếu tố đẩy/popping và duy trì hai "con trỏ". Chế độ hoạt động cơ bản của tôi là:

// Pop element from current index 
// Calculate new index 
// Write element to new index 
// Update min and max "pointers" 

Answer 1

Bạn đúng là thuật toán hiện tại của bạn không an toàn, có một số nơi tranh chấp có thể xảy ra.

Điều này là không thể tối ưu hóa mà không có thêm thông tin. Bạn cần phải biết nơi mà sự chậm lại đang xảy ra trước khi bạn có thể cải thiện nó - và cho rằng bạn cần số liệu. Lập hồ sơ cho mã của bạn và tìm ra bit nào thực sự lấy thời gian, bởi vì bạn chỉ có thể đạt được bằng cách song song các bit đó và thậm chí sau đó bạn có thể thấy rằng nó thực sự là bộ nhớ hay cái gì đó khác là yếu tố giới hạn chứ không phải CPU.

Cách tiếp cận đơn giản nhất sẽ là khóa toàn bộ cấu trúc cho toàn bộ quá trình. Điều này sẽ chỉ làm việc nếu các chủ đề đang làm rất nhiều chế biến khác là tốt, nếu không bạn sẽ thực sự mất hiệu suất so với luồng đơn.

Sau đó, bạn có thể xem xét có khóa riêng cho các phần khác nhau của cấu trúc dữ liệu. Bạn sẽ cần phải phân tích chính xác những gì bạn đang sử dụng khi nào và ở đâu và làm việc ra những gì sẽ hữu ích để phân chia. Ví dụ bạn có thể có khối của mảng phụ với mỗi đoạn có khóa riêng của nó.

Hãy cẩn thận về các trường hợp chết trong tình huống này, bạn có thể có yêu cầu 32, sau đó muốn 79 trong khi một chuỗi khác đã có 79 và sau đó muốn 32. Đảm bảo bạn luôn yêu cầu khóa theo cùng thứ tự.

Tùy chọn nhanh nhất (nếu có thể) thậm chí có thể cung cấp cho mỗi luồng bản sao riêng cấu trúc dữ liệu, mỗi quy trình 1/N của tác phẩm và sau đó hợp nhất các kết quả ở cuối. Bằng cách này, không cần đồng bộ hóa trong quá trình xử lý.

Nhưng một lần nữa, tất cả trở lại các số liệu và lược tả. Đây không phải là một vấn đề đơn giản.