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

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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 28
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 29
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 30
 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ó toán tử NOR với 3 toá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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 31
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 32
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 33
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 34
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 35
 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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 36
 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!
  beq và bne: trường hợp thường xảy ra
  Đó là sự kết hợp tốt
BK
TP.HCM
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 37
 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 = 1
  sltu $t0, $s0, $s1 # không dấu
  +4,294,967,295 > +1 $t0 = 0
BK
TP.HCM
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 38
 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 thanh ghi
 2. Chuyển quyền điều khiển cho thủ tục
 3. Nhậ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 thanh ghi để trả về 
 cho chương trình gọi
 6. Trở về chương trình gọi
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 39
 Ý đồ 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 40
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 41
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 42
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 43
 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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 44
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 45
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 46
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 47
 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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 48
 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 toàn bộ mã ký tự thế giới, cùng với symbols
  UTF-8, UTF-16: variable-length encodings
BK
TP.HCM
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 49
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 50
 Ví dụ: Sao chuỗi (String Copy)
  C code (naï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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 51
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 52
 Hằng 32-bit
  Phần lớn các hằng hạn chế trong 16-bit
  Đáp ứng đủ cho các toá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
lhi $s0, 61 0000 0000 0111 1101 0000 0000 0000 0000
ori $s0, $s0, 2304 0000 0000 0111 1101 0000 1001 0000 0000
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 53
 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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 54
 Đị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
  = PC3128 : (address × 4)
BK
TP.HCM
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 55
 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 4 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 56
 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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 57
 Tóm tắt Addressing Mode
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 58
 Đồ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ụ: hoán vị register ↔ memory
 
BK Hoặc 1 cặp atomic lệnh
TP.HCM
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 59
 Đồ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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 60
 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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 61
 Biên dịch và thực hiện
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 62
 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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 63
 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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 64
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 65
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 66
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 67
 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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 68