Prof. Kishore Kothapalli and his students published the following papers at the 36th International Parallel and Distributed Processing Symposium (IPDPS-2022) held virtually.
- Shared-Memory Parallel Algorithms for Fully Dynamic Maintenance of 2-Connected Components – Prof. Kishore Kothapalli, Chirayu Haryn and Dr. G Ramakrishna from IIT Tirupati and Dr. Dip Sankar Banerjee from IIT Jodhpur.
Research work as explained by the authors: Finding the biconnected components of a graph has many applications in many other graph problems including planarity testing, computing the centrality metrics, finding the (weighted) vertex cover, colouring, and the like. Recent years saw the design of efficient algorithms for this problem across sequential and parallel computational models. However, current algorithms do not work in the setting where the underlying graph changes over time in a dynamic manner via the insertion or deletion of edges.
Dynamic algorithms in the sequential setting that obtain the biconnected components of a graph upon insertion or deletion of a single edge are known from over two decades ago. Parallel algorithms for this problem are not heavily studied. In this paper, we design shared-memory parallel algorithms that obtain the biconnected components of a graph after the insertion or deletion of a batch of edges. Our algorithms hence will be capable of exploiting the parallelism adduced due to a batch of updates.
We implement our algorithms on an AMD EPYC 7742 CPU having 128 cores. Our experiments on a collection of 10 real-world graphs from multiple classes indicate that our algorithms outperform parallel state-of-the-art static algorithms.
- Dynamic Batch Parallel Algorithms for Updating PageRank – Prof. Kishore Kothapalli along with his Ph.D student Subhajit Sahu and Dr. Dip Sankar Banerjee, IIT Jodhpur
Research work as explained by the authors: The design and implementation of parallel algorithms for dynamic graph problems is attracting significant research attention in recent years, driven by numerous applications to social network analysis, neuroscience, and protein interaction networks. One such problem is the computation of PageRank values of vertices in a directed graph.
This paper presents two new parallel algorithms for recomputing the PageRank values of vertices in a dynamic graph. Our techniques require the recomputation of the PageRank of only the vertices affected by the insertion/deletion of a batch of edges. We conduct detailed experimental studies of our algorithm on a set of 11 real-world graphs. Our results on Intel Xeon Silver 4116 CPU and NVIDIA Tesla V100 PCIe 16GB GPU indicate that our algorithms outperform static and dynamic update algorithms by 6.1\x and 8.6\x on the CPU, and by 9.8\x and 9.3\x on the GPU respectively. We also compare the performance of the algorithms in batched mode to cumulative single-edge updates.
IPDPS is an international forum for engineers and scientists from around the world to present their latest research findings in all aspects of parallel computation. In addition to technical sessions of submitted paper presentations, the meeting had workshops, tutorials, and commercial presentations & exhibits. IPDPS represented an unique international gathering of computer scientists from around the world.