So schreiben Sie die VHDL-Beschreibung eines einfachen Algorithmus: Der Steuerpfad

Nie wieder künstlich klingen: So schreiben Sie für’s Hören (Kann 2019).

$config[ads_text] not found
Anonim

So schreiben Sie die VHDL-Beschreibung eines einfachen Algorithmus: Der Steuerpfad


Steve Arar setzt seine VHDL-Serie mit dieser Diskussion über die Umwandlung eines einfachen Algorithmus in eine VHDL-Beschreibung fort - diesmal konzentriert er sich auf den Kontrollpfad-Teil eines digitalen Designs.

In meinem letzten Artikel habe ich beschrieben, wie man die VHDL-Beschreibung eines einfachen Algorithmus schreibt. Ich legte den Unterschied zwischen dem Datenpfad und dem Steuerpfad in digitaler Form fest und fuhr dann fort, in den Datenpfad einzutauchen. In diesem Artikel sehen wir uns stattdessen den Kontrollpfad an.

Dieser Artikel wird die Konvertierung eines einfachen Algorithmus in eine VHDL-Beschreibung überprüfen. Wir werden einen LCM-Algorithmus (Least-Common-Multiple) als Beispiel verwenden.

Überprüfung des Datenpfads

Im vorigen Artikel haben wir gesehen, dass wir zur Implementierung des Datenpfades des LCM-Algorithmus, der durch den Pseudocode in Listing 1 beschrieben wird, das in Abbildung 1 gezeigte Schema verwenden können.

Listing 1

 1 a=m 2 b=n 3 while (a != b) 4 { 5 if ( a < b ) 6 { 7 a=a+m 8 b=b 9 } 10 else 11 { 12 a=a 13 b=b+n 14 } 15 } 16 lcm=a 

Abbildung 1

Durch Anwenden der geeigneten Logikpegel auf den Auswahleingang der Multiplexer können wir auswählen, welche Operation ausgeführt wird. In diesem Artikel werden wir die Schaltung entwerfen, die ein entsprechendes "SEL" -Signal erzeugt, so dass der Datenpfad von 1 die Operationen durchführt, die benötigt werden, um das LCM der Eingänge zu berechnen.

Ändern des Pseudocodes, um die Beschreibung einer FSM anzupassen

In Fig. 1 muss das "sel" -Signal drei verschiedene Werte haben, so dass es einen der drei Eingänge zu dem Multiplexer auswählen kann. Daher ist es vernünftig zu erwarten, dass wir eine Drei-Zustands-FSM benötigen, wobei jeder Zustand einer der drei Eingaben entspricht, aber wir werden sehen, dass die FSM tatsächlich mit nur zwei Zuständen implementiert werden kann.

Der nächste Zustand der FSM wird basierend auf dem Ablauf des Algorithmus in Listing 1 gewählt. Der Ablauf des Algorithmus bezieht sich entweder auf die nächste Zeile oder auf einen bestimmten Punkt im Code, entsprechend dem "while" und "wenn" Strukturen. Um den Pseudocode von Listing 1 einer FSM-Beschreibung näher zu bringen, schreiben wir die while-Anweisung wie folgt um:

Listing 2

 1 a=m 2 b=n 3 if (a=b) 4 { 5 goto line 28 6 } 7 else 8 { 9 if ( a < b ) 10 { 11 a=a+m 12 b=b 13 } 14 else 15 { 16 a=a 17 b=b+n 18 } 19 } 20 if( a=b ) 21 { 22 goto line 28 23 } 24 else 25 { 26 goto line 9 27 } 28 lcm=a 

Diese neue Version verwendet "if-else" -Strukturen, um die "while" -Anweisung zu ersetzen; Dies erleichtert das Design der FSM für den Algorithmus. Die Bedingungen dieser "if" -Anweisungen können uns einige Hinweise auf die Bedingungen für die FSM-Übergänge von einem Zustand zu einem anderen geben.

Um den obigen Algorithmus praktikabler zu machen, werden wir einige andere Merkmale hinzufügen: Wir nehmen an, dass der LCM-Schaltkreis einen "Bereit" -Ausgang und einen "Start" -Eingang aufweist. Wenn der "Ready" -Ausgang logisch hoch ist, wissen wir, dass sich das System im "Leerlauf" -Modus befindet und bereit ist, an einem neuen Paar von Eingabewerten zu arbeiten. Das Setzen der "Bereit" -Ausgabe-Hoch bedeutet auch, dass die Schaltung das LCM der vorherigen Eingaben gefunden hat. Wenn wir also das Ende des Algorithmus erreichen, sollten wir den Ausgang "ready" auf logisch high setzen.

