We present several algorithms to generate tables for asymmetric numeral systems and prove that they are optimal in terms of discrepancy. In turn, this gives rise to the strongest proven bound on entropy loss. We further give improved theoretical bounds for the entropy loss in tabled asymmetric numeral systems and a brief empirical evaluation of the stream variant.

FPGAs play an increasing role in the reconfigurable accelerator landscape. A key challenge in designing FPGA-based systems is partitioning computation between processor cores and FPGAs. An appropriate division of labor is difficult to predict in advance and requires experiments and measurements. When an investigation requires rewriting part of the system in a new language or with a new programming model, its high cost can delay design-space exploration. A single-language system with an appropriate programming model and compiler that targets both platforms transforms this tedious exploration to a simple recompile with new compiler directives.

Hardware-software codesign for FPGAs requires flexible and changeable boundaries between hardware and software. Design space exploration is facilitated by expressing programs in a language that can be compiled for both CPU and FPGA execution. Such an approach requires efficient and general communication mechanisms between hardware and software. We present a practical solution to this problem for heterogeneous programs expressed in CAL, an actor based language running on a PCIe-based FPGA system where communication between a processor and FPGA is relatively expensive. We show how a network of continuously executing software and hardware actors with fine-grained communication can be expressed as a coprocessor model that executes the network in discrete steps with efficient coarse-grained transfers across the PCIe bus.

The use of parallelism has increased drastically in recent years. Parallel platforms come in many forms: multi-core processors, embedded hybrid solutions such as multi-processor system-on-chip with reconfigurable logic, and cloud datacenters with multi-core and reconfigurable logic. These heterogeneous platforms can offer massive parallelism, but it can be difficult to exploit, particularly when combining solutions constructed with multiple architectures. To program a heterogeneous platform, a developer must master different programming languages, tools, and APIs to program each aspect of platform separately and then must find a means to connect them with communication interfaces. The motivation of this work is to provide a single programming model and framework for hardware-software stream programs on heterogeneous platforms. Our framework, StreamBlocks, starts with a dataflow programming model for both embedded and datacenter platforms. Dataflow programming is an alternative model of computation that captures both data and task parallelism. We describe a compiler infrastructure for CAL dataflow programs for hardware code generation. CAL is a dataflow programming language that can express multiple dataflow models of computation. StreamBlocks is based on the Tycho compiler infrastructure, which transforms each actor in a dataflow program to an abstract machine model, called Actor Machine. Actor Machines provides a unified model for executing actors in both hardware and software and permit our compiler extension and backend to generate efficient FPGA code. Unlike other systems, the programming model and compiler directly support hardware-software systems in which an FPGA functions as a coprocessor to a CPU. This permits easy integration with existing workflows.

In recent years, the number and variety of heterogeneous multiprocessor system-on-chip MPSoCs, such as for instance Zynq platforms, has sensibly increased. However, today all design flow solutions capable of programming the different components of such platforms require to the designer either to modify the software or hardware based designs to obtain higher performance implementations. Thus, the developer needs to either rewrite functional blocks in HDL or to use high-level synthesis of C-like sequential languages with platform locked extensions. In this paper, a compiler infrastructure that takes as input a single behavioral representation, expressed in high-level dataflow RVC-CAL language, is proposed for programming any of the components of heterogeneous Zynq MPSoCs platforms without the need of modifying any line of code on the design.

The rapid detection and identification of infectious pathogens are a critical need for healthcare in both developed and developing countries. There is a need for portable diagnostics and epidemiological surveillance systems that can be deployed in remote field settings for infectious diseases testing, such as pandemic "hotspots" in Africa or southeast Asia. Together with the Vital-IT and Swiss-Prot groups, we developed a fast pathogen detection embedded hardware accelerator (no bigger than 75x50mm) capable of analyzing up to 250Mnt/s of DNA sequence. To deploy this solution, an embedded DNA Next Generation Sequencer (NGS) is used for retrieving the genetic material from patient's sample at the point of care (e.g., the Oxford Nanopore Technologies MinION). Successively, the collected DNA sequences are analized in order to detect the presence of known pathogen patterns. Currently, up to 100 different pathogens can be analized at the same time using one single embedded accelerator. Due to the low-power consumption of this hardware accelerator, it is possible to give access to worldwide health organizations and local administrations to a complete real-time embedded and battery powered surveillance solution. Moreover, this solution can greatly scale to big computing clusters, where a larger pathogens number can be analized in parallel, outperforming current state of art computationally expensive solutions.

The paper presents the results of design explorations for the implementation of the Smith-Waterman (S-W) algorithm executing DNA and protein sequences alignment. Both design explorations studies and the corresponding FPGA implementations are obtained by writing a dynamic dataflow program implementing the algorithm and by direct high-level synthesis (HLS) to FPGA HDL. The main feature of the obtained implementation is a low-latency, pipelinable multistage processing element (PE), providing a substantial decrease in the resource utilization and an increase in the computation throughput when compared to state of the art solutions. The implementation solution is also fully scalable and can be efficiently reconfigured according to the DNA sequence sizes and to system performance requirements. The FPGA design presented in the paper can efficiently scale up to 250 MHz obtaining 14746 Alignments/s using a single S-W core with 4 PEs, and up to 31.8 Mega-Alignments/min using 36 S-W cores on the same FPGA for sequences of 160×100 nucleotides.

This paper investigates the reduction of dynamic power for streaming applications yielded by asynchronous dataflow designs by using clock gating techniques. Streaming applications constitute a very broad class of computing algorithms in areas such as signal processing, digital media coding, cryptography, video analytics, network routing, packet processing, etc. This paper introduces a set of techniques that, considering the dynamic streaming behavior of algorithms, can achieve power savings by selectively switching off parts of the circuits when they are temporarily inactive. The techniques being independent from the semantic of the application can be applied to any application and can be integrated into the synthesis stage of a high-level dataflow design flow. Experimental results of at-size applications synthesized on field-programmable gate arrays platforms demonstrate power reductions achievable with no loss in data throughput.

This paper introduces a new methodology for pipeline synthesis with applications to data flow high-level system design. The pipeline synthesis is applied to dataflow programs whose operators are translated into graphs and dependencies relations that are then processed for the pipeline architecture optimization. For each pipeline-stage time, a minimal number of pipeline stages are first determined and then an optimal assignment of operators to stages is generated with the objective of minimizing the total pipeline register size. The obtained “optimal” pipeline schedule is automatically transformed back into a dataflow program that can be synthesized to efficient hardware implementations. Two new pipeline scheduling: “least cost search branch and bound” and a heuristic technique have been developed. The first algorithm yields global optimum solutions for middle size designs, whereas the second one generates close-to-optimal solutions for large designs. Experimental results on FPGA designs show that the total pipeline register size gain in a range up to 4.68× can be achieved. The new algorithms overcome the known downward and upward direction dataflow graph traversal algorithms concerning the amount of pipeline register size by up to 100% on average.

This paper describes and demonstrates a tool chain which enables HW-SW co-synthesis from a single high-level dataflow program. This toolchain does not only enable rapid-prototyping of complex designs, but also provides a complete system integration framework including synthesis of SW-HW interconnect. This framework minimizes the designer efforts for a low level implementation. A co-design example of a JPEG codec is demonstrated using a high-level dataflow language, named CAL.