Hallo,
ich bin absoluter Laie im Bereich Mikrocontroller und entwickel gerade
einen Algorithmus mit Fourier-Transformation und vielen weiteren
Operationen. Nun möchte ich die Hardware, auf der der Algorithmus laufen
soll, in Auftrag geben. Ich wurde nun nach der Komplexität des
Algorithmus gefragt bzw. auch, was die Anforderungen an den Prozessor
sind.
Ich wäre sehr dankbar, könnte mir jemand sagen, welche Spezifikationen
ich ableiten soll bzw. relevant sind.
Anmerkung: Der Algorithmus verrechnet kontinuierlich Sensorwerte die
einer festen Fensterbreite unterliegen.
Besten Dank
Wichtig dazu ist, wie du schon erwähnt hast, die Komplexität deines
Algorithmus. Diese wird in der O-Notation (Landau Notation) angegeben.
Wenn du nicht weisst, wie komplex dein Algorithmus ist, kannst du ihn
sonst einmal hier posten. Willst du dich selbst einlesen, kannst du
einmal dieses "Tutorial" lesen, in welchem Code-Beispiele angeschaut
werden: http://www.codeadventurer.de/?p=2266
Das sollte man wohl etwas pragmatischer angehen. Wirklich interessant
ist ja die Frage, wie viele Maschinenbefehle pro Sekunde braucht das
Programm? Und was brauchst du an Peripherie? AD-Wandler? USB? Wlan? ...
Erste grobe Abschätzung - du testest das Programm auf einem PC, und
überschlägst, welche Taktfrequenz erforderlich wäre.
Zweiter Schritt, du kaufst dir für 50€ eine Experimentierplatine und
überprüfst, ob deine Überschlagsrechnung wirklich hinhaut.
Und der Dritte Schritt - du implementierst Ein-Ausgabe auf der
Experimentierplatine und überprüfst, ob der MC alle Aufgaben
gleichzeitig erledigen kann.
Vielen Dank für die nützlichen Tipps.
@silsi: Die Zeitdauer ist ja wiederum abhängig von dem Prozessor mit dem
ich es berechne und wenn ich es richtig verstehe kann ich mit der Landau
Notation lediglich die Performance auf dem aktuellen System
wiederspiegeln und kann keine Aussage darüber treffen, was der Prozessor
leisten müsste. Sehe ich das richtig?
@Pragmatiker: Die Maschinenbefehle pro Sekunde wären vermutlich eine
gute Herangehensweise. Peripherie könnte ich erstmal vernachlässigen, da
sich der Hersteller darum kümmern wird.
Nochmals vielen Dank und ich schaue mal wie ich mit den Infos
weiterkomme.
Beste Grüße
Flo
Florian Lutz schrieb:> kann keine Aussage darüber treffen, was der Prozessor> leisten müsste. Sehe ich das richtig?
Nö. Denn bei Dir sollte die Problemgröße n keine Unbekannte sein!
Grobe Anhaltspunkte für die Performance kann auch eine testweise
Implementation auf dem PC liefern. Schreibt man die halbwegs portabel in
C, kann man die auch ohne größere Änderungen auf dem µC übernehmen.
Florian Lutz schrieb:> ich bin absoluter Laie im Bereich Mikrocontroller und entwickel gerade> einen Algorithmus mit Fourier-Transformation und vielen weiteren> Operationen.
Ein Algorithmus ist zweifellos notwendig, ist aber weniger als die halbe
Miete. Was am Ende gebraucht wird, ist ein Programm. Und zwischen
Programm und Algorithmus liegen noch etliche Schritte.
> Nun möchte ich die Hardware, auf der der Algorithmus laufen> soll, in Auftrag geben.
Dazu ist es eindeutig zu früh.
> Ich wurde nun nach der Komplexität des Algorithmus gefragt
Das interessiert in der Praxis keinen. Dich als Programmierer natürlich
schon. Aber sobald das Programm einmal steht, interessiert kein Schwein
mehr, ob der Algorithmus O(n) oder O(log n) braucht. Schon allein
deswegen, weil sich die Problemgröße n nachher gar nicht mehr ändert.
Außerdem rechnet die Informatik sehr großzügig mit "Operationen" und
unterscheidet dann nicht mehr, ob das nun Ganzzahl-Additionen in maximal
der Breite der ALU sind oder Fließkomma-Divisionen. Bei der Auswahl der
Hardware ist das aber ein entscheidender Unterschied.
> bzw. auch, was die Anforderungen an den Prozessor sind.
Eben. Das ist die Frage, die dir die Hardware-Leute stellen.
Der erste Schritt würde darin bestehen, die Anforderungen an die
Geschwindigkeit des Programms festzulegen. Dann würde man einen
Prototypen des Programms schreiben und die Geschwindigkeit messen. Dazu
verwendet man Hardware, die prinzipiell geeignet ist und im Zweifel eher
schneller/größer als nötig.
Mit etwas Glück übererfüllt der Prototyp die Anforderungen und man kann
die Hardware etwas sparsamer auslegen. Weit öfter reicht die
Geschwindigkeit des Prototypen aber nicht aus und man muß am Programm
nachbessern oder auf andere (schnellere, spezialisiertere) Hardware
setzen.
> Anmerkung: Der Algorithmus verrechnet kontinuierlich Sensorwerte die> einer festen Fensterbreite unterliegen.
Dann hast du also einen festen zeitlichen Ablauf und eine feste
Datenmenge. Z.B. "alle 10 ms müssen die letzten 1000 Sensorwerte durch
Berechnung X laufen". Daraus läßt sich jetzt einfach eine Zielvorgabe
ableiten, wie lange die Funktion für "Berechnung X" maximal dauern darf.
Florian Lutz schrieb:> Peripherie könnte ich erstmal vernachlässigen, da> sich der Hersteller darum kümmern wird.
Wie kommst du denn DA drauf?
Irgendwie kommen die Daten doch rein? Über einen A/D-Wandler (Intern,
Extern?)? USB?
Und irgendwie muss doch etwas mit den Daten geschehen, nachdem sie
verarbeitet worden sind. Okay, außer, dass sie im RAM vor sich hin
gammeln. Soll ein Pin geschaltet werden? Soll ein Display angesteuert
werden? Sollen die Daten wieder versendet werden? Soll ... passieren?
Das gehört doch mit zu DEINEM Part...
Florian Lutz schrieb:> @Pragmatiker: Die Maschinenbefehle pro Sekunde wären vermutlich eine> gute Herangehensweise. Peripherie könnte ich erstmal vernachlässigen, da> sich der Hersteller darum kümmern wird.
Du unterschätzt offenbar, wie groß der Rechenleistungsbedarf für die
Ansteuerung der Peripherie werden kann. Mit Glück passt alles gut zu den
Hardwareressourcen, d.h. die integrierten Peripherieblöcke können Deine
Wandler genau so ansteuern wie benötigt. Mit etwas Pech funktioniert das
meiste in Hardware, aber in der Software wird durchaus nennenswert Zeit
damit verbraten, Daten hin- und herzukopieren, zu skalieren usw., bevor
sie in Deiner Applikation landen. Und mit sehr viel Pech kann man die
Peripherieblöcke überhaupt nicht auf die geplante Art und Weise
verwenden und muss ggf. sog. "Bitbanging" betreiben, d.h.
Schnittstellenprotokolle in Software nachbilden. Und so etwas kann schon
die Vollauslastung eines dicken Mikroprozessors bedeuten. BTDT.
Möglicherweise kann auch ein SoC mit FPGA-Anteil interessant sein, z.B.
Xilinx Zynq. Damit lassen sich auch recht exostische
Schnittstellenanforderungen in Hardware gießen und einige Algorithmen in
Hardware auslagern, z.B. FFT.
Ich schließe mich aber vorbehaltlos dem Vorschlag an, dass zunächst eine
Evaluierung auf einem oder mehreren Entwicklungsboards erfolgen sollte.
Die sind einfach billig und funktionieren meist (nicht immer...) ganz
passabel.
In-/Output sind definiert und welche Schnittstellen notwendig sind. Der
Hersteller meinte, dass er von mir lediglich den Teil des Algorithmus
bewertet braucht, der letzten Endes 'nur noch' die Analyse der
Sensorwerte macht. Dass die Peripherie hierbei sehr relevant ist, ist
verständlich, darum kümmert sich allerdings der Hersteller.
Vielen Dank an alle für die überaus nützlichen Infos. Werde nun den Weg
über die Evaluierung auf Basis von Entwicklerboards gehen und mich so an
die richtige Hardware herantasten.
Besten Dank an alle!
Du kannst auch ruhig schonmal anfangen die harten Brocken für die
Berechnung probeweise zu implementieren um zu sehen was ein gängiger
Compiler draus macht, evtl. erstmal nur für einen einzigen Sensor und
schauen wie schnell die Berechnung überhaupt sein wird auf irgendeinem
gängigen Prozessor den Du gerade rumliegen hast und dann als Vergleich
hinzuziehen kannst: Wieviel RAM werde ich mindestens brauchen? Wieviele
Taktzyklen brauche ich mindestens? Kann ich was reißen wenn alles in
Festkomma gerechnet wird? Komme ich mit 32Bit Registern aus für alle
Zwischenergebnisse? Brauche ich Divisionen? Bei manchen
Problemstellungen kann man sowas auch schon auf dem Papier abschätzen
(ich brauche mindestens soviele Multiplikationen und soviele Additionen,
wieviele Takte würde das in handgeklöppeltem Assembler kosten, kann ich
Multiply-Accumulate Instruktionen nutzen? Was würde mein Compiler draus
machen?) um schnell zu sehen ob Du mit einem gegebenen Prozessor
überhaupt eine Chance hättest oder was Du mindestens bräuchtest.
Die Entwicklungsumgebungen der MCs bringen meist einen Emulator mit.
Wenn du nur die Berechnung ohne Ein-Ausgabe entwickelst, könnte ein
Performancetest in Emulator einfacher sein, als auf realer Hardware.
mit FFT und Kreuzkorrelation bin ich wegen der Rechenleistung auch schon
mal ins Fettnäpfchen getappt und speziell hier kann man sich ziemlich
verpeilen. Allderdings mit 30 Jahren Erfahrung und bevor eine Platine
gemacht wurde. Nachdem ich sehr schnell gelernt habe, daß es bei Excel
auch einen Fortschrittsbalken gibt, bin ich auf Matlab umgestiegen.
1) Programmier das Teil mal auf Matlab. Ging bei mir mit der vorhandenen
Ma<trizenrechnung ziemlich einfach. Das kannst du dann auf einem PC
deiner Wahl laufen lassen und siehst wie groß die Zeiten sind und ob sie
vernachlässibar sind. Bei mir war das gleich mit echten Daten und
Visualisierung weil das Matlab halt auch konnte.
2) Sind die Zeiten vernachlässigbar, so kannst du dir Gedanken über
einen uC und den dazu passenden Speicher machen. Sind sie wesentlich,
solltest du über eine Hardwarelösung nachdenken da die PCs heutzutage im
Vergleich zu manchen uC generell rattenschnell sind.
3) Bei mir war auch die Hardwarelösung (FPGA) unrealistisch, da noch
etliche Bits zur Rechentiefe gefahlt haben die man mit den vorhandenen
Bibliotheken nicht erreichen hätte können.
Daher habe ich angenommen, daß ich eine VHDL Lösung ganz mit eigenem
Code ohne Bibliotheken auch auch nicht gebacken kriege und es blieb bis
heute bei einem (Linux)PC mit Matlab wo die Rechnung in nur 2-3
Quellzeilen drinstecken. Die Daten werden zwischengepuffert und etwa
10-20% davon wird gerechnet, der Rest geht verloren. Praktisch liegen
dabei immer noch 2-3 Resutlate pto Sekunde vor, was für den Anwender
etwa so aussieht als ob es in Echtzeit funktionieren würde. Der Prozess
ist zwar schnell, ändert sich aber nicht so schnell sondern ist zum
nächsten Zyklus immer ähnlich, so daß es nicht auffällt.
