Hedi Tabia

Mohamed Daoudi

J-P Vandeborre

A A parts-based approach for automatic 3D-shape categorization using belief functions

Keywords: H.3.1 [Information Storage and Retrieval]: Content Analysis and Indexing, I.2.10 [Artificial Intelligence]: Vision and Scene Understanding-shape, I.5.3 [Pattern Recognition]: Clustering Multimedia data, Classification 3D-categorization, object recognition, belief functions

Grouping 3D-objects into (semantically) meaningful categories is a challenging and important problem in 3D-mining and shape processing. Here, we present a novel approach to categorize 3D-objects. The method described in this paper, is a belief function based approach and consists of two stages. The training stage, where 3D-objects in the same category are processed and a set of representative parts is constructed, and the labeling stage, where unknown objects are categorized. The experimental results obtained on the Tosca-Sumner and the Shrec07 datasets show that the system efficiently performs in categorizing 3D-models.

INTRODUCTION

The representation of objects in three dimensions (3D) has recently have recently gained great popularity in computer vision communities and has become an integral part of modern computer graphics applications, such as computer-aided design, game development and more recently film production. At the same time, 3D data have become widely used in diverse fields including computer vision, computational geometry, molecular biology and medicine. The availability of low cost 3D scanners and the rapid evolution in graphics hardware and software, has greatly facilitated 3D model acquisition, creation and manipulation. The content-based analysis becomes a necessary solution for structuring, managing and organizing 3D objects from large collections. In this context, the aim of this paper is to propose a fully automatic framework for 3D-object categorization based on the content.

Related works

Through the state-of-the-art, we can find mainly two different families of related work. The first family deals with the 3D-shape retrieval and the second family is concerned by the 3D-shape classification.

In the first family, many systems have been proposed for efficient information retrieval from digital collection of 3D-objects. [START_REF] Kazhdan | Rotation invariant spherical harmonic representation of 3d shape descriptors[END_REF]] present a general approach based on spherical harmonics for obtaining rotation invariant representations and show its application in the retrieval task. Antini et al. [START_REF] Antini | Retrieval of 3d objects using curvature correlograms[END_REF]] present an approach relying on curvature correlograms to perform description and retrieval by content of 3D objects. Funkhouser et al. [START_REF] Funkhouser | A search engine for 3D models[END_REF]] present a web-based search engine system that supports queries based on 3D sketches, 2D sketches, 3D models, and/or text keywords. For the shape-based queries, they have developed a matching algorithm that uses spherical harmonics to compute discriminating similarity measures without requiring repair of model degeneracies or alignment of orientations. Filali et al. [START_REF] Filali Ansary | A bayesian 3D search engine using adaptive views clustering[END_REF] propose a method for 3D-object indexing based on 2D-views. In their paper, they present an adaptive nearest neighbor-like algorithm to select the most relevant characteristic views from the 3D-object. A Bayesian approach is used in order to improve the retrieval rate. Assfalg et al. [START_REF] Assfalg | Content-based retrieval of 3-d objects using spin image signatures[END_REF]] presents an adaptive spin images approach for 3D-retrieval by content. Hilaga et al. [START_REF] Hilaga | Topology matching for fully automatic similarity estimation of 3D shapes[END_REF]] proposed a technique, called Topology Matching, in which similarity between polyhedral models is calculated by comparing Multiresolutional Reeb Graphs (MRGs) based on the Reeb graph computation of a 3Dobject. [START_REF] Bronstein | Partial similarity of objects, or how to compare a centaur to a horse[END_REF][START_REF] Bronstein | Partial similarity of shapes using a statistical significance measure[END_REF]] also proposed to consider the 3D-matching problem as a multi-criterion optimization problem trying to simultaneously maximize the similarity and the significance of the matching parts.

Compared to the work on 3D-object retrieval where objects are compared together in pair, 3D-classification, which consists to affect an object query to one category, is still an open problem. Few paper such as [START_REF] Huber | Parts-based 3d object classification[END_REF][START_REF] Donamukkala | Automatic class selection and prototyping for 3-d object classification[END_REF] have addressed this issue. The method is used for classifying vehicles into a set of pre-determined object classes. For that, parts are extracted from training objects and grouped into part classes. A mapping from part classes to object classes is derived from the learned part classes and known object classes. For a 3D object, after local shape features are computed, the object class is determined using the learned part classes and the part-to-object mapping. The decomposition in the approach is just to divide objects into front, middle, and back parts. The method is based on a Bayesian classifier and it is limited to specific datasets, which should respect the decomposition constraint.

Main contributions

In this paper, we present a fully automatic framework for 3D-object categorizing based on the belief functions. The categorization is addressed with a parts-based approach. It consists of capturing a compact model of a given category by building a set of representative parts. For this purpose, the objects in the same category are partitioned into several parts. These parts are then used to construct a set of representative ones with which objects in the same category can be described. A straightforward way to build this set is using vector quantization techniques. Here, we use a variation of the evidential k-nearest neighbors algorithm. The centroids of the resulting clusters are used as representative parts of the category. This process is iterated for all the categories in the training set.

The labeling of unknown 3D-objects is achieved by labeling their associated parts. Here, we assume that each part can help to predict the category of the whole object. More specifically, each part of the object to be labeled is considered as an item of evidence supporting certain hypotheses concerning the category membership of that object. Based on this evidence, the object parts are compared with category representative parts and basic belief masses are assigned to each category. As a result of considering each object part in turn, we obtain a set of Basic Belief Assignments (BBAs) that can be combined using the Dempster's rule of combination to form a resulting BBA synthesizing a final belief regarding the category of the whole object.

Another issue is dealt with in this paper, is when labeling an unknown 3D-object, one can be faced with the problem of handling an unclassifiable object (reject). Here we show that we are able to handle this issue using belief theory based data association method. Using a specific modeling of belief functions, this is done by detecting and managing a portion of a conflict, which originates from the non-exhaustivity of the frame of discernment.

The remainder of the paper is organized as follows. In Section 2 the training stage is presented. Then, in Section 3 the labeling stage is detailed. Section 4 presents experimental results. Conclusions and future developments end the paper.

A 3D-OBJECT CATEGORY MODEL

From a training set of 3D-objects, the procedure we suggest for obtaining the model of each category is based on the assumption that 3D-objects in the same category have the same parts. More specifically, we assume that each category can be represented by a set of representative parts, with which shapes in that category can be described. In this section, we focus on constructing the set of representative parts for each category.

Object partitioning and part description

3D-partitioning, which consists to extract a set of parts that share the same characteristics from a 3D-object, is a deeply-studied domain as the reader may realize through a recent comprehensive survey [START_REF] Shamir | A survey on mesh segmentation techniques[END_REF]]. In our method, we adopt a fully automatic topology driven 3D mesh segmentation algorithm [START_REF] Tierny | Topology driven 3D mesh hierarchical segmentation[END_REF] where feature boundaries and feature hierarchy are both computed in a semantic-oriented manner. The main steps of this approach are shown in Figure 2. First, a set of feature points is extracted from the 3D object as shown in Figure 2(a). Then the enhanced topological skeleton of the input triangulated surface is constructed (Figure 2(b)). Finally, it is used to delimit the core of the object and to identify junction areas. This final step results in a fine segmentation of the object (Figure 2(c)).

