1,720,957 research outputs found
Acceleration of the Chan-Vese model for 3D segmentation of tumors in CT scans using GPUs
No full textSegmentation and annotation of tumors in CT scans of the brain is a cumbersome time-consuming task for medical experts. Carefully annotated data can be used to build training data sets for machine learning frameworks, with the ultimate goal to fully automate this process. This thesis focuses on acceleration of the annotation process by implementation of an interactive accelerated segmentation model rather than implementation or evaluation of the machine learning part. The Chan-Vese model is an active contour model which can be used to detect objects for which the boundaries are not necessarily defined by gradient. An energy functional is minimized by evolvement of the contour. Evolvement of the contour in a numerical approximation, which uses finite differences and a level set formulation, is determined by solving a Partial differential equation (PDE) with an iterative solver. This thesis presents implementations for both 2D and 3D which use Successive over-relaxation (SOR) to solve the PDE. This computationally intensive task benefits from acceleration to keep the feedback loop, in the process of tuning parameters and convergence to the searched segmentation, as short as possible. The effect of varying the different parameters of the model are visualized for different examples images to allow for educated guesses. Accelerated implementations which leverage Compute Unified Device Architecture (CUDA) on a Graphics processing unit (GPU) are presented and compared to sequential and multithreaded OpenMP implementations. Evaluation of the CUDA implementations with single precision on a POWER8 platform with a K40 GPU shows a speedup of 56 and 107 over sequential implementations for 2D and 3D respectivelyComputer EngineeringComputer EngineeringElectrical Engineering, Mathematics and Computer Scienc
Acceleration of read alignment with coherent attached FPGA coprocessors
No full textWith the advent of Next Generation Sequencing (NGS), the cost of sequencing human DNA has decreased significantly over the past decade. This decrease in cost has attracted a great deal of attention from medical research and is now transitioning to clinical practice. Precision medicine, tailored to a persons's genetic profile, is becoming a viable option in the battle against cancer and rare genetic diseases. NGS sequencers produce millions of small fragments of DNA called reads. Mapping those reads to a reference genome proves to be a tremendous computational task and forms the bottleneck in current DNA analysis flows. BWA-MEM, a state-of-the-art alignment tool, applies the seed and extend paradigm to rapidly align the reads with a reference genome. The Smith-Waterman (S-W) algorithm is widely adopted by these state-of-the-art aligners. We have identified the S-W algorithm to be the main computational bottleneck on IBM's POWER8 processor. This recently released processor includes a new Coherent Accelerator Processor Interface (CAPI), that provides cache coherent access to shared memory for heterogeneous processors. We present a highly parallel FPGA-based accelerator that offloads the Smith-Waterman task. We have integrated the accelerator with software, relying on CAPI, in a tightly coupled fashion. This integrated heterogeneous system is able to achieve a speedup of 1.6X over purely software-based multithreaded execution of BWA-MEM. Furthermore, we propose a more general framework for dividing workload between the processor and accelerator in a fine-grained manner. We expect to achieve the maximum obtainable speedup (bounded by Amdahl's law) of 2X with the proposed framework.Computer EngineeringMicroelectronics & Computer EngineeringElectrical Engineering, Mathematics and Computer Scienc
Evaluation of different storage systems for Apache Spark and Apache Hadoop
No full textBig Data systems have been used for multiple years to solve problems that require scale. A framework takes care of scalability and resiliency issues, and allows the user to focus on relevant computation, in the form of map and reduce functions. In these Big Data systems, we currently see a shift from the traditional use of the Hard Disk Drive (HDD) towards in-memory computation. In this thesis, we have theoretically evaluated these two generations of Big Data systems, as well as two implementations, being Apache Hadoop and Apache Spark, in combination with Flash technology. We have also evaluated the possible use of Flash technology in these Big Data sys- tems, by performing two experiments. Our first experiment exam- ined the performance of Apache Spark versus Apache Hadoop for a representative iterative algorithm, and the performance degradation of Apache Spark under memory constrains. We have found that, for the chosen algorithm, Apache Spark performs equal-or-better compared to Apache Hadoop when data has to be loaded from the HDD, such as is the case of the initialization phase of a program. For the iterative part of our program, we have seen an overall speedup of 30, and a speedup of 100 for the map and reduce phases. In our second experiment, we evaluated two ways of using Flash, in particular using the IBM FlashSystem 840 connected to a Power8, in Apache Spark. We have first evaluated Flash technology with a mounted file system, and used this setup to replace the HDD as default spill loca- tion. We have found that this was not valuable, as the possible performance improvements were negligible compared to the overhead generated by data aggregation and system calls. We then shifted our focus to CAPI connected Flash, and modified Apache Spark to spill intermediate data directly to the FlashSystem using key value pairs. In our experiment, while limiting the memory to a fixed amount to force spilling, we were able to remove 70% of the overhead caused by spilling. This was mainly overhead of Operating System (OS) involvement. In our future work, we will address the overhead caused by data aggregation, as we can write smaller amounts of data, because we are writing in key value pairs. We believe that, once this overhead is removed, Big Data systems can benefit from Flash technology, and especially CAPI Flash technology, as one can use a system with a limited amount of expensive DRAM and a large Flash backend, to solve larger problem sets while maintaining a performance equal to in-memory computation.Embedded SystemsComputer EngineeringElectrical Engineering, Mathematics and Computer Scienc
Methods for Efficient Integration of FPGA Accelerators with Big Data Systems
No full textBecause of fundamental limitations of CMOS technology, computing researchers and the computing industry are focusing on using transistors in integrated circuits more efficiently towards obtaining a computational goal. At the architectural level, this has led to an era of heterogeneous computing, where various types of computational components are used to solve problems. In this dissertation, we focus on the integration of one such heterogeneous component; the FPGA accelerator, with one of the main drivers behind the increasing need of computational performance; big data systems. With the increased availability of these FPGA accelerators in data centers and clouds, and with an increasing amount of I/O bandwidth between accelerated systems and their host, the industry is trying to push these components into more widespread usage in big data applications. For big data systems, three related challenges are observed. First, the software systems consist of many layered run-time systems that have often been designed to raise the level of abstraction, often at the cost of potential performance. Second, hardware-unfriendly in-memory data structures, and (to the accelerator) uninteresting metadata may convolute designs required to integrate FPGA accelerators with big data systems software. Last, serialization is applied to face the second challenge, but the rate at which serialization is performed is much lower than the rate at which accelerators may absorb data. For FPGA accelerators, we also observe three challenges. First, highly vendor-specific styles of designing hardware accelerators hampers the widespread reuse of existing solutions. Second, developers spend a lot of time on designing interfaces appropriate for their data structure, since they are typically provided with just a byte-addressable memory interface. Third, developers spend a lot of time on the infrastructure or ‘plumbing’ around their computational kernels, while their focus should be the kernel itself. We describe a toolchain named Fletcher, based on the Apache Arrow in-memory format for tabular data structures, that uses Arrow to deal with the challenges on the big data systems software side, and also deals with the challenges on the FPGA accelerator development side. The toolchain allows to rapidly generate platform-agnostic FPGA accelerator designs where kernels operate on tabular data sets, requiring the developer to only implement the kernel, automating all other aspects of the design, including hardware interfaces, hardware infrastructure, and software integration. We describe applications in regular expression matching, k-means clustering, Hidden Markov Models with the posit numeric format, and decoding Parquet files. We finally apply the lessons learned on the work of the Fletcher framework in a new interface specification for streaming dataflow designs, named Tydi. We introduce a hardware-oriented type system that allows to express complex, dynamically sized data structures often found in the domain of big data analytics. The type system helps to increase the productivity when designing hardware transporting such data structures over streams, abstracting their use in hardware without losing the ability to make common design trade-offs.Computer Engineerin
An FPGA-based Snappy Decompressor-Filter
No full textNew interfaces to interconnect CPUs and accelerators at memory-class bandwidth pose new opportunities and challenges for the design of accelerators. This thesis studies one such accelerator, a decompressor for Parquet files compressed with the Snappy library. Our design targets reconfigurable logic (FPGAs) attached via the open coherent accelerator processor interface(OpenCAPI) at 25.6GB/s. We give an overview of the previous research in hardware-based (de)compression engines and present and analyze our design. Much of the challenge of designing the decompression engine stems from the need to process more than one token per cycle. In our design, a single engine can process two tokens per cycle. A Xilinx KU15P FPGA is expected to support multiple such engines. The input throughput and the output throughput ranges of a single engine are 3.96.3 bytes/cycle and 8.315 bytes/cycle, respectively. Based on the implementation results, a single engine of the proposed design could work at 140MHz, meaning 0.510.82 GB/s input throughput or 1.081.96 GB/s output throughput. The Parquet format enables the parallel decompression of multiple blocks when multiple units are instantiated. With the latest generation of FPGAs, we estimate at most 28 units can be supported leading to a total input/output bandwidth of 14.28/30.24 to 22.96/54.88 GB/s. Because the output bandwidth can exceed the interface bandwidth if multiple engines are supported, the design is especially effective when combined with a filter engine that reduces the output size.Electrical Engineering | Microelectronic
Multi-way Hash Join Based on FPGAs
No full textThe multi-way hash join is one of the commonly used and time-consuming database operations. Many algorithms have been developed to accelerate this operation, some of which use accelerators such as field programmable gate arrays (FPGAs). However, most of the previous work was focused on computation-intensive operations such as (de)compression, because the interface between the FPGA and the host can only provide relatively low bandwidth.\parHowever, new generation high-bandwidth, low-latency interfaces to interconnect host processors and accelerators such as the open coherent accelerator processor interface(OpenCAPI) provide FPGAs with new opportunities to accelerate database operations. In this thesis, we explore the potential of using OpenCAPI-attached FPGAs to accelerate multi-way joins. Via the OpenCAPI, the FPGA can obtain a high-bandwidth communicating with CPUs and the main memory at 25.6GB/s. We first investigate the previous research in software-based multi-way joins and observe that this operation is limited by the bandwidth of main memory. Thus, the main challenge of designing the accelerator emerges as avoiding unnecessary memory accesses. We partition the build relations into the size that can build a hash table in Block RAMs (BRAMs), and avoid multiple-pass memory accesses. In our design, the intermediate join phase is pipelined with a partition phase to reduce the size of the intermediate results. The proposed design is configurable for the attached bandwidth, and it can achieve a throughput of 5 GB/s when a 25.6 GB/s bandwidth is provided.Electrical Engineering | Microelectronic
High-Performance Cluster-Scalable Computational Methods for Genomics Applications
No full textThe ever increasing pace of advancements in sequencing technologies has enabled rapid DNA/genome sequencing to become much more accessible. In particular, next (second) and third generation sequencing technologies offer high throughput, massively parallel and cost effective sequencing solutions. Individual sample sequencing data volumes as well as the number of assembled genomes are also growing quickly. These advances in high throughput sequencing technologies and demand for fast computational processing and downstream analysis of sequencing data in clinical settings is widening the gap between the time spent in sample collection and sequencing versus computational analysis. To improve the scalability and performance optimizations of genome variant calling analysis workflows on modern computing systems, in this dissertation four potential research directions have been selected for further exploration. First, to exploit the performance of modern processors hardware features like multi-core and vector units on the GATK best practices variant calling pipelines, we introduce ArrowSAM, a columnar inmemory data format to place and process genomics data in-memory thus removing the need for repeated file storage accesses in intermediate variant calling pipeline applications. Our second contribution focuses on integration of the Apache Arrow based columnar in-memory data format in the PySpark API to enable exploiting the benefits of vectorized operations in the Python language using user-defined functions on Spark dataframes. For our third research contribution, we tested and benchmarked both the scalability and performance of Arrow Flight for client-server as well as cluster scaled communication.For our final research contribution reported in this dissertation, we implemented an orthogonal approach that is even more scalable than Apache Spark and Arrow Flight based solutions and offers flexibility to use many different variant callers.Computer Engineerin
Tydi-lang: a language for typed streaming hardware: A manual for future Tydi-lang compiler developers
No full textTransferring composite data structures with variable-length fields often requires designing non-trivial protocols that are not compatible between hardware designs. When each project designs its own data format and protocols the ability to collaborate between hardware developers is diminished, which is an issue especially in the open-source community. Because the high-level meaning of a protocol is often lost in translation to low-level languages when a custom protocol needs to be designed, extra documentation is required, the interpretation of which introduces new opportunities for errors. The Tydi specification (Tydi-spec) was proposed to address the above issues by codifying the composite and variable-length data structures in a type and providing a standard protocol to transfer typed data among hardware components. The Tydi intermediate representation (Tydi-IR) extends the Tydi-spec by defining typed interfaces, typed components, and connections among typed components.In this paper, we propose Tydi-lang, a high-level hardware description language (HDL) for streaming designs. The language incorporates Tydi-spec to describe typed streams and provides templates to describe abstract reusable components. We also implement an open-source compiler from Tydi-lang to Tydi-IR. We leverage a Tydi-IR to VHDL compiler, and also present a simulator blueprint to identify streaming bottlenecks. We show several Tydi-lang examples to translate high-level SQL to VHDL to demonstrate that Tydi-lang can efficiently raise the level of abstraction and reduce design effort.https://github.com/twoentartian/tydi-lang Source code for the thesis project.Computer Scienc
Database Acceleration on FPGAs
No full textThough field-programmable gate arrays (FPGAs) have been used to accelerate database systems, they have not been widely adopted for the following reasons. As databases have transitioned to higher bandwidth technology such as in-memory and NVMe, the communication overhead associated with accelerators has become more of a burden. Also, FPGAs are more difficult to program, and GPUs have emerged as an alternative technology with better programming support. However, with the development of new interconnect technology, memory technology, and improved FPGA design tool chains, FPGAs again provide significant opportunities. Therefore, we believe that FPGAs can be attractive again in the database field. This thesis focuses on FPGAs as a high-performance compute platform, and explores using FPGAs to accelerate database systems. It investigates the current challenges that have held FPGAs back in the database field as well as the opportunities resulting from recent technology developments. The investigation illustrates that FPGAs can provide significant advantages for integration in database systems. However, to make further progress, studies in a number of areas, including new database architectures, new types of accelerators, deep performance analysis, and the development of the tool chains are required. Our contributions focus on accelerators for databases implemented in reconfigurable logic. We provide an overview of prior work and make contributions to two specific types of accelerators: both a compute-intensive (decompression) and a memory-intensive (hash join) accelerator.SIKS Dissertation Series No. 2019-37Computer Engineerin
Algorithms for Efficient Inference in Convolutional Neural Networks
No full textIn recent years, the accuracy of Deep Neural Networks (DNNs) has improved significantly because of three main factors: the availability of massive amounts training data, the introduction of powerful low-cost computational resources, and the development of complex deep learning models. The cloud can provide powerful computational resources to calculate DNNs but limits their deployment due to data communication and privacy issues. Thus, computing DNNs at the edge is becoming an important alternative to calculating these models in a centralized service. However, there is a mismatch between the resource-constrained devices at the edge and the models with increased computational complexity. To alleviate this mismatch, both the algorithms and hardware need to be explored to improve the efficiency of training various feedforward and recurrent neural networks and inferring using a DNN.Computer Engineerin
- …
