Ứng dụng tính toán đa dụng trên các bộ xử lý đồ họa đa lõi vào tăng tốc bài toán PageRank


PageRank, một phương pháp đánh giá độ quan trọng của các trang web dựa trên siêu liên kết, là nền tảng cho việc xếp hạng trang web trong máy tìm kiếm Google và nhiều máy tìm kiếm khác.Tuy nhiên, việc tính toán PageRank là một thách thức không nhỏ do số lượng website ngày càng lớn (ước tính hơn 40 tỷ trang). Đồng  thời, môi trường World Wide Web lại có sự thay đổi liên tục về cấu trúc liên kết và số lượng các trang web.Trong khi đó, để phục vụ cho truy vấn, giá trị PageRank cuả các trang web lại phải được cập nhật liên tục và cần thực hiện trong khoảng thời gian ngắn. Bài báo này đưa ra cách tiếp cận sử dụng năng lực tính toán song song rất lớn của các bộ xử lý đồ họa đa lõi để tăng tốc quá trình tính toán PageRank.

Bài báo trước hết sử dụng một định dạng gọi là binary link structure file [3] để lưu trữ dữ liệu đồ thị web. Sau đó tiến hành song song hóa giải thuật PageRank để thực hiện tính toán trên các lõi của GPU. Chương trình  được  viết  bằng  ngôn  ngữ  CUDA và thử nghiệm trên hệ thống trang bị 2 card kép NVIDIA Geforce GTX 295 (tổng cộng 4GPU), sử dụng bộ dữ liệu thực tế là tập các trang web tiếng việt được crawling tại Việt Nam từ tháng 1/2011 tới  tháng  2/2011, gồm 7 triệu trang web, 132 triệu liên kết. Các kết quả thử nghiệm cho thấy chương trình tính PageRank song song nhanh hơn từ 10 lần (1GPU) đến 20 lần (4GPU) so với một phiên bản tuần tự trên CPU  Intel Core 2 Quad Q8400 2.67GHz. Kết quả này minh chứng khả năng ứng dụng công nghệ tính toán trên các bộ xử lý đồ họa trong lĩnh vực tính toán PageRank.

LINK DOWNLOAD


PageRank, một phương pháp đánh giá độ quan trọng của các trang web dựa trên siêu liên kết, là nền tảng cho việc xếp hạng trang web trong máy tìm kiếm Google và nhiều máy tìm kiếm khác.Tuy nhiên, việc tính toán PageRank là một thách thức không nhỏ do số lượng website ngày càng lớn (ước tính hơn 40 tỷ trang). Đồng  thời, môi trường World Wide Web lại có sự thay đổi liên tục về cấu trúc liên kết và số lượng các trang web.Trong khi đó, để phục vụ cho truy vấn, giá trị PageRank cuả các trang web lại phải được cập nhật liên tục và cần thực hiện trong khoảng thời gian ngắn. Bài báo này đưa ra cách tiếp cận sử dụng năng lực tính toán song song rất lớn của các bộ xử lý đồ họa đa lõi để tăng tốc quá trình tính toán PageRank.

Bài báo trước hết sử dụng một định dạng gọi là binary link structure file [3] để lưu trữ dữ liệu đồ thị web. Sau đó tiến hành song song hóa giải thuật PageRank để thực hiện tính toán trên các lõi của GPU. Chương trình  được  viết  bằng  ngôn  ngữ  CUDA và thử nghiệm trên hệ thống trang bị 2 card kép NVIDIA Geforce GTX 295 (tổng cộng 4GPU), sử dụng bộ dữ liệu thực tế là tập các trang web tiếng việt được crawling tại Việt Nam từ tháng 1/2011 tới  tháng  2/2011, gồm 7 triệu trang web, 132 triệu liên kết. Các kết quả thử nghiệm cho thấy chương trình tính PageRank song song nhanh hơn từ 10 lần (1GPU) đến 20 lần (4GPU) so với một phiên bản tuần tự trên CPU  Intel Core 2 Quad Q8400 2.67GHz. Kết quả này minh chứng khả năng ứng dụng công nghệ tính toán trên các bộ xử lý đồ họa trong lĩnh vực tính toán PageRank.

LINK DOWNLOAD

M_tả
M_tả

Không có nhận xét nào: