Minor Thesis - Development and Analysis of Barrier Protocols

A year ago, I defended my minor thesis (equivalently bachelor thesis or Großer Beleg) (PDF download). The repository, including smaller course work on similar topics from before, is on GitHub: https://github.com/hydroo/barrier.

Thesis

Contents

• 1/2 Intro/Background
• Cache coherency and atomic operations don't scale
• Probabilistic synchronization is a good idea
• Survey of currently used barrier protocols and of general ways to implement barriers
• Detailed look at MPI 3's remote memory access API for implementing less deterministic barrier/synchronization protocols
• 3 Three Novel Barrier Protocols
• MGB Barrier: Inspired by Nicholas Mc Guire
• B1 Barrier: The opposite of the Central Counter Barrier
• B2 Barrier: Variant of the B1 Barrier that computes more and communicates less
• 4 Evaluation
• Central Counter Barrier vs B1 Barrier
• Dissemination Barrier vs B2 Barrier
• Some high-level observations about the four protocols
• Verify correctness of the protocols via model checking
• Compare the speed and energy consumption of the four barriers using quantitative model checking

Personal Comment

Sadly, I had to prioritize model checking over measurement-based analysis.
Therefore, I have little confidence in the quantitative model checking results. Aside from that, I quite like the thesis, and think there are valuable ideas in there. Especially:

• The so-called progress problem that most barriers have. It is explained in Section 4.1.
• The B1 and B2 Barrier can be faster than every other barrier protocol. Depending on the computation speed and communication latency different variants of them should be used. They avoid the progress problem. They have their weaknesses, too. More analysis is required to definitely state if the additional resource requirements outweigh the speed advantage.
• The so-called barrier building blocks (Section 2.3)

Repository

Abstract

This is a semi-organized repository of ~1 year of university work. During this time I:

• Surveyed existing barrier protocols
• Surveyed actual implementations
• Surveyed what low-level tools are available to develop synchronization primitives, and in particular barriers
• Invented new protocols
• Analyzed/modelchecked/benchmarked them
• In-depth look at MPI 3's remote memory access API and its suitability for implementing (less deterministic) barriers and other synchronization protocols

License

Everything is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 license. If this licensing scheme is a problem for your intentions, please contact me. I'm open to suggestions.

Why upload the whole thing?

• Because there are few reasons not to
• I would oftentimes be very happy, if I could dig through the source code of someone's research
• For people interested in researching barrier protocols and synchronization primitives in general
• For the useful code snippets contained
• As a portfolio entry so potential employers can see what I did and how I did it