Tổng quan luận án

Luận án tiến sĩ với tiêu đề "Nâng cao hiệu năng thi hành các phép toán trên đồ thị" được nghiên cứu sinh Dư Phương Hạnh thực hiện tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội, dưới sự hướng dẫn khoa học của PGS. Nguyễn Hải Châu và PGS. Nguyễn Kim Khoa (Trường ETS – Đại học Quebec, Canada), thuộc chuyên ngành Hệ thống thông tin (Mã số: 9480104.01), bảo vệ năm 2019.

Tính cấp thiết và khoảng trống nghiên cứu

Trong bối cảnh nền kinh tế số và sự gia tăng khối lượng dữ liệu quy mô lớn (theo thống kê của Internet Live Stats năm 2019, lưu lượng vận chuyển qua Internet đạt xấp xỉ 79.870 GB/giây, với 4,8 tỷ lượt tìm kiếm Google và 184 tỷ thư điện tử mỗi ngày), mô hình dữ liệu đồ thị (graph data model) đã trở thành công cụ biểu diễn cấu trúc dữ liệu và quan hệ phi cấu trúc trong các mạng xã hội (Facebook với hơn 2,327 tỷ người dùng, YouTube 1,9 tỷ, WhatsApp 1,5 tỷ người dùng hoạt động vào tháng 09/2019), mạng sinh học và mạng giao thông.

Tuy nhiên, việc xử lý các phép toán trên đồ thị quy mô lớn gặp phải ba thách thức chính:

  1. Hạn chế về cấu trúc dữ liệu và khả năng khai thác bộ nhớ đệm (cache): Các cấu trúc dữ liệu đồ thị hiện tại chủ yếu tổ chức theo danh sách liền kề hoặc ma trận thưa nhưng chưa chú trọng tối ưu hóa tính cục bộ của dữ liệu (data locality). Các công cụ phân tích đồ thị thực hiện ít tính toán trên mỗi phần tử nhưng lại truy xuất bộ nhớ ngẫu nhiên, dẫn đến tỷ lệ lỗi bộ nhớ đệm (cache miss) cao, làm suy giảm hiệu năng xử lý.
  2. Xử lý truy vấn đường đi/khoảng cách ngắn nhất trên đồ thị động quy mô lớn: Các mạng xã hội và đồ thị thực tế liên tục phát sinh các thao tác cập nhật đỉnh, cạnh đan xen với các truy vấn tìm khoảng cách ngắn nhất giữa hai đỉnh. Các thư viện phổ biến như NetworkX hay SNAP C++ chủ yếu thi hành đơn luồng tuần tự; giải thuật tìm kiếm theo chiều rộng hai chiều (bidirectional Breadth-First Search - bBFS) hiện có chỉ dựa trên số đỉnh ở hàng đợi hiện tại mà chưa đánh giá cấu trúc phân nhánh kế tiếp, dẫn đến bùng nổ số lượng đỉnh cần duyệt.
  3. Chi phí tính toán cao đối với các độ đo trung tâm trong phân tích đồ thị: Việc xác định tầm quan trọng của các đỉnh thông qua độ trung tâm gần (Closeness Centrality - CC) và độ trung tâm trung gian (Betweenness Centrality - BC) đòi hỏi giải bài toán đường đi ngắn nhất từ tất cả các cặp đỉnh (All Pairs Shortest Path - APSP), với độ phức tạp tính toán đa thức bậc cao ($O(|V|^3)$ hoặc $O(|V|^2 \log|V| + |V||E|)$). Khi áp dụng cho đồ thị hàng triệu đến hàng trăm triệu đỉnh/cạnh, việc thi hành tuần tự là bất khả thi, trong khi các hệ thống tính toán phân tán (như Giraph, GraphLab) đòi hỏi hạ tầng cụm máy tính phức tạp và không tối ưu cho phần cứng máy chủ đa lõi thông thường.

Mục tiêu nghiên cứu

