Guowu Yang

William N N Hung

Xiaoyu Song

Marek Perkowski

Exact Synthesis of 3-qubit Quantum Circuits from Non-binary Quantum Gates Using Multiple-Valued Logic and Group Theory

We propose an approach to optimally synthesize quantum circuits from non-permutative quantum gates such as Controlled-Square-Root-of-Not (i.e. Controlled-V). Our approach reduces the synthesis problem to multiple-valued optimization and uses group theory. We devise a novel technique that transforms the quantum logic synthesis problem from a multi-valued constrained optimization problem to a group permutation problem. The transformation enables us to utilize group theory to exploit the properties of the synthesis problem. Assuming a cost of one for each two-qubit gate, we found all reversible circuits with quantum costs of 4, 5, 6, etc, and give another algorithm to realize these reversible circuits with quantum gates.

Introduction

In this paper, we propose a novel approach to optimally synthesize quantum circuits by group theory where the primary inputs are binary basis states (outputs are not necessarily binary, they may be random binary after measurement of superposition states). Finding the smallest number of gates to synthesize a reversible circuit does not necessarily result in a quantum implementation with the lowest cost (in terms of quantum gates) [START_REF] Hung | Quantum Logic Synthesis by Symbolic Reachability Analysis[END_REF]. The exact minimal costs for NMR [START_REF] Nielsen | Quantum Computation and Quantum Information[END_REF] realization of several quantum gates from truly quantum (not permutative) gates such as Pauli Rotations or Controlled-Square-Root-of-Not have been calculated [START_REF] Lee | Costs of basic gates in quantum computation[END_REF]. They can be also calculated for other quantum technologies. We focus on synthesizing reversible circuits to quantum implementations with the lowest cost. The method is general and enumerative. It can be adapted to any particular numerical values of costs. These circuits include common reversible gates that can be used at higher levels of logic synthesis or for technology mapping. We formulate the quantum logic synthesis problem via group theory. Our method guarantees to find the minimum quantum-cost implementation with truly quantum gates (given a set of specified component gates). In contrast to previous works, which either use permutative reversible gates to design permutative circuits or universal quantum gates to design quantum circuits, we use a subset of quantum gates to design permutative binary circuits that can be either deterministic (when output symbols are restricted to basis binary states) or probabilistic (when there is no such constraint imposed on the output symbols).

Formulation

We briefly describe our problem formulation in this section. Further details of our formulation can be found in our technical report [START_REF] Yang | Exact Synthesis of 3-qubit Quantum Circuits from Nonbinary Quantum Gates using Multiple Valued Logic and Group Theory[END_REF].

We are interested in synthesizing quantum circuits using elementary quantum gates: NOT gates, XOR (controlled-NOT) gates, controlled-V gates and controlled-V + gates. In order to use Group Theory, we need to encode the input values. Given our elementary quantum gates, there are four possible values [START_REF] Hung | Quantum Logic Synthesis by Symbolic Reachability Analysis[END_REF] for each qubit: 0, 1, V 0 , and V 1 . We represent quantum states as permutations (of truth table entries), and quantum gates as permutations as well. The outputs of quantum gates are simply permutations on permutations. For each gate, we construct a banned set as a filter to extract reasonable truth table entries. A banned set N A , for example, is the set of all entries in which the value of the controlling qubit A is V 0 or V 1 , because only binary values are allowed to be used for control bits.

We constructed a Finding Algorithm (see technical report [START_REF] Yang | Exact Synthesis of 3-qubit Quantum Circuits from Nonbinary Quantum Gates using Multiple Valued Logic and Group Theory[END_REF] for details) to compute the reversible circuit set G[k] of all reversible circuits which have cost k. The idea is to create a set A[k] of all quantum circuits that can be constructed using k or less quantum gates. B[k] is the set of quantum circuits that can be constructed using k (and at least k) quantum gates. We create pre_G For arbitrary n-qubit reversible circuits, we use N to denote the group realized by NOT gate. The size of N is 2 n , for all a N, a*a=( ), and for all a,b N, a*b=( ) iff a=b.

Let G be the set of all n-qubit reversible circuits realized by control gate and Feynman gate. Let H be the set of all n-qubit reversible circuits realized by control gate, Feynman gate and NOT gate. We can deduce that H can be evenly decomposed to 2 n leftcosets of G without intersection, shown in the following theorem. Based on the Finding Algorithm and Theorem 2, we formulate an Expressing Algorithm [START_REF] Yang | Exact Synthesis of 3-qubit Quantum Circuits from Nonbinary Quantum Gates using Multiple Valued Logic and Group Theory[END_REF]. An important property of the Expressing Algorithm is that if the quantum cost of g does not exceed the bound cb, then the Expresssing Algorithm will return d

[0], d[1], …, d[t] such that g = d[0]*d[1]*…*d[t]
and t is minimum.

Experiments

We applied our minimum cost algorithm to 3 qubit synthesis; the results are shown in the following 540 4320 For cost up to 3: G [START_REF] Nielsen | Quantum Computation and Quantum Information[END_REF], G [START_REF] Hung | Quantum Logic Synthesis by Symbolic Reachability Analysis[END_REF] and G [START_REF] Yang | Exact Synthesis of 3-qubit Quantum Circuits from Nonbinary Quantum Gates using Multiple Valued Logic and Group Theory[END_REF] consists of the set of the binary input binary output circuits which are the combinations of 1, 2, 3 Feynman gates respectively. In G [START_REF] Lee | Costs of basic gates in quantum computation[END_REF], there are 60 circuits realized by 4 Feynman gates, the other 24 circuits realized by 3 control gates and 1 Feynman gate. And these 24 circuits exhibit a property of universal gates: all 3-bit binary input and binary output reversible circuits can be realized by NOT gates, Feynman gates and any one of these 24 circuits. There are four representative circuits from these 24 circuits. Each of these four circuits has other five similar circuits with different permutations of the three bits.

Our algorithm can be used to synthesize a quantum circuit from a specified circuit. We applied our algorithm to synthesize the well known Peres and Toffoli circuits. It took 9 CPU seconds (on a 850MHz Pentium® III) to synthesize the Peres circuit (cost=4) and 98 seconds for the Toffoli circuit (cost=5).

Our synthesis algorithm found two implementations for Peres. For the Toffoli circuit, we found four quantum implementations. Notice that for runtime performance our algorithm does not intend to find all possible implementations of the specified circuit. It only finds some implementations as the synthesis result.

Details of our experiments can be found in our technical report [START_REF] Yang | Exact Synthesis of 3-qubit Quantum Circuits from Nonbinary Quantum Gates using Multiple Valued Logic and Group Theory[END_REF].

Conclusion

In this paper we formulated a method to exactly minimize a subset of quantum circuits by reducing the problem to multiple-valued logic and group theory. As far as we know, this is the first time that such a combined approach has been proposed. Using this method we found many new gates and inexpensive realizations of permutative quantum circuits. For instance, we found a family of Peres-like gates which have all the same lowest cost and can be used to synthesize permutative quantum circuits (section 4). Not only is the Peres gate the cheapest of all NMR realized permutative gates, but we show that there is a large family of such gates with the same smallest possible cost, for which nobody has developed a synthesis method yet. Our method can also be used to synthesize circuits with binary inputs and superposed quantum output states. Because such output states are converted in "quantum measurements" to randomly generated vectors with known probabilities [START_REF] Nielsen | Quantum Computation and Quantum Information[END_REF], our method is then without any modification a new approach to synthesize a class of binary-input circuits that have random but controlled binary outputs (we remove the constraint that outputs are binary states).

  [k]={b'| b'=Restrictedperm(b,S), b [k]}, where b(S)=S means if the input pattern is binary, then its output is also a binary pattern. So the circuit b' is a reversible circuit with cost k. We create the set G[k] by subtracting G[k-1], …, G[1] from pre_G[k] because when we compute the b'=Restrictedperm(b, S) circuit, b' may potentially be a member of any G[j], j<k. Theorem 1. G[k] is the set of all reversible circuits that fulfill our input/output constraints and have minimum quantum cost = k without using NOT gate.

Theorem 2 :

 2 H= a N a*G, and a,b N (a b) (a*G) (b*G)= .

  table.

	Cost k	|G[k]|	|S 8 [k]|
	0	1	8
	1	6	4 8
	2	30	240
	3	52	416
	4	84	672
	5	156	1248
	6	398	3184
	7

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


Irith Pomeranz

Sudhakar M Reddy

Worst-Case and Average-Case Analysis of n-Detection Test Sets

Test sets that detect each target fault n times (n-detection test sets) are typically generated for restricted values of n due to the increase in test set size with n. We perform both a worst-case analysis and an average-case analysis to check the effect of restricting n on the unmodeled fault coverage of an (arbitrary) n-detection test set. Our analysis is independent of any particular test set or test generation approach. It is based on a specific set of target faults and a specific set of untargeted faults. It shows that, depending on the circuit, very large values of n may be needed to guarantee the detection of all the untargeted faults. We discuss the implications of these results.

Introduction

Under an n -detection test set, each target fault is detected n times, by n different test vectors. If a fault has fewer than n different test vectors that detect it, all its test vectors are included in an n -detection test set. The motivation for the use of n -detection test sets is that by increasing the number of detections of target faults, the likelihood of detecting unmodeled faults and defects is increased as well. In addition, generation of n -detection test sets for a specific fault model requires only minor modifications to a test generation procedure for the same fault model. This is typically simpler than writing a test generation procedure for a new fault model. Generation of n -detection test sets and their advantages in detecting unmodeled faults and defects were studied in [START_REF] Ma | An Experimental Chip to Evaluate Test Techniques Experiment Results[END_REF]- [START_REF] Venkataraman | An Experimental Stud of n -Detect Scan ATPG Patterns on a Processor[END_REF].

Determining a value for n is typically done based on tester memory and test application time constraints. Since the size of a compact n -detection test set increases approximately linearly with n , n ≤ 10 appears to have become the accepted bound on n . Several questions arise when n is restricted. (1) How much unmodeled fault or defect coverage is missed by restricting n . (2) How much higher should n be in order to eliminate the fault or defect coverage loss. The latter is important in deciding whether higher values of n should be considered.

