Reverzní výpočet - Reverse computation - Wikipedia

Reverzní výpočet je software použití pojmu reverzibilní výpočet.

Protože nabízí možné řešení problému s teplem, kterému čelí výrobci čipů, byl reverzibilní výpočet rozsáhle studován v oblasti počítačové architektury. Příslib reverzibilního výpočtu spočívá v tom, že množství tepelné ztráty pro reverzibilní architektury by bylo minimální pro významně velké množství tranzistorů.[1][2] Spíše než vytvářet entropii (a tím i teplo) prostřednictvím destruktivních operací, reverzibilní architektura šetří energii prováděním dalších operací, které zachovávají stav systému.[3][4]

Koncept reverzního výpočtu je poněkud jednodušší než reverzibilní výpočet, protože reverzní výpočet je vyžadován pouze k obnovení ekvivalent stav softwarové aplikace, spíše než podporovat reverzibilitu sady všech možných pokynů. Reverzibilní výpočetní koncepty byly úspěšně použity jako zpětný výpočet v oblastech softwarových aplikací, jako je návrh databáze,[5] kontrolní bod a ladění,[6] a diferenciace kódu.[7][8]

Zpětný výpočet pro paralelní diskrétní simulaci událostí

Seznam operací, které jsou zpětně vypočítatelné a jejich náklady.

Na základě úspěšné aplikace konceptů reverzní výpočty v jiných softwarových doménách, Chris Carothers, Kalyan Perumalla a Richard Fujimoto[9] navrhnout použití zpětného výpočtu ke snížení režijních nákladů šetřících stav paralelní diskrétní simulace událostí (PDES). Definují přístup založený na kódech reverzní události (které lze automaticky generovat) a prokazují výkonnostní výhody tohoto přístupu oproti tradičnímu ukládání stavu pro jemnozrnné aplikace (ty s malým množstvím výpočtu na událost) .The key property that reverse computation využívá, že většina operací, které mění stavové proměnné, má „konstruktivní“ povahu. Toto je vrátit operace pro takové operace nevyžaduje žádnou historii. K vrácení operace jsou vyžadovány pouze nejaktuálnější hodnoty proměnných. Například operátoři jako ++, ––, + =, - =, * = a / = patří do této kategorie. Upozorňujeme, že operátory * = a / = vyžadují zvláštní zacházení v případě podmínek násobení nebo dělení nulou a přetečení / podtečení. Složitější operace, jako je kruhový posun (swap je zvláštní případ) a určité třídy generování náhodných čísel také sem patří.

Operace formuláře a = b, modulo a bitový výpočty, které vedou ke ztrátě dat, se označují jako destruktivní. Tyto operace lze obvykle obnovit pouze pomocí konvenčních technik šetření stavu. Pozorujeme však, že mnoho z těchto destruktivních operací je důsledkem příchodu dat obsažených ve zpracovávané události. Například v práci Yaun, Carothers, et al., Ve velkém měřítku TCP simulace,[10] čas posledního odeslání zaznamenává časové razítko posledního paketu předaného logickému procesu routeru. Díky operaci výměny je tato operace reverzibilní.

Historie zpětného výpočtu, jak je aplikována na paralelní diskrétní simulaci událostí

Taxonomie digitální simulace.

V roce 1985 představil Jefferson optimistický synchronizační protokol, který byl použit v paralelních diskrétních simulacích událostí, známých jako Time Warp.[11] K dnešnímu dni je technika známá jako Zpětný výpočet byl použit pouze v softwaru pro optimisticky synchronizovanou simulaci paralelních diskrétních událostí.

V prosinci 1999 absolvoval Michael Frank University of Florida. Jeho disertační práce zaměřil se na zpětný výpočet na hardwarové úrovni, ale zahrnoval popis architektury instrukční sady i programovacího jazyka vysoké úrovně (R) pro procesor založený na zpětném výpočtu.[12][poznámky 1]

V roce 1998 Carothers a Perumalla publikovali příspěvek pro workshop Principles of Advanced and Distributed Simulation[13] v rámci postgraduálního studia pod vedením Richarda Fujimota představili techniku ​​reverzního výpočtu jako alternativní mechanismus zpětného posunu v optimisticky synchronizovaných simulacích paralelních diskrétních událostí (Time Warp). V roce 1998 se Carothers stala docentkou na Rensselaer Polytechnic Institute. Ve spolupráci s postgraduálními studenty Davidem Bauerem a Shawnem Pearcem integrovala Carothers design Georgia Tech Time Warp do Rensselaer's Optimistic Simulation System (ROSS), který podporoval pouze zpětný výpočet jako mechanismus vrácení zpět. Carothers také konstruovala RC modely pro BitTorrent ve společnosti General Electric, stejně jako četné síťové protokoly se studenty (BGP4 TCP Tahoe, Multicast ). Carothers vytvořil kurz Parallel and Distributed Simulation, ve kterém byli studenti povinni konstruovat RC modely v ROSS.

