We introduce a framework for synthesis of behavioral models in which design information is represented using an automaton model. This model offers the advantage of supporting different constraints (e.g., timing, resource, synchronization, etc.) with a uniform formalism. The set of all feasible execution traces (schedules) is constructed and traversed using efficient BDD-based implicit state-traversal techniques. As an application example of this formalism, we present a novel scheduling/control-generation algorithm under environmental constraints where both the design and constraints are represented using automata. We present an algorithm that generates a minimum-latency schedule and a control unit representation. This approach is able to exploit degrees of freedom among interacting components of a multimodule system during scheduling, and is well suited for system-level design, where component encapsulation and interfacing are important.

This paper presents a set of new techniques for the optimization of multiple-level combinational Boolean networks. We describe first a technique based upon the selection of appropriate multiple-output subnetworks (consisting of so-called compatible gates) whose local functions can be optimized simultaneously. We then generalize the method to optimize larger and more arbitrary subsets of gates, called unate subsets. Because simultaneous optimization of local functions can take place, our methods are more powerful and general than Boolean optimization methods using don't cares, where only single-gate optimization can be performed. In addition, our methods represent a more efficient alternative to Boolean relations-based optimization procedures because the problem can be modeled by a unate covering problem instead of the more difficult binate covering problem. The method is implemented in program ACHILLES and compares favorably to SIS.>

In this paper we present a method for modeling don't cares at high-level in a form that can be used by sequential logic synthesis. Behavior is specified by a set of concurrent, interacting processes. Each process is described formally by its set of execution traces and represented by an /spl omega/-automaton. This type of specification is formally precise and allows the inclusion of don't cares by allowing multiple execution traces for a given input. Moreover, it allows us to cast the synthesis problem into a language containment problem, and to provide a formal description of these don't cares. We have developed a prototype synthesis system based on this framework, targeting the synthesis of the control portion of a circuit. Starting from a hardware description language Hardware, a specification is expressed in terms of a set of interconnected /spl omega/-automata. We demonstrate the feasibility of the approach by showing the possibility of traversing the state space of the specification automata.>

We show very efficient methods to compute Walsh spectrum for logic functions with large numbers of inputs (30 or more) using Binary Decision Diagrams. The BUD structure is extended to have any integer values as leaf (constant) nodes. The result is an efficient representation for integer vectors and integer matrices. The proposed procedure works directly on an extended BDD for the logic function, and computes the full Walsh spectrum in the form of an extended BDD. The algorithm presented is a more efficient version of the matrix-multiplication method. Our method embeds the Walsh transform matrix implicitly into program code with recursive calls, which results in a significant speed improvement. Our algorithm has the same complexity as the fastest known Walsh algorithm, and utilizes a much more efficient data structure than traditional truth tables. Furthermore, in cases where the complete set of spectra coefficient is either infeasible or impractical, we also present a method to compute subsets of Walsh coefficients. We present experimental results showing that logic functions having more than 60 inputs which cannot be processed by other published methods can be computed within 30 seconds on Sparc 2.>

The Walsh transform has numerous applications in computer-aided design, but the usefulness of these tech-niques in practice has been limited by the size of the boolean functions that can be transformed. Currently available techniques limit the functions to less than 20 variables. In this paper, we show how to compute concise representations of the Walsh transform for functions with several hundred vari-ables. We have applied our techniques to boolean technolqy mapping and, in certain cases, we obtained a speed up of as much as 50 % for the matching phase.

Abstract- Thts paper prmenta a set of new teelmiques for the nptimtzattmr of multiple-level combtnattorud Boolean networks. Such teehntquea are breed on a temporary tmnsfonnatlon of the networ& tnto an internally unste one. We descrtbe tirat a teebnique baaed upon the seleetion of appropriate multiple-output subnetwo~s (consisting of s~c.slled comprztible gates) whose local functions can be opthntzed sttmdtaneoualy. We then generalize the method to larger subsets of tmate gates. Beeauae shntdtaneoua opttmizatton of local functions ean take place, our methods are more powerful and general than Boolean optimization methods using don t cares, where only single-gate opti. ndzatton am be performed. In addttton, our methods rvpmaent a more efficient alternative to Boolean rvlations-b=d opttndzation procedures beeauae the problem can be mndeled by a mate covertng problem tnstead of the more difficult binate eoverhtg problem. The method ts implemented in program achilks and compares favorably to ~S. 1