July 2011 Newsletter Placing you one click away from the best new CAD research! Plain-text version at http://www.umn.edu/~tcad/newsletter/2011-07.txt KEYNOTE PAPER Rivers, J. A. Gupta, M. S. Shin, J. Kudva, P. N. Bose, P. Error Tolerance in Server Class Processors http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5875991 This paper provides: 1) a very brief motivation and technological trend data to show why hard and soft errors are expected to be of increasing concern in the future; 2) a summary review of chip-level error tolerance practices today-with a brief reference to IBM's POWER6 and POWER7 designs; 3) open research challenges and current solution approaches of promise, based on published literature; and 4) concluding remarks. REGULAR PAPERS ANALOG, MIXED-SIGNAL, AND RF CIRCUITS Brambilla, A. Gruosso, G. Gajani, G. S. A Probe-Based Harmonic Balance Method to Simulate Coupled Oscillators http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5875987 The probe-based harmonic balance (HB) method is a well-known and largely used tool to compute the steady state behavior of autonomous circuits (oscillators). In this paper, the method is extended to analyze coupled oscillators, where the working frequencies and conditions, i.e., pulling and locking modes, have great relevance. It is shown that probe insertion can be considered as a specific matrix-bordering technique applied to the Jacobian matrix of the HB method. It transforms the original coupled autonomous system in a non-autonomous one, forcing the circuit to lock to the probes themselves. In this context, a novel approach to find the steady state solution is introduced. This approach exploits the properties of the power exchanged among the probes and the coupled oscillators. Possibly, more than one steady state solution with the oscillators working in pulling or locking modes can be found. Suvak, O. Demir, A. On Phase Models for Oscillators http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5875993 Oscillators have been a research focus for decades in many disciplines such as electronics and biology. The time keeping capability of oscillators is best described by the scalar quantity phase. Phase computations and equations describing phase dynamics have been useful in understanding oscillator behavior and designing oscillators least affected by disturbances such as noise. In this paper, we present a unified theory of phase equations assimilating the work that has been done in electronics and biology for the last seven decades. We first provide a review of isochrons, which forms the basis of a generalized phase notion for oscillators. We present a general framework for phase equations and derive an exact phase equation that is practically unusable but facilitates the derivation of usable ones based on linear (already known) and quadratic (new and more accurate) approximations for isochrons. We discuss the utility of these phase equations in performing (semi) analytical phase computations and also describe simpler and more accurate phase computation schemes. Numerical experiments on several examples are presented comparing the accuracy of the various phase equations and computation schemes described in this paper. EMERGING TECHNOLOGIES Zhao, Y. Xu, T. Chakrabarty, K. Broadcast Electrode-Addressing and Scheduling Methods for Pin- Constrained Digital Microfluidic Biochips http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5875970 Recent advances in digital microfluidics have enabled lab-on-a-chip devices for DNA sequencing, immunoassays, clinical chemistry, and protein crystallization. Basic operations such as droplet dispensing, mixing, dilution, localized heating, and incubation can be carried out using a 2-D array of electrodes and nanoliter volumes of liquid. The number of independent input pins used to control the electrodes in such microfluidic "biochips" is an important cost-driver, especially for disposable printed circuit board devices that are being developed for clinical and point-of- care diagnostics. However, most prior work on biochip design-automation has assumed independent control of the electrodes using a large number of input pins. We present a broadcast-addressing-based design technique for pin- constrained multifunctional biochips. The proposed method provides high throughput for bioassays and it reduces the number of control pins by identifying and connecting control pins with "compatible" actuation sequences. We also describe two scheduling methods to map fluidic operations on the pin-constrained design, in order to minimize the completion time while avoiding pin-actuation conflicts. The proposed methods are evaluated using multifunctional chips designed to execute a set of multiplexed bioassays, the polymerase chain reaction, and a protein dilution assay. Xiao, Z. Young, E. F. Y. Placement and Routing for Cross-Referencing Digital Microfluidic Biochips http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5875969 Computer-aided design problems of digital microfluidic biochips are receiving much attention, and most of the previous works focus on direct-addressing biochips. In this paper, we solve the placement and droplet routing problem in cross-referencing biochips. In these biochips, the electrodes are addressed in a row-column manner, which may cause electrode interference that prevents simultaneous movements of multiple droplets. We propose a routing algorithm that solves the droplet routing problem directly. A two-coloring graph-theoretic method is used in our router to detect and prevent the electrode interference. In addition, we propose an integer linear programming based method to solve the placement problem. Our method considers the characteristics of cross-referencing biochips and is aware of droplet routing. Real-life benchmarks are used to evaluate the proposed methods. Compared with previous works, our router improves on average 4% in routing time and 58% in runtime. It can route all the benchmarks within the time limits, while the latest work fails in some cases. Moreover, experimental results show that by running our router on the placement result generated by our method and those generated by the latest work, an average improvement of 11%, 29%, 54%, and 46% in the maximum routing time, average routing time, stalling steps, and cell usage can be achieved. MODELING AND SIMULATION Rubanov, N. A General Framework to Perform the MAX/MIN Operations in Parameterized Statistical Timing Analysis Using Information Theoretic Concepts http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5875992 As integrated circuit technologies are scaled down to the nanometer regime, process variations have increasing impact on circuit timing. To address this issue, parameterized statistical static timing analysis (SSTA) has been recently developed. In parameterized SSTA, process variations are represented as random variables (RVs) and timing quantities (delays and others) are expressed as functions of these variables. Most of the existing algorithms to compute the MAX/MIN operations in parameterized SSTA model spatial and path-based statistical dependencies of variation sources using the second-order statistical methods. Unfortunately, such methods have limited capabilities to determine statistical relations between RVs. This results in decreasing the accuracy of the MAX/MIN algorithms, especially when process parameters follow non-Gaussian probability density functions (PDFs) and/or affect timing quantities nonlinearly. In contrast, information theory (IT) provides powerful techniques that allow a natural PDF- based analysis of probabilistic relations between RVs. So, in this paper, we propose a new framework to perform the MAX/MIN operations based on IT concepts. The key ideas behind our framework are: 1) exploiting information entropy to measure unconditional equivalence between an actual MAX/MIN output and its approximate parameterized representation, and 2) using mutual information to measure equivalence of actual and parameterized MAX/MIN outputs from the viewpoint of their statistical relations to process variations. We construct a general IT- based MAX/MIN algorithm that allows a number of particular realizations accounting for statistical properties of parameterized RVs. The experimental results validate the correctness and demonstrate a high accuracy of the new IT-based approach to compute the MAX/MIN. PHYSICAL DESIGN Yan, J. Z. Chu, C. Mak, W.-K. SafeChoice: A Novel Approach to Hypergraph Clustering for Wirelength- Driven Placement http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5875968 This paper presents a completely new approach to the problem of hypergraph clustering for wirelength-driven placement. The novel algorithm we propose is called SafeChoice (SC). Different from all previous approaches, SC is proposed based on a fundamental theorem, safe condition which guarantees that clustering would not degrade the placement wirelength. To mathematically derive such a theorem, we first introduce the concept of safe clustering, i.e., do clustering without degrading the placement quality. To efficiently check the safe condition for pair-wise clustering, we propose a technique called selective enumeration. SafeChoice maintains a global priority queue based on the safeness and area of potential clusters. Using a simple heuristic, it automatically stops clustering when generating more clusters would degrade the placement wirelength. Moreover, we extend SafeChoice to do clustering while considering the object physical locations, i.e., physical clustering. Finally, we apply SafeChoice into a two- phase placement framework and propose a high-quality analytical placement algorithm called SCPlace. Comprehensive experimental results show that the clusters produced by SC consistently help the placer to achieve the best wirelength among all other clustering algorithms, and SCPlace generates the best half-perimeter wirelength compared with all other state-of-the-art placers. Lin, J.-M. Hung, Z.-X. UFO: Unified Convex Optimization Algorithms for Fixed-Outline Floorplanning Considering Pre-Placed Modules http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5875990 Fixed outline floorplanning has recently attracted more attention due to its usefulness in solving real problems in industry. This paper applies two convex optimization methods, named UFO, to solve this problem, which consists of a global distribution stage followed by a local legalization phase. In the first stage, modules are transformed into circles, and a push-pull (PP) model is proposed to uniformly distribute modules over the fixed outline with consideration of their wirelength. Due to the quality of the PP model, we obtain good results after the first stage. Therefore, it is not necessary to consider wirelength in the legalization phase. In order to maintain good results of the first stage, we propose a procedure to extract the geometric relations of the modules from the results of the first stage and store it in constraint graphs. Then, the locations and shapes of the modules are determined by second-order cone programming, which penalizes overlap and obeys the boundary constraints. Finally, we extend the UFO methodology to consider pre-placed modules in a fixed outline. We have implemented two convex functions on MATLAB, and experimental results have demonstrated that UFO clearly outperforms the results reported in the literature on the GSRC and MCNC benchmarks. Chou, S. Han, C.-S. Huang, P.-K. Tien, K.-F. Ho, T.-Y. An Effective and Efficient Framework for Clock Latency Range Aware Clock Network Synthesis http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5875988 In this paper, we present an effective and efficient framework to minimize clock latency range (CLR), which is a crucial objective measuring the process variability of the high-performance clock network. An enhanced deferred- merge embedding algorithm is proposed to handle the skew and slew constraints simultaneously. Besides, instead of using traditional buffering methods that consider only capacitance loading, we adopt slew-constrained buffering for more accurate results. To explore the variation effect with different combinations of buffers and wires in terms of CLR, we design an experiment to examine it and propose an effective buffer and wire sizing scheme. In addition, obstacle avoidance handling is included in our framework. Experimental results show that our framework achieves the best results in terms of CLR compared with any other team in the 2009 ACM ISPD clock network synthesis contest and four state-of-the-art works. TEST Lin, Y.-T. Blanton, R. D. S. METER: Measuring Test Effectiveness Regionally http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5875989 Researchers from both academia and industry continually propose new fault models and test metrics for coping with the ever-changing failure mechanisms exhibited by scaling fabrication processes. Understanding the relative effectiveness of current and proposed metrics and models is vitally important for selecting the best mix of methods for achieving a desired level of quality at reasonable cost. Evaluating metrics and models traditionally relies on actual test experiments, which is time-consuming and expensive. To reduce the cost of evaluating new test metrics, fault models, design-for-test techniques, and others, this paper proposes a new approach, MEeasuring Test Effectiveness Regionally (METER). METER exploits the readily available test-measurement data that is generated from chip failures. The approach does not require the generation and application of new patterns but uses analysis results from existing tests, which we show to be more than sufficient for performing a thorough evaluation of any model or metric of interest. METER is demonstrated by comparing several metrics and models that include: 1) stuck-at; 2) N-detect; 3) PAN-detect (physically-aware N-detect); 4) bridge fault models; and 5) the input pattern fault model (also more recently referred to as the gate-exhaustive metric). We also provide in-depth discussion on the advantages and disadvantages of METER, and contrast its effectiveness with those from the traditional approaches involving the test of actual integrated circuits. Mukherjee, N. Pogiel, A. Rajski, J. Tyszer, J. BIST-Based Fault Diagnosis for Read-Only Memories http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5875994 This paper presents a built-in self-test (BIST)-based scheme for fault diagnosis that can be used to identify permanent failures in embedded read-only memories. The proposed approach offers a simple test flow and does not require intensive interactions between a BIST controller and a tester. The scheme rests on partitioning of rows and columns of the memory array by employing low cost test logic. It is designed to meet requirements of at-speed test thus enabling detection of timing defects. Experimental results confirm high diagnostic accuracy of the proposed scheme and its time efficiency.