Minnesbunden funktion

Minnesbundet hänvisar till en situation där tiden för att slutföra ett givet beräkningsproblem i första hand bestäms av mängden ledigt minne som krävs för att lagra arbetsdata . Detta till skillnad från algoritmer som är beräkningsbundna , 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 skillnad mellan de två.

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

  
 
        0  
             

        
 

   
 
          
            
        0
           0
         
           
     
                
         

       Fibonacci  (  n  )  {  for  i  =  till  n  -1  resultat  [  i  ]  =  -1  // -1 betyder odefinierad  retur  Fibonacci_Results  (  resultat  ,  n  );  }  Fibonacci_Results  (  results  ,  n  )  {  if  (  results  [  n  ]  !=  -1  )  // Om det har lösts tidigare,  returnera  resultat  [  n  ]  // slå upp det.  if  (  n  ==  )  val  =  else  if  (  n  ==  1  )  val  =  1  else  val  =  Fibonacci_Results  (  results  ,  n  -2  )  +  Fibonacci_Results  (  results  ,  n  -1  )  results  [  n  ]  =  val  // Spara detta resultat för återanvändning.  returvärde  }  _

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

  
 
        0
          0
        
          

          
  Rekursiv_Fibonacci  (  n  )  {  if  (  n  ==  )  returnera  if  (  n  ==  1  )  returnera  1  retur  Rekursiv_Fibonacci  (  n  -1  )  +  Rekursiv_Fibonacci  (  n  -2  )  }

Medan den endast rekursiva algoritmen är enklare och mer elegant än algoritmen som använder rekursion och memoisering, har den senare en betydligt lägre tidskomplexitet än den förra.

Termen "minnesbunden funktion" har dykt upp först nyligen 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 tillämpningar. Nyligen [ när? ] 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änder minnesbundna funktioner för att förhindra spam

Minnesbundna funktioner kan vara användbara i ett arbetsbevissystem som kan avskräcka skräppost , som har blivit ett problem med epidemiska proportioner på Internet .

År 1992 publicerade IBM-forskarna Cynthia Dwork och Moni Naor en artikel på CRYPTO 1992 med titeln Pricing via Processing or Combatting Junk Mail, som föreslår en möjlighet att använda CPU-bundna funktioner för att avskräcka missbrukare från att skicka skräppost. Systemet baserades på idén att datoranvändare är mycket mer benägna att missbruka en resurs om kostnaden för att missbruka resursen är försumbar: den bakomliggande orsaken till att skräppost har blivit så skenande är att det har en minimal kostnad för spammare att skicka ett e- postmeddelande .

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 förbruka CPU-resurser på avsändarens maskin för varje meddelande, vilket förhindrar att enorma mängder skräppost skickas i en kort period.


Grundschemat som skyddar mot övergrepp är följande: Låt S vara avsändare, R vara mottagare och M vara e-post. Om R i förväg samtyckt till att ta emot e-post från S sänds M på vanligt sätt. Annars S någon funktion G(M) och skickar (M, G(M)) till R . R kontrollerar om det den får från S är av formen (M, G(M)) . Om ja, accepterar R M . I annat fall avvisar R M . Bilden till höger visar fall där det inte fanns några tidigare överenskommelser .

Funktionen G() väljs så att verifieringen av R är relativt snabb (tar en millisekund) och så att beräkningen av S är något långsam (som involverar åtminstone flera sekunder). Därför S att avskräckas från att skicka M till flera mottagare utan föregående avtal: kostnaden i termer av både tid och datorresurser för att beräkna G() upprepade gånger kommer att bli mycket oöverkomlig för en spammare som har för avsikt att skicka många miljoner e-postmeddelanden .

Det stora 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 pipelines 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 mediokert 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 PDA , vilket kan vara till besvär 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 utbredd användning av alla scheman 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) som CPU-skillnader kan antyda. Dessa förhållanden är tillräckligt " jämlika " för de avsedda tillämpningarna: funktionerna är effektiva för att motverka missbruk och lägger inte till en oöverkomlig fördröjning av legitima interaktioner, över ett brett spektrum av system.

Det nya jämlikhetssättet är att förlita sig på minnesbundna funktioner. Som nämnts tidigare är en minnesbunden funktion en funktion vars beräkningstid domineras av den tid som ägnas åt åtkomst till minnet. En minnesbunden funktion får åtkomst till platser i ett stort minnesområde på ett oförutsägbart sätt, på ett sådant sätt att användningen av cachar inte är effektiv. Under de senaste åren har CPU-hastigheten ökat drastiskt, men det har skett jämförelsevis små framsteg när det gäller att utveckla snabbare huvudminne. Eftersom förhållandet mellan minneslatenser 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

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Memory-bound_function&oldid=1121694789 "