Especialización de algoritmos en tiempo de ejecución

En informática , la especialización de algoritmos en tiempo de ejecución es una metodología para crear algoritmos eficientes para tareas de computación costosas de ciertos tipos. Esta metodología tiene su origen en el campo de la demostración automática de teoremas y, más específicamente, en el proyecto del demostrador de teoremas Vampire .

La idea está inspirada en el uso de la evaluación parcial en la optimización de la traducción de programas. Muchas operaciones centrales en los demostradores de teoremas exhiben el siguiente patrón. Supongamos que necesitamos ejecutar algún algoritmo.${\displaystyle {\mathit {alg}}(A,B)}$en una situación donde un valor de${\displaystyle A}$está fijo para potencialmente muchos valores diferentes de${\displaystyle B}$Para hacerlo de manera eficiente, podemos intentar encontrar una especialización de${\displaystyle {\mathit {alg}}}$para cada fijo${\displaystyle A}$, es decir, dicho algoritmo${\displaystyle {\mathit {alg}}_{A}}$, que ejecutar${\displaystyle {\mathit {alg}}_{A}(B)}$es equivalente a ejecutar${\displaystyle {\mathit {alg}}(A,B)}$.

El algoritmo especializado puede ser más eficiente que el genérico, ya que puede aprovechar algunas propiedades particulares del valor fijo.${\displaystyle A}$. Normalmente,${\displaystyle {\mathit {alg}}_{A}(B)}$puede evitar algunas operaciones que${\displaystyle {\mathit {alg}}(A,B)}$tendrían que funcionar, si se sabe que son redundantes para este parámetro en particular.${\displaystyle A}$. En particular, a menudo podemos identificar algunas pruebas que son verdaderas o falsas para${\displaystyle A}$, desenrollar bucles y recursión, etc.

La diferencia clave entre la especialización en tiempo de ejecución y la evaluación parcial es que los valores de${\displaystyle A}$en el cual${\displaystyle {\mathit {alg}}}$Las especializaciones no se conocen de forma estática, por lo que la especialización tiene lugar en tiempo de ejecución .

También existe una importante diferencia técnica. La evaluación parcial se aplica a algoritmos representados explícitamente como códigos en algún lenguaje de programación. En tiempo de ejecución, no necesitamos ninguna representación concreta de${\displaystyle {\mathit {alg}}}$Solo tenemos que imaginarlo .${\displaystyle {\mathit {alg}}}$Cuando programamos el procedimiento de especialización, todo lo que necesitamos es una representación concreta de la versión especializada.${\displaystyle {\mathit {alg}}_{A}}$Esto también significa que no podemos utilizar ningún método universal para especializar algoritmos, como suele ocurrir con la evaluación parcial. En su lugar, tenemos que programar un procedimiento de especialización para cada algoritmo en particular.${\displaystyle {\mathit {alg}}}$Una ventaja importante de hacerlo es que podemos usar algunos trucos ad hoc poderosos que explotan peculiaridades de${\displaystyle {\mathit {alg}}}$y la representación de${\displaystyle A}$y${\displaystyle B}$, que están más allá del alcance de cualquier método de especialización universal.

El algoritmo especializado debe representarse de forma que pueda interpretarse.

En muchas situaciones, generalmente cuando${\displaystyle {\mathit {alg}}_{A}(B)}$debe calcularse sobre muchos valores de${\displaystyle B}$en fila,${\displaystyle {\mathit {alg}}_{A}}$se puede escribir como instrucciones de código máquina para una máquina abstracta especial , y normalmente se dice que${\displaystyle A}$se compila . El código en sí puede optimizarse adicionalmente mediante transformaciones que preservan la respuesta y que se basan únicamente en la semántica de las instrucciones de la máquina abstracta.

Las instrucciones de la máquina abstracta generalmente se pueden representar como registros . Un campo de dicho registro, un identificador de instrucción (o etiqueta de instrucción ), identifica el tipo de instrucción; por ejemplo, se puede usar un campo entero , con valores enteros específicos que corresponden a instrucciones específicas. Otros campos se pueden usar para almacenar parámetros adicionales de la instrucción; por ejemplo, un campo de puntero puede apuntar a otra instrucción que representa una etiqueta, si la semántica de la instrucción requiere un salto. Todas las instrucciones del código se pueden almacenar en una estructura de datos iterable , como un arreglo , una lista enlazada o un árbol .

La interpretación (o ejecución ) se lleva a cabo obteniendo las instrucciones en un orden determinado, identificando su tipo y ejecutando las acciones asociadas a dicho tipo.

En muchos lenguajes de programación, como C y C++ , se puede usar una switchinstrucción simple para asociar acciones con diferentes identificadores de instrucción. Los compiladores modernos suelen compilar una switchinstrucción con etiquetas constantes (por ejemplo, enteras) de un rango estrecho almacenando la dirección de la instrucción correspondiente a un valor.${\displaystyle i}$en el${\displaystyle i}$-ésima celda de una matriz especial, como medio de optimización eficiente. Esto se puede aprovechar tomando valores para los identificadores de instrucciones de un pequeño intervalo de valores.

Hay situaciones en las que se dan muchos casos de${\displaystyle A}$están destinados al almacenamiento a largo plazo y las llamadas de${\displaystyle {\mathit {alg}}(A,B)}$ocurren con diferentes${\displaystyle B}$en un orden impredecible. Por ejemplo, es posible que tengamos que comprobar${\displaystyle {\mathit {alg}}(A_{1},B_{1})}$primero, luego${\displaystyle {\mathit {alg}}(A_{2},B_{2})}$, entonces${\displaystyle {\mathit {alg}}(A_{1},B_{3})}$y así sucesivamente. En tales circunstancias, la especialización a gran escala con compilación puede no ser adecuada debido al uso excesivo de memoria. Sin embargo, a veces podemos encontrar una representación especializada compacta.${\displaystyle A^{\prime }}$ por cada${\displaystyle A}$, que se pueden almacenar con, o en lugar de,${\displaystyle A}$También definimos una variante${\displaystyle {\mathit {alg}}^{\prime }}$que trabaja en esta representación y cualquier llamado a${\displaystyle {\mathit {alg}}(A,B)}$es reemplazado por${\displaystyle {\mathit {alg}}^{\prime }(A^{\prime },B)}$, diseñado para hacer el mismo trabajo más rápido.

• Psyco , un compilador especializado en tiempo de ejecución para Python.
• programación multietapa

• A. Voronkov, "La anatomía del vampiro: implementación de procedimientos ascendentes con árboles de código", Journal of Automated Reasoning , 15(2), 1995 ( idea original )

• A. Riazanov y A. Voronkov , "Verificación eficiente de restricciones de ordenación de términos", Proc. IJCAR 2004, Lecture Notes in Artificial Intelligence 3097, 2004 ( ilustración compacta pero autocontenida del método ).
• A. Riazanov y A. Voronkov, Recuperación eficiente de instancias con indexación de rutas estándar y relacionales , Information and Computation , 199(1-2), 2005 ( contiene otra ilustración del método )
• A. Riazanov, "Implementación de un demostrador de teoremas eficiente" , tesis doctoral, Universidad de Manchester, 2003 ( contiene la descripción más completa del método y muchos ejemplos ).