Breadth-first search (BFS) is a fundamental building block of various high-performance computing applications beyond graph analysis and also known as a benchmark problem in the Graph 500 list. The increasing volume of global data demands efficient distributed BFS, which, however, is hindered by the high communication costs of exchanging vertex data between compute nodes. To address this challenge, this paper introduces four techniques: (i) forest pruning, which reduces the number of vertices by eliminating those unnecessary for the search; (ii) group reordering and (iii) multilevel bitmap compression, which decrease the memory footprint of graph data, thereby enabling fewer nodes to manage larger graphs; and (iv) adaptive parameter tuning, which quickly optimizes the hyperparameters of the BFS algorithm. In the evaluation using 152,064 nodes of the supercomputer Fugaku, our implementation achieved 198 tera-traversed edges per second, doubling the performance reported in the latest Graph500-related study on Fugaku.

Graph embedding is the process of obtaining a vector representation of graph nodes. The representation obtained by graph embedding is highly versatile. It can be used for various tasks, such as recommendation and clustering tasks. However, there are only a few methods that incorporate attributes indicating node characteristics, such as user gender, age, or product category, into graph embedding. Therefore, we hypothesize that nodes with the same attribute are often connected to the same node. Consequently, we propose two methods for graph embedding, parallel and serial, that use metric learning to reflect attribute data in node features. The proposed method can be applied to any graph embedding and metric learning method, and thus can also be applied to many new methods yet to be developed. Numerical experimental results show that the proposed method using node attributes is superior to the existing methods in both AUROC and accuracy.

Deep learning models are vulnerable to adversarial examples, and adversarial attacks used to generate such examples have attracted considerable research interest. Although existing methods based on the steepest descent have achieved high attack success rates, ill-conditioned problems occasionally reduce their performance. To address this limitation, we utilize the conjugate gradient (CG) method, which is effective for this type of problem, and propose a novel attack algorithm inspired by the CG method, named the Auto Conjugate Gradient (ACG) attack. The results of large-scale evaluation experiments conducted on the latest robust models show that, for most models, ACG was able to find more adversarial examples with fewer iterations than the existing SOTA algorithm Auto-PGD (APGD). We investigated the difference in search performance between ACG and APGD in terms of diversification and intensification, and define a measure called Diversity Index (DI) to quantify the degree of diversity. From the analysis of the diversity using this index, we show that the more diverse search of the proposed method remarkably improves its attack success rate.

Lattice problems are a class of optimization problems that are notably hard. There are no classical or quantum algorithms known to solve these problems efficiently. Their hardness has made lattices a major cryptographic primitive for post-quantum cryptography. Several different approaches have been used for lattice problems with different computational profiles; some suffer from super-exponential time, and others require exponential space. This motivated us to develop a novel lattice problem solver, CMAP-LAP, based on the clever coordination of different algorithms that run massively in parallel. With our flexible framework, heterogeneous modules run asynchronously in parallel on a large-scale distributed system while exchanging information, which drastically boosts the overall performance. We also implement full checkpoint-and-restart functionality, which is vital to high-dimensional lattice problems. CMAP-LAP facilitates the implementation of large-scale parallel strategies for lattice problems since all the functions are designed to be customizable and abstract. Through numerical experiments with up to 103,680 cores, we evaluated the performance and stability of our system and demonstrated its high capability for future massive-scale experiments.

There is increasing demand for the high-speed processing of large-scale graphs in various fields. However, such graph processing requires irregular calculations, making it difficult to scale performance on large-scale distributed memory systems. Against this background, Graph500, a competition for evaluating the performance of large-scale graph processing, has been held. We developed breadth-first search (BFS), which is one of the benchmark kernels used in Graph500, and took the top spot a total of 10 times using the K computer. In this paper, we tune BFS performance and evaluate it using the supercomputer Fugaku, which is the successor to the K computer. The results of evaluating BFS for a large-scale graph composed of about 1.1 trillion vertices and 17.6 trillion edges using 92,160 nodes of Fugaku indicate that Fugaku has 2.27 times the performance of the K computer. Fugaku took the top spot on Graph500 in June 2020.

