Monthly R&D Status Report Date: November 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 external interactions, including two major talks (a plenary talk at Asilomar and an embedded tutorial at ICCAD) and a large number of important visitors (see the summary of presentations below). In addition, we are progressing rapidly towards a major Tycho release, and continue to make improvements on control and signal processing (both SR and FSM approaches). 2. Significant Accomplishments 2.1 Synchronous/Reactive Modeling and Specification Stephen Edwards has made significant progress in generating schedules for the new synchronous/reactive (SR) domain. He has created a branch-and-bound algorithm that can find single-appearance schedules that compute the behavior of an SR system in minimum time. There are two variants. One takes an exact exhaustive approach; the other uses a heuristic to look for good candidates and ignores the rest. Experimental results suggest that the exact algorithm is often practical, often finding the minimum-cost schedule in a few seconds. For systems where the exact scheduler is impractical, the heuristic scheme can run as much as one hundred times faster and produces schedules usually no more than 25% worse than the exact algorithm. Empirical results on randomly-generated graphs suggest the overall schedule execution time grows on average as n^1.25, significantly better than the theoretical quadratic bound. 2.2 Finite State Machines Bilung Lee has installed three demonstration systems that hierarchically combine finite state machines (FSMs) with both discrete-event and dataflow Ptolemy applications. The demonstrations are classic examples of in the reactive systems community: the reflex game and the digital watch. 2.3 Windows NT Christopher Hylands was able to bring up Tycho under NT. There is still much work to be done, but this validates our strategy of ensuring that new software from the group is genuinely portable. 2.4 Improvements to Ptolemy Tom Lane (Structured Software Systems) has redesigned the type resolution system in Ptolemy, fixing a number of anomalies. The key changes are that types propagate forwards through arcs rather than backwards, that groups of multiple portholes are no longer constrained to have the same data type, and that higher-order functions in the HOF domain are evaluated in a new pre-initialization phase of execution. This solves a number of problems: * When a fork delivers particles to inputs of different types, the type conversion will occur at the receiving end not the sending end, because the plasma or buffer will be of the sender's type. This prevents doing coercion that may be appropriate for only some of the recipients. * Input ANYTYPE multiportholes can accept particles of different types from different sources. This is an essential capability for polymorphic stars like Printer. * In a star like Merge, the constraint that output type = input type will still constrain the input multiporthole members individually. Thus, the DE Merge will still require that all input types be the same, as it should. * Rewiring the schematic before porthole type assignment fixes all the type-assignment problems with HOF stars. In particular, HOFNop will not improperly constrain types, and we can get rid of the type-specific variants of HOFSrc. Bilung Lee has installed some kernel changes needed by the FSM domain and other applications. These changes enable resetting communication arcs to their initial conditions in the middle of a simulation. Brian Evans (of UT Austin) ran Purify on Ptolemy and patched a few memory access violations. 2.5 Improvements to Tycho John Reekie has added a preferences manager to Tycho, and used it to greatly improve default colors and fonts. Preferences are organized as a tree of preference sets, so each set inherits from more primitive sets. Widgets subscribe to preference sets, and are automatically updated when the preferences change. This is a major improvement to Tycho. Christopher Hylands created an "Exec" class, an interactive Unix shell window that operates within Tycho. He also created a context-sensitive Java editor class. Luis Gutierrez has integrated a video capture facility with the Tk photo widget. This will be evolved into a Tycho-based video capability. John Reekie revamped the menu architecture in Tycho to make it hierarchical and to add a popup menu with content specified by the widget under the mouse. We added mechanisms to the Graphics class to export postscript, GIF, and xwd files with images of the contents of the Graphics widget. We also added an "exportImagemap" command to the directed acyclic graph (DAG) editor to create the imagemaps needed by "clickable images" on the worldwide web. For an example of an application of this, see: http://ptolemy.eecs.berkeley.edu/~eal/curriculum/CLASSES/prereqUndergrad.html We have built in to Tycho a robust workaround for a defect in the Itcl language where destruction of an object during an update invoked from within a method could have disastrous effect. Specifically, we created a protected method safeEval that prevents destruction of the current object while evaluating its arguments and used this method for all invocations of modal dialogs. We also reworked the mechanism used to create modal dialogs, simplifying it and making it more intuitive. We created new base classes: TWidget, Object. With TopLevel, we now have a complete set of base classes underlying all Tycho classes. We added a ColorBrowser widget for use with the preferences manager. We redesigned the EntryQuery object, making it more generic and flexible, and renaming it Query. It is used for constructing complex dialog boxes with entry boxes, radio buttons, text windows, and mediated entries. Christopher Hylands made a number of improvements to "tydoc", the automatic documentation-generation system for Tycho classes. Christopher Hylands modified the TclX profiler to create a standalone file that can be compiled, which means that we don't need to ship all of TclX to get the Tycho Tcl Profiler to work. 2.6 Infrastructure Improvements Christopher Hylands upgraded our Sun network to Solaris2.5.1. He also dealt with a number of security problems, including a break-in to our main departmental server (the host of our software warehouse, which was found to be running a password snooping program). Christopher Hylands created a script that uses Netscape to print collections of HTML on-line documentation. This script will form the centerpiece of our hardcopy strategy for documentation. He also installed weblint and htmlchek, to utilities for checking HTML files for valid cross references and syntax errors. These are invoked by the makefiles. 2.7 Staff Changes With funding from Lockheed/Martin, we have a new postdoc in the group, Rajagopal Nagarajan, from Imperial College. Raja is an expert on semantics and will be helping with the FSM/dataflow and SR fundamentals. 3. Publications and Presentations 3.1 Publications [1] "System-Level Design Methodology for Embedded Signal Processors," by The Ptolemy Team, RASSP DIGEST, http://rassp.scra.org [2] "Comparing Models of Computation," Edward A. Lee and Alberto Sangiovanni-Vincentelli, Proc. of ICCAD, San Jose, November, 1996. 3.2 Publications Accepted [3] Takashi Miyazaki and Edward A. Lee, "Code Generation by Using Integer-Controlled Dataflow Graphs", accepted by ICASSP'97. [4] S. Sriram and E. A. Lee, "Determining the Order of Processor Transactions in Statically Scheduled Multiprocessors," accepted by the J. on VLSI Signal Processing. 3.3 Papers Submitted [5] S. S. Bhattacharyya, S. Sriram, and E. A. Lee, "Resynchronization of Static Multiprocessor Schedules -- Part 1: Fundamental Concepts and Unbounded-latency Analysis," submitted to the IEEE Transactions on Parallel and Distributed Systems, November, 1996. [6] S. S. Bhattacharyya, S. Sriram, and E. A. Lee, "Resynchronization of Static Multiprocessor Schedules -- Part 2: Latency-constrained Resynchronization," submitted to the IEEE Transactions on Parallel and Distributed Systems, November, 1996. 3.4 Presentations * "The Conceptual-Level Approach to Complex System Design," David Lidsky, UC Berkeley, presentation in our Design, Modeling, and Specification of Systems Seminar, October 31. * "On the Methodology of Design for Electronic Systems," Edward A. Lee, Plenary Talk at the Asilomar Conference on Computers and Communication, November 4, 1996. * "Wordlength Optimization of 2D IDCT Hardwares for the HDTV Application," Seehyun Kim, Digital Signal Processing Seminar, November 8. * "Comparing Models of Computation," Edward A. Lee, embedded Tutorial, ICCAD, San Jose, November 11. * "A Typed Framework for Semantics of Dataflow Networks," Rajagopal Nagarajan, presentation in our Design, Modeling, and Specification of Systems Seminar, November 14. 3.5 Guest Presentations * "From System to Implementation: Past, Present, and Speculation," Joachim Kunkel, Synopsys, presentation in our Design, Modeling, and Specification of Systems Seminar, October 17. * "Unified Code Generation for Polymorphic Blocks," James A. Rowson, Alta Group of Cadence, presentation in our Design, Modeling, and Specification of Systems Seminar, October 24. * "DARPA's RASSP Program: A Technical Overview," Vijay K. Madisetti, Georgia Tech, Digital Signal Processing Seminar, October 30. * "Open Problems and Directions in Communications and DSP CAD," Rajeev Jain, UCLA, presentation in our Design, Modeling, and Specification of Systems Seminar, November 7. * "Multiprocessor scheduling of a Signal Flow Graph for Workstation Clusters," Ki-il Kum, Seoul National University, presentation in our Design, Modeling, and Specification of Systems Seminar, November 7. * "Using Ptolemy for Simulation of Free Space Optoelectronic Information Processing Systems," Prof. Steven P. Levitan Dept. of Electrical Engineering University of Pittsburgh, presentation in our Design, Modeling, and Specification of Systems Seminar, November 14.