[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

Mitani et al., 2016 - Google Patents

Parallelizing exact and approximate string matching via inclusive scan on a GPU

Mitani et al., 2016

View PDF
Document ID
18298922257732490994
Author
Mitani Y
Ino F
Hagihara K
Publication year
Publication venue
IEEE Transactions on Parallel and Distributed Systems

External Links

Snippet

In this study, to substantially improve the runtimes of exact and approximate string matching algorithms, we propose a tribrid parallel method for bit-parallel algorithms such as the Shift- Or and Wu-Manber algorithms. Our underlying idea is to interpret bit-parallel algorithms as …
Continue reading at www-hagi.ist.osaka-u.ac.jp (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G06F9/30—Arrangements for executing machine-instructions, e.g. instruction decode
    • G06F9/30003—Arrangements for executing specific machine instructions
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G06F9/30—Arrangements for executing machine-instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline, look ahead
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G06F9/46—Multiprogramming arrangements
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformations of program code
    • G06F8/41—Compilation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F19/00—Digital computing or data processing equipment or methods, specially adapted for specific applications
    • G06F19/10—Bioinformatics, i.e. methods or systems for genetic or protein-related data processing in computational molecular biology
    • G06F19/22—Bioinformatics, i.e. methods or systems for genetic or protein-related data processing in computational molecular biology for sequence comparison involving nucleotides or amino acids, e.g. homology search, motif or SNP [Single-Nucleotide Polymorphism] discovery or sequence alignment
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements

Similar Documents

Publication Publication Date Title
Mitani et al. Parallelizing exact and approximate string matching via inclusive scan on a GPU
Schatz et al. High-throughput sequence alignment using Graphics Processing Units
Schlegel et al. Fast Sorted-Set Intersection using SIMD Instructions.
Inoue et al. Faster set intersection with SIMD instructions by reducing branch mispredictions
Cho et al. PARADIS: An efficient parallel algorithm for in-place radix sort
Helal et al. Alto: Adaptive linearized storage of sparse tensors
Wei et al. Accelerating the Bron-Kerbosch algorithm for maximal clique enumeration using GPUs
Chen Efficient and scalable graph pattern mining on {GPUs}
Chen et al. Fingers: Exploiting fine-grained parallelism in graph mining accelerators
Kozawa et al. Gpu-accelerated graph clustering via parallel label propagation
Nguyen et al. Efficient, out-of-memory sparse MTTKRP on massively parallel architectures
Pham et al. Accelerating bwa-mem read mapping on gpus
Xiaochen et al. Register level sort algorithm on multi-core SIMD processors
Huo et al. An execution strategy and optimized runtime support for parallelizing irregular reductions on modern gpus
Constantin et al. Parallelization of the Hoshen-Kopelman algorithm using a finite state machine
Han et al. Succinct suffix sorting in external memory
Kouzinopoulos et al. A hybrid parallel implementation of the Aho–Corasick and Wu–Manber algorithms using NVIDIA CUDA and MPI evaluated on a biological sequence database
Jiang et al. Fast and efficient parallel breadth-first search with power-law graph transformation
Ozdal Improving efficiency of parallel vertex-centric algorithms for irregular graphs
Kouzinopoulos et al. Parallel processing of multiple pattern matching algorithms for biological sequences: methods and performance results
Sakai et al. Towards automating multi-dimensional data decomposition for executing a single-GPU code on a multi-GPU system
Kaski et al. Engineering motif search for large motifs
Wang et al. Accelerating the Smith-Waterman algorithm by GPU for high-throughput sequence alignment
Zhang Transforming and optimizing irregular applications for parallel architectures
Wang et al. Optimization in the parallelism extraction algorithm with spanning tree on a multi‐GPU environment