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

A precise non-asymptotic complexity analysis of parallel hash functions without tree topology constraints

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 2020年第0期137卷 246-251页

作者： Atighehchi, Kevin Univ Clermont Auvergne CNRS LIMOS F-63000 Clermont France

A recent work shows how we can optimize a tree based mode of operation for a hash function where the sizes of input message blocks and digest are the same, subject to the constraint that the involved tree structure has all its leaves at the same depth. In this work, we show that we can further optimize the running time of such a mode by using a tree having leaves at all its levels. We make the assumption that the input message block has a size a multiple of that of the digest and denote by d the ratio block size over digest size. The running time is evaluated in terms of number of operations performed by the hash function, i.e. the number of calls to its underlying function. It turns out that a digest can be computed in inverted right perpendicular log(d+1)(l/2)inverted left perpendicular +2 evaluations of the underlying function using inverted right perpendicular l/2 inverted left perpendicular processors, where / is the number of blocks of the message. Other results of interest are discussed, such as the optimization of the parallel running time for a tree of restricted height. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Hash functions Merkle trees parallel algorithms Prefix-free Merkle-Damgard Sponge functions

来源：评论

学校读者我要写书评

暂无评论

Modeling, optimization and performance prediction of parallel algorithms

Modeling, optimization and performance prediction of paralle...

引用

IEEE Symposium on Computers and Communications (ISCC)

作者： Martin Húdik Michal Hodoň Department of Technical Cybernetics University of Žilina Žilina Slovakia

ISBN: (纸本)9781479942763

The high intensity of research and modeling in fields of mathematics, physics, biology and chemistry requires new computing resources. For the big computational complexity of such tasks computing time is large and costly. The most efficient way to increase efficiency is to adopt parallel principles. Purpose of this paper is to present the issue of parallel computing with emphasis on the analysis of parallel systems, the impact of communication delays on their efficiency and on overall execution time. Paper focuses is on finite algorithms for solving systems of linear equations, namely the matrix manipulation (Gauss elimination method GEM). algorithms are designed for architectures with shared memory (openMP), distributed-memory (MPI) and for their combination (MPI+openMP). The properties of the algorithms were analytically determined and they were experimentally verified. The conclusions are drawn for theory and practice.

关键词： Computers Mathematical model Algorithm design and analysis Equations Computational modeling parallel algorithms Computer architecture

来源：评论

学校读者我要写书评

暂无评论

Tight Analysis of parallel Randomized Greedy MIS

引用

ACM TRANSACTIONS ON algorithms 2020年第1期16卷 6-6页

作者： Fischer, Manuela Noever, Andreas Swiss Fed Inst Technol Univ Str 6 CH-8092 Zurich Switzerland

We provide a tight analysis that settles the round complexity of the well-studied parallel randomized greedy MIS algorithm, thus answering the main open question of Blelloch, Fineman, and Shun [SPAA'12]. The parallel/distributed randomized greedy Maximal Independent Set (MIS) algorithm works as follows. An order of the vertices is chosen uniformly at random. Then, in each round, all vertices that appear before their neighbors in the order are added to the independent set and removed from the graph along with their neighbors. The main question of interest is the number of rounds it takes until the graph is empty. This algorithm has been studied since 1987, initiated by Coppersmith, Raghavan, and Tompa [FOCS'87], and the previously best known bounds were O(log n) rounds in expectation for Erdos-Renyi random graphs by Calkin and Frieze [Random Struc. Alg.'90] and O(log(2) n) rounds with high probability for general graphs by Blelloch, Fineman, and Shun [SPAA'12]. We prove a high probability upper bound of O(log n) on the round complexity of this algorithm in general graphs and that this bound is tight. This also shows that parallel randomized greedy MIS is as fast as the celebrated algorithm of Luby [STOC'85, JALG'86].

关键词： PRAM parallel algorithms greedy algorithm maximal independent set

来源：评论

学校读者我要写书评

暂无评论

Risk Prediction and Treatment in Enterprise Management Based on Ant Colony parallel Algorithm

Lecture Notes on Data Engineering and Communications Technol...

引用

Lecture Notes on Data Engineering and Communications Technologies 2022年 129卷 99-106页

作者： Shi, Kaixin TOJOY Wisdom Enterprise Service Co. Ltd. Shanghai China

As the global economy continues to grow, the business scope of enterprises is further expanded, the environment will become more complex, the risks they face will increase, and the uncertainty will gradually increase. If an enterprise fails to manage risks properly, it will not only affect the normal operation of the enterprise, but may even lead to bankruptcy. This paper aims to study the risk prediction and processing in enterprise management based on the ant colony parallel algorithm. Based on the analysis of the current situation of risk prediction research at home and abroad, combined with the function of risk prediction and the principle of risk prediction index selection, a risk prediction system is established and reused. The parallel and distributed characteristics of ant colony algorithm establish a risk prediction model to predict enterprise management risks. The prediction results show that the relative error value of all samples is controlled below 3%, and the minimum error value is only 0.86%. Therefore, the ant parallel algorithm model can meet the accuracy requirements of enterprise management risk prediction. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel architecture to accelerate superparamagnetic clustering algorithm

引用

ELECTRONICS LETTERS 2020年第14期56卷 701-+页

作者： Wang, Pan Ke Chen, Chang Hao Pun, Sio Hang Zhang, Baijun Mak, Peng Un Vai, Mang I. Lei, Tim C. Univ Macau Inst Microelect State Key Lab Analog & Mixed Signal VLSI Macau Peoples R China Univ Macau Dept Elect & Comp Engn Macau Peoples R China Sun Yat Sen Univ Sch Elect & Informat Technol State Key Lab Optoelect Mat & Technol Guangzhou Peoples R China Univ Colorado Dept Elect Engn Denver CO 80202 USA

Superparamagnetic clustering (SPC) is an unsupervised classification technique in which clusters are self-organised based on data density and mutual interaction energy. Traditional SPC algorithm uses the Swendsen-Wang Monte Carlo approximation technique to significantly reduce the search space for reasonable clustering. However, Swendsen-Wang approximation is a Markov process which limits the conventional superparamagnetic technique to process data clustering in a sequential manner. Here the authors propose a parallel approach to replace the conventional appropriation to allow the algorithm to perform clustering in parallel. One synthetic and one open-source dataset were used to validate the accuracy of this parallel approach in which comparable clustering results were obtained as compared to the conventional implementation. The parallel method has an increase of clustering speed at least 8.7 times over the conventional approach, and the larger the sample size, the more increase in speed was observed. This can be explained by the higher degree of parallelism utilised for the increased data points. In addition, a hardware architecture was proposed to implement the parallel superparamagnetic algorithm using digital electronic technologies suitable for rapid or real-time neural spike sorting.

关键词： Monte Carlo methods Markov processes pattern clustering parallel architectures parallel algorithms neurophysiology medical computing Swendsen-Wang Monte Carlo approximation technique Markov process open-source dataset hardware architecture parallel architecture superparamagnetic clustering algorithm unsupervised classification technique data density mutual interaction energy SPC algorithm real-time neural spike sorting digital electronic technology parallel superparamagnetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Message Complexity of Multi-Valued Implicit Agreement with Shared Random Bits 22

Message Complexity of Multi-Valued Implicit Agreement with S...

引用

23rd International Conference on Distributed Computing and Networking, ICDCN 2022

作者： Bose, Kaustav Molla, Anisur Rahaman Advanced Computing and Microelectronics Unit Indian Statistical Institute India R. C. Bose Centre for Cryptology and Security Indian Statistical Institute India

ISBN: (纸本)9781450395601

An agreement protocol enables a system of n nodes in a distributed network to agree on a common input value. In the implicit version of the problem, only a subset of the nodes are required to decide the common value. This paper focuses on the message complexity of randomized implicit agreement in synchronous distributed networks. It has been shown by Augustine et al. [PODC 2018] that if the nodes have access to a shared coin, then implicit agreement can be solved with high probability1 using messages2 in expectation. However, their algorithm works only for binary input values, i.e, the input values given to the nodes are from the set {0, 1}. In this paper, we extended the result to the multi-valued setting where the input values may come from a larger but constant sized domain. We present an algorithm that solves the multi-valued implicit agreement problem with matching performance guarantees as in binary agreement. © 2022 ACM.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Speeding Up the Gomory-Hu parallel Cut Tree Algorithm with Efficient Graph Contractions

引用

ALGORITHMICA 2020年第6期82卷 1601-1615页

作者： Maske, Charles Cohen, Jaime Duarte Jr, Elias P. Univ Fed Parana Dept Informat Curitiba Parana Brazil Univ Estadual Ponta Grossa Dept Informat Ponta Grossa Parana Brazil