Přibližně ve stejné době absolvoval Perumalla Georgia Tech a šel pracovat do Národní laboratoř v Oak Ridge (ORNL). Tam postavil simulátor uSik, což byl kombinovaný optimistický / konzervativní protokol PDES. Systém byl schopen dynamicky určit nejlepší protokol pro LP a přemapovat je během provádění v reakci na dynamiku modelu. V roce 2007 společnost Perumalla testovala uSik na Modrý gen / l a zjistili, že zatímco škálovatelnost je omezena na 8K procesory pro čistou implementaci Time Warp, konzervativní implementace se rozšiřuje na 16K dostupných procesorů. Všimněte si, že benchmarking byl proveden pomocí PHOLD s omezenou vzdáleností událostí 10%, kde bylo časové razítko událostí určeno exponenciálním rozdělením s průměrem 1,0 a k každé události byl přidán další pohled 1,0. Jednalo se o první implementaci PDES na Blue Gene pomocí reverzního výpočtu.

Od roku 1998 do roku 2005 Bauer vykonával postgraduální práce v RPI pod Carothers, se zaměřením pouze na zpětný výpočet. Vyvinul první systém PDES založený výhradně na zpětném výpočtu, který se nazývá Rensselaerův optimistický simulační systém (ROSS).[14] pro kombinované sdílené a distribuovaná paměť systémy. Od roku 2006 do roku 2009 pracoval Bauer pod E.H. Stránka na Mitre Corporation a ve spolupráci s Carothers a Pearce posunuli simulátor ROSS k procesoru 131 072 Blue Gene / P (Neohrožený). Tato implementace byla stabilní pro sazby vzdálených událostí 100% (každá událost odeslaná přes síť). Během svého působení v RPI a MITER vyvinul Bauer síťový simulační systém ROSS.Net[15] který podporuje návrh poloautomatického experimentu pro optimalizaci černé skříňky modelů síťových protokolů prováděných v ROSS. Primárním cílem systému bylo optimalizovat více modelů síťových protokolů pro provádění v ROSS. Například vytvoření struktury vrstvení LP k eliminaci událostí předávaných mezi LP síťového protokolu na stejném simulovaném stroji optimalizuje simulaci síťových uzlů TCP / IP eliminací časových značek s nulovým posunem mezi protokoly TCP a IP. Bauer také konstruoval RC modely založené na agentech sociální kontaktní sítě studovat účinky infekční choroby, zejména pandemická chřipka, která se rozšíří na stovky milionů agentů; stejně jako RC modely pro mobilní ad-hoc sítě implementující funkce mobility (detekce blízkosti) a vysoce přesné fyzické vrstvy elektromagnetická vlna propagace (Maticový model přenosové linky).[16]

Došlo také k nedávnému tlaku komunity PDES do oblasti kontinuální simulace. Například Fujimoto a Perumalla ve spolupráci s Tangem a kol.[17] implementovali RC model částice v buňce a prokázali vynikající zrychlení při kontinuální simulaci pro modely světla jako částice. Bauer a Page předvedli vynikající zrychlení pro model RC Transmission Line Matrix (P.B. Johns, 1971), modelující světlo jako vlnu na mikrovlnných frekvencích. Bauer také vytvořil RC variantu SEIR který generuje enormní zlepšení oproti kontinuálním modelům v oblasti šíření infekčních nemocí. Model RC SEIR je navíc schopen efektivně modelovat více nemocí, zatímco kontinuální model exploduje exponenciálně s ohledem na počet možných kombinací nemocí v celé populaci.

Události

Poznámky

  1. ^ Dr. Frank udržuje dva webové stránky svých publikací na zpětný výpočet do roku 2004 a později.

