Calcul aproximativ

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Calculul aproximativ este orice formă de calcul al cărui rezultat nu este garantat a fi corect. Există mai multe domenii de aplicații în care o aproximare a rezultatului este totuși tolerată. În situații similare, este posibil să se aplice tehnici de aproximare care vă permit să efectuați calculul consumând mai puține resurse decât ar fi necesar pentru un calcul exact.

Un exemplu de câmp de aplicație în care calculul aproximativ găsește spațiu amplu sunt sistemele de planificare a traseului rutier [1] în care, pentru a avea un rezultat într-o perioadă scurtă de timp, se acceptă să urmeze o cale suboptimală în locul celei optime. Un alt exemplu de câmp de aplicație este cel al procesării video. Pentru a efectua procesări deosebit de complexe la fața locului, sunteți de acord să săriți ocazional un cadru . Această tehnică exploatează faptul că într-o anumită rată de cadre aparatul vizual al unei ființe umane nu percepe defecte în videoclip. Tehnici similare sunt utilizate pe scară largă în jocurile video [2] .

Factorul cheie pentru aplicarea strategiilor de aproximare este identificarea procedurilor care pot fi aproximate cu mari economii de resurse fără repercusiuni drastice asupra calității rezultatului [3] . Există situații în care identificarea unor astfel de proceduri este banală; există condiții în care numai un expert în domeniul aplicației este capabil să izoleze operațiunile mai puțin sensibile la erori; foarte des este vorba de a ajunge la un compromis între performanța pe care doriți să o îmbunătățiți și eroarea pe care o introduceți. În acest din urmă caz, se utilizează studiul propagării erorilor în cadrul algoritmului de procesare analizat.

Strategii

Calculul aproximativ poate fi aplicat la diferite niveluri de granularitate și în contexte diferite.

Aproximare hardware

Componentele logice pot fi proiectate și construite astfel încât să ofere rezultate aproximative mai rapide și / sau consumând mai puțină energie decât componentele lor corespunzătoare.

Există doi factori asupra cărora se poate acționa pentru a obține performanță: logica circuitului [4] [5] și condițiile de lucru [3] . În primul caz, aproximarea are ca scop eliminarea din circuit a logicii necesare gestionării configurațiilor de intrare rare. Componenta va da rezultatul exact de cele mai multe ori. În sistemele care implementează de fapt soluții de acest tip, este o practică obișnuită să combinați hardware aproximativ cu componentele exacte și să stabiliți politici pentru utilizarea uneia și a celeilalte. În al doilea caz, circuitul poate fi alimentat la tensiune redusă pentru a economisi energie în detrimentul unei eventuale corupții accidentale a datelor ( flipping de biți ).

Aproximarea datelor

Este posibil să renunțați parțial la exactitatea datelor procesate și / sau arhivate pentru a economisi resurse.

Un exemplu este prelucrarea datelor în virgulă mobilă . Există diferite standarde de reprezentare binară a numerelor cu virgulă mobilă (float, dublu, ...) și fiecare dintre ele garantează o precizie diferită. Prelucrarea unui număr reprezentat conform unui standard mai precis necesită mai mult timp și energie decât un număr care urmează un standard mai puțin precis. Standardul de reprezentare utilizat este de obicei stabilit de programatorul de sistem. Aplicarea forțată a unui standard de precizie mai redus unei porțiuni din procesarea și / sau stocarea (unei porțiuni din) date economisește timp și energie.

De asemenea, este posibil să se acționeze asupra hardware-ului care controlează datele făcând reprezentarea datelor în memorie sau prezența lor în memorie aproximativă. Primul caz include structuri de memorie care trunchiază cele mai puțin semnificative biți dintr-un număr. Un exemplu al celui de-al doilea caz sunt sistemele de memorie volatile ( DRAM și altele asemenea) atunci când sunt actualizate la frecvențe mai mici decât cele standard pentru a consuma mai puțină energie [3] [4] ; acest lucru poate compromite consistența datelor din memorie.

Dezactivarea sistemelor de control și corectare a erorilor reduce timpul de procesare al unui pachet de date în detrimentul garanțiilor privind corectitudinea acestuia.

Aproximare software

Puteți aproxima logica software-ului în sine pentru a consuma mai puține resurse.

Unii algoritmi de construcție oferă garanții cu privire la consumul unei resurse (de obicei, timpul de terminare), dar nu și cu privire la acuratețea rezultatului. Această clasă include algoritmi Monte Carlo randomizați .

Mai general, există tehnici care pot fi aplicate majorității aplicațiilor [3] . Unii dintre ei sunt:

  • Perforarea buclei vă permite să omiteți sistematic iterațiile unei bucle. Acest lucru vă permite să reduceți timpul de execuție. Efectul acestei aproximări are asupra erorii finale depinde de logica aplicației în sine.
  • Saltarea sarcinilor vă permite să săriți executarea unor operații ( sarcini ), de obicei cele mai complexe și solicitante din punct de vedere al calculului. Acest salt se aplică atunci când, în timpul execuției, apar condiții care fac inutilă sau foarte probabil inutilă execuția operațiunilor obiect al saltului.
  • Memorizarea constă în stocarea rezultatelor parțiale ale unor proceduri utilizate foarte frecvent și apoi reutilizarea lor în loc de a rula din nou procedura pentru a le recalcula.

Domenii de aplicare

