Romain Peretti

Guillaume Gomard

Loïc Lalouat

Christian Seassal

Emmanuel Drouard
email: emmanuel.drouard@ec-lyon.fr

Absorption enhancement in photonic crystal thin films by pseudo disordered perturbations

The effects resulting from the introduction of a controlled perturbation in a single pattern membrane on its absorption are first studied and then analyzed on the basis of band folding considerations. The interest of this approach for photovoltaic applications is finally demonstrated by overcoming the integrated absorption of an optimized single pattern membrane through the introduction of a proper pseudo disordered perturbation.

INTRODUCTION

Photonic nanostructures have been intensely investigated in the framework of thin and ultra-thin film solar cells for light management purposes in order to improve the light collection, and enhance the absorption close to the energy bandgap of the active material through light-trapping schemes. In this context, the concept of absorbing photonic crystal (PhC) has emerged [START_REF] Seassal | SPIE Photonics Europe, Photonics for Solar Energy Systems II, Proceedings of SPIE[END_REF]. It is based on the patterning of the active layer itself, in which nanoholes are periodically drilled. Theoretical and experimental studies have demonstrated that such a configuration, if properly designed, could be beneficial for the absorption over the whole spectral range considered [START_REF] Gomard | [END_REF]. Thus, at short wavelengths, the PhC patterning leads to a significant decrease of the reflection losses while at large wavelengths, new absorption peaks appear and result from the coupling of the incident light with pseudo guided modes. Beyond those remarkable features, it turned out that due to the limited number of pseudo guided modes supported by this periodical structure, it is highly challenging to avoid large dips in the resulting absorption spectrum close to the bandgap. Motivated by the prospect of further enhancing the absorption in this spectral region and improving the angular and polarization tolerance of the patterned layers, several research groups have recently studied the introduction of structural disorder within those PhC membranes. The latter, which is most often position disorder, falls into three categories: multiperiodic patterns, correlated-disordered configurations and random structures. Using a controlled amount of disorder, absorption enhancements with regards to a single pattern PhC could be reported, which was attributed to more favorable coupling conditions and to the introduction of new absorption peaks [3][4][5].

In this paper, we propose to analyze the origin and the properties of the added modes so as to facilitate the engineering of such perturbed structures. Let us first consider a single pattern membrane possessing an isolated absorption peak in its low-absorbing region. This resonance is supposed to result from the coupling to a slow Bloch mode (SBM) which is pseudo guided in the membrane. Using the time domain coupled mode theory, it can be shown that a maximal peak absorption is reached at the resonant wavelength of the mode when the absorption losses of the mode equal the external ones [START_REF] Gomard | [END_REF]. This situation is known as the critical coupling conditions, and can lead to absorptions up to 100% at a single wavelength if the absorption of the peak considered is added to the absorption of Fabry-Pérot and/or surrounding SBM resonances [6,[START_REF] Peretti | SPIE Photonics Europe, Photonic Crystal Materials and Devices X, Proceedings of SPIE[END_REF]. The optimal operation regime is nevertheless different if one wants to optimize the integrated absorption of the isolated peak considered, which is the relevant quantity for photovoltaic applications. Indeed, its value depends not only on the peak absorption, but also on the width of the absorption peak. The latter, which can be related to the quality factor (Q) of the mode, increases together with its external losses. Consequently, it appears that the integrated absorption of an isolated peak is maximized when the external losses are dominating over the absorption ones (overcoupling regime) [START_REF] Gomard | [END_REF].

OPTIMIZATION

Thus, the addition of disorder in a regular lattice potentially enables to enhance the integrated absorption of the membrane via two mechanisms: the filling of the lowabsorbing region with new absorption peaks thanks to the coupling of the incident light into additional SBM, and the improvement of the coupling conditions to maximize the integrated absorption of each mode. Those two mechanisms are reviewed in more details in the following sections.

EFFECTS OF THE INTRODUCTION OF A PERTURBATION IN MEMBRANES Methodology and structures studied

The absorption of the structures studied, calculated for a normal incidence of the light, is obtained using Finite-difference time-domain (FDTD) simulations by taking into account the chromatic dispersion of the optical indices of a-Si:H (see [9] for details). The integrated absorption of the structures (under AM1.5G illumination) and the corresponding short circuit current density J sc (assuming an internal quantum efficiency of 1) can thus be easily derived. To analyze the modes involved in the absorption, their Q factors are estimated using a harmonic inversion algorithm (Harminv [10]). Those quality factors are compared to the critical quality factor Q c [9] which is obtained when the external losses equal the intrinsic (absorption) losses. It is used as a benchmark for identifying the various coupling regimes, especially the overcoupling regime where Q is lower than Q c .

The first configuration investigated in this paper, used as a reference, is based on a feasible structure and consists in a 195 nm thin layer of hydrogenated amorphous silicon (a-Si:H) on a glass substrate. The absorbing layer is fully etched by cylindrical nano-holes arranged according to a square lattice (corresponding to a C 4V point group), as depicted on Figure 1.a (left). For the sake of clarity, the geometrical parameters (period a = 220 nm and surfacic air filling fraction ff = 50%) of this single pattern (SP) membrane are chosen so that only one absorption peak is present in the wavelength range where resonant modes (Q>10) are Proceeding of Material Research Society Fall Meeting 2013 needed, namely above around 600 nm, where the extinction coefficient of a-Si:H is below 0.17 [9].

The corresponding absorption spectrum is reported on Figure 1.a (right), together with the one of an equivalent unpatterned membrane for comparison. Three modes are identified by the modal analysis: two of them are anti-symmetric with respect to the (xy) plane of the membrane, and therefore cannot couple to a plane wave under normal incidence (i.e. in Γ) [9,[START_REF] Sakoda | Optical properties of photonic crystals[END_REF], and one of them is symmetric and generates an absorption peak at 666 nm as its coupling with the incident light is allowed. It can be noted that the overcoupling regime is barely reached, since its Q factor is almost equal to Q c .

To investigate the effects of disorder, a second configuration, referred to as "Multiple Pattern" (MP), will be simulated. It corresponds to a simple perturbation scenario as only the position of some holes is changed while conserving the overall C 4V symmetry and ff. Considering a supercell of size 3ax3a, this can be achieved by moving the four holes located at the corners of the supercell towards its center, as shown on Figure 1.b. This symmetric multiple pattern configuration will be used to derive general conclusions on the effects of disorder, which will be then extended to any non-symmetric and space-correlated disorder structures. We express the magnitude of the opto-geometric perturbation (denoted M) applied to a supercell of period Na as:

( ) ( ) ( ) ( ) S n dS Na n M on perturbati ∆ ∆ = ×       × ∆ = ∫∫ λ λ λ 2 1 (1)
where the first term is the refractive index difference between a-Si:H and air, and the second one is the infinitesimal displacement area induced by the perturbation and integrated along the x and y directions. Since the refractive index difference is similar for the different perturbations, the latter can be simply expressed by the magnitude of surface perturbation ∆S (in square period units) which does not depend on the wavelength considered. In our case, ∆S will be limited by the fact that the overlap of holes is not allowed in order to keep the same ff and facilitate the analysis of our results.

Effects of the introduction of controlled disorder in symmetric patterned membranes

This section aims at emphasizing the consequences of introducing a controlled amount of disorder inside the SP membrane leading to the MP configuration presented on Figure 1.b (N = 3). We will focus on the wavelength range of interest between 600 and 750 nm. As soon as a small perturbation is introduced, new modes appear as highlighted on Figure 2.a. Globally, they are spectrally separated from the mode at 666 nm, and therefore only weakly perturbing the original peak. The main consequence is the creation of additional absorption peaks. Both phenomena can be translated into an enhancement of the integrated absorption (see Figure 2 b). The latter keeps increasing as ∆S tends to its highest limit, gaining up to +5.5% in absolute value with regards to the SP (∆S=0) configuration. A closer look at the Q factors of the new modes shows that they are progressively decreased when ∆S is strengthened, sometimes far below their corresponding Q c (over-coupling regime), with the already mentioned consequences of the broadening of the peaks and an improvement of the overall integrated absorption [START_REF] Gomard | [END_REF]. Finally, as the resonant wavelengths of the added modes are also sensitive to the perturbation, this result in an overlap of the modes and less dips in the spectrum.

Increase of the spectral density of modes through band folding mechanisms

The creation of additional modes which have the potential to couple to an incident plane wave can be qualitatively explained by considering the band folding mechanisms occurring within the reduced Brillouin zone (RBZ) of the structures studied and assuming very low perturbations (∆S 0). This situation is depicted on Figure 3.a. As can be seen on this simplified schematic, as the period of the MP supercell is 3 times higher than for the unperturbed cell (in real space), several high-symmetry points corresponding to the MP are introduced in the first RBZ of the SP structure. Taking the example of the Γ MP point represented by the black dot, the folding mechanism may allow to couple modes in vertical direction (Γ MP ) which were not located at Γ SP . Two folding schemes, summarized on Figure 3 .b, can be distinguished: either the folded branches cross at the same frequency giving rise to a degenerated mode which can couple to a normal plane wave [9,[START_REF] Sakoda | Optical properties of photonic crystals[END_REF], or cross at different frequencies (anti-crossing configuration) in which case the added modes in Γ MP will not be able to couple with the normal incident light. It follows that only the former situation will generate new absorption peaks. It should be also precised that the present description gives information on the number of modes introduced, but not on their frequencies. In addition, a rigorous analysis of this symmetric MP structure in its reciprocal space, as developed in [9] for modes that can couple under normal incidence, enabled to conclude that the density of modes is increased by a factor of N² for supercells whose unit cell area is N² times larger than that of the SP structure (provided that the spectral range of interest is broad enough). Theoretically, this can potentially lead to N² times more peaks in the absorption spectrum, although it should be precised that the actual number of peaks contributing to a real increase of the absorption is lower as they should be located in the low-absorbing spectral region and present favourable coupling conditions. This demonstration can be generalized to any space-correlated disorder structures (with a supercell period N) such as non-symmetric MP configurations. As the original symmetry is broken, the folded modes are split into two as they are no longer degenerated. Besides, the other modes which were uncoupled for symmetry reasons can now be coupled under normal incidence. As they are twice as numerous as symmetric modes, the overall number of modes which can be coupled with such perturbations is 4N² times the number of modes in the SP case.

Case study: absorption enhancement in a pseudo disordered membrane

As an illustration of the previous sections, we studied the effects of a pseudo disordered perturbation for which the holes are moved in their own subcell according to a normal distribution. This perturbation was introduced in an optimized SP membrane (a = 345 nm, ff = 50%) [9]. As evidenced on Figure 4, the pseudo disordered 3ax3a membrane presents not only more absorption peaks above 600 nm than the SP membrane but also broader ones, resulting in an absolute integrated absorption increase of 2%. This value was only obtained for ∆S = 0.6(Na) 2 , suggesting the existence of an optimum value of the perturbation as underlined in other studies [3].

CONCLUSIONS

The absorption of a single patterned membrane can be overcome by the introduction of a controlled amount of position disorder thanks to the broadening of the absorption peaks and the increase of the density of modes which directly depends on the size of the supercell considered.

Figure 1 .

 1 Figure 1. a) Schematic representation of the single pattern membrane (left) and absorption spectra of the unpatterned and single pattern membranes (left axis) in correspondence with the calculated Q c (red

Figure 2 .

 2 Figure 2. a) Evolution of the absorption spectrum and of the Q factors of the modes with ∆S in the MP structure (Q c depicted with dashed line. b) Influence of the perturbation magnitude on its J sc and integrated absorption.

Figure 3 .

 3 Figure 3. a) First RBZ of the SP structure (in black, labeled "SP") depicted with some high-symmetry k points of the MP supercell (in red, labeled "MP"). b) Band folding corresponding to a crossing (left) or anticrossing (right) situation.

Figure 4 :

 4 Figure 4: Absorption increase in an optimized SP structure via a pseudo disordered perturbation.

ACKNOWLEDGMENTS

This work was supported by the European Community (FP7 project PhotoNvoltaics N°309127) and by Orange Labs Networks (contract 0050012310-A09221).


Benoit Leprettre
email: benoit_leprettre@mail.schneider.fr

Nadine Martin Lis

Schneider Electric

Extraction of Pertinent Subsets from Time-Frequency Representations for Detection and Recognition Purposes

Keywords: Non stationary signal interpretation, Time-frequency representation, Watershed segmentation, Kalman filter, Trajectory tracking, Capon filter, Minimum variance estimator, Autoregressive model, Spectral analysis

A time-frequency representation can highlight non-stationarities in a signal. We propose to extract subsets from the Time-Frequency Representation (TFR) for classification or recognition purposes. We developed two approaches. The first one is developed for TFRs obtained from the Short Time Fourier Transform or the gliding Minimum Variance method. The extraction of compact subsets is viewed as a segmentation of the TFR, which is performed by morphological filtering and Watershed segmentation. The second approach is developed when the TFR has been obtained using parametric estimators. We consider a hybrid estimator, the ARCAP method, and use a Kalman filter trajectory tracker to extract spectral lines. The proposed methods are illustrated by examples on natural signals : dolphin whistle acoustical signals, cavitation signals and seismic signals produced by snow avalanches.

Résumé

Une représentation temps-fréquence peut mettre en évidence les non-stationarités présentes dans un signal. Nous proposons d'extraire des sous-ensembles ou motifs d'une représentation temps-fréquence (RTF), ceci pour des objectifs de classification ou d'interprétation. Nous avons développé deux approches. La première s'applique sur des RTF obtenus soit par une transformée de Fourier à court terme, soit par la méthode de Minimum de variance glissante.

L'extraction de motifs est vue comme une segmentation de la RTF, segmentation réalisée par des filtres morphologiques et par la méthode de la ligne de partage des eaux. La deuxième approche est développée sur des TFR obtenus à partir d'estimateurs spectraux paramétriques. Nous avons considéré un estimateur hybride, la méthode ARCAP, et développé des filtres de Kalman pour réaliser un suivi de trajectoires dans le plan temps-fréquence afin d'extraire les lignes spectrales au cours du temps. Les deux méthodes proposées sont illustrées à l'aide d'applications sur des signaux réels : signaux acoustiques de sifflements de dauphins, signaux de cavitation et signaux sismiques créés par des avalanches de neige.

Introduction

Time-frequency (TF) analysis is of great interest when one needs to process a recorded signal in order to make a decision by detecting specific features. Time-Frequency Representations (TFRs) can highlight differences between several types of non-stationary signals and help greatly in the classification or decision task. As a TFR is highly redundant, taking into account a limited number of relevant subsets can improve the quality of the decision. In this paper, we present two approaches for extracting subsets from specific TFRs. The first one, in section 2, is developed for TFRs represented as a full [time, frequency, power or energy] matrix. The second one, in section 3, is developed for TFRs in which only some points are associated to a power or energy value. The proposed feature extraction methods are illustrated with examples on natural signals.

As the purpose of this paper is not to review the different existing TRFs, we just indicate the methods we have used. In the first proposed approach, we use the Gliding Minimum Variance (or Capon's) method assuming a local stationarity [Martin 95], [Durnerin 00]. The structure of the TFR is similar to that of a spectrogram, in the sense that a power value is assigned to each point of the defined TF plane. Figure 1 is an example of such TFR and will be described in section 2.2. However, the achieved TF resolution is higher and the variance of the estimator is lower. The obtained TFR is a full N w xN f matrix P, where element P [n,f] is the power of the signal at discrete time n and at frequency f. N w (resp. N f ) is the number of points in time (resp. frequency). The aim here is the extraction of compact TF patterns. This first method is well suited to process narrow and broad band signals.

In the second approach, we use the gliding ARCAP estimator [Martin 95], [Padovèse 96], [Leprettre 98]. This hybrid method estimates the signal frequencies from an AR modeling of the signal. At these estimated frequencies, the power values are estimated by Capon's estimator. Unlike the Minimum Variance TFR or the spectrogram, the obtained ARCAP TFR, a N w xN f matrix P too, is not of full-matrix type. It is a "cloud of points"type TFR. With a model of order M AR , only N f = M AR /2 frequency points with corresponding powers are identified at each time n instead of a complete spectrum. By juxtaposing this set of points on a 3D time-frequency-power coordinates system, separated, coherent spectral lines appear. Figure 4-a is an example of such TFR and will be described in section 3.2. If M AR was set correctly, these spectral lines represent the somehow organized TF components of the signal. We call TF trajectories those relevant spectral lines that we aim to extract. As it highlights spectral lines, the ARCAP TF estimator is suited to process narrow-band signals or signals made of several pure frequencies.

Extraction of Subsets from the Matrix-Type TFRs

As the obtained TFR is a N w xN f matrix, the extraction of a subset can be seen as an image segmentation problem.

Several techniques have been developed in the fields of Image Processing and Pattern Recognition. However, a TFR is a very particular type of image. The generation process of the image is known: it consists of successive estimated spectra juxtaposed along the time axis. The method and the parameters (e.g. window length, overlap) used for the analysis are known. A priori knowledge is available: the characteristics of the analyzed signal may allow selecting the areas of interest inside which patterns should be sought for. A TFR is anisotropic: the dimensions along the axes of the image are physically different (time, frequency, power). It has a relevant amplitude structure: in some cases, one needs to extract patterns that are not iso-energetic. Patterns corresponding to transient, evanescent signals produced by sources of varying power (e.g. animals sounds) may not be completely extracted with an iso-energetic method. In that case, nonlinear filters can be an interesting alternative.

We propose to apply morphological operators.

Extracting features from the TFR using Mathematical Morphology

We propose to use methods based on Mathematical Morphology to take the a priori knowledge into account and extract the pertinent subsets [Pierson 97]. Two steps corresponding to Beucher's segmentation paradigm [Beucher 90] can be considered in the proposed approach.

Step 1: Modeling the a priori knowledge by transforming the TFR Let P=P[n,f] be the considered TFR matrix obtained using Minimum Variance estimation. The procedure is the following: 1) Define criteria that allow distinguishing between the noise and the interesting patterns, e.g. the peak power of a pattern and / or the contrast between a peak of the TFR and the surrounding background noise. 2) According to the selected criteria, define and calculate a transform of the TFR that highlights the frontiers between the patterns of interest and the background noise. This transform changes the original TFR into P' [n,f] that will eventually be segmented. If the criterion is the contrast, the corresponding transform can for example be the modulus of the morphological gradient defined in [Serra 82]. 3) Use this function to mark in P' [n,f] the areas of interest (patterns to extract) and these corresponding to the noise. The markers can be obtained by simply thresholding P' [n,f] or using more elaborate morphological transforms (e.g. a combination of Top-Hat Transforms, erosions, dilations, etc.), depending on the characteristics of the TFR and on the complexity of the recognition problem. This part of the procedure, sometimes called the "intelligent" part, involves all the user's knowledge in order to try understanding the TFR.

Step 2: Extracting subsets automatically using the Watershed method

The second step of the procedure is automatic and is aiming to really extract the relevant subsets. First, a modified function P'' [n,f] is reconstructed by eroding the noise markers. Then, the Watershed method [Beucher 90][Vincent 91] is used on P'' [n,f] in order to obtain closed contours following the local maxima of P'' [n,f], i.e. the ridgelines of the TFR. The interesting point is that this method is non parametric and the obtained subsets are not necessarily iso-energetic. The Watershed method thus allows to extract contours with non homogenous power, or to extract interesting patterns of different power levels from a TFR.

Application on real data

The signal on figure 1 Hz. Signal and noise markers are calculated from this knowledge (figures 1b-c). Details of the procedure are in [Pierson 97]. After this first step, which must be adapted to each context, the watershed method is applied. Figure 1d shows that only the features of interest are extracted. Classical iso-energetic segmentation (figure 1e) extracts many noise contours in addition to the interesting features. The counter-part of good performance of our approach is that it cannot be applied without a priori knowledge of the signal. But it yields significant results for both frequency and amplitude modulated signals in colored noise. Another difficult example, a cavitation signal, is presented in figure 2. The watershed segmentation yields results closer to the interpretation of human experts (the "golden ears").

Interpreting the T-F 2D contours

The original TFR has just been reduced to a limited number of closed contours defining its most pertinent subsets.

Several parameters can directly be derived from these contours, for example: position (time and frequency) of the center of gravity of the subset, duration (i.e. extension along the time axis), bandwidth (i.e. extension along the frequency axis), average power of the time-frequency points inside the contour, orientation with respect to the axes, etc. A review of several classical methods for describing contours can be found in [Marinovic 85] and several applications in [Granlund 72], [Chassery 91]. The description parameters can in turn be used as the input of a decision system based e.g. on expert reasoning or statistical analysis, depending on whether an exhaustive training set of signals is available or not. Interpration of TFR's after a morphological non linear filtering can be found in [Pierson 97].

Limits of the gradient method for segmenting TFRs

Lots of segmentation technics are based on a gradient function. It may be of some interest to study not the influence of the noise, which is known to be significant, but the influence of the signal spectral bandwidth on the gradient function. Without any loss of generality, let us consider the estimate

    2 ˆ   X x  of the periodogram of a stochastic signal       t b t s t x   where    X is its Fourier Transform,   t s a deterministic signal with spectrum     s and   t b a gaussian white noise with variance 2  .     x ˆ is a noncentral chi-square random variable whose mean is            s x E   2 ˆ and variance             s x Var 2 4 2 ˆ 
. Therefore, the gradient function in the frequency direction

           x G ˆ is a
random variable whose mean is the derivative of

      x E ˆ
and second order moment is

      0 2 2 2 ˆ                   G E with                   x x E ˆ.
From these relations, we can deduce the variance of Setting

   G ˆ:           0 2 2 2 ˆ                        s s G Var (1)
    2 A for having A independent of   , we get   2 2 2        e s . Inserting into (1), we obtain     2 2 2 2 ˆ         e G E and                       2 2 2 2 2 2 1 1 ˆ2 2 2 2           e e G Var
.

(2)

The mean maximum is reached for

    
. At this frequency, the mean and the variance of the gradient function are

    2 1 1 ˆ    e G E   and           2 1 2 2 2 1 ˆe G E G Var        . ( 3
)
As a major result, when the spectral bandwidth   increases, the mean maximum varies with   1 and so is rapidly lowering. Furthermore, the standard deviation, square root of the variance, is greater than the mean even for high signal to noise ratio. Figure 3-a shows results for four values of   without additive noise whereas figure 3-b shows the fast increase of the variance even for a signal to noise ratio of only 30 dB.

a. without noise b. with additive noise Figure 3 Spectrum of a Gaussian envelope and its discrete derivative for 2 different widths

The variation of the gradient with   1 creates a too strong dependence of this function with the spectral bandwidth of the signal even for high signal to noise ratios. So, the gradient function fails in highlighting wide band patterns. This property considerably limits the use of this type of segmentation for real signals.

Extraction of Subsets from TFRs of Cloud-of-points Type

In this paragraph we consider the particular case of an ARCAP TFR, but a similar methodology can be carried out with TFRs obtained by e.g. extracting peak values from a matrix-type TFR.

Extracting features from the TFR using Kalman Filtering

If the signal is made of one or several narrow-band components, some of the points of the ARCAP TFR are structured so that they form coherent lines (so-called time-frequency "trajectories") representing the main TF components of the signal: pure or modulated frequencies. However, in the context of gliding parametric estimation, the link between the estimated parameters at successive dates is lost during the analysis process. What we propose to do is to link the points corresponding to the same frequency component together in order to extract and interpret the identified time-frequency trajectories.

If the SNR is high and the simultaneous frequencies are not too close to each other, a simple thresholding of the ARCAP TFR followed by a nearest neighbor assignment procedure can be used to link the points together and identify the coherent lines [Leprettre 96] [Leprettre 98].

Modulation Model Particularities Linear      i t t   . 0 Ballistic model of order 1                i i t t t t t t t t t             v v v . v(t) =  constant speed null acceleration Parabolic        i t t t    . 0 2 0 Ballistic model of order 2 v(t) = 2.(t-t 0 ) (t) = 2 constant acceleration Hyperbolic     i t a t   0 1 .                            i i t t t t t t t t t t t t t t t                       v v v + t . . . 2 2
After second-order Mac Laurin development :

v(t) = a 0 .(2at-1) (t) = 2 0 .a 2 Sinusoidal         i t b t    .sin 0 After second-order Mac Laurin development : v(t) = b(cos -.sin.t) (t) = -b.sin

Table 1 Frequency modulations and related ballistic models

If the SNR of the signal is small, the choice of the parameters for finding the neighbor is difficult and thus a more elaborate procedure is needed. We propose to model the frequency modulation law of the searched trajectories.

The problem is thus connected to that of following up the trajectory of a ballistic object, which can be solved using Kalman filtering. Table 1 shows four types of frequency modulations with corresponding ballistic models.

We propose to use two separate Kalman filters in order to take both the frequency variations and the power changes into account. So, the state vector is defined by

    T n g n v n u n X ) ( ), ( ), ( 
with v(n) the first derivative (or speed) and g(n) the second derivative (or acceleration) of u(n), which represents either the estimated frequencies or the estimated powers. Thus, from a Taylor expanding of u(n), the state model of order 2 writes as

                                            ) ( . 0 0 1 ) ( ) ( . 1 2 / 1 6 / 1 . 1 0 0 1 1 0 2 / 1 1 1 1 n e n X n y n n X n X  (5)
The errors (n) with variance Q and e(n) with variance R are uncorrelated white noises representing the errors on the model and on the observations y(n) respectively. Let be   n X f the state vector of the first filter where the first component is one of the estimated frequencies at time n: u f (n) = f(n), then let R f and Q f be the error variances.

Likewise, let   n X P be the state vector of the second filter where u P (n) = P[n,f], the amplitude of the TFR, and so R P and Q P . This parallel modeling of frequencies and amplitudes is possible due to the fact that the variables f and P are independent. The algorithms are initialized with one observed point of the ARCAP TFR with null speed and acceleration. For each filter, the vector   . Then, in the time-frequency space, at time n+1, an observed point is searched for within a given interval defined with the variance (R f + Variance(f)) for the frequency and (R P + Variance(P[n,f])) for the power. Several possible points may be candidates. The nearest point (n+1, f m , P[n+1,f m ]) is assigned to the component according to the minimum of Mahalanobis distance d M [Chui 87] defined by:

n n X / 1 ˆ , prediction of   1  n X given   n X ,
    P f n P Var P f n P f f Var f f d m m m m M ] , 1 [ ]) ] , 1 [ ( ) ( 2 2         (6)
This matched point becomes the observation at time n+1 from which estimation  

1 / 1 ˆ  n n X
is set for each filter and according to the variance parameters Q f , R f , Q P and R P . This provides

f n n u f ) 1 / 1 ( ˆ   and P n n x P ) 1 / 1 ( ˆ   .
If no point is found in the given interval, the current trajectory dies and another trajectory is initiated using a point of the TFR not already assigned to a trajectory.

When this procedure is carried out on the whole TFR, what we get is a set of one-dimensional time-frequency components (the so-called spectral lines). Two types of data are available for each line: a matched trajectory containing only points from the original ARCAP TFR and formed with all (n, f m , P m [n,f m ]) points and a modeled trajectory formed with the output of Kalman filters, the ) , , ( P f n points. If the confidence in the model (defined by Q f and Q P ) is much higher than the confidence in the observed values (defined by R f and R P ), the modeled trajectory is smoother than the matched trajectory. Shorter lines which have only a few points, the number of which must be set according to the characteristics of the signal, are considered as noise and eliminated. Kalman filtering of order 1 is often satisfactory. Orders higher than 2 could as well be considered [Davy 98]. But, even if the signal is highly modulated, a 2 nd order is sufficient. Recursive implementations of Kalman filtering can be found in the literature [Chui 87]. See [Roguet 96] and [Cottereau 00] for specific studies concerning the tracking of ARCAP time-frequency trajectories.

Application on a real signal

Interpreting the 1D spectral lines

The original ARCAP time-frequency representation is reduced to a limited number of matched and/or modeled spectral lines representing only the most pertinent information of the original TFR. As the extracted components are one-dimensional curves, they are easier to handle than the whole TFR. Several parameters with physical significance can be derived from each component: onset moment, duration, mean frequency and power values, etc. Global trends can be evaluated using e.g. interpolation and lowpass filtering. Ruptures inside a component can be detected using e.g. wavelet analysis or prediction models if needed. The trajectories can also be compared to various models (polynomials, spline functions, etc.) derived from physical considerations or to a library of typical features of interest. The parameters derived from the extracted spectral lines sum up the time-frequency characteristics of the signal in a convenient way. They can be used as the input vector of a decision system for classification purposes. An illustration of this can be found in [Leprettre 98] for the avalanche signal recognition of the previous section.

Conclusion

Two methods for extracting pertinent information from TFRs have been presented.

  is a dolphin communication whistle recorded using a 32 kHz sampling frequency. Capon's RTF (figure1a) shows that the interesting features are successive transient signals modulated in both amplitude and frequency. Energetic patterns above 13 kHz are eliminated due to anti-aliasing filtering. A highly-energetic, colored noise is present. A priori knowledge on that signal allows the definition of two criterions. The first one is based on the amplitude. The high amplitude peaks [31.5 dB, 50.5 dB] are the interesting signatures. Few of them arise from the background noise[20 dB, 31.5 dB]. The second criterion characterizes the mean frequency bandwidth of the peaks and is obtained after several adapted Top-Hat transforms applied with a vertical linear structuring element[Pierson 97]. It is in fact a size criterion. For that signal, we obtain a mean bandwitdh of 1570

  Figure 1 Dolphin Communication whistles in a submarine acoustic a-Capon TFR, Nf=256, M=20, L=127 (4 ms), L=64 (2 ms), Fe = 32 KHz b. Signal markers c. Noise markers d. Result of the watershed e. Result of isolevel segmentation at 31.5 dB from the minimal power

  ARCAP trajectory tracking has been applied to the recognition of seismic signals produced by snow avalanches and provided by Meteo-France [Leprettre 96][Leprettre 98]. First-order Kalman filters identified four spectral lines. These are shown superimposed with the ARCAP analysis on figure 4-a and as isolated one-dimensional full-scale curves on figure 4-b. For each extracted time-frequency trajectory a couple of parameters are estimated: extreme frequencies, mean and standard deviation.

Figure 4

 4 Figure 4 Seismic signals produced by snow avalanches a. Superimposed ARCAP analysis and Kalman trajectory tracking b. Extracted Kalman trajectories: frequency and power

  The first one is based on morphological segmentation and is suitable to matrix-type TFRs like. The second one implements a trajectory tracking Kalman filter and is suitable to TFRs of cloud-of-points type obtained after a modeling process such as ARCAP analysis, or after peak extraction from a matrix-type TFR. Examples on real signals have been presented and commented. Morphological segmentation can produce interesting extraction performance even on complex signals (low signal to noise ratio, colored noise, severe non stationarities in time or in frequency). As a priori knowledge is necessary, it is difficult to propose a global strategy for choosing the required parameters. Every application must be well controlled. The tracking of time-frequency trajectories, only suitable for narrow-band signals, provides a good performance with a low complexity. Time-frequency decision is currently fast growing.[Martin 98] reflects the state of the art in the French community. In order to improve the first presented method, we would like to eliminate the drawback produced by the gradient function. A work is in progress with a completely different approach, whose preliminary results are in[Hory 00],[Hory 01].


Vinod Pangracious

Emna Amouri

Zied Marakchi

Habib Mehrez

L B Lb

Umsb

Architecture Level Optimization of 3-Dimensional Tree-based FPGA

Keywords: 3D Integration, Tree-based FPGA, Placement, Partitioning, Routing, Butterfly-fat-tree

We describe a methodology to design and optimize Three-dimensional (3D) Tree-based FPGA by introducing a break-point at particular tree level interconnect to optimize the speed, area, and power consumption. The ability of the design flow to decide a horizontal or vertical network break-point based on design specifications is a defining feature of our design methodology. The vertical partitioning is organized in such a way to balance the placement of logic blocks and switch blocks into multiple tiers while the horizontal partitioning optimizes the interconnect delay by segregating the logic blocks and programmable interconnect resources into multiple tiers to build a 3D stacked Tree-based FPGA. We finally evaluate the effect of Look-Up-Table (LUT) size, cluster size, speed, area and power consumption of the proposed 3D Tree-based FPGA using our home grown experimental flow and show the horizontal partitioned 3D stacked Tree-based FPGA with LUT and cluster size 4 has the best area-delay product to design and manufacture 3D Tree-based FPGA.

Introduction

The modern Field Programmable Gate Arrays (FPGAs) have become a viable alternative to cell-based design technology by providing re-configurable computing platforms with improved performance and higher density. While the re-configurability provides flexibility, FPGA also leads to area and performance overhead in comparison to cell-based application specific integrated circuits (ASICs). With the development of sub-100-nm CMOS technologies, the design and manufacturing cost of cell-based implementation have become exorbitant for most ASICs, making FPGA increasingly popular for prototype designs. However current FPGA architectures cannot meet the speed and area requirements of many ASIC due to their high programming overhead.

To provide the required reconfigurable functionality, FPGA provide a large amount of programmable interconnect resources and it consumes 90% of the total FPGA area (A. Rahman et al., 1990;[START_REF] Lin | Performance Benefits of Monolithically Stacked 3D FPGA[END_REF]. Since die area is one of main factors that determine the manufacturing costs, reducing the silicon footprint of the programmable routing resources can lead to significant improvement in speed, area, power consumption and manufacturing cost to an interconnect dominated FPGAs. Three-dimensional integration (3D) is a promising technology for reducing interconnect length (R. [START_REF] Reif | Fabrication Technologies for Three-Dimensional Integrated Circuits[END_REF]. It involves stacking of multiple silicon dies or wafers interconnected using Through Silicon Vias (TSV). The 3D technology using vertical interconnects (TSVs) (V. Pavlidis et al., 2006) has the potential to reduce the programmable interconnects length by bringing the logic components close together, which leads to significant improvement in functionality, scale of integration, silicon area and speed of integrated circuits provided that the devices are efficiently packed, placed and wired. There are many different 3D integration technologies presented in literature, but the most appealing techniques to date are those involving either low-temperature silicon epitaxy or wafer bonding. In an interconnect dominated FPGA, 3D integration can address problems pertaining to routing congestion, limited I/O connections, low resource utilization, and long wire delays. Recently Xilinx developed a 65nm passive silicon interposer based 2.5D high density 28nm heterogeneous FPGAs (R. [START_REF] Chaware | Assembly Process Integration Challenges and Reliability Assessment of Multiple 28nm FPGAs Assembled on a Large 65nm Passive Interposer[END_REF]. The passive silicon interposer provide large wiring density interconnection, minimize coefficient of thermal expansion (CTE) mismatch between the Cu/low-k die and copper filled TSV interposer, and improve chip performance due to shorter interconnection from chip to the substrate. However this type of design and manufacturing A true 3D integration technology can lead to significant reduction in wire length and interconnect delay by using TSVs (R. [START_REF] Reif | Fabrication Technologies for Three-Dimensional Integrated Circuits[END_REF]. A number of recent publication proposed novel 3D architectures and design methodologies that lead FPGA with better performance than existing planner FP-GAs (A. Rahman et al., 1990;[START_REF] Lin | Performance Benefits of Monolithically Stacked 3D FPGA[END_REF]C. Ababei et al., 2006;[START_REF] Siozios | Architecture Level Exploration of Alternative schmes Targeting 3D FPGAs: A Software Supported Methodology[END_REF]. There are two major types of 3D FPGA architectures found in the literature. The first one is developed by monolithic stacking, whereby the active devices are lithographically built in between metal layers (M. [START_REF] Lin | Performance Benefits of Monolithically Stacked 3D FPGA[END_REF] and the second type is evolved from original 2D structure by extending the 2D switch boxes (SBs) to 3D ones (K. [START_REF] Siozios | Architecture Level Exploration of Alternative schmes Targeting 3D FPGAs: A Software Supported Methodology[END_REF]C. Ababei et al., 2006). So far, there are two design and exploration frameworks targeting 3D FPGA architectures: the three-dimensional place and route (TPR) (C. Ababei et al., 2006) and 3D MEANDER (K. [START_REF] Siozios | Architecture Level Exploration of Alternative schmes Targeting 3D FPGAs: A Software Supported Methodology[END_REF]. In TPR, all SBs are assumed to be 3D-SBs and the number of TSVs is assumed to be unlimited, which is an impractical assumption as far as design and manufacturing of 3D chips is concerned. Meanwhile 3D ME-ANDER is a fully-fledged design framework for 3D FPGAs and it provides the capability to analyze the impact of different deployment strategy for 3D-SBs in multi-tier FPGAs. It proposes various 3D FPGA architectures and design styles in which 2D-SBs and 3D-SBs are intermittently used in certain regular spatial patterns. Nonetheless the number of available TSVs within 3D-SBs is assumed to be fixed and that means the methodology does not investigate the impact of different numbers of TSVs in a 3D-SB. A dynamically re-configurable 3D FPGA is presented in (S. [START_REF] Chiricescu | Design and Analysis of A Dynamically Reconfigurable Three-Dimensional FPGA[END_REF], which consisted of three physical layers: logic blocks along with local interconnects, programmable interconnects layer and memory layer. The performance analysis of a monolithically stacked 3D FPGA using three physical layers presented in (M. [START_REF] Lin | Performance Benefits of Monolithically Stacked 3D FPGA[END_REF].

Motivation And Problem Formulation

According to (K. [START_REF] Siozios | Architecture Level Exploration of Alternative schmes Targeting 3D FPGAs: A Software Supported Methodology[END_REF]C. Ababei et al., 2006) the SBs has been the most area-consuming unit compared to other design elements in 2D FPGAs and this situation is becoming even worse in 3D FPGAs because the TSVs are located on 3D-SBs. Although the design and manufacturing engineers are trying to reduce TSV dimensions, the minimum feature size on the die is also shrinking. Therefore, the TSVs are expected to remain larger than wire dimensions in metal layers within the die (S [START_REF] Gupta | Techniques for Producing 3D ICs with High-Density Interconnect[END_REF]. Moreover it has been reported in [START_REF] Cha | Architectural Exploration of 3D FPGAs Towards A Better Balance Between Area and Delay[END_REF] that the TSV utilization is actually quite low if the 3D-SBs are with full vertical connectivity in use. The experiments carried out in our laboratory and recent publications point out that the utilization of TSVs is actually very low in 3D Mesh-based FPGAs [START_REF] Cha | Architectural Exploration of 3D FPGAs Towards A Better Balance Between Area and Delay[END_REF] with full vertical connectivity, which motivates us to explore new architectures that can be better optimized to achieve higher speed, reduced power consumption, area and to increase logic density. In this paper, we prefer to use a Tree-based multilevel FPGA architecture, because from our experimental and design experience, we believe, due to the multilevel Butterfly Fat-Tree (BFT) based interconnect topology, Tree-based FPGA is a better architecture style to build high density 3D re-configurable systems compared to Mesh-based industrial FPGAs. In a Tree-based FPGA architecture (Z. [START_REF] Marrakchi | FPGA Interconnect Topologies Exploration[END_REF][START_REF] Marrakchi | Hierarchical FPGA clustering based on multilevel partitioning approach to improve routability and reduce power dissipation International Conference on Reconfigurable Computing and FPGAs[END_REF][START_REF] Marrakchi | A new Multilevel Hierarchical MFPGA and its suitable configuration tools[END_REF], the programmable interconnects are arranged in a multilevel network with the switch blocks placed at different tree levels and the Logic Blocks (LBs) are grouped into clusters located at different levels. Due to the multilevel network arrangement, we do not have to deal with 3D SBs in the case of Tree-based FPGA, rather all switch blocks remain as 2D and only the interconnects are partitioned between multi-tiers and interconnected using TSVs.

In a Tree-based FPGA architecture (Z. [START_REF] Marrakchi | FPGA Interconnect Topologies Exploration[END_REF], the Logic Blocks (LBs) are grouped into clusters located at different levels. Each clus- ter contains a switch block to connect local LBs. Figure 1 illustrates a 2 level arity 4 Tree-based FPGA architecture. The switch blocks are divided into Mini Switch Blocks (MSBs). The Tree-based FPGA architecture unifies two unidirectional upward and downward interconnection networks using a BFT based network topology to connect Downward MSBs (DMSBs) and Upward MSBs (UMSBs) to LBs inputs and outputs. Design and implementation of two-dimensional layout for Tree-based FPGA is a challenging task, since the interconnect delay increases exponentially as the tree grows to higher levels (Z. [START_REF] Marrakchi | FPGA Interconnect Topologies Exploration[END_REF]. As illustrated in Figure 2, we propose two innovative 3D stacking methodologies using vertical or horizontal network partitioning to improve density and network delay of 3D Tree-based FPGA.

Figure 2 shows a 3 level, arity 4 Tree-based FPGA architecture with horizontal and vertical break-point. In the case of horizontal partitioning the tree-based programmable interconnect network is horizontally partitioned at a particular tree level called the break-point and interconnected using TSVs to optimize network delay. In this case the logic density and interconnects below the break-point will be placed in active layer 1 and the interconnect networks above the break point will be placed at active layer 0 of the 3D stacked chip. On the other hand, the vertical partitioning, as illustrated in Figure 2, the hardware positions are fixed. The logic units and interconnect networks are placed equally on multiple active layers of the 3D stacked chip. Thus the silicon area and power consumption of the active layers are balanced and design complexity is reduced. The horizontal partitioning method provide higher speed and additional design flexibility to optimize the programmable network delay and inter-layer heat dissipation of the 3D chip.

Summary of Results and Outline of the Paper

In this article we focus on performance optimization of programmable interconnects networks that are placed in multiple active layers of the horizontal or vertically partitioned design methodology to design and manufacture a high-performance 3D Tree-based FPGA. The main contribution of the article as follows. We propose innovative design and exploration methodologies to improve the speed and density of 3D Tree-based FPGA using vertical and horizontal break-points of tree-based programmable interconnect networks. Using Rent-based analytical wire length distribution models, we propose a methodology to optimize total count and area of TSVs and programmable routing resources. Using an extensive sets of benchmarks, we analyze the speed, area, power consumption and the effect of LUT and cluster size of the 3D stacked Tree-based FPGA. Using a comprehensive experimental setup we show that the 3D homogeneous Tree-based FPGA provides 65.13% improvement in speed and reduces 36% interconnect network area compared to 2D Mesh-based planer FPGA. This article is organized as follows. Section 4 describes the 3D Tree-based FPGA experimental and design methodology. Section 5 describes the experimental results. Section 6 presents the impact of LUT and cluster size of Tree-based FPGA architecture on performance. Section 7 explains power optimization methodology of 3D Tree-based FPGA. Section 8 describe 3D Thermal modeling and analysis of Tree-based FPGA architecture and finally section 9 concludes the article.

Experimental Flow

The proposed experimental flow for design and exploration of 3D Treebased FPGA architecture is illustrated in Figure 3. The HDL code generator is designed to generate VHDL code based on a hierarchical design approach that partitions the design into smaller sections, implements them separately and assembles them together at the final design phase. The physical design experiments are performed using the layout generated using ST Micro's 130nm technology node (V. Pangracious et el., 2013). Mentor's circuit simulator Eldo is used to estimate the wire delay and power consumption of switches and interconnection networks at different tree levels.

3D Physical Design Methodology

The physical design process begins with the RTL description of Treebased FPGA generated using VHDL code generator as illustrated in section 4. Figure 4 presents the 3D physical design flow used in the design of 3D Tree-based FPGA. Based on the type of partitioning being used, the design is partitioned into two independent designs (tier 0 and tier 1). In the case of horizontal partitioning, tier 1 contains LUTs and local programmable interconnects from levels 0 to 3 (design2) and tier 0 contains programmable interconnect above the break-point along with IOs (design1) and for vertical partitioning total logic blocks and interconnect are partitioned equally into two designs. We then used cadence design compiler to compile VHDL into structural Verilog for each die. The compiled Verilog is then input into Cadence Encounter to perform semi-automated physical design steps. The design tool augmented to test different 3D stacking methodologies. We used both Face-2-Face (F2F) and Face-2-Back (F2B) stacking methodology using via first TSV process. The insulation material between TSV and silicon is oxide with 1000 routed through TSVs to the back surface of tier 0 and from there, they will be fanned out past the edge of the device to connect to I/O pads on the surface of the 3D FPGA chip, while in F2B stacking, the tier 0 via-first TSVs have their landing pads on Metal 1 and Metal 6. The connection between via-first TSVs are made using local interconnection and vias in between adjacent dies. In the case of F2F stacking wafer thinning is done after bonding, while in F2B, the tier 0 die is thinned down to TSVs first and bonded using the TSV landing pads. These landing pads includes keep-out-zones uniformly located around them to reduce coupling effects on active devices located around it. We used Encounter and Caliber-LVS to perform early analysis on the design before sign-off analysis is undertaken. To perform the DRC/LVS of the two-tier 3D FPGA layout, we used a GDS-merger (c program) tool to merge two independent layout into an integrated chip layout and compare it with the top level schematic by using Calibre-LVS as illustrated in Figure 4. The merger tools interconnects those pins with same names in design1(tier0) and design2 (tier1) and no major change required in the top level schematic files to perform Calibre-LVS.

Floorplaning And Thermal Analysis

The goal is to distribute the BFT based programmable interconnect levels into two active layers in order to minimize the interconnect delay and balance the temperature uniformly across the active layers of the 3D Tree-based FPGA. The multilevel BFT-based programmable interconnect network is divided at a particular level called the break-point level and interface nets are interconnected using TSVs to optimize the network delay at the break-point level and above. The 2-dimensional Tree-based FPGA design is partitioned based on design specification (horizontal or vertical) to form a two-tier 3D Tree-based FPGA. To generate the two-tier Tree-based FPGA floorplan, we used a thermal driven floorplanning tool (K [START_REF] Sankaranarayanan | A case for thermal-aware floorplanning at the microarchitectural level[END_REF] configured with ST micro's 130nm technology node. This tool is configured to optimize wire length and temperature of the block level floorplan of the two-tier Tree-based FPGA chip. The floorplan tool takes a list of functional blocks, areas, aspect ratios, connectivity between the blocks and power consumption of each functional blocks as inputs. For example, in the case of horizontal partitioning, we have created two floorplans: the first floorplan consists of the logic units and local interconnections up to level 3 of the Tree-based FPGA and the second floor plan consists of programmable interconnect levels levels 4, 5, 6. The floorplan tool generates thermal estimations and interconnection wire delay of local and global metal layer.

For this study the communication is realized with Through Silicon Via (TSV) and electrical characterization of TSV is performed using the approach presented in (D M [START_REF] Jang | Development and Evaluation of 3D SiP with Vertically Interconnected Through Silicon Vias (TSV)[END_REF]. One important aspect of thermal-aware floorplanner is the trade-off between temperature and performance. We used the wire delay model associated with floorplanner to optimize the wire length.

However the floorplan solution is always a trade-off between temperature and wire delay of the blocks used in simulation. To manage this trade-off, we have taken steps during design phase to make sure the placement of high power blocks do not lead to hotspots without compromising on design performance. The floorplan tool is augmented to include the flexibility of creating horizontal or vertical break-points in the BFT based interconnect network according to the 3D Tree-based FPGA design specifications.

One of the main concerns in the design and manufacturing of 3D-ICs is heat dissipation (A. [START_REF] Gayasen | Designing a 3-D FPGA: Switch Box Architecture and Thermal Issues[END_REF]. By stacking multiple active layers and increasing logic density, it become more difficult to remove the inter-tier heat. Hotspot power dissipation results in significantly higher temperatures in 3D stacked chips compared to the same power dissipation in single 2D chips. The reason for the increase in temperature is due to the reduced thermal spreading in the thinned dies on the one hand, and to the use of low thermal conductivity adhesives on the other hand. Therefor a detailed thermal analysis at the design stage is required. The floorplan tool uses 3D resistance mesh based thermal model presented in (J. Ayala et al., 2009) to extract the thermal profile of the floorplans of the two-tier 3D Tree-based FPGA. The 3D Thermal resistance mesh based multi-layer thermal model for Tree-based FPGA consider the spatial distribution of signal TSVs to control the heat transfer among different module in the multi-tier chip. The thermal model also consider the impact of TSVs material (Cu,Tungsten or doped Poly-silicon ) while estimating the temperature profile. The effective thermal conductivity of active and passive layers in 3D stacked chip is calculated by equation 1. The k cu and K th are the thermal conductivity of copper and silicon active layer. The heat transfer take place on those locations where Cu TSVs are placed. Using this module, the inter-layer heat transfer and thermal profile of 3D FPGA is modeled and analyzed.

k ef f = k cu .(T SV Area ) + K th .(Level BP Area -T SV Area )
(1)

Partitioning, Placement And Routing

Synthesis consists of translating a circuit description into gate-level representation. As presented in Figure 5, the operation is independent of the architecture. In our flow we use SIS (E. M. [START_REF] Sentovich | A System for Sequential Circuit Synthesis[END_REF] synthesis tool. SIS requires architecture parameters like k, the LUT input number. In our flow we use FlowMap algorithm (J. [START_REF] Cong | On Area/Depth Trade-off in LUT-Based FPGA Technology Mapping[END_REF], which is included in SIS package. As presented in Figure 5, this tool depends only on LUT size and can target any interconnect topology. We use a top-down recursive partitioning and clustering approach. The aim is to reduce external communications and to collect highly connected cells into the same cluster. First, we construct the top level clusters, then each cluster is partitioned into sub-clusters, until the bottom level of the architecture is reached. Then during the placement phase, each cluster is assigned to a random position inside its owner cluster. The partitioning in each level consists of three phases. First we run a multilevel coarsening phase where the size of hypergraph is succeviely decreased using the first choice algorithm (N. [START_REF] Selvakkumaran | Multi-Objective Hypergraph-Partitioning Algorithm for Cut and Maximum Subdomain-Degree Minimization[END_REF]. Then k-way partitioning of the smaller hypergraph in computed such that the balancing constraint is satisfied. After that we run the un-coarsening phase where the partitioning is successively refined using using FM algorithm (C. M. [START_REF] Fiduccia | A Liner-time Heuristic for Improving Network Partitions[END_REF], as it is projected in the larger hypergraphs. The objective of the refinement is to minimize the hyperedge-cut, which is the total number of hyperedges that span multiple partitions. Since the structure of Tree is maintained in our two-tier 3D FPGA, the break-point will not play any role in application partitioning and placement process. However it is used during architecture optimization process. Figure 5 presents the block level representation of Tree-based FPGA architecture exploration platform.

For Tree-based architecture, the netlist obtained in .NET format first partitions the LUTs and I/Os into different clusters in such a way the intercluster communication is minimized. Once the netlist is partitioned into a tree of nested clusters, we attribute randomly to each cluster a position inside its owner. Since the two-tier 3D Tree-based FPGA is stacked with programmable routing resources on top of the logic blocks and interconnected using TSVs, no detailed placement is required. After partitioning and placement is done, placement file is generated, which contains positions of different blocks on the two-tier 3D stacked Tree-based FPGA architecture. This placement file along with the netlist file is then passed to 3D router, which is responsible for routing the netlist. The routing problem consists in assigning the nets that connect placed logic blocks (tier1) to routing resources in the interconnect structure (tier0). The upward interconnect adds extra paths to connect a LB to a destination but eliminates the predictability property. Hence we model the routing resources as a directed graph abstraction G(V;E). The set of vertices V represents the in/out pins of logic blocks and the routing wires in the interconnect structure. An edge between two vertices represents a potential connection between the two vertices. The routing algorithm we implemented is PathFinder (L. [START_REF] Mcmurchie | PathFinder: A Negotiation based Performance Driven Router for FPGAs[END_REF][START_REF] Marrakchi | Hierarchical FPGA clustering based on multilevel partitioning approach to improve routability and reduce power dissipation International Conference on Reconfigurable Computing and FPGAs[END_REF][START_REF] Marrakchi | A new Multilevel Hierarchical MFPGA and its suitable configuration tools[END_REF], which uses an iterative, negotiation-based approach to successfully route all nets in a netlist. During the first routing iteration, nets are freely routed without paying attention to resource sharing. Two terminal nets are routed using Dijkstra's shortest path algorithm (T. Cormen et al , 1990), and multi-terminal nets are decomposed into terminal pairs by the Prim's minimum-spanning tree algorithm (T. Cormen et al , 1990). At the end of an iteration, resources can be congested because multiple nets use them. During subsequent iterations, the cost of using a resource is increased, taking into account the number of nets that share the resource, and the history of congestion on that resource. Thus, nets are made to negotiate for routing resources including those interconnections at the break-point.

With the help of the routing result, the different sub-paths are identified and each edge is annotated with delay of corresponding sub-path. The edges interconnect active layers of the 3D stacked Tree-based FPGA annotate corresponding TSV delay to the pins which the circuit specifies as a connection between inter-tier layers. Through this process a new direct 3D acyclic timing graph of the routed circuit is generated to evaluate the performance 3D Tree-based FPGA. In order to optimize the TSV count and routing resources, a Rent-based wire-length optimization methodology de- veloped using 3D router program. The optimizer first select the break-point level to optimize the TSV count and afterwards randomly chooses other tree levels to optimize routing architecture. Once the optimization is complete, the 3D router will estimate the area and static power consumption of the optimized 3D stacked Tree-based FPGA chip.

Horizontal Partitioning

The location of the horizontal break-point is decided based on optimization of programmable interconnect network delay. The interconnect delay In tier 0, the locations of programmable interconnects levels are rearranged in order to optimize the wire delay at higher levels. Figure 9 shows the metal 6 TSV contact and landing pads on tier 0 and tier 1 dies.

Horizontal Break Point Delay Results

Measured

Vertical Partitioning

The main focus of vertical break-point method is to balance the total silicon area and power consumption of the Tree-based FPGA equally into the active layers of the 3D stacked chip. The total logic density and programmable routing resources are equally partitioned into multiple stacked active layers. The highest level of the programmable Tree network is split vertically and interconnected using TSVs as illustrated in Figure 10. The advantages of vertical methodology compared to horizontal are balanced power consumption and silicon area in all layers of the 3D stacked chip and at same time design complexity is reduced. For the vertical partitioning method, the interconnect delay up to break-point levels is same as the 2D layout, but the largest wire length in Tree-based FPGA, which is the break point level in interconnected using TSVs and the delay has been reduced to TSV delay as illustrated in Figure 11. If we consider speed is most important design constraint, horizontal partitioning methodology is better.

Experimental Methodology

Evaluation of vertical and horizontal partitioning methodology of 3D Tree-based FPGA architecture is performed using the experimental flow described in section 4. To evaluate the performance of the proposed 3D Treebased FPGA architecture, we place and route the largest set of 20 MCNC 5 benchmark circuits, and compare this with the 3D Mesh-based FPGA architecture (K. [START_REF] Siozios | Architecture Level Exploration of Alternative schmes Targeting 3D FPGAs: A Software Supported Methodology[END_REF][START_REF] Siozios | A Novel Framework for Exploring 3-D FPGAs with Heterogeneous Interconnect Fabric[END_REF]. In order to have a detailed critical path delay analysis and architecture optimization, we used both generalized and individual architecture experimentation methodologies.

Generalized Experimental Methodology and Result Analysis

In order to validate the performance of 3D Tree-based FPGA architecture, we have used a generalized fully connected (Rent set to 1) two-tier Tree-based FPGA architecture with 7 levels and arity 4 for each benchmarks circuits. Once the partitioning is over, the individual netlist are placed and routed using the experimental flow presented in Figure 5. The performance analysis of vertical and horizontal break point 3D Tree-based FPGA is reported in Table 1. The respective average speed improvements measured for horizontal and vertically partitioned stacking methodology are 65.13% and 43.52%. The horizontally partitioned 3D stacking methodology provides 1.5 times speed improvement compared to vertical partitioning method. The speed improvement in horizontal partitioning method is due to design optimization and minimization of interconnect wire length at the higher levels tree networks that are placed in tier 0 of the 3D stacked chip as illustrated in Figure 7. In tier 0 we have additional design flexibility to re-order programmable routing resources to optimize wire length. However in the vertical break-point method, the highest tree interconnect wire length is optimized using TSV interconnects and the rest of tree levels only limited optimization possible as illustrated in Figure 11.

The improvement in critical path delay between 3D Tree-based compared to Mesh-based FPGA is presented in figure 12. The multi-layer 3D Treebased FPGA interconnect using TSVs shows an average of 65.13% speed improvement compared to the 2D counterpart. The 3D Mesh-based FPGA reported in (K. [START_REF] Siozios | Architecture Level Exploration of Alternative schmes Targeting 3D FPGAs: A Software Supported Methodology[END_REF][START_REF] Siozios | A Novel Framework for Exploring 3-D FPGAs with Heterogeneous Interconnect Fabric[END_REF] with heterogeneous interconnect fabric using intermittent 2D and 3D switch blocks distribution with the same layout area measured an average speed improvement of 43%. In conclusion the comparison results presented in figure 12 shows horizontally partitioned 3D Tree-based FPGA is 1.5 times faster than 3D Mesh-based FPGA. The design and manufacturing solution presented in (K. [START_REF] Siozios | A Novel Framework for Exploring 3-D FPGAs with Heterogeneous Interconnect Fabric[END_REF] by using same silicon area for both 2D and 3D SBs is not piratical for high density FPGAs. This design style will increase silicon footprint of high density FPGAs, but the 3D multi-tier Tree-based FPGA with horizontal or vertical partitioning is more efficient as well as economical design and manufacturing methodology because in our design we have only 2D switch blocks.

Architecture Optimization and Result Analysis

The main objective of individual experiments is optimize TSV count and programmable routing resources in 3D Tree-based FPGA. Experiments are performed individually for each netlist using the optimization flow presented

Speed Improvement (%) Benchmark (MCNC)

Figure 12:

Comparison between 3D Tree-based FPGA and 3D Mesh-based FPGA(K. [START_REF] Siozios | Architecture Level Exploration of Alternative schmes Targeting 3D FPGAs: A Software Supported Methodology[END_REF] in Figure 13. The architecture optimizer designed as an add-on utility using the router program implemented using the PathFinder algorithm (L. Mc-Murchie et al , 1995;[START_REF] Marrakchi | Hierarchical FPGA clustering based on multilevel partitioning approach to improve routability and reduce power dissipation International Conference on Reconfigurable Computing and FPGAs[END_REF][START_REF] Marrakchi | A new Multilevel Hierarchical MFPGA and its suitable configuration tools[END_REF], which uses an iterative, negotiation-based approach to successfully route all nets in an application netlist. The router program in association with a binary search algorithm, considers the same architecture with different p values at each levels of the two-tier 3D Tree-based FPGA to determine the smallest number of input and output signals at each Tree levels by allowing to route the benchmark circuits. At first, the optimization program considers architecture break point level with different Rent (p) values. The purpose is to find, for all benchmark circuits, the architecture with the fewest necessary TSVs between the break point levels while keeping the programmable interconnect resources placed in tier 0 and 1 intact. The solution provides the spatial distribution and minimum number of vertical interconnects required to route each benchmark in the two-tier Tree-based FPGA. From this solution we extract the minimum possible number and location of TSVs that can removed from the architecture without compromising the performance of the 3D chip. The decision to remove TSVs is taken based on the spatial distribution and p values of all benchmark used in the optimization process. The highest p

The Downward Network Model

As described in Figure 1, the Tree-based FPGA architecture unifies two unidirectional upward and downward interconnection networks using a BFT based network topology to connect Downward MSBs (DMSBs) and Upward MSBs (UMSBs) to LBs inputs and outputs. A cluster situated at level ℓ contains N in (ℓ -1) DMSBs, where N in (ℓ) is the number of inputs of cluster located at level ℓ with k outputs and N in (ℓ)+kNout(ℓ-1)

N in (ℓ-1)
inputs, whereas k is also the cluster arity size. Since DMSBs are full crossbar devices, the total number of switches at level ℓ cluster is k(N in (ℓ) + kN out (ℓ -1)). At each level ℓ, N k ℓ clusters, whereas N is total number Logic Blocks and the total number of interconnects in the downward network is

log k (N ) ℓ=1 k × N × N in (ℓ) + kN out (ℓ -1) k ℓ (3)
Following equation 2, we can simplify the number of outputs of a Logic Block is N out (0) = c out and the number of inputs equal N in (ℓ) = c in .k ℓ.p and N in (ℓ -1) = c out .k (ℓ-1)p and so on. The total interconnects used at each level ℓ can be calculated by equation 4.

N interconnects (down) = N × (k p c in + kc out ) × log k (N ) ℓ=1 k (p-1)(ℓ-1)
(4)

The Upward Network Model

Similar to the downward interconnect network. The upward interconnect network also built using a Butterfly-Fat-Tree network topology. In level ℓ every cluster contains N out (ℓ-1) UMSBs with k inputs and outputs. UMBSs are also full crossbar devices with k 2 × N out (ℓ -1) switches at a level ℓ cluster. There are N k ℓ clusters at each level ℓ, and the total number of upward interconnection block is

log k (N ) ℓ=1 k 2 × N k ℓ × N out (ℓ -1) (5)
N out (0) = c out is the outputs of Logic Block and using equation 2, N out (ℓ -1) = c out .k (ℓ-1)p . The total number of interconnect required for the upward interconnect network is calculated using equation 6

N interconnects (up) = N × k × c out × log k (N ) ℓ=1 k (p-1)(ℓ-1) (6)
The total number interconnects in Tree-based FPGA architecture is

N interconnects (T ree) = N interconnects (down) + N interconnects (up) N interconnects (T ree) = N.(k p c in + 2kc out ) log k (N ) ℓ=1 k (p-1)(ℓ-1) (7)
The total number of interconnects at different levels of the Tree is calculated by substituting p=1 in the equation 7, where N is the total number of logic blocks, c in and c out are the number of inputs and outputs of logic blocks, k is the arity, and p and ℓ are the Rent's parameter and tree interconnect level. However in normal cases the value of p ranges from 0.3 to 0.8.

At first, the optimization program considers architecture break point level with different Rent (p) values. The purpose is to find, for all benchmark circuits, the architecture with the fewest necessary TSVs between the break point levels. As described in (Z. [START_REF] Marrakchi | FPGA Interconnect Topologies Exploration[END_REF], in a Tree-based FPGA the reduction in number of interconnects at level ℓ impacts the number of interconnects at level ℓ+1, since the number of DMSBs/UMSBs at level ℓ+1 is equal to the number of inputs/outputs at level ℓ. Using equation 2 and 7, the Rent's value and optimized TSV count and interconnect requirements are calculated for each iteration to optimize break point levels. Once the break-point optimization is completed, the optimizer randomly chooses other tree levels above or below the break-point to optimize the routing resources. Table 2 presents the TSV count optimization results of horizontal partitioning method. A minimum possible reduction of 35% TSVs and an average speed degradation of 4.44% are recorded in these experiments. A similar experiment with 3D Mesh-based FPGA (K. [START_REF] Siozios | Architecture Level Exploration of Alternative schmes Targeting 3D FPGAs: A Software Supported Methodology[END_REF] with 40% reduction of TSV resulted in speed degradation of 11.5% as illustrated in Table 2, which indicates the impact of TSV and routing resources optimization on speed is minimized in 3D Tree-based FPGA compared to 3D Mash-based FPGA.

Table 3 presents the results from TSV and architecture optimization experiments on each interconnect level of the Tree-based 3D FPGA. A minimum reduction of 35% and 38% TSVs are recorded for horizontal and vertical which makes 3D stacked Tree-based FPGA a cost effective solution.

LUT And Cluster size Effect on Performance

In this section we evaluate the impact of LUT and cluster size on performance and power consumption of two-tier 3D Tree-based FPGA. Figure 14 presents the effect of increasing LUT (lookup table) size from 3 to 7 with cluster size fixed to 4 using horizontal and vertical break-point stacking on critical path delay of 3D Tree-based FPGA. As the LUT size increases, the area of chip and switch delay increases. The critical path delay analysis experiments consider the impact of increased switch delay, number of interconnects and TSVs as LUT size increases. The results shows that, LUT size equal 4 has the best area-delay product as illustrated in Figure 14. Even though the critical path delay improves as LUTs size increases as shown in Figure 14 creases due to localization of routing resources and increased switch delay.

Figure 15 presents the effect of increasing cluster size from 4 to 7 with LUT size fixed to 4. As cluster size increases the logic density and switch size increases, which forces the mapped application to use more local routing resources in the tree levels close to logic blocks than routing resources at higher tree levels in a timing driven routing procedure. This makes the critical delay shorter as cluster size increases. By varying the break-point location, the critical path delay of 3D Tree-based FPGA can be optimized for the horizontal partitioning method, however this process makes the architecture more application-specific. Our area and critical path delay analysis against various LUT and cluster size analysis reveals cluster and LUT size equal to 4 is better in terms of speed, power and silicon area to design and manufacture a genera-purpose high density and high speed 3D Tree-based FPGA systems.

Power Optimization

The power optimization of two-tier 3D stacked Tree-based FPGA is achieved through the minimization of TSV count and programmable routing resources. The optimized routing resources and TSV count are listed in Table 3. In Mesh-based industrial 3D FPGA, the same power is used for individual blocks in multiple tiers of 3D chip. This doubles the total FPGA power for twotier Mesh-based FPGA and this leads to pessimistic prediction of inter-layer temperature. While for Tree-based 3D FPGA, the power consumption of the dies in each tier is balanced through the optimization process of routing resources and TSV count. Figure 16 shows the interconnect power at different levels of the 3D Tree-based FPGA. The Rent parameter based architecture optimization shows 35.13% reduction in total power consumption of 7 level Tree-based 3D interconnect network. This is very promising for FPGA architecture in terms of silicon area, since FPGA is an interconnect-dominated architecture and it is impossible to manufacture it with huge number of TSV and switches. Figure 17 presents the effect of LUT and cluster size on estimation of power consumption. The power consumption increased exponentially as LUT and cluster size increase due to exponential growth of switch size as the tree grows to higher levels. Considering the power consumption and performance results, LUT and cluster size equal 4 is the best architecture for manufacturing 3D FPGA. Nonetheless higher LUT and cluster size can be used where performance is considered to be the major design criterion.

3D Thermal Optimization

One of the major issues to mainstream acceptance of 3D ICs is the thermal problem. The heat coupling among high power devices in the 3D stack creates several hotspots and increases the background temperature significantly. Thermal issues in FPGAs are relatively unexplored. Some researchers have proposed the use of distributed sensors for monitoring temperatures in FP-GAs (S. [START_REF] Velusamy | Monitoring temperature in FPGA based SoCs[END_REF][START_REF] Lopez-Buedo | Dynamically inserting, operating, and eliminating thermal sensors of FPGA-based systems[END_REF]. The management of inter-layer heat is growing in FPGAs. Recent articles on thermal management in 2.5D and 3D FPGAs from leading manufactures clearly indicate the importance of thermal issues in FPGA design (A. Rehman et al , 2006(A. Rehman et al , , 2012)). Our 3D thermal model consider the impact of spatial distribution of signal TSV and power delivery network TSVs to compute the thermal profile of the 3D Tree-based FPGA chip (J. Ayala et al., 2009). Figure 18 presents the two-tier floorplan and TSV distribution styles used in the design and simulation 3D Tree-based FPGA. The floorplan (a) shows tier 1 design with clusters placed along with local interconnects. The high temperature spots are the locations where more than one cluster connects with interconnect level 3, which connect the inputs and outputs to tier 1 layout design. The heat transfer take place through copper TSVs (assumed in 3D thermal model) from tier 0 to tier 1.

The inter-layer temperature is optimized by considering area and spatial distribution of TSVs and power delivery networks (PDNs). The TSVs and PDNs are effectively used as a 3D thermal net with help vias in metal layers to

Tree-based FPGA blocks sections

Temperature (K)

Figure 19: Measured inter-layer temperature results from 2 tier 3D Tree-based FPGA transfer heat from tier 1 to tier 0 layer. The 3D thermal model considers the impact of via fill material based the type of technology used to manufacture TSVs, like via-first, via-middle or via-last process. While estimating the temperature profile, the 3D thermal model compute the effective thermal conductivity of active and passive layers based on TSV and silicon area in 3D stacked chip. Since the TSVs always pass through the silicon substrate, to calculated the effective thermal conductivity, we use equation 1. The viafirst process use tungsten, while via-middle process use doped poly-silicon and via-last process use copper for via fill and SiO 2 for isolation. Figure 19 shows the temperature at different Tree levels in 2-tier 3D Tree-based FPGA. The measured peak temperature of 2D Tree-based FPGA is 351K and average temperature is 346K. With our localized rearrangement of interconnects and switch blocks along with TSV area, the peak and average temperature are optimized at 355K and 351K respectively for 3D FPGA.

Conclusion and Future work

An efficient design and exploration methodology for 3D Tree-based FPGA presented. The horizontal and vertical break-point design methodology based on design specification is a defining feature of our design flow. A timely architecture and TSV count optimization methodology have been introduced and a reduction of 36% in overall interconnect area observed. The maximum TSV count limited to 65% in horizontal and 62% in vertical break-point cases. The experimental analysis shows the horizontal break-point method is better for high speed applications. The impact of speed and power consumption on different LUT and cluster size is also presented. Therefor we believe that all the design and architecture styles presented in this paper can serve as a robust foundation for the design and manufacturing of even more practical 3D re-configurable systems based on Tree-based FPGA architectures.

One future direction we propose, is to implement two-tier 3D Tree-based FPGA using monolithic stacking. This approach will further reduce the wire length and thereby improve performance. Since the two-tier design is done in such a way to stack almost 80% of the the programming overhead (tier 0) of Tree-based FPGA on top of logic blocks (tier 1) and interconnected using TSVs. In the case of monolithic stacking the interconnect layers between programming overhead and logic blocks will be implemented in a state-ofthe-art CMOS technology. This design and implementation methodology provide additional flexibility to improve logic density, speed and reduce power consumption and silicon area. However the main challenge in this approach is to balance the density of TSVs to that of the via density in the CMOS technology used to implement Logic and interconnect layers.

Figure 1 :

 1 Figure 1: A two-level Tree-based Multilevel FPGA interconnect with Upward and Downward BFT based interconnection network topology

Figure 2 :

 2 Figure 2: A three-level Tree-based FPGA interconnect network break point representation: Horizontal break-point: blue dotted line, Vertical break-point: red dotted line

Figure 3 :

 3 Figure 3: An integrated design and evaluation software flow for 3D Tree-based FPGA: VHDL generation, physical design, thermal model along with placement and routing

Figure 4 :

 4 Figure 4: 3D physical design methodology developed to implement multi-tier 3D Treebased FPGA using 2D CAD tools

Figure 5 :

 5 Figure 5: Architecture exploration software flow developed to evaluate the performance of 3D Tree-based FPGA

Figure 6 :

 6 Figure 6: 3D stacked Tree-based FPGA with horizontal break point between level 3 and 4 of the 7 levels FPGA architecture. The red dotted line indicate the horizontal break-point.

Figure 8 :Figure 9 :

 89 Figure 8: Horizontal break-point interconnect delay estimation of 7 level Tree-based FPGA architecture Design 1 Tier 0 Design 2 Tier 1

Figure 10 :

 10 Figure 10: Representation of 3D stacked Tree-based FPGA with vertical break point

Figure 11 :

 11 Figure 11: Vertical break-point interconnect delay estimation of 7 level Tree-based FPGA architecture

Figure 14 :

 14 Figure 14: Impact of LUT size on performance with cluster size fixed to 4

Figure 15 :

 15 Figure 15: Impact of Cluster size on performance with LUT size fixed to 4

Figure 16 :Figure 18 :

 1618 Figure 16: Power consumption analysis of 3D Tree-based programmable interconnect network

Circuit Netlist Synthesis Thermal Profile Analysis description Architecture Tree-based FPGA HDL Generation Physical Design 130nm ST Micro Layout Parameter Extraction Timing Characterization timing chracterization Tree level interconnect (Hierarchical Design) Thermal driven Floorplan (Mentor's Eldo, Circuit Analysis) Timing Analysis Area & Power Estimation Bitstream generation Floorplan Development 3D Tree-based FPGA Routing Generalized Routing Solution Horizontal/Vertical Network Clustering, Partitioning and Placement

Table 1 :

 1 3D Tree-based FPGA Performance Analysis

		Tree Levels=7, Arity=4, Arch=4x4x4x4x4x4x4
		Critical Path Performance (nS)	Performance Gain(%)
	Name	Tree-based Vertical Horizontal 2D Vs 3D 2D Vs 3D
	MCNC	2D (ns)	3D (ns)	3D (ns)	Verti (%)	Hori (%)
	alu4	59.91	41.73	25.81	30.33	56.91
	apex2	80.41	45.18	30.92	43.81	65.54
	apex4	76.42	46.61	31.83	38.99	58.34
	bigkey	79.1	27.60	20.19	65.11	74.48
	clma	198.6	90.33	59.48	54.38	69.96
	des	90.8	40.36	28.83	55.55	68.25
	diffeq	62.6	48.46	26.66	22.59	57.41
	dsip	61.9	28.55	19.78	53.88	68.05
	elliptic	107.1	83.73	42.76	21.75	60.02
	ex1010	143.1	74.85	45.42	47.69	68.26
	ex5p	168.2	64.71	41.43	61.53	75.37
	frisc	129.6	82.28	42.82	36.51	66.96
	misex3	67.4	41.38	24.94	38.61	63.00
	pdc	143.9	69.04	45.86	52.02	68.13
	s298	130.81	81.54	45.81	37.67	64.98
	s38417	75.46	43.38	30.69	42.78	59.33
	s38584	118	69.54	40.51	41.07	65.67
	seq	64.58	42.91	24.59	33.56	61.92
	spla	109.54	58.57	38.29	46.26	65.04
	tseng	131.1	70.47	45.51	46.25	65.07
	Average	104.88	57.37	35.47	43.52	65.13

Table 2 :

 2 3D Tree-based FPGA with 7 level and Arity 4: TSV count Optimization Results

			Tree Levels=7, Arity=4, Arch=4x4x4x4x4x4x4
		Tree-based FPGA	Tree	Mesh
	Circuits Optimized 3D TSV 35% TSV Reduction 40% TSV Reduction
	MCNC Rent's "p" Gain(%) Speed degradation%	Speed degrade%
	alu4	0.47	53	4.3	2.34
	apex2	0.51	49	5.8	11
	apex4	0.61	39	1.1	10
	bigkey	0.60	40	2.8	4.1
	clma	0.58	42	4.8	25
	des	0.56	44	4.1	8
	diffeq	0.64	36	4.5	-14
	dsip	0.65	35	4.1	4
	elliptic	0.62	38	3.4	34
	ex1010	0.55	45	3.5	5
	ex5p	0.58	42	5.1	12
	frisc	0.62	38	5.4	28
	misex3	0.64	36	5.2	-8
	pdc	0.59	41	3.8	10
	s298	0.55	45	5.8	19
	s38417	0.64	36	5.1	8
	s38584	0.62	38	4.5	9
	seq	0.61	39	5.5	8
	spla	0.58	42	5.2	6
	tseng	0.63	37	4.8	7
	average			4.44	11.5
			Maximum Interconnect Requirement, p=0.65
			Minimum possible TSV reduction=35%
	break-point. An average speed degradation of 4.44% and 3.2% is recorded in
	horizontal and vertical break-point. The optimized silicon area for individ-
	ual interconnect levels are reported in Table 3. Using our optimization flow,
	overall interconnect area of the 3D Tree-based FPGA is reduced by 36%,

Table 3 :

 3 Architecture Optimization Results

	Tree Levels=7	Arity=4, Arch=4x4x4x4x4x4x4
	Tree-based Architecture	3D Chip	Optimized Optimized
	Levels	Active Layer Rent 'p'	Area µm 2
	Logic Blocks	Layer 1	-	93635273
	Switch Level 0	Layer 1	0.67	2412
	Switch Level 1	Layer 1	0.54	10800
	Switch Level 2	Layer 1	0.66	37496
	Switch Level 3	Layer 1	0.65	232128
	BreakP oint Horizontal	Horizontal Break Point Level 3 p V ertical =0.66
	Level 3 to 4	TSV Area=40192µm 2
	Switch-blocks Tree-Level 4	Layer 2	0.67	6072770
	Switch Level 5	Layer 2	0.66	45553499
	Switch Level 6	Layer 2	0.62	42139683
	BreakP oint V ertical	Vertical Break Point Level 6 p Horizontal =0.65
	Level 6	TSV Area=61091µm 2
	Speed Degradation	Vertical=3.2%, Horizontal=4.7%

http://er.cs.ucla.edu/benchmarks/ibm-place.

DMSB DMSB DMSB DMSB OUT UMSB UMSB UMSB DMSB DMSB DMSB DMSB DMSB UMSB UMSB UMSB

of Tree-based programmable interconnects increases exponentially (Z. [START_REF] Marrakchi | FPGA Interconnect Topologies Exploration[END_REF]V. Pangracious et el., 2013) as the tree grows to higher levels. Figure 6 shows the 3D layout representation of Tree-based FPGA (V. Pangracious et el., 2013). In the case of horizontal partitioning method the LBs and local interconnects belong to levels below the break-point are placed in tier 1 and programmable interconnect resources at tree levels above break point are placed in tier 0 of the 3D stacked two-tier chip as illustrated in Figure 7. This will enable us to increase the logic density of the chip, since the logic density is completely segregated and placed in tier 1 and this design model provides additional flexibility in optimizing the interconnect delay and modeling inter-layer heat dissipation.

The setup used for wire length estimation and delay measurement using Mentor's circuit simulator Eldo is reported in (V. Pangracious et el., 2013). Figure 8 shows the interconnect delays measured using 2D and 3D layouts. We used six metal 130nm process provided by ST Microelectronics that is modified to include TSVs specification. The delay measurement experiments used TSV size of 4µm diameter and a minimum pitch of 8µm (ITRS., value obtained from all benchmarks at each levels will be set as the architecture Rent. To make 3D Tree-based FPGA more efficient in terms of design and manufacturing, it is essential to minimize the TSV count because TSV consumes more silicon area than horizontal interconnects (M. Pathak et el., 2010). After completing the break-point optimization, we use the Rent's parameter (Z. [START_REF] Marrakchi | FPGA Interconnect Topologies Exploration[END_REF] to optimize the programmable routing resources that are placed in tier 0 and 1 using random approach, in which the interconnect levels are selected randomly and modifly its inputs and outputs signals depending on the previous result obtained at the same level. The Rent's parameter p defined for a Tree-based architecture is illustrated in equation 2. The Tree level is represented as ℓ and k is the cluster arity, c is the number of in/out pins of an LB and IO is the number of in/out pins of a cluster located at level ℓ. The optimization of upward and downward networks based on Rent's parameter is done as follows.

IO(ℓ) = c.k ℓ.p

(2)