Technical Report MSC-2017-08

Title: Software Management of Hardware Memory Versioning
Authors: Tehila Mayzels
Supervisors: Yoav Etsion
PDFCurrently accessibly only within the Technion network
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 dependencies 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.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2017
To the main CS technical reports page

Computer science department, Technion