Identifying Inter-task Communication in Shared Memory Programming Models
Pages 168 - 182
Abstract
Modern computers often use multi-core architectures, covering clusters of homogeneous cores for high performance computing, to heterogeneous architectures typically found in embedded systems. To efficiently program such architectures, it is important to be able to partition and map programs onto the cores of the architecture. We believe that communication patterns need to become explicit in the source code to make it easier to analyze and partition parallel programs. Extraction of these patterns are difficult to automate due to limitations in compiler techniques when determining the effects of pointers.
In this paper, we propose an OpenMP extension which allows programmers to explicitly declare the pointer based data-sharing between coarse-grain program parts. We present a dependency directive, expressing the input and output relation between program parts and pointers to shared data, as well as a set of runtime operations which are necessary to enforce declarations made by the programmer. The cost and scalability of the runtime operations are evaluated using micro-benchmarks and a benchmark from the NAS parallel benchmark suite. The measurements show that the overhead of the runtime operations is small. In fact, no performance degradation is found when using the runtime operations in the benchmark from the NAS parallel benchmark suite.
References
[1]
OpenMP Architecture Review Board: OpenMP application program interface, version 3.0. Technical report, OpenMP Archtecture Review Board (2008).
[2]
Liblit, B., Aiken, A., Yelick, K.A.: Type systems for distributed data sharing. In: Cousot, R. (ed.) SAS 2003. LNCS, vol. 2694, pp. 273-294. Springer, Heidelberg (2003).
[3]
Bailey, D.H., et al.: The NAS parallel benchmarks--summary and preliminary results. In: Proceedings of Supercomputing 1991, pp. 158-165. ACM, New York (1991).
[4]
Jin, H., Frumkin, M., Yan, H.: NPB-OpenMP 3.0. Technical Report NAS-99-011, NASA Ames Research Center, Moffett Field, CA 94035-1000 (October 1999).
[5]
Adve, S.V., Gharachorloo, K.: Shared memory consistency models: A tutorial. IEEE Computer 29(12), 66-76 (1996).
[6]
Sinnen, O.: Task Scheduling for Parallel Systems. Wiley-Interscience, Hoboken (2007).
[7]
Duran, A., Pérez, J.M., Ayguadé, E., Badia, R.M., Labarta, J.: Extending the OpenMP tasking model to allow dependent tasks. In: Eigenmann, R., de Supinski, B.R. (eds.) IWOMP 2008. LNCS, vol. 5004, pp. 111-122. Springer, Heidelberg (2008).
[8]
Rinard, M.C., Lam, M.S.: The design, implementation, and evaluation of Jade. TOPLAS 20(3), 483-545 (1998).
[9]
Allen, F.E.: Control flow analysis. SIGPLAN Not. 5(7), 1-19 (1970).
[10]
Schmitz, M.T., Al-Hashimi, B.M., Eles, P.: System-Level Design Techniques for Energy-Efficient Embedded Systems. Kluwer Academic Publishers, Norwell (2004).
[11]
Sinnen, O., Sousa, L.: A classification of graph theoretic models for parallel computing. Technical Report RT/005/99, Instituto Superior Tecnico, Technical University of Lisbon (1999).
[12]
Vallerio, K.S., Jha, N.K.: Task graph extraction for embedded system synthesis. In: Proceedings of VLSID 2003, p. 480. IEEE Computer Society Press, Los Alamitos (2003).
[13]
Liu, A.H., Dick, R.P.: Automatic run-time extraction of communication graphs from multithreaded applications. In: Proceedings of CODES+ISSS 2006, pp. 46- 51. ACM, New York (2006).
[14]
Dubois, M., Scheurich, C., Briggs, F.: Memory access buffering in multiprocessors. SIGARCH Comput. Archit. News 14(2), 434-442 (1986).
[15]
Gharachorloo, K., et al.: Memory consistency and event ordering in scalable shared-memory multiprocessors. In: Proceedings of ISCA 1990, pp. 15-26 (1990).
[16]
Emami, M., Ghiya, R., Hendren, L.J.: Context-sensitive interprocedural points-to analysis in the presence of function pointers. In: PLDI 1994, pp. 242-256 (1994).
[17]
Hind, M.: Analysis: Havent we solved this problem yet. In: Proceedings of PASTE 2001, pp. 54-61. ACM, New York (2001).
[18]
Ramalingam, G.: The undecidability of aliasing. TOPLAS 16(5), 1467-1471 (1994).
[19]
Adve, V.S., Sakellariou, R.: Compiler synthesis of task graphs for parallel program performance prediction. In: Midkiff, S.P., Moreira, J.E., Gupta, M., Chatterjee, S., Ferrante, J., Prins, J.F., Pugh, B., Tseng, C.-W. (eds.) LCPC 2000. LNCS, vol. 2017, pp. 208-226. Springer, Heidelberg (2001).
[20]
Snir, M., et al.: MPI - The Complete Reference, 2nd edn. The MPI Core, vol. 1. The MIT Press, Cambridge (1998).
[21]
Ayguadé, E., et al.: A proposal for task parallelism in OpenMP. In: Chapman, B., Zheng, W., Gao, G.R., Sato, M., Ayguadé, E., Wang, D. (eds.) IWOMP 2007. LNCS, vol. 4935, pp. 1-12. Springer, Heidelberg (2008).
[22]
Asanovic, K., et al.: The landscape of parallel computing research: A view from Berkeley. Technical Report UCB/EECS-2006-183, EECS Department, University of California, Berkeley (2006).
[23]
Rodman, A., Brorsson, M.: Programming effort vs. performance with a hybrid programming model for distributed memory parallel architectures. In: Proceedings of EuroPar 1998, pp. 888-898 (1999).
[24]
Karlsson, S., Brorsson, M.: A comparative characterization of communication patterns in applications using MPI and shared memory on an IBM SP2. In: Panda, D.K., Stunkel, C.B. (eds.) CANPC 1998. LNCS, vol. 1362, pp. 189-201. Springer, Heidelberg (1998).
[25]
Courtois, P.J., Heymans, F., Parnas, D.L.: Concurrent control with "readers" and "writers". Commun. ACM 14(10), 667-668 (1971).
[26]
IEEE: IEEE std. 1003.1c-1995 thread extensions. Technical report, IEEE, Formerly POSIX.4a. now included in 1003.1-2004 (1995).
[27]
Bull, J.M., O'Neill, D.: A microbenchmark suite for OpenMP 2.0. SIGARCH Comput. Archit. News 29(5), 41-48 (2001).
[28]
McKenney, P.E., Slingwine, J.D.: Read-copy update: Using execution history to solve concurrency problems. In: Proceedings of PDCS 1998, pp. 509-518 (1998).
- Identifying Inter-task Communication in Shared Memory Programming Models
Recommendations
Shared memory programming for large scale machines
PLDI '06: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and ImplementationThis paper describes the design and implementation of a scalable run-time system and an optimizing compiler for Unified Parallel C (UPC). An experimental evaluation on BlueGene/L®, a distributed-memory machine, demonstrates that the combination of the ...
Shared memory programming for large scale machines
Proceedings of the 2006 PLDI ConferenceThis paper describes the design and implementation of a scalable run-time system and an optimizing compiler for Unified Parallel C (UPC). An experimental evaluation on BlueGene/L®, a distributed-memory machine, demonstrates that the combination of the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2009
182 pages
ISBN:9783642022845
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 22 May 2009
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in