research-article

Public Access

Chain: tasks and channels for reliable intermittent programs

Authors:

Brandon LuciaAuthors Info & Claims

OOPSLA 2016: Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications

Pages 514 - 530

https://doi.org/10.1145/2983990.2983995

Published: 19 October 2016 Publication History

Abstract

Energy harvesting computers enable general-purpose computing using energy collected from their environment. Energy-autonomy of such devices has great potential, but their intermittent power supply poses a challenge. Intermittent program execution compromises progress and leaves state inconsistent. This work describes Chain: a new model for programming intermittent devices.

A Chain program is a set of programmer-defined tasks that compute and exchange data through channels. Chain guarantees forward progress at task granularity. A task is restartable and never sees inconsistent state, because its input and output channels are separated. Our system supports language features for expressing advanced data exchange patterns and for encapsulating reusable functionality.

Chain fundamentally differs from state-of-the-art checkpointing approaches and does not incur the associated overhead. We implement Chain as C language extensions and a runtime library. We used Chain to implement four applications: machine learning, encryption, compression, and sensing. In experiments, Chain ensured consistency where prior approaches failed and improved throughput by 2-7x over the leading state-of-the-art system.

References

[1]

G. A. Agha. Actors: a model of concurrent computation in distributed systems. MIT Press, Cambridge, Mass, 1986.

[2]

D. Balsamo, A. Weddell, G. Merrett, B. Al-Hashimi, D. Brunelli, and L. Benini. Hibernus: Sustaining computation during intermittent supply for energy-harvesting systems. Embedded Systems Letters, IEEE, PP(99):1–1, 2014. ISSN 1943-0663.

[3]

T. W. Barr and S. Rixner. Medusa: Managing concurrency and communication in embedded systems. In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference, USENIX ATC’14, pages 439–450, Berkeley, CA, USA, 2014. USENIX Association.

Digital Library

[4]

R. L. Bocchino, E. Gamble, K. P. Gostelow, and R. R. Some. Spot: A programming language for verified flight software. In Proceedings of the 2014 ACM SIGAda Annual Conference on High Integrity Language Technology, HILT ’14, pages 97–102, New York, NY, USA, 2014. ACM.

Digital Library

[5]

M. Buettner, B. Greenstein, and D. Wetherall. Dewdrop: An energy-aware task scheduler for computational RFID. In USENIX Symposium on Networked Systems Design and Implementation (NSDI), Mar. 2011.

Digital Library

[6]

B. D. Carlstrom, A. McDonald, H. Chafi, J. Chung, C. C. Minh, C. Kozyrakis, and K. Olukotun. The Atomos Transactional Programming Language. In Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’06, pages 1–13, New York, NY, USA, 2006. ACM.

Digital Library

[7]

J. Coburn, A. M. Caulfield, A. Akel, L. M. Grupp, R. K. Gupta, R. Jhala, and S. Swanson. NV-Heaps: making persistent objects fast and safe with next-generation, non-volatile memories. In ASPLOS, Mar. 2011.

Digital Library

[8]

1950380.

[9]

A. Colin, A. P. Sample, and B. Lucia. Energy-interferencefree system and toolchain support for energy-harvesting devices. In Proceedings of the 2015 International Conference on Compilers, Architecture and Synthesis for Embedded Systems, CASES ’15, pages 35–36, Piscataway, NJ, USA, 2015. IEEE Press. ISBN 978-1-4673-8320-2.

Digital Library

[10]

A. Colin, G. Harvey, B. Lucia, and A. Sample. An energyinterference-free hardware/software debugger for intermittent energy-harvesting systems. In ASPLOS, 2016.

Digital Library

[11]

J. Condit, E. B. Nightingale, C. Frost, E. Ipek, B. Lee, D. Burger, and D. Coetzee. Better I/O through byteaddressable, persistent memory. In Symposium on Operating Systems Principles (SOSP), Oct. 2009. 10.1145/1629575.1629589.

Digital Library

[12]

M. de Kruijf and K. Sankaralingam. Idempotent code generation: Implementation, analysis, and evaluation. In Proceedings of the International Symposium on Code Generation and Optimization ”’(CGO)”’, 2013.

Digital Library

[13]

M. de Kruijf, K. Sankaralingam, and S. Jha. Static analysis and compiler design for idempotent processing. In Proceedings of 33rd International Conference on Programming Language Design and Implementation (PLDI), 2012.

Digital Library

[14]

S. R. Dulloor, S. Kumar, A. Keshavamurthy, P. Lantz, D. Reddy, R. Sankaran, and J. Jackson. System software for persistent memory. In EuroSys ’14, Apr. 2014. 10.1145/2592798.2592814.

Digital Library

[15]

J. Gray and A. Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1992.

Digital Library

[16]

L. Hammond, V. Wong, M. Chen, B. D. Carlstrom, J. D. Davis, B. Hertzberg, M. K. Prabhu, H. Wijaya, C. Kozyrakis, and K. Olukotun. Transactional memory coherence and consistency. In ISCA, June 2004.

Digital Library

[17]

T. Harris and K. Fraser. Language Support for Lightweight Transactions. In Proceedings of the 18th Annual ACM SIGPLAN Conference on Object-oriented Programing, Systems, Languages, and Applications, OOPSLA ’03, pages 388–402, New York, NY, USA, 2003. ACM.

Digital Library

[18]

M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In Proceedings of the 20th Annual International Symposium on Computer Architecture, ISCA ’93, pages 289–300, New York, NY, USA, 1993. ACM.

Digital Library

[19]

H. Jayakumar, A. Raha, and V. Raghunathan. QuickRecall: A low overhead HW/SW approach for enabling computations across power cycles in transiently powered computers. In Int’l Conf. on VLSI Design and Int’l Conf. on Embedded Systems, Jan. 2014.

Digital Library

[20]

A. Kulkarni, Y. D. Liu, and S. F. Smith. Task types for pervasive atomicity. In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA ’10, pages 671–690, New York, NY, USA, 2010. ACM.

Digital Library

[21]

Y. Kwon, K. Mechitov, and G. Agha. Concurrent Objects and Beyond: Papers dedicated to Akinori Yonezawa on the Occasion of His 65th Birthday, chapter Design and Implementation of a Mobile Actor Platform for Wireless Sensor Networks, pages 276–316. Springer Berlin Heidelberg, Berlin, Heidelberg, 2014.

[22]

Y. Lee, G. Kim, S. Bang, Y. Kim, I. Lee, P. Dutta, D. Sylvester, and D. Blaauw. A modular 1mm3 die-stacked sensing platform with optical communication and multi-modal energy harvesting. In Solid-State Circuits Conference Digest of Technical Papers (ISSCC), 2012 IEEE International, pages 402–404, Feb 2012.

[23]

V. Liu, A. Parks, V. Talla, S. Gollakota, D. Wetherall, and J. R. Smith. Ambient backscatter: Wireless communication out of thin air. In Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM, SIGCOMM ’13, pages 39–50, New York, NY, USA, 2013. ACM. ISBN 978-1-4503-2056-6.

Digital Library

[24]

B. Lucia and B. Ransford. A simpler, safer programming and execution model for intermittent systems. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2015, pages 575–585, New York, NY, USA, 2015. ACM. ISBN 978-1- 4503-3468-6.

Digital Library

[25]

N. A. Lynch and M. Fischer. On describing the behavior and implementation of distributed systems, 1981.

[26]

A. Mirhoseini, E. M. Songhori, and F. Koushanfar. Idetic: A high-level synthesis approach for enabling long computations on transiently-powered ASICs. In IEEE Pervasive Computing and Communication Conference (PerCom), Mar. 2013.

[27]

D. Narayanan and O. Hodson. Whole-system persistence with non-volatile memories. In ASPLOS, Mar. 2012.

Digital Library

[28]

S. Pelley, P. M. Chen, and T. F. Wenisch. Memory persistency. In ISCA, June 2014.

Digital Library

[29]

Powercast Co. Development Kits - Wireless Power Solutions. http://www.powercastco.com/products/ development-kits/. Visited July 30, 2014.

[30]

A. Prokopec and M. Odersky. Isolates, channels, and event streams for composable distributed programming. In 2015 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!), Onward! 2015, pages 171–182, New York, NY, USA, 2015. ACM.

Digital Library

[31]

Proteus Digital Health. Proteus Digital Health. http://www. proteus.com/, 2015.

