Kleinsten / größten Wert finden

Flo Gast #1274964
Lesenswert?
• ▲
▼ 
Hi,

ich bin gerade dabei, aus einer Menge von Werten den kleinsten bzw. 
größten Wert zu suchen. Das klappt eigentlich auch schon. Folgendermaßen 
sieht mein erster Versuch aus (PSEUDO-Code größter Wert):

1
variable tmp_max = 0

2


3
for A in erster_Wert to letzter_Wert loop

4
   if A > tmp_max then

5
      tmp_max = A

6
   end if

7
end loop


Das funktioniert soweit (in der Simulation!). Jedoch bin ich am 
überlegen, wie man das effizienter gestalten kann. Bspw. dass man etwas 
parallelisieren könnte. Nur habe ich noch keine gescheiten Ansatz 
gefunden.
Das Problem für mich ist, dass die Anzahl der Werte variabel ist (von 9 
- 81). Für 9 Werte ist es für mich z.B. noch vorstellbar, dass man 
parallel je zwei Werte nimmt und diese vergleicht. Dann nimmt man die 5 
Ergebnisse dieses Vergleichs und vergleicht wieder je zwei Werte usw... 
Das würde bei neun Werten 4 Takte benötigen, bis man das Ergebnis hat.
Ein andere Möglichkeit wäre die Werte zu sortieren, aber das nimmt 
wahrscheinlich mehr Zeit in Anspruch als die Suche nach dem kleinsten 
Wert.

Hat jemand evt. einen Tipp wie man die Suche nach dem größten bzw. 
kleinsten Wert auf einem FPGA umsetzen kann?
Beitrag melden Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Markierten Text zitieren Antwort Antwort mit Zitat
Ras F. #1275006
Lesenswert?
• ▲
▼ 
Ich weiß es nicht genau. Aber besser als O(n*log(n)) wird es wohl nicht 
gehen. Insofern bist Du mit Deinem binary Tree garnicht mal so schlecht.

Brauchst Du denn wirklich immer (d.h. jeden Takt) das Maximum/Minimum 
über den definierten Zeitraum? Oder reicht es, wenn Du nach z.B. 81 
Datensätzen das Maximum hast? In dem Fall könntest Du einfach die 
Variable gegen ein Register (Signal) tauschen und die Schleife weglassen 
und bist mit einem einzigen Komparator fertig. Das Register muss dann 
nach der entsprechenden Anzahl von Datensätzen zurückgesetzt werden.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Flo Gast #1275296
Lesenswert?
• ▲
▼ 
Hallo allerseits,
vielen Dank für die Antworten!

Also, um etwas konkreter zu werden, es geht um Pixelwerte in einem 
Graubild (--> Wertebereich: 0 - 255).
Und pro Takt wird immer ein Bildbereich der Größe 3x3, 5x5, ... bis max 
9x9 betrachtet.
D.h. im "schlimmsten Fall" kommen wirklich pro Takt 81 Werte, von denen 
das min/max benötigt wird. Aber das min/max muss nicht nach einem Takt 
vorliegen. Das kann ruhig mit ein paar Takten Verzögerung geschehen.

> Du könntest auch ein Sortiernetz implementieren, das wäre dann auch 
Synthetisierbar.

Wäre eine Sortierung nicht Aufwendiger als nur min/max?

Wie es aussieht, läuft es wohl dann doch auf einen "Binary Tree" und 
paarweise Vergleichen raus.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Flo F Gast #1275321
Lesenswert?
• ▲
▼ 
Wo siehst Du den paarweisen Vergleich?
Dein Loop im ersten Post ist bereits O(n), er schaut jeden Wert genau 1x 
an - und dass muss er wohl auch.

Zum paralleliseren bleibt Dir wie wohl in der Tat ein (binaerer) Baum, 
der aber im zeitlich optimalsten Fall dann auf unterster Eben 40 
Vergleiche gleichzeitig machen muss. Alternativ je nach Speicherlayout 
an Zeilen/Reihen parallelisieren & am Ende aggregieren.
Aber an der Gesamtzahl Operationen aendert das nichts (sie steigt 
sogar).

Gruss
Flo
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Läubi .. Persönliche Seite #1275612
Lesenswert?
• ▲
▼ 
Flo schrieb:
>> Du könntest auch ein Sortiernetz implementieren, das wäre dann auch
> Synthetisierbar.
>
> Wäre eine Sortierung nicht Aufwendiger als nur min/max?
Jein.. Du brauchst ja keins was alle Werte sortiert, sondern nur eins 
was dir das größte Element nach oben sortiert. (Ein Pfeli repräsentiert 
ein Element was Zwei Werte der größe nach Vertauscht)
Das Sortiernetz würde dann so aussehen für 4 Werte:
1
a ------------^--- max

2
              |

3
b -------^--------

4
         |

5
c ---^------------

6
     |

7
d ----------------

Da gibt es natürlich jezt noch tolle Optimierungen aber die sind hier 
m.m nach nicht nötig. Nach einer initialen Latenz von 3 Takten kommt in 
jedem Takt ein neuer Maximalwert heraus da du aus jedem Schritt eine 
getaktete Stufe machen kannst, und da du eh einen Strom von Daten hast 
ist das doch optimal...

> Wie es aussieht, läuft es wohl dann doch auf einen "Binary Tree" und
> paarweise Vergleichen raus.
Geht auch als "Binärer Vergleicher" aber das funktioniert nur gut mit 
Zweierpotenzen:
1
a ---------------- 

2
      |        

3
b ---`´---^------- max

4
          |

5
c ---^------------

6
     |

7
d ----------------

Du brauchst trozdem drei Vergleicher, hast also keine Hardware gesparrt, 
das einzige ist das die Initiale Latenz der Pipeline einen Takt kürzer 
ist, und das ganze funktioniert nur mit 2er Potenzen.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren