Uncertainty in circuit performance due to manufacturing and environmental variations is increasing with each new generation of technology. It is therefore important to predict the performance of a chip as a probabilistic quantity. This paper proposes three novel path-based algorithms for statistical timing analysis and parametric yield prediction of digital integrated circuits. The methods have been implemented in the context of the EinsTimer static timing analyzer. The three methods are complementary in that they are designed to target different process variation conditions that occur in practice. Numerical results are presented to study the strengths and weaknesses of these complementary approaches. Timing analysis results in the face of statistical temperature and Vddvariations are presented on an industrial ASIC part on which a bounded timing methodology leads to surprisingly wrong results

Uncertainty in circuit performance due to manufacturing and environmental variations is increasing with each new generation of technology. It is therefore important to predict the performance of a chip as a probabilistic quantity. This paper proposes three novel algorithms for statistical timing analysis and parametric yield prediction of digital integrated circuits. The methods have been implemented in the context of the EinsTimer static timing analyzer. Numerical results are presented to study the strengths and weaknesses of these complementary approaches. Across-the-chip variability continues to be accommodated by EinsTimer's "Linear Combination of Delay (LCD)" mode. Timing analysis results in the face of statistical temperature and Vdd variations are presented on an industrial ASIC part on which a bounded timing methodology leads to surprisingly wrong results.

This paper presents a method that, during scheduling of DSP algorithms, handles constraints of storage files with FIFOs or stacks together with resource and timing constraints. Constraint analysis techniques and the characteristics of the exact coloring of conflict graphs are used to identify values that are bottlenecks for storage assignment with the aim of ordering their accesses. This is done with pairs of values until it can guarantee that all constraints will be satisfied.

Tight data- and timing constraints are imposed by communication and multimedia applications. The architecture for the embedded processor implies resource constraints. Instead of random-access registers, relative location storages or rotating register files are used to exploit the available parallelism of resources by means of reducing the initiation interval in pipelined schedules. Therefore, the compiler or synthesis tool must deal with the difficult tasks of scheduling of operations and location assignment of values while respecting all the constraints including the storage file capacity. This paper presents a method that handles constraints of relative location storages during scheduling together with timing and resource constraints. The characteristics of the coloring of conflict graphs, representing the relative overlap of value instances, are analyzed in order to identify the bottlenecks for location assignment with the aim of serializing their lifetimes. This is done with pairs of loop instances of values until it can be guaranteed that all constraints will be satisfied.

This paper reviews aspects of the field of design technology (also addressed as "computer aided design" or as "design automation") for electronic systems as it developed over the last 40 years. The point of observation is based in Europe. Yet it is the intention of the author to maintain a worldwide scope-for as much as he is able to do. We will look at the early computers and how they triggered the first experiments in solving electronic design problems. Then we will review the first attempts of circuit simulation and layout synthesis. This is followed by a description of design technology progress in the 1970s and the early 1980s. We continue with an interlude giving some historical background of the European social and industrial arena and its influence on the industrial impact of the design technology field. Then the story turns back to the field itself and looks at the issue of design and description languages and the underlying semantic models. This is in fact the opening to a chapter on high-level synthesis, architectures and the co-design of hardware and software, scratching the surface of the very important issue of embedded systems. Eventually, a view is opened on the spectrum of products to come, which will reduce the computer to a commodity. Rather, this spectrum will encompass the entire field of communication in any phase of life. Finally, the story closes with the most prominent demands faced by the design technology field as the electronics industry sets out to fulfill all the promises that silicon manufacturing suggests.

Code generation methods for digital signal processors are increasingly hampered by the combination of tight timing constraints imposed by signal p processing applications and resource constraints implied by the processor architecture. In particular, limited resource availability (e.g.registers) poses a problem for traditional methods that perform code generation in separate stages (e.g., scheduling followed by register binding). This separation often results in suboptimality (or even infeasibility) of the generated solutions because it ignores the problem of phase coupling (e.g., since value lifetimes are a result of scheduling, scheduling affects the solution space for register binding). As a result, traditional methods need an increasing amount of help from the programmer (or designer) to arrive at a feasible solution. Because this requires an excessive amount of design time and extensive knowledge of the processor architecture, there is a need for automated techniques that can cope with the different kinds of contraints during scheduling. By exploiting these constraints to prune the schedule search space, the scheduler is often prevented from making a decision that inevitably violates one or more constraints. FACTS is a research tool developed for this purpose. In this paper we will elucidate the philosophy and concepts of FACTS and demonstrate them on a number of examples.

In the high-level synthesis of ASICs or in the code generation for ASIPs, the presence of conditionals in the behavioral description represents an obstacle to exploit parallelism. Most existing methods use greedy choices in such a way that the search space is limited by the applied heuristics. For example, they might miss opportunities to optimize across basic block boundaries when treating conditional execution. We propose a constructive method which allows generalized code motions. Scheduling and code motion are encoded in the form of a unified resource-constrained optimization problem. In our approach many alternative solutions are constructed and explored by a search algorithm, while optimal solutions are kept in the search space. Our method can cope with issues like speculative execution and code such duplication. Moreover, it can tackle constraints imposed by the advance choice of a controller, such as pipelined-control delay and limited branch capabilities. The underlying timing models support chaining and multicycling. As tasking code motion into account may lead to a larger search space, a code-motion pruning technique is presented. This pruning is proven to keep optimal solutions in the search space for cost functions in terms of schedule lengths.

Article Free Access Share on A reordering technique for efficient code motion Authors: Luiz C. V. dos Santos Design Automation Section, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands Design Automation Section, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The NetherlandsView Profile , Jochen A. G. Jess Design Automation Section, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands Design Automation Section, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The NetherlandsView Profile Authors Info & Claims DAC '99: Proceedings of the 36th annual ACM/IEEE Design Automation ConferenceJune 1999 Pages 296–299https://doi.org/10.1145/309847.309935Published:01 June 1999Publication History 17citation240DownloadsMetricsTotal Citations17Total Downloads240Last 12 Months15Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Emerging design problems are prompting the use of code motion and speculation in high-level synthesis to shorten schedules and meet tight time-constraints. Unfortunately, they may increase the number of states to an extent not always affordable for embedded systems. We propose a new technique that not only leads to less states, but also speeds up scheduling. Equivalent states are predicted and merged while building the finite state machine. Experiments indicate that flexible code motions can be used, since our technique restrains state expansion.

Code generation methods for digital signal processing (DSP) applications are hampered by the combination of tight timing constraints imposed by the performance requirements of DSP algorithms and resource constraints imposed by a hardware architecture. In this paper, we present a method for register binding and instruction scheduling based on the exploitation and analysis of the combination of resource and timing constraints. The analysis identifies implicit sequencing relations between operations in addition to the preceding constraints. Without the explicit modeling of these sequencing constraints, a scheduler is often not capable of finding a solution that satisfies the timing and resource constraints. The presented approach results in an efficient method to obtain high-quality instruction schedules with low register requirements.

The demands in terms of processing performance, communication bandwidth and real-time throughput of many multimedia applications are much higher than today's processing architectures can deliver. The PROPHID heterogeneous multiprocessor architecture template aims to bridge this gap. The template contains a general purpose processor connected to a central bus, as well as several high-performance application domain specific processors. A high-throughput communication network is used to meet the high bandwidth requirements between these processors. In this network multiple time-division-multiplexed data streams are transferred over several parallel physical channels. This paper presents a method for guaranteeing the throughput for hard-real-time streams in such a network. At compile time sufficient bandwidth is assigned to these streams. The assignment can be determined in polynomial time. Remaining bandwidth is assigned to soft-real-time streams at run time. We thus achieve efficient stream communication with guaranteed performance.

Code generation methods for DSP applications are hampered by the combination of tight timing constraints imposed by the performance requirements of DSP algorithms, and resource constraints imposed by a hardware architecture. In this paper we present a method for register binding and instruction scheduling based on the exploitation and analysis of resource and timing constraints. The analysis identifies sequencing constraints between operations additional to the precedence constraints. Without the explicit modeling of these sequencing constraints, a scheduler is often not capable of finding a solution that satisfies the timing, resource and register constraints. The presented approach results in an efficient method of obtaining high quality instruction schedules with low register requirements.

PROPHID is a design method aiming at high-performance systems with a focus on high-throughput signal processing for multimedia applications. The processing and communication bandwidth requirements of such systems are very high. To obtain a good balance between performance, programmability and efficiency in terms of speed, area and power PROPHID uses a novel heterogeneous multi-processor architecture template which exploits task-level concurrency. A general purpose processor aimed at control-oriented tasks and low to medium-performance signal processing tasks, as well as application domain specific processors aimed at high-performance signal processing tasks are available in this template. Next to a central control-oriented bus a special high-throughput communication network is used to meet the high bandwidth requirements of the application domain specific processors. This paper discusses the characteristics and advantages of the PROPHID architecture showing that high performance is obtained by embedding multiple autonomous data-driven processors in a stream-based communication environment.

The gate sizing problem is the problem of finding load drive capabilities for all gates in a given Boolean network such, that a given delay limit is kept, and the necessary cost in terms of active area usage and/or power consumption is minimal. This paper describes a way to obtain the entire cost versus delay tradeoff curve of a combinational logic circuit in an efficient way. Every point on the resulting curve is the global optimum of the corresponding gate sizing problem. The problem is solved by mapping it onto piecewise linear models in such a way, that a piecewise linear (circuit) simulator can do the job. It is shown that this setup is very efficient, and can produce tradeoff curves for large circuits (thousands of gates) in a few minutes. Benchmark results for the entire set of MCNC '91 two-level examples are given.

This paper presents an alternative modeling and simulation method for CMOS bridging faults. The significance of the method is the introduction of a set of generic-bridge tables which characterize the bridged outputs for each bridge and a set of generic-cell tables which characterize how each cell propagates a logically undefined input. These two sets of tables are derived dynamically for a specific design by using a SPICE circuit simulator. Then they can be used by any logic fault simulator to simulate bridging faults. In this way, the proposed method can perform very fast bridging fault simulation yet with SPICE accuracy. The paper shows how these two sets of tables are derived and used in a parallel pattern fault simulator. Experimental results on ISCAS85 benchmarks are promising.

No abstract available.

Application domain specific DSP cores are becoming increasingly popular due to their advantageous trade--off between flexibility and cost. However, existing code generation methods are hampered by the combination of tight timing and resource constraints, imposed by the throughput requirements of DSP algorithms together with a fixed core architecture. In this paper, we present a method to model resource and instruction set conflicts uniformly and statically before scheduling. With the model we exploit the combination of all possible constraints, instead of being hampered by them. The approach results in an exact and run time efficient method to solve the instruction scheduling problem, which is illustrated by real life examples. 1. Introduction Predefined DSP cores which are tuned towards specific application domains are becoming increasingly popular, due to their advantageous trade--off between flexibility and cost. Such a core is relatively flexible in comparison to an ASIC: differen...

The impact of spot defects on the susceptibility for electrical failure of a net is analyzed. Basedon this analysis, a general routing cost function is presented, in which the manufacturability of a net is taken into account in conjunction with the traditional routing objectives. The new cost function, relating the process spot defects to the routing procedure has been implemented. For the benchmark layouts obtained by both the original routing tool and the new routing module, the failure probabilities are analyzed. The results show that the failure probability of a layout is significantly decreased if the spot defect mechanism is taken into account in the routing procedure, while the area of the layout is kept constant. 1 Introduction Routing a net is a "classical" topic in CAD for VLSI. The problem can be formalized as the Minimum Steiner Tree problem in an appropriate routing graph [Len90]: Problem: Minimum Steiner Tree Instance: Aconnected undirected graph G(V, E), also called ...

In this paper a flexible interface to high-level synthesis data (NEAT) is presented. NEAT offers three design views to common high-level synthesis data domains. Inter- and intra-domain relations are used to represent design relations between synthesis objects and to store synthesis results. To extend the functionality of the common synthesis interface programmers use object oriented programming techniques to create their own specific synthesis interface. Interaction between high-level synthesis tools is achieved by exchanging data using a common file-format, which can easily be extended. A graphical interface has been established to allow interactive interpretation and manipulation of synthesis results. NEAT offers unlimited extendibility and no restrictions towards synthesis trajectories, and therefore is highly suitable as a research platform.>

Execution intervals are commonly used in high-level synthesis systems to identify the relation between operations and the cycle steps in which they possibly can be scheduled. These intervals are normally based on the ASAP (as soon as possible) and ALAP (as late as possible) values of operations under the assumption of unlimited resources. In this paper a novel and much more accurate execution interval analysis is presented for designs on which resource constraints are imposed. The analysis prunes the search space of schedulers without limiting the solution space and therefore enhances the quality of schedulers. The method is based on a bipartite graph matching formulation and runs in polynomial time. Well-known benchmarks show the positive effects of the approach on scheduling results and run times.

In this paper, a net-oriented method to analyze realistic faults is presented. The key point of the method is to analyze the faults caused by a spot defect net by net. First the possible faults related to a net are extracted. Hence all faults in a layout are extracted by enumerating all nets on the layout. An approach to calculate the critical area with respect to each fault is also described. A formula is proposed to compute the fault weight theoretically instead of weighting a fault by counting the number of appearances of the fault. The proposed method has been implemented on a HP750 workstation. To demonstrate its practical performance, all layouts in iscas85 benchmarks as well as some other layouts ranging from 450 to 28,000 transistors have been analyzed. The results show that our method is much faster than other approaches published in literature.

This paper presents a new modeling and simulation technique for CMOS opens. The significance of the method is that both the hazard and charge-sharing effects of all possible opens are modeled in terms of a set of detecting conditions. They are efficiently represented at logic level. Then during fault simulations only these detecting conditions are evaluated to decide if the opens are detected. In this way, all efficient simulation techniques developed at logic level can be applied. The paper shows how the detecting conditions are derived for arbitrary opens. Results of a parallel pattern simulator show a good trade-off of accuracy versus efficiency.>

Complex tests are often required for the measurement of certain IC parameters. Because these tests are too expensive to include in a production test, an alternative test method is studied. Additional structures that behave identically with respect to the considered parameter, called monitors, are placed near the original structures. If a strong spatial correlation exists for the parameter, the parameter values of the monitors can be used to predict the parameter values of the products. It is shown that, by means of monitor measurement data regression, the prediction can be improved. An analysis of the resulting prediction error is presented, which is used to evaluate the method for specific cases.>

CMOS bridge faults have very complex behavior and make the testing difficult. This paper proposes a new technique to model all types of bridges as faulty boolean expressions. The modeling is based on analyzing the affected subcircuits using a simplified transistor model. Experiments show that this way of modeling is a good tradeoff of accuracy versus efficiency and allows fast evaluation of test patterns for large circuits.>

A general approach to gate array routing based on an abstract routing space model is presented. An efficient k-terminal net maze runner is described. It does not partition nets into two-terminal net routing problems, but solves the problem by simultaneously growing k search waves. It is shown that the explored routing space diminishes when compared to bidirectional routing schemes. Experimental data show a reduction of CPU time up to 55% and a decrease of total net length up to 6% compared to a bidirectional maze router. For k-terminal nets it is shown that net length decreases with increasing k. Additional routing space restriction is attained by use of variable search space restriction and by the introduction of a dynamic routing space partitioning method based on the concept of regions. This concept allows for determination of nonroutable nets or parts of nets in an efficient way. The new partitioning method may be implemented in any maze runner without increasing the complexity of the maze runner algorithm. Results show an additional decrease of CPU time up to 35%.>

Nowadays, the IC features are still becoming smaller, the areas larger and the packing densities higher. Thus, the occurrence of defects has a growing impact on production yields. Defect monitoring systems are widely used to obtain information about these defects. This paper describes a process-independent method to develop such a defect monitoring system. This implies that rules are given for the design of the monitor, the required resistance measurements, the applied data processing and the data presentation. This method can be applied to design monitors for various applications. For example, the monitor can contain one or more layers and can be process or product-related. An application of the method is also shown.

A method based on a deterministic geometrical construction of critical areas is presented for determining the sensitivity of layouts to spot defects. The models for fatal faults considered are bridges and cuts related to patterns in one layer. The approach, based on the concept of susceptible sites, has a complexity O(N log N), where N is the number of line segments. Only two scans are necessary to extract all susceptible sites, which then are used to compute the critical areas for a whole set of points in a domain of defect size.>

The authors report research concerning the effects of inaccurate silicon processing on integrated circuits. To acquire information about defective processing steps, electrical measurements applied to defect monitors or product yield modules (PYMs) are proposed. The authors describe two such PYMs derived from a 128K SRAM matrix, as well as the kinds of measurements that should be carried out and the way they should be evaluated to obtain defect density data for yield prediction. In addition, the authors present some new theoretical results concerning the actual ability of defect monitors to deliver reliable results. They also consider the complexity of the measuring procedure. It turns out that, depending on the flexibility of the experimental setup, this complexity is more significantly dependent on the number of defects to be detected than on the complexity of the monitor structure.>

An interactive environment is presented for the analysis of yield information required on modern integrated circuit manufacturing lines. The system estimates wafer yields and wafer-yield variations, quantifies regional yield variations within wafers, identifies clusters in wafers and/or in lots, and is able to predict wafer yields via simple simulation tools. An analysis approach based on site yields makes the system independent of the product and of the technology. The analysis technique makes it possible to investigate the effects of both correlated and uncorrelated sources of yield loss. The statistical information obtained can be used to study changes in the technological process. Graphical displays in the form of wafer maps are used to represent the spatial distribution of dice in the wafer. Capabilities for such as radial and angular distribution analyses, among others, are provided to examine data, and hypothetical wafer maps are created to visualize and predict simulated wafer yields.>

A novel approach to technology mapping that produces a standard-cell IC implementation from a previously optimized and decomposed set of Boolean functions is presented. Instead of trying to solve the problem for random libraries of standard cells, which proved to be very difficult, it has been solved for cell generators, which are only limited by technology constraints. The completeness of the sets of cells that can be generated by a cell generator, given a certain technology, makes it possible to use an elegant mapping algorithm. The algorithm was coded in CommonLISP, and used to map a large number of benchmark examples. The results compare favorably with published results.>

Some new results are presented concerning the pivoting of large systems of linear equations with respect to parallel processing techniques. It will be assumed that the processing of a pivot takes one time slot. The pivoting problem is studied by means of an associated graph model. Given a triangulated graph a set of label classes is established. Class k contains all pivots which may be processed in parallel during the kth time slot. The label classes are used to establish the elimination-tree (e-tree). The e-tree is a spanning tree for the given graph. The critical path in the e-tree indicates the minimum number of time slots necessary to complete the L/U-decomposition. Furthermore, the earliest and latest admissible time slot for the processing of every pivot may be derived, such that the critical path is not affected. The e-tree can be seen as a data structure to guide parallel processing based on sparsity.