Luận văn: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

Chia sẻ: Nhung Thi | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

92
lượt xem 18
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bo mạch đồ họa (graphics adapter), card màn hình (graphics card), thiết bị đồ họa, card màn hình, card đồ họa đều là tên gọi chung của thiết bị chịu trách nhiệm xử lý các thông tin về hình ảnh trong máy tính. Bo mạch đồ họa thường được kết nối với màn hình máy tính giúp người sử dụng máy tính có thể giao tiếp với máy tính. Mọi máy tính cá nhân, máy tính xách tay đều phải có bo mạch đồ họa....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn: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

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 TÓM T T LU N VĂN TH C SĨ K THU T Đà N ng - Năm 2011
Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Ngư i hư ng d n khoa h c: TS. Nguy n Thanh Bình Ph n bi n 1: PGS.TS. Phan Huy Khánh Ph n bi n 2: TS. Trương Công Tu n Lu n văn ñư c b o v t i H i ñ ng ch m Lu n văn t t nghi p th c sĩ k thu t h p t i Đ i h c Đà N ng vào ngày 11 tháng 9 năm 2011. Có th tìm hi u lu n văn t i: • Trung tâm Thông tin - H c li u, Đ i h c Đà N ng • Trung tâm H c li u, Đ i h c Đà N ng
-1- M Đ U 1. Lý do ch n ñ tài 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 ñã
-2- 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”. 2. 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.
-3- Đánh giá k t qu theo yêu c u c a ñ tài. 3. Đ 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. 4. Phương pháp nghiên c u 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 . 5. Ý nghĩa khoa h c và th c ti n c a ñ tài Ý nghĩa khoa h c
-4- - 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. Ý nghĩa 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 Lu n văn bao g m 3 chương sau ñây: 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.
-5- 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. CHƯƠNG 1: CƠ S LÝ THUY T 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 gi i thu t 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. 1.1. T NG QUAN V TÍNH TOÁN SONG SONG 1.1.1. T ng quan v tính toán song song 1.1.1.1. L ch s ra ñ i tính toán song song Trong nh ng th p niên 60, n n t ng ñ thi t k máy tính ñ u d a trên mô hình c a John Von Neumann (Xem 0Hình 1.1.), v i m t ñơn v x lý ñư c n i v i m t vùng lưu tr làm b nh và t i m t th i ñi m ch có m t l nh ñư c th c thi. Hình 1.1. Mô t ki n trúc Von Neumann
-6- V i nh ng bài toán yêu c u v kh năng tính toán và lưu tr l n thì mô hình ki n trúc này còn h n ch . Đ tăng cư ng s c m nh tính toán gi i quy t các bài toán l n có ñ tính toán cao, ngư i ta ñưa ra ki n trúc m i, v i ý tư ng k t h p nhi u b x lý vào trong m t máy tính, mà hay g i là x lý song song (Multiprocessor) ho c k t h p s c m nh tính toán c a nhi u máy tính d a trên k t n i m ng. K t lúc này, ñ khai thác ñư c s c m nh ti m tàng trong mô hình máy tính nhi u b x lý song song, cũng như trong mô hình m ng máy tính x lý song song thì các gi i thu t tu n t không còn phù h p n a cho nên vi c xây d ng thi t k gi i thu t song song là ñi u quan tr ng. Gi i thu t song song có th phân rã công vi c trên các ph n t x lý khác nhau. 1.1.1.2. T i sao ph i tính toán song song 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. M c ñích c a x lý song song 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, 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.
-7- 1.1.2. Phân lo i các ki n trúc song song 1.1.2.1. Ki n trúc ñơn dòng l nh ñơn lu ng d li u (SISD) 1.1.2.2. Ki n trúc ñơn dòng l nh ña lu ng d li u (SIMD 1.1.2.3. Ki n trúc ña dòng l nh ñơn d li u (MISD) 1.1.2.4. Ki n trúc ña dòng l nh ña lu ng d li u (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 Hình 1.6. 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 1.1.3.3. Mô hình song song d li u 1.1.3.4. Mô hình hư ng ñ i tư ng 1.1.3.5. Mô hình logic 1.1.4. Đánh giá hi u qu tính toán song song 1.1.4.1. Th i gian th c hi n Th i gian tính toán Th i gian truy n thông Th i gian r i 1.1.4.2. Tăng t c và hi u qu 1.1.4.3. Tính qui mô 1.2. THI T K GI I THU T SONG SONG Trong ph n này ñ c p ñ n phương pháp thi t k gi i thu t song song cho bài toán, quá trình thi t k gi i thu t th t s không d dàng ñ có th rút g n thành m t công th c ñơn gi n như công th c gi i h phương trình b c hai, gi i h phương trình tuy n tính, … mà yêu c u có s s p x p tư duy sáng t o. M c ñích c a ph n này ñưa ra m t
-8- khung thi t k , m t s ñánh giá mang tính toán h c nh m gi m b t nh ng chi phí do ph i quay lui l i sau khi l a ch n phương án không h p lý. 1.2.1. Nguyên lý thi t k gi i thu t song song Khi thi t k gi i thu t song song, c n ph i th c hi n: - 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. - 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. Khi thi t k gi i thu t song song, c n tuân th 5 nguyên lý sau: Các nguyên lý l p l ch: M c ñích là gi m t i thi u các b x lý s d ng trong gi i thu t sao cho th i gian tính toán là không tăng (xét theo khía c nh ñ ph c t p). Nguyên lý hình ng: Nguyên lý này ñư c áp d ng khi bài toán xu t hi n m t dãy các thao tác { T1, T2, . . ., Tn}, trong ñó Ti+1 th c hi n sau khi T1 k t thúc. Nguyên lý chia ñ tr : Chia bài toán thành nh ng ph n nh hơn tương ñ i ñ c l p v i nhau và gi i quy t chúng m t cách song song. Nguyên lý ñ th ph thu c d li u: Phân tích m i quan h d li u trong tính toán ñ xây d ng ñ th ph thu c d li u và d a vào ñó ñ xây d ng gi i thu t song song. Nguyên lý ñi u ki n tranh ñua: N u hai ti n trình cùng mu n truy c p vào cùng m t m c d li u chia s thì chúng ph i tương tranh v i nhau, nghĩa là chúng có th c n tr l n nhau. 1.2.2. Nh n th c v n ñ và chương trình có th song song hóa Trư c khi dùng th i gian và s c l c nh m phát tri n gi i pháp song song cho m t v n ñ , hãy xác ñ nh có ph i ñó là m t trong nh ng v n ñ mà trên th c t có th song song hóa ñư c hay không.
-9- 1.2.3. Thi t k gi i thu t song song b ng phân rã ph c thu c d li u 1.2.4. Thi t k gi i thu t song song b ng phương pháp chia ñ tr 1.2.5. Ví d thi t k gi i thu t song song cho bài toán tính t ng 1.2.5.1. Xây d ng gi i thu t tu n t 1.2.5.2. Xây d ng gi i thu t song song 1.2.6. Ví d thi t k gi i thu t song song cho bài toán s p x p 1.2.6.1. Gi i thu t s p x p tu n t 1.2.6.2. Xây d ng gi i thu t song song 1.3. T NG K T CHƯƠNG 1 Trong chương này ñã trình bày ñư c m t s lý thuy t cơ b n v l p trình song song như: Phân lo i các ki n trúc song song, các mô hình l p trình song song và cách th c ñánh giá hi u qu gi i thu t song song. Ngoài ra, trong chương m t còn trình bày m t s nguyên lý thi t k gi i thu t song song cho bài toán chia ñ tr , phân rã ph thu c d li u, … và áp d ng xây d ng gi i thu t song song cho m t s bài toán cơ b n như s p x p t ñó áp d ng ñ song song hóa m t bài toán trình t . Môi trư ng ñ tri n khai các gi i thu t song song trong lu n văn dùng ngôn ng CUDA th c thi trên thi t b ñ h a GPU c a hãng NVIDA. N i dung chi ti t v ph n này ñư c trình bài trong chương hai.
- 10 - 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 và ñư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. 2.1. C U TRÚC H TH NG X LÝ Đ H A GPU 2.1.1. Gi i thi u công ngh GPU B x lý ñ h a (Graphic Proccessing Unit) g i t c là GPU ñã tr thành m t ph n không th tách r i c a h th ng máy tính ngày nay. Trong sáu năm v a qua ñã ñánh d u s gia tăng n tư ng trong hi u su t và kh năng c a GPU. GPU hi n ñ i không ch là m t công c x lý ñ h a m nh mà còn là m t b x lý h tr l p trình song song m c cao, giúp gi i các bài toán s h c c n kh năng x lý s h c ph c t p và băng thông b nh tăng hơn ñáng k so v i CPU cùng lo i. S tăng t c nhanh chóng c a GPU trong c kh năng h tr l p trình và năng l c tính toán c a nó ñã t o ra m t xu hư ng nghiên c u m i. M t c ng ñ ng ñã nghiên c u và ñã ánh x thành công m t lư ng l n các v n ñ ph c t p ñòi h i tính toán l n vào GPU. Đi u này trong n l c chung nh m m c ñích 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 m c ñích thông d ng trên GPU là m t thay th h p d n cho CPU t i trong h th ng máy tính hi n ñ i. Trong m t tương lai không xa,
- 11 - 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. 2.1.2. Ki n trúc GPU GPU là m t b x lý v i dư th a tài nguyên tính toán. Tuy nhiên, xu hư ng quan tr ng nh t g n ñây ñó là trưng bày kh năng tính toán ñó cho các l p trình viên. Nh ng năm g n ñây, GPU ñã phát tri n t m t hàm c ñ nh, b x lý chuyên d ng t i b x lý l p trình song song, ñ y ñ tính năng ñ c l p v i vi c b sung thêm các ch c năng c ñ nh và các ch c năng chuyên bi t. Hơn bao gi h t 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. 2.1.2.1. Đư ng ng d n ñ h a 2.1.2.2. Ti n hóa c a ki n trúc GPU 2.1.2.3. Ki n trúc GPU hi n ñ i 2.1.3. So sánh GPU và CPU CPU là b vi x lý trung tâm dùng ñ tính toán và x lý các chương trình vi tính, d ki n... và ñóng vai trò ñi u ph i ho t ñ ng c a các thi t b khác. Còn GPU là b vi x lý chuyên x lý các d li u v hình nh, ñ h a. Ngày nay c CPU và GPU ñ u có nh ng bư c phát tri n th n t c, m t GPU cao c p có kh năng x lý ñ t t c ñ hàng t phép tính trên giây ( TetaFLops /s). Hình 2.1. So sánh ki n trúc CPU và GPU
- 12 - Hình 2.1. cho th y s ph n t toán h c GPU nhi u hơn h n CPU, ñi u này mang ñ n cho GPU m t kh năng x lý song song c c kỳ hi u qu . 2.2. CÔNG NGH TÍNH TOÁN H TR SONG SONG D LI U CUDA 2.2.1. Gi i thi u công ngh CUDA CUDA là t vi t t t c a thu t ng Compute Unified Device Architecture, t m d ch là ki n trúc thi t b h p nh t cho tính toán. CUDA b t ñ u xu t hi n t tháng b y năm 2007 v i vai trò ban ñ u là m t b công c phát tri n ph n m m d a trên ngôn ng l p trình C. Bây gi CUDA ñang ti n hóa thành ki n trúc ñi n toán GPU, hay còn g i là GPGPU c a NVIDIA. CUDA có m t trên h u h t các GPU ñ i m i c a NVIDIA, t dòng GeForce giành cho gi i trí ñ n Quadro giành cho ñi n toán hình nh chuyên nghi p và dòng Tesla cho tính toán hi u năng cao. B ph n m m CUDA có các l p mô t trong Hình 2.3. g m: B ñi u khi n cho ph n c ng, API l p trình, môi trư ng th c thi và hai thư vi n toán h c m c cao hơn c a các hàm thư ng dùng: CUFFT và CUBLAS. Ph n c ng ñư c thi t k ñ h tr b ñi u khi n h ng nh và l p môi trư ng th c thi. T ñó cho t c ñ cao. Hình 2.3. Ki n trúc b ph n m m CUDA
- 13 - 2.2.2. ng d ng c a CUDA trong các lĩnh v c công ngh 2.2.2.1. CUDA cho ngành công nghi p trò chơi 2.2.2.2. CUDA cho các ng d ng video s 2.2.3. Môi trư ng l p trình v i CUDA Đ chương trình CUDA ho t ñ ng ñư c trong môi trư ng windows ho c linux, c n ph i có các thư vi n h tr . Các thư vi n này do NVIDIA cung c p g m có các ph n sau: Trình ñi u khi n thi t b ñ h a cho GPU c a NIVIDA, b công c phát tri n CUDA (g i là CUDA Toolkit) và b CUDA SDK. 2.2.4. Cơ ch ho t ñ ng m t chương trình CUDA Đ hi u cách ho t ñ ng m t chương trình CUDA (Xem Hình 2.6.), c n th ng nh t m t s các khái ni m sau: Host: Là nh ng tác v và c u trúc ph n c ng, ph n m m ñư c x lý t CPU. Divice: Là nh ng tác v và c u trúc phân c ng, ph n m m ñư c x lý t i GPU. Hình 2.6. Sơ ñ ho t ñ ng truy n d li u gi a Host và Device Cách ho t ñ ng ñư c mô t như sau: Bư c 1: D li u c n ñư c tính toán luôn trên b nh c a Host vì v y bư c ñ u tiên là truy n d li u c n tính toán t b nh Host qua b nh Device.
- 14 - Bư c 2: Sau ñó Device s g i các hàm riêng c a mình ñ tính toán d li u ñó. Sau khi tính toán xong, d li u c n ñư c tr v l i cho b nh c a Host. 2.2.5. Mô hình l p trình 2.2.5.1. B ñ ng x lý ña lu ng m c cao 2.2.5.2. Gom lô các lu ng 2.2.6. Mô hình b nh 2.2.7. Tìm hi u ngôn ng l p trình CUDA 2.2.7.1. Ngôn ng l p trình CUDA là m r ng c a ngôn ng l p trình C 2.2.7.2. Nh ng m r ng c a ngôn ng l p trình CUDA so v i ngôn ng C 2.2.7.3. T khóa ph m vi ki u hàm 2.2.7.4. T khóa ph m vi ki u bi n 2.2.7.5. Th c hi n c u hình 2.2.7.6. Các bi n Built-in 2.2.7.7. Các l nh ñi u khi n 2.2.7.8. Các l nh b nh 2.2.7.9. Biên d ch v i NVCC 2.2.8. Ví d tính toán song song b ng CUDA 2.2.8.1. C ng hai ma tr n Mô t bài toán: C ng hai ma tr n A[n][m] và B[n][m], k t qu tr v ma tr n C[n][m]. Hình 2.9. C ng hai ma tr n
- 15 - 2.2.8.2. Nhân hai ma tr n Mô t bài toán: Nhân hai ma tr n A[n][k] và B[k][m], k t qu tr v ma tr n C[n][m]. Hình 2.10. Nhân hai ma tr n 2.3. T NG K T CHƯƠNG 2 Trong chương này ñã trình bày ki n trúc c a thi t b ñ h a GPU, so sánh s khác nhau gi a GPU và CPU, các ng d ng trên thi t b GPU ña lõi. Trình bày sơ lư c v ngôn ng l p trình CUDA, cách biên d ch m t chương trình CUDA ch y trên thi t b ñ h a GPU c a NVIDA. Vi t m t s ví d v l p trình song song, t ñó th y ñư c s c m nh tính toán trên thi t b ñ h a GPU ña lõi. Trong chương ti p theo, trình bày cách xây d ng gi i thu t song song ñ gi i quy t m t bài toán ch y b ng CUDA.
- 16 - 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 Chương này s v n d ng cơ s lý thuy t v l p trình song song ñã trình bày trong chương m t và s d ng d ng công ngh l p trình song song CUDA trên thi t b ñ h a (GPU) ñã trình bày trong chương hai ñ gi i bài toán v tin sinh h c so sánh trình t b ng gi i thu t quy ho ch ñ ng, gi i thu t Smith-Waterman. Đ tìm hi u gi i quy t bài toán so sánh trình t , chương này còn trình bày m t s khái ni m cơ b n v tin sinh h c như: AND, protein, … T ñó mô t bài toán và gi i quy t b ng gi i thu t song song v i CUDA. Đưa ra nh ng so sánh, ñánh giá v l i ích c a vi c s d ng gi i thu t song song ñ i v i bài toán này. 3.1. GI I THI U Ph n này gi i thi u nh ng ki n th c cơ b n v tin sinh h c và m t s khái ni m v tin sinh h c nh m ph c v cho vi c tìm hi u bài toán so sánh trình t theo h gen. 3.1.1. So sánh trình t Trong quá trình phân tích trình t thì khái ni m so sánh trình t ñóng vai trò quan tr ng. Đây là n n t ng cơ b n cho vi c phân tích. So sánh trình t giúp cho quá trình d báo s gi ng nhau v ch c năng c a các trình t , d báo c u trúc b c ba c a DNA, protein. Trong vi c tìm hi u m t gene m i, m i ngư i thư ng quan tâm ñ n vi c xác ñ nh nh ng ñ c ñi m ñ phân bi t gene ñ ng th i ñưa ra nh ng gi thuy t v ch c năng c a gene. Vi c ñưa ra nh ng gi thuy t v ch c năng c a gene thư ng d a vào nh ng gi i thu t ñánh giá s gi ng nhau, tương ñ ng gi a các trình t .
- 17 - 3.1.2. Đ nh nghĩa so sánh trình t So sánh trình t (còn g i là phép gióng hàng, gióng c t) là quá trình nghiên c u s gi ng nhau gi a các chu i trình t (sequence), ño lư ng s gi ng nhau gi a các trình t . Cách th c so sánh gi a hai hay nhi u trình t d a trên vi c so sánh m t chu i các thành ph n (ký t ) c a trình t ñ tìm ra nh ng ñi m tương ñ ng, gi ng nhau gi a các trình t . Các trình t ñư c ñ c p trong ph n nghiên c u này là các chu i trình t DNA, RNA ho c các trình t amino acid (protein). Xét 2 chu i: A C G C T G, C A T G T và ño lư ng s gi ng nhau gi a hai chu i này. Hình 3.1. là m t ví d v k t qu ño lư ng s gi ng nhau c a hai chu i trên. Tiêu chí ñ ñánh giá s gi ng nhau c a hai chu i trên s d a trên m t hàm ñánh giá (scoring function). Hình 3.1. Ví d v so sánh hai trình t Ký t “–“ ñư c g i là m t gap, gap th hi n cho ý nghĩa trong sinh h c ñó là m t ph n c a trình t ñã b m t ñi do, các hành vi c a quá trình ti n hóa sinh v t như: ñ t bi n, s m t ñi m t thành ph n trong chu i trình t . Giá tr hàm ñánh giá càng cao thì k t qu so sánh trình t càng t t. Xét m t hàm ñánh giá ñơn gi n như sau: N u hai thành ph n trong chu i là gi ng nhau thì hàm ñánh giá s có k t qu +2, n u hai thành ph n trong chu i khác nhau thì hàm ñánh giá t i v trí này s có k t qu -1. Như v y k t qu so sánh trên s có giá tr hàm ñánh giá là: 3*(2)+(-1)*5=1. 3.1.3. H th ng ký t T p h p các ph n t có th xu t hi n trong trình t g i là m t h th ng các ký t ( ∑ ). Trong ADN, s d ng m t th th ng kí t ∑ =
- 18 - {A, C, G, T, λ} trong ñó A, C, G, T ñ i di n cho b n nucleotides: adenine (A), cytosine (C), guanine (G) và thymine (T). λ là ký t ñ c bi t ñ i di n cho m t kho ng tr ng là m t v trí mà không có nucleotide th c t . Trong h u h t các trư ng h p, ký t gap (‘-‘) có th ñư c s d ng ñ thay th cho λ. B t kỳ m t trình t nào cũng là m t s th hi n b i các ph n t có th xu t hi n trong trình t và ñư c ñ nh nghĩa trong ∑ . 3.1.4. Các phép bi n ñ i Phép thay th : Phép chèn – xóa: Phép ñ o ngư c: Phép d ch chuy n: 3.1.5. Kho ng cách 3.1.6. S p hàng trình t h gen 3.1.7. Các thu t toán s p hàng trình t h gen 3.2. PHÁT BI U BÀI TOÁN SO SÁNH TRÌNH T 3.2.1. Mô t bài toán G i S1 và S2 là hai chu i, m t s so sánh trình t gi a S1 và S2 t o ra hai chu i S1’ và S2’ b ng cách thêm các ký t gap “-“ vào S1 và S2, trong ñó: * |S1’|=|S2’| * N u lo i b các ký t “-“ kh i S1’ và S2’ ta s có S1 và S2. V i | S1|, | S2| l n lư t là chi u dài c a S1 và S2. Hình 3.2. So sánh hai trình t 3.2.2. Hư ng gi i quy t b ng gi i thu t quy ho ch ñ ng Ph n này gi i thi u hư ng gi i quy t bài toán so sánh trình t b ng phương pháp quy ho ch ñ ng. K thu t này cho phép xây d ng