BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC THÁI NGUYÊN CHU ĐỨC TOÀN
NGHIÊN CỨU THUẬT TOÁN ĐIỀU KHIỂN THÍCH NGHI
LUỒNG THAM CHIẾU ĐỂ NÂNG CAO TỐC ĐỘ CHO CÁC
HỆ XỬ LÝ SONG SONG CHUYÊN DỤNG

Chuyên ngành: Kỹ thuật Điều khiển và Tự động hóa
Mã số: 62.52.02.16 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT
THÁI NGUYÊN - 2013

TÓM TẮT LUẬN ÁN
1. Tính cấp thiết đề tài

Nhiều lĩnh vực mới như đồ họa máy tính, trí tuệ nhân tạo, phân
tích số, tính toán song song trong công nghiệp dầu khí, các thiết bị
không người lái, thiết bị nhận dạng bám sát đa mục tiêu di động ,
đòi hỏi phải xử lý một khối lượng dữ liệu rất lớn với tốc độ rất cao.
Hầu hết những bài toán này, những máy tính tuần tự là không đáp
ứng được yêu cầu thực tế. Nghiên cứu về hệ xử lý song song hiện
nay tập chung hai hướng nghiên cứu chính như sau:
Một là nghiên cứu các hệ xử lý đa năng như siêu máy tính
(Suppercomputer), máy tính lớn (Mainframe), máy tính mini
(Minicomputer) thực hiện đa năng: cấu trúc phần cứng và chức
năng phần mềm của máy tính cần phải được tổ chức đa chức năng
rất phức tạp. Mô hình toán cũng rất phức tạp, vượt qua khỏi cơ
cấu tính toán thông thường. Do vậy, khi áp dụng cho các ứng
dụng chuyên dụng, tốc độ xử lý của chúng thường chậm hơn so
với khả năng của bộ vi xử lý, thông số thời gian thực khó kiểm
soát một cách chính xác Hệ xử lý song song đa năng quy mô rất lớn
kèm theo cơ cấu phần mềm vận hành cấu trúc này rất phức tạp. Vì
vậy các hệ máy tính này có giá thành rất đắt. Đây là vấn đề khó khăn
khi giải quyết các bài toán đặc thù có yêu cầu tốc độ nhanh, giá thành
rẻ phù hợp với điều kiện nền kinh tế Việt Nam.
Hai là nghiên cứu các hệ xử lý song song đa CPU chuyên dụng đó
là: Hệ xử lý song song chuyên dụng phục vụ một hay một lớp bài
toán cụ thể, gần nhau về chức năng. Do đó, phương thức thao tác,
cấu trúc tập hợp dữ liệu cần xử lý, cấu trúc dữ liệu kết quả đều xác
2
2. Đối tượng và phạm vi nghiên cứu
- Đối tượng nghiên cứu luận án là KGNDC trong hệ xử lý song
song đa CPU chuyên dụng.
- Phạm vi nghiên cứu của luận án là giới hạn trong việc xây dựng
mô hình toán học tham chiếu tới KGNDC trong hệ xử lý song song
đa CPU chuyên dụng, chỉ rõ các điều kiện ràng buộc giữa các thông
số và các thông số có thể thay đổi điều khiển được để tổng hợp hệ
điều khiển thích nghi luồng tham chiếu tới KGNDC nhằm nâng cao
hiệu năng giảm thiểu xác suất xung đột khi truy cập tài nguyên dùng
chung.
3. Phương pháp nghiên cứu của luận án
- Dựa trên lý thuyết kinh điển là lý thuyết hàng đợi, lý thuyết xác
suất cụ thể là quá trình Morkov dừng, phân bố Poát - xông để xây
dựng và tính toán hiệu năng cho mô hình toán học tham chiếu tới
KGNDC trong hệ xử lý song song đa CPU.
- Mô tả toán học mô hình bộ nhớ dùng chung trong hệ xử lý song
song đa CPU.
- Nghiên cứu xây dựng hệ thống điều khiển thích nghi luồng tham
chiếu sử dụng công nghệ đương đại FPGA.
4. Ý nghĩa khoa học và thực tiễn luận án
4.1. Về mặt khoa học
Ý nghĩa khoa học là nghiên cứu triển khai ứng dụng các bộ điều
khiển thích nghi luồng tham chiếu tới KGNDC cho hệ xử lý song
song đa CPU chuyên dụng nhằm nâng cao hiệu năng, nâng cao tốc
4 độ, giảm thiểu tối đa xác suất xung đột khi truy cập tài nguyên dùng

1.5.1. Các đặc trưng của hệ xử lý song song đa CPU chuyên dụng
a) Chức năng chuyên dụng
Chức năng chuyên dụng còn được thể hiện trên cấu trúc dữ liệu mà
hệ phải xử lý. Cấu trúc dữ liệu này phần lớn là dữ liệu véc tơ do có
cấu trúc phần tử giống nhau và chúng xắp xếp có thứ tự (như cấu
trúc: cự ly-phương vị-độ cao) cho phép dễ dàng véc tơ hoá cơ sở dữ
liệu này. Hệ quả là dễ thực hiện các thao tác xử lý dữ liệu theo cơ
chế đường ống - một cơ chế nâng cao hiệu năng của hệ xử lý.
b. Cấu trúc phần cứng tối giản
Do hệ xử lý song song chuyên dụng thực hiện một nhiệm xác định
và nhiệm vụ này được xác lập chỉ trên một lớp bài toán nên các
thông số cấu trúc được xác định khá chính xác. Hệ quả là khâu tổ
chức phần cứng sẽ bảo đảm sự tối giản bằng các thuật toán phân
hoạch chuẩn.
c. Tốc độ và hiệu năng cao
d. Độ tin cậy cao
6 Đây là một yêu cầu, đồng thời cũng là đặc điểm của hệ xử lý
song song chuyên dụng. Thoạt nhìn có vẻ như yêu cầu này là xung
đột với yêu cầu về tốc độ cao của hệ. Tuy nhiên, khác với máy tính
đa dụng, hệ xử lý song song chuyên dụng phần lớn là hệ thống khó
bảo trì, thậm chí không thể bảo trì (như các hệ xử lý đặt trên vệ tinh,
trên các tên lửa tự dẫn, hoặc nằm trong hệ thống cảnh báo sớm đặt
dưới lòng biển ) nên nó đòi hỏi độ tin cậy phải cao.
1.5.2. Kiến trúc của hệ xử lý song song đa CPU chuyên dụng
a. Mô hình hệ xử lý song song đa CPU chuyên dụng
b. Những yếu tố ảnh hưởng đến hiệu năng hệ xử lý song song đa
CPU chuyên dụng

Hình 1.13. Cự ly quan sát của hệ
Vành khăn c
ự ly

ngoài cùng
N1024t
t
Vành khăn
cự ly N1023
Vành khăn
cự ly N1
Xung kích phát
tần số 375 Hz
Xung ph
ản
xạ từ mục
tiêu trên các
cự ly khác
nhau

Chu k

- Lựa chọn được đối tượng nghiên cứu là hệ xử lý song song đa
CPU chuyên dụng cụ thể là KGNDC.
9 - Định hướng nghiên cứu hệ xử lý song song đa CPU chuyên
dụng theo hướng ứng dụng phương pháp điều khiển hiện đại để điều
khiển luồng tham chiếu tới KGNDC trong hệ xử lý song song đa
CPU cụ thể là cơ cấu điều khiển thích nghi luồng tham chiếu tới
KGNDC nhằm giảm thiểu tối đa xác suất xung đột khi truy cập tài
nguyên chung.
Trên cơ sở nghiên cứu các bước đầu về hệ xử lý song song đa
CPU chuyên dụng, trong chương 2 luận án sẽ đi sâu nghiên cứu,
phân tích, xây dựng mô hình toán học tham chiếu tới KGNDC.
Chương 2. Xây dựng mô hình toán học tham chiếu bộ nhớ chung
trong hệ xử lý song song đa CPU
2.1. Cơ sở lý thuyết
Để xây dựng mô hình toán học cho cơ chế điều khiển tối ưu luồng
tham chiếu trong hệ xử lý song song đa CPU chuyên dụng dựa vào
các yêu cầu của các hệ xử lý chức năng được diễn tả trong chương 1
thực hiện với KGNDC, luận án cần sử dụng:
- Lý thuyết hàng đợi (queuing theory) dùng để mô tả n luồng tham
chiếu tới KGNDC với cơ chế xếp hàng ở lối vào/ra.
- Lý thuyết xác suất, cụ thể là quá trình Markov được sử dụng để
đồng nhất cơ chế tham chiếu của n luồng tham chiếu tới KGNDC
với cơ chế đồng bộ trong hoạt động của hệ xử lý song song đa CPU
chuyên dụng. Tức là trạng thái hệ thống chỉ được xác lập sau thời
điểm xung nhịp hệ thống. Hơn nữa ở đây chỉ sử dụng quá trình
Markov dừng để khẳng định rằng trạng thái tương lai của hệ thống
10