After the object partitioning, parts are represented by local descriptors which capture the geometry of the part. It is well known that the performance of all data classifier depends critically on the ability of the descriptors to discriminate among the various classes. Choosing the right set of feature is a difficult problem. The descriptors must be sufficiently rich to discriminate between different parts of shapes, and at the same time be invariant to different transformations that a shape can undergo. There exists several part description algorithms, and below we overview some of them.

-GD2: The GD2 is a local distributions of geodesic distances. It has been used for shape recognition by Osada et al. [START_REF] Osada | Shape distributions[END_REF] as a global shape distribution, which measures Euclidean distances of random surface points. -Gcords: Geodesic cords-based descriptors is defined as a distribution of geodesic distances from one source point to other. First, an Euclidean Cords-based descriptors was be introduced by Paquet et al. [START_REF] Paquet | Nefertiti: a query by content system for three-dimensional model and image databases management[END_REF] for global 3D-shape matching. We have adapted this approach to local feature descriptor.

-HSI: Histogram of Shape Index, is defined as the histogram of shape index values, calculated over mesh part. The shape index, first introduced by Koenderinket al. [START_REF] Koenderink | Surface shape and curvature scales[END_REF], is defined as a function of the two principal curvatures on continuous surfaces.

Representative part construction

Here, we attempt to find representative parts of each category. For this end, we developed an evidential clustering method based on the Transferable Belief Model (TBM) concept [START_REF] Shafer | A mathematical theory of evidence[END_REF][START_REF] Zouhal | An evidence-theoretic k-nn rule with parameter optimization[END_REF]].

Transferable Belief Model concept.

The TBM is based on a two-level model: a credal level where beliefs are entertained, combined and updated, and a pignistic level where beliefs are converted into probabilities to make decisions.

-Credal level: Let Ω denote a finite set called the frame of discernment. A Basic Belief Assignment (BBA) or mass function is a function m : 2 Ω → [0, 1], such that:

A⊆Ω m(A) = 1. m(A)
measures the amount of belief that is committed to A. The subsets A of Ω such that m(A) > 0 are called focal elements. Given two BBAs m 1 and m 2 defined over the same frame of discernment Ω and induced by two distinct pieces of information, we can combine them using the Dempster's combination rule [START_REF] Shafer | A mathematical theory of evidence[END_REF] given by:

(m 1 ⊗ m 2 )(A) = 1 1 -B∩C=∅ m 1 (B)m 2 (C) B∩C=A m 1 (B)m 2 (C).
(1) for all A ⊆ Ω. -Pignistic level: When a decision has to be made, the beliefs held at the credal level induce a probability measure at the pignistic level. Hence, a transformation from belief functions to probability functions must be done. This transformation is called the pignistic transformation. Let m be a BBA defined on Ω, the probability function induced by m at the pignistic level, denoted by BetP and also defined on Ω is given by:

BetP (ω) = A⊆Ω,ω∈A m(A) |A| (2)
for all ω ∈ Ω and where |A| is the number of elements of Ω in A.

Clustering algorithm.

Let us consider a category C in the training set. All objects in C are processed (each object is partitioned) and the sets of parts are extracted. Let P C = {P 1 , ..., P N } be the collection of all object parts in C. We assume that these parts can be classified into M classes W = {W 1 , ..., W M } (for the choice of M see Algorithm 1)and each part P i will be assumed to possess a class label indicating with certainty its membership to one class in W . Let P s be an incoming part to be classified. Classifying P s means assigning it to one class in W . Using the vocabulary of the evidential theory, W can be called the frame of discernment of the problem.

Let us denote by Θ s the set of the k-nearest neighbors of P s in P C , according to some distance measure D (in this paper D represents the L 2 distance between 2 descriptors). Let P k ∈ Θ s a 3D-part classed in W l . The pair (P k , W l ) can be regarded as a piece of evidence that increases our belief that P s also belongs to W l . However, this piece of evidence does not by itself provide 100% certainty. In the evidential formalism, this can be expressed by saying that only some parts of our belief are committed to W l . Since the fact that P k ∈ W l does not point to any other particular hypothesis, the rest of our belief can not be distributed to anything else than W , the whole frame of discernment. This item of evidence can therefore be represented by a Basic Belief Assignment (BBA) m k verifying:

m k (W l ) = χe (-γ l D 2 (Ps,P k )) m k (W ) = 1 -m k (W l ) (3) m k (A) = 0 ∀A ∈ 2 W \ {W, {W l }}
With χ a parameter such that 0 ≤ χ ≤ 1. γ l is obtained by an optimization procedure proposed by Zouhal and Denoeux [START_REF] Zouhal | An evidence-theoretic k-nn rule with parameter optimization[END_REF]]. We set χ = 0.9. For each of the k-nearest neighbors of P s , a BBA depending on both its class label and its distance to P s can therefore be defined. In order to make a decision regarding the class assignment of P s , these BBAs can be combined using Dempster's rule [START_REF] Shafer | A mathematical theory of evidence[END_REF]] into one BBA m s . As a result, P s will take the label of the class maximizing the pignistic probability induced by m s . Algorithm 1 summarizes this method. Once the clustering process is achieved, we compute the centroid of each cluster. The centroid is a part whose parameter values are the mean of the parameter values of all the parts in the cluster. Centroids, in this paper, are called representative parts and denoted by R.

LABELING A NEW 3D-OBJECT

In this section, we focus on the labeling of 3D objects. Figure 3 shows the various steps of this process. First, giving an object O to be labeled (Figure 3 step a), the algorithm begins by partitioning this object (Figure 3 step b). Second, an invariant descriptor is associated to each extracted part of that object (Figure 3 step c). The partitioning and the description of these parts are done in the same way as in the training process. The labeling of the object O is achieved based on its parts. Here, we assume that each part can help to predict the category of the whole object. In the context of belief functions, we can say that each part represents an evidence source which provides an information regarding the category of the object. By considering all parts, we obtain a set of evidence sources that can be combined to produce a final decision concerning the category of the object.

Fig. 3. The labeling system architecture: the input of the system is a 3D-object to be labeled. The output is the probabilities of belonging to each category .

Evidence extracting from parts

Recalling here that, after the training process, each category contains a set of representative parts. Given a part extracted from the object to be labeled (for example P 1 in Figure 3 step c), we select in each category the representative part that is the closest to P 1 (Figure 3 step d-1). Then, from the selected representative part a mass function that quantifies the degree of belief given to the assumption "P 1 matches with a particular category C j " is derived (Figure 3 step d-2). As a result of considering each category in turn we obtain a set of BBAs that can be combined using the Dempster's rule of combination to form a resulting BBA. This BBA syntheses a final belief regarding the relation between the part and the categories (Figure 3 step d-3).

More formally, let us denote by {P i } 1≤i≤I the set of I parts composing the object O. From the training set, we enumerate J categories Ω c = {C j } 1≤j≤J . A category C j contains a set of representative parts. Let R j Pi be the closest representative part to the part P i in the category C j . Each pair (P i , R j Pi ) with 1 ≤ j ≤ J constitutes a distinct item of evidence regarding the category membership of P i . If P i is closed to R j Pi then one will be inclined to believe that both parts belong to the same category. On the contrary if their dissimilarity is very large then we consider that P i may belongs to C j the complement of the C j in Ω c . Consequently this item of evidence may be postulated to induce a basic belief assignment BBA m ij over Ω c defined by:

