Сотрудники :: Гасанов Эльяр Эльдарович :: Публикации Гасанова Э.Э.

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

Э.Э.Гасанов, Е.P.Ерохина
Московский государственный университет

Скачать статью полностью в формате PDF (300 кб): modelir.pdf
Для просмотра Вам понадобится Adobe Acrobat Reader 4.x-5.x

Резюме.

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

Дискретная математика (1999) 11, N 3

Наверх