Alexandru Andrei

Marcus T Schmitz

Petru Eles

Zebo Peng

Bashir M Al Hashimi

Quasi-Static Voltage Scaling for Energy Minimization with Time Constraints

Supply voltage scaling and adaptive body-biasing are important techniques that help to reduce the energy dissipation of embedded systems. This is achieved by dynamically adjusting the voltage and performance settings according to the application needs. In order to take full advantage of slack that arises from variations in the execution time, it is important to recalculate the voltage (performance) settings during runtime, i.e., online. However, voltage scaling (VS) is computationally expensive, and thus significantly hampers the possible energy savings. To overcome the online complexity, we propose a quasi-static voltage scaling scheme, with a constant online time complexity O(1). This allows to increase the exploitable slack as well as to avoid the energy dissipated due to online recalculation of the voltage settings. We conduct several experiments that demonstrate the advantages of the proposed technique over the previously published voltage scaling approaches.

Introduction and Related Work

Two system-level approaches that allow an energy/performance tradeoff during application run-time are dynamic voltage scaling (DVS) [START_REF] Demers | A Scheduling Model for Reduced CPU Energy[END_REF][START_REF] Ishihara | Voltage Scheduling Problem for Dynamically Variable Voltage Processors[END_REF][START_REF] Martin | Combined Dynamic Voltage Scaling and Adaptive Body Biasing for Lower Power Microprocessors under Dynamic Workloads[END_REF] and adaptive body-biasing (ABB) [START_REF] Kim | Dynamic Vth Scaling Scheme for Active Leakage Power Reduction[END_REF][START_REF] Martin | Combined Dynamic Voltage Scaling and Adaptive Body Biasing for Lower Power Microprocessors under Dynamic Workloads[END_REF]. While DVS aims to reduce the dynamic power consumption by scaling down circuit supply voltage V dd , ABB is effective in reducing the leakage power by scaling down frequency and increasing the threshold voltage V th through bodybiasing. Voltage scaling (VS) approaches for time constrained multitask systems can be broadly classified into offline (e.g. [START_REF] Andrei | Overhead-Conscious Voltage Selection for Dynamic and Leakage Power Reduction of Time-Constraint Systems[END_REF][START_REF] Demers | A Scheduling Model for Reduced CPU Energy[END_REF][START_REF] Ishihara | Voltage Scheduling Problem for Dynamically Variable Voltage Processors[END_REF][START_REF] Yan | Combined Dynamic Voltage Scaling and Adaptive Body Biasing for Heterogeneous Distributed Real-time Embedded Systems[END_REF]) and online (e.g. [START_REF] Demers | A Scheduling Model for Reduced CPU Energy[END_REF][START_REF] Mosse | Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems[END_REF][START_REF] Hong | On-Line Scheduling of Hard Real-Time Tasks on Variable Voltage Processors[END_REF][START_REF] Zhu | Feedback EDF Scheduling Exploiting Dynamic Voltage Scaling[END_REF]) techniques, depending on when the actual voltage settings are calculated. Offline techniques calculate all voltage settings at compile time (before the actual execution), i.e., the voltage settings for each task in the system are not changed at run-time. On the other hand, online techniques recompute the voltage settings during run-time. Both approaches have their advantages and disadvantages. Offline VS approaches avoid the computational overhead in terms of time and energy associated with the calculation of the voltage settings. However, to guarantee the fulfilment of deadline constraints, worst-case execution times (WCET) have to be considered during the voltage calculation. In reality, nevertheless, the actual execution time of the tasks, for most of their activations, is shorter than their WCET, with variations of up to 10 times [START_REF] Ernst | Embedded program timing alalysis based on path clustering and architecture classification[END_REF]. Thus, an offline optimization based on the worst case is too pessimistic and hampers the achievable energy savings. In order to take advantage of the dynamic slack that arises from variations in the execution times, it is useful to dynamically recalculate the voltage settings during application run-time, i.e., online.

Dynamic approaches, however, suffer from the significant overhead in terms of execution time and power consumption caused by the online voltage calculation. As we will show, this overhead is intolerablly large even if low complexity online heuristics are used instead of higher complexity optimal algorithms. Unfortunatelly, researchers have neglected this overhead when reporting high quality results obtained with dynamic approaches [START_REF] Demers | A Scheduling Model for Reduced CPU Energy[END_REF][START_REF] Mosse | Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems[END_REF][START_REF] Hong | On-Line Scheduling of Hard Real-Time Tasks on Variable Voltage Processors[END_REF][START_REF] Zhu | Feedback EDF Scheduling Exploiting Dynamic Voltage Scaling[END_REF].

In [START_REF] Catthoor | Pareto-Optimization-Based Run-Time Task Scheduling for Embedded Systems[END_REF] an approach is outlined in which the online scheduler is ex-ecuted at each activation of the application. The decision taken by the scheduler is based on a set of precalculated supply voltage settings. The approach assumes that at each activation it is known in advance which subgraphs of the whole application graph will be executed. For each such subgraph worst case execution times are assumed and, thus, no dynamic slack can be exploited.

In this paper we propose a quasi-static voltage scaling technique for energy minimization of multi-task real-time systems. This technique is able to exploit the dynamic slack and, at the same time, keeps the online overhead (required to readjust the voltage settings at run-time) extremly low. The obtained performance is superior to any of the previously proposed dynamic approaches. Henceforth, we will refer to the proposed voltage scaling technique as quasi-static voltage scaling (QSVS).

The work presented in this paper makes the following contributions: (a) A quasi-static voltage scaling scheme for multi-task applications is proposed. In the offline phase, it computes and stores possible voltage settings. The online phase is responsible to adapt the applied voltage settings at run-time, based on the stored information and the actual task execution times. We investigate the "optimality" of QSVS compared to an ideal, but practically infeasible, online voltage scaling approach. The time complexity of the QSVS technique is polynomial in the offline phase and constant in the online part. (b) The introduced QSVS scheme addresses the combined reduction of dynamic and leakage power consumption using supply and body-bias voltage scaling. (c) We perform, for the first time, an evaluation of the impact of the overhead of different dynamic voltage scaling approaches on realistic applications. These evaluations are performed using cycle accurate simulation tools as well as measurements on a real processor.

The paper is organized as follows: Preliminaries and motivations are given in Section 2, as well as the key ideas behind the presented work. An exact problem formulation for quasi-static voltage scaling is given in Section 3. Our algorithms to solve this problem are described in Section 4. Extensive experimental results, including a real-life example, are presented in Section 5. Finally, conclusions are drawn in Section 6.

Preliminaries

Application and Architecture Model

In this work, we consider applications that are modeled as task graphs, i.e., several tasks with possible data dependencies among them, as in Fig. 1(a). Each task is characterized by several parameters (see also section 3), such as a deadline, the effectively switched capacitance, and the number of clock cycles required in the best-case (BNC), expectedcase (ENC), and worst-case (WNC). Tasks are running without being preempted until their completion. For such systems is has been proved in [START_REF] Hu | Task Scheduling and Voltage Selection for Energy Minimization[END_REF] that the EDF (earliest deadline first) scheduling is optimal from the energy point of view. Thus, we assume that the order of task execution is fixed offline, according to an EDF policy, as shown in Fig. 1(b). The tasks are executed on an embedded architecture that consists of a voltage-scalable processor (scalable in terms of supply and body-bias The approach presented in this paper aims to reduce this online overhead by performing the necessary VS computations offline (at compile time) and storing a limited amount of information as look-up tables (LUTs) within memory. This information is then used during application run-time (i.e., online) to calculate the voltage and performance settings extremely fast (constant time O(1)), see Fig. 1(d).

Power and Delay Models

Digital CMOS circuitry has two major sources of power dissipation: (a) dynamic power P dyn , which is dissipated whenever active computations are carried out (switching of logic states), and (b) leakage power P leak which is consumed whenever the circuit is powered, even if no computations are performed. The dynamic power is expressed by [START_REF] Anantha | Low Power Digital CMOS Design[END_REF][START_REF] Martin | Combined Dynamic Voltage Scaling and Adaptive Body Biasing for Lower Power Microprocessors under Dynamic Workloads[END_REF],

P dyn = C e f f • f •V 2 dd (1)
where C e f f , f , and V dd denote the effective charged capacitance, operational frequency, and circuit supply voltage, respectively. Although, until recently, the dynamic power dissipation had been dominating, the trend to reduce the overall circuit supply voltage and, consequently, threshold voltage is raising concerns about the leakage currents-for near future technology (< 70nm) it is expected that leakage will account for more than 50% of the total power. The leakage power is given by [START_REF] Martin | Combined Dynamic Voltage Scaling and Adaptive Body Biasing for Lower Power Microprocessors under Dynamic Workloads[END_REF],

P leak = L g •V dd • K 3 • e K 4 •V dd • e K 5 •V bs + |V bs | • I Ju (2)
where V bs is the body-bias voltage and I Ju represents the body junction leakage current. The fitting parameters K 3 , K 4 and K 5 denote circuit technology dependent constants and L g reflects the number of gates. For clarity reasons we maintain the same indices as used in [START_REF] Martin | Combined Dynamic Voltage Scaling and Adaptive Body Biasing for Lower Power Microprocessors under Dynamic Workloads[END_REF], where also actual values for these constants are provided. Nevertheless, scaling the supply and the body-bias voltage, in order to reduces the power consumption, has a side effect on the circuit delay d, which is inverse proportional to the operational frequency f [START_REF] Anantha | Low Power Digital CMOS Design[END_REF][START_REF] Martin | Combined Dynamic Voltage Scaling and Adaptive Body Biasing for Lower Power Microprocessors under Dynamic Workloads[END_REF],

f = 1 d = ((1 + K 1 ) •V dd + K 2 •V bs -V th1 ) α K 6 • L d •V dd ( 3
)
where α denotes the velocity saturation imposed by the given technology (common value: 1.4 ≤ α ≤ 2), L d is the logic depth, and K 1 , K 2 , K 6 , and V th1 reflect circuit dependent constants [START_REF] Martin | Combined Dynamic Voltage Scaling and Adaptive Body Biasing for Lower Power Microprocessors under Dynamic Workloads[END_REF]. Equations ( 1), (2), and (3) provide the energy/performance trade-off of digital circuits. Ideal Online Voltage Scaling

Motivation

This section motivates the presented work and outlines the basic idea of the proposed quasi-static voltage scaling technique.

Complexity Evaluation of Voltage Scaling

As we have mentioned in the introduction, to fully take advantage of variations in the execution time of tasks, with the aim to reduce the energy dissipation, it is unavoidable to recompute the voltage settings online according to the actual task execution times. This is demonstrated in Fig. 2, where we consider an application consisting of n = 4 tasks.

Only after task τ 1 has terminated, we know its actual finishing time and, accordingly, the amount of dynamic slack that can be distributed to the remaining tasks (τ 2 ,τ 3 ,τ 4 ). Ideally, in order to optimally distribute the slack among these tasks (τ 2 ,τ 3 , and τ 4 ), it is necessary to run a voltage scaling algorithm (in Fig. 2 indicated as VS 1) before starting the execution of task τ 2 . A straightforward implementation of an ideal online voltage scaling algorithm is to perform a "complete" recalculation of the voltage settings each time a task finishes, using for example the VS approaches described in [START_REF] Yan | Combined Dynamic Voltage Scaling and Adaptive Body Biasing for Heterogeneous Distributed Real-time Embedded Systems[END_REF][START_REF] Schmitz | Considering Power Variations of DVS Processing Elements for Energy Minimisation in Distributed Systems[END_REF]. However, such an implementation would be only feasible if the computational overhead associated with the voltage scaling algorithm is very low, which is not the case in practice. The computational complexity of such optimal voltage scaling algorithms for monoprocessor systems is O(m • n) [START_REF] Yan | Combined Dynamic Voltage Scaling and Adaptive Body Biasing for Heterogeneous Distributed Real-time Embedded Systems[END_REF][START_REF] Schmitz | Considering Power Variations of DVS Processing Elements for Energy Minimisation in Distributed Systems[END_REF] (with m specifying the accuracy-a usual value of 100 and n being the number of tasks). That is, a substantial amount of CPU cycles are spent calculating the voltage/frequency settings each time a task finishes-during these cycles the CPU uses precious energy and reduces the amount of exploitable slack.

To get insight into the computational requirements of voltage scaling algorithms and how this overhead compares to the amount of computations performed by actual applications, we have simulated and profiled several applications and voltage scaling techniques, using two cycle accurate simulators: StrongARM (SA-1100) [START_REF] Qin | Flexible and Formal Modeling of Microprocessors with Application to Retargetable Simulation[END_REF] and PowerPC(MPC750) [18]. We have also performed measurements on actual implementations using an AMD platform (AMD Athlon 2400XP). Tab. 1 shows these results for two applications that can be commonly found in hand-held devices: a GSM voice codec and an MPEG video encoder. Results are shown for AMD, SA-1100 and MPC750 and are given in terms of best-case (BNC) and worst-case number (WNC) of thousands of clock cycles needed for the execution of one period of the considered applications (20 ms for the GSM codec and 40 ms for the MPEG encoder). 1 For instance, on the SA-1100 processor one iteration of the MPEG encoder requires in the best-case 4.458 kcycles and in the worst-case 8.043 kcycles, that is a variation of 45%. Similarly, Tab. 2 presents the simulation outcomes for different voltage scaling algorithms. As an example, performing the optimal online voltage scaling using the algorithm from [START_REF] Yan | Combined Dynamic Voltage Scaling and Adaptive Body Biasing for Heterogeneous Distributed Real-time Embedded Systems[END_REF] once for 20 remaining tasks (just like VS 1 is once performed for the three remaining tasks τ 2 , τ 3 , and τ 4 in Fig. 2) requires 8,410 kcycles on the AMD processor, 136,950 kcycles on the MPC750 processor, while the SA-1100 requires even 1,232,552 kcycles. Using the same algorithm for V dd -only scaling (no V bs scaling), needs 210 kcycles on the AMD processor, 32,320 kcycles on the SA-1100 and 3,513 kcycles on the MPC750. The difference in complexity between supply voltage scaling and combined supply and body bias scaling comes from the fact that in the case of V dd -only, for a given frequency there exists one corresponding supply voltage, as opposed to a potentially infinite number of (V dd ,V bs ) pairs in the other case. Given a certain frequency, an optimization is needed to compute the (V dd ,V bs ) pair that minimizes the energy. Comparing the results in Tables 1 and2 indicates that voltage scaling often surpasses the complexity of the applications itself. For instance, performing a "simple" V dd -only scaling requires more CPU time (on AMD 210k cycles) than decoding a single voice frame using the GSM codec (on AMD 155k cycles). Clearly, such overheads seriously affect the possible energy savings, or even outdo the energy consumed by the application. Several suboptimal heuristics with lower complexities have been proposed for online computation of the supply voltage. Gruian [START_REF] Gruian | Energy-Centric Scheduling for Real-Time Systems[END_REF] has proposed a linear time heuristic, while the approaches given in [START_REF] Mosse | Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems[END_REF][START_REF] Zhu | Feedback EDF Scheduling Exploiting Dynamic Voltage Scaling[END_REF] use a greedy heuristic of constant time complexity. We report their performance in terms on the required number of cycles in Tab. 2, including also their additional adaptation for combined supply and body bias scaling. While these heuristics have a smaller online overhead than the optimal algorithms, their cost is still high, except for the greedy algorithm for supply voltage scaling [START_REF] Mosse | Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems[END_REF][START_REF] Zhu | Feedback EDF Scheduling Exploiting Dynamic Voltage Scaling[END_REF]. However, even the cost of the greedy increases up to 5.4 times when it is used for supply and body bias scaling. The overhead of our proposed algorithm is given in the last line of Tab. 2.

Bench- AMD Athlon SA1100 MPC750 mark BNC WNC Var. BNC WNC Var. BNC WNC Var. type (k) (k) (%) (k) (k) (%) (k) (k) (%) GSM

Basic Idea: Quasi-Static Voltage Scaling

To overcome the VS overhead problem, we propose a quasi-static voltage scaling technique. This approach is divided into two phases. In the first phase, which is performed before the actual execution (i.e., offline), voltage settings for all tasks are pre-computed based on possible task start times. The resulting voltage/frequency settings are stored in look-up tables (LUTs) that are specific to each task. It is important to note that this phase performs the time intensive optimization of the voltage settings.

The second phase is performed online and it is outlined in Fig. 3. Each time new voltage settings for a task need to be calculated, the online scheme looks up the voltage/frequency settings from the LUT based on the actual task start time. If there is no exact entry in the LUT that corresponds to the actual start time, then the voltage settings are estimated using a linear interpolation between the two entries that surround the actual start time. For instance, task τ 3 has an actual start time of 3.58ms. As indicated in Fig. 3, this start time is surrounded by the LUT entries 3.55ms and 3.60ms. In accordance, the frequency and voltage setting for task τ 3 are interpolated based on these entries. The main advantage of the online quasi-static VS algorithm is its constant time complexity O [START_REF] Al Hashimi | Improving the Efficiency of Memory Partitioning by Address Clustering[END_REF]. As shown in the last line of Tab.

Problem Formulation

Consider a set of NT tasks, T = {τ i } such that the execution order is fixed according to an EDF policy. The processor can vary its supply voltage V dd and body-bias voltage V bs within certain continuous ranges. The dynamic and leakage power dissipation as well as the operational frequency (cycle time) depend on the selected voltage pair (mode). Tasks are executed cycle by cycle and each cycle can be potentially executed at different voltage settings, i.e., a different energy/performance trade-off. Each task τ i is characterized by a six-tuple,

τ i =< BNC i , ENC i ,W NC i ,Ce f f i , D i >
where BNC i , ENC i , and W NC i denote the best-case, the expected-case, and the worst-case number of clock cycles, respectively, that task τ i requires for its execution. BNC (W NC) is defined as the lowest (highest) number of cycles task τ i needs for its execution, while ENC is the arithmetic mean value of the probability density function p(W NC) of the task execution cycles W NC, i.e., ENC = ∑ W NC j=1 j • p j ( j). Further, Ce f f i and D i represent the effectively charged capacitance and the deadline. The aim is to reduce the energy consumption by exploiting dynamic slack as well as static slack. Dynamic slack results from tasks that require less execution cycles than in their worst case. Static slack is the result of idleness due to system over-performance, observable even when tasks execute with the worst-case number of cycles.

Our goal is to store a look-up table LUT i for each task τ i , such that the energy consumption during runtime is minimized. The size of the memory available for storing the look-up tables (and, implicitly the total number NL of table entries) is given as a constraint.

Quasi-Static Algorithm

Quasi-static voltage scaling aims to reduce the online overhead required to compute voltage settings by splitting the voltage scaling process into two phases. That is, the voltage settings are prepared offline, and the stored voltage settings are used online to adjust the voltage/frequency in accordance to the actual task execution times.

Offline Algorithm

The pseudo-code corresponding to the calculations performed offline is given in Fig. 4. The algorithm requires the following input information. The scheduled task set T , defined in section 3. For the tasks τ i ∈ T , the expected (ENC i ), the worst-case (WNC i ) and the best-case (BNC i ) number of cycles, the effectively switched capacitance (Ceff i ) and the deadline D i . Furthermore, total number of look-up table entries NL is given. The algorithm returns the quasi-static scaling table LUT i , for each task τ i ∈ T . This table includes n i (∑ n i=1 n i = NL) possible start times t s i, j , j = 1..n i for each task τ i , and the corresponding optimal settings for the supply voltage Vdd and the operational frequency f. Upon initialization, the algorithm computes the earliest and latest start times for each task (lines 01-06). The earliest start time EST i is based on the situation in which all tasks would execute with their best-case number of clock cycles at the highest voltage settings, i.e., the shortest possible execution (lines 01-03). The latest start time LST i is calculated as the latest start time of task τ i that allows to satisfy the deadlines for all the tasks τ j , j ≥ i, executed with the worst-case number of clock cycles at the highest voltages (lines 04-06). The algorithm proceeds by initializing the set of remaining tasks T r with the set of all tasks T (line 07). In the following (lines 08-18), the voltage and frequency settings for the start time intervals of each task are calculated. More detailed, in line 09 and 10 the size of the interval [EST i , LST i ] of possible start times is computed and the interval counter j is initialized. The number of entry points n i that are stored for each task (i.e., the number of possible start times considered) is calculated in line 11. This will be further discussed in Section 4.3. For all n i possible start times t s in the start time interval of task τ i (line 12), the task start time t s i is set to the possible start time (line 13) and the corresponding optimal voltage and frequency settings of τ i are computed (line 14). For this computation, we use the algorithm presented in [START_REF] Andrei | Overhead-Conscious Voltage Selection for Dynamic and Leakage Power Reduction of Time-Constraint Systems[END_REF], modified to incorporate the optimization for the expected case. We will explain this algorithm in Section 4.1.1. At this point, the voltages and frequency of task τ i for a starting at time t s i are stored in the quasi-static scaling table LUT i (line 15). The for-loop (line 11-23) is repeated for all n i possible start times of task τ i . Please note that we do not store the body-bias voltages Vbs i , which will be recomputed online. The reason behind this decision will be outlined in the quasi-static online algorithm (Section 4.2). The algorithm returns the quasi-static scaling table LUT i for all tasks τ i ∈ T .

Voltage Scaling Algorithm

We will briefly present the voltage scaling algorithm used in line 14 (Fig. 4). The problem can be formulated as a convex nonlinear optimization as follows: Minimize [START_REF] Kim | Dynamic Vth Scaling Scheme for Active Leakage Power Reduction[END_REF] The variables that need to be optimized in this formulation are the task execution times t k , the task start times s k as well as the voltages V dd k and V bs k . The whole formulation can be explained as follows. The total energy consumption, which is the combination of dynamic and leakage energy, has to be minimized. As we aim the energy optimization in the most likely case, the expected number of clock cycles ENC k is used. The minimization has to comply to the following relations and constraints. The task execution time has to be equivalent to the number of clock cycles of the task multiplied by the circuit delay for a particular V dd k and V bs k setting, as expressed by Eq. ( 5). Eq. 6 expresses the task execution order. Deadlines are inforced in Eq. 7. Up to this point, we have used the expected number of clock cycles ENC k as this is the situation for which we want to optimize the energy consumption. However, in order to insure that tasks will not miss their deadlines in the worst case, we need Eq. 8. Please remember from the computation of the latest start time (LST), that if task τ k finishes the execution before the latest start time of task τ k+1 , then the rest of the tasks are guaranteed to meet their deadlines even in the worst case.

|T r | ∑ k=i ENC k •C e f f k •V 2 dd k E dyn k + L g (K 3 •V dd k • e K 4 •V dd k • e K 5 •V bs k + I Ju • |V bs k |) • t k E leak k (4) subject to t k = ENC k • (K 6 • L d •V dd k ) ((1 + K 1 ) •V dd k + K 2 •V bs k -V th 1 ) α (
s k + t k ≤ s k+1 (6) s k + t k ≤ D k ∀ τ k that have a deadline (7) s k + t k ≤ LST k+1 (8) s k ≥ 0 (9) V dd min ≤ V dd k ≤ V dd max and V bs min ≤ V dd k ≤ V bs max

Online Algorithm

Fig. 5 gives the pseudocode of the online algorithm. This algorithm is called each time after a task finishes its execution, in order to calculate the voltage settings for the next task τ n . The input consists of the task start time t s n , the quasi-static scaling table LUT n , and the number of interval steps n n . As output, the algorithm returns the frequency f n and voltage settings Vdd n and Vbs n for the next task, τ n . In the first step, the algorithm calculates the two entries x and y from the quasi-static scaling table LUT n that contain the start times which surround the actual time t s n (line 01). According to the identified entries, the frequency setting f n for the execution of task τ n is linearly interpolated using the two frequency settings from the quasi-static scaling table LUT n [x] and LUT n [y] (line 02). Similarly, in step 03 the supply voltage Vdd n is linearly interpolated from the two surround voltage entries in LUT n . As mentioned in Section 4.1, we do not directly interpolate the setting for the body-bias voltage Vbs n , due to the nonlinear relation between frequency, supply voltage, and body-bias voltage. That is, interpolating V dd and V bs at the same time, can result in operational frequency that do not match the actually needed frequency-resulting in possible deadline violations. Therefore, we calculate the body-bias voltage directly for the interpolated frequency and supply voltage values, using Eq. 3 (line 04). The algorithm terminates and returns the settings for the frequency, supply and body-bias voltage (line 05). It is worthwhile to mention that all four steps that are necessary to perform the online calculation are computed in constant time, i.e., the time complexity of the quasi-static online algorithm is O [START_REF] Al Hashimi | Improving the Efficiency of Memory Partitioning by Address Clustering[END_REF].

At this point it is also interesting to note that the linear approximation performed by the online algorithm is safe (i.e. frequencies are calculated such that they guarantee that tasks will not violate their dead- Quasi-static Alg. proposed in [START_REF] Andrei | Quasi-Static Voltage Scaling for Energy Minimization with Time Constraints[END_REF] Greedy [START_REF] Anantha | Low Power Digital CMOS Design[END_REF] Task-splitting [START_REF] Demers | A Scheduling Model for Reduced CPU Energy[END_REF] Greedy [START_REF] Anantha | Low Power Digital CMOS Design[END_REF] Task-splitting ANC/WNC Deviation from theoretical limit (%) Deviation from theoretical limit (%) Deviation from theoretical limit (%) Figure 6. Experimental results: online voltage scaling lines). It can be shown that running the voltage scaling algorithm for all possible start times t s of a task results in a frequency function f (t s ) that is convex [START_REF] Andrei | Quasi-Static Voltage Scaling for Energy Minimization with Time Constraints[END_REF]. Thus any linear approximation of the frequency will result in frequency values higher or equal to the optimal one, and consequently no deadline will be violated. The quality of the the linear approximation depends directly on the number of intermediate start times used. The next section will discuss this important aspect.

Calculation of the Look-Up Table Sizes

In this section we address the problem of how many entries to assign to each LUT under a given memory constraint, such that the resulting entries yield high energy savings. A simple approach to distribute the memory among the LUTs is to allocate the same number of entries for each LUT. However, due to the fact that different tasks have different start time interval sizes and nominal energy consumptions, the memory should be distributed using a more effective scheme (i.e. reserving more memory for critical tasks). In the following we will introduce a heuristic approach to solve the LUT size problem. Clearly, the two main parameters that determine the criticality (in the sense that it should be allocated more entries in the LUT) of a task are the size of the interval of possible task τ i start times (LST i -EST i ) and the nominal expected energy consumption of a task (E i ). The expected energy consumption of a task E i is the energy consumed by that task when executing the expected number of clock cycles (ENC i ) at the nominal voltages. Consequently, in order to allocate the n i look-up table entries for each tasks, we use the following formula:

n i = NL • E i • (LST i -EST i ) ∑ NT i=1 E i • (LST i -EST i ) (11)

Experimental Results

We have conducted several experiments using numerous generated benchmarks as well as a real-life application, in order to demonstrate the applicability of the proposed approach. The processor parameters have been adopted from [START_REF] Martin | Combined Dynamic Voltage Scaling and Adaptive Body Biasing for Lower Power Microprocessors under Dynamic Workloads[END_REF]. The first set of experiments was conducted in order to investigate the quality of the results provided by different online VS techniques in the case when their actual run-time overhead is ignored. In Fig. 6(a) we show the results obtained with the following five different VS approaches:

1) the ideal online VS approach (the scheduler that calculates the optimal VS with no overhead).

2) the quasi-static VS technique proposed in this paper (Section 4).

