Институт системного программирования им. В.П. Иванникова РАН


Об эквивалентности потоковых программ.

Авторы

Захаров В.А.

Аннотация

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

Ключевые слова

потоковая программа, реактивная программа, проблема эквивалентности

Издание

Материалы XI Международного семинара «Дискретная математика и ее приложения», посвященного 80-летию со дня рождения академика О.Б. Лупанова (Москва, МГУ, 18-23 июня 2012 г.), 2014, Изд-во механико-математического ф-та МГУ Москва, с. 119-121.

Научная группа

Теоретическая информатика

Все публикации за 2014 год Все публикации