Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu.

- Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu Page 1 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI.
- LÊ QUỐC THI NGHIÊN CỨU THUẬT TOÁN SONG SONG TRÊN MÔI TRƢỜNG MPI CHO BÀI TOÁN SO KHỚP XÂU Chuyên ngành : Công nghệ thông tin LUẬN VĂN THẠC SĨ KỸ THUẬT CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC TS.
- NGUYỄN TUẤN DŨNG Hà Nội – Năm 2014 Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu Page 2 LỜI CAM ĐOAN Tôi – Lê Quốc Thi - Cam kết luận văn này là công trình nghiên cứu của bản thân tôi dưới sự hướng dẫn của TS.
- Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu Page 3 LỜI CẢM ƠN Trước hết, tôi xin gửi lời cảm ơn trân trọng nhất tới TS.Nguyễn Tuấn Dũng, bộ môn Khoa học máy tính, Viện Công nghệ thông tin và Truyền thông, trường Đại học Bách Khoa Hà Nội, người đã hướng dẫn, tận tình chỉ bảo và hỗ trợ tôi trong suốt quá trình làm luận văn tốt nghiệp.
- Tôi xin gửi lời cám ơn tới các thầy cô trong Viện Công nghệ thông tin và Truyền thông cùng toàn thể các thầy cô trường Đại học Bách Khoa Hà Nội đã cùng giúp đỡ, hỗ trợ tôi trong suốt quá trình nghiên cứu và thực hiện luận văn này Hà Nội, tháng 02 năm 2014 Học viên : Lê Quốc Thi Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu Page 4 MỤC LỤC MỤC LỤC.
- 7 1.1 Bài toán so khớp xâu.
- 7 1.2 Một số thuật toán so khớp xâu.
- 11 1.2.2 Phương pháp Aho-corasick.
- 15 1.2.3 Phương pháp phân tách Head-Body.
- 19 1.2.4 Thực hiện bài toán so khớp xâu trong môi trường song song.
- 26 Chƣơng 2 - Cài đặt và phân tích các thuật toán cho bài toán so khớp xâu.
- 30 2.1 Phân tích, cài đặt và đánh giá thuật toán tuần tự.
- 30 2.1.1 Phân tích phương pháp Aho-corasick.
- 30 2.1.2 Phân tích phương pháp phân tách Head-Body.
- 37 2.2 Xây dựng bài toán MSM trong môi trường song song.
- 43 2.2.1 Cài đặt thuật toán trong môi trường song song MPI.
- 43 2.2.2 Phương pháp Head Body trong môi trường song song.
- 43 2.2.3 Phương pháp song song Master – Slave cho thuật toán Head Body.
- 44 2.2.4 Cài đặt phương pháp Head Body với MPI.
- 46 Chƣơng 3 - Kết quả thu đƣợc từ thực nghiệm và ứng dụng của bài toán.
- 51 3.2 Ứng dụng của bài toán.
- 61 Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu Page 5 DANH MỤC HÌNH VẼ Hình 1.
- Các hàm goto, failure, output sinh ra từ thuật toán AC.
- Ảnh hưởng tỉ lệ so khớp tới hiệu năng của thuật toán [6.
- Phương pháp song song cho thuật toán Head-Body.
- 44 Hình 6: Biểu đồ so sánh hiệu năng của phương pháp song song Head-Body với tỉ lệ so khớp và kích thước subtext.
- 51 Hình 7: Biểu đồ so sánh hiệu năng phương pháp song song và tuần tự với số processor khác nhau.
- 52 Hình 8: Biểu đồ so sánh phương pháp HB song song và AC song song.
- 53 Hình 9: Biểu đồ so sánh hiệu năng phương pháp HB song song và AC song song trong môi trường nhiều máy.
- 57 Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu Page 6 DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ Từ viết tắt Từ đầy đủ Ý nghĩa MSM Multi String Matching Bài toán tìm kiếm nhiều từ mẫu.
- AC Aho-Corasick algromith Thuật toán Aho-Corasick DFA Deterministic finite automata Automat hữu hạn tiền định NFA Nondeterministic finite automata Automat hữu hạn không tiền định HB Head-Body algromith Thuật toán phân tách Head Body H-DFA Head DFA Phần head có dạng DFA trong thuật toán Head-Body B-NFA Body NFA Phần body có dạng NFA trong thuật toán Head-Body STT State transition table Bảng chuyển trạng thái Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu Page 7 Chƣơng 1 - Đặt vấn đề và định hƣớng giải pháp 1.1 Bài toán so khớp xâu Bài toán so khớp xâu (Multi String Matching) là bài toán xuất hiện nhiều trong các ứng dụng thực tế.
- Giải thuật string matching kiểm tra và phát hiện sự xuất hiện của nhiều kí tự liên tiếp trong một tập dữ liệu.
- Với yêu cầu đó, đã có rất nhiều thuật toán về string matching được đưa ra, một trong số các thuật toán hiệu quả nhất là Aho-corasick (AC.
- Thuật toán này có những ưu điểm nổi bật là có thể tìm kiếm đồng thời sự xuất hiện của nhiều từ mẫu và có thời gian tính toán là tuyến tính tỉ lệ thuận với chiều dài của dữ liệu vào.
- Rất nhiều nghiên cứu đã được thực hiện với thuật toán AC, trên nhiều khía cạnh nhua trong đó có việc thực thi thuật toán trên nhiều nền tảng.
- Gần đây, các bộ xử lý đồ họa (GPU) cũng được sử dụng, đặc biệt là các bộ xử lý của NVIDIA với công nghệ CUDA hỗ trợ lập trình song song.
- Hầu hết các phương pháp này đều tập trung vào việc cải thiện tốc độ.
- Chỉ vài năm gần đây, các khía cạnh khác Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu Page 8 như sự ổn định hiệu suất, khả năng làm việc với các từ điển lớn bắt đầu được quan tâm, đặc biệt là vấn đề từ điển lớn.
- Tuy nhiên, thuật toán AC thường chỉ cho hiệu năng tốt khi có ít sự so khớp trên đầu vào, tức là kích thước của các mẫu tìm được trên kích thước dữ liệu đầu vào là thấp.
- Khi tỷ lệ này tăng lên, hiệu năng của thuật toán thường bị giảm nhanh chóng.
- Hơn nữa, việc hiệu suất thay đổi khi thực hiện với các dữ liệu đầu vào và từ điển có kích thước khác nhau luôn là một nhược điểm của các phương pháp dựa trên phần mềm.
- Điều này đặc biệt đúng với các kiến trúc dựa trên bộ nhớ cache: khi phép toán tìm kiếm được thực hiện bên trong bộ nhớ cache, thuật toán sẽ thực hiện rất hiệu quả.
- Tuy nhiên nếu việc tìm kiếm thực hiện ở bộ nhớ chính - main memory, hiệu năng của thuật toán khá thấp.
- Lúc này thuật toán sẽ phải truy nhập dữ liệu từ những vị trí trong bộ nhớ chính, dẫn đến sự thay đổi về hiệu năng.
- Để khắc phục được các nhược điểm này, nhiều phương pháp giúp cải thiện thuật toán AC đã được đưa ra.
- Trong đó có hai thuật toán là sử dụng bảng băm và thuật toán phân tách Head-Body.
- Việc sử dụng bảng băm giúp giảm kích thước dữ liệu phải xử lý do thuật toán AC sinh ra, tuy nhiên việc hàm băm có chi phí cao và dễ xảy ra va chạm băm làm cho thuật toán này trong nhiều trường hợp không tỏ ra hiệu quả.
- Một phương pháp mới là phân tách Head-Body sẽ tiếp cận bài toán theo hướng khác với hàm băm, vẫn giảm kích thước dữ liệu để đủ cho việc tìm kiếm có thể diễn ra trong bộ nhớ cache đồng thời hiệu năng không thay đổi nhiều trên các từ điển và các dữ liệu đầu vào khác nhau.
- Phương pháp và kỹ thuật trong hướng tiếp cận này sẽ được phân tích, so sánh và đánh giá với thuật toán AC.
- Với việc xây dựng bài toán MSM dựa trên phần mềm, một phương pháp cải Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu Page 9 thiện hiệu năng tất yếu được nghĩ tới là sử dụng nhiều máy tính cùng thực hiện bài toán.
- Đây chính là mục đích của tính toán song song phân cụm (Cluster), một hệ thống máy tính song song được xây dựng từ các nút tính toán và thiết bị mạng thông dụng, mỗi nút tính toán đóng vai trò điều khiển vào/ra là một hệ thống làm việc hoàn chỉnh, có khả năng làm việc độc lập.
- Việc thiết lập hệ thống tính toán song song phân cụm từ những máy tính có cấu trúc đơn giản, sử dụng công nghệ mạng phổ biến đã được bắt đầu từ năm 1994 với mô hình Beowulf Cluster của Thomas Sterling cùng Donal Becker.
- Tuy nhiên, luận văn sẽ không đi sâu về phía phần cứng mà tập trung vào việc thiết kế phần mềm chạy trên các bộ xử lý đa nhân với cấu trúc như các cluster, với thư viện lập trình song song được sử dụng là Message Passing Interface-MPI.
- Bài toán MSM có thể được thực hiện song song bằng cách chia đoạn dữ liệu đầu vào thành tập hợp các đoạn dữ liệu nhỏ hơn dữ liệu ban đầu và được gửi đến mỗi bộ xử lý để thực hiện tìm kiếm.
- Tuy nhiên, để có được hiệu suất tối đa trên tất cả các bộ xử lý cần đòi hỏi những thuật toán hiệu quả trong việc cân bằng tải.
- Luận văn sẽ đưa ra các thuật toán song song áp dụng cho bài toán MSM và thực hiện so sánh, phân tích hiệu quả các thuật toán đó trên dữ liệu đầu vào, từ điển và số bộ xử lý khác nhau.
- Ngoài ra, luận văn sẽ xây dựng mô hình song song cho thuật toán Head-Body để kiểm tra hiệu quả của nó trên cơ chế truyền thông điệp.
- Về ứng dụng của bài toán, trong những năm gần đây, bài toán MSM ngày càng được quan tâm hơn do sự bùng nổ của lượng thông tin trên mạng internet và nhu cầu tìm kiếm của người dùng.
- Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu Page 10 Với những nôi dung trình bày ở trên, luận văn bao gồm các phần tóm tắt như sau: Chương 1: Đặt vấn đề và định hướng giải pháp, phần này bao gồm các cơ sở lý thuyết và các thuật toán cho bài toán MSM Chương 2: Cài đặt và phân tích các thuật toán cho bài toán Multi String Matching Chương 3: Kết quả thu được từ thực nghiệm và ứng dụng của bài toán Chương 4: Kết luận và hướng phát triển của đề tài.
- Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu Page 11 1.2 Một số thuật toán so khớp xâu 1.2.1 Các cách tiếp cận cơ bản 1.2.1.1 Cách tiếp cận ngây thơ Phương pháp đầu tiên và đơn giản nhất có thể nghĩ đến ngay là lần lượt xét từng vị trí i trong xâu ký tự gốc từ 1 đến n-m+1, so sánh T[i…(i+m-1)] với P[1..m] bằng cách xét từng cặp ký tự một và đưa ra kết quả tìm kiếm.
- Người ta còn gọi phương pháp này là cách tiếp cận ngây thơ (Naïve string search).
- Dưới đây là thủ tục đặc tả của phương pháp này : NAÏVE_STRING_MATCHER (T, P) 1.
- s là vị trí tìm được 9.
- không có vị trí nào thỏa mãn Dễ thấy độ phức tạp trung bình của thuật toán là O(n+m), nhưng trong trường hợp tồi nhất độ phức tạp là O(n.m), ví dụ như tìm kiếm mẫu “”aaaab” trong xâu “aaaaaaaaab”.
- 1.2.1.2 Thuật toán Rabin-Karp Tư tưởng chính của phương pháp này là sử dụng phương pháp băm (hashing).
- Tức là mỗi một xâu sẽ được gán với một giá trị của hàm băm (hash function), ví dụ xâu “hello” được gán với giá trị 5, và hai xâu được gọi là bằng nhau nếu giá trị băm của nó bằng nhau.
- Như vậy thay vì việc phải đối sánh các xâu con của T với mẫu P, ta chỉ cần so sánh giá trị hàm băm của chúng và đưa ra kết luận.
- Đặc tả chúng thuật toán như sau : Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu Page 12 1.
- giá trị băm của xâu P 3.
- giá trị băm của xâu T 4.
- giá trị băm của xâu T[i+1..i+m] 9.
- return not found Vấn đề đặt ra ở đây là khi có quá nhiều xâu sẽ tồn tại các trường hợp các xâu khác nhau có giá trị băm giống nhau, do đó khi tìm thấy hai xâu có giá trị băm giống nhau vẫn phải kiểm tra lại xem chúng có thực sự bằng nhau hay không (dòng 6), may mắn là trường hợp này rất ít xảy ra với một hàm băm thiết kế đủ tốt.
- Phân tích thuật toán ta thấy : dòng 2,3,6,8 có độ phức tạp là O(m), nhưng dòng 2,3 chỉ thực hiện duy nhất một lần, dòng 6 chỉ thực hiện khi giá trị băm bằng nhau (rất ít), chủ yếu là dòng số 8 sẽ quyết định độ phức tạp của thuật toán.
- Bởi khi tính giá trị băm cho T[i+1..i+m] ta mất thời gian là O(m), công việc này được thực hiện trong n-m+1 lần như vậy độ phức tạp không hơn gì so với phương pháp ở phần 2.
- Như vậy ta phải tính lại giá trị hs trong thời gian hằng số (constant time), cách giải quyết ở đây là tính giá trị băm của T[i+1..i+m] dựa vào giá trị băm của T[i..i+m-1] bằng cách sử dụng cách băm tròn (rolling hash, là cách băm mà giá trị đầu vào được băm với một kích thước cửa số cổ định trượt trên độ dài của giá trị cần băm).
- Cụ thể trong bài toán này, ta sử dụng công thức sau để tính giá trị băm tiếp theo trong một khoảng thời gian hằng số : hash(T[i+1…i+m.
- Đó là một cách băm đơn giản, dưới đây sẽ trình bày một hàm băm phức tạp và tốt hơn cho các trường hợp dữ liệu lớn.
- Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu Page 13 Ví dụ như xâu “hi” băm bằng số nguyên tố 101 sẽ có giá trị băm là ASCII của ký tự 'h' là 104 và của ký tự 'í là 105).
- Thêm nữa, ta có thể tính giá trị băm của một xâu con dựa vào các xâu con trước nó, ví dụ như ta có xâu "abracadabra", ta cần tìm một mẫu tìm kiếm có độ dài là 3.
- Ta có thể tính giá trị băm của xâu “bra” dựa vào giá trị băm của xâu “abr” (xâu con trước nó) bằng cách lấy giá trị băm của “abr” trừ đi giá trị băm của ký tự „a‟ đầu tiên (ví dụ như là giá trị ASCII của ký tự 'á và 101 là số nguyên tố đang sử dụng) và cộng thêm giá trị băm cảu ký tự „a‟ cuối cùng trong xâu “bra” (ví dụ như .
- 1.2.1.3 Thuật toán Knuth-Morris-Pratt Ý tưởng chính của phương pháp này như sau: trong quá trình tìm kiếm vị trí của mẫu P trong xâu gốc T, nếu tìm thấy một vị trí sai ta chuyển sang vị trí tìm kiếm tiếp theo và quá trình tìm kiếm sau này sẽ được tận dụng thông tin từ quá trình tìm kiếm trước để không phải xét các trường hợp không cần thiết.
- Ví dụ : tìm mẫu P = “ABCDABD” trong xâu T = “ABC ABCDAB ABCDABCDABDE” giả sử m và i là chỉ số chạy thuật toán tương ứng đối với xâu T và P.
- Ta lần lượt có các bước của thuật toán như sau.
- Ta chú ý là ký tự đầu tiên của P là „A‟ không xuất hiện trong T từ vị trí 0 đến 3 nên ta chuyển đến xét m=4.
- m=4, i=0 m S: ABC ABCDAB ABCDABCDABDE W: ABCDABD Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu Page 14 i: 0123456 Tại m=10, i=6 xâu T và mẫu P không khớp nhau (T[10.
- Ta lại thấy chuỗi “AB” trong mẫu P không xuất hiện trong T từ vị trí 5 đến vị trí 7, nên ta chuyển sang m=8.
- m=8 m S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456 Ta thấy trong mẫu không xuất hiện ký tự space, nên chuyển tiếp m=11 + m=11 m S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456 Ta thấy m=17 của T không khớp với i=6 của P nên ta xét tiếp m=15 +m=15 m S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456 Ta tìm được kết quả mẫu P xuất hiện trong xâu T ở vị trí 15.
- Như vậy qua ví dụ ta thấy vấn đề chủ yếu ở đây là tìm vị trí tiếp theo để kiểm tra sau khi bắt gặp một vị trí sai.
- Bây giờ ta giả sử có bảng đối sánh thành phần (partial match table) chỉ cho ta biết điểm xuất phát tiếp theo khi gặp một ví trí đối sánh sai (mismatch) F[1..m] trong đó giá trị F[i] là tổng số ký tự ta lùi lại để xét tiếp trên xâu T sau khi gặp một vị trí sai trong khi đang xét đến ký tự thứ i trong xâu mẫu tìm kiếm.
- Tức là nếu ở vị trí m mà T[m+i] khác P[i] thì ta sẽ xét tiếp vị trí m+i-F[i] trên xâu T.
- Có hai ưu điểm ở đây : thứ nhất là F[0]=-1 tức là nếu P[0] là vị trí sai thì ta sẽ chuyển ngay đến ký tự tiếp theo, thứ hai là mặc dù ta quay lại vị trí m+i-F[i] là Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu Page 15 vị trí kiểm tra tiếp theo nhưng thực sự ta chỉ cần đối sánh mẫu từ vị trí P[F[i.
- Cụ thể với bảng trên, lược đồ thuật toán KMP như sau : 1.
- If i = n then ta tìm được xâu con của T thỏa mãn bắt đầu từ vị trí m.
- Độ phức tạp thuật toán là O(k) với k là độ dài của xâu gốc T .
- 1.2.2 Phƣơng pháp Aho-corasick Trước khi đi đến thuật toán cụ thể, chúng ta sẽ mô tả chi tiết bài toán multi- string matching: Với dữ liệu đầu vào, ta có thể coi đó là một xâu xây dựng trên một bộ chữ.
- Đối với bài toán tìm kiếm từ trên đoạn văn bản, bộ chữ là bảng mã ASCII với 256 kí tự, nhưng đối với bài toán tìm kiếm mà mẫu là các chuỗi bit (như bài toán kiểm tra file xem có chứa mã độc hay không) thì bộ chữ này chỉ bao gồm các bit 0 và 1.
- Yêu cầu của bài toán là xác định tất cả các từ mẫu trong K mà là xâu con của x kèm theo vị trí của xâu con đó trong x .Các từ mẫu này có thể chồng lên nhau, tức là một từ mẫu A mà là tiền tố của từ mẫu B thì sự xuất hiện của từ mẫu B phải tính cả sự xuất hiện của A.
- Mô hình tìm kiếm này sẽ được biểu diễn bởi một tập hợp các trạng thái được đánh chỉ số.
- Nghiên cứu thuật toán song song trên môi trường MPI cho bài toán so khớp xâu Page 16 Một mô hình tìm kiếm như vậy được mô tả bởi ba hàm : 1 Hàm goto kí hiệu là g 2 Hàm failure kí hiệu là f 3 Hàm output Ví dụ với tập K={“her”, “here”, “the”} thì mô hình tìm kiếm sinh từ tập K này sẽ được biểu diễn bởi ba hàm tương ứng với các hình sau h e reth e (a).Goto function i f(i b).Failure function i outuput(i) 3 4 7 9 her here, her the {hers} (c).Output function Hình 1.
- Các hàm goto, failure, output sinh ra từ thuật toán AC Với hàm goto được biểu diễn bởi cây như hình a, có một trạng thái được gọi là trạng thái bắt đầu, thường được kí hiệu là 0

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt