Max(a,b) möglichst effizient

Was für Größen? Drück dich bitte konkreter aus.
Bei Konstanten machts dir der Compiler für lau.

Kan asta schrieb:
> Was für Größen? Drück dich bitte konkreter aus.
> Bei Konstanten machts dir der Compiler für lau.

Sry war keine Absicht, es handelt sich um variable Integers mit beiden 
Vorzeichen.

Queck Silber schrieb:
> variable Integers mit beiden
> Vorzeichen.

Sowas nennt sich signed int.

Entweder willst du schönen Quelltext, dann würde ich sowas machen:

Variante (1): #define max(a,b) ((a > b) ? a : b)

Variante (2): Oder du willst dir die Hände schmutzig machen, dann halt 
Assembler. Ist dann allerdings sehr platform/projekt-spezifisch.

Deine letzten zwei Fragen sind ohne genaue Kenntnis deiner Hardware 
nicht zu beantworten. Deine unkonkrete Herangehensweise lässt mich zu 
dem Schluss kommen, dass dir Variante (1) besser steht.

Peter II schrieb:
> es geht hierbei wohl nicht um C

Oha. Ob dieses Missverständnis jetzt an mir liegt...

Kan asta schrieb:
> Deine letzten zwei Fragen sind ohne genaue Kenntnis deiner Hardware
> nicht zu beantworten.

Ich habe einen Xilinx Spartan 6 XC6SLX45

PS: Ich arbeite mit der Xilinx ISE in VHDL

c <= a;
if b > a then
   c <= b;
end if;

Kan asta schrieb:
> c <= a;
> if b > a then
>    c <= b;
> end if;

super, danke dir!

Leider (mein Fehler) hab ich in der Überschrift des Themas die dritte 
Größe vergessen. Im Text später habe ich es dann erwähnt. Also dasselbe 
nur mit dem Maximum aus drei Größen. Würdest du das so machen:?

max <= a;

if b > a then
   max <= b;
end if;
if c > ??? then
   max <= c;
end if;

Das Problem sind die 3 Fragezeichen, denn ich kann ja nicht fragen:
if c > a,
weil c ja durchaus größer als a aber kleiner als b sein könnte. 
Andersrum gilt dasselbe.

else

Kan asta schrieb:
> else

das funktionert auch nicht, denn wenn b größer a ist, wird der 
else-Zweig nicht aufgerufen. Es könnte aber sein, dass b größer a ist 
und c größer b.

dann musst du wohl oder übel

> if b > a then
>    max <= b;
> end if;
> if c > max then
>    max <= c;
> end if;

schreiben.

Kan asta schrieb:
> dann musst du wohl oder übel
>
>> if b > a then
>>    max <= b;
>> end if;
>> if c > max then
>>    max <= c;
>> end if;
>
> schreiben.

Das war auch mein Gedanke, aber max ist in dem Takt noch nicht 
verfügbar. Also kann ich nicht nach c > max fragen.

warum ist max kein signal?

Kan asta schrieb:
> warum ist max kein signal?

Würde das einen Unterschied machen? Soweit ich weiß, werden auch Signal 
nicht sofort aktualisiert, sondern erst beim Takt.
Der Vollständigkeit halber, nur um dahingehend Klarheit zu schaffen, 
möchte ich noch sagen, dass ich beabsichtige mit einer 
One-Process-State-Machine zu arbeiten.

Kurzschluss schrieb:
> wie wärs damit:
>
> max := a;
> if(b>max)then
> max := b;
> end if
> if(c > max)then
> max := c;
> end if;
> out <= max;
>
>
> max müsste eine variable sein

Ist an sich ne gute Idee, aber ich meine mal gehört zu haben, dass man 
Variablen nicht benutzt (ähnlich wie Schleifen).

Queck Silber schrieb:
> in möglichst wenig Takten.
Vergleicher sind Logik und daher taktlos.

> Mein Ansatz war: ...
Ich würde das so probieren:

1

signal a,b,c,m : integer;

2

3

process (a,b,c) begin

4

  if (a>b) then

5

     if (a>c) then m <= a;

6

     else          m <= c;

7

  else

8

     if (b>c) then m <= b;

9

     else          m <= c;

10

  end if;   