Luận án xác định 4 mục tiêu nghiên cứu cụ thể:

  1. Khảo sát, phân tích và đánh giá các phương pháp, kỹ thuật tổ chức dữ liệu đồ thị cùng các phép toán cơ bản trên đồ thị.
  2. Xây dựng mô hình đặc tả bài toán xử lý các truy vấn khoảng cách ngắn nhất trên đồ thị động quy mô lớn; đề xuất các giải pháp nâng cao hiệu năng thông qua tổ chức dữ liệu phù hợp và tính toán song song.
  3. Nâng cao hiệu năng các giải thuật tính toán độ đo trung tâm (độ trung tâm gần và độ trung tâm trung gian) trên đồ thị tĩnh quy mô lớn bằng kỹ thuật song song hóa kết hợp tối ưu bộ nhớ đệm.
  4. Cài đặt thử nghiệm, đo đạc thực nghiệm và so sánh đối sánh hiệu năng các giải pháp đề xuất với các hệ thống, công cụ chuẩn hiện có trên các tập dữ liệu đồ thị thực tế.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Đồ thị không trọng số, bao gồm đồ thị có hướng và vô hướng quy mô lớn; các phép toán cơ bản (thêm cạnh, xóa cạnh, duyệt BFS/DFS), truy vấn khoảng cách ngắn nhất trên đồ thị động và hai độ đo trung tâm (CC, BC) trong phân tích đồ thị.
  • Phạm vi nghiên cứu:
    • Đồ thị động có hướng, không trọng số, hỗ trợ các thao tác cập nhật cạnh (thêm/xóa) và truy vấn khoảng cách ngắn nhất giữa hai đỉnh bất kỳ.
    • Đồ thị tĩnh quy mô lớn phục vụ tính toán các độ đo trung tâm mạng xã hội.
    • Phạm vi phần cứng: Tập trung vào kiến trúc hệ thống tính toán đa lõi dựa trên bộ nhớ chia sẻ (shared-memory multi-core systems); không xét các đồ thị vượt quá 1 tỷ đỉnh (như toàn bộ mạng dữ liệu toàn cầu của Facebook) do giới hạn tài nguyên tính toán thực nghiệm.

Tổng quan tài liệu và vị trí của luận án

Luận án tổng thuật các công trình nghiên cứu trong và ngoài nước theo ba nhóm:

Các luận án tiến sĩ liên quan

  • Luận án của Slota (2016, Đại học Pennsylvania, Mỹ): Đề xuất giải pháp song song và khả mở cho các phép phân tích đồ thị (bao gồm BFS) trên kiến trúc đa lõi, GPU và mô hình lai MPI/OpenMP. Luận án này xử lý đồ thị đến hàng tỷ đỉnh nhưng chỉ tập trung vào các thao tác đọc (read-only) trên đồ thị tĩnh, chưa xét các phép toán tương tranh có cập nhật trên đồ thị động.
  • Luận án của Beamer (2016, Đại học California, Berkeley, Mỹ): Tối ưu hóa tính cục bộ dữ liệu để tăng tỷ lệ cache hit và cải tiến hướng duyệt BFS trên đồ thị đường kính nhỏ theo phương pháp heuristic chuyển hướng duyệt. Nghiên cứu này cũng chỉ giới hạn ở các thao tác đọc và đồ thị tĩnh.
  • Luận án của Guerrieri (2015, Đại học Trento, Ý): Đề xuất giải thuật DFEP (Distributed Funding-based Edge Partitioning) và hệ thống ETSCH để xử lý đồ thị phân tán. Tuy nhiên, giải pháp chưa khai thác được tính cục bộ dữ liệu trên các mô hình tính toán hiện đại để giảm thiểu cache miss.
  • Luận án của Kyrola (2014, Đại học Carnegie Mellon - CMU, Mỹ): Đề xuất giải thuật trượt cửa sổ song song (Parallel Sliding Windows) và cấu trúc danh sách liền kề phân mảnh (Partitioned Adjacency Lists), xây dựng nền tảng GraphChi và GraphChi-DB xử lý đồ thị trên bộ nhớ ngoài (ổ cứng SSD). Cách tiếp cận này bị giới hạn bởi tốc độ vào/ra dữ liệu (I/O), chưa khai thác tối đa tài nguyên bộ nhớ RAM lớn và CPU đa nhân.

