×

Table space designs for implicit and explicit concurrent tabled evaluation. (English) Zbl 1452.68035

Summary: One of the main advantages of Prolog is its potential for the implicit exploitation of parallelism and, as a high-level language, Prolog is also often used as a means to explicitly control concurrent tasks. Tabling is a powerful implementation technique that overcomes some limitations of traditional Prolog systems in dealing with recursion and redundant sub-computations. Given these advantages, the question that arises is if tabling has also the potential for the exploitation of concurrency/parallelism. On one hand, tabling still exploits a search space as traditional Prolog but, on the other hand, the concurrent model of tabling is necessarily far more complex, since it also introduces concurrency on the access to the tables. In this paper, we summarize Yap’s main contributions to concurrent tabled evaluation and we describe the design and implementation challenges of several alternative table space designs for implicit and explicit concurrent tabled evaluation that represent different trade-offs between concurrency and memory usage. We also motivate for the advantages of using fixed-size and lock-free data structures, elaborate on the key role that the engine’s memory allocator plays on such environments, and discuss how Yap’s mode-directed tabling support can be extended to concurrent evaluation. Finally, we present our future perspectives toward an efficient and novel concurrent framework which integrates both implicit and explicit concurrent tabled evaluation in a single Prolog engine.

MSC:

68N17 Logic programming
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alba, E.; Almeida, F.; Blesa, M. J.; Cabeza, J.; Cotta, C.; Dí-Az, M.; Dorta, I.; Gabarró, J.; León, C.; Luna, J.; Moreno, L. M.; Pablos, C.; Petit, J.; Rojas, A.; Xhafa, F., (2002)
[2] Ali, K.; Karlsson, R., The muse approach to OR-parallel prolog, International Journal of Parallel Programming, 19, 2, 129-162, (1990) · doi:10.1007/BF01407834
[3] Areias, M.; Rocha, R., On combining linear-based strategies for tabled evaluation of logic programs, Journal of Theory and Practice of Logic Programming, International Conference on Logic Programming, Special Issue, 11, 4-5, 681-696, (2011) · Zbl 1222.68051
[4] Areias, M.; Rocha, R., International Conference on Parallel and Distributed Systems, An efficient and scalable memory allocator for multithreaded tabled evaluation of logic programs, 636-643, (2012), IEEE Computer Society
[5] Areias, M.; Rocha, R., Towards multi-threaded local tabling using a common table space, Journal of Theory and Practice of Logic Programming, International Conference on Logic Programming, Special Issue, 12, 4-5, 427-443, (2012) · Zbl 1260.68056
[6] Areias, M.; Rocha, R., Batched evaluation of linear tabled logic programs, Journal of Computer Science and Information Systems, Special Issue on Advances in Model Driven Engineering, Languages and Agents, 10, 4, 1775-1797, (2013)
[7] Areias, M.; Rocha, R.; Flatt, M.; Guo, H.-F., (2014)
[8] Areias, M.; Rocha, R., (2015)
[9] Areias, M.; Rocha, R., A lock-free hash trie design for concurrent tabled logic programs, International Journal of Parallel Programming, 44, 3, 386-406, (2016) · doi:10.1007/s10766-014-0346-1
[10] Areias, M.; Rocha, R., On scaling dynamic programming problems with a multithreaded tabling system, Journal of Systems and Software, 125, 417-426, (2017) · doi:10.1016/j.jss.2016.06.060
[11] Bagwell, P., (2001)
[12] Berger, E. D.; Mckinley, K. S.; Blumofe, R. D.; Wilson, P. R., Hoard: A scalable memory allocator for multithreaded applications, ACM SIGPLAN Notices, 35, 11, 117-128, (2000) · doi:10.1145/356989.357000
[13] Blumofe, R. D.; Joerg, C. F.; Kuszmaul, B. C.; Leiserson, C. E.; Randall, K. H.; Zhou, Y., Cilk: An efficient multithreaded runtime system, SIGPLAN Not., 30, 8, 207-216, (1995) · doi:10.1145/209937.209958
[14] Carro, M.; Hermenegildo, M. V., (1999)
[15] Chapman, B.; Jost, G.; Van Der Pas, R., Using OpenMP: Portable Shared Memory Parallel Programming, (2008), The MIT Press
[16] Chen, W.; Warren, D. S., Tabled evaluation with delaying for general logic programs, Journal of the ACM, 43, 1, 20-74, (1996) · Zbl 0882.68050 · doi:10.1145/227595.227597
[17] Chico, P.; Carro, M.; Hermenegildo, M. V.; Silva, C.; Rocha, R., (2008)
[18] Costa, J.; Raimundo, J.; Rocha, R., (2009)
[19] Cruz, F.; Rocha, R., (2010)
[20] Desouter, B.; Van Dooren, M.; Schrijvers, T., Tabling as a library with delimited control, Journal of Theory and Practice of Logic Programming, 15, 4-5, 419-433, (2015) · Zbl 1379.68054 · doi:10.1017/S1471068415000137
[21] Evans, J., (2006)
[22] Fonseca, N. A.; Srinivasan, A.; Silva, F. M. A.; Camacho, R., Parallel ILP for distributed-memory architectures, Machine Learning, 74, 3, 257-279, (2009) · doi:10.1007/s10994-008-5094-2
[23] Fredkin, E., Trie memory, Communications of the ACM, 3, 490-499, (1962)
[24] Freire, J.; Swift, T.; Warren, D. S., (1996)
[25] Ghemawat, S.; Menage, P., (2014)
[26] Gidenstam, A.; Papatriantafilou, M.; Tsigas, P., NB: Allocating memory in a lock-free manner, Algorithmica, 58, 2, 304-338, (2010) · Zbl 1204.68044 · doi:10.1007/s00453-008-9268-x
[27] Gloger, W., (2014)
[28] Guo, H.-F.; Gupta, G., (2001)
[29] Gupta, G.; Pontelli, E., (1999)
[30] Gupta, G.; Pontelli, E.; Ali, K.; Carlsson, M.; Hermenegildo, M. V., Parallel execution of prolog programs: A survey, ACM Transactions on Programming Languages and Systems, 23, 4, 472-602, (2001) · doi:10.1145/504083.504085
[31] Herlihy, M.; Wing, J. M., (1987)
[32] Hermenegildo, M. V.; Greene, K., The &-prolog system: Exploiting independent and-parallelism, New Generation Computing, 9, 3-4, 233-257, (1991) · doi:10.1007/BF03037164
[33] Herrmann, C. A.; Lengauer, C., HDC: A higher-order language for divide-and-conquer, Parallel Processing Letters, 10, 2-3, 239-250, (2000) · doi:10.1142/S0129626400000238
[34] Johnson, E.; Ramakrishnan, C. R.; Ramakrishnan, I. V.; Rao, P., (1999)
[35] Knuth, D. E., The Art of Computer Programming, volume 3: (2nd ed.) Sorting and Searching, (1998), Addison-Wesley Longman · Zbl 0895.68054
[36] Kumar, V., Introduction to Parallel Computing, (2002), Addison-Wesley
[37] Kumar, V.; Grama, A.; Gupta, A.; Karypis, G., Introduction to Parallel Computing: Design and Analysis of Algorithms, (1994), Benjamin-Cummings Publishing Co., Inc. · Zbl 0861.68040
[38] Liang, S.; Fodor, P.; Wan, H.; Kifer, M., (2009)
[39] Loogen, R.; Ortega-Mallén, Y.; Peña-Marí, R., Parallel functional programming in Eden, Journal of Functional Programming, 15, 3, 431-475, (2005) · Zbl 1096.68018 · doi:10.1017/S0956796805005526
[40] 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.; Hausman, B., (1988)
[41] Marques, R.; Swift, T., (2008)
[42] Marques, R.; Swift, T.; Cunha, J. C., (2010)
[43] Martello, S.; Toth, P., Knapsack Problems: Algorithms and Computer Implementations, (1990), John Wiley and Sons · Zbl 0708.68002
[44] Masmano, M.; Ripoll, I.; Crespo, A., (2006)
[45] Moura, P., (2008)
[46] Peláez, I.; Almeida, F.; Suárez, F., (2007)
[47] Pontelli, E.; Gupta, G., (1997)
[48] Ramakrishnan, I. V.; Rao, P.; Sagonas, K.; Swift, T.; Warren, D. S., Efficient access mechanisms for tabled logic programs, Journal of Logic Programming, 38, 1, 31-54, (1999) · Zbl 0911.68033 · doi:10.1016/S0743-1066(98)10013-4
[49] Rao, P.; Ramakrishnan, C. R.; Ramakrishnan, I. V., (1996)
[50] Reinders, J., Intel Threading Building Blocks, (2007), O’Reilly & Associates, Inc.: O’Reilly & Associates, Inc., Sebastopol, CA, USA
[51] Rocha, R.; Silva, F.; Santos, Costa, V., (1999)
[52] Rocha, R.; Silva, F.; Santos, Costa, V., (2001)
[53] Rocha, R.; Silva, F.; Santos Costa, V., On applying or-parallelism and tabling to logic programs, Theory and Practice of Logic Programming, 5, 1-2, 161-205, (2005) · Zbl 1093.68021 · doi:10.1017/S1471068404002030
[54] Sagonas, K.; Swift, T., An abstract machine for tabled execution of fixed-order stratified logic programs, ACM Transactions on Programming Languages and Systems, 20, 3, 586-634, (1998) · doi:10.1145/291889.291897
[55] Saha, D., (2006)
[56] Santos, J.; Rocha, R., (2013)
[57] Santos, Costa, V.; Rocha, R.; Damas, L., The YAP prolog system, Journal of Theory and Practice of Logic Programming, 12, 1-2, 5-34, (2012) · Zbl 1244.68017 · doi:10.1017/S1471068411000512
[58] Santos, Costa, V.; Warren, D. H. D.; Yang, R., (1991)
[59] Shen, K., (1992)
[60] Somogyi, Z.; Sagonas, K., (2006)
[61] Stivala, A.; Stuckey, P.; De La Banda, M. G.; Hermenegildo, M.; Wirth, A., Lock-free parallel dynamic programming, Journal of Parallel and Distributed Computing, 70, 8, 839-848, (2010) · Zbl 1233.68225 · doi:10.1016/j.jpdc.2010.01.004
[62] Swift, T.; Warren, D. S., XSB: Extending prolog with tabled logic programming, Theory and Practice of Logic Programming, 12, 1-2, 157-187, (2012) · Zbl 1244.68021 · doi:10.1017/S1471068411000500
[63] Tenenbaum, A. M.; Langsam, Y.; Augenstein, M. J., Data Structures Using C, (1990), Prentice Hall
[64] Zhou, N.-F., The language features and architecture of B-Prolog, Journal of Theory and Practice of Logic Programming, 12, 1-2, 189-218, (2012) · Zbl 1244.68024 · doi:10.1017/S1471068411000445
[65] Zhou, N.-F.; Kjellerstrand, H.; Fruhman, J., Constraint Solving and Planning with Picat, (2015), Springer
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.