Gokhan Memik
email: memik@ece.northwestern.edu

Mahmut T Kandemir
email: kandemir@cse.psu.edu

Ozcan Ozturk
email: ozturk@cse.psu.edu

Increasing Register File Immunity to Transient Errors*

Transient errors are one of the major reasons for system downtime in many systems. While prior research has mainly focused on the impact of transient errors on datapath, caches and main memories, the register file has largely been neglected. Since the register file is accessed very frequently, the probability of transient errors is high. In addition, errors in it can quickly spread to different parts of the system, and cause application crash or silent data corruption. This paper addresses the reliability of register files in superscalar processors. Particularly, we propose to duplicate actively used physical registers in unused physical registers. The rationale behind this idea is that if the protection mechanism (parity or ECC) used for the primary copy indicates an error, the duplicate can provide the data as long as it is not corrupted. We implement two types of strategies based on this register duplication idea. In the "conservative strategy," we limit ourselves with the given register usage behavior, and duplicate register contents only on otherwise unused registers. Consequently, there is no impact on the original performance when there is no error, except for the protection mechanism used for the primary copy. Our experiments with two different versions of this strategy show that, with the more powerful conservative scheme, 78% of the accesses are to the physical registers with duplicates .The "aggressive strategy" sacrifices some performance to increase the number of register accesses with duplicates. It does so by marking the registers not used for a long time as "dead" and using them for duplicating actively used registers. The experiments with this strategy indicate that it takes the fraction of the reliable register accesses to 84%, and degrades the overall performance by only 0.21% on the average.

INTRODUCTION

Both consumer and business electronic product owners today are demanding high reliability in addition to high performance. With shrinking feature sizes, reducing supply and threshold voltages, transient errors are becoming an important problem. Such errors can occur even with zero-defect product and cause single-event upsets, which can eventually lead to application crash or wrong output. Moreover, the transient error problem is expected to be even more pressing in the future due to aggressive scaling-down of the supply voltages (V dd ), ever-scaling feature sizes, increasing clock rates, and the use of flip-chip packaging. Even if the error probability for a single transistor can be kept constant in the future, the overall error probability in a chip is going to increase in parallel with the number of transistors on a chip. While it is critical to put every effort to avoid these errors by careful circuit design and packaging, they can still occur and need to be addressed. While recent research has mainly focused on the impact of errors on main memories [START_REF] Dell | A White Paper on the Benefits of Chipkill-Correct ECC for PC Serve Main Memory[END_REF], cache structures [START_REF] Chen | Fault Containment in Cache Memories for TMR Redundant Processor Systems[END_REF][START_REF] Kim | An Adaptive Write Error Detection Technique in On-Chip Caches of Multi-Level Caching Systems[END_REF][START_REF] Kim | Area Efficient Architectures for Information Integrity in Cache Memories[END_REF], and the datapath [START_REF] Shivakumar | Modeling the Effect of Technology Trends on the Soft Error Rate of Combinational Logic[END_REF], the register file has largely been ignored. Although the register file itself does not occupy a large on-chip area, it is accessed very frequently. As a result, chances for a transient error in the register file to occur are high. In addition, a register error, if not taken care of, can quickly propagate to the other parts of the system. In light of this, several processor architectures employ error detection and recovery schemes in their register files, e.g. IBM G5 uses an ECC-based scheme [START_REF] Reinhardt | Transient Fault Detection via Simultaneous Multithreading[END_REF]. In fact, soft errors in register files can lead to a large number of system failures [START_REF] Dupont | Soft Error: A new skill in semiconductor business[END_REF][START_REF] Rebaudengo | An Accurate Analysis of the Effects of Soft Errors in the Instruction and Data Caches of a Pipelined Microprocessor[END_REF]. In addition, due to the high operation frequency, register files are not immune to other types of transient errors (e.g., errors due to inductive noise). There are at least two obvious ways of protecting register files against transient errors. First, one can use parity to detect any odd number of bit errors. While a parity-based protection is not expensive to accommodate (from both performance and energy perspectives), it is limited since no error correction is provided. An ECC scheme, on the other hand, can correct single or multiple bit errors. However, this advantage comes at the expense of increased power consumption and latency. Even a simple ECC can take up to three times the delay of a simple ALU operation [START_REF] Tremblay | Support for Fault Tolerance in VLSI Processors[END_REF]. More importantly, the energy consumption of an ECC-based scheme can be as high as an order of magnitude larger than the energy consumed during a register access [START_REF] Phelan | Addressing Soft Errors in ARM Core-based SoC[END_REF]. Realistically speaking, most of the errors that occur are single bit errors, and a scheme that can successfully correct single bit errors without incurring power/performance problems seems to be highly desirable. 1 for processor configuration. Superscalar processors have been traditionally used to increase the performance in general-purpose architectures. Due to their complexity, their usage in embedded systems was limited. However, recently we are seeing increasingly more superscalar designs for embedded systems, e.g., STMicroelectronics [START_REF]STPC Microcontrollers -Overview[END_REF], ARM [START_REF] Eetimes | Two call on superscalar CPUs for handset apps[END_REF], Renesans and Hitachi [START_REF]Renesas and Hitachi announce development of 32-Bit RISC CPU Core for Embedded Systems[END_REF]. Our scheme targets such superscalar machines. In search for an error correction scheme that incurs small power and performance penalties, we studied the register usage of the Spec2000 benchmarks. Figure 1 plots the fraction of the physical registers that are allocated (i.e., that are mapped to a logical register or hold valid data) during the execution for 253.perlbmk and 172.mgrid benchmarks (the details of our experimental setup and simulation parameters will be given later). One can see from these plots that, while the register usage behavior changes during the course of execution, a significant fraction of the physical registers (in particular for the 172.mgrid) are not used. Based on this observation, this paper proposes to use unused physical registers as duplicates for the actively used ones. Specifically, we investigate two different strategies: conservative and aggressive. In the conservative strategy, we limit ourselves with the given register usage behavior of the application being executed. That is, we duplicate active registers in the unused ones without affecting the original execution cycle count of the application. We evaluate two different implementations of this conservative strategy.

In the conservative-base (CB) version, whenever we allocate a new physical register, we create a duplicate for it, either in an unused register or over another duplicate. In the conservative-enhanced (CE) version, when creating a new duplicate over an existing one, we select the victim duplicate carefully, considering the frequency of register usage. Also, we initiate a copy operation whenever a register becomes available. A common characteristic of these two versions is that they do not increase the original number of execution cycles. As a consequence, when the register pressure is very high, they tend to perform no duplication. In comparison, the aggressive strategy creates a duplicate at the expense of performance. The main idea is to predict the cases where a physical register is not going to be used in the future, and (after writing its contents to memory) use it for duplicating the contents of an active physical register. We used 20 applications (10 integer and 10 floating-point) from the Spec2000 benchmark to evaluate our strategies. Experimental results obtained using SimpleScalar [START_REF] Burger | SimpleScalar Tool Set[END_REF] indicate that using the most powerful conservative scheme results in nearly 78% of the register accesses to have their duplicates (which is a good guarantee in case the protection mechanism of the primary register indicates an error).

Our experiments also show that the aggressive scheme brings up the number of such reliable register accesses to 84% on the average, at the expense of a slight degradation in the original performance (0.21% on the average across all benchmarks). The rest of this paper is organized as follows. The next section explains the default physical register allocation mechanism. Section 3 presents our experimental setup. Section 4 gives the details of the proposed duplication-based strategies, and presents experimental data showing their effectiveness. Section 5 discusses the related architectural-level work on reliability. Section 6 concludes the paper by summarizing our observations.

CONVENTIONAL REGISTER RENAMING

If the number of physical registers is sufficient, register renaming removes the write-after-read (WAR) and write-after-write (WAW) hazards, allowing higher levels of instruction-level parallelism (ILP) to be achieved at runtime. This is achieved by mapping logical registers to physical registers dynamically during the execution. Specifically, each new logical register value is mapped to a different physical register. Therefore, even if the instructions are executed out-of-order, no WAR or WAW hazards will occur.

For each fetched instruction, two tasks have to be performed to complete renaming: A new physical register has to be allocated for the destination register(s), and the source registers should be renamed to corresponding physical registers. There are several possible implementations to achieve this. In this work, we employ a scheme similar to that of Alpha 21264 [START_REF] Kessler | The Alpha 21264 Microprocessor[END_REF], where the renamed and architectural register files are merged into a single register file, and there is a separate table for mapping logical registers to physical, each physical register can be in one of the following four states: not used or available (NU); used as an architectural register (AR); allocated, but not valid (AN): allocated-valid (AV). Initially, only the physical registers that correspond to the logical registers are in the AR state, all the remaining registers are in the NU state. When a register is allocated for a logical register, it is transitioned to the AN state. Then, when the instruction in question writes the value to the register, the register is placed into the AV state. When the instruction completes, the register is placed into the AR state. We modify this model to achieve a precise rollback and to keep track of "in-flight" instructions, i.e., the currently executing instructions that have a physical register mapped as a source register. If an instruction is squashed, we need to rollback only the corresponding registers to their original states and values. In recent Pentium family microprocessors [START_REF] Hinton | The microarchitecture of the Pentium 4 processor[END_REF] this is achieved with the help of a Reorder Buffer. We, on the other hand, extend the Reservation Station (RS) to hold the previous mapping information for the destination registers. We also keep track of whether the RS entry corresponds to an instruction that is the last consumer for a particular physical register and which RS entry was the previous last consumer for this source register. This instruction is used to transition the physical register state to AR or NU. Only the last consuming instruction changes the state of a register during its commit stage. If the last consumer instruction completes and the logical register is already mapped into another physical register, the register can be placed directly into the NU state; otherwise, it is transitioned to the AR state. If the last consuming instruction is squashed, we use the previous RS entry field to retrieve the information about the previous last consumer. If this instruction has already committed, we can change the state to AR or NU. In our experiments, we do not differentiate between AR, AN, and AV states: as far as our techniques are concerned, all these registers are considered as "active" registers. Hence, we only differentiate between registers that are not in use and registers that are active.

