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

Saliency detection for large-scale mesh decimation

COMPUTERS & GRAPHICS-UK 2023年 111卷 63-76页

作者： dos Anjos, Rafael Kuffner Roberts, Richard Andrew Allen, Benjamin Jorge, Joaquim Anjyo, Ken Univ Leeds Leeds England Victoria Univ Wellington CMIC Wellington New Zealand IMAG Grp Tokyo Japan INESC ID Lisbon Portugal

Highly complex and dense models of 3D objects have recently become indispensable in digital industries. Mesh decimation then plays a crucial role in the production pipeline to efficiently get visually convincing yet compact expressions of complex meshes. However, the current pipeline typically does not allow artists control the decimation process, just a simplification rate. Thus a preferred approach in production settings splits the process into a first pass of saliency detection highlighting areas of greater detail, and allowing artists to iterate until satisfied before simplifying the model. We propose a novel, efficient multi-scale method to compute mesh saliency at coarse and finer scales, based on fast mesh entropy of local surface measurements. Unlike previous approaches, we ensure a robust and straightforward calculation of mesh saliency even for densely tessellated models with millions of polygons. Moreover, we introduce a new adaptive subsampling and interpolation algorithm for saliency estimation. Our implementation achieves speedups of up to three orders of magnitude over prior approaches. Experimental results showcase its resilience to problem scenarios that efficiently scales up to process multi-million vertex meshes. Our evaluation with artists in the entertainment industry also demonstrates its applicability to real use-case scenarios. (c) 2023 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Geometric processing Mesh saliency Mesh decimation parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A Novel Compute-Efficient Tridiagonal Solver for Many-Core Architectures

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2023年第1期34卷 195-206页

作者： Liu, Kan Xue, Wei Tsinghua Univ Dept Comp Sci & Technol Beijing 100084 Peoples R China

The tridiagonal solver is an important kernel and is widely supported in mainstream numerical libraries. While parallel algorithms have been studied for many-core architectures, the performance of current algorithms and implementations is still hindered by input size sensitivity and cross-platform portability. In this paper, we propose a novel algorithm WM-pGE for the batched solution of diagonally dominant tridiagonal systems. The algorithm balances the key design objectives, including computation complexity, memory complexity, parallelism, and input size sensitivity, better than existing algorithms. Moreover, an elegant formulation is presented to show the implementation and cross-platform optimization without loss of efficiency and generality, by extracting the platform-dependent works into only four vector operators. The results from our batched tridiagonal experiments show that the proposed algorithm outperforms the prior work PCR-pThomas by 25% and 12% on NVIDIA Tesla V100 in single and double precision, respectively. On Intel KNL, our method achieves a 10% improvement in performance over PCR-pThomas in double precision.

关键词： Computer architecture Layout Sensitivity parallel algorithms Heuristic algorithms Graphics processing units Computational complexity parallel numerical algorithm Tridiagonal solver batched Tridiagonal solver many-core architectures

来源：评论

学校读者我要写书评

暂无评论

Efficient deterministic MapReduce algorithms for parallelizable problems

引用

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 2023年 177卷 28-38页

作者： Frei, Fabian Wada, Koichi Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland Hosei Univ Dept Appl Informat Chiyoda City Tokyo Japan

The MapReduce framework has firmly established itself as one of the most widely used parallel computing platforms for processing big data on tera-and peta-byte scale. Approaching it from a theoretical standpoint has proved to be notoriously difficult, however. In continuation of Goodrich et al.'s early efforts, explicitly espousing the goal of putting the MapReduce framework on footing equal to that of long-established models such as the PRAM, we investigate the obvious complexity question of how the computational power of MapReduce algorithms compares to that of combinational Boolean circuits commonly used for parallel computations. Relying on the standard MapReduce model introduced by Karloff et al. a decade ago, we develop an intricate simulation technique to show that any problem in NC (i.e., a problem solved by a logspace-uniform family of Boolean circuits of polynomial size and a depth polylogarithmic in the input size) can be solved by a MapReduce computation in O(T(n)/ log n) rounds, where n is the input size and T(n) is the depth of the witnessing circuit family. Thus, we are able to closely relate the standard, uniform NC hierarchy modeling parallel computations to the deterministic MapReduce hierarchy DM R C by proving that NCi+1 subset of DM R Ci for all i is an element of N. Besides the theoretical significance, this result has important applied aspects as well. In particular, we show for all problems in NC1-many practically relevant ones, such as integer multiplication and division, the parity function, and recognizing balanced strings of parentheses being among these-how to solve them in a constant number of deterministic MapReduce rounds.(c) 2023 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： MapReduce Circuit complexity parallel algorithms Nick?s class Complexity theory