Calculul aproximativ este utilizat pe scară largă în toate domeniile de aplicații tolerante la erori. Câteva exemple sunt:

Paradigme derivate

Calculul aproximativ are ca principală limitare identificarea impactului pe care o posibilă aproximare îl are asupra rezultatului final. În cazul aplicațiilor la scară largă, se întâmplă adesea ca cei care au cunoștințe suficiente despre domeniul aplicației să nu aibă cunoștințe tehnice pentru a implementa corect tehnici de aproximare. Derivate din aceste probleme, au apărut paradigme de programare [6] [7] care separă în mod clar rolurile de expert în domeniu și expert în eficiență. Acest lucru reduce nivelul minim de cunoștințe al unei singure figuri profesionale pentru a aplica tehnici aproximative de calcul și favorizează difuzarea acestora.

Notă

  1. ^ (RO) Gilbert Laporte, Problema de rutare a vehiculului: o privire de ansamblu asupra algoritmilor exacți și aproximativi, în European Journal of Operational Research, vol. 59, nr. 3, Elsevier, 1992, pp. 345-358.
  2. ^ (EN) Alex Braylan, Mark Hollenbeck, Elliot Meyerson și Risto Miikkulainen, Frame skip este un parametru puternic pentru învățarea jocului atari, în Space, vol. 1600, 2000, p. 1800.
  3. ^ a b c d ( EN ) Sparsh Mittal, A Survey of Techniques for Approximate Computing , în ACM Comput. Surv. , vol. 48, nr. 4, ACM, mai 2016, pp. 62: 1–62: 33, DOI : 10.1145 / 2893356 .
  4. ^ a b ( EN ) Q. Xu și T. Mytkowicz și NS Kim, Aproximate Computing: A Survey , în IEEE Design Test , vol. 33, nr. 1, februarie 2016, pp. 8 - - 22, DOI : 10.1109 / MDAT.2015.2505723 .
  5. ^ (EN) Zhu, Ning și Goh, Wang Ling și Zhang, Weija și Yeo Kiat Seng și Kong Zhi Hui, Proiectarea sumatorului de trunchiere cu eroare de mare viteză și toleranța la erori și aplicarea acestuia în procesarea semnalului digital, în tranzacțiile IEEE pe sisteme de integrare la scară foarte mare (VLSI) , vol. 18, nr. 8, IEEE, 2010, pp. 1225 - - 1229.
  6. ^ (EN) Donald Nguyen, Andrew Lenharth și Keshav Pingali, O infrastructură ușoară pentru analiza grafică, în Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, ACM, 2013, pp. 456 - - 471.
  7. ^ (EN) Cristina Silvano, John Agosta, Stefano Cherubin, David Gadioli, Gianluca Palermo, Andrea Bartolini, Luca Benini, Jan Martinovič, Martin Palkovič, Kateřina Slaninová, João Bispo, João MP Cardoso, Abreu Rui Pedro Pinto, Carlo Cavazzoni, Nico Sanna, Andrea R. Beccari, Radim Cmar și Erven Rohou, Abordarea ANTAREX la reglarea automată și adaptabilitatea sistemelor HPC eficiente din punct de vedere energetic , în Proceedings of the ACM International Conference on Computing Frontiers , ACM, 2016, pp. 288 - - 293.

Bibliografie

  • ( EN ) Gilbert Laporte, Problema de rutare a vehiculelor: o privire de ansamblu asupra algoritmilor exacți și aproximativi , în European Journal of Operational Research , vol. 59, nr. 3, Elsevier, 1992, pp. 345-358.
  • ( EN ) Alex Braylan, Mark Hollenbeck, Elliot Meyerson și Risto Miikkulainen, Frame skip este un parametru puternic pentru învățarea jocului atari , în Space , vol. 1600, 2000, p. 1800.
  • (EN) Sparsh Mittal, A Survey of Techniques for Computing Approximate , în ACM Comput. Surv. , vol. 48, nr. 4, ACM, mai 2016, pp. 62: 1–62: 33, DOI : 10.1145 / 2893356 .
  • ( EN ) Q. Xu și T. Mytkowicz și NS Kim, Aproximate Computing: A Survey , în IEEE Design Test , vol. 33, nr. 1, februarie 2016, pp. 8 - - 22, DOI : 10.1109 / MDAT.2015.2505723 .
  • (RO) Zhu, Ning și Goh, Wang Ling și Zhang, Weija și Yeo, Kiat Seng și Kong, Zhi Hui, Design de consum redus de energie de mare viteză vipera trunchierea-eroare-tolerante și aplicarea acesteia în procesarea semnalului digital, în IEEE Tranzacții pe sisteme de integrare la scară foarte mare (VLSI) , vol. 18, nr. 8, IEEE, 2010, pp. 1225 - - 1229.
  • ( EN ) Donald Nguyen, Andrew Lenharth și Keshav Pingali, O infrastructură ușoară pentru analiza graficelor , în 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 MP Cardoso, Abreu Rui, Pedro Pinto, Carlo Cavazzoni, Nico Sanna, Andrea R. Beccari, Radim Cmar și Erven Rohou, Abordarea ANTAREX la reglarea automată și adaptabilitatea sistemelor HPC eficiente din punct de vedere energetic , în Proceedings of the ACM International Conference on Computing Frontiers , ACM, 2016, pp. 288 - - 293.

Elemente conexe

Adus de la „ https://it.wikipedia.org/w/index.php?title=Calculation_approximate&oldid=121932070 ”