Reference

  1. ^ Landauer, Rolf (červenec 1961). "Nevratnost a tvorba tepla v procesu výpočtu". IBM Journal of Research and Development. 5 (3): 183–191. CiteSeerX  10.1.1.68.7646. doi:10.1147 / kolo 53.0183.
  2. ^ Von Neumann, John (1966). Teorie samoreprodukčních automatů. University of Illinois Press. str. 388. Citováno 2009-04-06.
  3. ^ Bennett, Charles H. (1982). „Termodynamika výpočtu - recenze“ (PDF). International Journal of Theoretical Physics. 21 (12): 905–940. Bibcode:1982IJTP ... 21..905B. CiteSeerX  10.1.1.655.5610. doi:10.1007 / BF02084158. Citováno 2009-04-06.
  4. ^ Frank, Michael P. (červen 1999). Reverzibilita pro efektivní práci na počítači, Ph.D. Teze (PDF). Massachusetts Institute of Technology, Ústav elektrotechniky a informatiky. Citováno 2009-04-06.
  5. ^ Leeman Jr., George B. (1986). "Formální přístup ke zrušení operací v programovacích jazycích". Transakce ACM v programovacích jazycích a systémech. 8 (1): 50–87. doi:10.1145/5001.5005.
  6. ^ Biswas, Bitan; Mall, R. (1999). Msgstr "Zpětné provedení programů". Oznámení ACM SIGPLAN. 34 (4): 61–69. doi:10.1145/312009.312079.
  7. ^ Griewank, Andreas; Juedes, David; Utke, Jean (1996). "Algoritmus 755: Adolc: balíček pro automatickou diferenciaci algoritmů napsaných v c / c ++". Transakce ACM na matematickém softwaru. 22 (2): 131–167. doi:10.1145/229473.229474.
  8. ^ Grimm, J; Pottier, L .; Rostaing-Schmidt, N. (1996). „Optimální čas a minimální časoprostorový produkt pro obrácení určité třídy programů“ (PDF). Technická zpráva.
  9. ^ Carothers, Christopher D .; Perumalla, Kalyan S .; Fujimoto, Richard M. (1999). „Efektivní optimistické paralelní simulace využívající zpětný výpočet“ (PDF). Transakce ACM na modelování a počítačové simulaci. 9 (3): 224–253. CiteSeerX  10.1.1.113.1702. doi:10.1145/347823.347828. Archivovány od originál (PDF) dne 17.07.2011. Citováno 2009-04-06.
  10. ^ Yaun, Garrett; Carothers, Christopher D .; Kalyanaraman, Shivkumar (2003). Rozsáhlé modely TCP využívající optimistickou paralelní simulaci. Sborník ze sedmnáctého workshopu o paralelní a distribuované simulaci. str. 153–162. CiteSeerX  10.1.1.115.1320. doi:10.1109 / PADS.2003.1207431. ISBN  978-0-7695-1970-8.
  11. ^ Jefferson, David R. (1985). „Virtuální čas“ (PDF). Transakce ACM v programovacích jazycích a systémech. 7 (3): 404–425. doi:10.1145/3916.3988. Citováno 2009-04-06.
  12. ^ Vieri, C .; Ammer, M.J .; Frank, M .; Margolus, N.; Knight, T. (červen 1998). "Plně reverzibilní asymptoticky nulový mikroprocesor" (PDF). Seminář mikroarchitektury poháněný energií: 138–142.
  13. ^ Workshop Principles of Advanced and Distributed Simulation Workshop, nyní ACM SIGSIM Conference on Principles of Advanced Discrete Simulation (PADS)
  14. ^ Carothers, Christopher D .; Bauer, D. W .; Pearce, Shawn O. (2002). „ROSS: vysoce výkonný modulární systém Time Warp s nízkou pamětí“. Journal of Parallel and Distributed Computing. 62 (11): 1648–1669. CiteSeerX  10.1.1.78.3105. doi:10.1016 / S0743-7315 (02) 00004-7.
  15. ^ Bauer, David W .; Yaun, Garrett; Carothers, Christopher D .; Yuksel, Murat; Kalyanaraman, Shivkumar (2003). ROSS.Net: optimistický rámec paralelní simulace pro rozsáhlé internetové modely. Sborník konference o zimní simulaci z roku 2003. 1. 703–711. doi:10.1109 / WSC.2003.1261486. ISBN  978-0-7803-8131-5.
  16. ^ Bauer Jr., David W .; Page, Ernest H. (2007). "Optimistická simulace paralelní diskrétní události metody matice přenosové linky založené na událostech". Sborník 39. konference o zimní simulaci: 40 let! To nejlepší teprve přijde: 676–684. CiteSeerX  10.1.1.132.307.
  17. ^ Tang, Y .; Perumalla, K. S .; Fujimoto, R. M .; Karimabadi, H .; Driscoll, J .; Omelchenko, Y. (2005). Optimistické simulace paralelních diskrétních událostí fyzických systémů pomocí zpětného výpočtu (PDF). Principy pokročilé a distribuované simulace. 26–35. CiteSeerX  10.1.1.110.5893. doi:10.1109 / PADS.2005.16. ISBN  978-0-7695-2383-5. Citováno 2009-04-06.