Lập trình động song song

Question

Có giấy tờ hay nào thảo luận về cách thực hiện một chương trình động và song song nó không?

Answer 1

IIRC, những gì bạn thường làm với lập trình động là phân tích một cách đệ quy một vấn đề thành các vấn đề phụ và tập hợp các giải pháp tối ưu từ các giải pháp tối ưu. Điều gì làm cho nó có hiệu quả là tất cả các giải pháp tối ưu đều được tích hợp vào bộ đệm nên chúng không cần phải được tính toán lại.

Nếu vấn đề có thể được chia thành nhiều cách, bạn có thể chia người giải quyết cho mỗi lần giải thể. Nếu mỗi (phụ) vấn đề trung bình 1 + epsilon (đối với epsilon thú vị hơn 0) có thể subsolutions, sau đó bạn sẽ nhận được rất nhiều song song theo cách này. Có thể bạn sẽ cần khóa trên các mục trong bộ nhớ cache để bảo vệ các giải pháp riêng lẻ không bị xây dựng nhiều lần.

Bạn cần một ngôn ngữ mà bạn có thể nĩa các nhiệm vụ rẻ hơn công việc để giải quyết chúng và rất vui khi có nhiều tác vụ được chia đôi cùng một lúc. Các dịch vụ song song điển hình trong hầu hết các ngôn ngữ làm điều này một cách tồi tệ; bạn không thể có nhiều tác vụ được chia đôi trong các hệ thống sử dụng "mô hình ngăn xếp lớn" (xem How does a stackless language work?).

Chúng tôi đã triển khai ngôn ngữ lập trình song song của chúng tôi, PARLANSE, để có được một ngôn ngữ có thuộc tính phù hợp.

Answer 2

Gần đây, chúng tôi đã xuất bản một bài báo cho thấy cách song song với bất kỳ d.p. trên máy tính chia sẻ bộ nhớ đa lõi bằng bảng băm không có khóa được chia sẻ:

Stivala, A. và Stuckey, PJ và Garcia de la Banda, M. và Hermenegildo, M. và Wirth, A. 2010 "Khóa lập trình song song động miễn phí "J. Parallel Distrib. Tính toán. 70: 839-848 doi: 10,1016/j.jpdc.2010.01.004

http://dx.doi.org/10.1016/j.jpdc.2010.01.004

Về cơ bản, bạn bắt đầu nhiều chủ đề, tất cả chạy cùng mã bắt đầu từ giá trị của d.p. bạn muốn tính toán, tính toán từ trên xuống (đệ quy), và ghi nhớ trong bảng băm không khóa, nhưng ngẫu nhiên thứ tự các bài toán con được tính toán sao cho các luồng phân tách trong đó các toán con mà chúng tính toán. Về mặt thực hiện, chúng tôi chỉ sử dụng C và pthread trên hệ thống kiểu UNIX, tất cả những gì bạn cần là có thể chia sẻ bộ nhớ, và CompareAndSwap (CAS) cho đồng bộ hóa không khóa giữa các luồng.

Vì bài báo này đã được xuất bản trong một tạp chí Elsevier, bạn sẽ cần phải truy cập ở trên thông qua thư viện Đại học hoặc tương tự với đăng ký với nó. Bạn có thể nhận được một bản in trước thông qua trang web của Giáo sư Stuckey.