The RUMBLE Algorithm

In this section we discuss the details of the RUMBLE algorithm, which employs the linear program from the previous section to incrementally improve the timing of poorly placed latches. 

As noted in [13], the process of extracting gates to form a subcircuit may suffer from complications when subpaths of combinatorial logic between peripheral nodes are not modeled. These subpaths introduce additional timing constraints that, if left absent from the model, could invalidate the optimality of the solution. 

3 Buffer Insertion During Timing-Driven Placement 

Set pseudcl = [fanJn C fim-out) - movables - pseudo pseudo = pseudo U pseudo while pseudo 0 

Pseudomovables are collected by intersecting the transitive cones of logic between inputs and outputs to detect feedback paths, as shown in the pseudocode of Fig. 3.11. To ensure accuracy, the inputs and outputs of pseudomovables themselves must be bounded by fixed endpoints, as shown illustrated in Fig. 3.10c. These fringe nodes completely isolate the timing of the resulting convex subcircuit from outer cones of logic. 

---

The remainder of this chapter is organized as follows. Section 3.2 discusses background and previous work. Section 3.3 describes the timing model we use in this work. Section 3.4 describes how RUMBLE performs timing-driven placement. Section 3.5 describes the RUMBLE algorithm. Section 3.6 shows experimental results. Conclusions are drawn in Sect. 3.7. 

Fig. 3.12 The RUMBLE algorithm proceeds by a selecting a subcircuit to work on. An LP is formulated and solved, with movable gates being relocated as shown in b. Existing repeater trees are no longer appropriate, and are subsequently removed in c. Finally, the nets are re-buffered, forming the final subcircuit shown in d...

---