m ij (C j ) = µ • S(P i , C j ) m ij (C j ) = µ • (1 -S(P i , C j )) (4) m ij (Ω c ) = 1 -µ S(P i , C j ) = e (-D(Pi,R j P i
)) is a function of the distance between the part P i and its closest representative part R j Pi in the category C j . µ is a weakening coefficient ( [START_REF] Shafer | A mathematical theory of evidence[END_REF]]) associated with the category C j . In practice, we set µ = 0.9 for all categories.

As a result of considering each category we obtain J BBAs as shown in Figure 3 step d-2. These masses are combined using the Dempster's rule of combination to form a resulting BBA m i synthesizing a final belief regarding the attachment of P i to each category. Figure 3 step d-3 shows the resulting BBA m i .

3D-object labeling

In order to get a final decision about the category of the unknown 3D-object, all masses m i i ∈ [1..I] are combined using the Dempster's rule of combination (Figure 34).

A decision can be made regarding the category membership of the 3D-object by examining the pignistic probability deduced from the resulting mass m (Figure 345). The labeling process is summarized in Algorithm 2. FORALL Cj in Ωc 2. Find the closest representative part R j P i to the part Pi; 3. Compute mij (according to eq.4); ENDFOR 4. Compute mi by combining mij using Dempster's rule eq.1; ENDFOR 5. Compute m by combining all mi using Dempster's rule eq.1; 6. Compute the pignistic probability induced by m for all categories using eq.2; 7. Label O according to the highest pignistic probability; End

Reject option

Introducing a reject option is very useful, yet a difficult problem in data classification. Instead of Bayesian classifiers where the reject is modeled empirically by comparing the posteriori probability with a threshold (T) [START_REF] Vailaya | Image classification for contentbased indexing[END_REF], the reject in the belief theory is modeled in natural way. It can be deducted from the conflict on each Table I. Representation of the Dempster's rule of combination

C 1 ∅ C 1 C 1 C 1 C 2 ∅ C 2 Ωc C 2 C 1 Ωc C 2 C 2 Ωc
mass distribution in Figure 3 step d-3. The idea consists to divide the conflict into two components, a conflict due to the non-exhaustivity of the frame of discernment represented by the reject and an unknown conflict. In order to illustrate this idea, let us consider a two element frame of discernment

Ω c = {C 1 , C 2 }. Ω c can also be repre- sented by C 1 , C 1 or C 2 , C 2 .
Given two BBA m 1 and m 2 which are defined on Ω c by: m 1 = m 1 (C 1 ), m 1 (C 1 ), m 1 (Ω c ) : a 3D-object belongs or does not belong to the category C 1 or we are in a situation of almost complete ignorance concerning the category of that part.

m 2 = m 2 (C 2 ), m 2 (C 2 ), m 2 (Ω c
) : a 3D-object belongs or does not belong to the category C 2 or we are in a situation of almost complete ignorance concerning the category of that part.

Here, m 1 and m 2 are considered as two independent sources of information to be combined in order to decide with which category, the object is associated. The evidence combination of these two belief using Dempsters rule of combination can be represented by Table I.

The last row and the first column of this table are named by the subsets of Ω c . Each of the squares in the table correspond to the intersection of the subset of each source of information m 1 and m 2 . The value of BBA taken for the resulting subset is obtained by the multiplication of the BBA values of the subsets constituted Ω c . From this table, we can see that the conflict (the mass of the empty set) is represented by two grids. Its value is given by:

m 12 (∅) = m 1 (C 1 ).m 2 (C 2 ) + m 1 (C 1 ).m 2 (C 2 )
(5) The first portion of the conflict m 1 (C 1 ).m 2 (C 2 ) is created because the two sources of information m 1 and m 2 related respectively to category C 1 and C 2 confirmed that a 3D-object corresponds to the two categories at the same time. In contrast, the second portion of the conflict m 1 (C 1 ).m 2 (C 2 ) is created because the two sources of information confirm that the 3D-object does not correspond to any category and thus the frame of discernment is not exhaustive. Hence, in our view, the separation between the first and the second portion of the conflict must be done because they do not have the same origin. We define a reject when sources of information confirm that the 3D-object does not correspond to any category. The reject is added to the frame of discernment as a new element and its belief degree is given by: m 12 (reject) = m 1 (C 1 ).m 2 (C 2 ). More specifically, in our case and through multiple sources of informations in the Table in Figure 3 step (d-2), the mass value of the reject is given by:

m i (Reject) = J j=1 (m ij (C j )) (6)
Finally, according to the pignistic probability deduced from the mass function computed in section 3.2, a decision can be taken about the reject of the 3D-object.

EXPERIMENTAL RESULTS

We present results from three experiments. In the first we evaluate the performance of the belief based classifier and explore the impact of the choice of descriptors on classifier accuracy. The accuracy is computed as the percentage of object models which are correctly classified. We then compare the performance of the belief based classifier with the Bayesian classifier [START_REF] Huber | Parts-based 3d object classification[END_REF]] on the same problem. In the penultimate experiment we describe results with comparison to some state of the art retrieval methods. The last experiment shows the contribution of reject modeling option of our framework.

The experiments were conducted on two different datasets. The first dataset is the Shrec07 database. It contains 400 3D-objects classified into 20 classes. It is a challenging dataset, not only because of the large number of classes, but also because it contains shapes with highly variable poses and non-rigid or isometric transformations. Figure 4 shows some examples from this dataset. Each object in the figure represents one class. The second dataset is composed of shapes from the Tosca and the Sumner datasets. The Tosca dataset has been proposed by [START_REF] Bronstein | Efficient computation of isometry-invariant distances between surfaces[END_REF]] for non-rigid shape correspondence measures. The Sumner dataset has been proposed by [START_REF] Sumner | Deformation transfer for triangle meshes[END_REF] for deformable shape correspondence. The total set size is 380 shapes. Figure 5 shows some examples from this dataset. Each object in the figure represents one class.

Framework performance

From a qualitative point of view, Figure 6 and 7 give a good overview of the efficiency of the framework on the Shrec07 dataset. Figure 6 presents a confusion matrix. Rows in this matrix correspond to query parts extracted from a human 3D-object, and columns correspond to the different categories shown in Figure 4 (Ordered from left to right and from top to bottom). The lightness of each element (i; j) is proportional to the magnitude of the similarity between the part i and its closest representative one in the category j. Lighter elements represent better matches, while hot elements indicate worse matches. One can notice in this visualization that the parts of the human object tends to match with the 12th object category which corresponds to the human one in Figure 4. This result confirms our assumption that 3D-objects in the same category have the same parts.

Figure 7 shows another confusion matrix. In this matrix rows correspond to 3Dobject queries and columns correspond to the categories shown in Figure 4. The lightness of the diagonal squares of the matrix proves the effectiveness of our classifier.

More quantitatively, Table II and Table III show the classification results of our framework using different descriptors. On the Shrec07 dataset (Table II), HSI and Gcords descriptors yielded an accuracy of around 73%, while the GD2 leads to a much higher accuracy of around 93.5%. These results show that the GD2 is more suited for local shape description. A combination of the GD2 and HSI feature yields a better accuracy than GD2 feature alone 94.8%(the combination is based on the mean distance).

On the Tosca-Sumner dataset (Table III), the combination of the GD2 and HSI feature also gives the highest accuracy rate 97.9%.

Belief classifier versus Bayesian classifier

Table IV and Table V show a comparison accuracy between the belief classifier and the Bayesian classifier on respectively the shrec07 and the Tosca-Sumner datasets.

