HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

Nguyễn Thành Phương

ĐỀ TÀI

GIẢI PHÁP TĂNG TỐC ĐỘ XỬ LÝ
THUẬT TOÁN SMITH-WATERMAN

LUẬN VĂN THẠC SĨ KỸ THUẬT

THÀNH PHỐ HỒ CHÍ MINH - 2016


HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

Nguyễn Thành Phương

ĐỀ TÀI

GIẢI PHÁP TĂNG TỐC ĐỘ XỬ LÝ
THUẬT TOÁN SMITH-WATERMAN

Chuyên ngành: Hệ thống Thông tin
Mã số: 60.48.01.04

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS. TRẦN VĂN LĂNG

THÀNH PHỐ HỒ CHÍ MINH – 2016

i

LỜI CAM ĐOAN
Trong quá trình thực hiện luận văn, dưới sự hướng dẫn trực tiếp của PGS.TS.
Trần Văn Lăng, tôi đã nghiên cứu và hoàn thành luận văn với sự nổ lực nghiên cứu
của bản thân. Do đó, tôi xin cam đoan rằ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 của PGS.TS. Trần Văn Lăng và mọi tham khảo được sử dụng
trong luận văn đều có trích dẫn nguồn cụ thể, rõ ràng, trung thực về tên tác giả, tên
công trình nghiên cứu, thời gian và địa điểm công bố.
Mọi sao chép không hợp lệ hoặc vi phạm quy chế đào tạo tôi xin chịu hoàn
toàn trách nhiệm./.
TP HCM, ngày 05 tháng 09 năm 2016
HỌC VIÊN THỰC HIỆN LUẬN VĂN

Nguyễn Thành Phương


ii

LỜI CẢM ƠN
Trong quá trình thực hiện luận văn này, tôi xin gửi lời cảm ơn chân thành đến
PGS.TS. Trần Văn Lăng, Viện phó Viện cơ học và Tin học ứng dụng TP HCM, là
người đã trực tiếp hướng dẫn tôi để hoàn thành luận văn này. Đồng thời, tôi cũng xin
gửi lời cảm ơn đến quý thầy cô thuộc Học Viện Bưu chính Viễn thông nói chung, tại
cơ sở Thành phố Hồ Chí Minh nói riêng đã tạo điều kiện thuận lợi cho tôi hoàn thành
luận văn đúng tiến độ.
Một lần nữa tôi xin gửi lời cảm ơn chân thành đến quý Thầy Cô.
TP HCM, ngày 05 tháng 09 năm 2016
HỌC VIÊN THỰC HIỆN LUẬN VĂN


Nguyễn Thành Phương


iii

MỤC LỤC
LỜI CAM ĐOAN ....................................................................................................... i
LỜI CẢM ƠN ............................................................................................................ ii
MỤC LỤC ................................................................................................................. iii
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ..............................................v
DANH SÁCH CÁC BẢNG ...................................................................................... vi
DANH SÁCH CÁC HÌNH ...................................................................................... vii
MỞ ĐẦU .....................................................................................................................1
CHƯƠNG 1- CƠ SỞ LÝ THUYẾT ...........................................................................4
1.1.

Tổng quan về GPU: ..........................................................................................4

1.1.1.

GPU là gì: ......................................................................................................4

1.1.2.

Lịch sử phát triển của GPU: ..........................................................................4

1.1.3.

Cấu trúc của GPU và cơ chế song song ứng dụng: .......................................5


1.2.

Tổng quan về OPENCL ....................................................................................6

1.2.1.

Giới thiệu về OPENCL:.................................................................................6

1.2.2.

Cấu trúc của OPENCL: .................................................................................7

1.2.3.

Quy trình phát triển một chương trình OPENCL: .......................................12

1.3.

Bài toán bắt cặp trình tự: .................................................................................12

1.4.

Các thuật toán giải quyết bài toán bắt cặp trình tự sinh học: ..........................13

TIỂU KẾT CHƯƠNG 1............................................................................................14
CHƯƠNG 2 - NGUYÊN LÝ ĐẨY NHANH THUẬT TOÁN SMITHWATERMAN TRONG MÔI TRƯỜNG CPU-GPU................................................15
2.1.

Thuật toán Smith-waterman nguyên thủy: ......................................................15


2.1.1.

Giới thiệu: ....................................................................................................15

2.1.2.

Nguyên lý hoạt động: ..................................................................................15

2.1.3.

Thuật toán và Đánh giá:...............................................................................21

2.2.

Phương pháp cải tiến thuật toán Smith-Waterman: ........................................22

2.2.1.

Phương pháp cắt tỉa: ....................................................................................24

2.2.2.

Ràng buộc dưới cho tất cả các cặp trong quá trình so sánh: .......................26


iv

2.2.3.


Tế bào kích hoạt ..........................................................................................28

2.2.4.

Lý thuyết song song thuật toán Smith- Waterman: .....................................28

2.3.

Thuật toán cải tiến ...........................................................................................31

2.3.1.

Thuật toán Smith-Waterman với phương pháp cắt tỉa: ...............................31

2.3.2.

Phương pháp kết hợp giữa cắt tỉa và xử lý song song .................................32

TIỂU KẾT CHƯƠNG 2............................................................................................34
CHƯƠNG 3- KẾT QUẢ THỰC NGHIỆM .............................................................35
3.1.

Chương trình thực nghiệm ..............................................................................35
Chương trình: ...............................................................................................35

3.1.1.
3.1.1.1.

Hàm quét tìm Platforms: ..........................................................................35


3.1.1.2.

Hàm quét tìm thiết bị: ..............................................................................36

3.1.1.3.

