Please use this identifier to cite or link to this item:
http://hdl.handle.net/10603/144572
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 |
URI: | http://hdl.handle.net/10603/144572 |
Appears in Departments: | Computer Science and Engineering |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
01_title.pdf | Attached File | 44.51 kB | Adobe PDF | View/Open |
02_certificates.pdf | 20.78 kB | Adobe PDF | View/Open | |
03_acknowledgements.pdf | 32.75 kB | Adobe PDF | View/Open | |
04_abstract.pdf | 38.18 kB | Adobe PDF | View/Open | |
05_contents.pdf | 63.06 kB | Adobe PDF | View/Open | |
06_chapter01.pdf | 511.16 kB | Adobe PDF | View/Open | |
07_chapter02.pdf | 448.79 kB | Adobe PDF | View/Open | |
08_chapter03.pdf | 158.92 kB | Adobe PDF | View/Open | |
09_chapter04.pdf | 398.55 kB | Adobe PDF | View/Open | |
10_chapter05.pdf | 171.46 kB | Adobe PDF | View/Open | |
11_chapter06.pdf | 150.52 kB | Adobe PDF | View/Open | |
12_chapter07.pdf | 162.93 kB | Adobe PDF | View/Open | |
13_chapter08.pdf | 336.68 kB | Adobe PDF | View/Open | |
14_chapter09.pdf | 54.43 kB | Adobe PDF | View/Open | |
15_publications.pdf | 31.7 kB | Adobe PDF | View/Open | |
16_bibliography.pdf | 91.59 kB | Adobe PDF | View/Open |
Items in Shodhganga are licensed under Creative Commons Licence Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0).
Altmetric Badge: