We are interested in optimizing the design of multifunction embedded systems such as multistandard audio/video codecs and multisystem phones. Such systems run a prespecified set of applications, and any "one" of the applications is selected at a run time, depending on system parameters. Our goal is to develop a methodology for the efficient design of such systems. A key observation underlying our method is that it may not be efficient to design for each application separately. This is attributed to two factors. First, considering each application in isolation can lead to application-specific decisions that do not necessarily lead to the best overall system solution. Second, these applications typically tend to have several commonalities among them, and considering applications independently may lead to inconsistent mappings of common tasks in different applications. Our approach is to optimize jointly across the set of applications while ensuring that each application itself meets its timing constraints. Based on these guiding principles, we formulate, as a codesign problem, the design and synthesis of an efficient hardware-software implementation for a multifunction embedded system. The first step in our methodology is to identify nodes that represent similar functionality across different applications. Such "common" nodes are characterized by several metrics such as their repetitions, urgency, concurrency, and performance/area tradeoff. These metrics are quantified and used by a hardware/software partitioning tool to influence hardware/software mapping decisions. The idea behind this is to bias common tasks toward the same resource as far as possible while also considering preferences and timing constraints local to each application. Further, relative criticality of applications is also considered, and the mapping decisions in more critical applications are allowed to influence those in less critical applications. We demonstrate how this is achieved by modifying an existing partitioning algorithm (GCLP) used to partition single-function systems. Our modified algorithm considers global preferences across the application set as well as the preference of each individual application to generate an efficient overall solution while ensuring that timing constraints of each application are met. The overall result of the system-level partitioning process is 1) a hardware or software mapping and 2) a schedule for execution for each node within the application set. On an example set consisting of three video applications, we show that the solution obtained by the use of our method is 38% smaller than that obtained when each application is considered independently.

We are interested in optimizing the design of multi-function embedded systems that run a pre-specified set of applications, such as multi-standard audio/video codecs and multi-system phones. Such systems usually have stringent performance constraints and tend to have mixed hardware-software implementations. The current stare of the art in the hardware/software codesign of such systems is to design for each application separately. This often leads to application-specific sub-optimal decisions and inconsistent mappings of common nodes in different applications. We use these as the guiding principles to formulate, as a codesign problem, the design and synthesis of an efficient hardware-software implementation for a multi-function embedded system. Our solution methodology is to first identify nodes that represent similar functionality across different applications. Such "common" nodes are characterized by several metrics. These metrics are quantified and used by a hardware/software partitioning tool to map common nodes to the same resource as far as possible. We demonstrate how this is achieved by modifying a traditional partitioning algorithm (GCLP) used to partition single applications. The overall result of the system-level partitioning process is (1) a hardware or software mapping and (2) a schedule for execution for each node within the application set. On an example set consisting of three video applications, we show that the solution obtained by the use of our method is 38% smaller than that obtained when each application is considered independently.

This paper addresses the problem of deriving a register-transfer level (RTL) model from a transistor-level circuit. Using existing techniques, the transistor-level circuit is converted into a relation that describes the evolution of the signals in the circuit with respect to the simulator clock. This simulation relation is then manipulated to derive the stable behavior of the circuit. Given this stable behavior and information about the clocking scheme, we determine if the circuit is combinational, asynchronous or synchronous. For combinational and synchronous circuits we derive an equivalent register-transfer level model. This development enables full-custom circuit designers to use tools that were till now available only to designers working at the gate-level. The algorithm has been successfully used to characterize several custom designs, as well as the entire AT&T standard-cell library.

