Ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ họa trong bài toán pagerank

- Phạm Nguyễn Quang Anh ỨNG DỤNG CÔNG NGHỆ TÍNH TOÁN ĐA DỤNG TRÊN CÁC BỘ XỬ LÝ ĐỒ HOẠ TRONG BÀI TOÁN PAGERANK Chuyên ngành: Công nghệ thông tin LUẬN VĂN THẠC SĨ KHOA HỌC CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: T.S.
- Nguyễn Hữu Đức Hà Nội – Năm 2011 Ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ hoạ trong bài toán PageRank Phạm Nguyễn Quang Anh – CHCNTT MỤC LỤC HÌNH ĐẶT VẤN ĐỀ CHƯƠNG I: BÀI TOÁN PAGERANK .
- Các phương pháp xếp hạng trang web dựa vào các siêu liên kết .
- Tính toán vectơ PageRank .
- Kết luận CHƯƠNG 2: GPU VÀ CÔNG NGHỆ TÍNH TOÁN ĐA DỤNG GP-GPU .
- Khả năng tính toán .
- Giải thuật tuần tự Ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ hoạ trong bài toán PageRank Phạm Nguyễn Quang Anh – CHCNTT .
- Hướng phát triển TÀI LIỆU THAM KHẢO Ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ hoạ trong bài toán PageRank Phạm Nguyễn Quang Anh – CHCNTT MỤC LỤC HÌNH Hình 1: Ví dụ về một đồ thị web Hình 2: Node 3 là vũng rank Hình 3: GPU dành cho nhiều transistor hơn CPU để xử lý dữ liệu Hình 4: Số phép tính dấu phẩy động trên giây và băng thông bộ nhớ của CPU và GPU Hình 5: Kiến trúc Tesla Hình 6: CUDA được thiết kế để hỗ trợ nhiều ngôn ngữ hoặc các API khác nhau Hình 7: Khả năng tự mở rộng Hình 8: Lưới của các block Hình 9: Phân cấp bộ nhớ Hình 10: Lập trình không đồng nhất Hình 11: Kiến trúc của một Web Crawler Hình 12: Tính PageRank trên nhiều luồng GPU Hình 13: Giải thuật scan tìm max trên 8 phần tử Hình 14: Cấu trúc bảng băm Hình 15: Các bước xây dựng bảng băm Ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ hoạ trong bài toán PageRank Phạm Nguyễn Quang Anh – CHCNTT ĐẶT VẤN ĐỀ Máy tìm kiếm (Search engine) hiện là công cụ không thể thiếu trong thời đại thông tin, giúp người dùng tìm được những gì mình cần một cách nhanh chóng và chính xác.
- Các máy tìm kiếm lưu trữ thông tin của các trang web trích ra từ các trang html.
- Các trang này được lấy về bởi một Web crawler (còn được gọi là spider.
- một trình duyệt web tự động đi theo các liên kết trên các site.
- Dữ liệu của các trang web được lưu trữ trong một cơ sở dữ liệu chỉ mục, mục tiêu của chỉ mục này là cho phép thông tin được tìm kiếm một cách nhanh nhất.
- Khi người dùng nhập một câu truy vấn (bằng các từ khoá), máy tìm kiếm sẽ kiểm tra bộ chỉ mục của nó và cung cấp một danh sách các trang khớp nhất theo tiêu chí của mình.
- Có thể có hàng triệu trang web có chứa một từ hoặc cụm từ xác định, một vài trang lại có mức độ liên quan, độ quan trọng cao hơn các trang khác.
- Cách thức máy tìm kiếm xác định trang web nào là khớp nhất, thứ tự hiển thị các kết quả là khác nhau giữa các máy tìm kiếm.
- Ví dụ, nhiều Máy tìm kiếm đặt các trang web có từ khoá tìm kiếm ở tiêu để có trọng số cao hơn các trang có các từ đó ở trong thân bài.
- Độ quan trọng của văn bản mà chúng ta sẽ chú trọng trong đồ án này được xác định bằng việc phân tích cấu trúc các siêu liên kết (hyperlink) của web.
- Năm 1998, Sergey Brin và Larry Page đưa ra một công thức tính độ quan trọng của trang web gọi là PageRank [1].
- PageRank đã được Google sử dụng cho Máy tìm kiếm Ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ hoạ trong bài toán PageRank Phạm Nguyễn Quang Anh – CHCNTT của mình.
- Tư tưởng của PageRank là thông tin trên web có thể được phân cấp bởi mức độ nổi tiếng dựa trên liên kết: một trang web được sắp xếp cao hơn nếu có nhiều liên kết trỏ đến nó hơn.
- PageRank của một trang được định nghĩa một cách đệ quy và phụ thuộc vào số lượng và giá trị PageRank của tất cả các trang trỏ đến nó.
- Mặc dù chỉ là một trong các yếu tố quyết định thứ tự các kết quả trả về, PageRank luôn là nền tảng của tất cả các công cụ tìm kiếm của Google và đã cho thấy được sự vượt trội so với các phương pháp phân tích cấu trúc liên kết khác.
- Việc tính toán PageRank được thực hiện trên lượng dữ liệu khổng lồ (hàng triệu đến hàng tỷ trang web) và đòi hỏi một khối lượng tính toán lớn.
- Theo ước tính, số lượng trang web trên World Wide Web hiện là khoảng hơn 40 tỷ.
- Với kích thước dữ liệu lớn như vậy, việc tính toán PageRank là một thách thức không nhỏ.
- Thứ nhất, nội dung của từng trang web có thể thay đổi liên tục.
- Điều này dẫn tới sự thay đổi trong các liên kết của trang web và tương ứng là sự thay đổi của cấu trúc web.
- Thứ hai, kích thước của World Wide Web tính theo số trang web tăng lên liên tục.
- Có hàng tỷ trang web mới được tạo ra mỗi năm.
- Tính động của World Wide Web khiến việc tính toán PageRank gặp nhiều khó khăn.
- Để các giá trị PageRank luôn được cập nhật trước sự thay đổi không ngừng của World Wide Web thì giai đoạn tính toán PageRank phải được thực hiện liên tục trong thời gian càng ngắn càng tốt.
- Điều này đòi hỏi các hệ thống đủ mạnh cho nhu cầu tính toán này.
- Luận văn hướng đến việc ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ họa (GPGPU – General Purpose Computation on Graphic Processing Units) cho bài toán PageRank.
- GPGPU [7] là công nghệ sử dụng bộ xử lý đồ hoạ (GPU) để thực hiện các ứng dụng tính toán vốn được tiến hành trên CPU.
- Năng lực tính toán của các GPU tỏ ra vượt trội so với bộ xử lý của Intel với khả năng song song hoá cao trên rất nhiều luồng.
- GPGPU Ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ hoạ trong bài toán PageRank Phạm Nguyễn Quang Anh – CHCNTT đã được áp dụng trên nhiều lĩnh vực đòi hỏi khối lượng tính toán lớn như tin sinh, xử lý tín hiệu số, mã hoá và thám mã, mô phỏng, các bài toán khai phá dữ liệu,… Phạm vi của đồ án: Đồ án sẽ nghiên cứu về lý thuyết PageRank, tư tưởng hình thành của nó, cách thức mô hình hoá bài toán.
- Đồ án sẽ đề xuất phương pháp tính toán PageRank bằng giải thuật tuần tự trên CPU.
- Từ giải thuật tuần tự này, đồ án sẽ nghiên cứu hướng song song hoá giải thuật, cách tổ chức cấu trúc dữ liệu, các thao tác tối ưu hoá do tác giả đề ra để thực hiện việc tính toán trên GPU.
- Cuối cùng, các thử nghiệm trên các bộ dữ liệu thực tế sẽ được thực hiện để đo đạc khả năng tăng tốc khi tính toán PageRank trên GPU so với trên CPU.
- Chương 1: Chương này tìm hiểu các phương pháp đánh giá trang web dựa trên các siêu liên kết, trong đó tập trung vào phương pháp PageRank: ý tưởng xây dựng nên PageRank, các bước xây dựng, điều chỉnh, hoàn thiện công thức.
- Chương 2: Giới thiệu công nghệ tính toán song song đa dụng trên các bộ xử lý đồ hoạ GPU.
- Chương 4: Trình bày các thử nghiệm, so sánh hiệu năng tính toán thông qua thời gian thực hiện của hai chương trình tuần tự và song song.
- Ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ hoạ trong bài toán PageRank Phạm Nguyễn Quang Anh – CHCNTT CHƯƠNG I: BÀI TOÁN PAGERANK Trong chương này chúng ta sẽ tìm hiểu các phương pháp xếp hạng trang web dựa trên cấu trúc của các siêu liên kết trong đó tập trung vào giải thuật PageRank.
- Chương này sẽ trình bày tư tưởng cơ bản của PageRank, cách biểu diễn PageRank bằng công thức toán học, các điều chỉnh đối với công thức này để phục vụ cho việc tính toán.
- Các phương pháp xếp hạng trang web dựa vào các siêu liên kết Trong phần này chúng ta tìm hiểu các phương pháp xếp hạng trang web.
- Cấu trúc liên kết của Web tạo nên một đồ thị có hướng.
- Các node của đồ thị biểu diễn một trang web và các cung có hướng thể hiện các siêu liên kết.
- Các liên kết đi đến một trang được gọi là các liên kết vào (inlink), và các liên kết xuất phát từ một trang được gọi là các liên kết ra (outlink).
- HITS sử dụng cả liên kết vào và liên kết ra để tính mức độ nổi tiếng của từng trang web.
- Một trang web được coi là hub nếu nó có nhiều liên kết ra, và trang web có nhiều liên kết vào được coi là authority.
- HITS sẽ tính toán cả hai thước đo cho mỗi trang web: giá trị authority – đánh giá giá trị của nội dung của trang và giá trị hub – đánh giá giá trị các liên kết mà trang web trỏ tới các trang khác.
- Tư tưởng của HITS là: một trang là một hub tốt (có giá trị hub cao) khi nó trỏ tới các authority tốt, và Ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ hoạ trong bài toán PageRank Phạm Nguyễn Quang Anh – CHCNTT một trang web là một authority tốt nếu nó được trỏ bởi các hub tốt.
- Với k Giả sử mỗi trang web được gán giá trị khởi tạo (0)ix và (0)iy) Việc tính toán HITS được chia ra làm 2 bước chính.
- Do đó ở bước thứ nhất, một đồ thị N liên quan đến các từ khoá tìm kiếm bao gồm các trang web có chứa các từ khoá này.
- Có nhiều cách để tìm ra các trang này, một trong số đó là sử dụng chỉ mục file ngược (inverted file index), ví dụ: Từ khoá ID các trang web Term Term Term N .
- Ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ hoạ trong bài toán PageRank Phạm Nguyễn Quang Anh – CHCNTT Sau khi N được dựng nên, việc tính HITS được thực hiện trên đồ thị này.
- Vòng lặp tính toán sẽ dừng khi ta đạt được độ chính xác mong muốn.
- HITS đưa ra hai danh sách đã sắp xếp cho người dùng: một danh sách với các trang có giá trị authority cao và một danh sách với các trang có giá trị hub cao.
- Đôi khi người dùng muốn các trang có authority cao bởi vì họ cần tìm sâu vào một truy vấn.
- Ở lần khác, họ có thể muốn các trang có hub cao khi họ đang tìm kiếm một cách rộng rãi.
- HITS đưa bài toán xếp hạng về một bài toán nhỏ hơn với các trang web liên quan đến từ khoá truy vấn.
- Kích thước của đồ thị này nhỏ hơn rất nhiều so với tổng số trang web trên web.
- Phương pháp PageRank Năm 1998, Page và Brin [1] đưa ra một phương pháp đánh giá các trang web sựa trên các liên kết vào của chúng, gọi là PageRank.
- Tư tưởng của PageRank là: một trang web là quan trọng nếu nó được trỏ bởi các trang web quan trọng.
- Việc hình thành công thức PageRank được dựa trên một giả định là mỗi một siêu liên kết là một sự giới thiệu.
- Một siêu liên kết từ trang web A tới trang B là một sự ghi nhận của A đối với B.
- Do đó, một trang có nhiều sự giới thiệu (mà được xác định qua số liên Ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ hoạ trong bài toán PageRank Phạm Nguyễn Quang Anh – CHCNTT kết vào) phải quan trọng hơn trang có ít liên kết vào.
- Tuy nhiên trạng thái của trang web giới thiệu cũng cần được xét tới, tức là trọng số của trang web giới thiệu là nhỏ nếu trang đó có nhiều liên kết ra và ngược lại.
- Một cách khác, một trang có rank cao nếu tổng số rank của các liên kết vào nó là cao.
- Điều này đúng với cả hai trường hợp khi trang có nhiều liên kết vào và trang có một vài liên kết vào có trọng số cao.
- Giá trị này bằng tổng các PageRank của các trang web trỏ tới Pi.
- (1) Trong đó, PiB là tập các trang trỏ đến Pi và jP là số lượng liên kết ra của Pj.
- Vấn đề với công thức này là giá trị ( )jr P, PageRank của trang web trỏ vào Pi vẫn chưa được tính toán.
- Họ giả sử rằng ban đầu tất cả các trang web có giá trị PageRank như nhau (là 1/n với n là tổng số lượng trang web có được).
- 1/ir P n cho tất các trang Pi và được lặp lại cho đến khi các giá trị PageRank hội tụ đến một giá trị cuối cùng.
- Ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ hoạ trong bài toán PageRank Phạm Nguyễn Quang Anh – CHCNTT Giả sử chúng ta có đồ thị web như Hình 1.
- Hình 1: Ví dụ về một đồ thị web Ta sẽ có PageRank của các trang web sau 2 vòng lặp đầu như sau: Ban đầu Vòng lặp 1 Vòng lặp 2 Thứ tự sau vòng lặp 2 r0(P1.
- Biểu diễn công thức dưới dạng ma trận: Ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ hoạ trong bài toán PageRank Phạm Nguyễn Quang Anh – CHCNTT Các công thức (1) và (2) tính PageRank cho từng trang tại một thời điểm.
- Sử dụng ma trận, tại mỗi vòng lặp chúng ta tính một vectơ PageRank, là một vectơ 1n lưu giữ các giá trị PageRank của toàn bộ trang web chúng ta có.
- Chúng ta sử dụng một vectơ 1n để biểu diễn các giá trị PageRank của tất cả trang web.
- Ma trận H là một ma trận siêu liên kết chuẩn hoá theo hàng với ij1/iH P nếu có một cạnh từ điểm i tới điểm j, và 0 nếu ngược lại.
- Giả sử với đồ thị ở hình 1, chúng ta có ma trận H như sau: Các phần tử khác không ở hàng i tương ứng với các liên kết ra của trang i, trong khi đó các phần tử khác không ở cột i tương ứng với các liên kết vào của trang i.
- (3) Từ công thức (3), chúng ta có các nhận xét sau: Ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ hoạ trong bài toán PageRank Phạm Nguyễn Quang Anh – CHCNTT 2009 - 13.
- H là ma trận rất thưa (phần lớn các phần tử bằng 0) bởi hầu hết các trang web chỉ trỏ tới một lượng nhỏ các trang web khác.
- Thứ hai, việc nhân vectơ với ma trận thưa có khối lượng tính toán ít hơn nhiều so với O(n2) của ma trận dày.
- Trên thực tế, nó có độ phực tạp tính toán là O(nnz(H.
- Ước lượng cho thấy rằng các trang web có trung bình 10 liên kết ra, có nghĩa là H có khoảng 10n phần tử khác không, so với n2 phần tử khác không của một ma trận dày hoàn toàn.
- Ví dụ, một vấn đề gọi là vũng rank, là các trang web tích luỹ ngày càng nhiều PageRank sau mỗi vòng lặp, chiếm gần hết điểm số của các trang khác mà không chia sẻ.
- Ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ hoạ trong bài toán PageRank Phạm Nguyễn Quang Anh – CHCNTT Ví dụ này còn cho thấy một vấn đề khác của PageRank gây ra bởi các vũng.
- Một người lướt web ngẫu nhiên sẽ đi một cách ngẫu nhiên dọc theo cấu trúc siêu liên kết của Web.
- Khi đến một node với một vài liên kết ra, anh ta sẽ chọn một trong số chúng một cách ngẫu nhiên, đi đến một trang khác và tiếp tục quá trình này vô tận.
- Tỷ lệ thời gian mà người duyệt web dừng ở một trang xác định là thước đo độ quan trọng tương đối của trang web đó.
- Node treo là các node không có liên kết ra.
- Với cấu trúc web như ở hình 1, ta có ma trận ngẫu nhiên như sau: Ứng dụng công nghệ tính toán đa dụng trên các bộ xử lý đồ hoạ trong bài toán PageRank Phạm Nguyễn Quang Anh – CHCNTT Ta có thể thấy rằng: (1/ )TS H a ne.
- S là ma trận có được bởi sự kết hợp giữa ma trận siêu liên kết ban đầu và mà trận cấp một 1/Tne.
- Điều chỉnh này như sau: khi những người duyệt web đi theo cấu trúc siêu liên kết của Web, sẽ có những thời điểm họ cảm thấy chán và bỏ cách duyệt web theo các siêu liên kết mà nhập một địa chỉ mới vào thanh địa chỉ của trình duyệt.
- Khi việc này xảy ra, người duyệt web ngẫu nhiên sẽ "nhảy" đến một trang mới, từ đó anh ta tiếp tục duyệt web theo các siêu liên kết cho đến lần nhảy tiếp theo, và tiếp tục như vậy.
- là tham số quyết định tỷ lệ thời gian người duyệt web ngẫu nhiên đi theo các siêu liên kết và thời gian anh ta nhảy ngẫu nhiên.
- 0,6 khi đó 60% thời gian người duyệt web ngẫu nhiên đi theo các siêu liên kết và 40% thời gian anh ta nhảy đến một trang ngẫu nhiên.
- G là tối giản: mọi trang web được nối trực tiếp đến mọi trang web khác

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt