Abschlusstest Rechnerorganisation WS18/19 Zeitraum 1
1. Aufgabe: Pipelining (18 Punkte) Gegeben ist folgender Quelltextauszug:
1 add $sp, $sp, $4 2 slt $s0, $sp, $a0 3 lb $t1, 0($sp)
4 sub $t3, $t1, $a1 5 lw $t2 4($a2)
6 add $t4, $a0, $t2
源代码
4级流水线
Der Code soll auf der aus der Vorlesung bekannten 4-Stugen Pipeline des MIPS-Prozessors (IF, ID, EX, MEM, WB) ausgeführt werden. Die Register werden in der zweiten Phase der Instruktiondecode Phase gelesen und in der ersten Takthälfte der Writeback-Phase beschrieben.
寄存器用于指令解码的第二阶段，在写回阶段的前半部分读取和写入
(a) In welchen Code-Zeilen können potenziell Hazards (Pipeline Hemmnisse) auftreten? Um welche Art von Hazard handelt es sich?
a) 哪些代码中可能发生潜在危险(pipeline barriers)，是什么危险
cpuinnaion
(b) Durch das Einfügen von NOP-Instruktionen können Hazards verhindert werden. Kreu- zen Sie die minimale benötigte Anzahl von NOP-Instruktionen an, die benötigt werden, damit das Programm korrekt ausgeführt wird
NOP 数量
Lösung:
Je Hazard 0,5 Punkte (Zeile + Name)
1=>2 Data Hazard ($sp) 1=>3 Data Hazard ($sp) 3=>4 Load-Use-Hazard ($t1) 5=>6 Load-Use-Hazard ($t2)
每个危险0.5分，(行数+名称
Instruktion
Anzahl NOPs
1 add $sp, $sp, $4
0
1
2
3
X
2 slt $s0, $sp, $a0
0
1
2
3
X
3 lb $t1, 0($sp)
0
1
2
3
X
4 sub §t3, $t1, $a1
0
1
2
3
X
5 lw $t2 4($a2)
0
1
2
3
X
6 add $t4, $a0, $t2
0
1
2
3
1/10
Abschlusstest Rechnerorganisation WS18/19 Zeitraum 1
问题中红是多少? 假设流水线执行开始为空 ?
(c) Wie groß ist der CPI des Programms aus (b)? Gehen Sie davon aus, dass die Pipeline zu Beginn der Ausführung leer ist.
Lösung:
1P für Ansatz
1P für richtiges Ergebnis
时钟周期 执 令 时钟周期流水线
#Taktzyklus = 6 Befehle + 6 NOPs + 4 Taktzyklen Pipeline = 16 Taktzyklen
CPI = #Taktzyklen/#Instruktionen = 16 Taktzyklen / 6 Instruktionen = 2,66 Taktzyklen/Instruktion
(d) Nehmen Sie jetzt an, dass der Prozessor über eine Forwarding-Unit, Hazard-Detection und einen Branch-Delay-Slot verfügt. Verfolständigen Sie das unten stehende Pipeline-Diagramm für den gezeigten Code. Fügen Sie die Kürzel, IF, ID, EX, MEM, WB für jeden Befehl in der Tabelle ein und markieren Sie alle Wartezyklen (stall cycles), indem Sie an der Stelle ein X notieren. Mar- kieren Sie alle Data-Forwards mit Pfeilen zwischen den beteiligten Stufen.
(e) Wie groß ist der CPI Ihrer Lösung aus (d)? Welcher Speedup kann demnach durch en Einsatz der Forwarding Unit und der Hazard-Detection erzielt werden? 加速 了 多少 ?
Lösung:
1P für CPI-Ansatz
1P für richtiges Ergebnis des CPI
1P für Speedup-Ansatz und Ergebnis
Folgefehler (FF) von (d) oder (c) werden gegeben
#Taktzyklen = 12 Taktzyklen (ablesen aus Diagramm)
CPI = #Taktzyklen/#Instruktionen = 12 Taktzyklen / 6 Instruktionen = 2,00 Taktzyklen/Instruktion
S = CPIold/CPInew 2,66/2,00 = 1,33 => 33%Speedup
d)现在假定处理器具有转发单元，危害检测和分支延迟 时隙。 完成上面所示代码的管道图。 在表中为每个指令 添加缩写IF，ID，EX，MEM，WB，并通过在适当的位置 标记X来标记所有停顿周期。 在涉及的两个级别之间用箭 头将所有数据向前标记。
Instruktion|Takt1 2 1 add $sp, $sp, $4 IF ID
2 slt $s0, $sp, $a0 3 lb $t1, 0($sp)
4 sub §t3, $t1, $a1 5 lw $t2 4($a2)
6 add $t4, $a0, $t2 7XX
3 4 5 6 7 8 9 EX MEM WB
10 11 12
MEM WB
IF ID
IF ID
EX MEM WB
EX MEM WB
IF ID
IF X
2/10
X EX MEM WB
ID EX MEM WB
X IF
ID X EX
Abschlusstest Rechnerorganisation WS18/19 Zeitraum 1 2. Aufgabe: Rechenleistung (12 Punkte)
内存访问 150 Ps ALU loops
Nehmen Sie an, ein Speicherzugri kostet 150ps, eine ALU-Operation 100ps und ein Zugri auf ein Register kostet 50ps. Andere Latenzen können vernachlässigt werden.
(a)
寄存器 50ps 其它延迟 可唔
Wie groß ist die minimale Taktzykluszeit eines Eintaktprozessors mit diesen Latenzen?
单周期 cpu Ansatz gibt einen Punkt und einen Punkt auf das Ergebnis.
Instruction Memory: 150ps Register: 50ps
ALU: 100ps
Data Memory: 150ps Register: 50ps
=> Summe 500ps
Lösung:
5 阶流水线的最小时钟周期
(b) Wie groß ist die minimale Taktzykluszeit eines Pipelined-Prozessors mit der klassischen
5-Stufen-Pipeline, ebenfalls unter der Annahme oben genannter Latenzen?
Lösung:
Ansatz /Erklärung gibt einen Punkt und einen Punkt auf das Ergebnis. Längste Einzelverzögerung => 150ps Speicherzugri
(c) Welcher maximale Speedup ist demnach möglich, wenn man einen Pipelined-Prozessor
einsetzt?
Speedup = 500ps/150ps = 3,33
Lösung:
Je Grund gibt es einen Punkt
对比流水线和单周期, 提速了多少 Ansatz gibt einen Punkt und einen Punkt auf das Ergebnis.
Lösung:
(d) Der Faktor aus der vorherigen Teilaufgabe kann nur erreicht werden, wenn der Pipeli- ned-Prozessor einen CPI von 1 erreicht. Selbst wenn der Prozessor Forwarding unterstützt und Sprünge verzögert ausführen kann (durch einen Branch Delay Slot), ist dies nur selten möglich. Geben Sie hierfür zwei Gründe an
仅当流水线处理器的CPI达到1时，才能实现上一个子任务的因 数。 即使处理器支持转发并且可以延迟执行跳转(通过分支延迟 插槽)，这也是极不可能的。 请给出两个原因
3/10
Abschlusstest Rechnerorganisation WS18/19 Zeitraum 1
• Stallcycles
• Branch-Delay-Slot nicht füllbar
• Pipeline befüllen
上面所有都加速15%,各个延迟为多少
(e) Sie möchten sowohl Eintakt, als auch Pipelined-Prozessor um den Faktor 1,15 beschleu- nigen. Angenommen, Sie können dafür genau eine der Komponenten (Speicherzugri, ALU-Ope- ration oder Registersatz) beschleunigen. Wie groß darf die Latenz der Komponente nach der Ver- besserung noch sein, um den gewünschten Speedupfaktor zu erzielen? Nutzen Sie die folgende Tabelle für Ihre Ergebnisse und vergessen Sie nicht, Ihren Lösungsweg zu notieren!
Pipelinded:
Speicher 15% schneller
Speedup = 150ps/1,15 = 130,4ps
Eintakt
Speedup = 500ps/1,15 = 434,8ps
Speicher 15% schneller
2 * tSpeicherzugri + 2 * tRegister + tALU = 434,8ps
=> tSpeicherzugri = 117,4ps Register 15% schneller
2 * tSpeicherzugri + 2 * tRegister + tALU = 434,8ps
=> tSpeicherzugri = 17,4ps ALU 15% schneller
2 * tSpeicherzugri + 2 * tRegister + tALU = 434,8ps => tALU = 34,8ps
Eintakt
Pipelined
Komponente
Speicher
ALU
Register
Speicher
Neue Latenz
117,4ps
34,8ps
17,4ps
130,4ps
4/10
Abschlusstest Rechnerorganisation WS18/19 Zeitraum 1 3. Aufgabe: Speicherhierachie (12 Punkte)
cpui3-wgset-ass.ciatieade 寻址 高速缓存
Ein Prozessor verfügt über einen 3-fach-satzassoziativen Cache. Für die Adressierung des Caches wer- den 36 Bit für den Tab, 8 Bit für den Index und 4 Bit für den Blockoset verwendet.
(a)
(b) Wie viele Sätze gibt es in dem Cache? Wie groß ist ein Block?
(c)
• • • •
Vervollständigen Sie die Skizze des Caches, indem Sie die folgenden Werte eintrage:
Mit welcher Adressgröße arbeitet der Prozessor?
?
比 的Ad.es 大小 1P für richtiges Ergebnis
Lösung:
1P für Ansatz
Adressgröße = Taglänge + Indexlänge + Blockosetlänge = 36 Bit + 8 Bit +4 Bit = 48 Bit
Lösung:
cad有多少record
Blod 多大
0,5P je Ansatz
1P je richtiges Ergebnis
#Sätze = 2Indexlänge = 28Sätze = 256 Sätze Blockgröße = 2Blockosetlänge = 24 Bytes = 16 Bytes
minimaler und maximaler Index Blockgröße in Bytes
Satzgröße in Byte
Anzahl der Ways BGdsize.in/ytesRwrdsizeinbgtegNunberafwegs
Blockgröße: 16 Bytes
输入以下值来完成高速缓存的草图
Satzgröße: 48 Bytes min Index: 0
max Index: 255
3 Wege
5/10
Abschlusstest Rechnerorganisation WS18/19 (d) Wie groß ist die Kapazität des Caches?
Zeitraum 1
缓存的 容量是多少 ? 1P für richtiges Ergebnis
Lösung:
1P für Ansatz
Kapazität = #Sätze * Assoziativität * Blockgröße = 256 * 3 * 16 Bytes = 12288Bytes (12 kBytes)
6/10
Abschlusstest Rechnerorganisation WS18/19 Zeitraum 1
4. Aufgabe: Datenpfaderweiterung (18 Punkte)
图⻅下⻚ 单周期 CM 为 R-gpexor.comund
Der aus der Vorlesung bekannte Eintaktprozessor (siehe gegenüberliegende Seite) soll um ein R-Typ
Befehl xor erweitert werden. 写 一个㘩 ” 程序
V ten Sie auf die korrekte Bitbreite der Signale! 答案
=1
答案 → Steuersignal Wert
0
。
癲 手写
L.se
Ainvert 0 Binvert 0
Operation 3
← 答案
xor-operationhgicammad.im
,
befehlen and, not und or implementiert.
or $t0, $t12, $t2 and $t3, $t1, $t2 not $t3, $t3
and $t0, $t0, $t3
not $t0, $t2
and $t0, $t3, $t0 not $t1, $t1,
and $t1, $t1, $t2 or $t0, $t0, $t1
b)Extend the 1-bit ALU known from the exercise so that it can perform the xor operation can perform. Use the defaults on this page and make sure that it should be possible invert
ㄏthe inputs!
(b) Erweitern Sie die aus der Übung bekannte 1-Bit ALU so, damit diese die xor-Operation i ausführen kann. Benutzen Sie die Vorgabe dieser Seite und beschten Sie, dass es möglich sein soll
(a) Verfassen Sie ein MIPS-Assemblerprogramm, welches die xor-Operation mit den Logik-
plenuud
die Eingänge zu invertieren!
(c) Wie müssen die Steuersignale der ALU gesetzt sein, damit a xor b ausgeführt wird? Ach-
c)How must the control signals of the ALU be set so that a xor b is executed? Pay attention to the correct bit widths of the signals!
7/10
3
Abschlusstest Rechnerorganisation WS18/19 Zeitraum 1
d) 下表填空
(d) Erweitern Sie die ALU-Steuerung, indem Sie die folgende Tabelle ergänzen.
(Hinweis: Die xor-Operation gehört nicht zum Core Instruction Set, ihr Function Code ist aber auf der Rückseite der Green Card aufgeführt.)
Opco- Funct. de
lw/sw – beq – R-Typ add R-Typ sub R-Typ and R-Typ or
R-Typ xor
Bewertung: (2 Punkte) Richtige Erweiterung der ALU-Steuerung, -1 Punkt pro Fehler.
(e)Geben Sie die Steuersignale an, damit der Eintaktprozessor (siehe unten) den xor-Befehl aus- führt. Verwenden Sie don‘t care, falls möglich. 如何 输入信号使 下 图单周期 比 发出
Jump: 0 Branch: 0 MemRead: 0 MemToReg: 0 ALUOp: 10 MemWrite: 0 ALUSrc: 0 RegWrite: 1
Add
为应答处
Instruction [5-0]
ALU Op
0 0 0 1 1 0 1 0 1 0 1 0
x x x x 1 0 1 0 1 0 1 0
Funct. Field [5:0]
x x x x x x 0 0 0 0 0 1 0 1 0 0 1 0
ALU Desired Ctrl. ALU Signals Action
x 0010 add x 0110 sub 0 0010 add 0 0110 aub
0 0000 and
1 0001 or
1 0
1 0
0 1 1
0 0011 xor
Bewertungsschema: (4 Punkte), -1 Punkt pro fehlerhaftes Steuersignal RegDest: 1
xorwmmend
。
0 1 MM ux ux
1 0
PC
Read address
Instruction [31-0]
Instruction memory
Instruction [25-21] Read register 1
Read data 1
4
Add ALU result
Instruction [25-0]
Shift
26 left2 28
Jump address [31 – 0] PC+4[31-28]
RegDst
Jump
Branch
MemRead
MemToReg
Instruction [31-26]
Control ALUOp
Shift left 2
0 M
Instruction [20-16]
Instruction [15-11]
Instruction [15-0]
Read
0 register 2
Zero
ALU ALU result
Address Read 1 data Mu
为 原 题 空白 应答处
8/10
Write
MemWrite ALUSrc RegWrite
M Write Read
1
ux register
data 2 data Registers
16 Sign 32 extend
2
ux x 10
ALU control
4
Write memory data
Data