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

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

来源：评论

学校读者我要写书评

暂无评论

parallel Binary Search Tree Construction Inspired by Thread-Level Speculation

Parallel Binary Search Tree Construction Inspired by Thread-...

引用

Summer Virtual Conference on Software Engineering, Artificial Intelligence, Networking and parallel/Distributed Computing (SNPD-Summer), ACIS International

作者： Hiroaki Hirata Atsushi Nunome Faculty of information and human sciences Kyoto Institute of Technology Kyoto City Japan

ISBN: (纸本)9798350396386

Binary search trees (BSTs) are one of the most important data structures in computer science. A parallel construction algorithm of a BST can be easily derived from the sequential algorithm. Since the structure of the generated BST is different depending on the order of inserted nodes, however, such a parallel algorithm cannot generate a BST with the same structure (node position) as a BST generated by the sequential algorithm. So this paper presents a new parallel algorithm to construct a BST having the same structure as a BST the sequential algorithm constructs. This algorithm was derived based on the concept of thread-level speculation but is a purely (non-speculatively) parallel one. Our experiments showed that for the large enough size of BSTs, the program implementing our new algorithm could construct a BST with a single structure by only 9% performance loss than the program that constructs BST having different structures every time of execution.

关键词： Computer science Instruction sets Software algorithms Binary search trees Data structures parallel algorithms Artificial intelligence

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Efficient numerical algorithm for solving the gravimetry problem of finding a lateral density in a layer: parallel implementation

引用

MATHEMATICAL METHODS IN THE APPLIED SCIENCES 2020年第13期43卷 7774-7787页

作者： Akimova, Elena N. Misilov, Vladimir E. RAS Ural Branch Krasovskii Inst Math & Mech Ekaterinburg Russia Ural Fed Univ Inst Radioelect & Informat Technol Ekaterinburg Russia

The paper is devoted to developing the new time- and memory-efficient algorithm BiCGSTABmem for solving the inverse gravimetry problem of determination of a variable density in a layer using the gravitational data. The problem is in solving the linear Fredholm integral equation of the first kind. After discretization of the domain and approximation of the integral operator, this problem is reduced to solving a large system of linear algebraic equations. It is shown that the matrix of coefficients is the Toeplitz-block-Toeplitz one in the case of the horizontal layer. For calculating and storing the elements of this matrix, we construct an efficient method, which significantly reduces the required memory and time. For the case of the curvilinear layer, we construct a method for approximating the parts of the matrix by a Toeplitz-block-Toeplitz one. This allows us to exploit the same efficient method for storing and processing the coefficient matrix in the case of a curvilinear layer. To solve the system of linear equations, we constructed the parallel algorithm on the basis of the stabilized biconjugated gradient method with using the Toeplitz-block-Toeplitz structure of the matrix. We implemented the BiCGSTAB and BiCGSTABmem algorithms for the Uran cluster supercomputer using the hybrid MPI + OpenMP technology. A model problem with synthetic data was solved for a large grid. It was shown that the new BiCGSTABmem algorithm reduces the computation time in comparison with the BiCGSTAB. Scalability of the parallel algorithm was studied.

关键词： BiCGSTAB method density finding problem inverse problems MPI plus OpenMP technology parallel algorithms Toeplitz matrices

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

An Asynchronously Alternative Stochastic Gradient Descent Algorithm for Efficiently parallel Latent Feature Analysis on Shared-Memory

An Asynchronously Alternative Stochastic Gradient Descent Al...

引用

IEEE International Conference on Big Knowledge (ICBK)

作者： Wen Qin Xin Luo School of Computer Science and Technology Chongqing University of Posts and Telecommunications Chongqing China Chongqing Institute of Green and Intelligent Technology Chinese Academy of Sciences Chongqing School University of Chinese Academy of Sciences Chongqing China College of Computer and Information Science Southwest University Chongqing China

A latent feature analysis (LFA) model is highly efficient in performing representation learning to high-dimensional incomplete (HDI) data like user-item interactions data from a recommender system. Stochastic gradient descent (SGD) is frequently adopted as the learning algorithm by an LFA model owing to its low computational complexity. However, a standard SGD algorithm is in nature a serial algorithm, which affects the resultant LFA model's scalability on mass HDI data. On the other hand, existing parallel SGD algorithms commonly suffer from low speedup when building an LFA model due to their frequent synchronizations during the training process. Motivated by this discovery, this paper proposes an Asynchronously Alternative Stochastic Gradient Descent (A 2 SGD) algorithm to achieve an efficiently parallelized LFA model on shared-memory with two fold-ideas: a) adopting the principle of an alternative stochastic gradient descent algorithm to decouple the LFA process, thereby achieving two parallelizable subtasks with minimal learning information loss; b) designing a novel parallelization scheme by eliminating synchronizations from both the subtask and the thread perspectives, i.e., both sub-tasks are taken simultaneously, and their affiliated threads also executes without synchronizations. Rigorously theoretical convergence proof illustrates that the newly-proposed parallelization scheme guarantees the convergence of a resultant LFA model. Detailed experimental results on four real HDI datasets indicate that an A 2 SGD-based LFA model outperforms several state-of-the-art parallel SGD-based LFA models in terms of both missing data estimation accuracy and parallelization speedup.

关键词： Training Representation learning Computational modeling Scalability Stochastic processes Data models parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：