Bài giảng Kiến trúc máy tính - Chương 2: Ngôn ngữ Máy: Tập lệnh

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ập lệnh

1. Các thành phần & Cấu trúc BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 2
2. Tập lệnh (Instruction Set)  Tập các lệnh của 1 máy tính  Máy tính khác nhau có các tập lệnh khác nhau  Tuy vậy, có thể có nhiều điểm giống nhau  Máy tính ở các thế hệ trước thường có tập lệnh rất đơn giản  Lý do: dễ thực hiện  Một số máy tính hiện nay cũng có tập lệnh đơn giản BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 4
3. Phép tính số học  Phép cộng (+) và trừ (-): 3 toán hạng  2 nguồn và 1 đích add a, b, c # a = b + c  Các phép tính số học đều có dạng trên  Nguyên tắc thiết kế 1: Đơn giản dễ tạo tính quy tắc  Tính quy tắc sẽ đơn giản hơn việc thực hiện  Đơn giản sẽ nâng hiệu xuất, giảm giá thành. BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 6
4. Toán hạng là thanh ghi  Có nhiều lệnh số học sử dụng các thanh ghi làm toán hạng  MIPS có tệp 32 thanh ghi 32-bit  Use for frequently accessed data  Đánh số từ 0 đến 31  32-bit dữ liệu được gọi là 1 “từ” (“word”)  Được đặt tên gợi nhớ (Ass. Names):  $t0, $t1, , $t9 chứa các giá trị tạm thời  $s0, $s1, , $s7 chứa các biến  Nguyên tắc thiết kế 2: Càng nhỏ, càng nhanh  Ngược lại với bộ nhớ chính: hàng triệu ô nhớ. BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 8
5. Toán hạng là bộ nhớ  Bộ nhớ chính dùng để lưu trữ toán hạng có cấu trúc  Arrays, structures, dynamic data  Sử dụng cho các phép số học  Nạp các giá trị từ bộ nhớ vào các thanh ghi  Lưu giữ các kết quả trong thanh ghi ra bộ nhớ  Bộ nhớ được định vị theo đơn vị từng byte  Mỗi địa chỉ định vị trí cho một 8-bit byte  1 từ được sắp xếp gồm 4 bytes trong bộ nhớ  Địa chỉ truy xuất = Địa chỉ biểu diễn * 4 byte  MIPS chứa dữ liệu theo Big Endian  Big Endian: Byte có giá trị lớn nằm ở địa chỉ thấp  Little Endian: Byte có giá trị nhỏ nhất Địa chỉ thấp BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 10
6. Ví dụ 2: Toán hạng bộ nhớ  C code: A[12] = h + A[8];  h chứa trong $s2, địa chỉ cơ sở của A chứa trong $s3  Sau khi biên dịch thành MIPS code:  Chỉ số 8 tương đương với độ dời 32 lw $t0, 32($s3) # Nạp 1 từ add $t0, $s2, $t0 sw $t0, 48($s3) # Nhớ 1 từ BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 12
7. Toán hạng trực tiếp  Các dữ liệu hằng trong 1 lệnh, như addi $s3, $s3, 4  Không tồn tại lệnh trừ với toán hạng trực tiếp (?????)  Tương đương với cộng 1 số âm addi $s2, $s1, -1  Nguyên tắc thiết kế 3: Làm cho các trường hợp phổ biến thực hiện nhanh  Hằng có giá trị nhỏ rất phổ biến  Toán hạng trực tiếp trách được lệnh nạp BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 14
8. Số nguyên nhị phân không dấu  Cho 1 số n-bit, có dạng n  Tầm vực giá trị sẽ là: 0 đến +2 – 1  Ví dụ:  0000 0000 0000 0000 0000 0000 0000 10112 = 0 + + 1×23 + 0×22 +1×21 +1×20 = 0 + + 8 + 0 + 2 + 1 = 1110  Giá trị 1 số nhị phân không dấu 32-bit sẽ là:  0 đến +4,294,967,295 (giá trị thập phân) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 16
9. Số nguyên có dấu dạng bù 2 (tt.)  Bit 31 là bit dấu  1 có nghĩa là số âm (-)  0 có nghĩa là số không âm (+) n – 1  Dạng –(–2 ) không tồn tại  Các số không âm biểu diễn giống số không dấu và số bù 2  Vài số đặc biệt như:  0: 0000 0000 0000  –1: 1111 1111 1111  Số âm nhỏ nhất: 1000 0000 0000  Số dương lớn nhất: 0111 1111 1111 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 18
10. Mở rộng bit với số có dấu  Biểu diễn với số bit nhiều hơn  Dữ nguyên giá trị  Ví dụ: Trong tập lệnh MIPS  addi: mở rộng số bit giá trị toán hạng trực tiếp  lb, lh: mở rộng số bit với byte/(1/2 từ) được nạp  beq, bne: mở rộng số bit của độ dời địa chỉ  Thêm giá bit dấu vào các bit mở rộng bên trái  Đối với giá trị không dấu: gán 0s  Ví dụ: chuyển số 8-bit thành số 16-bit  +2: 0000 0010 => 0000 0000 0000 0010  –2: 1111 1110 => 1111 1111 1111 1110 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 20
11. Các lệnh dạng R op rs rt rd shamt funct 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits  Cấu trúc thành phần của lệnh dạng R  op: Mã lệnh (opcode)  rs: Chỉ số thanh ghi nguồn thứ nhất  rt: Chỉ số thanh ghi nguồn thứ nhì  rd: Chỉ số thanh ghi đích  shamt: Số bit dịch chuyển  funct: mã chức năng mở rộng (extends opcode) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 22
12. Biểu diễn số dạng hệ 16  Hệ số 16  Rút gọn cách biểu diễn chuỗi nhị phân  4 bits cho mỗi số hex  Ví dụ: eca8 6420  1110 1100 1010 1000 0110 0100 0010 0000 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 24
13. Tổ chức chương trình  Lệnh được biểu diễn dạng nhị phân, giống như dữ liệu  Lệnh và dữ liệu được lưu trong bộ nhớ  Các chương trình có thể thực hiện trên các chương trình khác, ví dụ: compilers, linkers,  Tương thích nhị phân cho phép chương trình thực hiện trên các máy khác nhau ISA chuẩn BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 26
14. Các tác vụ dịch (shift) op rs rt rd shamt funct 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits  shamt: dịch vị trí các bits  Dịch trái  Dịch trái các bit n vị trí và gán n bit bên phải giá trị 0 i  sll bởi i bits có nghĩa nhân 2  Dịch phải  Dịch phải các bit n vị trí và gán n bit bên trái giá trị 0 i  srl bởi i bits có nghĩa chia 2 (chỉ không dấu) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 28
15. Tác vụ “hoặc” (OR)  Thêm 1 số bit vào 1 từ  Gán giá trị 1 nhóm bit thành 1 trong khi giữ nguyên giá trị các bit còn lại or $t0, $t1, $t2 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 30
16. Các tác vụ điều kiện  Rẽ nhánh đến 1 lệnh có nhãn, nếu điều kiện thỏa  Nếu không thỏa, tiếp tục  beq rs, rt, L1  Nếu (rs == rt), nhảy đến lệnh có nhãn L1;  bne rs, rt, L1  Nếu (rs != rt), nhảy đến lệnh có nhãn L1;  j L1  Nhảy vô điều kiện đến lệnh có nhãn L1 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 32
17. Biên dịch các phát biểu Loop  C code: while (save[i] == k) i += 1;  i chứa trong $s3, k trong $s5, địa chỉ của save chứa trong $s6  Sau khi biên dịch thành MIPS code: Loop: sll $t1, $s3, 2 add $t1, $t1, $s6 lw $t0, 0($t1) bne $t0, $s5, Exit addi $s3, $s3, 1 j Loop Exit: BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 34
18. Các tác vụ kiểm tra điều kiện khác  Gán kết quả là 1, nếu điều kiện thỏa  Nếu không thỏa, gán là 0  slt rd, rs, rt  if (rs < rt) rd = 1; else rd = 0;  slti rt, rs, constant  if (rs < constant) rt = 1; else rt = 0;  Sử dụng kết hợp với lệnh beq, bne slt $t0, $s1, $s2 # if ($s1 < $s2) bne $t0, $zero, L # branch to L BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 36
19. Dấu và Không dấu  So sánh có dấu: slt, slti  So sánh không dấu: sltu, sltui  Ví dụ  $s0 = 1111 1111 1111 1111 1111 1111 1111 1111  $s1 = 0000 0000 0000 0000 0000 0000 0000 0001  slt $t0, $s0, $s1 # có đấu  –1 +1 $t0 = 0 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 38
20. Ví dụ: Case/Switch slt $t3 , $s5 , $zero L0: add $s0 , $s3 , $s4 bne $t3 , $zero , Exit j Exit slt $t3 , $s5 , $t2 L1: add $s0 , $s1 , $s2 beq $t3 , $zero , Exit j Exit L2: sub $s0 , $s1 , $s2 add $t1 , $s5 , $s5 j Exit add $t1 , $t1 , $t1 L3: sub $s0 , $s3 , $s4 Exit: add $t1 , $t1 , $t4 lw $t0, 0($t1) jr $t0 Khoa Khoa học & Kỹ thuật Máy tính 25-Aug-16 40
21. Ý đồ sử dụng các thanh ghi  $a0 – $a3: chứa thông số (reg’s 4 – 7)  $v0, $v1: giá trị trả về (reg’s 2 and 3)  $t0 – $t9: chứa giá trị tạm  Có thể thay đổi nội dung khi thực hiện thủ tục  $s0 – $s7: bảo vệ  Cất/khôi phục bởi thủ tục  $gp: Con trỏ toàn cục dữ liệu tĩnh (reg 28)  $sp: stack pointer (reg 29)  $fp: frame pointer (reg 30)  $ra: Địa chỉ trở về (reg 31) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 42
22. Ví dụ: gọi thủ tục (leaf)  C code: int leaf_example (int g, h, i, j) { int f; f = (g + h) - (i + j); return f; }  Thông số g, , j chứa trong $a0, , $a3  f trong $s0 (vì vậy, $s0 cất trong stack)  Kết quả trả về trong $v0 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 44
23. Gọi thủ tục (Non-Leaf)  Thủ tục gọi thủ tục khác  Gọi đệ quy, thủ tục gọi phải cất vào stack thông tin:  Địa chỉ trở về của nó trong thủ tục “cha”  Tất cả các thông số và giá trị tạm thời  Phục hồi từ stack sau khi thủ tục kết thúc BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 46
24. Ví dụ: gọi thủ tục (Non-Leaf) tt.  Sau khi biên dịch thành MIPS code: fact: addi $sp, $sp, -8 # adjust stack for 2 items sw $ra, 4($sp) # save return address sw $a0, 0($sp) # save argument slti $t0, $a0, 1 # test for n < 1 beq $t0, $zero, L1 addi $v0, $zero, 1 # if so, result is 1 addi $sp, $sp, 8 # pop 2 items from stack jr $ra # and return L1: addi $a0, $a0, -1 # else decrement n jal fact # recursive call lw $a0, 0($sp) # restore original n lw $ra, 4($sp) # and return address addi $sp, $sp, 8 # pop 2 items from stack mul $v0, $a0, $v0 # multiply to get result BK jr $ra # and return TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 48
25. Bố cục chứa trong bộ nhớ  Text: mã lệnh chương trình  Dữ liệu tĩnh: biến toàn cục  Ví dụ: static variables in C, constant arrays and strings  $gp initialized to address allowing ±offsets into this segment  Dữ liệu động: heap  E.g., malloc in C, new in Java  Stack: lưu trữ tự động BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 50
26. Nhóm các lệnh Byte/Halfword  Dùng cho các tác vụ xử lý theo bit  MIPS byte/halfword load/store  Xử lý chuỗi khá phổ biến lb rt, offset(rs) lh rt, offset(rs)  Sign extend to 32 bits in rt lbu rt, offset(rs) lhu rt, offset(rs)  Zero extend to 32 bits in rt sb rt, offset(rs) sh rt, offset(rs)  Chỉ ghi phần giá trị thấp byte/halfword BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 52
27. Ví dụ: String Copy (tt.) Sau khi biên dịch thành MIPS code: strcpy: addi $sp, $sp, -4 # adjust stack for 1 item sw $s0, 0($sp) # save $s0 add $s0, $zero, $zero # i = 0 L1: add $t1, $s0, $a1 # addr of y[i] in $t1 lbu $t2, 0($t1) # $t2 = y[i] add $t3, $s0, $a0 # addr of x[i] in $t3 sb $t2, 0($t3) # x[i] = y[i] beq $t2, $zero, L2 # exit loop if y[i] == 0 addi $s0, $s0, 1 # i = i + 1 j L1 # next iteration of loop L2: lw $s0, 0($sp) # restore saved $s0 addi $sp, $sp, 4 # pop 1 item from stack jr $ra # and return BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 54
28. Xác định địa chỉ rẽ nhánh  Dạng lệnh rẽ nhánh gồm:  Opcode, 2 thanh ghi, target address  Vị trí nhảy đến địa chỉ rẽ nhánh thường gần lệnh rẽ nhánh: nhảy tới hoặc lui op rs rt constant or address 6 bits 5 bits 5 bits 16 bits  Tương đối với giá trị PC  Địa chỉ đích = PC + offset × 4  PC đã tăng lên 4, khi lệnh thực hiện BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 56
29. Ví dụ: Xác định địa chỉ đích  Sử dụng lại đoạn code vòng lặp trước đây  Giả sử Loop bắt đầu từ địa chỉ 80000 Loop: sll $t1, $s3, 2 80000 0 0 19 9 2 0 add $t1, $t1, $s6 80004 0 9 22 9 0 32 lw $t0, 0($t1) 80008 35 9 8 0 bne $t0, $s5, Exit 80012 5 8 21 2 addi $s3, $s3, 1 80016 8 19 19 1 j Loop 80020 2 20000 Exit: 80024 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 58
30. Tóm tắt Addressing Mode BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 60
31. Đồng bộ trong MIPS  Load linked: ll rt, offset(rs)  Store conditional: sc rt, offset(rs)  Succeeds if location not changed since the ll  Returns 1 in rt  Fails if location is changed  Returns 0 in rt  Ví dụ: atomic swap (to test/set lock variable) try: add $t0,$zero,$s4 ;copy exchange value ll $t1,0($s1) ;load linked sc $t0,0($s1) ;store conditional beq $t0,$zero,try ;branch store fails add $s4,$zero,$t1 ;put load value in $s4 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 62
32. Biên dịch và thực hiện BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 64
33. Liên kết các Object Modules  Linker: Còn gọi là link editor, cho phép ghép các object file riêng lẻ lại với nhau thành một chương trình thống nhất có thể thực thi được gọi là executable file  Quá trình ghép diễn ra theo 3 bước  Xếp mã chương trình và dữ liệu lại với nhau  Xác định địa chỉ cho các nhãn chương trình và dữ liệu So trùng các tham cứu nội và ngoại (internal/external reference)  Một executable file có các thành phần gần giống với object file trừ các phần: relocation information, symbol table và debugging information  Các object file, ngoài các chương trình do người dùng (user) viết, còn có các trình con viết sẵn trong thư viện (library) do compiler cung cấp, do người dùng tạo lập hay BK từ các nguồn chuyên biệt TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 66
34. Liên kết động  Chỉ liên kết/nạp khi thủ tục được gọi  Yêu cầu phần code của thủ tục được cấp phát bộ nhớ  Tránh việc phát sinh cấp phát sinh ra bởi kết nối với thư viện  Tự động cập nhật phiên bản mới của thư viện BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 68
35. Kết luận (tt.)  Đo đạc thực hiện tập lệnh của MIP với chương trình đánh giá BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 70