11

end process;

Queck Silber schrieb:
>> max müsste eine variable sein
> Ist an sich ne gute Idee, aber ich meine mal gehört zu haben, dass man
> Variablen nicht benutzt (ähnlich wie Schleifen).
Man darf Variable durchaus benutzen. Man sollte nur um die möglichen 
Fallstricke wissen. Ich hätte auch diesen Ansatz mit der Variablen:

1

signal a,b,c,m : integer;

2

3

process (a,b,c) 

4

variable h: integer;

5

begin

6

  if (a>b) then    h := a;

7

  else             h := b;

8

  end if;

9

10

  if (h>c) then    m <= h;

11

  else             m <= c;

12

  end if;   

13

end process;

Also in C könnte man es so machen, ob das in VHDL umzusetzen ist, ist 
die andere Frage.

1

int max(int a, int b) {

2

  return a ? (a-b)>0 : b 

3

}

cyblord ---- schrieb:
> Also in C könnte man es so machen
> return a ? (a-b)>0 : b
Damit kann man das Maximum von drei Werten feststellen?
Und ausserdem bekommst du da noch falsche Werte... :-o
Denn da steht:
Wenn a ungleich Null, dann gib eine 1 zurück, wenn a-b größer Null ist, 
sonst gib b zurück.


Ich würde das in C so machen, dass es jeder erkennt:
  return  a>b ? a : b;

Lothar Miller schrieb:
> cyblord ---- schrieb:
>> Also in C könnte man es so machen
>> return a ? (a-b)>0 : b
> Damit kann man das Maximum von drei Werten feststellen?
> Und ausserdem bekommst du da noch falsche Werte... :-o
> Denn da steht:
> Wenn a ungleich Null, dann gib eine 1 zurück, wenn a-b größer Null ist,
> sonst gib b zurück.
>
>
> Ich würde das in C so machen, dass es jeder erkennt:
>   return  a>b ? a : b;

Ja sorry habs in der Hektik vertauscht. Aber im Ausgangsthread gehts 
doch um 2 Werte und nicht um 3.

Lothar Miller schrieb:
> Man darf Variable durchaus benutzen. Man sollte nur um die möglichen
> Fallstricke wissen.

Danke erstmal für den Beitrag, wie gewohnt: super. Könntest du bitte 
noch ein/zwei Stichworte zu diesen Fallstricken verlieren?

Die schnellste Variante (aber vom Resourceverbrauch aufwändiger) wäre 
wohl, drei Vergeliche (a>b, b>c, c>a) gleichzeititg durchzuführen und 
dann als Steuersignale auf einen (unvollständigen, da nicht alle 
Kombinationen vorkommen) 8:1 Mux zu geben. Das reduziert die Logiktiefe 
auf einen Komparator (die 3 sind ja parallel) und einen Mux.

Queck Silber schrieb:
> Danke erstmal für den Beitrag, wie gewohnt: super.
Merci.

> Könntest du bitte
> noch ein/zwei Stichworte zu diesen Fallstricken verlieren?
Wurden schon verloren, ich hab sie wiedergefunden im 
Beitrag "Variable vs Signal"

Peter K. schrieb:
> Die schnellste Variante (aber vom Resourceverbrauch aufwändiger) wäre
> wohl, drei Vergeliche (a>b, b>c, c>a) gleichzeititg durchzuführen und
> dann als Steuersignale auf einen (unvollständigen, da nicht alle
> Kombinationen vorkommen) 8:1 Mux zu geben. Das reduziert die Logiktiefe
> auf einen Komparator (die 3 sind ja parallel) und einen Mux.

Danke dir, das sehe ich auch so, aber die Umsetzung des VHDL liegt ja 
zum größten Teil beim Compiler. Folglich versuche ich also eine 
möglichst gute Lösung in VHDL zu finden.

PS: Thx to Lothar

> aber die Umsetzung des VHDL liegt ja zum größten Teil beim Compiler

Nicht ganz. Du hast schon noch Möglichkeit, das zu beeinflussen. Wenn Du 
zuerst mit a>b ein Maximum auswählst, dann dieses mit c vergleichst und 
wieder auswählst, wir dir der Synthesizer m.E. das auch so realisieren: 
comparator, mux (2:1), comparator, mux (2:1). Das ist dann insgesamt 
kleiner, aber langsamer.

Klaus schrieb:
> Hast du überhaupt Ahnung von VHDL? Wie dir schonmal gesagt wurde, ist
> das hier nicht das C-Forum.

Abgesehen davon, dass du hier nix beiträgst:
Was ist denn daran falsch (vorausgesetzt max ist eine variable, und 
abgesehen von der vergessenen Zuweisung max <= a;)?

Peter K. schrieb:
> Das ist dann insgesamt kleiner, aber langsamer.

Ok, mal ne ganz blöde Frage, wenns erlaubt ist: Damit meinst du die 
Signallaufzeit, oder? Denn innerhalb eines Taktes müsste das doch 
machbar sein? Vorausgesetzt natürlich, dass die Taktzeit größer als die 
Signallaufzeit ist.

MaWin schrieb:
> Der Sinn deiner Hausaufgabe steckt darin, ob dir eine
> Lösung einfällt, die in einem Takt durchlaufen wird.
>
> Die gibt es, aber Hausaufgaben werden hier nicht gelöst.
> Man würde dir ja den ganzen Spass verderben.

Sorry, liegt es daran, dass es schon spät ist oder warum kommt mir der 
Beitrag so seltsam vor? Nun wie dem auch sei, wenn du eine gute Lösung 
kennst, möchte ich dich bitte sie mir mitzuteilen. Eine Hausaufgabe ist 
das hier sicherlich nicht. Die Zeiten sind bei mir vorbei.

PS: Da ich den Beitrag im Forum "VHDL..." gepostet habe, hatte ich 
angenommen, dass es klar ist um welche Sprache es sich handelt.

Um die genz Sache abzukürzen habe ich das einfach mal ausprobiert:

1

-- Macro Statistics

2

-- # Comparators                 : 2

3

--  32-bit comparator greater    : 2

4

--    Maximum combinational path delay: 17.308ns

5

--    Number of Slices  64

6

   process (a,b,c) 

7

   variable h: integer;

8

   begin

9

     if (a>b) then    h := a;

10

     else             h := b;

11

     end if;

12

13

     if (h>c) then    m <= h;

14

     else             m <= c;

15

     end if;   

16

   end process;

17

18

-- Macro Statistics

19

-- # Comparators                 : 3

20

--  32-bit comparator greater    : 3

21

-- # Multiplexers                : 1

22

--  32-bit 4-to-1 multiplexer    : 1   

23

--    Maximum combinational path delay: 12.886ns

24

--    Number of Slices  80

25

   process (a,b,c) begin

26

     if (a>b) then

27

        if (a>c) then m <= a;

28

        else          m <= c;

29

        end if;

30

     else

31

        if (b>c) then m <= b;

32

        else          m <= c;

33

        end if;

34

     end if;   

35

   end process;  

36

37

-- Macro Statistics

38

-- # Comparators                 : 3

39

--  32-bit comparator greater    : 3

40

-- # Multiplexers                : 1

41

--  32-bit 4-to-1 multiplexer    : 1   

42

--    Maximum combinational path delay: 12.886ns

43

--    Number of Slices  80

44

   process (a,b,c) 

45

   variable agb, agc, bgc : std_logic;

46

   begin

47

     agb := '0';

48

     if (a>b) then

49

        agb := '1';

50

     end if;

51

     agc := '0';

52

     if (a>c) then

53

        agc := '1';

54

     end if;

55

     bgc := '0';

56

     if (b>c) then

57

        bgc := '1';

58

     end if;

59

60

     if    agb='1' and agc='1' then

61

        m <= a;

62

     elsif agb='0' and bgc='1' then

63

        m <= b;

64

     else

65

        m <= c;

66

     end if;

67

   end process;

Fazit: die unteren beiden Lösungen werden genau gleich implementiert 
(Basis ISE13 und S3). Und bei genauerem Hinschauen ist das auch kein 
Wunder...


Queck Silber schrieb:
> PS: Da ich den Beitrag im Forum "VHDL..." gepostet habe, hatte ich
> angenommen, dass es klar ist um welche Sprache es sich handelt.
Das Forum beginnt mit "FPGA" und endet mit "& Co". da könnte eigentlich 
auch Abel oder Verilog gemeint gewesen sein....

