A HYBRID SHARED MEMORY EXECUTION MODEL FOR A DATA PARALLEL LANGUAGE WITH I/O
Abstract
We propose a novel execution model for the implicitly parallel execution of data parallel programs in the presence of general I/O operations. This model is called hybrid because it combines the advantages of the standard execution models fork/join and SPMD. Based on program analysis the hybrid model adapts itself to one or the other on the granularity of individual instructions. We outline compilation techniques that systematically derive the organization of parallel code from data flow characteristics aiming at the reduction of execution mode switches in general and synchronization/communication requirements in particular. Experiments based on a prototype implementation show the effectiveness of the hybrid execution model for reducing parallel overhead.
References
-
B. Bacci , Skeletons and Transformations in an Integrated Parallel Programming Environment , Parallel Computing Technologies (PaCT'99) ,LNCS ( Springer , 1999 ) . Google Scholar - CACM 35(8), (1992). Google Scholar
- IEEE Software Engineering 26(3), (2000). Google Scholar
-
W. N. Chin , Towards an Automated Tupling Strategy , Proc. PEPM'93. ( ACM Press , 1993 ) . Google Scholar - SIGPLAN Notices 37(6), (2002), DOI: 10.1145/571727.571737. Google Scholar
-
M. Cole , Algorithmic Skeletons: Structured Management of Parallel Computation ( Pitman , London, UK , 1989 ) . Google Scholar - Parallel Computing 30(3), (2004), DOI: 10.1016/j.parco.2003.12.002. Google Scholar
- IEEE Computational Science and Engineering 5(1), (1998), DOI: 10.1109/99.660313. Google Scholar
-
S. Gorlatch and C. Lengauer , (De)Composition Rules for Parallel Scan and Reduction , Proc. MPPM'97. ( IEEE Computer Society Press , 1997 ) . Google Scholar -
S. Gorlatch and S. Pelagatti , Parallel and Distributed Processing ,LNCS ( Springer , 1999 ) . Google Scholar -
S. Gorlatch , C. Wedler and C. Lengauer , Optimization Rules for Programming with Collective Operations , Proc. IPPS/SPDP'99 ( 1999 ) . Google Scholar -
C. Grelck , Implementing the NAS Benchmark MG in SAC , Proc. IPDPS'02. ( IEEE Computer Society Press , 2002 ) . Google Scholar -
C. Grelck , Optimizations on Array Skeletons in a Shared Memory Environment , Implementation of Functional Languages (IFL'01) ,LNCS ( Springer , 2002 ) . Google Scholar - J. Functional Programming 15(3), (2005). Google Scholar
-
C. Grelck and S.-B. Scholz , Classes and Objects as Basis for I/O in SAC , Proc. IFL'95. . Google Scholar -
C. Grelck and S.-B. Scholz , Towards an Efficient Functional Implementation of the NAS Benchmark FT , Parallel Computing Technologies (PaCT'03) ,LNCS ( Springer , 2003 ) . Google Scholar -
R. Gupta , The Fuzzy Barrier: A Mechanism for High Speed Synchronization of Processors , Proc. ASPLOS-III. ( ACM Press , 1989 ) . Google Scholar -
H. Kuchen , A Skeleton Library , Parallel Processing (Euro-Par'02) ,LNCS ( Springer , 2002 ) . Google Scholar -
H. Kuchen , Domain-Specific Program Generation ,LNCS ( Springer , 2004 ) . Crossref, Google Scholar - Concurrency Journal (1996). Google Scholar
- J. Functional Programming 13(6), (2003). Google Scholar
- Theoretical Computer Science 73(2), (1990), DOI: 10.1016/0304-3975(90)90147-A. Google Scholar