Studies of acquiring appropriate continuous representations of a discrete objects such as graph and knowledge based data have been conducted by many researches in the field of machine learning. In this paper, we introduce Nested SubSpace arrangement (NSS arrangement), a comprehensive framework for representation learning. We show that existing embedding techniques can be regarded as a member of NSS arrangement. Based on the concept of the NSS arrangement, we implemented Disk-ANChor ARrangement (DANCAR), a representation learning method specializing to reproduce general graphs. Numerical experiments have shown that DANCAR has successfully embedded WordNet in ${\mathbb R}^{20}$ with the F1 score of 0.993 in the reconstruction task. DANCAR is also suitable for visualization to understand the characteristics of graph.

Lattice-based cryptography has received attention as a next-generation encryption technique, because it is believed to be secure against attacks by classical and quantum computers. Its essential security depends on the hardness of solving the shortest vector problem (SVP). In the cryptography, to determine security levels, it is becoming significantly more important to estimate the hardness of the SVP by high-performance computing. In this study, we develop the world’s first distributed and asynchronous parallel SVP solver, the MAssively Parallel solver for SVP (MAP-SVP). It can parallelize algorithms for solving the SVP by applying the Ubiquity Generator framework, which is a generic framework for branch-and-bound algorithms. The MAP-SVP is suitable for massive-scale parallelization, owing to its small memory footprint, low communication overhead, and rapid checkpoint and restart mechanisms. We demonstrate its performance and scalability of the MAP-SVP by using up to 100,032 cores to solve instances of the Darmstadt SVP Challenge.

Abstract The studies of browsing behavior have gained increasing attention in web analysis for providing better service. Most of the conventional approaches focus on simple indices such as average dwell time and conversion rate. These indices make similar evaluations to websites even if their features are significantly different. Moreover, such statistical indices are not sensitive to the dynamics of users’ interests. In this paper, we propose a new framework for measuring a website’s attractiveness that takes into account both the distribution and dynamics of users’ interests. Within the framework, we define a new index for the website, called Attractiveness Factor, which evaluates the degree of users’ attention. It consists of three procedures: First, we capture the transition of users’ interests during browsing by solving a nonnegative matrix factorization and constrained network flow problems. To accommodate multiple types of interests of a user, we applied a soft clustering as opposed to a hard clustering to model attributes of users and websites. Second, for each website, the feature of each cluster is obtained by fitting the dwell time distribution with Weibull distribution. Finally, we calculate Attractiveness Factor of a website by applying the results of clustering and fitting. Attractiveness Factor depends on the distribution of the dwell time of users interested in the website, which reflects the change of interest of users. Numerical experiments with real web access data of Yahoo Japan News are conducted by solving extremely large-scale optimization problems. They show that Attractiveness Factor captures more exceptional information about browsing behavior more effectively than well-used indices. Attractive factors give low ratings to category pages; however, it can assign high ratings to websites that attract many people, such as hot topic news about the 2018 FIFA World Cup, Japan’s new imperial era’ REIWA,’ and North Korea—the United States Hanoi Summit. Moreover, we demonstrate that Attractiveness Factor can detect the tendency of users’ attention to each website at a given time interval of the day.

One of the most critical problems in bike-sharing services is a bicycle repositioning problem, which is how service providers must relocate their bicycles to maintain the quality of service. In this paper, we propose an end-to-end approach for the bike repositioning problem, which realizes the operator-feasible repositioning plan with cooperation among multiple trucks. Our proposed algorithm consists of three procedures. First, we predict the number of rented and returned bicycles at each station with a deep learning based on the bicycle usage information. Second, we determine the optimal number of bicycles to satisfy the availability of each station by solving an integer optimization problem. Finally, we solve the vehicle routing problem formulated as another integer optimization problem. Based on our algorithm, service operators can actually perform a relocation task based with a reference to the truck capacity, routes, and the number of bicycles to be loaded and unloaded. We demonstrate the applicability of our algorithm in the real world through numerical experiments on the real bicycle data of a Japanese company.

