Skip to content

README.md

Latest commit

 

History

History
53 lines (38 loc) · 2.57 KB

README.md

File metadata and controls

53 lines (38 loc) · 2.57 KB

High-Performance Software Transactional Memory (STM)

A custom C++ implementation of a Software Transactional Memory (STM) system inspired by the Transactional Locking II (TL2) algorithm. This library provides thread-safe, concurrent reads and writes to shared memory without relying on coarse-grained locks, allowing for high-throughput multi-threaded applications.

Note: The C++ interface (tm.hpp) was provided as part of Concurrent Computing (CS-453) at EPFL. The backend logic, transaction management, and algorithmic optimizations in tm.cpp are my original implementation.

Key Technical Features

  • Versioned Locking (TL2): Uses a global clock and a lock table std::atomic_uint64_t to manage optimistic concurrency control and detect Read-After-Write hazards.
  • Algorithmic Optimizations:
    • Bloom Filters: Transactions use a 64-bit local Bloom Filter to achieve $O(1)$ write-set lookups, drastically speeding up read operations during active transactions.
    • Thread-Local Storage (TLS): Implements a thread-local transaction pool (tx_pool_storage) to recycle transaction objects, minimizing expensive heap allocations during high-contention workloads.
  • Custom Memory Management: Safely handles deferred allocations (tm_alloc) and frees (tm_free), ensuring memory is only modified globally upon a successful commit. Uses a recycle bin for fast reallocation of aborted transaction segments.
  • Hardware-Aware Backoff: Implements exponential backoff using _mm_pause() (x86) or yield (ARM) to optimize CPU pipeline usage during spin-wait scenarios.

Project Structure

TL2-inspired-STM/
├── README.md
├── CMakeLists.txt
├── src/
│   └── tm.cpp           # Core STM implementation (My Code)
├── include/
│   └── tm.hpp           # Provided STM Interface (EPFL)
└── tests/
    └── benchmark.cpp    # Multi-threaded bank account transfer benchmark

Build and Run Instructions

This project uses CMake. A compiler supporting at least C++17 is required.

# 1. Clone the repository and navigate into it
# 2. Create a build directory
mkdir build && cd build

# 3. Generate Makefiles (Enable Release mode for accurate benchmarking)
cmake -DCMAKE_BUILD_TYPE=Release ..

# 4. Compile
make

# 5. Run the benchmark
./benchmark

📊 Benchmarking

The included benchmark simulates high-contention bank transfers across thousands of accounts. It spawns multiple threads attempting concurrent transfers and verifies data consistency at the end of the execution run. STM Scaling Graph