Hardware Reference
In-Depth Information
type
tVektortyp
is
(natural
range
<>)
of
tTyp;
variable
x, z: tVektortyp(n-
1
downto
0
);
...
begin
z(
0
) := x(
0
);
for
idx
in
z'low+
1
to
z'high
loop
z(idx) := z(idx-
1
)
x(idx);
end loop
;
beliebigerassoziativerOperator l¨angsterSignalpfad
x
0
z
0
z
1
x
1
x
2
z
2
···
x
n−1
z
n−1
Abb. 3.20. Schleife, die einen Ausdruck mit assoziativen Operatoren durch eine
Kettenstruktur nachbildet
In einem Ausdruck mit einer festen Anzahl von assoziativen Operationen
lässt sich der Berechnungsfluss durch eine geeignete Klammernsetzung opti-
mieren (vgl. Abschnitt 2.2.2). In dem Ausdruck in Abb. 3.21 werden zuerst
Paare von Eingabesignalen und anschließend jeweils Paare von Zwischener-
gebnissen so zusammengefasst, dass der Berechnungsfluss einen Baum bildet.
Die korrespondierende Schaltung hat nur eine Verzögerungszeit der Ordnung
O(log (n)).
AusdruckmitKlammern
Berechnungsbaum
((
x
0
◦x
1
)
◦
(
x
2
◦x
3
))
◦
((
x
4
◦x
5
)
◦x
6
)
x
0
x
1
x
2
x
3
x
4
x
5
x
6
Abb. 3.21. Überführung der Ketten- in eine Baumstruktur
Baumartige Berechnungsflüsse lassen sich auch mit einer Schleife beschrei-
ben. Abbildung 3.22 zeigt hierfür einen Reduktionsalgorithmus, der solange
paarweise 2i Eingabewerte zu i Zwischenwerten zusammenfasst, bis nur ein
Zwischenwert, der Ausgabewert, übrig ist. Bei einer paarweisen Zusammen-
fassung von n Eingabesignalen entstehen n 2 Zwischenergebnisse und ein
Gesamtergebnis. In Abb. 3.22 wird für alle Werte zusammen ein Feld mit
2 n 1 Elementen vereinbart. In die ersten n Elemente werden die Ein-
gabewerte geschrieben. Anschließend werden in jedem Schleifendurchlauf die
Werte zweier benachbarter Feldelemente zusammengefasst und in das nächs-
te freie Element geschrieben. Die ersten n 2 Schleifendurchläufe berechnen
die Zwischenergebnisse im Baum und der n1-te Schleifendurchlauf aus den
letzten beiden Zwischenergebnissen das Endergebnis.
Das Prinzip ist auch auf andere Reduktionsschemata anwendbar. Ein
Carry-Save-Addierer fasst immer drei Summanden oder Zwischensummen zu
zwei Zwischensummen zusammen. Die Iteration stoppt, wenn nur noch zwei
nicht zusammengefasste Zwischensummen übrig sind, für deren Zusammenfas-
