Specification Test Compaction for Analog Circuits and

Testing a non-digital integrated system against all of its specifications can be quite expensive due to the elaborate test application and measurement setup required. W e propose to eliminate redundant tests by employing based statistical learning. Application of the proposed methodology to an operational amplifier and a MEMS accelerometer reveal that redundant tests can be statistically identified from a complete set of specification-based tests with negligible error. Specifically, after eliminating of eleven based tests for an operational amplifier, the defect escape and yield loss is small at 0.6% and respectively. For the accelerometer, defect escape of 0.2% and yield loss of 0.1 occurs when the hot and cold tests are eliminated. For the accelerometer, this level of Compaction would reduce test cost by more than half.

'There can, of course, be yield loss and defect escape based on the type of test used for each specification however.

Introduction

In contrast to digital circuit test, there are no universally accepted fault models for non-digital components. Consequently, validating the circuit specifications continues to be the most accepted form of non-digital component test However, the number of circuit specifications to be verified has increased significantly over the past few decades. In addition, the cost to verify each specification can be exorbitant due to elaborate test setup, test pattern application and measurement. In order to reduce test cost, only a subset of the specifications are actually verified in practice The subset of specifications used for testing is selected based on the experience of designers and test engineers. Such an ad selection of the specification set can lead however to an unpredictable amount of yield loss and defect escape.

A desired solution to this problem is to develop a costeffective test methodology that can verify all the circuit specifications. Several efforts have been published that address this goal. For example, various low-cost, built-in test (BIST) solutions have been proposed that reduce test cost by eliminating external test equipment Alternately, efforts have been made to use digital circuitry to generate tests and analyze test data for mixed-signal circuits

Work in [6] describes a test sequence generation approach that can implicitly verify all the circuit specifications. In this approach, test cost is reduced by using tests that are not derived from the specifications. We propose to achieve the goal of obtaining a cost effective test set that can verify all the device specifications by identifying and eliminating the redundancy in the complete specification test set using statistical learning. Beginning the test set compaction procedure from the complete specification-based test set guarantees no initial escape or yield loss'. Redundant tests are eliminated until the prediction error exceeds a user-defined tolerance. During test set compaction, a statistical model is derived to predict behavior based on the remaining tests. Since the amount of prediction error of the derived statistical model is constrained, the procedure enables controlled yield loss and defect escape in contrast to ad test compaction. In addition, when the statistical model makes an inconsistent prediction, the tested part is deemed to belong to a "guard-bandregion". Devices in the guard-band region can be further tested to prevent unnecessary yield loss.

The rest of the paper is organized as follows: In Section 2, we introduce the necessary background for the problem addressed. Section 3 contains a description of the statistical learning based specification test set compaction procedure. Section 4 describes solutions to the various roadblocks encountered during test compaction. In Section 5, we scribe simulation results showing the viability of the test set compaction procedure for an operational amplifier and a MEMS accelerometer. Finally, in Section 6, our work is summarized and future work is described.

Preliminaries

In this section, we present the terminology and background necessary for discussion of the specification-based test compaction methodology.

Definitions

A specification for a device under test (DUT) is a performance parameter of the circuit that must be measured and verified. A specification test for includes setup for application of stimuli, application of the stimuli and analysis of the responses to obtain the value of for a particular manufactured device. We define a device instance to be good if all the specification values = .., obtained from the specification-based tests T = . . , fall within a set of desired ranges R = ..,r,}, where is the acceptable range for specification A device instance is deemed bad or faulty if any of the values obtained from the specification tests T fall outside the corresponding range The process of finding if a device is good or bad is called the analysis. In this paper, we achieve test compaction by identifying and eliminating tests = ..., for redundant specifications = . . . , from the complete set of specification-based tests T. It is important to note however that a greater level of compaction may be possible if the compaction process is performed at the test level as opposed to the specification level.

Statistical Learning and

The following terminology is adapted from Given a set of data points is minimized, and (3) the number of maxima and minima in f (X) is minimized. This means that the error in estimating at most data points in . . . , is controlled to be less than E . However, there can be where > and the additional error is denoted as The value

= -f
is the model error for f (X) at

Since testing is intrinsically a classification problem, E-SVM is especially suited for the test compaction methodology. Additionally, E-SVM gives sufficiently high accuracy in reasonable time making its repeated application feasible. Finally, E-SVM can efficiently handle the huge data set that is required during test compaction (details are given in Section 4.1).

Test Set Compaction Methodology

To remedy the drawback of traditional ad elimination of tests, we propose a systematic approach to prune the test set using

Data Generation

Training data is generated using Monte-Carlo simulations of devices with random variations imposed on various device parameters. This approach most likely creates some devices that are not possible within a real manufacturing environment. However, a test compaction methodology that works well here will also perform well for realistic devices. In addition, test compaction using training data generated from device simulation is significantly less expensive as compared to actual tests applied to a manufactured chip However, the downside is that simulation data is likely less accurate.

Figure 1 shows a block diagram illustrating the process of training data generation for N device (training) instances.

In the process of training data generation, the device description, the list of device specifications that are to be considered for compaction, and a manufacturing process model

Test Set Pruning

The goal of a systematic test set compaction approach is to offer control over yield loss and defect escape while test cost is reduced. Figure 2 The aforementioned procedure described is obviously greedy which means the optimality of the solution depends on the order in which the tests are examined. An alternative approach involves assessing the number of training instances successfully classified by each specification to decide test order. Yet another approach focuses on clustering specifications based on an estimate of their mutual dependence. The resulting clusters would be used to decide test order. In our case, we analyze device functionality to decide the order of the tests.

Application on the Tester

A compacted test set is the set of specification-based tests that must be applied to the DUT. However, the acceptability ranges are no longer valid. In fact, surfaces for the acceptability ranges of the compacted test set are created by the statistical model. Consider three specifications and where can be expressed as = After elimination of the test for redundant specification new acceptability ranges and for specifications and describing the behavior of the DUT are created.

the acceptability ranges change because there can be device instances that fall within and but not within meaning the instance is faulty. The change in and is illustrated in Figure 3. The rectangular box in Figure 3 represents the acceptability ranges and while the shaded region is the derived area defining good devices when the test for is eliminated. It is therefore necessary to provide the tester with this additional information for correct analysis of the manufactured devices. One solution is to provide the tester with the model derived from the training data. However, this may require a significant amount of additional tester resources. Alternately, we propose to divide the space of compacted specifications into grids and assign a good or bad attribute to each grid cell based on information gathered from the statistical model. This creates a lookup table that can be added to the tester program with little additional cost. analysis. The dots represent "good" device instances while the crosses represent "bad" device instances.

Statistical Learning for Test

Given the overview of the proposed test compaction methodology in Section 3, here we elaborate upon the issues associated with applying statistical modeling to the manufacturing test of analog and MEMS

Classification versus Regression

The traditional approach for statistical learning based test has focus on regression [6, However, regression is a multi-dimensional problem, where each dimension is a specification. Consequently, the training data required to adequately cover the multidimensional space for building the regression model can be extremely large. We observe that the test problem is a simple classification issue. Additionally, classification only requires adequate coverage of the class boundaries, thus significantly reducing the training data required for modeling. Therefore, based classification is an appropriate choice for the test compaction problem addressed.

Guard-Band Region

It is important to note that analysis for test is a two-class classification problem. This means a DUT that has measured specification values for each specification S within is "good" and one that has at least one measured value outside is "bad". As a result, there is discontinuity at the boundary between good and bad. Consequently, a very small model error for devices near the boundary can lead to significant misclassification. Consider a set of devices located the boundary of the decision. Also assume that these devices have the same values for the set of specifications {Sbut have unequal We use two models to build the guard-band region. The boundaries are perturbed in each direction by a preset value to create these two models. A device predicted to be good or bad by both models can be classified to be good or bad with high confidence. On the other hand, a contradiction in the predictions from the two models means that the device is in the guard-band region. The two dotted lines in Figure are obtained by perturbing the boundary by a predefined amount and the region between the two dotted lines is the guard-band region.

Based on the number of expected devices in the band region and cost, devices can be further tested to answer the question. Since it is likely that the number of devices belonging to this class will be small, potential benefits of adaptive test can be easily obtained. Alternately, the devices in the guard-band region may be deemed as good or bad, or even classified to be of lower grade based on the quality requirements of the application.

Training Data Compaction and Normalization

Although more training instances is desirable for obtaining a good coverage of the input space, building a statistical model with a large data set can be quite time consuming. To alleviate this problem, we propose to compress the data set by eliminating some training instances. Specifically, the training space is divided into a grid space. Only training instances belonging to grid cells with good as well as bad training instances are retained in the new training data set. For grid cells that contain only good or bad devices, the training instances are merged by using the center point of the grid cell with the appropriate attribute. Because different specifications have different units and ranges of variations, it is necessary to normalize the data to ensure uniform convergence of the multi-dimensional space. Each specification has a predefined acceptability range that is used to determine if the device satisfies We normalize each specification value of the training instance by mapping the lower bound of the to zero and the upper bound to one. This means that after normalization, a good device specification value is in the range [0, and any value outside the range is bad.

Test Compaction Examples

The proposed methodology has been applied to an operational amplifier and a MEMS accelerometer. For both examples, the training data has been generated using the circuit simulator Virtuoso Spectre libraries have been used to model the MEMS accelerometer. For statistical classification, we have used to perform

Operational Amplifier

The first device considered was an operational amplifier that was not fabricated. Five thousand training instances and 1000 test instances were generated by randomly altering the MOSFET lengths and widths and capacitor values within of their nominal values. Our choice for training and test data sizes was somewhat arbitrary in that it was based on the amount of CPU time required for simulation. Recall that training instances are used for model generation, while test instances are used to verify the derived model. A guard band of of the acceptability range boundaries was defined. Guard band size was cho- sen to optimally trade-off the number of instances in the guard band versus prediction error. The prediction error is equated to the number of incorrect predictions made by the derived model. More specifically, yield loss is defined as the number of good devices the model predicted to be bad, and defect escape is the number of bad devices the model predicted to be good.

Table 1 lists the set of specifications considered for the operational amplifier. The specifications considered and their units are listed in Columns 1 and 2, respectively. Column 3 contains the nominal values of each specification, while Column 4 lists the range of values in which the circuit is deemed good. The corresponding yield of the operational amplifier is 75.4% and 84.8% for the training and test data, respectively.

Figure 5 plots the yield loss, defect escape and the number of devices predicted to belong to the guard-band region for increasing levels of test compaction. The x-axis shows the eliminated tests. Specifically, the plots show the various components of error as the named tests are cumulatively eliminated as we move from left to right along the x-axis. As observed from the plot in Figure 5, a significant amount of specification compaction can be obtained at a very low level of prediction error, while the number of instances predicted in the guard-band region remains stable. This means that a trade-off between the amount of test cost reduction and prediction error exists. The optimal amount of test cost reduction can be determined by setting defined error limits based on the application.

Note that the decrease in the number of devices in the guard-band that occurs for the elimination of the shortcircuit test is accompanied with an increase in defect escape and therefore does not reflect an improvement in model accuracy as tests are eliminated. Of course, the unknown model error associated with prediction can cause a montonic change in accuracy but this is unlikely given the use of a well-chosen guard band.

MEMS Accelerometer

MEMS accelerometers are subjected to tests at hot and cold temperatures in addition to the room-temperature tests for the same set of specifications These temperature tests are quite expensive as the manufactured chip has to be heated or cooled until it reaches the desired steady-state temperature. Significant cost can therefore be avoided if temperature test outcomes can be predicted using the room-temperature test results.

We analyzed a MEMS accelerometer design from using 1000 training and 1000 test instances. These instances were generated by adding variations to the accelerometer component lengths, widths and relative angles. Similar to the example, the number of device instances generated was limited by amount of CPU time required by Spectre to simulate an accelerometer instance. The effect of temperature is modeled as chip shrinkage or expansion, meaning the anchors of the accelerometer move towards or away from the center of the accelerometer for cold and hot temperatures, respectively. Finally, the guard-band region was defined to contain devices that have specification values within of the acceptability range boundaries. Similar to the amplifier, guard band size was chosen to optimally trade-off the number of instances in the guard band versus prediction error. Table 2 lists the accelerometer specifications that are tested at the three temperatures. The accelerometer yield is 77.4% and 79.3% for the training and test data, respectively. The hot, cold and room temperatures used for testing are -40°C and respectively. The results of the compaction process for the hot and cold temperature tests are given in Table Rows Table 2. Specifications for a MEMS accelerometer, their nominal values and ranges.

Conclusions

We have proposed a statistical learning based specification compaction procedure. As opposed t o ad compaction in use today, this methodology allows for a controlled yield loss and defect escape. Additionally, use of simulation for compaction is advantageous in terms of cost. We have also proposed the use of classification based SVM modeling that is specifically suited for test. Initial application of the approach to an operational amplifier and a MEMS accelerometer shows significant test compaction can be achieved with very low yield loss and defect escape due to prediction error.

In future work, we plan t o generate training instances that model the manufacturing process in a more accurate fashion and test instances that also contain real defects. We also intend to estimate the guard-band region based on the device distribution as opposed to a fixed Finally, we would like to build a cost model that accurately quantifies the reduction in test cost as well as overall device cost due to test compaction.

'

  This research is supported by the and GSRC programs under contracts 2003-CT-888 and 2003-DT-660, respectively.

  Statistical (Machine) Learning is the process of building a model for the unknown relation = using the given set of data points. The data that is used to build the model is called the training data, while the data used to verify the model is called the test data. In this work, we have used Vector Machines (SVM) for statistical learning based model derivation. The goal in is to build a hyper-plane that divides the input into two classes that pertain to = and = -1. Given a set of training data . . . , and a predefined error limit this classificationis achieved by building a function f (X)to esti-

  for the device serves as input. The device representation is altered based on the process model. Each altered device representation is known as a training instance. Based on the set of specifications under consideration, the device instance is set up, simulated, and measurements are derived from simulation results. This measured data is stored as training data. The whole process is repeated until the number of training instances simulated equals the number of training instances desired.

  Figure A description of training data generation.

  illustrates how the proposed test compaction methodology achieves this goal. The process of test compaction begins with the complete based test set, the training data set and acceptability ranges for each specification. Based on the range data, the nature of each device instance is obtained and added to the training data. Next, the test compaction process starts with the complete test set meaning that is empty which implies no initial yield loss or defect escape. A test t , is then selected for potential elimination and is removed from the training data set. Using E-SVM, the reduced training data is utilized to build a model for predicting for the set of eliminated specifications The total number of device instances that are sified with respect to defines the prediction error If it is possible to build a E-SVM model to have a prediction error on test data to be lower than a user-defined tolerance the chosen test is deemed redundant and is permanently from the set of specification-based tests. If, on the other hand, the model cannot be created with sufficient accuracy, the test is deemed necessary and is added back to the set of specifications to be explicitly tested. This process is continued until each test t , T is examined. At the end of this process, a compacted set of specification-based tests and a model predicting the behavior of the device based on the compacted set of tests is obtained.

Figure 2 .

 2 Figure 2. A flowchart description of the process of specification test compaction.

Figure 3 .

 3 Figure 3. An illustration of the derivation of new acceptability ranges foranalysis. The dots represent "good" device instances while the crosses represent "bad" device instances.

Figure 4 .

 4 Figure 4. An illustration of the accuracy improvement going from (a) an unguarded boundary to (b) a guarded decision boundary. The solid line indicates the decision boundary, while the dotted lines show the guard band. To solve this problem, we propose to guard-band the decision boundaries. Guard banding significantly reduces the probability of a good device being predicted as bad (yield loss) or a bad device being predicted as good (defect escape). Guard banding is useful because only the tail of the device distribution from a good or a bad prediction falls in the incorrect class. Consider now a set of devices near the guard-band boundary, where again all the devices have the same values for and different values for From Figure we observe that only the tail of the device distribution associated with that particular prediction falls in the incorrect class. The use of a guard band therefore significantly reduces the likelihood of misprediction.We use two models to build the guard-band region. The boundaries are perturbed in each direction by a preset value to create these two models. A device predicted to be good or bad by both models can be classified to be good or bad with high confidence. On the other hand, a contradiction in the predictions from the two models means that the device is in the guard-band region. The two dotted lines in Figureareobtained by perturbing the boundary by a predefined amount and the region between the two dotted lines is the guard-band region.Based on the number of expected devices in the band region and cost, devices can be further tested to answer the question. Since it is likely that the number of devices belonging to this class will be small, potential benefits of adaptive test can be easily obtained. Alternately, the devices in the guard-band region may be deemed as good or bad, or even classified to be of lower grade based on the quality requirements of the application.

Figure 5 .Figure 6 .

 56 Figure 5. Percentages of yield loss, defect escape and number of devices predicted in the guard band as specification tests are dropped in order from left to right. To illustrate how model accuracy is improved by the amount of training data, we have plotted trends for yield loss, defect escape, and the number of devices predicted in the guard band against number of training instances in

  3 through 5 in Table3contain respectively the percentages of the N

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

Acknowledgement

The authors would like to thank Prof. Gary Fedder and Dr. Nilmoni Deb for their insights in temperature variation modeling and temperature test for the MEMS accelerometer.


Pekka Syri

Juha Hakkinen

Markku Moilanen

IEEE 1149.4 compatible ABMs for basic RF measurements

An analogue testing standard IEEE 1149.4 is mainly targeted for low-frequency testing. The problem studied in this paper is extending the standard also for radio frequency testing. IEEE 1149.4 compatible measurement structures (ABMs) developed in this study extract the information one is measuring from the radio frequency signal and represent the result as a DC voltage level. The ABMs presented in this paper are targeted for power and frequency measurements operating in frequencies from 1 GHz to 2 GHz. The power measurement error caused by temperature, supply voltage and process variations is roughly 2 dB and the frequency measurement error is 0.1 GHz, respectively.

Introduction

An emerging testing standard IEEE 1149.4 allows the access of selected locations in the ASIC for testing purposes [START_REF]IEEE Standard for a Mixed-Signal Test Bus[END_REF]. The standard uses so-called analogue boundary modules (ABM) to access the internal and external signals of the ASIC. However, the standard is mainly targeted for low-frequency testing, wherefore it is not directly applicable to high-frequency use.

In order to allow the measurement of RF signals, some kind of signal processing must be performed inside the ABM. This processing extracts the information one is measuring from the RF signal and represents the result as a low-frequency signal, which can be further processed by structures specified in the standard (1149.4). Specifically, the aim of this study is to design the required RF analogue circuit structures (i.e. RF-to-LF signal processing) needed to produce IEEE 1149.4 compatible ABMs for RF frequency and power measurements.

Test circuit

The circuit is composed of two individual ABM structures, the first being a basic RF-ABM shown in Fig. 1 and the other containing preamplifiers, which allows the measurement of weaker signals. The main parts of the basic RF-ABM shown in figure 1 are frequency (Fdet) and power detectors (Pdet) which output DC quantities relative to the input signal power and frequency, respectively.

Measurement results (Vout, out-and out+) from and tuning inputs (tunef and tuneP) to the detectors themselves can be connected to the IEEE 1149.4 type analogue test port (ATP) using a programmable switch matrix (.4 MUX). Both ABM structures are controlled with an external control unit (PC, for example) using a serial data bus (signals labelled select in the figure originate from this serial data).

Power detector

Literature reports many possible circuit topologies, which may be used for RF power measurement [START_REF] Robert | Low-Power Monolithic RF Peak Detector Analysis[END_REF][3] [START_REF] Ratni | A New Structure for a Six-Port Reflectometer using a Silicon MOSFET for Power Measurement[END_REF]. Unfortunately the circuit process, which was used to realize the ABM test circuit, did not offer support for diode-or BJT-based power detectors. Therefore, a circuit structure comprising only a MOS transistor shown in Fig. 2 was developed.

Fig. 2. MOS transistor based RF power detector.

In this circuit, the gate of transistor Q 1 is biased exactly to the threshold voltage, external tuning of this voltage is possible through the IEEE 1149.4 analogue bus via pin V t . Now, Q 1 will conduct current I D only for the positive half cycles of the sinusoidal input voltage V i , thus creating an output voltage across the load composed of R 4 and Q 2 similar to that of the half wave rectifier. The DC value, which is relative to the input power of this output signal, is extracted by the low pass filter formed by the load and C 2 . Output voltage of the power detector can be calculated by equation [START_REF] David | Analog Integrated Circuit Design[END_REF] where I DC = DC value of the half wave rectified drain current of Q1.

Frequency detector

The frequency detector shown in Fig. 3 was used in the test circuit. The operation of the circuit is depicted in reference [START_REF] Djemouai | High Performance Integrated CMOS Frequency-to-Voltage Converter[END_REF].

Fig. 3. The schematic of the frequency detector.

Main operating principle of the frequency detector is that after many periods of the input signal, the voltage across C 2 will reach a stable (DC) value, which is related to the input frequency f (=1/T) by equation [START_REF] Djemouai | High Performance Integrated CMOS Frequency-to-Voltage Converter[END_REF] f C

I T C I V c c o 2 1 2 1 1
.

(2)

Measurement results

Both ABM structures were tested to ensure they are operating according to the simulations. More accurate characterization measurements were performed for the basic ABM only. ABM structures were DC-calibrated before measurements using tuning connections (tuneP and tunef) [see fig 1.].

According to measurements made on the silicon, the accurate measurement range of the power detector is from 1.2 GHz to 1.8 GHz. Figure 4 shows the calculated power measurement error vs. the simulated response and the error without process variation. In these measurements the frequency of the measured signal was 1.5 GHz (the middle frequency of the accurate measurement range), the supply voltage was 2.5 V 0.25 V and the temperature range was -10 C…70 C. According to the measurement results the power measurement range of the basic ABM is -18 dBm…6 dBm. The preamplifiers of the other ABM increase the measurement range to the lower power levels and the final range is from -25 dBm to -3 dBm.

Figure 5 shows the calculated frequency measurement error vs. the simulated response and the error without process variation (the supply voltage was 3.3 V 0.3 V and the temperature range was -10 C…70 C). According to the measurements the power level of the measured signal for the frequency detector of the basic ABM has to be at least +5 dBm and the representative value for the structure including preamplifiers is -5 dBm.

Conclusions

It seems according to the simulations and measurements that it is possible to use the IEEE 1149.4 testing standard for radio frequency testing. The ABMs developed in this study can be used in basic frequency and power measurements. DC-calibration developed in this study decreases measurement errors considerably. The power measurement error caused by the temperature, supply voltage and process variations is roughly 2 dB and the frequency measurement error is 0.1 GHz, respectively. If the error caused by the process variation is calibrated out, the power measurement error decreases to 1 dB and the frequency measurement error to 0.05 GHz, respectively.

Fig. 1 .

 1 Fig. 1. The basic ABM.

Fig. 4 .

 4 Fig. 4. Power measurement error vs. simulated response and error without process variation.

Fig. 5 .

 5 Fig. 5. Frequency measurement error vs. simulated response and error without process variation.

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


Carlos Eduardo Savioli

Claudio C Czendrodi

Jose Vicente Calvano
email: calvano@olimpo.com.br

Antonio Carneiro

Mesquita Filho
email: mesquita@coe.ufrj.br

Fault-Trajectory Approach for Fault Diagnosis on Analog Circuits

This issue discusses the fault-trajectory approach suitability for fault diagnosis on analog networks. Recent works have shown promising results concerning a method based on this concept for ATPG for diagnosing faults on analog networks. Such method relies on evolutionary techniques, where a generic algorithm (GA) is coded to generate a set of optimum frequencies capable to disclose faults.

Introduction

The modern fabrication processes for electronic circuitry allow highly integrated d evices. Such p ossibilities together with the endless wishes of customers drive the electronic industry, demanding g ood solutions for test, design for testability and diagnosis. Such wishes boosters the complexity of the test issue. The diagnosis problem m ay be considered the paramount, and, so far, there is a lack in the literature of an approach generic enough, to be considered a method. Our issue intends to discuss the suitability of a fault trajectory approach for component fault diagnosis on analog circuits. The method is based on the fault trajectory concept for fault diagnosis on analog networks, which relies on evolutionary techniques, where a GA is coded to o ptimize test vector generation.

The method

The method consists of finding a convenient test signal to excite the circuit under test (CUT), and observe at output, a response, that m ay be considered faulty, depending on a given requirements. According to the behavior of the output response faulty components diagnose can be performed. The test signal m ust have the following requirements: i t must disclose faults in the circuit, and, in addition, it must disclose which component is faulty also. However, on the other hand, it shouldn't have a n excessive number of different input patterns. Then, the test may not consume a great amount of time; nor should g enerate a test vector long and complex, which may be unfeasible and expensive. Yet, at the circuit's output, the response signal shall be convenient for a detection issue. For such needs, GAs [START_REF] Holland | Adaptation in natural and artificial systems[END_REF], as robust search-space data miners, seems to b e a very useful approach to discover potential set of optimal solutions [START_REF] Rechenberg | Evolut.-Optim. Tech. Syst. nach Prinzip. der biologischen Evolut[END_REF][START_REF] Fogel | Artificial Intelligence through Simulated Evolution[END_REF], GAs can be used to produce test patterns [START_REF] Prinetto | An ATPG for Large Sequential Circuits based on GAs[END_REF]. In this case, GAs are able, from a first set of random t est patterns generated automatically, to verify the suitability of each pattern towards the ideal solution defined by the user [START_REF] Mesquita | Chromosome Repr. through Adjacency Matrix in Evolut[END_REF]. Some of these patterns may be discarded and o thers may be recombined among each other, in a continuous search for even better test patterns.

The fault model and the fault dictionary

Our approach u ses a fault simulation process (FS), where an adequate fault model m ust be used. It i s assumed that the faults are under the functional parametric fault [START_REF] Calvano | Fault Models and Test Generation for OpAmp Circ.-The FFM[END_REF] paradigm: a fault in a circuit will be the result of a parametric deviation in a component value. This way, faults in R & C are represented as % deviations on their values, and faults on active devices will be represented as % deviation on the values of their macro model [START_REF] Calvano | Fault Models and Test Generation for OpAmp Circ.-The FFM[END_REF]. The FS process consists of building from the original circuit (the one with nominal values components) a set of different circuits (the faulty ones), where their components are out the nominal value at a time. This is done inserting faults on all i ts components (systematic % deviation on its values) within a given range. As an example if the target circuit is a filter, and its main requirement is its frequency response, one can assume that a good attempt for a test vector is a set of sinusoidal signals.

Of course, the filtering behavior is totally checked against a frequency sweep generator, but, in practice, such approach is unfeasible especially for built-in structures. This way, what we look for is a test vector composed b y a minimum of frequencies. The correct choice of such set of signals is made via the use of a FS and a GA for optimizing the search, since the number of f aulty circuits against a possible set of frequencies are infinite.

Application example

We have used a normalized biquad negative feedback low-pass filter as the CUT [START_REF] Calvano | Fault Models and Test Generation for OpAmp Circ.-The FFM[END_REF]. The devices of the CUT whose faults are to be detected are the seven passive components. When a parametric fault is inserted, the value of a passive device is transformed in a value, which may range from e.g. 60%-140% of its nominal value. For each passive component faulty circuits are generated u sing parametric deviations in steps of 10% of deviation, the zero % represents the nominal behavior (fig. 1). High diagnosis will be possible if our test vector is able to distinguish a faulty device from another one. This way, we have to look for the test vector components that are able to evidence every faulty component influence in the circuit response. Using the frequency-sampling theorem, we propose a linear transformation that reduces all observable spectra of a given response to a point of a Cartesian coordinate space. Figure 2 depicts 2 curves, the 1 st one is called H, and represents the golden behavior, and the 2 nd one, called K, a faulty response due to a defective component. If both circuits were stimulated by a test vector composed b y, e.g. two frequencies f 1 & f 2 , it will be equivalent to sample the two curves at f 1 and f 2 frequencies. The sampling performed in fig. 2 leads to the following transformation into a Cartesian coordinate XY plane: H(f 1 )=A 1 , K(f 1 )=B 1 , and H(f 2 )=A 2 K(f 2 )=B 2. As the sampling frequencies are the same for each curve, the transformation yields the pairs: (A1,A2), & (B1,B2), as XY coordinate points. The 1 st p oint represents the golden behavior and the 2 nd a faulty one. Some simplification is introduced if we consider the golden behavior p oint as the Cartesian coordinate plan origin.

The "Fault Trajectory"

As we are dealing with analog linear continuous-time circuits, we consider reasonable the responses are smooth and monotonic. Crescent/De-crescent parametric deviations on components within a given range shall produce a set of coordinate points in the plane which can be c onnected, to compose what we define a fault trajectory. According to this concept, each d eviated d evice in the c ircuit has its own trajectory, or "component parametric fault trajectory", in that Cartesian plan. Fig. 3 depicts such situation, in this case for the c omponent R3 [START_REF] Calvano | Fault Models and Test Generation for OpAmp Circ.-The FFM[END_REF]. Each fault t rajectory, in order to b e distinguished each other, must have a totally independent "pathway". Finally, the "efficacy", or diagnosis grade, for a given test vector, is enunciated as: "One shall be able to find out a set of frequencies f 1 ,f 2 ,...f n to compose a test vector in order to distinguish the highest number of fault components via circuit faulty behavior". To accomplish the above statement (i.e., to find out the frequencies that composes the test vector), evolvable techniques are used. This optimizes the search of the best solution over a spread and wide universe of possible solutions.

The "Genetic Algorithm"

We have c hosen a test vector composed b y two frequencies. A GA performs the suitability analysis of a given test vector. The basic flow of the GA is found in [START_REF] Savioli | ATPG for Fault Diagnosis on Analog Electrical Networks Using Evolutionary Techniques[END_REF]. Its main features are: 128 individuals, 15 g enerations, reproduction rate of 50%, mutation rate of 40%, the "roulette wheel" as the mining method, and the number of generations as the stop criteria. The selection method or the fitness criteria a re based on the search of a graphical configuration for the trajectories that minimizes the number of common pathways, and intersections among the fault trajectories. The fitness of a test vector composed by f m , f n is given as: fitness (f n , f m ) = 1 / (1+I). Where I is the number of trajectories intersections. Each faulty circuit corresponds to a point in our XY plane. These points can be piece-wised, and considering that just one c ircuit's component is faulty at a time, we have the procedure: Given a point in the Cartesian plane due to an unknown fault, it can be assigned to a PW segment, which would be the segment with the highest probability to b e the right one. Such operation is done drawing perpendiculars from known fault trajectories to the point where the unknown fault is (fig 3) the unknown fault is represented by an (*). In this example, the unknown fault seems to belong to the N device trajectory, since its distance to the only two segments from which perpendiculars exist is smaller for the N-type than to the M-type fault.

3.

Figure 1 :

 1 Figure 1: "golden behavior" & "fault dictionary items".

Figure 2 :

 2 Figure 2: the transformation into a coordinate data.

Figure 3 :

 3 Figure 3: R3 fault trajectory (left), fault diag. (right).

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


Jung-Chun Kao
email: jungchuk@ece.cmu.edu

Radu Marculescu
email: radum@ece.cmu.edu

Energy-Aware Routing for E-Textile Applications †

As the scale of electronic devices shrinks, "electronic textiles" (e-textiles) will make possible a wide variety of novel applications which are currently unfeasible. Due to the wearability concerns, low-power techniques are critical for etextile applications. In this paper, we address the issue of the energy-aware routing for e-textile platforms and propose an efficient algorithm to solve it. The platform we consider consists of dedicated components for e-textiles, including computational modules, dedicated transmission lines and thin-film batteries on fiber substrates. Furthermore, we derive an analytical upper bound for the achievable number of jobs completed over all possible routing strategies. From a practical standpoint, for the Advanced Encryption Standard (AES) cipher, the routing technique we propose achieves about fifty percent of this analytical upper bound. Moreover, compared to the non-energy-aware counterpart, our routing technique increases the number of encryption jobs completed by one order of magnitude.

Introduction

The scaling of device technologies has opened research opportunities in the area of pervasive computing [START_REF] Marculescu | Electronic Textiles: A Platform for Pervasive Computing[END_REF]. In particular, it became possible to fabricate flexible materials with sophisticated computing and communication devices embedded into them. Such computational fabrics, called etextiles, are expected to have many applications ranging from consumer electronics, to military, health and security devices.

For e-textiles, the system has to be not only light and mobile, but also withstand wear-and-tear due to frequent washing. Due to the potential stress upon e-textile's interconnects, one solution is to use a communication network instead of the traditional bus-based architecture. Besides reliable operation, e-textiles have strict processing, storage, energy and size constraints per computational node. Thus, in order to be able to handle complicated applications, electronic textiles need to rely on low-power techniques. The target application that runs on an e-textile platform must be appropriately partitioned and able to self-manage as a whole. These additional requirements lead to an interesting and unique routing problem which is the main objective of this paper.

Advanced Encryption Standard (AES) [7] is selected as the driver application running onto an e-textile platform. This selection is motivated by two reasons: First, AES is a robust encryption algorithm so since data secrecy plays a critical role in pervasive computing, exploring the potential of AES for distributed implementations on e-textile fabrics becomes very important. Second, in June 2004, IEEE ratified the wireless local area network (WLAN) standard, 802.11i which requires AES for data encryption. This further increases the potential of AES for future pervasive applications.

Our approach to study the distributed implementation of AES on e-textiles consists on several steps: First, we divide the AES cipher into several modules (each performing an unique function) that we design and simulate in Verilog. Second, we develop an energy-aware routing strategy. This consists of a mapping technique from application modules to architecture nodes in a mesh-based topology of various sizes, a control mechanism based on a TDMA scheme, and the online general-purpose energy-aware routing (EAR) algorithm. A cycle-accurate network simulator, et_sim, has been developed as a by-product for e-textile platforms. The electrical characteristics of dedicated components extracted from our designs, plus data from [START_REF] Cottet | Electrical Characterization of Textile Transmission Line[END_REF][START_REF] Neudecker | Lithium-Free Thin-Film Battery with In Situ Plated Li Anode[END_REF] are fed into et_sim to compare EAR results with the non-energy-aware routing counterpart.

From a theoretical standpoint, our contribution is twofold: First, we formulate the routing problem for e-textile applications and develop an online energy-aware routing algorithm to solve it. Second, we derive an analytical upper bound for the achievable number of jobs completed in arbitrary architectures. According to the simulation results, EAR achieves approximately 50% of the analytical upper bound and exceeds its non-energy-aware counterpart by a factor between 5 to 15 times. We point out that the methodology and theoretical results presented here apply to any e-textile distributed system, either wearable or nonwearable (e.g. e-textiles hanging on the walls, etc).

The remainder of the paper is organized as follows. In Section 2, related work is summarized. We formulate the routing problem in Section 3. In Section 4, we present the analytical upper bound for all possible routing strategies. Section 5 outlines the architectural issues, the battery model and detailed platform description. The general-purpose energy-aware routing algorithm is discussed in Section 6. We present the experimental results for the AES cipher and compare them with the analytical upper bound in Section 7. In Section 8, we conclude by summarizing our main contribution.

Related Work

There has been some recent work on embedding complicated electrical components into wearable fabrics. In [START_REF] Post | Smart Fabric, or Wearable Clothing[END_REF][START_REF] Post | E-Broidery: Design and Fabrication of Textile-Based Computing[END_REF], the authors demonstrate the idea of attaching off-theshelf electrical components to traditional clothing materials and also provide the method by which user interfaces (and even chip packages) may be woven directly into fabric during textile manufacturing.

On the other hand, devices dedicated for e-textiles such as textile transmission lines (e.g. [START_REF] Cottet | Electrical Characterization of Textile Transmission Line[END_REF]) and batteries (e.g. thin-film batteries [START_REF] Neudecker | Lithium-Free Thin-Film Battery with In Situ Plated Li Anode[END_REF][START_REF] Neudecker | Power Fibers: Thin-Film Batteries on Fiber Substrates[END_REF]) are currently under development. The routing of electrical power and communication through a wearable fabric is addressed in [START_REF] Gorlick | Electric Suspenders: A Fabric Power Bus and Data Network for Wearable Digital Devices[END_REF]. It provides a detailed account of the physical and electrical components for routing electricity through suspenders made of fabric and embedded conductive strands, as well as a data-link layer protocol on a Controller Area Network (CAN) bus.

Several architectures with distributed deployment of batteries are proposed in [START_REF] Stanley-Marbell | Modeling, Analysis and Self-Management of Electronic Textiles[END_REF]. Adaptive techniques, such as code migration and remote execution, applied to redundantly deployed nodes have also been proposed to increase the operational lifetime of the e-textile applications.

In contrast to these previous efforts, we investigate techniques for energy-aware routing to increase the operational lifetime of a system and the achievable number of completed jobs. Several energy-aware routing algorithms have been proposed for wireless ad-hoc/sensor networks in [START_REF] Maleki | Lifetime Prediction Routing in Mobile Ad Hoc Networks[END_REF][START_REF] Chang | Maximum Lifetime Routing in Wireless Sensor Networks[END_REF]. However, they do not apply to e-textile platforms because of the inherent difference in the cost functions that characterize wireless and wired environments, and because of their high requirement of computational and memory resources. We follow the same general distributed deployment scheme of batteries as in [START_REF] Stanley-Marbell | Modeling, Analysis and Self-Management of Electronic Textiles[END_REF], but due to potential link failures, the target architecture in our case is a network instead of a bus-based architecture. Also, unlike [START_REF] Stanley-Marbell | Modeling, Analysis and Self-Management of Electronic Textiles[END_REF], fixed and re-programmable devices are supported as computational nodes in our architecture. These differences make our routing problem quite unique.

Problem Description

We assume that i) the target application is partitioned into several modules which have been customized or are available as IP cores in a library, and ii) the target e-textile system is composed of a wired communication network which connects many active and idling nodes. Each module performs an unique (fixed) function and cooperates with other modules to complete the job by exchanging packets of fixed length. Each node is an instance of exactly one module; it is possible to have, however, duplicates of modules across the network. The total number of nodes that implement different modules in the network cannot exceed the total number of available nodes.

It is assumed that each node has its own attached battery and, for simplicity, all batteries have the same initial capacity. An operation is defined as the act of computation at any module and the subsequent act of communication until the originated packet arrives at the next node which can be either an intermediate node or the destination node. Typically, each module needs to perform several operations before a job is completed. A node is considered dead when its attached battery is completely depleted. The target system dies when the critical nodes become dead.

In general, the hardware modules can be either fixed or reprogrammable, but the remapping techniques (e.g. code migration and remote execution [START_REF] Stanley-Marbell | Modeling, Analysis and Self-Management of Electronic Textiles[END_REF]) on reprogrammable modules are not considered in this paper. Instead, it is assumed that, once determined, the application mapping onto architecture remains fixed. This avoids not only the difficult prediction of the overhead caused by the remapping techniques (which is highly dependent on architecture and application itself), but also the requirement of using reprogrammable components. Our main objective is to design an energy-aware routing strategy that can increase the number of jobs completed for e-textile applications. Finding the appropriate routing strategy involves several design issues such as choosing the appropriate network topology, control mechanism, mapping technique, etc. To better present the formulation of the routing strategy problem, we summarize the basic parameters in Table 1.

Table 1: Parameter notation

Parameter Description

RS

Routing strategy which consists of network topology, mapping technique, control mechanism and routing algorithm J (RS) The number of jobs completed under the routing strategy RS B Initial capacity of each battery (battery budget) K

The maximum number of available nodes (node budget) p

The number of (distinct) modules f i

The number of operations that module i has to run before a job is completed where 1 i p E i

Energy consumption of module i per act of computation where 1 i p S i

The set of nodes at which duplicates of module i are located where 1 i p n i

The number of duplicates of module i in the target topology, i.e. There are n i nodes mapped to module i where 1 i p c i Energy consumption per act of communication originated from module i where 1 i p C j

Total Energy consumption at node j during communication (either transmitting the packet originated from node j or relaying packets originated from other nodes) before the target system dies, where 1 j K OH j

The induced overhead in terms of energy consumption by the routing strategy RS at node j where 1 j K i

The normalized energy consumption of module i, which is defined as the total energy that module i (more precisely, all nodes mapped to module i) consumes before a job is completed Some parameters in Table 1 depend only on application and architecture. For instance, an encryption round (job) for the 128-bit AES (see With these notations, the problem of determining the routing strategy for performance maximization (in terms of number of completed jobs), under resource constraints, can be formulated as follows: Given:

Data flow of the target application, specifically p and f i 's Modules energy consumption per act of computation, E i 's The battery budget, B, and the node budget, K

Determine:

The optimal routing strategy which maximizes the number of jobs completed over all possible routing strategies; that is, ) ( max

) (RS RS J such that j j j j i RS i S j j p i i OH C x E B p i J f x K n i ) ( ) ( 1 , , 2 , 1 ,
where x j is the actual number of operations at node j before the target system dies and the subscript i(j) denotes the type of module that node j implements.

The first condition in the above formulation requires that the total number of nodes is less or equal to the maximum number of available nodes. The second condition ensures that J (RS) jobs are completed under the routing strategy RS. The last condition guarantees that the target system remains alive before J (RS) jobs are completed. Among all possible routing strategies, the one which satisfies these three conditions and maximizes the number of completed jobs represents the optimal solution.

Analytical Results on Routing Strategy

In this section, we derive an analytic upper bound on the achievable number of jobs completed over all routing strategies. To this end, we first construct the ideal routing strategy RS * which has the following features:

i. The topology of RS * is chosen to match the data flow of the target application. ii. The mapping from modules to nodes is considered optimal. Specifically, for each i, the number of duplicates of module i, n i , is optimal. Furthermore, for each i, we expand the domain of n i from positive integers to positive real numbers.

iii. An incomplete operation due to node battery depletion can, without incurring any cost, continue the remaining fraction of operation at a living node that performs the same functionality. iv. There is no overhead of the ideal routing strategy caused by the control mechanism. Feature i implies that RS * consumes the least amount of energy during communication. Feature ii ensures that the more power a module consumes, the higher proportion of nodes will be mapped to that module. Feature iii implies that the target system is alive as long as, for each module, there exists (at least) a live node mapped to that module.

Features i, iii and iv reduce the complex routing strategy problem to the problem of optimizing the number of nodes for each type of module. To complete a job, module i has to perform f i operations, each consuming E i + c i on computation and communication, so the energy consumption sums up to the normalized energy consumption, i = f i (E i + c i ). Since the target system under RS * dies when all nodes where some application module is mapped to become dead, the achievable number of completed jobs under an arbitrary routing strategy RS is where n is a vector defined as (n 1 ,n 2 ,…,n p ).

) 1 ( ) , , , ( max
Due to limited space, we state Theorem 1 without proof. Theorem 1: (Upper bound for the achievable number of completed jobs) Given the application parameters p and f i 's, the energy consumption for each module E i , the battery budget B and the node budget K, the maximum number of completed jobs is given by

) 2 ( 1 * p i i B K J
where i is the normalized energy consumption of module i. Furthermore, the optimal number of duplicates of modules i is given by

) 3 ( 1 * p j j i i K n
Theorem 1 not only gives a tight upper bound for the achievable number of completed jobs, but also reveals an important design rule: for each i, the optimal number n i * of duplicates of module i is proportional to the corresponding value of the normalized energy consumption, i .

Platform Description

Although our energy-aware routing strategy can be applied to any application, we focus on the AES cipher as an illustrative example of our work. For a fair comparison, the proposed energy-aware routing strategy and its non-energyaware counterpart are kept exactly the same except their routing algorithms which are the energy-aware routing algorithm (EAR) and the shortest-distance routing algorithm (SDR), respectively.

Energy Modeling

E-textile systems have to be tiny, light, flexible and slim so that they can be easily embedded into the fabric. Due to the above reasons, the novel thin-film battery [START_REF] Neudecker | Lithium-Free Thin-Film Battery with In Situ Plated Li Anode[END_REF][START_REF] Neudecker | Power Fibers: Thin-Film Batteries on Fiber Substrates[END_REF] is a good candidate for the attached battery on e-textile platforms. The battery modeling for the thin-film battery is addressed in this section. We also present the energy models of the computational modules and the transmission lines for the AES cipher on e-textiles. Using measured data, we find out that, for the AES cipher, the power consumed on the transmission lines is not negligible compared with the power consumed in the computational modules. This suggests that, for e-textiles, the remaining battery capacity, as well as the distances of routing paths should be considered when making the routing decisions.

AES Partitioning and Computation Energy Consumption

We outline the pseudo code of AES cipher in Fig 1 . For 128-bit AES, Nb=4 and Nr=10. Because of limited capability for raw processing and battery capacity, the whole system has to be partitioned into several modules. None of these modules should consume a large amount of power. Finally, the following partitioning scheme is used.

Module 1: SubBytes( ) / ShiftRows( ) Module 2: MixColumns( ) Module 3: KeyExpansion / AddRoundKey( ) We specified all these modules in Verilog and synthesized them with the Synopsys Design Compiler using a 0.16 m technology. While these modules can operate at clock frequencies up to 233MHz, the power consumption at 100MHz was measured. The energy consumption values, per act of computation, are E 1 =120.1pJ, E 2 =73.34pJ, E 3 =176.55pJ for modules 1, 2 and 3, respectively.

Electrical Characteristics of Transmission Lines and Communication Energy Consumption

The electrical characteristics of dedicated textile transmission lines of various lengths are extracted from [START_REF] Cottet | Electrical Characterization of Textile Transmission Line[END_REF]. The fabrics used contain polyester yarns that are twisted with one copper thread of 40 m diameter and are insulated with a polyesterimide coating. We performed SPICE simulations and found out that the energy consumption values, per bitswitching activity, are 0.4472pJ, 4.4472pJ, 11.867pJ and 53.082pJ for transmission lines of 1cm, 10cm, 20cm and 100cm, respectively. These values multiplied by the packet size represent the energy consumed on transmitting a packet over these transmission lines and are fed into our network simulator, et_sim. [START_REF] Neudecker | Lithium-Free Thin-Film Battery with In Situ Plated Li Anode[END_REF]. The discharging characteristic together with the discrete-time model in [START_REF] Benini | Discrete-Time Battery Models for System-Level Low-Power Design[END_REF] which closely approximates the behavior of its circuit-level continuous-time counterpart is implemented in our network simulator, et_sim. This way, the accuracy is acceptable (within 15%), since the actual capacity of any group cells may vary as much as 20% even between identical units [START_REF] Benini | Discrete-Time Battery Models for System-Level Low-Power Design[END_REF].

Battery Modeling

To reduce the simulation time, the initial (nominal) capacity of the thin-film battery is reduced to 60000pJ. We also assume that the corresponding discharging voltage profile shrinks proportionally in the horizontal direction. We assume that a node is dead after the output voltage of its attached battery drops below 3.0 Volts and the remaining energy stored in the attached battery is wasted.

Mapping the AES Application onto the Mesh Architecture

As Theorem 1 shows, the normalized energy consumption per module ( i ) is a key factor for the mapping from application modules to network nodes. Based on Theorem 1, a large number of nodes are mapped to module 3 which consumes the highest normalized energy among all three application modules.

Assuming any node with coordinates (x, y), our mapping strategy is to map that node to module 1 if m(x)+m(y)=2, to module 2 if m(x)+m(y)=0, and to module 3 if m(x)+m(y)=1 where m(x) is defined as x modulo 2. The shared communication medium is used only for exchanging the control information. Under the TDMA scheme, the width of shared medium can be very narrow, for instance, only 2-bit wide. In addition, compared with the significant performance gain (see Fig 7 in Sec 7), the percentage of energy consumed on the shared medium is small. Therefore, backing up the information sent over the shared medium, in case of potential failures, is feasible even under the strict resource constraints that characterize e-textile systems.

We include a deadlock recovery mechanism in the TDMA scheme: when a job stays at a node for more than a threshold period, that node needs to report the occurrence of deadlock during its next upload slot. The central controller sends then the new routing instruction to that node to redirect the job along an unlocked path during the next download phase. During the second phase, for all pairs of nodes, we compute the K-by-K shortest-path matrix D = [D ij ] and the Kby-K successor matrix S = S ij , for 1 i, j K, where K denotes the budget of nodes, D ij is the shortest distance from node i to node j, and S ij is the successor of node i along the shortest path to node j. A variation of the Floyd-Warshall algorithm of complexity O(n 3 ) (see [START_REF] Cormen | Introduction to Algorithms[END_REF]) is used to compute all-pairs shortest paths and their successors; the pseudo code is given in Fig 5 . In the pseudo code in Fig 5 , W is set to W (SDR) for SDR and is set to W (EAR) for EAR.

The third phase has to determine the destination node among the nodes which have the same functionality and avoid using the ports which are currently in a deadlock state. The pseudo code is shown in Fig 6.

The recovery from deadlock is ensured because of the ifbranch in line 5 of the pseudo code. The third phase yields a running time of O(n 2 ). This is because the total number of executions of line 5 is K (n 1 +n 2 +…+n p ) = K 2 . The hidden constant in the third phase is close to zero when few deadlock and/or congestion situations occur (see lines 5-8 in Fig 6). Even in case of severe deadlock/congestion, the hidden constant in the third phase is at most equal to that in the second phase. ) (

Fig 6: The 3rd phase of EAR and SDR algorithms

From the above arguments, we know that, for either EAR or SDR, the complexity is O(n 3 ), the hidden constants are small and most of the running time is spent in the second phase. Thus, EAR and SDR are practical for graphs consisting of tens to a few hundreds of nodes.

Experimental Results

To evaluate the performance gain that can be achieved under EAR, we simulate the AES cipher using mesh networks of various sizes. The results are compared with those obtained by using its non-energy-aware counterpart, SDR. The results are also compared with the analytical upper bound to illustrate how much room for further improvement still exists. In addition, multiple concurrent jobs are fed into the target system to see the effectiveness of the developed deadlock recovery mechanism.

A cycle-accurate network simulator, et_sim, was implemented. et_sim supports, in default mode, any 2D mesh network with the mapping technique described in Sec 5.2. Since many factors (e.g. energy consumed on computational components and on transmission lines, the discharging characteristics of batteries, etc) have a significant impact on the performance, et_sim models them accurately with their actual values (see Sec 5 for details).

EAR vs. SDR

Throughout Sec 7.1 to 7.2, it is assumed that a single central controller with infinite energy resource is deployed, and therefore the system dies when some critical node is dead. We will discuss how several central controllers with finite energy affect the system lifetime in Sec 7.3.

In this first set of experiments, a new job is launched when the previous one is completed. In other words, there is exactly one job in the target system and therefore no buffering at nodes is needed. As in Sec 5.1.3, the battery model is based on the discharging characteristics of a thin-film battery together with a discrete-time approximation. The performance data is collected when the target system becomes dead.

The experimental results of performance gain are shown in Fig 7 . It is observed that, EAR does better than SDR by a factor between 5 to 15 times, depending on the size of the network. Compared with the significant performance gain, the overhead caused by the control mechanism is very small: indeed, the percentage of energy consumed on exchanging the control information divided by the total energy consumption in 4x4, 5x5, 6x6, 7x7 and 8x8 mesh networks is only 2.8%, 3.1%, 4.1%, 9.3% and 11.6%, respectively.

EAR vs. Theoretical Upper Bound

In Table 2, the number of jobs completed under EAR are compared with the corresponding analytical upper bounds given by Theorem 1. For a fair comparison, the battery model of the Li-free thin-film battery is replaced with the ideal battery model which outputs constant voltage with 100% efficiency until depletion.

It can be observed in Table 2 that EAR achieves 44.5% to 48.2% of the maximum achievable number of completed jobs. The gap between EAR and the upper bound is due to a) the imperfect matching of the mesh topology and application flow, and b) the overhead caused by exchanging control information. Therefore, for all practical purposes, EAR performs much better than it appears from data in Table 2.

