Unerwartetes Syntheseergebnis (??)

[Andy L. (nemai)]

Hi,

mein "Problem" ist, dass mir Quartus bei der Synthese meines AES-Designs 
etwas völlig kontraintuitives, wie mein Dozent zu sagen pflegt, liefert.

Ein Codeschnipsel:

function SubstitutionBox(input: in std_logic_vector(7 downto 0)) 
    return std_logic_vector is
    variable temp: std_logic_vector(7 downto 0);
begin
    case input is
      when x"00" => temp := x"63";
      when x"01" => temp := x"7c";
      when x"02" => temp := x"77";
      when x"03" => temp := x"7b";
      when x"04" => temp := x"f2";
      ........
      when x"fd" => temp := x"54";
      when x"fe" => temp := x"bb";
      when x"ff" => temp := x"16";
      when others => null;
    end case;
    return temp;
end function SubstitutionBox;





  process(CLK,RES_N) is
    type sub_state_type is (idle, sub1, sub2, sub3);  
    variable sub_state : sub_state_type;
    variable work : matrix_128bit;
  begin
    if RES_N = '0' then
      sub_state := idle;
      BUSY <= '0';
    elsif rising_edge(CLK) then
      case sub_state is
        when idle => 
          if ENA = '1' then
            work := DATA_IN;
            --BUSY <= '1';
            work(0) := SubstituteVector(work(0));
            work(1) := SubstituteVector(work(1));
            work(2) := SubstituteVector(work(2));
            work(3) := SubstituteVector(work(3));
            
            DATA_OUT <= work;
            
            --sub_state := sub1;
          end if;
--        when sub1 =>
--          work(1) := SubstituteVector(work(1));
--          sub_state := sub2;
--        when sub2 =>
--          work(2) := SubstituteVector(work(2));
--          sub_state := sub3;
--        when sub3 =>
--          work(3) := SubstituteVector(work(3));
--          DATA_OUT <= work;
--          BUSY <= '0';
--          sub_state := idle;
--      end case;
    end if;
 end process;

Oben meine Implementierung der AES S-Box mit 256 Einträgen, unten die 
Anwendung. Parallel auf 16 Byte. (matrix_128bit == 4 x vector_32bit == 4 
x slv8)

Nun müsste mir Quartus doch eigentlich 16 mal eine riesige logische 
Lookuptable auf den FPGA ballern. Ich habe auch in meiner Referenz zu 
einer AES Implementierung in VHDL gelesen, dass allein der vollparallele 
Substitutionsschritt so ca. 25000LE einnimmt.

Jetzt bin ich aber schwer verwundert, denn mein Gesamtdesign liegt bei 
schlappen 4988LE mit 734 Registern. Wenn ich im Syntheseergebnis etwas 
nachforsche, sehe ich, dass Quartus mir für jede Funktion 
SubstitutionBox ein "sync ram" angelegt hat. Müsste dieser aber nicht 
M4K Blöcke belegen? Denn deren Verbrauch liegt bei 0.

Man erkennt auch, dass der untere Teil ein schlampiger Automat ist. 
Eigentlich hatte ich die 4 Substitutionen auf 4 Takte verteilt, weil ich 
mir dachte, dann brauch ich parallel nur 4 mal die S-Box um Logik zu 
sparen. Aber es macht überhaupt keinen Unterschied, ob ich aufteile oder 
nicht - im Gegenteil, so brauche ich ca 150 Register weniger.

Alles in allem verstehe ich es nicht ganz. Es läuft auf der Hardware, 
ist aber irgendwie winzig klein. Kann mir jemand was dazu sagen?

Gruß

[Klaus (Gast)]

Das kannst du rausfinden, in dem du dir den RTL-Schematic anschaust. 
Dann siehst du genau, was die Synthese daraus gebastelt hat.

[Schlumpf (Gast)]

Andy L. schrieb:
> Nun müsste mir Quartus doch eigentlich 16 mal eine riesige logische
> Lookuptable auf den FPGA ballern.

Ich kann grad nicht erkennen, wie du auf die 16 kommst..

Ich sehe "nur" eine Umsetzung von 8 Bit auf 8 Bit in deiner 
"Substituion", welche dann 4 mal verwendet wird.

[progger (Gast)]

Was ist mit dem "when others" in der statemachine für sub-state?

[Schlumpf (Gast)]

progger schrieb:
> Was ist mit dem "when others" in der statemachine für sub-state?

Und welcher der vier definierten States soll denn mit Others gemeint 
sein???

[Andy L. (nemai)]

