Greg Stitt
email: gstitt@cs.ucr.edu

Frank Vahid
email: vahid@cs.ucr.edu

A Decompilation Approach to Partitioning Software for Microprocessor/FPGA Platforms

In this paper, we present a software compilation approach for microprocessor/FPGA platforms that partitions a software binary onto custom hardware implemented in the FPGA. Our approach imposes less restrictions on software tool flow than previous compiler approaches, allowing software designers to use any software language and compiler. Our approach uses a back-end partitioning tool that utilizes decompilation techniques to recover important high-level information, resulting in performance comparable to high-level compiler-based approaches.

Introduction

Several commercial platforms have begun to integrate microprocessors and FPGA onto a single-chip. Designers have typically used the FPGA in these platforms for implementing peripherals. More recently, designers have used the FPGA to implement custom hardware that speeds up the execution of software running on the microprocessor.

For several platforms, platform vendors have developed compilers to enable software developers to automatically partition high-level software source code onto the FPGA in order to speedup software execution. These compilers provide good technical solutions for partitioning software but impose several restrictions that software developers may find undesirable. One restriction is that these compilers generally support only one particular language, generally C/C++. Software developers also generally have well-established software development tools and would resist a change to a different compiler.

Thus, a partitioning tool would likely be far more practical if placed after the compiler in the tool flow, operating during the software linking stage, or by parsing the final software binary. The partitioning/synthesis tool would thus be independent of the compiler tool -any source language and/or compilers could be utilized. The partitioning/synthesis tool could be provided by the platform vendor, thus incorporating specific knowledge of the platform architecture, which may involve extensive details involving communication, memory, interrupt, arbitration, etc., necessary to perform good partitioning and synthesis. Such an approach will not replace the use of specialized languages and compilers used by advanced designers, but will instead extend the advantages of microprocessor/FPGA platforms to a much wider range of software developers, for whom the possibly lower-quality results compared to a compiler approach are still far better than software-only implementations.

In this paper, we show that the key to performing good partitioning and synthesis after compilation is to be able to recover the necessary high-level information. Such recovery is known as decompilation. We have therefore developed an extensive set of decompilation methods specifically intended for partitioning and synthesis. We point out that our methods are also applicable for synthesizing an entire software application, not just kernels, to a custom circuit.

Decompilation

Decompilation was originally developed for purposes of translating software binaries from one instruction set architecture to another and for recovering high-level code from legacy assembly code. We use decompilation for a different purpose, namely for converting a software binary into a representation suitable for synthesis. That different purpose meant we had to select among existing decompilation methods and adapt them to our needs, and also that we had to develop new decompilation methods specifically for our purpose.

Our decompilation process uses existing decompilation techniques [START_REF] Cifuentes | Preliminary Experiences with the Use of the UQBT Binary Translation Framework[END_REF] to convert the software binary into a control/data flow graph (CDFG) that is annotated with high-level information. Initially, binary parsing converts the software binary into an instruction set independent representation. Next, CDFG creation builds a control/data flow graph (CDFG) for the application. Control structure recovery analyzes the CDFG and determines high-level control structures, such as loops and if statements.

After recovering a CDFG of the application, we apply several optimizations to eliminate overhead introduced by the instruction set. One such overhead is the use of arithmetic instructions with a immediate value of zero in order to move a value between two registers. Although a move instruction is more appropriate, binary-level synthesis cannot assume a compiler will use instructions appropriate for synthesis. If the arithmetic operator is synthesized, then large amounts of area will be wasted. We remove this overhead using constant propogation. We also perform operator size reduction, strength reduction, and stack operation removal.

In addition to removing instruction set overhead, we must also undo software compiler optimizations in order to make the recovered CDFG more appropriate for synthesis. Strength reduction of multiplication operations is a compiler optimization that can reduce the quality of binary-level synthesis. Although strength reduction is generally beneficial, the additional adders and shift resources required to perform multiplications may exhaust these resources, leading to increased latency, even if hardware multipliers are available. To achieve the fastest hardware, the synthesis tool must decide whether strength reduction is beneficial. To give the synthesis tool this added flexibility, we perform strength promotion to convert series of shift/add operations back into the original multiplication form.

Loop unrolling can also result in inefficient binary-level synthesis. Loop unrolling can obscure high-level information such as memory access patterns and resource requirements, which are needed for effective synthesis. Loop unrolling can also greatly increase the size of a software binary, which can increase synthesis execution times and memory requirements, making dynamic synthesis approaches infeasible. We use loop rerolling to identify unrolled loops and then roll the loops back into a representation similar to their original representation in high-level code.

Partitioning and synthesis

Although we considered using standard hardware/software partitioning approaches [START_REF] Henkel | A Low Power Hardware/Software Partitioning Approach for Core-Based Embedded Systems[END_REF][3], we use a simpler technique based on the well-known 90-10 rule in order to reduce the time required for partitioning.

Achieving a small partitioning execution time is important because we intend to integrate our approach with existing dynamic partitioning and dynamic synthesis approaches [START_REF] Lysecky | Dynamic FPGA Routing for Just-in-Time Compilation[END_REF]. Our partitioning algorithm proceeds in three steps. In the first step, we use profiling results to identify the most frequent few loops, which generally correspond to 90 percent of execution while consisting of only a few dozen lines of code. We then include these loops in the hardware partition. In the second step, we use alias information to find regions of code that access the same memory locations as the loops in the hardware partition. If space allows, we include these regions in the hardware partition so that the required memory locations can be moved to memory within the FPGA, increasing parallelism. In the third step, we continue to add regions to the hardware partition based on profiling results and hardware suitability until the area constraint is violated. This final step allows an entire application to be synthesized if space allows.

Our approach utilizes a behavioral synthesis tool that we implemented ourselves. The input to the synthesis tool is the decompiled CDFG for the regions selected for hardware implementation. The output of the tool is register transfer-level VHDL. We use Xilinx ISE to synthesize the VHDL to a netlist.

Results of decompilation-based partitioning

We applied our decompilation-based partitioning approach to twenty examples from EEMBC, PowerStone, MediaBench, and our own benchmark suite. All examples were compiled using gcc with -O1 optimizations.

Instead of using a commercial platform, we utilized a hypothetical platform consisting of a MIPS microprocessor and Xilinx Virtex II FPGA. Using a hypothetical platform allows us to more easily evaluate different types of platforms with different clock speeds and FPGA sizes.

The decompilation-based approach showed consistently good application speedups and energy savings, averaging 5.4 and 69%, compared to a MIPS processor running at 200 MHz. The average kernel speedup was 44.8. Compared to a 400 MHz MIPS, the application speedups were 3.8 and the energy savings were 49%. For slower platforms with a 40 MHz microprocessor, the application speedup was 12.6 and the energy savings were 84%. The average area required was an equivalent of 26,261 logic gates. For these examples, our approach recovered almost all the relevant high-level constructs successfully. The only unsuccessful situations occurred during CDFG recovery, which failed for two EEMBC examples because of indirect jumps.

In addition to the experiments based on software binaries generated with -O1 optimizations, we performed the same experiments on binaries generated using four different optimizations levels for four of the previous examples. As expected, software execution times improved as the level of compiler optimizations increased. In most cases, the execution times of the synthesized examples also improved with more compiler optimizations. This phenomenon implies that software compiler optimizations generally do not negatively impact binary-level synthesis, and in many cases binary-level synthesis actually improves when more compiler optimizations are applied. Speedup was significant for all levels of compiler optimizations, although the speedup did not always increase with more compiler optimizations. Speedup did not always increase because as more compiler optimizations are applied, the software became significantly faster, which increased the difficulty of achieving large speedups. Note that execution time is the true measure of the effectiveness of binary-level synthesis. We report speedups to simply show that significant improvements are achieved for each individual level of compiler optimization. The energy savings were also very similar across different levels of compiler optimizations.

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

Acknowledgements

This research was supported in part by the National Science Foundation (CCR-0203829) and by the Semiconductor Research Corporation (2003-HJ-1046G).


Aseem Agarwal
email: abagarwa@umich.edu

Kaviraj Chopra
email: kaviraj@umich.edu

David Blaauw
email: blaauw@umich.edu

Statistical Timing Based Optimization using Gate Sizing

published or not. The documents may come

Introduction

Static Timing Analysis (STA) has been the mainstay of performance verification for the past two decades. Traditionally, process variation has been addressed in STA using corner-based analysis where all gates are assumed to operate at a worst-, typical-or bestcase condition and within-die variability is not modeled. However, in the nanometer regime, within-die variation has become a substantial portion of the overall variability and corner-based STA suffers from significant inaccuracy. This has given rise to a new field of statistical timing analysis known as SSTA.

In SSTA, the circuit delay is considered a random variable and the objective of SSTA is to compute its probability distribution. Socalled block-based SSTA approaches [START_REF] Berkelaar | Statistical Delay Calculation, a Linear Time Method[END_REF][START_REF] Liou | Fast Statistical Timing Analysis By Probabilistic Event Propagation[END_REF][START_REF] Agarwal | Computation and Refinement of Statistical Bounds on Circuit Delay[END_REF][START_REF] Devgan | Block-based Static Timing Analysis with Uncertainty[END_REF][START_REF] Chang | Statistical Timing Analysis Considering Spatial Correlations using a Single Pert-like Traversal[END_REF] are analogous to STA in that they propagate arrival times through the circuit. As the arrival times traverse gates, the delay of the gate is added to the arrival time and a maximum arrival time is selected when multiple arrival times converge at a gate. In SSTA, the arrival times also become random variables, and hence, the addition and maximum operations of STA are replaced by convolution and a statistical maximum, respectively. Like STA, they require a single pass of the circuit to compute the circuit delay distribution. From the CDF (cumulative distribution function) of the circuit delay, the user is then able to obtain the percentage of fabricated dies which meets a certain delay requirement, or conversely, the expected performance for a particular yield. In turn, gate or transistor sizing approaches should consider such metrics for their objective function and should perform their optimization in a statistically aware manner. SSTA-based optimization can significantly improve the yield of a design compared to deterministic optimization. This is due to the fact that deterministic optimization tends to create a so-called "wall" of critical and nearly critical paths, as shown in Figure 1a, since there is no incentive to improve path delays that are not critical. All critical paths can affect the circuit delay due to delay variability, and hence, a balanced circuit with many near-critical paths is highly susceptible to process variations. This is illustrated in While both path distributions have the same deterministic circuit delay, the unbalanced distribution results in a better statistical circuit delay since it has fewer near-critical paths. Hence, deterministic optimization can actually worsen the true statistical circuit delay due to the lack of a true statistical objective function.

Recently, a number of statistical optimization algorithms have been proposed in [START_REF] Hashimoto | Increase in delay uncertainty by performance optimization[END_REF][START_REF] Bai | Uncertainty-aware circuit optimization[END_REF][START_REF] Jacobs | Gate sizing using a statistical delay model[END_REF][START_REF] Raj | A methodology to improve timing yield in the presence of process variations[END_REF]. In [START_REF] Hashimoto | Increase in delay uncertainty by performance optimization[END_REF] it is shown that by performing deterministic optimization, it is possible to degrade the performance of the die statistically due to the creation of a timing wall (Figure 1). Hence, in [START_REF] Bai | Uncertainty-aware circuit optimization[END_REF] the authors propose a method to avoid the formation of such a wall by purposely improving non-critical paths in the deterministic optimization. In [START_REF] Jacobs | Gate sizing using a statistical delay model[END_REF] and [START_REF] Raj | A methodology to improve timing yield in the presence of process variations[END_REF], the statistical optimization problem has been considered as a nonlinear programming problem. Delays are considered to be gaussian and approximations are used for computing the statistical maximum. In [START_REF] Raj | A methodology to improve timing yield in the presence of process variations[END_REF], a heuristic approach is proposed using the concept of statistically 'undominated' paths. These approaches suffer from lack of true sensitivity computation and prohibitive runtimes for large circuits.

In this paper, we therefore propose a new sensitivity based, statistical gate sizing algorithm. We use a coordinate descent algorithm where in each iteration the gate with the highest sensitivity is sized up. We show that such a statistically aware optimization can improve the 99-percentile delay by up to 10.5% over that obtained with traditional deterministic optimization. It should be noted, as shown in Figure 2, that a sizing change can impact both the mean and the shape of the circuit delay CDF. Depending on the objective specified by the user, the CDF perturbation can be evaluated in a number of ways. In this paper, we consider as objective the CDF delay at the 99% probability or confidence point, as shown in Figure 2. Hence, the computed sensitivity is measured as the change in the 99-percentile delay of the circuit delay CDF. However, other objective functions could be equally well supported by the proposed framework.

Since brute-force computation of such CDF perturbation sensitivities is extremely expensive, a key contribution of this paper is an efficient and exact pruning algorithm that allows for identification of the most sensitive gate in the circuit. Our pruning approach is based on a proposed theory of bounds on CDF perturbations due to sizing. We establish the useful property that these perturbation bounds can only diminish as the arrival time perturbations are propagated through the circuit using convolutions and maximum operations. Based on this property, we propose a pruning algorithm for finding the highest sensitivity gate in a sizing iteration, without complete propagation of the perturbed arrival times for all gates.

We perform an iterative propagation of perturbed arrival times for a pruned set of gates by maintaining their so-called perturbation fronts (defined later). We test our approach on a number of benchmark circuits, and demonstrate up to 56 times faster runtimes than the brute force sensitivity computation based optimization, without loss in accuracy.

The remainder of this paper is organized as follows. In Section 2, we present our modeling assumptions, along with the problem formulation, basic definitions and delay model. In Section 3, we present our approach for sensitivity computation and optimization. In Section 4, we present our results and compare deterministic optimization with brute force statistical and our proposed accelerated approach. Finally, in Section 5 we draw our conclusions.

Problem Formulation

In this section we define our modeling assumption and our SSTA approach. We also formulate the statistical optimization problem and present basic definitions and the delay model. Gate delay variability is composed of two primary components: inter-die (between-die) variability and intra-die (within-die) variability. Inter-die variability expresses the change in gate delay from one die to the next and has traditionally been modeled using corner analysis with reasonable accuracy. The main focus of SSTA has therefore been on intra-die variability, which corner-based analysis is unable to model. Hence, similar to the optimization approaches proposed in [START_REF] Jacobs | Gate sizing using a statistical delay model[END_REF][START_REF] Raj | A methodology to improve timing yield in the presence of process variations[END_REF] we focus on intra-die variability in this paper.

One of the difficulties in SSTA arises from reconvergent circuit structures, which results in correlations between arrival times. In [START_REF] Liou | Fast Statistical Timing Analysis By Probabilistic Event Propagation[END_REF][START_REF] Agarwal | Computation and Refinement of Statistical Bounds on Circuit Delay[END_REF], it was shown that the worst-case runtime for exact computation of the circuit delay CDF in a reconvergent circuit is exponential with circuit size, making its computation impractical. However, in [START_REF] Agarwal | Computation and Refinement of Statistical Bounds on Circuit Delay[END_REF] a simple method where these correlations are ignored was shown to result in an upper bound on the circuit delay CDF and hence a conservative analysis. Furthermore, it was shown that these bounds are typically tight and give a reasonably close approximation of the exact circuit delay CDF while their computation runtime is linear with circuit size. In this paper, we therefore use the bounds proposed in [START_REF] Agarwal | Computation and Refinement of Statistical Bounds on Circuit Delay[END_REF] for computation of the circuit delay CDF. It is important to note that the optimization objective is defined on this bound of the circuit delay CDF and not on the exact circuit delay CDF itself, since this would lead to prohibitive runtimes. However, we show in the result section that the optimization of the bounds, as performed by our method, results in nearly equivalent improvement of the exact circuit delay, as verified using Monte-Carlo simulation.

In addition to reconvergent circuit structures, spatial correlation of the gate delays can also give rise to correlation of arrival times [START_REF] Chang | Statistical Timing Analysis Considering Spatial Correlations using a Single Pert-like Traversal[END_REF]. However, similar to previous optimization methods [START_REF] Jacobs | Gate sizing using a statistical delay model[END_REF][START_REF] Raj | A methodology to improve timing yield in the presence of process variations[END_REF], our optimization approach does not model such correlations at this time, although the proposed methods form a basis from which such correlations can be incorporated.

In a statistical timing paradigm, the delay of the circuit is a random variable. As a result, one needs to determine an appropriate objective function for optimization, defined on the distribution of the circuit delay random variable. Since we use propagation of discretized arrival time PDFs, and not merely the statistical measures such as mean and variance, we obtain the entire shape of the circuit delay distribution. Hence, the proposed framework can support a wide range of cost functions as optimization objectives. For simplicity of explanation, however, we choose as our optimization objective the p-percentile point of the delay distribution. In our experiments, we choose p to be the 99-percentile point, as shown in Figure 2.

We use the following graph representation for our circuits.

Definition 1.

A timing graph G is a directed graph having exactly one source and one sink node: G={N,E,ns,nf}, where N={n 1 ,n 2 ,...,n k } is a set of nodes, E={e 1 ,e 2 ,...,e l } is a set of edges, is the source node, and is the sink node and each edge is simply an ordered pair of nodes e=(n i ,n j ).

The nodes in the timing graph correspond to nets in the circuit, and the edges in the graph correspond to connections from gate inputs to gate outputs.

Delay Model

We use a simple delay model for our experiments, similar to that used in [START_REF] Hashimoto | Increase in delay uncertainty by performance optimization[END_REF], based on the logic effort model. In this model, the pinto-pin delay (edge delay) of a gate is defined as

, ( E Q 1 )
where, D int is a constant, intrinsic delay due to cell-internal capacitances, C load is the total load capacitance, K is a constant for the standard cell and C cell is the total capacitance of the standard cell.

We determine these constants for all the standard cells in our synthesis library for our experiments. For the statistical modeling of these delays we assume that the standard deviation is a fixed percentage of the nominal delay, although our method is not restricted to this model.

Proposed Optimization Approach

We first present in Section 3.1 the straightforward approach to performing statistical optimization using sensitivities. In Section 3.2, we develop novel properties of sensitivity propagation based on which an efficient pruning algorithm is presented in Section 3.3.

Straightforward Approach

Our brute force statistical algorithm is similar in structure to a deterministic coordinate descent algorithm. The deterministic optimization is sensitivity based and iteratively minimizes the circuit delay starting from a minimum size implementation. During each iteration, the gate with the maximum sensitivity is identified and sized up. If the optimization is deterministic in nature, any gate that improves the circuit delay by being sized up, must lie on the critical path of the circuit and hence, the sensitivity computation can be restricted to only those gates on the critical path.

However, in optimizing statistical circuit delay, there may be no single longest path, because the circuit delay PDF is a combination of all the path delay PDFs. Hence, statistical sensitivity needs to be

∈ nf N ∈ e E ∈ D e D int K C load C cell ⁄ × + =
computed for all gates in the circuit making a sensitivity based statistical optimization significantly more computationally demanding. According to the objective function defined in Section 2, the statistical sensitivity is the change in the p-percentile point of the circuit delay CDF due to the upsizing of a gate. This means that the perturbation of sizing a gate must be propagated to the sink node in order to calculate the sensitivity of the gate. This necessitates a statistical timing analysis run for each gate in the circuit at every sizing step of the algorithm with a runtime complexity of O(N*E) for every sizing iteration, where N is the number of nodes and E is the number of edges of graph G. This results in unacceptable runtimes. Therefore, we propose an approach where the gate with maximum sensitivity can be identified without explicit propagation of perturbed arrival time CDFs for each gate.

Properties of sensitivity propagation

To allow for pruning of sensitivities, we now introduce the following useful definitions and properties of sensitivity propagation.

As shown in Figure 5, A i is the CDF of the arrival time random variable at node i and A' i is the corresponding perturbed CDF obtained by scaling up a gate. Their PDFs are denoted by a i and a' i , respectively. We define the difference in the p-percentile point of the CDFs A i and A' i as . The maximum difference over all p is given by .

First, we assume that the perturbed CDF A' i has the exact same shape as the unperturbed CDF A i and differs from A i only by a constant shift in time, i.e. A i (t) = A' i (t -∆ i ) and also a i (t) = a' i (t -∆ i ). This is assumed to be true for all perturbed CDFs. Under this assumption, we prove in Theorems 1 through 3 that the maximum difference ∆ i between the perturbed and unperturbed CDFs at a node can not increase as the perturbed CDFs are propagated through the circuit using convolution and statistical maximum. This property is useful in bounding the difference between the perturbed and unperturbed CDFs at the sink node, without complete propagation of the gate's perturbed CDF to the sink node. However, a change in a gate size often affects not only the mean of the gate delay, but also the shape of the CDF. Therefore, we show that it is possible to construct a lower bound on the perturbed CDF, such that the shape of this lower bound is identical to the unperturbed CDF, as illustrated by CDF B' i in Figure 5. We then apply Theorems 1 through 3 to this lower bound on the perturbed CDF and show that these theorems are true for any shape perturbation. Finally, we show the use of these theorems to effectively prune out the propagation of perturbed CDFs.

Theorem 1. Convolution operation:

Consider the timing graph shown in Figure 3a. Let a i and a' i be the original and the perturbed PDF at node i such that a i (t) = a' i (t -∆ i ) and let d e be the delay PDF of edge e. If the arrival time PDF a j and the perturbed a' j at node j are given by a j = Conv(a i , d e ) and a' j = Conv(a' i , d e ) , then ∆ i = ∆ j . Proof : The proof is obvious and omitted for brevity.

In the following two theorems, we show that a similar property to that of Theorem 1 holds for the maximum operation. As previously mentioned, we assume that correlation of the arrival times due to reconvergent fanout can be ignored for the maximum operation and hence, the theorems are defined for an upper bound of the exact arrival time CDF [START_REF] Agarwal | Computation and Refinement of Statistical Bounds on Circuit Delay[END_REF].

Theorem 2. Max operation with multiple perturbed arrival times: Consider a node i in the probabilistic timing graph shown in Figure 3b. Let A i1 and A i2 be the arrival time CDFs of two fanin subgraphs incident at node i. Let A' i1 and A' i2 be the perturbed CDFs obtained by scaling a single gate x that is common to the fanin cones of A i1 and A i2 . If the arrival time CDF A i and perturbed CDF A' i at node i are given by, A i = max(A i1 , A i2 ) and

A' i = max(A' i1 , A' i2 ) respectively, then .
Proof : We consider two cases. case 1:

Consider ∆ i1 = ∆ i2 .
By definition of maximum operation assuming independence, (EQ 2) and (EQ 3) R.H.S. of EQ2 and EQ3 being same,

A i (t) = A' i (t -∆ i1 ), but we know that A i (t) = A' i (t -∆ i ). Hence, ∆ i = ∆ i1 = ∆ i2 .
case 2: Consider .

Without loss of generality, assume ∆ i1 > ∆ i2 , and also ∆ i1 = ∆ i2(case1) and ∆ i2 < ∆ i2(case1) as shown in Figure 4. We define a new CDF due to ∆ i2 as A'' i2 , and the new resultant max as A'' i . Again by definition, (EQ 4)

Also, A'' i2 (t -∆ i1 ) < A' i2 (t -∆ i1 ), because ∆ i2 < ∆ i2(case1)
. Hence, by equating EQ3 and EQ4, we get A'' i (t -∆ i1 ) < A' i (t -∆ i1 ). This implies, , and by algebraic manipulation. Hence, .

Note that the proof can be trivially extended for gates with more than two inputs. Proof : This is a special case of Theorem 2, where ∆ i2 = 0. The above three theorems were defined assuming that the perturbed CDF has the exact same shape as the unperturbed CDF. As mentioned, this may not be true in practice and hence, we define a

δ i p ( ) T A i p , ( ) T A' i p , ( ) - = ∆ i max p δ i p ( ) = Figure 3. Timing graphs i j a ' i , a i a ' j , a j A ' i1 , A i1 A i2 A ' i , A i i (a) (c) d e A ' i1 , A i1 A ' i2 , A i2 A ' i , A i i (b) x ∆ i max ∆ i1 ∆ i2 , ( ) ≤ A i t ( ) A i1 t ( ) A i2 t ( ) ⋅ = A' i t ∆ i1 - ( ) A' i1 t ∆ i1 - ( ) A' i2 t ∆ i1 - ( ) ⋅ = ∆ i1 ∆ i2 ≠ A'' i t ∆ i1 - ( ) A' i1 t ∆ i1 - ( ) A'' i2 t ∆ i1 - ( ) ⋅ = T A'' i p , ( ) T A' i p , ( ) > T A i p , ( ) T -A'' i p , (
)

T A i p , ( ) T -A' i p , ( ) < ∆ i ∆ i1 <
A ' i1 A i1 A i2 A i A ' i2 A ' i A '' i A '' i2 ∆ i1 ∆ i2 case1 ( ) ∆ i2 ∆ i ∆ i1 ∆ i2 case1 ( ) = ∆ i1 ∆ i ∆ i1 ≤
lower bound on the perturbed CDF which has the exact same shape as the unperturbed CDF as follows. Definition 2. The lower bound CDF B' i of perturbed arrival time A' i is defined as the time shifted CDF A i by ∆ i (Figure 5).

Since the shape of the lower bound B' i is the same as that of the unperturbed CDF A i , Theorems 1 through 3 can be applied to this lower bound. Note, however, that the maximum time difference between the lower bound of the perturbed CDF B' i and the unperturbed CDF A i is equal to the maximum difference between the perturbed CDF A' i itself, and A i (by Definition 2). Hence, implicitly, Theorems 1 through 3 also hold for arbitrary shaped perturbations of an arrival time CDF. This allows the use of the perturbation bound ∆ i as an upper bound on the actual difference between the perturbed and unperturbed CDFs at the sink node. Using this bound allows gates to be pruned from consideration for the highest sensitivity gate as explained in more detail in Section 3.3.

Before presenting such a general upper bound on the perturbation of a CDF at the sink node, we first recognize that when we propagate a perturbed CDF in a circuit, multiple perturbed CDFs are generated at points of multiple fanout. We therefore introduce a so-called perturbation front, P k , which is the set of nodes that is visited in each iteration of a breadth-first propagation of the perturbed CDF to the sink node. We now define the maximum over all ∆ i where node i belongs to a perturbation front due to upsizing gate x as ∆m x = max i ∆ i . Note that when the perturbation front reaches the sink node, it consists of only a single perturbed arrival time corresponding to the sink node.

Theorem 4. Given a perturbation front P k associated with a gate

x then , where is the maximum difference between perturbed and unperturbed arrival times over all nodes in the perturbation front P k and ∆ nf is the maximum difference between perturbed and unperturbed CDF at the sink node nf.

Proof : The proof follows from Theorems 1 through 3.

Theorem 4 states that the maximum difference between the perturbed and unperturbed CDF at the sink node, is bounded by the maximum change of the perturbed and unperturbed CDFs in the perturbation front.

Our Algorithm

In this section, our statistical gate sizing algorithm is presented. The objective function is the p-percentile point of the circuit delay CDF. The sensitivity S x of gate x is computed numerically using the ratio of the change in p-percentile circuit delay per unit change in gate width:

where, is the change in gate width and nf is the sink node of G. Based on the computed sensitivities, the most sensitive gate in each iteration of the coordinate descent is selected.

The goal of the inner loop of the optimization is to find the gate with maximum sensitivity without performing a complete SSTA run for each gate perturbation in the circuit. The idea is to propagate highly sensitive gates (i.e. gates which have a large value of S i ) to the sink node and then use their S i value to prune out gates which can be shown to have a lesser sensitivity using the proposed bounds. Given a gate x with partially propagated arrival time CDFs at perturbation front P k , we define the perturbation front sensitivity bound , where is the maximum perturbation change across the nodes of the front. From Theorem 4 it follows that Sm x < S x and hence the sensitivity bound Sm x can be used to prune gate x before its perturbation front reaches the sink node. In other words, if at any time during the propagation of the front for gate x the bound Sm x become less than a previously computed sensitivity S i of gate i, gate x can be eliminated from further consideration.

It is advantageous to identify a gate with a high sensitivity value S i early in the analysis so that a large number of gates can be pruned. In our approach, we therefore perform level by level propagation of perturbed arrival times in an iterative manner. During every iteration the perturbation front with the maximum Sm x value is propagated one level forward and its Sm x value is recomputed. When a perturbation front reaches the sink node, its true sensitivity S i is computed and is used to prune the perturbation front of other gates. The pseudo-code of the statistical gate sizing algorithm is given in Figure 6.

First, SSTA is performed to compute the arrival times at each node (step 2). To implement level by level propagation, we maintain propagated arrival times A' and Sm x for each candidate gate and use the notation 'x.A'set' which represents the super-set of gates in the current perturbation front of gate x. It is a super-set as it also contains the fanout gates of the current perturbation front, which is required to advance the perturbation front one level forward. Sm x and A'set are initialized for every gate in the circuit by calling procedure Initialize (step 3 and 4). In step 5, a sorted list of all gates in G is created by arranging gates in descending order of Sm x . It repre-

A ' i A i p B ' i ∆ i

Figure 5. Arrival time CDFs at node i

Perturbed CDF Lower Bound

Unperturbed CDF delay

∆ nf ∆m x ≤ ∆ m x S x δ nf p ( ) w x ∆ ⁄ = w x ∆ Sm x ∆m x w x ∆ ⁄ = ∆m x Statistical_Gate_Sizing(G) 1. do { 2. SSTA(G); 3.
For each gate x 4.

x.A'set = Initialize(x); 5.

gate_list = list of all gates x in G sorted by Sm x 6. Max_S = 0; 7.

while( gate_list is not empty) { 8.

x = Head(List); 9.

PropagateOneLevel(x); sents the list of all unpruned candidates which may or may not result in maximum S x , i.e. the set of all gates having Sm x > Max_S, where Max_S is the maximum S x amongst all candidate nodes whose perturbation front have reached the sink node. Max_S is initialized to be '0' (step 6) before beginning the search for the most sensitive gate.

In each iteration, the head of the sorted gate_list is selected for propagation. The procedure PropagateOneLevel propagates the arrival times by one level and updates the A'set of gate x accordingly, as explained later. During propagation, new nodes are added to A'set and nodes which do not belong to the perturbation front are deleted. Sm x is re-computed in step 10. If perturbation front of gate x reaches the sink node, gate x is removed from the candidate gate_list (step 11 and 12) and Max_S is updated (step 13-17). On the other hand, if the perturbation front has not yet reached the sink node, the position of gate x in the sorted gate_list is updated with respect to its new Sm x (step 19). In Step 20, gates in the list for which Sm x < Max_S are removed from the list. When the candidate gate_list becomes empty the propagation loop terminates and the gate with maximum sensitivity is sized up by ∆w. The algorithm can be easily modified to size multiple gates in the same iteration.

The pseudocode for procedure Initialize is given in Figure 7.

Given a gate x, the algorithm initializes the perturbation front A'set and computes the initial value Sm x for gate x. The width w of gate x is temporarily sized up by ∆w and the CDF for all pin-to-pin delays of gate x are updated. In addition, the delay CDFs of fanin gates that drive the inputs of gate x are also updated due to the increased loading by gate x (step 1). Consequently, the arrival time CDFs at gate x and its fanins will be perturbed hence, these nodes are added to the initial perturbation front (step 2). In general, it is possible that the fanin of x is also a fanin of other fanins of x. Therefore, perturbed arrival times are computed starting from the minimum level gate (step 3). The procedure PropagateOneLevel is called iteratively until the propagation level reaches the level of gate x (step 4 and 5). The perturbation front created after step 5 is shown in Figure 8. Thereafter, Sm x is computed in step 6. Finally, the original pin-topin delays of gate x and its fanin gates are restored (step 7).

The pseudocode for procedure PropagateOneLevel is given in Figure 9. In step 1-4, a list of gates at the propagation level is created from the A'set of x. For every node in the list, the perturbed arrival time distribution AT_PDF, is computed by performing convolution and max operations (step 6). Then ∆ i is computed by comparing the propagated perturbed arrival time and the original arrival time (i.e. the arrival time computed in step 2). For each node in prop_list, fanout nodes are added to the A'set in steps 8-12. Note that a node can be removed from the A'set once the perturbed arrival times at all its fanouts are computed. This is performed using a count variable fo_count which is initialized to the number of fanouts of the gate (step 11). When a perturbed arrival time is propagated from a node, fo_count of all fanin gates is decremented. A node is removed from A'set when its fo_count becomes zero.

Results

The proposed statistical optimization method was implemented and tested on a synthesized version of ISCAS'85 [START_REF] Brglez | A Neutral Netlist of 10 Combinatorial Benchmark Circuits[END_REF] benchmark circuits using a 180nm commercial cell library. We compare our proposed approach with deterministic and brute-force statistical optimization methods. Intra-die process variation was modeled using a truncated Gaussian gate delay distribution. The standard deviation was 10% of the nominal delay and the distribution was truncated at the 3 sigma point. However, any delay distribution could be used in our framework. As shown later, the arrival time bounds as suggested in [START_REF] Agarwal | Computation and Refinement of Statistical Bounds on Circuit Delay[END_REF] were compared with Monte Carlo simulation, showing an acceptable difference, especially for the 99-percentile point (< 1%).

The deterministic optimization that we use for comparison is similar to a coordinate descent algorithm. Sensitivities are computed for all the gates on the critical path and the gate with the highest sensitivity is sized up. These sensitivities are computed as the change in the circuit delay due to a change in the gate size. The brute force statistical optimization, on the other hand, computes statistical sensitivities exactly by performing an SSTA run for every candidate gate.

Table 1 shows a comparison between the proposed statistical optimization and deterministic optimization. Results have not been shown for the brute force approach as they match exactly with the proposed optimization algorithm. The optimization results for the 99-percentile circuit delay point, after performing over 1000 sizing iterations, is shown in column 3-6. Note that while the deterministic optimization does not use SSTA in the optimization process, the reported 99-percentile delay point was obtained by running SSTA on the circuit solution after every sizing iteration. In column 3, we report the % increase in the total gate size of the circuit due to optimization. Column 4 and 5 show the 99-percentile delay obtained from deterministic and statistical optimization, respectively. The improvement obtained from statistical optimization over deterministic optimization is shown in column 6. The average improvement is 7.8% over all benchmarks with a maximum improvement of 10.5%.

Table 2 shows a comparison of runtimes between brute force statistical optimization and our accelerated approach. Our optimization results are identical with those of the brute force approach, but provide a runtime improvement of up to 56x for large circuits. The results demonstrate that as many as 55 out of 56 candidate nodes are pruned, demonstrating the effectiveness of the proposed bounds and pruning algorithm. We also found that the runtime per iteration varies significantly over the optimization iterations. In certain cases, there is a large range of gate sensitivities, and a highly sensitive gate quickly prunes out many inferior gates, whereas in other cases, many gates in the circuit have similar sensitivities, making pruning more difficult. Note that in the latter case, exact identification of the most sensitive gate will not be as important for the optimization result, opening the way for future research on fast heuristics for finding the most sensitive gate. In column 2 and 3, we report the average runtime per iteration (computed over a 1000 iterations) using the brute force and our accelerated approach, respectively. column 4 shows the runtime improvement factor. The improvement is higher for larger circuits, since in these circuits the cost of maintaining additional data structures is amortized over the savings of statistical computations, such as convolution and max. Finally, columns 5 and 6, show the range of runtimes per iteration for our approach and corresponding range of improvement factors, respectively.

Figure 10 shows the area-delay curve using our approach and deterministic optimization for c3540. The 99-percentile points of the circuit delay CDF are plotted on the x-axis and the corresponding total gate size value on the y-axis, for every sizing iteration. We have also plotted the 99-percentile points of the circuit delay using Monte Carlo simulations. As shown in the figure, there is a very small difference between the bounds and Monte Carlo results. Thus, using bounds as an optimization objective results in a comparable improvement in the exact circuit delay.

Conclusions

In this paper, we have demonstrated the need for a fast statistical optimization algorithm. We have shown through our experiments that there is a clear advantage in using statistical optimization com-pared to a deterministic one. We proposed a fast statistical optimization which is exact in comparison with a brute force statistical optimization but provides significant speedup. Our approach is based on proposed theory of perturbation bounds which allow efficient identification of the highest sensitive gate for sizing. The perturbation bound is used in pruning out less sensitive gates without explicitly propagating their effect, and is a key contribution of this paper. Finally, we demonstrated the accuracy and efficiency of our approach over a large number of test cases. Our results show a maximum runtime improvement by a factor of 56. Future work includes development of heuristics for fast and approximate identification of the statistically most sensitive gate in the circuit.

  Figure 1(a) and (b), where a balanced and unbalanced path distribu-tions are shown with their associated circuit delay distributions.

Figure 1 .

 1 Figure 1. a) distribution of paths in a circuit b) corresponding circuit delay PDFs

Figure 2 .

 2 Figure 2. Optimization objective (99-percentile delay point)

Theorem 3 .

 3 Max operation with single perturbed arrival time: Consider a node i in the timing graph shown in Figure3c. Let A i1 and A i2 be the arrival time CDFs of two fanin subgraphs incident at node i. Let A' i1 be the only perturbed CDF. If the arrival time CDF A i and perturbed CDF A' i at node i are given by, A i = max(A i1 , A i2 ) and A' i = max(A' i1 , A i2 ) respectively, then .

Figure 4 .

 4 Figure 4. Arrival time CDFs -max operation (case 2)

Figure 7 .Figure 8 .

 78 Figure 7. Initialize creates a perturbation front for gate x

Table 1 . Results for the 99-percentile delay point

 1

	Circuit	Results for the 99-percentile delay pt. (ns)
	name node/edge	% inc.	deterministic statistical %impr.
	c432 214/379	97	3.49	3.14	10.03
	c499 561/978	25.6	3.98	3.56	10.55
	c880 425/804	93	4.09	3.74	8.55
	c1355 570/1071	23.7	4.80	4.30	10.41
	c1908 466/858	20.9	6.48	6.12	5.50
	c2670 1059/1731	21.4	3.65	3.40	6.85
	c3540 991/1972	11.5	5.98	5.70	5.0
	c5315 1806/3311	6.7	5.90	5.40	8.47
	c6288 2503/4999	28.1	16.00	15.05	5.93
	c7552 2202/3945	13.1	8.10	7.60	6.17

Table 2 . Results for the runtime improvement

 2

	Circuit	Average time per iteration (sec) Range of time	Range of
	name	brute force our algo. imp. factor	per iteration(s)	impr. factor
	c432	5		1.35	3.7		0.72-1.81		3-7
	c499	90		22.4	4.01			5-30		3-18
	c880	15		4.0		3.75			1.5-5		3-10
	c1355	95		23		4.13			9-31		3-11
	c1908	102		25		4.08			10-36		3-10
	c2670	43		5.0		8.6		1.6-7.0		6-27
	c3540	194		28		6.9			6-35		6-32
	c5315	403		40		10.07		16-55		7-25
	c6288	3600	248		14.5		64-310		12-56
	c7552	1190	114		10.4		34-150		8-35
		9
							Determinstic Optimization
		8.8					( 99% pt. using bounds)
							( 99% pt. using Monte Carlo)
	total gate size	8.4 8.6
			Statistical
		8.2	Optimization
			( 99% pt. bounds)
		8	( 99% pt. Monte Carlo)
		7.8	5.6	5.8	6.0	6.2	6.4	6.6	6.8	7.0	7.2	7.4	7.6
								delay (ns)
				Figure 10. Area-delay curve for c3540

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

Acknowledgements

This research was supported by SRC contract 2001-HJ-959 and NSF grant CCR-0205227.


Maxim Teslenko

Elena Dubrova

An Efficient Algorithm for Finding Double-Vertex Dominators in Circuit Graphs

Graph dominators provide a general mechanism for identifying re-converging paths in circuits. This is useful in a number of CAD applications including computation of signal probabilities for test generation, switching activities for power and noise analysis, statistical timing analysis, cut point selection in equivalence checking, etc. Single-vertex dominators are too rare in circuit graphs to handle re-converging paths in a practical way. This paper addresses the problem of finding double-vertex dominators, which occur more frequently. First, we introduce a data structure, called dominator chain, which allows representing all possible O(n 2 ) double-vertex dominators of a given vertex in O(n) space, where n is the number of vertices of the circuit graph. Dominator chains can be efficiently manipulated, e.g. it takes constant time to look-up whether a given pair of vertices is a double-vertex dominator. Second, we present an efficient algorithm for finding double-vertex dominators. The experimental results show that the presented algorithm is an order of magnitude faster than existing algorithms for finding double-vertex dominators. Thus, it is suitable for running in an incremental manner during logic synthesis.

Introduction

This paper considers the problem of finding dominators in circuit graphs. A vertex v is said to dominate another vertex u if every path from u to the output of the circuit contains v [START_REF] Lengauer | A fast algorithm for finding dominators in a flowgraph[END_REF]. For example, in the circuit graph in Figure 1, vertex n dominates vertex e; vertex p dominates vertex h. Dominators provide a general mechanism for identifying reconverging paths in circuits. If a vertex v is the origin of a reconverging path, then the immediate dominator of v is the earliest point at which such a path converges. For example, in Figure 1, the re-converging path originated at e ends at n; the re-converging path originated at g ends at f . Knowing the precise starting and ending points of a reconverging path is useful in a number of applications including computation of signal probabilities for test generation, switching activities for power and noise analysis, statistical timing analysis, cut point selection in equivalence checking, etc.

The signal probability of a net in a combinational circuit is the probability that a randomly generated input vector will produce the value one on this net [START_REF] Parker | Probabilistic treatment of general combinational networks[END_REF]. Efficient signal probability analysis allows to improve the coverage of test generation for biased random simulation. The average switching activity in a combinational circuit is the probability of its net values to change from 0 to 1 or vice versa. It correlates directly with the average power dissipation of the circuit [START_REF] Najm | Transition density: A new measure of activity in digital circuits[END_REF], thus its analysis is useful for guiding logic optimization methods targeting low power.

Computation of signal probabilities and switching activities based on topologically processing the circuit from inputs to outputs and evaluating the gate functions generally produces incorrect results due to higher-order exponents introduced by correlated signals. For example, if the functions f and g have variables in common, then P[ f ∧ g] = P[ f ] • P[g], where P is the signal probability. Dominators provide the earliest points during topological processing at which the re-converging paths meet and thus the signals cease to be correlated. Therefore, the computation of signal probabilities and switching activities can be efficiently partitioned along the dominator points [START_REF] Krenz | Fast algorithm for computing spectral transforms of Boolean and multiple-valued functions on circuit representation[END_REF][START_REF] Seth | PREDICT-probabilistic estimation of digital circuit testability[END_REF][START_REF] Costa | Switching activity estimation using limited depth reconvergent path analysis[END_REF]. At the origin of a reconverging path, v, an auxiliary variable is introduced. At the end of the path, the immediate dominator of v, this variable is eliminated. As a result, the computation is carried out using a minimum set of variables.

Single-vertex dominators can be found in time linear in the number of vertices of the graph [START_REF] Harrel | A linear time algorithm for finding dominators in flow graphs and related problems[END_REF][START_REF] Alstrup | Dominators in linear time[END_REF][START_REF] Buchsbaum | A new, simpler linear-time dominators algorithm[END_REF]. However, they are quite rare in circuits. It is more common that a vertex is dominated by a set of vertices. For example, in Figure 1, primary input b is dominated by the set {e, h}. To be able to deal with re-converging paths in a practical way, an efficient algorithm for computing multipledominators of a small size is needed. Small size is important because usually 2 k combinations of values of a k-vertex dominator have to be manipulated [START_REF] Krenz | Fast algorithm for computing spectral transforms of Boolean and multiple-valued functions on circuit representation[END_REF].

General algorithms for finding multiple-vertex dominators have exponential worst case complexity [START_REF] Gupta | Generalized dominators and post-dominators[END_REF]. Multiple-vertex dominators of a fixed size k can be computed in O(n k ) time, where n is the number of vertices of the circuit graph [START_REF] Dubrova | On relation between non-disjoint decomposition and multiple-vertex dominators[END_REF]. This paper presents an algorithm for finding double-vertex dominators (k = 2), which is significantly faster than the algorithm [START_REF] Dubrova | On relation between non-disjoint decomposition and multiple-vertex dominators[END_REF]. The efficiency of our algorithm is due to a number of interesting properties of double-vertex dominators. The most important one is that the set of all possible double-vertex dominators of a given vertex can be represented by a unique dominator chain of linear size which can be looked-up in constant time.

Being able to efficiently represent and manipulate all doublevertex dominators for a given vertex is important, because it makes the computation of common dominators easy. As we show in the paper, double-vertex dominators for a set of vertices can be derived from the dominator chains of individual vertices.

The paper is organized as follows. Section 2 presents the notation. Section 3 summarizes the previous work. Sections 4 and 5 introduce the new data structure and the dominator algorithm, respectively. The experimental results are shown in Section 6.

Properties of Dominators

Let C = (V, E, root) denote a single-output directed acyclic circuit graph, where V represents the set of gates and primary inputs and E ⊆ V ×V describes the nets connecting the gates. A particular vertex root ∈ V is marked as the circuit output.

A vertex v dominates another vertex u if every path from u to the root contains v [START_REF] Lengauer | A fast algorithm for finding dominators in a flowgraph[END_REF]. Vertex v is the immediate dominator of u, if v dominates u and every other dominator of u dominates v. For example, in Figure 1, vertex n is the immediate dominator of j, e and k; vertex f is the immediate dominator of n and p. Every vertex v ∈ V except root has a unique immediate dominator, idom(v) [START_REF] Lowry | Object code optimization[END_REF]. The edges {(idom(v), v) | v ∈ V -{root}} form a directed tree T (C) rooted at root, called the dominator tree of C. Figure 1(b) shows the dominator tree for the circuit in Figure 1(a). Dominators provide a general mechanism for identifying reconverging paths in circuit graphs. Every edge of the dominator tree (idom(v), v) ∈ T (C) represents the starting and the ending points of a path. If the fanout degree of v, Fanout(v) = {u |(v, u) ∈ E}, is one, then the re-converging path is trivial (i.e. an edge). Otherwise, vertex v is the origin of a re-converging path and vertex idom(v) is the earliest point at which such a path converges. For example, in Figure 1(a), the re-converging path originated at e ends at idom(e) = n; the re-converging path originated at b ends at idom(b) = f . Many graphs do not have any single-vertex dominators except root. It is more common that a vertex is dominated by a set of vertices. Below we give a general definition for a set of vertices being dominated by another set. When the sizes of both sets are one, this definition reduces to the above mentioned definition from [START_REF] Lengauer | A fast algorithm for finding dominators in a flowgraph[END_REF].

Definition 1 A set of vertices {v 1 ,...,v k } is a common multiple- vertex dominator of size k for a set of vertices {u 1 ,...,u l } ⊂ V - {v 1 ,...,v k }, if
1. every path from any u j , p ∈ {1,...,l}, to root contains some v i , i ∈ {1,...,k} 2. for every v i , there exists at least one path from some u p , p ∈ {1,... ,l}, to root which contains v i and does not contain any other v j , i, j ∈ {1,... ,k}, i = j.

In the paper, we omit the word "common" when l = 1, i.e. when a set dominates a single vertex.

The second condition of the Definition 1 is needed to remove redundancies. For example, in Figure 1(a), all paths from e to f pass through the set of vertices { j, n}. However, vertex j is redundant, because n is a single-vertex dominator of e.

Note, that the notion of dominator is more general than the notion of min-cut in circuit partitioning [START_REF] Kernighan | An efficient heuristic procedure for partitioning of electrical circuits[END_REF]. A min-cut is required to dominate all vertices in its transitive fanin.

A number of properties are specific for multiple-vertex dominators. First, in single-vertex case, any vertex v ∈ V -{root} is dominated by at least one vertex, root. Multiple-vertex dominators may not exist for some vertices. For example, a tree-like circuit does not have any multiple-vertex dominators. In a tree structure the condition (2) of the Definition 1 is not satisfied for any subset {v 1 ,...,v k }, k > 1, since the individual vertices v i , i ∈ {1,... ,k}, dominate all vertices in their transitive fanins.

Second, the immediate k-vertex dominators are not unique for k > 2. We define immediate k-vertex dominators as follows.

Definition 2 The set W = {v 1 ,...,v k } in an immediate common k- vertex dominator of {u 1 ,...,u l }, if W is a common k-vertex domi- nator of {u 1 ,...,u l }
and there is no other common k-vertex dominator of {u 1 ,...,u l }, W , such that each vertex of W is either dominated by W or belongs to W .

Previous Work

The problem of finding single-vertex dominators was first considered in global flow analysis and program optimization. Lorry and Medlock [START_REF] Lowry | Object code optimization[END_REF] presented an O(n 4 ) algorithm for finding all immediate single-vertex dominators in a flowgraph with n vertices. Successive improvements of this algorithm were done by Aho and Ullman [START_REF] Aho | The Theory of Parsing, Translating, and Compiling[END_REF], Purdom and Moore [START_REF] Purdom | Immediate predominators in a directed graph[END_REF], and Tarjan [START_REF] Tarjan | Finding dominators in a directed graphs[END_REF], culminating in Lengauer and Tarjan's [START_REF] Lengauer | A fast algorithm for finding dominators in a flowgraph[END_REF] O(eα(e, n)) algorithm, where e is the number of edges and α is the standard functional inverse of the Ackermann function which grows slowly with e and n.

The asymptotic time complexity of finding single-vertex dominators was reduced to linear by Harel [START_REF] Harrel | A linear time algorithm for finding dominators in flow graphs and related problems[END_REF], Alstrup et al. [START_REF] Alstrup | Dominators in linear time[END_REF] and Buchsbaum et al. [START_REF] Buchsbaum | A new, simpler linear-time dominators algorithm[END_REF]. However, these improvements in asymptotic complexity did not contribute much to reducing the actual runtime. For example, the algorithm [START_REF] Buchsbaum | A new, simpler linear-time dominators algorithm[END_REF] runs 10% to 20% slower than Lengauer and Tarjan's [START_REF] Lengauer | A fast algorithm for finding dominators in a flowgraph[END_REF]. Lengauer and Tarjan algorithm appears to be the fastest of algorithms for single-vertex dominators on graphs of large size.

While it is possible to compute all single-vertex dominators in linear time, algorithms for finding all multiple-vertex dominators for a directed graph have exponential worst case complexity [START_REF] Gupta | Generalized dominators and post-dominators[END_REF]. In [START_REF] Dubrova | On relation between non-disjoint decomposition and multiple-vertex dominators[END_REF], it was shown that it is possible to compute multiple-vertex dominators of a fixed size k in polynomial time. The algorithm presented in [START_REF] Dubrova | On relation between non-disjoint decomposition and multiple-vertex dominators[END_REF] finds the set of all possible kvertex dominators for a circuit graph C = (V, E, root) by iteratively restricting C with respect to one of its vertices, v ∈ V . The restriction is done by removing from V all vertices dominated by v, S(v). Dominators of size k -1 are computed for the resulting restricted graph C = (V , E , root), with V = V -S(v) and

E = E -{(u, w)|u ∈ S(v) ∨ w ∈ S(v)},
by applying the same technique recursively. Once k is reduced to 1, a single-vertex dominator algorithm is used. Since single-vertex dominators can be computed in linear time, the overall complexity of the algorithm [START_REF] Dubrova | On relation between non-disjoint decomposition and multiple-vertex dominators[END_REF] is bounded by O(|V | k ).

Dominator Chain

In this section, we introduce a data structure called dominator chain which allows representing all possible O(|V | 2 ) doublevertex dominators of a given vertex in O(|V |) space.

Definition 3 For any u ∈ V , the dominator chain D(u) is a vector of type

{V 11 ,V 21 }, {V 12 ,V 22 },...,{V 1m ,V 2m } whose elements V i j , i ∈ {1, 2}, j ∈ {1,... ,m}, 0 ≤ m < |V |/2
, are vectors of vertices of V . Every pair {V 1 j ,V 2 j } satisfies the following properties:

1. For every v ∈ V i j , there exists a matching vector W = w 1 ,...,w s , which is a sub-vector (i.e. linear interval) of

V k j , k ∈ {1, 2}, k = i, such that
• for all r ∈ {1,... ,s}, {v, w r } is a double-vertex dominator of u;

• no other pair of vertices {v, v }, v ∈ V -W , is a doublevertex dominator of u;

• the order of the elements of the matching vector W is given by: if {v, w r } is a double-vertex dominator of w t , then t < r, for all r,t ∈ {1,... ,s}, r = t.

2. The immediate double-vertex dominator of u is the first elements of V 11 and V 21 . For all j ∈ {2,...,m}, the immediate common double-vertex dominator of the last elements of V 1 j-1 and V 2 j-1 is the first elements of V 1 j and V 2 j . There is no common double-vertex dominator of the last elements of V 1m and V 2m .

No pair

{V 1 j ,V 2 j }, ∀ j ∈ {1,... ,m}, can be partitioned into two pairs {V 1 j 1 ,V 2 j 1 } and {V 1 j 2 ,V 2 j 2 }, where V 1 j 1 ∪ V 1 j 2 = V 1 j , V 1 j 1 ∩V 1 j 2 = Ø, V 2 j 1 ∪V 2 j 2 = V 2 j , V 2 j 1 ∩V 2 j 2 = Ø, which
satisfy properties 1 and 2.

As an example, consider the circuit shown in Figure 2. The set of all double-vertex dominators for u is: {a, b}, {a, c}, {a, d}, {e, c}, {e, d}, {h, c}, {h, d}, {h, g}, {k, l}, {m, l}, {k, n}, {m, n}. The dominator chain for u is

{V 11 ,V 21 }, {V 12 ,V 22 } = { a, e, h , b, c, d, g }, { k, m , l, n }
The matching vector W of any vertex v in the dominator chain contains all vertices w such that {v, w} is a double-vertex dominator of u. In Figure 2, the matching vector for vertex a is b, c, d ; the matching vector for d is a, e, h . The first elements of V 11 and V 21 , {a, b}, are the immediate double-vertex dominator of u. The first elements of V 12 and V 22 , {k, l}, are the immediate common double-vertex dominator of the last elements of V 11 and V 21 , {h, g}. The pair {m, n} does not have any common double-vertex dominator.

To prove that the dominator chain contains all possible doublevertex dominators of a vertex, we first show several fundamental properties of double-vertex dominators. Let Dom(u) denote the set of all possible double-vertex dominators of u. The first Lemma says that, if two dominators have a vertex in common, then one of them dominates the non-common vertex of the other one.

Lemma 1 If {v 1 , v 2 } ∈ Dom(u) and {v 2 , v 3 } ∈ Dom(u), then ei- ther {v 1 , v 2 } ∈ Dom(v 3 ) or {v 2 , v 3 } ∈ Dom(v 1 ).
Proof: Suppose v 3 is not dominated by {v 1 , v 2 }. Since {v 2 , v 3 } ∈ Dom(u), there exists a path from u to root, p u→root , which contains v 3 and does not contain v 2 . Since {v 1 , v 2 } ∈ Dom(u), p u→root contains v 1 . Furthermore, v 1 precedes v 3 in p u→root , because, by assumption, {v 1 , v 2 } ∈ Dom(v 3 ) and thus there exists a path p v 3 →root which does not contain neither v 1 nor v 2 .

The part p u→v 1 of the path p u→root does not contain v 2 and v 3 . Each path p v 1 →root contains either v 2 nor v 3 , because otherwise the existence of the path p u→v

1 p v 1 →root would contradict {v 2 , v 3 } ∈ Dom(v 1 ). Thus, by Definition 1, {v 2 , v 3 } ∈ Dom(v 1 ). Similarly we can show that {v 2 , v 3 } ∈ Dom(v 1 ) implies {v 1 , v 2 } ∈ Dom(v 3 ).

2

The second Lemma covers the case of two dominators with no vertices in common.

, v 2 } ∈ Dom(v 3 ) implies that v 1 is a single-vertex dominator of v 3 . Thus, {v 3 , v 4 } ∈ Dom(u) implies that {v 1 , v 4 } ∈ Dom(u). (b) Suppose that v 3 precedes v 2 in p v 2 →v 3 . Then, {v 3 , v 4 } ∈ Dom(v 2 ) implies that v 4 is a single-vertex dominator of v 2 . Thus, {v 1 , v 2 } ∈ Dom(u) implies that {v 1 , v 4 } ∈ Dom(u).
- tor. Since v 2 is common, it should hold that {v 1 , v 2 } ∈ Dom(v 3 ) and {v 2 , v 3 } ∈ Dom(v 1 ). This contradicts Lemma 1, which says that either {v 1 , v 2 } ∈ Dom(v 3 ) or {v 2 , v 3 } ∈ Dom(v 1 )
. case 2: By Lemma 2, either (1) {v 1 , v 2 } dominates both vertices in {v 3 , v 4 } (or vice versa), or (2) there exists two other dominators of u, each having a vertex in common with both {v 1 , v 2 } and {v 3 , v 4 }. In the first case, one of the dominators does not satisfy Definition 2. In the second case, case 1 applies to show that only one of the overlapping dominators can be immediate.

2

Now we give the main result of the paper. The proof is based on Lemmata 1 and 2 and Theorem 1.

Theorem 2

The dominator chain exists for any u ∈ V . It contains all possible double-vertex dominators of u. All pairs {V 1 j ,V 2 j }, j ∈ {1,... ,m}, are uniquely defined. For each i ∈ {1, 2}, the overall number of vertices ∑ m j=1 |V i j | is smaller than the longest path from u to root.

For vertices with no double-vertex dominators, e.g. root, the dominator chain is an empty vector.

The following Lemma shows that different vectors V i j 's of a dominator chain do not intersect.

Lemma 3 Any two distinct vectors V i j and V kl in the dominator chain do not have vertices in common:

V i j ∩V kl = V i j = V k j , if i = k and j = l,

Ø, otherwise

for all i, k ∈ {1, 2}, j, l ∈ {1, 2,... ,m}.

It follows from Lemma 3 that the dominator chain can be represented in an O(|V |) space. To make possible constant-time lookup in the dominator chain D(u), three parameters are assigned to vertices:

• For all v ∈ V : f lag(v) ∈ {1, 2}, distinguishing whether v belongs to V 1 j or to V 2 j . In the example in Figure 2, vertices b, c, d and g belong to V 21 , hence their f lag equals 2.

• For all v ∈ D(u): index(v) ∈ {1, 2,... ,∑ m j=1 |V i j |} indicating the position of v in the vector V i1 ,V i2 ,...,V im , i = f lag(v). By Lemma 3, index(v) is uniquely defined (up to permutation of vectors V 1 j and V 2 j in the pairs {V 1 j ,V 2 j }). In the example in Figure 2 Then, checking whether {v 1 , v 2 } dominates u can be done as follows:

1. Check whether f lag(v 1 ) is not equal to f lag(v 2 ). If yes, go to step 2. Otherwise, {v 1 , v 2 } ∈ D(u).

Check whether min

(v 1 ) ≤ index(v 2 ) ≤ max(v 1 ). If yes, the {v 1 , v 2 } ∈ D(u). Otherwise, {v 1 , v 2 } ∈ D(u).
For example, suppose we check whether {d, h} dominates u in the example in Figure 2

. Vertex d is in V 21 , therefore f lag(d) = 2. Vertex h is in V 11 , i.e. f lag(h) = 1. Since f lag(d) = f lag(h),
we continue to the step 2. We have min(d) = 1, max(d) = 3 and index(h) = 2. Since 1 ≤ 2 ≤ 3 holds, we conclude that {d, h} dominates u.

As another example, let us check whether {g, a} dominates u. On step 1, f lag(g) = 2 and f lag(a) = 1. Since f lag(g) = f lag(a), we continue to the step 2. We have min(g) = max(g) = 3, and index(a) = 1. Since 3 ≤ 1 ≤ 3 does not hold, we conclude that {g, a} does not dominate u.

The problem of computing common double-vertex dominators for a set of vertices u 1 , u 2 ,...,u k can be transformed to the problem of computing double-vertex dominators for a single vertex using the following technique. We add a "fake" vertex u as a predecessor of u 1 , u 2 ,...,u k . Clearly, each {v 1 , v 2 } ∈ D(u) is a common dominator for the set u 1 , u 2 ,...,u k as well. Thus, Definition 3 can be extended to the set of vertices D(u 1 , u 2 ,...,u k ) with a small modification that the first elements of V 11 and V 21 represent the immediate common double-vertex dominator of the set u 1 , u 2 ,...,u k . Similarly, all presented theorems and lemmata can be extended to common double-vertex dominators.

Dominator chain D(u 1 , u 2 ,...,u k ) can be computed directly from the dominator chains of individual vertices

