PaperlayerView exact revision on arXiv

Source-linked AI summary

Alpaca: Intermittent Execution without Checkpoints

Kiwan Maeng, Alexei Colin, Brandon Lucia

arXiv:1909.06951v1cs.DC

TL;DR

Intermittent energy-harvesting devices challenge software systems to preserve progress and memory consistency across unexpected power failures. Alpaca addresses this with task-based execution and privatized shared data that commits only after successful task completion. Compared with prior systems, its prototypes consistently improve performance, achieving up to 23.8x improvement in some cases.

  • Problem

    Intermittent power failures erase volatile state and can leave persistent data inconsistent, requiring software to preserve progress and memory consistency.

  • Method

    Alpaca decomposes programs into tasks and privatizes task-shared data, committing updates only when a task completes successfully.

  • Results

    Alpaca-undo and Alpaca-redo outperform Chain, DINO, and Ratchet on harvested energy and continuous power, with improvements up to 23.8x in some cases.

  • Takeaways & Limitations

    Alpaca provides a low-overhead intermittent-computing model that avoids checkpointing and reduces costly time and memory overheads of prior approaches.

  • Takeaways & Limitations

    The prototype requires direct array-element references rather than pointer-based array indirection, an implementation-specific limitation.

Abstract

from arXiv · show

The emergence of energy harvesting devices creates the potential for batteryless sensing and computing devices. Such devices operate only intermittently, as energy is available, presenting a number of challenges for software developers. Programmers face a complex design space requiring reasoning about energy, memory consistency, and forward progress. This paper introduces Alpaca, a low-overhead programming model for intermittent computing on energy-harvesting devices. Alpaca programs are composed of a sequence of user-defined tasks. The Alpaca runtime preserves execution progress at the granularity of a task. The key insight in Alpaca is the privatization of data shared between tasks. Updates of shared values in a task are privatized and only committed to main memory on successful execution of the task, ensuring that data remain consistent despite power failures. Alpaca provides a familiar programming interface and a highly efficient runtime model. We also present an alternate version of Alpaca, Alpaca-undo, that uses undo-logging and rollback instead of privatization and commit. We implemented a prototype of both versions of Alpaca as an extension to C with an LLVM compiler pass. We evaluated Alpaca, and directly compared to three systems from prior work. Alpacaconsistently improves performance compared to the previous systems, by up to 23.8x, while also improving memory footprint in many cases, by up to 17.6x.

1 INTRODUCTION

Energy-harvesting systems operate intermittently, requiring software to preserve progress, consistency, and atomicity while efficiently using limited energy and memory. Alpaca addresses these requirements with task-based execution and atomic commitment of task updates, improving performance over prior systems.

  • Motivation: Energy-harvesting devices operate only when environmental energy is available, creating power failures that erase volatile state.The design space includes radio, solar, and other environmental energy sources.
  • Requirements: Programs must preserve progress, maintain consistent state across volatile and non-volatile memory, and respect atomicity constraints.One example is sampling related sensors together.
  • Alpaca: Alpaca uses a static task model to preserve progress, enforce programmer-provided atomicity constraints, and tune execution to energy availability.Its task updates commit atomically only when execution completes successfully.
  • Alpaca: Alpaca avoids checkpointing volatile state by discarding task updates after power failure, while leveraging both volatile and non-volatile memory.This design addresses hardware flexibility and reduces runtime overhead relative to prior approaches.
  • Evaluation: Alpaca improves performance over prior systems by 4–5.2x on average and up to 23.8x in some cases.The introduction also reports smaller memory footprint in many cases, though the supplied passage truncates that metric.

2 BACKGROUND AND MOTIVATION

Intermittent power failures disrupt progress and can leave memory inconsistent, especially when execution reads and later rewrites persistent state. Existing checkpointing and task-bounding approaches address parts of this problem but incur overheads or restrict atomicity and hardware choices.

  • Background: Intermittent operation compromises forward progress and can produce inconsistent device and memory states.These effects motivate abstractions tailored to intermittent execution.
  • Background: Energy-harvesting devices may draw energy from solar power, radio waves, or mechanical interaction and manipulate both volatile and non-volatile memory.Their operation alternates between active periods and inactive periods as energy availability changes.
  • Hardware Model: Alpaca makes few hardware assumptions and supports arbitrary mixtures of volatile and non-volatile memory, unlike systems requiring all memory to be non-volatile.Supported non-volatile memories include atomic-read/write technologies such as FRAM and Flash.
  • Memory Consistency: Volatile-only checkpointing can leave data inconsistent when a power failure interrupts a read-after-write dependence.In the RSA example, restarting with an already-updated carry produces the wrong result.
  • Prior Work: Intermittent systems preserve progress using checkpoints or bounded tasks, but compiler-automated checkpointing may checkpoint too frequently or copy unnecessary memory.The supplied passages also identify pointer-aliasing limitations and difficulty meeting high-level atomicity constraints.

3 ALPACA PROGRAMMING MODEL

Alpaca organizes intermittent programs as explicitly sequenced tasks that operate on consistent memory snapshots and produce consistent outputs. Privatization and task atomicity allow interrupted work to restart safely while preserving progress when tasks eventually receive sufficient energy.

  • Programming Model: Alpaca combines user-defined tasks with privatization to support progress, atomicity constraints, and consistent memory under intermittent execution.Tasks and privatization are the programming model’s two core concepts.
  • Task-Based Programming: A task executes on a consistent memory snapshot and produces consistent outputs, with interrupted execution restarting from the task’s beginning.A task that eventually completes has behavior equivalent to some continuously powered execution.
  • Task-Based Programming: Programmers decompose applications into tasks and use transition_to statements to define control flow between tasks.Each transition immediately jumps to the beginning of the named successor task.
  • Example: Alpaca’s application model can sample a sensor, calculate an average, and transmit the result via radio.These stages illustrate an application written using the task-based model.
  • Task Atomicity: Task atomicity ensures that either all effects of a task become visible or none do, and that a completed task takes effect only once.Progress is preserved assuming the system eventually buffers enough energy to complete each task.
  • Privatization: During compilation, Alpaca privatizes task-shared variables into task-local buffers and commits changes after task completion.This prevents inconsistent direct updates to shared memory during interrupted execution.

4 ALPACA IMPLEMENTATION

Alpaca implements task-granular intermittent execution through compiler analysis, data privatization, and two-phase commit. Its runtime preserves consistency by selectively buffering W-A-R data and atomically applying completed-task updates.

  • Implementation overview: Alpaca preserves progress at task granularity while keeping task-shared and task-local data consistent through a compiler pass and runtime library.The implementation targets efficient execution in addition to progress and consistency.
  • Privatization: Privatization copies selected task-shared variables into buffers, redirects task accesses, and commits updates only after task completion.This makes task execution idempotent and its effects atomic despite power failures.
  • Compiler analysis: The compiler detects W-A-R dependencies and privatizes only involved variables, avoiding instrumentation for other data.This selective instrumentation is intended to reduce runtime overhead.
  • Two-phase commit: Two-phase commit records privatized updates in a non-volatile commit_list before copying each buffered value back to its original location.A persistent commit_ready state lets the runtime resume commit after a power failure.
  • Array privatization: Array privatization tracks first writes with version-backed bitmasks whose entries are 16-bit versions and clear implicitly when cur_version changes.The scheme privatizes at array-element granularity and handles counter rollover by explicitly resetting entries.

5 ALPACA WITH UNDO-LOGGING

Alpaca-undo is an alternative implementation that replaces privatization and commit with undo-logging and rollback. It retains Alpaca’s programming interface and is reported to be faster than the redo-logging design on average.

  • Design alternative: Alpaca-undo uses undo-logging and rollback instead of Alpaca-redo’s privatization and commit.Both variants share the same programming interface but differ in memory management.
  • Evaluation: 1.53x faster on average, Alpaca-undo outperforms its redo-logging counterpart.The comparison is reported for the two Alpaca design variants.
  • Redo-logging: Alpaca-redo privatizes W-A-R variables and commits their updates when a task completes, providing zero-cost recovery after power failures.Redo-logging requires two copy operations per variable per completed task.
  • Undo-logging: Alpaca-undo uses a static undo log, backs up non-array W-A-R variables at task start, and backs up array values before their first writes.It uses the version-backed bitmask scheme for detecting first writes to array elements.

6 ALPACA DISCUSSION

Alpaca provides task-level atomicity and memory consistency through selective privatization, while avoiding checkpointing overhead. Its Alpaca-undo variant instead uses backup copies, in-place updates, and rollback support.

  • Low Overhead: Alpaca avoids checkpointing costs by retaining only the identity of the last executing task rather than repeatedly saving registers or the stack.Compared with Ratchet and DINO, selective privatization reduces copying, time, and energy overhead.
  • Alpaca-undo: Alpaca-undo clears its backup metadata after successful task completion, while a failed execution can restore backed-up values to preserve consistency.The runtime tracks backed-up variables using backup_list and a rollback flag.
  • Memory Consistency: Alpaca guarantees task atomicity by privatizing shared variables involved in W-A-R dependencies and committing updates only after successful completion.Task-local volatile state is reinitialized after power failures, while privatized non-volatile state prevents inconsistent repeated execution.

6.3 I/O

Alpaca supports sensor and actuator code through task structure, but conditional non-volatile updates based on changing inputs can violate task idempotence. Applications must use intermittence-safe I/O patterns and tolerate repeated outputs.

  • Atomic I/O: Alpaca can keep related sensor readings consistent by placing their acquisition in the same task.The example reads temperature and pressure together before updating heater or cooler state.
  • I/O Limitations: Conditional non-volatile updates driven by sensed inputs can violate task idempotence after a power failure.Different sensor results across execution attempts can leave heaterOn and coolerOn simultaneously true.
  • I/O Patterns: Programmers can preserve idempotence by separating input capture from conditional updates or making both control-flow paths access the same memory locations.Alpaca targets applications that can tolerate repeated outputs because actuation cannot be undone.

6.4 Forward Progress

Forward progress is outside Alpaca’s solved problems because a task requiring more energy than the device buffers can never complete. Alpaca therefore relies on programmer-controlled task sizing and omits dynamic checkpoint fallback.

  • Forward Progress: A task whose energy cost exceeds the device’s buffered energy cannot complete, preventing forward progress.Input-dependent task energy makes this problem more complex.
  • Prior Approaches: Dynamic checkpointing can impose state-capture costs and may violate I/O atomicity.Prior systems use dynamic checkpoints after repeated failures or when energy is low.
  • Design Boundary: Alpaca does not include a dynamic checkpointing fallback and instead requires programmers to size tasks below the target device’s energy capacity.The authors report no forward-progress problems in their test programs.

6.5 Reusability of Tasks

Alpaca reuses functionality as sequences of tasks because energy limits can prevent encapsulating an operation in one function. The prototype supports substantial C features but imposes pointer and array-access restrictions.

  • Task Reuse: Alpaca reuses task sequences by manually passing arguments, return addresses, and return values through task-shared variables.A single function is insufficient when its energy demand exceeds the device’s buffer.
  • Prototype Scope: The prototype supports a useful C subset, including most uses of pointers and complex data structures, but retains implementation-specific limitations.The paper distinguishes these prototype restrictions from fundamental Alpaca limitations.
  • Pointer Analysis: The prototype’s limited pointer alias analysis requires TS pointers to receive TS-variable addresses only when those addresses are constant.This restriction still permits function pointers when pointers refer to constant variables.
  • Array Access: Array elements must be referenced directly, such as A[30], because indirect pointer access would require additional dynamic analysis.The restriction avoids dynamically disambiguating which array bitmask to update.

7 BENCHMARKS AND METHODOLOGY

The evaluation compares Alpaca variants directly with DINO, Chain, and Ratchet across six applications on harvested-energy hardware. The methodology also accounts for implementation assumptions and fair task-boundary comparisons.

  • Evaluation platform and systems: Alpaca was evaluated on real WISP5 energy-harvesting hardware using applications ported for direct comparison with DINO, Chain, Alpaca-redo, Alpaca-undo, and Ratchet.The WISP5 uses a TI MSP430FR5969 processor powered by harvested RF energy.
  • Applications: The benchmark suite contained six applications, including activity recognition, cuckoo filter, RSA encryption, and cold-chain equipment monitoring.Four applications came from prior Chain work, and two were ported from MIBench.
  • Comparison assumptions: DINO was evaluated with hand-annotated perfect pointer aliasing, while Alpaca required no such assumption.The evaluation reports that Alpaca outperformed this oracle DINO configuration.
  • Comparison assumptions: Ratchet was ported from ARM to TI MSP430 without some ARM-specific optimizations, which the original evaluation associated with around 1.6x slowdown.This porting choice affects the comparison baseline.
  • Experimental controls: Applications used identical task definitions for Chain, Alpaca-redo, and Alpaca-undo, with DINO boundaries inserted at equivalent code points.Ratchet boundaries were inserted automatically by its system rather than manually.

