Làm thế nào nhanh chóng có thể 'tìm kiếm tối đa trong một mảng' có thể nhận được?

Question

Câu hỏi này xuất phát từ một cuộc thảo luận đã được đề cập đến trong câu hỏi khác này: Parallelize already linear-time algorithm. Đó là không phải là bài tập về nhà.

Bạn được cung cấp một dãy số N và máy có bộ vi xử lý P và bộ nhớ chia sẻ CREW (đọc đồng thời, bộ nhớ ghi độc quyền).

các chặt chẽtrên ràng buộc trên thuật toán nhanh nhất để tìm số lớn nhất trong mảng là gì? [Rõ ràng, cũng là: thuật toán là gì?]

Tôi không đề cập đến tổng số công việc đã thực hiện [có thể không bao giờ là nhỏ hơn O (N)].

Answer 1

Tôi nghĩ rằng đó là O(N/P') + O(Log2(P')), trong đó P'=min{N,P}. Bộ vi xử lý P' tìm kiếm max trong số N/P' phần tử, tiếp theo là Log2 kết hợp cặp song song được thực hiện song song. Việc kết hợp P'/2 đầu tiên được thực hiện bởi bộ xử lý được đánh số chẵn, tiếp theo 'P'/4 '- bởi các bộ xử lý tại các vị trí chia hết cho 8, sau đó là 16, v.v.

Chỉnh sửaP' được giới thiệu để bao gồm trường hợp khi bạn có nhiều nút xử lý đáng kể hơn so với các phần tử bạn cần tìm kiếm.

Answer 2

Tôi nghi ngờ điều này là O (N/P) + O (P)

• Chia sẻ công việc giữa các bộ xử lý P có một chi phí O (P)
• kết hợp công việc được thực hiện bởi bộ xử lý P có cũng tốn O (P)
• Một tìm kiếm parallell hoàn hảo của N mục bằng cách xử lý P có chi phí thời gian O (N/P)

thuật toán ngây thơ của tôi sẽ được

• ghi mục 0 vào một tế bào CREW nhãn "kết quả"
• bắt đầu P tìm kiếm hoàn toàn độc lập, mỗi thông qua 1/P thứ của các mục N
• sau khi hoàn thành mỗi spinloop sử dụng tìm kiếm CAS để thay thế "kết quả" với kết quả tìm kiếm một phần, nếu nó lớn hơn. (Tùy thuộc vào định nghĩa của bạn về CREW bạn có thể không cần spinloop)

Answer 3

Cook, Dwork và Reischuk cho thấy rằng mọi thuật toán CREW để tìm tối đa n phần tử phải chạy trong thời gian Omega (lg n), thậm chí với số bộ xử lý không hạn chế và bộ nhớ không giới hạn. Nếu tôi nhớ chính xác, thuật toán có giới hạn trên phù hợp xuất hiện trên giấy của họ:

Stephen Cook, Cynthia Dwork và Rüdiger Reischuk. Giới hạn trên và dưới cho các máy truy cập ngẫu nhiên song song mà không cần ghi đồng thời. Tạp chí SIAM về Tin học, 15 (1): 87-97, 1986.

Answer 4

Sau đây là tối ưu bound:

Nếu p < = n/log n bạn có thể làm điều đó trong thời gian O (n/p) thời gian; nếu không thì đó là O (log n) tức là khi p> n/log n bạn không đạt được gì so với p = n/log n.

Proof - thấp hơn ràng buộc:

yêu cầu bồi thường 1: Bạn không bao giờ có thể làm nhanh hơn Ω (n/p), bởi vì vi xử lý p có thể đưa ra chỉ tăng tốc của p

yêu cầu bồi thường 2: Bạn không bao giờ có thể làm nhanh hơn hơn Ω (log n), bởi vì mô hình CREW (xem giấy không xác định); nếu bạn muốn kiểm tra nếu một mảng 0-1 có ít nhất một 1, bạn cần thời gian O (log n).

Proof - trên ràng buộc:

yêu cầu bồi thường 3: Bạn có thể tìm tối đa sử dụng n/log xử lý n và trong thời gian O (log n) thời gian

Proof: Nó rất dễ dàng để tìm tối đa sử dụng bộ vi xử lý n và log n thời gian; nhưng trên thực tế, trong thuật toán này hầu hết các bộ xử lý hầu như không hoạt động; bằng cách thích hợp, (xem ví dụ: sách phức tạp của Papadimitriou) số của chúng có thể được hạ xuống n/log n.

---

Bây giờ, được đưa ra ít hơn n/log n vi xử lý bạn có thể cho công việc được giao để xử lý K tới 1 bộ xử lý, điều này chia yêu cầu xử lý bởi K và nhân lên thời gian theo yêu cầu của K.

Hãy K = (n/log n)/p; thuật toán trước chạy trong thời gian O (K log n) = O (n/p), và yêu cầu n/(log n * K) = p bộ vi xử lý.

---

được sửa đổi: Tôi chỉ nhận ra rằng khi p < = n/log n, thuật toán dasblinkenlight vừa thể hiện cùng một thời gian chạy tiệm cận:

n/p + log p < = n/p + log (n/log n) < = n/p + log n < = n/p + n/p < = 2n/p = O (n/p)

để bạn có thể sử dụng thuật toán có độ phức tạp O (n/p) khi p < = n/log n và O (log n) nếu không.

Answer 5

Đối với P = N^2, đó là O (1).

Tất cả khởi tạo mảng Boolean CannotBeMax [i] = FALSE

Proc (i, j) đặt CannotBeMax [i] = A [i] < A [j]

Max là A [CannotBeMax [i ] == FALSE]

Lưu ý rằng tất cả các bài viết đồng thời cố gắng viết thông tin giống nhau để câu trả lời nhất quán cho dù thành công nào.