This paper discusses a formal verification technique for comparing the functionality of a transistor netlist extracted from a layout with a design description in a hardware description language (HDL). Using novel techniques based on binary decision diagrams (BDD's), a state machine is first abstracted from a transistor netlist, given information relating to clock signals and clock models. The resulting state machine behavior is then compared with another that is derived from the HDL description. The basic ingredients of the technique used can be directly applied (or, in other cases, extended) to various related contexts of interest. In particular, the abstracted machine(s) can be represented as BDD relations or as synchronous sequential networks, both of which are common starting points for sequential synthesis and verification tools.>

Discusses the specification and automated synthesis of mixed synchronous/asynchronous systems in the context of a VHDL-based design environment. We propose a flexible paradigm for describing asynchronous behavior in VHDL that supports (1) the description of behavior as a signal transition graph (STG), (2) its expression in the form of an initializable edge-triggered finite state machine, and (3) the specification of a level-sensitive asynchronous finite state machine. An important feature is that free-running signals such as clocks can be included in the asynchronous specifications. The input specification, consisting of timing diagrams and/or the behavior and interface specifications for a set of interacting processes, is mapped into an appropriate combination of hazard-free asynchronous circuits and synchronous circuits.>

The authors discuss a formal verification technique using binary decision diagrams (BDDs) for comparing the functionality of a transistor netlist extracted from a layout with a design description in a hardware description language (HDL). A state machine is first abstracted from a transistor netlist, given information relating to clock signals and clock models. The resulting state machine behavior is then compared with another that is derived from the HDL description. The basic ingredients of the technique used can be directly applied (or, in other cases, extended) to various related contexts of interest.>

Many VLSI floorplanners work by recursively decomposing rectangular modules into lower-level rectangular modules until the leaf-level modules are reached[5]. Good layouts require good floorplans. The quality of a floorplan depends (among other things) on how the leaf-level modules are clustered into the various levels of the hierarchy. Some of the factors that determine the suitability of a decomposition are the geometry of the modules, the connectivity among modules, and timing constraints. Our experience with the mechanization of a VLSI design manager[1] has shown that the initial structural hierarchy that arises during synthesis from behavioral specifications is not always suitable for floorplanning. We describe hierarchical-clustering-based algorithms that lead to a small number of superior candidate hierarchies.

Techniques for the specification and automated synthesis of systems containing a mixture of synchronous and asynchronous (self-timed) subsystems are discussed. The input to the system consists of the behavior and performance specifications for a set of processes that interact by communicating over channels connecting typed ports; a graphical perspective on temporal constraints is provided via a timing diagram editor. Factors that influence the decomposition of the overall system into subprocesses and the choice of implementation styles include external interface constraints, system performance requirements, and system design complexity. Syntax-directed transformations are applied to the initial specification to generate a hierarchical structural description. Existing logic optimization and physical layout tools are then used to produce either standard cell or custom CMOS layouts. Fragments of the design of a processor interface board are used to illustrate various concepts.>

This paper discusses the use of formal reasoning techniques to aid in the automated structural design of leaf cells, in the more global context of VLSI circuit design. The technique supports an encapsulation of the technology-dependent aspects of a design by using appropriate formal models, and guarantees the consistency of the designs produced with respect to the functional specification and the technology model employed. The approach is illustrated by its use in the design of some leaf cells in CMOS. The role of the techniques when used in an interactive mode and in the verification of existing designs is also discussed.

Certain aspects of the behavior of concurrent systems are intrinsically probabilistic in nature, e.g., the behavior of imperfect communication media used in network protocols. We address the problem of expressing such behavior in an algebraic calculus for communicating systems. The introduction of probabilistic information in the calculus alleviates the problem of proving liveness, as proving liveness now amounts to proving that its probability is 1. A methodology for proving both safety and liveness is developed and used in proving the correctness of the Alternating Bit Protocol.

The paradigm of equational programming potentially possesses all the features provided by Prolog-like languages. In addition, the ability to reason about equations, which is not provided by Prolog, can be accommodated by equational languages. In this paper, we propose an extended equational programming paradigm, and describe an equational logic programming language which is an extension of the equational language defined in [Hoff82]. Semantic foundations for the extension are discussed. The extended language is a powerful logic programming language in the sense of Prolog and thus enjoys the programming features that Prolog possesses. Furthermore, it provides an ability to solve equations, which captures the essential power of equational programming.

This paper is a preliminary assessment of the viability of Prolog as a basis for the design of expert systems, where the major competition is assumed to be from Lisp and Lisp-based systems. We critically examine the basic features of Prolog from various perspectives to see to what extent they support (or hinder) expert system development. Our conclusion is that while Prolog has significant assets along several dimensions, Prolog as it exists today needs to be modified and appropriately enhanced to make it competitive to extant Lisp-based systems; we suggest the nature of some of these modifications.

A novel lazy evaluation mechanism, pattern-driven lazy reduction, is developed that serves as a unifying evaluation mechanism for both functional and logic programs. The reduction of a function call can be viewed as “semantically” unifying the function call with the left hand side of a defining equation, and applying the unifier to the right hand side. Lazy reduction is achieved by the pattern which the function call matches against. Function reductions are actually “driven” by patterns in this sense. It is shown that this evaluation mechanism works well for both functional programs and logic programs that involve “executable” functions. As a result, logic programs can be enhanced with (1) the availability of a functional computing environment where there is no notion of backtracking, thus alleviating the degree of control difficulties typically encountered in logic programs, and (2) the ability to terminate “infinite computations” without the introduction of complex control issues at the user-level. On the other hand, functional programs can be equipped with the power of logic programming languages, e.g., Prolog.