Brief Announcement: Faster Stencil Computations using Gaussian Approximations

被引：3

作者：

Ahmad, Zafar ^{[1
]}

Chowdhury, Rezaul ^{[1
]}

Das, Rathish ^{[2
]}

Ganapathi, Pramod ^{[1
]}

Gregory, Aaron ^{[1
]}

Zhu, Yimin ^{[1
]}

机构：

[1] SUNY Stony Brook, Stony Brook, NY 11794 USA

[2] Univ Waterloo, Waterloo, ON N2L 3G1, Canada

来源：

PROCEEDINGS OF THE 34TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, SPAA 2022 | 2022年

基金：

加拿大自然科学与工程研究理事会;

关键词：

Linear Stencil; Gaussian Approximation; Fast Gauss Transform; FINITE-DIFFERENCE;

D O I：

10.1145/3490148.3538558

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Stencil computations are widely used to simulate the change of state of physical systems. The current best algorithm for performing aperiodic linear stencil computations on a d(>= 1)-dimensional grid of size N for T timesteps does (Theta) over tilde (TN1-1/d + N log N) work. We introduce novel techniques based on random walks and Gaussian approximations for an asymptotic improvement of this work bound for a class of linear stencils. We also improve the span (i.e., parallel running time on an unbounded number of processors) asymptotically from the current state of the art.

引用

页码：291 / 293

页数：3

共 21 条

[1]

Ahmad Zafar, 2021, SPAA '21: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, P8, DOI 10.1145/3409964.3461803

[2] FOURST: A code generator for FFT-based fast stencil computations [J].

Ahmad, Zafar ;

Javanmard, Mohammad Mahdi ;

Croisdale, Gregory ;

Gregory, Aaron ;

Ganapathi, Pramod ;

Pouchet, Louis-Noel ;

Chowdhury, Rezaul .

2022 IEEE INTERNATIONAL SYMPOSIUM ON PERFORMANCE ANALYSIS OF SYSTEMS AND SOFTWARE (ISPASS 2022), 2022, :99-108

[3]

Barth Timothy J., 2013, Highorder Methods for Computational Physics, V9

[4] A new error estimate of the fast Gauss transform [J].

Baxter, BJC ;

Roussos, G .

SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2002, 24 (01) :257-259

[5] Optimal Parallel Algorithms in the Binary-Forking Model [J].

Blelloch, Guy E. ;

Fineman, Jeremy T. ;

Gu, Yan ;

Sun, Yihan .

PROCEEDINGS OF THE 32ND ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA '20), 2020, :89-102

[6]

Bondhugula U., 2007, PLUTO PRACTICAL FULL

[7]

Cormen T. H., 2009, INTRO ALGORITHMS

[8]

Elgammal A, 2001, PROC CVPR IEEE, P563

[9]

Frigo M., 2005, P 19 ANN INT C SUP, V1, P361, DOI DOI 10.1145/1088149.1088197

[10] THE FAST GAUSS TRANSFORM [J].

GREENGARD, L ;

STRAIN, J .

SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1991, 12 (01) :79-94

← 1 2 3 →