Kleiner Algorithmus zur Aufteilung von N-zu-N Problemen

Hier können Artikel, Tutorials, Bücherrezensionen, Dokumente aller Art, Texturen, Sprites, Sounds, Musik und Modelle zur Verfügung gestellt bzw. verlinkt werden.
Forumsregeln
Möglichst sinnvolle Präfixe oder die Themensymbole nutzen.
Antworten
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4254
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Kleiner Algorithmus zur Aufteilung von N-zu-N Problemen

Beitrag von Chromanoid »

Ich bin mir nicht sicher ob der Algorithmus wirklich etwas taugt, ob es ein alter Hut ist oder ob es einfach bessere Lösungen für das Problem gibt. Auch bei der mathematischen Notation bin ich mir etwas unsicher. Ich würde mich daher sehr über Kommentare jedweder Art freuen. Das Zeug ist während meiner Diplomarbeit entstanden.

\(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;
	}
}
\(Verteilungsalgorithmus
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
Zuletzt geändert von Chromanoid am 13.12.2016, 21:35, insgesamt 21-mal geändert.
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Kleiner Algorithmus zur Aufteilung von N-zu-N Problemen

Beitrag von Alexander Kornrumpf »

Moin,

kannst du das LaTex in deinem Beitrag noch fixen oder ein .pdf hochladen?

Es würde der Darstellung sicher auch helfen wenn du es im Vergleich zu Map-Reduce beschreiben würdest, dann hat das Gehirn einen bekannten Anknüpfungspunkt.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Kleiner Algorithmus zur Aufteilung von N-zu-N Problemen

Beitrag von Krishty »

Alexander Kornrumpf hat geschrieben:kannst du das LaTex in deinem Beitrag noch fixen oder ein .pdf hochladen?
Was muss gefixt werden?
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Kleiner Algorithmus zur Aufteilung von N-zu-N Problemen

Beitrag von Alexander Kornrumpf »

Krishty hat geschrieben:
Alexander Kornrumpf hat geschrieben:kannst du das LaTex in deinem Beitrag noch fixen oder ein .pdf hochladen?
Was muss gefixt werden?
Ich sehe den Code und würde gerne den Output sehen.

EDIT: Mein Fehler. Javascript war aus.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Kleiner Algorithmus zur Aufteilung von N-zu-N Problemen

Beitrag von Krishty »

War bei mir am Anfang auch. Als Hinweis für die anderen: JavaScript für cdn.mathjax.org aktivieren.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4254
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: Kleiner Algorithmus zur Aufteilung von N-zu-N Problemen

Beitrag von Chromanoid »

Danke für den Hinweis :) Geht Internet überhaupt noch ohne JavaScript :)?

@Alexander: Ich schraube heute morgen abend noch mal ein bisschen am Artikel und baue neben Codebeispielen auch eine Abgrenzung zu MapReduce ein. So kann man tatsächlich nur wenig damit anfangen.
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4254
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: Kleiner Algorithmus zur Aufteilung von N-zu-N Problemen

Beitrag von Chromanoid »

So habe den Beitrag noch ein bisschen überarbeitet. Für den "vorläufigen" Algorithmus ist jetzt auch ein Codebeispiel dazugekommen.
Antworten