来源：评论

学校读者我要写书评

暂无评论

A parallel Algorithm for Updating a Multi-objective Shortest Path in Large Dynamic Networks

A Parallel Algorithm for Updating a Multi-objective Shortest...

引用

2023 International Conference on High Performance Computing, Network, Storage, and Analysis, SC Workshops 2023

作者： Khanda, Arindam Shovan, S.M. Das, Sajal K. Missouri University of Science and Technology RollaMO United States

ISBN: (纸本)9798400707858

In dynamic networks, where continuous topological changes are prevalent, it becomes paramount to find and update different graph properties without the computational burden of recalculating from the ground up. However finding or updating a multi-objective shortest path (MOSP) in such a network is challenging, as it involves simultaneously optimizing multiple (conflicting) objectives. In light of this, our paper focuses on shortest path search and proposes parallel algorithms tailored specifically for large incremental graphs. We first present an efficient algorithm that updates the single-objective shortest path (SOSP) whenever a new set of edges are introduced. Leveraging this SOSP update algorithm, we also devise a novel heuristic approach to adaptively update a MOSP in large networks. Empirical evaluations on both real and synthetic incremental networks with shared memory implementations attest to the scalability and efficacy of the proposed algorithms. © 2023 ACM.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Adaptive Monte Carlo Uncertainty Forecasting for High Dimensional Nonlinear Dynamic Systems

引用

IEEE ACCESS 2023年 11卷 12119-12138页

作者： Vanfossen, Andrew W. Kumar, Mrinal Ohio State Univ Dept Mech & Aerosp Engn Columbus OH 43210 USA

The problem of uncertainty forecasting for complex dynamical systems in the framework of particle methods can be effectively addressed through the solution methodology known as adaptive Monte Carlo (AMC). Monte Carlo (MC) methods involve discretizing the initial probability density function (pdf) followed by forward propagation of particles through system dynamics to obtain an approximate particle representation of the evolved state uncertainty. While simple to implement, MC faces questions surrounding transient statistical consistency and rate of convergence. AMC (adopted here) addresses these issues on-the-fly using defined bounds on estimation accuracy alongside ensemble enrichment routines. This paper presents several improvements in the ensemble enrichment module of AMC. The AMC platform is re-engineered to include the novel implementation of a parallel global stochastic optimization routine in conjunction with additional module enhancements that work together towards the goal of efficient forecasting. Moreover, the efficacy of algorithms utilized within every submodule of AMC are detailed and improved upon under the framework of arithmetic minimization and parallelization. Each submodule is profiled to determine computational bottlenecks, optimized or replaced with more efficient methods such as simulated annealing (SA), and parallelized ultimately leading to a clock time reduction of 200 - 400% for benchmark entry descent and landing, Lorenz-96, and Lotka-Volterra models.

关键词： Uncertainty Numerical models Forecasting Mathematical models Biological system modeling Monte Carlo methods Data models Simulated annealing Adaptive Monte Carlo arithmetic minimization parallel algorithms nonconvex optimization simulated annealing uncertainty quantification

来源：评论

学校读者我要写书评

暂无评论

ezLDA: Efficient and Scalable LDA on GPUs

引用

IEEE ACCESS 2023年 11卷 100165-100179页

作者： Wang, Shilong Liu, Hang Gaihre, Anil Yu, Hengyong Univ Massachusetts Lowell Dept Elect & Comp Engn Lowell MA 01854 USA Stevens Inst Technol Dept Elect & Comp Engn Hoboken NJ 07030 USA

Latent Dirichlet Allocation (LDA) is a statistical approach for topic modeling with a wide range of applications. Attracted by the exceptional computing and memory throughput capabilities, this work introduces ezLDA which achieves efficient and scalable LDA training on GPUs with the following three contributions: First, ezLDA introduces three-branch sampling method which takes advantage of the convergence heterogeneity of various tokens to reduce the redundant sampling task. Second, to enable sparsity-aware format for both D and W on GPUs with fast sampling and updating, we introduce hybrid format for W along with corresponding token partition to T and inverted index designs. Third, we design a hierarchical workload balancing solution to address the extremely skewed workload imbalance problem on GPU and scale ezLDA across multiple GPUs. Taken together, ezLDA achieves superior performance over the state-of-the-art attempts with lower memory consumption.

关键词： Bayes method GPU high performance computin latent dirichlet allocation LDA parallel algorithms parallel programming machine learning unsupervised learning

来源：评论

学校读者我要写书评

暂无评论

Exploring Scalable parallelization for Edit Distance-Based Motif Search

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2023年第2期20卷 1587-1593页

作者： Qiu, Junqiao Ebnenasir, Ali City Univ Hong Kong Dept Comp Sci Kowloon Tong Hong Kong Peoples R China Michigan Technol Univ Dept Comp Sci Houghton MI 49931 USA

Motif Searching is an important problem that can reveal crucial information from biological data. Since the general motif searching is NP-hard and the volume of biological data is growing exponentially in recent years, there is a pressing need for developing time and space-efficient algorithms to find motifs. In this paper, we explore scalable parallelization for Edit Distance-Based Motif Search (EMS). We introduce two parallel designs, recursEMS which integrates the existing EMS solver into a parallel recursion tree running in multiple processes, and parEMS that presents a novel thread-based method which avoids the storage of redundant motif candidates. To make the parallel designs practical, we implement SPEMS, a Scalability-sensitive parallel solver for EMS. For any given biological dataset and search instance, SPEMS can provide an EMS parallelization towards the optimal performance, or a sub-optimal performance but being more space efficient. Evaluations on two real-world DNA dataset TRANSFAC and ChIP-seq show that SPEMS can obtain 10x geometric mean speedup over the state-of-the-art at the expense of no less than 74.7% memory overheads, or provide 2.2x geometric mean speedup with the possibility of consuming less memory, when running on a 48-core machine.

关键词： Biology Proteins parallel algorithms DNA Costs Time complexity Search problems Edit-distance motif search parallelism

来源：评论

学校读者我要写书评

暂无评论

A GPU-based real-time processing system for frequency division multiple-input-multiple-output radar

引用

IET RADAR SONAR AND NAVIGATION 2023年第10期17卷 1524-1537页

作者： Liu, Gaogao Bao, Yuqian Yue, Ning Wang, Sitian Wu, Hui Liu, Qiang Yang, Wenbo Xidian Univ Sch Elect & Engn Xian Peoples R China

Multiple-Input-Multiple-Output (MIMO) radar has the characteristic of multiple antenna channels, bringing on a big data volume for signal processing. Therefore, the trade-off between detection ability and computational efficiency is always considered. In this article, an optimisation system is proposed to enhance the real-time performance of frequency division MIMO radar without compromising accuracy. For the scenario of low-altitude small target detection, a signal processing acceleration method is proposed and a MIMO radar optimisation system based on graphics processing unit (GPU) architecture is built. The signal model of frequency division MIMO radar is first established, improving the classical signal processing flow efficiency from the perspective of reducing fast Fourier transform (FFT) times and windowing operation times. To achieve an advanced acceleration, the parallel architecture of ArrayFire-library in GPU is then employed. Distinct minimum parallel units are extracted by analysing the principle of digital beamforming (DBF), pulse compression, moving target detection (MTD), and constant false-alarm rate (CFAR) algorithms. And the corresponding parallel algorithms are designed to constitute a parallel acceleration system of frequency division MIMO. Simulation results indicate that the proposed method significantly improves the efficiency of MIMO system with a maximum acceleration ratio of 65 times, meeting the real-time processing requirements.

关键词： array signal processing frequency-domain analysis MIMO radar optimisation parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Scalable computational kernels for mortar finite element methods

引用

ENGINEERING WITH COMPUTERS 2023年第5期39卷 3691-3720页

作者： Mayr, Matthias Popp, Alexander Univ Bundeswehr Munchen Inst Math & Comp Based Simulat Werner-Heisenberg-Weg 39 D-85577 Neubiberg Germany Univ Bundeswehr Munchen Data Sci & Comp Lab Werner-Heisenberg-Weg 39 D-85577 Neubiberg Germany

Targeting simulations on parallel hardware architectures, this paper presents computational kernels for efficient computations in mortar finite element methods. Mortar methods enable a variationally consistent imposition of coupling conditions at high accuracy, but come with considerable numerical effort and cost for the evaluation of the mortar integrals to compute the coupling operators. In this paper, we identify bottlenecks in parallel data layout and domain decomposition that hinder an efficient evaluation of the mortar integrals. We then propose a set of computational strategies to restore optimal parallel communication and scalability for the core kernels devoted to the evaluation of mortar terms. We exemplarily study the proposed algorithmic components in the context of three-dimensional large-deformation contact mechanics, both for cases with fixed and dynamically varying interface topology, yet these concepts can naturally and easily be transferred to other mortar applications, e.g. classical meshtying problems. To restore parallel scalability, we employ overlapping domain decompositions of the interface discretization independent from the underlying volumes and then tackle parallel communication for the mortar evaluation by a geometrically motivated reduction of ghosting data. Using three-dimensional contact examples, we demonstrate strong and weak scalability of the proposed algorithms up to 480 parallel processes as well as study and discuss improvements in parallel communication related to mortar finite element methods. For the first time, dynamic load balancing is applied to mortar contact problems with evolving contact zones, such that the computational work is well balanced among all parallel processors independent of the current state of the simulation.

关键词： Mortar methods Contact mechanics Interface problems parallel algorithms Finite elements Domain decomposition

来源：评论

学校读者我要写书评

暂无评论

Evaluating the Effects of Modern Storage Devices on the Efficiency of parallel Machine Learning algorithms

引用

INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS 2020年第3-4期29卷

作者： Akritidis, Leonidas Fevgas, Athanasios Tsompanopoulou, Panagiota Bozanis, Panayiotis Univ Thessaly Data Structuring & Engn Lab Dept Elect & Comp Engn 37 Glavani & 28th October Str Volos 38221 Greece

Big Data analytics is presently one of the most emerging areas of research for both organizations and enterprises. The requirement for deployment of efficient machine learning algorithms over huge amounts of data led to the development of parallelization frameworks and of specialized libraries (like Mahout and MLlib) which implement the most important among these algorithms. Moreover, the recent advances in storage technology resulted in the introduction of high-performing devices, broadly known as Solid State Drives (SSDs). Compared to the traditional Hard Drives (HDDs), SSDs offer considerably higher performance and lower power consumption. Motivated by these appealing features and the growing necessity for efficient large-scale data processing, we compared the performance of several machine learning algorithms on MapReduce clusters whose nodes are equipped with HDDs, SSDs, and devices which implement the latest 3D XPoint technology. In particular, we evaluate several dataset preprocessing methods like vectorization and dimensionality reduction, two supervised classifiers, Naive Bayes and Linear Regression, and the popular k-Means clustering algorithm. We use an experimental cluster equipped with the three aforementioned storage devices under different configurations, and two large datasets, Wikipedia and HIGGS. The experiments showed that the benefits which derive from the usage of SSDs depend on the cluster setup and the nature of the applied algorithms.

关键词： Machine learning data mining MapReduce performance parallel algorithms flash memory SSDs 3D XPoint Distributed Storage

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：