Hostname: page-component-8448b6f56d-sxzjt Total loading time: 0 Render date: 2024-04-19T15:52:48.463Z Has data issue: false hasContentIssue false
  • English
  • Français

Threads and or-parallelism unified

Published online by Cambridge University Press:  09 July 2010

VíTOR SANTOS COSTA ,
INÊS DUTRA  and
RICARDO ROCHA
VíTOR SANTOS COSTA
Affiliation:
CRACS and INESC-Porto LA, Faculty of Sciences, University of Porto Rua do Campo Alegre, 1021/1055, 4169-007 Porto, Portugal (e-mail: vsc@dcc.fc.up.pt, ines@dcc.fc.up.pt, ricroc@dcc.fc.up.pt)
INÊS DUTRA
Affiliation:
CRACS and INESC-Porto LA, Faculty of Sciences, University of Porto Rua do Campo Alegre, 1021/1055, 4169-007 Porto, Portugal (e-mail: vsc@dcc.fc.up.pt, ines@dcc.fc.up.pt, ricroc@dcc.fc.up.pt)
RICARDO ROCHA
Affiliation:
CRACS and INESC-Porto LA, Faculty of Sciences, University of Porto Rua do Campo Alegre, 1021/1055, 4169-007 Porto, Portugal (e-mail: vsc@dcc.fc.up.pt, ines@dcc.fc.up.pt, ricroc@dcc.fc.up.pt)
Get access Rights & Permissions [Opens in a new window]

Abstract

One of the main advantages of Logic Programming (LP) is that it provides an excellent framework for the parallel execution of programs. In this work we investigate novel techniques to efficiently exploit parallelism from real-world applications in low cost multi-core architectures. To achieve these goals, we revive and redesign the YapOr system to exploit or-parallelism based on a multi-threaded implementation. Our new approach takes full advantage of the state-of-the-art fast and optimized YAP Prolog engine and shares the underlying execution environment, scheduler and most of the data structures used to support YapOr's model. Initial experiments with our new approach consistently achieve almost linear speedups for most of the applications, proving itself as a good alternative for exploiting implicit parallelism in the currently available low cost multi-core architectures.

Keywords

