Musterlo ̈sung
U ̈bung8 RAWiSe18/19
Aufgabe 1 (Speedup durch Pipelining)
(1) Wie gross ist der maximale Speedup einer 10-stufigen Pipeline gegenu ̈ber einer Mehrzyklenimplementierung desselben Instruktionssatzes? Berechnen Sie den Speed- up sowohl fu ̈r den Fall, dass die Mehrzyklenimplementierung einen CPI von 10 auf- weist, als auch fu ̈r den Fall, dass der durchschnittliche CPI 5,2 ist.
(2) Wieviele Instruktionen muss eine 6-stufige Pipeline mindestens abarbeiten, damit der Speedup gegenu ̈ber einer Architektur ohne Pipelining, die fu ̈r alle Instruktionen 6 Taktschritte beno ̈tigt, 5,9 betra ̈gt?
Musterlo ̈sung
(1) Im Fall der Mehrzyklenimplementierung mit einem CPI von 10 fu ̈r jede Instruktion
kann einfach die Formel fu ̈r den asymptotischen Speedup benutzt werden.
n·k
lim k+n−1 =k⇒Speedup=10
Im Fall der Mehrzyklenimplementierung mit einem durchschnittlichen CPI von 5,2 mu ̈ssen wir zwei unterschiedliche Parameter k in der Formel fu ̈r den asymptotischen Speedup einsetzen. Ohne Verbesserung durch Pipelining beno ̈tigt die Mehrzyklen- implementierung durchschnittlich kMehrzyklen = 5,2 Zyklen; mit Pipelining fu ̈r jede Instruktion kP ipelining = 10 Zyklen.
n→∞
n · kMehrzyklen
lim k
n→∞ P ipelining
+n−1 =kMehrzyklen ⇒Speedup=5,2
Pipelining, egal mit wievielen Stufen, fu ̈hrt im Idealfall (ohne Konflikte) zu einem CPI von eins. Die Verbesserung gegenu ̈ber einer Mehrzyklenimplementierung ent- spricht damit immer dem durchschnittlichen CPI-Wert der Mehrzyklenimplemen- tierung.
(2) Hier ko ̈nnen wir wieder die Formel aus der Vorlesung nehmen und nach n auflo ̈sen: n·k
k+n−1 =Speedup
⇔ n·k=Speedup·(k+n−1)
⇔ n·k=Speedup·k+Speedup·n−Speedup
⇔ n·k−Speedup·n=Speedup·k−Speedup
⇔ n(k−Speedup)=Speedup(k−1)
⇔ n=Speedup(k−1)
(k − Speedup)
Seite 1 / 6
Musterlo ̈sung
U ̈bung8 RAWiSe18/19
Wenn wir nun die Werte einsetzen erhalten wir folgende Lo ̈sung: n= 5,9(6−1) =295
(6 − 5,9)
Wir beno ̈tigen also 295 Instruktionen, um auf einen Speedup von 5,9 zu kommen.
Aufgabe 2 (Speedup bei inhomogenen Verzo ̈gerungszeiten)
Die einzelnen Datenpfadelemente in einer Einzyklenimplementierung haben die Verzo ̈ge- rungszeiten τi, i : 1…k. Nun wird Pipelining eingefu ̈hrt, und die k Datenpfadelemen- te werden durch Pipelineregister getrennt. Bestimmen Sie den Speedup gegenu ̈ber der Einzyklenimplementierung in Abha ̈ngigkeit von τi,k und n, der Anzahl abgearbeiteter Instruktionen. Die Verzo ̈gerungszeiten der Pipelineregister ko ̈nnen dabei vernachla ̈ssigt werden.
Wie gross kann der Speedup fu ̈r k = 4, τi = {50, 100, 200, 50}[ps] maximal werden? Musterlo ̈sung
Fu ̈r die Einzyklenimplementierung ist der CPI-Wert gleich eins, und die Taktperiode ergibt sich durch die Summe der Verzo ̈gerungszeiten der Datenpfadelemente, ki=1 τi. Beim Pipelining muss die Taktperiode der gro ̈ssten Verzo ̈gerungszeit aller Datenpfadelemente entsprechen, damit alle Stufen korrekt arbeiten ko ̈nnen, max(τi). Bei der Abarbeitung von n Instruktionen ergibt sich folgender Speedup:
Speedup = n · ki=1 τi (n−1+k)·maxki=1 (τi)
Der maximale Speedup wird fu ̈r n → ∞ erreicht und betra ̈gt:
Speedup = lim n→∞
n · ki=1 τi (n−1+k)·maxk (τ )
ki=1 τi = maxk (τ )
i=1 i
Im konkreten Zahlenbeispiel ist der Takt fu ̈r die Einzyklenimplementierung 400 ps, fu ̈r
das Pipelining 200 ps. Daraus ergib sich ein maximaler Speedup von 400 ps/200 ps = 2.
i=1 i
Seite 2 / 6
Musterlo ̈sung
U ̈bung8 RAWiSe18/19
Aufgabe 3 (Graphische Darstellungen des Pipelining)
Folgende Codesequenz wird auf der 5-stufigen MIPS-Pipeline ausgefu ̈hrt:
add $4, $2, $3
sw $5, 4($2)
sw $6, 8($2)
Abbildung 1 zeigt die graphische Darstellung der Pipelinebelegung. Stellen Sie fu ̈r jeden Taktschritt fest, welche Instruktion in welcher Pipelinestufe bearbeitet wird und wel- che Elemente des Datenpfads verwendet werden. Zeichnen Sie diese Elemente in den Pipelining-Datenpfad (auf den Zusatzbla ̈ttern) ein. Kennzeichnen Sie bei sequentiellen Elementen durch Schraffieren der rechten oder linken Ha ̈lfte, ob sie gelesen oder geschrie- ben werden.
Abbildung 1: Pipelinebelegung
Musterlo ̈sung
Die Lo ̈sung der Aufgabe finden Sie auf den nachfolgenden Seiten.
Seite 3 / 6
add $4, $2, $3
sw $5, 4($2) add $4, $2, $3
sw $5, 8($2) sw $5, 4($2) add $4, $2, $3
sw $5, 8($2) sw $5, 4($2) add $4, $2, $3
sw $5, 8($2) sw $5, 4($2) add $4, $2, $3
sw $5, 8($2) sw $5, 4($2)
sw $5, 8($2)