Ý tưởng cho dự án lập trình song song của sinh viên

Question

Tôi đang tìm cách thực hiện một dự án lập trình song song trong C (có thể sử dụng pthreads hoặc có thể OpenMP) cho một lớp. Nó sẽ được thực hiện bởi một nhóm khoảng bốn sinh viên, và sẽ mất khoảng 4 tuần. Tôi đã nghĩ rằng sẽ rất thú vị khi tấn công một số vấn đề NP-hoàn chỉnh với một thuật toán phức tạp hơn như một algo di truyền với mô phỏng ủ, nhưng tôi không chắc chắn nếu nó sẽ là một dự án đủ lớn.

Bất kỳ ai biết về bất kỳ vấn đề nào có thể hưởng lợi từ một cách tiếp cận song song?

Answer 1

Tôi nhớ dự án 'học tập' tại trường đại học của chúng tôi về việc song song các thuật toán cắt xén alpha-beta. Bản cắt tỉa Alpha-beta không quá phức tạp và có độ phức tạp khá lớn. Nếu bạn song song nó, bạn sẽ cần phải cài đặt một số tín hiệu/chia sẻ dữ liệu để thực sự hưởng lợi từ việc song song. Nếu không một số chủ đề sẽ đi quá thường xuyên hoặc quá sâu vào các chi nhánh đã được coi là quá xấu bởi các chủ đề khác. Tôi nghĩ rằng đó có thể là một trường hợp sử dụng tốt.