Các công cụ, thư viện và hướng nghiên cứu chuyên sâu

  • Các thư viện xử lý đồ thị: NetworkX (Python) và SNAP C++ Library hỗ trợ phân tích mạng phức tạp nhưng thi hành thuật toán bBFS và tính độ trung tâm một cách tuần tự (đơn luồng). Các thư viện NetworKit và TeexGraph đã sử dụng OpenMP để song song hóa trên kiến trúc đa lõi nhưng chưa tối ưu cấu trúc dữ liệu theo phân cấp bộ nhớ đệm CPU.
  • Các hệ thống tính toán phân tán: Pregel, Apache Giraph, GraphLab, PowerGraph, GraphX xử lý đồ thị quy mô hàng tỷ cạnh trên hệ thống cụm máy tính (cluster) hoặc siêu máy tính (supercomputer), nhưng có độ trễ lớn và kém hiệu quả khi xử lý các truy vấn tương tranh trên đồ thị động quy mô trung bình đến lớn trên nền tảng máy chủ độc lập.
  • Các giải pháp tại cuộc thi ACM SIGMOD Programming Contest 2016: Cuộc thi đặt ra bài toán xử lý truy vấn khoảng cách ngắn nhất trên đồ thị động có cập nhật liên tục:
    • H_minor_free (giải Nhất): Nhúng trạng thái cạnh (ALIVE, DEAD, UNKNOWN) vào dữ liệu đỉnh liền kề và dùng OpenMP duyệt bBFS.
    • uoa_team (giải Nhì): Sử dụng cấu trúc dữ liệu đa phiên bản (multiversioning) và hàng đợi tương tranh (concurrentqueue).
    • akGroup (nhóm tác giả luận án - giải Ba): Tổ chức dữ liệu danh sách đỉnh đến/đi kèm chỉ mục, áp dụng heuristic chọn chiều duyệt bBFS và song song hóa truy vấn.
    • gStreamPKU: Nén bit để tăng tỷ lệ cache hit và xây dựng đồ thị Delta cập nhật theo lô bằng thư viện TBB.
    • while1: Dùng danh sách cạnh giao tác và nhân bản đồ thị trên các nút NUMA.
  • Các phương pháp tính độ trung tâm: Giải thuật kinh điển của Freeman (1977) và Brandes (2001) cho Betweenness Centrality; các kỹ thuật tính xấp xỉ qua lấy mẫu (Eppstein, Okamoto, Riondato); thuật toán tăng dần iCENTRAL của Jamour (2018); giải pháp tính trên nhiều GPU như MGBC của Bernaschi (2016).

Khoảng trống nghiên cứu luận án lựa chọn

Luận án tập trung giải quyết khoảng trống kết hợp đồng thời giữa: (1) thiết kế cấu trúc dữ liệu đồ thị tối ưu hóa tính cục bộ nhằm giảm tỷ lệ cache miss; (2) xây dựng giải thuật bBFS cải tiến có khả năng chọn hướng duyệt tối ưu dựa trên cả bậc đỉnh con và đỉnh cháu; (3) cơ chế song song hóa đồng thời cả phép toán cập nhật (thêm/xóa cạnh) và truy vấn khoảng cách ngắn nhất trên hệ thống đa lõi; và (4) song song hóa tính toán các độ đo trung tâm toàn cục (CC, BC) trên đồ thị quy mô lớn mà không đòi hỏi hạ tầng phần cứng phân tán phức tạp.

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

Cơ sở lý thuyết và các khái niệm

  • Lý thuyết đồ thị: Luận án sử dụng các định nghĩa hình thức về đồ thị $G = (V, E)$, đồ thị có hướng, vô hướng, đồ thị không trọng số; bậc vào $d_{in}(v)$, bậc ra $d_{out}(v)$; đường kính đồ thị; thành phần liên thông mạnh/yếu.
  • Biểu diễn đồ thị: Khảo sát các cấu trúc dữ liệu kinh điển gồm danh sách cạnh ($O(|E|)$ không gian), ma trận liền kề ($O(|V|^2)$ không gian), danh sách liền kề ($O(|V| + |E|)$ không gian), ma trận liên thuộc ($O(|V| \cdot |E|)$ không gian), và ma trận hàng thưa nén (Compressed Sparse Row - CSR).
  • Các phép toán cơ bản: Thuật toán duyệt theo chiều rộng (BFS - Thuật toán 2.1) và duyệt theo chiều sâu (DFS - Thuật toán 2.2) với độ phức tạp thời gian $O(|V| + |E|)$; giải thuật tìm kiếm hai chiều bBFS (Thuật toán 2.3).
  • Các độ đo phân tích mạng:
    • Bậc trung tâm (Degree Centrality - CD): $C_D(v) = \text{deg}(v)$.
    • Độ trung tâm gần (Closeness Centrality - CC): $$CC(v) = \frac{1}{\sum_{u \in V} \text{dst}(u, v)}$$ (tính trên thành phần liên thông lớn nhất $\Gamma_G$).
    • Độ trung tâm trung gian (Betweenness Centrality - BC): $$BC(v) = \sum_{s \neq v \neq t \in V} \frac{\sigma_{st}(v)}{\sigma_{st}}$$ trong đó $\sigma_{st}$ là số đường đi ngắn nhất giữa $s$ và $t$, $\sigma_{st}(v)$ là số đường đi ngắn nhất đi qua $v$.
    • Độ trung tâm vector riêng (Eigenvector Centrality) và Mật độ đồ thị ($D$).
  • Lý thuyết tính toán song song:
    • Định luật Amdahl xác định hệ số tăng tốc: $\text{SpeedUp} = \frac{1}{(1-P) + \frac{P}{N}}$ (với $P$ là tỷ lệ mã song song, $N$ là số bộ xử lý).
    • Kiến trúc phần cứng: Bộ nhớ chia sẻ (UMA/NUMA với cơ chế cache coherency), bộ nhớ phân tán, và kiến trúc lai chia sẻ - phân tán.
    • Mô hình lập trình song song: Đa luồng chia sẻ bộ nhớ (sử dụng OpenMP, Intel CilkPlus, POSIX Threads).

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

  • Phương pháp nghiên cứu lý thuyết: Mô hình hóa hình thức các phép toán cập nhật và truy vấn dưới dạng một lịch thi hành tuần tự/tương tranh $S$; chứng minh tính đúng đắn của giải thuật; phân tích độ phức tạp thời gian và không gian bộ nhớ.
  • Phương pháp nghiên cứu thực nghiệm:
    • Cài đặt các thuật toán bằng C++ để tối ưu hóa hiệu năng cấp phát bộ nhớ và quản lý luồng.
    • Sử dụng các bộ dữ liệu đồ thị chuẩn từ SNAP (Stanford Network Analysis Project) gồm mạng xã hội Pokec, LiveJournal, và bộ dữ liệu từ cuộc thi ACM SIGMOD Contest 2016.
    • Thiết lập các kịch bản lịch thi hành với tỷ lệ thao tác khác nhau (ví dụ: kịch bản 8-1-1 gồm 80% truy vấn, 10% thêm cạnh, 10% xóa cạnh; kịch bản 5-4-1 gồm 50% truy vấn, 40% thêm cạnh, 10% xóa cạnh).
    • Đo lường thời gian thi hành (giây) và hệ số tăng tốc (speedup factor) trên cùng một cấu hình phần cứng đa lõi, đối chuẩn trực tiếp với SNAP C++, NetworkX, TeexGraph, NetworKit và các giải pháp đạt giải SIGMOD 2016.

Nội dung chính theo từng chương

Chương 1: Giới thiệu chung

Chương này thiết lập cơ sở khoa học và thực tiễn của đề tài. Tác giả chỉ ra sự bùng nổ của dữ liệu đồ thị trong kỷ nguyên số và phân tích các giới hạn kỹ thuật của các hệ thống quản trị dữ liệu truyền thống. Nội dung chương làm rõ tính cấp thiết của việc nâng cao hiệu năng xử lý đồ thị động và phân tích độ đo trung tâm, tổng hợp các công trình liên quan trên thế giới, định hình 4 mục tiêu nghiên cứu, phạm vi, phương pháp luận và cấu trúc 5 chương của luận án.

