ĐẠI HỌC QUỐC GIA TP.HỒ CHÍ MINH 
TRƯỜNG ĐẠI HỌC BÁCH KHOA 
@ & ? 

NGUYỄN THANH TÙNG 

GIẢI THUẬT ĐỊNH THỜI Mà
CHO KIẾN TRÚC PIPELINE 
Chun ngành: Khoa học máy tính 

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 12 năm 2008


1 

Giới thiệu 

Bộ xử lý của máy tính là bộ não của máy tính, chúng ta muốn máy tính làm 
những  cơng  việc  nào đó  mà  chúng  ta  cần  thì  chúng ta  phải  ra  lệnh  cho  máy  tính. 
Việc ra lệnh cho máy tính thực hiện theo các u cầu của chúng ta thơng qua việc 
lập trình. Bộ xử lý của các máy tính chỉ hiểu được các lệnh máy, hay cịn được gọi 
là ngơn ngữ máy, do đó những lập trình viên muốn lập trình trên các bộ xử lý này sẽ 
gặp rất nhiều khó khăn vì ngơn ngữ máy khơng gần với những ngơn ngữ tự nhiên. 
Để bộ xử lý của máy  tính có thể hiểu được những chương trình được viết ở ngơn 
ngữ lập trình cấp cao (là những ngơn ngữ gần với ngơn ngữ tự nhiên) cần phải có 
một  chương  trình  chuyển  đổi  ngôn  ngữ  cấp  cao  thành  ngôn  ngữ  máy,  đó  là  trình 
biên dịch. 
Trình biên dịch là phần mềm quan trọng, nó dùng để chuyển một ngơn ngữ 
lập trình cấp cao thành một ngơn ngữ lập trình cấp thấp hơn, giúp cho lập trình viên 

viết  chương  trình  trên  các  ngơn  ngữ  gần  với  các  ngơn  ngữ  trong  cuộc  sống  đời 
thường mà máy tính vẫn có thể hiểu được. Trình biên dịch thực hiện cơng việc đọc 
một  chương  trình  nguồn  ở  dạng  ngơn  ngữ  cấp  cao  và  dịch  nó  sang  chương  trình 
đích là ngơn ngữ máy tương ứng với bộ xử lý của máy tính được sử dụng. 
Trình biên dịch tốt là trình biên dịch sinh ra mã đối tượng tốt. Nếu trình biên 
dịch sinh ra mã đối tượng tốt thì chương trình sẽ thực thi nhanh hơn. Sinh mã đối 
tượng nằm ở giai đoạn cuối của trình biên dịch. Vấn đề sinh mã tối ưu trong trình 
biên dịch là khơng thể thực hiện được về mặt lý thuyết tổng qt, song trong thực tế 
ta có thể lựa chọn các kỹ thuật cụ thể để tạo ra được các mã đối tượng tốt mà khơng 
cần  phải  là mã  tối  ưu.  Trong q  trình  sinh  mã  đối  tượng, để  tạo  ra được  mã đối 
tượng tốt người ta phải thực hiện nhiều cơng đoạn và một trong những cơng đoạn 
đó là định thời mã đối tượng.


2 

Định thời mã đối tượng là cơng việc quan trọng và cần thiết trong giai đoạn 
sinh mã đối tượng của trình biên dịch. Bởi vì ngơn ngữ máy phụ thuộc vào kiến trúc 
của bộ xử lý, do đó vấn đề cần thiết là phải xây dựng một trình biên dịch phát sinh 
mã đối tượng phù hợp với kiến trúc bộ xử lý đó. Vì vậy cơng việc hốn đổi các câu 
lệnh của ngơn ngữ máy, sao cho tận dụng được những ưu điểm của bộ xử lý là cần 
thiết nhằm tăng tốc độ thực hiện của chương trình. Trong những máy tính hiện đại 
ngày nay, các bộ xử lý thường được sử dụng kiến trúc Pipeline tuyến tính. 
Việc  xây  dựng  một  trình  biên  dịch  để  tận  dụng  ưu  điểm  của  kiến  trúc 
Pipeline tuyến tính nhằm tăng tốc độ thực thi của chương trình là cần thiết. Bộ xử lý 
Pipeline tuyến tính  là một dãy các bước xử lý, các bước này  kết nối tuyến tính để 
thực  hiện một  chức  năng  cố  định  trên  một dòng  dữ  liệu  theo  từng  bước  một.  Để 
trình biên dịch sinh ra mã tốt thì trong q trình sinh mã đối tượng ta cần thực hiện 
cơng  việc  định  thời  mã  đối  tượng,  sao  cho  giảm  thiểu  được  càng  nhiều  interlock 
càng tốt (nghĩa là giảm thiểu các bước trì hỗn. Các bước trì hỗn của câu lệnh sinh 

ra vì phải đợi các kết quả của các câu lệnh trước đó). 
Để  định  thời  mã,  người  ta  thường  chia  quá  trình  định  thời  mã  cho  một 
chương  trình  thành  hai  giai  đoạn.  Giai  đoạn  một  là  phân  rã  chương  trình  thành 
những khối cơ bản và giai đoạn hai là thực hiện định thời lệnh trên khối cơ bản đó. 
Khối  cơ bản là một dãy  những câu  lệnh  liên tiếp, dãy  các  câu  lệnh này  có  những 
dịng điều khiển đi vào tại vị trí bắt đầu và những dịng điều khiển đi ra tại vị trí kết 
thúc,  những  dịng  điều  khiển  này  khơng  bị  gián  đoạn  hoặc  có  thể  chấp  nhận  rẽ 
nhánh tại vị trí cuối. 
Đề  tài  này  đã  đưa  ra  giải  thuật  List_cycle_scheduling  thực  hiện  việc  định 
thời mã  cho một khối cơ bản. Giải thuật List_cycle_scheduling được cài đặt trong 
Trimaran­3.7. Kết quả thử nghiệm  của giải thuật List_cycle_scheduling  cho ra kết 
quả  là:  Tổng  số  chu  kỳ  thực  hiện  của  chương  trình  hiện  thực  bằng  giải  thuật 
List_cycle_scheduling  so  với  các  giải  thuật  do  Trimaran  cài  đặt  (như  giải  thuật 
Cycle_scheduling, Oper_scheduling, List_bt_scheduling) là gần bằng nhau và Thời


