Floorplanning algorithms have traditionally underperformed experienced designers, even when relatively simple interconnect metrics are concerned. However, the sheer scale of modern systems on chip makes an all-manual design flow infeasible. In this paper, we propose a new efficient automated approach to the floorplan repair problem, where a set of violated design constraints are satisfied by applying small changes to an existing rough floorplan. Such a floorplan can be produced by a human designer, by a scalable placement algorithm, or result from engineering adjustments to a pre-existing floorplan. In all cases, overlapping modules must be separated, and in some instances, modules may need to be repositioned to satisfy other requirements.The algorithmic framework we propose is built upon an expressive graph-based encoding of constraints. While capable of representing floorplans with or without overlapping modules, it can also support the outline of the core area, fixed module locations, region constraints, proximity and alignment constraints, etc. Instead of applying randomized local search in the hope of satisfying these constraints, we track all implications of imposed constraints and resolve violations by invoking gradual modifications to the floorplan.The primary focus of this paper is on a particularly efficient conflict-directed algorithm for floorplan repair and legalization. It is shown to completely eliminate overlaps from layouts produced by Capo 9.4, Feng Shui 5.1 and APlace 2.01 on IBM-HB benchmarks with hard blocks, typically requiring negligible runtime and increasing interconnect length by only several percent. Furthermore, we are able to generate legal solutions for these instances that surpass previously reported results in wirelength by an average of roughly 7%.
We present a method for applying local search to overconstrained instances of the Disjunctive Temporal Problem (DTP). Our objective is to generate high quality solutions (i.e., solutions that violate few constraints) in as little time as possible. The technique presented here differs markedly from previous work on DTPs, as it operates within the total assignment space of the underlying CSP rather than the partial assignment space of the related meta-CSP. We provide experimental results demonstrating that the use of local search leads to substantially improved performance over systematic methods.
We present an algorithm and pruning techniques for efficiently finding optimal solutions to over-constrained instances of the Disjunctive Temporal Problem with Preferences (DTPP). Our goal is to remove the burden from the knowledge engineer who normally must reason about an inherent trade-off: including more events and tighter constraints in a DTP leads to higher-quality solutions, but decreases the chances that a solution will exist. Our method solves a potentially over-constrained DTPP by searching through the space of induced DTPPs, which are DTPPs that include a subset of the events in the original problem. The method incrementally builds an induced DTPP and uses a known DTPP algorithm to find the value of its optimal solution. Optimality is defined using an objective function that combines the value of a set of included events with the value of a DTPP induced by those events. The key element in our approach is the use of powerful pruning techniques that dramatically lower the time required to find an optimal solution. We present empirical results that show their effectiveness.
A fundamental problem in timing-driven physical synthesis is the reduction of critical paths in a design. In this work, we propose a powerful new technique that moves (and can also resize) multiple cells simultaneously to smooth critical paths, thereby reducing delay and improving worst negative slack or a figure-of-merit. Our approach offers several key advantages over previous formulations, including the accurate modeling of objectives and constraints in the true timing model, and a guarantee of legality for all cell locations.
In this paper, we focus on extending the expressive power of constraint-based temporal reasoning formalisms. We begin with the well-known Simple Temporal Problem with Uncertainty, and incorporate three extensions: prior observability, in which the values of uncontrollable events become known prior to their actual occurrence; partial shrinkage, in which an observation event triggers the reduction of a contingent temporal interval; and a generalization of partial shrinkage to requirement links, making it possible to express certain types of uncertainty that may arise even when the time points in a problem are themselves fully controllable. We describe levels of controllability in the resulting formalism, the Generalized STPU, and relate this formalism to related developments in disjunctive temporal reasoning. Throughout, we motivate our approach with simple, real-world examples that illustrate the limitations of existing formalisms and the flexibility of our proposed extensions.
In this paper, we present the complete design and architectural details of MaizeRouter. MaizeRouter reflects a significant leap in progress over existing publicly available routing tools yet relies upon relatively simple operations, including extremeedgeshifting , a technique aimed primarily at the efficient reduction of routing congestion, and edgeretraction , a counterpart to extreme edge shifting that serves to reduce unnecessary wirelength. We present enhanced variations of these operations to enable the rapidexploration of candidate paths, along with a form of dynamiccostdeflation that provides our various path computation procedures with progressively more accurate (and less optimistic) cost information as search continues. These algorithmic contributions are built upon a framework of interdependent net decomposition, a representation that improves upon traditional two-pin net decomposition by preventing duplication of routing resources while enabling cheap and incremental topological reconstruction. Collectively, these operations permit a broad search space that previous algorithms have been unable to achieve, resulting in solutions of considerably higher quality than those of well-established routers.
