Monthly R&D Status Report Date: December 15, 1996 Title: "SYSTEM-LEVEL DESIGN METHODOLOGY FOR EMBEDDED SIGNAL PROCESSORS" Contract Number: F33615-93-C-1317 Principal Investigator: Edward A. Lee Organization: University of California at Berkeley 1. Tasks Performed This period was dominated by preparations for the release of Tycho, which will occur within a few days. Other major accomplishments include completion of a PhD thesis on scheduling techniques for synchronous and multidimensional synchronous dataflow. 2. Significant Accomplishments 2.1 Scheduling Praveen Murthy has completed and filed a PhD thesis on scheduling techniques for synchronous and multidimensional synchronous dataflow. Below is the abstract. "In this thesis, we present various scheduling techniques for programs expressed as Synchronous Dataflow (SDF) and Multidimensional Synchronous dataflow graphs. Synchronous dataflow has proven efficient as a specification model for block-diagram based programming environments for signal processing. Two key reasons for its popularity are that a) static schedules can be constructed at compile time, thus eliminating the overhead due to dynamic scheduling, and b) it models multirate signal processing application very naturally and intuitively. The first property is particularly important in environments where code-synthesis for embedded processors is desirable, since embedded signal processing applications have rigid throughput requirements in order to meet hard- real-time constraints. Multidimensional Synchronous Dataflow (MDSDF) is an extension of SDF to multiple dimensions; in this model, applications such as image and video signal processing, which operate on multidimensional signal spaces, are more naturally modeled and specified than in SDF. The amount of on-chip memory available on embedded processors is often severely limited. Adding off-chip memory is usually not an option because it entails a speed penalty, it increases overall system cost and size, and increases power requirements. Thus, when generating software implementations from SDF specifications for a uniprocessor, the scheduling problem of minimizing code size and buffer memory size becomes crucial. If the scheduling is not done carefully, the blowup in the size of the implementation can preclude implementation on the processor. Previous techniques have focused on scheduling to minimize code size. However, this neglected the buffer memory usage of the schedule; in this thesis, we develop techniques that jointly minimize for code size and buffer-memory size of the software implementation. We give three polynomial-time algorithms: a dynamic programming algorithm that is used as a post-optimization step, and two heuristics that use different approaches to constructing these schedules. The general problem is shown to be NP-complete, thus justifying the use of heuristics. An extensive experimental study is given to show the efficacy of all these techniques. We extend these scheduling results to MDSDF specifications. We then tackle a problem of a different type. A multidimensional signal can be sampled in many different ways. A straightforward extension of one-dimensional sampling results in the so-called rectangular sampling structure, where the samples lie on a rectangular grid. However, a more general sampling structure is a geometrical lattice; sampling lattices that are not rectangular can have many advantages in certain applications. For example, a signal sampled on a non-rectangular lattice can have a lower sampling density than one sampled on an equivalent rectangular lattice. For real-time processing of multidimensional signals, a lower sampling density means fewer samples to process in a given time interval. The standard MDSDF model suffers from the inability to model multidimensional systems sampled on arbitrary sampling lattices; hence, we give an extension of MDSDF that is capable of modeling such systems. The model we give preserves the property of static, compile-time schedulability. However, constructing such schedules requires the solution to some challenging problems. In particular, we show that an augmented set of balance equations have to be solved simultaneously in the extended model. The additional equations are quite different from the usual balance equations in SDF and MDSDF; they involve computing so-called "integer volumes" of parallelepipeds. This computation turns out to be an interesting number-theoretic problem, and we present several approaches for solving it. Finally, we present a practical example of a video sampling structure conversion system to show the usefulness of the generalized MDSDF model." 2.2 Specification and Modeling of Reactive Real-Time Systems Class The class on specification and modeling of reactive real-time systems has concluded, and project presentations were made on the following topics: * Synchronous/Reactive Domain in Ptolemy * A study of Trace Theory and its application to modeling concurrent systems * Kahn Process Networks in Java * Concurrent models based on Java Threads * Comparing Reactive Languages * Petri Nets related to Dataflow * FMSs and Dataflow combined * Simulation of Hybrid Systems in Java 2.3 Improvements to Tycho There were a very large number of improvements to Tycho in this time period in preparation for a release. These include: * many bug fixes, * interactive documentation of the graphics infrastructure, * improvements to dynamic loading, * construction of a standalone Tcl profiler (independent of TclX), * printing of text and graphics files, * exporting of graphics files to EPS, GIF, and XWD formats, * enhanced dialog construction tools, * speed improvements in graph layout code, and * enhanced library for portable operating system interaction. The Macintosh and NT ports of Tycho are progressing, although the Macintosh port continues to show problems. We will not hold up the release for it. 2.4 Other uses of Ptolemy The CAD group at Berkeley has announced the public availability of the POLIS-v0.2 co-design environment for control-dominated embedded systems, which is based on Ptolemy. POLIS offers an integrated interactive environment for specification, co-simulation, formal verification, and synthesis of embedded systems implemented as a mix of hardware and software components. Version 0.2 offer many add features, including brand new microcontroller resource library handling and Ptolemy simulation debugging. Most of the information about POLIS, including pointers to source and object code (for various CPUs and OSes) is available at our WEB site: http://www-cad.eecs.berkeley.edu/Respep/Research/hsc/abstract.html 3. Publications and Presentations 3.1 Publications [1] "Scheduling Techniques for Synchronous And Multidimensional Synchronous Dataflow," Praveen Murthy, PhD thesis, November 1996. 3.2 Presentations * "Synchronous programming languages for reactive systems," Alain Girault, Visiting Scholar, Dept. of Electrical Engineering and Computer Science, UC Berkeley, November 21, 1996. See: http://ptolemy.eecs.berkeley.edu/design-seminar/nov21.html * "Moderated Panel," Edward Lee, Richard Newton, and Jan Rabaey, Design, Modeling, and Specification of Systems Seminar, Thursday December 5. * "Abstractions for System-Level Design," Prof. Edward A. Lee, UC Berkeley, Invited talk at UC Davis Dept. of ECE, December 6, 1996. * "The SR Domain Ptolemy," Stephen Edwards, Workshop on Synchronous Languages, Dagstuhl, December 9, 1996. * "Modelling Distribution with Partial Orders," Alain Girault, Workshop on Synchronous Languages, Dagstuhl, December 12, 1996. 3.3 Guest Presentations * "Methods, Models and a CAD Methodology," Daniel Gajski, Information and Computer Science, University of California at Irvine, CAD Seminar, Wednesday, December 4, 1996.