Tài liệu Tối ưu hóa truy vấn tìm đường ngắn nhất trên đồ thị động quy mô lớn

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM HẢI ĐĂNG TỐI ƯU HÓA TRUY VẤN TÌM ĐƯỜNG NGẮN NHẤT TRÊN ĐỒ THỊ ĐỘNG QUY MÔ LỚN Ngành: Hệ thống thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 TÓM TẮT LUẬN VĂN THẠC SĨ NGÀNH HỆ THỐNG THÔNG TIN Hà Nội – 2016 Giới thiệu chung Động lực nghiên cứu Hiện nay, chúng ta đang sống trong thời đại bùng nổ về công nghệ công tin cũng như bùng nổ về các mạng xã hội. Một số mạng điển hình như mạng xã hội (Facebook, Twitter), mạng sinh học, mạng phân tán nội dung, mạng lưới giao thông, mạng thông tin… có số lượng dữ liệu tăng nhanh chóng mặt. Để giải quyết những thách thức về mặt dữ liệu lớn trên, có rất nhiều phương pháp tiếp cận, trong đó phương pháp tiếp cận dựa trên đồ thị được cho là trực quan và phù hợp nhất [8]. Với việc sử dụng lý thuyết đồ thị, với các đỉnh biểu diễn các thực thể và các cạnh biểu diễn mối liên hệ giữa chúng. Trong đồ thị, tìm đường đi (ngắn nhất) là vấn đề tìm sự kết nối giữa hai đỉnh của một đồ thị và đảm bảo đường đi đó là ngắn nhất dựa trên một số yêu cầu cho trước. Đây là vấn đề nền tảng và cơ bản được áp dụng trong rất nhiều ứng dụng thực tế như tìm đường đi ngắn nhất giữa hai địa điểm sử dụng GPS hay tìm mối liên kết giữa hai người trên mạng xã hội [6]. Vấn đề này bình thường rất đơn giản, nhưng trong bối cảnh số lượng các đỉnh, cạnh của đồ thị rất lớn (vài triệu đỉnh) và thay đổi nhanh (thêm cạnh, bớt cạnh), làm thế nào để tối ưu hóa quá trình tìm đường đi ngắn nhất là một thách thức lớn [21]. Mục tiêu và nội dung chính của luận văn Với mục tiêu trên, luận văn này sẽ trình bày giải pháp để cải thiện hiệu năng quá trình tối ưu truy vấn trên đồ thị động, quy mô lớn có hướng, không trọng số. Phương pháp tối ưu dựa trên các ý tưởng: cấu trúc dữ liệu phù hợp, tối ưu không gian tìm kiếm và cài đặt phù hợp. Tổ chức luận văn Nội dung của luận văn sẽ được tổ chức như sau: Mở đầu: Đặt vấn đề Chương 1: Giới thiệu về cơ sở lý thuyết, các vấn đề liên quan đến đồ thị và bài toán tìm đường đi ngắn nhất trong đồ thị. Chương 2: Trình bày bài toán, cách tiếp cận và phương pháp giải quyết bài toán. Chương 3: Thực nghiệm và kết quả đạt được. Kết luận chung: Kết luận và đưa ra hướng phát triển tiếp theo. 1 Chương 1. Cơ sở lý thuyết và các vấn đề liên quan 1.1. Đồ thị Trước khi tìm hiểu về lý thuyết đồ thị, chúng ta cùng xét một ví dụ về một mạng xã hội nhỏ [7] sau: Hình 1.1: Mạng xã hội Đây là ví dụ cơ bản về đồ thị. Tên người chính là các đỉnh, và mỗi đường liên kết giữa hai người chính là các cạnh. Chúng ta thường biểu diễn sự liên kết giữa hai đỉnh u và v bởi cặp (u, v). Bởi vì quan hệ “biết nhau” ở đây là quan hệ hai chiều, nên đây là ví dụ của đồ thị vô hướng. Trong đồ thị vô hướng thì cạnh (u, v) tương tự như cạnh (v, u). Trong đồ thị có hướng, thì quan hệ “biết nhau” không còn là hai chiều nữa, một người A biết người B nhưng chưa chắc người B đã biết người A. Nhìn trên đồ thị, An và Sơn có thể biết nhau thông qua Linh và Hạnh. Đây đường đi ngắn nhất giữa hai đỉnh An và Sơn. Chúng ta đánh dấu đường đi ngắn nhất này trong Hình 1.2. Hình 1.2: Đường đi trong mạng xã hội Khi đường đi xuất phát từ một đỉnh và quay lại chính nó, chúng ta gọi đó là một chu trình. Ví dụ từ An Bình tới Cường, Linh rồi cuối cùng quay 2 lại An. Thực ra, có chu trình ngắn hơn đó là từ An qua Bình tới Linh rồi quay lại An. Hình 1.3: Chu trình trong mạng xã hội Trong mạng xã hội, chúng ta có thể sử dụng một trọng số để xác định mức độ biết nhau giữa hai người. Một ví dụ cụ thể khác về đồ thị có trọng số chính là bản đồ đường đi. Giả sử tất cả đều là đường hai chiều, thì bản đồ đường đi này cũng là một đồ thị vô hướng, giá trị trọng số chính là số biểu diễn khoảng cách giữa các thành phố. Ví dụ Hình 1.4 mô tả khoảng cách giữa một số tỉnh thành phía Bắc nước Việt Nam. Hình 1.4: Bản đồ khoảng cách một số tỉnh thành phía Bắc Trong trường hợp bản đồ đường đi, nếu chúng ta muốn tìm đường đi ngắn nhất giữa các vị trí, chúng ta phải tìm kiếm đường đi qua các vị trí trung gian sao cho tổng trọng số là nhỏ nhất. Ví dụ ở bản đồ Hình 1.4, đường đi ngắn nhất từ Hà Nội tới Hạ Long, sẽ qua Hải Dương, Hải Phòng. Tổng cộng đoạn đường đi này có chiều dài 163km. Mối quan hệ giữa hai đỉnh không phải lúc nào cũng là hai chiều. Lấy ví dụ, trong bản đồ đường đi, chúng ta có thể gặp đường đi một chiều. Để 3 biểu diễn sự có hướng này, các cạnh được thêm dấu mũi tên ở cuối và đồ thị này được gọi là đồ thị có hướng. Ví dụ Hình 1.5 mô tả một mạng xã hội có hướng. Dễ nhận thấy, đồ thị ở Hình 1.5 không có chu trình, khi đó đồ thị được gọi là có hướng không chu trình. Hình 1.5: Mạng xã hội có hướng Như chúng ta thấy, đồ thị có rất nhiều ứng dụng trong biểu diễn các sự vật, mối quan hệ giữa các sự vật đó trong thế giới thực. Phần tiếp theo, luận văn sẽ trình bày một số lý thuyết nền tảng về đồ thị. 1.1.1. Giới thiệu đồ thị Đồ thị (G), kí hiệu là G = (V, E) bao gồm một tập các đỉnh (V) và tập các cạnh (E). Trong đó mỗi cạnh E nối giữa hai đỉnh thuộc tập các đỉnh (V) và được kí hiệu là E = (u, v) (Đỉnh u nối với đỉnh v). Ví dụ về đồ thị được đưa ra ở Hình 1.6. Hình 1.6: Đồ thị Đồ thị được phân loại dựa như sau: Đơn đồ thị vô hướng, Đa đồ thị vô hướng, Giả đồ thị vô hướng, Đơn đồ thị có hướng, Đa đồ thị có hướng. 1.1.2. Một số thuật ngữ cơ bản Bậc của đỉnh Bậc của đỉnh v trong đồ thị G = (V, E) ký hiệu deg(v) là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của 4 nó. Trong đồ thị có hướng, bậc của đỉnh v được chia ra thành bậc trong (số lượng các cạnh được nối tới đỉnh v, kí hiệu là deg+(v)) và bậc ngoài (số lượng các cạnh được nối từ đỉnh v, kí hiệu là deg-(v)). Đường đi và chu trình, đồ thị liên thông Trong đồ thị vô hướng, đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương trên đồ thị vô hướng G = (V, E) là dãy x0, x1, …, xn-1, xn | u = x0, v = xn, (xi, xi+1) ∈ E, i = 0, 1, ..., n-1 hoặc dãy các cạnh: (x0, x1), (x1, x2), ..., (xn-1, xn) Đỉnh u gọi là đỉnh đầu, đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp [1]. Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó. 1.1.3. Biểu diễn đồ thị Trong phần này, luận văn sẽ giới thiệu bốn cấu trúc dữ liệu chính để biểu diễn một đồ thị. Trong mỗi cấu trúc, phần biểu diễn các đỉnh được giữ nguyên, tuy nhiên phần biểu diễn các cạnh lại hoàn toàn khác nhau. Đồ thị ở Hình 1.7 sử dụng cho toàn bộ ví dụ trong phần 1.1.3 này. Hình 1.7: Đồ thị có hướng Danh sách cạnh (Edge list) Trong biểu diễn đồ thị theo danh sách các cạnh, tất cả các cạnh e thuộc E đều được lưu dưới dạng hai phần tử (vi, vj) trong danh sách lưu trữ. Danh sách kề (Adjacency list) Trong biểu diễn đồ thị bằng danh sách kề, với mỗi đỉnh u, ta lưu trữ tất cả các đỉnh v kề với nó. 5 Ma trận liên thuộc (Incidence matrix) Ma trận liên thuộc đỉnh – cạnh của đồ thị G = (V, E) là một đồ thị |V| x |E|, trong đó phần tử ở hàng thứ i và cột thứ j bằng 1 khi và chỉ i là đỉnh đầu của cung thứ j, bằng -1 khi và chỉ khi i là đỉnh cuối của cung thứ j và bằng 0 trong trường hợp còn lại. Ma trận kề (Adjaceny matrix) Ma trận kề của đồ thị G = (V, E) là một đồ thị |V| x |V|, trong đó phần tử ở hàng thứ i và cột thứ j bằng 1 khi và chỉ khi tồn tại cung (i, j) trong đồ thị, bằng 0 trong trường hợp ngược lại. Một số thống kê về độ phức tạp một số phương phức cơ bản được trình bày ở Bảng 1.1. Giả sử n: số đỉnh, m: số cạnh, dv: bậc của đỉnh v. Bảng 1.1: Một số thống kê về độ phức tạp một số phương phức cơ bản trong đồ thị [9] Phương thức Danh sách Danh sách Ma trận Ma trận kề cạnh kề liên thuộc numVertices( ) Trả về số lượng đỉnh của đồ thị. O(1) O(1) O(1) O(1) O(1) O(1) O(1) O(1) O(n) O(n) O(n) O(n) O(m) O(m) O(m) O(m) O(m) O(min(du , dv)) O(m) O(1) numVertices( ) Trả về số lượng cạnh của đồ thị. vertices( ) Trả về phép duyệt tất cả các đỉnh của đồ thị. edges( ) Trả về phép duyệt tất cả các cạnh của đồ thị. getEdge(u, v) Kiểm tra xem cạnh (u, v) có tồn tại không? 6 outDegree(v) inDegree(v) Trả về số lượng đỉnh vào và đỉnh ra của nốt v. O(m) O(1) O(m) O(n) O(m) O(dv ) O(m) O(n) O(1) O(1) O(m×n) O(n2) O(m) O(dv) O(m×n) O(n2) O(1) O(1) O(1) O(1) O(1) O(1) O(1) O(1) Θ(n) Θ(m+n) Θ(m×n) Θ(n2) outgoingEdges(v) incomingEdges(v) Trả về phép duyệt tất cả đỉnh vào và đỉnh ra của nốt v. insertVertex(x) Thêm một đỉnh mới vào đồ thị. removeVertex(v) Xóa một đỉnh trong đồ thị. insertEdge(u, v) Thêm một cạnh mới vào đồ thị. removeEdge(u, v) Xóa một cạnh trong đồ thị. Không gian lưu trữ 1.1.4. Các thuật toán tìm kiếm trên đồ thị và ứng dụng Trong đồ thị, bài toán duyệt qua tất cả các đỉnh của đồ thị sao cho mỗi đỉnh chỉ thăm đúng duy nhất một lần là một bài toán quan trọng thu hút sự quan tâm nghiên cứu của rất nhiều các nhà khoa học. Trong mục này, luận văn sẽ trình bày hai thuật toán duyệt đồ thị cơ bản: thuật toán tìm kiếm theo chiều sâu (Depth First Search – DFS) và thuật toán tìm kiếm theo chiều rộng (Breadth First Seach – BSF). Hai thuật toán cơ bản này làm cơ sở để giải quyết một số bài toán quan trọng trong lý thuyết đồ thị. 7 1.2. Bài toán tìm đường đi ngắn nhất Trong các ứng dụng thực tế, bài toán tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị có một ý nghĩa to lớn. Ví dụ, bài toán tìm đường đi ngắn nhất giữa hai điểm trên bản đồ (có thể ngắn nhất về thời gian, hoặc về khoảng cách…). Hiện nay, có rất nhiều phương pháp để giải quyết các bài toán như vậy nhưng thông thường, các thuật toán được xây dựng trên cơ sở lý thuyết đồ thị dường như cho hiệu quả cao nhất. Trong phần này luận văn sẽ đề cập đến một số bài toán tìm đường đi ngắn nhất cơ bản. Bài toán tìm đường đi ngắn nhất sẽ được áp dụng cho đồ thị G = (V, E) có hướng, có trọng số với trọng số là hàm w: Ε ⟹ % ánh xạ cạnh với một giá trị thực. Khi đó, chi phí w(p) của đường đi p = (v0, v1, …, vk) chính là tổng trọng số của từng cạnh kết hợp thành đường đi này. / & ' = & *+,- , *+ +0- Tổng quát có thể phát biểu: tìm đường đi ngắn nhất xuất phát từ đỉnh đầu s đến đỉnh cuối t, (s,t ∈ V). Độ dài của đường đi ký hiệu là d(s,t) (khoảng cách từ s đến t). Nếu như không tồn tại đường đi từ s tới t thì d(s,t)=∞. Vấn đề tìm đường đi ngắn nhất trong đồ thị có các bài toán cơ bản: tìm đường đi ngắn nhất xuất phát từ một đỉnh và tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh. Phần lớn các thuật toán tìm khoảng cách này được xây dựng nhờ kỹ thuật tính toán từ ma trận trọng số w[u, v], u,v ∈ V, cận trên d[v] của khoảng cách từ s đến tất cả các đỉnh v ∈ V được tính. Mỗi khi biểu thức sau thỏa mãn d[u] + w[u, v] < d[v] thì ta sẽ gán d[v] = d[u] + w[u, v]. Quá trình này cứ tiếp tục cho đến khi tất cả các đỉnh kề với các cạnh trên mỗi bước đi đã được duyệt. Kết quả d[v] chính là khoảng cách ngắn nhất giữa s và t. Sau đây, luận văn sẽ trình bày chi tiết các thuật toán tìm đường đi ngắn nhất BELLMAN-FORD, DIJKSTRA’S, FLOYDWARSHALL, BFS, BBFS. 1.3. Tổng kết chương Chương 1 đã trình bày về các vấn đề tổng quát của đồ thị, một số thuật ngữ cơ bản trong đồ thị, đường đi và chu trình, đồ thị liên thông, biểu diễn đồ thị trong máy tính, các thuật toán tìm kiếm trên đồ thị và ứng dụng. Phần cuối chương, luận văn đề cập đến bài toán tìm đường đi ngắn nhất và các giải thuật cơ bản để giải quyết bài toán này. Điều này làm cơ sở để tiếp cận và giải quyết bài toán được trình bày trong chương tiếp theo. 8 Chương 2. Bài toán, cách tiếp cận và phương pháp giải quyết Trong phần này luận văn sẽ trình bày chi tiết về bài toán, cách tiếp cận bài toán và đi sâu vào hướng giải quyết của bài toán. 2.1. Định nghĩa bài toán Tổng quát Mục tiêu của bài toán là trả lời các truy vấn tìm đường đi ngắn nhất trên đơn đồ thị, động, có hướng và không trọng số, với quy mô dữ liệu lớn nhanh nhất có thể. Sự động (thay đổi) của đồ thị có nghĩa là có các sự kiện thay đổi dữ liệu cấu trúc trong đồ thị, cụ thể là hai sự kiện thêm cạnh (Addition) và xóa cạnh (Deletion). Từ đó, có tất cả ba sự kiện có thể xảy ra trong đồ thị được miêu tả cụ thể dưới đây: Sự kiện 1: [Query: u v (Q u v)]: Sự kiện này truy vấn khoảng cách ngắn nhất từ đỉnh u đến đỉnh v. Nếu không có đường đi giữa hai đỉnh này hoặc không tồn tại đỉnh u hay v trong đồ thị thì kết quả trả về là -1. Khoảng cách từ một đỉnh tới chính nó là 0. Sự kiện 2: [‘A’/add: u v (A u v)]: Sự kiện này mô tả sự thay đổi trong đồ thị khi thêm một cạnh mới từ đỉnh u đến đỉnh v. Nếu cạnh đã tồn tại, đồ thị không thay đổi. Nếu một hoặc cả hai đỉnh trong cạnh được thêm chưa có thì nó phải được thêm vào đồ thị. Sự kiện 3: [‘D’/delete: u v (D u v)]: Sự kiện này mô tả sự thay đổi trong đồ thị khi xóa một cạnh nối từ đỉnh u đến đỉnh v. Nếu cạnh này không tồn tại, đồ thị không thay đổi. Dữ liệu vào ban đầu Dữ liệu vào ban đầu được biểu diễn dưới dạng danh sách các cạnh, mỗi cạnh bao gồm một cặp hai định danh của hai đỉnh (đỉnh bắt đầu và đỉnh kết thúc của cạnh). Định danh này được biểu thị bằng một số nguyên dương. Định danh lớn nhất có thể biểu diễn là 232-1. Đầu vào của chương trình là các dòng biểu diễn cạnh của đồ thị, mỗi dòng chứa chính xác hai số nguyên dương theo định dạng chuẩn ASCII được ngăn cách nhau bởi một dấu cách. Kí tự ‘S’ ở dòng cuối cùng sẽ báo hiệu sẽ kết thúc quá trình nhập dữ liệu đồ thị. Ví dụ: trong Hình 2.1, dữ liệu đầu vào bên trái biểu diễn đồ thị ở bên phải. 9 Hình 2.1: Dữ liệu đầu vào Truy vấn và kết quả đầu ra Mỗi bộ dữ liệu kiểm tra được chia ra thành các lô, mỗi lô bao gồm một tập các sự kiện, mỗi sự kiện trên một dòng riêng biệt. Dòng cuối cùng của một lô sẽ chỉ có ký tự ‘F’ để báo hiệu kết thúc lô. Mỗi một sự kiện được biểu diễn bởi một kí tự (‘Q’, ‘A’, ‘D’) đã được định nghĩa ở trên, theo sau là hai số nguyên dương chuẩn ASCII cách nhau bởi một dấu cách. Hai số nguyên dương chính là định danh của một đỉnh. Kết quả truy vấn sẽ phải trả về theo đúng thứ tự truy vấn của lô. Hình 2.2 là một ví dụ về lô dữ liệu kiểm thử được. Hình 2.2: Lô dữ liệu kiểm thử 2.2. Các vấn đề liên quan Để thực hiện các sự kiện thêm, xóa cạnh và truy vấn tìm đường ngắn nhất trên đồ thị, hiện có rất nhiều công cụ và thư viện cho phép chúng ta làm điều đó. Ví dụ, gói NetworkX của ngôn ngữ lập trình Python là một bộ công cụ được tạo ra để xử lý, thao tác với đồ thị và mạng lưới phức tạp [12]. Hay Stanford Network Analysis Platform (SNAP) [20] là bộ công cụ có hiệu năng cao trong việc phân tích, xử lý, thao tác với đồ thị lớn. Các thư viện này cài đặt một số thuật toán tìm khoảng cách ngắn nhất giữa hai đỉnh. Một trong những chiến lược hiệu quả nhất để tìm khoảng cách ngắn nhất giữa hai đỉnh là tìm kiếm từ hai hướng theo ý tưởng duyệt đồ thị theo chiều rộng (BFS). Tuy nhiên, phần cài đặt của các thư viện này chưa được tối ưu vì phần tìm kiếm chỉ xử lý tuần tự và việc lựa chọn hướng đi tiếp theo chỉ dựa trên số lượng các đỉnh trong danh sách hàng đợi. Trong tối ưu hóa đồ thị dữ liệu lớn, GraphLab [22], PowerGraph [9], GraphX [10] là một trong các công cụ được đánh giá cao khi xử lý dữ liệu 10 cả về vấn đề phân tán và vấn đề tính toán song song. Tuy nhiên, giống như NetworkX và SNAP C++, chúng không thích hợp cho bài toán tìm đường đi ngắn nhất giữa hai điểm trong đồ thị thay đổi, trong trường hợp rất nhiều cạnh và đỉnh liên tục được thêm vào và xóa đi. Liên quan đến đồ thị thay đổi, rất nhiều các nhà nghiên cứu đã chú trọng đến vấn đề này [15] [19] [21] cho thấy khối lượng công việc đối với bài toán tìm đường đi ngắn nhất là rất lớn. Để áp dụng sức mạnh của xử lý đa luồng [2] [3] [13] [14], miêu tả cấu trúc phù hợp song song hóa thuật toán duyệt đồ thị theo chiều rộng trên đồ thị lớn. Nhưng các hành động thêm cạnh hay xóa cạnh vẫn chưa được chú ý trong các hệ thống này. Các thư viện xử lý song song trong ngôn ngữ lập trình C/C++. OpenMP Hình 2.3: Giới thiệu về OpenMP Pthread (POSIX Thread) Hình 2.4: Giới thiệu về Pthread Intel Cilk Plus Hình 2.5: Song song hóa truy vấn bởi Cilk Plus 11 2.3. Cách tiếp cận giải quyết bài toán Để giải quyết bài toán này, bước đầu tiên chúng ta phải đi tìm một cấu trúc dữ liệu để biểu diễn đồ thị trong máy tính. Sau khi tìm được cấu trúc dữ liệu phù hợp, chúng ta phải tìm các phương pháp để ba phép toán tìm khoảng cách ngắn nhất, thêm cạnh, xóa cạnh chạy nhanh nhất có thể. Cuối cùng, dựa vào công nghệ đa luồng trên máy tính có nhiều chíp xử lý, chúng ta có thể tận dụng để song song hóa quá trình tìm đường đi ngắn nhất của các truy vấn liên tiếp nhau. Chi tiết về phương pháp giải quyết bài toán được trình bày trong các phần tiếp theo. 2.4. Cấu trúc dữ liệu phù hợp Hiện nay, việc xử lý lệnh bên trong một CPU nhanh hơn rất nhiều khi so sánh với việc lấy dữ liệu từ trong bộ nhớ chính. Dựa trên kiến trúc bộ nhớ đệm của CPU, khi một chương trình xử lý dữ liệu lớn, dữ liệu được tổ chức liên tiếp dường như là cách tốt nhất để tăng tỉ lệ cache hit. Bảng 2.1: Độ trễ trong bộ nhớ 2016 Thời gian (ns) L1 cache 0.5 Branch mispredict 4 Mutex lock/unlock 17 Main reference 100 >2 ALU instruction latency 3 L2 cache reference Ghi chú memory 8 x L1 cache 25xL2 cache, 200xL1 cache Trong đồ thị, cách đơn giản và thuận tiện nhất để biểu diễn các đỉnh của đồ thị là định nghĩa nó dưới dạng một số nguyên dương. Do vậy, nếu đồ thị có |V| đỉnh thì các đỉnh của nó sẽ có định danh từ 0 đến |V| - 1. Trong 4 phương pháp được trình bày ở phần 1.1.3, danh sách kề là cách thích hợp nhất để biểu diễn đồ thị động quy mô lớn bởi không gian lưu trữ tương đối nhỏ Θ(|V| + |E|) và thuận tiện để thêm hoặc xóa đỉnh, cạnh. Với danh sách kề đồ thị có thể được biểu diễn theo hai cách sau: Danh sách kề các đỉnh vào của đồ thị Đồ thị sẽ được biểu diễn bởi một danh sách các đỉnh vào của các nốt liên tiếp nhau (incoming_edges) và một mảng chỉ số vào (incoming_index) để có thể lấy được danh sách các đỉnh vào của một nốt. 12 Danh sách kề các đỉnh ra của đồ thị Tương tự như danh sách kề các đỉnh vào của đồ thị, đồ thị sẽ được biểu diễn bởi một danh sách các đỉnh ra của các nốt liên tiếp nhau (outgoing_edges) và một mảng chỉ số ra (outgoing_index) để có thể lấy được danh sách các đỉnh ra của một nốt. Hình 2.6: Cấu trúc dữ liệu của đồ thị Cụ thể, đồ thị G sẽ được biểu diễn bởi các mảng incoming_edges, incoming_index, outgoing_edges, outgoing_index. Nhờ vào việc sử dụng danh sách các đỉnh vào và đỉnh ra của từng nốt, chúng ta có thể duyệt đồ thị từ cả hai phía (Bi-directional BFS). 2.5. Tối ưu quá trình thêm và xóa cạnh của đồ thị 2.5.1. Thêm mới một cạnh Vấn đề đặt ra là làm thế nào một cạnh có thể được thêm vào đồ thị với thời gian nhanh nhất. Khi sử dụng danh sách liền kề truyền thống để biểu diễn đồ thị, các chiến lược có thể dùng để thêm mới một cạnh như sau. Chèn vào giữa mảng Trước khi thêm cạnh mới vào đồ thị, vị trí các phần tử của đỉnh vào/ra của một nốt được xác định. Tất cả các phần tử đỉnh vào/ra của các nốt kế tiếp sẽ được dịch sang phải một ví trị để dành vị trí trống cho đỉnh vào/ra của cạnh mới được thêm vào. Quá trình này được miêu tả trong Hình 2.7. Hình 2.7: Thêm một cạnh bằng cách chèn vào giữa mảng 13 Thực tế cho thấy rằng, phương pháp này chỉ thích hợp với những đồ thị có kích thước nhỏ. Vì khi dữ liệu đồ thị rất lớn, số cạnh lên đến hàng triệu, số lượng đỉnh ra và đỉnh vào rất nhiều, chi phí để di chuyển tất cả các phần tử của các nốt kế tiếp sang phải một vị trí là không nhỏ. Cấp phát trước một khoảng trống Để giảm bớt chi phí di chuyển tất các phần tử các nốt kế tiếp sang phải một vị trí mỗi khi thêm một đỉnh vào/ra, một khoảng trống giữa các đỉnh vào/ra của các nốt được cấp phát trước. Điều này cho phép tối ưu quá trình thêm cạnh. Quá trình này được miêu tả trong Hình 2.8 và Hình 2.9. Hình 2.8: Cấu trúc dữ liệu danh sách kề cấp phát trước khoảng trống Hình 2.9: Thêm một cạnh bằng cách cấp trước khoảng trống Tuy nhiên, mảng danh sách cạnh liền kề biểu diễn đồ thị sẽ bị hổng rất nhiều, dẫn đến tăng tỉ lệ cache miss trong khi duyệt đồ thị. Di chuyển phần tử xuống cuối mảng Hình 2.10: Quá trình thêm một cạnh 14 Trước khi thêm vào một đỉnh vào/ra của một nốt, tất cả các phần tử của nốt đó được chuyển xuống cuối mảng, sau đó mới thêm đỉnh mới. Quá trình này được miêu tả trong Hình 2.10. Đối với bài toán cụ thể này, phương án 3 "Di chuyển phần tử xuống cuối mảng" sẽ cho kết quả tốt hơn phương án 2 "Cấp phát trước một khoảng trống". Bởi vì đối với cấu trúc dữ liệu các đỉnh được sắp xếp liền kề, phương án 3 sẽ cho phép các đỉnh nằm ở vị trí liên tiếp nhau nhiều hơn, trong khi đó phương án 2 sẽ cho nhiều khoảng trống hơn giữa các đỉnh. Dựa vào phân tích tối ưu ở phần trên, phương án 3 sẽ cho tỉ lệ cache miss ít hơn, do đó tăng được hiệu năng hệ thống. Và cuối cùng, phương án 3 được lựa chọn để sử dụng trong quá trình thêm mới một cạnh. 2.5.2. Xóa đi một cạnh Dựa trên cấu trúc đồ thị trên, chỉ cần thay đổi giá trị số lượng đỉnh vào/ra trong mảng chỉ số incoming_index /outgoing_index và xóa đi đỉnh nối trong mảng danh sách đỉnh vào/ra. Quá trình này được miêu tả trong Hình 2.11 Hình 2.11: Quá trình xóa một cạnh 2.6. Tối ưu quá trình xử lý truy vấn tìm đường đi ngắn nhất Trong quá trình xử lý truy vấn tìm đường đi ngắn nhất, thuật toán duyệt đồ thị theo chiều rộng được sử dụng. Thuật toán này được xem như là phương pháp tối ưu đối với đồ thị quy mô lớn, có hướng, có/không trọng số [3] [11]. Một điểm cần chú ý nữa là với thuật toán này là khả năng song song hóa chạy được trên nhiều luồng, nhiều CPU. Bởi vậy, chiến lược để giải quyết bài toán là xử lý song song các truy vấn liên tiếp. Chiến lược này được giải thích chi tiết dưới đây. 15 2.6.1. Cải thiện thuật toán tìm đường đi ngắn nhất từ hai hướng Thuật toán duyệt đồ thị theo chiều rộng được sử dụng với quá trình duyệt từ hai hướng (đỉnh đầu và đỉnh kết thúc) bởi sử dụng cả hai mảng đỉnh vào (incoming_array) và đỉnh ra (outgoing_array). Dự đoán hướng đi ở mỗi lần lặp Trong thuật toán duyệt đồ thị theo chiều rộng từ hai hướng bình thường, nhánh có số lượng đỉnh trong hàng đợi ít hơn sẽ được duyệt ưu tiên. Ví dụ như Hình 2.12, chúng ta cần tìm đường đi ngắn nhất giữa đỉnh 1 và đỉnh 9. Khi sử dụng thuật toán cơ bản, tổng cộng 1 + 2 + 6 = 9 đỉnh phải cho và danh sách hàng đợi duyệt. Thay vì duyệt theo hướng đỉnh ra, chúng ta duyệt theo hướng đỉnh vào. Khi đó, số lượng đỉnh cần phải cho vào danh sách hàng đợi duyệt chỉ còn lại 1 + 2 = 3. Do vậy, chúng ta không chỉ so sánh tổng số đỉnh vào và đỉnh ra tại mức 1, mà so sánh với cả mức thứ 2. Điều này sẽ giảm thiểu thời gian tìm đường đi ngắn nhất. Hình 2.12: Thứ tự duyệt đỉnh trong thuật toán duyệt đồ thị theo chiều rộng từ hai hướng 2.6.2. Song song hóa truy vấn tìm đường đi ngắn nhất Cilk Plus được sử dụng cho quá trình song song hóa. Trong quá trình thực hiện, OpenMP và Pthread cũng đượ thử nghiệm. Tuy nhiên, đối với bài toán cụ thể được trình bày trong luận văn này, Cilk Plus cho kết quả tốt nhất. Cilk Plus thực hiện quá trình song song hóa theo Hình 2.5. 2.7. Tổng kết chương Chương 2 đã trình bày chi tiết về bài toán cần giải quyết cũng như các vấn đề liên quan đến bài toán. Phần tiếp theo luận văn trình bày cách tiếp cận giải quyết bài toán và phương pháp giải quyết bài toán dựa trên cấu trúc dữ liệu, quá trình thêm, xóa cạnh và quá trình truy cấn tìm đường ngắn nhất. Dựa vào các phân tích ở chương 2, chương tiếp theo sẽ trình bày cụ thể về phương pháp cài đặt và kết quả thực nghiệm của giải thuật. 16 Chương 3. Thực nghiệm và đánh giá Để kiểm nghiệm phương pháp tìm đường đi ngắn nhất trong đồ thị động, quy mô lớn, thuật toán đã được sử dụng để tham gia cuộc thi lập trình ACM Sigmod năm 2016 (ACM Sigmod Programming Contest 2016) và được chọn là một trong năm đội xuất sắc nhất giải. Bên cạnh đó, các bộ dữ liệu lớn từ SNAP [5] cũng được dùng để đánh giá phương pháp này. 3.1. Cài đặt Ba sự kiện chính được cài đặt trong các hàm exec_queries, add_edge, del_edge. Chi tiết cài đặt được miêu tả trong Thủ tục 1 dưới đây. Thủ tục 1: Xử lý tổng hợp các sự kiện Để tích hợp quá trình song song hóa trong truy vấn tìm đường đi ngắn nhất, trước khi thêm mới một cạnh, tất cả truy vấn tìm đường đi ngắn nhất trong danh sách trước đó sẽ được thực hiện. Thủ tục để thêm mới một cạnh (u, v) vào đồ thị G được mô tả dưới đây. Thủ tục 2: Thêm mới một cạnh (u, v) vào đồ thị G Để tích hợp quá trình song song hóa trong tìm khoảng cách ngắn nhất, trước khi thực sự xóa cạnh, tất cả truy vấn tìm đường đi ngắn nhất trong danh sách trước đó sẽ được thực hiện. Thủ tục xóa cạnh (u, v) của đồ thị G được mô tả dưới đây. 17 Thủ tục 3: Xóa cạnh (u, v) của đồ thị G Thủ tục quan trọng nhất là tìm đường đi ngắn nhất giữa hai đỉnh (u, v) được mô tả cụ thể trong Thủ tục 4 dưới đây. Thủ tục 4: Tìm đường đi ngắn nhất giữa hai đỉnh (u, v) theo phương pháp duyệt đồ thị theo chiều rộng từ hai hướng cải tiến. 18 Sử dụng cách thức thao tác trực tiếp đến bit, dùng thứ tự bit để đánh dấu đỉnh trong đồ thị (đỉnh chưa xét thì giá trị bit=0, đỉnh đã xét thì giá trị bit=1) thay vì dùng mảng sẽ giảm không gian bộ nhớ và thơi gian thi hành. Hình 3.1: Thời gian thực thi giữa hai phép toán thao tác trên mảng và bit Cilk Plus được dùng để song song hóa các thủ tục tìm đường ngắn nhất. Thủ tục 5: Xử lý song song các truy vấn liên tiếp trong đồ thị G 3.2. Thực nghiệm 3.2.1. Cuộc thi ACM Sigmod Contest 2016 Trong cuộc thi này, 4 bộ dữ liệu đồ thị lớn được dùng để đánh giá các giải pháp của các đội. Mỗi bộ bao gồm một tập các quá trình thêm cạnh, xóa cạnh, truy vấn tìm đường đi ngắn nhất liên tục. Bảng 3.1 thống kê chi tiết các thông số trong bộ dữ liệu kiểm tra của ACM Sigmod. Bảng 3.1:Thống kê bộ dữ liệu ACM Sigmod Thông số Small Medium X-Large XX-Large Đỉnh 1574074 2000000 1971281 6009555 Cạnh 3232855 5000000 5533214 16518948 Bậc trong lớn nhất 114557 90412 12 779 Bậc ngoài lớn nhất 114125 356364 12 770 Cấu hình máy kiểm nghiệm của ban tổ chức 19