检索结果-内蒙古大学图书馆

Dual Domain Decomposition Method for High-Resolution 3D Simulation of Groundwater Flow and Transport

WATER 2024年第13期16卷 1864页

作者： Deng, Hao Li, Jiaxin Huang, Jixian Zou, Yanhong Liu, Yu Chen, Yuxiang Zheng, Yang Mao, Xiancheng Cent South Univ Sch Geosci & Info Phys Changsha 410083 Peoples R China Cent South Univ Key Lab Metallogen Predict Nonferrous Met & Geol E Minist Educ Changsha 410083 Peoples R China

The high-resolution 3D groundwater flow and transport simulation problem requires massive discrete linear systems to be solved, leading to significant computational time and memory requirements. The domain decomposition method is a promising technique that facilitates the parallelization of problems with minimal communication overhead by dividing the computation domain into multiple subdomains. However, directly utilizing a domain decomposition scheme to solve massive linear systems becomes impractical due to the bottleneck in algebraic operations required to coordinate the results of subdomains. In this paper, we propose a two-level domain decomposition method, named dual-domain decomposition, to efficiently solve the massive discrete linear systems in high-resolution 3D groundwater simulations. The first level of domain decomposition partitions the linear system problem into independent linear sub-problems across multiple subdomains, enabling parallel solutions with significantly reduced complexity. The second level introduces a domain decomposition preconditioner to solve the linear system, known as the Schur system, used to coordinate results from subdomains across their boundaries. This additional level of decomposition parallelizes the preconditioning of the Schur system, addressing the bottleneck of the Schur system solution while improving its convergence rates. The dual-domain decomposition method facilitates the partition and distribution of the computation to be solved into independent finely grained computational subdomains, substantially reducing both computational and memory complexity. We demonstrate the scalability of our proposed method through its application to a high-resolution 3D simulation of chromium contaminant transport in groundwater. Our results indicate that our method outperforms both the vanilla domain decomposition method and the algebraic multigrid preconditioned method in terms of runtime, achieving up to 8.617x and 5.515x speedups,

关键词： groundwater simulation domain decomposition parallel algorithm fast solution 3D numeric modeling

来源：评论

学校读者我要写书评

暂无评论

A 3D TLM code for the study of the ELF electromagnetic wave propagation in the Earth's atmosphere

引用

COMPUTERS & GEOSCIENCES 2024年 183卷

作者： Salinas, Alfonso Porti, Jorge Navarro, Enrique A. Toledo-Redondo, Sergio Albert, Inmaculada Castilla, Aida Univ Granada Res Ctr Informat & Commun Technol CITIC UGR Dept Electromagnetism & Matter Phys Granada Spain Univ Granada Res Ctr Informat & Commun Technol CITIC UGR Dept Appl Phys Granada Spain Univ Valencia IRTIC Inst ETSE Burjassot Spain Univ Murcia Dept Electromagnetism & Elect Murcia Spain

The interest in the study of electromagnetic propagation through planetary atmospheres is briefly discussed. Special attention is devoted to extremely-low-frequency fields in the Earth's atmosphere for its global nature and possible applications to climate monitoring studies among others. In the Earth's case, the system can be considered as a spherical electromagnetic shell resonator in which two concentric and large conducting spheres with a radius around 6300 km are separated by a very small distance of around 100 km, the atmosphere height. A numerical solution using the Transmission Line Method is proposed. The classical spherical-coordinate description is easy to use, however, the important difference in the dimensions along the three coordinate directions causes high numerical dispersion in the results. A Cartesian scheme with equal node size for all directions is used to reduce this undesired dispersion. A pre-processing stage is the key point introduced to lessen the resulting high demand of memory and time calculation and make the solution feasible. A parallelized Fortran code together with pre- and post-processing Python programs to ease the user interface are provided with this work. Details on the Fortran code and the Python modules are included both in the paper and the source codes to allow the use and modifications by other researchers interested in electromagnetic propagation through planetary atmospheres. The program allows calculation of the time evolution of the electromagnetic field at any point in the atmosphere. It includes the possibility of considering multiple time-dependent sources and different homogeneous and inhomogeneous conductivity profiles to model different situations. Profiles to study day-night asymmetries or locally perturbed profiles which have been attributed to earthquakes in the literature are implemented, for instance.

关键词： Atmosphere electrodynamics TLM method Schumann resonances Full 3D numerical model parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

A new hybrid GPU-CPU sparse LDLT factorization algorithm with GPU and CPU factorizing concurrently

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2024年 79卷

作者： Liu, Yunmou Du, Hui Li, Zhuogen Chen, Pu Peking Univ Coll Engn Dept Mech & Engn Sci Beijing 100871 Peoples R China Peking Univ State Key Lab Turbulence & Complex Syst Beijing 100871 Peoples R China Peking Univ NanChang Innovat Inst Nanchang 330008 Peoples R China

This paper proposes a new task assignment scheme for sparse LDLT factorization on a hybrid GPU-CPU platform, and correspondingly an efficient supernodal algorithm, GPU Node and CPU Pipelining (GNCP). GNCP assigns a large number of weakly coupled tasks to GPU and CPU respectively so that GPU and CPU can execute different factorization tasks concurrently without explicit synchronization, which has not been achieved by previous researches. More precisely, based on the number of CPU threads, the global memory of GPU as well the size of the matrix, we introduce the concept of the truncation level in the partition tree built by the multi-level graph partitioning. The sum of FLOP associated with decoupled nodes in the truncation level accounts for about 65% of the whole computations in tested numerical examples. GNCP assigns the factorization tasks of each node in the truncation level to GPU. The data of each node in the truncation level are copied to the global memory of GPU and factorized entirely and independently by GPU one-by-one. Once factorization of any node in the truncation level has been completed, the cross-factorizations of this node to its ancestors and the following related operations are decoupled from other GPU tasks. These tasks are assigned to CPU threads with a reentrant pipelining strategy, accounting for about 35% of the whole calculations. Using this novel design, CPU and GPU are working concurrently and a large part of factorization is performed in overlapped time. Numerical tests for matrices from SuiteSparse matrix collection show higher performance than the well-known hybrid GPU-CPU solver CHOLMOD.

关键词： Sparse LDL T factorization GPU algorithm Hybrid GPU-CPU algorithm parallel algorithm Partition tree

来源：评论

学校读者我要写书评

暂无评论

HyLAC: Hybrid linear assignment solver in CUDA

引用

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 2024年 187卷

作者： Kawtikwar, Samiran Nagi, Rakesh Univ Illinois Ind & Enterprise Syst Engn Champaign IL 61820 USA Singapore Univ Technol & Design Engn Syst & Design Singapore Singapore

The Linear Assignment Problem (LAP) is a fundamental combinatorial optimization problem with a wide range of applications. Over the years, significant progress has been made in developing efficient algorithms to solve the LAP, particularly in the realm of high-performance computing, leading to remarkable reductions in computation time. In recent years, hardware improvements in General Purpose Graphics Processing Units (GPGPUs) have shown promise in meeting the ever-increasing compute bandwidth requirements. This has attracted researchers to develop GPU-accelerated algorithms to solve the LAP. Recent work in the GPU domain has uncovered parallelism available in the problem structure to achieve significant performance improvements. However, each solution presented so far targets either sparse or dense instances of the problem and has some scope for improvement. The Hungarian algorithm is one of the most famous approaches to solving the LAP in polynomial time. Hungarian algorithm has classical O(N-4) (Munkres') and tree based O(N-3) (Lawler's) implementations. It is well established that the Munkres' implementation is faster for sparse LAP instances while the Lawler's implementation is faster for dense instances. In this work, we blend the GPU implementations of Munkres' and Lawler's to develop a Hybrid GPU-accelerated solver for LAP that switches between the two implementations based on available sparsity. Also, we improve the existing GPU implementations to reduce memory contention, minimize CPU-GPU synchronizations, and coalesced memory access. The resulting solver (HyLAC) works faster than existing CPU/GPU LAP solvers for sparse as well as dense problem instances. HyLAC achieves a speedup of up to 6.14x over existing state-of-the-art GPU implementation when run on the same hardware. We also develop an implementation to solve a list of small LAPs (tiled LAP), which is particularly useful in the optimization domain. This tiled LAP solver performs 22.59x faster than t

关键词： Hungarian algorithm Linear assignment problem GPU-accelerated graph algorithms High-performance computing parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient Sorting of Homomorphic Encrypted Data With k-Way Sorting Network

引用

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY 2021年 16卷 4389-4404页

作者： Hong, Seungwan Kim, Seunghong Choi, Jiheon Lee, Younho Cheon, Jung Hee Seoul Natl Univ Dept Math Sci Seoul 08826 South Korea Sogang Univ Dept Math Seoul 04107 South Korea SeoulTech ITM Div Dept Ind Engn Seoul 01811 South Korea Seoul Natl Univ CryptoLab Seoul 08826 South Korea

In this study, we propose an efficient sorting method for encrypted data using fully homomorphic encryption (FHE). The proposed method extends the existing 2-way sorting method by applying the k-way sorting network for any prime k to reduce the depth in terms of comparison operation from O(log(2)(2) n) to O(k log(k)(2) n), thereby improving performance for k slightly larger than 2, such as k = 5. We apply this method to approximate FHE which is widely used due to its efficiency of homomorphic arithmetic operations. In order to build up the k-way sorting network, the k-sorter, which sorts k-numbers with a minimal comparison depth, is used as a building block. The approximate homomorphic comparison, which is the only type of comparison working on approximate HIE, cannot he used for the construction of the k-sorter as it is because the result of the comparison is not binary, unlike the comparison in conventional bit-wise FHEs. To overcome this problem, we propose an efficient k-sorter construction utilizing the features of approximate homomorphic comparison. Also, we propose an efficient construction of a k-way sorting network using cryptographic SIMD operations. To use the proposed method most efficiently, we propose an estimation formula that finds the appropriate k that is expected to reduce the total time cost when the parameters of the approximating comparisons and the performance of the operations provided by the approximate FHE are given. We also show the implementation results of the proposed method, and it shows that sorting 5(6) = 15625 data using 5-way sorting network can be about 23.3% faster than sorting 2(14) = 16384 data using 2-way.

关键词： Approximate homomorphic encryption sorting network parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Convergence theorems for solving a system of pseudomonotone variational inequalities using Bregman distance in Banach spaces

引用

BOLLETTINO DELLA UNIONE MATEMATICA ITALIANA 2022年第4期15卷 561-588页

作者： Jolaoso, Lateef Olakunle Aphane, Maggie Raji, Musiliu Tayo Osinuga, Idowu Ademola Olajuwon, Bakai Ishola Sefako Makgatho Hlth Sci Univ Dept Math & Appl Math POB 94 ZA-0204 Pretoria South Africa Fed Univ Agr Dept Math Abeokuta Ogun Nigeria

In this paper, we present two new parallel Bregman projection algorithms for finding a common solution of a system of pseudomonotone variational inequality problems in a real reflexive Banach space. The first algorithm combines a parallel Bregman subgradient extragradient method with the Halpern iterative method for approximating a common solution of variational inequalities in reflexive Banach spaces. The second algorithm involves a parallel Bregman subgradient extragradient method, Halpern iterative method and a line search procedure which aims to avoid the condition of finding prior estimate of the Lipschitz constant of each cost operator. Two strong convergence results were proved under standard assumptions imposed on the cost operators and control sequences. Finally, we provide some numerical experiments to illustrate the behaviour of the sequences generated by the proposed algorithms.

关键词： parallel algorithm Variational inequalities Extragradient method Pseudomonotone Bregman distance Banach space

来源：评论

学校读者我要写书评

暂无评论

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

引用

JOURNAL OF THE ACM 2021年第3期68卷 1–41页

作者： Boroujeni, Mahdi Ehsani, Soheil Ghodsi, Mohammad Hajiaghayi, Mohammadtaghi Seddighin, Saeed Sharif Univ Technol Azadi St Tehran Iran Univ Maryland College Pk MD 20742 USA Toyota Technol Inst Chicago Chicago IL USA Inst Res Fundamental Sci IPM Tehran Iran

The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is "one of the biggest unsolved problems in the field of combinatorial pattern matching" [37]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an O(n(1.810)) quantum algorithm that approximates the edit distance within a factor of 3. We further extend this result to an O(n(1.708)) quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to metric estimation and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of 1 + epsilon, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.

关键词： Edit distance approximation algorithm subquadratic time algorithm quantum algorithm parallel algorithm MapReduce

来源：评论

学校读者我要写书评

暂无评论

A parallel Symmetric Successive Overrelaxation Method for OVERFLOW

A Parallel Symmetric Successive Overrelaxation Method for OV...

引用

AIAA Aviation Forum and Exposition

作者： Derlaga, Joseph M. Jackson, Charles W. Buning, Pieter G. NASA Langley Res Ctr Computat AeroSci Branch 15 Langley BlvdMS 128 Hampton VA 23681 USA

ISBN: (数字)9781624106101

ISBN: (纸本)9781624106101

The block Jacobi symmetric successive overrelaxation (SSOR) algorithm has been reformulated as a parallelized algorithm for the OVERFLOWstructured, overset grid, computational fluid dynamics flow solver. Simple changes to the flow solver required to implement the algorithm are discussed. A series of test cases are presented that demonstrate how the addition of implicit overset boundaries has improved the robustness and nonlinear convergence characteristics of the flow solver.

关键词： Computational Fluid Dynamics Freestream Conditions Turbulence Models Convection parallel algorithm NACA 0015 Eddy Viscosity Fuselages Boeing

来源：评论

学校读者我要写书评

暂无评论

High-Performance Truss Analytics in Arkouda 29

High-Performance Truss Analytics in Arkouda

引用

29th Annual IEEE International Conference on High Performance Computing, Data, and Analytics (HiPC)

作者： Du, Zhihui Patchett, Joseph Rodriguez, Oliver Alvarado Li, Fuhuan Bader, David A. New Jersey Inst Technol Dept Data Sci Newark NJ 07102 USA

ISBN: (纸本)9781665494236

In graph analytics, a truss is a cohesive subgraph based on the number of triangles supporting each edge. It is widely used for community detection applications such as social networks and security analysis, and the performance of truss analytics highly depends on its triangle counting method. This paper proposes a novel triangle counting kernel named Minimum Search (MS). Minimum Search can select two smaller adjacency lists out of three and uses fine-grained parallelism to improve the performance of triangle counting. Then, two basic algorithms, MS-based triangle counting, and MS-based support updating are developed. Based on the novel triangle counting kernel and the two basic algorithms above, three fundamental parallel truss analytics algorithms are designed and implemented to enable different kinds of graph truss analysis. These truss algorithms include an optimized K-Truss algorithm, a Max-Truss algorithm, and a Truss Decomposition algorithm. Moreover, all proposed algorithms have been implemented in the parallel language Chapel and integrated into an open-source framework, Arkouda. Through Arkouda, data scientists can efficiently conduct graph analysis through an easy-to-use Python interface and handle large-scale graph data in powerful back-end computing resources. Experimental results show that the proposed methods can significantly improve the performance of truss analysis on real-world graphs compared with the existing and widely adopted list intersection-based method. The implemented code is publicly available from GitHub (https://***/Bears-R-Us/arkoudanjit).

关键词： K-Truss Triangle Counting Graph Analytics parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

A tile-fusion method for accelerating Winograd convolutions

引用

NEUROCOMPUTING 2021年 460卷 9-19页

作者： Ji, Zeyu Zhang, Xingjun Wei, Zheng Li, Jingbo Wei, Jia Xi An Jiao Tong Univ Sch Comp Sci & Technol Xian 710049 Peoples R China

Compared with fast convolution methods such as im2col and the fast Fourier transform, Winograd-based convolution, which has been widely applied to accelerate convolutional neural networks (CNNs), can provide high performance with smaller filters. Although there are several reported studies on the algorithmic optimization of CNNs, most of them are targeted at hardware architectures. The existing implementations of the Winograd method perform well below what one would expect, due to the fact that the tile size of Winograd-based convolution is usually empirical and the features of each convolution layer are ignored. This study aims to fill this gap and focuses on the efficient implementation of Winograd based convolution in the CNN model. Specifically, we discuss the causes of poor performance, calculate the coefficient of computation complexity model and demonstrate a speedup in the inference process using an elaborate tile-fusion method, which derives the optimal tile size for each convolution layer in a CNN model. Compared with the representative existing implementations of CuDNN with a 4 x 4 tile, Arm Compute Library with a 6 x 6 tile, and NNPACK with an 8 x 8 tile, the results show significant performance improvements on of up to 1.89 x , 1.29 x and 1.17 x , respectively. (c) 2021 Published by Elsevier B.V.

关键词： Fast convolution Winograd algorithm parallel algorithm Convolutional neural network Tile size Zero padding

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：