Design of Parallel PageRank algorithm

Abstract

The purpose of this thesis is to encode a parallel software which will compute PageRank values efficiently for large scaled networks. Such a parallel computation will be able to perform computation for multi-core and multi-processor hardware structures. The purpose of this thesis, encoding and actual results of parallel PageRank computations are presented: CPU, memory, and I/O characteristics of the computations are presented for .Net platform. A computational profile of various steps of the algorithm is provided: Resource consumption during data-read, PageRank computations, and results persistence is presented. The performance of parallel computation is presented by contrasting various figures between sequential computation and parallel computations with various numbers of Windows threads. Microsoft .NET and specifically C# programming language were used for software implementation of Parallel PageRank Algorithm. A new library arranging programming operation in multi-core hardware structures was supplied for the latest version of Microsoft .NET platform (4.0). This library was used for parallelization works in software. Microsoft has recognized the importance of parallelism, and has incorporated various technologies into its solutions spectrum: Task Parallel Library for multi-core computation, and Message Passing Interface employed under HPC Server can be utilized to parallelize computations. This thesis used Task Parallel Library to implement a multi-threaded extension of PageRank algorithm. The language of choice was C#.

Bu tezin amacı, büyük ölçekli şebekeler(network) için, PageRank değerlerini verimli olarak hesaplayacak paralel bir yazılımı kodlamaktır. Bu tür bir paralel hesaplama, çok-çekirdekli ve çok-işlemcili donanım mimarileri için hesaplama yapabilecektir. Bu tez kapsamında paralel PageRank algoritma tasarımı, paralel PageRank hesaplamaları kodlaması ve hesaplama için gerçek sonuçlar sunulmaktadır. Kaynak tüketimi ve veri okuma, PageRank hesaplamaları sırasında sonuçları detaylı sunulmuştur: farklı yaklaşımlar ile algoritmanın hesaplama profili sağlanmıştır. .Net platformu için CPU, bellek ve hesaplamaların I/O özellikleri sunulmaktadır: Sıralı ve paralel hesaplamalar için arasında hesaplama performansı Microsoft windows işletim sistemi kanallarının (Microsoft Windows threads) sayıları ile sunulmaktadır. Paralel PageRank Algoritmasının yazılım implementasyonu için Microsoft .NET platformu, ve spesifik olarak da C# programlama dili kullanılmıştır. Microsoft, .NET platformunun en son versiyonunda (4.0), çok-çekirdekli donanım mimarilerinde programlamayı düzenleyen yeni bir kütüphane tedarik etmiştir. Bu kütüphane, yazılımdaki paralelizasyon işleri için kullanılmıştır. Microsoft paralellik önemini kabul etmektedir ve parallelik için çeşitli teknolojiler geliştimiştir: çok-çekirdekli hesaplamalar için Task Parallel Library ve HPC Server altında çalışan Message Passing Interface (MPI) ile hesaplamaları paralizasyonu için kullanılabilir. Bu tez, PageRank algoritması multi-threaded bir uzantısı uygulamak için Task Parallel Library kullanılmıştır. Tercih edilen programlama dili C # „tır.