[32]

B. Ransford and B. Lucia. Nonvolatile memory is a broken time machine. In Proceedings of the Workshop on Memory Systems Performance and Correctness, MSPC ’14, pages 5:1–5:3, New York, NY, USA, 2014. ACM. ISBN 978-1- 4503-2917-0.

Digital Library

[33]

B. Ransford, J. Sorber, and K. Fu. Mementos: System support for long-running computation on RFID-scale devices. In ASPLOS, Mar. 2011.

Digital Library

[34]

R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21(2):120–126, Feb. 1978. ISSN 0001-0782.

Digital Library

[35]

[36]

A. P. Sample, D. J. Yeager, P. S. Powledge, A. V. Mamishev, and J. R. Smith. Design of an RFID-based battery-free programmable sensing platform. IEEE Transactions on Instrumentation and Measurement, 57(11):2608–2615, Nov. 2008.

[37]

D. Shasha, F. Llirbat, E. Simon, and P. Valduriez. Transaction chopping: Algorithms and performance studies. ACM Trans. Database Syst., 20(3):325–363, Sept. 1995.

Digital Library

[38]

N. Shavit and D. Touitou. Software Transactional Memory. In Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’95, pages 204–213, New York, NY, USA, 1995. ACM.

Digital Library

[39]

S. Venkataraman, N. Tolia, P. Ranganathan, and R. H. Campbell. Consistent and durable data structures for non-volatile byte-addressable memory. In FAST, Feb. 2011.

Digital Library

[40]

N. Villar and S. Hodges. The Peppermill: A human-powered user interface device. In Conference on Tangible, Embedded, and Embodied Interaction (TEI), Jan. 2010. org/10.1145/1709886.1709893.

Digital Library

[41]

T. A. Welch. A technique for high-performance data compression. Computer, 17(6):8–19, June 1984. ISSN 0018-9162.

Digital Library

[42]

Zac Manchester. KickSat. http://zacinaction.github. io/kicksat/, 2015.

[43]

W. Zhang, M. de Kruijf, A. Li, S. Lu, and K. Sankaralingam. Conair: Featherweight concurrency bug recovery via singlethreaded idempotent execution. In Proceedings of the 18th International Conference on Architectural Support for Programming Languages and Operating Systems ”’(ASPLOS)”’, 2013.

Digital Library

[44]

Y. Zhang, R. Power, S. Zhou, Y. Sovran, M. K. Aguilera, and J. Li. Transaction chains: Achieving serializability with low latency in geo-distributed storage systems. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP ’13, pages 276–291, New York, NY, USA, 2013. ACM.

Digital Library

Cited By

Song WKaxiras SVoigt TYao YMottola LShu YLiu JTan RHe YChen J(2024)TaDA: Task Decoupling Architecture for the Battery-less Internet of ThingsProceedings of the 22nd ACM Conference on Embedded Networked Sensor Systems10.1145/3666025.3699347(409-421)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3666025.3699347
Custode LFarina PYildiz EKilic RYildirim KIacca GShu YLiu JTan RHe YChen J(2024)Fast-Inf: Ultra-Fast Embedded Intelligence on the Batteryless EdgeProceedings of the 22nd ACM Conference on Embedded Networked Sensor Systems10.1145/3666025.3699335(239-252)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3666025.3699335
Shukla SPudukotai Dinakarrao SDev KYoo JMeinerzhagen P(2024)Energy Harvesting-Supported Efficient Low-Power ML Processing with Adaptive Checkpointing and Intermittent ComputingProceedings of the 29th ACM/IEEE International Symposium on Low Power Electronics and Design10.1145/3665314.3670837(1-6)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1145/3665314.3670837
Show More Cited By

Index Terms

Chain: tasks and channels for reliable intermittent programs

Recommendations

Alpaca: intermittent execution without checkpoints

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 ...
Chain: tasks and channels for reliable intermittent programs
OOPSLA '16

Energy harvesting computers enable general-purpose computing using energy collected from their environment. Energy-autonomy of such devices has great potential, but their intermittent power supply poses a challenge. Intermittent program execution ...
Supporting peripherals in intermittent systems with just-in-time checkpoints
PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation

Batteryless energy-harvesting devices have the potential to be the foundation of applications for which batteries are infeasible. Just-In-Time checkpointing supports intermittent execution on energy-harvesting devices by checkpointing processor state ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA 2016: Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications

October 2016

915 pages

ISBN:9781450344449

DOI:10.1145/2983990

General Chair:
Eelco Visser
Delft University of Technology, Netherlands
,
Program Chair:
Yannis Smaragdakis
University of Athens, Greece

ACM SIGPLAN Notices Volume 51, Issue 10
OOPSLA '16
October 2016
915 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/3022671
Editor:
Matthew Fluet
Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

In-Cooperation

SIGAda: ACM Special Interest Group on Ada Programming Language

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 October 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

SPLASH '16

Sponsor:

SIGPLAN

SPLASH '16: Conference on Systems, Programming, Languages, and Applications: Software for Humanity

November 2 - 4, 2016

Amsterdam, Netherlands

Acceptance Rates

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

170
Total Citations
View Citations
1,650
Total Downloads

Downloads (Last 12 months)248
Downloads (Last 6 weeks)41

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Song WKaxiras SVoigt TYao YMottola LShu YLiu JTan RHe YChen J(2024)TaDA: Task Decoupling Architecture for the Battery-less Internet of ThingsProceedings of the 22nd ACM Conference on Embedded Networked Sensor Systems10.1145/3666025.3699347(409-421)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3666025.3699347
Custode LFarina PYildiz EKilic RYildirim KIacca GShu YLiu JTan RHe YChen J(2024)Fast-Inf: Ultra-Fast Embedded Intelligence on the Batteryless EdgeProceedings of the 22nd ACM Conference on Embedded Networked Sensor Systems10.1145/3666025.3699335(239-252)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3666025.3699335
Shukla SPudukotai Dinakarrao SDev KYoo JMeinerzhagen P(2024)Energy Harvesting-Supported Efficient Low-Power ML Processing with Adaptive Checkpointing and Intermittent ComputingProceedings of the 29th ACM/IEEE International Symposium on Low Power Electronics and Design10.1145/3665314.3670837(1-6)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1145/3665314.3670837
Banerjee JIslam SWei WPan CXie M(2024)Autotile: Autonomous Task-tiling for Deep Inference on Battery-less Embedded SystemProceedings of the Great Lakes Symposium on VLSI 202410.1145/3649476.3658798(323-327)Online publication date: 12-Jun-2024
https://dl.acm.org/doi/10.1145/3649476.3658798
Xu SZhang WZhao MZhou ZJu LDe V(2024)Cache-aware Task Decomposition for Efficient Intermittent Computing SystemsProceedings of the 61st ACM/IEEE Design Automation Conference10.1145/3649329.3657382(1-6)Online publication date: 23-Jun-2024
https://dl.acm.org/doi/10.1145/3649329.3657382
Yildiz EAkhunov KRiva LGoknil AKurtev IYildirim K(2024)Adaptable Runtime Monitoring for Intermittent SystemsProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3650070(1175-1191)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3650070
Ahmed SIslam BYildirim KZimmerling MPawełczak PAlizai MLucia BMottola LSorber JHester J(2024)The Internet of Batteryless ThingsCommunications of the ACM10.1145/362471867:3(64-73)Online publication date: 22-Feb-2024
https://dl.acm.org/doi/10.1145/3624718
Xia CMin TZhang DWang C(2024)Understanding the Needs of Novice Developers in Creating Self-Powered IoTProceedings of the 2024 CHI Conference on Human Factors in Computing Systems10.1145/3613904.3642576(1-17)Online publication date: 11-May-2024
https://dl.acm.org/doi/10.1145/3613904.3642576
Akhunov KYldrm K(2024)CRAM-Based Acceleration for Intermittent Computing of Parallelizable TasksIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2023.329342612:1(48-59)Online publication date: Jan-2024
https://doi.org/10.1109/TETC.2023.3293426
Xuan LLin CYen TChen YHsu C(2024)FASE: Energy Isolation Framework for Latency-Sensitive Applications in Intermittent Systems With Multiple PeripheralsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.331819943:2(456-467)Online publication date: Feb-2024
https://doi.org/10.1109/TCAD.2023.3318199
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents