Combinatorial optimization problems on graphs, such as Maximal Independent Set (\(\mathcal {M}\)), Graph Coloring (\(\mathcal {GC}\)), and Maximal Matching (\(\mathcal {MM}\)), are computationally challenging and are significantly harder in dynamic settings where edges and vertices evolve continuously. Maintaining valid solutions under high-rate updates requires more than recomputation or static parallelism. We present SAGA, a high-performance framework for real-time combinatorial optimization on dynamic graphs. SAGA adopts a state-aware execution model in which each vertex maintains compact local state, enabling incremental and localized updates in response to graph changes. By coupling fine-grained task parallelism with data-parallel execution, SAGA minimizes communication overhead through state-aware partitioning and distributed state management. The SAGA compute engine maintains evolving solutions consistently across worker nodes while supporting low-latency queries. We evaluate SAGA on a distributed memory cluster against three state-of-the-art graph frameworks. On streaming instances of \(\mathcal {M}\), \(\mathcal {MM}\), and \(\mathcal {GC}\), SAGA achieves speedups of up to 11.8 ×, 6.2 ×, and 8.4 ×, respectively, sustains up to 7.2M operations per second, and delivers over 10.8 × lower query latency compared to state-of-the-art graph analytics frameworks under concurrent update workloads.

Centrality measures quantify the importance of vertices in a network and are widely used in domains such as social network analysis and epidemiology. Given the size and evolving nature of real-world networks, there is growing interest in parallel algorithms that efficiently update centrality values in dynamic settings. In this paper, we study the update of the percolation centrality measure in a dynamic graph. We present parallel algorithms to handle changes to the percolation value of a batch of vertices and the addition and deletion of a batch of edges to the graph. We leverage the graphs’ structural properties to improve our algorithms’ performance. To our knowledge, we are the first to propose such algorithms for percolation centrality. We implement and benchmark our algorithms on a server with two AMD EPYC CPUs and an Nvidia A100 GPU. Our experiments on a collection of real-world graphs indicate that our algorithms achieve speedups of 8.79 × and 2.82 × on CPU and GPU, respectively, for edge updates, and 309.44 × and 18.71 × on CPU and GPU, respectively, for vertex percolation updates over state-of-the-art static algorithms for a batch of 10000 edges and vertices, respectively.

In network analysis, Katz centrality is widely used to measure node influence by considering both direct and indirect connections weighted by path length. While numerous studies have examined Katz centrality for static graphs, relatively few address the challenges posed by dynamic graphs. Katz centrality can utilize perturbation theory by exploiting iterative solvers to obtain updated Katz scores in dynamic graphs. However, these methods are limited to handling only small changes, as they generally accept only minor structural updates limited to only edge insertions or removals. Additionally, due to an iterative approach, the solutions can be sequential and provide approximate answers, which may reduce accuracy when the graph undergoes frequent updates over time. This paper introduces a novel algorithm that significantly improves the efficiency of Katz centrality calculations in dynamic graphs. After each update, we identify affected nodes using a Breadth First Search (BFS) frontier and then apply dynamic programming, which allows for both edge/node insertions and deletions. Our parallel implementation on a shared memory platform achieves a 5.29 x speedup on an average over the static version. Our algorithm can update a batch of 1 million edges on an existing graph of 1 billion edges in 24.73 seconds.

Finding the Maximal Independent Set (MIS) in a graph is a well-known problem with applications in resource allocation, load balancing, and routing optimization. This task is particularly challenging for large graphs as it requires multiple iterations over the entire set of vertices. Recently, there has been significant interest in developing techniques to maintain the MIS dynamically in evolving graphs rather than re-computing from scratch. In this paper, we propose new data structures and techniques for computing MIS in parallel on dynamic graphs. We specifically propose techniques to handle insertions and deletions in a batched setting. We conducted detailed experiments on shared memory multicore CPUs using graphs ranging from 50 million to ${1. 2}$ billion edges. Our results show that using our technique for insertions and deletions can provide up to 15.64x and 10.57x speedups on average over comparable baselines. Additionally, the final MIS we produce varies by only about ${0. 1 8 \%}$ in cardinality compared to the existing state-of-the-art.

Community detection is the problem of identifying natural divisions in networks. Efficient parallel algorithms for identifying such divisions is critical in a number of applications, where the size of datasets have reached significant scales. This paper presents one of the most efficient implementations of the Leiden algorithm, a high quality community detection method. On a server equipped with dual 16-core Intel Xeon Gold 6226R processors, our Leiden implementation, which we term as GVE-Leiden, outperforms NetworKit Leiden and cuGraph Leiden (running on NVIDIA A100 GPU) by 8.2 × and 3.0 × respectively — achieving a processing rate of 403M edges/s on a 3.8B edge graph. In addition, GVE-Leiden improves performance at a rate of 1.6 × for every doubling of threads.

