High-throughput and low-latency sorting is a key requirement in many applications that deal with large amounts of data. This paper presents efficient techniques for designing high-throughput, low-latency sorting units. Our sorting architectures utilize modular design techniques that hierarchically construct large sorting units from smaller building blocks. The sorting units are optimized for situations in which only the M largest numbers from N inputs are needed, because this situation commonly occurs in many applications for scientific computing, data mining, network processing, digital signal processing, and high-energy physics. We utilize our proposed techniques to design parameterized, pipelined, and modular sorting units. A detailed analysis of these sorting units indicates that as the number of inputs increases their resource requirements scale linearly, their latencies scale logarithmically, and their frequencies remain almost constant. When synthesized to a 65-nm TSMC technology, a pipelined 256-to-4 sorting unit with 19 stages can perform more than 2.7 billion sorts per second with a latency of about 7 ns per sort. We also propose iterative sorting techniques, in which a small sorting unit is used several times to find the largest values.

The set-top and portable device market continues to grow, as does the demand for more performance under increasing cost, power, and thermal constraints. The integration of Graphics Processing Units (GPUs) into these devices and the emergence of general-purpose computations on graphics hardware enable a new set of highly parallel applications. In this paper, we propose and make the case for a GPU multitasking technique called spatial multitasking. Traditional GPU multitasking techniques, such as cooperative and preemptive multitasking, partition GPU time among applications, while spatial multitasking allows GPU resources to be partitioned among multiple applications simultaneously. We demonstrate the potential benefits of spatial multitasking with an analysis and characterization of General-Purpose GPU (GPGPU) applications. We find that many GPGPU applications fail to utilize available GPU resources fully, which suggests the potential for significant performance benefits using spatial multitasking instead of, or in combination with, preemptive or cooperative multitasking. We then implement spatial multitasking and compare it to cooperative multitasking using simulation. We evaluate several heuristics for partitioning GPU stream multiprocessors (SMs) among applications and find spatial multitasking shows an average speedup of up to 1.19 over cooperative multitasking when two applications are sharing the GPU. Speedups are even higher when more than two applications are sharing the GPU.

State-of-the-art graphic processing units (GPUs) can offer very high computational throughput for highly parallel applications using hundreds of integrated cores. In general, the peak throughput of a GPU is proportional to the product of the number of cores and their frequency. However, the product is often limited by a power constraint. Although the throughput can be increased with more cores for some applications, it cannot for others because parallelism of applications and/or bandwidth of on-chip interconnects/caches and off-chip memory are limited. In this paper, first, we demonstrate that adjusting the number of operating cores and the voltage/frequency of cores and/or on-chip interconnects/caches for different applications can improve the throughput of GPUs under a power constraint. Second, we show that dynamically scaling the number of operating cores and the voltages/frequencies of both cores and on-chip interconnects/caches at runtime can improve the throughput of application even further. Our experimental results show that a GPU adopting our runtime dynamic voltage/frequency and core scaling technique can provide up to 38% (and nearly 20% on average) higher throughput than the baseline GPU under the same power constraint.

Embedded multicore devices require high performance with minimal power consumption; many systems use dedicated hardware units to meet these constraints. However, embedded systems have also become increasingly multi-purpose and must be able to execute a wide range of applications - some of which might not yet be known at design time. It is therefore difficult to choose an appropriate mix of dedicated hardware that meets a device's size, cost, and capability constraints. A reconfigurable hardware coprocessor is a potential solution, as it is highly effective at accelerating a variety of different tasks (which need not necessarily be known in advance), and does so using less energy than general purpose processors. In this work, we first describe a method for sharing a single reconfigurable fabric amongst multiple processors on the same chip. We then examine the scalability of the memory subsystem that joins these resources, and determine methods to improve its performance to maximize acceleration. In this work, we show that our RH coprocessor model allows multiple applications to share a single RH fabric. Furthermore, we show that application performance does not significantly degrade as we increase the number of cores sharing a single coprocessor.

Effectively scheduling tasks on heterogeneous resources is critical to maximizing the overall benefit of those resources in system-on-a-chip architectures. In this paper we focus on scheduling soft a periodic tasks alongside periodic tasks with hard deadline constraints on heterogeneous real-time systems. We introduce a method to improve a periodic task responsiveness without breaking periodic task deadline guarantees, by first scheduling periodic tasks offline, then dynamically scheduling a periodic tasks in the remaining resource slack time. Experimental results indicate that the quality of a periodic task scheduling depends highly on the slack distribution within and across resources after periodic task scheduling, and on the flexibility of the a periodic task scheduler to rearrange these compute slacks to accommodate incoming a periodic tasks.

Decimal floating-point (DFP) arithmetic is becoming increasingly important and specifications for it are included in the revised IEEE 754 standard for floating-point arithmetic (IEEE 754-2008). The binary encoding of DFP numbers specified in IEEE 754-2008 is commonly referred to as Binary-Integer Decimal (BID). BID uses a binary integer to encode the significant, which allows it to leverage existing high-speed binary circuits. However, performing decimal rounding on these binary significant is challenging. In this paper, we propose and evaluate several approaches to perform decimal rounding in hardware for DFP numbers that use the BID encoding. We summarize several rounding techniques, present the theory and design of each proposed rounding unit, and use synthesis results to evaluate the critical path delay, latency, and area of rounding units for 64-bit BID numbers. Our results indicate that the bulk of each rounder design is occupied by a binary fixed-point multiplier that can be shared with other integer and floating-point operations. This is the first paper to present and compare a variety of techniques for BID-based rounding hardware. These techniques are valuable to designers of BID-based DFP solutions.

Modern scientific applications are large, complex, and highly parallel they are commonly executed on supercomputers with tens of thousands of processors. Yet these applications still commonly require weeks or even months to execute. Thus, single-thread performance remains a concern for highly parallel scientific applications. Adding a reconfigurable accelerator to each CPU could improve system performance; however, scientific applications have design constraints that differ from most application domains commonly accelerated by reconfigurable logic. In this article, we discuss the constraints imposed by scientific applications on the computation model, the accelerator architecture, and the accelerator’s communication interface with the CPU. Based on these constraints and application analysis, we have previously proposed adding a Reconfigurable Functional Unit (RFU) to accelerate integer graphs that calculate complex memory addresses. In this work, we now propose a flexible multi-instruction interface technique that allows dataflow graphs implemented on the RFU to access a large number of inputs and outputs with minor CPU datapath modifications. We present an in-depth examination of the performance effects of different communication interfaces that use this technique, and select one that best matches the needs of Sandia’s scientific applications. Although RFU execution overall improves performance, we also isolate two key negative performance effects introduced by aggregating CPU instructions into dataflow graphs: delayed issue and graph serialization. Finally, to demonstrate the marketability of an RFU beyond scientific applications, we reanalyze the proposed interfaces using the SPEC-fp benchmark suite. We show that although choosing an interface based on SPEC-fp needs is detrimental to Sandia application performance, choosing an interface based on Sandia demands works well for more general-purpose applications.

Evaluating the performance of reconfigurable computing applications in multi-tasking systems using simulation (as can be needed in early design-space exploration) faces several challenges. The complexity of full-system, cycle-accurate simulation prevents executing applications of any appreciable size to completion. One must sample only a portion of execution; yet unless care is taken, the measured performance for the sampled interval will not be indicative of the complete execution. Although this is generally a problem for simulation-based evaluation, the problem is exacerbated for multi-tasking systems. This paper therefore presents work to develop a performance evaluation methodology that accurately measures hybrid (both hardware and software) application performance, accounts for additional overhead introduced by hybrid resource management (such as run-time allocation of reconfigurable hardware), and correctly compensates for momentary imbalances in processor time allocation that are only artifacts of the (necessarily) short simulated execution timespan and would balance out over time.

The introduction of asymmetric embedded multiplier blocks in recent Xilinx FPGAs complicates the design of larger multiplier sizes. The two different input bitwidths of the embedded multipliers lead to two different shifting factors for the partial products that must be summed. This makes even the most straightforward multiplier design less intuitive. In this thesis, I present a methodology and set of equations to automatically generate Verilog hardware description code for arbitrary multiplier sizes composed of arbitrarily-sized asymmetric embedded multiplier cores. The presented technique also uses intelligent rearrangement of the multiplier block outputs into partial product terms to reduce the overall delay of the circuit. Multipliers created with this generator are faster and use fewer DSP blocks than either those created using Xilinx Core Generator or those created by simply using the ?*? operator in Verilog. It also uses fewer LUTs than those created using the ?*? operator. Finally, the presented generator can create multipliers larger than possible with Core Generator, and is limited only by the number of available embedded multipliers.

Researchers in embedded and reconfigurable computing are often hindered by a lack of suitable benchmarks with which to accurately evaluate their work. Without a suitable benchmark suite, researchers use either outdated, unrealistic benchmarks or spend valuable time creating their own. In this paper, we present ERCBench—a freely-available, open-source benchmark suite geared towards embedded and reconfigurable computing research. ERCBench benchmarks represent a variety of application areas, including multimedia processing, wireless communications, and cryptography. They consist of synthesizable Verilog models for hardware accelerators and hybrid hardware/software applications that combine software-based control flow with hardware-based computation tasks.

The operating system plays an important role in managing the reconfigurable hardware (RH) resources in a reconfigurable computing system to maximize system performance. These systems are becoming increasingly more complex, with multi-core CPUs and multi-tasking applications, each containing multiple kernels of computation that could be accelerated in RH. In such a system, the dynamic allocation of RH resources also becomes increasingly difficult. In this paper we examine one of the important issues a scheduler may encounter: the performance benefits of accelerating a particular kernel in an application may be enhanced by also accelerating other kernels in the application. We show that a scheduler that ignores these interdependencies will not always find the best allocation. We also propose a new RH scheduler designed specifically to handle these interdependencies, improving system performance.

Embedded systems increasingly include heterogeneous compute resources. Yet the vast majority of real-time scheduling methods are designed for single-resource or homogeneous multi-resource systems. Heterogeneity complicates scheduling; task execution time is resource-dependent. Furthermore, the best resource for one task may not necessarily be the best resource for all tasks, so one resource may not be universally more valuable than another. This paper presents new algorithms designed specifically for heterogeneous real-time scheduling. We evaluate the algorithms' deadline miss rates for heterogeneous task sets that represent a variety of execution scenarios, and show that two of our algorithms have lower deadline miss rates than the Earliest Deadline First or Least Laxity First approaches. We also discuss how task set and system characteristics affect the schedulers' abilities to achieve a quality schedule.

In this paper, we describe the first hardware design of a combined binary and decimal floating-point multiplier, based on specifications in the IEEE 754-2008 floating-point standard. The multiplier design operates on either (1) 64-bit binary encoded decimal floating-point (DFP) numbers or (2) 64-bit binary floating-point (BFP) numbers. It returns properly rounded results for the rounding modes specified in IEEE 754-2008. The design shares the following hardware resources between the two floating-point datatypes: a 54-bit by 54-bit binary multiplier, portions of the operand encoding/decoding, a 54-bit right shifter, exponent calculation logic, and rounding logic. Our synthesis results show that hardware sharing is feasible and has a reasonable impact on area, latency, and delay. The combined BFP and DFP multiplier occupies only 58% of the total area that would be required by separate BFP and DFP units. Furthermore, the critical path delay of a combined multiplier has a negligible increase over a standalone DFP multiplier, without increasing the number of cycles to perform either BFP or DFP multiplication.

The best interface between CPUs and reconfigurable hardware in heterogeneous systems remains an open question. The trend in multi-core processors is to communicate through a shared memory hierarchy; but cache organizations that work best for general-purpose multi-core systems may not be best for heterogeneous systems. In this paper we explore a variety of cache topologies for connecting a CPU with reconfigurable hardware through a shared memory hierarchy. We demonstrate that in our modeled heterogeneous system, like in general multi-core systems, sharing at least one level of the cache is important for performance and multiple cache levels can reduce the dynamic power consumption of the memory hierarchy.

