Bài giảng Kiến trúc máy tính - Chương 2: Ngôn ngữ máy tính và các phép toán - Nguyễn Đức Minh

.globl printf main: ori $2, $0, 5 syscall move $8, $2 loop: beq $8, $9, done blt $8, $9, brnc sub $8, $8, $9 j loop brnc: sub $9, $9, $8 j loop done: jal printf Gbl? Symbol Address str 1000 0000 cr 1000 000b yes main 0040 0000 loop 0040 000c brnc 0040 001c done 0040 0024 yes printf ???? ???? Relocation Info Address Data/Instr 1000 0000 str 1000 000b cr 0040 0018 j loop 0040 0020 j loop 0040 0024 jal printf Liên kết (linker) HUST-FET, 13/02/201198 C program compiler assembly code assembler object code library routines executable linker machine code main text segment printf text segment Liên kết HUST-FET, 13/02/201199 Liên kết các đoạn mã máy độc lập với nhau  Chỉ cẩn biên dịch và assemble lại các đoạn mã có thay đổi: nhanh hơn 1. Quyết định mẫu cấp phát bộ nhớ cho đoạn mã và đoạn dữ liệu của từng mô đun.  Chú ý: Các mô đun được assemble độc lập, mỗi mô đun đều có đoạn mã bắt đầu tại 0x0040 0000 và dữ liệu tĩnh bắt đầu tại 0x1000 0000 2. Cấp phát lại địa chỉ tuyệt đối để phản ánh đúng địa chỉ bắt đầu của đoạn mã và đoạn dữ liệu 3. Sử dụng bảng biểu tượng để xác định các nhãn chưa được xác định  Các địa chỉ dữ liệu, rẽ nhánh nhảy tới các mô đun ngoài  Linker tạo ra tệp thực hiện được Liên kết HUST-FET, 13/02/2011100 printf: . . . main: . . . jal ???? call, printf Linker Object file C library Relocation info main: . . . jal printf printf: . . . Executable file Liên kết 2 tệp mã lệnh HUST-FET, 13/02/2011101 H d r T x ts e g D s e g R e lo c S m tb l D b g File 1 H d r T x ts e g D s e g R e lo c S m tb l D b g File 2 + Executable H d r T x ts e g D s e g R e lo c Nạp chương trình HUST-FET, 13/02/2011102 C program compiler assembly code assembler object code library routines executable linker loader memory machine code Nạp chương trình HUST-FET, 13/02/2011103 Nạp (sao chép) mã thực hiện từ đĩa vào bộ nhớ tại địa chỉ bắt đầu được xác định bởi hệ điều hành Sao chép các tham số (nếu có) của hàm chính vào ngăn xếp Khởi tạo các thanh ghi và đặt con trỏ ngăn xếp vào vị trí trống (0x7fff fffc) Nhảy đến hàm khởi tạo (tại PC = 0x0040 0000). Hàm khởi tạo sẽ chép các tham số vào thanh ghi tham số và gọi hàm chính bằng lệnh jal main Phép toán và cách thực hiện Phép toán dịch Phép toán số học Cộng, trừ Nhân Chia Phép toán dấu phẩy động HUST-FET, 13/02/2011104Chương 2. Ngôn ngữ máy tính và các phép toán Dữ liệu máy tính: Vector bit  Lưu trữ trong thanh ghi hoặc từ nhớ   Truyền dẫn trên đường bus  Xử lý bằng phép toán  Phép toán dịch  Kiểm tra 1 bit, đặt 1 bit, xóa 1 bit  Sao chép các bit  Hiện tượng tràn HUST-FET, 13/02/2011105Chương 2. Ngôn ngữ máy tính và các phép toán Phép toán dịch HUST-FET, 13/02/2011106Chương 2. Ngôn ngữ máy tính và các phép toán  Dịch logic  Các chữ số trống được điền bằng 0  Sang phải1 bit: srl1(an-1,an-2,,a0) = (0,an-1,an-2,,a1)  Sang trái 1 bit: sll1(an-1,an-2,,a0) = (an-2,an-3,,a0,0)  Dùng để triển khai bộ nhân và chia không dấu  Dịch số học  Bít dấu (MSB) không được thay đổi  dịch phải sao chép bít dấu vào các chữ số trống  dịch trái không dịch bít dấu  Sang phải 1 bit: sra1(an-1,an-2,,a0) = (an-1,an-1,an-2,,a1)  Sang trái 1 bit: sla1(an-1,an-2,,a0) = (an-1,an-3,,a0,0)  Dùng để triển khai bộ nhân và chia có dấu  Kết quả sai và xảy ra hiện tượng tràn nếu: an-1 ≠ an-2 an-1 an-2 a00 a1 an-1 an-2 0 a1 a0 an-1 an-2 a0a1 an-1 an-2 0an-3 a0 Bộ dịch Dịch trái 0 hoặc 1 bít Có thể thiết kế bộ dịch cả trái và phải HUST-FET, 13/02/2011107Chương 2. Ngôn ngữ máy tính và các phép toán Bộ dịch Bộ dịch trái 1 bít, và dịch phải 2 bít HUST-FET, 13/02/2011108Chương 2. Ngôn ngữ máy tính và các phép toán Bộ cộng nửa, cộng 2 số 1 bit HUST-FET, 13/02/2011109 Tín hiệu vào: a, b Tín hiệu ra: s (sum), co (carry out) Câu hỏi: Xác định biểu thức Bool cho s, và co Half Adder (HA) a b s co a b s co 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 s b a co Bộ cộng đầy đủ, cộng 3 số 1 bit Tín hiệu vào: a, b, ci (carry in) Tín hiệu ra: s (sum), co (carry out) Câu hỏi: Xác định biểu thức Bool cho s, và co HUST-FET, 13/02/2011110 Full Adder (FA) a ci s cob a b ci s co 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 b ci s co a Phép cộng, trừ 2 số có dấu  2 số biểu diễn ở dạng mã bù 2.  Cộng từng bit từ bit LSB đến bit MSB; Nhớ sang cột kế tiếp  Kết quả sai và tràn xảy ra khi 2 bit nhớ cuối cùng khác nhau: co,3 ≠ ci,3  Cộng 2 số khác dấu luôn không xảy ra tràn  Phép trừ là phép cộng với số đảo (dùng mã bù 2) HUST-FET, 13/02/2011111Chương 2. Ngôn ngữ máy tính và các phép toán 0 1 1 1 5 0 1 0 1 3 0 0 1 1 -8 1 0 0 0 Tràn 1 0 0 0 -7 1 0 0 1 -2 1 1 1 0 7 0 1 1 1 Tràn 1 1 1 1 -3 1 1 0 1 -5 1 0 1 1 -8 1 0 0 0 Không tràn 0 0 0 0 5 0 1 0 1 2 0 0 1 0 7 0 1 1 1 Không tràn Bộ cộng 2 số n bít dạng bù 2 Bộ cộng nối tiếp gồm n bộ cộng đủ n cổng logic xor để tính số đảo khi trừ Cổng logic xor để phát hiện tràn HUST-FET, 13/02/2011112Chương 2. Ngôn ngữ máy tính và các phép toán FA FA FAFA ... ... an-1 bn-1 a2 b2 a1 b1 a0 b0 add/ subtract cn-1 cn-2 c2 c1 c0 C-1 s2 s1 s0sn-1 overflow b ci s co a Tốc độ bộ cộng  Bộ cộng nối tiếp  Tín hiệu nhớ lan truyền (ripples) qua tất cả các bộ cộng "ripple carry adder"  Độ trễ tăng tuyến tính với số lượng bộ cộng (số bit của mỗi toán hạng)  Bít nhớ: tar(cn) = tar(cn-1) + 2 = 3 + 2*(n-1)  Bít tổng: tar(sn) = tar(cn) + 1 = 4 + 2*(n-1) Tăng tốc bằng bộ cộng tính bit nhớ trước (Carry lookahead Adder) HUST-FET, 13/02/2011113Chương 2. Ngôn ngữ máy tính và các phép toán Bộ cộng CLA HUST-FET, 13/02/2011114Chương 2. Ngôn ngữ máy tính và các phép toán  Với Ripple-Carry Adder, bit nhớ được tính dựa trên các bít nhớ trước đó tốc độ chậm  Tăng tốc độ, tính bit nhớ ở mỗi cột trực tiếp từ tín hiệu đầu vào  Bit nhớ đầu ra của cột i được tính từ tín hiệu tạo nhớ và tín hiệu lan truyền nhớ ci = gi+ci-1 pi si = ai  bi  ci-1 ci = aibi + aici-1 + bici-1 = aibi + ci-1(ai + bi) = aibi + ci-1(ai  bi) Tín hiệu tạo nhớ: gi= aibi Tạo ra ci khi ai = bi = 1 Lan truyền nhớ: pi= (ai  bi) Truyền nhớ từ đầu vào đến đầu ra khi ai  bi = 1 Bộ cộng CLA  Tính toán bit nhớ  Mỗi công thức nhớ trên có thể được triển bởi một mạch logic 2 mức  Để tính toán pi, gi ta cần mạch logic 1 mức từ đầu vào  Vậy cần tối đa 3 mức từ đầu vào để tính được tín hiệu nhớ Tăng tốc độ Cần cổng AND n+2 đầu vào cho cn! HUST-FET, 13/02/2011115Chương 2. Ngôn ngữ máy tính và các phép toán c0 = g0 + p0c-1 c1 = g1 + p1c0 = g1 + p1g0+ p1p0c-1 c2 = g2 + p2c1 = g2 + p2g1+ p2p1g0 + p2p1p0c-1 c3 = g3 + p3c2 = g3 + p3g2+ p3p2 g1 + p3p2p1g0 + p3p2p1p0 c-1 Bộ cộng CLA HUST-FET, 13/02/2011116Chương 2. Ngôn ngữ máy tính và các phép toán pi bi ci-1 si ai gi p0 g0 c-1 c0 p1 g1 g0 c1 p0 p1 c-1 c2 p2 g2 g1 p1 p2 g0 p0 p1 c-1 p2 c3 p3 g3 g2 p2p3 g1 p1 p2 g0 p3 p0 p1 c-1 p2 p3 Gồm 2 tầng Tầng 1: Tính toán tổng, tính hiệu tạo nhớ và truyền nhớ (1 mức logic) - PFA Tầng 2: Tính toán bit nhớ (2 mức logic) - CLA Phép nhân không dấu  Nhân lần lượt các cột của số bị nhân và số nhân được tích cục bộ  Các tích cục bộ được cộng với nhau theo cột  Ví dụ HUST-FET, 13/02/2011117Chương 2. Ngôn ngữ máy tính và các phép toán a3 a2 a1 a0 * b3 b2 b1 b0 a3b0 a2b0 a1b0 a0b0 + a3b1 a2b1 a1b1 a0b1 + a3b2 a2b2 a1b2 a0b2 + a3b3 a2b3 a1b3 a0b3 s7 s6 s5 s4 s3 s2 s1 s0 a b a*b 0 0 0 0 1 0 1 0 0 1 1 1 1 0 1 1 * 0 0 1 1 11*3 1 0 1 1 + 1 0 1 1 + 0 0 0 0 + 0 0 0 0 0 0 1 0 0 0 0 1 33 Bộ nhân không dấu song song  Sử dụng logic tổ hợp HUST-FET, 13/02/2011118Chương 2. Ngôn ngữ máy tính và các phép toán FA a b cico s b0a0 b1a1 b0a2b0a3 b1a2 b2a0b2a1 b3a0 FA a b cico s FA a b cico s FA a b cico s FA a b cico s FA a b cico s b1a0 b0a1 b1a3 b2a2 b3a1 FA a b cico s FA a b cico s FA a b cico s b2a3 b3a2 FA a b cico s FA a b cico s b3a3 FA a b cico s p7 p6 p5 p4 p3 p2 p1 p0 Phép nhân có dấu Mở rộng bít dấu cho các tích cục bộ  Với tích cục bộ của bit dấu số b3, cần lấy số đối (số bù 2) HUST-FET, 13/02/2011119Chương 2. Ngôn ngữ máy tính và các phép toán a3 a2 a1 a0 * b3 b2 b1 b0 a3b0 a3b0 a3b0 a3b0 a3b0 a2b0 a1b0 a0b0 + a3b1 a3b1 a3b1 a3b1 a2b1 a1b1 a0b1 + a3b2 a3b2 a3b2 a2b2 a1b2 a0b2 + a3b3 a3b3 a2b3 a1b3 a0b3 + 1 p7 p6 p5 p4 p3 p2 p1 p0 Ví dụ 2.9 – Phép nhân có dấu HUST-FET, 13/02/2011120Chương 2. Ngôn ngữ máy tính và các phép toán 1 0 1 1 * 0 0 1 1 -5*3 1 1 1 1 1 0 1 1 + 1 1 1 1 0 1 1 + 0 0 0 0 0 0 + 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 0 0 1 -15 Phép nhân có dấu  Đơn giản hóa HUST-FET, 13/02/2011121Chương 2. Ngôn ngữ máy tính và các phép toán a3 a2 a1 a0 * b3 b2 b1 b0 a3b0 a3b0 a3b0 a3b0 a3b0 a2b0 a1b0 a0b0 + a3b1 a3b1 a3b1 a3b1 a2b1 a1b1 a0b1 + a3b2 a3b2 a3b2 a2b2 a1b2 a0b2 + a3b3 a3b3 a2b3 a1b3 a0b3 + 1 p7 p6 p5 p4 p3 p2 p1 p0 a3 a2 a1 a0 * b3 b2 b1 b0 a2b0 a1b0 a0b0 + a2b1 a1b1 a0b1 + a2b2 a1b2 a0b2 + a2b3 a1b3 a0b3 + 1 - a3b0 - a3b1 - a3b2 - a3b3 p7 p6 p5 p4 p3 p2 p1 p0 Phép nhân có dấu  Đơn giản hóa HUST-FET, 13/02/2011122Chương 2. Ngôn ngữ máy tính và các phép toán a3 a2 a1 a0 * b3 b2 b1 b0 a2b0 a1b0 a0b0 + a2b1 a1b1 a0b1 + a2b2 a1b2 a0b2 + a2b3 a1b3 a0b3 + 1 - a3b0 - a3b1 - a3b2 - a3b3 p7 p6 p5 p4 p3 p2 p1 p0 a3 a2 a1 a0 * b3 b2 b1 b0 a2b0 a1b0 a0b0 + a2b1 a1b1 a0b1 + a2b2 a1b2 a0b2 + a2b3 a1b3 a0b3 + 1 - 0 a3b3 a3b2 a3b1 a3b0 p7 p6 p5 p4 p3 p2 p1 p0 Phép nhân có dấu  Đơn giản hóa HUST-FET, 13/02/2011123Chương 2. Ngôn ngữ máy tính và các phép toán a3 a2 a1 a0 * b3 b2 b1 b0 a2b0 a1b0 a0b0 + a2b1 a1b1 a0b1 + a2b2 a1b2 a0b2 + a2b3 a1b3 a0b3 + 1 - 0 a3b3 a3b2 a3b1 a3b0 p7 p6 p5 p4 p3 p2 p1 p0a3 a2 a1 a0 * b3 b2 b1 b0 a2b0 a1b0 a0b0 + a2b1 a1b1 a0b1 + a2b2 a1b2 a0b2 + a2b3 a1b3 a0b3 + 1 + 1 a3b3 a3b2 a3b1 a3b0 1 p7 p6 p5 p4 p3 p2 p1 p0 Phép nhân có dấu  Đơn giản hóa HUST-FET, 13/02/2011124Chương 2. Ngôn ngữ máy tính và các phép toán a3 a2 a1 a0 * b3 b2 b1 b0 a2b0 a1b0 a0b0 + a2b1 a1b1 a0b1 + a2b2 a1b2 a0b2 + a2b3 a1b3 a0b3 + 1 + 1 a3b3 a3b2 a3b1 a3b0 1 p7 p6 p5 p4 p3 p2 p1 P0 a3 a2 a1 a0 * b3 b2 b1 b0 a3b0 a2b0 a1b0 a0b0 + a3b1 a2b1 a1b1 a0b1 + a3b2 a2b2 a1b2 a0b2 + a3b3 a2b3 a1b3 a0b3 + 1 1 p7 p6 p5 p4 p3 p2 p1 p0 Bộ nhân có dấu HUST-FET, 13/02/2011125Chương 2. Ngôn ngữ máy tính và các phép toán Bộ nhân nối tiếp  Sử dụng bộ cộng để cộng các tích cục bộ  Thực hiện phép nhân trong vài chu kỳ đồng hồ  Lưu số bị nhân, số nhân và kết quả tạm thời trong các thanh ghi  Với mỗi bit bi của số nhân B (từ phải qua trái)  Nhân bi với số bị nhân A và cộng tích với kết quả tổng tạm thời Y  Nếu bi = 1 thì cộng A vào Y  Dịch A sang trái 1 bit HUST-FET, 13/02/2011126Chương 2. Ngôn ngữ máy tính và các phép toán Bộ nhân nối tiếp HUST-FET, 13/02/2011127Chương 2. Ngôn ngữ máy tính và các phép toán Dịch trái A[2n-1:0] 2n-bit ALU Dịch phải B[n-1:0] Y[2n-1:0] control Start A[n-1:0] ← SBN B[n-1:0] ← SN Y[2n-1:0] ← 0 Count ← n B0 = 1 Y←Y+A Dịch phải B Dịch trái A Count ← Count - 1 Count = 0 Stop Y N Y N Triển khai gồm: 2 thanh ghi 2n bit 1 thanh ghi n bit 1 bộ cộng 2n bit 1 khối điều khiển Ví dụ 2.10 - Bộ nhân nối tiếp HUST-FET, 13/02/2011128Chương 2. Ngôn ngữ máy tính và các phép toán Nhận xét:  Một nửa số bit của A luôn bằng 0  Khi A dịch trái, bit 0 được thêm vào bên phải  các bit LSB của tích không bị ảnh hưởng Ý tưởng: Giữ A ở phía trái của tích và dịch tích sang phải 1 Start A[n-1:0] ← SBN B[n-1:0] ← SN Y[2n-1:0] ← 0 Count ← n B0 = 1 Y←Y+A Dịch phải B Dịch trái A Count ← Count - 1 Count = 0 Stop Y N Y N 0 1 10 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 0 1 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 Counter=4 Counter=3 Counter=2 Counter=1 Counter=0 Y A B B B B B Y A Y A Y A Y A Dịch trái A[2n-1:0] 2n-bit ALU Dịch phải B[n-1:0] Y[2n-1:0] control Bộ nhân nối tiếp – Dùng n-bit ALU HUST-FET, 13/02/2011129 A[n-1:0] n-bit ALU B[n-1:0] C,Y[2n-1:0] control Start A[n-1:0] ← SBN B[n-1:0] ← SN C,Y[2n-1:0] ← 0 Count ← n B0 = 1 C,Y[2n-1:n]← Y[2n-1:n]+A Dịch phải B Dịch phải C,Y Count ← Count - 1 Count = 0 Stop Y N Y N Triển khai gồm: 2 thanh ghi n bit 1 thanh ghi 2n+1 bit 1 bộ cộng n bit 1 khối điều khiển Ví dụ 2.11 – Bộ nhân nối tiếp HUST-FET, 13/02/2011130 Nhận xét: Trong quá trình nhân chỉ một số bit của Y có ý nghĩa với kết quả Counter=4 Counter=3 Counter=2 Counter=1 Counter=0 1 1 0 1A 1 1 0 1A 1 1 0 1A 0 0 1 0B 0 0 0 1B 0 1 0 1B 1 0 1 1B 0 0 0 0B Y 0 0 1 1 1 0 0 01 Y 1 0 0 1 1 1 0 00 1 1 0 1A 0 0 0 0 0 0 0 0Y 0 1 1 0 1 0 0 0 0Y 0 0 1 1 0 1 0 0 0Y 0 1 0 0 1 1 1 0 00Y 0 1 0 0 1 1 1 00Y 0 0 0 1 1 1 1 01Y 1 0 0 0 1 1 1 10Y A[n-1:0] n-bit ALU B[n-1:0] C,Y[2n-1:0] control Start A[n-1:0] ← SBN B[n-1:0] ← SN C,Y[2n-1:0] ← 0 Count ← n B0 = 1 C,Y[2n-1:n]← Y[2n-1:n]+A Dịch phải B Dịch phải C,Y Count ← Count - 1 Count = 0 Stop Y N Y N Bộ nhân nối tiếp HUST-FET, 13/02/2011131 Start A[n-1:0] ← SBN C,Y[n-1:0],B[n-1:0] ← 0,SN Count ← n B0 = 1 C,Y[n-1:0]← Y[n-1:0]+A Dịch phải C,Y,B Count ← Count - 1 Count = 0 Stop Y N Y N an-1 a0 Bộ tổng n bit yn-1 y0 bn-1 b0 Logic điều khiển cộng và dịch phải cn Số bị nhân A Số nhân B Triển khai gồm: 1 thanh ghi n bit 1 thanh ghi 2n+1 bit 1 bộ cộng n bit 1 khối điều khiển Ví dụ 2.12 – Bộ nhân nối tiếp HUST-FET, 13/02/2011132 Counter=4 Counter=3 Counter=2 Counter=1 Counter=0 1 1 0 1A 1 1 0 1A 1 1 0 1A 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 Y 0 0 1 11 Y 1 0 0 10 1 1 0 1A 0 0 0 0Y 0 1 1 0 1Y 0 0 1 1 0Y 0 1 0 0 10Y 0 1 0 00Y 0 0 0 11Y 1 0 0 00Y Start A[n-1:0] ← SBN C,Y[n-1:0],B[n-1:0] ← 0,SN Count ← n B0 = 1 C,Y[n-1:0]← Y[n-1:0]+A Dịch phải C,Y,B Count ← Count - 1 Count = 0 Stop Y N Y N an-1 a0 Bộ tổng n bit yn-1 y0 bn-1 b0 Logic điều khiển cộng và dịch phải cn Số bị nhân A Số nhân B 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 Nhân Booth Nhân với một chuỗi số 1 A * 1111 = A * (24 – 20) = A * 24 – A  Dịch A sang trái 4 bit và trừ đi A Số bị nhân B chứa chuỗi số 1 từ bit vị trí v đến bit vị trí u (bn-1, bn-2, bu+1,bu,,bv,bv-1,..,b0) = (bn-1, bn-2, 0,1,,1,0,..,b0) Chuỗi bit có thể thay thế bằng 2u+1 – 2v Các phép nhân và cộng cho các bít bu đến bv có thể được thay bằng phép dịch trái và phép trừ Ví dụ: B = 001110 (1410), u = 3, v = 2  A x B = A* 2 4 – A*21 HUST-FET, 13/02/2011133 Ví dụ 2.13 – Bộ nhân Booth HUST-FET, 13/02/2011134 0 +1 0 0 -1 0 0 1 0 1 0 1A 0 0 1 1 1 0B B 1 1 0 1 0 1 1 01111 0 0 1 0 1 0 1 00000 0 1 0 1 0 0 0 01000 0 0 1 0 0 1 1 01000 Thực hiện 1. Bắt đầu chuỗi số 1 (chuyển từ 0 sang 1, hai bit liên tiếp là 01): trừ đi số bị nhân 2. Trong chuỗi số 0, hoặc chuỗi số 1 (2 bit liên tiếp là 00 hoặc 11): dịch trái số bị nhân 3. Kết thúc chuỗi số 1 (chuyển từ 1 sang 0, hai bit liên tiếp là 10): cộng với số bị nhân Thuật toán nhân Booth HUST-FET, 13/02/2011135 Start A[n-1:0] ← SBN B[n-1:0] ← SN C,Y[n-1:0],B-1 ← 0 Count ← n B0B-1 C,Y[n-1:0] ←Y[n-1:0]+A Dịch phải C,Y,B,B-1 Count ← Count - 1 Count = 0 Stop Y N 01 N C,Y[n-1:0] ←Y[n-1:0]-A 10 00,11 an-1 a0 Bộ tổng n bit yn-1 y0 bn-1 b0 Logic điều khiển cộng, trừ và dịch phải cn Số bị nhân A Số nhân B b-1 Ví dụ 2.14 – Minh họa thuật toán Booth HUST-FET, 13/02/2011136 Start A[n-1:0] ← SBN B[n-1:0] ← SN C,Y[n-1:0],B-1 ← 0 Count ← n B0B-1 C,Y[n-1:0] ←Y[n-1:0]+A Dịch phải C,Y,B,B-1 Count ← Count - 1 Count = 0 Stop Y N 01 N C,Y[n-1:0] ←Y[n-1:0]-A 10 00,11 an-1 a0 Bộ tổng n bit yn-1 y0 bn-1 b0 Logic điều khiển cộng, trừ và dịch phải cn Số bị nhân A Số nhân B b-1 Counter=6 Counter=5 Counter=1 1 00A 1 10 0 11-A 0 11 0 0 0 0Y 000 1 1 1 00 00 0 1 1 10 0 0 0Y 0 0 000 0 0 1 1 11 0 1 1Y 0 0 011 0 Counter=40 0 1 10 1 0 1Y 1 0 111 1 Counter=30 0 0 11 0 1 0Y 1 1 111 1 Counter=21 0 0 01 1 0 1Y 1 1 111 0 1 00+A 1 10 1 0 0 00 0 1 0Y 1 1 100 0 1 1 0 00 0 10Y 1 0 000 0 Counter=00 1 1 01 0 00Y 0 0 000 1 Nhân Booth: Nhân có dấu HUST-FET, 13/02/2011137 Vì a, b là 2 số có dấu dạng bù 2: a = -2n-1*an + 2 n-2*an-2 + ... + 2*a1 + a0 Xét 2 bit liên tiếp (ai , ai-1 ), hiệu của chúng và hoạt động nhân: Giá trị được tính toán bởi bộ nhân Booth: (0 - a0) * b + (a0 - a1) * b * 2 + (a1 – a2) * b * 2 2 ... + (an-3 – an-2) * b * 2 n-2 + (an-2 – an-1) * b * 2 n-1 Triển khai các số hạng và tối giản: b * (-2n-1*an + 2 n-2*an-2 + ... + 2*a1 + a0)= b * a. which is exactly the product of a and b. ai ai-1 ai –ai-1 action 1 0 -1 Trừ b, và dịch 0 1 1 Cộng b và dịch 0 0 0 Bỏ qua 1 1 1 Bỏ qua Phép chia HUST-FET, 13/02/2011138 Phép nhân Cộng với số bị nhân và dịch trái số bị nhân Tối ưu phần cứng: cộng với số bị nhân và dịch phải tích Phép chia Trừ cho số chia và dịch phải số chia Ví dụ: Y = A / B Tối ưu phần cứng: trừ cho số chia và dịch trái phần dư Y 0 B 1 1 1 1 1A 00 B 0 1 1 0Y 0 B 0 0 11 0 0 1A 00 0 1Y 0 B 0 0 1 10 0 1Y 00 Thuật toán chia nối tiếp HUST-FET, 13/02/2011139 Start B[n:0] ← SC C, Y[n-1:0],A[n-1:0] ← 0,SBC Count ← n C = 1 A0←0 Phục hồi Y = Y+B Count ← Count - 1 Count = 0 Stop Y N Y N Dịch trái C,Y,A C,Y[n-1:0]← C,Y[n-1:0]-B A0←1  Trừ Y = Y – B và kiểm tra bit dấu C của kết quả  Nếu C = 1 (phép trừ kết quả âm)   Bít kết quả a0=0  Phục hồi số bị chia: Y = Y + B  Nếu C = 0 (phép trừ kết quả dương)   Bít kết quả a0=1 bn-1 b0 Bộ trừ n+1 bit C y0 an-1 a0 Logic điều khiển trừ và dịch trái Số chia B Số bị chia A 0 yn-1 Ví dụ 2.15 – Bộ chia nối tiếp HUST-FET, 13/02/2011140 Counter=4 Counter=3 Counter=2 Counter=1 0 0 1 1B 1 1 1 0 1 0 0 0 1 1 1 0 0 1 1 1 Y 1 1 1 01 0 0 0 0Y 0 0 0 0 0Y 0 1 1 0 1Y 1 0 0 0 10Y 0 0 1 10Y 0 0 0 00Y 0 0 0 00Y 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 1 1 1 1 00 0 0 0Y 0 1 1 0 1-B 1 1 1 0 00 0 0 1Y 0 1 1 0 1-B 1 1 1 0 00 0 0 1Y 0 1 1 0 1-B 1 1 1 0 1-B 1 1 1 1 01Y 0 0 1 0 0 0 0 10Y 0 0 1 0 Counter=0 Start B[n:0] ← SC C, Y[n-1:0],A[n-1:0] ← 0,SBC Count ← n C = 1 A0←0 Phục hồi Y = Y+B Count ← Count - 1 Count = 0 Stop Y N Y N Dịch trái C,Y,A C,Y[n-1:0]← C,Y[n-1:0]-B A0←1 bn-1 b0 Bộ trừ n+1 bit C y0 an-1 a0 Logic điều khiển trừ và dịch trái Số chia B Số bị chia A 0 yn-1 Chia có dấu 1. Chia phần giá trị tuyệt đối 2. Xác định dấu của kết quả  Dấu của thương:  Dương nếu số chia và số bị chia cùng dấu  Âm nếu số chia và số bị chia khác dấu  Dấu của phần dư: luôn cùng dấu với số bị chia 3. Đảo kết quả nếu cần thiết HUST-FET, 13/02/2011141 Phép toán dấu phẩy động HUST-FET, 13/02/2011142  Phép cộng trừ: giả sử EA > EB  Số dấu phẩy động:  Phép nhân  Phép chia  Chuẩn hóa kết quả: Đưa định trị về dạng chuẩn hóa và điều chỉnh số mũ tương ứng BA E B E A MBMA 2;2    AEBA MMBA 2'     BA EEBA MMBA  2//     BA EEBA MMBA  2 BA EE BB MM  2'trong đó