Queck Silber schrieb:
> Ok, mal ne ganz blöde Frage, wenns erlaubt ist: Damit meinst du die
> Signallaufzeit, oder? Denn innerhalb eines Taktes müsste das doch
> machbar sein? Vorausgesetzt natürlich, dass die Taktzeit größer als die
> Signallaufzeit ist.

Genau. Jetzt musst Du Dich, basiert auf Deinem Clockcycle, nur noch für 
eine der beiden nun schon mehrfach beschriebenen Lösungen entscheiden:

- Langsamer und kleiner (2x Komparator, 2x    2:1 Mux, im Bsp. 17.308ns)
- Schneller und grösser (3x Komparator, 1x 8(4):1 Mux, im Bsp. 12.886ns)

Für Deine Technologie/Speedgrade/Bussbreite gelten natürlich andere 
Zeiten, aber die Grössenordnung der Verhältnisse wir sicher ähnlich 
sein.

Ergänzung
Es gibt noch Varianten den Resourcenbedarf weiter zu verringern, wenn 
man das Ergebniss nicht in einem Extra-Register (hier m) speichert (das 
ist wie die Aufgabe geschildert wurde auch nicht gefordert).

a) das ergebnis-bit der Vergleicher (0: Input1 größer; 1: Input2 größer/ 
gleich) wird als 2 bit vector zurückgeben.. "11" -> max in a, "01" max 
in b, ...

b) eines der Operandenregister wird als Zielregister (Akkumulator) 
vereinbart und das ergebnis in diesen gespeichert.

Bsp. a) ist quasi ein pointer auf register. Da registerbänke oft als 
Registerbänke aus RAM-arrays aufgebaut werden (Picoblaze), is es 
tatsächlich eine Addresse (Pointer). Andernfalls wäre es der selector 
des Datenausgangsmultiplexer (auswählen zwischen Qa, Qb oder Qc.

Vorher sollte man natürlich eine Datenflussanalyse betreiben bzw die 
zeitliche verfügbarkeit/verwendung der daten analysieren. Gut möglich, 
das a,b,c nacheinander (nicht im selben Takt) anliegen. Dann genügt ein 
einzelner Vergleicher (statt zwei/drei), der aller zwei Takte das 
Ergebnis liefert.

MfG,

Fritz Jaeger schrieb:
> Gut möglich, das a,b,c nacheinander (nicht im selben Takt) anliegen.
Hmmm... hier ist weit&breit nirgends ein Takt zu sehen...

> Bsp. a) ist quasi ein pointer auf register.
Letztlich wird immer ein Multiplexer draus. Der kann natürlich auch 
in der Adressierlogik eines RAMs versteckt sein...

Lothar Miller schrieb:
> Fritz Jaeger schrieb:
>> Gut möglich, das a,b,c nacheinander (nicht im selben Takt) anliegen.
> Hmmm... hier ist weit&breit nirgends ein Takt zu sehen...

Im ersten Posting schon. Mein Post ja auch nur als Hinweis gedacht in 
welche Richtung man den FPGA-dreifach-vergleicher modifizieren kann, 
wenn es die Randbedingungen zulassen. Warum warten bis alle Daten 
eintröpfeln und dann mit massiver paraller Logix alles in einem Takt 
berechen, wenn man bequem mit weniger Hardware Zwischenergebnisse bilden 
und auswerten kann! Lokale Optimierungen sind halt weniger effektiv als 
globale Betrachtungen, das soll hier vermittelt werden.

MfG,

Vielen Dank euch allen, ihr habt mir sehr geholfen! Ich werde mir noch 
ein paar Gedanken machen bezüglich des Posts von Fritz Jaeger und dann 
vermutlich zu einer möglichst schnellen wenn auch größeren Lösung 
greifen.

Queck Silber schrieb:
> und dann vermutlich zu einer möglichst schnellen
> wenn auch größeren Lösung greifen.
Was ist "schnell", und was ist "groß"?

Lothar Miller schrieb:
> Queck Silber schrieb:
>> und dann vermutlich zu einer möglichst schnellen
>> wenn auch größeren Lösung greifen.
> Was ist "schnell", und was ist "groß"?

