i

ĐẠI HỌC THÁI NGUYÊN
ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

ĐINH TIẾN NGỌC

NGHIÊN CỨU CÔNG NGHỆ XỬ LÝ GPU VÀ ỨNG DỤNG

THÁI NGUYÊN 2017


ii

LỜI CAM ĐOAN
Tôi xin cam đoan :
Những nghiên cứu dưới đây trong luận văn của tôi hoàn toàn trung thực
không vi phạm bất kỳ quyền sở hữu trí tuệ nào. Nếu sai tôi xin chịu hoàn toàn
trách nhiệm.
TÁC GIẢ LUẬN VĂN

Đinh Tiến Ngọc


iii

LỜI CẢM ƠN

Lời đầu tiên tôi xin chân thành cảm ơn đếnTS. Lê Quang Minh người thầy đã
tận tình giúp đỡ, hướng dẫn tôi hoàn thành luận văn này.
Tôi cũng xin chân thành cảm ơn các thầy, cô giảng viên cao học người đã giúp


coproccessor

bộ đồng xử lý

kernel

hạt nhân

texture

Kết cấu: cấu trúc của đối tượng, nó được xem như mô hình
thu nhỏ của đối tượng.

texturefetches

Hàm đọc kết cấu

texturereference

Tham chiếu kết cấu

warp

Mỗi khối được tách thành các nhóm SIMD của các luồng.

SIMD

Single Instruction Multiple Data: đơn lệnh đa dữ liệu


DANH MỤC HÌNHVẼ ................................................................................................ vii
LỜI MỞ ĐẦU ............................................................................................................. viii
CHƯƠNG I : KHÁI QUÁT VỀ BỘ XỬ LÝ ĐỒ HỌA GPU VÀ XỬ LÝ SONG SONG
......................................................................................................................................... 1
1.1 Khái quát về xử lý song song................................................................................. 1
1.1.1 Khái quát về xử lý song song .......................................................................... 1
1.1.2 Khái quát về Hệ thống máy tính song song ..................................................... 3
1.1.3 Khái quát về lập trình song song ..................................................................... 7
1.1.4 Các nguyên tắc khi thiết kế giải thuật xử lý song song ................................... 9
1.2. Khái quát về công nghệ GPU và các ứng dụng .................................................. 10
1.2.1. Tổng quan về GPU ....................................................................................... 11
1.2.2. Nguồn gốc và quá trình phát triển GPU ....................................................... 11
1.2.3. Cấu trúc của bộ xử lý đồ họa GPU ............................................................... 15
1.2.4. Lập trình trên GPU ....................................................................................... 19
1.2.5. Các hỗ trợ phần mềm cho xử lý tính toán trên GPU .................................... 22
1.2.6. Các kỹ thuật tính toán trên GPU ................................................................... 26
1.2.7.Các giải thuật ứng dụng trên GPU ............................................................. 29
CHƯƠNG II: XỬ LÝ SONG SONG TRÊN THIẾT BỊ ĐỒ HỌA GPU VỚI CUDA . 31
2.1. Khái quát về CUDA ............................................................................................ 31
2.2.Cơ chế lập trình và cách thức hoạt động của CUDA ........................................... 33
2.2.1.Cơ chế lập trình.............................................................................................. 33
2.2.2.Cách thức hoạt động của CUDA ................................................................... 33
2.3. Tổng quan về lập trình với CUDA ...................................................................... 38
2.3.1. Là ngôn ngữ lập trình mở rộng của ngôn ngữ lập trình C ............................ 38


vi
2.3.2. Các phần mở rộng của CUDA ...................................................................... 38
2.3.3.Biến Built-in trong CUDA............................................................................. 41
2.3.4. Biên dịch CUDA thông qua NVCC.............................................................. 42

Hình10: Kiến trúc GPU của NVIDIA và AMD................................................. 19
Hình 11: Kiến trúc phần mềm CUDA ................................................................ 31
Hình 12: Thao tác cấp phát và thu hồi bộ nhớ ................................................... 32
Hình 13: Vùng nhớ dùng chung mang dữ liệu gần ALU hơn .......................... 33
Hình 14: Sơ đồ hoạt động truyền dữ liệu giữa Host và Device ............................. 34
Hình 15: Khối luồng .............................................................................................. 36
Hình 16: Mô hình bộ nhớ trên GPU ...................................................................... 37
Hình 17: Chiều của lưới và khối với chỉ số khối và luồng .................................... 42
Hình 18: Phương pháp đánh chỉ số luồng.............................................................. 45
Hình 19 : Mã hóa và giải mã ................................................................................. 49
Hình 20: Biến đổi SubBytes() đối với mảng trạng thái ......................................... 51
Hình 21: Mô tả Hàm ShiftRows() ......................................................................... 51
Hình 22: Mô tả hàm MixColumns() ...................................................................... 52
Hình 23: Mô tả hàm AddRoundKey() ................................................................... 53
Hình 24: Mô tả hàm InvShiftRow()....................................................................... 55


viii

LỜI MỞ ĐẦU
Với sự phát triển như vũ bão của công nghệ, ngày nay công nghệ thông tin đã
trở thành một phần không thể thiếu trong cuộc sống. Không những thế nó còn là một
công cụ hữu hiệu trong các ngành khoa học, công nghệ cao,… đặc biệt là những
ngành có nhu cầu tính toán lớn. Tuy nhiên trong khi với nhu cầu tính toán ngày cành
tăng cao đó, ngành công nghệ thông tin lại vấp phải một vấn đề tối quan trọng đó là
năng lực xử lý của CPU có hạn. Các nhà phát triển phần cứng đã thực hiện gia tăng
mức độ xử lý cho CPU bằng cách gia tăng xung cho CPU. Tuy nhiên việc này cũng
chạm ngưỡng bởi gặp phải vấn đề về tản nhiệt cho CPU do nhiệt độ CPU quá cao.
Một hướng mới đã được các nhà nghiên cứu đưa ra đó là phát triển bộ xử lý đa
nhân với cơ chế xử lý song song.

VÀ XỬ LÝ SONG SONG
1.1 Khái quát về xử lý song song
1.1.1 Khái quát về xử lý song song
Nguồn gốc ra đời của xử lý songsong
Một trong những nền tảng máy tính cơ bản đó là thiết kế máy tính của John Von
Neumann. Đó là thiết kế mà ở đó một lệnh được thực hiện trên một bộ xử lý.

Hình1: Kiến trúc Von Neumann
Khi cần tính toán với lượng câu lệnh và phép tính lớn thì thiết kế trên trở nên
lỗi thời. Người ta đã đưa ra các phương pháp nhằm giải quyết vấn đề trên. Trong đó
có việc tăng số lượng nhân xử lý hoặc kết nối nhiều máy tính thông qua mạng để
tăng tốc độ xử lý.
Khi tăng tốc xử lý các phép tính trên máy tính song song, việc sử dụng các thuật
toán tuần tự đã không còn thích hợp và không tận dụng hết khả năng tiềm tàng của
máy tính song song. Dẫn đến việc ra đời các giải thuật song song.

Lý do phải xử lý song song
Như đã nói ở trên máy tính song song với bộ xử lý nhiều nhân đã thay thế dần
máy tính đơn nhân, một bộ xử lý. Và với những thuật toán, câu lệnh, phép xử lý tuần
tự đã không còn phù hợp với máy tính song song. Do vậy xử lý song song đã ra đời
thay thế cho xử lý tuần tự nhằm đem lại hiệu năng tính toán cao hơn.
Bằng chứng đã thấy trong thực tế với nhiều bài toán xử lý với lượng dữ liệu lớn


2

yêu cầu tốc độ nhanh và độ chính xác như các bài toán về đồ họa, xử lý ảnh, xử lý
tín hiệu, mô phỏng giao thông, mô phỏng sự chuyển động của các phân tử, nguyên
tử, dự báo thời tiết, mô phỏng bản đồ gen……Xử lý song song đã chứng minh được
khả năng xử lý cũng như khả năng phát triển của nó sau này.

