Soumeya Leila Hernane

Jens Gustedt

Mohamed Benyettou

A Dynamic Distributed Algorithm for Read Write Locks (extended abstract) *

Keywords: Distributed locks, read-write locks, dynamic locking

In this paper, a new algorithm that extends Naimi-Trehel token-based mutual exclusion is proposed. Contributions are twofold. First, our algorithm evolves within an changing environment; processes can join and leave the system while the parent tree is in ongoing transformation and, while requests accessing the critical section are inserted. Both the tree structure and the original algorithm are amended. We impose new rules and add new variables to the original structure, so as to maintain the connectivity of the parent tree as well as the Next chain, whatever circumstances. Second, the possibility to share the token between processes is introduced. This allows either multiple concurrent readers or a single writer to enter the critical section. In the Next chain of successive readers, a newly introduced Reading handler ensures that all following requesters for read access may enter the critical section simultaneously, and keeps the token as long as at least one reader is in the critical section. In all cases, our approach can be implemented such that it keeps an average complexity of O(log(n)) messages per request.

Un algorithme pour la gestion dynamique de verrous lecture/écriture (résumé étendu)

Résumé : Nous proposons dans ce papier une extension de l'algorithme d'exclusion mutuelle, à base de jeton de Naimi-Tréhel. Notre contribution se présente sous deux angles différents. Premièrement, notre algorithme progresse dans un environnement inconstant. Les processus peuvent joindre et quitter le système. En même temps, l'arbre parent subit des transformations au fur et à mesure que les requêtes d'accès à la section critique sont insérées. Les modifications portent aussi bien sur l'algorithme que sur la structure arborescente parent ainsi que sur la chaîne Next.

De ce fait, Nous imposons de nouvelles règles et de nouvelles variables aux structures de départ, de sorte que la connexité de l'arbre parent ainsi que celle de la chaîne Next soient maintenues.

Deuxièmement, nous rendons possible l'agencement du jeton partagé à l'exclusif. Ainsi, la section critique devient accessible, soit par plusieurs lecteurs concurrents soit par un seul écrivain. Dans la chaîne Next. le gestionnaire des lecteurs est introduit pour assurer l'entrée en section critique de tous les lecteurs successifs. De même, le gestionnaire des lecteurs garde le jeton partagé tant qu'au moins un lecteur est en section critique.

Dans tous les cas de figure, l'implantation de notre approche garantit une complexité logarithmique de l'ordre de O(log(n)) messages par requête.

Mots-clés : verrou repartie, verrous lecture/écriture, verrouillage dynamique

Introduction and Overview

Several protocols have been proposed in the literature to solve mutual exclusion problems within distributed systems. They can be either permission-based (Lamport [START_REF] Lamport | Ti clocks, and the ordering of events in a distributed system[END_REF], Maekawa [START_REF] Maekawa | An algorithm for mutual exclusion in decentralized systems[END_REF], Ricart-Agrawala [START_REF] Ricart | An optimal algorithm for mutual exclusion in computer networks[END_REF]) or token-based , Raymond [START_REF] Raymond | A tree-based algorithm for distributed mutual exclusion[END_REF]). The first set allows entering the critical section (CS) after receiving permission from other nodes. They incur a high communication overhead. The second set conditions the entrance into the CS by the possession of a token which is passed between nodes. They differ from each other in the way the request messages are routed to reach the token. This group of algorithms is tree-based and many of them exhibit a O(log (N)) complexity in terms of the number of messages per request. Our work focuses on this class of algorithms for the sake of this message complexity.

The distributed algorithm of Naimi-Trehel [START_REF] Naimi | How to detect a failure and regenerate the token in the log(N ) distributed algorithm for mutual exclusion[END_REF] based on path reversal is the benchmark for mutual exclusion. In this paper, we will merely refer to it in the version of Naimi-Trehel-Arnold [START_REF] Naimi | A log(N ) distributed mutual exclusion algorithm based on path reversal[END_REF], that additionally provides the proofs for the properties that we will use. Many other extensions of this algorithm have been proposed in the literature, we mention a few of them. A Fault tolerant token based mutual exclusion algorithm using a dynamic tree was presented by Sopena [START_REF] Sopena | A fault-tolerant token-based mutual exclusion algorithm using a dynamic tree[END_REF]. It improves over by ensuring a lower cost in terms of messages in the presence of failures. Quinson-Vernier [START_REF] Quinson | Byte-range asynchronous locking in distributed settings[END_REF] provide a byte range asynchronous locking of the Naimi-Trehel algorithm based on sub-queues when partial locks are requested. Wagner-Mueller [START_REF] Wagner | Token-based read/write-locks for distributed mutual exclusion[END_REF] have proposed token based read-write locks for distributed mutual exclusion. The protocol distinguishes read and write requests and presents good performance. However, up to our knowledge it has no proof of safety and liveness. In [START_REF] Mohamed | Distributed concurrent control with readers and writers[END_REF], Mohamed & Naimi have proposed a solution of Readers/Writers in the distributed systems. A specification of the algorithm was given by predicates used to express the axioms and in order to prove the algorithm. However, the complexity has not been studied. Based on the same assumptions as the original algorithm of Naimi-Trehel, this work presents an extended algorithm. Gustedt's DHO [START_REF] Gustedt | Data handover: Reconciling message passing and shared memory[END_REF] presents a theoretical programming paradigm and an interface, for locking and mapping data in both read and write modes. It neither provides nor forces any particular algorithm or protocol read-write locks that would be used by that abstract interface.

Contributions in this paper are twofold. First, we extend the original Naimi-Trehel algorithm so that the parent tree and the Next chain (for definitions of these terms please see the original Naimi-Trehel algorithm [START_REF] Mohamed | Distributed concurrent control with readers and writers[END_REF]) evolve in a dynamic environment, while maintaining safety and liveness properties, see Section 2. Second, in addition to exclusive locks hold by a single writer, we allow multiple readers to enter the CS, so that the algorithm covers both exclusive and concurrent locks, Section 3. In this framework, we propose a new data structure that handles additional features. Finally, in Section 4 we conclude, in particular to advertise the use of this approach within an API that handles resources in large scale distributed systems.

Mutual exclusion algorithm with volatile processes

The Naimi-Trehel algorithm is based on a distributed queue along which the token circulates, and on a distributed tree structure for queries. The query tree is rooted at the tail of the queue to allow to append new requests to the queue at any moment. The basics of the Naimi-Trehel algorithm can be found in [START_REF] Naimi | How to detect a failure and regenerate the token in the log(N ) distributed algorithm for mutual exclusion[END_REF].

Concurrent requests

Within Naimi-Trehel's algorithm, a given parent p 1 of two processes p 2 and p 3 can be queried simultaneously by both. In such case, if p 1 treats p 2 first, p 3 is put on hold and is disconnected temporarily from the tree. An example from [START_REF] Naimi | How to detect a failure and regenerate the token in the log(N ) distributed algorithm for mutual exclusion[END_REF] is shown in Fig. 1. Initially, Fig. 1(a), p 1 holds the token and p 3 claims the CS by sending a request to its parent. in turn, p 1 updates its parent and its Next to p 3 , Fig. 1(b). Then, p 2 and p 5 claim the CS. They send request to p 1 and set forthwith their parent to null. So, p 1 points towards p 2 and forwards the request to p 3 , Fig. 1(c). Meanwhile, p 5 waits and is disconnected from the tree.

Once p 1 sent p 2 's request to p 3 , it switches to p 5 's request. Thus, it forwards the request to p 2 and sets its parent to p 5 . Meanwhile, p 2 is cut from the tree, Fig. 1(d). In Fig. 1(e), p 2 's request is achieved and p 5 's ends in Fig. 1(f).

We notice that, processes set their parent variable to null as soon as they forward the request. Within a system of n processes, n-1 processes may request the token concurrently and this will generate n disjoint parent's trees. This example was presented in [START_REF] Naimi | How to detect a failure and regenerate the token in the log(N ) distributed algorithm for mutual exclusion[END_REF] in the context of node failures. In our proposal, processes handle one request at a time (Section 2). We provide an extension of the algorithm that allows processes to enter or to leave the system. Note that if a process wants to enter the group, it just has to choose a relative parent to join the tree. It will then be connected to the system. So the difficulty in node dynamicity lies in the departure of processes, to which we thus focus in the sequel.

To that aim, we amend the original algorithm by requiring that processes are never cut from the parent tree, whatever the circumstances. This helps to keep all links alive if a given process leaves the system. We assume that a process does not support a new request before the previous one is completed.

Atomic Operations

In this subsection we amend the structure and query processing of the mutual exclusion algorithm, such that we avoid overlapping of operations that relate to a given process p i . In order to meet new requirements of the extended algorithm, we add to the set of variables as defined above: Inria Send: A Boolean that refers to the process state, initially set to false. If true, then the process has sent a request that is not completed.

Req: A list of received requests by a process, initially empty.

Wait ack: A Boolean that refers to an acknowledgment (ACK) set by a given process, initially set to false.

Previous: Each process knows who will hold the token before him, it is easily updated simultaneously as Next. Next and Previous form a doubly linked list.

Let {p 1 ..p i ..p n } a finite set of processes within a distributed system. Processes are bound to states related to handling requests, not on the token possession. A process p i can be:

Idle: If it has a parent, it can either send a request to it and then switch Send to true, or receive a request from any other process that points on p i as parent. Req list is null.

Sending: p i sent a request that is not yet completed. It is not ready to receive any request as Send is true. Req is null.

Busy: p i handles and registers a request. It is not ready to register others, however it can put them in Req list.

We consider a branch of the parent tree {..p j-1 , p j , p j+1 ..p n } as a sequence of processes such that p n is the root, whereas p j+1 is the parent of p j . Hence, p j points towards p j+1 . Suppose initially, p 0 is the root that holds the token.

As in the original Naimi-Trehel algorithm, assume that at a time t, p j requests the token from its parent p j+1 . Additionally we will always require that, before, it sets the Send variable to true.

Conversely, if p j+1 has sent a request that is not yet achieved, it puts p j 's request on hold and stores it in Req list. As soon as p j+1 is available, it starts processing the p j 's request. If its parent exists (j+2), p j+1 sends it to p j and waits for ACK. Then, p j resends the request to p j+2 .

Similarly, if p j+2 is not busy, it sends its parent to p j and waits for ACK. Otherwise, it puts the pending request in Req list. The processing is carried on until p n is claimed. Then, p n informs p j that it is the root of the tree and, it registers p j as the Next. In turn, p j sets its Previous to p n . Processes p j+1 ..p n update their parent to p j .

Suppose that p j+1 is a parent of another process p i . As in Figure 1, p 1 is the parent of p 2 and p 5 . Suppose that p i sends a request to p j+1 . Knowing that p j+1 has not yet received an ACK from p j , it puts the p i request in Req list.

The processing ends when p j sends an ACK to its parent (p j+1 ) and to all its ascendants into the parent's tree. It was then that processes p j+1 ..p n handle Next requests that are in Req list, according to the FIFO policy. Then, p j sets its parent variable to null and its Send value to false.

Thus, we avoid the overlap of requests. Likewise, we ensure consistency in the logical order of requests.

Average Message Complexity

The average number of messages needed for a request to reach a root within Naimi-Trehel's algorithm depends on the height of the request tree process. By using the arguments from [START_REF] Naimi | A log(N ) distributed mutual exclusion algorithm based on path reversal[END_REF] we will show that this results in an average message complexity of O(log(N)) , where N is the whole number of processes in the system.

In the original algorithm, a request is propagated through the parent tree from a son p j to parent p j+1 , as the requesting process p j sends, itself a message to each process in the parent tree. In our algorithm, in addition each process (p j+1 ..p n ) in the branch of the tree, sends a message to the requesting process p j containing its parent. Then, from the end of the tail, p j sends acknowledgments to its parent and to all its ascendants. So in summary, the message complexity per request grows by 3 and will be remain O(log(N)) on average, as in the original algorithm.

Notwithstanding, the extra cost of the modified algorithm does not depend of the whole number of processes and thus, remains O(log N) . By this addition, we are aiming to provide a mutual exclusion algorithm in a dynamic environment.

Formal Description

There is no common clock in our system. However, we introduce a local clock to determine the sequence of events that happen at a given process ρ. Values are assigned to variables described above for each state of the process. By that, atomicity for requests is ensured, while overlap is avoided.

