This project explores algebraic techniques for analysis of discrete-event systems (DES) with the objective of improving efficiency of simulation for DES models of embedded systems. An event in a DES is characterized by temporal instances of actions. A system behavior is characterized as a fixed-point determination of the modeled linear system in response to generation and propagation of events. We explore the relationship between events in order to devise efficient event generation and propagation techniques.

The goal of this project is to develop formalisms and techniques for analysis of performance of embedded computing systems. The overall quality of a system is measured by the cost of implementation as the size of hardware and memory components and by performance measures such as latency and throughput at specific inputs and outputs of the design. In addition, most applications of embedded systems are required to operate under detailed timing and execution rate constraints on an operation or sets of operations. We are experimenting with algorithms to carry out performance analysis and transformations needed to ensure constraint satisfiability for a given implementation.

We have developed a tabular model to describe system functionality that is concise and canonical. We are investigating various optimization techniques based on this model. The most promising approach is the optimization of control based on behavioral and structural ``don't care'' conditions. We are also exploring use of this model for system partitioning, interface resolution, and encoding tasks.

Embedded computing refers to use of computing in dedicated applications that may even be noncomputing. The goal of this project is to explore design techniques and to develop CAD tools to build these systems using microelectronic modules on the same chip or substrate. For such systems, portability and implementation cost issues impose constraints on components used and total power consumption. Rapid exploration of design alternatives by means of CAD tools is pivotal to efficient implementation of embedded systems. This research leverages recent advances in software compilation and hardware synthesis to develop a unified co-synthesis framework in which to evaluate design trade-offs.

We consider partitioning of embedded system tasks into hardware and software implementations. System designs are characterized by flexible partitions that may be shifted to meet changing performance criteria. One of our goals is to delay this determination to as late in the design process as possible. We are investigating a novel compiler-directed approach to system-level partitioning that takes into account constraints on size, power, cost and performance of the system being designed and, at the same time, minimizes the cost of implementation of a suitable hardware-software interface. The resulting portions can be implemented using a loosely coupled multirate execution model with minimal synchronization between the portions.

Presynthesis performs source level optimization on input HDL descriptions to produce efficient HDL descriptions. The output HDL is optimized for subsequent synthesis tasks. We have built a presynthesis tool, named PUMPKIN, which incorporates user-specified ``don't care'' conditions to remove redundancies in the input hardware descriptions. This tool can also be used for intermodule optimization and to facilitate design reuse by providing a common HDL description of a block that can be tailored to specific applications without altering the original source code. Use of presynthesis optimizations also makes the final synthesis results relatively insensitive to the individual HDL coding styles.

Generation of embedded software requires operation linearization under constraints to ensure timely interation with other system components, particularly concurrent hardware. In addition, because there is limited on-chip register storage, operation linearization must take into account the delay resulting from additional data movement operations needed to ensure constraints can be met. We are exploring conditions to guarantee the satisfiability of imposed performance constraints for a given software and runtime system. Our current approach to software synthesis uses a multithreaded software system architecture with a nonpreemptive runtime system. We are exploring extensions and opimization of this model for use in large software systems.

The goal of this project is to develop a model and a language for specification of the system interface that is independent of any specific implementation format. Depending upon system interface implementation, there may be more than one data format for a given data type. Further, depending upon implementation technology, a data format may be dynamically or statically decided. We are investigating methods to generate interface descriptions by generating symbolic implicant tables for the interface signals and relations. We are exploring use of appropriate encoding techniques to synthesize the interconnect structure under constraints on performance and size of implementation.

The project addresses the problem of generating a provably correct software implementation of a system functionality modeled using a hardware description language (HDL). We are working on defining formal conditions and developing tools that would take parts of such HDL descriptions and correctly produce a sequential program that implements the same behavior. The emphasis on parts and (temporal/functional) correctness is important, since one can easily show examples where no sequential code generated from a given HDL model would produce the desired behavior. We are exploring the conditions under which this translation can be achieved and the transformations that can be used to make a HDL model serializable.

Various aspects of computer-aided design of VLSI circuits are investigated including physical design, synthesis of finite state machines, and data and control path synthesis.

Automated design of logic networks for VLSI chips has suddenly become popular in the computer industry because it takes less time and fewer mistakes are made. The Transduction method, our oldest logic synthesizer, has become the de facto industry standard, being recently adopted by IBM and major CAD vendors. We had developed a synthesizer, SYLON, for synthesizing MOS logic networks with minimum area, by extending our previous logic synthesizers, the Transduction method and Algorithm DIMN. Recent comparison of SYLON with other synthesizers shows that SYLON produces logic networks with the smallest areas. Now we are developing a new synthesizer for producing MOS logic networks with minimum delay by developing new algorithms.