Stephen A Edwards
email: sedwards@cs.columbia.edu

The Challenges of Hardware Synthesis from C-like Languages

MANY TECHNIQUES for synthesizing digital hardware from C-like languages have been proposed, but none have emerged as successful as Verilog or VHDL for register-transfer-level design. This paper looks at two of the fundamental challenges: concurrency and timing control.

. Both languages' abstractions are close to processor data types and operations. BCPL treats memory as an array of words; integers, pointers, and characters are represented as a word. For the PDP-11, Ritchie added character, integer, and floating-point types. C's arrays are a side effect of its pointer semantics, which enables simple, efficient implementations, but also demands compilers with aggressive optimization to perform costly pointer analysis.

 and De Micheli [3]. Stroud et al.'s early Cones [23] synthesized each functions in a combinational block. Its strict C subset handled conditionals; loops, which it unrolled; and arrays treated as bit vectors. As input for their Olympus synthesis system [4], Ku and De Micheli developed HardwareC [12], a behavioral hardware language with support for hardware structure and hierarchy. Galloway's Transmogrifier C [8] supports loops, conditionals, and integer arithmetic. It places cycle boundaries at function calls and at the beginning of while loops.

The SystemC [9] C++ library supports hardware and system modeling. While most popular for modeling (it provides concurrency with lightweight threads [13]), a subset of the language can be synthesized. Classes model hierarchical structures containing combinational and sequential processes.

, the user's C++ program runs to generate a data structure that represents hardware.

Cones [START_REF] Stroud | Behavioral model synthesis with cones[END_REF] Early, combinational only HardwareC [START_REF] Ku | HardwareC: A language for hardware design[END_REF] Behavioral synthesis-centric Transmogrifier C [START_REF] Galloway | The Transmogrifier C hardware description language and compiler for FPGAs[END_REF] Limited scope SystemC [START_REF] Grötker | System Design with Sys-temC[END_REF] Verilog in C++ Ocapi [START_REF] Schaumont | A programming environment for the design of complex high speed ASICs[END_REF] Algorithmic structural descriptions C2Verilog [START_REF] Soderman | Implementing C algorithms in reconfigurable hardware using C2Verilog[END_REF] Comprehensive; company defunct Cyber [START_REF] Wakabayashi | C-based synthesis experiences with a behavior synthesizer[END_REF] Restricted C with extensions (NEC) Handel-C [START_REF] Celoxica | [END_REF] C with CSP (Celoxica) SpecC [START_REF] Gajski | SpecC: Specification Language and Methodology[END_REF] Resolutely refinement-based Bach C [START_REF] Kambe | A C-based synthesis system, Bach, and its application[END_REF] Untimed semantics (Sharp) CASH [START_REF] Budiu | Compiling application-specific hardware[END_REF] Synthesizes asynchronous circuits [START_REF] Soderman | Implementing C algorithms in reconfigurable hardware using C2Verilog[END_REF][START_REF] Soderman | Implementing C designs in hardware: a full-featured ANSI C to RTL Verilog compiler in action[END_REF] hold a broad patent on C-to-Verilog translation [START_REF] Panchul | System for converting hardware designs in highlevel programming language to hardware implementations[END_REF] describing the compiler.

NEC's Cyber system [START_REF] Wakabayashi | C-based synthesis experiences with a behavior synthesizer[END_REF] accepts a C variant dubbed BDL that contains hardware extensions but prohibits recursive functions and pointers. Timing can be implicit or explicit.

Celoxica's Handel-C [START_REF] Celoxica | [END_REF] adds constructs for parallel statements and OCCAM-like rendezvous communication. Each assignment statement runs in one cycle.

Gajski et al.'s SpecC [START_REF] Gajski | SpecC: Specification Language and Methodology[END_REF] adds constructs for finite-state machines, concurrency, pipelining, and structure through thirtythree keywords [START_REF] Dömer | SpecC Language Reference Manual. SpecC consortium[END_REF]. Systems written in the complete language must be refined into the synthesizable subset.

Sharp's Bach C [START_REF] Kambe | A C-based synthesis system, Bach, and its application[END_REF] adds explicit concurrency and rendezvous communication. The compiler does the scheduling; the number of cycles taken by each construct is not set by a rule. It supports arrays but not pointers.

Budiu et al.'s CASH [START_REF] Budiu | Compiling application-specific hardware[END_REF] is unique because it generates asynchronous hardware. It identifies instruction-level parallelism in ANSI C and generates asynchronous dataflow circuits. Concurrency is the biggest difference between hardware, for which is is fundamental, and software. Efficient software algorithms are rarely the best choice in hardware. More disturbing is that C and C++ are optimized for expressing sequential algorithms and contain no language-level support for concurrency, in part because there is no agreed-upon model for parallel programming [START_REF] Skillicorn | Models and languages for parallel computation[END_REF]. The absence of concurrency support means it must be added or inferred by the compiler.

About half the languages require the programmer to express concurrency with parallel constructs. HardwareC, SystemC, and Ocapi all use process-level constructs; Handel-C, Bach C, and SpecC can also group concurrent statements. SystemC's parallelism resembles Verilog or VHDL's: a system is a collection of clock-edge-triggered processes. Handel-C, SpecC, and Bach C's approaches are more software-like: their constructs dispatch groups of instructions in parallel.

Concurrency introduces a fundamental change to the language, demanding substantially different programmer thinking. Even if s/he is experienced with concurrent programming with the usual thread-and-shared-memory model, the parallel constructs in hardware languages differ substantially.

Other languages present a sequential model to the programmer and rely on the compiler to identify parallelism. While compilers for languages with parallel constructs also identify parallelism, Cones, Transmogrifier C, C2Verilog, and CASH rely on the compiler completely. Cones flattens each function, including loops and conditionals, into a single two-level networks. CASH, by contrast, takes a VLIW-compiler-like approach, analyzing inter-instruction dependencies and scheduling instructions to maximize parallelism.

Two common approaches to identifying parallelism differ in their granularity. Instruction-level parallelism (ILP) groups nearby instructions that can run simultaneously. Now the preferred approach in the computer architecture community, it seems that ILP beyond about five simultaneous instructions is unlikely due to fundamental limits [START_REF] Wall | Limits of instruction-level parallelism[END_REF][START_REF] Wall | Speculative execution and instruction-level parallelism[END_REF]. Pipelining, the second approach, requires less hardware than ILP but can be less effective. Again, dependencies and control-flow transfers limit parallelism. Pipelining works well on regular loops, e.g., in scientific computation [START_REF] Kennedy | Optimizing Compilers for Modern Architectures[END_REF], but is less effective in general.

For hardware, relying on the compiler to expose parallelism is awkward because using it effectively requires understanding details of the compiler's operation. Efficient implementations demand careful coding, and appropriate idioms would be awkward for programmers accustomed to writing efficient C. Time is absent from the C programming model. It guarantees causality, but says nothing about execution time. A simple model for both programmers and compilers, it can make achieving timing constraints difficult. The transparency of C software compilation makes gross improvements easy, but improving an already-optimized fragment is difficult.

Meeting a performance target under power and cost constraints is usually mandatory in hardware, since it is always easier to implement a function in software. Thus, any hardware synthesis technique needs a way to meet timing constraints.

The C-like languages in this paper generate synchronous hardware (except Cones, which generates combinational logic, and CASH, which generates asynchronous), so there must be a mechanism for dividing time into clock cycles. Solutions range from mandatory cycle annotations to implicit rules.

A designer using Ocapi specifies state machines and each state gets a cycle. State machines in the SpecC refinement flow may start with implicit clock boundaries, but they are made concrete eventually. SystemC's combinational processes become combinational logic, but its sequential processes denote cycle boundaries with wait calls.

Typical in high-level synthesis, HardwareC supports timing constraints such as "these three statements must execute in two cycles." While such constraints can be subtle for the designer and challenging for the compiler, they allow easier design-space exploration. Bach C is similar.

The C2Verilog compiler inserts cycles using complex rules and provides mechanisms for imposing timing constraints. Unlike HardwareC, these constraints are outside the language.

Transmogrifier C and Handel-C use implicit rules for inserting clocks. In Handel-C, only assignment and delay statements take a clock cycle. In Transmogrifier C, only loop iterations and function calls take a cycle. While simple to understand, such rules can require recoding to meet timing. Handel-C may require assignment statements to be fused and loops may need to be unrolled in Transmogrifier C.

Table 1 :

 1

C-like languages/compilers (chronological order). classes provide mechanisms for specifying datapaths, finitestate machines, etc. (Paško et al. [16] adds RAM interfaces). The result is translated into a language such as Verilog and synthesized. Lipton et al.'s PDL++ [14] is similar. C2Verilog, developed at CompiLogic (renamed C Level Design then bought by Synopsys in November 2001) has truly broad support for ANSI C. It can translate pointers, recursion, dynamic memory allocation, and other thorny C constructs. Soderman and Panchul

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Edwards is supported by an NSF CAREER award, a grant from Intel corporation, an award from the SRC, and from New York State's NYSTAR program.


Himanshu Kaul

Dennis Sylvester

David Blaauw

Trevor Mudge

Todd Austin

DVS for On-Chip Bus Designs Based on Timing Error Correction

On-chip buses are typically designed to meet performance constraints at worst-case conditions, including process corner, temperature, IR-drop, and neighboring net switching pattern. This can result in significant performance slack at more typical operating conditions. In this paper, we propose a dynamic voltage scaling (DVS) technique for buses, based on a double sampling latch which can detect and correct for delay errors without the need for retransmission. The proposed approach recovers the available slack at non-worst-case operating points through more aggressive voltage scaling and tracks changing conditions by monitoring the error recovery rate. Voltage margins needed in traditional designs to accommodate worst-case performance conditions are therefore eliminated, resulting in a significant improvement in energy efficiency. The approach was implemented for a 6mm memory read bus operating at 1.5GHz (0.13 m technology node) and was simulated for a number of benchmark programs. Even at the worst-case process and environment conditions, energy gains of up to 17% are achieved, with error recovery rates under 2.3%. At more typical process and environment conditions, energy gains range from 35% to 45%, with a performance degradation under 2%. An analysis of optimum interconnect architectures for maximizing energy gains with this approach shows that the proposed approach performs well with technology scaling.

Introduction

On-chip buses can contribute a significant portion of the total power consumption. This is especially true for high performance and communication-centric designs, where the buses are long and are heavily buffered to meet aggressive delay targets. Due to increased wire delays and longer wire lengths, on-chip communication is often performance critical and directly impacts the processor cycle time. The design parameters of a bus (pitch, number and size of repeaters, shield wires, etc.) must be chosen to meet the timing constraints under worst-case conditions, including switching behavior of neighboring wires, process corner and environment (IR-drop and temperature) conditions. The probability of all worst-case conditions occurring simultaneously is usually small and hence, the bus is faster than it needs to be for more common case operating conditions. In this paper, we propose a method for dynamically scaling down the supply voltage for typical case conditions, resulting in significant energy reduction while still meeting delay constraints.

Various layout [START_REF] Sylvester | Getting to the Bottom of Deep Submicron II: A Global Wiring Paradigm[END_REF][START_REF] Mui | A Global Interconnect Optimization Scheme for Nanometer Scale VLSI With Implications for Latency, Bandwidth, and Power Dissipation[END_REF], repeater sizing [START_REF] Kapur | Power Estimation in Global Interconnects and its Reduction Using a Novel Repeater Optimization Methodology[END_REF][START_REF] Banerjee | A Power-Optimal Repeater Insertion Methodology for Global Interconnects in Nanometer Designs[END_REF] and encoding [START_REF] Stan | Low-Power Encodings for Global Communication in CMOS VLSI[END_REF][START_REF] Sotiriadis | Analysis and Implementation of Charge Recycling for Deep Sub-micron Buses[END_REF] solutions have been proposed for reducing power consumption in on-chip buses. However, these approaches are focused on improving energy efficiency at the worst-case conditions and do not take advantage of the potential energy reduction at more typical operating conditions. Hence, they are orthogonal to the approach proposed in this paper. Also, supply voltage scaling is a Memory Fig. 1. DVS memory read bus with double sampling flops. more powerful method for energy reduction, since it can ideally result in a quadratic savings in energy, without any routing area overhead. Dynamic voltage scaling (DVS) for energy reduction is not a new concept in general, but its application for on-chip buses operating in non-worst-case conditions has not been explored previously.

The traditional approach to DVS exploits fluctuations in the computational requirement of an application and scales down the frequency and voltage during periods of low performance utilization [START_REF]Intel SpeedStep Technology[END_REF][START_REF] Corp | LongRun Power Management[END_REF]. However, this approach does not exploit the variation in operating conditions and therefore still incorporates substantial margins to accommodate worst-case conditions. In this paper, we formulate the problem as reducing energy while maintaining the same clock frequency, noting that this approach can be combined with traditional DVS as well. A number of approaches were proposed that embed self-tuning circuits to provide dynamic reduction of the supply voltage and/or clock frequency.

The so called Correlating VCO [START_REF] Burd | A Dynamic Voltage Scaled Microprocessor System[END_REF][START_REF] Gutnik | An Efficient Controller for Variable Supply-Voltage Low Power Processing[END_REF] and Delay Line Speed Detector [START_REF] Dhar | Closed-Loop Adaptive Voltage Scaling Controller For Standard-Cell ASICs[END_REF] schemes use a circuit under test that mimics the critical path delay on the chip and the voltage for the chip is changed based on the speed of this test circuit. Duplicating a bus would result in a huge area overhead, making such techniques impractical for designs with buses as the critical path. In a different tuning approach, the actual circuit performance is tested periodically with worst-case latency vectors using a so-called Triple-Latch Monitor [START_REF] Kehl | Hardware Self-Tuning and Circuit Performance Monitoring[END_REF]. Though this approach can adjust to more local performance conditions, it cannot take advantage of typical latency vectors. Also the power overhead can be substantial for bus designs since worst-case vectors need to be propagated through the bus for evaluating the operating condition at regular intervals. Finally, IR-drop at repeater blocks in a bus are strongly dependent on the input vectors due to the large size of repeaters and their influence on IR-drop. In this case, the Triple Latch Monitor cannot take advantage of typical delays and IRdrop on a bus.

A key characteristic of the previous approaches is that they ensure correct operation at all times, and hence require additional safety margins which reduce their power efficiency. This paper proposes a more aggressive voltage scaling technique that is based on dynamic detection and correction of delay errors. Error recovery is incorporated in the bus architecture by employing a modified flip-flop that samples its input at the normal clock as well as at a delayed clock and was previously proposed for use in logic pipeline designs in [START_REF] Ernst | Razor: A Low-Power Pipeline Based on Circuit-Level Timing Speculation[END_REF]. If a difference between the 2 samples is detected, a control signal from the flop indicates that the data captured by the normal clock is incorrect and an error recovery mechanism ensures that the correct data value (that was sampled by the delayed clock) is propagated, while also ensuring that the incorrect data from the previous cycle is flushed out from the next stage.

A major advantage with the proposed approach is that error recovery does not require a failing vector to be retransmitted on the bus, providing great potential for energy reduction on the bus with a smaller energy overhead for error recovery. At the same time, all local performance conditions, including IR-drop and neighboring switching patterns, are accounted for by the approach, allowing for the removal of all voltage safety margins. In the proposed approach, the voltage is increased only when not doing so would result in an unacceptable number of delay error corrections, thereby significantly improving the energy efficiency.

We implemented the proposed approach for a memory read bus of an Alpha processor design. Fig. 1 shows the schematic of the system level implementation that would be required for this approach. The bus feeds into the memory unit of the execution core, where load data is typically held in a buffer before being committed to an architectural state. The original flip-flops that hold the load data can be replaced by the double-sampling flipsflops and timing errors can be handled in a manner similar to cache misses and speculative loads, with a one cycle penalty for error recovery. A similar mechanism will be required for handling the non-deterministic latency (in cycles) with this approach for other types of buses.

The remainder of this paper is organized as follows. The delay error detection and correction flip-flop is discussed in Section 2, along with its implications on the bus design. The simulation framework is discussed in Section 3. The impact of statically scaled supply voltage on error-rates and energy reductions for a range of benchmark programs is presented across a range of possible process, voltage drop and temperature (PVT) corners in Section 4. In Section 5, a simple voltage regulation system in conjunction with the proposed bus design is simulated for gauging the energy savings possible by dynamically scaling supply voltages to take advantage of the difference in switching activities across programs. Interconnect architectures that favor increased voltage scaling for a bus with the proposed approach are discussed and quantitatively analyzed in Section 6. The implication of this is discussed in the context of the efficacy of the proposed bus design for scaled technologies. Section 7 presents some concluding remarks.

Double sampling flip-flop Design

The proposed approach to DVS is based on the usage of a double sampling flip-flop (Fig. 2) for error detection and correction. In the absence of timing errors, the flop operates as a traditional master-slave flip-flop. When the input of the flop does not meet the setup time for error-free operation, the correct input is captured by the shadow latch since it is controlled by a delayed clock (with respect to the main flip-flop). The presence of a timing error in the previous cycle is signaled by the Error_L signal, which is an XOR function of the data in the slave latch and the shadow latch. Upon assertion of the Error_L signal, the correct data is restored in the flop through the multiplexer placed in the feed back path of the master latch. The design approach does need to be conservative to allow for data to be captured correctly by the shadow latch at the minimum allowable voltage under worst-case operating conditions. The local error signals (Error_L) of all the individual flip-flops in a bank that lie between two pipeline stages are ORed to produce an error signal that indicates a timing error in the previous pipeline stage. This signal is polled by the control system to measure error rates and is also used for triggering the error recovery mechanism in the architecture. Error correction requires at least a one cycle penalty since the incorrect data that was sent to the next stage needs to be flushed out before the correct data from the shadow latch is re-transmitted. The extra cycle penalty for timing errors could be accommodated by the processor in similar ways that cache misses are handled and the performance (IPC) may not necessarily degrade by the same amount as the error-rate (especially for out-of-order execution).

This error detection and correction capability comes at the cost of a much increased hold-time constraint with the flip-flop. As a result it needs to be ensured that the delays of short paths that feed into a shadow latch never violate the increased hold-time constraint. This hold constraint limits the amount of clock delay that can be accommodated on the shadow latch and hence the degree of voltage scaling below the point of first failure that can be exploited in the DVS scheme. In bus structures, however, the difference between short and long path delays is much less than that in logic circuits, making bus structures highly suitable for this approach of error detection and correction. In our analysis, it was found that the shadow latch clock could be delayed by as much as 33% of the clock cycle without violating the short-path constraint.

With each error recovery in the flop, a performance and energy penalty is incurred. The energy penalty with error-recovery stems from the energy consumed in the error detection/recovery logic and the re-execution of instructions when recovering from an error. As supply voltage is lowered the energy savings increase at the cost of increased error-rates. The trade-off between bus energy reduction and the energy penalty associated with increasing error rates as supply voltage is scaled down implies an optimal supply voltage exists at which the total energy with the DVS approach is optimal. Hence, the voltage must be controlled such that the energy optimal error rate is not exceeded. In addition, the performance impact of error recovery places limits on the acceptable error rate. In our experiments, a maximum average error rate of 2% was used, and was found to provide substantial energy savings while incurring negligible performance impact.

Simulation framework

A 6mm 32-bit bus (Fig. 3) routed on a global metal layer of a 0.13 m CMOS process at minimum pitch (0.8 m) is used for analyzing the impact of the DVS approach on a memory read bus. A nominal supply of 1.2V is used. Capacitance extraction is performed with a 2D field-solver. A 1.5mm inter-repeater

in[0] 6mm in[1]
in [START_REF] Mui | A Global Interconnect Optimization Scheme for Nanometer Scale VLSI With Implications for Latency, Bandwidth, and Power Dissipation[END_REF] in [START_REF] Kapur | Power Estimation in Global Interconnects and its Reduction Using a Novel Repeater Optimization Methodology[END_REF] in distance is used with shield wires inserted after every 4 wires. Such a shield insertion interval (in terms of wires) is a typical design practice for limiting noise and inductive effects for wide buses [START_REF] Kumar | Interconnect and Noise Immunity Design for the Pentium 4 Processor[END_REF]. The receiver end of the bus feeds into the input of a flip-flop (not shown in the figure). A fixed clock frequency of 1.5GHz is assumed. The repeaters are sized so that the maximum delay (measured from node in to node out) on the bus is 600ps (allowing 10% cycle time slack for set-up time and clock skew). The maximum delay is measured under worst-case conditions of neighbor switching activity and the PVT conditions, i.e., slow process corner, temperature of 100C and a voltage (IR) drop of 10%. This sizing approach reflects a typical design philosophy to ensure that the performance target is achieved even under worstcase conditions with a fixed supply voltage.

The bus is analyzed for performance and energy with the DVS approach over millions of cycles of program execution. In order to reduce the simulation complexity, while maintaining SPICE-level accuracy, the delays (for every wire) and energy consumption on the bus are tabulated for all possible data input combinations using HSPICE. Such look-up tables are created for individual supply voltages (in increments of 20mV) over a range of supply voltages and also for different combinations of process corner and temperature. Leakage current through the repeaters is also tabulated for the different supply voltages and environment conditions so as to include the contribution of leakage energy to the total bus energy.

For evaluation purposes we use the data trace on the memory read bus from 10 of the SPEC2000 benchmarks. The data trace for each benchmark is obtained by modifying the sim-safe simulator in the SimpleScalar/Alpha version 3.0 toolset [START_REF] Austin | SimpleScalar: an Infrastructure for Computer System Modeling[END_REF]. The simulations were run using the SPEC reference inputs. We used the SimPoint toolset's Early SimPoints to pinpoint 10 million instruction trace sequences that were highly representative of the entire program execution [START_REF] Sherwood | Automatically Characterizing Large Scale Program Behavior[END_REF]. Each instruction is assumed to represent a single clock cycle (IPC=1). All error-rate analysis is based on the number of resulting bus timing errors (with correct data captured by the shadow latch) during a window of program instructions. A single bus timing error represents the assertion of the error signal by one or more error detecting flip-flops in the bank in a single cycle. The number of errors based on clock cycles for the actual system architecture will yield lower error-rates since the same number of errors will occur in a larger time window due to the fact that IPC in a pipeline is typically less than 1. Therefore, the error rates reported in the paper are pessimistic. From a performance perspective, the reduction in IPC for a particular error rate is highly dependent on the architecture and the specific program. For the sake of simplicity, we assume a 1 cycle penalty for error recovery and translate this to a reduction in performance (IPC) that is the same as the error-rate.

Voltage scaling and PVT corner impact on error rate

Since the proposed approach relies on error correction at aggressively scaled supply voltages, it is necessary to gauge the effect of scaling supply voltages under different PVT corners on the resulting error rates since it can determine the performance degradation and the energy overhead from error correction. The different process corners used are slow, typical and fast. For local voltage conditions on the repeaters/drivers, either no IR drop is assumed or a 10% droop in supply voltage is assumed for any particular supply voltage when delay is calculated. The temperature conditions assumed are either 25C or 100C. For different combinations of process, IR drop and temperature, the benchmark programs were simulated over a range of supply voltages for all PVT corners.

The effect of scaled supply voltages for 2 different PVT corners is shown in Fig. 4. Every point on the energy and errorrate curves represents combined energy and error rates of running all the benchmark programs (with each one being run for 10 million cycles) at the specific supply voltage. The supply voltage is scaled only up to the point where the longest bus delay can still meet the setup time of the shadow latch for the specific PVT corner. Since the bus was designed to operate error-free for the worst case condition (same as that used for Fig. 4a), the error rates increase as soon as the supply voltage is lowered below the nominal 1.2V supply. For a faster PVT corner, the same performance can be maintained while supply voltage can be scaled. This is evident in Fig. 4b, where no errors are introduced up to a 980mV supply.

For every error, there is an energy overhead involved in retransmitting the correct data to the processor pipeline. Since only a small fraction of the flops in a bank typically result in errors, most of the extra energy consumption usually comes from clocking all the flip-flops for an extra cycle. The effect of this over head is also shown in Fig. 4 and is very small compared to the energy savings on the bus. The error-correction overhead will be higher when the entire pipeline is considered and would also depend on the architecture. Since we are examining the bus in isolation, we choose error rates from the perspective of performance degradation, which closely tracks the error-rates.

The effect of 3 different target error rates (0%, 2% and 5%) is examined. If a PVT corner results in a faster bus, the supply voltage can be scaled further to achieve the same error rate under the delay constraint. In Fig. 5 the delay spread on the normal bus (at VDD=1.2V) from the various PVT corners is shown on the X-axis. The energy gains achievable by operating the bus at the lowest supply voltage that does not result in exceeding the target error rate for the PVT corner are shown on the Y-axis. As expected, the energy gains for a target error rate increase as the PVT corner results in a faster bus, with gains of 35% for the typical process corner with no performance degradation. Also, if the higher error rate of 5% can be tolerated, the gains are higher. The gains from 0% and 2% error rates are indistinguishable. This results from the fact that the error rates jump directly from 0 to above 2% for the used supply voltage discretizations (of 20mV).

Though we treat each of the performance dictating factors independently (for the sake of simplicity), the process corner is the only true independent variable while the IR drop and temperature can also be functions of the specific program. Incorporating such dependencies would involve complex models. The goal of the analysis is to show the range of energy gains possible for the range of performance dictating conditions.

Energy Reduction with Proposed DVS Scheme

The bus switching activity can vary from one program to another and even during a single program execution. The results of the previous section do not reflect the energy gains possible if the supply voltage is scaled during program execution while still maintaining a target error rate. The in-situ error rate measurement capability of the proposed approach can allow further energy gains (on top of those available from PVT corners) for individual programs by taking advantage of the bus switching activity.

To illustrate the dependence of dynamic supply scaling on program behavior we first examine the optimal supply voltage selection (with the knowledge of future program switching behavior) over time while maintaining a fixed error rate. For different target error rates, the percentage of time that the bus spends over various supply voltages during the execution of 3 different programs is shown in Fig. 6. When no errors are tolerated (not shown in figure), all the programs run at the supply voltage that the specific PVT corner allows for zero error operation -the energy gains being dictated only by the PVT corner. If a small percentage of error rates can be tolerated, the optimal supply voltages during program execution can vary widely from one program to another. For a target error rate of 2% crafty can run at 900mV during most of the program execution, while the supply cannot be reduced below 980mV even with a target error rate of 5% for mgrid.

In an actual system, it is not possible to guarantee a target error rate since there is delay involved in changing the supply voltage with a regulator and the switching activity for a block of time in the future cannot be known a priori. A simple voltage supply control system (Fig. 7) is simulated with the bus during program execution. The system calculates errors generated by the bus in 10,000 cycles using an error counter that is incremented by the Error signal from the bank of flip-flops. The counter is reset after every 10,000 cycles. The voltage controller changes the voltage based on the error rate in the last 10,000 cycles. The system tries to maintain error rates between 1% and 2% (which is a reasonable trade-off of performance for energy gains). If the error rate is less than 1%, the supply voltage is reduced by 20mV and if it is greater than 2%, supply voltage is increased by 20mV. A more sophisticated proportional control system could have been used that results in voltage changes proportional to the magnitude of error difference between the target and sampled error rates. Since the error-rate of the bus is a non-linear function of supply voltage, it is not possible to calculate the transfer function for the bus. Calculation of the proportionality constant for such a system would not be trivial. Also, the simpler system that we have simulated is shown to work reasonably well without the hardware overhead of a more sophisticated system. Since the voltage regulators take time to adjust the voltage (typically around 1 s/10mV), the supply voltage on the bus is changed by 20mV only after a delay of 2 s (3000 cycles at 1.5Ghz operation) after the decision to change the supply voltage is taken by the regulator. The minimum voltage allowed by the regulator is chosen conservatively for the bus to meet the setup time of the shadow latch. The only factor that we have used for tuning (the minimum allowable voltage by the regulator) is the process corner since that does not change with time. is such that shadow latch setup time is met for typical process, 100C and 10% IR drop. Table 1 lists the energy reductions possible with two voltage scaling schemes. The fixed voltage scaling (VS) scheme is a generic representation of other voltage scaling schemes that can only account for global process variations and have conservativeness built into them since they cannot handle timing errors. The proposed DVS scheme is as discussed earlier in the section. For the worst-case PVT corner (slow process, 100C, 10% IR drop), no energy gains are possible with zero error rates (fixed VS), while the implemented DVS results in 1% to 17% energy gains across the benchmarks. Any energy gains at this PVT corner with the proposed DVS are possible only by taking advantage of the unique program switching activities on the bus. Though the combined error-rate for all the programs with the implemented DVS system is less than 2%, 2 programs result in average error rates that are slightly higher than the target. Note however, that while the error rate cannot be guaranteed, correct operation using error recovery is always ensured. At the faster PVT corner (typical process, 100C, no IR drop), the difference between fixed VS and implemented DVS is even higher because the fixed VS scheme can lower supply voltage only up to the point where error-free operation is guaranteed with 10% VDD drop. The fixed VS scheme cannot take advantage of the fact that there may not be any VDD drops in the actual design. At the faster PVT corner all programs finish with individual average error rates within 2% and overall energy gains of 38.6%, while individual programs show gains from 35% to 45%.

The variation in supply voltage and instantaneous (i.e., over a time period of 10000 cycles) error rates for the faster PVT corner of Table 1 are plotted in Fig. 8. The supply voltage is assumed to start from the nominal 1.2V. The programs are run consecutively (each one running for 10 million cycles) and the region of individual program executions is demarcated by the same numerical ordering as in Table 1. For the error rates, each dot represents the error-rate over the period of 10000 cycles. It is evident that the proposed DVS control system can adjust for the PVT corner as well as the switching activity that is unique to every program. The supply voltage and error-rates exhibit unique patterns for each program and the switch from one program to another is clear. As mentioned above, though the average errorrates (from the execution of 10 million instructions of a program) for the programs are within the 2% target, the instantaneous errorrates can be well over the target (reaching as high as 6% in Fig. 8) during execution. The main reason for this is the delay involved in ramping up the voltage by the controller when high error rates are observed.

Interconnect Architecture and Technology Scaling

The proposed approach to DVS provides advantages similar to that of asynchronous design -maximize gains for typical case operation rather than worst-case. The maximum amount of supply lowering with the proposed approach is primarily limited by the error rates. For a particular error-rate constraint, a design that does not change the worst-case delay while improving the typical case delay allows the supply voltage to be lowered further before the error rate constraint is reached.

The electrical equivalent of an interconnect wire is shown in Fig. 9. The line of interest has a signal V while A0 and A1 serve as neighboring aggressors. Switching pattern I results in worst-case delays on the wire. The Elmore delay for such a switching pattern is : t D = R ( Cg + 4 Cc) (1) This switching pattern is responsible for the initial (and acceptable) increase in error rates as supply voltages are reduced. When the supply voltage is reduced to a point where delay (for error-free operation) cannot be met with switching pattern II, the error rates immediately jump to a higher, and often unacceptable level (>10%). The difference in Elmore delays between pattern I and pattern II is:

t D = R Cc (2)

Fig. 2 .

 2 Fig. 2. Circuit schematic of double sampling flip-flop.

Fig. 4 .

 4 Fig. 3. Bus setup.

Fig. 5 .

 5 Fig. 5. Energy gains for target error rates over the delay spread (for non-DVS bus) that can occur from the range of PVT corners.

Fig. 6 .

 6 Fig. 6. Optimum supply voltage distribution during execution for 3 programs while maintaining constant error rates. The PVT corner used is typical process, 100C and no IR drop.

Fig. 8 .

 8 Fig. 8. Supply voltage and instantaneous error rates during execution of the benchmark programs for the PVT corner of Typical Process, 100C, No IR drop. Regions of benchmark execution are labeled by the same numbers as the numerical order inTable1. Error rates may appear overlapped in time due to resolution limitations.

Table 1 . Energy gains with 2 DVS schemes for 2 PVT corners.

 1 Otherwise, worst case conditions of temperature and IR drop are assumed. For example, if the PVT corner is typical, 100C and no IR drop, minimum voltage allowed

	Bus

Table 1 . Error rates may appear overlapped in time due to resolution limitations.

 1

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Reset

Wire layout geometries that increase this difference between these delays (by increasing the Cc/Cg ratio) allow the bus to operate at lower supply voltages with the proposed DVS method for the same non-zero error rate constraint, provided the worst case delay remains unchanged. Since the fastest delay on the bus reduces with this approach, the delay to the shadow latch clock would need to be reduced. This limits the minimum voltage that the bus can operate at. Since the power savings with this approach are limited more by the acceptable error-rate rather than the absolute minimum supply voltage that can be operated, this is a reasonable trade-off.

We alter the wire parasitics of the bus so that the Cc/Cg ratio is 1.95X that of the original bus while ensuring that the wire resistance and total effective capacitance (Cg + 4Cc) for worstcase delay does not change. Repeater sizes are unchanged since the worst-case delay does not change. The worst-case switching delay remains unchanged across all PVT corners. Static voltage scaling at various PVT corners confirmed that the voltage could be scaled by a further 20mV (than original bus) for almost all PVT corners before reaching the error-rate constraint. The results for energy gains across PVT corners are shown in Fig. 10. The curve for zero error rates does not change since the maximum delay does not change. The 2% and 5% error-rate curves show slightly higher energy gains. Simulations with the proposed voltage control system of the previous section also showed increased energy gains for all programs, with the average energy gain for the worst-case PVT corner (slow process, 100C, 10%IR drop) increasing from 6.3% (in Table 1) to 8.2%. The error rate for all the programs with the proposed DVS bus is still within the target of 2%.

With scaled technologies, the wire capacitance does not change appreciably [START_REF] Ho | The Future of Wires[END_REF], while the wire resistance increases. As a result, the delay spread on wires due to neighbor switching activity increases (since the R Cc term in (2) increases). The proposed bus design results in a higher energy savings with an increased difference in delay between worst-case and more typical switching activities and, therefore, can be expected to scale well with technology.

Conclusions

A DVS approach for energy reduction in on-chip buses with double sampling flip-flops has been proposed. The proposed bus design allows aggressive voltage scaling since it provides recovery from timing errors without retransmission of failed data on a bus. A 6mm memory read bus that was designed to operate at 1.5Ghz (for a 0.13 m CMOS technology) under worst-case conditions was analyzed using this approach. An extensive analysis of the effect of static voltage scaling across a range of PVT corners showed that if voltage is scaled down to reduce any available slack (while maintaining the same clock frequency) at a particular PVT corner, energy gains up to 48% are possible even with no error rates. The gains increase if slightly higher error-rates can be tolerated. A voltage regulation system to allow dynamic voltage scaling and take advantage of typical switching activities during program execution was also tested. Even at the worst-case process and environment conditions, energy gains up to 17% were achieved for individual programs, while at more typical process and environment conditions, the energy gains range from 35% to 45%. These energy gains were achieved with less than 2% impact on performance. The effect of interconnect geometries that favor increased voltage scaling for a bus with the proposed approach was analyzed and the results indicate that the approach should scale favorably with interconnect scaling.


Le Cai

Yung-Hsiang Lu

Joint Power Management of Memory and Disk *

This paper presents a scheme to combine memory and power management for achieving better energy reduction. Our method periodically adjusts the size of physical memory and the timeout value to shut down a hard disk for reducing the average power consumption. We use Pareto distributions to model the distributions of idle time. The parameters of the distributions are adjusted at run-time for calculating the corresponding timeout value of the disk power management. The memory size is changed based on the inclusion property to predict the number of disk accesses at different memory sizes. Experimental results show more than 50% energy savings compared to a 2competitive fixed-timeout method.

Introduction

Power reduction has become a major goal in system designs. Among all components, the storage hierarchy (cache, memory, and disks) consumes a significant percentage of power. In a data center, storage devices can consume over 25% power [START_REF] Zhu | Reducing Energy Consumption of Disk Storage Using Power-Aware Cache Management[END_REF]. Many studies have been conducted to reduce memory's power consumption [START_REF] Hu | Let Caches Decay: Reducing Leakage Energy Via Exploitation of Cache Generational Behavior[END_REF][START_REF] Lebeck | Power Aware Page Allocation[END_REF] or disks' power consumption [START_REF] Gniady | Program Counter Based Techniques for Dynamic Power Management[END_REF][START_REF] Zhu | Reducing Energy Consumption of Disk Storage Using Power-Aware Cache Management[END_REF]. However, the close relationship between memory management and power management has not been fully investigated. We use an example to illustrate the importance of combining memory management and power management.

Adding memory often improves performance by reducing the numbers of disk accesses. However, when power management is adopted, more memory may actually degrade performance and increase power consumption. For example, when a system's physical memory increases, more data reside in memory so the disk becomes idle and enters a lowpower ("sleep") state more often. If the memory is not large enough, the system accesses the disk soon.

Since it has to wake up on-demand, the disk saves insufficient energy to compensate the spin-up energy and the system actually consumes more energy. The minimum spin-down time to save energy is called break-even time [START_REF] Lu | Quantitative Comparison of Power Management Algorithms[END_REF]. Moreover, the performance degrades due to the disk's wakeup delayusually several seconds or billions of cycles. This example shows that adding more memory may increase the overall power consumption and degrade performance even though disk accesses occur less frequently. If we further increase the memory size, the disk can remain spinned-down longer to save more energy but the savings may not compensate the power consumed by the additional memory. It is essential to combine memory management and power management to reduce power consumption and to improve performance. This joint management method is different from previous adaptive disk power management methods [START_REF] Douglis | Adaptive Disk Spin-down Policies for Mobile Computers[END_REF][START_REF] Lu | Adaptive Hard Disk Power Management on Personal Computers[END_REF] because they respond to the changes of disk accesses without actively adjusting memory sizes.