- Các câu lệnh được các bộ vi xử lý thực

thực hiện một cách lần lượt.

hiện một cách song song, đồng thời.

- Mỗi câu lệnh thực thiện trên duy nhất - Mỗi câu lệnh có thể thao tác trên nhiều
một thành phần dữ liệu.

thành phần dữ liệu khác nhau.


3

- Chỉ cần viết đúng câu lệnh và giải

- Viết đúng câu lệnh và giải thuật. Ngoài ra

thuật là có thể chạy chương trình

phải chỉ rõ phần nào của chương trình cần
phải chạy song song.

- Dùng với các bài toán dữ liệu nhỏ, độ - Được sử dụng đối với các bài toán có dữ
phức tạp không cao và yêu cầu thời gian liệu lớn, độ phức tạp cao và thời gian ngắn.
chấp nhận được.

 Mục đích của xử lý song song
Dựa trên việc tính toán song song trên nhiều bộ xử lý cho tốc độ xử lý cao,
xử lý song song thường dùng cho các bài toán có độ phức tạp lớn, yêu cầu khối lượng

(single)

Single Instruction Single

Trạng thái đa

SIMD
Data

(multiple)

Single Instruction Multiple

Trạng thái đơn

MISD
Data

(single)

Multiple Instruction Single

Trạng thái đa

MIMD
Data

(multiple)

Multiple Instruction Multiple


Hình 4 : Kiến trúc máy SISD
Mô hình cấu trúc đơn dòng lệnh đa luồng dữ liệu (SIMD)
Mỗi bộ xử lý thực hiện xử lý một luồng dữ liêu. Các bộ xử lý cùng thực hiện
một phép toán trên nhiều luồng dữ liệu khác nhau và có một thành phần để điều khiển
cho các bộ xử lý thực hiện xử lý các luồng câu lệnh.


6

Hình 5 : Kiến trúc máy SIMD
Mô hình cấu trúc đa dòng lệnh đơn luồng dữ liệu (MISD)
Là loại máy tính có thể thực hiện nhiều câu lệnh trên cùng một mục dữ liệu.

Hình 6 : Kiến trúc máy MISD
Mô hình cấu trúc đa dòng lệnh đa luồng dữ liệu (MIMD)
Là loại máy tính đa nhân, đa bộ xử lý có thể thực hiện nhiều câu lệnh trên
nhiều luồng khác nhau.Các bộ xử lý đều có bộ nhớ riêng biệt nhưng cũng có thể truy
cập vào bộ nhớ chung khi cần giúp tăng tốc độ xử lý. Mô hình kiến trúc này là mô
hình kiến trúc phức tạp nhất nhưng cũng là mô hình ưu việt nhất và cũng đã có nhiều
máy tính được xây dựng trên kiến trúc này, ví dụ: BBN Butterfly.


7

Hình 7 : Kiến trúc máy MIMD

1.1.3 Khái quát về lập trình song song
Là việc lập trình các câu lệnh các đoạn chương trình song song để chạy trên
hệ thống máy tính song song. Cũng có thể hiểu là việc song song hóa các thuật toán

Là mô hình được sử dụng rộng rãi cho các hệ phân tán. Bao gồm các đặc trưng
sau:
 Trong quá trình tính toán mỗi luồng sử dụng một vùng nhớ cục bộ riêng.
 Các luồng có thể sử dụng chung tài nguyên.
 Việc trao đổi giữa các luồng được thực hiện bằng cách gửi các thông điệp.
 Mỗi luồng sẽ thực hiện việc điều khiển việc truyền dữ liệu. Ví dụ mỗi thao tác gửi

ở một luồng thì phải ứng với một thao tác nhận ở luồng khác.

Hình 8: Mô hình lập trình truyền thông hai tác vụ của hai máy tính

Song song dữ liệu trong xử lý song song
Ở mô hình này chủ yếu việc song song được thực hiện trên một tập dữ liệu.
Cấu trúc của tập dữ liệu này là mảng hoặc khối. Cùng một phép toán, Các tác vụ sẽ
thực hiện trên cùng một kiểu dữ liệu nhưng trên các tập dữ liệu khác nhau. Mô hình


