Graph pattern mining is essential for analyzing dynamic networks, where graphs evolve over time. To accommodate these changes, existing solutions update match sets incrementally, avoiding the need to re-mine the entire graph and achieving significant performance improvements. However, these methods suffer from inefficiencies due to redundant set intersection operations across subgraph instances, causing performance degradation.

The growing demand for high-bandwidth and largecapacity memory access in data-intensive workloads has driven the development and deployment of Processing-in-Memory (PIM) architectures. However, existing DIMM-based PIM systems suffer from the severe communication bottleneck between the processing elements (PEs) near the PIM banks due to their requirement on host CPU forwarding. This bottleneck limits the efficiency of collective operations and degrades scalability and performance for workloads that require inter-PE communication. To address the communication limitation, we propose CoCoTree, a computation-capable architecture for collective communication in scalable DIMM-based PIM. CoCoTree supports direct and high-throughput inter-PE communication without host intervention. CoCoTree accelerates key collective communication using novel hierarchical binary tree topology and lightweight in-network computation support. We design and implement microarchitectures for the main building blocks: Co-Leaf and Co-Node, to efficiently handle the data packing, routing, and processing in CoCoTree. Furthermore, we also introduce a packet-based communication protocol tailored to the CoCoTree architecture, which decouples control and data through a twophase configuration-computation communication mechanism to efficiently support a wide range of collective communication operations. CoCoTree effectively mitigates inter-PE communication bottlenecks, enabling scalable PIM systems capable of meeting the demands of growing data size. Experimental results show that CoCoTree achieves up to$95.6 \times$improvement for collective operations and improves end-to-end application performance by up to$10.5 \times$across various workloads over the baseline PIM, while outperforming state-of-the-art PIM communication architectures in both performance and scalability.

Multi-Scale Deformable Attention (MSDAttn) has become a fundamental component in various vision tasks due to its effective multi-scale grid sampling (MSGS). However, its reliance on random sampling results in highly irregular memory access patterns, making it a memory-intensive operation inefficient for GPUs. Near-memory processing (NMP) offers a promising solution for accelerating memory-bound kernels, yet existing NMP-based attention accelerators remain suboptimal for MSDAttn due to incompatible load balancing and data reuse strategies. Specifically, current NMP solutions uniformly distribute processing elements (PEs) across all banks, leading to significant PE underutilization and excessive cross-bank data transfers. Moreover, most rely on locality-based reuse, which fails under MSDAttn’s unpredictable sampling patterns.

With the explosive growth of modern graph data, ReRAM-based graph processing paradigms are emerging as promising solutions to the “memory wall” bottleneck. However, existing paradigms often lean on overly idealized ReRAM architectures, overlooking the critical influence of various hardware faults due to the analog nature and immature fabrication processes of realistic ReRAMs. These hardware faults can lead to convergence anomalies or unacceptable output deviations (i.e., Severe Errors), undermining the reliability of ReRAM-based graph processing. While some studies enhance the reliability of ReRAM-based computation through fault-aware remapping or robust algorithm design, the unique graph execution characteristics make these efforts challenging to migrate effectively. In this work, we first develop ReGFI, a microarchitecture-level Fault Injection framework for ReRAM-based Graph processing. Unlike traditional fault injection methods that only introduce random algorithm-level faults, ReGFI precisely maps hardware faults into the microarchitectural graph execution flow to effectively characterize their effects on the execution correctness. Based on ReGFI, we propose FReRAM, a Fault-Resilient graph processing paradigm in realistic ReRAMs. Firstly, observing the fault robustness of graph vertices compared to graph edges, we reverse-map the vertex values to the non-ideal crossbar while using the edge values as inputs, for proactive SE avoidance. Then, leveraging the cell idleness in ReRAM crossbars and bit-wise reliability discrepancies of graph data, we recycle idle crossbar cells and squeeze out approximable Least Significant Bits to robust-encode the fault-sensitive bits, for further SE elimination. Experimental results exhibit that FReRAM achieves 88.84% SE reduction while incurring negligible overhead for fault-resilient ReRAM-based graph processing. Furthermore, we evaluate the effectiveness and performance of FReRAM under different hardware configurations, graph datasets, and data formats.

Approximate nearest neighbor search (ANNS) is crucial in many applications to find semantically similar matches for user queries. Especially with the development of large language models (LLMs), ANNS is becoming increasingly important in retrieval-augmented generation (RAG). An in-depth analysis of ANNS reveals that its diverse operations, from extensive memory access to intensive sorting, are key performance bottlenecks, imposing significant strain on both the memory system and computing resources. Based on these observations, we present SeIM, a hierarchical in-memory architecture to accelerate ANNS. SeIM is designed to accommodate the diverse operational characteristics of ANNS. Specifically, SeIM offloads highly parallel memorybound operations to the memory bank level and introduces a unified execution model to reuse hardware units, requiring only lightweight modifications to standard DRAM architecture. Additionally, SeIM places compute-bound sorting operations, which require cross-unit data access, at the memory controller level and employs an adaptive transmission filtering technique to reduce unnecessary data transfers and processing during sorting. Our evaluation shows that SeIM achieves $268 \times 22 \times$, and $5 \times$ higher throughput, $306 \times 59 \times$, and $4 \times$ lower latency, and $3081 \times$, $287 \times$, and $2 \times$ higher power efficiency than state-of-the-art CPU-, GPU-, and ASIC-based ANNS solutions.

Heterogeneous Graph Neural Networks (HGNNs) are pivotal for extracting semantic and structural information from heterogeneous graphs. Traditional HGNN implementations often grapple with the challenges of excessive metapath instances, requiring substantial storage or incurring high instance-matching overhead. These methods typically suffer from redundant instance encoding and costly semantic graph construction. Addressing these issues, we introduce an advanced Metapath Graph (MG) abstraction that encapsulates the structural information of all metapath instances within a compact representation. This approach significantly reduces storage demands, eliminates redundant instance encodings, and foregoes the need for constructing semantic graphs, thereby facilitating rapid HGNN inference. Our software-based system, MetaHG, leverages layerwise encoding and aggregation to avoid redundancies without the necessity of semantic graphs. It incorporates a fast, lightweight partitioning method to efficiently manage large graphs. Distinctively, MetaHG seamlessly integrates with both dynamic HGNNs and homogeneous GNNs, unlike conventional systems. Comparative evaluations demonstrate that MetaHG surpasses the state-of-the-art BFS- and DFS-based HGNN systems, MAGNN and the software implementation of MetaNMP, by 42.5× and 4.53×, respectively, on average.

By integrating external knowledge bases, Retrieval-augmented Generation (RAG) enhances natural language generation for knowledgeintensive scenarios and specialized domains, producing content that is both more informative and personalized.RAG systems typically consist of two fundamental stages: retrieval and generation.The retrieval stage experiences low bandwidth utilization due to its random and irregular memory access patterns.Meanwhile, the generation stage is also constrained by memory bandwidth limitations, which arise from involving a significant number of General Matrix-Vector Multiplications (GEMV) operations.These two stages collectively lead to memory bottlenecks within RAG systems.Recent efforts leverage HBM-based Processing-in-Memory (PIM) to accelerate conventional Large Language Models (LLMs).However, the retrieval stage incurs substantial storage overhead due to the need to maintain large-scale knowledge bases, resulting in a capacity bottleneck.Solely relying on HBM-based PIM in RAG is both costly and insufficient to meet the capacity demands.Fortunately, DIMM-based PIM provides a low-cost, high-capacity alternative that complements HBM.In this work, we propose HeterRAG, a novel heterogeneous PIM acceleration system for RAG.It combines

Graph pattern mining is essential for deciphering complex networks. In the real world, graphs are dynamic and evolve over time, necessitating updates in mining patterns to reflect these changes. Traditional methods use fine-grained incremental computation to avoid full re-mining after each update, which improves speed but often overlooks potential gains from examining inter-update interactions holistically, thus missing out on overall efficiency improvements. In this article, we introduce Cheetah, a dynamic graph mining system that processes updates in a coarse-grained manner by leveraging exploration domains . These domains exploit the community structure of real-world graphs to uncover data reuse opportunities typically missed by existing approaches. Exploration domains, which encapsulate extensive portions of the graph relevant to updates, allow multiple updates to explore the same regions efficiently. Cheetah dynamically constructs these domains using a management module that identifies and maintains areas of redundancy as the graph changes. By grouping updates within these domains and employing a neighbor-centric expansion strategy, Cheetah minimizes redundant data accesses. Our evaluation of Cheetah across five real-world datasets shows it outperforms current leading systems by an average factor of 2.63×.

