BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

NGUYỄN VĂN CƯỜNG

NGHIÊN CỨU NoC CẤU HÌNH LẠI ĐƯỢC TRÊN FPGA VÀ PHÁT TRIỂN
THUẬT TOÁN ÁNH XẠ ĐỘNG ỨNG DỤNG TRÊN NỀN TẢNG NoC

Chuyên ngành: Kỹ thuật điện tử
Mã số: 62520203

TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT ĐIỆN TỬ

Hà Nội – 2017


Công trình này được hoàn thành tại:
Trường Đại học Bách khoa Hà Nội

Người hướng dẫn khoa học:
PGS.TS. PHẠM NGỌC NAM

Phản biện 1:
Phản biện 2:
Phản biện 3:

Luận án được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ
cấp Trường họp tại Trường Đại học Bách khoa Hà Nội
Vào hồi … giờ … , ngày … tháng … năm 2017

Có thể tìm hiểu luận án tại thư viện:

hình lại trong thiết bị luôn có giới hạn. Do vậy, cần lựa chọn thêm một giải pháp quản lý động cho
hệ thống. Một trong những giải pháp quan trọng và rất linh hoạt đó là kỹ thuật ánh xạ ứng dụng
động. Kỹ thuật này kết hợp với khả năng cấu hình lại từng phần động của thiết bị phần cứng như
FPGA sẽ tạo ra một giải pháp hứa hẹn để giải quyết yêu cầu triển khai nhiều ứng dụng có thể điều
chỉnh được mức chất lượng lên nền tảng có tài nguyên tái cấu hình hạn chế [8, 86].
Hơn nữa, do độ phức tạp của các thiết bị nhúng hiện đại ngày càng tăng, một số lượng ngày
càng nhiều ứng dụng với chất lượng dịch vụ (QoS: Quality of Service) khác nhau có thể được triển
khai lên thiết bị, thường là trong một môi trường các nền tảng cấu hình lại không đồng nhất. Bởi vì
một nền tảng cấu hình lại không đồng nhất với sự linh hoạt của các bộ xử lý nhúng và hiệu quả tính
toán của một số vùng cấu hình lại đã được chứng minh là có nhiều ưu điểm hơn so với nền tảng
đồng nhất [1, 49]. Trong một nền tảng như vậy, các bộ xử lý nhúng thường được sử dụng để quản lý
và thực hiện một số tác vụ phức tạp thấp trong khi các vùng cấu hình lại được sử dụng để tăng tốc
độ tính toán cho các tác vụ phức tạp. Khả năng cấu hình động cho phép nền tảng thích nghi với các
yêu cầu xử lý thay đổi của các ứng dụng.
Mặt khác, các yêu cầu truyền thông ngày càng gia tăng trong một hệ thống trên chip (SoC:
System on Chip) phức tạp như nền tảng đa lõi không đồng nhất cấu hình lại được. Do vậy việc lựa
chọn một cơ sở hạ tầng truyền thông phù hợp là cần thiết. Điều này phải đảm bảo các kết nối cần
thiết với một QoS được xác định trước, chẳng hạn như thông lượng hoặc trễ tối đa. Tuy nhiên, trong
nhiều trường hợp mức ưu tiên của các ứng dụng chưa được biết trước tại lúc thiết kế mà chỉ biết
được khi chúng được triển khai vào hệ thống tại thời gian chạy. Trong trường hợp này, các yêu cầu


2
truyền thông hiệu quả không được biết đến tại thời gian tổng hợp, do đó một cơ sở hạ tầng truyền
thông linh hoạt sẽ được lựa chọn. Hơn nữa, một SoC phức tạp còn yêu cầu tích hợp một số lượng
lớn các lõi IP (Intellectual Property) lên nó, vì vậy, một cơ sở hạ tầng truyền thông hiệu năng cao,
khả năng xử lý song song để kết nối các IP khác nhau cần được sử dụng. Với yêu cầu này, các kiến
trúc truyền thống như Bus chia sẻ hay kết nối trực tiếp điểm-điểm không thể áp dụng được. Kiến
trúc mạng trên chip (NoC: Network on Chip) ra đời và xem như một giải pháp thay thế cho kiến
trúc Bus và kết nối điểm-điểm theo hướng công nghệ này. Kiến trúc NoC cung cấp một cơ sở hạ

Đề xuất kiến trúc NoC hiệu năng cao bao gồm kiến trúc bộ định tuyến và bộ giao tiếp
mạng.
(ii)
Xây dựng nền tảng phần cứng đa lõi linh hoạt có khả năng cấu hình lại được từng phần
trên FPGA dựa trên kiến trúc NoC. Nền tảng này cho phép thay đổi tự động một số mô
đun trong lớp truyền thông hoặc lớp tính toán của NoC tại thời gian chạy để thích nghi
với các yêu cầu thay đổi của các ứng dụng.
(iii) Xây dựng và đề xuất các thuật toán cho bài toán ánh xạ các ứng dụng có thể điều chỉnh
mức chất lượng vào nền tảng phần cứng cấu hình lại được dựa trên NoC.
Phạm vi nghiên cứu:


