Panagiotis Manolios

Sudarshan K Srinivasan

Refinement Maps for Efficient Verification of Processor Models *

While most of the effort in improving verification times for pipeline machine verification has focused on faster decision procedures, we show that the refinement maps used also have a drastic impact on verification times. We introduce a new class of refinement maps for pipelined machine verification, and using the state-of-the-art verification tools UCLID and Siege we show that one can attain several orders of magnitude improvements in verification times over the standard flushing-based refinement maps, even enabling the verification of machines that are too complex to otherwise automatically verify.

Introduction

We show that the refinement maps used for pipelined machine verification can have a drastic impact on verification time and therefore should be studied as first-class objects. In this paper, we describe a new class of refinement maps that can provide several orders of magnitude improvements in verification times over the standard flushing-based refinement maps. Our refinement maps are based on flushing and commitment, two well-known refinement maps. The idea with flushing is that partially completed instructions are made to complete without fetching any new instructions. The idea with commitment is that partially completed instructions are invalidated and the programmer visible components are rolled back to correspond with the last committed instruction. Our refinement maps use the commitment approach on the latches at the front of the pipeline and the flushing approach on the latches at the end of the pipeline. This essentially decomposes the verification problem into two smaller problems, each half as complex as the original problem. However, since verification times grow exponentially in the size of the problem, this leads to drastic verification time improvements.

We automatically and efficiently verify the pipelined machines described in this paper by showing that they have exactly the same infinite executions as the machines defined by the corresponding instruction set architectures, up to stuttering. This is accomplished by constructing a WEB-refinement proof, which implies that the pipelined machine satisfies exactly the same CTL * \ X properties satisfied by the instruction set architecture [START_REF] Manolios | Mechanical Verifi cation of Reactive Systems[END_REF]. Thus, we verify both safety and liveness properties of the pipelined machine models we study. Automation is attained by expressing the WEB-refinement proof obligation in the logic of Counter arithmetic with Lambda expressions and Uninterpreted functions (CLU), which is a decidable logic [START_REF] Bryant | Modeling and verifying systems using a logic of counter arithmetic with lambda expressions and uninterpreted functions[END_REF]. We use the tool UCLID [START_REF] Lahiri | Modeling and verifi cation of out-of-order microprocessors using UCLID[END_REF] to transform the CLU formula into a CNF (Conjunctive Normal Form) formula, which we then check with the SAT solver Siege [START_REF] Ryan | Siege homepage[END_REF].

We now selectively review previous work on pipelined machine verification that is directly related to our work. Burch and Dill showed how to automatically compute the abstraction function using flushing [START_REF] Burch | Automatic verifi cation of pipelined microprocessor control[END_REF] and gave a decision procedure for the logic of uninterpreted functions with equality and Boolean connectives. Another, more efficient decision procedure was given in [START_REF] Bryant | Exploiting positive equality in a logic of equality with uninterpreted functions[END_REF]. The work was further extended in [START_REF] Bryant | Modeling and verifying systems using a logic of counter arithmetic with lambda expressions and uninterpreted functions[END_REF], where a decision procedure for the CLU logic that exploits optimized encoding schemes [START_REF] Seshia | A hybrid SATbased decision procedure for separation logic with uninterpreted functions[END_REF] is given. The decision procedure is implemented in UCLID, which has been used to verify out-of-order microprocessors [START_REF] Lahiri | Modeling and verifi cation of out-of-order microprocessors using UCLID[END_REF] and which we use to verify the models presented in this paper. The notion of correctness for pipelined machines that we use was first proposed in [START_REF] Manolios | Correctness of pipelined machines[END_REF], and is based on WEB-refinement [START_REF] Manolios | Mechanical Verifi cation of Reactive Systems[END_REF]. The first proofs of correctness for pipelined machines based on WEB-refinement were carried out using the ACL2 theorem proving system [START_REF] Kaufmann | Computer-Aided Reasoning: An Approach[END_REF][START_REF] Kaufmann | ACL2 homepage[END_REF]. The advantage of using a theory of refinement over using the Burch and Dill notion of correctness, even if augmented by a "liveness" criterion, is that deadlock may avoid detection with the Burch and Dill approach [START_REF] Manolios | Correctness of pipelined machines[END_REF], whereas it follows directly from the WEB-refinement approach that deadlock (or any other liveness problem) is ruled out. In [START_REF] Manolios | Automatic verifi cation of safety and liveness for xscale-like processor models using web refi nements[END_REF], it is shown how to automatically verify safety and liveness properties of pipelined machines using WEB-refinement. Theorem proving approaches include [START_REF] Sawada | Formal Verifi cation of an Advanced Pipelined Machine[END_REF][START_REF] Sawada | Verifi cation of a simple pipelined machine model[END_REF][START_REF] Hosabettu | Proof of correctness of a processor with reorder buffer using the completion functions approach[END_REF].

The paper is organized as follows. In Section 2, we provide an overview of refinement based on WEBs, the theory upon which our correctness proofs depend. In Section 3, we describe the pipelined machines we use in the paper and how we model the novel aspects of these machines using UCLID. In Section 4, we present experimental data measuring verification time and related statistics for the standard refinement maps. In Section 5, we propose our new refinement maps and analyze their performance experimentally. Everything required to reproduce our results, e.g., machine models, correctness statements, CNF formulas, etc., is available upon request. Conclusions and an outline of future work appear in Section 6.

Refi nement

Pipelined machine verification is an instance of the refinement problem: given an abstract specification, S, and a concrete specification, I, show that I refines (implements) S. In the context of pipelined machine verification, the idea is to show that MA, a machine modeled at the microarchitecture level, a low level description that includes the pipeline, refines ISA, a machine modeled at the instruction set architecture level. A refinement proof is relative to a refinement map, r, a function from MA states to ISA states. The refinement map shows us how to view an MA state as an ISA state, e.g., the refinement map has to hide the MA components (such as the pipeline) that do not appear in the ISA.

What exactly do we mean when we say MA refines ISA? We mean that the two systems are stuttering bisimilar: for every pair of states w, s such that w is an MA state and s = r(w), we have that for every infinite path σ starting at s, there is a "matching" infinite path δ starting at w, and conversely. That σ and δ "match" implies that applying r to the states in δ results in a sequence that is equivalent to σ up to finite stuttering (repetition of states). Stuttering is a common phenomenon when comparing systems at different levels of abstraction, e.g., if the pipeline is empty, MA will require several steps to complete an instruction, whereas ISA completes an instruction during every step. Of course, reasoning about infinite paths is difficult to automate, and in [START_REF] Manolios | Mechanical Verifi cation of Reactive Systems[END_REF], WEB-refinement, an equivalent formulation is given that requires only local reasoning, involving only MA states, the ISA states they map to under the refinement map, and their successor states.

In [START_REF] Manolios | Automatic verifi cation of safety and liveness for xscale-like processor models using web refi nements[END_REF], it is shown how to automate the proof of WEBrefinement in the context of pipelined machine verification. The idea is to strengthen, thereby simplifying, the WEBrefinement proof obligation; the result is a CLU-expressible formula that guarantees that the two machines satisfy the same formulas expressible in the temporal logic CTL * \ X, over the state components visible at the instruction set architecture level. CTL * \ X is a very expressive temporal logic, allowing one to express both safety and liveness properties. The CLU-expressible formula that implies WEBrefinement follows, where rank is a function that maps states of MA into the natural numbers.

∀w ∈ MA

:: s = r(w) ∧ u = ISA-step(s) ∧ v = MA-step(w) ∧ u = r(v) =⇒ s = r(v) ∧ rank(v) < rank(w)
In the formula above s and u are ISA states, and w and v are MA states; ISA-step is a function corresponding to stepping the ISA machine once and MA-step is a function corresponding to stepping the MA machine once. The proof obligation relating s and v is the safety component, and the proof obligation that rank(v) < rank(w) is the liveness component.

Processor Modeling and Verifi cation

We use as benchmarks for our experiments various complex pipelined machines whose modeling and verification is described in this section. The base processor model is a 6 stage pipelined machine with the following stages: instruction fetch (IF), instruction decode (ID), execute (EX), data memory access (M1 and M2), and write back (WB). We implement the following instruction types: ALU instructions with register-register and register-immediate addressing modes, loads, stores, and branches. We further extend this base processor model with features such as a pipelined fetch stage, an instruction queue (holding up to 3 instructions), direct mapped instruction and data caches, and a write buffer. The model has a simple branch prediction scheme that always predicts taken. A pipelined machine containing all of the above features is shown in Figure 1.

The modeling of pipelined machines using UCLID is well documented. Here we focus on the new features we have modeled, which include the write buffer and the direct mapped instruction and data caches. The instruction cache is modeled using three memory elements ICache-Valid, ICache-Tag, and ICache-Block that take the index as input and return a Boolean value indicating if the entry in the instruction cache is valid, the tag, and the data block, respectively. Three uninterpreted functions GetIndex, GetTag, and GetBlockOffset take the program counter as input, and return the index, tag, and block offset, respectively. Another uninterpreted function Select-Word is used to extract the instruction from the data block. The instruction memory is modeled as a lambda expression that takes 2 arguments, an index and a tag, and returns a block of data. This way of modeling the instruction memory allows us to match the contents of the instruction memory and the instruction cache. We need an invariant stating that valid instruction cache entries should be consistent with those in the instruction memory. We also prove that the instruction cache invariant is inductive, i.e., we prove that if the invariant holds for an arbitrary pipelined machine state, it also holds for any successor state.

The data cache is direct mapped and is similarly modeled. Writes to the data memory are write-through and update the data cache. An inductive invariant similar to the instruction cache is required for the data cache, stating that all the valid entries in the data cache are consistent with the data memory.

The write buffer is implemented as a queue and has 4 entries. Each entry has a data part, an address part, and a valid bit. Store instructions do not update the data memory directly, but write to the tail of the write buffer queue. The head of the write buffer queue is read and used to update the data memory. Reads from the data memory have to take into account the valid entries in the write buffer, as the write buffer has the most recent data values. Among the write buffer entries, priority is given to the entries closer to the tail. We require an inductive invariant for the write buffer establishing that if we update the data memory with all the valid entries in the write buffer, then we obtain the memory we would have obtained if a write buffer were not used. That is, if D is the data memory and U is the memory state obtained after updating all the valid write buffer entries to D, then U = R, where R is a memory that is similar to D except that store instructions directly update R (instead of going through the write buffer).

Refi nement Maps

Burch and Dill proposed the use of flushing to automatically define the refinement map used to establish the correctness of pipelined machines [START_REF] Burch | Automatic verifi cation of pipelined microprocessor control[END_REF]. The idea with flushing is that partially executed instructions in the pipeline latches are made to complete and update the programmer visible components, without fetching any new instructions. The programmer visible components for the pipelined machine models we consider include the program counter, the register file and the data memory. Once the pipeline is flushed, all the pipeline latches are invalid and the resulting state is an instruction set architecture (ISA) state. The Burch and Dill approach did not consider liveness, but in our context a rank function is needed and we define it as the number of steps required to fetch and complete a new instruction. Note that the presence of branch prediction makes this a non-trivial function.

The commitment approach can be thought of as the dual of flushing, as partially executed instructions are invalidated instead of being flushed, and the programmer visible components are rolled back to correspond to the last committed instruction. We use history variables [START_REF] Abadi | The existence of refi nement mappings[END_REF] to simplify the definition of this refinement map. Also, we need an inductive invariant that we call the "Good MA" invariant, which states that the contents of the latches have to be consistent with memory. The rank function for the commitment approach is defined as the number of steps required to commit an instruction. This is a trivial function, as it is essentially the number of consecutive invalid latches starting at the end of the pipeline.

We used both the flushing and the commitment approach to verify the pipelined machines described in Section 3. For all experimental results presented in this paper, we used the UCLID decision procedure (version 1.0) coupled with the siege SAT solver [START_REF] Ryan | Siege homepage[END_REF] (variant 4), using a 3.06 GHz Intel Xeon, with an L2 cache size of 512 KB.

Table 1 shows the verification times and related statistics for the various processor models. The names in the "Processor" column start with a "C" or "F", indicating whether commitment or flushing is used. Next, a number indicating the number of stages is given. Finally and optionally, the letters "I", "D", and "W" indicate the presence of an instruc- tion cache, data cache, and write buffer, respectively. The Siege running times can be obtained by subtracting the total time from the UCLID time. A "Fail" entry indicates that Siege failed on the problem (by immediately reporting that the problem is too complex and quiting).

Figure 2 shows how verification times vary as we first increase the length of the pipeline and then add an instruction cache, a data cache, and a write buffer. First, note that there are important differences between the flushing and commitment approaches. As a function of the length of the pipeline, verification times based on flushing grow exponentially, whereas verification times based on commitment are much more stable, e.g., for machine 10, the commitment refinement map leads to verification times that are about 166 times faster than verification times using flushing.

A key observation from the results in Table 1 and Figure 2 is the general rule of thumb that verification times grow exponentially as the number of stages in the pipeline (its length) increases or as the number of state variables per stage increases (the pipeline width), as happens when we add the instruction and data caches and write buffer. These results are not so surprising when we consider that the number of symbolic simulation steps required by the flushing approach depends on the length of the pipeline, and the invariant required for the commitment approach also depends on the complexity (width) of the pipeline. These observations give rise to the idea of an intermediate refinement map that uses flushing to deal with the width and commitment to deal with the depth. We explore this idea in more detail in the next section.

Intermediate Refi nement Maps

In this section, we propose the idea of intermediate refinement maps that partially flush and partially commit. Flushing a stage of the pipeline implies that we also flush later stages; similarly, committing a stage of a pipeline implies that we commit previous stages. Therefore, the intermediate refinement maps are obtained by selecting a stage of the pipeline and committing all stages up to and including it and flushing all later stages. Since the intermediate refinement maps are just based on commitment and flushing, they are quite easy to define.

Based on the above considerations, we define a set of intermediate refinement maps for NBP, a 10-stage machine that has an instruction queue, an instruction cache, a data cache, a write buffer, and a branch predictor that makes arbitrary choices. Note that NBP is more complex than 10IDW (see Table always predicts taken. The refinement maps are IR0, ..., IR9, where IRi commits the first i latches of the pipeline and flushes the remaining latches. For example, IR0, IR5, and IR9 correspond to pure flushing, commiting all latches before the decode stage, and pure commitment, respectively. Since we are proving that the pipelined machines satisfy the same safety and liveness properties as their corresponding instruction set architecture models, we also have to define rank functions. For refinement map IRi we define the rank function ranki to return a pair of natural numbers: the first is the commitment component, computed by ranki c , and the second is the flushing component, computed by ranki f . These two functions are essentially the standard rank functions used for flushing and commitment [START_REF] Manolios | Automatic verifi cation of safety and liveness for xscale-like processor models using web refi nements[END_REF]: ranki c returns the number of steps required for a new instruction to reach latch i + 1, the first flushed latch, while ranki f returns the number of steps required to fetch and complete a new instruction for a machine that consists of the latches after latch i, i.e., the flushed latches. The less-than ordering on ranki is the component-wise order.

Table 2 and Figure 3 show the verification times we obtain as we apply the various intermediate refinement maps to NBP. Note that the Y-axis in Figure 3 uses a logarithmic scale. The refinement map for IR9 is the standard commitment map and leads to a verification time of 234,440 seconds. The refinement map for IR0 is the standard flushing map and Siege is not able to handle the SAT instance generated by UCLID for IR0. Thus, in Figure 3, the verification time for IR0 is extrapolated, using Table 1 as a guide, and is shown as a dotted line. As i increases from 0 to 4, the verification times for IRi decrease at an exponential rate, with IR4 being about 64 times faster than IR0. After this point, verification times increase, as the time for IR5 shows.

There are several factors that account for the verification time improvements. First, by using the commitment approach for the latches up to the instruction queue, we effec- tively reduce the depth of the pipeline, thereby avoiding the exponential penalty incurred by flushing on deep pipelines, as witnessed in Figures 2 and3. In addition, by using flushing for the wide, later part of the pipeline, the "Good MA" invariant required by the commitment approach is greatly simplified in terms of the complexity of the resulting formulas; the conceptual complexity is about the same. Since about 90% of the verification effort required by the commitment approach is for proving the "Good MA" invariant, the savings are substantial. Second, the use of intermediate refinement maps essentially gives rise to two verification problems: one for the part of the machine up to the selected stage and the other for the rest of the machine. By selecting a stage in the middle, the machines are about half as complex as the initial pipelined machine, but since verification times are exponential in the size of the machines, this leads to exponential improvements in verification times. This explains the U-shaped graph in Figure 3, which takes its minimal value at IR4 and then increases at IR5.

From the results we obtained in this and the previous section, we now give some simple guidelines for choosing refinement maps optimized for reduced verification times. From the above considerations, this amounts to deciding up to which stage to use commitment. We suggest choosing the stage closest to the middle of the pipeline for which the complexity of the formula corresponding to the "Good MA" invariant is simple. The reason we suggest a latch somewhere in the middle is that this effectively leads to two verification problems, one of which is based on flushing and one on commitment, but as Table 1 and Figure 2 show, verification times are exponential in the length of the pipeline; thus, such a decomposition leads to drastic improvements in ver-ification times. The reason why we suggest that thought be given to the complexity of the formula for the "Good MA" invariant is that the verification time for the commitment approach is dominated by cost of establishing this invariant.

Finally, we make two further observations. First, most pipelines have a structure similar to the ones we use in this paper; thus, we expect our techniques to be widely applicable. Second, we have found that our approach simplifies the verification effort because if the resulting SAT instance is satisfiable, it is easy to determine if the problem lies with the commitment part of the proof or with the flushing part of the proof. This allows one to more readily identify errors than if a pure flushing or pure commitment approach is used, as the counterexamples will involve the whole pipeline, and will therefore contain many irrelevant details.

Conclusion

We have introduced a new class of refinement maps for pipelined machine verification, and using the state-of-theart verification tools UCLID and Siege have shown that one can attain several orders of magnitude improvements in verification times over the standard flushing-based refinement maps, even enabling the verification of machines that are too complex to otherwise automatically verify. The refinement maps allow us to use the commitment approachwhere partially completed instructions are invalidated and the programmer visible components are rolled back to correspond with the last committed instruction-on the latches at the front of the pipeline and the flushing approachwhere partially completed instructions are made to complete without fetching any new instructions-on the latches at the end of the pipeline. The result is that we are left with two verification problems, but on machines that are half as complex as the initial pipelined machine; since verification times are exponential in the size of the machines, this leads to drastic improvements in verification times. We give a simple recipe for defining such refinement maps and for defining the rank functions needed to establish liveness. Given our results, it seems worthwhile to further investigate the role of refinement maps on verification times. For future work, we plan to apply these techniques to a wider class of pipelined machines.

Figure 1 .

 1 Figure 1. High-level organization of pipelined machine model.

Figure 2 .

 2 Figure 2. Verification times obtained by first increasing the length of the pipeline and then adding an instruction cache, a data cache, and a write buffer.

Figure 3 .

 3 Figure 3. Verification times for a 10-stage processor model with an instruction cache, a data cache, and a write buffer using various refinement maps.

Table 1 . Verification statistics for various pipelined machine models.

 1

	Processor CNF Vars	Verification Times (sec) UCLID Total
	C6	12,328	2	36
	C6I	31,347	5	61
	C6ID	52,077	9	105
	C6IDW	75,494	13	164
	C7	13,290	2	31
	C7IDW	101,065	22	264
	C8	14,094	2	32
	C8IDW	127,637	24	407
	C9	15,208	3	24
	C9IDW	159,441	31	582
	C10	17,115	3	33
	C10I	76,418	21	1,826
	C10ID	128,102	26	2,038
	C10IDW	195,159	45	2,388
	F6	40,083	6	19
	F6I	66,843	11	25
	F6ID	110,181	20	72
	F6IDW	120,343	23	97
	F7	53,441	9	137
	F7IDW	218,572	79	400
	F8	95,456	15	597
	F8IDW	316,217	115	1,812
	F9	143,954	24	2,163
	F9IDW	452,124	181	7,711
	F10	198,222	34	5,481
	F10I	291,492	58	6,689
	F10ID	572,063	151	Fail
	F10IDW	605,734	170	Fail

Table 2 . Verification statistics for a 10-stage pipeline machine with branch prediction, an instruction cache, a data cache, and a write buffer using various refinement maps.

 2 ), which only has a simple branch predictor that

	Refinement Map CNF Vars	Verification Times (sec) UCLID Total
	IR0	729,285	153	Fail
	IR1	507,790	94	34,913
	IR2	382,970	62	11,631
	IR3	276,001	44	5,553
	IR4	183,236	28	3,626
	IR5	100,746	14	7,451
	IR9	253,461	34	234,440

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

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

