In order to support the real-time interaction with LLMs and the instant search or the instant recommendation on social media, it becomes an imminent problem to build a k-NN graph or an indexing graph for the massive number of vectorized multimedia data. In such scenarios, the scale of the data or the scale of the graph may exceed the processing capacity of a single machine. This paper aims to address the graph construction problem of such scale via efficient graph merge. For the graph construction on a single node, two generic and highly parallelizable algorithms, namely Two-way Merge and Multi-way Merge are proposed to merge subgraphs into one. For the graph construction across multiple nodes, a multi-node procedure based on Two-way Merge is presented. The procedure makes it feasible to construct a large-scale k-NN graph/indexing graph on either a single node or multiple nodes when the data size exceeds the memory capacity of one node. Extensive experiments are conducted on both large-scale k-NN graph and indexing graph construction. For the k-NN graph construction, the large-scale and high-quality k-NN graphs are constructed by graph merge in parallel. Typically, a billion-scale k-NN graph can be built in approximately 17h when only three nodes are employed. For the indexing graph construction, similar NN search performance as the original indexing graph is achieved with the merged indexing graphs while requiring much less time of construction.

Nearest neighbor search (NN search) plays a fundamental role in many disciplines. According to recent studies, graph-based search methods show superior performance over other types of methods. In order to accommodate the high dimensionality as well as the growing data-scale, the disk-based NN search in which the index graph and the full-precision vectors are kept in SSD has become a promising direction. This paper optimizes the disk-based NN search from three perspectives. Firstly, an eXtended Neighborhood Graph (XN-Graph) structure is proposed. In contrast to the existing index graphs, the out-edges of the graph neighborhood are collected from much wider coverage of the data space. It therefore reduces the number of hops during NN search, which in turn reduces the search latency. Additionally, a dataset partitioning method called Boundary-adaptive Balanced Partition is proposed to facilitate the graph construction in cases where the system cannot handle large datasets in a single round. Moreover, an efficient hybrid NN search method called In-Memory First Search is proposed. Compared to the existing methods, it considerably reduces the CPU idle times. With the support of XN-Graph, it shows 1.5-3 times lower search latency than SOTA methods. On billion-scale datasets, its QPS is still above 4000 when Recall@10 is as high as 0.9.

As a classick-NN graph construction method, NN-Descent has been adopted in various applications for its simplicity, genericness, and efficiency. However, its memory consumption is high due to the employment of two extra supporting graph structures. In this paper, a novelk-NN graph construction method is proposed. Similar to NN-Descent, thek-NN graph is constructed by doing cross-matching continuously on the sampled neighbors on each neighborhood. Whereas different from NN-Descent, the cross-matching is undertaken directly on thek-NN graph under construction. It makes the extra graph structures adopted to support the cross-matching no longer necessary. Moreover, no synchronization between different threads is needed within one iteration. The high-quality graph is constructed at the high-speed efficiency and considerably better memory efficiency over NN-Descent on both the multi-thread CPU and the GPU.

As a new algorithm of graph embedding, graph neural networks (GNNs) have been widely used in many fields. However, GNN computing has the characteristics of both sparse graph processing and dense neural network, which make it difficult to be deployed efficiently on the existing graph processing accelerators or neural network accelerators. Recently, some GNN accelerators have been proposed, but the following challenges have not been fully solved: 1) the minibatch GNN inference scenario has the potential of software and hardware co-design, which can bring 30% computation amount reduction, and this is not well utilized. Besides, the cost of message flow graph construction is large and may account for more than 50% of the total delay; 2) the feature aggregation has a large amount of data access and relatively small amount of computation, which leads to low on-chip data reuse, only 10% of dense computing; and 3) without the optimization of sparse computing units, simple memory bank and cross bar architecture can easily lead to bank access conflict and load imbalance, reducing the utilization of computing units to less than 60%. In order to solve the above problems, we propose a algorithm-hardware co-design scheme to accelerate GNN inference, which includes three technologies: 1) a reuse-aware sampling method is proposed for minibatch inference scenarios, which reduces 30% of the calculation and improves the on-chip reusability of local data; 2) through the nodewise parallelism-aware quantization, the features and weights are quantized to integers with eight or four bits, which reduces the amount of memory access by at least four times; and 3) an accelerator supporting the above technologies is designed and evaluated, and different operations are supported by the sampling-inference integration architecture. The multibank on-chip memory pool is designed to support data reuse, and edge stream reordering is used to reduce data access conflicts, improving the utilization of computing units by$1.5\times $. Combined with the above technologies, the experiments show that our design achieves$9.2\times $speedup and$29\times $energy efficiency improvement compared with the Deep Graph Library framework running on servers equipped with CPU and GPU.

Frame refreshes, that are used to retain frame images from frame buffers for display subsystems in mobile devices, waste energy and memory bandwidth. In this paper, we propose an intelligent frame refresh mechanism to reduce redundant frame refreshes and useless data accesses to frame buffers, which bridges the semantic gap between frame buffers and frame refreshes, and exploits the knowledge of frame buffers to guide frame refreshes. Based on this mechanism, we introduce two detailed schemes to optimize refreshes by utilizing different information. The flipping-aware frame refresh scheme uses the frame buffer switching operations to detect frame image updates and triggers useful refreshes. The row-level frame refresh scheme supports to refresh only modified rows instead of the whole frame, under the guidance of pixel status information of frame buffers. Our evaluation results show that our proposed mechanism can reduce memory requests by nearly 50% and memory power consumption up to 30%, compared to conventional fixed frame refresh mechanism.