Funzione legata alla memoria - Memory-bound function

Il limite di memoria si riferisce a una situazione in cui il tempo per completare un dato problema computazionale è deciso principalmente dalla quantità di memoria richiesta per contenere i dati di lavoro . Ciò è in contrasto con gli algoritmi che sono vincolati al calcolo , in cui il numero di passaggi di calcolo elementari è il fattore decisivo.

A volte i limiti di memoria e calcolo possono essere scambiati l'uno contro l'altro, ad esempio salvando e riutilizzando i risultati preliminari o utilizzando tabelle di ricerca .

Funzioni di memoria e funzioni di memoria

Le funzioni di memoria e le funzioni di memoria sono correlate in quanto entrambe implicano un ampio accesso alla memoria, ma esiste una distinzione tra le due.

Le funzioni di memoria utilizzano una tecnica di programmazione dinamica chiamata memoizzazione per alleviare l'inefficienza della ricorsione che potrebbe verificarsi. Si basa sulla semplice idea di calcolare e memorizzare soluzioni ai sottoproblemi in modo che le soluzioni possano essere riutilizzate in seguito senza ricalcolare nuovamente i sottoproblemi . L'esempio più noto che sfrutta la memoizzazione è un algoritmo che calcola i numeri di Fibonacci . Il seguente pseudocodice utilizza la ricorsione e la memoizzazione e viene eseguito in tempo CPU lineare : 

 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
 }

Confronta quanto sopra con un algoritmo che utilizza solo la ricorsione e viene eseguito in tempo CPU esponenziale : 

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

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

Mentre l'algoritmo solo ricorsivo è più semplice ed elegante dell'algoritmo che utilizza la ricorsione e la memoizzazione, quest'ultimo ha una complessità temporale significativamente inferiore rispetto al primo.

Il termine "funzione legata alla memoria" è emerso solo di recente ed è utilizzato principalmente per descrivere una funzione che utilizza XOR e consiste in una serie di calcoli in cui ciascun calcolo dipende dal calcolo precedente. Mentre le funzioni di memoria sono state a lungo un attore importante nel miglioramento della complessità del tempo, le funzioni legate alla memoria hanno visto molte meno applicazioni. Recentemente, tuttavia, gli scienziati hanno proposto un metodo che utilizza le funzioni legate alla memoria come mezzo per scoraggiare gli spammer dall'abuso delle risorse, il che potrebbe essere un importante passo avanti in quell'area.

Utilizzo di funzioni legate alla memoria per prevenire lo spam

Le funzioni legate alla memoria potrebbero essere utili in un sistema di prova del lavoro che potrebbe scoraggiare lo spam , che è diventato un problema di proporzioni epidemiche su Internet .

Nel 1992, i ricercatori di IBM Cynthia Dwork e Moni Naor hanno pubblicato un articolo al CRYPTO 1992 dal titolo Pricing via Processing or Combatting Junk Mail , suggerendo la possibilità di utilizzare funzioni legate alla CPU per scoraggiare gli autori di abusi dall'invio di spam. Lo schema era basato sull'idea che gli utenti di computer hanno molte più probabilità di abusare di una risorsa se il costo dell'abuso della risorsa è trascurabile: il motivo per cui lo spam è diventato così dilagante è che l'invio di un'e-mail ha un costo minuscolo per gli spammer.

Dwork e Naor hanno proposto che lo spamming potrebbe essere ridotto iniettando un costo aggiuntivo sotto forma di un costoso calcolo della CPU : le funzioni legate alla CPU consumerebbero le risorse della CPU sulla macchina del mittente per ogni messaggio, impedendo così l'invio di enormi quantità di spam in un breve periodo.

Lo schema di base che protegge dagli abusi è il seguente:
Sia S il mittente, R il destinatario e M un'e-mail. Se R ha acconsentito in anticipo a ricevere e-mail da S , allora M viene trasmesso nel solito modo. Altrimenti, S calcola una funzione G (M) e invia (M, G (M)) a R . R controlla se ciò che riceve da S è della forma (M, G (M)) . Se sì, R accetta M . Altrimenti, R respinge M . La figura a destra mostra casi in cui non c'erano accordi precedenti .

La funzione G () è selezionata in modo tale che la verifica di R sia relativamente veloce (impiega un millisecondo) e tale che il calcolo di S sia alquanto lento (coinvolge almeno diversi secondi). Pertanto, S sarà scoraggiato dall'inviare M a più destinatari senza accordi preliminari: il costo in termini sia di tempo che di risorse di calcolo di ripetutamente G () diventerà molto proibitivo per uno spammer che intende inviare molti milioni di e-mail .

Il problema principale dell'utilizzo dello schema precedente è che le CPU veloci elaborano molto più velocemente delle CPU lente. Inoltre, i sistemi informatici di fascia alta hanno anche condutture sofisticate e altre caratteristiche vantaggiose che facilitano i calcoli. Di conseguenza, uno spammer con un sistema all'avanguardia difficilmente sarà influenzato da tale deterrenza, mentre un utente tipico con un sistema mediocre sarà influenzato negativamente. Se un calcolo richiede alcuni secondi su un nuovo PC , potrebbe richiedere un minuto su un vecchio PC e diversi minuti su un PDA , il che potrebbe essere un fastidio per gli utenti di vecchi PC, ma probabilmente inaccettabile per gli utenti di PDA. La disparità nella velocità della CPU del client costituisce uno dei principali ostacoli all'adozione diffusa di qualsiasi schema basato su una funzione legata alla CPU. Pertanto, i ricercatori si preoccupano di trovare funzioni che la maggior parte dei sistemi informatici valuterà all'incirca alla stessa velocità, in modo che i sistemi di fascia alta possano valutare queste funzioni un po 'più velocemente dei sistemi di fascia bassa (2-10 volte più velocemente, ma non 10-100 volte più veloce) come potrebbero implicare le disparità della CPU. Questi rapporti sono sufficientemente " egualitari " per le applicazioni previste: le funzioni sono efficaci nello scoraggiare gli abusi e non aggiungono un ritardo proibitivo alle interazioni legittime, attraverso un'ampia gamma di sistemi.

Il nuovo approccio egualitario consiste nel fare affidamento sulle funzioni legate alla memoria. Come affermato in precedenza, una funzione legata alla memoria è una funzione il cui tempo di calcolo è dominato dal tempo impiegato per accedere alla memoria. Una funzione legata alla memoria accede a posizioni in una vasta regione di memoria in modo imprevedibile, in modo tale che l'utilizzo delle cache non sia efficace. Negli ultimi anni, la velocità della CPU è cresciuta drasticamente, ma ci sono stati progressi relativamente piccoli nello sviluppo di una memoria principale più veloce. Poiché il rapporto tra le latenze di memoria delle macchine costruite negli ultimi cinque anni è tipicamente non superiore a due e quasi sempre inferiore a quattro, la funzione legata alla memoria sarà egualitaria per la maggior parte dei sistemi nel prossimo futuro.

Guarda anche

Riferimenti

link esterno