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

High Performance Computing, Networking, Storage and Analysis, SC-W: Workshops of the International Conference for

作者： Ritvik Rao Kavitha Chandrasekar Laxmikant Kale University of Illinois Urbana IL USA

ISBN: (数字)9798350355543

ISBN: (纸本)9798350355550

Large-scale graphs with billions and trillions of vertices and edges require efficient parallel algorithms for common graph problems, one of which is single-source shortest paths (SSSP). Bulk-synchronous parallel algorithms such as ∆-stepping experience large synchronization costs at the scale of many nodes, so asynchronous approaches are needed for scalability. However, asynchronous approaches are susceptible to wasteful, speculative execution. We introduce ACIC, a highly asynchronous approach modulated by continuous concurrent introspection and adaptation. Using message-driven concurrent reductions and broadcasts, task-based scheduling, and an adaptive aggregation library, we explore techniques such as evolving windows and generation and prioritized flow of optimal updates, or edge relaxations, aimed at reducing speculative loss without constraining parallelism. Our results, while preliminary, demonstrate the promise of these ideas, with the potential to impact a wider class of graph algorithms.

关键词： Shortest path problem Costs Scalability High performance computing Conferences Libraries Synchronization parallel algorithms Optimization Monitoring

来源：评论

学校读者我要写书评

暂无评论

Implementation of Longest Common Subsequence Algorithm Using Thread parallelization in Java

Implementation of Longest Common Subsequence Algorithm Using...

引用

International Conference on Business and Industrial Research (ICBIR)

作者： Mark Phil B. Pacot Gleen A. Dalaorao Department of Computer Science Caraga State University Caraga Region Philippines Department of Information Technology Caraga State University Caraga Region Philippines

ISBN: (数字)9798350383027

ISBN: (纸本)9798350383034

This sequence alignment stands as a pivotal method in the realm of bioinformatics, meticulously employed to ascertain the degree of similarity between diverse sequences such as DNA, RNA, and amino acids. Among the myriad techniques utilized in tackling sequence alignment challenges, the Longest Common Subsequence (LCS) takes center stage. This paper delves into the realm of enhancing LCS efficiency through the implementation of thread parallelization. Drawing inspiration from the seminal work of Wagner and Fischer in 1974, both sequential and parallel techniques exhibit remarkable consistency in identifying the maximum length of LCS. However, this research goes a step further by introducing thread parallelization, which leverages multithreading, resource synchronization, and task decomposition within the domain of parallel programming. The meticulous integration of these advanced techniques results in a notable enhancement in terms of running time compared to the conventional iterative sequential approach. The experimentation and evaluation of both sequential and parallel approaches were conducted using Netbeans, a robust Integrated Development Environment (IDE) tailored for the Java Programming Language. The findings underscore the superior performance of the thread parallelization strategy, establishing its prowess in optimizing the execution time of LCS problem resolution.

关键词： Java parallel programming Multithreading Instruction sets RNA Synchronization Bioinformatics parallel algorithms Standards Optimization

来源：评论

学校读者我要写书评

暂无评论

An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LIS

arXiv

引用

arXiv 2024年

作者： Koo, Jaehyun MIT United States

We present an O(1)-round fully-scalable deterministic massively parallel algorithm for computing the min-plus matrix multiplication of unit-Monge matrices. We use this to derive a O(log n)-round fully-scalable massively parallel algorithm for solving the exact longest increasing subsequence (LIS) problem. For a fully-scalable MPC regime, this result substantially improves the previously known algorithm of O(log4 n)-round complexity, and matches the best algorithm for computing the (1 + ǫ)-approximation of LIS. © 2024, CC BY.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel algorithm for pattern matching problems under substring consistent equivalence relations

arXiv

引用

arXiv 2022年

作者： Jargalsaikhan, Davaajav Hendrian, Diptarama Yoshinaka, Ryo Shinohara, Ayumi Graduate School of Information Sciences Tohoku University Sendai Japan

Given a text and a pattern over an alphabet, the pattern matching problem searches for all occurrences of the pattern in the text. An equivalence relation ≈ is called a substring consistent equivalence relation (SCER), if for two strings X and Y, X ≈ Y implies |X| = |Y | and X[i : j] ≈ Y [i : j] for all 1 ≤ i ≤ j ≤ |X|. In this paper, we propose an efficient parallel algorithm for pattern matching under any SCER using the "duel-and-sweep" paradigm. For a pattern of length m and a text of length n, our algorithm runs in (Equation presented) time and (Equation presented) work, with (Equation presented) time and (Equation presented) work preprocessing on the Priority Concurrent Read Concurrent Write parallel Random-Access Machines (P-CRCW PRAM), where (Equation presented), and (Equation presented) are parameters dependent on SCERs, which are often linearly bounded in n and m, respectively. © 2022, CC BY.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Image Encryption Scheme for Deniable Authentication Based on Chaos Theory

引用

International Journal of Network Security 2024年第3期26卷 454-466页

作者： Zhang, Qiu-Yu Liu, Yi-Lin Wu, Guo-Rui School of Computer and communication Lanzhou University of Technology No. 287 Lan-Gong-Ping Road Lanzhou730050 China

Aiming at the complex structure of the existing deniable authentication image encryption methods based on public key cryptography and the high computational cost caused by many bilinear and modular power operations, an image encryption scheme for deniable authentication based on chaos theory was proposed. Firstly, the data owner uses the pseudo-random number generator based on the key encryption technology of Caesar’s password to generate the session key and conduct a secure exchange between the data owner and the data user by generating a hash code. Then, the improved Arnold chaotic hashing parallel algorithm is used to encrypt and decrypt the original image iteratively, and the corresponding hash values are generated during the encryption and decryption process. Finally, the data user judges the hash value to achieve deniable authentication. Experimental results show that the proposed scheme simplifies the design of the repudiation authentication cryptographic protocols and ensures the privacy and security of data user identities. The improved Arnold chaotic hashing parallel algorithm is used to improve image encryption algorithms’ security and computational efficiency. © (2024), (International Journal of Network Security). All rights reserved.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

NC algorithms FOR COMPUTING A PERFECT MATCHING AND A MAXIMUM FLOW IN ONE-CROSSING-MINOR-FREE GRAPHS

引用

SIAM JOURNAL ON COMPUTING 2021年第3期50卷 1014-1033页

作者： Eppstein, David Vazirani, Vijay V. Univ Calif Irvine Comp Sci Dept Irvine CA 92697 USA

In 1988, Vazirani gave an NC algorithm for computing the number of perfect matchings in K-3,K-3-minor-free graphs by building on Kasteleyn's scheme for planar graphs, and stated that this "opens up the possibility of obtaining an NC algorithm for finding a perfect matching in K-3,K-3-free graphs." In this paper, we finally settle this 30-year-old open problem. Building on recent NC algorithms for planar and bounded-genus perfect matching by Anari and Vazirani and later by Sankowski, we obtain NC algorithms for perfect matching in any minor-closed graph family that forbids a one-crossing graph. This family includes several well-studied graph families including the K-3,K-3-minor-free graphs and K-5-minor-free graphs. Graphs in these families not only have unbounded genus, but can have genus as high as O(n). Our method applies as well to several other problems related to perfect matching. In particular, we obtain NC algorithms for the following problems in any family of graphs (or networks) with a one-crossing forbidden minor: (1) Determining whether a given graph has a perfect matching and, if so, finding one. (2) Finding a minimum-weight perfect matching in the graph, assuming that the edge weights are polynomially bounded. (3) Finding a maximum st-flow in the network, with arbitrary capacities. The main new idea enabling our results is the definition and use of matching-mimicking networks, small replacement networks that behave the same with respect to matching problems involving a fixed set of terminals, as the larger network they replace.

关键词： parallel algorithms perfect matching graph minors mimicking networks maximum flow

来源：评论

学校读者我要写书评

暂无评论

Collaborative Optimization for Resource-constrained Federated Learning in Large-scale IoT Networks

Collaborative Optimization for Resource-constrained Federate...

引用

IEEE International Conference on Communications in China Workshops (ICCC)

作者： Haihui Xie Shuwu Chen Teng Sun Junhui Zhao Minghua Xia College of Computer and Information Sciences Fujian Agriculture and Forestry University Fuzhou China The 54th Research Institute of China Electronics Technology Group Corporation Shijiazhuang China School of Electronic and Information Engineering Beijing Jiaotong University Beijing China School of Electronics and Information Technology Sun Yat-sen University Guangzhou China

ISBN: (数字)9798350377675

ISBN: (纸本)9798350377682

