Speichergebundene Funktion - Memory-bound function

Speicherplatzgrenze bezieht sich auf eine Situation , in der die Zeit ein gegebenes abzuschließen Rechenproblem wird in erster Linie durch die Menge der entschiedenen Speicher benötigt , um die Arbeit zu halten Daten . Dies steht im Gegensatz zu Algorithmen, die rechen gebunden , wobei die Anzahl der elementaren Rechenschritte ist der entscheidende Faktor.

Speicher- und Rechengrenzen können manchmal gegeneinander ausgetauscht werden, z. B. durch Speichern und Wiederverwenden vorläufiger Ergebnisse oder Verwenden von Nachschlagetabellen .

Speichergebundene Funktionen und Speicherfunktionen

Speichergebundene Funktionen und Speicherfunktionen sind insofern miteinander verbunden, als beide einen umfangreichen Speicherzugriff beinhalten, zwischen beiden jedoch unterschieden wird.

Speicherfunktionen verwenden eine dynamische Programmiertechnik , die als Memoisierung bezeichnet wird, um die möglicherweise auftretende Ineffizienz der Rekursion zu verringern. Es basiert auf der einfachen Idee, Lösungen für Teilprobleme zu berechnen und zu speichern, damit die Lösungen später wiederverwendet werden können, ohne die Teilprobleme erneut zu berechnen . Das bekannteste Beispiel, das die Memoisierung nutzt, ist ein Algorithmus , der die Fibonacci-Zahlen berechnet . Der folgende Pseudocode verwendet Rekursion und Memoisierung und wird in linearer CPU-Zeit ausgeführt : 

 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
 }

Vergleichen Sie das Obige mit einem Algorithmus, der nur Rekursion verwendet und in exponentieller CPU-Zeit ausgeführt wird: 

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

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

Während der Nur-Rekursions-Algorithmus einfacher und eleganter ist als der Algorithmus, der Rekursion und Memoisierung verwendet, weist der letztere eine wesentlich geringere zeitliche Komplexität auf als der erstere.

Der Begriff "speichergebundene Funktion" ist erst kürzlich aufgetaucht und wird hauptsächlich zur Beschreibung einer Funktion verwendet, die XOR verwendet und aus einer Reihe von Berechnungen besteht, bei denen jede Berechnung von der vorherigen Berechnung abhängt. Während Speicherfunktionen seit langem ein wichtiger Akteur bei der Verbesserung der Zeitkomplexität sind, haben speichergebundene Funktionen weitaus weniger Anwendungen gesehen. In jüngster Zeit haben Wissenschaftler jedoch eine Methode vorgeschlagen, bei der speichergebundene Funktionen verwendet werden, um Spammer vom Missbrauch von Ressourcen abzuhalten. Dies könnte ein wichtiger Durchbruch in diesem Bereich sein.

Verwenden speichergebundener Funktionen, um Spam zu verhindern

Speichergebundene Funktionen können in einem Proof-of-Work-System nützlich sein , das Spam abschrecken kann , das im Internet zu einem Problem von epidemischem Ausmaß geworden ist .

1992 veröffentlichten die IBM-Forscher Cynthia Dwork und Moni Naor auf der CRYPTO 1992 einen Artikel mit dem Titel Preisgestaltung über die Verarbeitung oder Bekämpfung von Junk-Mail , in dem die Möglichkeit vorgeschlagen wurde, CPU-gebundene Funktionen zu verwenden, um Missbraucher vom Versenden von Spam abzuhalten. Das Schema basierte auf der Idee, dass Computerbenutzer eine Ressource viel häufiger missbrauchen, wenn die Kosten für den Missbrauch der Ressource vernachlässigbar sind: Der Grund dafür, dass Spam so weit verbreitet ist, ist, dass das Senden einer E-Mail für Spammer nur geringe Kosten verursacht.

Dwork und Naor schlugen vor, dass Spam durch zusätzliche Kosten in Form einer teuren CPU- Berechnung reduziert werden könnte : CPU-gebundene Funktionen würden für jede Nachricht CPU-Ressourcen auf dem Computer des Absenders verbrauchen und somit verhindern, dass große Mengen an Spam in a gesendet werden kurze Zeit.