This paper presents a technique using operating systems to perform joint power and memory management for physical memory and hard disks. We assume that part of memory can be turned on and off, as suggested in [START_REF] Hu | Let Caches Decay: Reducing Leakage Energy Via Exploitation of Cache Generational Behavior[END_REF][START_REF] Lebeck | Power Aware Page Allocation[END_REF], to reduce power and to improve performance. We change the memory size by allocating or releasing reserved memory pages in operating systems since reserved pages are unavailable to application programs. We adopt the timeout policy to manage the disks for three reasons: (a) Timeout is widely used and outperforms many policies [START_REF] Lu | Quantitative Comparison of Power Management Algorithms[END_REF]. (b) It assists some other policies, such as timeindex stochastic optimization [START_REF] Simunic | Event-Driven Power Management[END_REF]. (c) It is used as a "backup" scheme when a prediction policy has insufficient history to predict [START_REF] Gniady | Program Counter Based Techniques for Dynamic Power Management[END_REF]. The objective of this study is to determine two parameters at run-time: the timeout value for shutting down the disk and the size of the physical memory. Our method considers the interactions between the memory and the disk to minimize the energy consumption.

Two major challenges exist in the joint management: (a) determining disk IO (the number and the interarrival time) at different sizes of memory without running the same programs multiple times and (b) adjusting the timeout values without offline analysis. We use the concept of the ghost buffer [START_REF] Mattson | Evaluation techniques for storage hierarchies[END_REF][START_REF] Patterson | Informed Prefetching and Caching[END_REF] to predict the number of disk accesses at different memory sizes. The ghost buffer records replaced memory pages as if they are stored in additional physical memory. With the recorded information, the ghost buffer can determine how many disk accesses can be eliminated by adding certain amount of memory. We model the distributions of interarrival time of disk accesses as Pareto distributions. This is because previous studies [START_REF] Simunic | Dynamic Power Management for Portable Systems[END_REF][START_REF] Vogels | File System Usage in Windows NT 4.0[END_REF] and our analysis of HP disk traces [START_REF] Ruemmler | UNIX Disk Access Patterns[END_REF] show Pareto distributions can closely model disk IO. We evaluate the joint management using a web server and use SPECweb99 as the benchmark. Our experiment results show that the joint method can save more than 50% energy compared with a 2-competitive fixedtimeout method.

Background

Power-Aware Storage Hierarchy

Hu et al. [START_REF] Hu | Let Caches Decay: Reducing Leakage Energy Via Exploitation of Cache Generational Behavior[END_REF] turn off individual cache lines whose data are unlikely to be accessed again. Their method is 2-competitive by turning off a cache line 10000 cycles after the last access. Lebech et al. [START_REF] Lebeck | Power Aware Page Allocation[END_REF] use multiple power modes of RDRAM and dynamically turn off memory chips with power-aware page allocation in operating systems. These studies suggest that future memory should support power management to turn on/off part of the memory. The energy to turn on and off memory chips is negligible compared with the memory's static energy. For example, a 64MB RDRAM chip consumes less than 1µJ energy to change from a power-down state to an active state [START_REF] Lebeck | Power Aware Page Allocation[END_REF]. Zhu et al. [START_REF] Zhu | Reducing Energy Consumption of Disk Storage Using Power-Aware Cache Management[END_REF] show that lower miss rates do not necessarily save disk energy. A power model of hard disk is presented by Zedlewski et al. [START_REF] Zedlewski | Modeling Hard-Disk Power Consumption[END_REF]. Papathanasiou et al. [START_REF] Papathanasiou | Energy efficient prefetching and caching[END_REF] use prefetching to prolong the idle time of hard disks so that they may stay off to save power. Two recent studies calculate the sizes of prefetching buffers to optimize power savings [START_REF] Cai | Dynamic Power Management Using Data Buffers[END_REF][START_REF] Pettis | Power Management by Prefetching Streaming Data[END_REF]; both studies assume streaming data that are not reused. Gurumurthi et al. [START_REF] Gurumurthi | DRPM: Dynamic Speed Control for Power Management in Server Class Disks[END_REF] propose adjusting the rotation speed of disk platters to reduce power consumption. Their approach is similar to frequency scaling in processors. Timeout is often used to predict long idle periods. Simunic et al. [START_REF] Simunic | Dynamic Power Management for Portable Systems[END_REF] present a time-indexed Markov chain stochastic model to optimize power management policies based on Pareto distribution. Douglis et al. [START_REF] Douglis | Adaptive Disk Spin-down Policies for Mobile Computers[END_REF] dynamically adapt the disk timeout to save energy while meeting the performance requirements. Lu et al. [START_REF] Lu | Adaptive Hard Disk Power Management on Personal Computers[END_REF] divide disk accesses into different sessions; the method dynamically changes the timeout based on the predicted duration of each session. These two methods respond to the changes of disk IO patterns. In contrast, our method proactively changes disk IO by adjusting the size of physical memory.

Memory Size and Disk IO

Changing memory size can affect disk IO and power consumption because more memory may reduce disk accesses and allow the disk to sleep longer. One approach to obtain these relationships is running the same program multiple times with different memory sizes. This is time-consuming and impossible if the programs need run-time inputs. Franklin et al. [START_REF] Franklin | Computation of Page Fault Probability From Program Transition Diagram[END_REF] use Markov chains to model the probabilities of page faults with different memory sizes. Their method needs all memory references in advance so it only applies to offline analysis. Mattson et al. [START_REF] Mattson | Evaluation techniques for storage hierarchies[END_REF] use the inclusion property of many memory replacement algorithms: the content of smaller-size memory is a subset of the content of larger memory for the same memory access sequence. We use the least recently used (LRU) replacement algorithm as an example. An LRU list records the most recently accessed memory pages. If there are q pages, the LRU list stores q most recently accessed pages. If there are s pages and s < q, the list of s pages is a subset of the list of q pages. Any reference to the s most recently accessed pages hits in memory when the memory size is either s or q pages. When the memory size is s pages, the references to the (s + 1) th to q th most recently accessed pages are misses. These accesses hit in memory when the size is q page. If we count the references to the (s + 1) th to q th most recently accessed pages, we can obtain the relationship of memory sizes and the number of disk accesses. Specifically, we know the additional number of disk accesses when the memory size changes from q pages to s pages. This method can apply to determining the effect of shrinking the physical memory. The same method is used to online predict page miss ratio [START_REF] Zhou | Dynamic tracking of page miss ratio curve for memory management[END_REF].

To determine the effect of enlarging the physical memory, a "ghost buffer" [START_REF] Patterson | Informed Prefetching and Caching[END_REF] is used to record replaced pages. All pages in the ghost buffer form a doubly-linked list and they are ordered based on the time when they are replaced. Different from the LRU list, the ghost buffer stores only the tags, such as their inode IDs and offsets in the file; no actual data are stored. Using the tags, we can uniquely identify a page. When disk accesses happen, the tags of the required pages are compared with the tags stored in the ghost buffer. A match means that an earlier replaced page is accessed again. This memory access would not cause disk IO if the memory size is larger and the page was not replaced. If the matched page is the i th page from the head of the ghost buffer, i pages memory is needed to keep this page in memory. Hence, by recording the position of the matched pages and the number of matches, this algorithm can determine the number of reduced disk accesses when adding memory pages.

Joint Management

The joint manager periodically determines the appropriate size of physical memory and the timeout value to spin-down the disk. We use T to represent the period length. Every period we record the number of disk accesses. Using this number and the information from the LRU list and the ghost buffer, our method predicts the disk accesses and the length distribution of the idle time during next period for the chosen memory size. The proper timeout and memory size are chosen based on the their relationships with the average power consumption. Table 1 lists the symbols used in our method.

Idle Time of Disks

Since disk accesses often occur in bursts, many idle periods are very short and provide no opportunity for power management. We remove these short idle periods by using a sliding window. If one disk access is followed by another and the idle time is smaller than the window length, this idle period is ignored. We use 0.1s as the window length since the break-even time of most disks is much larger than this value. Let be a random variable represent- ing the lengths of the disk's idle time. We model the probability by Pareto distributions:

f ( ) = αβ α α+1 , > β, α > 1 ( 1 )
Here, β is the length of the sliding window so all idle periods are longer than β. The value of α determines the distribution of . When α is small, it is more likely to have long idle periods. At run time, we can calculate the average idle time to determine α's value. Let E( ) represent the mean of :

E( ) = αβ α-1 . The value of α is E( ) E( )-β .
We estimate E( ) by the average length of idle time. For duration T , the average idle time is the ratio of T and the number of accesses: E( ) = T n . Here, n is the predicted number of disk accesses each T . We use the predicted value when the memory size changes (to be explained later). Hence, we obtain

α = T T -βn (2)
This paper considers only two power modes: on and off, but the method can be extended to more modes. To obtain the energy consumption of the disk, we compute the disk's off time from [START_REF] Cai | Dynamic Power Management Using Data Buffers[END_REF]. All idle periods longer than the timeout t o will trigger the disk to be turned off. The off time is the difference between the idle time and t o , i.e.t o . For the idle periods shorter than t o , there is no off time. The probability of an idle period longer than t o is ∞ to f ( )d . The average off time of each idle period is ∞ to (t o )f ( )d and there are n idle periods:

t s = n ∞ to ( -t o )f ( )d = n( β to ) (α-1) β α-1 (3)
If β is smaller than t o ( β to < 1), the off time is longer with a smaller α. From (1), we also compute the average number of the times to turn off disk each T . This number is used to compute the energy consumed to turn on and off disk.

n s = n ∞ to f ( )d = n( β t o ) α (4)
A smaller α means a larger n s because long idle periods are more likely. In each T the memory and the disk consume: (a) static energy for the disk and m pages of memory: p m mT +p d (T -t s ), (b) dynamic energy: e d n, and (c) turn-on energy: p d t be n s . Each time turning on and off disk consumes p d t be based on the definition of break-even time. We ignore the energy consumed to turn on and off memory because this energy consumption is much smaller than the static energy consumption of memory. We add (a) (b) and (c) to obtain the total energy in T :

p m mT + p d (T -t s ) + e d n + p d t be n s (5)
We use ( 3) and ( 4) to replace t s and n s in ( 5) to obtain the energy consumption represented by t o :

p m mT + p d [T - nβ α (α -1)t (α-1) o ] + e d n + p d t be n( β t o ) α (6)
We calculate the derivative of (6) with respect to t o and make it equal to zero.

p d n( β to ) α -p d n( β to ) α αt be to = 0 ⇒ t o = αt be (7)
The second derivative is positive when t o = αt be . Thus, we obtain the minimum power consumption when t o = αt be . Since a larger α indicates more short idle periods, increasing timeout can reduce the probability to turn off the disk during short idle periods. The timeout value also increases when the break-even time becomes larger. Larger break-even time means more energy is consumed to turn on and off disk; the power manager should increase timeout to avoid turning off the disk.

Number of Disk Accesses

The joint manager decides the memory size and the corresponding number of disk accesses using the LRU list and the ghost buffer. The manager counts the number of disk accesses in each T and predicts the access number for the next T . Let n i be the predicted number of accesses during [iT, (i + 1)T ]. We use a recursive formula to predict n i .

[2]=0 c[3]=0 c[1]=0 c[4]=0 c[2]=0 c[3]=0 c[1]=0 c[4]=0 c[2]=0 c[3]=0 c[1]=0 c[4]=0 a LRU list counters c[2]=0 c[3]=1 c[1]=0 c[4]=0 c[2]=1 c[3]=1 c[1]=0 c[4]=0 c[2]=2 c[3]=1 c[1]=0 c[4]=0
n i = kN i-1 + (1 -k)n i-1 ( 8
)
The values of N i-1 and n i-1 are the observed and predicted numbers of accesses in the previous period. We choose k = 0.5 to balance the recent number and the previous number since n i-1 is predicted from previous numbers. This is similar to the prediction used in [START_REF] Hwang | A Predictive System Shutdown Method for Energy Saving of Event-driven Computation[END_REF]: exponentially reducing the effect of previous observations and predictions.

Formula ( 8) represents the number of disk accesses when the memory size remains constant. We use the information from the LRU list and the ghost buffer to obtain the values of n i with different memory sizes. cess and require totally four accesses. The value of each counter indicates the additional disk accesses when the corresponding page is removed. The ghost buffer has the similar function except that the ghost buffer records the numbers of the accesses to the replaced pages. Thus, the ghost buffer can predict how many disk accesses can be removed by enlarging the memory size. We enumerate possible memory sizes with 1MB as the unit and compare the energy consumption. This enumeration needs little time because the memory size is generally within several thousand MBs and it is fast to compute the energy consumption from (6).

Experiment

Experiment Configuration

We implement our method in Linux 2.4.20. Each memory page has one entry in both the LRU list and the ghost buffer. Each entry uses 8 bytes for two integer variables recording the inode ID and the offset in file and 16 bytes for four pointers storing previous and next entries in two double-linked lists. Two integer counter arrays are used to count the references to the entries in the LRU list and the ghost buffer. We use the LRU list in Linux and only add the ghost buffer and two counter arrays. When the physical memory is 1GB, the ghost buffer and each counter array have 0.25M entries for 4KB pages. The overall memory usage is 0.25 * (8+16+4+4) = 8MB. An Apache web server and SPECweb99 benchmarks are used in the experiments. The numbers of simultaneous connections generate different amounts of workload. We conduct experiments under different connection numbers and each experiment lasts for one hour. One minute is chosen for T since it performs well in our experiments. Because of the space limitation, we will not discuss the detail of determining T . Table 2 lists the parameters in the experiments. The main memory is Micron MT48LC1M16A1S DRAM and we obtain its static power from the specification. We divide this power by the number of the memory pages to estimate the value of p m . We use p m to estimate the power consumption of different sizes of physical memory since no existing commercial memory chips allow run-time resizing. Therefore, the system actually has a constant size of physical memory. Our modified operating system restricts the available size to application programs in order to create the effects of varying memory sizes. In the experiments, the hard disk switches between the idle and the standby modes. The disk's off status refers to standby and p d is the power difference between the idle and the standby states. We use a Seagate ST340810A hard disk and it consumes 5.13W and 1.14W power in the idle and standby modes, respectively; the value of p d is 5.13 -1.14 = 3.99W. To obtain the dynamic energy of the hard disk (e d ) for accessing one page, we measure the disk's energy consumption under different workloads. After subtracting the static energy, we divide the difference by the number of accessed pages. The quotient is used as the disk's dynamic energy per page. The value of e d varies with the rate of disk accesses. Our experiments use the average value. We measure the energy consumed by the hard disk when it is switched from idle to standby and back to idle. This energy is divided by p d to calculate t be . The formulas derived in Section 3 are used to compute the energy consumption of the memory and the disk. Our method is compared with the 2-competitive timeout methods using t be as the timeout value. These timeout methods use the physical memory of the size from 64MB to 1024MB.

Energy Consumption

Figure 2 shows the power consumption of the joint management and the fixed-timeout methods with different memory sizes. When the memory size is 1 GB, the system consumes the most power and we use its power as the base (100%) for comparison. The workload varies from 10 to 70 client connections because the server starts denying requests when the number of connections exceeds 70. The figure shows that our method achieves the best power savings, from 48% to 62%. When the numbers of connections are below 30, the timeout method with 128 MB memory consumes comparable power with our management scheme. However, the power increases dramatically as the number of connections grows if the memory size remains 128 MB. This is because that the small memory size causes many disk accesses. In contrast, the power increases much slower with our scheme because it chooses appropri- ate memory sizes and timeout values as the workload varies. Table 3 lists the average memory sizes and the minimum and maximum timeout values used in the joint method. When the workload is light, the joint method uses a smaller size of memory to save power. When the workload becomes heavier, the joint method uses more memory to reduce disk IO and to reduce the disk's power consumption. For memory sizes above 256 MB, the power consumption remains almost constant. This is because large memory cannot completely eliminate all disk accesses. The workload varies even in an experiment with a constant number of client connections. The joint method adapts the timeout to the workload variation.

Conclusion

In this paper, we present a joint method for memory management and power management. This method uses the close relationship between memory management and disk IO to save power. Our method provides an analytic model to compute the proper disk timeout to minimize the energy consumption. We predict the number and the interarrival time of disk IO for different memory sizes without offline analysis. Our experimental results show that the joint method can save more power than timeout methods with fixed memory sizes.

Figure 1 .

 1 Figure 1. The reference count of LRU list.

  Figure 1 illustrates how to count the references to the LRU list for a system with four pages of physical memory. A counter array c[.] is used to record the reference number to each page in the LRU list. When the referenced page is the i th page from the head of the LRU list, the i th counter c[i] increases one. For example, the memory is accessed by a sequence of six references {a, b, d, a, d, a}. The first three references need disk accesses since pages {a, b, d} are not in memory. After these three references, the values of all counters are zero and the LRU list is {d, b, a}. The fourth reference is for page a, the third page in the list. The counter c[3] increments by one. The fifth access is d and it is the second page in the list; thus c[2] increments by one. Finally, the sixth access is page a again and it is the second in the list; c[2] increments by one. The final values of counters are {0, 2, 1, 0}. These values indicate that there is no access to the first and fourth page, two accesses to the second page, and one access to the third page. Since c[4] = 0, no additional disk access occurs if we reduce the memory to three pages. Because c[3] is nonzero, reducing the memory to two pages will add one (c[3] = 1) more disk ac-

Figure 2 .Table 3 .

 23 Figure 2. Power consumption of the joint method and fixed-timeout methods. The power consumption percentage is based on the timeout method with 1GB memory.

Table 1 . Symbols and their meanings.

 1

	symbol description
	N	observed number of disk accesses
	n	predicted number of disk accesses
	T	period (s)
	t o	disk timeout (s)
	t be	break-even time of disk (s)
	t s	off time each T (s)
	n s	times to turn off disk each T
	m	memory size (page)
	e d	disk dynamic energy (J/page)
	p d	disk static power (W)
	p m	static power of memory (W/page)

Table 2 . Parameters in experiments.

 2

	symbol value symbol value
	β	0.1s	p m	5 × 10 -5 W/page
	T	60s	e d	0.42J/page
	t be	7.3s	p d	3.99W

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

* This project is supported in part by Purdue Research Foundation and National Science Foundation Career CNS 0347466.


Elena Moscu Panainte
email: e.panainte@et.tudelft.nl

Koen Bertels
email: k.bertels@et.tudelft.nl

Stamatis Vassiliadis
email: s.vassiliadis@et.tudelft.nl

Instruction Scheduling for Dynamic Hardware Configurations

Although the huge reconfiguration latency of the available FPGA platforms is a well-known shortcoming of the current FCCMs, little research in instruction scheduling has been undertaken to eliminate or diminish its negative influence on performance. In this paper, we introduce an instruction scheduling algorithm that minimizes the number of executed hardware reconfiguration instructions taking into account the "FPGA area placement conflicts" between the available configurations. The algorithm is based on compiler analyses and feedback-directed techniques and it can switch from hardware execution to software execution for an operation, when the reconfiguration latency could not be reduced. The algorithm has been tested for the M-JPEG encoder application and the real hardware implementations for DCT, Quantization and VLC operations. Based on simulation results, we determine that, while a simple scheduling produces a significant performance decrease, our proposed scheduling contributes for up to 16x M-JPEG encoder speedup.

Introduction

The latest commercial FPGA platforms now offer support for partial and dynamic hardware configurations. Nevertheless, one of their main drawback remains the huge reconfiguration latency. In order to hide this latency, compiler support is fundamental to automatically schedule and optimize the compiled application code for efficient reconfigurable hardware usage.

