On parallelization of asymptotically optimal dualization algorithms

Основной целью работы является разработка и реализация подхода к построению эффективных параллельных алгоритмов для труднорешаемых перечислительных задач и демонстрация этого подхода на примере одной из центральных перечислительных задач — задачи дуализации. Из известных алгоритмов дуализации наиболее быстрыми являются асимптотически оптимальные алгоритмы. Эти алгоритмы имеют теоретическое обоснование эффективности «в среднем». Поскольку число решений дуализации растет экспоненциально с ростом размера входа, актуальным является использование параллельных вычислений. В статье предложена статическая схема распараллеливания асимптотически оптимальных алгоритмов дуализации и осуществлено ее тестирование. Проведена статистическая обработка экспериментов с целью определения вида распределения случайной величины, определяющей объемы подзадач. Выявлены условия, при которых схема демонстрирует ускорение, близкое к максимальному, и достаточно равномерную загрузку процессоров.