3 

gian thực thi của giải thuật List_cycle_scheduling có những kết quả tốt hơn các giải 
thuật đó. 
Nội dung đề tài gồm năm chương. 
Chương 1: Một vài khái niệm cơ bản. Chương này nêu các khái niệm có liên 
quan đến nội dung của những giải thuật nêu ra trong đề tài. 
Chương 2: Một vài giải thuật định thời cục bộ. Chương này nêu ra một vài 
giải thuật định thời mã làm cơ sở để đưa ra giải thuật List_cycle_scheduling. 
Chương 3: Giải thuật List_cycle_scheduling. Trong chương này đưa ra giải 
thuật List_cycle_scheduling, ví dụ minh họa cho giải thuật này và phân tích độ phức 
tạp của giải thuật. 
Chương 4: Kết quả thử nghiệm của giài thuật List_cycle_scheduling. Trong 
chương này giới thiệu cơng cụ để hiện thực cho giải thuật này là Trimaran. Đưa ra 

các mẫu dữ liệu dùng để thử nghiệm cho giải thuật, Tổng số chu kỳ thực hiện trên 
các mẫu này và Thời gian thực thi của các giải thuật khi áp dụng cho các mẫu dữ 
liệu. So sánh kết quả của giải thuật List_cycle_scheduling với các giải thuật khác. 
Chương 5: Kết luận. Tổng kết các kết quả đạt được của đề tài và định hướng 
phát triển của đề tài.


PHỤ LỤC 

Giới thiệu ..................................................................................... 1 
Chương 1.  Một vài khái niệm cơ bản  .......................................................... 4 
1)  Kiến trúc pipeline.................................................................... 4 
2)  Sự phụ thuộc giữa các câu lệnh  .............................................. 9 
3)  DDAG (The Dependency Directed Acyclic Graph)  ................ 10 
4)  Khối cơ bản (Basic block)....................................................... 12 
Chương 2.  Một vài giải thuật định thời cục bộ  ............................................ 14 
1)  Giải thuật DLS (Delayed­Load Scheduling algorithm) ........... 14 
2)  Giải thuật CSP (Code Scheduling for Pipelined processors): .. 21 
3)  Giải thuật ICS (Integrated Code Scheduling) .......................... 25 
4)  Giải thuật List_scheduling:  .................................................... 30 
5)  Giải thuật Cycle_scheduling:  ................................................. 33 
6)  Giải thuật Oper_scheduling: ................................................... 37 
7)  Giải thuật List_BT_scheduling: .............................................. 41 

Chương 3.  Giải thuật List_cycle_scheduling ............................................... 47 
1)  Đặt vấn đề .............................................................................. 47 
2)  Nội dung giải thuật ................................................................. 49 
3)  Ví dụ ...................................................................................... 53 
4)  Phân tích độ phức tạp của giải thuật  ....................................... 59



Chương 4.  Kết quả thử nghiệm của giải thuật List_cycle_scheduling .......... 61 
1)  Giới thiệu Trimaran ................................................................ 61 
2)  Hiện thực giải thuật List_cycle_scheduling  ............................ 63 
3)  Tổng số chu kỳ thực hiện  ....................................................... 64 
4)  Thời gian thực thi ................................................................... 65 
5)  Kết luận kết quả thử nghiệm ................................................... 69 

Chương 5.  Kết luận ..................................................................................... 70


1 

Tóm tắt 

Hiện nay, các bộ xử lý của máy tính thường sử dụng kiến trúc Pipeline nên 
việc xây dựng một trình biên dịch để tận dụng ưu điểm của kiến trúc Pipeline nhằm 
tăng tốc độ thực thi của chương trình là cần thiết. Định thời mã đối tượng là cơng 
việc quan trọng và cần thiết trong giai đoạn sinh mã đối tượng của trình biên dịch. 
Định thời mã thực hiện cơng việc định thời điểm thực thi của câu lệnh và hốn đổi 
các câu lệnh của ngơn ngữ máy, sao cho ý nghĩa của chương trình khơng thay đổi 
và làm tăng tốc độ thực hiện của chương trình. Định thời mã đối tượng có hai loại 
là: Định thời tồn cục và Định thời cục bộ. Đề tài này đã tìm hiểu một vài giải thuật 
định thời cục bộ và đưa ra giải thuật List_cycle_scheduling thực hiện việc định thời 
cục bộ cho một khối cơ bản.


4 

Chương 1 


Một vài khái niệm cơ bản 

Trong chương này nêu ra một vài khái niệm sẽ được sử dụng khi trình bày 
các  giải  thuật  định  thời  lệnh  cho  kiến  trúc  Pipeline.  Mục  đích  của  việc  định  thời 
lệnh là thay đổi trật tự của những câu lệnh và xác định thời điểm bắt đầu thực hiện 
câu lệnh, sao cho chúng có thể thực thi nhanh nhất nếu có thể và phù hợp với kiến 
trúc máy đích. Chương này trình bày các khái niệm như sau: Kiến trúc Pipeline, Sự 
phụ thuộc giữa các câu lệnh, Khối lệnh cơ bản, và đồ thị DDAG. 

1) 

Kiến trúc Pipeline: 

Bộ  xử  lý  Pipeline  tuyến  tính  (Linear  Pipeline  Processors)  là  một  dãy  các 
bước xử lý, các bước này kết nối tuyến tính để thực hiện một chức năng cố định trên 
một dịng dữ liệu theo từng bước một. Trong những máy tính hiện đại ngày nay thì 
Pipeline  tuyến  tính  được  cài  đặt  cho  việc  thực  thi  lệnh,  tính  tốn  số  học,  và  hoạt 
động truy cập bộ nhớ [KH93]. 
Một bộ xử lý Pipeline tuyến tính được xây dựng với k bước xử lý. Dữ liệu ở 
bên ngồi đi vào Pipeline tại bước đầu tiên S 1 . Kết quả xử lý được đưa từ bước S i 
đến bước Si+1, với i=1, 2, …, k­1. Kết quả cuối cùng được đưa ra khỏi Pipeline tại 
bước cuối cùng S k . 
Một dịng những câu lệnh có thể thực thi trên Pipeline theo kiểu Overlap (các 
lệnh  gối  lên  nhau).  Ví  dụ  như  những  Pipeline  lệnh  cho  những  bộ  xử  lý  CISC  và 
RISC. 
Việc thực thi lệnh là một dãy các hoạt động, bao gồm: bước đọc lệnh (fetch 
stage:  F),  bước  giải  mã  lệnh  (decode stage:  D),  bước  chiếm giữ  tài  nguyên  (issue



5 

stage: I), bước thực thi lệnh (execute stage: E), bước ghi kết quả (writeback stage: 
W).
·  Bước đọc lệnh : là đọc lệnh từ bộ nhớ.
·  Bước giải mã lệnh: giải mã lệnh để thực hiện và nhận diện những tài 
nguyên cần thiết. Những tài nguyên này bao gồm: các thanh ghi, các 
bus, và những đơn vị chức năng.
·  Bước  chiếm  giữ tài nguyên: Giữ  trước  những  tài nguyên  (thanh  ghi, 
bộ  nhớ,…).  Pipeline  điều  khiển  những  Interlock  thì  được  duy  trì  tại 
bước này. Những dữ liệu vào từ bên ngồi thì cũng được đọc từ những 
thanh ghi trong khoảng thời gian này.
·  Bước  thực  thi  lệnh:  Thực  thi  lệnh  có  một  hoặc  nhiều  Bước  thực  thi 
lệnh. Ví dụ như ở hình 1.1.1 thì có ba Bước thực thi lệnh.
·  Bước ghi kết quả: Ghi kết quả thực hiện lệnh vào những thanh ghi. 
Ví dụ: Một Pipeline lệnh  được mơ tả như sau: (có bảy bước) 

Fetch 

Decode 

Issue 

Execute 

Execute 

Execute 

Writeback 


F 

D 

I 

E 

E 

E

W 

(Hình 1.1.1: Một Pipeline lệnh có bảy bước) 
Ví  dụ  như  ta  có  các  câu  lệnh  trong  ngơn  ngữ  cấp  cao  như  sau:  X=Y+Z; 
A=B*C; Ta viết lại các câu lệnh trên bằng ngơn ngữ cấp thấp như ở hình 1.1.2. 
Các  câu  lệnh  của  đoạn  chương  trình  trên  sẽ  được  thực  thi  trên  cấu  trúc 
Pipeline  như  sau:  Câu  lệnh  1  được  thực  hiện  từ  xung  clock  1  đến  xung  clock  7. 
Tương tự, câu lệnh 2 được thực hiện từ xung clock 2 đến xung clock 8. Nhưng câu 
lệnh 3  thì được  thực hiện  từ  xung  clock 3 đến xung  clock  12,  và  câu lệnh này  bị 
interclock từ xung clock 5 đến xung clock 7; bởi vì câu lệnh này dùng kết quả thực 
thi từ câu lệnh 1 và câu lệnh 2 nên nó phải đợi cho đến khi câu lệnh 1 và câu lệnh 2 


6 

thực  thi  xong  thì mới  thực  thi được.  Tương  tự,  câu  lệnh  4  được  thực  thi  từ  xung 
clock 4 đến xung clock 15, nó bị interclock từ xung clock 5 đến xung clock 7 (bởi 

vì  nó  đợi  câu  lệnh  3  thực  hiện  bước  chiếm  giữ  tài  nguyên)  và  nó  bị  interlock  từ 
xung clock 9 đến xung clock 10 (bởi vì nó phải đợi kết quả thực thi từ câu lệnh 3). 
Câu lệnh 5 được thực hiện từ xung clock 8 đến xung clock 16 và nó bị interlock từ 
xung clock 9 đến xung clock 10; bởi vì nó phải đợi cho câu lệnh 4 thực hiện bước 
chiếm giữ tài ngun thì nó mới thực hiện tiếp được. Câu lệnh 6 thực hiện từ xung 
clock 11 đến xung clock 17. Câu lệnh 7 được thực hiện từ xung clock 12 đến xung 
clock 20 và bị interlock từ xung clock 14 đến xung clock 15; Bởi vì nó phải đợi kết 
quả thực thi từ câu lệnh 5 và câu lệnh 6. Câu lệnh 8 được thực hiện từ xung clock 
13 đến xung clock 23, nó bị interlock từ xung clock 14 đến xung clock 15 (bởi vì nó 
đợi  câu  lệnh  7  thực  hiện  bước  chiếm  giữ  tài  ngun)  và  nó  bị  interlock  từ  xung 
clock 17 đến xung clock 18 (bởi vì nó đợi kết quả thực thi của câu lệnh 7). Kết quả 
được chỉ ra ở Hình 1.1.3. 
(1)  Load R1, Y 
(2)  Load R2, Z 
(3)  Add R3, R1, R2 
(4)  Store X, R3 
(5)  Load R4, B 
(6)  Load R5, C 
(7)  Mul R6, R4, R5 
(8)  Store A, R6 
(Hình 1.1.2:Đoạn lệnh chưa định thời) 
Vậy ta phải tốn 23 xung clocks để thực hiện đoạn lệnh trên; Nhưng ta lại bị 
interclock  đến 9 xung  clock.  Vậy  vấn đề đặt  ra là  ta có  thể  nào  tối  thiểu được  số 
interclock khi thực thi chương trình mà khơng làm thay đổi tính đúng đắn của nó.


7 

1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23 
(1)  F  D  I  E  E  E  W 

(2) 

F  D  I  E  E  E  W 

(3) 

F  D 

(4) 

F 

(5) 

I  E  E 

E  W 

D 

I 

E 

E 

E  W 

F 


D 

I 

E 

E 

E  W 

F 

D 

I 

E 

E 

F 

D 

I 

F 

D 


(6) 
(7) 
(8) 

E  W 
E 

E 

E  W 
I 

E 

E 

E  W 

(Hình 1.1.3:Đoạn lệnh ở hình 1.1.2 được thực hiện trên kiến trúc Pipeline) 
Ta thấy interclock của câu lệnh 3 và 4 là do nó phải đợi kết quả thực thi từ 
câu lệnh 1 và 2. Như vậy ta phải tìm những câu lệnh cịn lại của chương trình, sao 
cho  khơng phụ  thuộc  vào  kết  quả  của  câu lệnh  3  và 4;  Sau  đó di  chuyển các  câu 
lệnh này lên các vị trí của câu lệnh 3 và 4, cịn các câu lệnh 3 và 4 ta di chuyển về 
phía dưới. Ta dễ dàng thấy rằng câu lệnh 5 và 6 khơng phụ thuộc vào kết quả thực 
thi của câu lệnh 3 và 4; Do đó ta hốn đổi vị trí của câu lệnh 5 và 6 cho câu lệnh 3 
và 4. Ta có kết quả như sau: 
(1)  Load R1, Y 
(2)  Load R2, Z 
(5)  Load R4, B 
(6)  Load R5, C 

(3)  Add R3, R1, R2 
(4)  Store X, R3 
(7)  Mul R6, R4, R5 
(8)  Store A, R6


8 

Ta lại thấy rằng câu lệnh 4 lại phụ thuộc vào kết quả thực thi của câu lệnh 3, 
nhưng câu lệnh 7 lại khơng phụ thuộc vào kết quả của câu lệnh 4; Do đó ta hốn đổi 
vị trí của câu lệnh 4 với câu lệnh 7. Khi đó ta có được đoạn chương trình đã  được 
định thời như Hình 1.1.4. 
(1)  Load R1, Y 
(2)  Load R2, Z 
(5)  Load R4, B 
(6)  Load R5, C 
(3)  Add R3, R1, R2 
(7)  Mul R6, R4, R5 
(4)  Store X, R3 
(8)  Store A, R6 
(Hình 1.1.4:Đoạn lệnh ở hình 1.1.2 đã được định thời) 
Tương  tự  như  trên,  đoạn  trình  ở  hình  1.1.4  được  thực  thi  trên  kiến  trúc 
Pipeline như sau (Hình 1.1.5): 

(1) 
(2) 
(5) 
(6) 
(3) 
(7) 

(4) 
(8) 

1 

2 

3 

4 

5 

6 

7 

8 

9 

10 

11 

12 

F 

D 


I 

E 

E 

E 

W 

F 

D 

I 

E 

E 

E 

W 

F 

D 

I 


E 

E 

E 

W 

F 

D 

I 

E 

E 

E 

W 

F 

D 

I 

E 


F 

13 

14 

E 

E 

W 

D 

I 

E 

F 

D 

I 

F 

D 

15 


E 

E 

W 

E 

E 

