DATA-PARALLEL CONCURRENT CONSTRAINT PROGRAMMING

With the advent of cost-effective massively parallel computers, resear chers conjecture that the future concurrent constraint programming sys tem is composed of a massively parallel constraint solver as the back- end with a concurrent inference engine as the front-end (Cohen, Comm, ACM 33 (7) (1990) 52-68). This paper represents, to the best of our kn owledge, the first attempt to build a concurrent constraint programmin g system on a massively parallel SIMD computer. A concurrent constrain t programming language called Firebird is presented. Firebird can hand le finite domain constraints and supports both concurrency and data-pa rallelism. As a result, it is suitable for implementation on both mult iprocessors and SIMD computers, Concurrency arises from the stream and -parallelism of committed-choice logic programmining languages. Our SI MD implementation supports or-parallelism but stream and parallelism i s implemented sequentially. In a nondeterministic derivation step, one of the domain variables is selected to create a choice point. All pos sible alternatives are attempted in parallel. Data-parallelism is expl oited in the resulting or-parallel execution. In this paper, we first present the Firebird computation model. We then present an SIMD implem entation of the Firebird language on the DECmpp massively parallel com puter based on the data-parallel abstract machine (DPAM). A performanc e analysis of the system is also presented. (C) 1998 Elsevier Science Inc. All rights reserved.