Bài giảng Kiến trúc máy tính và hợp ngữ - Chương 05: Kiến trúc Mips 32 BIT - Lê Quốc Hòa

Nội dung text: Bài giảng Kiến trúc máy tính và hợp ngữ - Chương 05: Kiến trúc Mips 32 BIT - Lê Quốc Hòa

1. • Nhiệm vụ cơ bản nhất của CPU là phải thực hiện các lệnh được yêu cầu, gọi là instruction • Các CPU sẽ sử dụng các tập lệnh (instruction set) khác nhau để có thể giao tiếp với nó 2
2. • Chúng ta sẽ làm quen với tập lệnh cho kiến trúc MIPS (PlayStation 1, 2; PSP; Windows CE, Routers ) • Được xây dựng theo kiến trúc (RISC) với 4 nguyên tắc: – Càng đơn giản, càng ổn định – Càng nhỏ gọn, xử lý càng nhanh – Tăng tốc xử lý cho những trường hợp thường xuyên xảy ra – Thiết kế đòi hỏi sự thỏa hiệp tốt 4
3. .data # data segment str: .asciiz “Hello asm !” .text # text segment .globl main main: # starting point of program addi $v0, $0, 4 # $v0 = 0 + 4 = 4 print str syscall la $a0, str # $a0 = address(str) syscall # excute the system call 6
4. • Như chúng ta đã biết khi lập trình, biến (variable) là khái niệm rất quan trọng khi muốn biểu diễn các toán hạng để tính toán • Trong kiến trúc MIPS không tồn tại khái niệm biến, thay vào đó là thanh ghi toán hạng 8
5. • Save register: – MIPS lấy ra 8 thanh ghi ($16 - $23) dùng để thực hiện các phép tính số học, được đặt tên tương ứng là $s0 - $s7 – Tương ứng trong C, để chứa giá trị biến (variable) • Temporary register: – MIPS lấy ra 8 thanh ghi ($8 - $15) dùng để chứa kết quả trung gian, được đặt tên tương ứng là $t0 - $t7 – Tương ứng trong C, để chứa giá trị biến tạm (temporary variable) 10
6. • Phần 1: Phép toán số học (Arithmetic) • Phần 2: Di chuyển dữ liệu (Data transfer) • Phần 3: Thao tác luận lý (Logical) • Phần 4: Rẽ nhánh (Un/Conditional branch) 12
7. • Giả sử xét câu lệnh sau: add a, b, c – Chỉ thị cho CPU thực hiện phép cộng a  b + c – a, b, c được gọi là thanh ghi toán hạng – Phép toán trên chỉ có thể thực hiện với đúng 3 toán hạng (không nhiều cũng không ít hơn) 14
8. • Toán hạng trong các lệnh trên phải là thanh ghi • Trong MIPS, lệnh thao tác với số nguyên có dấu được biểu diễn dưới dạng bù 2 • Làm sao biết 1 phép toán được biên dịch từ C (ví dụ a = b + c) là thao tác có dấu hay không dấu? Dựa vào trình biên dịch • Có thể dùng 1 toán hạng vừa là nguồn vừa là đích add $s0, $s0, $s1 • Cộng, trừ với hằng số? $s2 sẽ đóng vai trò là hằng số – Cộng: addi $s0, $s1, 3 (addi = add immediate) – Trừ: addi $s0, $s1, -3 16
9. • Chuyển thành lệnh MIPS từ lệnh C: f = (g + h) – (i + j) • Chia nhỏ thành nhiều lệnh MIPS: add $t0, $s1, $s2 # temp1 = g + h add $t1, $s3, $s4 # temp2 = i + j sub $s0, $t0, $t1 # f = temp1 – temp2 18
10. • Thao tác nhân / chia của MIPS có kết quả chứa trong cặp 2 thanh ghi tên là $hi và $lo Bit 0-31 thuộc $lo và 32-63 thuộc $hi 20
11. • Cú pháp: div $s0, $s1 • Kết quả (64 bit) chứa trong 2 thanh ghi – $lo (32 bit) = $s0 / $s1 (thương) – $hi (32 bit) = $s0 % $s1 (số dư) 22
12. • Kết quả phép tính vượt qua miền giá trị cho phép Tràn số xảy ra • Một số ngôn ngữ có khả năng phát hiện tràn số (Ada), một số không (C) • MIPS cung cấp 2 loại lệnh số học: – add, addi, sub: Phát hiện tràn số – addu, addiu, subu: Không phát hiện tràn số • Trình biên dịch sẽ lựa chọn các lệnh số học tương ứng – Trình biên dịch C trên kiến trúc MIPS sử dụng addu, addiu, subu 24
13. • Cú pháp: opt opr, opr1 (opr2) – opt (operator): Tên thao tác (Load / Save) – opr (operand): Thanh ghi lưu từ nhớ (word) – opr1 (operand 1): Hằng số nguyên – opr2 (operand 2): Thanh ghi chứa địa chỉ vùng nhớ cơ sở (địa chỉ nền) 28
14. • $s0 được gọi là thanh ghi cơ sở (base register) thường dùng để lưu địa chỉ bắt đầu của mảng / cấu trúc • 12 gọi là độ dời (offset) thường dùng để truy cập các phần tử mảng hay cấu trúc 30
15. • Số biến cần dùng của chương trình nếu nhiều hơn số thanh ghi của CPU? • Giải pháp: – Thanh ghi chỉ chứa các biến đang xử lý hiện hành và các biến thường sử dụng – Kỹ thuật spilling register 32
16. • Hãy chuyển thành mã hợp ngữ MIPS: A[12] = h - A[8] • Trả lời: lw $t0, 32($s3) # Chứa A[8] vào $t0 sub $t0, $s2, $t0 sw $t0, 48($s3) # Kết quả vào A[12] 34
17.  MIPS lưu dữ liệu trong bộ nhớ theo nguyên tắc Alignment Restriction  Các đối tượng lưu trong bộ nhớ (từ nhớ) phải bắt đầu tại địa chỉ là bội số của kích thước đối tượng  Mà mỗi từ nhớ có kích thước là 32 bit = 4 byte = kích thước lưu trữ của 1 thanh ghi trong CPU Như vậy, từ nhớ phải bắt đầu tại địa chỉ là bội số của 4 36
18. • Để truy xuất vào 1 từ nhớ sau 1 từ nhớ thì cần tăng 1 lượng 4 byte chứ không phải 1 byte • Do đó luôn nhớ rằng các lệnh lw và sw thì độ dời (offset) phải là bội số của 4 • Tuy nhiên bộ nhớ các máy tính cá nhân ngày nay lại được đánh địa chỉ theo từng byte (8 bit) 38
19. • Giả sử nạp 1 byte có giá trị xzzz zzzz vào thanh ghi trên CPU (x: bit dấu của byte đó) • Giá trị thanh ghi trên CPU (32 bit) sau khi nạp có dạng: xxxx xxxx xxxx xxxx xxxx xxxx xzzz zzzz Tất cả các bit từ phải sang sẽ có giá trị = bit dấu của giá trị 1 byte vừa nạp (sign-extended) Nếu muốn các bit còn lại từ phải sang có giá trị không theo bit dấu (=0) thì dùng lệnh: lbu (load byte unsigned) 40
20. • Chúng ta đã xem xét các thao tác số học (+, -, *, /) – Dữ liệu trên thanh ghi như 1 giá trị đơn (số nguyên có dấu / không dấu) • Cần thao tác trên từng bit của dữ liệu Thao tác luận lý – Các thao tác luận lý xem dữ liệu trong thanh ghi là dãy 32 bit riêng lẻ thay vì 1 giá trị đơn • Có 2 loại thao tác luận lý: – Phép toán luận lý – Phép dịch luận lý 42
21. • MIPS hỗ trợ 2 nhóm lệnh cho các phép toán luận lý trên bit: – and, or, nor: Toán hạng nguồn thứ 2 (opr2) phải là thanh ghi – andi, ori: Toán hạng nguồn thứ 2 (opr2) là hằng số • Lưu ý: MIPS không hỗ trợ lệnh cho các phép luận lý NOT, XOR, NAND • Lý do: Vì với 3 phép toán luận lý and, or, nor ta có thể tạo ra tất cả các phép luận lý khác Tiết kiệm thiết kế cổng mạch • Ví dụ: not (A) = not (A or 0) = A nor 0 44
22. • MIPS hỗ trợ 2 nhóm lệnh cho các phép dịch luận lý trên bit: – Dịch luận lý • Dịch trái (sll – shift left logical): Thêm vào các bit 0 bên phải • Dịch phải (srl – shift right logical): Thêm vào các bit 0 bên trái – Dịch số học • Không có dịch trái số học • Dịch phải (sra – shift right arithmetic): Thêm các bit = giá trị bit dấu bên trái 46
23. • Tương tự lệnh if trong C: Có 2 loại – if (condition) clause – if (condition) clause1 else clause2 • Lệnh if thứ 2 có thể diễn giải như sau: if (condition) goto L1 // if Làm clause1 clause2 // else Làm clause2 goto L2 // Làm tiếp các lệnh khác L1: clause1 L2: 48
24. • Biên dịch câu lệnh sau trong C thành lệnh hợp ngữ MIPS: if (i == j) f = g + h; else f = g – h; • Ánh xạ biến f, g, h, i, j tương ứng vào các thanh ghi: $s0, $s1, $s2, $s3, $s4 • Lệnh hợp ngữ MIPS: beq $s3, $s4, TrueCase # branch (i == j) FalseCase: sub $s0, $s1, $s2 # f = g – h (false) j Final # goto “Final” label TrueCase: add $s0, $s1, $s2 # f = g + h (true) Final: 50
25. • Ánh xạ biến vào các thanh ghi như sau: g h i j base address of A $s1 $s2 $s3 $s4 $s5 • Trong ví dụ trên có thể viết lại thành lệnh MIPS như sau: Loop: sll $t1, $s3, 2 # $t1 = i * 22 add $t1, $t1, $s5 # $t1 = addr A[i] lw $t1, 0 ($t1) # $t1 = A[i] add $s1, $s1, $t1 # g = g + A[i] add $s3, $s3, $s4 # i = i + j bne $s3, $s2, Loop # if (i != j) goto Label 52
26. • beq và bne được sử dùng để so sánh bằng (== và != trong C) Muốn so sánh lớn hơn hay nhỏ hơn? • MIPS hỗ trợ lệnh so sánh không bằng: – slt opr1, opr2, opr3 – slt: Set on Less Than – if (opr2 < opr3) opr1 = 1; else opr1 = 0; 54
27. • Các phép so sánh còn lại như >, ≥, ≤ thì sao? • MIPS không trực tiếp hỗ trợ cho các phép so sánh trên, tuy nhiên dựa vào các lệnh slt, bne, beq ta hoàn toàn có thể biểu diễn chúng! 56
28. • So sánh == Dùng lệnh beq • So sánh != Dùng lệnh bne • So sánh Dùng cặp lệnh (slt bne) • So sánh ≤ và ≥ Dùng cặp lệnh (slt beq) 58
29. • switch (k) { case 0: f = i + j; break; case 1: f = g + h; break; case 2: f = g - h; break; } • Ta có thể viết lại thành các lệnh if lồng nhau: if (k == 0) f = i + j; else if (k == 1) f = g + h; else if (k == 2) f = g – h; • Ánh xạ giá trị biến vào các thanh ghi: f g h i j k $s0 $s1 $s2 $s3 $s4 $s5 60
30. • Hàm (fucntion) trong C (Biên dịch) Trình con (Thủ tục) trong hợp ngữ • Giả sử trong C, ta viết như sau: void main() { int a, b; sum(a, b); • Hàm được chuyển thành lệnh hợp ngữ như thế nào ? } • Dữ liệu được lưu trữ ra sao ? int sum(int x, int y) { return (x + y); } 62
31. • MIPS hỗ trợ 1 số thanh ghi để lưu trữ dữ liệu cho thủ tục: – Đối số input (argument input): $a0 $a1 $a2 $a3 – Kết quả trả về (return ): $v0 $v1 – Biến cục bộ trong thủ tục: $s0 $s1 $s7 – Địa chỉ quay về (return address): $ra • Nếu có nhu cầu lưu nhiều dữ liệu (đối số, kết quả trả về, biến cục bộ) hơn số lượng thanh ghi kể trên? Bao nhiêu thanh ghi là đủ ? Sử dụng ngăn xếp (stack) 64
32. C sum (a, b); /* a: $s0, b: $s1 */ [Làm tiếp thao tác khác ] } 66 NHẬN XÉT 2 int sum (int x, int y) { return x + y; } M Địa chỉ Lệnh I 1000 add $a0, $s0, $zero # x = a • Thay vì dùng 2 lệnh để lưu địa chỉ quay về vào P 1004 add $a1, $s1, $zero # y =thanh b ghi $ra và nhảy đến thủ tục “sum”: S 1008 addi $ra, $zero, 1016 # lưu 1008địa chỉ addi lát sau$ra, quay$zero, về 1016 vào $ #ra $ ra= 1016= 1016 1012 j sum # goto sum 1012 j sum # nhảy đến nhãn sum MIPS hỗ trợ lệnh mới: jal (jump and link) để thực 1016 [Làm tiếp thao tác khác ] hiện 2 công việc trên: . 1008 jal sum # $ra = 1012, goto sum 2000 sum: add $v0, $a0, $a1 Tại sao# thực không hiện cần thủ xác tục định “sum” tường minh địa chỉ quay về trong $ra ? 2024 jr $ra # nhảy tới địa chỉ trong $ra 66
33. • Chuyển đoạn chương trình sau thành mã hợp ngữ MIPS: void main() int mult (int mcand, int mlier) { { int i, j, k, m; int product = 0; while (mlier > 0) { i = mult (j, k); product = product + mcand; m = mult (i, i); mlier = mlier – 1; } } return product; } 68
34. • Là ngăn xếp gồm nhiều ô nhớ kết hợp (vùng nhớ) nằm trong bộ nhớ chính • Cấu trúc dữ liệu lý tưởng để chứa tạm các giá trị trong thanh ghi – Thường chứa địa chỉ trả về, các biến cục bộ của trình con, nhất là các biến có cấu trúc (array, list ) không chứa vừa trong các thanh ghi trong CPU • Được định vị và quản lý bởi stack pointer • Có 2 tác vụ hoạt động cơ bản: – push: Đưa dữ liệu từ thanh ghi vào stack – pop: Lấy dữ liệu từ stack chép vào thanh ghi • Trong MIPS dành sẵn 1 thanh ghi $sp để lưu trữ stack pointer • Để sử dụng Stack, cần khai báo kích thước vùng Stack bằng cách tăng (push) giá trị con trỏ ngăn xếp stack pointer (lưu trữ trong thanh ghi $sp) – Lưu ý: Stack pointer tăng theo chiều giảm địa chỉ 70
35. • Khởi tạo stack (init) • Lưu trữ tạm các dữ liệu cần thiết vào stack (push) • Gán các đối số (nếu có) • Gọi lệnh jal để nhảy đến các thủ tục con • Khôi phục các dữ liệu đã lưu tạm từ stack (pop) • Khôi phục bộ nhớ, kết thúc stack (free) 72
36. • Nhảy đến thủ tục bằng lệnh jal và quay về nơi trước đó đã gọi nó bằng lệnh jr $ra • 4 thanh ghi chứa đối số của thủ tục: $a0, $a1, $a2, $a3 • Kết quả trả về của thủ tục chứa trong thanh ghi $v0 (và $v1 nếu cần) • Phải tuân theo nguyên tắc sử dụng các thanh ghi (register conventions) 74
37. • $ra: (Có thể thay đổi) Khi gọi lệnh “jal” sẽ làm thay đổi giá trị thanh ghi này. Thủ tục gọi (caller) lưu lại (backup) giá trị của thanh ghi $ra vào stack nếu cần • $v0 - $v1: (Có thể thay đổi) Chứa kết quả trả về của thủ tục • $a0 - $a1: (Có thể thay đổi) Chứa đối số của thủ tục • $t0 - $t9: (Có thể thay đổi) Đây là các thanh ghi tạm nên có thể bị thay đổi bất cứ lúc nào 76
38. .data # data segment str: .asciiz “Hello asm !” .text # text segment .globl main main: # starting point of program addi $v0, $0, 4 # $v0 = 0 + 4 = 4 print str syscall la $a0, str # $a0 = address(str) syscall # excute the system call 80
39. $0 0 $zero $1 $at Reserved for assembler use $2 $v0 $3 $v1 Procedure results $4 $a0 $5 $a1 Procedure Saved $6 $a2 arguments $7 $a3 $8 $t0 $9 $t1 $10 $t2 $11 $t3 Temporary $12 $t4 values $13 $t5 $14 $t6 $15 $t7 $16 $s0 $17 $s1 $18 $s2 Saved $19 $s3 across Operands $20 $s4 procedure $21 $s5 calls $22 $s6 $23 $s7 $24 $t8 More $25 $t9 temporaries $26 $k0 $27 $k1 Reserved for OS (kernel) $28 $gp Global pointer $29 $sp Stack pointer Saved $30 $fp Frame pointer $31 $ra Return address 82
40. • “Lệnh giả”: Mặc định không được hỗ trợ bởi MIPS • Là những lệnh cần phải biên dịch thành rất nhiều câu lệnh thật trước khi được thực hiện bởi phần cứng Lệnh giả = Thủ tục • Dùng để hỗ trợ lập trình viên thao tác nhanh chóng với những thao tác phức tạp gồm nhiều bước 84
41. Name instruction syntax meaning Move move rd, rs rd = rs Load Address la rd, rs rd = address (rs) Load Immediate li rd, imm rd = 32 bit Immediate value Branch greater than bgt rs, rt, Label if(R[rs]>R[rt]) PC=Label Branch less than blt rs, rt, Label if(R[rs] =R[rt]) PC=Label branch less than or equal ble rs, rt, Label if(R[rs] 0) PC=Label 86
42. • Có 3 format lệnh trong MIPS: – R-format: Dùng trong các lệnh tính toán số học (add, sub, and, or, nor, sll, srl, sra ) – I-format: Dùng trong các lệnh thao tác với hằng số, chuyển dữ liệu với bộ nhớ, rẽ nhánh – J-format: Dùng trong các lệnh nhảy (jump – C: goto) 88
43. • Các trường lưu địa chỉ thanh ghi rs, rt, rd có kích thước 5 bit Có khả năng biểu diễn các số từ 0 đến 31 Đủ để biểu diễn 32 thanh ghi của MIPS • Trường lưu số bit cần dịch shamt có kích thước 5 bit Có khả năng biểu diễn các số từ 0 đến 31 Đủ để dịch hết 32 bit lưu trữ của 1 thanh ghi 90
44. • Biểu diễn machine code của lệnh: sll $t2, $s0, 4 • Biểu diễn lệnh với R-format theo từng trường: opcode rs rt rd shmat funct 0 0 16 10 4 0 000000 00000 10000 01010 00100 000000 • opcode = 0 Xác định thao tác dịch trái luận lý • funct = 0 (tất cả các lệnh theo cấu trúc R-format đều có opcode = 0) • rs = 0 (không dùng trong phép dịch) • rt = 16 (toán hạng nguồn là $s0 ~ $16) • rd = 10 (toán hạng đích là $t2 ~ $10) • shmat = 4 (số bit dịch = 4) 92
45. 6 bits 5 5 16 opcode rs rt immediate  opcode (operation code): mã thao tác, cho biết lệnh làm gì (tương tự opcode của R-format, chỉ khác không cần thêm trường funct)  Đây cũng là lý do tại sao R-format có 2 trường 6 bit để xác định lệnh làm gì thay vì 1 trường 12 bit Để nhất quán với các cấu trúc lệnh khác (I-format) trong khi kích thước mỗi trường vẫn hợp lý  rs (source register): thanh ghi nguồn, thường chứa toán hạng nguồn thứ 1  rt (target register): thanh ghi đích, thường chứa kết quả lệnh  immediate: 16 bit, có thể biểu diễn số nguyên từ -215 đến (215 – 1)  I-format đã có thể lưu hằng số 16 bit (thay vì 5 bit như R-format) 94
46. • Trường hằng số (immediate) có kích thước 16 bit • Nếu muốn thao tác với các hằng số 32 bit? Tăng kích thước trường immediate thành 32 bit? Tăng kích thước các lệnh thao tác với hằng số có cấu trúc I-format Phá vỡ cấu trúc lệnh 32 bit của MIPS 96
47. • Muốn gán giá trị 32 bit 0xABABCDCD vào thanh ghi $t0 ? – Không thể dùng: addi $t0, $t0, 0xABABCDCD – Giải pháp dùng lệnh lui: lui $t1, 0xABAB ori $t1, $t1, 0xCDCD add $t0, $0, $t1 98
48. • Trong MIPS, thanh ghi PC (Program Counter) sẽ chứa địa chỉ của lệnh đang được thực hiện • immediate: số có dấu, chứa khoảng cách so với địa chỉ lệnh đang thực hiện nằm trong thanh ghi PC – immediate + PC địa chỉ cần nhảy tới • Cách xác định địa chỉ này gọi là PC-Relative Addressing (định vị theo thanh ghi PC) – Xem slide “Addressing Mode” (phần sau) để biết thêm về các Addressing mode trong MIPS 100
49. • Cách tính địa chỉ rẽ nhánh: – Nếu không rẽ nhánh: PC = PC + 4 = địa chỉ lệnh kế tiếp trong bộ nhớ – Nếu thực hiện rẽ nhánh: PC = (PC + 4) + (immediate * 4) • Vì sao cộng immediate với (PC + 4) thay vì PC? Khi rẽ nhánh bị delayed 1 lệnh kề với lệnh rẽ nhánh • Nhận xét: immediate cho biết số lệnh cần nhảy qua để đến được nhãn 102
50. • Mỗi lệnh trong MIPS có kích thước 32 bit • Mong muốn: Có thể nhảy đến bất kỳ lệnh nào (MIPS hỗ trợ các hàm nhảy không điều kiện như j) Nhảy trong khoảng 232 (4 GB) bộ nhớ I-format bị hạn chế giới hạn vùng nhảy Dùng J-format • Tuy nhiên, dù format nào cũng phải cần tối thiểu 6 bit cho opcode để nhất quán lệnh với các format khác J-format chỉ có thể dùng 32 – 6 = 26 bit để biểu diễn khoảng cách nhảy 104
51. • Trong J-format, các lệnh nhảy có thể nhảy tới các lệnh có địa chỉ trong khoảng 226 • Muốn nhảy tới các lệnh có địa chỉ lớn hơn từ 227 đến 232 ? – MIPS hỗ trợ lệnh jr (đọc trong phần thủ tục) – Tuy nhiên nhu cầu này không cần thiết lắm vì chương trình thường không quá lớn như vậy 106
52. • Là phương thức xác định vị trí (địa chỉ hóa) các toán hạng trong kiến trúc MIPS • Có 5 phương pháp chính: – Immediate addressing (Vd: addi $t0, $t0, 5) Toán hạng = hằng số 16 bit trong câu lệnh – Register addressing (Vd: add $t0, $t0, $t1) Toán hạng = nội dung thanh ghi – Base addressing (Vd: lw $t1, 8($t0) ) Toán hạng = nội dung ô nhớ (địa chỉ ô nhớ = nội dung thanh ghi + hằng số 16 bit trong câu lệnh) – PC-relative addressing (Vd: beq $t0, $t1, Label) Toán hạng = địa chỉ đích lệnh nhảy = nội dung thanh ghi PC + hằng số 16 bit trong câu lệnh – Pseudodirect addressing (Vd: j 2500) Toán hạng = địa chỉ đích lệnh nhảy = các bit cao thanh ghi PC + hằng số 26 bit trong câu lệnh 108
53. • Sách Petterson & Hennessy: Đọc hết chương 2 • Tài liệu tham khảo: Đọc “08_HP_AppA.pdf” 110