CHƯƠNG 5: CẤP MÁY QUI ƯỚC
(CONVENTIONAL MACHINE LEVEL- ARCHITECTURE LEVEL)
CẤP MÁY QUI UỚC
5.1 Ví dụ về cấp máy quy ước
+ Họ 8088, 80286, 80386 ... của Intel
+ Họ 68000, 68020, 68030 ... của Motorola
5.2 Khuôn dạng lệnh
5.3 Định địa chỉ
5.4 Chỉ thị (lệnh)_instruction
5.5 Luồng điều khiển




5.1 Một số ví dụ cấp máy qui ước
5.1.1 Họ 8088/80286/80386 Intel
Một số đặc tính của 8086
Tổ chức bộ nhớ
Các thanh ghi
8088/80286/80386 (xem tài liệu)
Pentium II:
Các thanh ghi quan trọng
So sánh họ Intel và Motorola
Giống nhau: đều có các chỉ thị tương ứng nhau
Có chỉ thị di chuyển dữ liệu.
Có phép toán trên nhị phân, thập phân, boolean
Thao tác dịch, quay.
Khác nhau:
Định địa chỉ.
Các thanh ghi (Moto đơn giản hơn)
Giao tiếp I/O



5.2 Khuôn dạng lệnh
4 dạng khuôn lệnh tiêu biểu:
Zero-address instruction (lệnh không địa chỉ)
One-address instruction (lệnh 1 địa chỉ)
Two-address instruction (lệnh 2 địa chỉ)
Three-address instruction (lệnh 3 địa chỉ)
Một số quan hệ giữa chiều dài của lệnh và chiều dài của từ
5.2.1 Các thiêu chuẩn thiết kế khuôn dạng lệnh
Nhà sản xuất khi thiết kế khuôn dạng lệnh:
A. Lệnh ngắn tốt hơn lệnh dài
Lý do:
a.1 Tiết kiệm về bộ nhớ
5.2.1 Các thiêu chuẩn thiết kế khuôn dạng lệnh (tt)
a.2 Về tốc độ
Mỗi bộ nhớ có tốc độ truyền (đọc, ghi) riêng, được quyết định bởi công nghệ, kỹ thuật thiết kế

Tốc độ truyền của bộ nhớ : T bps, lệnh dài trung bình R bit
---> bộ nhớ phát tối đa T/R lệnh trong một giây.
---> tốc độ bộ xử lý (thực thi bao nhiêu lệnh trong 1 giây) tăng khi chiều dài lệnh ngắn

Chú ý:
- CPU tốc độ thấp (thời gian thực hiện lệnh lớn>thời gian tìm nạp từ bộ nhớ), v/đề trên không quan trọng.
- CPU tốc độ cao (thông thường) (thời gian thực hiện lệnh < thời gian tìm nạp từ bộ nhớ), bộ nhớ gây ra hiệu ứng cổ chai (bottle neck)  v/đề trên rất quan trọng.


5.2.1 Các thiêu chuẩn thiết kế khuôn dạng lệnh (tt)
Chiều dài từ = k*chiều dài ký tự
Ví dụ: Một thiết kế với ký tự 9 bit, chỉ thị 12 bit, và 1 từ là 32 bit sẽ gây ra lãng phí không gian bộ nhớ


Phân tích, chọn lựa số bit trong bus và trường địa chỉ
Ví dụ: Có 2 giải pháp bộ nhớ cho 1 máy tính:
(I): dùng từ 32 bit với 14 đường địa chỉ
(II): dùng từ 8 bit với 16 đường địa chỉ
Giải pháp (II) có chiều dài từ ngắn hơn, nên chiều dài chỉ thị ngắn hơn
=> ít chiếm không gian hơn, thời gian tìm nạp địa chỉ cũng ngắn hơn.
5.2.2 Mở rộng Opcode
Mục đích: phối hợp giữa số bit của opcode và địa chỉ
Xét lệnh dài 16 bit: 4 bit opcode, và 3 địa chỉ 4 bit như h.vẽ
 Phù hợp thiết kế có 16 thanh ghi, địa chỉ thanh ghi là 4 bit
+Cũng lệnh có (n+k) bit: (k-1) bit cho opcode, (n+1) bit cho địa chỉ
giảm còn 1/2 số thao tác, nhưng tăng bộ nhớ gấp 2 hoặc cùng
bộ nhớ nhưng độ phân giải tăng gấp đôi.
+Cũng lệnh có (n+k) bit: (k+1) bit cho opcode, (n-1) bit cho địa chỉ
Tăng gấp đôi số thao tác, nhưng bộ nhớ giảm 1/2 hoặc cùng
bộ nhớ nhưng độ phân giải giảm 1/2.
Xét lệnh có (n+k) bit : k bit opcode và n bit địa chỉ
Cho phép thực hiện 2k thao tác khác nhau và định địa chỉ
được cho 2n ô nhớ.
Một số mở rộng opcode khác
Một mở rộng opcode cho phép
15 lệnh 3-địa chỉ, 14 lệnh 2-địa chỉ,
31 lệnh 1-địa chỉ
16 lệnh 0-địa chỉ.