Schlumpf schrieb:
> Ich kann grad nicht erkennen, wie du auf die 16 kommst..
>
> Ich sehe "nur" eine Umsetzung von 8 Bit auf 8 Bit in deiner
> "Substituion", welche dann 4 mal verwendet wird.

Entschuldige, ich habe das schlampig beschrieben. Die Funktion 
SubstituteVector setzt einen Vector von 4 8-bit SLV um. Da diese 4 mal 
dort drin steht, komme ich insgesamt auf 16 Substitutionen.

Klaus: Genau dort hab ich herausgefunden, dass mein Design voller 
SYNC_RAMs ist, aber das ist keine Erklärung zu meinem "Problem".

Mich verwundert viel mehr, dass es zwischen den beiden Versionen des 
Automaten (der aktuellen und der auskommentierten) kaum einen 
Unterschied im Logikverbrauch gibt, obwohl es gerade vollparallel und 
vorher halb sequentiell war.
Auch verbrauche ich keinerlei Speichermöglichkeiten obwohl ich die 
ganzen besagten SYNC_RAMs drin habe - das ist, was mich am meisten 
"stört".

Gruß :-)

[berndl (Gast)]

aehm, ich verstehe das vlt. falsch, aber in deiner function machst du 
aus deinem 8-bit Eingangsvektor einen anderen 8-bit Ausgangsvektor. Wenn 
die Synthese das jetzt mit RAM in der LUT (bei Xilinx heisst das 
'distributed RAM') aufbaut, dann passiert folgendes:
* 16bit Ausgangsvektor passen in eine LUT (bei 4fach LUT)
* -> 16 LUTs koennen ein Bit des Ausgangsvektors abspeichern
* --> 16x8 LUTs speichern alle 256x8 Bit ab
* ---> dahinter noch 8 mal einen 16:1 Multiplexer (einer pro Bit)

Du kommst 'pro Funktionsaufruf' also auf 128 (=16x8) LUTs sowie die paar 
LUTs fuer den 16:1 Mux. Und den baust du in deinem Code oben 4 mal ein. 
Macht also 512 LUTs plus die Muxerei...

[Schlumpf (Gast)]

Ah verstehe.. hätte ich aber auch selber draufkommen können, dass die 
Funktionsnamen ja nicht identisch sind.

Nun, ich denke mal, dass die Synthese da über Distributed Memories was 
zusammengebastelt hat. Und die gehen zu Lasten der LUTs und nicht der 
Memory-Blöcke.

Und anhand deiner Beschreibung würde ich behaupten, dass die Synthes in 
beiden Fällen eine "Vollparallele" Umsetzung macht.
In dem einen Fall eben alles in einem State und in dem auskommentierten 
eben eine parallele Struktur, bei der halt einzelne Pfade bei 
unterschiedlichen Bedingungen "arbeiten".. aber parralel bleibt die 
Struktur dennoch.. so oder so.

[Andy L. (nemai)]

Ah okay, es kommt etwas Licht ins Dunkel :-)

@berndl: Habe die Rechnung leider nicht abschließend verstanden, da ich 
schon nicht ganz weiß, worauf du dich mit einem 16bit Vektor beziehst, 
aber ich verstehe so die Grundaussage in etwa.

@Schlumpf: Wie gesagt, ich habe mir vorgestellt, dass es weniger 
verbraucht, wenn ich 4 große Substitutionsboxen habe und die rundenweise 
vermuxe, als gleich 16 zu bauen - aber da ist das Synthesetool wohl 
anderer Meinung.

Komisch finde ich es dennoch - ich habe mit diesem AES-Prozessor an 
einer englischsprachigen Masterthesis zur gleichen Thematik Maß 
genommen. Dort wurde das komplette 16-schrittige Verfahren für eine AES 
Blockgröße von 128bit in ca. 43000LEs one-way (also nur Verschlüsselung 
allein) realisiert. Daher habe ich so eine gewisse Grundskepsis, wenn 
ich für das Gleiche gerade nur ein Zehntel der Logik brauche. Es ist für 
mich auch gerade schwierig in Hardware 3x128 std_logics von außen zu 
steuern / zu lesen.
Ich arbeite übrigens auf einem Altera Cyclone II.

Aber gut, ich danke erst mal allen für die Tipps; wenn noch jemand gute 
Ideen dazu hat nur zu :-) Ich werde das Design die Woche nochmal an der 
Uni durch Precision jagen und mal schauen, was das im Komplettsystem 
daraus macht.
Falls es dort große Erkenntnisse gibt, melde ich mich nochmal.

Gruß ;-)

[Schlumpf (Gast)]

