Fast Test Pattern Generation for Sequential Circuits Using Decision Diagram Representations

The paper presents a novel hierarchical approach to test pattern generation for sequential circuits based on an input model of mixed-level decision diagrams. A method that handles, both, data and control parts of the design in a uniform manner is proposed. The method combines deterministic and simulation-based techniques. On the register-transfer level, deterministic path activation is combined with simulation based-techniques used for constraints solving. The gate-level local test patterns for components are randomly generated driven by high-level constraints and partial path activation solutions. Experiments show that high fault coverages for circuits with complex sequential structures can be achieved in a very short time by using this approach.     

Analyzing and exploiting the structure of the constraints in theILP approach to the scheduling problem

In integer linear programming (ILP), formulating a “good” model is of crucial importance to solving that model. In this paper, we begin with a mathematical analysis of the structure of the assignment, timing, and resource constraints in high-level synthesis, and then evaluate the structure of the scheduling polytope described by these constraints. We then show how the structure of the constraints can be exploited to develop a well-structured ILP formulation, which can serve as a solid theoretical foundation for future improvement. As a start in that direction, we also present two methods to further tighten the formulation. The contribution of this paper is twofold: 1) it provides the first in-depth formal analysis of the structure of the constraints, and it shows how to exploit that structure in a well-designed ILP formulation, and 2) it shows how to further improve a well-structured formulation by adding new valid inequalities     

Constraint-based model for network service provisioning

As the network services deployed over the Internet become more complex, their configurations are more difficult to manage. The constraints that exist among the network service configuration parameters are an important source of complexity in the configuration, validation and fault management processes. Existing solutions do not provide adequate high-level models to capture and integrate various types of configuration constraints. It is therefore necessary to adopt a structured approach in order to solve this problem. Thus, in this paper, we propose a structured and integrated constraint-based model for network service configuration, validation and fault management.     

Phase-Coupled Mapping of Data Flow Graphs to Irregular Data Paths

Many software compilers for embedded processors produce machine code of insufficient quality. Since for most applications software must meet tight code speed and size constraints, embedded software is still largely developed in assembly language. In order to eliminate this bottleneck and to enable the use of high-level language compilers also for embedded software, new code generation and optimization techniques are required. This paper describes a novel code generation technique for embedded processors with irregular data path architectures, such as typically found in fixed-point DSPs. The proposed code generation technique maps data flow graph representation of a program into highly efficient machine code for a target processor modeled by instruction set behavior. High code quality is ensured by tight coupling of different code generation phases. In contrast to earlier works, mainly based on heuristics, our approach is constraint-based. An initial set of constraints on code generation are prescribed by the given processor model. Further constraints arise during code generation based on decisions concerning code selection, register allocation, and scheduling. Whenever possible, decisions are postponed until sufficient information about a good decision has been collected. The constraints are active in the "background" and guarantee local satisfiability at any point of time during code generation. This mechanism permits to simultaneously cope with special-purpose registers and instruction level parallelism. We describe the detailed integration of code generation phases. The implementation is based on the constraint logic programming (CLP) language ECLiPSe. For a standard DSP, we show that the quality of generated code comes close to hand-written assembly code. Since the input processor model can be edited by the user, also retargetability of the code generation technique is achieved within a certain processor class. This revised version was published online in July 2006 with corrections to the Cover Date.     

An electromigration and thermal model of power wires for a priori high-level reliability prediction

In this paper, a simple power-distribution electrothermal model including the interconnect self-heating is used together with a statistical model of average and rms currents of functional blocks and a high-level model of fanout distribution and interconnect wirelength. Following the 2001 SIA roadmap projections, we are able to predict a priori that the minimum width that satisfies the electromigration constraints does not scale like the minimum metal pitch in future technology nodes. As a consequence, the percentage of chip area covered by power lines is expected to increase at the expense of wiring resources unless proper countermeasures are taken. Some possible solutions are proposed in the paper.     

Multiprocessor SoC software design flows

Typical design flows supporting the software development for multiprocessor systems are based on a board support package and high-level programming interfaces. These software design flows fail to support critical design activities, such as design space exploration or software synthesis. One can observe, however, that design flows based on a formal model of computation can overcome these limitations. In this article, we analyze the major challenges in multiprocessor software development and present a taxonomy of software design flows based on this analysis. Afterwards, we focus on design flows based on the Kahn process network (KPN) model of computation and elaborate on corresponding design automation techniques. We argue that the productivity of software developers and the quality of designs could be considerably increased by making use of these techniques.     

Synthesis of ASIC regular arrays for real-time image processing systems

In this paper the problems involved with high-level synthesis of ASIC regular arrays for real-time signal processing systems will be outlined. It will be shown that novel nonlinear, behavior preserving, transformations and extended affine mapping techniques are of key importance in mapping nonuniform recurrence equations on regular arrays with realistic constraints on area, throughput and I/O bandwidth.     

Data streams classification with ensemble model based on decision-feedback简

The main challenges of data streams classification include infinite length, concept-drifting, arrival of novel classes and lack of labeled instances. Most existing techniques address only some of them and ignore others. So an ensemble classification model based on decision-feedback（ECM-BDF） is presented in this paper to address all these challenges. Firstly, a data stream is divided into sequential chunks and a classification model is trained from each labeled data chunk. To address the infinite length and concept-drifting problem, a fixed number of such models constitute an ensemble model E and subsequent labeled chunks are used to update E. To deal with the appearance of novel classes and limited labeled instances problem, the model incorporates a novel class detection mechanism to detect the arrival of a novel class without training E with labeled instances of that class. Meanwhile, unsupervised models are trained from unlabeled instances to provide useful constraints for E. An extended ensemble model Ex can be acquired with the constraints as feedback information, and then unlabeled instances can be classified more accurately by satisfying the maximum consensus of Ex. Experimental results demonstrate that the proposed ECM-BDF outperforms traditional techniques in classifying data streams with limited labeled data.     

Integrated model parameter extraction using large-scaleoptimization concepts

A robust approach to modelling parameter extraction in microwave circuit design is presented. The approach not only attempts to match DC and AC measurements under different bias conditions simultaneously, but also employs the DC characteristics of the device as constraints on Bias-dependent parameters, this improving the uniqueness and reliability of the solution. The approach is an expansion of the hierarchical modeling techniques recently proposed J.W. Bandler and S.H. Chen (1988). Based on J.W. Bandler and Q.J. Zhang's (1987) automatic decomposition concepts for large-scale optimization, a sequential model building method is proposed which can be combined with powerful l₁ optimization techniques to establish a model with simple topology and sufficient accuracy. Practical FET models are used to illustrate the formulation. A detailed numerical example is presented to show the effectiveness of the approach     

Self-configuring communication middleware model for clusters with multiple interconnections

Communication middleware such as MuniCluster provides high-level communication mechanisms for networked applications by hiding the low-level communication details from the applications. The MuniCluster model provides mechanisms to enhance the network performance properties through message separation and parallel transfer. However, the configurations of such services require various measurements and setups to efficiently utilize the availability of multiple network interfaces. In this paper we introduce and evaluate a self-configuring model that allows applications to transparently utilize the existence of multiple network interfaces and networks. Here we present enhancements to the MuniCluster model by adding the self-configuration mechanism. Using network resource discovery and deciding on how to efficiently utilize the multiple networks, the model enhances overall communications performance. The proposed techniques deal with the heterogeneity of interfaces and networks to enhance the communication performance transparent form the applications. The proposed techniques also deal with heterogeneity in the interfaces and networks in their numbers, latencies, and bandwidths.     

Optimum and heuristic transformation techniques for simultaneousoptimization of latency and throughput

Although throughput alone can be arbitrarily improved for several classes of systems using previously published techniques, none of those approaches are effective when latency constraints, which are increasingly important in embedded DSP systems, are considered. After formally establishing the relationship between latency and throughput in general computation, we explore the effect of pipelining on latency, and establish necessary and sufficient conditions under which pipelining does not alter latency. Many systems are either linear, or have subsystems that are linear. For such cases we have used a state-space based approach that treats various transformations in an integrated fashion, and answers analytically whether it is possible to simultaneously meet any given combination of constraints on latency and throughput, The analytic approach is constructive in nature, and produces a complete implementation when feasibility conditions are fulfilled. We also present a suboptimal but hardware efficient heuristic approach for the special case of initially-relaxed single-input single-output linear time-invariant computations. A novel software platform consisting of a high-level synthesis system coupled to a symbolic algebra system was used to implement the proposed algorithm transformations. Instead of optimizing to improve throughput and latency, our transformations can also be used to increase the implementation efficiency while achieving the same latency and throughput as the original design     

Stability-based algorithms for high-level synthesis of digitalASICs

This paper presents new algorithms for the scheduling and allocation phases in high-level synthesis under time and resource constraints. This is achieved by formulating these problems in terms of Liapunov's stability theorem using a transformation technique between the design space and the dynamic system space. These algorithms are based on moves in the design space, which correspond to the moves toward the equilibrium point in the dynamic system space. The scheduling algorithm (MFS) takes care of mutually exclusive operations, loop folding, multicycle operations, chained operations, and pipelining (structural and functional). The mixed scheduling-allocation algorithm (MFSA) can handle all of the above scheduling applications as well as simultaneously performing allocation of functional units, registers, and interconnects while minimizing the overall cost