Bài giảng Kiến trúc máy tính - Chương 3: Phép số học - Nguyễn Thanh Sơn

BK 
TP.HCM 
Computer Architecture 
Computer Science & Engineering 
Chương 3 
Phép số học 
BK 
TP.HCM 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 2 
Các phép số học 
 Các phép tính trên số nguyên 
 Cộng và Trừ 
 Nhân và Chia 
 Xử lý tràn 
 Số thực với dấu chấm di động (Floating-
Point) 
 Cách biểu diễn và các phép tính 
BK 
TP.HCM 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 3 
Nhắc lại mạch số 
Môn học: 
 Nhập môn điện toán (Năm I) 
 Thiết kế hệ thống số 
25 August 2016 Khoa Khoa học & Kỹ thuật Máy tính 4 
Mạch Half Adder 
Half 
adde
r 
y 
S 
C 
x x 
y 
S 
C 
1 0 1 1 
0 1 0 1 
0 1 1 0 
0 0 0 0 
C S y x 
AND XOR 
AND 
XOR 
25 August 2016 Khoa Khoa học & Kỹ thuật Máy tính 5 
Mạch Full Adder 
Full 
adder 
y 
S 
C 
x 
C0 
S = x + y + C0 
S = (x + y) + C0 
Tính: S1 = x + y 
Tính: S2 = S1 + C0 
Half adder 1 
Half adder 2 
25 August 2016 Khoa Khoa học & Kỹ thuật Máy tính 6 
Full adder (2) 
1 0 1 0 1 1 1 1 1 1 
1 1 0 1 1 1 0 0 1 1 
1 1 0 1 1 1 0 1 0 1 
0 0 0 0 1 0 1 0 0 1 
1 0 1 0 0 1 0 1 1 0 
0 0 0 1 0 0 1 0 1 0 
0 0 0 1 0 0 1 1 0 0 
0 0 0 0 0 0 0 0 0 0 
C C2 C1 S1 C0 C S y x C0 
C = 1 when C1 = 1 or C2 = 1 
25 August 2016 Khoa Khoa học & Kỹ thuật Máy tính 7 
Full adder (3) 
C0 
x 
y 
S1 
S 
C1 
C2 
C 
Half 
adde
r 
Half 
adde
r 
25 August 2016 Khoa Khoa học & Kỹ thuật Máy tính 8 
Cộng nhiều Bits 
y0 
S0 
x0 
0 
S1 
S2 
S3 C 
x1 
x2 
x3 
y1 
y2 
y3 
Full 
adder 0 
Full 
adder 1 
Full 
adder 2 
Full 
adder 3 
x3x2x1x0 
C S3S2S1S0 
y3y2y1y0 
+ 
BK 
TP.HCM 
Phép cộng số nguyên 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 9 
 Ví dụ: 7 + 6 
 Tràn nếu kết quả tràn ngưỡng 
 Cộng 2 toán hạng trái dấu: không tràn 
 Cộng 2 toán hạng đều dương 
 Tràn nếu bit dấu của kết quả là 1 
 Cộng 2 toán hạng đều âm 
 Tràn nếu bit dấu của kết quả là 0 
BK 
TP.HCM 
Phép trừ số nguyên 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 10 
 Cộng số âm của toán hạng thứ 2 
 Ví dụ: 7 – 6 = 7 + (–6) 
 +7: 0000 0000  0000 0111 
–6: 1111 1111  1111 1010 
+1: 0000 0000  0000 0001 
 Tràn nếu kết quả vượt ngưỡng 
 Phép trừ 2 toán hạng cùng dấu, không bao giờ tràn 
 Trừ 1 toán hạng âm với 1 toán hạng dương 
 Tràn nếu bit dấu của kết quả là 0 
 Trừ 1 toán hạng dương với 1 toán hạng âm 
 Tràn nếu bit dấu của kết quả là 1 
BK 
TP.HCM 
Xử lý tràn 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 11 
 Một số ngôn ngữ (như C) không xử lý tràn 
 Sử dụng lệnh MIPS: addu, addui, subu 
 Các ngôn ngữ khác (như Ada, Fortran) yêu 