Hàm tính toán giới hạn thấp hơn: .............................................................36

3.1.1.4.

Kernel file của phương pháp cắt tỉa kết hợp song song: ..........................37

3.1.1.5.

Thực thi kernel: ........................................................................................39

3.1.2.
3.2.

Một số hình ảnh thực thi chương trình: .......................................................43
Môi trường thực nghiệm và dữ liệu test: ........................................................45

3.2.1.

Môi trường thực nghiệm: .............................................................................45

3.2.2.

Bộ dữ liệu Test: ...........................................................................................46


3.3.

Kết quả thực nghiệm: ......................................................................................48

3.3.1.

Kết quả thực nghiệm: ..................................................................................48

3.3.2.

So sánh thời gian thực thi giữa SW nguyên thủy và cắt tỉa trên CPU: .......49

3.3.3.

So với thuật toán Smith-Waterman xử lý song song: ..................................49

3.3.4. So sánh với thuật toán Smith-Waterman cắt tỉa và tối ưu hóa band của
nhóm nghiên cứu người Nhật:...................................................................................50
KẾT LUẬN: ..............................................................................................................51
DANH MỤC TÀI LIỆU THAM KHẢO ..................................................................52


v

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Viết tắt

Tiếng Anh

Tiếng Việt


CPU

Central Processing Unit

Bộ xử lý trung tâm

GPU

Graphics Processing Unit

Bộ xử lý đồ họa

VGA

Video Graphic Array

Card đồ họa

SM

Stream Multiprocessing

Dòng đa xử lý


vi

DANH SÁCH CÁC BẢNG
Hình 2.1: Mô hình tổng quát tính điểm số của ma trận


17

Hình 2.2: Ví dụ đoạn tương đồng của hai trình tự

23

Hình 2.3: Mô hình tổng quát biểu diễn trình tự tương đồng (Nguồn [5])

24

Hình 2.4: Biểu diễn bắt cặp trình tự của ba chuỗi Sa, Sb, Sc trên chuỗi Sa

26

Hình 2.5: Sự trùng khớp và không trùng khớp của ba trình tự (Nguồn [5])

27

Hình 2.7: Cách song song thuật toán SW trong giai đoạn điền ma trận

30

Bảng 3.1: Bảng đặc điểm kỹ thuật máy tính thực nghiệm

46

Bảng 3.2: Dữ liệu Test của chương trình

48



vii

DANH SÁCH CÁC HÌNH
Hình 1.1: Cấu trúc GPU (Graphics Pipeline) ..............................................................6
Hình 1.2: Mô hình nền tảng của OPENCL (Nguồn Khronos 2011) ...........................8
Hình 1.3: Hệ thống của OPENCL ...............................................................................8
Hình 1.4: Work-group và Work-item (Nguồn [10]) ...................................................9
Hình 1.5: Trình biên dịch của OPENCL ...................................................................10
Hình 1.6: Memory Model của OPENCL (Nguồn Khronos 2011) ............................11
Hình 2.1: Mô hình tổng quát tính điểm số của ma trận ............................................17
Hình 2.2: Ví dụ đoạn tương đồng của hai trình tự ....................................................23
Hình 2.3: Mô hình tổng quát biểu diễn trình tự tương đồng (Nguồn [5]).................24
Hình 2.4: Biểu diễn bắt cặp trình tự của ba chuỗi Sa, Sb, Sc trên chuỗi Sa ................26
Hình 2.5: Sự trùng khớp và không trùng khớp của ba trình tự (Nguồn [5]) .............27
Hình 2.6: Tính điểm số Hi,j (Nguồn [5]).................... Error! Bookmark not defined.
Hình 2.7: Cách song song thuật toán SW trong giai đoạn điền ma trận ...................30
Hình 3.1: Kết quả bắt cặp trình tự cặp (2) - (3) dùng SW nguyên thủy....................44
Hình 3.2: Kết quả bắt cặp trình tự cặp (2) - (3) dùng SW cắt tỉa trên CPU ..............44
Hình 3.3: Kết quả bắt cặp trình tự cặp (2) - (3) dùng SW cắt tỉa trên GPU..............45
Hình 3.4: Cấu trúc của file input cho giải thuật SW cắt tỉa ......................................46
Hình 3.5: Ví dụ file input cho thuật toán ..................................................................47
Hình 3.6: Kết quả thực nghiệm trên 4 môi trường ....................................................48
Hình 3.7: Thời gian thực thi của giải thuật SW nguyên thủy và cắt tỉa trên CPU ....49
Hình 3.8: Thời gian thực thi của giải thuật SW song song và SW song song, cắt tỉa
...................................................................................................................................50


1


MỞ ĐẦU
Công nghệ thông tin là một trong những ngành khoa học kỹ thuật có tính phổ
dụng rộng rãi, được áp dụng trong nhiều lĩnh vực khác nhau. Trong đó, không thể
không kể đến việc ứng dụng công nghệ thông tin trong công nghệ sinh học. Và chính
sự hội tụ của hai nền khoa học lớn này đã hình thành một ngành khoa học đã và đang
phát triển khá mạnh mẽ đó chính là ngành Tin sinh học (Bioinformatics). Từ khi Tin
sinh học ra đời, nó đã trở thành một công cụ hỗ trợ đắc lực trong việc nghiên cứu và
ứng dụng các sáng chế, phát minh của ngành công nghệ sinh học vào thực tiễn.
Trong những năm gần đây, các nhà khoa học trong lĩnh vực sinh học đã phát
hiện ra những cấu trúc sinh học phân tử mới và xây dựng thành một hệ thống cơ sở
dữ liệu sinh học phân tử khá lớn tập trung thành các ngân hàng dữ liệu (GenBank,
EMBL, DDBJ). Tháng 08 năm 2015, GenBank đã công bố có 199.823.644.287 bases,
từ 187.066.846 sequences trong hệ thống ngân hàng dữ liệu của đơn vị này.
Tuy nhiên, Với dữ liệu lớn thì việc tìm kiếm dữ liệu hoặc tìm kiếm sự tương
đồng trong database sẽ tốn rất nhiều chi phí về mặt thời gian, đặc biệt là bài toán bắt
cặp trình tự sinh học. Có nhiều thuật toán được xây dựng để giải quyết bài toán bắt
cặp trình tự sinh học, và mỗi thuật toán lại có tính ưu việt khác nhau về mặt thời gian
hoặc hiệu quả thực hiện. Thuật toán Smith-Waterman thường được áp dụng để giải
quyết bài toán bắt cặp trình tự sinh học vì thuật toán này cho kết quả có độ chính xác
cao, tuy nhiên giải thuật này lại mất khá nhiều thời gian thực hiện. Để nâng cao tính
hiệu quả của giải thuật Smith-Waterman và góp phần cải thiện thời gian thực hiện
của thuật toán này, luận văn sẽ tập trung vào việc đẩy mạnh thời gian thực hiện của
giải thuật dựa trên nền tảng các GPU. Luận văn được đề xuất với tên như sau: “Giải
pháp tăng tốc độ xử lý thuật toán Smith-Waterman”.
Trong những năm gần đây, các nhà khoa học trong lĩnh vực tin sinh học trên thế giới
đã nghiên cứu những phương pháp để cải tiến và tối ưu hóa thuật toán Smith-Waterman
trong quá trình bắt cặp trình tự sinh học.
Các nhà nghiên cứu thuộc Trường Đại học Bách khoa Hà Nội đã công bố công trình
nghiên cứu của mình với việc sử dụng hệ thống máy tính lớn tích hợp card đồ họa trong



2

việc bắt cặp đa trình tự bằng thuật toán Smith-Waterman, nhóm nghiên cứu đã cài đặt
thuật toán Smith-Waterman trên Cluster được trang bị card đồ họa NVIDIA GPU (hay
một cụm GPU) [3]. Trong quá trình thực hiện, tác giả đã thực nghiệm trên một hệ thống
cluster gồm hai nút, một nút được trang bị card đồ họa kép NVIDIA GeForce GTX 295,
mô ̣t card Tesla C1060, và nút còn lại được trang bị 2 card đồ họa kép NVIDIA
GeForce GTX 295. Kết quả của thực nghiệm cho thấy, hiệu suất đã tăng lên rất nhiều
so với các phương pháp trước đây như SWPS3 hoặc CUDASW. Từ kết quả thực nghiệm
của mình, nhóm nghiên cứu đã cho thấy vai trò và sức mạnh điện toán lớn của card đồ
họa trong quá trình xử lý một số vấn đề về tin sinh học, đặc biệt là trong bắt cặp trình tự.
Tháng 06 năm 2014, nhóm nghiên cứu gồm PGS.TS. Trần Văn Lăng và Chung
Khánh Duy đã ứng dụng công nghệ OPENCL vào việc song song hóa thuật toán SmithWaterman bằng cách tính toán cùng lúc ma trận con hình vuông với kích thước k theo
hướng đường chéo, đồng thời xác định hàm số biến thiên theo k dựa trên kết quả thực
nghiệm đạt được. Mặt khác, nhóm nghiên cứu cũng đã xác định được giá trị k phù hợp
nhất để thời gian thực hiện song song hóa thuật toán Smith-Waterman là tối ưu nhất.
Nhóm tác giả đã ứng dụng thành công khả năng tương thích với nhiều loại thiết bị khác
nhau của OPENCL vào nghiên cứu của mình. Trong quá trình nghiên cứu, nhóm tác giả
đã sử dụng phần cứng của Intel để minh họa OPENCL thay vì được minh họa trên nền
tảng NVIDIA, và đây là vấn đề mà CUDA chưa thể làm được, đó là thực thi trên đa nền
tảng. Kết quả thực nghiệm cho thấy rằng: thời gian thực thi của việc song song thuật
toán Smith-Waterman bằng OPENCL đã được cải thiện gấp 3 lần so với giải thuật tính
toán tuần tự của thuật toán Smith-Waterman nguyên thủy [2]. Tuy nhiên trong quá trình
thực nghiệm, nhóm nghiên cứu chỉ áp dụng trên nền tảng OPENCL 1.1 đã được xây
dựng vào năm 2010, mà chưa áp dụng trên nền tảng mới hơn là OPENCL 2.0 được phát
triển vào năm 2012 (năm 2015 đã có phiên bản 2.1). Mặt khác, do điều kiện nên nhóm
nghiên cứu chỉ thực nghiệm trên Intel core I5 nên tốc độ cải thiện thuật toán SmithWaterman so với thuật toán nguyên thủy là chưa cao.
Ngoài ra, trong những tháng đầu năm 2015, nhóm nghiên cứu người Nhật gồm Daiki

Okada, Fumihiko Ino và Kenichi Hagihara đã tìm ra phương pháp nhằm tối ưu hóa thuật


3

