Σχεδιασμός και Υλοποίηση Συστήματος STM με Γρήγορη Πρόσβαση Μεταδεδομένων

Abstract

The purpose of this diploma dissertation is the design and implementation of a Software Transactional Memory (STM) system in C called StandawayTM. As Moore’s Law is reaching its limits and multi-core systems have became predominant, Amdahl’s Law seems to be the most relevant in achieving high performance execution. In order to make parallel processing possible, there exist a set of tools like semaphores, locks, mutexes, barriers and atomic instruction. But all the above require of the programmer to be aware of all data dependencies and race conditions that might be present in her code making parallel programming a difficult task. Thus, Transactional Memory (TM) was proposed, which aimed to automate parallel programming by asking the programmer to specify the regions of code that are transactional, that is, to be executed atomically in regard to all other regions that are also marked as transactional. TM can be implemented in two ways, as Software in Software Transactional Memory (STM) or as Hardware in Hardware Transactional Memory (HTM). Their comparison is the object of a lot of research and are not the subject of this thesis, and we will only examine STMs. Every STM system monitors the memory accesses of threads in order to decide if a conflict occurred and the atomicity of a transactional region (atomic block) is in danger. That is, if during the execution of an atomic block, another thread has affected a memory location that the atomic block is accessing. Each STM system usually keeps a record of all read and write accesses by all threads in logs or Bloom Filters. Both Bloom Filters and search in logs for conflict detection is an expensive procedure. Also each transactional access of memory, both read and write, has a lot of overhead in regard to a non-transactional access. With StandawayTM we suggest a new way of keeping track of all accesses which allows for conflict detection in constant time as well as minimum overhead in each transactional access. In this diploma dissertation, we will initially formalize Transactional Memory and then analyze the design choices of StandawayTM as well as explain the reason behind them. Finally we will present and explain experimental results and make suggestions on further improvements in the design of StandawayTM.