ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA

KHOA CÔNG NGHỆ THÔNG TIN

BẢO VỆ LUẬN VĂN THẠC SĨ
CHUYÊN NGÀNH KHOA HỌC MÁY TÍNH

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
HVTH: TRƯƠNG VĂN HIỆU
Lớp: KHMT-K19 (Khóa 2009-2011)
CBHD: TS. NGUYỄN THANH BÌNH
Đà Nẵng, tháng 09/2011

1


NỘI DUNG TRÌNH BÀY
1

Giới thiệu đề tài

2

Cơ sở lý thuyết song song

3

Giới thiệu GPU và CUDA



Tăng tốc độ CPU

Nhiệt độ CPU
sẽ quá cao

Phát triển công nghệ đa
lõi, nhiều lõi

CUDA phát triển ứng dụng song
song: Điện toán hóa học, sắp xếp,
tìm kiếm, vật lý, y khoa…

Quá trình tính toán cần phải có giải thuật song
song hữu hiệu. Đề 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”
3/23


Giới thiệu đề tài(tt)







Mục tiêu của đề tài:
Tìm hiểu các giải thuật và cách thiết kế mẫu trong tính
toán song song.

Nguyên lý thiết kế giải thuật song song
Phân chia dữ liệu
cho các tác vụ

Chỉ ra cách truy cập
và chia sẻ dữ liệu

Khi thiết kế giải thuật song
song, cần phải thực hiện
Phân các tác vụ
cho các tiến trình
(cho bộ xử lý)

Các tiến trình được
đồng bộ ra sao
6/23


Nhận thức vấn đề, chương trình có thể song song hóa


Trước khi phát triển giải pháp song song cho một
bài toán  hãy xác định đó là vấn đề mà trên thực
tế có thể song song hóa được hay không ?



Ví dụ về vấn đề có
thể song song hóa
được: tính tổng hai

tổng


Phát biểu bài toán: Tính tổng N số (n1, n2,…, nN)

Giải pháp tuần tự: dùng vòng for.
 Giải pháp song song: Giả sử có N/2 bộ xử lý
Bước 1: tính (n1, n2), (n3, n4), …, (nN-1, nN)


Bước tiếp theo: tính trên N/4 cặp dữ liệu…
Qua logn bước sẽ tính toán xong.

9/23


Giới thiệu GPU


GPU (Graphic Proccessing Unit): bộ xử lý đồ họa

10/23


So sánh GPU và CPU
CPU: bộ vi xử lý trung tâm dùng để tính toán và
xử lý các chương trình, dữ kiện... và điều phối
hoạt động các thiết bị khác.
 GPU: bộ vi xử lý chuyên xử lý các dữ liệu về hình
ảnh, đồ họa.

Host,Device


B1: Dữ liệu tính toán tại bộ nhớ của Host  truyền
dữ liệu cần tính toán từ Host qua bộ nhớ Device.
 B2: Sau đó Device sẽ tính toán dữ liệu  trả về
bộ nhớ Host.


13/23


Ví dụ tính toán song song bằng CUDA


Mô tả: cộng hai ma trận A[n][m] và B[n][m], kết
quả trả về ma trận C[n][m].



Mô tả: Nhân hai ma trận A[n][k] và B[k][m], kết
quả trả về ma trận C[n][m].

14/23


Một số định nghĩa so sánh trình tự
So sánh trình tự: là quá trình nghiên cứu sự giống
nhau giữa các chuỗi trình tự và đo lường sự giống
nhau giữa các trình tự.

Xây dựng giải thuật bằng quy hoạch động


Xây dựng ma trận đánh giá trên công thức
S(i, j) = max { S(i-1, j-1) + σ(S1[i], S2[ j]) , S(i-1, j) r , S(i, j-1) - r }, với i > 0, j > 0.

2 a=b
 Hàm đánh giá: σ ( a, b ) = 
− 1 a ≠ b

17/23


Xây dựng giải thuật bằng pp song song


Nhận xét: Tại bước xây dựng ma trận đánh giá ta
nhận thấy khi tính giá trị cho các phần tử nằm trên
đường chéo phụ không phụ thuộc lẫn nhau, do đó
có thể tính toán riêng rẽ từng phần tử trên từng
luồng khác nhau.
 Với từng phần tử của
đường chéo được tính
bởi một luồng riêng.
Như vậy đường chéo
có n phần tử thì cần n
luồng để tính giá trị cho
đường chéo.

18/23

tin sinh học có công cụ hỗ trợ để nghiên cứu.
20/23


21/23