Trường kí hiệu bởi
xxxx, yyyy, và zzzz là trường địa chỉ 4-bit
Một số ví dụ về các khuôn dạng lệnh
Khuôn dạng lệnh của Pentium II
Khuôn dạng lệnh của SPARC đời đầu
5.3 Định địa chỉ
Định địa chỉ tức thời
Định địa chỉ trực tiếp
Định địa chỉ thanh ghi
Định địa chỉ gián tiếp
Định địa chỉ số
Định địa chỉ stack


5.3.1/ Định địa chỉ tức thời (immediate addressing)


5.3.2/ Định địa chỉ trực tiếp (direct addressing)


Phần địa chỉ của chỉ thị là địa chỉ của toán hạng
Có 2 phương pháp:
+ sử dụng các opcode khác nhau
+ sử dụng kiểu, kí hiệu đặc biệt cho toán hạng
 khắc phục khuyếch điểm của định địa chỉ tức thời
Phần địa chỉ của chỉ thị chứa chính toán hạng
Toán hạng: toán hạng tức thời (immediate operand)
Ưu điểm:
đơn giản, không dùng tham chiếu bộ nhớ để tìm nạp toán hạng
Khuyết điểm:
toán hạng có tầm giá trị bị giới hạn.
5.3.3 Định địa chỉ thanh ghi


5.3.4 Định địa chỉ gián tiếp

Phần địa chỉ của chỉ thị là tên thanh ghi, hay từ nhớ lưu địa chỉ của toán hạng
Ưu điểm: linh động, phù hợp cho việc phát triển cho các lập trình ứng dụng
Phần địa chỉ của chỉ thị là tên thanh ghi, hay từ nhớ còn được gọi là pointer_con trỏ.
Thường có các kí hiệu đặc biệt cho con trỏ
V/dụ: @R0
Phần địa chỉ của chỉ thị là tên thanh ghi lưu toán hạng
Ưu điểm:
+ các thanh ghi nhanh hơn bộ nhớ chính
+ do ít thanh ghi nên cần ít bit để địa chỉ hóa thanh ghi
Tuy nhiên, dẫn đến cần phải chọn lựa, quyết định toán hạng nào lưu trong thanh ghi, toán hạng nào lưu trong bộ nhớ chính
5.3.5 Định địa chỉ số


