Genome assembly is a field of bioinformatics which refers to the process of taking small fragments of genetic material and putting them back together in order to reconstruct the original DNA sequence from which the fragments originated. As the DNA genome assembly input datasets in most cases have a very large amount of data, it is important to develop custom architectures in order to speed up these processes and gain significant execution time reduction. In this paper we present the Reads Matching Filter (RMF), an input dataset prefiltering process, based on string matching and implemented on Field Programmable Gate Array (FPGA) technology, in order to reduce the genome assembly execution time. The outputs of the RMF running on the FPGA as well as the original input dataset are given as input to the Velvet genome assembler which produces the assembly of the input sequences. The Velvet genome assembler is based on the manipulation of de Bruijn graphs, and produces its output via the removal of errors and the simplication of repeated regions. The FPGA-based RMF pre-filtering process manages to speedup the entire genome assembly processing, including I/O, by up to 6 times, while maintaining the quality of the output sequence contigs (i.e. the series of overlapping DNA sequences).

Aquaculture faces the issue of net integrity on cage farming. Holes on the net need to be detected but as yet the process is not fully automated. This work is a second-generation embedded system to detect in real time holes in aquaculture nets from a video input. It extends previous results by processing video rather than still images, under lighting variation, haze, and different size of holes along each frame. The modeling and simulation of the new algorithm has been done in MATLAB; the system has been designed and implemented on a Field Programmable Gate Array (FPGA) - based platform. The proposed system has substantially better performance vs. software at a much lower energy consumption.

The Phylogenetic Likelihood Function (PLF) is one of the cornerstone functions in most phylogenetic inference tools; its execution represents the majority of time required to complete an analysis. This work proposes the acceleration of this function using reconfigurable hardware accelerators, focusing on system-on-chips that integrate Field Programmable Gate Array (FPGA) resources as well as traditional High Performance Computing (HPC) systems that use FPGA-based accelerator cards. Taking into account the specific properties of each platform in order to exploit their processing capabilities, the proposed solutions provide significant performance gains. The measured acceleration of PLF function is up to 8x while the overall time to complete a phylogenetic analysis using the popular RAxML software can be reduced up to 3.2 times (with respect to a pure software implementation on a high-end server processor). Compared to other similar solutions proposed in literature, our systems perform up to 65% faster.

In an era of complex networked parallel heterogeneous systems, simulating independently only parts, components, or attributes of a system-under-design is a cumbersome, inaccurate, and inefficient approach. Moreover, by considering each part of a system in an isolated manner, and due to the numerous and highly complicated interactions between the different components, the system optimization capabilities are severely limited. The presented fully-distributed simulation framework (called as COSSIM) is the first known open-source, high-performance simulator that can handle holistically system-of-systems including processors, peripherals and networks; such an approach is very appealing to both Cyber Physical Systems (CPS) and Highly Parallel Heterogeneous Systems designers and application developers. Our highly integrated approach is further augmented with accurate power estimation and security sub-tools that can tap on all system components and perform security and robustness analysis of the overall system under design—something that was unfeasible up to now. Additionally, a sophisticated Eclipse-based Graphical User Interface (GUI) has been developed to provide easy simulation setup, execution, and visualization of results. COSSIM has been evaluated when executing the widely used Netperf benchmark suite as well as a number of real-world applications. Final results demonstrate that the presented approach has up to 99% accuracy (when compared with the performance of the real system), while the overall simulation time can be accelerated almost linearly with the number of CPUs utilized by the simulator.

Cellular automata (CA) are discrete mathematical models discovered in the 1940s by John von Neumann and Stanislaw Ulam and have been used extensively in many scientific disciplines ever since. The present work evolved from a Field Programmable Gate Array– (FPGA) based design to simulate urban growth into a generic architecture that is automatically generated by a framework to efficiently compute complex cellular automata with large 29 × 29 neighborhoods in Cartesian or toroidal grids, with 16 or 256 states per cell. The new architecture and the framework are presented in detail, including results in terms of modeling capabilities and performance. Large neighborhoods greatly enhance CA modeling capabilities, such as the implementation of anisotropic rules. Performance-wise, the proposed architecture runs on a medium-size FPGA up to 51 times faster vs. a CPU running highly optimized C code. Compared to GPUs the speedup is harder to quantify, because CA results have been reported on GPU implementations with neighborhoods up to 11 × 11, in which case FPGA performance is roughly on par with GPU; however, based on published GPU trends, for 29 × 29 neighborhoods the proposed architecture is expected to have better performance vs. a GPU, at one-10th the energy requirements. The architecture and sample designs are open source available under the creative commons license.

Traditional data management systems map information using centralized and static data structures. Modern applications need to process in real time datasets much larger than system memory. To achieve this, they use dynamic entities that are updated with streaming input data over a sliding window. For efficient and high performance processing, approximate sketch synopses of input streams have been proposed as effective means for the summarization of streaming data over large sliding windows with probabilistic accuracy guarantees. This work presents a system-level solution to accelerate the Exponential Count-Min (ECM) sketch algorithm on reconfigurable technology. Different reconfigurable architectures for the sketch structure that correspond to different cost and performance tradeoffs are presented. We map the proposed system-level ECM sketch architectures to a high-end modern HPC platform to achieve guaranteed and best-effort update rates up to 150 and 180 million tuples per second respectively. We compare the performance of the implemented system against the best optimized multi-thread software alternative and show that our scalable full-system accelerators outperform software solutions by 5-7.5x for Virtex6 devices and in excess of 10x for current Ultrascale devices.

In this paper we present a reconfigurable logic-based parallel architecture for the computation of 29X29 large-neighborhood cellular automata at 60 frames-per-second (FPS) real time update rate, using a small FPGA. The computation for each one of the n2elements of a two-dimensional input is O(k2), where k is the size of the neighborhood in each dimension. All buffering and computation is performed internally in the FPGA. In terms of performance results, our architecture outperforms a general-purpose CPU running highly optimized software programmed in C by up to 51×; in neighborhoods up to 11×11 in which there are published results from GPUs our architecture has similar performance to GPUs at one-tenth the energy requirements, however, our architecture has the same performance for 29×29 neighborhoods whereas GPU performance drops as neighborhood grows. We expect this work to provide enabling new tools for the use of cellular automata models in the physical sciences.

Convolutional Neural Networks (CNNs) represent the cutting edge in signal analysis tasks like classification and regression. Realization of such architectures in hardware capable of performing high throughput computations, with minimal energy consumption, is a key enabling factor towards the proliferation of analysis immediately after acquisition. Our driving problem is a satellite-based remote sensing platform in which onboard signal processing and classification tasks must take place, given strict bandwidth and energy limitations. In this work, we exploit the implementation of a CNN on Field Programmable Gate Array (FPGA) platforms and explore different ways to minimize the impact of different hardware restrictions to performance. We compare our results against competing technologies such as Graphics Processing Units (GPU) in terms of throughput, latency and energy consumption. In actual experimental runs we demonstrate competitive latency and throughput of the FPGA platform vs. GPU technology at an order-of-magnitude energy savings, which is especially important for space-borne computing.

In this paper, we present an open-source Cyber Physical Systems (CPS) simulation framework that aims to address the limitations of currently available tools. Our solution models the computing devices of the processing nodes and the network that comprise the CPS system and thus provides cycle accurate results, realistic communications and power/energy consumption estimates based on the actual dynamic usage scenarios. The simulator provides the necessary hooks to security testing software and can be extended through an IEEE standardized interface to include additional tools, such as simulators of physical models.

Neuromorphic computing is expanding by leaps and bounds through custom integrated circuits (digital and analog), and large scale platforms developed by industry or government-funded projects (e.g. TrueNorth and BrainScaleS, respectively). Whereas the trend is for massive parallelism and neuromorphic computation in order to solve problems, such as those that may appear in machine learning and deep learning algorithms, there is substantial work on brain-like highly accurate neuromorphic computing in order to model the human brain. In such a form of computing, spiking neural networks (SNN) such as the Hodgkin and Huxley model are mapped to various technologies, including FPGAs. In this work, we present a highly efficient FPGA-based architecture for the detailed hybrid Leaky Integrate and Fire SNN that can simulate generic characteristics of neurons of the cerebral cortex. This architecture supports arbitrary, sparse O(n2) interconnection of neurons without need to re-compile the design, and plasticity rules, yielding on a four-FPGA Convey 2ex hybrid computer a speedup of 923x for a non-trivial data set on 240 neurons vs. the same model in the software simulator BRAIN on a Intel(R) Xeon(R) CPU E5-2620 v2 @ 2.10GHz, i.e. the reference state-of-the-art software. Although the reference, official software is single core, the speedup demonstrates that the application scales well among multiple FPGAs, whereas this would not be the case in general-purpose computers due to the arbitrary interconnect requirements. The FPGA-based approach leads to highly detailed models of parts of the human brain up to a few hundred neurons vs. a dozen or fewer neurons on the reference system.

