Kleinsten / größten Wert finden

[Flo (Gast)]

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):

variable tmp_max = 0

for A in erster_Wert to letzter_Wert loop
   if A > tmp_max then
      tmp_max = A
   end if
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?

[faustian (Gast)]

Ich sehe es mal gegeben dass eine von sich aus sortierte Datenhaltung 
nicht in Frage kommt?


Werte oder Teilmenge in Register geben, paarweise vergleichen, die 
ergebnisse der Vergleiche wieder in einen Registersatz halber Groesse 
geben, dort wieder paarweise....?

[Ras F. (rasfunk)]

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.

[faustian (Gast)]

Kommt auch auf den Wertebereich an - WAS sind das fuer Werte? Bei 4x4 
Bit oder so kaeme noch die GANZ brutale Methode (Bucketsort) in Frage...

[Läubi .. (laeubi)]

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

[Flo (Gast)]

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.

[Flo F (Gast)]

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

[Läubi .. (laeubi)]

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:

a ------------^--- max
              |
b -------^--------
         |
c ---^------------
     |
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:

a ---------------- 
      |        
b ---`´---^------- max
          |
c ---^------------
     |
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.

[D. I. (Gast)]

Läubi .. schrieb:

> 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.

Und falls man die nicht hat, kann man immer noch entsprechend mit 
Dummywerten auffüllen

[Flo (Gast)]

Danke für die Anregungen und Ideen! Ich werde es mir mal durch den Kopf 
gehen lassen, welche Möglichkeit sich bei mir am einfachsten realisieren 
lässt.

Grüße
Flo