Generalized sparse matrix-matrix multiplication (SpGEMM) is a critical computational primitive that is highly memory-bound due to its inherent irregular data-dependent access pattern. Near-bank processing-in-memory (PIM) is a promising technique to overcome the memory bottleneck of SpGEMM by performing computations near the bank where the data is stored. However, earlier PIM studies fail to fully utilize the high memory bandwidth when performing SpGEMM due to low bank-level parallelism. As a result, 80% memory bandwidth is wasted as observed in our in-depth experimental analysis.Our key insight in this paper is that non-conflicting matrix columns in SpGEMM, where each row of these columns has no more than one non-zero element, can be processed simultaneously in different banks. We hence propose HighP, a near-bank PIM accelerator for SpGEMM with high bank-level parallelism. We first propose a set-based search mechanism, which finds non-conflicting columns through set operations automatically. We then develop a DIMM-based PIM architecture with detailed hardware and workflow designs for SpGEMM. Set operation logic and unified scratchpad memory management are designed to perform set operations with high computational parallelism and to enhance data reuse, respectively. HighP provides up to 17.88× performance improvement compared to the state-of-th-eart SpGEMM accelerator and achieves up to 8.19× performance improvement over the state-of-the-art PIM solution.

Hypergraph Neural Networks (HGNNs) are increasingly utilized to analyze complex inter-entity relationships. Traditional HGNN systems, based on a hyperedge-centric dataflow model, independently process aggregation tasks for hyperedges and vertices, leading to significant computational redundancy. This redundancy arises from recalculating shared information across different tasks. For the first time, we identify and harness implicit dataflows (i.e., dependencies) within HGNNs, introducing the microedge concept to effectively capture and reuse intricate shared information among aggregation tasks, thereby minimizing redundant computations. We have developed a new microedge-centric dataflow model that processes shared information as fine-grained microedge aggregation tasks. This dataflow model is supported by the Read-Process-Activate-Generate execution model, which aims to optimize parallelism among these tasks. Furthermore, our newly developed MeHyper, a microedge-centric HGNN accelerator, incorporates a decoupled pipeline for improved computational parallelism and a hierarchical feature management strategy to reduce off-chip memory accesses for large volumes of intermediate feature vectors generated. Our evaluation demonstrates that MeHyper substantially outperforms the leading CPUbased system PyG-CPU and the GPU-based system HyperGef, delivering performance improvements of $1,032.23 \times$ and $10.51 \times$, and energy efficiencies of $1,169.03 \times$ and $9.96 \times$, respectively.

Graph processing is pivotal in deriving insights from complex data structures but faces performance limitations due to the irregular nature of graphs. Traditional general-purpose processors often struggle with low instruction-level parallelism and energy inefficiency when handling graph data. In response, modern graph accelerators have embraced an intra-edge-parallel model to enhance parallelization, significantly outperforming conventional processors. However, the indiscriminate processing of edges in existing systems results in substantial computational redundancy, negatively impacting overall efficiency. This article introduces PRAGA, an innovative graph accelerator designed to optimize efficiency by selectively processing edges that significantly contribute to final results while preserving high computational parallelism. PRAGA utilizes an intra-edge-sequential model, prioritizing edge processing to capitalize on coarse-grained vertex-level parallelism and minimize unnecessary computations. It incorporates a hot-value manager to alleviate network-on-chip congestion and a memory-aware coalescer to minimize redundant data accesses. Our experimental results, obtained using a Xilinx Alveo U280 FPGA accelerator card, demonstrate that PRAGA achieves speedups of 17.88× and 5.86× over state-of-the-art accelerators ScalaGraph and GraphDyns, respectively, and outperforms the advanced GPU-based system Gunrock by 22.52× on average. This substantial improvement underscores PRAGA’s potential to redefine performance benchmarks in graph processing.

Sparse general matrix-matrix multiplication is widely used in data mining applications. Its irregular memory access patterns limit the performance of general-purpose processors, thus motivating many FPGA-based hardware innovations in recent years. Nevertheless, existing accelerators fail to efficiently support heterogeneous input matrix sparsity, which is universal in various real-world applications. With in-depth experimental analysis, we observe that their performance is bottlenecked by their fixed tiling mechanisms, which only alleviate the irregularity of one input matrix. Based on the observation, we propose SpaHet, a software/hardware co-design to accelerate heterogeneous-sparsity based sparse matrix multiplication. SpaHet adopts a dual-adaptive sliding window mechanism to cover the reuse characteristics of both input matrices simultaneously. With a specialized exploration algorithm, the window-based mechanism can automatically find the optimal tiling strategy instead of applying a fixed one based on empirical experience. A sparsity-aware merge tree is also proposed to maximize the output matrix reuse via accumulating intermediate results thoroughly. Our results on a Xilinx Alveo U280 accelerator card show that SpaHet outperforms state-of-the-art CPU-, GPU- and FPGA-based solutions by 7.71×, 1.1×, and 2.74× in performance, respectively.

With the merits of high productivity and ease of use, highlevel synthesis (HLS) tools bring hope to fast FPGA-based architecture development. However, their usability and popularity are still limited due to lack of support for dynamic memory management (DMM). Though HLS-compatible DMM solutions have been proposed recently, nevertheless, based on our investigation, none of them can hit high performance (i.e., minimal memory (de-)allocation latency) and resource efficiency (i.e., managing arbitrarily sized memory with minimal FPGA resource consumption) with one stone, seriously limiting their practicality. In response, we propose HeroDMM, a high-performance and resource-efficient dynamic memory manager for HLS. Specifically, HeroDMM organizes the managed memory area with a novel cartesian-like tree (CT) structure, a key to resolving the dilemma between (de-)allocation latency and resource efficiency standing in front of prior efforts. With the CT structure, HeroDMM further devises a delicate memory management algorithm and specializes the hardware implementation for achieving ever-higher performance while ensuring resource efficiency. Results show that HeroDMM outperforms state-of-the-art HLS-compatible DMM solutions by 61.69%~99.99% in performance improvement and 23.79%~97.22% in resource consumption savings.

Nowadays, high-level synthesis (HLS) has gained prominence for FPGA-based architecture prototyping, enhancing productivity significantly. Despite this advancement, HLS tools are impeded by a critical drawback: they lack support for dynamic memory management (DMM), leading to static mem-ory allocation and suboptimal use of memory resources. In response, numerous efforts have been made to develop DMM solutions compatible with HLS. However, our analysis indicates that existing solutions fail to concurrently meet the desired trifecta of scalability (efficient management of memory of any size), efficiency (minimal latency in memory (de-)allocation), and robustness (low allocation failure rates). This limitation hampers their applicability in real-world scenarios. In this paper, we introduce GraDMM, a “three-birds-one- stone” solution that comprehensively enhances the scalability, efficiency, and robustness of DMM. The key insight is to formulate memory (de-)allocation as graph analytics and lever-age sophisticated FPGA-based graph processing techniques. To achieve scalability, GraDMM specializes a simplified pipeline that significantly suppresses resource utilization expansion caused by managed memory scaling. This is crucial for managing arbitrarily sized memory on resource-limited FPGA platforms. For efficiency, GraDMM implements a data-centric concurrent traversal scheme and a shortcut-assisted fast traversal policy to accelerate (de-)allocation-guided graph traversal, reducing mem-ory (de-)allocation latency. To enhance robustness, GraDMM incorporates an adaptive memory defragmenter that defragments managed memory to minimize fragmentation-induced allocation failures. GraDMM is encapsulated as a library, providing high- level interfaces for users and ensuring synthesizability with Vi- vado HLS. Experimental results demonstrate that GraDMM out-performs three state-of-the-art HLS-compatible DMM solutions by significant margins: 56.71 %-85.59% in resource consumption savings, 78.94 % -99.99 % in (de-)allocation latency improvement, and 10.71 %-65.75% in allocation failure reduction.

Hypergraph processing has emerged as an effective approach to analyze complex multilateral relationships in real-world scenarios. Existing hypergraph processing solutions based on conventional architectures are severely bottlenecked by off-chip memory accesses. In this paper, we propose the first Processing-In-Memory (PIM)-featured ReRAM-based hypergraph accelerator, dubbed PhGraph, which facilitates performance-and energy-efficient hypergraph processing. On the hardware level, PhGraph integrates analog memristor-based PIM (with high matrix-grained parallelism) and digital memristor-based PIM (for high bipartite-edge-grained efficiency) into one standalone solution. On the software level, an overlap-aware hypergraph partitioning mechanism is proposed to polarize hypergraph workloads into matrix-formatted dense and bipartite-edge-formatted sparse partitions for performance acceleration using analog memristor-based PIM and digital ones, respectively. In addition, PhGraph is equipped with load-balanced partition scheduling and algorithm mapping co-designs to boost hardware utilization and efficiency. Experimental results show that PhGraph outperforms the state-of-the-art CPU-, FPGA-, and ASIC-based solutions by up to 4,309.81×, 547.13×, and 166.76× in terms of performance, and 36,416.11×, 924.12×, and 41.44× in terms of energy-savings, respectively.

3D reconstruction is a fundamental task in robotics and AI, providing a prerequisite for many related applications. Fringe projection profilometry is an efficient and non-contact method for generating 3D point clouds out of 2D images. However, during the actual measurement, it is inevitable to experiment with translucent objects, such as skin, marble, and fruit. Indirect illumination from these objects has substantially compromised the precision of 3D reconstruction via the contamination of 2D images. This paper presents a fast and accurate approach to correct for indirect illumination. The essential idea is to design a highly suitable network architecture founded on a precise error model that facilitates accurate error rectification. Initially, our method transforms the error generated by indirect illumination into a sine series. Based on this error model, the multilayer perceptron is more effective in error correction than traditional methods and convolutional neural networks. Our network was trained solely on simulated data but was tested on authentic images. Three sets of experiments, including two sets of comparison experiments, indicate that the designed network can efficiently rectify the error induced by indirect illumination.

Fringe projection profilometry is a widely used technique for 3D measurement due to its high accuracy and speed. However, the accuracy significantly decreases when measuring complex texture objects, especially in the junction of different colors. This paper analyzes the causes of errors resulting from complex textures and proposes a height compensation method to revise the error by employing a dual-projector structure. Moreover, the dual-projector is capable of acquiring a pair of errors with opposite signs, which can be utilized to calculate the accurate 3D information after determining the ratio of this pair of errors. Experiments provide significant improvement in measuring complex texture objects, demonstrating the proposed method's ability.

Genome graphs analysis has emerged as an effective means to enable mapping DNA fragments (known as reads) to the reference genome. It replaces the traditional linear reference with a graph-based representation to augment the genetic variations and diversity information, significantly improving the quality of genotyping. The in-depth characterization of genome graphs analysis uncovers that it is bottlenecked by the irregular seed index access and the intensive alignment operation, stressing both the memory system and computing resources.Based on these observations, we propose MeG2, a lightweight, commodity DRAM-compliant, processing-in-memory architecture to accelerate genome graphs analysis. MeG2is specifically integrated with the capabilities of both near-memory processing and bitwise in-situ computation. Specifically, MeG2leverages the low access latency of near-memory processing with the index-centric offload mechanism to alleviate the irregular memory access in the seeding procedure, and harnesses the row-parallel capacity of in-situ computation with the distance-aware technique to exploit the intensive computational parallelism in the alignment process. Results show that MeG2outperforms the CPU-, GPU-, and ASIC-based genome graphs analysis solutions by 502× (30.2×), 272× (15.1× ), and 5.5× (8.3×) for short (long) reads, while reducing energy consumption by 1628× (85.6×), 1443× (77.1×), and 7.8× (11.7×), respectively. We also demonstrate that MeG2offers significant improvements over existing PIM-based genome sequence analysis accelerators.

Multi-version graph processing has been widely used to solve many real-world problems. The process of the multi-version graph processing typically includes: (1) a history graph version switching at a specific time and (2) graph processing on this history graph. Existing multi-version graph systems assume ideally that every request for a particular graph version at a particular time will have a corresponding snapshot available. However, in most cases, this is not true. Then existing solutions usually have to settle with an "approximating" version as a substitute, leading to unexpected results for the underlying graph algorithm and thus reducing the practicality of a multi-version graph system for many application scenarios significantly.In this paper, we observe that only a few graph updates have a great impact on the final results. We therefore present AFaVS, a novel multi-version graph system that can improve accuracy effectively in both time- and memory-efficient manners. The cornerstone of AFaVS lies in a novel concept "value" that characterizes the importance of graph updates. AFaVS proposes differential management of updates based on their values and achieves higher accuracy while preserving processing and memory efficiency. AFaVS is also equipped with value-guided version switching and locality-aware optimizations to boost its overall efficiency. Our results on a variety of real-world datasets show that AFaVS outperforms four state-of-the-art multi-version graph systems by 74.35%~95.72% in terms of accuracy improvement and 57.03%~90.44% in terms of memory reduction while introducing less than 2.96% extra computing time. We have deployed AFaVS in a disaster recovery system on the production cluster of Alibaba, achieving 78.8%~90.1% fewer error rates than advanced systems at a comparable efficiency.

Graph convolutional networks(GCNs) are promising to enable machine learning on graph data. GCNs show potential vertex-level and intra-vertex parallelism for GPU acceleration, but their irregular memory accesses arising in aggregation operations and the inherent sparsity for vertex features of graphs cause inefficiencies on the GPU. In this paper, we present gPIM, which aims to accelerate GCNs inference through aprocessing-in-memory(PIM) enabled architecture. gPIM is expected to perform compute-intensive combination on the GPU while aggregation and memory-bound combination are offloaded to the PIM-featuredhybrid memory cubes(HMCs). To maximize the efficiency of such GPU-HMC architecture, gPIM is novel with two key designs: 1) A GCN-induced graph partitioning that minimizes communication overheads between cubes, 2) A programmer-transparent performance estimation mechanism that predicts the performance bound of operations accurately for workload offloading. Experimental results show that gPIM significantly outperforms Intel Xeon E5-2680v3 CPU (8,979.52×), NVIDIA Tesla V100 GPU (96.01×), and a state-of-the-art GCN accelerator AWB-GCN (4.18×).

Graph convolutional networks (GCNs) are promising to enable machine learning on graphs. GCNs exhibit mixed computational kernels, involving regular neural-network-like computing and irregular graph-analytics-like processing. Existing GCN accelerators obey a divide-and-conquer philosophy to architect two separate types of hardware to accelerate these two types of GCN kernels, respectively. This hybrid architecture improves intra-kernel efficiency but considers little inter-kernel interactions in a holistic view for improving overall efficiency.In this paper, we present a new GCN accelerator, RE-FLIP, with three key innovations in terms of architecture design, algorithm mappings, and practical implementations. First, ReFlip leverages PIM-featured crossbar architectures to build a unified architecture for supporting the two types of GCN kernels simultaneously. Second, ReFlip adopts novel algorithm mappings that can maximize potential performance gains reaped from the unified architecture by exploiting the massive crossbar-structured parallelism. Third, ReFlip assembles software/hardware co-optimizations to process real-world graphs efficiently. Compared to the state-of-the-art software frameworks running on Intel Xeon E5-2680v4 CPU and NVIDIA Tesla V100 GPU, ReFlip achieves the average speedups of 6,432× and 86.32× and the average energy savings of 9,817× and 302.44×, respectively. In addition, ReFlip also outperforms a state-of-the-art GCN hardware accelerator, AWB-GCN, by achieving an average speedup of 5.06× and an average energy saving of 15.63×.

Beyond ordinary graphs, hypergraphs are a graph representation to flexibly express complex multilateral relationships between entities. Hypergraph processing can be used to solve many real-world problems, e.g., machine learning, VLSI design, and image retrieval. Existing hypergraph processing systems handle a hypergraph in order of its hyperedge and vertex indices. This makes processing hypergraphs on generalpurpose architectures suffer significantly from excessive offchip memory accesses, most of which however are redundant in frequently accessing overlapped hyperedges and vertices, but the index-ordered scheduling destroys this potential locality.In this paper, we propose a novel Generate-Load-Apply (GLA) execution model to improve locality in hypergraph processing. The key insight of GLA is to use a concept of chain to characterize the overlapped feature of a hypergraph, exposing data reuse opportunities missed in existing hypergraph systems. The precondition of driving GLA model is to generate expected chains on the fly, but the software solution is so expensive that its overheads may outweigh the benefits achieved from the chain-driven scheduling. We further present ChGraph, the first hardware-accelerated hypergraph processing engine near each core. ChGraph is specialized in accelerating the chain generation and the chain-guided data loading (to hide memory access latency) while the general-purpose cores are responsible only for handling the apply operations of GLA. We evaluate ChGraph against a state-of-the-art hypergraph processing system Hygra on six hypergraph algorithms using five large real-world hypergraphs. Results on a simulated 16core system show that ChGraph reduces the number of offchip memory accesses by up to 4.56× and achieves up to 4.73× speedup while introducing only 0.26% area overhead.

Graph processing is promising to extract valuable insights in graphs. Nowadays, emerging 3D-stacked memories and silicon technologies can provide over terabytes per second memory bandwidth and thousands of processing elements (PEs) to meet the high hardware demand of graph applications. However, this leap in hardware capability does not result in a huge increase but even a degradation sometimes in performance for graph processing. In this paper, we discover that the centralized on-chip memory hierarchy adopted in existing graph accelerators is the villain causing poor scalability due to its quadratic increase of hardware overheads with respect to the number of PEs.We present a novel distributed on-chip memory hierarchy by leveraging the network-on-chip (NoC) to enable massively parallel graph processing. We architect ScalaGraph, a brand new graph processing accelerator, to exploit this insight. ScalaGraph adopts a software-hardware co-design to minimize NoC communication overheads via an efficient row-oriented dataflow mapping and runtime aggregation. A specialized scheduling mechanism is also proposed to improve load imbalance. Our results on a Xilinx Alveo U280 FPGA card show that ScalaGraph on a modest configuration of 512 PEs achieves 2.2× and 3.2× speedups over a state-of-theart graph accelerator GraphDyns and a GPU-based graph system Gunrock, respectively. Moreover, ScalaGraph enables supporting at least 1,024 PEs with nearly linear performance scaling while GraphDyns fails to work.

Processing-in-memory (PIM) is promising to solve the well-known data movement challenge by performing in-situ computations near the data. Leveraging PIM features is pretty profitable to boost the energy efficiency of applications. Early studies mainly focus on improving the programmability for computation offloading on PIM architectures. They lack a comprehensive analysis of computation locality and hence fail to accelerate a wide variety of applications. In this paper, we present a general-purpose instruction-level offloading technique for near-DRAM PIM architectures, namely IOTPIM, to exploit PIM features comprehensively. IOTPIM is novel with two technical advances: 1) a new instruction offloading policy that fully considers the locality of the whole on-chip cache hierarchy, and 2) an offloading performance benefit prediction model that directly predicts offloading performance benefits of an instruction based on the input dataset characterizes, preserving low analysis overheads. The evaluation demonstrates that IOTPIM can be applied to accelerate a wide variety of applications, including graph processing, machine learning, and image processing. IOT-PIM outperforms the state-of-the-art PIM offloading techniques by 1.28×-1.51× while ensuring offloading accuracy as high as 91.89% on average.

Hypergraph processing has emerged as a powerful approach for analyzing complex multilateral relationships among multiple entities. Past research on building hypergraph systems suggests that changing the scheduling order of bipartite edge tasks can improve the overlap-induced data locality in hypergraph processing. However, due to the complex intertwined connections between vertices and hyperedges, it is almost impossible to find a locality-optimal scheduling order. Thus, these task-centric hypergraph systems often suffer from substantial off-chip communications. In this paper, we first propose a novel data-centric Load-Trigger-Reduce (LTR) execution model to exploit fully the locality in hypergraph processing. Unlike a task-centric model that loads the required data along with a task, our LTR model invokes tasks as per the data used. Specifically, once the hypergraph data is loaded into the on-chip memory, all of its relevant computation tasks will be triggered simultaneously to output intermediate results, which are finally reduced to update the final results. Our LTR model enables all hypergraph data to be accessed once in each iteration. To fully exploit the LTR performance potential, we further architect an LTR-driven hypergraph accelerator, XuLin, which features with an adaptive data loading mechanism to minimize the loading cost via chunk merging at runtime. XuLin is also equipped with a priority-based differential data reduction scheme to reduce the impact of conflicting updates on performance. We have implemented XuLin both on a Xilinx Alveo U250 FPGA card and using a cycle-accurate simulator. The results show that XuLin outperforms the state-of-the-art hypergraph processing solutions Hygra and ChGraph by $20.47 \times$ and $8.77 \times$ on average, respectively.

Dynamic graph convolutional networks (DGCNs) have emerged as an effective approach to analyzing graph data that is constantly changing. The typical DGCNs incorporate not only graph convolutional networks (GCNs) to extract the structural information but also with recurrent neural networks (RNNs) to capture the temporal information from evolving graph data. These two alternative execution kernels of DGCNs impose unique architecture challenges for both types of kernels to be implemented efficiently. The presence of complex execution patterns of DGCNs renders existing architectures unsuitable. In this article, we present the first DGCN accelerator with an integrated architecture, named ReaDy, to accelerate DGCNs based on emerging PIM-featured ReRAM architectures. ReaDy is novel with an integrated architecture that enables running the GCN and RNN kernels of DGCNs simultaneously. Specifically, ReaDy is equipped with a redundancy-free scheduling mechanism to alleviate intrinsic dynamic irregularity for the GCN kernel, improving hardware utilization. In addition, ReaDy also includes a locality-aware dataflow strategy to exploit the inherent intervertex data locality for the RNN kernel, reducing superfluous data accesses to vertices and weight parameters. In a holistic view, ReaDy further enhances the entire system via an interkernel pipeline to reduce the off-chip accesses of intermediate results, boosting the overall efficiency of DGCNs significantly. Compared to the state-of-the-art software framework, PyGT, running on Intel Xeon E5-2680v4 CPU and NVIDIA Ampere A100 GPU, ReaDy achieves the average speedups of$955\times $and$27.33\times $, and the average energy savings of 1$093\times $and$80.21\times $, respectively. In addition, ReaDy outperforms ReFlip-ERA, which is obtained by combining a state-of-the-art GCN accelerator ReFlip and RNN accelerator ERA-LSTM, by an average speedup of$8.30\times $and an average energy saving of$7.29\times $.

Graph mining aims to explore interesting structural information of a graph. Pattern-centric systems typically transform a generic-purpose graph mining problem into a series of subgraph matching problems for high performance. Existing pattern-centric mining systems reduce the substantial search space towards a single pattern by exploring a highly-optimized matching order, but inherent computational redundancies of such a matching order itself still suffer severely, leading to significant performance degradation. The key innovation of this work lies in a general redundancy criterion that characterizes computational redundancies arising in not only handing a single pattern but also matching multiple patterns simultaneously. In this paper, we present SumPA, a high-performance pattern-centric graph mining system that can sufficiently remove redundant computations for any complex graph mining problems. SumPA features three key designs: (1) a pattern abstraction technique that can simplify numerous complex patterns into a few simple abstract patterns based on pattern similarity, (2) abstraction-guided pattern matching that completely eliminates (totally and partially) redundant computations during subgraph enumeration, and (3) a suite of system optimizations to maximize storage and computation efficiency. Our evaluation on a wide variety of real-world graphs shows that SumPA outperforms the two state-of-the-art systems Peregrine and GraphPi by up to 61.89× and 8.94×, respectively. For many mining problems on large graphs, Peregrine takes hours or even days while SumPA finishes in only a few minutes.

Existing FPGA-based graph accelerators, typically designed for static graphs, rarely handle dynamic graphs that often involve substantial graph updates (e.g., edge/node insertion and deletion) over time. In this paper, we aim to fill this gap. The key innovation of this work is to build an FPGA-based dynamic graph accelerator easily from any off-the-shelf static graph accelerator with minimal hardware engineering efforts (rather than from scratch). We observe \em spatial similarity of dynamic graph updates in the sense that most of graph updates get involved with only a small fraction of vertices. We therefore propose an FPGA library, called GraSU, to exploit spatial similarity for fast graph updates. GraSU uses a differential data management, which retains the high-value data (that will be frequently accessed) in the specialized on-chip UltraRAM while the overwhelming majority of low-value ones reside in the off-chip memory. Thus, GraSU can transform most of off-chip communications arising in dynamic graph updates into fast on-chip memory accesses. Our experiences show that GraSU can be easily integrated into existing state-of-the-art static graph accelerators with only 11 lines of code modifications. Our implementation atop AccuGraph using a Xilinx Alveo#8482; \ U250 board outperforms two state-of-the-art CPU-based dynamic graph systems, Stinger and Aspen, by an average of 34.24× and 4.42× in terms of update throughput, improving further overall efficiency by 9.80× and 3.07× on average.

Processing-In-Memory (PIM) is an emerging technology that addresses the memory bottleneck of graph processing. In general, analog memristor-based PIM promises high parallelism provided that the underlying matrix-structured crossbar can be fully utilized while digital CMOS-based PIM has a faster single-edge execution but its parallelism can be low. In this paper, we observe that there is no absolute winner between these two representative PIM technologies for graph applications, which often exhibit irregular workloads. To reap the best of both worlds, we introduce a new heterogeneous PIM hardware, called Hetraph, to facilitate energy-efficient graph processing. Hetraph incorporates memristor-based analog computation units (for high-parallelism computing) and CMOS-based digital computation cores (for efficient computing) on the same logic layer of a 3D die-stacked memory device. To maximize the hardware utilization, our software design offers a hardware heterogeneity-aware execution model and a workload offloading mechanism. For performance speedups, such a hardware-software co-design outperforms the state-of-the-art by 7.54 ×(CPU), 1.56 ×(GPU), 4.13× (memristor-based PIM) and 3.05× (CMOS-based PIM), on average. For energy savings, Hetraph reduces the energy consumption by 57.58× (CPU), 19.93× (GPU), 14.02 ×(memristor-based PIM) and 10.48 ×(CMOS-based PIM), on average.

Graph mining is becoming increasingly important due to the ever-increasing demands on analyzing complex structures in graphs. Existing graph accelerators typically hold most of the randomly-accessed data in an on-chip memory to avoid off-chip communications. However, graph mining exhibits substantial random accesses from not only vertex dimension but also edge dimension (with the latter being excessively more complex than the former), leading to significant degradations in terms of both performance and energy efficiency.We observe that the most random memory requests arising in graph mining come from accessing a small fraction of valuable (vertex and edge) data when handling real-world graphs. To exploit this extension locality with maximum parallelism, we architect GRAMER, the first graph mining accelerator. GRAMER contains a specialized memory hierarchy, where the valuable data (precisely identified through a cost-efficient heuristic) is permanently resident in a high-priority memory while others are maintained in a cache-like memory under a lightweight replacement policy. The specific pipelined processing units are carefully designed to maximize computational parallelism. GRAMER is also equipped with a work-stealing mechanism to reduce load imbalance. We have implemented GRAMER on a Xilinx Alveo U250 accelerator card. Compared with two state-of-the-art CPU-based graph mining systems, Fractal and RStream, running on a 14-core Intel E5-2680 v4 processor, GRAMER achieves not only considerable speedups (1.11 × ~ 129.95 ) but also significant energy savings (5.79 × ~ 678.34×)

With the maturity of monolithic 3D integration, 3D ReRAM provides impressive storage-density and computational-parallelism with great opportunities for parallel-graph processing acceleration. In this paper, we present RAGra, a 3D ReRAM-based graph processing accelerator, which has two significant technical highlights. First, monolithic 3D ReRAM usually has the complexly-intertwined feature with shared input wordlines and output bitlines for different layers. We propose novel mapping schemes, which can guide to apply different graph algorithms into 3D ReRAM seamlessly and correctly for exposing the inherently-irregular parallelism of 3D ReRAM. Second, consider the sparsity of real-world graphs, we further propose a row- and column-mixed execution model, which can filter invalid subgraphs for exploiting the massive parallelism of 3D ReRAM. Our evaluation on 8-layer stacked ReRAM shows that RAGra outperforms state-of-the-art planar (2D) ReRAM based graph accelerator GraphR by 6.18× performance improvement and 2.21 ×energy saving, on average. In particular, RAGra significantly outperforms Grid-Graph (a typical CPU-based graph system) by up to 293.12×.

Graph-specific computing with the support of dedicated accelerator has greatly boosted the graph processing in both efficiency and energy. Nevertheless, their data conflict management is still sequential when certain vertex needs a large number of conflicting updates at the same time, leading to prohibitive performance degradation. This is particularly true and serious for processing natural graphs.

Existing graph processing frameworks greatly improve the performance of memory subsystem, but they are still subject to the underlying modern processor, resulting in the potential inefficiencies for graph processing in the sense of low instruction level parallelism and high branch misprediction. These inefficiencies, in accordance with our comprehensive micro-architectural study, mainly arise out of a wealth of dependencies, serial semantic of instruction streams, and complex conditional instructions in graph processing. In this paper, we propose that a fundamental shift of approach is necessary to break through the inefficiencies of the underlying processor via the dataflow paradigm. It is verified that the idea of applying dataflow approach into graph processing is extremely appealing for the following two reasons. First, as the execution and retirement of instructions only depend on the availability of input data in dataflow model, a high degree of parallelism can be therefore provided to relax the heavy dependency and serial semantic. Second, dataflow is guaranteed to make it possible to reduce the costs of branch misprediction by simultaneously executing all branches of a conditional instruction. Consequently, we make the preliminary attempt to develop the dataflow insight into a specialized graph accelerator. We believe that our work would open a wide range of opportunities to improve the performance of computation and memory access for large-scale graph processing.