The ever-increasing genomic dataset sizes, fueled by continuous advances in DNA sequencing technologies, are expected to bring new scientific achievements in several fields of biology. The fact that the demand for higher sequencing throughput has long outpaced Moore's law, however, presents a challenge for the efficient analysis of future large-scale datasets, suggesting the urgent need for custom solutions to keep up with the current trend of increasing sample sizes. In this work, we focus on a widely employed, yet prohibitively compute- and memory-intensive, measure that is called linkage disequilibrium (LD), defined as the non-random association between alleles. Modern microprocessor architectures are not well equipped to deliver high performance for LD due to the lack of a vectorized population counter (counting set bits in registers). We present a modular and highly parallel reconfigurable architecture that, in combination with a generic memory layout transform, allows to rapidly conduct large-scale pairwise calculations on arbitrarily large one- and two-dimensional binary vectors, exhibiting increased bit-counting capacity. We map the proposed architecture to all four reconfigurable devices of a multi-FPGA platform, and deploy them synergistically for the evaluation of LD on genomic datasets with up to 1,000,000 sequences, achieving between 12.7X (4 FPGAs vs. 12 cores) and 134.9X (4 FPGAs vs. 1 core) faster execution than state-of-the-art reference software running on multi-core workstations. For real-world analyses that employ LD, such as scanning the 22nd human chromosome for traces of positive selection, the proposed system can lead to 6X faster processing, thus enabling more thorough genome-wide scans.

Stream join is a fundamental and computationally expensive data mining operation for relating information from different data streams. This paper presents two FPGA-based architectures that accelerate stream join processing. The proposed hardware-based systems were implemented on a multi-FPGA hybrid system with high memory bandwidth. The experimental evaluation shows that our proposed systems can outperform a software-based solution that runs on a high-end, 48-core multiprocessor platform by at least one order of magnitude. In addition, the proposed solutions outperform any other previously proposed hardware-based or software-based solutions for stream join processing. Finally, our proposed hardware-based architectures can be used as generic templates to map stream processing algorithms on reconfigurable logic, taking into consideration real-world challenges and restrictions.

Stream join is a fundamental operation that combines information from different high-speed and high-volume data streams. This paper presents an FPGA-based architecture that maps the most performance-efficient stream join algorithm, i.e. ScaleJoin, to reconfigurable logic. The system was fully implemented on a Convey HC-2ex hybrid computer and the experimental performance evaluation shows that the proposed system outperforms by up to one order of magnitude the corresponding fully optimized parallel software-based solution running on a high-end 48-core multiprocessor platform. The proposed architecture can be used as a generic template for mapping stream processing algorithms to reconfigurable logic, taking into consideration real-world challenges.

Graph mining is an important research area within the domain of data mining. One of the most challenging tasks of graph mining is frequent subgraph mining. This work presents the first FPGA-based implementation, to the best of our knowledge, of the most efficient and well-known algorithm for the Frequent Subgraph Mining (FSM) problem, i.e. gSpan. The proposed system, named High Performance Computing-gSpan (HPC-gSpan), achieves manyfold speedup vs. the official software solution of the gboost library when executed on a high-end CPU for various real-world datasets.

The implementation of low-cost 3D Stereo Vision systems requires stereo matching algorithms. Various efforts have been reported in the literature, however, these systems require substantial hardware resources. The contribution of the present work is on a low-cost real-time system, which was fully implemented on a small Xilinx FPGA. The system presented in this work extends previous results of the authors through design space exploration, architecture improvements and careful problem sizing.

Many applications from autonomous vehicles to surveillance can benefit from real-time 3D stereo vision. In the present work we describe a 3D stereo vision design and its implementation that exploits effectively the resources of a Xilinx Virtex-5 FPGA. The post place-and-route design achieved a processing rate of 87 frames per sec (fps) for 1920 × 1200 resolution. The hardware prototype system was tested and validated for several data sets with resolutions up to 400 × 320 and we achieved a processing rate of 1570 fps.

Data mining is a new field of computer science with a wide range of applications. Its goal is to extract knowledge from massive datasets in a human-understandable structure, for example, the decision trees. In this article we present an innovative, high-performance, system-level architecture for the Classification And Regression Tree (CART) algorithm, one of the most important and widely used algorithms in the data mining area. Our proposed architecture exploits parallelism at the decision variable level, and was fully implemented and evaluated on a modern high-performance reconfigurable platform, the Convey HC-1 server, that features four FPGAs and a multicore processor. Our FPGA-based implementation was integrated with the widely used “rpart” software library of the R project in order to provide the first fully functional reconfigurable system that can handle real-world large databases. The proposed system, named HC-CART system, achieves a performance speedup of up to two orders of magnitude compared to well-known single-threaded data mining software platforms, such as WEKA and the R platform. It also outperforms similar hardware systems which implement parts of the complete application by an order of magnitude. Finally, we show that the HC-CART system offers higher performance speedup than some other proposed parallel software implementations of decision tree construction algorithms.

This paper presents an in-depth look of how FPGA computing can offer substantial speedups in the execution of bioinformatics algorithms, with specific results achieved to date for a broad range of algorithms. Examples and case studies are presented for sequence comparison (BLAST, CAST), multiple sequence alignment (MAFFT, T-Coffee), RNA and protein secondary structure prediction (Zuker, Predator), gene prediction (Glimmer/GlimmerHMM) and phylogenetic tree computation (RAxML), running on mainstream FPGA technologies as well as high-end FPGA-based systems (Convey HC1, BeeCube). This work also presents technological and other obstacles that need to be overcome in order for FPGA computing to become a mainstream technology in Bioinformatics.

We design a very high speed LDPC code decoder architecture for (3,6)-regular codes by employing hybrid quantization, pipelining, and FPGA-specific optimizations. Our pipelined architecture fully addresses the decoder's significant I/O requirements, even when an early termination circuit is employed. The proposed decoder can achieve a throughput of up to 16.9 Gbps at an Eb/N0 of 3.5 dB using a code of length 1152, running at a clock speed of 153 MHz and performing a maximum of 10 decoding iterations, thus out-performing the state of the art by a significant margin. This design was fully implemented and tested on a Xilinx Virtex 5 XC5VLX110 FPGA. We also present an alternative, low-complexity design, which is able to achieve a throughput of up to 21.6 Gbps by sacrifing 0.75 dB in terms of Eb/N0.

The Lightfield descriptor method for 3D computer graphics offers the highest quality object retrieval from a database at the expense of higher storage and computational cost vs. other methods. This paper presents two special purpose architectures, based on FPGAs and GPUs, for the depth buffer extraction algorithm which is used by the Light field Descriptor method. The two architectures were fully designed and implemented in hardware on a Virtex 5 FPGA Device and on a GeForce GPU. The FPGA-based design offers a measured average speedup of 50x vs. software. The corresponding GPU results were by comparison less promising, but still better than software solutions. Results reported in this paper are from actual runs on hardware.

The available e-data throughout the Web are growing at such a high rate that data mining on the web is considered the biggest challenge of information technology. As a result it is crucial to find new and innovative ways for classifying and mining those huge amounts of data. In this paper we present an implementation of a state-of-the-art data mining algorithm on a modern FPGA. This is one of the first approaches utilizing the resources of an FPGA to accelerate certain very CPU intensive data-mining/data classification schemes and our real-world results from actual runs on hardware demonstrate that it is a highly promising one. In particular, our FPGA-based system achieves, depending on the data classified, a speedup from 4x and up to 50x (on average 25x) when compared with a state-of-the art multi-core CPU, including I/O overhead.

The Sinusoidal Pulse Width Modulation (SPWM) principle is widely used in power electronic DC/AC converters (inverters) in energy conversion and motor control applications. The digital SPWM generation unit implementations have dominated over their counterparts based on analog circuits. In this paper, an FPGA-based SPWM generator is presented, which is capable to operate at switching frequencies up to 1 MHz (requiring FPGA operation at 100-160 MHz), thus it is capable to support the high switching frequency requirements of modern power electronic DC/AC converters. The successful operation of the proposed SPWM generator at high switching frequencies is demonstrated with post place-and-route simulation results for design verification and actual runs on hardware for design validation and proof-of-concept. The switching frequency of this system is an order of magnitude faster than previously proposed FPGA-implemented SPWM systems.

The Eternity II puzzle is a combinatorial search problem which qualifies as a computational grand challenge. As no known closed form solution exists, its solution is based on exhaustive search, making it an excellent candidate for FPGA-based architectures, in which complex data structures and non-trivial recursion are implemented in hardware. This paper presents such an architecture, which was designed and fully implemented on a Virtex5 FPGA (XUP ML505 board). Despite the serial nature of the recursion, as parallelism can be applied with the initiation of multiple searches, the system shows a measured speedup of 2.6 vs. a high-end multi-core compute server.

Fine-grain reconfigurable devices suffer from the time needed to load the configuration bitstream. Even for small bitstreams in partially reconfigurable FPGAs this time cannot be neglected. In this article we survey the performance of the factors that contribute to the reconfiguration speed. Then, we study an FPGA-based system architecture and with real experiments we produce a cost model of Partial Reconfiguration (PR). This model is introduced to calculate the expected reconfiguration time and throughput. In order to develop a realistic model we take into account all the physical components that participate in the reconfiguration process. We analyze the parameters that affect the generality of the model and the adjustments needed per system for error-free evaluation. We verify it with real measurements, and then we employ it to evaluate existing systems presented in previous publications. The percentage error of the cost model when comparing its results with the actual values of those publications varies from 36% to 63%, whereas existing works report differences up to two orders of magnitude. Present work enables a user to evaluate PR and decide whether it is suitable for a certain application prior entering the complex PR design flow.

SRAM-based FPGAs are susceptible to Single-Event Upsets (SEUs) in radiation-exposed environments due to their configuration memory. We propose a new scheme for the diagnosis and recovery from upsets that combines i) duplication of the core to be protected, ii) partial reconfiguration to reconfigure the faulty part only, and iii) hardcore processor(s) for deciding when and which part will be reconfigured; executing the application in software instead of hardware during fault handling; and controlling the reconfiguration. A hardcore processor has smaller cross section and it is less susceptible than reconfigurable resources. Thus it can temporarily undertake the execution during upset conditions. Real experiments demonstrate that our approach is feasible and an area reduction of more than 40% over the dominant Triple Modular Redundancy (TMR) solution can be achieved at the cost of a reduction in the processing rate of the input.

Secondary structure prediction is a compute-intensive task that is used in many bioinformatics applications. In this paper we have selected two of the most well-known secondary structure prediction algorithms, the Predator and the Zuker algorithm, and we present two FPGA-based systems that implement them. Also, this paper presents different schemes of data reuse and data organization of structure prediction systems to avoid the data I/O bottleneck. The speedup of the execution time is at least 37x for the Predator method and 3x for the Zuker method compared to the corresponding software implementations. Finally, this paper shows that the exploitation of FPGA capabilities offers high performance systems that can be used by the bioinformatics community.

Optimal Golomb Rulers (OGR) are a discrete mathematics problem for which there is no known closed form solution. This problem is so computationally intensive that it is considered a “grand challenge problem”. Since the early 1990's FPGA-based OGR engines have been designed, with excellent performance vs. general-purpose computing. This paper presents a new, single FPGA clientserver architecture for OGR derivation. The new client architecture supports parallel evaluation of multiple hypotheses (up to 16), each implemented as a shift operation, and one server which can support many clients. The new architecture has a measured speedup of 8 against an Intel Core 2 Duo processor for a single client supporting up to eight “shifts” and running on a Virtex 2P FPGA, and a post place-and-route simulation-derived speedup of 160 with four clients on a Virtex 5 FPGA, each supporting up to sixteen “shifts”. The new architecture has been fully implemented and runs on actual hardware, whereas simulations have been used to project performance on FPGA's which were not available for experimentation.

In the FPT 2010 International Conference an Othello competition has been announced, based on the popular game and with requirements for implementation of full designs on standardized FPGA platforms. This paper presents in detail the CarlOthello architecture and design, which is heavily pipelined in order to increase the expansion rate of the overall system, reaching a peak of 4×108expansions per second. The Monte Carlo-based Othello player was fully designed, implemented in hardware, and tested. This design wins every game against the FPT 2010 reference software.

As FPGA devices become larger, more coarse-grain modules coupled with large scale reconfigurable fabric become available, thus enabling new classes of applications to run efficiently, as compared to a general-purpose computer. This paper presents an architecture that benefits from the large number of DSP modules in Xilinx technology to implement massive floating point arithmetic. Our architecture computes the Phylogenetic Likelihood Function (PLF) which accounts for approximately 95% of total execution time in all state-of-the-art Maximum Likelihood (ML) based programs for reconstruction of evolutionary relationships. We validate and assess performance of our architecture against a highly optimized and parallelized software implementation of the PLF that is based on RAxML, which is considered to be one of the fastest and most accurate programs for phylogenetic inference. Both software and hardware implementations use double precision floating point arithmetic. The new architecture achieves speedups ranging from 1.6 up to 7.2 compared to a high-end 8-way dual-core general-purpose computer running the aforementioned highly optimized OpenMP-based multi-threaded version of the PLF.

An important biology problem is the decoding of the DNA and the extraction of useful genetic information. There are many bioinformatics algorithms that try to solve the gene finding problem and one of the most efficient is the Glimmer algorithm. In this paper, we present a hardware architecture that implements the Glimmer algorithm. The architecture was developed specifically for the capabilities of present-day FPGAs. In addition, this paper presents an efficient hardware method to construct a huge but very sparse lookup table by taking advantage the tree-like structure of memories.

Genetic algorithms (GA) are search algorithms based on the mechanism of natural selection and genetics. FPGAs have been widely used to implement hardware-based genetic algorithms (HGA) and have provided speedups of up to three orders of magnitude as compared to their software counterparts. In this paper, we propose a parameterized partially reconfigurable HGA architecture (PPR-HGA). The novelty of this architecture is that it allows for the objective function to be updated through partial reconfiguration, and supports various genetic parameters.

Driven by novel biological wet lab techniques such as pyrosequencing there has been an unprecedented molecular data explosion. The growth of biological sequence data has significantly out-paced Moore's law. This development also poses new computational and architectural challenges for the field of phylogenetic inference, i.e., the reconstruction of evolutionary histories (trees) for a set of organisms which are represented by respective molecular sequences. Phylogenetic trees are currently increasingly reconstructed from multiple genes or even whole genomes. The introduced term "phylogenomics" reflects this development. Hence, there is an urgent need to deploy and develop new techniques and computational solutions to calculate the computationally intensive scoring functions for phylogenetic trees. In this paper, we propose a dedicated computer architecture to compute the phylogenetic maximum likelihood (ML) function. The ML criterion represents one of the most accurate statistical models for phylogenetic inference and accounts for 85% to 95% of total execution time in all state-of-the-art ML-based phylogenetic inference programs. We present the implementation of our architecture on an FPGA (field programmable gate array) and compare the performance to an efficient C implementation of the ML function on a high-end multi-core architecture with 16 cores. Our results are two-fold: (i) the initial exploratory implementation of the ML function for trees comprising 4 up to 512 sequences on an FPGA yields speedups of a factor 8.3 on average compared to execution on a single-core and is faster than the OpenMP-based parallel implementation on up to 16 cores in all but one case; and (ii) we are able to show that current FPGAs are capable to efficiently execute floating point intensive computational kernels.

Recursion is a powerful technique used to solve problems with repeating patterns, and is a fundamental structure in software. To date there is no known general way to apply a recursive solution to reconfigurable hardware; it is considered difficult to implement, of low performance and resource-intensive. In this paper we extend previous results on hardware structures for recursion by V. Sklyarov, and we demonstrate that recursion can be efficiently implemented in a general way on FPGAs. We show that our general, non-optimized architecture presents approximately 3 times speedup against optimized software algorithm implementations. It also shows 75% speedup, at least 40% lower area utilization, and at the same time it is simpler, less designer time consuming and more general vs. previously published hardware implementations.

This paper presents a new architecture to accelerate quantum computations, using reconfigurable computing structures. It was designed post place and route, validated with standard benchmarks, and its performance has been evaluated vs. a high end computer running the same benchmarks with highly optimized code. The acceleration of arbitrary quantum circuits is very promising because it extends the kind of quantum computing problems that can be solved with reconfigurable architectures.

SCAN is a class of formal languages for compression, encryption and information hiding. We have previously studied and reported separate hardware implementations of SCAN compression and encryption. This paper presents initial results on the design of a complete single-chip system for the SCAN compression, encryption and information hiding algorithm using the stretch technology with reconfigurable and fixed resources. The result is a simple, low cost, embeddable core combining all three operations seamlessly and the design was fully mapped to the stretch technology.

Dynamic reconfiguration is gaining popularity [2], [4] but it may cause degradation of overall execution time due to the time to download the bitstream before an application starts execution of the new configuration. Thus evaluation of its performance becomes an interesting area [3]. In this work we include an analysis of the reconfiguration time by defining the delays that add up to it. An experimental setup is deployed that can be used for performance evaluation of applications implemented with dynamic reconfiguration, as well as of mechanisms developed to reduce reconfiguration overhead.

The most prevalent algorithm for DNA sequence matching is the BLAST algorithm. We have developed several FPGA-based architectures to speed up BLAST execution. In this work we present a new VLSI architecture as a followup to our reconfigurable logic-based architectures, and we compare the performance of several software and hardware implementations of BLAST.

The Parrotfish project is a low cost, distributed environment for (partial) reconfiguration of distributed field programmable systems, e.g. sensor networks. In this paper we present architectures and results in which the wireless nodes of a distributed system can undergo runtime task-reversals under triggering from external conditions, using Bluetooth as a low cost wireless medium. The project gets its name from the small fish found in Florida waters, which can change gender as needed under group dynamics

Partial reconfiguration suffers from the inherent high latency and low throughput which is more considerable when reconfiguration is performed on-demand. This work deals with this overhead in processors combining a fixed processing unit (FPU), and a reconfigurable processing unit (RPU). Static and dynamic prefetching (Li, 2002), and instruction forecasting (Iliopoulos and Antonakopoulos, 2001) are targeting at reduction of the overhead through preloading of configurations. Banerjee et al. (2005) transform the task graph of an application and a heuristic algorithm evaluates the reduction in schedule length and selects the most promising configuration. Tasks are scheduled according to the physical resource constraints. In this work the prefetching model of Li (2002) was augmented by taking into account the hardware area constraints of a partially reconfigurable system. Given the task graph of an application, tasks with low probability to be executed are split and preloaded according to the hardware in order to be fully utilized. Thus, the time during which reconfiguration is overlapped with processor execution is increased

Dynamic reconfiguration allows for the reuse of the same hardware by different tasks of an application at different stages of its execution. However, reconfiguring the hardware at run-time incurs a configuration delay causing performance degradation of the application. This paper evaluates a preloading model that hides the configuration overhead. An existing preloading model is augmented according to the physical constraints of the system. A reduction of 6% up to 86% in execution time has been obtained with the new model

DNA sequence comparison is a computationally intensive problem, known widely since the competition for human DNA decryption. Database search for DNA sequence comparison is of great value to computational biologists. Several algorithms have been developed and implemented to solve this problem efficiently, but from a user base point of view the BLAST algorithm is the most widely used one. In this paper, we present a new architecture for the BLAST algorithm. The new architecture was fully designed, placed and routed. The post place-and-route cycle-accurate simulation, accounting for the I/O, shows a better performance than a cluster of workstations running highly optimized code over identical datasets. The new architecture and detailed performance results are presented in this paper

The BLAST algorithm is the prevalent tool that is used by molecular biologists for DNA sequence matching and database search. In this work we demonstrate that with an appropriate reconfigurable architecture, BLAST performance can be improved with a single-chip solution 5 times over a specialized and optimized computer cluster, or 37 times over a single computer. These initial results account for I/O and are very encouraging for the development of a large scale, reconfigurable BLAST engine

This project is aimed at developing the full TCP/IP protocol as an open-source IP core which can be freely used, as well as to develop know-how on protocol boosting for complex protocols such as TCP/IP. The problem was quite challenging, especially if we consider that just about all commercial implementations of TCP/IP do not fully implement all of the protocol specifications.

By "distributed reconfigurable systems" we mean systems of distributed resources, which include dynamically reconfigurable FPGA components. There already exist systems such as wearable computers with distributed reconfigurable resources, but the broader area is rather unexplored. Reconfigurable distributed systems have some unique characteristics or desired behavior, which merit further study. To illustrate, any attempt for a full implementation of TCP/IP in hardware leads to prohibitively expensive solutions for low-cost sensor networks. Therefore, lighter protocols are needed. However, whereas data exchange can be effectively done through unreliable communication channels, reconfiguration assumes that a reliable data stream has to be provided for purposes of reconfiguration. Whereas a bit error rate (BER) due to noise, etc. can pose no problem in data communication, it would effectively lead to inability to reconfigure just about any present day reconfigurable device, unless accounted for at the protocol level. And yet we just dismissed TCP/IP as a protocol, although it would have provided for the desired robustness.

The SCAN methodology is a class of formal languages which can be applied to compression, encryption, and data hiding or in combinations thereof. The SCAN algorithm for video compression belongs to the category of interframe techniques. Each frame is compared to its preceding one and through frame differencing redundant information is removed. As in all algorithms of this category key frames are placed as beginning points for finding the differences with subsequent frames. Frames between key frames are named difference frames and they only contain the information that has changed from the previous frame. The differences between frames are determined using a user-defined threshold value, and therefore in general this type of compression can be lossy. The consequent degradation of picture is controlled by the user via the choice of threshold value. When this threshold is 0 the compression becomes lossless. The final goal is to develop a seamless architecture for compression, encryption and information hiding.

This paper briefly presents a block cipher encryption architecture and a reconfigurable logic-based hardware design for the SCAN encryption algorithm. Detailed performance results are presented for still images as well as video, and the reconfigurable architecture is compared to software-only implementations of the same algorithm as well as a preliminary ASIC design.