Chương 2: Cơ sở lý thuyết

Chương 2 hệ thống hóa toàn diện nền tảng lý thuyết:

  • Trình bày chi tiết các định nghĩa hình thức về đồ thị, các dạng đồ thị (vô hướng, có hướng, có trọng số, đa đồ thị, đồ thị thuộc tính, đồ thị hai phía).
  • Phân tích ưu/nhược điểm và độ phức tạp không gian của 5 phương pháp biểu diễn đồ thị: Danh sách cạnh, Ma trận liền kề, Danh sách liền kề, Ma trận liên thuộc, và Ma trận hàng thưa nén (CSR).
  • Chi tiết hóa thuật toán duyệt đồ thị cơ bản (BFS, DFS) và thuật toán bBFS tìm khoảng cách ngắn nhất; định nghĩa các bài toán SSSP, SDSP, APSP.
  • Trình bày cơ sở toán học của 4 độ đo trung tâm: Degree Centrality ($C_D$), Closeness Centrality ($CC$), Betweenness Centrality ($BC$), và Eigenvector Centrality.
  • Trình bày nguyên lý tính toán song song: Định luật Amdahl, các mô hình kiến trúc bộ nhớ (UMA, NUMA, Phân tán, Lai) và mô hình lập trình đa luồng (CilkPlus, OpenMP).

Chương 3: Tối ưu hoá truy vấn khoảng cách ngắn nhất trên đồ thị động

Chương 3 trình bày các đóng góp trọng tâm của luận án đối với bài toán xử lý truy vấn khoảng cách ngắn nhất trên đồ thị động quy mô lớn:

  • Đặc tả bài toán: Mô hình hóa đồ thị động $G=(V,E)$ chịu tác động bởi dòng các phép toán $O = {A, D, Q}$ (trong đó $A(u,v)$ là thêm cạnh, $D(u,v)$ là xóa cạnh, $Q(u,v)$ là truy vấn khoảng cách ngắn nhất), được thực thi theo một lịch trình tương tranh $S$.
  • Giải pháp 1 – akGroup:
    • Tổ chức cấu trúc dữ liệu đồ thị lưu trữ đồng thời danh sách đỉnh đến ($N_{in}$) và đỉnh đi ($N_{out}$) có chỉ mục hỗ trợ truy cập trực tiếp.
    • Tối ưu hóa phép toán cập nhật: Thực hiện ghi nhận toàn bộ các thao tác $A$ và $D$ trước, sau đó xử lý song song các truy vấn $Q$.
    • Tối ưu hóa bBFS: Đề xuất kỹ thuật heuristic lựa chọn hướng duyệt thông minh dựa trên đánh giá bậc phân nhánh của các đỉnh kế tiếp (đỉnh con và đỉnh cháu) nhằm hạn chế tối đa số lượng đỉnh mở rộng vào hàng đợi.
  • Giải pháp 2 – akGroupPlus:
    • Nâng cấp cấu trúc dữ liệu bằng cách gắn trạng thái thời gian/phiên bản trực tiếp vào mỗi cạnh, cho phép xử lý tương tranh giữa các phép toán cập nhật và truy vấn khoảng cách mà không cần khóa toàn bộ cấu trúc đồ thị.
    • Tối ưu hóa việc kiểm tra tính hợp lệ của cạnh tại thời điểm truy vấn $t$ thông qua bảng băm và mảng trạng thái.
  • Giải pháp 3 – bigGraph:
    • Hoàn thiện mô hình xử lý song song hóa toàn diện cả các phép toán cập nhật $A, D$ và các phép toán truy vấn $Q$.
    • Tối ưu hóa cấu trúc bộ nhớ dạng mảng tuyến tính liền kề nhằm tối đa hóa tính cục bộ dữ liệu, giảm thiểu tối đa hiện tượng cache miss trên CPU đa lõi.
  • Kết quả thực nghiệm:
    • Đánh giá trên bộ dữ liệu SIGMOD Contest 2016, SNAP Pokec, SNAP LiveJournal với các tập lịch 8-1-1 và 5-4-1. Các giải pháp đề xuất cho thấy thời gian xử lý giảm vượt trội so với SNAP C++ và NetworkX; giải pháp akGroup đạt giải Ba tại ACM SIGMOD Programming Contest 2016.

Chương 4: Nâng cao hiệu năng tính độ trung tâm trên đồ thị

Chương 4 tập trung giải quyết bài toán phân tích đồ thị tĩnh quy mô lớn:

  • Phân tích bài toán: Chi phí tính toán $CC$ và $BC$ trên toàn bộ tập đỉnh $V$ tương đương với việc giải $|V|$ bài toán SSSP.
  • Giải pháp đề xuất trên nền tảng bigGraph:
    • Thiết kế cấu trúc dữ liệu mảng thưa nén tối ưu bộ nhớ đệm, cho phép các luồng xử lý truy cập song song vào đồ thị mà không gây tranh chấp bộ nhớ (memory contention).
    • Giải thuật song song tính Closeness Centrality (Thuật toán 4.3): Phân chia tập đỉnh cho các luồng xử lý độc lập để tính BFS đơn nguồn, sử dụng mảng đánh dấu vết cục bộ cho từng luồng nhằm tránh xung đột dữ liệu.
    • Giải thuật song song tính Betweenness Centrality (Thuật toán 4.4): Song song hóa pha duyệt BFS và pha tích lũy phụ thuộc (theo thuật toán Brandes) trên từng đỉnh nguồn $s \in V$.
  • Kết quả thực nghiệm:
    • Thử nghiệm trên các mạng xã hội thực tế từ kho dữ liệu SNAP.
    • So sánh đối kháng với hai bộ thư viện C++ song song hiện đại là NetworKit và TeexGraph.
    • Kết quả đo đạc cho thấy bigGraph đạt tốc độ thi hành nhanh hơn và có hệ số tăng tốc (speedup) tuyến tính hơn theo số lượng lõi CPU so với NetworKit và TeexGraph ở cả hai độ đo CC và BC.
Độ đo trung tâm Giải pháp đề xuất Công cụ đối chuẩn Đặc tính tối ưu chính
Closeness Centrality (CC) bigGraph (Song song SSSP) NetworKit, TeexGraph, SNAP C++ Tối ưu cache locality, phân chia luồng độc lập, không khóa (lock-free)
Betweenness Centrality (BC) bigGraph (Song song Brandes) NetworKit, TeexGraph Tối ưu pha tích lũy đường đi ngắn nhất, giảm tranh chấp bộ nhớ đa luồng

Chương 5: Kết luận và hướng phát triển

Chương cuối cùng tổng kết các kết quả đạt được của luận án, khẳng định việc hoàn thành các mục tiêu đề ra, thẳng thắn chỉ rõ các hạn chế kỹ thuật hiện tại và vạch ra các hướng nghiên cứu tiếp theo.

Kết quả và những đóng góp mới

Đóng góp về mặt lý luận và mô hình

  1. Mô hình hóa hình thức quá trình xử lý truy vấn trên đồ thị động: Xây dựng mô hình toán học và lịch thi hành biểu diễn các tương tác cập nhật cạnh và truy vấn khoảng cách ngắn nhất đồng thời trên đồ thị quy mô lớn.
  2. Kỹ thuật Heuristic chọn hướng duyệt trong bBFS: Đề xuất phương pháp chuyển đổi hướng duyệt hai chiều không chỉ dựa vào kích thước hàng đợi tức thời mà còn ước lượng số đỉnh bậc hai (đỉnh cháu), giảm thiểu không gian tìm kiếm.

Đóng góp về mặt giải thuật và thực tiễn

  1. Bộ ba giải pháp xử lý đồ thị động (akGroup, akGroupPlus, bigGraph):
    • Đề xuất cấu trúc dữ liệu đồ thị có hướng tối ưu hóa bộ nhớ đệm.
    • Cơ chế song song hóa đồng thời cả thao tác cập nhật cạnh và thao tác truy vấn đường đi ngắn nhất trên CPU đa lõi.
    • Đạt giải Ba cuộc thi quốc tế ACM SIGMOD Programming Contest 2016.
  2. Giải pháp song song hóa tính toán độ đo trung tâm:
    • Xây dựng giải thuật tính $CC$ và $BC$ song song đạt hiệu năng vượt trội so với các thư viện mã nguồn mở chuyên dụng NetworKit và TeexGraph trên các tập dữ liệu mạng xã hội quy mô lớn.
  3. Công bố khoa học: Các kết quả nghiên cứu của luận án đã được công bố tại các hội thảo quốc tế và tạp chí chuyên ngành uy tín:
    • Hội thảo IEEE BDCAT 2016 (công bố giải pháp akGroup).
    • Hội thảo quốc tế ICCCI 2017 (mô hình hóa xử lý truy vấn khoảng cách ngắn nhất).
    • Tạp chí quốc tế Transactions on Computational Collective Intelligence (TCCI), Springer, 2018 (giải pháp hoàn chỉnh cho đồ thị động).
    • Hội thảo quốc tế SoICT 2018 (giải pháp song song hóa tính độ đo trung tâm bigGraph).

Hạn chế và hướng nghiên cứu tiếp

Hạn chế của luận án

  • Loại đồ thị: Luận án mới chỉ tập trung nghiên cứu trên đồ thị không trọng số; chưa mở rộng sang đồ thị có trọng số hoặc đồ thị đa thuộc tính phức tạp.
  • Giới hạn quy mô phần cứng: Do hạ tầng tính toán thực nghiệm giới hạn trên máy chủ đa lõi bộ nhớ chia sẻ, các thử nghiệm chưa thể triển khai trên các đồ thị có quy mô vượt quá 1 tỷ đỉnh (như toàn bộ mạng dữ liệu toàn cầu của Facebook).
  • Phạm vi độ đo trung tâm: Mới tập trung tối ưu hai độ đo chính là Closeness Centrality và Betweenness Centrality trên đồ thị tĩnh, chưa xét cơ chế cập nhật tăng dần (incremental computation) cho các độ đo này khi đồ thị biến động liên tục.

Hạn chế và hướng nghiên cứu tiếp

  1. Mở rộng cấu trúc dữ liệu và giải thuật song song sang các loại đồ thị có trọng số, đồ thị thuộc tính (property graphs) và đồ thị thời gian.
  2. Nghiên cứu kết hợp kiến trúc bộ nhớ chia sẻ đa lõi với các bộ tăng tốc đồ họa chuyên dụng (Multi-GPU) và kiến trúc bộ nhớ lai để xử lý các đồ thị siêu lớn vượt ngưỡng hàng tỷ đỉnh.
  3. Xây dựng các giải thuật cập nhật tăng dần (incremental/dynamic centrality algorithms) cho độ đo trung tâm trung gian và độ trung tâm gần trên đồ thị động.

Giá trị tham khảo

Luận án có giá trị tham khảo chuyên môn đối với các đối tượng:

  • Nghiên cứu sinh, học viên cao học và giảng viên ngành Khoa học máy tính, Hệ thống thông tin: Có thể sử dụng Chương 2 làm tài liệu tham khảo về lý thuyết đồ thị, các phương pháp biểu diễn đồ thị nâng cao (CSR, danh sách liền kề tối ưu), và nguyên lý tính toán song song trên kiến trúc đa lõi (UMA/NUMA, Amdahl).
  • Các kỹ sư phát triển phần mềm và kiến trúc sư hệ thống dữ liệu lớn: Có thể tham khảo trực tiếp mã nguồn, thuật toán và kỹ thuật thiết kế cấu trúc dữ liệu tối ưu bộ nhớ đệm (Chương 3 và Chương 4) để cài đặt các module xử lý đồ thị hiệu năng cao, các công cụ phân tích mạng xã hội nội bộ mà không cần đầu tư hệ thống máy tính cụm tốn kém.
  • Các nhà nghiên cứu trong lĩnh vực Khoa học mạng (Network Science) và Xã hội học tính toán: Cung cấp phương pháp luận và công cụ tính toán chính xác các độ đo trung tâm quan trọng trên tập dữ liệu thực nghiệm lớn trong thời gian tối ưu.

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

