Calcolo approssimato

Il calcolo approssimato è una qualunque forma di calcolo il cui risultato non è garantito essere corretto. Esistono diversi domini applicativi dove una approssimazione del risultato è comunque tollerata. In situazioni simili è possibile applicare tecniche di approssimazione che consentono di eseguire il calcolo consumando una quantità di risorse inferiore rispetto a quanta ne sarebbe richiesta da un calcolo esatto.

Un esempio di campo applicativo dove il calcolo approssimato trova ampio spazio sono i sistemi di pianificazione di itinerari stradali dove pur di avere un risultato entro un breve lasso di tempo, si accetta di seguire un percorso subottimo invece del percorso ottimo. Un altro esempio di campo applicativo è quello dell'elaborazione video. Per effettuare sul momento elaborazioni particolarmente complesse si accetta di saltare occasionalmente un fotogramma. Questa tecnica sfrutta il fatto che entro un certo valore di frame rate l'apparato visivo di un essere umano non percepisce difetti nel video. Simili tecniche sono ampiamente utilizzate in ambito videoludico.

Il fattore chiave per l'applicazione di strategie di calcolo approssimato è l'identificazione delle procedure che possono essere approssimate con grande risparmio di risorse senza drastiche ripercussioni sulla qualità del risultato. Esistono situazioni in cui l'identificazione di tali procedure è banale; esistono condizioni in cui solo un esperto del dominio applicativo è in grado di isolare le operazioni meno sensibili agli errori; molto spesso si tratta di raggiungere un compromesso tra le prestazioni che si desidera migliorare e l'errore che si introduce. Nell'ultimo caso si ricorre allo studio della propagazione degli errori all'interno dell'algoritmo di elaborazione in analisi.

Strategie

Il calcolo approssimato può essere applicato a diversi livelli di granularità e in diversi contesti.

Approssimazione dell'hardware

È possibile progettare e realizzare componenti logici che forniscono risultati approssimati in tempi più rapidi e/o consumando meno potenza rispetto ai corrispettivi componenti esatti.

Due sono i fattori sui quali si può agire per guadagnare prestazioni: la logica del circuito e le condizioni di lavoro. Nel primo caso l'approssimazione mira ad eliminare dal circuito la logica necessaria a gestire configurazioni di input poco frequenti. Il componente fornirà il risultato esatto la maggior parte delle volte. Nei sistemi che realmente implementano soluzioni di questo tipo è pratica comune affiancare hardware approssimato a componenti esatti e stabilire politiche di utilizzo di uno e dell'altro. Nel secondo caso il circuito può essere alimentato a tensione ridotta per risparmiare energia a scapito di una possibile corruzione accidentale dei dati (bit flipping).

Approssimazione dei dati

È possibile rinunciare parzialmente alla precisione dei dati che sono oggetto di elaborazione e/o di archiviazione per risparmiare risorse.

Un esempio è l'elaborazione dei dati in virgola mobile. Esistono diversi standard di rappresentazione binaria di numeri in virgola mobile (float, double, ...) e ciascuno di essi garantisce una diversa precisione. L'elaborazione di un numero rappresentato secondo uno standard a maggiore precisione richiede più tempo ed energia rispetto ad un numero che segue uno standard meno preciso. Lo standard di rappresentazione utilizzato è di solito impostato dal programmatore del sistema. Applicare forzosamente, per una parte dell'elaborazione e/o archiviazione di (una parte dei) dati, uno standard a precisione inferiore consente di risparmiare tempo ed energia.

È possibile agire anche sull'hardware che controlla i dati rendendo approssimata la rappresentazione dei dati in memoria o la loro presenza in memoria. Nel primo caso rientrano le strutture di memoria che troncano i bit meno significativi di un numero. Un esempio del secondo caso sono i sistemi di memoria volatile (DRAM e simili) quando vengono aggiornati a frequenze inferiori rispetto a quelle standard per consumare meno potenza; questo può compromettere la coerenza dei dati in memoria.

La disabilitazione dei sistemi di controllo e correzione degli errori riduce il tempo di elaborazione di un pacchetto di dati a scapito di garanzie sulla correttezza degli stessi.

Approssimazione del software

È possibile approssimare la logica del software stesso per consumare meno risorse.