toán Smith-Waterman bằng cách loại bỏ những cặp interpair trong quá trình bắt cặp trình
tự. Nhóm nghiên cứu đã tích hợp việc cắt tỉa các cặp interpair và kết hợp thuật toán MyerMillers để cắt tỉa các tế bào trên hai ma trận của GPU, trên nền tảng CUDA. Trong quá
trình thực nghiệm, nhóm nghiên cứu cũng đã kế thừa những phương pháp của các nhà
nghiên cứu trước đó và cũng đưa ra một phương pháp mới nhằm cải thiện quá trình so
sánh tất cả các cặp trong bài toán bắt cặp trình tự. Mặt khác, nhóm tác giả cũng nhận thấy
những ưu điểm và khuyết điểm mà các tác giả trước đã đưa ra, và nhóm đưa ra một
phương pháp riêng cho mình. Việc cắt tỉa và tối ưu này có thể thực hiện trên tất cả các
cặp trong quá trình so sánh bắt cặp trình tự của cùng một loài. Và phương pháp của nhóm
nghiên cứu đã làm cho thuật toán Smith-Waterman được tối ưu ở giai đoạn đầu của thuật
toán. Tuy nhiên, quá trình cắt tỉa này sẽ không hiệu quả đối với việc bắt cặp trình tự khác
loài [5].


4

CHƯƠNG 1- CƠ SỞ LÝ THUYẾT
1.1. Tổng quan về GPU:
Trong kiến trúc của máy tính, bộ vi xử lý trung tâm (CPU) là một bộ phận quan
trọng để vận hành máy tính, là khối điều khiển, xử lý các chương trình và dữ kiện.
Tuy nhiên đối với những ứng dụng đòi hỏi tốc độ xử lý cao thì CPU có thể không thể
đáp ứng, đặc biệt là trong lĩnh vực đồ họa, game 3D. Vì vậy, để tăng tốc độ xử lý và
thực thi chương trình, người ta bổ sung GPU vào hệ thống máy tính, vậy GPU là gì
và phương thức tăng tốc độ xử lý của nó trong hệ thống máy tính như thế nào, những
điều này sẽ được trình bày cụ thể dưới đây.


1.1.1. GPU là gì:
GPU (Graphics Processing Unit) là bộ vi xử lý chuyên dụng có nhiệm vụ tăng tốc,
xử lý đồ họa cho bộ vi xử lý trung tâm CPU nhằm tăng tốc các ứng dụng đồ họa, ứng
dụng khoa học, kỹ thuật và phân tích dữ liệu lớn. GPU có thể đẩy nhanh tốc độ xử lý
ở nhiều môi trường khác nhau: máy tính (máy tính cá nhân, máy trạm, máy chơi game
chuyên dụng), điện thoại di động, máy tính bảng, robot, …
Với mục đích nhằm tăng tốc độ xử lý cho CPU nên GPU được ứng dụng trong
nhiều lĩnh vực khác nhau. Tuy nhiên, trong lĩnh vực đồ họa, đặc biệt là đồ họa 3D thì
GPU được ứng dụng rộng rãi, vì GPU là một bộ vi xử lý chuyên biệt được xây dựng
nhằm thực hiện các phép toán đặc biệt cần thiết cho các ứng dụng đồ họa 3D. Ngoài
ra, GPU còn được sử dụng trong việc tăng tốc các video theo chuẩn Adobe Flash,
chuyển đổi giữa các định dạng video, ví dụ từ .AVI sang .MP4, nhận diện hình ảnh
và hỗ trợ nhận diện virus.

1.1.2.

Lịch sử phát triển của GPU:

Nửa cuối thập niên 1970, hàng loạt các thiết bị đồ họa ra đời làm tiền đề cho
ngành công nghiệp đồ họa 3D sau này. Điển hình là Chip video “Pixie” CDP1861 của
RCA dùng để cung cấp đầu ra cho tín hiệu video tương thích NTSC có độ phân giải
62x128 hoặc 64x32 trên các thiết bị Consol RCA Studio II. [2, trang 7].
Và trong khoảng 17 năm gần đây, GPU đã phát triển rất mạnh mẽ với nhiều cải


5

tiến, bổ sung, đặc biệt là những linh kiện phần cứng nhằm tăng tốc độ xử lý của trình
điều khiển VGA (Video Graphic Array). Khi GPU mới xuất hiện thì chưa có khả năng
lập trình mở rộng, sau thời gian phát triển và cải tiến thì việc lập trình mở rộng trở

nên khá dễ dàng.
GPU đã vượt qua CPU về khả năng tính toán số học và băng thông bộ nhớ, chúng
trở nên khá lý tưởng để đẩy nhanh tốc độ xử lý dữ liệu song song cho nhiều ứng dụng
khác nhau.
Không chỉ tập trung vào việc phát triển những dòng sản phẩm chuyên xử lý các
ứng dụng đồ họa, các nhà nghiên cứu đã khai thác hiệu quả xử lý của GPU ở nhiều
lĩnh vực khác như y khoa, điện tử, … Từ đó, GPU được sử dụng để thực thi các ứng
dụng điện toán đa dụng, từ đó hình thành GPGPU (điện toán đa dụng). Mặc dù,
GPGPU đã thể hiện tính ưu việt của mình trong quá trình xử lý dữ liệu nhưng nó cũng
gặp phải nhiều vấn đề lớn như: trình độ của người lập trình viên, thuật ngữ của chương
trình (xác định tọa độ đỉnh, kết cấu và đổ bóng), truy cập bộ nhớ ngẫu nhiên chưa
được hỗ trợ, tính chính xác kép chưa được hỗ trợ nên có một số ứng dụng không thể
thực thi trên môi trường GPU.

1.1.3. Cấu trúc của GPU và cơ chế song song ứng dụng:
Những GPU phổ biến ngày nay được cấu trúc theo một kiểu được gọi là ống
đồ họa (graphics pipeline - GPs). Một ống đồ họa bao gồm nhiều giai đoạn, mỗi giai
đoạn được xử lý trên GPU bởi những bộ xử lý song song. Mỗi GPUs bao gồm nhiều
streaming multiprocessors (SMs) và mỗi SM thường từ 8 – 32 SIMT (Single
instruction, multiple thread). Ví dụ: Fermi series của Nvidia có 16 SM có chiều rộng
là 32 SIMT. Chính nhờ vào các yếu tố này mà ngoài chức năng xử lý đồ họa, GPU
được ứng dụng rộng rãi trong quá trình tính toán song song dữ liệu.
Việc tính toán trong GPU có nhiều mô hình xử lý khác nhau: mô hình xử lý
đa luồng thread, mô hình truyền thông điệp và mô hình xử lý song song. Mỗi mô hình
có một chức năng và đặc điểm riêng, nhưng tất cả các mô hình nhằm tăng khả năng
tính toán dữ liệu của GPU.


6


Hình 1.1: Cấu trúc GPU (Graphics Pipeline)

- Mô hình đa luồng xử lý là mô hình lập trình dưới dạng chia sẻ bộ nhớ, trong
cùng một tiến trình có thể có nhiều luồng xử lý được xử lý song song cùng lúc. Các
luồng có thể chia sẻ dữ liệu cho nhau trong quá trình tính toán, do đó có thể giảm
thiểu tài nguyên bộ nhớ được sử dụng.
- Mô hình truyền thông điệp: có ứng dụng rộng rãi trong hệ thống phân tán. Mô
hình này có một số đặc điểm như sau: Tất cả các task đều sử dụng chung một vùng
nhớ cục bộ trong suốt quá trình tính toán. Tuy nhiên, các task có thể nằm trên nhiều
máy khác nhau, không chỉ riêng ở một máy. Vì vậy, các task trao đổi dữ liệu với nhau
bằng các thông điệp, điều này đòi hỏi sự hợp tác và tương thích giữa vác tiến trình
trong quá trình gửi và nhận.
- Mô hình song song dữ liệu: việc tính toán sẽ được chia nhỏ từ các mẫu dữ liệu
lớn, việc trao đổi dữ liệu với nhau thông qua một địa chỉ không gian bộ nhớ toàn cục.
Tập hợp các task có liên quan đều xử lý mẫu dữ liệu có cùng cấu trúc, tuy nhiên mỗi
task sẽ làm việc trên mỗi vùng dữ liệu khác nhau.

1.2.

Tổng quan về OPENCL

1.2.1. Giới thiệu về OPENCL:
OpenCL (Open Computing Language) là một chuẩn lập trình mã nguồn mở miễn
phí sử dụng ngôn ngữ OPENCL-C dựa trên những tiêu chuẩn của C99 và IEEE-754
(chuẩn dấu chấm động cho số học), do đó, cấu trúc lệnh của OPENCL hoàn toàn
giống với ngôn ngữ lập trình C.
OPENCL được đề xuất và phát triển bởi Apple, sau đó được các hãng khác phát
triển thêm dưới sự hợp tác của Apple và AMD, Intel, IBM và NVIDIA. Nhưng sau



7

đó, Apple đã sang nhượng lại cho Khrosnos Group, là tổ chức đang nắm giữ các chuẩn
khác như OPENGL, OPENAL, …Phiên bản OPENCL 1.0 đã được phát hành chính
thức vào ngày 18/12/2008. Và sau đó, các hãng NVIDIA, AMD đã phát triển và công
bố những công cụ hỗ trợ để phát triển chương trình trên nền tảng OPENCL; và tháng
11/2015 đã ra mắt phiên bản 2.1.
Phiên bản 2.1 là phiên bản đầu tiên có hạt nhân dựa trên nền tảng ngôn ngữ C++.
Do mới được phát triển về sau này, nên trong phiên bản 2.1 được thừa hưởng những
ưu điểm và khắc phục tương đối những hạn chế, nhược điểm của ngôn ngữ C và C++.
Trong phiên bản 2.1, thư viện của OPENCL C là một thư viện con được chứa trong
thư viện của OPENCL C++, vì mục tiêu phát triển của phiên bản này đó chính là tạo
điều kiện thuận lợi nhất cho tất cả các lập trình viên khi tham gia phát triển các ứng
dụng sử dụng ngôn ngữ OPENCL.
OPENCL đã được phát triển theo xu hướng cross-platform, độc lập với hạ tầng
phần cứng và tận dụng được tối đa các thiết bị này trong quá trình tính toán song song
trên các thiết bị, kể cả trên GPU. Ngoài ra, OPENCL không chỉ hỗ trợ lập trình song
song xử lý các tác vụ (task-parallel programming) mà còn hỗ trợ lập trình song song
dữ liệu (data-parallel programming). Bên cạnh đó, OPENCL có thể được thực thi trên
nhiều hệ điều hành khác nhau từ IOS, Linux cho đến Windows.

1.2.2. Cấu trúc của OPENCL:
Sự vận hành của OpenCL được mô tả bởi cụm các model có mối liên hệ với
nhau, bao gồm Platform Model (mô hình nền tảng), Execution Model (mô hình thực
thi), Memory Model (mô hình bộ nhớ), và Programming Model (mô hình lập trình).
a) Platform Model:
Mô hình nền tảng OPENCL được định nghĩa là một máy chủ (host) kết nối với
một hoặc nhiều thiết bị OPENCL. Mô hình nền tảng bao gồm một máy chủ (host
device) –điều khiển chương trình hoạt động – và các đơn vị tính toán, đơn vị xử lý.



8

Hình 1.2: Mô hình nền tảng của OPENCL (Nguồn Khronos 2011)