multi-threadingor-parallelismimplementation
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 10 , Special Issue 4-6: 26th International Conference on Logic Programming , July 2010 , pp. 417 - 432
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ali, K. 1986. Or-parallel execution of Prolog on a multi-sequential machine. International Journal of Parallel Programming 15, 3, 189–214.CrossRefGoogle Scholar
Ali, K. and Karlsson, R. 1990a. Full prolog and scheduling OR-parallelism in muse. International Journal of Parallel Programming 19, 6, 445–475.CrossRefGoogle Scholar
Ali, K. and Karlsson, R. 1990b. The muse approach to OR-parallel prolog. International Journal of Parallel Programming 19, 2, 129–162.CrossRefGoogle Scholar
Carro, M. and Hermenegildo, M. V. 1999. Concurrency in prolog using threads and a shared database. In International Conference on Logic Programming. The MIT Press, 320–334.Google Scholar
Casas, A., Carro, M., and Hermenegildo, M. V. 2008. A high-level implementation of non-deterministic, unrestricted, independent and-parallelism. In International Conference on Logic Programming. Lecture Notes in Computer Science, vol. 5366. Springer, 651–666.CrossRefGoogle Scholar
Correia, M., Silva, F., and Santos Costa, V. 1997. The SBA: Exploiting orthogonality in and-or parallel systems. In International Logic Programming Symposium. MIT Press, 117–131.Google Scholar
Demoen, B., de la Banda, M. G., Mariott, K., Schachte, P., and Stuckey, P. 1998. Global Variables in HAL, a Logic Implementation. Technical report cw271, Department of Computer Science, K. U. Leuven.Google Scholar
Fonseca, N. A., Srinivasan, A., Silva, F. M. A., and Camacho, R. 2009. Parallel ILP for distributed-memory architectures. Machine Learning 74, 3, 257–279.Google Scholar
Gupta, G. and Pontelli, E. 1999. Stack Splitting: A Simple Technique for Implementing Or-parallelism on Distributed Machines. In International Conference on Logic Programming. MIT Press, 290–304.Google Scholar
Gupta, G., Pontelli, E., Ali, K., Carlsson, M., and Hermenegildo, M. V. 2001. Parallel execution of prolog programs: A survey. ACM Transactions on Programming Languages and Systems 23, 4, 472–602.CrossRefGoogle Scholar
Hermenegildo, M. V. and Greene, K. 1991. The &-prolog system: Exploiting independent and-parallelism. New Generation Computing 9, 3-4, 233–257.Google Scholar
Kovcs, L. 1992. An incremental prolog system development for the floor plan design by dissecting. In Proceedings of the International Conference on Practical Application of Prolog, vol. 1. 1–18.Google Scholar
Lusk, E., Butler, R., Disz, T., Olson, R., Overbeek, R., Stevens, R., Warren, D. H. D., Calderwood, A., Szeredi, P., Haridi, S., Brand, P., Carlsson, M., Ciepielewski, A., and Hausman, B. 1988. The Aurora or-parallel prolog system. In International Conference on Fifth Generation Computer Systems. Institute for New Generation Computer Technology, 819–830.Google Scholar
Marques, R., Swift, T., and Cunha, J. C. 2010. A simple and efficient implementation of concurrent local tabling. In International Symposium on Practical Aspects of Declarative Languages. Lecture Notes in Computer Science, vol. 5937. Springer, 264–278.CrossRefGoogle Scholar
Moura, P., Crocker, P., and Nunes, P. 2008. High-Level Multi-threading Programming in Logtalk. In International Symposium on Practical Aspects of Declarative Languages. Lecture Notes in Computer Science, vol. 4902. Springer, 265–281.CrossRefGoogle Scholar
Moura, P., Rocha, R., and Madeira, S. C. 2009. High level thread-based competitive or-parallelism in logtalk. In International Symposium on Practical Aspects of Declarative Languages. Lecture Notes in Computer Science, vol. 5418. Springer, 107–121.Google Scholar
Pontelli, E. and Gupta, G. 1997. Implementation mechanisms for dependent and-parallelism. In International Conference on Logic Programming. MIT Press, 123–137.CrossRefGoogle Scholar
Pontelli, E., Villaverde, K., Guo, H.-F., and Gupta, G. 2006. Stack splitting: A technique for efficient exploitation of search parallelism on share-nothing platforms. Journal of Parallel and Distributed Computing 66, 10, 1267–1293.CrossRefGoogle Scholar
Rocha, R., Silva, F., and Santos Costa, V. 1999. YapOr: An or-parallel prolog system based on environment copying. In Portuguese Conference on Artificial Intelligence. Lecture Notes in Artificial Intelligence, vol. 1695. Springer, 178–192.Google Scholar
Santos Costa, V. 1999. COWL: Copy-on-write for logic programs. In International Parallel Processing Symposium, Held Jointly with the Symposium on Parallel and Distributed Processing. IEEE Computer Society Press, 720–727.Google Scholar
Santos Costa, V. 2008. On supporting parallelism in a logic programming system. In Workshop on Declarative Aspects of Multicore Programming. 77–91.Google Scholar
Santos Costa, V., Rocha, R., and Silva, F. 2000. Novel models for or-parallel logic programs: A performance analysis. In EuroPar 2000 Parallel Processing. Lecture Notes in Computer Science, vol. 1900. Springer, 744–753.Google Scholar
Santos Costa, V., Warren, D. H. D., and Yang, R. 1991. Andorra-I: A parallel prolog system that transparently exploits both and- and or-parallelism. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM Press, 83–93.Google Scholar
Shen, K. 1992. Exploiting dependent and-parallelism in prolog: The dynamic dependent and-parallel scheme (DDAS). In Joint International Conference and Symposium on Logic Programming. MIT Press, 717–731.Google Scholar
Stevens, W. R. 1992. Advanced Programming in the UNIX Environment. Addison–Wesley.Google Scholar
Tick, E. 1987. Memory Performance of Prolog Architectures. Kluwer.CrossRefGoogle Scholar
Wielemaker, J. 2003. Native preemptive threads in SWI-Prolog. In International Conference on Logic Programming. Lecture Notes in Computer Science, vol. 2916. Springer, 331–345.Google Scholar