Algorithmus für die Ablaufplanung in einer ALU

[ollih]

Hallo,

Leider sind meine Informatik Kenntnisse nich so gut da ich nur einpaar Informatikvorlesungen als Nebenfach hatte.

Im Allgemeinen brauch ich eine Ablauplanung für recht einfache Berechnungen. Der Prozessor den ich verwende kann z.b. nur 3 Multiplikationen auf einmal und sechs Additionen..... ich muss also schauen, dass ich pro Rechenschritt nicht die Ressourcen überschreite und die Ressourcen die insgesamt da sind für die Lösung des gesamten Problems möglichst gut verteile.

Ein einfaches Beispiel:

Calculation = ( ( a * b ) + ( c + d ) / e ) / f * Cos[g]

Diese Rechnung will ich nun durch einen Algorithmus schicken der mir dann eine Ablaufplanung ausgiebt.

Auf den ersten Blick sieht man, dass z.b. im ersten Zeitschritt die Multiplikation von a*b , die Addition von c+d und der Cosinus von g berechnet werden könnten.

Von Hand ist eine Ablaufplanung in der Art denkbar:

First time step:

1a: a * b = S1a

1b: c + d =S1b

1c: Cos[g] = S1c

Second time step:

2a: S1b / e = S2a

Third time step:

3a: S1a + S2a = S3a

Fourth time step:

4a: S3a * S1c = S4a

Fifth time step:

5a: S4a / f = FINISED

Was hier natürlich wichtg für alle Berechnungen dieser Art ist, dass mein Prozesser nur beschränkte Ressourcen hat und auch die unterschiedlichen Berechnungen unterschiedlich viel Zeit brauchen. Ein Cosinus dauert bei mir z.b. ca. 30 Clocks... eine Addition nur 5 Clocks.

Das sind wohl erstmal genügend Anregungen zu meinem Problem, das natürlich schon sehr oft gelöst wurde... leider noch nicht von mir. Über einpaar Hilfestellungen würde ich mich freuen. Vielleicht gibt es ja schon diverse Tools die das können. Ich verwende für fast alles was ich mache Mathematica.

Im Anhang noch eine kleine graphische Ausgabe für das Beispiel, die automatisch mit Mathematica generiert wurde.

Wenn ich sowas hätte angepasst auf meine Ressourcen wäre das super.

Bearbeitet 24. September 2009 von ollih

[Crush]

Also ein guter Beschleunigungstrick ist es, die Divisionen in Multiplikationen umzuwandeln. Also anstatt a/b berechne eine Variable x = 1/b und rechne nachher einfach a*x. Das bringt schon etwas. Den Cosinus könntest Du nur beschleunigen, wenn Du Tabellen einsetzen könntest, damit wäre das allerdings recht ungenau. Was Du mit Deiner "Ablaufplanung" bezwecken willst, verstehe ich nicht, weil das zur Beschleunigung nichts beiträgt. Da es sich nicht um eine rekursive Formel handelt, werden Deine Systemresourcen ohnehin optimal verwendet. Du könntest sicher noch etwas schneller werden, wenn Du mit möglichst dem Wertebereich genügend großen Datentypen im Ganzzahlbereich arbeiten würdest. Also alles möglichst auf int32 oder int64 Datentypen mit fixed-point Berechnungen auslegen könntest und bestenfalls für den cos eine Transformation notwendig ist, dürfte das ganze noch einmal deutlich schneller werden.

Bearbeitet 24. September 2009 von Crush

[flashpixx]

Also ein guter Beschleunigungstrick ist es, die Divisionen in Multiplikationen umzuwandeln. Also anstatt a/b berechne eine Variable x = 1/b und rechne nachher einfach a*x.

Ah ja und was ist bitte 1/b? Ist das keine Division? Die Annahme, dass Multiplikationen schneller auf CPU Ebene sind ist in der heutigen Zeit nicht mehr relevant.

Den Cosinus könntest Du nur beschleunigen, wenn Du Tabellen einsetzen könntest, damit wäre das allerdings recht ungenau.

Ich will jetzt nur mal den Hinweis auf die Taylorentwicklung zu den trigonometrischen Funktionen hinweisen und auch dass die einzelnen Taylorfolgenglieder aus Elementarfunktionen wie Faktultät (Multiplikation) und Division aufgebaut sind. Das ganze wird dann als Reihe mit alternierendem Vorzeichen gegen unendlich summiert....

Zur "effizienten" Lösung kannst Du die Idee aus der Parallelisierung über Eliminationsbäume nehmen. Schau Dir mit Hilfe dieser Bäume an, wie für einen Schritt Deine Berechnung durchgeführt wird. Teilbäume, die parallele Zweige und gemeinsame Wurzel haben, lassen sich dann auch parallel berechnen. Im optimalsten Fall kannst Du 6 Additionen parallel durchführen und diese dann mit den 3 Multiplikationen zusammenführen, bevor der nächste Schritt kommt.

Ich denke Du wirst hier nicht um eine theoretische Betrachtung des Problems herum kommen. Ein Tool, dass Dir die fertige Lösung liefert gibt es nicht. Das Problem ist generell nicht aus der Informatik, sondern würde ich eher in der parallelen Numerik bzw Optimierung sehen

Bearbeitet 24. September 2009 von flashpixx

[ollih]

Ich habe eine eigene CPU in Hardware mit VHDL realisiert.

Ich möchte mathematische Modelle in Hardware umsetzen. Also in VHDL.

Die mathematischen Modelle sind irgendwelche Berechnungen.

Wie bei dem Beispiel hängt die Anzahl der Berechnungsschritte davon ab, wieviele Zwischenergebnisse ich benötige und wieviele Berechnungen ich gleichhzeitig durchführen kann.

Was ich habe sind die Modelle in Mathematica... aber die will ich natürlich nicht von Hand in Hardware implementieren sondern das soll ein Programm machen, das dann Rücksicht auf die Ressourcen der CPU nimmt.

[flashpixx]

Was ich habe sind die Modelle in Mathematica... aber die will ich natürlich nicht von Hand in Hardware implementieren sondern das soll ein Programm machen, das dann Rücksicht auf die Ressourcen der CPU nimmt.

Letztendlich wäre das eine Art Kompilierentwicklung. Um das wirklich effizient zu gestalten wird dafür wohl eine Menge an theoretischen Grundlagen durchzuführen sein, vor allem wenn Du ein allgm gültiges Modell haben willst.

Letztendlich wird sich das aber in den Grundstrukturen an genanntem anlehnen. Eine "Pauschallösung" wird es da nicht geben. Ich weißt aber jetzt auch nicht was Du hier als Antwort erwartest? Eine Lösung für Dein Problem?

[Crush]

@flashpixx: natürlich bringt das Invertieren des Divisors nur dann etwas, wenn e und f sich nicht ständig ändern. Ich hab das halt nicht erwähnt, weil ich dachte, wenn es in Frage kommt wird er es schon verstehen und verwenden können. Ich selbst hab ja keine Ahnung, was die Variablen darstellen sollen. Sind sie jedoch konstant ist die Division so nur einmal durchzuführen. Die Multiplikation ist schneller. Andere Datentypen sind schneller. Der Geschwindigkeitsvorteil in Taktzyklen ist der Frage nach sehr wohl relevant, weil ollih sogar den Clock-Vergleich aufführt. Wenn das keine Rolle spielt, warum sollte er es dann tun?

[flashpixx]

Ich selbst hab ja keine Ahnung, was die Variablen darstellen sollen. Sind sie jedoch konstant ist die Division so nur einmal durchzuführen.

Wenn ich die angegebene Funktion nehme und soll genau diese einmalig effizient, d.h. mit möglichst hohem Parallelisierungsgrad berechnen, dann ist es eher hinderlich eine Division in einer Multiplikation auszudrücken, denn die Multiplikation würde 2 Taktzyklen benötigen, die auch keinen Parallelisierungsgrad zu lassen.

Die Multiplikation ist schneller. Andere Datentypen sind schneller. Der Geschwindigkeitsvorteil in Taktzyklen ist der Frage nach sehr wohl relevant, weil ollih sogar den Clock-Vergleich aufführt. Wenn das keine Rolle spielt, warum sollte er es dann tun?

Ein eine einzelne Option innerhalb eines Taktes gesehen fällt nicht ins Gewicht. Selbst eine Wurzeloperation ist analog zu vergleichen mit einer Addition. Wenn ich die gegebene Funktion nehme und diese Funktion 10^9 mal ausführen, dann spielt die Zeit einer einzelne Operation keine Rolle, sondern wie "gut" die Parallelisierung der Operationen ausgenutzt wird.

Ich verweise auf Amdahlsches Gesetz ? Wikipedia

[ollih]

hi flashpixx,

erwarte hier keine lösung für mein problem. bisschen inspiration und infoquellen. du hast recht suche wohl eher sowas wie einen compiler.

ich kann mich noch dunkel an informatik 1 bzw TI erinnern. da hatten wir mal sowas wie.. ablaufplanung, ressourcen kosten etc.

was ich suche ist vielleicht ein tip für ein tool das mir möglichst vie arbeit abnimmt. will nicht das rad neu erfinden. mein prozessor ist recht spartanisch.

kann nur die grundrechenarten und sinos und cosinus.

kann mir einfach nicht vostellen dass noch niemand ein tool geschrieben hat das genau das macht was ich such. will ja nicht gleich den code generiert haben. mit einem guten ablaufplan kann ich das dann ja selber implementieren.

[flashpixx]

was ich suche ist vielleicht ein tip für ein tool das mir möglichst vie arbeit abnimmt. will nicht das rad neu erfinden. mein prozessor ist recht spartanisch.

kann nur die grundrechenarten und sinos und cosinus.

kann mir einfach nicht vostellen dass noch niemand ein tool geschrieben hat das genau das macht was ich such. will ja nicht gleich den code generiert haben. mit einem guten ablaufplan kann ich das dann ja selber implementieren.

Sicher nicht, denn fast alle diese Optimierungsprobleme sind NP-vollständig, somit sind die Tools mit guten Approximationsalgorithmen aufgebaut. Es gibt z.B. entsprechende Tools, die in den VHDL Systemen implementiert sind, aber diese kosten sehr viel. Dein Problem ist recht speziell - aber wie ich finde extrem interessant - ich würde da mit Graphentheorie / Graphenalgorithmen arbeiten bzw verschiedene Algorithmen aus der parallelen Numerik "klauen".

So wie ich es ja geschrieben hatte könntest Du Dein angegebenes Problem wie gesagt ja darüber Lösen, dass Du eben einen entsprechenden Baum aufbaust und schaust welche Zweige parallel verarbeitet werden können, den cos kannst Du durch die Taylorentwicklung annähern bis er dann entsprechend hinreichend gut ist. Wenn Du ein paar 1000 Glieder berechnest und keine allzu großen Datentypen hast, sollte das schon gut sein.

Ich würde ja auch noch überlegen, ob Du ein theoretisches Modell benötigst oder ob Du eine praktische Implementierung brauchst. Bei der Praxis kann man sich ggf durch Approximationen oder wie Crush schon schrieb über Lookup-Tables realisieren. Aber dieses wäre dann eben durch die Technik bedingt

[ollih]

danke für dein interesse flashpixx,

mein problem ist garnicht so umfassend wie es vielleicht auf den ersten blick erscheint.

also zuerst mal hab ich schon in vhdl einen prozessor realisiert.

der macht sowas wie:

=========================================================

(achtung pseudocode)

WHEN RECHNUNG1 =>

add_a(0) <= 5;

add_b(0) <= 3;

mul_a(0) <= 5;

mul_b(0) <= 5;

mul_a(1) <= 2;

mul_b(1) <= 3;

--==========

nextstate <= RECHNUNG2;

state <= RECHNEN;

multiplikationen <= 2;

additionen <= 1;

when RECHNUNG2 =>

add_a(0) <= mulResult(0);

add_b(0) <= mulResult(1);

--==========

nextstate <= RECHNUNG3;

state <= RECHNEN;

additionen <= 1;

... etc.

=========================================================

Also ich hab eine Statemachine die sequenziell meine Berechnungen macht.

Die muss ich selber schreiben... und mir natürlich überlegen was man erst addieren muss um es anschliessen zu multiplizieren usw......

Im Status "Rechnen" werden die Operanden dem Rechenwerk übergeben. Wie man hier in dem Beispiel sieht kann ich mehrere Multiplikationen an das Rechenwerk schicken. Da ich den Prozessor selber entworfen hab kann ich das einstellen wie ich will.. also ich kann das Array mul_a und mul_b so gross machen wie ich lust habe und muss dann natürlich mulResult anpassen.

Cosinus/Sinus kann ich auch rechnen. Das geht mit einem Cordic. Keine Ahnung wie der genau funktioniert aber muss ich mich auch nicht drum kümmern.

Um den Code da oben einfach generieren zu können muss ich nur ein Tool haben, dass mir das abnimmt dann kann ich einfach alle Berechnungen in Hardware pressen.

Also irgend ein mathematisches Modell das schnell berechnet werden soll und das in einer Schleife... Stichwort Hardwarebeschleunigung.

Das mit dem Baum ist eine gute Idee. In meinem ersten Beitrag hab ich mal einen angeheftet. Falls du Mathematica kennst: TreeForm[berechnung]

ist alles was man eingeben muss.

Den Blöden Baum muss ich jetzt noch modifizieren.... da häng ich total fest.

Also genau wie du sagst was geht parallel was geht nur nacheinander. Wieviele Additionen parallel wieviele Multiplikationen..... usw.

Dann kommt natürlich noch dazu: Und das macht es auch langsam etwas kompliziert ist .. Die addition dauert 4 Clocks... die Multiplikation 5 und die Division gerade .. .50 oder so.

Momentan mache ich es mir leicht was das Problem anbelangt. Wenn eine Addition und eine Division parallel läuft dann dauert alles so lang wie die Division benötigt um durchgeführt zu werden... ist natürlich suboptimal.

Muss irgendwie rausfinden wie man vernünftig die Graphen manipuliert, vereinfacht usw... aber das ist ne ******* arbeit

ich such immer noch das spezialtool das mir das abnimmt

[flashpixx]

Das mit dem Baum ist eine gute Idee. In meinem ersten Beitrag hab ich mal einen angeheftet. Falls du Mathematica kennst: TreeForm[berechnung]

ist alles was man eingeben muss.

Da muss ich leider passen, ich kenne zwar Mathematica, aber arbeite nur mit Matlab und Maple bzw für C++ mit OpenMPI

Den Blöden Baum muss ich jetzt noch modifizieren.... da häng ich total fest.

Also genau wie du sagst was geht parallel was geht nur nacheinander. Wieviele Additionen parallel wieviele Multiplikationen..... usw.

Dann kommt natürlich noch dazu: Und das macht es auch langsam etwas kompliziert ist .. Die addition dauert 4 Clocks... die Multiplikation 5 und die Division gerade .. .50 oder so.

Das wird dann wohl ein entsprechend "gewichteter" Baum sein. Da Du ja hier unterschiedliche Zeitkosten für die Operation hast, wird das natürlich um einiges komplizierter.

Momentan mache ich es mir leicht was das Problem anbelangt. Wenn eine Addition und eine Division parallel läuft dann dauert alles so lang wie die Division benötigt um durchgeführt zu werden... ist natürlich suboptimal.

Ich würde hier erstmal von der Theorie ausgehen, d.h. stumpf annehmen alles dauert gleich lange.

Muss irgendwie rausfinden wie man vernünftig die Graphen manipuliert, vereinfacht usw... aber das ist ne ******* arbeit

ich such immer noch das spezialtool das mir das abnimmt

Ich denke nicht, dass Du so etwas finden wirst, ich weiß zwar in VHDL kann man direkt die Laufzeiten analysieren lassen (habe das mal testweise gemacht), die entsprechenden Tools, die das können, können auch optimieren, sind aber genauso wie Tools die Leiterbahnen optimieren, extrem teuer.

Schreib mich ggf mal per ICQ an, da ich in der letzten Zeit mit parallelen Algorithmen zu tun hatte, dann würde ich Dir diverse Auszüge aus meinen Scripten geben

[AndiE]

Hi,

ich meine, dass es doch im Binären eine (kanonische(?)) Normalform gibt, die da lautet:

z=y1 ODER y2 ODER y3 ODER ... ODERn

mit Yn=x1 UNDx2 UND x3 ... UND xm

wobei x, y und z auch negiert sein können.

Diese Dreiform (Negation, und, oder) könnte man evtl. auf die Regel "Punkterechnung geht vor Stichrechnung" ummodeln und vorher noch unäre Operationen wie Negation, Reziprokbildung., cos usw. ausführen.

Das ergäbe diesen Ablauf:

1. unäre Operationen

2. Multipikationen

3. Additionen

Da es vier Operationen(Addition,Multiplikation, Reziprok und Negation) gibt, muß auch das Endergebnis entsprechend behandelt werden.

Beispiel:

Um den Gesamtwiderstand von n parallel geschalteten Widerständen zu berechnen, müsste man die n Reziproke in parallelen Prozessen bilden, diese dann addieren, und von der Summe wieder das Reziprok bilden.

Schon hätte man das Ergebnis.

LG

Andre'

LG

Andre'

[flashpixx]

Diese Dreiform (Negation, und, oder) könnte man evtl. auf die Regel "Punkterechnung geht vor Stichrechnung" ummodeln und vorher noch unäre Operationen wie Negation, Reziprokbildung., cos usw. ausführen.

Was hat dies damit zu tun, dass hier Operatoren parallelisiert werden müssen, um möglichst effizient zu arbeiten?

Mit den Operatoren "and", "or", "neg" kann ich entsprechende ALU Gatter bauen, die mir eine Addition auf Bitebene durchführen, aber parallelisieren kann ich damit nicht, da ich die Latenzen der Gatter und der Bahnen berücksichtigen muss.

Vor allem wie willst Du einen Kosinus via logischer Operatoren ausdrücken?

Um den Gesamtwiderstand von n parallel geschalteten Widerständen zu berechnen, müsste man die n Reziproke in parallelen Prozessen bilden, diese dann addieren, und von der Summe wieder das Reziprok bilden.

Schon hätte man das Ergebnis.

Was hat dieses Beispiel mit dem Problem zu tun? Wenn ich n Widerstände habe, kann ich, wenn ich n Parallelprozesse erzeugen kann, den reziproken Wert parallel ermitteln und dann sogar die Summenbildung noch bis zu einem gewissen Grad parallelisieren. Wie sieht das aber aus wenn ich aus 10 Widerständen den reziproken Wert bilden muss, aber nur 2 ALUs habe?

Die Problemstellung kennt das n nicht, sondern nur die Anzahl der ALUs, wobei hier eine Division / Multiplikation langsamer ist, als eine Summe, das auch noch zu berücksichtigen ist.