Parallel execution of multi-set constraint rewrite rules

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel execution of multi-set constraint rewrite rules

Full text

Pdf (470 KB)

Source

International Conference on Principles and Practice of Declarative Programming archive
Proceedings of the 10th international ACM SIGPLAN conference on Principles and practice of declarative programming table of contents

Valencia, Spain

SESSION: Concurrency & parallelism table of contents

Pages 20-31

Year of Publication: 2008

ISBN:978-1-60558-117-0

Authors

Martin Sulzmann	IT University of Copenhagen, Copenhagen, Denmark
Edmund S. L. Lam	National University of Singapore, Singapore

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 40, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1389449.1389453 What is a DOI?

ABSTRACT

Multi-set constraint rewriting allows for a highly parallel computational model and has been used in a multitude of application domains such as constraint solving, agent specification etc. Rewriting steps can be applied simultaneously as long as they do not interfere with each other.We wish that the underlying constraint rewrite implementation executes rewrite steps in parallel on increasingly popular becoming multi-core architectures. We design and implement efficient algorithms which allow for the parallel execution of multi-set constraint rewrite rules. Our experiments show that we obtain some significant speed-ups on multi-core architectures

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. Abdennadher. Operational semantics and confluence of constraint propagation rules. In Proc. of CP¿97, LNCS, pages 252--266. Springer-Verlag, 1997.
	2	G. J. Duck. Compilation of Constraint Handling Rules. PhD thesis, The University of Melbourne, 2005.
	3	G. J. Duck, P. J. Stuckey, M. J. García de la Banda, and C. Holzbaur. The refined operational semantics of Constraint Handling Rules. In Proc of ICLP'04, volume 3132 of LNCS, pages 90--104. Springer-Verlag, 2004.
	4	C. Forgy. A fast algorithm for the many patterns/many objects match problem. Artificial Intelligence, 19(1):17--37, 1982.
	5	T. Frühwirth. Theory and practice of constraint handling rules. Journal of Logic Programming, Special Issue on Constraint Logic Programming, 37(1-3):95--138, 1998.
	6	T. Frühwirth. Parallelizing union-find in Constraint Handling Rules using confluence analysis. In Proc. of ICLP'05, volume 3668 of LNCS, pages 113--127. Springer-Verlag, 2005.
	7	Thom Frühwirth, Constraint handling rules: the story so far, Proceedings of the 8th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.13-14, July 10-12, 2006, Venice, Italy [doi>10.1145/1140335.1140337]
	8	Glasgow haskell compiler home page. http://www.haskell.org/ghc/.
	9	A. Gupta , C. Forgy , A. Newell , R. Wedig, Parallel algorithms and architectures for rule-based systems, Proceedings of the 13th annual international symposium on Computer architecture, p.28-37, June 02-05, 1986, Tokyo, Japan
	10	Christian Holzbaur , Maria Garcia De La Banda , Peter J. Stuckey , Gregory J. Duck, Optimizing compilation of constraint handling rules in HAL, Theory and Practice of Logic Programming, v.5 n.4-5, p.503-531, July 2005 [doi>10.1017/S1471068405002413]
	11	T. Ishida, Parallel Rule Firing in Production Systems, IEEE Transactions on Knowledge and Data Engineering, v.3 n.1, p.11-17, March 1991 [doi>10.1109/69.75883]
	12	Leslie De Koninck , Tom Schrijvers , Bart Demoen, User-definable rule priorities for CHR, Proceedings of the 9th ACM SIGPLAN international conference on Principles and practice of declarative programming, July 14-16, 2007, Wroclaw, Poland [doi>10.1145/1273920.1273924]
	13	L. De Koninck, P.J. Stuckey, and G.J. Duck. Optimizing compilation of CHR with rule priorities. In Proc. of FLOPS'08, 2008. To appear.
	14	The K.U. Leuven CHR System. http://www.cs.kuleuven.be/~toms/Research/CHR.
	15	Edmund S. L. Lam , Martin Sulzmann, A concurrent constraint handling rules implementation in Haskell with software transactional memory, Proceedings of the 2007 workshop on Declarative aspects of multicore programming, p.19-24, January 16-16, 2007, Nice, France [doi>10.1145/1248648.1248653]
	16	Simon Marlow , Tim Harris , Roshan P. James , Simon Peyton Jones, Parallel generational-copying garbage collection with a block-structured heap, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA [doi>10.1145/1375634.1375637]
	17	C. Perfumo, N. Sonmez, O. S. Unsal, A. Cristal, M. Valero, and T. Harris. Dissecting transactional executions in Haskell. In The Second ACM SIGPLAN Workshop on Transactional Computing (TRANSACT), 2007.
	18	T. Schrijvers. Analyses, optimizations and extensions of Constraint Handling Rules: Ph.D. summary. In Proc. of ICLP'05, volume 3668 of LNCS, pages 435--436. Springer-Verlag, 2005.
	19	M. Stahl. Implementing CHR with STM, March 2007. personal communication.
	20	P. Van Weert, T. Schrijvers, and B. Demoen. K.U.Leuven JCHR: a user-friendly, flexible and efficient CHR system for Java. In Proc. of Second Workshop on Constraint Handling Rules, pages 47--62, 2005.