EXPERIMENTAL SETUP

In the rest of this paper, we explain each proposed technique followed by the presentation of its experimental results. Therefore, we first present our experimental setup.

SIMULATION PARAMETERS AND BENCHMARKS

The SimpleScalar/Alpha [START_REF] Burger | SimpleScalar Tool Set[END_REF] simulator is used to evaluate the proposed techniques. The necessary modifications to the simulator have been implemented to perform register renaming, error injection, and the proposed error protection strategies. Some of the schemes use the selective replay capabilities that exist in some modern microprocessors such as Intel Pentium 4 [START_REF] Kim | Understanding Scheduling Replay Schemes[END_REF]. Selective replay is used to selectively rollback instructions that were not able to execute correctly because of a misprediction. Therefore, we have also made changes to SimpleScalar to simulate a realistically sized issue queue, and to simulate a realistic scheduler under selective replay. The base architecture is a 4-way superscalar processor with 32 logical and 80 physical integer and floating point registers, 16 KB, 4-way associative level 1 instruction and data caches and a 256 KB, 8-way unified level 2 cache. We simulate 10 floating-point and 10 integer benchmarks from the SPEC2000 benchmarking suite. We simulate 300 Million instructions after fast-forwarding an application-specific number of instructions as proposed by Sherwood et al. [START_REF] Sherwood | Basic Block Distribution Analysis to Find Periodic Behavior and Simulation Points in Applications[END_REF]. The important statistics for our applications are given in Table 1. We see from this table that the number of register accesses is much higher than the number of L1 data cache accesses, which indicates that the chances for a transient error in the register file to be consumed are higher than that of a cache error. The last two columns of the table give the number of errors we inject into the register file during the simulations and how many of those injected errors cause a fault.

ERROR INJECTION

To test the effectiveness of the error protection techniques proposed in this paper, we inject errors into the register file. These errors can change the value stored in the register file (representing soft errors), or they can occur during the reading or writing the register value (representing other types of transient errors). The former is achieved by using a random number generator to trigger an error in a random location in the register file. This generator is invoked at every simulation cycle. The error probability is set to 10 -7 per each bit in the register file in accordance with literature [START_REF] Li | Soft error and energy consumption interactions: a data cache perspective[END_REF]. All the base experiments use this probability. Later, to conduct a sensitivity analysis, we have also performed some experiments with a larger probability. Similarly, for the latter type of errors, in every access to the register file (including register writes), we generate an error with the same probability. In accordance with other studies, the probability of two-bit errors is set to 10 -9 and the probability of three-bit errors is set to 10 -11 [START_REF] Li | Soft error and energy consumption interactions: a data cache perspective[END_REF].

ERROR PROTECTION STRATEGIES 4.1 CONSERVATIVE STRATEGIES

The conservative strategies proposed in this work utilize only the physical registers that are not used by the register renaming mechanism. Consequently, they do not degrade the performance compared to the base architecture.

CONSERVATIVE-BASE (CB)

In the base architecture, the RRC has information about the physical registers that are not used. Therefore, when we allocate a new physical register, we also allocate a register that will be used for copying the register value 1 . The copy register name is placed into the RUU (or the Reservation Station). At the writeback pipeline stage, the copy register is also written. In CB, this is the only time when a copy can be generated. Note that, the RRC can later allocate the copy register to be used for storing copies of other register values. In addition, the copy register can also be activated, i.e., logical registers can be mapped to it. Therefore, even if during the execution of the program all the physical registers are active, there is no performance penalty caused by CB. Figure 2 depicts the structures that are modified for CB. There are three important modifications. First, the RRC is enhanced to select a copy register and store the copy register name for any physical 1 The register that stores the copy value is called the copy register.

register that has a copy. Also, a physical register can be in an additional state called copy, which indicates that it is used as a copy register (duplicate). For CB, this information is only needed during an error. Second, the Reservation Station is also enhanced to store the name of this copy register to enforce the copy operation during the execution of the instruction. Therefore, the path between the register file and the RS should be modified to contain this information. Finally, we need to make a modification to the register file as well. Specifically, it should be enhanced to perform the copy operation. For CB, copy operations are performed only during the write operations. Therefore, we can add a "copy" port for each write port in the register file. Any input in the copy port would force the corresponding write value to be copied in the given register name.

Note that, additional ports can potentially have an impact on the access time of the register file. However, the complexity of implementing the copy operation discussed here is expected to be less compared to having an additional write port, because the values written to the registers will be the same. Hence, we only need to receive two register numbers and one value as input and write the value to both the registers. In addition, compared to alternative reliability measures (such as ECC 3 ), the increased complexity of this addition would be smaller. In any case, if this extra delay is intolerable, one option might be to perform the copy operation at the background (e.g., one cycle after the actual write). Irrespective of the error detection mechanisms, we can use two metrics that can demonstrate how our duplication-based schemes are performing in practice. The first of these is called the duplication success rate, which is defined as the fraction of successful duplication attempts. The second metric is the reliable read rate, which gives us the fraction of time we read a register for which a duplicate exists. Of these, the reliable read rate is more important since we ultimately want to maximize the number of times where the accessed physical register has its duplicate. Figure 3 presents the results for both statistics. Figure 3(a) gives the duplication success rate for CB (due to lack of space, we only present the results for two applications and averages). We find that the duplication success rate is around 85% for the integer benchmarks and 88% for the floatingpoint benchmarks. These values are reasonable since the only time a duplication attempt can fail is when all the physical registers are active, which happens rarely in a typical execution. We also see that majority of the duplicates are made to empty physical registers. This is mainly because in this scheme when a duplicate is overwritten (by another duplicate or a primary copy), it is not restored. When we look at the reliable read rates given in Figure 3(b) (marked as has copy), we find that on the average 71% of the reads are made to the registers with duplicates. This result tells us that 71% of the time we can correct odd number of bit errors if the duplicate is clean (assuming that the registers are protected using parity). CB has two main drawbacks. First, in many cases, it might happen that a register can lose its duplicate but continue to be read many times in subsequent computation. Since in CB the duplicates are

Avg. Error Recovery [%]

CE + parity AG + parity ecc CE + ecc AG + ecc created only at writes, all such accesses will be counted as "unreliable reads." Since CB allocates copy registers on write only, during the periods with high register pressure, most copies are overwritten and they are reallocated a copy register when the pressure reduces. The second drawback is that, when it is creating a new duplicate in a register that holds another one, the selection of this victim register is done in some predetermined order.

CONSERVATIVE-ENHANCED (CE)

This scheme tries to eliminate the drawbacks of the CB by initiating copy operations whenever a register becomes available. In addition, CE tries to alleviate the second shortcoming of CB by being more careful in selecting the copy registers. More specifically, for each physical register, CE keeps track of the last time the register has been accessed. Then, if a copy has to be overwritten, the copy belonging to the "oldest" physical register is selected. The oldest in this context is the physical register that has not been accessed for the longest duration at the time of the decision. CE also uses a similar approach to decide on the physical register to be copied in the case of copy generation due to copy-on-free (i.e. the copy operation performed when a register becomes available).

To capture the age of a physical register, we use a 7-bit global counter that is incremented at every 1000 cycles. When a register is accessed, the value of the global counter is stored in the corresponding register access time field in the RRC. When a decision is made, this value is used to select the copy register to be overwritten or the physical register to be copied. If the counter rolls over (which will happen at every 128,000 cycles), we check the most significant bits of the counter values of the physical registers. The physical registers with the MSB value being zero (i.e., the registers that have not been accessed for more than 64,000 cycles) are marked using an additional "too-old" bit in the RRC. When a copy register needs to be overwritten and there is a physical register with a copy that has the too-old bit set, its copy is overwritten. The duplication success rate and reliable read rate for this scheme are given in Figures 4(a) and 4(b), respectively. One can observe from these results that CE in general generates better results than CB. Specifically, CE achieves a 78% reliable read rate, and 65% of the copies overwrite other copies. Intuitively, a register that has not been accessed for more than 10,000 cycles has less chance of being accessed again soon compared to a register that has been accessed in last 10 cycles. In Section 4.2, we study these probabilities, and present empirical data that this intuition is indeed correct. Therefore, by having copies for registers that are recently accessed, CE increases the reliable read rates.

AGGRESSIVE STRATEGY (AG)

The partial success of CE is a strong motivation to look for more aggressive schemes. Particularly, an aggressive scheme can address the failures incurred by the lack of a duplicate. We started to search for such a strategy by collecting further statistics on register usage.