Large-scale Internet-of- Things (IoT) networks enable intelligent applications and services, such as autonomous deriving. As many users generate various datasets, federated learning in distributed IoT networks emerges from learning from distinct datasets. To realize efficient and reliable communications in distributed networks, we propose a collaborative optimization model for resource-constrained federated learning using a joint design of wireless resource allocation and expected learning losses. Precisely, we start to formulate a learning-oriented power allocation problem. Then, we derive a convergence bound and build the relationship between communications and learning. At last, we perform an optimal algorithm based on majorization-minimization frameworks. Thanks to the high parallelization of the proposed algorithm, extensive experimental results corroborate that optimal power allocation in distributed networks benefits efficient federated learning compared to the state-of-the-art benchmark algorithms.

关键词： Wireless communication Federated learning Optimization models Collaboration Reliability engineering Propagation losses Resource management parallel algorithms Optimization Convergence

来源：评论

学校读者我要写书评

暂无评论

An Efficient parallel Implementation of a Perfect Hashing Method for Hypergraphs

An Efficient Parallel Implementation of a Perfect Hashing Me...

引用

IEEE International Symposium on parallel and Distributed Processing Workshops and Phd Forum (IPDPSW)

作者： Somesh Singh Bora Uç ar INRIA and LIP (CNRS - Universit&#x00E9 de Lyon - INRIA - ENS Lyon) France

ISBN: (数字)9781665497473

ISBN: (纸本)9781665497480

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

来源：评论

学校读者我要写书评

暂无评论

Automatic Construction of parallel Algorithm Portfolios for Multi-objective Optimization

arXiv

引用

arXiv 2022年

作者： Ma, Xiasheng Liu, Shengcai Hong, Wenjing School of Mechanical Engineering University of Science and Technology Beijing Beijing100083 China Beijing Key Laboratory of Research and Application for Robotic Intelligence of Hand-Eye-Brain Interaction Beijing100083 China Singapore Guangdong Key Laboratory of Brain-Inspired Intelligent Computation Department of Computer Science and Engineering Southern University of Science and Technology Guangdong Shenzhen518055 China

It has been widely observed that there exists no universal best Multi-objective Evolutionary Algorithm (MOEA) dominating all other MOEAs on all possible Multi-objective Optimization Problems (MOPs). In this work, we advocate using the parallel Algorithm Portfolio (PAP), which runs multiple MOEAs independently in parallel and gets the best out of them, to combine the advantages of different MOEAs. Since the manual construction of PAPs is non-trivial and tedious, we propose to automatically construct high-performance PAPs for solving MOPs. Specifically, we first propose a variant of PAPs, namely MOEAs/PAP, which can better determine the output solution set for MOPs than conventional PAPs. Then, we present an automatic construction approach for MOEAs/PAP with a novel performance metric for evaluating the performance of MOEAs across multiple MOPs. Finally, we use the proposed approach to construct a MOEAs/PAP based on a training set of MOPs and an algorithm configuration space defined by several variants of NSGA-II. Experimental results show that the automatically constructed MOEAs/PAP can even rival the state-of-the-art ensemble MOEAs designed by human experts, demonstrating the huge potential of automatic construction of PAPs in multi-objective optimization. Copyright © 2022, The Authors. All rights reserved.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel Vertex Color Update on Large Dynamic Networks

Parallel Vertex Color Update on Large Dynamic Networks

引用

International Conference on High Performance Computing

作者： Arindam Khanda Sanjukta Bhowmick Xin Liang Sajal K. Das Missouri University of Science and Technology Rolla USA University of North Texas Denton USA

We present the first GPU-based parallel algorithm to efficiently update vertex coloring on large dynamic networks. For single GPU, we introduce the concept of loosely maintained vertex color update that reduces computation and memory requirements. For multiple GPUs, in distributed environments, we propose priority-based ordering of vertices to reduce the communication time. We prove the correctness of our algorithms and experimentally demonstrate that for graphs of over 16 million vertices and over 134 million edges on a single GPU, our dynamic algorithm is as much as 20x faster than state-of-the-art algorithm on static graphs. For larger graphs with over 130 million vertices and over 260 million edges, our distributed implementation with 8 GPUs produces updated color assignments within 160 milliseconds. In all cases, the proposed parallel algorithms produce comparable or fewer colors than state-of-the-art algorithms.

关键词： Image color analysis Heuristic algorithms High performance computing Memory management Graphics processing units parallel algorithms Kernel

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：