Sortieren Sie den Ressourcenzugriffsplan für mehrere Threads, damit die Anzahl der Schreibkonflikte minimiert wird
Szenario:
Gegeben eine Menge von Ressourcen R:
Gegeben eine Reihe von Threads T, die parallel laufen:
Jeder Thread muss auf eine Liste von n Ressourcen zugreifen. Jede Liste ist ein Beispiel für R, was bedeutet, dass jede Ressource in jeder Liste eindeutig ist:
Da die Zugriffslisten jedoch zufällig ausgewählt werden, können Konflikte auftreten:
Die zufälligen Ressourcenlisten werden einmal am Anfang initialisiert. Danach führt jeder Thread anschließend eine atomAdd-Operation für jede Ressource in der Liste durch. Die Zugriffsreihenfolge der Ressourcen in jeder Liste ist irrelevant.
Frage:
Gibt es einen Algorithmus, der die Planungslisten sortiert, so dass die Anzahl der Schreibkonflikte minimiert wird? Das Endergebnis würde also so aussehen:
Meine bisherigen Einsichten:
- Die Stichprobenauswahl ist wichtig für den Kontext des Algorithmus, daher ist es keine Option, die Listen auf andere Weise zu initialisieren (nur ihre Reihenfolge kann geändert werden).
- Der Gesamtplan kann als Matrix S mit | T | betrachtet werden Zeilen und n Spalten, wobei jeder Eintrag ein Element von R ist.
- Wenn | T | & lt; = | R |, ist eine Lösung ohne Konflikte möglich.
- Wenn | T | == | R |, die Spalten einer optimierten Planungsmatrix S sind Permutationen von R.
- Wenn | T | & gt; | R | sollte die durchschnittliche Anzahl der Concurrent-Zugriffe in einer optimierten Planungsmatrix | T | sein / | R |
Mögliche Ansätze:
Ich suche nach einer analytischen Lösung für dieses Problem. Könnte es NP-vollständig sein? Wenn dies der Fall ist, denke ich darüber nach, einen genetischen Algorithmus zu entwickeln, um dieses Problem zu lösen.
Bearbeiten 1 : Diagramme hinzugefügt.
4 Antworten
Ich denke, die Frage lautet "können wir die Listen sortieren, um die Konflikte zu reduzieren."
Ich denke, eine optimale Lösung ist NP-vollständig, aber ich würde nach der Anzahl der Vorkommen in der Menge für jede Ressource suchen.
Schritt 1
Die am häufigsten verwendete Ressource ist die am schwersten zu planende Ressource. Somit würde ich diese Ressource in jeden der Threads in Position 1, 2, 3, 4, ... einfügen, bis ein Konflikt auftritt (der unvermeidlich sein kann), z. 1,2,3,4, ..., n, 1, 2, ....
Das sind die "großen Steine". Diese sollten zuerst platziert werden.
Schritt 2
Die nächste am häufigsten verwendete Ressource sollte dann ausprobiert werden. Dies sollte identifizieren, welche Schlitze (1 = & gt; n) kürzlich verwendet wurden, und diese Liste für eine Scheibe durchsuchen, die sowohl nicht zugewiesen als auch nicht kürzlich verwendet wurde.
Welcher Slot auch gewählt wird, er wird an die Spitze der zuletzt verwendeten Warteschlange verschoben, um für eine Weile vermieden zu werden.
Dies begünstigt die Verteilung der Ressource, erlaubt aber Duplikate. Diese Duplikate werden in letzter Zeit verwendet und nicht mehr für die Planung bevorzugt, bis keine gültigen Auswahlmöglichkeiten verfügbar sind.
Endlich
Schritt 2 wird für jede Ressource in der Reihenfolge ihres Auftretens wiederholt.
Formalisierungsproblem
Zunächst sieht es wie eine Variante von OSSP aus. Wir müssen R resources über T processors einplanen. Einige Planungszeiten sind 0 , einige sind 1 .
Allerdings müssen wir die gesamte Sequenz in n Zeitschritte vervollständigen, und es gibt genau n*T Nicht-Null-Zeitpläne.
Wir suchen also nach einer Terminplanung in n time, ohne T-T conflicts (da kein Thread gleichzeitig mit zwei Ressourcen arbeiten kann) und mit einer minimalen Anzahl von R-R Konflikten. Ich nehme an, dass die zu minimierende Zielfunktion ist:
Dabei ist count eine Anzahl von Threads, die die Ressource j zur Zeit i verwenden.
Problemdiagramm erstellen
Lassen Sie uns ein Diagramm G=(V,E) mit Vertex für jeden Thread (erster Teil) und jede Ressource (zweiter Teil) konstruieren. Für jede Planungszeit, die nicht Null ist, haben wir eine Kante vom Thread zur Ressource. Dieser Graph ist offensichtlich zweiteilig.
Jeder Thread-Vertex hat einen Grad von n .
Unser Ziel ist es, diesen Graphen mit n colours so zu kanten, dass:
-
Kein Fadenknoten hat zwei benachbarte Kanten mit der gleichen Farbe
-
Die Anzahl der angrenzenden Kanten mit der gleichen Farbe ist minimal
Konfliktfreie Lösung
Wenn es keinen Ressourcen-Vertex mit dem Grad d > n gibt, dann hat der Graph eine richtige Kantenfärbung mit höchstens n -Farben. Und die richtige Färbung ist natürlich die beste Farbe in Bezug auf die Zielfunktion - es gibt überhaupt keine Konflikte.
Die bipartite Kantenzeichnung kann in O(n * T * R) time erfolgen.
Lösung mit Konflikten
Angenommen, wir haben einen Ressourcenvertex mit dem Grad d > n . Das bedeutet, dass es keine richtige Kantenfärbung mit n Farben gibt, und wir werden einen Konflikt in unserem Zeitplan haben.
Gebunden an die Anzahl der Konflikte.
Wir haben einige Scheitelpunkte V_conflict mit Grad d > n . Dann ist die Anzahl der Konflikte genau q : 
Es kann nicht weniger sein, da jede widersprüchliche Farbe in der Kantenfärbung ein Konflikt in unserem Plan ist, und für jeden Vertex mit Grad d > n haben wir mindestens d - n widersprüchliche Farben.
Nun wollen wir eine Lösung mit genau q Konflikten konstruieren. Entfernen Sie einen beliebigen Kantensatz von jedem Stützpunkt in V_conflict , um ihren Grad auf n zu verringern. Wir haben genau q Kanten entfernt. Jetzt haben wir eine konfliktfreie Lösung (als richtige Graphenkantenfärbung in n colors).
Fügen Sie nun zuvor entfernte q -Kanten ein und weisen Sie Farbe zu, die noch keiner Kante des entsprechenden Fadenscheitelpunktes zugewiesen ist. Da jede hinzugefügte Kante nur einen Konflikt verursachen kann, haben wir jetzt genau q , was eine untere Grenze ist.
Dieser ganze Schritt mit Konflikten kann gemacht werden in:
-
O(R)für die Bestimmung vonV_conflict -
O(R*T)zum Entfernen von Konfliktkanten -
O(n * T * R)zum Lösen der reduzierten konfliktfreien Version. -
O(n * q)für das Hinzufügen der Kanten zurück zum Graphen
Eine vollständige Lösung kann in O(n * T * R) time erreicht werden.
Annäherung
- Aus der Ressourcenliste jedes Threads erstellen wir eine zusammengeführte Liste namens
CountedResourceList, die die<resource-id, total occurrence count of that id>in absteigender Reihenfolge der Zählungen speichert. Dies dauert O (rt * log (rt)) Zeit. Das Warum? davon wird im folgenden Beispiel erklärt. In derselben Iteration erstellen wir eine HashMap, so dass wir in O (1) herausfinden können, in welche Thread-Liste diese Ressourcen-ID geschrieben werden soll (basierend auf der Idee von Invertierter Index für diejenigen, die sich damit identifizieren können. - Als nächstes erstellen wir eine Matrix namens
SortedListMatrix- von t Zeilen und r Spalten. In dieser Matrix beginnen wir damit, die Resource-IDs vonCountedResourceListin die Zeile dieses Threads zu platzieren, die ursprünglich diese maximal auftretende Ressourcen-ID enthielt. Auf diese Weise werden die Ressourcen-IDs in der Reihenfolge der am häufigsten vorkommenden ausgegeben. - Um beim Einfügen von Ressourcen-IDs zu helfen, erstellen wir auch ein
int[t] FreeColumnCount, das die Anzahl der freien Spalten für jeden Thread festhält. Da der Thread mit weniger freien Slots die Möglichkeit hat, die Ressourcen-ID im Konfliktfall zu verschieben, wird eine Ressourcen-ID zuerst in der Zeile mit den wenigsten freien Slots für die Threads mit dieser Ressourcen-ID gefüllt. - Ausgehend von der 0. Spalte des ersten Threads, der die höchste auftretende Ressourcen-ID enthält, wählen wir die Position für die nächste ID aus, die mit den Formeln
row = GetRowForResource(id) in the HashMap, and column = (column+1)%reingefügt werden soll. Wenn die resultierende Spalte in einer Zeile belegt ist, nehmen wir den nächsten nicht belegten Spaltenwert durch Iterieren mit derselben Formel des Spaltenwerts, ohne die Zeile zu ändern. Daher werden -Spalten umbrochen und Zeilen werden aus der HashMap ermittelt, so dass eine Ressourcen-ID in die richtige Liste und an den am wenigsten widersprüchlichen Ort geführt wird. - Nachdem diese Matrix vollständig ausgefüllt wurde, beginnen Sie mit der 0. Zeile und weisen die Zeilen jedem Thread als ihre neue am wenigsten in Konflikt stehende Ressourcenliste zu.
Attn: Ich habe die Komplexität einiger Schritte intermittierend erwähnt, werde aber bald mit der Komplexität der gesamten Laufzeit aktualisieren. Für den Moment versuche ich, einen Algorithmus zu finden, der korrekt ist.
Ein Beispiellauf
Ursprüngliche Annahmen und Definitionen:
- Anzahl der Threads = t , beginnend mit Thread 0 bis t-1
- Anzahl der Ressourcen für jeden Thread = r
- Die Ressourcen für die Vorbereitung der Ressourcenliste für Threads sind & gt; = r
Beginnen wir mit einem Fall von t = 4. T0 = {4, 3, 5}, T1 = {1, 2, 6}, T2 = {3, 1, 2}, T4 = {2, 7, 1}. Jetzt weiß ich, dass diese Liste keine Konflikte hat. Es sollte einen Vorverarbeitungsschritt geben, der herausfindet, ob überhaupt eine Neuanordnung vorgenommen werden sollte. Zum Beispiel, wenn die Listen bereits die möglichen Mindestkonflikte haben ODER wenn es keine Konflikte gibt, sollten die Listen so zurückgegeben werden, wie sie sind. Dennoch, lassen Sie uns den Pseudocode in Aktion sehen.
Zuerst lesen wir alle Ressourcen in allen Listen und legen sie in einzelne Buckets von Ressourcen-IDs. Mit Zählsortierung wird dies ein linearer Schritt, der O (tr + konstant) verwendet Zeit. Da jedoch nur die Ressourcen-IDs gezählt werden, müssen wir Merge Sort weiter verwenden, um die IDs zu sortieren die Reihenfolge des abnehmenden Auftretens. Dieser Schritt dauert O ((rt) log (rt)) . Das Ergebnis ist eine Liste oder IDs in absteigender Reihenfolge des Auftretens sortiert -
CountedResourceList= & lt; 3 mal, id 1 & gt ;, & lt; 3 mal, id 2 & gt ;, & lt; 2 mal, id 3 & gt ;, & lt; 1 mal jeweils ids 4, 5, 6, 7 & gt;
Während derselben Iteration erstellen wir auch die HashMap und das FreeColumnCount -Array.
Als Nächstes erstellen wir das SortedListMatrix , das beginnend mit row = ersten Thread gefüllt wird, um die maximal auftretende Ressourcen-ID zu enthalten (durch Aufruf von GetRowForResource (id)) , Spalte = 0 . Die Matrix ist zunächst leer und wird dann folgendermaßen gefüllt:
Die Laufzeitkomplexität des obigen Schritts ist O (rt) .
Wenn die Matrix vollständig belegt ist, wird T0 die Zeile 0 als Ressourcenliste zugeordnet, T1 als Zeile 1 ...
Ich kenne keine Algorithmen. Ein Ansatz mit dem Verständnis, dass es in Ordnung ist, die Sequenz neu zu ordnen, wäre - Sperren zu haben, die jede der Ressourcen darstellen.
Ein Thread beim Zugriff auf eine Ressource erhält die entsprechende Sperre für diese Ressource. Wenn ein anderer Thread auf dieselbe Ressource zugreifen möchte, plant er den Zugriff mit dem nächsten neu. Zum Beispiel kann T1 auf R1 zugreifen. Wenn T2 auch Zugriff auf R1 benötigt, kann T2 stattdessen den Zugriff für R1 mit say-Zugriff für R2 umplanen (wechseln) und dann R1 nehmen, vorausgesetzt T1 ist damit erledigt.
Tags und Links algorithm parallel-processing sorting