A second generation of an embedded input device for kinetically challenged persons is presented. The new system can detect O(n/sup 2/) free motions in space with O(n) hardware, and has the capability to form extendable vocabularies of motions. The improved motion detection computational model is presented, together with experimental results.

A new architecture for Golomb ruler derivation has been developed so that rulers up to 24 marks can be proven on it. In this architecture, 8-mark stubs that are derived on a personal computer are subsequently processed by the FCCM, called GE2, allowing for parallel processing of as many stubs as are the available FPGAs. Actual runs of the new design have been performed on the TOP parallel FPGA machine at Virginia Tech. This paper presents the design improvements over the original architecture, which include single FPGA implementation, hardware/software codesign, FIFO based I/O, design for parallel execution, and performance results from actual runs.

A new architecture for Golomb ruler derivation has been developed, and an FPGA-based custom compute engine of the new architecture has been fully designed. The new FCCM, called GE1, is presented in terms of its datapath, and control path. Portions of the GE1 have been implemented to verify functional correctness and accuracy of the simulation results. The new machine requires twenty Xilinx 5000 series FPGA's for derivation of the 20 mark Golomb ruler, and its performance is roughly 30 times that of a high-end workstation, making its cost-performance ratio exceptionally good for derivation of new rulers.

An algorithm for the derivation of Golomb rulers has been mapped on the Quickturn RPM, the Splash 2, and a newly developed FCCM, named GEI. The relative advantages and disadvantages of the three cases are quantified and analyzed in this paper.

A new parallel distributed algorithm for Golomb (1977) ruler derivation is presented. This algorithm was used to prove computationally the optimality of three rulers. Two of these were previously proven but yet unpublished, and the authors' independent derivation confirmed these results. The last ruler, of 19 marks and size 246, was known to be near-optimal and was computationally proven optimal in this work.

Extensions to VHDL have been defined in order to produce a compiler that allows for system design with synthesizable and non-synthesizable multi-chip subsystems. The compiler has been completed and this paper presents a case study that has been made to evaluate the merits and limitations of this approach. Finally, a brief discussion is made of the error generation. Capability that results from the use of formal methods in the definition of the VHDL language extensions.

System design is typically done in VHDL to facilitate top-down design and to enable the mapping of a design to many implementations. Reusability of subsystems to date has largely been performed with libraries of synthesizable VHDL subsystems. This paper presents recommended extensions to VHDL to allow the VHDL designer to interact with nonsynthesizable subsystems while still designing in VHDL. The extended VHDL code is passed through a precompiler that outputs two standard VHDL files: a simulatable VHDL model of the system, and a synthesizable model of the design where subsystems are replaced by signals to the external hardware.>

The use of the Teamwork computer-aided software engineering (CASE) environment in a hardware application is examined. Teamwork is used to capture and maintain the specifications of a real-time image processing system under development at Duke University. It is demonstrated that when coupled with appropriate methodology, Teamwork can be used in hardware projects. The strengths and weaknesses of this approach are identified. The requirements for similar environments to overcome some of the problems encountered are outlined.>

An examination is made of how knowledge about communication among processes can be used to improve task scheduling on symmetric multiprocessors. Two series of experiments have also been conducted on a symmetric multiprocessor to quantify the performance of a knowledge-based scheduler. It is shown that overall system performance is improved with the new approach.>

The effect of designer inexperience and incomplete CAD tool suites on the rapid prototyping of microelectronic systems was studied through a course on advanced digital system design. Some of the results confirm that well known and respected design methodologies are indeed preferable to other alternatives, whereas other results showed previously unknown traits. All of the projects were successfully completed, demonstrating that the stated limitations can be overcome. The results of the study are discussed.>

A panel session concerning the use of knowledge-based techniques is reported. The discussion covers the following topics: knowledge-based machine vision architectures; experiences from a knowledge-based integrated-circuit testing system; artificial-intelligence (AI) tools for requirements capture and analysis; an approach to knowledge modeling in expert systems design; and a homogeneous approach to bringing AI and database management systems together.>

An interactive environment utilizing a knowledge-based system for the transparent testing of integrated circuits from simulation data has been developed. Unique features of this system are its modularity and its ease of expansion with new simulators and testers. The system uses the Omnitest language and a tester description language. The environment is fully operational and has been used to test several fabricated integrated circuits. An example illustrating the operation of the system is presented.>

The term "rapid system prototyping" is introduced in the context of academic research in digital systems. The technological issues as well as issues of policy which affect system prototyping in academia are presented, as well as opportunities stemming from a rapid system design cycle. The complementary role of academia and industry in the development of systems is outlined.>