Một máy chủ là một máy tính bất kỳ với CPU và một hệ điều hành chuẩn
(Windows, Linux, IOS, …). Thiết bị OPENCL có thể là một GPU hoặc CPU đa lõi,
một thiết bị OPENCL bao gồm một hay nhiều đơn vị tính toán. Khi chương trình thực
thi, máy chủ sẽ tạo ra một môi trường ảo (context) và cung cấp các thiết bị tính toán
(compute device) cùng với khoảng vùng nhớ nhất định mà chương trình sẽ sử dụng.
Bên cạnh đó một “hàng đợi lệnh thực thi” (command queue) cũng sẽ được tạo ra để
chương trình có thể điều phối các lệnh trong kernel và thực hiện các thao tác truy xuất
tới bộ nhớ. Tốc độ truy xuất giữa các device sẽ chậm hơn rất nhiều so với tốc độ giao
tiếp nội bộ của các thành phần trong device đó và bản thân host device.

Hình 1.3: Hệ thống của OPENCL

b) Execution Model:
Mô hình thực thi bao gồm hai thành phần chính: kernel và host program.


9

Kernel: là một đơn vị cơ bản của tập các lệnh được viết ra để thực thi trên một hay
nhiều thiết bị OpenCL device. Việc tính toán song song trên các thiết bị tính toán
trong OPENCL được xác định bằng cách định nghĩa việc tính toán trong một không
gian chỉ mục N chiều (index space). Khi một kernel được xếp trong hàng đợi để chờ
thực thi bởi host program thì một không gian chỉ mục được định nghĩa. Mỗi phần tử
thực thi độc lập trong không gian chỉ mục được gọi là đơn vị xử lý (work-item), các
đơn vị xử lý thực thi trên một cùng một kernel nhưng trên vùng dữ liệu khác nhau.

Để lưu trữ tất cả các đơn vị xử lý thì một không gian chỉ mục cần phải được định
nghĩa khi một kernel command được đặt vào command queue.

Hình 1.4: Work-group và Work-item (Nguồn [10])

Khi thực thi các kernel sẽ được biên dịch thành các kernel object, program
object cũng được biên dịch từ các program. Khi chương trình được thực thi trên một
thiết bị nào đó thì sẽ tính toán được số lượng đơn vị xử lý tương ứng trong một không
gian chỉ mục nhất định. Không gian chỉ mục trong OPENCL hỗ trợ tối đa 3 chiều,
khi N=1 xử lý các dữ liệu một chiều, N=2 thường xử lý ảnh và N=3 thường được sử
dụng để xử lý các ảnh 3D.
OPENCL có cơ chế đồng bộ tính toán giữa các work-item trong work-group
nhưng không hỗ trợ giữa các work-group với nhau. Và mỗi work-item có một mã
định danh duy nhất (global ID) để xác định trong không gian chỉ mục. Tương tự, mỗi
workgroup cũng sẽ có một định danh duy nhất work-group ID, để xác định vị trí của


10

work-group trong index space. OPENCL cũng cho phép định vị trí của một workitem trong work-group thông qua local ID.

Hình 1.5: Trình biên dịch của OPENCL

Host program: Các host program chịu trách nhiệm cho việc thiết lập và quản lý
việc thực hiện của các kernel trên các thiết bị của OPENCL thông qua các context.
Thông qua việc sử dụng các OPENCL API, máy chủ có thể tạo và tương tác với các
context thông qua các thiết bị được thêm vào: Device, Program object, Kernel và
Memory Object. Sau khi context được tạo, thì hàng đợi lệnh cũng được tạo để quản
lý việc thực hiện của các kernel trên các OPENCL Device gắn với các context.
Command queue có 3 loại: Kernel Execute command (Chỉ thị thực thi Kernel),

Memory command (chỉ thị bộ nhớ), Synchronization command (Chỉ thị đồng bộ).
c) Memory Model:
Mô hình bộ nhớ trong OPENCL được phân chia thành 4 vùng nhớ chính:
Private memory, Local memory, Global/ Constant memory và Host memory. Mỗi
vùng nhớ có một chức năng và nhiệm vụ khác nhau, cụ thể như sau:
- Private memory là vùng nhớ được truy xuất bởi các work-item.
- Local memory là vùng nhớ dùng để chia sẻ dữ liệu giữa các work-items trong
cùng một work-group. Các work-item có quyền đọc và ghi dữ liệu trong local
memory.
- Constant memory là vùng nhớ toàn cục, không thay đổi trong suốt quá trình
làm việc của các kernel và là một vùng trên global memory. Các work-item thì chỉ có
thể truy xuất vào vùng nhớ này, riêng máy host thì có thể đọc và ghi dữ liệu trong


11

vùng nhớ này. Giá trị trên constant memory được cung cấp bởi host application.
- Global memory là vùng bộ nhớ mà tất cả các work-item hoặc work-group có
thể truy xuất đọc và ghi. Vùng bộ nhớ này được cấp phát duy nhất trong suốt quá
trình chương trình host đang chạy và được mô tả bởi platform model.

Hình 1.6: Memory Model của OPENCL (Nguồn Khronos 2011)

Việc sử dụng bộ nhớ hiệu quả và tốc độ phụ thuộc rất nhiều vào cách dùng bốn
loại bộ nhớ trên. Trong đó private memory và local memory cho tốc độ cao nhất, vùng
nhớ cho tốc độ truy xuất chậm chính là global memory.
d) Programming Model:
OPENCL hỗ trợ hai mô hình lập trình song song: song song dữ liệu (dataparallel) và song song tác vụ (task-parallel). Các tiến trình song song dữ liệu thực thi
nhiều instance có cùng kernel một cách đồng thời, mỗi instance xử lý một tập dữ liệu
riêng biệt. Mỗi tập dữ liệu liên kết với một điểm trong không gian chỉ mục một, hai

hay ba chiều. Song song tác vụ lại tương tự như những tiến trình thực thi đa luồng có
tính chất độc lập nhau, mỗi process thực hiện những nhiệm vụ khác nhau. Trong
OpenCL, lập trình song song tác vụ bao gồm việc lập hàng đợi nhiều kernel, và để
OpenCL thực hiện chúng một cách song song sử dụng các thiết bị tính toán có thể có.


12

1.2.3. Quy trình phát triển một chương trình OPENCL:
Để viết một chương trình OPENCL cần phải trãi qua các bước sau:
-

Xác định nhiệm vụ cần thực hiện song song: Việc xác định các nhiệm vụ cần

thực hiện song song sẽ giúp cho chương trình có thể chạy với hiệu suất cao nhất, đồng
thời sẽ giúp người lập trình có thể lập ra cấu trúc bộ nhớ và tính toán được chi phí của
chương trình.
-

Viết các kernel và các hàm bổ trợ: Để thực hiện tính toán song song trên

OpenCL device, bắt buộc phải viết các kernel. Các kernel được đóng gói và biên dịch
khi chương trình thực thi.
-

Setup context: Sử dụng các hàm có trong OpenCL framework để tìm và quyết

định thiết bị nào sẽ dùng trong chương trình. Sau đó khởi tạo môi trường ảo bao gồm
memory object và command queue.
-


Viết mã lệnh để biên dịch và build chương trình OpenCL: Sau khi đã xác định

được OpenCL device và setup context, chúng ta sẽ viết mã lệnh cho host application
để biên dịch mã nguồn chương trình và sử dụng các kernel object từ mã nguồn đã
biên dịch. Các lệnh sau được thực hiện liên tục theo thứ tự.
-

Khởi tạo các đối tượng memory object: Để giữ các dữ liệu nhập xuất và trả về

giá trị cho các đối số đầu vào (input object), memory object tham gia vào nhiệm vụ
thao tác vùng nhớ giữa host device và OpenCL device.
-

Lập hàng đợi lệnh có thứ tự (enqueue command) để điều khiển việc thực thi

liên tục và đồng bộ các kernel, đọc và ghi dữ liệu và thao tác trên các memory object.
-

Đọc giá trị trả về: Enqueue command để đọc giá trị xuất từ work-item và đưa

nó vào host memory.

1.3.

Bài toán bắt cặp trình tự:
Bắt cặp trình tự hay so sánh trình tự nhằm tìm đến sự tương đồng giữa các

trình tự bằng cách đo lường sự giống nhau của các chuỗi trình tự. Các chuỗi trình tự
ở đây chính là các chuỗi trình tự ADN, RNA hoặc các trình tự amino acid (protein).

Và việc bắt cặp trình tự được thực hiện bằng cách thêm “gap” vào những vị trí sao
cho các cột tương đồng nhau.


13

Ví dụ: cho trình tự a: AGTGACT, trình tự b: ATGCT, kết quả của quá trình bắt cặp
trình tự là:
AGTGACT
|

||

||

A– TG– CT
Để đánh giá được mức độ tương đồng của các trình tự, áp dụng công thức sau:
𝒏𝒂 𝒙 𝒎𝒂𝒕𝒄𝒉 + 𝒏𝒊 𝒙 𝒎𝒊𝒔𝒎𝒂𝒕𝒄𝒉 + 𝒏𝒈 𝒙 𝒈𝒂𝒑

(1.1)

Trong đó: na, ni, ng lần lượt là số các phần tử giống nhau, không giống nhau và số các
gap được thêm vào; match, mismatch và gap lần lượt là các chỉ số tính toán để tìm ra
mức độ tương đồng (match >0).
Ví dụ: Cho trình tự a: AGTGACT, trình tự b: ATGCT, match= 2, mismatch = -1 và
gap = -2. Với kết quả của trình tự:

AGTGACT
|


||

||

A– TG– CT
Theo công thức (1.1) ta có: na = 5, ni=2, ng=2  5 * (2) + 2 *(-1) + 2 *(-2) = 4
Vậy mức độ tương đồng của hai trình tự là 4 điểm.

1.4.

Các thuật toán giải quyết bài toán bắt cặp trình tự sinh học:
Có nhiều thuật toán được xây dựng đẻ giải quyết bài toán bắt cặp trình tự:

thuật toán Needleman-Wunsch, Smith-Waterman, Blast, …. Thuật toán NeedlemanWunsch và Smith-Waterman đều dựa trên cơ chế quy hoạch động, tuy nhiên mỗi giải
thuật lại có một phương pháp xử lý và tìm kiếm khác nhau.
Đối với thuật toán Needleman-Wunsch áp dụng cho bài toán bắt cặp trình tự
toàn bộ, tính toán điểm tương đồng của toàn bộ chuỗi trình tự. Thuật toán SmithWaterman thì chỉ tính toán một đoạn tương đồng trong chuỗi trình tự có điểm số
tương đồng tối ưu nhất. Vì vậy thuật toán này chỉ áp dụng để giải quyết bài toán bắt
cặp trình tự cục bộ. Giải thuật Smith-Waterman có nhiều ưu điểm vượt trội, song vẫn
tồn tại những hạn chế khá lớn của giải thuật này đó chính là tốc độ xử lý thuật toán


14

khá chậm, tốn nhiều thời gian để xử lý, đặc biệt là các chuỗi trình tự có độ dài của
trình tự khá lớn (ví dụ vi khuẩn bacillus có độ dài trình tự lên đến 5 triệu). Vì thế,
luận văn này nghiên cứu phương pháp cải tiến tốc độ xử lý thuật toán trên môi trường
CPU và GPU, phương pháp này sẽ được trình bày cụ thể trong chương hai.
TIỂU KẾT CHƯƠNG 1
Trong chương này giói thiệu một cách tổng quát nhất những nội dung cơ bản