Effect of Controller Failures on System Lifetime

In this section, the effect of controller failures due to battery depletion is investigated. We designed in Verilog several central controllers for mesh networks of various sizes and measured their power consumption. For example, the controller of a 4x4 mesh network operating at 100MHz clock frequency consumes a dynamic power of 6.94mW and a leakage power of 0.57mW.

Plotted in Fig 8 are the simulation results for a different number of controllers, each controller having an attached battery as mentioned in Sec 5.1.3. The system lifetime is determined by either the lifetime of the AES nodes or the lifetime of the central controllers, whichever is smaller. For a fixed-sized mesh network, increasing of the number of controllers extends the system lifetime up to a threshold after which the lifetime of AES nodes becomes the dominant factor of the system lifetime. Given a fixed number of available controllers, the tails in Fig 8 are decreasing because a controller for a bigger mesh consumes more power than a controller for a smaller mesh.

Conclusion

In this paper, the issue of energy-aware routing in electronic textiles has been addressed. As main contributions, we have derived an analytical upper bound for routing and developed a general-purpose energy-aware routing algorithm, EAR, which considers the concrete limitations given by limited battery capacities, long wire effects, etc. For the AES cipher, EAR achieves approximately 50% of the analytical upper bound. Furthermore, in a mesh network with less or equal to 64 nodes, the performance gain of EAR over its nonenergy-aware counterpart ranges from 5 to 15 times, depending on the size of the network. It is expected that the performance gain will be even higher in larger networks.

Fig 1 )

 1 takes 10 operations of type Subbytes/Shiftrows, 9 operations of type Mixcolumns and 11 operations of type Addroundkey. Therefore f 1 , f 2 and f 3 are 10, 9 and 11 respectively. Other parameters, however, depend also on the routing algorithm and control mechanism. The induced overhead, OH j , and the total energy consumption during communication, C j , are such examples.

Fig 1 :

 1 Fig 1: The pseudo code of the AES cipher

Fig 2

 2 Fig 2 shows the discharge voltage profile of a Li-free thinfilm battery[START_REF] Neudecker | Lithium-Free Thin-Film Battery with In Situ Plated Li Anode[END_REF]. The discharging characteristic together with the discrete-time model in[START_REF] Benini | Discrete-Time Battery Models for System-Level Low-Power Design[END_REF] which closely approximates the behavior of its circuit-level continuous-time counterpart is implemented in our network simulator, et_sim. This way, the accuracy is acceptable (within 15%), since the actual capacity of any group cells may vary as much as 20% even between identical units[START_REF] Benini | Discrete-Time Battery Models for System-Level Low-Power Design[END_REF].To reduce the simulation time, the initial (nominal) capacity of the thin-film battery is reduced to 60000pJ. We also assume that the corresponding discharging voltage profile shrinks proportionally in the horizontal direction. We assume that a node is dead after the output voltage of its attached battery drops below 3.0 Volts and the remaining energy stored in the attached battery is wasted.

Fig 2 :

 2 Fig 2: Discharge curve of thin-film batteries (from [10])

Fig 3 :Fig 4 :

 34 Fig 3: (a) Network-based architectures, (b) The mapping of AES using a 4-by-4 mesh network 5.3 Control Mechanism A centralized control mechanism based on a time division multiple access (TDMA) scheme (see Fig 4) has been implemented. It consists of several active and idle centralized controllers, many AES nodes and a shared communication medium. The AES nodes periodically report their respective statuses to the central controllers during their own upload slots. The active central controllers figure out the routing paths for all nodes based on the reported information. After the routing paths are determined, the information about the next hops on routing paths is sent to corresponding regular nodes through the shared medium in the coming downloading phase. 1 2 3 4 5 6 1 2 3 4 5 6 uploading downloading Fig 4: TDMA scheme used to implement the control mechanism

Fig 5 :

 5 Fig 5: The 2 nd phase of EAR and SDR algorithms

Fig 7 :

 7 Fig 7: The number of completed jobs (EAR vs. SDR)

Fig 8 :

 8 Fig 8: The effect of the amount of central controllers on system lifetime in mesh networks of various sizes

Table 2 : Comparison between EAR and the upper bound

 2

		of jobs completed	Simulation results, J (EAR)	Theoretical upper bound, J *	( J EAR	)	J	*
	Network size	4x4 5x5 6x6 7x7 8x8	62.8 92 132.7 194 234	131.42 205.25 295.70 402.48 525.69	47.8% 44.8% 44.9% 48.2% 44.5%

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 research was supported in part by MARCO/DARPA Gigascale Systems Research Center (GSRC) under grant no. 2003-DT-660.

EAR and SDR Algorithms

The EAR algorithm and its shortest distance routing counterpart (SDR) have been developed to decide the routing paths on-line, based on the reported system information. Both of them have the capability of recovery from deadlock.

When the currently reported system information differs from the previous one, the central controller executes the routing algorithm in order to instruct the nodes on how to modify their routing tables. SDR generally selects the shortest path while EAR determines the path based on the reported battery information as well. Both of SDR and EAR are composed of three phases that will be detailed next.

In the first phase, for both SDR and EAR, a weight is assigned to each directed interconnect. The network topology is represented as a directed graph G = (V, E) where V is the set of vertices and E is the set of edges. For convenience, our algorithms use an adjacency-matrix representation. The edge weight matrix,

], of SDR is set to

where L ij is the length of the directed interconnect. One the other hand, the edge weight matrix

where N B (j) Z + is the reported battery level of node j, N B (j)<N B , and f( ) is a weighting function. In our

where Q > 0 is a constant to strengthen the impact of the battery information.


Nicolas P Rougier
email: nicolas.rougier@inria.fr

Behdad Esfahbod
email: behdad@behdad.org

Digital Typography Rendering 25 years of text rendering

Keywords: Computing methodologies → Rasterization, Non-photorealistic rendering, Text rendering, Bézier curves, shaders, typography, antialiasing, kerning, shaping, hinting, unicode