cầu xử lý tràn bằng ngoại lệ 
 Sử dụng lệnh MIPS: add, addi, sub 
 Khi có tràn, bẫy bằng ngoại lệ & xử lý: 
 Cất PC vào thanh ghi exception PC (EPC) 
 Nhảy đến chương trìn xử lý tràn 
 Dùng mfc0 khôi phục giá trị EPC value, trở về sau 
khi xử lý tràn 
BK 
TP.HCM 
Phép nhân 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 12 
 Bắt đầu bằng phép nhân thuần túy 
 1000 
× 1001 
 1000 
 0000 
 0000 
1000 
1001000 
Length of product is 
the sum of operand 
lengths 
multiplicand 
multiplier 
product 
BK 
TP.HCM 
Phần cứng thực hiện nhân 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 13 
BK 
TP.HCM 
Bộ nhân cải thiện 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 14 
 Các bước song song: add/shift 
 Một chu kỳ cho mỗi phép cộng (tích thành phần) 
 Có thể chấp nhận khi tần xuất thấp 
BK 
TP.HCM 
Bộ nhân nhanh 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 15 
 Sử dụng nhiều bộ cộng cùng lúc 
 Cost/performance tradeoff 
 Có thể thực hiện theo cơ chế ống 
 Nhiều tác vụ nhân thực hiện cùng lúc 
BK 
TP.HCM 
Lệnh nhân trong MIPS 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 16 
 Kết quả sẽ là 64-bit, chứa trong 2 thanh ghi 
32-bit 
 HI: chứa 32-bit cao 
 LO: chứa 32-bit thấp 
 Lệnh nhân 
 mult rs, rt / multu rs, rt 
 64-bit kết quả chứa trong HI/LO 
 mfhi rd / mflo rd 
 Chuyển từ HI/LO vào rd 
 Có thể kiểm tra giá trị HI xem kết quả phép nhân có 
tràn? 
 mul rd, rs, rt 
 32 bits thấp của kết quả phép nhân –> rd 
BK 
TP.HCM 
Phép chia 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 17 
 Kiểm tra chia 0 báo lỗi 
 Long division approach 
 If divisor ≤ dividend bits 
 1 bit in quotient, subtract 
 Otherwise 
 0 bit in quotient, bring down 
next dividend bit 
 Restoring division 
 Do the subtract, and if remainder 
goes < 0, add divisor back 
 Signed division 
 Divide using absolute values 
 Adjust sign of quotient and 
remainder as required 
 1001 
 1001010/1000 
 -1000 
 10 
 101 
 1010 
 -1000 
 10 
Toán hạng n-bit cho kết quả n-bit 
thương số và số dư 
Quotient 
(thương số) 
Dividend 
(số bị chia) 
Remainder 
(số dư) 
Divisor 
(số chia) 
BK 
TP.HCM 
Phần cứng thực hiện chia 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 18 
Initially dividend 
Initially divisor 
in left half 
BK 
TP.HCM 
Bộ chia cải thiện 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 19 
 Một chu kỳ cho mỗi phép trừ thành phần 
 Tương tự rất nhiều với bộ nhân 
 Có thể dùng cùng một phần cứng cho cả 2 
BK 
TP.HCM 
Bộ chia nhanh 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 20 
 Không thể thực hiện song song như 
trong bộ nhân 
 Dấu trong mỗi phép trừ thành phần là điều 
kiện 
 Có thể tạo bộ chia nhanh (e.g. SRT 
devision) 
BK 
TP.HCM 
Lệnh chia trong MIPS 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 21 
 Thanh ghi HI/LO chứa kết quả phép 
chia 
 HI: 32-bit số dư (remainder) 
 LO: 32-bit (kết quả) quotient 
 Lệnh trong MIP 
 div rs, rt / divu rs, rt 
 Không kiểm tra tràn hoặc lỗi /0 
 Nếu có yêu cầu, phần mềm phải tự thực hiện 
 Sử dụng lệnh mfhi, mflo để lấy kết quả 