3
Nghiên cứu mô hình kiến trúc NoC sử dụng cấu hình lưới hai chiều, kỹ thuật điều khiển
luồng wormhole, kênh ảo và giải thuật định tuyến XY để xây dựng mô hình truyền
thông NoC có hiệu năng cao.
(ii)
Nghiên cứu công nghệ FPGA của Xilinx, công nghệ cấu hình lại từng phần động của
FPGA để phát triển nền tảng phần cứng có khả năng cấu hình lại được lớp truyền thông
hoặc lớp tính toán.
(iii) Nghiên cứu bài toán ánh xạ các ứng dụng động có thể điều chỉnh mức chất lượng vào
nền tảng phần cứng đa lõi cấu hình lại được dựa trên NoC với giả thiết kiến trúc lớp
truyền thông là cố định và chỉ cấu hình lại lớp tính toán (các PE) của NoC để thích nghi
với sự chuyển đổi từ ứng dụng này đến ứng dụng khác lên nền tảng phần cứng hoặc sự
thay đổi mức chất lượng của các ứng dụng. Ngoài ra, luận án cũng chỉ tập trung vào
nghiên cứu mô hình ứng dụng dưới dạng đồ thị tác vụ.
Phương pháp nghiên cứu
Đầu tiên, phương pháp điều tra và phân tích dựa trên sách, tạp chí và các nguồn tài liệu khác từ
Internet sẽ được sử dụng. Các ưu điểm và hạn chế của các vấn đề nghiên cứu liên quan đến luận án
sẽ được chỉ ra. Từ đó, tác giả sẽ đề xuất một số mô hình và thuật toán cho vấn đề nghiên cứu.

dòng dữ liệu trong mạng. Đóng vai trò là hạt nhân trong NoC với mỗi mô hình NoC khác nhau, bộ


4
định tuyến được thiết kế riêng để thực hiện thuật toán định tuyến, cơ chế điều khiển luồng riêng
biệt.
Liên kết vật lý (Physical link): Là các kết nối vật lý giữa các bộ định tuyến trong mạng NoC.
Liên kết bao gồm các đường truyền dữ liệu và các tín hiệu điều khiển/báo hiệu.
Cấu hình mạng (Topology): Là cấu trúc hình học của NoC, cấu trúc hình học này sẽ quyết định
cách liên kết giữa các bộ định tuyến với nhau, giải thuật định tuyến và thậm chí cả cơ chế điều
khiển luồng.
Định tuyến (Routing): Là cơ chế tìm đường đi cho gói tin (Packet) từ tài nguyên nguồn đến tài
nguyên đích thông qua các kết nối trong mạng.
Điều khiển luồng (Flow control): Là cơ chế cấp phát tài nguyên bộ đệm, liên kết cho gói tin khi
gói tin đang truyền trong mạng.
Độ trễ (Latency): Là thời gian cần thiết để truyền một gói tin đi từ nguồn đến đích. Trong NoC,
có nhiều yếu tố ảnh hưởng tới độ trễ bao gồm trễ do định tuyến, độ chiếm dụng kênh, trễ do tranh
chấp tài nguyên, thời gian ghép và tách gói tin (packetization and depacketization), thời gian ghép
và tách flit (flitization and deflitization), sự đồng bộ giữa các bộ định tuyến.
Băng thông (Bandwidth): Là tốc độ cao nhất của luồng thông tin trong mạng được đo bằng số
bit/giây.
Thông lượng (Throughput): Là tổng số gói tin đến được đích của chúng trên mỗi đơn vị thời
gian.

IP core
(1,1)

Router

IP core

I

IP core
(1,0)

Router

Physical links

Router

Router

N
I

Router

N
I

IP core
(0,2)

N
I

IP core
(0,1)


assignment) đã được chứng minh là một vấn đề NP-hard [31]. Không gian tìm kiếm tăng giai thừa
lần theo kích thước hệ thống. Ví dụ, một NoC có kích thước 8x8, theo lý thuyết có thể có 64!
trường hợp ánh xạ.
Tổng quát, nếu ánh xạ N tác vụ vào M nút mạng (NM) thì có thể có

M!
trường hợp
 M  N !

ánh xạ các tác vụ vào các nút của NoC. Trong trường hợp số tác vụ bằng số nút mạng (M=N) thì số
trường hợp ánh xạ trở thành M!. Ánh xạ có ảnh hưởng trực tiếp đến hiệu năng của NoC như độ trễ,
thông lượng, tiêu thụ điện năng, năng lượng, v.v. Vì vậy cần phải có các kỹ thuật ánh xạ hiệu quả
để tối ưu các thông số này. Kỹ thuật ánh xạ phụ thuộc vào các yếu tố sau đây:
(i) Mô hình ứng dụng (ví dụ: Task Graph [25], Data Flow Graph [88], v.v.)
(ii) Mô hình kiến trúc nền tảng phần cứng (ví dụ: Nền tảng đồng nhất, không đồng nhất, số
lượng PE và loại PE, v.v.)
(iii) Các tham số ràng buộc của ứng dụng (ví dụ: Hiệu năng tính toán, trễ truyền thông, mức
chất lượng, v.v.)
(iv) Mô hình thực hiện truyền thông giữa các PE (ví dụ: Thời gian thực hiện, năng lượng tiêu
thụ, v.v.)
(v) Ước lượng thời gian thực hiện trên các PE khác nhau.
Bài toán ánh xạ các tác vụ của ứng dụng lên nền tảng NoC có thể được thực hiện tại thời gian
thiết kế (design-time) hoặc sau khi thiết kế tức là khi hệ thống đang hoạt động (run-time). Đối với
kỹ thuật ánh xạ tại thời gian thiết kế hay gọi là ánh xạ tĩnh thì kiến trúc nền tảng và ứng dụng đã
được biết trước, vì vậy chúng không phù hợp cho việc thêm các ứng dụng mới vào hệ thống tại thời
gian chạy. Đối với kỹ thuật ánh xạ tại thời gian chạy hay gọi là ánh xạ động thì gần như các ứng
dụng đều có thể chạy trên hệ thống khi hệ thống đang hoạt động, kỹ thuật này là một giải pháp phù
hợp cho việc triển khai nhiều ứng dụng lên hệ thống có tài nguyên giới hạn. Sau khi ánh xạ các tác
vụ lên hệ thống thì một số tác vụ đã được ánh xạ có thể được điều chỉnh vị trí, nếu yêu cầu người
dùng thay đổi hoặc có ứng dụng mới đưa vào hệ thống.

Những vấn đề nêu trên chỉ có thể được giải quyết bằng các kỹ thuật ánh xạ tại thời gian chạy.
CHƢƠNG 2
PHÁT TRIỂN NỀN TẢNG PHẦN CỨNG CẤU HÌNH LẠI ĐƢỢC CHO NoC
Thiết kế bộ định tuyến cho NoC
Mạng trên chip được đề xuất như một giải pháp cho truyền thông giữa các IP trong thiết kế các
hệ thống trên chip phức tạp. Tránh bế tắc, cắt giảm tắc nghẽn để tăng hiệu năng cho mạng là những
thử thách lớn khi thiết kế NoC bởi vì chúng ảnh hưởng trực tiếp đến hiệu năng toàn mạng. Để giải
quyết các vấn đề này, các bộ định tuyến thường sử dụng kiến trúc kênh ảo đều tại mỗi cổng. Trong
mục này, tác giả đề xuất một kiến trúc cho bộ định tuyến sử dụng điều khiển luồng wormhole kết
hợp với số lượng kênh ảo không đều trên cổng tại ngõ ra để cắt giảm chi phí nhưng vẫn đảm bảo
“deadlock free” và hiệu năng trong trường hợp lưu lượng dữ liệu đi qua mạng là cao nhất. Chi phí
và hiệu năng của bộ định tuyến đã đề xuất sẽ được phân tích, đánh giá và so sánh với các bộ định
tuyến sử dụng 2 và 4 kênh ảo.
2.1.1. Đề xuất kiến trúc bộ định tuyến
Kiến trúc bộ định tuyến sử dụng cấu hình mạng hai chiều dạng lưới (2D-Mesh), chuyển mạch
gói, điều khiển luồng wormhole kết hợp với kênh ảo không đều trên cổng và thuật toán định tuyến
XY. Bộ định tuyến có 5 cổng gồm cổng Bắc (N), Nam (S), Đông (E), Tây (W) và cổng nội bộ L.
Tại mỗi cổng, dữ liệu có thể truyền theo hai hướng và có độ rộng là 34 bit. Kích thước của mỗi flit
là 34 bit gồm 32 bit dữ liệu và 2 bit còn lại sử dụng cho nhận dạng loại flit. Có 3 loại flit: Flit tiêu
đề (header flit), flit thân (body flit) và flit đuôi (end flit).
Kiến trúc đề xuất của bộ định tuyến như Hình 2.3, bao gồm 5 khối chính: Bộ đệm ngõ vào
(FIFO), bộ giải mã flit (Flit decoder), chuyển mạch (Switch), kênh ảo và bộ phân xử (Arbiter).
Bộ đệm ngõ vào dùng để lưu trữ tạm thời các flit.
Bộ giải mã flit thực hiện chức năng nhận, phân tích thông tin định tuyến trong flit tiêu đề và
đưa ra thông tin định tuyến đến các ngõ ra cho gói tin.
Chuyển mạch thực hiện chức năng kết nối đường chuyển dữ liệu đến đúng ngõ ra tương ứng
theo tín hiệu điều khiển từ khối giải mã flit.
Kênh ảo được thiết kế giống như các FIFO dùng để lưu trữ tạm thời các flit khi các flit chưa
được cấp phát kênh vật lý.
2.1.

E

Switch

34

ack_out
req_in

L
d_in
ack_out
req_in

S Flit
decoder

VC 0
VC 1
VC 2
VC 3

Arbiter
4 to1

VC 0
VC 1
VC 2
VC 3


VC 0
VC 1

Arbiter
2 to1

FIFO

L Flit
decoder

VC 0
VC 1
VC 2
VC 3

Arbiter
4 to1

34

N
d_out

req_out

FIFO
34

d_in

Các flit đi vào bộ đệm FIFO và được lưu trữ tạm thời tại đây. Các tín hiệu bắt tay req_in và
ack_out sẽ thông báo đến bên gửi tình trạng sẵn sàng ghi và ghi dữ liệu thành công vào FIFO. Tiếp
theo các flit sẽ được đưa vào bộ giải mã flit. Tại đây địa chỉ nguồn và địa chỉ đích chứa trong flit
tiêu đề được phân tích để đưa ra tín hiệu điều khiển hướng đi cho các flit. Tiếp theo bộ chuyển
mạch sẽ dựa vào các tín hiệu điều khiển được tạo ra từ bộ giải mã flit để tiếp tục chuyển dữ liệu đến
các ngõ ra và đưa vào các kênh ảo tương ứng. Cuối cùng, bộ phân xử sẽ lựa chọn và cấp phát kênh
vật lý cho flit để truyền các flit đến các bộ định tuyến đích đến khi toàn bộ gói tin được truyền
xong.
Điểm đặc biệt trong thiết kế này đó là việc bố trí các kênh ảo khác nhau tại các cổng nhằm tiết
kiệm tài nguyên phần cứng nhưng vẫn tránh được tắc nghẽn và đảm bảo được hiệu năng mạng bằng
cách kết hợp linh hoạt giữa việc sử dụng thuật toán định tuyến XY với việc bố trí số kênh ảo phù
hợp tại các cổng ngõ ra. Điều này có thể được giải thích như sau: Theo nguyên tắc hoạt động của
thuật toán định tuyến XY, khi chuyển các flit từ nguồn đến đích, đầu tiên các flit sẽ được truyền
theo phương X sau đó đến phương Y đến khi tìm đúng địa chỉ đích sẽ dừng. Do vậy, cổng ngõ ra E
sẽ nhận được dữ liệu từ các cổng ngõ vào W và L; cổng ngõ ra W sẽ nhận được dữ liệu từ cổng ngõ
vào E và L; cổng ngõ ra S sẽ nhận được dữ liệu từ các cổng vào N, E, W và L; cổng ngõ ra N sẽ
nhận được dữ liệu từ cổng ngõ vào S, E, W và L; cổng ngõ ra L sẽ nhận được dữ liệu từ các cổng
ngõ vào N, S, E và W. Dựa trên phân tích này, tác giả bố trí 4 kênh ảo tại các cổng ngõ ra N và S và
2 kênh ảo cho các cổng ngõ ra còn lại E và W.
2.1.2. Kết quả và đánh giá
2.1.2.1. Kết quả tổng hợp
Kiến trúc bộ định tuyến được mô hình hóa bằng ngôn ngữ phần cứng Verilog HDL và được
tổng hợp trên KIT FPGA Virtex-6 chip 6VLX240TFF156 bởi công cụ ISE (Integrated Software


8
Environment )14.1. Bảng 2.2 chỉ ra tài nguyên FPGA đã sử dụng khi tổng hợp. Kết quả tổng hợp
cho thấy bộ định tuyến đã đề xuất chiếm khoảng 0,48% Register và 0,88% LUT so với tổng tài
nguyên FPGA. Nếu so sánh với trường hợp bộ định tuyến sử dụng 2 kênh ảo thì số Register tăng
26,6% và số LUT tăng 19,5%. Tuy nhiên, khi so sánh với trường hợp 4 kênh ảo thì thiết kế đã đề


0,34

1399

0,46

1692

0,56

Slice LUTs

150720

1026

0,68

1274

0,85

1814

1,20

2.1.2.2. Kết quả mô phỏng
Độ trễ và thông lượng trung bình của mạng với kích thước 3x3 sử dụng bộ định tuyến chứa 1,
2, 4 kênh ảo và bộ định tuyến đã đề xuất sẽ được đánh giá và so sánh. Các thông số mô phỏng được

32 bits

core_req

wr_en_FFA empty_FFA full_FFA
release_FFA
release_FFB
pkt_size

full_FFA empty_FFA rd_en_FFA
release_FFA
release_FFB
A/B_select
Flit_type

C2R_WRITE_CTRL

C2R_READ_CTRL

state_FFA
core_req
state_FFB
ack_core
wr_en_FFB empty_FFB full_FFB

ack_core

Flitilizer

FIFO A


req_core

rd_en_FFA empty_FFA full_FFA
release_FFA
release_FFB
A/B_select

full_FFA empty_FFA wr_en_FFA
release_FFA
pkt_size
release_FFB
flit_en

R2C_READ_CTRL

R2C_WRITE_CTRL

state_FFA
Core_ack
state_FFB
req_core
rd_en_FFB empty_FFB full_FFB

De-flitilizer

FIFO A

state_FFA
state_FFB

tăng so với phiên bản sử dụng bộ đệm đơn, điều này có thể lý giải như sau: Xét về kích thước bộ
đệm, gần như không thay đổi vì bộ đệm kép được tách đôi từ bộ đệm đơn như đã trình bày trong
Mục 2.2.1 của luận án. Tuy nhiên, xét về mặt phức tạp của bộ điều khiển quá trình ghi/đọc trong
phiên bản dùng bộ đệm đơn và bộ đệm kép thì phiên bản sử dụng bộ đệm kép có độ phức tạp lớn
hơn. Đó cũng là nguyên nhân làm tăng tài nguyên sử dụng của NI sử dụng bộ đệm kép.
Bảng 2.4. Kết quả tổng hợp trên FPGA
Tổng hợp sử dụng tài nguyên
Logic
Utilization

NI - 1 FIFO
Sẵn có

Đã sử
dụng

%

Tác giả
Đã sử
dụng

%

Slice Registers

301440

202



10
Kết quả tổng hợp cho thấy rằng tốc độ hoạt động của NI do tác giả đề xuất lớn hơn so với tốc
độ hoạt động của NI sử dụng một bộ đệm và nghiên cứu trong [4]. Nó được thể trong Bảng 2.5. Trễ
của bộ giao tiếp mạng sử dụng bộ đệm kép thấp hơn trễ trong NI sử dụng bộ đệm đơn.
Bảng 2.5. Tốc độ hoạt động của các bộ giao tiếp mạng
Các nghiên cứu
Tốc độ (Mhz)

NI-1
FIFO
302

[4]
MNI
310

Tác giả
SNI
252

397

