Chương 1: Giới thiệu về Đề tài CHƯƠNG 3: CƠ SỞ LÝ THUYẾT Chương này trình bày chi tiết về các cơ sở lý thuyết được áp dụng trong đề tài như: độ đo xoắn thời gian động, các phương pháp xác định các điểm cực trị quan trọng giúp cho quá trình phân đoạn chuỗi thời gian. Ngoài ra, chương này còn trình bày về công nghệ GPU, kiến trúc cũng như mô hình lập trình song song dựa vào GPU và các phương pháp tiếp cần để tăng tốc xử lý khi tính toán độ đo xoắn thời gian động. CHƯƠNG 4 : PHƯƠNG PHÁP ĐỀ NGHỊ Chương này giới thiệu chi tiết hướng tiếp cận trong việc giải bài toán kết chuỗi con theo hướng tiếp cận bằng phần cứng thuần túy và giải pháp kết hợp giữa phần mềm và phần cứng GPU. Chương này cũng giới thiệu tổng quan về mô hình, kiến trúc và các thành phần quan trọng của ứng dụng kết chuỗi con dựa vào GPU.
CHƯƠNG 5: THỰC NGHIỆM Chương này trình bày kết quả của một số loại thực nghiệm như: thực nghiệm về tính chính xác của phương pháp đề xuất cho kết quả bài toán kết chuỗi con, thực nghiệm so sánh hai giải thuật kết chuỗi con tuần tự và song song. Bên cạnh đó, một số đánh giá, kết luận và đề xuất cũng sẽ được nêu lên dựa trên các kết quả thực nghiệm có được. CHƯƠNG 6: TỔNG KẾT Chương này trình bày tổng lược lại toàn bộ nội dung quan trọng của luận văn, các đóng góp chính của đề tài, và hướng phát triển. PHẦN TÀI LIỆU THAM KHẢO 7 Chương 2: Các Công trình nghiên cứu liên quan CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN Chương này giới thiệu sơ lược một số nghiên cứu liên quan như: độ đo tương tự, và các công trình liên quan đến kết chuỗi con.
Phần đầu chương nêu lên định nghĩa dạng tổng quát và một số thể hiện cụ thể của không gian độ đo như là độ đo Minkowski, độ đo xoắn thời gian động. Phần kế đến trình bày tổng lược các công trình liên quan như ý tưởng phân đoạn chuỗi thời gian nhờ các điểm cực trị quan trọng, giải thuật kết chuỗi con trực tiếp. Phần tiếp theo trình bày về các hướng tiếp cận giải quyết bài toán kết chuỗi con dựa trên GPU hiện nay. Phần cuối chương sẽ giới thiệu phương pháp mà luận văn đề nghị để giải quyết bài toán kết chuỗi con trên dữ liệu chuỗi thời gian.
CÁC CÔNG TRÌNH LIÊN QUAN ĐẾN ĐỘ ĐO KHOẢNG CÁCH Về độ đo khoảng cách, trước đây hầu hết các công trình đều sử dụng độ đo Minkowski, hay cụ thể là Euclid. Cách tính khoảng cách này khá đơn giản và dễ dàng, phù hợp cho những biến đổi DFT, DWT, …. Tuy nhiên, kết quả của phép đo ảnh hưởng nhiều bởi nhiễu và không hiệu quả với những dữ liệu được đo ở nhiều thang do khác nhau. Hiện nay, đã có nhiều công trình sử dụng DTW kể từ khi nó được ứng dụng vào bài toán nhận dạng giọng nói [12], hai tác giả Berndt và Clifford đã lần đầu áp dụng độ do này cho bài toán liên quan đến chuỗi thời gian [3].
Sau đó, cũng đã có nhiều công trình ([5], [6], [9], [13], [14]) sử dụng độ đo này. Độ đo xoắn thời gian động DTW có cách tính khoảng cách Minkowski nhưng thay vì so trùng hai đường biểu diễn dữ liệu bằng cách tính khoảng cách từng cặp điểm 1 − 1 (điểm thứ 𝑖 của chuỗi thứ nhất so với điểm thứ 𝑖 của chuỗi thứ hai) thì một điểm có thể ánh xạ với nhiều điểm và ánh xạ này không tuyến tính. Cách tính khoảng cách xoắn thời gian động sẽ được trình bày chi tiết trong phần 3. Ưu điểm của phương pháp này là cho phép nhận dạng những mẫu có hình dạng giống nhau nhưng chiều dài hình dạng về mặt thời gian có thể khác nhau và hiệu quả hơn rất nhiều so với phương pháp tính khoảng cách theo Euclid, đặc biệt trong bài toán phân lớp, gom cụm hay trong các ứng dụng nhận dạng giọng nói.
Tuy nhiên, nhược điểm của phương pháp này là độ phức tạp tính toán lớn cả về thời gian lẫn không gian bộ nhớ. 8 Chương 2: Các Công trình nghiên cứu liên quan Để khắc phục các nhược điểm này, các tác giả đã đưa nhiều phương pháp phần mềm nhằm tăng tốc quá trình tính toán cho DTW. Có thể kể đến như ràng buộc dải của Sakoe và Chiba [12], ràng buộc hình bình hành của Itakura [15] hay bộ kỹ thuật UCR - DTW của Rakthanmanon và nhóm cộng sự [16]. CÁC CÔNG TRÌNH LIÊN QUAN ĐẾN BÀI TOÁN KẾT CHUỖI CON Để thực hiện kết chuỗi con, trước hết cần phân đoạn chuỗi thời gian thành những chuỗi con.
Tuy nhiên, nhiều tác giả đưa ra những phương pháp phân đoạn và kết chuỗi thời gian quá cầu kỳ, phức tạp với thời gian tính toán lâu. Do đó, luận văn đề nghị hướng tiếp cận cho bài toán bằng việc phân đoạn dựa vào các điểm cực trị quan trọng (important extreme points) của tác giả Fink và Gandhi [17] và mô hình xác định tham số R của công trình [13] [14] để tìm các phân đoạn. Định nghĩa về các điểm cực trị và giải thuật xác định chúng được giới thiệu trong phần 3. Về bài toán kết chuỗi con, phương pháp đầu tiên là cách kết chuỗi con trực tiếp.
Chuỗi thời gian sẽ được kết trực tiếp bằng giải thuật lặp lồng nhau (nested loop) và thực hiện so trùng tất cả các chuỗi con có thể mà không có thêm bất kỳ kỹ thuật nào khác. Cách tiếp cận này bảo đảm tính đúng đắn và đẩy đủ của kết quả. Tuy nhiên, hạn chế lớn nhất của phương pháp là đưa đến trường hợp vét cạn (brute force) trên dữ liệu chuỗi thời gian. Ngoài ra còn có các phương khác như phương pháp kết chuỗi con dưa trên dữ liệu đã lập chỉ mục ([18], [19], [20]).
Các nhóm tác giả đề xuất lập chỉ mục không gian 𝑅 − 𝑇𝑟𝑒𝑒 và thực hiện thao tác kết chuỗi con hoặc thực hiện phép kết không gian trên dữ liệu đã được lập chỉ mục. Tuy nhiên, tất cả các hướng tiếp cận lập chỉ mục dựa trên cây 𝑅 đều yêu cầu không gian bộ nhớ lớn cho việc duy trì và xây dựng lại cấu trúc chỉ mục 𝑅 − 𝑇𝑟𝑒𝑒. Mà việc xây dựng lại cây 𝑅 tốn nhiều tài nguyên. Do đó, chi phí truy vấn tốn kém trong ngữ cảnh này.
CÁC CÔNG TRÌNH LIÊN QUAN ĐẾN SONG SONG HÓA DỰA TRÊN GPU Hầu hết các cách tiếp cận kể trên đều hướng đến giải pháp bằng phần mềm. Các phương pháp có thể đưa kết quả nhanh nhưng độ chính xác chỉ mang tính xấp xỉ, hơn nữa khó áp dụng với dữ liệu dạng luồng (streaming data). Vì thế, một số tác giả đã tiếp 9 Chương 2: Các Công trình nghiên cứu liên quan cận theo hướng tăng tốc bằng phần cứng như kỹ thuật xử lý song song dựa vào GPU ([5], [6], [8], [9], [10], [11]) cho những bài toán khai phá dữ liệu liên quan đến chuỗi thời gian tĩnh, cũng như dữ liệu luồng. Theo như giải pháp của Sart và các cộng sự năm 2010 [6] cho bài toán so trùng chuỗi con, các tác giả đã thực hiện giải thuật vét cạn song song trên GPU.
Trong đó, mỗi luồng của GPU sẽ đảm nhận tính toán độc lập một ma trận DTW, kết quả trả về từ GPU sẽ là một mảng các giá trị khoảng cách DTW. Host hay CPU sẽ so sánh các giá trị này với ngưỡng cho trước để tìm ra các chuỗi con trùng với chuỗi truy vấn. Cụ thể, hiện thực DTW trên GPU của tác giả đề xuất bao gồm ba công đoạn sau: 1. Sao chép dữ liệu từ CPU sang GPU.
CPU kích hoạt các hạt nhân (kernel) của GPU để xử lý song song. Sao chép kết quả trả về từ GPU cho CPU. Ở bước một, CPU sao chép toàn bộ chuỗi thời gian T vào bộ nhớ toàn cục của GPU. Nếu kích thước của T lớn hơn bộ nhớ sẵn dùng của thiết bị thì nó được chia thành những lô (batch) nhỏ hơn và xử lý mỗi lần một lô.
Quá trình này có thể gây ra độ trễ, nhưng không ảnh hưởng nhiều đến xử lý thời gian thực vì thời gian sao chép thường chỉ khoảng vài phần ngàn giây (milisecond). Cho nên, việc sao chép từng lô một có thể chịu được tốc độ dữ liệu đến hàng trăm hertz mà không làm tràn bộ đệm. Vì chuỗi truy vấn Q được cố định và sử dụng để so trùng với tất cả các lô, nên nó được sao chép vào bộ nhớ toàn cục ngay từ đầu và giữ nó ở đó trong suốt quá trình thực thi. Ở bước thứ hai, CPU gọi kernel trong GPU để xử lý song song.
Mỗi luồng trong kernel sẽ xử lý một cửa sổ trượt (sliding window) trong T qua hai bước: truy cập vào của sổ trượt và tính khoảng cách DTW với chuỗi truy vấn Q. Nếu chúng ta nhóm các luồng chịu trách nhiệm cho các cửa sổ trượt liên tiếp trong một khối, thì việc truy cập bộ nhớ bằng những luồng này sẽ dẫn đến các truy cập được kết hợp lại. Tức là, việc truy cập vùng nhớ chỉ thực hiện một lần cho các luồng thuộc một khối.1, một khối gồm bốn luồng cho thấy việc truy cập bộ nhớ lần đầu bởi những luồng này chỉ đọc một lần thay vì là bốn, bởi vì các luồng hoạt động trên các vị trí tiếp giáp trong bộ nhớ. 10 Chương 2: Các Công trình nghiên cứu liên quan Hình 2.1: Phân chia công việc giữa các luồng.
Truy cập bộ nhớ được kết hợp bởi các luồng trùng lắp [6]. Mặt khác, Q là một chuỗi thời gian truy vấn cố định và theo định nghĩa, nó không bị thay đổi trong quá trình thực thi. Hơn nữa Q nhỏ hơn nhiều so với T nên nó có thể vừa với bộ nhớ chia sẻ của thiết bị GPU. Bộ nhớ chia sẻ là bộ nhớ đặc biệt có sẵn trong một lõi trong bộ xử lý đa nhân của thiết bị GPU.
Bộ nhớ chia sẻ nhanh hơn 150x so với bộ nhớ toàn cục. Thông thường, bộ nhớ chia sẻ là nhỏ hơn nhiều so với bộ nhớ toàn cục và do đó là nơi lý tưởng cho chuỗi thời gian truy vấn. Cuối cùng trong bước thứ ba, khi tất cả các luồng kết thúc thực thi, CPU sao chép kết quả của khoảng cách DTW trở lại bộ nhớ hệ thống và xử lý cho ra kết quả cuối cùng của bài toán so trùng chuỗi con. KẾT LUẬN Luận văn đề nghị và mở rộng hướng tiếp cận của Sart và các cộng sự cho bài toán tổng quát hơn là kết chuỗi con, đồng thời kết hợp thêm ràng buộc Sakoe-Chiba và các kỹ thuật chặn dưới khi tính toán độ đo DTW nhằm tăng tốc hơn nữa quá trình tính toán này.
