1
MỞ ĐẦU
1. Cơ sở nghiên cứu và mục đích của luận văn
Ngày nay, với sự phát triển của khoa học kỹ thuật, các yêu cầu về hệ vi
xử lý chuyên dụng ngày càng cấp thiết. Đối với một số ứng dụng như trong
các hệ thống quan sát, các hệ thống đo lường, điều khiển vệ tinh… thì số
lượng phép tính phải thực hiện đồng thời là cực lớn.
Các hệ siêu máy tính có giá thành cao và sẽ rất lãng phí khi sử dụng
trong các ứng dụng chuyên dụng với lớp bài toán hẹp hơn. Vì thế, việc sử
dụng vi xử lý với tốc độ tính toán cao kết hợp với việc áp dụng các thuật toán
tính toán nhanh trong khi vẫn đảm bảo giá thành hợp lý là rất cần thiết.
2. Tổ chức luận văn
Luận văn được trình bầy thành 3 chương. Phần mở đầu, tác giả trình
bày tóm tắt cơ sở nghiên cứu và mục đích cũng như tổ chức của luận văn.
Chương 1, trình bầy khái quát về lý thuyết xử lý song song. Các dòng
vi xử lý trong thực tế và đánh giá về tốc độ cũng như khả năng ứng dụng của
chúng trong những lớp bài toán cụ thể.
Chương 2, giới thiệu về họ vi xử lý vec tơ NM6403 do hãng module
của Nga sản xuất. Đây là một hệ vi xử lý tốc độ cao, rất thích hợp cho những
ứng dụng cụ thể đòi hỏi tốc độ xử lý cực cao.
Chương 3, cũng là chương quan trọng nhất. Sử dụng hệ vi xử lý véc tơ
NM6403 tốc độ cao, áp dụng thuật toán FHT để được hiệu quả tính toán
nhanh nhất, luận văn giới thiệu một cách tiếp cận để xây dựng một hệ vi xử lý
tốc độ cao ứng dụng trong những lớp bài toán cụ thể.
2
CHƯƠNG 1: TỔNG QUAN VỀ LÝ THUYẾT XỬ LÝ SONG SONG
1.1 Phân loại các kiến trúc hệ vi xử lý song song
1.1.1 Kiến trúc hệ vi xử lý theo cách thông thường – đơn chỉ thị đơn dữ
liệu (SISD)
Đây chính là kiểu kiến trúc Von Neuman cho hệ vi xử lý tuần tự thông
thường, có ưu điểm là đơn giản cả về cấu trúc phần cứng và phần mềm hệ

các bộ nhớ ở cấp i+1. Gọi c
i
, t
i
và s
i
tương ứng là chi phí trên một byte, thời
gian truy nhập trung bình và kích thước bộ nhớ tổng cộng ở cấp i, ta có quan
hệ giữa các cấp i và i+1 như sau:
• Về chi phí trên một byte nhớ: c
i
> c
i+1
• Về thời gian truy nhập trung bình: t
i
< t
i+1
• Về kích thước bộ nhớ: s
i
< s
i+1
Như vậy bộ nhớ ở cấp i có chi phí cao hơn nhưng thời gian truy nhập
ngắn hơn (nhanh hơn) và có kích thước nhỏ hơn bộ nhớ ở cấp i+1. Bộ nhớ
cấp 1 là bộ nhớ gắn liền với mỗi bộ xử lý và được gọi là bộ nhớ cục bộ (bộ
nhớ cache).
1.2.1.2 Tối ưu hóa phân cấp bộ nhớ
Vấn đề đặt ra trong thiết kế một phân cấp bộ nhớ điển hình là việc tối
ưu hóa để giảm đến thấp nhất thời gian truy nhập phân cấp hiệu dụng T với
chi phí hệ thống bộ nhớ cho trước là C
0

