Monthly R&D Status Report Date: July 15, 1995 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 Much of the effort in this reporting period centered around dynamic dataflow modeling and the interaction between dataflow models (which are untimed) and discrete-event models (which are timed). We have made what appears to be a major breakthrough in the former and considerable progress in the latter. 2. Significant Accomplishments 2.1. Dynamic Dataflow Models Tom Parks, Prof. Soonhoi Ha (of Seoul National University), and Edward Lee jointly made what appears to be a considerable breakthrough on the dynamic dataflow model of computation, apparently solving a long standing open problem. This solution appears to define a robust and simple scheduler that can be used in the DDF and process network (PN) domains in Ptolemy, as well as in commercial simulators like COSSAP (from Synopsys), DDSIM (from Mentor Graphics), and SPW (from Cadence). The problem can be stated simply. A dynamic dataflow scheduler should satisfy two requirements: R1: If the dataflow graph does not contain a deadlock condition, the scheduler should not halt. R2: If the dataflow graph can be executed forever in bounded memory, then the scheduler should be able to execute it forever in bounded memory. In general, given a dataflow graph, it is undecidable whether the graph will deadlock (the halting problem). It is also undecidable whether the graph can be executed in bounded memory (Joe Buck showed in his PhD thesis how to convert this problem to the halting problem). It is easy to define a scheduling algorithm that satisfies R1 or R2, but no scheduling algorithm can always, in finite time, guarantee both R1 and R2. This problem has plagued us for years, and has also appeared in much of the dataflow architecture work. We have found two simple scheduling strategies, both simpler than what we have implemented in the DDF and PN domains, and have outlined a proof that these scheduling strategies satisfy both R1 and R2. While the result is still preliminary, over the next few weeks we will be implementing these schedulers and formalizing their proof of correctness. 2.2. Cyclo Static Dataflow Tom Parks and Jose Pino have identified some key advantages of the cyclo-static dataflow model when used for defining applications that will run in parallel. In particular, multirate applications that do not have dependencies across iterations result in far simpler precedence graphs that exhibit more parallelism when the cyclo-static representation is used. 2.3. Dataflow and Discrete-Event Interactions Prof. Soonhoi Ha of Seoul National University helped us to make a set of changes to improve the SDF/DE interaction. These changes allow us to build arbitrarily deeply nested mixed systems while maintaining a consistent and intuitive notion of global time. This is challenging because the synchronous dataflow (SDF) domain has no notion of time. The model we are following is that the dataflow domains appear to any timed domain to fire "instantaneously". That is, they produce outputs with the same time stamps as the inputs. If they are multirate systems, then they may optionally also produce additional events with time stamps in the future, under the control of a target parameter. The changes that were required included modifications to the DE schedulers to prevent them from advancing their notion of time beyond their requested stopping time. In addition, the SDF wormhole object had to explicitly handle time stamps in order to define its multirate behavior. We have built a number of demonstration systems that illustrate this interaction. 2.4 Tycho Work continues on the iTcl front-end for Ptolemy. Brian Evans has been working on the Ptolemy documentation with an eye towards integrating it seamlessly into the tycho hypertext system. The documentation for a domain will be a combination of schematics, code, and HTML text. Christopher Hylands has defined a new directory hierarchy that cleanly separates source code from code that is needed at runtime, and has built a set of makefiles for the tycho source. Joel King has implemented a signal handler in tycho that will intercept system crashes and guide the user towards a reasonable way to deal with them. 2.5. Signal Reprocessing We have been collaborating with the Boston University/MIT RASSP team on signal reprocessing in Ptolemy. Signal reprocessing is where, based on the output of a signal processing operation, you adjust the parameters in the operation and process the same data again to get a "better" result. Adaptive filtering is an example. A more complicated example concerns estimating two sinusoids of unknown spacing. One way is to use the FFT and adjust the FFT length until the sinusoids are resolved (separated). There are a number of ways to provide a general framework for reprocessing signals using the heterogeneity supported in Ptolemy. In Ptolemy, we can define an outer reprocessing system (galaxy) that decides how to change the processing parameters in the inner dataflow subsystems (galaxies). Before firing the inner dataflow galaxies, the reprocessing galaxy would reset the parameters of the inner galaxies. The reprocessing galaxy would act as a controller of the inner galaxies. In the current release of Ptolemy, we could define the outer-level controller using the (1) dynamic dataflow domain, and (2) the synchronous dataflow domain with a higher-order function mechanism that recompiles inner galaxies before invoking them. Two new computational models are being developed and investigated to serve as outer controller systems: (1) a finite-state machine domain, at U.C. Berkeley, and (2) an integrated processing and understanding of signals domain, at Boston University and U.C. Berkeley. At the 1994 RASSP Conference, Joseph Winograd and Hamid Nawab from Boston University demonstrated a standalone radar clutter analysis testbed using the Integrated Processing and Understanding of Signals (IPUS) architecture to process radar data using expert knowledge encapsulated by computer. Over the last year, with the help of Wan-Teh Chang, Brian Evans, Edward Lee, and others at U.C. Berkeley, they have integrated the IPUS architecture into the Ptolemy environment as an IPUS domain. The IPUS domain has a dynamic scheduler that reacts to events (knowledge) registered in global data structures (e.g., blackboards) by local actors (e.g., knowledge sources). The IPUS domain reasons about knowledge at different levels of abstraction arranged in a hierarchy. Various local actors (e.g. knowledge sources) have been developed that can be reused in any IPUS application. The Ptolemy and BU teams plan a demonstration of the new IPUS domain running the radar clutter analysis testbed at the 1995 RASSP Conference. 2.6. Technical Improvements to Ptolemy We have created an iTcl interface to the Tcl script blocks in Ptolemy. Because this interface is object oriented, it is much cleaner than the original interface. The Tcl script blocks are used to create customized user interfaces and displays for simulations. Brian Evans has converted the supporting Tk code for the Ptolemy Interactive Graphical Interface to Tk 4.0. Christopher Hylands has already installed Tk 4.0 for Tycho development, and plans to reconfigure the GUI to use Tk 4.0. Then, we will upgrade the Tcl/Tk stars to use Tk 4.0. Xavier Warzee of Thomson CSF has provided a set of Power PC binaries for Ptolemy version 0.5.2. These have been put on the ftp site. Christopher Hylands has installed gcc-2.7.0/libg++-2.7, identified some minor incompatibilities, and (with help from Joe Buck of Synopsys) identified one bug in the g++ compiler and a workaround in Ptolemy. We plan to release a patch for Ptolemy 0.5.2. 2.7. Infrastructure and Personnel We have added four new members to the Ptolemy team. They are Farhad Jalilvand, Matthew Tavis, Kang Ngee Chia, and Joel King. Farhad is putting together communications demos for Ptolemy and converting demos to World Wide Web format to enhance the Quick Tour. Matt is working on the user interface, including converting the Gantt and Logic Analyzer displays to Tcl/Tk and helping with the Tycho development in iTcl. Kang Ngee Chia is working on code generation in C. Joel King, who is joining the group as a graduate student, will be working on mixed-signal simulators, and will begin by integrating Spice into Ptolemy. Christopher Hylands has fixed three bugs in Kerberos that prevented it from working under Solaris 2.x, and has installed Kerberos on our network. Kerberos is a network security program from Carnegie-Mellon University that has proven very effective at preventing unauthorized accesses. 3. Schedule Reconciliation No changes. 4. Conferences, Meetings, and Trips Presentations made by members of the Berkeley team: 1) E. A. Lee, "System-Level Design of Signal Processing Systems," presented as part of a tutorial on "Domain Specific Design Tools for DSP", Design Automation Conference, June 16, 1995. 2) E. A. Lee, "The University On-Line", talk at a MiniConference on Multimedia Networking at Berkeley on June 16. 3) E. A. Lee, "Effective Heterogeneous Design and Cosimulation,", Presented at the NATO Advanced Study Institute Workshop on Hardware/Software Codesign, Lake Como, Italy,June 18 - 30. 4) B. L. Evans, "Interactive Solution Sets as Components of Fully Electronic Signals and Systems Courseware", Presented at the Knowledge-Based Signal Processing Roundtable, Boston University, Boston, MA, June 30, 1995. 5) B. L. Evans, "Programming Computer Algebra Systems to Justify Their Answers and to Diagnose Errors in Incorrect Solutions," Presented at the NSF Workshop on Revitalizing the Engineering, Mathematics, and Science Curricula Via Symbolic Algebra, Invited Talk, Terre Haute, IN, July 10, 1995. 6) A. Kalavade, "Symbolic Computation in System Simulation and Design," Presented at the SPIE International Symposium on Advanced Signal Processing Algorithms, Invited Paper, San Diego, July 12, 1995. Meetings conducted and attended by members of the Ptolemy Team: 7) Edward Lee met with representatives of Thomson CSF, INRIA, and Simulog on the use and support of Ptolemy in Europe, U.C. Berkeley, June 30, 1995. 8) Brian Evans visited the Knowledge-Based Signal Processing Group at Boston University, which has a joint RASSP project with MIT, to work on signal reprocessing, from June 26 - 30, 1995. Brian's visit was a follow-up to a visit to U.C. Berkeley by Joseph Winograd. As a result of our collaboration, BU and U.C. Berkeley will be demonstrating the a reprocessing system running under Ptolemy at the 1995 RASSP conference at the end of July. 9) Prof. Soonhoi Ha of Seoul National University visited U.C. Berkeley for 1.5 weeks to work on dynamic dataflow schedulers and the interaction between dataflow and discrete event computational models. Prof. Ha is an alumnus of the DSP Design (Ptolemy) group. 10) Brian Evans was an instructor at the 1995 "NSF Workshop on on Revitalizing the Engineering, Mathematics, and Science Curricula Via Symbolic Algebra" held at the Rose-Hulman Institute of Technology, Terre Haute, IN, July 10-17, 1995. The workshop brings 30 math, science, and engineering professors at various U.S. colleges and universities to explore the new kinds of problems and exploration that are possible with computer algebra systems. Mathematica and Maple are the tools for the courseware development. A preliminary World Wide Web page about the NSF Workshop is at http://www.rose-hulman.edu/~maym. Presentations by visitors at U.C. Berkeley: 11) Vojin Zivojnovic of the Technical University of Aachen visited on July 7 and gave two talks: a) "Demo and Description of SuperSim, the compiled instruction set simulator for DSPs" b) "Reachability of Data Flow Graphs and the Retiming Transformation". 5. Publications [1] W.-T. Chang, A. Kalavade,and E. A. Lee, "Effective Heterogeneous Design and Cosimulation,", Presented at the NATO Advanced Study Institute Workshop on Hardware/Software Codesign, Lake Como, Italy,June 18 -- 30, 1995. (http://ptolemy.eecs.berkeley.edu/papers/effective). [2] Brian L. Evans, Steve X Gu, Asawaree Kalavade, Edward A. Lee, "Symbolic Computation in System Simulation and Design", Proc. SPIE Int. Sym. on Advanced Signal Processing Algorithms, Invited Paper, San Diego, July 10-12, 1995, pp. 396-407. (http://ptolemy.eecs.berkeley.edu/pub/ptolemy/papers/spie95symbcomp.ps.Z). All Ptolemy publications are listed chronologically and can be searched by author, topic, etc., by accessing our World Wide Web page at URL http://ptolemy.eecs.berkeley.edu/ under "Publications".