Project description (CS-453)
September 24, 2024
Contents
1 Software transactional memory 2
1.1 Gentle introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Speciffcation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Possible implementations (in English) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 Using a coarse-lock (i.e. the “reference” implementation) . . . . . . . . . . . . . . . 5
1.3.2 Dual-versioned transactional memory . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 The project 9
2.1 Practical information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Testing and submission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.2 Grading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.3 Other rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Interface of the software transactional memory . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Data structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 Functions to implement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3 Concurrent programming with shared memory 17
3.1 Atomic operations since C11/C++11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Memory ordering in C11/C++11: a quick overview . . . . . . . . . . . . . . . . . . . . . . 17
3.3 From C11/C++11 to the model used in the course . . . . . . . . . . . . . . . . . . . . . . 19
11 Software transactional memory
Your goal is to implement a software transactional memory library.
The project repository (see Section 2.1) contains a very simple reference implementation of such a
library, along with the skeleton for another implementation: the one you’ll have to (design and) code.
The project repository includes the source code for, and a Makeffle to run the program that will evaluate
 your implementation on the evaluation server (provided by the Distributed Computing Laboratory).
But ffrst, let’s informally describe what a (software) transactional memory is, and why it can be useful.
1.1 Gentle introduction
Let me introduce you to Alice. Alice runs a bank. As for any bank today, her system must be able to
process electronic orders. And it should be fast (Alice’s bank is very successful and has many customers).
At least two decades ago, to increase the system throughput, Alice could have only needed to buy
newer hardware, and her program would run faster. But 15–20 years ago, this free lunch ended [1]: Alice
now has to use the computational power of several hardware threads to get the most of modern processors.
This is where a transactional memory can come in handy, and where you step in to help Alice.
Alice’s program is currently written to run on a single thread. When Alice runs her code on her
single-core processor (no concurrency), it runs as expected.
For instance, let’s say that two customers, Bob and Charlie, want to transfer money: both Bob and
Charlie wants to wire each other (and they did not agree beforehand on “who owes who” to make only
one transfer. . .). The pseudo-code for the “money transfer” function could be the following:
shared accounts as integer[];
fn transfer(src, dst, amount) {
if (accounts[src] < amount) // Not enough funds
return; // => no transfer
accounts[dst] = accounts[dst] + amount;
accounts[src] = accounts[src] - amount;
}
Bob wants to send 10 CHF to Charlie, and Charlie 15 CHF to Bob. Since there is only one hardware
thread, each transfer will naturally be processed one after the other. That is, if Bob’s request was
received just before Charlie’s request:
Bob 12 CHF
Charlie 10 CHF
−−−−−−−−→
Bob’s request
Bob 2 CHF
Charlie 20 CHF
−−−−−−−−−−→
Charlie’s request
Bob 17 CHF
Charlie 5 CHF
Another possible execution, if instead Charlie’s request was processed ffrst by Alice’s banking system:
Bob 12 CHF
Charlie 10 CHF
−−−−−−−−−−→
Charlie’s request
Bob 12 CHF
Charlie 10 CHF
−−−−−−−−→
Bob’s request
Bob 2 CHF
Charlie 20 CHF
Even if Bob may not be very happy with this second possible outcome, it is still a consistent execution
as far as the speciffcation of the bank is concerned: when the funds are insufffcient, no transfer happens.
Now, Alice wants to try her program (by assumption correct on a single-core processor) on brandnew,
 multi-core hardware. This way her system will be able to process transfers concurrently, (hopefully)
answering her customers faster. So Alice, for testing purposes, runs the same program on multiple
threads, each taking customer requests as they come. To analyze what outcomes are possible when two
threads process the two respective transfers from Bob and Charlie in concurrence, we will rewrite the
pseudo code to highlight each shared memory access, and in which order they are written in the program:
fn transfer(src, dst, amount) {
let v0 = accounts[src]; // 0th read
if (v0 < amount) // Not enough funds
return; // => no transfer
let v1 = accounts[dst]; // 1st read
accounts[dst] = v1 + amount; // 1st write
let v2 = accounts[src]; // 2nd read
accounts[src] = v2 - amount; // 2nd write
}
2We assume that this pseudo-code runs on a pseudo-machine with atomic register
1
, and that this
pseudo-machine does not reorder memory accesses
2
: memory is always accessed in the same order as
written in the program, and there exist a total order following which each atomic memory access happens.
Supposing the account of Bob is at index 0 in accounts, and the account of Charlie at index 1, a possible,
concurrent execution is then (for clarity, v0, v1, v2 have been replaced by accounts[. . . ]):
Bob request’s thread Charlie request’s thread
0th read 12 == accounts[0]
1st read 10 == accounts[1]
1st write accounts[1] = 20
0th read 20 == accounts[1]
1st read 12 == accounts[0]
2nd read 12 == accounts[0]
2nd write accounts[0] = 2
1st write accounts[0] = 27
2nd read 20 == accounts[1]
2nd write accounts[1] = 5
Figure 1: A concurrent execution that leads to an inconsistent state.
Under this concurrent execution, starting from Bob and Charlie having respectively 12 + 10 = 22
CHF in total on their bank accounts, they end up with a total of 27 + 5 = 32 CHF. Oups! Alice’s system
involutarily “offered” 10 CHF to Bob, by letting the thread from Charlie’s request overwrites (in this
speciffc execution) the deduction of 10 CHF made by the thread concurrently handling Bob’s request.
From the standpoint of the speciffcation of the bank, this is an inconsistency.
A possible immediate solution could be to use a mutual exclusion mechanism, i.e. a lock:
fn transfer(src, dst, amount) {
lock accounts { /* Only one thread at a time can enter this block:
...concurrent threads wait until no thread is in this block */
let v0 = accounts[src]; // 0th read
if (v0 < amount) // Not enough funds
return; // => no transfer
let v1 = accounts[dst]; // 1st read
accounts[dst] = v1 + amount; // 1st write
let v2 = accounts[src]; // 2nd read
accounts[src] = v2 - amount; // 2nd write
}
}
Such a mechanism would prevent the execution from Figure 1, as only one thread accessing the shared
variable accounts can run at any given time. But this mechanism also prevents multiple threads from
processing transfers concurrently. Alice wanted to use multiple cores speciffcally to process multiple
requests at the same time, answering faster her (many) customers. Always taking a single, coarse lock
when accessing the shared memory is thus not a satisfying solution.
Actually, Alice noticed that some transfers can always run concurrently, without the need for any
synchronization. For instance, if Bob wires Charlie and Dan wires Erin at the same time, no ordering
 of memory accesses can lead to an inconsistency. This is simply because the two sets of shared
memory segments respectively accessed by these two transfers, i.e. {accounts[0], accounts[1]} and
{accounts[2], accounts[3]}, do not overlap
3
: they do not conffict.
This is where the transactional memory is useful: it runs in parallel transactions that do not conffict,
 and synchronizes these which do conffict, (hopefully) allowing to make the most out of multi-core
processors with minimal coding efforts. To get a glimpse of the general ideas behind the interface of the
software transactional memory proposed in this project
4
, let’s rewrite (again) Alice’s pseudo-code:
1The notion of atomic register is taught at the beginning of the course.
2The memory consistency models of modern hardware is outside the scope of this course.
3Also, memory segments that are only read by each thread can overlap without synchronization.
4Please refer to Section 2.2 for a precise deffnition of the interface of the library you have to implement.
3// Initialization of the transactional memory, which holds the accounts
shared tm = new TransactionalMemory(/* ... */);
/* ...Initialize the array of accounts,
at the "start address" of the shared memory... */
fn transfer(src, dst, amount) {
let accounts = tm.get start address() as integer[];
while (true) {
try {
let tx = tm.begin();
if (tx.read(&accounts[src]) < amount) {
tx.commit();
break;
}
tx.write(&accounts[dst], tx.read(&accounts[dst]) + amount);
tx.write(&accounts[src], tx.read(&accounts[src]) - amount);
tx.commit();
break;
} except (RetryTransaction) {
continue;
}
}
}
A transaction is enclosed, between calls to tm.begin and tx.end. Unlike with a lock, these functions
(especially begin) may not block, allowing for concurrent executions.
Reads and writes (and allocs and frees) onto the shared memory are all controlled by the software
transactional memory library: Alice’s code is not allowed to e.g. directly read accounts[dst]. Instead,
a call to tx.read must be made (tx.write, tx.alloc, tx.free for other operations). Notably, each of
these operations can abort, requesting the caller to try again the same transaction.
1.2 Speciffcation
The software transactional memory library sees and controls every access to the shared memory. The
library can delay execution, return two different values when reading the same address from two different,
concurrent transactions, etc. Basically, the goal of the library is to make concurrent transactions appear
as if they were executed serially, without concurrency. (In the course, this notion is called opacity.) Also,
once a transaction successfully committed, its modiffcations must be visible in subsequent transactions.
A software transactional memory library that achieves this goal will be deemed correct.
Think of the serial executions of Bob’s and Charlie’s concurrent transfers (in Section 1.1): either the
request from Bob was processed ffrst, not seeing any modiffcation from Charlie’s request, or the opposite.
They executed one after the other. Also, if Bob makes a new transaction (e.g. requesting its account
details) after these two transactions committed, Bob must see both of their outcomes on his screen.
We can deffne three notions which, taken together, would satisfy the (informal) goal described above.
These notions are: snapshot isolation, atomicity, and consistency. Namely:
ˆ Snapshot isolation ensures that: (1) no write/alloc/free
5
in any non-committed transaction can
be read/become available/unavailable in any other transaction, (2) all the reads/writes/allocs/frees
made in a transaction appear to be made from the same atomic snapshot of the whole shared
memory, excepted for (3) a transaction observes its own modiffcations (i.e. writes/allocs/frees).
Example: if snapshot isolation had been satisffed in Figure 1, as Charlie’s transaction already read
v1 == 12, then the 2
nd
read from Charlie’s thread could not have read v2 == 20, which either: (1)
is the effect of a write in a non-committed transaction, if Bob’s transaction had not committed, or
(2) belongs to a different snapshot, if Bob’s transaction had committed between the two reads.
ˆ Atomicity ensures that all the memory writes/allocs/frees of any committed transaction seem to
have all happened at one indivisible point in time.
Example: without atomicity, Bob’s transaction could successfully commit, and another transaction
(e.g. Charlie’s transaction) could take a snapshot where only one of the two writes had been made.
5When Alice’s program calls tx.free, the transactional memory library is not required to immediately call libc’s free.
4ˆ Consistency ensures, for a committing transaction T, that: (1) none of the transactions that
committed since the atomic snapshot of T (a) freed a segment of memory read or written by T or
(b) allocated a segment that overlaps with a segment allocated by T, and (2) each read made by T
in its snapshot would read the same value in a snapshot taken after the last
6
committed transaction.
Example: let’s consider again Figure 1. Both Bob’s and Charlie’s transactions run concurrently with
(in this example) the same snapshot: Bob has 12 CHF and Charlie 10 CHF. It is consistent for Bob’s
transaction to commit ffrst, as there has been no committed transaction since Bob’s transaction
begun and thus the shared memory remained the same since the snapshot of Bob’s transaction.
Regarding Charlie’s committing transaction, which reads memory locations that were modiffed since
its atomic snapshot, it would not be consistent to commit: Charlie’s transaction must be retried
7
.
Now if we consider the other example of Bob wiring Charlie while Dan wires Erin, it would be
consistent for both transactions to commit, since they accessed different words of the shared memory.
Side notes:
ˆ There are several deffnitions of consistency in the literature. Here we provide a sensible deffnition
for this project, while being arguably more precise/speciffc/actionable than some other existing
deffnitions (e.g. “Data is in a consistent state when a transaction starts and when it ends.” [3]).
ˆ Point (3) of snapshot isolation is usually found in consistency.
1.3 Possible implementations (in English)
This section describes the reference implementation and a possible transactional memory for this project.
You are free to implement any other software transactional memory (see the rules in Section 2.1.3). More
ideas can be found while studying:
ˆ TinySTM: https://github.com/patrickmarlier/tinystm
ˆ LibLTX: https://sourceforge.net/projects/libltx
ˆ stmmap: https://github.com/skaphan/stmmap
1.3.1 Using a coarse-lock (i.e. the “reference” implementation)
This implementation is very simple to describe: the transactional memory library uses a single mutex to
(trivially) serialize transactions made onto the shared memory.
When a transaction begins (i.e. tm.begin is called), the single mutex is taken. When the transaction
ends, it always commits (i.e. never retries), and the single mutex is released. Read, write, allocation and
deallocation operations are directly mapped to reading/writing the memory at the requested addresses,
and essentially calling libc’s malloc/free
8
.
This approach is obviously correct, as it directly consists in both (1) executing transactions serially
and (2) ensuring new transactions see all the writes/allocs/frees from the last committed transaction.
From the prism of the three notions laid above, snapshot isolation is guaranteed because no (concurrent)
 transaction can run to observe the memory effects of the pending transaction holding the lock,
