Thạc Sĩ 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ĩ năm 2011
Đề 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
Định dạng file word kèm slide


MỤC LỤC
LỜI CAM ĐOAN i
MỤC LỤC ii
DANH MỤC CÁC CHỮ VIẾT TẮT iv
DANH MỤC CÁC BẢNG v
DANH MỤC CÁC HÌNH VẼ vi
MỞ ĐẦU 1
CHƯƠNG 1: CƠ SỞ LÝ THUYẾT 6
1.1. TỔNG QUAN VỀ TÍNH TOÁN SONG SONG 6
1.1.1. Tổng quan về tính toán song song. 6
1.1.2. Phân loại các kiến trúc song song. 9
1.1.3. Các mô hình lập trình song song. 12
1.1.4. Đánh giá hiệu quả tính toán song song. 14
1.2. THIẾT KẾ GIẢI THUẬT SONG SONG 20
1.2.1. Nguyên lý thiết kế giải thuật song song. 20
1.2.2. Nhận thức vấn đề và chương trình có thể song song hóa. 21
1.2.3. Thiết kế giải thuật song song bằng phân rã phục thuộc dữ liệu. 23
1.2.4. Thiết kế giải thuật song song bằng phương pháp chia để trị 24
1.2.5. Ví dụ thiết kế giải thuật song song cho bài toán tính tổng. 25
1.2.6. Ví dụ thiết kế giải thuật song song cho bài toán sắp xếp. 27
1.3. TỔNG KẾT CHƯƠNG 1. 29
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 30
2.1. CẤU TRÚC HỆ THỐNG XỬ LÝ ĐỒ HỌA GPU 30
2.1.1. Giới thiệu công nghệ GPU 30
2.1.2. Kiến trúc GPU 31
2.1.3. So sánh GPU và CPU 35
2.2. CÔNG NGHỆ TÍNH TOÁN HỖ TRỢ SONG SONG DỮ LIỆU CUDA 37
2.2.1. Giới thiệu công nghệ CUDA 37
2.2.2. Ứng dụng của CUDA trong các lĩnh vực công nghệ. 39
2.2.3. Môi trường lập trình với CUDA 40
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. 63
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Ự 66
3.2.1. Mô tả bài toán. 66
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


MỞ ĐẦU
Nhu cầu tính toán trong lĩnh vực khoa học, công nghệ ngày càng cao và trở thành một thách thức lớn. Từ đó các giải pháp nhằm tăng tốc độ tính toán đã được ra đời, từ năm 2001 đến năm 2003 tốc độ của Pentium 4 đă tăng gấp đôi từ 1.5GHz lên đến 3GHz. Tuy nhiên hiệu năng của CPU (Central Processing Unit) không tăng tương xứng như mức gia tăng xung của CPU và việc gia tăng tốc độ xung của CPU nhanh chóng chạm phải ngưỡng tối đa mà cụ thể trong khoảng thời gian 2 năm từ năm 2003 đến năm 2005 tốc độ của CPU chỉ tăng từ 3GHz lên 3.8GHz. Trong quá trình tăng tốc độ xung của CPU các nhà sản xuất đã gặp phải vấn đề về nhiệt độ của CPU sẽ quá cao và các giải pháp tản nhiệt khí đã đến mức tới hạn không thể đáp ứng được khả năng làm mát khi CPU hoạt động ở xung quá cao như vậy. Vì vậy việc gia tăng xung hoạt động của CPU không sớm thì muộn cũng sẽ đi vào bế tắc.
Trước tình hình này, các nhà nghiên cứu vi xử lý đã chuyển hướng sang phát triển công nghệ đa lõi, nhiều lõi, với cơ chế xử lý song song trong các máy tính nhằm tăng hiệu năng và tiết kiệm năng lượng.
Một trong các công nghệ xử lý song song ra đời đó là GPU (Graphics Processing Unit - bộ xử lý đồ họa). Ban đầu, việc chế tạo GPU chỉ với những mục đích công việc phù hợp với khả năng là tăng tốc độ xử lý đồ họa, cũng như trong ngành trò chơi là chủ yếu. Nhưng đến thời điểm GPU NV30 của NVIDIA ra đời, GPU bắt đầu tham gia vào những công việc khác ngoài đồ họa như: Hỗ trợ tính toán dấu chấm động đơn, hỗ trợ tính toán lên cả ngàn lệnh. Vì thế đã nảy sinh ra ý tưởng dùng GPU để xử lý, tính toán song song những chương trình không thuộc đồ họa.
Câu hỏi được đặt ra là làm thế nào để ứng dụng GPU vào việc xử lý tính toán song song? Câu hỏi này nhanh chóng được giải quyết bằng công nghệ CUDA (Compute Unified Device Architecture – kiến trúc thiết bị hợp nhất cho tính toán) của NVIDIA ra đời năm 2007. Với CUDA, các lập trình viên nhanh chóng phát 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 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.
- Chuyển đổi một số giải thuật xử lý trình tự sang tính toán song song sao cho tốc độ tính toán nhanh hơn giải thuật cũ, phát biểu bài toán thực tế có áp dụng giải thuật trên, cài đặt và giải quyết trên thiết bị xử lý đồ họa GPU bằng ngôn ngữ lập trình CUDA.
Phạm vi nghiên cứu
Nghiên cứu chuyển một số giải thuật cơ bản tuần tự sang song song chạy trên thiết bị đồ họa GPU của NVIDIA bằng ngôn ngữ CUDA.
3. Phương pháp nghiên cứu
Đề tài này sẽ kết hợp hai phương pháp nghiên cứu, đó là:
Phương pháp nghiên cứu lý thuyết
- Nghiên cứu lý thuyết về tính toán song song, các giải thuật tính toán song song.
- Nghiên cứu lý thuyết về cơ chế hoạt động tính toán trong GPU.
Phương pháp nghiên cứu thực nghiệm
Sử dụng phương pháp nghiên cứu lý thuyết kết hợp với nghiên cứu thực nghiệm:
- Thiết kế giải thuật song song và cài đặt bằng CUDA.
- Triển khai xây dựng ứng dụng.
- Chạy thử nghiệm và lưu trữ các kết quả đạt được, sau đó đánh giá lại kết quả.
4. Kết quả dự kiến
Nghiên cứu được một số giải thuật tính toán song song.
Cài đặt các giải thuật tính toán song song chạy trên thiết bị đồ họa GPU.
Xây dựng ứng dụng tính toán trên thiết bị đồ họa GPU sử dụng giải thuật tính toán song song.
5. Ý nghĩa khoa học và thực tiễn của luận văn
Về mặt lý thuyết
- Nắm được các giải thuật, các mẫu thiết kế tính toán song song.
- Khai thác các bộ thư viện CUDA SDK ứng dụng trong ngôn ngữ lập trình song song bằng CUDA.
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 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.


DANH MỤC TÀI LIỆU THAM KHẢO
Tiếng Việt
[1] PSG TS Nguyễn Đức Nghĩa (2007), Tính Toán Song Song, Nhà xuất bản Đại học Quốc gia Hà Nội.
[2] Đức Khánh (2/2010), “Cuda quá khứ - hiện tại & tương lai của điện toán GPU”, Tạp chí CGEZINE, X4, tr 34 - 41.
[3] Nguyễn Thị Thùy Linh (2009), Tính toán hiệu năng cao với bộ xử lý đồ họa GPU và ứng dụng, Luận văn thạc sĩ, Đại học Công nghiệp - Đại học quốc gia Hà Nội, tr 17-60.
[4] Ngô Quốc Vinh (2008), Hướng dẫn cách thiết lập dự án CUDA, Kyoto-Japan.
[5] TS Lê Huy Thập (8/2010), Cơ sở lý thuyết song song, Nhà xuất bản thông tin và truyền thông, Hà Nội.
[6] Phạm Mạnh Hùng (2007), Các kỹ thuật toán học cho bài toán so sánh đa trình tự, Luận văn thạc sĩ Khoa học máy tính, Đại học Bách khoa thành phố Hồ Chí Minh.
[7] Trịnh Công Quý (2005), Phát triển ứng dụng song song với OpenMP, Luận văn tốt nghiệp Đại học, Đại học Công nghệ - Đại học quốc gia Hà Nội, tr 3, 12.
Tiếng Anh
Alfred J. Menezes, Paul C. Van Oorschot, Scott A. Vanstone (1997), Handbook of Applied Cryptography, CRC Press,.
[8] Thuy T.Nguyen, Duc H.Nguyen, Phong H.Phan (2010), Accelerating Smith-Waterman local sequence alignment on GPU cluster, Department of Information Systems Hanoi University of Science and Technology Hanoi, Vietnam.
[9] NVIDIA (3/6/2011), NVIDIA CUDA C Programming Guide, NVIDIA CUDA.
Trang Web
Trang web http://www.cgnewspaper.com/vi
Đoạn phim tại http://www.youtube.com/v/ZrJeYFxpUyQ
Website: http://www.nvidia.com/physX
Website: http://developer.nvidia.com/object/physx.html
Website http://www.nvidia.com/object/cuda_gpus.html