When dealing with reconfigurable hardware, the compiler should be aware of the competition for the reconfigurable hardware resources (FPGA area) between multiple hardware operations during the application execution time. A new type of conflict -called in this paper "FPGA area placement conflict" -emerges between two hardware configurations that cannot coexist together on the target FPGA.

In this paper, we propose a general instruction scheduling algorithm that automatically minimizes the number of required hardware configurations taking into account both the "FPGA area placement conflicts" and the characteristics of the compiled software application. More specifically, the algorithm anticipates the hardware configurations in less frequently executed application points avoiding the "FPGA area placement conflicts".

The paper is organized as follows. In the following section, we present background information and related work. In section 3, we describe the goals and the contribution of this paper. A formal description of our scheduling problem is included in Section 4. Section 5 introduces the instruction scheduling algorithm. The M-JPEG case study is discussed in Section 6 and finally, we present conclusions and future work.

Background and Related Work

In this paper, we assume the Molen programming paradigm [START_REF] Vassiliadis | The molen programming paradigm[END_REF] [START_REF] Vassiliadis | The molen polymorphic processor[END_REF] for FCCMs (Field-programmable Custom Computing Machines) where the reconfigurable hardware is controlled by two instructions: i) SET for hardware configuration and ii) EXECUTE for hardware execution. The code generated for a hardware operation (an operation performed on the reconfigurable hardware) includes i) parameter passing, ii) the SET instruction, iii) the EXECUTE instruction and iv) returning the computed results. This sequence of instructions where the SET instruction is immediately followed by the associated EX-ECUTE instruction is referred to in the rest of this paper as the "simple scheduling".

In [START_REF] Moscu Panainte | Dynamic hardware reconfi gurations: Performance impact on mpeg2[END_REF], it has been reported that this simple scheduling produces significant performance decrease due to the huge reconfiguration latency of current FPGA. In order to deal with this drawback, a recent instruction scheduling algorithm has been proposed in [START_REF] Moscu Panainte | The Pow-erPC backend molen compiler[END_REF] for a particular case when there is only one hardware operation in the whole application. The main idea is to move the SET instructions outside loops in order to eliminate redundant hardware configurations.

However, in order to achieve significant performance improvement for real applications, more than one operation is usually implemented in hardware. As the available area of the reconfigurable platforms is limited, the coexistence of all hardware configurations on the FPGA for all application execution time may be restricted. Moreover, hardware implementations of these operations can be developed by different IP providers that can impose a predefined FPGA area allocated for each operation, resulting "FPGA-area placement conflicts". Two hardware operations have an "FPGAarea placement conflicts" (or just conflict in the rest of the paper) if i) their combined reconfigurable hardware area is larger than the total FPGA area or ii) the intersection of their hardware areas is not empty. In Figure 1(a) we sketch a possible FPGA area allocation for three operations performed on the FPGA. We observe that op1 and op2 cannot fit together on the FPGA (thus op1 conflicts with op2) while op2 and op3 have a common overlapping area (thus op2 conflicts op3).

A compiler approach that considers the restricted case of two consecutive and non-conflicting hardware operations is presented in [START_REF] Tang | A Compiler Directed Approach to Hiding Confguration Latency in Chameleon Processors[END_REF]. In this approach, the hardware execution of the first operation is scheduled in parallel with the hardware configuration of the second operation. Our approach is more general as it performs scheduling for any number of hardware operations at procedural level and not only for two consecutive hardware operations. The performance gain produced by our scheduling algorithm results from reducing the number of performed hardware configurations.

Motivation and Contribution

Figure 1(b) shows the control-flow graph of a procedure, when op1, op2 and op3 operations are performed on the reconfigurable hardware and they are placed on the FPGA as presented in Figure 1(a). The numbers associated with each edge of the graph represent the execution frequency of the edge. One first observation is the redundant repetitive execution of SET op1 instruction from B5 in the loop B4-B5-B6. Additionally, it should be noticed that moving this SET op1 instruction on (B1, B2) edge will also make redundant the SET op1 instruction from B13. In the initial simple scheduling, the FPGA is configured for op1 100 times in B5 and 10 times in B13. As a result of our scheduling algorithm, the hardware configuration for op1 will be executed only 20 times. The hardware configuration for op2 from B10 cannot be moved further then B7, as it will change the hardware configuration for op3 that must be performed in B7. There are no redundant configurations for op3, thus the hardware execution of op3 has to be preceded each time by the hardware configuration. When the hardware configuration consumes all the performance gain produced by the hardware execution of op3, the scheduler can switch to its software execution on the GPP (General-Purpose Processor).

¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ OP1 OP3 OP2
In this paper, we propose a general approach for intraprocedural instruction scheduling of the hardware configuration instructions taking into account the "FPGA-area placement conflicts". It is based on the state-of-art compiler optimization for partial expression redundancy elimination presented in [START_REF] Cai | Optimal and effi cient speculation-based partial redundancy elimination[END_REF]. In order to incorporate the "FPGA-area placement conflicts" between the hardware operations, we introduce a new type of data-flow analysis as described in Section 5. Additionally, it can switch for one operation from hardware execution to its software execution when the hardware operation provides no performance improvement even after the scheduling phase.

Problem Statement

We represent the control flow graph (CFG) of a procedure as a directed graph G < N, E, w > where the nodes N represent the basic blocks, the edges E represent the control flow dependencies and the weight function w: E → R + represents the execution frequency of each edge. The operations implemented in hardware are included in HW set. We define DEF op the set of basic blocks n ∈ N that contain an instruction SET op immediately followed by EXEC op instruction. A node n ∈ DEF op is called a definition node for op. In our example from Figure 1, B5 and B13 are definition nodes for op1. An "FPGA-area placement conflict" between two operations op1 and op2 is represented as op1 op2. The information about these conflicts is provided by a symmetric function f : HW x HW → {0,1}, where f(op1, op2) = 1 if op1 op2, and 0 otherwise. We define Con f lict op = {n ∈ N|∃op i ∈ HW, n ∈ DEF op i ∧ op op i }. A node n ∈ Con f lict op is called a conflict node for op. In Figure 1, B10 and B14 are conflict nodes for both op1 and op3.

In order to simplify this discussion, we make the following assumptions. We assume that there is a single entry node with no predecessor (pred(entry) = / 0, where pred(n)={m ∈ N | (m,n) ∈ E}) and a single exit node with no successor (succ(n) = / 0, where succ(n)={m ∈ N | (n,m) ∈ E}). Also, we assume that a node cannot be simultaneous in DEF op and Con f lict op . In consequence, when more conflicting operations are included in the same basic node, this node must be split into a set of nodes, one for each operation. The final assumption is that only the SET/EXECUTE instructions included in the CFG affect the reconfigurable hardware.

For each operation op, we consider a set of insertion edges δ op ⊆ E. The merit of δ op is measured by the function W δ = ∑ e∈δ op w(e). Loosely stated, the objective of our algorithm is to move upwards the SET instructions from DEF op on less frequently executed edges, in order to reduce the total number of performed SET instructions. A formal description of this problem is as follows:

PROBLEM Given a directed, weighted graph G < N, E, w > and a set of hardware operations HW, each defined in DEF op ⊆ N and with conflicts in Con f lict op ⊆ N, find a set of insertion edges δ ⊆ E for each op ∈ HW which minimizes W δ under the following constraints:

• ∀ n ∈ DEF op , for all paths from entry to n, there is an insertion edge (u,v),

• k ∈ Con f lict op such that k is included in any subpath from v to n
The minimization of W δ assures that a smaller or equal number of SET instructions will be performed in the final CFG graph than in the input graph. The first constraint reflects the requirement that hardware must be first configured (using the SET instruction) on all paths before the operation can be performed (using EXECUTE instruction). The second constraint assures that no conflict operation will change the hardware configuration before the operation execution.

Instruction Scheduling Algorithm

The problem of removing redundant hardware configurations is similar to the well-known problem of removing redundant expressions. As hardware configurations do not cause any exception, we can use an aggressive speculative scheduling for the hardware configurations in order to anticipate them on less executed paths and thus, to make redundant the hardware configurations from frequently executed paths. We introduce the scheduling algorithm that solves the problem defined in the previous section in three steps. In the first step, the subgraphs where the hardware configurations can be anticipated are constructed. Next, a minimum s-t cut algorithm is applied to find the optimal insertion edges δ op for each hardware operation. Finally, a switch from hardware to software execution is introduced for the cases when the expense of hardware configurations in the newly inserted nodes still outperforms the performance gain of hardware execution.

Step 1: The Anticipation Subgraph

Constructing the anticipation graph is a key step in our algorithm. The main goal is to eliminate from the initial graph the edges that cannot propagate upwards the hardware configurations due to hardware conflicts. This step contains two uni-directional data-flow analyses and one pass for constructing the anticipation subgraph by removal of nonessential edges.

Partial Anticipability A hardware configuration for operation op is partially anticipated in a point m if there is at least one path from m to the exit node that contains a definition node for op and none of the paths from m to the first such definition node contains a conflict node for op.

A confluence conflict node n is a node with two successors s1 and s2 such that op1 is partially anticipated at the entry point of s1, op2 is partially anticipated at the entry point of s2 and op1 op2. Due to hardware conflicts, op1 and op2 cannot be both anticipated in the confluence conflict node n. We consider a restricted partial anticipability analysis where the confluence conflict nodes limit the partial anticipability for both op1 and op2. This is a backward data-flow problem, where the data-flow equations for a basic block i are defined as follows:

PANTin(i) = Gen(i) ∪ (PANTout(i) -Kill(i)) PANTout(i) = U j∈Succ(i) PANTin( j)
PANTout(exit) = / 0 In the first equation, GEN(i) is the set of hardware operations generated in the basic block i. A hardware operation op1 is generated in a basic block i if i ∈ DEF op . The set Kill(i) includes all hardware operations that are in conflict with the operations generated in the basic block i. A hard- 1 ware operation op ∈ PANTin(i) is partially anticipated at the entry of a basic block i if it is generated in i or if it is partially anticipated at the exit of i and it is not killed in i.

The second equation differs from standard data-flow equations involved in iterative data-flow analysis where the join operator is S or T . The operator U is a conditional reunion that excludes the conflicting hardware operations and defined as follows:

A U B = {x ∈ A S B| ∃y ∈ A S B,
x y} This operator is used to stop the partial anticipability of the operations with hardware conflicts at confluence points. A hardware operation op ∈ PANTout(i) is partially anticipated at the exit of a basic block i if it is partially anticipated at the entry of any successor of i and i is not a conflict confluence node for op. In Figure 2, we present the values for PANT for the input graph presented in Figure 1. For the basic blocks where these values are missing, there are implicitly assumed as / 0. Availability We use the standard forward data-flow analysis for availability described by the set of data-flow equations: This analysis is used to eliminate the hardware configurations when they are already available. The values for AVAL for our example graph are presented in Figure 2.

AVALout(i) = Gen(i) ∪ (AVALin(i) -Kill(i)) AVALin(i) = T j∈Pred(i)
Constructing the Anticipation Graph Based on the previously presented data-flow analysis results, for each operation op ∈ HW we eliminate from the initial graph the nodes which are not essential as follows. We call an edge (u,v) an essential edge for op if

Ess(u, v) = (u, v) ∈ E ∧op / ∈ AVALout(u)∧op ∈ PANTin(v). The reduced graph G rd contains the nodes N rd = {n ∈ N|∃m ∈ N, Ess(n, m) ∨ Ess(m, n)} and the edges E rd = {(u, v) ∈ E|Ess(u, v)}.
The reduced graph may contain a set of disconnected subgraphs. In order to connect them, we introduce a new pseudo entry node (called s) and a pseudo exit node (called t) and the edges E st = {(s, n)|n has no predecessor in N rd } S {(n,t)|n has no successor in N rd } with infinite execution frequency. For our example from Figure 1, the anticipation graphs are presented in Figure 3.

Step 2: Minimum s-t Cut

In this step, the set of insertion edges from our problem definition is determined by applying a minimum s-t cut algorithm. The purpose of the min cut algorithm is to select the less frequently executed edges from the anticipation graph on all paths to the definition nodes. In consequence, the min cut algorithms assures the minimization requirement and the first constraint from our problem definition, while the construction of the anticipation graph secures the second constraint.

One of the important advantages of using a min cut algorithm is to avoid moving upwards SET instructions on edges inside loops. In our implementation, we used Edmonds-Karp minimum s-t cut algorithm. For the three hardware op- 1, their minimum cuts are presented in Figure 3. We notice that for op3 (depicted in Figure 3 (c)), the SET instruction from B7 can propagate further then B2 (on edge (B1, B2)). The minimum cut algorithm chooses the edge (B2, B3) as its execution frequency is smaller (10 versus 20 for (B1,B2)).

Step 3: Selection of Software/Hardware Execution

In the cases when, even after our scheduling, the hardware configuration and execution is more expensive than the pure software execution, the scheduling algorithm can switch for this operation from hardware execution to software execution. In this case, all the SET instructions for this operation are eliminated and its EXECUTE instructions are replaced by standard calls to the associated software function. In our example from Figure 1, op3 may be in this case if one hardware configuration and one hardware execution is more expensive than one software execution.

M-JPEG Case Study

The presented instruction scheduling algorithm has been implemented as a MachSUIF pass [3] within the Molen compiler [START_REF] Moscu Panainte | The Pow-erPC backend molen compiler[END_REF] which generates code for the Molen prototype on the Virtex II Pro FPGA platform. The target C application of this case study is the multimedia benchmark Motion JPEG (M-JPEG) encoder and the input sequence contains 30 color frames from "tennis" in YUV format with a resolution of 256x256 pixels. The operations performed on the FPGA are DCT (2-D Discrete Cosine Transform), Quantization and VLC (Variable Length Coding). The Xilinx IP cores for DCT [START_REF] Pillai | Video compression using dct[END_REF], Quantization [START_REF] Pillai | Quantization. In Application Note: Virtex and Virtex-II Series[END_REF] and VLC [START_REF] Pillai | Variable length coding[END_REF] are used for hardware implementations. The GPP included in the Molen prototype is the IBM PowerPC 405 processor at 250 MHz.

We present in Table 1 the characteristics of DCT, Quantization and VLC hardware and software executions. Based on the characteristics of the XC2VP20 chip, for which a complete configuration of 9280 slices takes about 20 ms, The profiling results for the software execution from Table 1 are based on simulations using the PowerPC simulator from Simics [START_REF] Magnusson | Simics: A full system simulation platform[END_REF]. Comparing the values from Table 1 (column 4 and 5), we notice that the hardware configuration alone is about 10 times more expensive than the complete software execution. Using Amdhal's law, we determine that the simple scheduling for DCT will slowdown the M-JPEG benchmark up to 10x. For this reason, we compare the performance of our scheduling algorithm to the pure software approach rather than the inefficient simple scheduling. The estimated performance for the M-JPEG application for different possible conflicts between the three hardware operations are presented in Figure 4. The standard unit of this comparison is the pure software execution (SW) when the M-JPEG benchmark is completely performed on the GPP alone. The performance of our instruction scheduling algorithm for the real Xilinx hardware implementations is denoted as REAL. As recently some hardware approaches [START_REF] Blodget | Partial and dynamic reconfi guration of xilinx virtex-ii fpgas[END_REF] have been proposed for reducing the hardware configuration time, we also analyze the impact of our scheduling algorithm when the hardware configuration is accelerated by a factor of 20x 1 compared to the current values from Table 1, column 4. The performance of our instruction scheduling algorithm combined with this faster hardware configuration is presented in Figure 4 as FAST. For completeness, we also present the IDEAL case when the hardware config- The factor has been chosen arbitrarily. Mutatis mutandis, similar observations will then hold.

uration is performed in zero cycles. We notice that for the "no conflict" case, the performance improvement is about 94 % (equivalent to a 16x speedup) for both REAL and FAST scheduling and very close to the IDEAL performance. In this case, the instruction scheduling algorithm moves the hardware configurations for all three operations at the procedure entry point. In consequence, there is only one hardware configuration for each hardware operation, thus the difference between REAL and FAST is negligible.

For the rest of the "conflict" cases, the scheduler for REAL will switch from hardware execution to software execution for the conflicting operations. For example, when there is a DCT -Quantization conflict, the scheduler will move both DCT and Quantization operation in software, while the third non conflicting operation VLC remains in hardware; its hardware configuration needs to be performed only once, at the procedure entry point.

For the FAST scheduling, even when one operation has a conflict, it may remain in hardware, thanks to the 20x faster hardware configuration. For the case with DCT -Quantization -VLC conflicts, both DCT and VLC are performed in hardware and produce a performance improvement of 43 % as the fast hardware configuration does not consume all performance gain of the hardware execution. The scheduler selects the software execution for Quantization, in order to prevent a performance decrease produced by its hardware configuration and execution (16 % for Quantization) . Therefore, the performance improvement for simple scheduling (all operations executed on the reconfigurable hardware) and 20x faster reconfigurations is 27 % while our scheduling algorithm contributes to a performance improvement between 43 % and 94 % compared to SW.

In consequence, we notice that for the non-conflict case, our algorithm capitalizes the maximum performance gain that can be obtained by hardware execution of the considered operations. Finally, the results presented in Figure 4 emphasize the important performance impact of our scheduling algorithm even for the future faster FPGAs.

Conclusions

In this paper, we have introduced a general scheduling algorithm for hardware configuration instructions. This algorithm takes into account specific features of the reconfigurable hardware such as the "FPGA area placement conflicts" and the reconfiguration latencies of each hardware operations. Based on the characteristics of the compiled application, the scheduling reduces the number of performed hardware configurations preserving the application semantics. It combines advanced compiler techniques with powerful graph theory algorithms. The results of our case study show that the performance is dramatically improved by us-ing our scheduling algorithm, and this improvement will hold for future faster FPGA platforms.

When confronted with the choice between the software or hardware execution, our future work will focus on defining the heuristics to guide this selection. Another issue is to allow the data-flow analysis to propagate a conflicting operation beyond the confluence conflict points. We are also looking at incorporating dynamic placement on the reconfigurable hardware in our scheduling.

Figure 1 .

 1 Figure 1. Motivational example for instruction scheduling of hardware configurations (b) with FPGA-area placement constraints (a)

Figure 2 .

 2 Figure 2. Set of PANT and AVAL values for the input graph from Figure 1

AVALoutFigure 3 .

 3 Figure 3. The anticipation graph for op1 (a), op2 (b) and op3 (c) from Figure 1

Figure 4 .

 4 Figure 4. Comparison of estimated performance for our scheduling algorithm for M-JPEG benchmark

1

 1

Table 1 . HW/SW features for the operations that candidate for hardware implementation

 1

		HW Execution	SW Execution
	Op	EXEC	Area	SET	One call	%Total
	Name	[cycle]	[slice]	[cycle]	[cycle] M-JPEG
	DCT	416	848 431771	44396	80 %
	Quant	73	397 202073	1494	3 %
	VLC	272	193	98237	6921	12.5 %

erations from Figure

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)