Let T=(t 0 , . . . , t n ) an ordered sequence of times with t i < t i+1 refering to request reception by ρ, and let T'={. . . , t ′ i , . . .} be the set of times of the acknowledgments of those registered requests. Note that ρ doesn't record a new request until it received the ACK of the previous one. We have

t 0 < t ′ 0 < • • • t i < t ′ i • • • < t n < t ′ n .
Let State(ρ, t) be the state of ρ at time t. A process ρ is in Idle state if it is neither sending, or receiving requests, nor waits for an ACK. If ρ is Busy, it waits for an ACK from the process whose request has been registered. If ρ is Sending, it has sent a request to its parent and has not finished sending ACKS. In summary, for each t in [t ′ i , t i+1 ] the following hold:

STATE(ρ, t) = Idle ⇒ SEND = false; REQ = N ull WAIT ACK = false STATE(ρ, t) = Busy ⇒ SEND = false; REQ = N ull WAIT ACK = true STATE(ρ, t) = Sending ⇒ SEND = true; REQ = N ull WAIT ACK = false
Also, ρ must be in the Idle state before sending or recording a given request, i.e for t 1 < t 2 , if STATE(ρ, t 1 ) and STATE(ρ, t 2 ) are Sending or Busy, then there is an intermediate t ′ with t 1 < t ′ < t 2 such that STATE(ρ, t ′ )=Idle.

Inria

A Dynamic Mutual Exclusion Algorithm

We impose the condition that the tree still always connected. For that, we bring additional modifications that will be dealing with the exit strategy for processes. We add the following variables to the previous structure, to maintain the connectivity of the tree.

Child [1..m]: An array allocated dynamically, containing m process IDs that have ρ as parent.

Del: Boolean, initially false. It is permanently set to true once ρ leaves the system.

End del: Boolean, initially false. It is set to true while ρ is negotiating its departure, and goes back to false at the end of that process.

Several events occur before a process ρ leaves the system. We summarize them in chronologically as follows:

1. If ρ is in the CS, it leaves it. Then, it grants its Next if it exists and, this will be the new root.

2. ρ broadcasts a message to its children. It asks each of them if it is also leaving, Sending or Busy. ρ waits for a message from each of them, this will avoid deadlock.

3. If one of the children is now leaving the system, its End del variable is true. Thus, ρ waits until the End del of the Child is false. It will receive a message subsequently.

4. Once all children are notified, they won't send any request or message to ρ, until they receive a new parent.

5. Once ρ becomes Idle and its Req list becomes empty, it sets Del and End del to true.

6. If ρ is the current root (and thus Next was empty in 1), then ρ elects one of its children R to become the new root.

7. ρ sends either this new root R or its parent to its children.

8. All children update their parent variable. Thus, the links of the tree are well maintained.

9. If they are set, ρ notifies its Next and its Previous such that the doubly linked list can be shortcut by them.

10. At the end of the leaving process, ρ sets End del to false and, if it was non-null, notifies parent that it has finished the departing procedure.

By that, as the parent tree remains connected, the Next and the Previous chains links are preserved.

We note that Liveness and safety properties are maintained. The complete proof of these properties will be presented in the full version of this paper.

Handling requests

Within the basic algorithm of Naimi-Trehel, the root of the tree updates its Next to ρ when the latter sends a request to its parent [START_REF] Naimi | How to detect a failure and regenerate the token in the log(N ) distributed algorithm for mutual exclusion[END_REF]. We focus on the maintenance of the Next chain. Assume a chain of processes {p 0 ..p j-1 , p j , p j+1 ..p n } that have pending requests and where p j+1 is the Next of p j and p j-1 is the Previous of p j . At that time, p j and p j-1 exchange their respective type. Then, p j-1 sets its Next to p j . Several cases may occur:

• If p j-1 's type is W and p j 's type is R then p j sets the Reading handler to itself, its Previous to p j-1 and increments the Reader counter.

• If p j-1 's and p j 's type are R then, p j sends a message and sets its Previous to the Reading handler. This one increments the Reader counter. Note that the Reading handler can be within [p 0 ..p j-1 ].

• If p j-1 's type is R and p j 's type is W then p j sets its Previous to the Reading handler. The latter sets its Next to p j .

• If p j-1 's and p j 's type are W then they update their Next and Previous variable respectively, just as before in the case that we only maintained exclusive access to the CS. Figure 2 shows an example of 4 consecutive pending requests. p 1 is the Reading handler of p 2 , p 3 and p 4 . Figure 2(c) summarizes result of events of read requests that have been launched consecutively by p 3 , p 4 and p 2 . In Fig. 2(d), the reader chain enters in the CS and p 5 sends a write request. In terms of complexity, three additional messages are required, two for the type exchange and one to send the identification of the Reading handler. Thus, the message complexity of handling requests remains O(log (N)) .

Conclusion

A new approach of an extended model for a class of distributed mutual exclusion algorithms has been presented in this paper. Our model is an extension of the Naimi-Trehel token-based algorithm. It presents two main benefits; first, it allows a continuous evolution of dedicated distributed environment and secondly, it offers two different access modes to the CS. This contribution should reveal useful in context of grid computing, peer to peer computer networking or any large scale distributed infrastructure. In those systems, resources are set to disappear and reappear. The first modification of the algorithm provides this feature. Furthermore, our approach has a low (=logarithmic) complexity in expected number of messages per operation. We are currently implementing our approach and plan to measure the ability of that algorithm to provide a robust and scalable framework such as grids. In ongoing work, we aim to join the current algorithm to an application programming interface, Data Handover DHO [START_REF] Gustedt | Data handover: Reconciling message passing and shared memory[END_REF], which is a framework for an efficient management for locking and mapping data (an subranges of it) in both read and write modes. Both, our first and second modification of the Naimi-Trehel algorithm will support these ideas. The DHO functions allow the user to insert requests, to release resources and to leave the system, seamlessly to the internal structure of the algorithm provided in our previous work [START_REF] Hernane | Modeling and Experimental Validation of the Data Handover API[END_REF].

Figure 1 :

 1 Figure1: Example of concurrent requests of Naimi-Trehel's Algorithm[START_REF] Naimi | How to detect a failure and regenerate the token in the log(N ) distributed algorithm for mutual exclusion[END_REF]

