Automatic Constraint Partitioning to Speed Up CLP Execution

• Marluce Rodrigues Pereira UFLA
• Patricia Kayser Vargas Centro Universitário La Salle
• Maria Clicia Stelling de Castro UERJ
• Felipe M. G. Franca UFRJ
• Inas de Castro Dutra UFRJ

Abstract

Speedup in distributed executions of Constraint Logic Programming (CLP) applications are directed related to a good constraint partitioning algorithm. In this work we study different mechanisms to distribute constraints to processors based on straightforward mechanisms such as Round-Robin and Block distribution, and on a more sophisticated automatic distribution method, Grouping-Sink, that takes into account the connectivity of the constraint network graph. This aims at reducing the communication overhead in distributed environments. Our results show that Grouping-Sink is, in general, the best alternative for partitioning constraints as it produces results as good or better than Round-Robin or Blocks with low communication rate.

Keywords: High performance computing, Partitioning algorithms, Computer architecture, Distributed computing, Logic programming, Round robin, Time factors, Concurrent computing, Processor scheduling, Testing