A model for estimating the defective part level after the application of a given test set was given in [START_REF] Grimaila | REDO -Random Excitation and Deterministic Observation -First Commercial Experiment[END_REF] and [START_REF] Dworak | Enhanced DO-RE-ME based Defect Level Prediction using Defect Site Aggregation-MPG-D[END_REF].

The model is based on the numbers of times fault sites are activated and observed by the test set, which are improved by n -detection test generation. This model can provide answers to the questions above with respect to a given test set. However, it was not used for providing general answers that are independent of the test set or the test generation procedure used. In addition, to answer the second question it would be necessary to perform test generation for increasing values of n , and the bound on n is unknown a-priori.

In this work we investigate a method of analysis to answer both questions in a way that is independent of any particular test set or test generation procedure. We perform the analysis by considering a specific set of target faults for n -detection test generation (single stuck-at faults), and a specific set of untargeted faults (four-way bridging faults [START_REF] Sengupta | Defect-Based Tests: A Key Enabler for Successful Migration to Structural Test[END_REF], [START_REF] Krishnaswamy | A Study of Bridging Defect Probabilities on a Pentium (TM) 4 CPU[END_REF]). The four-way bridging fault model was used for developing manufacturing tests for static defects in industrial designs [START_REF] Krishnaswamy | A Study of Bridging Defect Probabilities on a Pentium (TM) 4 CPU[END_REF], [START_REF] Chakravarty | Experimental Evaluation of Scan Tests for Bridges[END_REF]. Bridging faults were also used earlier as surrogates for unmodeled defects in estimating the defect coverage obtained by a given test set [START_REF] Grimaila | REDO -Random Excitation and Deterministic Observation -First Commercial Experiment[END_REF], [START_REF] Dworak | Enhanced DO-RE-ME based Defect Level Prediction using Defect Site Aggregation-MPG-D[END_REF]. The questions we answer become the following. (1) How much untargeted fault coverage (coverage of four-way bridging faults) is missed by restricting n . (2) How much higher should n be in order to ensure that all the untargeted faults (all the four-way bridging faults) are detected.

We investigate both a worst-case analysis and an average-case analysis to answer these questions. The worst-case analysis assumes that if it is possible to generate an n -detection test set that will fail to detect an untargeted fault, such a test set will be generated. The average-case analysis provides the probabilities that an arbitrary n -detection test set will detect untargeted faults. The worst-case analysis and its results are described in Section 2. The average-case analysis and its results are described in Section 3. The results of Sections 2 and 3 are analyzed in Section 4, and additional results, using a stricter definition of an n -detection test set, are presented to support the analysis.

Worst-case analysis

Let F = {f 0 ,f 1 , . . . ,f k -1 } be the set of faults for which n -detection test generation is carried out (the set of target faults). Let G = {g 0 ,g 1 , . . . ,g m -1 } be the set of faults through which the n -detection test set is evaluated (the set of untargeted faults). Our goal in this section is to obtain (1) the number of faults in G that are guaranteed to be detected by an n -detection test set for F ; and (2) the minimum value of n required to guarantee that all the detectable faults in G will be detected.

We base the analysis on the set U of all the input vectors of the circuit. For every fault h i ∈ F ∪G , T (h i ) ⊆ U is the set of test vectors that detect h i . The analysis based on the set of all the input vectors can be done only for circuits with small numbers of inputs. At the end of Section 4 we discuss how the proposed analysis can be used for large designs.

We first illustrate the analysis using the example circuit shown in Figure 1. We use the set of collapsed single stuck-at faults as the set F , and the set of four-way bridging faults as the set G . The fault line l stuck-at a is denoted by l /a . A four-way bridging fault is denoted by (l 1 ,a 1 ,l 2 ,a 2 ). The fault is activated when l 1 = a 1 and l 2 = a 2 . It then results in l 1 = a 1 in the faulty circuit. We use the decimal representation of the input vectors to represent U . For the circuit of Figure 1 we have U = {0,1, . . . ,15}.

The bridging fault g 0 = (9,0,10,1) is detected by the set of input vectors T (g 0 ) = {6,7}. In the first three columns of Table 1 we show all the single stuck-at faults in F that are detected by at least one of the input vectors 6 and 7, and the set T (f i ) for every such fault f i . Considering f 0 = 1/1 with T (f 0 ) = {4,5,6,7}, we note that it is possible to detect f 0 twice, using test vectors 4 and 5, without detecting g 0 . A third detection of f 0 will require that either input vector 6 or input vector 7 will be included in the test set, thus guaranteeing that g 0 will be detected. Considering f 1 = 2/0 with T (f 1 ) = {6,7,12,13,14,15}, it is possible to detect f 1 four times, using test vectors 12, 13, 14 and 15, without detecting g 0 . A fifth detection of f 1 will guarantee that g 0 will be detected. In general, for a fault g j ∈ G , let F (g j ) ⊆ F be the subset of faults such that T (f i ) ∩ T (g j ) ≠ φ for every f i ∈ F (g j ). Let N (f i ) be the size of T (f i ), and let M (g j ,f i ) be the size of the intersection T (f i ) ∩ T (g j ). We can detect f i N (f i )-M (g j ,f i ) times without detecting g j . If the number of detections of f i is increased to N (f i )-M (g j ,f i )+1, g j is guaranteed to be detected. We denote N (f i )-M (g j ,f i )+1 by n min (g j ,f i ). This is the minimum value of n for which detection of f i guarantees detection of g j . Considering all the faults in F (g j ), we define n min (g j ) = min{n min (g j ,f i ):f i ∈ F (g j )}. This is the minimum number of detections n that guarantees detection of g j by an n -detection test set for F .

In Table 1 we show the values of n min (g 0 ,f i ) considering all the faults in F (g 0 ). Based on the information given in Table 1, we have n min (g 0 ) = 3. Thus, in order to guarantee that an arbitrary n -detection test set will detect g 0 , n must be larger than or equal to three.

Results of the computation of n min (g j ) for the combinational logic of MCNC finite-state machine benchmarks are shown in Tables 2 and3 (at the end of the paper). In Table 2 we are interested in faults out of G that are guaranteed to be detected by any n -detection test set for n ≤n max . Here, n max is a constant for which it is practical to generate an n -detection test set (n max = 10 in our experiments). In Table 3 we are interested in faults out of G that require large values of n to guarantee that they will be detected by an n -detection test set. We report in Table 3 on faults that are guaranteed to be detected by an ndetection test set only if n >n max . We only include in Table 3 circuits for which such faults exist.

Table 2 is organized as follows. After the circuit name we show the number of four-way bridging faults considered (detectable non-feedback four-way bridging faults between outputs of multi-input gates). Under column n min (g j )≤n min 0 we show the percentage of faults g j ∈ G such that n min (g j ) ≤ n min 0 . This is the percentage of faults for which an n -detection test set that guarantees their detection requires n ≤ n min 0 . If n = n min 0 results in 100% coverage of four-way bridging faults, we do not report on higher values of n . For example, bbara has 858 faults in G . Of these faults, 80.42% require n min (g j ) = 1 to guarantee their detection, i.e., they will be detected by any 1-detection test set; 84.85% of the faults require n min (g j ) ≤ 2 to guarantee their detection, i.e., they will be detected by any 2-detection test set; 97.55% of the faults are guaranteed to be detected by any 10-detection test set.

Table 3 is organized as follows. After the circuit name we show the number of four-way bridging faults considered. Under column n min (g j )≥n min 0 we show the number (and the percentage in parentheses) of faults g j ∈ G such that n min (g j ) ≥ n min 0 . This is the number (or percentage) of faults for which an n -detection test set that guarantees their detection must be computed for n ≥ n min 0 . For example, considering bbara , none of the faults in G requires n min (g j ) ≥ 100 to guarantee its detection. Three faults require n min (g j ) ≥ 20, and 21 faults require n min (g j ) ≥ 11 (which is 2.45% of the faults in G ).

From Tables 2 and3 it can be seen that large percentages of the faults in G will be detected by any ndetection test set for n = 1, and very large percentages will be detected by any n -detection test set for n = 10. Nevertheless, there are non-trivial numbers of faults that are not guaranteed to be detected by a 10-detection test set. For the last seven circuits in Table 3, even n = 100 is not sufficient to guarantee the detection of all the faults in G . We show the distribution of n min (g j ) for dvram in Figure 2, considering faults for which n min (g j ) ≥ 100.

Average-case analysis

The analysis in Section 2 is a worst-case analysis since it assumes that as long as n is low enough to allow a fault g j ∈ G to escape detection, a test for g j will not be included in an n -detection test set. In practice, this worst case may not happen. Our goal in this section is to obtain the probabilities of detecting the faults in G by an arbitrary n -detection test set, for different values of n . We construct several n -detection test sets randomly for n = 1,2, . . . ,n max using Procedure 1 given below. Procedure 1 constructs K test sets T 0 ,T 1 , . . . ,T K -1 for every value of n . Initially, T k = φ for 0 ≤ k < K . Procedure 1 performs n max iterations where it considers every test set. At the end of iteration n , T k is an n -detection test set, for 0 ≤ k < K . In iteration n , Procedure 1 considers every fault f i ∈ F . For 0 ≤ k < K , if f i is detected by T k fewer than n times, and T (f i ) contains tests that are not included in T k (i.e., T (f i )-T k ≠ φ), Procedure 1 selects a test randomly out of T (f i )-T k , and adds it to T k . Procedure 1: Constructing n -detection test sets (1) For k = 0,1, . . . ,K -1, set T k = φ. Set n = 1.

(2) For every f i ∈ F :

For every test set T k , k = 0,1, . . . ,K -1:

(a) Find the number of times f i is detected by

