nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Safe Parallelism: Compiler Analysis Techniques for Ada and OpenMP

verfasst von : Sara Royuela, Xavier Martorell, Eduardo Quiñones, Luis Miguel Pinho

Erschienen in: Reliable Software Technologies – Ada-Europe 2018

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

There is a growing need to support parallel computation in Ada to cope with the performance requirements of the most advanced functionalities of safety-critical systems. In that regard, the use of parallel programming models is paramount to exploit the benefits of parallelism.

Recent works motivate the use of OpenMP for being a de facto standard in high-performance computing for programming shared memory architectures. These works address two important aspects towards the introduction of OpenMP in Ada: the compatibility of the OpenMP syntax with the Ada language, and the interoperability of the OpenMP and the Ada runtimes, demonstrating that OpenMP complements and supports the structured parallelism approach of the tasklet model.

This paper addresses a third fundamental aspect: functional safety from a compiler perspective. Particularly, it focuses on race conditions and considers the fine-grain and unstructured capabilities of OpenMP. Hereof, this paper presents a new compiler analysis technique that: (1) identifies potential race conditions in parallel Ada programs based on OpenMP or Ada tasks or both, and (2) provides solutions for the detected races.

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 Theory and Practice of EDF Scheduling in Distributed Real-Time Systems

Nächstes Kapitel Microservice-Based Agile Architectures: An Opportunity for Specialized Niche Technologies

Nur mit Berechtigung zugänglich

Spark considers the following synchronized objects: protected objects, atomic objects (all accesses are atomic), and suspension objects (a kind of private semaphore).

The term task in OpenMP is not related to Ada tasks. OpenMP tasks are lightweight parts of the code that can be executed in parallel by worker threads. In that regard, OpenMP tasks are very similar to Ada tasklets [16].

OpenMP allows three ways to determine the data-sharing attributes: predetermined, implicitly determined, and explicitly determined. The first two kinds are defined by several rules in the specification, the latter requires explicit definition by the user.

Model checking mechanisms allow exhaustively and automatically checking a given model regarding a given specification. Typically, hardware or software components are checked against safety requirements such as the absence of deadlocks and other critical states that can cause a system to crash.

An OpenMP conforming program is that which follows all rules and restrictions of the OpenMP specification.

Hard Real-Time Hierarchical Object-Oriented Design (HRT-HOOD) is an object-based structured design method for hard real-time systems [39].

In OpenMP, the binding region is the enclosing region that determines the execution context. The binding region of a task is the innermost enclosing parallel region.

The OpenMP API is an specification for defining parallelism in C, C++ and Fortran programs.

The OpenMP specification (Sect. 2.17 [10]) defines a series of rules that determine which constructs cannot be nested within each other.

NVIDIA: Automotive (2017). https://www.nvidia.com/en-us/self-driving-cars

AdaCore: Automotive (2018). https://www.adacore.com/industries/automotive

Pinho, L.M., Moore, B., Michell, S.: Parallelism in Ada: status and prospects. In: George, L., Vardanega, T. (eds.) Ada-Europe 2014. LNCS, vol. 8454, pp. 91–106. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08311-7_8CrossRef

Taft, S.T., Moore, B., Pinho, L.M., Michell, S.: Safe parallel programming in Ada with language extensions. ACM SIGAda Ada Lett. 34(3), 87–96 (2014)CrossRef

Pinho, L.M., Moore, B., Michell, S., Tucker Taft, S.: An execution model for fine-grained parallelism in Ada. In: de la Puente, J.A., Vardanega, T. (eds.) Ada-Europe 2015. LNCS, vol. 9111, pp. 196–211. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-19584-1_13CrossRef

Pinho, L.M., Moore, B., Michell, S., Taft, S.T.: Real-time fine-grained parallelism in Ada. ACM SIGAda Ada Lett. 35(1), 46–58 (2015)CrossRef

Taft, T., Moore, B., Pinho, L.M., Michell, S.: Reduction of parallel computation in the parallel model for Ada. ACM SIGAda Ada Lett. 36(1), 9–24 (2016)CrossRef

Royuela, S., Martorell, X., Quiñones, E., Pinho, L.M.: OpenMP tasking model for Ada: safety and correctness. In: Blieberger, J., Bader, M. (eds.) Ada-Europe 2017. LNCS, vol. 10300, pp. 184–200. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-60588-3_12CrossRef

