S Tosun

N Mansouri

E Arvas
email: earvas@ecs.syr.edu

M Kandemir
email: ‡kandemir@cse.psu.edu

Yuan Xie
email: yuanxie@cse.psu.edu

Reliability-Centric High-Level Synthesis

Importance of addressing soft errors in both safety critical applications and commercial consumer products is increasing, mainly due to ever shrinking geometries, higher-density circuits, and employment of power-saving techniques such as voltage scaling and component shut-down. As a result, it is becoming necessary to treat reliability as a first-class citizen in system design. In particular, reliability decisions taken early in system design can have significant benefits in terms of design quality. Motivated by this observation, this paper presents a reliabilitycentric high-level synthesis approach that addresses the soft error problem. The proposed approach tries to maximize reliability of the design while observing the bounds on area and performance, and makes use of our reliability characterization of hardware components such as adders and multipliers. We implemented the proposed approach, performed experiments with several designs, and compared the results with those obtained by a prior proposal.

Introduction

With ever shrinking geometries and higher-density circuits, the issue of soft errors and reliability in system design is set to become an increasingly challenging issue for the industry as a whole. This is true for both commercial consumer applications and safety critical applications. Specifically, for high-volume low-margin consumer products, frequent soft errors can lead to expensive field maintenance. For safety critical applications, poor reliability can be catastrophic in terms of both human and equipment cost. Therefore, reliability-aware design that targets at mitigating the potential consequences of soft errors is highly desirable.

While substantial progress has been made over the years in formulating and understanding the basic concepts in high-level synthesis (HLS), most of the prior studies focused on performancearea or performance-power-area tradeoffs. In comparison, relatively fewer papers considered reliable/fault-tolerant HLS. However, considering the emerging soft error problem, it is becoming increasingly important to incorporate reliability concerns into the HLS process.

Prior work investigated soft error susceptibility of memory elements and combinational circuits [START_REF] Johansson | In-flight and ground testing of single event upset sensitivity in static RAM's[END_REF]. It showed that combinational circuits are less susceptible to soft errors than memory elements. This is because of three major error masking effects on combinational circuits; namely logical, electrical, and latching-window masking. On the other hand, Sivakumar et al [START_REF] Sivakumar | Modeling the Effect of Technology Trends on the Soft Error Rate of Combinational Logic[END_REF] demonstrate that the soft error susceptibility of combinational circuits will be comparable to that of memory circuits by the year of 2011 with the current technology trends. This significant prediction urges the computer designers for further research to reduce the soft error effects on the data-path part of their designs since the current protection techniques for combinational circuits introduce more area, power consumption, and/or performance penalty than those designed for memory elements. These observations motivate us to consider the effects of soft errors on the problem of high-level data-path synthesis and the overall reliability for the combinational part of the resulting designs. Therefore, the work proposed in this paper is orthogonal and complementary to techniques proposed for improving reliability of memory components.

In this paper, we propose and evaluate a reliability-centric HLS approach that addresses soft errors. We call our approach "reliability-centric" since it tries to maximize reliability of the resulting design while observing the bounds on area and performance. Note that this is very different from a conventional HLS framework that incorporates reliability concerns into the design in an ad-hoc fashion after the major design decisions (based on performance, area, and/or power) have already been made. This paper makes the following contributions: ◊ It describes our reliability characterization of library components such as adders and multipliers. Our library accommodates several versions of each type of resource, where each version can have different area, performance and reliability characteristics as compared to the others. In the context of this characterization, we also discuss the relationship between reliability and soft errors.

◊

It presents a reliability-centric HLS framework that operates under performance and area bounds. The framework makes use of our reliability characterization, and selects the most reliable version (implementation) for each operation (in the data-flow graph representation of the design) as long as we do not exceed the area or performance bounds.

◊

It presents an experimental evaluation of the proposed framework, and compares it to a prior study that improves reliability through redundancy. Our experimental evaluation identifies the cases where one of the techniques performs better than the other, and points out a unified approach that could merge the two techniques for increasing reliability further. The rest of this paper is organized as follows. The next section presents a discussion of the prior work. Section 3 gives a background on soft errors. Section 4 presents the results obtained from our reliability characterization of hardware components. Section 5 explains the method used in this paper to evaluate the reliability of the overall design. Section 6 presents our approach to scheduling, resource binding, and resource allocation. Section 7 presents experimental data, showing the impact of the proposed reliability-centric approach. Section 8 concludes the paper with a summary of our contributions and summarizes our future efforts.

Related Work

Most of the prior studies on reliable design make use of component redundancy. They typically use one resource (version) for each type of operation with a fixed reliability, and the reliability is increased by adopting N Modular Redundancy (NMR). Orailoglu and Karri [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF] introduced an elegant design methodology for faulttolerant ASICs to explore the three-dimensional space of reliability, area, and performance. They presented two strategies that are based on NMR. The first strategy targets at minimizing the overall cost of the design under performance and reliability constraints, while the second one tries to maximize the reliability given the cost and performance constraints. Their technique adds an extra cost to the design that is proportional to N (in NMR) for specific resource. For example, if the design area is S without any redundancy and the resource with the area of A is duplicated (i.e., N=2), then the area of resulting design is S+A, excluding the area required by the result-checking circuitry and interconnects. This technique gives very good results if the cost bound permits the designer to add redundancy to the design. A similar approach is used in related studies such as [START_REF] Guerra | High level synthesis for reconfigurable data path structures[END_REF]. In addition, these studies make use of transformations that alter the computational structure such that the original behavior is maintained. The transformation based synthesis is used to reduce the overhead introduced by redundant components.

Another method used to improve the reliability of the high-level system is to duplicate the entire structure for the self-recovering circuits. This technique is used in various studies such as [START_REF] Antola | High-level synthesis of data paths with concurrent error detection[END_REF]. After copying the entire flow graph, they used various strategies to minimize the overall area of the final design. For example, [START_REF] Antola | High-level synthesis of data paths with concurrent error detection[END_REF] exploits the freedom of operations, and schedules both the copies to reduce the area overhead. Our approach differs from these previous studies since it makes use of a reliability-characterized library that has different versions of resources with different area, performance, and reliability metrics. The library we use permits us choose the most reliable resources for a specific task. In other words, instead of increasing reliability through redundancy, we achieve reliable design by using different versions of the components (as allowed by area and performance bounds).

Background on Soft Errors

A soft error, also called single event upset (SEU), is a "glitch" in a semiconductor device [START_REF] Ziegler | IBM experiments in soft fails in computer electronics[END_REF]. These glitches are random, usually not catastrophic, and they do not normally destroy the device. Soft errors could be induced through three different radiation sources, alpha particles from the naturally occurring radioactive impurities in device materials, high-energy cosmic ray induced neutrons, and neutron induced 10B fission. Soft errors occur when the collected energy Q at a particular node is greater than a critical charge Q critical , which results in a bit flip at that node. This concept of critical charge can be used to estimate the soft error rate (SER), as will be detailed in the next section. Figure 1 illustrates the device view and the circuit view of the bit flipping caused by a particle strike. Soft errors are the most benign form of radiation effects on the circuitry, where radiation directly or indirectly induces a localized ionization capable of upsetting internal data states. The causes for soft errors are usually outside of the designer's control. While these errors result in an upset event, the circuit itself is not damaged. Many systems can tolerate a certain degree of soft errors. For example, in a video application, soft errors can manifest themselves as missing or wrong colored bits on a display screen. These errors may or may not be noticeable or important to the user. However, when memory elements are used to control the functionality of the device, such as in an SRAM FPGA, soft errors can have a much more serious impact and lead not only to corrupt data, but also to a loss of functionality and critical failures. Soft error phenomenon in memory was known to exist as early as 1970s, and studies have been conducted to tackle this problem at the circuit level. For example, in 1996, IBM disclosed its experiments on computer electronics failure due to soft error from 1978 to 1994 [START_REF] Ziegler | IBM experiments in soft fails in computer electronics[END_REF]. Because of technology scaling, drastic shrinking in device sizes, associated with reduction in operating voltages and increase in clock frequencies, digital logic is becoming increasingly susceptible to soft errors from natural ground level radiation. Consequently, providing reliable functioning in the existence of soft errors is becoming increasingly critical.

Current n+ n+

+ - + - + - + - + -+ - + - + - + - A particle strike V out CL V in A particle strike Bit Flip ! 1->0!
It should be emphasized that the reliability problem is more critical for embedded systems than their general-purpose counterparts due to following reasons. First, as compared to general-purpose systems, embedded systems are generally employed in harsher environments. Second, to reduce power demands, many battery-operated embedded systems accommodate circuit/architectural-level techniques such as voltage scaling and cache shutdown, which increase the vulnerability of the entire system to soft errors. Third, the need for developing safety or mission critical embedded applications with high demands in terms of computational power under low-cost real time constraints pushed designers to explore the possibilities offered by incorporating the reliability concerns in hardware and software design of an embedded system. Therefore, reliability concern must be taken as the first-class parameter in embedded system design.

Reliability Characterization Based on Soft Errors

A key component of the proposed reliability-centric high-level synthesis effort is the library characterization for soft errors. Current state-of-the-art in library characterization [START_REF] Ackalloor | An overview of library characterization in semi-custom design[END_REF] focuses mainly on latency, area, and power. However, it is equally important to study the soft error susceptibility of the library components so that one can conduct a tradeoff analysis between reliability and other metrics, which is critical for our purposes.

Efficient soft error fault injection and simulation techniques [START_REF] Alexandrescu | New Methods for Evaluating the Impact of Single Event Transients in VDSM ICs[END_REF] can be used to evaluate the soft error susceptibility of a library component. For each component (such as carry-lookahead adder or carry-skip adder), each of the nodes (gates) in the netlist can be characterized individually to determine their soft error susceptibility by fault injection and simulation. After this step, by analyzing the interconnection of gates in the netlist, the overall soft error susceptibility of the design can be determined.

Our resource library has components with different area, performance, and reliability properties. The basic resources we implemented are adders and multipliers. For example, for adder implementations, we used ripple-carry adder, Brent-Kung adder, and Kogge-Stone adder, and for multiplier implementations, we used carry-save multiplier and Leap frog multiplier. In order to estimate the reliabilities of these different versions of adders and multipliers, we use a three-step approach illustrated in Figure 2.

For the first step, we derive the Q critical values from circuit simulation. For example, we determine the Q critical values for

          - × × ∝ Qs Qcritical CS Nflux SER exp SER = λ } exp{ ) ( t t R λ - = Qcritical SER
Failure rate Reliability ripple-carry, Brent-Kung, and Kogge-Stone adders as 59.460e-21 C, 29.701e-21 C, and 37.291e-21 C, respectively. After finding the Q critical for each implementation, the soft error rate (SER) is estimated by using the expression,

     - × × ∝ s Q critical Q CS flux N SER exp ,
proposed by Hazucha et al [START_REF] Hazucha | Optimized test circuits for SER characterization of a manufacturing process[END_REF]. In this expression, N flux is the intensity of the neutron flux, CS is the area of cross section of the node, and Q s is the charge collection efficiency that strongly depends on doping. The other parameters, neutron flux (N flux ) and the area of cross section of the node (CS), can be chosen to be the same for different circuit implementations with the same process technology. With the assumption of uniform neutron flux and the same technology generation being used for circuit implementation, the total charge efficiency (Q s ) can be assumed to be the same for two circuits. Thus, the SERs for two circuits with the same technology generation can be related to each other as

} 2 1 exp{ * 2 1 s Q critical Q critical Q SER SER - = .
We now need to relate the SER of each component to its reliability metric. Reliability is defined as the probability with which a component will perform its intended function satisfactorily for a period of time [t 0 ,t], given that the component was working properly at time t 0 [START_REF] Neubeck | Practical Reliability Analysis[END_REF]. To calculate the reliability of a design, one needs to determine its failure rate , which is the probability with which the design will fail in the next time unit, given that it has been working properly in the current one. The reliability of a component can be related to its failure rate by the distribution function

} exp{ ) ( t t R λ - =
. If we assume that every soft error will result in a failure, we can use the SER of a component as its failure rate, shown as the second step in Figure 2. We can then use the reliability function to determine the reliability of a component, which is the third step in the same figure. Note that in our library characterization, the reliability of the ripple-carry adder is set to 0.999; and the reliabilities of other components are determined based on this value, using three steps depicted in Figure 2.

We laid out the circuits using the MAX layout editor tool, and used the HSPICE simulator to simulate the layouts. The normalized area and delay values for each implementation are shown in Table 1 under columns two and three, respectively. Using the steps explained above, the reliability values for these resources are estimated as shown in the fourth column of Table 1. In our experiments, we use the values given in Table 1.

Resource type Area (Unit) Delay (cc) Reliability

Adder

Design Reliability

While the results obtained from the reliability characterization of components presented in Section 4 are important, we also need a mechanism to evaluate the reliability of an entire design built from such components. Our goal in this section is to present the model adopted in calculating the reliability of an entire design, given the reliability characterizations of individual components. Note that this is critical as it allows us to compare the two alternate designs (that implement the same functionality with different versions of resources) from a reliability perspective.

A design is typically composed of multiple components that interact with each other. The overall reliability of a design is calculated based on how these components are related to each other. Two basic reliability models are serial and parallel reliability models [START_REF] Neubeck | Practical Reliability Analysis[END_REF], illustrated in Figures 3(a In the serial model, all the components involved should succeed in order to have a system-wide (design-wide) success. As a result, the overall reliability of the system from point A to B in Figure 3(a) can be expressed as

∏ = = n i i R s R 1 .
In reliability engineering, the overall reliability of the parallel model between points A and B in Figure 3(b) can be found as

∏ = - - = n i i R s R 1 ) 1 ( 1 ,
since it is assumed that only one component's success results in system-wide success. However, in the context of high-level synthesis, in order to have a successful execution of entire design, all hardware components must succeed. Consequently, to express the reliability of the design, we adopt the formula

∏ = = n i i R s R
1 for parallel models as well. As an example, the reliability of the data-flow graph shown in Figure 4(a) can be expressed as

F R E R D R C R B R A R s R * * * * * = .
(a) (b) Since we want to compare our approach to a redundancy-based solution as well, let us now discuss the concept of redundancy in mathematical terms. N Modular Redundancy (NMR) [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF] is a simple majority voting system that has N modules connected in parallel. TMR (Triple Modular Redundancy) is a special case of NMR illustrated in Figure 4(b). The reliability of the NMR can be expressed as

∑ = - - =         N k i i N R i R i N NMR R ) 1 ( * ,
where N is the number of components in the system and k is the number of components that must succeed in order to have a successful execution. The relationship between N and k is given by 1

2 - = k N . If 3 ≥ N
, the structure can have the ability of fault tolerance, which is the capability of the system to continue to perform successfully after a fault occurrence [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF]. If a simple duplication is used, the system can detect the fault when a fault is introduced and some recovery mechanisms such as rollback can be used to recapture the successful state of the system. In our experiments, we also used NMR structure to demonstrate the efficiency of using multiple implementations of a node (in the data-flow graph) to increase the reliability of the overall design.

Reliability-Centric Resource Allocation, Binding and Scheduling

In this section, we present resource allocation, binding and scheduling for our reliability-centric high-level synthesis approach. The problem of finding the most reliable design based on our library can be stated as follows: Given a data-flow graph G s (V,E), a resource set R, desired latency L d , and desired area A d , determine the design with the highest reliability. Note that both bounds L d and A d can prevent us from selecting the most reliable component for every operation in the data-flow graph. Each resource (version) r with type t in R has typically a different area, performance, and reliability characteristic from the other resources (versions) of type t. In this section, we present our approach to determining the most reliable system by using these resources.

To illustrate the impact of using more reliable resources (instead of less reliable ones), we consider Figure 5(a) and Figure 5(b), which are two possible schedules for the data-flow graph given in Figure 4(a). For this example, we bound the latency to 5 clock cycles and the area to 4 units. For the first schedule, shown in Figure 5(a), we use only adders of type 2 (see Table 1). In contrast, for the second schedule we consider using all the adder types in Table 1. As a result, the first schedule has 4 units of total area (two adders of type 2) and a reliability of 0.82783. On the other hand, the second one has 3 units of total area (one adder of type 1 and one adder of type 2) and its reliability is 0.90713. This small example illustrates that we can have a more reliable design by using different resources with different reliability/area/performance characteristic. The overall algorithm is given in Figure 6. In this algorithm, we first find an initial solution (between lines 3 through 5), which is the most reliable one among all possible solutions. This is because this initial solution employs the most reliable version for each node in the data-flow graph. The algorithm performs resource allocation, binding, and scheduling [START_REF] Hwang | Scheduling and hardware sharing in pipelined data paths[END_REF] in lines 3, 4 and 5. Note that, while this algorithm can be used for both pipelined and non-pipelined * In a scheduled data-flow graph, a step is a clock cycle that an operation (node) starts its execution. The type of an operation is given inside of the node with symbols such as + and * for addition and multiplication, respectively. The name (id) of the node is also given along with its type with a letter or a number.

data-paths, we use it here only in the context of non-pipelined circuits. The scheduling algorithm partitions the data-flow graph into the number of cycles determined by As Soon As Possible (ASAP) scheduling, and calculates the density of each partition for a specific type of operation. The total partition density is found by adding the probabilities with which a node can be scheduled within a partition. Then, it schedules an operation in the least dense partition in which the operation can be scheduled. The algorithm tries to distribute the operations evenly among the partitions so that the number of resources used in the final design is minimized. After scheduling the graph and binding the resources to each node, the algorithm returns the latency and the total area of this initial solution. As indicated earlier, this initial solution is the most reliable one since the most reliable versions are allocated for each node. However, it may not necessarily meet the latency or/and area constraints. Consequently, we may need to select a victim node and sacrifice its reliability by using a less reliable version for it. This is achieved in two steps. In the first step, given between lines 7 through 12 in Figure 6, we check if the performance constraint (bound) is met. If the latency L of the initial schedule is greater than the desired latency (bound) L d , then we iteratively reduce L by allocating a new resource (typically a less reliable one) to a node until we reach to L d . Specifically, we pick the slowest node on the critical path (Note that selecting a node which is not on the critical path will not help us reduce the initial latency value), and use a faster but potentially less reliable version for it. After this, the critical path of the current design may change. Thus, we may have to select a node from another path, which is the current critical path, in the next iteration if the current latency value is still higher than the bound (L d ). This process is repeated until we meet the latency bound. If all the available versions have been tried and we still could not meet the performance bound, we can conclude that it is not possible to find a solution for the graph with given latency constraint and available resources. After allocating new resources to some of the nodes, we may need to update the resource sharing if necessary (i.e., if A>A d ) to minimize the total area since we introduce new resources to the design that can increase the overall

+F

Step 1

Step 2

Step 3

Step 4

Step 5

(a) (b)

1. Find_Design (Gs(V,E),R,Ld,Ad) 2. { 3.
Allocate the most reliable resource to each node (G,R); 4.

L=ASAP(G,R); ALAP(G,R,L);

5.

Schedule(G,R,L); Bind_Resources(G,R); 6.

A=Find_Total_Area(G,R); 7.

while(L>Ld & ∃ r' ∈ R. tr>tr') do 8. { 9.
Select the node nl on the critical path with highest delay; 10.

Allocate a resource r' to nl such that tr>tr'; area of the design. This may result in sacrificing more nodes that share the same resource with the ones that we updated. After having met the latency constraint, we next calculate the total area of the design, and check whether the area bound is met. If the area A of the scheduled graph is greater than the desired area A d , then we make two attempts to reduce the area. We first check if there is a latency slack that could be exploited (i.e., L<L d ) to reduce the number of resources in the schedule. This attempt is implemented between lines 15 through 21 in Figure 6. If this is not possible, then we make our second attempt (lines 23 through 28), which is based on an idea similar to the one we employed for reducing the latency. Specifically, we select a victim node to be sacrificed based on node areas, and allocate a smaller version to it. However, when we choose a new version, we also need to check if this version increases the latency. If it does, we select an alternate node, and repeat the process until the area bound is met. If all the versions have been tried and we still could not meet the area bound, then we can conclude that it is not possible to find a solution to the given graph with given area constraint and available resources. Finally, if our algorithm returns a design that meets the area and performance bounds, we calculate the total reliability of the design using approach described in Section 5.

Experimental Evaluation

In this section, we present experimental data showing the impact of the proposed approach, and compare our results with those obtained by a prior work. In our experiments, we used several high-level synthesis benchmarks. Due to space concerns, we only give the results for three benchmark examples; namely, a 16-point symmetric FIR filter [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF], a 16 point elliptic wave filter (EW) [START_REF] Hwang | Scheduling and hardware sharing in pipelined data paths[END_REF], and a differential equation solver (DiffEq) [12]. For the resource library, we use the values in Table 1. We first illustrate the impact of our approach on the FIR filter design. Then, we show how reliability of a design changes with respect to performance and area. Finally, we present a comparison of our approach with the solution presented in [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF] on different benchmarks. We also show the results when our approach is combined with the method in [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF]. Note that, except for the last experiment, our approach does not employ any redundancy.

In the first experiment, we schedule the FIR filter with two different approaches. Figure 7(a) shows the first approach that uses only one implementation for each type of operator (node). Specifically, we restrict ourselves to type 2 adders and type 2 multipliers. In comparison, the scheduling resulted from our reliability-centric approach is shown in Figure 7(b). The latency and area bounds for both the designs are 11 clock cycles and 8 units, respectively. The resulting area and reliability for the first design are 8 units (two adders of type 2 and two multipliers of type 2) and 0.48467, respectively. On the other hand, our design has a reliability of 0.78943 while the total area is the same as the first one. To reach this reliability value, our solution employs two adders of type 1, two multipliers of type 1, and one adder of type 2, resulting 8 units of total area. It must be emphasized that if we use other combinations of resources from Table 1 for the first approach, we may not be able to meet the area and/or latency bounds. For example, suppose that we used an adder of type 1 and a multiplier of type 1 to schedule the FIR filter. In this case, the minimum latency that could be achieved would be 18 clock cycles (which is larger than the 11 cycles bound). This experiment shows that having multiple versions of components with different reliability, performance, and area values can help us reach a more reliable design than an alternate scheme, which restricts itself to one type of resource only. In the second experiment, we demonstrate, using our approach, the tradeoff between performance and reliability and between area and reliability. We use the FIR filter in this experiment. Figures 8(a) and 8(b) plot the reliability when the latency and area values, respectively, are varied. The reliability values in Figure 8(a) are found by setting the area constraint to 8 units. As can be observed from the figure, the performance changes inversely with reliability, i.e., when we have a larger latency bound, we achieve better reliability. We study the impact of area bound on design reliability by setting a constant latency bound (10 clock cycles in this case) and varying the area bound. In the final set of experiments, we compare our approach to the approach presented in [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF]. We also illustrate the results obtained when these two techniques are combined. To do this, we scheduled the FIR, EW, and DiffEq benchmarks with different area and latency bounds. We started with the minimum allowable latency and area values, and then increased the area and latency bounds. For each schedule, we calculated the overall design reliability. The results are provided in Table 2(a), Table 2(b), and Table 2(c), respectively. We show the area and latency bounds used in the first two columns of these tables. In column three, we give the reliability values obtained using the technique presented in [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF], and column four shows the reliability values obtained by our approach explained in this paper. Column five gives the percentage (reliability) improvements brought by our approach over the technique in [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF]. Note that a negative value means that our approach generates worse result than [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF] under those particular parameters. As can be seen from this column, our approach generates more reliable designs when the latency/area bounds are tighter. However, when we start to increase the area bound while keeping the latency bound constant, [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF] improves the overall design reliability. With larger area bounds, it finds better results. For example, in Table 2(a), when the latency bound is 10 clock cycles, and the area bound is 9 units, [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF] finds a design with the reliability of 0.48467. In comparison, with the same bounds, our Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Step 7

Step 8

Step 9

Step 10

Step approach obtains a reliability value of 0.59998, a 23.79% improvement over [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF]. However, when the area bound is loosened to 13 under the same latency bound, [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF] increases the reliability of the design to 0.76572, which means a 9.22% improvement over our approach. When we combine these two methods (i.e., when we also employ redundancy following our approach), we can have even more reliable designs under very tight bounds as shown in column six of Table 2. For the combined approach, we introduce redundancy as suggested in [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF]. Note that, when we add redundancy for an operator, we use the same version selected by our reliability-centric approach as duplicate(s). For example, if we use adder of type 2 in the schedule, we also use the same type of adder as the redundant copy. The improvements brought by this combined approach over [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF] are given in column seven of Table 2. This combined approach obtains a better reliability than [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF], as can be seen from these tables.

In Figure 9, we give the average reliability values (over all our experiments) obtained by [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF], our approach, and the combined approach for FIR, EW, and DiffEq benchmarks. Our approach brings 21.92%, 9.67%, and 9.21% overall design reliability improvements over [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF] for FIR, EW, and DiffEq designs, respectively. The combined approach obtains even more reliable designs with design reliability increase of 30.33%, 28.57%, and 10.26% over [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF] for FIR, EW, and DiffEq, respectively. Note that, the reliability values for these designs are found for tight area and latency values, which is desirable for system design.

Conclusions and Future Work

This paper focuses on high-level synthesis and presents a reliability-centric approach to address the growing soft error problem. The main idea behind this approach is to increase the reliability of the design as much as possible, bounded only by allowable area and latency. As opposed to the prior work on the topic, the proposed framework accommodates different versions of the same type of resource, each differing in performance, area, and/or reliability. Our experimental evaluation identifies the cases where one can expect the proposed approach to be better than the prior proposal. We also discuss how our approach can be combined with the prior work to achieve even further improvements on reliability of the design under consideration. As our future plan, we would like to compare this approach to other possible alternate schemes such as optimizing area under reliability and performance constraints, or optimizing performance under reliability and area constraints.

Figure 1 :

 1 Figure 1: Soft error phenomenon: a device view and a circuit view.

Figure 2 :

 2 Figure 2: Relationship between Qcritical, SER, failure rate, and reliability.

  ) and 3(b), respectively.

Figure 3 :

 3 Figure 3: Serial (a) and parallel (b) reliability models.

Figure 4 :

 4 Figure 4: (a) An example data-flow graph (b) TMR structure.

Figure 5 :

 5 Figure 5: Two possible schedules for the data-flow graph * shown in Figure 4(a).

Figure 6 :

 6 Figure 6: Algorithm for reliable design under performance and area constraints. Ad and Ld correspond to latency (performance) and area bounds, respectively.

Figure 7 :

 7 Figure 7: Two possible schedules for the FIR filter with Ld=11 and Ad=8.

Figure 8 (

 8 b) plots the results and shows that reliability increases proportionally with area.

Figure 8 :

 8 Figure 8: (a) Reliability vs performance (b) Reliability vs area.

2 :

 2 Reliability values and improvements under different latency and area bounds. (a) FIR filter, (b) EW filter, (c) DiffEq.

Figure 9 :

 9 Figure 9: Average reliability values for [3], our approach, and the combined approach for three different HLS benchmarks.

Table 1 : Area, delay, and reliability values for different adder and multiplier versions.

 1

	1	1	2	0.999
	Adder 2	2	1	0.969
	Adder 3	4	1	0.987
	Multiplier 1	2	2	0.999
	Multiplier 2	4	1	0.969

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

Average Reliability Values

Ref [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF] Our Approach Our Approach + Ref [START_REF] Orailoglu | A Design Methodology For The High-level Synthesis Of Fault-tolerant Asics[END_REF]


Aviral Shrivastava
email: aviral@ics.uci.edu

Nikil Dutt
email: dutt@ics.uci.edu

Alex Nicolau
email: nicolau@ics.uci.edu

Eugene Earlie
email: eugene.earlie@intel.com

PBExplore: A Framework for Compiler-in-the-Loop Exploration of Partial Bypassing in Embedded Processors

Varying partial bypassing in pipelined processors is an effective way to make performance, area and energy tradeoffs in embedded processors. However, performance evaluation of partial bypassing in processors has been inaccurate, largely due to the absence of bypass-sensitive retargetable compilation techniques. Furthermore no existing partial bypass exploration framework estimates the power and cost overhead of partial bypassing. In this paper we present PBExplore: A framework for Compiler-in-the-Loop exploration of partial bypassing in processors. PBExplore accurately evaluates the performance of a partially bypassed processor using a generic bypass-sensitive compilation technique. It synthesizes the bypass control logic and estimates the area and energy overhead of each bypass configuration. PBExplore is thus able to effectively perform multi-dimensional exploration of the partial bypass design space. We present experimental results on the Intel XScale architecture on MiBench benchmarks and demonstrate the need, utility and exploration capabilities of PBExplore.

Introduction

Register bypasses or forwarding paths improve the performance of a processor by eliminating certain data hazards in pipelined processors [START_REF] Hennessy | Computer Architecture: A Quantitative Approach[END_REF][START_REF] Muchnick | Advanced Compiler Design and Implementation[END_REF]. With bypasses, additional datapaths and control logic are added to the processor so that the result of an operation is available for subsequent dependent operations even before it is written to the register file. However, extensive bypassing implies that very wide multiplexors or buses with several drivers may be needed. Paths including the bypasses often are timing critical and cause pressure on cycle time (especially the single cycle paths). The delay of the bypass logic can be significant for wide issue machines [START_REF] Ahuja | The performance impact of incomplete bypassing in processor pipelines[END_REF]. Thus the performance benefits of bypassing may be accompanied by significant increase in the cycle time, chip area, energy consumption, wiring congestion, and overall design complexity. Recent research thus advocates the use of partial bypassing in processors [START_REF] Abnous | Pipelining and bypassing in a vliw processor[END_REF]. It has been shown that in a design with extensive bypasses, several bypasses have low utilization, and thus can be removed, thereby reducing the power/cost/area of the design without significantly affecting the performance [START_REF] Fan | Systematic register bypass customization for application-specific processors[END_REF]. Moreover, the bypassing in a processor can be changed in most cases without affecting the instruction set of the processor. Exploring bypasses is therefore a valuable technique for designing application specific embedded processors.

Traditionally the decision of which bypasses to add/remove is based on the designer's intuition and/or simulation-only exploration. The traditional method of exploring partial bypasses i.e. simulation-only exploration is performed by measuring the performance of the same compiled code (binary) on processor models with different bypass configurations. The configuration with the best performance is chosen. However, once a bypass configuration is chosen, a "production compiler" is developed for the chosen bypass configuration. Although it takes a lot of time and effort to develop the production compiler, finally it is able to exploit the bypasses present in the processor. It has been shown that tuning the compiler for the bypass configuration has significant impact on the performance of a partially bypassed processor [START_REF] Shrivastava | Operation tables for scheduling in the presence of incomplete bypassing[END_REF]. This implies that the performance estimation done by the simulation-only exploration incurrs significant errors. Furthermore in a simulation-only exploration, since the code that executes on the processor may not be the correct representative of the code that will be finally executed on the processor, it leads to inaccurarcies in other estimates e.g. power. There is thus a crucial need of a bypass-sensitive compiler-in-the-loop exploration of partial bypassing in embedded processors.

Embedded systems, which are characterized by multidimensional design constraints including power, perfor-mance and cost, critically require an exploration framework which is able to accurately evaluate the performance, area and energy of each design alternative and thus perform meaningful multi-dimensional trade-offs.

In this paper we present PBExplore: A Compiler-inthe-Loop Framework to explore Partial Bypassing in processors. PBExplore evaluates the performance of a bypass configuration by generating code for the processor with given bypass configuration and simulates the generated code on cycle accurate simulator of the processor with the same bypass configuration. PBExplore also synthesizes the bypass control logic and evaluates the area and energy overhead of the bypass configuration. Thus PBExplore is able to effectively perform meaningful multi-dimensional (performance-area-power) trade-offs among bypass configurations. This makes PBExplore a valuable assist for designers of programmable embedded systems.

Related Work

Bypassing has been popular since it was first described in the IBM Stretch [START_REF] Bloch | The engineering design of the stretch computer[END_REF]. The impact of bypassing on the area, cost, power, and overall chip complexity has been examined in detail, consequently suggesting the use of partial bypassing [START_REF] Cohn | Architecture and compiler tradeoffs for a long instruction word microprocessor[END_REF][START_REF] Abnous | Pipelining and bypassing in a vliw processor[END_REF][START_REF] Gray | Viper: A vliw integer microprocessor[END_REF]. Code generation techniques for partially bypassed processors and framework to customize the bypasses therein, have been proposed [START_REF] Buss | Tailoring pipeline bypassing and functional unit mapping for application in clustered vliw architectures[END_REF][START_REF] Fan | Systematic register bypass customization for application-specific processors[END_REF]. However, the compilation techniques and the frameworks are for VLIW processors only, furthermore, they employ crude cost estimates, and no energy estimates at all. Thus existing frameworks are unable to perform a multi-dimensional exploration of processors with partial bypassing, which is very important for embedded processors.

PBExplore uses a generic retargetable bypass-sensitive compilation technique proposed in [START_REF] Shrivastava | Operation tables for scheduling in the presence of incomplete bypassing[END_REF] to accurately evaluate the performance of each bypass configuration. PBExplore automatically synthesizes the bypass control logic to estimate the area and energy overhead of the bypass configurations. PBExplore is thus able to effectively and meaningfully perform multi-dimensional exploration of processors with partial bypassing.

The rest of the paper is organized as follows: In Section 3 we describe our partial bypass exploration framework. Section 3.1 describes bypass-sensitive compilation using Operation Tables. Section 3.2 discusses the issues in the design of a bypass-sensitive cycle accurate simulator. Section 3.3 describes the design of a generic bypass control logic and briefs on our area and energy overhead estimations. Section 4 we show that simulation-only exploration and our compiler-in-the-Loop exploration, differ significantly and that they may lead to different design decisions. We then perform experiments to show that PB-Explore can effectively perform a multi-dimensional exploration of partial byassing. We conclude in Section 5.

PBExplore

PBExplore is driven by bypass configuration as shown in Figure 1. All the bypasses present in the processor are descibed in the bypass configuration. A bypass is defined in terms of the pipeline stage where it is generated, and the operand that can use it. The application is compiled using a bypass-sensitive compiler that is parameterized on the bypass configuration. The generated executable is then simulated on a cycle accurate simulator that is parametrized on the same bypass configuration. The cycle accurate simulator reports the runtime (in cycles) for the application. The bypass configuration is used to synthesize the bypass control logic and estimate the area overhead of bypasses. A Power simulator uses the synthesized bypass control logic, and the input stimuli in each cycle (generated by the cycle accurate simulator) to estimate the energy consumed by the bypass control logic for the execution of the application. Thus PBExplore is able to make an accurate estimation of performance (cycles of execution), area and energy consumption overhead for each bypass configuration. We now describe the different components of PBExplore.

Bypass Sensitive Compiler

The goal of a bypass-sensitive compiler is to generate code such that operations use the bypasses present to exchange values and do not suffer from hazards due to missing bypasses. Consider the simple 5-stage processor pipeline as shown in Figure 2. The Operand Read (OR) pipeline stage is shown in detail to describe incomplete bypassing. There is a bypass from the Execute (EX) pipeline stage to the second operand in the OR. For modeling purposes we cluster all the bypasses to an operand into a virtual Bypass Register File (BRF). All the bypasses to the operand write into its The bypass from EX to the first operand is modeled using connections C4, C5 and BRF. In the processor pipeline in Figure 2, the first operand can be read from the Register File (RF) only, while the second operand can also be the result of the operation in EX. In this pipeline, if an operation in OR needs the result of the operation in EX as the first operand, there will be a pipeline hazard, while if it needs to read it as the second operand, there will be no hazard. Thus a bypasssensitive retargetable compiler needs to be cognizant of the processor pipeline and the bypasses present/absent. Operation Tables (OTs) succintly capture the processor pipeline and the bypasses present and enable the compiler to generate code sympathetic to the bypass configuration. Like RTs (reservation Tables), OTs describe the resources that an operation may use in each cycle of its execution. In addition OTs describe when an operation reads/writes/bypasses its operands, and operand itself (register identifier). OTs also describe the resources that are available read/write/bypass the operands.

The OT for a simple instruction, ADD R1 R2 R3 of a the processor pipeline in Figure 2 is shown in Table 1. The ADD operation utilizes resource Fetch (F) pipeline stage in the first cycle and Decode (D) pipeline stage in the second cycle. In the third cycle, it reads two operands R2 and R3. The first operand R2, may be read only from the Register File RF via connection C1, while the second operand, R2 can be read from the RF via connection C2, or from the BRF via connection C5. In the fourth cycle, add operation is executed and the result R1 is bypassed to BRF via connection C4. In the fifth and final cycle R1 is written back to RF via connection C3. OTs of operations in a given schedule can be combined to discover all the pipeline hazards. Table 2 shows how OTs can be used to detect data hazard between two simple dependent instructions: ADD R1 R2 R3 SUB R5 R1 R4 on the pipeline shown in Figure 2. The OT-based compiler has to maintain the state of the machine in terms of busy resources and available registers in each register file for each cycle. This bookkeeping allows the detection of data hazards (e.g. when a required register is not present in a reachable register file), and resource hazards (e.g. a required resource is busy). Table 2 shows that after scheduling the first operation (ADD), register R1 is not available in RF in cy- Thus OTs can be used to detect all the pipeline hazards in a given schedule, even in the presence of partial bypassing. This ability of accurate hazard detection can be used to reorder operations and generate bypass sensitive code. Since PBExplore is an exploration framework, and we are interested in estimating the performance potential of a bypass configuration, we look at all possible orderings of operations in a basic block, and pick up the one with best performance. Since this scheme is exponential, we impose a limit on the number of operation orderings (10, 000) that we try. This bound leaves the compile-time (few mins) negligible as compared to cycle accurate simualtion time (few hours).

Cycle Busy Resources !RF BRF ADD R1 R2 R3 SUB R5 R1 R4

Cycle Accurate Simulator

The code generated for a particular bypass configuration has to be executed on cycle accurate processor simulator with the same bypass configuration to estimate the execution cycles required for the application. Structural cycle accurate simulators that are written in sequential languages like C, model the processor pipeline by modeling pipeline stages and the pipeline registers explicitly. Modeling pipeline registers eliminates the dependencies between the pipeline stages, making it possible to execute the pipeline stages in any order. Each pipeline stage reads the pipeline register just before it, executes, and then writes the result into the pipeline register after it. Updating the contents of the pipeline register results in an increment in the simulation cycles of execution.

However, bypasses impose a dependency between the pipeline stage generating the bypass and the one using it. The bypass value generating stage should be executed before the one that uses it. To solve this problem we represent the processor pipeline using a directed graph, which has an edge from the pipeline stage that generates the bypass to the one that uses it. Any breadth first ordering of this graph (topological sort) produces a legal execution order of the pipeline stages. The cycle accurate simulator also generates the inputs and outputs of the bypass control logic every cycle. This is used by the power simulator to estimate the energy overhead for the bypass configuration.

Area and Energy Overhead Estimation

We quantify the area and energy consumption overhead of bypassing by synthesizing the bypass control logic for each bypass configuration. Figure 3 shows the bypass logic for the second operand in the OR pipeline stage in the pipeline in Figure 3, which recieves only one bypass (from the EX pipeline stage). Each operand can potentially recieve bypass from each pipeline stage. Of course for real processors that have large number of such bypasses for each operand, the bypass control logic scales and result in significant area and energy consumption overhead. Each pipeline stage that is a source of a bypass, generates a bypass value, a bypass valid and a bypass register number. If the operand to be read matches any of the incoming bypass register numbers, then the corresponding bypass value is chosen, otherwise the value from the register file is chosen. We synthesize the bypass logic using the Synopsys Design Compiler [START_REF]Synopsys Design Compiler[END_REF] and estimate the area overhead of the bypass control logic. Synopsys Power Estimator [START_REF]Synopsys Design Compiler[END_REF] is then used to simulate this bypass control logic with the input stimuli generated by the cycle accurate simulator to estimate the energy consumption of the bypass control logic.

Experiments

To demonstrate the need, usefulness and capabilities of PBExplore, we perform several experiments on the Intel XScale[10] architecture. XScale is a popular embedded processor for wireless and handheld devices. We perform experiments on benchmarks from MiBench [START_REF] Guthaus | Mibench: A free, commercially representative embedded benchmark suite[END_REF] suite, which represent applications in the same domain. Due to space constraints we present only a few results, however the results and conclusions are similar for other benchmarks. Figure 5 shows the 7-stage out-of-order super-pipeline of XScale. XScale has three execution pipelines, the X pipeline (units X1, X2, and XWB), the D pipeline (units D1, D2 and DWB), and M pipeline (units M1, M2 and Mx(referred to as MWB in this paper)). For our experiments we assume that 7 pipeline stages, X1, X2, XWB, M2, MWB, D2 and DWB can bypass to all the 3 operands in RF . Thus there are 7 × 3 = 21 different bypasses in XScale. No computation finishes before or in the pipeline units M1 and D1, thus there are no bypass connection from these units.

We synthesized the bypass control logic for each bypass configuration using design compiler of Synopsys-2001.10 and 0.8µ library lsi 10k. To estimate the area overhead we synthesized the bypass control logic for minimum delay. We used Synopsys power estimate and the input stimuli from cycle accurate simulator to estimate the energy consumed by each bypass configuration for the given application.

In the first part of experimental section, we show that performance evaluation by the simulation-only exploration and our bypass-sensitive compiler-in-the-loop exploration differ significantly, and may lead to different design decisions. In the second part we perform a multi-dimensional

Simulation-only versus Compiler-in-the-Loop Exploration

In the XScale pipeline model, we vary whether a pipeline stage bypasses its result or not. If a pipeline stage bypasses, all the operands can read the result. Thus there are 2 7 = 128 possible bypass configurations. Figure 4(a) plots the runtime (in execution cycles) of the bitcount benchmark for all these configurations using simulation-only (light squares), and compiler-in-the-loop (dark diamonds) exploration. We make two important observations from this graph. The first is that all the light squares are below their corresponding dark diamonds, indicating that the execution cycles evaluated by compiler-in-the-loop exploration is less than the execution cycles evaluated by the simulation-only exploration. This implies that the bypass-sensitive compiler is able to effectively take advantage of the bypass configuration, and is generating good quality code for each bypass configuration. The second observation is that the difference in the execution cycles for a bypass configuration can be up to 10%, implying that the performance evaluation by simulation-only exploration can be up to 10% inaccurate.

A case can be made for simulation-only exploration by arguing that the error in exploration is important only if it leads to a difference in trend. To counter this claim we will now zoom into this graph and show that simulation-only exploration and compiler-in-the-Loop exploration result in different trends, and may lead to different design decisions. Figure 4(b) is a zoom-in of Figure 4(a) and shows the ex-plorations when only the X-bypasses are varied, while the rest are present. To bring out the difference in trends, the bypass configurations in this graph are sorted in the order of execution cycles as evaluated by simulation-only exploration. Figure 4(b) shows that as per the simulation-only approach, all configurations with bypasses from two stages in the X-pipeline are similar, i.e. the execution cycles for configurations < X2 X1 >, < XWB X1 > and < XWB X2 > are similar. However, our bypass-sensitive compiler is able to exploit the configuration < X2 X1 > better than other configurations with two X-bypasses. Figure 4(c) and Figure 4(d) focuses on varying D and M bypasses while keeping the rest in-place. Figure 4(c) shows that the simulationonly exploration evaluates the performance of the bypass configurations with one bypass as equivalent. However, our PBExplore determines that if you can have only one bypass, the bypass from the D2 pipeline stage is a superior choice. We make similar observations for the M-bypass exploration in Figure 4(d).

Performance-Area-Energy Exploration

To demonstrate that PBExplore can effectively perform a multi-dimensional exploration, we vary the bypasses only for the first operand, and assume that all the bypasses reach the other two operands. Thus there are 2 7 = 128 bypass configurations. Figure 6 (a) and (b) show the performancearea and performance-energy trade-offs of various bypass configurations computed using PBExplore. The performance area and energy consumption are shown relative to that of a fully bypassed processor. The interesting paretooptimal design points 1 and 2 are marked in both the graphs.

Figure 6. Power-Area-Energy trade-offs using PBExplore

Design point 1 represents the bypass configuration when MWB and XWB do not bypass to the first operand. This bypass configuration, uses 18% less area than full bypassing and consumes 14% less energy than full bypassing, while suffering only 2% performance penalty. Similarly design point 2 represents the bypass configuration when only D2 and X2 bypass to the first operand. This configuration uses 25% less area and consumes 16% less power than fully bypassed processor, while losing only 6% on performance. These configurations represent cheaper (in area and energy consumption) design alternatives, at the cost of minimal performance degradation. These are exactly the kind of trade-offs that an embedded processor designers would need to evaluate when customizing bypasses.

Summary

Effective performance, area and energy trade-offs can be achieved by varying partial bypassing in a processor. Given that a bypass-sensitive compiler significantly affects the performance of a partially bypassed processor, simulationonly exploration of partial bypass configurations is inaccurate. In this paper we present PBExplore which not only accurately evaluates the performance of a partially bypassed processor, it also accurately estimates the area and energy overhead of a partial bypass configurations. We have shown that traditional exploration leads to sub-optimal design decisions and that PBExplore is able to effectively perform multi-dimensional performance-area-energy tradeoffs in embedded processor design. However the partial bypass design space is huge, and cannot be explored by evaluating each point. Our future work includes developing partial bypass design space walker.

Figure 1 .

 1 Figure 1. PBExplore: A Compiler-in-the-Loop Framework for Partial Bypass Exploration

Figure 2 .

 2 Figure 2. Example Processor Pipeline bypass register file, and it is read while reading the operand.The bypass from EX to the first operand is modeled using connections C4, C5 and BRF. In the processor pipeline in Figure2, the first operand can be read from the Register File (RF) only, while the second operand can also be the result of the operation in EX. In this pipeline, if an operation in OR needs the result of the operation in EX as the first operand, there will be a pipeline hazard, while if it needs to read it as the second operand, there will be no hazard. Thus a bypasssensitive retargetable compiler needs to be cognizant of the processor pipeline and the bypasses present/absent.Operation Tables (OTs) succintly capture the processor pipeline and the bypasses present and enable the compiler to generate code sympathetic to the bypass configuration. Like RTs (reservation Tables), OTs describe the resources that an operation may use in each cycle of its execution. In addition OTs describe when an operation reads/writes/bypasses its operands, and operand itself (register identifier). OTs also describe the resources that are available read/write/bypass the operands.The OT for a simple instruction, ADD R1 R2 R3 of a the processor pipeline in Figure2is shown in Table1. The ADD operation utilizes resource Fetch (F) pipeline stage in the first cycle and Decode (D) pipeline stage in the second cycle. In the third cycle, it reads two operands R2 and R3. The first operand R2, may be read only from the Register File RF via connection C1, while the second operand, R2 can be read from the RF via connection C2, or from the BRF via connection C5. In the fourth cycle, add operation is executed and the result R1 is bypassed to BRF via connection C4. In the fifth and final cycle R1 is written back to RF via connection C3. OTs of operations in a given schedule can be combined to discover all the pipeline hazards. Table2shows how OTs can be used to detect data hazard between two simple dependent instructions: ADD R1 R2 R3 SUB R5 R1 R4 on the pipeline shown in Figure2. The OT-based compiler has to maintain the state of the machine in terms of busy resources and available registers in each register file for each cycle. This bookkeeping allows the detection of data hazards (e.g. when a required register is not present in a reachable register file), and resource hazards (e.g. a required resource is busy). Table2shows that after scheduling the first operation (ADD), register R1 is not available in RF in cy-

Figure 5 . 7 -Figure 4 .

 574 Figure 5. 7-stage super-pipeline of XScale 4

Table 1 . Operation Table of ADD R1 R2 R3 cle

 1

	Operation Table of ADD R1 R2 R3
	1 F
	2 D
	3 OR
	ReadOperands
	R2
	C1, RF
	R3
	C2, RF
	C5, BRF
	DestOperands
	R1, RF
	4 EX
	WriteOperands
	R1
	C4, BRF
	5 WB
	WriteOperands
	R1
	C3, RF

[START_REF] Buss | Tailoring pipeline bypassing and functional unit mapping for application in clustered vliw architectures[END_REF]

. Register scoreboarding makes destination of a issued instruction unavialble in the register file until it is written back to to avoid a WAW hazards. The next operation (SUB) can read R1, its first operand only from RF (due to absence of a bypass from EX pipeline stage to the first operand of RF). Thus there is a data hazard in cycle 4. The data hazard is cleared in the next cycle (cycle 5), when R1 becomes available via RF.

Table 2 . Hazard detection using OTs

 2

	EX_reg	EX_value
	EX_valid
	RF_valid	RF_value
	reg_no
	==
	AND
		MUX
	OR
	value	valid
	Figure 3.

Bypass control logic for the second operand

Execution cycles compared to full bypassing Area compared to full bypassing 1 2 Performance Energy Trade-off

	105%		Performance Area Trade-off				105%
	100%								100%
	70% 75% 80% 85% 90% 95%						Energy compared to full	bypassing	80% 85% 90% 95%	1	2
	65%								75%
	60%								70%
	100%	105%	110%	115%	120%	125%	130%		100%	105%	110%	115%	120%	125%	130%
												Execution cycles compared to full bypassing

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)

Acknowledgements

This work was partially funded by Intel Corporation, UC Micro (03-028), SRC (Contract 2003-HJ-1111), and NSF (Grants CCR-0203813 and CCR-0205712). We would also like to thank members of ACES lab, especially Partha Biswas for helping crystallize our thoughts in the brainstorming sessions.


C Bolchini

F Salice

D Sciuto
email: sciuto@elet.polimi.itl.pomantecefriel

Reliable System Specification for Self-Checking Data-Paths

The design of reliable circuits has received a lot of attention in the past, leading to the definition of several design techniques introducing fault detection and fault tolerance properties in systems for critical applications/environments. Such design methodologies tackled the problem at different abstraction levels, from switch-level to logic, RT level, and more recently to system level. Aim of this paper is to introduce a novel system-level technique based on the redefinition of the operators functionality in the system specification. This technique provides reliability properties to the system data path, transparently with respect to the designer. Feasibility, fault coverage, performance degradation and overheads are investigated on a FIR circuit.

Introduction

When embedded systems implement critical applications they should exploit a certain degree of reliability; in particular, Concurrent Error Detection (CED) capabilities are frequently a requirement, since in critical operational environments error propagation can have catastrophic effects.

In the past, a set of techniques [START_REF] Jha | Design and synthesis of Self-Checking VLSI circuits[END_REF][START_REF] Pradhan | Fault-tolerant computing: theory and techniques[END_REF] has been proposed (for both combinational and sequential devices) in order to provide such CED property by acting directly at low abstraction level, toward the end of the hardware design flow. However, time-to-market constraints and the increasing complexity of modern devices make it impossible to manage the problem at such a low level and a different approach, able to raise the abstraction level, is necessary. As a matter of fact, standard design methodologies target devices by starting from system level specifications. At this description level, the system specification identifies the functional characteristics of the application without detailing implementation aspects. Because the insertion and the use of reliability methodologies significantly impacts on performance, timing, energy and area, it is necessary to transfer these aspects toward the upper levels of the synthe-sis flow, by adding the reliability constraints to the classical cost/performance parameters. Our goal is to define a codesign methodology able to integrate CED capabilities from the first steps of the design process, so to achieve a reliable system. The need of frameworks for reliable co-design has been already highlighted in the last years, leading to the development of approaches able to manage reliability at system level. However some of the studies presented in literature [START_REF] Teixeira | Test resource partitioning: a design and test issue[END_REF] focus on Design for Testability (DfT) techniques defined at system-level without considering CED approaches. Other works [START_REF] Bolchini | Reliability properties assessment at system level: A co-design framework[END_REF] consider such kind of property by means of a tagged specification used to drive a special two-level partitioning to identify the proper reliable design methodology to be used in the subsequent steps of the system design process. Another important work is the one presented in [START_REF] Dave | Cofta: Hardware-software cosynthesis of heterogeneous distributed embedded system architectures for low overhead fault tolerance[END_REF] where a task-graph based co-design environment (suited for specific application domains) provides error detection properties based on duplication or assertions. However, the use of such assertions is not transparent to the designer and a quantitative evaluation of the fault coverage cannot be computed. The proposal in [START_REF] Arnstein | A general consistency technique for increasing the controllability of high level synthesis tools[END_REF] considers behavioral assertions to drive a high-level synthesis tool: such an approach is interesting but it is hardware oriented and the assertions involved are related only to area and performance issues (i.e. no fault tolerance). In [START_REF] Cheynet | System safety through automatic high-level code transformations: an experimental evaluation[END_REF] a software modification strategy is proposed for on-line fault detection; the authors define a set of rules for explicitly introducing redundancy in the high-level code, in some specific situations. This paper presents a novel approach to reliable system design by exploiting the SystemC-Plus object-oriented features that can be applied in the more general framework proposed in [START_REF] Bolchini | Reliability properties assessment at system level: A co-design framework[END_REF]. The methodology is presented in detail with respect to a limited running case in order to describe both advantages and drawbacks of the approach. The methodology, as it is, has led to significant results, yet it is currently under development in order to better exploit the potential benefits of the adopted mechanisms, while minimizing the present limitations. The methodology considers SystemC-Plus descriptions as a starting point, thus giving the possibility of synthesizing the enriched specification either in hardware or in software, the proposed approach is independent of the final implementation and thus it can be exploited in a complete co-design flow (e.g. simulation, partitioning, synthesis, etc.) without any specific intervention, and so obtaining a straightforward way to reach a reliable hw/sw implementation.

This paper is organized as follows. Section 2 describes the key elements of the proposed approach, whereas the details of the defined self-checking class are introduced in Section 3. Section 4 discusses the quality of the technique, investigating fault coverage issues for several target architectures. The proposed co-design flow is presented in Section 5, with the results of the FIR benchmark application. The last section draws some conclusions and future work.

The proposed approach

In the following the key elements of the proposed approach are detailed: the specification language, the fault model, the design methodology, the target architecture and the coverage analysis. Specification language. The proposed approach is based on the SystemC-Plus specification language [START_REF]SystemC+[END_REF], a proper extension of the synthesizable Synopsys-subset of SystemC [START_REF]SystemC Reference Manual[END_REF], that allows full exploitation of objectoriented features (inheritance, polymorphism, etc.) in the specification, while keeping hardware and software synthesis capabilities. Fault Model. The adopted fault model consists of the single functional unit failure, where any number of physical faults can cause one (and only one) functional unit to perform incorrectly. The considered faults affect the target platform, mining hardware and software execution units. The functional units considered in this work are those dedicated to perform the basic arithmetic and logical computations (e.g. ALUs, multipliers, shifters, etc.), i.e. those that can be mapped directly onto the operators (arithmetic, logic or bit-a-bit) used in the specification (e.g. =, +, -, *, etc.). The functional failure is modeled by means of a variable number of errors (e.g. stuck at, bit-flip, etc.) affecting the bits of the result provided by the faulty unit. Both permanent and transient and intermittent faults are covered by our approach, the latter increasingly like to occur in any integrated device, due to the technology trend that reduces size and increases operating frequency ([12]). Design methodology. According to the adopted fault model, the idea is to provide the designer with the possibility of using a self-checking data type that autonomously performs controls on data resulting from basic computations. The verification of results' correctness is achieved by means of one or more functional redundancy mechanisms (the number and the complexity of such mechanisms will depend on the desired trade-off between fault coverage, cost and performance) as typically adopted in the software field (e.g. software checking [START_REF] Wasserman | Reflections on the pentium division bug[END_REF][START_REF] Shreve | Real-time Checkers: Built-in Test for Mission Critical Software[END_REF][START_REF] Wasserman | Software reliability via runtime result-checking[END_REF][START_REF] Reinhart | Applying checkers to improve the correctness and integrity of software[END_REF], and assertion [START_REF] Kanawati | Evaluation of integrated system-level checks for on-line error detection[END_REF][START_REF] Alkhalifa | Design and evaluation of system-level checks for online control flow error detection[END_REF][START_REF] Guerreiro | Another mediocre assertion mechanism for c++[END_REF]). Target architecture. Because the specification is independent of the target platform, the proposed approach does not need any particular information about the final architecture. The resulting implementation (totally hardware, totally software with one or more processors, or a mix of them) depends on the adopted design flow and the constraints to be satisfied, as in any hw/sw codesign flow.

Coverage analysis

The effectiveness of the proposed self-checking technique is evaluated in terms of the achieved fault coverage and the additional costs. Both qualitative and quantitative analyses have been carried out. As an example, consider the z=x+y operation, controlled by the inverse operation w=z-x (in this case the controlling mechanism is w==y). Referring to the adopted fault model, two situations can be envisioned. Using a multi functional resource system and a proper allocation/scheduling policy it is possible to achieve a 100% fault coverage if different functional units perform the two operations. On the other hand, a software implementation on a monoprocessor system (or a limited resource hardware system) could lead to a solution where the same functional unit could perform both operations. In the latter case there could be faults causing undetected erroneous data affecting the fault coverage to some degree since one unit performs the operation and its control. For example, there could be a situation where, by means of an undesired error masking (or error compensation), an erroneous z' could lead to a w'=z'-x, with w' coincident to y so nullifying the error control. Section 5 dedicates particular attention to the worst-case fault coverage evaluation, investigating the probability of a fault causing consistent error compensation when performing two related operations.

In the following the + operator and its underlying hardware adder component will be used as running example, without loss of generality. The same considerations apply to any arithmetic/logical component working on integer data, in a straightforward manner; only the overall cost/performance results are here reported. The limitation to integers depends on SystemC ability to synthesize only this type.

Class template SCK<TYPE>

The operative element of the proposed approach is the SCK class template (it is the only SystemC-Plus exten-sion used with respect to synthesizable SystemC). The use of a class template in C++ fashion (e.g. as proposed in [START_REF] Macphee | A framework for dynamic checks in c arrays via a C++ class[END_REF] where a very similar approach is used to prevent errors in the software design) allows the designer to adopt it with all the synthesizable basic data types by changing only the data declaration. A proper overloading mechanism of the basic operators applies the desired reliability-oriented mechanisms, while the SystemC-Plus features will guarantee the synthesizability property. For example, when using an SCK<int> data type, the operator + will verify the consistency of its result by means of an inverse operation (i.e. operator -), consequently updating the value of an error bit associated with the data itself. Operators are designed to propagate also the error bit value. As a result, we obtain a specification that includes the operations verifying the correctness of the provided results, while keeping a minimal impact on the way the system is specified.

Operator overloading is not an innovative technique, although it has been employed in the past for different goals and generally for dealing with software properties, rather than being used to detect hardware failures as in the present approach.

SCK interface

Figure 1 shows the interface of the class SCK (limited in this example for clarity to operators = and +). The error bit E has been introduced and associated with the internal data ID, together with the methods used to manage such data (GetError and GetID) and the prototypes of the useful versions of the two operators. It is worth noting that the presence of the empty constructor is due to synthesis constraints. For example, a different implementation of the + operator uses the (z-y==x)&&(z-x==y) control condition proving higher fault coverage and hardware cost.

SCK implementation

A similar hidden control mechanism has been defined for the other arithmetic operators, taking also into consideration problems related to the precision of the inverse operation (for the division case); It is worth noting that there is no available tool for evaluating the fault coverage of the final realization with respect to the on-line fault detection properties, yet the local fault coverage analysis (carried out with an exact fault detection analysis for the single arithmetic units) can be used as an estimation of the reliability level that will be achieved.

Fault coverage analysis

The effectiveness of our approach relies on the percentage of faults that may cause undetected errors when using a system with limited resources such that the nominal operation and its controlling operation cannot unveil a fault, as introduced in Section 2.1. An in-depth analysis based on the integer faulty class has been carried out. For example, using the FAddFSubIntC faulty type, a fault causing an error on the addition could produce also an error on the subtraction operation such that the fault is not detected. This consideration highlights the need for a detailed low-level analysis to evaluate the fault coverage guaranteed by the proposed approach with respect to several target architectures.

Let us consider, as an example, instruction c=a+b. As shown in Figure 2, the enhanced operator + will perform the addition a+b and will also perform the hidden operation d=c+(-a) followed by a comparison between d and b. In a fault free situation, with the exception of overflows (which are separately dealt with) d equals b; no error indication set. On the other hand, when a fault occurs within the adder (and c=a+b produces c' instead of c) when performing the hidden operation d'=c'+(-a), one of the following situations may arise:

1. the operation is performed on a different functional unit (fault free for hypothesis), thus the resulting value d' is different from b: the fault is detected; 2. the operation is performed on the same faulty unit, in this case two are the possible outcomes: (a) d' differs from b: the fault either is not observable, hence d' is the correct result of the operation, or is observable and detected. (b) d' equals b: the fault is observable in such a way that an erroneous result is produced, but in such a way that the two errors mask the fault.

Situation (2b) is the critical one and it affects the fault coverage due to the presence of faults that the methodology cannot cover. It is worth noting that the problem arises only when the same resource is used to compute both the related operations: it is thus necessary to evaluate the exact fault coverage that is achievable by means of the proposed approach in such a situation (worst case analysis), as discussed in the following.

The testing environment

Fault coverage is evaluated at hardware level, by considering the target architectures and the faults included in the adopted fault model. A specific test architecture has been defined to analyze the faults masking effects with respect to the pairs of operations used within the overloading of the SCK class operators. More in detail, we simulate faults effects considering the pair of operations that are implemented in the enhanced operator (e.g., + andfor operator +) when they are performed on the same functional unit. The test architecture is independent of the actual implementation, and can be used with different technological choices, with a carry look-ahead implementation of an adder, as well as with a ripple carry implementation. Two environments have been setup, in VHDL and C. The g function, when needed, is the one used to produce the value for the dual operation (e.g. in the case of the + and -operations pair, the g function performs the 1's complement and the f function receives a 1 on the carry-in to work in 2's complement).

Table 2 shows how the coverage analysis has been carried out, reporting the experimental results obtained for a ripple-carry adder performing the + operation, where "Tech 1" refers to a single overloading of the operator using as control operation op2=ris-op1; "Tech 2" refers to the dual controlling operation op1 = ris-op2; the third approach ("Tech 1&2") includes both overloading strategies.

To obtain results independent of the actual implementation of the adder (e.g. FPGA, ASIC with standard or fullcustom, etc.), functions f, g and faults have been modeled at the functional level (i.e. the faulty functional unit is the single full-adder in the chain composing the n-bit adder). The first column of Table 2 refers to the width of the operands used to perform the computation, ranging from 1 to 12 bits. The second column reports the total number of fault situations for each case, dependent on the number of input combinations and faults in the adder, given by the following equation:

No. of faulty situations = num faults 1bit × n × 2 2n
where n is the operand size, num f aults 1bit the number of faults for the 1-bit adder which equals 32. This result is used to evaluate the achieved fault coverage. The other columns report how the detection capability varies with respect to the different overloading strategies for the + operator. Each entry shows the achieved fault coverage, that is the number of times the methodology guarantees that the result is either correct or an error signal is raised. For example, using 2-bit operands, the adoption of the control operation op2=ris-op1 does not allow the detection of a fault causing an observable error in 32 situations, a fault coverage of 96.88%. The number of undetected errors drops, though implying a higher overhead in terms of computational time and/or area overhead.

Another interesting measure consists of the capability of the methodology to detect the fault, independently of the fact that it produces an erroneous result or not (i.e. independently of the fault observability). By analyzing the 2bit adder case, the number of observable errors is 216 yet in almost all approaches the technique allows fault detection also when the produced result is correct: 352 (out of 1024) for "Tech1", 384 for "Tech2" and 428 for the combination of both. This property allows the reduction of the probability of a second fault occur before the first one is detected, thus improving the system reliability. It is worth mentioning that classical Self-Checking design techniques provide fault detection capabilities only when the fault is observable. In conclusion, the example shows that for a ripple-carry adder (independently from its actual implementation) using different functional units to perform related operations the coverage is always 100%; using the same unit the percentage of input combinations that by-pass the checks varies, depending on the adopted strategy, in the range [81.90%, 99.87%].

The same approach has been applied to the other operators (-, *, and /), analyzed w.r.t. several overloading techniques and their combination, achieving similar results in terms of fault observability and fault coverage.

The reliable co-design flow

This section shows the reliable co-design flow based on self-checking specification used to evaluate cost and performance of the proposed approach. Starting from a selfchecking specification in SystemC-Plus, the design flow adopted (the flow is OFFIS [START_REF]SystemC+[END_REF] and Synopsys [16] based for the HW part, GNU [7] based for the SW one) is shown in Figure 3. By means of the OFFIS SystemC-Plus Synthesizer, SystemC-Plus is transformed into synthesizable behavioral and/or RT SystemC. By means of the g++ compiler we can easily obtain the software implementation, with Synopsys CoCentric the hardware one.

Methodology evaluation

By implementing both the reliable and not-reliable system specification a comparison in terms of costs and performance has been carried out, to evaluate the quality of the proposed approach on the final system. A FIR circuit has been designed with the proposed design flow [START_REF] Bolchini | Reliable system co-design: the fir case study[END_REF], allowing an in-depth analysis of the approach. Several experiments have been carried out on the same circuit and results are reported in Table 3, while other circuits are now taken into consideration. Table 3. Application of the proposed methodology to the FIR.

Results on this example are encouraging as far as the overloading mechanism is concerned, especially since such an approach has been used in the past but for different environments and purposes. The most significant aspects are:

• extensible reliability library: the overloading mechanism provides a flexible and extensible way to define a library or readily-available Self-Checking designs for the basic operators, each one with a cost/fault coverage characterization; the designer can select different self-checking approaches depending on the trade-off. • information hiding: the most complex aspects related to reliability are transparent to the designer, for both hardware and software implementations. • standard technology: the use of a mechanism part of the specification language allows the approach to be integrated in any SystemC hw/sw co-design flow.

On the other hand, the application of the approach pointed out the possibility of incurring in template conflicts when templates for overloading are already part of the original description. In such a case the proposed approach cannot be adopted.

This last motivation, together with the desire to be independent of proprietary software (such as the converter from SystemC-Plus to SystemC), is leading to the evolution of the proposed approach to virtually exploit the overloading mechanism directly in the SystemC description.

When the software implementation is selected, analyses have been carried out to verify that the redundant operations for achieving the desired reliability are not "simplified" by the compiler thus nullifying the operator overloading efforts. Both code size and execution times remain almost unmodified.

Let us remember, that the achieved fault coverage is complete for hardware implementation, whereas software implementations are characterized by the coverage estimated for the single functional unit, where the lowest estimated value is about 98%.

Concluding remarks

The paper proposes a methodology for designing circuits with reliability properties by introducing in the initial system specification elements able to provide the ability to autonomously detect the occurrence of hardware faults. The approach provides such on-line testing capabilities by using the overloading mechanism for the SystemC-Plus language, today's specification language for hardware/software codesign flows. In a manner that is completely transparent to the designer, "hidden" operations perform additional computation to verify the correctness of the resulting data. The achieved results in terms of fault coverage are promising and future work will focus on the trade-off between fault coverage and costs, in order to allow the designer to select the desired level of reliability while keeping area overhead and performance degradation within an acceptable limit.

Figure 1 .

 1 Figure 1. The SCK interface.

Figure 2

 2 Figure 2 shows the self-checking implementation of the operator + used in the SCK class. The code shows the strat-

Figure 2 .

 2 Figure 2. Self-Checking operator +.

Figure 3 .

 3 Figure 3. The reliable co-design flow.

Table 1

 1 reports the most promising overloading techniques we evaluated.

	Operators		Techniques
		Tech1	Tech2	Both
	Add +	op2' = ris -op1	op1' = ris -op2
	ris = op1+op2	op2 == op2'	op1 == op1'
	Fault Cov.	97.25%	98.81%	99.11%
	Sub -	op1' = ris + op2	ris' = op2 -op1
	ris = op1 -op2	op1 == op1'	0 == ris + ris'
	Fault Cov.	96.85%	94.01%	99.58%
	Mult +	ris' = (-op1)×op2	ris' = op1×(-op2)
	ris = op1×op2	0 == ris + ris'	0 == ris + ris'
	Fault Cov.	96.22%	96.38%	97.43%
	Div /	op1' = ris×op2	op1' = -ris×op2	-
		+ (op1 % op2)	-(op1 % op2)
	ris = op1 / op2	op1 == op1'	op1 == op1'	-
	Fault Cov.	94.33%	97.16%	-

Table 1 . Overloading techniques and fault coverage.

 1

Table 2 . Experimental results for different overloadings

 2

for operator +.

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