Bài giảng Kiến trúc máy tính - Chương 3: Phép toán số học trên máy tính (Phần 1)

Nội dung text: Bài giảng Kiến trúc máy tính - Chương 3: Phép toán số học trên máy tính (Phần 1)

1. CE Phép Cộng & Phép Trừ 1. Overflow của số không dấu (Unsigned number) Ví dụ 2: 1. A = 11001000 - Số không dấu B = 1100111 B = 01100111 (điền đủ 8 bit) - Dùng 8 bit biểu diễn 2. 11001000 A = 200 (10) 01100111 B = 103 (10) A + B = ? 100101111 => kết quả là 9 bit, dư bit 1 tràn Trả lời: A + B = 255 và bị tràn 255 – giá trị lớn nhất của số 8 bit 11
2. CE Phép Cộng & Phép Trừ 2. Overflow của số có dấu (Signed number) Khi thực hiện phép cộng/trừ hai số có dấu, phép toán bị tràn nếu xảy ra một trong 4 tình huống như bảng sau: • Hàng 1: Nếu cộng hai số dương, mà kết quả âm => phép toán bị tràn • Hàng 2: Nếu cộng hai số âm, mà kết quả dương => phép toán bị tràn • Hàng 3: Nếu trừ một số dương cho một số âm, mà kết quả âm => phép toán bị tràn (Tình huống này giống như hàng 1, trừ một số dương cho một số âm, tức là cộng một số dương với một số dương mà kết quả là âm thì bị tràn) • Hàng 4: Nếu trừ một số âm cho một số dương, mà kết quả dương => phép toán bị tràn • (Tình huống giống như hàng 2, trừ một số âm cho một số dương, tức là cộng một số âm với một Có thể tóm tắt như sau: số âm mà kết quả là dương thì bị tràn) • Nếu là phép trừ quy về phép cộng dùng bù 2 • Quy tắc tràn số tính như sau:  Nếu cộng hai số trái dấu, kết quả không bao giờ bị tràn  Nếu cộng hai số cùng dấu mà ra kết quả khác dấu => tràn 12
3. CE Phép Cộng & Phép Trừ Ba ví dụ về Overflow 1. A = 11001000 của số có dấu B = 01100111 2. Cộng lại: Ví dụ 3: 11001000 - Số có dấu 01100111 - Dùng 8 bit biểu diễn - Tính A + B 100101111 => kết quả phép cộng 00101111 (không quan tâm bit 1 dư ra) 3. Kiểm tra tràn: Xét bảng bên dưới với phép cộng, A 0, không có hàng nào tương ứng => không bị tràn (Cộng 2 số trái dấu chắc chắn không bị tràn) A + B = 11001000 + 01100111 = -56(10) + 103(10) = 00101111(2) = 47(10) 13
4. CE Phép Cộng & Phép Trừ Ba ví dụ về Overflow 1. A = 11110111 của số có dấu B = 11101101 2. 11110111 Ví dụ 4: 11101101 - Số có dấu - Dùng 8 bit biểu diễn 111100100 => kết quả phép cộng 11100100 (không quan tâm bit 1 - Tính A + B dư ra) 3. Kiểm tra tràn: Xét bảng bên dưới với phép cộng, A không tràn) A + B = 11110111 + 11101101 = –9(10) –19(10) = 11100100(2) = -28(10) 14
5. CE Phép Cộng & Phép Trừ Ba ví dụ về Overflow 1. A = 11001000 của số có dấu B = 01100111 (điền đủ 8 bit) B-bù 2 = 10011001 Ví dụ 5: 2. 11001000 - Số có dấu 10011001 - Dùng 8 bit biểu diễn - Tính A - B = ? 101100001 => kết quả phép cộng 01100001 (không quan tâm bit 1 dư ra) 3. Kiểm tra tràn: A = 11001000 = -56(10) B = 10011001 = -103(10) Xét bảng bên dưới với phép trừ, A 0 tương ứng với hàng A + B nếu đúng phải bằng - 159, số này rõ ràng vượt ra thứ 3, và tổng phép trừ trên cũng ra dương, đúng như trong giá trị cuối của khỏi giới hạn của biểu diễn có hàng 3 trong bảng => bị tràn dấu bù 2 dùng 8 bits (Cộng 2 số âm mà kết quả dương => bị tràn) A - B = -128(10) và bị tràn (-128 là giá trị nhỏ nhất của số có dấu 8 bit) + 15
6. CE Phép Cộng & Phép Trừ Như vậy, với các phép toán bị tràn:  Nếu là số không dấu, kết quả là giá trị lớn nhất trong giới hạn có thể biểu diễn  Nếu là số có dấu:  Nếu cộng hai số âm, kết quả là giá trị nhỏ nhất trong giới hạn có thể biểu diễn  Nếu cộng hai số dương, kết quả là giá trị lớn nhất trong giới hạn có thể biểu diễn Giới hạn có thể biểu diễn của một số: Số không dấu n-bit: từ 0 tới (2n-1) Số có dấu n-bit: từ -2n-1 tới (2n-1-1) Ví dụ: Biểu diễn số không dấu dùng 8 bit: số sẽ từ 0 tới 255 Biểu diễn số có dấu dùng 3 bit: số sẽ từ -22 tới 22-1 hay bao gồm: -4, -3, -2, -1, 0, 1, 2, 3 Biểu diễn số có dấu dùng 8 bit: số sẽ từ -27 tới 27-1 hay bao gồm: -128, -127, , 0, , 127 16
7. CE Phép Cộng & Phép Trừ Xử lý tràn  Từ đó, các nhà thiết kế phần cứng phải cung cấp một cách để bỏ qua tràn hoặc phát hiện tràn trong các trường hợp cần thiết.  Trong kiến trúc MIPS, mỗi lệnh thường có hai dạng lệnh tương ứng với xét overflow hay bỏ qua overflow: ■ Lệnh cộng (add), cộng số tức thời (addi), trừ (sub) là các lệnh có xét overflow, tức sẽ báo lỗi và phát ra một ngoại lệ (exception) nếu kết quả bị tràn. ■ Lệnh cộng (addu), cộng số tức thời (addiu), và trừ (subu) không gây ra ngoại lệ tràn. Khi một chương trình đang thực thi, nếu bị tác động đột ngột (lỗi hoặc phải thi hành một tác vụ khác, ), buộc phải dừng luồng chương trình đang chạy này và gọi đến một chương trình không định thời trước đó thì được gọi là một “interrupt” hay một “exception”. Lưu ý: Trong một số hệ thống máy tính, thuật ngữ ‘interrupt’ được sử dụng như exception, nhưng ở một số hệ thống thì có sự phân biệt hai thuật ngữ này 17
8. CE PHÉP TOÁN SỐ HỌC TRÊN MÁY TÍNH 1. Giới thiệu 2. Phép cộng & Phép trừ 3. Phép Nhân 4. Phép chia 5. Số chấm động 18
9. CE Phép nhân Ví dụ Multiplicand: số bị nhân Multiplier: số nhân Product: tích Ví dụ trên là nhân hai số đang ở dạng thập phân, nhưng các chữ số đều là 0 và 1. Phép nhân trên hai số nhị phân cũng tương tự, và luôn luôn có 2 trường hợp: 1. Chép số bị nhân xuống vị trí thích hợp (1 ×multiplicand) nếu chữ số tương ứng đang xét ở số nhân là 1. 2. Đặt số 0 (0 ×multiplicand) vào vị trí thích hợp nếu chữ số tương ứng đang xét ở số nhân là 0. 19
10. CE Phép Nhân Giải thuật thực hiện phép nhân từng bước ở phần cứng (cho hai số 32 bit) Hình 1: Cấu trúc phần cứng thực hiện phép nhân Chú ý: khi thực hiện phép nhân cho giải thuật theo sơ đồ, ta thấy có 3 bước và 3 bước này được lặp lại 32 lần. Nếu mỗi bước được thực hiện bởi 1 chu kỳ xung clock thì giải thuật này yêu cầu gần 100 chu kỳ xung clock cho phép toán nhân hai số 32 bit. Hình 2: Sơ đồ giải thuật thực hiện phép nhân 20
11. CE Ví dụ cho phép nhân (3 ví dụ) Ví dụ 1: Thực hiện phép nhân 2(10) x 3(10) (sử dụng số 4 bit không dấu) theo cấu trúc phần cứng như hình + Lưu đồ giải thuật đi kèm cho cấu trúc phần cứng21
12. Ví dụ 1: Cấu trúc phần cứng như hình vẽ là nhân 2 số 32 bits, kết quả là số 64 bits, 2 x 3 = ? Có: thanh ghi multiplicand 64 bits (10) CE(10) thanh ghi multiplier là 32 bits 2 = 0010 thanh ghi product là 64 bits (10) Ví dụ 1 yêu cầu nhân 2 số 4 bits không dấu, sử dụng cấu trúc phần cứng tương tự như (multiplicand) hình, vậy kết quả phải là số 8 bits 3(10) = 0011 => thanh ghi multiplicand 8 bits (giá trị khởi tao 0000 0010) (multiplier) thanh ghi multiplier là 4 bits (giá trị khởi tạo 0011) thanh ghi product là 8 bits (giá trị khởi tạo 0000 0000) Iteration Step Multiplier Multiplicand Product 0 Khởi tạo 0011 0000 0010 0000 0000 - Sau khi khởi tạo xong. Mỗi vòng lặp (interation) sẽ gồm 3 bước: • B1. Kiểm tra bit 0 của multiplier xem có bằng 1 hay không; nếu bằng 1 thì product = product + multiplicand; nếu bằng 0, không làm gì cả • B2. Dịch trái Multiplicand 1 bit • B3. Dịch phải Multiplier 1 bit - Số vòng lặp cho giải thuật này đúng bằng số bit dùng biểu diễn (ví dụ 1 yêu cầu dùng số 4 bit, thì có 4 vòng lặp) - Sau khi kết thúc số vòng lặp, giá trị trong thanh ghi product chính là kết quả phép nhân 22
13. CE 8 bits 8 bits 4 bits 8 bits Bảng thực hiện từng bước giải thuật phép nhân 2 số: 00102 x 00112 23
14. CE Phép Nhân LầnĐáp lặp ánBước: bảng thực hiện từng bướcSố giảinhân thuậtSố phépbị nhân nhân Tích 2 số 0 Khởi tạo giá trị 0011 0000 0010 0000 0000 1 1a: 1 Tích = Tích + Số bị nhân 0011 0000 0010 0000 0010 2: dịch số bị nhân sang trái 1 bit 0011 0000 0100 0000 0010 3: dịch số nhân sang phải 1 bit 0001 0000 0100 0000 0010 2 1a: 1 Tích = Tích + Số bị nhân 0001 0000 0100 0000 0110 2: dịch số bị nhân sang trái 1 bit 0001 0000 1000 0000 0110 3: dịch số nhân sang phải 1 bit 0000 0000 1000 0000 0110 3 1: 0 giữ nguyên giá trị 0000 0000 1000 0000 0110 2: dịch số bị nhân sang trái 1 bit 0000 0001 0000 0000 0110 3: dịch số nhân sang phải 1 bit 0000 0001 0000 0000 0110 4 1: 0 giữ nguyên giá trị 0000 0001 0000 0000 0110 2: dịch số bị nhân sang trái 1 bit 0000 0010 0000 0000 0110 3: dịch số nhân sang phải 1 bit 0000 0010 0000 0000 0110 24
15. CE Phép Nhân Giải thuật thực hiện phép nhân ở phần cứng có cải tiến (với hai số 32 bit) multiplier Cấu trúc phần cứng của phép nhân có cải tiến  So với giải thuật trước đó thì thanh ghi số bị nhân, bộ ALU, thanh ghi số nhân tất cả điều 32 bits, chỉ có thanh ghi tích là khác – 64 bits;  Trong mỗi vòng lặp, số chu kỳ xung clock tiêu tốn có thể giảm xuống chỉ còn 1 chu kỳ 25
16. CE Ví dụ 2: Cấu trúc phần cứng như hình vẽ là nhân 2 số 32 bit, kết quả là số 64 50(8) x 23(8) = ? bit, Có: thanh ghi multiplicand 32 bit 50(8) = 101000 thanh ghi product 64 bit (khi khởi tạo, đưa multiplier vào 32 bit (multiplicand) thấp của product, còn nữa cao khởi tạo 0) 23(8) = 010011 (multiplier) Ví dụ 2 yêu cầu nhân 2 số 6 bit, sử dụng cấu trúc phần cứng tương tự như hình, vậy kết quả phải là số 12 bit thanh ghi multiplicand 6 bit (giá trị khởi tao 101000) thanh ghi product là 12 bit (6 bit thấp là multiplier, 6 bit cao là 0 000000 010011) Iteration Step/Action Multiplicand Product/Multiplier 0 Khởi tạo 101000 000000 010011 Multiplier 26
17. Ví dụ 2: Cấu trúc phần cứng như hình vẽ là nhân 2 số 32 bits, kết quả là số 64 bits, 50 x 23 = ? Có: thanh ghi multiplicand 32 bits (8) CE(8) thanh ghi product 64 bits (khi khởi tạo, đưa multiplier vào 32bits thấp của product, còn nữa cao khởi tạo 0) 50(8) = 101000 (multiplicand) Ví dụ 2 yêu cầu nhân 2 số 6 bits, sử dụng cấu trúc phần cứng tương tự như hình, vậy kết quả phải là số 12 bits 23 = 010011 (8) thanh ghi multiplicand 6 bits (giá trị khởi tao 101000) (multiplier) thanh ghi product là 12 bits (6 bit thấp là multiplier, 6 bit cao là 0 000000 010011) Iteration Step/Action Multiplicand Product/Multiplier 0 Khởi tạo 101000 000000 010011 - Sau khi khởi tạo xong. Mỗi vòng lặp (interation) sẽ gồm 2 bước: • B1. Kiểm tra bit 0 của Product/multiplier xem có bằng 1 hay không; nếu bằng 1 thì nữa cao của product/multiplier = nữa cao của product/multiplier + multiplicand; nếu bằng 0, không làm gì cả • B2. Dịch phải Product/Multiplier 1 bit - Số vòng lặp cho giải thuật này đúng bằng số bit dùng biểu diễn (ví dụ 2 yêu cầu dùng số 6 bit, thì có 6 vòng lặp) - Sau khi kết thúc số vòng lặp, giá trị trong thanh ghi product chính là kết quả phép nhân Multiplier 27
18. CE 2. Shift right Product/Multiplier 2. Shift right Product/MultiplierProduct/Multiplier 2. Shift right Product/Multiplier Kết quả phép nhân 2. Shift right Product/Multiplier 2. Shift right Product/Multiplier 2. Shift right Product/Multiplier 28
19. CE Hoặc có thể trình bày ngắn gọn như bảng sau: 29
20. CE Ví dụ 3: 50(8) x 23(8), using 8-bit number Iteration Step Multiplicand Product/ Multiplier 0 Initial values 0101 0000 0000 0000 0010 0011 1 Prod = Prod + Mcand 0101 0000 0101 0000 0010 0011 Shift right Product 0101 0000 0010 1000 0001 0001 2 Prod = Prod + Mcand 0101 0000 0111 1000 0001 0001 Shift right Product 0101 0000 0011 1100 0000 1000 3 lsb = 0, no op 0101 0000 0011 1100 0000 1000 Shift right Product 0101 0000 0001 1110 0000 0100 4 lsb = 0, no op 0101 0000 0001 1110 0000 0100 Shift right Product 0101 0000 0000 1111 0000 0010 5 lsb = 0, no op 0101 0000 0000 1111 0000 0010 Shift right Product 0101 0000 0000 0111 1000 0001 6 lsb = 0, no op 0101 0000 0101 0111 1000 0001 Shift right Product 0101 0000 0010 1011 1100 0000 7 lsb = 0, no op 0101 0000 0010 1011 1100 0000 Shift right Product 0101 0000 0001 0101 1110 0000 8 lsb = 0, no op 0101 0000 0001 0101 1110 0000 Shift right Product 0101 0000 0000 1010 1111 0000 30
21. CE Phép Nhân Phép nhân có dấu  Cách đơn giản để thực hiện phép nhân có dấu là tách phần trị tuyệt đối và dấu của số bị nhân và số nhân ra.  Lấy phần trị tuyệt đối dương tương ứng của số nhân và số bị nhân nhân nhau  Sau đó xét dấu cho tích dựa vào dấu của số nhân và số bị nhân (có thể dùng phép XOR) 31
22. CE Phép Nhân Phép nhân trong MIPS  MIPS sử dụng hai thanh ghi đặc biệt 32 bit là Hi và Lo để chứa 64 bit kết quả của phép nhân Để lấy giá trị từ thanh ghi Hi và Lo ra một thanh ghi khác, sử dụng hai lệnh dành riêng là mfhi mà mflo  Nhân hai số không dấu, MIPS cung cấp lệnh multu. Nhân hai số có dấu, MIPS cung cấp lệnh mult 32
23. CE Phép Nhân Giới thiệu một ý tưởng cải tiến phép nhân: Phép nhân theo cách hiện thực tính nhanh (Sinh viên tự tham khảo thêm) Sơ đồ hiện thực phép tính nhanh ở mức phần cứng 33
24. CE PHÉP TOÁN SỐ HỌC TRÊN MÁY TÍNH 1. Giới thiệu 2. Phép cộng & Phép trừ 3. Phép Nhân 4. Phép chia 5. Số chấm động 34
25. CE Phép Chia  Ngược lại của phép nhân là phép chia. Trường hợp ngoại lệ – chia 0. Ví dụ: Divisor: số chia Dividend: số bị chia Quotient: thương số Remainder: số dư 35
26. CE Phép Chia Giải thuật thực hiện phép chia trên phần cứng Khi khởi tạo, số chia đưa vào nữa cao Divisor sll Q, Q0=1 Khi khởi tạo, số bị chia đưa vào nữa thấp Remainder Hình 1. Sơ đồ các khối hiện thực phép chia ở mức phần cứng Chú ý: Hai số chia và bị chia là số dương, do đó kết quả thương và số dư là không âm. Thực hiện phép toán trên số dương, do đó, thương và các toán hạng của phép chia có giá trị là 32 bit, bỏ qua các số có dấu. Hình 2. Lưu đồ giải thuật của phép chia 36
27. CE Ví dụ cho phép chia (2 ví dụ) Ví dụ 1: Thực hiện phép chia 50(8)/23(8) (sử dụng số 6 bit không dấu) theo cấu trúc phần cứng như hình Khi khởi tạo, số chia đưa vào nữa cao Divisor sll Q, Q0=1 + Khi khởi tạo, số bị chia đưa vào nữa thấp của Remainder Lưu đồ giải thuật đi kèm cho cấu trúc phần cứng 37
28. Khi khởi tạo, số -Sau khi khởi tạo xong. Mỗi vòng lặp chia đưa vào nữa (interation) sẽ gồm 3 bước: cao DivisorCE • B1. Lấy toàn bộ remainder trừ divisor (hiệu lưu đè lên giá trị remainder hiện đang có) • B2. Kiểm tra hiệu vừa tính ở trên là âm hay dương (kiểm tra bit trọng số cao nhất, nếu 1 là âm, nếu 0 là dương): Nếu âm: - Lấy giá trị hiện tại của remainder Ví dụ 1: cộng với divisor, tổng lưu lại vào 50 /23 = ? Khi khởi tạo, số bị remainder (8) (8) - Dich trái quotient 1 bit Dividend = 50 = 101 000 chia đưa vào nữa 8 2 thấp của Remainder - Thêm 0 vào bit 0 của quotient (thật Divisor = 238 = 010 0112 ra thao tác này không cần, vì dịch Cấu trúc phần cứng như hình vẽ là đang làm việc trên phép chia số 32 trái 1 bit mặc định đã thêm 0 vào bit bits 0 của nó) Có: thanh ghi divisor 64 bits Nếu dương: thanh ghi quotient là 32 bits - Dich trái quotient 1 bit thanh ghi remainder là 64 bits - Chuyển bit 0 của quotient thành 1 Ví dụ 1 yêu cầu phép chia dùng số 6 bits không dấu, sử dụng cấu trúc • B3. Dịch phải Divisor 1 bit phần cứng tương tự như hình, vậy các thanh ghi trong ví dụ cần được - Số vòng lặp cho giải thuật này đúng bằng số khởi tao với số bit tương ứng: bit dùng biểu diễn + 1 (ví dụ 1 yêu cầu dùng số 6 => thanh ghi divisor 12 bits (giá trị khởi tao 010011000000 – 6 bits bit, thì có 7 vòng lặp) cao là giá trị của divisor, 6 bits thấp đưa 0 vào ) - Sau khi kết thúc số vòng lặp, giá trị trong thanh thanh ghi quotient là 6 bits (giá trị khởi tạo 000000) ghi quotient chính là kết quả phép chia, giá trị thanh ghi remainder là 12 bits (giá trị khởi tạo 000000101000 - 6 trong remainder là phần dư bits cao đưa 0 vào, 6 bits thấp đưa dividend vào) Step Action Quotient Divisor Remainder 0 Initial Vals 000 000 010 011 000000 000000 101000 (Giá trị khởi tạo)
29. Ví dụ 1: Step Action Quotient Divisor Remainder 0 Initial Vals 000 000 010 011 000 000 000 000 101 000 50(8)/23(8) = ? CE 1 R = R – D 000 000 010 011 000 000 101 101 101 000 Dividend = 508 = R 0, dịch trái Q 1 bit, Q0 = 1 000 001 000 000 100 110 000 000 000 010 Dịch phải D 1 bit 000 001 000 000 010 011 000 000 000 010 7 R = R – D 000 001 000 000 010 011 111 111 101 111 R < 0, R = R + D, dịch trái Q 1 bit 000 010 000 000 010 011 000 000 000 010 Dịch phải D 1 bit 000 010 000 000 001 101 000 000 000 010 Thương số Phần dư Ký hiệu: Q, D và R lần lượt là viết tắt của Quotion, Divisor và Remainder 39
30. CE Phép Chia Giải thuật thực hiện phép chia trên phần cứng Ví dụ 2: thực hiệp phép chia cho 2 số 4 bit sau: 710 : 210 hay 01112 : 00102 tức Remainder = Remaider + Divisor Bảng thực hiện giải thuật phép chia theo từng bước 40
31. CE Phép Chia Giải thuật thực hiện phép chia trên phần cứng có cải tiến (Sinh viên tự tham khảo thêm) Remainder Quotient Cấu trúc phần cứng phép chia có cải tiến 41
32. CE Phép Chia Phép chia có dấu Nếu phép chia có dấu . Bước 1. Bỏ qua dấu, thực hiện phép chia thông thường . Bước 2. Xét dấu  Dấu của thương sẽ trái với dấu hiện tại nếu dấu của số chia và số bị chia trái ngược nhau  Dấu của số dư: Các xác định bit dấu cho số dư bằng công thức sau: Số bị chia = Thương x Số chia + Số dư Số dư = Số bị chia – (Thương x Số chia) Ví dụ: – 7 : +2 thì thương = -3, dư = –1 Kiểm tra kết quả: –7 = –3 x 2 + (–1) = –6 – 1 42
33. CE Phép Chia Phép chia trong MIPS  Trong cấu trúc phần cứng cho phép nhân có cải tiến, hai thanh ghi Hi và Lo được ghép lại để hoạt động như thanh ghi 64 bit của Product/Multiplier Quan sát cấu trúc phần cứng cho phép nhân có cải tiến và phép chia có cải tiến, rõ ràng hai cấu trúc này tương tự nhau. Từ đó, MIPS cũng sử dụng hai thanh ghi Hi và Lo cho cả phép nhân và chia.  Sau khi phép chia thực hiện xong:  Hi chứa phần dư  Lo chứa thương số  Để xử lý cho các số có dấu và số không dấu, MIPS có 2 lệnh: phép chia có dấu (div), và phép chia không dấu (divu). 43
34. CE PHÉP TOÁN SỐ HỌC TRÊN MÁY TÍNH 1. Giới thiệu 2. Phép cộng & Phép trừ 3. Phép Nhân 4. Phép chia 5. Số chấm động 44