Inkrementální výpočet - Incremental computing

Inkrementální výpočet, také známý jako přírůstkový výpočet, je softwarová funkce který, kdykoli kousek data změny, pokusy o uložení čas pouze přepočítáním těch výstupů, které závisí na změněných datech.[1][2][3] Když je přírůstkové výpočty úspěšné, může to být výrazně rychlejší než naivní výpočet nových výstupů. Například a tabulkový kalkulátor softwarový balíček může ve své funkci přepočtu používat přírůstkové výpočty k aktualizaci pouze těch buněk obsahujících vzorce, které (přímo nebo nepřímo) závisí na změněných buňkách.

Když je přírůstkové počítání implementováno nástrojem, který jej může automaticky implementovat pro různé části kódu, je tento nástroj příkladem programová analýza nástroj pro optimalizace.

Inkrementální výpočet poskytuje prostředek pro výpočet nového páru vstupů a výstupů (I2, O2) na základě starého páru vstupů a výstupů (I1, O1). Klíčovou technikou je funkce ΔP, která spojuje změny ve vstupu se změnami ve výstupu.
Přírůstkové výpočty odvozují nový pár vstup / výstup z jednoho nebo více starých vztahů vstup / výstup. K tomu musí ΔP spojit změnu vstupu se změnou výstupu. Spotřebitele výsledku může zajímat plně aktualizovaný výstup nebo delta výstup nebo obojí.

Statický versus dynamický

Inkrementální výpočetní techniky lze obecně rozdělit do dvou typů přístupů:

Statické přístupy pokusit se odvodit přírůstkový program od konvenčního programu P pomocí např. buď manuálního návrhu a refaktoringu, nebo automatických transformací programu. K těmto programovým transformacím dochází před poskytnutím jakýchkoli vstupů nebo vstupních změn.

Dynamické přístupy zaznamenat informace o provádění programu P na konkrétním vstupu (I1) a použít tyto informace, když se vstup změní (na I2), aby se aktualizoval výstup (z O1 na O2). Obrázek ukazuje vztah mezi programem P, funkcí výpočtu změny ΔP, která tvoří jádro inkrementálního programu, a dvojicí vstupů a výstupů, I1, O1 a I2, O2.

Specializované versus univerzální přístupy

Některé přístupy k přírůstkovému výpočtu jsou specializované, zatímco jiné mají obecný účel. Specializované přístupy vyžadují, aby programátor explicitně určil algoritmy a datové struktury, které se použijí k zachování nezměněných dílčích výpočtů. Obecné přístupy na druhé straně používají jazykové, kompilátorové nebo algoritmické techniky k poskytnutí přírůstkového chování jinak neinkrementálních programů.[4]

Statické metody

Programové deriváty

Vzhledem k výpočtu a potenciální změna , můžeme vložit kód před změnou (pre-derivát) a po změně (post-derivát) k aktualizaci hodnoty rychlejší než opakované spuštění . Paige sepsala seznam pravidel pro formální rozlišení programů v SUBSETL.[5]

Zobrazit údržbu

V databázových systémech, jako je DBToaster, jsou pohledy definovány pomocí relační algebry. Inkrementální údržba pohledu staticky analyzuje relační algebru a vytváří pravidla aktualizace, která rychle udržují pohled v přítomnosti malých aktualizací, jako je vložení řádku.[6]

Dynamické metody

Inkrementálního výpočtu lze dosáhnout sestavením a graf závislosti všech datových prvků, které je třeba přepočítat, a jejich závislostí. The elements that need to be updated when a single element changes are given by the přechodné uzavření vztahu závislosti grafu. Jinými slovy, pokud existuje cesta od změněného prvku k jinému prvku, může být tento prvek aktualizován (v závislosti na tom, zda se změna nakonec dostane k prvku). Je možné, že bude třeba graf závislosti aktualizovat při změně závislostí nebo při přidávání nebo odebírání prvků ze systému. Používá se interně implementací a obvykle se nemusí uživateli zobrazovat.

Zachycení závislostí napříč všemi možnými hodnotami se lze vyhnout určením podmnožiny důležitých hodnot (např. Výsledků agregace), ve kterých lze závislosti sledovat, a postupným přepočítáváním dalších závislých proměnných, a tím vyvážením množství informací o závislostech, které mají být sledovány, množstvím přepočítání provést při změně vstupu.[7]

Částečné hodnocení lze chápat jako metodu pro automatizaci nejjednoduššího možného případu přírůstkového výpočtu, při kterém se pokusí rozdělit programová data do dvou kategorií: ta, která se může lišit na základě vstupu programu, a ta, která nemůže (a nejmenší jednotka změna je jednoduše „všechna data, která se mohou lišit“). Částečné vyhodnocení lze kombinovat s dalšími postupnými výpočetními technikami.

U cyklů v závislostním grafu nemusí jediný průchod grafem stačit k dosažení pevného bodu. V některých případech je úplné přehodnocení systému sémanticky ekvivalentní s přírůstkovým hodnocením a může být v praxi efektivnější, ne-li teoreticky.[8]