BK 
TP.HCM 
Dấu chấm di động (Floating Point) 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 22 
 Biểu diễn các số khác số nguyên (số thực) 
 Bao gồm cả số rất nhỏ lẫn số rất lớn 
 Giống như biểu diễn số trong khoa học 
 –2.34 × 1056 
 +0.002 × 10–4 
 +987.02 × 109 
 Kiểu nhị phân 
 ±1.xxxxxxx2 × 2
yyyy 
 Kiểu float và double trong ngôn ngữ C 
BK 
TP.HCM 
Chuẩn của hệ thống số chấm di động 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 23 
 Định chuẩn bởi Tổ chức IEEE(754-1985) 
 Được phát triển nhằm đáp ứng tiêu 
chuẩn trình bày thống nhất 
 Dễ sử dụng và chuyển đổi giữa các bộ mã 
trong khoa học 
 Hiện nay trở thành thông dụng 
 Tồn tại 2 cách biểu diễn 
 Chính xác đơn(32-bit) 
 Chính xác kép (64-bit) 
BK 
TP.HCM 
Dạng định chuẩn theo IEEE 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 24 
 S: bit dấu (0  (+) , 1  (-)) 
 Normalized significand: 1.0 ≤ |significand| < 2.0 
 Luôn có 1 bit trước dấu chấm, nên bit này thường ẩn 
 Significand is Fraction with the “1.” restored 
 Exponent: excess representation: actual exponent + Bias 
 Ensures exponent is unsigned 
 Single: Bias = 127; Double: Bias = 1203 
BK 
TP.HCM 
Tầm giá trị với độ chính xác đơn 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 25 
 Giá trị (Exponents) 00000000 và 11111111 : dự trữ 
 Giá trị nhỏ nhất 
 Số mũ: 00000001 
 số mũ thực chất sẽ là = 1 – 127 = –126 
 Fraction: 00000  significand = 1.0 
 ±1.0 × 2–126 ≈ ±1.2 × 10–38 
 Giá trị lớn nhất: 
 Số mũ: 11111110 
 số mũ thực tế sẽ là = 254 – 127 = +127 
 Fraction: 11111  significand ≈ 2.0 
 ±2.0 × 2+127 ≈ ±3.4 × 10+38 
BK 
TP.HCM 
Mức độ chính xác 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 26 
 Mang tính tương đối 
 Xác định bởi các bit fraction 
 Đơn: khoảng 2–23 
 Tương đương với 23 × log102 ≈ 23 × 0.3 ≈ 6: 
 chính xác đến 6 số (hệ thập phân) 
 Kép: khoảng 2–52 
 Tương đương với 52 × log102 ≈ 52 × 0.3 ≈ 16: 
 chính xác đến 16 số (hệ thập phân) 
BK 
TP.HCM 
Ví dụ: Dấu chấm di động 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 27 
 Biểu diễn số thực thập phân: –0.75 
 –0.75 = (–1)1 × 1.12 × 2
–1 
 S = 1 
 Fraction = 1000002 
 Exponent = –1 + Bias 
 Đơn: –1 + 127 = 126 = 011111102 
 Kép: –1 + 1023 = 1022 = 011111111102 
 Single: 101111110100000 
 Double: 101111111110100000 
BK 
TP.HCM 
Ví dụ: (tt.) 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 28 
 Cho biết số thực thập phân của một số 
biểu diễn bằng dấu chấm di động (đơn) 
sau: 
 1100000010100000 
 S = 1 
 Fraction = 01000002 
 Fxponent = 100000012 = 129 
 x = (–1)1 × (1 + 012) × 2
(129 – 127) 
 = (–1) × 1.25 × 22 
 = –5.0 
BK 
TP.HCM 
Số vô hạn (Infinities) và 
 Số không hợp lệ (NaNs) 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 29 
 Exponent = 111...1, Fraction = 000...0 
 ±Infinity 
 Dùng để kiểm tra kết quả của phép tính 
 Exponent = 111...1, Fraction ≠ 000...0 
 Not-a-Number (NaN) 
 Số không hợp lệ 
 Ví dụ: chia cho zero: 0.0 / 0.0 
 Dùng để kiểm tra kết quả của phép tính 