E 

W 

I 

E 

E 

16 

17 

E 

W 

(Hình 1.1.5: Đoạn lệnh ở hình 1.1.4 được thực hiện trên kiến trúc Pipeline)



9 

Vậy lúc này ta chỉ tốn 17 xung clocks để thực hiện các câu lệnh; Trong khi 
đó với đoạn lệnh chưa được định thời ta phải tốn 23 xung clocks để thực hiện. Như 
vậy đoạn chương trình sau khi định thời, khi ta thực thi đã tiết kiệm được 6 xung 
clocks. Do đó việc định thời lại các câu lệnh để thực thi trong bộ xử lý Pipeline là 
cần thiết nhằm tận dụng kiến trúc Pipeline để tăng tốc độ thực hiện của một chương 
trình. 
Ta thấy rằng để thực hiệc việc định thời lệnh trên kiến trúc Pipeline, ta phải 
chỉ ra được sự phụ thuộc giữa các câu lệnh và cơng việc định thời lại được thực hiện 
trên các câu lệnh ở mức mã máy tại thời gian biên dịch. Vì vậy bài tốn định thời 
lệnh trên kiến trúc Pipeline là bài tốn NP­complete [HG83]. 

2) 

Sự phụ thuộc giữa các câu lệnh: 

Khi  ta  thực  hiện  định  thời  các  câu  lệnh  trong  chương  trình  thì  ta  phải  biết 
được những phụ thuộc giữa các câu lệnh trong chương trình đó. Các câu lệnh trong 
chương trình có những phụ thuộc cơ bản sau [KKF95]:
·  Sự phụ thuộc dữ liệu (Data dependence): Khi một câu lệnh a tạo ra một tập 
các dữ liệu và những dữ liệu này được dùng cho câu lệnh b thì câu lệnh b sẽ 
khơng thực hiện được cho đến khi dữ liệu được tạo ra bởi câu lệnh a. Sự phụ 
thuộc này gọi là sự phụ thuộc dữ liệu. 
Ví dụ: 
r1=r2+r3 

Để tính được r1 ta phải có r2 và r3 


r4=r1*3 

Để tính được r4 ta phải có r1 

r5=r4­r2 

Để tính được r5 ta phải có r4 và r2

·  Sự  phụ  thuộc  điều  khiển  (Control  dependence):  Trong  kiến  trúc  máy  Von 
Neumann, thực thi của một chương trình được điều khiển bởi trạng thái bên 
trong của máy. Sau một rẽ nhánh, câu lệnh khơng thực thi cho đến khi có sự 
thay đổi trạng thái hồn tồn. Mối quan hệ kiểu này gọi là sự phụ thuộc điều 
khiển.


10 

Ví dụ:

bt:r1==r4 

bt đúng
r3=3 

bt sai 
r3=r2 
r2=1 

·  Sự phụ thuộc tài ngun (Resource dependence): Có những câu lệnh có mối 

quan hệ  với nhau  thì  khơng  thực  thi tại  cùng  một thời điểm, bởi  vì  sự giới 
hạn tài ngun. Mối quan hệ này gọi là sự phụ thuộc tài ngun. 
Ví dụ: 
r1=2 

Sự phụ thuộc dữ liệu 

r3=r1+4 
r1=r5­1 

3) 

Sự phụ thuộc tài ngun của thanh ghi 

DDAG (The Dependency Directed Acyclic Graph): 

Để định thời các câu lệnh mà khơng làm thay đổi tính đúng đắn của chương 
trình thì ta phải biểu diễn được các ràng buộc của các câu lệnh, ta phải biết bất kỳ 
một câu lệnh nào đó có phụ thuộc vào các câu lệnh khác hay khơng. Đồ thị DDAG 
sẽ giúp ta thể hiện được các ràng buộc dữ liệu giữa các câu lệnh. 
Chúng ta xây dựng mỗi nút của DDAG là một câu lệnh và những cạnh của 
đồ thị chỉ ra sự phụ thuộc dữ liệu giữa các câu lệnh. Một cạnh bắt đầu từ nút a vào 
một nút b, nghĩa là: câu lệnh a phải được thực thi trước câu lệnh b để bảo đảm tính 
đúng đắn của tồn bộ chương trình. 
Ví dụ: ta có chương trình nguồn được viết dưới dạng ngơn ngữ cấp cao, như 


11 

sau: h= a*b +(c+d)*(a+e); 

Viết lại đoạn chương trình trên bằng ngơn ngữ tựa ngơn ngữ máy: 
(1)  Load PR1, a 
(2)  Load PR2, b 
(3)  Mul PR3, PR1, PR2 
(4)  Load PR4, c 
(5)  Load PR5, d 
(6)  Add PR6, PR4, PR5 
(7)  Load PR7, e 
(8)  Add PR8, PR1, PR7 
(9)  Mul PR9, PR6, PR8 
(10) Add PR10, PR3, PR9 
(11) Store h, PR10 
(Hình 1.3.1) 
Ta thấy câu lệnh 3 muốn thực thi được thì câu lệnh 1 và 2 phải thực thi xong. 
Do đó ta biểu diễn ràng buộc này như sau: 

1 

2 