Andy L. schrieb:
> @Schlumpf: Wie gesagt, ich habe mir vorgestellt, dass es weniger
> verbraucht, wenn ich 4 große Substitutionsboxen habe und die rundenweise
> vermuxe, als gleich 16 zu bauen - aber da ist das Synthesetool wohl
> anderer Meinung.

Wenn du das Rundenweise willst, dann musst du das auch so beschreiben.
Also deinen Eingangsvektor über einen Mux an deine Substitutionsbox in 
Abhängigkeit des Zustands der FSM schalten. Und ebenso den 
Ausgangsvektor.

Die Synthese ist da nicht anderer Meinung, sondern sie synthetisiert 
das, was du beschrieben hast. Es ist eher so, dass dein Code nicht das 
repräsentiert, was du gerne hättest ;-)

[berndl (Gast)]

Andy L. schrieb:
> Habe die Rechnung leider nicht abschließend verstanden, da ich
> schon nicht ganz weiß, worauf du dich mit einem 16bit Vektor beziehst,
> aber ich verstehe so die Grundaussage in etwa.

also, du gehst mit einem 8-Bit breiten Vektor in deine function, 
lieferst also '256 Adressen' und erwartest '256 Datenvektoren zur 
Auswahl, jeweils 8-Bit breit'.

Eine LUT kann als RAM/ROM 16 Bit abspeichern (bei LUT mit 4 Adressbits, 
bei einem Spartan6 mit 6 Adr-Bits eben 64 Bit). 16 LUTs (4-fach) koennen 
also alle 256 Bits fuer einen deiner 8 Ausgangsvektoren speichern (dein 
Returnwert ist ja ein slv 7:0). Also koennen in 16x8 LUTs alle deine 
Ausgangsdaten abgespeichert werden.
Diese 16x8 LUTs musst du jetzt mit acht 16:1 Multiplexern verarbeiten um 
das gewuenschte Ergebnis zu bekommen. Jetzt haengt diese Mux-Logik halt 
davon ab, was so ein Logic-Element kann: Wenn ein LE einen 4:1 Mux 
realisieren kann, dann sind das halt vier 4:1 Muxe gefolgt von einem 
weiteren 4:1 Mux pro Ausgangsbit, also dann (4+1)x8 LEs fuer die Muxerei 
pro Instanz. Bei 2:1 Mux pro LE halt dann (8+4+2+1)x8 LEs pro Instanz.

Ein Problem in deiner Beschreibung verursacht auch noch einen uebel 
hohen Fan-Out deiner Addresse (4 von den 8 Bit des Eingangsvektors): Die 
16x8 LUTs, die deine Ausgangsdaten (pro Instanz) speichern, muessen von 
4 Adressbits gesteuert werden. Also ein Fan-Out von 128 fuer 4 Bits 
deines Eingansvektors. Und dafuer wird es sicherlich noch zusaetzliche 
Buffer/Route-through LEs brauchen. Ist dann aber auch eine Frage der 
gewuenschten Taktfrequenz...

[berndl (Gast)]

Schlumpf schrieb:
> Ah verstehe.. hätte ich aber auch selber draufkommen können, dass die
> Funktionsnamen ja nicht identisch sind.

Wieso? Die Funktion oben wird 4 mal aufgerufen. Nur der Parameter ist 
jeweils unterschiedlich. Und wenn das im gleichen Takt 4 mal aufgerufen 
wird, dann wird das auch 4 mal eingebaut

> Nun, ich denke mal, dass die Synthese da über Distributed Memories was
> zusammengebastelt hat. Und die gehen zu Lasten der LUTs und nicht der
> Memory-Blöcke.

So wie's oben steht (4 Aufrufe der Funktion in einem Takt) geht es nur 
entweder mit 4x distributed RAM oder auch z.B. mit 2x Dual Port embedded 
RAM (BRAM bei Xilinx). Wenn es zeitlich entzerrt wird, dann ginge auch 
jeweils 1 Instanz mit distributed RAM oder embedded RAM. Was sich mit 
embedded RAM entspannen wuerde waere das Fan-Out Problem. Aber das 
entscheidet das Synthesetool halt so oder so, eben auch abhaengig von 
den Timing-Anforderungen...

[Schlumpf (Gast)]

Andy L. schrieb:
> @Schlumpf: Wie gesagt, ich habe mir vorgestellt, dass es weniger
> verbraucht, wenn ich 4 große Substitutionsboxen habe und die rundenweise
> vermuxe, als gleich 16 zu bauen - aber da ist das Synthesetool wohl
> anderer Meinung.

