Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Srimanth thesis.pdf (3.13 MB)

ETD Abstract Container

Abstract Header

Graph Partitioning Algorithms for Minimizing Inter-node Communication on a Distributed System

Gadde, Srimanth
http://rave.ohiolink.edu/etdc/view?acc_num=toledo1376561814

Abstract Details

2013, Master of Science in Electrical Engineering, University of Toledo, College of Engineering.
Processing large graph datasets represents an increasingly important area in computing research and applications. The size of many graph datasets has increased well beyond the processing capacity of a single computing node, thereby necessitating distributed approaches. As these datasets are processed over a distributed system of nodes, this leads to an inter-node communication cost problem (also known as inter-partition communication), negatively affecting the system performance. This research proposes new graph partitioning algorithms to minimize the inter-node communication by achieving a sufficiently balanced partition. Initially, an intuitive graph partitioning algorithm using Random Selection method coupled with Breadth First Search is developed for reducing inter-node communication by achieving a sufficiently balanced partition. Second, another graph partitioning algorithm is developed using Particle Swarm Optimization with Breadth First Search to reduce inter-node communication further. Simulation results demonstrate that the inter-node communication using PSO with BFS gives better results (reduction of approximately 6% to 10% more) compared to the RS method with BFS. However, both the algorithms minimize the inter-node communication efficiently in order to improve the performance of a distributed system.
Robert Green (Committee Chair)
Vijay Devabhaktuni (Committee Co-Chair)
William Acosta (Committee Member)
Mansoor Alam (Committee Member)
104 p.
Computer Engineering; Computer Science
Inter-node communication, Intra-node communication, Distributed graph processing, Graph partitioning algorithms, breadth first search, particle swarm optimization, large graph datasets

Recommended Citations

Citations

  • Gadde, S. (2013). Graph Partitioning Algorithms for Minimizing Inter-node Communication on a Distributed System [Master's thesis, University of Toledo]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=toledo1376561814

    APA Style (7th edition)

  • Gadde, Srimanth. Graph Partitioning Algorithms for Minimizing Inter-node Communication on a Distributed System. 2013. University of Toledo, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=toledo1376561814.

    MLA Style (8th edition)

  • Gadde, Srimanth. "Graph Partitioning Algorithms for Minimizing Inter-node Communication on a Distributed System." Master's thesis, University of Toledo, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=toledo1376561814

    Chicago Manual of Style (17th edition)

toledo1376561814
875
© 2013, all rights reserved.
This open access ETD is published by University of Toledo and OhioLINK.