CSC5101 – Advanced Programming of Multicore Architectures

Parallel and Distributed Systems track

TP – Transactional memory

In this lab, we will implement a small runtime for a software transaction memory.

As usually, write a main function that creates N threads, where N is a parameter of the application. The main function has to wait for the termination of the threads before exiting.

We will consider the memory as an array of cells, where each cell contains both a value (an integer) and a counter. For this reason, you have to define the following structures:

We consider that the variable x is the variable at the index of 0 in the array of cells. In each thread, uses this structure to increment 1024*1024 times the x variable with an atomic instruction. Check, at the end of the application, that x has a consistent value (1024*1024 times the number of threads).

Don't forget to write an initialization function that allocate the cells and give them an initial value (0 for the value and 0 for the counter).

Measure, with clock_gettime in CLOCK_MONOTONIC mode, the average time taken by the threads to execute the loop.

Now, add an argument to your application, which will specify the algorithm used to protect the x variable. For this first version, the argument should be equal to atomic. If the protection algorithm is not equal to atomic, your application should terminates with an error.

Add a second version of the loop where you protect the x variable with a pthread_mutex_lock. Check that the application is slower.

Now, we will implement a third version that relies on a software transactional memory. You will have to use this API:
  • void startTX(): starts a transaction,
  • uintptr_t read(int n): read the value of the cell at index n. The read can detect an abort. If it is the case, read has to return a reserved value (MAX_INT for example).
  • void write(int n, uintptr_t value): write the value of the cell at index n,
  • bool commitTX(): commit the transaction if it is possible, and abort it otherwise. The function has to return false in case of abort.
For the moment, just add the function with empty codes. In order to test the transactional memory version, you can use this code:
for(size_t i=0; i<1024*1024; i++) { restart: startTX(); int value = read(0); // read x if(value == MAX_INT) goto restart; write(0, value + 1); // write x + 1 if(!commitTX()) // try to commit goto restart; // in case of abort, restart }

Complete the function in order to implement the algorithm given during the lecture. For that purpose, you will have to define a thread-local structure to store the state of a transaction (_Thread_local). At this step, don't try to free an old cell during a commit (recall that, in order to record a new value in commit, you have to allocate a new cell with a new value and a new counter, and to change atomically the pointer to the cell).

Optional

You can now try to recycle the memory of the old cells during a commit. Technically, when a thread use a cell (for example, when a thread reads a cell during a read operation), you cannot free it in commit. In order to know when you can free a cell, you can reuse the hazard pattern presented in the previous lab.