979 research outputs found
Hardware acceleration of BWA-MEM genomic short read mapping for longer read lengths
No full textWe present our work on hardware accelerated genomics pipelines, using either FPGAs or GPUs to accelerate execution of BWA-MEM, a widely-used algorithm for genomic short read mapping. The mapping stage can take up to 40% of overall processing time for genomics pipelines. Our implementation offloads the Seed Extension function, one of the main BWA-MEM computational functions, onto an accelerator. Sequencers typically output reads with a length of 150 base pairs. However, read length is expected to increase in the near future. Here, we investigate the influence of read length on BWA-MEM performance using data sets with read length up to 400 base pairs, and introduce methods to ameliorate the impact of longer read length. For the industry-standard 150 base pair read length, our implementation achieves an up to two-fold increase in overall application-level performance for systems with at most twenty-two logical CPU cores. Longer read length requires commensurately bigger data structures, which directly impacts accelerator efficiency. The two-fold performance increase is sustained for read length of at most 250 base pairs. To improve performance, we perform a classification of the inefficiency of the underlying systolic array architecture. By eliminating idle regions as much as possible, efficiency is improved by up to +95%. Moreover, adaptive load balancing intelligently distributes work between host and accelerator to ensure use of an accelerator always results in performance improvement, which in GPU-constrained scenarios provides up to +45% more performance.Accepted author manuscriptComputer EngineeringFTQC/Bertels LabQuantum & Computer Engineerin
An FPGA-based systolic array to accelerate the BWA-MEM genomic mapping algorithm
Get PDFWe present the first accelerated implementation of BWA-MEM, a popular genome sequence alignment algorithm widely used in next generation sequencing genomics pipelines. The Smith-Waterman-like sequence alignment kernel requires a significant portion of overall execution time. We propose and evaluate a number of FPGA-based systolic array architectures, presenting optimizations generally applicable to variable length Smith-Waterman execution. Our kernel implementation is up to 3x faster, compared to software-only execution. This translates into an overall application speedup of up to 45%, which is 96% of the theoretically maximum achievable speedup when accelerating only this kernel.Accepted Author ManuscriptComputer Engineerin
GPU Acceleration of BWA-MEM DNA Sequence Alignment
No full textOver the past 20 years, the cost of sequencing genomes has reduced drastically. As DNA data grows at an unprecedented rate, the need for fast and affordable software and hardware solutions for DNA analysis is higher than ever. A critical and time-consuming component in any DNA analysis pipeline is sequence alignment, which refers to mapping smaller sequences onto larger reference regions exhibiting high similarity. Many modern aligners break the problem of alignment into seed and extension. First, the algorithm finds matching substrings between the references and the query and then extends these strings on both ends to contain areas around the seeds. One of the most popular and utilized alignment tools is the Burrows-Wheeler aligner, specifically its Maximal Exact Match version called BWA-MEM. This tool solves the alignment problem by first finding seeds using a unique index called the FMD index, which reduces the complexity of the string matching problem while the extension is performed using a modified Smith-Waterman algorithm. Since the seed and extension methods are time-consuming tasks, they have been the target of various optimizations and acceleration attempts in the past. In this thesis, we aimed to integrate two previously developed GPU libraries, namely GPUSeed which finds seeds in a BWA-MEM like manner and GASAL2 which aims to accelerate the extension, into the BWA-MEM pipeline. The three software components were first analyzed from a theoretical standpoint and then profiled in order to determine the algorithmic and execution differences between the baseline CPU functions of BWA-MEM and the accelerated GPU implementations of GPUSeed and GASAL2. For the GPUSeed library, we found that seeding is performed 24× faster compared to the baseline BWA-MEM. For the GASAL2 library, we found around 1.5× better execution time over the baseline, while the main alignment results of the good quality alignments only differ by around 1.8% due to the GASAL2 acceleration heuristics. Based on our profiling observations, we integrated the three libraries into one complete accelerated BWA-MEM implementation and optimized various stages to achieve better performance and lower results deviations. Our integrated solution achieves speedups between 6.82× and 8.72× for single thread execution, depending on the dataset. For multithreaded execution, we find speedups between 2× and 2.8× over the baseline. For the alignment results, we found that our integrated program has around 2% of lines in the main result different from the baseline program, and if we filter alignments with mapping quality below 20, the percentage of different lines reduces to around 1%. Finally, depending on the query dataset, our accelerated library achieved between 60% and 75% GPU utilization during the seeding phase. For the extension part, we found a consistent 100% utilization for a dataset with 250 bases per query when using 14 CPU threads and varying GPU utilization between 40% and 95% for datasets with smaller query sizes. Our accelerated BWA-MEM implementation is freely available on GitHub.Computer Engineerin
Episodic encoding is more than the sum of its parts: An fMRI investigation of multifeatural contextual encoding
No full textEpisodic memories are characterized by their contextual richness, yet little is known about how the various features comprising an episode are brought together in memory. Here we employed fMRI and a multidimensional source memory procedure to investigate processes supporting the mnemonic binding of item and contextual information. Volunteers were scanned while encoding items for which the contextual features (color and location) varied independently, allowing activity elicited at the time of study to be segregated according to whether both, one, or neither feature was successfully retrieved on a later memory test. Activity uniquely associated with successful encoding of both features was identified in the intra-parietal sulcus, a region strongly implicated in the support of attentionally mediated perceptual binding. The findings suggest that the encoding of disparate features of an episode into a common memory representation requires that the features be conjoined in a common perceptual representation when the episode is initially experienced
An Efficient GPU-Accelerated Implementation of Genomic Short Read Mapping with BWA-MEM
No full textNext Generation Sequencing techniques have resulted in an exponential growth in the generation of genetics data, the amount of which will soon rival, if not overtake, other Big Data elds, such as astronomy and streaming video services.To become useful, this data requires processing by a complex pipeline of algorithms, taking multiple days even on large clusters. The mapping stage of such genomics pipelines, which maps the short reads onto a reference genome, takes up a signicant portion of execution time. BWA-MEM is the de-facto industry-standard for the mapping stage. Here, a GPU-accelerated implementation of BWA-MEM is proposed. The Seed Extension phase, one of the three main BWA-MEM algorithm phases that requires between 30%-50% of overall processing time, is ooaded onto the GPU. A thorough design space analysis is presented for an optimized mapping of this phase onto the GPU. The re-sulting systolic-array based implementation obtains a two-fold overall application-level speedup, which is the maximum theoretically achievable speedup. Moreover, this speedup is sustained for systems with up to twenty-two logical cores. Based on the ndings, a number of suggestions are made toimprove GPU architecture, resulting in potentially greatly increased performance for bioinformatics-class algorithms
Review of Joyce Carol Oates\u27s \u3cem\u3eDIS MEM BER and Other Stories of Mystery and Suspense\u3c/em\u3e
Get PDFReview of Joyce Carol Oates\u27s short story collection DIS MEM BER, considering the author\u27s attention to psychological detail and experimental forms of narrative
Power-Efficiency Analysis of Accelerated BWA-MEM Implementations on Heterogeneous Computing Platforms
Get PDFNext Generation Sequencing techniques have dramatically reduced the cost of sequencing genetic material, resulting in huge amounts of data being sequenced. The processing of this data poses huge challenges, both from a performance perspective, as well as from a power-efficiency perspective. Heterogeneous computing can help on both fronts, by enabling more performant and more power-efficient solutions. In this paper, power-efficiency of the BWA-MEM algorithm, a popular tool for genomic data mapping, is studied on two heterogeneous architectures. The performance and power-efficiency of an FPGA-based implementation using a single Xilinx Virtex-7 FPGA on the Alpha Data add-in card is compared to a GPU-based implementation using an NVIDIA GeForce GTX 970 and against the software-only baseline system. By offloading the Seed Extension phase on an accelerator, both implementations are able to achieve a two-fold speedup in overall application-level performance over the software-only implementation. Moreover, the highly customizable nature of the FPGA results in much higher power-efficiency, as the FPGA power consumption is less than one fourth of that of the GPU. To facilitate platform and tool-agnostic comparisons, the base pairs per Joule unit is introduced as a measure of power-efficiency. The FPGA design is able to map up to 44 thousand base pairs per Joule, a 2.1x gain in power-efficiency as compared to the software-only baseline.Accepted Author ManuscriptComputer EngineeringQuantum & Computer EngineeringFTQC/Bertels La
MEM-LEED的實際製作、測試及應用
No full text[[abstract]]本研究主要是MEM-LEED的實際制作、測試及應用。
傳統觀察晶體表面原子排列的方法有二：一為電子顯微鏡，直接觀測晶體表面結構：
二為利用低能電子繞射原理觀測倒數空間，再由倒數空間轉換為實數空間。MEM-LEED
(Mirror Dlectron Microscopy-Low Energy Diffraction) 即利用靜電透鏡的焦聚改
變, 而將MEM 之鏡式電子顯微鏡與LEED之低能電子繞射結合在一起。
LEED-mode 是利用低能電子對晶體表面原子排列作繞射, 而產生倒數空間(Reciproc-
al Space) 的圖形, 而後再利用矩陣運算轉換實數空間(Real Space)中原子真實排列
狀錶。MEM-mode是控制樣品(Sample)表面的電位, 使其略小於電子槍射出來的電子的
電位, 這樣電子將接觸樣品表面而未接觸, 此時電子接近樣品表面時速度很小, 非常
容易受樣品表面凹凸不平的等位面的影響, 而在螢幕(Screen)上產生明暗的影像。如
果控制樣品表面的電位, 使其略大於電子鎗射出來的電子的電位, 則電子就接觸樣品
了。利用這個原理, 我使用MEM-mode偵測170k下H 吸附Pt(110)-1×2時的表面功函數
的變化量ΔΦ隨H 吸附Pt(110)-1×2的覆蓋率θ的增加而遞減。
我使用TDS(Thermal Desorption Spectroscopy)探討H /Pt(110-1×2在不同的暴氣率
L(1L=1×10 torr.sec) 與覆蓋率θ的關係及ΔΦ與θ的關係。TDS 的實驗中得到H
/Pt(110)-1×2 的退吸過程有β 與β 兩個尖峰(Peak)。β 是二階退吸以氫原子
形式吸附, β 是一階退吸以氫分子形式吸附, 其中β 的退能量為6.5kcal/mole (
吸附溫度為170K)。
Attention to attributes and objects in working memory
Get PDFIt has been debated on the basis of change-detection procedures whether visual working memory is limited by the number of objects, task-relevant attributes within those objects, or bindings between attributes. This debate, however, has been hampered by several limitations, including the use of conditions that vary between studies and the absence of appropriate mathematical models to estimate the number of items in working memory in different stimulus conditions. We reexamined working memory limits in 2 experiments with a wide array of conditions involving color and shape attributes, relying on a set of new models to fit various stimulus situations. In Experiment 2, a new procedure allowed identical retrieval conditions across different conditions of attention at encoding. The results show that multiple attributes compete for attention, but that retaining the binding between attributes is accomplished only by retaining the attributes themselves. We propose a theoretical account in which a fixed object capacity limit contains within it the possibility of the incomplete retention of object attributes, depending on the direction of attention.</p
Hardware Acceleration of BWA-MEM Genome Mapping Application
No full textNext Generation Sequencing technologies have had a tremendous impact on our understanding of DNA and its role in living organisms. The cost of DNA sequencing has decreased drastically over the past decade, leading the way for personalised genomics. Sequencers provide millions of fragments of DNA (termed short reads), which have to be aligned aginst a reference genome to reconstruct the full information of the DNA molecule under study. Processing short reads requires large computational resources, with many specialised computing platforms now being used to accelerate software aligners. We take up the challenge of accelerating a well know sequence alignment tool called Burrows Wheeler aligner on the Convey Hybrid Computing platform, which has FPGAs as co-processors. The focus of the research is to accelerate the BWA-MEM algorithm of the Burrows Wheeler aligner on the Convey HC-2 platform. The implementation was carried out using the Vivado HLS tool. The architectures proposed are targeted to overcome the memory bottleneck of the application. Two architectures are proposed, the Base architecture and the Batch architecture meant to address the memory bottle- neck. The architectures provide possibilities of further pipelining and implementation of more cores, which is expected to provide better performance than the current implementation.Computer EngineeringMicroelectronics & Computer EngineeringElectrical Engineering, Mathematics and Computer Scienc
- …
