Mẫu 1a MẪU BÌA LUẬN VĂN CĨ IN CHỮ NHŨ VÀNG Khổ 210 x 297 mm PHẠM HỒNG PHONG BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI - Phạm Hồng Phong CHUYÊN NGHÀNH CÔNG NGHỆ THƠNG TIN ÁP DỤNG CƠNG NGHỆ TÍNH TỐN SONG SONG CUDA CHO BÀI TỐN BẮT CẶP ĐA TRÌNH TỰ LUẬN VĂN THẠC SĨ KHOA HỌC CƠNG NGHỆ THƠNG TIN KHỐ 2010 Hà Nội – Năm 2011 MẪU TRANG PHỤ BÌA LUẬN VĂN Mẫu 1b BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Phạm Hồng Phong ÁP DỤNG CƠNG NGHỆ TÍNH TỐN SONG SONG CUDA CHO BÀI TỐN BẮT CẶP ĐA TRÌNH TỰ Chun ngành : CƠNG NGHỆ THÔNG TIN LUẬN VĂN THẠC SĨ KHOA HỌC CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC : TS NGUYỄN HỮU ĐỨC Hà Nội – Năm 2011 LỜI CAM ĐOAN T 35T LỜI CẢM ƠN T 35T DANH MỤC TỪ VIẾT TẮT VÀ THUẬT NGỮ T T DANH MỤC BẢNG T 35T DANH MỤC HÌNH VẼ T 35T CHƯƠNG 1: GIỚI THIỆU CHUNG T T 1.1 Tin sinh học ứng dụng T T 1.2 Cơng nghệ tính tốn đa dụng GPGPU xử lý đồ họa 10 T T 1.3 Lý chọn đề tài 11 T 35T 1.4 Mục đích nghiên cứu luận văn, đối tượng nghiên cứu 12 T T 1.5 Các nội dung đóng góp tác giả 12 T T 1.6 Phương pháp nghiên cứu 13 T T CHƯƠNG 2: BÀI TOÁN BẮT CẶP ĐA CHUỖI 14 T T 2.1 Tin sinh học chuỗi sinh học 14 T T 2.1.1 Các chuỗi sinh học 14 T 35T 2.1.2 Mã hóa chuỗi sinh học 14 T T 2.2 Bài tốn bắt cặp đơi trình tự 16 T T 2.2.1 Khái niệm 17 T 35T 2.2.2 Phương pháp tính điểm 18 T T 2.2.3 Bắt cặp toàn cục bắt cặp cục 22 T T 2.2.4 Giải thuật 23 T 35T 2.3 Bài tốn bắt cặp đa trình tự 24 T T 2.3.1 Khái niệm 24 T 35T 2.3.2 Phương pháp tính điểm 25 T T Áp dụng cơng nghệ tính toán song song CUDA cho toán bắt cặp đa trình tự 2.3.3 Giải thuật 26 T 35T CHƯƠNG 3: CƠNG NGHỆ TÍNH TỐN ĐA DỤNG T T TRÊN BỘ XỬ LÝ ĐỒ HỌA29 T T 3.1 Bộ xử lý đồ họa đa lõi NVIDIA 29 T T 3.1.1 Giới thiệu chung 29 T 35T 3.1.2 Kiến trúc xử lý đồ họa đa lõi NVIDIA 30 T T 3.1.3 Hiệu tính toán 34 T T 3.2 Bộ công cụ phát triển ứng dụng CUDA 36 T T 3.2.1 Giới thiệu chung 36 T 35T 3.2.2 Kiến trúc xử lý 37 T 35T 3.2.3 C cho CUDA 38 T 35T 3.2.4 Phân cấp nhớ 39 T 35T 3.2.5 Cài đặt 40 T 35T 3.3 Tổng quan GPUCluster 41 T T CHƯƠNG 4: GIẢI THUẬT BẮT CẶP ĐA TRÌNH TỰ TRÊN GPU 43 T T 4.1 Giải thuật bắt cặp đa trình tự Clustal 43 T T 4.1.1 Giới thiệu chung 43 T 35T 4.1.2 Bước 1: Bắt cặp đơi trình tự 44 T T 4.1.3 Bước 2: Xây dựng tiến hóa 45 T T 4.1.4 Bước 3: Bắt cặp đa trình tự 47 T T 4.2 Song song hóa giải thuật bắt cặp đa trình tự Clustal GPU 50 T T 4.2.1 Chiến lược song song hóa 50 T T 4.2.2 Song song hóa cho CUDA 51 T T 4.2.3 Phương pháp song song hóa theo dải cho bước 53 T T 4.2.4 Song song hóa cho bước 58 T T Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự 4.2.4 Thử nghiệm đánh giá 59 T T 4.2.4.1 Môi trường thử nghiệm 59 T T 4.2.4.2 Dữ liệu thử nghiệm 61 T 35T 4.2.4.3 Kết thử nghiệm 62 T 35T 4.3 Song song hóa giải thuật bắt cặp đơi trình tự Smith-Waterman T GPUCluster 65 35T 4.3.1 Song song hóa giải thuật 65 T T 4.3.1 Kết thử nghiệm 67 T 35T CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 70 T T 5.1 Kết luận 70 T 35T 5.2 Hướng phát triển 70 T 35T TÀI LIỆU THAM KHẢO 72 T 35T Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự LỜI CAM ĐOAN Tôi – Phạm Hồng Phong – xin cam đoan • Luận văn tốt nghiệp Thạc sĩ công trình nghiên cứu thân tơi hướng dẫn TS Nguyễn Hữu Đức • Các kết Luận văn tốt nghiệp trung thực, chép tồn văn cơng trình khác Hà nội, ngày 10 tháng 11 năm 2011 Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự LỜI CẢM ƠN Tôi xin gửi lời cảm ơn sâu sắc tới thầy giáo – Tiến sĩ Nguyễn Hữu Đức – giám đốc Trung tâm tính tốn hiệu cao ĐHBKHN, người tận tình hướng dẫn theo dõi sát tơi q trình thực luận văn Ngay từ ngày đầu chọn lựa đề tài cho luận văn, Thầy người đưa ý tưởng, giúp tơi xác định tốn mục đích nghiên cứu Cùng với q trình thực luận văn này, Thầy đưa nhận xét, lời khun định hướng có ích để tơi hồn thành luận văn Tiếp theo, tơi xin gửi lời cảm ơn chân thành tới Thầy giáo – Giáo sư, Tiến sĩ – Nguyễn Thanh Thủy – Hiệu phó trường Đại học Cơng nghệ, ĐHQGN Thầy để lại nhiều điều đáng học hỏi Thầy cịn giám đốc Trung tâm tính tốn hiệu cao ĐHBKH Tơi học hỏi từ Thầy nhiều, từ cách thức phương pháp làm khoa học, nghiên cứu điều sống Tôi gửi lời cảm ơn tới đồng nghiệp bạn nhóm nghiên cứu tính tốn đa lõi MCG Trung tâm tính tốn hiệu cao ĐHBKHN Có thể nói luận văn khơng hồn thành trọn vẹn khơng có phối hợp cộng tác thành viên nhóm: KS Dương Nhật Tân, KS Nguyễn Hữu Bảo Trung Cũng xin gửi lời cảm ơn tới đồng nghiệp khác tơi Trung tâm tính tốn hiệu cao, Bộ môn HTTT Viện CNTT&TT ĐHBKHN, học hỏi từ người nhiều điều chan hịa, chia sẻ người giúp cho thực luận văn tốt Cuối cùng, xin gửi lời tri ân từ tận đáy lịng tới ba Phạm Đình Ba mẹ Nguyễn Thị Kim Lan Sự hi sinh to lớn ba mẹ giúp có ngày hơm nay, ba mẹ chỗ dựa cho sống Hà nội, ngày 10 tháng 11 năm 2011 Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự DANH MỤC TỪ VIẾT TẮT VÀ THUẬT NGỮ Từ viết tắt/ thuật ngữ Ý nghĩa GPU Graphics Processing Unit, xử lý đồ họa CPU Central Processing Unit, xử lý trung tâm CUDA Compute Unified Device Architecturec, kiến trúc tính tốn song song sử dụng xử lý đồ họa phát triển NVIDIA GPGPU General Purpose computation on GPU, công nghệ tính tốn đa dụng xử lý đồ họa, ứng dụng GPU vào lĩnh vực tính tốn vốn thuộc CPU ADN Axit Deoxyribo Nucleic, chuỗi sinh học làm nhiệm vụ lưu trữ gen giống loài ARN Axit Ribo Nucleic, chuỗi sinh học làm nhiệm vụ truyền đạt gen trình xây dựng chuỗi protein tế bào BLOSUM BLOcks of amino acid SUbstitution Matrix, ma trận trọng số protein xây dựng nên từ kết thống kê nghiên cứu khứ kernel nhân, phần code chương trình chạy GPU chương trình CUDA thread luồng, phần tử tính toán nhỏ kiến trúc CUDA, luồng thực instance kernel lõi xử lý GPU đảm nhận block nhóm thread, đa xử lý GPU đảm nhận grid nhóm block, GPU đảm nhận xử lý toàn grid Clustal giải thuật bắt cặp đa trình tự phổ biến, sử dụng để song song hóa luận văn Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự DANH MỤC BẢNG Bảng 1: Các ký tự mã hóa cho chuỗi ADN/ARN hỗ trợ định dạng FASTA 15 U T T U Bảng 2: Các ký tự mã hóa cho chuỗi protein hỗ trợ định dạng FASTA 15 U T T U Bảng 3: Ma trận trọng số protein BLOSUM62 21 U T T U Bảng 4: Các nhớ CUDA 39 U T T U Bảng 5: Cấu hình GPU hệ thống Bkluster 61 U T T U Bảng 6: So sánh thời gian chạy CUDAClustal Clustal 64 U T T U Bảng 7: So sánh thời gian chạy theo bước CUDAClustal Clustal 64 U T T U Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự DANH MỤC HÌNH VẼ Hình 1: Minh họa bắt cặp đơi trình tự 17 U T T U Hình 2: Minh họa cách bắt cặp đơi trình tự chuỗi 17 U T T U Hình Bắt cặp đa trình tự sinh phần mềm ClustalX 24 U T T U Hình GPU GeForce 6600GT 29 U T T U Hình 5: Kiến trúc Streaming Processor 30 U T T U Hình 6: Kiến trúc Streaming Multiprocessor 31 U T T U Hình 7: Kiến trúc Texture/Processor Cluster GPU G80/G92/GT200 32 U T T U Hình 8: Kiến trúc Streaming Processor Array GPU GT80 33 U T T U Hình 9: Kiến trúc GPU GeForce 9800 GTX 34 U T T U Hình 10: So sánh tương quan sử dụng transistor CPU GPU 35 U T T U Hình 11: So sánh hiệu tính tốn GPU CPU 35 U T T U Hình 12: Kiến trúc grid – block – thread 38 U T T U Hình 13: Ví dụ cú pháp C cho CUDA 39 U T T U Hình 14: Giao diện phần mềm ClustalX 2.1 44 U T T U Hình 15: Tính tốn điểm cặp vị trí bắt cặp đa trình tự 48 U T T U Hình 16: Quan hệ phụ thuộc phần tử ma trận độ tương tự 51 U T T U Hình 17: Chiến lược song song hóa 51 U T T U Hình 18: Quá trình tính ma trận theo dải song song hóa nội tác vụ 54 U T T U Hình 19: Sử dụng nhớ song song hóa nội tác vụ 55 U T T U Hình 20: Q trình tính ma trận theo dải song song hóa liên tác vụ 57 U T T U Hình 21: Bắt cặp đa trình tự sinh CUDAClustal 63 U T T U Hình 22: Cách thức phân chia liệu hệ thống GPU Cluster 66 U T T U Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự yêu cầu phải giảm số lượng thread block và/hoặc độ rộng dải thread để tiếp tục sử dụng shared memory register vào mục đích trên, khiến giảm hiệu việc tính tốn song song 4.2.4 Thử nghiệm đánh giá 4.2.4.1 Môi trường thử nghiệm Giải thuật Clustal song song hóa luận văn cài đặt chạy thử nghiệm cụm máy tính đa GPU (GPU cluster) Bkluster đặt Trung tâm tính tốn hiệu cao (High Performance Computing Center – HPCC) thuộc trường Đại học Bách Khoa Hà Nội Cụm máy tính Bkluster bao gồm nút, nút pnode2 pnode trang bị GPU CUDA Giải thuật luận văn chạy thử nút pnode3 với GPU có cấu sau: Device 0: "GeForce GTX 295" CUDA Driver Version: CUDA Runtime Version: CUDA Capability Major revision number: CUDA Capability Minor revision number: Total amount of global memory: Number of multiprocessors: Number of cores: Total amount of constant memory: Total amount of shared memory per block: Total number of registers available per block: Warp size: Maximum number of threads per block: Maximum sizes of each dimension of a block: Maximum sizes of each dimension of a grid: Maximum memory pitch: Texture alignment: Clock rate: Concurrent copy and execution: Run time limit on kernels: Integrated: Support host page-locked memory mapping: Compute mode: can use this device simultaneously) Device 1: "GeForce GTX 295" CUDA Driver Version: 4.0 4.0 939327488 bytes 30 240 65536 bytes 16384 bytes 16384 32 512 512 x 512 x 64 65535 x 65535 x 2147483647 bytes 256 bytes 1.24 GHz Yes No No Yes Default (multiple host threads 4.0 59 Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự CUDA Runtime Version: CUDA Capability Major revision number: CUDA Capability Minor revision number: Total amount of global memory: Number of multiprocessors: Number of cores: Total amount of constant memory: Total amount of shared memory per block: Total number of registers available per block: Warp size: Maximum number of threads per block: Maximum sizes of each dimension of a block: Maximum sizes of each dimension of a grid: Maximum memory pitch: Texture alignment: Clock rate: Concurrent copy and execution: Run time limit on kernels: Integrated: Support host page-locked memory mapping: Compute mode: threads can use this device simultaneously) Device 2: "GeForce GTX 295" CUDA Driver Version: CUDA Runtime Version: CUDA Capability Major revision number: CUDA Capability Minor revision number: Total amount of global memory: Number of multiprocessors: Number of cores: Total amount of constant memory: Total amount of shared memory per block: Total number of registers available per block: Warp size: Maximum number of threads per block: Maximum sizes of each dimension of a block: Maximum sizes of each dimension of a grid: Maximum memory pitch: Texture alignment: Clock rate: Concurrent copy and execution: Run time limit on kernels: Integrated: Support host page-locked memory mapping: Compute mode: threads can use this device simultaneously) Device 3: "GeForce GTX 295" CUDA Driver Version: 4.0 938803200 bytes 30 240 65536 bytes 16384 bytes 16384 32 512 512 x 512 x 64 65535 x 65535 x 2147483647 bytes 256 bytes 1.24 GHz Yes No No Yes Default (multiple host 4.0 4.0 939327488 bytes 30 240 65536 bytes 16384 bytes 16384 32 512 512 x 512 x 64 65535 x 65535 x 2147483647 bytes 256 bytes 1.24 GHz Yes No No Yes Default (multiple host 4.0 60 Áp dụng cơng nghệ tính toán song song CUDA cho toán bắt cặp đa trình tự CUDA Runtime Version: CUDA Capability Major revision number: CUDA Capability Minor revision number: Total amount of global memory: Number of multiprocessors: Number of cores: Total amount of constant memory: Total amount of shared memory per block: Total number of registers available per block: Warp size: Maximum number of threads per block: Maximum sizes of each dimension of a block: Maximum sizes of each dimension of a grid: Maximum memory pitch: Texture alignment: Clock rate: Concurrent copy and execution: Run time limit on kernels: Integrated: Support host page-locked memory mapping: Compute mode: threads can use this device simultaneously) 4.0 939327488 bytes 30 240 65536 bytes 16384 bytes 16384 32 512 512 x 512 x 64 65535 x 65535 x 2147483647 bytes 256 bytes 1.24 GHz Yes No No Yes Default (multiple host Bảng 5: Cấu hình GPU hệ thống Bkluster 4.2.4.2 Dữ liệu thử nghiệm Dữ liệu sử dụng để chạy thử nghiệm luận văn trích từ sở liệu UniProtKB/Swiss-Prot UniProtKB viết tắt Universal Protein Knowledgebase, sở liệu chứa lượng lớn thông tin sinh học protein rút từ nghiên cứu khứ Trong đó, phần Swiss-Prot phần sở liệu đánh giá hiệu chỉnh tay Giải thuật luận văn chạy thử liệu, tương ứng với trường hợp khác nhau: số lượng lớn chuỗi ngắn, số lượng nhỏ chuỗi dài Cụ thể: • test1.fasta: 200 chuỗi, độ dài trung bình 300 • test2.fasta: 300 chuỗi, độ dài trung bình 300 • test3.fasta: 100 chuỗi, độ dài trung bình 800 • test4.fasta: 50 chuỗi, độ dài trung bình 1600 61 Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự 4.2.4.3 Kết thử nghiệm a Kết cài đặt giải thuật Giải thuật bắt cặp đa trình tự song song luận văn cài đặt thành công phần hệ thống Bkluster tên gọi CUDAClustal CUDAClustal song song hóa thành công bước giải thuật Clustal thay đổi bước để chuẩn bị cho việc song song hóa bước Do thiếu thời gian đầu tự công sức thực nghiêm túc nên CUDAClustal khơng song song hóa bước 3, bước cuối giải thuật Clustal Đồng thời CUDAClustal dừng việc sử dụng GPU vào việc tính tốn song song, không đạt mục tiêu sử dụng đa GPU GPU cluster b Chất lượng giải thuật Kết sinh cho thấy CUDAClustal cho cách bắt cặp đa trình tự tương đối tốt Các vùng tương tự chuỗi thể rõ ràng (Hình 21) Tuy chưa tốt giải thuật Clustal nguyên gốc, kết CUDAClustal đạt giá trị sử dụng định 62 Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự Hình 21: Bắt cặp đa trình tự sinh CUDAClustal Trong trình thực luận văn, để đơn giản hóa việc cài đặt giải thuật tập trung vào việc song song hóa, tác giả sử dụng phiên đơn giản giải thuật thành phần giải thuật Clustal Giải thuật CUDAClustal nâng cao chất lượng so với việc sử dụng phiên tốt mặt di truyền học để tiến hành bắt cặp đa trình tự Ngồi ra, giải thuật CUDAClustal bước tồn nhược điểm lớn, khắc phục có thời gian Đó việc tính tốn khoảng cách cặp chuỗi thực toàn lần gọi kernel, nên số lượng chuỗi đầu vào lớn, số lượng block sử dụng vượt kích thước grid cho phép Đồng thời, dung lượng nhớ global memory dùng để lưu kết thread vượt tổng dung lượng GPU dẫn tới lỗi thiếu nhớ c Hiệu tính tốn Về mặt hiệu tính toán, CUDAClustal cho thấy cải thiện đáng kể so với giải thuật Clustal tác giả tự cài đặt để so sánh Đánh giá tổng thể thời 63 Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự gian chạy tồn giải thuật, CUDAClustal có thời gian chạy nhanh vài lần so với Clustal (Bảng 6) Số chuỗi Độ dài chuỗi trung bình CUDAClustal Clustal test1.fasta 200 ~300 120,13s 220,25s test2.fasta 300 ~300 269,88s 545,25s test3.fasta 100 ~800 110,82 327,51 Bộ liệu test4.fasta Thời gian chạy 50 ~1600 121,65s 332,2s Bảng 6: So sánh thời gian chạy CUDAClustal Clustal Cụ thể, CUDAClustal nhanh gấp đôi so với Clustal xử lý liệu có số chuỗi lớn (test1.fasta, test2.fasta), nhanh gấp gần lần trường hợp liệu có chiều dài trung bình lớn (test3.fasta, test4.fasta) Tuy nhiên, CUDAClustal song song hóa bước 1, nên để đánh giá xác mức độ gia tăng hiệu tính tốn, ta cần xem xét đến thời gian chạy bước hai giải thuật (Bảng 7) Kết cho thấy tất liệu, CUDAClustal cho mức tăng hiệu tính tốn tốt: thời gian chạy bước CUDAClustal nhỏ xấp xỉ 30 lần so với Clustal Như vậy, tính riêng phần song song hóa giải thuật, hiệu việc sử dụng GPU vượt xa so với mức mục tiêu đặt Điều có nghĩa bước giải thuật song song hóa, tổng thời gian chạy cịn rút ngắn nhiều Bước Bộ liệu Bước & CUDAClustal Clustal CUDAClustal Clustal 4,40s 124,13s 115,46s 96,12s 0,35s 12,16s 304,28s 257,37s 287,88s 0,04s 8,03s 237,00s 102,48s 90,51s Thao tác nhớ Chạy kernel test1.fasta 0,26s test2.fasta test3.fasta test4.fasta 0,001s 6,51s 233,05s 115,14s 99,15s Bảng 7: So sánh thời gian chạy theo bước CUDAClustal Clustal 64 Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự 4.3 Song song hóa giải thuật bắt cặp đơi trình tự Smith-Waterman GPUCluster Như đề cập trên, phương pháp song song hóa theo dải tác giả đề xuất lợi ích to lớn việc sử dụng nhớ GPU cách linh hoạt cho tốn bắt cặp đa trình tự, nhiên tính phức tạp cài đặt, giải thuật gồm nhiều pha thời gian đầu tư cho luận văn hạn chế nên tác giả chưa cài đặt ý tưởng đề xuất hệ thống gồm nhiều GPU - GPUCluster, mà GPU Mặc dù vậy, tác giả cài đặt thử phiên tốn bắt cặp đơi trình tự giải thuật Smith-Waterman hệ thống nhiều GPU – GPUCluster thu kết khả thi Điều tiền đề quan trọng cho việc hoàn thiện cài đặt toàn giải thuật Clustal hệ thống GPUCluster Trong phần này, tác giả trình bày sơ lược ý tưởng việc song song hóa giải thuật bắt cặp đơi trình tự Smith-Waterman GPUCluster, kết đăng tải Tạp chí quốc tế tính tốn JoC: Phong H.Pham, Tan N.Duong, Ngoc M.Ta, Hung D.Le, Duc H.Nguyen, Thuy T.Ngyen, Cuong Q.Tran, “Applying GPUs for Smith-Waterman sequence alignment acceleration” The GSTF International Journal on Computing, Vol I, Issue ISSN: 2010-2283, trang: 175 – 179 Với đặc tả giải thuật Smith-Waterman phần 4.1.2, với phân tích yếu tố song song hóa q trình tính tốn ma trận, tác giả triển khai hai hướng tiếp cận cho giải thuật Smith-Waterman hệ thống GPU Cluster với hai mức song song mặt liệu trên, song song hóa nội tác vụ song song hóa liên tác vụ, với cài đặt song song giải thuật Smith-Waterman GPUCluster – swGPUCluster 4.3.1 Song song hóa giải thuật Dựa phương pháp song song hóa theo hai mức đề cập trên, chương trình thực phân chia liệu cho hệ thống GPU Cluster để thực 65 Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự GPU máy Hệ thống Cluster sử dụng thư mục liệu chia sẻ chung, đồng hóa máy Thư mục lưu trữ liệu chuỗi sinh học Giả sử hệ thống có n_client máy, máy trang bị n_device GPUs Ban đầu chuỗi liệu chia thành n_client phần dựa vào kích thước liệu Để tránh xung đột truy cập vào tập tin chứa liệu chuỗi, tác giả sử dụng khóa liệu (locker) db_lock ghi trạng thái liệu (data-status-record) db_start cho phiên truy cập máy Khóa liệu ghi trạng thái liệu trung chuyển máy Khi máy kiểm tra thấy liệu khơng bị khóa, tiến hành đọc ghi trạng thái liệu để xác định vị trí liệu vừa đọc gần nhất, để từ tiếp tục nạp liệu vào nhớ máy Kết thúc trình đọc, máy trạm cập nhật lại ghi trạng thái liệu mở khóa liệu Hình 22: Cách thức phân chia liệu hệ thống GPU Cluster Trước liệu phân chia cho GPUs, chúng xếp theo thứ tự tăng dần độ dài chuỗi Sự phân tách hướng tới hai mục đích Thứ nhất, phân chia liệu vào hai block mà thực thi theo hai phương pháp trình bày Quá trình điều khiển tham số chạy chương 66 Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự trình threshold; độ dài chuỗi nhỏ threshold, giao cho block để xử lý, ngược lại block thứ hai Các block tiếp tục phân chia thành n_device phần tương ứng với thiết bị, block phải thực cho khối liệu tương đương theo hai cách Mục đích thứ hai thread block giao cho thực thi chuỗi có độ dài tương đương nên thời gian chạy chúng xấp xỉ nhau, điều làm tăng hiệu việc thực thi giải thuật Chương trình bao gồm hai kernel inter-task intra-task thực giải thuật song song theo hai mức hệ thống GPU Cluster; kernel thực thi song song hóa liên tác vụ kernel cịn lại song song hóa nội tác vụ Sau nạp liệu chuỗi vào nhớ GPU, chương trình gọi đến kernel để thực bắt cặp trình tự Sau kết ghi lại nhớ thiết bị, tiếp ghi lại vào nhớ máy, máy lại thực ghi kết vào tệp tin tạm Tại máy 0, chương trình thực tổng hợp lại kết thực tất máy trạm 4.3.1 Kết thử nghiệm Để đánh giá hiệu chương trình swGPUCluster, thơng thường sử dụng đơn vị CUPS - số ô ma trận H cập nhật giây, bao gồm việc tính tốn giá trị ma trận E, F cách tức thời Cơng thức để tính tốn giá trị CUPS cho bắt cặp trình tự sau: cups = qLen * dbLent/t Ở qLen độ dài chuỗi truy vấn, dbLen độ dài chuỗi tham chiếu, t thời gian chạy chương trình Giá trị t bao gồm thời gian tải liệu từ nhớ máy vào nhớ thiết bị, thời gian tính tốn GPUs thời gian truyền kết cho nút Trong thử nghiệm cài đặt song song giải thuật Smith-Waterman GPUCluster, tác giả sử dụng tập chuỗi truy vấn với độ dài từ 100 đến 5000, sở liệu chuỗi sinh học UniProt phiên 2010_05 - Apr 20, 2010, bao gồm 516.080 chuỗi 181.676.505 amino acids Với sở liệu giá trị ngưỡng threshold 3072, có tới 515.472 chuỗi bắt cặp theo phương pháp 67 Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự song song hóa liên tác vụ 608 chuỗi khác bắt cặp theo phương pháp song song hóa nội tác vụ Các kết cài đặt thử nghiệm hai nút: Node0 Node1 sử dụng multi-GPU (3 cạc GTX295 – 6GPUs cạc Tesla C1060 – 1GPU), với giá trị kích thước block số threads = 256, kích thước grid với số SMs (streaming multi-processors) GPU hiệu hệ thống đạt mức tối ưu Hiệu chương trình Smith-Water man GPUCluster tăng theo độ dài chuỗi truy vấn từ giá trị tối thiểu 37.328 GCPUS đến giá trị cực đại 46.706 GCUPS Dưới kết chạy chương trình swGPUCluster: Tên chuỗi Độ dài chuỗi Thời gian(s) GCUPS P02232 144 0.779393 37.328 P01111 189 0.944164 39.202 P14942 222 1.078783 40.795 P07327 375 1.721378 42.945 P25705 553 2.532260 43.419 P21177 729 3.224185 44.907 P27895 1000 4.337310 45.849 P07756 1500 6.456398 46.065 P04775 2005 8.579664 46.355 P19096 2504 10.681426 46.530 P0C6B8 3564 15.174918 46.612 P08519 4548 19.348871 46.653 P33450 5147 21.894938 46.690 Q9UKN1 5478 23.294546 46.706 Bảng Thời gian thực chương trình song song Smith-Waterman GPUCluster Với kết đạt chạy chương trình, tác giả so sánh với cài đặt tốt trước giải thuật Smith-Waterman là: cudaSW++ swps3 Cài đặt cudaSW++ [20] thử nghiệm cạc GTX295 GPU, kết cho hiệu 68 Áp dụng công nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự thấp 8.387 GCUPS cao 9.232 GCUPS Nếu so sánh với cudaSW++ GPU, tốc độ thực thi swGPUCluster tăng khoảng 4.4 đến lần Một so sánh hiệu khác thực với cài đặt swps3, swps3 [21] thử nghiệm x86/SSE2 bao gồm nút trang bị với vi xử lý Core Quad Q8400 2.66 Ghz lõi, 8GB RAM thực thi với luồng Hiệu swGPUCluster tăng khoảng 13.8 đến 22.8 lần so với cài đặt swps3 kiến trúc x86/SSE2 lõi khoảng 3.4 đến 11.4 lần so với swps3 kiến trúc x86/SSE2 đa lõi 69 Áp dụng công nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 5.1 Kết luận Cơng nghệ tính tốn đa dụng GPU cho thấy khả gia tăng đáng kể hiệu tính tốn tốn song song hóa nói chung tốn bắt cặp đa trình tự nói riêng Trong tốn bắt cặp đa trình tự, việc song song hóa bước giải thuật Clustal đem lại mức tăng hiệu xấp xỉ lần toàn giải thuật xấp xỉ 30 lần riêng bước Bên cạnh đó, song song hóa giải thuật bắt cặp đơi trình tự Smith-Waterman theo hai hướng tiếp cận xuyên suốt, cài đặt thử nghiệm hệ thống gồm nhiều GPU (6 GPUs) cho thấy khả xử lý với lượng liệu lớn kết hợp sức mạnh tính tốn nhiều GPU Kết cho thấy luận văn đạt thành công mức độ định Tuy khơng cài đặt tồn giải thuật hệ thống đa GPU GPU cluster, xây dựng giải thuật song song hóa hiệu đạt hiệu tính tốn gần mong muốn 5.2 Hướng phát triển Giải thuật bắt cặp đa trình tự song song CUDAClustal luận văn cịn cải tiến điểm sau: • Song song hóa bước (bắt cặp đa trình tự) giải thuật Clustal cách thực bắt cặp đa trình tự nút có chiều cao (từ nút lá) song song lúc Việc đặt móng bước (xây dựng tiến hóa), thơng qua việc lưu trữ nút vào mảng phân chia theo chiều cao • Sử dụng phiên tốt mặt di truyền học giải thuật thành giải thuật Clustal (quy hoạch động, neighbor-joining) để tăng chất lượng bắt cặp đa trình tự 70 Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự • Trong bước 1, trường hợp song song hóa liên tác vụ, tiến hành gọi kernel theo gói (batch) có số lượng block cố định để ngăn ngừa việc vượt kích thước grid cho phép, giúp tăng khả xử lý liệu lớn • Tiến hành cài đặt hệ thống đa GPU GPU cluster để tiếp tục gia tăng hiệu tính tốn 71 Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự TÀI LIỆU THAM KHẢO [1] Yongchao Liu, Bertil Schmidt, Douglas L Maskell (2009), “MSA-CUDA: Multiple Sequence Alignment on Graphics Processing Units with CUDA”, In 20th IEEE International Conference on Application-specific Systems, Architectures and Processors, pp 121-128 [2] Julie D Thompson, Desmond G Higgins, Toby J Gibson (1994), “CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position specific gap penalties and weight matrix choice”, European Molecular Biology Laboratory, 22(22): pp T 2 T T 4673–4680 [3] Anand Lal Shimpi, Derek Wilson (2008), “NVIDIA's 1.4 Billion Transistor GPU: GT200 Arrives as the GeForce GTX 280 & 260”, URL: http://www.anandtech.com/show/2549/2 [4] “NVIDIA CUDA C Programming Guide Version 3.2” (2010), NVIDIA [5] Saitou N., Nei M (1987), “The neighbor-joining method: a new method for reconstructing phylogenetic trees”, Molecular Biology and Evolution, 4(4), pp 406-425 [6] Studier J.A., Keppler K.J (1988), “A note on the Neighbor-Joining algorithm T of Saitou and Nei”, Mol Biol Evol, (6): pp 729–731 [7] Tạ Minh Ngọc (2010), “Bắt cặp trình tự cục hệ thống GPU Cluster”, Under-graduate Thesis, Hanoi University of Science and Technology, Vietnam [8] Wikipedia (2011), “FASTA format”, URL: http://en.wikipedia.org/wiki/FASTA_format [9] Wikipedia (2011), “Sequence alignment”, URL: http://en.wikipedia.org/wiki/Sequence_alignment [10] Wikipedia (2011), Multiple sequence alignment”, URL: http://en.wikipedia.org/wiki/Multiple_sequence_alignment 72 Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự [11] Wikipedia (2011), “Bioinformatics”, URL: http://en.wikipedia.org/wiki/Bioinformatics [12] Wikipedia (2011), “Pairwise sequence alignment”, URL: http://en.wikipedia.org/wiki/Pairwise_sequence_alignment [13] Wikipedia , “Smith Waterman alignment”, URL: en.wikipedia.org/wiki/Smith–Waterman_algorithm 3T T [14] Notredame, Higgins, Heringa (2000), “T-Coffee: A novel method for multiple T sequence alignments” JMB, 302(205-217) [15] Chenna R, Sugawara H, Koike T, Lopez R, Gibson TJ, Higgins DG, T Thompson JD (2003), “Multiple sequence alignment with the Clustal series of programs”, Nucleic Acids Res, 31, pp 3497-3500 [16] http://gpgpu.org/ T [17] NVIDIA.http://www.nvidia.com/object/cuda_home_new.htm T [18] GraphStream (2009), Inc website URL: http://www.graphstream.com T [19] http://en.wikipedia.org/wiki/Needleman-Wunsch_algorithm T [20] Yongchao Liu, Douglas L Maskell, Bertil Schmidt (2009), “CUDASW++: T optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units”, BMC Research Notes, 2:73 [21] Szalkowski A, Ledergerber C, Krahenbuhl P and Dessimoz C (2008), T “SWPS3 – fast multi-threaded vectorized Smith-Waterman for IBM Cell/B.E and ×86/SSE2”, BMC Research Notes, 1:107 73 ... phương pháp song song hóa – phương pháp song song hóa theo dải cho giải thuật Clustal nhằm giải tốn 12 Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự bắt cặp đa trình tự thử... việc thêm chuỗi vào cách bắt cặp đa trình tự xây dựng Các phần mềm bắt cặp đa trình tự phổ 27 Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự biến sử dụng cách tiếp cận gồm... hồn tất bước giải thuật bắt cặp đa trình tự Clustal sử dụng luận văn 46 Áp dụng cơng nghệ tính tốn song song CUDA cho tốn bắt cặp đa trình tự 4.1.4 Bước 3: Bắt cặp đa trình tự Trong bước cuối, tiến