Data-flow analysis

Data-flow analysis is a technique for gathering information about the possible set of values calculated at various points in a computer program. A program's control-flow graph (CFG) is used to determine those parts of a program to which a particular value assigned to a variable might propagate. The information gathered is often used by compilers when optimizing a program. A canonical example of a data-flow analysis is reaching definitions. A simple way to perform data-flow analysis of programs is to set up data-flow equations for each node of the control-flow graph and solve them by repeatedly calculating the output from the input locally at each node until the whole system stabilizes, i.e., it reaches a fixpoint. This general approach, also known as Kildall's method, was developed by Gary Kildall while teaching at the Naval Postgraduate School. Bas

Stability of time-sensitive networks: strategies for partial regulation

Nicolò Dal Fabbro

In time-sensitive networks, regulators can be used to reshape traffic, and their usage may be necessary to guarantee stability by providing worst-case delay bounds. In this project, I study partial regulation of time-sensitive networks with cyclic dependencies, focusing on performance analysis. Using recently developed Network Calculus tools, such as TFA (Total Flow Analysis), TFA++, FP-TFA (Fixed Point Total Flow Analysis) I study how delay bounds can be improved by varying position and number of per-flow regulators (PFRs) in a FIFO-per-class network. The problem is non-trivial because in very complex networks the number of possible combinations of positions becomes huge. I find that the choice of position and number of regulators can bring to significant improvements in the computed delay bounds. The main part of the analysis is done on a synthetic use-case network. The results of the analysis are discussed and some heuristics for the general case are inferred. I apply the work done to a realistic network by proposing an algorithm that aims to jointly find good positions and number of regulators in a general topology through a parametric analysis. In the realistic case, I find significant correspondences with the synthetic use-case results and considerations.

2020

Software Support for Non-Volatile Memory (NVM) Programming

David Teksen Aksun

Non-Volatile Memory (NVM) is an emerging type of memory device that provides fast, byte-addressable, and high-capacity durable storage. NVM sits on the memory bus and allows durable data structures designs similar to the in-memory equivalent ones. Expensive serialization/deserialization operations, usually associated with block-based storage, are not necessary. Unfortunately, using NVM is not as simple as placing a data structure in NVM and expecting persistence. As NVM sits on the memory bus, processor caches buffer the cache lines from it that are referenced by load and store instructions. The volatility of the caches and possible power failures at a random point in a program complicate the design and require ways to handle these failures. Prior work focused on implementing crash-consistency mechanisms to correctly recover a program's data after a failure. The goal was to minimize the use of costly cache line write-back and fence instructions, which are necessary for correct durability. Moreover, commercial NVM devices are slower compared to DRAM and affect the design. In addition to performance overheads, correctly implementing crash consistency is hard. The programmers need to carefully reason about cache line write-back instructions and the order of persistent writes. Finding bugs can take from minutes to hours. In this thesis, we use checkpointing as an effective crash-consistency mechanism with low overhead for building durable data structures. We also describe an inter-procedural dataflow analysis for fast detection of NVM programming bugs. We show the practicality of these ideas through three primary contributions and their implementations. Firstly, we present InCLL to address NVM checkpointing. InCLL is a novel technique that uses fine-grained checkpointing and in-cache-line logging to minimize the number of explicit write-back and fence instructions in the fast path of data structure modifications. We evaluate InCLL both on DRAM and Optane devices for the Masstree data structure. Secondly, we present a new checkpointing design, CpNvm, which minimizes NVM write-back instructions on the critical path of the execution. We achieve low overheads for Masstree and Memcached for write-heavy workloads, and almost no overheads for read-only workloads. In addition, we present FlowNvm to find NVM programming bugs. FlowNvm can identify NVM programming pattern violations and anti-patterns at compile-time using inter-procedural dataflow analysis.

EPFL2021

Software Support for Non-Volatile Memory (NVM) Programming

David Teksen Aksun

EPFL2021

Stability of time-sensitive networks: strategies for partial regulation

Numerical Simulation and Flow Analysis of an Elbow Diffuser

Software Support for Non-Volatile Memory (NVM) Programming

Stability of time-sensitive networks: strategies for partial regulation

Numerical Simulation and Flow Analysis of an Elbow Diffuser

Software Support for Non-Volatile Memory (NVM) Programming