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

Реализация процедур прогнозирования трудоемкости параллельного решения SAT-задач

Тип публикации: Материал конференции

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

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

Журнал: Тр. Междунар. конф. "Параллельные вычисл. технологии" (Уфа, 29 марта-2 апреля 2010 г.)

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

Номера страниц: 163-174

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

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

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

Издательство: Издат. центр ЮУрГУ

Местоположение издательства: Челябинск

Адрес издателя: Челябинск

Название издательства: Издат. центр ЮУрГУ

Аннотация: Разработана и реализована в виде MPI-программы крупноблочная параллельная технология решения SAT-задач (задач поиска решений уравнений вида «КНФ = 1», где КНФ - конъюнктивная нормальная форма) в распределенных вычислительных средах. В рамках данной технологии осуществляется декомпозиция исходной SAT-задачи на семейство подзадач. Используется процедура статистического прогнозирования трудоемкости параллельного решения SAT-задач, которая позволяет определить оптимальные (по прогнозу) параметры декомпозиции. Использование параметров декомпозиции, найденных с помощью процедур прогнозирования, позволяет успешно решать SAT-задачи, кодирующие задачи обращения ряда криптографических дискретных функций.

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

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

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

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

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

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