Bài giảng Kiến trúc máy tính - Chương 7: Biểu diễn và tính toán số học trong 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

NỘI DUNG

(cid:1) ALU (Arithmetic and Logical Unit) (cid:1) Biểu diễn và tính toán số nguyên (fixed

point)

(cid:1) Biễu diễn và tính toán số dấu chấm động

(floating point)

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 2

ALU

(cid:1) Thành phần thực hiện tất cả các phép tính

số học và luận lý

(cid:1) 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.

(cid:1) Được xây dựng từ các linh kiện điện tử số

ALU

flags

control unit

Registers

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 3

ALU

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 4

BIỂU DIỄN SỐ NGUYÊN (fixed point)

(cid:1) Dùng số nhị phân (cid:1) Integer có nghĩa là tập hợp tất cả các số

nguyên

(cid:1) Integer có thể là số dương hay số âm

Biễu diễn số nguyên: biễu diễn theo dấu và độ lớn

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 5

(cid:1) 0 = + (cid:1) 1 = - (cid:1) Ví dụ

+18 = 0 001 0010 -18 = 1 001 0010

(cid:1) Bit đầu tiên bên trái là bit dấu

− 2n

aunê

i a2 i

− 1n

∑

= 0i − 2n

−

aunê

i a2 i

− 1n

∑

     

= 0i

(cid:1) Vấn đề biểu diễn số 0 ( +010=0 0000000; -010=1 0000000) (cid:1) Tổng quát một số A gồm n bit

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 bù hai

(cid:1) Cũng dùng bit đầu tiên bên trái làm bit dấu (cid:1) Tổng quát số A có n bit

− 2n

− 1n

−=

− 1n

i a2 i

∑

= 0i

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 7

Biễu diễn thập phân

Biễu diễn dấu và độ lớn

Biễn diễn bù 2

0111

0110

0101

0100

0011

0010

0001

0000

-0

1000

-1

1001

1111

-2

1010

1110

-3

1011

1101

-4

1100

-5

1101

1011

-6

1110

1010

-7

1111

1001

-8

1000

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 8

Chuyển đổi qua lại giữa chiều dài chuỗi bit khác nhau

(cid:1) 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

(cid:1) Với biểu diễn theo dấu và độ lớn:

(cid:1) Di chuyển bit dấu sang vị trí ngoài cùng bên trái (cid:1) Điền bit 0 vào các chỗ trống

(cid:1) Với biểu diễn bù 2

(cid:1) Di chuyển bit dấu sang vị trí ngoài cùng bên trái (cid:1) Điền bit dấu vào các chỗ trống

Tính toán số nguyên trong biểu diễn bù 2: Lấy số đảo

(cid:1) 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.

(cid:1) Trong số bù 2 làm hai bước:

(cid:1) Đảo ngược các bit (cid:1) Cộng với 1

(cid:1) Ví dụ:

+18= 0001 0010 1110 1101 + 1 11101110 = -18

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 9

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 10

A và B là hai số đảo của nhau

− 2n

− 1n

−=

− 1n

i a2 i

∑

= 0i

− 2n

− 1n

−=

++ 1

− 1n

i a2 i

∑

= 0i

Cộng và trừ số biểu diễn bù 2

(cid:1) Cộng và trừ như hai số không dấu (cid:1) Phép trừ: X-Y = X+(-Y) (cid:1) Bỏ qua bit nhớ vượt ra ngoài kích thước từ

nhớ

(cid:1) 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.

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 11

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 12

Ví dụ

1001 = -7

1100 = -4

+0101 = 5

+0100 = 4

1110 = -2

10000 = 0

0011 = 3

1100 = -4

+0100 = 4

+1111 = -1

0111 = 7

11011 = -5

Tính tràn

0101 = 5

1001 = -7

+1010 = -6

+0100 = 4

10011 = Tràn

1001 = Tràn

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 13

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 14

