THE IMPACT OF DYNAMIC CHANNELS ON FUNCTIONAL TOPOLOGY SKELETONS
Abstract
Parallel functional programs with implicit communication often generate purely hierarchical communication topologies during execution: communication only happens between parent and child processes. Hence, messages between siblings must be passed via the parent causing inefficiencies that can be avoided by direct communication between arbitrary processes. The Eden parallel functional language provides dynamic channels to implement arbitrary communication topologies. This paper analyses the impact of dynamic channels on Eden's topology skeletons, i.e. skeletons which define process topologies such as rings, toroids, or hypercubes. We compare topology skeletons with and without dynamic channels with respect to runtime and communication. Our case studies confirm that dynamic channels decrease the number of messages by up to 50% and substantially reduce runtime. Detailed analyses of EdenTV (Eden trace viewer) execution profiles reveal a bottleneck in the root process when only hierarchical channel connections are used and a better distribution of communications with dynamic channels.
References
- Communications of the ACM 39(3), 85 (1996), DOI: 10.1145/227234.227246. Crossref, ISI, Google Scholar
-
Silvia Breitinger and Rita Loogen , Channel Structures in the Parallel Functional Language Eden , Glasgow Workshop on Fund. Prg. ( 1997 ) . Google Scholar -
Murray I. Cole , Algorithmic Skeletons: Structured Management of Parallel Computation ( MIT Press , 1989 ) . Google Scholar Marco Danelutto , Parallel functional programming with skeletons: the OCamlP3L experiment, ACM workshop on ML and its applications (1998) p. 31. Google ScholarJ. Darlington , Parallel Programming Using Skeleton Functions, PARLE'93 — Parallel Architectures and Languages Europe,LNCS (Springer, 1993) p. 146. Google ScholarL. A. Galán , C. Pareja and R. Penña , Functional skeletons generate process topologies in Eden, PLILP'96 - Programming Languages: Implementations, Logics, and Programs,LNCS (Springer, 1996) p. 289. Google ScholarA. Giacalone , P. Mishra and S. Prasad , Facile: a Symmetric Integration of Concurrent and Functional Programming, Tapsoft'89 - Int. Joint Conf. on Theory and Practice of Software Development,LNCS (Springer, 1989) p. 181. Google Scholar- , Patterns and Skeletons for Parallel and Distributed Computing , eds.
Fethi A. Rabhi and Sergei Gorlatch ( Springer , 2003 ) . Google Scholar - Journal of Functional Programming 15(3), 431 (2005), DOI: 10.1017/S0956796805005526. Crossref, ISI, Google Scholar
- Parallel Algorithms and Appi 16, 181 (2001). Crossref, Google Scholar
R. Peña , F. Rubio and C. Segura , Deriving non-hierarchical process topologies, Trends in Functional Programming3 (2001) p. 51. Google Scholar-
M. J. Plasmeijer and M. van Eekelen , Functional Programming and Parallel Graph Rewriting ( Addison-Wesley , 1993 ) . Google Scholar - , Research Directions in Parallel Functional Programming, eds.
K. Hammond and G. Michaelson (Springer, 1999) p. 323. Crossref, Google Scholar -
M. J. Quinn , Parallel Computing ( McGraw-Hill , 1994 ) . Google Scholar -
J. H. Reppy , Concurrent Programming in ML ( Cambridge Univ. Press , 1999 ) . Crossref, Google Scholar - Pablo Roldán-Gómez. Eden Trace Viewer: A Tool to Visualize Parallel Functional Program Executions. Master's thesis, Univ. Complutense de Madrid, Spain, 2004. (in German) . Google Scholar
-
P. R. Serrarens and R. Plasmeijer , Explicit message passing for concurrent clean , IFL'98 — Implementation of Functional Languages ,LNCS ( Springer , 1999 ) . Google Scholar P. W. Trinder , Jones. GUM: A Portable Parallel Implementation of Haskell, Proc. PLDI '96 — Progr. Language Design and Impl. (ACM, 1996) pp. 78–88. Google Scholar