T k . Let this number be n i ,k . (b) If n i ,k < n and T (f i )-T k ≠ φ: Select a test t ∈ T (f i )-T k randomly. Add t to T k . (3) Set n = n +1. If n ≤ n max , go to Step 2.
Using the test sets T 0 , . . . ,T K -1 produced by Procedure 1 for every value of n , we estimate the probability that an arbitrary n -detection test set will detect a fault g j ∈ G as follows. For every n -detection test set T k such that g j is detected by T k (i.e., T (g j ) ∩ T k ≠ φ), we increment a count d (n ,g j ) by one. We define the probability of detecting g j by an arbitrary n -detection test set as p (n ,g j ) = d (n ,g j )/K .

For illustration, we consider the example circuit of Figure 1. In Table 4 we show n -detection test sets for n = 1 and 2. For each value of n we have K = 10 test sets. We consider the fault g 6 with T (g 6 ) = {12}. For this fault, n min (g 6 ) = 4. For n = 1, the set T (g 6 ) has a nonempty intersection with T 5 and T 7 . We obtain d (1,g 6 ) = 2 and p (1,g j ) = 0.2. For n = 2, the set T (g 6 ) has a nonempty intersection with T 0 , T 4 , T 5 and T 7 . We obtain d (2,g 6 ) = 4 and p (2,g j ) = 0.4. We computed p (n ,g j ) using K = 10000 test sets for n = 1,2, . . . ,n max where n max = 10. We report the results considering only faults g j that are not guaranteed to be detected by a 10-detection test set, and considering only circuits that have such faults. In addition, we only report the results for n = 10 (the detection probabilities for lower values of n are lower). The results are shown in Table 5 (at the end of the paper). After the circuit name we repeat the number of faults that are not guaranteed to be detected by a 10-detection test set (the number of faults with n min (g j ) ≥ 11). We then show the numbers of faults for which the probability of detection p (10,g j ) is at least 1, 0.9, 0.8, . . . , 0.1, 0. We do not enter a number for a given probability if all the faults have a higher probability of detection. The fault with the lowest probability for ex 2 has p (10,g j ) = 0.052. The two faults with the lowest probabilities for bbsse have p (10,g j ) = 0.093 and 0.091. The fault with the lowest probability for cse has p (10,g j ) = 0.043.

From Table 5 it can be seen that some of the faults in G , that are not guaranteed to be detected by a 10detection test set, have very high probabilities of being detected by such a test set. However, there are also nontrivial numbers of faults with lower probabilities. These faults may be left undetected by a 10-detection test set. Increasing n to detect such faults may sometimes require very high values of n as can be seen from Table 3. Overall, the average-case analysis is consistent with the worst-case analysis in pointing to the existence of untargeted faults that are not likely to be detected by a 10detection test set.

Discussion

The results of the previous sections indicate the following.

An n -detection test set for a reasonable value of n (around n = 10) is guaranteed to detect a high percentage of the untargeted faults, and will detect most of the remaining untargeted faults with a high probability. However, there are also faults that are likely to escape detection by an n -detection test set. The values of n required for such faults can be very high. Thus, increasing n is not likely to be an effective solution for improving the effectiveness of an n -detection test set.

In some situations the small loss in untargeted fault coverage may be acceptable. When it is not, direct test generation for additional fault models can be carried out. Alternatively, methods to improve the effectiveness of an n -detection test set can be used. To illustrate this point we use an alternate method to generate n -detection test sets, based on a different definition of an n -detection test set. The definition we used so far is the standard one. For completeness, we repeat this definition next. Definition 1: Let T be a test set where no test is duplicated. A fault f is detected n times by T if T contains n tests that detect f . Under the alternate definition from [START_REF] Pomeranz | Definitions of the Numbers of Detections of Target Faults and their Effectiveness in Guiding Test Generation for High Defect Coverage[END_REF], two tests that detect a target fault f are required to be sufficiently different in order to be counted as different detections of f . The definition given in [START_REF] Pomeranz | Definitions of the Numbers of Detections of Target Faults and their Effectiveness in Guiding Test Generation for High Defect Coverage[END_REF] is the following. Definition 2: Let T be a test set where no test is duplicated. A fault f is detected n times by T if there exist n tests t 1 ,t 2 , . . . ,t n in T such that the following condition is satisfied. For every i and j such that 1 < i ≤ n and 1 ≤ j < i , let t ij be the test which is specified in bits where t i and t j are specified to the same value, and unspecified in other bits. The test t ij does not detect f . Definition 2 simulates f under a test t ij that contains the common bits of t i and t j . If these bits are sufficient for detecting f , then the two tests t i and t j are considered similar, and are not counted as two detections of f . If t ij does not detect f , then t i and t j are considered sufficiently different, and they are counted as different detections of f . We use Definition 2 in Procedure 1 for the construction of n -detection test sets as follows. When we find the number of detections n i ,k of a fault f i under a test set T k , we use Definition 2 to compute n i ,k . If n i ,k < n , we find the tests out of T (f i )-T k that, if added to T k , will be counted as different detections of f i according to Definition 2. If the number of detections of f i cannot reach n according to Definition 2, we use Definition 1 instead. This is done to avoid situations where faults are detected much fewer than n times.

Results of average-case analysis based on Definition 1 and based on Definition 2 are shown in Table 6. In this case we used K = 1000 test sets for the analysis. On the first row for every circuit we show the results obtained using Definition 1, and on the second row we show the results obtained using Definition 2. We target the same set of faults in both cases.

Table 6 demonstrates that Definition 2 can improve the quality of an n -detection test set by increasing the probability that an untargeted fault will be detected by the test set. For example, out of the 474 four-way bridging faults with n min (g j ) ≥ 11 in the circuit keyb , 381 faults are detected with probability greater than or equal to 0.8 by a standard 10-detection test set generated using Definition 1, whereas 440 faults are detected with probability greater than or equal to 0.8 if the test set is generated using Definition 2. The probabilities of detection given in Tables 5 and6 can be used to calculate the probability that an untargeted fault escapes detection.

As noted earlier, the analysis proposed requires information regarding which targeted and untargeted faults are detected by each input vector of the circuit, and hence can be directly used for circuits with small numbers of inputs. However, as the data in Table 6 shows, the analysis can be used to evaluate the relative effectiveness of different n -detection test generation methods. Additionally, one can partition a larger circuit into smaller subcircuits and apply the analysis to the subcircuits. Such analysis can be used to evaluate the effectiveness of a chosen value of n , and to estimate the probability of untargeted faults escaping detection.

Concluding remarks

In order to restrict the test set size, n -detection test sets are typically generated for restricted values of n . We addressed the following questions related to this restriction. (1) How much unmodeled fault or defect coverage is missed by restricting n . (2) How much higher should n be in order to eliminate the fault or defect coverage loss. Our analysis was independent of any particular test set. We used single stuck-at faults as target faults, and fourway bridging faults as untargeted faults for the purpose of this study. We used both a worst-case analysis and an average-case analysis to provide answers for these questions. The worst-case analysis assumed that if it is possible to generate an n -detection test set that will fail to detect an untargeted fault, such a test set will be generated. The average-case analysis provided the probabilities for an arbitrary n -detection test set to detect untargeted faults.

Figure 1 :

 1 Figure 1: Example circuitIn general, for a fault g j ∈ G , let F (g j ) ⊆ F be the subset of faults such that T (f i ) ∩ T (g j ) ≠ φ for every f i ∈ F (g j ). Let N (f i ) be the size of T (f i ), and let M (g j ,f i ) be the size of the intersection T (f i ) ∩ T (g j ). We can detect f i N (f i )-M (g j ,f i ) times without detecting g j . If the number of detections of f i is increased to

Figure 2 :

 2 Figure 2: Distribution of n min (g j ) for dvram

Table 1 : Faults with test vectors that overlap with

 1

	i	f i	T (f i )	n min (g 0 ,f i )
	0 1/1	4 5 6 7	3
	1 2/0	6 7 12 13 14 15	5
	3 3/0	2 6 7 10 14 15	5
	9 8/0	2 6 10 14	4
	11 9/1	0 1 2 3 4 5 6 7 8 9 10 11	11
	12 10/0	6 7 14 15	3
	14 11/0	1 2 3 5 6 7 9 10 11 13 14 15	11

T (g 0 ) = {6,7}

Table 4 : Test sets for example circuit

 4

	k	n=1	T k n =2
	0	6 8 10 13	2 5 6 8 10 12 13 14
	1	0 2 7 11 13	0 2 4 5 7 9 10 11 13 14
	2	3 6 8 13	3 4 5 6 8 9 11 13 14 15
	3	4 5 11 14 15	0 3 4 5 9 10 11 14 15
	4	5 6 8 10 15	2 5 6 8 9 10 12 15
	5	0 5 7 9 10 11 12 0 5 6 7 9 10 11 12 14
	6	4 8 9 11 14 15	4 5 8 9 10 11 14 15
	7	1 3 4 6 8 12	1 3 4 6 8 9 10 12 13 14
	8	3 5 7 8 9 13 14	3 4 5 7 8 9 10 13 14
	9	2 5 6 8 9 15	2 4 5 6 8 9 10 14 15

