Luận án TS: Nâng cao hiệu năng thi hành các phép toán trên đồ thị

Luận án Nâng cao hiệu năng thi hành các phép toán trên đồ thị mô hình hoá quá trình xử lý các truy vấn khoảng cách ngắn nhất trên đồ thị động, quy mô lớn dựa vào lịch thi hành phép toán đồng thời và dựa vào cấu trúc dữ liệu phù hợp cho phép nâng cao hiệu năng bộ nhớ đệm cache; đề xuất ba giải pháp (akGroup, akGroupPlus và bigGraph) để nâng cao hiệu năng thi hành các truy vấn đồng thời trên đồ thị động quy mô lớn với khả năng thi hành song song cả các truy vấn duyệt đồ thị lẫn cập nhật đồ thị; xây dựng hai giải thuật nâng cao hiệu năng quá trình tính độ trung tâm gần và độ trung tâm trung gian trên đồ thị quy mô lớn.

Luận án TS: Nâng cao hiệu năng thi hành các phép toán trên đồ thị

1. Mở đầu

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

Nghiên cứu, khảo sát và đánh giá một số phương pháp, kỹ thuật tổ chức dữ liệu đồ thị cũng như các phép toán cơ bản trên đồ thị.

Nghiên cứu 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 một số giải pháp để nâng cao hiệu năng thi hành các truy vấn khoảng cách ngắn nhất trên đồ thị động, quy mô lớn dựa trên cách tiếp cận tổ chức dữ liệu phù hợp và tính toán song song.

Nâng cao hiệu năng một số giải thuật tính các độ đo phục vụ các phép toán phân tích đồ thị dựa trên cách tiếp cận tổ chức dữ liệu phù hợp và tính toán song song.

Tiến hành cài đặt thử nghiệm các giải pháp đã xây dựng trong luận án; đánh giá và so sánh với một số giải pháp hiện có dựa trên những bộ dữ liệu chuẩn. 

1.2 Phạm vi nghiên cứu

Chúng tôi chỉ chú trọng đến bài toán nghiên cứu trên đồ thị không trọng số. Đối với bài toán xử lý các truy vấn khoảng cách ngắn nhất trên đồ thị động, chúng tôi quan tâm đến đồ thị có hướng, không trọng số với các phép toán thêm cạnh, xoá cạnh (từ đó có thể hình thành các phép toán thêm/xoá đỉnh) và truy vấn khoảng cách ngắn nhất giữa hai đỉnh. Đối với các phép toán hỗ trợ phân tích đồ thị quy mô lớn, chẳng hạn như các mạng xã hội, một số độ đo trung tâm sẽ được quan tâm, đề xuất giải pháp nâng cao hiệu năng tính toán các độ đo này trong luận án.

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

Về phương pháp nghiên cứu, trong luận án này chúng tôi sẽ kết hợp cả phương pháp nghiên cứu lý thuyết lẫn nghiên cứu thực nghiệm. Về nghiên cứu lý thuyết, chúng tôi sẽ tiến hành thu thập các tài liệu khoa học đã được công bố tại các nhà xuất bản, trường Đại học có uy tín trong và ngoài nước để từ đó phân tích, đánh giá những phương pháp, kỹ thuật cũng như kết quả thu được trong lĩnh vực liên quan đến bài toán nghiên cứu của luận án. Các đề xuất trong luận án cũng được chú trọng phân tích, đánh giá tường minh về tính đúng đắn, độ phức tạp về mặt lý thuyết. Về nghiên cứu thực nghiệm, chúng tôi sẽ áp dụng phương pháp thực nghiệm đối với toàn bộ các giải pháp, đề xuất của chúng tôi để kiểm nghiệm lại kết quả lý thuyết. Việc thực nghiệm cũng được tiến hành trên những bộ dữ liệu thường xuyên được cộng đồng nghiên cứu sử dụng và trên cùng nền tảng tính toán để có thể so sánh với những giải pháp khác đã được công bố.

2. Nội dung

2.1 Giới thiệu chung

Động lực nghiên cứu

  • Cấu trúc dữ liệu phù hợp để nâng cao hiệu năng thi hành các phép toán trên đồ thị
  • Xử lý các truy vấn khoảng cách ngắn nhất trên đồ thị động quy mô lớn 
  • Nâng cao hiệu năng tính các độ đo quan trọng trong phân tích đồ thị quy mô lớn 

Một số nghiên cứu liên quan

Mục tiêu, phạm vi nghiên cứu, đóng góp và bố cục của luận án

  • Mục tiêu nghiên cứu
  • Phạm vi và phương pháp nghiên cứu 

Các đóng góp chính của luận án

Tổ chức của luận án 

2.2 Cơ sở lí thuyết

Lý thuyết đồ thị 

  • Khái niệm
  • Kiểu đồ thị
  • Các đặc điểm chính của đồ thị

Biểu diễn đồ thị 

  • Danh sách các cạnh
  • Ma trận liền kề 
  • Danh sách liền kề 
  • Ma trận liên thuộc  
  • Ma trận hàng thưa nén 

Các phép toán chính trên đồ thị 

  • Duyệt đồ thị 
  • Phân tích đồ thị 
  • Mật độ đồ thị 
  • Phân cụm đồ thị 

