Bài giảng Kiến trúc máy tính - Nguyễn Đức Minh (Mới)

M Reg
A
L
UIM Reg DM Reg
 Một loại xung đột dữ liệu xuất hiện khi chuyển tiếp: Xung
đột giữa kết quả của lệnh đang ở giai đoạn WB và lệnh
đang ở giai đoạn MEM – kết quả nào cần được chuyển
tiếp?
Xung đột dữ liệu khi có lệnh lw
HUST-FET, 13/03/201157
I
n
s
t
r.
O
r
d
e
r
lw $1,4($2)
and $6,$1,$7
xor $4,$1,$5
or $8,$1,$9
A
L
UIM Reg DM Reg
A
L
UIM Reg DM
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Regsub $4,$1,$5
Xung đột điều khiển
HUST-FET, 13/03/201158
 Khi địa chỉ các lệnh không tuần tự (i.e., PC = PC + 4); 
xuất hiện khi có các lệnh thay đổi dòng chương trình
 Lệnh rẽ nhánh không điều kiện (j, jal, jr)
 Lệnh rẽ nhánh có điều kiện (beq, bne)
 Ngắt, Exceptions
 Giải pháp
 Tạm dừng (ảnh hưởng CPI)
 Tín toán điều kiện rẽ nhánh càng sớm càng tốt trong giai đoạn
pipeline giảm số chu kỳ phải dừng
 Rẽ nhánh chậm (Delayed branches - Cần hỗ trợ của trình dịch)
 Dự đoán và hy vọng điều tốt nhất!
 Xung đột điều khiển ít xảy ra, nhưng không có giải pháp
giải quyết hiệu quả như chuyển tiếp đối với xung đột dữ
liệu
Lệnh nhảy: Cần một chu kỳ dừng
HUST-FET, 13/03/201159
flush
I
n
s
t
r.
O
r
d
e
r
j
j target
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
 Lệnh nhảy rất ít xuất hiện – chỉ chiếm 3% số lệnh trong 
SPECint
 Lệnh nhảy không được giải mã cho đến giai đoạn ID, 
cần một lệnh xóa (flush)
 Để xóa, đặt trường mã lệnh của thanh ghi pipeline IF/ID 
bằng 0 (làm nó trở thành 1 lệnh noop)
Giải quyết
xung đột
lệnh nhảy
bằng cách
chờ – flush
A
L
UIM Reg DM Reg
Xung đột điều khiển lệnh rẽ nhánh
HUST-FET, 13/03/201160
I
n
s
t
r.
O
r
d
e
r
lw
Inst 4
Inst 3
beq
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
Giải quyết xung đột điều khiển lệnh rẽ nhánh
HUST-FET, 13/03/201161
flush
flush
flush
I
n
s
t
r.
O
r
d
e
r
beq
A
L
UIM Reg DM Reg
beq target
A
L
UIM Reg DM Reg
A
L
U
Inst 3
IM Reg DM
Giải quyết
xung đột
bằng chờ–
flush –
nhưng ảnh
hưởng CPI
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
Giải quyết xung đột điều khiển lệnh rẽ nhánh
HUST-FET, 13/03/201162
flush
I
n
s
t
r.
O
r
d
e
r
beq
beq target
A
L
UIM Reg DM Reg
Inst 3
A
L
UIM Reg DM
Fix branch 
hazard by 
waiting –
flush
A
L
UIM Reg DM Reg
 Tính toán điều kiện rẽ nhánh càng sớm càng tốt, tức
là trong giai đoạn giải mã chỉ cần 1 chu kỳ chờ
A
L
UIM Reg DM Reg
Rẽ nhánh chậm
HUST-FET, 13/03/201163
 Nếu phần cứng cho rẽ nhánh nằm ở giai đoạn ID, ta có thể
loại bỏ các chu kỳ chờ rẽ nhánh bằng cách sử dụng rẽ
nhánh chậm (delayed branches) – luôn thực hiện lệnh theo
sau lệnh lệnh rẽ nhánh – rẽ nhánh có tác dụng sau lệnh kế
tiếp nó
 Trình dịch MIPS compiler chuyển 1 lệnh an toàn (không bị ảnh
hưởng bởi lệnh rẽ nhánh) tới sau lệnh rẽ nhánh (vào khe trễ). Vì
vậy sẽ dấu được sự rẽ nhánh chậm
 Với pipeline sâu (nhiều giai đoạn), trễ rẽ nhánh tăng cần
nhiều lệnh được chèn vào sau lệnh rẽ nhánh
 Rẽ nhánh chậm đang được thay thế bởi các phương pháp khác
tốn kém hơn nhưng mềm dẻo (động) hơn như dự đoán rẽ nhánh
 Sự phát triển của IC cho phép có bộ dự đoán rẽ nhánh ít tốn kém
hơn
Sắp xếp lệnh trong rẽ nhánh chậm
HUST-FET, 13/03/201164
 TH A là lựa chọn tốt nhất, điền được khe trễ và giảm I
 TH B và C, lệnh sub cần sao lại, tăng I
 TH B và C, phải đảm bảo thực hiện lệnh sub không ảnh hưởng khi
không rẽ nhánh
add $1,$2,$3
if $2=0 then
delay slot
A. Từ trước lệnh rẽ nhánh B. Từ đích lệnh rẽ nhánh C. Từ nhánh sai
add $1,$2,$3
if $1=0 then
delay slot
add $1,$2,$3
if $1=0 then
delay slot
sub $4,$5,$6
sub $4,$5,$6
becomes becomes becomes
if $2=0 then
add $1,$2,$3
add $1,$2,$3
if $1=0 then
sub $4,$5,$6
add $1,$2,$3
if $1=0 then
sub $4,$5,$6
Dự đoán rẽ nhánh tĩnh
HUST-FET, 13/03/201165
 Giải quyết xung đột rẽ nhánh bằng cách giả sử 1 hướng rẽ
nhánh và tiếp tục không cần chờ tính toán kết quả rẽ
nhánh thực sự.
1. Đoán không rẽ nhánh – luôn giả sử lệnh không rẽ nhánh, 
tiếp tục nạp các lệnh kế tiếp, chỉ khi có rẽ nhánh thì cần
dừng pipeline
 Nếu rẽ nhánh, xóa các lệnh sau rẽ nhánh (sớm ở trong pipeline)
- trong giai đoạn IF, ID, và EX nếu bộ tính rẽ nhánh ở MEM – ba dừng
- trong giai đoạn IF và ID nếu bộ tính rẽ nhánh ở EX – hai dừng
- trong giai đoạn IF nếu bộ tính rẽ nhánh ở ID – môt dừng
 Đảm bảo rằng các lệnh bị xóa không ảnh hưởng tới trạng thái
máy. 
 Khởi tạo lại pipeline ở đích lệnh rẽ nhánh
Xóa khi dự đoán sai
HUST-FET, 13/03/201166
4 beq $1,$2,2I
n
s
t
r.
O
r
d
e
r
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg8 sub $4,$1,$5
Xóa khi dự đoán sai (Đoán không rẽ nhánh)
HUST-FET, 13/03/201167
flush
4 beq $1,$2,2I
n
s
t
r.
O
r
d
e
r
A
L
UIM Reg DM Reg
16 and $6,$1,$7
20 or r8,$1,$9
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg8 s b $4,$1,$5
 Để xóa, đặt trường mã lệnh của thanh ghi pipeline IF/ID 
bằng 0 (làm nó trở thành 1 lệnh noop)
Dự đoán rẽ nhánh
HUST-FET, 13/03/201168
 Giải quyết xung đột bằng cách giả thiết kết quả rẽ
nhánh và tiếp tục
2. Đoán có rẽ nhánh – dữ đoán luôn luôn có rẽ nhánh
 Đoán có rẽ nhánh luôn cần 1 chu kỳ dừng (nếu phần cứng tính
rẽ nhánh ở giai đoạn ID)
 Cần phương pháp đọc trước (vào bộ đệm) lệnh ở địa chỉ
đích??
 Vì thiệt hại do rẽ nhánh đang tăng lên (với các pipeline 
sâu), mô hình dự đoán rẽ nhánh tĩnh sẽ ảnh hưởng tới
hiệu năng. Với nhiều phần cứng hơn, có thể thử dự
đoán hoạt động rẽ nhánh động lúc chương trình được
thực hiện
3. Dự đoán rẽ nhánh động – đoán rẽ nhánh lúc chạy dựa
trên các thông tin chạy (run-time information)
Dự đoán rẽ nhánh động bằng 1 bit
HUST-FET, 13/03/201169
 Bô dự đoán 1 bít sẽ sai 2 lần nếu đoán không rẽ nhánh:
 Nếu lặp 10 lần ta sẽ có tỉ lệ rẽ nhánh đúng là 80%. Nếu
dùng lệnh rẽ nhánh beq thì đúng 90%
 Giá sử predict_bit = 0 lúc bắt đầu (chỉ ra
không rẽ nhánh) lệnh rẽ nhánh điều khiển
ở cuối vòng lặp
1. Lần thực hiện vòng lặp 1, bộ dự đoán sai
cho lệnh rẽ nhánh vì nó dẫn quay lại đầu
vòng lặp; cần đảo bít rẽ nhánh (predict_bit
= 1)
2. Khi nào vẫn còn rẽ nhánh (vẫn lặp), dự
đoán đúng
3. Khi thoát khỏi vòng lặp, bộ dự đoán sẽ sai
1 lần nữa vì lần này sẽ không rẽ nhánh
mà ra ngoài vòng lặp; đảo bit rẽ nhánh
(predict_bit = 0)
Loop: 1st loop instr
2nd loop instr
.
.
.
last loop instr
bne $1,$2,Loop
fall out instr
Dự đoán rẽ nhánh động bằng 2 bit
HUST-FET, 13/03/201170
 Cơ chế dùng 2 bit cho độ chính xác 90% vì chỉ khi dự
đoán sai 2 lần thì bit dự đoán mới thay đổi
Predict
Taken
Predict
Not Taken
Predict
Taken
Predict
Not Taken
Taken
Not taken
Not taken
Not taken
Not taken
Taken
Taken
Taken
Loop: 1st loop instr
2nd loop instr
.
.
.
last loop instr
bne $1,$2,Loop
fall out instr
Exceptions
HUST-FET, 13/03/201171
 Exceptions (ngắt - interrupts) có thể coi là 1 dạng xung
đột dữ liệu. Exception xuất hiện từ:
 Tràn khi thực hiện lệnh số học
 Lệnh không được định nghĩa
 Yêu cầu từ thiết bị vào ra
 Yêu cầu dịch vụ hệ điều hành (VD. lỗi trang, lỗi TLB)
 Lỗi chức năng phần cứng
 Pipeline cần phải:
• dừng thực hiện lệnh lỗi, 
• để tất cả các lệnh trước đó hoàn thành, 
• xóa các lệnh sau đó, 
• đặt thanh ghi chỉ ra nguyên nhân exception, 
• lưu lại địa chỉ lệnh lỗi, 
• nhảy đến địa chỉ định trước (địa chỉ của hàm xử lý exception)
 Phần mềm (OS) sẽ xử lý tiếp exception. 
Hai loại exceptions
HUST-FET, 13/03/201172
 Ngắt – không đồng bộ với sự thực hiện chương trình
 gây ra bởi sự kiện bên ngoài
 có thể được xử lý giữa các lệnh, nên để các lệnh đang có
trong pipeline hoàn thành trước khi chuyển điều khiển cho
hàm xử lý ngắt của OS.
 đơn giản là dừng và tiếp tục chương trình người dùng
 Bẫy (Exception) – đồng bộ với sự thực hiện chương
trình
 gây ra bởi sự kiện bên trong
 hàm xử lý bẫy cần sửa chữa điều kiện cho đúng lệnh bị bẫy, 
nên phải dừng lệnh lỗi trong trong pipeline và chuyển điều
khiển cho hàm xử lý bẫy của OS
 lệnh lỗi có thể tiếp tục chương trình có thể bị kết thúc hoặc
được tiếp tục
Exception có thể xuất hiện ở đâu trong pipeline
HUST-FET, 13/03/201173
 Tràn số học
 Lệnh không định nghĩa
 Lỗi TLB hoặc trang
 Yêu cầu dịch vụ I/O
 Lỗi phần cứng
A
L
UIM Reg DM Reg
Stage(s)? Synchronous?
Exception có thể xuất hiện ở đâu trong pipeline
HUST-FET, 13/03/201174
A
L
UIM Reg DM Reg
Stage(s)? Synchronous?
EX yes
yes
yes
no
no
 Chú ý rằng nhiều exception có thể xuất hiện đồng thời
trong một chu kỳ đồng hồ
ID
IF, MEM
any
any
 Tràn số học
 Lệnh không định nghĩa
 Lỗi TLB hoặc trang
 Yêu cầu dịch vụ I/O
 Lỗi phần cứng
Nhiều exception đồng thời
HUST-FET, 13/03/201175
I
n
s
t
r.
O
r
d
e
r
Inst 0
Inst 1
Inst 2
Inst 4
Inst 3
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
 Lệnh sớm nhất sẽ bị ngắt đầu tiên
Nhiều exception đồng thời
HUST-FET, 13/03/201176
I
n
s
t
r.
O
r
d
e
r
Inst 0
Inst 1
Inst 2
Inst 4
Inst 3
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
A
L
UIM Reg DM Reg
D$ page fault
arithmetic overflow
undefined instruction
I$ page fault
 Lệnh sớm nhất sẽ bị ngắt đầu tiên
Tổng kết
HUST-FET, 13/03/201177
 Tất cả các bộ xử lý hiện đại đều dùng pipeline để tăng
hiệu suất (CPI=1 và đồng hồ nhanh - fc lớn)
 Tốc độ đồng hồ pipeline bị giới hạn bởi giai đoạn pipeline 
chậm nhất – thiết kế pipeline cân bằng là rất quan trọng
 Cần phát hiện và giải quyết xung đột trong pipeline
 Xung cấu trúc – giải quyết: thiết kế pipeline đúng
 Xung đột dữ liệu
- Dừng (ảnh hưởng CPI)
- Chuyển tiếp (cần phần cứng hỗ trợ)
 Xung đột điều khiển – đặt phần cứng quyết định rẽ nhánh lên các
trạng thái đầu trong pipeline
- Dừng (ảnh hưởng CPI)
- Rẽ nhánh chậm (cần hỗ trợ của trình dịch)
- Dự đoán rẽ nhánh tĩnh và động (cần phần cứng hỗ trợ)
 Xử lý ngắt trong pipeline phức tạp