BK 
TP.HCM 
Phép cộng 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 30 
 Giả sử có phép cộng 2 số thập phân (4 ký số) 
 9.999 × 101 + 1.610 × 10–1 
 1. Điều chỉnh dấu chấm 
 Dời số mũ của số nhỏ hơn cho đồng số mũ 
 9.999 × 101 + 0.016 × 101 
 2. Cộng hệ số 
 9.999 × 101 + 0.016 × 101 = 10.015 × 101 
 3. Chuẩn hóa kết quả & kiểm tra ngưỡng 
 1.0015 × 102 
 4. Làm tròn và điều chỉnh nếu cần thiết 
 1.002 × 102 
BK 
TP.HCM 
Cộng nhị phân 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 31 
 Giả sử cộng 2 số nhị phân (4 ký số): 
 1.0002 × 2
–1 + –1.1102 × 2
–2 (0.5 + –0.4375) 
 1. Điều chỉnh dấu chấm 
 Dời số mũ của số nhỏ hơn cho đồng số mũ 
 1.0002 × 2
–1 + –0.1112 × 2
–1 
 2. Cộng hệ số 
 1.0002 × 2
–1 + –0.1112 × 2
–1 = 0.0012 × 2
–1 
 3. Chuẩn hóa kết quả & kiểm tra ngưỡng 
 1.0002 × 2
–4, (nằm trong ngưỡng cho phép) 
 4. Làm tròn và điều chỉnh nếu cần thiết 
 1.0002 × 2
–4 (không cần điều chỉnh) = 0.0625 
BK 
TP.HCM 
Phần cứng bộ cộng (FP) 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 32 
 Phức tạp hơn rất nhiều so với bộ cộng số 
nguyên 
 Nếu thực hiện trong 1 chu kỳ đồng hồ - 
Chu kỳ quá dài 
 Dài hơn nhiều so với các phép cộng số nguyên 
 Kéo dài thời gian xung đồng hồ  ảnh hưởng đến 
các lệnh khác 
 Bộ cộng (FP) thường kéo dài nhiều chu kỳ 
 Có thể cải thiện bằng cơ chế ống 
BK 
TP.HCM 
Phần cứng bộ cộng (FP) 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 33 
Bước 1 
Bước 2 
Bước 3 
Bước 4 
BK 
TP.HCM 
Phép nhân thập phân 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 34 
 Giả sử nhân 2 số thập phân (4 ký số) 
 1.110 × 1010 × 9.200 × 10–5 
 1. Cộng số mũ 
 Nếu dùng số mũ biased, trừ biased vào tổng 
 Số mũ mới là = 10 + –5 = 5 
 2. Nhân hệ số 
 1.110 × 9.200 = 10.212  10.212 × 105 
 3. Chuẩn hóa kết quả & kiểm tra ngưỡng 
 1.0212 × 106 
 4. Làm tròn và điều chỉnh nếu cần thiết 
 5. Xác định dấu của kết quả 
 +1.021 × 106 
BK 
TP.HCM 
Phép nhân nhị phân (FP) 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính) 35 
 Giả sử nhân 2 số thập phân (4 ký số) 
 1.0002 × 2
–1 × –1.1102 × 2
–2 (0.5 × –0.4375) 
 1. Cộng số mũ 
 Unbiased: –1 + –2 = –3 
 Biased: (–1 + 127) + (–2 + 127) = –3 + 254 – 127 = –3 + 
127 
 2. Nhân hệ số 
 1.0002 × 1.1102 = 1.1102  1.1102 × 2
–3 
 3. Chuẩn hóa kết quả & kiểm tra ngưỡng 
 1.1102 × 2
–3 (không đổi: nằm trong ngưỡng cho phép) 
 4. Làm tròn và điều chỉnh nếu cần thiết 
 1.1102 × 2
–3 (no change) 
 5. Xác định dấu: (+) × (–)  (-) 
 –1.1102 × 2
–3 = –0.21875 
BK 
TP.HCM 
Phần cứng Bộ số học (FP) 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 36 
 Bộ nhân (FP) và Bộ cộng (FP) có độ 