On the shrec07 dataset, our classifier showed an accuracy of 96.7% and 92.9% on the training set and an independent test set, respectively. That is to say 94.8% accaracy over the entire dataset. Using a Bayesian classifier we report only 66.63% accurancy.

On the Tosca-Sumner dataset, results comfirme the contribution of the use of the belief framework instead of the Bayesian one. The belief classifier reports 97.9% while the Bayesian one reports only 75.65%.

Comparison with related work

In this experiment we compare our method effectiveness to methods proposed by Biasotti et al. [START_REF] Biasotti | A comparison framework for 3d object classification methods[END_REF]]. In their work, authors compared the performance of five similarity measures on four different shape descriptors in classifying 3D objects. The four different shape descriptors used in their paper are: The spherical harmonics (SH) in [START_REF] Kazhdan | Rotation invariant spherical harmonic representation of 3d shape descriptors[END_REF]] which is a volume-based descriptor, The light-field descriptor (LF) in [START_REF] Chen | On visual similarity based 3D model retrieval[END_REF]] which is an image-based descriptor and two topological matching methods, the Multi-resolution Reeb graph in (MRG) [START_REF] Hilaga | Topology matching for fully automatic similarity estimation of 3D shapes[END_REF]] and the Extended Reeb graph (ERG) in [START_REF] Biasotti | 3d object comparison based on shape descriptors[END_REF].The five similarity measures are: The Minimum Distance Classifier (MinDC) which coincides with the Nearest Neighbor classifier, Maximum Distance Classifier (MaxDC) which classifies a query by taking into account the most dissimilar descriptor belonging to the class. The Average Distance Classifier (AvgDC) which is defined as the average distances between the query and the members of the class. The Centroid Distance Classifier (CDC) where the query is classified according to its dissimilarity with a representative member of a class. And the Atypicity Distance Classifier (ADC) which evokes the notion of typicity, to represent how much a descriptor is typical of the class it belongs to, with respect to the elements in the other classes.

In order to demonstrate the effectiveness of our method compared with the Biasotti et al's classifiers, we tested our method on the same dataset used by Biasotti et al. This dataset is a subset of the SHREC07 dataset composed of 280 3D-objects classified into 14 classes. The results of the experiment are shown in Table VI. Each entry is related to the performance of a given shape descriptor (enumerated in the second row) for a given classifier (reported in the first column of the table). The classification accuracy of our method is given in the last row. While Biasotti et al. concluded that the MinDC (nearest neighbor) similarity measure performed the best for all four different shape descriptors in their work, one can notice that our classifier shows the highest classification rate 97.6%. Moreover, the nearest neighbor based approaches require to compare each object to be classified to all objects in the dataset, which seems to be impractical with huge databases where our method is preferred, while it requires matching of only the representative parts. Please note that using a PC with a 3 Ghz Core 2 Duo processor with 3 GB memory, and a Matlab implementation of our algorithms, the running time of the labeling process depends on the quality of the meshes and their number of vertices. The full processing time of a query (from the SHREC07 or the Tosca-Sumner datasets) varies from 2 to 25 seconds.

Reject option contribution

Table VII shows the accuracies for 3D-classification with and without reject option on the Shrec07 dataset. One can notice that the classification accuracy improved from 94.8% to 96.5%. For Bayesian classifier, the 3D-object whose maximum a posteriori probability is below the threshold (T) in Table VII are rejected. When T=0.15, we notice that the Bayesian classifier rejects much more than our classifier. However our accuracy is still higher.

CONCLUSION

In this paper, we have presented a parts-based method for categorizing 3D-objects using a new evidential classifier. The categorization process is completely automated and consists of two different stages. The training stage which lies on the category model building is based on the belief function theory and it goes into two steps: 1) 3D-object partitioning and 2) representative parts construction. The second stage is the labeling, in which belief functions have been also used. In the labeling process, we have introduced a reject option, which can be used to handle the labeling of unknown 3D-objects.

The classifier has been evaluated on two databases of 400 and 380 3D-models. Our system achieved a classification accuracy over 94.8% and 97.9%, respectively on the two datasets. The reject option has also been evaluated and the experimental results obtained on the Shrec07 dataset show that this option efficiently improves the classification accuracy from 94.8% to 96.5%. However, the surface partitioning method used in our framework introduces a bias in the categorizing process. To guarantee stability and performance, this partitioning has to be stable within a same class of objects.

In practice, with the SHREC07 and Tosca-Sumner datasets, partitioning turns out to be homogeneous within most classes. Furthermore, since we have focused our interest to propose meta-algorithm for a relevant categorizing approach, some parts of the method can be changed and tested (3D partitioning, local descriptors). For example, in order to deal with imperfect meshes, we can use volume-based partitioning approaches [START_REF] Mademlis | Combining topological and geometrical features for global and partial 3-d shape retrieval[END_REF] which are preferred than surface-based approaches. In the future, we would like to investigate the integration of the spatial relation between parts in the matching process.

Fig. 1 .

 1 Fig. 1. The training system architecture: the input of the system is categories of 3D-objects. The output is a set of representative-parts. The objects in this figure are selected from the animal and the human categories in the Shrec07 dataset.

Fig. 2 .

 2 Fig. 2. 3D-object partitioning using topology driven 3D mesh segmentation algorithm

Figure 1

 1 presents the different steps of the training process. Given a set of J categories, The Figure shows four main steps applied for each category: (1) object partitioning; (2) part description; (3) part clustering; (4) representative part computation.

ALGORITHM 2 :

 2 : Labeling a new 3D-object Input: Given a training set of J categories Ωc = {Cj} 1≤j≤J . Each category is represented by a set of representative parts.. Given an 3D-object O to be labeled. Begin 1. Partition O into I 3D-parts {Pi} 1≤i≤I ; FORALL Pi in {Pi} 1≤i≤I

Fig. 4 .

 4 Fig. 4. Shrec07 dataset snapshot. Each object corresponds to one category.

Fig. 5 .

 5 Fig. 5. Tosca-Sumner dataset snapshot. Each object corresponds to one category.

Fig. 6 .

 6 Fig. 6. The confusion matrix for a human object part categorization. Rows are query parts. Columns are object categories. (Using the GD2 feature descriptor on the Shrec07 dataset)

Fig. 7 .

 7 Fig. 7. The confusion matrix for some 3D-object categorization. Rows are query object. Columns are object categories. (Using the GD2 feature descriptor on the Shrec07 dataset)

Table II .

 II Classification accuracies with feature descriptor changing on the Shrec07 dataset.

	Test Data	Dataset Size GD2	HSI	Gcords GD2-HSI GD2-Gcords HSI-Gcords
	Training Set	100	96.7	75.6	74.3	96.7	96.7	90.9
	Test Set	300	90.3	70.8	69.9	92.9	91.1	78.5
	Entire Dataset	400	93.5	73.2	72.1	94.8	93.9	84.7

Table III .

 III Classification accuracies with feature descriptor changing on the Tosca-Sumner dataset.TableIV. Classification result comparison with the Bayesian classifier on the Shrec07. (Using the GD2-HSI feature descriptor).

		Test Data	Dataset Size Our methods	Bayesian classifier
					Accuracy (%)		Accuracy (%)
		Training Set	100		96.7		68.9
		Test Set	300		92.9		65.5
		Entire Dataset	400		94.8		66.63
	Table V. Classification result comparison with the Bayesian classifier on the
	Tosca-Sumner. (Using the GD2-HSI feature descriptor)
		Test Data	Dataset Size Our methods	Bayesian classifier
					Accuracy (%)		Accuracy (%)
		Training Set	90		98.9		77.9
		Test Set	290		96.9		73.4
		Entire Dataset	380		97.9		75,65
	Test Data	Dataset Size	GD2	HSI	Gcords GD2-HSI GD2-Gcords HSI-Gcords
	Training Set	90	98.5	82.9	85.4	98.9	96.7	94.3
	Test Set	290	95.2	80.5	82.6	96.9	90.8	90.7
	Entire Dataset	380	96.85 81.7	84	97.9	93.75	92.5