Sơ đồ phần cứng thực hiện cộng và trừ

Biể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

Nhân hai số không dấu

(cid:1) Phức tạp hơn, có nhiều giải thuật được dùng

trong các máy khác nhau.

(cid:1) Nhân hai số nhị phân không dấu n bit tạo ra

tích số có 2n bit

Sơ đồ khối bộ nhân bằng cách cộng và dịch

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 17

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 18

Lưu đồ thuật toán nhân hai số không dấu

Start

C,A M Số bị nhân Q Số nhân Count n

Yes

Q0=1?

C,A<--A+M

Dịch phải C,A,Q Count = Count -1

Yes

Count=0?

Tích số chứa trong A và Q

End

Quá trình nhân

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 19

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 20

Nhân hai số bù 2

(cid:1) Không thể nhân như hai số không dấu, ví dụ

(cid:1) không dấu 11(1011) x 13 (1101) = 143 (10001111) (cid:1) bù 2

1011(-5) x 1101 (-3) = 10001111 (-113) -----> Sai

(cid:1) Vấn đề ở chỗ số âm

Khử yếu tố âm

(cid:1) Ví dụ nếu nhân hai số 1001 và 0011 (cid:1) Không dấu: được 00011011 (9 x 3=27) (cid:1) Số bù 2: được 11101011 (-7 x 3 = -21)

1001 (9) x 0011 (3)

1001 (-7) x 0011 (3)

00001001 1001 x 20 00010010 1001 x 21 00011011 (27)

11111001 (-7) x 20 = -7 11110010 (-7) x 21= -14 11101011 (-21)

Bù 2

Không dấu

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 21

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 (tt)

(cid:1) Phương pháp:

(cid:1) Đổ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.

(cid:1) Giải thuật Booth được chuộng hơn

Giải thuật Booth

(cid:1) 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

(cid:1) Khởi động với A=0, Q-1= 0 và Count = n (cid:1) While Count>0 (cid:1) switch (Q0Q-1) (cid:1) Case 01 (cid:1) Case 10

A=A+M A=A-M

(cid:1) rsht (A,Q,Q-1), dịch số học sang phải. (cid:1) Count = Count - 1

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 23

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 24

Lưu đồ giải thuật Booth

Ví dụ 7 x 3 theo giải thuật Booth

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 25

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 26

Chia hai số nhị phân

Thương số

Số bị chia

Số chia

1011

Số dư

00001101 10010011 1011 001110 1011 001111 1011 100

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ư

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 27

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 28

Áp dụng chia hai số bù 2

(cid:1) M=số chia, AQ=số bị chia, Count = n (cid:1) While Count>0

(cid:1) dịch cả Q,A sang trái 1 bit (cid:1) if M và A cùng dấu

(cid:1) A=A-M

(cid:1) else

(cid:1) A=A+M (cid:1) if A không đổi dấu

(cid:1) Q0=1

(cid:1) else

(cid:1)

if A=0 và Q=0 (cid:1) Q0=1

(cid:1) else

(cid:1) 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.

(cid:1) Count = Count -1

start

AQ = số bị chia M = số chia count = số bit

ShiftLeft (AQ) count=count-1

yes

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 29

A=A+M

A=A-M

yes

M và A cùng dấu?

A=0 và Q=0?

yes

Q0=1

A=giá trị A cũ

yes

stop

count=0? Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM

A không đổi dấu?

Ví dụ

A

Q = 0111 (7)

M=1101 (-3)

0000

0111

Khởi tạo giá trị ban đầu

0000

1110

shift

1101

add

0000

1110

restore

0001

1100

shift

1110

add

0001

1100

restore

0011

1000

shif

0000

add

0000

1001

0001

0010

set Q0=1 shift

1110

add

0001

0010

restore

Biểu diễn dấu chấm động (floating point)

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 31

rất lớn hay rất nhỏ.