> 0 với i = 1, 2, …, n. Trong thực tế, các ràng buộc về chi
phí bao gồm cả chi phí của mạng liên kết bộ xử lý – bộ nhớ.
1.2.1.3 Các phương pháp địa chỉ hóa cho bộ nhớ chính
Có hai phương pháp phân chia các địa chỉ giữa các module nhớ. Một
phương pháp, gọi là đan xen bậc cao, phân chia địa chỉ trong M = 2
m
module
sao cho mỗi module i, với
0 1i M
≤ ≤ −
, chứa các địa chỉ liên tiếp
.2
n m
i
−
đến
( )
1 .2 1
n m
i
−
+ −
. Trong đó m bit cao được sử dụng để chọn module còn n – m bit
thấp được sử dụng để chọn địa chỉ bên trong module (hình 1.5).
4
Hình 1.5: Đan xen bậc cao
Hình 1.6: Đan xen bậc thấp
Phương pháp thứ hai, đan xen bậc thấp, phân chia địa chỉ sao cho các
địa chỉ kế tiếp được đặt trong các module kế tiếp. Trong đó m bit thấp của địa
chỉ được sử dụng để chọn module, trong khi n – m bit cao chọn địa chỉ bên

1.3.1 Mô hình đa máy tính
Mô hình đa máy tính gồm có một số máy tính Von Neumann (hoặc
những nút), được liên kết thông qua mạng. Mỗi máy tính thực hiện chương
trình riêng của mình. Chương trình này có thể truy nhập bộ nhớ cục bộ và có
thể gửi và nhận những thông báo thông qua mạng.
1.3.2 Các mô hình hệ vi xử lý song song khác
Ngoài mô hình đa máy tính, các mô hình khác đối với hệ vi xử lý song
song đã được nghiên cứu phát triển. Ở đây ta xem xét ba mô hình điển hình
ngoài mô hình đa máy tính. Trong hình vẽ này, kí hiệu P biểu thị một bộ xử lý
độc lập. Đầu tiên, trong hình 1.13a, là một máy tính kiểu MIMD có bộ nhớ
phân tán được liên kết với nhau như một mạng lưới (mesh). Trong đó mỗi bộ
xử lý có bộ nhớ phân tán riêng. Hình 1.13b là mô hình bộ đa xử lý với bộ nhớ
chia sẻ. Trong đó, các bộ xử lý truy nhập tới bộ nhớ chung, thông qua một
bus. Để nâng cao hiệu quả và giảm thời gian truy nhập bộ nhớ, các bộ nhớ
7
cache cho mỗi bộ xử lý được thiết kế để lưu trữ các dữ liệu thường xuyên
được sử dụng. Và thứ ba là mô hình đa xử lý với các bộ xử lý được liên kết
qua một mạng cục bộ, ở đây là mạng Ethernet (hình 1.13c).
(a)
(b)
(c)
1.3.3 Các mô hình hệ vi xử lý song song chuyên dụng trên cơ sở bộ xử lý
NM6403
Các hệ vi xử lý song song chuyên dụng tốc độ cao có thể được xây
dựng trên cơ sở bộ xử lý NM6403 kết hợp với các bộ xử lý tín hiệu số
TMS320C40, trong đó TMS320C40 đóng vai trò như các nút chuyển mạch.
Kiến trúc này cho phép nâng cao mạnh mẽ hiệu năng của hệ thống, đặc biệt
trong các ứng dụng chuyên biệt yêu cầu tốc độ tính toán cực nhanh với độ
chính xác cao. Hình 1.15 sau đưa ra hai mô hình kiến trúc theo nguyên tắc
này.

