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

Accelerating smith-waterman algorithm for Biological Database Search on CUDA-Compatible GPUs

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2010年第6期E93D卷 1479-1488页

作者： Munekawa, Yuma Ino, Fumihiko Hagihara, Kenichi Osaka Univ Grad Sch Informat Sci & Technol Suita Osaka 5650871 Japan

This paper presents a fast method capable of accelerating the smith-waterman algorithm for biological database search on a cluster of graphics processing units (GPUs). Our method is implemented using compute unified device architecture (CUDA), which is available on the nVIDIA GPO. As compared with previous methods, our method has four major contributions. (1) The method efficiently uses on-chip shared memory to reduce the data amount being transferred between off-chip video memory and processing elements in the GPO. (2) It also reduces the number of data fetches by applying a data reuse technique to query and database sequences. (3) A pipelined method is also implemented to overlap GPU execution with database access. (4) Finally, a master/worker paradigm is employed to accelerate hundreds of database searches on a cluster system. In experiments, the peak performance on a GeForce GTX 280 card reaches 8.32 giga cell updates per second (GCUPS). We also find that our method reduces the amount of data fetches to 1/140, achieving approximately three times higher performance than a previous CODA-based method. Our 32-node cluster version is approximately 28 times faster than a single GPO version. Furthermore, the effective performance reaches 75.6 giga instructions per second (GIPS) using 32 GeForce 8800 GTx cards.

关键词： smith-waterman algorithm sequence alignment acceleration GPU CUDA

来源：评论

学校读者我要写书评

暂无评论

ASW: Accelerating smith-waterman algorithm on Coupled CPU-GPU Architecture

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 2019年第3期47卷 388-402页

作者： Zou, Huihui Tang, Shanjiang Yu, Ce Fu, Hao Li, Yusen Tang, Wenjie Tianjin Univ Coll Intelligence & Comp Tianjin Peoples R China Nankai Univ Sch Comp Tianjin Peoples R China Natl Univ Def Technol Coll Syst Engn Changsha Hunan Peoples R China

smith-waterman algorithm (SW) is a popular dynamic programming algorithm widely used in bioinformatics for local biological sequence alignment. Due to the O(n2) high time and space complexity of SW and growing size of biological data, it is crucial to accelerate SW for high performance. In view of the GPU high efficiency in science computation, many existing studies (e.g., CUDAlign, CUDASW++) speedup SW with GPU. However, the strong data dependency makes SW communication intensive, and the previous works fail to fully leverage the heterogeneous capabilities of the GPU machine for either the neglect of the CPU ability or the low bandwidth of PCI-e. In this paper, we propose ASW, which aims at accelerating SW algorithm with accelerated processing unit (APU), a heterogeneous processor integrates CPU and GPU in a single die and share the same memory. This coupled CPU-GPU architecture is more suitable for frequent data exchanging due to the elimination of PCI-e bus. For the full utilization of both CPU and GPU in APU system, ASW partitions the whole SW matrix into blocks and dynamically dispatches each block to CPU and GPU for the concurrent execution. A DAG-based dynamic scheduling method is presented to dispatch the workload automatically. Moreover, we also design a time cost model to determine the partition granularity in the matrix division phase. We have evaluated ASW on AMD A12 platform and our results show that ASW achieves a good performance of 7.2 GCUPS (gigacells update per second).

关键词： smith-waterman algorithm Heterogeneous processors APU Load balancing

来源：评论

学校读者我要写书评

暂无评论

Pattern matching of alarm flood sequences by a modified smith-waterman algorithm

引用

CHEMICAL ENGINEERING RESEARCH & DESIGN 2013年第6期91卷 1085-1094页

作者： Cheng, Yue Izadi, Iman Chen, Tongwen Univ Alberta Dept Elect & Comp Engn Edmonton AB T6G 2V4 Canada Matrikon Inc Edmonton AB T5J 3N4 Canada

Alarm flooding is one of the main problems in alarm management. Alarm flood pattern analysis is helpful for root cause analysis of historical floods and for incoming flood prediction. This paper deals with a data driven method for alarm flood pattern matching. An alarm flood is represented by a time-stamped alarm sequence. A modified smith-waterman algorithm considering the time stamp information is proposed to calculate a similarity index of alarm floods. The effectiveness of the algorithm is validated by a case study on actual chemical process alarm data. (C) 2012 The Institution of Chemical Engineers. Published by Elsevier B.V. All rights reserved.

关键词： Alarm flood Time-stamped sequences Approximate sequence matching smith-waterman algorithm Knowledge extraction

来源：评论

学校读者我要写书评

暂无评论

A Review of Parallel Implementations for the smith-waterman algorithm

引用

INTERDISCIPLINARY SCIENCES-COMPUTATIONAL LIFE SCIENCES 2022年第1期14卷 1-14页

作者： Xia, Zeyu Cui, Yingbo Zhang, Ang Tang, Tao Peng, Lin Huang, Chun Yang, Canqun Liao, Xiangke Natl Univ Def Technol Sch Comp Changsha 410073 Peoples R China

The rapid advances in sequencing technology have led to an explosion of sequence data. Sequence alignment is the central and fundamental problem in many sequence analysis procedure, while local alignment is often the kernel of these algorithms. Usually, smith-waterman algorithm is used to find the best subsequence match between given sequences. However, the high time complexity makes the algorithm time-consuming. A lot of approaches have been developed to accelerate and parallelize it, such as vector-level parallelization, thread-level parallelization, process-level parallelization, and heterogeneous acceleration, but the current researches seem unsystematic, which hinders the further research of parallelizing the algorithm. In this paper, we summarize the current research status of parallel local alignments and describe the data layout in these work. Based on the research status, we emphasize large-scale genomic comparisons. By surveying some typical alignment tools' performance, we discuss some possible directions in the future. We hope our work will provide the developers of the alignment tool with technical principle support, and help researchers choose proper alignment tools.

关键词： smith-waterman algorithm Vector-level parallelization Intra-sequence alignment Inter-sequence alignment

来源：评论

学校读者我要写书评

暂无评论

The Comparative Analysis of smith-waterman algorithm with Jaro-Winkler algorithm for the Detection of Duplicate Health Related Records

The Comparative Analysis of Smith-Waterman Algorithm with Ja...

引用

International Conference on Advances in Big Data, Computing and Data Communication Systems (icABCD)

作者： Agbehadji, Israel Edem Yang, Hongji Fong, Simon Millham, Richard Durban Univ Technol Dept Informat Technol ICT & Soc Res Grp Durban South Africa Bath Spa Univ Dept Comp & Informat Sci Bath Avon England Univ Macau Dept Comp & Informat Sci Taipa Macau Peoples R China

ISBN: (纸本)9781538630600

Duplicate detection is a process of identifying a pair of words that refers to the same real-word object. Generally, words consist of letters that have a syntax representation. In most cases, words, such as names, are incorrectly spelt during data entry and that creates duplicate data and if it is unresolved could lead to inc onsistency of data. Fundamental algorithms that are applied in th e design of duplicate detection systems includes smith-waterman and Jaro-Winkler algorithms. The study compares and analyses t he application of smith-waterman algorithm and Jaro-Winkler a lgorithm to find duplicate words in large dataset such as health d ataset. The basis for comparison is to find how accurate these algo rithms are in detecting duplicate words in large health dataset. T he contribution of this paper is the use of transitive and symmetry property on both smith-waterman and Jaro-Winkler algorithm when large dataset is involved in the duplicate detection processes

关键词： smith-waterman algorithm Jaro-Winkler algorith m duplicate detection similarity measure tokenization

来源：评论

学校读者我要写书评

暂无评论

An Efficient and High Performance Linear Recursive Variable Expansion Implementation of the smith-waterman algorithm

An Efficient and High Performance Linear Recursive Variable ...

引用

Annual International Conference of the IEEE-Engineering-in-Medicine-and-Biology-Society

作者： Hasan, Laiq Al-Ars, Zaid Delft Univ Technol Comp Engn Lab NL-2628 CD Delft Netherlands

ISBN: (纸本)9781424432950

In this paper, we present an efficient and high performance linear recursive variable expansion (RVE) implementation of the smith-waterman (S-W) algorithm and compare it with a traditional linear systolic array implementation. The results demonstrate that the linear RYE implementation performs up to 2.33 times better than the traditional linear systolic array implementation, at the cost of utilizing 2 times more resources.

关键词： Bioinformatics Sequence Alignment smith-waterman algorithm FPGAs Systolic Arrays Recursive Variable Expansion

来源：评论

学校读者我要写书评

暂无评论

Highly Efficient Mapping of the smith-waterman algorithm on CUDA-compatible GPUs

Highly Efficient Mapping of the Smith-Waterman Algorithm on ...

引用

21st IEEE International Conference on Application-Specific Systems, Architectures and Processors

作者： Dohi, Keisuke Benkrid, Khaled Ling, Cheng Hamada, Tsuyoshi Shibata, Yuichiro Nagasaki Univ Dept Comp & Informat Sci Nagasaki 852 Japan Univ Edinburgh Sch Engn Edinburgh Scotland

ISBN: (纸本)9781424469673

This paper describes a multi-threaded parallel design and implementation of the smith-waterman (SW) algorithm on graphic processing units (GPUs) with NVIDIA corporation's Compute Unified Device Architecture (CUDA). Central to this is a divide and conquer approach which divides the computation of a whole pairwise sequence alignment matrix into multiple sub-matrices (or parallelograms) each running efficiently on the available hardware resources of the GPU in hand, with temporary intermediate data stored in global memory. Moreover, we use thread warps and padding techniques in order to decrease the cost of thread synchronization, as well as loop unrolling in order to reduce the cost of conditional branches. While intermediate data is stored in global memory for large queries, the most inner loop in our implementation will only access shared memory and registers. As a result of these optimizations, our implementation of the SW algorithm achieves a throughput ranging between 9.09 GCUPS (Giga Cell Update per Second) and 12.71 GCUPS on a single-GPU version, and a throughput between 29.46 GCUPS and 43.05 GCUPS on a quad-GPU platform. Compared with the best GPU implementation of the SW algorithm reported to date, our implementation achieves up to 46% improvement in speed. The source code of our implementation is available in the public domain for Bioinformaticians to benefit from its performance.

关键词： CUDA GPU smith-waterman algorithm

来源：评论

学校读者我要写书评

暂无评论

Pattern Matching of Alarm Sequences by Using an Improved smith-waterman algorithm 3

Pattern Matching of Alarm Sequences by Using an Improved Smi...

引用

3rd International Conference on Electronics and Communication;Network and Computer Technology (ECNCT)

作者： Cheng, Li Tu, Yuanfei Gu, Shenkai Zheng, Yinghao Yang, Xiaojian Li, Chaochao Ke, Yun Hu, Jiwei Nanjing Tech Univ Coll Elect Engn & Control Sci Nanjing 211816 Peoples R China Nanjing Tech Univ Coll Comp Sci Nanjing 211816 Peoples R China Changxing HuaQiang Electron Co Ltd Huzhou 313119 Peoples R China

ISBN: (数字)9781510652118

ISBN: (纸本)9781510652118;9781510652101

Alarm flooding is one of the important problems affecting industrial safety in modern industry. Finding similar alarm sequences and clustering the disordered alarm flood sequences by a reasonable pattern matching method is an effective way to realize alarm rationalization In this paper, the element in an alarm flood sequence is represented by an alarm tag and a priority level. Based on this representation approach, we improved the smith-waterman algorithm by modified the score strategy based on alarm priorities and proposed a similarity score-based sequence segmentation method for reducing the computation cost. The effectiveness of our method was demonstrated by analyzing alarm data from an actual refinery diesel hydrogenation unit.

关键词： Alarm flood sequences matching smith-waterman algorithm alarm management industrial alarm system

来源：评论

学校读者我要写书评

暂无评论

Implementing smith-waterman algorithm with Two-dimensional Cache on GPUs

Implementing Smith-Waterman Algorithm with Two-dimensional C...

引用

2nd International Conference on Cloud and Green Computing / 2nd International Conference on Social Computing and its Applications (CGC/SCA)

作者： Feng, Xiaowen Jin, Hai Zheng, Ran Shao, Zhiyuan Zhu, Lei Huazhong Univ Sci & Technol Sch Comp Sci & Technol Cluster & Grid Comp Lab Serv Comp Technol & Syst Lab Wuhan 430074 Peoples R China

ISBN: (纸本)9780769548647;9781467330275

Finding regions of similarity between two data streams is a computational intensive and memory consuming problem, which refers to as sequence alignment for biological sequence. smith-waterman algorithm is an optimal method to find the local sequence alignment. It requires a large amount of computation and memory, and is also constrained by the memory access speed when accelerated by using Graphics Processing Units (GPUs). A new method to implement smith-waterman algorithm with two-dimensional cache is proposed, which aims at accelerating the first stage of smith-waterman algorithm and coalesced writing back the corresponding results to GPU global memory. Our proposal is implemented over NVIDIA Geforce GTX295 GPU, and compared with CUDASW++ 2.0. Experimental results show that our approach outperforms CUDASW++ 2.0 in the datasets chosen from NCBI.

关键词： smith-waterman algorithm Multiple Sequence Alignment Two-dimensional Cache Coalesced Memory Access GPU

来源：评论

学校读者我要写书评

暂无评论

PipeBSW: A Two-Stage Pipeline Structure for Banded smith-waterman algorithm on FPGA 20

PipeBSW: A Two-Stage Pipeline Structure for Banded Smith-Wat...

引用

20th IEEE-Computer-Society Annual Symposium on VLSI (ISVLSI)

作者： Li, Luyi Lin, Jun Wang, Zhongfeng Nanjing Univ Sch Elect Sci & Engn Nanjing Peoples R China

ISBN: (纸本)9781665439466

With the development of bioinformatics, there is unprecedented progress and wide applications of DNA sequencing technology, especially in helping biological and medical researchers obtain and analyze complete DNA sequences. smith-waterman (S-W) algorithm is one of the critical algorithms used in this technology. However, the tremendous amount of DNA sequence data makes it very inefficient to implement the algorithm only with software, so many recent works have tried to accelerate it on hardware. Unfortunately, many of them implemented on the CPU+FPGA heterogeneous platform are likely to require high memory bandwidth and large hardware resource. To mitigate these drawbacks, in this paper we propose PipeBSW, an hardware acceleration implementation on FPGA based on the concept of banded SW. Using the lookahead calculation technique in cells and a two-stage pipeline structure for processing elements and the backtracking module, the experimental results show that the proposed system can achieve a 720.9Mbps throughput with a 58.4% LUT consumption reduction, compared with the prior work without the pipeline structure.

关键词： FPGA smith-waterman algorithm Hardware Acceleration DNA Alignment

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：