8 EVALUATION

Alpaca-redo and Alpaca-undo outperform prior systems in runtime while using moderate non-volatile memory, with Alpaca-undo generally more efficient. The evaluation also examines overhead sources, volatile privatization, programming effort, and task sizing.

  • Runtime performance: Alpaca-redo and Alpaca-undo outperform Chain, DINO, and Ratchet on continuous power and harvested energy, with Alpaca-undo leading both Alpaca variants.On harvested energy, Alpaca-undo outperforms Chain, DINO, and Ratchet by 5.19x, 4.63x, and 4.00x on average, respectively.
  • Runtime performance: 1.55x and 2.31x are Alpaca-undo’s and Alpaca-redo’s average slowdowns versus plain C on continuous power.Alpaca-undo also outperforms Alpaca-redo by 1.49x on average in this condition.
  • Runtime overhead: Alpaca’s lower overheads arise from lighter logging and task transitions than the channel manipulation, checkpointing, and restoration costs of prior systems.Alpaca-redo’s transitions commit privatized values, whereas Alpaca-undo’s transitions clear a backup-list index and flags.
  • Non-volatile memory: Alpaca-undo and Alpaca-redo use slightly more non-volatile memory than Ratchet but much less than Chain and DINO.Alpaca selectively privatizes non-volatile state rather than checkpointing all volatile state.
  • Volatile privatization: Around 110 RMWs per task mark the point where Alpaca-VM begins to outperform Alpaca-redo, but real applications average only 2.1 reads and 1.05 writes to privatized variables.The measured application access counts therefore remain far below the reported tipping point.
  • Programmer effort: Alpaca requires less code change than Chain, while allowing task-shared variables to be accessed with ordinary C loads and stores.Its programming complexity lies between Chain and DINO based on lines of code and keyword counts.
  • Task sizing: Task sizing requires balancing completion energy against privatization, commit, and transition overhead, assuming the system eventually buffers enough energy for each task.Tasks that are too long may prevent progress with a fixed-size energy buffer, while tasks that are too short can impede performance.
  • Task sizing: Except near continuous RF powering, work completed before brownout is invariant to input power and depends on the device’s energy buffer size.This means programmers primarily reason about a task’s total energy cost rather than instantaneous input power.

9 RELATED WORK

Alpaca differs from prior intermittent-computing approaches by combining task-based execution with selective data privatization rather than relying on broad checkpointing or channel-based versioning. It also relates to idempotence, non-volatile memory, transactions, and hardware support.

  • Intermittent computing: Alpaca avoids volatile-state checkpointing by using programmer-defined task boundaries and selective protection of shared non-volatile data.Prior systems use automatic checkpoints or version non-volatile memory manually or automatically.
  • Hardware and execution models: Unlike hardware-specific non-volatile processors and Clank, Alpaca targets existing hardware with a programming and execution model.Dewdrop supports only small one-shot tasks and does not support computations spanning failures.
  • Idempotence: Alpaca leverages idempotently re-executable tasks by eliminating write-after-read dependences, while Ratchet relies on compiler idempotence analysis for checkpoint placement.Alpaca does not assume entirely non-volatile memory and leaves task sizes free from that analysis.
  • Transactional memory: Alpaca differs from transactional memory because it targets consistency across re-executions after power failures rather than multithreaded programs.Both use speculative updates that become visible when an atomic region completes, but their target execution settings differ.

10 CONCLUSION AND FUTURE WORK

The paper concludes that Alpaca provides low-overhead intermittent computing without checkpointing through task-based execution and idempotence-based logging. It identifies automated task decomposition as an important direction for future work.

  • Conclusion: Alpaca’s prototype significantly improves performance over several prior systems while providing a low-overhead intermittent programming model without checkpointing.The model combines task-based execution with a logging scheme built on idempotence analysis.
  • Future work: Automating or assisting program decomposition into tasks remains future work because task decomposition is currently reasonable but mostly manual.This need was also raised by Chain and DINO.
Loading 1909.06951v1…