3
Tương tự, câu lệnh 6 thực thi được khi ta thực thi xong câu lệnh 4 và 5. Câu 
lệnh 8 thực thi được khi ta thực thi xong câu lệnh 1 và 7. Câu lệnh 9 thực thi được 
khi ta thực thi xong câu lệnh 6 và 8. Câu lệnh 10 thực thi được khi ta thực thi xong 


12 

câu lệnh 3 và 9. Câu lệnh 11 thực thi được khi ta thực thi xong câu lệnh 10. Do đó 
ta biểu diễn các ràng buộc đó như sau: 


4 

5 

1 

6 

3 

6 

8 

9 

8 

9 

10

10 

1 

7 

11


2 

4 

3 

5 

7 

6 

8 
9 
10

11 
(Hình 1.3.2: Đồ thị DDAG) 
Như vậy DDAG cho đoạn chương trình ở hình 1.3.1 là  hình 1.3.2 

4) 

Khối cơ bản (Basic block): 


13 

Ngồi ra trong chương trình cịn có những ràng buộc điều khiển. Để xác định 
được những  ràng buộc  này,  ta  phân hoạch  chương trình  thành  các khối cơ bản và 

các ràng buộc điều khiển đuợc thể hiện bằng các cạnh nối các khối cơ bản với nhau. 
Khối  cơ bản là một dãy  những  câu  lệnh  liên tiếp.  Dãy  các  câu  lệnh này  có 
những dịng điều khiển đi vào tại vị trí bắt đầu và những dịng điều khiển đi ra tại vị 
trí kết thúc. Những dịng điều khiển này khơng bị gián đoạn hoặc có thể chấp nhận 
rẽ nhánh tại vị trí cuối. 
Ví dụ: ta xét đoạn chương trình như hình 1.4.1 
S1
ifFalse (Exp) goto L1 

S1 

S2

S1

B1 

Jmp L2 

IfFalse (Exp) goto L1 

Exp 

L1: 
S3 
L2: 

B2 
S2 


S4 

S2 

B3 

S3 

S3 

(Hình 1.4.1) 
Trong đó: S1, S2, S3, S4 là 

S4 

những  khối  lệnh  khơng 
chứa những lệnh nhảy. 

Hình  1.4.2:  Lưu 
đồ của đoạn  lệnh 
ở hình 1.4.1. 

B4

S4 

Hình 1.4.3: Đồ thị xác 
định những dịng  điều 
khiển của đoạn lệnh ở 
hình 1.4.1. 


Theo  hình 1.4.3  thì  đoạn  chương  trình  ở  hình  1.4.1  có  bốn  khối  cơ  bản là: 
B1, B2, B3, B4 và các cạnh nối các khối này là các dịng điều khiển. 
Vậy việc định thời lệnh cho chương trình có hai dạng là định thời tồn cục và 
định  thời  cục  bộ.  Định  thời  toàn  cục  là  định  thời  lệnh  cho  tồn  bộ  chương  trình. 
Định  thời  cục bộ  là  định  thời  trên  khối cơ bản. Trong phạm  vi của đề tài này chỉ 
trình bày các giải thuật định thời cục bộ. 


14 

Chương 2 

Một vài giải thuật định thời cục bộ 

Chương này trình bày các giải thuật định thời cục bộ làm kiến thức nền tảng 
cho  việc  hình  thành  giải  thuật  List_cycle_scheduling.  Để  thực  hiện  định  thời 
chương trình, chúng ta phân rã chương trình thành những khối cơ bản và thực hiện 
định thời trên những khối cơ bản đó. Định thời cục bộ (local scheduling) là ta thực 
hiện  định  thời  lệnh  trên  khối cơ bản.  Nội dung  của chương này  trình bày  các  giải 
thuật  định  thời  cục  bộ  sử  dụng  cho  kiến  trúc  Pipeline,  bao  gồm:  Giải  thuật  DLS, 
Giải  thuật  CSP,  Giải  thuật  ICS,  Giải  thuật  List_scheduling,  Giải  thuật 
Cycle_scheduling, Giải thuật Oper_scheduling, và Giải thuật List_bt_scheduling. 

1) 

Giải thuật DLS (Delayed­Load Scheduling algorithm) 
Giải  thuật  DLS  dùng  để  định  thời  lệnh  và  phân  phối  thanh  ghi  [TC91], 

nhưng  điểm  nổi  bậc  nhất  của  giải  thuật  là  phân  phối  thanh  ghi  và  chỉ  ra  đoạn 

chương  trình  khi  định  thời  cần  tối  thiểu  bao  nhiêu  thanh  ghi  mà  không  gây  ra 
Spilling. Giải thuật này sử dụng cây biểu thức để định thời lệnh. 
Nội dung của giải thuật DLS: 
Bước 1: Xây dựng cây biểu thức. 
Bước 2:  Tính minReg  cho mỗi  nút  trong  cây  biểu thức.  MinReg  là một  số 
ngun xác định số thanh ghi tối thiểu cần cho việc định thời lệnh mà khơng gây ra 
Spilling. MinReg tại nút a được tính như sau: 
If ( a là nút lá) 
a.minReg=1; 
Else{


15 

If (a.left.minReg==a.right.minReg) 
a.minReg=a.left.minReg+1; 
Else 
a.minReg=Max(a.left.minReg, a.right.minReg); 
} 

