Monday, June 2, 2014

Fine-Grained Linked List with Execution Time Analysis

Fine-grained linked list

Source code

class NODE {
public:
    int key;
    NODE *next;
    mutex nodelock;

    NODE(int v) {
        key = v;
        next = nullptr;
    }
    NODE() {
        next = nullptr;
    }
    void lock()
    {
        nodelock.lock();
    }
    void unlock()
    {
        nodelock.unlock();
    }
};

class FLIST{
private:
    NODE head, tail;
public:
    FLIST(){
        head.key = 0x80000000;
        tail.key = 0x7FFFFFFF;
        head.next = &tail;
    }
    void Init(){
        while (head.next != &tail) {
            NODE *temp = head.next;
            head.next = head.next->next;
            delete temp;
        }
    }
    bool Add(int x)
    {
        NODE *pred, *curr;
        head.lock();
        pred = &head;
        curr = pred->next;
        curr->lock();
        while (curr->key < x) {
            pred->unlock();
            pred = curr;
            curr = curr->next;
            curr->lock();
        }

        if (curr->key == x) {
            curr->unlock();
            pred->unlock();
            return false;
        }
        else {
            NODE *node = new NODE(x);
            node->next = curr;
            pred->next = node;
            curr->unlock();
            pred->unlock();
            return true;
        }
    }
    bool Remove(int x)
    {
        NODE *pred, *curr;
        head.lock();
        pred = &head;
        curr = pred->next;
        curr->lock();
        while (curr->key < x) {
            pred->unlock();
            pred = curr;
            curr = curr->next;
            curr->lock();
        }

        if (curr->key == x) {
            pred->next = curr->next;
            curr->unlock();
            pred->unlock();
            delete curr;
            return true;
        }
        else {
            curr->unlock();
            pred->unlock();
            return false;
        }
    }
    bool Contains(int x)
    {
        NODE *pred, *curr;
        head.lock();
        pred = &head;
        curr = pred->next;
        curr->lock();
        while (curr->key < x) {
            pred->unlock();
            pred = curr;
            curr = curr->next;
            curr->lock();
        }

        if (curr->key == x) {
            curr->unlock();
            pred->unlock();
            return true;
        }
        else {
            curr->unlock();
            pred->unlock();
            return false;
        }
    }
};

The provided source code implements a fine-grained synchronization linked list, where each node in the list is protected by a mutex to ensure thread safety. This approach locks individual nodes during operations to allow multiple threads to operate on different parts of the list concurrently, thus improving performance over coarse-grained locking techniques that lock the entire list.

Key Concepts in the Code:

  1. Fine-Grained Locking:

    • In fine-grained synchronization, each node has its own lock (nodelock), which allows more fine-tuned control over concurrency. This way, different threads can work on different nodes simultaneously, as long as they are not accessing the same node.

  2. Node Structure:

    • The NODE class contains:
      • key: the value of the node.
      • next: pointer to the next node in the list.
      • nodelock: a mutex used for locking the node during operations.

  3. Locking and Unlocking:

    • The lock and unlock methods ensure that no other thread can modify a node while it is being operated on, preventing race conditions and maintaining consistency.

  4. Add:

    • The Add method inserts a new node with the key x into the list. It locks the predecessor and current nodes, checks if the node already exists, and if not, adds the new node.

  5. Remove:

    • The Remove method removes the node with the key x from the list. It locks the predecessor and current nodes, checks if the node to be removed exists, and if so, removes it and deletes the node.

  6. Contains:

    • The Contains method checks if a node with the key x exists in the list. It locks the predecessor and current nodes and verifies if the key exists.

Execution Time Analysis:

The execution times of the fine-grained linked list under different thread loads are measured. Here’s the performance table:

Number of ThreadsExecution Time (ms)
1 Thread7074ms
2 Threads6680ms
4 Threads6817ms
8 Threads80780ms
16 Threads81509ms

Key Insights:

  1. Performance Scaling:
    • As the number of threads increases from 1 to 2, the execution time decreases, indicating that fine-grained synchronization provides some benefit in reducing contention for the nodes.
  2. Performance Degradation at Higher Thread Counts:
    • As the number of threads increases further (from 2 to 4), the execution time starts to stabilize, but when the number of threads reaches 8 and 16, the performance degrades significantly. This suggests that while fine-grained locking reduces contention to some extent, there is still substantial overhead associated with acquiring and releasing locks, especially as the number of threads grows.
  3. Locking Overhead:
    • Even though fine-grained locking allows better parallelism compared to coarse-grained locking, the overhead of locking and unlocking each node increases as the number of threads grows, leading to performance degradation beyond 4 threads.

Hardware Specifications:

  • CPU: Intel Core i5-3570 (3.40 GHz)
  • RAM: 8GB DDR3

The system specifications suggest that the CPU and memory are capable of handling multithreaded operations, but the locking overhead remains a significant bottleneck at higher thread counts.

Conclusion:

  • Fine-grained synchronization improves concurrency by allowing multiple threads to operate on different parts of the list simultaneously. However, as the number of threads increases, the performance suffers due to the overhead of acquiring and releasing locks on each individual node.
  • While fine-grained locking provides better scalability compared to coarse-grained locking, it still doesn't scale well under high concurrency, especially when many threads are involved.
  • For applications with many threads, alternative techniques such as lock-free or non-blocking synchronization may offer better performance by reducing the locking overhead.

This analysis shows the trade-offs between fine-grained locking and alternative synchronization techniques in linked lists, especially in terms of performance at higher thread counts.

게시:
Labels: