Renan Netto
email: renan.netto@posgrad.ufsc.br

Sheiny Fabre
email: sheiny.fabre@posgrad.ufsc.br

Tiago Augusto Fontana
email: tiago.fontana@posgrad.ufsc.br

Vinicius Livramento

Laércio Pilla

José Luís Güntzel

How Deep Learning Can Drive Physical Synthesis Towards More Predictable Legalization

Keywords: Physical synthesis, placement, legalization, machine learning

Machine learning has been used to improve the predictability of different physical design problems, such as timing, clock tree synthesis and routing, but not for legalization. Predicting the outcome of legalization can be helpful to guide incremental placement and circuit partitioning, speeding up those algorithms. In this work we extract histograms of features and snapshots of the circuit from several regions in a way that the model can be trained independently from region size. Then, we evaluate how traditional and convolutional deep learning models use this set of features to predict the quality of a legalization algorithm without having to executing it. When evaluating the models with holdout cross validation, the best model achieves an accuracy of 80% and an F-score of at least 0.7. Finally, we used the best model to prune partitions with large displacement in a circuit partitioning strategy. Experimental results in circuits (with up to millions of cells) showed that the pruning strategy improved the maximum displacement of the legalized solution by 5% to 94%. In addition, using the machine learning model avoided from 22% to 99% of the calls to the legalization algorithm, which speeds up the pruning process by up to 3×.

INTRODUCTION

The high flexibility provided by machine learning (ML) models allows their use to predict the outcome of physical design algorithms. They have been employed so far to help choose between different clock tree synthesis algorithms [START_REF] Kahng | High-dimensional metamodeling for prediction of clock tree synthesis outcomes[END_REF], to fix miscorrelations between different timing engines [START_REF] Han | A deep learning methodology to proliferate golden signoff timing[END_REF], and to identify detailed routing violations during the placement stage [START_REF] Chan | Routability optimization for industrial designs at sub-14nm process nodes using machine learning[END_REF][START_REF] Tabrizi | A machine learning framework to identify detailed routing short violations from a placed netlist[END_REF][START_REF] Zhou | An accurate detailed routing routability prediction model in placement[END_REF]. The benefits of ML models come from their ability to improve the quality of physical design algorithms by predicting information that would otherwise be too costly to evaluate during execution.

Machine learning techniques have yet to be employed to help predict the outcome of legalization algorithms. As technology nodes advance, new challenges affect modern legalization algorithms. Some of these challenges include pin accessibility, usage of multi-row cell libraries, complex design rules, physical floorplan complexity, as well as tight performance and power constraints. In addition, modern legalization algorithms have to keep a low circuit displacement to avoid degrading the solution of upstream steps.

The prediction of the outcome of legalization algorithms by ML techniques has multiple applications: [START_REF]Ophidian: an open source library for physical design research and teaching[END_REF] choosing, among multiple legalization algorithms, the one that will result in the lowest displacement for a given legalization region, similar to what has been done for clock tree synthesis [START_REF] Kahng | High-dimensional metamodeling for prediction of clock tree synthesis outcomes[END_REF]; [START_REF] Chan | Routability optimization for industrial designs at sub-14nm process nodes using machine learning[END_REF] guiding an incremental placement technique. The ML models could predict which cell movements result in the greatest improvement on different metrics, without requiring the execution of the legalization algorithm itself;

(3) guiding a circuit partitioning strategy. Circuit partitioning can be used to decompose the circuit in smaller disjoint parts, which can reduce the execution time of legalization algorithms by more than one order of magnitude. However, it can also degrade some quality metrics since it reduces the solution space available to the legalization algorithm.

In this work we explore mainly option (3) by integrating the proposed machine learning model into a circuit partitioning strategy to avoid partitions that result in large displacement. Furthermore, we partially explore option [START_REF] Chan | Routability optimization for industrial designs at sub-14nm process nodes using machine learning[END_REF], because the proposed model can be used to predict when some optimizations will largely degrade the solution obtained by upstream steps. We do so by training different ML models to detect when the maximum displacement of a given partition exceeds a specified threshold. Then, we select the model with the best results to be integrated in the partitioning strategy, acting as a pruning mechanism. The main contributions of this paper are:

• We propose a feature extraction strategy for training machine learning models using the information of circuit partitions as input. This set of features is independent of the partition size. • To the best of our knowledge, this is the first work to use machine learning models to help a legalization algorithm. We evaluate different ML models in order to select the best one for this problem (which achieved an accuracy of 80% and an F-score ≥0.7). • We employed the best ML model as a pruning mechanism for a circuit partitioning strategy. Results using circuits from both ICCAD 2017 and ICCAD 2015 CAD Contests show that the pruning strategy reduced the maximum displacement of those circuits by up to 94%, and the use of ML accelerated the pruning by up to 3×.

The remaining sections are organized as follows. Section 2 displays the related work on ML models used for physical design, and multi-row legalization. Sections 3 and 4 present the proposed ML methodology and its integration into a legalization algorithm.

Finally, Section 5 shows the experimental results and Section 6 provides concluding remarks.

RELATED WORK

Machine learning techniques have been used to solve different physical design problems. The work from [START_REF] Kahng | High-dimensional metamodeling for prediction of clock tree synthesis outcomes[END_REF] trains a regression model to predict the outcome of different clock tree synthesis engines. The authors extract features from architectural, floorplanning and design parameters. In order to handle a large number of linearly correlated parameters, they separate the features in two models, which are trained separately and combined using linear regression. Another application is predicting the outcome of golden signoff timing engines [START_REF] Han | A deep learning methodology to proliferate golden signoff timing[END_REF], where the authors propose a regression model to correct miscorrelations between two commercial signoff tools. For that, they extract multiple features concerning capacitance, resistance and delay of cells and wires.

Recently, machine learning techniques have been used to predict the violation of routability constraints in a placed netlist. For example, the work from [START_REF] Zhou | An accurate detailed routing routability prediction model in placement[END_REF] extracts features regarding pin distribution, routing blockage, global routes and local nets in order to predict the number of DRC violations in a placed area. The work from [START_REF] Chan | Routability optimization for industrial designs at sub-14nm process nodes using machine learning[END_REF] improves this idea by predicting the actual locations of the DRC violations, using a different set of features. Finally, the work from [START_REF] Tabrizi | A machine learning framework to identify detailed routing short violations from a placed netlist[END_REF] focuses on predicting only the existence of detailed routing short violations, so that this information can be used in a detailed placement flow, for example. Although different works make use of machine learning techniques, none of them aim to predict the quality of legalization algorithms, which is the focus of this work. Since legalization is performed not only after the global placement, but also after other placement optimization techniques, improving the legalization solution consequently improves the quality of those optimizations.

Several recent works have been proposed to legalize circuits from advanced technology nodes, which contain multi-row cells. For example, the works from [START_REF] Chow | Legalization algorithm for multiple-row height standard cell design[END_REF] and [START_REF] Wang | An effective legalization algorithm for mixed-cell-height standard cells[END_REF] propose algorithms that legalize cells one at a time. Their algorithms enumerate a set of valid insertion points for each cell and place each in the location that minimizes circuit displacement. While the algorithm from [START_REF] Chow | Legalization algorithm for multiple-row height standard cell design[END_REF] uses a greedy heuristic, the algorithm from [START_REF] Wang | An effective legalization algorithm for mixed-cell-height standard cells[END_REF] adapts the Abacus legalization algorithm [START_REF] Spindler | Abacus: fast legalization of standard cell circuits with minimal movement[END_REF] that uses dynamic programming.

Instead of handling each cell at a time, the works from [START_REF] Hung | Mixed-cell-height standard cell placement legalization[END_REF] and [START_REF] Chen | Toward optimal legalization for mixed-cell-height circuit designs[END_REF] propose algorithms that simultaneously legalize multiple cells. The authors of [START_REF] Hung | Mixed-cell-height standard cell placement legalization[END_REF] propose an Integer Linear Programming (ILP) model to solve the multi-row legalization problem. Due to the high complexity of the ILP model, they divide the circuit into bins, solving the problem for multiple bins in parallel. Such strategy leads to better results, but at the cost of longer run times. The authors of [START_REF] Chen | Toward optimal legalization for mixed-cell-height circuit designs[END_REF], by their turn, relax some constraints of the problem in order to model it as a Linear Complementarity Problem. This way, they can still achieve better results than the previous works, but with a more reasonable run time. Finally, the work of [START_REF] Li | Routability-driven and fence-aware legalization for mixed-cell-height circuits[END_REF] improves over [START_REF] Chow | Legalization algorithm for multiple-row height standard cell design[END_REF] and considers additional metrics for legalization problem, such as routability constraints.

A machine learning model that predicts the outcome of such legalization algorithms can be used to guide incremental optimization techniques or partitioning strategies. For example, the work of [START_REF] Fabre | Enhancing multi-threaded legalization through kd tree circuit partitioning[END_REF] proposes a circuit partitioning strategy to speed up legalization by executing the legalization algorithm in smaller regions of the circuit. This way, the authors sped up the legalization, but at the cost of maximum displacement degradation, since the partitioning reduces the solution space of the legalization algorithm. Therefore, in this work we also integrate the proposed machine learning model to this partitioning strategy, so that the model guides this process to avoid partitions with large displacement.

MACHINE LEARNING METHODOLOGY

We model the legalization outcome prediction as a binary classification problem. Given a legalization algorithm L, a partition of cells p i , and a displacement threshold ∆, the output of the ML model is a binary variable y ∈ {0, 1}, indicating whether L legalizes the cells of p i without any cell displacement exceeding ∆1 .

In this work, instead of using L and ∆ as inputs of the ML model, we train models for a specific combination of L and ∆. As consequence, the model receives as input the rectangular region (given by R(p i )) and cells of a partition (given by C(p i )), and must predict if the legalization algorithm L used to train the model is able to legalize this partition under a maximum displacement threshold of ∆. In order to do so, we must provide a large number of samples to train the ML model, so that it can identify which patterns lead to a partition with a large displacement.

Training data generation

Algorithm 1 shows how we generate the data for training and validation of the ML model. Given a set of cells C = {c 1 , c 2 , ..., c n-1 , c n }, a legalization algorithm L and the rectangular area of the circuit R = (X l ef t , X r iдht , Y top , Y bot tom ), the algorithm aims to generate data from partitions of different sizes. The first step consists in defining the number of samples that will be generated for each partition size (line 1). By generating the same number of samples for each size (1024 in this work), we avoid having the ML model become biased to a specific partition size. In addition, increasing the number of samples acts as a data augmentation strategy, which generates more samples from the same circuit and helps avoiding overfitting.

In order to generate the circuit partitions, we used the strategy from [START_REF] Fabre | Enhancing multi-threaded legalization through kd tree circuit partitioning[END_REF], which partitions the circuit using a k-d tree data structure, where each leaf node represents a partition. The strategy receives as input a desired height for the k-d tree and generates 2 heiдht partitions. Therefore, Algorithm 1 iterates over different values for the tree height (line 3), and the necessary number of iterations to generate the desired number of samples is calculated in line 4. We limit the maximum height of the k-d tree to 9 because, as the height increases, the partitions become smaller. A height higher than 9 would result in partitions with less than a few hundred of cells, which would be too small.

For each iteration, a new circuit partitioning is generated (line 7). To ensure that the partitions are different from each other, we apply a vector of random movements to the cells in C (line 6). The MOV E_CELLS function in Algorithm 2 is responsible for applying Algorithm 2: MOVE_CELLS(C, R)

P ← CIRCUIT_PARTITIONING(C, heiдht ); 8 foreach p i ∈ P do 9 Λ, r esul t ← L(C(p i ), R(p i )); 10 F ← F ∪ GET_FEATURES(C (p i ), R(p i ), Λ, r esul t , ∆);
1 foreach c i ∈ C do 2 rx ← RAN DO M (-10000, 10000); 3 ry ← RAN DO M (-10000, 10000); 4 x (c i ) ← x ′ (c i ) + rx ; 5 y(c i ) ← y ′ (c i ) + ry ; 6 x (c i ) ← min(X r iдht -w (c i ), max (X l e f t , x (c i ))); 7 y(c i ) ← min(Yt op -h(c i ), max (Y bot t om , y(c i ))); 8 end
this movement. For each cell, two random variables r x , r y ∈ Z are generated representing the cell movement on x and y coordinates, respectively. We generate them using a uniform integer distribution in the range [-10000, 10000] to ensure that the movement is large enough to generate significantly different placements2 . After moving the cells, we make sure that they lie within the circuit boundaries R (lines 6-7). Observe that the MOV E_CELLS function is called before partitioning the circuit, so the amount of movement is not dependent of the partition size.

After generating the set of partitions P, Algorithm 1 legalizes each partition (lines [START_REF] He | Deep residual learning for image recognition[END_REF][START_REF] Howard | fast.ai -Making neural networks uncool again[END_REF][START_REF] Hung | Mixed-cell-height standard cell placement legalization[END_REF][START_REF] Kahng | High-dimensional metamodeling for prediction of clock tree synthesis outcomes[END_REF]. Observe that it legalizes only the cells in C(p i ) inside the partition and the legalization area is limited to the partition area R(p i ). In addition, the legalization function from line 9 does not actually move the cells, it only finds legal locations for the cells and returns those locations (denoted by Λ). It also returns a boolean variable indicating if the legalization was successful or not (denoted by result), as the legalization may fail for a given partition. Observe that the proposed ML methodology is independent from a specific legalization algorithm, as long as the algorithm may be executed for a subset of the circuit cells and for a subregion of the circuit area. For this reason, we do not present the pseudocode of the legalization algorithm, but we used an adaptation of the Abacus legalization algorithm from [START_REF] Spindler | Abacus: fast legalization of standard cell circuits with minimal movement[END_REF] to handle multi-row cells.

Feature selection

Given the legalization result and legal locations, the next step is obtaining the features for this partition. In the end, when all features are collected, the data is saved in an output file in line 14. In this work we evaluate traditional and convolutional neural network models, so we need features for both of them. For convolutional models, the input is simply a snapshot image of the partition. We used different colors to distinguish between movable and fixed cells.

Movable cells are represented by shades of the same color. This way, the model can identify overlaps since they are represented by the combined colors of multiple cells. On the other hand, for the traditional models we need to select an appropriate set of features. Partitions become hard to legalize with low displacement when they have a high density of cells, or when they have many cell overlaps. Therefore, we selected the features presented in Table 1 for our ML methodology. The first two features aim to represent global information of the partition density. Since partitions with multi-row cells are harder to legalize, we measure not only the cell density, but also the area occupied by cells of each height. However, just the global information is not enough to identify partitions that are hard to legalize, since some circuit rows may be more crowded than others. The third feature aims to represent this information by means of an histogram of the area occupied by cells on each partition subrow. A subrow is a row segment that does not overlap with any macroblocks and/or fixed cells. Finally, a subrow may be overcrowded but with few cell overlaps, which makes it easier to legalize. Therefore, the last feature measures the area occupied by overlaps on each subrow, so that the ML model can correlate this information to the result.

GET_FEATURES(C(p i ), R(p i ), Λ, result, ∆) 1 A f ← 0; Am ← 0; Ar ← w (p i ) × h(p i ); A h ← []; 2 δmax ← -∞; 3 foreach c i ∈ C(p i ) do 4 if f ix ed (c i ) then 5 box ← int er sect ion(c i , R(p i )); 6 A f ← A f + w (box ) × h(box ); 7 else 8 Am ← Am + w (c i ) × h(c i ); 9 A h [h(c i )] ← A h [h(c i )] + w (c i )×h(c i ) Ar ; 10 end 11 δ (c i ) ← |l (c i ) -λ(c i )|; 12 δmax ← max(δmax, δ (c i )); 13 end 14 ∆ ← Am Ar -A f ; 15 y ← δmax ≤ ∆; 16 A ← []; O ← []; Σ ← partition subrows; 17 foreach σ i ∈ Σ do 18 C(σ i ) ← cells intersecting σ i ; 19 a(σ i ) ← 0; o(σ i ) ← 0; 20 foreach c i ∈ C(σ i ) do 21 a(σ i ) ← a(σ i ) + w (c i ); 22 end 23 C ′ ← cells intersecting in C(σ i ); 24 foreach c j ∈ C ′ do 25 o(σ i ) ← o(σ i ) + w (c j ); 26 end 27 A[σ i ] ← a(σ i ) w (σ i ) ; O [σ i ] ← o(σ i ) w (σ
Figure 1 shows by means of an example how the histograms for the last two features are generated for a given partition. Figure 1(a) illustrates a partition with 20 movable cells (blue rectangles), one fixed cell (gray rectangle) and 10 subrows (σ 1 to σ 10 ). Figures 1(b) and (c) show the area and overlap histograms for this partition. For illustration purposes, the histograms contain 5 bins, but we actually used histograms with 20 bins for better precision. Each bin indicates the number of rows whose area of cells (or overlap of cells) is within a given range. We can see that the histogram in Figure 1(b) concentrates on the middle region, with most subrows having from 40% to 60% of their area occupied by cells. On the other hand, the histogram in Figure 1(c) concentrates on the 0% to 20% bin, with only two subrows having more than 20% of their area occupied by overlaps. However, using absolute values for the y axis of those histograms may bias the ML model to large partitions, since they would have a larger number of subrows. In order to avoid this issue, we normalize the y axis with relation to the number of subrows in the partition, resulting in the histograms H a and H o in Figures 1(d) and (e). Observe that they have the same structure of the previous histograms, with the only difference being the normalized vertical axis.

Algorithm 3 shows the details of how these features are collected from a given partition. The loop from lines 3-13 calculates the values for the first two features (density and area occupied by cells of each height), so it starts by initializing the necessary variables to do so. Those variables are: the area occupied by fixed cells (A f ), the area occupied by movable cells (A m ), the area of the partition itself (A r ) and a list with the areas occupied by cells of each height (A h ). Observe that the area occupied by fixed cells is not considered in A h , since those cells are not moved by the legalization algorithm. However, their area is important to measure the partition density, which is given by the area occupied by movable cells A m divided by the free area in the partition (A r -A f ) in line 14. In addition, for each height, A h is normalized by the partition area. The first loop also measures the maximum displacement of the legalized cells in lines 11-12. This information is used to determine the class of this partition in line 15.

The loop from lines 17-29, on the other hand, is responsible for obtaining the data for the histograms H a and H o . This is done by iterating through all subrows σ i ∈ Σ of the partition and, for each one, measuring the width occupied by the cells intersecting the area of σ i , storing this information in variable a(σ i ). In addition, for the subset of cells C ′ ∈ C(σ i ) that have some overlap with other cells in said subrow, we compute how much overlap there is using variable o(σ i ). Finally, both a(σ i ) and o(σ i ) are normalized by the subrow width w(σ i ) in line 27. This normalization ensures that the ML model is not biased by large subrows that have larger absolute values of a(σ i ) and o(σ i ). The last part of the algorithm creates the normalized histograms H a and H o in lines 30-31.

PHYSICAL DESIGN INTEGRATION

After training and validating the ML model proposed in Section 3, we integrated it in the circuit partitioning strategy of [START_REF] Fabre | Enhancing multi-threaded legalization through kd tree circuit partitioning[END_REF] as a use case to evaluate the ML model. As mentioned in Section 3, their work partitions the circuit using a k-d tree data structure, in a way that the leaf nodes represent the partitions, which are legalized separately. If a partition can not be legalized, it is merged with its sibling node, and the legalization proceeds to their parent node. In the end, the whole circuit legalization can be sped up, since the partitioning strategy reduces the input size of the legalization algorithm. However, doing so may degrade the solution quality, especially maximum displacement. Therefore, we modified their partitioning strategy to merge sibling nodes not only when the legalization fails, but when it results in a large displacement as well. This way, we can prune partitions that would otherwise degrade the solution quality.

There are two ways of doing this pruning strategy: (1) running the legalization algorithm and measuring the displacement of the obtained solution; (2) using the ML model to predict the outcome of the legalization without running the legalization algorithm. We compare these two solutions in order to evaluate the efficiency and impact of the ML model.

Algorithm 4 shows how we implemented the first pruning strategy. The algorithm receives as input the partitions to be legalized (P), the legalization algorithm (L) and the maximum displacement threshold (∆). Then, it iterates through all partitions trying to legalize them. For each partition p i , it runs the legalization algorithm (line 4) and measures the obtained maximum displacement δ max (lines 5-9). If δ max exceeds the threshold ∆ or if the legalization Algorithm 4: PARTITIONED_LEGALIZATION (P, L, ∆) fails, the partition is ignored and its parent node is added to P to be legalized instead (lines 10-11). Otherwise, its cells are placed in their legal locations (lines [START_REF] Kim | ICCAD-2015 CAD contest in incremental timing-driven placement and benchmark suite[END_REF][START_REF] Knime | Knime -open for innovation[END_REF][START_REF] Li | Routability-driven and fence-aware legalization for mixed-cell-height circuits[END_REF]. Observe that, by adding the parent node of p i in P, it is possible to avoid the legalization of the sibling of p i as well with the verification of line 3. If the parent of p i is already in P, this means the sibling of p i resulted in a large displacement or could not be legalized, so p i should be ignored as well.

1 foreach p i in P do 2 P ← P \ {p i }; 3 if par ent (p i ) P then 4 Λ, r esul t ← L(C(p i ), R(p i )); 5 δmax ← -∞; 6 foreach c i ∈ C(p i ) do 7 δ (c i ) ← |l (c i ) -λ(c i ) |;
Running the legalization algorithm to prune partitions with large displacement results in several unnecessary calls to the legalization algorithm, which may take too much time. Therefore, the second pruning strategy relies on the ML model to predict when a partition should be ignored, as detailed in Algorithm 5. Observe that now the algorithm receives as input the machine learning model M as well, which is used in line 4 to predict when the partition can be pruned. Then, it runs the legalization algorithm L only if it was not pruned (line 7), and checks only if the partition was legalized (lines 8-10). If the partition was successfully legalized, it places the cells in the legal locations. In the end, the whole circuit is legalized, but requiring fewer calls to the legalization algorithm L than in Algorithm 4.

EXPERIMENTAL RESULTS

Experimental setup

This work uses the benchmarks from ICCAD 2015 and ICCAD 2017 CAD Contest [START_REF] Darav | Iccad-2017 cad contest in multi-deck standard cell legalization and benchmarks[END_REF][START_REF] Kim | ICCAD-2015 CAD contest in incremental timing-driven placement and benchmark suite[END_REF]. Table 2 presents the names and number of cells of each circuit. We divided the circuits in three groups: training, validation and test. The training and validation sets were obtained by randomly separating the circuits from the ICCAD 2017 CAD Contest into those groups using the holdout method for cross validation. They were used to evaluate different ML models and to select the best model for the integration described in Section 4. This way, the ML model is trained and validated using circuits with multi-row cells, which are more challenging to legalize. On the other hand, the test set is used along with the validation one for a second experiment, which evaluates the quality of the selected ML model when integrated in a circuit partitioning strategy. The test set is composed by the ICCAD 2015 CAD Contest benchmarks, which were not used when selecting the best ML model. Although those circuits do not contain multi-row cells, they are much larger than the others. Therefore, they provide a way to evaluate the speedup achieved by the ML model on large designs.

We performed all experiments in a Linux workstation with an Intel ® Xeon ® E5430 processor with 4 cores @ 2.66 GHz and 16GB DDR2 667MHz RAM. In order to identify the best ML model for our problem we evaluated three options: an artificial neural network (ANN) with a single hidden layer with 10 neurons, a decision tree (DT) and a deep convolutional neural network (CNN), using the resnet34 CNN architecture [START_REF] He | Deep residual learning for image recognition[END_REF]. The first two models were prototyped using the Knime platform [START_REF] Knime | Knime -open for innovation[END_REF], while the CNN was prototyped using the fast.ai library [START_REF] Howard | fast.ai -Making neural networks uncool again[END_REF]. After selecting the best ML model, it was retrained with the same parameters using the Keras framework [START_REF] Keras | The Python Deep Learning library[END_REF], so that we could integrate the model in the C++ code of the circuit partitioning strategy. All experiments are available under public domain, so that they can be reproduced [START_REF]Ophidian: an open source library for physical design research and teaching[END_REF].

Evaluation of machine learning models

Table 3 shows the results of the ML models on the validation set for three different maximum displacement thresholds (∆): 5, 10, and 15 rows. We evaluated the models by their accuracy, precision, recall and F-score 3 . We selected the best results obtained for each model. Since the number of samples of each class (true positive, false positive, etc.) is not necessarily balanced, it is important to evaluate not only the accuracy of the model, but also the precision and recall.

A low precision means a model assumes that some partitions would result in a large displacement when that is not the case, resulting in worse execution times as it takes longer to legalize the larger parent partition. On the other hand, a low recall means that the model will not prune some partitions that should have been pruned. This will result in quality degradation, since Algorithm 5 will accept the legalization even though it should not. When the maximum displacement threshold is 5 rows, ANN and CNN are very similar in accuracy, with CNN achieving a better Fscore. The DT model, on the other hand, seems to be the worst of the three models, with lower accuracy, precision, and recall. When we increased the maximum displacement threshold to 10 rows, there is a slight increase on the accuracy of the DT and ANN models, and 3 F-score is calculated by the harmonic mean of precision and recall.

no difference for the CNN model. However, there was a reduction on the precision for all models, due to the more unbalanced data for this displacement threshold. The recall was only affected on DT, which again makes it the worst of the three models. Finally, when the maximum displacement threshold is 15 rows, the data is even more unbalanced, with less positive instances. In this case, there was an F-score reduction on both ANN and CNN models. The impact was greater on the CNN, whose F-score dropped from 0.83 (with threshold of 5 rows) to 0.68 (with threshold of 15 rows).

These results led us to the following conclusions: (1) DT has a worse F-score for all maximum displacement thresholds, which makes it a poor model for the analyzed problem; (2) increasing the maximum displacement threshold degrades the quality of all models, due to more unbalanced data. Thus, an evaluation with even higher thresholds would require the generation of data with more positive instances.

Integration with circuit partitioning

Based on the evaluation of the ML models, we selected the ANN model to be integrated in the circuit partitioning strategy. Although the CNN achieved a higher accuracy and F-score for the maximum displacement threshold of 5 rows, we selected ANN over CNN for the following reasons: (1) the ANN model achieved a higher accuracy and F-score for the highest displacement threshold (15 rows), which suggests that this model is more robust to unbalanced data; (2) the CNN model is more complex, and therefore it takes longer to classify partitions using it. In order for this increased run time to be compensated, the CNN model must have a much higher accuracy than ANN, which is not the case for the evaluated models; (3) further experiments showed that the CNN model has lower accuracy on smaller partitions than on larger partitions. Since smaller partitions are the majority in the partitioning strategy, it is better to have a higher accuracy for them.

Table 4 shows the results of applying the pruning strategy presented in Section 4 on the validation and test circuits with relation to average displacement, maximum displacement and half-perimeter wirelength (HPWL) 4 . Observe that none of the circuits presented in this table were used for the model training. For each metric we present the ratio of the result when using the pruning strategy by the original result from [START_REF] Fabre | Enhancing multi-threaded legalization through kd tree circuit partitioning[END_REF]. This way, a ratio lower than 1 for a given metric means that its value was reduced (and improved) when using the pruning strategy. For each metric, the table shows the results of two versions of the pruning strategy: LEG (Algorithm 4), and ANN (Algorithm 5 using the ANN model). In addition, the table is divided in the same maximum displacement thresholds as Table 3 (5, 10 and 15 rows).

First of all, observe that for LEG, the results remain the same for all metrics even when increasing the threshold from 5 to 15 rows. The ratios were on average 0.96, 0.32 and 0.99 for average displacement, maximum displacement and HPWL, respectively. This means that increasing the maximum displacement threshold does not make a significant difference for those circuits. The improvement was especially high for the maximum displacement, since this is the metric being verified by the pruning strategy. In addition, there was a significant reduction on the average displacement of circuits pci_bridдe32_a_md2, pci_bridдe32_b_md1, pci_bridдe32_b_md2, pci_bridдe32_a_md1, superblue18 and superblue4, which are the smallest circuits used on this experiment. This happened because, for larger circuits, legalizing the parent nodes in the partitioning strategy may increase the average displacement, since they have a larger area and, therefore, allow more cell movement. However, the increase on average displacement is largely compensated by the reduction on maximum displacement.

When using the ANN model with a maximum displacement threshold of 5 or 10 rows, the results were the same as LEG for almost all circuits, which means the accuracy of the ML model was enough to avoid degrading the solution quality. However, when increasing the maximum displacement threshold to 15 rows, the lower precision of the ANN model results in degradation of the max displacement metric, whose average ratio becomes 0.42. However, this value is still much lower than the results from [START_REF] Fabre | Enhancing multi-threaded legalization through kd tree circuit partitioning[END_REF].

Besides analyzing the solution quality, it is important to also analyze how many calls to the legalization algorithm were avoided by using ANN, and what was the impact on the execution time. Figure 2 shows the ratio of the number of calls to the legalization algorithm performed by ANN compared to LEG. For all cases, the ANN model reduced the number of legalization calls, with a greater reduction in the larger circuits. This happens because the larger number of cells in these circuits increases the probability of a cell resulting in a large displacement, requiring more partition merges. In addition, this reduction is greater with a threshold of 5 rows because it requires 4 Although circuit des_per f _b_md 1 belongs to the validation set, it was not used in this experiment because the legalization algorithm was not capable of legalizing this circuit. more merges, which increases the number of legalization calls for LEG. However, even in the worst case, ANN required 22% less calls to the legalization algorithm (pci_bridдe32_a_md1, 15 rows), but up to 99% in the best case (superblue7, 5 rows). This reduction on number of legalization calls resulted in the speedup presented in Figure 3. This figure shows the speedup only for ICCAD 2015 CAD Contest benchmarks, since the speedup is negligible for the other circuits due to their small size. The speedup was calculated as the ratio of the execution time of LEG by the execution time of ANN, so a speedup greater than 1 means ANN is faster.

The results in Figure 3 show that ANN is faster for all cases, except for superblue16 with the maximum displacement threshold of 15 rows, achieving speedups from 0.86 to 3. In addition, for most cases, the speedup is higher when the maximum displacement threshold is lower because, as observed in Figure 2, in those cases the reduction in the number of legalization calls is greater. However, there are some exceptions, such as superblue18 for thresholds of 10 and 15 rows, as well as superblue3 and superblue5 for thresholds of 15 rows. These cases are also situations where the solution quality has changed when increasing the maximum displacement threshold (Table 4). In these cases, ANN failed to identify some partitions with large displacement, which reduces the execution time but can degrade the solution quality. Finally, although ANN degrades the quality of the pruning for some circuits when using larger displacement thresholds, we observed that the pruning quality is the same for all thresholds when using LEG. Therefore, for the evaluated circuits, increasing the maximum displacement threshold does not improve the solution quality, but only reduces the execution time. Figure 4 shows the speedup achieved by the ANN results for the threshold of 5 rows (which achieved the best solution quality for ANN) compared to the results of LEG for the threshold of 15 rows (which has the smallest execution times for LEG). In this figure, it is possible to see that the best ANN solution is still faster than the best LEG solution by at least 1.14 and up to 2.3, which shows that ANN can effectively speed up the pruning strategy without compromising the solution quality. The speedup of at least 2 in some cases means that, for some circuits, it is possible to evaluate two different maximum displacement thresholds using in the time that only one could be evaluated with LEG.

CONCLUSIONS

In this work we evaluated how ML models can be used to improve the predictability of legalization algorithms. We evaluated three models, including one deep convolutional neural network. The best model was integrated into a circuit partitioning strategy, to act as a pruning mechanism to identify partitions that will result in large displacement after legalization. This pruning strategy greatly reduces the maximum displacement of the legalized solution, and the ML model accelerates this process by avoiding up to 99% of the calls to the legalization algorithm.

As future work, we intend to investigate the possibility of using ML models not only to predict when a partition will violate a given displacement threshold, but to estimate the resulting displacement itself. This can be used to guide incremental placement algorithms, by using the ML model to evaluate the quality of different optimizations (or different legalization algorithms), without requiring to call the legalization algorithm.

Algorithm 1 :

 1 GENERATE_DATA(C, L, R) 1 n_sampl es ← 1024; 2 max _heiдht ← 9; F ← ; 3 for heiдht ← 1 to max _heiдht do 4 n_it er at ions ← n_s ampl es 2 heiдht ; 5 for num_it ← 1 to n_it er at ions do 6 MOVE_CELLS(C, R);

7

 7

  Histogram of area occupied by cells in each subrow. (a) Partition with 20 movable cells and one fixed cell. (d) Normalized area histogram (H a ). (c) Histogram of area occupied by overlaps in each subrow. (e) Normalized overlap histogram (H o ).

Figure 1 :

 1 Figure 1: Circuit features extracted for a hypothetical partition.

8 δmax 9 end 10 if 5 : 6 else 7 Λ 8 if ¬r esul t then 9 P

 891056789 ← max(δmax , δ (c i )); δmax > ∆ ∨ ¬r esul t then 11 P ← P ∪ {par ent (p i )};12 else 13 foreach c i ∈ C(p i ) do 14 l (c i ) ← λ(c i ); ML_PARTITIONED_LEGALIZATION (P, L, ∆, M) 1 foreach p i in P do 2 P ← P \ {p i }; 3 if par ent (p i ) P then 4 if M(C(p i ), R(p i )) then 5 P ← P ∪ {par ent (p i )}; , r esul t ← L(C(p i ), R(p i )); ← P ∪ {par ent (p i )};10 else 11 foreach c i ∈ C(p i ) do 12 l (c i ) ← λ(c i );

Figure

  Figure Comparison between the number of calls to the legalization algorithm done by LEG and ANN.

Figure 3 :

 3 Figure 3: Comparison between and ANN's execution times (speedup = ratio LEG/ANN).

Figure 4 :

 4 Figure 4: Comparison of the execution times between LEG with threshold of 15 rows and ANN with threshold of 5 rows (speedup = ratio LEG/ANN).

Table 1 :

 1 Features used by the ML model.

	Feature Meaning
	D	Density of the partition area
	A h	Area occupied by cells of each height
	H a	Normalized histogram of area occupied by cells on each partition subrow
	H o	Normalized histogram of area occupied by overlaps on each partition subrow
	Algorithm 3:

  i ) ; 28 end 29 Ha ← normalized histogram with values of A; 30 Ho ← normalized histogram with values of O ; 31 return (y, ∆, A h , Ha , Ho );

Table 2 :

 2 Benchmarks used in the experiments.

	Benchmark	# Cells of different heights 1 2 3 4	Benchmark set	Group
	pci_bridge32_a_md1 26K	1.7K 597	448	ICCAD17	validation
	pci_bridge32_a_md2 25K	2K	1.1K 994	ICCAD17	validation
	pci_bridge32_b_md1 26K	1.7K 585	439	ICCAD17	validation
	pci_bridge32_b_md2 28K	292	292	292	ICCAD17	validation
	pci_bridge32_b_md3 27K	292	585	585	ICCAD17	training
	fft_2_md2	28K	2.1K 705	529	ICCAD17	training
	fft_a_md2	27K	2K	672	504	ICCAD17	training
	fft_a_md3	28K	672	672	672	ICCAD17	training
	des_perf_a_md1	103K	4.6K 0	0	ICCAD17	training
	des_perf_a_md2	105K	1K	1086 1K	ICCAD17	training
	des_perf_1	112K	0	0	0	ICCAD17	training
	des_perf_b_md1	106K	5.8K 0	0	ICCAD17	training
	des_perf_b_md2	101K	6.7K 2.2K 1.6K ICCAD17	training
	edit_dist_1_md1	118K	7.9K 2.6K 1.9K ICCAD17	training
	edit_dist_a_md2	115K	7.7K 2.5K 1.9K ICCAD17	training
	edit_dist_a_md3	119K	2.5K 2.5K 2.5K ICCAD17	training
	superblue18	768M	0	0	0	ICCAD15	test
	superblue4	795M	0	0	0	ICCAD15	test
	superblue16	981M	0	0	0	ICCAD15	test
	superblue5	1086M 0	0	0	ICCAD15	test
	superblue1	1209M 0	0	0	ICCAD15	test
	superblue3	1213M 0	0	0	ICCAD15	test
	superblue10	1876M 0	0	0	ICCAD15	test
	superblue7	1931M 0	0	0	ICCAD15	test

Table 3 :

 3 Results of different ML models for different maximum displacement thresholds.

		Max disp threshold of 5 rows	Max disp threshold of 10 rows	Max disp threshold of 15 rows
	ML model accuracy precision recall F-score accuracy precision recall F-score accuracy precision recall F-score
	ANN	81%	86%	72%	0.78	85%	78%	73%	0.75	84%	69%	72%	0.70
	DT	76%	83%	63%	0.71	82%	76%	58%	0.66	83%	71%	63%	0.67
	CNN	82%	84%	83%	0.83	82%	72%	83%	0.77	80%	70%	66%	0.68

Table 4 :

 4 Results when integrating the ANN model to the partitioning strategy

			Max disp threshold of 5 row			Max disp threshold of 10 row	Max disp threshold of 15 row
	Design	Avg disp	Max disp	HPWL	Avg disp	Max disp	HPWL	Avg disp	Max disp	HPWL
		LEG ANN LEG ANN LEG ANN LEG ANN LEG ANN LEG ANN LEG ANN LEG ANN LEG ANN
	pci_bridge32_a_md2 0.92	0.92 0.77	0.77 0.95	0.95 0.92	0.92 0.77	0.77 0.95	0.95 0.92	0.92 0.77	0.77 0.95	0.95
	pci_bridge32_b_md1 0.69	0.69 0.30	0.30 0.99	0.96 0.69	0.69 0.30	0.30 0.99	0.96 0.69	1.01 0.30	0.91 0.99	1.00
	pci_bridge32_b_md2 0.90	0.91 0.33	0.33 0.98	0.98 0.90	0.91 0.33	0.33 0.98	0.98 0.90	0.87 0.33	0.45 0.98	0.98
	pci_bridge32_a_md1 0.89	0.89 0.95	0.95 0.98	0.98 0.89	0.89 0.95	0.95 0.98	0.98 0.89	0.89 0.95	0.95 0.98	0.98
	superblue10	1.01	1.01 0.21	0.21 1.00	1.00 1.01	1.01 0.21	0.21 1.00	1.00 1.01	1.01 0.21	0.21 1.00	1.00
	superblue18	0.96	0.96 0.11	0.11 1.00	1.00 0.96	0.92 0.11	0.11 1.00	1.00 0.96	0.92 0.11	0.24 1.00	1.00
	superblue4	0.87	0.87 0.17	0.17 1.00	1.00 0.87	0.87 0.17	0.17 1.00	1.00 0.87	0.85 0.17	0.17 1.00	0.99
	superblue7	1.04	1.04 0.13	0.13 1.00	1.00 1.04	1.04 0.13	0.13 1.00	1.00 1.04	1.04 0.13	0.13 1.00	1.00
	superblue1	1.08	1.08 0.06	0.06 1.00	1.00 1.08	1.08 0.06	0.06 1.00	1.00 1.08	1.08 0.06	0.06 1.00	1.00
	superblue16	1.06	1.06 0.52	0.52 1.00	1.00 1.06	1.06 0.52	0.52 1.00	1.00 1.06	1.06 0.52	0.52 1.00	1.00
	superblue3	1.01	1.01 0.18	0.18 1.00	1.00 1.01	1.01 0.18	0.18 1.00	1.00 1.01	0.94 0.18	0.28 1.00	1.00
	superblue5	1.05	1.05 0.12	0.12 1.00	1.00 1.05	1.05 0.12	0.12 1.00	1.00 1.05	0.96 0.12	0.34 1.00	1.00
	Average	0.96 0.96 0.32 0.32 0.99 0.99 0.96 0.96 0.32 0.32 0.99 0.99 0.96 0.96 0.32 0.42 0.99 0.99
	Median	0.98 0.98 0.19 0.19 1.00 1.00 0.98 0.96 0.19 0.19 1.00 1.00 0.98 0.95 0.19 0.31 1.00 1.00

The displacement of a cell c i is given by the Manhattan distance between its legalized location l (c i ) = (x (c i ), y(c i )) and its location before legalization l ′ (c i ) = (x ′ (c i ), y ′ (c i )).

The smallest circuit used in the experiments has an area of

× 342000, so this movement corresponds to at most 3% of the circuit dimensions.

ACKNOWLEDGMENTS

This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior -Brasil (CAPES) -Finance Code 001 and by the Brazilian Council for Scientific and Technological Development (CNPq) through Project Universal (457174/2014-5) and PQ grants 310341/ 2015-9.


A n accurate local measurement of two-phase flow characteristics is important for the development of two-phase flow models. Computational fluid dynamics (CFD) is developing rapidly in chemical engineering and models arising for these simulations need accurate experimental data to be validated. In gas-liquid contactors, precise knowledge of interfacial area is essential for quantification of mass transfer efficiency. Multi-sensor needle probes are a very common tool for gas-liquid local dynamics investigations in high void fraction bubbly flows where most other techniques have failed. The current study concerns a double optical probe but some recent work has involved miniaturized four-sensor conductivity probes [START_REF] Kim | Study on Interfacial Structures in Slug Flows Using Miniaturized Four-Sensor Conductivity Probe[END_REF] which provide similar signals. However, the results concerning the probe intrusiveness are relevant to most existing probes.

From these probes, local two-phase flow parameters such as bubble frequency, bubble velocity, void fraction, bubble chord lengths, bubble size and interfacial area concentration can be deduced. Interfacial area can be evaluated through statistical correlations incorporating bubble frequency, bubble velocity distribution and a correction factor based on the impact (hitting) angle described by the normal interfacial velocity vector and probe vertical axis [START_REF] Revankar | Local Interfacial Area Measurement in Bubbly Flow[END_REF][START_REF] Dias | Statistical Method to Calculate Local Interfacial Variables in Two-Phase Bubbly Flows Using Intrusive Crossing Probes[END_REF]. However, [START_REF] Kiambi | Measurements of Local Interfacial Area: Application of Bi-Optical Fibre Technique[END_REF] showed in a recent study that the interfacial area, when evaluated by this way in a highly dispersed flow, is underestimated with respect to the classical 6a g /d Sauter formula. The inaccuracies are attributed to bubble velocity overestimation due to bubble spherical shape assumption, bubble surface deformation, and missed bubbles (bubbles that miss at least one of the sensors). Furthermore, it is not clear from previous studies whether the velocity to be taken into account to characterise interfacial area transport, has to be the bubble interface velocity, the vertical velocity or that of its centre of mass.

The objectives of the authors are to put in evidence bubble-probe interaction and the related disturbance, and to evaluate the corresponding discrepancies in the measured parameters. The path of the bubble as it ascends in water is filmed by two high-speed cameras and the resulting signal is recorded by means of a double optical probe electronic module.

*Author to whom correspondence may be addressed. E-mail address: henri.delms@ensigct.fr

Experimental Set-up and Measurement Procedure Experimental Set-up

The set-up consists of a test section in an open tank of 700mm height with a square cross-section of 150mm as shown in Figure 1. To allow full optical access the four sides of the tank are made of glass. For air injection two stainless steel capillary tubes are located at the mid-point of the tank base. These capillaries of 0.33mm and 1mm internal diameters produce bubbles of 2.15mm and 4.5mm equivalent diameters respectively. Air is injected at low flow rates to ensure

The objective of this study is to evaluate the accuracy of double optical probe technique in local two-phase flow measurements. Able to provide both bubble velocity, chord length, and gas hold-up, this technique involves nevertheless delicate signal treatment procedures and, being intrusive, depends on probe tips configurations and sizes. During probe-bubble interactions, bubble surface is occasionally deformed and this can complicate measurements analysis. The current study is focussed on the rise of single bubbles of known sizes in still water (equivalent diameter of 2.15mm and 4.5mm). Bubble parameters obtained from digital image processing method and from a double optical probe are compared statistically. L'objectif de ce travail est de quantifier la précision de la sonde optique à deux fibres pour des mesures locales en écoulements biphasiques. Bien que pouvant fournir la vitesse de bulle, sa longueur de corde, et le taux de gaz, cette technique nécessite des procédures de traitement du signal délicates, et étant intrusive, elle dépend des forme et taille de la sonde. On visualise comment l'interaction sonde-bulle perturbe la forme et la vitesse de la bulle. Pour deux diamètres équivalents, 2,15 et 4,5mm, les paramètres de bulles uniques en ascension dans de l'eau au repos, obtenus par sonde optique double et par traitement d'images, sont comparés statistiquement.

Keywords: Double optical probe, gas hold-up, bubble velocity, image processing. that the bubble volume at detachment is controlled by static balance between surface tension and buoyancy forces. Bubbling frequency is kept low enough to avoid the wake effects of preceding bubbles.

Measurements of Bubble

Double Optical Fibre Probe

A double optical probe (RBI) is mounted into the tank at a height of 350mm above injection level where the bubbles have already attained their terminal velocity. The probe tips have a diameter of 40mm and are 3.1mm from each other (Figure 2a). The image acquisition is synchronised with the optical probe acquisition such that the signal from the first probe sensor triggers the image acquisition. This means that only bubbles pierced by the first fibre are filmed.

The measurement principle of the probe technique lays on the difference of refraction indexes between the two media (air and water). The sampling frequency of the probe is 6.25kHz which ensures accurate signal registration. Each of the two optical sensors is connected to its own measuring circuit and therefore each sensor is used as an independent phase identifier. A sample of two signals recorded is shown in Figure 2b. Phase discrimination is done by setting a threshold on the output signal as shown on the figure.

From the output signal of the probe, the local gas hold-up and the local bubbling frequency can be evaluated [START_REF] Liu | Structure of Air-water Bubbly Flow in a Vertical Pipe: Liquid Mean Velocity and Turbulence Measurements[END_REF] Local gas hold-up at a point P in the gas/liquid flow is given by a p = Â nb 1 t R /T where nb is the total number of bubbles pierced by fibre1, T is the total measuring time and t R is the bubble residence time on the first probe (t R = t12 -t11, see Figure 2b). A statistical analysis based on cross correlation of both signals [START_REF] Kamp | Écoulements turbulents à bulles dans une conduite en micropesanteur[END_REF] identifies bubbles pierced by both probe tips and for these bubbles, the interfacial velocity is obtained from the bubble transit time between the two probe tips t21 -t11 : interfacial bubble velocity from the probe is evaluated from V Pi = l12/(t21 -t11) l 12 where is the distance between the two probe tips. Bubble chords lengths are equal to: (t12 -t11) V Pi . At first, the 0.33mm injector was placed on the bottom of the test tank to produce small bubbles. Rising bubbles are filmed by means of a Kodak Ektapro EM high-speed video system at rate of 1000 images.s -1 . Two cameras perpendicular to tank walls (Figure 1) are used simultaneously to allow a three-dimensional bubble analysis (Figure 1). Filming is performed in such a way that the spatial resolution describes accurately and simultaneously the bubble shape and path. A plane grid of known geometry is filmed to be used for images calibration (conversion of Pixels into mm). A total of 250 bubbles were filmed. After filming, the 0.33mm injector was replaced with the 1mm injector and the same procedure repeated. Only camera setting were adjusted to cater for bubble size.

Images from the two high-speed cameras are digitalized and stored in a computer. A commercial program (Optimas) is used for image processing. The treatment steps include division by background image, filtering, threshold setting and binarisation, erosions and dilations. The bubble contours are finally extracted. The maximum error in bubble contour extraction is about 1 pixel. The bubble centre of mass, the major and minor axis are obtained from bubble contours by aid of homemade software. Two different procedures were used for threedimensional bubble interface reconstruction.

Reconstruction of Small Bubble Interface

Bubbles from 0.33mm injector have an equivalent diameter of 2.15mm. They are oblate ellipsoids of constant shape. In the bubble motion, the axis of symmetry (minor axis) is parallel to bubble centre velocity [START_REF] Ellingsen | On the Rise of an Ellipsoidal Bubble in Water: Oscillatory Paths and Liquid-Induced Fluctuations[END_REF]. In all cases the measured contour of the bubble was similar to an ellipse with major semi-axis = 1.38±0.05 mm and minor semi-axis = 0.72±0.05 mm.

After initial acceleration, bubbles undergo regular path oscillations. Consequently, the bubble-centre coordinates could be written as:

x G (t) = x 0 + L x sin [w x (t-t 0x )]
(1)

y G (t) = y 0 + L y sin [w y (t-t 0y )] (2) z G (t) = z 0 + L z sin [w z (t-t 0z )] + - V z t (3)
where t is the time. The spatial origins (x 0 , y 0 , z 0 ), the time origins (t 0x , t 0y , t 0z ), the amplitudes (L x , L y , L z ) and the angular frequencies (w x , w y , w z ) were determined for each bubble by least square fitting method between measured bubble centre time series and the analytic equations above, until the bubble touches the probe. Details of this procedure are given in [START_REF] Ellingsen | On the Rise of an Ellipsoidal Bubble in Water: Oscillatory Paths and Liquid-Induced Fluctuations[END_REF]. For a bubble of given size, the parameters of its trajectory are determined : this procedure ensured an accurate determination of the bubble interface. Figure 3a shows superimposition of a filmed bubble and a theoritical ellipse. Extrapolation of the analytical equations beyond fibres positions is used to analyse the probe impact on the bubble trajectory. During impact, several observations were made : (i) some bubbles were flattened by the probe during piercing, (ii) some bubbles were deviated by the first fibre and never reached the second probe, and (iii) the impact on the first probe provoked sometimes a sudden trajectory change. The last observation is illustrated by Figure 3b.

Thus for small bubbles (d = 2.15mm), the shape and the path are well defined and the bubble velocities are obtained by derivatives of the 3 analytic functions above.

Reconstruction of Large Bubble Interface

For larger bubbles however, the procedure described above is no longer valid. In fact according to [START_REF] Perkins | Shape Oscillations of Rising Bubbles[END_REF], bubbles of this size (equivalent diameter 4.5mm) have no constant shape. They exhibit both shape and path oscillations. The shape is rather elongated ellipsoidal and spheroid becoming wobbly and the motion is rocking. This was confirmed by visual observations. Direct bubble shape determination was not possible as only projections on two vertical planes are available (x-z and y-z). An algorithm was developed to obtain the 3 dimensional shape of the bubble at each instant from the two planes [START_REF] Kiambi | Analyse métrologique de la sonde optique double : interaction sonde-bulle et application en gazosiphon[END_REF]. Figure 4 (a andb) shows the bubble images from the two cameras and the corresponding shape obtained. The validity of this procedure was checked by computing the volume (which should be constant) of the resulting reconstructed bubble shapes. For the same bubble, the volume variation between any two images from the shapes hence obtained was 2% while that between different bubbles was 7%. This variation is reasonable as it incorporates bubble shape changes.

The Virtual Probe

A virtual probe is introduced on the path of each reconstructed bubble shape and the impact times (t11, t12, t21, t22) are evaluated numerically from the 3 dimensional analysis of the reconstructed bubble motion past the virtual probe fibres positions. Interfacial bubble velocity (V mi ) around the probe is evaluated from the distance (l 12 ) between the 2 probe fibres and the impact times. Bubble residence time on the first fibre,t R , which leads to gas hold-up and bubble chords lengths, is also pierced by the first fibre, T being the measuring time and t Rm the average bubble residence time on the first fibre. Then, the relative error on void fraction can be written as :

The results of this work quantify only the error on mean residence time. The underestimation of 14% for bubbles of 2.15mm and that of 6% on bubbles of 4.5mm shows that the intrusive nature of the double optical probe can be consequential in void fraction determination. Note that the probe is more accurate as the size of bubbles increases.

Bubble Velocity

The PDF of bubble centre velocities for bubbles of d = 2.15mm are represented in Figure 7. Table 3 shows the number of bubbles sampled and the corresponding mean velocities. The advantage of imaging method is that, other velocity components (such as bubble vertical velocity, the magnitude of (4)

D D D a a = + Nb Nb t t Rm R
the bubble velocity and velocity fluctuations) can be evaluated at each instant along the bubble path. The vertical component of the bubble centre velocity V z , the horizontal components (V x , V y ) and the absolute bubble centre velocity V n , are deduced from images.

Interfacial velocities from the probe V pi , and from images V mi refer to bubble interface velocity past the real and virtual probes respectively. From Figure 7, real probe gives an interfacial velocity (V pi ) higher than the virtual probe (V mi ). This difference is probably induced by the bubble path deviations by the first fibre of the real probe. Note that to quantify velocity from an optical probe the bubble must be pierced by the two fibres. It is probable that bubbles ascending vertically are less perturbed by the probe and are more likely to reach the second fibre. This may induce a statistical bias favouring higher vertical velocities. The observations made during bubble piercing also shows that the first fibre provokes sudden bubble directional rotations which could induce vertical bubble accelerations (see Figure 3b). Although

Figure 1 .

 1 Figure 1. Experimental set-up.

Figure 2 .

 2 Figure 2. Double optical probe and the time lags from output signals by the two fibres.

Figure 3 .

 3 Figure 3. Superimposition of bubble contour and an exact ellipse for bubbles of 2.15mm equivalent diameter.

Figure 7 .

 7 Figure 7. Probability density functions of different bubble velocities (bubbles of 2.15mm).

Figure 6 .

 6 Figure 6. Comparison of residence times of down stream and up stream fibres between real and virtual probes: bubble of 4.5mm.

Table 2 .

 2 Data of residence time for bubbles of 4.5mm equivalent diameter.

	Real probe		Number	Mean residence
			of bubbles	time
		Fibre 1	3367	5.1
		(t12 -t11)
		Fibre 2	2545	4.4
		(t22 -t21)
	Virtual probe	Fibre 1	881	5.4
		(t12 -t11)
		Fibre 2	1159	5.3
		(t22 -t11)

Table 3 .

 3 Velocity components fir bubbles of 2.15mm equivalent diameter.

	Real probe		Number	Mean
			of bubbles	velocity
		Interfacial velocity	418	373.30
		(mm/s)
	Virtual probe	Interfacial velocity	287	355.03
		(mm/s)
		Absolute velocity	187	333.40
		(mm/s)
		Vertical velocity	187	313
		(mm/s)
		Horizontal velocity	187	0
		(mm/s)

Laboratoire de Génie Chimique de Toulouse, Parc d'Activités de Basso Cambo, 5 rue Paulin Talabot, 31106 Toulouse, France

Institut de Mécanique des Fluides de Toulouse, 1 Allée du Professeur Camille Soula,

Toulouse, France