Ứng dụng GPU trong tính toán PageRank: Nghiên cứu và triển khai

Luận văn về ứng dụng công nghệ tính toán đa dụng trên GPU giải quyết bài toán Pagerank. Tối ưu hiệu năng, tăng tốc độ xử lý dữ liệu lớn.

Trường đại học

Trường Đại học Bách Khoa Hà Nội

Chuyên ngành

Công nghệ thông tin

Người đăng

Ẩn danh

Thể loại

Luận văn thạc sĩ

2011

Phí lưu trữ

30 Point

Mục lục chi tiết

MỤC LỤC

HÌNH

DAT VAN DE

1. CHƯƠNG I: BÀI TOÁN PAGERANK

1. Các phương pháp xếp hạng trang web dựa vào các siêu liên kết. Các phương pháp xếp hạng trang web dựa vào các siêu liên kết

1.1. Hyperink-Induced Topic Search (HIIS)

2. Phương pháp PageRank

3. Tính toán vectơ PageRank

4. Tham số % trong mô hình PageRank

2. CHƯƠNG 2: GPU VÀ CÔNG NGHỆ TÍNH TOÁN ĐÁ DỤNG GP-GPU

1. Các bộ xử lý đồ họa đa lỗi của Nvidia

2. Kiến trac cia GPU Tesla

3. Môi trường phát triển ứng dụng cho GPU_ CƯDA

3.1. Khả năng mở rộng của CUDA Tri

3.2. Các khải niệm chúnh: eel

3.3. Lập trinh khong déng mbit

3.4. Khả năng tính toán

3.5. Giao diện lập trinh

3.6. Biên dich với NVCC

3. CHƯƠNG 3: AP DUNG GPU TRONG TINH PAGERANK

1. Tiền xử lý dữ liệu

2. IIướng tiếp cận - giải thuật

3. Giải thuật tuần tự

4. Tưởng song song hoá

5. Thao tac nguyén tu (atomic operation)

6. Điều kiện dùng

7. Tam trữ dồ thị

8. Bang bam

8.1. Xây dựng bảng băm

4. CHƯƠNG 4: TIỮ NGIIỆM VÀ ĐÁNIT GIÁ

5. CHUGONG 5: KET LUAN VA HUGNG PHAT TRIEN

1. Hướng phát triển

TAI LIEU THAM KHAO

Tóm tắt

I. Tổng Quan Ứng Dụng GPU Tính Toán PageRank Khám Phá Tiềm Năng

