\(Problemstellung
Jedes Element einer n-elementigen Liste soll mit allen anderen Elementen dieser Liste verglichen bzw. als Pärchen betrachtet werden. Der Vergleich der Elemente findet regelmäßig unter weichen Echtzeitanforderungen statt und es können jederzeit neue Elemente hinzukommen oder entfernt werden. Jedes Element hat einen eindeutigen Index bzw. Identifikator. Der Vergleich der Elemente soll auf mehrere Rechner verteilt werden.
Abgrenzung
Der hier vorgestellte Verteilungsalgorithmus verteilt und repliziert die Elemente der Liste auf mehrere Rechner so, dass jede Kombination zweier Elemente mindestens einmal auf mindestens einem der Rechner vorkommt. Es wird angenommen, dass jede Kombination aus zwei Elementen - jedes Pärchen - gleich wahrscheinlich zu einem benötigten Ergebnis führt. Der Algorithmus verteilt und repliziert die Elemente ohne Berücksichtigung der konkreten Vergleichsoperation. Jede Betrachtung eines Pärchens erfolgt unabhängig von den anderen Pärchen bzw. Betrachtungen.
Die Anzahl der Elemente und die Anzahl der Replikationen, die pro Rechner gehalten werden müssen, ist unter diesen Bedingungen minimal. Der Algorithmus stellt so einen Weg dar, die räumliche Lokalität der Elemente bzw. entsprechender Replikationen optimal auszunutzen. Der Algorithmus ermöglicht außerdem, dass jede Kombination der Elemente genau einmal von einem Rechner betrachtet wird, also eine optimale Aufteilung der $n \choose 2$ Vergleichsoperationen/Betrachtungen zwischen den Rechnern. Die Verteilung erfolgt anhand der Indizes bzw. Identifikatoren der Elemente und ist mit Bezug auf die Anzahl der Rechner deterministisch. Der vorgestellte Algorithmus kann als Zuordnungsfunktion für eine verteilte replizierende Hashtabelle verstanden werden. Jedes Bucket beinhaltet eine Menge an Elementen die mit den Elementen anderer deterministisch ermittelbarer Buckets die gesuchten Pärchen bilden.
Der Algorithmus ist kein Mechanismus im Sinne von "divide and conquer" da eine genau bekannte Anzahl an Problemen nämlich $n \choose 2$ lediglich auf unterschiedliche Rechner aufgeteilt wird. Die Anzahl der vorzunehmenden Operationen sinkt dadurch nicht, lediglich die Anzahl der Elemente pro Rechner und der Kommunikationsaufwand zwecks Replikation sind optimal.
Vorläufige Überlegungen:
Wir haben $p$ Rechner zur Verarbeitung zur Verfügung. Es gibt $n$ Elemente und entsprechend $n \choose 2$ Kombinationen, die betrachtet werden sollen. Im Folgenden beginnen Indizes immer mit 0\) :).
Bei einer Menge $M$ mit $n$ Objekten
$$M_n=\{o_0,o_1,...,o_{n-1}\}$$
ergibt sich die Menge $K_n$ mit den Kombinationen
$$K_n=\{k_0=(o_0,o_1),k_1=(o_0,o_2),k_z=(o_x,o_y),...,k_{{n \choose 2}-1}=(o_{n-1},o_{n-2})\}$$
Für $k_z=(o_x,o_y)$ mit $x>y$ gilt:
\begin{aligned}
z_{xy}&={-{\frac{y^2}{2}}+\left(n-{\frac{3}{2}}\right)\,y+x-1}\\
y&=n-\left \lceil {\frac{\sqrt{-8\,z+4\,n^2-4\,n+1}}{2}}+{\frac{1}{2}} \right \rceil\\
x&={\frac{2\,z+y^2-2\,n\,y+3\,y+2}{2}}\\
\end{aligned}
Wenn man sich $K_6$ als Matrix mit $z$ als Zellenwert, $x$ als Spaltennummer und $y$ als Zeilennummer vorstellt, dann erhält man also Folgendes:
$$K_6=\begin{pmatrix}\mbox{ .}&0&1&2&3&4\cr \mbox{ .}&\mbox{.}&5&6 &7&8\cr \mbox{ .}&\mbox{.}&\mbox{.}&9&10&11\cr \mbox{ .}&\mbox{.}&\mbox{.}&\mbox{.}&12&13\cr \mbox{ .}&\mbox{.}&\mbox{.}&\mbox{.}& \mbox{.}&14\cr \mbox{ .}&\mbox{.}&\mbox{.}& \mbox{.}&\mbox{.}&\mbox{.}\end{pmatrix}$$
Wenn wir also $n$ kennen, dann können wir jeder einzigartigen Kombination aus den Objekten $o_x$ und $o_y$ einen Index $z_{xy}$ zuordnen. Wenn wir $n$ und den Index $z$ einer Kombination kennen, kennen wir die Indizes $x$ und $y$ der Objekte dieser Kombination. Mit diesen Informationen können wir schon eine einfache Verteilung von Kombinationen auf verschiedene Rechner vornehmen. Wir teilen einfach die Anzahl der Kombinationen $n \choose 2$ durch die Anzahl der Rechner $p$ und ordnen jedem Rechner einen Teil der Kombinationen zu. Dies führt allerdings noch zu keiner optimalen Verteilung, da die meisten Rechner fast alle Objekte vorgeladen haben müssen. Eine Veranschaulichung mit $p=3$ und $n=6$:
[/latex]Es folgt der "vorläufige" Algorithmus als Pseudocode:
Code: Alles auswählen
int p;//=Prozessor Anzahl
Object[] objects;//=Elemente
int n;//=Anzahl der Elemente
//Binomialkoeffizient(n,2)
int kombinationen=n*(n-1)/2;
//Vergleichsoperation
void operation(Object o1, Object o2) { /*...*/ }
//Pro Prozess
int indexP;//=Prozessor Index
void run() {
//Index der ersten zu verarbeitenden Kombination
int startZ=kombinationen/p*indexP;
int z=startZ;
//Index der letzten zu verarbeitenden Kombination
int endZ=kombinationen/p*(indexP+1);
int startY=n-ceil(sqrt(-8*startZ+4*n*n+1)*0.5+0.5);
int startX=(2*startZ+startY*startY-2*n*startY+3*startY+2)*0.5;
for(int y=startY;y<n;y++) {
for(int x=startX;x<n;x++) {
if(z>=endZ)
return;
operation(objects[x],objects[y]);
z++;
}
startX=y+2;
}
}
Um das zu verbessern kann man statt die einzelnen Kombinationen zu verteilen im einfachen Fall $p \in\{1,3,6,10,15,21,28,...\}=\{x \in \mathbb{N} \wedge x>1 \mid f(x):={x \choose 2} \}$ jedem Rechner einen rechteckigen Sektor in der "Kombinationsmatrix" zuordnen:
Die Kanten der Sektoren sind Teilintervalle des Intervalls $[0...n-1]$. Man kann also jedes Objekt einem Teilintervall zuordnen. Um die Zuordnung der Objekte zu Teilintervallen zu erleichtern kann man die Zuordnung auch gut über ein gleichverteiltes Abtragen der Objekt-IDs o.Ä. auf einen vordefinierten Intervall lösen. Jedes Objekt wird nun allen Rechnern zugeordnet deren Sektoren den entsprechenden Teilintervall als Kante haben. Es ergibt sich bei den Objekten $\{\alpha, \beta, \gamma, \delta, \epsilon\}$ also $n=5$, $p=6$ und entsprechend den Sektorkanten/Teilintervallen $\{A, B, C, D\}$ folgendes Bild, Rechner = Knoten:
Die Kombinationen der Objekte eines Teilintervalls können dann mit dem in "Vorläufige Überlegungen" genannten Algorithmus zwischen den Rechnern verteilt werden.
Alternativ ist eine weitere Aufteilung der Elemente möglich. Die Elemente werden ähnlich wie bei der ersten Aufteilung anhand von Teilintervallen Sektoren zugeordnet. In diesem Fall muss es so viele Sektoren geben, dass diese gleichmäßig unter den Rechnern aufgeteilt werden können. So werden die Elemente anhand der Sektoren in Gruppen aufgeteilt. Jeder Rechner bekommt entsprechend ein oder mehrere Gruppen zugeordnet. Die Elemente dieser ihm zugeordneten Gruppen muss der Rechner dann immer mit den Elementen der gleichen Gruppe und mit den Elementen anderer Gruppen vergleichen. Die Zuordnung der zu prüfenden Gruppenkombinationen erfolgt mit dem vorläufigen Algorithmus.
Es folgt eine graphische Darstellung mit den Objekten $\{\alpha, \beta, \gamma, \delta, \epsilon\}$ und $p=6$. Es wird nur die in der vorherigen Darstellung als $A$ bezeichnete Sektorkante mit den zugehörigen Knoten 0, 1 und 2 angezeigt. Die Objekte liegen in diesem Fall alle in diesem Teilintervall.
Mit einer solchen zusätzlichen Aufteilung sind je nach Anwendungsfall die Vergleichsoperationen effizienter auszuführen.\)
Praktische Anwendung
Den vorgestellten Verteilungsmechanismus habe ich für JBullet implementiert. Dabei wird die Verteilung nur in sofern berücksichtigt, dass jeder Rechner eine kleinere Menge an zu verarbeitenden Objekten innehat als ohne die Verteilung. D.h. bei 3 Rechnern und 1000 Objekten muss jeder Rechner noch ~667 und bei 6 Rechnern noch ~500 Objekte verarbeiten (2 durch Anzahl der Teilintervalle). Hinzu kommt der Austausch der Daten während der Kollisionsauflösung. Ich gehe dabei so vor, dass erst die Ergebnisse der "global einzigartigen" Kombinationen zwischen den Rechnern ausgetauscht werden und danach alle restlichen Kombinationen ohne weitere Kommunikation redundant auf jedem Rechner verarbeitet werden. Bei meinen Mickey-Maus-Benchmarks mit sehr vielen immer neu auftretenden Kollisionen konnte ich so "in der Cloud" die Ticks pro Sekunde mit der Anzahl der Rechner erhöhen (p=1 -> ~15, p=3 -> ~20, p=6 -> 25).
[scaled_img=500]http://zfx.info/download/file.php?id=1742&mode=view[/scaled_img]
Mit einer GPU o.Ä. kann man sicher bessere Steigerungen erzielen. Das "Deaktivieren" unbewegter Objekte habe ich in meinem Test außerdem auch nicht berücksichtigt, das bringt in vielen Fällen ja einen gehörigen Performanceboost. Das ist bei verteilter Verarbeitung viel schlechter lösbar. Mir ging es bei den Tests vor allem darum, ob es sich überhaupt lohnen kann. Ich war positiv überrascht, als ich dann tatsächlich Verbesserungen feststellen konnte.
Andere Anwendungsfelder, die ich mir evt. vorstellen kann sind Sachen wie verteiltes Complex Event Processing oder ganz allg. verteilte Vergleichsoperationen. Falls ihr eine Idee habt, könnt ihr ja den Algorithmus gerne mal ausprobieren.
Viele Grüße
Christian