Royuela, S., Pinho, L.M., Quiñones, E.: Converging safety and high-performance domains: integrating OpenMP into Ada. In: Design, Automation & Test in Europe, March 2018

10.

OpenMP Architecture Review Board: OpenMP Application Programming Interface 4.5 (2015). http://www.openmp.org/wp-content/uploads/openmp-4.5.pdf

11.

Royuela, S., Duran, A., Serrano, M.A., Quiñones, E., Martorell, X.: A functional safety OpenMP\(^{*}\) for critical real-time embedded systems. In: de Supinski, B.R., Olivier, S.L., Terboven, C., Chapman, B.M., Müller, M.S. (eds.) IWOMP 2017. LNCS, vol. 10468, pp. 231–245. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-65578-9_16CrossRef

12.

Ada Resource Association: Ada 95 Reference Manual. ISO/IEC 8652:1995(E) with COR.1 (2000). http://www.adaic.org/resources/add_content/standards/95lrm/RM.pdf

13.

Burns, A., Dobbing, B., Romanski, G.: The Ravenscar tasking profile for high integrity real-time programs. In: Asplund, L. (ed.) Ada-Europe 1998. LNCS, vol. 1411, pp. 263–275. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055011CrossRef

14.

Barnes, J.G.P.: High Integrity Software: The Spark Approach to Safety and Security: Sample Chapters. Pearson Education, London (2003)

15.

Taft, S.T., Schanda, F., Moy, Y.: High-integrity multitasking in SPARK: static detection of data races and locking cycles. In: 17th International Symposium on High Assurance Systems Engineering, pp. 238–239. IEEE (2016)

16.

Michell, S., Moore, B., Pinho, L.M.: Tasklettes – a fine grained parallelism for Ada on multicores. In: Keller, H.B., Plödereder, E., Dencker, P., Klenk, H. (eds.) Ada-Europe 2013. LNCS, vol. 7896, pp. 17–34. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38601-5_2CrossRef

17.

Serrano, M.A., Melani, A., Vargas, R., Marongiu, A., Bertogna, M., Quiñones, E.: Timing characterization of OpenMP4 tasking model. In: International Conference on Compilers, Architecture and Synthesis for Embedded Systems, pp. 157–166. IEEE Press, October 2015

18.

Serrano, M.A., Melani, A., Bertogna, M., Quiñones, E.: Response-time analysis of DAG tasks under fixed priority scheduling with limited preemptions. In: Design, Automation & Test in Europe, pp. 1066–1071. IEEE, March 2016

19.

Melani, A., Serrano, M.A., Bertogna, M., Cerutti, I., Quiñones, E., Buttazzo, G.: A static scheduling approach to enable safety-critical OpenMP applications. In: 22nd Asia and South Pacific Design Automation Conference, pp. 659–665. IEEE, January 2017

20.

Sun, J., Guan, N., Wang, Y., He, Q., Yi, W.: Scheduling and analysis of real-time OpenMP task systems with tied tasks. In: Proceedings of Real-Time Systems Symposium (2017)

21.

Kroening, D., Poetzl, D., Schrammel, P., Wachter, B.: Sound static deadlock analysis for C/Pthreads. In: 31st International Conference on Automated Software Engineering, pp. 379–390. IEEE, September 2016

22.

Ma, H., Diersen, S.R., Wang, L., Liao, C., Quinlan, D., Yang, Z.: Symbolic analysis of concurrency errors in OpenMP programs. In: 42nd International Conference on Parallel Processing, pp. 510–516. IEEE, October 2013

23.

Basupalli, V., Yuki, T., Rajopadhye, S., Morvan, A., Derrien, S., Quinton, P., Wonnacott, D.: ompVerify: polyhedral analysis for the OpenMP programmer. In: Chapman, B.M., Gropp, W.D., Kumaran, K., Müller, M.S. (eds.) IWOMP 2011. LNCS, vol. 6665, pp. 37–53. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21487-5_4CrossRef

24.

Royuela, S., Ferrer, R., Caballero, D., Martorell, X.: Compiler analysis for OpenMP tasks correctness. In: 12th International Conference on Computing Frontiers, p. 7. ACM, May 2015

