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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Tight Analysis of parallel Randomized Greedy MIS

引用

ACM TRANSACTIONS ON algorithms 2020年第1期16卷 1–13页

作者： 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Optimal Metastability-Containing Sorting via parallel Prefix Computation

引用

IEEE TRANSACTIONS ON COMPUTERS 2020年第2期69卷 198-211页

作者： Bund, Johannes Lenzen, Christoph Medina, Moti Max Planck Inst Informat Saarland Informat Campus D-66123 Saarbrucken Germany Ben Gurion Univ Negev Sch Elect & Comp Engn IL-8410501 Beer Sheva Israel

Friedrichs et al. (TC 2018) showed that metastability can be contained when sorting inputs arising from time-to-digital converters, i.e., measurement values can be correctly sorted without resolving metastability using synchronizers first. However, this work left open whether this can be done by small circuits. We show that this is indeed possible, by providing a circuit that sorts Gray code inputs (possibly containing a metastable bit) and has asymptotically optimal depth and size. Our solution utilizes the parallel prefix computation (PPC) framework (JACM 1980). We improve this construction by bounding its fan-out by an arbitrary f >= 3, without affecting depth and increasing circuit size by a small constant factor only. Thus, we obtain the first PPC circuits with asymptotically optimal size, constant fan-out, and optimal depth. To show that applying the PPC framework to the sorting task is feasible, we prove that the latter can, despite potential metastability, be decomposed such that the core operation is associative. We obtain asymptotically optimal metastability-containing sorting networks. We complement these results with simulations, independently verifying the correctness as well as small size and delay of our circuits. Proofs are omitted in this version;the article with full proofs is provided online at http://***/abs/1911.00267.

关键词： Approximation Theory Computational Complexity Gray Codes parallel algorithms Sorting Asymptotically Optimal Metastability Containing Sorting Networks TC 2018 Sorting Inputs Time To Digital Converters Measurement Values Gray Code Inputs Metastable Bit Asymptotically Optimal Depth parallel Prefix Computation Framework PPC Circuits Asymptotically Optimal Size PPC Framework Sorting Reflective Binary Codes Integrated Circuit Modeling Task Analysis Delays Computational Modeling Encoding

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Fast Grayscale Morphology for Circular Window

引用

COMPUTER GRAPHICS FORUM 2023年第7期42卷

作者： 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

来源：评论

学校读者我要写书评

暂无评论

Development of vector algorithm using CUDA technology for three-dimensional retinal laser coagulation process modeling

COMPUTER OPTICS

引用

COMPUTER OPTICS 2021年第3期45卷 427-+页

作者： Shirokanev, A. S. Andriyanov, N. A. Ilyasova, N. Y. Samara National Research University Moskovskoye Shosse 34 Samara 443086 Russian Federation IPSI RAS – Branch of the FSRC “Crystallography and Photonics” RAS Molodogvardeyskaya 151 Samara 443001 Russian Federation Financial University under the Government of the Russian Federation Leningradskii prospekt 49 Moscow 125167 Russian Federation

For diabetic retinopathy treatment, laser coagulation is used in modern practice. During the laser surgery process, the parameters of laser exposure are selected manually by a doctor, which requires the doctor to have sufficient experience and knowledge to achieve a therapeutic effect. On the basis of mathematical modeling of the laser coagulation process, it is possible to estimate the crucial parameters without performing an operation. However, the retina has a rather complex structure, and when even low-cost numerical methods are used for modeling, it takes a long time to obtain a result. In this regard, the development of time-efficient algorithms for three-dimensional modeling is an urgent task, since the use of such algorithms will provide a comprehensive study within a limited time. In this paper, we study the execution time of algorithms that implement various variations in the application of the splitting method and the finite difference method, adapted to the set problem of heat conduction. The study reveals the most efficient algorithm, which is then vectorized and implemented using the CUDA technology. The study was carried out using Intel Core i7-10875H and Nvidia RTX 2080 MAX Q and showed that an analog of the vector algorithm, focused on solving a multidimensional heat conduction problem, provides an acceleration of no more than 1.5 times compared to the sequential version. The developed vector-based algorithm, focused on the application of the sweep method in all directions of the three-dimensional problem, significantly reduces the time spent on copying into the memory of the video card and provides a 40-fold acceleration in comparison with the sequential three-dimensional modeling algorithm. On the basis of the same approach, a parallel algorithm of mathematical modeling was developed, which provided a 20-fold acceleration at full processor load.

关键词： diabetic retinopathy laser coagulation mathematical modeling heat conduction equation parallel algorithms vector algorithms CUDA

来源：评论

学校读者我要写书评

暂无评论

A Distributed Method for Fast Mining Frequent Patterns From Big Data

引用

IEEE ACCESS 2021年 9卷 135144-135159页

作者： Huang, Peng-Yu Cheng, Wan-Shu Chen, Ju-Chin Chung, Wen-Yu Chen, Young-Lin Lin, Kawuu W. Natl Kaohsiung Univ Sci & Technol Dept Comp Sci & Informat Engn Kaohsiung 807618 Taiwan Natl Kaohsiung Univ Sci & Technol Dept Elect Engn Kaohsiung 807618 Taiwan Foxconn Technol Grp Taipei 114699 Taiwan

In recent years, knowledge discovery in databases provides a powerful capability to discover meaningful and useful information. For numerous real-life applications, frequent pattern mining and association rule mining have been extensively studied. In traditional mining algorithms, data are centralized and memory-resident. As a result of the large amount of data, bandwidth limitation, and energy limitations when applying these methods to distributed databases, especially in this era of big data, the performance is not effective enough. Hence, data mining on distributed environments has emerged as an important research area. To improve the performance, we propose a set of algorithms based on FP growth that discover FPs that are capable of providing fast and scalable service in distributed computing environments and a brief data structure to store items and counts to minimize the data for transmission on the network. To ensure completeness and execution capability, DistEclat and BigFIM were considered for the experiment comparison. Experiments show that the proposed method has superior cost-effectiveness for processing massive datasets and good capabilities under various experiment conditions. The proposed method on average required only 33% of the execution time and 45% of the transmission cost of DistEclat. Compared to BigFIM, The proposed method on average required 23.3% of the execution time and 14.2% of the transmission cost of BigFIM.

关键词： Data mining Distributed databases Itemsets Costs Memory management Big Data Artificial intelligence Data mining parallel algorithms distributed computing

来源：评论

学校读者我要写书评

暂无评论

A lightweight semi-centralized strategy for the massive parallelization of branching algorithms

引用

parallel COMPUTING 2023年 116卷

作者： Pastrana-Cruz, Andres Lafond, Manuel Univ Sherbrooke Dept Informat 2500 Blvd Univ Sherbrooke PQ J1K 2R1 Canada

Several NP-hard problems are solved exactly using exponential-time branching strategies, whether it be branch-and-bound algorithms, or bounded search trees in fixed-parameter algorithms. The number of tractable instances that can be handled by sequential algorithms is usually small, whereas massive parallelization has been shown to significantly increase the space of instances that can be solved exactly. However, previous centralized approaches require too much communication to be efficient, whereas decentralized approaches are more efficient but have difficulty keeping track of the global state of the *** this work, we propose to revisit the centralized paradigm while avoiding previous bottlenecks. In our strategy, the center has lightweight responsibilities, requires only a few bits for every communication, but is still able to keep track of the progress of every worker. In particular, the center never holds any task but is able to guarantee that a process with no work always receives the highest priority task *** strategy was implemented in a generic C++ library called GemPBA, which allows a programmer to convert a sequential branching algorithm into a parallel version by changing only a few lines of code. An experimental case study on the vertex cover problem demonstrates that some of the toughest instances from the DIMACS challenge graphs that would take months to solve sequentially can be handled within two hours with our approach.

关键词： Load balancing Vertex cover parallel algorithms Scalable parallelism Branching algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：