Voxelization is a standard technique to represent arbitrary shaped geometries on a Cartesian grid. It is often utilized in pre-processing stage of any computational fluid dynamics (CFD) simulation for distinguishing the fluid and solid domain. In addition, identification of boundary fluid nodes in the immediate vicinity of the solid body is extremely crucial for proper imposition of boundary conditions and force evaluation. These nodes are therefore tagged separately and is often termed as surface voxelization. However, this procedure becomes non-trivial and computationally expensive as the complexity of geometry increases, especially if it is deformable and moving. Here voxelization needs to be performed in the solid volume as well, as the nodes keep switching from solid to fluid and vice versa at every iteration. For fluid-structure interaction problems, the analysis of flow behaviour requires an additional operation where the point of intersection of the lattice links connecting the fluid boundary nodes and solid bound nodes need to be further calculated. This ensures that deformation of geometry is properly captured and the correct boundary velocity is enforced onto the fluid (no slip). In this work we present techniques for GPU acceleration of voxelization for moving deformable geometries intended for CFD solvers based on the lattice Boltzmann method (LBM). The proposed techniques show speed-ups of up to 5.1x over equivalent parallel implementations.

Finding the biconnected components of a graph has a large number of applications in many other graph problems including planarity testing, computing the centrality metrics, finding the (weighted) vertex cover, coloring, 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 subsequent to 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.11The implementation and an extended version of this paper is at [5].

In recent times, approximate computing has emerged as a promising technique to achieve significant power and energy benefits in computational systems. It is widely employed in fault-tolerant computationally intensive applications that require large arithmetic blocks. Applications such as image processing and machine learning often invoke the Multiply-Accumulate (MAC) unit for convolution operations. This paper proposes a novel architecture for an (unsigned × unsigned) approximate rounding and truncation based MAC unit named ART-MAC. It replaces the accurate multiplier architecture with an approximate multiplier proposed along with this work, thus improving the overall Quality of Results (QoR). The proposed design consumes 35.35% less power and showcases a significant speedup of 1.23 times when compared to the conventional MAC unit. On an average, the ART-MAC consumes 7.44% lesser on-chip area and showcases 13.49% lesser power-delay-product (PDP) compared to existing state-of-the-art designs.

Approximate Computing aims at achieving better performance at a marginal loss of accuracy in error-resilient applications. Several approximate arithmetic circuits have been proposed in the past which use carry prediction schemes, block-based approaches and genetic algorithms. However, these architectures are usually non power-aware and often incur large area overhead with the introduction of re-configurability. This work explores a new facet of approximation, which involves using the Unified Power Format (UPF) model to introduce approximation on additions. We call this methodology AxLEAP. Further, we validate the proposed methodology on a new approximate adder, which we term as AxL-Add. AxL-Add has a simple and re-configurable design with a marginal area overhead of 1.69% over accurate adder. After extensive evaluation, we show that our methodology is up to 67% better in terms of power consumption while providing near accurate results at the end application.

In recent times, approximate computing has found significant use in applications that can tolerate partially inaccurate results. This tolerance can be exploited to design simpler hardware aimed at getting area and energy benefits. In this work, we propose a novel technique to multiply two unsigned binary numbers through a Segmentation based Approximate Multiplier (SAM). The proposed design reduces the size of the Partial Products Matrix (PPM) in the order of n × (2n — 1) to a Reduced Partial Product Matrix (R-PPM) of the order 4 × 2n. Additionally, it also eliminates the extra hardware required for compression and rearrangement of partial products. μ-SAM, an optimized version of our basic design is also proposed along with this work. μ-SAM further minimizes the on-chip area and power consumption of the basic design. The basic design consumes 32.43% lesser on-chip area when compared to the conventional Wallace tree multiplier [1] and produces results that are 89.1% more accurate when compared to other existing state-of-the-art designs such as TOSAM [2], LETAM [3], and DQ4:2C4 [4].

In recent years, DRAM-based main memories have become susceptible to the Row Hammer (RH) problem, which causes bits to flip in a row without accessing them directly. Frequent activation of a row, called an aggressor row , causes its adjacent rows’ ( victim ) bits to flip. The state-of-the-art solution is to refresh the victim rows explicitly to prevent bit flipping. There have been several proposals made to detect RH attacks. These include both probabilistic as well as deterministic counter-based methods. The technique of handling RH attacks, however, remains the same. In this work, we propose an efficient technique for handling the RH problem. We show that the mechanism is agnostic of the detection mechanism. Our RH handling technique omits the necessity of refreshing the victim rows. Instead, we use a small non-volatile Spin-Transfer Torque Magnetic Random Access Memory (STTRAM) that ensures no unnecessary refreshes of the victim rows on the DRAM device and thus allowing more time for normal applications in the same DRAM device. Our model relies on the migration of the aggressor rows. This accounts for removing blocking of the DRAM operations due to the refreshing of victim rows incurred in the previous solution. After extensive evaluation, we found that, compared to the conventional RH mitigation techniques, our model minimizes the blocking time of the memory that is imposed due to explicit refreshing by an average of 80.72% in the worst-case scenario and provides energy savings of about 15.82% on average, across different types of RH-based workloads. A lookup table is necessary to pinpoint the location of a particular row, which, when combined with the STTMRAM, limits the storage overhead to 0.39% of a 2 GB DRAM. Our proposed model prevents repeated refreshing of the same victim rows in different refreshing windows on the DRAM device and leads to an efficient RH handling technique.

Approximate computing has in recent times found significant applications towards lowering power, area, and time requirements for arithmetic operations. Several works done in recent years have furthered approximate computing along these directions. In this work, we propose a new approximate adder that employs a carry prediction method. This allows parallel propagation of the carry allowing faster calculations. In addition to the basic adder design, we also propose a rectification logic which would enable higher accuracy for larger computations. Experimental results show that our adder produces results 91.2% faster than the conventional ripple-carry adder. In terms of accuracy, the addition of rectification logic to the basic design produces results that are more accurate than state-of-the-art adders like SARA[13] and BCSA[5] by 74%.

PageRank (PR) is the standard metric used by the Google search engine to compute the importance of a web page via modeling the entire web as a first order Markov chain. The challenge of computing PR efficiently and quickly has been already addressed by several works previously who have shown innovations in both algorithms and in the use of parallel computing. The standard method of computing PR is handled by modelling the web as a graph. The fast growing internet adds several new web pages everyday and hence more nodes (representing the web pages) and edges (the hyperlinks) are added to this graph in an incremental fashion. Computing PR on this evolving graph is now an emerging challenge since computations from scratch on the massive graph is time consuming and unscalable. In this work, we propose Hybrid Page Rank (HyPR), which computes PR on evolving graphs using collaborative executions on muti-core CPUs and massively parallel GPUs. We exploit data parallelism via efficiently partitioning the graph into different regions that are affected and unaffected by the new updates. The different partitions are then processed in an overlapped manner for PR updates. The novelty of our technique is in utilizing the hybrid platform to scale the solution to massive graphs. The technique also provides high performance through parallel processing of every batch of updates using a parallel algorithm. HyPR efficiently executes on a NVIDIA V100 GPU hosted on a 6th Gen Intel Xeon CPU and is able to update a graph with 640M edges with a single batch of 100,000 edges in 12 ms. HyPR outperforms other state of the art techniques for computing PR on evolving graphs [1] by 4.8x. Additionally HyPR provides 1.2x speedup over GPU only executions, and 95x speedup over CPU only parallel executions.

The architectural trend towards heterogeneity has pushed heterogeneous computing to the fore of parallel computing research. Heterogeneous algorithms, often carefully handcrafted, have been designed for several important problems from parallel computing such as sorting, graph algorithms, matrix computations, and the like. A majority of these algorithms follow a work partitioning approach where the input is divided into appropriate sized parts so that individual devices can process the “right” parts of the input. However, arriving at a good work partitioning is usually non-trivial and may require extensive empirical search. Such an extensive empirical search can potentially offset any gains accrued out of heterogeneous algorithms. Other recently proposed approaches too are in general inadequate.In this paper, we propose a simple and effective technique for work partitioning in the context of heterogeneous algorithms. Our technique is based on sampling and therefore can adapt to both the algorithm used and the input instance. Our technique is generic in its applicability as we will demonstrate in this paper. We validate our technique on three problems: finding the connected components of a graph (CC), multiplying two unstructured sparse matrices (spmm), and multiplying two scalefree sparse matrices. For these problems, we show that using our method, we can find the required threshold that is under 10% away from the best possible thresholds.

Deep learning frameworks have recently gained widespread popularity due to their highly accurate prediction capabilities and availability of low cost processors that can perform training over a large dataset quickly. Given the high core count in modern generation high performance computing systems, training deep networks over large data has now become practical. In this work, while targeting the Computational Network Toolkit (CNTK) framework, we propose new mechanisms and designs to boost the performance of the communications between GPU nodes. We perform thorough analysis of the different phases of the toolkit such as I/O, communications, and computation of CNTK to identify the different bottlenecks that can be potentially alleviated using the high performance capabilities provided by many CUDA aware MPI runtimes. Using a CUDA aware MPI library, we propose CUDA Aware CNTK (CA-CNTK) which does low overhead communications. Different datasets ranging from small to large sizes prove the advantage of our re-design, and how it can show similar results on deep learning frameworks having a similar execution pattern. Our designs show an average improvement of 23%, 21% and 15% per epoch for the popular CIFAR10, MNIST and ImageNet datasets, respectively.

GPU accelerators are widely used in HPC clusters due to their massive parallelism and high throughput-per-watt. Data movement continues to be the major bottleneck on GPU clusters, more so when data is non-contiguous, which is common in scientific applications. CUDA-Aware MPI libraries optimize the non-contiguous data movement processing using latency oriented techniques such as using GPU kernels to accelerate the packing/unpacking operations. Although they optimize the latency of a single operation, the inherent restrictions of the designs limit their efficiency for throughput oriented patterns. Indeed, none of the existing designs fully exploit the massive parallelism of the GPUs to provide high throughput and efficient resources utilization by enabling maximal overlap. In this paper, we propose novel designs for CUDA-Aware MPI libraries to achieve efficient GPU resource utilization and maximal overlap between CPUs and GPUs for non-contiguous data processing and movement. The proposed designs take advantage of several CUDA features, such as Hyper-Q/multi-streams and callback function, to deliver high performance and efficiency. To the best of our knowledge, this is the first such study to provide high throughput and efficient resource utilization for non-contiguous MPI data processing and movement to/from GPUs. The performance evaluation with the proposed designs using DDTBench shows up to 54%, 67%, 61% performance improvement on the SPECFEM3D_oc, SPECFEM3D_cm and WRF_y_sa benchmarks respectively for intra-node inter-GPU ping-pong experiments. The proposed designs also deliver up to 33% improvement on the total execution time over the existing designs for the HaloExchange-based application kernel that models the communication pattern of the MeteoSwiss weather forecasting model over 32 GPU nodes on Wilkes GPU cluster.

Graph algorithms play a prominent role in several fields of sciences and engineering. Notable among them are graph traversal, finding the connected components of a graph, and computing shortest paths. There are several efficient implementations of the above problems on a variety of modern multiprocessor architectures. It can be noticed in recent times that the size of the graphs that correspond to real world data sets has been increasing. Parallelism offers only a limited succor to this situation as current parallel architectures have severe short-comings when deployed for most graph algorithms. At the same time, these graphs are also getting very sparse in nature. This calls for particular work efficient solutions aimed at processing large, sparse graphs on modern parallel architectures. In this paper, we introduce graph pruning as a technique that aims to reduce the size of the graph. Certain elements of the graph can be pruned depending on the nature of the computation. Once a solution is obtained for the pruned graph, the solution is extended to the entire graph. We apply the above technique on three fundamental graph algorithms: breadth first search (BFS), Connected Components (CC), and All Pairs Shortest Paths (APSP). To validate our technique, we implement our algorithms on a heterogeneous platform consisting of a multicore CPU and a GPU. On this platform, we achieve an average of 35% improvement compared to state-ofthe-art solutions. Such an improvement has the potential to speed up other applications that rely on these algorithms.

The advent of multicore and many-core architectures saw them being deployed to speed-up computations across several disciplines and application areas. Prominent examples include semi-numerical algorithms such as sorting, graph algorithms, image processing, scientific computations, and the like. In particular, using GPUs for general purpose computations has attracted a lot of attention given that GPUs can deliver more than one TFLOP of computing power at very low prices. In this work, we use a new model of multicore computing called hybrid multicore computing where the computation is performed simultaneously a control device, such as a CPU, and an accelerator such as a GPU. To this end, we use two case studies to explore the algorithmic and analytical issues in hybrid multicore computing. Our case studies involve two different ways of designing hybrid multicore algorithms. The main contribution of this paper is to address the issues related to the design of hybrid solutions. We show our hybrid algorithm for list ranking is faster by 50% compared to the best known implementation [Z. Wei, J. JaJa; IPDPS 2010]. Similarly, our hybrid algorithm for graph connected components is faster by 25% compared to the best known GPU implementation [26].