Table VI .

 VI Classification result comparison with related work.

		State of the art methods (Rate%)
		SH	LF	MRG	ERG
	MinDC	89%	88 %	88 %	83 %
	MaxDC 33%	38 %	41 %	38 %
	AvgDC	66%	73 %	74 %	58 %
	CDC	64%	68 %	76 %	60 %
	ADC	63%	68 %	73 %	58 %
		Our method (Rate%)
			97.6%

Table VII .

 VII Classification results with Reject option on the Shrec07 dataset.

	Classification	Training	Test	Reject	Accuracy
	Algorithm	Set Size	Set Size	Rate (%)	(%)
	Our algorithm with reject option	100	400	6.6	96.5
	Bayesian algorithm with reject (T=0.1)	100	400	3.1	68
	Bayesian algorithm with reject (T=0.15)	100	400	7.3	70.7
	Our algorithm without reject option	100	400	0	94.8
	Bayesian algorithm without reject	100	400	0	66.63

ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

ACKNOWLEDGMENTS

This research was supported partially by the Contrat de Projet Etat-Région (CPER) Région Nord-Pas-De calais Ambient Intelligence


S Tuukkanen

S Streiff

P Chenevier

M Pinault

H.-J Jeong

S Enouz-Vedrenne

C S Cojocaru

D Pribat

J.-P Bourgoin

Toward full carbon interconnects: High conductivity of individual carbon nanotube to carbon nanotube regrowth junctions

A versatile chemical vapor deposition (CVD) based method for the fabrication and electrical measurement of individual carbon nanotube junctions was developed. ferritin or Fe particles were grafted on multiwalled carbon nanotubes (MWNTs) and used as catalysts for the subsequent growth of secondary MWNT by CVD. Junctions were then individually connected. The conductivities of the MWNTs and of the junction were measured. Statistical data show that the conductance of the MWNT-MWNT junction is similar to that of MWNT. This result paves the way for the use of carbon nanotubes as electrical interconnects in electronic applications.

Carbon nanotubes (CNTs) can be used in future electronics both as interconnects 1,2 and as functional elements. 3 In particular, CNTs have demonstrated higher electrical conductivity and current density 4,5 than Cu and could avoid difficulties foreseen in nanometer scale Cu interconnects due to electromigration and mechanical instability. Therefore CNTs are appealing candidates for wiring in electronics circuits. 6 Several examples of CNT vias 7,8 and interconnects 9 have been reported recently. However, to develop CNT solutions for interconnects, highly conducting CNT-CNT junctions are required. As CNT to CNT cross contacts are poor, 9 connections could be achieved by metal welding 10 or direct CNT intermolecular Y junction. 11,12 On the one hand, the electrical conductivity of CNT Y junctions has already been investigated, but only in the case of Y junctions obtained in a single growth step. 13,14 However, building CNT interconnects requires the fabrication of T-type junctions by a multiple step process. On the other hand, regrowth of CNT on CNT has In order to realize and electrically connect individual CNT junctions, sample preparation had to be carefully optimized. Namely single regrown CNTs on well separated MWNTs were preferred. First, MWNT-catalyst conjugates were spread at low density on a substrate patterned with an alignment grid so that individual, well separated MWNTs could be localized. Second, the catalyst nature and grafting yield as well as the CVD-growth parameters were fine tuned to obtain suboptimal regrowth yield, and thus favor single regrowth events. MWNT-catalyst conjugates (primary MWNTs) were localized and imaged before and after CVD growth in order to identify newly grown (secondary) MWNTs without ambiguity. Isolated CNT junctions were electrically connected using conventional e-beam lithography and the electrical characteristics of the MWNTs and the junction were measured.

Ferritin was coupled to MWNT through a well-known 18 been demonstrated [15][16][17] but the conductivity of those T-type amide-bond strategy. For this purpose, carboxyl moieties 20 junctions has not been measured and neither was their inte-were generated by acid treatment 21 onto the aerosol-assisted gration into CNT-wiring networks explored. CVD produced MWNTs. MWNTs were then incubated

In the present paper, we describe the fabrication and electrical characterization of individual CNT junctions using chemical vapor deposition (CVD) regrowth. The selective placement of catalyst particles was achieved either by chemical coupling or by electrodirected placement. In a first approach, multiwalled CNTs (MWNTs) were functionalized either covalently with ferritin protein 18 or noncovalently 17,19 by hydrophobic iron oxide nanoparticles (FeO x NPs). Alternatively, bare MWNTs were first electrically connected and FeO x NPs were deposited thereon using dielectrophoresis (DEP). In all cases, MWNT-catalyst conjugates were deposited on a SiO 2 substrate and subsequently calcinated and reduced, yielding MWNT supported Fe(0) particles used as catalyst for the CVD growth of new MWNTs.

with carbodiimide and N-hydroxysuccinimide in aqueous buffer and reacted in situ with ferritin 20 in a ferritin/MWNT mass ratio of 3:2. The obtained MWNT-ferritin conjugates showed a quite high coverage with an average density of about 10 ferritin molecules per 100 nm of MWNT length as evidenced by transmission electron microscopy (TEM) [Fig. 1(a)].

FeO x NPs were obtained by precipitation of iron oleate in boiling dioctylether according to Park et al. 22 Due to the hydrophobicity of their oleate shell, FeO x NPs have a good affinity for MWNT and MWNT-FeO x NP conjugates were obtained by simply coincubating MWNT with FeO x NP (Ref. 20) (mass ratio 1:60). TEM images of the conjugates [Fig. 1(b)] showed MWNT covered with �5 nm particles. The average coverage was about 40 FeO x NPs per 100 nm of MWNT length, which is noticeably higher than for MWNTferritin conjugates. Prior to CVD growth, the samples were calcinated in air at 550 ° C for 10 min to remove the organic shell. CNT growth was performed in an acetylene CVD reactor as de- scribed earlier. 23 The reduction (H 2 , 20 min) of the iron ox

0 1 2 3 4 0 1 2 3 4 0 1 2 3
ide catalysts into Fe(0) was followed by CVD growth (C 2 H 2 ,

Counts

Counts Counts 10 min). 20 We first checked that ferritin and FeO x NP induced CNT growth in our CVD process and optimized the process for growth of small MWNTs on SiO 2 substrates. 20 MWNT growth was preferred to single walled nanotube (SWNT) (Ref. 24) growth from ferritin because individual CNT to CNT junction selection and electrical connection required scanning electron microscopy (SEM) imaging, the resolution of which does not allow individual SWNT detection. The CVD temperature was thus set at 700 ° C to produce small MWNTs. 23 In this process, ferritin and FeO x NP deposited on a SiO 2 substrate yielded MWNT of similar diameters (5-20 nm). In CVD regrowth from the MWNT-catalyst conjugates, the catalyst particles often appeared at the tip of the secondary MWNT [Figs. 1(c) and 1(d)], which suggests a tipgrowth mechanism. SEM images of the MWNT-catalyst conjugates after CVD regrowth are shown in Figs. 1(e) and 1(f). MWNT-FeO x NP conjugates appear almost fully covered with packed particles, whereas MWNT-ferritin conjugates show sparse particles along the MWNT. In order to better control the FeO x NP coverage, DEP-based electrodeposition was performed. 25 MWNTs were first deposited using DEP by applying an ac voltage between electrodes on a chip covered with a drop of MWNT solution. 20 The same procedure was then used for the deposition of FeO x NP in toluene. The high aspect ratio of MWNTs increased DEP attraction toward their tip, 26 favoring FeO x NP deposition at the end of the contacted MWNT. Individual particles can be seen along the MWNT on Fig. 1