The Compact Muon Solenoid (CMS) Trigger of the Large Hadron Collider (LHC) particle accelerator at CERN selects potentially interesting particle collision data to process and archive for further study. The first stage of the trigger system, the hardware-based L1 Trigger, must sift through roughly 3 terabits/second of data describing the energy distribution of particles generated in the collisions, and reduce it to 100 megabits/second of event data that subsequent systems can handle. Without the CMS Trigger, the amount of experiment-generated data would quickly outstrip the archiving ability of the LHC system. Because of the sheer amount of input data and the rate at which it is generated, the hardware-based L1 Trigger is subject to stringent performance requirements. These will become even more severe as the LHC is upgraded over the next ten years, requiring a careful redesign of the L1 Trigger hardware. For example, future upgrades may introduce particle motion-tracking data into the L1 Trigger, resulting in an increased input data rate of up to 40 terabits/second. The need to modify the design as the LHC system is upgraded, the low-volume cost advantages of FPGAs, and a desire for a flexible and adaptable system all point toward the use of FPGAs as a hardware implementation solution. In this paper, we present several different FPGA implementations of the electron/photon identification module, a key part of the new Clustering Algorithm for the upgraded L1 Trigger. We analyze the resource requirements and performance tradeoffs, and present a qualitative discussion of flexibility to meet the changing needs of the CMS experiment. Finally, we narrow potential design choices to the top candidates and use one in a full Clustering Algorithm implementation.

Save and restore of context data is traditionally used in process preemption in multi-tasking operating systems. Multi-tasking, and by consequence, preemption, is key to effective CPU sharing. However, it is much more expensive to save and restore context data in reconfigurable hardware than it is in traditional software. The configuration and current state comprises a large amount of data, making the transfer a long and expensive operation. In this paper, we explore alternatives to the save and restore operation for hardware multi-tasking. We compare the system performance of three alternate policies for reconfigurable hardware kernel preemption in a multi-process system: block, drop and roll. The best-performing policy is able to achieve on average within 4% of the performance of an idealized, zero-overhead save and restore method on a mixed application workload.

Performance evaluation of hybrid (heterogeneous ISA) computing systems faces three major challenges: hybrid execution, multi-tasking, and system-level simulation variation. To evaluate system-level design decisions, a metric must encompass all forms of execution in a system, and incorporate any overheads introduced by hybrid execution. Differences in relative application speedups in a multi-tasking system complicate overall system performance evaluation. In full-system simulation, the relatively limited time-span for feasible tests compounds the evaluation problem. This paper discusses these challenges and presents metrics that address them.

Embedded systems designers frequently avoid using floating-point computation because it is too costly to include a floating-point unit (FPU) in an embedded processor. However, the performance of software floating-point libraries can be lacking. Therefore we propose a fractured floating point unit (FFPU)-a hybrid solution using a mix of custom hardware instructions and software code. An FFPU is designed as a compromise between software libraries and custom FPUs in both area and performance. We present three 32-bit FFPUs designs for a Nios II soft processor, and compare their performance and area to the baseline Nios II and a Nios II with a complete FPU. The FFPUs improve floating-point addition and subtraction performance by 24 to 52 percent over the baseline, with an ALM increase of only 12 to 32 percent, and no increase in DSP blocks.

The IEEE Standards Committee recently approved the IEEE 754-2008 Standard for Floating-point Arithmetic, which includes specifications for decimal floating-point (DFP) arithmetic. A growing number of DFP solutions have emerged, and developers now have many DFP design choices including arbitrary or fixed precision, binary or decimal significand encodings, 64-bit or 128-bit DFP operands, and software or hardware implementations. There is a need for accurate analysis of these solutions on representative DFP benchmarks. In this paper, we expand previous DFP benchmark and performance analysis research. We employ a DFP benchmark suite that currently supports several DFP solutions and is easily extendable. We also present performance analysis that (1) provides execution profiles for various DFP encodings and types, (2) gives the average number cycles for common DFP operations and the total number of each DFP operation in each benchmark, and (3) highlights the tradeoffs between using 64-bit and 128-bit DFP operands for both binary and decimal significand encodings. This analysis can help guide the design of future DFP hardware and software solutions.

No abstract available.

The use of reconfigurable hardware to accelerate computing intensive part of the applications has long been shown to provide large execution speedups. However, the long configuration latency and the limited amount of reconfigurable hardware resources demands careful arbitration of those resources among the applications in the system. In past efforts, we demonstrated that effective allocation of reconfigurable hardware resources can boost overall system throughput in a multi-tasking system. For that work, we invoked reconfigurable hardware scheduling periodically with a fixed interval. In this work, we further examine the size of the static scheduling interval, and propose two adaptive interval approaches that use a phase tracking technique to reduce overall scheduling overhead by up to 85%.

Effective reconfigurable hardware (RH) allocation plays a critical role in multi-tasking systems. Past RH scheduling research has focused on how to allocate RH based on the area and performance of competing hardware kernels. However, these approaches generally assume that the metrics associated with those hardware kernels are pre-determined. However, design-time estimates may not always be accurate or even stable. If the scheduler uses incorrect information, performance of one or more applications will suffer. In this paper, we adapt common performance-monitoring techniques to reconfigurable computing and quantify the importance of active performance monitoring of reconfigurable applications.

Most modern multitasking operating systems assume that, in order to be fair, CPU time should be allocated equally to processes of the same priority. However, this assumption is no longer valid in a system with acceleration hardware, such as reconfigurable hardware (RH), if the goal is equal computation ability for the processes. A process that uses acceleration hardware such as RH can accomplish far more work in a set span of time than a process that only executes on the CPU for that same time. When both accelerated and non-accelerated processes run concurrently, an equal time-slice allocation of CPU resources will not result in equal amounts of work performed. In this paper we present a new allocation technique that distributes computation ability, either equally or with parameterized bias. This technique allows all processes to benefit from RH acceleration—even those that are not specifically designed for it. We demonstrate different possible balancing methods using a custom built Linux kernel with this new scheduler, running on a full-system cycle-accurate simulation platform.

Because of the difficulty of increasing single-threaded processor performance, multi-core systems are becoming increasingly popular. These systems bring new challenges to the design of a reconfigurable computing system, with reconfigurable hardware potentially shared between multiple simultaneously-executing applications. In this paper, we examine how to best use reconfigurable hardware in a multiprocessor system. One of the key aspects of this work is improving overall system throughput by sharing configured circuits between multiple processes concurrently executing on the system. In this work, we show that using our extensions for sharing configured circuits between processes improves overall system throughput, and outperforms a static schedule of the kernels between the multiple processes.

Reconfigurable hardware is ideal for use in systems-on-a-chip (SoC), as it provides both hardware-level performance and post-fabrication flexibility. However, any one architecture is rarely equally optimized for all applications. SoCs targeting a specific set of applications can greatly benefit from incorporating customized reconfigurable logic instead of generic field-programmable gate-array (FPGA) logic. Unfortunately, manually designing a domain-specific architecture for every SoC would require significant design time. Instead, this paper discusses our initial efforts towards creating a reconfigurable hardware generator capable of automatically creating flexible, yet domain-specific, designs. Our tests indicate that our generated architectures are more than 5times smaller than equivalent FPGA implementations and nearly as area-efficient as standard cell designs. We also use a novel technique employing synthetic circuit generation to demonstrate the flexibility of our architecture generation techniques.

Reconfigurable hardware (RH) is used in an increasing variety of applications, many of which require support for features commonly found in general purpose systems. In this work we examine some of the challenges faced in integrating RH with general purpose processors and memory systems. We propose a new CPU-RH-memory interface that takes advantage of on-chip caches and uses virtual memory for communication. Additionally we describe the simulator model we developed to evaluate this new architecture. This work shows that an efficient interface can greatly accelerate RH applications, and provides a strong first step toward multiprocessor reconfigurable computing.

While scientific applications in the past were limited by floating point computations, modern scientific applications use more unstructured formulations. These applications have a significant percentage of integer computation - increasingly a limiting factor in scientific application performance. In real scientific applications employed at Sandia National Labs, integer computations constitute on average 37% of the application operations, forming large and complex dataflow graphs. Reconfigurable functional units (RFUs) are a particularly attractive accelerator for these graphs because they can potentially accelerate many unique graphs with a small amount of additional hardware. In this study, we analyze application traces of Sandia's scientific applications and the SPEC-FP benchmark suite. First we select a set of dataflow graphs to accelerate using the RFU, then we use execution-based simulation to determine the acceleration potential of the applications when using an RFU. On average, a set of 32 or fewer graphs is sufficient to capture the dataflow behavior of 30% of the integer computation, and more than half of Sandia applications show an improvement of 5% or more.

As it becomes more difficult to increase single-threaded performance, focus on multi-core processor designs increases. However, individual core performance is still important, especially for long-executing applications such as in scientific computing. Based on scientific application needs as modeled by SPEC-FP and a set of applications from Sandia National Labs, we have created several different reconfigurable functional unit (RFU) designs for superscalar multi-processor supercomputers. This paper discusses the design process and evaluates the RFUs' ability to implement instruction dataflow graphs from scientific workloads. Our best-performing RFU design is able to implement 89% of the dataflow graphs in the benchmarks.

Reconfigurable hardware has been shown to provide an efficient compromise between the flexibility of software and the performance of hardware. However, even coarse-grained reconfigurable architectures target the general case and miss optimization opportunities present if characteristics of the desired application set are known. Restricting the structure to support a class or a specific set of algorithms can increase efficiency while still providing flexibility within that set. By generating a custom array for a given computation domain, we explore the design space between an ASIC and an FPGA. However, the manual creation of these customized reprogrammable architectures would be a labor-intensive process, leading to high design costs. Instead, we propose automatic reconfigurable architecture generation specialized to given application sets. This paper discusses configurable ASIC (cASIC) architecture generation that creates hardware on average up to 12.3x smaller than an FPGA solution with embedded multipliers and 2.2x smaller than a standard cell implementation of individual circuits

In this paper, we present a full-system reconfigurable computing simulation platform intended to promote innovative new research in reconfigurable computing. Currently, reconfigurable computing researchers frequently use tools such as simple trace-based simulators to provide performance estimates for their designs and methods. However, because the scope of these simulations is generally high-level and limited to the reconfigurable hardware and possibly a host processor, the results presented may unfortunately be less than completely accurate, particularly with respect to memory and processor-hardware communication timing. As reconfigurable computing systems become less theoretical and move closer to widespread realization, more accurate evaluations are necessary to compare new system designs, configuration methods, hardware scheduling algorithms, and hardware structures. We therefore discuss the issues involved in implementing a full-system simulator for reconfigurable computing, presenting specific implementation techniques, and demonstrate the value of reconfigurable computing full-system simulation on an example application

Many modern scientific applications execute on massively parallel collections of microprocessors. Supercomputers such as the Cray XT3 (Red Storm) and Blue Gene/L support thousands to tens of thousands of processors per parallel job. However, individual microprocessor performance remains a critical component of overall performance. Traditional approaches to improve scientific application performance concentrate on floating-point (FP) instructions; however, our studies show that in the scientific applications used at Sandia National Labs, integer instructions constitute a large and critical part of the instruction mix. Although the SPEC-FP benchmark suite is considered representative of FP workloads, it has a much smaller proportion of integer computation instructions than the Sandia scientific applications, with 22.9% as compared to 36.9%. Integer instructions in Sandia applications also behave differently than in SPEC-FP. Integer instruction outputs are reused 8.8x to 13.1x more often in SPEC-FP benchmarks, and integer dataflow in Sandia applications is more complex than in the SPEC-FP suite. In this work, we examine common dataflow and usage patterns of integer instructions---information essential to develop hardware techniques to accelerate critical scientific applications. We present statistics for SPEC-FP and Sandia applications, summarizing integer computation usage and the size, shape and interface (number of inputs/outputs) of dataflow graphs.

Although many studies have demonstrated the benefits of reconfigurable computing, it has not yet penetrated the mainstream. One of the biggest unsolved problems is the management of the reconfigurable hardware in a multi-threaded environment. Most research in reconfigurable computing has assumed a single-threaded model, but this is unrealistic for personal computing and many types of embedded computing. In these cases, there may be several different threads or processes running simultaneously, each wishing to use the reconfigurable hardware. The operating system must decide how to allocate the hardware at run-time based on the status of the system. The system status could also influence the choice of different implementations for each circuit based on area/speed tradeoffs. This paper examines reconfigurable computing as it could be used in mainstream systems, focusing on a proposed scheduling algorithm to allocate the reconfigurable hardware. Our initial tests indicate that reconfigurable computing with our scheduler can easily achieve at least a 20% system-level speedup.

Although the benefits of software acceleration using reconfigurable logic have been demonstrated repeatedly, this style of computing has not yet penetrated the mainstream. One of the biggest unsolved problems is the management of the reconfigurable hardware in a multi-threaded environment. While most research in reconfigurable computing has assumed a single-threaded model, this is unrealistic for both personal computing and many types of embedded computing. In these cases, there may be several different threads running simultaneously. Each of these threads may have one or more sections of code (kernels) which would benefit from hardware acceleration. Somehow the operating system must decide at runtime which kernels to implement in software vs. hardware based on the status of the system. This includes potentially choosing from multiple possible hardware implementations (with different area/delay tradeoffs) of a single kernel. This paper examines our vision of reconfigurable computing applications in mainstream multithreaded systems, including a presentation of a proposed scheduling algorithm for allocating the reconfigurable hardware.

Traditional metrics used to compare hardware designs include area, performance, and power. However, these metrics do not form a complete evaluation of reconfigurable hardware. For these designs, flexibility is also a key issue, since it is the flexibility of reconfigurable hardware that allows it to implement a variety of circuits. Despite its importance, there is not yet an established method to measure flexibility. This paper explores the flexibility testing issue for domain-specific reconfigurable architectures. We discuss the concept of flexibility as it pertains to domain-specific architectures, and propose a flexibility testing technique involving synthetic circuit generation. This technique is then used to compare three different domain-specific architecture generation algorithms, demonstrating that the testing can in fact differentiate between architectures of differing levels of flexibility.

In this work, we parameterize and explore the interconnect structure of pipelined FPGAs. Specifically, we explore the effects of interconnect register population, length of registered routing track segments, registered IO terminals of logic units, and the flexibility of the interconnect structure on the performance of a pipelined FPGA. Our experiments with the RaPiD [4] architecture identify tradeoffs that must be made while designing the interconnect structure of a pipelined FPGA. The post-exploration architecture that we found shows a 19% improvement over RaPiD, while the area overhead incurred in placing and routing benchmarks netlists on the post-exploration architecture is 18%.

The design of a routing channel for an FPGA is a complex process, requiring the careful balance of flexibility with silicon efficiency. With the growing move towards embedding FPGAs into SoC designs, and the opportunity to automatically generate FPGA architectures, this problem becomes even more critical. The design of a routing channel requires determining the number of routing tracks, the length of the wires in those tracks, and the positioning of the breaks on the tracks. This paper focuses on the last of these problems, the placement of breaks in tracks to maximize overall flexibility. We have developed both an optimal algorithm and a number of heuristics to solve the track placement problem. The optimal algorithm finds a best solution provided the problem meets a number of restrictions. Most of the heuristics are without restrictions, and the most promising of these find solutions on average within 1.13% of optimal. Full text available as UWEE Technical Report #UWEETR-2002-0013 at http://www.ee.washington.edu/.

Due to its potential to greatly accelerate a wide variety of applications, reconfigurable computing has become a subject of a great deal of research. By mapping the compute-intensive sections of an application to reconfigurable hardware, custom computing systems exhibit significant speedups over traditional microprocessors. However, this potential acceleration is limited by the requirement that the speedups provided must outweigh the considerable cost of reconfiguration. The ability to relocate and defragment configurations on field programmable gate arrays (FPGAs) can dramatically decrease the overall reconfiguration overhead incurred by the use of the reconfigurable hardware. We therefore present hardware solutions to provide relocation and defragmentation support with a negligible area increase over a generic partially reconfigurable FPGA, as well as software algorithms for controlling this hardware. This results in factors of 8 to 12 improvement in the configuration overheads displayed by traditional serially programmed FPGAs.

Custom computing systems exhibit significant speedups over traditional microprocessors by mapping compute-intensive sections of a program to reconfigurable logic (Hauck, 1998). However, the high overhead of reconfiguration can limit the execution times achievable with these systems. Research has shown that the ability to relocate and defragment configurations on an FPGA dramatically decreases the overall configuration overhead (Li et al., 2000). We therefore explore the adaptation of the Xilinx 6200 series FPGA for relocation and defragmentation. Due to some of the complexities involved with this structure, we also present a novel architecture designed from the ground up to provide relocation and defragmentation support with a negligible area increase over a generic partially reconfigurable FPGA.

Although run-time reconfigurable systems have been shown to achieve very high performance, the speedups over traditional microprocessor systems are limited by the cost of configuration of the hardware. We explore the idea of configuration caching. We present techniques to carefully manage the configurations present on the reconfigurable hardware throughout program execution. Through the use of the presented strategies, we show that the number of required reconfigurations is reduced, lowering the configuration overhead. We extend these techniques to a number of different FPGA programming models, and develop both lower bound and realistic caching algorithms for these structures.