(cid:1) Nguyên lý: Dùng dạng ký hiệu khoa học để biểu diễn số

(cid:1) ví dụ: 168 000 000 000 000 = 1.68 x 1014 0.000000000000168 = 1.68 x 10-14

(cid:1) 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ố!

(cid:1) Dùng cách tương tự để biểu diễn số nhị phân, dạng: ±S x B±E

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 32

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

Chuẩn hóa

(cid:1) Số được viết dưới dạng chuẩn:

± 1.bbb…b × 2±E

(cid:1) Tại sao? – dễ tính toán, dễ so sánh (không âm) (cid:1) Cơ sở nào?

(cid:1) Dùng bit dấu (sign bit) (cid:1) Không cần lưu bit 1 bên trái dấu chấm (mặc định) (cid:1) bbb…b được lưu nguyên dạng (cid:1) E được lưu ở dạng mã thừa (bias) (cid:1) Không cần lưu cơ số

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 33

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 34

Ví dụ

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

-1.1010001 x 2-10100 = 1 01101011 10100010000000000000000 = -1.6328125 x 2-20

Dải số ứng với 32-bit word

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 35

(2-2-23) x 2128 -2-127 2-127 (2-2-23) x 2128

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 36

Mật độ số

(cid:1) Các số không trải đều trên trục số, càng gần zero mật độ càng cao.

(cid:1) Cần áp dụng phương pháp làm tròn. (cid:1) Cân đối và giải pháp

(cid:1) Tăng số mũ --> mở rộng dải, số lượng số không đổi--> độ chính

xác giảm.

(cid:1) Chỉ có cách duy nhất là tăng số bit (single precision (32 bit) và

double-precision (64bit))

(cid:1) Dùng cơ số lớn, ví dụ thay 210100 = 16101

Chuẩn IEEE 754

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 37

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 38

Tham khảo về chuẩn IEE 754

[1]http://www.eecs.berkeley.edu/~wkahan/ieee754status/IEEE754.PDF [2] http://babbage.cs.qc.edu/courses/cs341/IEEE-754references.html

Tính toán trên số dấu chấm động

(cid:1) Cộng và trừ

(cid:1) Kiểm tra số có bằng zero hay không (cid:1) Điều chỉnh hai số cho bằng số mũ (cid:1) Cộng hay trừ phần định trị (cid:1) 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

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 39

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 40

Lưu đồ cộng và trừ

Tính toán trên số dấu chấm động (tt)

(cid:1) Nhân và chia

(cid:1) Kiểm tra số có bằng zero hay không (cid:1) Cộng hay trừ phần mũ (cid:1) Kiểm tra tràn trên và tràn dưới (cid:1) Nhân hay chia phần định trị (cid:1) Chuẩn hóa (cid:1) Làm tròn

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 41

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 42

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

Ví dụ

(cid:1) X = 0.3 × 102 = 30 (cid:1) Y = 0.2 × 103 = 200 Tính

(cid:1) X + Y=(0.3 x 102-3 + 0.2) x 103 = 0,23 x 103 (cid:1) X – Y=(0.3 x 102-3 - 0.2) x 103 = - 0,17 x 103 (cid:1) X × Y= (0.3 x 0.2) x 102+3 = 0.006 x 105 (cid:1) X ÷ Y = (0.3÷ 0.2) x 10 2-3 = 1.5 x 10-1

Chuẩn IEEE cho số học dấu chấm động nhị phân

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 45

(cid:1) - ∞ < mỗi số hữu hạn < +∞ (cid:1) Các phép toán số học liên quan đến vô cực

(cid:1) Vô cực

dụ mũ quá nhỏ)

(cid:1) Quiet and signaling NaNs (NaN = Not a Number) (cid:1) Các số không chuẩn – để kiểm soát tràn số mũ (số rất nhỏ, ví

Biểu diễn và tính toán số học _Nguyễn Hồng Sơn_PTITHCM 46

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.