Control

Bộ nhớ dùng
chung
+ Kênh địa chỉ
+ Kênh điều khiển
Hình 2.1. Tham chiếu bộ nhớ dùng chung trong hệ xử lý
song song.
11 Trong đó: N
acc
– Tổng số lượng các tham chiếu thành công.
N
acc0
- tổng số các tham chiếu đã phát động bởi hệ
thống. Nếu coi xác suất tham chiếu tới KGNDC là E để đảm bảo một
tham chiếu thành công thì ta cần 1/E phép thử.
Gọi P là xác suất thanh ghi tham chiếu lối vào là rỗi, còn khi
bận sẽ có xác suất là Q = 1- P. E
l
là hiệu năng của hệ thống khi
điều kiện thanh ghi lối vào đang ở trạng thái rỗi
E
p
là hiệu năng của hệ thống khi điều kiện thanh ghi lối vào
đang ở trạng thái bận. Ba đại lượng này có quan hệ chặt chẽ với
nhau và được biễu diễn bằng bài toán xác suất có điều kiện. Để
đảm bảo một tham chiếu thành công cần N

– Hiệu năng tham chiếu thanh ghi
lối vào bận; (iii) E
l
– Hiệu năng thanh ghi tham chiếu lối vào rỗi.
Những đại lượng này rất phức tạp và phụ thuộc rất nhiều tham số
liên quan đến cấu trúc hệ thống.
12 2.2.2.1. Xác định đại lượng P – Xác suất để thanh ghi tham chiếu lối
vào rỗi
- Để khảo sát được P ta cần mô hình hoá toàn bộ quá trình tham
chiếu của các CPU đến bộ nhớ dùng chung. Trên cơ sở của mô hình
lý thuyết hàng đợi, mô tả trên hình 2.2.a, kết hợp với các đặc điểm
của hệ xử lý song song đa CPU chuyên dụng, có thể xem kiến trúc
bộ nhớ dùng chung như một hệ thống gồm k hàng đợi độc lập theo
quy tắc M/D/1/m. Điều đó có nghĩa: quá trình tham chiếu tới bộ nhớ
dùng chung là quá trình Poission và có phân bố Markov (M); thời
gian phục vụ của bộ nhớ là xác định (D); không gian nhớ phục vụ
các tham chiếu bằng 1 và kích thước hàng đợi của mỗi mô đun nhớ
bằng m
- Xác suất để thanh ghi tham chiếu lối vào rỗi sẽ được xác định:

 
   
   
 
 

 