3) the greedy heuristic proposed in [START_REF] Mosse | Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems[END_REF]. 4) the task splitting heuristic proposed in [START_REF] Zhu | Feedback EDF Scheduling Exploiting Dynamic Voltage Scaling[END_REF]. 5) the algorithm proposed in [START_REF] Demers | A Scheduling Model for Reduced CPU Energy[END_REF].

Originally, approaches given in [START_REF] Demers | A Scheduling Model for Reduced CPU Energy[END_REF][START_REF] Mosse | Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems[END_REF][START_REF] Zhu | Feedback EDF Scheduling Exploiting Dynamic Voltage Scaling[END_REF] perform DVS only. However, for comparison fairness, we have extended these algorithms towards combined supply and body-bias scaling. The results of all five techniques are given as the percentage deviation from the results produced by a hypothetical voltage scaling algorithm that would know in advance the exact number of clock cycles executed by each task. Of course such an approach is practically impossible. Nevertheless, we use this theoretical lower limit as baseline for the comparison. During the experiments, we varied the ratio of actual number of clock cycles (ANC) and worst case number of clock cycles (WNC) from 0.1 to 1 with a step width of 0.1. For each step, 1000 randomly generated task graphs were evaluated, resulting in a total of 10000 evaluations for each plot. As mentioned earlier, for this first experiment we ignored the computational overheads of all the investigated approaches, i.e., we assumed that the voltage scaling requires zero time. Furthermore, the actual number of clock cycles (ANC) are set based on a normal distribution using the expected number of cycles (ENC) as the mean value. Observing Fig. 6(a) leads to the following interesting conclusions. Firstly, if the actual number of cycles (ANC) corresponds to the worst-case number (WNC), all VS techniques approach the theoretical limit. In other words, if the application has been scaled for the WNC and all task execute with WNC, then all online VS techniques perform equally well. This, however, changes if the ANC differs from the WNC, which is always the case in practice. For instance, in the case that the ratio between ANC and WNC is 0.1, we can observe that ideal online VS is 25% off the theoretical limit. On the other hand, the technique described in [START_REF] Demers | A Scheduling Model for Reduced CPU Energy[END_REF] is 60% worse than the theoretical limit. The approaches based on the methods proposed in [START_REF] Mosse | Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems[END_REF][START_REF] Zhu | Feedback EDF Scheduling Exploiting Dynamic Voltage Scaling[END_REF] yield results that are 42% and 45% below the theoretical optimum. Another interesting observation is the fact that the ideal online scaling and our proposed quasi-static technique produce results of the same high quality. Of course, the quality of the quasi-static VS depends on the number of entries that are stored in the look-up tables (LUTs). Due to the importance of this influence, we have devoted a supplementary experiment to demonstrate how the number of entries affects the VS quality. In the experiment illustrated in Fig. 6(a) and (b) the total number of entries was set to 4000, which was sufficient to achieve results that differed with less then 0.5% from the ideal online scaling for task graphs with up to 100 nodes. In summary, Fig. 6(a) demonstrates the high quality of the voltage settings produced by the quasi-static approach, which are very close of those produced by the ideal algorithm and substantially better then the values produced by any other proposed approach.

In order to evaluate the global quality of the different VS approaches (taking into consideration the online overheads), we conducted two sets of experiments (Fig. 6(b) and Fig. 6(c)). In Fig. 6(b) we have compared our quasi-static algorithm with the approaches proposed in [START_REF] Mosse | Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems[END_REF][START_REF] Zhu | Feedback EDF Scheduling Exploiting Dynamic Voltage Scaling[END_REF]. The influence of the overheads is tightly linked with the size of the applications. Therefore, we use two sets of applications (Applic. 1 and Applic. 2) of different sizes. Applic. 1 has the size comparable to that of the MPEG encoder and Applic. 2 has a size similar to the GSM codec. As we can observe, the proposed quasi-static voltage scaling achieves considerably higher savings than the other two approaches. Although all three approaches illustrated in Fig. 6(b) have constant online complexity (O(1)), the overhead of the quasi-static approach is considerably lower. At the same time, as shown in Fig. 6(a), the quality of settings produced by QSVS is much higher.

In Fig. 6(c) we have compared our quasi-static approach with a hy- pothetical "best possible" dynamic voltage scaling algorithm. Such a hypothetical algorithm would produce the optimal voltage settings with a linear overhead similar to that of the heuristic proposed in [START_REF] Gruian | Energy-Centric Scheduling for Real-Time Systems[END_REF] (see Tab. 2). Please note that such an algorithm has not been proposed since all known optimal solutions incur a higher complexity then the one in [START_REF] Gruian | Energy-Centric Scheduling for Real-Time Systems[END_REF]. We evaluated 10000 randomly generated task graphs. In this particular experiment we set the size of the task graphs similar to the MPEG encoder. We considered two cases: the hypothetical online algorithm is executed with the overhead from [START_REF] Gruian | Energy-Centric Scheduling for Real-Time Systems[END_REF] for V dd -only and with the overhead that would result if the algorithm is rewritten for the combined (V dd , V bs ) scaling. Please note that in both of the above cases we consider that the hypothetical algorithm performs V dd as well as V bs scaling. As we can see, the quasi-static algorithm is superior by up to 10% even to the hypothetical algorithm with the lower V dd -only overhead, while in case which is still optimistic but closer to reality of the higher (V dd , V bs ) overhead the superiority of the quasi-static approach is up to 30%. Overall these experiments demonstrate that the quasi-static solution is superior to any proposed and foreseeable dynamic voltage scaling approach. The next set of experiments was conducted in order to demonstrate the influence of the memory size used of the look-up tables on the possible energy savings with the quasi-static voltage scaling. For this experiment we have used three sets of tasks graphs with 20, 50, and 100 tasks, respectively. Fig. 7 shows the percentage deviation of energy savings with respect to an ideal online VS as a function of the memory size. For example, in order to obtain a deviation below 0.5%, a memory of 40kB is needed for systems consisting of 100 tasks. For the same quality, 20 and 8kB are needed for 50 and 20 tasks, respectively. It is interesting to observe that with a small penalty in the energy savings, the required memory decreases almost by half. For instance, for 100 tasks, the quasi-static algorithm achieves 2% deviation relative to the ideal algorithm with a memory of only 24kB. It is important to note, that in all the performed experiments we have taken into consideration the energy overhead due to the memories. This overheads have been calculated based on the energy values raported in [START_REF] Al Hashimi | Improving the Efficiency of Memory Partitioning by Address Clustering[END_REF][START_REF] Alvandpour | A 4.5-ghz 130-nm 32-kb l0 cache with a leakage-tolerant self reverse-bias bitline scheme[END_REF] in the case of SRAM memories.

In addition to the above given benchmark results, we have conducted experiments on a real-life MPEG encoder. The MPEG encoder consists Approach E(µJ) Reduc. (%) Nominal 1.63 -Static VS 1.39 15 Greedy [START_REF] Mosse | Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems[END_REF] 0.55 67 Task Splitting [START_REF] Zhu | Feedback EDF Scheduling Exploiting Dynamic Voltage Scaling[END_REF] 0.52 69 Quasi-static 0.36 78 Table 3. Optimization results for the MPEG algorithm of 25 tasks and is considered to run on a MPC750 processor. Tab. 3 shows the resulting energy consumption obtained with different scaling approaches. The first line gives the energy consumption of the MPEG encoder running at the nominal voltages. Line two shows the result obtained with an optimal static voltage scaling approach. The energy improvement in this case is approximatelly 15%. Lines 3-4 show the improvements produced using the greedy online techniques proposed in [START_REF] Mosse | Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems[END_REF][START_REF] Zhu | Feedback EDF Scheduling Exploiting Dynamic Voltage Scaling[END_REF] which achieve reductions of 67% and 69%, respectively. The last row presents the results obtained by our quasi-static algorithm that improves over the nominal consumption by 78%. The results confirm the high solution quality of the proposed quasi-static scaling technique.

Conclusions

In this paper, we have introduced a novel quasi-static voltage scaling technique for time-constraint applications. The method avoids an unnecessarily high overhead by precomputing possible voltage scaling scenarios and storing the outcome in look-up tables. The avoided overheads can be turned into additional energy savings. Furthermore, we have addressed both dynamic and leakage power through supply and body-bias voltage scaling. We have shown that the proposed approach is superior to both static and dynamic approaches proposed so far in literature. Experiments conducted on numerous automatically generated examples and real-life benchmarks demostrate the quality of the proposed technique. We have introduced our approach considering that continous voltages are available. However, the proposed technique can be easily adapted to the situation when only discrete voltage levels are available. In this case the calculation of the discrete voltage levels which replace the calculated continuous ones, as well as the consideration of the transition overheads, can be performed using the techniques proposed in [START_REF] Andrei | Overhead-Conscious Voltage Selection for Dynamic and Leakage Power Reduction of Time-Constraint Systems[END_REF][START_REF] Ishihara | Voltage Scheduling Problem for Dynamically Variable Voltage Processors[END_REF].

Figure 2 .

 2 Figure 2. Ideal online voltage scaling approach

Figure 3 .

 3 Figure 3. Quasi-static voltage scaling based on prestored look-up tables and voltage interpolation requires only 900 CPU cycles each time new voltage settings have to be calculated. Please note the complexity of the online quasi-static VS is independent of the number of remaining tasks.

Figure 4 .

 4 Figure 4. Pseudocode: Offline Algorithm

  Influence of the online overead on an ideal linear time heuristic (assuming zero overhead)

Figure 7 .

 7 Figure 7. Experimental results: deviation from ideal

Table 1 . Simulation results of different applications

 1

		140	155	10	367	394	7	159	181	13
	MPEG	731 1,700 43 4,458 8,043 45 3,869 6,439 40

Table 2 . Simulation results: Voltage scaling algorithms

 2

	Voltage scaling	AMD	SA-1100	MPC750
	algorithm	NC (k)	NC (k)	NC (k)
	OptimalVS(Vdd+Vbs, 20 tasks) [11]	8,410 1,232,552	136,950
	OptimalVS(Vdd, 20 tasks) [11]	210	32,320	3,513
	MTS Heuristic(Vdd, 20 tasks) [6]	8	84	12
	MTS Heuristic(Vdd+Vbs, 20 tasks)	40	623	73
	Greedy Heuristic(Vdd) [7]	0.9	10	1.0
	Greedy Heuristic(Vdd+Vbs)	4.9	34	3.8
	Quasi-Static(Vdd+Vbs) (proposed)	0.9	1.0	1.0

  2, the LUT look-up

		Quasi-Static Voltage Scaling
	P		O(1)		O(1) Stored offline	O(1)
			t s	f	V dd		t s	f	V dd		t s	f	V dd
			1.50 1.52 1.54	20 22 24	1.75 1.70 1.60	LUT	3.50 3.55 3.60	21 19 16	1.48 1.54 1.58	LUT	5.55 5.60 5.65	16 15 18	1.44 1.48 1.53	LUT
			1.56	26	1.80		3.65	21	1.64		5.70	20	1.57
			Interpol.		Interpol.		Interpol.
		τ 1 (1.62,-0.02)	VS	τ 2 (1.6,-0.03)	VS	τ 3 (1.56,-0.1)	VS	τ 4 (1.46,-0.2)
	0	1	2		3	4		5	6	7	θ	t

STATIC VS OFF-LINE Input

  : -execution order of tasks τ ∈ T -for all tasks τ i ∈ T :BNC i ,ENC i ,W NC i ,Ce f f i ,D i

		-NL
	Output: -Lookup tables LUT i
	01: for i = 1 to NT {
	02:	EST i ← calc earliest starttime
	03: }//end for
	04: for i = NT downto 1 {
	05:	LST i ← calc latest starttime
	06: }//end for
	07: T r ← T
	08: for all τ i ∈ T r { //ordered i=1..NT
	09:	I i ← LIST i -EIST i
	10:	j ← 0
	11:	n i ← comp interpolation points(τ i ,LST i ,EST i )
	12:	for (t s ←EST i ; t s ≤LST i ; t s ← t s + I i /n) {
	13:	t s i ← t s
	14:	(Vdd i ,Vbs i ,f i ) ← volt scaling(T r ,t s i ) //ENC based
	15: 16:	LUT i [j] ← store QS lookup(t s i ,Vdd i ,f) j ← j + 1
	17:	}//end for
	18:	T r ← T r -τ i
	19: }//end for all
	20: for all τ i ∈ T return LUT i

Algorithm: QUASI

5 )

 5 Algorithm: QUASI STATIC VS ONLINE Input: -start time t sn of next task τ n -Quasi-Static Scaling Table LUT n -number of start time interval steps n Output: -frequency and voltage settings for task τ n 01: (x,y) ← calc st interval(LUT n ,t sn ) 02: f n ← inter freq(LUT n ,x,y,t sn ) 03: Vdd n ← inter Vdd(LUT n ,x,y,t sn ) 04: Vbs n ← calc Vbs(f n ,Vdd n ) 05: return (f n ,Vdd n ,Vbs n )

	Figure 5. Pseudocode: Online Algorithm

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

Note that the numbers for BNC and WNC are lower and upper bounds observed during the profiling. They have not been analytically derived. Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

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

Acknowledgements

Alexandru Andrei was supported by CUGS swedish graduate school in computer science. Petru Eles and Zebo Peng were supported by SSF through the STRINGENT excellence center. Marcus Schmitz and Bashir Al Hashimi were supported by EPSRC under grant GR/S95770.


Sohini Dasgupta
email: sohini.dasgupta@ncl.ac.uk

Alex Yakovlev
email: alex.yakovlev@ncl.ac.uk

Modeling and Verification of Globally Asynchronous and Locally Synchronous Ring Architectures

The goal of this paper is to demonstrate a prevalent global deadlock situation resulting from a local deadlock in a GALS ring architecture. We present a novel design for building systems which will be tolerant to such deadlocks arising in the local modules. This paper, concentrates on the modeling of the proposed design methodology and its correctness is proved with the help of a public domain verification tool.

Introduction

Future VLSI systems will be based on system-on-chip concepts, involving multiple clocked domains, e.g. synchronous processor cores. The on-chip modules will be glued together by interface logic that must facilitate high speed communication between synchronous modules operating at different clock frequencies. Such heterogeneous systems have a high requirement of a reliable high speed communication scheme, and mitigation of synchronization failure. Designing systems with such characteristics is a difficult task. Globally Asynchronous and Locally Synchronous (GALS) architectures takes advantage of industry standard synchronous methodology with individual clock domains and of self timed interface to cross clock boundaries. An important issue related to designing GALS systems is the dearth of proven design methodologies for the asynchronous communication network that encapsulates each synchronous island to aid data transfer.

The design process must be based on a system model which would aid the traversal from specification to implementation. Petri net modeling allows sound representation of the functionality of the system. There exists various model checking tools to verify the correctness with respect to certain desired properties, refining the system, at every step, leading to efficient synthesis of the system. Correctness of communication protocols play a key role for GALS architectures. The traditional synchronous validation schemes, e.g. simulation and testing, are not compatible or viable to verify the correctness. Formal verification is becoming the most practical way to ensure the correctness of designs.

Point-to-point GALS architectures have been a major impediment in providing efficient throughput and greater freedom in composing existing Intellectual Property(IP) cores of different speed and different types of interfaces. The use of a simple topologies like fork, join, bus and ring, is a possible solution to the above problems. The design architecture proposed by Villiger et. al. [START_REF] Villiger | Self timed ring for globally asynchronous and locally synchronous systems[END_REF], is a step towards the right direction but has some inherent limitations. The ring transceiver in [START_REF] Villiger | Self timed ring for globally asynchronous and locally synchronous systems[END_REF], consisted mainly of two parts, a router that decides where the incoming packets have to go and an arbiter that either allows an incoming packet from the preceding ring transceiver, or allows the output port of the host circuitry to feed a packet into the ring. The ring design methodology encounters a deadlock in the entire system, if an input port of a participating synchronous module is by any way blocked or defective. The occurrence of such a phenomenon will block the whole ring, as the pipeline stages get filled up with data packets from the dead node backwards to all the senders. This drawback is deterrent to the performance and reliability of GALS architectures. This paper extends GALS multi-point scheme presented in [START_REF] Villiger | Self timed ring for globally asynchronous and locally synchronous systems[END_REF] to handle the limitations posed by the previous designs by introducing reliable intermodule communication through ring architectures and achieve maximal throughput, while preserving self-timed operation.

GALS Ring Architecture

The Overall Design

A ring architecture design which handles the problem stated in the previous section is depicted in Fig. 1(a). The ring transceiver mainly consists of a ring access controller, which decides whether to allow an incoming packet from the previous transceiver or a new data packet pushed into the channel by the output port of the host synchronous module, shown in Fig. 1(b).

The Ring Transceiver

As opposed to the ring transceiver in [START_REF] Villiger | Self timed ring for globally asynchronous and locally synchronous systems[END_REF], the proposed design of the ring transceiver does not have a router, which decodes where the incoming packet needs to go. This is solely because, the packet due to a particular module has been put onto the channel, dedicated to that module, right from the start of its journey. Therefore there are as many channels as there are synchronous modules. The ring access controller receives both the incoming data from previous transceivers and from its host circuitry, as shown in Fig. 1(b). At this point it decides whether to pass or insert data into the channel with the help of an arbiter. The input port and the output port of the synchronous modules can carry out processes concurrently as they are independent. Hence the module can send and receive data at the same time. In our design, the output port sends data packets to the input port of its host, in addition to sending it to other participating modules.

Ring Access Controller

Fig. 3 shows the Petri net (PN) representation of the ring access controller of a system consisting of three participating synchronous modules. The requests arriving from the previous transceiver, Req2 and Req3, exclusively try to win the arbiter grant on arb2. On reception of the grant signal on either PR2 or PR3, the request proceeds to latch the data to be sent to the appropriate module.

The Input Port

The PN of the channel leading to input port is depicted in the Fig. 2. There exist, dedicated channels, to each input port. The shown in the figure, the request R1 due to arrive at the input port of Module1 has no connection with the other two channels dedicated to modules 2 and 3. Hence, requests R2 and R3 continue to traverse the ring, unaffected by the failure of the input port occurrences of Module1. Hence with the above method, global deadlock arising from local deadlock can be prevented.

The Output Port

The output port generates data packets and inserts them in the channel to be transmitted to the appropriate synchronous module. Before feeding packets into the channel, the output port decides, where it is due and inserts it accordingly in the respective channels. Therefore, an additional circuitry is required to decode the addresses (not shown in the figure). The pipeline stages, on each channel, hold data sent from any module, only to liberate it after the reception of the acknowledgement signal from the receiving module. The output port either sends to or stores data on appropriate channels depending on the arbitration circuit (as shown in Fig. 3). The output port can send data packets to the input port of its host on channel InR1. This channel does not proceed to contest for an arbiter grant on arb1, since it creates its own channel and stores its data in the FIFO, and proceeds towards the input port of Module1 (shown in Fig. 2).

Verification of GALS Ring Architecture

Model checking is an approach to formal verification used to determine whether a model satisfies the system specification. The model checking can be done by using two parameters, the system model and the property that the system must satisfy. In our design, for the verification we consider 1-safe nets, i.e. a place p ∈ P may hold a maximum of one token for a certain marking. This is done to reduce the complexity of verification. The tool used to verify the design is CLP [START_REF] Khomenko | Model checking based on prefixes of petri net unfoldings[END_REF]. The choice of the verification tool is based on its expressiveness and analysis power.

There are several types of analysis that can be performed using CLP: mainly, reachability and functional analysis. Our verification procedure focuses on reachability analysis and deadlock check.

Results

This section presents the verification results of the design of the Ring Transceiver in [START_REF] Villiger | Self timed ring for globally asynchronous and locally synchronous systems[END_REF], Des1, and the new design, Des2, proposed in this paper. The results obtained when the input port of one of the participating module is faulty, in both designs, is shown in the Table below. As a first step of verification, the system models are unfolded using PUNF [START_REF] Khomenko | Model checking based on prefixes of petri net unfoldings[END_REF]. The output of PUNF is provided as input to CLP. The analysis proved that the new design was deadlock free, while the previous design experienced global deadlock. We are currently involved in the circuit synthesis of the ring transceiver.

Figure 1 .

 1 Figure 1. (a)Ring Architecture(b)Transceiver

Figure 2 .

 2 Figure 2. Input channel for Mod1

Figure 3 .

 3 Figure 3. PN for RAC Control Unit

  |s|=No. of States, |t|=No. of Transitions |B|= No. of conditions, |E|=No. of Events DSt=Dead States, DTr= Dead Transitions

	Mod |s| Des1 60 39 1526 799 |t| |B| |E| Des2 50 35 2034 947	DSt DTr Live √ √ x x x √

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


Balkaran Gill

Michael Nicolaidis

Francis Wolff

Chris Papachristou

Steven Garverick

An Efficient BICS Design for SEUs Detection and Correction in Semiconductor Memories

In this paper we propose a new Built in Current Sensor (BICS) to detect single event upsets in SRAM. The BICS is designed and validated for 100nm process technology. The BICS reliability analysis for process, voltage, temperature, and power supply noise are provided. This BICS detect various shapes of current pulses generated due to particle strike. The BICS power consumption and area overhead are also provided. This BICS found to be very reliable for process, voltage and temperature variation and under stringent noise conditions.

Introduction

Memories occupy the largest block of area in modern ICs. In addition, memories are more sensitive to failures than logic, and this includes both hard and soft (transient) failures. Thus memories involve the largest amount of failures in modern ICs, becoming the major cause for reliability problems. One of the main causes of reliability reduction comes from particle strikes that create soft errors, also referred as SEUs (single event upsets) [START_REF] Granlund | Soft error rate increase for new generations of srams[END_REF][START_REF] Roche | Comparisons of soft error rate for srams in commercial soi and bulk below the 130-nm technology node[END_REF][START_REF] Dodd | Neutron-induced latchup in srams at ground level[END_REF]. With past technologies, this problem was limited to radiation hostile environments like in space. However, with very-deepsubmicron technologies (VDSM), aggressive device size and power supply reductions have impacted severely circuit sensitivity, as they reduced aggressively the critical charge of memory cells. Thus, low energy particles can flip memory cells, making memories sensitive to atmospheric neutrons as well as to alpha particles created by unstable isotopes that can be found in the materials of a chip. Thus, soft errors are today a concern even at ground level, at least for those applications where reliability is an important attribute. To maintain acceptable reliability levels in memories, Error Correcting Codes (ECC) are often used to detect and correct SEUs. But ECCs may cause significant area, per-formance and power dissipation penalties. Also, ECC only detects and corrects the error at the time the faulty word is being read, and not when it occurs. In large memory systems, there can be a long latency between the occurrence of the SEU and the error correction, which can cause accumulation of SEUs, can invalidate the error detection and correction capabilities of ECC.

To cope with these drawbacks, an approach using asynchronous Built in Current Sensor (BICS) on the vertical power lines of a memory and parity bit per memory word was used in [START_REF] Calin | Upset-tolerant cmos sram using current monitoring: Prototype and test experiments[END_REF]. The BICS is asynchronous, since the occurrence of particle strikes is random in time. This makes the BICS design more difficult than synchronous BICSs proposed for detecting permanent faults. During a particle hit that flips a memory cell, the BICS placed on the power lines feeding the cell detect the abnormal current dissipation, and locates the faulty column. The parity bit allows locating the faulty word and correcting the error. Because SEUs are detected as soon as they occur, error detection latency is eliminated. At the same time, the area overhead is reduced drastically with respect to ECC (since we use a single parity bit per memory word, and a single BICS for every two memory columns. Further, speed penalty is eliminated, since we do not need to check the read data at each read cycle. The work in [START_REF] Calin | Upset-tolerant cmos sram using current monitoring: Prototype and test experiments[END_REF], uses a BICS that induces a 300mV voltage drop on the V dd and 400mV on the Gnd lines. This sensor was designed with an old technology and its operation was not validated for voltage, temperature and process variations and for different shape of current pulses.

The aim of this work is to propose a new BICS which is designed for current CMOS process (100nm), operates reliably under wide voltage, temperature, and process variations, as well as stringent noise conditions. At the same time, the new BICS is also smaller than the previous one, and dissipates less power. Another important characteristic is that the voltage drop induced by the new BICS on the V dd and Gnd lines is only 7.5mV and 8.5mV, respectively. Thus, the new BICS will not affect the noise margins of the memory, which is not the case for the old one. Note also that these characteristics make our BICS approach practical, while this is not a case in earlier BICS approaches monitoring logic parts [START_REF] Tsiatouhas | A hierarchical architecture for concurrent soft error detection based on current sensing. On-line testing workshop[END_REF]. The reason is that in logic parts a large number of gates switch concurrently, creating a huge transient current. This results in a high voltage drop and noise in the power supply making the BICS impractical. Solutions using a BICS per a small number of gates are also impractical, due to the high area cost. In contrast, in our approach, only one memory cell can be active per memory column, resulting on a small transient current and a small voltage drop.

This paper is divided into following sections. Section 2 discusses about the SEUs in SRAM cell. Section 3 discusses proposed new BICS to detect SEUs in SRAM in contrast with BICS of [START_REF] Calin | Upset-tolerant cmos sram using current monitoring: Prototype and test experiments[END_REF]. Section 4 discusses the simulations mechanism and SPICE simulation results when different shapes of current pulses are injected at the sensitive node of the memory cell. Section 5 describes BICS reliability for process, voltage and temperature variations and power supply noise. This section also discusses about the power dissipation of BICS. Section 6 presents comparisons between new BICS and BICS of [START_REF] Calin | Upset-tolerant cmos sram using current monitoring: Prototype and test experiments[END_REF]; we conclude in section 7.

Single Event Upsets in SRAM

A Single Event Upset (SEU) in the SRAM cell occurs when a charged particle strikes at the sensitive node and flips the state of the SRAM cell. These charged particles are present in the space environment as cosmic rays and also within the chip as α-particles. With advanced silicon technologies, SEUs can also be created at ground level by secondary particles created during the interaction of atmospheric neutrons with die materials. The α-particles are emitted due to the radioactive decay of uranium and thorium impurities present in the chip materials and interconnects. SEUs in the memory cause logic error as they change the logic value stored in the cell by flipping it from 1 to 0 or 0 to 1. The is temporary i.e. the cell is not permanently damaged and it can be rewritten in the next memory write cycle.

Every memory cell has two sensitive nodes, the drain of the OFF-NMOS transistor and drain of the of the OFF-PMOS transistor. The drain and substrate of the OFFtransistor create a reverse-biased junction. The reversebiased junctions of the cell are most sensitive nodes to the particle strike. Immediately followed by the particle strike, charges generation and collection occur. Electrons and holes are generated when the particle passes through the depletion region formed between the drain and substrate of the OFF-transistor. The generated charges are collected at the opposite voltage terminals of the reverse-biased junction i.e. electrons move towards positive voltage and holes move towards negative voltage. The movements of charges cause a current pulse at the struck node. The memory cell flips when the collected charge, Q, is more than the charge stored at the struck node. The minimum charge required to flip the cell is called Q crit . The Q crit not only depends on the collected charge but also on the shape of the current pulse. The current pulse is represented by an equivalent current source between the drain and the substrate of the transistor [START_REF] Murley | Soft-error monte carlo modeling program, semm[END_REF][START_REF] Hazucha | Neutron induced soft errors in cmos memories under reduced bias[END_REF][START_REF] Anghel | Cost reduction and evaluation of a temporary faults detecting technique[END_REF][START_REF] Messenger | Collection of charge on junction nodes from ion tracks[END_REF][START_REF] Vargas | Seu -tolerant sram design based on current monitoring[END_REF][START_REF] Gill | Soft delay error effects in cmos combinational circuits[END_REF].

A 1 to 0 flip is defined as when a particle strike discharges the charge stored at the drain of the OFF-NMOS transistor, and similarly 0 to 1 flip is defined as when a particle strikes at the drain of the OFF-PMOS transistor. As technology scales down, the charge stored at the sensitive nodes of the memory cell is reduced because Q node = C × V dd making SRAM more prone to soft errors.

New Built in Current Sensor

Figure 1 shows the BICS used in [START_REF] Calin | Upset-tolerant cmos sram using current monitoring: Prototype and test experiments[END_REF]. This BICS is a high-speed current-mode comparator which detects transient current pulses and provides logic level output to set the asynchronous latch. This BICS is composed of two current comparators and an asynchronous latch. The comparator I UH is symmetrical counterpart of the comparator I UL . The fundamental operation of the BICS is based on the current controlled current switches. The transistor T L1 in I UL comparator is turned off when upset current I UL flows into the source of this transistor. Similarly, the upset current I UH causes to turn off transistor T H1 . Turning off these transistors under the upset current flow is very sensitive to process, voltage and temperature variations making the BICS very sensitive to these variations. This BICS also reduces the noise margins of the memory cell as it causes voltage drop around 300mV on V dd and 400mV on Gnd lines.

To overcome these limitations, we have designed a new BICS which uses current mirror and current source load inverter to amplify the upset current pulse and convert it into logic level voltage pulse. Figure 2 depicts the new BICS, Svdd in this figure is a 1 to 0 flip detector which detects and amplifies a transient current pulse generated due to 1 to 0 flip and provides logic level voltage pulse. For 0 to 1 flip detection, Sgnd is used which is a symmetrical counterpart of Svdd. The logical pulses provided by Svdd and Sgnd are used to set an asynchronous latch. The BICS provides V dd and Gnd for the whole column of the memory cell.

Svdd is formed using transistors

M V 1 -M V 8 .
Transistors M V 1 and M V 2 forms a n-channel current mirror and M V 7 with M V 8 makes current source load inverter. Transistors M V 5 and M V 6 are the source resistors for the current mirror. The source current for the current mirror and current source load inverter is provided by transistors M V 3 , M V 4 and M V 8 . The biasing voltage for transistors M V 3 , M V 4 and M V 8 is provided by the reference voltage generator which is common for 8 or 16 BICS. The reference voltage generator is a simple CMOS voltage divider which provides two levels of biasing voltage, B V and B G for Svdd and Sgnd respectively. This reference voltage generator is used for ensuring correct BICS operation under power supply variations. It decreases or increases the output biasing voltage when V dd decreases or increases.

When a particle strikes at the drain of OFF NMOStransistor of the SRAM cell it causes a transient current pulse at the struck node. The current flows from the V dd to the struck node through the complementary ON PMOStransistor which is shown as I V . As I V flows from V dd to the struck node, the current through transistor M V 1 decreases. It results to a decrease of the current flowing through M V 2 , and thus to the increase of the voltage drop between drain and source of M V 2 . The drain of M V 2 is connected to the gate of M V 7 , so the difference between gate to source voltage of M V 7 increases, which results in a voltage pulse at the drain of M V 7 . This voltage pulse is again amplified to the full logic level at node E V by the inverter formed by transistors M V 9 and M V 10 . Similarly Sgnd provides a voltage pulse at node E G when particle strikes at the drain of OFF PMOS-transistor. The signals Bypass vdd and Bypass gnd are used to disable the BICS operation during memory write and read operations.

The outputs E V and E G of Svdd and Sgnd respectively are connected to the asynchronous latch. If any of the two outputs goes high, the latch is triggered and it activates the Err i signal. A reset signal is used to reset the asynchronous latch after the upset is detected and information is read from the latch for correction.

R BH R H R ' H n : 1 T H1 T H2 T H3 T H4 T H5 T H6 T H7 R ' L R L T L1 T L2 T L3 T L4 T L5 T L6
I V I G Vdd Vdd Vdd M V2 M V7 M V9 M V4 M V8 M V10 M V5 M VB M V6 M G2 M G3 M G4 M G8 M G7 M G6 M G5 M GB M V3 B V B G Asynchronous Latch Svdd Sgnd E g E v Vdd B G Reference Voltage Generator B V Vdd Figure 2. New BICS

Simulation Mechanism and Results

The BICS and memory cell was designed in 100nm process technology. The power supply voltage for this technology was used as 1.2v and the SPICE parameters were obtained from [1,[START_REF] Cao | New paradigm of predictive mosfet and interconnect modeling for early circuit simulation[END_REF]. The layout design rules were scaled to this technology according to MOSIS layout rules for 0.18µm technology.

In CMOS circuits SEUs are modeled by injecting a current pulse at the sensitive node. This pulse has rapid rise time and gradual fall time. The shape of the pulse can be approximated by the following equation proposed in [START_REF] Srinivasan | Accurate, predictive modeling of soft error rate due to cosmic rays and chip alpha radiation[END_REF].

I α (t) = Q t f -t r × (e -t t f -e -t tr ) (1)
Where Q is the charge collected due to the particle strike and t r is the time constant for initially establishing the ion track, usually assumed few pico seconds (<10ps) [START_REF] Messenger | Collection of charge on junction nodes from ion tracks[END_REF], t f is the decay time of the current pulse. In SPICE simulations, we vary both Q and t f and observe additional delay due to the α-particles strike at the output of the circuits. we are assuming t r = 5ps. Figure 3 shows the shape of the injected current pulse for different values of Q and t f with t r = 5ps For SPICE simulations, a BICS is placed at the end of the memory column. The BICS feeds power to the whole column of 128 memory cells. For 1 to 0 flip simulations, a current source is used between the drain of the OFF-NMOS transistor and the ground which applies current pulse of equation 1. Similarly for 0 to 1 flip simulations, the current source is used between V dd and drain of OFF-PMOS transistor.

I α (t) (mA) Time (ps) Q = 3fc, t f = 20ps Q = 4fc, t f = 50ps Q = 5fc, t f = 10ps Q = 6fc, t f = 90ps

Simulation Results

Figure 4 shows the SPICE simulation results for 1 to 0 flip which occurred at 50ns. The top chart shows that the memory cell flips when a current pulse is injected at the drain of OFF-NMOS transistor. This current pulse was generated using equation 1 for Q = 3fc and t f = 30ps. In this case, the particle strike flips the memory cell and the flip is detected by Svdd part of the BICS. The middle chart shows logic level output (E V ) of Svdd. The voltage pulse produced at the output of Svdd is latched in the asynchronous latch as shown in the bottom chart. Similar results were obtained for 0 to 1 flips, these results are tabulated in tables 1 and 2 for various shapes of injected current pulses. The simulation results for 1 to 0 pulses, are shown in table 1. The first column shows the amount of collected charge, Q. For every value of Q, decay time t f is varied between 10ps and 100ps using a step of 10ps. As said earlier t r is selected to be 5ps, we could vary this time from 2ps to 6ps to be sure that we cover all practical situations, but the variation of t r in such a narrow range does not affect the results. The diamonds in table 1 show the case when a particle hits a cell but the cell does not flip and the particle hit is not detected. The Stars show the case when a particle hits a cell but the cell does not flip and particle hit is detected. The triangles show the case when a particle strike flips the cell and is detected by the Svdd part of the BICS. The simulation results for 0 to 1 flip, i.e. when the particle hit at the drain of the OFF-PMOS transistor, are shown in Table 2.

We have not found current pulses that can flip the cell but the current sensors do not detect the event. Thus, the BICS scheme is very efficient for SEU detection, as we do not observe escapes. However, we observe that in some situations we have false alarms, as the BICS detects the particle hit, but the hit does not flip the cell. These false alarms could create a problem if we mis-correct a correct cell, thus creating an error. However, this situation cannot happen because no parity bit will detect an error, thus no mis-corrections will be performed. 2. Simulation results for 0 to 1 flip and PMOS transistors, respectively. The V dd was also varied from 1.08 to 1.32 volt where nominal V dd was 1.2 volt. The temperature range was -25 to 85 C. The BICS was found to work perfectly for all these variations.

Power Supply Noise analysis

To emulate the noise in the power supply, 64 inverters (very large in size) were switched simultaneously by a voltage source of 2GHz frequency. Figure 5 shows the simulation setup for the noise analysis. A common V dd and Gnd were used for the inverters, the reference voltage generator and the BICS which assures that the noise generated by the inverters propagates to the reference voltage generator and BICS. 64 inverters were chosen as they produced good amplitude of noise current in the V dd. The absolute value of this noise current was around 600mA. The SPICE simulations showed that BICS works perfectly under this noisy environment.

Power Dissipation Analysis

The power dissipation of BICS under nominal voltage and temperature is 11.32µW for the typical process parameters. Table 3 shows the power dissipation of the sensor at room temperature (T = 27C) for various process and Vdd variations. The first column shows V dd variations in the range of ±10%. The subsequent columns show 5 process From this table and given that the BICS was designed to monitor 256 memory cells in a column and one BICS is used for two columns, we can find that the extra power dissipation due to BICS for the memory. For example, for 1 Mbit SRAM architecture with 256 rows and 4096 columns, 2048 BICSs will be required so the power penalty for typical process will be 23.18 mW .

Comparisons

Table 4 shows the comparisons between our proposed BICS and one given in [START_REF] Calin | Upset-tolerant cmos sram using current monitoring: Prototype and test experiments[END_REF]. Our proposed BICS causes to reduce the noise margins in V dd and Gnd lines only 8.5mV and 7.5mV respectively which is <1% of 1.2v V dd where as BICS in [START_REF] Calin | Upset-tolerant cmos sram using current monitoring: Prototype and test experiments[END_REF] reduces noise margins around 6 % and 8% respectively for 300mV and 400mV for 5v V dd. It is to be noted that in table 4, some entries are marked as no-data. In that case the authors in [START_REF] Calin | Upset-tolerant cmos sram using current monitoring: Prototype and test experiments[END_REF] have not provided data. The biasing for the new BICS is based on voltage biasing where as for BICS in [START_REF] Calin | Upset-tolerant cmos sram using current monitoring: Prototype and test experiments[END_REF] is based on current biasing. The current based biasing needs a constant current source on the chip which is additional overhead and also cause power dissipation. The voltage based biasing in new BICS, makes it more reliable as it is easy to create biasing voltage and if the V dd varies, the biasing voltage varies so the BICS still keeps working. The number of transistors in new BICS are 27 where as for BICS in [START_REF] Calin | Upset-tolerant cmos sram using current monitoring: Prototype and test experiments[END_REF] are 34, so the area overhead of new BICS is smaller than the BICS in [START_REF] Calin | Upset-tolerant cmos sram using current monitoring: Prototype and test experiments[END_REF] The BICS in [START_REF] Calin | Upset-tolerant cmos sram using current monitoring: Prototype and test experiments[END_REF] wasn't validated for PVT, noise and current shape analysis. We have also shown power consumption by BICS for various supply voltages and process variations.

Type

new BICS BICS in [START_REF] Calin | Upset-tolerant cmos sram using current monitoring: Prototype and test experiments[END_REF] Noise

Conclusion

We have proposed a new Built in Current Sensor (BICS) to detect single event upsets in SRAM. The BICS was design and validated for 100nm process technology. The PVT and power supply noise analysis shows that BICS is reliable in harsh environment. We have provided data for power consumption by BICS and detection of different shape current pulses. The proposed BICS shows many advantages over BICS proposed in [START_REF] Calin | Upset-tolerant cmos sram using current monitoring: Prototype and test experiments[END_REF].

Figure 3 .

 3 Figure 3. The shape of the current pulse for different values of Q and t f

Figure 4 .

 4 Figure 4. SPICE simulation results for 1 to 0 flip for Q = 3fC and t f = 30ps

Q-

  Decay time, t f , (ps) (fC) 10 20 30 40 50 60 70 80 To emulate the effect of the process variation the SPICE simulations were run for V tn ±10%, and V tp ±10%, where V tn and V tp are the threshold voltages of NMOS Q Decay time, t f , (ps) (fC) 10 20 30 40 50 60 70 80 Flip and detected -No flip but detected -No flip and no detection Table

Table 3 . Power dissipation for voltage and pro- cess variations

 3

		Vdd
	2 GHz
	Voltage
	Source		Inv 1		Inv 2		Inv 64
			Ref. Volt
	Bypass_vdd	Sensor	Error_out
	Bypass_gnd	(BICS)	Reset
		Vdd'	Cell 1	Gnd'
			Cell 2
			Cell 32
		bit	bit
	Figure 5. Simulation setup for the noise anal-
	ysis of the BICS
	variations combining typical, slow and fast transistor char-
	acteristics.
	V dd(v)		Power dissipation (µW )
		TT	SS		FF	SF	FS
	1.08	6.15	4.43	8.48	6.77	5.65
	1.2	11.32 8.41 15.08 12.45 10.34
	1.32	19.27 14.67 24.95 21.16 17.58
	TT -Typical NMOS, Typical PMOS
	SS -Slow NMOS, Slow PMOS
	FF -Fast NMOS, Fast PMOS
	SF -Slow NMOS, Fast PMOS
	FS -Fast NMOS, Slow PMOS

Table 4 . Comparisons between new BICS and BICS of [3]

 4

	Margins	8.5mv, 7.5mV 300mV, 400mV
	Biasing	Voltage	Current
	Number of Transistors	27	34
	PVT analysis	Yes	No-data
	Power supply
	noise analysis	Yes	No-data
	Validated for
	different shape of
	current pulses	Yes	No-data
	Power consumption
	analysis	Yes	No-data

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)


Ludovic Pricoupenko

The three-body pseudo-potential for atoms confined in one dimension

Keywords: numbers: 34, 50, Cx 03, 65, Nk 03, 65, Ge 05, 30, Jp

Following a strong analogy with two-dimensional physics, the three-body pseudo-potential in one dimension is derived. The Born approximation is then considered in the context of ultracold atoms in a linear harmonic waveguide. In the vicinity of the dimer threshold a direct connection is made between the zero-range potential and the dimensional reduction of the three-body Schrödinger equation.

I. INTRODUCTION

At sufficiently low temperature, ultracold atoms in very elongated harmonic traps can be considered as in a one-dimensional (1D) geometry. For bosons, the idealization of the trap in terms a 1D harmonic waveguide permits one to achieve a mapping with the Lieb-Liniger model [1,2]. In this context, few-body systems in 1D attracted recent interest [3][4][5][6]. As a consequence of the Yang-Baxter criterion [START_REF] Sutherland | Beautiful Models, 70 Years of Exactly Solved Quantum Many-Body Problems[END_REF], the three-body problem occupies also a central place in studying the breakdown of integrability in these systems [START_REF] Mazets | [END_REF][9][10][11]. Interestingly, virtual excitations of pairs of atoms in the transverse modes of the waveguide led to the introduction of a 1D zero-range three-body force [START_REF] Mazets | [END_REF]9]. This force has important consequences in the prediction of a 1D dilute liquid state [12,13]. Moreover, it permits one to predict the existence of an excited trimer state in the vicinity of the dimer threshold [14,15]. This prediction coincides exactly with the one derived directly from the dimensional reduction of the 3D Schrödinger equation in the presence of a 1D waveguide [16].

In Ref. [15] a renormalization procedure is used to cure the divergencies coming from the bare zero-range threebody force. In Ref. [14] a three-body contact condition is used instead, to implement the zero-range model. These two-last studies lead to exactly the same reduced equation of the three-body problem, referred hereafter as the 1D Skorniakov Ter-Martirosian (STM) equation. Nevertheless the 1D STM equation in Ref. [16] differs from the later even though, the same prediction for the excited trimer state is obtained near the dimer threshold.

In this work, a three-body zero-range pseudo-potential leading to a mathematically well-behaved problem is derived both in configuration (section II) and in momentum space (section III). The pseudo-potential has the same form than the two-body Λ-potential in the twodimensional (2D) space [17]. In section IV, the STM equation for three-bosons interacting via the two-and the three-body zero-range forces is derived. This STM equation is identical to the one obtained in Refs. [14,15]. The Λ parameter of the pseudo-potential can be any positive real. However the first order Born approximation breaks this Λ-freedom and a specific value of Λ permits to re-cover the renormalized strength of the zero-range force in section V. Finally in section VI, the equivalence between the zero-range 1D model and the dimensional reduction method is obtained in the vicinity of the dimer threshold where the Born approximation is accurate.

II. REGULARIZED ZERO-RANGE THREE-BODY FORCE

In this section the 1D three-body contact potential is introduced in complete analogy with the 2D two-body problem. Let us consider three particles of same mass m labeled by the index i ∈ (1, 2, 3). The positions of the three particles are given by the coordinates z i . The center of mass of the system is C = (z 1 + z 2 + z 3 )/3 and the two other Jacobi coordinates are

z ij = z i -z j ; Z ij = 2 √ 3 z k - z i + z j 2 , (1)
where all the index i, j, k are distinct and are a cyclic permutation of the triplet (1, 2, 3). The general form of the zero-range three-body potential can be written as

V pp 3 Ψ(z 1 , z 2 , z 3 ) = 2 m δ(z 12 )δ(z 23 )ψ 3 (C). (2)
the function C|ψ 3 , is denoted hereafter as the threebody contact. It will will be shown later that it characterizes the singular behavior of the wavefunction at the contact of the three particles. For a given pair (ij), one introduces the hyper-radius R = Z 2 ij + z 2 ij and the hyper-coordinates R = z ij êz + Z ij êZ , where (ê z , êZ ) is an orthonormal basis. The potential in Eq. ( 2) can be expressed as

V pp 3 Ψ(z 1 , z 2 , z 3 ) = 2 2 m √ 3 δ 2 (R)ψ 3 (C). (3)
Due to its s-wave character, the expression of the zerorange potential in Eq. (3) does not depend on the choice of a specific pair of particles in the definition of the hyper-coordinate R. For the bare three-body zero-range potential used for example in Ref. [15], the three-body contact ψ 3 (C) is just the value of the wavefunction at the contact of the three particles. However, similarly to the two-dimensional Green's function, for a given value of the three-body contact, the two-dimensional delta distribution in Eq. ( 3) gives rise to a logarithmic singularity of the wavefunction at

R = 0: Ψ(z 1 , z 2 , z 3 ) ∼ ln (R/l) πψ 3 (C)/ √ 3 + . . .
where l is a characteristic length of the system. The bare zerorange potential leads thus to a mathematically not wellbehaved model. In practice, the bare potential can be used in the Born approximation, where the wavefunction at first order is regular at the contact [13]. When the bare potential is used non perturbatively as in Ref. [15], a renormalizing procedure of the strength is necessary. In order to construct a zero-range pseudo-potential, one has to introduce a regularizing operator such that when applied to the wavefunction considered, it gives a finite value of the three-body contact. For this purpose, one fixes the later characteristics length l by imposing a boundary condition at the contact of the three particles as R → 0 for all the wavefunctions solution of the Schrödinger equation:

Ψ(z 1 , z 2 , z 3 ) = ψ 3 (C) π √ 3 ln R a 3 + . . . ( 4
)
where a 3 is the 1D three-body scattering length. This boundary condition has been already introduced for the three-body problem in 1D in Ref. [14]. Equations ( 3) and ( 4) are formally equivalent to the definition of a zerorange force in the 2D two-body problem [17,18]. For instance, in the free 1D space and in absence of two-body force, one finds from the contact condition in Eq. ( 4) one trimer at energy

E 3 = -4e -2γ 2 ma 2 3
, analogous to the dimer in 2D for a zero-range potential.

It is then straightforward to use for the three-body zero-range force, the known expression of the 2D Λpotential that encapsulates the contact condition of Eq. ( 4):

V pp 3 Ψ(z 1 , z 2 , z 3 ) = -π √ 3 2 m ln (e γ Λa 3 /2) δ(z 12 )δ(z 13 ) lim R→0 1 -ln e γ ΛR 2 R ∂ ∂R Ψ(z 1 , z 2 , z 3 ). ( 5
)
The parameter Λ in the pseudo-potential of Eq. ( 5) is any positive number, i.e. for any value of Λ, the pseudopotential imposes the contact condition of Eq. ( 4). In Eq. ( 5), one identifies the Λ-dependent strength

g 3 (Λ) = -π √ 3 2 m ln (e γ Λa 3 /2) (6)
and the regularizing operator

C|R Λ |Ψ = lim R→0 1 -ln e γ ΛR 2 R ∂ ∂R Ψ(z 1 , z 2 , z 3 ). ( 7
)
One can verify that for a state satisfying the contact condition in Eq. ( 4), one recovers as expected the strength of the zero-range force with g 3 (Λ)

C|R Λ |Ψ = 2 m ψ 3 (C).

III. THREE-BODY PSEUDO-POTENTIAL IN THE MOMENTUM REPRESENTATION

In what follows, the three-body zero-range pseudopotential is derived in the momentum representation. The momentum of the three particles are denoted by k i . To avoid any ambiguities with the equations in configuration space, the bra-ket notation will be used below. The analogy with the two-body problem in 2D can be pursued and the derivation follows along the same lines as in Refs. [19,20]. For this purpose, one defines the Jacobi coordinates in the momentum space. The momentum of the center of mass is

k C = k 1 + k 2 + k 3 .
The two other Jacobi coordinates are defined by

k ij = k i -k j 2 ; K ij = 2k k -(k i + k j ) 3 . (8)
In what follows, the notations k = k 12 and K = K 12 are used. Similarly to what has been done in the previous section, one introduces the hyper-momentum

Q = ku z + √ 3 2 Ku Z . (9)
The stationary Schrödinger equation at energy E, for a system with only one interaction term given by the threebody force of Eq. ( 2) is in the momentum space

Q 2 + k 2 C /6 + mE/ 2 Q, k C |Ψ = -k C |ψ 3 . (10
) Equation (10) gives the high momentum behavior of the wavefunction for all energies and also in the possible presence of other non singular three-body potential. The three-body contact can be thus defined in the momentum representation by

k C |ψ 3 = -lim Q→∞ Q 2 Q, k C |Ψ . (11)
Let us consider the Green's function at the negative energy -2 Λ 2 /m in the center of mass frame, for a vanishing hyper-radius (R → 0):

d 2 Q (2π) 2 exp (iQ • R) Q 2 + Λ 2 = - 1 2π ln e γ RΛ 2 + . . . (12)
Equation ( 12) can be used for any positive value of the parameter Λ and permits one to express the three-body contact condition in Eq. ( 4) as

2 √ 3 d 2 Q (2π) 2 Q, k C |Ψ + k C |ψ 3 Q 2 + Λ 2 = 2 k C |ψ 3 mg 3 (Λ) .
(13) From Eqs. (2) and ( 13), one can deduce the three-body pseudo-potential in the momentum representation

k 1 , k 2 , k 3 |V pp 3 |Ψ = g 3 (Λ) k C |R Λ |Ψ . ( 14
)
where

k C |R Λ |Ψ = 2 √ 3 d 2 Q (2π) 2 Q, k C |Ψ + k C |ψ 3 Q 2 + Λ 2 . ( 15
)
IV. STM EQUATION

In this section the bound states made of three identical bosons are considered. The three particles interact via the three-body pseudo-potential of Eq. ( 14). Moreover, each pair of particles (ij) interact via the zero-range potential of the Lieb-Liniger model :

V (z ij ) = - 2 2 ma 2 δ(z ij ), ( 16
)
where a 2 is the 1D two-body scattering length. One introduces the two-body contact, which corresponds to the value of the wavefunction at the contact of two particles considered. For the contact of the pair ( 12), one has in the momentum representation :

K, k C |ψ 2 = dk 2π k, K, k C |Ψ . (17)
In the center of mass frame the wavefunction can be factorized as m is thus

k, K, k C |Ψ = (2π)δ(k C ) k, K|φ
k 2 + 3 4 K 2 + q 2 k, K|φ = -S 3 + 2 a 2 ( K|S 2 + -k -K/2|S 2 + k -K/2|S 2 ) . ( 18
)
The STM equation follows from Eq. ( 18) after integration over the relative momentum k:

  a 2 - 1 q 2 + 3K 2 4   K|S 2 + a 2 S 3 4q 2 + 3K 2 = 4 dK ′ 2π K ′ |S 2 K 2 + K ′ 2 + KK ′ + q 2 . (19)
Injection of Eq. ( 18) in the contact condition (13) gives

3 a 2 dK 2π K|S 2 3 4 K 2 + q 2 = - S 3 ln(qa 3 e γ /2) π √ 3 . ( 20
)
This last relation permits to close Eq. ( 19) and to recover the set of equations for the two-body contact obtained in Refs. [14,15]. Remarkably, an exact implicit equation on the binding wavenumber q has been derived from Eqs. ( 19) and (20) in Ref. [13].

V. Λ-DEPENDENT AND RENORMALIZED STRENGTHS

In Ref. [15], a renormalization of the bare three-body interaction is used for the derivation of the trimer spectrum as a function of the ratio between the two scattering length a 3 and a 2 . Interestingly, the renormalized strength introduced in Ref. [15] for a bound state of binding wavenumber q coincides with g 3 (q) [21]. In the point of view of the pseudo-potential, this corresponds also to the value Λ = q in the regularizing operator. For this choice, the explicit dependence on the three-body contact in Eq. ( 15) is exactly canceled. In the following lines, it is shown that this choice is relevant for the first Born approximation of the zero-range pseudo-potential.

Let us consider a regime where the three-body pseudopotential gives a small contribution in the eigenenergies. In the center of mass frame, the eigenstate can be decomposed in two parts:

|φ = |φ (0) + |δφ , (21)
where |φ (0) is an eigenstate of the three-body problem without the three-body pseudo-potential. The wavefunction φ (0) (z 1 , z 2 , z 3 ) is thus regular at the contact of the three-particles and the singular behavior is solely included in the perturbation |δφ . In the momentum space, the perturbation Q|δφ is much smaller than Q|φ (0) except in the high momentum limit where

Q|δφ ∼ - S 3 Q 2 + q 2 . (22)
Equation ( 22) is valid above a given Q 0 i.e. for Q > Q 0 ≫ q. However, for Λ = q, the contribution in Eq. ( 22) is exactly canceled in the regularization and

R Λ=q |φ ∼ 2 √ 3 d 2 Q (2π) 2 Q|φ (0) = φ (0) (R = 0). (23)
Thus, in this perturbative regime the choice Λ = q permits one to recover the Born approximation of the bare zero-range potential where 1/| ln(qa 3 )| is the small parameter.

VI. THREE-BODY PROBLEM NEAR THE DIMER THRESHOLD IN A 1D WAVEGUIDE

In the case of a 1D harmonic atomic waveguide, the effect of virtual excitations of pairs of particles in the direction transverse to the free motion breaks the integrability in the many-body quasi-1D problem. For taking this effect into account, it is necessary to introduce a perturbation to the Lieb-Liniger model. It has been shown that this perturbation can be modeled at the first order Born approximation by a zero-range bare three-body potential with the strength [START_REF] Mazets | [END_REF]:

g Born 3 = - 6 2 a 2 ⊥ ma 2 2 ln 4 3 , (24)
where a ⊥ = 2 /(mω) is the characteristic length of the waveguide.

When the 2-body scattering length a 2 is large and positive, i.e. at the threshold of the dimer of binding wavenumber 1/a 2 , the Lieb-Liniger model predicts a shallow trimers (the McGuire trimer) in the 1D waveguide. Virtual excitations of pairs of particles induce a perturbation of this trimer of binding wavenumber q = 2/a 2 [START_REF] Mcguire | [END_REF]. This last wavenumber gives the momentum scale of the parameter Λ chosen when the Born approximation is achieved on the pseudo-potential. At the leading order of logarithmic accuracy, one can then identify the bare strength in Eq. ( 24) with g 3 (Λ) and Λ = 1/a 2 . One finds ln(a 3 /a 2 ) ∼ Importantly, the asymptotic law near the threshold for the two trimers coincide exactly with the ones found from the dimensional reduction of the 3D Schrödinger equation in presence of an harmonic waveguide [14][15][16]:

q 0 ∼ 2 a 2 + 4a 2 ⊥ a 3 2 ln 4 3 ; q 1 ∼ 1 a 2 + 2a 4 ⊥ 3a 5 2 ln 2 4 3 , (25)
where q 0 and q 1 are the binding wavenumbers.

In the dimensional reduction method of Ref. [16], there is no three-body force in the Hamiltonian and the quasi-1D character of the system is revealed by a summation over the transverse mode in the STM equation:

  1 3 4 K 2 + q 2 -a 2   K|S 2 = -2 dK ′ π ∞ n=0 1 4 n K ′ |S 2 4n a 2 ⊥ + q 2 + K 2 + K ′ 2 + KK ′ . ( 26
)
The momentum 1/a ⊥ plays the role of a cut-off in the integral term of Eq. (26). In the limit where the momentum K, K ′ and q are much smaller that 1/a ⊥ , one has

∞ n=1 1 4 n 1 4n a 2 ⊥ + q 2 + K 2 + K ′ 2 + KK ′ ∼ ln 4 3 a 2 ⊥ . (27)
The approximation in Eq. ( 27) was the one used for the derivation of the asymptotic law for the two trimers in Eq. ( 25). In what follows it is shown that this approximation is equivalent to the Born approximation of Eq. ( 24) performed with the zero-range pseudo-potential.

For that purpose, one considers formally the effective three-body potential V 3 whhich gives Eq. (26). The Hamiltonian is

H = - 2 2m 3 i=1 ∂ 2 ∂z 2 i - 2 2 ma 2 i<j≤3 δ(z ij ) + V 3 . (28)
The absence of singular behavior of the eigenstates of Eq. ( 26) shows that necessarily the potential V 3 is nonlocal in the configuration space. One can remark that the regime where the two-body contact K|S 2 is negligible for a momentum K of the order of 1/a ⊥ , corresponds to the regime where the zero-range three-body force can be treated in the Born approximation. Then using the approximation Eq. ( 27), one finds an energy dependent potential valid in the Born approximation. For an hypermomentum Q 1/a ⊥ , one can write in the center of mass frame

k, K|V 3 |φ = - 2 m π ln(4/3)(k 2 + 3 4 K 2 + q 2 ) a 3 ⊥ a 2 × < dk ′ dK ′ (2π) 2 k ′ , K ′ |φ (29)
and k, K|V 3 |φ ∼ 0 for Q 1/a ⊥ . In Eq. ( 29), < means an integration in the domain where the hyper-momentum

Q ′ = k ′ 2 + 3 4 K ′ 2
is smaller than 1/a ⊥ . Multiplying Eq. ( 29) by φ|k, K and assuming that V 3 is a small perturbation, one can use the relation

φ|H 0 -E|k, K ∼ 2 2 ma 2 ( S 2 |K + S 2 | -k -K/2 + S 2 |k -K/2 ) . ( 30
)
The integration of the resulting equation on the hypermomentum in the domain Q < 1/a ⊥ gives the expectation value of the effective three-body potential in the center of mass frame :

φ|V 3 |φ ∼ - 6 2 a 2 ⊥ ma 2 2 ln 4 3 |φ(R = 0)| 2 . ( 31
)
One thus recovers the same strength of the three-body potential as the one of the zero-range model in the Born approximation in Eq. (24).

VII. CONCLUSION

The three-body Λ-potential introduced in this paper leads to a mathematically well-behaved Schrödinger equation, avoiding thus a renormalization procedure of a bare zero-range force. This pseudo-potential is used in the context of atoms in a 1D waveguide where the virtual excitations in the transverse modes give rise to an effective zero-range three-body force in addition to the usual two-body force of the Lieb-Liniger model. For the three-body problem, in the limiting case of a large two-body scattering length, a three-body potential is obtained from the STM equation derived directly from the 3D Schrödinger equation in the presence of a 1D waveguide. This potential treated at the Born approximation explains the equivalence found near the dimer threshold, between the zero-range potential approach and the direct method of Ref. [16].

  . The two-and three-body contact are also factorized as K, k C |ψ 2 = (2π)δ(k C ) K|S 2 and k C |ψ 3 = (2π)δ(k C )S 3 . The three-body Schrödinger equation for a bound state of energy E = -2 q 2

a 2

 2 → ∞. In this regime, in presence of the three-body potential, in addition to the perturbed McGuire state, another trimer is found near the atom-dimer continuum.