More Like this

1. A Fast Algorithm for Aperiodic Linear Stencil Computation using Fast Fourier Transforms

   https://doi.org/10.1145/3606338  

   Ahmad, Zafar; Chowdhury, Rezaul; Das, Rathish; Ganapathi, Pramod; Gregory, Aaron; Zhu, Yimin (December 2023, ACM Transactions on Parallel Computing)

   Stencil computations are widely used to simulate the change of state of physical systems across a multidimensional grid over multiple timesteps. The state-of-the-art techniques in this area fall into three groups: cache-aware tiled looping algorithms, cache-oblivious divide-and-conquer trapezoidal algorithms, and Krylov subspace methods. In this article, we present two efficient parallel algorithms for performing linear stencil computations. Current direct solvers in this domain are computationally inefficient, and Krylov methods require manual labor and mathematical training. We solve these problems for linear stencils by using discrete Fourier transforms preconditioning on a Krylov method to achieve a direct solver that is both fast and general. Indeed, while all currently available algorithms for solving general linear stencils perform Θ(NT) work, whereNis the size of the spatial grid andTis the number of timesteps, our algorithms performo(NT) work. To the best of our knowledge, we give the first algorithms that use fast Fourier transforms to compute final grid data by evolving the initial data for many timesteps at once. Our algorithms handle both periodic and aperiodic boundary conditions and achieve polynomially better performance bounds (i.e., computational complexity and parallel runtime) than all other existing solutions. Initial experimental results show that implementations of our algorithms that evolve grids of roughly 10⁷cells for around 10⁵timesteps run orders of magnitude faster than state-of-the-art implementations for periodic stencil problems, and 1.3× to 8.5× faster for aperiodic stencil problems. Code Repository:https://github.com/TEAlab/FFTStencils 

   more » « less
2. Modeling optimization of stencil computations via domain-level properties

   https://doi.org/10.1145/3528425.3529103  

   Nesterenko, Brandon; Yi, Qing; Lin, Pei-Hung; Liao, Chunhua; Runnels, Brandon (April 2022, Thirteenth International Workshop on Programming Models and Applications for Multicores and Manycores)

   Stencil computations are widely used in the scientific simulation domain, and their performance is critical to the overall efficiency of many large-scale numerical applications. Many optimization techniques, most of them varying strategies of tiling and parallelization, exist to systematically enhance the efficiency of stencil computations. However, the effective- ness of these optimizations vary significantly depending on the wide range of properties demonstrated by the different stencils. This paper studies several well-known optimization strategies for stencils and presents a new approach to effectively guide the composition of these optimizations, by modeling their interactions with four domain-level proper- ties of stencils: spatial dimensionality, temporal order, order of accuracy, and directional dependence. When using our prediction model to guide optimizations for five real-world stencil applications, we were able to identify optimization strategies that outperformed two highly optimized stencil libraries by an average of 2.4x. 

   more » « less
3. Runtime Composition of Iterations for Fusing Loop-carried Sparse Dependence

   https://doi.org/10.1145/3581784.3607097  

   Cheshmi, Kazem; Strout, Michelle; Mehri Dehnavi, Maryam (November 2023, ACM)

   Dependence between iterations in sparse computations causes inefficient use of memory and computation resources. This paper proposes sparse fusion, a technique that generates efficient parallel code for the combination of two sparse matrix kernels, where at least one of the kernels has loop-carried dependencies. Existing implementations optimize individual sparse kernels separately. However, this approach leads to synchronization overheads and load imbalance due to the irregular dependence patterns of sparse kernels, as well as inefficient cache usage due to their irregular memory access patterns. Sparse fusion uses a novel inspection strategy and code transformation to generate parallel fused code optimized for data locality and load balance. Sparse fusion outperforms the best of unfused implementations using ParSy and MKL by an average of 4.2× and is faster than the best of fused implementations using existing scheduling algorithms, such as LBC, DAGP, and wavefront by an average of 4× for various kernel combinations. 

   more » « less
4. The FAST Algorithm for Submodular Maximization

   Breuer, Adam; Balkanski, Eric; Singer, Yaron (November 2020, Proceedings of Machine Learning Research)

   null (Ed.)

   In this paper we describe a new parallel algorithm called Fast Adaptive Sequencing Technique (FAST) for maximizing a monotone submodular function under a cardinality constraint k. This algorithm achieves the optimal 1-1/e approximation guarantee and is orders of magnitude faster than the state-of-the-art on a variety of experiments over real-world data sets. Following recent work by Balkanski & Singer (2018a), there has been a great deal of research on algorithms whose theoretical parallel runtime is exponentially faster than algorithms used for sub- modular maximization over the past 40 years. However, while these new algorithms are fast in terms of asymptotic worst-case guarantees, it is computationally infeasible to use them in practice even on small data sets because the number of rounds and queries they require depend on large constants and high-degree polynomials in terms of precision and confidence. The design principles behind the FAST algorithm we present here are a significant departure from those of recent theoretically fast algorithms. Rather than optimize for asymptotic theoretical guarantees, the design of FAST introduces several new techniques that achieve remarkable practical and theoretical parallel runtimes. The approximation guarantee obtained by FAST is arbitrarily close to 1-1/e, and its asymptotic parallel runtime (adaptivity) is O(log(n) log2(log k)) using O(n log log(k)) total queries. We show that FAST is orders of magnitude faster than any algorithm for submodular maximization we are aware of, including hyper-optimized parallel versions of state-of-the-art serial algorithms, by running experiments on large data sets. 

   more » « less
5. 3rd and 11th orders of accuracy of ‘linear’ and ‘quadratic’ elements for Poisson equation with irregular interfaces on Cartesian meshes

   https://doi.org/10.1108/HFF-09-2021-0596  

   Idesman, Alexander; Dey, Bikash (December 2021, International Journal of Numerical Methods for Heat & Fluid Flow)

   Purpose The purpose of this paper is as follows: to significantly reduce the computation time (by a factor of 1,000 and more) compared to known numerical techniques for real-world problems with complex interfaces; and to simplify the solution by using trivial unfitted Cartesian meshes (no need in complicated mesh generators for complex geometry). Design/methodology/approach This study extends the recently developed optimal local truncation error method (OLTEM) for the Poisson equation with constant coefficients to a much more general case of discontinuous coefficients that can be applied to domains with different material properties (e.g. different inclusions, multi-material structural components, etc.). This study develops OLTEM using compact 9-point and 25-point stencils that are similar to those for linear and quadratic finite elements. In contrast to finite elements and other known numerical techniques for interface problems with conformed and unfitted meshes, OLTEM with 9-point and 25-point stencils and unfitted Cartesian meshes provides the 3-rd and 11-th order of accuracy for irregular interfaces, respectively; i.e. a huge increase in accuracy by eight orders for the new 'quadratic' elements compared to known techniques at similar computational costs. There are no unknowns on interfaces between different materials; the structure of the global discrete system is the same for homogeneous and heterogeneous materials (the difference in the values of the stencil coefficients). The calculation of the unknown stencil coefficients is based on the minimization of the local truncation error of the stencil equations and yields the optimal order of accuracy of OLTEM at a given stencil width. The numerical results with irregular interfaces show that at the same number of degrees of freedom, OLTEM with the 9-points stencils is even more accurate than the 4-th order finite elements; OLTEM with the 25-points stencils is much more accurate than the 7-th order finite elements with much wider stencils and conformed meshes. Findings The significant increase in accuracy for OLTEM by one order for 'linear' elements and by 8 orders for 'quadratic' elements compared to that for known techniques. This will lead to a huge reduction in the computation time for the problems with complex irregular interfaces. The use of trivial unfitted Cartesian meshes significantly simplifies the solution and reduces the time for the data preparation (no need in complicated mesh generators for complex geometry). Originality/value It has been never seen in the literature such a huge increase in accuracy for the proposed technique compared to existing methods. Due to a high accuracy, the proposed technique will allow the direct solution of multiscale problems without the scale separation. 

   more » « less