Wenn ein gültiges Paar von Eingangswerten an die LCM-Schaltung angelegt wird, setzen wir den Eingang "start" auf logisch hoch, um der Schaltung mitzuteilen, dass sie den Algorithmus starten soll.

Das ASMD-Diagramm eines Algorithmus

Um die VHDL-Beschreibung eines Algorithmus zu finden, können wir verschiedene Zustände des Steuerpfades in einem Diagramm namens ASMD zeichnen, das für Algorithmic State Machine mit einem Datenpfad steht. Das ASMD-Chart stellt nicht nur die FSM des Kontrollpfades dar, sondern beschreibt auch die Registertransferoperationen des Datenpfades. Wir werden den LCM-Algorithmus als ein Beispiel dafür verwenden, wie man das ASMD-Diagramm eines gegebenen Algorithmus herleitet.

Basierend auf unserer bisherigen Diskussion scheint es, dass wir eine FSM mit drei Zuständen verwenden sollten. Jeder Zustand der FSM kann den Wert der a- und b- Register aktualisieren, den Schaltungsausgängen einige Werte zuweisen, wie z. B. die "Bereit" -Ausgabe, und die Bedingungen der "if" -Strukturen prüfen, um den nächsten Zustand der FSM zu bestimmen. Alle diese Informationen können durch das ASMD-Diagramm des Algorithmus dargestellt werden.

Gehen wir mit dem LCM-Algorithmus fort: Wir nennen den Anfangszustand des Systems "Leerlauf". In diesem Zustand ist das System bereit, neue Eingangspaare zu akzeptieren, so dass "ready" auf high gesetzt ist. Wie in Abbildung 2 gezeigt, können wir ein Rechteck verwenden, um diesen Zustand darzustellen. Der Name des Zustands (dh "Leerlauf") wird über das Rechteck geschrieben, und die Zuweisung, die der "Bereit" -Ausgabe entspricht, wird innerhalb des Rechtecks ​​geschrieben.

Figur 3

Welche anderen Teile des Algorithmus in diesem Zustand "Start" -Eingang ausgeführt werden können, ist logisch niedrig, wir sollten die Berechnungen nicht starten, wahrscheinlich weil die Eingaben noch nicht gültig sind. Daher sollten wir für "Start" = "0" im "Leerlauf" -Zustand bleiben. Wenn "start" jedoch logisch hoch ist, sollten wir die Eingänge m und n in den a- bzw. b- Registern speichern und die Berechnungen starten. Wir können das Speichern von m und n im "Leerlauf" -Zustand durchführen.

Um bedingte Strukturen darzustellen, verwenden wir eine grüne Sechseckform. Für die bedingten Zuordnungen des Algorithmus verwenden wir eine rote Ellipse. Daraus erhalten wir:

Figur 4

Beachten Sie, dass die Zuordnungen zu Registern durch einen Pfeil angezeigt werden, z. B. ein ← m. Diese Notation wird verwendet, um zu betonen, dass solche Zuweisungen an der nächsten Taktflanke wirksam werden. Die Zuweisung, die der Ausgabe "bereit" entspricht, wird jedoch durch die Notation "<=" dargestellt. Dies bedeutet, dass, wenn wir im "Leerlauf" -Zustand sind, der "Bereit" -Ausgang immer logisch hoch ist, unabhängig vom Zustand der Uhr. Beachten Sie auch die gestrichelte Box in Abbildung 4, die angibt, dass alle diese Vorgänge im "Leerlauf" -Zustand ausgeführt werden.

Als nächstes erreichen wir die "if" -Anweisung von Zeile 3, die a und b vergleicht, um die nächste Operation zu bestimmen. Wenn a = b, ist der Algorithmus beendet und wir können den Wert von a dem Ausgang lcm zuweisen ; Dies kann in einem neuen Zustand geschehen. Es gibt jedoch noch eine andere Alternative: Wir können bedingungslos den Wert von a zu lcm zuweisen, aber den Wert von lcm nur dann berücksichtigen, wenn der Algorithmus beendet ist.

Mit anderen Worten, lcm ist nur gültig, wenn der "Bereit" -Ausgang hoch ist. Daher können wir einfach die Bedingung a = b überprüfen, um zu entscheiden, ob der Algorithmus beendet ist (in welchem ​​Fall wir in den "Leerlauf" -Zustand zurückkehren) oder ob wir mit dem Rest des Algorithmus fortfahren müssen. Bisher haben wir die folgende Tabelle:

Abbildung 5

Beachten Sie, dass, obwohl in Abbildung 5 nicht gezeigt, die Ausgabe lcm gleich a ist und gültig ist, wenn "ready" logisch hoch ist.

Sehen wir uns nun die "if" -Anweisung von Zeile 9 an. Können wir die Bedingung $$ a \ leq b $$ im "idle" -Zustand überprüfen? Beachten Sie, dass die "if" -Struktur, die bei Zeile 9 beginnt, die Hauptberechnungen des LCM-Algorithmus darstellt, und aufgrund der "if" -Anweisung in Zeile 20 können wir mehrmals zu der "if" -Anweisung der Zeile 9 zurückkehren. Deshalb schlage ich vor, die Line 9 "if" -Anweisung in einen neuen FSM-Zustand zu setzen. Es sollte angemerkt werden, dass wir für ein bestimmtes Design mehrere ASMD-Diagramme erstellen könnten, aber einige dieser ASMDs benötigen möglicherweise mehr Zustände oder mehr bedingte Blöcke.

Nach dem Hinzufügen der erforderlichen Blöcke für den nächsten Zustand des ASMD-Diagramms gelangen wir zum vollständigen Diagramm des Algorithmus, der in 6 gezeigt ist. Wie Sie sehen können, wird der nächste Zustand als "op" bezeichnet. Der erste Bedingungsblock dieses Zustands vergleicht a mit b und führt die erforderliche Operation gemäß dem Ergebnis des Vergleichs durch. Schließlich wird die Bedingung $$ a = b $$ überprüft. Wenn diese Bedingung als wahr bewertet wird, endet der Algorithmus und das System geht in den Zustand "Leerlauf". Andernfalls kehrt es in den Zustand "op" zurück, wie in Zeile 26 des Pseudocodes angegeben.

Abbildung 6

Es gibt ein paar Punkte, die weiter beachtet werden müssen: Erstens zeigt das ASMD-Diagramm nur die Register an, deren Wert sich geändert hat. Zum Beispiel sind die Zeilen 12 und 16 von Listing 2 in Fig. 6 nicht gezeigt. Außerdem ist, wie Sie sehen, der Ausgang "ready" im "Leerlauf" -Zustand logisch hoch, aber sein Wert ist für den "op" -Zustand nicht gegeben. Dies ist die Art und Weise, wie wir angeben, dass der "Bereit" -Ausgang nur im "Leerlauf" -Zustand hoch ist und daher im "OP" -Zustand als logisch niedrig betrachtet wird.

Zweitens, seien Sie vorsichtig mit bedingten Blöcken, die nach einer Zuweisung zum Register platziert werden. Beachten Sie, dass die Zuweisung zum Register beim nächsten Takt aktiviert wird. Deshalb sollten wir bei der Verwendung des Wertes eines Registers in Bedingungsblöcken vorsichtig sein: Sollen wir den aktuellen Wert des Registers oder seinen nächsten Wert verwenden? Das von uns erstellte ASMD-Chart basiert auf Pseudocode, bei dem der Wert einer Variablen direkt nach einer gegebenen Zuweisung aktualisiert wird. Dies bedeutet, dass wir den nächsten Wert der a- und b- Register in unserem Diagramm verwenden sollten.

Wir werden zwei neue Signale add_a und add_b definieren, die jeweils a + m und b + n entsprechen, und dann können wir das Diagramm von 6 neu zeichnen, wie in 7 gezeigt. Beachten Sie, dass die bedingten Blöcke jetzt den nächsten Wert von verwenden registriert in Vergleichen.

Abbildung 7

Drittens, während wir ursprünglich planten, eine FSM mit drei Zuständen zu entwerfen, zeigt das Diagramm in Abbildung 7, dass unsere FSM nur zwei Zustände hat. Wie Sie sehen können, werden zwei Sätze von Zuweisungen zu den a- und b- Registern (Zeilen 11-12 und Zeilen 16-17 von Listing 2) in einen einzigen Zustand versetzt, nämlich den "op" -Zustand; es wird jedoch keinen Konflikt zwischen diesen beiden Zuweisungssätzen geben, da nur einer von ihnen in einem gegebenen Taktzyklus ausgeführt werden kann.

Tatsächlich werden für das Ablaufdiagramm von Fig. 7 die Multiplexer des Datenpfads wie in Fig. 8 gezeigt implementiert. Der Wert des sel- Signals, das den Zustand der FSM darstellt, ist entweder Eins oder Null. Wenn sich der FSM jedoch im "op" -Zustand befindet, wird der Ausgang eines Komparatorblocks bestimmen, ob die Zeilen 11 und 12 des Pseudocodes oder die Zeilen 16 und 17 ausgeführt werden sollen.