phức tạp như nhau 
 Chỉ khác nhau cho phép tính hệ số 
 Phần cứng Bộ số học thường thực hiện 
các tác vụ sau: 
 Cộng, Trừ, Nhân, Chia, Căn, Nghịch đảo 
 Chuyển đổi FP  integer 
 Các tác vụ này thường kéo dài trong 
nhiều chu kỳ xung đồng hồ 
 Cải thiện bằng cơ chế đường ống 
BK 
TP.HCM 
Lệnh FP trong MIPS 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 37 
 Phần cứng bộ FP là một coprocessor 
 Mở rộng kiến trúc tập lệnh 
 Có các thanh ghi FP riêng 
 32 thanh ghi (đơn): $f0, $f1,  $f31 
 Chính xác kép bằng cách ghép: $f0/$f1, $f2/$f3, .. 
 Phiên bản 2 của MIPs ISA hỗ trợ 32 × 64-bit FP reg’s 
 Các lệnh FP chỉ thực hiện trên các thanh ghi FP 
 Chương trình thường không thực hiện các phép số 
nguyên trên dữ liệu FP hoặc ngược lại 
 Thanh ghi riêng không làm phức tạp thêm code 
 Các lệnh FP load và store 
 lwc1, ldc1, swc1, sdc1 
 Ví dụ: ldc1 $f8, 32($sp) 
BK 
TP.HCM 
Lệnh FP trong MIPS 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 38 
 Phép tính số học (đơn) 
 add.s, sub.s, mul.s, div.s 
 Ví dụ: add.s $f0, $f1, $f6 
 Phép tính số học (kép) 
 add.d, sub.d, mul.d, div.d 
 Ví dụ: mul.d $f4, $f4, $f6 
 Lệnh so sánh (đơn/kép) 
 c.xx.s, c.xx.d (xx is eq, lt, le, ) 
 Gán hoặc xóa bit điều kiện code 
 e.g. c.lt.s $f3, $f4 
 Rẽ nhánh theo điều kiện 
 bc1t, bc1f 
 Ví dụ: bc1t TargetLabel 
BK 
TP.HCM 
Ví dụ: Chuyển °F sang °C 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 39 
 C code: 
 float f2c (float fahr) { 
 return ((5.0/9.0)*(fahr - 32.0)); 
} 
 fahr chứa trong $f12, kết quả trong $f0, hằng số 
trong bộ nhớ toàn cục 
 Biên dịch thành MIPS code: 
 f2c: lwc1 $f16, const5($gp) 
 lwc2 $f18, const9($gp) 
 div.s $f16, $f16, $f18 
 lwc1 $f18, const32($gp) 
 sub.s $f18, $f12, $f18 
 mul.s $f0, $f16, $f18 
 jr $ra 
BK 
TP.HCM 
Ví dụ: Nhân Ma trận 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 40 
 X = X + Y × Z 
 Tất cả đều là ma trận 32 × 32, các phần tử của ma trận 64-bit 
(chính xác kép) 
 C code: 
 void mm (double x[][], 
 double y[][], double z[][]) { 
 int i, j, k; 
 for (i = 0; i! = 32; i = i + 1) 
 for (j = 0; j! = 32; j = j + 1) 
 for (k = 0; k! = 32; k = k + 1) 
 x[i][j] = x[i][j] 
 + y[i][k] * z[k][j]; 
} 
 Địa chỉ của x, y, z chứa trong $a0, $a1, $a2, và 
i, j, k trong $s0, $s1, $s2 
BK 
TP.HCM 
Ví dụ: Nhân Ma trận (tt.) 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 41 
BK 
TP.HCM 
Ví dụ: Nhân Ma trận (tt.) 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 42 
BK 
TP.HCM 
Kết luận 
25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 43 
 ISAs hỗ trợ phép số học 
 Số nguyên có dấu và không dấu 
 Floating-point approximation to reals 
 Bounded range and precision 
 Operations can overflow and underflow 
 MIPS ISA 
 Core instructions: 54 most frequently used 
 100% of SPECINT, 97% of SPECFP 
 Other instructions: less frequent