Sandeep Kumar Goel
email: sandeepkumar.goel@philips.com

Erik Jan Marinissen
email: erik.jan.marinissen¡@philips.com

On-Chip Test Infrastructure Design for Optimal Multi-Site Testing of System Chips

Multi-site testing is a popular and effective way to increase test throughput and reduce test costs. We present a test throughput model, in which we focus on wafer testing, and consider parameters like test time, index time, abort-on-fail, and contact yield. Conventional multi-site testing requires sufficient ATE resources, such as ATE channels, to allow to test multiple SOCs in parallel. In this paper, we design and optimize on-chip DfT, in order to maximize the test throughput for a given SOC and ATE. The onchip DfT consists of an E-RPCT wrapper, and, for modular SOCs, module wrappers and TAMs. We present experimental results for a Philips SOC and several ITC'02 SOC Test Benchmarks.

Introduction

The manufacturing test costs of subsequent generations of SOCs threaten to increase beyond what is acceptable, if no proper countermeasures are taken. Factors that drive the (digital) test costs up are the increases in pin count, test data volume, speed and corresponding required ATE accuracy. Especially the test data volume has risen dramatically, due to a combination of growth in transistor count and new advanced test methods (such as delay-fault testing) which add significantly to the test set size. As a consequence, testing of 'monster chips' [START_REF] Kumar Goel | Test Infrastructure Design for the Nexperia ¡ Home Platform PNX8550 System Chip[END_REF] requires expensive ATEs with a large channel count and deep test vector memory [START_REF] Marinissen | On the Role of DfT in IC-ATE Matching[END_REF]. Several methods are applied to reduce the test costs. With Built-In Self Test (BIST), SOCs test (parts of) themselves and hence eliminate the need for ATE altogether. However, BIST is expensive to implement on-chip, and hence its usage is typically limited to applications which require in-field testing. Test Data Compression (TDC) techniques still require the presence of an ATE, but reduce the demands on both vector memory and test application time by exploiting the many don't care bits in the test set to compress it. Another effective approach to reduce test cost, orthogonal to TDC, is multi-site testing, in which multiple instances of the same SOC are tested in parallel on a single ATE [START_REF] Andrew | Applications of Semiconductor Test Economics, and Multisite Testing to Lower Cost of Test[END_REF][START_REF] Khoche | A New Methodology for Improved Tester Utilization[END_REF][START_REF] Volkerink | Tackling Test Trade-offs from Design, Manufacturing to Market using Economic Modeling[END_REF][START_REF] Volkerink | Test Economics for Multi-site Test with Modern Cost Reduction Techniques[END_REF][START_REF] Iyengar | Test Resource Optimization for Multi-Site Testing of SOCs Under ATE Memory Depth Constraints[END_REF]. More sites mean more devices are tested in parallel. Multi-site testing amortizes the fixed ATE costs over multiple SOCs.

Efficient multi-site testing requires effective management of test resources as the number and depth of ATE channels and the onchip DfT, while taking into account parameters such as prober index time, contact yield, etc. One way to allow an increase in the number of sites is to increase the number of ATE channels. However, this solution not only brings substantial extra costs, but also is not very scalable for SOCs with high pin counts. The other way to increase the number of sites is to narrow down the SOC-ATE interface, i.e., the number of SOC terminals that needs to be contacted during testing. Reduced-Pin-Count-Test (RPCT) [START_REF] Basset | Low-Cost Testing of High-Density Logic Components[END_REF][START_REF] Vranken | Enhanced Reduced Pin-Count Test for Full Scan Design[END_REF][START_REF] Khoche | A New Methodology for Improved Tester Utilization[END_REF] is a well-known DfT technique that does exactly this. This paper focuses on designing and optimizing an on-chip test infrastructure (DfT) to facilitate high-throughput multi-site wafer testing of large SOCs. We assume a given and fixed target test cell, including ATE and probe station. We present a two-step algorithm that designs the SOC test infrastructure such that the SOC test data volume fits on the target ATE within a single load and the multisite test throughput is maximum. The number of sites at which the throughput is maximum, we refer to as 'optimal multi-site'. This is a different optimization criterion from simply maximizing the number of multi-sites; a large number of sites means less ATE channels per SOC, which in turn increases the test application time per SOC. Consequently, in order to minimize test costs through multi-site testing, the number of sites should be tuned such that the test throughput is maximized. In case the SOC uses a flattened top-level test, the algorithm determines all parameters to design an Enhanced-RPCT wrapper [START_REF] Vranken | Enhanced Reduced Pin-Count Test for Full Scan Design[END_REF]. In case the given SOC uses a modular, core-based test approach [START_REF] Zorian | Testing Embedded-Core Based System Chips[END_REF], in addition to the E-RPCT wrapper, the algorithm determines the on-chip test architecture consisting of TAMs and core wrappers [START_REF] Iyengar | Co-Optimization of Test Wrapper and Test Access Architecture for Embedded Cores[END_REF][START_REF] Sandeep | SOC Test Architecture Design for Efficient Utilization of Test Bandwidth[END_REF]. The outline of this paper is as follows. Section 2 reviews the prior work in this domain. Section 3 describes our assumptions regarding multi-site testing. Section 4 details our cost model for test time and test throughput. Section 5 formally defines the problem of designing on-chip test infrastructures for optimal multi-site testing of SOCs, while Section 6 describes our two-step algorithm to solve it. Section 7 contains experimental results for the Philips SOC PNX8550 [START_REF] Kumar Goel | Test Infrastructure Design for the Nexperia ¡ Home Platform PNX8550 System Chip[END_REF] and several SOCs taken from the ITC'02 SOC Test Benchmarks [START_REF] Jan Marinissen | A Set of Benchmarks for Modular Testing of SOCs[END_REF]. Finally, Section 8 concludes the paper.

Prior Work

Reduced-Pin-Count Testing (RPCT) is a DfT technique used to reduce the number of IC pins that need to be contacted by the ATE. RPCT assumes the presence of internal-and boundary-scan. The basic principle of RPCT is that only the input and output terminals of the scan chains (including the boundary-scan chain), test control pins, and clock pins need to be connected to ATE channels. Access to all other functional pins is achieved via the boundaryscan chain. First use of RPCT with LSSD boundary-scan was re-ported by IBM to enable the use of low-cost ATE for ASICs [START_REF] Basset | Low-Cost Testing of High-Density Logic Components[END_REF]. Since then, several extensions have been made to the basic RPCT technique. Two such extensions are re-configurable RPCT [START_REF] Khoche | A New Methodology for Improved Tester Utilization[END_REF] and Enhanced RPCT [START_REF] Vranken | Enhanced Reduced Pin-Count Test for Full Scan Design[END_REF]. In [START_REF] Khoche | A New Methodology for Improved Tester Utilization[END_REF], a technique to design an RPCT wrapper around an SOC is presented. In this case, the DfT for the SOC can be designed without even knowing about the target ATE. Later, by using the re-configurable logic, the number of scan chains and their length can be modified in the RPCT wrapper according to the ATE specification. The basic idea behind E-RPCT [START_REF] Vranken | Enhanced Reduced Pin-Count Test for Full Scan Design[END_REF] is to provide access not only to the functional terminals, but also to the internal scan chains via the boundary-scan architecture, in order to enable even further scalability of the SOC-ATE interface. The E-RPCT wrapper around an IC truly converts external test inputs and outputs into ¡ internal test inputs and outputs, for all integers ¢ ¡ with ¥ ¦ ¦ ¡ . Our paper is based on the usage of E-RPCT.

Many papers published in the domain of multi-site testing model the economics of multi-site testing for test cost reduction. In [START_REF] Andrew | Applications of Semiconductor Test Economics, and Multisite Testing to Lower Cost of Test[END_REF], a conceptual semiconductor test-economic model is used to analyze the interrelations between the parameters that make up the test cost per device, such as test time, index time, yield, utilization, ATE capital cost, etc. In [START_REF] Volkerink | Tackling Test Trade-offs from Design, Manufacturing to Market using Economic Modeling[END_REF][START_REF] Volkerink | Test Economics for Multi-site Test with Modern Cost Reduction Techniques[END_REF], similar but rather limited cost models are described. The only paper that presents techniques to design and optimize on-chip test hardware to enable multi-site testing is [START_REF] Iyengar | Test Resource Optimization for Multi-Site Testing of SOCs Under ATE Memory Depth Constraints[END_REF]. It presents a rectangle bin-packing based technique to design the test architecture (consisting of TAMs and core wrappers) for a core-based SOC with a target ATE, such that the test architecture requires a minimum number of ATE channels and the SOC test data volume fits on the given ATE. A minimum number of ATE channels per device enables the maximum multi-site testing possible for the given SOC. While this paper was the first one in this domain, it has several limitations. The paper only discusses the design of core wrappers and TAMs for modularly tested, core-based SOCs, and ignores the design of chip-level RPCT wrappers. It maximizes the number of sites that can be tested in parallel, while we show in our paper that this does not always yield maximum throughput. To maximize the number of sites, the paper assumes that a common set of input channels can be used to broadcast test stimuli to all sites, which is often not practical. And finally, [START_REF] Iyengar | Test Resource Optimization for Multi-Site Testing of SOCs Under ATE Memory Depth Constraints[END_REF] looks at the test time only, and does not take into account parameters like index time, contact yield and re-test rate, and abort-onfail.

Multi-Site Test Flow

Multi-site testing can be done at wafer test as well as at final ('packaged IC') test. In this paper, we assume the following twostep test flow.

1. During wafer test, the internal circuitry of the SOC die in question is tested. This is done through a narrow E-RPCT interface, in order to enable a large number of multi-sites, as well as to reduce the chances for contact test fails. The non-E-RPCT pins of the SOC are not contacted.

2. During final test, the IOs of the packaged SOC are tested. For this purpose, all pins of the SOC are contacted. Optionally, the SOC internal circuitry can be tested again, either through all pins, or through their E-RPCT subset. The number of multi-sites during final test is limited by the number of available ATE channels divided by the number of pins per SOC, as well as by the available device handler.

In this paper, we focus on maximizing the multi-site test throughput during wafer testing. The complete wafer is located near the ATE, and the E-RPCT bonding pads of the SOCs under test are physically probed. Today's high channel-count ATEs and corresponding high pin-count probe technologies enable massive multisite testing. Unfortunately, the circular shape of the wafer brings some losses in multi-site testing at the periphery of the wafer; these are ignored in the sequel of this paper.

Iyengar et al. [START_REF] Iyengar | Test Resource Optimization for Multi-Site Testing of SOCs Under ATE Memory Depth Constraints[END_REF] assumed that ATE stimuli are broadcasted to all multi-sites. However, stimuli broadcast is often impractical. Some ATEs simply do not support broadcasting; they assign a channel to a site, and, if that site fails, no more stimuli will be sent to the device under test. Furthermore, broadcasting can cause undesired side effects, such as a fault at the bonding pad of one site causing incorrect test results on other sites. Hence, our solution approach in this paper explicitly supports both the cases with and without stimuli broadcasting. Obviously, the optimal multi-site for the case without stimuli broadcast is significantly lower than for the case with stimuli broadcast.

Multi-Site Cost Model

The total time spent on a set of devices to be tested in parallel is the sum of the index time ¨© and the test application time ¨ , as depicted in Figure 1.

Index Test Set 1 Index Test Set 2 Index Test Set 3
... The index time ¨© is the time required to position the probe interface in order to make contact with the bonding pads of the SOC(s) under test. We assume the index time to be a constant, dependent on the type of probe station. A typical value is ¨© ¥ s.

t i t a

The test consists of a contact test and a manufacturing test. In the contact test, it is checked whether all terminals required for the subsequent manufacturing test are properly connected to the ATE. If one or more of these terminals are not properly connected, the SOC fails the contact test. The probability ! of a single terminal to pass the contact test, also referred to as the contact yield, needs to be high to be able to successfully test high pin-count SOCs. All terminals undergo their contact test simultaneously, and hence the contact test time

¨! is a constant. A typical value is ¨! $ ¥ ms.
During the manufacturing test, the SOC is checked for manufacturing faults. In this paper, we only consider digital tests, i.e., for logic and memories. The probability & of a single SOC to pass the manufacturing test is also referred to as the yield. The manufacturing test time ¨& depends on the width of the RPCT test interface, the test data volume, and how well the various SOC tests can be scheduled.

The total test time can now be written as

¨ ¨© ) ¨ ¨© ) ¨! ) ¨& (4.1)
In high-volume production testing, where faulty devices are often not analyzed, but simply discarded, it is possible to abort the test as soon as the first failing test vector is observed. This abort-on-fail strategy can significantly reduce the average test time per device, especially in the case of relatively low yields. As we will show in Section 7, multi-site testing reduces the effect of the abort-on-fail strategy on the average test time, as now tests can only be aborted if all sites have started failing, which is simply less likely to happen. For an SOC with pins involved in its test, the probability ¡ ! that at least one out of SOCs will pass the contact test is

¡ ! $ ¢ ¤ $ ¢ ! § © (4.2)
Similarly, the probability

¡ &
that at least one out of SOCs will pass the manufacturing test is

¡ & $ ¢ ¤ $ ¢ & © (4.3)
Based on the assumption that failing SOCs do not take any test time (¨& ¥ ), a theoretical lower bound on the total test application time for a set of devices can be written as

¨ ¨! ) ¡ ! ¡ & ¨& (4.4)
The choice for the obviously unrealistic assumption that ¨& ¥ for failing SOC is motivated by the fact that it allows us to make a strong conclusion about the reduced effectiveness of abort-on-fail in multi-site testing in Section 7.

Assuming a full utilization of the ATE, the total number of devices tested per hour ! for multi-site testing can be written as

! $ % ¥ ¥ ¨© ) ¨ (4.5)
In this equation, both ¨© and ¨ are in seconds. Furthermore, ¨ can be either the original test application time, or, when abort-on-fail is used, the reduced test application time of Equation 4.4.

In many companies, it is common practice to re-test those devices that failed only on their contact test. The premise of re-testing is that the chances are high that the failure was caused by a wrong probe contact, rather than that the SOC itself was faulty. If that is indeed the case, it would be a waste to discard basically good products. Excluding the unlikely event of multiple failing terminal contacts per SOC, ! SOCs with terminals each and a contact yield ! per terminal, will require

¤ $ ¢ ! © !
SOCs per hour to be re-tested. While the number of devices tested per hour ! remains unaffected, re-testing has an impact on the number of unique devices tested per hour 1 !

. Assuming at most one failing terminal contact per SOC, and assuming that devices are re-tested at most once, 1 ! can be written as

1 ! ¤ $ ¢ ¤ $ ¢ ! © © ! (4.6)

Problem Definitions

The problem of test infrastructure design for optimal multi-site testing (i.e., with maximal throughput) of modularly-tested (corebased) SOCs can be formally defined as follows.

Problem 1 [Optimal Multi-Site Testing for Core-Based SOCs] Given an SOC consisting of a set of modules 7 , and for each Module ¡ 8 7 the number of test patterns ¤ ¡ © , the number of functional input terminals B ¤ ¡ © , the number of functional output terminals D ¤ ¡ © , the number of functional bidirectional terminals

F ¤ ¡ ©
, the number of scan chains G ¤ ¡ © , and for each scan chain I , the length of the scan chain in flip flops P ¤ ¡ ¢ I ©

. Given a target ATE with R channels, each with vector memory depth S . Furthermore is given a target SOC probe station with index time ¨© . Determine the number of multi-sites , the number of ATE channels per site ( even), and a T U -to-V E-RPCT wrapper for the SOC and test architecture (i.e., determine the number of TAMs, the width of these TAMs, the assignment of modules to TAMs, and the core wrapper design per module [START_REF] Iyengar | Co-Optimization of Test Wrapper and Test Access Architecture for Embedded Cores[END_REF][START_REF] Sandeep | SOC Test Architecture Design for Efficient Utilization of Test Bandwidth[END_REF]), resulting in W test clock cycles per SOC, such that during multi-site testing 1.

`R , i.e., the number of required ATE channels does not exceed the number of available ATE channels; 2. W `S , i.e., the required ATE vector memory depth does not exceed the available depth;

3. the test throughput ! is maximum.

e DfT solutions to Problem 1 look like the architecture depicted in Figure 2(a). Problem 1 addresses the case of a modularly-tested (core-based) SOC. Problem 2, in which the same problem is solved for a flattened SOC, actually turns out to be a degenerate case of Problem 1. For a flattened SOC, we simply deal with one module, i.e., f 7 f $ . The module wrapper and E-RPCT wrapper coincide, and there are no TAMs. This case is depicted in Figure 2(b). ) and with stimuli broadcast ( § q

) § q `R
), (2) without abort-on-fail (¨ ¨! ) ¨& ) and with abort-on-fail (¨

¨! ) ¡ ! ¡ & ¨&
), and (3) without re-test (maximizing ! ) and with re-testing (maximizing

!

).

On-Chip Infrastructure Design

In this section, we present a two-step algorithm that solves Problems 1 and 2. In Step 1 of the algorithm, we determine the maximum multi-site t v x for the given SOC and ATE, and the corresponding test infrastructure. In Step 2, we use linear search to find the number of sites y ($ ` y ` t v x

) for which the test throughput is maximum and we modify the test infrastructure accordingly. Details of both steps are given below.

Step 1: While determining t v x , we use two optimization criteria, as illustrated in Figure 3(a). Criterion 1 is the minimization of the number of ATE channels utilized by one SOC, such that the test still fits into the vector memory depth S of the ATE. Criterion 2 is the minimization of the actual filling of the vector memory. Criterion 1 has priority, as it maximizes the number of sites, as shown in Figure 3 In this step, we first calculate the minimum number of ATE channels t ¢ ¤ ¡ © required for every module ¡ 8 7 such that module's test time does not exceed the ATE vector memory depth per channel S . To design the wrapper around a module for a given number of ATE channels, we use the COMBINE algorithm presented in [START_REF] Jan Marinissen | Wrapper Design for Embedded Core Test[END_REF].

If t ¢ ¤ ¡ © £ R
, for any ¡ 8 7

, then the SOC cannot be tested on the target ATE and the procedure is exited. Otherwise, modules are sorted in decreasing order of their t ¢ ¤ ¡ ©

. Now we start with the first module, assign it the

t ¢ ¤ ¡ ©
number of channels and form a channel group of width

t ¢ ¤ ¡ ©
. Iteratively, we move to the next module and check whether it can be assigned to an already existing channel group without exceeding its vector memory depth limit. If more than one such channel groups are found, then the module is assigned to the group that requires the smallest vector memory depth.

In case, the module cannot be assigned to any existing channel group, we consider two options: (1) create a new channel group, or (2) increase the width of an existing channel group such that the module can be assigned without exceeding the vector memory limit. We select the best of the two options, i.e., the option in which the total free memory available on all used channels is maximum. This minimizes the test application time for the SOC considering the same number of channels. In both options, we take into account that the total number of used channels does not exceed R . If the assignment of a module leads to the violation of this constraint, then the SOC cannot be tested on the ATE and the procedure is exited. The procedure is repeated until all modules are assigned.

The summed width of all channel groups determines the total num-ber of channels for the SOC. Similarly, the test application time for the SOC is equal to the maximum of the filled vector memory over all channel groups. The maximum multi-site possible t v x = ¥ ¦ § ¨i n the case without stimuli broadcast, and t v x = ¥ q ¦ § ¨¢ $ in the case with stimuli broadcast.

One iteration of

Step 1 is illustrated in Figure 4. Figure 4(a) shows a situation in which Cores © and have already been assigned to a TAM that requires $ ATE channels, while Core is assigned to another TAM that requires U ATE channels. In Figure 4(b), the algorithm tries to add Core to either one of the two already existing TAMs. Unfortunately, both alternatives exceed the vector memory depth limit S . Hence, the algorithm is forced to start using more ATE channels in order to add Core . In Figure 4(c), the three alternatives considered are depicted. Alternative (i) is to add a new channel group for Core , in this case with

$ t ¢ ¤ © ATE channels. Alternative (ii) extends TAM 1 from $ to $ )
$ channels, and is only valid if Core can now be added without exceeding the vector memory depth S . Similarly, Alternative (iii) extends TAM 2 from U to U ) $ channels. The alternative which yields the smallest vector memory filling is selected.

Step 2: In this step, we identify the number of sites y for which the throughput ! is maximum. We use linear search from t v x down to 1 to calculate the corresponding ! value. In every iteration, we try to redistribute the ATE channels freed up by giving up one site over the remaining sites. Only if £ U (for the case without stimuli broadcast) or

£ ) $
(for the case with stimuli broadcast), redistribution makes sense. In so, for each site, we assign iteratively free channels to the channel group that is maximally filled. This can reduce the test application time per site. We record the throughput for the value of . Finally, after the linear search, we find y as the number of sites for which the throughput ! is maximum.

Figure 5 illustrates the operation of the proposed algorithm for the Philips SOC PNX8550 [START_REF] Kumar Goel | Test Infrastructure Design for the Nexperia ¡ Home Platform PNX8550 System Chip[END_REF], for both the cases with and without stimuli broadcast. For the target ATE, we assumed R " $ U channels and S $ $ M vector memory per channel. Furthermore, we consider 5 MHz clock speed for the test clock, an index time ¨© ¥ s, and a contact test time ¨! $ ¥ ms. For the case without broadcast, Step 1 already yielded the optimal result, i.e., t v x y $ "

, and the corresponding throughput is ! $ " ¢ ' ¥ devices per hour. However, for the case with broadcast, Step 1 results in t v x U $ multi-sites, with a throughput channels get freed-up. Initially there are insufficient freed-up channels to be able increase the channel width to the remaining sites, i.e.,

¦ ) $

, and hence, throughput ! only decreases. ! starts to increase again at y U $

. The straight, dashed line shows, again for the stimuli broadcast case, which throughputs would have been obtained for various multisites, based on Step 1 only. If for some reason (e.g., equipment), the multi-site is limited to, say, `$ % , Steps 1+2 together result in 34% more throughput than Step 1 only.

Experimental Results

First, we present experimental results for the Philips SOC PNX8550 [START_REF] Kumar Goel | Test Infrastructure Design for the Nexperia ¡ Home Platform PNX8550 System Chip[END_REF]. This modular, core-based SOC is based on the Philips Nexperia Figure 6 shows what happens to the test throughput ! if we extend our basic ATE with more channels (Figure 6(a)) or deeper vector memory (Figure 6(b)). The figures illustrate that the test throughput increases linearly with the number of ATE channels; by doubling the number of ATE channels, the test throughput can be doubled. This is due to the fact that the number of sites increases linearly with the number of channels, while the test time remains constant. On the other hand, the test throughput does not increase linearly with the vector memory depth. This is due to the fact that an increase in test vector memory depth leads both to an increase in multi-site, as well as to an increase in test application time. Therefore, doubling the test vector memory does not result in a double throughput. However, the cost of increasing the vector memory depth is rather small compared to the cost of increasing the number of ATE channels. According to standard market prices, buying 16 additional ATE channels with 7 M memory depth would cost roughly USD 8,000. At the same time, upgrading test vector memory for 16 channels from 7 M to 14 M would cost only USD 1,500. Therefore, if we double the test vector memory for all 512 channels, it will cost around

¤ $ U T $ % © $ ¥ ¥ USD ¢ ¥ ¥ ¥
. For this money, the increase in test throughput is 27%. For the same amount of money, we can buy roughly ¢ % channels. This will result in a increase of 18% in test throughput. Therefore, for the same cost, increasing the test vector memory depth is more beneficial than increasing the number of ATE channels. Subsequently, we analyze the impact of the re-test rate on the test throughput. Figure 7(a) shows the variation in the unique test throughput 1 !

with the contact yield ! . From the figure, we can see that the negative impact of re-testing on 1 !

decreases with increasing vector memory depth. This is due to the fact that with deep test vector memory, less ATE channels are used per device, and hence the re-test rate is small. However, for small test vector memories, there is a significant drop in the number of unique devices per hour for low contact yield. Therefore, it can be concluded that deep test vector memory is not only useful from a test throughput point of view, but also from a contact yield point of view. Next, we show the influence of multi-site testing on the effectiveness of applying the abort-on-fail technique. In Figure 7(b), we show the variation in the test time ¨& with SOC yield & . The figure shows that increased multi-site testing quickly reduces the positive effect of applying abort-on-fail. Even at a low yield of 70% (and under the overly optimistic assumption that for failing devices ¨& ¥ , see Equation 4.4), the effectiveness of abort-onfail becomes invisible beyond .

Finally, we compare the results of the proposed algorithm to those published by Iyengar et al. [START_REF] Iyengar | Test Resource Optimization for Multi-Site Testing of SOCs Under ATE Memory Depth Constraints[END_REF] for several ITC'02 SOC Test Benchmarks [START_REF] Jan Marinissen | A Set of Benchmarks for Modular Testing of SOCs[END_REF]. [START_REF] Iyengar | Test Resource Optimization for Multi-Site Testing of SOCs Under ATE Memory Depth Constraints[END_REF] assumes stimuli broadcast and calculates t v x instead of y . In order to compare on an equal basis, for this comparison we also assumed stimuli broadcast and have only applied Step 1 of our algorithm. Table 1 lists the number of ATE channels used for a single SOC. We report both a theoretical lower bound on from [START_REF] Iyengar | Test Resource Optimization for Multi-Site Testing of SOCs Under ATE Memory Depth Constraints[END_REF], as well as our result. In most cases, our algorithm matches the lower bound. The table also lists the 1: Experimental results for maximum multi-site for the rectangle bin-packing algorithm in [START_REF] Iyengar | Test Resource Optimization for Multi-Site Testing of SOCs Under ATE Memory Depth Constraints[END_REF] and our new algorithm.

maximum multi-site J L N , obtained by [START_REF] Iyengar | Test Resource Optimization for Multi-Site Testing of SOCs Under ATE Memory Depth Constraints[END_REF] and by us. In all cases, except for SOC p93791 with 1.768 M channel depth, our algorithm obtains a higher multi-site.

Conclusion

To reduce test cost, multi-site testing is an effective approach. In this paper, we considered multi-site wafer testing and modeled the test throughput considering parameters like test time, index time, stimuli broadcast, abort-on-fail, and contact yield. We showed that multi-site testing requires optimizing the design of the on-chip test infrastructure.

To design the test infrastructure for a given SOC with a fixed target ATE, we presented a two-step algorithm. We design the test infrastructure in such a way, that the SOC test volume fits on the target ATE and the test throughput is maximum. For a given SOC, the presented technique determines the parameters required to design an E-RPCT wrapper around the SOC. If the given SOC is core-based, then the procedure also determines the on-chip test architecture consisting of core wrappers and TAMs.

We presented experimental results for Philips SOC PNX8550, as well as for several ITC'02 SOC Test Benchmarks. The results show that the proposed algorithm outperforms other published approaches. Experimental results also show that to increase the test throughput, increasing the vector memory depth is more costeffective than increasing the number of ATE channels. Finally, we conclude that benefits of the abort-on-fail technique are rather limited when used in combination with multi-site testing.

Figure 1 :

 1 Figure 1: Wafer testing time consists of index time © and test time .

Figure 2 :

 2 Figure 2: Test infrastructure design for (a) modular and (b) flat SOCs. Problems 1 and 2 actually come in several variants: (1) without stimuli broadcast ( `R

Figure 3 :

 3 Figure 3: Fitting SOC test data on the target ATE with as few ATE channels as possible in order to allow the maximum number of multi-sites.

  hour. At t v x U $ , only $ ¥ channels per site are used. As we decrease the number of sites,

Figure 4 :

 4 Figure 4: Example illustration of Step 1 for an SOC with two cores.

Figure 5 :

 5 Figure 5: Example illustrating the operation of the proposed algorithm for Philips SOC PNX8550.

¡

  Home Platform and contains 62 logic and 212 memory modules. In our experiments, we assume R $ U , S M, a test clock of 5 MHz, no stimuli broadcast, ¨© ¥ s, and ¨! $ ¥ ms (unless specified otherwise).

Figure 6 :

 6 Figure 6: Variation in throughput with (a) number of ATE channels and (b) vector memory depth.

Figure 7 :

 7 Figure 7: Impact of (a) re-testing of devices on the test throughput, and (b) abort-on-fail technique on total test time in a multi-site environment.

  (b). Criterion 2 is meant to reduce the test application time per SOC.

	ATE channels	1	2	ATE channels	SOC test SOC test SOC test
	k	SOC test			SOC test
		vector memory depth/channel		vector memory depth/channel
		(a)			(b)

Table

	SOC d695		¡ £ ¥ §	SOC p22810		¡ ¥ £	SOC p34392		¡ ¥ £	SOC p93791		¡ ¥ £
		LB [7]	Us	[7]	Us		LB [7]	Us	[7]	Us		LB [7]	Us	[7]	Us		LB [7]	Us	[7]	Us
	48K	28	28	16	17	384K	36	36	23	27	768K	40	40	21	24	1.000M	54	58	16	16
	56K	24	24	18	20	448K	30	32	27	31	896K	34	34	24	29	1.256M	44	46	21	21
	64K	22	22	22	22	512K	26	28	31	35	1.000M	30	30	31	33	1.512M	36	38	24	25
	72K	18	20	24	24	576K	24	24	35	41	1.128M	26	26	33	38	1.768M	32	36	29	27
	80K	18	18	27	27	640K	22	22	38	45	1.256M	24	24	35	41	2.000M	28	28	33	35
	88K	16	16	31	31	704K	20	20	45	50	1.384M	22	22	38	45	2.256M	24	26	38	38
	96K	14	14	31	35	768K	18	18	45	55	1.512M	20	20	41	50	2.512M	22	24	41	41
	104K	14	14	35	35 16 41 832K 1M 14	14	63	72	2.000M	16	16	55	63	3.512M	16	18	63	63

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

We thank Peter Lagner of Advantest in Munich, Germany, Domenico Chindamo of Agilent Technologies in Rome, Italy, and Stefan Eichenberger and Robert van Rijsinge of Philips Semiconductors in Nijmegen, The Netherlands for fruitful discussions during the conception of this work.


Alexander G Dean
email: alexdean@ncsu.edu

Software Thread Integration and Synthesis for Real-Time Applications

Introduction

Software Thread Integration (STI) [START_REF] Dean | Compiling for concurrency: Planning and performing software thread integration[END_REF] and Asynchronous STI (ASTI) [START_REF] Kumar | Asynchronous software thread integration for effi cient software implementations of embedded communication protocol controllers[END_REF] are compiler techniques which interleave functions from separate program threads at the assembly language level, creating implicitly multithreaded functions which provide low-cost concurrency on generic hardware. This extends the reach of software and reduces the need to rely upon dedicated hardware. STI and ASTI are driven by two types of timing requirements: thread-level (e.g. the delay between an event occuring and a service thread running) and instruction-level (e.g. when a specific instruction or code region must begin executing relative to the start of the function or another such instruction or region). These coarse-and fine-grain approach provide a precise method of defining timing requirements. STI provides synchronous thread progress; both functions proceed lock-step. ASTI provides asynchronous (independent) thread progress through the use of lightweight context switches (coroutine calls) between primary and secondary threads. The primary thread has hard-real-time constraints, while the secondary thread is not real-time, or has much longer deadlines.

We assume that instructions take a predictable number of cycles to execute. This implies a straightforward instruction execution pipeline (if used) and a predictable memory system (e.g. the cache is locked, software managed, or not present). These requirements are met for the processors we target: 8 and 16 bit microcontrollers. We target applications with only one hard real-time thread (the primary thread, used for the communication protocol), although recent extensions to STI [START_REF] Welch | Extending sti for demanding hard-real-time systems[END_REF] support multiple hard-real-time primary threads. We have implemented a thread-integrating compiler Thrint which implements many of these analyses and transformations for the AVR architecture, which is 8bit, load/store, and optimized for embedded C code.

STI

STI targets functions which are independent, data ready and can run to completion. This may require buffering work for one function to ensure it is ready to run when the other is released. For example, in a video controller, graphics ren- dering work is buffered to be available whenever a periodic scan line interrupt service routine runs [START_REF] Welch | Extending sti for demanding hard-real-time systems[END_REF]. STI works by merging two functions into one implicitly multithreaded function, as shown in Figure1. When used for real-time software, it enables the placement of time-critical instructions from one thread so they execute at a specific time relative to the beginning of the integrated function, regardless of the control or data flow characteristics of either thread.

STI begins with building a control-dependence graph representation of the functions to be integrated. We partition the register file between threads at compile time, but more sophisticated register allocation is possible. The bestand worst-case timing of the code is derived statically. This timing is then regularized; execution paths of uneven duration are padded to last the same amount of time (nops and nop loops are used for space efficiency).

Code from one thread can now be moved to execute at given time in the other, using code transformations such as motion, replication, and various for loops (peeling, splitting, guarding, unrolling and fusion). Integration copies code into each path of control flow in a location which ensures it executes at the correct times regardless of the thread progress. Integration involves control-dependence graph traversal (and is hierarchical), and nested transformations are cumulative. Non-looping primary code regions are handled individually. Moving a region into a conditional requires replicating it into both sides, while entering a loop requires either guarding the execution with a conditional which triggers on a specific loop iteration or else splitting and peeling the loop. Looping primary function regions are unrolled and treated as non-looping regions unless they overlap with secondary function loops. In that case the overlapping iterations of the two loops are unrolled as needed to match the secondary function loop body work to available idle time in the primary function loop body, increasing efficiency. Integrated code may be also guarded by a conditional test to allow execution based upon mode flags. Next, the timing of the code is analyzed statically again to verify that the transformations placed code properly. In the final stage assembly code is regenerated from the control graph to be assembled and linked with the rest of the application.

ASTI

ASTI targets applications with frequent context switches and a requirement for asynchronous thread progress. For example, in a software-implemented (bit-banged) communication protocol, the protocol thread must run whenever there is bus activity. However, the idle time in the protocol thread is fragmented into pieces lasting less than a bit or byte. To avoid starvation, other threads are integrated with the protocol thread so they run during the idle time.

ASTI cuts the cost of context switching between the primary (e.g. protocol) and secondary threads by reducing the number of switches, as shown in Figure 2. ASTI uses the idle time T Idle within a frequently-called primary thread function as a window in which to execute a segment of a secondary thread via a coroutine call (or cocall). There will be T SegmentIdle = T Idle -2 * T Cocall of that time available, given that two cocalls (T Cocall long each) must execute for each segment. After padding to equalize timing of conditionals and loops modulo T SegmentIdle , the entire secondary thread is broken into segments of duration T SegmentIdle . Intervening primary code within the idle time window is removed and integrated into each segment of the secondary thread, ensuring that running any segment of the secondary thread will still result in the proper intervening primary code executing at the correct times. Coroutine calls are integrated in the secondary thread to ensure it yields control back to the primary thread at the end of the segment, just before the available idle time expires.

Applications

In the STIGLitz project [START_REF] Welch | Extending sti for demanding hard-real-time systems[END_REF], STI enables an inexpensive 20 MHz AVR 8-bit microcontroller to generate monochrome NTSC video while servicing a high-speed (115.2 kbaud) serial communication link. This system offers graphics rendering speed-ups of 3.99x to 13.5x by recovering fine-grain idle time in the display refresh function and using it for video rendering.

We used ASTI to create a bridge between an RS232 link and a software-implemented J1850 automotive embedded network protocol controller [START_REF] Kumar | Asynchronous software thread integration for effi cient software implementations of embedded communication protocol controllers[END_REF]. Compared to an interruptbased approach, ASTI results in a secondary thread speedups of 1.56x (message reception) and 1.83x (transmission), enabling the use of an 8 MHz AVR 8-bit microcontroller. An interrupt-based approach would require a 14.7 MHz clock to provide the same performance.

Conclusion

STI and ASTI extend the performance of commodity low-end microcontrollers through static scheduling techniques, potentially avoiding the need for dedicated hardware or faster clock speeds.

Figure 1 .

 1 Figure 1. STI interleaves functions at the assembly code level.

Figure 2 .

 2 Figure 2. ASTI eliminates most context switches and also recovers finer grain idle time.

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

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


Ian Oliver
email: ian.oliver@nokia.com

Applying UML and MDA to Real Systems Design

Traditionally system design has been made from a black box/functionality only perspective which forces the developer to concentrate on how the functionality can be decomposed and recomposed into so called components. While this technique is well established and well known it does suffer from some drawbacks; namely that the systems produced can often be forced into certain, incompatible architectures, difficult to maintain or reuse and the code itself difficult to debug. Now that ideas such as the OMG's Model Based Architecture (MDA) or Model Based Engineering (MBE) 1 and the ubiquitous modelling language UML are being used (allegedly) and desired we face a number of challenges to existing techniques.

When working with the UML, one must take into consideration object orientation. The UML is a language for expressing systems (or whatever) in terms of object oriented concepts and its meta-model and its semantics make this explicit. Object orientation, unlike functional based approaches makes both functionality and data first-class modelling elements. Whenever anything is specified in UML, that modelling element is either based on the notion of a class or is directly related to a class. Some methods appear to adhere to this but fail to use classes in this way by assuming the existence of a 'global' system and then just using classes as data elements. Effectively the UML equivalent of programming Fortran in C++.

Use case based development makes this situation worse by only concentrating only on behaviour and then also by not by integrating with the class-object concepts of OO. Use cases are often 'realised' as sequence diagrams, where the objects are never shown nor specified in a class diagram so that analysis of how the objects may be correctly connected or related is never achieved. In this approach objects themselves are just the objectification of functions.

The result of this is that systems developed using use cases suffer from poor or non existence object orientation, little or impossible to achieve reuse, every object in the system can communicate and be related to every other object in the system (coupling tends to be very high if not total) and that if a class structure is reverse engineered then it is often the case that most classes contain a single function which is often redefined in very deep inheritance hierarchies. Inheritance If use cases are to be used then they must either be as very high level requirements which are then subjected to proper OO analysis2 and/or they are later used as tests to the system (cf: Model Based Testing). Use cases here are being used as the basis of scenarios that the customer believes they want; they can be thought of as scripts or constraints in the model checking sense. There is almost never a one-to-one mapping between the use cases and the functionality of the system that is finally constructed, just that the system is capable of providing the services or functionality required to enact the described scenario.

In an OO based system, the global behaviour or functionality is emergent from the particular collaborations and configurations of objects and their relationships rather than being specified explicitly for the whole system. Use cases in this respect are preferably used as (high level) tests to the model rather than first-class development artifacts.

The Model Driven Architecture is based around the concepts of models and transformations (or mappings) between those models. A transformation is a kind of model which contains information about the platform onto which you are mapping its source model(s). In a more generic scenario, a model may actually be a structure of models and a transformation a generic engine that takes a model of a platform as its parameter. The source models of a transformation are known as platform independent models (PIMs) and the target models as platform specific models (PSMs). These terms are relative to a given platform -given any model one can not state whether it is platform independent or platform specific without a second model related to it by one or more transformations.

What the MDA is trying to achieve is the axiomatisation of development and architectural principles; the knowledge held by engineers on solving certain problems is embodied inside the transformations. The situation however is no different from the ideas of compilation of 3 ¡ generation languages into machine code -transformation engines in some MDA tools are known as model compilers.

The MDA as defined by the OMG is based around that models are expressed in the UML or one of its profiles and that their meta-models are expressed in the Meta Object Facility or MOF. Transformations then act on the meta-model level transforming the concepts in one meta-model to concepts in another meta-model. However, as MOF can be considered a form of graphical BNF then any language's meta-model can be expressed in this form. Note that transformations operate at a semantic level rather than syntactic and may take a large amount of contextual or platform information into consideration. Compare this with the generally poor attempts at automatic code generation seen in many tools which seemingly equate the notion of a class at any abstraction level with that of a class in some 3GL programming language. A syntactic transformation implies that no change of abstraction level is made between the input and output of the transformation and effectively the input and output are the same but just expressed in different formalisms with the same semantics; this is commonly seen with say, SDL and C or UML or Java/C++.

Application in System Development

To correctly apply UML/MDA one must have a much greater understanding and adherence to the various levels of abstraction that are possible, a well defined separation of concerns and a process/method that actively supports modelling.

Abstraction relates to what information is required in models and how these models relate to each other. One of the problems with UML is that it is often used at the same level of abstraction as the implementation. There are very few tools that allow much further abstraction in a meaningful way. This is then coupled with areas where OO is unknown, for example hardware or protocol development, which gives way to concerns about the models not containing enough information or being too abstract for meaningful development. UML is designed as an extensible language which can be tailored for particular domains, it is in the system domain and the hardware aspects, that currently UML is particularly lacking.

MDA requires that, ideally, for each particular aspect or concern and at each level of abstraction a model is constructed. This separation of concerns, while good engineering practise, is rarely seen. Deciding which aspects are necessary for successful system development is difficult as is maintaining these concerns. At each abstraction level a well defined set of tests must be performed upon this system and maintained as the 'system models' are developed. At minimum one must have a separation between the domain of the system (what the system is) and the potential platforms (or architectures) onto which the system may be mapped. Separation of 'domain' and 'platform' is the key to success here and avoiding polluting either model with information from the other.

The language of these models varies depending upon abstraction level and aspect. There do exist numerous UML profiles for this work and in particular we note UML for QoS and Fault Tolerance, UML Profile for Schedulablity, Performance and Time, the UML Testing Profile, the Systems Modelling Language (SysML) and the UML for Communicating Systems (ETSI). Unfortunately these languages lack overall coherence, unless you count the core UML they are based upon, and lack of tool support. The other major problem here is that the concepts in these languages are often ambiguous even at a platform independent or generic level, for example, "what is a process?" UML2 is not going to solve any problems here as to the casual user nothing has changed although there are new diagram types but less information on the semantics of these diagrams and once again how the diagrams and their elements relate to each other in the model. Classes are classes regardless of whether UML1.x or 2.x is used and their meaning context dependent. This leads to then methodology (meaning the combination of methods and process). While we have languages and concepts for expressing artifacts and modelling elements relevant to systems development we are sorely lacking in consistent, well defined methods for the utilisation of these languages. As yet, while the MDA provides us with a methodological structure we are still missing how the modelling languages fit into that structure. A well defined set of semantic transformations do not exist for manipulating those models at their various levels of abstractions; those transformation that do exist are often syntactic in nature and do not effectively take into consideration the mapping via a platform into a more platform specific model.

Much of the methodology work required is deciding which languages (UML profile + extensions) to use at which level of abstraction and how each level of abstraction relates to each other. Certainly a core, basic language must be used at higher level of abstraction, eg: plain UML with each level progressively adding more information and changing the language. This change is dictated somewhat by the chosen platforms for mapping and thus the target implementation.

Finally if one is to model then one must have a reason about why those models are being produced. If a model can not be tested somehow then there is little point in producing that model -models must convey information to the users of those models. Testing here can mean metrics, validations (simulation, animation etc), verification (proof, model checking) and so on.

Conclusion

The problems faced by UML and MDA in systems development are broadly the same as in any other development area.

The main problem we have encountered faced is that OO is not common in this area and that the UML is being misunderstood and not being applied correctly -the wrong types of analysis are being made (functional vs OO). Often it is just the case that the models do not contain any relevant information and are not being used to support the system under development -this is commonly seen with documentation oriented methods in which the documentation is more important than the actual product itself and thus the quality of that product. While UML has the potential to support other development paradigms it is still inherently an object oriented language and requires support from external processes and methodsthis must be understood first before successful application.

we use MDA in this article but the terms are generally interchangeable here often gets used as a development mechanism rather than the taxonomy mechanism it really is.

Uses cases are not object oriented! 1 Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

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


Diana Marculescu

Energy Bounds for Fault-Tolerant Nanoscale Designs

published or not. The documents may come

Introduction

Nanoscale computing for either CMOS or non-CMOS technology is widely agreed to be characterized by nondeterministic and unreliable behavior. In the case of nanometer CMOS designs, uncertainties stem from process and system parameter variability and their impact on performance and behavior of switching devices, as well as from increased susceptibility to soft errors which may thus create incorrect or faulty functionality. For non-CMOS nanoscale electronics (such as molecular or self-assembly), uncertainties in operation originate in the inherent non-deterministic switching behavior of such devices. While fault-tolerant computing is a mature area of research, automatically designing reliable systems out of unreliable components may prove to be a challenging task. As a natural solution to the fault-tolerance problem, the use of redundancy has been proposed and analyzed theoretically as early as five decades ago in the seminal work of von Neumann [START_REF] Neumann | Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components[END_REF] and more recently by others [START_REF] Pippenger | Reliable computation by formulas in the presence of noise[END_REF][START_REF] Pippenger | On a lower bound for the redundancy of reliable networks with noisy gates[END_REF][START_REF] Kleitman | On the design of reliable Boolean circuits that contain partially unreliable gates[END_REF][START_REF]Lower bounds for the complexity of reliable Boolean circuits with noisy gates[END_REF][START_REF] Evans | On the maximum tolerable noise for reliable computation by formulas[END_REF][START_REF] Evans | Signal propagation and noisy circuits[END_REF]. While a practical solution to synthesizing in an automated manner nanoscale designs that are inherently fault-tolerant has yet to be found, nonetheless such theoretical results offer a good insight into the achievable limits of error-resilience and required minimum redundancy (or extra logic) needed. Furthermore, in the case of CMOS nanoscale technology, power density and energy cost have become the main design bottlenecks [START_REF]International Technology Roadmap for Semiconductors[END_REF]. Adding redundancy in the hope of increasing error-resilience has the negative effect of eventually decreasing the energy efficiency of a given design. Thus, given the clear trade-off between achieving resilience via redundancy addition and energy efficiency, tools that can aid and guide the design process in a nanoscale design methodology become mandatory.

This paper is a step in this direction, by proposing theoretic lower bounds and trade-offs between energy efficiency and redundancy needed for achieving a certain error-resilience level. Such bounds and theoretical trade-offs provide valuable insights early in the design process and may aid and guide the automatic synthesis process of nanoscale systems. While the faulttolerance aspects described in this paper are relevant for any type of nanoscale designs based on emerging technologies that inherently include non-determinism in normal operation, we will restrict ourselves to considering as a driver application computing systems that use electrons and energy barriers to represent or manipulate their states [START_REF] Zhirnov | Limits to Binary Logic Switch Scaling -A Gedanken Model[END_REF]. CMOS nanoscale designs are one such example. Based on first principle physics laws, it has been shown recently [START_REF] Zhirnov | Limits to Binary Logic Switch Scaling -A Gedanken Model[END_REF] that power density of such designs will reach in the next decade values close to 100 Watts/ cm 2 . These power densities, coupled with increased complexities and integration densities, put a lot more pressure on achieving more efficient designs in the nanoscale era. To address this problem, we consider the case of fault-tolerant nanoscale systems which need to rely on added redundancy to be able to cope with increased error rates. To characterize the available trade-offs between the required redundancy and the associated energy cost, we propose the use of a complexity theory-based framework.

Related Work and Paper Contribution

This paper addresses the impact of error-resilience and redundancy in a theoretical framework that can guide the design process for nanoscale systems. Our framework is able to provide bounds on the energy cost associated with achieving a given error-resilience level for a design based on error-prone gates (characterized by non-deterministic behavior), while also detailing when these bounds are likely to be tight. As opposed to the theoretical bounds developed by von Neumann and his successors [START_REF] Neumann | Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components[END_REF][START_REF] Pippenger | Reliable computation by formulas in the presence of noise[END_REF][START_REF] Pippenger | On a lower bound for the redundancy of reliable networks with noisy gates[END_REF][START_REF] Kleitman | On the design of reliable Boolean circuits that contain partially unreliable gates[END_REF][START_REF]Lower bounds for the complexity of reliable Boolean circuits with noisy gates[END_REF][START_REF] Evans | On the maximum tolerable noise for reliable computation by formulas[END_REF], our approach does not assume any particular use of redundancy, such as majority voting or parallel restitution [START_REF] Neumann | Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components[END_REF]. Instead, it is based on a framework relying on information theory concepts [START_REF] Evans | Signal propagation and noisy circuits[END_REF] to quantify the energy efficiency of nanoscale designs in the presence of errors.

While the problem of analyzing the fault-tolerance of nanoscale designs under given gate or wire error models has been recently started to gain interest [START_REF] Bahar | A Probabilistic-Based Design Methodology for Nanoscale Computation[END_REF], no such study has linked the error-resilience of a circuit to its energy efficiency. Recent work [START_REF] Hegde | Towards achieving energyefficiency in presence of deep submicron noise[END_REF] has shown, using information theoretic arguments, that it is possible to trade-off energy efficiency and fault-tolerance through the use of voltage scaling. Indeed, by allowing the voltage to be reduced, power cost is reduced significantly, while noise level is increased, thereby allowing for trading-off energy and error-resilience. However, our goal is different. We propose to quantify how added redundancy necessary for achieving reliable operation out of unreliable components impacts overall energy efficiency of a nanoscale design. In addition, our approach is not bound to any particular type of redundancy (based on techniques such as majority voting or parallel restitution) and assumes that "noisy" gates and can be modeled as error-free devices cascaded with a symmetric communication channel modeling the error. In addition, while previous work [START_REF] Hegde | Towards achieving energyefficiency in presence of deep submicron noise[END_REF] has linked energy efficiency and fault-tolerance in an information theoretic environment, it targets voltage scaling-reliability trade-offs and does not address entities that are more complex than a single gate or device. Our theoretical framework is able to completely characterize complex designs in terms of the energy-errorresilience trade-offs, while also providing insights into the relative contributions of static and switching energy.

Preliminaries

Without loss of generality, we restrict ourselves to nanoscale systems with the following characteristics: • Circuits are assumed comprised of devices or gates that can be either error-free, or failure prone. 1

•

We consider the case of error-free and failure-prone circuits in which internal gates can fail independently with a probability . 2 We assume that any interconnect error probabilities are lumped into device error probabilities.

•

We also consider device (gate) output error probabilities modeled as symmetric communication channels with an ε error probability. As shown in Figure 1, each failure-prone device is assumed modeled as an error-free device cascaded with a symmetric communication channel.

•

For the case of failure-prone circuits, we consider the case of -reliable computation, that is, with probability of 1-δ, the output of the circuit is correct.

•

While not restricting ourselves to any particular technology characterized by failure-prone operation, we consider the case of systems that use electrons and energy barriers to represent or manipulate their states. Examples include nanoscale CMOS applications or systems comprised of irreversible logic switch devices.

• Given this constraint, we are mostly concerned with switching energy or the energy lost due to information processing or transfer. To this end, we consider the impact that any additional redundancy added to increase error resilience has on the overall energy efficiency of a nanoscale design. Assuming that most of the switching energy is consumed during output charging and discharging (

, where E is the total energy consumed during a certain time interval, V dd is the supply voltage, C is the load capacitance and sw is the total switching activity during the considered interval), fault-tolerant circuits relying on added redundancy for increased error resilience can have both their load capacitance and switching activity affected.

In addition, added redundancy may also impact logic depth, and thus overall latency. To this end, trade-offs between energy, delay or composite metrics (such as energy-delay product) on one hand, and required output error resilience δ, on the other hand, can be uncovered and analyzed in an analytical manner.

Bounds on Switching Energy Metrics

Intuitively, added logic redundancy, not necessarily committed to any particular implementation (e.g., majority based voting used in triple or n-tuple modular redundancy vs. parallel restitution [START_REF] Neumann | Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components[END_REF]) is expected to increase the error resilience of a failure-prone nanoscale design by providing multiple logical paths from the inputs to the outputs, thus decreasing the impact of the "noise" on the overall input-output communication channel. One may expect that the added redundant logic (when error-free) will perform in a similar manner as far as switching activity is concerned. However, we note that a non-zero error probability on the output of each device (be it part of the original circuit, or part of the redundant logic) can affect the switching behavior of that gate output, as shown next.

Impact on Switching Activity

In what follows, we denote by p(x) the probability of a binary random variable x being one and by sw(x) the probability that x changes state. We also denote by x an array of binary variables, and by f a multiple output Boolean function.

The following result quantifies the change in the switching activity that a given "noise" level produces on the output of a switching device: Theorem 1. If y, z are the error-free and error-prone outputs of a device which fails with a probability of as in Figure 1,then: . Hint for proof: 3 Uses switching activity definition for temporal 1. Devices and gates are assumed to denote the same entity in this paper. 2. As it will be seen in the sequel, if error probabilities are close to 1/2, reliable computation is not possible unless an unbounded overhead is considered.

0 ε 1 2 ⁄ ≤ ≤

Error-free device

Error model

x y z 0 0 1 1 ε 1 ε - 1 ε - y z ε Figure 1.
Modeling error-prone devices using error-free devices and a symmetric communication channel error model ε. The errorfree device is a gate with a single or multiple bit input x and a single bit output y.

1 δ - ( )
3. Due to space limits, if not provided, all proofs can be found in [START_REF] Marculescu | Fault-Tolerant Nanoscale Design: An Energy Perspective[END_REF].

E 1 2 ---CV dd 2 sw = ε sw z ( ) 1 2ε - ( ) 2 sw y ( ) 2ε 1 ε - ( ) + = independent signals:
. It is interesting to note that failure-prone designs do not necessarily experience a monotonic trend as far as switching activity is concerned. As seen in Figure 2, while for smaller values of the error probability ε, the switching activity is less affected, for larger values (closer to 0.5) the switching activity becomes closer to 0.5, thus making gates with smaller switching activity more active and vice versa. In other words, increased error rates make the output of a failure-prone device look more random and less likely to carry any useful information.

Impact on Circuit Size

As shown in Theorem 1, any non-zero probability of error for a failure-prone device affects its average switching activity. In addition, added redundancy does not come for free: it affects both logic depth, as well as circuit size, which in turn affect performance and energy cost of the entire system.

In this section, we quantify the impact of added logic redundancy on circuit size, for a given error probability per gate ε, and a required maximum error probability on the output δ.

The following result provides the tightest bounds known for the minimum circuit size required for computing a Boolean function with a given output fault-tolerance: Theorem 2. [START_REF] Evans | Information Theory and Noisy Computation[END_REF] For and , if a Boolean function is -reliably computed by a circuit with ε-noisy, k-input gates, then the additional redundancy in the circuit is at least: 1 where s is the sensitivity of Boolean function f (or the maximum number of inputs that, if changed individually, produce a change on the output), , and .

The theorem confirms previous results [START_REF]Combinatorial Methods in Boolean Function Complexity[END_REF][START_REF] Reischuk | Reliable Computation with Noisy Circuits and Decision Trees, A General nlogn Lower Bound[END_REF] that show an proportionality relation for the error-prone circuit size, but points to a superlinear increase in complexity with increased values of ε. Indeed, for ε values close to 0.5, circuit size approaches infinity, thus making -reliable computation impossible for all practical purposes. On the other hand, it has been shown [START_REF] Pippenger | Reliable computation by formulas in the presence of noise[END_REF][START_REF] Pippenger | On a lower bound for the redundancy of reliable networks with noisy gates[END_REF][START_REF]Lower bounds for the complexity of reliable Boolean circuits with noisy gates[END_REF]] that an upper bound on the size of a faulttolerant circuit is (S 0 is the size of the error-free implementation). For both the upper and lower bounds, equality is achieved for parity functions, implemented using decision trees or Shannon-like circuits. While the result above holds for single output circuits (Boolean functions), we extend it to general circuits below: Corollary 1. For and , if an m-output function of n inputs is -reliably computed by a circuit with ε-noisy, k-input gates, then the additional redundancy in the circuit is at least: where s is the sensitivity of the multiple output function f , and are as in Theorem 2. Hint for proof: The characteristic function for f is a single output function with the same sensitivity.

To understand the impact of increased gate count due to added redundancy, we show in Figure 3 the lower bound from Theorem 2 and Corollary 1 as a function of device error ε to -reliably compute a 10-input parity function with sensitivity s = 10, error-free size S 0 = 21, and δ = 0.01. We note that more than an order of magnitude redundancy factor is needed for error levels close to 0.5. It is thus expected that the increased size will also impact the total load capacitance and energy cost of the implementation.

Impact on Switching Energy

The impact of using redundancy on the energy of fault-tolerant nanoscale designs can be quantified through: 1) the change in the average switching activity for a generic internal gate; and 2) the change in the required number of devices needed to achieve a certain output reliability. Since we assume that, if considered error-free, redundant logic behaves almost the same as the original circuit in terms of switching activity, one can infer that Theorem 1 holds for the average switching activity of the errorfree and error-prone circuits implementing the same function.

In addition, Corollary 1 can be used to quantify the increase in the total load capacitance of the fault-tolerant 1. In this paper, log is assumed base two, unless noted otherwise. --------------------------------------------------------------------t ω --------------------------------- --------------------------- --------------------------------------------------------------------t ω , implementation: most high-level energy estimation frameworks have shown that total load capacitance is, with sufficient accuracy, proportional to the total device count [START_REF] Nemani | Towards a high-level power estimation capability[END_REF][START_REF] Marculescu | Information-Theoretic Measures for Power Analysis[END_REF]. Thus, one can conclude that the increase factor in energy for a faulttolerant implementation satisfies the following:

ε increases 0 ε < 1 2 ⁄ ≤ 0 δ ≤ 1 2 ⁄ < 1 δ - ( ) s s 2s 2 1 2δ - ( ) ( ) log ⋅ + log ⋅ k t log ⋅ -
3 1 ω - ( ) 3 + ω 1 ω - ( )
= ω 1 1 2ε - k - 2 -
= s s log ⋅ 1 δ - ( ) O S 0 S 0 log ⋅ ( ) 0 ε < 1 2 ⁄ ≤ 0 δ ≤ 1 2 ⁄ < f : 0 1 , { } n 0 1 , { } m → 1 δ - ( ) s s 2s 2 1 2δ - ( ) ( ) log ⋅ + log ⋅ k t log ⋅ -
1 δ - ( )
Corollary 2. Consider . The energy E ε,δ of a circuit composed of ε-noisy, k-input gates, that reliably computes f satisfies: where E 0 is the energy cost of the error-free implementation, s is the sensitivity of f , sw 0 (

) is the average switching activity per gate of the error-free implementation, S 0 is the size of the error-free circuit implementing f , and are as in Theorem 2. Hint for proof: Uses Theorems 1-2 for energy estimation, assuming load capacitance is proportional to the total device count [16][17].

Case Study: Nanoscale CMOS Designs

The results presented in Section 4 hold true for the switching energy of any nanoscale computing system that relies on irreversible switching devices that use electrons and energy barriers to represent or manipulate their states. However, it is worth noting that, in the particular case of nanoscale CMOS designs (i.e., 0.09um and beyond) leakage power becomes the dominant component of the overall power, and thus increased redundancy implies increased number of idle devices or more leakage power. In addition, added logic redundancy comes at the expense of increased logic depth, which affects negatively circuit latency and overall performance. We address the sequel some of these issues and the available trade-offs between switching energy bounds and leakage cost or performance.

Impact on Leakage Power

While the direct impact of logic redundancy on static power is clear through the increased number of potentially idle devices, there is a more subtle effect on leakage energy, due to changes in average switching activity per gate. More precisely, with probability a generic gate in the error-prone circuit is idle and subject to leakage energy, not switching energy. Thus, any change in the average switching activity triggers a change in the overall contribution of leakage energy to overall circuit energy. The next result details this change: Theorem 3. If is the ratio of leakage energy to switching energy in a circuit composed of ε-noisy gates, then:

where is the ratio of leakage energy to switching energy in the error-free case and sw 0 ( ) is the average switching activity per gate of the error-free implementation.

Hint for proof: Since switching energy and static energy (S 0 is the size of the circuit, V dd the supply voltage, and K is a factor that depends on technology and threshold voltage), we can use Theorems 1-2 to determine switching/static energy in the error-prone case.

To understand how the relative contribution to the overall energy cost changes, we show in Figure 4 the variation of the normalized ratio for the error-prone circuit, with respect to the error-free implementation for various switching activity values and error probabilities. As it can be noticed, the relative contribution of leakage energy decreases with increased error rates if the switching activity sw 0 is less than 0.5. Indeed, in this case, switching activity in the error-prone implementation increases and thus devices are less likely to be idle. The opposite is true if the switching activity of the error-free circuit exceeds 0.5. The relative contribution stays the same if sw 0 is exactly 0.5.

Impact on Performance, Average Power and Energy-Delay Product

Added redundancy is expected to have a significant effect on the circuit depth as well, and thus on overall latency. Indeed, the following result has been shown for circuit depth of faulttolerant circuits: Theorem 4. [START_REF] Evans | Signal propagation and noisy circuits[END_REF] Consider . The logic depth d ε,δ of a circuit composed of ε-noisy, k-input gates, that -reliably computes f satisfies:

• If , then . • If , then .
where with 1 and ∆ is defined as ----------------------------------------------------------------

f : 0 1 , { } n 0 1 , { } m → 1 δ - ( ) E ε δ , E 0 ---------- 1 s 2 2 1 2δ - ( ) ( ) log ⋅ + log ( ) k t log ⋅ -
- s S 0 ----- ⋅ + 1 2 ε - ( ) 2 2ε 1 ε - ( ) sw 0 ---------------------- + ⋅ ≥ 0 sw 0 1 ≤ < t ω , 1 sw ε δ , - (
) -----------------------------------------------------------------------------

W L ε δ , , W L ε δ , , W L 0 , ---------------- 1 2ε - ( ) 2 2ε 1 ε - ( ) 1 sw 0 - ( ) ⁄ + 1 2ε - ( ) 2 2ε 1 ε - ( ) sw 0 ⁄ + -
= W L 0 , 0 sw 0 1 < < 1.
As shown in Section 4, only error levels that are less than 0.5 are of practical interest, thus the error probability is modeled as . ) as a function of device error probability ε. The baseline is the ratio for the error-free implementation ( ).

E 0 S 0 V dd 2 sw 0 ∝ E L 0 , 1 sw 0 - ( ) S 0 V ⋅ dd K ⋅ ⋅ ∝
Note the logarithmic scale on the Y-axis.

W L ε δ , , W L 0 , f : 0 1 , { } n 0 1 , { } m → 1 δ - ( ) ξ 2 1 k ⁄ > d ε δ , n∆ ( ) log kξ 2 ( ) log ⁄ ≥ ξ 2 1 k ⁄ ≤ n 1 ∆ ⁄ ≤ ε 1 ξ - ( ) 2 ⁄ = 0 ξ < 1 ≤ 1 ξ - ( ) 2 ⁄
. In other words, to achieve a given error resilience (characterized by δ), for sufficiently low error probabilities per gate, the minimum logic depth is inversely proportional to ; otherwise, no circuit -reliably computes f , unless the number of inputs is less than 1/∆. In the latter case, no known bounds are available for the size of the fault-tolerant implementation.

Analyzing these results, we note that, trade-offs between the fault-tolerance and performance, on one hand, and the average power consumption, or energyxdelay product, on the other hand, can be deduced. Assuming that the latency of the failureprone circuit varies as [START_REF] Chen | Performance and Vdd Scaling in Deep Submicrometer CMOS[END_REF] (where V T is the threshold voltage and α is a technology dependent factor), if the same energy budget as the error-free circuit is targeted, the fault-tolerant implementation will need to rely on a lower V dd to compensate for the change in switched capacitance, which in turn further increases overall latency. Similar conclusions can be drawn if performance constraints need to be maintained instead: in this case, V dd must be increased to compensate for the logic depth increase, thus triggering an energy increase. As shown in Figure 5, the lower bound for normalized energyxdelay product is higher than the one for normalized latency, for the same error level. This comes at no surprise, given the fact that both energy and delay increase for the faulttolerant circuit implementation. However, the same cannot be said about the average power (or energy spent per unit time).

Figure 6 shows the dependency of the normalized average power on the device error probability and internal gates fanin. As it can be seen, for low error rates, the average power of the fault-tolerant implementation is larger than the one of the errorfree circuit: in this case, delay increases at a lower rate than circuit size, and thus energy. Furthermore, a larger fanin reduces the overhead in average power. For larger error rates, however, the logic depth (and thus delay) increases at much higher rates than circuit size, thus making error-resilient implementations more power efficient, at the expense of significantly larger delays. In this case, larger fanins introduce a smaller power reduction as the difference in the increase rate for circuit depth and circuit size tapers off.

Results

Although the theoretical results presented in previous sections are applicable on average to generic circuits, it is worthwhile to investigate how do these lower bounds apply for specific benchmarks. Even though all lower bounds presented are tight for a certain family of Boolean functions (mainly, parity functions implemented using decision-trees or based on a Shannon-like organization), when applied to specific circuits, these bounds still offer an idea about the possible trends that switching (and static) energy may have for fault-tolerant nanoscale designs.

To this end, we consider a subset of ISCAS'85 benchmarks and some computer arithmetic circuits (ripple-carry adders and array multipliers) with various bitwidths. The ISCAS'85 benchmarks have been optimized in the SIS [START_REF] Sentovich | SIS: A System for Sequential Circuit Synthesis[END_REF] environment using script.rugged. All benchmarks have been mapped using a generic library comprised of gates with a maximum fanin of three. The average switching activity of a generic gate part of each benchmark has been obtained considering randomly generated inputs. For the error-free implementation we have assumed that 50% of the total energy is leakage (which is inline with predictions for technologies smaller than 0.09um [START_REF]International Technology Roadmap for Semiconductors[END_REF]).

We show in Figure 7 the lower bounds for the energy and delay of the fault-tolerant implementation, normalized with respect to the error-free implementation. In each case, we consider three scenarios corresponding to gates independently failing with probability ε = {0.001, 0.01, 0.1}, and required maximum probability on the output δ = 0.01. As it can be seen, the lower bounds increase significantly with higher error rates, necessitating in some cases at least 40% more energy if error rates are 1% per gate. We note that, while energy bounds are more circuit dependent (due to Boolean sensitivity s and switching activity sw 0 ), delay is less so, as the only circuit specific information it relies on is the average fanin k. Figure 8 shows the trend for the average power and energyxdelay lower bounds, normalized with respect to the error-free implementation. While energyxdelay lower bound experiences up to a 2.8X increase, average power is reduced due to the significant increase in logic depth (and latency).

∆ 1 δ δ log 1 δ - ( ) 1 δ - ( ) log + + = kξ 2 ( ) log 1 δ - ( ) D ε δ , d ε δ , V dd V dd V T - ( ) α ----------------------------- ⋅ ∝

Conclusion

This paper has introduced the use of complexity theory concepts for determining lower bounds on energy and related metrics for nanoscale, fault-tolerant designs. The theoretical results presented herein can be used to guide the automatic synthesis of error-prone nanoscale designs, while also uncovering the interplay between switching and static energy for these systems. Future work includes the treatment of sequential circuits and the refinement of the lower bounds depending on the circuit functionality.

Figure 2 .

 2 Figure 2. Switching activity of error-prone devices as a function of the switching activity of error-free devices.

Figure 3 .

 3 Figure 3. Minimum redundancy needed as a function of the device error ε, for s = 10, S 0 = 21, and δ = 0.01 assuming 2-, 3-, and 4input gate implementations.

Figure 4 .

 4 Figure 4. Normalized ratio between leakage energy and switching energy ( ) as a function of device error probability ε. The

Figure 5 .

 5 Figure 5. Normalized delay (energyxdelay) as a function of ε. The baseline is the delay (energyxdelay) for the error-free implementation. The contributions of the switching and leakage energy are assumed equal and switching activity is considered 0.5 in the baseline. All other parameters are as in Figure 3. Note the logarithmic scale on the Y-axis.

Figure 6 .

 6 Figure 6. Normalized average power as a function of device error probability ε. The baseline is the average power for the error-free implementation. The contributions of the switching and leakage energy are assumed equal and the switching activity is considered 0.5 in the baseline. All other parameters are as in Figure 3.

Figure 7 .

 7 Figure 7. Lower bounds for energy and delay for ε = {0.001, 0.01, 0.1} and δ = 0.01, normalized with respect to the error-free implementation. The contributions of switching and leakage energy are assumed equal in the error-free baseline.

Figure 8 .

 8 Figure 8. Lower bounds for average power and energyxdelay for ε = {0.001, 0.01, 0.1} and δ = 0.01, normalized with respect to the error-free implementation. The contributions of switching and leakage energy are assumed equal in the error-free baseline.

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