Kartik Lakhotia
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Kartik Lakhotia has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
- Viktor Prasanna
University of Southern California
3 shared publications - Fabrizio Petrini
Intel Labs, Santa Clara, CA, USA
2 shared publications - Kelly Isham
Colgate University, Hamilton, NY, USA
2 shared publications - Laura Monroe
Los Alamos National Laboratory, Los Alamos, NM, USA
2 shared publications - Maciej Besta
ETH Zurich, Zurich, Switzerland
2 shared publications - Rajgopal Kannan
DEVCOM ARL Army Research Office
2 shared publications
Latest Publications
- Open Access
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 345-357
PolarStar: Expanding the Horizon of Diameter-3 Networks
We present PolarStar, a novel family of diameter-3 network topologies derived from the star product of low-diameter factor graphs. PolarStar gives the largest known diameter-3 network topologies for almost all radixes, thus providing the best known scalable diameter-3 network. Compared to current state-of-the-art diameter-3 networks, PolarStar achieves 1.3x geometric mean increase in scale over Bundlefly, 1.9x over Dragonfly, and 6.7x over 3-D HyperX. PolarStar has many other desirable properties, including a modular layout, large bisection, high resilience to link failures and a large number of feasible configurations for every radix. We give a detailed evaluation with simulations of synthetic and real-world traffic patterns and show that PolarStar exhibits comparable or better performance than current diameter-3 networks.
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 345-357
Open AccessPolarStar: Expanding the Horizon of Diameter-3 Networks
We present PolarStar, a novel family of diameter-3 network topologies derived from the star product of low-diameter factor graphs. PolarStar gives the largest known diameter-3 network topologies for almost all radixes, thus providing the best known scalable diameter-3 network. Compared to current state-of-the-art diameter-3 networks, PolarStar achieves 1.3x geometric mean increase in scale over Bundlefly, 1.9x over Dragonfly, and 6.7x over 3-D HyperX. PolarStar has many other desirable properties, including a modular layout, large bisection, high resilience to link failures and a large number of feasible configurations for every radix. We give a detailed evaluation with simulations of synthetic and real-world traffic patterns and show that PolarStar exhibits comparable or better performance than current diameter-3 networks.
- Open Access
- 20 June 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 10 (2) , 1-35
Parallel Peeling of Bipartite Networks for Hierarchical Dense Subgraph Discovery
Wing and Tip decomposition are motif-based analytics for bipartite graphs that construct a hierarchy of butterfly (2,2-biclique) dense edge and vertex induced subgraphs, respectively. They have applications in several domains, including e-commerce, recommendation systems, document analysis, and others. Existing decomposition algorithms use a bottom-up approach that constructs the hierarchy in an increasing order of the subgraph density. They iteratively select the edges or vertices with minimum butterfly count peel , i.e., remove them along with their butterflies. The amount of butterflies in real-world bipartite graphs makes bottom-up peeling computationally demanding. Furthermore, the strict order of peeling entities results in a large number of sequentially dependent iterations. Consequently, parallel algorithms based on bottom up peeling incur heavy synchronization and poor scalability. In this article, we propose a novel Parallel Bipartite Network peelinG (PBNG) framework that adopts a two-phased peeling approach to relax the order of peeling, and in turn, dramatically reduce synchronization. The first phase divides the decomposition hierarchy into few partitions and requires little synchronization. The second phase concurrently processes all partitions to generate individual levels of the hierarchy and requires no global synchronization. The two-phased peeling further enables batching optimizations that dramatically improve the computational efficiency of PBNG. We empirically evaluate PBNG using several real-world bipartite graphs and demonstrate radical improvements over the existing approaches. On a shared-memory 36 core server, PBNG achieves up to 19.7× self-relative parallel speedup. Compared to the state-of-the-art parallel framework P ar B utterfly , PBNG reduces synchronization by up to 15,260× and execution time by up to 295×. Furthermore, it achieves up to 38.5× speedup over state-of-the-art algorithms specifically tuned for wing decomposition. Our source code is made available at https://github.com/kartiklakhotia/RECEIPT .
- 20 June 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 10 (2) , 1-35
Open AccessParallel Peeling of Bipartite Networks for Hierarchical Dense Subgraph Discovery
Wing and Tip decomposition are motif-based analytics for bipartite graphs that construct a hierarchy of butterfly (2,2-biclique) dense edge and vertex induced subgraphs, respectively. They have applications in several domains, including e-commerce, recommendation systems, document analysis, and others. Existing decomposition algorithms use a bottom-up approach that constructs the hierarchy in an increasing order of the subgraph density. They iteratively select the edges or vertices with minimum butterfly count peel , i.e., remove them along with their butterflies. The amount of butterflies in real-world bipartite graphs makes bottom-up peeling computationally demanding. Furthermore, the strict order of peeling entities results in a large number of sequentially dependent iterations. Consequently, parallel algorithms based on bottom up peeling incur heavy synchronization and poor scalability. In this article, we propose a novel Parallel Bipartite Network peelinG (PBNG) framework that adopts a two-phased peeling approach to relax the order of peeling, and in turn, dramatically reduce synchronization. The first phase divides the decomposition hierarchy into few partitions and requires little synchronization. The second phase concurrently processes all partitions to generate individual levels of the hierarchy and requires no global synchronization. The two-phased peeling further enables batching optimizations that dramatically improve the computational efficiency of PBNG. We empirically evaluate PBNG using several real-world bipartite graphs and demonstrate radical improvements over the existing approaches. On a shared-memory 36 core server, PBNG achieves up to 19.7× self-relative parallel speedup. Compared to the state-of-the-art parallel framework P ar B utterfly , PBNG reduces synchronization by up to 15,260× and execution time by up to 295×. Furthermore, it achieves up to 38.5× speedup over state-of-the-art algorithms specifically tuned for wing decomposition. Our source code is made available at https://github.com/kartiklakhotia/RECEIPT .
- Open Access
- 17 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 165-176
In-network Allreduce with Multiple Spanning Trees on PolarFly
Allreduce is a fundamental collective used in parallel computing and distributed training of machine learning models, and can become a performance bottleneck on large systems. In-network computing improves Allreduce performance by reducing packets on the fly using network routers. However, the throughput of current innetwork solutions is limited to a single link bandwidth. We develop, compare and contrast two different sets of Allreduce spanning trees embedded into PolarFly, a high-performance diameter-2 network topology. Both of our solutions offer theoretically guaranteed near-optimal performance, boosting Allreduce bandwidth by a factor equal to half the network radix of nodes. While our first set offers low-latency with trees of depth-3, the second set offers congestion-free implementation which reduces complexity and resource requirements of in-network computing units. In doing so, we also distinguish PolarFly as a highly suitable network for distributed deep learning and other applications that employ throughput-bound large Allreductions.
- 17 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 165-176
Open AccessIn-network Allreduce with Multiple Spanning Trees on PolarFly
Allreduce is a fundamental collective used in parallel computing and distributed training of machine learning models, and can become a performance bottleneck on large systems. In-network computing improves Allreduce performance by reducing packets on the fly using network routers. However, the throughput of current innetwork solutions is limited to a single link bandwidth. We develop, compare and contrast two different sets of Allreduce spanning trees embedded into PolarFly, a high-performance diameter-2 network topology. Both of our solutions offer theoretically guaranteed near-optimal performance, boosting Allreduce bandwidth by a factor equal to half the network radix of nodes. While our first set offers low-latency with trees of depth-3, the second set offers congestion-free implementation which reduces complexity and resource requirements of in-network computing units. In doing so, we also distinguish PolarFly as a highly suitable network for distributed deep learning and other applications that employ throughput-bound large Allreductions.
- 29 December 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Micro
- Vol. 42 (2) , 44-52
Accelerating Allreduce With In-Network Reduction on Intel PIUMA
The Intel Programmable Integrated Unified Memory Architecture (PIUMA) system maps collective operations directly into the network switches and supports pipelined embeddings for high-throughput collective computation. Utilizing these features and PIUMA’s network topology, we develop a methodology to generate extremely low latency embeddings for in-network Allreduce. Our analysis shows that the proposed in-network Allreduce is highly scalable, with less than 1.5-μs single-element latency on 16K nodes. Compared to host-based Allreduce, it exhibits 36× less latency and 3.5× higher throughput. With deep neural network training as an example, we further demonstrate the benefits of our in-network Allreduce on end-user applications.
- 29 December 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Micro
- Vol. 42 (2) , 44-52
Accelerating Allreduce With In-Network Reduction on Intel PIUMA
The Intel Programmable Integrated Unified Memory Architecture (PIUMA) system maps collective operations directly into the network switches and supports pipelined embeddings for high-throughput collective computation. Utilizing these features and PIUMA’s network topology, we develop a methodology to generate extremely low latency embeddings for in-network Allreduce. Our analysis shows that the proposed in-network Allreduce is highly scalable, with less than 1.5-μs single-element latency on 16K nodes. Compared to host-based Allreduce, it exhibits 36× less latency and 3.5× higher throughput. With deep neural network training as an example, we further demonstrate the benefits of our in-network Allreduce on end-user applications.
- 1 September 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-7
A Fast and Efficient Parallel Algorithm for Pruned Landmark Labeling
Hub labeling based shortest distance querying plays a key role in many important networked graph applications, such as route planning, socially-sensitive search and web page ranking. Over the last few years, Pruned Landmark Labeling (PLL) has emerged as the state-of-the-art technique for hub labeling. PLL drastically reduces the complexity of label construction by pruning Shortest-Path Trees (SPTs). However, PLL is inherently sequential, as different SPTs must be constructed in a specific order of source vertices to ensure small label size. Particularly, for large graphs, it takes significant processing time to construct even pruned SPTs from all vertices in the graph. While there are many works on parallelizing single source shortest path, these solutions cannot be directly used for PLL, as pruning and label querying introduce significant additional complexity while restricting parallelism within an SPT. In this paper, we propose a novel, fast and efficient algorithm to significantly accelerate PLL on large graphs based on a two-level parallelization of SPTs: intra- and inter-tree. For intra-tree, we generate pruned SPTs based on a modification of the Bellman-Ford (BF) algorithm. We further optimize BF to reduce SPT label querying and initialization costs. We implement our algorithm using the recently proposed Graph Processing Over Partitions (GPOP) which dramatically improves cache-efficiency and DRAM communication-bandwidth. When pruned SPTs become very small and parallelizing individual SPTs is not advantageous, we switch to inter-tree parallelization and construct multiple trees concurrently in a batch. Experiments conducted on a 36 core (2-way hyperthreaded) Intel Broadwell server show that on some datasets, our proposed parallel algorithm can achieve greater than 35.1× speedup over state-of-the-art sequential algorithm.
- 1 September 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-7
A Fast and Efficient Parallel Algorithm for Pruned Landmark Labeling
Hub labeling based shortest distance querying plays a key role in many important networked graph applications, such as route planning, socially-sensitive search and web page ranking. Over the last few years, Pruned Landmark Labeling (PLL) has emerged as the state-of-the-art technique for hub labeling. PLL drastically reduces the complexity of label construction by pruning Shortest-Path Trees (SPTs). However, PLL is inherently sequential, as different SPTs must be constructed in a specific order of source vertices to ensure small label size. Particularly, for large graphs, it takes significant processing time to construct even pruned SPTs from all vertices in the graph. While there are many works on parallelizing single source shortest path, these solutions cannot be directly used for PLL, as pruning and label querying introduce significant additional complexity while restricting parallelism within an SPT. In this paper, we propose a novel, fast and efficient algorithm to significantly accelerate PLL on large graphs based on a two-level parallelization of SPTs: intra- and inter-tree. For intra-tree, we generate pruned SPTs based on a modification of the Bellman-Ford (BF) algorithm. We further optimize BF to reduce SPT label querying and initialization costs. We implement our algorithm using the recently proposed Graph Processing Over Partitions (GPOP) which dramatically improves cache-efficiency and DRAM communication-bandwidth. When pruned SPTs become very small and parallelizing individual SPTs is not advantageous, we switch to inter-tree parallelization and construct multiple trees concurrently in a batch. Experiments conducted on a 36 core (2-way hyperthreaded) Intel Broadwell server show that on some datasets, our proposed parallel algorithm can achieve greater than 35.1× speedup over state-of-the-art sequential algorithm.