Figure 5 shows the fraction of active physical registers accessed after going into the AR state. Note that small values are highlighted in the lower portion of the graph. We see from these results that, on the average, only 18% of the registers are re-accessed after going into the AR state. This ratio drops to 10.8%, 4.4%, 0.4%, and 0.06% after 10, 100, 1,000, and 10,000 cycles after going into the AR state, respectively. In other words, if we wait long enough, it is likely that contents of a given physical register are dead, and thus can be used for holding the duplicate of an active register. Architecturally, AG is not significantly different from CE. The RRC is enhanced to implement the eviction decision. This will be explained further in the following discussion. In addition, the physical register states are also changed. Instead of five states, the AG scheme uses two additional states: victim-copy and victimavailable. Victim-copy indicates that the RRC has evicted this physical register and uses it as a copy register. Victim-available, on the other hand, indicates that the physical register is evicted, but it is not used at the moment. Victim registers are never mapped to logical registers. If we had mapped it to other logical registers, we would have needed a complicated rollback mechanism to change the mapping. Once a register is selected as a victim register, the RRC introduces a dummy store operation into the pipeline. We assume that predetermined portions of the address space are allocated for copying the registers. The RRC then checks for source registers addressed to this physical register. If such an instruction is fetched, the RRC introduces a dummy load operation in front of this instruction to read the value back to the register file. Since the original register can only be used as a copy register, this load is guaranteed to not change any logical register mappings. If, instead, the logical register is overwritten, the register will be placed into the NU (if it is victim-available) or Copy (if it is victim-copy) states. AG is conservative in the register evictions. If the number of available registers goes above 10% of the available physical registers, the evicted registers are read back to the register file. It should be emphasized that even a misprediction in our context does not cause a correctness problem, as we always write the contents of the register to the memory before it is modified. However, a high misprediction rate can cause an increase in the original execution cycles. Therefore, the threshold value after which the contents of a register are pronounced dead should be kept large enough. In our experiments, we mark the registers that are not accessed for more than 10,000 cycles as dead. This results in increased reliability with minimal performance impact. Due to limited space, we do not present the results for the duplication success rate and reliable read rate for the AG. In summary, the reliable read rate for the aggressive scheme is 84% on the average. The duplication success rates are reduced compared to CE. This is an expected result as, with the evicted registers, the RRC has more registers that can be used for copying, thereby reducing the number of copy overwrites.

ERROR RESILIENCE RESULTS

Note that, all the results presented so far were for simulations without injecting any errors. While these results clearly showed that our strategies are successful in providing reliable reads, it is also important to evaluate their behavior under errors. To do this, we inject transient errors into the register file using the method explained in Section 3.1. The graph in Figure 6 presents the error resilience results for AG when used with parity (AG + parity) and with ECC (AG + ecc). We also present the results for CE + parity, CE + ecc, and pure ECC schemes. Note that, for the aggressive scheme, we assumed that the memory is reliable, i.e., if the register does not contain any errors while it is written to the memory, it will still have no errors when it is read back. The results indicate that the aggressive scheme performs better, in terms of error recovery, than CE. Particularly, AG + parity and AG + ecc can recover over 77.1% and 95.0% of the transient errors, respectively. We have also performed an analysis of the failed recoveries for AG + parity. We do not present the detailed results here; but, they revealed that most failures (37.1%) are due to lack of duplicates, and the multi-bit errors and the corrupted copies constitute 30.5% and 32.4% of the failures, respectively.

PERFORMANCE RESULTS

Unlike the conservative strategies, AG has a performance penalty that should be quantified as well for a fair comparison. Therefore, we measure the misprediction rate for AG. We define the misprediction rate as the number of times we pronounce a physical register as dead but the register is later accessed. The misprediction rates for integer and floating-point benchmarks are 0.22% and 0.19%, respectively, indicating that our prediction mechanism works very well with a threshold value of 10,000 cycles. To see the impact of this misprediction rate on the overall performance of our applications, we recorded execution cycles. The average performance degradation is around 0.09% across all applications.

ENERGY CONSUMPTION RESULTS

After having discussed the reliability and performance results in detail, we now focus on energy consumption of different schemes. Figure 7 gives the register file energy consumption for four schemes (CB in conjunction with parity, CE in conjunction with parity, AG in conjunction with parity, and the pure ECC scheme), as normalized values with respect to the pure parity-based scheme for an error-free execution (the energy results with errors injected are very similar since the number of errors is very small compared to the total number of register file accesses). To measure the energy consumed by the ECC scheme, we simulated the error detection/correction events. Then, we used published energy consumption values [START_REF] Phelan | Addressing Soft Errors in ARM Core-based SoC[END_REF] to find the energy impact of the techniques. On average, an ECC operation consumes 206% of the energy consumed for a register file access. Also, it should be emphasized that the energy consumption values given for CB and CE include all the energy overheads associated with these schemes. Specifically, we consider the register write operations due to copies, the energy overhead of the register file due to the additional copy port, increased size of the reservation table and the RRC for all the techniques; the global-counter and 8-bit counter stores for CE; the extra memory accesses, effects of selective replay, and increased number of instructions executed for the aggressive strategy. We see from these results that the conservative strategies are much more energy efficient than the pure ECC scheme. This is because the ECC scheme pays an energy price (over the pure parity-based protection) at each register access (i.e., whether we have error or not). On average, CB, CE, AG, and ECC increase the energy consumption by 11.1%, 15.7%, 28.8%, and 195.6% respectively. It should also be emphasized that, while a 15.7% increase in the register file energy consumption (for CE) may seem significant at first glance, the register file energy itself typically constitutes a small fraction of the overall system energy. Therefore, one may expect the impact on the overall system energy consumption to be within tolerable limits. Overall, these results clearly indicate that, while a pure ECC-based protection mechanism might be a good candidate from the reliability angle, it is certainly not a good candidate when one considers power consumption. Note that, even if the ECC computation is done at the background (i.e., with no performance penalty) as has been assumed here, it is still not possible to hide its energy overhead.

DISCUSSION

In this paper, we have presented a scheme for increasing the robustness of register files to transient errors. The main idea was to duplicate the values of the activate registers in the registers that are not used. One could also come up with alternate techniques for duplicating the register values. One such scheme would be to replicate the register file and have a second "copy" register file where the writes to the main register file are snooped and performed on the copy register file. The main drawback with this approach would be doubling the register file size. Although the register file itself constitutes a small fraction of the overall chip area, it resides in a critical segment of the datapath, and increasing the area in this segment can have a negative impact on the overall performance of the processor. Note that, in comparison, our approach tunes the aggressiveness of protection based on the dynamic demands on the physical registers.

RELATED WORK

Designing for transient-error tolerance has traditionally been considered in the context of systems that operate in high-radiation environments or in outer space, where there is a heavy concentration of alpha-particles and atmospheric neutrons [START_REF] Turmon | Software-implemented fault detection for high-performance space applications[END_REF]. Research from IBM showed that computer systems are susceptible to transient faults induced by these particles [START_REF] Srinivasan | Modeling the Cosmic-Ray-Induced Soft-Error Rate in Integrated Circuits: An Overview[END_REF]. More recently, designing computer systems for resiliency [START_REF] Patel | A Processor-Level Framework for High-Performance and High-Dependability[END_REF] to transient faults has gained greater significance due to the combined effect of higher integration densities, lower voltages, and faster clock frequencies. Redundancy is a frequently used technique for providing fault tolerance. Spatial redundancy may involve a complete duplication of all hardware components as in the HP NonStop Himalaya machine [START_REF] Albonesi | Selective cache ways[END_REF]. The IBM POWER4 [START_REF] Bossen | POWER4 System Design for High Reliability[END_REF] provides an extensive hierarchy of checkers distributed in all the major sections of the processor. Temporal redundancy has been proposed for both superscalar and SMT paradigms [START_REF] Rashid | Fault tolerance through reexecution in multiscalar architecture[END_REF][START_REF] Ray | Dual Use of Superscalar Datapath for Transient-Fault Detection and Recovery[END_REF][START_REF] Sato | Tolerating Transient Faults through an Instruction Reissue Mechanism[END_REF]. The DIVA architecture takes a slightly different approach wherein a special checker-processor is used at the commit stage of the main core's pipeline to verify the correctness of the instructions being committed [START_REF] Austin | DIVA: A Reliable Substrate for Deep Submicron Microarchitecture Design[END_REF].

Figure 1 .

 1 Figure1. Fraction of active physical registers over the simulation time for the 253.perlbmk and 172.mgrid applications. See Table1for processor configuration. Superscalar processors have been traditionally used to increase the performance in general-purpose architectures. Due to their complexity, their usage in embedded systems was limited. However, recently we are seeing increasingly more superscalar designs for embedded systems, e.g., STMicroelectronics[START_REF]STPC Microcontrollers -Overview[END_REF], ARM[START_REF] Eetimes | Two call on superscalar CPUs for handset apps[END_REF], Renesans and Hitachi[START_REF]Renesas and Hitachi announce development of 32-Bit RISC CPU Core for Embedded Systems[END_REF]. Our scheme targets such superscalar machines. In search for an error correction scheme that incurs small power and performance penalties, we studied the register usage of the Spec2000 benchmarks. Figure1plots the fraction of the physical registers that are allocated (i.e., that are mapped to a logical register or hold valid data) during the execution for 253.perlbmk and 172.mgrid benchmarks (the details of our experimental setup and simulation parameters will be given later). One can see from these plots that, while the register usage behavior changes during the course of execution, a significant fraction of the physical registers (in particular for the 172.mgrid) are not used. Based on this observation, this paper proposes to use unused physical registers as duplicates for the actively used ones. Specifically, we investigate two different strategies: conservative and aggressive. In the conservative strategy, we limit ourselves with the given register usage behavior of the application being executed. That is, we duplicate active registers in the unused ones without

Figure 2 .

 2 Figure 2. Register renaming for CB. The straddled area indicates the additional hardware required. The addition to RS is used to store the name of the copy register for the destination register. The RRC stores information about the copies as well.Irrespective of the error detection mechanisms, we can use two metrics that can demonstrate how our duplication-based schemes are performing in practice. The first of these is called the duplication success rate, which is defined as the fraction of successful duplication attempts. The second metric is the reliable read rate, which gives us the fraction of time we read a register for which a duplicate exists. Of these, the reliable read rate is more important since we ultimately want to maximize the number of times where the accessed physical register has its duplicate. Figure3presents the results for both statistics. Figure3(a)gives the duplication success rate for CB (due to lack of space, we only present the results for two applications and averages). We find that the duplication success rate is around 85% for the integer benchmarks and 88% for the floatingpoint benchmarks. These values are reasonable since the only time a duplication attempt can fail is when all the physical registers are active, which happens rarely in a typical execution. We also see that majority of the duplicates are made to empty physical registers. This is mainly because in this scheme when a duplicate is overwritten (by another duplicate or a primary copy), it is not restored. When we look at the reliable read rates given in Figure3(b) (marked as has copy), we find that on the average 71% of the reads are made to the registers with duplicates. This result tells us that 71% of the time we can correct odd number of bit errors if the duplicate is clean (assuming that the registers are protected using parity). CB has two main drawbacks. First, in many cases, it might happen that a register can lose its duplicate but continue to be read many times in subsequent computation. Since in CB the duplicates are

Figure 3 .

 3 Figure 3. Success of the CB scheme: (a) The fraction of duplication failure (dup. fail), duplication over another copy (dup. copy), and duplication over an available register (dup. available), (b) The fraction of accesses to registers having a copy and the ones without a copy.

Figure 4 .

 4 Figure 4. Success of the CE scheme. The labels are the same as in Figure 3.

Figure 5 .

 5 Figure[START_REF] Chen | Fault Containment in Cache Memories for TMR Redundant Processor Systems[END_REF]. Register re-usage: Fraction of registers accessed after being put into the AR state (reaccessed), fraction of registers accessed after 10 cycles (after 10), after 100 cycle (100), after 1000 cycles (1000), and after 10000 cycles (after 10000) of going into the AR state.

Figure 6 .

 6 Figure 6. Error recovery rates for Aggressive scheme. AG + parity is the aggressive scheme with pure-parity based error detection, AG + ecc is the aggressive technique along with the ECC error recovery/detection.

Figure 7 .

 7 Figure 7. Increase in energy consumption for different schemes. The energy numbers are relative to the consumption in the register file.

  If the instruction is cancelled (or squashed), the register is transitioned back to the NU state. Similarly, if the logical register is mapped to another register, the register is placed into the NU state after all the corresponding instructions complete. Register values can only be read if the physical register is in AV or AR states. There are usually three hardware structures to implement register renaming: The Mapping Table (MT) maps logical registers to physical registers; the Reservation Station (RS) keeps information about each fetched instruction; and the Register Renaming Circuit (RRC) stores the state of each physical register. The RRC can snoop the register file accesses to update the state values.

Table 1

 1

	Appl.	cycle
		[M]

. Simulated applications and important statistics: Number of execution cycles, total number of level 1 data cache accesses, number of register values read, number of register values written, the number of errors injected during the simulations, and the number of faults caused by these injected errors.

DL1 acc.[M] Reg. reads[M] Reg. writes[M] Error injected[K] Faults caused[K]

	168.wupwise	260.1	93.4	550.82	284.55	32.9	30.9
	171.swim	837.5	97.5	344.10	127.46	106.1	44.4
	172.mgrid	492.9 109.8	285.96	48.28	62.4	57.8
	173.applu	661.9 114.2	284.64	41.53	93.8	84.1
	177.mesa	147.8 109.8	339.7	192.92	18.7	9.1
	179.art	1845.7 102.8	309.8	125.65	233.7	92.4
	183.equake	1407.6 127.2	436.50	183.93	178.2	139.9
	188.ammp	762.8 116.2	501.86	195.35	96.6	40.6
	189.lucas	567.2	72.0	338.17	154.46	71.8	55.9
	301.apsi	308.6 111.8	571.27	230.48	39.1	33.3
	FP. Average	729.2 105.5	396.28	158.46	92.3	58.9
	164.gzip	200.8	71.8	480.1	309.7	25.4	17.4
	175.vpr	682.3 118.8	428.2	248.9	86.4	61.2
	176.gcc	376.0 126.7	459.7	270.5	47.6	19.6
	181.mcf	2151.6	20.3	260.4	185.3	272.5	75.7
	186.crafty	308.8 119.5	450.8	280.5	39.1	17.6
	197.parser	576.8	89.2	498.1	289.8	73.0	38.2
	253.perlbmk	261.5 108.3	419.3	240.4	33.1	14.5
	254.gap	230.4 115.1	459.4	297.9	29.2	14.5
	255.vortex	314.2 124.8	317.9	185.1	39.8	20.3
	300.twolf	802.7 100.1	518.2	300.5	101.6	66.3
	Int. Average	590.5	99.5	429.2	260.9	74.8	34.5
	Average	659.9 102.5	329.9	178.0	83.6	46.7

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

CONCLUDING REMARKS

This paper proposes and evaluates different strategies for increasing the resilience of register files to transient errors. These strategies are based on the observation that at a given time a significant fraction of the physical registers do not hold valid data, and can thus be used as placeholders for duplicates of the actively used registers. Our conservative schemes do not impact original performance of applications, and duplicate registers using only otherwise unused registers. We found that the most effective conservative scheme (CE) has around a 78% reliable read rate, and recovers from the 67% of the cases where a pure parity-based scheme fails. Our experiments with the aggressive strategy showed that it takes the error recovery rate to 77%, at the expense of slight (0.21%) degradation in the original performance. It is to be emphasized that errors occur rarely. Therefore, one of the most important issues is not to incur too much additional performance/energy overhead in the normal (error-free) case. Our conservative and aggressive strategies achieve this. Hence, we believe that the duplication-based recovery schemes are attractive solutions under these requirements.

* This work is supported in part by the NSF Career Award #0093082.


Reinhold Heckmann

Christian Ferdinand Absint

Verifying Safety-Critical Timing and Memory-Usage Properties of Embedded Software by Abstract Interpretation

Static program analysis by abstract interpretation is an efficient method to determine properties of embedded software. One example is value analysis, which determines the values stored in the processor registers. Its results are used as input to more advanced analyses, which ultimately yield information about the stack usage and the timing behavior of embedded software.

Abstract Interpretation

Failure of a safety-critical application on an embedded processor can lead to severe damage or even loss of life. Therefore, utmost carefulness and state-of-the-art machinery have to be applied to make sure that an application meets all requirements. To do so lies in the responsibility of the system designer(s).

Classical software validation methods like code review and testing with debugging are very expensive. Furthermore, they cannot really guarantee the absence of errors. In contrast, abstract interpretation [START_REF] Cousot | Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints[END_REF] is a formal verification method that yields statements valid for all program runs with all inputs, e.g., absence of violations of timing or space constraints, or absence of runtime errors.

Nowadays tools based on abstract interpretation are commercially available and have proved their usability in industrial practice. For example, stack overflow can be detected by AbsInt's StackAnalyzer, and violations of timing constraints are found by AbsInt's aiT tool [START_REF] Ferdinand | Reliable and precise WCET determination for a real-life processor[END_REF] that determines upper bounds for the worst-case execution times of the tasks of an application. Among other things, these tools perform a value analysis that tries to determine the values stored in the processor's memory for every program point.

Value analysis is a static analysis method based on abstract interpretation. It produces results valid for every program run and all inputs to the program. Therefore, it cannot always predict an exact value for a memory location, but determines abstract values instead that stand for sets of concrete values. There are several variants of value analysis depending on what kinds of abstract values are used. In constant propagation, an abstract value is either a single concrete value or the statement that no information about the value is known. In interval analysis, abstract values are intervals that are guaranteed to contain the exact values. Further extensions of value analysis record known equalities between otherwise unknown values, or more generally, upper and lower bounds for their differences, or even more generally, arbitrary linear constraints between values.

Value analysis, even in its simple form as interval analysis, has various applications as an auxiliary method providing input for other analysis tasks. Some of these applications are listed in the next few sections.

Stack usage analysis

A possible cause of catastrophic failure is stack overflow that usually leads to run-time errors that are difficult to diagnose. The problem is that the memory area for the stack usually must be reserved by the programmer. Underestimation of the maximum stack usage leads to stack overflow, while overestimation means wasting memory resources. Measuring the maximum stack usage with a debugger is no solution since one only obtains results for single program runs with fixed inputs. Even repeated measurements cannot guarantee that the maximum stack usage is ever observed.

AbsInt's StackAnalyzer provides a solution to this problem: By concentrating on the value of the stack pointer during value analysis, the tool can figure out how the stack increases and decreases along the various control-flow paths. The predicted worst-case stack usages of individual tasks in a system can be used in an automated overall stack usage analysis for all tasks running on one Electronic Control Unit, as described in [START_REF] Janz | Das OSEK Echtzeitbetriebssystem, Stackverwaltung und statische Stackbedarfsanalyse[END_REF] for systems managed by an OSEK/VDX real-time operating system.

Worst-case execution time prediction

Many tasks in safety-critical embedded systems have hard real-time characteristics. Failure to meet deadlines may be as harmful as producing wrong output or failure to work at all. Yet the determination of the Worst-Case Execution Time (WCET) of a task is a difficult problem because of the characteristics of modern software and hardware.

Embedded control software (e.g., in the automotive industries) tends to be large and complex. The software in a single electronic control unit is usually developed by several people, several groups or even several different providers. It is typically combined with third-party software such as realtime operating systems and/or communication libraries.

Caches and branch target buffers are used in virtually all performance-oriented processors to reduce the number of accesses to slow memory. Pipelines enable acceleration by overlapping the executions of different instructions. Consequently the timing of the instructions depends on the execution history.

The widely used classical methods of predicting execution times are not generally applicable. Software monitoring and dual-loop benchmark change the code, which in turn changes the cache behavior. Hardware simulation, emulation, or direct measurement with logic analyzers can only determine the execution time for some fixed inputs.

In contrast, abstract interpretation can be used to efficiently compute a safe approximation for all possible cache and pipeline states that can occur at a program point in any program run with any input. These results can be combined with ILP (Integer Linear Programming) techniques to safely predict the worst-case execution time and a corresponding worst-case execution path.

AbsInt's WCET tool aiT determines the WCET of a program task in several phases [START_REF] Ferdinand | Reliable and precise WCET determination for a real-life processor[END_REF]: CFG building decodes, i.e. identifies instructions, and reconstructs the control-flow graph (CFG) from a binary program; value analysis computes value ranges for registers and address ranges for instructions accessing memory; loop bound analysis determines upper bounds for the number of iterations of simple loops; cache analysis classifies memory references as cache misses or hits; pipeline analysis predicts the behavior of the program on the processor pipeline; path analysis determines a worst-case execution path of the program.

The results of value analysis are used to determine possible addresses of indirect memory accesses-important for cache analysis-and in loop bound analysis. They are usually so good that only a few indirect accesses cannot be determined exactly. Value analysis can also determine that certain conditions always evaluate to true or always evaluate to false. As a consequence, certain paths controlled by such conditions are never executed. Therefore, their execution time does not contribute to the overall WCET of the program, and need not be determined in the first place.

Cache Analysis uses the results of value analysis to predict the behavior of the (data) cache. The results of cache analysis are used within pipeline analysis allowing the prediction of pipeline stalls due to cache misses. The combined results of the cache and pipeline analyses are the basis for computing the execution times of program paths. Separating WCET determination into several phases makes it possible to use different methods tailored to the subtasks. Value analysis, cache analysis, and pipeline analysis are done by abstract interpretation [START_REF] Cousot | Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints[END_REF]. Integer linear programming is used for path analysis.

aiT allows to inspect the timing behavior of (timecritical parts of) program tasks. The analysis results are determined without the need to change the code and hold for all executions. aiT takes into account the combination of all the different hardware characteristics while still obtaining tight upper bounds for the WCET of a given program in reasonable time. Its results are documented in a report file and as annotations in the control-flow graph that can be visualized using AbsInt's graph viewer aiSee.

Conclusion

Tools based on abstract interpretation can perform static program analysis of embedded applications. Their results hold for all program runs with arbitrary inputs. Employing static analyzers is thus orthogonal to classical testing, which yields very precise results, but only for selected program runs with specific inputs. The usage of static analyzers enables one to develop complex systems on state-of-theart hardware, increases safety, and saves development time. Precise stack usage and timing predictions enable the most cost-efficient hardware to be chosen. As recent trends, e.g., in automotive industries (X-by-wire, time-triggered protocols) require knowledge on the WCETs of tasks, a tool like aiT is of high importance.

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


Jawad Khan

Ranga Vemuri

An Iterative Algorithm for Battery-Aware Task Scheduling on Portable Computing Platforms

HAL is

Introduction

Battery powered portable systems have finite amount of battery energy available and therefore battery lifetime maximization is one of the most important design goals for such systems. In this paper we present an iterative heuristic algorithm based on the battery discharge characteristics. Our goal is to meet a desired deadline and save as much battery energy as possible.

Target Hardware Architecture: The algorithm described in this work is applicable to any embedded platform, although the methods for changing the energy consumption of a task vary depending upon which processing element is used. In a processor based embedded system power-performance tradeoffs can be achieved by voltage and clock scaling. It is assumed that several discrete voltage and frequency combinations are available. If the embedded platform has an FPGA as the main processing element then it is assumed that several different hardware implementations are available which can be downloaded in the form of bitstreams. It is assumed that for each design-point, performance and total power cosumption estimates are available for any given portable platform, including the peripheral components such as memory and display power usage. Further, it is also assumed that intertask communication occurs via shared memory and the energy cost and latency of the memory transfers are a part of the execution time and energy costs of the task under consideration.

Application Specification: The application is described as a directed acyclic task graph (DAG) G(V,E). The vertices (nodes) of the graph are tasks which are to be executed on the portable platform and each task has several different implementation options available called design-points. Associated with each task i and its design-point j is its execution time and current consumption . The current consumption of a task is assumed to be measured as the average total current consumption of the portable platform which is the cumulative current consumption of all subsystems being used in the portable platform. The edges E describe data and control dependence between different tasks of the task graph. In the rest of the paper we will use , and there are m design points available for each task. There is a deadline d associated with the task graph before which all the tasks must be completed.

Problem Description: Given a DAG G(V,E), a set of design-points for each task, execution time, current usage estimate for each design-point and a desired deadline for the completion of the task graph, determine a valid schedule which does not violate the control and data dependencies of the tasks in the task graph and also find a mapping of each task to a suitable design-point such that the deadline for the entire taskgraph is met and the battery energy used is as small as possible. Our algorithm finds an initial sequence and then assigns design-points to the tasks. The suitability of the task sequence and the design-point selection is judged by using a battery model due to [START_REF] Rakhmatov | An analytical high-level battery model for use in energy management of portable electronic systems[END_REF] which will be discussed in Section 3. The chosen task sequence is modified using a heuristic approach and design-point selection is performed again to improve the quality of the solution. The algorithm is described in detail in Section 4. We tested the algorithm using different task-graphs and design-points and the results are discussed in Section 5.

Related Work

In processor based embedded computing platforms dynamic voltage and frequency scaling has been proven to be extremely effective for low power execution of tasks [START_REF] Panigrahi | Battery-Driven System Design: A New Frontier in Low Power Design[END_REF][5][6] [START_REF] Martin | Balancing Batteries, Power, Performance: System Issues in CPU Speed-Setting for Mobile Computing[END_REF]. In battery-powered embedded systems the energy source is non-linear therefore, the existing voltage scaling techniques are not directly applicable to these systems. Luo

v V ∈ E i j I i j n V = e E =

An Iterative Algorithm for Battery-Aware Task Scheduling on

Portable Computing Platforms* Jawad Khan and Ranga Vemuri ECECS Department, University of Cincinnati, Cincinnati, Ohio 45221-0030, USA {jkhan,ranga}@ececs.uc.edu and Jha studied static task scheduling for battery powered multiprocessor environments [START_REF] Luo | Battery-aware static scheduling for distributed real-time embedded systems[END_REF]. They used a battery model which was based on Peukert's law and an empirical model due to Pedram [START_REF] Pedram | Design considerations for battery-powered electronics[END_REF]. Rakhmatov et al developed an algorithm for battery-aware task scheduling using dynamic programming [START_REF] Rakhmatov | Energy management for battery-powered embedded systems[END_REF] along with its other variants. Chowdhury et al [START_REF] Chowdhury | Battery-aware task scheduling for a system-on-a-chip using voltage/clock scaling[END_REF] proposed a simplified heuristic which reduced the voltage level of the tasks as much as possible starting from the last task in the schedule. In contrast to these works, our work provides a way to simultaneously solve the task sequencing and design-point assignment in an iterative fashion. In any given iteration a valid schedule and assignment is available which can be used. If the user wishes then the solution quality is improved over subsequent iterations. Further, compared to our algorithm, it is not easy to implement a Simulated Annealing or Linear Program Forumulation based algorithms on an embedded computing platform which has inherent limitations on memory and battery capacity.

Battery Characteristics and Motivation

Rated Capacity of a battery is defined as the capacity of the battery (in mAh) under a nominal constant current discharge and is reported by the manufacturer. It is observed that higher rates of discharge tend to reduce the rated capacity significantly (rate capacity effect) and reducing discharge rates between heavy discharge periods allows the battery to regain some of its lost capacity (recovery effect) [START_REF] Linden | Handbook of Batteries[END_REF]. Rakhmatov et al. [START_REF] Rakhmatov | An analytical high-level battery model for use in energy management of portable electronic systems[END_REF] developed a variable load analytical model based on the laws of chemical kinetics, which takes into account both the rate capacity effect and the recovery effect. Equation 1 describes the battery model.

(1)

The value of gives the amount of charge lost by time T, which is the length of a current discharge profile having n distinct discharge intervals. I k is the current drawn from the battery in the k th discharge interval, where t k is the start time of the kth discharge interval and is the duration of this interval. The battery lifetime is estimated by evaluating Equation 1 for increasing values of T and stopping where : At this point the value to T is taken as the battery lifetime. Equation 1 is used as the battery-aware cost function to be minimized. We have chosen to use this battery model because of its high accuracy and low computational complexity. It was shown in [START_REF] Rakhmatov | Energy management for battery-powered embedded systems[END_REF] that for a set of n tasks if dependencies are ignored and the value of is assumed to be sufficiently large then sequencing tasks in the non increasing order of their currents is the best and sequencing the tasks in the non decreasing order of their currents is the worst. This property is also important for task-graphs where dependencies are present because it provides the lower and upper bounds on the value of cost function given in Equation 1. The authors in [START_REF] Chowdhury | Battery-aware task scheduling for a system-on-a-chip using voltage/clock scaling[END_REF] also proved that given a pair of two identical tasks in the profile and a delay slack to be utilized by down scaling, it is always better to use the slack on the later task than on earlier task. We use the above two properties along with the observation that tasks which have lower overall average energy consumption should be given priority for voltage down scaling.

Battery-Aware Task Sequencing and Design-Point Assignment

Some important definitions are presented below first: Execution Time matrix (D) is an (n x m) matrix where gives the execution time of task i using design-point j; for each task i the execution times of the design-points are stored in ascending order of magnitude.

Current matrix (I) is an (n x m) matrix where gives current of task i using design-point j; for each task i the currents of the design-points are stored in descending order of magnitude.

Design-Point Selection matrix (S) is an (n x m) matrix where is 1 if task i is assigned to design-point j. S is initialized such that ={1 if j = m, 0 otherwise}. Energy Vector E: is a row vector where each element specifies a task and the tasks are stored in increasing order of their average energies.

Slack Ratio (SR) of a design-point is defined as the ratio of the amount of slack left to the deadline, if that design-point is chosen for execution. If t is the execution time of a designpoint and d the deadline of the task graph then formally SR is defined as:

. Similarly, if SR is to be calculated for several design-points chosen, then t would be defined as the sum of the execution times of all the design-points chosen. SR gives an indication of how much slack is left which needs to be utilized. It is beneficial to use as much slack as possible. Therefore, a smaller value of SR is better.

Current Ratio (CR) of a design-point is defined as , where I is the average current used by the design-point and and are the maximum and minimum currents among all the design-points of all tasks. CR is normalized to be between 0 and 1. CR gives an indication of relative current of a particular design-point when compared to all the other design-points. A smaller value of CR is better.

Energy Ratio (ENR) of a task sequence is defined as , where E n is the total average energy used by the chosen design-points for all the tasks. Energy ratio is low if a set of design-points uses lower overall average energy. Its value is between 0 and 1. and are the current and the voltage of the designpoint c chosen for task i, respectively. and is its corresponding execution time. and are the energies of tasks sequences if all the lowest and highest power designpoints are used for all tasks, respectively.

Current Increase Fraction (CIF) of a task sequence is a measure of non-decreasing trends in the current discharge profile. The lower its value, the less number of increasing current transitions are there in the discharge profile. We define CIF as follows where c denotes the chosen design point for any task k:

σ I k ∆ k 2 e β - 2 m 2 T t k ∆ k -) - ( e β - 2 m 2 T t k ) - ( - β 2 m 2 ---------------------------------------------------------------------------- m 1 = 10 ∑ +         k 0 = n 1 - ∑ = σ ∆ k σ α ≅ α D i j , I i j , S i j , S i j , SR d t - ( ) d ( ) ⁄ = CR I I min - (
)

I max I min - ( ) ⁄ = I max I min ENR E n E min - ( ) E max E min - ( ) ⁄ = E n I i c , V i c , D i c , × × i 1 = n 1 - ∑ = I i c , V i c , D i c , E min E max E min I i min , D i min , × i 1 = n 1 - ∑ = E max I i max , D i max , × i 1 = n 1 - ∑ =

Design-Point Fraction (DPF):

If there are a total of m design points available for each task then DPF is the fraction of total design-points assigned to any single design-point k for all n tasks. DPF is a measure of the number of different designpoints being used in a particular assignment. Equation 2 and Equation 3 formally define DPF where k denotes the design point under consideration where x is the number of free nodes:

(2) (3)
As can be seen from the definition, the use of higher powered design-points is penalized the most. The penalization decreases as the lower powered design points are used and is zero for the lowest powered design-points.

Suitability of a Design-Point (B

) is a measure of how suitable a particular design-point is for achieving the minimum battery capacity usage goal and the suitability of a design-point is defined as

Algorithm Description

During each iteration of the algorithm a valid schedule is created and a design-point assignment is chosen. In subsequent iterations the solution is improved such that the amount of battery capacity used is less than the previous iteration. The algorithm terminates once the solution is not improved during two consecutive iterations. We start choosing design-points from the last task and work our way up to the first task. During the selection of the design-point for any particular task the suitability of the each design-point (B) is calculated. The designpoint which has the lowest value of B is chosen and the task is fixed to that design-point. Each task can be in three different states of design-point allocation: free, tagged and fixed. A task is tagged when we are evaluating the suitability of one of its design-points. When all of its design-points are evaluated and the best one is selected we set the state of the task to be fixed. Tasks which are neither tagged nor fixed are called free tasks. We use an heuristic approach for searching the design-space which involves the use of a window function (Explained later) until all design-points are considered. Once all tasks are assigned to design-points the battery capacity used is calculated and we sequence the tasks according to a weight assignment which is based on the current consumption of the designpoints assigned to different tasks in this iteration (Explained in Section 4.). This new sequence is then used for the next iteration.

BatteryAwareSQNDPAllocation is the top level algorithm for task sequencing and design-point assignment and is given in Figure 1. MinBCost contains the minimum battery cost for any given iteration and is initialized to infinity. PrevIterCost contains the cost of the previous iteration for comparison pur- S}=EvaluateWindows(L,E,I,D) poses and is also initialized to infinity. We use a modified list based scheduling algorithm for generating task sequences for a particular task graph. At the start of the algorithm each task is assigned a weight which is equal to the average energy of all design-points available for it. The tasks which have a larger weight are scheduled earlier than other tasks in the ready list, which is a list of all nodes which have all their predecessors scheduled. The scheduled list is called L(1..n) and is generated by the algorithm called SequenceDecEnergy(D,I). Each task is assigned a unique time-step and all the n tasks in this list are scheduled to be executed sequentially. The actual algorithm is omitted due relatively straight-forward nature. success is a flag which is set whenever there is a better solution found in the present iteration. If the solution does not improve over two consecutive iterations the algorithm terminates with the best solution found.

CIF J k k 2 = n ∑ n 1 - ⁄ = where J k 1 if I k 1 c , - I k c , < 0 Otherwise       k 2…n = = DPF m k - ( ) f × F k × k 1 = m ∑ = f 1 m 1 - ( ) ⁄ = F k S i k , x ( ) ⁄ i 1 = x ∑ = k 1…m ∈ ∀ B SR CR ENR CIF DPF + + + + = {MinBCost,
Wflag = TRUE WindowStart = m-1 while (Wflag) if (d < C T (WindowStart)) then WindowStart = WindowStart -1 Wflag = TRUE if (WindowStart == 1)

Window Function:

In each iteration a window dictates how many design-points for each task are to be considered for allocation. For example, consider five tasks and four design points as shown in Figure 3. The three different windows basically mask out all the columns which are beyond the width of the window and only the design-points within the window are evaluated. EvaluateWindows(L,E,I,D) initially tries to find a valid start width (WindowStart) for the window. C T (k) is the execution time if all design-points belonging to column k are chosen. The algorithm checks whether it would be possible to meet the deadline by executing even the highest power designpoints or not: if d < C T (1) then the deadline cannot be met and the algorithm exits with an error. Otherwise the window width is incrementally increased until all m design-points are evaluated. The design-point allocation (S) which results in the least amount of battery cost (MinBCost) is then returned. .

Choosing Design Points:

In ChooseDesignPoints() we first initialize S and set the state of all nodes in E to be free. Recall that E is the Energy Vector. We will use E as a priority function while evaluating DPF. We start from the last task in the sequence and fix it to the lowest power design-point and move up towards the first task. Tsum keeps track of the sum of the execution times of the tasks fixed so far. Ttemp is used to keep track of the sum of execution time of the tagged tasks as well as the sum of the execution time of the fixed tasks. We evaluate the suitability B of each design point j of each task one by one. For any given task i the design-point k which has the minimum value of B is chosen and the task i is fixed to design point k and the value of Tsum is updated to reflect the chosen design-point for task i Calculation of DPF, CIF and ENR: The algorithms given in Figure 2 At any given point during the execution there will be some tasks in S which have been fixed, tagged and free. Similarly, each task in E(Etemp) has two states: fixed and free. A task is fixed in E if it is fixed or tagged in S and also when the highest powered design-point is chosen for it. If the deadline is not being met by choosing the lowest power consuming designpoints of all free tasks in E(Etemp), moving the first free task in E(Etemp) from lower to a higher power consuming designpoint decreases the execution time in the hope that the deadline will be met with the least increase in the overall energy consumption. For example, consider the tasks and their designpoints shown in Figure 4. Here tasks T5 and T4 have been fixed to DP4 and DP1, respectively. T3 is the tagged task and we are calculating the DPF of DP2. Figure 4-a shows the initial condition at the start of calculation of DPF. Notice tasks T1 and T2 are both initially assigned to DP4. Suppose, that it is found that this assignment does not meet the deadline. Now we wish to use a higher powered DP such that the deadline is met. We look at Energy vector E and find that tasks 3,4,5 are fixed. The first free task in E is T1. Therefore, it is assigned the next higher powered design-point, DP3 (Figure 4-b) . Suppose, that this assignment also, does not meet the deadline. The assignment of T1 is moved up to DP2 (Figure 4-c). Now, let us assume that the assignment meets the deadline. Therefore, no further (E,S,T,D,WindowStart,i,d

F 4 = 1/2, F 3 =0, F 2 =1/2, F 1 =0, therefore DPF = 1/3 for task T3, DP2.
This process is repeated until either the deadline is met or there are no more free tasks available in E(Etemp). If no free tasks are found in E(Etemp), the value of DPF is set to infinity to indicate that choosing the corresponding tagged designpoint would result in a deadline violation. Finally, if we are considering the last task we set DPF equal to the slack ratio so that more emphasis is given to decreasing the slack. Caculate-Factors() is called at the end to calculate the CIF and ENR based upon the design-point allocation decisions made in the calculation of DPF. CIF basically tries to capture the increasing current profile in any design-point assignment. ENR gives the overall energy consumption of the design-point assignment.

Calculation of the Weighted Sequence: The main subroutine called BatteryAwareSQNDPAllocation calls Find-WeightedSequence() after different windows are evaluated. We try to improve the sequence by assigning weights to each task v according to Equation 4where is the sub-graph rooted at the node v. A list based scheduling method similar to SequenceDecEnergy is used for this algorithm as well but with modified weights.

(4)

The battery cost is calculated using Equation 1 for the task sequence generated and the design-points selected. This is done using the function called CalculateBatteryCost(). If there is no improvement in the battery cost in two successive iterations, the algorithm terminates.

Illustrative Example

We demonstrate the working of the algorithm with the help of the task graph (G3) shown in Table 1, which has 15 tasks and five different design points. For G3 the task durations were proportional to the worst case execution of the tasks and were made inversely proportional to the scaling factor with respect to voltage of DP1 (V 1 ) and task currents for differnent designpoints were made directly proportional to the cube of the scaling factor with respect to V 1. The scaling factors used for the five design points with respect to V 1 were as follows: 1, 0.85, 0.68, 0.51, 0.33. This task graph corresponds to a class of task graphs called fork-join, such task graphs have been used in multiprocessor scheduling research to model the structure of commonly encountered paralel algorithms [START_REF] Kwok | Dynamic critical-path scheduling: An effective technique for allocating task graphs tomultiprocessors[END_REF]. The dependency constraints are listed under the column called "Parents". We let the deadline to be 230 minutes, and executed our algorithm on G3, also we assumed that the amount of battery capacity available was sufficiently large to accommodate the requirements of different tasks.

Despite the unually large values for the task durations used in this example the algorithm is equally applicable to any chosen time scale. Table 2 shows the task sequences generated for the four iterations of the algorithm along with the designpoints (DP) assigned for each sequence. A "w" after a sequence number indicates the weighted sequence calculated for the corresponding iteration. Table 3 gives the values of battery capacity used given in milli-Ampere-minutes along with the duration of the task sequence given in minutes, for each sequence and its weigthed counterpart for the four iterations of the algorithm execution. The column marked "Win 1:5" contains the results for the battery capacity and the execution time when the algorithm was allowed to consider all five design points for all tasks. The data for each subsequent window where the number of allowed design points for consideration were decreased by one is also given in Table 3. The column called "Min " contains the minimum value of battery capacity chosen from among the four different windows evaluated during an iteration. The last column gives the execution time corresponding to the window chosen which uses the minimum battery capacity.The battery capacity after the first iteration is 16353 mAmin which decreases after each subsequent iteration until iteration 3. For iteration 4 there is no improvement in the value of the battery capacity used and the algorithm terminates. Also notice that for each iteration a valid schedule is generated which satisfies the deadline.

G v v G ∈ ∀ w v ( ) I v v ∀ G v ∈ ∑ = β 0.273 = α ( )

Case Study

We present a real-world application of a robotic arm controller implemented on a voltage scalable processor as described in [START_REF] Mooney | Hardware/software co-design of runtime schedulers for real-time systems[END_REF] [START_REF] Rakhmatov | Energy management for battery-powered embedded systems[END_REF] to demonstrate the usefulness of this algorithm. The task-graph of this application (called G2) is shown in Figure 5 along with its various design-points. For G2 the task durations were proportional to the worst case execution of the tasks and were made inversely proportional to the scaling factor with respect to voltage of DP4 (V 4 ) and task currents for differnent design-points were made directly proportional to the cube of the scaling factor with respect to V 4. The scaling factors used for the four design points with respect to V 4 were as follows: 2.5, 1.66, 1.25, 1. The battery capacities used for three different deadlines (55, 75, 95 minutes) are shown in Table 4.

Comparison with an Approach in [1]:

We compared the results from our algorithm to a method in [START_REF] Rakhmatov | Energy management for battery-powered embedded systems[END_REF] where the design points were chosen using a dynamic program such that the total energy used is minimized and a given deadline is met. In the algorithm given in [START_REF] Rakhmatov | Energy management for battery-powered embedded systems[END_REF], after the design-point allocation a greedy sequencing of all tasks in the task graph G(V,E) was performed where the tasks were assigned a weight according to Equation 5, where : is the subgraph rooted at node v and is the mean current of all nodes in the subgraph rooted at node v. Whenever a node is to be scheduled the node with the largest weight was selected among the nodes in the ready list.

(5)

We executed the two algorithms for three different deadlines for the two different test task graphs G2 and G3 discussed earlier. We present the data for this comparison in Table 4. Notice that as the deadline increases the amount of battery capacity used decreases. This is because the algorithm can choose design points which have lower performance but also consume less capacity. Also, we see that our algorithm gives better results for the two task graphs under consideration .

Figure 1 .

 1 Figure 1. Algorithms for Battery-Aware Task Sequencing and Design-Point Allocation

  are used to calculate DPF, CIF and ENR. Initially CalculateDPF() is called from ChooseDesignPoints() Then it calls CaculateFactors() to calculate ENR and CIF. Copies of S and E are made as Stemp and Etemp.

  {CIF,ENR}=CaculateFactors(S,I,D)Ttemp = S * D // where * denotes element by element Itemp = S * I // multiplication of two matrices of same dimensions Time = Column by Column sum of matrix Ttemp // Time and Current are column vectors Current = Column by Column sum of matrix Itemp CIF = 0 for x = 2,..,n do if Current(x-1) < Current(x) then CIF = CIF + 1 end if end for CIF = CIF /( total number of tasks -1) E n = Current * Time Energy = sum of all rows of E n ENR = (Energy -Emin)/(Emax -Emin) return{CIF,ENR} {ENR,CIF,DPF} = CalculateDPF

) 4 Figure 3 .

 43 Figure 2. Algorithms for various factor calculations

  Figure 4. DPF Calculation

  ,T5,T7,T3,T2,T6,T8,T10,T9,T13,T12,T11,T14,T15 DP P5,P5,P5,P4,P4,P4,P4,P4,P4,P4,P4,P4,P4,P4,P5, S1w T1,T3,T2,T4,T5,T6,T7,T8,T10,T9,T13,T12,T11,T14,T15 2 S2 T1,T3,T2,T4,T5,T6,T7,T8,T10,T9,T13,T12,T11,T14,T15 DP P5,P1,P2,P5,P5,P5,P5,P5,P5,P5,P5,P5,P5,P5,P5 S2w T1,T3,T2,T4,T5,T6,T7,T8,T9,T10,T13,T11,T12,T14,T15 3 S3 T1,T3,T2,T4,T5,T6,T7,T8,T9,T10,T13,T11,T12,T14,T15 DP P5,P5,P1,P5,P5,P5,P4,P5,P4,,P5,P5,P5,P5,P5,P5 S3w T1,T2,T4,T5,T7,T3,T6,T8,T9,T10,T13,T11,T12,T14,T15 4 S4 T1,T2,T4,T5,T7,T3,T6,T8,T9,T10,T13,T11,T12,T14,T15 DP P5,P1,P5,P5,P4,P5,P5,P5,P4,,P5,P5,P5,P5,P5,P5 S4w T1,T2,T4,T5,T7,T3,T6,T8,T9,T10,T13,T11,T12,T14,T15 σ ∆ σ

Table 1 . Data for example task graph G3

 1

	Tasks	Design Point 1	Design Point 2	Design Point 3	Design Point 4	Design Point 5	Parents
		I	D	I	D	I	D	I	D	I	D
		mA	min	mA	min	mA	min	mA	min	mA	min
	T1 917 7.3 563 11.2 288 15.0 122 18.7 33 22.0	-
	T2 519 11.2 319 17.3 163 23.1 69 28.9 19 34.0	T1
	T3 611 5.9 375 9.2 192 12.2 81 15.3 22 18.0	T1
	T4 938 5.3 576 8.2 295 10.9 124 13.6 34 16.0	T1
	T5 781 4.0 480 6.1 246 8.2 104 10.2 28 12.0	T1
	T6 800 4.6 491 7.1 252 9.5 106 11.9 29 14.0	T2,T3
	T7 720 7.3 442 11.2 226 15.0 96 18.7 26 22.0	T4,T5
	T8 600 5.3 368 8.2 189 10.9 80 13.6 22 16.0	T6,T7
	T9 650 4.6 399 7.1 204 9.5 86 11.9 23 14.0	T8
	T10 710 5.9 436 9.2 223 12.2 94 15.3 26 18.0	T8
	T11 500 6.6 307 10.2 157 13.6 66 17.0 18 20.0	T9
	T12 510 4.6 313 7.1 160 9.5 68 11.9 18 14.0	T10
	T13 700 4.0 430 6.1 220 8.2 93 10.2 25 12.0	T9
	T14 400 5.3 246 8.2 126 10.9 53 13.6 14 16.0 T11,T12T13
	T15 380 3.3 233 5.1 119 6.8 50 8.5 14 10.0	T14

Table 2 . : Task Sequences of G3 for different iterations Iter Seq No Task Sequences

 2

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)

