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 userdefined 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. Shared values written in a task are detected using idempotence analysis and copied into a buffer private to the task. At the end of the task, modified values from the private buffer are atomically committed to main memory, ensuring that data remain consistent despite power failures. Alpaca provides a familiar programming interface, a highly efficient runtime model, and places few restrictions on a target device's hardware. We implemented a prototype of Alpaca as an extension to C with an LLVM compiler pass. We evaluated Alpaca, and directly compared to two systems from prior work. Alpaca eliminates checkpoints, which improves performance up to 15x, and Alpaca avoids static multi-versioning, which improves memory consumption by up to 5.5x. and quickly consumes the stored energy. Energy depletes more quickly during operation (e.g. milliseconds) than it accumulates during charging (e.g., seconds). When energy is depleted and the device powers off, volatile state, e.g. registers and stack memory, is lost, while non-volatile state, e.g., ferroelectric memory (FRAM), persists. The charge/discharge cycle of an energy-harvesting device forces software to execute according to the intermittent execution model Lucia and Ransford 2015; Van Der Woude and Hicks 2016 ]. An intermittent execution includes periods of activity perforated by power failures. The key distinction between intermittent execution and continuously-powered execution is that in the intermittent model a computation may execute only partially before power fails and must be resumed after the power is restored. Correct and efficient intermittent execution requires a system to meet a set of correctness requirements (C1-3) and performance goals (G1-3). C1: A program must preserve progress despite losing volatile state on power failures. C2: A program must have a consistent view of its state across volatile and non-volatile memory. C3: A program must respect high-level atomicity constraints (e.g., sampling related sensors together). G1: Applications should place as few restrictions on the processor and memory hardware architecture as possible. G2: Applications should be tunable at design time to use the energy storage capacity efficiently. G3: Applications should minimize runtime overhead, memory footprint, restore overhead, and re-executed code. Recent work made progress toward several of these goals. Volatile checkpointing approaches [Balsamo et al. 2016 [Balsamo et al. , 2015 Mirhoseini et al. 2013; Ransford et al. 2011a,b] ensure progress (C1). Static multi-versioning [Colin and Lucia 2016] and dynamic versioning [Lucia and Ransford 2015; Van Der Woude and Hicks 2016] systems selectively create copies of modified data to keep volatile and non-volatile state consistent (C2). Task-based systems [Colin and Lucia 2016; Lucia and Ransford 2015] allow programmers to express application-level atomicity constraints (C3) and match the energy cost of a task to the device energy capacity (G2). However, prior approaches necessarily compromise on some of the goals. Volatile-only checkpointing does not ensure that volatile and non-volatile data remain consistent (C2). Static and dynamic versioning systems have high overheads in time [Lucia and Ransford 2015] or space [Colin and Lucia 2016] (G3). Idempotent compilation [Van Der Woude and Hicks 2016] reduces overhead (G3), but applies only to devices where all memory is non-volatile, not to off-the-shelf microcontrollers with hybrid volatile and non-volatile memory on the market today (G1). The fully-automatic nature of idempotent compilation deprives the programmer of control over the energy cost of the resulting tasks (G2) and complicates forcing tasks to respect high-level atomicity constraints (C3). This paper develops Alpaca 1 , a programming and execution model that allows software to execute intermittently. Like state-of-the-art systems, Alpaca preserves progress despite power failures (C1) and ensures memory consistency (C2). Alpaca uses a static task model without checkpoints and explicit restoration of volatile state. Alpaca's approach to maintaining memory consistency despite power failures is conceptually similar to transactional memory (TM) [Shavit and Touitou 1995] with redo-logging. An Alpaca task manipulates privatized copies of data and commits updates to those data atomically when the task completes. By discarding privatized copies, Alpaca can restart a task with negligible cost, similarly to Chain [Colin and Lucia 2016], but without the memory overhead of static multi-versioning (G3). Alpaca dynamically versions non-volatile data, like DINO [Lucia and Ransford 2015], but without checkpointing volatile state (G3). Alpaca selectively versions non-volatile memory locations identified by a compiler-based idempotence analysis, like 1 Alpaca: Adaptive Lightweight Programming Abstraction for Consistency and Atomicity Alpaca: Intermittent Execution without Checkpoints Ratchet [Van Der Woude and Hicks 2016], but without volatile state checkpoints (G3) and without being limited to hardware with only non-volatile memory (G1). Alpaca's design differences, relative to state-of-the-art systems, translate into performance gains of 4.2x on average (up 15x in some cases) and a non-volatile memory footprint smaller by 1.3-5.5x. In contrast to a fully automated compiler-only approach [Van Der Woude and Hicks 2016] and just-in-time dynamic checkpointing approach [Balsamo et al. 2016 [Balsamo et al. , 2015 Mirhoseini et al. 2013; Ransford et al. 2011a,b], Alpaca's task model allows the programmer to control where tasks begin and end. With this control, Alpaca applications can satisfy application-level atomicity requirements (C3) and use tasks sized to device energy capacity (G2). Section 2 provides background on intermittent computing. Sections 3 and 4 describe the Alpaca programming model and its implementation. Section 5 discusses key design decisions. Sections 6 and 7 describe our benchmarks and evaluation. We conclude with a discussion of related (Section 8) and future (Section 9) work.
Alpaca REF preserves execution progress at the granularity of a task by privatizing the shared data between tasks that are detected using idempotence analysis.
Alpaca: intermittent execution without checkpoints
PACMPL
Computer Science Engineering