A case for approximate intermittent computing

The Internet of Things is nowadays part of our daily lives: embedded devices animate sensors, actuators and other tools that can collect or transmit informa- tion about physical objects. At the same time, powerful data analysis techniques are making it possible to make sense and control an amount of data never seen before. Despite the opportunities the IoT is creating, there are important criti- calities that still hinder the diffusion of this technology. An increasingly pressing issue is how to make the massive deployment of billions of devices sustainable: the vast majority of embedded devices is powered up by disposable batteries. Not only do batteries have an important environmental impact at the end of the lifecycle of the devices, but they are also hard and costly to replace when devices are deployed in remote or inaccessible areas. These characteristics of batteries make it necessary to find alternative solutions to unlock a massive adoption of the IoT. As a consequence, a new paradigm is gaining momentum: we are talking about Transiently Powered Computing (TPC). The idea of TPC is to use energy harvesting techniques to extract from the environment small and unreliable energy streams, which can be used to power up embedded devices virtually independent from batteries. However, applications deployed in TPC devices are subject to problems totally different from traditional computing. The sources that are used for energy har- vesting produce a highly unpredictable power throughput, and therefore TPC devices can turn off unpredictably, losing their internal state and the partial results of the computations they were performing. As a consequence, even small energy savings can make the difference from pro- ducing a result or nothing at all. The goal of this thesis is to address the domain of TPC using the techniques of Approximate Computing (AC). AC aims to al- ter the execution of arbitrary applications introducing some degree of error to produce a higher degree of saving. Approximate Computing Techniques (ACTs) make it possible to save computation time, memory and energy. In this work, we will focus on the ACT of Iterative Refinement: it consists of starting from an initially rough solution, and continuously invest computational effort to improve it. By construction, Iterative Refinement (or Anytime) algo- rithms can always yield a feasible result: as a consequence, whenever a power failure occurs, it is possible to react by submitting the partial solution computed so far. We have applied this ACT to create an Anytime version of Support Vector Ma- chines (ASVM). We applied ASVM to a Human Activity Recognition (HAR) problem, and compared the performance of our method with a state-of-the-art TPC solution. ASVM saved up to 41% of the energy cost of executions while paying an ac- curacy loss always below 20% also in the scenarios where we applied the most aggressive approximations. Moreover, the results produced by ASVM were more timely by up to 10s when the sampling rate is 50Hz.

L’Internet delle Cose è oggi parte della nostra vita quotidiana: i dispositivi embedded animano sensori, attuatori e altri strumenti in grado di raccogliere o trasmettere informazioni a proposito di oggetti fisici. Allo stesso tempo, po- tenti tecniche di analisi dei dati stanno permettendo di dare un senso e di controllare una quantità di dati mai vista prima. Nonostante le opportunità che l’internet degli oggetti sta creando, ci sono importanti criticità che ancora ostacolano la diffusione di questa tecnologia. Una questione sempre più pres- sante è come rendere sostenibile il massiccio dispiegamento di miliardidi dis- positivi: la stragrande maggioranza dei dispositivi embedded è alimentata da batterie usa e getta. Non solo le batterie hanno un importante impatto ambi- entale alla fine del ciclo di vita dei dispositivi, ma sono anche difficili e costosi da sostituire quando i dispositivi sono installati in aree remote o inaccessibili. Queste caratteristiche delle batterie rendono necessario trovare soluzioni alterna- tive per sbloccare l’adozione massiccia dell’internet delle cose. Di conseguenza, un il nuovo paradigma sta prendendo piede: il Transiently Powered Computing (TPC). L’idea del TPC è di utilizzare tecniche di energy harvesting per estrarre dall’ambiente piccoli e inaffidabili flussi di energia, che possono essere utiliz- zati per alimentare dispositivi embedded praticamente indipendenti dalle bat- terie. Tuttavia, le applicazioni implementate nei dispositivi TPC sono soggette a problemi totalmente diversi dall’informatica tradizionale. Le fonti utilizzabili tramite energy harvesting producono flussi inaffidabili e altamente imprevedibili, e quindi i dispositivi TPC possono spegnersi in modo imprevedibile, perdendo il loro stato interno e i risultati parziali dei calcoli che stavano eseguendo. Di con- seguenza, anche piccoli risparmi di energia possono fare la differenza tra ottenere un risultato, o nulla in assoluto. L’obiettivo di questa tesi è di affrontare i prob- lemi del TPC utilizzando le tecniche di Approximate Computing (AC). Lo scopo dell’AC è di modificare l’esecuzione di applicazioni arbitrarie introducendo un certo grado di errore per produrre un maggior grado di risparmio. Tecniche di calcolo approssimato (ACT) consentono di risparmiare tempo di calcolo, memo- ria ed energia. In questo lavoro ci concentreremo sull’Iterative Refinement: esso consiste nel partire da una soluzione inizialmente approssimata, e investire con- tinuamente ulteriore sforzo computazionale per migliorarla. Per costruzione, gli algoritmi che fanno uso di iterative Refinement (o Anytime) possono in ogni istante restituire un risultato accettabile: di conseguenza, ogni volta che una il dispositivo embedded si spegne per via della mancanza di energia è possibile reagire presentando la soluzione parziale calcolata fino a quel momento. Abbi- amo applicato questa ACT per creare una versione Anytime di Support Vector Machines (ASVM). Abbiamo applicato ASVM al riconoscimento delle attività umane (HAR), e confrontato le prestazioni del nostro metodo con una soluzione stato dell’arte basata sulla tecnica del checkpointing. ASVM ha risparmiato fino al 41% del costo energetico dell’esecuzione, perdendo al contempo sem- pre meno del 20% di accuratezza anche negli scenari in cui abbiamo applicato un’approssimazione più aggressiva. Inoltre, i risultati prodotti da ASVM hanno un anticipo fino a 10s quando la frequenza di campionamento è di 50Hz.