Funkce vázaná na paměť - Memory-bound function

Vázaná paměť odkazuje na situaci, ve které je čas na dokončení daného výpočtového problému rozhodován primárně množstvím paměti potřebné k uložení pracovních dat . To je na rozdíl od algoritmů, které jsou vázány na výpočet , kde je rozhodujícím faktorem počet elementárních kroků výpočtu.

Hranice paměti a výpočtu lze někdy obchodovat proti sobě, např. Uložením a opětovným použitím předběžných výsledků nebo pomocí vyhledávacích tabulek .

Funkce vázané na paměť a paměťové funkce

Funkce vázané na paměť a paměťové funkce souvisí tím, že obě zahrnují rozsáhlý přístup do paměti, ale mezi těmito dvěma existuje rozdíl.

Paměťové funkce používají techniku dynamického programování zvanou memoizace , aby zmírnily neefektivitu rekurze , ke které může dojít. Je založen na jednoduché myšlence výpočtu a ukládání řešení dílčích problémů, aby bylo možné řešení později znovu použít, aniž by se dílčí problémy znovu přepočítávaly . Nejznámějším příkladem, který využívá výhod memoizace, je algoritmus, který počítá Fibonacciho čísla . Následující pseudokód používá rekurzi a memoizaci a běží v lineárním čase CPU : 

 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
 }

Porovnejte výše uvedené s algoritmem, který používá pouze rekurzi a běží v exponenciálním čase CPU: 

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

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

Zatímco algoritmus pouze pro rekurzivní zpracování je jednodušší a elegantnější než algoritmus, který používá rekurzi a memoizaci, druhý má výrazně nižší časovou složitost než první.

Termín „funkce vázaná na paměť“ se vynořil pouze nedávno a používá se hlavně k popisu funkce, která používá XOR a sestává z řady výpočtů, ve kterých každý výpočet závisí na předchozím výpočtu. Zatímco paměťové funkce jsou již dlouho důležitým činitelem při zlepšování časové složitosti, funkce vázané na paměť zaznamenaly mnohem méně aplikací. V poslední době však vědci navrhli metodu využívající funkce vázané na paměť jako prostředek k odrazování spammerů od zneužívání zdrojů, což by mohlo být v této oblasti zásadním průlomem.

Použití funkcí vázaných na paměť k zabránění spamu

Funkce vázané na paměť mohou být užitečné v systému kontroly práce, který by mohl odradit spam , který se stal problémem epidemických rozměrů na internetu .

V roce 1992 publikovali výzkumní pracovníci IBM Cynthia Dwork a Moni Naor na CRYPTO 1992 článek s názvem Ceny prostřednictvím zpracování nebo boj proti nevyžádané poště , který naznačuje možnost použití funkcí vázaných na CPU k odradení zneužitelných od odesílání spamu. Schéma bylo založeno na myšlence, že uživatelé počítačů mnohem pravděpodobněji zneužijí zdroj, pokud jsou náklady na jeho zneužití zanedbatelné: hlavním důvodem, proč se spam tak rozšířil, je to, že odesílání e-mailů má pro spamery nepatrné náklady.

Dwork a Naor navrhli, že spam může být snížen vložením dodatečných nákladů v podobě nákladného výpočtu CPU : Funkce vázané na CPU by spotřebovaly prostředky CPU na stroji odesílatele pro každou zprávu, čímž by se zabránilo odeslání velkého množství spamu do krátké období.

Základní schéma, které chrání před zneužitím, je následující:
Nechť S je odesílatel, R je příjemce a M je e-mail. Pokud R předem souhlasil s přijímáním e-mailů od S , pak se M přenáší obvyklým způsobem. V opačném případě, S vypočítá nějakou funkci G (M), a odešle (M, G (F)) na R . R zkontroluje, zda to, co přijímá od S, má tvar (M, G (M)) . Pokud ano, R přijímá M . V opačném případě, R odmítá M . Obrázek vpravo zobrazuje případy, kdy neexistovaly žádné předchozí dohody .

Funkce G () je vybrána tak, že ověření pomocí R je relativně rychlé (trvá milisekundu) a tak, že výpočet pomocí S je poněkud pomalý (zahrnující alespoň několik sekund). Proto bude společnost S odradena od zasílání M více příjemcům bez předchozích dohod: náklady na čas a výpočetní prostředky výpočtu G () se opakovaně stanou velmi nepřístupnými pro spammera, který má v úmyslu posílat mnoho milionů e-mailů .

Hlavním problémem použití výše uvedeného schématu je, že rychlé CPU počítají mnohem rychleji než pomalé CPU. Počítačové systémy vyšší třídy dále mají také sofistikované kanály a další výhodné funkce, které usnadňují výpočty. Výsledkem bude, že spammer s nejmodernějším systémem bude takovým odstrašením těžko ovlivněn, zatímco typický uživatel s průměrným systémem bude nepříznivě ovlivněn. Pokud výpočet na novém počítači trvá několik sekund, na starém počítači to může trvat minutu a na PDA několik minut , což může být pro uživatele starých počítačů nepříjemné, ale pro uživatele PDA pravděpodobně nepřijatelné. Rozdíl v rychlosti klientského CPU představuje jeden z významných překážek širokého přijetí jakéhokoli schématu založeného na funkci vázané na CPU. Vědci se proto zabývají hledáním funkcí, které většina počítačových systémů vyhodnotí přibližně stejnou rychlostí, aby systémy vyšší třídy mohly tyto funkce vyhodnotit o něco rychleji než systémy nižší třídy (2–10krát rychlejší, ale ne 10–100krát rychlejší), jak by mohly naznačovat rozdíly CPU. Tyto poměry jsou pro zamýšlené aplikace dostatečné „ rovnostářské “: funkce jsou účinné při odrazování od zneužití a nepřidávají prohibitivní zpoždění legitimních interakcí napříč širokou škálou systémů.

Novým rovnostářským přístupem je spoléhat se na funkce vázané na paměť. Jak již bylo uvedeno dříve, funkce vázaná na paměť je funkce, jejíž výpočetní době dominuje čas strávený přístupem k paměti. Funkce vázaná na paměť přistupuje nepředvídatelným způsobem k místům ve velké oblasti paměti takovým způsobem, že použití mezipaměti není efektivní. V posledních letech drasticky vzrostla rychlost CPU, ale ve vývoji rychlejší hlavní paměti došlo k poměrně malému pokroku. Vzhledem k tomu, poměry v paměti latencí strojů postavených v posledních pěti letech je obvykle ne více než dva, a téměř vždy menší než čtyři, bude paměť vázaný funkce bude rovnostářský k většině systémů v blízké budoucnosti.

Viz také

Reference

externí odkazy