Implementation of the Michael & Scott Non-Blocking Queue for a Weak Memory Model to compare the performance gains, and check the correctness.

We have implemented the following data structures:

• MS Queue for Strong Memory Model (x86)
• MS Queue for Weak Memory Model (POWER9, Apple Silicon, ARM, etc)

We have model checked using CDSChecker:

• MS Queue for Strong Memory Model (x86) w/o freeing memory
• MS Queue for Weak Memory Model (POWER9, Apple Silicon, ARM, etc) w/o freeing memory

(back to top)

• C++ 11
• CMake
• CPU with weak memory ordering (ex: POWER9, Apple Silicon, ARM...)
• R with ggplot2, tidyr, dplyr and readr packages (Optional: to run the benchmark)

The project was successfully compiled and tested on

• Intel CPU (i9-12900K) with Ubuntu 22.04
• Apple Silicon (Apple M1 Pro) with macOS Monterey 12.6
• POWER9 with Red Hat Entreprise 8.8

On Apple Silicon, linking against the atomics library leads to an error. If you are compiling the code for an Apple Silicon CPU, you should remove the linkage to atomics in the Makefiles and CmakeLists to successfully compile.

To run the benchmark, you can execute the bench.sh script. It will generate a bench.pdf plot and print the average speedup.

The implementation for the strong MS queue is located at src/ms_queue_strong. To run the tests:

1. Go to the directory: cd src/ms_queue_strong
2. Build the project: cmake .; make
3. Run the tests: ./test_seq; ./test_par

The implementation for the weak MS queue is located at src/ms_queue_weak. To run the tests:

1. Go to the directory: cd src/ms_queue_weak
2. Build the project: cmake .; make
3. Run the tests: ./test_seq; ./test_par

We have tested our strong and weak implementations of the MS queue using the Model Checker CDSChecker.

Because CDSChecker does not support atomic operations over datatype larger than 64 bits, we have simplified the algorithm:

• Queue items are 32-bit unsigned integers,
• No deallocation of memory (to prevent ABA issues when removing the Pointer structure).

To run CDSChecker over the strong and weak algorithms, follow those instructions:

1. Go to the directory: cd CDSChecker/ms-queue/ms-queue-strong-no-free
2. Compile the binary: make
3. Run CDSChecker: ./../../run.sh test_2threads -y -m 2

1. Go to the directory: cd CDSChecker/ms-queue/ms-queue-weak-no-free
2. Compile the binary: make
3. Run CDSChecker: ./../../run.sh test_2threads -y -m 2

(back to top)

Alexis Le Glaunec - [email protected]

(back to top)