www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Mathematische Beschreibung - Array verteilen


Autor: Jansi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Jansi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Alexander Liebhold (lippi2000)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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
mit


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

Autor: Alexander Liebhold (lippi2000)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kleiner Fehler, es gilt:

Autor: Alexander Liebhold (lippi2000)
Datum:

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

Autor: Jansi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Alexander Liebhold (lippi2000)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
OK, dann sollte es so gehen:

Autor: Alexander Liebhold (lippi2000)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.