Table 2 : Worst-case percentages of detected faults (small n )

 2

					n min (g j )≤
	circuit	faults	1	2	3	4	5	1 0
	lion	23 100.00
	dk27	218	83.03 100.00
	ex5	1287	92.07 100.00
	train4	8	75.00 100.00
	bbtas	155	89.68	94.84 100.00
	dk15	1544	97.99	99.42 100.00
	dk512	1127	92.72	99.91 100.00
	dk14	3694	90.80	97.64	99.97 100.00
	dk17	1244	94.21	98.95	99.92 100.00
	firstex	288	83.33	97.57	99.65 100.00
	lion9	182	79.67	89.56	96.15 100.00
	mc	356	87.08	92.42	96.35 100.00
	dk16	40781	92.90	98.75	99.61	99.94 100.00
	modulo12	448	63.62	84.82	93.30	99.11 100.00
	s8	294	59.18	70.41	95.24	99.32 100.00
	tav	176	51.14	73.86	88.64	92.05 100.00
	donfile	11956	85.95	97.58	98.59	99.37	99.79 100.00
	ex7	1358	90.65	97.05	99.26	99.34	99.34 100.00
	train11	482	69.92	80.08	92.95	99.59	99.79 100.00
	beecount	804	89.30	97.39	98.51	98.76	99.25	99.75
	ex2	11499	90.30	96.54	98.57	99.41	99.78	99.99
	ex3	2104	86.26	95.01	98.95	99.62	99.76	99.86
	ex6	4051	94.20	94.20	95.51	95.51	98.52	99.61
	mark1	2469	89.67	89.83	92.99	93.20	94.53	95.95
	bbara	858	80.42	84.85	89.28	89.51	92.31	97.55
	ex4	2038	88.86	88.86	89.99	89.99	93.57	95.98
	keyb	20894	88.27	91.17	93.61	93.99	95.03	97.73
	opus	1901	79.22	83.96	89.90	92.00	93.42	97.42
	bbsse	4265	89.14	89.14	89.17	89.17	92.19	95.97
	cse	9110	93.61	93.61	95.16	95.16	98.25	99.13
	dvram	14737	88.78	88.78	88.78	88.78	88.78	88.78
	fetch	8958	92.10	92.10	92.10	92.10	92.10	92.10
	log	4290	95.36	95.36	95.36	95.36	95.36	95.36
	rie	24150	95.04	95.04	95.04	95.04	95.04	95.04
	s1a	49524	84.34	84.34	84.59	84.59	85.68	88.02

Table 3 : Worst-case numbers of detected faults (large n )

 3

				n min (g j )≥
	circuit	faults	100	20		11
	beecount	804	0 (0.00)	0	(0.00)	2	(0.25)
	ex2	11499	0 (0.00)	0	(0.00)	1	(0.01)
	ex3	2104	0 (0.00)	0	(0.00)	3	(0.14)
	ex6	4051	0 (0.00)	0	(0.00)	16	(0.39)
	mark1	2469	0 (0.00)	0	(0.00)	100	(4.05)
	bbara	858	0 (0.00)	3	(0.35)	21	(2.45)
	ex4	2038	0 (0.00)	19	(0.93)	82	(4.02)
	keyb	20894	0 (0.00)	206	(0.99)	474	(2.27)
	opus	1901	0 (0.00)	4	(0.21)	49	(2.58)
	bbsse	4265	2 (0.05)	38	(0.89)	172	(4.03)
	cse	9110	2 (0.02)	37	(0.41)	79	(0.87)
	dvram	14737 1256 (8.52) 1653 (11.22) 1653 (11.22)
	fetch	8958	688 (7.68)	708	(7.90)	708	(7.90)
	log	4290	199 (4.64)	199	(4.64)	199	(4.64)
	rie	24150 1136 (4.70) 1197	(4.96) 1197	(4.96)
	s1a	49524	258 (0.52) 4260	(8.60) 5934 (11.98)

Table 5 : Average-case probabilities of detection

 5

	p (10,g j )≥

Table 6 : Average-case probabilities of detection under Definitions 1 and 2

 6

	p (10,g j )≥

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)

1. Research supported in part by SRC Grant No. 2004-TJ-1244. 2. Research supported in part by SRC Grant No. 2004-TJ-1243.


Chuan-Yue Yang

Jian-Jia Chen

Tei-Wei Kuo

An Approximation Algorithm for Energy-Efficient Scheduling on A Chip Multiprocessor *

In the recent decade, voltage scaling has become an attractive feature for many system component designs. In this paper, we consider energy-efficient real-time task scheduling over a chip multiprocessor architecture. The objective is to schedule a set of frame-based tasks with the minimum energy consumption, where all tasks are ready at time 0 and share a common deadline. We show that such a minimization problem is NP-hard and then propose a 2.371-approximation algorithm. The strength of the proposed algorithm was demonstrated by a series of simulations, for which near optimal results were obtained.

Introduction

With the increasing popularity and prevailing supports on voltage scaling for electronic circuits, energy efficiency has become a highly important design issue in hardware and software implementations [START_REF] Chen | Segmented bus design for low-power systems[END_REF][START_REF] Gutnik | Embedded power supply for lowpower DSP[END_REF][START_REF] Jone | Design theory and implementation for low-power segmented bus systems[END_REF][START_REF] Pedram | Power Aware Design Methodologies[END_REF]. The design of electronic circuitry is usually done such that a higher supply voltage would result in a higher execution speed (or a higher frequency). An example power consumption function [START_REF] Chandrakasan | Lower-power CMOS digital design[END_REF][START_REF] Weiser | Scheduling for reduced CPU energy[END_REF], as follows, shows the power consumption of a processor as a function of the processor speed:

P (s) = C ef V 2 dd s ( 1
)
where s = k h ((V dd -V t ) 2 )/V dd , and P, s, C ef , V t , V dd , and k h denote the power consumption, the processor speed, the effective switch capacitance, the threshold voltage, the supply voltage, and a hardware-design-specific constant, respectively (V dd ≥ V t ≥ 0, k h > 0, and C ef > 0). Modern superscalar processors achieve excellent performance through pipelined instruction executions and concurrent services of independent instruction streams. Further performance improvement is often done by increasing the processor frequency but at the cost of energy consumption. When energy consumption and system performance must be considered at the same time, the multiprocessor architecture seems being a reasonable choice, especially for multiprogramming environments (e.g., [START_REF] Nikitovic | An adaptive chip-multiprocessor architecture for future mobile terminals[END_REF]). The chip-multiprocessor architecture is proposed as an attempt to overcome the chipspace constraint and the processor communication delay problem for the multiprocessor architecture. With a slight increasing on the die size, multiple processors, i.e., cores, are mounted on a single die to retain many advantages of the multiprocessor architecture but with only comparatively low wire delay. While many excellent research results have been proposed for uniprocessor energy-efficient scheduling, e.g., [START_REF] Aydin | Dynamic and aggressive scheduling techniques for power-aware real-time systems[END_REF][START_REF] Chen | Profit-driven uniprocessor scheduling with energy and timing constraints[END_REF][START_REF] Ishihara | Voltage scheduling problems for dynamically variable voltage processors[END_REF][START_REF] Mejía-Alvarez | Adaptive scheduling server for power-aware real-time tasks[END_REF][START_REF] Yao | A scheduling model for reduced CPU energy[END_REF][START_REF] Yun | On energy-optimal voltage scheduling for fixed-priority hard real-time systems[END_REF], little work has been done for multiprocessor systems, e.g., [START_REF] Chen | Multiprocessor energy-efficient scheduling with task migration considerations[END_REF][START_REF] Gruian | System-level design methods for low-energy architectures containing variable voltage processors[END_REF][START_REF] Zhang | Task scheduling and voltage selection for energy minimization[END_REF], even though the multiprocessor architecture has become increasingly popular in various platforms. The strong demand for multiprocessor energyefficient scheduling is not only from server systems but also from the embedded systems, such as System-on-Chip systems. In particular, power saving on the chip multiprocessor architecture received much attention recently, especially due to its applications to embedded systems. For example, the adaptive chip-multiprocessor (ACMP) architecture proposed in [START_REF] Nikitovic | An adaptive chip-multiprocessor architecture for future mobile terminals[END_REF] allows each core to switch its operation mode among RUN, STANDBY, and DORMANT in a dynamic manner to reduce the energy consumption.

Real-time task scheduling over a chip multiprocessor with the capability of dynamic voltage scaling (abbreviated as DVS-CMP) is exploited in this paper. The DVS-CMP architecture explored in this paper has M homogeneous cores, where each core could be dormant independently, and all nondormant cores must operate at the same voltage supply. The objective of this research is to schedule a set of frame-based tasks with the minimum energy consumption on a DVS-CMP processor, where all tasks are ready at time 0 and share a common deadline. We show that such a scheduling problem is NP-hard and propose a 2.371-approximation algorithm. The strength of the proposed algorithm is demonstrated by a series of simulations, for which we have near optimal results. The rest of this paper is organized as follows: Section 2 presents related work on energy-efficient scheduling. In Section 3, we formally define the problem under considerations. An approximation algorithm was proposed for energyefficient scheduling in Section 4. Simulation results are shown in Section 5 to evaluate the capability of the proposed algorithm. Section 6 is the conclusion.

Related Work

Energy-efficient scheduling has been an active research topic in the past decade. Although many excellent results have been proposed for uniprocessor real-time task scheduling, e.g., [START_REF] Aydin | Dynamic and aggressive scheduling techniques for power-aware real-time systems[END_REF][START_REF] Chen | Profit-driven uniprocessor scheduling with energy and timing constraints[END_REF][START_REF] Ishihara | Voltage scheduling problems for dynamically variable voltage processors[END_REF][START_REF] Mejía-Alvarez | Adaptive scheduling server for power-aware real-time tasks[END_REF][START_REF] Yao | A scheduling model for reduced CPU energy[END_REF][START_REF] Yun | On energy-optimal voltage scheduling for fixed-priority hard real-time systems[END_REF], little work is done for multiprocessor systems so far. However, with the strong raising of the market for various multiprocessor architectures and their variations, multiprocessor energy-efficient scheduling has started receiving much attention in recent years, e.g., [START_REF] Anderson | Energy-efficient synthesis of periodic task systems upon identical multiprocessor platforms[END_REF][START_REF] Chen | Multiprocessor energy-efficient scheduling with task migration considerations[END_REF][START_REF] Gruian | System-level design methods for low-energy architectures containing variable voltage processors[END_REF][START_REF] Gruian | Lenes: Task scheduling for low energy systems using variable supply voltage processors[END_REF][START_REF] Zhang | Task scheduling and voltage selection for energy minimization[END_REF][START_REF] Mishra | Energy aware scheduling for distributed real-time systems[END_REF][START_REF] Zhu | Scheduling with dynamic voltage/speed adjustment using slack reclamation in multi-processor realtime systems[END_REF]. In particular, Chen, et al. [START_REF] Chen | Multiprocessor energy-efficient scheduling with task migration considerations[END_REF] proposed an approximation algorithm for multiprocessor energyefficient scheduling over a set of independent frame-based tasks, where all tasks share the same deadline. Gruian proposed a simulated annealing (SA) approach and a list-based heuristic algorithm with a dynamic priority assignment policy for the considerations of precedence constraints [START_REF] Gruian | System-level design methods for low-energy architectures containing variable voltage processors[END_REF][START_REF] Gruian | Lenes: Task scheduling for low energy systems using variable supply voltage processors[END_REF]. Mishra, et al. [START_REF] Mishra | Energy aware scheduling for distributed real-time systems[END_REF] explored scheduling issues over the communication delay for tasks. Zhu, et al. [START_REF] Zhu | Scheduling with dynamic voltage/speed adjustment using slack reclamation in multi-processor realtime systems[END_REF] explored on-line scheduling for a set of independent/dependent frame-based tasks. Given an off-line schedule with the worst-case task execution times, on-line strategies were proposed to reclaim the slacks resulted from the early completion times of tasks.

Although some research work has been proposed for multiprocessor energy-efficient scheduling, many previous results considered multiprocessor scheduling in which each processor can operate independently at its own processor speed. In this research, we are interested in a DVS-CMP architecture, in which there are M given homogeneous cores, where each core could be dormant independently, and all nondormant cores must operate at the same voltage supply. Our objective is to schedule a set of frame-based tasks with the minimum energy consumption on the given DVS-CMP processor, where all tasks are ready at time 0 and share a common deadline. The work done by Anderson and Baruah [START_REF] Anderson | Energy-efficient synthesis of periodic task systems upon identical multiprocessor platforms[END_REF] is related to our research in this paper. They proposed algorithms for the synthesizing of a multiprocessor hard-realtime system with independent periodic tasks and exploited the trade-offs between the number of processors in the system and the energy consumption. Different from their work, we aim at scheduling for the energy consumption minimization on a DVS-CMP processor with a fixed number of cores.

Problem Definition

In this paper, we exploit energy-efficient scheduling on a chip multiprocessor equipped with M homogeneous cores. The power consumption function in [START_REF] Chandrakasan | Lower-power CMOS digital design[END_REF][START_REF] Weiser | Scheduling for reduced CPU energy[END_REF], i.e., Formula 1, is adopted in this paper, where V t = 0, or V dd >> V t . The power consumption function can be rephrased as P (s) = αs 3 , where α is a constant. The available processor speeds for the DVS-CMP under considerations are assumed being adjustable in a continuous manner, and no upper bound on the processor speed is given (that is as the same as that in [START_REF] Irani | Algorithms for power savings[END_REF][START_REF] Yao | A scheduling model for reduced CPU energy[END_REF]). Furthermore, let the overheads on the switching of the supply voltage be negligible. Suppose that any of the cores could be turned into a sleep mode (i.e., s = 0) at any time, but all of non-sleeping cores must operate at the same processor speed. Let the energy consumed for a core at the processor speed s for t time units be P (s)t, and the execution of an amount c (in cycles on a core) of computation at the processor speed s take c/s time units. The energy-efficient scheduling problem to be explored in this paper could be defined as follows:

Definition 1 Energy Consumption Minimization for DVS-CMP Scheduling (ECMS):

Consider a set T of independent tasks on a DVS-CMP, where all tasks in T are ready at time 0 and share a common deadline D. Let each task τ i ∈ T be associated with an amount c i (in cycles on a core) of computation requirements.

The objective of this problem is to minimize the energy consumption in the scheduling of tasks in T without violating the common deadline D, where task migration between any two cores is not permitted.

A schedule of an input instance for the ECMS problem is a mapping of the executions of the tasks in the set to cores on the DVS-CMP with speed assignments and their corresponding time intervals. A schedule is feasible if no task misses the common deadline D, and the DVS-CMP constraints are not violated. Let Φ(Ψ) denote the energy consumption of a schedule Ψ. A schedule is optimal if it is feasible and its energy consumption is the minimum energy consumption of all feasible schedules.

The Proposed Algorithm

Energy Consumption Minimization with Tasks Being Partitioned

In this subsection, we shall propose a scheduling algorithm in energy consumption minimization when tasks are already partitioned. A task assignment is defined as a partition of T into M disjoint subsets X ≡ def {X 1 , X 2 , . . . , X M }. A schedule that is based on X must have tasks in X i ∈ X running on the i-th core. An optimal X-based schedule is a schedule that has the minimum energy consumption among X-based schedules. The load X i of each X i ∈ X is defined as the total amount of the computation requirements of the tasks in X i , and the load distribution X of X is denoted as {X 1 , X 2 , . . . , X M }. Without losing the generality, let X i ∈ X be sorted in a non-decreasing order of their loads. For the simplicity of discussions, let X M+1 = ∞ and X 0 = 0. A schedule Ψ satisfies the deep sleeping property if a core µ is in the sleep mode at any time t for t < t < D when µ is found in the sleep mode at some time 0 ≤ t < D. Lemma 1 For any task assignment X, there exists an optimal X-based schedule that satisfies the deep sleeping property.

Proof.

Given a feasible X-based schedule ψ that does not satisfy the deep sleeping property, let the time interval (0, D] of ψ be divided into disjoint time fragments such that the processor speeds of non-sleeping cores are different between any two different consecutive time fragments. (Note that the processor speeds of all non-sleeping cores are the same in each fragment by the definitions of DVS-CMP discussed in this paper). Let time fragments that have the same processor speed be merged together such that (0, D] have k fragments, and each t i of the fragments has a processor speed s i . Without losing of generality, we let 0 < s 1 < s 2 < • • • < s k . Let y i,j denote the number of core cycles needed for the j-th core of the i-th fragment, and |t i | denote the total duration of the i-th fragment (note that each fragment might consist of non-consecutive time intervals). ψ is a schedule derived from ψ as follows: The j-th core executes tasks at the speed We shall turn the resulted schedule ψ into another schedule ψ that satisfies the deep sleeping property: Let t be the earliest time moment that some core µ j goes into the sleep mode in ψ. Let n be the index which satisfies

s i in ( i-1 h=1 |t h |, i-1 h=1 |t h |+y i,j /s i ] for i = 1, 2, . . . , k and is turned into the sleep mode in ( i-1 h=1 |t h | + y i,j /s i , i h=1 |t h |] for i = 1,
n-1 h=1 |t h | ≤ t < n h=1 |t h |.
Suppose that µ j is non-sleeping at some time moment t , where t < t < D. Let Y be the total number of cycles executed after t on the core µ j (for all fragments). These Y cycles on µ j are then executed in the fragments starting from t n at their corresponding speeds (t n+1 , etc) from the time moment t until all of the Y cycles are done. The amount of consumed energy is less in the transformation, due to the convexity of the power consumption function. By repeating the same process for every core, we can always transform a feasible X-based schedule into one that satisfies the deep sleeping property and consumed no more energy than the original one does.

Based on the deep sleeping property, we can derive an optimal schedule based on a given task assignment X, as shown in Algorithm 1. Xi ← Xi + cj for ∀τj ∈ Xi;

4: L ← È M i=1 (Xi -Xi-1) 3 √ M -i + 1 and t0 ← 0; 5: for i = 1 to M do 6: si ← L 3 √ M -i+1 and ti ← ti-1 + D (X i -X i-1 ) 3 √ M -i+1 L ; 7:
let Ψ turn the i-th core into the sleep mode at ti and set the speed as si in (ti-1, ti] for the non-sleeping cores; 8: return Ψ by executing tasks assigned to each core in an arbitrary order;

Lemma 2 For any given task assignment X, the X-based schedule derived by Algorithm 1 is optimal.

Proof. Let the energy consumption for the schedule derived by Algorithm 1 be E * , where 3 . We shall show that any X-based schedule Ψ (that satisfies the deep sleeping property) consumes no less energy than E * . Let z 0 be the index such that X j is equal to 0 for all z 0 ≥ j ≥ 0. z i is recursively defined as the index such that X j is equal to X zi-1+1 for all z i ≥ j > z i-1 and i ≥ 1. Besides, let k the index such that z k = M . y i is defined to be X zi -X zi-1 for all i ≥ 1.

E * = α D 2 ( M i=1 (X i - X i-1 ) 3 √ M -i + 1)
Let β i be the time instant when the (z i-1 + 1)-th core is turned into sleep (β 0 = 0) for Ψ. Due to the deep sleeping property, there are (Mz i-1 ) cores that are non-sleeping in (β i-1 , β i ], and z i-1 cores are sleeping in (β i-1 , β i ]. Note that X i 's ∈ X are sorted in a non-decreasing order of their loads. γ i is defined as β iβ i-1 . Because of the convexity of the power consumption function, executing y i cycles at the same speed yi γi for γ i time units is the best choice for energy consumption. Therefore, Φ(Ψ) ≥ α k i=1 (Mz i-1 )( yi γi ) 3 γ i . Furthermore, there must exist at least one core that is not in the sleeping mode before D unless there is no load for any core (because the speed lower bound of each core is 0). Let Φ(X) be the energy consumption of an optimal X-based schedule. We have

Φ(X) ≥ min È k i=1 γi=D α k i=1 (M -z i-1 )( y i γ i ) 3 γ i (2)
By adopting the Lagrange multiplier method, the right-hand side of Equations ( 2) is minimized when

γ i = D • 3 M -z i-1 y i k j=1
We have 1

Φ(Ψ) ≥ Φ(X) ≥ α D 2 ( k i=1 yi 3 Ô M -zi-1) 3 = α D 2 ( M i=1 (Xi -Xi-1) 3 Ô M -i + 1) 3 = E * ≥ Φ(X). (3)
Since E * = Φ(X), we reach the conclusion. Let X be any given load distribution of T . A schedule is based on X if the number of cycles executed on the i-th core is equal to X i . Let the minimum energy consumption among schedules based on X be Φ(X). We have the following corollary:

Corollary 1 Φ(X) = α D 2 ( È M i=1 (Xi -Xi-1) 3 √ M -i + 1) 3 .

