Paper Review:Buffer insertion with adaptive blockage avoidance

Abstract
Buffer insertion is a fundamental technology for very large scale integration interconnect optimization. This work presents the repeater insertion with adaptive tree adjustment (RIATA) heuristic that directly extends van Ginneken’s classic algorithm to handle blockages in the layout. Given a Steiner tree containing a Steiner point that overlaps a blockage, a local adjustment is made to the tree topology that enables additional buffer insertion candidates to be considered. This adjustment adapts to the demand on buffer insertion and is incurred only when it facilitates the maximal slack solution. RIATA can be combined with any performance-driven Steiner tree algorithm and permits various solution search schemes to achieve different solution quality and runtime tradeoffs. Experiments on several large nets confirms that high-quality solutions can be obtained through this technique with greater efficiency than simultaneous approaches.

Paper Review: Buffer placement in distributed RC-tree networks for minimal Elmore delay

Abstract
This paper presents an algorithm for choosing the buffer positions for a wiring tree such that the "Elmore-delay" is minimal. For given required arrival times at the sinks of the wiring tree, the algorithm chooses buffers such that the required departure time at the source is as late as possible The topology of the wiring tree, a steiner tree, is assumed given, as well as the possible (legal) positions of the buffers. The algorithm uses a depth first search on the wiring tree to construct a set of time/capacitance pairs that correspond to different choices. The complexity of the algorithm is O(B^2) where B is the number of possible buffer positions. An extension of the asic algorithm allows minimization of the number of buffers as a secondary objective.

Paper Review: Gate Sizing Using Incremental Parameterized Statistical Timing Analysis

Abstract
As technology scales into the sub-90nm domain, manufacturing variations become an increasingly significant portion of circuit delay. As a result, delays must be modeled as statistical distributions during both analysis and optimization. This paper uses incremental, parametric statistical static timing analysis (SSTA) to perform gate sizing with a required yield target. Both correlated and uncorrelated process parameters are considered by using a first-order linear delay model with fitted process sensitivities. The fitted sensitivities are verified to be accurate with circuit simulations. Statistical information in the form of criticality probabilities are used to actively guide the optimization process which reduces run-time and improves area and performance. The gate sizing results show a significant improvement in worst slack at 99.86% yield over deterministic optimization.

Paper Review: An Exact Solution to the Transistor Sizing Problem for CMOS Circuits Using Convex Optimization

Abstract
A general sequential circuit consists of a number of combinational stages that lie between latches. For the circuit to meet a given clocking specification, it is necessary for each combinational stage to satisfy a certain delay requirement. Roughly speaking, increasing the sizes of some transistors in a stage reduces the delay, with the penalty of increased area. The problem of transistor sizing is to minimize the area of a combinational stage, subject to its delay being less than a given specification. Although this problem has been recognized as a convex programming problem, most existing approaches do not take full advantage of this fact, and often give nonoptimal results. An efficient convex optimziation algorithm has been used here. This algorithm is guaranteed to find the exact solution to the convex programming problem. We have also improved upon existing methods for computing the circuit delay as an Elmore time constant, to achieve higher accuracy. CMOS circuit examples, including a combinational circuit with 832 transistors are presented to demonstrate the efficacy of the new algorithm.

Paper Review: Duet An accurate Leakage Estimation and Optimization Tool for Dual-Vt Circuits

Abstract
We present a new approach for the estimation and optimization of standby power dissipation in large MOS digital circuits. We first introduce a new approach for accurate and efficient calculation of the average standby or leakage current in large digital circuits by introducing the concepts of “dominant leakage states” and the use of state probabilities. Combined with graph reduction techniques and simplified nonlinear simulation, our method achieves speedups of three to four orders of magnitude over exhaustive SPICE simulations while maintaining very good accuracy. The leakage current calculation is then utilized in a new leakage and performance optimization algorithm for circuits using dual Vt processes. Our approach is the first to consider the assignment of both the Vt and the width of a transistor, simultaneously. Our optimization approach uses incremental calculation of leakage and performance sensitivities and can take into account a partially defined circuit state constraint for the standby mode of the device. In tests on a variety of industrial circuits, our optimization approach was able to obtain 81–100% of the performance achievable with all low transistors, but with 1/3 to 1/6 the standby current. We also show that knowledge of the standby state of the device enhances the leakage/performance tradeoff.

Paper Review: Fixed-outline floorplanning through better local search

Abstract

Classical floorplanning minimizes a linear combination of area and wirelength. When Simulated Annealing is used, e.g., with the Sequence Pair representation, the typical choice of moves is fairly straighgorward. In this work, we study the fixed-outline jloorplan for- mulation that is more relevant to hierarchical design style and is justijied for very large ASICs and SOCs. We empirically show that the bed-outlinejloorplan problem in- stances are signijicantly harder than the well-researched instances without jived outline. Furthermore, we suggest new objective functions to drive simulated annealing and new types of moves that better guide local search in the new context. Our empirical evaluation is based on a new jloorplanner implementation Parquet-1 that can operate in both outline-free and fixed-outline modes. Our proposed moves are based on the notion offloor- plan slack. The proposed slack computation can be imple- mented with all existing algorithms to evaluate sequence pairs, of which we use the simplest, yet semantically in- distinguishable from the fastest reported ([16]). A similar slack computation is possible with many other jloorplan representations. In all cases, the slowdown is by a con- stant factor - roughly 2x.

Paper Review: B*-Trees: A New Representation for Non-Slicing Floorplans