các pipeline chức năng, các phần tử xử lý và các bộ đếm thanh ghi phục vụ
cho việc thực hiện các thao tác vectơ. Nói chung, xử lý vectơ cho hiệu quả
cao và tốc độ xử lý nhanh hơn xử lý vô hướng.
Một trong những ưu điểm của xử lý vectơ so với xử lý vô hướng là
giảm được các tiếp đầu phần mềm (overhead) trong điều khiển vòng lặp.
2.1.3 Quá trình phát triển của xử lý vectơ và xu hướng hiện nay
Các thế hệ của máy tính vectơ chủ yếu thực hiện việc cải thiện về tốc
độ tính toán nhờ cải tiến cấu trúc hệ vi xử lý theo kiểu đường ống hay đa xử
lý. Bên cạnh đó, một hướng tiếp cận mới với các hệ vi xử lý vectơ đang được
nghiên cứu và thực hiện trên quan điểm nâng cao cả về tốc độ tính toán và
10
khả năng ứng dụng trong các lĩnh vực chuyên biệt, đó là kiến trúc kết hợp xử
lý vectơ và mạng Nơron: kiến trúc Neural-Matrix. Điều này bắt nguồn từ
nhận xét rằng mặc dù các thao tác tính toán trong xử lý vectơ cho phép tăng
được tốc độ tính toán một cách mạnh mẽ so với xử lý vô hướng song nếu các
tính toán vectơ được thực hiện ở dạng tường minh đầy đủ thì số phép tính cần
thực hiện vẫn còn lớn và thời gian thực thi còn lớn. Tốc độ tính toán và hiệu
năng hệ vi xử lý vectơ hoàn toàn có thể tăng lên hơn nữa nếu bộ xử lý vectơ
có khả năng thích nghi theo kiểu trí tuệ nhân tạo trong các thao tác tính toán
vectơ.
2.2 Hệ vi xử lý vectơ MC431
2.2.1 Giới thiệu chung về hệ vi xử lý vectơ MC431
Hệ vi xử lý vectơ MC431 được hãng Module (Nga) công bố và đưa ra
thị trường năm 2003, là một hệ vi xử lý vectơ tốc độ cao, giá thành hợp lý
được thiết kế cho nhiều chức năng hệ thống khác nhau, đặc biệt hiệu quả
trong các ứng dụng về xử lý tín hiệu số, xử lý ảnh-video, mạng Nơron và các
tính toán kiểu vectơ-ma trận. Tốc độ của MC431 là 120 MOPS (Million
Operations per Second: Triệu phép tính trong 1 giây) với các thao tác vô
hướng và 960 MMAC (Million Multiplication and Accumulation per Second:
Triệu phép nhân và tích lũy trong 1 giây) với các thao tác vectơ.

(VALU). Khối OU được sử dụng để xử lý các thao tác nhân – cộng, số học-
logic, phép hoán vị trên các vectơ dữ liệu đóng gói.
13
2.3.2.1 Ma trận hoạt động
Đây là một khối thao tác thực hiện các phép nhân – cộng và chuyển vị.
Đặc biệt, thao tác tích lũy trọng số thực hiện tại ma trận hoạt động có ý nghĩa
quan trọng trong các ứng dụng tính toán của NM6403.
2.3.2.2 Ma trận phụ
Ma trận phụ được sử dụng để tải trước và lưu trữ các trọng số sẽ được
sử dụng cho ma trận hoạt động.
Hình 2.7: Sơ đồ khối bộ xử lý vectơ trong NM6403
2.3.2.3 Khối số học – logic vectơ (VALU)
Khối này thực hiện các tính toán số học và logic trên các từ dữ liệu
đóng gói. Các tính toán được thực hiện đồng thời trên tất cả các phần tử của
từ dữ liệu đóng gói.
14
2.3.2.4 Bộ đệm các trọng số kiểu FIFO (wfifo)
Được sử dụng để lưu trữ các trọng số được chuyển từ bộ nhớ ngoài vào
ma trận phụ, như một bộ đệm giữa bộ nhớ ngoài và ma trận phụ.
2.3.2.5 Bộ đệm – bộ tích lũy kiểu FIFO (afifo)
Đây là một hàng đợi kiểu FIFO dung lượng 32 từ 64 bit. Nó được sử
dụng là bộ đệm dích của bất kỳ thao tác nào trong VU.
2.3.2.6 Bộ đệm – bộ nhớ trong kiểu FIFO (ram)
Được sử dụng như một trong các bộ đệm đầu vào cho ma trận hoạt
động hay khối VALU.
2.3.2.7 Khối đặt mặt nạ (MAU: Mask Application Unit)
Khối này được sử dụng để đặt mặt nạ tới các vectơ dữ liệu đầu vào.
2.3.3 Các thanh ghi trong bộ xử lý NM6403
Bộ xử lý NM6403 chứa 3 tệp thanh ghi sau:
• Tệp thanh ghi chính

