Bài giảng Kiến trúc máy tính - Bài 7: Biểu diễn và tính toán số học trong máy tính - Nguyễn Hồng Sơn

11 Bài 7 BIỂU DIỄN VÀ TÍNH TOÁN SỐ HỌC TRONG MÁY TÍNH Nguyễn Hồng Sơn Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 2 NỘI DUNG
ALU (Arithmetic and Logical Unit)
Biểu diễn và tính toán số nguyên (fixed point)
Biễu diễn và tính toán số dấu chấm động (floating point) 2Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 3 ALU
Thành phần thực hiện tất cả các phép tính số học và luận lý
Tất cả các thành phần khác của máy tính nhằm chuyển data vào ALU để nó xử lý và sau đó lấy ra.
Được xây dựng từ các linh kiện điện tử số Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 4 ALU ALU control unit Registers flags Registers 3Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 5 BIỂU DIỄN SỐ NGUYÊN (fixed point)
Dùng số nhị phân
Integer có nghĩa là tập hợp tất cả các số nguyên
Integer có thể là số dương hay số âm Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 6 Biễu diễn số nguyên: biễu diễn theo dấu và độ lớn
Bit đầu tiên bên trái là bit dấu
0 = +
1 = -
Ví dụ +18 = 0 001 0010 -18 = 1 001 0010
Vấn đề biểu diễn số 0 ( +010=0 0000000; -010=1 0000000)
Tổng quát một số A gồm n bit       =− = = ∑ ∑ − = − − = − 2n 0i 1ni i 2n 0i 1ni i 1aunêa2 0aunêa2 A 4Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 7 Biễu diễn số nguyên: biễu diễn bù hai
Cũng dùng bit đầu tiên bên trái làm bit dấu
Tổng quát số A có n bit ∑ − = − − +−= 2n 0i i i 1n 1n a2a2A Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 81000--8 10011111-7 10101110-6 10111101-5 11001100-4 11011011-3 11101010-2 11111001-1 -1000-0 00000000+0 00010001+1 00100010+2 00110011+3 01000100+4 01010101+5 01100110+6 01110111+7 --+8 Biễn diễn bù 2Biễu diễn dấu và độ lớnBiễu diễn thập phân 5Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 9 Chuyển đổi qua lại giữa chiều dài chuỗi bit khác nhau
Khi lưu một số có n bit vào m bit với m>n, số đã bị chuyển đổi sang dạng số m bit
Với biểu diễn theo dấu và độ lớn:
Di chuyển bit dấu sang vị trí ngoài cùng bên trái
Điền bit 0 vào các chỗ trống
Với biểu diễn bù 2
Di chuyển bit dấu sang vị trí ngoài cùng bên trái
Điền bit dấu vào các chỗ trống Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 10 Tính toán số nguyên trong biểu diễn bù 2: Lấy số đảo
Trong biểu diễn dấu và độ lớn để lấy số đảo của một số chỉ cần đảo ngược bit dấu.
Trong số bù 2 làm hai bước:
Đảo ngược các bit
Cộng với 1
Ví dụ: +18= 0001 0010 1110 1101 + 1 11101110 = -18 6Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 11 A và B là hai số đảo của nhau ∑ − = − − +−= 2n 0i i i 1n 1n a2a2A ∑ − = − − ++−= 2n 0i i i 1n 1n a21a2B Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 12 Cộng và trừ số biểu diễn bù 2
Cộng và trừ như hai số không dấu
Phép trừ: X-Y = X+(-Y)
Bỏ qua bit nhớ vượt ra ngoài kích thước từ nhớ
Khi hai số cùng âm hay cùng dương và kết quả có dấu ngược lại thì có sự kiện tràn xảy ra, ALU thông báo sự kiện để ngăn chặn. 7Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 13 Ví dụ 1001 = -7 +0101 = 5 1110 = -2 1100 = -4 +0100 = 4 10000 = 0 0011 = 3 +0100 = 4 0111 = 7 1100 = -4 +1111 = -1 11011 = -5 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 14 Tính tràn 0101 = 5 +0100 = 4 1001 = Tràn 1001 = -7 +1010 = -6 10011 = Tràn 8Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 15 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 16 Sơ đồ phần cứng thực hiện cộng và trừ 9Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 17 Nhân hai số không dấu
Phức tạp hơn, có nhiều giải thuật được dùng trong các máy khác nhau.
Nhân hai số nhị phân không dấu n bit tạo ra tích số có 2n bit Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 18 Sơ đồ khối bộ nhân bằng cách cộng và dịch 10 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 19 Lưu đồ thuật toán nhân hai số không dấu Start C,A 0 M Số bị nhân Q Số nhân Count n Q0=1? Dịch phải C,A,Q Count = Count -1 C,A<--A+M Count=0? End No Yes YesNo Tích số chứa trong A và Q Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 20 Quá trình nhân 11 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 21 Nhân hai số bù 2
Không thể nhân như hai số không dấu, ví dụ
không dấu 11(1011) x 13 (1101) = 143 (10001111)
bù 2 1011(-5) x 1101 (-3) = 10001111 (-113) -----> Sai
Vấn đề ở chỗ số âm Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 22 Khử yếu tố âm
Ví dụ nếu nhân hai số 1001 và 0011
Không dấu: được 00011011 (9 x 3=27)
Số bù 2: được 11101011 (-7 x 3 = -21) 1001 (9) x 0011 (3) 00001001 1001 x 20 00010010 1001 x 21 00011011 (27) 1001 (-7) x 0011 (3) 11111001 (-7) x 20 = -7 11110010 (-7) x 21= -14 11101011 (-21) Không dấu Bù 2 12 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 23 Khử yếu tố âm (tt)
Phương pháp:
Đổi các thừa số sang số dương, nhân bình thường và sau đó sẽ lấy dạng bù 2 của kết quả nếu hai thừa số là khác dấu.
Giải thuật Booth được chuộng hơn Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 24 Giải thuật Booth
Lưu số bị nhân vào thanh ghi M và số nhân vào thanh ghi Q, dùng một ô nhớ Q -1 đặt bên phải Q
Khởi động với A=0, Q -1= 0 và Count = n
While Count>0
switch (Q0Q-1)
Case 01 A=A+M
Case 10 A=A-M
rsht (A,Q,Q -1), dịch số học sang phải.
Count = Count - 1 13 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 25 Lưu đồ giải thuật Booth == = Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 26 Ví dụ 7 x 3 theo giải thuật Booth 14 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 27 Chia hai số nhị phân 00001101 100100111011 1011 1011 1011 001110 001111 100 Thương số Số bị chiaSố chia Số dư Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 28 Lưu đồ giải thuật chia hai số nhị phân không dấu Q chứa thương số A chứa số dư 15 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 29 Áp dụng chia hai số bù 2
M=số chia, AQ=số bị chia, Count = n
While Count>0
dịch cả Q,A sang trái 1 bit
if M và A cùng dấu
A=A-M
else
A=A+M
if A không đổi dấu
Q0=1
else
if A=0 và Q=0
Q0=1
else
A=Restore (A)// lấy lại giá trị A trước khi cộng/trừ với M, không lấy trị hiện hành.
Count = Count -1 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 30 start AQ = số bị chia M = số chia count = số bit ShiftLeft (AQ) count=count-1 M và A cùng dấu?A=A+M A=A-M A không đổi dấu?A=0 và Q=0? count=0? A=giá trị A cũ Q0=1 stop yes yes yes yes no no no no 16 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 31 Ví dụ restore00100001 add1110 shift00100001 set Q0=110010000 add0000 shif10000011 restore11000001 add1110 shift11000001 restore11100000 add1101 shift11100000 Khởi tạo giá trị ban đầu01110000 M=1101 (-3)Q = 0111 (7)A Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 32 Biểu diễn dấu chấm động (floating point)
Nguyên lý: Dùng dạng ký hiệu khoa học để biểu diễn số rất lớn hay rất nhỏ.
ví dụ: 168 000 000 000 000 = 1.68 x 1014 0.000000000000168 = 1.68 x 10-14
Linh động chuyển dấu chấm thập phân đến vị trí thuận tiện và dùng số mũ để theo dõi vị trí dấu chấm=> giúp biểu diễn dễ dàng một số rất lớn hay rất nhỏ chỉ bằng vài ký số!
Dùng cách tương tự để biểu diễn số nhị phân, dạng: ±S x B±E 17 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 33 Ví dụ • Số âm sign=1. Số dương sign = 0 • Số mũ thực = Biased Exponent - Bias • Bias = 2k-1-1= 2(8-1)-1=27-1 = 127 • Significand (mantissa): định trị, là giá trị sau dấu chấm • Ví dụ: 0 11000100 11100000000000000000000 Dấu + Định trị = 1/2 + 1/4 + 1/8 = 0.875 Số mũ = 69 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 34 Chuẩn hóa
Số được viết dưới dạng chuẩn: ± 1.bbbb × 2±E
Tại sao? – dễ tính toán, dễ so sánh (không âm)
Cơ sở nào?
Dùng bit dấu (sign bit)
Không cần lưu bit 1 bên trái dấu chấm (mặc định)
bbbb được lưu nguyên dạng
E được lưu ở dạng mã thừa (bias)
Không cần lưu cơ số 18 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 35 Ví dụ -1.1010001 x 2-10100 = 1 01101011 10100010000000000000000 = -1.6328125 x 2-20 1.1010001 x 210100 = 0 10010011 10100010000000000000000 = 1.6328125 x 220 -1.1010001 x 210100 = 1 10010011 10100010000000000000000 = -1.6328125 x 220 1.1010001 x 2-10100 = 0 01101011 10100010000000000000000 = 1.6328125 x 2-20 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 36 Dải số ứng với 32-bit word -2-127 2-127 (2-2-23) x 2128(2-2-23) x 2128 19 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 37 Mật độ số
Các số không trải đều trên trục số, càng gần zero mật độ càng cao.
Cần áp dụng phương pháp làm tròn.
Cân đối và giải pháp
Tăng số mũ --> mở rộng dải, số lượng số không đổi--> độ chính xác giảm.
Chỉ có cách duy nhất là tăng số bit (single precision (32 bit) và double-precision (64bit))
Dùng cơ số lớn, ví dụ thay 210100 = 16101 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 38 Chuẩn IEEE 754 20 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 39 [1] [2] Tham khảo về chuẩn IEE 754 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 40 Tính toán trên số dấu chấm động
Cộng và trừ
Kiểm tra số có bằng zero hay không
Điều chỉnh hai số cho bằng số mũ
Cộng hay trừ phần định trị
Chuẩn hóa kết quả (làm tròn nếu cần) (123 x 100) - (456 x 10-2) = (123 x 100) + (4.56 x 100) = 127.56 x 100 21 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 41 Lưu đồ cộng và trừ Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 42 Tính toán trên số dấu chấm động (tt)
Nhân và chia
Kiểm tra số có bằng zero hay không
Cộng hay trừ phần mũ
Kiểm tra tràn trên và tràn dưới
Nhân hay chia phần định trị
Chuẩn hóa
Làm tròn 22 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 43 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 44 23 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 45 Ví dụ
X = 0.3 × 102 = 30
Y = 0.2 × 103 = 200 Tính
X + Y=(0.3 x 102-3 + 0.2) x 103 = 0,23 x 103
X – Y=(0.3 x 102-3 - 0.2) x 103 = - 0,17 x 103
X × Y= (0.3 x 0.2) x 102+3 = 0.006 x 105
X ÷ Y = (0.3÷ 0.2) x 10 2-3 = 1.5 x 10-1 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 46 Chuẩn IEEE cho số học dấu chấm động nhị phân
Vô cực
- ∞ < mỗi số hữu hạn < +∞
Các phép toán số học liên quan đến vô cực
Quiet and signaling NaNs (NaN = Not a Number)
Các số không chuẩn – để kiểm soát tràn số mũ (số rất nhỏ, ví dụ mũ quá nhỏ) 24 Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 47 Bài tập 1.Lấy vài ví dụ nhân hai số bù 2 bất kỳ và thực hiện phép nhân theo giải thuật Booth. 2. Lấy vài ví dụ chia hai số bù 2 bất kỳ và thực hiện phép chia theo giải thuật chia hai số bù 2. 3. Cho định dạng 8-bit phần mũ và 23-bit phần định trị, hãy cho biết chuỗi bit biểu diễn của: a. -720 b. 0,645 4. Mô tả hoạt động cộng số dấu chấm động, cho phần định trị bị xén còn 4 ký số thập phân: a. 0.5566 x 103 + 0.7777 x 103 b. 0.3344 x 102 - 0.8877 x 10-1