The skyline is an optimization operator widely used for multi-criteria decision making. It allows minimizing an n-dimensional dataset into its smallest subset. In this work we present SkyFlow, the first heterogeneous CPU+GPU graph-based engine for skyline computation on a stream of data queries. Two data flow approaches, Coarse-grained and Fine-grained, have been proposed for different streaming scenarios. Coarse-grained aims to keep in parallel the computation of two queries using a hybrid solution with two state-of-the-art skyline algorithms: one optimized for CPU and another for GPU. We also propose a model to estimate at runtime the computation time of any arriving data query. This estimation is used by a heuristic to schedule the data query on the device queue in which it will finish earlier. On the other hand, Fine-grained splits one query computation between CPU and GPU. An experimental evaluation using as target architecture a heterogeneous system comprised of a multicore CPU and an integrated GPU for different streaming scenarios and datasets, reveals that our heterogeneous CPU+GPU approaches always outperform previous only-CPU and only-GPU state-of-the-art implementations up to 6.86×and 5.19×, respectively, and they fall below 6% of ideal peak performance at most. We also evaluate Coarse-grained vs Fine-Grained finding that each approach is better suited to different streaming scenarios.

The trend for heterogeneous embedded systems is the integration of accelerators and general-purpose CPU cores on the same die. In these integrated architectures, like the Zynq UltraScale+ board (CPU+FPGA) that we target in this work, hardware support for shared memory and low-overhead synchronization between the accelerator and the CPU cores make the case for exploring strategies that exploit a tight collaboration between the CPUs and the accelerator. In this paper we propose a novel lightweight scheduling strategy, FastFit, targeted to FPGA accelerators, and a new scheduler based on it, named MultiFastFit, which asynchronously tackles heterogeneous systems comprised of a variety of CPU cores and FPGA IPs. Our strategy significantly reduces the overhead to automatically compute the near-optimal chunksizes when compared to a previous state-of-the-art auto-tuned approach, which makes our approach more suitable for fine-grained applications. Additionally, our scheduler MultiFastFit has been designed to enable the efficient co-execution of work among compute devices in such a way that all the devices are busy while minimizing the load unbalance. Our approaches have been evaluated using four benchmarks carefully tuned for the low-power UltraScale+ platform. Our experiments demonstrate that the FastFit strategy always finds the near-optimal FPGA chunksize for any device configuration at a reasonable cost, even for fine-grained and irregular applications, and that heterogeneous CPU+FPGA co-executions that exploit all the compute devices are usually faster and more energy efficient than the CPU-only and FPGA-only executions. We have also compared MultiFastFit with other state-of-the-art scheduling strategies, finding that it outperforms other auto-tuned approach up to 2x and it achieves similar results to manually-tuned schedulers without requiring an offline search of the ideal CPU-FPGA partition or FPGA chunk granularity.

In this work, we study the problem of efficiently executing a state-of-the-art time series algorithm class – SCAMP – on a heterogeneous platform comprised of CPU + High Performance FPGA with integrated HBM (High Bandwidth Memory). The geometry of the algorithm (a triangular matrix walk) and the FPGA capabilities pose two challenges. First, several replicated IPs can be instantiated in the FPGA fabric, so load balance is an issue not only at system-level (CPU+FPGA), but also at device-level (FPGA IPs). And second, the data that each one of these IPs accesses must be carefully placed among the HBM banks in order to efficiently exploit the memory bandwidth offered by the banks while optimizing power consumption. To tackle the first challenge we propose a novel hierarchical scheduler named Fastfit, to efficiently balance the workload in the heterogeneous system while ensuring near-optimal throughput. Our scheduler consists of a two level scheduling engine: (1) the system-level scheduler, which leverages an analytical model of the FPGA pipeline IPs, to find the near-optimal FPGA chunk size that guarantees optimal FPGA throughput; and (2) a geometry-aware device-level scheduler, which is responsible for the effective partitioning of the FPGA chunk into sub-chunks assigned to each FPGA IP. To deal with the second challenge we propose a methodology based on a model of the HBM bandwidth usage that allows us to set the minimum number of active banks that ensure the maximum aggregated memory bandwidth for a given number of IPs. Through exhaustive evaluation we validate the accuracy of our models, the efficiency of our intra-device partition strategies and the performance and energy efficiency of our Fastfit heterogeneous scheduler, finding that it outperforms state-of-the-art previous schedulers by achieving up to 99.4% of ideal performance.

Heterogeneous chips that combine CPUs and FPGAs can distribute processing so that the algorithm tasks are mapped onto the most suitable processing element. New software-defined high-level design environments for these chips use general purpose languages such as C++ and OpenCL for hardware and interface generation without the need for register transfer language expertise. These advances in hardware compilers have resulted in significant increases in FPGA design productivity. In this paper, we investigate how to enhance an existing software-defined framework to reduce overheads and enable the utilization of all the available CPU cores in parallel with the FPGA hardware accelerators. Instead of selecting the best processing element for a task and simply offloading onto it, we introduce two schedulers, Dynamic and LogFit, which distribute the tasks among all the resources in an optimal manner. A new platform is created based on interrupts that removes spin-locks and allows the processing cores to sleep when not performing useful work. For a compute-intensive application, we obtained up to 45.56% more throughput and 17.89% less energy consumption when all devices of a Zynq-7000 SoC collaborate in the computation compared against FPGA-only execution.

The presentation of Table 2 was incorrect in the original article. The correct Table 2 is given below. The original article has been corr

In heterogeneous computing, efficient parallelism can be obtained if every device runs the same task on a different portion of the data set. This requires designing a scheduler which assigns data chunks to compute units proportional to their throughputs. For FPGA-CPU heterogeneous devices, to provide the best possible overall throughput, a scheduler should accurately evaluate the different performance behaviour of the compute devices. In this article, we propose a scheduler which initially detects the highest throughput each device can obtain for a specific application with negligible overhead and then partitions the dataset for improved performance. To demonstrate the efficiency of this method, we choose a Zynq UltraScale+ ZCU102 device as the hardware target and parallelise four applications showing that the developed scheduler can provide up to 94.06% of the throughput achievable at an ideal condition, with comparable power and energy consumption.

Ultra high density oligonucleotide microarrays allow several millions of genetic markers in a single experiment to be observed. Current bioinformatics software for gene expression quantile data normalization is unable to process such huge datasets. In parallel with this perception, the huge volume of molecular data produced by current high-throughput technologies in modern molecular biology has increased at a similar pace the challenge in our capacity to process and understand data. On the other hand, the arrival of CUDA has unveiled the extraordinary power of Graphics Processors (GPUs) to accelerate data intensive general purpose computing more and more as times goes by. This work takes these two emerging trends to benefit side by side during the development of a high performance version for a biomedical application of growing popularity: gene expression normalization. A variety of experimental issues are analyzed for this execution, including cost, performance and scalability of the graphics architecture on three different platforms. Our study reveals advantages and drawbacks of using the GPU as target hardware, providing lessons to benefit a broad set of existing genetic applications, either based on those pillars or having similarities with their procedures.

BACKGROUND: Microarray technology is generating huge amounts of data about the expression level of thousands of genes, or even whole genomes, across different experimental conditions. To extract biological knowledge, and to fully understand such datasets, it is essential to include external biological information about genes and gene products to the analysis of expression data. However, most of the current approaches to analyze microarray datasets are mainly focused on the analysis of experimental data, and external biological information is incorporated as a posterior process. RESULTS: In this study we present a method for the integrative analysis of microarray data based on the Association Rules Discovery data mining technique. The approach integrates gene annotations and expression data to discover intrinsic associations among both data sources based on co-occurrence patterns. We applied the proposed methodology to the analysis of gene expression datasets in which genes were annotated with metabolic pathways, transcriptional regulators and Gene Ontology categories. Automatically extracted associations revealed significant relationships among these gene attributes and expression patterns, where many of them are clearly supported by recently reported work. CONCLUSION: The integration of external biological information and gene expression data can provide insights about the biological processes associated to gene expression programs. In this paper we show that the proposed methodology is able to integrate multiple gene annotations and expression data in the same analytic framework and extract meaningful associations among heterogeneous sources of data. An implementation of the method is included in the Engene software package.

Abstract We present a novel application of knowledge discovery technology to a developing and challenging application area such as bioinformatics. This methodology allows the identification of relationships between low‐magnitude similarity (LMS) sequence patterns and other well‐contrasted protein characteristics, such as those described by database annotations. We start with the identification of these signals inside protein sequences by exhaustive database searching and automatic pattern recognition strategies. In a second step we address the discovering of association rules that will allow tagging sequences that hold LMS signals with consequent functional keywords. We have designed our own algorithm for discovering association rules, meeting the special necessities of bioinformatics problems, where the patterns we search lie in sparse datasets and are uncommon and thus difficult to locate. Computational efficiency has been verified both with synthetic and real biological data showing that the algorithm is well suited to this application area compared to state of the art algorithms. The usefulness of the method is confirmed by its ability to produce previously unknown and useful knowledge in the area of biological sequence analysis. In addition, we introduce a new and promising application of the rule extraction algorithm on gene expression databases.

We present a video content analysis and metadata organizational system for research videos arising from biological microscopy of living cells. Automated procedures are described to determine the position, size, shape and orientation of cells in each video frame. From the temporal changes in the values of these simple metadata parameters, high-level descriptors are derived that describe the semantic content of the video. This content information (specific intrinsic metadata) is of high information value, since it describes the behavior of cells and the timing of events within the video, including changes in environmental conditions experienced by the cells. When such metadata are properly organized in a searchable database, a content-based video query and retrieval system may be developed to locate particular objects, events or behaviors. Moreover, the availability of such semantic contents in the formal and generic format we propose will allow the application of data mining techniques and the amassing of more elaborate knowledge, e.g., species classification depending on behavior, patterns in response to environment changes, etc. The suitability and functionality of the proposed metadata model is demonstrated by the automated analysis of five different types of biological experiments, recording epithelial wound healing, bacterial multiplication, the rotations of tethered bacteria, and the swimming of motile bacteria and of human sperm.

We present a video analysis and content-based video query and retrieval system for research videos arising from biological microscopy that: (a) uses image processing procedures to identify objects and events automatically within the digitized videos, thus leading to the generation of content information (specific intrinsic metadata) of high information value by automated analysis of their visual content; and (b) permits subsequent queries to be performed on the specific intrinsic metadata thus generated, allowing important factual and analytical information to be obtained and selected video sequences matching the query criteria to be retrieved. Such a system requires the novel use of image and video processing techniques, and new approaches to the organization, accessing and querying of video metadata databases.