1. Luận án giải quyết bài toán tối ưu trên loại đồ thị nào?

Luận án tập trung vào đồ thị không trọng số (cả đồ thị có hướng và vô hướng), bao gồm: (1) đồ thị động quy mô lớn có các thao tác cập nhật cạnh (thêm/xóa cạnh) đan xen với truy vấn khoảng cách ngắn nhất; và (2) đồ thị tĩnh quy mô lớn phục vụ tính toán các độ đo trung tâm mạng xã hội.

2. Điểm khác biệt cốt lõi giữa 3 giải pháp akGroup, akGroupPlus và bigGraph trong Chương 3 là gì?

  • akGroup: Tổ chức dữ liệu danh sách đỉnh đến/đi có chỉ mục, thực hiện cập nhật đồ thị tuần tự trước rồi mới xử lý song song các truy vấn khoảng cách bằng bBFS cải tiến.
  • akGroupPlus: Gắn thông tin trạng thái/phiên bản trực tiếp vào từng cạnh, hỗ trợ xử lý tương tranh giữa thao tác cập nhật và thao tác truy vấn khoảng cách mà không cần khóa dữ liệu toàn cục.
  • bigGraph: Tối ưu hóa cấu trúc dữ liệu dạng mảng liền kề để tăng tối đa tỷ lệ cache hit, đồng thời song song hóa toàn diện cả các phép toán cập nhật lẫn truy vấn khoảng cách ngắn nhất.

3. Kỹ thuật cải tiến thuật toán bBFS của tác giả dựa trên nguyên lý nào?

Thuật toán bBFS thông thường chỉ chọn chiều duyệt tiếp theo dựa trên số lượng đỉnh hiện có trong hàng đợi. Luận án đề xuất kỹ thuật heuristic đánh giá cấu trúc phân nhánh sâu hơn: xem xét tổng bậc của các đỉnh láng giềng (đỉnh con) và các đỉnh bậc hai kế tiếp (đỉnh cháu) của mỗi hàng đợi, từ đó chọn hướng duyệt có số lượng đỉnh mở rộng thực tế ít hơn, giúp giảm đột biến không gian tìm kiếm.

4. Hiệu năng tính độ trung tâm của bigGraph được so sánh với những công cụ nào và kết quả ra sao?

Trong Chương 4, bigGraph được thực nghiệm đối sánh trực tiếp với hai thư viện C++ tính toán song song nổi tiếng là NetworKit và TeexGraph trên các tập dữ liệu mạng xã hội chuẩn từ SNAP. Kết quả cho thấy bigGraph đạt thời gian thi hành ngắn hơn và hệ số tăng tốc (speedup) cao hơn khi tăng số lượng lõi CPU, nhờ loại bỏ được tranh chấp bộ nhớ và khai thác triệt để tính cục bộ dữ liệu bộ nhớ đệm.

Kết luận

Luận án tiến sĩ của tác giả Dư Phương Hạnh đã giải quyết thành công bài toán nâng cao hiệu năng xử lý đồ thị quy mô lớn thông qua việc kết hợp giữa thiết kế cấu trúc dữ liệu tối ưu hóa bộ nhớ đệm CPU và các giải thuật tính toán song song trên kiến trúc đa lõi. Các đóng góp chính bao gồm mô hình hóa xử lý truy vấn trên đồ thị động, đề xuất ba giải pháp tối ưu truy vấn khoảng cách ngắn nhất (akGroup, akGroupPlus, bigGraph), và xây dựng giải thuật song song hiệu năng cao tính toán độ trung tâm gần và độ trung tâm trung gian. Toàn bộ các đề xuất đều được kiểm chứng chặt chẽ bằng thực nghiệm trên các bộ dữ liệu chuẩn, đạt giải thưởng quốc tế và công bố trên các tạp chí, kỷ yếu hội thảo chuyên ngành uy tín.