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

[v] = w[s,v]; truoc[v] = s; d[s] = 0; T = V \ {s}; while T # ∅ do tìm đỉnh u ∈ T thỏa mãn d[u] = min { d[z] : z ∈ T}; T = T \ {u}; for v ∈ T do if d[v] > d[u] + w[u,v] then d[v] = d[u] + w[u,v]; truoc[v] = u; } Thuật toán Dijkstra’s tìm được đường đi ngắn nhất trên đồ thị sau thời gian cỡ O(n2) [1]. FLOYD-WARSHALL Đầu vào: Đồ thị có hướng G = (V, E) với n đỉnh. Ma trận trọng số w[i,j], i,j = 1,2,...,n Đầu ra: Ma trận đường đi ngắn nhất giữa các cặp đỉnh d[i,j], i,j = 1,2,...,n Trong đó d[i,j] cho độ dài đường đi ngắn nhất từ i đến j. Ma trận ghi nhận đường đi p[i,j] i,j = 1,2,...,n Trong đó p[i,j] ghi nhận đỉnh đi trước đỉnh j trong đường đi ngắn nhất từ i đến j. Floyd-Warshall(){ for i = 1 to n do for j = 1 to n do 24 d[i,j] = a[i,j]; p[i,j] = i; for k = 1 to n do for i = 1 to n do for j = 1 to n do if d[i,j] > d[i,k] + d[k,j] d[i,j] = d[i,k] + d[k,j]; p[i,j] = p[k,j]; } Dễ thấy thuật toán Floyd-Warshall có độ phức tạp là O(n3) [1]. Ba thuật toán Bellman-Ford, Dijkstra’s và Floyd-Warshall dùng để tìm đường đi ngắn nhất trong đồ thị G = (V, E) có hướng, có trọng số. Tuy nhiên, trong thực tế, ví dụ như mạng xã hội, bài toán tìm đường đi ngắn nhất cơ bản là tìm số lượng đỉnh trung gian ít nhất để kết nối hai đỉnh. Khi đó đồ thị G = (V, E) có hướng, có trọng số trở thành đồ thị có hướng, không trọng số, hay tất cả trọng số của các cạnh đều là 1. Để giải quyết bài toán này, thuật toán duyệt đồ thị theo chiều rộng đã được giới thiệu ở mục 1.1.4 được cho là hiệu quả nhất, hai thuật toán Bellman-Ford và Dijkstra’s cùng sử dụng ý tưởng của BFS duyệt các đỉnh kề với nốt để tìm được đường đi ngắn nhất. Thuật toán tìm đường đi ngắn nhất dựa vào duyệt đồ thị theo chiều rộng được trình bày chi tiết dưới đây. BFS Đầu vào: Đồ thị có hướng G = (V, E) với n đỉnh. s ∈ V: đỉnh xuất phát t ∈ V: đỉnh kết thúc Đầu ra: Khoảng cách từ đỉnh s đến đỉnh t BFS(){ if s == t return 0; QUEUE = ∅; 25 for v ∈ V do check[v] = FALSE; d(s) = 0; QUEUE <= s; //Đưa s vào hàng đợi check[s] = TRUE; While QUEUE # ∅ do { p <= QUEUE; //Lấy p từ QUEUE for u ∈ neighbor (p) do if (check[u] == FALSE) QUEUE <= u; //Đưa u vào hàng đợi d(u) = d(p) + 1; if u == t return d(u); } return -1; } Trường hợp xấu nhất thuật toán phải duyệt hết tất cả các đỉnh của đồ thị thông qua các cạnh kề, như vậy độ phức tạp thuật toán BFS là O(n + m). Với thuật toán BFS, các đỉnh kề lần lượt được duyệt từ đỉnh bắt đầu s cho đến khi nào tìm được đỉnh t. Một cải tiến của thuật toán BFS là chúng ta có thể bắt đầu từ hai hướng (BBFS – Bi-directional BFS) (bắt đầu duyệt từ cả đỉnh vào và đỉnh ra). Khi đó, tại mỗi bước chúng ta kiểm tra xem số lượng đỉnh nằm trong hàng đợi đỉnh vào hay đỉnh ra nhỏ hơn để quyết định hướng tiếp theo. Theo lý thuyết, bước kiểm tra này sẽ làm giảm số lượng các đỉnh cần duyệt, do đó sẽ làm giảm thời gian thi hành của thuật toán. Hơn nữa, chúng ta có thể kết hợp với quá trình song song hóa duyệt theo cả hai hướng từ đỉnh vào và đỉnh ra một lúc. Điều này cũng làm giảm thời gian thi hành thuật toán. Chi tiết thuật toán BBFS được cài đặt dưới đây. BBFS Đầu vào: Đồ thị có hướng G = (V, E) với n đỉnh. s ∈ V: đỉnh xuất phát 26 t ∈ V: đỉnh kết thúc Đầu ra: Khoảng cách từ đỉnh s đến đỉnh t BBFS(){ if s == t return 0; QUEUE_OUT = ∅; QUEUE_IN = ∅; for v ∈ V do check_in[v] = FALSE; check_out[v] = FALSE; d_out(s) = 0; d_in(t) = 0; QUEUE_OUT <= s; //Đưa s vào hàng đợi các đỉnh ra QUEUE_IN <= t; //Đưa t vào hàng đợi các đỉnh vào check_in[s] = TRUE; check_in[t] = TRUE; While QUEUE_ OUT # ∅ OR QUEUE_IN # ∅ do { if (length(QUEUE_ OUT) < length(QUEUE_IN) { p <= QUEUE_OUT; //Lấy p từ QUEUE_OUT for u ∈ neighbor (p) do if (check_out[u] == FALSE) { QUEUE_OUT <= u; //Đưa u vào hàng đợi đỉnh ra d_out(u) = d_out(p) + 1; if (check_in[u] == TRUE) { return d_out[u] + d_in[u]; } if u == t return d_out(u); } 27 } else { p <= QUEUE_IN; //Lấy p từ QUEUE_IN for u ∈ neighbor (p) do if (check_in[u] == FALSE) QUEUE_IN <= u; //Đưa u vào hàng đợi đỉnh vào d_in(u) = d_in(p) + 1; if (check_out[u] == TRUE) { return d_out[u] + d_in[u]; } if u == s return d_in(u); } } return -1; } Trường hợp xấu nhất thuật toán phải duyệt hết tất cả các đỉnh của đồ thị thông qua các cạnh kề, như vậy độ phức tạp thuật toán BBFS là O(n + m). 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 cùng của 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. 28 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 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 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 (operation) có thể xảy ra trong đồ thị được miêu tả cụ thể dưới đây: Sự kiện 1: [‘Q’/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. Để kiểm tra kết quả mô hình này, luận văn sử dụng các bộ dữ liệu kiểm tra từ cuộc thi lập trình ACM Sigmod (ACM Sigmod Programming Contest) 2016 [6]. Cấu trúc của các bộ dữ liệu này được miêu tả chi tiết dưới đây. 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ể 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ị. 29 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. 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 theo định dạng chuẩn ASCII cách nhau bởi một dấu cách. Giữa kí tự và mỗi số nguyên dương cũng có một dấu cách để ngăn 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. Dễ dàng thấy, lô 1 có 3 truy vấn Q, như vậy kết quả sẽ cho 3 số trên 3 dòng tương ứng với từng truy vấn Q. Tương tự như vậy, kết quả trả về của lô thứ 2 sẽ là 2 số trên 2 dòng tương ứng với 2 truy vấn Q. 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 đường đi 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]. Trong NetworkX, nốt có thể là bất cứ đối tượng nào trong Python, cạnh có thể chứa dữ liệu tùy ý. NetworkX cũng cung cấp các lớp của đối tượng đồ thị, công cụ sinh để tạo ra đồ thị chuẩn, chương trình vào ra để đọc dữ liệu trong cơ sở dữ liệu, thuật toán để 30 phân tích đồ thị và một số công cụ hiển thị đồ thị cơ bản. Phần lớn giao diện lập trình ứng dụng của NetworkX được cung cấp dưới dạng các hàm, thủ tục với tham số đầu vào là đồ thị. Mã nguồn của mỗi mô đun rất dễ để đọc và đọc mã nguồn trên ngôn ngữ lập trình Python là cách tốt nhất để hiểu sâu hơn về thuật toán được sử dụng trong NetworkX. Bên cạnh đó, với hệ thống tài liệu hướng dẫn sử dụng, tài liệu chương trình rất cụ thể và thân thiện, tất cả mọi người đều có thể dễ dàng tìm hiểu công cụ NetworkX này [16]. Tương tự như NetworkX, Stanford Network Analysis Platform (SNAP) 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 mạng dữ liệu lớn [20]. SNAP có thể xử lý mạng dữ liệu lớn lên đến hàng trăm triệu cạnh và hàng tỉ đỉnh. SNAP cung cấp hơn 140 thuật toán khác nhau để có thể thao tác hiệu quả với đồ thị dữ liệu lớn, tính toán đặc tính cấu trúc, khởi tạo đồ thị ngẫu nhiên, và xử lý các thuộc tính của đỉnh, cạnh dưới dạng mã nguồn mở C++ hoặc python. Bên cạnh khả năng làm việc với dữ liệu lớn, một điểm mạnh nữa của SNAP là các nốt, cạnh hay các thuộc tính của đồ thị có thể dễ dàng thay đổi trong quá trình tính toán. Điều này rất hữu ích đối với quá trình thêm/xóa cạnh liên tục trong đồ thị dữ liệu lớn đã được trình bày ở phần trên SNAP. Các thư viện này cài đặt rất nhiều thuật toán để có thể tìm được 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 này 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ì những lý do như sau. Thứ nhất, đường đi ngắn nhất chỉ được tìm kiếm theo tuần tự (xử lý trên một chip), và việc lựa chọn hướng đi tiếp theo trong phần tìm kiếm theo hai hướng chỉ dựa trên số lượng các đỉnh trong danh sách hàng đợi. Việc này sẽ khiến thuật toán mất thêm rất nhiều thời gian để duyệt qua các đỉnh tiếp theo trong hàng đợi này. Trong tối ưu hóa đồ thị dữ liệu lớn, GraphLab [22], PowerGraph [9], GraphX [10] là các công cụ được đánh giá cao khi xử lý dữ liệu trong đồ thị lớn cả về vấn đề phân tán và vấn đề tính toán song song. Những hệ thống này sẽ đạt được hiệu quả tốt nhất khi được cài đặt trên các siêu máy tính, các cụm máy chủ lớn. 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 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 cần phải xử lý đối với bài toán tìm đường đi ngắn nhất trên biểu đồ vận tải thay đổi liên tục. Để áp dụng sức 31 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 cuối cùng, các hành động thêm cạnh hay xóa cạnh vẫn chưa được chú ý đến trong các hệ thống này. Để có thể tận dụng được sức mạnh của hệ thống đa luồng, đa nhân, đa tiến trình trong các bộ vi xử lý hiện nay, có rất nhiều thư viện đã hỗ trợ việc này. Cụ thể, trong ngôn ngữ lập trình C/C++, một số thư viện nổi tiếng được trình bày dưới đây. OpenMP [17] OpenMP là một giao diện lập trình ứng dụng (API) được dùng để song song hóa quá trình đa luồng, chia sẻ bộ nhớ. OpenMP bao gồm 3 thành phần API chính: biên dịch trực tiếp, thư viện chạy chương trình và biến môi trường. Các mục đích của OpenMP như sau: - Chuẩn hóa o Cung cấp chuẩn giữa rất nhiều kiến trúc/nền tảng chia sẻ bộ nhớ. o Đã được định nghĩa và chứng thực bởi một nhóm các nhà phát triển phần cứng và phần mềm máy tính. - Mục tiêu o Xây dựng câu lệnh điều hướng đơn giản và hiệu quả cho các chương trình chia sẻ bộ nhớ trong máy tính. o Quá trình song song hóa có thể được cài đặt chỉ sau 3 hoặc 4 câu lệnh điều hướng. - Dễ dàng sử dụng o Cung cấp khả năng nâng cao song song hóa trong một chương trình tuần tự. o Cung cấp khả năng để thực hiện song song hóa trên cả chương trình đơn giản và chương trình phức tạp. - Dễ dàng tiếp cận o Sử dụng API cho ngôn ngữ lập trình C/C++ hoặc Fortran. o Diễn đàn công cộng cho người sử dụng. o Có thể cài đặt trên nền tảng Unix/Linux hoặc Windows. Hình 2.3: Giới thiệu về OpenMP 32 Pthread (POSIX Thread) [18] Thư viện Pthread được xây dựng trên chuẩn thread API dành cho C/C++. Nó cho phép một luồng có thể sinh thêm một luồng mới đồng thời với nó. Nó rất hiệu quả cho hệ thống đa nhân, nhiều chip xử lý, nơi mà các luồng có thể được lên lịch chạy trên một bộ vi xử lý khác để tận dụng lợi ích của xử lý song song và phân tán. Các luồng thường xử lý các công việc có khối lượng như nhau để tránh sự quá tải đối với một chíp xử lý. Mặc dù tận dụng được sự hiệu quả của hệ thống đa nhân, nhưng phương pháp này cũng khiến cho quá trình vào ra (I/O) của hệ thống có độ trễ lớn hơn hay một vài một vài chức năng hệ thống có thể bị tạm hoãn (một thread xử lý công việc, trong khi các thread khác phải đợi kết quả từ thread này). Lập trình song song ví dụ như MPI hay PVM được sử dụng trong môi trường phân tán, trong khi đó thread chỉ được sử dụng trong một máy tính riêng lẻ. Tất cả thread trong một tiến trình chia sẻ không gian địa chỉ giống nhau. Một thread được sinh ra bởi một thủ tục và các tham số của nó được dùng trong tiến trình thread mới. Mục đích cuối cùng của việc sử dụng thư viện thread này là để xử lý chương trình nhanh hơn. Thread bao bồm các phương thức khởi tạo, kết thúc, đồng bộ, lập lịch, quản lý dữ liệu và tương tác giữa các tiến trình. Một thread không duy trì danh sách thread nó tạo ra, cũng như không biết thread nào tạo ra nó. Tất cả thread trong một tiến trình chia sẻ không gian địa chỉ chung, cấu trúc tiến trình, dữ liệu, tín hiệu xử lý Mỗi thread có các thông số đặc trưng riêng sau: định danh thread, một tập các thanh ghi, con trỏ ngăn xếp, biến cục bộ, địa chỉ trả về, độ ưu tiên và giá trị trả về. Nếu thread được khởi tạo thành công thì giá trị trả về sẽ là 0. Hình 2.4: Giới thiệu về Pthread 33 Intel Cilk Plus [4] Đây là cách dễ nhất, nhanh nhất để khai thác sức mạnh của hệ thống máy tính đa nhân, đa CPU. Intel Cilk Plus là một thư viện mở rộng của C/C++ để song song hóa các tác vụ hoặc xử lý dữ liệu. Intel Cilk Plus có những đặc điểm chính sau đây: - Hiệu năng cao o Một quá trình xử lý hiệu quả dựa trên sự tối ưu hóa trong quá trình lập lịch các tác vụ song song. o Vector hỗ trợ sẽ được sử dụng để nâng cao hiệu năng, đây là vector được ẩn trong các bộ vi xử lý của chúng ta. o Các đối tượng tùy biến cao cho phép lập trình điều khiển các luồng rất hiệu quả. - Dễ dàng tìm hiểu o Chỉ 3 từ khóa được sử dụng để cài đặt song song hóa. o Cú pháp tuần tự hiểu hiểu và gỡ lỗi trong chương trình dễ dàng hơn. o Ký hiệu mảng (Array Notations) cung cấp cách thức biểu diễn dữ liệu song song theo một cách tự nhiên nhất. - Dễ dàng sử dụng o Tự động cân bằng tải cung cấp hiệu quả cao trong bài toán song song hóa. o Dễ dàng áp dụng song song với các thuật toán đã có. o Hỗ trợ chương trình viết bằng cả hai ngôn ngữ C hoặc C++. Hình 2.5: Song song hóa truy vấn bởi Cilk Plus 34 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. Cấu trúc dữ liệu phải đáp ứng mục đích cao nhất của bài toán là trả lại các kết quả truy vấn tìm khoảng cách ngắn nhất giữa hai đỉnh trong đồ thị nhanh nhất có thể cùng với ràng buộc về tài nguyên hệ thống. Điều đó đồng nghĩa với các phương thức thêm cạnh, xóa cạnh cũng phải thực hiện rất nhanh. 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 dựa 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. Trong cấu trúc của một bộ nhớ đệm, dữ liệu có thể được truy xuất ngay lập tức khi ở trong bộ nhớ đệm. Điều đó có nghĩa là, một khối bộ nhớ đệm có thể bao gồm 64/4 = 8 nốt. 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ệ nằm trong bộ nhớ (cache hit). Sự trễ này được miêu tả chi tiết trong Bảng 2.1. Bảng 2.1: Độ trễ trong bộ nhớ 2016 Thời gian (ns) Ghi chú L1 cache 0.5 >2 ALU instruction latency Branch mispredict 3 L2 cache reference 4 8 x L1 cache Mutex lock/unlock 17 Main memory reference 100 25x L2 cache, 200x L1 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. Để biểu diễn các đỉnh trong đồ thị trên máy tính, như đã trình bày ở mục 1.1.3, có 4 phương pháp chính 35 sau: danh sách cạnh, danh sách kề, ma trận liên thuộc và ma trận kề. Bởi vì quy mô đồ thị của chúng ta rất lớn, số lượng cạnh và đỉnh lên tới vài triệu, cùng với ràng buộc về tài nguyên hệ thống nên cách biểu diễn bởi ma trận liên thuộc hay ma trận kề không còn phù hợp (không gian lưu trữ cần thiết là Θ(|V| x |E|) và Θ(|V|2) tương ướng). Biểu diễn bằng danh sách cạnh tốn ít không gian lưu trữ nhất Θ(|E|) và đơn giản nhất, tuy nhiên, với cách biểu diễn quá trình tìm đường đi ngắn nhất cần duyệt tất cả các cạnh liền kề của một đỉnh sẽ mất thời gian khá lớn (O(m)). Do vậy, danh sách kề chính là cách thích hợp nhất để biểu diễn đồ thị quy mô lớn có nhiều thay đổi bởi vì 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. Trong đơn đồ thị có hướng, không trọng số, đồ thị có thể được biểu diễn theo hai danh sách kề như 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 trong truy vấn tìm đường ngắn nhất. Vị trí đỉnh vào đầu tiên của nốt N sẽ được lưu trữ tại vị trí N trong mảng chỉ số vào (inconming_index[N]). Thêm vào đó, giá trị số lượng đỉnh vào của một đỉnh cũng được lưu trữ để thuận tiện cho việc duyệt sau này. Để tăng tỉ lệ cache hit, giá trị số lượng đỉnh vào này cần được lưu trữ liền kề với vị trí đỉnh vào đầu tiên của một nốt. Cụ thể, một cặp (vị trí đỉnh vào đầu tiên, tổng số đỉnh vào) được lưu trữ trong mảng chỉ số vào incoming_index. Khi đó, chúng ta có thể lấy giá trị đỉnh vào đầu tiên và số lượng đỉnh vào của đỉnh N tại vị trí incoming_index[Nx2] và incoming_index[Nx2 + 1] tương ứng. Ví dụ: đồ thị ở Hình 2.1 được biểu diễn theo danh sách kề các đỉnh vào như sau: Incoming_edges: [3, 4, 1, 2, 2] Incoming_index: [(0,0), (0,2), (2,1), (3,1), (4,1)] 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 trong truy vấn tìm đường đi ngắn nhất. Vị trí đỉnh ra đầu tiên của nốt N sẽ được lưu trữ tại vị trí N trong mảng chỉ số ra (outgoing_index[N]). Thêm vào đó, giá trị số lượng đỉnh ra của một đỉnh cũng được lưu trữ để thuận tiện cho việc 36 duyệt sau này. Để tăng tỉ lệ cache hit, giá trị số lượng đỉnh ra này cần được lưu trữ liền kề với vị trí đỉnh ra đầu tiên của một nốt. Cụ thể, một cặp (vị trí đỉnh ra đầu tiên, tổng số đỉnh ra) được lưu trữ trong mảng chỉ số outgoing_index. Khi đó, chúng ta có thể lấy giá trị đỉnh ra đầu tiên và số lượng đỉnh ra của đỉnh N tại vị trí outgoing_index[Nx2] và outgoing_index[Nx2 + 1] tương ứng. Ví dụ: đồ thị ở Hình 2.1 được biểu diễn theo danh sách kề các đỉnh ra như sau: Outgoing_edges: [2, 3, 4, 1, 1] Outgoing_index: [(0,0), (0,1), (1,2), (3,1), (4,1)] Từ những ý tưởng nêu trên, đồ thị được mô hình hóa dữ liệu dưới dạng theo cấu trúc danh sách kề, được miêu tả cụ thể như sau: - Mỗi đỉnh được biểu diễn bởi một số nguyên dương. - Tất cả các đỉnh vào và đỉnh ra được tổ chức dưới dạng danh sách kề. - Một mảng lưu vị trí bắt đầu và số lượng đỉnh vào/đỉnh ra của mỗi 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 như sau: - incoming_edges, incoming_index là mảng gồm các phần tử nguyên 4 byte để lưu trữ thông tin liên quan đến các đỉnh vào của các nốt. incoming_edges lưu tất cả các đỉnh vào của các nốt, incoming_index lưu trữ vị trí bắt đầu và số lượng đỉnh vào của các nốt. - outgoing_edges, outgoing_index là mảng gồm các phần tử nguyên 4 byte để lưu trữ thông tin liên quan đến các đỉnh ra của các nốt. outgoing_edges lưu tất cả các đỉnh ra của các nốt, outgoing_index lưu trữ vị trí bắt đầu và số lượng đỉnh ra của các nốt. 37 Ví dụ ở Hình 2.6 mô tả đầu vào (input) bên trái sẽ cho cấu trúc dữ liệu theo danh sách kề các đỉnh vào ở bên phải. 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ị theo chiều rộng từ cả hai phía. Nó sẽ cho phép tính toán khoảng cách ngắn nhất giữa hai điểm dựa trên thuật toán duyệt đồ thị theo từ rộng từ cả hai phía (bi-directional BFS) [19] 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 ít nhất. Khi sử dụng danh sách kề truyền thống để biểu diễn đồ thị, các chiến lược có thể được dùng để thêm mới một cạnh như sau: Chèn vào giữa mảng Phương pháp này rất đơn giản, 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 (Thêm cạnh (2, 1) vào đồ thị). Hình 2.7: Thêm một cạnh bằng cách chèn vào giữa mảng 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ỏ khoảng vài nghìn 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ỏ. Do đó, phương pháp thứ hai dưới đây được áp dụng. 38 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, dựa trên phân tích ở mục 2.4 có thể thấy, phương pháp này không thực sự hiệu quả đối với đồ thị dữ liệu lớn. Vì khi đó, mảng danh sách cạnh liền kề biểu diễn đồ thị sẽ bị hổng rất nhiều, điều này dẫn đến tăng tỉ lệ cache miss trong khi duyệt đồ thị. Để cải thiện tỉ lệ cache miss này, chúng ta có thể giảm số lượng khoảng trống bằng cách giảm bớt không gian cấp phát trước. Ví dụ như sau mỗi khoảng đỉnh vào/ra của 32 nốt sẽ có không gian dành cho 8 nốt thêm mới được cấp phát trước. Điều đó có nghĩa là chúng ta có thể thêm tối đa 8 nốt trong mỗi khoảng đỉnh vào/ra của 32 nốt. Phương án này đã giảm được hạn chế rất nhiều, tuy nhiên, một phương án khác cho hiệu quả tốt hơn được trình bày tiếp theo sau đây. 39 Di chuyển phần tử xuống cuối mảng 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 (Hình 2.10). Hình 2.10: Quá trình thêm một cạnh Đối với bài toán trong luận văn, phương án 3 "Di chuyển phần tử xuống cuối mảng" 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 đố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 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, quá trình xóa một cạnh rất đơn giả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 (Xóa cạnh (3, 1)). Hình 2.11: Quá trình xóa một cạnh 40 2.6. Tối ưu quá trình xử lý truy vấn tìm đường 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, không trọng số [3] [13]. Một điểm cần chú ý nữa là với thuật toán này, 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. 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 Dự đoán hướng đi, số lượng các đỉnh ra/vào cần duyệt ở mức kế tiế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. Tuy nhiên, thông tin này chưa đủ. 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 duyệt đồ thị theo chiều rộng từ hai hướng bình thường: + Duyệt các đỉnh ra của nốt 1, được một phần tử đỉnh 3. + Duyệt các đỉnh vào của nốt 9, được hai phần tử đỉnh 8 và đỉnh 7. + So sánh số lượng các đỉnh ra của nốt 1 và số lượng đỉnh vào của nốt 9. Vì số lượng đỉnh ra của nốt 1 là 1 bé hơn số lượng đỉnh vào của nốt 9 là 2, vậy nên chúng ta tiếp tục đi theo nhánh đỉnh ra. Lúc này số lượng đỉnh ra của đỉnh 3 là 6, trong trường hợp này chúng ta phải duyệt qua tất cả 6 đỉnh mới tìm được phần tử đỉnh 8. Như vậy, tổng cộng 1 + 2 + 6 = 9 đỉnh phải cho vào danh sách hàng đợi duyệ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 41 Để giảm thiểu không gian duyệt (giảm thiểu số lượng các đỉnh cần duyệt), như ví dụ Hình 2.12, 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 đưa 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ột mức, mà so sánh với cả mức thứ 2. Quay trở lại với ví dụ ở Hình 2.12, trước khi duyệt chúng ta sẽ ước lượng tổng số đỉnh ra/vào sẽ được cho vào hàng đợi ở mức 1 và mức 2. Khi đó, đối với đỉnh 1, tổng số đỉnh là 1 + 6 = 7, còn đối với đỉnh 9 là 2 + 1 = 3. Suy ra, đỉnh 9 sẽ được duyệt trước. Điều này sẽ giảm thiểu thời gian tìm kiếm đường đi ngắn nhất trong bài toán này. 2.6.2. Song song hóa truy vấn tìm đường đi ngắn nhất Quá trình xử lý các truy vấn liên tiếp được mô tả chi tiết dưới đây: - Cilk Plus được sử dụng cho quá trình song song hóa. Trong quá trình thực hiện song song hóa, OpenMP và Pthread cũng được tiến hành 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. - Ngoài ra, hai mảng toàn cục dùng để đánh dấu các đỉnh đã được duyệt, một dùng cho các đỉnh ra, một dùng cho các đỉnh vào được sử dụng cho mỗi lần tìm kiếm đường đi ngắn nhất giữa hai đỉnh. - Sau đó, mỗi một luồng sẽ sử dụng một mảng vào/ra phù hợp, được phân chia bởi mảng toàn cục. Sau khi kết thúc quá trình tìm kiếm, mảng vào/ra tương ứng với từng luồng sẽ tự động được giải phóng để chuẩn bị cho quá trình tìm kiếm tiếp theo. 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à đưa ra 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 vấ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. 42 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ị lớn động, không trọng số, 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 Như đã phân tích ở chương 2, 3 sự kiện mà chính cần cài đặt là: tìm đường ngắn nhất giữa hai đỉnh, thêm một cạnh và xóa một cạnh. Ba sự kiện này sẽ được giới thiệu trong các hàm exec_queries, add_edge, del_edge. Trong quá trình xử lý sự kiện, mỗi khi chương trình đọc vào một dòng, chữ cái đầu tiên sẽ được dùng để phân loại sự kiện và thi hành các thủ tục tương ứng với sự kiện đó. 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. 43 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. 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) dựa trên thuật toán duyệt đồ thị theo chiều rộng từ hai hướng cải tiến bởi sử dụng cả hai mảng đỉnh vào (incoming_array) và đỉnh ra (outgoing_array). Quá trình này được mô tả cụ thể trong Thủ tục 4 dưới đây. 44 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. Trong thuật toán duyệt đồ thị theo chiều rộng (mục 1.1.4), chúng ta có bước đánh dấu các đỉnh đã được duyệt. Để đánh dấu các đỉnh này, thuật toán được cài đặt theo mã giả đã được giới thiệu ở (mục 1.1.4). Khi đó, để có thể đánh dấu được các đỉnh đã xét/chưa xét chúng ta cần khởi tạo một mảng đúng bằng số lượng đỉnh của đồ thị. Ví dụ đối với đồ thị một triệu cạnh, chúng ta cần có mảng một triệu phần tử. Với mỗi phần tử kiểu chiếm dung lượng 4 byte bộ nhớ, không gian lưu 45 trữ đối với mảng này là 4 byte * 1.000.000 = 4.000.000 byte ~ 4 megabyte bộ nhớ. Tuy nhiên, nếu chúng ta thao tác trực tiếp đến bit, dùng thứ tự các bit để đánh dấu các đỉnh trong đồ thị, nếu đỉnh đó chưa xét thì giá trị bit là 0, đỉnh được xét thì giá trị bit là 1. Khi đó không gian lưu trữ mảng đánh dấu đối với đồ thị có 1 triệu sẽ là 1.000.000 bit ~ 125.000 byte ~ 0.125 megabyte bộ nhớ. Như vậy, không gian bộ nhớ sẽ giảm 32 lần. Điều này rất cần thiết khi chúng ta thao tác với đồ thị quy mô dữ liệu rất lớn. Mặt khác, khi cài đặt mảng đánh dấu theo kiểu truy xuất đến từng bit, các phép toán trên từng bit nhanh hơn rất nhiều so với các phép toán trên các phần tử mảng. Đồ thị Hình 3.1 miêu tả chi tiết hơn về thời gian thực thi giữa hai phép toán thao tác trên mảng và thao tác trên bit. Trong đồ thị, số lượng phép toán bao gồm tổng số lần gán một phần tử (một bit) bằng 1 và số lần kiểm tra xem phần tử đó đã được gán bằng 1 hay chưa. 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 Cuối cùng, Cilk Plus được dùng để song song hóa các thủ tục tìm đường đi ngắn nhất giữa hai đỉnh (u, v). Thủ tục 5: Xử lý song song các truy vấn liên tiếp trong đồ thị G 0 1 2 3 4 5 6 7 1000 10000 100000 m ilis ec on d Số lượng phép toán Thời gian thực thi giữa hai phép toán thao tác trên mảng và bit Bit Array 46 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 1 574 074 2 000 000 1 971 281 6 009 555 Cạnh 3 232 855 5 000 000 5 533 214 16 518 948 Bậc trong lớn nhất 114 557 90 412 12 779 Bậc ngoài lớn nhất 114 125 356 364 12 770 Dựa trên quy định của ban tổ chức, tất cả các giải pháp của các đội đều được kiểm nghiệm trên máy tính có cấu hình như sau: + CPU: 2 x Intel E5-2620v2 (12 cores / 24 threads) + RAM: 20GB + Hệ điều hành: Ubuntu 14.04 Linux + Phần mềm: Automake 1.15, gcc5.2.1 Dưới đây là kết quả của giải pháp được cài đặt bằng ngôn ngữ lập trình C: Bảng 3.2: Kết quả cuộc thi ACM Sigmod (tính theo giây) Đội Bộ dữ liệu Small Medium X-Large XX-Large akgroup (giải pháp luận văn/đồng giải ba) 0.118 0.494 1.284 2.878 H_minor_free (giải nhất) 0.107 0.220 0.886 2.333 47 uoa_team (giải nhì) 0.208 0.217 1.085 2.123 while1 (đồng giải ba) 0.157 0.234 1.150 2.597 gStreamPKU (đồng giải ba) 0.134 0.072 1.087 3.239 Với kết quả trên, giải pháp đã được lựa chọn là một trong năm đội xuất sắc nhất cuộc thi lập trình ACM Sigmod 2016 (Hình 3.2) và được mời đến trình bày kết quả tại hội nghị Sigmod 2016. 3.2.2. Kiểm nghiệm với bộ dữ liệu SNAP Hai bộ dữ liệu phù hợp với mô hình được chọn là LiveJournal và Pokec. Trong đó LiveJournal là bộ dữ liệu về cộng đồng trực tuyến miễn phí với gần 10 triệu thành viên, và một lượng đáng kể số lượng thành viên thường xuyên hoạt động (có khoảng 300.000 cập nhật/ngày). LiveJournal cho phép các thành viên duy trì các tạp chí, blog cá nhân và nhóm. Nó cũng cho phép mọi người trên cộng đồng này tự kết bạn với nhau [5]. Pokec là bộ dữ liệu về mạng xã hội trực tuyến phổ biến ở Slovakia. Mặc dù khi Facebook đã phát triển ở đây, số lượng người dùng trên Pokec vẫn ổn định. Mạng xã hội Pokec đã được triển khai ở đây hơn 10 năm và có khoảng 1,6 triệu người kết nối. Bộ dữ liệu bao gồm dữ liệu về các người dùng (ẩn danh) trên toàn mạng. Nó bao gồm giới tính, tuổi, sở thích, giáo dục. Thông tin được cung cấp dưới dạng ngôn ngữ Slovakia. Kết nối ở trong mạng xã hội này là có hướng [5]. 48 Hình 3.2: Kết quả cuộc thi ACM Sigmod 2016 49 Chi tiết về hai bộ dữ liệu được miêu tả tại Bảng 3.3. Bảng 3.3: Thống kê bộ dữ liệu LiveJournal và Pokec Thông số LiveJournal Pokec Đỉnh 4 847 571 1 632 803 Cạnh 68 993 773 30 622 564 Độ dài khoảng cách lớn nhất 16 11 Bậc trong lớn nhất 20 293 8 763 Bậc ngoài lớn nhất 13 906 13 733 Cấu hình máy thử nghiệm + CPU: 4 x Intel Xeon E7- 4850 @ 2.00GHz (10 cores / 20 threads) + RAM: 128GB + Hệ điều hành: CentOS 6.7 Linux + Phần mềm: Automake 1.15, gcc5.2.0 Khối lượng kiểm nghiệm Để kiểm nghiệm phương pháp, một công cụ sinh tự động các sự kiện đã được chúng tôi xây dựng theo phương pháp như đã trình bày ở mục 2.1. Với mỗi đồ thị, chúng tôi đã sinh bộ kiểm thử với khoảng 1.000.000 sự kiện. Tỉ lệ sự kiện truy vấn/thêm cạnh/xóa cạnh tương ứng là 8/1/1. Thực chất, có khoảng 800.000 truy vấn tìm đường ngắn nhất, 100.000 sự kiện thêm cạnh và 100.000 sự kiện xóa cạnh. Kết quả thử nghiệm Thuật toán được trình bày trong luận văn được so sánh với hai giải pháp Reference, Snap đã được trình bày ở mục 2.2, cùng với các giải pháp trong cuộc thi ACM Sigmod Contest 2016. Trong giải pháp Reference, đồ thị được lưu trữ dưới dạng danh sách liền kề theo kiểu dictionary trong ngôn ngữ lập trình python. Mỗi sự kiện thêm cạnh và xóa cạnh được thực hiện tuần tự. Sự kiện truy vấn vẫn sử dụng thuật toán tìm kiếm tìm đường đi ngắn nhất từ hai hướng. Còn trong giải pháp Snap, đồ thị vẫn 50 được lưu trữ dưới dạng danh sách liền kề theo cấu trúc dữ liệu vector trong ngôn ngữ lập trình C++. Hai sự kiện thêm cạnh và xóa cạnh vẫn được thực hiện tuần tự. Sự kiện truy vấn sử dụng thuật toán tìm đường đi ngắn nhất từ cả hai hướng. Thêm nữa, các giải pháp của bốn đội xuất sắc nhất trong cuộc thi ACM Sigmod 2016 cũng được sử dụng để so sánh. Dưới đây là tóm tắt giải pháp của bốn đội. H_minor_free (đội đạt giải nhất): Lưu trữ đồ thị dưới dạng danh sách cạnh liền kề theo cấu trúc vector trong ngôn ngữ C++. Mỗi cạnh được gán thêm thuộc tính ALIVE: cạnh có thể đi qua, DEAD: cạnh không thể đi qua, UNKNOWN: cạnh được thay đổi trong quá trình thực hiện lô. Với mỗi lô, thuật toán được thực hiện qua ba bước. - Bước 1: Với mỗi cạnh được thêm vào hoặc xóa đi thay đổi thuộc tính của cạnh thành UNKNOWN - Bước 2: Sử dụng thuật toán duyệt đồ thị theo chiều rộng từ hai hướng sử dụng OpenMP để song song truy vấn. - Bước 3: Thay đổi thuộc tính của cạnh thành ALIVE (sự kiện thêm cạnh), DEAD (sự kiện xóa cạnh) sau quá trình truy vấn. Uoa_team (đội đạt giải nhì): Đồ thị được biểu diễn dưới dạng danh sách kề, gồm danh sách kề các đỉnh vào và danh sách kề các đỉnh ra. Các sự kiện thêm cạnh và xóa cạnh không thực hiện song song mà được lưu trong các cấu trúc dữ liệu khác nhau cùng với phiên bản của nó. Sự kiện truy vấn sử dụng thuật toán duyệt đồ thị theo chiều rộng từ hai hướng kết hợp với phương pháp threadpool để tăng tốc quá trình truy vấn. While1: Đồ thị được biểu diễn dưới dạng hai danh sách kề các đỉnh ra và đỉnh vào. Mỗi sự kiện thêm cạnh và xóa cạnh được thêm vào danh sách transaction. Sau khi kết thúc mỗi lô, transaction này sẽ được áp dụng để thêm cạnh và xóa cạnh từ đồ thị. Chương trình sử dụng nhiều luồng để tăng tốc xử lý các sự kiện. Luồng chính xử lý các sự kiện thêm, xóa cạnh. Sự kiện truy vấn sử dụng thuật toán duyệt đồ thị theo chiều rộng từ hai hướng được phân phối cho các luồng còn lại gStreamPKU: Lưu trữ đồ thị dưới dạng danh sách cạnh liền kề theo cấu trúc unordered_map trong ngôn ngữ C++. Một đồ thị tạm gọi là Delta Graph được xây dựng để lưu các sự kiện thêm cạnh và xóa cạnh cùng với nhãn thời gian của các sự kiện này. Thuật toán duyệt đồ thị theo chiều rộng từ hai hướng được sử dụng trong sự kiện truy vấn kết hợp với Threading Building Blocks (TBB) để tăng tốc quá trình truy vấn. 51 Để đánh giá hiệu quả thuật toán, mỗi phương pháp được chạy tổng cộng 5 lần, sau đó lấy kết quả trung bình. Đối với giải pháp trong luận văn và của các đội trong cuộc thi ACM Sigmod 2016, chương trình thực thi với 24 luồng (giống điều kiện máy kiểm thử của ban tổ chức). Kết quả trung bình được trình bày chi tiết trong Bảng 3.4. Bảng 3.4: Kết quả thử nghiệm (tính theo mili giây) Giải pháp Bộ dữ liệu Sigmod Test Pokec Live Journal Giải pháp trong luận văn 2 787 17 985 42 876 Reference 1 825 674 1 903 068 53 235 981 Snap 48 741 49 316 108 ~ 5 ngày H_minor_free 1 422 6 047 15 673 Uoa_team 7 110 17 526 14 724 While1 Kết quả truy vấn chưa chính xác Kết quả truy vấn chưa chính xác Kết quả truy vấn chưa chính xác gStreamPKU 2 918 7 134 12 085 Bên cạnh đó, luận văn cũng so sánh các phương pháp của các giải pháp khi thay đổi số lượng luồng xử lý truy vấn. Kết quả chi tiết được miêu tả trong Hình 3.3, Hình 3.4 và Hình 3.5 dưới đây. . 52 Hình 3.3: Kết quả thử nghiệm với bộ dữ liệu SIGMOD TEST Hình 3.4: Kết quả thử nghiệm với bộ dữ liệu POKEC 0 1000 2000 3000 4000 5000 6000 7000 8000 1 2 4 8 16 24 32 48 M ill ise co nd s Number of Threads SIGMOD TEST Thesis H_miror_free uoa_team gStreamPKU 0 10000 20000 30000 40000 50000 60000 70000 1 2 4 8 16 24 32 48 M ill ise co nd s Number of Threads POKEC Thesis H_miror_free uoa_team gStreamPKU 53 Hình 3.5: Kết quả thử nghiệm với bộ dữ liệu LIVEJOURNAL Dựa trên các kết quả thu được, chúng ta có thể rút ra kết luận, tùy thuộc vào từng bộ dữ liệu mà quá trình song song hóa có hiệu quả hay không. Bộ dữ liệu Sigmod có số lượng các đỉnh có bậc trong và bậc ngoài lớn. Nói cách khác, số đỉnh tập trung đến, hoặc tập trung đi từ một vài đỉnh, không phân bố đều trên cả đồ thị. Hệ quả là số lượng đỉnh treo rất nhiều. Do đó, truy vấn tìm đường ngắn nhất sẽ thực thi rất nhanh. Khi đó, chi phí cho việc quản lý nhiều luồng sẽ không bù lại được chi phí thi hành song song hóa. Bởi vậy, trong trường hợp này số lượng luồng ít sẽ cho kết quả tốt. Ngược lại, hai bộ dữ liệu LiveJournal và Pokec có quy mô dữ liệu đồ sộ hơn rất nhiều lần so với bộ dữ liệu Sigmod (gấp khoảng 25 và 10 lần), và có tỉ lệ đỉnh/cạnh rất lớn (3/4 và 1/2), kết hợp với các cạnh phân bố đều hơn, khi đó, quá trình song song hóa mới thực sự có tác dụng. Tuy nhiên, việc tăng số lượng luồng chỉ lên đến một mức nhất định. Quá giới hạn này, chương trình sẽ gặp phải vấn đề chi phí quản lý luồng đã đề cập ở trên. Vì vậy, với mỗi bộ dữ liệu, chúng ta phải dựa vào thực tế để tìm ra được ngưỡng luồng đạt hiệu quả cao nhất. 3.3. Tổng kết chương Chương 3 đã trình bày chi tiết phương án cài đặt dựa trên các phân tích ở chương 2. Bên cạnh đó, luận văn cũng so sánh kết quả thực nghiệm với hai thư viện NetworkX và Snap, cũng như so sánh cụ thể hơn với bốn đội đã đạt kết quả tốt nhất trong cuộc thi lập trình ACM Sigmod 2016. Kết quả thu được cho phép kết luận phương án được ra của luận văn đạt hiệu quả tốt. 0 20000 40000 60000 80000 100000 120000 140000 1 2 4 8 16 24 32 48 M ill ise co nd s Number of Threads LIVEJOURNAL Thesis H_miror_free uoa_team gStreamPKU 54 Kết luận chung Các đóng góp chính Sau một thời gian nghiên cứu và tìm hiểu đề tài, luận văn đã được hoàn thành và đạt được những nội dung chính đề ra với mục tiêu tối ưu truy vấn tìm đường ngắn nhất trên đơn đồ thị, động, có hướng, không trọng số với quy mô dữ liệu lớn. Về lý thuyết, luận văn đã trình bày một số kiến thức cơ bản về đồ thị, các dạng đồ thị cũng như ứng dụng của lý thuyết đồ thị đối với các bài toán cụ thể trong đời sống hàng ngày. Tiếp theo, luận văn trình bày bốn mô hình liên quan đến việc cài đặt đồ thị trong thực tế và phân tích ưu, nhược điểm của từng mô hình. Bên cạnh đó, luận văn trình bày về bài toán tìm đường đi ngắn nhất trong đồ thị, các thuật toán cơ bản hay được sử dụng và ứng dụng của bài toán trong thực tiễn. Kế tiếp, luận văn trình bày các công cụ mã nguồn mở, các vấn đề liên quan khi xử lý bài toán liên quan đến đồ thị, kết hợp với đánh giá về mặt thuận lợi và khó khăn khi áp dụng với đơn đồ thị, động, có hướng, không trọng số với quy mô dữ liệu lớn. Về thực nghiệm, luận văn đã đưa ra các phương pháp để cải thiện quá trình tìm đường ngắn nhất, cũng như cài đặt hoàn chỉnh mã nguồn trên ngôn ngữ C. Phương pháp đã được kiểm nghiệm tại cuộc thi lập trình ACM Sigmod 2016 và cho kết quả khá khả quan. Thêm vào đó, thuật toán trong luận văn cũng được so sánh với một số bộ công cụ mã nguồn mở được cho là xử lý các bài toàn liên quan đến đồ thị tốt nhất hiện nay và với chính bốn đội xuất sắc nhất từ cuộc thi lập trình ACM Sigmod 2016 trên hai bộ dữ LiveJournal và Pokec. Kết quả cho thấy phương pháp đạt kết quả tốt dựa trên việc sử dụng cấu trúc dữ liệu phù hợp, tối ưu thuật toán duyệt đồ thị theo chiều rộng từ hai hướng, cũng như sử dụng công cụ Cilk Plus để song song hóa quá trình truy vấn. Hướng phát triển Dựa trên đó, hướng phát triển tiếp theo của đề tài là tối ưu hóa thuật toán, áp dụng các phương pháp khác vào quá trình tìm kiếm đường đi ngắn nhất như tính toán trước hay dự kiến đường đi ngắn nhất giữa hai đỉnh đi qua một số đỉnh trung gian nào đó. Từ đó có thể giảm được khá nhiều thời gian tính toán khi mỗi lần lại phải tính toán lại từ đầu đường đi ngắn nhất đó. Tiếp theo là có thể áp dụng các kỹ thuật này giảm tỉ lệ cache miss trong CPU cho các bài toán cần hiệu năng cao khác như xử lý giao dịch trực tuyến (Online Transaction Processing). 55 Danh mục công trình khoa học của tác giả 1. Phuong-Hanh DU, Hai-Dang PHAM, Ngoc-Hoa NGUYEN, "Optimizing the Shortest Path Query on Large-Scale Dynamic Directed Graph", Proceedings of the 3rd IEEE/ACM International Conference on Big Data Computing Applications and Technologies (BDCAT 2016), Shanghai, China, 2016. (Accepted). 56 Tài liệu tham khảo [1] Tiếng Việt Nguyễn Đức Nghĩa, Nguyễn Tô Thành, Toán rời rạc.: Nhà xuất bản Đại học Quốc gia Hà Nội, 2006. [2] Tiếng Anh Dip Sankar Banerjee, Shashank Sharma, and Kishore Kothapalli, "Work efficient parallel algorithms for large graph exploration," in 20th Annual International Conference on High Performance Computing, 2013, pp. 433 - 442. [3] Venkatesan T. Chakaravarthy, Fabio Checconi, Fabrizio Petrini, and Yogish Sabharwal, "Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems," in Parallel and Distributed Processing Symposium, 2014 IEEE 28th International, 2014, pp. 889 - 901. [4] Cilk Plus. [Online]. https://www.cilkplus.org [5] Stanford Large Network Dataset Collection. [Online]. [6] The ACM SIGMOD Programming Contest. (2016) [Online]. sigmod16contest/ [7] Tom Cormen and Devin Balkcom. KHANACADEMY. [Online]. https://www.khanacademy.org/computing/computer-science/algorithms/ [8] Jayanta Mondal and Amol Deshpande, "Managing large dynamic graphs efficiently," in ACM SIGMOD International Conference on Management of Data, 2012, pp. 145-156. [9] Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin, "PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs," in OSDI'12 Proceedings of the 10th USENIX conference on Operating Systems Design and Implementation, 2012, pp. 17-30. [10] Joseph E. Gonzalez et al., "GraphX: Graph Processing in a Distributed Dataflow Framework," in OSDI'14 Proceedings of the 11th USENIX conference on Operating Systems Design and Implementation, 2014, pp. 599-613. [11] Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser, Data Structures and Algorithms in Java, 6th ed. United States of America: Wiley, 2014. 57 [12] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swar, "Exploring network structure, dynamics, and function using NetworkX," in Proceedings of the 7th Python in Science Conference (SciPy), 2008, pp. 11-15. [13] Charles E. Leiserson and Tao B. Schardl, "A work-efficient parallel breadth- first search algorithm (or how to cope with the nondeterminism of reducers)," in Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures, 2010, pp. 303-314. [14] Qingxia Li and Wenhong Wei, "A parallel single-source shortest path algorithm based on bucket structure," in 2013 25th Chinese Control and Decision Conference (CCDC), 2013, pp. 3445 - 3450. [15] Waqas Nawaz, Kifayat-Ullah Khan, and Young-Koo Lee, "CORE Analysis for Efficient Shortest Path Traversal Queries in Social Graphs," in In Social Graphs,Big Data and Cloud Computing (BdCloud), 2014 IEEE Fourth International Conference, Sydney, 2014, pp. 363-370. [16] NetworkX. [Online]. [17] Open Multi-Processing. [Online]. [18] POSIX Threads Programming. [Online]. https://computing.llnl.gov/tutorials/pthreads/ [19] Grégoire Scano, Marie-José Huguet, and Sandra Ulrich Ngueveu, "Adaptations of k-shortest path algorithms for transportation networks," in Industrial Engineering and Systems Management (IESM), 2015 International Conference on, 2015, pp. 663 - 669. [20] Stanford Network Analysis Platform. [Online]. [21] Leong Hou U, Hong Jun Zhao, Man Lung Yiu, Yuhong Li, and Zhiguo Gong, "Towards Online Shortest Path Computation," IEEE Transactions on Knowledge and Data Engineering, vol. 26, no. 4, pp. 1012 - 1025, Apr. 2014. [22] Jian Wei, Kai Chen, Yi Zhou, Qu Zhou, and Jianhua He, "Benchmarking of Distributed Computing Engines Spark and GraphLab for Big Data Analytics," in 2016 IEEE Second International Conference on Big Data Computing Service and Applications (BigDataService), 2016, pp. 10 - 13.