Wenn du das Rundenweise willst, dann musst du das auch so beschreiben.
Also deinen Eingangsvektor über einen Mux an deine Substitutionsbox in 
Abhängigkeit des Zustands der FSM schalten. Und ebenso den 
Ausgangsvektor.

Die Synthese ist da nicht anderer Meinung, sondern sie synthetisiert 
das, was du beschrieben hast. Es ist eher so, dass dein Code nicht das 
repräsentiert, was du gerne hättest ;-)

berndl schrieb:
> Wieso? Die Funktion oben wird 4 mal aufgerufen. Nur der Parameter ist
> jeweils unterschiedlich. Und wenn das im gleichen Takt 4 mal aufgerufen
> wird, dann wird das auch 4 mal eingebaut

Funktionsname : SubstitutionBox
Aufgerufene Funktion : SubstituteVector

FSM ruft SubstituteVector 4 mal auf und SubstituteVector ruft 
SubstitutionBox vier mal auf.. und genau das war nicht klar.
Irgendwie graut´s mir, wenn ich "Funktionsaufruf" bei snthetisierbarem 
VHDL lese oder sogar selber schreibe gg

[berndl (Gast)]

Schlumpf schrieb:
> Funktionsname : SubstitutionBox
> Aufgerufene Funktion : SubstituteVector

ups, das hatte ich uebersehen...

> FSM ruft SubstituteVector 4 mal auf und SubstituteVector ruft
> SubstitutionBox vier mal auf.. und genau das war nicht klar.
> Irgendwie graut´s mir, wenn ich "Funktionsaufruf" bei snthetisierbarem
> VHDL lese oder sogar selber schreibe gg

dito!

[Schlumpf (Gast)]

berndl schrieb:
> ups, das hatte ich uebersehen...

ging mir zuerst auch so.. deswegen mein Kommentar:

Schlumpf schrieb:
> Ah verstehe.. hätte ich aber auch selber draufkommen können, dass die
> Funktionsnamen ja nicht identisch sind.

[berndl (Gast)]

Hilft dann natuerlich ungemein, wenn genau die function oben im 
Code-Schnippsel nicht dabei ist... (Zeige- oder Mittelfinger :o) heb)!

[Schlumpf (Gast)]

.. das war doch nur ein Test, ob wir alle aufmerksam bei der Sache sind 
;-)

[Andy L. (nemai)]

Für den Seelenfrieden ;-)

type vector_32bit is array (0 to 3) of std_logic_vector(7 downto 0);
type matrix_128bit is array (0 to 3) of vector_32bit;

function SubstituteVector(data : in vector_32bit) return vector_32bit is
    variable temp : vector_32bit;
  begin
    for i in 0 to 3 loop
      temp(i) := SubstitutionBox(data(i));
    end loop;  
    return temp;
  end function;

Ich gebe euch Recht, dass die beiden Dinge gefehlt haben - aber Schlumpf 
hat natürlich auch Recht, das war ein Test ;-P


Gruß


PS: Danke für die ausführliche Erklärung berndl :-)

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Schlumpf schrieb:
> Irgendwie graut´s mir, wenn ich "Funktionsaufruf" bei snthetisierbarem
> VHDL lese oder sogar selber schreibe
Und Schleifen und Variablen ohne Not...   :-o
Hier darf/muss/soll ganz offensichtlich ein Softie Hardware 
beschreiben.

Es wäre allemal klarer und "VHDL-mäßiger", wenn diese Elemente einfach 
als Komponente implementiert und händisch verdrahtet werden würden.

Andy L. schrieb:
> Nun müsste mir Quartus doch eigentlich 16 mal eine riesige logische
> Lookuptable auf den FPGA ballern.
Lokkup-Tabellen werden nicht  als "riesige Logik" ausgeführt, sondern am 
besten als RAM (sogar die "kleine" LUT4 oder LUT6 im FPGA ist ein 16x1 
oder 64x1 RAM). Und solche Elemente können dann (wie schon ausführlich 
erläutert) eben auch als RAM parallelgeschaltet und als größeres RAM 
verwendet werden. Nur dann, wenn die Synthese meint, die LUT könnte 
einfacher kombinatorisch ausgeführt werden, dann wird Kombinatorik draus 
(z.B. wenn im RAM ein Zusammenhang zwischen Adressen und Daten erkennbar 
ist).

> wie mein Dozent zu sagen pflegt
Nur interessehabler: Was pflegt denn der Dozent ausserdem noch zu tun?

[Andy L. (nemai)]

Lothar:
Ich erachte "Softie" mal nicht als Beleidigung.

Was würdest du sagen, wenn ich behaupte, dass ich Elektrotechniker mit 
Spezialisierung Technische Informatik / Digitale Systeme bin? :-)

Mein Dozent übrigens ebenso.

[Schlumpf (Gast)]

Andy L. schrieb:
> Spezialisierung Technische Informatik / Digitale Systeme

Aber das sind doch genau die 'Softies' :-)

Denke auch nicht, dass Lothar das abwertend gemeint hat, sondern man 
kann halt am VHDL-Stil schon oft erkennen, ob der Verfasser eher die SW- 
oder die HW-Brille auf hatte.

[Andy L. (nemai)]

Schlumpf schrieb:
> Denke auch nicht, dass Lothar das abwertend gemeint hat

In meinem akademischen Umfeld ists ne schwere Beledigung; da der Lothar 
gerade da vermutlich aber nicht herkommt, sehe ichs ihm wie gesagt nach.

Wenn ich aber als "Softie" gelte, so frage ich mich, was noch 
hardwareorientierteres man studieren/lernen könnte, um in euren Augen 
"richtiges" VHDL zu schreiben. Stumpfe Ausbildung zum VHDL-Coder? ;-)

Auch frage ich mich, was gegen Schleifen spricht. "Verdrahte mal 
händisch" die Transponierung eines beliebig großen Matrix-Datentyps. 
Entweder so viele Zeilen wie die Matrix Plätze hat oder 3 Zeilen mit 2 
Schleifen. Dass die Schleife nur vom Compiler aufgerollt wird ist mir 
auch klar. Die ist doch nur n Mittel, das Übersichtlichkeit und Faulheit 
unterstützt.

[Marius W. (mw1987)]

Es spricht zunächst mal nichts gegen Schleifen. Nur muss man genau 
wissen, was eine Schleife in VHDL macht. Die baut nämlich schön 
parallele Hardware. Und das kann dann so weit ausarten, dass dir selbst 
eine vermeintlich "simple" Rechnung schnell den FPGA voll und seeehr 
langsam macht.

Gruß
Marius

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Ich meine "Softie" nicht abwertend, aber man sieht sofort, ob eine 
sequenzielle Programmier-Denkweise hinter einer Hardwarebeschreibung 
steckt, oder eben eine parallele Schaltungs-Denkweise.

> In meinem akademischen Umfeld ists ne schwere Beledigung; da der Lothar
> gerade da vermutlich aber nicht herkommt, sehe ichs ihm wie gesagt nach.
Ich wusste leider nicht, dass deine Füsse (und die deiner Kollegen) so 
lang sind. Sonst wäre ich dir sicher nicht draufgetreten...   :-o
Vielleicht beruhigt es dich, wenn ich dir sage, dass unsere "Softies" 
(ich setz das jetzt besser mal in Hochkommas)  ähnlich neckische 
Begriffe für Hardwareentwickler haben. Siehst du: man lernt nie aus. 
Weder ich noch du...

Zurück zur Sache:
Du kannst in VHDL hinschreiben was du willst, nur mutiert ein 
(geschachtelter) Funktionsaufruf wegen seiner Unscheinbarkeit einfach 
eher zu einem nicht handhabbaren Logikmonster. Wenn dir das bewusst ist, 
dann bitte: nur zu.

Gegen eine Schleife spricht z.B. dass mit so einer Schleife kein 
embeddedRam oder Blockram gebaut und angesprochen werden kann, weil in 
einem echten Ram eben nicht auf alle Speicherzellen gleichzeitig 
zugegriffen werden kann.

Und: technische Informatiker sind "Softies". Wie ist bei deinem Studium 
das Verhältnis Hardware (=Schaltungstechnik) zu Software/Systemtechnik?

[Andy L. (nemai)]

Entschuldige, wenn ich vorhin etwas ruppig reagiert habe; war noch wegen 
etwas anderem ultragenervt und hab das nicht richtig schubladisiert.

Zu deinem Schleifenargument: Ich kann mir spontan ehrlich gesagt auch 
keinen RAM vorstellen, den man in einer Schleife baut. Ich würde in 
meiner jugendlichen Naivität sogar glauben, dass das eine mit dem 
anderen kaum etwas zu tun hat (?)

Zum Verhältnis: Schwer zu sagen, da vieles in meinem Wahlbereich weder 
dem einen noch dem anderen zuordenbar ist. (z.B. 
Halbleitertechnik&Photovoltaik, ich bin eine bunte Mischung) Ansonsten 
ists relativ ausgewogen, ich hab mit Software eigentlich nicht arg viel 
am Hut. 2 Semester Programmieren muss jeder durch ..aber sonst ist 
eigentlich recht technisch. TI selbst ist natürlich Systemtechnik.