nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Featherlight Speculative Task Parallelism

verfasst von : Vivek Kumar

Erschienen in: Euro-Par 2019: Parallel Processing

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

Speculative task parallelism is a widely used technique for solving search based irregular computations such as graph algorithms. Here, tasks are created speculatively to traverse different search spaces in parallel. Only a few of these tasks succeed in finding the solution, after which the remaining tasks are canceled. For ensuring timely cancellation of tasks, existing frameworks either require programmer introduced cancellation checks inside every method in the call chain, thereby hurting the productivity, or provide limited parallel performance.

In this paper we propose Featherlight, a new programming model for speculative task parallelism that satisfies the serial elision property and doesn’t require any task cancellation checks. We show that Featherlight improves productivity through a classroom-based study. Further, to support Featherlight, we present the design and implementation of a task cancellation technique that exploits runtime mechanisms already available within managed runtimes and achieves a geometric mean speedup of 1.6\(\times \) over the popular Java ForkJoin framework on a 20 core machine.

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 Graph Coloring Using GPUs

Nächstes Kapitel One Table to Count Them All: Parallel Frequency Estimation on Single-Board Computers

Destroying threads in C#. https://docs.microsoft.com/en-us/dotnet/standard/threading/destroying-threads. Accessed Feb 2019

Documentation on The Python standard library. https://docs.python.org/3/library/concurrent.futures.html. Accessed Feb 2019

OpenMP API, version 4.5. http://www.openmp.org/wp-content/uploads/openmp-4.5.pdf. Accessed Feb 2019

Scala scheduler. https://doc.akka.io/docs/akka/snapshot/scheduler.html?language=scala. Accessed Feb 2019

Oracle docs, February 2019. https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ExecutorService.html

Productivity analysis, February 2019. https://www.usebackpack.com/iiitd/m2018/cse000

Alpern, B., et al.: The Jalapeño virtual machine. IBM Syst. J. 39(1), 211–238 (2000). https://doi.org/10.1147/sj.391.0211CrossRef

Blackburn, S.M., et al.: The DaCapo benchmarks: Java benchmarking development and analysis. In: OOPSLA, pp. 169–190 (2006). https://doi.org/10.1145/1167473.1167488

Charles, P., et al.: X10: an object-oriented approach to non-uniform cluster computing. In: OOPSLA, pp. 519–538 (2005). https://doi.org/10.1145/1094811.1094852

10.

Frigo, M., Leiserson, C.E., Randall, K.H.: The implementation of the Cilk-5 multithreaded language. In: PLDI, pp. 212–223 (1998). https://doi.org/10.1145/277650.277725

11.

Grama, A., Kumar, V., Gupta, A., Karypis, G.: Introduction to Parallel Computing. Pearson Education, Upper Saddle River (2003)MATH

12.

Imam, S., Sarkar, V.: Habanero-Java library: a Java 8 framework for multicore programming. In: PPPJ, pp. 75–86 (2014). https://doi.org/10.1145/2647508.2647514

13.

Imam, S., Sarkar, V.: The Eureka programming model for speculative task parallelism. In: ECOOP, vol. 37, pp. 421–444 (2015). https://doi.org/10.4230/LIPIcs.ECOOP.2015.421

14.

Kolesnichenko, A., Nanz, S., Meyer, B.: How to cancel a task. In: Lourenço, J.M., Farchi, E. (eds.) MUSEPAT 2013. LNCS, vol. 8063, pp. 61–72. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39955-8_6CrossRef

15.

Kumar, V.: Featherlight implementation (2019). https://github.com/hipec/featherlight/archive/d60047a.tar.gz

16.

Kumar, V., Blackburn, S.M., Grove, D.: Friendly barriers: efficient work-stealing with return barriers. In: VEE, pp. 165–176 (2014). https://doi.org/10.1145/2576195.2576207

17.

Kumar, V., Dolby, J., Blackburn, S.M.: Integrating asynchronous task parallelism and data-centric atomicity. In: PPPJ, pp. 7:1–7:10 (2016). https://doi.org/10.1145/2972206.2972214

18.

Kumar, V., Frampton, D., Blackburn, S.M., Grove, D., Tardieu, O.: Work-stealing without the baggage. In: OOPSLA, pp. 297–314 (2012). https://doi.org/10.1145/2398857.2384639CrossRef

19.

Kumar, V., Zheng, Y., Cavé, V., Budimlić, Z., Sarkar, V.: HabaneroUPC++: a compiler-free PGAS library. In: PGAS, pp. 5:1–5:10 (2014). https://doi.org/10.1145/2676870.2676879

20.

Lea, D.: A Java fork/join framework. In: JAVA, pp. 36–43 (2000). https://doi.org/10.1145/337449.337465

21.

Lin, Y., Wang, K., Blackburn, S.M., Hosking, A.L., Norrish, M.: Stop and go: understanding yieldpoint behavior. In: ISMM, pp. 70–80 (2015). https://doi.org/10.1145/2754169.2754187

22.

Marochko, A.: Exception handling and cancellation in TBB–Part II (2008)

23.

McCandless, M., Hatcher, E., Gospodnetic, O.: Lucene in Action, Second Edition: Covers Apache Lucene 3.0. Manning Publications Co., Greenwich (2010)

24.

Olivier, S., et al.: UTS: an unbalanced tree search benchmark. In: LCPC, pp. 235–250 (2007). http://dl.acm.org/citation.cfm?id=1757112.1757137

25.

Peierls, T., Goetz, B., Bloch, J., Bowbeer, J., Lea, D., Holmes, D.: Java Concurrency in Practice. Addison-Wesley Professional, Reading (2005)

26.

Wheeler, D.A.: SLOCCount (2001). http://www.dwheeler.com/sloccount/

27.

Guo, Y., Barik, R., Raman, R., Sarkar, V.: Work-first and help-first scheduling policies for Async-finish task parallelism. In: IPDPS, pp. 1–12 (2009). https://doi.org/10.1109/IPDPS.2009.5161079

Titel: Featherlight Speculative Task Parallelism
verfasst von: Vivek Kumar
Verlag: Springer International Publishing
Buch: Euro-Par 2019: Parallel Processing
Print ISBN: 978-3-030-29399-4

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

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-29400-7_28

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"