Exploiting Concurrency in Graph algorithms

Singhal, N and Peri, Sathya (2017) Exploiting Concurrency in Graph algorithms. Masters thesis, Indian Institute of Technology Hyderabad.

[img] Text
Thesis_Mtech_CS_3710.pdf - Submitted Version
Restricted to Registered users only until 2 August 2018.

Download (1MB) | Request a copy


Concurrent programming has become popular in the recent years to facilitate exploitation of hardware capabilities. Because threads are executed concurrently on di�erent processors, and are subject to operating system scheduling decisions, page faults, interrupts, etc., we must think of the computation as completely asynchronous, so that the steps of di�erent threads can be interleaved arbitrarily. This signi�cantly makes the task of designing correct concurrent data structures quite challenging. Furthermore, the issues of correctness and performance are closely tied to each other: algorithmic enhancements that seek to improve performance often make it more difficult to design and verify a correct data structure implementation. Firstly, we considered the problem of graph coloring on static graphs. The basic motivation behind this problem was to limit the number of threads being created at runtime (irrespective of the size of the graph to be colored). We explored four different approaches: (1) barrier synchronization; (2) jones plassman; (3) locking variants and (4) using transactions. The barrier synchronization and Jones Plassman Algorithm do not fare well and are not comparable to the sequential coloring. On the other hand, locks and transactions seem to perform fairly well in terms of time taken for coloring maintaining a reasonable number of colors used. We also present ideas to cut long waiting chains formed by locks. Concurrent data structures or CDS such as concurrent stacks, queues, lists etc. have become very popular in the past few years due to the rise of multi-core systems and due to their performance benefits over their sequential counterparts. But one of the greatest challenges with CDSs is developing correct structures and then proving their correctness either through automatic verification or through hand-written proofs [1]. Considering the complexity of developing a CDS and verifying its correctness, we address the most basic problem of this domain in this chapter: given the set of LPs of a CDS, how to show its correctness? We have developed a hand-crafted technique of proving correctness of the CDSs by validating it LPs which is inspired by rely-guarantee approach [2, 3]. Our technique can be applied to prove the correctness of several commonly used CDSs developed in literature such as Lock-free Linked based Sets [4], hoh-locking-list [5, 6], lazy-list [6, 7], Skiplists [8], etc. Graph is a common data-structure that is being used in various fields where they are very large and dynamic in nature. Dynamic graphs are the one's which are subjected to a sequence of changes like insertion, deletion of vertices and/or edges [9]. We have been specifically motivated by the problem of Serialization Graph Testing (SGT) scheduler [10] from Databases and Transactional Memory [11]. The SGT scheduler maintains the property that con ict graph always remains acyclic to ensure correctness. The traditional solution employed by SGT in Databases & STMs to maintain dynamic graphs is to use a single coarse lock to protect the entire graph. We propose a solution for this problem by developing a concurrent directed graph data-structure which allows threads to concurrently add/delete/contains on vertices/edges while ensuring linearizability. Furthermore, we also provide a linearizable solution for SGT i.e. (1) identifying all con icting & real-time edges, (2) adding all those edges while ensuring acyclicity. Both these occur atomically while ensuring that the history generated satisfies strict-serializability.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Thesis (Masters)
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 01 Jan 2018 11:27
Last Modified: 01 Jan 2018 11:36
URI: http://raiith.iith.ac.in/id/eprint/3710
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 3710 Statistics for this ePrint Item