Figure 2 :

 2 Figure 2: Example of mixed requests

RR n°7798

This section relates to the second contribution in which the sharing of the token is introduced to the previous extended algorithm, resulting in a a read-write mutual exclusion algorithm with volatile processes. Contrary to the contribution of [START_REF] Wagner | Token-based read/write-locks for distributed mutual exclusion[END_REF], in our approach we introduce a Reading handler of concurrent requests. It will cope with the volatility of processes. However, the exit strategy of the Reading handler will be dealt with later. First of all, we add the following local variables to the structure of a given process ρ, see Section 2.2:

Type: Request type, W (exclusive write) or R (inclusive read).

Reading handler: Referring to the first process that requests a shared token after an exclusive one. Initially set to null.

Reader counter: A counter that is incremented if ρ is a Reading handler and at each subsequent read request. Set to zero, initially.

In the following, we assume that the reader chain is a Next chain of pending successive read requesters. Initial values are added within the initialization() function.

Inria

Entering the CS

Within a chain {p 0 ..p j-1 , p j , p j+1 ..p n } of successive read requesters, as soon as p 0 (the Reading handler) accesses the CS, it invites its Next to do so, and so on until the last read requester p n . When it enters the CS, each process in the reader chain sends a message to the Reading handler which in turn increments the Reader counter. So, we have only one additional message per participating process in terms of complexity.

Procedure CS accessing ρ enters the CS

Token release

Once they release the token, processes send a message to the Reading handler, which decrements the Reader counter. We note that the previous of p n+1 is the Reading handler (p 0 ). The Reading handler doesn't release the token to the first process requesting an exclusive token following the reader chain, until the Reader counter is zero. Obviously, a process ρ never shares an exclusive token with a shared one.

Procedure Token release; send CS accessing message to Next;

The correctness of the algorithm for the extension to shared tokens is will be available in the full version of this paper. Inria


Isabelle Bord-Majek

Philippe Kertesz

Julie Mazeau

Daniel Caban-Chastas

Bruno Levrier

Laurent Bechou

Yves Ousten

OPERATIONAL PERFORMANCES DEMONSTRATION OF POLYMER-CERAMIC EMBEDDED CAPACITORS FOR MMIC APPLICATIONS

Keywords: Embedded capacitors, polymer-ceramic dielectrics, robustness, operational microwave performance

Embedded passives are becoming increasingly important for the manufacture of highly integrated electronic boards and packages. The need for embedded passives emerges from the growing consumer demand for product miniaturization thus requiring smaller components and space efficient packaging. This can be realized by replacing discrete components that demands a higher volume than embedded passives. Embedded passives have already been investigated in the last few years. However nowadays used dielectric materials have to be optimized in order to improve the performances of the passive components in terms of dielectric behaviour and reliability. The most promising candidates for dielectric materials applied for embedded passives are polymerceramic nanocomposites. In this paper the robustness of embedded capacitors using such commercial dielectrics regarding the environmental conditions (temperature and humidity) is studied. Microwave measurements performed on an embedded structure design for Low Noise Amplifier (LNA) MMIC decoupling allow to demonstrate clearly the capacity of this new technology.

INTRODUCTION

Electronic board and package miniaturization imply the size reduction of bulky and numerous passive components. It is reasonable to expect passive component densities of 20-30 passives/cm 2 [START_REF] Ramkumar | Lead-free 0201 manufacturing, assembly and reliability test results[END_REF]. Although surface mounted devices (SMD) components can be provided as very small passives, their reflow process onto the printed circuit board (PCB) is very tricky limiting thus their operational reliability [START_REF] Ousten | Environmental conditions influence on embedded capacitors -Comparison with discrete capacitors[END_REF].

Many studies have been performed on the recurring problem of the reliability of ceramic capacitors in all shapes and sizes. It is now widely known that the increase of the stress is caused by the mismatch of the thermal expansion coefficient and the thermal conductivity between the ceramic dielectric, the terminations, the solder, the copper land and the substrate. During cooling, the difference of dissipation due to heat flow between these elements creates important contraction or compression constraints on the different materials. Any concentration of stress can induce cracks (fracture of the leads, shear and fracture of the solder joint, lifting of the copper lands) or cause failure of the assembly during operational use of the components [START_REF] Bechou | Simulation of assembly generated constraints on ceramic capacitors during SMT processing and size optimization of the capacitor by design of experiments[END_REF].

In order to overcome the risk of early failures related to ceramic capacitors, an interesting approach consists in their replacement with passive layers embedded in a PCB substrate (as FR4 or KAPTON FLEX) during the PCB manufacturing process. The integration of passive layers into the PCB might lead to both increase the integration density and improve the reliability. Moreover the embedded capacitor can be located close to the active component reducing the associated parasitic inductances that are linked to its interconnects.

To be used as dielectric layer for embedded capacitors, the material must:

• present the following dielectric properties: high dielectric constant and low dielectric losses over a broad frequency range,

• be deposited as thin layer (roughly around 10μm),

• be in accordance with PCB temperature process (~ 200°C, high pressure processes),

• provide a thermal (high glass transition temperature Tg) and mechanical stability, and

• be low-cost.
In this way polymer-ceramic composites are promising materials for embedded capacitors because they combine the high dielectric permittivity of ceramic powders and the processability and flexibility of polymers (in particular low temperature processing) [START_REF] Windlass | Colloidal processing of polymer ceramic nanocomposite integral capacitors[END_REF]. In this paper we focus only on such commercial dielectric materials.

EMBEDDED CAPACITORS BASED ON COMMERCIAL POLYMER-

CERAMIC DIELECTRICS

Embedded capacitors are made of a dielectric material layer deposited between two metal layers (usually copper foils) that are buried in the PCB. Inorganic dielectric materials commonly used for discrete capacitors are partly replaced by organic polymers. Polymer-ceramic composites are expected to be the major candidate as dielectric layer for embedded capacitors because such composite materials present both characteristics of the processibility of polymers and a high dielectric constant of inorganic materials as barium titanate [START_REF] Wu | Dielectric properties of barium titanate ceramics with different materials powder size[END_REF][START_REF] Wang | Characteristics of polyimide/barium titanate composite films[END_REF].

