Моделирование и сложность поиска в многопроцессорных системах

При программировании поиска для многопроцессорных систем существует как минимум два подхода. Первый (сепаративный) подход предполагает разделение данных между процессорами (исполнителями) и дальнейшую независимую обработку каждым исполнителем своей части данных. Второй (кооперативный) подход предполагает совместное владение данными и совместную обработку. В работе предлагается математическая модель параллельных алгоритмов поиска и в рамках этой модели исследуется параллельное решение задач поиска с отношением поиска, являющимся отношением линейного квазипорядка. Описан способ оптимального разделения данных при использовании сепаративного подхода для данной задачи и показано, что в общем случае сепаративный подход не дает оптимального решения, то есть приведен пример таких задач поиска с отношением линейного квазипорядка, для которых кооперативный подход дает лучшие результаты.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты 95–01–00597 и 98–01–00130.