Document Open Access Logo

Constraint Based Compiler Optimization for Energy Harvesting Applications

Authors Yannan Li, Chao Wang

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2023.16.pdf
  • Filesize: 1.07 MB
  • 29 pages

Document Identifiers

Author Details

Yannan Li
  • University of Southern California, Los Angeles, CA, USA
Chao Wang
  • University of Southern California, Los Angeles, CA, USA

Funding

This work was partially funded by the U.S. NSF grants CNS-1702824 and CCF-2220345.

Cite As Get BibTex

Yannan Li and Chao Wang. Constraint Based Compiler Optimization for Energy Harvesting Applications. In 37th European Conference on Object-Oriented Programming (ECOOP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 263, pp. 16:1-16:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ECOOP.2023.16

Abstract

We propose a method for optimizing the energy efficiency of software code running on small computing devices in the Internet of Things (IoT) that are powered exclusively by electricity harvested from ambient energy in the environment. Due to the weak and unstable nature of the energy source, it is challenging for developers to manually optimize the software code to deal with mismatch between the intermittent power supply and the computation demand. Our method overcomes the challenge by using a combination of three techniques. First, we use static program analysis to automatically identify opportunities for precomputation, i.e., computation that may be performed ahead of time as opposed to just in time. Second, we optimize the precomputation policy, i.e., a way to split and reorder steps of a computation task in the original software to match the intermittent power supply while satisfying a variety of system requirements; this is accomplished by formulating energy optimization as a constraint satisfiability problem and then solving the problem using an off-the-shelf SMT solver. Third, we use a state-of-the-art compiler platform (LLVM) to automate the program transformation to ensure that the optimized software code is correct by construction. We have evaluated our method on a large number of benchmark programs, which are C programs implementing secure communication protocols that are popular for energy-harvesting IoT devices. Our experimental results show that the method is efficient in optimizing all benchmark programs. Furthermore, the optimized programs significantly outperform the original programs in terms of energy efficiency and latency, and the overall improvement ranges from 2.3X to 36.7X.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Compilers
  • Theory of computation → Constraint and logic programming
Keywords
  • Compiler
  • energy optimization
  • constraint solving
  • cryptography
  • IoT

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Saad Ahmed, Naveed Anwar Bhatti, Muhammad Hamad Alizai, Junaid Haroon Siddiqui, and Luca Mottola. Efficient intermittent computing with differential checkpointing. In Jian-Jia Chen and Aviral Shrivastava, editors, ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems, pages 70-81. ACM, 2019. URL: https://doi.org/10.1145/3316482.3326357.
  2. Saad Ahmed, Muhammad Nawaz, Abu Bakar, Naveed Anwar Bhatti, Muhammad Hamad Alizai, Junaid Haroon Siddiqui, and Luca Mottola. Demystifying energy consumption dynamics in transiently powered computers. ACM Trans. Embed. Comput. Syst., 19(6):47:1-47:25, 2020. URL: https://doi.org/10.1145/3391893.
  3. James Allen, Matthew Forshaw, and Nigel Thomas. Towards an extensible and scalable energy harvesting wireless sensor network simulation framework. In Walter Binder, Vittorio Cortellessa, Anne Koziolek, Evgenia Smirni, and Meikel Poess, editors, Companion Proceedings of the 8th ACM/SPEC on International Conference on Performance Engineering, ICPE 2017, L'Aquila, Italy, April 22-26, 2017, pages 39-42. ACM, 2017. URL: https://doi.org/10.1145/3053600.3053610.
  4. Giuseppe Ateniese, Giuseppe Bianchi, Angelo Capossele, and Chiara Petrioli. Low-cost standard signatures in wireless sensor networks: a case for reviving pre-computation techniques? In Network and Distributed System Security Symposium, 2013. Google Scholar
  5. Giuseppe Ateniese, Giuseppe Bianchi, Angelo T Capossele, Chiara Petrioli, and Dora Spenza. Low-cost standard signatures for energy-harvesting wireless sensor networks. ACM Transactions on Embedded Computing Systems, 16(3):64, 2017. Google Scholar
  6. The avr-crypto-lib software package. https://github.com/cantora/avr-crypto-lib. Accessed: 2019-09-26.
  7. Domenico Balsamo, Alex S Weddell, Geoff V Merrett, Bashir M Al-Hashimi, Davide Brunelli, and Luca Benini. Hibernus: Sustaining computation during intermittent supply for energy-harvesting systems. IEEE Embedded Systems Letters, 7(1):15-18, 2015. Google Scholar
  8. Alexei Colin, Graham Harvey, Brandon Lucia, and Alanson P. Sample. An energy-interference-free hardware-software debugger for intermittent energy-harvesting systems. In Tom Conte and Yuanyuan Zhou, editors, International Conference on Architectural Support for Programming Languages and Operating Systems, pages 577-589. ACM, 2016. URL: https://doi.org/10.1145/2872362.2872409.
  9. Alexei Colin and Brandon Lucia. Chain: tasks and channels for reliable intermittent programs. In Eelco Visser and Yannis Smaragdakis, editors, ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 514-530. ACM, 2016. URL: https://doi.org/10.1145/2983990.2983995.
  10. Riccardo Dall'Ora, Usman Raza, Davide Brunelli, and Gian Pietro Picco. SensEH: From simulation to deployment of energy harvesting wireless sensor networks. In IEEE 39th Conference on Local Computer Networks, Edmonton, AB, Canada, 8-11 September, 2014 - Workshop Proceedings, pages 566-573. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/LCNW.2014.6927704.
  11. Leonardo De Moura and Nikolaj Bjørner. Z3: An efficient SMT solver. In International conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 337-340. Springer, 2008. Google Scholar
  12. The tiny Dutch startup solving the IoT industry’s battery problem. https://sifted.eu/articles/nowi-dutch-startup-solving-iot-battery-problem/. Accessed: 2020-08-04.
  13. Hassan Eldib and Chao Wang. An SMT based method for optimizing arithmetic computations in embedded software code. In International Conference on Formal Methods in Computer-Aided Design, pages 129-136. IEEE, 2013. Google Scholar
  14. Hassan Eldib, Chao Wang, Mostafa M. I. Taha, and Patrick Schaumont. Quantitative masking strength: Quantifying the power side-channel resistance of software code. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 34(10):1558-1568, 2015. Google Scholar
  15. Joakim Eriksson, Fredrik Österlind, Thiemo Voigt, Niclas Finne, Shahid Raza, Nicolas Tsiftes, and Adam Dunkels. Accurate power profiling of sensornets with the COOJA/MSPSim simulator. In IEEE 6th International Conference on Mobile Adhoc and Sensor Systems, pages 1060-1061, 2009. Google Scholar
  16. Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In International Conference on Machine Learning, pages 201-210, 2016. Google Scholar
  17. Graham Gobieski, Brandon Lucia, and Nathan Beckmann. Intelligence beyond the edge: Inference on intermittent embedded systems. In International Conference on Architectural Support for Programming Languages and Operating Systems, pages 199-213. ACM, 2019. Google Scholar
  18. Graham Gobieski, Amolak Nagi, Nathan Serafin, Mehmet Meric Isgenc, Nathan Beckmann, and Brandon Lucia. MANIC: A vector-dataflow architecture for ultra-low-power embedded systems. In IEEE/ACM International Symposium on Microarchitecture, pages 670-684, 2019. Google Scholar
  19. Shengjian Guo, Meng Wu, and Chao Wang. Adversarial symbolic execution for detecting concurrency-related cache timing leaks. In ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pages 377-388. ACM, 2018. Google Scholar
  20. Josiah D. Hester, Timothy Scott, and Jacob Sorber. Ekho: realistic and repeatable experimentation for tiny energy-harvesting sensors. In Ákos Lédeczi, Prabal Dutta, and Chenyang Lu, editors, ACM Conference on Embedded Network Sensor Systems, pages 1-15. ACM, 2014. URL: https://doi.org/10.1145/2668332.2668336.
  21. Matthew Hicks. Clank: Architectural support for intermittent computation. In International Symposium on Computer Architecture, pages 228-240. ACM, 2017. URL: https://doi.org/10.1145/3079856.3080238.
  22. Susan Horwitz and Thomas W. Reps. The use of program dependence graphs in software engineering. In Tony Montgomery, Lori A. Clarke, and Carlo Ghezzi, editors, International Conference on Software Engineering, Melbourne, Australia, May 11-15, 1992, pages 392-411, 1992. Google Scholar
  23. Zunchen Huang and Chao Wang. Symbolic predictive cache analysis for out-of-order execution. In International Conference on Fundamental Approaches to Software Engineering, pages 163-183. Springer, 2022. Google Scholar
  24. Texas Instrument. MSP430FR599x Technical Documentation. URL: https://www.ti.com/product/MSP430FR5994.
  25. Hrishikesh Jayakumar, Arnab Raha, Jacob R. Stevens, and Vijay Raghunathan. Energy-aware memory mapping for hybrid FRAM-SRAM mcus in intermittently-powered iot devices. ACM Trans. Embed. Comput. Syst., 16(3):65:1-65:23, 2017. URL: https://doi.org/10.1145/2983628.
  26. Mustafa Emre Karagozler, Ivan Poupyrev, Gary K Fedder, and Yuri Suzuki. Paper generators: harvesting energy from touching, rubbing and sliding. In ACM symposium on User interface software and technology, pages 23-30, 2013. Google Scholar
  27. Sepideh Khoshnood, Markus Kusano, and Chao Wang. ConcBugAssist: constraint solving for diagnosis and repair of concurrency bugs. In International Symposium on Software Testing and Analysis, pages 165-176. ACM, 2015. Google Scholar
  28. The lamport_signature software package. https://github.com/detomastah/lamport_signature. Accessed: 2019-09-26.
  29. Chris Lattner and Vikram Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In International Symposium on Code Generation and Optimization: feedback-directed and runtime optimization, page 75, 2004. Google Scholar
  30. The Libgcrypt software package. https://gnupg.org/software/libgcrypt/index.html. Accessed: 2019-09-26.
  31. The Libmcrypt software package. https://github.com/tugrul/libmcrypt-gyp/tree/master. Accessed: 2019-09-26.
  32. Brandon Lucia and Benjamin Ransford. A simpler, safer programming and execution model for intermittent systems. ACM SIGPLAN Notices, 50(6):575-585, 2015. Google Scholar
  33. Kaisheng Ma, Yang Zheng, Shuangchen Li, Karthik Swaminathan, Xueqing Li, Yongpan Liu, Jack Sampson, Yuan Xie, and Vijaykrishnan Narayanan. Architecture exploration for ambient energy harvesting nonvolatile processors. In IEEE International Symposium on High Performance Computer Architecture, pages 526-537, 2015. Google Scholar
  34. Kiwan Maeng, Alexei Colin, and Brandon Lucia. Alpaca: intermittent execution without checkpoints. Proc. ACM Program. Lang., 1(OOPSLA):96:1-96:30, 2017. URL: https://doi.org/10.1145/3133920.
  35. Kiwan Maeng and Brandon Lucia. Adaptive dynamic checkpointing for safe efficient intermittent computing. In USENIX Symposium on Operating Systems Design and Implementation, pages 129-144, 2018. Google Scholar
  36. Kiwan Maeng and Brandon Lucia. Supporting peripherals in intermittent systems with just-in-time checkpoints. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 1101-1116, 2019. Google Scholar
  37. Shorter Merkle Signatures. https://www.openssl.org. Accessed: 2019-09-26.
  38. Azalia Mirhoseini, Ebrahim M Songhori, and Farinaz Koushanfar. Idetic: A high-level synthesis approach for enabling long computations on transiently-powered ASICs. In IEEE International Conference on Pervasive Computing and Communications, pages 216-224, 2013. Google Scholar
  39. The MSP430 emulator. https://github.com/contiki-ng/mspsim. Google Scholar
  40. OpenSSL. https://www.openssl.org. Accessed: 2019-09-26.
  41. Benjamin Ransford, Jacob Sorber, and Kevin Fu. Mementos: System support for long-running computation on RFID-scale devices. In ACM SIGARCH Computer Architecture News, pages 159-170, 2011. Google Scholar
  42. Thomas W. Reps, Susan Horwitz, and Shmuel Sagiv. Precise interprocedural dataflow analysis via graph reachability. In Ron K. Cytron and Peter Lee, editors, ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Francisco, California, USA, January 23-25, 1995, pages 49-61, 1995. Google Scholar
  43. Emily Ruppel and Brandon Lucia. Transactional concurrency control for intermittent, energy-harvesting computing systems. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 1085-1100, 2019. Google Scholar
  44. Alanson P Sample, Daniel J Yeager, Pauline S Powledge, Alexander V Mamishev, and Joshua R Smith. Design of an rfid-based battery-free programmable sensing platform. IEEE transactions on instrumentation and measurement, 57(11):2608-2615, 2008. Google Scholar
  45. Claude E. Shannon. Communication theory of secrecy systems. Bell Syst. Tech. J., 28(4):656-715, 1949. Google Scholar
  46. Milijana Surbatovich, Limin Jia, and Brandon Lucia. I/O dependent idempotence bugs in intermittent systems. Proceedings of the ACM on Programming Languages, 3(OOPSLA):183, 2019. Google Scholar
  47. Charles Suslowicz, Archanaa S Krishnan, and Patrick Schaumont. Optimizing cryptography in energy harvesting applications. In Proceedings of the Workshop on Attacks and Solutions in Hardware Security, pages 17-26. ACM, 2017. Google Scholar
  48. Joel Van Der Woude and Matthew Hicks. Intermittent computation without hardware support or programmer intervention. In USENIX Symposium on Operating Systems Design and Implementation, pages 17-32, 2016. Google Scholar
  49. Chao Wang and Patrick Schaumont. Security by compilation: an automated approach to comprehensive side-channel resistance. ACM SIGLOG News, 4(2):76-89, 2017. Google Scholar
  50. Jingbo Wang, Chungha Sung, Mukund Raghothaman, and Chao Wang. Data-driven synthesis of provably sound side channel analyses. In International Conference on Software Engineering, pages 810-822. IEEE, 2021. Google Scholar
  51. Jingbo Wang, Chungha Sung, and Chao Wang. Mitigating power side channels during compilation. In ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pages 590-601. ACM, 2019. Google Scholar
  52. Meng Wu, Shengjian Guo, Patrick Schaumont, and Chao Wang. Eliminating timing side-channel leaks using program repair. In Frank Tip and Eric Bodden, editors, ACM SIGSOFT International Symposium on Software Testing and Analysis, pages 15-26. ACM, 2018. Google Scholar
  53. Jiawei Yuan and Shucheng Yu. Privacy preserving back-propagation neural network learning made practical with cloud computing. IEEE Transactions on Parallel and Distributed Systems, 25(1):212-221, 2013. Google Scholar
  54. Jun Zhang, Pengfei Gao, Fu Song, and Chao Wang. SCInfer: Refinement-based verification of software countermeasures against side-channel attacks. In International Conference on Computer Aided Verification, pages 157-177. Springer, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact