›
›

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

pdf 70 trang ngocly 3500
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ập lệnh", để 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_tap_lenh.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ập lệnh

  1. Kiến trúc Máy tính Khoa học & Kỹ thuật Máy tính Chương 2 Ngơn ngữ Máy: Tập lệnh BK TP.HCM
  2. 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
  3. Các bước thực hiện lệnh . Nạp lệnh: từ bộ nhớ . PC tăng lên sau mỗi lần nạp lệnh . PC lưu địa chỉ lệnh kế tiếp . Thực hiện lệnh: giải mã & thực hiện lệnh BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 3
  4. 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
  5. Tập lệnh MIPS  Được sử dụng trong mơn học này  Stanford MIPS được thương mại hĩa bởi MIPS Technologies (www.mips.com)  Cĩ thị phần lớn với lõi nhúng (embedded core)  Ứng dụng trong thiết bị điện tử, Mạng, lưu trữ, Camera, máy in, v.v.,  Đặc thù cho nhiều kiến trúc tập lệnh mới  Tham khảo MIPS Data tear-out card, và trong phụ lục B, E của sách giáo khoa BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 5
  6. Phép tính số học  Phép cộng (+) và trừ (-): 3 tố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
  7. Ví dụ: thực hiện phép số học  C code: f = (g + h) - (i + j);  Sau khi biên dịch thành MIPS code: add t0, g, h # temp t0 = g + h add t1, i, j # temp t1 = i + j sub f, t0, t1 # f = t0 - t1 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 7
  8. Tốn hạng là thanh ghi  Cĩ nhiều lệnh số học sử dụng các thanh ghi làm tố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
  9. Ví dụ: tốn hạng thanh ghi  C code: f = (g + h) - (i + j);  f, , j chứa trong $s0, , $s4  Sau khi biên dịch thành MIPS code: add $t0, $s1, $s2 add $t1, $s3, $s4 sub $s0, $t0, $t1 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 9
  10. Tốn hạng là bộ nhớ  Bộ nhớ chính dùng để lưu trữ tố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
  11. Ví dụ 1: Tốn hạng bộ nhớ  C code: g = h + A[8];  g chứa trong $s1, h 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  4 bytes/word lw $t0, 32($s3) # Nạp 1 từ (4bytes) add $s1, $s2, $t0 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 11
  12. Ví dụ 2: Tố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
  13. So sánh tốn hạng thanh ghi & bộ nhớ  Truy cập tốn hạng thanh ghi nhanh hơn bộ nhớ  Thực hiện tốn hạng bộ nhớ cần nạp và cất dữ liệu cần nhiều lệnh thực hiện hơn  Trình biên dịch yêu cầu các biến chứa trong thanh ghi tối đa  Chỉ chứa các biến trong bộ nhớ khi chúng ít được dùng đến  Tối ưu thanh ghi rất quan trọng! BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 13
  14. Tố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 tố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  Tố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
  15. Thanh ghi Hằng 0 (Zero)  Thanh ghi MIPS 0 ($zero) là hằng cố định cĩ giá trị 0  Giá trị khơng thay đổi được  Cĩ ích cho các tác vụ thường gặp như:  Ví dụ, gán giá trị một thanh ghi cho thanh ghi khác add $t2, $s1, $zero # $t2 = $s1 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 15
  16. 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
  17. Số nguyên cĩ dấu dạng bù 2  Cho 1 số n-bit như sau: (n – 1) (n – 1)  Tầm giá trị: –2 đến +2 – 1  Ví dụ:  1111 1111 1111 1111 1111 1111 1111 11002 = –1×231 + 1×230 + + 1×22 +0×21 +0×20 = –2,147,483,648 + 2,147,483,644 = –410  Giá trị 1 số nhị phân cĩ dấu 32-bit sẽ là  –2,147,483,648 đến +2,147,483,647 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 17
  18. 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
  19. Số âm cĩ dấu  Đảo giá trị bit và cộng 1  Đảo giá trị bit: 1 → 0, 0 → 1  Ví dụ: giá trị (-) 2  +2 = 0000 0000 00102  –2 = 1111 1111 11012 + 1 = 1111 1111 11102 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 19
  20. 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ị tố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
  21. Biểu diễn lệnh  Lệnh được mã hĩa thành giá trị nhị phân  Gọi là mã máy  Các lệnh của MIP  Mã hĩa thành từ lệnh 32-bit  Chia thành các phần nhỏ: Mã lệnh, thanh ghi,  Theo quy tắc!  Các thanh ghi MIP được đánh số:  $t0 – $t7 tương ứng với thanh ghi 8 – 15  $t8 – $t9 tương ứng với thanh ghi 24 – 25  $s0 – $s7 tương ứng với thanh ghi 16 – 23 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 21
  22. 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
  23. Ví dụ: Lệnh dạng R add $t0, $s1, $s2 special $s1 $s2 $t0 0 add 0 17 18 8 0 32 000000 10001 10010 01000 00000 100000 000000100011001001000000001000002 = 0232402016 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 23
  24. 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
  25. Lệnh MIPS dạng I op rs rt constant or address 6 bits 5 bits 5 bits 16 bits  Các lệnh số học trực tiếp hoặc lệnh nạp/cất  rt: Thanh ghi đích hoặc nguồn 15 15  Nếu là hằng: –2 to +2 – 1  Nếu là địa chỉ: Độ dời + địa chỉ cơ sỏ chứa trong rs  Nguyên tắc thiết kế 4: Thiết kế tốt yêu cầu sự kết hợp hợp lý  Nhiều dạng lệnh làm phức tạp giải mã, nhưng cho phép lệnh chứa đồng nhất chỉ trong 32-bit  Giữ dạng lệnh càng giống nhau càng tốt BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 25
  26. 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
  27. Tác tác vụ luận lý  Các lệnh xử lý bit  Cĩ tác dụng rút trích hoặc thêm nhĩm bit vào 1 từ BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 27
  28. 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
  29. Tác vụ “VÀ” (AND)  Dùng để đánh dấu các bits trong 1 từ  Chọn một số bits, xĩa số cịn lại về 0 and $t0, $t1, $t2 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 29
  30. 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
  31. Các tác vụ “Not”  Cĩ tác dụng đảo giá trị các bit trong 1 từ: đổi 0 thành 1, và 1 thành 0  MIPS cĩ tốn tử NOR với 3 tốn hạng  a NOR b == NOT ( a OR b ) nor $t0, $t1, $zero Register 0: always read as zero $t1 0000 0000 0000 0000 0011 1100 0000 0000 $t0 1111 1111 1111 1111 1100 0011 1111 1111 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 31
  32. 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
  33. Biên dịch các phát biểu if  C code: if (i==j) f = g+h; else f = g-h;  f, g, chứa trong $s0, $s1,  Sau khi biên dịch thành MIPS code: bne $s3, $s4, Else add $s0, $s1, $s2 j Exit Else: sub $s0, $s1, $s2 Exit: BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 33
  34. 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
  35. Khối căn bản (Basic Blocks)  Một khối chứa tuần tự các lệnh, trong đĩ  Khơng cĩ rẽ nhánh đi (except at end)  Khơng chứa địa chỉ đích đến (except at beginning)  Biên dịch sẽ nhận biết khối này để tối ưu kết quả dịch  Tăng nhanh việc xử lý các lệnh trong khối này BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 35
  36. 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
  37. Thiết kế lệnh rẽ nhánh  Tại sao khơng cĩ lệnh blt, bge, etc?  <, ≥, Thực hiện phần cứng chậm hơn =, ≠  Khi kết hợp với rẽ nhánh sẽ phải thực hiện nhiều việc hơn yêu cầu xung đồng hồ chậm hơn  All instructions penalized! (khơng thống nhất cho các lệnh)  beq và bne: trường hợp thường xảy ra  Đĩ là sự kết hợp tốt BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 37
  38. 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
  39. Ví dụ: Case/Switch Dịch đoạn mã C sau đây sang hợp ngữ MIPS Switch ( k ) { case 0 : f = i + j ; break ; case 1 : f = g + h ; break ; case 2 : f = g - h ; break ; case 3 : f = i - j ; break ; }  Giả sử các biến f đến k tương ứng với $s0 đến $s5, thanh ghi $t2 mang giá trị 4 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 39
  40. 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
  41. Gọi thủ tục  Các bước thực hiện gọi thủ tục 1. Chuyển thơng số vào vị trí (thanh ghi) 2. Chuyển quyền điều khiển cho thủ tục 3. Nhận tài nguyên lưu trữ cho thủ tục 4. Thực hiện cơng việc của thủ tục 5. Chuyển kết quả vào vị trí (thanh ghi) để trả về cho chương trình gọi 6. Trở về chương trình gọi BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 41
  42. Ý đồ 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ỏ tồ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
  43. Lệnh gọi thủ tục  Gọi thủ tục: jump and link (jal) jal ProcedureLabel  Địa chỉ lệnh kế chứa trong thanh ghi $ra  Nhảy đến địa chỉ đích  Trở về chương trình gọi: jump register jr $ra  Sao giá trị của $ra vào PC  Cĩ thể dùng nhảy theo điều kiện  Ví dụ: phát biểu case/switch BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 43
  44. 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
  45. Ví dụ: gọi thủ tục (tt.)  Sau khi biên dịch thành MIPS code: leaf_example: addi $sp, $sp, -4 sw $s0, 0($sp) add $t0, $a0, $a1 add $t1, $a2, $a3 sub $s0, $t0, $t1 add $v0, $s0, $zero lw $s0, 0($sp) addi $sp, $sp, 4 jr $ra BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 45
  46. 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
  47. Ví dụ: gọi thủ tục (Non-Leaf)  C code: int fact (int n) { if (n < 1) return f; else return n * fact(n - 1); }  Thơng số n chứa trong $a0  Kết quả trả về chứa trong $v0 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 47
  48. 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
  49. Cách lưu trữ trong Stack  Dữ liệu cục bộ được cấp phát tại thủ tục  e.g., C automatic variables  Procedure frame (activation record)  Compiler sử dụng để quản lý lưu trữ trong stack BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 49
  50. Bố cục chứa trong bộ nhớ  Text: mã lệnh chương trình  Dữ liệu tĩnh: biến tồ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
  51. Dữ liệu ký tự  Tập ký tự dạng Byte-encoded  ASCII: 128 Ký tự  95 graphic, 33 điều khiển  Latin-1: 256 Ký tự  ASCII, +96 ký tự graphics  Tập ký tự 32-bit dạng Unicode:  Sử dụng trong Java, C++ wide characters,  Chứa tồn bộ mã ký tự thế giới, cùng với symbols  UTF-8, UTF-16: variable-length encodings BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 51
  52. 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
  53. Ví dụ: Sao chuỗi (String Copy)  C code (nạve):  Ký tự Null- đánh dấu kết thúc string void strcpy (char x[], char y[]) { int i; i = 0; while ((x[i]=y[i])!='\0') i += 1; }  Địa chỉ của x, y chứa trong $a0, $a1  i chứa trong $s0 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 53
  54. 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
  55. Hằng 32-bit  Phần lớn các hằng hạn chế trong 16-bit  Đáp ứng đủ cho các tốn hạng trực tiếp 16-bit  Với các Hằng lớn hơn (32-bit) lui rt, constant  Sao 16-bit của hằng vào 16 bits bên trái của rt  Xĩa 16 bits bên phải của rt về 0 lui $s0, 61 0000 0000 0011 1101 0000 0000 0000 0000 ori $s0, $s0, 2304 0000 0000 0111 1101 0000 1001 0000 0000 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 55
  56. 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
  57. Địa chỉ nhảy trực tiếp  Đích của lệnh Jump (j and jal) bất cứ đâu trong đoạn lệnh chương trình op address 6 bits 26 bits  (Pseudo) Địa chỉ đích  = PC31 28 : (address × 4) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 57
  58. 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
  59. Rẽ nhánh xa  Trong trường hợp địa chỉ đích rẽ nhánh quá xa (vượt giá trị độ dời 16-bit), Hợp ngữ sẽ điều chỉnh lại code.  Ví dụ: beq $s0,$s1, L1 ↓ bne $s0,$s1, L2 j L1 L2: BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 59
  60. Tĩm tắt Addressing Mode BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 60
  61. Đồng bộ  Hai bộ xử lý dùng chung 1 vùng bộ nhớ  P1 ghi thơng tin, sau đĩ P2 đọc  Cĩ sự tranh chấp truy cập, nếu P1 & P2 khơng địng bộ với nhau Kết quả khơng xác định được  Hỗ trợ phần cứng yêu cầu  Tác vụ Atomic đọc/ghi bộ nhớ  Khơng cho phép truy cập nào khác, khi xảy ra tác vụ đọc hoặc ghi  Các tác vụ thực hiện chỉ với 1 lệnh  Ví dụ: hốn vị register ↔ memory  BK Hoặc 1 cặp atomic lệnh TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 61
  62. Đồ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
  63. Lệnh giả trong hợp ngữ  Phần lớn lệnh trong hợp ngữ tương đồng 1-1 với lệnh mã máy  Lệnh giả (Pseudo): dễ nhớ, ví dụ move $t0, $t1 → add $t0, $zero, $t1 blt $t0, $t1, L → slt $at, $t0, $t1 bne $at, $zero, L  $at (register 1): assembler temporary BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 63
  64. 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
  65. Tạo Object Module  Assembler (hoặc compiler) biên dịch chương trình ra lệnh máy  Thiết lập các thơng tin để xây dựng 1 chương trình để cĩ thể thực thi, bao gồm  Header: đặc tả nội dung của object module  Text segment: các lệnh đã được biên dịch  Static data segment: dữ liệu được cấp phát cho chương trình trong suốt quá trình tực thi  Relocation info: định vị tuyệt đối của chương trình được nạp vào bộ nhớ  Symbol table: global definitions and external refs BK  Debug info: liên quan đến gỡ rối chương trình TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 65
  66. 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, ngồ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
  67. Nạp một chương trình  Nạp tập tin thực thi trên đĩa vào bộ nhớ 1. Đọc header để xác định dung lượng các đoạn 2. Tạo khơng gian địa chỉ ảo 3. Khởi động dữ liệu trong bộ nhớ 4. Set up arguments on stack 5. Khởi động các thanh ghi (gồm $sp, $fp, $gp) 6. Nhảy tới đầu chương trình  Sao các thơng số vào $a0, và gọi main  Khi kết thúc trở về từ main, do exit syscall BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 67
  68. 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
  69. Kết luận  Các nguyên tắc thiết kế 1. Simplicity favors regularity 2. Smaller is faster 3. Make the common case fast 4. Good design demands good compromises  Các lớp phần mềm/cứng  Biên dịch, Hợp ngữ, Phần cứng  MIPS: là mơ hình đặc thù kiến trúc tập lệnh RISC BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 69
  70. 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