Специализация по алгоритмам времени выполнения

В информатике . специализация алгоритмов времени выполнения — это методология создания эффективных алгоритмов для дорогостоящих вычислительных задач определенного рода Методология берет свое начало в области автоматизированного доказательства теорем , а точнее, в проекте доказательства теорем Vampire .

Идея основана на использовании частичной оценки при оптимизации перевода программы. Многие основные операции в средствах доказательства теорем демонстрируют следующую закономерность.Предположим, что нам нужно выполнить некоторый алгоритм ${\mathit {alg}}(A,B)$ в ситуации, когда значение $A$ фиксируется для потенциально многих различных значений $B$. Чтобы сделать это эффективно, мы можем попытаться найти специализацию ${\mathit {alg}}$ за каждое фиксированное $A$, т. е. такой алгоритм ${\mathit {alg}}_{A}$, что выполнение ${\mathit {alg}}_{A}(B)$ эквивалентно выполнению ${\mathit {alg}}(A,B)$.

Специализированный алгоритм может быть более эффективным, чем общий, поскольку он может использовать некоторые конкретные свойства фиксированного значения. $A$. Обычно ${\mathit {alg}}_{A}(B)$ можно избежать некоторых операций, которые ${\mathit {alg}}(A,B)$ пришлось бы выполнять, если бы было известно, что они избыточны для этого конкретного параметра $A$. В частности, мы часто можем определить некоторые тесты, которые являются истинными или ложными для $A$, циклы развертывания и рекурсия и т. д.

Отличие от частичной оценки

Ключевое различие между специализацией во время выполнения и частичной оценкой заключается в том, что значения $A$ на котором ${\mathit {alg}}$ является специализированным, не известны статически, поэтому специализация происходит во время выполнения .

Есть и важное техническое отличие. Частичная оценка применяется к алгоритмам, явно представленным в виде кодов на каком-либо языке программирования. Во время выполнения нам не нужно какое-либо конкретное представление ${\mathit {alg}}$. Нам остается только представить ${\mathit {alg}}$ когда мы программируем процедуру специализации.Все, что нам нужно, это конкретное представление специализированной версии. ${\mathit {alg}}_{A}$. Это также означает, что мы не можем использовать какие-либо универсальные методы специализации алгоритмов, что обычно имеет место при частичном вычислении. Вместо этого нам нужно запрограммировать процедуру специализации для каждого конкретного алгоритма. ${\mathit {alg}}$. Важным преимуществом этого является то, что мы можем использовать некоторые мощные специальные приемы, использующие особенности ${\mathit {alg}}$ и представление $A$ и $B$, которые недоступны никаким универсальным методам специализации.

Специализация по компиляции

Специализированный алгоритм должен быть представлен в форме, которую можно интерпретировать.Во многих ситуациях, обычно когда ${\mathit {alg}}_{A}(B)$ должен вычисляться по многим значениям $B$ подряд мы можем написать ${\mathit {alg}}_{A}$ как код особой абстрактной машины , и мы часто говорим, что $A$ компилируется ​ . Тогда сам код можно дополнительно оптимизировать с помощью сохраняющих ответ преобразований, опирающихся только на семантику инструкций абстрактной машины.

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

Интерпретация осуществляется путем выборки инструкций в определенном порядке с определением их типа.и выполнение действий, связанных с этим типом. В C или C++ мы можем использовать оператор переключения для связи некоторые действия с разными тегами инструкций. Современные компиляторы обычно довольно эффективно компилируют оператор переключения с целочисленными метками из узкого диапазона, сохраняя адрес оператора, соответствующий значению. $i$ в $i$-я ячейка специального массива. Это можно использоватьвзяв значения для тегов инструкций из небольшого интервала целых чисел.

Специализация в области данных и алгоритмов

Бывают ситуации, когда много случаев $A$ предназначены для длительного хранения и вызова ${\mathit {alg}}(A,B)$ происходят с разными $B$ в непредсказуемом порядке.Например, нам может потребоваться проверить ${\mathit {alg}}(A_{1},B_{1})$ сначала, потом ${\mathit {alg}}(A_{2},B_{2})$, затем ${\mathit {alg}}(A_{1},B_{3})$, и так далее.В таких обстоятельствах полномасштабная специализация с компиляцией может оказаться непригодной из-за чрезмерного использования памяти. Однако иногда можно найти компактное специализированное представление $A^{\prime }$для каждого $A$, который может храниться с или вместо $A$. Мы также определяем вариант ${\mathit {alg}}^{\prime }$ это работает в этом представлении и любой вызов ${\mathit {alg}}(A,B)$ заменяется на ${\mathit {alg}}^{\prime }(A^{\prime },B)$, предназначенный для выполнения той же работы быстрее.

См. также

• Psyco — специализированный компилятор времени выполнения для Python.
• многоэтапное программирование

Ссылки

• А. Воронков, «Анатомия вампира: реализация восходящих процедур с помощью деревьев кодов», Journal of Automated Reasoning , 15(2), 1995 ( оригинальная идея )

Дальнейшее чтение

• Рязанов А., Воронков А. А. , "Эффективная проверка ограничений упорядочивания терминов", Учеб. IJCAR 2004, Конспекты лекций по искусственному интеллекту 3097, 2004 ( компактная, но самодостаточная иллюстрация метода )
• А. Рязанов и А. Воронков, Эффективный поиск экземпляров с индексацией стандартных и реляционных путей , Информация и вычисления , 199(1-2), 2005 ( содержит еще одну иллюстрацию метода )
• Рязанов А., «Реализация эффективного средства доказательства теорем» , кандидатская диссертация, Манчестерский университет, 2003 г. ( содержит наиболее полное описание метода и множество примеров )