(2.15)
2.2.2.2. Xác định E
p
- Hiệu năng khi các hàng đợi của các mô đun
nhớ đầy
Xét trong trường hợp hiệu năng khi các hàng đợi của các mô đun nhớ
đầy: Khi phát động một tham chiếu từ một đơn CPU bất kỳ, thì vẫn
có xác suất được phục vụ (tham chiếu có xác suất thành công nhất
định). Vì vậy ta tính E
p
Hiệu năng khi các hàng đợi mô đun nhớ đầy,
E
p
được tính như sau:
13 bTTnqq
q
E
PP
P
/)1(2112
2
2

 (2.18)
2.2.2.3. Xác định E
l
- Hiệu năng khi thanh ghi tham chiếu lối vào

Chương 2 luận án đã giải quyết được các vấn đề sau:
14 - Đã xây dựng được mô hình toán học tham chiếu tới KGNDC cho
hệ xử lý song song đa CPU chuyên dụng, ràng buộc các tham số có
thể tính toán và điều khiển được như kích thước hàng đợi m, b…
- Mô hình toán học tham chiếu KGNDC sẽ được sử dụng ở
chương 3 trong việc xây dựng hệ thống có cơ cấu điều khiển thích
nghi luồng tham chiếu tới KGNDC cho hệ xử lý song song đa CPU
chuyên dụng.
Chương 3. Xây dựng mô hình điều khiển thích nghi cho hệ xử lý
song song đa CPU chuyên dụng
3.1. Xây dựng phần mềm khảo sát
3.1.1. Xây dựng modul chính phần mềm khảo sát

Hình 3.1. Giao diện phần mềm tính toán hiệu năng hệ xử lý song
song đa CPU
3.1.2. Xây dựng modul phần mềm tính toán hiệu năng hệ xử lý
song song đa CPU trong quan hệ với chu kỳ bộ nhớ dùng chung
Tc
15
Hình 3.2. Giao diện phần mềm tính toán hiệu năng hệ xử lý song
song đa CPU trong quan hệ với chu kỳ bộ nhớ dùng chung Tc
3.1.3. Xây dựng modul phần mềm tính toán hiệu năng hệ xử lý
song song đa CPU trong quan hệ với số lượng luồng tham chiếu n


E

Hình 3.5. Hiệu quả tham chiếu ngẫu nhiên băng nhớ logic theo T
được so sánh trong hai trường hợp khi m=2 và trường hợp
không có băng nhớ logic (m =0, T
l
=T
d
=0)
17
Hình 3.6. Sự phụ thuộc của E theo chu kỳ vật lý của mô đun nhớ Tc
khi m thay đổi
0.0
0.2
0.4
0.6
0.8
1.0
1 5 10 15 20 25 30 35 40 45 50
m=6
m=4
m=2
m=0
n
E

0.0

0.6
0.8
1.0
1 5 10 15 20 25 30 35 40 45 50
Tc
m=6
m=4
m=2
m=0

Hình 3.8. Đồ thị của E theo chu kỳ vật lý mô đun nhớ Tc khi giữ cố
định ρ= 0,5
Với một hệ thống gồm có n luồng tham chiếu, l băng nhớ lôgíc, T
l
=1, m= 4 6 và q=1.0 (tải đầy đủ). Để hiệu năng E > 0,90 với
1
0
,


, với m =2 , cần chọn

<0,2. Khi tăng T
l
, chúng có tác động
làm hạ thấp hiệu năng toàn phần, để duy trì hiệu năng cần giữ

<
0,5.
Những tỷ lệ quan hệ tương tự có thể được đưa ra khi khảo sát với

3.4. Công nghệ FPGA
3.4.1. Tái kiến trúc phần cứng bằng chương trình
3.4.2. Thiết kế hệ thống trên FPGA
3.5. Sơ đồ nguyên lý điều khiển thích nghi theo tham số m
Phần khảo sát đã chỉ rõ được mối quan hệ định lượng giữa hiệu
năng E với kích thước hàng đợi. Tuy nhiên E còn phụ thuộc vào mật
độ luồng tham chiếu theo thời gian (do tham số n không là hằng số)
nên cần một cơ cấu điều khiển kích thước m của hàng đợi trong mối
Bộ điều khiển thích nghi
ĐT ĐK

lp
pl
QEPE
EE
E



E
yc
E
out
∆e
m
-
B
ộ
đi
ều

hành: bước 1-mã 011; bước 2-mã 111; bước 3-mã 111.
21
Hình 3.16. Mô hình điều khiển kích thước hàng đợi m
Bảng 3.2. Bảng điều khiển
Tín hiệu điều khiển cho FPGA dưới dạng mã nhị phân 3 bit với:
000 -> hở mạch 111-> không làm gì
Đầu vào D2 Đầu vào D3
Đầu vào Tầng đường
ống tiếp theo
Đầu ra D1 001 010 011
Đầu ra D2 100 101
Đầu ra D3 110
Trình t
ự phát
mã điều khiển

Phát bước 1 Phát bước 2 Phát bước 3
3.6. Kết luận chương 3
Chương 3 đã giải quyết được các vấn đề sau:
22 - Xây dựng các thuật toán, chương trình tính toán hiệu năng trong
môi trường Delphi.
- Đưa ra các kết quả mô phỏng cho thấy với trường hợp mô hình
toán học tham chiếu tới KGNDC khi không sử dụng bộ đệm kích
thước hàng đợi m có hiệu năng thấp hơn nhiều so với trường hợp khi

nay đều cho phép thực hiện.
2. Kiến nghị
Luận án mới dừng lại ở mô hình điều khiển thích nghi theo
một tham số hệ thống là kích thước hàng đợi m nên tính linh hoạt
và mềm dẻo chưa cao. Vì vậy hướng nghiên cứu tiếp của luận án là
tích hợp thêm một số tham số khác vào cơ chế điều khiển thích
nghi như: chu kỳ làm việc của bộ nhớ T
c
, số lượng băng nhớ b của
KGNDC…