Abstract

We present in this paper an efficient, flexibile and effective data structure, B*-trees for non-slicing floorplans. B*-trees are based on ordered binary trees and the admissible placement presented in [1]. Inheriting from the nice properties of ordered binary trees, B*-trees are very easy for implementation and can perform the respective primitive tree operations search, insertion, and deletion in only O(1), O(1), and O(n) times while exisitng representations for non-slicing floorplans need at least O(n) time for each of these operations, where n is the number of modules. The correspondence between an admissible placement and its induced B*-tree is 1-to-1 (i.e., no redundancy); further, the transformation between them takes only linear time. Unlike other representations for non-slicing floorplans that need to construct constraint graphs for cost evaluation, in particular, the evaluation can be performed on B*-trees and their correspoding placements directly and incrementally. We further show the flexibility of B*-trees by exploring how to handle rotated, pre-placed, soft, and rectilinear modules. Experimental results on MCNC benchmarks show that the B*-tree representation runs about 4.5 times faster, consumes about 60% less memory and results in smaller silicon area than the O-tree one [1]. We also develop a B*-tree based simulated annealing scheme for floorplan design; the scheme achieves near optimum area utilization even for rectilinear modules.

Paper Review: VLSI/PCB placement with obstacles based on sequence-pair

Abstract

In a typical VLSI/PCB design, some modules are pre-placed in advance, and the other modules are requested to be placed without overlap with these pre-placed modules. The presence of such obstacles introduces inconsistency to a coding scheme, called a sequence-pair which has been proposed for an obstacle free placement problem. We solve this difficulty by proposing a procedure, called "adaptation", which transforms inconsistent sequence-pair to a consistent one, with utmost consideration for minimizing the modification. It is shown that a simulated annealing is well organized to test only feasible placements with the adaptation procedure. Using the adaptation, an MCNC benchmark data, ami49 is packed with 20% of the modules being pre-placed. Further, a PCB example which includes 32 free modules and 4 pre-placed modules (connectors) is laid out successfully by our method with a conventional wiring estimation followed by a commercial router.

Paper Review: Classical Floorplanning Harmful?

Abstract

Classical floorplanning formulations may lead researchers to solve the wrong problems. The paper points out several examples, including (i) the preoccupation with packing driven, as opposed to connectivity-driven, problem formulations and benchmarking standards; (ii) the preoccupation with rectangular (and L or T shaped) block shapes; and (iii) the lack of attention to algorithm scalability, fixed die layout requirements and the overall RTL down methodology context. The right problem formulations must match the purpose and context of prevailing RTL-down design methodologies, and must be neither overconstrained nor underconstrained. The right solution ingredients are those which are scalable while delivering good solution quality according to relevant metrics. We also describe new problem formulations and solution ingredients, notably a perfect rectilinear floorplanning formulation that seeks zero-whitespace, perfectly packed rectilinear floorplans in a fixed-die regime. The paper closes with a list of questions for future research.

Paper Review: Statistical Timing Analysis: From Basic Principles to State of the Art

Abstract

Static-timing analysis (STA) has been one of the most pervasive and successful analysis engines in the design of digital circuits for the last 20 years. However, in recent years, the in- creased loss of predictability in semiconductor devices has raised concern over the ability of STA to effectively model statistical variations. This has resulted in extensive research in the so-called statistical STA (SSTA), which marks a significant departure from the traditional STAframework. In this paper,we review the recent developments in SSTA. We first discuss its underlying models and assumptions, then survey the major approaches, and close by discussing its remaining key challenges.

Status Goals and Plans For Dec 17, 2009

Main Goal:  Spend winter break reading literature and find both an area and a niche to fill.

Paper Review: Timing verification and the timing analysis program

Timing Verifications consists of validating ht epath delays (primary input or storage element to primary output or storage element) to be sure they are not too long or too short and checking the clock pulses to be sure they are not too wide or too narrow. The programs addressing these problems neither produce input patterns like test pattern generators nor require input patterns like traditional simulators. Several programs (described here) operate by tracing paths [P173, WO78, SA81, KA81]. One program [MC80] extends simulation into a pessimistic analyzer not dependent on test patterns.

Timing Analysis, a program described recently in [HI82a], is designe dot analyze the timing of large digital computers and is based, in part, on the concepts discloed in a patented method [DO81] for determining the extreme characteristics of logic block diagrams. The output of Timing Analysis includes "slack" at each block to provide a measure of the severity of the timing problem. The program also generates stnadard deviations for the times so that a statistical timing design can be produced rather than a worst case approach.

Review of Pea Soup, Tripe and Mathematics

Full article can be found here

Topics are taught without motivation behind them, and most students find this uninteresting.

I agree with this. I've always been concerned that this was what made me "an engineer" but I believe simpler examples could really
motivate the topics. I also find this point to be somewhat untrue, but I will metion that later

Study Locations

Like many, I have issues getting down to studying or cranking something out.  It's a tough challenge, and there's no one solution that works for everyone.  It has to be quiet enough that you can focus at the work on hand, often you need a large enough work space to make it useful for writing/drawing/sketching and one factor that most people don't consider is the creativity of the location.

Status Goals and Plans For Dec 10, 2009

New Main Goal: Spend winter break reading literature and find both an area and a niche to fill.

Previous Main Goal: Understand, simulate & evolve an IC-based antenna
This seems to be at least partly complete as far as available tools are available.  The novelty of it has worn off after reading more literature.