• norsk
    • English
  • English 
    • norsk
    • English
  • Login
View Item 
  •   Home
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Department of Informatics
  • View Item
  •   Home
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Department of Informatics
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

A Comparison of Vertex and Edge Partitioning Approaches for Parallel Maximal Matching

Sørnes, Alexander N
Master thesis
Thumbnail
View/Open
116145831.pdf (906.4Kb)
URI
https://hdl.handle.net/1956/7896
Date
2013-12-09
Metadata
Show full item record
Collections
  • Department of Informatics [541]
Abstract
This thesis will compare two ways of distributing data for parallel graph algorithms: vertex and edge partitioning, using a distributed memory system. Previous studies on the parallelization of graphs has often been focused on a vertex partitioning, where each processor is assigned a set V' \(\subseteq\) V where G = (V,E), yielding a one-dimensional partitioning. It has been shown, however, that an edge partitioning (or 2D partitioning), where each processor is assigned a set E' \(\subseteq\) E, may yield a benefit in terms of a lower communication volume. The performance and scalability of vertex and edge partitionings are compared by implementing the Karp-Sipser matching set algorithm for both partitioning schemes. A matching set is a set E' \(\subseteq\) E of independent edges such that each vertex in V occurs at most once in E'. We find that while the vertex partitioned algorithm gives a significantly higher speedup, the increased performance of the edge partitioned algorithm on more dense graphs suggests that if the graph framework is improved further, it could lead to the implementation of an edge partitioned matching algorithm that offers better scalability and comparable matching quality to a vertex partitioned matching algorithm. An edge partitioning requires a rigorous framework for handling the communication resulting when edges owned by multiple processors are incident on the same vertex. Hopefully, the framework developed for representing an edge partitioned graph facilitates the implementation of other parallel graph algorithms using an edge partitioning approach.
Publisher
The University of Bergen
Copyright
Copyright the author. All rights reserved

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit
 

 

Browse

ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDocument TypesJournalsThis CollectionBy Issue DateAuthorsTitlesSubjectsDocument TypesJournals

My Account

Login

Statistics

View Usage Statistics

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit