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

Beyond worst-case analysis Observed low depth for a P-complete problem 13

Beyond worst-case analysis Observed low depth for a P-comple...

13th International Workshop on Programming Models and Applications for Multicores and Manycores (PMAM) part of PPoPP Conference

作者： Vishkin, Uzi Univ Maryland College Pk MD 20742 USA

ISBN: (纸本)9781450393393

The performance of a simple parallel algorithm for 3CNF Horn-SAT is observed. The algorithm requires linear work. The algorithm also exhibits low parallel time ("depth") for central Horn-SAT formulae benchmarks. The work optimality of the algorithm, its observed low depth, P-completeness of the problem and algorithm-specific modeling put together demonstrate a way for going beyond worst-case for parallel algorithms. The questioning of the near exclusivity of the worst-case analysis mode in typical algorithms courses has received considerable attention recently for a broad range of algorithms. The current paper suggests a new line, unique to parallel algorithms, for questioning the worst-case analysis mode, dramatically undermining the broad perception that a P-completeness result is nothing short of "a nightmare for parallel processing", as phrased in an authoritative textbook.

关键词： parallel algorithms P-Completeness Beyond worst-case

来源：评论

学校读者我要写书评

暂无评论

Large Scale Image Classification Using GPU-based Genetic Programming 22

Large Scale Image Classification Using GPU-based Genetic Pro...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Zeng, Peng Lensen, Andrew Sun, Yanan Sichuan Univ Coll Comp Sci Chengdu Peoples R China Victoria Univ Wellington Sch Engn & Comp Sci Wellington New Zealand

ISBN: (纸本)9781450392686

Genetic programming (GP) has been applied to image classification and achieved promising results. However, most GP-based image classification methods are only applied to small-scale image datasets because of the limits of high computation cost. Efficient acceleration technology is needed when extending GP-based image classification methods to large-scale datasets. Considering that fitness evaluation is the most time-consuming phase of the GP evolution process and is a highly parallelized process, this paper proposes a CPU multi-processing and GPU parallel approach to perform the process, and thus effectively accelerate GP for image classification. Through various experiments, the results show that the highly parallelized approach can significantly accelerate GP-based image classification without performance degradation. The training time of GP-based image classification method is reduced from several weeks to tens of hours, enabling it to be run on large-scale image datasets.

关键词： genetic programming image classification parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A Scalable parallel Algorithm for 3-D Magnetotelluric Finite Element Modeling in Anisotropic Media

引用

IEEE TRANSACTIONS ON GEOSCIENCE AND REMOTE SENSING 2022年 60卷

作者： Zhu, Xiaoxiong Liu, Jie Cui, Yian Gong, Chunye Natl Univ Def Technol Sci & Technol Parallel & Distributed Proc Lab Lab Software Engn Complex Syst Changsha 410073 Peoples R China Cent South Univ Sch Geosci & Info Phys Changsha 410083 Peoples R China

3-D magnetotelluric (MT) forward modeling has always been faced with the problems of high memory requirements and long computing time. In this article, we design a scalable parallel algorithm for 3-D MT finite element modeling in anisotropic media. The parallel algorithm is based on the distributed mesh storage, including multiple parallel granularities, and is implemented through multiple tools. Message-passing interface (MPI) is used to exploit process parallelisms for subdomains, frequencies, and solving equations. Thread parallelisms for merge sorting, element analysis, matrix assembly, and imposing Dirichlet boundary conditions are developed by Open Multi-Processing (OpenMP). We validate the algorithm through several model simulations and study the effects of topography and conductivity anisotropy on apparent resistivities and phase responses. Scalability tests are performed on the Tianhe-2 supercomputer to analyze the parallel performance of different parallel granularities. Three parallel direct solvers Supernodal LU (SUPERLU), MUltifrontal Massively parallel sparse direct Solver (MUMPS), and parallel Sparse matriX package (PASTIX) are compared in solving sparse systems of equations. As a result, reasonable parallel parameters are suggested for practical applications. The developed parallel algorithm is proven to be efficient and scalable.

关键词： Finite element analysis Mathematical model parallel algorithms Memory management Sparse matrices Conductivity Computational modeling Conductivity anisotropy finite element method (FEM) magnetotelluric (MT) parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Performance evaluation of ECC scalar multiplication using parallel modular algorithms on mobile devices

Performance evaluation of ECC scalar multiplication using pa...

引用

Annual Conference on Privacy, Security and Trust, PST

作者： Tiago Vanderlei de Arruda Yeda Regina Venturini Tiemi Christine Sakata Computer Department Federal University of Sao Carlos Sorocaba Sao Paulo Brazil

Mobile devices, such as smartphones, allow people around the world to access a huge amount of online applications anywhere and anytime. Elliptic Curve Cryptography (ECC) algorithm can be used in mobile devices to trust the access to these applications. Scalar multiplication is the main and most expensive operation in ECC and its cost is directly related to the size of the key used. It is composed of a lot of modular arithmetic operations (addition, subtraction, squaring, multiplication and inversion), defined by the coordinate system used. Using the short Weierstrass Jacobian coordinate system, the modular multiplication and squaring are the most costly operations performed in our experiments. In this paper we analyze the performance of scalar multiplication using a variety of sequential and parallel modular multiplication algorithms with standardized NIST curves. To predict the timings for highorder curves, it is used a 1536-bit pairing-friendly curve available on RELIC. Experiments were performed on a SabreLite IMX6Quad board with a quad-core ARM cortex A9 (ARMv7 architecture) processor, which allows the analysis of these scalar multiplications on a mobile device architecture. Results show that Bipartite 2th timings were faster than the sequential ones for 1536-bit curves. Bipartite timings were strictly close to the best sequential timing for 521 bits, indicating that for a not too much longer key, parallel algorithms' timings are capable to overcome the sequential ones.

关键词： Timing Elliptic curve cryptography Algorithm design and analysis Elliptic curves Mobile handsets parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A Theoretical Bound Which Improves the Performance of Compilation-Based Multi-Agent Path Finding

引用

IEEE ACCESS 2025年 13卷 86133-86143页

作者： Lopez, Rodrigo Asin-Acha, Roberto Baier, Jorge A. Pontificia Univ Catolica Chile Dept Comp Sci Santiago 8320165 Chile Univ Tecn Federico Santa Maria Dept Informat Santiago 8940897 Chile Inst Milenio Fundamentos Datos Santiago 8320000 Chile

A well-known approach to optimally solving Multi-Agent Path Finding (MAPF) is by compilation to Boolean Satisfiability or Answer Set Programming. Such compilation-based approaches to MAPF are superior to others on dense, relatively small instances. During solving, the underlying solver is invoked multiple times, each with an encoding of the same instance for a different makespan. The runtime of the last solver invocation, whose input is the instance encoded with a theoretical upper bound of the makespan of the optimal solution, is critical to performance. This paper proposes a new theoretical upper bound for such a last invocation, which we prove is correct. Unlike the previously known bound, given a MAPF instance, our bound requires computing a semi-relaxed solution, which is the union of cost-optimal solutions for partitions of such an instance. The computation of our new bound requires optimally solving partitions, which requires more computational resources than those needed for computing the bound currently used by state-of-the-art solvers. We propose a recursive parallel approach that, we call ReBo, which despite additional overhead in upper bound computation, obtains substantially better overall results by exploiting the new bound. ReBo uses a heuristic to select an appropriate partition for bound computation, which does not guarantee that the solution returned is optimal. However, in our benchmarks, composed of 2,890 problems over warehouses and random instances, ReBo never finds a suboptimal solution. In addition, we found that the new bound is significantly tighter than the previously known, on average, 21.2% smaller than the previous bound. This allows us to generate encodings that are around 33.45% smaller, allowing ReBo to solve 4.9% more instances than a state-of-the-art solver in our benchmark set.

关键词： Upper bound Encoding Costs Mathematical models Runtime Benchmark testing Answer set programming Scalability Visualization Video games parallel algorithms multi-agent systems path planning answer set programming

来源：评论

学校读者我要写书评

暂无评论

Fully-adaptive Model for Broadcasting with Universal Lists 24

Fully-adaptive Model for Broadcasting with Universal Lists

引用

24th International Symposium on Symbolic and Numeric algorithms for Scientific Computing (SYNASC)

作者： Gholami, Saber Harutyunyan, Hovhannes A. Concordia Univ Dept Comp Sci & Software Engn Montreal PQ Canada

ISBN: (纸本)9781665465458

In classical broadcasting, a piece of information must be transmitted to all entities of a network as quickly as possible, starting from a particular member. Since this problem has an enormous number of applications and is proven to be NP-Hard, several models are defined in the literature while trying to simulate real-world situations and relax several constraints. A well-known branch of broadcasting utilizes a universal list throughout the process. That is, once a vertex is informed, it must follow its corresponding list, regardless of the originator and the neighbor it received the message. The problem of broadcasting with universal lists could be categorized into two sub-models: non-adaptive and adaptive. In the latter model, a sender will skip the vertices on its list from which it has received the message, while those vertices will not be skipped in the first model. In this study, we will present another sub-model called fully adaptive. Not only does this model benefit from a significantly better space complexity compared to the classical model, but, as will be proved, it is faster than the two other sub-models. Since the suggested model fits real-world network architectures, we will design optimal broadcast algorithms for well-known interconnection networks such as trees, grids, and cube-connected cycles under the fully-adaptive model. We also present a tight upper bound for tori under the same model.

关键词： parallel algorithms graph theory broadcasting universal lists fully-adaptive

来源：评论

学校读者我要写书评

暂无评论

A unified consensus-based parallel ADMM algorithm for high-dimensional regression with combined regularizations

arXiv

引用

arXiv 2023年

作者： Wu, Xiaofei Zhang, Zhimin Cui, Zhenyu College of Mathematics and Statistics Chongqing University Chongqing401331 China School of Business Stevens Institute of Technology HobokenNJ07030 United States

The parallel alternating direction method of multipliers (ADMM) algorithm is widely recognized for its effectiveness in handling large-scale datasets stored in a distributed manner, making it a popular choice for solving statistical learning models. However, there is currently limited research on parallel algorithms specifically designed for high-dimensional regression with combined (composite) regularization terms. These terms, such as elastic-net, sparse group lasso, sparse fused lasso, and their nonconvex variants, have gained significant attention in various fields due to their ability to incorporate prior information and promote sparsity within specific groups or fused variables. The scarcity of parallel algorithms for combined regularizations can be attributed to the inherent nonsmoothness and complexity of these terms, as well as the absence of closed-form solutions for certain proximal operators associated with them. In this paper, we propose a unified constrained optimization formulation based on the consensus problem for these types of convex and nonconvex regression problems and derive the corresponding parallel ADMM algorithms. Furthermore, we prove that the proposed algorithm not only has global convergence but also exhibits linear convergence rate. Extensive simulation experiments, along with a financial example, serve to demonstrate the reliability, stability, and scalability of our algorithm. The R package for implementing the proposed algorithms can be obtained at https://***/xfwu1016/CPADMM. Copyright © 2023, The Authors. All rights reserved.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

GPU-Accelerated High-Bandwidth Radar Centroiding

GPU-Accelerated High-Bandwidth Radar Centroiding

引用

IEEE High Performance Extreme Computing Virtual Conference (HPEC)

作者： Brigada, David J. Merfeld, Maximilian Warner, Kara MIT Lincoln Lab 244 Wood St Lexington MA 02421 USA

ISBN: (数字)9781665497862

ISBN: (纸本)9781665497862

Radar signal processing is a computationally intensive task, especially for high-bandwidth systems. Traditionally, such systems have relied on the interleaving of processing on multiple nodes of large compute clusters to achieve the necessary throughput. Development in general-purpose GPU computing has led to a massive increase in the computational power available to highly parallel tasks. Most parts of the radar signal processing pipeline are well suited for such a task. This paper describes an algorithm for centroiding, a key part of the search radar pipeline that has not yet been demonstrated on a GPU. With this centroiding algorithm, the entire high-data-rate portion of the processing pipeline can be run on the GPU, yielding a speedup factor of approximately 40. The primary benefit of this approach is a massive reduction in data copying from the GPU to the CPU-a factor of over 1200 in this case-alleviating the main barrier to GPU-based radar processing systems.

关键词： Blob detection data structures parallel algorithms radar

来源：评论

学校读者我要写书评

暂无评论

An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model

引用

OPERATIONS RESEARCH 2021年第5期70卷 iii-vi, 2597-3033, C2-C3页

作者： Balkanski, Eric Rubinstein, Aviad Singer, Yaron Columbia Univ Dept Ind Engn & Operat Res New York NY 10027 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA Harvard Univ Sch Engn & Appl Sci Cambridge MA 02138 USA

In this paper, we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Despite the burst in work on submodular maximization in the adaptive complexity model, the fundamental problem of maximizing a monotone submodular function under a matroid constraint has remained elusive. In particular, all known techniques fail for this problem and there are no known constant factor approximation algorithms whose adaptivity is sublinear in the rank of the matroid k or in the worst case sublinear in the size of the ground set n. We present an algorithm that has an approximation guarantee arbitrarily close to the optimal 1 - 1/e for monotone submodular maximization under a matroid constraint and has near-optimal adaptivity of O(log (n) log (k)). This result is obtained using a novel technique of adaptive sequencing, which departs from previous techniques for submodular maximization in the adaptive complexity model. In addition to our main result, we show how to use this technique to design other approximation algorithms with strong approximation guarantees and polylogarithmic adaptivity.

关键词： submodular optimization parallel algorithms matroids adaptivity

来源：评论

学校读者我要写书评

暂无评论

Communication optimization strategies for distributed deep neural network training: A survey

引用

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 2021年 149卷 52-65页

作者： Ouyang, Shuo Dong, Dezun Xu, Yemao Xiao, Liquan Natl Univ Def Technol Coll Comp Changsha 410073 Hunan Peoples R China

Recent trends in high-performance computing and deep learning have led to the proliferation of studies on large-scale deep neural network training. However, the frequent communication requirements among computation nodes drastically slow the overall training speeds, which causes bottlenecks in distributed training, particularly in clusters with limited network bandwidths. To mitigate the drawbacks of distributed communications, researchers have proposed various optimization strategies. In this paper, we provide a comprehensive survey of communication strategies from both an algorithm viewpoint and a computer network perspective. Algorithm optimizations focus on reducing the communication volumes used in distributed training, while network optimizations focus on accelerating the communications between distributed devices. At the algorithm level, we describe how to reduce the number of communication rounds and transmitted bits per round. In addition, we elucidate how to overlap computation and communication. At the network level, we discuss the effects caused by network infrastructures, including logical communication schemes and network protocols. Finally, we extrapolate the potential future challenges and new research directions to accelerate communications for distributed deep neural network training. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Distributed deep learning Communication optimization parallel algorithms Network infrastructure

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：