Supervision : Bertil FOLLIOT

Co-supervision : THOMAS Gaël

Optimized inter-core communication for pipeline parallelism

Among the various paradigms of parallelization, pipeline parallelism has the advantage of maintaining sequentiality of algorithms, thus being applicable in case of data dependencies. More over, the stream-computing extension for OpenMP proposed by Pop and Cohen allows to apply this form of parallelization without needing a complete rewrite of the code, by simply adding annotations to it. However, due to the *importance* of the communication needed between the cores, the performances obtained by following this paradigm depends very much on the communication algorithm used. Yet, the communication algorithm used in this extension relies on queues that can handle several producers and consumers while applications using pipeline parallelism mainly works with linear communication chains.
To improve the performances of pipeline parallelism implemented by the stream- computing extension for OpenMP, this thesis propose to use, whenever possible, a more specialized communication algorithme called BatchQueue. By only handling the special case of a communication with one producer and one consumer, BatchQueue can reach throughput up to two time faster than existing algorithms. Furthermore, once integrated to the stream-computing extension for OpenMP, the evaluation shows that BatchQueue can improve speedup of application up to a factor 2 as well. The study thus shows that using a more efficient specialized communication algorithm can have a significant impact on overall performances of application implementing pipeline parallelism.

2009-2013 Publications

• 2013
  • Th. Preud'homme : “Communication inter-cœurs optimisée pour le parallélisme de flux”, thesis, phd defence 06/10/2013, supervision Folliot, Bertil, co-supervision : Thomas, Gaël (2013)
• 2012
  • Th. Preud'Homme, J. Sopena, G. Thomas, B. Folliot : “An improvement of OpenMP pipeline parallelism with the BatchQueue algorithm”, 18^th IEEE International Conference on Parallel and Distributed Systems (ICPADS'12), Singapore, Singapore, pp. 348-355, (IEEE Computer Society Press) (2012)
• 2011
  • Th. Preud'Homme, J. Sopena, G. Thomas, B. Folliot : “BatchQueue : file producteur / consommateur optimisée pour les multi-cœurs”, 8^e Conférence Française sur les Systèmes d'Exploitation (CFSE'11), Saint-Malo, France, pp. 1-12 (2011)
  • Th. Preud'Homme, J. Sopena, G. Thomas, B. Folliot : “BatchQueue: Efficient core-to-core communication for pipeline parallelism”, ASPLOS 2011 - Sixteenth International Conference on Architectural Support for Programming Languages and Operating Systems, Newport Beach, California, United States (2011)
• 2010
  • Th. Preud'Homme, J. Sopena, G. Thomas, B. Folliot : “BatchQueue: Fast and Memory-thrifty Core to Core Communication”, 22^nd International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2010, Petrópolis, Brazil, pp. 215-222, (The Institute of Electrical and Electronics Engineers, Inc) (2010)
• 2009
  • Th. Preud'Homme, G. Thomas, B. Folliot : “GCKernel : Composition of garbage collectors”, The EuroSys 2009 Doctoral Workshop, Nuremberg, Germany, pp. 1-2 (2009)