Obliczenia odwrotne
Obliczenia odwrotne to programowe zastosowanie koncepcji obliczeń odwracalnych .
Ponieważ oferuje możliwe rozwiązanie problemu ciepła, z którym borykają się producenci chipów, obliczenia odwracalne zostały szeroko zbadane w dziedzinie architektury komputerów. Obietnica obliczeń odwracalnych polega na tym, że ilość strat ciepła dla odwracalnych architektur byłaby minimalna dla znacznie dużej liczby tranzystorów. Zamiast tworzyć entropię (a tym samym ciepło) poprzez destrukcyjne operacje, odwracalna architektura oszczędza energię, wykonując inne operacje, które zachowują stan systemu.
Koncepcja obliczeń odwrotnych jest nieco prostsza niż obliczenia odwracalne, ponieważ obliczenia odwrotne są wymagane tylko do przywrócenia równoważnego stanu aplikacji, a nie do obsługi odwracalności zestawu wszystkich możliwych instrukcji. Odwracalne koncepcje obliczeniowe zostały z powodzeniem zastosowane jako obliczenia odwrotne w obszarach zastosowań oprogramowania, takich jak projektowanie baz danych, punkty kontrolne i debugowanie oraz różnicowanie kodu.
Obliczenia odwrotne dla równoległej symulacji zdarzeń dyskretnych
Opierając się na pomyślnym zastosowaniu koncepcji obliczeń odwrotnych w innych domenach oprogramowania, Chris Carothers, Kalyan Perumalla i Richard Fujimoto sugerują zastosowanie obliczeń odwrotnych w celu zmniejszenia kosztów ogólnych związanych z oszczędzaniem stanu w równoległej symulacji zdarzeń dyskretnych (PDES). Definiują podejście oparte na odwrotnych kodach zdarzeń (które mogą być generowane automatycznie) i demonstrują zalety tego podejścia w zakresie wydajności w porównaniu z tradycyjnym zapisywaniem stanu dla aplikacji drobnoziarnistych (tych z niewielką ilością obliczeń na zdarzenie). Kluczową właściwością wykorzystywaną przez obliczenia odwrotne jest to, że większość operacji modyfikujących zmienne stanu ma charakter „konstruktywny”. To jest cofnięcie operacji dla takich operacji nie wymaga historii. Do cofnięcia operacji wymagane są tylko najbardziej aktualne wartości zmiennych. Na przykład operatory takie jak ++, ––, +=, -=, *= i /= należą do tej kategorii. Należy zauważyć, że operatory *= i /= wymagają specjalnego traktowania w przypadku mnożenia lub dzielenia przez zero oraz warunków przepełnienia / niedomiaru. Bardziej złożone operacje, takie jak przesunięcie kołowe (szczególnym przypadkiem jest zamiana) i niektóre klasy generowania liczb losowych, również należą do tej kategorii.
Operacje postaci a = b, obliczenia modulo i bitowe , które powodują utratę danych, są określane jako destrukcyjne. Zazwyczaj te operacje można przywrócić tylko przy użyciu konwencjonalnych technik oszczędzania stanu. Zauważamy jednak, że wiele z tych destrukcyjnych operacji jest konsekwencją nadejścia danych zawartych w przetwarzanym zdarzeniu. Na przykład w pracy Yauna, Carothersa i in., z TCP na dużą skalę , czas ostatniego wysłania rejestruje znacznik czasu ostatniego pakietu przekazanego w procesie logicznym routera. Operacja zamiany powoduje, że operacja ta jest odwracalna.
Historia obliczeń odwrotnych w zastosowaniu do symulacji równoległych zdarzeń dyskretnych
W 1985 roku Jefferson wprowadził optymistyczny protokół synchronizacji, który był wykorzystywany w równoległych symulacjach zdarzeń dyskretnych, znany jako Time Warp. Do tej pory technika znana jako obliczenia odwrotne była stosowana tylko w oprogramowaniu do optymistycznie zsynchronizowanej, równoległej symulacji zdarzeń dyskretnych.
W grudniu 1999 roku Michael Frank ukończył University of Florida . Jego praca doktorska koncentrowała się na obliczeniach odwrotnych na poziomie sprzętowym, ale zawierała opisy zarówno architektury zestawu instrukcji, jak i języka programowania wysokiego poziomu (R) dla procesora opartego na obliczeniach odwrotnych.
W 1998 roku Carothers i Perumalla opublikowali artykuł na warsztaty Principles of Advanced and Distributed Simulation w ramach swoich studiów podyplomowych pod kierunkiem Richarda Fujimoto, przedstawiając technikę Reverse Computation jako alternatywny mechanizm wycofywania w optymistycznie zsynchronizowanych równoległych symulacjach zdarzeń dyskretnych (Time Warp). W 1998 Carothers został profesorem nadzwyczajnym w Rensselaer Polytechnic Institute . Współpracując ze studentami Davidem Bauerem i Shawnem Pearce'em, Carothers zintegrował projekt Georgia Tech Time Warp z Optimistic Simulation System (ROSS) firmy Rensselaer, który jako mechanizm wycofywania obsługiwał tylko obliczenia odwrotne. Carothers skonstruował również modele RC dla BitTorrent w General Electric, a także liczne protokoły sieciowe ze studentami ( BGP4 , TCP Tahoe, Multicast ). Carothers stworzył kurs dotyczący symulacji równoległych i rozproszonych, w ramach którego studenci musieli konstruować modele RC w systemie ROSS.
Mniej więcej w tym samym czasie Perumalla ukończył Georgia Tech i rozpoczął pracę w Oak Ridge National Laboratory (ORNL). Tam zbudował symulator uSik, będący połączeniem optymistycznego/konserwatywnego protokołu PDES. System był w stanie dynamicznie określać najlepszy protokół dla płyt LP i mapować je ponownie podczas wykonywania w odpowiedzi na dynamikę modelu. W 2007 roku Perumalla przetestowała uSik na Blue Gene/L i odkryli, że podczas gdy skalowalność jest ograniczona do procesorów 8K dla samej implementacji Time Warp, konserwatywna implementacja skaluje się do dostępnych procesorów 16K. Należy zauważyć, że testy porównawcze zostały przeprowadzone przy użyciu metody PHOLD z ograniczoną częstością zdarzeń zdalnych wynoszącą 10%, gdzie znaczniki czasowe zdarzeń określono na podstawie rozkładu wykładniczego ze średnią 1,0, a do każdego zdarzenia dodano dodatkowe wyprzedzanie w wysokości 1,0. Była to pierwsza implementacja PDES na Blue Gene przy użyciu obliczeń odwrotnych.
W latach 1998-2005 Bauer pracował podyplomowo w RPI pod kierownictwem Carothersa, skupiając się wyłącznie na obliczeniach odwrotnych. Opracował pierwszy system PDES oparty wyłącznie na obliczeniach odwrotnych, nazwany Optimistic Simulation System (ROSS) Rensselaera. dla połączonych współdzielonej i rozproszonej . Od 2006 do 2009 roku Bauer pracował pod kierunkiem EH Page w Mitre Corporation i we współpracy z Carothersem i Pearce'em przeniósł symulator ROSS na 131 072 procesor Blue Gene/P (Nieustraszony). Ta implementacja była stabilna dla współczynnika zdalnych zdarzeń wynoszącego 100% (każde zdarzenie wysłane przez sieć). Podczas pracy w RPI i MITRE Bauer opracował system symulacji sieci ROSS.Net, który obsługuje półautomatyczne projektowanie eksperymentów w celu optymalizacji czarnych skrzynek modeli protokołów sieciowych wykonywanych w ROSS. Głównym celem systemu była optymalizacja wielu modeli protokołów sieciowych do wykonania w ROSS. Na przykład utworzenie struktury warstwowej LP w celu wyeliminowania zdarzeń przekazywanych między protokołami sieciowymi LP na tej samej symulowanej maszynie optymalizuje symulację węzłów sieci TCP/IP poprzez wyeliminowanie znaczników czasu o zerowym przesunięciu między protokołami TCP i IP. Bauer skonstruował również modele oparte na agentach RC dla sieci kontaktów społecznościowych w celu zbadania skutków choroby zakaźne , w szczególności grypa pandemiczna, obejmująca setki milionów czynników; a także modele RC dla mobilnych sieci ad-hoc realizujące funkcjonalność mobilności (wykrywanie bliskości) i wysoce dokładną propagację fal elektromagnetycznych w warstwie fizycznej (model Transmission Line Matrix).
Niedawno społeczność PDES posunęła się również w kierunku symulacji ciągłej. Na przykład Fujimoto i Perumalla, współpracując z Tang i in. wdrożyli model RC cząstki w komórce i zademonstrowali doskonałe przyspieszenie w porównaniu z symulacją ciągłą dla modeli światła jako cząstki. Bauer i Page zademonstrowali doskonałe przyspieszenie modelu RC Transmission Line Matrix (PB Johns, 1971), modelując światło jako falę o częstotliwościach mikrofalowych. Bauer stworzył również wariant RC SEIR który generuje ogromną poprawę w stosunku do modeli ciągłych w obszarze rozprzestrzeniania się chorób zakaźnych. Ponadto model RC SEIR jest w stanie skutecznie modelować wiele chorób, podczas gdy model ciągły eksploduje wykładniczo w odniesieniu do liczby możliwych kombinacji chorób w całej populacji.
Wydarzenia
Notatki
- ^ Dr Frank prowadzi dwie strony internetowe z jego publikacjami na temat obliczeń odwrotnych do 2004 r. i później .