טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMayzels Tehila
SubjectSoftware Management of Hardware Memory Versioning
DepartmentDepartment of Computer Science
Supervisor Professor Yoav Etsion
Full Thesis textFull thesis text - English Version


Abstract

Task-based programming is an emerging paradigm that simplifies parallel programming.
The idea is to partition the code into logical operations called tasks, when one or more
independent tasks running concurrently, as threads, out of program order. Task-based
models, however, mostly focus on expressing concurrency and, for the most part, do not
reason about data synchronization. Memory dependences among tasks must be taken
into consideration in order to get correct results, but this may be difficult or impossible
to decide before run time.
The recently proposed O-structures memory versioning model is intended to fill this
gap and dynamically track data dependencies. The model extends the concept of register
renaming to the entire memory and thereby eliminates false- and anti-dependencies
between tasks. Using this model, each task views the same memory snapshot it would
have viewed if executed sequentially. However, it only provides low-level primitives,
which makes programming more complex and requires deep understanding of the system.
In this research, we extend the LLVM compiler to support O-structures and to
manage the hardware memory versioning with minimal programmer work. Our compiler
uses simple programmer annotations to identify which memory elements should be
tracked by the versioning hardware. It then replaces those memory elements with special
O-structures elements and replaces regular memory accesses with special versioned
memory accesses. In order to maximize parallelism, it also takes care to efficiently
acquire and release those O-structures, using the correct versions.
Our work focuses on handling a class of
unipath algorithms on dynamic irregular
data structures. In this class of algorithms, there is exactly one path from the structure’s
root to each of its elements. The potential of parallelization here is high, but since
the data structure is pointer based, it is difficult or impossible to specify and handle
dependencies. With versioning memory model, pipelining of tasks is achieved by handover-hand synchronization. Our compiler enables programs that use unipath data
structure algorithms to run successfully with versioned memory model, using only
a few annotations. Hence, reaches maximal parallelism with minimal programmer
intervention.