Funkcja związana z pamięcią - Memory-bound function

Pamięć ograniczona odnosi się do sytuacji, w której o czasie rozwiązania danego problemu obliczeniowego decyduje przede wszystkim ilość pamięci wymaganej do przechowywania danych roboczych . Kontrastuje to z algorytmami związanymi z obliczeniami , w których liczba elementarnych kroków obliczeniowych jest decydującym czynnikiem.

Granice pamięci i obliczeń można czasami wymieniać między sobą, np. Zapisując i ponownie wykorzystując wstępne wyniki lub korzystając z tabel przeglądowych .

Funkcje związane z pamięcią i funkcje pamięci

Funkcje związane z pamięcią i funkcje pamięci są powiązane w tym sensie, że oba obejmują szeroki dostęp do pamięci, ale istnieje różnica między nimi.

Funkcje pamięci wykorzystują technikę programowania dynamicznego zwaną zapamiętywaniem , aby zmniejszyć nieefektywność rekursji, która może wystąpić. Opiera się na prostym pomyśle obliczania i przechowywania rozwiązań dla podproblemów, tak aby można je było później ponownie wykorzystać bez ponownego obliczania podproblemów . Najbardziej znanym przykładem wykorzystującym zapamiętywanie jest algorytm obliczający liczby Fibonacciego . Poniższy pseudokod używa rekurencji i zapamiętywania oraz działa w liniowym czasie procesora : 

 Fibonacci (n)
 {
     for i = 0 to n-1
         results[i] = -1  // -1 means undefined

     return Fibonacci_Results (results, n);
 }

 Fibonacci_Results (results, n)
 {
     if (results[n] != -1)  // If it has been solved before,
         return results[n]  // look it up.
     if (n == 0)
         val = 0
     else if (n == 1)
         val = 1
     else
         val = Fibonacci_Results(results, n-2 ) + Fibonacci_Results(results, n-1)
     results[n] = val  // Save this result for re-use.

     return val
 }

Porównaj powyższe z algorytmem, który używa tylko rekurencji i działa w wykładniczym czasie procesora: 

 Recursive_Fibonacci (n)
 {
     if (n == 0)
         return 0
     if (n == 1)
         return 1

     return Recursive_Fibonacci (n-1) + Recursive_Fibonacci (n-2)
 }

Chociaż algorytm rekurencyjny jest prostszy i bardziej elegancki niż algorytm wykorzystujący rekursję i zapamiętywanie, ten drugi ma znacznie mniejszą złożoność czasową niż poprzedni.

Termin „funkcja związana z pamięcią” pojawił się dopiero niedawno i jest używany głównie do opisu funkcji, która używa XOR i składa się z serii obliczeń, w których każde obliczenie zależy od poprzedniego obliczenia. Podczas gdy funkcje pamięci od dawna odgrywają ważną rolę w poprawianiu złożoności czasowej, funkcje związane z pamięcią miały znacznie mniej zastosowań. Jednak ostatnio naukowcy zaproponowali metodę wykorzystującą funkcje związane z pamięcią, aby zniechęcić spamerów do nadużywania zasobów, co może być głównym przełomem w tej dziedzinie.

Używanie funkcji związanych z pamięcią w celu zapobiegania spamowi

Funkcje związane z pamięcią mogą być przydatne w systemie proof-of-work, który może powstrzymać spam , który stał się problemem rozmiarów epidemii w Internecie .

W 1992 roku naukowcy IBM Cynthia Dwork i Moni Naor opublikowali na CRYPTO 1992 artykuł zatytułowany Pricing via Processing or Combatting Junk Mail , sugerujący możliwość wykorzystania funkcji związanych z procesorem w celu powstrzymania nadużyć przed wysyłaniem spamu. Schemat opierał się na założeniu, że użytkownicy komputerów są znacznie bardziej skłonni do nadużywania zasobu, jeśli koszt nadużycia zasobu jest znikomy: przyczyną, dla której spam stał się tak rozpowszechniony, jest to, że wysyłanie wiadomości e-mail kosztuje spamerzy znikome .

