Singhal, N and Peri, Sathya
(2017)
Exploiting Concurrency in Graph algorithms.
Masters thesis, Indian Institute of Technology Hyderabad.
Abstract
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.
Actions (login required)
 |
View Item |
Altmetric
Altmetric