Bước 3: Sắp xếp thứ tự thực hiện của các câu lệnh Load và các phép toán. 
Ngõ vào: root là cây biểu thức 
Ngõ ra: opSched là danh sách các phép toán, và loadShed là danh sách 
các lệnh đã được sắp thứ tự. 
Procedure order(root, opSched, loadSched){ 
If (root là nút lá) { 
Thêm root vào danh sách loadSched; 
} else { 
if (root.left.minReg > root.right.minReg) { 
order(root.left, opSched, loadSched); 

order(root.right, opSched, loadSched); 
} else { 
order(root.right, opSched, loadSched); 
order(root.left, opSched, loadSched); 
} 
Thêm root vào danh sách opSched; 
} 
} 

Bước 4: Thực hiện thứ tự các câu lệnh đã được sắp xếp theo Bước 3


16 

Ngõ vào: opSched, loadSched, và Regs. Regs là số thanh ghi dùng để 
định thời lệnh. 
Ngõ ra: staList là danh sách các câu lệnh đã được định thời. 
Procedure schedule(opSched, loadSched, Regs, staList){ 
initLoads=Min(Regs, chiều dài của danh sách loadSched); 
For i=1 to initLoads { 
§  Lấy câu lệnh đầu tiên ldi  ra khỏi danh sách loadSched; 
§  Phân phối thanh ghi Ri cho câu lệnh ldi; 
§  Thêm câu lệnh ldi  vào danh sách staList; 
} 
while (danh sách loadSched khác rỗng) { 
§  Lấy phép tốn đầu tiên op ra khỏi danh sách opSched; 
§  op.reg=op.right.reg; 
§  Thêm phép tốn op vào danh sách staList; 
§  Lấy câu lệnh ld ra khỏi danh sách loadSched; 
§  Phân phối thanh ghi op.left.reg cho câu lệnh ld; 

§  Thêm câu lệnh ld vào danh sách staList; 
} 
while (danh sách opSched khác rỗng) { 
§  Lấy phép tốn đầu tiên op ra khỏi danh sách opSched; 
§  op.reg=op.right.reg; 
§  Thêm phép tốn op vào danh sách staList; 
§  Giải phóng thanh ghi op.left.reg; 
} 
}


17 

v  Thực hiện giải thuật DLS: 
Ngõ vào: root, Delay. Delay là một số ngun. 
Ngõ ra: staList 
Procedure generate(root, Delay, staList) { 
Tính minReg cho các nút của cây biểu thức root; 
Order(root, opSched, loadSched); 
Schedule(opSched, loadSched, root.minReg+Delay,staList); 
} 

Ví dụ: Ta xét câu lệnh trong ngơn ngữ cấp cao sau: h= a*b +(c+d)*(a+e) 
Bước 1và 2: Tạo cây biểu thức và tính minReg tại mỗi nút 

+3 
3

*2 
3 

+1 

+ 2 

*1 

2 

2 

2 

d 

c 

e 

a 

a 

b 

1 

1 

1 


1 

1 

1 

(Hình 2.1.1:Cây biểu thức và minReg tại mỗi nút) 
Các nút a, b, c, d, e là các nút lá nên minReg của các nút này bằng 1. Nút  +1 
là nút cha của hai nút c và d, nút c có minReg bằng 1 và nút d có minReg bằng 1, do 
đó nút +1  có minReg bằng minReg của nút d cộng 1; nghĩa là bằng 2. Tương tự, các 
nút  +2  và nút *1  có minReg bằng 2; Nút  *2  có minReg bằng 3. Nút +3 là nút cha của 


18 

hai nút  *2  và  *1, nút  *2  có minReg bằng 3 và nút  *1  có minReg bằng 2, do đó nút +3 
có  minReg  bằng  minReg  của  nút  lớn  nhất;  Nghĩa  là  bằng  minReg  của  nút  *2  và 
bằng 3. 
Bước 3: Thứ tự thực hiện của các lệnh load và các phép tốn 
Kết quả duyệt cây biểu thức ta được: 
((d c +1) (e a +2) *2) (a b  *1) +3 
Do đó thứ tự thực hiện của các câu lệnh load là: d, c, e, a, a, b; Và thứ tự thực 
hiện của các phép tốn là:  +1, +2, *2, *1, +3. 
Bước 4: Định thời lệnh. Giả sử số thanh ghi dùng để định thời là 4. 
Vì số thanh ghi sử dụng là 4, nên giải thuật DLS lấy bốn lệnh load đầu tiên 
là: 
Load r1,d 
Load r2,c 
Load r3,e 
Load r4,a 


Vì hết thanh ghi để phân phối cho các lệnh load cịn lại nên giải thuật DLS 
lấy  một  phép  tốn  trong  danh  sách  phép  tốn  (đó  là  phép  tốn  +1)  là:  Add 
r2,r1,r2.  Sau khi thực hiện câu lệnh này thì thanh ghi r1 được giải phóng, do đó 

giải thuật thực hiện việc lấy câu lệnh load tiếp theo là:  Load r1,a.Q trình thực 
hiện tương tự cho đến khi các câu lệnh load trong danh sách lệnh load được lấy hết. 
Ta có các lệnh được lấy là: 
Add r4,r3,r4 
Load r3,b 

Tiếp theo ta lấy các phép tốn cịn lại trong danh sách phép tốn (là  *2,  *1, 
+3), ta được các câu lệnh sau:


19 

Mul r4,r2,r4 
Mul r3,r1,r3 
Add r3,r4,r3 

Vậy ta có danh sách các câu lệnh đã được định thời như cột bên phải trong 
hình 2.1.2. Cột bên trái của hình 2.1.2 chứa các câu lệnh chưa được định thời 
Khi đó ta tính được tổng số chu kỳ thực hiện của đoạn chương trình định thời 
bằng giải thuật DLS (với Delay=1) là 20 xung clocks. Trong khi đó, nếu ta khơng 
định thời lệnh thì tổng số chu kỳ thực hiện của đoạn chương trình là 25 xung clocks. 
Vậy giải thuật DLS đã cải thiện được tốc độ thực hiện của chương trình. 
Các lệnh chưa định thời 

DLS(Delay=1) 


(1)  Load R1, a 

Load r1,d 

(2)  Load R2, b 

Load r2,c 

(3)  Mul R1, R1, R2 

Load r3,e 

(4)  Load R3, c 

Load r4,a 

(5)  Load R4, d 

Add r2,r1,r2 

(6)  Add R3, R3, R4 

Load r1,a 

(7)  Load R4, e 

Add r4,r3,r4 

(8)  Add R4, R1, R4 


Load r3,b 

(9)  Mul R3, R3, R4 

Mul r4,r2,r4 

(10) Add R3, R3, R2 

Mul r3,r1,r3 

(11) Store h, R3 

Add r3,r4,r3 
store r3,h 

25 xung clocks 

20 xung clocks 

(Hình 2.1.2: Định thời theo giải thuật DLS) 
Giả sử số chu kỳ thực hiện của các lệnh là: (đơn vị tính là xung clock)


20 

Tên lệnh 

Số xung clock 


Load 

4 

Store 

1 

Add 

2 

Mul 

3 

(Hình 2.1.3) 
v  Những ưu điểm của giải thuật:
·  Giải thuật tối thiểu tổng số chu kỳ thực hiện và việc dùng thanh ghi.
·  Tổng số chu kỳ thực hiện tỷ lệ với kích thước của cây biểu thức.
·  Giải thuật có khả năng phối hợp việc lựa chọn lệnh, định thời lệnh và 
phân phối thanh ghi. 
v  Nhược điểm của giải thuật DLS:
·  Giải  thuật  DLS  dùng  cây  biểu  thức  để  định  thời  nên  quá  trình  định 
thời  lệnh  chỉ  thực  hiện  được  khi  ta  xây  dựng  được  cây  biểu  thức. 
Nghĩa là giải thuật chỉ định thời trên những khối lệnh cơ bản phát sinh 
mã từ những biểu thức.
·  Phép tốn sử dụng trong giải thuật để định thời là phép tốn hai ngơi, 
do đó với những phép tốn khơng phải là phép tốn hai ngơi thì giải 
thuật sẽ khơng thực hiện được.

·  Khi định thời giải thuật dùng một phép tốn ngay kề sau một câu lệnh 
load, nhưng số chu kỳ thực hiện cho một câu lệnh load là khá lớn, do 
đó gây ra Interlock trong Pipeline. Giả sử lệnh load có số chu kỳ thực 
hiện  là  4  xung  clock,  như  vậy  Pipeline  phải  interlock  3  xung  clock 
mới thực hiện được phép tốn đứng kề sau nó.


21 

2)  Giải thuật CSP (Code Scheduling for Pipelined processors): 
Giải thuật CSP dùng để thực hiện định thời lệnh [GM86], và giải thuật giả sử 
là số thanh ghi mà hệ thống máy cấp cho giải thuật ln đủ, do đó giải thuật khơng 
quan tâm đến việc phân phối thanh ghi. Giải thuật thực hiện việc định thời lệnh sao 
cho tối thiểu càng nhiều Interlock càng tốt. Giải thuật dùng đồ thị DDAG để định 
thời lệnh.
Nội dung của giải thuật CSP: 
Ngõ vào:Danh sách tập lệnh (chưa được định thời) và số chu kỳ thực 
thi của từng câu lệnh. 
Ngõ ra: Danh sách tập lệnh staList đã được định thời. 
Bước 1: Xây dựng DDAG trọng số. Trọng số của mỗi nút trên DDAG được 
tính  bằng chi  phí  tích  lũy  của  mỗi  nút  trong DDAG  bằng  cách  ước 
lượng số chu kỳ thực thi của mỗi lệnh. Tính bậc ra của mỗi nút. 
Bước 2: Tạo ra Tập dự tuyển (là những nút của DDAG có bậc vào bằng 0) 
và sắp xếp các nút trong tập này theo thứ tự giảm dần của trọng số 
và tăng dần theo bậc ra của mỗi nút. 
Bước 3: 
While (Tập dự tuyển khác rỗng) {
·

Lấy câu lệnh đầu tiên s ra khỏi Tập dự tuyển;


·

Thêm lệnh s và danh sách staList;

·

Xố nút s trong DDAG;

·

Chèn những nút mới có bậc vào bằng 0 trong DDAG vào Tập 
dự tuyển (sao cho các nút của Tập dự tuyển vẫn đảm bảo thứ 
tự  giảm  dần  của  trọng  số  và  tăng  dần  theo  bậc  ra  của  mỗi 
nút); 

}