Hukommelsesbundet funktion - Memory-bound function

Hukommelse bundet henviser til en situation, hvor tid til at fuldføre en given beregningsproblem primært bestemt af mængden af hukommelse kræves for at holde de arbejdende data . Dette er i modsætning til algoritmer, der er beregningsbundne , hvor antallet af elementære beregningstrin er den afgørende faktor.

Hukommelses- og beregningsgrænser kan undertiden handles mod hinanden, f.eks. Ved at gemme og genbruge foreløbige resultater eller bruge opslagstabeller .

Hukommelsesbundne funktioner og hukommelsesfunktioner

Hukommelsesbundne funktioner og hukommelsesfunktioner er relateret, idet begge involverer omfattende hukommelsesadgang, men der er en sondring mellem de to.

Hukommelsesfunktioner bruger en dynamisk programmeringsteknik kaldet memoization for at lindre ineffektiviteten af rekursion, der måtte opstå. Det er baseret på den enkle idé at beregne og lagre løsninger til underproblemer, så løsningerne kan genbruges senere uden at genberegne delproblemerne igen. Det bedst kendte eksempel, der udnytter memoization, er en algoritme, der beregner Fibonacci-numrene . Følgende pseudokode bruger rekursion og memoization og kører i lineæ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
 }

Sammenlign ovenstående med en algoritme, der kun bruger rekursion og kører i eksponentiel CPU-tid: 

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

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

Mens den kun rekursive algoritme er enklere og mere elegant end algoritmen, der bruger rekursion og memoization, har sidstnævnte en betydeligt lavere tidskompleksitet end den tidligere.

Udtrykket "hukommelsesbundet funktion" er først dukket op for nylig og anvendes hovedsageligt til at beskrive en funktion, der bruger XOR og består af en række beregninger, hvor hver beregning afhænger af den tidligere beregning. Mens hukommelsesfunktioner længe har været en vigtig aktør i forbedring af tidskompleksitet, har hukommelsesbundne funktioner set langt færre applikationer. For nylig har forskere imidlertid foreslået en metode, der bruger hukommelsesbundne funktioner som et middel til at afholde spammere fra at misbruge ressourcer, hvilket kan være et stort gennembrud i dette område.

Brug af hukommelsesbundne funktioner til at forhindre spam

Hukommelsesbundne funktioner kan være nyttige i et proof-of-work-system, der kan afskrække spam , hvilket er blevet et problem med epidemiske proportioner på Internettet .

I 1992 offentliggjorde IBM-forskere Cynthia Dwork og Moni Naor et papir på CRYPTO 1992 med titlen Pricing via Processing or Combatting Junk Mail , hvilket antydede en mulighed for at bruge CPU-bundne funktioner til at afskrække misbrugere fra at sende spam. Ordningen var baseret på ideen om, at computerbrugere er meget mere tilbøjelige til at misbruge en ressource, hvis omkostningerne ved at misbruge ressourcen er ubetydelige: den bagvedliggende årsag til, at spam er blevet så voldsom, er at afsendelse af en e-mail har ringe omkostninger for spammere.

Dwork og Naor foreslog, at spamming muligvis reduceres ved at indføre en ekstra omkostning i form af en dyr CPU- beregning: CPU-bundne funktioner vil forbruge CPU-ressourcer på afsenderens maskine for hver besked, hvilket forhindrer enorme mængder spam i at blive sendt i en kort periode.

Den grundlæggende ordning, der beskytter mod misbrug, er som følger:
Lad S være afsender, R være modtager, og M være en e-mail. Hvis R på forhånd har aftalt at modtage e-mail fra S , sendes M på den sædvanlige måde. Ellers S beregner en funktion G (M) og sender (M, G (M)) til R . R kontrollerer, om det modtager fra S er af formen (M, G (M)) . Hvis ja, R accepterer M . Ellers R afviser M . Figuren til højre viser tilfælde, hvor der ikke var nogen tidligere aftaler .

Funktionen G () er valgt således, at verifikationen ved R er relativt hurtig (tager et millisekund) og sådan, at beregningen ved hjælp af S er noget langsom (involverer mindst flere sekunder). Derfor vil S afskrækkes fra at sende M til flere modtagere uden forudgående aftaler: omkostningerne i form af både tid og computerressourcer ved computing G () bliver gentagne gange meget uoverkommelige for en spammer, der har til hensigt at sende mange millioner e-mails .

Det største problem ved at bruge ovenstående ordning er, at hurtige CPU'er beregner meget hurtigere end langsomme CPU'er. Yderligere har avancerede computersystemer også sofistikerede rørledninger og andre fordelagtige funktioner, der letter beregninger. Som et resultat vil en spammer med et avanceret system næppe blive påvirket af en sådan afskrækkelse, mens en typisk bruger med et middelmådigt system vil blive negativt påvirket. Hvis en beregning tager et par sekunder på en ny pc , kan det tage et minut på en gammel pc og flere minutter på en PDA , hvilket kan være en gener for brugere af gamle pc'er, men sandsynligvis uacceptabelt for brugere af PDA'er. Forskellen i klientens CPU-hastighed udgør en af ​​de fremtrædende vejspærringer for udbredt anvendelse af ethvert skema baseret på en CPU-bundet funktion. Derfor er forskere optaget af at finde funktioner, som de fleste computersystemer vil evaluere med omtrent samme hastighed, så avancerede systemer muligvis evaluerer disse funktioner noget hurtigere end low-end-systemer (2–10 gange hurtigere, men ikke 10–100 gange hurtigere) som CPU-forskelle måske antyder. Disse forhold er " egalitære " nok til de tilsigtede applikationer: funktionerne er effektive til at modvirke misbrug og tilføjer ikke en uoverkommelig forsinkelse på legitime interaktioner på tværs af en bred vifte af systemer.

Den nye egalitære tilgang er at stole på hukommelsesbundne funktioner. Som tidligere nævnt er en hukommelsesbundet funktion en funktion, hvis beregningstid er domineret af den brugte tid på at få adgang til hukommelse. En hukommelsesbundet funktion får adgang til placeringer i et stort område af hukommelsen på en uforudsigelig måde på en sådan måde, at brug af caches ikke er effektiv. I de senere år er CPU-hastigheden vokset drastisk, men der har været forholdsvis små fremskridt med at udvikle hurtigere hovedhukommelse. Da forholdet mellem hukommelsestiden på maskiner, der er bygget i de sidste fem år, typisk ikke er større end to og næsten altid mindre end fire, vil den hukommelsesbundne funktion være ligestillet med de fleste systemer i overskuelig fremtid.

Se også

Referencer

eksterne links