Dwork i Naor zaproponował, że spam może być zmniejszona przez wtrysk dodatkowy koszt w postaci drogiego procesora obliczeń: funkcje CPU-bound by konsumować zasobów procesora w urządzeniu nadawcy dla każdej wiadomości, zapobiegając w ten sposób ogromne ilości spamu wysyłanego w A krótki okres.

Podstawowy schemat zabezpieczający przed nadużyciami jest następujący:
Niech S będzie nadawcą, R będzie odbiorcą, a M będzie e-mailem. Jeśli R zgodził się wcześniej na otrzymywanie wiadomości e-mail od S , wówczas M jest przesyłany w zwykły sposób. W przeciwnym razie, S oblicza niektórych funkcji G (M), i wysyła (M G (M)) w celu badania . R sprawdza, czy to, co otrzymuje od S, ma postać (M, G (M)) . Jeśli tak, R przyjmuje M . W przeciwnym razie, R odrzuca M . Rysunek po prawej stronie przedstawia przypadki, w których nie było wcześniejszych uzgodnień .

Funkcja G () jest wybrana w taki sposób, że weryfikacja przez R jest stosunkowo szybka (zajmuje milisekundę) i taka, że ​​obliczenie przez S jest nieco powolne (zajmuje co najmniej kilka sekund). W związku z tym S będzie zniechęcany do wysyłania M do wielu odbiorców bez wcześniejszych uzgodnień: koszt zarówno czasu, jak i zasobów obliczeniowych G () wielokrotnie stanie się bardzo przeszkodą dla spamera, który zamierza wysłać wiele milionów wiadomości e-mail .

Głównym problemem związanym z używaniem powyższego schematu jest to, że szybkie procesory obliczają znacznie szybciej niż wolne procesory. Ponadto systemy komputerowe wyższej klasy mają również wyrafinowane potoki i inne korzystne cechy, które ułatwiają obliczenia. W rezultacie spamer posiadający najnowocześniejszy system nie zostanie dotknięty takim odstraszaniem, podczas gdy typowy użytkownik posiadający przeciętny system będzie miał negatywny wpływ. Jeśli obliczenia trwają kilka sekund na nowym komputerze , może to zająć minutę na starym komputerze i kilka minut na PDA , co może być uciążliwe dla użytkowników starych komputerów, ale prawdopodobnie nie do zaakceptowania dla użytkowników urządzeń PDA. Rozbieżność w szybkości procesora klienta stanowi jedną z głównych przeszkód dla powszechnego przyjęcia dowolnego schematu opartego na funkcji związanej z procesorem. Dlatego naukowcy są zainteresowani znalezieniem funkcji, które większość systemów komputerowych będzie oceniać z mniej więcej taką samą szybkością, tak aby systemy high-end mogły oceniać te funkcje nieco szybciej niż systemy low-end (2–10 razy szybciej, ale nie 10–100 razy szybciej), jak mogą sugerować różnice w procesorze. Te współczynniki są wystarczająco „ egalitarne ” dla zamierzonych zastosowań: funkcje skutecznie zniechęcają do nadużyć i nie powodują zaporowego opóźnienia legalnych interakcji w wielu różnych systemach.

Nowe podejście egalitarne polega na wykorzystaniu funkcji związanych z pamięcią. Jak wspomniano wcześniej, funkcja związana z pamięcią to funkcja, której czas obliczania jest zdominowany przez czas spędzony na dostępie do pamięci. Funkcja związana z pamięcią uzyskuje dostęp do lokalizacji w dużym obszarze pamięci w nieprzewidywalny sposób, w taki sposób, że używanie pamięci podręcznych nie jest efektywne. W ostatnich latach szybkość procesora wzrosła drastycznie, ale nastąpił stosunkowo niewielki postęp w tworzeniu szybszej pamięci głównej. Ponieważ stosunki z opóźnieniami pamięci maszyn zbudowanych w ciągu ostatnich pięciu lat, jest zazwyczaj nie większa niż dwa, a prawie zawsze mniej niż czterech, funkcja pamięci związana będzie egalitarny do większości systemów dającej się przewidzieć przyszłości.

Zobacz też

Bibliografia

Linki zewnętrzne