Cyber-Physical Systems (CPSs) are attracting significant attention from a number of industries, including social infrastructure, manufacturing, retail, among others. We can easily gather big datasets of people and transportation movements by utilizing camera and sensor technologies, and create new industrial applications by optimizing and simulating social mobility in the cyberspace. In this paper, we develop the system which automatically performs a series of processes, including object detection, multiple object tracking, and mobility optimization. The mobility of humans and objects is one of the essential components in the real world. Therefore, our system can be widely applied to various application fields. Our major contributions to this paper are remarkable performance improvement of multiple object tracking and building the new mobility optimization engine. In the former, we improve the multiple object tracker using K-Shortest Paths (KSP), which achieves significant data reduction and acceleration by specifying and deleting unnecessary nodes. Numerical experiments show that our proposed tracker is over three times faster than the original KSP tracker while keeping the accuracy. We formulate the mobility optimization problem as the SATisfiability problem (SAT) and the Integer Programming problem (IP) in the latter. Numerical experiments demonstrate that the total transit time can be reduced from 30 s to 10 s. We discuss the characteristics of solutions obtained by the two formulations. We can finally select the appropriate optimization method according to the constraints of calculation time and accuracy for real applications.

In this paper, we propose a practical approach to evacuation planning by utilizing network flow and deep learning algorithms. In recent years, large amounts of data are rapidly being stored in the cloud system, and effective data utilization for solving real-world problems is required more than ever. Hierarchical Data Analysis and Optimization System (HDAOS) enables us to select appropriate algorithms according to the degree of difficulty in solving problems and a given time for the decision-making process, and such selection helps address real-world problems. In the field of emergency evacuation planning, however, the Lexicographically Quickest Flow (LQF) algorithm has an extremely long computation time on a large-scale network, and is therefore not a practical solution. For Osaka city, which is the second-largest city in Japan, we must solve the maximum flow problems on a large-scale network with over 8.3M nodes and 32.8M arcs for obtaining an optimal plan. Consequently, we can feed back nothing to make an evacuation plan. To solve the problem, we utilize the optimal solution as training data of a deep Convolutional Neural Network (CNN). We train a CNN by using the results of the LQF algorithm in normal time, and in emergencies predict the evacuation completion time (ECT) immediately by the well-learned CNN. Our approach provides almost precise ECT, achieving an average regression error of about 2%. We provide several techniques for combining LQF with CNN and addressing numerous movements as CNN's input, which has rarely been considered in previous studies. Hodge decomposition also demonstrates that LQF is efficient from the standpoint of the total distance traveled by all evacuees, which reinforces the validity of the method of utilizing the LQF algorithm for deep learning.

There are many large-scale graphs in real world such as Web graphs and social graphs. The interest in large-scale graph analysis is growing in recent years. Breadth-First Search (BFS) is one of the most fundamental graph algorithms used as a component of many graph algorithms. Our new method for distributed parallel BFS can compute BFS for one trillion vertices graph within half a second, using large supercomputers such as the K-Computer. By the use of our proposed algorithm, the K-Computer was ranked 1st in Graph500 using all the 82,944 nodes available on June and November 2015 and June 2016 38,621.4 GTEPS. Based on the hybrid BFS algorithm by Beamer (Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing Workshops and PhD Forum, IPDPSW ’13, IEEE Computer Society, Washington, 2013 ), we devise sets of optimizations for scaling to extreme number of nodes, including a new efficient graph data structure and several optimization techniques such as vertex reordering and load balancing. Our performance evaluation on K-Computer shows that our new BFS is 3.19 times faster on 30,720 nodes than the base version using the previously known best techniques.

As the power consumption of HPC systems will be a primary constraint for exascale computing, a main objective in HPC communities is recently becoming to maximize power efficiency (i.e., performance per watt) rather than performance. Although programmers have spent a considerable effort to improve performance by tuning HPC programs at a code level, tunings for improving power efficiency is now required. In this work, we select two representative HPC programs (Graph500 and SDPARA) and evaluate how traditional code-level performance tunings applied to these programs affect power efficiency. We also investigate the impacts of the tunings on power efficiency at various operating frequencies of CPUs and/or GPUs. The results show that the tunings significantly improve power efficiency, and different types of tunings exhibit different trends in power efficiency by varying CPU frequency. Finally, the scalability and power efficiency of state-of-the-art Graph500 implementations are explored on both a single-node platform and a 960-node supercomputer. With their high scalability, they achieve 27.43 MTEPS/Watt with 129.76 GTEPS on the single-node system and 4.39 MTEPS/Watt with 1,085.24 GTEPS on the supercomputer.

Breadth-First Search(BFS) is one of the most fundamental graph algorithms used as a component of many graph algorithms. Our new method for distributed parallel BFS can compute BFS for one trillion vertices graph within half a second, using large supercomputers such as the K-Computer. By the use of our proposed algorithm, the K-Computer was ranked 1st in Graph500 using all the 82,944 nodes available on June and November 2015 and June 2016 38,621.4 GTEPS. Based on the hybrid-BFS algorithm by Beamer[3], we devise sets of optimizations for scaling to extreme number of nodes, including a new efficient graph data structure and optimization techniques such as vertex reordering and load balancing. Performance evaluation on the K shows our new BFS is 3.19 times faster on 30,720 nodes than the base version using the previously-known best techniques.

We introduce a memory efficient implementation for the NVM-based Hybrid BFS algorithm that merges redundant data structures to a single graph data structure, while offloading infrequent accessed graph data on NVMs based on the detailed analysis of access patterns, and demonstrate extremely fast BFS execution for large-scale unstructured graphs whose size exceed the capacity of DRAM on the machine. Experimental results of Kronecker graphs compliant to the Graph500 benchmark on a 2-way INTEL Xeon E5-2690 machine with 256 GB of DRAM show that our proposed implementation can achieve 4.14 GTEPS for a SCALE31 graph problem with 231vertices and 235edges, whose size is 4 times larger than the size of graphs that the machine can accommodate only using DRAM with only 14.99 % performance degradation. We also show that the power efficiency of our proposed implementation achieves 11.8 MTEPS/W. Based on the implementation, we have achieved the 3rd and 4th position of the Green Graph500 list (2014 June) in the Big Data category.

The semi definite programming (SDP) problem is one of the central problems in mathematical optimization. The primal-dual interior-point method (PDIPM) is one of the most powerful algorithms for solving SDP problems, and many research groups have employed it for developing software packages. However, two well-known major bottlenecks, i.e., the generation of the Schur complement matrix (SCM) and its Cholesky factorization, exist in the algorithmic framework of the PDIPM. We have developed a new version of the semi definite programming algorithm parallel version (SDPARA), which is a parallel implementation on multiple CPUs and GPUs for solving extremely large-scale SDP problems with over a million constraints. SDPARA can automatically extract the unique characteristics from an SDP problem and identify the bottleneck. When the generation of the SCM becomes a bottleneck, SDPARA can attain high scalability using a large quantity of CPU cores and some processor affinity and memory interleaving techniques. SDPARA can also perform parallel Cholesky factorization using thousands of GPUs and techniques for overlapping computation and communication if an SDP problem has over two million constraints and Cholesky factorization constitutes a bottleneck. We demonstrate that SDPARA is a high-performance general solver for SDPs in various application fields through numerical experiments conducted on the TSUBAME 2.5 supercomputer, and we solved the largest SDP problem (which has over 2.33 million constraints), thereby creating a new world record. Our implementation also achieved 1.713 PFlops in double precision for large-scale Cholesky factorization using 2,720 CPUs and 4,080 GPUs.

The breadth-first search (BFS) is one of the most important kernels in graph theory. The Graph500 benchmark measures the performance of any supercomputer performing a BFS in terms of traversed edges per second (TEPS). Previous studies have proposed hybrid approaches that combine a well-known top-down algorithm and an efficient bottom-up algorithm for large frontiers. This reduces some unnecessary searching of outgoing edges in the BFS traversal of a small-world graph, such as a Kronecker graph. In this paper, we describe a highly efficient BFS using column-wise partitioning of the adjacency list while carefully considering the non-uniform memory access (NUMA) architecture. We explicitly manage the way in which each working thread accesses a partial adjacency list in local memory during BFS traversal. Our implementation has achieved a processing rate of 11.15 billion edges per second on a 4-way Intel Xeon E5-4640 system for a scale-26 problem of a Kronecker graph with 226vertices and 230edges. Not all of the speedup techniques in this paper are limited to the NUMA architecture system. With our winning Green Graph500 submission of June 2013, we achieved 64.12 GTEPS per kilowatt hour on an ASUS Pad TF700T with an NVIDIA Tegra 3 mobile processor.

Semidefinite programming (SDP) is one of the most important problems among optimization problems at present. It is relevant to a wide range of fields such as combinatorial optimization, structural optimization, control theory, economics, quantum chemistry, sensor network location and data mining. The capability to solve extremely large-scale SDP problems will have a significant effect on the current and future applications of SDP. In 1995, Fujisawa et al. started the SDPA(Semidefinite programming algorithm) Project aimed at solving large-scale SDP problems with high numerical stability and accuracy. SDPA is one of the main codes to solve general SDPs. SDPARA is a parallel version of SDPA on multiple processors with distributed memory, and it replaces two major bottleneck parts (the generation of the Schur complement matrix and its Cholesky factorization) of SDPA by their parallel implementation. In particular, it has been successfully applied to combinatorial optimization and truss topology optimization. The new version of SDPARA (7.5.0-G) on a large-scale supercomputer called TSUBAME 2.0 at the Tokyo Institute of Technology has successfully been used to solve the largest SDP problem (which has over 1.48 million constraints), and created a new world record. Our implementation has also achieved 533 TFlops in double precision for large-scale Cholesky factorization using 2,720 CPUs and 4,080 GPUs.

A SemiDefinite Programming (SDP) problem is one of the most central problems in mathematical optimization. SDP provides an effective computation framework for many research fields. Some applications, however, require solving a large-scale SDP whose size exceeds the capacity of a single processor both in terms of computation time and available memory. SDPARA (SemiDefinite Programming Algorithm paRAllel package) [Yamashita et al. 2003b] was designed to solve such large-scale SDPs. Its parallel performance is outstanding for general SDPs in most cases. However, the parallel implementation is less successful for some sparse SDPs obtained from applications such as Polynomial Optimization Problems (POPs) or Sensor Network Localization (SNL) problems, since this version of SDPARA cannot directly handle sparse Schur Complement Matrices (SCMs). In this article we improve SDPARA by focusing on the sparsity of the SCM and we propose a new parallel implementation using the formula-cost-based distribution along with a replacement of the dense Cholesky factorization. We verify numerically that these features are key to solving SDPs with sparse SCMs more quickly on parallel computing systems. The performance is further enhanced by multithreading and the new SDPARA attains considerable scalability in general. It also finds solutions for extremely large-scale SDPs arising from POPs which cannot be obtained by other solvers.

This paper presents CAILS, an experimental Computer Assisted Iconic Language System that deals with three specific areas in communication: cross-linguistic, visual/spatial concept representation and visual educational techniques.