Probabilistic cost analysis of logic programs

Análisis de costo probabilístico de programas lógicos

Se han desarrollado análisis de costos de programas lógicos para obtener automáticamente cotas superiores e inferiores delcosto del tiempo de ejecución de dicho tipo de programas. Esta información es muy útil para una variedad de propósitos,incluyendo control de granularidad, optimización de consultas en bases de datos, y transformación de programas y síntesis.Sin embargo, las técnicas actuales carecen de exactitud en algunos casos que son bastante representativos (por ejemplo,algunos programas de dividir para reinar como Quicksort). Este artículo describe un enfoque probabilístico alternativoque hace posible obtener una estimación más precisa del costo de ejecución. Una de sus ventajas es que plantea sólo unospocos cambios sobre los esquemas propuestos previamente.

INTRODUCCIÓN

El coste de la computación es, en general, una medida de los recursos que una computación necesita consumir para proceder satisfactoriamente. Las medidas de coste habituales son el tiempo, los pasos de cálculo, la memoria utilizada y otras. En este trabajo nos ocuparemos (de forma algo abstracta) de los costes que aumentan monotónicamente con la ejecución, ejemplificados por el tiempo / número de pasos de cálculo. La información sobre el coste de ejecución de los cálculos puede ser útil para diversas aplicaciones. Por ejemplo, es útil para la programación de tareas y el control de la granularidad (es decir, el control dinámico de la creación de hilos/procesos) en la ejecución paralela [14, 3, 17, 11, 15, 13], la transformación de programas, la optimización de consultas en bases de datos [2], la seguridad con conocimiento de los recursos en el código móvil [9, 8], y para demostrar que un programa cumple con estrictas restricciones de tiempo en los sistemas de tiempo real.

En el contexto de la programación lógica, los trabajos sobre estimación de costes se han centrado generalmente en el análisis de costes de límites superiores [4] o inferiores [6]. Una deficiencia importante de estas aproximaciones a la estimación de costes es su pérdida de precisión en presencia del caso frecuente de los programas "divide y vencerás" en los que los tamaños de los argumentos de salida de la parte "divide" no son independientes. En el conocido programa QuickSort (véase la figura 1), por ejemplo, dado que cualquiera de las salidas del predicado partition/4 se alimenta de nuevo como lista de entrada a qsort/2, el enfoque de análisis de costes de límites superiores [4] funciona bajo la suposición de que ambas salidas pueden ser simultáneamente la lista de entrada completa, con lo que se sobreestima significativamente el coste del programa QuickSort (en la sección "Lack of Tightness in Some Upper Bounds" se explica con más detalle por qué ocurre esto).