A 2.371-Approximation Algorithm

We shall first show the NP-hardness of the ECMS problem and then propose a 2.371-approximation algorithm.

Corollary 2

The ECMS problem is NP-hard.

Proof. Based on Equation

(3) in Lemma 2, Φ(Ψ) is mini- mum if and only if X j = È τ i ∈T ci M
for j = 1, 2, . . . , M. This problem could be reduced from the multiprocessor scheduling problem [SS8] in [START_REF] Garey | Computers and intractability: A guide to the theory of NP-completeness[END_REF], that is NP-complete.

The proposed 2.371-approximation algorithm (Algorithm LTF), as shown in Algorithm 2, adopts the Largest-Task-First strategy to partition T into M disjoint sets. Tasks are considered in a non-increasing order of their computation requirements. For the simplicity of discussions, let T be sorted in a non-increasing order of the computation requirements of tasks (where ties could be broken arbitrarily).

Algorithm 2 : LTF

Input: (T, D, M);

Output: A feasible schedule Ψ LT F with minimal energy consumption; 1: sort all tasks in a non-increasing order of the computation requirements of tasks; 2: Xi ← φ and Xi ← 0 for i = 1 to M ; Xm ← Xm + {τi} and Xm ← Xm + ci; 6: reorder Xi by a non-decreasing order of their loads and let X LT F ← {X1, X2, . . . , XM }; 7: return the resulted schedule Ψ LT F by applying MES(X LT F ); Let T, D, and M denote the task set under discussions, its common deadline, and the number of cores, respectively. Algorithm LTF always assigns a task to the core with the smallest load, where tasks are picked up in a non-increasing order of their computation requirements. The seeking of the core with the smallest load could be done by the manipulation of 1 The detail proof is omitted due to the space limitation.

a heap data structure. The time complexity of Algorithm LTF is O(|T |(log |T | + log M ) + M ), which is dominated by the cost for task sorting and heap manipulation.

Given a task set T (with D as the common deadline) and the number M of cores, Ψ LT F , X LT F , and X LT F denote the schedule, the task assignment, and the load distribution derived by Algorithm LTF, respectively. For the simplicity of discussions, let us renumber cores such that elements in X LT F be sorted in a non-decreasing order of their loads. That is, X LT F i ≤ X LT F i+1 for 1 ≤ i < M, where X LT F i denotes the i-th element in X LT F , and X LT F i is the load of X LT F i . For the abbreviation, X LT F i is also referred to as p i .

Lemma 3 Given two load distributions X and X for the same task set, Φ(X) < Φ(X ) if there exist two indices i and j

(j > i) such that X k = X k for k = i, j, and 0 < X i -X i < min{X i -X i-1 , X j+1 -X j }.

Proof.

Based on Corollary 1,

Φ(X) = α D 2 ( È M k=1 (X k -X k-1 ) 3 √ M -k + 1) 3 and Φ(X ) = α D 2 ( È M k=1 (X k -X k-1 ) 3 √ M -k + 1) 3 , respectively. Φ(X) < Φ(X ) because M k=1 (X k -X k-1 ) 3 Ô M -k + 1 - M k=1 (X k -X k-1 ) 3 Ô M -k + 1 = k=i,j ((X k -X k ) 3 Ô M -k + 1 -(X k -X k ) 3 Ô M -k) = (Xi -X i )[( 3 Ô M -i + 1 -3 Ô M -i) -( 3 Ô M -j + 1 -3 Ô M -j)] < 0.
When p 1 = 0, Algorithm LTF always generates an optimal schedule because no core is associated with more than one task. For the rest of this section, suppose that p 1 = 0. We first derive an upper bound on Φ(Ψ LT F ) for any schedule Ψ LT F derived by Algorithm LTF and then a lower bound on the optimal energy consumption for T (regardless of which algorithm is adopted). Let mk = |{i | p i ≤ k • p 1 }|, and P k = mk i=1 p i for some real k ≥ 1. X LT F (k) = {p 1 , p2 , . . . , pM } is revised based on X LT F by load redistribution as follows:

1. pi ← p i if i > mk ; 2. pi ← p 1 if k• mk p1-P k p1(k-1) ≥ i ≥ 1; 3. pi ← k • p 1 if mk ≥ i ≥ k• mk p1-P k p1(k-1) + 1; 4. pi ← P k -p 1 ( k• mk p1-P k p1(k-1) -1) -k • p 1 ( mk - k• mk p1-P k p1(k-1) ) if i = k• mk p1-P k p1(k-1)
.

Lemma 4

The minimum energy consumption to schedule tasks based on X LT F (k) is no less than that based on X LT F for any real k ≥ 1.

Proof. Initially, let X = X LT F . We could repeat the following revision procedure of X until i ≥ j (where i and j are the smallest and the largest indices which satisfy X i > p 1 and

X j < kp 1 , respectively): X i ← X i -δ and X j ← X j + δ, where δ ← min{X i -p 1 , kp 1 -X j }.
The final load distribution X would be as the same as X LT F (k) after a finite number of the above procedure applied. Based on Lemma 3, Φ(X LT F (k)) ≥ Φ(X LT F ).

For the simplicity of representation, we denote k• mk p1-P k p1(k-1)

as χ. We have the following inequality:

Φ(X LT F (k)) ≤ α D 2 [ 3 √ M p1 + 3 Ô M -χ(k -1)p1 + M i= mk +1 (pi -pi-1) 3 √ M -i + 1] 3 , ( 4
)
where the inequality comes from the following inequality:

3 M -χ (p χ -p1 ) + 3 M -χ (p mk -p χ ) ≤ 3 √ M -χ(k -1)p 1 . Let T = {τ i | c i ≥ È |T | j=i+1 cj M-i }.
We shall show that one core will be selected to service only one task in T , regardless of whether X LT F or an optimal task assignment X OP T is considered. When a task τ j / ∈ T is considered in Algorithm LTF (i.e., Steps 3-5), there must exist a core m * whose load p m * is no more than c i for any τ i ∈ T . Therefore, no other task will be assigned to any core occupied by any τ i ∈ T by Algorithm LTF. Consider any task assignment X derived by some algorithm. If some task τ i ∈ T and some other task τ j are assigned on the same core where c i ≥ c j , another task assignment X could always be generated by moving τ j to another core m where X m < c i . The optimal X -based schedule consumes less energy than that based on X. Thus X must not be the optimal task assignment. Therefore, one core will be selected to service only one task in T for an optimal task assignment X OP T . Let X OP T = {q 1 , q 2 , . . . , q M } be the load distribution for an optimal solution. Note that m k = |{i | p i ≤ k • p 1 }|. We could prove the following lemma.

Lemma 5 If k = 2, then q mk +i = p mk +i , for all 1 ≤ i ≤ M -mk .

Proof. Let j be the largest index for a core to which a task τ n ∈ T -T is assigned, and

τ n ∈ X LT F j . Let the last task inserted into X LT F j be τ r . Since c n < È |T | j=|T |+1 cj M-|T | , |X LT F j | ≥ 2.
It is clear that c r ≤ p 1 and p jc r ≤ p 1 . Therefore, p j ≤ 2p 1 . Since X LT F h > 2p 1 for any h > m2 , we have j ≤ m2 . Furthermore, we know that q j+i = p j+i , for all 1 ≤ i ≤ Mj.

Note that P k = mk i=1 p i , where mk is defined by X LT F (k). Similar to the definition of X LT F (k), we define XOP T (k) as an adjusted load distribution according to X OP T by re-distributing mk i=1 q i so that q1 = q2 = • • • = q mk = È mk i=1 qi mk . Similar to the proof in Lemma 4, we have Φ(X OP T ) ≥ Φ( XOP T (k)) for any k ≥ 1. We conclude this section by showing the following theorem.

Theorem 1 Algorithm LTF has a 2.371-approximation ratio for the ECMS problem.

Proof. The approximation ratio A LT F is:

A LT F = Φ(X LT F ) Φ(X OP T ) ≤ Φ(X LT F (2)) Φ( XOP T (2)) ≤ (( 3 √ M + 3 √ M -χ) p1 + È M i= m2 +1 ( pi -pi-1 ) 3 √ M -i + 1) 3 ( 3 √ M q1 + 3 Ô M -m2 (2 p1 -q1 ) + È M i= m2 +1 ( pi -pi-1 ) 3 √ M -i + 1) 3 ≤ (( 3 √ M + 3 √ M -χ) p1 ) 3 ( 3 √ M q1 + 3 Ô M -m2 (2 p1 -q1 )) 3 ≤ ( ( 3 √ M + 3 Ö L-M p1 p1 ) p1 3 √ M L M ) 3 , ( 5
)
where L is q1 m2 + 2p 1 (M -m2 ). Note that q1 m2 = m2 i=1 q i = P 2 . We have L = χp 1 +2p 1 (M -χ). Let f (x) be defined as f (x) =

( 3 √ M + 3 √ K-Mx x )x 3 √ M K M
for any rational number K where x • a + 2x • (Ma) = K for some non-negative rational number a. By solving the equation f (x) = 0, where f (x) < 0, we have

f (x) ≤ 4 3 , ( 6
)
where the maximal value stands when x = 8K 9M . According to Equations ( 5) and ( 6), we have A LT F ≤ ( 43 ) 3 < 2.371.

Simulation Results

The purpose of this section is to provide performance evaluation of Algorithm LTF. Algorithm RAND was also simulated for reference, where the Algorithm RAND greedily assigned a task to any core with the minimum load without sorting tasks. The relative energy consumption ratio, which was defined as Φ(Ψ LT F ) Φ(Ψ OP T ) , was adopted as the performance metric, where Ψ OP T is an optimal schedule for the ECMS problem. Ψ OP T can be obtained via an exhaustive search with a branch and bound strategy. When |T | was a large number, the relaxed relative energy consumption ratio, which was defined as Φ(Ψ LT F ) Φ( XOP T (2)) (please refer to Section 4 for the definition of XOP T (k)) was adopted as the performance metric. By definitions, Φ( XOP T (2)) can be obtained in an efficient manner 2 .

