›
›

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

pdf 142 trang hapham 4410
Download
Bạn đang xem 20 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_kien_truc_may_tinh_chuong_2_ngon_ngu_may_tinh_va_c.pdf

Nội dung text: 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

  1. KIẾN TRÚC MÁY TÍNH ET4270 TS. Nguyễn Đức Minh [Adapted from Computer Organization and Design, 4th Edition, Patterson & Hennessy, © 2008, MK] [Adapted from Computer Architecture lecture slides, Mary Jane Irwin, © 2008, PennState University]
  2. Tổ chức lớp Số tín chỉ 3 (3-1-1-6) Giảng viên TS. Nguyễn Đức Minh Văn phòng C9-401 Email minhnd1@gmail,com Website • Username: ca.fet.hut@gmail.com • Pass: dungkhoiminh Sách Computer Org and Design, 3rd Ed., Patterson &Hennessy, ©2007 Digital Design and Computer Architecture, David Money Harris Thí nghiệm 3 bài Bài tập Theo chương, đề bài xem trên trang web Giới thiệu 2 HUST-FET, 13/02/2011
  3. Điểm số Điều kiện thi Lab Bài thi giữa kỳ 30% Bài tập 20% (Tối đa 100 điểm) Tiến trình 10% Tối đa: 100 điểm, Bắt đầu: 50 điểm Tích lũy, trừ qua trả lời câu hỏi trên lớp và đóng góp tổ chức lớp Bài thi cuối kỳ 70% Giới thiệu 3 HUST-FET, 13/02/2011
  4. Lịch học  Thời gian:  Từ 14h00 đến 17h20  Lý thuyết: 11 buổi x 135 phút / 1 buổi  Bài tập: 4 buổi x 135 phút / 1 buổi  Thay đổi lịch (nghỉ, học bù) sẽ được thông báo trên website trước 2 ngày Giới thiệu 4 HUST-FET, 13/02/2011
  5. Kết luận chương 1  Hệ thống máy tính được xây dựng từ phân cấp các lớp trừu tượng. Các chi tiết triển khai lớp dưới bị che khuất khỏi lớp trên.  Kiến trúc tập lệnh – lớp giao tiếp giữa phần cứng và phần mềm mức thấp – là lớp trừu tượng quan trọng trong hệ thống máy tính.  Phần cứng máy tính gồm 5 thành phần: đường dữ liệu, khối điều khiển, bộ nhớ, khối vào, và khối ra. 5 thành phần đó kết nối với nhau bằng hệ thống bus theo mô hình vonNeumann hoặc mô hình Havard.  Phương pháp đánh giá hiệu năng một hệ thống máy tính là dùng thời gian thực hiện 1 chương trình. Thời gian thực hiện chương trình được tính bằng công thức: Tcpu I CPI Tc Chương 2. Ngôn ngữ máy tính và các phép toán 5 HUST-FET, 13/02/2011
  6. Nội dung 1. Hệ đếm và biểu diễn số trong máy tính (nhắc lại) 2. Kiến trúc tập lệnh 1. Yêu cầu chức năng máy tính vonNeumman 2. Yêu cầu chung của kiến trúc tập lệnh 3. Kiến trúc tập lệnh MIPS 4. Biên dịch 3. Các phép toán và cách thực hiện trong máy tính Chương 2. Ngôn ngữ máy tính và các phép toán 6 HUST-FET, 13/02/2011
  7. Hệ đếm cơ số r Một số biểu diễn trong hệ đếm cơ số r gồm m chữ số trước dấu phẩy và n chữ số sau dấu phẩy: D (dm 1dm 2 d1d0 ,d 1d 2 d n )r Trong đó 0 ≤ di ≤ r-1 là các chữ số dm-1: chữ số có ý nghĩa lớn nhất d-n: chữ số có ý nghĩa nhỏ nhất Giá trị của D trong hệ cơ số 10: m 1 i D di r i n Chương 2. Ngôn ngữ máy tính và các phép toán 7 HUST-FET, 13/02/2011
  8. Các hệ đếm thông dụng Hệ cơ số 10: r = 10; 0 ≤ di ≤ 9 Hệ cơ số 2: r = 2; di (0,1); di được gọi là các bit Hệ cơ số 8: r = 8; 0 ≤ di ≤ 7 Hệ cơ số 16: r = 16; di (0, ,9,A,B,C,D,E,F) Máy tính dùng hệ cơ số 2, và 16 Chương 2. Ngôn ngữ máy tính và các phép toán 8 HUST-FET, 13/02/2011
  9. Chuyển từ thập phân sang nhị phân  Bước 1 - Phần nguyên: Chia số cần đổi cho 2 lấy phần dư; Lấy thương chia tiếp cho 2 lấy phần dư; Lặp lại cho đến khi thương bằng 0; Phần dư cuối cùng là bit có giá trị lớn nhất (MSB), phần dư đầu tiên là bit có giá trị nhỏ nhất (trước dấu phẩy)  Bước 2 - Phần thập phân: Nhân số cần đổi với 2, lấy phần nguyên của tích; Lấy phần thập phân của tích nhân tiếp với 2, lấy phần nguyên; Lặp lại đến khi tích bằng 0 hoặc tích bị lặp lại; Phần nguyên đầu tiên là bit đầu tiên, phần nguyên cuối cùng là bít cuối cùng (sau dấu phẩy). Chương 2. Ngôn ngữ máy tính và các phép toán 9 HUST-FET, 13/02/2011
  10. Chuyển từ nhị phân sang hệ 16  Nhóm số thập phân thành các nhóm 4 bít, lần lượt từ phải sang trái.  Nhóm cuối cùng có thể có số bit nhỏ hơn 4 (b ,b ,b ,b ,b ,b ,b ,b ,b ,b ,b ,b ) m 1 m 2m 3m 4 7 65 4 3 21 0 hm / 4 1 h1 h0  Chuyển mỗi nhóm 4 bít thành 1 chữ số hệ 16 Hệ 2 Hệ 16 Hệ 2 Hệ 16 Hệ 2 Hệ 16 Hệ 2 Hệ 16 0001 1 0101 5 1001 9 1101 D 0010 2 0110 6 1010 A 1110 E 0011 3 0111 7 1011 B 1111 F 0100 4 1000 8 1100 C Chương 2. Ngôn ngữ máy tính và các phép toán 10 HUST-FET, 13/02/2011
  11. Ví dụ 2.1 – Chuyển đổi hệ đếm  Chuyển đổi các số sau giữa các cơ số 10, 2 và 16  (241,625)10  (1101 0101,1001)2  (4A,3F)16 Chương 2. Ngôn ngữ máy tính và các phép toán 11 HUST-FET, 13/02/2011
  12. Biểu diễn số nguyên không dấu Hex Binary Decimal 231 230 229 . . . 23 22 21 20 trọng số 0x00000000 0 0000 0 31 30 29 . . . 3 2 1 0 vị trí 0x00000001 0 0001 1 0x00000002 0 0010 2 1 1 1 . . . 1 1 1 1 bit 0x00000003 0 0011 3 0x00000004 0 0100 4 0x00000005 0 0101 5 1 0 0 0 . . . 0 0 0 0 - 1 0x00000006 0 0110 6 0x00000007 0 0111 7 0x00000008 0 1000 8 232 - 1 0x00000009 0 1001 9 • Các số dương không 0xFFFFFFFC 1 1100 232 - 4 cần bít dấu 0xFFFFFFFD 1 1101 232 - 3 • Khoảng biểu diễn: [0, 2m-1] 0xFFFFFFFE 1 1110 232 - 2 0xFFFFFFFF 1 1111 232 - 1 Chương 2. Ngôn ngữ máy tính và các phép toán 12 HUST-FET, 13/02/2011
  13. Biểu diễn số nguyên bằng 1 bít dấu và độ lớn m 2 bm 1 i (bm 1,bm 2, ,b1,b0 ) ( 1) bi 2 i 0  Trong đó:  Bít MSB bm-1 là bít dấu; bm-1 = 0 biểu diễn số dương, bm-1 = 1 biểu diễn số âm  Các bít còn lại biểu diễn 1 số nhị phân không dấu  Có 2 biểu diễn số 0: 10 0 (-0) và 00 0(+0)  Khoảng biểu diễn [-(2m-1-1), 2m-1-1] Chương 2. Ngôn ngữ máy tính và các phép toán 13 HUST-FET, 13/02/2011
  14. Biểu diễn số nguyên bằng mã bù 2 m 2 m 1 i (bm 1,bm 2, ,b1,b0 )bù 2,m bit bm 1 2 bi 2  Trong đó: i 0  Bít MSB bm-1 là bít dấu; bm-1 = 0 biểu diễn số dương, bm-1 = 1 biểu diễn số âm  Các bít còn lại biểu diễn giá trị của số ở dạng mã bù 2  Có 1 biểu diễn số 0: 00 0  Khoảng biểu diễn [-2m-1, 2m-1-1]  Quy tắc tìm biểu diễn bù 2, m bít :  Đổi số dương sang mã nhị phân, thêm các bít 0 để đủ m bít. (Bít lớn nhất là bít dấu = 0)  Tìm mã bù 1 bằng cách đảo các bít  Mã bù 2 = mã bù 1 + 1 Chương 2. Ngôn ngữ máy tính và các phép toán 14 HUST-FET, 13/02/2011
  15. Biểu diễn số nguyên bằng mã bù 2 =-23  Quy tắc tìm biểu diễn bù 2, 4 bít : 1000 -8 1001 -7 =-(23 - 1) 1010 -6 1011 -5 1100 -4 1101 -3 1110 -2 1111 -1 0000 0 0001 1 0010 2 0011 3 0100 4 0101 5 0110 6 0111 7 =23 - 1 Chương 2. Ngôn ngữ máy tính và các phép toán 15 HUST-FET, 13/02/2011
  16. Biểu diễn số nguyên mã lệch (bias) m 1 i (bm 1,bm 2, ,b1,b0 )2,bias bi 2 bias i 0 Trong đó: bias là độ lệch và thường bằng 2m-1 Không có bit dấu Khoảng biểu diễn: [-2m-1, 2m-1-1] Chương 2. Ngôn ngữ máy tính và các phép toán 16 HUST-FET, 13/02/2011
  17. Ví dụ 2.2 – Biểu diễn số nguyên  Chuyển các số sau sang dạng mã bù 1, mã bù 2 và mã 2 lệch 127 độ dài 8 bít  123  -8  -3  -126  129  -129 Chương 2. Ngôn ngữ máy tính và các phép toán 17 HUST-FET, 13/02/2011
  18. Biểu diễn số thực chuẩn IEEE-754  Độ chính xác đơn dùng 32 bit nhị phân 31 30 23 22 0 S Mũ exp: số nguyên lệch 127 Độ lớn chuẩn hóa M s e e e f f f  Bao gồm: 7 6 0 22 21 0  1 bít dấu s: 0 số dương; 1 số âm  8 bít biểu diễn số mũ theo mã lệch 127: 7 i exp (e7e6 e0 )2,bias127 2 ei 127  23 bít biểu diễn phần độ lớn được chuẩni 0 hóa 1 ≤ M < 2 M = (1,f22f21 f0)2 s exp RIEEE 754 ( 1) 2 M Chương 2. Ngôn ngữ máy tính và các phép toán 18 HUST-FET, 13/02/2011
  19. Biểu diễn số thực chuẩn IEEE-754  Biểu diễn các số đặc biệt Số mũ lệch 127 Độ lớn Số được biểu diễn 0 0 0 1 to 254 Bất kỳ Số chuẩn hóa 255 0  ∞ 255 Số khác 0 NaN 0 Số khác 0 Số không chuẩn hóa Chương 2. Ngôn ngữ máy tính và các phép toán 19 HUST-FET, 13/02/2011
  20. Biểu diễn số thực chuẩn IEEE-754  Khoảng biểu diễn Độ chính xác đơn Độ chính xác kép Machine epsilon 2-23 or 1.192 x 10-7 2-52 or 2.220 x 10-16 Độ chính xác Smallest positive Số dương nhỏ 2-126 or 1.175 x 10-38 2-1022 or 2.225 x 10-308 nhất Largest positive (2- 2-23) 2127 or 3.403 x (2- 2-52) 21023 or 1.798 x Số dưong lớn 1038 10308 nhất Decimal Precision 6 significant digits 15 significant digits Độ chính xác 6 chữ số sau dấu phảy 15 chữ số sau dấu phảy thập phân Chương 2. Ngôn ngữ máy tính và các phép toán 20 HUST-FET, 13/02/2011
  21. Ví dụ 2.3 – Biểu diễn số thực dạng IEEE-754  Đổi các số sau thành biểu diễn số thực dấu phẩy động độ chính xác đơn  125,50  -56,25  Đổi các biểu diễn số thực dấu phẩy động độ chính xác đơn sau thành số thực ở hệ 10  1 1101 1001 11000 0 (tổng cộng 32 bít)  0 1001 1101 10100 0 (tổng cộng 32 bít) Chương 2. Ngôn ngữ máy tính và các phép toán 21 HUST-FET, 13/02/2011
  22. Biểu diễn ký tự, chữ số  Mã ASCII: 7 bit hoặc 8 bít  Mã Unicode: 16 bít  Mã BCD b3b2b1b0 000 001 010 011 100 101 110 111 Decimal BCD 0000 NUL DLE SP 0 @ P ‘ p 0001 SOH DC1 ! 1 A Q a q digit 0010 STX DC2 “ 2 B R b r 0 0000 0011 ETX DC3 # 3 C S c s 0100 EOT DC4 $ 4 D T d t 1 0001 0101 ENQ NAK % 5 E U e u 2 0010 0110 ACK SYN & 6 F V f V 3 0011 0111 BEL ETB ‘ 7 G W g w 1000 BS CAN ( 8 H X h x 4 0100 1001 HT EM ) 9 I Y i y 5 0101 1010 LF SUB * : J Z j z 6 0110 1011 VT ESC + ; K [ k { 1100 FF FS , N ^ n ~ 9 1001 1111 SI US / ? O _ o DEL Chương 2. Ngôn ngữ máy tính và các phép toán 22 HUST-FET, 13/02/2011
  23. Máy tính vonNeumann: Hoạt động cơ bản  Nạp chỉ thị từ bộ nhớ chương trình Instruction  Xác định hành động và kích thước chỉ Fetch thị Instruction  Định vị và nạp dữ liệu toán hạng Decode  Tính giá trị kết quả hoặc trạng thái Operand Fetch  Lưu dữ liệu vào bộ nhớ để sử dụng sau Execute  Xác định lệnh tiếp theo Result Store Next Instruction Chương 2. Ngôn ngữ máy tính và các phép toán 23 HUST-FET, 13/02/2011
  24. Máy tính vonNeumann: Yêu cầu chức năng  Yêu cầu nguyên tắc:  Máy tính hoạt động theo các chỉ thị máy Memory  Chỉ thị được biểu diễn bằng các số không phân biệt với dữ liệu Accounting prg (machine code)  Chương trình được lưu trữ trong bộ nhớ C compiler  Khái niệm về chương trình được lưu trữ (eng. (machine code) stored-program): Payroll  Chương trình được cung cấp như là 1 tệp các số data nhị phân. Source code in  Máy tính có thể chạy các chương trình đã tạo sẵn C for Acct prg nếu chúng tương thích với 1 kiến trúc tập lệnh  Số lượng ít các kiến trúc tập lệnh chuẩn Xác định yêu cầu chức năng: Kiến trúc tập lệnh Chương 2. Ngôn ngữ máy tính và các phép toán 24 HUST-FET, 13/02/2011
  25. Kiến trúc tập lệnh: Đánh giá Thông số khi thiết kế: Có thể triển khai được không? Mất bao lâu? Giá thành? Có thể lập trình được không? Có dễ biên dịch?  Thông số tĩnh: Độ lớn chương trình trong bộ nhớ?  Thông số động: Số lượng chỉ thị được thực hiện? Số lượng byte cần nạp để chạy chương trình? Số chu kỳ đồng hồ cần cho mỗi chỉ thị? Tốc độ đồng hồ? CPI Thông số tốt nhất: Thời gian thực hiện! Inst. Count Cycle Time Chương 2. Ngôn ngữ máy tính và các phép toán 25 HUST-FET, 13/02/2011
  26. Kiến trúc tập lệnh: Yêu cầu  Kích thước và kiểu dữ liệu  Phép toán: loại nào được hỗ trợ  Định dạng và mã hóa chỉ thị:  Chỉ thị được giải mã thế nào?  Vị trí toán hạng và kết quả  Số lượng toán hạng?  Giá trị toán hạng được lưu ở đâu?  Kết quả được lưu ở vị trí nào?  Các toán hạng bộ nhớ được định vị thế nào?  Chỉ thị tiếp theo: nhẩy, điều kiện, rẽ nhánh Chương 2. Ngôn ngữ máy tính và các phép toán 26 HUST-FET, 13/02/2011
  27. Dữ liệu: Kiểu & kích thước Byte =Byte 8 bits Sử dụng để lưu dữ liệu dấu HalfwordHalfword = 2 bytes phẩy động Word = Word 4 bytes DoublewordDoubleword = 8 bytes Quadword (16 bytes) ít được sử dụng Chương 2. Ngôn ngữ máy tính và các phép toán 27 HUST-FET, 13/02/2011
  28. Kiến trúc tập lệnh: Yêu cầu  Kích thước và kiểu dữ liệu  Phép toán: loại nào được hỗ trợ  Định dạng và mã hóa chỉ thị:  Chỉ thị được giải mã thế nào?  Vị trí toán hạng và kết quả  Số lượng toán hạng?  Giá trị toán hạng được lưu ở đâu?  Kết quả được lưu ở vị trí nào?  Các toán hạng bộ nhớ được định vị thế nào?  Chỉ thị tiếp theo: nhẩy, điều kiện, rẽ nhánh Chương 2. Ngôn ngữ máy tính và các phép toán 28 HUST-FET, 13/02/2011
  29. Các phép toán  Load/Store: Đọc và ghi bộ nhớ  Computational: Tính toán số học và logic, so sánh  Có lệnh nhân chia hay không?  Các lệnh so sánh nào?  Jump and Branch: Nhẩy và rẽ nhánh  Floating Point: Lệnh dấu phẩy động  coprocessor  Memory Management: Quản lý bộ nhớ  Special: Lệnh đặc biệt Chương 2. Ngôn ngữ máy tính và các phép toán 29 HUST-FET, 13/02/2011
  30. Các phép toán Dịch chuyển dữ liệu Đọc (từ bộ nhớ), Ghi (tới bộ nhớ) Chuyển giữa các ô nhớ Chuyển giữa các thanh ghi Vào (từ thiết bị I/O), Ra (tới thiết bị I/O) push, pop (từ/tới ngăn xếp) Số học Số nguyên (nhị phân, thập phân), Số thực dấu phẩy động. Cộng, trừ, nhân chi Dịch Dịch trái/phải, Quay trái/phải Logic not, and, or, set, clear Điều khiển (nhảy, rẽ nhánh) Không điều kiện, Có điều kiện Liên kết với thủ tục call, return Ngắt trap, return Đồng bộ test & set Chuỗi search, translate Đồ họa (MMX) Phép toán song song Chương 2. Ngôn ngữ máy tính và các phép toán 30 HUST-FET, 13/02/2011
  31. Các phép toán Các phép toán đơn giản được sử dụng nhiều và chiếm đa số trong các chỉ thị của chương trình Cần tập trung vào các phép toán: load, store move register-register add, subtract, and, shift compare equal, compare not equal branch, jump, call, return Chương 2. Ngôn ngữ máy tính và các phép toán 31 HUST-FET, 13/02/2011
  32. Kiến trúc tập lệnh: Yêu cầu  Kích thước và kiểu dữ liệu  Phép toán: loại nào được hỗ trợ  Định dạng và mã hóa chỉ thị:  Chỉ thị được giải mã thế nào?  Vị trí toán hạng và kết quả  Số lượng toán hạng?  Giá trị toán hạng được lưu ở đâu?  Kết quả được lưu ở vị trí nào?  Các toán hạng bộ nhớ được định vị thế nào?  Chỉ thị tiếp theo: nhẩy, điều kiện, rẽ nhánh Chương 2. Ngôn ngữ máy tính và các phép toán 32 HUST-FET, 13/02/2011
  33. Định dạng lệnh: các trường  Mã lệnh chỉ ra nhiệm vụ (chức năng) của lệnh  Tham chiếu toán hạng nguồn chỉ ra các toán hạng được xử lý bởi lệnh  Tham chiếu kết quả chỉ ra nơi lưu trữ kết quả của lệnh  Tham chiếu lệnh kế tiếp chỉ ra cách tính toán hoặc nơi lưu trữ lệnh sẽ được thực hiện tiếp theo  Thường không được chỉ ra rõ ràng trong lệnh mà được ngầm coi là lệnh liền sau lệnh hiện tại trong chuỗi lệnh  Trong một số loại lệnh, địa chỉ của lệnh tiếp theo sẽ được chỉ ra Chương 2. Ngôn ngữ máy tính và các phép toán 33 HUST-FET, 13/02/2011
  34. Kiến trúc tập lệnh: Yêu cầu  Kích thước và kiểu dữ liệu  Phép toán: loại nào được hỗ trợ  Định dạng và mã hóa chỉ thị:  Chỉ thị được giải mã thế nào?  Vị trí toán hạng và kết quả  Số lượng toán hạng?  Giá trị toán hạng được lưu ở đâu?  Kết quả được lưu ở vị trí nào?  Các toán hạng bộ nhớ được định vị thế nào?  Chỉ thị tiếp theo: nhẩy, điều kiện, rẽ nhánh Chương 2. Ngôn ngữ máy tính và các phép toán 34 HUST-FET, 13/02/2011
  35. Số lượng toán hạng (1)  3 toán hạng:  Địa chỉ của 2 toán hạng, và kết quả đều được chứa trong mã lệnh  OP A, B, C  A ← B OP C  Dễ biên dịch từ ngôn ngữ bậc cao sang lệnh máy  Giá trị toán hạng lưu trong các thanh ghi  Lệnh chỉ ra chỉ số thanh ghi  2 toán hạng: (giá trị trong các thanh ghi, hoặc địa chỉ ô nhớ)  Một địa chỉ được dùng cho toán hạng và kết quả  OP A, B  A ← A OP B  Biên dịch đòi hỏi thêm lệnh và thanh ghi để lưu trữ tạm thời  Giá trị toán hạng lưu trong thanh ghi hoặc trong ô nhớ.  Lệnh chỉ ra chỉ số thanh ghi hoặc địa chỉ ô nhớ Chương 2. Ngôn ngữ máy tính và các phép toán 35 HUST-FET, 13/02/2011
  36. Số lượng toán hạng (2)  Một toán hạng: lệnh tích lũy (accumulator)  Một toán hạng và kết quả được quy định ngầm được lưu trong 1 thanh ghi đặc biệt (Accumulator – AC)  Toán hạng còn lại lưu trong thanh ghi  OP A  AC ← AC OP A  Thông dụng trong bộ xử lý tín hiệu số  Không toán hạng: lệnh ngăn xếp (stack)  Tất cả các địa chỉ được quy định ngầm  Kết quả và toán hạng thứ hai nằm ở địa chỉ đỉnh của stack: T  Toán hạng thứ nhất nằm ở địa chỉ thứ 2 của stack: T-1  OP  T ← T-1 OP T  Số lượng toán hạng quyết định: độ dài lệnh, I và CPI Chương 2. Ngôn ngữ máy tính và các phép toán 36 HUST-FET, 13/02/2011
  37. Ví dụ 2.4: So sánh số lượng toán hạng Xét câu lệnh ở ngôn ngữ bậc cao: Y = (A – B)/(C+D*E) Biên dịch thành hợp ngữ: 3 địa chỉ 1 địa chỉ 0 địa chỉ SUB Y, A, B LOAD D Chuyển sang dạng toán tử sau: MUL T, D, E MUL E Y = AB-CDE*+/ ADD T, T, C ADD C DIV Y, Y, T STORE Y PUSH A LOAD A PUSH B SUB B SUB DIV Y PUSH C 2 địa chỉ STORE Y PUSH D MOV Y, A PUSH E SUB Y, B MUL MOV T, D ADD MUL T, E DIV ADD T, C POP Y DIV Y, T Chương 2. Ngôn ngữ máy tính và các phép toán 37 HUST-FET, 13/02/2011
  38. Kiến trúc tập lệnh: Yêu cầu  Kích thước và kiểu dữ liệu  Phép toán: loại nào được hỗ trợ  Định dạng và mã hóa chỉ thị:  Chỉ thị được giải mã thế nào?  Vị trí toán hạng và kết quả  Số lượng toán hạng?  Giá trị toán hạng được lưu ở đâu?  Kết quả được lưu ở vị trí nào?  Các toán hạng bộ nhớ được định vị thế nào?  Chỉ thị tiếp theo: nhẩy, điều kiện, rẽ nhánh Chương 2. Ngôn ngữ máy tính và các phép toán 38 HUST-FET, 13/02/2011
  39. Giá trị toán hạng – Chế độ địa chỉ Register Add R4,R3 R4R4+R3 Immediate Add R4,#3 R4 R4+3 Displacement Add R4,100(R1) R4 R4+Mem[100+R1] Register indirect Add R4,(R1) R4 R4+Mem[R1] Indexed / Base Add R3,(R1+R2) R3 R3+Mem[R1+R2] Direct or absolute Add R1,(1001) R1 R1+Mem[1001] Memory indirect Add R1,@(R3) R1 R1+Mem[Mem[R3]] Auto-increment Add R1,(R2)+ R1 R1+Mem[R2]; R2 R2+d Auto-decrement Add R1,–(R2) R2 R2–d; R1 R1+Mem[R2] Scaled Add R1,100(R2)[R3] R1  R1+Mem[100+R2+R3*d] Chương 2. Ngôn ngữ máy tính và các phép toán 39 HUST-FET, 13/02/2011
  40. Chế độ địa chỉ tức thì (Immediate)  Giá trị của toán hạng (toán hạng) là trường toán hạng của câu lệnh Instruction Opcode Operand  Operand = Operand field  Không tham chiếu đến bộ nhớ để nạp dữ liệu  Toán hạng luôn là hằng số trong khi chạy chương trình  Tốc độ cao  Khoảng giá trị của toán hạng nhỏ  Ví dụ: ADD R4, #3: R4 R4+3 Chương 2. Ngôn ngữ máy tính và các phép toán 40 HUST-FET, 13/02/2011
  41. Chế độ địa chỉ thanh ghi (Register)  Toán hạng được chứa trong thanh ghi chỉ ra bởi trường địa chỉ Instruction Opcode Register index: n Register file Operand  Operand = R[n] (Rn)  Không truy cập bộ nhớ  Thực thi nhanh  Trường địa chỉ dùng ít bit  Lệnh ngắn hơn  Nạp lệnh nhanh hơn  Số lượng thanh ghi bị hạn chế Chương 2. Ngôn ngữ máy tính và các phép toán 41 HUST-FET, 13/02/2011
  42. Chế độ địa chỉ dịch chuyển (Displacement) Instruction Opcode Register index: n Offset: A Memory Register file Operand Pointer to operand  Trường địa chỉ chứa gồm 2 phần cơ sở và độ lệch  A chứa giá trị được sử dụng trưc tiếp  n chứa chỉ số của thanh ghi để sử dụng gián tiếp  A, Rn có thể là cơ sở và độ lệch hoặc ngược lại  Địa chỉ của toán hạng EA = R[n] + A  Operand = MEM[EA] Chương 2. Ngôn ngữ máy tính và các phép toán 42 HUST-FET, 13/02/2011
  43. Chế độ địa chỉ tương đổi (Relative) Instruction Opcode Address A Memory Register file Operand PC  Phiên bản của địa chỉ dịch chuyển  R = PC, được ngầm định trong mã lệnh (opcode)  operand = MEM[A + PC]  Lấy toán hạng từ địa chỉ cách vị trí chương trình hiện tại A ô nhớ  Dùng để truy cập các hằng số, biến, địa chỉ địa phương Chương 2. Ngôn ngữ máy tính và các phép toán 43 HUST-FET, 13/02/2011
  44. Địa chỉ bộ nhớ  Địa chỉ bộ nhớ:  Địa chỉ byte: đánh địa chỉ cho các ô nhớ kích thước 1 byte  Địa chỉ word: đánh địa chỉ cho các ô nhớ kích thước 1 word  2 câu hỏi khi thiết kế ISA:  Các kiểu dữ liệu lớn hơn byte được lưu trữ thế nào?  Địa chỉ khác byte được tính toán thế nào?  Các kiểu dữ liệu lớn có được lưu trữ ở vị trí địa chỉ byte bất kỳ hay không? (Vấn đề alighment) 31 23 15 7 0 word x+4 x+3 x+2 x+1 x byte address Chương 2. Ngôn ngữ máy tính và các phép toán 44 HUST-FET, 13/02/2011
  45. Địa chỉ bộ nhớ: Endianess và Alignment  Big Endian:  Địa chỉ word = địa chỉ của byte có ý nghĩa lớn nhất trong word (Most Significant Byte)  IBM 360/370, Motorola 68k, MIPS, Sparc, HP PA  Litle Endian:  Địa chỉ word = địa chỉ của byte có ý nghĩa nhỏ nhất trong word (Least Significant Byte)  Intel 80x86, DEC Vax, DEC Alpha  Alignment:  Dữ liệu được lưu trữ ở địa chỉ byte chia hết cho kích thước. Chương 2. Ngôn ngữ máy tính và các phép toán 45 HUST-FET, 13/02/2011
  46. Địa chỉ bộ nhớ: Endianess và Alignment  Big Endian:  Địa chỉ word = địa chỉ của byte có ý nghĩa lớn nhất trong word (Most Significant Byte)  IBM 360/370, Motorola 68k, MIPS, Sparc, HP PA  Litle Endian:  Địa chỉ word = địa chỉ của byte có ý nghĩa nhỏ nhất trong word (Least Significant Byte)  Intel 80x86, DEC Vax, DEC Alpha  Alignment:  Dữ liệu được lưu trữ ở địa chỉ byte chia hết cho kích thước. Chương 2. Ngôn ngữ máy tính và các phép toán 46 HUST-FET, 13/02/2011
  47. Địa chỉ bộ nhớ: Endianess và Alignment  Big Endian:  Địa chỉ word = địa chỉ của byte có ý nghĩa lớn nhất trong word (Most Significant Byte)  IBM 360/370, Motorola 68k, MIPS, Sparc, HP PA  Litle Endian:  Địa chỉ word = địa chỉ của byte có ý nghĩa nhỏ nhất trong word (Least Significant Byte)  Intel 80x86, DEC Vax, DEC Alpha 0 1 2 3  Alignment: Aligned  Dữ liệu được lưu trữ ở địa chỉ byte chia hết cho kích thước. Not Aligned Chương 2. Ngôn ngữ máy tính và các phép toán 47 HUST-FET, 13/02/2011
  48. Sử dụng chế độ địa chỉ  Displacement: 42% avg, 32% to 55%  Immediate: 33% avg, 17% to 43% 75% 88%  Register deferred (indirect): 13% avg, 3% to 24%  Scaled: 7% avg, 0% to 16%  Memory indirect: 3% avg, 1% to 6%  Misc: 2% avg, 0% to 3%  75% displacement & immediate  88% displacement, immediate & register indirect Chương 2. Ngôn ngữ máy tính và các phép toán 48 HUST-FET, 13/02/2011
  49. Thống kê chế độ địa chỉ Kích thước trường toán hạng trực tiếp 8 bit: 50-60% 16 bit; 75%-80% Các chế độ địa chỉ quan trọng Dịch chuyển (Displacement) Trực tiếp (Immediate) Thanh ghi gián tiếp (Register indirect) Kích thước độ lệch trong chế độ địa chỉ: 12-16 bít Kích thước toán hạng trực tiếp: 8-16 bít Chương 2. Ngôn ngữ máy tính và các phép toán 49 HUST-FET, 13/02/2011
  50. Định dạng chỉ thị  Độ dài chỉ thị:  Cố định  Thay đổi  Lai: gồm 1 vài loại chỉ thị có độ dài cố định khác nhau  Khi kích thước chương trình quan trọng: dùng chỉ độ dài thay đổi  Khi hiệu năng quan trọng: dùng độ dài cố định Variable: Fixed: Hybrid: Chương 2. Ngôn ngữ máy tính và các phép toán 50 HUST-FET, 13/02/2011
  51. Một số kiến trúc tập lệnh Chương 2. Ngôn ngữ máy tính và các phép toán 51 HUST-FET, 13/02/2011
  52. Kiến trúc RISC  Reduce Instruction Set Computer  DEC Alpha, AMD 29k, ARC, ARM, Atmel AVR, MIPS, PA-RISC, Power (PowerPC), SuperH, và SPARC.  Định dạng lệnh và độ dài lệnh cố định, đơn giản  Dễ giải mã lệnh  Các thanh ghi chung mục đích có thể sử dụng trong nhiều ngữ cảnh  Dễ thiết kế phần mềm biên dịch  Có thể cần các thanh ghi dấu phẩy động riêng biệt  Chế độ địa chỉ đơn giản  Các chế độ địa chỉ phức tạp được thực hiện thông qua chuỗi lệnh số học và lệnh nạp/ghi  Ít hỗ trợ các loại dữ liệu phức tạp Chương 2. Ngôn ngữ máy tính và các phép toán 52 HUST-FET, 13/02/2011
  53. Kiến trúc CISC  Complex Instruction Set Computer  System/360, z/Architecture, PDP-11, VAX, Motorola 68k, và x86.  Lệnh có độ dài thay đổi, phức tạp  Có thể bao gồm 1 vài phép toán nhỏ  Gần ngôn ngữ lập trình bậc cao  Nhiều chế độ địa chỉ phức tạp  Hỗ trợ các loại dữ liệu phức tạp Chương 2. Ngôn ngữ máy tính và các phép toán 53 HUST-FET, 13/02/2011
  54. CISC vs. RISC RISC CISC - Tập lớn các thanh ghi - Giới hạn số thanh ghi - Tập lệnh đơn giản - Tập lệnh phức tạp - Tập trung trao đổi dữ liệu giữa thanh ghi - Nhấn mạnh vào các hoạt động truy cập - Các lệnh thực hiện trong một chu kỳ máy bộ nhớ - Các lệnh LOAD/STORE đơn giản để truy - Lệnh có thể được thực hiện trong nhiều cập bộ nhớ chu kỳ máy - Giới hạn chế độ địa chỉ - Một lệnh có thể tương đương với nhiều - Từ mã có chiều dài cố định lệnh của RISC - Nhiều chế độ địa chỉ - Mã lệnh có chiều dài thay đổi tùy vào từng lệnh Chương 2. Ngôn ngữ máy tính và các phép toán 54 HUST-FET, 13/02/2011
  55. CISC vs. RISC RISC CISC - Mã lệnh thực hiện nhanh - Ngôn ngữ lập trình assembly mạnh - Đơn vị điều khiển đơn giản - Giảm các yêu cầu khi thiết kế trình dịch - Giải mã nhanh - Các tính năng với dấu phẩy động mạnh - Xử lý song song đường ống hiệu suất cao - Tăng khả năng của cache - Thiết kế, phát triển và kiểm tra nhanh - Hỗ trợ trình dịch tăng cường sự tối ưu - Giảm các lỗi rẽ nhánh của đường ống - Tăng tốc truyền tham số cho các thủ tục Chương 2. Ngôn ngữ máy tính và các phép toán 55 HUST-FET, 13/02/2011
  56. Ví dụ 2.4. So sánh hiệu năng RISV vs. CISC Kiến trúc tập lệnh ISA có 2 lớp chỉ thỉ phức tạp (C) và đơn giản (S). Trong 1 chương trình thời gian thực hiện chỉ thị S chiếm 95%. Để triển khai ISA bằng kiến trúc RISC ta sẽ triển khai các chỉ thị S bằng phần cứng và chỉ thị C bằng phần mềm (dùng đoạn chỉ thị S và coi như 1 chỉ thị giả C). So sánh với kiến trúc CISC, các chỉ thị S sẽ được thực hiện nhanh hơn 20% và các chỉ thị CISC bị chậm đi 3 lần. Kiến trúc nào có hiệu năng cao hơn và cao hơn bao nhiêu lần? Chương 2. Ngôn ngữ máy tính và các phép toán 56 HUST-FET, 13/02/2011
  57. Kiến trúc tập lệnh MIPS Định dạng chỉ thị: 32 bit 3 loại định dạng: R-chỉ thị thanh ghi: 2 toán hạng nguồn thanh ghi, 1 toán hạng đích thanh ghi I-chỉ thị trực tiếp: 1 toán hạng nguồn thanh ghi, 1 toán hạng nguồn trực tiếp, 1 toán hạng đích thanh ghi J-chỉ thị nhảy: 1 toán hạng nguồn trực tiếp op rs rt rd sa funct R format op rs rt immediate I format op jump target J format Chương 2. Ngôn ngữ máy tính và các phép toán 57 HUST-FET, 13/02/2011
  58. Nguyên tắc thiết kế MIPS (RISC)  Tính đơn giản quan trọng hơn tính quy tắc(Simplicity favors regularity)  Chỉ thị kích thước cố định (32 bit)  Ít định dạng chỉ thị (3 loại định dạng)  Mã lệnh ở vị trí cố định (6 bit đầu)  Nhỏ hơn thì nhanh hơn  Số chỉ thị giới hạn  Số thanh ghi giới hạn  Số chế độ địa chỉ giới hạn  Tăng tốc các trường hợp thông dụng  Các toán hạng số học lấy từ thanh ghi (máy tính dựa trên cơ chế load- store)  Các chỉ thị có thể chứa toán hạng trực tiếp  Thiết kế tốt đòi hỏi sự thỏa hiệp  3 loại định dạng chỉ thị Chương 2. Ngôn ngữ máy tính và các phép toán 58 HUST-FET, 13/02/2011
  59. Chỉ thị số học của MIPS  Mã hợp ngữ của chỉ thị số học add $t0, $s1, $s2 sub $t0, $s1, $s2  Mỗi chỉ thị số học thực hiện một phép toán  Mỗi chỉ thị chứa chính xác ba chỉ số của các thanh ghi trong tệp thanh ghi của đường dữ liệu ($t0,$s1,$s2) destination  source1 op source2  Định dạng chỉ thị loại thanh ghi (R format) 0 17 18 8 0 0x22 59 HUST-FET, 13/02/2011
  60. Các trường trong chỉ thị MIPS Các trường trong 1 chỉ thị MIPS được đặt tên: op rs rt rd shamt funct op 6-bits mã lệnh xác định phép toán (opcode) rs 5-bits chỉ số thanh ghi chứa toán hạng nguồn 1 trong tệp thanh ghi rt 5-bits chỉ số thanh ghi chứa toán hạng nguồn 2 trong tệp thanh ghi rd 5-bits chỉ số thanh ghi sẽ lưu kết quả trong tệp thanh ghi shamt 5-bits số lượng dịch (cho chỉ thị dịch) funct 6-bits mã chức năng thêm cho phần mã lệnh Chương 2. Ngôn ngữ máy tính và các phép toán 60 HUST-FET, 13/02/2011
  61. Tệp thanh ghi của MIPS Register File  Gồm 32 thanh ghi 32-bit 32 bits src1 data 5  2 cổng đọc src1 addr 32  1 cổng ghi 5 src2 addr 32 src2  Thanh ghi: 5 locations dst addr data 32  Nhanh hơn bộ nhớ chính 32 write data - Nhiều thanh ghi sẽ chậm hơn (VD., 1 tệp gồm 64 thanh ghi word sẽ write control chậm hơn tệp gổm 32 thanh ghi khoảng 50%) - Số lượng cổng đọc ghi ảnh hưởng bậc 2 đến tốc độ  Dễ biên dịch - VD., (A*B) – (C*D) – (E*F) có thể thực hiện phép nhân theo thứ tự bất kỳ, không giống như ngăn xếp  Chứa biến chương trình - cải thiện độ lớn mã chương trình Chương 2. Ngôn ngữ máy tính và các phép toán 61 HUST-FET, 13/02/2011
  62. Các thanh ghi MIPS Tên Chỉ số Công dụng Preserve on call? $zero 0 constant 0 (hardware) n.a. $at 1 reserved for assembler n.a. $v0 - $v1 2-3 returned values no $a0 - $a3 4-7 arguments yes $t0 - $t7 8-15 temporaries no $s0 - $s7 16-23 saved values yes $t8 - $t9 24-25 temporaries no $gp 28 global pointer yes $sp 29 stack pointer yes $fp 30 frame pointer yes $ra 31 return addr (hardware) yes Chương 2. Ngôn ngữ máy tính và các phép toán 62 HUST-FET, 13/02/2011
  63. Truy cập bộ nhớ  2 chỉ thị dịch chuyển dữ liệu để truy cập bộ nhớ o lw $t0, 4($s3) #đọc 1 từ từ bộ nhớ o sw $t0, 8($s3) #ghi 1 từ vào bộ nhớ  Dữ liệu được đọc vào (lw) hoặc ghi ra từ (sw) 1 thanh ghi trong tệp thanh ghi – 5 bit chỉ số thanh ghi  32 bit địa chỉ bộ nhớ được tạo ra bằng cách cộng giá trị thanh ghi cơ sở (base register) với giá trị offset  Trường offset rộng 16 bit sẽ giới hạn các ô nhớ trong khoảng 213 hay 8,192 words ( 215 hay 32,768 bytes) tính từ giá trị của thanh ghi cơ sở Chương 2. Ngôn ngữ máy tính và các phép toán 63 HUST-FET, 13/02/2011
  64. Định dạng lệnh truy cập bộ nhớ  Định dạng chỉ thị Load/Store (Định dạng I): lw $t0, 24($s3) 35 19 8 2410 Memory 2410 + $s3 = 0xf f f f f f f f . . . 0001 1000 $t0 0x120040ac + . . . 1001 0100 $s3 0x12004094 . . . 1010 1100 = 0x120040ac 0x0000000c 0x00000008 0x00000004 0x00000000 data word address (hex) Chương 2. Ngôn ngữ máy tính và các phép toán 64 HUST-FET, 13/02/2011
  65. Ví dụ 2.5. Truy cập bảng (array)  Cho A[ ] = là 1 mảng bắt đầu tại địa chỉ cơ sở lưu trong thanh ghi $s3;  Biến h được gắn với thanh ghi $s2;  Dịch: A[5] = h + A[8]  Thành mã hợp ngữ MIPS: 8 7 6 lw $t0, 32 ($s3) # $t0  A[8] 5 4 add $t0, $s2, $t0 # $t0  h+$t0 3 2 sw $t0, 20 ($s3) # A[5]  $t0 1 I-type OP rs rt immediate 65 HUST-FET, 13/02/2011
  66. Ví dụ 2.6. Truy cập mảng với chỉ số thay đổi  A[ ] = array with base address in $s3;  variables g, h, i associated with registers $s1, $s2, $s4  Compile: g = h + A[i]  into MIPS instructions: add $t1, $s4, $s4 # $t1  i+i = 2i add $t1, $t1, $t1 # $t1  2i+2i = 4i add $t1, $t1, $s3 # $t1  address of A[i] lw $t0, 0 ($t1) # $t0  A[i] add $s1, $s2, $t0 # $s1  h + A[i] 66 HUST-FET, 13/02/2011
  67. Lưu trữ byte: Endianess (Nhắc lại)  Big Endian: leftmost byte is word address  Little Endian: rightmost byte is word address Địa chỉ:little endian byte 0 3 2 1 0 Thanh ghi msb lsb 0 1 2 3 Địa chỉ:big endian byte 0 67 HUST-FET, 13/02/2011
  68. Đọc và ghi byte  MIPS các lệnh đặc biệt để dịch chuyển bytes lb $t0, 1($s3) #load byte from memory sb $t0, 6($s3) #store byte to memory op rs rt 16 bit number  Các byte 8bit nào được đọc và ghi?  Lệnh đọc đưa byte được đọc vào 8 bit ngoài cùng bên phải từ bộ nhớ vào thanh ghi đích - Các bit khác của thanh ghi?  Lệnh ghi lấy 8 bit ngoài cùng bên phải của thanh ghi nguồn và ghi vào bộ nhớ - Giữ các byte khác trong từ nhớ không thay đổi 68 HUST-FET, 13/02/2011
  69. Ví dụ 2.7. Đọc ghi byte  Cho đoạn mã sau và trạng thái bộ nhớ. Xác định trạng thái bộ nhớ sau khi thực hiện đoạn mã add $s3, $zero, $zero lb $t0, 1($s3) sb $t0, 6($s3)  Giá trị lưu trong $t0? Memory 0x 0 0 0 0 0 0 0 0 24  Từ nào được ghi vào bộ nhớ ở vị trí 0x 0 0 0 0 0 0 0 0 20 nào? 0x 0 0 0 0 0 0 0 0 16 0x 1 0 0 0 0 0 1 0 12  Điều gì xảy ra khi máy tính là loại little 0x 0 1 0 0 0 4 0 2 8 Endian? 0x F F F F F F F F 4 0x 0 0 9 0 1 2 A 0 0 Data Word Address (Decimal) 69 HUST-FET, 13/02/2011
  70. Đọc ghi nửa từ  MIPS also provides special instructions to move half words lh $t0, 1($s3) #load half word from memory sh $t0, 6($s3) #store half word to memory op rs rt 16 bit number  What 16 bits get loaded and stored?  load half word places the half word from memory in the rightmost 16 bits of the destination register - what happens to the other bits in the register?  store half word takes the half word from the rightmost 16 bits of the register and writes it to the half word in memory - leaving the other half word in the memory word unchanged 70 HUST-FET, 13/02/2011
  71. Lệnh trực tiếp  Các hằng số trong chương trình thường có giá trị nhỏ  Các phương pháp lưu trữ và sử dụng hằng số:  Lưu các hằng thường dùng trong bộ nhớ và đọc chúng  Tạo 1 thanh ghi kết nối cứng (như $zero) để lưu hằng số  Dùng các lệnh đặc biệt có chứa hằng số addi $sp, $sp, 4 #$sp = $sp + 4 slti $t0, $s2, 15 #$t0 = 1 if $s2<15  Định dạng mã máy (Định dạng I): 0x0A 18 8 0x0F  Hằng số được chứa trong lệnh!  Định dạng trực tiếp giới hạn giá trị trong khoảng +215–1 to -215 Chương 2. Ngôn ngữ máy tính và các phép toán 71 HUST-FET, 13/02/2011
  72. Lệnh dịch  Shifts move all the bits in a word left or right sll $t2, $s0, 8 #$t2 = $s0 > 8 bits  Instruction Format (R format) 0 16 10 8 0x00  Such shifts are called logical because they fill with zeros  Notice that a 5-bit shamt field is enough to shift a 32-bit value 25 – 1 or 31 bit positions Chương 2. Ngôn ngữ máy tính và các phép toán 72 HUST-FET, 13/02/2011
  73. Lệnh logic  There are a number of bit-wise logical operations in the MIPS ISA and $t0, $t1, $t2 #$t0 = $t1 & $t2 or $t0, $t1, $t2 #$t0 = $t1 | $t2 nor $t0, $t1, $t2 #$t0 = not($t1 | $t2)  Instruction Format (R format) 0 9 10 8 0 0x24 andi $t0, $t1, 0xFF00 #$t0 = $t1 & ff00 ori $t0, $t1, 0xFF00 #$t0 = $t1 | ff00  Instruction Format (I format) 0x0D 9 8 0xFF00 Chương 2. Ngôn ngữ máy tính và các phép toán 73 HUST-FET, 13/02/2011
  74. Sử dụng các hằng số lớn  Đưa 1 hằng số 32 bit vào 1 thanh ghi  Sử dụng 2 lệnh:  Lệnh nạp vào phần cao "load upper immediate“ lui $t0, 0xaaaa 16 0 8 1010101010101010  Lệnh nạp vào phần thấp: ori $t0, $t0, 0xaaaa 1010101010101010 0000000000000000 0000000000000000 1010101010101010 1010101010101010 1010101010101010 74 HUST-FET, 13/02/2011
  75. Lệnh điều khiển dòng chương trình  Lệnh rẽ nhánh có điều kiện: bne $s0, $s1, Lbl #go to Lbl if $s0 $s1 beq $s0, $s1, Lbl #go to Lbl if $s0=$s1  Ex: if (i==j) h = i + j; bne $s0, $s1, Lbl1 add $s3, $s0, $s1 Lbl1:  Định dạng lệnh (Định dạng I): 0x05 16 17 16 bit offset  Địa chỉ đến được xác định như thế nào ? Chương 2. Ngôn ngữ máy tính và các phép toán 75 HUST-FET, 13/02/2011
  76. Xác định địa chỉ rẽ nhánh đến  Sử dụng 1 thanh ghi (giống như lw và sw) cộng với 16-bit offset  Thanh ghi địa chỉ lệnh PC (Instruction Address Register ) - Việc sử dụng PC được tự động bao hàm trong lệnh - PC được cập nhật (PC+4) khi lệnh được nạp vì vậy khi tính toán nó chứa giá trị địa chỉ của lệnh kế tiếp  giới hạn khoảng cách rẽ nhánh trong khoảng -215 đến +215-1 (word) lệnh kể từ lệnh sau lệnh rẽ nhánh. Tuy nhiên phần lớn các rẽ nhánh là địa phương. Trường 16 bit thấp của lệnh rẽ nhánh 16 offset sign-extend 00 branch dst 32 32 Add address PC 32 Add 32 32 32 4 32 ? 76 HUST-FET, 13/02/2011
  77. So sánh hỗ trợ lệnh rẽ nhánh  Có lệnh beq, bne, các loại điều kiện khác? (VD., rẽ nhánh nếu nhỏ hơn)? Cần 1 lệnh so sánh khác: slt  Set on less than: slt $t0, $s0, $s1 # if $s0 < $s1 then # $t0 = 1 else # $t0 = 0  Instruction format (R format): 0 16 17 8 0x24  Các phiên bản khác của slt slti $t0, $s0, 25 # if $s0 < 25 then $t0=1 sltu $t0, $s0, $s1 # if $s0 < $s1 then $t0=1 sltiu $t0, $s0, 25 # if $s0 < 25 then $t0=1 77 HUST-FET, 13/02/2011
  78. Sử dụng slt  Dùng slt, beq, bne, và giá trị 0 trong thanh ghi $zero để tạo ra các điều kiện rẽ nhánh khác  less than blt $s1, $s2, Label slt $at, $s1, $s2 #$at set to 1 if bne $at, $zero, Label #$s1 < $s2  less than or equal to ble $s1, $s2, Label  greater than bgt $s1, $s2, Label  great than or equal to bge $s1, $s2, Label  Các lệnh rẽ nhánh được thêm vào tập lệnh như các lệnh giả, được nhận dạng và mở rộng bằng trình dịch assembler  Trình dịch assembler cần thanh ghi riêng ($at) 78 HUST-FET, 13/02/2011
  79. Lệnh nhảy không điều kiện  Lệnh nhảy không điều kiện: j label #go to label  Định dạng lệnh (J Format): 0x02 26-bit address từ trường 26 bits thấp của lệnh nhảy 26 00 32 4 PC 32 79 HUST-FET, 13/02/2011
  80. Nhảy đến địa chỉ ở xa  Khi địa chỉ nhảy đến ở xa hơn, và không thể biểu diễn bằng 16 bits?  Phần mềm assembler hỗ trợ – nó chèn 1 lệnh nhảy không điều kiện đến địa chỉ nhảy đến và đảo điều kiện rẽ nhánh beq $s0, $s1, L1 trở thành bne $s0, $s1, L2 j L1 L2: 80 HUST-FET, 13/02/2011
  81. Nhảy đến địa chỉ thay đổi  Các ngôn ngữ bậc cao có các lệnh như case hay switch cho phép lựa chọn trong nhiều trường hợp phụ thuộc vào 1 biến  Lệnh: jr $t1 #go to address in $t1  Mã máy: op rs funct R format 0 9 0 0 0 8 = 0x08 81 HUST-FET, 13/02/2011
  82. Lệnh case (switch) ở ngôn ngữ bậc cao switch (k) { case 0: h=i+j; break; /*k=0*/ Memory case 1: h=i+h; break; /*k=1*/ case 2: h=i-j; break; /*k=2*/  Giả sử 3 từ liên tiếp trong bộ nhớ bắt đầu từ địa chỉ lưu L2 trong $t4 chứa giá trị của các nhãn L0, L1, và L2 và k L1 lưu trong $s2 $t4 L0 add $t1, $s2, $s2 #$t1 = 2*k add $t1, $t1, $t1 #$t1 = 4*k add $t1, $t1, $t4 #$t1 = addr of JumpT[k] lw $t0, 0($t1) #$t0 = JumpT[k] jr $t0 #jump based on $t0 L0: add $s3, $s0, $s1 #k=0 so h=i+j j Exit L1: add $s3, $s0, $s3 #k=1 so h=i+h j Exit L2: sub $s3, $s0, $s1 #k=2 so h=i-j Exit: . . .  Các từ lưu địa chỉ các nhãn như trên gọi là bảng địa chỉ nhảy (jump address table)  Bảng này chứa dữ liệu nhưng thường nằm chung với đoạn mã chương trình 82 HUST-FET, 13/02/2011
  83. Gọi hàm hoặc thủ tục 1. Hàm chính (hàm gọi, caller) đặt các tham số vào vị trị mà thủ tục (hàm bị gọi, callee) có thể truy cập  $a0 - $a3: 4 thanh ghi tham số 2. Hàm gọi chuyển quyền điều khiển cho hàm bị gọi 3. Hàm bị gọi được cấp chỗ lưu trữ cần thiết 4. Hàm bị gọi thực hiện công việc mong muốn 5. Hàm bị gọi đặt kết quả vào vị trí hàm gọi có thể truy cập  $v0 - $v1: 2 thanh ghi kết quả 6. Hàm bị gọi trả điều khiển cho hàm gọi  $ra: 1 thanh ghi địa chỉ trở về để quay về vị trí xuất phát 83 HUST-FET, 13/02/2011
  84. Lệnh để gọi 1 hàm  MIPS procedure call instruction: jal ProcAddress #jump and link  Lưu PC+4 vào thanh ghi $ra như là đường dẫn đến lệnh kế tiếp khi trở về từ hàm  Định dạng mã máy: op 26 bit address J format 3 ????  Hàm sẽ trở về hàm gọi bằng: jr $ra #return 84 HUST-FET, 13/02/2011
  85. Tổng kết MIPS  Các loại lệnh Registers  Load/Store  Computational R0 - R31  Jump and Branch  Floating Point - coprocessor PC  Memory Management HI LO  Special  3 định dạng lệnh: độ rộng 32 bit 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits OP rs rt rd shamt funct R format OP rs rt 16 bit number I format OP 26 bit jump target J format 85 HUST-FET, 13/02/2011
  86. Tổng kết các lệnh MIPS Category Instr OpC Example Meaning Arithmetic add 0 & 20 add $s1, $s2, $s3 $s1 = $s2 + $s3 (R & I subtract 0 & 22 sub $s1, $s2, $s3 $s1 = $s2 - $s3 format) add immediate 8 addi $s1, $s2, 4 $s1 = $s2 + 4 shift left logical 0 & 00 sll $s1, $s2, 4 $s1 = $s2 > 4 (fill with logical zeros) shift right 0 & 03 sra $s1, $s2, 4 $s1 = $s2 >> 4 (fill with arithmetic sign bit) and 0 & 24 and $s1, $s2, $s3 $s1 = $s2 & $s3 or 0 & 25 or $s1, $s2, $s3 $s1 = $s2 | $s3 nor 0 & 27 nor $s1, $s2, $s3 $s1 = not ($s2 | $s3) and immediate c and $s1, $s2, ff00 $s1 = $s2 & 0xff00 or immediate d or $s1, $s2, ff00 $s1 = $s2 | 0xff00 load upper f lui $s1, 0xffff $s1 = 0xffff0000 immediate 86 HUST-FET, 13/02/2011
  87. Tổng kết các lệnh MIPS Category Instr OpC Example Meaning Data load word 23 lw $s1, 100($s2) $s1 = Memory($s2+100) transfer store word 2b sw $s1, 100($s2) Memory($s2+100) = $s1 (I format) load byte 20 lb $s1, 101($s2) $s1 = Memory($s2+101) store byte 28 sb $s1, 101($s2) Memory($s2+101) = $s1 load half 21 lh $s1, 101($s2) $s1 = Memory($s2+102) store half 29 sh $s1, 101($s2) Memory($s2+102) = $s1 Cond. br on equal 4 beq $s1, $s2, L if ($s1==$s2) go to L branch br on not equal 5 bne $s1, $s2, L if ($s1 !=$s2) go to L (I & R set on less a slti $s1, $s2, if ($s2<100) $s1=1; format) than immediate 100 else $s1=0 set on less 0 & 2a slt $s1, $s2, $s3 if ($s2<$s3) $s1=1; than else $s1=0 Uncond. jump 2 j 2500 go to 10000 jump jump register 0 & 08 jr $t1 go to $t1 jump and link 3 jal 2500 go to 10000; $ra=PC+4 87 HUST-FET, 13/02/2011
  88. Tổ chức máy tính MIPS Processor Memory Register File 1 1100 src1 addr src1 5 32 data src2 addr 32 5 registers dst addr ($zero - $ra) read/write 5 src2 write data data addr 30 32 32 2 32 32 bits words br offset read data 32 Add PC 32 32 Add 32 32 32 4 Fetch 32 write data 0 1100 PC = PC+4 32 0 1000 4 5 6 7 0 0100 32 ALU 0 1 2 3 Exec Decode 0 0000 32 word address 32 32 bits (binary) byte address (big Endian) 88 HUST-FET, 13/02/2011
  89. Chế độ địa chỉ MIPS op rs rt rd funct Register 1. Register addressing word operand op rs rt offset Memory 2. Base addressing word or byte operand base register 3. Immediate addressing op rs rt operand 4. PC-relative addressing op rs rt offset Memory branch destination instruction Program Counter (PC) 5. Pseudo-direct addressing op jump address Memory || jump destination instruction Program Counter (PC) 89 HUST-FET, 13/02/2011
  90. Nguyên tắc thiết kế RISC  Simplicity favors regularity  fixed size instructions – 32-bits  small number of instruction formats  Smaller is faster  limited instruction set  limited number of registers in register file  limited number of addressing modes  Good design demands good compromises  three instruction formats  Make the common case fast  arithmetic operands from the register file (load-store machine)  allow instructions to contain immediate operands 90 HUST-FET, 13/02/2011
  91. Biên dịch C program Biến đổi chương trình C thành hợp ngữ compiler assembly code  Các ưu điểm của chương trình ngôn ngữ bậc cao  Số dòng mã ít hơn rất nhiều  dễ hiểu dễ biên dịch   Ngày nay các trình biên dịch tối ưu có thể tạo ra mã hợp ngữ tốt như chuyên gia lập trình và thường tốt hơn khi dịch các chương trình lớn  Kích thước mã nhỏ hơn, tốc độ nhanh hơn 91 HUST-FET, 13/02/2011
  92. Assembler C program Kiểm tra cú pháp mã hợp ngữ và chuyển đổi mã biểu tượng (mã hợp compiler ngữ) thành mã đổi tượng (mã máy). assembly code  Ưu điểm của assembler assembler  Dễ nhớ  Sử dụng nhãn địa chỉ - giá trị địa object code chỉ được tính bởi assembler  Sử dụng chỉ thị giả - VD., “move $t0, $t1” chỉ có trong assembler và sẽ được chuyển thành chỉ thị “add $t0,$t1,$zero”)  Chú ý: Khi xác định hiệu năng cần đếm số chỉ thị được thực thi chứ không phải kích thước mã chương trình. 92 HUST-FET, 13/02/2011
  93. Nhiệm vụ chính của assembler 1. Tạo bảng biểu tượng (symbol table) chứa tên biểu tượng (nhãn) và địa chỉ tương ứng  1 biểu tượng địa phương được sử dụng trong tệp nó được định nghĩa. Biểu tượng được quy ước mặc định là địa phương.  1 biểu tượng toàn cục (ngoại) tham chiếu/được tham chiếu đến mã hoặc dữ liệu ở 1 tệp. Các biểu tượng toàn cục được khai báo rõ ràng là toàn cục (VD., .globl main) 2. Dịch các lệnh ở mã hợp ngữ thành ngôn ngữ máy bằng cách “lắp ghép” các giá trị số tương ứng với mã lệnh (opcode), chỉ số thanh ghi (register specifiers), số bít dịch (shift amounts), và độ lệch các lệnh jump/branch. 93 HUST-FET, 13/02/2011
  94. Các nhiệm vụ khác của Assembler  Thay mã giả lệnh bằng mã hợp ngữ hợp lệ  Thanh ghi $at được dành riêng cho assembler để làm việc này  Thay lệnh rẽ nhánh xa bằng 1 lệnh rẽ nhánh gần theo sau bởi 1 lệnh nhảy  Thay lệnh với giá trị tức thời lớn bằng lệnh lui theo sau bởi 1 lệnh ori  Đổi các số ở dạng thập phân và hệ 16 thành các số ở dạng nhị phân và ký tự thành mã ASCII tương ứng.  Xử lý các dẫn hướng sắp xếp dữ liệu (e.g., .asciiz)  Triển khai các macro thành các chuỗi chỉ thị 94 HUST-FET, 13/02/2011
  95. Sơ đồ bộ nhớ MIPS Memory f f f f f f f c Mem Map I/O Kernel Code & Data $sp 7f f f f f fc Stack 230 words Dynamic data $gp 1000 8000 Static data 1000 0000 Text Segment PC 0040 0000 Reserved 0000 0000 95 HUST-FET, 13/02/2011
  96. Cấu trúc 1 tệp mã máy  Object file header: kích thước và vị trí các phần sau trong tệp  Text (code) segment (.text) : mã máy  Data segment (.data) : dữ liệu đi kèm với mã  Dữ liệu tĩnh (static data) – được cấp phát trong toàn bộ quá trình chạy  Dữ liệu động (dynamic data) – cấp phát khi cần thiết  Relocation information: xác định các lệnh (dữ liệu) sử dụng (nằm tại vị trị) địa chỉ tuyệt đối – không liên quan đến 1 thanh ghi (kể cả PC)  Trên MIPS các lệnh j, jal, và 1 số lệnh đọc ghi (VD., lw $t1, 100($zero) ) sử dụng địa chỉ tuyệt đối  Symbol table: các nhã toàn cục cùng với địa chỉ (nếu được định nghĩa cùng trong đoạn mã) hoặc không cùng địa chỉ (nếu được định nghĩa ngoài đoạn mã)  Debugging information 96 HUST-FET, 13/02/2011
  97. Ví dụ 2.8. Cấu trúc tệp mã máy Gbl? Symbol Address .data str 1000 0000 .align 0 cr 1000 000b str: .asciiz "The answer is " yes main 0040 0000 cr: .asciiz "\n" .text loop 0040 000c .align 2 brnc 0040 001c .globl main done 0040 0024 .globl printf main: ori $2, $0, 5 yes printf ???? ???? syscall Relocation Info move $8, $2 loop: beq $8, $9, done Address Data/Instr blt $8, $9, brnc 1000 0000 str sub $8, $8, $9 1000 000b cr j loop brnc: sub $9, $9, $8 0040 0018 j loop j loop 0040 0020 j loop done: jal printf 0040 0024 jal printf 97 HUST-FET, 13/02/2011
  98. Liên kết (linker) C program compiler main text segment assembly code assembler printf text segment object code library routines linker machine code executable 98 HUST-FET, 13/02/2011
  99. Liên kết 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 99 HUST-FET, 13/02/2011
  100. Liên kết Executable file Object file main: main: . . . . . . jal printf jal ???? Linker printf: . . call, printf C library . Relocation printf: . info . . 100 HUST-FET, 13/02/2011
  101. Liên kết 2 tệp mã lệnh Executable File 1 + File 2 Dbg Smtbl Reloc Dseg Txtseg Hdr Hdr Txtseg Dseg Reloc Hdr Hdr Txtseg Dseg Reloc Smtbl Dbg Smtbl Reloc Dseg Txtseg Hdr 101 HUST-FET, 13/02/2011
  102. Nạp chương trình C program compiler assembly code assembler object code library routines linker machine code executable loader memory 102 HUST-FET, 13/02/2011
  103. Nạp chương trình  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 103 HUST-FET, 13/02/2011
  104. 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 Chương 2. Ngôn ngữ máy tính và các phép toán 104 HUST-FET, 13/02/2011
  105. 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 Chương 2. Ngôn ngữ máy tính và các phép toán 105 HUST-FET, 13/02/2011
  106. Phép toán dịch  Dịch logic a0n-1 an-2 a1 a0  Các chữ số trống được điền bằng 0 an-1 an-2 a1 a00  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 an-1 an-2 a1 a0  Bít dấu (MSB) không được thay đổi an-1 an-2 an-3 a00 . 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 Chương 2. Ngôn ngữ máy tính và các phép toán 106 HUST-FET, 13/02/2011
  107. 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 Chương 2. Ngôn ngữ máy tính và các phép toán 107 HUST-FET, 13/02/2011
  108. Bộ dịch Bộ dịch trái 1 bít, và dịch phải 2 bít Chương 2. Ngôn ngữ máy tính và các phép toán 108 HUST-FET, 13/02/2011
  109. Bộ cộng nửa, cộng 2 số 1 bit Tín hiệu vào: a, b a s Half Adder Tín hiệu ra: s (sum), co (carry out) (HA) b co a b s co 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 Câu hỏi: a s Xác định biểu thức Bool cho s, và co b co 109 HUST-FET, 13/02/2011
  110. Bộ cộng đầy đủ, cộng 3 số 1 bit Tín hiệu vào: a, b, ci (carry in) a s Full Adder Tín hiệu ra: s (sum), co (carry out) ci (FA) co Câu hỏi: b Xác định biểu thức Bool cho s, và co a b ci s co 0 0 0 0 0 a b 0 0 1 1 0 0 1 0 1 0 s 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 ci co 1 1 0 0 1 1 1 1 1 1 110 HUST-FET, 13/02/2011
  111. 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 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 5 0 1 0 1 -7 1 0 0 1 5 0 1 0 1 -3 1 1 0 1 3 0 0 1 1 -2 1 1 1 0 2 0 0 1 0 -5 1 0 1 1 -8 1 0 0 0 7 0 1 1 1 7 0 1 1 1 -8 1 0 0 0 Tràn Tràn Không tràn Không tràn  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) Chương 2. Ngôn ngữ máy tính và các phép toán 111 HUST-FET, 13/02/2011
  112. Bộ cộng 2 số n bít dạng bù 2 an-1 bn-1 a2 b2 a1 b1 a0 b0 add/ subtract cn-1 cn-2 c2 c1 c0 C-1 FA FA FA FA a b sn-1 s2 s1 s0 s overflow ci Bộ cộng nối tiếp gồm co 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 Chương 2. Ngôn ngữ máy tính và các phép toán 112 HUST-FET, 13/02/2011
  113. 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) Chương 2. Ngôn ngữ máy tính và các phép toán 113 HUST-FET, 13/02/2011
  114. Bộ cộng CLA  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 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 Lan truyền nhớ: pi= (ai  bi) Tạo ra ci khi ai = bi = 1 Truyền nhớ từ đầu vào đến đầu ra khi ai  bi = 1  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 Chương 2. Ngôn ngữ máy tính và các phép toán 114 HUST-FET, 13/02/2011
  115. Bộ cộng CLA  Tính toán bit nhớ 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  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! Chương 2. Ngôn ngữ máy tính và các phép toán 115 HUST-FET, 13/02/2011
  116. Bộ cộng CLA 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 ai pi bi si ci-1 gi Tầng 2: Tính toán bit nhớ (2 mức logic) - CLA c-1 p p0 p1 c-1 3 p2 c-1 p0 g0 p0 c0 p1 p1 p2 p2 g0 p3 g0 c-1 p1 g1 p0 p2 p2 p3 p1 g1 c 2 g2 c3 g0 c1 p2 p3 p1 g2 g3 g1 Chương 2. Ngôn ngữ máy tính và các phép toán 116 HUST-FET, 13/02/2011
  117. 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 a3 a2 a1 a0 * b3 b2 b1 b0 a b a*b a b a b a b a b 3 0 2 0 1 0 0 0 0 0 0 + a b a b a b a b 3 1 2 1 1 1 0 1 0 1 0 + a3b2 a2b2 a1b2 a0b2 1 0 0 + a3b3 a2b3 a1b3 a0b3 s7 s6 s5 s4 s3 s2 s1 s0 1 1 1  Ví dụ 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 Chương 2. Ngôn ngữ máy tính và các phép toán 117 HUST-FET, 13/02/2011
  118. Bộ nhân không dấu song song  Sử dụng logic tổ hợp a3b0 a2b0 a1b0 a0b0 a3b1 a2b1 a1b1 a0b1 a b a b a b a b co FA ci co FA ci co FA ci co FA ci s s s s a3b2 a2b2 a1b2 a0b2 a b a b a b a b co FA ci co FA ci co FA ci co FA ci s s s s a3b3 a2b3 a1b3 a0b3 a b a b a b a b co FA ci co FA ci co FA ci co FA ci s s s s p7 p6 p5 p4 p3 p2 p1 p0 Chương 2. Ngôn ngữ máy tính và các phép toán 118 HUST-FET, 13/02/2011
  119. 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) 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 Chương 2. Ngôn ngữ máy tính và các phép toán 119 HUST-FET, 13/02/2011
  120. Ví dụ 2.9 – Phép nhân có dấu 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 Chương 2. Ngôn ngữ máy tính và các phép toán 120 HUST-FET, 13/02/2011
  121. Phép nhân có dấu  Đơn giản hóa 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 a3 a2 a1 a0 * b3 b2 b1 +b0 1 p p p p p p p p a2b0 a1b0 a0b0 7 6 5 4 3 2 1 0 + a2b1 a1b1 a0b1 + a2b2 a1b2 a0b2 + a2b3 a1b3 a0b3 + 1 - a3b0 - a3b1 - a3b2 - a3b3 p7 p6 p5 p4 p3 p2 p1 p0 Chương 2. Ngôn ngữ máy tính và các phép toán 121 HUST-FET, 13/02/2011
  122. Phép nhân có dấu  Đơn giản hóa a3 a2 a1 a0 * b3 b2 b1 b0 a2b0 a1b0 a0b0 + a2b1 a1b1 a0b1 + a2b2 a1b2 a0b2 + a2b3 a1b3 a0b3 + 1 - a3b0 - a3b1 - a3b2 a3 a2 a1 a0 * b3 b2 b1 b0 - a3b3 a2b0 a1b0 a0b0 p7 p6 p5 p4 p3 p2 p1 p0 + a2b1 a1b1 a0b1 + a2b2 a1b2 a0b2 + a2b3 a1b3 a0b3 + 1 - 0 a3b3 a3b2 a3b1 a3b0 p7 p6 p5 p4 p3 p2 p1 p0 Chương 2. Ngôn ngữ máy tính và các phép toán 122 HUST-FET, 13/02/2011
  123. Phép nhân có dấu  Đơn giản hóa 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 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 Chương 2. Ngôn ngữ máy tính và các phép toán 123 HUST-FET, 13/02/2011
  124. Phép nhân có dấu  Đơn giản hóa 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 Chương 2. Ngôn ngữ máy tính và các phép toán 124 HUST-FET, 13/02/2011
  125. Bộ nhân có dấu Chương 2. Ngôn ngữ máy tính và các phép toán 125 HUST-FET, 13/02/2011
  126. 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 Chương 2. Ngôn ngữ máy tính và các phép toán 126 HUST-FET, 13/02/2011
  127. Bộ nhân nối tiếp Start Triển khai gồm:  2 thanh ghi 2n bit A[n-1:0] ← SBN  1 thanh ghi n bit B[n-1:0] ← SN  1 bộ cộng 2n bit Y[2n-1:0] ← 0 Count ← n  1 khối điều khiển Y B0 = 1 Y←Y+A Dịch trái Dịch phải N A[2n-1:0] B[n-1:0] Dịch phải B Dịch trái A Count ← Count - 1 2n-bit ALU N Count = 0 Y[2n-1:0] control Y Stop Chương 2. Ngôn ngữ máy tính và các phép toán 127 HUST-FET, 13/02/2011
  128. Ví dụ 2.10 - Bộ nhân nối tiếp Dịch trái Dịch phải A[2n-1:0] B[n-1:0] Y 0 0 0 0 0 0 0 0 2n-bit ALU A 0 0 0 0 1 1 0 1 B 1 0 1 1 Counter=4 Y 0 0 0 0 1 1 0 1 Y[2n-1:0] control A 0 0 0 1 1 0 1 0 B 0 1 0 1 Counter=3 Y 0 0 1 0 0 1 1 1 Start A 0 0 1 1 0 1 0 0 B 0 0 1 0 Counter=2 A[n-1:0] ← SBN B[n-1:0] ← SN Y 0 0 1 0 0 1 1 1 Y[2n-1:0] ← 0 A 0 1 1 0 1 0 0 0 B 0 0 0 1 Counter=1 Count ← n Y 1 0 0 0 1 1 1 1 Y B0 = 1 Y←Y+A A 1 1 0 1 0 0 0 0 B 0 0 0 0 Counter=0 N Dịch phải B Dịch trái A Nhận xét: Count ← Count - 1  Một nửa số bit của A luôn bằng 0 N  Khi A dịch trái, bit 0 được thêm vào bên phải Count = 0 các bit LSB của tích không bị ảnh hưởng Y Stop Ý tưởng: Giữ A ở phía trái của tích và dịch tích sang phải Chương 2. Ngôn ngữ máy tính và các phép toán 128 HUST-FET, 13/02/2011
  129. Bộ nhân nối tiếp – Dùng n-bit ALU Start Triển khai gồm:  2 thanh ghi n bit  1 thanh ghi 2n+1 bit A[n-1:0] ← SBN B[n-1:0] ← SN  1 bộ cộng n bit C,Y[2n-1:0] ← 0  1 khối điều khiển Count ← n Y C,Y[2n-1:n]← B = 1 0 Y[2n-1:n]+A N Dịch phải B A[n-1:0] B[n-1:0] Dịch phải C,Y Count ← Count - 1 N n-bit ALU Count = 0 Y Stop C,Y[2n-1:0] control 129 HUST-FET, 13/02/2011
  130. Ví dụ 2.11 – Bộ nhân nối tiếp Y 0 0 0 0 0 0 0 0 0 A[n-1:0] B[n-1:0] A 1 1 0 1 B 1 0 1 1 Counter=4 Y 0 1 1 0 1 0 0 0 0 n-bit ALU Y 0 0 1 1 0 1 0 0 0 C,Y[2n-1:0] control A 1 1 0 1 B 0 1 0 1 Counter=3 Y 1 0 0 1 1 1 0 0 0 Start Y 0 1 0 0 1 1 1 0 0 A[n-1:0] ← SBN A 1 1 0 1 B 0 0 1 0 Counter=2 B[n-1:0] ← SN C,Y[2n-1:0] ← 0 Y 0 1 0 0 1 1 1 0 0 Count ← n Y 0 0 1 0 0 1 1 1 0 Y C,Y[2n-1:n]← B = 1 A 1 1 0 1 0 Y[2n-1:n]+A B 0 0 0 1 Counter=1 N Y 1 0 0 0 1 1 1 1 0 Dịch phải B Dịch phải C,Y Y 0 1 0 0 0 1 1 1 1 B 0 0 0 0 Counter=0 Count ← Count - 1 Nhận xét: Trong quá trình nhân chỉ một số bit N Count = 0 của Y có ý nghĩa với kết quả Y Stop 130 HUST-FET, 13/02/2011
  131. Bộ nhân nối tiếp Start Triển khai gồm:  1 thanh ghi n bit  1 thanh ghi 2n+1 bit A[n-1:0] ← SBN  1 bộ cộng n bit C,Y[n-1:0],B[n-1:0] ← 0,SN  1 khối điều khiển Count ← n Y C,Y[n-1:0]← B = 1 0 Y[n-1:0]+A N Dịch phải C,Y,B Số bị nhân A Count ← Count - 1 an-1 a0 Logic điều khiển cộng và N Bộ tổng n bit Count = 0 dịch phải Y cn yn-1 y0 bn-1 b0 Stop Số nhân B 131 HUST-FET, 13/02/2011
  132. Ví dụ 2.12 – Bộ nhân nối tiếp Số bị nhân A Y 0 0 0 0 0 1 0 1 1 Counter=4 an-1 a0 A 1 1 0 1 Logic điều khiển cộng và Bộ tổng n bit Y 0 1 1 0 1 1 0 1 1 dịch phải Y 0 0 1 1 0 1 1 0 1 Counter=3 c y y b b A 1 1 0 1 n n-1 0 n-1 0 Số nhân B Y 1 0 0 1 1 1 1 0 1 Start Y 0 1 0 0 1 1 1 1 0 Counter=2 A 1 1 0 1 A[n-1:0] ← SBN Y 0 1 0 0 1 1 1 1 0 C,Y[n-1:0],B[n-1:0] ← 0,SN Count ← n Y 0 0 1 0 0 1 1 1 1 Counter=1 A 1 1 0 1 Y C,Y[n-1:0]← B = 1 0 Y[n-1:0]+A Y 1 0 0 0 1 1 1 1 1 N Y 0 1 0 0 0 1 1 1 1 Counter=0 Dịch phải C,Y,B Count ← Count - 1 N Count = 0 Y Stop 132 HUST-FET, 13/02/2011
  133. 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ụ: 4 1 B = 001110 (1410), u = 3, v = 2 A x B = A* 2 – A*2 133 HUST-FET, 13/02/2011
  134. Ví dụ 2.13 – Bộ nhân Booth A 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 B 0 0 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 0 B 0 +1 0 0 -1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 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 134 HUST-FET, 13/02/2011
  135. Thuật toán nhân Booth Start A[n-1:0] ← SBN B[n-1:0] ← SN C,Y[n-1:0],B-1 ← 0 Count ← n C,Y[n-1:0] 10 01 C,Y[n-1:0] BB ←Y[n-1:0]-A 0 -1 ←Y[n-1:0]+A N 00,11 Dịch phải C,Y,B,B-1 Count ← Count - 1 an-1 Số bị nhân A a0 N Logic điều khiển cộng, trừ Bộ tổng n bit Count = 0 và dịch phải Y cn yn-1 y0 bn-1 Số nhân B b0 b-1 Stop 135 HUST-FET, 13/02/2011
  136. Ví dụ 2.14 – Minh họa thuật toán Booth A 0 1 0 1 0 1 Y 0 0 0 0 0 0 0 0 0 1 1 1 0 0 Counter=6 Y 0 0 0 0 0 0 0 0 0 0 1 1 1 0 Counter=5 Start -A 1 0 1 0 1 1 Y 1 1 0 1 0 1 1 0 0 0 1 1 1 0 A[n-1:0] ← SBN B[n-1:0] ← SN Y 1 1 1 0 1 0 1 1 0 0 0 1 1 1 Counter=4 C,Y[n-1:0],B-1 ← 0 Y 1 1 1 1 0 1 0 1 1 0 0 0 1 1 Counter=3 Count ← n Y 1 1 1 1 1 0 1 0 1 1 0 0 0 1 Counter=2 C,Y[n-1:0] 10 01 C,Y[n-1:0] BB +A 0 1 0 1 0 1 ←Y[n-1:0]-A 0 -1 ←Y[n-1:0]+A N 00,11 Y 0 0 1 0 0 1 0 0 1 1 0 0 0 1 Y 0 0 0 1 0 0 1 0 0 1 1 0 0 0 Counter=1 Dịch phải C,Y,B,B-1 Y 0 0 0 0 1 0 0 1 0 0 1 1 0 0 Counter=0 Count ← Count - 1 N an-1 Số bị nhân A a0 Count = 0 Logic điều khiển cộng, trừ Bộ tổng n bit và dịch phải Y Stop cn yn-1 y0 bn-1 Số nhân B b0 b-1 136 HUST-FET, 13/02/2011
  137. Nhân Booth: Nhân có dấu Vì a, b là 2 số có dấu dạng bù 2: n-1 n-2 a = -2 *an + 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: 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 Giá trị được tính toán bởi bộ nhân Booth: 2 (0 - a0) * b + (a0 - a1) * b * 2 + (a1 – a2) * b * 2 + n-2 n-1 (an-3 – an-2) * b * 2 + (an-2 – an-1) * b * 2 Triển khai các số hạng và tối giản: n-1 n-2 b * (-2 *an + 2 *an-2 + + 2*a1 + a0)= b * a. which is exactly the product of a and b. 137 HUST-FET, 13/02/2011
  138. Phép chia 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 A 0 0 1 1 1 Y 0 B 1 1 B 0 1 1 Y 0 0 B 0 0 1 1 Y 0 0 1 A 0 0 0 0 1 B 0 0 0 1 1 Y 0 0 1 0 Tối ưu phần cứng: trừ cho số chia và dịch trái phần dư 138 HUST-FET, 13/02/2011
  139. Thuật toán chia nối tiếp Start  Trừ Y = Y – B và kiểm tra bit dấu C của kết quả B[n:0] ← SC  Nếu C = 1 (phép trừ kết quả âm) C, Y[n-1:0],A[n-1:0] ← 0,SBC Count ← n  Bít kết quả a0=0  Phục hồi số bị chia: Y = Y + B Dịch trái C,Y,A C,Y[n-1:0]←  Nếu C = 0 (phép trừ kết quả dương) C,Y[n-1:0]-B  Bít kết quả a0=1 N C = 1 A0←1 0 bn-1 Số chia B b0 Y A0←0 Phục hồi Y = Y+B Logic điều khiển trừ và Bộ trừ n+1 bit dịch trái Count ← Count - 1 N Count = 0 C yn-1 y0 an-1 Số bị chia A a0 Y Stop 139 HUST-FET, 13/02/2011
  140. Ví dụ 2.15 – Bộ chia nối tiếp B 0 0 1 1 Start Y 0 0 0 0 0 0 1 1 1 Counter=4 Y 0 0 0 0 0 1 1 1 0 -B 1 1 1 0 1 B[n:0] ← SC C, Y[n-1:0],A[n-1:0] ← 0,SBC Y 1 1 1 0 1 1 1 1 0 Count ← n Y 0 0 0 0 0 1 1 1 0 Counter=3 Y 0 0 0 0 1 1 1 0 0 -B 1 1 1 0 1 Dịch trái C,Y,A Y 1 1 1 1 0 1 1 1 0 Counter=2 Y 0 0 0 0 1 1 1 0 0 C,Y[n-1:0]← Y 0 0 0 1 1 1 0 0 0 C,Y[n-1:0]-B -B 1 1 1 0 1 Y 0 0 0 0 0 1 0 0 0 Y 0 0 0 0 0 1 0 0 1 Counter=1 N Y 0 0 0 0 1 0 0 1 0 C = 1 A0←1 -B 1 1 1 0 1 Y Y 1 1 1 1 0 0 0 1 0 A0←0 Y 0 0 0 0 1 0 0 1 0 Counter=0 Phục hồi Y = Y+B 0 bn-1 Số chia B b0 Count ← Count - 1 N Logic điều khiển trừ và Count = 0 Bộ trừ n+1 bit dịch trái Y Stop C yn-1 y0 an-1 Số bị chia A a0 140 HUST-FET, 13/02/2011
  141. 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 141 HUST-FET, 13/02/2011
  142. Phép toán dấu phẩy động EA EB . Số dấu phẩy động: A M A 2 ; B M B 2 . Phép cộng trừ: giả sử EA > EB ' EA ' EA EB A B M A M B 2 trong đó M B M B 2 . Phép nhân EA EB A B M A  M B 2 . Phép chia EA EB A/ B M A / M B 2 . 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 142 HUST-FET, 13/02/2011