nach oben

International Journal of Parallel Programming

Erschienen in:

01.08.2016

A Loosely Coordinated Model for Heap-Based Priority Queues in Multicore Environments

verfasst von: Giuliano Laccetti, Marco Lapegna, Valeria Mele

Erschienen in: International Journal of Parallel Programming | Ausgabe 4/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Heap-based priority queues are very common dynamical data structures used in several fields, ranging from operating systems to scientific applications. However, the rise of new multicore CPUs introduced new challenges in the process of design of these data structures: in addition to traditional requirements like correctness and progress, the scalability is of paramount importance. It is a common opinion that these two demands are partially in conflict each other, so that in these computational environments it is necessary to relax the requirements of correctness and linearizability to achieve high performances. In this paper we introduce a loosely coordinated approach for the management of heap based priority queues on multicore CPUs, with the aim to realize a tradeoff between efficiency and sequential correctness. The approach is based on a sharing of information among only a small number of cores, so that to improve performance without completely losing the features of the data structure. The results obtained on a scientific problem show significant benefits both in terms of parallel efficiency, as well as in term of numerical accuracy.

Vorheriger Artikel Using Machine Learning Techniques to Detect Parallel Patterns of Multi-threaded Applications

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 "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

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

Afek, Y., Hakimi, M., Morrison, A.: Quasi-linearizability: relaxed consistency for improved concurrency. In: Proceedings 14th International Conference Principles of Distributed Systems, OPODIS 2010, Lecture Notes in Computer Science Volume 6490, pp. 395–410 (2010)

Alistarh, D., Kopinsky, J., Li, J., Shavit, N.: The SprayList: A Scalable Relaxed Proprity Queue. Microsoft Tecnical Report MSR-TR-2014-16

Arora, N., Blumofe, R., Plaxton, G.: Thread scheduling for multiprogrammed multiprocessors. Theory Comput. Syst. 34, 115–144 (2001)MathSciNetCrossRefMATH

Ayani, R.: LR\_algorithm: concurrent operations on priority queues. In Proceedings on the 2nd IEEE Symposium on Parallel and Distributed Processing, pp. 22–25 (1991)

Berntsen, J.: Practical error estimation in adaptive multidimensional quadrature routines. J. Comput. Appl. Math. 25, 327–340 (1989)MathSciNetCrossRefMATH

Berntsen, J., Espelid, T., Genz, A.: Algorithm 698: DCUHRE—an adaptive multidimensional integration routine for a vector of integrals. ACM Trans. Math. Softw. 17, 452–456 (1991)MathSciNetCrossRefMATH

Cools, R., Rabinowitz, P.: Monomial cubature rules since “Stroud”: a compilation. J. Comput. Appl. Math. 48, 309–326 (1993)MathSciNetCrossRefMATH

D’Amore, L., Casaburi, D., Galletti, A., Marcellino, L., Murli, A.: Integration of emerging computer technologies for an efficient image sequences analysis. Integr. Comput. Aided Eng. 18, 365–378 (2011)

Dongarra, J., Gannon, D., Fox, G., Kennedy, K.: The impact of multicore on computational science software. CTWatch Q. 3, 1–10 (2007)

10.

Dongarra, J., Foster, I., Fox, G., Gropp, W., Kennedy, K., Torczon, L., White, A.: Sourcebook of Parallel Computing. Morgan Kaufmann Publishers, Burlington (2003)

11.

Flatt, H.P., Kennedy, K.: Performance of parallel processors. Parallel Comput. 12, 1–20 (1989)MathSciNetCrossRefMATH

12.

Genz, A.: Testing multiple integration software. In: Ford, B., Rault, J.C., Thommaset, F. (eds.) Tools, Methods and Language for Scientic and Engineering Computation. North Holland, New York (1984)

13.

Genz, A., Malik, A.: An embedded family of fully symmetric numerical integration rules. SIAM J. Numer. Anal. 20, 580–588 (1983)MathSciNetCrossRefMATH

14.

Haas, A., Henzinger, T., Kirsch, C., Lippautz, M., Payer, H., Sezgin, A., Sokolova, A.: Distributed queues in shared memory. In: CF ’13 Proceedings of the ACM International Conference on Computing Frontiers, ACM New York. Article No. 17 (2013)

15.

Hendler, D., Shavit, N., Yerushalmi, L.: A scalable lock-free algorithm. J. Parallel Distrib. Comput. 70, 1–12 (2010)CrossRefMATH

16.

Henzinger, T., Kirsch, C., Payer, H., Sezgin, A., Sokolova, A.: Quantitative relaxation of concurrent data structure. In: POPL ’13 Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 317–328. ACM, New York (2013)

