NPRG058: Advanced Programming in Parallel Environment

Assignment 1 - Lock-free list

Your objective is to implement a lock-free stack with the following interface:

template <typename T> class LFStack {
public:
    void push(const T &v);
    T pop();
    bool empty() const;
};

Use your knowledge of C++ atomic operations and memory ordering models to ensure the best performance. The solutions will be tested on Parlab only (we do not have more exotic architectures at the moment); however, it should be designed so it can run safely on ARM or PowerPC for instance (i.e., you should not rely on specific hardware properties of x86).

The code starter pack can be downloaded in a ZIP file or copied on parlab from /home/_teaching/advpara/ha1-lf-stack. Use the attached makefile for compilation. The execution will require two parameters (number of threads and number of attempts). For your convenience, here is an example how to run it on parlab:

$> srun -p mpi-homo-short -A nprg058s -n 1 -c 1 make
$> srun -p mpi-homo-short -A nprg058s -n 1 -c 32 ./ha1main 32 100000

Try slightly smaller numbers for debugging, larger for more thorough testing (1,000,000 attempts on 32 threads should take roughly 30 seconds).