Abstract
This paper presents a new efficient programming toolchain for message-passing parallel algorithms which can fully ensure, for any typable programs and for any execution path, deadlock-freedom, communication safety and global progress through a static checking. The methodology is embodied as a multiparty session-based programming environment for C and its runtime libraries, which we call Session C. Programming starts from specifying a global protocol for a target parallel algorithm, using a protocol description language. From this global protocol, the projection algorithm generates endpoint protocols, based on which each endpoint C program is designed and implemented with a small number of concise session primitives. The endpoint protocol can further be refined to a more optimised protocol through subtyping for asynchronous communication, preserving original safety guarantees. The underlying theory can ensure that the complexity of the toolchain stays in polynomial time against the size of programs. We apply this framework to representative parallel algorithms with complex communication topologies. The benchmark results show that Session C performs competitively against MPI.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Jacobi and Gauss-Seidel Iteration, http://math.fullerton.edu/mathews/n2003/GaussSeidelMod.html
N-body algorithm using pipeline, http://www.mcs.anl.gov/research/projects/mpi/usingmpi/examples/advmsg/nbodypipe_c.htm
Bettini, L., Coppo, M., D’Antoni, L., De Luca, M., Dezani-Ciancaglini, M., Yoshida, N.: Global Progress in Dynamically Interleaved Multiparty Sessions. In: van Breugel, F., Chechik, M. (eds.) CONCUR 2008. LNCS, vol. 5201, pp. 418–433. Springer, Heidelberg (2008)
Bocchi, L., Honda, K., Tuosto, E., Yoshida, N.: A Theory of Design-by-Contract for Distributed Multiparty Interactions. In: Gastin, P., Laroussinie, F. (eds.) CONCUR 2010. LNCS, vol. 6269, pp. 162–176. Springer, Heidelberg (2010)
Carter, J., Gardner, W.B., Grewal, G.: The Pilot approach to cluster programming in C. In: IPDPSW, pp. 1–8. IEEE (2010)
Casanova, H., Legrand, A., Robert, Y.: Parallel Algorithms. Chapman & Hall (July 2008)
Danalis, A., et al.: MPI-aware compiler optimizations for improving communication-computation overlap. In: ICS 2009, pp. 316–325 (2009)
Deniélou, P.M., Yoshida, N.: Buffered Communication Analysis in Distributed Multiparty Sessions. In: Gastin, P., Laroussinie, F. (eds.) CONCUR 2010. LNCS, vol. 6269, pp. 343–357. Springer, Heidelberg (2010)
Deniélou, P.M., Yoshida, N.: Dynamic multirole session types. In: POPL, pp. 435–446. ACM (2011)
Deniélou, P.M., Yoshida, N.: Multiparty Session Types Meet Communicating Automata. In: Seidl, H. (ed.) Programming Languages and Systems. LNCS, vol. 7211, pp. 194–213. Springer, Heidelberg (2012)
Dwarf Mine homepage, http://view.eecs.berkeley.edu/wiki/Dwarf_Mine
Friedley, A., Lumsdaine, A.: Communication Optimization Beyond MPI. In: IPDPSW and Phd Forum. IEEE (2011)
Online Appendix, http://www.doc.ic.ac.uk/~cn06/pub/2012/sessionc/
Grama, A., Karypis, G., Kumar, V., Gupta, A.: Introduction to Parallel Computing, 2nd edn. Addison Wesley (January 2003)
Gropp, W., Lusk, E., Skjellum, A.: Using MPI: Portable Parallel Programming with the Message-Passing Interface. MIT Press (1999)
Honda, K., Mukhamedov, A., Brown, G., Chen, T.-C., Yoshida, N.: Scribbling Interactions with a Formal Foundation. In: Natarajan, R., Ojo, A. (eds.) ICDCIT 2011. LNCS, vol. 6536, pp. 55–75. Springer, Heidelberg (2011)
Honda, K., Vasconcelos, V.T., Kubo, M.: Language Primitives and Type Discipline for Structured Communication-Based Programming. In: Hankin, C. (ed.) ESOP 1998. LNCS, vol. 1381, pp. 122–138. Springer, Heidelberg (1998)
Honda, K., Yoshida, N., Carbone, M.: Multiparty asynchronous session types. In: POPL 2008, vol. 5201, p. 273 (2008)
Hu, R., Kouzapas, D., Pernet, O., Yoshida, N., Honda, K.: Type-Safe Eventful Sessions in Java. In: D’Hondt, T. (ed.) ECOOP 2010. LNCS, vol. 6183, pp. 329–353. Springer, Heidelberg (2010)
Hu, R., Yoshida, N., Honda, K.: Session-Based Distributed Programming in Java. In: Ryan, M. (ed.) ECOOP 2008. LNCS, vol. 5142, pp. 516–541. Springer, Heidelberg (2008)
Jim, T., Morrisett, G., Grossman, D., Hicks, M., Cheney, J., Wang, Y.: Cyclone: A Safe Dialect of C. In: Usenix Annual Technical Conference, Monterey, CA (2002)
Lattner, C., Adve, V.S.: LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In: CGO 2004, pp. 75–88 (2004)
Leighton, F.T.: Introduction to parallel algorithms and architectures: arrays, trees, hypercubes. Morgan Kaufmann (1991)
Metis and parmetis, glaros.dtc.umn.edu/gkhome/views/metis
Mostrous, D.: Session Types in Concurrent Calculi: Higher-Order Processes and Objects. Ph.D. thesis, Imperial College London (2009)
Mostrous, D., Yoshida, N., Honda, K.: Global Principal Typing in Partially Commutative Asynchronous Sessions. In: Castagna, G. (ed.) ESOP 2009. LNCS, vol. 5502, pp. 316–332. Springer, Heidelberg (2009)
Message Passing Interface, http://www.mcs.anl.gov/research/projects/mpi/
MPJ Express homepage, http://mpj-express.org/
Ng, N., Yoshida, N., Pernet, O., Hu, R., Kryftis, Y.: Safe Parallel Programming with Session Java. In: De Meuter, W., Roman, G.-C. (eds.) COORDINATION 2011. LNCS, vol. 6721, pp. 110–126. Springer, Heidelberg (2011)
Occam-pi homepage, http://www.occam-pi.org/
Scribble homepage, http://www.jboss.org/scribble
Siegel, S.F., Zirkel, T.K.: Automatic formal verification of MPI-based parallel programs. In: PPoPP 2011, p. 309. ACM Press (February 2011)
Villard, J.: Heaps and Hops. Ph.D. thesis, ENS Cachan (2011)
Vo, A., Vakkalanka, S., DeLisi, M., Gopalakrishnan, G., Kirby, R.M., Thakur, R.: Formal verification of practical MPI programs. In: PPoPP 2009, pp. 261–270 (2009)
Vo, A., et al.: A Scalable and Distributed Dynamic Formal Verifier for MPI Programs. In: SC 2010, pp. 1–10. IEEE (2010)
Yoshida, N., Deniélou, P.-M., Bejleri, A., Hu, R.: Parameterised Multiparty Session Types. In: Ong, L. (ed.) FOSSACS 2010. LNCS, vol. 6014, pp. 128–145. Springer, Heidelberg (2010)
ZeroMQ homepage, http://www.zeromq.org/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ng, N., Yoshida, N., Honda, K. (2012). Multiparty Session C: Safe Parallel Programming with Message Optimisation. In: Furia, C.A., Nanz, S. (eds) Objects, Models, Components, Patterns. TOOLS 2012. Lecture Notes in Computer Science, vol 7304. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30561-0_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-30561-0_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30560-3
Online ISBN: 978-3-642-30561-0
eBook Packages: Computer ScienceComputer Science (R0)