17.

Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Progr. Lang. Syst. 12, 463–492 (1990)CrossRef

18.

Herlihy, M.: Wait-free synchronization. ACM Trans. Progr. Lang. Syst. 11, 124–149 (1991)CrossRef

19.

Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: double ended queues as an example. In: Proceedings of 23th International Conference on Distributed Computing System (2003)

20.

Herlihy, M.P., Shavit, N.: The Art of Multiprocessor Programming. Rev. 1st edn. Morgan Kaufmann (2012)

21.

Kessels, J.: On the fly optimization of data structure. Commun. ACM 26, 895–901 (1983)CrossRefMATH

22.

Kogan, A., Petrank, E.: Wait-free queues with multiple enqueuers and dequeuers. In: PPoPP ’11 Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming, pp. 223–234. ACM, New York (2011)

23.

Krommer, A., Ueberhuber, C.: Computational Integration. SIAM, New Delhi (1998)CrossRefMATH

24.

Laccetti, G., Lapegna, M.: PAMIHR. A parallel FORTRAN program for multidimensional quadrature on distributed memory architectures. Lect. Notes Comput. Sci. 1685, 1144–1148 (1999)CrossRef

25.

Laccetti, G., Lapegna, M., Mele, V., Romano, D., Murli, A.: A double adaptive algorithm for multidimensional integration on multicore based HPC systems. Int. J. Parallel Progr. 40, 397–409 (2012)CrossRef

26.

Lapegna, M.: A global adaptive quadrature for the approximate computation of multidimensional integrals on a distributed memory multiprocessor. Concurr Pract. Exp. 4, 413–426 (1992)CrossRef

27.

Michael, M., Scott, M.: Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In: Proceedings PODC ’96 Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 267–275. ACM, New York (1996)

28.

Moir, M., Nussbaum, D., Shalev, O., Shavit, N.: Using elimination to implement scalable and lock-free FIFO queues. In: Proceeding SPAA ’05 Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 253–262. ACM, NewYork (2005)

29.

Moir, M., Shavit, N.: Concurrent Data Structures. In: Metha, D., Sahni, S. (eds.) Handbook of Data Structures and Applications, 1st edn, pp. 47-1–47-30. CRC Press, Boca Raton (2005)

30.

Murli, A., D’Amore, L., Laccetti, G., Gregoretti, F., Oliva, G.: A multi-grained distributed implementation of the parallel Block Conjugate Gradient algorithm. Concurr. Comput. Pract. Exp. 22, 2053–2072 (2010)

31.

Nurmi, O., Soisalon-Soininen, E., Wood, D.: Concurrent control in database structures with relaxed balance. In: Proceedings. of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 170–176. ACM, New York (1987)

32.

Rao, V., Kumar, V.: Concurrent access of priority queues. IEEE Trans. Comput. 37, 1657–1665 (1988)CrossRefMATH

33.

Shavit, N.: Data structure in multicore age. Commun. ACM 54, 76–84 (2011)CrossRef

34.

Shavit, N., Touitou, D.: Elimination tree and the construction of pools and stacks. Theory Comput. Syst. 30, 645–670 (1997)MathSciNetCrossRefMATH

35.

Sundell, H., Tsigas, P.: Fast and lock-free concurrent priority queues for multi-thread systems. J. Parallel Distrib. Comput. 65, 609–627 (2005)CrossRefMATH

36.

Wimmer, M., Versaci, F., Traff, J.L., Cedermann, D., Tsigas, P.: Data structure for task-based priority scheduling. In: PPoPP ’14 Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 379–380. ACM, New York (2014)

Titel: A Loosely Coordinated Model for Heap-Based Priority Queues in Multicore Environments
verfasst von: Giuliano Laccetti
Marco Lapegna
Valeria Mele
Publikationsdatum: 01.08.2016
Verlag: Springer US
Erschienen in: International Journal of Parallel Programming / Ausgabe 4/2016
Print ISSN: 0885-7458
Elektronische ISSN: 1573-7640
DOI: https://doi.org/10.1007/s10766-015-0398-x

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 "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2016

Performance Estimation of Task Graphs Based on Path Profiling

Optimizing the Matrix Multiplication Using Strassen and Winograd Algorithms with Limited Recursions on Many-Core

Achieving Optimal Inter-Node Communication in Graph Partitioning Using Random Selection and Breadth-First Search

Erratum to: Optimizing the Matrix Multiplication Using Strassen and Winograd Algorithms with Limited Recursions on Many-Core

Using Machine Learning Techniques to Detect Parallel Patterns of Multi-threaded Applications

MapReduce Parallel Programming Model: A State-of-the-Art Survey