D was set as any arbitrary positive rational number in the simulations. The amount of cycles c i for a task τ i was generated randomly in the range (0, D]. The power consumption function P (s) was s 3 . 100 independent simulations were run for each parameter configuration. When the results were for the average relative energy consumption ratio, their results were averaged. When they were for the maximum relative energy consumption ratio, the maximum value was returned. Figure 1(a) and (b) show the average and maximum relative energy consumption ratios for the simulated algorithms, when the number of cores ranged from 3 to 8, and the task set size ranged from 10 to 15. Figure 1(c) and (d) show the average and maximum relaxed relative energy consumption ratios for the simulated algorithms, when the number of cores ranged from 8 to 32, and the task set size ranged from 50 to 100. The maximum and average relative energy consumption ratios for Algorithm LTF were less than 1.36 and 1.07 respectively. Furthermore, the maximum and average relaxed relative energy consumption ratios for Algorithm LTF were less than 2.00 and 1.44, respectively.

Conclusion

In this paper, we explore real-time energy-efficient scheduling on a chip multiprocessor with dynamic voltage scaling. We consider frame-based task sets, in which all tasks are ready at time 0 and share a common deadline. When a task partition is given, we present an optimal scheduling algorithm for the minimization of energy consumption. When task partitioning and scheduling must be resolved, we first prove the NP-hardness of the problem and then propose a 2.371approximation algorithm with O(|T |(log |T | + log M ) + M ), where T is a given task set, and M is the number of cores for a chip multiprocessor. A series of simulations was conducted the strength of our proposed algorithm, for which we have very encouraging results.

  2, . . . , k. Schedules ψ and ψ have the same energy consumption.

1 :

 1 Steps 4-7 follow the definition of the power consumption function. The time complexity of Algorithm 1 is O(|T | + M ). The optimality is shown as follows. Algorithm 1 : MES Input: (X); Output: A feasible X-based schedule Ψ with the minimum energy consumption; Xi ← 0 for i = 0 to M ; 2: for i = 1 to M do 3:

3 :

 3 for i = 1 to |T | do 4: find the smallest Xm; (break ties arbitrarily) 5:

Figure 1 .

 1 Figure 1. The simulation results of Algorithm LTF and Algorithm RAND: (a) The average relative energy consumption ratio when |T | = 10...15 and M = 3...8 (b) The maximum relative energy consumption ratio when |T | = 10...15 and M = 3...8 (c) The average relaxed relative energy consumption ratio when |T | = 50...100 and M = 8...32 (d) The maximum relaxed relative energy consumption ratio when |T | = 50...100 and M = 8...32

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)

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

Since the problem is NP-hard, the performance metric relaxed relative energy consumption ratio aimed at the providing of an approximate index when the optimal solution could not be obtained "efficiently". Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

* Support in parts by research grants from ROC National Science Council (NSC-93-2213-E-002-031).


Jennifer C Stern
email: c.stern@nasa.gov

Amy C Mcadam

P D Archer

H Bower

A Buch

J Eigenbrode

C Freissinet

B Franz

D Glavin

J H Jones

Rocknest J C Data

Stern

H B Franz

P R Mahaffy

D W Ming

P B Niles

A Steele

B Sutter

CARBON ISOTOPIC COMPOSITION OF CO 2 EVOLVED DURING PERCHLORATE-INDUCED REACTIONS IN MARS ANALOG MATERIALS: INTERPRETING SAM/MSL

come

Carbon Isotopic composition of CO2 evolved during perchlorate-induced reactions in mars analog materials:

interpreting sam/msl rocknest data

Introduction:

The Sample Analysis at Mars (SAM) Instrument Suite on the Mars Science Laboratory (MSL) Rover Curiosity made its first solid sample evolved gas analysis of unconsolidated material at aeolian bedform Rocknest in Gale Crater. The magnitude of O 2 evolved in each run as well as the chlorinated hydrocarbons detected by SAM gas chromatograph/mass spectrometer (GCMS) [1] suggest a chlorinated oxidant such as perchlorate in Rocknest materials [2]. Perchlorate induced combustion of organics present in the sample would contribute to the CO 2 volatile inventory, possibly overlapping with CO 2 from inorganic sources. The resulting carbon and oxygen isotopic composition of CO 2 sent to the Tunable Laser Spectrometer (TLS) for analysis would represent mixed sources. This work was undertaken to better understand a) how well the carbon isotopic composition (δ 13 C) of CO 2 from partially combusted products represents their source and b) how the δ 13 C of combusted products can be deconvolved from other carbon sources such as thermal decomposition of carbonate.

Materials/Methods: SAM received a portion of Rocknest material [3] sieved to <150 µm for Evolved Gas Analysis (EGA). Samples were heated from 35° to ~835° C in a stream of He at 1.5 sccm at a ramp rate of 35° C/min under a 30 mb pressure of He in the SAM pyrolysis oven. Evolved gas was continuously sampled by the quadrupole mass spectrometer (QMS) on SAM, and a portion of gas evolved over a predetermined temperature range was sent to the TLS for isotopic analysis of evolved CO 2 and H 2 O.

A SAM-like EGA system consisting of an in-house pyrocell coupled to a commercial Hiden Mass Spectrometer fitted with a gas manifold to collect CO 2 evolved during pyrolysis has been established at GSFC and used successfully in conjunction with commercial Cavity Ringdown Spectroscopy (Picarro) to measure δ 13 C of CO 2 evolved from carbonate-bearing Mars analog materials [4]. For perchlorate EGA-MS experiments, samples consisted of simple organic compounds dried down onto fused silica and Mars analog samples representing a range of % carbon. Samples were heated both with and without 1 wt% Mgperchlorate and volatile releases were monitored by the Hiden mass spectrometer. Once CO 2 evolution vs. temperature curves were established for each sample, gas collection using the manifold system was timed for collection of bulk CO 2 and CO 2 evolved over selected temperature ranges to model the SAM-EGA-TLS experiment. δ 13 C of evolved CO 2 was measured by injection into a Thermo Trace Ultra GC with Carboxen 1006 GC column coupled to a Thermo Scientific Delta V Plus isotope ratio mass spectrometer (IRMS). δ 13 C of all solid samples was measured using conventional laboratory combustion Elemental Analysis (EA) coupled to IRMS.

Preliminary Results: Four analyses of Rocknest material, preceeded by a blank, showed generally consistent results with respect to evolution of volatile species H 2 O, CO 2 , SO 2 , and O 2 [5]. Rocknest material released CO 2 from ~200° C to ~600° C. All four runs are generally consistent, with four CO 2 peaks as suggested by Gaussian peak fitting routine (Figure 1).

2654.pdf 44th Lunar and Planetary Science Conference (2013)

small contribution of CO 2 from combustion of these organics. Preliminary calculations estimating CO 2 evolved by the most abundant MTSBSTFA-related products, mono-and bi-silylated water [8], suggest 260-420 nmol CO 2 could come from the combustion of these compounds. The total CO 2 molar abundance during EGA of Rocknest samples is approximately 10 µmol [3]. Accordingly, an upper limit for the relative amount of CO 2 represented by combustion of MTBSTFA-related products is ~ 4% of the total CO 2 evolved during Rocknest EGA experiments [2,8].

One interesting benefit of the presence of perchlorate in Martian soils is the resulting perchlorateinduced combustion of reduced carbon during pyrolysis. CO 2 from combustion of reduced carbon can be sent to the TLS for δ 13 C analysis. In this way, the δ 13 C composition of any combustable organic carbon on Mars could be measured. SAM carried a small volume of oxygen to Mars to perform a combustion experiment with the objective of obtaining δ 13 C composition of any reduced carbon species found; however, perchlorate may provide an additional boost in the combustion of more refractory carbon, and, if ubiquitous in Mars surface materials, provides a non-consumable source of oxygen for combustion.

Perchlorate-induced combustion experiments

Laboratory experiments using SAM-like techniques help us understand the effects of perchlorate on combustion of organics and the δ 13 C of the CO 2 evolved by this process. Preliminary data from samples run on the SAM-like Hiden system show significant differences between CO 2 evolution in the presence and absence of perchlorate. Figure 2 shows CO 2 evolution during heating of Green River Shale alone and with 1 wt% Mg-perchlorate. In Hiden EGA experiments without perchlorate, there appears to be minimal oxidation of organic carbon, and the main CO 2 peak evolution between 525° C to 725° C is consistent with thermal decomposition of carbonate minerals known to be present in the sample. In the experiment with 1% perchlorate, CO 2 is evolved in a broad peak between 200-500 °C. This may be due to a combination of factors. CO 2 evolution from carbonate may occur at lower temperatures via dissolution by HCl produced during decomposition of . However, organic fragments in Green River Shale also show changes in their thermal decomposition profile in the presence of perchlorate. Figure 3 suggests that there is some combustion of organics, as well as an earlier onset temperature (~100° C lower) for their evolution. Most likely, a combination of combusted organics and carbonate dissolution are responsible for the CO 2 evolution in this experiment.

Green River Shale, while not a perfect Mars analog in terms of concentration of organic carbon, is used as a model for samples with two distinct carbon components, carbonate and kerogen [10]. These two components have distinct isotopic compositions, with carbonate δ 13 C ~ 9‰ and kerogen δ 13 C ~ -28‰ [10 and this work]. Because these two contributions have δ 13 C almost 40‰ apart from one another, this sample is well suited to examine the effects described above on isotopic composition of CO 2 evolved in the presence of perchlorates. Ongoing work is underway to characterize the effects of oxidants proposed at Rocknest, notably Ca-perchlorate [2], on the δ 13 C of CO 2 evolved during EGA of multi-component analog samples.

  Figure 1. Rocknest #4 mass 45 trace suggesting 4 peaks for CO 2 . Data in blue, fitted peaks in red.

  References: [1] Glavin et al. (2013) LPS XLIV [2] Sutter et al. (2013a) LPS XLIV [3] Archer et al. (2013) LPS XLIV [4] Stern et al. (2012) Icarus. [5] Franz et al. (2013) LPS XLIV. [6] Sutter et al. (2013b) LPS XLIV [7] Freissinet et al. (2013) LPS XLIV [8] Buch et al. (2013) LPS XLIV [9] Cannon et al. (2012) GRL 39, L13203. [10] I. Gilmour and C. T. Pillinger (1985) Organic Geochemistry (8) 6.

Figure 2 .

 2 Figure 2. CO 2 evolution from Green River Shale in the presence (red) and absence (blue) of 1% Mg perchlorate.

Figure 3 .

 3 Figure 3. Major organic fragments evolved during pyrolysis of Green River Shale, with and without 1% Mg Perchlorate.


Caroline Freissinet
email: caroline.freissinet@nasa.gov

D P Glavin

A Buch

Cyril Szopa

S Kashyap

H B Franz

J L Eigenbrode

W B Brinckerhoff

R Navarro-González

Samuel Teinturier

Mudstone C Freissinet

C A Malespin

B D Prats

P R Mahaffy

In situ wet chemistry experiment on mars using the sample analysis at mars (sam) instrument: " opportunistic derivatization " to investigate organics in a martian mudstone

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction:

The wet chemistry experiments on the Sample Analysis at Mars (SAM) instrument were designed for the extraction and identification of refractory organic chemical components in solid samples using gas chromatography-mass spectrometry (GCMS) [1,2]. One of the chemical agents used, Nmethyl-N-tert-butyldimethylsilyl-trifluoroacetamide (MTBSTFA), was sealed inside seven Inconel metal cups present in the SAM Sample Manipulation System (SMS). Although none of these foil-capped derivatization cups have been punctured on Mars for a full-cup wet chemistry experiment as originally designed, data from SAM has shown that the MTBSTFA vapor that leaked into the SMS is available to react with volatiles in solid samples and is detected mostly as its reaction product with water [3,4]. Despite the MTBSTFA background in SAM, several organic molecules indigenous to Mars have been identified by GCMS above background levels in a drilled mudstone sample called Cumberland (CB) collected at Yellowknife Bay [3]. Here we report preliminary results from an MTBSTFA "opportunistic derivatization" (OD) GCMS experiment that maximized the MTBSTFA deposition on a CB mudstone sample stored in SAM. The experiment was optimized for the detection of MTBSTFA residual vapor reaction products with refractory organic compounds and other molecules present in the CB mudstone sample.

MTBSTFA Opportunistic Derivatization:

The CB sample used in the OD experiment was drilled in the Sheepbed mudstone on Sol 279, and a fresh triple portion aliquot of the mudstone sample (~ 135 ± 31 mg) was added on top of a previously pyrolyzed CB single portion sample. This "doggy bag" sample was left inside SAM for about 1280 sols and accumulated and reacted with MTBSTFA vapor present in the SMS during the traverse to the base of Mt. Sharp. The OD experiment was conducted as a multi-sol experiment as follows: 1) The first step (ODa) consisted of a medium temperature heating of the sample from ambient to ~560 ºC at a rate of 35 ºC/min under 1 standard cubic centimeters per min He flow, to remove most of the O 2 released from the decomposition of perchlorates, in order to limit the combustion of possible organic molecules and their MTBSTFA derivatives in the second OD step. No GCMS was run during this first step, however, volatiles released from the sample during heating to 560°C were analyzed directly using the quadrupole mass spectrometer (QMS) only. The cup was then removed from the pyrolysis oven and placed back into the SMS where the sample could readsorb and react with MTBSTFA vapor present in the SMS for 48 hours. 2) The second step (ODb) utilized a higher temperature heating, up to ~900 ºC, to perform derivatization of molecules in the samples that evolve at elevated sample temperatures (either trapped inside minerals or resulting from the breakdown of more complex organics). During this ODb phase, four pyrolysis temperatures cuts were sent to a hydrocarbon trap for GC analyses: ~40-115ºC, ~310-550ºC, ~590-670ºC and ~753ºC to the end of the run. The cuts were selected to target the release of compounds of interest, while also avoiding the saturation of the trap with MBSTFA byproducts or SO 2 from sulfate decomposition. The trap was set at a temperature of ~70°C for the first cut, a temperature at which most the MTBSTFA reaction products with water would pass through, while derivatized compounds of interest would be retained. At a sample temperature of ~300ºC, the SAM trap was cooled down from 70ºC to 5ºC to trap smaller volatiles. MTBSTFA reaction products and other volatiles collected on the hydrocarbon trap were then analyzed by GC separation, on two GC columns (GC1-MXT-20 and GC4-Chirasil-Dex, each column is 30 m length, 0.25 mm ID, 0.25 µm film thickness) and QMS analysis after heating the trap to 310°C [2]. After the ODa and ODb analyses of CB, a procedural control experiment is planed to be carried out using the identical SAM analytical conditions, on a quartz cup containing a triple portion CB sample that was heated previously to ~900°C three times. with a wide range of molecules that contain a labile hydrogen such as alcohols, primary and secondary amines, carboxylic acids and amino acids in the free form (Figure 1). The silyl ester products of these molecules are typically much more volatile than the original non-derivatized molecule, which enables the transfer of the MTBSTFA derivatives through the SAM gas processing system for GCMS analysis.

The initial abundance of MTBSTFA adsorbed on a cup and a sample was estimated from the abundances of the primary MTBSTFA byproducts formed from its reaction with water molecules including tertbutyldimethylsilanol, N-methyl-2,2,2-trifluoroacetamide, and 1,3-bis(1,1-dimethylethyl)-1,1,3,3tetramethyldisiloxane [3], and was expected to be at least 116 nmol or 0.03 mL, as estimated from the CB-Blank-1 EGA experiment [3]. In the ODb experiment, the abundances of MTBSTFA reaction products detected by GCMS and corresponding MTBSTFA abundances released from the Cumberland "doggy bag" triple portion were found to be ten times higher, in the µmol range. This result is not surprising since the OD experiments were optimized for the concentration and detection of MTBSTFA reaction products. However, only part of this was sent to the trap/GC columns, due to the temperature cuts and hot SAM trap combination. The temperature cuts were chosen to target, among others, potential molecules trapped in the sulfate minerals of CB. S-containing molecules were previously observed at high temperature in the CB sample [5]. The two high-temperature SO 2 peaks evolving from CB are thought to be Fe-sulfate and Mgsulfate [6]. Unfortunately, the temperature reached during the first OD step (ODa) started to decompose the Fe-sulfates, possibly releasing trapped organics. However, molecules trapped in the Mg-sulfates would be seen either as derivatized, or pristine, molecules in the OD experiment. The preliminary results show a tentative identification of thiophene, as expected, in GC4 (Fig. 2). Chlorobenzene was also tentatively identified, which has numerous implications. Unlike the previous detection of chlorobenzene in CB samples [3], this detection occurred at a higher temperature of the sample (> 560ºC vs. 250-450ºC previously). This chlorobenzene, if indigenous to the martian sample, would originate from a different source than the 250-450ºC one. Several N-containing compounds were observed at higher abundances than previously seen, and 2-propenenitrile was observed for the first time in SAM. Lastly, the high abundance of chloromethane detected by GC in ODb (Fig. 2), combined with the absence of chloromethylpropene, another usual MTBSTFA-perchlorate reaction product, suggests that a large fraction of the chloromethane may be indigenous to the sample. The OD data set is under investigation to identify more complex organic molecules on GC4, and also to decipher the chromatogram of the newly used GC1 column. This latter column not having an injection trap at the front end, leads to broader peaks and retention times that remain to be quantified with laboratory studies.

Conclusion:

This opportunistic derivatization experiment represents a successful demonstration of SAM capabilities. Newly optimized parameters, including a hot-trap to minimize MTBSTFA column overloading, multiple temperatures cuts, and a split column configuration, led to a successful derivatization on Mars using the residual MTBSTFA in the sample cup region of the instrument. Several MTBSTFA reaction products were generated during reactions with the Cumberland mudstone sample at elevated temperatures, as well as non-derivatized organic molecules, including chloromethane and 2propenenitrile of likely martian origin.

We are continuing the analysis of this interesting data set to identify derivatization products that could shed additional light on the chemical nature of the organic matter present in the Cumberland mudstone. This experiment is also a stepping stone for the future fullcup derivatization, currently in preparation [2].

References: [1]

Figure 1 :

 1 Figure 1: Example MTBSTFA reaction with an amino acid to form the volatile silyl ester derivative and a trifluoro-N-methylacetamide (TFMA) byproduct that are both detectable by the SAM GCMS.

Figure 2 :

 2 Figure 2: Chromatography from CB sample, ODb on GC4 after the sample has been cleaned out of part of its O2 in ODa. Relevant m/z values are called out as well as a "band 6" that includes all m/z values between 87-150 Da. m/z 52 for chloromethane, m/z 53 for 2methylpropene, m/z 65 for SO2, m/z 86 for dichloromethane, m/z 84 for thiophene, m/z 112 for chlorobenzene and m/z 147 for bisilylated water. GC column temperature is represented in red. All compounds represented, apart from BSW, are presumably martian.

2687.pdf Lunar and Planetary Science XLVIII (2017)

  Mahaffy, P. et al. (2012) Space Sci Rev, 170, 401-478. [2] Malespin, C. et al., this conference. [3] Freissinet et al. (2015) JGR Planets. [4] Glavin, D. et al. (2013) JGR Planets, Vol. 118, 1-19. [5] Freissinet, C. et al., LPSC 2015 abstract, [6] Sutter, B. et al., this conference.

	MS response (cps)	10 3 10 4 10 5 10 6	m/z 112 m/z 147 band 6 m/z 52 m/z 53 m/z 65 m/z 86 m/z 84	SO 2	Chloromethane	2-Propenenitrile	Dichloromethane		Thiophene	Chlorobenzene	BSW	150 100 50	GC Column temperature (ºC)
		10 2
		0		200	400	600	800	1000	1200	1400	1600
								Retention Time (s)