về GPU: tổng quan về GPU, cấu trúc, vai trò của nó trong hệ thống máy tính, đặc biệt
là trong quá trình tính toán song song. Đồng thời, chương này cũng đã trình bày một
cách cơ bản về tổng quan ngôn ngữ lập trình OPENCL từ quá trình phát triển cho đến
các thành phần hay cấu trúc của OPENCL. Mặt khác, qua chương này cũng hiểu được
quy trình viết một chương trình trên nền tảng OPENCL.
Mặt khác, trong chương một cũng đã giới thiệu tổng quát về bài toán bắt cặp
trình tự là gì, làm thế nào biết độ tương đồng của các trình tự. Các phương pháp để
giải quyết bài toán bắt cặp trình tự (toàn cục và cục bộ). Ngoài ra, chương một cũng
đã đánh giá sơ bộ tốc độ của từng giải thuật trong quá trình giải quyết bài toán bắt
cặp trình tự.


15

CHƯƠNG 2 - NGUYÊN LÝ ĐẨY NHANH THUẬT TOÁN
SMITH-WATERMAN TRONG MÔI TRƯỜNG CPU-GPU
2.1.

Thuật toán Smith-waterman nguyên thủy:

2.1.1. Giới thiệu:
Thuật toán Smith-Waterman là giải thuật giải quyết bài toán bắt cặp trình tự
cục bộ, nhằm tìm ra những đoạn có điểm tương đồng về cấu trúc hoặc chức năng giữa
các trình tự sinh học, nucleotide hoặc các chuỗi protein.
Thuật toán này được F. Smith và Michael S. Waterman đề xuất vào năm 1981.

2.1.2. Nguyên lý hoạt động:
Thuật toán Smith-Waterman là thuật toán sử dụng phương pháp quy hoạch động
để định lượng các điểm số cho quá trình bắt cặp trình tự. Giai đoạn backtracking được
bắt đầu từ ô có điểm số cao nhất và điểm số tương đồng thu được cho đến khi bắt gặp

ô có giá trị bằng 0, vì vậy điểm số tương đồng thu được là cao nhất. Bằng cách tìm
kiếm những điểm cao nhất trong ma trận, thì việc bắt cặp trình tự sẽ cho một kết quả
tối ưu nhất.
Do áp dụng phương pháp quy hoạch động nên trong quá trình tính toán, giải
thuật sử dụng ma trận để ghi nhận điểm số và áp dụng công thức sau:
Hi0=0 với ∀𝑖 = 0, 𝑛, H0j=0 với ∀𝑗 = 0, 𝑚

(2.1)

Hij=max(0, 𝐻𝑖−1,𝑗−1 + 𝜎𝑖𝑗 , 𝐻𝑖−1,𝑗 + 𝑑, 𝐻𝑖,𝑗−1 + 𝑑) , ∀𝑖 = 0, 𝑛, ∀𝑗 = 0, 𝑚 (2.2)
𝜎𝑖𝑗 = {

𝑚𝑎𝑡𝑐ℎ
và d=gap
𝑚𝑖𝑠𝑚𝑎𝑡𝑐ℎ

Trong đó:
-

n là độ dài của trình tự Sa,

-

m là độ dài trình tự Sb,

-

Hij là ma trận điểm số

-


d là giá trị của gap

-

match và mismatch lần lượt là điểm số trùng khớp và không trùng khớp của Sai
và Sbj, giả sử rằng điểm số match luôn dương (match ≥ 0).


16

Để giải quyết bài toán bắt cặp trình tự cục bộ, giải thuật trãi qua các bước sau:
Bước 1: Khởi tạo ma trận, áp dụng công thức (2.1).
Bước 2: Tính toán điểm số và điền ma trận, áp dụng công thức (2.2).
Bước 3: Tìm điểm số max trong ma trận Hi,j
Bước 4: Tìm dấu vết dựa trên ma trận vừa tính ở trên.
Bước 5: Kết quả bắt cặp trình tự
Để minh họa cho các bước của giải thuật, tìm hiểu ví dụ sau (ví dụ 1): cho trình
tự A: CGTGAATTCAT, trình tự B: GACTTAC, cho các giá trị match = 2,
mismatch=-1, gap = -1; n, m: lần lượt là độ dài của chuỗi trình tự A, B.
Bước 1: Khởi tạo ma trận n x m +1, áp dụng công thức (2.1):
Hi0=0 với ∀𝑖 = 0, 𝑛, H0j=0 với ∀𝑗 = 0, 𝑚

(2.1)

Ta giả định rằng n là số dòng và m là số cột của ma trận cần điền. Ma trận sẽ
được biểu diễn và các giá trị ở dòng đầu tiên, cột đầu tiên được thiết lặp như hình sau:
Bảng 2.1: Khởi tạo ma trận

0

C

0

G

0

T

0

G

0

A

0

A

0

T

0

T


0

C

0

A

0

T

0

G

A

C

T

T

A

C

0


0

0

0

0

0

0

Bước 2: Tính toán điểm số và điền ma trận, áp dụng công thức (2.2):
Hij=max(0, 𝐻𝑖−1,𝑗−1 + 𝜎𝑖𝑗 , 𝐻𝑖−1,𝑗 + 𝑑, 𝐻𝑖,𝑗−1 + 𝑑) , ∀𝑖 = 0, 𝑛, ∀𝑗 = 0, 𝑚

(2.2)