D(u i ) in O(k • min{|D u 1 |, |D u 2 |,...,|D u k |) time, i ∈ {1,...,k}.

Dominator Algorithm

The presented algorithm takes as its input a Boolean circuit C = (V, E, root) and a vertex u ∈ V . It returns the dominator chain D(u). The pseudo-code is shown in Figure 3.

Experimental Results

This section compares the performance of the presented algorithm to the algorithm [START_REF] Dubrova | On relation between non-disjoint decomposition and multiple-vertex dominators[END_REF]. Table 1 summarizes the results for 30 largest benchmarks from IWLS'02 benchmark set. Columns 1, 2 and 3 show the name of the function, the number of primary inputs and primary outputs, respectively. Column 5 shows the total sum of double-vertex dominators which dominate at least one primary input. This number is the same for the presented algorithm and the algorithm [START_REF] Dubrova | On relation between non-disjoint decomposition and multiple-vertex dominators[END_REF], because they both compute all possible double-vertex dominators for a given vertex. For a comparison, we also show in Column 4 the total sum of single-vertex dominators which dominate at least one primary input, computed using Lengauer and Tarjan's algorithm [START_REF] Lengauer | A fast algorithm for finding dominators in a flowgraph[END_REF]. In both cases, common dominators are counted only once. Every output is treated as a separate function. The numbers shown in Columns 4 and 5 are the total sum for all outputs of the circuit.

Columns 7 and 8 show runtime, in seconds, measured using the Unix command time (user time). The experiments were performed on a PC with a 650 MHz Pentium3 CPU and 256 MByte main memory. One can see that, on average, the presented algorithm is 27 times faster than the algorithm [START_REF] Dubrova | On relation between non-disjoint decomposition and multiple-vertex dominators[END_REF]. Some circuits may have less double-vertex dominators than single-vertex ones (C2670, des). Usually these are circuits with many single-vertex dominators. Recall that the definition of multiple-vertex dominator excludes redundancies. Therefore, in the extreme case of a tree-like circuit with n vertices "N single doms" would be n and "N double doms" would 0. No pair of vertices in a tree-like circuit satisfies the Definition 1.

Conclusion

This paper has two main contributions. First, we introduce a data structure for representing double-vertex dominators, which has a linear size and can be efficiently manipulated. Second, we design an algorithm for finding double-vertex dominators, which is, on average, an order of magnitude faster than the algorithm [START_REF] Dubrova | On relation between non-disjoint decomposition and multiple-vertex dominators[END_REF]. The speed of the presented algorithm makes it suitable for running in an incremental manner during logic synthesis.

Future work includes exploring new applications of the presented algorithm, e.g. statistical timing analysis.

Figure 1 :

 1 Figure 1: (a) Example circuit; (b) Its dominator tree.

Figure 1

 1 Figure 1 gives an example. Vertex b has two immediate 3vertex dominators: {e, l, m} and {h, j, k}. In Section 4 we show that immediate k-vertex dominators are unique for k = 2.

Lemma 2 2 :

 22 If {v 1 , v 2 } ∈ Dom(u) and {v 3 , v 4 } ∈ Dom(u), such that at least one of the vertices of {v 1 , v 2 } is not dominated by {v 3 , v 4 } and vice versa, then either {v 1 , v 4 } ∈ Dom(u) and {v 2 , v 3 } ∈ Dom(u) or {v 1 , v 3 } ∈ Dom(u) and {v 2 , v 4 } ∈ Dom(u) Proof: Suppose that {v 3 , v 4 } ∈ Dom(v 1 ) and {v 1 , v 2 } ∈ Dom(v 4 ). Then, there exists a path p v 1 →root which does not contain neither v 3 nor v 4 . Also, there exists a path p v 4 →root which does not contain neither v 1 nor v 2 . Two cases are possible: (1) there is a path p v 1 →v 4 ; (2) there is no such path. case 1: (a) Suppose that v 1 precedes v 4 in p v 1 →v 4 . Then, all paths from u to v 1 contain v 3 , since {v 3 , v 4 } ∈ Dom(u) and p v 1 →root exists. Thus, every path p u→root containing v 1 contains v 3 as well. Since {v 1 , v 2 } ∈ Dom(u), this implies that {v 2 , v 3 } ∈ Dom(u). (b) Suppose that v 4 precedes v 1 in p v 1 →v 4 . Then, all paths p u→v 4 contain v 2 , since {v 1 , v 2 } ∈ Dom(u) and p v 4 →root exists. Thus, every path p u→root containing v 4 contains v 2 as well. Since {v 3 , v 4 } ∈ Dom(u), this implies that {v 2 , v 3 } ∈ Dom(u). case If there is no path p v 1 →v 4 , then, similarly to (a), every path p u→root containing v 1 should contain v 3 as well. Since {v 1 , v 2 } ∈ Dom(u), this implies that {v 2 , v 3 } ∈ Dom(u). Consider vertices v 2 and v 3 . Two cases are possible: (1) there exists a path p v 2 →v 3 , (2) there is no such path. case 1: (a) Suppose that v 2 precedes v 3 in p v 2 →v 3 . Then {v 1

Figure 2 :

 2 Figure 2: Example circuit.

  , index(b) = 1, index(c) = 2, index(l) = 5 and index(n) = 6. • For all v ∈ D(u): a pair (min(v), max(v) = (index(w 1 ), index(w |W | )), where w 1 and w |W | are the first and the last vertices of the matching vector W of v. In the example in Figure 2, (min(b), max(b)) = (1, 1), (min(c), max(c)) = (1, 3), (min(d), max(d)) = (1, 3) and (min(g), max(g)) = (3, 3).

case 2 :

 2 If there is no path p v 2 →v 3 , then, similarly to (a), {v 1 , v 2 } ∈ Dom(v 3 ) implies that v 1 is a single-vertex dominator of v 3 . Thus,{v 3 , v 4 } ∈ Dom(u) implies that {v 1 , v 4 } ∈ Dom(u).2 Next, we prove that immediate double-vertex dominators are unique. As we showed in Section 2, this property does not extend to dominators of larger size. For every vertex u ∈ V , the immediate double-vertex dominator, if it exists, is unique. By contradiction. Suppose u has two immediate doublevertex dominators: {v 1 , v 2 } and {v 3 , v 4 }. Two cases are possible:(1) {v 1 , v 2 } and {v 3 , v 4 } have one common vertex, and (2) {v 1 , v 2 } and {v 3 , v 4 } do not have common vertices. case 1: Suppose v 2 is the common vertex, i.e. the second immediate dominator is {v 2 , v 3 }. By Definition 2, every vertex of an immediate dominator cannot be dominated by any other domina

	Theorem 1 Proof:

Table 1 :

 1 Benchmark results.

				N	N		runtime, sec
				single	double	[11]	new	impr.
	name	in	out	doms	doms	t 1	t 2	t 1 /t 2
	C1355	41	32	6	10512	3.5	0.45	7.78
	C1908	33	25	636	5696	1.5	0.36	4.17
	C2670	233	140	2091	410	1.55	0.23	6.74
	C3540	50	22	727	5657	6.85	0.42	16.31
	C432	36	7	195	2127	0.3	0.17	1.76
	C499	41	32	960	9968	2.3	0.45	5.11
	C5315	178	123	4093	11068	5.5	0.71	7.75
	C6288	32	32	480	3366	58.89	0.88	66.92
	C7552	207	108	4604	14728	7.27	1.16	6.27
	C880	60	26	432	1309	0.26	0.18	1.44
	alu2	10	6	48	55	0.81	0.16	5.06
	alu4	14	8	77	214	3.36	0.16	21.00
	apex5	114	88	800	8107	3.21	0.61	5.26
	apex6	135	99	525	1169	0.42	0.24	1.75
	apex7	49	37	140	476	0.17	0.15	1.13
	cmb	16	4	38	60	0.16	0.09	1.78
	comp	32	3	8	439	0.16	0.12	1.33
	cordic	23	2	38	65	0.12	0.1	1.20
	des	256	245	3361	2349	8.19	0.77	10.63
	frg2	143	139	1502	3609	1.76	0.44	4.00
	i8	133	81	2068	3296	2.87	0.5	5.74
	i9	88	63	876	1827	0.95	0.3	3.17
	i10	257	224	6446	30608	16.32	1.57	10.39
	pair	173	137	2459	9196	1.82	0.63	2.89
	rot	135	107	1657	4617	1.49	0.38	3.92
	term1	34	10	46	453	0.31	0.16	1.94
	too large	38	3	971	1467	423.73	0.69	614.1
	x1	51	35	366	1297	0.99	0.22	4.50
	x3	135	99	495	1801	0.68	0.22	3.09
	x4	94	71	305	2250	0.41	0.18	2.28
	average	95	67	1215	4607	18.5	0.42	27.65

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

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

Acknowledgments

We are grateful to the anonymous reviewer who gave us many valuable comments over the manuscript.

This work was supported in part by the Research Grant 2002-4300 from the Swedish Research Council Vetenskpsrådet.

algorithm DOMINATORCHAIN (V, E, root, u) v = u; k = 1; last index 1 = 0; last index 2 = 0; while 1 do idom(v) = SINGLEIDOM (v,V, E, root); /* defines the end of search region */ S = {v}; while 1 do i = 1; j = 1; V 1k = Ø; V 2k = Ø; {w 1 , w 2 } = DOUBLEIDOM (S,V, E, idom(v)); if {w 1 , w 2 } = Ø then break ; /* w 1 and w 2 become the 1st elements of V 1k and V 2k */ index(w 1 ) = last index 1 + 1; index(w 2 ) = last index 2 + 1; The outer while-loop partitions the circuit graph into regions using single-vertex dominators of u as cut points. Double-vertex dominators of u are searched within these regions.

The immediate double-vertex dominator for a given set S is obtained by DoubleIDom(S,V, E, idom(v)) by computing the maximum flow between the multiple sources defined by S and the sink idom(v). Each vertex in the V except the source and sink vertices is assigned a unit capacity. The source and sink vertices are assigned infinite capacity. The capacity limits the amount of flow through a vertex. According to min-cut maxflow theorem [START_REF] Ford | Maximum flow through a network[END_REF], the maximum possible flow is equal to the capacity of the min-cut disconnecting the source and the sink. In our case, the maximalvolume min-cut of size two corresponds to the immediate doublevector dominator for S. If the size of the cut is larger than two, DOUBLEIDOM returns an empty set.

Maximum flow is computed by constructing augmenting paths from the sources to the sink [START_REF] Ford | Maximum flow through a network[END_REF]. The algorithm repeatedly seeks an augmenting path and uses it to increase the maximum flow. At the same time, the capacitance of all edges involved in the path gets reduced by a unit. The algorithm stops when no such augmenting path exists. Our version of the augmenting path algorithm uses vertex capacitances instead of edge capacitances. Edges are used to direct possible path construction only.

If the double-vertex dominator {w 1 , w 2 } computed by DOUBLEIDOM is not an empty set, then w 1 is added to V 1k and w 2 is added to V 2k as first elements. ADDVECTOR(V ak , a,W, v) modifies V ak to accommodate the matching vector W of v as a part of it. Then, indexes of vertices of V ak are updated by the function UPDATEINDEX(|V ak |,V ak ) (Figure 4). Besides, ADDVECTOR assigns (min(v), max(v)) = (index(w 1 ), index(w |W | )) in V ak , where w 1 and w |W | are the first and the last elements of W , respectively. Further, for all w i , i ∈ {1,...,|W |}, the value a assigned to f lag(w i ), and the values of min(w i ) and max(w i ) are updated as follows:

1. min(w i ) is assigned the minimal of values {min(w i ), index(v)}, 2. max(w i ) is assigned the maximal of values {max(w i ), index(v)}, 3. if min(w i ) and max(w i ) are not defined yet, (min(w i ), max(w i )) are set to (index(v), index(v)).

Next, the dominator chain is updated. UPDATECHAIN applies FINDMATCHINGVECTOR(v,V bk , root) to find the matching vector for v which is ith element of V ak . The resulting vector is added to V bk using ADDVECTOR.

FINDMATCHINGVECTOR(v,V bk , root) works as follows. First, we look-up V bk to find a vertex w with index(w) = min(v). Such a vertex w always exists. This vertex becomes the first element of W . Then, we compute the immediate single-vertex dominator of w for the restricted circuit C = (V , E , root), with V = Vv and E = E -{(y, v)|y ∈ V -{v}}. By restricting the circuit we exclude from consideration all paths from u to root (root is local to FINDMATCHINGVECTOR(v, root)) which contain v. The computed idom(w) together with v is a double-vertex dominator for u, thus idom(w) is appended to the end of W . While-loop continues until the local root is reached.

When the current pair {V 1k ,V 2k } is updated for all vertices, it is added to D(u) as next element. When root is reached, DOMINATORCHAIN terminates by returning the resulting dominator chain D(u) for u.