3.1 Xử lý tín hiệu số theo phương pháp FHT
3.1.1 Các phép biến đổi trong xử lý tín hiệu số
Các phép biến đổi Fourier (FT: Fourier Transform) và biến đổi Fourier
rời rạc (DFT: Discrete Fourier Transform) được sử dụng rộng rãi trong xử lý
tín hiệu số. Đặc biệt là, việc xuất hiện thuật toán nhanh cho DFT, được gọi là
biến đổi Fourier nhanh (FFT: Fast Fourier Transform), đã tạo ra một bước
nhảy vọt trong lĩnh vực phân tích, thiết kế và thực hiện các bài toán xử lý tín
hiệu số.
Biến đổi FHT đặc biệt hiệu quả so với các phép biến đổi khác nhờ sự
đơn giản trong tính toán do các phần tử trong ma trận chỉ gồm các con số 1 và
-1; thời gian xử lý ngắn; dễ dàng trong thực hiện phần cứng và khả năng bền
vững trước các tác động bên ngoài cũng như các thao tác xử lý ảnh như nén
ảnh, thay đổi kích thước ảnh. Ngoài ra, FHT còn được ứng dụng trong công
nghệ trải phổ đa truy nhập phân chia theo mã CDMA (Code Division
Multiple Access) để tạo các mã người dùng trực giao hoàn toàn.
3.1.2 Ma trận Hadamard và phép biến đổi Hadamard
Ma trận Hadamard được định nghĩa dưới dạng hồi qui như sau
1 1
1
1 1
2
 
=
 
−
 
2
H
1
2

N
=
N
x H y
3.1.3 Biến đổi Hadamard nhanh (FHT)
Tính toán cho thấy, tương tự như với DFT, số phép tính cần thực hiện
của DHT là N
2
(N là độ dài của các vectơ đầu vào và vectơ kết quả). Hiệu quả
của thuật toán FHT so với DHT thể hiện ở chỗ: số phép tính cần thực hiện
giảm đi chỉ còn Nlog
2
N (rõ ràng sẽ số phép tính sẽ giảm đi rất nhiều khi N
lớn).
Thuật toán tính FHT đối với ma trận Hadamard bậc N (gọi là FHT N
điểm) có thể được tóm tắt như sau:
 Bước 1: Vectơ dữ liệu đầu vào với chiều dài N đầu tiên được
chia thành N/2 khối, mỗi khối gồm 2 phần tử, thực hiện các phép
tính trên các khối này theo các đẳng thức (1) và (2).
 Bước 2: Vectơ đầu vào chính là vectơ kết quả ở bước 1. Vectơ
này được chia thành N/4 khối, mỗi khối gồm 4 phần tử. Thực
hiện các phép tính trên các khối này theo các đẳng thức (3) và
(4).
 Tại bước k bất kỳ thực hiện tính toán như chỉ ra trong hình 3.1,
tức là tại bước này nỗi phần tử tương tác với phần tử cách nó 2
k-1
phần tử. Lặp lại các bước trên đến bước thứ n =log
2
N. Kết quả
cuối cùng thu được là vectơ có chiều dài N, là biến đổi

hai loại, một loại bền vững với các tác động sao chép trái phép và loại thứ hai
lại có tính chất hoàn toàn đối lập: dễ bị phá hủy trước các tác động trên.
Cũng có thể chia các hệ thống giấu tin theo đặc tính nhìn thấy, một loại
cần được che giấu để chỉ có một số người tiếp xúc với nó có thể thấy được
thông tin (kiểu vô hình); loại thứ hai thì ngược lại, cần được mọi người nhìn
thấy (kiểu hữu hình).
3.2.4 Kỹ thuật giấu thông tin trong ảnh số sử dụng FHT
Có 2 nhóm phương pháp dấu tin trong ảnh số:
- Nhóm các phương pháp trên miền không gian: lượng giấu tin thấp, kém
bền vững
- Nhóm các phương pháp giấu ảnh trên miền biến đổi: (DFT, DWT,
DHT) có khả năng cho dung lượng thông tin giấu cao và khả năng bền
vững trước các tác động của bên ngoài cũng như các thao tác xử lý ảnh
19
Kí hiệu giá trị các điểm ảnh của ảnh gốc là B và thông tin cần dấu là
B
W
. Cả hai đều được biến đổi FHT để được các giá trị hệ số biến đổi tương
ứng là f và w. Bộ mã hóa sử dụng các hệ số này để mã hóa được giá trị hàm
mã hóa: e = α . w . f
Trong đó ỏ là hệ số của bộ mã hóa, chẳng hạn chọn ỏ = 0,1. Sau bộ
cộng ta được hàm f
W
:
f
W
= f + α . w . f
Và sau biến đổi IFHT của f
w
thu được B