* This work was sponsored in part by the Ohio Board of Regents PhD

Enhancement Program


Takeshi Kitahara
email: kitahara@dad.eec.toshiba.co.jp

Naoyuki Kawabe

Fimihiro Minami

Katsuhiro Seta

Toshiyuki Furusawa

Area-efficient Selective Multi-Threshold CMOS Design Methodology for Standby Leakage Power Reduction

This paper presents a design flow for an improved selective multi-threshold(Selective-MT) circuit. The Selective-MT circuit is improved so that plural MT-cells can share one switch transistor. We propose the design methodology from RTL(Register Transfer Level) to final layout with optimizing switch transistor structure.

Introduction

The market for portable electric appliances has grown rapidly, generating great interest in low-power design. Not only dynamic power dissipation, but also standby leakage power has become a critical issue. The Dual-Vth(threshold voltage) technique [START_REF] Wei | Power Minimization by Simultaneous Dual-Vth Assignment and Gate-sizing[END_REF] is an effective method to reduce the leakage power; however, low-Vth cells on critical paths still dissipate large leakage power, and this is limitation of the Dual-Vth technique.

For this reason, we developed the Selective-MT technique [START_REF] Usami | Automated Selective Multi-Threshold Design For Ultra-Low Standby Applications[END_REF][START_REF] Uvieghara | A Highly-Integrated 3G CDMA2000 1X Cellular Baseband Chip With GSM/AMPS/GPS/Bluetooth/ Multimedia Capabilities And ZIF RF Support[END_REF]. The technique uses the MT-cell [START_REF] Usami | Automated Selective Multi-Threshold Design For Ultra-Low Standby Applications[END_REF][START_REF] Uvieghara | A Highly-Integrated 3G CDMA2000 1X Cellular Baseband Chip With GSM/AMPS/GPS/Bluetooth/ Multimedia Capabilities And ZIF RF Support[END_REF], instead of the low-Vth cell. The MT-cell is less leaky than the low-Vth cell on standby. Selective-MT technique can save the leakage power more than the Dual-Vth technique can. One drawback of the conventional Selective-MT technique is the area overhead. The technique uses the MT-cell, and they are larger than the low-Vth cell. We have improved the technique to overcome the drawback, so that plural MT-cells can share one switch transistor. The critical path delay changes according to the switch cell structure, so novel P&R methodology is required to design the improved Selective-MT circuit.

Selective-MT Technique

The conventional Selective-MT technique uses the MT-cell. Basic structure of the MT-cell is shown in Fig. 1(a). The logic part of the MT-cell consists of low-Vth transistors, and a high-Vth switch transistor controlled by the signal MTE is inserted. This switch transistor makes the MT-cell faster than the high-Vth cell and less leaky than the low-Vth cell. Fig. 2 shows an example of the conventional Selective-MT circuit. MT-cells are used on critical paths, and high-Vth cells used on non-critical paths.

Fig.3: Improved Selective-MT circuit

To reduce the area overhead by MT-cells, we have separated the switch transistor from the MT-cell. Basic structure of an improved MT-cell is shown in Fig. 1(b). The VGND(virtual ground) port is added to the MT-cell instead of the switch transistor, and the VGND port of the MT-cell is connected to the drain of the switch transistor. Not only the switch transistor, but also the output-hold circuit(output holder) [START_REF] Usami | Automated Selective Multi-Threshold Design For Ultra-Low Standby Applications[END_REF] has been separated. The output holder sets the output of the improved MT-cell to one when a circuit is on standby, and it prevents a circuit from dissipating unex-pected power. Fig. 3 shows an example of the improved Selective-MT circuit. The circuits in Fig. 2 and Fig. 3 are equivalent.

Design Methodology for Selective-MT

Fig. 4 shows the design flow to generate the improved Selective-MT circuit. First, the RTL description is synthesized to generate an initial netlist and initial placement. Only low-Vth cells are used at this stage. As the low-Vth cell is faster, the timing constraint can be satisfied. Then, the circuit with low-Vth cells is replaced by high-Vth cells and MT-cells(without VGND ports) with the timing specification satisfied. The MT-cell(without VGND port) has the same information as the one(with VGND port), except that there is no definition related to the VGND port. The switch transistor does not appear at this stage, so the information related to the VGND port is unnecessary. MT-cells are assigned to gates on critical paths, and high-Vth cells on non-critical paths, as shown in Fig. 3. This replacement is executed by the method which is similar to the way of generating the Dual-Vth circuit.

Fig.4: Selective-MT design flow

After a circuit with high-Vth cells and MT-cells(without VGND ports) is generated, a switch transistor and output holders are inserted. All MT-cells(without VGND ports) are replaced by the ones(with VGND ports) at this stage. One switch transistor is added, and all VGND ports at the MT-cells are connected to the drain of the switch transistor for generating an initial switch transistor structure. The output holder is inserted to the nets where it is required to prevent the signal floating. The output holder is not necessary for all MT-cells, as shown in Fig. 3. When all fanouts of the MT-cell are connected to MT-cells, an output holder is unnecessary.

Next, the switch transistor structure is constructed. This task is executed by the back-end optimizer CoolPower TM [4]. The tool generates clusters of MT-cells, and all VGND ports of MT-cells in one cluster are connected to the same switch transistor. It also decides the size of each switch transistor, so that the voltage bounce of each VGND line may not exceed the upper limit which the designer specifies. The switch transistor structure is constructed so that the wire length of each VGND line may not exceed an upper limit, as a long VGND line tends to suffer from the crosstalk. The number of MT-cell which shares the same switch transistor is also cared to prevent the electro-migration.

Then, routing including CTS(Clock Tree Synthesis) is executed. The MT enable signal MTE shown in Fig. 3 has many fanouts, as MTE is necessary to be connected to all switch transistors and output holders. So, buffers needs to be inserted to the MTE net appropriately. When constructing the switch transistor structure before routing is done, the information about the resistance and the capacitance of each wire is estimated based on the placement information. So, there is an error when compared with the precise RC information which is generated after routing is done. After it is extracted, the re-optimization of the switch transistor structure is executed by CoolPower TM again. The size of each switch transistor is adjusted, so as that the voltage bounce of each VGND line may not exceed the upper limit. Finally, ECO(Engineering Change Order) and timing analysis(e.g. STA or simulation) are performed for fixing the hold violation and for verification of the Selective-MT circuit. , and it shows that the standby leakage power could be reduced by 40% and the total area could be also reduced by 20%, compared with the conventional Selective-MT circuit.

Fig. 1 :

 1 Fig.1: Basic Structure of 2-input NAND MT-cell

RTL-

  Replacing Low-Vth cells by High-Vth cells & MT-cells(without VGND ports) with timing optimization -Replacing MT-cells(without VGND ports) by MT-cells(with VGND ports) -Inserting a switch transistor and output holders Constructing the switch transistor structure so that the voltage of each VGND line is smaller than the upper limit -Routing (including CTS) -Buffering the MT enable signal Optimizing the switch transistor structure based on post-route information(-Vth cells by High-Vth cells & MT-cells(without VGND ports) with timing optimization -Replacing MT-cells(without VGND ports) by MT-cells(with VGND ports) -Inserting a switch transistor and output holders Constructing the switch transistor structure so that the voltage of each VGND line is smaller than the upper limit -Routing (including CTS) -Buffering the MT enable signal Optimizing the switch transistor structure based on post-route information(

Table . 1: Comparison of three techniques

 . Table.1 expresses our experimental results

			Vth Con.-SMT Imp.-SMT
	A	Area Leakage	100.00% 164.84% 133.18% 100.00% 14.58% 9.42%
	B	Area Leakage	100.00% 142.22% 115.65% 100.00% 19.42% 12.21%

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