Alcuni algoritmi per costruzione forniscono garanzia sul consumo di una risorsa (tipicamente tempo di terminazione) ma non sull'esattezza del risultato. In questa classe rientrano gli algoritmi randomizzati di tipo Monte Carlo.

Più in generale, esistono tecniche che possono essere applicate alla maggior parte delle applicazioni. Alcune di esse sono:

• Loop perforation consente di saltare sistematicamente iterazioni di un ciclo. Questo consente ridurre il tempo di esecuzione. L'effetto che questa approssimazione ha sull'errore finale dipende dalla logica dell'applicazione stessa.
• Task skipping consente di saltare l'esecuzione di alcune operazioni (task), di solito i più complessi e impegnativi dal punto di vista computazionale. Questo salto viene applicato qualora durante l'esecuzione di verificano condizioni che rendono inutile o molto probabilmente inutile l'esecuzione delle operazioni oggetto del salto.
• Memoizzazione consiste nel memorizzare risultati parziali di alcune procedure utilizzate molto di frequente per poi riutilizzarli al posto di eseguire nuovamente la procedura per ricalcolarli.

Aree di applicazione

Il calcolo approssimato è ampiamente utilizzato in tutti i domini applicativi che tollerano errori. Alcuni esempi sono:

• Elaborazione video
• Teoria dei segnali
• Analisi numerica
• High Performance Computing
• Apprendimento automatico
• Pianificazione di itinerari stradali
• Sviluppo di videogiochi

Paradigmi derivati

Il calcolo approssimato ha come principale limitazione l'identificazione dell'impatto che una possibile approssimazione ha sul risultato finale. Su applicazioni di larga scala spesso accade che chi possiede conoscenza sufficiente riguardo al dominio applicativo non possiede le conoscenze tecniche per implementare correttamente tecniche di calcolo approssimato. Derivati da questi problemi, sono emersi paradigmi di programmazione che nettamente separano i ruoli di esperto del dominio e di esperto di efficienza. Questo riduce il livello minimo di conoscenze di una singola figura professionale per applicare le tecniche di calcolo approssimato e ne favorisce la loro diffusione.

Bibliografia

• (EN) Gilbert Laporte, The vehicle routing problem: An overview of exact and approximate algorithms, in European Journal of Operational Research, vol. 59, n. 3, Elsevier, 1992, pp. 345--358.
• (EN) Alex Braylan, Mark Hollenbeck, Elliot Meyerson e Risto Miikkulainen, Frame skip is a powerful parameter for learning to play atari, in Space, vol. 1600, 2000, p. 1800.
• (EN) Sparsh Mittal, A Survey of Techniques for Approximate Computing, in ACM Comput. Surv., vol. 48, n. 4, ACM, May 2016, pp. 62:1--62:33, DOI:10.1145/2893356.
• (EN) Q. Xu and T. Mytkowicz and N. S. Kim, Approximate Computing: A Survey, in IEEE Design Test, vol. 33, n. 1, Febbraio 2016, pp. 8 - - 22, DOI:10.1109/MDAT.2015.2505723.
• (EN) Zhu, Ning and Goh, Wang Ling and Zhang, Weija and Yeo, Kiat Seng and Kong, Zhi Hui, Design of low-power high-speed truncation-error-tolerant adder and its application in digital signal processing, in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 18, n. 8, IEEE, 2010, pp. 1225 - - 1229.
• (EN) Donald Nguyen, Andrew Lenharth e Keshav Pingali, A lightweight infrastructure for graph analytics, in Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, ACM, 2013, pp. 456 - - 471.
• (EN) Cristina Silvano, Giovanni Agosta, Stefano Cherubin, Davide Gadioli, Gianluca Palermo, Andrea Bartolini, Luca Benini, Jan Martinovič, Martin Palkovič, Kateřina Slaninová, João Bispo, João M. P. Cardoso, Abreu Rui, Pedro Pinto, Carlo Cavazzoni, Nico Sanna, Andrea R. Beccari, Radim Cmar e Erven Rohou, The ANTAREX approach to autotuning and adaptivity for energy efficient HPC systems, in Proceedings of the ACM International Conference on Computing Frontiers, ACM, 2016, pp. 288 - - 293.

Voci correlate

• Programma (informatica)
• Ottimizzazione (informatica)
• Parallelizzazione automatica
• Codice sorgente