Страница публикации

Неполные алгоритмы в крупноблочном параллелизме комбинаторных задач

Тип публикации: Статья в журнале

Тип материала: Текст

Авторы: Семенов А.А., Заикин О.С.

Журнал: Вычисл. методы и программирование

Язык публикации: russian

Том: 9

Номера страниц: 112–122

Количество страниц: 11

Номер: 1

Год публикации: 2008

Отчетный год: 2008

Аннотация: Для некоторых типов NP-трудных комбинаторных задач исследуются технологии поиска их решений посредством неполных алгоритмов, т.е. алгоритмов, конечность работы которых в общем случае не гарантируется. Речь идет об алгоритмах "программирования в ограничениях", использующих в своей работе идею пополнения базы ограничений с отбрасыванием нерелевантных ограничений. Сравниваются два подхода к решению ряда комбинаторных задач посредством неполных алгоритмов. Основой первого подхода является крупноблочное распараллеливание исходной задачи с последующим решением получаемых задач неполным алгоритмом на кластере. Во втором подходе исходная задача решается на одном процессора кластера (фактически на ПК) тем же самым алгоритмом. Показано, что в ряде случаев коэффициент ускорения, которое достигается в первом подходе, может существенно превосходить число процессоров кластера.

Индексируется WOS: Нет

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Да

Индексируется ВАК: Нет

Индексируется CORE: Нет