5.3.6 Định địa chỉ stack
Hoạt động của stack
Stack bao gồm các phần tử dữ liệu được cất theo một trật tự liên tiếp trong bộ nhớ
Phần tử đầu tiên được cất vào stack là đáy của stack
Phần tử gần nhất được cất vào stack là đỉnh của stack
Việc truy xuất dữ liệu trên stack nhờ thanh ghi con trỏ stack (SP)
Sử dụng một thanh ghi chỉ số (index) để hỗ trợ truy xuất 1 ô nhớ
Địa chỉ có 2 thành phần: giá trị của thanh ghi chỉ số và một hằng số
Khi truy xuất một khối các ô nhớ liên tiếp, chỉ cần tăng giá trị thanh ghi chỉ số
Hoạt động của stack
Vấn đề Polish ngược
+ Thông thường, trong toán học: toán tử ở giữa các toán hạng (x+y) (đây là kí hiệu infix)
không phải (xy+) (đây là kí hiệu postfix hay reverse Polish)
+ Polish ngược:
Thuận lợi hơn infix trong biểu diễn công thức:
- bất kỳ công thức nào cũng không cần dùng ( )
- thuận tiện trong đánh giá các công thức trên máy tính với stack
- loại bỏ được rắc rối về mức độ ưu tiên giữa các phép toán (v/d: infix a/b + c)
PHÂN TÍCH:
+ Có nhiều thuận toán biến đổi dạng infix  polish ngược
Xét thuật toán của E.W.Dijkstra
V/d: xét công thức gồm các kí hiệu: biến, toán tử + - * / và ( )
Để đánh dấu điểm kết thúc của công thức, chèn kí hiệu sau kí hiệu cuối cùng và trước kí hiệu đầu tiên
Polish ngược (tt)
Mỗi xe biểu thị một kí hiệu trong công thức được đổi từ dạng infix thành Polish ngược
Mỗi một xe biểu thị 1 ký hiệu
Khi mỗi xe tới chuyển mạch, xe dừng lại và được hỏi xem sẽ đi đến California hay Texas. Xe chứa biến luôn tới California. Còn lại các xe khác phải hỏi nội dung của xe gần nhất trên đường đi Texas trước khi vào chuyển mạch.
Polish ngược (tt)
Bảng quyết định dùng cho giải thuật đổi infix thành Polish ngược
1: xe ở chuyển mạch chuyển hướng về Texas
2: xe gần nhất trên đường đi Texas quẹo trái và tới California
3: xe ở chuyển mạch và xe gần nhất trên đường đi Texas đều bị cướp và biến mất (bị xóa)
4: dừng lại. Lúc này, các kí hiệu (các xe) ở California biểu thị công thức Polish ngược khi đọc từ trái sang phảI.
5: dừng lại. Một lỗi xảy ra. Công thức ban đầu không đươ85c cân đối đúng.
Polish ngược (tt)
Sau mỗi động tác, một so sánh mới được thực hiện giữa:
+ xe ở chuyển mạch (có thể là xe giống như trong so sánh trước hoặc có thể là xe đi tiếp)
+ xe bây giờ là xe cuối cùng trên đường đi Texas.
Quá trình tiếp tục đến khi đạt bước thứ 4.
Polish ngược: phù hợp với stack trong đó:
+ việc dẫn đường một xe tới Texas là thao tác PUSH
+ việc quay 1 xe đã ở trên đường đi Texas và gửi tới California là thao tác POP
So sánh Infix và Polish ngược:
+ trật tự các biến như nhau,
+ trật tự các toán tử khác nhau. Trong Polish ngược, toán tử xuất hiện theo trật tự chúng được thực thi trong thời gian đánh giá biểu thức
V/dụ:
Polish ngược (tt)
Polish ngược phù hợp cấu trúc stack, và do đó có nhiều thuận lợi so với sử dụng thanh ghi (sử dụng thanh ghi có nhiều ưu điểm như đã trình bày):
+ chiều dài chỉ thị ngắn hơn (do có nhiều chỉ thị không địa chỉ)
+ dễ dàng đánh giá các công thức
+ không cần dùng các thuật toán phức tạp để tối ưu hóa thanh ghi
Định địa chỉ trong các trình biên dịch
Các trình biên dịch ngôn ngữ cấp cao thường sử dụng các kiểu định địa chỉ sau:
+ trực tiếp: khi truy xuất các biến tòan cục.
+ tức thời: khi dời chuyển các hằng số
+ thanh ghi: khi lưu trữ các biến cục bộ
+ chỉ số: khi truy xuất các biến cục bộ
+ gián tiếp thanh ghi: khi lưu trử các con trỏ tới cấu trúc.
+ tự động định chỉ số: khi cất, lấy các tham số của thủ tục.
5.4 Các loại chỉ thị
Di chuyển dữ liệu
Thao tác nhị nguyên (dyadic operation): kết hợp hai toán hạng để sinh ra một kết quả
Thao tác đơn nguyên: một tóan hạng, tạo ra một kết quả.
So sánh và nhảy có điều kiện
Gọi thủ tục
Điều khiển vòng lặp
Xuất/nhập
5.5 Luồng điều khiển
Luồng điều khiển  trình tự thực thi các chỉ thị
Thông thường, thực hiện tuần tự các chỉ thị (các chỉ thị lần lượt được tìm nạp từ các vị trí nhớ liên tiếp)
Tuy nhiên, có sự thay đổi luồng điều khiển. do:
+ các chỉ thị gọi thủ tục
+ đồng chương trình (coroutine)
+ các bẫy, ngắt
5.5.1 Luồng điều khiển tuần tự và các chỉ thị nhảy
Sau khi một chỉ thị được thực thi, chỉ thị tiếp theo được tìm nạp và thực hiện. Sau mỗi chỉ thị, bộ đếm chương trình Program Counter được tăng thêm bởi chiều dài chỉ thị. Nếu xem xét, PC quan hệ tăng tuyến tính theo thời gian. (hình a)
Nhưng khi có các chỉ thị nhảy . . .  quan hệ tuyến tính đó bị phá vỡ  người lập trình khó theo dõi quá trình thực thi chỉ thị  dể có lỗi (hình b)
5.5.1 Luồng điều khiển tuần tự và các chỉ thị nhảy (tt)
5.5.2 Thủ tục
kỹ thuật quan trọng
cũng làm thay đổi dòng điều khiển, nhưng khác với lệnh nhảy là sau khi thực hiện xong c.việc, thủ tục trả điều khiển về cho chỉ thị theo sai chỉ thị gọi thủ tục (lệnh nhảy thì không)
Thủ tục đệ qui (recursive procedure)
 thủ tục đệ qui: thủ tục tự gọi chính thủ tục
