ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG ĐÌNH THẮNG LẬP TRÌNH SONG SONG TRÊN
NỀN ĐƠN VỊ XỬ LÝ ĐỒ HỌA VÀ
ỨNG DỤNG LUẬN VĂN THẠC SĨ Hà Nội – 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG ĐÌNH THẮNG LẬP TRÌNH SONG SONG TRÊN
NỀN ĐƠN VỊ XỬ LÝ ĐỒ HỌA VÀ
ỨNG DỤNG Ngành: Công nghệ Thông tin
Chuyên ngành: Hệ thống Thông tin
Mã số: 60 48 05 LUẬN VĂN THẠC SĨ
NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Trí Thành
Hà Nội – 20102 MỤC LỤC
LỜI CAM ĐOAN................................................................................................. 1
MỤC LỤC.............................................................................................................2
DANH MỤC HÌNH VẼ........................................................................................4
KÝ TỰ VIẾT TẮT................................................................................................5
LỜI CẢM ƠN.......................................................................................................6
MỞ ĐẦU...............................................................................................................7
CHƢƠNG 1: GIỚI THIỆU..................................................................................9
1.1. Mục đích của lập trình song song...............................................................9
1.2. Mục tiêu của luận văn...............................................................................12
1.3. Tổ chức của luận văn................................................................................12
CHƢƠNG 2: TỔNG QUAN VỀ ĐƠN VỊ XỬ LÝ ĐỒ HỌA (GRAPHIC
PROCESSING UNIT-GPU)............................................................................... 14
2.1. Tóm tắt lịch sử phát triển của đơn vị xử lý đồ họa (GPU)........................14
2.2. Sự khác nhau giữa GPU và CPU..............................................................15
2.3. Mô hình xử lý song song dữ liệu.............................................................. 17
2.4. Lợi ích sự thực thi tính toán song song.....................................................21
2.5. Phân cấp bộ nhớ........................................................................................22
2.5.1. Bộ nhớ toàn cục (global memory) và bộ nhớ cục bộ (local memory) 23 2.5.2. Bộ nhớ chia sẻ (shared memory)........................................................24
2.5.3. Bộ nhớ texture và constant................................................................. 24
2.6. Các chiến lƣợc tối ƣu hóa trên GPU........................................................24
2.6.1. Tối đa hóa thực thi song song.............................................................25
2.6.2. Tối ƣu hóa sử dụng bộ nhớ................................................................ 25 2.6.3. Tối ƣu hóa thực thi các thread............................................................26
2.6.4. Tối ƣu hóa sử dụng chỉ lệnh...............................................................27
2.7. nVidia CUDA............................................................................................27
2.8. Thrust........................................................................................................ 28 3 CHƢƠNG 3: MÔ HÌNH TRƢỜNG NGẪU NHIÊN CÓ ĐIỀU KIỆN
(CONDITIONAL RANDOM FIELDS -CRFS) ................................................. 3.1.Mô hình lý thuyết CRFs ..................................... 3.2.Ƣớc lƣợng tham số mô hình CRFs .................... 3.3.Ứng dụng CRFs trong trích chọn thông tin ........
CHƢƠNG 4: ỨNG DỤNG GPU SONG SONG TỪNG PHẦN CÔNG CỤ
CRF++.................................................................................................................
4.2. Công cụ CRF++ ........................................................................................
4.2.1. Training ...............................................................................................
4.2.2. Testing ................................................................................................. 4.3.Song song CRF++ ..............................................
4.3.1. Song song phần Training .................................................................... 4.4.Kết quả thực nghiệm ..........................................
4.4.1. Môi trƣờng thực nghiệm .....................................................................
4.4.2. Đánh giá kết quả .................................................................................
KẾT LUẬN .........................................................................................................
TÀI LIỆU THAM KHẢO................................................................................... 4 DANH MỤC HÌNH VẼ Hình 1: Sự khác nhau giữa CPU và GPU – GPU có nhiều bộ xử lý để định
hướng xử lý song song dữ liệu [2]. .....................................................................
Hình 2: So sánh tốc độ tính toán giữa CPU và GPU [2] ..................................
Hình 3: Nguyên lý lập trình trên GPU [2] .........................................................
Hình 4: Ví dụ về lưới 5 chiều của thread ...........................................................
Hình 5: Luật Amdahl's – tăng tốc phụ thuộc vào phần mã song song và số
lượng thread [3] ..................................................................................................
Hình 6: Thu thập và phân tán các hoạt động bộ nhớ [3] ..................................
Hình 7: Các loại bộ nhớ trong GPU [2] ............................................................
Hình 8: Phân cấp bộ nhớ theo khía cạnh phần mềm (trái) và phần cứng (phải)
[2] ........................................................................................................................
Hình
9: Phân rã tại nhánh phụ thuộc dữ liệu ...........
Hình 10: Điện toán GPU được tăng cường bởi kiến trúc CUDA .....................
Hình 11: So sánh mô hình HMMs, MEMMs và CRFs .......................................
Hình
12: Ví dụ tệp tin huấn luyện .............................
Hình
13: Tệp tin mẫu (template) ...............................
Hình
14: Kết quả thực hiện crf_learn .......................
Hình
15: Kết quả thực hiện crf_test ..........................
Hình 16: So sánh thời gian thực hiên tính toán trên GPU-CPU ....................... Hình 17: Biểu đồ thời gian thực hiên tính toán trên GPU-CPU .......................
Hình 18: Biểu đồ hình cột so sánh thời gian thực hiên tính toán trên GPU-CPU
.............................................................................................................................
Hình
19: Tập dữ liệu CoNLL 2000-shared task ........
Hình
20: So sánh thời gian thực hiện phần training 5 2D
3D
ALU
API
CPU
CRFs
CUBLAS
CUDA
CUDPP
CUFFT
DRAM
GPGPU
GPU
LBFGS
MIRA
MPI
OpenCL
OpenMP
PVM SIMD
SIMT
VLSI 6 LỜI CẢM ƠN
Để hoàn thành luận văn này tác giả đã nhận đƣợc sự giúp đỡ từ rất nhiều
cơ quan, đoàn thể và cá nhân.
Trƣớc hết tôi xin chân thành cảm ơn các thầy giáo, cô giáo trong Khoa
Công nghệ Thông tin, trƣờng Đại học Công nghệ, Đại học Quốc gia Hà Nội đã
tận tình giảng dạy, trang bị cho tôi những kiến thức quý báu trong suốt quá trình
học tập tại trƣờng.
Tôi xin bày tỏ lòng biết ơn sâu sắc đến TS. Nguyễn Trí Thành - ngƣời thầy
đã trực tiếp hƣớng dẫn tôi trong suốt quá trình xây dựng và hoàn thành luận văn
này.
Đồng thời, xin chân thành cảm ơn lãnh đạo Viện Công nghệ Thông tin
thuộc Viện Khoa học và Công nghệ Quân sự đã tạo điều kiện để tôi thực hiện
thành công luận văn tốt nghiệp này.
Hà Nội, tháng 10 năm 2010
Học viên Hoàng Đình Thắng 7 MỞ ĐẦU
Tính toán song song hay xử lý song song là quá trình xử lý thông tin trong đó nhấn mạnh việc nhiều đơn vị dữ liệu đƣợc xử lý đồng thời bởi một hay nhiều
bộ xử lý để giải quyết một bài toán. Trái ngƣợc với xử lý nối tiếp, đòi hỏi phải
xử lý các công việc theo thứ tự tuần tự
Có hai kiểu song song đó là: Song song về dữ liệu (data parallelism): là cơ chế sử dụng nhiều
đơn vị xử lý thực hiện cùng một thao tác trên nhiều đơn vị dữ liệu . Song song lệnh (control parallelism): là cơ chế trong đó nhiều
thao tác khác nhau tác động lên nhiều đơn vị dữ liệu khác nhau một
cách đồng thời.
Chíp đồ họa, với hàng chục lõi đƣợc sử dụng để tạo ra hình ảnh thực trên
màn hình máy tính, rất phù hợp cho các nhiệm vụ xử lý song song. Trong khi đó
thì bộ xử lý, với những lõi mạnh hơn nhƣng số lƣợng ít hơn (giống nhƣ Core
i7) lại phù hợp hơn cho các ứng dụng xử lý nối tiếp.
Trong một báo cáo các nhà nghiên cứu của Intel cho biết, trung bình,
NVIDIA GeForce GTX 280 (tung ra hồi tháng 6/2008) nhanh hơn gấp 2,5 lần so
với bộ xử lý (BXL) Intel Core i7 960 3,2GHz, và nhanh hơn trên 14 lần trong
những hoàn cảnh nhất định.
Xử lý song song là hƣớng nghiên cứu quan trọng, nó giúp cho việc thực
hiện các bài toán đƣợc nhanh hơn rất nhiều so với xử lý tuần tự. Luận văn sẽ
hƣớng tới tìm hiểu bài toán xử lý song song trên nền đơn vị xử lý đồ họa
(Graphic Processing Unit-GPU), một trong những hƣớng xử lý song song đang
đƣợc phát triển mạnh trong thời gian gần đây.
Đồng thời luận văn này cũng tìm hiểu về mô hình trƣờng ngẫu nhiên có
điều kiện (Conditional Random Fields-CRFs), một mô hình đƣợc ứng dụng thành công trong rất nhiều lĩnh vực nhƣ tin-sinh học, xử lý ngôn ngữ tự nhiên và
khai phá text/web.
CRF++ là một công cụ đƣợc xây dựng cho mô hình CRF, áp dụng cho các
tác vụ xử lý ngôn ngữ tự nhiên nhƣ: nhận dạng thực thể tên (Named Entity
Recognition), trích chọn thông tin (Information Extraction) và Text Chunking.
CRF++ là một phần mềm nguồn mở, đƣợc xây dựng bằng ngôn ngữ C++. 8 Luận văn này sẽ nghiên cứu cách mà tác giả của CRF++ thực hiện mô hình
CRF lý thuyết. Từ đó đề xuất cách song song một số phần của CRF++ sử dụng
mô hình song song trên đơn vị xử lý đồ họa. 9 CHƢƠNG 1: GIỚI THIỆU
1.1. Mục đích của lập trình song song
Yêu cầu thực tế cần thực hiện khối lƣợng tính toán lớn: bài toán xử lý ngôn
ngữ tự nhiên, bài toán xử lý ảnh 3D, thăm dò dầu khí, dự báo thời tiết,...(máy
tính xử lý tuần tự kiểu von Neumann là không đáp ứng yêu cầu)
Xử lý song song là quá trình xử lý gồm nhiều tiến trình đƣợc kích hoạt
đồng thời và cùng tham gia giải quyết một bài toán, nói chung xử lý song song
đƣợc thực hiện trên những hệ thống đa bộ xử lý.
Phân biệt xử lý song song với tuần tự: Trong xử lý tuần tự với một bộ xử lý thì tại mỗi thời điểm chỉ thực hiện đƣợc một phép toán. Trong xử lý song song thì nhiều bộ xử lý cùng kết hợp với nhau
để giải quyết cùng một bài toán cho nên giảm đƣợc thời gian xử lý vì
mỗi thời điểm có thể thực hiện đồng thời nhiều phép toán.
Mục đích của xử lý song song: là thực hiện tính toán nhanh trên cơ sở sử
dụng nhiều bộ xử lý đồng thời. Cùng với tốc độ xử lý nhanh hơn, việc xử lý
song song cũng sẽ giải đƣợc những bài toán phức tạp yêu cầu khối lƣợng tính
toán lớn.
Ba yếu tố chính dẫn đến việc xây dựng các hệ thống xử lý song song: Tốc độ xử lý của các bộ xử lý theo kiểu von Neumann đã dần
tiến tới giới hạn, không thể cải tiến thêm đƣợc do vậy dẫn tới đòi hỏi
phải thực hiện xử lý song song. Hiện nay giá thành của phần cứng (CPU) giảm mạnh, tạo điều
kiện để xây dựng những hệ thống có nhiều bộ xử lý với giá thành hợp
lý. Sự phát triển của công nghệ mạch tích hợp (VLSI) cho phép tạo
ra những hệ thống có hàng triệu bóng bán dẫn (transistor) trên một
chíp. Vấn đề xử lý song song liên quan trực tiếp đến: kiến trúc máy tính, phần
mềm hệ thống (hệ điều hành), thuật toán và ngôn ngữ lập trình,v.v…. Hệ thống tính song song: là một tập các bộ xử lý (thƣờng là cùng một loại)
kết nối với nhau theo một kiến trúc nào đó để có thể hợp tác với nhau trong hoạt
động và trao đổi dữ liệu đƣợc với nhau. 10 Chúng ta dễ nhận thấy là độ phức tạp của xử lý song song sẽ lớn hơn xử lý
tuần tự rất nhiều, và tập trung chủ yếu ở phƣơng diện trao đổi dữ liệu và đồng
bộ các tiến trình.
Để cài đặt các thuật toán song song trên các máy tính song song chúng ta
phải sử dụng những ngôn ngữ lập trình song song. Nhiều ngôn ngữ lập trình
song song đang đƣợc sử dụng nhƣ: Fortran 90, Pthread [24] với Fortran/C++,
MPI [21] với C/C++, PVM [22] với C/C++, OpenMP [23] với C/C++, v.v….
Một số khó khăn của lập trình song song truyền thống:
Khó khăn thứ nhất – Suy nghĩ tuần tự Chúng ta có thể thấy rằng tƣ duy tuần tự là do môi trƣờng lập trình quyết
định. Từ thập niên 80 đến khoảng gần đây, chúng ta chủ yếu làm việc với máy
tính cá nhân, và mô hình thực thi trên đó là từng bƣớc một. Cũng có máy tính
song song, nhƣng hiếm ngƣời đƣợc dùng nó trong công việc hàng ngày, vì
chuyện xây dựng một hệ máy tính nhƣ vậy ở mức quốc gia đã cực kỳ tốn kém
chứ đừng nói là công ty hay cá nhân.
Cũng chính vì thói quen suy nghĩ tuần tự đã ăn sâu nhƣ vậy nên giờ chuyển sang suy nghĩ kiểu song song rất là mệt mỏi, vì sẽ phải chú ý tới các lỗi đặc thù của
nó, nhƣ bế tắc (deadlock), khóa sống (livelock), điều kiện cạnh tranh,v.v…. Khó khăn thứ hai – Mở rộng hiệu năng Qui tắc Amdahl [3] trong lập trình song song cho chúng ta biết là lượng
tăng tốc tối đa có thể đạt được bằng việc song song hóa thuật toán thì tỷ lệ
nghịch với phần mã chương trình không thể chuyển sang dạng song song. Tức là
cho dù chỉ còn 10% mã chƣơng trình không thể song song hóa, thì sự tăng tốc
chƣơng trình đó cũng không vƣợt quá 10 lần. Tuy nhiên để ƣớc lƣợng mức độ
cải tiến theo kiểu này rất khó, vì không thể xác định chính xác bao nhiêu phần
trăm mã chƣơng trình thật sự chạy song song, do trong lúc thực thi song song,
mọi thứ lại rất có thể bị chuyển ngược lại thành tuần tự, nhƣ khi có tranh chấp
tài nguyên dùng chung, hay có truy cập đến nhiều vị trí khá cách xa nhau trong
bộ nhớ. Đây chính là một trong những hạn chế chính của mô hình lập trình song
truyền thống (vốn thƣờng cài đặt cách điều khiển tiểu trình qua cơ chế khóa, hay
qua giao diện truyền thông điệp, hay nhiều cách khác nữa đòi hỏi sự đồngbộ hóa
– tức là là tiến trình này đợi tiến trình kia hoàn tất công việc rồi mới làm tiếp
phần việc tiếp theo của mình) khi áp dụng cho nhiều nhân/lõi. Nói một cách dễ
hiểu, nếu chúng ta chỉ phải đợi từng người một hoàn tất công việc của họ một
cách độc lập, thì thời gian chờ đợi có thể coi là tăng tuyến tính với số người cần 11 đợi/đồng bộ. Nhưng nếu chúng ta phải đợi cùng lúc nhiều người, và kết quả
công việc của họ lại phụ thuộc lẫn nhau, thì thời gian chờ đợi sẽ tăng tổ hợp và
rất khó xác định, chứ không đơn giản chỉ là tăng tuyến tính. Còn có một khó khăn cơ bản hơn nữa trong mở rộng hiệu năng với số
nhân/lõi. Mô hình lập trình song song truyền thống tiếp cận bài toán cần giải
quyết theo kiểu top-down, bằng cách chia một bài toán lớn thành nhiều tác vụ
con, và mỗi tác vụ này sẽ đƣợc giao cho một bộ xử lý/nhân/lõi. Vấn đề rắc rối ở
đây là khi số lƣợng bộ xử lý/nhân/lõi tăng lên đến hàng chục, hay hàng trăm
nhƣ hiện nay, thì số tác vụ con đã đƣợc thiết kế để giao nhằm tận dụng sức
mạnh tính toán của chúng lại không có đủ. Cách tiếp cận phổ biến nhất cho tình
huống này là lại cố chia nhỏ các tác vụ con đó thành nhiều đơn vị thực thi nhỏ
hơn. Nhƣ vậy, cách làm này bị phụ thuộc vào từng thế hệ phần cứng bộ xử lý,
dẫn đến chuyện không thể mở rộng việc thực thi chƣơng trình một cách dễ dàng
theo kiểu không cần phải thay đổi, sửa chữa gì về mặt thuật toán hay mã nguồn
cài đặt. Và suy cho cùng thì nếu một bài toán mà đƣợc chia thành vài chục tác
vụ con chạy song song sẽ vô cùng khó quản lý và gỡ rối.
Khó khăn thứ ba – Tuần tự sang song song Việc cố gắng chuyển mã từ tuần tự sang song song dựa trên tác vụ là quá
trình này cần rất nhiều thời gian, có khi cả vài năm trời. Do tốc độ gia tăng số
nhân/lõi hiện tại quá nhanh, nên nhiều khi thuật toán song song mà chúng ta đã
bỏ ra vài năm kể từ năm nay để thiết kế lại không mở rộng tốt với số nhân/lõi
của vài năm nữa, ở thời điểm chúng ta hoàn tất việc cài đặt nó một cách song
song.
Ý
tƣởng gán một công việc nhỏ cho từng bộ xử lý/nhân/lõi trong máy tính
nhằm tăng hiệu năng phần mềm chạy trên đó là hoàn toàn tự nhiên và đƣợc đúc
kết từ kinh nghiệm trong đời sống hàng ngày. Tuy nhiên để tận dụng đƣợc hết
sức mạnh của hàng trăm, rồi hàng ngàn nhân/lõi trong tƣơng lai, chúng ta có lẻ
cần phải “đi trƣớc đón đầu” bằng cách tạo ra hàng chục ngàn, hàng trăm ngàn
công việc nhỏ li ti cung cấp cho đội quân nhân/lõi đông đảo và ngày một gia tăng đó.
Với những khó khăn đó, yêu cầu về một mô hình lập trình song kiểu mới
linh hoạt hơn và theo sát với sự thay đổi về số lƣợng nhân /lõi của một hệ thống
máy tính. Đó là lập trình song song đa dụng trên đơn vị xử lý đồ họa-GPU. 12 1.2. Mục tiêu của luận văn
Vì giới hạn của phần cứng, xu hƣớng tăng số lõi (cores) thay vì tăng xung
nhịp (clock rate) đang trở nên phổ biến. CPU thì có multicores, còn GPU thì có
many-cores. Ngày nay, GPU có thể hoạt động nhanh hơn cả CPU trong việc xử
lý tính toán. Cụ thể nhờ số lƣợng cores lớn (vài trăm so với 2,4, hoặc 8 của
CPU), tốc độ truy xuất bộ nhớ nhanh (85GB/s với G80, 150GB/s với GTX200).
Nhờ thế, vai trò của GPU đã vƣợt ra ngoài phạm vi truyền thống, đó là chạy các
ứng dụng tính toán. Tuy nhiên, GPU vẫn chƣa thay thế hoàn toàn đƣợc CPU, do
có nhiều tác vụ thực hiện hiệu quả hơn trên CPU. Do đó, GPU chỉ đóng vai trò
là một co-processor.
Mục đích của luận văn này là giới công nghệ song song đƣợc dùng trên
nền đơn vị xử lý đồ họa (GPU) và cung cấp cái nhìn tổng quan về xu hƣớng
hiện nay trong tính toán song song đa dụng trong GPU. Trình bày về các lợi thế
của tính toán song song quy mô lớn trên GPU.
Mô hình trƣờng ngẫu nhiên có điều kiện (Conditional Random FieldsCRFs), một mô hình đƣợc ứng dụng thành công trong rất nhiều lĩnh vực nhƣ
tin-sinh học, xử lý ngôn ngữ tự nhiên và khai phá text
CRF++ là một công cụ xây dựng cho mô hình CRF, đƣợc viết bằng ngôn
ngữ C++. Luận văn này sẽ ứng dụng GPU để song song hóa từng phần của
CRF++, nhằm mục đích cải thiện tốc độ tính toán của CRF++, nhất là trong
trƣờng hợp xử lý số liệu lớn (hàng chục nghìn câu, hàng triệu thuộc tính). 1.3. Tổ chức của luận văn Luận văn này gồm 4 chƣơng, với nội dung sơ bộ nhƣ sau:
Chương 1 - Giới thiệu nêu lên mục đích của lập trình song song, những khó
khăn của lập trình song song truyền thống, dẫn đến yêu cầu một mô hình lập
trình song song kiểu mới linh hoạt hơn. Chƣơng này cũng trình bày mục tiêu
của luận văn, tổ chức của luận văn.
Chương 2 - Tổng quan về đơn vị xử lý đồ họa (GPU), cung cấp cái nhìn
tổng quan về tính toán song song đa dụng trên đơn vị xử lý đồ họa. Mô tả sự
khác nhau cơ bản giữa đơn vị xử lý trung tâm (CPU) và đơn vị xử lý đồ họa
(GPU). Phần lớn của chƣơng này dành cho việc giải thích các nguyên tắc cơ bản
của tính toán song song đa dụng trên đơn vị xử lý đồ họa và giao diện lập trình
ứng dụng (API) trên GPU. 13 Chương 3 - Mô hình trường ngẫu nhiên có điều kiện (CRF), trình bày mô
hình lý thuyết CRF, phƣơng pháp ƣớc lƣợng tham số của mô hình CRF và một
số ứng dụng của CRF.
Chương 4 - Ứng dụng GPU song song hóa từng phần công cụ CRF++,
giới thiệu công cụ CRF++, cách thức mà tác giả của CRF++ thực hiện, từ đó đề
xuất chiến lƣợc song song CRF++ bằng GPU thông qua các thƣ viện lập trình
cho GPU nhƣ CUDA, Thrust. Phần cuối của chƣơng sẽ đƣa ra kết quả thực
nghiệm cũng nhƣ một số đánh giá, nhận xét. 14 CHƢƠNG 2: TỔNG QUAN VỀ ĐƠN VỊ XỬ LÝ
ĐỒ HỌA (GRAPHIC PROCESSING UNIT-GPU)
2.1. Tóm tắt lịch sử phát triển của đơn vị xử lý đồ họa (GPU) Trong suốt 20 năm qua GPUs đã trải qua những phát triển lớn. Bắt đầu phát
triển từ đơn vị xử lý đồ họa 2D đơn giản, đến đa mục đích, có thể lập trình
đƣợc, song song mức độ cao, có nhiều lõi đơn vị xử lý với khả năng tính toán
phi thƣờng và băng thông bộ nhớ rất cao.
Lịch sử của GPUs những năm 1970 với các máy tính có Atari 8-bit. Những
chíp đồ họa này đƣợc sử dụng để hòa trộn đồ họa và dữ liệu văn bản rồi hiển thị
chúng lên màn hình. Những năm 1980, kiến trúc của chíp này trở thành nền tảng
của sản xuất chíp hàng loạt tiếp theo, đƣợc tích hợp trong Commodore Amiga.
Chíp này là chip đầu tiên có đầy đủ các đặc tính tăng tốc đồ họa – nó chứa các
đặc tính nhƣ: vẽ hình ảnh gốc, tô màu hình ảnh, chuyển khối hình ảnh,
v.v….Đặc tính cách mạng là tất cả video đƣợc đẩy vào phần cứng. Năm 1984,
gần 10 năm sau khi phần cứng tăng tốc đồ họa trở thành chuẩn, IBM giới thiệu
tăng tốc 2D/3D đầu tiên dƣới cái tên IBM Professional Graphics Controller,
nhƣng thành công thì không đƣợc nhƣ mong đợi. Việc thiếu tính tƣơng thích,
xử lý chậm và giá cao ($4.500) làm cho dự án này thất bại [7].
Trong suốt những năm 1990, nhu cầu tăng tốc đồ họa trở nên cấp thiết, bởi
vì số lƣợng máy trạm ngày càng tăng với nền tảng công nghệ của Microsoft
Windows. Năm 1993, S3 Graphics giới thiệu chíp đơn 2D tăng tốc đầu tiên - S3
86C911, dƣới tên mã là Porsche 911. Chíp này thiết lập chuẩn tăng tốc 2D trong
vòng vài năm. Năm 1995 gần nhƣ tất cả các nhà sản xuất chíp đã bổ sung hỗ trợ
tăng tốc 2D vào sản phẩm của họ.
Giữa những năm 1990 đồ họa 3D thời gian thực trở nên phổ biến hơn trong
máy tính và trò chơi điều khiển. Nhu cầu đồ họa 3D thời gian thực dẫn đến phát
triển tăng tốc 3D thời gian thực đầu tiên. Các chíp giá rẻ nhƣ S3 ViRGE, Matrox
Mystique hay Ati Rage đƣợc dựa trên 2D tăng tốc và thêm các đặc tính 3D.
Bƣớc đột phá đầu tiên đến năm 1996, khi 3Dfx Interactive giới thiệu tăng tốc
3D đầu tiên đầu đủ tính năng có tên là Voodoo [8]. Gia tăng tốc độ này xác định
tiêu chuẩn mới cho chip đồ họa 3D cho ba năm tiếp theo. Bƣớc đột phá lớn thứ
hai đến năm 1999 khi tổng công ty nVidia giới thiệu GPU đầu tiên – NV10, 15 dƣới tên mã GeForce 256. Tất cả các con chíp hiện nay về cơ bản đều xuất phát
từ kiến trúc này.
Vào cuối năm 2006 nVidia giới thiệu kiến trúc thiết bị hợp nhất cho tính
toán đầu tiên - Compute Unified Device Architecture (CUDA). Các công ty đối
thủ AMD/ATI giới thiệu kiến trúc của họ (ATI FireStream) vài tháng sau đó.
Thời điểm này GPU trở nên dễ tiếp cận để phát triển phần mềm bằng các ngôn
ngữ lập trình chuẩn công nghiệp và thiết lập cách thức mới cho tính toán hiệu
năng cao [2]. 2.2. Sự khác nhau giữa GPU và CPU
Ý
tƣởng chính của tính toán song song đa dụng trên GPU (GPGPU) là sử
dụng nhiều bóng bán dẫn (transistor) để xử lý dữ liệu và xử lý dữ liệu song song.
Đây là sự khác biệt chính giữa CPU và GPU. GPU chủ yếu định hƣớng các thao
tác song song dữ liệu hơn là trữ dữ liệu (caching data) và điều khiển luồng [2].
Nhu cầu này chủ yếu xuất phát từ dựng hình đồ họa, bởi vì thiết bị đồ họa bắt
buộc phải xử lý một lƣợng lớn các phần tử dữ liệu đồ họa (nhƣ các điểm ảnh,
đỉnh và mảnh) và thao tác trên các phân tử này (lightning, blending, clipping,
texturing, …). Song song là cách để giảm lƣợng thời gian cần thiết để xử lý dữ
liệu và giảm chi phí tổng thể bằng cách phân phối nó trong xử lý các phần tử.
Nguyên tắc cơ bản là quá trình dựng hình đồ họa là cố định. Dữ liệu đƣợc xử lý
bởi phần cứng đồ họa đi qua nhiều giai đoạn trƣớc khi chúng đƣợc hiển thị và
chuỗi sự kiện này là không thay đổi. Hình 1: Sự khác nhau giữa CPU và GPU – GPU có nhiều bộ xử lý để định
hướng xử lý song song dữ liệu [2]. 16 Hình 2: So sánh tốc độ tính toán giữa CPU và GPU [2]
CPU phải xử lý nhiều tác vụ khác nhau vào cùng một thời gian. Vì vậy
CPU phải đƣợc tối ƣu hóa cho mục đích này, chủ yếu lƣu trữ dữ liệu quan trọng
đƣợc dùng bởi tiến trình đang chạy và nhanh chóng chuyển ngữ cảnh giữa các
tiến trình đang chạy. Tất cả các tác vụ đƣợc cung cấp một thời gian xử lý xác
định trƣớc để thực thi mã của chúng. Khi đến thời gian này, hệ điều hành
chuyển CPU sang tiến trình tiếp theo. Chuyển đổi ngữ cảnh giữa các tiến trình
đang chạy có thể đƣợc tính toán với cƣờng độ lớn. 17 Ngƣợc lại, GPU xử lý nhiều nhất một nhiệm vụ tại một thời điểm nhƣng
thực hiện nhiều lần song song. GPU sử dụng mô hình song song dữ liệu, để có
thể giải quyết các vấn đề số học cƣờng độ cao hơn CPU. Khi cùng một đoạn mã
GPU đƣợc thực hiện song song nhiều lần thì không cần kiểm soát luồng và quản
lý bộ nhớ đệm (cache). Thực thi tác vụ song song không đƣợc hỗ trợ trong
GPU. Có nghĩa là, không thể thực thi hai hoặc nhiều chƣơng trình khác nhau
trên cùng GPU vào cùng một thời điểm.
Mô hình xử lý dữ liệu song song ánh xạ các phần tử dữ liệu vào các đơn vị
làm việc cơ sở đƣợc gọi là các luồng (thread). Tính song song thread cùng với
phân cấp bộ nhớ chia sẻ và hàng rào đồng bộ hóa giữa các luồng làm nên khái
niệm trừu tƣợng về mô hình lập trình song song đa dụng của GPU [2]. 2.3. Mô hình xử lý song song dữ liệu
Mục này sẽ trình bày các khái niệm cơ bản trong đơn vị xử lý đồ họa.
Kernel là một đoạn mã chƣơng trình, đƣợc thể hiện bởi một hàm hay thủ tục viết bằng một ngôn ngữ lập trình cụ thể. Thread là một thực thể chạy mã nhị
phân, đƣợc thực thi song song nhiều lần [2]. Có thể nói kernel là một “mẫu
hàm” cho một nhóm thread. Hai thuật ngữ quan trọng tiếp theo là host và device.
Host là bao gồm bộ xử lý trung tâm và DRAM của CPU, còn device gồm các bộ
xử lý và DRAM của GPU. Host và device đƣợc phân tách bởi không gian địa
chỉ của hai DRAM. Host thực thi chƣơng trình chính (mã tuần tự) còn device
thực thi kernel (mã song song). Device trong mô hình này làm việc giống nhƣ
một bộ đồng xử lý (co-processor) đối với host. Hình 3 thể hiện cách thức thực
thi mã tuần tự và song song.
GPU thread dùng xử lý dữ liệu song song và mô hình lập trình. Trong mô
hình này, các phần tử dữ liệu cơ sở đƣợc lƣu trong bộ nhớ GPU đƣợc ánh xạ
vào thread đang chạy. Bộ nhớ GPU (không gian địa chỉ) là một mảng tuyến tính
của các phần tử cơ bản (bytes). Để ánh xạ thread vào bộ nhớ đối tƣợng chúng ta
cần biết cách tổ chức thread. Cơ cấu tổ chức này phải có khả năng xác định rõ
đối tƣợng bộ nhớ từ các giá trị định danh thread đƣợc sinh ra một cách tự động.
Để làm đƣợc điều này, cách dễ dàng nhất là tổ chức thread thành lƣới (grid) ảo
đa chiều của các thread. Với công nghệ CUDA, lƣới này có 5 chiều và để định
hƣớng tốt hơn, lại đƣợc chia thành 2 loại: khối 3 chiều của thread và lƣới 2
chiều của khối của thread. 18 Hình 3: Nguyên lý lập trình trên GPU [2]
Số định danh duy nhất của thread có thể ƣớc lƣợng từ một số biến liên
quan, đƣợc khởi tạo khi lƣới của khối thread đƣợc liệt kê. Các biến này có thể
truy cập từ bên trong mỗi kernel. Mỗi thread có biến riêng của nó, chứa tọa độ 19 ba chiều
trục , , x, y, z trong khối. Khối thread chứa các biến chiều và tọa độ 2 chiều x, y trong x, y, z ứng lƣới khối thread. Các chiều của thread cũng có thể truy cập từ trong các biến x, y. với các lƣới khối Các chiều của khối thread và của lƣới phải đƣợc thiết lập trƣớc khi chạy các tính toán. Số
định danh duy nhất của thread trong khối thread và số định danh duy nhất của
block trong grid đƣợc tính nhƣ sau [2]: threadId = blockId = Hình 4: Ví dụ về lưới 5 chiều của thread
Cơ cấu phân cấp cung cấp phƣơng tiện để tính toán trên các cấu trúc dữ
liệu nhƣ véctơ, ma trận hay mảng ba chiều. Tuy nhiên do hạn chế của phần
cứng, kích thƣớc của khối thread hay số thread trong mỗi block là giới hạn1.
1 Đối với nVidia CUDA tương thích với 1.x, kích thước lớn nhất của khối thread là 512x512x64,
nhưng có nhiều nhất 512 thread trong mỗi block. 20 Nghĩa là chúng ta không thể gọi khối thread với kích thƣớc bất kỳ. Đây là một hạn
chế, nhƣng chúng ta có thể “lợi dụng” tính toán theo một số khối của các thread. Nếu làm điều này, chúng ta luôn phải xác định kích thƣớc của grid để thực hiện các
tính toán. Tối đa kích thước của khối thread luôn luôn có nghĩa là giảm thiểu kích
thước của grid và ngược lại. Vậy làm thế nào để chúng ta chọn kích thƣớc của
khối thread, mà vẫn tuân theo giới hạn của phần cứng. Ví dụ, nếu chúng ta muốn
ánh xạ véctơ kích thƣớc xác định kích thƣớc với khối kích thƣớc của grid của khối thread. Có thể tính toán nhƣ sau:
ϵ and 1 ≤
1≤ ≤ maxBlockDimensionX ≤ maxThreadsPerBlock Để xác định kích thƣớc của
kích thƣớc * , chúng ta cần và vào block kích thƣớc ϵ trong trƣờng hợp ánh xạ ma trận
, : and 1 ≤ ≤ maxBlockDimensionX ϵ N and 1 ≤ ≤ maxBlockDimensionY 1≤ * ≤ maxThreadsPerBlock Trƣờng hợp ánh xạ mảng 3 chiều * *
trên, với thay đổi điều kiện ban đầu. 1≤ chúng ta dùng biểu thức nhƣ and 1 ≤ ≤ maxBlockDimensionX and 1 ≤ ≤ maxBlockDimensionY and 1 ≤ ≤ maxBlockDimensionZ * ≤ maxThreadsPerBlock * 21 2.4. Lợi ích sự thực thi tính toán song song
Để đạt đƣợc lợi ích tối đa từ tính toán song song chúng ta cần tìm giải pháp
làm thế nào để song song mã tuần tự. Trong GPGPU điều này đƣợc thực hiện
bởi song song thread và mô hình thực thi song song dữ liệu. Lợi ích tối đa (tăng
tốc lý thuyết) có thể đƣợc diễn tả bởi luật Amdahl's [3] Trong đố là một phần của chƣơng trình có thể đƣợc thực hiện song song, tƣợng trƣng cho phần mã đƣợc thực hiện tuần tự và là số bộ xử lý hoặc thread thực hiện phần song song. Hình 5 minh họa tăng tốc lý thuyết cho các
phần khác nhau của mã song song phụ thuộc vào số lƣợng thread thực hiện song
song. Hình 5: Luật Amdahl's – tăng tốc phụ thuộc vào phần mã song song và số lượng
thread [3] 22 2.5. Phân cấp bộ nhớ
Ngày này, GPUs hỗ trợ đánh địa chỉ bộ nhớ byte-wise và hỗ trợ thu thập
(gather) và phân tán (scatter) các hoạt động bộ nhớ. Truy cập bộ nhớ song song
là giải pháp chính cho thông lƣợng bộ nhớ lớn và xử lý dữ liệu song song. Điều
quan trọng cần đề cập đến là tất cả các hoạt động bộ nhớ phải đƣợc hợp nhất.
Hợp nhất truy cập bộ nhớ nghĩa là đọc từ một tập địa chỉ liên tục phải tƣơng ứng
với tổ chức thread (số định danh thread). Cách tốt nhất để hợp nhất bộ nhớ truy
cập là ánh xạ thread và block vào bộ nhớ đối tƣợng. Không hợp nhất hoặc truy
cập bộ nhớ ngẫu nhiên dẫn đến đọc và ghi tuần tự dữ liệu và làm mất hiệu suất
[2]. Hình 6: Thu thập và phân tán các hoạt động bộ nhớ [3]
Có thể xem xét bộ nhớ GPU từ hai khía cạnh: phần cứng và phần mềm. Với
khía cạnh phần mềm, cần phân biệt giữa các bộ nhớ global, local, shared, texture
và constant. Mỗi loại bộ nhớ có chức năng đặc thù và mục đích sử dụng riêng.
Với cái nhìn phần cứng, chỉ cần phân biệt giữa bộ nhớ thiết bị (DRAM), bộ nhớ
chia sẻ (shared memory) với constant và texture cache. 23 Hình 7: Các loại bộ nhớ trong GPU [2] Hình 8: Phân cấp bộ nhớ theo khía cạnh phần mềm (trái)
và phần cứng (phải) [2]
2.5.1. Bộ nhớ toàn cục (global memory) và bộ nhớ cục bộ (local memory)
Bộ nhớ toàn cục là phần bộ nhớ lớn nhất trong thiết bị GPU. Bộ nhớ này nằm
trong DRAM của thiết bị và có thể truy cập từ tất cả các thread trong grid và từ
host-device thông qua thƣ viện runtime đặc thù. Các đối tƣợng bộ nhớ khai báo
trong không gian bộ nhớ toàn cục có thời gian tồn tại là thời gian của ứng dụng. Bộ
nhớ toàn cục có thông lƣợng bộ nhớ rất lớn (hàng trăm gigabyte/giây). Hạn chế
chính của loại bộ nhớ này là độ trễ rất lớn khi đọc và ghi dữ liệu (hàng | 
