Minnesbunden funktion - Memory-bound function

Minne bunden hänvisar till en situation där tid att slutföra ett givet beräkningsproblem avgörs i första hand av den mängd minne som krävs för att hålla arbets uppgifter . Detta står i kontrast till algoritmer som är datorbundna , där antalet elementära beräkningssteg är den avgörande faktorn.

Minnes- och beräkningsgränser kan ibland handlas mot varandra, t.ex. genom att spara och återanvända preliminära resultat eller använda uppslagstabeller .

Minnesbundna funktioner och minnesfunktioner

Minnesbundna funktioner och minnesfunktioner är relaterade genom att båda involverar omfattande minnesåtkomst, men det finns en åtskillnad mellan de två.

Minnesfunktioner använder en dynamisk programmeringsteknik som kallas memoization för att lindra ineffektiviteten i rekursion som kan uppstå. Den bygger på den enkla idén att beräkna och lagra lösningar till delproblem så att lösningarna kan återanvändas senare utan att omberäkna delproblemen igen. Det mest kända exemplet som utnyttjar memoization är en algoritm som beräknar Fibonacci-siffrorna . Följande pseudokod använder rekursion och memoization och körs i linjär CPU-tid : 

 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
 }

Jämför ovanstående med en algoritm som endast använder rekursion och körs i exponentiell CPU-tid: 

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

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

Medan den enda rekursiva algoritmen är enklare och elegantare än algoritmen som använder rekursion och memoisering, har den senare betydligt lägre tidskomplexitet än den tidigare.

Uttrycket "minnesbunden funktion" har nyligen dykt upp och används huvudsakligen för att beskriva en funktion som använder XOR och består av en serie beräkningar där varje beräkning beror på den tidigare beräkningen. Medan minnesfunktioner länge har varit en viktig aktör för att förbättra tidskomplexiteten har minnesbundna funktioner sett mycket färre applikationer. Nyligen har dock forskare föreslagit en metod som använder minnesbundna funktioner som ett sätt att avskräcka spammare från att missbruka resurser, vilket kan vara ett stort genombrott inom det området.

Använda minnesbundna funktioner för att förhindra skräppost

Minnesbundna funktioner kan vara användbara i ett system för bevis på arbete som kan avskräcka skräppost , vilket har blivit ett problem med epidemiska proportioner på Internet .

1992 publicerade IBMs forskare Cynthia Dwork och Moni Naor en artikel på CRYPTO 1992 med titeln Pricing via Processing or Combatting Junk Mail , vilket föreslog en möjlighet att använda CPU-bundna funktioner för att avskräcka missbrukare från att skicka skräppost. Systemet baserades på tanken att datoranvändare är mycket mer benägna att missbruka en resurs om kostnaden för att missbruka resursen är försumbar: den bakomliggande anledningen till att skräppost har blivit så häftigt är att skicka ett e-postmeddelande har liten kostnad för spammare.

Dwork och Naor föreslog att skräppost skulle kunna minskas genom att tillföra en extra kostnad i form av en dyr CPU- beräkning: CPU-bundna funktioner skulle konsumera CPU-resurser vid avsändarens maskin för varje meddelande, vilket förhindrar att stora mängder skräppost skickas i en kort period.

Grundschemat som skyddar mot missbruk är följande:
Låt S vara avsändare, R vara mottagare och M vara ett e-postmeddelande. Om R i förväg har gått med på att ta emot e-post från S , så sänds M på vanligt sätt. Annars, S beräknar någon funktion G (M) och sänder (M, G (M)) till R . R kontrollerar om vad den får från S har formen (M, G (M)) . Om ja, R accepterar M . Annars, R avvisar M . Siffran till höger visar fall där det inte fanns några tidigare avtal .

Funktionen G () väljs så att verifieringen med R är relativt snabb (tar ett millisekund) och sådan att beräkningen med S är något långsam (involverar minst flera sekunder). Därför kommer S att avskräcka från att skicka M till flera mottagare utan tidigare överenskommelser: kostnaden i termer av både tid och datorresurser för beräkning G () blir upprepade gånger mycket oöverkomlig för en spammare som avser att skicka många miljoner e-postmeddelanden .

Det största problemet med att använda ovanstående schema är att snabba processorer beräknar mycket snabbare än långsamma processorer. Vidare har avancerade datorsystem också sofistikerade rörledningar och andra fördelaktiga funktioner som underlättar beräkningar. Som ett resultat kommer en spammare med ett toppmodernt system knappast att påverkas av sådan avskräckning medan en typisk användare med ett medelmåttigt system kommer att påverkas negativt. Om en beräkning tar några sekunder på en ny dator kan det ta en minut på en gammal dator och flera minuter på en handdator , vilket kan vara en olägenhet för användare av gamla datorer, men förmodligen oacceptabelt för användare av handdatorer. Skillnaden i klientens CPU-hastighet utgör en av de framträdande vägspärrarna för ett brett antagande av något schema baserat på en CPU-bunden funktion. Därför är forskare intresserade av att hitta funktioner som de flesta datorsystem kommer att utvärdera med ungefär samma hastighet, så att avancerade system kan utvärdera dessa funktioner något snabbare än low-end-system (2–10 gånger snabbare, men inte 10–100 gånger snabbare) eftersom CPU-skillnader kan innebära. Dessa förhållanden är tillräckligt " egalitära " för de avsedda applikationerna: funktionerna är effektiva för att avskräcka missbruk och lägger inte till en oöverkomlig fördröjning av legitima interaktioner över ett stort antal system.

Den nya egalitära metoden är att förlita sig på minnesbundna funktioner. Som tidigare nämnts är en minnesbunden funktion en funktion vars beräkningstid domineras av den tid som åtgår åtkomst till minne. En minnesbunden funktion får åtkomst till platser i en stor minnesregion på ett oförutsägbart sätt, så att cacheminnet inte är effektivt. Under de senaste åren har processorns hastighet vuxit drastiskt, men det har gjorts relativt små framsteg när det gäller att utveckla snabbare huvudminne. Eftersom förhållandena mellan minnesfördröjningar för maskiner som byggts under de senaste fem åren vanligtvis inte är större än två och nästan alltid mindre än fyra, kommer den minnesbundna funktionen att vara jämlik för de flesta system under överskådlig framtid.

Se även

Referenser

externa länkar