BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
TRƯƠNG VĂN HIỆU
NGHIÊN CỨU CÁC GIẢI THUẬT SONG SONG
TRÊN HỆ THỐNG XỬ LÝ ĐỒ HỌA GPU ĐA LÕI
LUẬN VĂN THẠC SĨ KỸ THUẬT
Đà Nẵng - Năm 2011
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
TRƯƠNG VĂN HIỆU
NGHIÊN CỨU CÁC GIẢI THUẬT SONG SONG
TRÊN HỆ THỐNG XỬ LÝ ĐỒ HỌA GPU ĐA LÕI
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số : 60.48.01
LUẬN VĂN THẠC SĨ KỸ THUẬT
Người hướng dẫn khoa học: TS. Nguyễn Thanh Bình
Đà Nẵng - Năm 2011
LỜI CAM ĐOAN
Tôi xin cam đoan:
a. Những nội dung trong luận văn này là do tôi thực hiện dưới sự
hướng dẫn trực tiếp của TS. Nguyễn Thanh Bình.
b. Mọi tham khảo dùng trong luận văn đều được trích dẫn rõ ràng và
trung thực về tên tác giả, tên công trình, thời gian và địa điểm công bố.
Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá,
tôi xin chịu hoàn toàn trách nhiệm.
Tác giả
Trương Văn Hiệu
MỤC LỤC
LỜI CAM ĐOAN iii
MỤC LỤC iv
v
2.2.4. Mô hình lập trình 42
2.2.5. Mô hình bộ nhớ 44
2.2.6. Tìm hiểu ngôn ngữ lập trình CUDA 46
2.2.7. Ví dụ tính toán song song bằng CUDA 58
2.3. TỔNG KẾT CHƯƠNG 2 60
CHƯƠNG 3: XÂY DỰNG ỨNG DỤNG GIẢI THUẬT SONG SONG
TRÊN HỆ THỐNG ĐA LÕI XỬ LÝ ĐỒ HỌA GPU CHO
BÀI TOÁN SO SÁNH TRÌNH TỰ 61
3.1. GIỚI THIỆU 61
3.1.1. So sánh trình tự 61
3.1.2. Định nghĩa so sánh trình tự 62
3.1.3. Hệ thống ký tự 63
3.1.4. Các phép biến đổi 63
3.1.5. Khoảng cách 64
3.1.6. Sắp hàng trình tự hệ gen 64
3.1.7. Các thuật toán sắp hàng trình tự hệ gen 64
3.2. PHÁT BIỂU BÀI TOÁN SO SÁNH TRÌNH TỰ 67
3.2.1. Mô tả bài toán 67
3.2.2. Hướng giải quyết bằng giải thuật quy hoạch động 67
3.3. THIẾT KẾ GIẢI THUẬT SONG SONG 71
3.3.1. Xây dựng giải thuật 71
3.3.2. Cài đặt giải thuật trên CUDA 72
3.3.3. Kết quả 73
3.4. ĐÁNH GIÁ KẾT QUẢ CHẠY CHƯƠNG TRÌNH 74
3.5. TỔNG KẾT CHƯƠNG 3 75
KẾT LUẬN 76
DANH MỤC TÀI LIỆU THAM KHẢO 78
PHỤ LỤC 80
DANH MỤC CÁC CHỮ VIẾT TẮT
Hình 3.1. Mô hình kiến trúc máy SIMD 10
Hình 4.1. Mô hình kiến trúc máy MISD 11
Hình 5.1. Mô hình kiến trúc máy MIMD 12
Hình 1.1. Mô tả lập trình giữa các tác vụ dùng chung bộ nhớ 12
Hình 2.1. Mô hình lập trình truyền thông giữa hai tác vụ trên hai
máy tính
13
Hình 3.1. Mô hình lập trình song song dữ liệu 13
Hình 1.1. Mô tả mối quan hệ các tham số trong công thức tính
thời gian truyền thông
15
Hình 1.2. Kỹ thuật xen kẽ tính toán và truyền thông giữa P1 và P2 17
Hình 2.1. Tính tổng N số 26
Hình 1.1. So sánh kiến trúc CPU và GPU 36
Hình 1.2. So sánh floating-point của GPU và CPU 36
Hình 1.1. Kiến trúc bộ phần mềm CUDA 37
Hình 1.2. Các thao tác thu hồi và cấp phát bộ nhớ 38
Hình 1.3. Vùng nhớ dùng chung mang dữ liệu gần ALU hơn 39
Hình 1.1. Sơ đồ hoạt động truyền dữ liệu giữa Host và Device 42
Hình 2.1. Khối luồng 44
Hình 1.1. Mô hình bộ nhớ trên GPU 45
Hình 1.1. Cộng hai ma trận 58
Hình 2.1. Nhân hai ma trận 59
Hình 1.1. Ví dụ về so sánh trình tự 62
Hình 1.1. So sánh hai trình tự 67
Hình 2.1. Giải thuật quy hoạch động cho bài toán PSA 68
Hình 2.2. Ma trận đánh giá S(i, j) 69
Hình 2.3. Kết quả giải thuật quy hoạch động cho bài toán PSA 69
Hình 1.1. Phương pháp song song tính giá trị các phần tử ma trận
đánh giá
triển các ứng dụng song song trong rất nhiều lĩnh vực khác nhau như: Điện toán hóa
- 2 -
học, sắp xếp, tìm kiếm, mô phỏng các mô hình vật lý, chuẩn đoán y khoa, thăm dò
dầu khí, … CUDA là bộ công cụ phát triển phần mềm trên GPU được xây dựng
bằng ngôn ngữ lập trình C. Với CUDA các lập trình viên dùng để điều khiển GPU
để xử lý, tính toán song song các dữ liệu lớn.
Việc tăng tốc trong quá trình tính toán không những đòi hỏi những thiết bị
GPU có khả năng xử lý tốc độ cao với dữ liệu khổng lồ mà cần phải có những giải
thuật song song hữu hiệu.
Xuất phát từ nhu cầu trên tôi chọn đề tài: “Nghiên cứu các giải thuật song
song trên hệ thống xử lý đồ họa GPU đa lõi”.
1. Mục tiêu và nhiệm vụ nghiên cứu
Để hoàn thành mục đích ý tưởng đề ra cần nghiên cứu các nội dung như sau:
- Tìm hiểu các giải thuật tính toán song song, các cách thiết kế mẫu trong tính
toán song song.
- Tìm hiểu cấu trúc của GPU
- Tìm hiểu và triển khai lập trình song song với CUDA
- Phát biểu, phân tích, cài đặt giải thuật cho bài toán đặt ra.
- Xây dựng giải thuật và ứng dụng áp dụng giải thuật tính toán song song trên
thiết bị đồ họa GPU.
- Đánh giá kết quả theo yêu cầu của đề tài.
2. Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu
Trong khuôn khổ luận văn thuộc loại nghiên cứu và ứng dụng, tôi chỉ giới hạn
nghiên cứu các vấn đề sau:
- Lý thuyết tính toán song song.
- 3 -
- Chuyển đổi một số giải thuật xử lý trình tự sang tính toán song song sao cho
Về mặt thực tiễn
Việc nghiên cứu và đề xuất giải pháp để “Nghiên cứu các giải thuật song song
trên hệ thống xử lý đồ họa GPU”, làm cơ sở để giải quyết một số bài toán cần lượng
tính toán lớn với dữ liệu khổng lồ.
6. Bố cục luận văn
Nội dung chính của luận văn được chia thành 3 chương như sau:
Chương 1: Cơ sở lý thuyết tính toán song song.
Trong chương này giới thiệu tổng quan về tính toán song song như: Lịch sử
phát triển song song, phân loại kiến trúc song song, các mô hình lập trình song song
và đánh giá hiệu quả tính toán song song. Trình bày nguyên lý thiết kế giải thuật
song song, giới thiệu một số mẫu thiết kế giải thuật song song bằng phương pháp
chia để trị, phương pháp cây nhị phân. Giới thiệu bài toán sắp xếp, bài toán tính
tổng dùng giải thuật song song. Qua đây đưa ra cái nhìn tổng quan hơn về tính toán
song song.
Chương 2: Cấu trúc hệ thống xử lý đồ họa GPU và công nghệ tính toán hỗ trợ
song song dữ liệu CUDA.
Chương này giới thiệu về thiết bị đồ họa GPU đa lõi của hãng NVIDIA gồm
các vấn đề: lịch sử phát triển, mô tả kiến trúc, nguyên lý hoạt động và những ứng
dụng trên thiết bị đồ họa này. Đưa ra những so sánh khác biệt của CPU và GPU.
Trình bày ngôn ngữ lập trình song song CUDA trên thiết bị đồ họa GPU của hãng
- 5 -
NVIDIA. Áp dụng giải quyết một số bài toán cộng ma trận, nhân ma trận, …bằng
phương pháp song song dùng ngôn ngữ CUDA thực thi trên thiết bị đồ họa.
Chương 3: Xây dựng ứng dụng áp dụng giải thuật song song trên hệ thống đa
lõi xử lý đồ họa GPU cho bài toán bắt cặp trình tự.
Trong chương này trình bày một số khái niệm cơ bản về tin sinh học: AND,
protein, … Từ đó tập trung mô tả bài toán so sánh trình tự sử dụng giải thuật Smith-
Waterman và giải quyết bằng giải thuật song song bằng CUDA đưa ra những đánh
giá về lợi ích của việc sử dụng giải thuật song song.
1.1.1.2. Tại sao phải tính toán song song
Việc tính toán song song là rất cần thiết. Ngoài hai nguyên nhân chính là nó
được dùng để tính toán các bài toán yêu cầu thời gian tính toán lớn và khối lượng
dữ liệu lớn còn có các nguyên nhân khác như để sử dụng tài nguyên của các máy
khác trong một mạng nội bộ hoặc thông qua mạng internet, có thể sử dụng nhiều tài
nguyên tính toán như kết hợp lại tạo nên một siêu máy tính. Do giới hạn về không
gian lưu trữ của bộ nhớ trên một máy đơn để giải quyết một vấn đề lớn việc sử dụng
nhiều bộ nhớ trên nhiều máy tính là rất hữu hiệu trong trường hợp này.
Giới hạn của tính toán tuần tự bao gồm cả hai nguyên nhân thực tế và nguyên
nhân vật lý. Ðể xây dựng nên một máy tính tuần tự tốc độ cao gặp rất nhiều hạn
chế:
Về kích cỡ: Công nghệ chế tạo bộ xử lý cho phép gắn nhiều bóng bán dẫn trên
một con chip. Tuy nhiên việc làm này sẽ làm tăng kích thuớc của bộ xử lý.
Về tốc độ truyền dữ liệu: Tốc độ truyền của máy tính tuần tự phụ thuộc trực
tiếp vào sự di chuyển dữ liệu trong phần cứng. Cho nên việc tăng tốc độ thực hiện
phải chủ yếu căn cứ vào các yếu tố tính toán.
Về thương mại: Việc tạo ra một bộ xử lý có tốc độ xử lý cao là rất tốn kém. Sử
dụng nhiều bộ xử lý nhỏ đạt hiệu quả tương tự mà lại ít tốn kém hơn [7].
- 8 -
1.1.1.3. Một số khái niệm xử lý song song
Định nghĩa về xử lý song song
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 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à xử lý tuần tự
Trong tính toán tuần tự với một bộ xử lý thì tại mỗi thời điểm chỉ được thực
hiện một phép toán. Trong tính toán 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.
tính về số lượng bộ xử lý, số chương trình thực hiện, cấu trúc bộ nhớ, … để phân
máy tính thành bốn loại dựa trên sự biểu hiện của cặp khái niệm: Dòng lệnh
(instruction stream) và dòng dữ liệu (data stream), mỗi loại nằm trong một trong hai
trạng thái đơn (single) hoặc đa (multiple) được thể hiện trong Bảng 1.1.
Bảng 1.1. Mô tả phân loại kiến trúc của Flynn
Dòng lệnh
(instruction stream)
Dòng dữ liệu
(data stream)
Loại kiến trúc
Trạng thái đơn
(single)
Trạng thái đơn
(single)
SISD
Single Instruction Single Data
Trạng thái đơn
(single)
Trạng thái đa
(multiple)
SIMD
Single Instruction Multiple Data
Trạng thái đa
(multiple)
Trạng thái đơn
(single)
MISD
Multiple Instruction Single Data
Trạng thái đa
(multiple)
1.1.2.5. Kiến trúc đa dòng lệnh đa luồng dữ liệu (MIMD)
Máy tính loại MIMD gọi là đa bộ xử lý, trong đó mỗi bộ xử lý có thể thực
hiện những luồng lệnh (chương trình) khác nhau trên các luồng dữ liệu riêng. Hầu
hết các hệ thống MIMD đều có bộ nhớ riêng và cũng có thể truy cập vào bộ nhớ
chung khi cần, do vậy giảm thiểu được thời gian trao đổi dữ liệu giữa các bộ xử lý
trong hệ thống. Đây là loại kiến trúc phức tạp nhất, nhưng nó là mô hình hỗ trợ xử
lý song song cao nhất và đã có nhiều máy tính được thiết kế theo kiến trúc này, ví
dụ: BBN Butterfly, Alliant FX, iSPC của Intel, Kiến trúc máy MIMD có mô hình
hoạt động theo Hình 5.1.
- 12 -
Hình 5.1. Mô hình kiến trúc máy MIMD
1.1.3. Các mô hình lập trình song song
1.1.3.1. Lập trình bộ nhớ dùng chung
Lập trình bộ nhớ dùng chung hay còn gọi là lập trình chia sẻ bộ nhớ. Trong
mô hình (Xem Hình 1.1. ) này được thiết kế cho máy tính xử lý song song
(multiprocessors), các tác vụ chia sẻ không gian địa chỉ dùng chung, được đọc/ghi
một cách không đồng bộ. Một số kỹ thuật được dùng trong lập trình bộ nhớ dùng
chung như khoá (locks) hay cờ (semaphores) được sử dụng để điều khiển truy nhập
đến bộ nhớ dùng chung. Truyền thông giữa các tác vụ thông qua các biến dùng
chung.
Hình 1.1. Mô tả lập trình giữa các tác vụ dùng chung bộ nhớ
1.1.3.2. Lập trình truyền thông điệp
Trong máy tính song song cung cấp kỹ thuật truyền thông điệp để trao đổi
giữa các tác vụ (Xem Hình 2.1. ). Hai tác vụ nằm trên hai máy khác nhau có thể trao
đổi với nhau bằng kỹ thuật truyền thông điệp trên mạng kết nối. Các thông điệp có
- 13 -
thể là các lệnh, dữ liệu, tín hiệu đồng bộ hay ngắt. Hai mô hình truyền thông điệp
được thực thi và sử dụng là đồng bộ hay không đồng bộ.
Thời gian tính toán của giải thuật song song là thời gian dành để thực hiện tính
toán. Đối với giải thuật tuần tự thì thời gian này chỉ phụ thuộc vào kích thước của
bài toán nhưng với tính toán song song thì việc tính toán lặp trên các tác vụ có thể
có. Do đó thời gian tính toán sẽ phụ thuộc vào số tác vụ thực hiện. Đối với mô hình
bộ nhớ chung thì số lượng bộ xử lý cũng ảnh hưởng đến tốc độ thực thi trên mỗi bộ
xử lý.
Thông thường có thể xác định bằng thời gian thực hiện tuần tự cộng với bất kỳ
thời gian nào thêm vào do thực hiện song song. Chẳng hạn như thời gian tính toán
lặp lại cùng một công việc trên các tác vụ.
Thời gian truyền thông
Thời gian truyền thông của một giải thuật là thời gian các tác vụ dành để gửi
và nhận thông điệp. Có hai loại truyền thông cần xác định: Truyền thông giữa hai
- 15 -
tác vụ trên hai bộ xử lý khác nhau và truyền thông giữa hai tác vụ cùng nằm trên
cùng bộ xử lý. Thông thường thời gian truyền bên trong bộ xử lý lớn hơn nhiều so
với thời gian truyền giữa hai bộ xử lý, nhất là đối với mô hình máy tính song song.
Trong mô hình máy tính song song lý tưởng thì chi phí để gửi một thông điệp
giữa hai tác vụ định vị trên bộ xử lý khác nhau phụ thuộc vào hai tham số sau:
Thời gian khởi tạo thông điệp: t
s
là thời gian cần thiết để khởi tạo truyền thông
Thời gian truyền dữ liệu: t
w
là thời gian cần thiết để truyền đi dữ liệu có kích
thước một word (2 byte). t
w
được xác định bởi băng thông vật lý của kênh truyền
thông kết nối bộ xử lý nguồn và đích.
Công thức tính thời gian gửi thông điệp có kích thước L (đơn vị là word) là:
(1.2) T
msg
= ( t
s
+ t
w
L) D
Với D là khoảng cách giữa nút nhận và gửi trong bước định đường.
- Đối với truyền thông định đường theo cơ chế chuyển mạch kêmh:
(1.3) T
msg
= t
s
+ t
w
L – t
h
D
Với D là khoảng cách giữa nút nhận và gửi trong bước định đường T
h
là chi
phí gia tăng cho mỗi bước định đường.
Trong thực tế, t
h
thường rất nhỏ, có thể bỏ qua được. Khi xem xét đến sự tranh
chấp băng thông truyền trên mạng kết nối thì công thức tính được thay đổi như sau:
(1.4) T
msg
= t
s
Thời gian thực hiện luôn là thước đo thuận tiện nhất để đánh giá hiệu năng của
giải thuật. Khi thời gian thực hiện có xu hướng biến đổi theo kích thước bài toán,
thời gian thực hiện phải được tiêu chuẩn hoá khi so sánh hiệu năng giải thuật với
kích thước bài toán khác nhau.
Hiệu quả của giải thuật được định nghĩa là phần thời gian mà các bộ xử lý
dùng để thực hiện công việc có ích, chỉ ra mức độ hiệu quả của một giải thuật khi sử
dụng các tài nguyên tính toán của một máy tính song song theo hướng độc lập với
kích thước bài toán, được xác định theo công thức sau:
Copyright: Tài liệu đại học ©