Tính toán song song 

  • Kiến trúc hệ thống tính toán song song 
  • Mô hình lập trình song song 
  • Một số bài toán song song điển hình .

2.3 Tối ưu hóa truy vấn khoảng cách ngắn nhất

Giới thiệu 

Đặc tả bài toán 

  • Mô hình dữ liệu và truy vấn 
  • Bài toán tối ưu hoá truy vấn khoảng cách ngắn nhất trên đồ thị động 
  • Cách tiếp cận giải quyết bài toán đặt ra  

Giải pháp 1: akGroup 

  • Cấu trúc dữ liệu đồ thị phù hợp 
  • Tối ưu hoá các phép toán cập nhật
  • Tối ưu các truy vấn 
  • Đánh giá thuật toán 

Giải pháp 2: akGroupPlus 

  • Tổ chức dữ liệu đồ thị kèm trạng thái
  • Xử lý các phép toán tương tranh 
  • Tối ưu hoá các phép toán cập nhật 
  • Tối ưu hoá các truy vấn tính khoảng cách ngắn nhất
  • Đánh giá thuật toán 

Giải pháp 3: bigGraph 

  • Ý tưởng chính 
  • Giải thuật song song hoá các phép toán cập nhật
  • Đánh giá thuật toán 

Thực nghiệm và đánh giá

  • Môi trường và dữ liệu thực nghiệm 
  • Phương pháp thử nghiệm, đánh giá 
  • Thử nghiệm và đánh giá kết quả 

2.4 Nâng cao hiệu năng

Giới thiệu 

Bài toán đặt ra

  • Tính độ trung tâm gần
  • Tính độ trung tâm trung gian  

Nâng cao hiệu năng tính độ trung tâm

  • Cấu trúc dữ liệu phù hợp 
  • Giải thuật song song tính độ trung tâm gần 
  • Giải thuật song song tính độ trung tâm trung gian

Thực nghiệm và đánh giá 

  • Môi trường thử nghiệm, đánh giá 
  • Dữ liệu thực nghiệm
  • Kết quả thực nghiệm và đánh giá 

3. Kết luận

Thực tế đã chứng minh được tính hiệu quả của lý thuyết đồ thị trong những bài toán thực tiễn, chẳng hạn như mô hình hoá các phép toán trên mạng xã hội Facebook, Twitter... Luận án này quan tâm đến việc ứng dụng lý thuyết đó để giải quyết bài toán quan trọng: nâng cao hiệu năng xử lý các phép toán đồng thời trên đồ thị. Với định hướng đó, chúng tôi đã tiến hành xác lập mục tiêu và các nội dung nghiên cứu chính của luận án (đã trình bày ở Chương 1). Qua các kết quả cả về lý thuyết lẫn thực nghiệm đã được trình bày cụ thể trong luận án, có thể khẳng định rằng toàn bộ mục tiêu và các nội dung nghiên cứu đề ra đã được hoàn thành, với các đóng góp chính bao gồm:

  • Mô hình hoá quá trình xử lý các phép toán tương tranh trên đồ thị quy mô lớn dựa vào lịch thi hành các phép toán đồng thời và dựa vào cấu trúc dữ liệu phù hợp; từ đó cho phép nâng cao hiệu năng bộ nhớ đệm cache và giảm thời gian truy xuất đến bộ nhớ chính.
  • Đề xuất ba giải pháp (akGroup, akGroupPlus và bigGraph) để nâng cao hiệu năng thi hành các truy vấn đồng thời trên đồ thị động quy mô lớn với khả năng thi hành song song cả các truy vấn duyệt đồ thị lẫn cập nhật đồ thị.
  • Nâng cao hiệu năng quá trình tính hai độ đo trung tâm: độ trung tâm gần và độ trung tâm trung gian trên đồ thị quy mô lớn, với giải pháp bigGraph được xây dựng dựa trên việc tổ chức dữ liệu đồ thị phù hợp và song song hoá các phép tính SSSP trên mỗi thành viên của mạng.

4. Tài liệu tham khảo

S. Adve, V. Adve, G. Agha, M. I Frank María, M. Garzarán, J. Hart, W.-m. Hwu, R. Johnson, K. Rakesh Kumar, D. Marinov, K. Nahrstedt, D. Padua, M. Parthasarathy, S. Patel Grigore Rosu, D. Roth, M. Snir, J. Torrellas, and C. Zilles. Parallel computing research at illinois the upcrc agenda. November 2008.

R. Alhajj and J. Rokne. Encyclopedia of Social Network Analysis and Mining. Springer, 1st edition, 2014. ISBN 978-1-4614-6169-2.

G. S. Almasi and A. Gottlieb. Highly Parallel Computing. Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, USA, 1989. ISBN 0-8053-0177-1.

K. Asanovic, R. Bodik, B. Catanzaro, J. James Gebis, P. Husbands, K. Keutzer, D. A. Patterson, W. Plishker, J. Shalf, S. Williams, and K. Yelick. The landscape of parallel computing research: A view from berkeley. EECS Department, University of California, Berkeley, EECS-2006-183:56, 12 2006....

--- Nhấn nút TẢI VỀ hoặc XEM ONLINE để tham khảo đầy đủ nội dung Luận án Tiến sĩ trên ---

Ngày:18/08/2020 Chia sẻ bởi:

CÓ THỂ BẠN QUAN TÂM