"Parallel Execution Models for Constraint Propagation"
Los algoritmos de propagación de restricciones presentan paralelismo implícito. Cada restricción se comporta como un proceso concurrente disparado por cambios en el almacén de variables (store) y su ejecución provoca la modificación del almacén. Hemos desarrollado diferentes modelos de ejecución en paralelo de propagación de restricciones para máquinas MIMD de memoria distribuida. Hemos adoptado el esquema de indexicals, un enfoque adecuado para conseguir arco consistencia para restricciones funcionales n-arias. Los modelos propuestos emergen de dos técnicas para la planificación, estática y dinámica, de restricciones. En los modelos de planificación estática se divide el grafo en N particiones, que se ejecutan en paralelo en N procesadores. Discutimos un factor clave que afecta al rendimiento: el criterio para determinar la división del grafo para una carga de trabajo homogénea en tiempo de ejecución. En los modelos de planificación dinámica, cualquier procesador puede ejecutar cualquier restricción, mejora.
B.Baudot, Y.Deville, "Analysis of Distributed Arc-Consistency Algorithms", Tech. report 97-07, Univ. of Louvain, Belgium.