Minne-bundet funksjon - Memory-bound function

Minne bundet refererer til en situasjon der tid til å fullføre en gitt beregnings problem avgjøres først og fremst av hvor mye minne som kreves for å holde arbeids data . Dette er i motsetning til algoritmer som er databundne , hvor antall elementære beregningstrinn er den avgjørende faktoren.

Minne- og beregningsgrenser kan noen ganger byttes mot hverandre, for eksempel ved å lagre og gjenbruke foreløpige resultater eller bruke oppslagstabeller .

Minne-bundet funksjoner og minne funksjoner

Minne-bundet funksjoner og minnefunksjoner er relatert i at begge involverer omfattende minnetilgang, men det er et skille mellom de to.

Minnefunksjoner bruker en dynamisk programmeringsteknikk kalt memoization for å avlaste ineffektiviteten til rekursjon som kan oppstå. Det er basert på den enkle ideen om å beregne og lagre løsninger til delproblemer slik at løsningene kan brukes på nytt senere uten å beregne delproblemene på nytt. Det mest kjente eksemplet som utnytter memoization er en algoritme som beregner Fibonacci-tallene . Følgende pseudokode bruker rekursjon og memoization, og kjø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 det ovennevnte med en algoritme som bare bruker rekursjon og kjører i eksponensiell 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 bare rekursive algoritmen er enklere og mer elegant enn algoritmen som bruker rekursjon og memoisering, har sistnevnte en betydelig lavere tidskompleksitet enn den tidligere.

Begrepet "minnebundet funksjon" har dukket opp nylig og brukes hovedsakelig for å beskrive en funksjon som bruker XOR og består av en serie beregninger der hver beregning avhenger av forrige beregning. Mens minnefunksjoner lenge har vært en viktig aktør for å forbedre tidskompleksiteten, har minnebundne funksjoner sett langt færre applikasjoner. Nylig har forskere imidlertid foreslått en metode som bruker minnebundne funksjoner som et middel til å motvirke spammere fra å misbruke ressurser, noe som kan være et stort gjennombrudd i det området.

Bruke hukommelsesbundne funksjoner for å forhindre spam

Hukommelsesbundne funksjoner kan være nyttige i et proof-of-work-system som kan avskrekke spam , noe som har blitt et problem med epidemiske proporsjoner på Internett .

I 1992 publiserte IBMs forskere Cynthia Dwork og Moni Naor et papir på CRYPTO 1992 med tittelen Pricing via Processing or Combatting Junk Mail , og antydet en mulighet for å bruke CPU-bundne funksjoner for å avskrekke misbrukere fra å sende spam. Ordningen var basert på ideen om at databrukere er mye mer sannsynlig å misbruke en ressurs hvis kostnadene ved å misbruke ressursen er ubetydelige: den underliggende årsaken til at spam har blitt så voldsomt er at det å sende e-post har liten kostnad for spammere.

Dwork og Naor foreslo at spamming kan reduseres ved å injisere en ekstra kostnad i form av en kostbar CPU- beregning: CPU-bundne funksjoner vil forbruke CPU-ressurser på avsenderens maskin for hver melding, og dermed forhindre at enorme mengder spam blir sendt i en kort periode.

Den grunnleggende ordningen som beskytter mot overgrep er som følger:
La S være avsender, R være mottaker og M være en e-post. Hvis R på forhånd har avtalt å motta e-post fra S , blir M overført på vanlig måte. Ellers S beregner en funksjon G (M) og sender (M, G (M)) til R . R sjekker om det den mottar fra S er av skjemaet (M, G (M)) . Hvis ja, R aksepterer M . Ellers R avviser M . Figuren til høyre viser saker der det ikke var noen tidligere avtaler .

Funksjonen G () er valgt slik at verifiseringen med R er relativt rask (tar et millisekund) og slik at beregningen av S er noe treg (involverer minst flere sekunder). Derfor vil S frarådes å sende M til flere mottakere uten tidligere avtaler: kostnaden når det gjelder både tid og databehandlingsressurser for databehandling G () vil gjentatte ganger være svært uoverkommelig for en spammer som har til hensikt å sende mange millioner e-poster .

Det største problemet med å bruke ovennevnte ordning er at raske CPUer beregner mye raskere enn sakte CPUer. Videre har avanserte datasystemer også sofistikerte rørledninger og andre fordelaktige funksjoner som letter beregninger. Som et resultat vil en spammer med et moderne system neppe bli påvirket av slik avskrekkelse, mens en typisk bruker med et middelmådig system vil bli negativt påvirket. Hvis en beregning tar noen sekunder på en ny PC , kan det ta et minutt på en gammel PC, og flere minutter på en PDA , noe som kan være til sjenanse for brukere av gamle PC-er, men sannsynligvis uakseptabelt for brukere av PDA-er. Ulikheten i klientens CPU-hastighet utgjør en av de fremtredende veisperringene for utbredt bruk av en hvilken som helst ordning basert på en CPU-bundet funksjon. Derfor er forskere opptatt av å finne funksjoner som de fleste datasystemer vil evaluere med omtrent samme hastighet, slik at avanserte systemer kan evaluere disse funksjonene noe raskere enn low-end-systemer (2–10 ganger raskere, men ikke 10–100 ganger raskere) som CPU-avvik kan antyde. Disse forholdene er " egalitære " nok for de tiltenkte applikasjonene: funksjonene er effektive for å motvirke misbruk og legger ikke til en uoverkommelig forsinkelse på legitime interaksjoner, over et bredt spekter av systemer.

Den nye egalitære tilnærmingen er å stole på hukommelsesbundne funksjoner. Som nevnt tidligere er en minnebundet funksjon en funksjon hvis beregningstid domineres av tiden brukt på å få tilgang til minne. En minnebundet funksjon får tilgang til steder i et stort område av minnet på en uforutsigbar måte, på en slik måte at bruk av hurtigbuffere ikke er effektiv. De siste årene har hastigheten på CPU vokst drastisk, men det har vært relativt liten fremgang i å utvikle raskere hovedminne. Siden forholdet mellom minnetiden på maskiner som er bygget de siste fem årene vanligvis ikke er større enn to, og nesten alltid mindre enn fire, vil den minnebundne funksjonen være likeverdig for de fleste systemer i overskuelig fremtid.

Se også

Referanser

Eksterne linker