Идеи для студента проекта параллельного программирования

Question

Я хочу сделать проект параллельного программирования на C (возможно, с использованием pthreads или, возможно, OpenMP) для класса. Это будет сделано группой из примерно четырех студентов, и должно занять около 4 недель. Я подумал, что было бы интересно атаковать какую-то NP-полную задачу с помощью более сложного алгоритма, такого как генетический алгоритм с имитацией отжига, но я не уверен, что это будет достаточно большой проект.

Кто-нибудь знал о каких-нибудь классных проблемах, которые могли бы выиграть от параллельного подхода?

Answer 1

Я помню «учебный» проект в нашем университете по распараллеливанию алгоритмов отсечения альфа-бета. Сама альфа-бета-обрезка не слишком сложна и имеет довольно большую сложность. Если вы распараллелите его, вам нужно будет установить некоторую сигнализацию / обмен данными, чтобы действительно выиграть от распараллеливания. В противном случае некоторые потоки слишком часто или слишком глубоко уходят в ветки, которые другие потоки уже сочли слишком плохими. Я думаю, что это может быть хорошим вариантом использования.