The polymer (usually epoxy or polyimide) is filled with high dielectric constant particles (usually BaTiO 3 according to EDX analysis presented Figure 1) modifying the organic film. Such dielectric composites commercially available as pre-fab laminates are studied later [7, 8, 9]. Embedded capacitors based on such dielectrics are partly made with plastic materials subjected to both moisture and temperature. In order to perform a robustness study, the impact of temperature and humidity on embedded capacitors based on commercial pre-fab laminates is studied.

ENVIRONMENTAL CONDITIONS INFLUENCE

The pre-fab laminates were buried in a conventional PCB by a PCB manufacturer according to the dielectric datasheet.

TEMPERATURE INFLUENCE ON CAPACITANCE

The temperature is supposed to be the more critical parameter for embedded capacitors based on a polymerceramic material. Capacitance measurements versus frequency were carried out using the impedance meter HP The capacitance C(ω) is linked to ε r (ω) by the following equation:

( ) ( ) 0 r S C d ε ω ε ω = (1)
where ω is the excitation frequency, ε 0 the vacuum permittivity, S the electrode area and d the dielectric thickness.

Moreover the capacitance increases with temperature due to the increase of the relative permittivity ε r (ω) with temperature. A change of the behaviour of the capacitance is observed after 125°C due to glass transition of the dielectric.

THERMAL STORAGE

In order to perform a robustness study, similar embedded capacitors as previously (made of the same nature of dielectric) were placed in a climatic chamber for hours. The electrode area of the studied capacitors is 1.0 x 1.0 mm² and the dielectric thickness is 8µm. Whatever the temperature, the capacitance decreases with exposure time. At ambient temperature, the dielectric material contains a little part of water. After exposure to 85°C / 150°C, water is evaporated. Water permittivity is higher than dielectric one whatever the frequency. So the material permittivity and then the capacitance decrease after exposure to 85°C / 150°C. The behaviour is similar at 85°C and 150°C. However the capacitance decrease is accelerated at 150°C: the same variation is observed at 150°C after 80h and at 85°C after 155h.

Figure 4 presents the capacitance variation versus exposure time at 150°C at different frequencies after drying for the Oak-Mitsui embedded capacitor based on the BC8T-FaradFlex ® material. A gradual slope change is observed with exposure time (especially at high frequency). After 135h the capacitance increases. This phenomenon may be correlated with a modification of the dielectric material during thermal ageing.

HUMIDITY STORAGE

Similar embedded capacitors (electrode area 1.0x1.0mm² and dielectric thickness 8µm) were stored in a climatic chamber with humidity control for hours. Capacitance measurements versus frequency were carried out after various exposure times to 85°C / 85% RH (Relative Humidity). Figure 5 presents the capacitance variation versus exposure time to 85°C / 85% RH at different frequencies for the Oak-Mitsui embedded capacitor based on the BC8T-FaradFlex ® material. The capacitance increases with exposure time because of water absorption by the material (water permittivity higher than polymer/ceramic permittivity). After 138 hours, no significant variation is observed. The maximal capacitance variation is about 5%.

COMPARISON WITH DISCRETE CAPACITORS

ENVIRONMENTAL CONDITIONS INFLUENCE

The maximum exposure time at high temperature, number of reflow solder cycles or re-work cycles are not limited by ceramic capacitors but by the laminate assembly and the plastic moulded components quality.

Generally defects induced on ceramic capacitors are due to manufacturing process and reflow problems. This kind of defects can generate failures during components operation. For example, in a previous study, we tested two lots of 25X7R 0805 ceramic capacitors 47pF using impedance spectroscopy. After thermal ageing (150°C during 1000h), a significant drift of the capacitance was systematically observed (nearly 20%) and some components were found defective because of cracks [START_REF] Ousten | Different approaches to packaging reliability[END_REF].

In the case of embedded capacitors based on polymer/ceramic dielectric, a 6% maximal capacitance variation is observed after 135h. After 1000h, the capacitance variation is only 3%, clearly lower than ceramic capacitors one (15%).

Humidity is not a recognized factor of failure of ceramic capacitors. Humidity may be dangerous for the metal terminations that make up the electrodes but not for the dielectric material. When both precious metal electrode and base metal electrode (BME) capacitors were subjected to autoclave (121 °C/ 100% RH) testing after 500h, it was found that the precious metal capacitors aged (average capacitance degraded less than 3% from their starting values), but the BME capacitors degraded to below the -30% specification limit [START_REF] Donahoe | Moisture induced degradation of multilayer ceramic capacitors[END_REF]. This problem is reduced in embedded capacitors because the electrodes are protected by the PCB. Our study showed a maximal capacitance variation with humidity of about 5%.

INTERNAL STRESS

Embedded passives are supposed to be more reliable than discrete passives as they do not require solder joints.

The shear stress (due to CTE mismatch) is the main cause of delaminations and cracks in the case of discrete capacitors. For the reliability point of view, it is essential to know the stress at the different interfaces in embedded capacitors.

The shear stress values inside the PCB were estimated using the analytical program CRITIDEL from EURELNET [12] at the interfaces:

• PCB-Copper

• Copper-Dielectric (i.e. Figure 6)

The values of mechanical properties necessary to the analytical calculation of the stress are summarized in the Table 1.

Material

OPERATIONAL MICROWAVE PERFORMANCE

EMBEDDED CAPACITORS FUNCTIONAL TEST VEHICLE

In the framework of HIFAP program (PIDEA+), we designed an embedded structure for « real » MMIC decoupling measurements: the Low Noise Amplifier (LNA) UMS (United Monolithic Semiconductors)

CHA3023 could be easily implemented with such embedded capacitors and it could be then easy to clearly demonstrate the potential of this new technology. In this way, two equivalent versions of the LNA were manufactured:

• a version with an embedded capacitor as decoupling capacitor (using an organic substrate)

• a version with a discrete ceramic capacitor as decoupling capacitor.

EMBEDDED DESIGNS EVALUATION

S parameters measurements were carried out using the test set network analyzer Agilent 85110A (connected to HF probes) in the frequency range [START_REF] Ousten | Environmental conditions influence on embedded capacitors -Comparison with discrete capacitors[END_REF]18GHz] for both previous LNA versions. The following parameters were checked:

-S11 input return loss -S22 output return loss -S21 output insertion loss (LNA's gain). The LNA return losses are also very similar in discrete and embedded capacitors configuration (around -15dB).

The oscillations are different in both cases (embedded en discrete capacitors configurations) because of the difference in impedance due to the design. However there is no impact on the LNA Gain.

The previous results show that the concept is validated at room temperature.

Thermal stability

No difference in LNA behaviour was observed for both vehicles (discrete and embedded capacitors configuration) at room temperature.

The previous circuits were then considered for measurement under high/low temperature in order to check decoupling thermal stability.

Measurement was performed using the following method (detailed in Figure 9) in the temperature range [-40, +80°C].

S parameters measurement @25°C

S parameters measurement @-40°C S parameters measurement @-30°C S parameters measurement @0°C S parameters measurement @10°C S parameters measurement @80°C S parameters measurement @25°C Moreover the S21 is stable after thermal cycling which implies that temperature effect is reversible. The assessed LNA operates properly within the frequency band and with respect to temperature.

The stability of embedded capacitors is now achieved representing a major breakthrough for microwave packaging.

CONCLUSIONS

Capacitive laminates commercially available were studied. Theoretical performance of embedded capacitors using organic polymer dielectric was first assessed:

• the capacitance decreases after thermal exposure ( ≤ 6%) because of water evaporation.

• the capacitance increases after humidity exposure (≤ 5%) due to water absorption.

Operational performance of embedded capacitors using organic polymer dielectric was then checked and compared to discrete capacitors one. Finally it was demonstrated that the commercial laminates could be used efficiently to replace discrete decoupling capacitors for microwave packaging and with no reliability issues (with respect to moisture and temperature) to be foreseen.

With the added benefits of elimination of solder joints, inventory, assembly and rework with respect to their surface mounted counterparts, embedded ceramic capacitors provide a very convincing and compelling option to meet the ever increasing need for miniaturization and improve performance in modern electronic designs.

Although embedded capacitors are promising, the range of available capacitance values is not sufficient for the moment (close to 0.5 to 2 nF/cm²). In order to reduce the size of the basic capacitor and generate a larger range of capacitance values (20 to 200 nF/cm²), two ways are currently explored:

• the synthesis of materials with higher values of dielectric permittivity (high-k materials) over a broad frequency range with respect to PCB manufacturing process requirements,

• and the reduction of the dielectric layer (< 8μm) which induces a good processability of the material (printable formulation).

In this way, polymer-ceramic nanomaterials used to make embedded capacitors must be improved.

Figure 1 :

 1 Figure 1: EDX analysis of a commercial dielectric layer based on BaTiO 3 particles (BC8T-FaradFlex ® material from Oak-Mitsui)

  4192A and the test fixture HP 16034E in the frequency range [1kHz, 1000kHz].

Figure 2

 2 Figure 2 shows the capacitance variation versus frequency in the temperature range [25°C, 150°C] for an Oak-Mitsui embedded capacitor based on the BC16T-FaradFlex ® material. The electrode area of the studied capacitor is 6.0 x 6.0 mm² and the dielectric thickness is 16µm.

Figure 2 :

 2 Figure 2: Capacitance variation versus frequency in the temperature range [25°C, 150°C] for an Oak-Mitsui embedded capacitor based on the BC16T-FaradFlex ® materialWhatever the temperature, the capacitance decreases as increases the frequency due to the drop of the relative permittivity ε r (ω) with frequency. The thermal expansion coefficient (CTE) of such commercial dielectrics is about 20.10 -6 C -1 . So the dimensional expansion is about 0.04µm in the studied temperature range [25°C, 150°C] that is negligible compared to the material thickness (16µm).

Figure 3

 3 Figure 3 shows the capacitance variation versus frequency after the first exposure hours to (a) 85°C and (b) 150°C for an Oak-Mitsui embedded capacitor based on the BC8T-FaradFlex ® material.

Figure 3 :

 3 Figure 3: Capacitance variation versus frequency after various exposure times to (a) 85°C and (b) 150°C for an Oak-Mitsui embedded capacitor based on the BC8T-FaradFlex ® material

Figure 4 :

 4 Figure 4: Capacitance variation versus exposure time at 150°C at different frequencies for an Oak-Mitsui embedded capacitor based on the BC8T-FaradFlex ® materialAfter drying, the capacitance decreases due to water evaporation. A maximal capacitance variation of only 6% is observed after 135h.

Figure 5 :

 5 Figure 5: Capacitance variation versus exposure time to 85°C / 85% RH at different frequencies for an Oak-Mitsui embedded capacitor based on the BC8T-FaradFlex ® material

Figure 6

 6 Figure 6 presents the calculated shear stress values versus the thickness of the dielectric layer.

Figure 6 :

 6 Figure 6: Shear stress values between PCB-Copper and Copper-Dielectric versus dielectric thickness calculated using CRITIDEL

Figure 7 Figure 7 :

 77 Figure 7 presents the LNA Gain (S21 output insertion loss) using (a) ceramic discrete capacitors and (b) embedded capacitors as decoupling capacitor.

Figure 8 Figure 8 :

 88 Figure 8 presents the LNA return losses (S11 and S22) using (a) ceramic discrete capacitors and (b) embedded capacitors.

Figure 9 :

 9 Figure 9: Thermal stability measurement method This way we could assess potential S parameters values hysteresis that would indicate that the embedded capacitors are not thermally stable.

Figure 10 Figure 10 :

 1010 Figure 10 presents the LNA return losses using embedded capacitors in the temperature range [-40, +80°C].

Figure 11

 11 Figure 11 presents the LNA Gain using embedded capacitors in the temperature range [-40, +80°C].

Figure 11 :

 11 Figure 11: LNA Gain versus frequency using embedded decoupling capacitors in the temperature range

Figure 12

 12 Figure 12 presents the LNA Gain variation compared to the reference gain at 25°C with embedded capacitors in the temperature range [-40, +80°C].

Figure 12 :

 12 Figure 12: LNA Gain variation compared to the reference gain at 25°C with embedded decoupling capacitors in the temperature range [-40, +80°C]

Young Modulus (GPa) CTE (ppm. C -1 )

	PCB	15	14
	Copper	100	17
	Dielectric	1.3	32

Table 1 :

 1 Mechanical properties of materials[12]

ACKNOWLEDGEMENTS

The authors gratefully acknowledge Jean-Yves Gondouin from Elvia-Lithos as PCB manufacturer and the different manufacturers (in particular Oak Mitsui) which provide us materials for the tests within research and development programs as HIFAP (PIDEA+), PROCURE FP5 and AMELIE FP6.


Sarra Ben Abbès

Haïfa Zargayouna

Adeline Nazarenko

Evaluating semantic classes used for ontology building and learning from texts

Keywords: Evaluation, semantic classes, concepts, terms, lexical level, structural level, ontologies

A large effort has been devoted to the development of ontology building tools but it is still difficult to assess their strengths and limitations. Proposed evaluations are hardly reproducible and there is a lack of wellaccepted protocols and data. In this paper, we propose to decompose the evaluation of ontology acquisition process into independent functionalities. We focus on the evaluation of semantic class acquisition considered as a main step in the ontology acquisition process. We propose an approach to automatically evaluate semantic classes of ontologies that offer lexical entries for concepts. It is based on the comparative paradigm (to a gold standard). Its main focus is to compare how similar the generated semantic classes are to the gold standard concerning the disposition of concepts frontiers. This comparison relies on the lexical level and on the hierarchical structure of the "gold" concepts. The propositions are implemented, two experiments are settled on different domains and prove that the measures give a more accurate information on quality of systems' performances.

INTRODUCTION

Ontologies are complex artifacts (composed of concepts, hierarchical relations and roles) which are built according to different points of views and purposes. In our work, we focus on ontology acquisition from texts which is generally a semi-automatic process that needs human validation in which evaluation is crucial. Given the complexity of ontological components, we propose to decompose the evaluation of ontology acquisition from texts into three separate evaluation tasks:

• Semantic class or class acquisition: the process gives as output a list of term clusters that are considered as semantic classes (draft concepts). A semantic class is a set of terms, • Building concept hierarchies: the process aims to design an hierarchical structure of concepts, • Role extraction: the process consists in identifying the semantic relations that hold between concepts (excluding hierarchical relations).

In this paper, we focus on the evaluation of semantic classes acquisition considered as a main step in the ontology acquisition process. We propose an automatic comparative approach that relies on the existence of a gold standard which is an ontology with lexical entries for concepts.

To compare semantic classes with the gold standard, we suppose that concepts of the gold standard (C) are also associated with one or several labels. In this paper, we called semantic classes, the outputs of acquisition tools and concepts, the conceptual entities of the gold standard.

We measure how similar the generated semantic classes are to the gold standard concerning the disposition of concepts frontiers. This comparison relies on the lexical level and the hierarchical structure of the "gold" concepts.

In the following paper, we present the evaluation protocol based on gradual measures that reflect the quality of outputs and take into account the specificity of the gold standard. Section 3 details the set of experiments done so far.

SEMANTIC CLASSES EVALUATION PROCESS

Our evaluation protocol takes as input: (1) the semantic classes as they are output by semantic class extraction systems or ontology building tools, and (2) a gold standard which is a lexicalized ontology repre-sented as hierarchy of concepts. The evaluation process outputs a score which is a relevance measure of the semantic classes with respect to the gold standard ontology (see figure 1). Gold standard-based evaluation has been set up in some challenges such as OAEI 1 and in approaches dealing with ontologies evaluation [START_REF] Brank | Gold standard based ontology evaluation using instance assignment[END_REF][START_REF] Zavitsanos | A distributional approach to evaluating ontology learning methods using a gold standard[END_REF]. The process of the evaluation of semantic class acquisition is defined by three steps: anchoring, tuning and relevance computation.

Anchoring step

The matching of a semantic class SC and reference concepts C is oriented and based on a lexical matching in which the list of semantic classes terms is compared with the concepts labels. A lexical matching is perfect when a SC has exactly the same terms as a C. However, a lexical matching is poor when a class has no common term with any concept of the gold standard. In practice, there is no exact matching between semantic classes and concepts and partial matching leads to three types of correspondence: 1 to 1, 1 to n, n to 1.

Tuning step

In order to avoid the scoring to be too dependent on the gold standard or a specific system behavior, the output is transformed to find its maximal correspondence with the gold standard: the output is tuned to the specific type and granularity of the chosen gold standard. This tuning is performed instead of considering several human judgments or revising the gold standard on the basis of the systems' outputs.

The tuning process takes three different matching cases into account:

• Some semantic classes and concepts stand in a 1 to 1 matching relationship. In that case, the output classes remain unchanged (no transformation). • Some classes match several concepts of the gold standard (1 to n matching relation). In that case the output classes are split into several subclasses, each one corresponding to a different 1 Ontology Alignment Evaluation Initiative matched concept (splitting transformation, see figure 2-a). • Several classes match the same concept (n to 1 matching relation). In that case the classes are merged into a larger one (merging transformation, see Fig. 2-b).

This tuning process is described in [START_REF] Zargayouna | Evaluation of textual knowledge acquisition tools: a challenging task[END_REF] and has been also applied to the evaluation of term extraction tools.

Relevance computation step

We choose to adapt well known classical measures, precision and recall, as they are generic and easy to interpret. However, these measures rely on a binary judgment of relevance. We want to take into account the gradual relevance. The overall precision and recall that we propose are computed in the basis of local relevances between tuned classes and gold concepts. These relevances are computed as follows:

• The relevance of non-transformed classes is based on the number of terms shared between the semantic class and the corresponding concept: from which it is derived and on the similarity of its matching concept with the concept that is considered as the pivot p of the splitting process:

P(SC ′ ,C) = number
relevance st (SC ′ i ,C) = F -measure(SC,C) × Sim W P (p,C)
where SC ′ i is a class derived by splitting an initial SC class, C is a concept of the gold standard, p is the pivot concept of the gold standard which has the highest F-measure with the semantic classes derived from SC. Sim W P (p,C) is a similarity measure between concepts p and C [START_REF] Wu | Verb semantics and lexical selection[END_REF].

These overall relevance measures are based on the lexical relevance of each class of the tuned output. The precision and recall of a system are computed as follows:

P = ∑ |S ′ | i=1 ∑ |GS| j=1 relevance(SC ′ i ,C j ) |S ′ | ; R = ∑ |S ′ | i=1 ∑ |GS| j=1 relevance(SC ′ i ,C j ) |GS|
where |S ′ | and |GS| are respectively the numbers of classes of the tuned output and concepts of the gold standard.

relevance(SC

′ i ,C j ) =          relevance nt (SC ′ i ,C j ) if SC ′ i is not transformed relevance mt (SC ′ i ,C j ) if SC ′ i is obtained by a merging operation relevance st (SC ′ i ,C j ) if SC ′
i is obtained by a splitting operation [START_REF] Maedche | Measuring Similarity between Ontologies[END_REF] proposed similarity measures between two ontologies that can be used for comparing an ontology to a gold standard. These measures take into account two levels: lexical (similarity measure String Matching (SM)) based on the edit distance and conceptual (semantic cotopy measure (SC)). However, the two ontologies are considered equal on quality. Our measures are adapted to the special context of evaluation: they are asymmetric i.e the similarity is oriented from the outputs to the gold standard. This enable to take into account the specific type and granularity of the chosen gold standard by tuning the systems' outputs.

EXPERIMENTS

Two experiments are done with two different domains: transport and astronomy. The goal of the first experiment is to check the behavior of the proposed measures. A small gold standard ontology had been built manually from the synsets of WordNet, in the transport domain. We artificially created 4 systems' outputs by removing terms or classes (silence) from the gold standard or by adding terms or classes (noise) to it. These outputs are based on the following data: (1) O nT contains noisy terms, (2) O nC contains additional noisy classes containing irrelevant labels, (3) O sT has missing terms, and (4) O sC has some missing classes. To test the limits of our mea- standard) has been built manually from texts of the astronomy domain using Terminae tool [START_REF] Szulman | The terminae method and platform for ontology engineering from texts[END_REF]. Associated to that ontology, two outputs have been provided by Formal Concept Analysis (FCA): a first output O1 has been settled (75 classes) by using a list of 24 initial terms/ basic concepts (V1). A second output O2 (111 classes) has been settled by using a set of terms (V2) that extends V1. There is no exact matching between the handcrafted clusters (O1 and O2) and the gold standard. Classical measures results are null (for O1 and O2, CP = CR = CFM = 0). This experiment proves that the proposed evaluation measures give a more accurate information on quality of systems' performances.

Outputs P R FM O1 0,5 0,17 0,25 O2 0,37 0,2 0,26

CONCLUSION AND FUTURE WORK

We have decomposed the problem of ontology acquisition evaluation into different sub-problems. In this paper, we have focused on the evaluation of semantic classes acquisition. We proposed a protocol for comparative evaluation allowing the matching between semantic classes and the gold standard. Thus, the quality assessment on gold standards is controversial: there has to be a gold standard, quality has to be assumed, etc. From the same textual corpus, there is a multitude of acceptable solutions that vary from one expert to another. In order to take into account the variability of the gold standard we proposed to tune the systems' outputs. This enable to find the maximal correspondence with the gold standard. We also proposed to compute a gradual relevance, the aim is to detect differences which are due to errors from those that can be due to different conceptualisation choices.

Experiments have showed that the proposed evaluation measures gave higher values than traditional ones and a more accurate information on the quality of the performances of acquisition systems.

We have focused on the quality of the classification neglecting, at the lexical level, the correspondence between terms that may itself be only partial (a term in the semantic class can be a variant of another concept of the gold standard). We use a simple matching technique in order not to distort the evaluation. As future work, we aim at including in our measures, a terminological distance between labels as proposed in [START_REF] Zargayouna | Evaluation of textual knowledge acquisition tools: a challenging task[END_REF].

Figure 1 :

 1 Figure 1: Semantic classes evaluation process

  of relevant terms of class SC ′ number of terms of the class SC ′ R(SC ′ ,C) = number of relevant terms of class SC ′ number of terms of the concept of gold standard C relevance nt (SC', C) = F-measure(SC ′ ,C) = where SC ′ is an output class, C is the matching concept of the gold standard, P(SC ′ ,C) is the precision of SC' wrt. C and R(SC ′ ,C) is the recall of SC' wrt. C. • Merging case (n to 1 relation): when many semantic classes are matched with only one concept of the gold standard, we propose to merge these classes into one semantic class SC. The relevance of SC is the average of F-measure of the different classes SC i from which it is formed. It is computed as follows: relevance mt (SC i ,C s ) = ∑ |X| i=1 F-measure(SC i ,C s ) |X| where SC i are semantic classes of the system, C s is the concept of the gold standard which matches different SC i and |X| the number of anchored (or matched) classes of the output to C s . • Splitting case (1 to n relation): The relevance of the split classes depends on the relative position in the gold standard hierarchy of the matching concepts. If they are close to each other, the splitting process is a smaller transformation than if they are far. The relevance of each split class depends on the relevance (F-measure) of the initial SC class

Figure 2 :

 2 Figure 2: Splitting and Merging cases

Table 2 :

 2 Evaluation of the outputs compared to the gold standard GS

	Outputs Precision Recall F-measure Ranking
	GS	1	1	1	1
	O sT	0,74	0,74	0,74	5
	O sC	1	0,67	0,8	4
	O nT	0,84	0,84	0,84	3
	O nC	0,86	1	0,92	2
	Table 1: Evaluation of the tools outputs compared to the
	gold standard
	sures, we considered additional artificial outputs that
	require a merging operation (O m ), a splitting opera-
	tion (O sp ) and a combination of both splitting and
	merging cases (O spm ). The evaluation gives an in-
	formation on the capacity of the evaluated systems to
	extract relevant domain terminologies and to regroup
	them into relevant classes. The second experiment
	have been carried out to show how far the proposed
	measures take into account the gold standard approx-
	imation and make an accurate evaluation comparing
	to the classical ones. An astronomy ontology (gold

Table 3 :

 3 Evaluation of the outputs obtained by FCA method: results

* P(SC ′ ,C) * R(SC ′ ,C) P(SC ′ ,C) + R(SC ′ ,C)

ACKNOWLEDGMENTS

The authors would like to thank Thibault Mondary (LIPN) and Yue Ma (LIPN) for fruitful discussions. This work was partly realized as part of the Quaero Program, funded by OSEO, French State agency for innovation.