until the pending transaction commits, and so, releases the lock. Atomicity is directly guaranteed by the
lock, and ditto for consistency, since there cannot be two transactions running concurrently: the pending
transaction is the only one able to alter the state of the shared memory.
1.3.2 Dual-versioned transactional memory
This transactional memory is only provided as a suggestion. You are free to look for other implementations
in the litterature. It is not the fastest possible for the grading workload
9
, and not even the simplest you can
implement. You thus have two choices: 1) be guided and follow the pseudocode in this document, which
will get you an STM that requires a good amount of non-trivial optimizations to get the maximum grade,
6The set of committed transactions must be linearizable, and for any valid linearization, the last committed transaction
for any (but the ffrst) transaction T is simply the transaction that is considered to have happened right before T.
7As long as tm end (see Section 2.2) for Bob’s transaction has not returned control, an implementation could as well,
without violating linearizability, make Bob’s transaction abort and instead let Charlie’s transaction commit.
8The implementation also needs to keep track of the allocated segments, to prevent any memory leak: see Section 2.2.
9Any reasonably optimized implementation will nevertheless be faster than the reference.
52) explore the world of transactional memories by yourself and implement a more efficient algorithm such
as TL2 or LSA, which should make getting the maximum grade easier. If you want to get help from the
TAs, and are not that much of an explorer, it is recommended you stick with the algorithm described
below. Also, only the high-level concepts and logic will be presented. Low-level details and optimizations,
e.g. actual memory layouts, are omitted on purpose, and for you to find.
Through the use of a very basic multiversionning scheme, this implementation aims at making sure
read-only transactions can both: run concurrently with read-write transactions, and never fail. Two copies
of every (aligned) word of the size of the requested alignment (see Section 2.2.2) are kept. When a transaction
reads/writes words in shared memory, the transactional library has to decide for each word which
of the two copies must be read/written, or if none can be read/written and the transaction must abort.
One key structure that can considerably simplify the design (at the expense of performance though)
is what we will call the Thread Batcher (or more simply, the Batcher ). The goal of the Batcher is to
artificially create points in time in which no transaction is running. This goal might sound uncanny, but
it is not: a mere mutex, as the one used in the reference implementation, creates such points in time.
Indeed, when the transaction that got the global lock releases it, no transaction is running.
You can think of the Batcher as a special kind of mutex: while a mutex lets only one blocked thread
enter and leave no matter how many threads were blocked waiting, the Batcher lets each and every
blocked thread(s) enter together when the last thread (from the previous batch) leaves. So the interface
of the Batcher is pretty much the same as the one of a mutex: enter and leave (analogous to lock and
unlock), and one special function called get epoch that can only be called by a thread after it entered
(and before it leaved) the Batcher. get epoch returns an integer that is unique to each batch of threads
(e.g. a counter, incrementing when the last thread of each batch leaves, would do well).
Batcher pseudo-code, assuming all functions execute in one indivisible point in time (they are atomic):
Data: counter : integer, remaining: integer, blocked: list of threads
fn get epoch()
return counter;
end
fn enter()
if remaining = 0 then
remaining = 1;
else
append current thread to blocked;
wait until “woken up”;
end
end
fn leave()
decrement remaining by 1;
if remaining = 0 then
increment counter by 1;
remaining = length of blocked;
“wake up” every thread in blocked;
empty list blocked;
end
end
With this implementation, each shared memory region holds one instance of Batcher. When a transaction
begins on a shared memory region, enter must be called. Symmetrically, when a transaction ends
(no matter if it committed or aborted), leave must be called as its last action.
At this point, we have “batched” transactions running onto the shared memory region. We will call
an “epoch” the time span during which each batch of transactions runs.
With our dual-versioned implementation, each segment of n word(s) (the size of a word here is the
requested alignment) is duplicated, and for each word there is a control structure to decide which version
to read/write, or if the transaction must abort. A schematic representation of one segment is given below:
6word 0 word 1 word 2 word 3
control control control control
copy A copy A copy A copy A
copy B copy B copy B copy B
. . .
For the sake of the presentation laid below, the word indexes above (i.e 0, 1, . . . ) will be assumed unique
for the whole shared memory region: there are no two words in the same region that have the same index.
The control structure contains the following pseudo-fields10:
ˆ Which copy is “valid” from the previous epoch (i.e. either A or B).
This copy will be called the “readable copy”, and the other copy will be called the “writable copy”.
ˆ The “access set” of read-write transaction(s) which have accessed the word in the current epoch.
Do not implement an actual set in any (optimized) implementation: this set will only be used to tell
whether a transaction can write to the word. Namely, if at least one other transaction has accessed
(i.e. read or written) this word in the same epoch, the write cannot happen. Said differently, if two
transactions are in the access set, it doesn’t matter which one they are.
ˆ Whether the word has been written in the current epoch.
The pseudo-code of the read/write/alloc/free/commit operations (+ 2 helper functions) can then be:
fn read word(index, target)
if the transaction is read-only then
read the readable copy into target;
return the transaction can continue;
else
if the word has been written in the current epoch then
if the transaction is already in the “access set” then
read the writable copy into target;
return the transaction can continue;
else
return the transaction must abort;
end
else
read the readable copy into target;
add the transaction into the “access set” (if not already in);
return the transaction can continue;
end
end
end
10Your implementation may not declare a control structure with this exact list of fields or with the exact same semantic:
your implementation should probably have more fields, with adjusted semantic, for the purpose of optimization. Moreover,
multiple fields can be merged using bit fields.
7fn write word(source, index)
if the word has been written in the current epoch then
if the transaction is already in the “access set” then
write the content at source into the writable copy;
return the transaction can continue;
else
return the transaction must abort;
end
else
if at least one other transaction is in the “access set” then
return the transaction must abort;
else
write the content at source into the writable copy;
add the transaction into the “access set” (if not already in);
mark that the word has been written in the current epoch;
return the transaction can continue;
end
end
end
fn read(source, size, target)
foreach word index within [source, source + size[ do
result = read word(word index , target + offset);
if result = transaction must abort then
return the transaction must abort;
end
end
return the transaction can continue;
end
fn write(source, size, target)
foreach word index within [target, target + size[ do
result = write word(source + offset, word index );
if result = transaction must abort then
return the transaction must abort;
end
end
return the transaction can continue;
end
fn alloc(size, target)
allocate enough space for a segment of size size;
if the allocation failed then
return the allocated failed;
end
initialize the control structure(s) (one per word) in the segment;
initialize each copy of each word in the segment to zeroes;
register the segment in the set of allocated segments;
return the transaction can continue;
end
fn free(target)
mark target for deregistering (from the set of allocated segments)
and freeing once the last transaction of the current epoch leaves
the Batcher, if the calling transaction ends up being committed;
return the transaction can continue;
end
8fn commit()
foreach written word index do
defer the swap, of which copy for word index is the “valid”
copy, just after the last transaction from the current epoch
leaves the Batcher and before the next batch starts running;
end
return the transaction has committed;
end
As for the Batcher pseudo-code, we assume the functions outlined above all execute atomically. This
means that the execution of a function should not be affected by the concurrent execution of other
functions. Practically, this implies that you should use synchronization primitives to control the access
to shared variables. Numerous implementation details, e.g. how to access the control structure of each
word, how to keep track of the allocated segments, etc, are intentionally left completely unspecified.
For reference: (very optimized) implementations can reach speedups above ×2.5 against the grading
workload, and the implementation of the TA is less than 1000 lines long (all comments and spaces
included). The proposed algorithms can be extended with speculative execution of read-only transactions
(for you to figure out) to get a higher speedup or to compensate for the lack of optimizations. You should
look for such optimizations after getting an initial version that works correctly.
2 The project
You are expected to be reasonably fluent in C11 or C++17 for this project. Picking one or the other
shouldn’t impact the performance of your implementation (granted you don’t use overly expensive abstractions).
Pick the one you’re the most familiar with. If you’re unsure, we advise you to stick to C11.
A (very brief) introduction to the memory model of C11/C++11, along with available atomic operations,
are provided in Section 3.
2.1 Practical information
This project is associated with a git repository, hosted on GitHub. It will be available at https://
github.com/LPD-EPFL/CS453-2024-project when the semester starts. Its layout is the following:
grading/ Directory containing the source code of the evaluation program, to test your solution on
your own machine. The evaluation server (see below) runs the exact same binary, possibly with a
different seed. Section 2.1.1 further details how to test and later submit your code.
include/ C11 and C++17 header files that define the public interface of the STM.
template/ Template (in C11) of your implementation, but you are free to replace everything and
write C++17 instead. See section 2.1.3 for more information.
reference/ Reference, single lock-based implementation (see Section 1.3.1).
Note that you are not allowed to write an implementation that is equivalent to this reference
implementation. See section 2.1.3 for more information.
sync-examples/ Examples of how to use synchronization primitives (locks, condition variables and
atomics).
The specification of the evaluation server, on which your submission will be run, are the following:
CPU Virtualized Intel(R) Xeon(R) E5-2680: 24 cores at 2.80GHz
RAM 128 GB
OS GNU/Linux (distribution: Ubuntu 24.04)
2.1.1 Testing and submission
At this point, you should have received your unique (and secret) user identifier by mail.
If not, ask the TAs as soon as possible: without this identifier, you cannot submit your implementation.
The proposed workflow is the following:
91. Clone/download the repository.
2. Make a local copy of/rename the template directory with your SCIPER number:
you@your-pc:/path/to/repository$ cp -r template 123456
Be aware make is sensitive to spaces in the path/names.
3. Complete or completely rewrite (your copy of) the template with your own code.
(a) Complete/rewrite your code; only the interface should be kept identical.
(b) Compile and test locally with:
you@your-pc:/path/to/repository/grading$ make build-libs run
(c) Send your code for testing on the evaluation server; see below.
(d) Repeat any of the previous steps until you are satisfied with correctness and performance.
The procedure to send your code for evaluation is the following:
1. Zip your modified (copy of the) template directory (not directly its content).
2. Send your code for evaluation with the submit.py script:
you@your-pc:/path/to/repository$ python3 submit.py --uuid <. . .> 123456.zip
The UUID (Unique User IDentifier) to use is the one you should have received by mail.
Your request will be queued on the evaluation server, and you will receive the results of both the compilation
and the execution of your implementation (including its speedup vs the reference one) as soon as
it finishes running. You can submit code as often as you want until the deadline.
Only the (correct) submission with the highest speedup will be stored persistently and considered for
grading, so no need to resubmit your best implementation just before the deadline. The TAs may still
ask you to provide a copy of your best implementation though (possibly after the deadline), so do not
delete anything before the end of the semester (2025-01-30).
As an option from the submit.py script, you can force-replace your submission with another one. In
this case no compilation nor performance check is performed. The submission script also allows you to
download the submission considered for your grade, so you can make sure the system has the version you
want to be considered for grading. You can display the command-line help for this tool with:
you@your-pc:/path/to/repository$ python3 submit.py -h
Also note that the automated submission system has no false negative, i.e. a correct implementation
will always be deemed correct; unless it is more than 16 times slower than the reference (see Section
2.1.2).
On the other hand, the system has false positive (i.e. incorrect implementations deemed correct).
Unless your submission includes portions of code that appear to be specifically designed to trick the
submission system into considering an incorrect implementation correct, if the submission system qualifies
your implementation as correct, it will be graded as a correct one.
2.1.2 Grading
Correctness is a must
The executed transactions must satisfy the specification (sections 1.2 and 2.2).
No correctness ⇒ no “passing” grade for the project (i.e. grade < 4).
Performance is required to get the maximum grade
The only considered metric is the number of transactions committed per second.
Providing a correct implementation guarantees you at least a grade of 4 for the project, although an
implementation that is at least 16 times slower than the reference (coarse lock-based) implementation
will not be deemed correct , regardless of whether a longer execution time would have allowed it to finish.
Please also note: an implementation that leaks memory will have its grade capped at 5.
Given its speedup relative to the reference, the grade of a correct implementation (that does not leak) is:
10Speedup s Grade g
s < 1/16 g < 4
s ∈ [
1/16, 1] g = 4 + 16s−1
15
s ∈ [1, 2.5] g = 5 + 2s−2
3
s > 2.5 g = 6
For reference, the maximum speedup obtained on this project is ×15.04 with an optimized (algorithmwise)
version of TL2. The associated implementation consisted in about ∼600 lines of C++17 (including
comments).
2.1.3 Other rules
The deliverable is to be written either in C11 or in C++17. The provided template code is written in
C11, and you can overwrite it completely if you deem it necessary. In case you want to develop in C++17
instead of C11, you should use the associated #include <tm.hpp> instead of #include <tm.h>.
You can use any external library, as long as they do not solve a concurrent programming problem.
One exception to this rule is if the external library you want to use only solves elementary concurrent
programming problems, e.g. the library implements mutexes and condition variables. If you are in doubt
whether you can use a specific library, please ask the TAs. Please keep in mind a few limitations though:
ˆ The size of each submission is limited to 100 kB (both compressed and uncompressed), so you
cannot only include in your submission libraries that are limited in size.
ˆ The compilation time is limited to 10 s.
Note that you are not allowed to write an implementation that is equivalent to the reference implementation,
i.e., that uses a single global lock to serialize transactions; even if this lock is a readers-writer lock
instead of a classic mutex. Any implementation that never allows any read-write transactions to execute concurrently will be deemed equivalent to the reference, no matter how intricated the locking mechanism is.
When in doubt, ask the TAs right away for clarifications.
You may read and take inspiration from existing STM libraries (see Section 1.3), and collaborate with
other students (e.g. share ideas, help debug each others’ code, etc). But at the end of the day it must be
your own code that carries out transactions in your submission.
2.2 Interface of the software transactional memory
To use this Software Transactional Memory (STM) library, the user of the library (i.e. Alice, or more
specifically here, the grading tool) first creates a new shared memory region . A shared memory region
is a non-empty set of non-overlapping shared memory segments . Shared memory region creation and
destruction are respectively managed by tm create and tm destroy. A shared memory region is always
created with one first, non-deallocable shared memory segment. Additional shared memory segments
(de)allocation are managed by tm alloc and tm free. The content of a shared memory regions can only
be accessed from inside a transaction, and solely by using the functions described in Section 2.2.2.
A transaction consists of a sequence of tm read, tm write, tm alloc, tm free operations in a shared
memory region, enclosed between a call to tm begin followed later by a call to tm end. A transaction
cannot access more than one shared memory region11. A transaction either commits its speculative
updates to the shared memory region when tm end is reached, or aborts and discards its speculative
updates (see Section 2.2.2). When a transaction is aborted, the user (i.e. the grading tool in this project)
is responsible for retrying the same transaction (i.e. going back to the same tm begin call site).
2.2.1 Data structures
The interface of the transactional memory library is composed of three data structures:
ˆ shared t: an opaque handle representing a shared memory region
ˆ tx t: an opaque handle representing a pending transaction on a shared memory region
11You may notice that the grading tool will actually create only one memory region. But your library should be able to
handle several distinct regions, and thus not use e.g. global variables to track transactional states.
11ˆ void*: a pointer in shared memory to the first word of a shared memory segment
Shared memory segments are (de)allocated like with malloc/free: tm alloc returns the address of the
first word, which is also the address to pass to tm free to free the segment. Words on the segment are
addressed as with C/C++ arrays, by adding an offset to the address of the first word of the segment. And
of course, the user will call tm read/tm write instead of directly performing reads/writes. This means
that you are free to put in place any naming scheme to address locations (i.e., words) within a shared
memory region as long as it supports pointer arithmetic and it fits in a void*. Whether words within a
shared memory region are addressed with valid virtual addresses is up to you. Moreover, you can assume
that allocated segments are at most 248-byte long.
Note that, since the layout of the structures pointed to by shared t, tx t, and void* (as a pointer to
a word on a shared memory segment) are all opaque to the user, you are free to design their internals the
way you want. Feel free to take some inspiration from how the reference implemented these structures.
2.2.2 Functions to implement
shared t tm create(size t size, size t align)
Create (i.e. allocate + init) a new shared memory region, with one first allocated segment of
the requested size and alignment.
Parameter Description
size Size of the first allocated segment of memory (in bytes), must be
a positive multiple of the alignment and at most 248
align Alignment (in bytes, must be a power of 2) that the shared memory
region must provide, and that each memory access made on
this shared memory region will have to satisfy
Returns: Opaque shared memory region handle, invalid shared on failure.
Additional comments:
ˆ The requested alignment in that function will be the alignment assumed in every
subsequent memory operation.
ˆ The first allocated segment must be initialized with zeroes.
ˆ The first allocated segment cannot be freed with tm free.
ˆ The alignment also defines the size of words, and thus the granularity of the transactional
memory.
ˆ This function can be called concurrently.
12void tm destroy(shared t shared)
Destroy (i.e. clean-up + free) a given shared memory region.
Parameter Description
shared Handle of the shared memory region to destroy
Additional comments:
ˆ No concurrent call for the same shared memory region.
ˆ It is guaranteed that when this function is called the associated shared memory region
has not been destroyed yet.
ˆ It is guaranteed that no transaction is running on the shared memory region when this
function is called.
ˆ The first allocated segment, and all the segments that were allocated with tm alloc
but not freed with tm free at the time of the call, must be freed by this function.
void* tm start(shared t shared)
Get a pointer in shared memory to the first allocated segment of the shared memory region.
Parameter Description
shared Handle of the shared memory region to query
Returns: Pointer in shared memory to the first word of the first allocated segment.
Additional comments:
ˆ This function can be called concurrently.
ˆ The returned address must be aligned on the shared region alignment.
ˆ This function never fails: it must always return the address of the first allocated
segment, which is not free-able.
ˆ The returned pointer must not be NULL (or nullptr in C++), and must not change
between invocations.
size t tm size(shared t shared)
Get the size to the first allocated segment of the shared memory region.
Parameter Description
shared Handle of the shared memory region to query
Returns: Size (in bytes) of the first allocated segment.
Additional comments:
ˆ This function can be called concurrently.
ˆ The returned size must be a multiple of the shared region alignment.
ˆ This function never fails: it must always return the size of the first allocated segment,
which is not free-able.
ˆ The size of the first allocated segment is a constant, set with tm create.
13size t tm align(shared t shared)
Get the required alignment for memory accesses on the shared memory region.
Parameter Description
shared Handle of the shared memory region to query
Returns: Alignment used for this shared memory region (in bytes).
Additional comments:
ˆ This function can be called concurrently.
ˆ The alignment of the shared memory region is a constant, set with tm create.
tx t tm begin(shared t shared, bool is ro)
Begin a new transaction on the given shared memory region.
Parameter Description
shared Shared memory region to begin a transaction on
is ro Whether the transaction will only perform read(s)
Returns: Opaque transaction handle, invalid tx on failure.
Additional comments:
ˆ This function can be called concurrently.
ˆ There is no concept of nested transactions, i.e. one transaction begun in another transaction.
ˆ
If is ro is set to true, then only tm read will be called from this transaction.
bool tm end(shared t shared, tx t tx)
End the given transaction.
Parameter Description
shared Shared memory region associated with the transaction
tx Transaction to end
Returns: true: the whole transaction committed, false: the transaction must be retried
Additional comments:
ˆ This function can be called concurrently, but concurrent calls must be made with at
least a different shared parameter or a different tx parameter.
ˆ This function will not be called by the user (e.g. the grading tool) if any of tm read,
tm write, tm alloc, tm free already notified that tx was aborted.
14bool tm read(shared t shared, tx t tx, void const* source, size t size, void* target)
Read operation in the transaction, source in the shared region and target in a private region.
Parameter Description
shared Shared memory region associated with the transaction
tx Transaction to use
source Source (aligned) start address (in shared memory)
size Length to copy (in bytes)
target Target (aligned) start address (in private memory)
Returns: true: the transaction can continue, false: the transaction has aborted
Additional comments:
ˆ This function can be called concurrently, but concurrent calls must be made with at
least a different shared parameter or a different tx parameter.
ˆ The private buffer target can only be dereferenced for the duration of the call.
ˆ The length size must be a positive multiple of the shared memory region’s alignment,
otherwise the behavior is undefined.
ˆ The length of the buffers source and target must be at least size, otherwise the
behavior is undefined.
ˆ The source and target addresses must be a positive multiple of the shared memory
region’s alignment, otherwise the behavior is undefined.
bool tm write(shared t shared, tx t tx, void const* source, size t size, void* target)
Write operation in the transaction, source in a private region and target in the shared region.
Parameter Description
shared Shared memory region associated with the transaction
tx Transaction to use
source Source (aligned) start address (in private memory)
size Length to copy (in bytes)
target Target (aligned) start address (in shared memory)
Returns: true: the transaction can continue, false: the transaction has aborted
Additional comments:
ˆ This function can be called concurrently, but concurrent calls must be made with at
least a different shared parameter or a different tx parameter.
ˆ The private buffer source can only be dereferenced for the duration of the call.
ˆ The length size must be a positive multiple of the shared memory region’s alignment,
otherwise the behavior is undefined.
ˆ The length of the buffers source and target must be at least size, otherwise the
behavior is undefined.
ˆ The source and target addresses must be a positive multiple of the shared memory
region’s alignment, otherwise the behavior is undefined.
15alloc t tm alloc(shared t shared, tx t tx, size t size, void** target)
Shared memory segment allocation in the transaction.
Parameter Description
shared Shared memory region associated with the transaction
tx Transaction to use
size Alloction requested size (in bytes) that is at most 248
target Pointer in private memory receiving the address of the first word
of the newly allocated, aligned segment
Returns: success alloc: the allocation was successful and transaction can continue,
abort alloc: the transaction has aborted,
nomem alloc: the memory allocation failed (e.g. not enough memory)
Additional comments:
ˆ This function can be called concurrently, but concurrent calls must be made with at
least a different shared parameter or a different tx parameter.
ˆ The pointer target can only be dereferenced for the duration of the call.
ˆ The value of *target is defined only if success alloc was returned.
ˆ The value of *target after the call if success alloc was returned must not be NULL
(or nullptr in C++).
ˆ When nomem alloc is returned, the transaction is not aborted.
ˆ The allocated segment must be initialized with zeroes.
ˆ Only tm free can be used to free the allocated segment.
ˆ The length size must be a positive multiple of the shared memory region’s alignment,
otherwise the behavior is undefined.
bool tm free(shared t shared, tx t tx, void* target)
Shared memory segment deallocation in the transaction.
Parameter Description
shared Shared memory region associated with the transaction
tx Transaction to use
target Pointer to the first word of the allocated segment to deallocate
Returns: true: the transaction can continue, false: the transaction has aborted
Additional comments:
ˆ This function can be called concurrently, but concurrent calls must be made with at
least a different shared parameter or a different tx parameter.
ˆ This function must not be called with target as the first allocated segment (the
address returned by tm start).
163 Concurrent programming with shared memory
Reference (C/C++): https://en.cppreference.com/w/
ˆ Order of evaluation: https://en.cppreference.com/w/cpp/language/eval_order
ˆ Undefined behavior: https://en.cppreference.com/w/cpp/language/ub
ˆ Atomic types in C11: https://en.cppreference.com/w/c/atomic
ˆ Atomic types since C++11: https://en.cppreference.com/w/cpp/atomic
ˆ Memory model: https://en.cppreference.com/w/cpp/language/memory_model
ˆ Memory order: https://en.cppreference.com/w/cpp/atomic/memory_order
It is very much recommended to at least skim through these references, especially if you had never heard
before about undefined behavior and the sequenced-before rules. These are two C/C++ notions that are
assumed to be known by the student, as these notions are not from concurrent programming.
3.1 Atomic operations since C11/C++11
In C and C++, it is a data race when a thread writes to a memory location concurrently read of written by
another thread, unless both accesses are atomic operations (see below) or one of the conflicting accesses
happens-before the other (see Section 3.2). If a data race occurs, the behavior of the program is undefined.
In C11, with #include <stdatomic.h>, the atomic version of a type T is declared with Atomic T.
Since C++11, with #include <atomic>, it can be declared with ::std::atomic<T>, with T being
TriviallyCopyable, CopyConstructible and CopyAssignable.
In both C11 and C++11 (and above), the operators for these types are overloaded and use atomic
counterparts for these operations. For instance, the increment operator ++x on an atomic object x is
equivalent to calling atomic fetch add(&x, 1) in C, and x.fetch add(1) in C++. As a quick overview:
Common name C function(s) C++ method(s)
Read atomic load .load
Write atomic store .store
Fetch-and-. . . atomic fetch ... .fetch ...
Swap atomic exchange .exchange
Compare-and-Swap atomic compare exchange weak .compare exchange weak
atomic compare exchange strong .compare exchange strong
(The only difference between the weak and strong version of a compare-and-swap is that the weak version
may (spuriously) act as if the stored value was not the expected value, even if they were equal.)
Each of these atomic operations either have: counterparts which names end in explicit and take
one (or two) more parameter(s) (in C11), or defaulted parameters (since C++11). These parameters
specify ordering constraints when the atomic operation is used to synchronize with concurrent threads.
Understanding these notions, and using the ordering parameters, are optional for the project. Memory
ordering is introduced in Section 3.2 only for completeness, and for students interested to know more.
Real uses of these atomic operations are available in the provided repository, in class Sync in file
grading/grading.cpp, and in the two custom definitions of struct lock t in file reference/tm.c.
3.2 Memory ordering in C11/C++11: a quick overview
Understanding this subsection (which is actually just a quick overview) is optional for this project. But
if you are interested on this matter, this section is not enough so here are a few pointers to start with:
ˆ Introduction to lock-free programming
https://preshing.com/20120612/an-introduction-to-lock-free-programming/
ˆ Memory Barriers Are Like Source Control Operations
https://preshing.com/20120710/memory-barriers-are-like-source-control-operations/
ˆ Acquire and Release Fences Don’t Work the Way You’d Expect
https://preshing.com/20131125/acquire-and-release-fences-dont-work-the-way-youd-expect/
17Let’s consider a basic, single-threaded C11/C++11 code snippet:
int a = 0;
int b = 0;
printf("a = %d, b = %d\n", a, b);
a = 1;
printf("a = %d, b = %d\n", a, b);
b = 1;
printf("a = %d, b = %d\n", a, b);
Following the sequenced-before rule (which is very intuitive in this example), we expect to see printed:
a = 0, b = 0
a = 1, b = 0
a = 1, b = 1
Indeed: it is not possible to read a = 0, b = 1 , as a = 1 is sequenced-before b = 1.
Now, let’s split this code snippet, to run it on two concurrent threads:
// Global variables // Thread 1 // Thread 2
int a = 0; a = 1; printf("a = %d, b = %d\n", a, b);
int b = 0; b = 1;
Given that the two global variables are initialized before any of the two thread started running, which
pair(s) of values (a, b) would the second thread be able to print? Answer: any of the following pairs12:
a = 0, b = 0
a = 1, b = 0
a = 1, b = 1
a = 0, b = 1
But why?
A technical reason is that both the compiler and the processor sometimes reorder memory operations.
For instance in the given example, the compiler might see fit to issue the read instruction(s) for b before
the one(s) for a, as the compiler is not constrained (not even by the sequenced-before rules) to read a
before b. The rule of thumb for compiler reordering and optimizations in general might be: “as long as
the result of a single-threaded execution is not altered, (almost) any change is allowed” (the as-if rule).
Hardware reordering can also happen very frequently, depending on the memory model provided by
the architecture your program run on. More on that in specific courses, e.g. CS-471.
These reorderings can become a problem for multi-threaded, concurrent programming though. In
C11 and since C++11, both hardware and compiler reorderings can be explicitly prevented (both at once)
through the use of the ordering parameter(s) in atomic operations or thread fences (a.k.a. barriers).
Similar to the sequenced-before rule, C11 and C++11 introduce several new notions, among which
synchronize-with and happen-before. For a formal description of the whole model, with examples, please
see: https://en.cppreference.com/w/cpp/atomic/memory_order#Formal_description.
Informally, the keystone is that the modifications made to an atomic variable happen in a total order,
on which every thread agrees. (This is not to be confused with a total order between modifications
happening to all the atomic variables.) From this agreement, the remaining step is to prevent some
operations (e.g. reads and/or writes) from being reordered before/after some important atomic operations.
As an example, let’s consider the implementation of a lock. The interface is composed of two functions:
lock and unlock. A lock protects some parts of the shared memory. So, in particular, we do not want
the lock-protected reads to happen before the lock is taken. Ditto for the lock-protected writes: they must
not happen after the lock is released, otherwise the next thread owning the lock could see an inconsistent
view (not all writes visible by the time the lock is taken). So a correct lock implementation could be:
12Actually, this program has two obvious data races: its behavior is technically undefined, (any/no)thing could be printed.
18// Shared lock
using Mutex = ::std::atomic<bool>;
Mutex mutex = false;
void lock(Mutex& mutex) {
bool expected = false;
while (!mutex.compare exchange weak(expected, true,
::std::memory order acquire, ::std::memory order relaxed)) {
expected = false;
while (mutex.load(::std::memory order relaxed)) // Spin wait
pause();
}
}
void unlock(Mutex& mutex) {
mutex.store(false, ::std::memory order release);
}
The use pattern for a thread would then be: (1) lock, (2) read/write shared memory, (3) unlock. The
acquire semantic (third parameter of compare exchange weak, see the documentation for this method)
ensures that a successful compare-and-swap happens-before read operations written after it. Similarly,
the release semantic on the store ensures that all the writes operations written before happen-before
the release. Finally when the lock is released then taken again (by the compare-and-swap), since there
is a total order for all the operations on the mutex, the write operations of the previous lock holder
happen-before any read operation from the new lock holder. The view is consistent.
One last note, regarding the use of thread fences instead of the memory ordering parameters of atomic
operations. Thread fences (a.k.a. barriers) prevent the reordering of reads and writes before/after the
fence. This is (almost) just a change of perspective from using memory ordering parameters: instead of
preventing memory operations from being reordered across a specific atomic operation, the fence prevents
some types of operations (e.g. reads, writes, or both) before/after the fence from being reorder after/before
it. This is slightly more constraining than memory ordering parameter(s) on atomic operations.
3.3 From C11/C++11 to the model used in the course
This section will be very short. In C11 and since C++11, operations with sequential consistency semantic:
ˆ globally follow a total order, and
ˆ happen-before each other in program order,
which is the semantic of the model introduced at the beginning of the course.
Using this semantic, we can correct the (trivial) example given at the beginning of Section 3.2:
// Global variables // Thread 1 // Thread 2
::std::atomic<int> a = 0; a = 1; int x = a;
::std::atomic<int> b = 0; b = 1; printf("a = %d, b = %d\n", x, b);
Since sequential consistency is the default ordering for atomic operations, the second thread will only be
able to print the following pairs:
a = 0, b = 0
a = 1, b = 0
a = 1, b = 1
The pair a = 0, b = 1 cannot be printed anymore, as with sequential semantic, a = 1 happens-before b
= 1, and so does the read a before the read b. Note that the second thread reads a into a local variable
before printing it since, in C/C++, the order of evalutation of parameters in a function call is undefined.

请加QQ：99515681  邮箱：99515681@qq.com   WX：codinghelp