Xét bài toán tháp Hà Nội
Cấu hình ban đầu của bài toán tháp Hà Nội với 5 đĩa
Luật chơi:
- Chuyển toàn bộ số đĩa ban đầu từ cọc 1 sang cọc 2 hoặc 3.
- Mỗi lần chuyển chỉ chuyển đước 1 đĩa.
- Đĩa ở trên bao giờ cũng nhỏ hơn đĩa ở dưới
7 bước giải bài toán tháp Hà Nội với 3 đĩa
Thủ tục giải bài toán tháp Hà Nội
Nội dung stack
5.5.3 Đồng thủ tục
A: thủ tục gọi, B: thủ tục được gọi
Khi một thủ tục được gọi, việc thực hiện thủ tục luôn bắt đầu ở phát biểu đầu tiên của thủ tục
Đồng thủ tục (tt)
Khi một đồng thủ tục bắt đầu lại (sau khi thực hiện xong thủ tục B), việc thực thi bắt đầu ở chỉ thị ngay vị trí rời trong bỏ lần trước
5.5.4 Bẫy (trap)
Là loại gọi thủ tục tự động, được khởi động bởi một điều kiện nào đó (do chương trình gây ra, ví dụ như phép cộng làm tràn overflow, tràn stack, chia cho 0, opcode không xác định).
Điều kiện khởi động bẫy là do chương trình gây ra, được phần cứng, vi chương trình phát hiện.
Khi xảy ra bẫy, luồng điều khiển được chuyển đến một vị trí nhớ cố định (thay vì theo tuần tự). Tại vị trí đó, có chỉ thị nhảy tới thủ tục là trap handler để thực hiện một động tác thích hợp.
Bẫy tiết kiệm được thời gian và bộ nhớ so với phương pháp kiểm tra, điều khiển bởi người lập trình.
Xét ví dụ:
Phép cộng làm tràn, có thanh ghi 1 bit là cờ nhớ C được set lên 1. Người lập trình có thể kiểm tra cờ nhớ C (v/dụ: lệnh JC rel) và điều khiển  tốn thời gian và bộ nhớ.
Trong khi đó, bẫy được sinh ra và thực hiện tự động.
5.5.5 Ngắt (Interrupt)
Là loại gọi thủ tục tự động, được khởi động bởi một điều kiện nào đó, không phải do chương trình gây ra (khác bẫy) mà do tác động khác (thường là liên quan tới I/O).
Ví dụ: các chân I/O INT0, INT1
 Ngắt: không đồng bộ với chương trình (bẫy: đồng bộ với chương trình)
 Do liên quan đến I/O => ngắt có thể tạo ra sự linh động cho người lập trình và cho các ứng dụng điều khiển.
Câu hỏi ôn tập chương 5
Các loại khuôn dạng lệnh?
Trình bày các tiêu chuẩn khuôn dạng lệnh?
So sánh cách định địa chỉ tức thời, địa chỉ trực tiếp, địa chỉ gián tiếp. Cho ví dụ
Nêu ưu điểm của địa chỉ chỉ số
Sử dụng thuật toán Dijsktra minh họa phép chuyển đổi công thức infix A+BxCxD sang dạng postfix
Nêu các loại luồng điều khiển
Minh họa thủ tục đệ quy bằng bài toán tháp Hà Nội 3 đĩa
Khái niệm về đồng thủ tục?
Thế nào là thủ tục bẫy? Cho ví dụ minh họa.
Có thể thiết kế opcode mở rộng với lệnh dài 12 bit cho tập lệnh sau không? Thanh ghi có địa chỉ 3 bit
4 lệnh với 3 thanh ghi
255 lệnh với 1 thanh ghi
16 lệnh với 0 thanh ghi









Câu hỏi ôn tập chương 5 (tt)

Một máy với 16 bit lệnh, 6 bit địa chỉ. Các lệnh có 1 hoặc 2 địa chỉ. Nếu có n lệnh 2 địa chỉ, thì số lệnh 1 địa chỉ tối đa là bao nhiêu?
Cho các giá trị bộ nhớ dưới đây.
word 20 chứa 40
word 30 chứa 50
word 40 chứa 60
word 50 chứa 70
Giá trị trong thanh ghi ACC là bao nhiêu nếu thực hiện các lệnh sau:
LOAD IMMEDIATE 20
LOAD DIRECT 30
LOAD INDIRECT 20
LOAD IMMEDIATE 30
LOAD DIRECT 30
LOAD INDIRECT 30
Chuyển đổi công thức infix sau sang dạng postfix:
A+B+C+D+E
(A+B)x(C+D)+E
(AxB)+(CxD)+E
(A-B)x(((C-DxE)/F)/G)Xh
Chuyển đổi công thức infix Boolean sau sang dạng Polish ngược
(A AND B) OR C
(A OR B) AND (A OR C)
(A AND B) OR (C AND D)
Tại sao thủ tục ngắt có quy định mức ưu tiên, trong khi thủ tục thông thường không có.