The memory-intensive embedding layer in recommendation model continues to be the performance bottleneck. While prior works have attempted to improve the embedding layer performance by exploiting the data locality to cache the frequently accessed embedding vectors and their partial sums. However, these solutions rely on the static cache, which is inapplicable in the embedding training scenario where the embedding vectors are updated frequently. To this end, this paper proposes ReFree, a redundancy-free near-memory processing (NMP) solution for recommendation model training. Specifically, ReFree identifies the reusable data in realtime for both embedding layer forward and backward stages and leverages a lightweight NMP architecture to enable redundancy-free near-memory acceleration of the entire embedding training process. Evaluation results on real-world datasets show that ReFree outperforms the state-of-the-art solutions by 10.9× and reduces 5.3× energy consumption on average.

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.

Personalized recommendation systems have become one of the most important Internet services nowadays. A critical challenge of training and deploying the recommendation models is their high memory capacity and bandwidth demands, with the embedding layers occupying hundreds of GBs to TBs of storage. The advent of memory disaggregation technology and Compute Express Link (CXL) provides a promising solution for memory capacity scaling. However, relocating memory-intensive embedding layers to CXL memory incurs noticeable performance degradation due to its limited transmission bandwidth, which is significantly lower than the host memory bandwidth. To address this, we introduce ReCXL, a CXL memory disaggregation system that utilizes near-memory processing for scalable, efficient recommendation model training. ReCXL features a unified, hardwareefficient NMP architecture that processes the entire embedding training within CXL memory, minimizing data transfers over the bandwidth-limited CXL and enhancing internal bandwidth. To further improve the performance, ReCXL incorporates softwarehardware co-optimizations, including sophisticated dependencyfree prefetching and fine-grained update scheduling, to maximize hardware utilization. Evaluation results show that ReCXL outperforms the CPU-GPU baseline and the naïve CXL memory by $7.1 \times \sim 10.6 \times(9.4 \times$ on average) and $12.7 \times \sim 31.3 \times(22.6 \times$ on average), respectively.

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.

Abstract Modern recommendation systems integrate graph convolution neural networks (GCN) for enhancing embedding representation. Compared with widely deployed neural network-based models, the extra message propagation layer of GCN-based recommendation is featured with extensive computations and irregular memory access. However, architecture designs for prevailing deep neural network recommendation models assume simple pooling in the embedding layer. ReRAM-based GCN accelerators are specialized for graph-related operations. However, they are designed for general graphs, while GCN-based recommendation models mainly operate on the user-item graph. In this paper, we proposed a resistive random accessed memory (ReRAM) based processing-in-memory (PIM) accelerator, ReGCNR, for GCN-based recommendation. ReGCNR is featured with three key innovations. First, we exploit the 3-dimensional (3-D) stacked heterogeneous ReRAM to fit with the large-size embedding table and user-item graph. Then, we propose a joint degree mapping schema that maximizes the efficiency of the execution pipeline. After that, ReGCNR assembles a well-coordinated pipeline and hardware scheduling design to boost overall system performance. Results show that ReGCNR outperforms GPU by 69.83 $$\times$$ × and 56.67 $$\times$$ × in terms of average speedup and energy saving, respectively. In addition, ReGCNR outperforms state-of-the-art ReRAM-based solutions by 11.13 $$\times$$ × speedups and 7.22 $$\times$$ × energy savings on average.