(g).

Examples of individual CNT junctions are shown in Figs. 1(c) and 1(d). Secondary MWNTs were usually smaller and appeared brighter than primary MWNTs because they are protruding above the surface, 20 therefore limiting electron transfer to the substrate. Unfortunately, their three- dimensional shape prevented metal connection by e-beam lithography. Therefore, we used a wetting/dewetting cycle in acetone to bend the protruding MWNTs under the meniscus pressure and have them stick to the substrate. After process optimization, approximately 100 CNT junctions were detected on a grid, from which approximately 20 were connected through e-beam lithography and metallization (Pd 5 nm/Au 50 nm).

A typical example of an electrically connected CNT junction structure and its current-voltage (I-V) characteristics are shown in Figs. 2(a) and 2(b). Statistics of the MWNT and junction conductances are shown in Figs. 2(c)-2(e). In all samples, secondary MWNTs were highly conducting (a few microamperes under 100 mV dc bias) and always showed a linear I-V curve. On the contrary, the primary MWNT conductance varied strongly according to the catalyst [Figs. 2(d) and 2(e)]. Their I-V curves were in most cases linear and symmetric, except for a slight S-shape in some highly resistive cases. All samples were fabricated using the same primary MWNTs and thus should show similar intrinsic conductances. The catalyst coupling method should not affect their conductance either since the organic shell around the catalyst was burnt out during calcination. Therefore, the strong conductivity drop in the case of MWNT-FeO x NP was most likely due to the dense FeO x NP coverage around the primary MWNTs, as can be seen in Fig. 1(f), which probably prevented direct electrical connection to the electrode. This drawback could nevertheless be overcome by the more controlled DEP deposition of FeO x NP [Fig. 2(g)]. As a first estimate, although the contact resistance with the metal electrode could rise up as high as gigaohms, the average conductance of the primary and secondary MWNTs lies probably in the 1 -100 f.LS range, in good agreement with previous reports. 7,9 In the case of the CNT junction, the measured conductance was limited by the bottleneck of the conductance path between the Au electrodes, which included two metal-MWNT contacts, two MWNT sections, and the CNT junction itself. The measured conductance of the CNT junction was usually intermediate between the conductance recorded for the primary and secondary MWNTs, which indicates that the CNT junction itself was not the conductance bottleneck. Our CNT junctions could sustain as high as 2 f.LA current.

The effect of gating on the conductance was also studied using a silicon backgate. 20 A very small or no change was observed in the conductance of CNT junctions and primary MWNTs. In the case of secondary MWNTs, a negative gate voltage produced a small (<50%) current increase. This is most likely due to some of the outer shells being semiconducting, as has been described for MWNTs of similar diameter. 27 As a conclusion, the CNT junctions appeared to behave as low resistivity contact elements, as needed for CNT-CNT interconnect use in future electronics. Although the molecular structure of our CNT junctions could not be investigated in detail by TEM, high resolution SEM observation of our regrown sample indicates a probable tip growth process, which implies that the catalyst particle moves away from the junction during the growth. A direct carbon on carbon connection is thus to be expected, as had been described in previous work. 12,16 Applying a versatile CVD-regrowth technique, we fabricated for the first time individual MWNT-MWNT junctions and characterized them electrically. Our method can be tuned to a large extent since catalysts could be bound to the initial MWNT by three independent methods, covalent bonding, hydrophobic association, or DEP driven electrodeposition, all affording similar CVD regrowth yields. Although some of our measurements were hindered by high contact resistance, both primary and secondary MWNTs showed conductivities in the 1 -100 f.LS range. The CNT junction itself did not noticeably decrease the conductivity of the MWNT-network, the metal to primary MWNT contact or the MWNTs themselves being the conductance bottleneck. Our work thus shows that highly conducting CNT interconnects can be developed from CVD growth technique.

FIG. 1 .

 1 FIG. 1. TEM images of (a) MWNT-ferritin and (b) MWNT-FeO x NP conjugates, showing CNTs (white arrows) decorated with metal particles (black arrows). SEM images of individual regrowth events from (c) MWNT-ferritin and (d) MWNT-FeO x NP conjugates. Circles show the probable location of the catalyst particle. SEM images showing the primary MWNTs after CVD growth in (e) MWNT-ferritin, (f) MWNT-FeO x NP, and (g) MWNT with DEP deposited FeO x NP samples.

FIG. 2 .

 2 FIG. 2. (Color online) (a) SEM image and (b) I-V characteristics of an electrically connected CNT junction obtained from MWNT-FeO x NP conjugates. [(c)-(e)] Histograms of conductances (see Ref. 20) for (c) MWNTferritin, (d) MWNT-FeO x NP conjugate, and (e) DEP deposited MWNT and FeO x NP samples. The primary CNT is measured between electrodes 1 and 2, the secondary CNT between 3 and 4 and the junction between 2 and 3.

The authors want to thank V. Derycke for his continuous interest and support in this work. We acknowledge the financial support from French ANR (Nanoreseaux project) and from Region Ile de France for funding our nanofabrication facility (SESAME project).


Laurent Gantel

Mohamed El

Amine Benkhelifa

Fabrice Lemonnier
email: fabrice.lemonnier@thalesgroup.com

François Verdier
email: francois.verdier@unice.fr

M E A Benkhelifa

Module Relocation in Heterogeneous Reconfigurable Systems-on-Chip using the Xilinx Isolation Design Flow

Keywords: FPGA, hardware thread, dynamic reconfiguration, module relocation, Isolation Design Flow

published or not. The documents may come

L'archive ouverte

I. INTRODUCTION

With the flexibility brought by the Dynamic and Partial Reconfiguration (DPR), the adaptation of the thread model on the hardware accelerator became interesting. Hybrid Thread [START_REF] Anderson | Supporting high level language semantics within hardware resident threads[END_REF] is a hardware thread model based on the POSIX 1 thread model. It contains a memory stack used to stock data parameters. It permits to process system calls understandable by a software thread, running on a CPU. This approach is pursued in ReconOS [START_REF] Lubbers | A portable abstraction layer for hardware threads[END_REF], where the hardware threads and a system call API, both described in VHDL, are proposed to make the programming process easier. In all these cases, as well as in SHUMDR [START_REF] Wang | The hardware thread interface design and adaptation on dynamically reconfigurable soc[END_REF], the thread is composed at least by a finite state machine to sequentially control the accelerator execution.

Some works such as [START_REF] Hübner | New 2dimensional partial dynamic reconfiguration techniques for real-time adaptive microelectronic circuits[END_REF] or [START_REF] Becker | Enhancing relocatability of partial bitstreams for run-time reconfiguration[END_REF] already used the DPR feature provided with Xilinx FPGAs to dynamically load new features into a running design. The thread was relocated 1 Portable Operating System Interface from the genuine bitstream. Such an approach allows dataflow treatment but is not flexible enough for more complex accelerators. Context management, as in [START_REF] Carver | Relocation and automatic floor-planning of fpga partial reconfiguration bitstreams[END_REF], combined with DPR permits to stop and restart a hardware thread at any time, offering hardware thread preemption capabilities.

All these processes must be executed by an operating system. To reduce timing overhead caused by dynamic reconfiguration, this operating system would have access to services implemented in hardware such as ICAP driver [START_REF] Liu | Run-time partial reconfiguration speed investigation and architectural design space exploration[END_REF] or relocation modules [START_REF] Rossmeissl | Partial bitstream 2-d core relocation for reconfigurable architectures[END_REF].

At present, when implementing dynamic modules in a reconfigurable system, the static routing of this system can cross over the dynamic areas. Consequently, relocating a bitstream without corrupting the static routing is not possible. To deal with this issue, new tools have been developed by the community. RapidSmith [START_REF] Lavin | RapidSmith: Do-It-Yourself CAD Tools for Xilinx FPGAs[END_REF] offers the ability to implement its own placer-router, whereas OpenPR [START_REF] Sohanghpurwala | OpenPR: An Open-Source Partial-Reconfiguration Toolkit for Xilinx FPGAs[END_REF] is an open-source based on the same routing engine which permits to create independent partition using blocker macros [START_REF] Koch | Fine-Grained Partial Runtime Reconfiguration on Virtex-5 FPGAs[END_REF]. These macros prevent the static routing from crossing inside the reconfigurable partitions. However this tool is not integrated into the standard flow and the number of supported devices is limited. In order to keep using the Xilinx tools, we rely on the new Isolation Design Flow [START_REF] Corbett | Xilinx White Paper 412: The Xilinx Isolation Design Flow for Fault-Tolerant Systems[END_REF] and some additional constraints to design homogeneous and relocatable partitions.

The paper is organized as follow. A brief definition of a HRSoC is given in Section II. Then a hardware thread model is introduced in Section II-A. Section III deals with the management of this kind of thread by an operating system and especially how we perform thread relocation. Finally, a new design flow to create identical dynamic partitions relying on the Isolation Design Flow is detailed in Section IV. To conclude, implementation results as well as conclusion and future work are presented respectively in Section V and VI.

II. CONTEXT AND MOTIVATIONS

Reconfigurable platforms based on different processing elements are called Heterogeneous Reconfigurable Systems-on-Chip (HRSoC). In such a platform, the application is divided into tasks. Some tasks are implemented as hardware accelerators and allocated into a partition of the chip, while others run as software tasks on computing processor elements. A hardware accelerator is defined as a hard-wired function developed to accelerate the processing of a task. A computing processor unit could be a General Purpose Processor, a specialized one like a Digital Signal Processor, a Graphics Processing Unit or a simple Micro-Controller Unit. Each one of these processing elements is more or less suited to certain types of tasks. We specified and implemented a HRSoC platform in the FOSFOR project [START_REF] Gantel | Dataflow programming model for reconfigurable computing[END_REF] (Flexible Operating System FOr Reconfigurable platform). This project aimed to define a reconfigurable multicore heterogeneous platform (Fig. 1). In the case of this project, hardware threads are managed by a hardware operating system (Flexible HwOS) implementing similar services in hardware to those offered by the operating system, such as thread management, semaphore counters or mailboxes.

A. Hardware Thread Model

The hardware thread (HT) we implemented in the FOS-FOR project consists in two independent zones (Fig. 2). A static zone, corresponding to the interface between the thread and the rest of the system. Through this interface, the thread can communicate with the HwOS and so with the other threads. The OS interface is a memory accessible at the same time by the thread and by the HwOS. A last interface allows the thread to take advantage of multicore platforms allowing it to access to a dedicated network. For this project, a custom network-on-chip has been developed to enhance memory accesses [START_REF] Devaux | Flexible communication support for dynamically reconfigurable fpgas[END_REF].

The dynamic zone consists of a logical user function (ie. the accelerator), and a finite state machine (FSM) to sequence system calls. This user FSM is controlled by a static system FSM, able to react to HwOS commands (start, suspend or stop commands). Separation between system and user zones is done in order to plan hardware thread preemption management. Namely, our objective is to allow the operating system to relocate a hardware thread in any available slot of the platform.

III. HARDWARE THREAD MANAGEMENT

An operating system managing hardware threads would rely on three services which are, a context management service, a reconfiguration service and a relocation service.

A. Context Management Service

There are two ways to save the context of a hardware thread. Either using check-pointing mechanisms [START_REF] Huang | Software-controlled dynamically swappable hardware design in partially reconfigurable systems[END_REF] or processing partial readback [START_REF] Lee | Hardware Context-Switch Methodology for Dynamically Partially Reconfigurable Systems[END_REF]. The first one is intrusive and implies that the developer inserts checkpoints in his source code. Checkpoints are the only moments where the preemption is enabled. To preempt a thread, the scheduler has to wait that the thread reaches a checkpoint and so saves its context. Consequences are a time overhead at each checkpoints and latency in preemption decision. The advantage is that the context size could be dramatically reduced, and ideally to zero.

The second way is technology dependent but it avoids real time failure since preemption could be done immediately without risk to lose information. Readback consists in reading the contents of the partial zone where the module is located. Segregation between static part and dynamic part inside hardware thread permits task context reduction and offers a common interface in order to integrate different accelerators in the same partition.

B. Reconfiguration Service

A design using partial dynamic reconfiguration, as the one provided by Xilinx FPGAs [START_REF] Lysaght | Invited paper: Enhanced architectures, design methodologies and cad tools for dynamic reconfiguration of xilinx fpgas[END_REF], is composed of a static part and defined reconfigurable zones in which reconfigurable modules can be loaded. Using this technology, the operating system is able to schedule hardware threads [START_REF] Belaid | Off-line placement of hardware tasks on fpga[END_REF], without resetting the rest of the system. For real-time applications, both readback and reconfiguration overheads must be minimized using a dedicated hardware reconfiguration controller, such as FaRM [START_REF] Duhem | FaRM: fast reconfiguration manager for reducing reconfiguration time overhead on FPGA[END_REF], Uparc [START_REF] Bonamy | UPaRC, Ultra-fast power-aware reconfiguration controller[END_REF] or the solution offered by Koch et al. [START_REF] Hansen | High Speed Partial Run-Time Reconfiguration Using Enhanced ICAP Hard Macro[END_REF]. For instance, FaRM which is used in the design test detailed later allow to process configuration with a throughput of 400 MB/s.

C. Relocation Service

As logic resources are critical in FPGAs, we would want to be able to run several threads in the same reconfigurable slot. One of the issue encountered in the classical flow is that a partial bitstream for a given module is generated for one slot and only one. To load a module on another slot, we need either another bitstream, which is memory consuming, or a relocated bitstream, whose creation is time consuming. In embedded system, with the increase of the FPGAs size, and so of the bitstream size, the amount of memory needed to store one specific partial bitstream for each targeted partition is becoming more and more prohibitive. This is why a relocation service seems to be the best choice. To relocate a partial bitstream, we implemented two services: a bitstream parser and a bitstream relocater.