Abbildung 8

Basierend auf dem ASMD-Diagramm von 7 und dem Schema von 8 können wir die VHDL-Beschreibung des Algorithmus finden, die in Listing 3 unten angegeben ist. Die Kommentare im VHDL-Code geben einige Hinweise zur Hardware, auf die sich jedes Codesegment bezieht.

Listing 3

 1 library IEEE; 2 use IEEE.STD_LOGIC_1164.ALL; 3 use IEEE.NUMERIC_STD.ALL; 4 entity lcm_fsmd is 5 port( clk, reset: in std_logic; 6 start: in std_logic; 7 m, n: in std_logic_vector(2 downto 0); 8 ready: out std_logic; 9 lcm: out std_logic_vector(5 downto 0)); 10 end lcm_fsmd; 11 architecture lcm_arch of lcm_fsmd is 12 type state_type is (idle, op); 13 signal state_reg, state_next: state_type; 14 signal a_reg, a_next, b_reg, b_next: unsigned(5 downto 0); 15 signal add_a, add_b: unsigned(5 downto 0); 16 begin 17 --control path: registers of the FSM 18 process(clk, reset) 19 begin 20 if (reset='1') then 21 state_reg <= idle; 22 elsif (clk'event and clk="1") then 23 state_reg <= state_next; 24 end if; 25 end process; 26 --control path: the logic that determines the next state of the FSM (this part of --the code is written based on the green hexagons of Figure 7) 27 process(state_reg, start, m, n, add_a, add_b) 28 begin 29 case state_reg is 30 when idle => 31 if ( start="1" ) then 32 if ( m=n ) then 33 state_next <= idle; 34 else 35 state_next <= op; 36 end if; 37 else 38 state_next41 if ( add_a = add_b ) then 42 state_next <= idle; 43 else 44 state_next <= op; 45 end if; 46 end case; 47 end process; 48 --control path: output logic 49 ready <= '1' when state_reg = idle else 50 '0'; 51 --data path: the registers used in the data path 52 process(clk, reset) 53 begin 54 if ( reset="1" ) then 55 a_reg'0'); 56 b_reg'0'); 57 elsif ( clk'event and clk="1" ) then 58 a_reg <= a_next; 59 b_reg <= b_next; 60 end if; 61 end process; 62 --data path: the multiplexers of Figure 8 63 process(state_reg, m, n, a_reg, b_reg, add_a, add_b) 64 begin 65 case state_reg is 66 when idle => 67 a_next <= unsigned( "000" & m); 68 b_next70 if ( a_reg < b_reg ) then 71 a_next <= add_a; 72 b_next <= b_reg; 73 else 74 a_next <= a_reg; 75 b_next <= add_b; 76 end if; 77 end case; 78 end process; 79 --data path: functional units 80 add_a <= unsigned(("000" & m)) + a_reg; 81 add_b <= unsigned(("000" & n)) + b_reg; 82 --data path: output 83 lcm <= std_logic_vector(a_reg); 84 end lcm_arch; 

Abbildung 9 zeigt eine ISE-Simulation für den obigen Code.

Abbildung 9

Für diese Simulation sind die Eingaben m = 7 und n = 6 . Am Ende des Algorithmus, wenn der Ausgang "ready" auf high geht, ist der lcm Ausgang 42, was das kleinste gemeinsame Vielfache von 7 und 6 ist.

Zusammenfassung

  • Ein FSM kann als Controller für den Datenpfad eines Algorithmus verwendet werden.
  • Durch Schreiben des Algorithmus unter Verwendung von "if" -Anweisungen können wir die FSM für den Algorithmus leichter entwerfen. Die Bedingungen der "if" -Anweisungen können uns tatsächlich einige Hinweise auf die Bedingungen für die FSM-Übergänge von einem Zustand zu einem anderen geben.
  • Das ASMD-Chart stellt nicht nur die FSM des Kontrollpfades dar, sondern beschreibt auch die Registertransferoperationen des Datenpfades.
  • Es ist möglich, mehrere ASMD-Diagramme für ein bestimmtes Design zu erstellen, aber einige dieser ASMDs benötigen möglicherweise mehr Zustände oder mehr bedingte Blöcke.

Um eine vollständige Liste meiner Artikel zu sehen, besuchen Sie bitte diese Seite.