Das Grundschema, das vor Missbrauch schützt, lautet wie folgt:
Sei S Absender, R Empfänger und M E-Mail. Wenn R zuvor zugestimmt hat, eine E-Mail von S zu erhalten , wird M auf die übliche Weise übertragen. Andernfalls S berechnet eine Funktion g (m) und sendet (M, G (M)) zu R . R prüft, ob das, was es von S empfängt, die Form (M, G (M)) hat . Wenn ja, R akzeptiert M . Andernfalls lehnt R M ab . Die Abbildung rechts zeigt Fälle, in denen keine vorherigen Vereinbarungen getroffen wurden .

Die Funktion G () wird so gewählt, dass die Überprüfung durch R relativ schnell ist (eine Millisekunde dauert) und dass die Berechnung durch S etwas langsam ist (mindestens einige Sekunden). Daher wird S davon abgehalten, M ohne vorherige Vereinbarung an mehrere Empfänger zu senden : Die Kosten in Bezug auf Zeit und Rechenressourcen für die wiederholte Berechnung von G () werden für einen Spammer, der viele Millionen E-Mails senden möchte, sehr unerschwinglich .

Das Hauptproblem bei der Verwendung des obigen Schemas besteht darin, dass schnelle CPUs viel schneller rechnen als langsame CPUs. Darüber hinaus verfügen High-End-Computersysteme auch über ausgefeilte Pipelines und andere vorteilhafte Funktionen, die Berechnungen erleichtern. Infolgedessen wird ein Spammer mit einem System nach dem Stand der Technik kaum von einer solchen Abschreckung betroffen sein, während ein typischer Benutzer mit einem mittelmäßigen System nachteilig betroffen sein wird. Wenn eine Berechnung auf einem neuen PC einige Sekunden dauert , kann sie auf einem alten PC eine Minute und auf einem PDA einige Minuten dauern , was für Benutzer alter PCs ein Ärgernis sein kann, für Benutzer von PDAs jedoch wahrscheinlich nicht akzeptabel ist. Die Ungleichheit in der Client-CPU-Geschwindigkeit ist eines der wichtigsten Hindernisse für die weit verbreitete Übernahme von Schemata, die auf einer CPU-gebundenen Funktion basieren. Daher geht es den Forschern darum, Funktionen zu finden, die von den meisten Computersystemen mit ungefähr derselben Geschwindigkeit ausgewertet werden, sodass High-End-Systeme diese Funktionen möglicherweise etwas schneller auswerten als Low-End-Systeme (2–10-mal schneller, aber nicht 10–100-mal schneller), wie CPU-Unterschiede implizieren könnten. Diese Verhältnisse sind für die beabsichtigten Anwendungen " egalitär " genug: Die Funktionen wirken wirksam gegen Missbräuche und führen nicht zu einer unerschwinglichen Verzögerung legitimer Interaktionen in einer Vielzahl von Systemen.

Der neue egalitäre Ansatz besteht darin, sich auf gedächtnisgebundene Funktionen zu stützen. Wie bereits erwähnt, ist eine speichergebundene Funktion eine Funktion, deren Rechenzeit von der Zeit dominiert wird, die für den Zugriff auf den Speicher aufgewendet wird. Eine speichergebundene Funktion greift auf unvorhersehbare Weise auf Speicherorte in einem großen Speicherbereich zu, sodass die Verwendung von Caches nicht effektiv ist. In den letzten Jahren ist die Geschwindigkeit der CPU drastisch gestiegen, bei der Entwicklung eines schnelleren Hauptspeichers wurden jedoch vergleichsweise geringe Fortschritte erzielt. Da das Verhältnis der Speicherlatenzen von Maschinen, die in den letzten fünf Jahren gebaut wurden, normalerweise nicht größer als zwei und fast immer kleiner als vier ist, wird die speichergebundene Funktion auf absehbare Zeit für die meisten Systeme egalitär sein.

Siehe auch

Verweise

Externe Links