Acknowledgments. We thank an anonymous referee for suggesting that we change the paper's title.

* This research was funded in part by NSF grants CCF-0429924 and IIS-0417413.


Brock J Lameres
email: brock_lameres@agilent.com

Sunil P Khatri

Encoding-based Minimization of Inductive Cross-talk for Off-chip Data Transmission

Inductive cross-talk within IC packaging is becoming a significant bottleneck in high-speed inter-chip communication. The parasitic inductance within IC packaging causes bounce on the power supply pins in addition to glitches and rise-time degradation on the signal pins. Until recently, the parasitic inductance problem was addressed by aggressive package design. In this work we present a technique to encode the off-chip data transmission to limit bounce on the supplies and reduce inductive signal coupling due to transitions on neighboring signal lines. Both these performance limiting factors are modeled in a common mathematical framework. Our experimental results show that the proposed encoding based techniques result in reduced supply bounce and signal degradation due to inductive cross-talk, closely matching the theoretical predictions. We demonstrate that the overall bandwidth of a bus actually increases by 85% using our technique, even after accounting for the encoding overhead. The asymptotic bus size overhead is between 30% and 50%, depending on how stringent the userspecified inductive cross-talk parameters are.

Introduction

Advances in VLSI fabrication technologies have led to a dramatic increase in the on-chip performance of integrated circuits. The increase in IC performance is predicted by the International Technology Roadmap for Semiconductors (ITRS) [START_REF]The International Technology Roadmap for Semiconductors[END_REF] to continue doubling every 18 months, following Moore's Law, for at least the next several years [START_REF] Tummalo | Fundamentals of Microsystem Packaging[END_REF]. However, package performance is predicted by the ITRS to only double over the next decade. This imbalance in performance expectations between the IC and the package is a major concern for system designers. The main limitation of the package performance is the parasitic inductance present in the level 1 (from IC die to package) and level 2 (from package to board) interconnects [START_REF] Miura | Electrical characterization and modeling of simultaneous switching noise for leadframe packages[END_REF][START_REF] Young | Return path inductance in measurements of package inductance matrixes[END_REF][START_REF] Hirano | Characterization and reduction of simultaneous switching noise for a multilayer package[END_REF]. The inductance factors that affect signal speed and integrity are as follows:

• Supply bounce. Typically supply (V SS and V DD ) pins are interspersed at regular intervals between signal pins. Every n th pin is a V SS or V DD . The supply bounce is proportional to the number of pins switching low or high. Ground bounce is expressed as:

V bnc = L ∑ i ( di dt ) (1)
Where L is the self-inductance of the V SS pin, and ∑ i ( di dt ) is evaluated over the number of signal pins switching low. Since the placement of power and signal pins is regular, we can compute this quantity as half the number of signal pins switching low to the immediate right of the V SS pin and half the number of signal pins switching low to the immediate left of the V SS pin. Since each signal always has a V SS pin to the left and to the right, we assume that if it switches high, then half the switching current is supplied by the V SS pin to its left, and the other half by the V SS pin to its right. In a similar manner, a supply voltage droop is encountered on V DD pins as well.

• Glitching. If a signal pin j is static, then a glitch may be induced in its voltage due to neighboring pins which switch. This is governed by the expression

V j glitch = ∑ k ±(M jk di k dt ) (2)
where i k is the current in the k th pin, and M jk is the mutual inductance between the j th pin being considered and the k th pin. The sign of the coupled voltage is positive or negative depending on whether the k th neighboring pin undergoes a rising or falling transition. • Switching speed. When a signal is switching, its transition can be sped up if the coupled voltage induced by its neighbors' mutual inductance aids the transition. We would like that a signal is not slowed down (i.e. either sped up, or unhindered) in its transitions due to this effect. We would like that when a signal j is rising (falling), the coupled voltage on this signal (Equation 2) due to its neighbors' transitions is zero or positive (negative). In this way, the transitions of signals are not slowed down due to inductive cross-talk.

The traditional approach to reducing the parasitic inductance within the package has been through aggressive package design. We are currently seeing success in the application of chipscale and flip-chip technologies in level 1 interconnect for highend applications. While such technologies decrease the above mentioned inductive effects, they are still relatively expensive for the majority of ICs. Further, they do not completely eliminate the inductive problems. Level 2 interconnect has been improved by moving toward surface mount and grid array style packaging. While these technologies are becoming affordable due to process improvements, they do not completely eliminate the inductance problem. While aggressive package design assists in the problem, it is a slow and expensive process to develop new packages. In this paper, we present a technique to avoid the inductive cross-talk in the interconnect by encoding the data being transmitted off-chip. We construct a set of equations which encode the constraints that any legal vector sequence must satisfy to avoid supply bounce, signal glitching, and signal edge speed degradation. The degree of supply bounce, glitching and edge speed degradation that can be tolerated are expressed by means of user-specified parameters. From this set of equations, we construct a set of legal vector sequences for the bus. We use this set to find the largest effective size of the bus that can be achieved by encoding, for a given physical size of the bus.

We show that the inter-chip bus throughput is increased as much as 85% by using our encoding techniques. The bus size overhead is as low as 20%, and can be reduced further by using less aggressive user-specified inductive cross-talk constraints. This compares very favorably with the 100% overhead associated with differential signaling.

The rest of this paper is organized as follows. Section 2 provides the definitions used in the rest of this paper. Section 3 describes previous work on this topic. Section 4 presents our encoding scheme to reduce inductive cross-talk. Experimental results are presented in Section 5, and conclusions are drawn in Section 6.

Preliminaries and Terminology

Consider k segments of n bus bits, with the j th segment consisting of signals b

j 0 , b j 1 , b j 2 •••b j n-1 .
Let the vector sequence on segment j be denoted as v j .

For example, if we had a V SS and V DD pin repeating after every 4 signal pins, the segments would consist of 6 pins. If the bus consisted of 20 signal pins, then we would implement it using 5 such segments.

• Definition 1 : A Vector Sequence v j is an assignment of values to the signals b j i as follows: b

j i = v j i , (where 0 ≤ i ≤ n -1 and v j i ∈ {0, 1, -1}).
Note that v j i = 1(-1) indicates that the i th signal of the j th bus segment is rising (falling), while v i = 0 indicates that it is either statically low or high.

• Definition 2 : A Legal Vector Sequence (modulo inductive cross-talk) v is an assignment to the signals b i such that:

• If b i is a supply pin, the total bounce on this pin is bounded by P bnc volts, where P bnc is a user-specified constant. • if b i is a signal pin which is static during the vector sequence, the glitch on this pin has a magnitude bounded by P 0 volts, where P 0 is a user-specified constant.

• if b i is a signal pin which is switching during the vector sequence, the switching speed of this pin is not degraded due to the effect of inductive cross-talk. Note that we can make this restriction stricter -by specifying that b i 's transition is in fact sped up due to inductive cross-talk.

Previous Work

There has been much work into the reduction of parasitic inductance through package advancement [START_REF] Miura | Electrical characterization and modeling of simultaneous switching noise for leadframe packages[END_REF][START_REF] Lopez | Influence of a floating plane on effective ground plane inductance in multilayer and coplanar packages[END_REF][START_REF] Hirano | Characterization and reduction of simultaneous switching noise for a multilayer package[END_REF]. Since the performance limitation is caused by the parasitic inductance in the level 1 and level 2 interconnects of the IC package, many packaging technologies have been developed. Table 1 shows the parasitic inductance values for three industry standard packages (a Quad FlatPak (QFP) with wirebonding, a Ball Grid Array (BGA) with wirebonding, and a flip-chip BGA package). In this table, L sel f is the self-inductance of a pin, and the columns to its right are the mutual inductive coupling coefficients of successive neighbors of this pin. Bus encoding algorithms have been developed to overcome the capacitive cross-talk for on-chip busses [START_REF] Duan | Analysis and avoidance of cross-talk in on-chip buses[END_REF][START_REF] Duan | Exploiting crosstalk to speed up on-chip buses[END_REF][START_REF] Victor | Bus encoding to prevent crosstalk delay[END_REF]. However, the problem of on-chip capacitive cross-talk minimization for busses is very different from that of off-chip inductive crosstalk minimization. Although our approach also constructs (inductive) cross-talk resistant CODECs algorithmically, in contrast to [START_REF] Duan | Analysis and avoidance of cross-talk in on-chip buses[END_REF][START_REF] Duan | Exploiting crosstalk to speed up on-chip buses[END_REF], we utilize memory-based CODEC solutions.

Package L sel f K 1 K 2 K 3 K 4 K 5 QFP-
Techniques have been presented to minimize the inductive problems due to packaging. Pipeline damping was presented in [START_REF] Powell | Pipeline damping: a microarchitectural technique to reduce inductive noise in supply voltage[END_REF]. In this approach, the authors attempt to minimize peak current levels by using a multi-valued output driver. While this approach improves performance by reducing the inductive ringing, it requires complex circuitry to implement the multi-valued output driver. CODECs have also been presented [START_REF] Chen | Switching codes for delta-i noise reduction[END_REF] that limit the total number of simultaneously switching signals with the same transition direction. This has the effect of reducing the power supply bounce by limiting the total amount of current flowing through the power supply pins at any given time. This technique reported performance improvements but only considered the supply bounce and not the signal-to-signal cross-talk. Our work improves upon previous techniques by additionally considering signal rise-time degradation and glitching due to inductive cross-talk. In our approach, all the inductive effects are captured in a common mathematical framework.

Our Approach

Consider a bus consisting of k identical segments, each of width n. For any segment j, let j -1 represent the segment to the immediate left of j, and let j + 1 represent the segment to its immediate right. Let us also denote the values of the n bits of segment j as v j i (0 ≤ i ≤ n -1). Figure 1 shows an example of a bus configuration with k = 3 and n = 5. The signal-to-power ratio for this bus configuration is α = # o f pins in each segment # o f supply pins in each segment = 5 2 . In general, when assigning package pins for an off-chip bus, V DD and V SS pins are interspersed among the signal pins in a regular fashion. The overall bus arrangement consists of a repetitive pattern of segments, each with their V DD and V SS pins in the same relative position within the segment (as shown in Figure 1).

In our approach, we write equations to encode the inductive cross-talk constraints for all bits of the j th bus segment. The constraints are different for signal, V DD , and V SS pins. Depending on the number of neighboring pins whose mutual inductance effects we want to model, the constraint equations will include pins belonging to neighboring segments as well. Since the segments are arranged in a repetitive manner, the encoding obtained for any segment will be valid for all k segments within the bus.

Having written these constraints, we then determine the vector sequences which satisfy these constraints. The valid sequences are used to construct a directed graph which encodes legal transitions between bus vectors. From this digraph, we construct a memory-based CODEC which is used during the bus data transfer.

Signal Pin Constraints

Consider the coupled voltage on a pin i (in bus segment j), due to a transition on its neighbor p (which is q pins away from i, and called the q th neighbor of i). This voltage is expressed as

v i = ±M ip di p
dt . The sign of the coupled voltage depends on the direction of the transition on the q th neighbor p. Since output drivers in a bus all have the same drive strength (i.e. for any pair of bus signal pins p and q), let k q = |M ip di p dt |. As a result, we can write v i = k q • v j i+p , where v j i+p ∈ {-1, 0, 1} as per Definition 1. Also, the arithmetic in the subscript of v j i+p is performed modulo n. For example, if n = 5, j = 4, and i = 0, then v j i-3 is the same as v 3 2 (i.e. the second bit of the adjacent bus segment to the left). Using this notation allows us to write the inductive cross-talk constraints very compactly.

We can write the mutual inductive coupling of any signal pin to its immediate neighbor signal pin as k 1 . Further, let the mutual inductive coupling of a signal pin to its neighbor's neighbor be expressed as k 2 (likewise k 3 , k 4 , etc.). We assume that k x = 0 for x > p. In other words, if p = 3, then we ignore the inductive cross-talk due to the 4 th neighbor and beyond, by setting k 4 = k 5 = ... = k n = 0. As a consequence, we include the mutual inductive contributions of three neighboring pins on either side of the pin under consideration. The k i labels in Figure 1 illustrate the mutual inductive signal coupling for p = 3. Note that each signal pin within the bus will experience coupling from pins on either side. This symmetry allows for encoding to reduce or cancel out the net mutual inductive effect experienced on a victim signal. For this work, any K j value less than 0.15 is ignored, and the corresponding k j values are set to 0.

The polarity of the mutual inductive coupling on the victim signal will depend on whether the neighboring signals are rising (v j i = 1) or falling (v j i = -1). Constraints for the victim signal are written for all three possible transitions, those being rising (v j i = 1), falling (v j i = -1), or static (v j i = 0). Using the notation described above, a constraint equation can be written for each victim signal, to limit the mutual inductive coupling effect. The inductive cross-talk requirements for a signal pin i in segment j are expressed below.

• If signal i rises in segment j, then the cumulative inductive cross-talk on this signal should not deter (or should aid) its transition by inducing a mutually coupled voltage which is greater than or equal to a user-specified quantity P 1 :

v j i = 1 ⇒ k 1 • (v j i-1 + v j i+1 ) + k 2 • (v j i-2 + v j i+2 ) + ... + k p • (v j i-p + v j i+p ) ≥ P 1
Note that P 1 has units of voltage and represents the minimum amount of inductive signal coupling allowed for the pin i in segment j. If P 1 = 0 and the inequality in the above expression is changed to an equality, then all the mutual inductive cross-talk is canceled out (i.e.

v j i-1 = -v j i+1 , etc.
). If we wish to speed up the transition of pin i in segment j, then we simply set P 1 > 0. This would force the mutually induced voltage on pin i of segment j to speed up its rising transition. Also note that by definition v j i for any supply pin is 0. This eliminates any mutual induced voltage on a victim signal pin i, due to V SS and V DD pins, as required. Likewise, any signal pin which remains static will also have v j i = 0 and hence will not cause in any mutually induced voltage on any neighboring victim pins.

• If signal i falls in segment j, then the cumulative inductive cross-talk on this signal should not deter (or should aid) its transition by inducing a mutually coupled inductive voltage which is less than or equal to a user-specified quantity P -1 :

v j i = -1 ⇒ k 1 • (v j i-1 + v j i+1 ) + k 2 • (v j i-2 + v j i+2 ) + ... + k p • (v j i-p + v j i+p ) ≤ P -1
Again, P -1 has units of voltage, and P -1 ≤ 0. Note that for symmetric rise and fall times we set |P 1 | = |P -1 |. However, |P 1 | and |P -1 | can be set to different values, to aid in only a rising or falling transition. In this way, the designer could compensate for differences in the rise and fall times of offchip drivers. • If signal i is static in segment j, then the cumulative inductive cross-talk on this signal should not result in a glitch greater than P 0 .

v j i = 0 ⇒ -P 0 ≤ k 1 • (v j i-1 + v j i+1 ) + k 2 • (v j i-2 + v j i+2 ) + ... + k p • (v j i-p + v j i+p ) ≤ P 0
Again, P 0 has units of voltage, just like P 1 and P -1 .

Power Pin Constraints

If a pin i in segment j is a V SS (V DD ) pin, we require that the bounce due to its self inductance be limited by P bnc , the absolute bounce (droop) voltage that can be tolerated. P bnc is a user-specified quantity.

Let z = |L di dt | in Equation 1. Note that since all output drivers of the bus are identically sized, di dt is identical for all drivers. Using this notation, we can write the constraint equation for V DD and V SS pins as follows:

v j 1 v j 2 v j 3 v j 4 v j 0 VSS VDD v j-1 0 VSS VDD VSS VDD Segment j -1 Segment j Segment j + 1 k1 k1 k2 k2 k3 k3 v j-1 1 v j-1 2 v j-1 3 v j-1 4 v j+1 0 v j+1 1 v j+1 2 v j+1 3 v j+1 4 Figure 1: Example Bus Configuration
• If signal i is V DD in segment j, then the cumulative supply bounce should be less than P bnc .

v j i = V DD ⇒ z 2 • (# o f v j i and v j-1 i
pins that are 1) ≤ P bnc Note that this assumes that any V DD pin supplies switching current for half the signal pins in its segment j, and half the signal pins in the segment to its left. Since each signal always has a V DD pin to the left and to the right, we assume that if it switches high, then half the switching current is supplied by the V DD pin to its left, and the other half by the V DD pin to its right. This explains the presence of the z 2 term in the constraint equation above.

• If signal i is V SS in segment j, then the cumulative ground bounce should be less than P bnc .

v j i = V SS ⇒ z 2 • (# o f v j i and v j-1 i
pins that are -1) ≤ P bnc It should be noted that the constraints for supply pins are solved to find the maximum number of signals that are allowed to transition in the same direction at once.

Once the configuration of V DD , V SS and signal pins is known for the bus, the above constraints can be greatly simplified. For example, in Figure 1, setting v j-1 0

= v j-1 4 = v j 0 = v j 4 = v j+1 0 = v j+1 4
= 0 would encode the supply constraints. In this manner, a single mathematical framework encodes all the required inductive cross-talk constraints, which are i) that switching signals should not have their slew-rates degraded, ii) that the glitch magnitude on static signal pins should be limited, and iii) the bounce on V DD and V SS pins should be bounded.

Constructing Legal Vector Sequences

Consider a particular bus configuration (n, k, and α) and user-specified inductive cross-talk constraints (P 1 , P -1 , P 0 , P bnc , and p). For each signal pin i within the segment j, three constraints equations are written (for v j i = 1, -1, and 0, per Section 4.1). For each power supply pin, one constraint expression is written, per Section 4.2. This results in a total of 3n -4 constraint equations for an nbit bus segment. These equations may refer to v j i values from neighboring bus segments as well. Each possible vector sequence is evaluated for legality by testing if it satisfies each of the 3n -4 constraint equations. The total number of signal pins that need to be considered depends on p. Since the v j i values for V DD and V SS pins are always zero, the number of evaluations is significantly reduced. Since there are three possible signal transitions (v j i = 1, -1, and 0) per signal bit, the total number of vector sequences that need to be tested for legality is 3 (n+2•p-6) . Note that the values of n and p for realistic busses is small, so these tests (which need to be done exactly once for a design) can be performed easily. In our experiments, n = 5 and p = 2, which is reasonable for real-life buses.

After testing the vector sequences for legality modulo inductive cross-talk, we create a set of legal vector sequences for the segment j. The size of this subset depends on how aggressively the parameters P 1 , P -1 , P 0 and P bnc are selected. The final list of legal vector sequences refers to n + 2p -6 signal pins (n -2 pins within the segment being considered, and 2p -4 pins on either side of the segment under consideration).

Constructing the CODEC

From the set of legal vector sequences, we next create a directed graph G(V, E), of legal bus transitions. We next find the effective size n of the bus that can be encoded using the transitions in G.

Note that for a vector sequence v j , we can construct a directed edge in G between vectors w j f rom and w j to (which are vertices of G). The end-points of this edge (w j f rom and w j to ) can be constructed given v j , as follows:

w j f rom,i = 1 if v j i = -1 (i.e. the signal is falling) or if v j i = 0 (i.e. the signal is static). w j f rom,i = 0 if v j i = 1 (i.
e. the signal is rising) or if v j i = 0 (i.e. the signal is static).

Similarly, we can write

w j to,i = 0 if v j i = -1 or if v j i = 0. w j to,i = 1 if v j i = 1 or if v j i = 0.
A directed edge between vertices w j f rom and w j to in G indicates the legality (from an inductive cross-talk viewpoint) of the transition from vector w j f rom to w j to . Therefore, given a set of vector sequences {v j } which are legal from a inductive cross-talk standpoint, we can construct a directed graph whose vertices are vectors in B n , and whose edges indicate a legal transition (from an inductive cross-talk viewpoint) between the source and sink vectors of the edge.

If an m-bit bus can be encoded using the legal transitions in G, then there must exist a set of vertices V c ⊆ V such that

• Each v s ∈ V c has at least 2 m outgoing edges e(v s , v d ) (includ- ing the self edge), such that the destination vertex v d ∈ V c . • The cardinality of V c is at least 2 m .
The above encoder is memory based. Note that the physical size of the bus n is obviously greater than or equal to m.

Given G, we find m using Algorithm 1. The input to the algorithm is m and G(V, E). We first find the out-degrees (selfedges are counted) of each v ∈ V . For each vertex v ∈ V , if the out-degree of v is less than 2 m , we assign V ← V \ v (i.e. we delete v) and delete all out-going edges rooted at v, as well as all in-coming edges incident on v. Given the updated digraph G, we repeat these steps until convergence. If, after convergence, the cardinality of V is greater than 2 m , we can construct a memory-based encoder using the legal transitions of G. The effective bus size that can be encoded in this case is m.

We initially call the algorithm with m = n -1 (where n is the physical bus size). If an m bit bus cannot be encoded using G, then we decrement m. We repeat this until we find a value of m such that the m-bit bus can be encoded by G.

Algorithm 1 Testing if G(V,E) can encode an n-bit bus test_encoder(m, G(V, E)) f ind out -degree o f each node v ∈ V degrees_changed = 1 while degrees_changed do degrees_changed = 0 for each v ∈ V do if out -degree(v) < 2 m then V ← V \ v E ← E \ out -edges(v) E ← E \ in -edges(v) degrees_changed = 1 end if end for end while
Note that this entire analysis needs to be performed for a representative bus segment. In other words, even if the bus is very wide, the analysis is performed for a single segment (which is typically very small). The experimental results we report next consider a typical bus segment (n = 5, k = 3). This segment could be part of a much larger bus, and the analysis would be valid for all segments of the bus.

Experimental Results

To validate the technique presented, we encoded an example bus configuration to avoid inductive cross-talk. The bus configuration is shown in Figure 1. We used the BGA-wb electrical parameters from Table 1. This bus was encoded using two sets of constraintsaggressive (P 0 , P 1 , P -1 and P bnc set to 5% of V DD ) and non-aggressive (P 0 , P 1 , P -1 and P bnc set to 10% of V DD ).

The first step consists of writing the constraint equations for every pin in the bus. In this bus, n = 5, k = 3, and α = 5/2. For the inductive coupling values in Table 1, we set p = 2 to ignore inductive coupling with a magnitude less than 0.15. This exercise yields 11 constraint equations, shown below. Note that these constraints have been simplified by removing terms with

v j i = 0. 1) v j 0 = V DD ⇒ L 2 • (# o f v j i pins that are 1) ≤ P bnc 2) v j 1 = 1 ⇒ k 1 • (v j 2 ) + k 2 • (v j 3 ) ≥ P 1 3) v j 1 = -1 ⇒ k 1 • (v j 2 ) + k 2 • (v j 3 ) ≤ P -1 4) v j 1 = 0 ⇒ -P 0 ≤ k 1 • (v j 2 ) + k 2 • (v j 3 ) ≤ P 0 5) v j 2 = 1 ⇒ k 1 • (v j 1 ) + k 1 • (v j 3 ) ≥ P 1 6) v j 2 = -1 ⇒ k 1 • (v j 1 ) + k 1 • (v j 3 ) ≤ P -1 7) v j 2 = 0 ⇒ -P 0 ≤ k 1 • (v j 1 ) + k 1 • (v j 3 ) ≤ P 0 8) v j 3 = 1 ⇒ k 2 • (v j 1 ) + k 1 • (v j 2 ) ≥ P 1 9) v j 3 = -1 ⇒ k 2 • (v j 1 ) + k 1 • (v j 2 ) ≤ P -1 10) v j 3 = 0 ⇒ -P 0 ≤ k 2 • (v j 1 ) + k 1 • (v j 2 ) ≤ P 0 11) v j 4 = V SS ⇒ L 2 • (# o f v j i pins that are -1) ≤ P bnc 5.1 Case 1: Fixed di dt
The first bus considered has a fixed di dt = 33 MA s . This corresponds to a data rate of 550 Mb/s in a 50 Ω system using the rule of thumb that datarate = 1 3•risetime . Note that the k i values depend on the magnitude of di dt . This means that as di dt is changed, the k i parameters will also change. However, the absolute voltage that the P x parameters represent (i.e., 5% or 10% of V DD ) will remain fixed.

We next find the set of legal vector sequences. The illegal vector sequences (along with the number of the constraint equation that they violate) are listed in Table 2. Note that the supply bounce constraints are violated frequently. Using the remaining (legal) vector sequences, we construct the digraph G as described in Section 4.4. We then find the effective bus width n which can be encoded using the legal transitions in G, as described in Algorithm 1.

We found the value of the effective bus size n as a function of the physical bus size m. The results are shown in Figure 2, where we plot the bus size overhead (i.e. n-m m ) as a function of n. Note that the asymptotic overhead is about 50% (using aggressive inductive cross-talk parameters) and about 30% (using non-aggressive inductive cross-talk parameters). ,4, and 5 shows the ground bounce, edge degradation, and glitch magnitudes for the three bus configurations. These plots correspond to the worst case inductive cross-talk among all bus pins. Note that the ground bounce magnitude (Figure 3) and the glitch magnitude (Figure 5) for both versions of the encoded bus are exactly at or below the limit specified (5% and 10% of V DD ), indicating that the experimental results track closely with the theory. Using the same analysis technique described in Case 1, we can sweep di dt to find the data rate at which the bus reaches the inductive cross-talk limits. For this example, we use the same bus configuration but the constraints are set to limit supply bounce, signal coupling, and glitching to 5% of V DD . The di dt for the original un-coded bus and the encoded bus is increased until the coupling limits are reached. The maximum di/dt values are 13.3 MA/s (un-encoded) and 37 MA/s (encoded). The 3-bit bus without encoding operates at 222 Mb/s (for a total throughput of 666 Mb/s), while our encoded 2-bit (effective) bus operates at 617 Mb/s (for a total throughput of 1234 Mb/s). Hence, encoding the bus increases the total throughput by 85% using the same physical size and considering the 33% bus size overhead. By relaxing the inductive crosstalk constraints, this overhead can be reduced further. The delay overhead in implementing the encoder is less than 200ps (using a 0.1µm process technology to implement the encoder logic).

Conclusions

Inductive cross-talk within IC packages is an important factor limiting off-chip I/O throughput. Addressing this issue with aggressive package design is slow and often too expensive for a majority of applications.

In this work, we presented a technique to encode off-chip bus data to avoid inductive cross-talk effects. The technique involves writing constraint equations which express the userspecified bounds on the amount of edge speed degradation, glitch magnitude, and supply bounce that can be tolerated. We incorporate all these inductive cross-talk effects in a common mathematical framework. We construct a set of legal vector sequences with respect to inductive cross-talk, and use these to develop a CODEC for inductive cross-talk avoidance.

Experimental results track very closely with the theory, and demonstrate an improvement of 85% in the bus throughput for an example bus. Additionally, the asymptotic bus size overhead for our technique is less than 50%.

Figure 2 :

 2 Figure 2: Encoding Efficiency

Figure 3 : 5 . 2

 352 Figure 3: Simulation of Ground Bounce 5.2 Case 2: Varying di dt

Figure 4 :

 4 Figure 4: Simulation of Edge Degradation

Figure 5 :

 5 Figure 5: Simulation of Glitch Magnitude

Table 1 :

 1 Self and Mutual Inductance Values for Modern Packages

	wb 4.550nH 0.744 0.477 0.352 0.283 0.263
	BGA-wb 3.766nH 0.537 0.169 0.123 0.097 0.078
	BGA-fc	1.244nH 0.630 0.287 0.230 0.200 0.175

Table 2 :

 2 Transition Violations for Fixed di dt Example

		0.15
		0.12							Original
		0.09							Aggressive Non-Aggressive
		0.06
		0.03
	(Volts)	-0.03 0.00
		-0.06
		-0.09
		-0.12
		-0.15
		0.0	0.3	0.5	0.8	1.0	1.3	1.5	1.8	2.0	2.3	2.5
							Time (ns)

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

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


Xun Liu
email: xunliu@ncsu.edu

Yuantao Peng North

Marios C Papaefthymiou
email: marios@eecs.umich.edu

RIP: An Efficient Hybrid Repeater Insertion Scheme for Low Power

This paper presents a novel repeater insertion algorithm for interconnect power minimization. The novelty of our approach is in the judicious integration of an analytical solver and a dynamic programming based method. Specifically, the analytical solver chooses a concise repeater library and a small set of repeater location candidates such that the dynamic programming algorithm can be performed fast with little degradation of the solution quality. In comparison with previously reported repeater insertion schemes, within comparable runtimes, our approach achieves up to 37% higher power savings. Moreover, for the same design quality, our scheme attains a speedup of two orders of magnitude.

Introduction

This paper presents a novel hybrid repeater insertion technique for low-power global interconnect designs. Given a two-pin interconnect and its timing budget, our algorithm derives the number of repeaters, and the width and location of each repeater so that the timing constraint is satisfied and power dissipation is minimized. The hybrid nature of our scheme stems from its judicious combination of an analytical repeater insertion solver and a dynamic programming (DP) based approach. Specifically, our algorithm proceeds in three steps. First, an initial repeater insertion solution is derived using DP with a very coarse repeater library. Second, an analytical procedure is applied to refine the initial solution and derive a new repeater library and a set of location candidates that fit the current design. Finally, the DP algorithm is repeated with the new library and location set for the low-power repeater insertion solution.

Our hybrid algorithm maintains the advantages of both analytical and DP-based schemes, producing high-quality interconnect designs efficiently. Furthermore, it is highly practical due to the adoption of a realistic interconnect model. Specifically, the interconnects are represented as a sequence of wire segments with fixed lengths and distinct RC characteristics, as derived from a routing procedure. Moreover, our algorithm can handle forbidden zones, i.e., parts of interconnects through macrocells in which no repeater can be placed, and is thus applicable to nets routed in real design scenarios.

We have implemented our repeater insertion algorithm into a software tool, called RIP, and applied it to the de-sign of low-power global interconnects. In comparison with the conventional DP algorithms, our scheme achieves power reductions of up to 37% with comparable runtimes. Moreover, for the same design quality, RIP achieves shorter runtimes by two orders of magnitude.

The remainder of the paper is organized as follows. Section 2 describes previous research on repeater insertion. The problem of low-power repeater insertion for multi-layer two-pin interconnects is formulated in Section 3. In Section 4, analytical constraints on the repeater widths and locations are derived that must be satisfied to minimize repeater power dissipation. Our algorithm is presented in Section 5. Section 6 presents our experimental results. Section 7 summarizes our paper.

Previous Work on Repeater Insertion

Extensive work on repeater insertion has appeared in the literature [START_REF] Bakoglu | Circuits, Interconnects, and Packaging for VLSI[END_REF][START_REF] Otten | Global wires harmful?[END_REF]. Repeater insertion has been applied to interconnect designs with various objectives such as delay minimization [START_REF] Alpert | A practical methodology for early buffer and wire resource allocation[END_REF][START_REF] Hedenstierna | CMOS circuit speed and buffer optimization[END_REF][START_REF] Nekili | Optimal methods of driving interconnections in VLSI circuits[END_REF] and power minimization [START_REF] Banerjee | A power-optimal repeater insertion methodology for global interconnects in nanometer designs[END_REF][START_REF] Garcea | Simultaneous analytical area and power optimization for repeater insertion[END_REF][START_REF] Kapur | Power estimation in global interconnect and its reduction using a novel repeater optimization methodology[END_REF][START_REF] Liu | Practical repeater insertion for low power: What repeater library do we need? In DAC[END_REF][START_REF] Nalamalpu | A practical approach to DSM repeater insertion: Satisfying delay constraints while minimizing area and power[END_REF]. Several circuit models have been proposed to compute the delay and power dissipation of repeaters such as the switch-level RC model [START_REF] Cong | Performance optimization of VLSI interconnect layout[END_REF] and moment matching model [START_REF] Alpert | Buffer insertion with accurate gate and interconnect delay computation[END_REF]. In analytical repeater insertion schemes, the optimization objectives are described using analytical functions of repeater width and location. The optimal repeater insertion solutions can be derived by setting the derivatives of these functions to zero and solving the ensuing equations [START_REF] Chu | Closed form solution to simultaneous buffer insertion/sizing and wire sizing[END_REF][START_REF] Chu | A new approach to simultaneous buffer insertion and wire sizing[END_REF]. Analytical schemes assume that the repeater widths and/or locations can be continuously changed. In actual designs, however, repeater widths are discrete due to layout design rules. In addition, the repeater locations are restricted to areas not occupied by circuit blocks. Consequently, when practical interconnects are considered, the analytical objective functions become very complex or even intractable.

To address the limitation of analytical schemes, a repeater insertion algorithm based on DP was proposed in [START_REF] Ginneken | Buffer placement in distributed RC-tree networks for minimal Elmore delay[END_REF] and improved in [START_REF] Shi | An O(nlogn) time algorithm for optimal buffer insertion[END_REF] for interconnect delay minimization. This algorithm has been modified for interconnect power reduction [START_REF] Lillis | Optimal wire sizing and buffer insertion for low power and a generalized delay model[END_REF][START_REF] Okamoto | Buffered Steiner tree construction with wire sizing for interconnect layout optimization[END_REF][START_REF] Zhou | Simultaneous routing and buffer insertion with restrictions on buffer locations[END_REF]. In these DP schemes, the possible widths and locations of the repeaters are discrete and finite. The algorithms choose the best solution out of all the possibilities. As a result, the efficiency of the DP schemes may be significantly affected by the given repeater library and potential repeater locations. Specifically, if the allowable repeater widths and locations are too limited, the quality of the interconnect may degrade substantially. On the other hand, when the numbers of repeater widths and locations are large, the DP algorithms become very timeconsuming [START_REF] Lillis | Optimal wire sizing and buffer insertion for low power and a generalized delay model[END_REF].

DP algorithms perform well for interconnect delay reduction, since the delay of a min-delay interconnect design is insensitive to its repeater widths and locations [START_REF] Cong | Buffer block planning for interconnect-Driven floorplanning[END_REF]. Consequently, a small-size coarse-granularity repeater library can be derived and applied to all interconnect designs with limited performance loss [START_REF] Alpert | Buffer library selection[END_REF]. However, when power reduction is considered, i.e., the problem addressed in this paper, DP schemes become less effective. Power dissipation of repeaters is sensitive to repeater widths, since at a first order approximation, gate capacitance depends linearly on repeater widths. Consequently, fine granularities are needed for repeater widths, so that repeater widths close to the optima can be used. However, the runtime complexity of DP schemes becomes pseudo-polynomial when power minimization is considered [START_REF] Lillis | Optimal wire sizing and buffer insertion for low power and a generalized delay model[END_REF]. The use of fine granularities leads to large numbers of possible repeater widths, resulting in excessively long runtimes. Figure 1 shows the structure of a multi-layer two-pin interconnect. The sizes of the driver and load are equal to w d and w r , respectively. The interconnect is made of m segments connected in a linear order as derived by a routing tool. The ith segment has a given length l i , and the resistance and capacitance per unit length are r i and c i , respectively. In a realistic interconnect routing scenario, the interconnect may go through some macro-blocks, in which no repeater can be placed. The portions of interconnect within the macro-blocks are represented as forbidden zones, whose ranges are labeled by

Problem Formulation

zs i ¡ ze i ¢ ¡ i ¤ 1 ¡ ¥ ¥ ¥ ¡ b.
The problem of low-power repeater insertion for multilayer two-pin interconnects can be described as follows:

Problem LPRI Let m be the number of interconnect segments, and let l i , r i and c i be the length, resistance per unit length, and capacitance per unit length of the segment i © 1

¡ 2 ¡ ¥ ¥ ¥ ¡

m , respectively. Furthermore, let b be the number of forbidden zones and zs i

¡ ze i ¢ ¡ i ¤ 1 ¡ ¥ ¥ ¥ ¡
b be the range of each zone i. Given the widths of the driver and receiver (w d ,w r ) and a timing target τ t , compute the number of repeaters n and the width w j and location x j of each repeater

j ¨© 1 ¡ 2 ¡ ¥ ¥ ¥ ¡ n such that j ¡ x j ¨ zs i ¡ ze i ¢ ¡ i ¤ 1 ¡ ¥ ¥ ¥ ¡
b, the delay of the interconnect is equal to or less than τ t , and the total power P of the repeaters is minimized.

Low-power Repeater Insertion Analysis

Repeater delay and power

(r i1, c i1, l i1 ) (r i2, c i2, l i2 ) w i+1 w i R s /w i C p w i r i1 l i1 c i1 l i1 /2 c i1 l i1 /2 c i2 l i2 /2 r i2 l i2 c i2 l i2 /2 c ik i l ik i /2 c ik i l ik i /2 (r ik i , c ik i , l ik i ) r ik i l ik i o w i+1 C Figure 2.
Circuit model of a repeater stage.

w 0 w n+1 w 1 w 2 w n (R 0, C 0 ) (R 1, C 1 ) (R n-1, C n-1 ) (R n, C n ) Figure 3
. Repeaters in a non-uniform net.

In our analysis of repeater delays, we use the widely adopted Elmore delay model, although more accurate analytical delay models can be used by replacing the Elmore delay with the corresponding delay functions. Figure 2 shows the circuit model of a single repeater stage in which the driving repeater is represented using the switchlevel RC model. Each interconnect segment is described using the lumped-RC π model. The receiving repeater is modeled as a capacitor. The Elmore delay of such a stage is derived as:

τ i ¤ R s C p R s w i ∑ j 1 k i l i j c i j C o w i 1 ¢ ∑ j 1 k i l i j r i j C o w i 1 ∑ j 1 k i 1 2 l i j c i j ∑ h j 1 k i l ih c ih ¢ r i j l i j ¡ (1)
where R s , C o , C p are the output resistance, input capacitance, and output capacitance of a unit-size repeater, k i is the number of segments between the repeaters i and i 1, and r i j ¡ c i j ¡ l i j ¢ are the unit length resistance, unit length capacitance, and length of segment

j ¨ 1 ¡ 2 ¡ ¥ ¥ ¥ ¡ k i ¢ .
When n repeaters are inserted into a multi-layer two-pin net as shown in Figure 3, the total delay can be written as:

τ total ¤ n ∑ i 0 τ i ¡ (2)
where τ i is the Elmore delay of each stage. Note that, to simplify Equation (2), we denote the widths of the interconnect driver w d and receiver w r as w 0 and w n 1 , respectively. From [START_REF] Banerjee | A power-optimal repeater insertion methodology for global interconnects in nanometer designs[END_REF], the short-circuit power of repeaters is very small for advanced VLSI technologies. The total power of repeaters can therefore be approximated by the sum of the dynamic power and leakage power and is given by:

P ¤ αv 2 dd fC total load n ∑ i 1 βw i ¡ (3)
where α is the signal activities, C total load is the total gate capacitance, and β is a constant. Since C total load is a linear function of the total repeater width, Equation (3) can be rewritten as follows:

P ¤ c γ n ∑ i 1 w i ¡ (4)
where c and γ are constants. Consequently, the minimization of the repeater power dissipation is equivalent to the minimization of the total repeater width p ¤ ∑ n i 1 w i . Notice that the power dissipation due to interconnects is a constant and therefore not considered during our low-power repeater insertion derivation.

Constraints on repeater widths

In Problem LPRI, it can be proved that, when the power dissipation is minimized, we have

τ total ¤ τ t ¥ (5)
Specifically, if τ total τ t , the repeater widths can then be further decreased to reduce power. As a result, we can use Lagrange relaxation to analyze the optimal repeater insertion solutions. In particular, we define

L ¤ p λ τ total ¡ τ t ¢ ¥ (6)
When power is minimized, we should have

∂L ∂w i ¤ 0 ¡ i ¤ 1 ¡ ¥ ¥ ¥ ¡ n ¥ (7)
Combining Equations ( 2), [START_REF] Chu | Closed form solution to simultaneous buffer insertion/sizing and wire sizing[END_REF], and (7), we have

1 λ¢ C o R i£ 1 R s w i£ 1 ¢ ¡ R s C i C o w i 1 ¢ w 2 i ¤ ¤ 0 ¡ i ¤ 1 ¡ ¥ ¥ ¥ ¡ n ¡ (8) where R i£ 1 ¤ ∑ j 1 k i¥ 1 r¦ i£ 1 § j l¦ i£ 1 § j
is the total interconnect resistance between repeaters i ¡ 1 and i, and C i ¤ ∑ j 1 k i c i j l i j is the total interconnect capacitance between repeaters i and i 1, as shown in Figure 3.

Constraints on repeater locations

We next develop a set of constraints on the repeater locations. Specifically, we denote the locations of the repeaters as

x i ¡ i ¤ 1 ¡ 2 ¡ ¥ ¥ ¥
n. Since τ total is a function of repeater widths w i and locations x i , using the first order Lagrange expansion, we have

∆τ total ¤ n ∑ i 1 ∂τ total ∂w i ∆w i n ∑ i 1 ∂τ total ∂x i ∆x i ¥ (9)
Since τ total ¤ τ t for the optimal repeater insertion design,

∆τ total ¤ 0 ¥ ( 10
)
Combining Equations ( 9) and ( 10), we have

n ∑ i 1 ∂τ total ∂w i ∆w i n ∑ i 1 ∂τ total ∂x i ∆x i ¤ 0 ¥ (11)
From Equation ( 7), we have

1 λ ∂τ total ∂w i ¤ 0 ¨∂τ total ∂w i ¤ ¡ 1 λ ¥ (12)
Combining Equations ( 11) and ( 12), we have The computation of ∂τ total ∂x i can be described with the aid of Figure 4. When repeater i moves downstream by a small distance ∆x i , a small resistive and capacitive load switches from the output to the input side of repeater i as shown in Figure 4 (b) and (c), in which the circuits in the dotted boxes represent the repeaters. As a result, the delay increase between repeaters i ¡ 1 and i can be calculated as

n ∑ i 1 ∆w i ¤ λ n ∑ i 1 ∂τ total ∂x i ∆x i ¥ ( 13
) i-1 r i1 x i ∆ r i1 x i ∆ c i1 x i /2 ∆ c i1 x i /2 ∆ c i1 x i /2 ∆ c i1 x i /2 ∆ (R i-1 ,C i-1 ) ( R i ,C i ) R s /w i-1 R s /w i-1 R s /w i R s /w i C p w i-1 C p w i-1 C p w i C p w i C o w i+1 C o w i+1 C o w i C o w i (a) (b) (c) i i+1
∆τ i£ 1© i ¤ ¢ C o w i r i1 R i£ 1 R s w i£ 1 ¢ c i1 ¤ ∆x i ¥ (14)
Similarly, the delay increase between repeaters i and i 1 is

∆τ i© i 1 ¤ ¡ ¢ C i C o w i 1 ¢ r i1 R s c i1 w i ¤ ∆x i ¥ (15)
The total delay change due to the repeater movement can then be derived by combining Equations ( 14) and ( 15) as follows: 16), we can derive the right-hand derivative of τ total with respect to x i by letting ∆x i approach zero:

∆τ total ¤ ∆τ i£ 1© i ∆τ i© i 1 ¥ (16) From Equation (
∂τ total ∂x i ¢ ¤ lim ∆x i © 0 ∆τ total ∆x i ( 17
) ¤ C o r i1 w i ¡ w i 1 ¢ R s c i1 1 w i£ 1 ¡ 1 w i ¢ c i1 R i£ 1 ¡ r i1 C i ¥
Similarly, the left-hand derivative of τ total with respect to

x i is ∂τ total ∂x i ¢ £ ¤ C o r¦ i£ 1 § k i¥ 1 w i ¡ w i 1 ¢ R s c¦ i£ 1 § k i¥ 1 1 w i£ 1 ¡ 1 w i ¢ c¦ i£ 1 § k i¥ 1 R i£ 1 ¡ r¦ i£ 1 § k i¥ 1 C i ¡ ( 18
)
where r¦ i£ 1 § k i¥ 1 and c¦ i£ 1 § k i¥ 1 are the resistance and capacitance per unit length of the interconnect at the input of repeater i.

For the repeater insertion solution that minimizes power dissipation, the total repeater width cannot be further reduced, namely

n ∑ i 1 ∆w i 0 ¥ (19)
Consequently, from Equation ( 13), we have

λ n ∑ i 1 ∂τ total ∂x i ∆x i 0 ¥ (20)
Furthermore, since the movements of repeaters are independent from each other, we have

i ¡ λ ∂τ total ∂x i ∆x i 0 ¥ (21)
Therefore, we have

λ ∂τ total ∂x i ¢ 0 ¡ (22) λ ∂τ total ∂x i ¢ £ ¢ 0 ¥ (23)
When repeater i is located inside an interconnect segment, we have

r i1 ¤ r¦ i£ 1 § k i¥ 1 and c i1 ¤ c¦ i£ 1 § k i¥ 1 . It follows that ∂τ total ∂x i ¢ ¤ ∂τ total ∂x i ¢ £
, and consequently, Inequalities ( 22) and ( 23) can be rewritten as

C o r i1 w i ¡ w i 1 ¢ R s c i1 1 w i£ 1 ¡ 1 w i ¢ c i1 R i£ 1 ¡ r i1 C i ¤ 0 ¥ (24)

Low-Power Repeater Insertion Algorithm

Analytical insertion

Solving the constraints in Section 4 for the optimal repeater widths and locations remains challenging, since τ total is not an explicit analytical function of x i . Furthermore, Relations ( 22) and (23) are inequalities. We next present algorithm REFINE, an iterative scheme that can derive a lowpower repeater insertion solution from an initial solution.

Figure 5 shows the pseudocode of our algorithm RE-FINE. Given the specification of a multi-layer two-pin net and an initial repeater insertion solution, REFINE derives a new solution so that the total repeater width is minimized. Specifically, in Line 1, REFINE calculates the optimal repeater widths of the initial solution by solving the non-linear Equations ( 5) and ( 8) using Newton-Raphson method. The parameter λ is also computed concurrently. It then calculates the total repeater width and initializes the loop-control variable ε in Line 2. The optimization procedure is performed iteratively using the while loop in Lines 3-10. In Line 4, the left-hand and right-hand partial derivatives of τ total with respect to the repeater location are computed for each repeater using Equations ( 17) and [START_REF] Okamoto | Buffered Steiner tree construction with wire sizing for interconnect layout optimization[END_REF] (or upstream) by a preselected distance. Based on Equation ( 13), such a movement results in the reduction of total repeater width. (If both relations do not hold, the moving direction is chosen for larger reduction.) A repeater will not be moved if the movement places the repeater inside a forbidden zone. After the movement, the lumped RC loads driven by each repeater are updated in Line 6. In Line 7, REFINE recalculates the width of each repeater and λ using Equations ( 5) and ( 8). The total repeater width is then updated in Line 8. The iteration continues until the improvement is smaller than a preselected threshold ε 0 . REFINE returns the repeater insertion solution in Line 10.

Repeater insertion heuristic

Though algorithm REFINE can quickly derive low-power repeater solutions, it assumes that the repeater width is continuously changeable, which is not practical. Furthermore, it requires an initial solution. In this section, we address these issues by combining REFINE with a DP algorithm. The pseudocode of our hybrid algorithm, called RIP, is given in Figure 6. RIP first performs a DP algorithm with coarse repeater widths and location candidates to derive an initial solution. Algorithm REFINE is then used to improve the initial solution in Line 2. In Line 3, RIP generates a new repeater library by rounding each repeater width from RE-FINE to its nearest valid discrete width. RIP also creates a small set of repeater location candidates by choosing several locations around the ones from REFINE. In Line 4, the DP algorithm is performed again with the new repeater library and location set to compute the final solution.

Experimental Evaluation

We have applied Algorithm RIP to various interconnect designs to demonstrate its effectiveness. Our interconnects and repeaters were generated using 0.18µm technology. Since our technique was used for global interconnects, each net was routed on metal4 and metal5 only. The number of segments for each net varied from 4 to 10. The length of each segment ranged from 1000 µm to 2500 µm. A single forbidden zone was created for each net. The length of the zone ranged from 20% to 40% of the total interconnect length. The location of forbidden zone was uniformly distributed along the corresponding interconnect.

During the application of RIP, a DP algorithm was performed in conjunction with a library of 5 repeaters. The smallest repeater width and the width granularity were set to 80u, where u is the minimal repeater width. The candidate locations were uniformly distributed along the interconnects with a granularity of 200 µm, excluding the forbidden zone. The ensuing results were then improved using our analytical solver REFINE. The repeater widths and locations of the refined solution were used to generate a new repeater library and a new set of location candidates. In particular, we rounded each repeater size to the nearest width in a repeater library with a granularity of 10u. The possible locations of repeaters included the locations derived by REFINE plus 10 locations before and after, with granularity 50 µm. Finally, the DP algorithm was performed using the new library and location set.

As a comparison, we used the DP algorithm in [START_REF] Lillis | Optimal wire sizing and buffer insertion for low power and a generalized delay model[END_REF], one of the most prevalent and well cited schemes, to derive lowpower repeater insertion solutions for the same interconnects and timing targets. We chose a repeater library of size 10 so that the total runtime of the DP scheme was comparable with that of our proposed scheme. We set the minimum repeater width to 10u and changed the granularity of the repeater widths. The candidate locations were uniformly distributed along the interconnects with a granularity of 200 µm, except for the forbidden zone.

Table 1 shows the experimental results from 20 interconnect designs. We designed each interconnect 20 times with timing targets ranging from 1.05 τ min to 2.05 τ min , where τ min is the minimum delay of the net. Columns 2-3 compare our scheme with the DP scheme in [START_REF] Lillis | Optimal wire sizing and buffer insertion for low power and a generalized delay model[END_REF] with library size 10 and granularity g ¤ 10u. As can be seen, our scheme can achieve maximal power savings ∆ Max up to 37.14%. Our scheme always succeeded in deriving solutions that satisfy the timing constraint, whereas the DP scheme resulted in several violations (6 out of 20 on the average), as shown in Column 3. When the library granularity g increases to 20u and 40u, the DP scheme can derive valid repeater insertion solutions for all the timing targets. As shown in Columns 5 and 7, our scheme achieves average power reductions ∆ Mean of 3.6% and 9.5% over the DP scheme, on the average. Figure 7 reveals the relation between the timing targets and the power savings of our approach over the DP scheme with a repeater library of size 10. When the repeater granularity is small, large-size repeaters are missing in the library. As a result, the DP scheme fails to find any valid solution when the timing target is very tight, as shown by zone I in Figure 7(a). When the timing target is very loose, i.e., zone III, the DP scheme performs as well as our approach, since large-size repeaters are not required. In fact, there exist a limited number of cases when the DP scheme provides better solutions. Our scheme achieves the best power savings when the timing target is in zone II. On the other hand, if the repeater library has a coarse width granularity, our scheme always outperforms the DP scheme as shown in Figure 7(b). The power savings increase when the timing target becomes loose, since such interconnect designs require various small-size repeaters, which seldom exist in a coarse-granularity library.

To demonstrate the favorable runtime-quality tradeoff of our scheme, we compared Algorithm RIP with the DP scheme that used a repeater library with a fixed width range of (10u, 400u). The repeater width granularity g DP varied from 40u to 10u, resulting in different numbers of repeaters in the library. Table 2 shows that, when g DP decreases, the average power savings (∆) of our scheme over the DP scheme reduces from 14.2% to 0.3%. However, the runtime T DP increases significantly. The average runtime of our scheme is about 0.17 seconds, more than 200 times faster than the DP scheme when both schemes produce comparable results. It is worth mentioning that when g DP ¤ 10u, the DP scheme used the same repeater library as that of RIP. Still, Algorithm RIP achieved slightly better power savings than the DP scheme. Such a seemingly surprising result is due to the fact that RIP judiciously chooses the candidate repeater locations, which have a smaller local granularity than that of the DP scheme.

Conclusion

In this paper, we propose a hybrid repeater insertion algorithm for interconnect power minimization. The novelty of our scheme is its judicious combination of an analytical solver with a DP scheme. Specifically, the analytical solver provides a concise repeater library and limited repeater location candidates, facilitating the efficient execution of the DP scheme. Our approach is highly practical, capable of handling multi-layer nets with forbidden zones. When applied to two-pin interconnects, our approach achieves up to 37% greater power savings or a speedup of more than 2 orders of magnitude in comparison with conventional DP schemes.

Our greedy analytical solver REFINE can be improved in several ways. Specifically, better power savings may be achieved if repeaters are allowed to move across small-size forbidden zones. Moreover, REFINE may be performed several times for further power reduction. We are currently extending our hybrid scheme to the design of low-power interconnect trees.

Figure 1 .

 1 Figure 1. Non-uniform two-pin interconnect.

Figure 4 .

 4 Figure 4. Repeater downstream movement.

Figure 5 .

 5 Figure 5. Algorithm REFINE.

RIP 1 Run

 1 DP with a coarse repeater library and locations 2 Run algorithm REFINE using the result from Line 1 3 Create a new library B and a set of candidate locations S 4 Run DP with B and S.

Figure 6 .

 6 Figure 6. Repeater Insertion Algorithm RIP.

Figure 7 .

 7 Figure 7. Power savings over DP scheme [13] with repeater granularity (a)10u (b)40u.

  Compute w i and λ 2 w total ¤ ∑ i w i and ε ¤ ∞ 3 while ε ¤ ε 0 4 Calculate ∂τ total ∂x i ¢ and ∂τ total ∂x i ¢ £ for each repeater 5 Move repeaters according to the results of Line 4 6 Update lumped (R i , C i ) driven by each repeater i 7 Solve for w i and λ 8 w total old ¤ w total , w total ¤ ∑ i w i 9 ε ¤ w total old ¡ w total ¢ w total old 10 return x i ,w i

. If Relation (22) (or (23)) does not hold, repeater i is moved downstream REFINE 1

Table 1 . Power reduction for two-pin nets.

 1

		g=10u		g=20u	g=40u
	Net	∆ Max V DP	∆ Max ∆ Mean	∆ Max ∆ Mean
		(%)		(%)	(%)	(%)	(%)
	1	22.95	7	10.00	4.72	28.57 11.41
	2	17.39	6	13.33	2.57	15.79	7.11
	3	26.19	6	7.69	2.85	21.05	8.47
	4	15.87	3	20.00	2.60	21.43	8.35
	5	20.69	9	13.33	4.83	21.43	9.96
	6	15.69	4	15.38	3.27	28.57	9.98
	7	15.69	7	10.53	2.27	28.57	8.96
	8	30.19	7	20.00	5.97	30.00 12.19
	9	20.00	7	10.00	4.27	28.57 11.31
	10	13.89	6	7.69	2.78	21.05	8.37
	11	23.40	6	12.50	2.12	30.00	9.43
	12	10.96	6	7.69	3.14	20.00	7.44
	13	17.86	8	10.00	3.95	21.43	8.54
	14	29.82	9	9.09	3.35	28.57 10.20
	15	19.23	5	10.00	2.65	21.43	8.32
	16	37.14	8	17.11	5.53	21.43 11.62
	17	24.62	6	9.09	3.19	26.67	9.84
	18	4.35	4	8.33	2.47	21.43	8.41
	19	11.11	7	9.09	3.36	21.43	9.80
	20	29.58	7	16.13	5.50	21.43 10.90
	Ave	20.33	6	11.8	3.6	23.94	9.53

Table 2 . Power savings and speedup tradeoff.

 2

	g DP (u) ∆ %	¢	T DP (s) Speedup
	40	14.2	1.0	6
	30	7.8		1.9	11
	20	4.0		5.8	34
	10	0.3		34.45	203

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