20
3.3 Lập trình xử lý tín hiệu số theo phương pháp FHT trên hệ xử lý vectơ
MC431
Bài toán lập trình tính FHT 256 điểm trên hệ xử lý vectơ MC431 được
đặt ra với các thông số sau đây:
• Dữ liệu đầu vào là một vectơ có chiều dài N = 256. Mỗi phần tử
của vectơ là một số nguyên có dấu được biểu thị bằng 1 Byte (8
bit).
• Kết quả của FHT là một vectơ có chiều dài N = 256. Mỗi phần tử
của vectơ là một số nguyên có dấu được biểu thị bằng 16 bit
(kiểu từ ngắn).
• Số bước tính toán là 8 (2
8
= 256).
3.3.1 Thực hiện 3 bước đầu tiên của FHT 256 điểm
Hình 3.4: Quá trình chia ma trận Hadamard bậc 8 thành hai ma trận con
Các tính toán được thực hiện theo trình tự sau:
 Nạp ma trận con các trọng số Hadamard thứ nhất vào ma trận
hoạt động của bộ xử lý.
 Tính các từ long chẵn của vectơ kết quả. Các kết quả được tích
lũy trong bộ đệm afifo. Dung lượng của afifo là 32 từ long (64
bit).
 Lưu trữ các kết quả tính được trong bước trên vào các vị trí chẵn
của mảng kết quả.
21
 Đồng thời nạp các trọng số mới tiếp theo vào ma trận hoạt động.
 Thực hiện các tính toán cho các từ long lẻ và lưu các kết quả vào
các vị trí lẻ của mảng kết quả.
Sau đây ta sẽ lần lượt thực hiện lập trình tính toán cho các bước trên.
3.3.1.1 Nạp trọng số vào ma trận hoạt động

 File chương trình chính C++ hadamard.cpp để khởi tạo dữ liệu
và chứa các lệnh gọi các thủ tục assembly trên.
Kết quả chạy debug cho biết số chu kỳ sử dụng trong tính toán FHT
256, được xác định bằng hiệu các giá trị của Timer 1 lúc bắt đầu và kết thúc
chương trình tính FHT 256. Giá trị thanh ghi t1 (của Timer 1) lúc bắt đầu tính
toán là 711h và khi kết thúc là 8BBh nên số chu kỳ được sử dụng là:
8BBh – 711h = 1AAh = 426 chu kỳ
Tần số clock của MC431 là 40MHz nên thời gian một chu kỳ là:
1/(40.10
6
) = 25.10
-9
s = 25 ns
23
Do đó, thời gian chạy chương trình FHT 256 điểm trên MC431 là:
426.25 ns = 10650 ns = 10,65 µs
3.3.4 Đánh giá kết quả
Hiệu năng hiệu dụng của bộ xử lý là:
8 phép tính x 256 phần tử / 426 chu kỳ = 4,8 phép tính số học / chu kỳ
Tuy nhiên số phép tính trong thực tế khác so với lý thuyết. Vì 3 bước
tính toán đầu tiên thực hiện trên cơ số 8 còn 5 bước tính toán tiếp theo thực
hiện trên cơ số 32 nên tổng số phép tính thực hiện trên mỗi phần tử là 40. Và
hiệu năng thực tế của NM6403 là: 40 phép tính x 256 phần tử / 426 chu kỳ =
24,0 phép tính số học / chu kỳ
Để đánh giá một cách cụ thể hơn về hiệu năng của hệ vi xử lý vectơ
MC431, ta có thể so sánh thời gian thực thi cùng một chương trình tính toán
giữa MC431 máy tính PC có kiến trúc kiểu Pentium.
Bộ xử lý NM6403
Pentium II
450 MHz