Overview

ALFRED (Automatic aLlocation oF non-volatile memoRy for transiEntly-powered Devices) 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. ALFRED components are availabe as a separate branch in ScEpTIC repo at https://bitbucket.org/neslabpolimi/sceptic/src/ALFRED/

You can find a complete description of ALFRED here, as well as a detailed technical report here.

ALFRED Pipeline Prototype

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.