Algorithm development for extreme-scale computing
Jiachang Sun, Chao Yang, Xiao‐Chuan Cai · National Science Review · 2016
The rapid advances of supercomputing and the growing needs of extreme-scale applications pose great challenges in the development of highly efficient and scalable parallel algorithms. In addition to the traditional homogeneous cluster system, some heterogeneous architectures with both multicore processors and many-core accelerators also offer tremendous advantages in terms of the computing capacity and the energy consumption. Several recently developed supercomputers in China, such as Dawning 6000, Sunway Blue Light, Tianhe-1A, and Tianhe-2, occupy top spots in the Top500 list [1]. To take the full advantage of the new computing hardware, developing suitable numerical algorithms and the corresponding software becomes an urgent task since most of the existing algorithm and software, including research and commercial codes, do not scale well on the newer machines. In addition to the investment of new hardware, the Chinese government has also sponsored algorithm and application development, via, for example, the National Natural Science Foundation of China [2], and the 863 and 973 programs of the Ministry of Science and Technology of China [3]. Significant progresses have been made in, e.g. several representative works before 2010 [4], such as GRAPES for weather and climate modeling [5], PRIS for petroleum reservoir simulation [6], GeoEast for seismic data processing [7], PHG for adaptive finite element computation [8], and JASMIN for scientific computing [9], and more recently, the code for aerodynamics computations of flows around a complete aircraft [10], the code for molecular dynamics simulations of crystalline silicon [11], and the code for gas-kinetic modeling of hypersonic flows around a reentry spacecraft [12]. However, most application codes can only run with a small number of processors because of the lack of scalable algorithms and software. Efforts have been made, for example, in the Supercomputing Centre, Chinese Academy of Sciences, for promoting research on algorithms that can scale to O(100, 000) cores. It is still a long way to meet the application needs at the extreme scale on the algorithmic front. The challenges come from many aspects, such as complex geometry, multiphysics, multiscale, and high dimensionality. For example, in global atmospheric simulations at the meso- or eddy scale, it is required to use horizontal resolutions of a few hundred meters over the globe, leading to a system consisting of thousands of billions of unknowns. The computation would take unacceptably long time if the algorithm is not highly scalable or not highly efficient. It is generally believed in the computational science and engineering community that, roughly speaking, algorithm contributes an equal factor, if not more, as the hardware does toward the improvement of the performance of the computation. The important roles of good algorithms include not only accelerating the applications on certain hardware platforms, but also providing valuable information that helps the design and advances of new supercomputers. For example, the molecular dynamics simulation [11] on large-scale GPU clusters has promoted the rapid development of CPU–GPU heterogeneous systems in China. While the High-Performance LINPACK benchmark, used to rank supercomputers on the Top500 List for years, is losing relevance to the performance of realistic applications, some new benchmarks such as Graph 500, High-Performance Conjugate Gradients, and High-Performance Geometric Multigrid, among others, are drawing more attentions from algorithms developers and hardware manufacturers. An indisputable fact is that there is a large gap between the expectations from an algorithm developer and the design space considered by a hardware architect, due partially to the power consumption limitation and the fact that the chips are not designed solely for scientific and engineering applications. Some factors that limit the algorithm development include the amount of fast memory such as register and cache, the capability of data movement between different memory units, and the uncertainties of hardware and system performance. An important feature of extreme-scale computing is that the communication time often dominates the total simulation time for many applications except those embarrassingly parallel problems. Therefore, the complexity of an algorithm, which is traditionally measured by the number of floating-point operations, needs to be redefined to, somehow, include the cost of data movement. And the focus of the design of algorithms should be shifted from computation to communication. Also, fault-tolerant algorithms will become necessary to counter the system uncertainties, and global synchronization needs to be reduced as much as possible. Next we discuss a few specific classes of algorithms. Parallel algorithms for the numerical solution of partial differential equations (PDEs) are frequently applied in many large-scale scientific and engineering computations. Although explicit methods are inexpensive to apply, implicit methods may offer better opportunities at the extreme scale because of the relaxed stability restrictions [13]. Preconditioned iterative solvers, either linear or nonlinear, are the key to the success of implicit methods. For problems with high nonlinearities, some nonlinear preconditioning techniques may become useful [14]. To increase the parallelism, parallel efficiency and robustness, algorithms such as parallel-in-time methods, asynchronized methods, and randomized methods are of great interests. Sometimes it is beneficial if the solver and preconditioner are not designed solely from the level of the algebraic system, but from some aspects of the continuous PDE and the physics from which the PDE is derived, e.g. [15,16]. Generally speaking, sparse matrix techniques have many advantages as compared to the dense matrix or matrix-free methods. However, the indirect memory access and the relatively low computational density may substantially degrade the performance of the computations, especially on many-core accelerators [17]. This situation is getting worse as the memory bandwidth of newer architecture grows in a much slower pace than the computing capacity. Ideas to relax the sparsity requirement or to replace it with a matrix-free kernel are gaining more attention. The dependence on indirect addressing of some matrix-based algorithms, such as approximate/incomplete factorizations, can be hopefully removed if certain grid information is effectively used. For sparse matrix computations, certain modifications such as the inclusion of certain information of the continuous PDE and the application of high-order methods with higher computational density may provide great opportunity to achieve high performance and efficiency. To improve the accuracy and lower the cost of computation, algorithms based on adaptive mesh refinement for both structured and unstructured grids have been extensively studied [18,19]. However, sometimes for realistic applications, the cost to obtain an optimal mesh is usually comparable or higher than solving the PDE itself. Issues such as indirect memory access, load imbalance, and global synchronization are often obstacles to achieving high performance. To successfully apply adaptive and/or unstructured meshes at the extreme scale, some tradeoffs between the accuracy requirements and the parallel efficiency have to be appropriately balanced. This is a highly nontrivial task for real-world applications. Other interesting problems, for example, eigenvalue problems for the stability analysis of structures, electronic structure calculations in material sciences, numerical solution of integral equations in astrophysics, N-body calculation in molecular dynamics, and optimization problems constrained by PDEs also demand extreme-scale computing systems. They all have their own distinct characteristics different from numerical PDEs, but there are also intrinsic connections among them, e.g. [20]. There is no doubt that algorithm is not the only factor that enables the efficient use of extreme-scale computers. A new generation of algorithm and software is necessary and the focus should be shifted from floating-point operation centered to communication centered, and features such as fault tolerance and asynchronous are highly desirable. A collaborative eco-system including hardware designers, software and algorithm developers needs to be established and maintained. A new generation of computational scientists is badly needed for this exciting field of extreme-scale computing that offers enormous potential for new engineering advances and scientific discoveries.