waashk/dblp huggingface dataset:
definition and solution of the memory packing problem for field-programmable systems. this paper defines a new optimization problem that arises in the use of a field-programmable system (fps). an fps consists of a set of field-programmable gate arrays and memories, and is used both for emulation of asics and computation. in both cases the application circuits will include a set of memories which may not match the number and aspect ratio of the physical memories available on the fps. this can often require that the physical memories be time-multiplexed to implement the required memories, in a circuit we call a memory organizer.we give a precise definition of the packing optimization problem and present an algorithm for its solution. the algorithm has been implemented in a cad tool that automatically produces a memory organizer circuit ready for synthesis by a commercial fpga tool set.
sub-90nm technologies: challenges and opportunities for cad. future high performance microprocessor design with technology scaling beyond 90nm will pose two major challenges: (1) energy and power, and (2) parameter variations. design practice will have to change from deterministic design to probabilistic and statistical design. this paper discusses circuit techniques and design automation opportunities to overcome the challenges.
an empirical model for accurate estimation of routing delay in fpgas. we present an empirical routing delay model for estimating interconnection delays in fpgas. we assume that the routing delay is a function of interplc distances, circuit size, fanout of the net and routing congestion in the channel. we performed extensive simulations of various circuits to generate a sufficiently large dataset. our method estimates delays by reading the average value tables and interpolating the values, if necessary. we present a rigorous statistical justification of this delay model. our results show that our method predicts the delays within 20% of actual and it far outperforms all other existing techniques.
an "effective" capacitance based delay metric for rc interconnect. efficient, yet accurate delay estimation for rc interconnect is required for the optimization loop of timing-driven physical design tools. for many applications, the elmore delay metric [4] has been widely used due to its efficiency and ease of use. however, it is well known that the elmore metric can have significant error since it ignores the resistive shielding of down-stream capacitance. we present a new interconnect metric called ecm that accounts for this resistive shielding by computing an effective capacitance to model the downstream capacitance. ecm can also be computed with the same complexity as the elmore delay and does not require the computation of moments. experiments show that ecm is significantly more accurate than elmore delay and is competitive with other metrics that use multiple moments.
analytical modeling of crosstalk noise waveforms using weibull function. to analyze the failure of a cmos circuit due to glitches induced by capacitive crosstalk, noise immunity curves (a.k.a. noise rejection curve) must be characterized. however, noise waveform models currently used for characterization such as ideal triangle and trapezoid can underestimate the propagated noise pulse by over 20% and result in missed violations. we provide an analytical solution to fit any given crosstalk noise waveform to a weibull function, which can generate identical propagated glitch heights compared to spice, resulting in accurate noise immunity curves.
predictable routing. predictable routing is the concept of using prespecified patterns to route a net. by doing this, we allow an more accurate prediction mechanism for metrics such as congestion and wirelength earlier in the design flow. additionally, we can better plan the routes, insert buffers and perform wire sizing earlier. with comparable routing quality, we show that we can predictably route up to 80% of a selected subset of nets. also, we introduce methods for finding a group of nets which can be predictably routed.
instruction generation for hybrid reconfigurable systems. in this work, we present an algorithm for simultaneous template generation and matching. the algorithm profiles the graph and iteratively contracts edges to create the templates. the algorithm is general and can be applied to any type of graph, including directed graphs and hypergraphs. we discuss how to target the algorithm towards the novel problem of instruction generation and selection for a hybrid (re)configurable systems. in particular, we target the strategically programmable system, which embeds complex computational units like alus, ip blocks, etc. into a configurable fabric. we argue that an essential compilation step for these systems is instruction generation, as it is needed to specify the functionality of the embedded computational units. additionally, instruction generation can be used to create soft macros -- tightly sequenced pre-specified operations placed in the configurable fabric.
a robust cell-level crosstalk delay change analysis. in this work we present a robust and efficient methodology for crosstalk-induced delay change analysis for asic design styles. the approach employs optimization methods to search for worst aggressor alignment, and it computes crosstalk induced delay change on each stage considering an impact on downstream logic. computational efficiency is achieved using pre-characterized current models for drivers and compact macromodels for interconnect. the proposed methodology has been implemented in a commercial noise analysis tool. experimental results obtained on industrial designs demonstrate high accuracy and reduced pessimism of the proposed methodology.
delay budgeting for a timing-closure-driven design method. in this paper, we present an rtl delay-budgeting approach for a timing-closure-driven design method. we formulate the delay-budgeting problem into the lagrange-multipliers-based slack distribution problem. we present two algorithms, namely the balanced slack distribution algorithm and the at-based (area-time) slack distribution algorithm, to solve the problem. we also present a timing-closure-driven design flow by integrating commercial synthesis/layout tools with the proposed algorithms. we have demonstrated the viability of the proposed rtl delay-budgeting method. the results show that without an accurate at-characteristic projection of modules the balanced slack distribution algorithm will be a good choice for delay budgeting at rtl.
variational analysis of large power grids by exploring statistical sampling sharing and spatial locality. we propose a parametric random walk algorithm to facilitate a feasible evaluation of a few critical network nodes under the influence of a large number of variation sources in a power grid. by combining statistical sampling sharing with random walks, we devise an efficient localized sensitivity analysis for large power distribution networks such that the analysis can be conducted without solving the complete network. we further show that this sampling-based parametric analysis can be extended from the first order sensitivity analysis to a more accurate second order analysis. by exploiting the natural spatial locality inherent in our algorithm formulation, the second order parametric analysis can be conducted very efficiently even for a large number of global and local variation sources. the proposed approach is demonstrated by analyzing large power grids under the influence of process and current loading variations to which the application of the standard brutal-force circuit simulation becomes completely infeasible. our results have demonstrated the superior performance of the proposed algorithm both in terms of accuracy and runtime.
the feasibility of on-chip interconnection using antennas. the feasibility of integrating antennas and required circuits to form wireless interconnects in foundry digital cmos technologies has been demonstrated. the key challenges including the effects of metal structures associated with integrated circuits, heat removal, packaging, and interaction of transmitted and received signals with nearby circuits appear to be manageable. besides, on-chip interconnection, this technology can potentially be applied for implementation of true single chip radio and radar, interchip communication systems, rfid tags and others.
analysis and optimization of substrate noise coupling in single-chip rf transceiver design. the relentless move toward single chip integration of rf, analog and digital blocks results in significant noise coupling effects that can degrade performance and hence, should be controlled. in this paper, we propose a practical methodology that uses a suite of commercial tools in combination with a high-speed extractor based on an innovative semi-analytical method to deal with noise coupling problems, and enable rf designers to achieve a first silicon-success of their chips. the integration of the methodology in a typical rf design flow is illustrated and its successful application to achieve a single-chip integration of a transceiver demonstrated.
stable and efficient reduction of substrate model networks using congruence transforms. parasitic analog-digital noise coupling has been identified as a key issue facing designers of mixed-signal integrated circuits. in particular, signal cross talk through the common chip substrate has become increasingly problematic. this paper demonstrates a new methodology for developing simulation, synthesis, and verification models to analyze the global electrical behavior of the non-ideal semiconductor substrate. rc substrate network models, which are generated via a triangular discretization method, are accurately approximated for subsequent analysis by an efficient reduction algorithm. this algorithm utilizes the well-conditioned lanczos process to formulate pade approximations of the network port admittance. congruence transformations are employed to ensure stability, and to create reduced networks which are easily realizable with spice-compatible rc elements. for validation, the strategy has been successfully applied to several mixed-signal circuit examples.
incremental partitioning-based vectorless power grid verification. to ensure reliable performance of a chip, design verification of the power grid is of critical importance. this paper builds on previous work that models the working behavior of the circuit in terms of abstracted current constraints and solves for worst-case voltage drop on the grid as a linear program. the main motivation is to allow the efficient verification of local power grid sections or blocks, enabling incremental design analysis of the grid. this approach substantially improves the computational time by reducing the problem size and the constraint set and replacing them by black box macromodels. this increase the capacity of the solver to handle industrial sized grids.
standby power optimization via transistor sizing and dual threshold voltage assignment. this paper presents a novel enumerative approach, with provable and efficient pruning techniques, for dual threshold voltage (vt) assignment at the transistor level. since the use of low vt may entail a substantial increase in leakage power, we formulate the problem as one of combined optimization for leakage-delay tradeoffs under vt optimization and sizing. based on an analysis of the effects of these two transforms on the delay and leakage, we justify a two-step procedure for performing this optimization. results are presented on the iscas85 benchmark suite favorably comparing our approach with an existing sensitivity-based optimizer.
clock skew scheduling for improved reliability via quadratic programming. this paper considers the problem of determining an optimal clock skew schedule for a synchronous vlsi circuit. a novel formulation of clock skew scheduling as a constrained quadratic programming (qp) problem is introduced. the concept of a permissible range, or a valid interval, for the clock skew of each local data path is key to this qp approach. from a reliability perspective, the ideal clock schedule corresponds to each clock skew within the circuit being at the center of the respective permissible range. however, this ideal clock schedule is not practically implementable because of limitations imposed by the connectivity among the registers within the circuit. to evaluate the reliability, a quadratic cost function is introduced as the euclidean distance between the ideal schedule and a given practically feasible clock schedule. this cost function is the minimization objective of the described algorithms for the solution of the previously mentioned quadratic program. furthermore, the work described here substantially differs from previous research in that it permits complete control over specific clock signal delays or skews within the circuit. specifically, the algorithms described here can be employed to obtain results with explicitly specified target values of important clock delays/skews with a circuit, such as for example, the clock delays/skews for i/o registers. an additional benefit is a potential reduction in clock period of up to 10%. an efficient mathematical algorithm is derived for the solution of the qp problem with &ogr;(r3) run time complexity and &ogr;(r2) storage complexity, where r is the number of registers in the circuit. the algorithm is implemented as a c++ program and demonstrated on the iscas'89 suite of benchmark circuits as well as on a number of industrial circuits. the work described here yields additional insights into the correlation between circuit structure and circuit timing by characterizing the degree to which specific signal paths limit the overall performance and reliability of a circuit. this information is directly applicable to logic and architectural synthesis.
symbolic debugging scheme for optimized hardware and software. symbolic debuggers are system development tools that can accelerate the validation speed of behavioral specifications by allowing a user to interact with an executing code at the source level. in response to a user query, the debugger retrieves the value of a source variable in a manner consistent with respect to the source statement where execution has halted. however, when a behavioral specification has been optimized using transformations, values of variables may be inaccessible in the run-time state.we have developed a set of techniques that, given a behavioral specification cdfg, enforce computation of a selected subset vcut of user variables such that (i) all other variables v &isin; cdfg can be computed from vcut and (ii) this enforcement has minimal impact on the optimization potential of the computation. the implementation of the new debugging approach poses several optimization tasks. we have formulated the optimization tasks and developed heuristics to solve them. the effectiveness of the approach has been demonstrated on a set of benchmark designs.
zero skew clock routing in multiple-clock synchronous systems. a clock routing algorithm for two-phase clock systems is presented. the algorithm, which minimizes both intraclock skew and interclock skew, has been implemented on sparc 1+ in c and has been tested on several industrial benchmarks as well as on randomly generated examples. in particular, the result was tested for a 267 synchronous component circuit at clock rates of 100 mhz. it is significant that this is the first ever result which deals with multiple clock routing with zero skew
static verification of test vectors for ir drop failure. atpg tools generate test vectors assuming zero delay model forlogic gates.in reality, however, gates have finite rise and falldelays that are dependent on process, voltage, and temperaturevariations across different dies on a wafer and within a die.a testengineer must verify the vectors for timing correctness before theyare handed off to the product engineer.currently, validation oftests is done using dynamic simulation of the circuit using the testvectors.a test vector is invalidated if it cannot reliably distinguishbetween a good and a faulty circuit under the signal placement andobservation error window of the tester equipment.since structuraltests can result in much more switching activity in the circuit thanwhat is estimated during normal functioning, the ir drop in thepower & ground lines can be significant, adversely impacting pathdelays.as a result, the validation performed by simulation can beerror prone.oversizing the power rails to address this problemimpacts the yield.we therefore propose the verification of testvectors for ir drop failure and present a flow for identifyingfailing vectors.attempting to address this verification in dynamicsimulation will force the use of circuit simulation or mixed-levelsimulation techniques, which are expensive in terms of run time.we discuss a static approach to validate the test vectors for failurein the presence of ir drop problems.
efficient mixed-domain analysis of electrostatic mems. we present efficient computational methods for scattered point and meshless analysis of electrostatic microelectromechanical systems (mems). electrostatic mems are governed by coupled mechanical and electrostatic energy domains. a self-consistent analysis of electrostatic mems is implemented by combining a finite cloud method based interior mechanical analysis with a boundary cloud method based exterior electrostatic analysis. lagrangian descriptions are used for both mechanical and electrostatic analyses. meshless finite cloud and boundary cloud methods combined with fast algorithms and lagrangian descriptions are flexible, efficient and attractive alternatives compared to conventional finite element/boundary element methods for self-consistent electromechanical analysis. numerical results are presented for an electrostatic comb drive device.
a probabilistic approach to buffer insertion. this work presents a formal probabilistic approach for solving optimizationproblems in design automation. prediction accuracy isvery low especially at high levels of design flow. this can be attributedmainly to unawareness of low level layout information andvariability in fabrication process. hence a traditional deterministicdesign automation approach where each cost function is representedas a fixed value becomes obsolete. a new approach is gainingattention in which the cost functions are representedas probability distributions and the optimization criteriais probabilistic too. this design optimization philosophy is demonstratedthrough the classic buffer insertion problem. formally,we capture wirelengths as probability distributions (as compared tothe traditional approach which considers wirelength as fixed values)and present several strategies for optimizing the probabilisticcriteria. during the course of this work many problems are provedto be np-complete. comparisons are made with the van-ginneken"optimal under fixed wire-length" algorithm. results show that thevan-ginneken approach generated delay distributions at the root ofthe fanout wiring tree which had large probability (0.91 in the worstcase and 0.55 on average) of violating the delay constraint. ouralgorithms could achieve 100% probability of satisfying the delayconstraint with similar buffer penalty. although this work considerswirelength prediction inaccuracies, our probabilistic strategy couldbe extended trivially to consider fabrication variability in wire parasitics.
hybrid techniques for electrostatic analysis of nanowires. we propose an efficient approach, namely the hybrid bie/poisson/schrodinger approach, for electrostatic analysis of nanowires. in this approach, the interior and the exterior domain electrostatics are described by poisson's equation (or poisson's equation coupled with schrodinger's equation when quantum-mechanical effects are dominant) and the boundary integral formulation of the potential equation, respectively. we employ a meshless finite cloud method and a boundary cloud method to solve the coupled equations self-consistently. the proposed approach significantly reduces the computational cost and provides a higher accuracy of the solution.
efficient statistical timing analysis through error budgeting. we propose a technique for optimizing the runtime in statistical timing analysis. given a global acceptable error budget at the primary output which signifies the difference in the area of the accurate and approximate timing cdfs, we propose a formulation of budgeting this global error across all nodes in the circuit. this node error budget is used to simplify the computation of arrival time cdfs at each node using approximations. this simplification reduces the runtime of statistical timing analysis. we investigate two ways of exploiting this node error budget, firstly through piecewise linear approximation (see ibid., a. devgan and c. kashyap, 2003) and secondly though hierarchical quadratic approximation. experimental results on iscas/mcnc benchmarks show that our approach is at most 3 times faster than accurate statistical timing analysis and had a very small error. we also found quadratic piecewise approximation to be more accurate than linear approximation but at lesser gains in runtime.
accurate power estimation for large sequential circuits. a power estimation approach is presented in which blocks of consecutive vectors are selected at random from a user-supplied realistic input vector set and the circuit is simulated for each block starting from an unknown state. this leads to two (upper and lower) bounds on the desired power value which can be quite tight (under 10% difference between the two in many cases). as a result, the power dissipation is obtained by simulating only a fraction of the potentially very large vector set.
leakage control through fine-grained placement and sizing of sleep transistors. leakage power is increasingly gaining importance with technology scaling. multi-threshold cmos (mtcmos) technology has become a popular technique for standby power reduction. sleep transistor insertion in circuits is an effective application of mtcmos technology for reducing leakage power. in this work we present a fine grained approach where each gate in the circuit is provided an independent sleep transistor. key advantages of this approach include better circuit slack utilization and improvements in signal integrity (which is a major disadvantage in clustering based approaches). to this end, we propose an optimal polynomial time fine grained sleep transistor sizing algorithm. we also prove the selective sleep transistor placement problem as np-complete and propose an effective heuristic. finally, in order to reduce the sleep transistor area penalty (which might get high since clustering is not performed), we propose a placement area constrained sleep transistor sizing formulation. our experiments show that on an average the sleep transistor placement and optimal sizing algorithm gave 69.7% and 59.0% savings in leakage power as compared to the conventional fixed delay penalty algorithms for 5 and 7% circuit slowdown respectively. moreover the post placement area penalty was less than 5% which is comparable to clustering schemes according to mohab anis et al. (2003).
integrating program transformations in the memory-based synthesis of image and video algorithms. in this paper we discuss the interaction and integration of two important program transformations in high-level synthesis&mdash;tree height reduction and redundant memory-access elimination. intuitively, these program transformations do not interfere with one another as they optimize different operations in the program graph and different resources in the synthesized system. however, we demonstrate that integration of the two tasks is necessary to better utilize available resources. our approach involves the use of a &ldquo;meta-transformation&rdquo; to guide transformation application as possibilities arise. results observed on several image and video benchmarks demonstrate that transformation integration increases performance through better resource utilization.