CSE 305 - Tutorial 6 - Fine-grain concurrent sets

File benchmarking_sets.cpp contains the code performing a prescribed number of insertions into the coarse- and fine-grained versions of ListSet and measuring the runtime. You can compile it with make set_benchmarker and run as ./set_benchmarker num_threads num_insertions (for example ./set_benchmarker 2 1000). However, the code provided to you works only for a single thread at the moment.

You are asked to do the following:

• complete the code so that, for every value of the num_threads, it performes the prescribed number of insertions from several threads in parallel;
• collect the runtime data for different number of threads (a bit beyond the number of cores on you machine) and different values of insertions (ranging from 1000 and 50000). Analyze how the performace changes depending on the method, number of threads, and number of insertions (not just qualitatively “larger/smaller” but also more quantitatively “linear/quadratic/constant factor”). Explain the patterns you observe, write the runtimes and your explanations in the comments after the code. If your machine does not have enough cores for an interesting analysis, use the machines in the classroom (you can connect to them by ssh).

Implement a class CoarseBST (full specification in td6.cpp) which is a binary search tree with only addition and containment queries made thread-safe using the coarse-grained locking scheme (cf. the coarse-grained SetList from the lecture). You are asked to implement add and contains methods

Design a version of the SetList class (fine grained version), BoundedSetList, that has fixed capacity, and a thread inserting an element into a set that has reached the capacity and does not contain the element gets blocked (using condition variable, not busy waiting!). Note that the data structure should be still fine-grained, that is, the mutex count_lock should be taken only at the moment of actual insertion. If at this point the capacity has already reached, you should unlock everything and wait for the empty space to appear, and start the insertion all over. For further details, see td6.cpp.