www.mikrocontroller.net

Forum: FPGA, VHDL & Co. Summe eines Arrays effizient berechnen


Autor: Mike (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ich mache mir gerade Gedanken über ein triviales Problem und dessen 
Lösung in VHDL. Bevor ich das selbst implementiere wollte ich mal 
fragen, ob es dazu vielleicht schon vorhandene Implementierungen gibt.

Folgendes:
Ich habe ein Array von unsigned-Datentypen, dessen Summe ich gerne 
berechnen würde. Ich denke, dies wird wohl am Effizientesten durch einen 
Addierbaum zu lösen sein mit Tiefe log(Array-Länge), oder?
Um einen maximalen Takt zu bekommen, würde ich die einzelnen Ebenen 
jeweils durch eine Registerstufe voneinander trennen, also eine Pipeline 
daraus machen.

Dazu meine Fragen:
- Gibt es eine noch bessere, effizientere Alternative (Latenz egal)?
- Gibt es dafür VHDL-Generatoren (Cores)?

Danke,
Mike

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Ich denke, dies wird wohl am Effizientesten durch einen
> Addierbaum zu lösen sein mit Tiefe log(Array-Länge), oder?
Das braucht einiges an Ressourcen und Verdrahtung...

> Gibt es eine noch bessere, effizientere Alternative (Latenz egal)?
Effizient in Bezug auf was?
Geschwindigkeit, Platz, Ressourcen, Leistungsverbrauch...

Wie groß ist das Array (BxT)?
Wie kommen die Daten in das Array?

Wenn die Laufzeit egal ist, dann würde ich (auch in Hinsicht auf 
Realisierbarkeit/Portierbarkeit) einfach mit einem Adresszähler durch 
das Array donnern, und dann pro Takt einen Wert aufsummieren.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
genau! Wenn er nämlich einen binären Baum baut, der zudem noch getaktet 
ist und mehrfach Register erfordert, braucht er sicher 10-20 Takte. Da 
kann schon 20 Werte im array prozessieren und bei Bearf 3-4 lines 
einrichten.

Autor: Mike (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

das habe ich vergessen zu erwähnen: Das Array ist selbst Bestandteil 
einer Pipeline, d. h. mit jedem Takt wird das Array mit neuen 
unsigned-Werten gefüllt. Array-Größe ist egal, ich sage einfach mal 10 
Worte je 8 Bit.

> Wenn die Laufzeit egal ist, dann würde ich (auch in Hinsicht auf
Realisierbarkeit/Portierbarkeit) einfach mit einem Adresszähler durch
das Array donnern, und dann pro Takt einen Wert aufsummieren.

Ja, wäre auch eine Idee. Nur müsste ich das dann in einer Array-Bank mit 
Zeigern realisieren, da das Array ja mit jedem Takt neu gefüllt wird.

Ich denke, dass der Addierbaum mit Registerstufen die beste Lösung 
darstellt in Bezug auf Einfachheit und hohe Taktrate, oder?

Gruß,
Mike

Autor: Jan M. (mueschel)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
In Sachen Taktrate und Latency sowie dem Fakt, dass in jedem Takt neue 
Daten verarbeitet werden können, ist ein Binärbaum wohl die beste 
Lösung. Die Größe der Logik dürfte jedoch vergleichsweise hoch sein - 
aber bei nur 10 Wörtern mit je 8 Bit brauchst du dir da noch keine 
Gedanken machen.

I.d.R. sollte es für aktuelle Bausteine auch kein Problem sein, mehr als 
2 Wörter in einem Takt zu addieren, Vierfach-Addierer sind meist auch 
noch hinreichend schnell, man muss nur auf die Klammersetzung achten:

e <= a + b + c + d; ist langsamer als e <= (a+b)+(c+d);, da einmal eine 
Kette von drei Addieren, einmal ein Binaerbaum aufgebaut wird.

Ich habe hier z.B. einen 16fach 16Bit Addierer, der nur zwei Takte 
Latency hat und im Virtex4 und Lattice ECP2 noch mit deutlich über 120 
MHz taktet.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Auch wenn jeweils immer ein neuer Wert hinzukommt, bleibt die 
Betrachtung bez de Latenz bestehen. Du bekommst immer nach jedem Takt 
ein neues Ergebnis. Du benötigst dann eben n Additionsstufen - entweder 
transversal als paralleler adder oder longitudinal als 
vollsummenaddierer.

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]
  • [vhdl]VHDL-Code[/vhdl]
  • [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.