A bitstream parser is needed to find the right information in the bitstream. Xilinx FPGAs are organized in rows and columns. Each column is composed of several frames, which is the smallest reconfigurable entity. To reconfigure a FPGA, the ICAP reads a bitstream, writes address information in the Frame Address Register (FAR) of the ICAP and writes frames contents into FPGA memory. Information which interests us in the bitstream is the FAR values and the CRC value. The process to relocate a partial bitstream is detailed in Fig. 4.

This process needs two bitstreams, one for the source partition and the other implemented for the target partition. A readback is done on the first partition. The resulting context is then saved in a new bitstream. The headers and footers of the second bitstream are then modified to target the wanted partition modifying the FAR and adding a newly computed CRC values. Finally, merging the headers and the saved context, we get a new relocated bitstream.

D. Interconnect implementation issues

In order to be able to safely relocate a dynamic module, the two dynamic reconfigurable partitions have both to be connected to the static partition in the same relative way. A signal going from the static partition to the reconfigurable module has to pass through a predefined route and to follow the same route in each reconfigurable partition. If it is not the case, hardware failures could occur and permanently damage the chip while relocating a bitstream. In order to do so, we want to have the ability to add some constraints on the inputs and the outputs of the LUTs used to interconnect the static and dynamic partitions, forming what is commonly called a bus macro. To achieve this goal, we designed hard macros using the XDL language [START_REF] Beckhoff | The Xilinx Design Language (XDL): Tutorial and use cases[END_REF]. This language allows to textually describe the route used by each nets in a component or even in a full design. Another issue in thread relocation management is the routing conflicts between the static and the dynamic part. In the current provider tools, the static routing cross over each dynamic partition in different ways. To prevent the overlapping of this static routing, the routing and logic resources contained in these partitions have to be prohibited to the static partition. To achieve it, it is necessary to insert additional constraints. These constraints can be added using the Isolation Design Flow.

IV. DESIGN TOOLS FLOW

The Isolation Design Flow (IDF), alternatively called Secure Chip Crypto (SCC) design flow, has been created to target fault-tolerant systems, especially in the critical applications in which safety and fault containment is a primary objective. This flow allows a designer to isolate the different modules of his system against each other. This is done regarding both the logic and the routing resources.

In this flow, each module to isolate is defined and synthesized separately. A top-level module groups all these modules as black boxes. To ensure a correct isolation, the implementation of these modules is done under some constraints. Namely, every connections between two isolated partitions have to pass through trusted routes (Fig. 5). A trusted route specifies that an output of a partition has to pass through a direct route to reach another partition. If the output is used as a load for two different inputs, this signal have to be split into two different signals passing through a LUT resource, and so forms what is called a trusted route. These constraints have to be applied to every inter-partitions signals when it is necessary except for the global signals such as the clock or the reset.

Moreover, in each isolated module, inputs and outputs which are not directly connected to an input or an output pad has to be defined as a non-buffered port as follow: attribute buffer type: string; attribute buffer type of <port name> : signal is "none";

In the case of the relocation where routes between the static partition and the dynamic ones have to be relatively identical, we instantiated hard macros to connect these two types of partition (Fig. 6). Once all modules are synthesized, the main part of the flow is done using the PlanAhead tool. Modules netlists are imported in the design and these which need to be isolated are converted into partitions. Each partition is configured with the SCC ISOLATION attribute, which notifies that the partitions have to be designed using the Isolation Design Flow. Then the physical block of each module is placed inside the FPGA matrix. Another constraint imposed by the Isolation Design Flow is that the input and output pads used by a partition have to be included inside the region covered by its corresponding physical block. In addition, the boundary between two isolated partition have to be of at least one CLB-wide, horizontally or vertically. This boundary is called a Fence and is an area in which neither the logic resources nor the routing switch matrices will be used. The following location constraints applied to the hard macros have to be inserted in an external constraint file and passed to XST using the -uc flag:

INST <hard macro name> LOC = SLICE X#Y#;
where "#" represents valid Slice X and Y coordinates. This flag ensures that the synthesizer will respect the location constraints and that the hard macro will be placed at the correct position, over the static and the dynamic boundary. Finally, once the design is placed and routed, the correct isolation of each partition can be checked with the help of the Isolation Verification Tool (IVT) [START_REF] Corbett | Xilinx White Paper 412: The Xilinx Isolation Design Flow for Fault-Tolerant Systems[END_REF]. In a first step, we experienced the implementation of relocatable hardware module using the Isolation Design Flow on the simple design illustrated in Fig. 6, and implemented on a Virtex 5 SX50T FPGA using the version 13.1 of IDS 2 . It is a Microblaze-based platform composed of the FaRM IP used to reconfigure the dynamic partitions, a hardware CRC module used to compute the new CRC of the relocated module as well as two dynamic modules. There is no external memory. The only off-chip connections are the FPGA clock and the reset button. The two reconfigurable modules implement respectively a two-bits adder and a twobits multiplier. Each one of these modules is controlled by the processor through a dedicated GPIO peripheral.

V. IMPLEMENTATION

As trusted routes are direct routes from one partition to another, the number of available paths to route a signal is limited. To simplify the routing of the hard macros, we first implement "soft macros" instantiating LUTs directly in the top level module for one of the partitions. After the place and route phase, hard macros are extracted from the design netlist using using the RapidSmith framework [START_REF] Lavin | RapidSmith: Do-It-Yourself CAD Tools for Xilinx FPGAs[END_REF]. Finally, the extracted hard macro is applied on each partition and the design is implemented once again.

After implementation (Fig. 7), the two modules are well isolated in terms of logic and routing resources, and the one CLB-wide boundary between the dynamic modules and the static partition is respected. This result permitted us to perform a safe relocation of these two modules in the available dynamic partitions without additional bitstreams.

VI. CONCLUSIONS AND FUTURE WORK

We implemented a design in which two identical partitions have been created. The design flow based on the Isolation Design Flow allowed us to ensure that the relocation process can be executed without damaging the FPGA device. Moreover, this design flow relies on additional tools and routing techniques provided by Xilinx which is non-intrusive regarding to custom tools. For the moment, we target only partitions which offers the same set of resources but as FPGAs size is increasing continuously, as shown by the presence of super logic region (SRL) in the latest Virtex 7 FPGAs, finding identical areas in a FPGA will become less and less difficult. The simple example design implemented in this article has been used as a proof of concept. We are currently applying this design flow on the FOSFOR platform in order to relocate hardware threads in a real and more complex application. In future work, as introduced in [START_REF] Koester | Design Optimizations for Tiled Partially Reconfigurable Systems[END_REF], implementing and comparing a set of bus macros respecting in our case the IDF constraints, will help us to evaluate more precisely the usability and the interest of this design flow. In addition, we aim to integrate this work with previous work about on-line scheduling and placement algorithms in order to provide an efficient thread management service to heterogeneous reconfigurable systems-on-chips.

7 Figure 1 .

 71 Figure 1. FOSFOR Architecture

454367892AAFigure 2 .

 2 Figure 2. Hardware Thread (HT) Architecture

Figure 3 .

 3 Figure 3. ICAP for Partial Reconfiguration

Figure 4 .

 4 Figure 4. Partial bitstream relocation process

Figure 5 .

 5 Figure 5. Trusted routes

Figure 6 .

 6 Figure 6. Test design

Figure 7 .

 7 Figure 7. Design test -Partition isolation

ISE Design Suite

ACKNOWLEDGMENT

We would like to acknowledge Xilinx for its support and the access to the Isolation Design Flow.