std_logic Rotation

[Ralf (Gast)]

Hallo zusammen,

ich habe einen 24-bit Vektor.
Dieser beinhaltet immer ein Paket von zusammenhängenden Einsen. Die 
Anzahl der Einsen ist variabel von 0 bis 24.

Nun möchte ich dieses Paket von Einsen nach links rotieren lassen.
Also habe ich folgendes in einem getakteten process geschrieben.

rotation_vektor <= rotation_vektor(rotation_vektor'HIGH-1 downto rotation_vektor'LOW) & rotation_vektor(rotation_vektor'HIGH);

Nun möchte ich die Anzahl der Einsen vergrößern bzw. verkleinern und 
zwar immer so, dass die Einsen am rechten Ende das Paketes dazu- oder 
wegkommen.
Nun kommt das Entscheidende:
Ich möchte/muss die Lage des Paketes mit der neuen Anzahl von Einsen 
nicht neu festlegen, sondern die Rotation soll wie gewohnt weiter gehen, 
nur eben im kommenden Takt mit ein paar Einsen mehr oder weniger.

Ich müsste also irgendwie das rechte Ende das Paketes finden und dann 
die Einsen dranhängen oder abziehen. Dazu habe ich leider noch keine 
sinnvolle Idee gefunden.

Oder könnte man vielleicht ein Signal mit nur Einsen mit variabler 
Länge, nämlich der Anzahl von Einsen, durch den 24-bit Vektor schieben?

Vielen Dank!
Ralf

[Spartanist (Gast)]

Beschreibe das mal beispielhaft in einer Grafik, damit wir wissen, was 
Du tun willst.

[berndl (Gast)]

z.B. indem du einen 'head' und einen 'tail' pointer baust. Der 'head' 
wird einfach mit inkrementiert, der 'teil' hat dann halt inkrement sowie 
addition/subtraktion dabei.
Wenn du das einmal richtig initialisierst laeuft das spaeter auch 
einfach so mit und gibt dir die Start/Endeposition des Einserblocks 
an...

[Ralf (Gast)]

Hallo,

Spartanist schrieb:
> Beschreibe das mal beispielhaft in einer Grafik, damit wir wissen, was
> Du tun willst.

hier mal ein Bsp mit 12bit:

000000001111 (Anzahl = 4)
000000011110
000000111100
000001110000 (neue Anzahl = 3)
000011100000
000111000000
001111110000 (neue Anzahl = 6)
011111100000
111111000000
111110000001
000000000010 (neue Anzahl = 1)
000000000100

Die linke 1 wird also immer ein Bit weiter nach links geschoben, während 
sich die Anzahl der Einsen dahiner ändern kann.

Die Begriffe 'head' und 'tail' pointer höre ich das erste Mal, ich 
versuche mal etwas darüber herauszufinden.

Vielen Dank!
Ralf

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

Ich würde da eine einzige '1' durchschieben, und hinterher die übrigen 
Einsen "anhängen". Das Ganze gibt dann einen Riesenmonstermultiplexer...

[berndl (Gast)]

eigentlich sind das doch nur read/write pointer eines FIFOs, ok, mit 
etwas Zusatzlogik.
Die Anzahl der Einsen kriegt man dann durch einfache Subtraktion raus

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

Aber der Trick ist, dass das nach der bisherigen Beschreibung offenbar 
in 1 Takt erledigt werden muss, und man sich den Ergebnisvektor nicht in 
bis zu 24 Takten "zusammenbasteln" kann...

Hier mal meine Lösung:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity SRvarOnes is
    Port ( clk    : in  STD_LOGIC;
           Ones   : in  STD_LOGIC_VECTOR (4 downto 0);
           Output : out  STD_LOGIC_VECTOR (23 downto 0));
end SRvarOnes;

architecture Behavioral of SRvarOnes is
  signal mastersr : std_logic_vector (23 downto 0) := x"000001";
begin
  mastersr <= mastersr(22 downto 0) & mastersr(23) when rising_edge(clk);

  process 
  variable einser : integer range 0 to 24;
  variable sr : std_logic_vector (23 downto 0);
  begin
    wait until rising_edge(clk);
    sr     := (others=>'0');  -- default: Alles Nullen
    einser := to_integer(unsigned(Ones));
    if (einser /= 0) then     -- wenn mindestens 1 Einser
      sr     := mastersr;
      einser := einser-1;
      for i in sr'range loop  -- 24 Bits durchmachen ...
        if (einser/=0) then   -- ... aber nur, wenn noch Einser aufzufüllen sind
          sr     := sr or (sr(0) & sr(23 downto 1)); 
          einser := einser-1;                    
        end if;
      end loop;
    end if;
    Output <= sr;
  end process;
end Behavioral;

Wenn natürlich nicht in jedem Quarz-Takt um eins weitergeschoben und 
der neue Registerwert berechnet werden muss, dann ist jede andere Lösung 
einfacher und ressourcensparender...

[Ralf (Gast)]

DANKE alle zusammen und vor allem Lothar!!!

Ich hatte in der Zwischenzeit mit den HEAD und TAIL Pointern gearbeitet 
und im Ansatz eine Lösung erarbeitet, hatte nur noch Probleme mit dem 
"Überlauf" auf die Stelle 0, weil dann der HEAD Pointer auf einmal 
kleiner war als der TAIL Pointer... wärhend ich darüber gegrübelt hatte, 
wollte ich mir Lothar's Lösung anschauen und bin begeistert.

Ich möchte nur noch eine Frage an Lothar loswerden:
Wie kommt man aus dem Stehgreif auf so eine Lösung?
Wenn man sich den Code anschaut und Schritt für Schritt durchgeht, 
versteht man alles und es ist logisch.
Aber ich würde aktuell nie alleine auf eine solche Lösung kommen.
Nur immer eine 1 durchshiften und dann immer mit der Rechtsrotation und 
der OR Verknüpfung die umliegenden Stellen bestimmen... mega gut!

Ich glaube da muss ich meine Synapsen noch etwas in dieser Richtung 
trainieren, um auch irgendwann eine solche Lösung erarbeiten zu können.

Vielen, vielen Dank!

[T. M. (xgcfx)]

Lothar Miller schrieb:
> mastersr <= mastersr(22 downto 0) & mastersr(23) when rising_edge(clk);

Hoppla, das geht ja wirklich durch die Synthese. Rein syntaktisch ist 
das klar, aber ich hätte nicht gedacht, dass das funktioniert.
Schön kurze Beschreibung eines Registers :)

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

T. M. schrieb:
> Hoppla, das geht ja wirklich durch die Synthese. Rein syntaktisch ist
> das klar, aber ich hätte nicht gedacht, dass das funktioniert.
Geht auch erst seit diesem Jahrzehnt...   ;-)

Ralf schrieb:
> Ich möchte nur noch eine Frage an Lothar loswerden:
> Wie kommt man aus dem Stehgreif auf so eine Lösung?
Man hat ca. 400 mehr oder weniger kleine Testprojekte auf der Platte, 
von denen ca. 2/3 funktionieren...  ;-)

[Ralf (Gast)]

Lothar Miller schrieb:

for i in sr'range loop  -- 24 Bits durchmachen ...
         if (einser/=0) then
           sr     := sr or (sr(0) & sr(23 downto 1)); 
           einser := einser-1;                    
         end if;
       end loop;

Sehe ich das richtig, das die Laufzeit mit der Anzahl der Einsen 
variiert? Also je mehr EInsen vorhanden sind, umso mehr Gatter werden 
durchlaufen?

Ich versuche nun rein interesse halber, den Code mal auf vielleicht 2 
Takte auszubauen, um ihn ressourcenschonender zu machen.
Laut Quartus sind es aktuell ca. 5000 Gatter...

Vielen Dank!
Ralf

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

Ralf schrieb:
> Sehe ich das richtig, das die Laufzeit mit der Anzahl der Einsen
> variiert? Also je mehr EInsen vorhanden sind, umso mehr Gatter werden
> durchlaufen?
Nein, das Ganze wird sowieso optimiert und parallel aufgebaut. Sieh dir 
einfach den RTL-Plan an...

> Ich versuche nun rein interesse halber, den Code mal auf vielleicht 2
> Takte auszubauen, um ihn ressourcenschonender zu machen.
Na bitte, schon das 2. Projekt. Dieser Prozess nennt sich "Lernen".
Weiter so... ;-)

[Ralf (Gast)]

Lothar Miller schrieb:
> Nein, das Ganze wird sowieso optimiert und parallel aufgebaut. Sieh dir
> einfach den RTL-Plan an...

Das habe ich versucht. Da spuckt mir Quartus 164 Seiten schematic aus, 
mit wild verschalteten Elementen, die mir die Interpretations des 
Syntheseergebnisses nicht gerade einfach machen. :-)

Ich glaube ich vertraue erstmal Quartus mit den "Total logic elements" 
und freue mich, wenn ich die Funktion auch mit zwei Takten Delay 
hinbekomme und dafür vielleicht nur 1200 Zellen benötige.

Ich werde meinen Fortschritt wieder hier posten.

Vielen Dank!

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

Ralf schrieb:
> Da spuckt mir Quartus 164 Seiten schematic aus
Klar: viel Logik braucht viel Platz...  ;-)

[Ralf (Gast)]

Mir fällt gerade auf, dass ich statt einem Delay von zwei Takten, eine 
Pipeline mit zwei Takten Latenz brauche.

Ich müsste also am Ausgang mit jedem Takt ein Ergebnis haben, dass eben 
nur dem Eingang von vor zwei Takten entspricht. Das dürfte einen 
komplett anderen Dankansatz erfordern, als die Lösung von Lothar 
hergibt. Denn ich habe gerade keine Idee, wie ich innerhalb von zwei 
Takten eine Eins in dem Vektor rotieren lassen kann.

Das vereinfacht die Sache nicht gerade, aber ich versuche mal mein Glück 
:)

Vielen Dank!
Ralf

[Uwe (Gast)]

> Denn ich habe gerade keine Idee, wie ich innerhalb von zwei
> Takten eine Eins in dem Vektor rotieren lassen kann.
Riesigen Multiplexer bzw. Barrel Shifter bzw. Hardwaremultiplizierer 
lassen sich als Barrelshifter benutzen.
Du könntest aber auch einfach den Takt mit nem PLL vervielfachen und das 
Desdign von Lthar mit einer n mal höheren Clock als das restliche Design 
laufen lassen.

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

Uwe schrieb:
> Desdign von Lothar mit einer n mal höheren Clock
> als das restliche Design laufen lassen.
Tja, wenn das Monster das könnte. Ich habe nur 40MHz erreicht...  :-(

[Ralf (Gast)]

Der Takt sollte nicht das Problem sein, denn ich arbeite nur mit 25MHz. 
Dann schon eher die Ressourcen... ich möchte beide Varianten mal direkt 
vergleichen, was Platz und Latenz anbelangt...

[Ralf (Gast)]

Hallo,

ich habe jetzt den Prozess der OR-Verknüpfung geteilt, um damit eine Art 
Pipeline zu bauen, die dann einen Takt Latenz bringt.

Ich hatte erwartet, dass ich dadurch die Hälfte der Gatter einsparen 
kann. Nach der Simulation und beim Betrachten des Syntheseergebisses ist 
mir dann aber aufgefallen, dass bei einer Pipeline ja nichts eingespart 
werden kann, da ja die Gatter nötig sind, um dann wieder den nächsten 
Eingangswert zu bearbeiten.

Ich habe also die Hälfte der Gatter um den ersten Teil zu bearbeiten und 
die zweite Hälfte bearbeitet den letzten Teil in der Pipeline. dazu 
kommt noch die Glue-Logic der beiden Komponenten... in Summe ist es also 
noch mehr geworden.

Habe ich da noch irgendeinen Denkfehler, oder kann ich bei der 
Pipelinegeschichte partout keine Gatter einsparen?
Irgendwie sehe ich darin keinerlei Vorteile, weil ich jetzt eigentlich 
mit mehr Gattern einen Takt mehr Latenz habe... sehr sinnfrei ;-)

Wenn ich nur jeden zweiten Eingangswert bearbeiten müsste, könnte ich 
einsparen, aber so...

Ich habe den Eingangswert jetzt auf 23 Bit gekürzt...

mastersr  <= mastersr (21 downto 0) & mastersr (22) when rising_edge(CLK);

rotation1 : process (CLK)
  variable einser : integer range 0 to 23;
  variable sr : std_logic_vector (22 downto 0);
begin
  if rising_edge(CLK) then
   sr   := (others => '0');
     einser := conv_integer(Ones);
     if (einser /= 0) then
        sr   := mastersr ;
        einser := einser - 1;
        for i in 0 to 11 loop 
           if (einser/=0) then
              sr     := sr or (sr(0) & sr(22 downto 1)); 
              einser := einser - 1;                    
           end if;
        end loop;
     end if;
     s_sr <= sr;       -- Wert an rotation2 übergeben
   s_einser <= einser; -- Wert an rotation2 übergeben
  end if;  
end process;

rotation2 : process (CLK)
  variable einser : integer range 0 to 23;
  variable sr : std_logic_vector (22 downto 0);
begin
  if rising_edge(CLK) then
   sr   := s_sr;     -- Wert von rotation1 übernehmen
   einser := s_einser; -- Wert von rotation1 übernehmen
     if (einser /= 0) then -- wenn mehr als 11 Einsen im Eingangsvektor
        sr   := s_sr;
        for i in 0 to 12 loop
           if (einser/=0) then
              sr     := sr or (sr(0) & sr(22 downto 1)); 
              einser := einser - 1;                    
           end if;
        end loop;
     end if;
     Output <= sr;
  end if;  
end process;

[Ralf (Gast)]

Ich habe meinen Denkfehler gefunden:
Die Pipeline würde nur Sinn machen, wenn die beiden Teilaufgaben nicht 
in einem Takt abhandelbar wären, also meinetwegen bei 60MHz. Dann 
zerteilt man die Aufgabe und hat bei doppelter Fläche eine effektive 
Taktrate von 30MHz, aber bei jedem 60Mhz Takt dennoch ein Ergebnis am 
Ausgang mit einer Latenz von einem Takt.

Folgende Darstellung der Arbeitspakete:

Serielle Bearbeitung:
|  A  |  B  |  A  |  B  |

Pipeline mit doppelter Gatteranzahl:
      |  A  |  B  |  A  |  B  |
|  A  |  B  |  A  |  B  |

Man erkauft sich also mit doppelter Gatteranzahl und einem Takt Latenz, 
dass man dennoch mit jedem Takt ein Ergebnis erhält. "There's no free 
lunch!"

In meinem Fall sieht es so aus:
Lösung Lothar:
|  A  |  A  |  A  |  A  |
|  B  |  B  |  B  |  B  |

Lösung Lothar mit Pipeline:
      |  A  |  B  |  A  |  B  |
|  A  |  B  |  A  |  B  |

Ich habe also bei gleicher Gatteranzahl nur einen Takt Latenz dazu 
bekommen und habe dadurch keinen Vorteil.

Ich muss also wohl, wenn ich mit jedem Takt ein Ergebnis haben möchte, 
mit den 5k Gattern leben.

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

Was mich noch interessieren würde: Wofür braucht man  sowas?