Das bezog sich auf die von dir vorgestellten Lösungen. Eine davon ist 
mit rund 12ns schneller als die andere mit 17ns, allerdings ist sie mit 
3 Comparatoren und 80 Slices auch größer als die andere mit 2 
Comparatoren und 64 Slices. Hat die "langsame" eigentlich gar keinen 
MUX?

Queck Silber schrieb:
> Hat die "langsame" eigentlich gar keinen MUX?
Wundert mich auch sehr...   :-/

MGA schrieb:
> Die langsame Version brauch auch keinen Muxer. Es wird doch nur
> folgendes erzeugt:
>
>   +----+
> a-|    |   +----+
>   |a>b |-h-|    |
> b-|    |   |h>c |-m
>   +----+ c-|    |
>            +----+

Mit dem Resultat des Vergelichs a>b hast Du h noch nicht. Die Auswahl 
aus a und b macht dann eben der besagte Muxer mit dem Vergleichsresultat 
am Selektionseingang...

Weil dieser Thread irgendwo zitiert wurde ... hier meine Lösung ohne 
Addierer oder Vergleichsoperator.

Auf einem Artix werden nur 17 LUTs belegt, keine FFs oder sonst was, gut 
IOs noch.

Und geht leider nur mit Unsigned Zahlen, also ohne Vorzeichen.

Gustl B. schrieb:
> hier meine Lösung ohne Addierer oder Vergleichsoperator.

1

process(ab)

2

  begin

3

  for I in 0 to 7 loop

4

    a_xor_b(I) <= ab(I) XOR ab(I+8);

5

  end loop;

6

end process;

Bringt das Ressourcen- oder Geschwindigkeitsvorteile gegenüber dem hier:

1

    a_xor_b <= a XOR b;

Und bringt diese Lösung gegenüber einer Addiererlösung dann auch 
Vorteile?

> Auf einem Artix werden nur 17 LUTs belegt
Dank der 6er-LUT ist das eigentlich nicht weiter erstaunlich: du 
brauchst für einen 8-fach Vergleicher (höchstens) 4 
hintereinandergeschaltete LUTs, für den Multiplexer brauchst du 8 LUTs. 
Der restliche Aufwand ist vermutlich der Laufzeitoptimierung zu 
verdanken...

BTW: oben hatten wir es mit einem Maximum aus 3 Werten zu tun. Man muss 
deine Lösung also 2 mal implementieren und "hintereinanderschalten".

Lothar M. schrieb:
> Bringt das Ressourcen- oder Geschwindigkeitsvorteile gegenüber dem hier:

Glaube ich nicht, war mir nur nichtmehr sicher ob man XOR direkt mit 
Vektoren verwenden kann.

Lothar M. schrieb:
> Und bringt diese Lösung gegenüber einer Addiererlösung dann auch
> Vorteile?

Nein. Ich hab das auch zuerst für C geschrieben wo keine if else und 
Addition erlaubt waren sondern es eine Pipeline werden sollte. In VHDL 
ist das relativ sinnlos, das stimmt. Ich fand die Idee mit dem 
Prioritätsencoder ganz nett um das MSB des XOR(a,b) zu finden.

Lothar M. schrieb:
> BTW: oben hatten wir es mit einem Maximum aus 3 Werten zu tun. Man muss
> deine Lösung also 2 mal implementieren und "hintereinanderschalten".

UPS sorry für Off-Topic.

Gustl B. schrieb:
> Ich fand die Idee mit dem Prioritätsencoder ganz nett um das MSB des
> XOR(a,b) zu finden.
Da hätte ich auch noch ein paar Ansätze... ;-)
http://www.lothar-miller.de/s9y/archives/55-Finde-das-MSB.html

> UPS sorry für Off-Topic.
Naja, ein wenig passt es ja noch...

Reschpekt! Das sind schöne Möglichkeiten in VHDL. Damals war ich auf der 
Suche nach dem MSB in C. Irgendwie gibt es da keine so elegante Lösung 
wenn man auf if und else verzichten muss. So als kompletter CPU-Laie 
hatte ich auch erstmal erwartet, dass aktuelle Befehlssätze so eine 
Funktion schon eingebaut haben.