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).
58 trang |
Chia sẻ: yenxoi77 | Lượt xem: 573 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu 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, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trê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.
Các file đính kèm theo tài liệu này:
- luan_van_toi_uu_hoa_truy_van_tim_duong_ngan_nhat_tren_do_thi.pdf