Stávající systémy

Podpora překladačů a jazyků

  • Automatická inkrementalizace (nazývaná také „Samočinná úprava výpočtu“ a „Adaptivní funkční programování“),[9] Delta ML, Haskell Adaptive
  • Generátor syntetizátoru Cornell[10]
  • IceDust - vlastní jazyk specifický pro doménu.

Rámečky a knihovny

  • Adapton[11] - s implementacemi v několika jazycích
  • Omezení jednosměrného toku dat (reaktivní výpočet v C ++)
  • Diferenciální tok dat
  • Jane Street Přírůstkové
  • Inkrementální Datalog (Logicblox)
  • Inkrementální Prolog (XSB)[12]
  • Přístupy specifické pro doménu:
    • Postupná kontrola typu

Aplikace

  • Databáze (údržba zobrazení)
  • Budujte systémy
  • Tabulky[13]
  • Vývojová prostředí
  • Finanční výpočty
  • Hodnocení gramatiky atributů
  • Grafické výpočty a dotazy
  • GUI (např. React a DOM diffing)
  • Vědecké aplikace

Viz také

Reference

  1. ^ Carlsson, Magnus (2002). "Monády pro přírůstkové výpočty". Sborník příspěvků ze sedmé mezinárodní konference ACM SIGPLAN o funkčním programování. New York: ACM. 26–35. doi:10.1145/581478.581482. ISBN  1-58113-487-8.
  2. ^ Umut A. Acar (2005). Samonastavovací výpočet (PDF) (Disertační práce).
  3. ^ Camil Demetrescu; Irene Finocchi; Andrea Ribichini (2011). „Reaktivní imperativní programování s omezeními toku dat“. Sborník z 26. mezinárodní konference ACM o jazycích a aplikacích objektově orientovaných programovacích systémů (OOPSLA 2011). ACM. 407–426. arXiv:1104.2293. doi:10.1145/2048066.2048100. ISBN  978-1-4503-0940-0.
  4. ^ Yan Chen; Joshua Dunfield; Matthew A. Hammer; Umut A. Acar. Implicitní samočinně se přizpůsobující výpočet pro čistě funkční programy. ICFP '11. str. 129–141. Archivovány od originál dne 2016-10-30. Citováno 2018-03-12.
  5. ^ Paige, Robert (1981). Formální diferenciace: Technika syntézy programu. UMI Research Press. ISBN  978-0-8357-1213-2.
  6. ^ Ahmad, Yanif; Kennedy, Oliver; Koch, Christoph; Nikolic, Milos (01.06.2012). "DBToaster: Delta zpracování vyššího řádu pro dynamická, často nová zobrazení". Proc. VLDB Endow. 5 (10): 968–979. arXiv:1207.0137. doi:10.14778/2336664.2336670. ISSN  2150-8097.
  7. ^ Mugilan Mariappan; Keval Vora (2019). "GraphBolt: Závislostem řízené synchronní zpracování streamovacích grafů". V rámci Evropské konference o počítačových systémech (EuroSys'19). s. 25: 1–25: 16. doi:10.1145/3302424.3303974.
  8. ^ Kimberley Burchett; Gregory H. Cooper; Shriram Krishnamurthi (2007). "Snížení: Technika statické optimalizace pro transparentní funkční reaktivitu". V ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation. 71–80. CiteSeerX  10.1.1.90.5866. ISBN  978-1-59593-620-2.
  9. ^ Hammer, Matthew A .; Acar, Umut A .; Chen, Yan (2009). „CEAL“. Sborník konferencí ACM SIGPLAN 2009 o návrhu a implementaci programovacího jazyka - PLDI '09. p. 25. doi:10.1145/1542476.1542480. ISBN  9781605583921.
  10. ^ Reps, Thomas; Teitelbaum, Tim (1984). Msgstr "Generátor syntetizátoru". Sborník prvního sympozia softwarového inženýrství ACM SIGSOFT / SIGPLAN o praktických prostředích pro vývoj softwaru - SDE 1. str. 42–48. doi:10.1145/800020.808247. ISBN  978-0897911313.
  11. ^ „Adapton: Programovací jazykové abstrakce pro přírůstkové výpočty“. adapton.org. Citováno 2016-10-07.
  12. ^ Saha, Diptikalyan; Ramakrishnan, C. R. (2005). "Přírůstkové vyhodnocení předloženého Prologu: nad rámec čistě logických programů". Praktické aspekty deklarativních jazyků. Přednášky z informatiky. 3819. 215–229. CiteSeerX  10.1.1.111.7484. doi:10.1007/11603023_15. ISBN  978-3-540-30947-5. ISSN  0302-9743.
  13. ^ Hammer, Matthew; Phang, Khoo; Hicks, Michael; Foster, Jeffrey (2014). ADAPTON: Skladatelný přírůstkový výpočet na základě poptávky (PDF). PLDI.