Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Препринт ИПМ № 70, Москва, 2013 г.
Авторы: Гречаник С. А., Ключников И. Г., Романенко С. А.
Стадированная многорезультатная суперкомпиляция: фильтрация результатов до их порождения
Аннотация:
В случае применения суперкомпиляции в области решения задач, многорезультатная суперкомпиляция позволяет обнаруживать наилучшие решения благодаря тому, что порождается некоторое множество возможных остаточных графов конфигураций, которое затем фильтруется в соответствии с некоторыми критериями. К сожалению, пространство поиска при этом может получаться весьма обширным. Однако, мы показываем, что можно значительно уменьшить объем поиска разложив процесс многорезультатной суперкомпиляции в композицию из двух стадий. На первой стадии порождается компактное представление множества остаточных графов, которое получается в результате задержки некоторых операций по построению графов. Эти операции выполняются на второй стадии, когда компактное представление интерпретируется, в результате чего и генерируется множество графов. Основная идея предлагаемого подхода состоит в том, что вместо фильтрации множества графов можно выполнять анализ и чистку его компактного представления. Во многих случаях, представляющих практический интерес (таких, как отбор графов минимального размера или отбрасывание графов, содержащих ненадежные конфигурации) чистка может быть выполнена за линейное время.
Ключевые слова:
Суперкомпиляция, многорезультатная суперкомпиляция, стадирование
Язык публикации: английский, страниц: 28
Направление исследований:
Программирование, параллельные вычисления, мультимедиа
Полный текст: Сведения об авторах:
  • Гречаник Сергей Александрович,  ,  ИПМ им. М.В. Келдыша РАН
  • Ключников Илья Григорьевич,  ,  ИПМ им. М.В. Келдыша РАН
  • Романенко Сергей Анатольевич,  orcid.org/0000-0002-2971-9647,  ИПМ им. М.В. Келдыша РАН