Luận văn thạc sĩ khoa học máy tính tăng tốc kết chuỗi con trên dữ liệu chuỗi thời gian dựa vào công nghệ gpu

Luận văn thạc sĩ nghiên cứu máy tính tăng tốc kết chuỗi con trên dữ liệu chuỗi thời gian dựa vào công nghệ gpu, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện

• Tác giả: Lâm Trường An
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Quốc gia TP. Hồ Chí Minh - Trường Đại học Bách Khoa
• Chuyên ngành: Khoa học máy tính
• Đề tài: Tăng tốc kết chuỗi con trên dữ liệu chuỗi thời gian dựa vào công nghệ GPU
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2018
• Địa điểm: Thành phố Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• DANH MỤC HÌNH
• DANH MỤC BẢNG
• 1. Chương 1: Giới thiệu về Đề tài
• 1.1. Bài toán Kết chuỗi con trên dữ liệu chuỗi thời gian
• 1.2. Ý nghĩa của Đề Tài
• 1.3. Mục tiêu, giới hạn và đối tượng nghiên cứu
• 1.4. Kết quả đạt được
• 1.5. Bố cục luận văn
• 2. Chương 2: Các Công trình nghiên cứu liên quan
• 2.1. Các công trình liên quan đến độ đo khoảng cách
• 2.2. Các công trình liên quan đến bài toán kết chuỗi con
• 2.3. Các công trình liên quan đến song song hóa dựa trên GPU
• 3. Chương 3: Khai phá dữ liệu chuỗi thời gian
• 3.1. Độ đo xoắn thời gian động DTW
• 3.2. Ràng buộc đường xoắn độ đo thời gian động
• 3.3. Ràng buộc chặn dưới
• 3.4. Kỹ thuật từ bỏ sớm
• 3.5. Các điểm Cực trị quan trọng
• 3.6. Công nghệ GPU
• 3.7. Tối ưu hóa hiệu suất khi lập trình trên GPU
• 4. Chương 4: Phương pháp đề xuất
• 4.1. Khái quát bài toán Kết chuỗi con
• 4.2. Chuẩn hóa dữ liệu
• 4.3. Phân đoạn chuỗi thời gian
• 4.4. Quá trình kết chuỗi con
• 4.5. Cắt tỉa các phép tính DTW không cần thiết
• 4.6. So trùng chuỗi con dựa vào GPU
• 4.7. Hạt nhân song song hóa việc tính độ đo DTW
• 5. Chương 5: Phương pháp thực nghiệm
• 5.1. Thực nghiệm kiểm tra kết quả kết chuỗi con
• 5.2. Thực nghiệm tốc độ thực thi
• 6. Chương 6: Tổng kết nội dung của Luận văn
• 6.1. Những đóng góp của đề tài
• 6.2. Hướng phát triển
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tăng tốc kết chuỗi con trên dữ liệu chuỗi thời gian

Luận văn tập trung vào việc tăng tốc kết chuỗi con trên dữ liệu chuỗi thời gian bằng cách sử dụng công nghệ GPU. Bài toán kết chuỗi con là một bài toán nền tảng trong nhiều ứng dụng khai phá dữ liệu, đặc biệt là trong các lĩnh vực như tài chính, y tế, và thiên văn học. Tăng tốc kết chuỗi con giúp cải thiện hiệu suất tính toán, đặc biệt khi xử lý các bộ dữ liệu lớn. Luận văn đề xuất một phương pháp kết hợp giữa tối ưu hóa hiệu suất bằng phần mềm và sức mạnh tính toán song song của GPU để giải quyết bài toán này.

1.1. Bài toán kết chuỗi con

Bài toán kết chuỗi con được định nghĩa là việc tìm kiếm các cặp chuỗi con tương tự trên hai chuỗi thời gian. Đây là bài toán tổng quát hơn so với bài toán so trùng chuỗi con, vốn chỉ tập trung vào việc tìm kiếm một chuỗi con trong một chuỗi thời gian lớn hơn. Bài toán này đòi hỏi việc phân đoạn chuỗi thời gian và tính toán độ tương tự giữa các chuỗi con, thường sử dụng độ đo Dynamic Time Warping (DTW).

1.2. Tối ưu hóa hiệu suất

Để tối ưu hóa hiệu suất, luận văn sử dụng các kỹ thuật như cắt tỉa các phép tính DTW không cần thiết và tính toán song song trên GPU. Các kỹ thuật này giúp giảm thiểu thời gian tính toán và tăng tốc độ xử lý dữ liệu. Đặc biệt, việc sử dụng GPU cho phép thực hiện hàng nghìn phép tính song song, giúp cải thiện đáng kể hiệu suất của bài toán.

II. Phương pháp đề xuất

Luận văn đề xuất một phương pháp kết hợp giữa tối ưu hóa thuật toán và tính toán song song trên GPU để giải quyết bài toán kết chuỗi con. Phương pháp này bao gồm các bước như chuẩn hóa dữ liệu, phân đoạn chuỗi thời gian, và tính toán độ đo DTW song song trên GPU. Kết quả thực nghiệm cho thấy phương pháp này đạt được hiệu suất cao trên các bộ dữ liệu lớn.

2.1. Chuẩn hóa dữ liệu

Quá trình chuẩn hóa dữ liệu giúp đảm bảo các chuỗi thời gian có cùng tỷ lệ và phạm vi giá trị, giúp việc tính toán độ tương tự chính xác hơn. Đây là bước quan trọng trước khi thực hiện các phép tính toán phức tạp như DTW.

2.2. Tính toán song song trên GPU

Việc sử dụng GPU cho phép thực hiện hàng nghìn phép tính DTW song song, giúp giảm thiểu thời gian tính toán. Luận văn sử dụng các kỹ thuật lập trình song song trên GPU để tối ưu hóa hiệu suất, đặc biệt là khi xử lý các bộ dữ liệu lớn.

III. Kết quả và đánh giá

Kết quả thực nghiệm cho thấy phương pháp đề xuất đạt được hiệu suất cao trên các bộ dữ liệu lớn, với thời gian tính toán được cải thiện đáng kể so với các phương pháp truyền thống. Luận văn cũng đánh giá tính khả thi và hiệu quả của việc sử dụng GPU trong việc tăng tốc kết chuỗi con trên dữ liệu chuỗi thời gian.

3.1. Hiệu suất tính toán

Kết quả thực nghiệm cho thấy phương pháp đề xuất giảm thiểu thời gian tính toán đáng kể, đặc biệt khi xử lý các bộ dữ liệu lớn. Việc sử dụng GPU giúp tăng tốc độ tính toán lên nhiều lần so với các phương pháp truyền thống.

3.2. Ứng dụng thực tiễn

Phương pháp đề xuất có nhiều ứng dụng thực tiễn trong các lĩnh vực như tài chính, y tế, và thiên văn học. Việc tăng tốc kết chuỗi con giúp cải thiện hiệu suất của các ứng dụng khai phá dữ liệu, đặc biệt là khi xử lý các bộ dữ liệu lớn và phức tạp.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên dữ liệu lớn, khối lượng dữ liệu chuỗi thời gian được sinh ra với tốc độ theo cấp số nhân từ các hệ thống quan trắc, thiết bị y tế đến thị trường tài chính. Trong thực tế, dữ liệu điện tâm đồ thu thập trong một giờ có thể đạt dung lượng khoảng 1 Gigabyte, nhật ký truy cập mạng máy tính ghi nhận khoảng 5 Gigabyte mỗi tuần, và dữ liệu cảm biến đo đạc từ các trạm không gian có thể lên tới 158 Gigabyte. Việc khai phá kho dữ liệu khổng lồ này đóng vai trò then chốt để phát hiện tri thức mới, nhận diện mô típ lặp lại và cảnh báo bất thường kịp thời.

Bài toán nền tảng trong khai phá chuỗi thời gian là so trùng chuỗi con và dạng mở rộng tổng quát hơn là kết chuỗi con nhiều-nhiều giữa hai chuỗi dữ liệu. Thách thức lớn nhất nằm ở việc tính toán độ đo khoảng cách tương tự. Khoảng cách Euclid truyền thống bộc lộ nhiều hạn chế khi dữ liệu bị nhiễu hoặc co giãn theo thời gian, trong khi độ đo xoắn thời gian động giải quyết triệt để sự lệch pha và khác biệt chiều dài nhưng lại có độ phức tạp thuật toán lên đến bậc hai. Thao tác tính toán xoắn thời gian động thường chiếm hơn 80% tổng thời gian truy vấn của toàn bộ hệ thống, tạo ra nút thắt cổ chai nghiêm trọng về hiệu năng.

Luận văn thạc sĩ chuyên ngành Khoa học Máy tính của tác giả Lâm Trường An, thực hiện tại Trường Đại học Bách Khoa thuộc Đại học Quốc gia Thành phố Hồ Chí Minh dưới sự hướng dẫn của Phó Giáo sư Tiến sĩ Dương Tuấn Anh, tập trung giải quyết bài toán tăng tốc kết chuỗi con trên dữ liệu chuỗi thời gian đơn biến tĩnh. Mục tiêu trọng tâm của nghiên cứu là xây dựng mô hình kết hợp giữa kỹ thuật phân đoạn chuỗi dựa trên điểm cực trị quan trọng, bộ lọc cắt tỉa phần mềm xếp tầng và kỹ thuật tính toán song song trên phần cứng bộ xử lý đồ họa. Đề tài mở ra hướng tiếp cận đột phá, rút ngắn thời gian xử lý các chuỗi dữ liệu có quy mô hơn 100.000 điểm từ nhiều giờ xuống chỉ còn vài giây, mở đường cho các ứng dụng phân tích thời gian thực trong y tế và tài chính.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu xây dựng trên nền tảng lý thuyết khai phá dữ liệu chuỗi thời gian, độ đo tương tự phi tuyến tính và kiến trúc tính toán song song không đồng nhất. Trọng tâm của khung lý thuyết gồm năm khái niệm cốt lõi:

Thứ nhất, độ đo xoắn thời gian động là phép đo khoảng cách tối ưu giữa hai chuỗi thời gian bằng phương pháp quy hoạch động nhằm tìm đường xoắn cực tiểu trên ma trận chi phí kích thước m x n. Điểm đặc trưng của phương pháp này là cho phép ánh xạ không tuyến tính một-nhiều giữa các điểm dữ liệu, khắc phục hoàn toàn hiện tượng lệch pha.

Thứ hai, kỹ thuật giới hạn đường xoắn Sakoe-Chiba áp dụng cửa sổ xoắn có độ rộng cố định r quanh đường chéo chính với điều kiện trị tuyệt đối hiệu số chỉ số không vượt quá r. Cơ chế này loại bỏ các đường xoắn phi thực tế và giảm đáng kể không gian trạng thái cần duyệt.

Thứ ba, giải thuật phân đoạn chuỗi dựa trên các điểm cực trị quan trọng do Fink và Gandhi đề xuất. Bằng cách sử dụng tham số R xác định dựa trên hai lần độ lệch chuẩn lấy mẫu từ lý thuyết thống kê, giải thuật trích xuất các điểm cực đại và cực tiểu có ý nghĩa với độ phức tạp tuyến tính O(n), tạo thành các phân đoạn mẫu truy vấn đại diện.

Thứ tư, hệ thống lọc chặn dưới xếp tầng bao gồm chặn dưới Kim đơn giản với độ phức tạp O(1) dựa trên các bộ điểm biên và chặn dưới Keogh với độ phức tạp O(n) sử dụng đường bao cận trên và cận dưới. Nguyên lý cơ bản là nếu giá trị chặn dưới vượt quá ngưỡng tương tự epsilon thì khoảng cách xoắn thời gian động thực tế chắc chắn vượt ngưỡng, cho phép cắt tỉa chuỗi con ngay lập tức mà không gây sai số.

Thứ năm, mô hình kiến trúc tính toán không đồng nhất kết hợp giữa bộ vi xử lý trung tâm và bộ xử lý đồ họa của hãng NVIDIA. Mô hình lập trình CUDA phân chia khối lượng công việc thành các khối luồng, mỗi khối gồm các warp 32 luồng thực thi theo cơ chế đơn chỉ thị đa dữ liệu, khai thác tối đa băng thông bộ nhớ và năng lực tính toán dấu chấm động.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp thực nghiệm định lượng trên năm bộ dữ liệu chuẩn benchmark quốc tế có đặc tính đa dạng gồm dữ liệu sinh học phân tử Chromosome, dữ liệu điện não đồ EEG, dữ liệu điện tâm đồ ECG, dữ liệu tiêu thụ điện năng Power và dữ liệu biến động thị trường chứng khoán Stock. Cỡ mẫu thực nghiệm dao động từ 10.000 điểm đến hơn 100.000 điểm dữ liệu thời gian liên tục. Phương pháp chọn mẫu tập trung vào các chuỗi thời gian có mật độ dao động cao, xuất hiện nhiều biến dạng sóng và chứa độ trễ pha để kiểm tra độ tin cậy tuyệt đối của thuật toán.

Lý do lựa chọn phương pháp phân tích kết hợp phần mềm và phần cứng là nhằm tận dụng sức mạnh xử lý điều khiển phức tạp của CPU cho việc chuẩn hóa dữ liệu, đồng thời chuyển giao toàn bộ các phép toán ma trận lặp lại sang hàng trăm nhân tính toán song song trên GPU. Dữ liệu đầu vào trước tiên được chuẩn hóa theo phương pháp Z-score với giá trị trung bình bằng 0 và phương sai bằng 1. Tiếp theo, CPU thực hiện phân đoạn chuỗi bằng thuật toán cực trị quan trọng với chi phí O(n). Các mẫu truy vấn sau đó được đưa vào quy trình cắt tỉa chặn dưới sơ cấp trước khi nạp vào bộ nhớ GPU. Trên GPU, mỗi luồng đảm nhận tính toán độc lập một ma trận khoảng cách cho từng cửa sổ trượt. Dữ liệu chuỗi truy vấn được lưu trực tiếp trên bộ nhớ chia sẻ có tốc độ truy xuất nhanh hơn bộ nhớ toàn cục khoảng 150 lần, giúp triệt tiêu độ trễ truy cập dữ liệu và tối ưu hóa thời gian xử lý toàn phần.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thực nghiệm đã chứng minh tính hiệu quả vượt bậc của phương pháp đề xuất qua bốn phát hiện quan trọng:

Phát hiện thứ nhất, giải thuật phân đoạn bằng điểm cực trị quan trọng giúp giảm số lượng mẫu truy vấn cần xử lý xuống khoảng 60% đến 80% so với phương pháp vét cạn trượt từng điểm, trong khi vẫn bảo toàn đầy đủ các đặc trưng hình học cốt lõi của chuỗi thời gian ban đầu với chi phí tính toán chỉ ở mức O(n).

Phát hiện thứ hai, sự kết hợp giữa kỹ thuật cắt tỉa chặn dưới Kim đơn giản và ràng buộc dải Sakoe-Chiba giúp loại bỏ thành công từ 70% đến hơn 85% số phép tính ma trận không cần thiết trước khi gửi dữ liệu sang thiết bị xử lý đồ họa, giảm thiểu áp lực truyền dữ liệu qua bus giao tiếp PCI-Express.

Phát hiện thứ ba, trên phần cứng thử nghiệm GPU NVIDIA GeForce GTX 850M với 640 nhân xử lý, phương pháp song song hóa đạt tốc độ thực thi nhanh hơn từ 15 lần đến hơn 50 lần so với giải thuật tuần tự truyền thống chạy trên CPU đơn lõi. Khi kiểm thử trên tập dữ liệu điện não đồ EEG và dữ liệu năng lượng Power có quy mô trên 100.000 điểm, thời gian thực thi giảm từ hàng chục phút xuống dưới 10 giây.

Phát hiện thứ tư, khi nâng cấp thử nghiệm lên kiến trúc GPU cao cấp NVIDIA Tesla P100 với 3.584 nhân xử lý và băng thông bộ nhớ vượt trên 700 Gigabyte mỗi giây, hệ thống ghi nhận mức tăng tốc vượt trội, nhanh hơn từ 3 lần đến 8 lần so với dòng card tầm trung GTX 850M. Tỷ lệ bỏ sót ứng viên đúng đạt mức 0%, khẳng định độ chính xác tuyệt đối của phương pháp.

Thảo luận kết quả

Nguyên nhân chính dẫn đến sự gia tốc mạnh mẽ của hệ thống là việc chuyển đổi mô hình tính toán từ tuần tự sang song song hàng loạt cấp độ luồng. Trong kiến trúc GPU, việc nhóm các luồng xử lý các cửa sổ trượt liên tiếp vào cùng một khối giúp kích hoạt cơ chế truy cập bộ nhớ kết hợp, cho phép đọc dữ liệu từ bộ nhớ toàn cục chỉ trong một chu kỳ truy xuất duy nhất. Hơn nữa, việc nạp chuỗi mẫu truy vấn cố định vào vùng bộ nhớ chia sẻ nội bộ của từng bộ xử lý đa nhân đã giải quyết triệt để hiện tượng nghẽn cổ chai băng thông.

So sánh với các công trình nghiên cứu trước đây như giải pháp sử dụng cấu trúc chỉ mục cây R-Tree, phương pháp đề xuất không tốn chi phí xây dựng lại chỉ mục đắt đỏ khi dữ liệu biến động. So với mô hình tính toán GPU thuần túy của nhóm tác giả Sart công bố năm 2010, giải pháp tích hợp thêm bộ lọc chặn dưới phần mềm đã giảm thiểu đáng kể số lượng luồng nhàn rỗi và tải trọng tính toán trên nhân GPU.

Các kết quả nghiên cứu trong luận văn được minh họa trực quan thông qua các biểu đồ đường so sánh thời gian thực thi giữa ba phương pháp: CPU tuần tự, GPU không cắt tỉa và GPU có cắt tỉa trên từng tập dữ liệu cụ thể. Đồ thị cho thấy độ dốc thời gian của phương pháp GPU có cắt tỉa gần như đi ngang khi chiều dài chuỗi dữ liệu tăng từ 20.000 lên 100.000 điểm. Bên cạnh đó, hệ thống bảng biểu chi tiết trình bày ma trận đối sánh giữa tham số ngưỡng R, kích thước cửa sổ xoắn r và giá trị khoảng cách epsilon, cung cấp bằng chứng định lượng rõ ràng về tính ổn định của thuật toán.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu thực nghiệm, luận văn đưa ra bốn đề xuất hành động cụ thể nhằm hoàn thiện và ứng dụng giải pháp vào thực tiễn:

Thứ nhất, tối ưu hóa cấu trúc bộ nhớ và cơ chế lập lịch warp trên các dòng card đồ họa thế hệ mới. Đội ngũ kỹ sư phần mềm hệ thống cần tái cấu trúc việc phân bổ thanh ghi và bộ nhớ chia sẻ nhằm đạt mức độ chiếm dụng tối đa trên mỗi bộ xử lý đa nhân. Mục tiêu là nâng cao thông lượng xử lý dữ liệu thêm khoảng 25% đến 40%, thực hiện trong lộ trình 3 đến 6 tháng tới.

Thứ hai, mở rộng mô hình tính toán sang môi trường đa GPU và cụm máy tính phân tán. Các chuyên gia dữ liệu lớn tại các viện nghiên cứu cần nghiên cứu cơ chế phân vùng chuỗi thời gian thông minh để phân phối đồng thời trên nhiều thiết bị GPU kết nối qua mạng tốc độ cao. Mục tiêu nhằm xử lý các tập dữ liệu có quy mô hàng triệu đến hàng tỷ điểm với thời gian phản hồi dưới 500 mili-giây, triển khai trong giai đoạn 6 đến 12 tháng.

Thứ ba, tích hợp thuật toán tăng tốc vào các hệ sinh thái phần mềm y tế và tài chính trực tuyến. Các doanh nghiệp phát triển giải pháp công nghệ y tế và công ty tài chính định lượng nên ứng dụng ngay mô hình này để xây dựng hệ thống phát hiện loạn nhịp tim tự động từ tín hiệu điện tâm đồ và cảnh báo bất thường tỷ giá ngoại tệ. Mục tiêu duy trì độ trễ xử lý dưới 50 mili-giây trên các luồng dữ liệu liên tục, hoàn thành trong vòng 9 tháng.

Thứ tư, mở rộng nghiên cứu sang bài toán chuỗi thời gian đa biến và dữ liệu luồng động. Các nhóm nghiên cứu học thuật cần phát triển các hàm chặn dưới đa chiều và cơ chế cập nhật cực trị trượt linh hoạt, đảm bảo độ chính xác khớp mẫu đạt trên 95% trong không gian đa chiều, thực hiện trong kế hoạch nghiên cứu 12 đến 18 tháng.

Đối tượng nên tham khảo luận văn

Nội dung và kết quả nghiên cứu của luận văn mang lại giá trị thiết thực cho bốn nhóm đối tượng chuyên môn:

Nhóm thứ nhất, các nhà nghiên cứu và học viên cao học chuyên ngành Khoa học Máy tính và Khai phá Dữ liệu. Luận văn cung cấp tài liệu tham khảo chuyên sâu về các phép đo tương tự chuỗi thời gian, phương pháp chứng minh tính chất chặn dưới và kỹ thuật phân đoạn chuỗi dựa trên lý thuyết thống kê.

Nhóm thứ hai, các kỹ sư lập trình tính toán hiệu năng cao và chuyên gia tối ưu hóa CUDA. Nhóm đối tượng này có thể khai thác các mã giả, kỹ thuật quản lý bộ nhớ chia sẻ, tối ưu hóa truy cập bộ nhớ kết hợp và kiến trúc xử lý luồng không đồng nhất được trình bày chi tiết trong luận văn để áp dụng vào các dự án song song hóa khác.

Nhóm thứ ba, các chuyên gia phân tích tín hiệu y sinh học và kỹ sư thiết bị y tế. Luận văn cung cấp giải pháp xử lý nhanh các chuỗi tín hiệu điện tim, điện não phức tạp, hỗ trợ xây dựng các công cụ chẩn đoán tự động không bị ảnh hưởng bởi nhiễu và độ lệch pha.

Nhóm thứ tư, các nhà phát triển hệ thống tài chính định lượng và công nghệ tài chính. Công trình mang lại thuật toán hiệu quả để so khớp các mô hình tỷ giá hối đoái, nhận diện chu kỳ phụ thuộc tiền tệ và phát hiện biến động bất thường của thị trường chứng khoán trong thời gian thực.

Câu hỏi thường gặp

Tại sao độ đo xoắn thời gian động lại vượt trội hơn khoảng cách Euclid trong phân tích chuỗi thời gian?

Khoảng cách Euclid chỉ so sánh từng cặp điểm tương ứng theo thứ tự thời gian cố định, dẫn đến sai số rất lớn khi dữ liệu bị co giãn hoặc lệch pha. Ngược lại, độ đo xoắn thời gian động sử dụng quy hoạch động để ánh xạ phi tuyến tính một điểm với nhiều điểm, cho phép nhận diện chính xác các dạng sóng tương đồng dù thời lượng xuất hiện khác nhau.

Tham số R trong thuật toán tìm điểm cực trị quan trọng được tính toán như thế nào?

Tham số R được xác định bằng công thức hai lần độ lệch chuẩn lấy mẫu từ lý thuyết thống kê trên chuỗi dữ liệu đã chuẩn hóa. Việc chọn giá trị này đảm bảo các điểm cực trị được giữ lại là những điểm biến động vượt ra ngoài dải dao động ngẫu nhiên thông thường, giúp loại bỏ nhiễu và giữ lại khung xương đặc trưng của chuỗi.

Việc kết hợp giải pháp phần mềm và phần cứng GPU đem lại lợi thế gì so với chỉ dùng GPU thuần túy?

Nếu chỉ sử dụng GPU thuần túy theo giải thuật vét cạn, hàng nghìn nhân tính toán sẽ phải xử lý cả những chuỗi con hoàn toàn sai khác. Việc tích hợp các kỹ thuật lọc chặn dưới phần mềm như chặn dưới Kim giúp CPU loại bỏ trước phần lớn các nhánh tính toán không hợp lệ, giảm tải băng thông truyền dữ liệu và tăng tốc độ xử lý tổng thể lên gấp nhiều lần.

Chặn dưới Kim đơn giản hoạt động ra sao và tại sao lại đạt độ phức tạp O(1)?

Chặn dưới Kim đơn giản trích xuất các bộ điểm đầu và điểm cuối của hai chuỗi con để tính toán khoảng cách chênh lệch cực tiểu. Do chỉ thao tác trên một số lượng điểm cố định mà không cần duyệt qua toàn bộ chiều dài chuỗi, giải thuật đạt thời gian thực thi cố định O(1), cho phép cắt tỉa ứng viên gần như ngay lập tức.

Luận văn có những giới hạn nghiên cứu nào về mặt dữ liệu và phần cứng?

Nghiên cứu tập trung giải quyết trên dữ liệu chuỗi thời gian đơn biến và ở trạng thái tĩnh. Về mặt phần cứng, các thử nghiệm được thực hiện trên cấu hình máy tính gắn một thiết bị GPU rời của hãng NVIDIA, chưa triển khai trên hệ thống phân tán nhiều card đồ họa đồng thời.

Kết luận

Luận văn đã giải quyết thành công bài toán tăng tốc kết chuỗi con trên dữ liệu chuỗi thời gian thông qua việc kết hợp tối ưu giữa giải thuật phần mềm và kiến trúc phần cứng GPU. Những đóng góp cốt lõi của công trình được tổng kết qua năm điểm nhấn sau:

• Xây dựng thành công quy trình phân đoạn chuỗi thời gian tự động dựa trên các điểm cực trị quan trọng với độ phức tạp tuyến tính O(n), tạo tiền đề vững chắc cho việc sinh các mẫu truy vấn chính xác.
• Đề xuất mô hình cắt tỉa xếp tầng kết hợp giữa chặn dưới Kim đơn giản và ràng buộc Sakoe-Chiba, giúp giảm thiểu hơn 70% khối lượng tính toán ma trận xoắn thời gian động.
• Hiện thực hóa thành công hạt nhân tính toán song song trên nền tảng NVIDIA CUDA, tận dụng tối đa bộ nhớ chia sẻ và kỹ thuật truy cập kết hợp để tăng tốc độ xử lý lên tới hơn 50 lần.
• Đánh giá thực nghiệm toàn diện trên năm bộ dữ liệu chuẩn quốc tế quy mô lớn, chứng minh tính đúng đắn và khả năng bảo toàn kết quả với tỷ lệ bỏ sót ứng viên bằng 0%.
• Mở ra hướng tiếp cận thực tiễn ứng dụng tính toán GPU vào các hệ thống khai phá dữ liệu lớn trong y tế, tài chính và công nghiệp quan trắc.

Kế hoạch tiếp theo bao gồm việc tối ưu hóa thuật toán cho dữ liệu chuỗi thời gian đa biến và xây dựng hệ thống xử lý phân tán trên cụm máy tính đa GPU trong vòng 12 tháng tới. Độc giả quan tâm đến lĩnh vực khai phá dữ liệu chuỗi thời gian và lập trình tính toán song song có thể khai thác toàn bộ mô hình và phương pháp luận của nghiên cứu này để ứng dụng vào các bài toán xử lý dữ liệu lớn trong thực tế.

Trích đoạn nội dung tài liệu

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.