Phát triển nền tảng phần cứng cấu hình lại từng phần động
Trong giới hạn của nghiên cứu này, tác giả sẽ tập trung vào phát triển một nền tảng mẫu có thể
thực hiện theo hai giải pháp. Giải pháp đầu tiên, nền tảng có thể cấu hình lại cơ sở hạ tầng truyền
thông mạng, có thể cấu hình bộ định tuyến hoặc các thành phần trong bộ định tuyến như bộ đệm,
chuyển mạch, bộ phân xử, v.v. hoặc cấu hình cả cấu hình mạng để tối ưu kiến trúc truyền thông,
trong khi duy trì cố định vị trí của các PE (lõi tính toán). Giải pháp này hoàn toàn phù hợp với kịch
bản các ứng dụng chạy trên hệ thống có tải làm việc thay đổi động (ví dụ: thay đổi hiệu năng, thay



11
SDRAM DDR3 để ghi vào ICAP, tiếp theo dữ liệu sẽ được đọc từ ICAP để ghi vào bộ nhớ cấu hình
của FPGA.
Flash
Memory

SysACE
CompactFlash

Timer

Microblaze
Processor

Phần không
cần cấu
hình

AXI/PLB BUS

HWICAP

Uart

DDR3

Phần cấu
hình

%
dụng
4249
1,41

AXI
Sử
%
dụng
4257
1,41

AXI + DDR3
Sử
%
dụng
15347
5,10

Register

301440

LUT

150720

4243

2,82

bộ nhớ RAM DDR3 nên tốc độ cấu hình được cải thiện hơn 5 lần so với trường hợp các file cấu
hình được đọc từ bộ nhớ ngoài CF vì độ rộng bus dữ liệu của bộ nhớ RAM DDR3 lớn hơn. Tuy
nhiên, hệ thống này tiêu tốn khá nhiều tài nguyên. Do vậy, tùy theo yêu cầu về QoS của từng miền
ứng dụng mà chúng ta có thể lựa chọn loại hệ thống cấu hình phù hợp để thực hiện.


12
Bảng 2.7. Thời gian và tốc độ cấu hình của hệ thống
Thông số cấu hình
PLB
Bitstream size (Kb)

1 Router
mạng 2x2

Cấu hình buffer
AXI

AXI+DDR3

Cả mạng
2x2

1 PE của
mạng 2x2

AXI+DDR3

36


3,070

3,070

3,070

3,070

CHƢƠNG 3
TRIỂN KHAI CÁC ỨNG DỤNG CÓ THỂ ĐIỀU CHỈNH MỨC CHẤT
LƢỢNG VÀO NỀN TẢNG CẤU HÌNH LẠI ĐƢỢC DỰA TRÊN NoC
TẠI THỜI GIAN CHẠY
Đặt vấn đề
Ngày nay, các thiết bị nhúng đang trở nên quan trọng trong cuộc sống của chúng ta. Xu hướng
triển khai nhiều ứng dụng và tích hợp nhiều tính năng lên chúng ngày càng gia tăng trong khi tài
nguyên của chúng luôn bị giới hạn. Điều này đòi hỏi người thiết kế phải có những giải pháp linh
hoạt và hiệu quả. Các FPGA hiện đại không ngừng tăng số lượng tài nguyên trên nó, giá thành tiếp
tục giảm, các tính năng mới được tích hợp đặc biệt là khả năng cấu hình lại từng phần động. Do
vậy, FPGA là một lựa chọn thích hợp để phát triển nhanh một nền tảng nhúng đa lõi linh hoạt và có
hiệu năng cao. Theo hướng này, một số hệ thống nhúng dựa trên FPGA đã được phát triển để hỗ trợ
cho các ứng dụng đa phương tiện và các ứng dụng xử lý tín hiệu [30, 38, 48, 54, 58]. Các ứng dụng
này thường yêu cầu cơ sở hạ tầng truyền thông hiệu năng cao và có khả năng xử lý dữ liệu nhanh.
Nhằm cung cấp một cơ sở hạ tầng truyền thông hiệu năng cao để kết nối các phần tử xử lý (PE)
khác nhau của một SoC phức tạp, mạng trên chip đã được đề xuất như là một thay thế cho các kiến
trúc truyền thống như Bus và kết nối điểm-điểm [9, 75]. Ngoài ra, một nền tảng cấu hình lại không
đồng nhất với sự linh hoạt của các bộ xử lý nhúng và hiệu quả tính toán của một số vùng cấu hình
lại được dựa trên NoC đã chứng minh là có nhiều ưu điểm hơn so với các nền tảng đồng nhất [1,
49]. Trong một nền tảng như vậy, các bộ xử lý nhúng thường được sử dụng để quản lý và thực hiện
một số tác vụ phức tạp thấp trong khi các vùng cấu hình lại trên FPGA được sử dụng để tăng tốc
tính toán cho các tác vụ phức tạp. Khả năng cấu hình động cho phép nền tảng FPGA thích nghi với






Mỗi đỉnh vk V là một tác vụ với bộ thông số tid , ttype , tcomp , treqcomp . Trong đó, tid là thông số
nhận dạng; ttype là kiểu tác vụ (tác vụ phần cứng tHW hoặc tác vụ phần mềm tSW ), các tác vụ phần
cứng được tạo ra từ ngôn ngữ phần cứng HDL và các tác vụ phần mềm được tạo ra từ ngôn ngữ lập
trình bậc cao như C/C++; tcomp là thời gian tính toán của tác vụ khi nó thực hiện trên tài nguyên
phần cứng hoặc phần mềm. Một tác vụ được thực hiện trên tài nguyên phần cứng sẽ có thời gian
tính toán nhỏ hơn khi nó thực hiện trên tài nguyên phần mềm [24, 69]; treqcomp là thời gian yêu cầu
tối thiểu để thực hiện hoàn thành một tác vụ trên tài nguyên phần cứng hoặc phần mềm.
Mỗi cạnh ers biểu diễn mối quan hệ giữa tác vụ vr và vs . Nó có các thông số như

t

comm

, treqcomm ,   ers   . Trong đó, tcomm là trễ truyền thông khi truyền các gói tin từ tác vụ vr đến

vs ; treqcomm là yêu cầu trễ truyền thông tối thiểu khi truyền các gói tin từ tác vụ vr đến vs ; và

  ers  là một hàm trọng lượng đại diện cho tốc độ truyền thông giữa các tác vụ.
3.2.1.2. Mô hình chất lượng
Giả sử có M ứng dụng A1 , A2 , A3 ,..., AM cùng chạy trên một thiết bị, mỗi ứng dụng Ai có N i
mức chất lượng Qi1 , Qi 2 , Qi 3 ,..., QiNi . Mỗi mức chất lượng yêu cầu một tập các tài nguyên bao gồm
thời gian tính toán, thời gian truyền thông, diện tích phần cứng và năng lượng. Mức chất lượng cao
hơn sẽ yêu cầu tài nguyên nhiều hơn [67, 69]. Ví dụ, giả sử ứng dụng A1 có các mức chất lượng

Q11  Q12  Q13    Q1N1 thì thời gian cần thực hiện ứng dụng tại mỗi mức chất lượng tương ứng

App1

App2

App3

úúú

AppM

Q11, Q12, …,Q1Ni
Quality levels
[10,15] V11
7

5

6

V12

V13

V14

[4,6]

[6,9]

[8,12]


physical connection

V12

RR

R

R

Reconfigurable platform

Hình 3.3. Mô hình hệ thống

3.2.2. Mô hình phần cứng
Nền tảng phần cứng được xem xét là một nền tảng cấu hình lại được không đồng nhất được
thực hiện trên FPGA Virtex-6 dựa trên mô hình NoC đã được phát triển trong Chương 2 (này tảng
này cũng có thể phát triển trên một KIT khác có tốc độ làm việc cao hơn như Zynq-7000). Nền tảng
bao gồm một vi xử lý nhúng ISP (Microblaze) và các PE phần cứng cấu hình lại được, chúng được
kết nối với nhau qua mạng truyền thông NoC. Trong chương này, tác giả chỉ xem xét tái cấu hình
cho các PE phần cứng, kiến trúc truyền thông của NoC được giữ cố định trong phần tĩnh của FPGA
(Hình 3.3). Mỗi PE có thể hỗ trợ tác vụ phần cứng hoặc phần mềm. Tác vụ phần mềm được thực
hiện trên ISP, trong khi tác vụ phần cứng được thực hiện trên các PE cấu hình lại được. Tác giả giả
định rằng mỗi PE phần cứng có khả năng hỗ trợ chỉ một tác vụ. Trong khi đó, vi xử lý nhúng ISP có
thể hỗ trợ một hoặc nhiều hơn một tác vụ và chịu trách nhiệm quản lý hệ thống bao gồm ánh xạ tác
vụ, lập lịch tác vụ, kiểm soát tài nguyên và điều khiển cấu hình lại.
Định nghĩa 2: Một nền tảng cấu hình lại dựa trên NoC được biểu diễn bởi một đồ thị
NoC  N  P, L  trong đó, P là tập các phần tử xử lý PE, và L là tập các kết nối vật lý giữa 2 bộ
định tuyến.

sẽ là:
Li

Li

r

s

tcommij    rstcommijrs  dist (( x, y ), (x', y'))

(3.2)

Trong đó,  rs  1 nếu có một kết nối giữa tác vụ vir và vis ,  rs  0 cho các trường hợp còn

lại. dist   x, y  ,  x’, y’   x ' x  y ' y là khoảng cách Manhattan (MD) từ PE pxy đến px ' y ' .

Tổng thời gian thực hiện của ứng dụng Ai tại mức chất lượng Qij được tính bởi công thức:

tij  tcompij  tcommij

(3.3)

Giả sử  i đại diện cho mức độ ưu tiên của ứng dụng. Lúc đó, bài toán ánh xạ có thể được xây
dựng như sau:
Giả sử có M ATG ứng dụng đưa vào hệ thống đồng thời hoặc tuần tự và trạng thái của nền
tảng phần cứng.
Tìm một hàm ánh xạ: A V , E   N  P, L  , Map  vik   pxy , vik V , pxy  P với các mục tiêu
B


p
 HW  HW
(3.6)
 tcompij  treqcompij

 tcommij  treqcommij
Cần lưu ý rằng, biểu thức (3.4) là mục tiêu chính của bài toán ánh xạ. Khi Bmax được tìm thấy,
biểu thức (3.5) sẽ được sử dụng để tìm một giải pháp vị trí đặt các tác vụ tối ưu.
3.3.
Các giải pháp cho bài toán ánh xạ các ứng dụng lên NoC tại thời gian chạy
3.3.1. Giải pháp tối ưu sử dụng thuật toán tìm kiếm đầy đủ
3.3.1.1. Thuật toán
Trong phần này, tác giả đề xuất giải pháp tối ưu đơn giản cho bài toán ánh xạ với việc xem xét
nền tảng phần cứng có kích thước nhỏ, số lượng ứng dụng triển khai lên nền tảng không lớn, số
mức chất lượng của mỗi ứng dụng nhỏ. Trong trường hợp như vậy, thuật toán tìm kiếm đầy đủ có
thể sử dụng để tìm ra giải pháp tối ưu cho bài toán ánh xạ đã được xây dựng như Mục 3.2.3 là hoàn
toàn khả thi. Mã của thuật toán tìm kiếm đầy đủ được trình bày như Thuật toán 1.


16
Thuật toán 1: Giải pháp tối ưu sử dụng thuật toán tìm kiếm đầy đủ
Input: A(V,E), N(P,L) // task vik V ; PE pxy  P
Output: tmpg (mapping A(V,E)  N(P,L))
1: BEGIN
2: Set benefit_max  0; time_min  ∞; tmpg  NULL;
3: Generate all possible mapping A(V,E)  N(P,L);
// number of hard task
3.3.1.2. Kết quả mô phỏng và đánh giá
Để đánh giá giải pháp đề xuất, một vài kịch bản mô phỏng sẽ được thực hiện. Trong giải pháp
này, một nền tảng NoC cấu hình lại được đã được trình bày ở Mục 3.2.2 với kích thước 3x3, bao
gồm 1 ISP và 8 vùng cấu hình lại sẽ được sử dụng. Có 3 ứng dụng tổng hợp được sử dụng trong mô
phỏng, đồ thị tác vụ của chúng được tạo ra bởi công cụ TGFF [25]. Trong đó, ứng dụng A1 có 4 tác
vụ và 3 mức chất lượng (Q11, Q12 và Q13). Ứng dụng A2 có 5 tác vụ và 4 mức chất lượng (Q21, Q22,
Q23 và Q24). Ứng dụng A3 có 3 tác vụ và 4 mức chất lượng (Q31, Q32, Q33 và Q34).
Với mỗi ứng dụng, thời gian tính toán của các tác vụ và trễ truyền thông giữa các cặp tác vụ
được tạo ra ngẫu nhiên cho mức chất lượng cao nhất. Đối với mức chất lượng thấp hơn, các thông
số này được tạo ra từ các giá trị cao nhất theo mô hình chất lượng đã được trình bày trong [69]. Bốn
kịch bản khác nhau được sử dụng để mô phỏng cho giải pháp đề xuất này như sau: (i) Mức độ ưu
tiên giữa các ứng dụng là bằng nhau; (ii) Ứng dụng A1 có mức ưu tiên cao nhất tiếp theo là ứng
dụng A2 và cuối cùng là ứng dụng A3; (iii) Ứng dụng A2 có mức ưu tiên cao nhất tiếp theo là ứng
dụng A3 và cuối cùng là ứng dụng A1; (iv) Mức độ ưu tiên của các ứng dụng lần lượt là A3 > A2 >
A1. Tất cả các kịch bản mô phỏng được thực hiện trên PC với các thông số: CPU core i3 – 2,6 Ghz ,
Bộ nhớ RAM - 4 GB, HDD – 720 GB. Các kết quả mô phỏng như vị trí đặt các tác vụ trên nền tảng
phần cứng, chất lượng đạt được của các ứng dụng và giá trị lợi ích tổng thể của các ứng dụng theo
các kịch bản được chỉ ra như Hình 3.5 và Bảng 3.3.


17

V32

V33

V13

V24


a) Kịch bản 1