A cut tree is a combinatorial structure that represents the edge-connectivity between all pairs of nodes of an undirected graph. Cut trees have multiple applications in dependability, as they represent how much it takes to disconnect every pair of network nodes. They have been used for solving connectivity problems, routing, and in the analysis of complex networks, among several other applications. This work presents a parallel version of the classical Gomory-Hu cut tree algorithm. The algorithm is heavily based on tasks that compute the minimum cut on contracted graphs. The main contribution is an efficient strategy to compute the contracted graphs, that allows processes to take advantage of previously contracted graph instances, instead of always computing all contractions from the original input graph. The proposed algorithm was implemented using MPI and experimental results are presented for several families of graphs and show significant performance gains.

关键词： Cut trees parallel algorithms Gomory-Hu algorithm Graph contractions

来源：评论

学校读者我要写书评

暂无评论

A Geometric Multigrid Method for Space-Time Finite Element Discretizations of the Navier-Stokes Equations and its Application to 3D Flow Simulation

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2023年第1期49卷 5-5页

作者： Anselmann, Mathias Bause, Markus Helmut Schmidt Univ Fac Mech & Civil Engn Holstenhofweg 85 D-22043 Hamburg Germany

We present a parallelized geometric multigrid (GMG) method, based on the cell-based Vanka smoother, for higher order space-time finite element methods (STFEM) to the incompressible Navier-Stokes equations. The STFEM is implemented as a time marching scheme. The GMG solver is applied as a preconditioner for generalized minimal residual iterations. Its performance properties are demonstrated for 2D and 3D benchmarks of flow around a cylinder. The key ingredients of the GMG approach are the construction of the local Vanka smoother over all degrees of freedom in time of the respective subinterval and its efficient application. For this, data structures that store pre-computed cell inverses of the Jacobian for all hierarchical levels and require only a reasonable amount of memory overhead are generated. The GMG method is built for the *** finite element library. The concepts are flexible and can be transferred to similar software platforms.

关键词： Navier-Stokes equations higher order space-time FEM geometric multi-grid method local Vanka smoother parallel algorithms Newton's method

来源：评论

学校读者我要写书评

暂无评论

Fast Grayscale Morphology for Circular Window

引用

COMPUTER GRAPHICS FORUM 2023年第7期42卷 e14983-e14983页

作者： Moroto, Yuji Umetani, Nobuyuki Univ Tokyo Tokyo Japan

Morphological operations are among the most popular classic image filters. The filter assumes the maximum or minimum value within a window and is often used for light object thickening and thinning operations, which are important components of various workflows, such as object recognition and stylization. Circular windows are preferred over rectangular windows for obtaining isotropic filter results. However, the existing efficient algorithms focus on rectangular or binary input images. Efficient morphological operations with circular windows for grayscale images remain challenging. In this study, we present a fast grayscale morphology heuristic computation algorithm that decomposes circular windows using the convex hull of circles. We significantly accelerate traditional methods based on Minkowski addition by introducing new decomposition rules specialized for circular windows. As our morphological operation using a convex hull can be computed independently for each pixel, the algorithm is efficient for modern multithreaded hardware.

关键词： Computing methodologies -> Image processing parallel algorithms Computer vision

来源：评论

学校读者我要写书评

暂无评论

A highly parallel algorithm for computing the action of a matrix exponential on a vector based on a multilevel Monte Carlo method

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2020年第12期79卷 3495-3515页

作者： Acebron, Juan A. Herrero, Jose R. Monteiro, Jose ISCTE Univ Inst Lisbon Dept Informat Sci & Technol Lisbon Portugal Univ Lisbon Inst Super Tecn INESC ID Lisbon Portugal Univ Politecn Cataluna Dept Arquitectura Computadors Barcelona Spain

A novel algorithm for computing the action of a matrix exponential over a vector is proposed. The algorithm is based on a multilevel Monte Carlo method, and the vector solution is computed probabilistically generating suitable random paths which evolve through the indices of the matrix according to a suitable probability law. The computational complexity is proved in this paper to be significantly better than the classical Monte Carlo method, which allows the computation of much more accurate solutions. Furthermore, the positive features of the algorithm in terms of parallelism were exploited in practice to develop a highly scalable implementation capable of solving some test problems very efficiently using high performance supercomputers equipped with a large number of cores. For the specific case of shared memory architectures the performance of the algorithm was compared with the results obtained using an available Krylov-based algorithm, outperforming the latter in all benchmarks analyzed so far. (C) 2020 Elsevier Ltd. All rights reserved.

关键词： Multilevel Monte Carlo method Exponential integrators Matrix functions Network analysis parallel algorithms High performance computing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：