Специализация алгоритма времени выполнения - Run-time algorithm specialization - Wikipedia

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

Psyco, специализированный компилятор времени выполнения для Python
многоступенчатое программирование

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

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