Keshav Pingali

Keshav Pingali

Auto-generated profile, based on publicly available information

Keshav Pingali

Department of Computer Science, University of Texas at Austin, USA

Research Focus & Metrics

Academic Career Length

23Years (2004-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
25 July 2015
Verified
Book Chapter
Closed access
PDF file
JWJoyce Jiyoung Whang
Joyce Jiyoung Whang
ALAndrew Lenharth
Andrew Lenharth
IDInderjit S. Dhillon
Inderjit S. Dhillon
KPKeshav Pingali
Keshav Pingali

1 December 2018 in Proceedings of the VLDB Endowment
Verified
Journal Article
Open access
PDF file
GGGurbinder Gill
Gurbinder Gill
RDRoshan Dathathri
Roshan Dathathri
LHLoc Hoang
Loc Hoang
KPKeshav Pingali
Keshav Pingali
Distributed-memory clusters are used for in-memory processing of very large graphs with billions of nodes and edges. This requires partitioning the graph among the machines in the cluster. When a graph is partitioned, a node in the graph may be replicated on several machines, and communication is required to keep these replicas synchronized. Good partitioning policies attempt to reduce this synchronization overhead while keeping the computational load balanced across machines. A number of recent studies have looked at ways to control replication of nodes, but these studies are not conclusive because they were performed on small clusters with eight to sixteen machines, did not consider work-efficient data-driven algorithms, or did not optimize communication for the partitioning strategies they studied. This paper presents an experimental study of partitioning strategies for work-efficient graph analytics applications on large KNL and Skylake clusters with up to 256 machines using the Gluon communication runtime which implements partitioning-specific communication optimizations. Evaluation results show that although simple partitioning strategies like Edge-Cuts perform well on a small number of machines, an alternative partitioning strategy called Cartesian Vertex-Cut (CVC) performs better at scale even though paradoxically it has a higher replication factor and performs more communication than Edge-Cut partitioning does. Results from communication micro-benchmarks resolve this paradox by showing that communication overhead depends not only on communication volume but also on the communication pattern among the partitions. These experiments suggest that high-performance graph analytics systems should support multiple partitioning strategies, like Gluon does, as no single graph partitioning strategy is best for all cluster sizes. For such systems, a decision tree for selecting a good partitioning strategy based on characteristics of the computation and the cluster is presented.

25 July 2015
Verified
Book Chapter
Closed access
PDF file
ALAndrew Lenharth
Andrew Lenharth
DNDonald Nguyen
Donald Nguyen
KPKeshav Pingali
Keshav Pingali

17 January 2022
Verified
Conference Paper
Closed access
JHJiayuan He
Jiayuan He
UAUdit Agarwal
Udit Agarwal
YYYihang Yang
Yihang Yang
RMRajit Manohar
Rajit Manohar
KPKeshav Pingali
Keshav Pingali
Global routing has become more challenging due to advancements in the technology node and the ever-increasing size of chips. Global routing needs to generate routing guides such that (1) routability of detailed routing is considered and (2) the routing is deterministic and fast. In this paper, we firstly introduce soft capacity which reserves routing space for detailed routing based on the pin density and Rectangular Uniform wire Density (RUDY). Second, we propose a deterministic parallelization approach that partitions the netlist into batches and then bulk-synchronously maze-routes a single batch of nets. The advantage of this approach is that it guarantees determinacy without requiring the nets running in parallel to be disjoint, thus guaranteeing scalability. We then design a scheduler that mitigates the load imbalance and livelock issues in this bulk synchronous execution model. We implement SPRoute 2.0 with the proposed methodology. The experimental results show that SPRoute 2.0 generates good quality of results with 43% fewer shorts, 14% fewer DRCs and a 7.4X speedup over a state-of-the-art global router on the ICCAD2019 contest benchmarks.

22 February 2019 in IEEE Software
Verified
Journal Article
Closed access
SBSaeid Barati
Saeid Barati
FBFerenc Bartha
Ferenc Bartha
SBSwarnendu Biswas
Swarnendu Biswas
RCRobert Cartwright
Robert Cartwright
ADAdam Duracz
Adam Duracz
SZSizhuo Zhang
Sizhuo Zhang
Our software framework, Proteus, treats adaptation as a first-class object, enabling rapid development of robust, adaptive applications. Proteus developers specify their programs' intent and adaptable components (or knobs). A control-theoretic runtime continually monitors the running application, adjusting knobs so that the specified intent is met.

1 May 2016
Verified
Conference Paper
Closed access
RKRashid Kaleem
Rashid Kaleem
AVAnand Venkat
Anand Venkat
SPSreepathi Pai
Sreepathi Pai
MHMary Hall
Mary Hall
KPKeshav Pingali
Keshav Pingali
Although there is an extensive literature on GPU implementations of graph algorithms, we do not yet have a clear understanding of how implementation choices impact performance. As a step towards this goal, we studied how the choice of synchronization mechanism affects the end-to-end performance of complex graph algorithms, using stochastic gradient descent (SGD) as an exemplar. We implemented seven synchronization strategies for this application and evaluated them on two GPU platforms, using both road networks and social network graphs as inputs. Our experiments showed that although none of the seven strategies dominates the rest, it is possible to use properties of the platform and input graph to predict the best strategy.