The attention-based neural network attracts great interest due to its excellent accuracy enhancement. However, the attention mechanism requires huge computational efforts to process unnecessary calculations, significantly limiting the system’s performance. To reduce the unnecessary calculations, researchers propose sparse attention to convert some dense-dense matrices multiplication (DDMM) operations to sampled dense-dense matrix multiplication (SDDMM) and sparse matrix multiplication (SpMM) operations. However, current sparse attention solutions introduce massive off-chip random memory access since the sparse attention matrix is generally unstructured. We propose CPSAA, a novel crossbar-based processing-in-memory (PIM)-featured sparse attention accelerator to eliminate off-chip data transmissions. First, we present a novel attention calculation mode to balance the crossbar writing and crossbar processing latency. Second, we design a novel PIM-based sparsity pruning architecture to eliminate the pruning phase’s off-chip data transfers. Finally, we present novel crossbar-based SDDMM and SpMM methods to process unstructured sparse attention matrices by coupling two types of crossbar arrays. Experimental results show that CPSAA has an average of 89.6×, 32.2×, 17.8×, 3.39×, and 3.84× performance improvement and 755.6×, 55.3×, 21.3×, 5.7×, and 4.9× energy-saving when compare with GPU, FPGA, SANGER, ReBERT, and ReTransformer.

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.

Due to the high complexity of constructing exact k -nearest neighbor graphs, approximate construction has become a popular research topic. The NN-Descent algorithm is one of the representative in-memory algorithms. To effectively handle large datasets, existing state-of-the-art solutions combine the divide-and-conquer approach and the NN-Descent algorithm, where large datasets are divided into multiple partitions, and a subgraph is constructed for each partition before all the subgraphs are merged, reducing the memory pressure significantly. However, such solutions fail to address inefficiencies in large-scale k -nearest neighbor graph construction. In this paper, we propose L-FNNG, a novel solution for accelerating large-scale k -nearest neighbor graph construction on CPU-FPGA heterogeneous platform. The CPU is responsible for dividing data and determining the order of partition processing, while the FPGA executes all construction tasks to utilize the acceleration capability fully. To accelerate the execution of construction tasks, we design an efficient FPGA accelerator, which includes the Block-based Scheduling (BS) and Useless Computation Aborting (UCA) techniques to address the problems of memory access and computation in the NN-Descent algorithm. We also propose an efficient scheduling strategy that includes a KD-tree-based data partitioning method and a hierarchical processing method to address scheduling inefficiency. We evaluate L-FNNG on a Xilinx Alveo U280 board hosted by a 64-core Xeon server. On multiple large-scale datasets, L-FNNG achieves, on average, 2.3× construction speedup over the state-of-the-art GPU-based solution.

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.

The k-nearest neighbor graph has emerged as the key data structure for many critical applications. However, it can be notoriously challenging to construct k-nearest neighbor graphs over large graph datasets, especially with a high-dimensional vector feature. Many solutions have been recently proposed to support the construction of k-nearest neighbor graphs. However, these solutions involve substantial memory access and computational overheads and an architecture-level solution is still absent. To address these issues, we architect FNNG, the first FPGA-based accelerator to support k-nearest neighbor graph construction. Specifically, FNNG is equipped with the block-based scheduling technique to exploit the inherent data locality between vertices. It divides the vertices that are close in space into blocks and process the vertices according to the granularity of the blocks during the construction process. FNNG also adopts the useless computation aborting technique to identify superfluous useless computations. It keeps the existing maximum similarity values of all vertices inside the computing unit. In addition, we propose an improved architecture in order to fully utilize both techniques. We implement FNNG on the Xilinx Alveo U280 FPGA card. The results show that FNNG achieves 190x and 2.1x speedups over the state-of-the-art CPU and GPU solutions, running on Intel Xeon Gold 5117 CPU and NVIDIA GeForce RTX 3090 GPU, respectively.

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.

Metapath-based heterogeneous graph models (MHGM) show excellent performance in learning semantic and structural information in heterogeneous graphs. Metapath matching is an essential processing step in MHGM to find all metapath instances, bringing significant overhead compared to the total model execution time. Even worse, in dynamic heterogeneous graphs, metapath instances require to be rematched while graph updated. In this paper, we observe that only a small fraction of metapath instances change and propose GraphMetaP, an efficient incremental metapath maintenance method in order to eliminate the matching overhead in dynamic heterogeneous graphs. GraphMetaP introduces a novel format for metapath instances to capture the dependencies among the metapath instances. The format incrementally maintains metapath instances based on the graph updates to avoide the rematching metapath overhead for the updated graph. Furthermore, GraphMetaP uses the fold way to simplify the format in order to recover all metapath instances faster. Experiments show that GraphMetaP enables efficient maintenance of metapath instances on dynamic heterogeneous graphs and outperforms 172.4X on average compared to the matching metapath method.

Heterogeneous graph neural networks (HGNNs) based on metapath exhibit powerful capturing of rich structural and semantic information in the heterogeneous graph. HGNNs are highly memory-bound and thus can be accelerated by near-memory processing. However, they also suffer from significant memory footprint (due to storing metapath instances as intermediate data) and severe redundant computation (when vertex features are aggregated among metapath instances). To address these issues, this paper proposes MetaNMP, the first DIMM-based near-memory processing HGNNs accelerator with reduced memory footprint and high performance. Specifically, we first propose a cartesian-like product paradigm to generate all metapath instances on the fly for heterogeneous graphs. In this way, metapath instances no longer need to be stored as intermediate data, avoiding significant memory consumption. We then design a data flow for aggregating vertex features on metapath instances, which aggregates vertex features along the direction of the metapath instances dispersed from the starting vertex to exploit shareable aggregation computations, eliminating most of the redundant computations. Finally, we integrate specialized hardware units in DIMM to accelerate HGNNs with near-memory processing, and introduce a broadcast mechanism for edge data and vertex features to mitigate the inter-DIMM communication. Our evaluation shows that MetaNMP achieves the memory space reduction of 51.9% on average and the performance improvement by 415.18× compared to NVIDIA Tesla V100 GPU.

The memory-intensive embedding layers of the personalized recommendation systems are the performance bottleneck as they demand large memory bandwidth and exhibit irregular and sparse memory access patterns. Recent studies propose near memory processing (NMP) to accelerate memory-bound embedding operations. However, due to the load imbalance caused by the skewed access frequency of the embedding data, existing NMP solutions that exploit fine-grained memory parallelism fail to translate the increasingly massive internal bandwidth to performance improvements, leading to resource underutilization and hardware overhead.

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×).

Approximate string matching (ASM) functions as the basic operation kernel for a large number of string processing applications. Existing Von-Neumann-based ASM accelerators suffer from huge intermediate data with the ever-increasing string data, leading to massive off-chip data transmissions. This paper presents a novel ASM processing-in-memory (PIM) accelerator, namely ReSMA, based on ReCAM- and ReRAM-arrays to eliminate the off-chip data transmissions in ASM. We develop a novel ReCAM-friendly filter-and-filtering algorithm to process the q-grams filtering in ReCAM memory. We also design a new data mapping strategy and a new verification algorithm, which enables computing the edit distances totally in ReRAM crossbars for energy saving. Experimental results show that ReSMA outperforms the CPU-, GPU-, FPGA-, ASIC-, and PIM-based solutions by 268.7×, 38.6×, 20.9×, 707.8×, and 14.7× in terms of performance, and 153.8×, 42.2×, 31.6×, 18.3×, and 5.3× in terms of energy-saving, respectively.

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.

Existing streaming graph processing systems typically adopt two phases of refinement and recomputation to ensure the correctness of the incremental computation. However, severe redundant memory accesses exist due to the unnecessary synchronization among independent edge updates. In this paper, we present GraphFly, a high-performance asynchronous streaming graph processing system based on dependency-flows. GraphFly features three key designs: 1) Dependency trees (D-trees), which helps quickly identify independent graph updates with low cost; 2) Dependency-flow based processing model, which exploits the space-time dependent co-scheduling for cache efficiency; 3) Specialized graph data layout, which further reduces memory accesses. We evaluate GraphFly, and the results show that GraphFly significantly outperforms state-of-the-art systems KickStarter and GraphBolt by 5.81× and 1.78× on average, respectively. Also, GraphFly scales well with different sizes of update batch and compute resources.

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 $.

Pruning deep neural networks (DNNs) can reduce the model size and thus save hardware resources of a resistive-random-access-memory (ReRAM)-based DNN accelerator. For the tightly coupled crossbar structure, existing ReRAM-based pruning techniques prune the weights of a DNN in a structured manner, thereby attaining low pruning ratios. This article presents a novel pruning technique, SegPrune, for pruning the weights of a DNN flexibly on crossbar architectures in order to maximize the pruning ratio achieved while preserving crossbar efficiency. We observe that different filters of a weight matrix share a large number of matrix subcolumns (in the same rows), called segments, that can be pruned by using the same segment shape in the sense that the weights at the same column position of these segments are either simultaneously accuracy-sensitive (and should thus be reserved) or simultaneously accuracy-insensitive (and can thus be pruned). Due to the bit-line exchangeability in the crossbar, segments with the same pruning shape can be assembled together into the same crossbar to ensure crossbar execution efficiency. We propose a projection-based shape voting algorithm to select suitable segment shapes to drive the weight pruning process. Accordingly, we also introduce a low-overhead data path that can be easily integrated into any existing ReRAM-based DNN accelerator, achieving a high pruning ratio and a high execution efficiency. Our evaluation shows that SegPrune outperforms the state-of-the-art, Hybrid-P, and FORMAS, by up to$14.6\times $and$3.6\times $in pruning ratio,$13.9\times $and$3.4\times $in inference speedup, and$12.5\times $and$3.1\times $in energy reduction, respectively, while achieving an even higher accuracy at the cost of less than 0.27% extra hardware area overhead.

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.

Resistive random access memory (ReRAM) addresses the high memory bandwidth requirement challenge of graph analytics by integrating the computing logic in the memory. Due to the matrix-structured crossbar architecture, existing ReRAM-based accelerators, when handling real-world graphs that often have the skewed degree distribution, suffer from the severe sparsity problem arising from zero fillings and activation nondeterminism, incurring substantial ineffectual computations.In this paper, we observe that the sparsity sources lie in the consecutive mapping of source and destination vertex index onto the wordline and bitline of a crossbar. Although exhaustive graph reordering improves the sparsity-induced inefficiency, its totally-random (source and destination) vertex mapping leads to expensive overheads. This work exploits the insight in a mid-point vertex mapping with the random wordlines and consecutive bitlines. A cost-effective preprocessing is proposed to exploit the insight by rapidly exploring the crossbar-fit vertex reorderings but ignores the sparsity arising from activation dynamics. We present a novel ReRAM-based graph analytics accelerator, named Spara, which can maximize the workload density of crossbars dynamically by using a tightly-coupled bank parallel architecture further proposed. Results on real-world and synthesized graphs show that Spara outperforms GraphR and GraphSAR by 8.21 × and 5.01 × in terms of performance, and by 8.97 × and 5.68× in terms of energy savings (on average), while incurring a reasonable (<; 9.98%) pre-processing overhead.

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×.

Time-evolving stream datasets exist ubiquitously in many real-world applications where their inherent hot keys often evolve over times. Nevertheless, few existing solutions can provide efficient load balancing on these time-evolving datasets while preserving low memory overhead. In this paper, we present a novel load balancing mechanism (named FISH), which can provide the efficient time-evolving stream processing at scale through recent hot keys identification and worker assignment. The key insight of this work is that the keys of time-evolving stream data can have a skewed distribution within the bounded distance of time interval. This enables to accurately identify the recent hot keys for the real-time load balancing within a bounded scope. We therefore propose an epoch-based recent hot key identification with specialized intra-epoch frequency counting (for maintaining low memory overhead) and inter-epoch hotness decaying (for suppressing superfluous computation). We also propose to heuristically infer the accurate information of remote workers through computation rather than communication for cost-efficient worker assignment. We have integrated our approach into Apache Storm. Our results on a cluster of 128 nodes for both synthetic and real-world stream datasets show that FISH significantly outperforms state-of-the-arts with the average and the 99th percentile latency reduction by 87.12 and 76.34 percent (versus W-Choices), and memory overhead reduction by 96.66 percent (versus Shuffle Grouping).