Thuật toán PageRank, nền tảng của các công cụ tìm kiếm, đòi hỏi khả năng xử lý dữ liệu khổng lồ. Việc tính toán PageRank trên toàn bộ đồ thị web là một thách thức lớn do kích thước và tính động của dữ liệu. Tính toán đa dụng trên GPU (GPGPU) nổi lên như một giải pháp đầy hứa hẹn, tận dụng sức mạnh song song của bộ xử lý đồ họa (GPU) để tăng tốc đáng kể quá trình này. Luận văn này đi sâu vào việc ứng dụng công nghệ tính toán đa dụng trên GPU cho bài toán PageRank, khám phá các phương pháp tối ưu hóa và đánh giá hiệu năng trên các bộ dữ liệu thực tế. 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ỏ. 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) cho bài toán PageRank. GPGPU là công nghệ sử dụng bộ xử lý đồ họa (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.

1.1. Giới thiệu bài toán PageRank và vai trò của GPU

Bài toán PageRank là một bài toán quan trọng trong lĩnh vực tìm kiếm thông tin và phân tích mạng xã hội. Nó được sử dụng để đánh giá độ quan trọng của các trang web dựa trên cấu trúc liên kết của chúng. GPU có kiến trúc song song, thích hợp cho việc thực hiện các phép tính ma trận lớn trong bài toán PageRank. GPU có khả năng thực hiện hàng ngàn phép tính đồng thời, giúp giảm đáng kể thời gian tính toán so với CPU. Việc tận dụng kiến trúc GPU để tính toán PageRank là một hướng nghiên cứu đầy tiềm năng, đặc biệt trong bối cảnh dữ liệu web ngày càng lớn và phức tạp. PageRank đã được Google sử dụng cho Máy tìm kiếm của mình. 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.

1.2. Tổng quan về công nghệ tính toán đa dụng trên GPU GPGPU

GPGPU cho phép sử dụng GPU không chỉ cho các tác vụ đồ họa mà còn cho các tác vụ tính toán khoa học và kỹ thuật. Các ngôn ngữ lập trình như CUDA và OpenCL cung cấp các công cụ để khai thác sức mạnh của GPU. CUDA là một nền tảng lập trình song song và một mô hình tính toán được phát triển bởi NVIDIA. Nó cho phép các nhà phát triển phần mềm sử dụng GPU của NVIDIA cho các mục đích tính toán chung. OpenCL là một tiêu chuẩn mở để lập trình song song trên nhiều loại bộ xử lý, bao gồm GPU, CPU và các thiết bị gia tốc khác. GPGPU đã được ứng dụng trong nhiều lĩnh vực, bao gồm tin sinh, xử lý tín hiệu số, mã hóa và khai phá dữ liệu. GPU có nhiều transistor hơn CPU để xử lý dữ liệu. 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.

1.3. Tại sao GPU lại phù hợp với bài toán PageRank

Bài toán PageRank có tính song song cao, nghĩa là nhiều phép tính có thể được thực hiện đồng thời. GPU với hàng ngàn lõi xử lý có thể thực hiện các phép tính này một cách hiệu quả. Bên cạnh đó, băng thông bộ nhớ lớn của GPU cho phép truy cập dữ liệu nhanh chóng, một yếu tố quan trọng để tối ưu hóa hiệu năng của thuật toán PageRank. GPU dành nhiều transistor hơn CPU để xử lý dữ liệu. GPGPU đã đượ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.

II. Vấn Đề Giới Hạn CPU và Nhu Cầu Tốc Độ Tính PageRank

Việc tính toán PageRank trên CPU gặp phải nhiều giới hạn do kiến trúc tuần tự của nó. Thời gian tính toán có thể kéo dài đáng kể, đặc biệt khi xử lý đồ thị web có kích thước lớn. Điều này gây khó khăn cho việc cập nhật PageRank thường xuyên, ảnh hưởng đến chất lượng của kết quả tìm kiếm. CPU có thể không đáp ứng được nhu cầu tính toán song song của bài toán PageRank. CPU có ít phép tính dấu phẩy động trên giây và băng thông bộ nhớ thấp hơn GPU. 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.

2.1. Phân tích các hạn chế của CPU trong bài toán PageRank

CPU được thiết kế cho các tác vụ đa năng, không chuyên biệt cho tính toán song song. Số lượng lõi xử lý trên CPU thường ít hơn nhiều so với GPU, hạn chế khả năng xử lý song song. CPU có độ trễ cao khi truy cập bộ nhớ, ảnh hưởng đến hiệu năng của các thuật toán truy cập dữ liệu nhiều như PageRank. Do kiến trúc tuần tự, CPU không thích hợp cho việc tối ưu hóa hiệu năng của thuật toán PageRank.

2.2. Tầm quan trọng của tốc độ tính toán PageRank trong thực tế

Tốc độ tính toán PageRank ảnh hưởng trực tiếp đến khả năng cung cấp kết quả tìm kiếm nhanh chóng và chính xác. Việc cập nhật PageRank thường xuyên giúp phản ánh những thay đổi trên web, đảm bảo tính актуальность của kết quả tìm kiếm. Tốc độ tính toán PageRank là yếu tố cạnh tranh quan trọng giữa các công cụ tìm kiếm. Một máy tìm kiếm cần phải 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. Sự hữu dụng của máy tìm kiếm phụ thuộc vào mức độ liên quan của lập kết quả trả về.

2.3. Bài toán PageRank và đặc điểm tính toán song song

Bài toán PageRank có thể chia thành các phép tính độc lập trên từng trang web, cho phép thực hiện song song. Việc tính toán giá trị PageRank của một trang web chỉ phụ thuộc vào giá trị PageRank của các trang web liên kết đến nó. Điều này tạo ra cơ hội lớn để tăng tốc quá trình tính toán bằng cách sử dụng GPU. GPU được thiết kế để hỗ trợ nhiều ngôn ngữ hoặc các API khác nhau.

III. Cách Tiếp Cận Phương Pháp Tính Toán PageRank trên GPU GPGPU

Luận văn này đề xuất một phương pháp tính toán PageRank hiệu quả trên GPU, sử dụng CUDA để khai thác sức mạnh song song của kiến trúc GPU. Phương pháp này bao gồm các bước: tiền xử lý dữ liệu, triển khai thuật toán PageRank trên GPU, và tối ưu hóa hiệu năng bằng cách sử dụng các kỹ thuật như chia sẻ bộ nhớ và thao tác nguyên tử. CUDA PageRank giúp tăng tốc tính toán. 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ự nay, đồ á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 hóa do tác giả đề ra để thực hiện việc tính toán trên GPU.

3.1. Các bước triển khai thuật toán PageRank trên GPU CUDA OpenCL

Đầu tiên, dữ liệu đồ thị web được chuyển từ CPU sang GPU. Tiếp theo, thuật toán PageRank được triển khai trên GPU bằng cách sử dụng CUDA. Mỗi luồng trên GPU tính toán giá trị PageRank cho một trang web. Sau mỗi vòng lặp, giá trị PageRank được cập nhật và kiểm tra sự hội tụ. Cuối cùng, kết quả PageRank được chuyển trở lại CPU.

3.2. Tối ưu hóa hiệu năng Chia sẻ bộ nhớ và thao tác nguyên tử

Chia sẻ bộ nhớ trên GPU giúp giảm độ trễ truy cập dữ liệu, tăng tốc độ tính toán. Thao tác nguyên tử đảm bảo tính nhất quán của dữ liệu khi nhiều luồng truy cập cùng một vị trí bộ nhớ. Tối ưu hóa truy cập bộ nhớ là rất quan trọng để đạt được hiệu năng cao. Tối ưu hóa PageRank GPU có thể giúp giảm thiểu thời gian tính toán.

3.3. Lựa chọn cấu trúc dữ liệu phù hợp trên GPU

Cấu trúc dữ liệu phù hợp đóng vai trò quan trọng trong việc tối ưu hóa hiệu năng trên GPU. Ma trận kề có thể được sử dụng để biểu diễn đồ thị web, nhưng nó tốn nhiều bộ nhớ. Danh sách kề là một lựa chọn hiệu quả hơn về bộ nhớ, đặc biệt đối với các đồ thị thưa. Cấu trúc dữ liệu cần được thiết kế để tối ưu hóa truy cập song song từ nhiều luồng.

IV. Ứng Dụng Thực Tế Thử Nghiệm và Đánh Giá Hiệu Năng GPGPU

Phương pháp tính toán PageRank trên GPU được thử nghiệm trên các bộ dữ liệu thực tế, bao gồm đồ thị web có kích thước khác nhau. Kết quả thử nghiệm cho thấy khả năng tăng tốc đáng kể so với tính toán trên CPU. Hiệu năng của phương pháp được đánh giá dựa trên thời gian tính toán, độ chính xác của kết quả và mức tiêu thụ năng lượng. Đánh giá hiệu năng GPU cho thấy sự vượt trội so với CPU. 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.

4.1. Mô tả bộ dữ liệu thử nghiệm và môi trường thực hiện

Các bộ dữ liệu thử nghiệm bao gồm các đồ thị web có số lượng trang web và liên kết khác nhau. Môi trường thực hiện bao gồm các GPU khác nhau của NVIDIA, cũng như các CPU đa lõi để so sánh hiệu năng. Đánh giá hiệu năng GPU trên các bộ dữ liệu lớn cho thấy khả năng mở rộng của phương pháp.

4.2. So sánh hiệu năng giữa GPU và CPU Kết quả và phân tích

Kết quả thử nghiệm cho thấy GPU có khả năng tăng tốc đáng kể so với CPU, đặc biệt khi xử lý đồ thị web có kích thước lớn. GPU có thể giảm thời gian tính toán PageRank từ hàng giờ xuống còn vài phút. Phân tích kết quả cho thấy GPU có lợi thế về tính toán song song và băng thông bộ nhớ.

4.3. Các yếu tố ảnh hưởng đến hiệu năng tính toán trên GPU

Kích thước đồ thị web, cấu trúc liên kết, và kiến trúc GPU đều ảnh hưởng đến hiệu năng tính toán. Việc lựa chọn cấu trúc dữ liệu phù hợp và tối ưu hóa các tham số của thuật toán có thể cải thiện đáng kể hiệu năng. Kiến trúc GPU Tesla được sử dụng để tính toán.

V. Kết Luận Tiềm Năng và Hướng Phát Triển Của CUDA PageRank

Luận văn này đã chứng minh tiềm năng của việc ứng dụng công nghệ tính toán đa dụng trên GPU cho bài toán PageRank. Phương pháp đề xuất có khả năng tăng tốc đáng kể quá trình tính toán, đáp ứng nhu cầu cập nhật PageRank thường xuyên. Hướng phát triển trong tương lai bao gồm nghiên cứu các phương pháp tối ưu hóa hơn nữa và ứng dụng GPU cho các bài toán phân tích đồ thị web phức tạp hơn. CUDA PageRank giúp tăng tốc tính toán. Hướng phát triển là cải tiến thuật toán PageRank.

5.1. Tóm tắt các kết quả đạt được và đóng góp của luận văn

Luận văn đã đề xuất một phương pháp tính toán PageRank hiệu quả trên GPU, sử dụng CUDA. Phương pháp này có khả năng tăng tốc đáng kể so với tính toán trên CPU. Luận văn đã cung cấp các kết quả thử nghiệm thực tế để chứng minh hiệu quả của phương pháp.

5.2. Hướng phát triển trong tương lai Cải tiến và ứng dụng mở rộng

Trong tương lai, có thể nghiên cứu các phương pháp tối ưu hóa hơn nữa, chẳng hạn như sử dụng bộ nhớ cache hiệu quả hơn. GPU có thể được ứng dụng cho các bài toán phân tích đồ thị web phức tạp hơn, chẳng hạn như phát hiện cộng đồng và dự đoán liên kết. Hướng phát triển là cải tiến thuật toán PageRank.

5.3. Ứng dụng thực tế và tiềm năng phát triển của GPGPU Pagerank

GPGPU Pagerank có thể được sử dụng để cải thiện hiệu năng của các công cụ tìm kiếm và các ứng dụng phân tích đồ thị web. GPGPU có tiềm năng phát triển lớn trong các lĩnh vực khác nhau, đặc biệt là trong bối cảnh dữ liệu lớn ngày càng phổ biế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.

Tóm tắt và mô tả trên trang này được tạo với sự hỗ trợ của AI từ nội dung tài liệu gốc; tài liệu do người dùng đóng góp và được kiểm duyệt trước khi xuất bản. Báo lỗi nội dung.

11/09/2025

Bạn đang xem trước tài liệu:

Luận văn ứ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

Tải đầy đủ

Trích đoạn nội dung tài liệu

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 bang 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. Đẻ làm được điều nảy „ chúng ta định nghĩa Web như là một đỏ thị.

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) 1. Hyperlink-Induced Topic Search (HITS) HITS Ia thuat ton phan tich lién ket dé danh gia cac trang web, duoc phat trién bai Jon Kleinberg [9].

HITS str dung ca lién két vao va lién ket ra dé tinh mtie d6 noi tieng cia timg trang web. HITS dua ra dinh nghia hub va authority, Mot 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. Một trang có thẻ vừa là hub vửa là authority. HITS sẽ tính toán cả hai thước đo cho mỗi trang web: giả trị authority — danh 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 la: mot trang là một hub tốt (có giả trị hub cao) khi nỏ trỏ tới các authority tốt, và Ung dung cng nghệ tính toán đa dụng trên các bộ xử lý đồ hoạ trong bai toan PageRank Phạm Nguyễn Quang Anh - CHCNTT 2009 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 bang 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. Đẻ làm được điều nảy „ chúng ta định nghĩa Web như là một đỏ thị.

Tư tưởng của HITS la: mot trang là một hub tốt (có giả trị hub cao) khi nỏ trỏ tới các authority tốt, và Ung dung 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 — CIICNTT 2009 Sau khi N dược đựng nên, việc tính HITS dược thực hiện trên dé thi nay. Vong lặp tình toán sẽ đừng khi ta đạt được độ chính xác mong muốn. Một trong những ưu điểm của LITTS nằm ở cách đánh giá bằng 2 tham sé do. [IT'S dua ra hai danh sách đã sắp xếp cho người đúng: một danh sách với các trang có giá trị authority cao và một đnh sách với các trang có giá trị hub cao.

Người dùng có thể lựa chọn giữa hai danh sách này. Dôi khi người dùng muiễ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, ho có thể muốn các trang có bub cao khi he dang tim kiếm một cách rộng rãi Một tru điểm khác của HITS lả kích thước của bải toán. HITS đưa bải toán xép hạng vẽ một bài tuần nhỏ hơm với các trang web liên quan đến từ khoá truy vẫn.

Kich 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. Tuy nhiên, một trong những nhược điểm lớn của HITS là tỉnh phụ thuộc vào truy vẫn. Tại thời điểm truy vấn, đỗ ¡ N phải được xây dụng và điều này được thực tiện cho mỗi lần tìm kiếm. Trên thực tế, hiện nay có ít máy tim kiểm sử đụng HITS.

Phuong phap PageRank Nain 1998, Page va Brin_[1] dira randt phuony phap danh gia cic ang web sua é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 1eb là quan trọng nếu nó được trô bởi các trang web quan trong. Việc hinh 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 Ð là một sự ghủ nhận của A đối với Ð, Do dỏ, một trang cỏ nhiều sự giới thiệu (mà dược xác định qua số liên.

Ung dung 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 — CIICNTT 2009 dã dượ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ô nhỏng, các bài toán khai phd dit ligu, Phạm vi của đỗ án: Dỗ á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á bai toán. Đồ án sẽ để xuất phương pháp tính toán PageRank bằng giải Huiật tuần tự lrên CPU, Từ giải Huiật tuần tự nay, dé am sẽ nghiên cứu hướng song song hoá giải thuật, cách tổ chức cầu trúc đữ liệu, các thao tác tối mu hoa đo tác giả đề ra để thực hiện việc lí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 để do dạc khả năng tăng tốc khi tính toàn PageRank trên GPU so với trén CPU. ‘Te đó, tổ chức của luận văn gồm các phần như sau: - 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.

TageRank, các bước xây đựng, điền 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ạ ort. - Chương 3: Đưa ra cách liếp cận để giải quyết bài toán, xây dựng chương trình tuần tự trên CPU vá song song trên GPU. - Chương 4: Trinh bày các thử nghiệm, so sánh hiện 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.

- Chương 5: Kết luận và đề xuất hướng phát triển cho đề tải Ung dung 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 — CIICNTT 2009 dã dượ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ô nhỏng, các bài toán khai phd dit ligu, Phạm vi của đỗ án: Dỗ á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á bai toán. Đồ án sẽ để xuất phương pháp tính toán PageRank bằng giải Huiật tuần tự lrên CPU, Từ giải Huiật tuần tự nay, dé am sẽ nghiên cứu hướng song song hoá giải thuật, cách tổ chức cầu trúc đữ liệu, các thao tác tối mu hoa đo tác giả đề ra để thực hiện việc lí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 để do dạc khả năng tăng tốc khi tính toàn PageRank trên GPU so với trén CPU.

Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