Parallel Constraint Logic Programming Language PARCS

PARCS is a declarative parallel constraint logic programming language that can deal with constraints over Herbrand universe and finite domains of integers like CHIP [Dincbas et al., '88]. To our knowledge, PARCS is the first CLP language to be thoroughly designed and implemented for high performance execution on modern distributed memory MPPs. PARCS exploits coarse grain parallelism that is derived from usual OR-parallelism and nondeterminism of instantiation of domain variables. Implementation techniques of PARCS for efficient execution on massively parallel processors include load balancing, branching method and compilation strategy based on extensive static analysis.

Example PARCS applications are cryptarithmetics, N-queens, paraffin and quasi-group problems. Compiler system of PARCS is currently running on real MPPs such as Fujitsu AP1000 (256 SPARC processors), Thinking Machines CM-5 (32 SPARC processors) and Intel Paragon XP/S (66 i860 processors). Single-node performance of PARCS compares with those of popular Prolog compilers, and good speedups have been achieved with respect to the number of processors.

Papers

Control in Parallel Constraint Logic Programming (PostScript file: size A4)

Naoki Kobayashi, Satoshi Matsuoka, and Akinori Yonezawa, in LPC'91, Tokyo, Japan, July, 1991.

PARCS: An MPP-Oriented CLP Language (PostScript file: size A4 letter)

KONNO Kazuhiro, NAGATSUKA Masaaki, KOBAYASHI Naoki, MATSUOKA Satoshi and YONEZAWA Akinori, in Proceedings of the First International Symposium on Parallel Symbolic Computation (PASCO'94), pp.254-263, World Scientific, Hagenberg/Linz, Austria, September 1994.

Back to Yonezawa Lab. Home Page....

Last modified: 12.15.'94

KONNO Kazuhiro / kaz@is.s.u-tokyo.ac.jp