b) Kịch bản 2

V24

V22

V21

V24

V33

V32

V25

V23

V12

V23

V21

V31

V11 V31
V14 V33


iii

iv

Kết quả

Ứng dụng Ai

Hệ số i

Mức chất
lƣợng

A1

0,33

Q11

A3

0,33

Q31

A2

0,33


Q13

A3

0,20

Q34

A3

0,50

Q31

A2

0,30

Q23

A1

0,20

Q13

Giá trị lợi
ích tổng thể
0,25


cho phép triển khai nhanh và linh hoạt các ứng dụng lên nền tảng. Ngoài ra, nó cũng có thể dễ dàng
thêm vào hệ thống các ứng dụng mới trong tương lai.
3.3.2.1. Chiến lược chọn vùng gần lồi
Chọn các vùng gần lồi liền kề trên nền tảng để ánh xạ các tác vụ của các ứng dụng vào chúng là
một giải pháp hiệu quả cho bài toán ánh xạ, nó đã được chứng minh trong các nghiên cứu [13-14].
Với một nền tảng phần cứng thực hiện trên FPGA có số lượng PE không lớn, tác giả đề
xuất một chiến lược chọn vùng gần lồi mới nhắm đến các mục tiêu như cấp phát tài nguyên linh
hoạt, thời gian thực hiện chọn vùng nhanh, giảm thiểu khoảng cách MD trung bình trong vùng
đã chọn, tạo ra các vùng lồi liền kề. Chiến lược này được chia thành 2 bước: Bước 1, tính toán
cấp phát số lượng PE cứng/mềm tương ứng với mức chất lượng của ứng dụng yêu cầu. Bước 2,
tìm một vùng gần lồi dựa trên phương pháp góc quét hình học và sử dụng thêm ràng buộc
khoảng cách MD tối thiểu để chọn một vùng gần lồi tối ưu cho ứng dụng.
 Cấp phát PE cứng/mềm cho ứng dụng theo yêu cầu chất lượng
Bước đầu tiên của chiến lược chọn vùng sẽ cấp phát số lượng PE cứng/ mềm tương ứng với
mức chất lượng mà ứng dụng yêu cầu. Nếu các ứng dụng đưa vào hệ thống một cách tự nhiên
khi đó số PE cứng/mềm sẽ được cấp phát theo một tỉ lệ công bằng sao cho tổng mức chất lượng
đạt được của các ứng dụng sau khi ánh xạ là cực đại. Ví dụ, số PE cứng/mềm được cấp phát dựa
theo độ phức tạp của ứng dụng. Nếu các ứng dụng vào được ưu tiên hoặc người dùng yêu cầu
một mức chất lượng nào đó, lúc đó số PE cứng sẽ được ưu tiên cấp phát nhiều hơn cho các ứng
dụng có độ ưu tiên hoặc yêu cầu chạy ở mức chất lượng cao hơn. Ví dụ, một ứng dụng yêu cầu
chạy ở mức chất lượng cao nhất, khi đó các PE cứng sẽ được cấp phát cho tất cả tác vụ của ứng
dụng.
 Chọn vùng gần lồi
Tiếp theo, một chiến lược chọn vùng mới dựa trên góc quét hình học kết hợp với khoảng
cách MD tối thiểu được sử dụng để chọn ra một vùng gần lồi cho ứng dụng vào. Chiến lược này
được mô tả như sau: Đầu tiên, tìm một PE trung tâm hoặc cận (gần) trung tâm làm tâm quét trên
nền tảng. Các góc quét khác nhau thay đổi từ 0->3600 có thể được sử dụng. Hướng quét có thể


19

sotf_PE = soft_PE_available;
13:
hard_PE =N_task - sotf_PE;
14:
else
15:
if hard_PE  hard_PE_available then
16:
sotf_PE = N_task - hard _PE_available;
17:
hard_PE =hard_PE_available;
18:
end if
19:
end if
20:
for mark_PE_angle to max_PE_angle do
21:
insert(PE in S to R);
22:
if enough sotf _PE and hard_PE then break;
23:
end if
24:
end for
25: update(mark_PE_angle, hard_PE_available, soft_PE_available);
26: update(remain_PE _angle);
27: end if
28: END


7: sort(task_vector_child, decrease_t_comm);
8: for all unmapped taski ϵ task_vector_child do
9:
id_pe_map = findPE_1_hop(task_cur,tile_info);
10: if id_pe_map != -1 then
11:
map_task_pe(taski, id_pe_map);
12: end if
13: end for
14: for all unmapped taski ϵ task_vector_child do
15: id_pe_map = pe_nearest (taski,tile_info,app_graph);
16: map_task_pe(taski,id_pe_map,tile_info);
17:
end for
18: task_next = find_next_task(task_vector,tile_info);
19:
while tile_infor_ unallocated.size != 0 do
20: task_vector_child= task_neighbor(task_next,tile_info,app_graph);
21: sort(task_vector_child, decrease_t_comm);
22: for all unmapped taski ϵ task_vector_child do
23:
id_pe_map = pe_nearest (taski ,tile_info,app_graph);
24:
map_task_pe(taski,id_pe_map,tile_info);
25: end for
26: task_next = find_next_task(task_vector,tile_info);
27: end while
28: END

3.3.2.3. Kết quả mô phỏng và đánh giá


TG

0,250
0,200
0,150
0,100
0,050
0,000
CV_NF CV_TG CV_NF CV_TG CV_NF CV_TG
5x5
6x6
7x7
Chiến lƣợc chọn vùng, kích thƣớc nền tảng

Hình 3.(8,9,10). Tổng giá trị lợi ích của các ứng dụng đã ánh xạ

Giá trị lợi ích đại diện cho mức độ hài lòng của người dùng khi nhận được một mức chất lượng
nhất định. Khi người dùng nhận được chất lượng cao nhất của một ứng dụng, giá trị lợi ích bằng 1.
Chất lượng thấp hơn sẽ có giá trị lợi ích nhỏ hơn [67]. Do vậy, tác giả sử dụng thông số này để đánh
giá chất lượng đạt được cho các ứng dụng sau khi ánh xạ. Hình 3.(8,9,10) chỉ ra giá trị OB của các
ứng dụng đạt được khi triển khai các ứng dụng vào nền tảng phần cứng với các kích thước lần lượt
là 5x5,6x6 và 7x7 theo các thuật toán khác nhau. Trong tất cả các trường hợp, thuật toán heuristic
của tác giả đề xuất cho kết quả tốt hơn so với thuật toán FF, NN và Chen-Ling. Cụ thể, đối với nền
tảng có kích thước 5x5, sử dụng chiến lược phân vùng NF, thuật toán của tác giả (TG) đề xuất cải
thiện giá trị lợi ích tổng thể lần lượt 41,6%, 26,9% và 28,0% so với thuật toán FF, NN và ChenLing. Tương tự, khi sử dụng chiến lược phân vùng của tác giả đề xuất, thuật toán của tác giả cũng
cải thiện lần lượt 37,1%, 24,1% và 16,7% so với FF, NN và Chen-Ling.
Đối với mạng có kích thước 6x6, thuật toán heuristic của tác giả cải thiện lần lượt 52,2%,
36,5% và 39,4% so với thuật toán FF, NN và Chen-Ling trong trường hợp sử dụng chiến lược phân
vùng NF. Tương tự, tăng lần lượt 43,7%, 37,2% và 34,0% so với FF, NN và Chen-Ling khi sử dụng

hiệu năng, chống phân mảnh cho các PE trên nền tảng phần cứng như đã phân tích ở trên mà còn
giúp triển khai nhanh các ứng dụng lên hệ thống, vấn đề này rất quan trọng cho một hệ thống quản
lý động. Tiếp theo, thời gian chạy của thuật toán chọn vùng và tỉ lệ của các thông số OB, AMD,
ACMD giữa chiến lược chọn vùng của tác giả đề xuất và NF sẽ được đánh giá.
Thời gian chạy thuật toán chọn vùng được thống kê theo giá trị trung bình khi triển khai các
ứng dụng lên các nền tảng với kích thước khác nhau lần lượt là 5x5, 6x6, 7x7, 8x8, 9x9 và 10x10.


23
Đối với một nền tảng xác định, tác giả chạy 2000 lần với tổng số tác vụ của các ứng dụng thay đổi
từ (x*y) đến (x*y +5). Ví dụ, với nền tảng có kích thước 5x5, thực hiện chạy 2000 lần cho các ứng
dụng có tổng số tác vụ thay đổi từ 25 đến 30. Kết quả thời gian chạy thuật toán chọn vùng được chỉ
ra như Bảng 3.7. Do chiến lược chọn vùng của tác giả đề xuất sử dụng một kỹ thuật đơn giản hơn
nên có thời gian chạy nhỏ hơn so với NF hay nói cách khác chiến lược của tác giả đề xuất có độ
phức tạp tính toán nhỏ hơn.
Bảng 3.7. Thời gian chạy trung bình của các chiến lược chọn vùng
Thời gian chạy trung bình (ms)

Kích thƣớc
nền tảng

Số tác vụ

5x5

2530

0,1165

0,0704


-75,30

9x9

8186

1,3365

0,2099

-84,29

10x10

100105

2,2836

0,2564

-88,77

CV_NF

Gain (%)

CV_TG

Tiếp theo, tác giả đánh giá tính hiệu quả cho các chiến lược chọn vùng thông qua tỉ số của các