Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Using Constraint Logic Programming to Schedule Solar Array Operations on the International Space Station Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

A GPU Implementation of the ASP Computation

verfasst von : Agostino Dovier, Andrea Formisano, Enrico Pontelli, Flavio Vella

Erschienen in: Practical Aspects of Declarative Languages

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

General Purpose Graphical Processing Units (GPUs) are affordable multi-core platforms, providing access to large number of cores, but at the price of a complex architecture with non-trivial synchronization and communication costs. This paper presents the design and implementation of a conflict-driven ASP solver, that is capable of exploiting the parallelism offered by GPUs. The proposed system builds on the notion of ASP computation, that avoids the generation of unfounded sets, enhanced by conflict analysis and learning. The proposed system uses the CPU exclusively for input and output, in order to reduce the negative impact of the expensive data transfers between the CPU and the GPU. All the solving components, i.e., the management of nogoods, the search strategy, backjumping, the search heuristics, conflict analysis and learning, and unit propagation, are performed on the GPU, by exploiting Single Instruction Multiple Threads (SIMT) parallelism. The preliminary experimental results confirm the feasibility and scalability of the approach, and the potential to enhance performance of ASP solvers.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel The KB Paradigm and Its Application to Interactive Configuration
Nächstes Kapitel The Picat-SAT Compiler
Literatur
1.
Balduccini, M., Pontelli, E., El-Khatib, O., Le, H.: Issues in parallel execution of non-monotonic reasoning systems. Parallel Comput. 31(6), 608–647 (2005)CrossRef
2.
Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, Cambridge (2010)MATH
3.
Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability (Frontiers in Artificial Intelligence and Applications), vol. 185. IOS Press, Amsterdam (2009)
4.
Campeotto, F., Dal Palù, A., Dovier, A., Fioretto, F., Pontelli, E.: Exploring the use of GPUs in constraint solving. In: Flatt, M., Guo, H.-F. (eds.) PADL 2014. LNCS, vol. 8324, pp. 152–167. Springer, Heidelberg (2014) CrossRef
5.
Campeotto, F., Dovier, A., Fioretto, F., Pontelli, E.: A GPU implementation of large neighborhood search for solving constraint optimization problems. In: Schaub, T., Friedrich, G., O’Sullivan, B. (eds.) ECAI 2014–21st European Conference on Artificial Intelligence - Including Prestigious Applications of Intelligent Systems (PAIS) 2014. Frontiers in Artificial Intelligence and Applications, vol. 263, pp. 189–194. IOS Press, Prague, Czech Republic (2014)
6.
Campeotto, F., Dovier, A., Pontelli, E.: A declarative concurrent system for protein structure prediction on GPU. J. Exp. Theor. Artif. Intell. (JETAI) 27(5), 503–541 (2015)CrossRef
7.
Dal Palù, A., Dovier, A., Formisano, A., Pontelli, E.: CUD@SAT: SAT solving on GPUs. J. Exp. Theor. Artif. Intell. (JETAI) 27(3), 293–316 (2015)CrossRef
8.
Dal Palù, A., Dovier, A., Pontelli, E., Rossi, G.: GASP: answer set programming with lazy grounding. Fundamenta Informaticae 96(3), 297–322 (2009)MathSciNetMATH
9.
Dovier, A., Formisano, A., Pontelli, E., Vella, F.: Parallel execution of the ASP computation - an investigation on GPUs. In: De Vos, M., Eiter, T., Lierler, Y., Toni, F. (eds.) Technical Communications of the 31st International Conference on Logic Programming (ICLP 2015), Cork, Ireland, August 31 - September 4, 2015, vol. 1433, CEUR Workshop Proceedings (2015). CEUR-WS.​org
10.
Fages, F.: Consistency of Clark’s completion and existence of stable models. Methods Logic Comput. Sci. 1(1), 51–60 (1994)
11.
Finkel, R.A., Marek, V.W., Moore, N., Truszczynski, M.: Computing stable models in parallel. In: Answer Set Programming, Towards Efficient and Scalable Knowledge Representation and Reasoning, Proceedings of the 1st International ASP 2001 Workshop, Stanford (2001)
12.
Formisano, A., Vella, F.: On multiple learning schemata in conflict driven solvers. In: Bistarelli, S., Formisano, A. (eds.) Proceedings of ICTCS 2014, vol. 1231, pp. 133–146. CEUR Workshop Proceedings, (2014). CEUR-WS.​org
13.
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Answer set solving in practice. Morgan & Claypool Publishers, San Rafael (2012)MATH
14.
Gebser, M., Kaufmann, B., Schaub, T.: Multi-threaded ASP solving with clasp. TPLP 12(4–5), 525–545 (2012)MathSciNetMATH
15.
Gelfond, M.: Answer sets. In: van Harmelen, F., Lifschitz, V., Porter, B.W. (eds.) Handbook of Knowledge Representation. Foundations of Artificial Intelligence, vol. 3, pp. 285–316. Elsevier, Amsterdam (2008)CrossRef
16.
17.
Järvisalo, M., Junttila, T.A., Niemelä, I.: Unrestricted vs restricted cut in a tableau method for boolean circuits. Ann. Math. Artif. Intell. 44(4), 373–399 (2005)MathSciNetCrossRefMATH
18.
Kao, M., Klein, P.N.: Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs. J. Comput. Syst. Sci. 47(3), 459–500 (1993)MathSciNetCrossRefMATH
19.
20.
21.
22.
Liu, L., Pontelli, E., Son, T.C., Truszczynski, M.: Logic programs with abstract constraint atoms: the role of computations. Artif. Intell. 174(3–4), 295–315 (2010)MathSciNetCrossRefMATH
23.
Manolios, P., Zhang, Y.: Implementing survey propagation on graphics processing units. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol. 4121, pp. 311–324. Springer, Heidelberg (2006) CrossRef
24.
Marek, V.W., Truszczynski, M.: Stable models and an alternative logic programming paradigm (1998). CoRR, cs.​LO/​9809032
25.
Marques-Silva, J.P., Sakallah, K.A.: GRASP: a search algorithm for propositional satisfiability. IEEE Trans. Comput. 48(5), 506–521 (1999)MathSciNetCrossRef
26.
Niemelä, I.: Logic programs with stable model semantics as a constraint programming paradigm. Ann. Math. Artif. Intell. 25(3–4), 241–273 (1999)CrossRefMathSciNetMATH
27.
28.
Perri, S., Ricca, F., Sirianni, M.: Parallel instantiation of ASP programs: techniques and experiments. TPLP 13(2), 253–278 (2013)MathSciNetMATH
29.
Cabalar, P.: Answer set; programming? In: Balduccini, M., Son, T.C. (eds.) Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning. LNCS, vol. 6565, pp. 334–343. Springer, Heidelberg (2011) CrossRef
30.
Pontelli, E., Le, H.V., Son, T.C.: An investigation in parallel execution of answer set programs on distributed memory platforms: task sharing and dynamic scheduling. Comput. Lang. Syst. Struct. 36(2), 158–202 (2010)
31.
Rossi, F., van Beek, P., Walsh, T.: Handbook of Constraint Programming. Foundations of Artificial Intelligence. Elsevier Science Inc., New York (2006) MATH
32.
Simons, P., Niemelä, I., Soininen, T.: Extending and implementing the stable model semantics. Artif. Intell. 138(1–2), 181–234 (2002)CrossRefMathSciNetMATH
33.
Syrjänen, T., Niemelä, I.: The smodels system. In: Eiter, T., Faber, W., Truszczyński, M. (eds.) LPNMR 2001. LNCS (LNAI), vol. 2173, pp. 434–438. Springer, Heidelberg (2001)
Metadaten
Titel
A GPU Implementation of the ASP Computation
verfasst von
Agostino Dovier
Andrea Formisano
Enrico Pontelli
Flavio Vella
Copyright-Jahr
2016
Buch
Practical Aspects of Declarative Languages

Print ISBN: 978-3-319-28227-5

Electronic ISBN: 978-3-319-28228-2

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-28228-2_3