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

36th IEEE International parallel and Distributed Processing Symposium (IEEE IPDPS)

作者： Singh, Somesh Ucar, Bora Univ Lyon ENS Lyon INRIA Lyon France Univ Lyon ENS Lyon INRIA LIP CNRS Lyon France Univ Lyon ENS Lyon INRIA CNRS Lyon France

ISBN: (纸本)9781665497473

Querying the existence of an edge in a given graph or hypergraph is a building block in several algorithms. Hashing-based methods can be used for this purpose, where the given edges are stored in a hash table in a preprocessing step, and then the queries are answered using the lookup operations. While the general hashing methods have fast lookup times in the average case, the worst case run time is much higher. Perfect hashing methods take advantage of the fact that the items to be stored are all available and construct a collision free hash function for the given input, resulting in an optimal lookup time even in the worst case. We investigate an efficient shared-memory parallel implementation of a recently proposed perfect hashing method for hypergraphs. We experimentally compare the resulting parallel algorithms with the state-of-the-art and demonstrate better run time and scalability on a set of hypergraphs corresponding to real-life sparse tensors.

关键词： Hash functions Distributed processing Tensors Scalability Conferences Sparse matrices parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Distributed Unconstrained Local Search for Multilevel Graph Partitioning 24

Brief Announcement: Distributed Unconstrained Local Search f...

引用

36th ACM Symposium on parallelism in algorithms and Architectures (SPAA)

作者： Sanders, Peter Seemaier, Daniel Karlsruhe Inst Technol Karlsruhe Germany

ISBN: (纸本)9798400704161

Partitioning a graph into blocks of roughly equal weight while cutting only few edges is a fundamental problem in computer science with numerous practical applications. While shared-memory parallel partitioners have recently matured to achieve the same quality as widely used sequential partitioners, there is still a pronounced quality gap between distributed partitioners and their sequential counterparts. In this work, we shrink this gap considerably by describing the engineering of an unconstrained local search algorithm suitable for distributed partitioners. We integrate the proposed algorithm in a distributed multilevel partitioner. Our extensive experiments show that the resulting algorithm scales to thousands of PEs while computing cuts that are, on average, only 3.5% larger than those of a state-of-the-art high-quality shared-memory partitioner. Compared to previous distributed partitioners, we obtain on average 6.8% smaller cuts than the best-performing competitor while being more than 9 times faster.

关键词： graph partitioning distributed algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient parallel algorithms for the maximum subarray problem 14

Efficient parallel algorithms for the maximum subarray probl...

引用

12th Australasian Symposium on parallel and Distributed Computing, AusPDC 2014

作者： Takaoka, Tadao Department of Computer Science University of Canterbury Christchurch New Zealand

ISBN: (纸本)9781921770340

parallel algorithm design is generally hard. parallel program verification is even harder. We take an ex-ample from the maximum subarray problem and and show those two problems of design and verification. The best known communication steps for a mesh architecture for the maximum subarray problem is 2n - 1. We give a formal proof for the parallel al-gorithm on the mesh architecture based on Hoare logic. The main part of the proof is to establish sev-eral space/time invariants with three indices (i, j, k). The indices) pair specifies the invariant at the) grid point of the mesh and k specifies the k-th step in the computation. Then ignoring additive constants, the communication steps are improved to (3/2)n steps and finally n steps, which is optimal in terms of communication steps. Also the first algo-rithm is implemented on a Blue Gene parallel com-puter and performance measurements conducted are shown. © 2014, Australian Computer Society, Inc.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Mini-batching with Fused Training and Testing for Data Streams Processing on the Edge 21

Mini-batching with Fused Training and Testing for Data Strea...

引用

21st ACM International Conference on Computing Frontiers (CF)

作者： Luna, Reginaldo Cassales, Guilherme Pfahringer, Bernhard Bifet, Albert Gomes, Heitor Murilo Senger, Hermes Univ Fed Sao Carlos Sao Carlos Brazil Univ Waikato Hamilton New Zealand Victoria Univ Wellington Wellington New Zealand

ISBN: (纸本)9798400705977

Edge Computing (EC) has emerged as a solution to reduce energy demand and greenhouse gas emissions from digital technologies. EC supports low latency, mobility, and location awareness for delay-sensitive applications by bridging the gap between cloud computing services and end-users. Machine learning (ML) methods have been applied in EC for data classification and information processing. Ensemble learners have often proven to yield high predictive performance on data stream classification problems. Mini-batching is a technique proposed for improving cache reuse in multi-core architectures of bagging ensembles for the classification of online data streams, which benefits application speedup and reduces energy consumption. However, the original mini-batching presents limited benefits in terms of cache reuse and it hinders the accuracy of the ensembles (i.e., their capacity to detect behavior changes in data streams). In this paper, we improve mini-batching by fusing continuous training and test loops for the classification of data streams. We evaluated the new strategy by comparing its performance and energy efficiency with the original mini-batching for data stream classification using six ensemble algorithms and four benchmark datasets. We also compare mini-batching strategies with two hardware-based strategies supported by commodity multi-core processors commonly used in EC. Results show that mini-batching strategies can significantly reduce energy consumption in 95% of the experiments. Mini-batching improved energy efficiency by 96% on average and 169% in the best case. Likewise, our new mini-batching strategy improved energy efficiency by 136% on average and 456% in the best case. These strategies also support better control of the balance between performance, energy efficiency, and accuracy.

关键词： Computing methodologies parallel computing methodologies parallel algorithms Shared memory algorithms

来源：评论

学校读者我要写书评

暂无评论

Probe Machine Based Computing Model for Maximum Clique Problem

引用

Chinese Journal of Electronics 2022年第2期31卷 304-312页

作者： CUI Jianzhong YIN Zhixiang TANG Zhen YANG Jing Department of Computer Huainan Union University School of Electronic and Information Engineering Anhui University of Science & Technology School of Mathematics Physics and Statistics Shanghai University of Engineering Science School of Mathematics and Big Data Anhui University of Science & Technology

Probe machine(PM) is a recently reported mathematic model with massive parallelism. Herein,we presented searching the maximum clique of an undirected graph with six vertices. We constructed data library containing n sublibraries, each sublibrary corresponded to a vertex in the given graph. Then, probe library according to the induced subgraph was designed in order to search and generate all maximal cliques. Subsequently,we performed probe operation, and all maximal cliques were generated in parallel. The advantages of the proposed model lie in two aspects. On one hand, solution to NP-complete problem is generated in just one step of probe operation rather than found in vast solution *** the other hand, the proposed model is highly *** work demonstrates that PM is superior to TM in terms of searching capacity when tackling NP-complete problem.

关键词： maximal cliques maximum clique problem searching capacity data library NP-complete problem computational complexity model lie induced subgraph probe operation undirected graph mathematic model graph theory parallel algorithms optimisation parallelism computing model vertex probe library probe machine

来源：评论

学校读者我要写书评

暂无评论

Efficient 3D Hilbert Curve Encoding and Decoding algorithms

引用

Chinese Journal of Electronics 2022年第2期31卷 277-284页

作者： JIA Lianyin LIANG Binbin LI Mengjuan LIU Yong CHEN Yinong DING Jiaman Faculty of Information Engineering and Automation Kunming University of Science and Technology Yunnan Key Laboratory of Artificial Intelligence Kunming University of Science and Technology Library Yunnan Normal University School of Information Science and Engineering Guangxi University for Nationalities School of Computing Informatics and Decision Systems Arizona State University

Hilbert curve describes a one-to-one mapping between multidimensional space and 1 D *** traditional 3D Hilbert encoding and decoding algorithms work on order-wise manner and are not aware of the difference between different input data and spend equivalent computing costs on them, thus resulting in a low efficiency. To solve this problem, in this paper we design efficient 3D state views for fast encoding and decoding. Based on the state views designed, a new encoding algorithm(JFK-3HE) and a new decoding algorithm(JFK-3HD) are proposed. JFK-3HE and JFK-3HD can avoid executing iteratively encoding or decoding each order by skipping the first 0 s in input data, thus decreasing the complexity and improving the efficiency. Experimental results show that JFK-3HE and JFK-3HD outperform the state-of-the-arts algorithms for both uniform and skew-distributed data.

关键词： order-wise manner multidimensional space encoding state-of-the-arts algorithms encoding algorithm parallel algorithms JFK-3HE statistical distributions decoding solid modelling design efficient 3D JFK-3HD traditional 3D Hilbert encoding equivalent computing costs different input data decoding algorithm Hilbert curve state views iterative methods

来源：评论

学校读者我要写书评

暂无评论

parallel integer multiplication 30

Parallel integer multiplication

引用

30th Euromicro International Conference on parallel, Distributed and Network-Based Processing (PDP)

作者： Samuel, Vivien PSL Res Univ CNRS Ecole Normale Super Dept Informat ENS 45 Rue Ulm Paris France Univ Lorraine CNRS INRIA LORIA Nancy France

ISBN: (纸本)9781665469586

Multiplication is a fundamental step in many algorithms. If the multiplication of two integers of n words has a complexity of M(n), divisions and squares can be computed in O(M(n)) as well and the greatest common divisor can be computed in O(M(n) log n). Thus being able to have a small value for M(n) is extremely important. To this day, the best known algorithm for reachable values is the Schonhage-Strassen algorithm which is implemented by a few arithmetic libraries. Asymptotically faster algorithms exist, however no computer is able to hold numbers big enough for those algorithms to outrun Schonhage-Strasser. The GNU Multiple Precision (GMP) library has a sequential-only implementation of Schonhage-Strassen. However some algorithms contains a step which is a single big multiplication. Thus when trying to parallelize such an algorithm, one requires a parallel algorithm for multiplication. An example of such an algorithm is the batch factorization for Number Field Sieve. Thus people trying to implement a parallel version of such algorithms need to find an arithmetic library that implements a parallel integer multiplication. An example of such a library is the Flint (Fast Library for Number Theory) library that contains a parallel implementation of Schonhage-Strassen. In this article we present an implementation of Schonhage-Strassen, that reaches a speedup of 20 for the multiplication of two integers of 10(7) words of 64 bits using a Xeon Gold with 32 cores.

关键词： Gold Codes Libraries Complexity theory parallel algorithms Arithmetic

来源：评论

学校读者我要写书评

暂无评论

Multi-threaded parallel tetrahedral mesh improvement by combining atomic operation and graph coloring

引用

ADVANCES IN ENGINEERING SOFTWARE 2024年 198卷

作者： Wang, Yifu Wang, Junji Wang, Bohan Wang, Yifei Chen, Jianjun Zhejiang Univ Sch Aeronaut & Astronaut Hangzhou 310027 Zhejiang Peoples R China

In industrial numerical simulations, efficiently generating high-quality tetrahedral meshes remains a significant challenge. Advances in high-performance computing have made parallelization a practical approach to improving the quality of large-scale tetrahedral meshes. This study proposes a fine-grained multithreaded parallel method to accelerate tetrahedral mesh improvement. By utilizing atomic operations, we fundamentally address thread safety concerns. Additionally, through the precise use of atomic operations, task decomposition strategies, and a multithreaded memory model, we minimize the probability of task overlap and data races, thereby enhancing overall parallel mesh improvement efficiency. Experimental results demonstrate that our parallel mesh improver is robust and effective for complex industrial models. On a laptop with 16 threads, we achieved a tenfold increase in tetrahedral mesh improvement speed, with the quality of the improved meshes being comparable to that of the sequential process.

关键词： parallel algorithms Tetrahedral mesh generation Quality improvement

来源：评论

学校读者我要写书评

暂无评论

parallel Discovery of Top-k Weighted Motifs in Large Graphs 26th

Parallel Discovery of Top-k Weighted Motifs in Large Graphs

引用

26th European Conference on Advances in Databases and Information Systems (ADBIS)

作者： Koutounidis, Nikolaos Papadopoulos, Apostolos N. Aristotle Univ Thessaloniki Sch Informat Thessaloniki Greece

ISBN: (纸本)9783031157400;9783031157394

The enumeration of all cliques in a graph or finding the largest clique are important problems that unfortunately are computationally intensive. Another alternative is to select only the most important motifs (e.g., small subgraphs, or patterns), where significance is expressed by means of a function that quantifies the importance of the subgraph. Given a weighted graph G(V, E, w()), where V is the set of nodes and E is the set of edges and w() is a function that returns the weight of an edge e we are looking for the efficient computation of the top-k weighted triangles (and also higher-order cliques, e.g., 4-cliques, 5-cliques, etc.). More specifically, the proposed methodology is based on a parallel algorithm which is efficient and scalable and exploits the multi-threading capabilities of modern multi-core processors. Initially we present a solution for the discovery of top-k triangles, which are the simplest non-trivial cliques and then we generalize our solution for the discovery of top-k cliques of higher order. Performance evaluation results based on real-life networks show that the proposed algorithmic technique is significantly more efficient than the centralized one and also it is scalable showing very good speedups by increasing the number of cores.

关键词： Graph mining Graph motifs parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and parallel Applications 63

Deterministic Low-Diameter Decompositions for Weighted Graph...

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Rozhon, Vaclav Elkin, Michael Grunau, Christoph Haeupler, Bernhard Swiss Fed Inst Technol Zurich Switzerland Ben Gurion Univ Negev Beer Sheva Israel Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781665455190

This paper presents new deterministic and distributed low-diameter decomposition algorithms for weighted graphs. In particular, we show that if one can efficiently compute approximate distances in a parallel or a distributed setting, one can also efficiently compute low-diameter decompositions. This consequently implies solutions to many fundamental distance based problems using a polylogarithmic number of approximate distance computations. Our low-diameter decomposition generalizes and extends the line of work starting from [RG20] to weighted graphs in a very model-independent manner. Moreover, our clustering results have additional useful properties, including strong-diameter guarantees, separation properties, restricting cluster centers to specified terminals, and more. Applications include: - The first near-linear work and polylogarithmic depth randomized and deterministic parallel algorithm for low-stretch spanning trees (LSST) with polylogarithmic stretch. Previously, the best parallel LSST algorithm required m center dot n(o(1)) work and n(o(1)) depth and was inherently randomized. No deterministic LSST algorithm with truly sub-quadratic work and sub-linear depth was known. - The first near-linear work and polylogarithmic depth deterministic algorithm for computing an l(1) -embedding into polylogarithmic dimensional space with polylogarithmic distortion. The best prior deterministic algorithms for l(1) -embeddings either require large polynomial work or are inherently sequential. Even when we apply our techniques to the classical problem of computing a ball-carving with strong-diameter O(log(2) n) in an unweighted graph, our new clustering algorithm still leads to an improvement in round complexity from O(log(10) n) rounds [CG21] to O(log(4) n).

关键词： Computer science Computational modeling Clustering algorithms Distortion Approximation algorithms Complexity theory parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：