9

này chủ yếu dành cho máy tính song song kiểu bộ xử lý mảng.

Hình 9 : Mô hình lập trình song song dữ liệu
1.1.4 Các nguyên tắc khi thiết kế giải thuật xử lý song song
Để xét đến việc xử lý song song cần quan tâm đến giải thuật và việc thực hiện
giải thuật song song đó trên loại máy tính nào.
Những bước cần thực hiện khi thiết kế giải thuật song song:
 Phân nhỏ bài toán thành bài toán con nhỏ hơn sao cho độc lập về mặt dữ liệu
và chức năng, và giải quyết các bài toán này đồng thời.
 Chỉ rõ việc chia sẻ dữ liệu và truy cập.
 Chia các tác vụ cho các tiến trình cho các nhân xử lý.


+
B
=

4

C

5

4

4

5

5

4

4

5

5

Các ví dụ về chương trình không thể song song hóa
Tính chuỗi Fibonacci (1, 1, 2, 3, 5, 8, 13, 21,…) bằng cách sử dụng công
thức: F(k+2)= F(k+1) + F(k), với n > 1.

lớn các vấn đề phức tạp đòi hỏi tính toán lớn vào GPU. Việc này đã góp phần ứng
dụng GPU vào giải quyết các bài toán hiệu năng cao của tính toán hiện đại. Tính
toán và lập trình trên GPU là một thay thế tiềm năng cho CPU trong hệ thống máy
tính hiện đại. Trong một tương lai không xa, GPU sẽ đảm nhận thay cho CPU những
công việc như xử lý hình ảnh, đồ họa, các tính toán phức tạp thay vì chỉ dừng lại ở
những ứng dụng trò chơi 3D.

1.2.2. Nguồn gốc và quá trình phát triển GPU
GPU là bộ xử lý của card đồ họa, dùng để tính toán các phép toán dấu phảy
động.
Lúc đầu GPU là bộ xử lý gắn trên card đồ họa phục vụ cho việc tính toán các
phép toán dấu phảy động.
Với các vi mạch siêu nhỏ, cùng các phép toán đăc biệt , GPU được sử dụng chủ
yếu trong các hoạt động cần đến xử lý đồ họa cao như trong các game đồ họa cao
hoặc các xử lý đồ họa 3D.
Việc xử lý một số phép toán đồ họa nguyên thủy khiến GPU chạy nhanh hơn
nhiều so với việc vẽ trực tiếp trên màn hình với CPU.


12

 Thập kỷ 70:
Công bố bộ điều khiển phần cứng kết hợp đồ họa và chế độ text, tính toán
vị trí và hiển thị (theo khuôn dạng phần cứng hỗ trợ) và những hiệu ứng khác trên
các máy tính ATARI 8-bit, bởi hãng sản xuất chip ANTIC và CTIA. Chíp ANTIC
là một bộ xử lý dành riêng cho ánh xạ (lập trình được) giữa dữ liệu đồ họa tới đầu
ra video và text. Nhà thiết kế chip ANTIC, sau đó đã thiết kế chip đồ họa cho
Commodore Amiga.
 Thập kỷ 80:
Chiếc máy tính đầu tiên có chứa các bộ blit (Block Image Transfer là sự

phí tối thiểu. hiệu năng đồ họa 3D đã chấp nhận được với bảng mạch rời dành
riêng cho các chức năng tăng tốc 3D (thiếu chức năng 2D GUI) như 3dfx Voodoo
vào thời điểm ban đầu. Công nghệ sản xuất một lần nữa tiến triển, Chipset Verite
của Rendition được là sản phẩm đầu tiên được tích hợp video, bộ tăng tốc 2D GUI,
và chức năng 3D tất cả vào một con chip.
Trở thành một lực lượng chi phối trên máy tính, và là một động lực cho phát
triển phần cứng OpenGL xuất hiện vào đầu những năm 90 như là API đồ họa chuyên
nghiệp. Phần mềm của OpenGL được phổ biến trong thời gian này, dù sau đó do
tác động của OpenGL đã dẫn đến hỗ trợ phần cứng rộng rãi. Một sự lựa chọn nổi lên
giữa các tính năng có trong phần cứng và những tính năng đó có trong OpenGL.
Trong thời gian cuối những năm 90 DirectX phổ biến với các nhà phát triển
game Windows. Microsoft khẳng định nghiêm ngặt về việc cung cấp sự hỗ trợ mộtmột của phần cứng Không giống như OpenGL. Việc đó đã làm DirectX ít phổ biến
như là API đồ họa độc lập ngay từ đầu trong khi đó các GPU có nhiều tính năng
đặc biệt, và hiện đã được ứng dụng OpenGL có thể được thừa hưởng, để lại DirectX
một thế hệ sau. Theo thời gian, Microsoft đã bắt đầu làm việc chặt chẽ hơn với các
nhà phát triển phần cứng, và bắt đầu nhắm mục tiêu các bản phát hành của DirectX
với những phần cứng đồ họa hỗ trợ. phiên bản API đầu tiên đang phát triển để đạt
được áp dụng rộng rãi trên thị trường chơi game là Direct3D 5,0 , và nó cạnh tranh
trực tiếp với nhiều phần cứng, như các thư viện đồ họa độc quyền, trong khi
OpenGL duy trì điều đó. Direct3D 7,0 hỗ trợ phần cứng tăng tốc biến đổi và ánh


14

sáng (T & L). Bộ tăng tốc 3D biến đổi từ lúc dầu chỉ là bộ quét đường thẳng đơn
giản về sau có thêm phần cứng quan trọng dùng cho các đường ống dẫn biến
đổi 3D. Sản phẩm đầu tiên trên thị trường với khả năng này là NVIDIA Geforce
256 (còn được gọi là NV10). Phần cứng biến đổi và ánh sáng, cả hai đều đã có
trong OpenGL, trong phần cứng những năm 90 và đặt tiền đề cho các phát triển
sau đó là các đơn vị đổ bóng điểm ảnh và đổ bóng vector mà với đặc tính linh hoạt

thêm các chức năng cố định, và các chức năng chuyên biệt. Giờ đây các khía cạnh
về khả năng lập trình của bộ xử lý chiếm đã vị trí trung tâm. Chúng ta đi xem xét
từng khía cạnh.
Đường ống dẫn đồ họa (GraphicsPipeline)
Đầu vào của GPU là các kiểu hình học cơ bản, điển hình là tam giác, trong thế
giới không gian 3 chiều. Sau một quá trình những khối hình nguyên thủy đó được
làm bóng mờ (shade) và được vẽ lên màn hình, nơi chúng được lắp ráp để tạo ra
hình ảnh cuối cùng.
Các phép toán vector:
Hình học nguyên thủy (primary geometric) cấu thành từ các vector riêng lẻ.
Bằng cách tính toán tương tác với các luồng ánh sáng trong một bối cảnh cụ thể
mỗi vector phải được chuyển thành không gian trên màn hình và có bóng mờ. Những
bối cảnh tiêu biểu có thể có hàng chục đến hàng trăm ngàn vector, và mỗi vector
có thể được tính toán độc lập. Việc tính toán này rất phù hợp cho phần cứng song
song.

Các Thành phần nguyên tố:
Phần tử hỗ trợ phần cứng cơ bản trong GPU ngày nay đó chính là các vector
được lắp ráp vào các hình tam giác.

Sự quét mành:
Việc xác định những vị trí điểm ảnh nào trong không gian màn hình được bao
chứa bởi mỗi tam giác được gọi là Quét mành (rasterization). Mỗi một tam giác


16

tạo ra một phần tử cơ bản được gọi là "mảnh" ở vị trí điểm ảnh trong không gian
màn hình mà nó bao chứa. Một chú ý là do nhiều tam giác có thể chồng lên nhau tại
một vị trí điểm ảnh bất kỳ nên giá trị màu của mỗi điểm ảnh có thể được tính từ nhiều