25.

Evangelista, S., Kaiser, C., Pradat-Peyre, J.-F., Rousseau, P.: Quasar: a new tool for concurrent Ada programs analysis. In: Rosen, J.-P., Strohmeier, A. (eds.) Ada-Europe 2003. LNCS, vol. 2655, pp. 168–181. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-44947-7_12CrossRefMATH

26.

Fechete, R., Kienesberger, G., Blieberger, J.: A framework for CFG-based static program analysis of Ada programs. In: Kordon, F., Vardanega, T. (eds.) Ada-Europe 2008. LNCS, vol. 5026, pp. 130–143. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68624-8_10CrossRef

27.

Qi, X., Xu, B.: An approach to slicing concurrent Ada programs based on program reachability graphs. Int. J. Comput. Sci. Netw. Secur. 6(1), 29–37 (2005)

28.

Mohaqeqi, M., Abdullah, J., Guan, N., Yi, W.: Schedulability analysis of synchronous digraph real-time tasks. In: 28th Euromicro Conference on Real-Time Systems, pp. 176–186. IEEE, July 2016

29.

Wang, B., Gao, H., Cheng, J.: Definition-use net and system dependence net generators for Ada 2012 programs and their applications. Ada User J. 38(1), 37–55 (2017)

30.

Faria, J.M., Martins, J., Pinto, J.S.: An approach to model checking Ada programs. In: Brorsson, M., Pinho, L.M. (eds.) Ada-Europe 2012. LNCS, vol. 7308, pp. 105–118. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30598-6_8CrossRef

31.

Holzmann, G.J.: The model checker SPIN. IEEE Trans. Softw. Eng. 23(5), 279–295 (1997)CrossRef

32.

AdaCore, Altran, Astrium Space Transportation, CEA-LIST, ProVal at INRIA and Thales Communications: Project Hi-Lite: GNATprove (2017). http://www.open-do.org/projects/hi-lite/gnatprove

33.

GNU: GNAT (2016). https://www.gnu.org/software/gnat

34.

Meyer, B.: Object-Oriented Software Construction, vol. 2. Prentice Hall, New York (1988)

35.

Ada Resource Association: Ada Reference Manual, ISO/IEC 8652:2012(E) (2012). http://archive.adaic.com/standards/83lrm/html

36.

Royuela, S., Duran, A., Liao, C., Quinlan, D.J.: Auto-scoping for OpenMP tasks. In: Chapman, B.M., Massaioli, F., Müller, M.S., Rorro, M. (eds.) IWOMP 2012. LNCS, vol. 7312, pp. 29–43. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30961-8_3CrossRef

37.

Royuela, S., Duran, A., Martorell, X.: Compiler automatic discovery of OmpSs task dependencies. In: Kasahara, H., Kimura, K. (eds.) LCPC 2012. LNCS, vol. 7760, pp. 234–248. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-37658-0_16CrossRef

38.

Burns, A., Dobbing, B., Vardanega, T.: Guide for the use of the Ada Ravenscar Profile in high integrity systems. ACM SIGAda Ada Lett. 24(2), 1–74 (2004)CrossRef

39.

Burns, A., Wellings, A.J.: HRT-HOOD: a structured design method for hard real-time systems. Real-Time Syst. 6(1), 73–114 (1994)CrossRef

40.

Duran, A., Ayguadé, E., Badia, R.M., Labarta, J., Martinell, L., Martorell, X., Planas, J.: OmpSs: a proposal for programming heterogeneous multi-core architectures. Parallel Process. Lett. 21(02), 173–193 (2011)MathSciNetCrossRef

41.

Lippe, E., van Oosterom, N.: Operation-based merging. In: Proceedings of the Fifth ACM SIGSOFT Symposium on Software Development Environments, SDE 5, pp. 78–87. ACM, New York (1992)

Titel: Safe Parallelism: Compiler Analysis Techniques for Ada and OpenMP
verfasst von: Sara Royuela
Xavier Martorell
Eduardo Quiñones
Luis Miguel Pinho
Verlag: Springer International Publishing
Buch: Reliable Software Technologies – Ada-Europe 2018
Print ISBN: 978-3-319-92431-1

Electronic ISBN: 978-3-319-92432-8

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-92432-8_9

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"