Memóriához kötött funkció - Memory-bound function

Memory kötött olyan helyzetre utal, amelyben az idő, hogy töltsenek ki egy adott számítási probléma dől elsősorban az összeg memória szükséges, hogy tartsa a dolgozó adatait . Ez ellentétes a számításhoz kötött algoritmusokkal , ahol az elemi számítási lépések száma a döntő tényező.

A memória és a számítási határok néha cserélhetők egymással, például az előzetes eredmények mentésével és újrafelhasználásával vagy keresési táblázatokkal .

Memóriához kötött funkciók és memóriafunkciók

A memóriához kötött funkciók és a memóriafunkciók annyiban kapcsolódnak egymáshoz, hogy mindkettő kiterjedt memória-hozzáféréssel jár, de különbség van a kettő között.

A memóriafunkciók az emlékeztetésnek nevezett dinamikus programozási technikát használják fel a felmerülő rekurzió hatékonyságának enyhítésére . Azon az egyszerű elképzelésen alapszik, hogy az alproblémákra vonatkozó megoldásokat kiszámolják és tárolják, hogy a megoldásokat később újra felhasználhassák anélkül, hogy újra számolnák az alproblémákat . A legismertebb példa, amely kihasználja a memoizációt, egy algoritmus, amely kiszámítja a Fibonacci-számokat . Az alábbi pszeudokód használ rekurzió memoization, fut, és a lineáris CPU idő : 

 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
 }

Hasonlítsa össze a fentieket egy algoritmussal, amely csak rekurziót használ, és exponenciális CPU-idő alatt fut : 

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

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

Míg a csak rekurzív algoritmus egyszerűbb és elegánsabb, mint a rekurziót és memoizációt alkalmazó algoritmus, az utóbbi időbeli bonyolultsága lényegesen alacsonyabb, mint az előbbinél.

A "memóriához kötött funkció" kifejezés csak a közelmúltban jelent meg, és elsősorban egy olyan funkció leírására használatos, amely XOR-t használ, és egy számítási sorozatból áll, amelyben minden egyes számítás az előző számítástól függ. Míg a memóriafunkciók régóta fontos szerepet játszanak az idő bonyolultságának javításában, a memóriához kötött funkciók sokkal kevesebb alkalmazást láttak. A közelmúltban azonban a tudósok javaslatot tettek egy módszerre, amely memóriához kötött funkciókat használ fel annak megakadályozására, hogy a spammerek visszaéljenek az erőforrásokkal, ami komoly áttörést jelenthet ezen a területen.

A memóriához kötött funkciók használata a spam megakadályozására

A memóriához kötött funkciók hasznosak lehetnek egy olyan munkabiztonsági rendszerben , amely elriasztja a spamet , amely az internet járványos méretének problémájává vált .

Cynthia Dwork és Moni Naor , az IBM kutatói 1992-ben publikáltak egy cikket a CRYPTO 1992- en Pricing via Processing or Combating Junk Mail címmel , amely CPU-hoz kötött funkciók használatának lehetőségét javasolja a visszaélők visszatartására a spam küldésétől. A rendszer azon az elgondoláson alapult, hogy a számítógép-használók sokkal nagyobb valószínűséggel élnek vissza erőforrásokkal, ha az erőforrás visszaélésének költségei elhanyagolhatók: a spam alapjául szolgáló ok annyira elburjánzott, hogy az e-mail küldésével a spammerek csekély költségekkel járnak.

Dwork és Naor azt javasolta, hogy a spamelés csökkenthető legyen egy további költség befecskendezésével egy drága CPU- számítás formájában: A CPU-hoz kötött funkciók minden üzenethez CPU-erőforrásokat emésztenek fel a küldő gépén, ezáltal megakadályozva a hatalmas mennyiségű spam küldését egy üzenetben. rövid periódus.

A visszaélések ellen védett alapvető séma a következő:
Legyen S feladó, R címzett és M e-mail. Ha R előzetesen beleegyezett e-mail fogadásába S-től , akkor M- t a szokásos módon továbbítják. Ellenkező esetben, S kiszámít egy függvény G (M) , és elküldi (M, G (M)) , hogy R . R ellenőrzi, hogy az S- től kapott formájú-e (M, G (M)) . Ha igen, R elfogadja M-et . Egyébként R elutasítja M-t . A jobb oldali ábra azokat az eseteket ábrázolja, amelyekben nem volt előzetes megállapodás .

A G () függvényt úgy választjuk meg, hogy az R általi ellenőrzés viszonylag gyors (milliszekundumot vesz igénybe), és hogy az S által történő számítás kissé lassú (legalább néhány másodpercig tart). Ezért S nem lesz hajlandó elküldeni M- et több címzettnek előzetes megállapodás nélkül: a G () többszöri kiszámításának időbeli és számítási erőforrásai költségei nagyon megfizethetetlenek lesznek egy spamelő számára, aki sok millió e-mailt kíván küldeni. .

A fenti séma használatának legfőbb problémája, hogy a gyors CPU-k sokkal gyorsabban számolnak, mint a lassú CPU-k. Továbbá, a felsőbb kategóriájú számítógépes rendszerek kifinomult csővezetékekkel és más előnyös tulajdonságokkal is rendelkeznek, amelyek megkönnyítik a számítást. Ennek eredményeként a korszerű rendszerrel rendelkező spammereket aligha érinti ez az elrettentés, míg egy átlagos, közepes rendszerű felhasználót hátrányosan érint. Ha a számítás új számítógépen néhány másodpercet vesz igénybe , egy régi számítógépen egy percig, PDA- n pedig több percig is eltarthat , ami a régi PC-k felhasználói számára kellemetlenséget okozhat, de a PDA-k felhasználói számára valószínűleg elfogadhatatlan. A kliens CPU sebességének különbségei az egyik legfontosabb akadályt jelentenek a CPU-hoz kötött függvényen alapuló sémák széleskörű elfogadásában. Ezért a kutatók olyan funkciók keresésével foglalkoznak, amelyeket a legtöbb számítógépes rendszer körülbelül azonos sebességgel értékel, így a csúcskategóriás rendszerek ezeket a funkciókat valamivel gyorsabban értékelhetik, mint az alacsony kategóriájú rendszerek (2–10-szer gyorsabban, de nem 10–100-szor). gyorsabban), amint azt a CPU-eltérések is jelenthetik. Ezek az arányok " egalitáriusak " elégek a tervezett alkalmazásokhoz: a funkciók hatékonyan megakadályozzák a visszaéléseket, és nem tesznek tiltó késedelmet a törvényes interakciókhoz a rendszerek széles körében.

Az új egalitárius megközelítés a memóriához kötött funkciókra támaszkodik. Mint korábban említettük, a memóriához kötött funkció olyan funkció, amelynek számítási idejét a memória elérésére fordított idő uralja. A memóriához kötött funkció kiszámíthatatlan módon jut el a memória nagy területének helyeihez oly módon, hogy a gyorsítótárak használata nem hatékony. Az elmúlt években a CPU sebessége drasztikusan nőtt, de a fő memória gyorsabb fejlesztése terén viszonylag kicsi az előrelépés. Mivel az arányok a memória késleltetése gépek épült az elmúlt öt évben jellemzően nem több, mint kettő, és majdnem mindig kevesebb, mint négy, a memória kötött funkció lesz egalitárius, hogy a legtöbb rendszer a belátható jövőben.

Lásd még

Hivatkozások

Külső linkek