Monthly R&D Status Report Date: May 15, 1994 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 Technical improvements to Ptolemy continue at a healthy rate. Our output of fundamental results is also healthy. This month involved an unusually large number of meetings with RASSP and government people. 2. Significant Accomplishments 2.1 Technical Improvements to Ptolemy The port to SGI under both Irix4 and Irix5 has been completed and distributed as a patch on the 0.5 release. A patch to support dynamic linking on HP platforms under both gcc and cfront has also been distributed. Xavier Warzee of SGS Thomson (France) reports completing a port to the IBM RS6000/ AIX 3.2.5. The implementation of dynamic linking on the SGI machines uses dlopen(), a System V Release 4 feature present in SunOS4.1.x, Solaris2.x and Irix5.x. It loads a shared object into a running image. The shared object must be compiled with Position Independent Code (PIC). This mechanism promises to be much more portable than our previous, hand-written dynamic linking mechanism. We are exploring using it to dynamically link entire domains. Ptiny Ptolemy (a small demonstration version of Ptolemy) has been completed, including a reduced version of the manual. It is also now available by anonymous ftp. This release fully supports all of our instructional uses of Ptolemy. The filter design programs optfir and wfir have been converted to C from Fortran in order to make them more portable and more consistent with the rest of our environment. Two visitors from the Naval Research Labs, Dick Stevens and Roger Hillson, spent two weeks with our group. The objective of their visit was to become familiar with Ptolemy internals. To make this possible, we agreed on an objective for them to design a "lean-and-mean" dynamic dataflow domain. The reason for doing this is that our current dynamic dataflow domain has a rather large number of experimental techniques built into it, many of which have subsequently been supplanted by better methods. Dick and Roger designed and built this domain in 1 week and two days, undoubtedly setting a record for the fastest construction of a useful domain. They plan to take this experience back to NRL to construct another dynamic dataflow domain that uses the "processing graph method (PGM)" as its model of computation. We plan to use their domain to replace the existing DDF domain. Brian Evans has created a link between Matlab and Ptolemy so that stars can have their functionality expressed as Matlab functions. This is not ready for release yet, but looks it looks like it will be a very successful way to rapidly prototype new algorithms. The pxgraph program has been linked to FrameMaker so that high quality data plots can be more easily generated for inclusion in papers. 2.2 Fundamental Progress Mike Chen has completed an experimental "multidimensional dataflow" domain, where arcs that connect blocks represent not simple sequences of tokens, but rather two-dimensional orderings of tokens. This domain is well matched to multidimensional signal processing and is capable of representing a broader range of algorithms with static flow of control than the synchronous dataflow model. The real potential, however, is in parallel computation, because the model of computation exposes much more parallelism at a much finer granularity than the SDF model. The domain has a rich enough set of stars to be usable for experimentation. We hope to begin soon experimenting with parallel scheduling by interfacing to our existing parallel schedulers. In what could be a significant breakthrough in our formal understanding of block-diagram languages, we have established a formal connection between so-called "Kahn process networks" and our style of dataflow graphs. A consequence of this is that we can rigorously prove necessary conditions for determinacy for arbitrary dataflow graphs. It turns out, much to our surprise, that the dataflow mechanism we use in our dynamic dataflow domain guarantees determinacy if the actors are functional. This happened by applying common sense to the design, rather than theory, but we now have the theory. We have made some progress understanding the implications of the cyclo-static dataflow model proposed by Rudy Lauwereins of the Catholic University in Leuven, Belgium. This model was described in the last report. Two key insights (from Tom Parks) are given below: 1. A star that has a long execution time (such as a large FFT) may want to have many phases that consume and produce no data but do perform computation. The early stages could consume data, and the late stages could produce data with those in the middle being pure computation. This would make it possible to suspend the execution of the star to switch to another, such as in a real-time system. Currently, with non-preemptive scheduling, then you are stuck if there is one star that has an execution time that is too long. 2. Cyclo-static dataflow stars can be used by current schedulers in a simple way. For each port, add up the number of tokens consumed/produced in each phase. Use this sum as the SDF parameters for that port, and fire the star by executing all the phases in sequence. Because all the phases are being executed at one time instead of spreading them out and interleaving them with the phases of other stars, you don't get any of the benefits of reduced buffer size, but at least you could use cyclo-static dataflow stars with all of our current schedulers. Someone could later write a new scheduler that would take advantage of the poly-phase nature of these cyclo-static stars. 2.3 Interactions We now have a newsgroup: comp.soft-sys.ptolemy. We will keep the ptolemy-hackers mailing list active, hopefully synchronizing the two to exchange messages. Mike Williamson (who is in charge of the VHDL code generation) attended the first semiannual interrim review for the RASSP Technology Base contract entitled "CAD Tools for the Development and Reuse of Models of Signal Processing Software and Hardware," which was held at Virginia Polytechnic Institute and State University in Blacksburg, VA. We have installed and learned to use a suite of Mentor tools, including the DSP station. We have installed (but not yet exercised extensively) a suite of Synopsys tools. We have installed ADEPT (from the UVA RASSP project), and are starting to learn to use it. This is with the help of Roger Hillson from NRL. We continue to update our WWW page. To access this, the URL (universal resource locator) for the home page is: file://ptolemy.eecs.berkeley.edu/pub/ptolemy/www/Ptolemy.html Gary Shaw, of Lincoln Labs, has provided us with a preliminary copy of the spec for the SAR RASSP benchmark. This will be used to guide an effort this summer to develop a radar library for Ptolemy. 3. Problems Encountered No serious problems arose this month. 4. Schedule Reconciliation We are on schedule. We are planning a release numbered 0.5.1 for August 15 that will incorporate all existing patches. 5. Next Period Activities We are continuing work on higher-order functions, finite-state machine models, VHDL code generation, image processing, multidimensional dataflow, scheduling, and formal methods. The semester at Berkeley is ending, so research productivity should rise. 6. Budget Summary We are on-budget, as near as I can tell. Details will be provided by the University accounting office. 7. Conferences, Meetings, and Trips Dick Stevens and Roger Hillson of NRL visited our group from April 25 through May 6 (see above). On May 3, Mark Richards met with Prof. Lee for a brief discussion at Berkeley. One outcome of this is that Mark is providing some design information on a radar library to the Ptolemy project. On May 4, Jim Armstrong of Virginia Tech (and a RASSP PI) visited our group, got a Ptolemy demo, and engaged in discussion about the design of our VHDL domains. On May 6, John Teets of CFI came with a group of selected members of the CFI SimBackPlane group. They got a Ptolemy demo and engaged in discussion about system-level heterogeneous design. Attending were: John Teets, CFI Mark Glasser, Vantage Ali Haveliwala, Viewlogic Bill Hobson, Cadence Eamonn O'Brien-Strain, Alta Group of Cadence On May 6, Prof. Lee gave a talk in our weekly DSP seminar entitled "Dataflow Process Networks and Their Application to Signal Processing" 8. Other Comments We welcome feedback on the content and format of this report, as we would like these reports as useful as possible.