Please use this identifier to cite or link to this item:
Title: Hybrid Multicore Algorithms for Some Semi Numerical Applications and Graphs
Researcher: Banerjee Dip Sankar
Guide(s): Kothapalli Kishore
Keywords: CPU+GPU
Heterogeneous Parallel Computing
High Performance Computing
Parallel Graph Algorithms
University: International Institute of Information Technology, Hyderabad
Completed Date: 26/11/2014
Abstract: In this thesis we work towards the development of hybrid multicore computing. Hybrid multicore computing is developing algorithms and optimization strategies for popular computing primitives on an hybrid platform. A hybrid platform is one which contains two or more multicore or many-core devices. There are several challenges towards the efficient algorithm design on hybrid platforms such as that of communication bottlenecks, load balance and synchronization. In this thesis we work towards developing algorithms for some computing primitives such as that of list ranking, sorting and pseudo-randomness and some graph algorithms. We experiment on a hybrid platform consisting of a 6-core Intel CPU and Nvidia GPUs of broadly two generations. In our first work we work towards the development of hybrid algorithms for List Ranking. The main contribution of this work is to address the issues related to the design of hybrid solutions. We show our hybrid algorithm for list ranking is faster by 50% compared to the best known implementation [Wei et. al.IPDPS 2010]. newline newlineThe ability to use randomness in computation is known to help in several situations. For such computations to be made possible on a general purpose computer, a source of randomness, or in general a pseudo random generator (PRNG), is essential. However, most of the PRNGs currently available on GPUs suffer from some basic drawbacks. Our approach produces 0.07 GNumbers per second. newline newlineThe quality of our generator is tested with industry standard tests. In the second part of the thesis, we work towards hybrid graph connected components and breadth first search. We achieve almost 25% improvement over the best known implementation in. For performing breadth first search (BFS), we employ a graph pruning strategy to reduce the size of large graphs which is often composed of a large percentage of pendant nodes. We apply a hybrid BFS on the remainder graph and is followed by a re-insertion phase. We achieve a 35% improvement over the current best know solution.
Pagination: xv,135
Appears in Departments:Computer Science and Engineering

Files in This Item:
File Description SizeFormat 
01_title.pdfAttached File44.51 kBAdobe PDFView/Open
02_certificates.pdf20.78 kBAdobe PDFView/Open
03_acknowledgements.pdf32.75 kBAdobe PDFView/Open
04_abstract.pdf38.18 kBAdobe PDFView/Open
05_contents.pdf63.06 kBAdobe PDFView/Open
06_chapter01.pdf511.16 kBAdobe PDFView/Open
07_chapter02.pdf448.79 kBAdobe PDFView/Open
08_chapter03.pdf158.92 kBAdobe PDFView/Open
09_chapter04.pdf398.55 kBAdobe PDFView/Open
10_chapter05.pdf171.46 kBAdobe PDFView/Open
11_chapter06.pdf150.52 kBAdobe PDFView/Open
12_chapter07.pdf162.93 kBAdobe PDFView/Open
13_chapter08.pdf336.68 kBAdobe PDFView/Open
14_chapter09.pdf54.43 kBAdobe PDFView/Open
15_publications.pdf31.7 kBAdobe PDFView/Open
16_bibliography.pdf91.59 kBAdobe PDFView/Open

Items in Shodhganga are protected by copyright, with all rights reserved, unless otherwise indicated.