This short course (1h30) is an introduction to digital typography rendering, providing key concepts of typography as well as introducing several computer graphics techniques to render text, from the oldest and most common techniques (texture based) to the latest methods taking full advantage of shaders with quasi flawless rendering.

INTRODUCTION

Typography is the art of arranging type to make written language legible, readable, and appealing when displayed 1 . However, for the neophyte, typography is mostly apprehended as the juxtaposition of characters displayed on the screen while for the expert, typography means typeface, scripts, unicode, glyphs, ascender, descender, tracking, hinting, kerning, shaping, weigth, slant, etc. Typography is actually much more than the mere rendering of glyphs and involves many different concepts. If glyph rendering is an important part of the rendering pipeline as it will be explainded below, it is nonetheless important to have a basic understanding of typography or there's a known risk at rendering garbage on screen, as it has been seen many times in games, software and operating systems.

TYPOGRAPHY

With the widespread adoption of Unicode 2 as the canonical character set for representing text a whole new domain has been opened up in the system software design. Traditionally fonts were a collection of glyphs and a simple one-to-one mapping between characters and glyphs. Rudimentary support for simple ligatures was available in some font formats. With Unicode however there was a need for formats allowing complex transformation of glyphs (substitution and positioning). Two technologies were developed to achieve that, one is OpenType Layout from Microsoft and Adobe, the other is AAT from Apple. These two technologies, plus TrueType and Type1 font formats, all were combined in what is called OpenType.

1 According to Wikipedia 2 http://unicode.org There are fundamental differences in how AAT and OpenType Layout work. In AAT the font contains all the logic required to perform complex text shaping (the process of converting Unicode text to glyph indices and positions). Whereas in OpenType, the script-specific logic (say, Arabic cursive joining, etc) is part of the standard and implemented by the layout engine, with fonts providing only the font-specific data that the layout engine can use to perform complex shaping. The Free Software text stack is based on the OpenType Layout technology. HarfBuzz3 is an implementation of the OpenType Layout engine (aka layout engine) and the scriptspecific logic (aka shaping engine).

Such complex shaping and layouting poses new problem in term of rendering. If it is possible to cache glyphs on the GPU for simple languages (e.g. English), it is virtually impossible to do the same with complex layouts where a tremendous amount of composed glyphs can be created on the fly. New approaches are thus necessary to ensure fast, correct and just-in-time rendering.

RENDERING

Near the end of the last century, [START_REF] Kilgard | A Simple OpenGL-based API for Texture Mapped Text[END_REF]] introduced a simple OpenGL-based API for texture mapped text. The method packed many rasterized glyphs into a single alpha-only texture map and used a lookup table to assign texture coordinates to a quadrilateral to extract a glyph when rendering. This approach yielded several advantages over previous approaches (fixed size bitmap, stroke font) because it allowed arbitrary rotation, scaling and projection over 3D surface. More importantly, it allowed to have arbitrary shaped glyph that can be loaded directly from standard bitmap font files, such that font designers could work with standard tools instead of writing explicit code to render glyph shapes. The primary drawback of the method was that at high resolution, text became quite pixelated, even using bi-linear texture interpolation. To cope with this problem, [START_REF] Green | Improved Alpha-Tested Magnification for Vector Textures and Special Effects[END_REF]] refined the method by computing a (non-adaptive) signed distance field in place of the rasterized glyph that could later be alpha-tested or thresholded. [START_REF] Gustavson | OpenGL Insights[END_REF] showed that distance field can be computed efficiently. The method of [START_REF] Green | Improved Alpha-Tested Magnification for Vector Textures and Special Effects[END_REF]] differed from the one proposed by [START_REF] Frisken | Adaptively sampled distance fields[END_REF]] that was relying on an adaptive distance field and octree and did not take advantage of shader at the time of publication.

Unfortunately, at very high resolution, artifacts still appeared and it became necessary to use true vector font to achieve flawless rendering. Before the advent of programmable shaders, this was performed by approximating Bézier curves with many line segments, which was computationally expensive. However, [START_REF] Loop | Resolution Independent Curve Rendering Using Programmable Graphics Hardware[END_REF] introduced a new approach for resolution-independent rendering of quadratic and cubic spline curves. By tessellating a glyph the proper way, they offered de facto a method for resolution independent rendering of a glyph with good rendering quality (anti-aliased is also supported). A few years later, [START_REF] Esfahbod | Glyphy[END_REF]] refined the signed distance field method by using arc approximation of Bézier curves and encoding the required information into a texture, allowing the conservation of sharp angles at any resolution. More recently, [START_REF] Kilgard | GPU-Accelerated Path Rendering[END_REF] proposed a two-steps method (stencil and cover) for GPU-accelerated path rendering as an OpenGL extension. As stated by the authors, their goals are completeness, correctness, quality, and performance, the extension actually covers most of the OpenVG specifications while giving very high performances. In the meantime, [START_REF] Rougier | Higher Quality 2D Text Rendering[END_REF]] proposed a method for 2d rendering achieving best possible result with subpixel rendering and positioning in the screen space. Two years ago, [START_REF] Chlumsky | Shape Decomposition for Multi-channel Distance Fields[END_REF]] made a breakthrough by proposing a multichannel signed distance field method that was able to render sharp angles (smoothed out corners is quite characteristic of the regular signed distance field method). Last, but not least, two new methods have been introduced last year by [START_REF] Walton | Path Finder[END_REF]] and [START_REF] Lengyel | GPU-Centered Font Rendering Directly from Glyph Outlines[END_REF]] respectively. The former is currently tested for a future integration in the Quantum rendering engine used by Firefox while the latter has been integrated into the slug library. They both achieved fast and beautiful rendering and may have nearly solved the glyph rendering problem... Until a new technique appears.

COURSE OVERVIEW

This 1h30 course has been split in two parts: one part introducing key concepts in digital typography as well as the related software stack (necessary libraries to read and use font information) and the second part about the various computer graphics techniques for rendering glyphs on screen.

•

  Part I: Introduction (25mn) • Part II: Texture based rendering (20mn) • Part II: Distance based rendering (20mn) • Part II: Geometry based rendering (20mn) • Conclusion (5mn)

https://www.freedesktop.org/wiki/Software/HarfBuzz/


Yuh-Fang Tsai

Vijaykrishnan Narayaynan

Yuan Xie

Mary Jane Irwin

Leakage-Aware Interconnect for On-Chip Network

On-chip networks have been proposed as the interconnect fabric for future systems-on-chip and multi-processors on chip. Power is one of the main constraints of these systems and interconnect consumes a significant portion of the power budget. In this paper, we propose four leakage-aware interconnect schemes .Our schemes achieve 10.13%~63.57% active leakage savings and 12.35%~95.96% standby leakage savings across schemes while the delay penalty ranges from 0% to 4.69%.

INTRODUCTION

While Network-on-Chip (NoC) is becoming an attractive alternative to the traditional global interconnect structure to address the design challenges of future high-performance nanoscale architectures, power consumption remains a significant constraint. In the deep sub-micron era, the interconnect wires and associated driver circuits consume an increasing fraction of the energy budget of the system. Given that there are plenty of techniques proposed to reduce the leakage power in memory structures such as buffers and the effectiveness of applying those techniques in router buffers have been proven [START_REF] Chen | Leakage Power Modeling and Optimization in Interconnection Networks[END_REF], we focus on low leakage crossbar designs in this work. In [START_REF] Deogun | Leakage-and Crosstalk-Aware Bus Encoding for Total Power Reduction[END_REF], bus encoding technique is developed so that leakage reduction is achieved through selective use of high threshold voltage transistors in the buffers (staggered threshold buffers). In this paper, we apply similar staggered threshold voltage buffers in the crossbar designs.

The rest of the paper is organized as follows. In the next section, the proposed leakage-aware interconnect designs and microarchitectural enhancements on the schemes are presented. The evaluations and experimental results are in Section 3 while the conclusions in Section 4.

LEAKAGE-AWARE INTERCONNECT

Daul-V t Feedback Crossbar (DFC)

Fig. 1 shows the dual-Vt feedback crossbar (DFC) switch with output driver of one output port. To manage the leakage power in standby mode, a sleep transistor N 5 which is controlled by sleep signal is added. This sleep transistor is shared by all the bits in a flit and it incurs negligible area overhead since wires dominate the area. While a router will be idle for a given amount of idle time, the sleep signal is set to HIGH and node A is pulled to GND level reducing the gate leakage of the pass transistors (N 1 -N 4 ).

Dual-V t Pre-Charged Crossbar (DPC)

The main idea of DPC is to have interconnects that have smaller delay time for one polarity of data than the other. By doing so, the output driver can be designed with asymmetric V t transistors to favor the speed of the other polarity of data. To achieve this, we pre-charge the output wire to a predefined state, V dd in our example, so that it has virtually zero delay time for data in logic 1 state. To balance the delay time, instead of sizing the inverters in drivers asymmetrically, we use asymmetric-V t leakage-aware inverters. Fig. 2 shows an example of the output to PE port of one case where a node is pre-charged to HIGH in DPC. A simple implementation is to pre-charge the output wires by transistor P 1 in the negative phase of the clock signal eliminating the delay penalty for low to high transition. When there is no request sent to the arbiter from all the input buffers or when in sleep mode, the pre-charge signal (pre) is deactivated to prevent switching power penalties.

Segmented Dual-V t Feedback Crossbar (SDFC)

Fig. 3(a) shows the segmented dual-Vt feedback crossbar (SDFC). As can be seen, the path 1 (bold solid line) has smaller capacitive and resistive loads as compared to path 2 (dashed line). This provides longer slack for transitions through path 1 than that through path 2. The longer slack removes more transistors from the critical path, allowing designers to use high V t transistors. This scheme not only adds more high Vt transistors but also results in higher probability that some segments of the wires can be put in standby mode.

Segmented Dual-V t Pre-Charged Crossbar (SDPC)

An example of the pre-charged to high SDPC is shown in Fig. 3(b). The longer slack in the paths in the shaded area allows all transistors in their output drivers to be of high V t . Moreover, the use of pre-charge transistors eliminates the threshold voltage drop limitation of using pass transistors and thus no level restoration requirement.

EXPERIMENTS AND RESULTS

We implemented the proposed schemes for a 5-by-5 matrix crossbar design with 128 bits per flit in 45nm technology. The interconnect properties, such as wire pitch, space, aspect ratio, and dielectric material parameters, are based on the ITRS roadmap [START_REF]International Technology Roadmap for Semiconductors[END_REF]. We predict the interconnect resistance and capacitance by the interconnect model of Berkeley Predictive Technology Model (BPTM) [START_REF]Berkeley Predictive Technology Model and BSIM4[END_REF]. Except the proposed schemes, the scheme SC, whose circuit is the same as the DFC except for using a single nominal V t , is also implemented as the base case.

Simulation results are summarized in Table 1. It is intuitive that the inclusion of high V t device saves both active and standby leakage power. As compared to DFC and SDFC, DPC and SPDC offer significantly higher standby leakage savings which are 93.68% and 95.96%, respectively. This is because their output drivers are in the resulting minimum leakage state in standby mode in DPC and SDPC. Switching to standby mode incurs a switching power penalty, however. We define the Minimum Idle Time shown in Table 1 as the minimum amount of time that a circuit stays in idle so that the leakage saved in standby mode is more than the switching power penalty. We would like to note that by segmenting the crossbar, not only is dynamic power mitigated but the leakage power is further reduced by 20% and 30% in SDFC and SDPC, respectively. This is achieved by our microarchitectural improvement in the output driver designs.

Besides, segmentation also increases the chance for a segment to be put in the standby mode for maximum leakage savings.

CONCLUSIONS

As existing interconnect designs in on-chip network draws significant leakage power, we proposed several dual-V t designs to reduce both active and standby leakage. The DFC saves 10.13% of active leakage and 12.36% of standby leakage while DPC saves 43.7% of active leakage and 93.68% of standby leakage at no delay penalty. Optimizing the interconnect structure by segmenting the interconnect and properly assigning the high V t transistors reduce the leakage further by 30% more in SDFC. DPC and SDPC target to systems which have major data transfers within the same polarity.

Figure 1 .Figure 2 .

 12 Figure 1. Schematic of output to PE direction path of DFC.N

Figure 3 .

 3 Figure 3. Segmented dual-Vt (a) feedback crossbar (b) pre-charged crossbar design.

Table 1 . Summary of simulation results for evaluated crossbar schemes. Note: * The power consumptions are obtained by assuming 50% static probability which is the worst case for power. **The savings and penalty are the results compared against results of SC.

 1

	SC	DFC	DPC	SDFC	SDPC

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

This work was supported in part by MARCO/DARPA GSRC Grant, NSF 0093085, and NSF 0202007.