Hallo Leute ich möchte ein System implementieren wo ich die Wahl habe die Mathematik hauptsächlich übers quadrieren von Zahlen oder das Multiplizieren von Zahlen zu lösen. Daher meine Frage: Ist die Quadrierung von einer 16 Bit Zahl effizienter (bzw kann man sie effizienter machen) als die Multiplikation von zwei 16 Bit Zahlen? Gibt es vllt einen schönen Algorithmus zum quadrieren von Zahlen? Ich arbeite auf einem Spartan3E und in VHDL. danke für eure Hilfe greez Kiigass PS: Es geht hier wirklich um den 1:1 vergleich, also ob -eine- Quadrierung effizienter sein kann als -eine- Multiplikation.
überlass das dem syntheseprogramm, probiers einfach aus. allerdings wenn du quadrierst brauchst du evtl weniger flipflops, weil du ja nur eine zahl speichern musst anstatt 2
Bei Standard-Einstellung wird beides in einen MUL18X18 gepackt und braucht überhaupt keine extra Slices. Ansonsten ist beides eine Kombinatorische Operation, also keine FlipFlops. Und das Sythesetool kann das durchaus optimieren. Also einfach hinschreiben und fertig.
Kiigass schrieb: > PS: Es geht hier wirklich um den 1:1 vergleich, also ob -eine- > Quadrierung effizienter sein kann als -eine- Multiplikation. Man könnte beides (Quadratur/Multiplikation) auch in ein RAM packen. Dem würde bei einer Quadratur verglichen mit der Multiplikation die halbe Adressbreite ausreichen... Ich würde allerdinges trotzdem einem Multiplizierer nehmen. Einfach, weil sich das schöner hinschreibt... ;-)
Lothar Miller schrieb: > Ich würde allerdinges trotzdem einem Multiplizierer nehmen. Einfach, > weil sich das schöner hinschreibt... ;-) Früher (tm) wurden Programme möglichst so geschrieben, dass das Compilat möglichst effektiv war - und heute ...
>und heute ...
Sollten die Compiler besser optimieren, als das, was der Programmierer
früher von Hand gemacht hat.
Werner schrieb: > Früher (tm) wurden Programme möglichst so geschrieben, dass das Compilat > möglichst effektiv war - und heute ... Heute ist die Hardware so effizient oder schnell oder die Synthese so gut, dass das nichts mehr ausmacht. Ich schreibe in VHDL meist nur das Verhalten hin und bin mit dem Ergebins zufrieden. Und ich schreibe Software in C, weil der Compiler das Übertragen in Maschinensprache mindestens gleich gut kann wie ich. Nur dort, wo ich definiertes (zeitliches) Verhalten brauche (<0,2% der Fälle), da kommt handgestrickter Assemblercode ins Spiel. Der Knackpunkt dabei ist, zu wissen, wann das eine "reicht" und das Andere "nötig" ist... ;-)
Lothar Miller schrieb: > Man könnte beides (Quadratur/Multiplikation) auch in ein RAM packen. So zum Beispiel:
1 | library IEEE; |
2 | use IEEE.STD_LOGIC_1164.ALL; |
3 | use IEEE.NUMERIC_STD.ALL; |
4 | |
5 | entity RAM_Multiplier is |
6 | Port ( Din : in STD_LOGIC_VECTOR (7 downto 0); |
7 | Dout : out STD_LOGIC_VECTOR (15 downto 0); |
8 | clk : in STD_LOGIC); |
9 | end RAM_Multiplier; |
10 | |
11 | architecture Behavioral of RAM_Multiplier is |
12 | type RAM_t is array (0 to 255) of signed (15 downto 0); |
13 | signal MathRAM : RAM_t; |
14 | begin
|
15 | -- RAM belegen
|
16 | table: for i in 0 to 255 generate |
17 | MathRAM(i) <= to_signed(i*i,16); |
18 | end generate; |
19 | -- Takten für BRAM
|
20 | Dout <= std_logic_vector(MathRAM(to_integer(unsigned(Din)))) when rising_edge(clk); |
21 | end Behavioral; |
Das wird doch automatisch in ein RAM gepackt, wenn man die option wählt und es kombinatorisch aufbaut. Was ich gesehen habe: Beim QUAD fällt immer das zweite Bit weg, es ist immer null. Wenn die Zahl bekannt ist, würde ich immer kombinatorisch bauen, weil dann viele Stränge wegfallen und die MUL zu einer fortgesetzten ADD verkommt.
Kiigass schrieb: > Daher meine Frage: Ist die Quadrierung von einer 16 Bit > Zahl effizienter (bzw kann man sie effizienter machen) als die > Multiplikation von zwei 16 Bit Zahlen? Betrachtet man die Mathematik und viel größere Zahlen als 16 Bit, dann ja. Die Quadrierung ist asymptotisch 1.5 mal schneller als eine vergleichbar Multiplikation zwei gleichgroßer Zahlen. Die Algorithmen die an diese theoretische Komplexität herankommen basieren auf der Multiplikation per Fourier Transformation. Der derzeit schnellste Algo ist die "modulare Fermat Fast Fourier Transformation in Z/(p^m Z) with p must not be prime nach A.Schönhage und S.Strassen" siehe "Schnelle Multiplikation grosser Zahlen by Arnold Schönhage and Volker Strassen, Computing 7, p. 281-292, 1971." Allerdings bezieht sich das wirklich auf enorm große Zahlen ab denen erst dieser Algorithmus seine Performanve ausspielen kann. Sind die Zahlen kleine dann gibt es verschiedene andere Verfahren sehr oft auf dem Prinzip "Divide and Conquer" basieren. Eine große Gruppe davon basieren auf den Idee von Karatsuba wie zb. die Toom-Cook Algorithmen. Sind die Zahlen noch kleiner also im Bereich der CPU Busbreiten, zB. <= 128Bit dann sind die Hardware Multiplizierer am performantesten. Möchte man aber auf einem 8Bit Rechnersystem mit 8Bit HW-Multiplizierer mit zB. 64 Bit Zahlen rechnen dann kann man im Gegensatz zur Schulmethode der Multiplikation uU. mit anderen Verfahren ein par Takte herausholen. Das trifft dann aber auf die Quadrierung und gleichermaßen auf die Multiplikation zu. Dh. es gibt keinen Unterschied in der machbaren Performance zwischen Quadrierung/Multiplikation wenn die Operandengröße so gering ist wie bei dir angenommen die 16Bit. Einziger Unterschied ist der Bedarf an Speicher, eventuellen Lookup Tabellen. Bei der Quadrierung wird weniger davon benötigt wenn der Algorithmus auf Lookup Tabellen beruht. Gruß Hagen
Auf FPGAs und ASICs mit schnellen Boolschen Operatonen kann man uU. die komplette Arithmetik des zu lösenden Problemes in eine ander Zahlendomain verschieben. Statt also zB. mit natürlichen Zahlen in P odr N zu rechnen wechselt man die Zahlendomain zb. in GF(2) = Galois Field zur basis 2. Beispiele dafür sind die Prüfsummen wie CRCs oder Fehlerkorregierende Codes. Diese arbeiten bei den "Zahlen" in GF(2^x). Vorteil dabei ist nämlich das man bei diesen GF(2^x) keine Überlaufsbetrachtungen machen muß. Zerlegt man eine Zahl in eine 2'Potenz Schreibweise und rechnet man damit in N,P dann entstehen Überträge von einer Bit-Potenz zur nöchsten. In GF(2^x) Darstellung ist dies nicht der Fall. Stellt man sich nun eine solche Zahl in einer CPU als in FFs gespeicherte Bits vor so muß man die Überträge als Verdrahtung innerhalb diser FFs betrachten die Propagationszeiten benötigen. In GF(2^x) sind diese FFs nicht minteinander verküpft und dh. man kann auf Bitebene der Zahlendarstellung alle Bits in parallel ausrechnen da es keine Überträge zwischen den Bits zu berücksichtigen gibt. Eine Multiplikation in N,P entspricht in GF(2^x) einer XOR Operation, diese kann hoch parellelisiert werden mir hohem Durchsatz. Gruß hagen
Klingt sehr interessant. Wo müsste ich da recherchieren? Ist das mehr Computeralgebra oder doch eher generale Mathematik?
Computeralgebra und Zahlentheorie. Nochwas zur Korrektur: oben schrieb ich was von Zahlendomains N und P. Das muß N und Z lauten da P ja die Primzahlen sind. Gruß hagen
Grundsätzlich ist quadrieren lässt sich einfacher realisieren als multiplizieren zweier etwa gleich großer Zahlen. Kiigass schrieb: > Ich arbeite auf einem Spartan3E Und da gehts los... Laufzeit für einzelne Multiplikation oder Durchsatz? Alle Multiplizierer gegen den ganzen Rest des Chips? ... Eigentlich macht nur die Durchlaufzeit für eine einzelne Multiplikation Sinn. Da wirst du dich mit handgebauter Logik sehr schwer gegen die dedizierte Hardware tun. Die Logik wird vmtl. zu weit verteilt werden.
Kiigass schrieb: > Hallo Leute > > ich möchte ein System implementieren wo ich die Wahl habe die Mathematik > hauptsächlich übers quadrieren von Zahlen oder das Multiplizieren von > Zahlen zu lösen. Daher meine Frage: Ist die Quadrierung von einer 16 Bit > Zahl effizienter (bzw kann man sie effizienter machen) als die > Multiplikation von zwei 16 Bit Zahlen? Gibt es vllt einen schönen > Algorithmus zum quadrieren von Zahlen? Ich arbeite auf einem Spartan3E > und in VHDL. Die 16 bit sind signed oder unsigned? Bei unsigned fehlt bspw. auf das das zweitniedrigste bit immer '0' ist, also 000 0 0 00 000 0 1 01 001 0 0 04 010 0 1 09 100 0 0 16 110 0 1 25 sollte man anhand binomialsatz auch in zwei minuten bewiesen haben. Das eine FF kannst du also schon mal im Produkt sparen. Das LSB des produktes ist gleich dem LSB des Faktor, kannst also auch auch dieses FF im produkt sparen. Da Routing sourcen bei vollen FPGA's immer kniffliger für den Router werden sollte, man diese beide Ausgangsleitungen des MULT18 offen lassen. Ich bin mir sicher, das auch weitere bits optimierbar sind. Vielleicht hat ein coregenerator ein optimiertes Quadriermakro, das synthesetool schafft es nicht diese Mathe-basics zu erkennen und zu nutzen. MfG,
Fpga Kuechle schrieb: > das synthesetool schafft es nicht diese Mathe-basics zu erkennen und das wäre auch schwer ... Das einzige, was die Synthe i.r.R. packt, ist die Reduktion der Multiplikation auf eine Addition und dann a) gfs die implementierung als constant coeficient multiplier und danbei dann b) das Invertieren der Addition zur Subtraktion, wenn mehr, als die Hälfte der Bits aktiv sind. So purzeln viele Skalierungen in FPGAs zusammen. Kleiner, als eine fortgesetzte Addition und carry chain kann man es meines Wissens nicht machen und schnell ist das in keinem Fall. Der embedded multiplier ist einfach unschlagbar. Ausserdem synthetisiert er an solchen Sachen (paralle Filter z.B.) relativ lange herum.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.