Messung der Intensität des eingehenden Ereignisstroms im Zerfallsmodell

    In der Klasse der Stream-Algorithmen gibt es eine Unterklasse, die das Problem der Suche nach schweren Elementen (Heavy Hitters) löst. Im Allgemeinen wird diese Aufgabe so formuliert, dass „die am häufigsten auftretenden Ereignisse im Eingabestrom identifiziert und ihre Intensität gemessen werden“. In dieser Veröffentlichung schlägt Artyom janatem Shvorin, Mitarbeiter von Qrator Labs, einen effektiven Algorithmus zur Lösung dieses Problems vor.

    Einleitung


    Algorithmen zum Auffinden schwerer Elemente helfen bei der Lösung von Problemen, z. B. bei der Bekämpfung von Netzwerküberlastungen, beim Erkennen von Netzwerkanomalien und -angriffen und beim Verwalten des dynamischen Routings. Mit dem bekannten NGINX-Webserver können Sie beispielsweise die Intensität von Anforderungen auf eine bestimmte Ressource beschränken. Dazu muss die Intensität quantitativ gemessen werden.

    In dieser Veröffentlichung möchten wir dem Leser einen anderen Ansatz zur Messung der Intensität des Ereignisflusses bei Vorhandensein vieler verschiedener (nicht identischer) Ereignisflüsse zeigen. Lassen Sie viele Arten von Ereignissen gegeben sein. Es muss ausgewertet werden, wie oft ein Ereignis dieses Typs auftritt, und es muss auf Fälle geachtet werden, in denen ein Ereignis eines Typs "zu oft" wiederholt wird.

    Ein wichtiges Merkmal dieses Tools ist seine hohe Effizienz, damit es nicht zum Engpass im gesamten Verkehrsanalyse- und Filtersystem wird. In diesem Fall geht es darum, ein Ereignis für mehrere Dutzend Taktzyklen des Zentralprozessors moderner Computer zu verarbeiten.

    Zusätzlich zur eigentlichen Messung der Intensität müssen die am häufigsten auftretenden Ereignistypen hervorgehoben werden. Ihre Intensität muss genauer gemessen werden, während seltene Arten von Ereignissen keine große Rolle spielen und es nicht erforderlich ist, ihre Intensität mit hoher Genauigkeit zu bewerten.

    Die Arbeit stellt den von uns entwickelten Zählalgorithmus auf Zerfallsbasis vor, der auf dem Zerfallsmodell einer radioaktiven Substanz basiert (siehe Abschnitt "Zerfallsmodell") und das Problem der Suche nach schweren Elementen mit hoher Effizienz löst.

    Die Aufgabe, schwere Elemente zu finden


    Aufgabenklassifizierung


    Folgende Unterklassen können in der beschriebenen Problemklasse unterschieden werden:

    • Schwellen-$ t $. Es ist erforderlich, Ströme mit einer höheren Intensität als einer bestimmten Fraktion zu isolieren$ t $ die Intensität des gesamten eingehenden Verkehrs.
    • Top-$ k $. Es ist erforderlich, einen bestimmten Betrag zuzuteilen$ k $ intensivste Fäden.
    • Isolierung von Strömen, deren Intensität einen bestimmten absoluten Wert überschreitet.

    Der vorgeschlagene Algorithmus gehört zur letzten der aufgelisteten Unterklassen.

    Zielarchitektur


    Abhängig von der Plattform, auf der dieser Stream-Algorithmus ausgeführt werden soll, gibt es eine Reihe von Hardware-Einschränkungen. Manchmal muss die erforderliche Funktionalität in Netzwerkgeräte (Switch, Switch usw.) eingebettet werden. Der vorgeschlagene Algorithmus soll auf einem Universalprozessor verwendet werden, kann jedoch mit einigen Parameterwerten in Netzwerkgeräte eingebettet werden.

    Aufgabenparameter


    • Der absolute Wert der Durchflussmenge, der als "gefährlich" eingestuft wird. Die Aufgabe des Algorithmus besteht darin, Flüsse zu identifizieren, deren Intensität einen vorgegebenen Schwellenwert überschreitet.
    • Schlüsselgröße - Kennung, die die Art des Ereignisses bestimmt. Bei dieser Implementierung ist es wie bei vielen anderen Algorithmen erforderlich, die Schlüsselwerte in einer Tabelle zu speichern, damit die Schlüsselgröße die Speicherkosten beeinflusst.
    • Ein Verfahren zum Berechnen der Schätzungen der Intensität eines Stroms gemäß den Ankunftszeiten derselben Ereignisse. Im Wesentlichen ist dies eine algorithmische Definition der Flussintensität. In diesem Fall wird ein exponentieller gleitender Durchschnitt berechnet, der einen einzigen Parameter hat - die charakteristische Zeit$ \ tau $, wobei das Gewicht des Ereignisses nach seiner Ankunft berücksichtigt wird.

    Lösungsgenauigkeit


    • Die Schätzung der Qualität des Algorithmus kann ein relativer oder absoluter Fehler bei der Schätzung der Strömungsintensität sein. Verwenden Sie auch$ (\ varepsilon, \ delta) $-Näherung als Schätzung der Genauigkeit: wenn mit Wahrscheinlichkeit $ 1- \ delta $ der fehler ist nicht mehr als $ \ varepsilon $Dann sagen sie, dass der Algorithmus eine Genauigkeitscharakteristik hat $ (\ varepsilon, \ delta) $.
    • Wenn der Fehler eher qualitativer als quantitativer Natur ist, z. B. die Aufnahme oder Nichtaufnahme eines bestimmten Datenstroms in die Liste der intensivsten Datenströme in der Task.$ k $Anschließend werden die Wahrscheinlichkeiten einer falsch-positiven und einer falsch-negativen Reaktion zur Bewertung herangezogen.

    Overhead


    Das Hauptmerkmal des Algorithmus ist in der Regel die maximale Intensität des eingehenden Stroms, den er verarbeiten kann. Das heißt, nur die Verarbeitungszeit eines Ereignisses ist wichtig. In der Praxis wirken sich jedoch auch andere Hardwareeinschränkungen aus, z. B. die Größe des Speichers, der zum Speichern der gesammelten Informationen über den Stream verwendet wird. Beim Einbetten von Funktionen in Netzwerkgeräte treten besonders schwerwiegende Hardwareeinschränkungen auf. Auf normalen Computern hilft jedoch das Vorhandensein einer großen Menge RAM-DRAM nicht immer, da der Zugriff auf DRAM unannehmbar lange dauern kann. Um die erforderliche Leistung zu erzielen, müssen Sie Kompromisse bei der Genauigkeit der Messung eingehen und die Größe des verwendeten Speichers so begrenzen, dass er in den Prozessor-Cache passt. Bei dieser Implementierung wird die Tabelle mit aussagekräftigen Parameterwerten im L2-Cache des Prozessors abgelegt. Infolgedessen konnte sichergestellt werden, dass die Verarbeitungszeit eines Ereignisses mehrere zehn Prozessorzyklen betrug.

    Methoden zur Beurteilung der Durchflussintensität


    Um die Intensität der Wiederholung von Ereignissen eines bestimmten Typs zu bestimmen, muss die Anzahl der Ereignisse über die Zeit berechnet werden. Dazu müssen Sie die Zeit des Ereignisses festlegen und es irgendwie speichern. In der Regel wird dazu ein Zähler verwendet, der beim Eintreten des entsprechenden Ereignisses inkrementiert. Dann wird die Intensität als das Verhältnis des Zählerwerts zu dem Zeitintervall geschätzt, in dem die Messung durchgeführt wird. Genauere Methoden zum Messen des aktuellen Werts der Intensität verwenden verschiedene Versionen des gleitenden Durchschnitts . Zum Beispiel ist der exponentielle gleitende Durchschnitt (EMA) eine Art gewichteter gleitender Durchschnitt mit exponentiell abnehmenden Gewichten.

    Eine neue Methode zur Berechnung der EMA wird vorgeschlagen. Hier wird ein exponentielles Zerfallsmodell verwendet, das ein physikalisches Phänomen wie den radioaktiven Zerfall beschreibt. Dieses Modell hat gegenüber dem herkömmlichen Ansatz mehrere Vorteile. Erstens ist die Präsentation von Daten sparsamer im Speicher. Zweitens ermöglicht das Abklingmodell eine schnelle Implementierung der Zähleraktualisierungsoperation - es erfordert eine kleine Anzahl von Ganzzahlarithmetikoperationen und einen zwischengespeicherten Speicherzugriff.

    Mehrere Thread-Abrechnungsmethoden


    Bei der Suche nach schweren Elementen besteht das Problem nicht nur in der hohen Intensität des Eingangsverkehrs, sondern auch in einer großen Anzahl verschiedener zu überwachender Flüsse (Ereignistypen). Eine naive Implementierung beinhaltet die Einrichtung eines separaten Zählers für jeden Thread, was zu einem erheblichen Speicherverbrauch führt. In diesem Fall besteht nicht nur die Gefahr der Erschöpfung des gesamten verfügbaren Speichers, sondern auch einer erheblichen Geschwindigkeitsverlangsamung aufgrund von Fehlern im Cache. Daher lehnen sie in der Regel die genaue Lösung des Problems der Suche nach schweren Elementen ab und verwerfen einen Teil der gesammelten Informationen über die Flüsse. Es gibt viele bekannte Methoden, um die Menge des verwendeten Speichers zu begrenzen und die Verarbeitungszeit eines Ereignisses zu verkürzen. Einige davon sind nachfolgend aufgeführt:

    • Packet Sampling
    • Platzsparender Algorithmus
    • Hashparallel
    • Hashpipe
    • Count-Min-Skizze

    Aufgabenformalisierung


    Bevor Sie mit der Beschreibung des Algorithmus fortfahren, müssen Sie mit ausreichender mathematischer Genauigkeit das Problem der Messung des Ereignisflusses formulieren, das wir in diesem Abschnitt ausführen werden.

    Die Abfolge von Ereignissen desselben Typs wird als eine Menge von Elementarereignissen definiert.$ \ {event_k \} _ {k \ in I} $Wo ist der Index? $ k $ läuft durch ein endliches oder unendliches diskretes Intervall $ I \ subset \ mathbb {Z} $.

    Im einfachsten Fall wird ein Ereignis nur durch den Zeitpunkt seines Auftretens bestimmt:$ event_k = t_k $, und die Ereignisse werden rechtzeitig geordnet: $ t_ {k_1} <t_ {k_2} $ für $ k_1 <k_2 $. In den meisten Implementierungen von Ereignisabrechnungssystemen wird die Zeit als diskrete Größe betrachtet:$ t_k \ in \ mathbb {Z} $Aus theoretischen Gründen ist es jedoch zweckmäßig, die Zeit zu verallgemeinern und als kontinuierlich zu betrachten: $ t_k \ in \ mathbb {R} $.

    Die Hauptfrage, die Event-Accounting-Systeme beantworten müssen, ist die Schätzung der Flussintensität. Die Intensität kann für einen einheitlichen Ereignisfluss streng formalisiert werden. Gleichmäßiger Fluss$ \ {t_k \} $ wie folgt definiert:

    $ t_k = \ varphi + pk, \ quadk \ in \ mathbb {Z}, $


    wo $ p> 0 $, $ \ varphi \ in [0, p) $- Durchflussparameter - Periode bzw. Phase. Das heißt, Ereignisse treten in regelmäßigen Abständen auf. Dann wird die Intensität eines solchen Flusses per Definition ausgedrückt als$ r = 1 / p $.

    Für ungleichmäßige Strömungen eine formale Definition der Intensität$ r = r (\ {t_k \}) $kann je nach Problemstellung variieren. Das Zerfallsmodell bleibt in diesem Fall funktionsfähig und nützlich, die Bewertung der Qualität der Berechnung der wahren Intensität wird jedoch nachstehend nur für den Fall gleichmäßiger Strömungen angegeben.

    Bei einigen Modellen ist es erforderlich, einige Merkmale des Ereignisses zu berücksichtigen, beispielsweise sein Gewicht$ c_k $- die Größe des Beitrags dieses Ereignisses zur gemessenen Intensität. Das Ereignis wird dann nicht nur durch den Zeitpunkt des Auftretens, sondern auch durch das Gewicht bestimmt:$ event_k = (t_k, c_k) $.

    In typischen Implementierungen von Ereignisabrechnungssystemen wird ein Zähler gestartet$ s $, der auf irgendeine Weise Informationen über den Fluss von Ereignissen sammelt und aus seinem aktuellen Wert jederzeit eine Schätzung der Flussintensität abrufen kann $ \ hat {r} = \ hat {r} (s) $so dass $ r \ ungefähr \ hat {r} $. Der Zähler wird beim Eintreffen eines anderen Ereignisses aktualisiert$ event_k $:

    $ s \ leftarrow update (s, event_k), $


    wo $ update () $- eine Funktion, die von der Implementierung bestimmt wird. Nachfolgend einige Beispiele mit Möglichkeiten zur Implementierung der Funktion.$ update () $:

    • Einfache Zählung der Anzahl der Ereignisse: $ update_1 (s, event_k) = s + 1 $;
    • Zählung der Anzahl der Ereignisse nach Gewicht: $ update_c (s, event_k) = s + c_k $;
    • Berechnung des Exponential Moving Average (EMA) mit Parameter$ \ beta $. Hier ist die Theke$ s = (v, t) $ speichert zwei Werte: den tatsächlichen EMA-Wert und den Zeitpunkt der letzten Aktualisierung.

      $ update_ {EMA} ((v, t), event_k) = (v ', t'), $

      wo $ v '= \ beta + (1- \ beta) ^ {t_k-t} \ cdot v, \ quad t' = t_k $.

    Bei einigen Aufgaben müssen Sie zwischen Ereignisströmen unterscheiden. Angenommen, es gibt viele verschiedene Arten von Ereignissen, die durch einen Index nummeriert sind$ i = 1, \ dots N $und es ist erforderlich, die Nachrichtenflüsse jedes Typs separat zu betrachten. Dann wird das Ereignis als beschrieben$ event_k = (t_k, i_k) $ (oder angesichts des Gewichts des Ereignisses $ event_k = (t_k, i_k, c_k) $), wo $ i_k $- Art der Veranstaltung. Viele Indizes$ k $im Zusammenhang mit dieser Art von Veranstaltung $ i $ bezeichnen $ I_i = \ {k \ mid i_k = i \} $.

    Zerfallsmodell


    Das Zerfallsmodell wird wie folgt beschrieben:

    $ v (t) = v_0e ^ {- \ lambda t}, $


    wo $ v_0 $ - "Stoffmenge" zum Zeitpunkt Null, $ v (t) $ - Menge zum Zeitpunkt $ t $, $ \ lambda $- Modellparameter (die sogenannte Zerfallskonstante). Der Name dieses Modells spiegelt die Tatsache wider, dass es das physikalische Phänomen des radioaktiven Zerfalls beschreibt .

    Zusätzlich führen wir folgende Notation ein:

    $ \ tau = 1 / \ lambda, \ quad \ alpha = e ^ {\ lambda}. $


    In unserem Fall als Modellparameter statt $ \ lambda $ bequemer zu bedienen $ \ tau $seit dem $ \ tau $hat eine zeitliche Dimension und kann informell als charakteristisches Zeitintervall definiert werden, in dem die Historie der Ereignisse gesammelt wird.

    Per Definition nehmen wir an, dass jeder Ereignistyp einer Größe entspricht$ v $Dies hat eine physikalische Bedeutung von „Substanzmenge“ und hängt von der Zeit ab, die beim Eintreten eines Ereignisses um eins springt, und der Rest der Zeit verringert sich gemäß dem oben angegebenen Exponentialgesetz.

    In Abb. Abbildung 1 zeigt, wie sich der Wert mit der Zeit ändert.$ v $für gleichmäßige Strömungen mit unterschiedlichen Intensitäten und für ungleichmäßige Strömungen.



    Abbildung 1: Wert$ v $Ströme für unterschiedliche

    Größe$ v $nicht explizit gespeichert, kann aber jederzeit berechnet werden. Gleicher Wert wird gespeichert$ s $so dass zur Zeit $ t_ {now} $ Wert $ v $ wie folgt ausgedrückt:

    $ v = \ alpha ^ {s-t_ {now}}. $


    Diese Darstellung entspricht dem Zerfallsmodell.

    Die Berechnung des Zählers im Zerfallsmodell entspricht der Berechnung des exponentiellen
    gleitenden Durchschnitts bis zu einem Normalisierungsfaktor (Konstante). Ein wichtiges Merkmal dieser Darstellung ist, dass der einzige im Zähler gespeicherte Wert ein Paar (Zeitpunkt des letzten Ereignisses, akkumulierter Wert) ersetzt, das im herkömmlichen Ansatz gespeichert wird.

    Zähleraktualisierung


    Eine nicht einfache Operation aktualisiert den Zählerwert $ s $beim Eintreten eines anderen Ereignisses. In diesem Fall ersetzen$ s $ zu einer neuen Bedeutung $ s '$welches sich aus folgender Gleichheit ergibt:

    $ \ alpha ^ {s'-t_ {now}} = \ alpha ^ {s-t_ {now}} + 1. $


    Hier links ist der Wert $ v $ gleich nach der veranstaltung und rechts der wert $ v $unmittelbar vor der Veranstaltung, erhöht um den Beitrag der Veranstaltung (gleich Eins). Wirksame Methoden zur Berechnung des Aktualisierungsergebnisses werden im Folgenden vorgeschlagen.

    In Bezug auf die Funktion$ update () $ Ausgehend von der Definition wird die Aktualisierungsoperation wie folgt ausgedrückt:

    $ update_1 (s, event_k) = t_k + \ log_ \ alpha (1 + \ alpha ^ {s-t_k}). $


    Hier ist die Ausführungszeit der Operation $ t_ {now} $ fällt mit der Zeit zusammen $ t_k $ die Ankunft der Nachricht.

    Intensitätsbestimmung


    Es gebe einen gleichmäßigen Fluss von Intensitätsereignissen $ r $Ereignisse treten also mit einem Punkt auf $ p = 1 / r $. Ein gleichmäßiger Fluss ist wie definiert definiert.

    Wenn die Messung unmittelbar nach dem Auftreten des nächsten Ereignisses durchgeführt wird, ist dies$ t_ {now} = t_n $ für manche $ n $dann akkumulierte der Zählerwert über die Zeit $ s $ wird wie folgt ausgedrückt:

    $ \ alpha ^ {s-t_ {now}} = \ sum_ {k = - \ infty} ^ n \ alpha ^ {t_k-t_ {now}} = \ sum_ {k = 0} ^ \ infty \ alpha ^ { -kp}, $


    woher

    $ \ alpha ^ {- \ Delta s} + \ alpha ^ {- p} = 1, $


    wo $ \ Delta s = s-t_ {now} $- der relative Wert des Zählers.

    In einem allgemeineren Fall kann der Zeitpunkt der Messung zwischen Ereignissen liegen:
    $ t_ {now} = t_n + \ psi $, $ \ psi \ in [0, p) $. In diesem Fall unterscheidet sich der Zählerwert in einer kleineren Richtung um den Betrag$ \ psi $:

    $ \ alpha ^ {- (\ Delta s + \ psi)} + \ alpha ^ {- p} = 1. $


    Die Aufgabe der Intensitätsmessung besteht darin, die Intensität anhand des Wertes des Zählers zu bewerten. Unter der Annahme, dass der Fluss gleichmäßig ist, kann man Schätzungen der wahren Intensität des gleichmäßigen Flusses von oben und unten erhalten, wobei die Extremwerte in der vorherigen Gleichung ersetzt werden$ \ psi = 0 $ und $ \ psi = p $:

    $ r ^ - \ le r <r ^ +, $


    wo

    $\begin{align}r^+&=r^+(\Delta s)=\frac1{\log_\alpha(1+\alpha^{-\Delta s})}\\r^-&=r^-(\Delta s)= \left\{\begin{array}{ll}\frac1{-\log_\alpha(1-\alpha^{-\Delta s})}&\mbox{при }\Delta s>0\\ 0&\mbox{иначе}\end{array}\right.\end{align}$


    Beide Bewertungen $r^+$ und $r^-$ monoton vom Wert des Zählers abhängen $s$(siehe Abb. 2) Daher sind zum Beispiel keine zusätzlichen Berechnungen erforderlich, um den aktuellen Zählerwert mit einem Schwellenwert zu vergleichen.



    Abbildung 2: Funktionsgraph$r^-$ und $r^+$ für $\tau=15$

    In dem Zerfallsmodell ist die Intensität beliebiger (nicht notwendigerweise gleichförmiger) Flüsse per Definition durch die obigen Schätzungen gegeben $r^+$ und $r^-$. Wenn die Messung außerdem unmittelbar nach der Verarbeitung des Ereignisses erfolgt, wird angenommen, dass die Intensität genau der unteren Schätzung entspricht.

    Die Grenzen der Anwendbarkeit des Zerfallsmodells


    Der Wert der Intensität unterliegt Einschränkungen, die im Zerfallsmodell korrekt gemessen werden können.

    Erstens, wenn der Zeitpunkt des Auftretens von Ereignissen als eine diskrete Größe gemessen wird, kann die Periode des Flusses nicht kleiner als eins sein. Das heißt, die Durchflussintensität sollte nicht überschritten werden$r_{max}=1$. Ab hier folgt eine Einschränkung des relativen Wertes des Zählers$\Delta s = s-t_{now}$ - Der Wert darf nicht überschritten werden $\sigma_{max}$was sich aus der Formel ergibt:

    $r^-(\sigma_{max}) = r_{max}.$


    Wert $\sigma_{max}$ wie folgt bewertet:

    $\sigma_{max}=\tau\ln\tau+\omega(\tau),$


    wo $0\le\omega(\tau)\le1/2$.

    Zweitens ist die Schätzung der Intensität schwacher (geringer) Ströme schwierig: für kleine relative Werte des Zählers$\Delta s$ Genauigkeit der oberen und unteren Schranke $r^+$ und $r^-$ verschlechtert sich und bei negativen Werten $\Delta s$Die Schätzung der niedrigeren Intensität degeneriert auf Null.

    Es gibt auch eine Beschränkung der Betriebszeit von Implementierungen des Abklingmodells, die mit einem Überlauf von Zählern verbunden sind. Da der Zählerwert nicht entkommen kann$t_{now}$ mehr als $\sigma_{max}$Die Betriebszeit des Systems wird tatsächlich durch die Länge des Zählers und die Dauer eines Zyklus bestimmt. Wenn ein 64-Bit-Register zum Speichern des Zählers verwendet wird, läuft dieser 100 Jahre lang nicht über. Bei Implementierungen mit Low-Bit-Registern sollte jedoch ein Zählerrücksetzmechanismus bereitgestellt werden.

    Mehrere Stream-Algorithmen


    Eigenschaften des Zerfallsmodells


    Die Besonderheit bei der Verwendung von EMA als Zählerwert besteht darin, dass der akkumulierte Wert bei Beendigung des Ereignisflusses schnell (exponentiell im Zeitverlauf) abnimmt und von Null nicht mehr zu unterscheiden ist. Im Zerfallsmodell wird diese Tatsache verwendet, um den Zähler automatisch zurückzusetzen: obwohl der Zählerwert$s$ Mit dem Eintreffen von Ereignissen, einige Zeit nach Beendigung des Ereignisflusses, erhöht sich der Wert ständig $v=\alpha^{s-t_{now}}$kann als gleich Null betrachtet werden, ohne den Zählerwert explizit zu ändern. Zeit$T_{vanish}$, bei dem ein zuvor akkumulierter Wert auf eine bedingte Null abfällt, hängt vom Parameter ab $\tau$und erforderliche Genauigkeit. Es wird ausgedrückt als$T_{vanish}=T_{min}+\sigma_{max}$wo $T_{min}$- die Abfallzeit des Wertes, der infolge eines einzelnen Ereignisses akkumuliert wurde. Der Abschnitt „Tabellenimplementierung“ gibt einen genauen Ausdruck$T_{min}$, aber hier genügt es, folgende Tatsache zu berücksichtigen: $T_{vanish} = O(\tau\ln\tau)$mit fester Genauigkeit.

    Ab hier folgt eine Schätzung der Größe des Zählerspeichers von oben unter Berücksichtigung vieler Abläufe für den Fall, dass Informationen überhaupt nicht verloren gehen - es reicht aus, um$T_{vanish}\cdot r_{max}$Zellen. Es gibt viele Verwendungsmöglichkeiten für das Problem der Suche nach schweren Elementen, bei denen keine großen Werte erforderlich sind.$\tau$und der gesamte Speicher befindet sich im RAM oder sogar im Cache des L3- oder L2-Prozessors. In diesem Fall ist eine kurze Zugriffszeit auf den Speicher vorgesehen, so dass die Aufgabe bei hohen Werten der Eingangsstromintensität durchführbar wird.

    Eine Hash-Tabelle eignet sich zum Implementieren des Speichers, wobei der Schlüssel die Art des Ereignisses ist. Gleichzeitig werden Zellen mit einem Zählerwert als leer betrachtet.$s$ erfüllt die Bedingung $s-t_{now} \le T_{min}$.

    Numerische Implementierung der Zerfallszählung


    Wertaktualisierungsvorgang


    Wir führen die folgende Notation ein:

    $\rho_\tau(x) = \tau\ln(1+e^{x/\tau}) = \log_{\alpha}(1+\alpha^x).$


    Dann wird die Aktualisierungsoperation wie folgt ausgedrückt:

    $s' = t_{now} + \rho_\tau(s-t_{now}).$


    Somit reduziert sich das Problem auf die effektive Berechnung der Approximation der Funktion $\rho_\tau$. Es ist praktisch, die Zeit als Ganzzahl darzustellen, sie beispielsweise in Prozessorzyklen zu messen, sodass eine Ganzzahlanzeige erstellt werden muss${R:\mathbb{Z}\to\mathbb{Z}}$so dass:

    $R_\tau(T) \approx \rho_\tau(T)\quad\mbox{для }T\in\mathbb{Z}.$


    Für diese Aufgabe ist Genauigkeit nicht relativ wichtig, sondern absolut, da additive Operationen hauptsächlich mit Zeitwerten verwendet werden. Offensichtlich ist aufgrund der Integralität der Zeitdarstellung ein Fehler von weniger als 0,5 Taktzyklen nicht erreichbar.
    Darüber hinaus führt die Messung der aktuellen Zeit in der Regel zu Fehlern. Wenn es zum Beispiel eine Möglichkeit gibt, die Zeit mit einer Genauigkeit von 10 Maßen zu messen, reicht es aus, dies zu fordern$R_\tau$ ergab eine Annäherung von ungefähr der gleichen Genauigkeit: $\left|R_\tau(T) - \rho_\tau(T)\right| \le 10.$

    Es können verschiedene Berechnungsmethoden vorgeschlagen werden. $R_\tau$ unterschiedliche Komplexität und Wirksamkeit.

    Berechnung $R_\tau$: FPU


    Am einfachsten ist es, Fließkomma-Arithmetik zu verwenden und direkt zu berechnen $\rho_\tau$per definitionem. Die Ausführungszeit dieser Operation beträgt ungefähr 100 Prozessorzyklen, was im Vergleich zu der unten vorgeschlagenen Methode ziemlich viel ist.

    Berechnung $R_\tau$: Tabellenimplementierung


    Die Idee einer Tabellenimplementierung besteht darin, die vorberechneten Funktionswerte in einer Tabelle zu speichern.

    Erstens mit Identität

    $\rho_\tau(-x) = -x + \rho_\tau(x),$


    genug um zu bauen $R_\tau(T)$ nur für $T\le0$.

    Zweitens seit

    $\rho_\tau(x)\to 0 \mbox{ при } x\to-\infty,$


    existiert $T_{min}>0$so dass $R_\tau(T)=0$ bei $T\le-T_{min}$. Wo$T_{min}$ kann aus den folgenden Überlegungen gefunden werden:

    $T_{min}=\lceil t_{min}\rceil,\quad \rho_\tau(t_{min})=1/2,$

    woher
    $T_{min}=\lceil-\log_\alpha(\alpha^{1/2}-1)\rceil=\lceil-\tau\ln(e^{1/{2\tau}}-1)\rceil.$

    Es genügt also zu definieren $R_\tau(T)$ für ${T_{min}<T\le0}$.

    Funktionsgraph$\rho_\tau(x)$dargestellt in fig. 3. Die Besonderheit dieser Funktion besteht darin, dass bei einer Änderung des Parameters$\tau$an beiden achsen erfolgt die gleiche skalierung.



    Abbildung 3: Funktionsgraph$\rho_\tau(x)$

    Offensichtliche Umsetzung $R_\tau$ besteht im Aufbau eines Tisches aus $T_{min}$Zellen, in denen die berechneten Werte gespeichert werden. Da alle Werte der Funktion in diesem Intervall zwischen 0 und liegen$\rho_\tau(0)=\tau\ln2$beträgt die Gesamtgröße der Tabelle $T_{min}\log_2(\tau\ln2)$bisschen.

    Der Wertaktualisierungsalgorithmus lautet wie folgt:

    $\begin{align} t_{now}& \leftarrow getTime()\\ \delta & \leftarrow \min\{|s-t_{now}|, T_{min}\}\\ \delta' &\leftarrow R(-\delta)\\ s' &\leftarrow \delta' + \max\{s, t_{now}\} \end{align}$



    Die absolute Genauigkeit dieser Methode beträgt 1/2, da sie die beste ganzzahlige Approximation einer reellen Funktion liefert.

    Leistungsergebnisse


    Die folgenden drei Realisierungen des exponentiellen gleitenden Durchschnitts wurden miteinander verglichen:
    1. eine naive Implementierung von EMA;
    2. das Zerfallsmodell durch FPU (dh mit dem Aufruf der Funktionen exp () und log () der mathematischen Bibliothek);
    3. Das Zerfallsmodell nach der tabellarischen Methode.

    Quellcode des Tests für si: pastebin.com/N1Xg9dud .

    Die Ausführungszeit eines Aufrufs der update () - Funktion bei$\tau=100000$ (in diesem Fall die zu berechnende Tabelle $R_\tau$in dem L1 - Cache platziert) in Implementierungen 1, 2 und 3 100 , 125 , 11 CPU - Zyklen, respectively.

    Die Verwendung eines exponentiellen gleitenden Durchschnitts ist eine bequeme Methode, um Ereignisse zu zählen und die Intensität zu messen. Diese Operation ist jedoch rechenintensiv, was die Anwendungsmöglichkeiten stark einschränkt. Unsere Implementierung des Algorithmus basierend auf dem Zerfallsmodell ist zum einen schön und zum anderen effizienter als die naive Implementierung der EMA-Berechnung. Die Effizienz wird durch zwei Faktoren sichergestellt: eine tabellarische Berechnung der transzendentalen Funktion und eine wirtschaftlichere Speicherdarstellung des Zählers.

    Danksagung


    Diese Veröffentlichung wurde von uns im Rahmen eines Projekts in einem Testmodus erstellt, um die Funktionsmechanismen des Qrator-Filternetzwerks hervorzuheben. Vielen Dank an Anton Orlov, Artem Gavrichenkov, Evgeny Nagradov und Nikita Nikitadanilov Danilov für Diskussionen und Ideen.

    Jetzt auch beliebt: