nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Constraint Solving on Hybrid Systems

verfasst von : Pedro Roque, Vasco Pedro

Erschienen in: Declarative Programming and Knowledge Management

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Applying parallelism to constraint solving seems a promising approach and it has been done with varying degrees of success. Early attempts to parallelize constraint propagation, which constitutes the core of traditional interleaved propagation and search constraint solving, were hindered by its essentially sequential nature. Recently, parallelization efforts have focussed mainly on the search part of constraint solving, as well as on local-search based solving. Lately, a particular source of parallelism has become pervasive, in the guise of GPUs, able to run thousands of parallel threads, and they have naturally drawn the attention of researchers in parallel constraint solving.

In this paper, we address challenges faced when using multiple devices for constraint solving, especially GPUs, such as deciding on the appropriate level of parallelism to employ, load balancing and inter-device communication, and present our current solutions.

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

Nächstes Kapitel Run-Time Analysis of Temporal Constrained Objects

Intel MICs are coprocessors that combine many Intel processor cores onto a single chip with dedicated RAM.

If a device takes less than one second to explore a block of search spaces, most of that time is spent communicating with the host and initializing its data structures.

A CUDA core is a processing element capable of executing one integer or floating instruction per clock for a thread.

Arbelaez, A., Codognet, P.: A GPU implementation of parallel constraint-based local search. In: 2014 22nd Euromicro International Conference on PDP, pp. 648–655. IEEE (2014)

Barták, R., Salido, M.A.: Constraint satisfaction for planning and scheduling problems. Constraints 16(3), 223–227 (2011)MathSciNetCrossRef

Brailsford, S., Potts, C., Smith, B.: Constraint satisfaction problems: algorithms and applications. Eur. J. Oper. Res. 119, 557–581 (1999)CrossRef

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, Cham (2014). https://doi.org/10.1007/978-3-319-04132-2_11CrossRef

Chu, G., Schulte, C., Stuckey, P.J.: Confidence-based work stealing in parallel constraint programming. In: Gent, I.P. (ed.) CP 2009. LNCS, vol. 5732, pp. 226–241. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04244-7_20CrossRef

Diaz, D., Richoux, F., Codognet, P., Caniou, Y., Abreu, S.: Constraint-based local search for the costas array problem. In: Hamadi, Y., Schoenauer, M. (eds.) LION 2012. LNCS, pp. 378–383. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34413-8_31CrossRef

Filho, C., Rocha, D., Costa, M., Albuquerque, P.: Using constraint satisfaction problem approach to solve human resource allocation problems in cooperative health services. Expert Syst. Appl. 39(1), 385–394 (2012)CrossRef

Gaster, B., Howes, L., Kaeli, D., Mistry, P., Schaa, D.: Heterogeneous Computing with OpenCL. Morgan Kaufmann Publishers Inc., San Francisco (2011)

Jefferson, C., Miguel, I., Hnich, B., Walsh, T., Gent, I.P.: CSPLib: a problem library for constraints (1999). http://www.csplib.org

10.

Jenkins, J., Arkatkar, I., Owens, J.D., Choudhary, A., Samatova, N.F.: Lessons learned from exploring the backtracking paradigm on the GPU. In: Jeannot, E., Namyst, R., Roman, J. (eds.) Euro-Par 2011. LNCS, vol. 6853, pp. 425–437. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23397-5_42CrossRef

11.

Mairy, J.-B., Deville, Y., Lecoutre, C.: Domain k-wise consistency made as simple as generalized arc consistency. In: Simonis, H. (ed.) CPAIOR 2014. LNCS, vol. 8451, pp. 235–250. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07046-9_17CrossRef

12.

MIT: a suite of minizinc benchmarks (2017). https://github.com/MiniZinc/minizinc-benchmarks

13.

Munshi, A., Gaster, B., Mattson, T.G., Fung, J., Ginsburg, D.: OpenCL Programming Guide, 1st edn. Addison-Wesley Professional, Boston (2011)

14.

Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.: MiniZinc: towards a standard CP modelling language. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 529–543. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74970-7_38CrossRef

15.

NVIDIA Corporation: NVIDIA GeForce GTX 980 featuring maxwell, the most advanced GPU ever made. White paper. NVIDIA Corporation (2014)

16.

Pedro, V.: Constraint programming on hierarchical multiprocessor systems. Ph.D. thesis, Universidade de Évora (2012)

17.

Pedro, V., Abreu, S.: Distributed work stealing for constraint solving. In: Vidal, G., Zhou, N.F. (eds.) CICLOPS-WLPE 2010, Edinburgh, Scotland, U.K. (2010)

18.

Rolf, C.C., Kuchcinski, K.: Load-balancing methods for parallel and distributed constraint solving. In: 2008 IEEE International Conference on Cluster Computing, pp. 304–309, September 2008

19.

Rolf, C.C., Kuchcinski, K.: Parallel solving in constraint programming. In: MCC 2010, November 2010

20.

Régin, J.-C., Rezgui, M., Malapert, A.: Embarrassingly parallel search. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 596–610. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40627-0_45CrossRef

21.

Schulte, C.: Parallel search made simple. In: Beldiceanu, N., et al. (eds.) Proceedings of TRICS: CP 2000, Singapore, September 2000

22.

Schulte, C., Duchier, D., Konvicka, F., Szokoli, G., Tack, G.: Generic constraint development environment. http://www.gecode.org/

Titel: Constraint Solving on Hybrid Systems
verfasst von: Pedro Roque
Vasco Pedro
Verlag: Springer International Publishing
Buch: Declarative Programming and Knowledge Management
Print ISBN: 978-3-030-00800-0

Electronic ISBN: 978-3-030-00801-7

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-00801-7_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"