Mathematische Beschreibung - Array verteilen

[Jansi (Gast)]

Hallo,

für eine Berechnung nutze ich einen Microcontroller und 5 FPGAs, die 
"rechnen". Es kommt ein Block mit Aufgaben rein und muss auf die FPGAs 
verteilt werden. Alle Aufgaben haben in etwa die gleiche Lauf- bzw. 
Rechenzeit. Ich verteile die Aufgaben momentan so, dass ich in einer 
While Schleife über das Array itteriere und 5 eigenständige Arrays 
erstelle für jeden FPGA. Die FPGAs bekommen dann das Array und liefern 
dann die Ergebnisse.

Doch nun suche ich eine formale Beschreibung für das, was ich mache. Ich 
will das jetzt mal etwas verdeutlichen. Ich habe 52 Aufgaben.

FPGA 1-2 bekommen 11 Aufgaben
FPGA 3-5 bekommen 10 Aufgaben

Doch wie beschreibe ich so etwas formal?

[Detlef _. (detlef_a)]

Gatt charts bieten sich da an. Ein Satz von Rechnungen, die voneinander 
abhängen und auf ein Netzwerk von Prozessoren verteilt werden müssen 
läßt sich als matching eines gerichteten Gaphen (die Rechnungen) auf 
einen ungerichteten Graphen darstellen.

Cheers
Detlef

[Jansi (Gast)]

Alle Aufgaben, die zu berechnen sind, sind voneinander unabhängig. Es 
geht mir wie gesagt nur um die formale Beschreibung der Verteilung mit 
der While Schleife.

[Alexander L. (lippi2000)]

Also ganz schlau werd ich aus deinem Text aber nicht....

Also du teilst die 52 Aufgaben nacheinaander in 5er-Gruppen die du dann 
an bei jedem Durchlauf an 5 FPGA's schickst!?
Also 11 Durchgänge:

Durchgang 1-10 --> 5 FPGA's belegt
Durchgang 11 --> 2 FPGA's belegt

D.h. FPGA 1 bekommt die 1.Aufgabe und danach jede 5., so lange bis die 
Maximalanzahl der Aufgaben erreicht ist.

Also ich würde sagen:

n = Schleifenzähler
x = Anzahl der parallelen Stufen
h = Nummer der parallelen Stufe
G = Gesamtanzahl der Aufgaben

$$FPGA\;h = \begin{cases} n*x+h, & \text{wenn }\frac{G}{n*x}\geq 1 \\ n*x+h, & \text{wenn}\lbrack\frac{G}{n*x}<1\rbrack\land \lbrack (G-((n-1)*x+h))>0\rbrack \\ \text{keine}, & \text{sonst} \end{cases}$$

mit

$$n \epsilon N \lbrack \text{0,}\lceil \frac{G}{x}\rceil \rbrack$$

An deinem Beispiel heißt das:

x = 5
G = 52
n = [1,11] "wegen Aufrunden!"

Im 1.Durchlauf bekommt dein FPGA Nummer 3 die Aufgabe 0*5+3 = 3
Im 4. Durchlauf bekommt FPGA Nummer 2 die Aufgabe 4*5+2 = 22
Im 11.Durchlauf bekommt FPGA Nummer 1 die Aufgabe 10*5+1 = 51
Im 11. Durchlauf bekommt FPGA Nummer 3 keine Aufgabe.

Gruß Alexander

[Alexander L. (lippi2000)]

Kleiner Fehler, es gilt:

$$n \epsilon N \lbrack \text{0,} \lceil \frac{G}{x} \rceil -1 \rbrack$$

[Alexander L. (lippi2000)]

Und noch eine Kleinigkeit:  Im zweiten case muss es bei der 
UND-Verknüpfung natürlich "größer-gleich" heißen.

[Jansi (Gast)]

Hi,

danke für deine Hilfe. Auf den ersten Blick sieht das ganz gut aus. Doch 
dann ist mir eine Kleinigkeit aufgefallen:

Die Schleife fängt ja bei 0 an und wird bei jedem durchlauf 
inkrementiert. Aber wenn ich mir die Bedingungen ansehe, dann habe ich 
bei dem Bruch n*x stehen. Somit würde ich bei n=0 durch eine 0 teilen.

Als ich die Verteilung realisiert habe, dachte ich ehrlich gesagt an 
irgendwie an eine Kindergärtnerin, die Süßigkeiten verteilt. Die Kinder 
haben sich im Kreis um die Dame aufgestellt und im Kreis verteilt sie 
die Süßigkeiten, bis der Beutel leer ist.

Diese Verteilung würde ich sehr gerne ohne irgendwelchen Pseudocode 
beschreiben, also rein formal.

[Alexander L. (lippi2000)]

OK, dann sollte es so gehen:

$$FPGA\; h= \begin{cases} (n-1)*x, & \text{wenn }\frac{G}{n*x} \geq 1 \\ (n-1)*x, & \text{wenn }\lbrack\frac{G}{n*x}<1\rbrack\land\lbrack(G-((n-1)*x+h)\geq 0\rbrack \\ \text{kein}, & \text{sonst} \end{cases} \;\text{ mit }n\epsilon N\lbrack\text{1,}\frac{G}{x}\rbrack$$

[Alexander L. (lippi2000)]

Du kannst natürlich auch mit folgenden Ablauf vorgehen:

1. Aufgabenspeicher leer?
       JA --> verbleibe bei 1.
     NEIN --> weiter zu 2.

2. Aufgabe an FPGA schreiben

3. Nächster FPGA

4. Ist FPGA-Nr. 6?
       JA --> springe zu FPGA-Nr.1
     NEIN --> verbleibe bei aktuellen FPGA

5. Gehe zu 1.


Das Ganze natürlich noch viel ausgefeilter, da man sehen muss wieviele 
Aufgaben im Speicher stehen, wann die FPGA's fertig sind usw.