Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/20943
Title: Parallel execution of constraint handling rules - Theory, implementation and application
Authors: LAM SOON LEE, EDMUND
Keywords: constraint, parallelism, concurrency, programming languages, concurrent semantics, multiset rewriting
Issue Date: 6-Jul-2010
Source: LAM SOON LEE, EDMUND (2010-07-06). Parallel execution of constraint handling rules - Theory, implementation and application. ScholarBank@NUS Repository.
Abstract: Constraint Handling Rules (CHR) is a concurrent committed choice rule based programming language designed specifically for the implementation of incremental constraint solvers. Over the recent years, CHR has become increasingly popular primarily because of it?s high-level and declarative nature, allowing a large number of problems to be concisely implemented in CHR. The abstract CHR semantics essentially involves multi-set rewriting over a multi-set of constraints. This computational model is highly concurrent as theoretically rewriting steps over non-overlapping multi-sets of constraints can execute concurrently. Most intriguingly, this would allow for the possibility for implementations of CHR solvers with highly parallel execution models. Yet despite of this, to date there is little or no existing research work that investigates into a parallel execution model and implementation of CHR. Further more, parallelism is going mainstream and we can no longer rely on super-scaling with single processors, but must think in terms of parallel programming to scale with symmetric multi-processors (SMP). In this thesis, we introduce a concurrent goal-based execution model for CHR. Following this, we introduce a parallel implementation of CHR in Haskell, based on this concurrent goal-based execution model. We demonstrate the scalability of this implementation with empirical results. In addition, we illustrate a non-trivial application of our work, known as HaskellJoin, an extension of the popular high-level concurrency abstraction Join Patterns, with CHR guards and propagation.
URI: http://scholarbank.nus.edu.sg/handle/10635/20943
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
LamSLE.pdf1.48 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

427
checked on Dec 11, 2017

Download(s)

308
checked on Dec 11, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.