Paralellisation of Arc-Consistency Algorithms in a Centralised Memory Machine - Maria Clicia Stelling de Castro, Marluce R. Pereira, Inês C. Dutra (Cadernos do IME - Série Informática, 2013)
This work presents the parallelisation of the AC-5 arc-consistency algorithm for a centralised memory machine (Enterprise). We conducted our experiments using an adapted version of the PCSOS parallel constraint solving system, over finite domains. In the implementation for a centralised memory machine (CMM) we use synchronisation based on atomic read-modify-write primitives supported in hardware. We ran four benchmarks used by the original PCSOS to debug and assess the performance of the system. Our results show that arc-consistency algorithms have very good speedups on CMM systems. We implemented different kinds of partitioning for the constraints, and different kinds of distributed labeling. We showed that performance of the benchmarks are greatly affected by these kinds of partitioning and distributed labeling. One of our applications achieves superlinear speedups due to distributed labeling. Speedups for the centralised memory machine are better than for the original version. Our results still show that we have a great potential to improve performance. Better organisation of shared data structures, analysis of the constraint graph could lead to a better distribution of labeling and indexicals, as well as algorithm restructuring could help to improve performance.