Approximate Nearest Neighbor Search (ANNS) plays a critical role in various disciplines spanning data mining and artificial intelligence, from information retrieval and computer vision to natural language processing and recommender systems. Data volumes have soared in recent years and the computational cost of an exhaustive exact nearest neighbor search is often prohibitive, necessitating the adoption of approximate techniques. The balanced performance and recall of graph-based approaches have more recently garnered significant attention in ANNS algorithms, however, only a few studies have explored harnessing the power of GPUs and multi-core processors despite the widespread use of massively parallel and general-purpose computing. To bridge this gap, we introduce a novel parallel computing hardware-based proximity graph and search algorithm. By leveraging the high-performance capabilities of modern hardware, our approach achieves remarkable efficiency gains. In particular, our method surpasses existing CPU and GPU-based methods in constructing the proximity graph, demonstrating higher throughput in both large- and small-batch searches while maintaining compatible accuracy. In graph construction time, our method, CAGRA, is 2.2-27x faster than HNSW, which is one of the CPU SOTA implementations. In large-batch query throughput in the 90 % to 95 % recall range, our method is 33–77 x faster than HNSW, and is 3.8-8.8 x faster than the SOTA implementations for GPU. For a single query, our method is 3.4-53x faster than HNSW at 95% recall.

The top-K problem is an essential part of many important applications in scientific computing, information retrieval, etc. As data volume grows rapidly, high-performance parallel top-K algorithms become critical. We propose two parallel top-K algorithms, AIR Top-K (Adaptive and Iteration-fused Radix Top-K) and GridSelect, for GPU. AIR Top-K employs an iteration-fused design to minimize CPU-GPU communication and device data access. Its adaptive strategy eliminates unnecessary device memory traffic automatically under various data distributions. GridSelect can process data on-the-fly. It adopts a shared queue and parallel two-step insertion to decrease the frequency of costly operations. We comprehensively compare 8 open-source GPU implementations and our methods for a wide range of problem sizes and data distributions. For batch sizes 1 and 100, respectively, AIR Top-K shows 1.98--21.48× and 8.01--574.78× speedup over previous radix top-K algorithm, and 1.44--7.34× and 1.38--31.91× speedup over state-of-the-art methods. GridSelect shows up to 882.29× speedup over its baseline.

Large-scale distributed training of deep neural networks results in models with worse generalization performance as a result of the increase in the effective mini-batch size. Previous approaches attempt to address this problem by varying the learning rate and batch size over epochs and layers, or ad hoc modifications of batch normalization. We propose scalable and practical natural gradient descent (SP-NGD), a principled approach for training models that allows them to attain similar generalization performance to models trained with first-order optimization methods, but with accelerated convergence. Furthermore, SP-NGD scales to large mini-batch sizes with a negligible computational overhead as compared to first-order methods. We evaluated SP-NGD on a benchmark task where highly optimized first-order methods are available as references: training a ResNet-50 model for image classification on ImageNet. We demonstrate convergence to a top-1 validation accuracy of 75.4 percent in 5.5 minutes using a mini-batch size of 32,768 with 1,024 GPUs, as well as an accuracy of 74.9 percent with an extremely large mini-batch size of 131,072 in 873 steps of SP-NGD.

Rich information matrices from first and second-order derivatives have many potential applications in both theoretical and practical problems in deep learning. However, computing these information matrices is extremely expensive and this enormous cost is currently limiting its application to important problems regarding generalization, hyperparameter tuning, and optimization of deep neural networks. One of the most challenging use cases of information matrices is their use as a preconditioner for the optimizers, since the information matrices need to be updated every step. In this work, we conduct a step-by-step performance analysis when computing the Fisher information matrix during training of ResNet-50 on ImageNet, and show that the overhead can be reduced to the same amount as the cost of performing a single SGD step. We also show that the resulting Fisher preconditioned optimizer can converge in 1/3 the number of epochs compared to SGD, while achieving the same Top-1 validation accuracy. This is the first work to achieve such accuracy with K-FAC while reducing the training time to match that of SGD.

Large-scale distributed training of deep neural networks suffers from the generalization gap caused by the increase in the effective mini-batch size. Previous approaches try to solve this problem by varying the learning rate and batch size over epochs and layers, or some ad hoc modification of the batch normalization. We propose an alternative approach using a second order optimization method that shows similar generalization capability to first order methods, but converges faster and can handle larger mini-batches. To test our method on a benchmark where highly optimized first order methods are available as references, we train ResNet-50 on ImageNet-1K. We converged to 75% Top-1 validation accuracy in 35 epochs for mini-batch sizes under 16,384, and achieved 75% even with a mini-batch size of 131,072, which took only 978 iterations.

Many supercomputers are shifting to architectures with low B (byte/s; memory transfer capability) per F (FLOPS capability) ratios. However, utilizing increased F is difficult for applications that inherently require large B. Targeting an implicit unstructured low-order finite-element analysis solver, which typically requires large B, we have developed a concentrated computation algorithm that yields significant performance improvements on low B/F supercomputers. 35.7% peak performance was achieved for a sparse matrix-vector multiplication kernel, and 15.6% peak performance was achieved for the whole solver on the second generation Xeon Phi-based Oakforest-PACS. This is 5.02 times faster than (and 6.90 times the peak performance of) the state-of-the-art solver (the SC14 Gordon Bell finalist solver). On Oakforest-PACS, the proposed solver was approximately 2.42 times faster than the state-of-the-art solver running on the K computer. The proposed approach has implications for systems and applications and is expected to have significant impact on various fields that use finite-element methods for nonlinear time evolution problems.

To enable overlap of computation and communication with non-blocking collective communication, it is required to progress asynchronously a sequence of communications. One of the naive implementation is to use a separate thread for communitation and run it in back of computation thread. However if the total number of threads is greater than the number of physical cores, context switches cause performance degradation of the computation thread. Simultaneous MultiThread (SMT) can be used to avoid this problem. However, commonly-used busy polling for incoming message detection also causes performance degradation of the computation thread. In this paper, we propose incoming message detection method using MONITOR/MWAIT instructions to reduce the performance degradation. Experiment results show that the performance of computation thread is improved largely compared to the busy polling method while latency is suppressed by a small increase.