Overview ======== .. |ALFRED-REPO| raw:: html https://bitbucket.org/neslabpolimi/sceptic/src/ALFRED/ .. |ALFRED| raw:: html here .. |ALFRED-TECHREP| raw:: html here .. |ScEpTIC-REF| raw:: html ScEpTIC **ALFRED** (\ **A**\ utomatic a\ **L**\ location o\ **F** non-volatile memo\ **R**\ y for transi\ **E**\ ntly-powered **D**\ evices) is a virtual memory abstraction that resolves the dichotomy between volatile and non-volatile memory in intermittent computing. We implement a prototype of ALFRED pipeline as an extension of |ScEpTIC-REF|. ALFRED components are availabe as a separate branch in ScEpTIC repo at |ALFRED-REPO| You can find a complete description of ALFRED |ALFRED|, as well as a detailed technical report |ALFRED-TECHREP|. ALFRED Pipeline Prototype ######################### .. image:: pipeline.png :alt: ALFRED pipeline We implement a prototype of ALFRED pipeline starting from *stage 2*. The analysis and transformation passes that compose our prototype are available in ``ScEpTIC/AST/transformations/virtual_memory``. Note that our prototype expects as input the LLVM IR of the source program, already instrumented with checkpoints. We provide below a short description of how our prototype works. Phase 1 - AST re-parsing ######################## As first operation, our prototype re-organizes the structure of the Abstract Syntax Tree (AST) used by ScEpTIC into a new logical structure that ease the analysis and transformation of the input program. Conditional statements and loops correspond to dedicated objects and the AST of each function no longer have backward edges or bifurcations. Note that ScEpTIC creates one separate AST for each function. The **ASTParser** submodule available in ``ScEpTIC/AST/transformations/virtual_memory/parsers/ast_parser.py`` reorganizes the instructions of ASTs into basic blocks using the **BasicBlock** class, and groups the basic blocks that represent loops and conditional statements onto **LoopBlock** and **ConditionalBlock**, respectively. Phase 2 - Computation Intervals Identification ############################################## Our prototype of ALFRED now splits the input program into computation intervals. First, the **ComputationIntervalsManager** submodule available in ``ScEpTIC/AST/transformations/virtual_memory/computation_intervals_manager.py`` normalizes all the instances of **LoopBlocks** and **ConditionalBlocks**, removing the compile-time uncertainty in the span of computation intervals. For doing so, it uses the components available in the ``ScEpTIC/AST/transformations/virtual_memory/normalizations/checkpoints/`` directory. Next, the **ComputationIntervalsManager** submodule extracts the basic blocks contained in the instances of **LoopBlocks** and **ConditionalBlocks** that include a checkpoint operation, and then splits each ASTs into computation intervals. Phase 3 - Memory Tags Identification #################################### Our prototype of ALFRED now uses the **MemoryTagsParser** submodule available in ``ScEpTIC/AST/transformations/virtual_memory/parsers/memory_tags_parser.py`` to associate to each memory read and write operation the memory tag of the targeted memory location. Note that the memory tag is identified from the metadata that ScEpTIC associates to each instruction, which consists in debug symbols. At this phase, the program reaches *stage 3* of ALFRED pipeline. Phase 3 - Mapping Virtual Memory ################################ Our prototype of ALFRED now maps virtual memory onto volatile/non-volatile memory, thus making the memory read and write instructions of ASTs target volatile/non-volatile memory. The **ComputationIntervalsManager** transforms each AST using the ``apply_virtual_memory_transformations()`` method. As first operation, the method normalizes each computation interval to address the compile-time uncertainty of loops, conditional statements, and function calls, respectively, using the **MemoryUsage** submodule available in ``ScEpTIC/AST/transformations/virtual_memory/analysis/memory_usage.py``. Then, the method relies on the **VirtualMemoryTransformation** submodule available in ``ScEpTIC/AST/transformations/virtual_memory/virtual_memory_transformations.py`` to map memory read and write instructions as follows. First, it makes all the memory read and write instructions target volatile memory, by associating to them the ``VirtualMemoryEnum.VOLATILE`` attribute. Then, it maps memory write instructions to non-volatile memory, by associating to them the ``VirtualMemoryEnum.NON_VOLATILE`` attribute. Similarly, it then maps memory write instructions to non-volatile memory. Finally, it consolidate memory read instructions, making a subset of reads target volatile memory. Note that, the **VirtualMemoryTransformation** submodule addresses also the uncertainty introduced by our technique to deal with intermittence anomalies, using the ``address_war_hazards()`` method. At this phase, the program reaches *stage 4* of ALFRED pipeline. Phase 4 - Addressing Anomalies ############################## As ScEpTIC abstracts the emulated MCU memory, we need not reproduce the memory layout and versioning required by our technique to address anomalies. Hence, the program can be considered to be at *stage 5* of ALFRED pipeline. Note that all the program normalizations required by our technique are instead already applied during the previous phase. Phase 5 - Final ScEpTIC AST ########################### All the memory read and write instructions of the program now target either volatile or non-volatile memory. As such, the **ComputationIntervalsManager** submodule merges the transformed ASTs onto the same data structure that ScEpTIC uses to emulate the LLVM IR execution. The program now reaches *stage 6* of ALFRED pipeline, as this operation is logically equivalent to producing the final binary. Note that we extended ScEpTIC with a interruption manager that calculates the program energy consumpation and uses the ``VirtualMemoryEnum`` attribute to identify the targeted memory location.