Monthly R&D Status Report Date: April 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 We have moved forward on some fundamental design representation and scheduling issues. In addition, a few technical improvements were made on the Ptolemy 0.5 release and distributed in the form of patches. 2. Significant Accomplishments 2.1 Technical Improvements to Ptolemy Working with some researchers at IMEC in Belgium, we have gotten dynamic linking working on HPPA architectures with both Cfront and g++ compilers. We have created and tested versions of Ptolemy compiled with extensive optimization for all three platforms (DEC, Sun, HP). The performance improvement is significant. We have begun using Quantify, from Pure Inc., to systematically quantify and track performance bottlenecks. We have gotten a port of Ptolemy working on our SGI Indigo-2, but unfortunately, not under the latest version of the O/S. We will continue to work on this. Alan Kamas has created a small version of Ptolemy (code named Ptiny Ptolemy) that dramatically reduces the investment in time and disk space for users to try the system. It includes only the SDF and DE domains (no code generation). We have removed demos that require large extraneous software packages (such as the image and video processing demos). The source code has also been removed. The resulting executables and demos require 11.77 Megabytes, and using gzip compress to 3.26 Meg (3 floppies). We are putting together a reduced manual for this version, and will announce its availability after more extensive testing. Working towards automated regression tests, Wan-Teh Chang has improved the existing run-all-demos command so that it works with all demos. We are now routinely using PureLink, the incremental linker from Pure Inc. This dramatically speeds turnaround time in the software debugging cycle. A number of other technical improvements and minor bug fixes have been installed. 2.2 Fundamental Progress The most dramatic result in this period is the introduction of higher-order functions into Ptolemy. A higher-order function is a function that can take a function as an argument and can return a function. The intent of these is to allow for compact, scalable, and highly parallel graphical representations of algorithms at arbitrary granularity. A simple example is a Ptolemy system constructed using the new star SDFMap: Map --/--> TkBarGraph The slash represents a bus of arbitrary width. The TkBarGraph can accept any number of inputs, and generates a bar chart for each input. In the above example, for instance, the parameters of the Map star (a higher-order function) might be set to: blockname: IIDUniform where_defined: input_map: output_map: output parameter_map: upper "1.0-map_inst_no*0.05" The Map block creates N instances of the IIDUniform star, where N is the width of the bus connected to its output. It sets the parameters according the parameter_map, connects according to the input_map and output_map, and then self-destructs. In the parameter map, "map_inst_no" gets replaced with the instance number. Thus, in a simple two-block graphical representation, a highly parallel system can be compactly described. Although IIDUniform is a built-in primitive block ("star"), you can also use a composite block ("galaxy") defined somewhere else. If you use a galaxy name for blockname, you can specify where the oct facet is that defines it using the where_defined parameter. Another higher-order block, called SDFChain, replaces itself with a chain of any number of instances of another block (star or galaxy), with optional pipelining. For instance, we created one demo that implements a cascade of biquad filters. A third higher-order block, tentatively called SDFMap2, replaces itself with either one of two other blocks (stars or galaxies). This can be used to implement recursion in SDF. The recursion is evaluated at setup time, so no runtime overhead is incurred. A great deal of parallelism can be compactly described. One demo computes an FFT of any power-of-two order using only a simple butterfly or a small FFT (under parameter control). This demo, thus, achieves arbitrary granularity in its potential parallelism, specified by a single parameter. 2.2 Interactions with and Contributions from the Outside The ptolemy-hackers mailing list has grown to include 149 non-Berkeley addresses. Joe Buck (of Synopsys) has submitted a CFV (call for votes) for a Usenet/Internet newsgroup for Ptolemy. Alberto Vignani of the FIAT Research Center in Italy has ported Ptolemy 0.5 to Linux running on a 486 PC. We have included his patches in our ftp site. Dialog continues with Precedence and Berkeley Design Technology on integration of Ptolemy with Precedence's simulation backplane. Precedence and BDT are preparing a proposal for their part of the work to Martin Marrietta for inclusion in their RASSP project. Our support of this effort will fall under our RASSP project. Richard Tobias of White Eagle Systems Technology, Inc., is getting close to finishing the port of Ptolemy to Solaris 2.x. The port is mostly working, but without Tcl/Tk stars and without dynamic linking. We will help them solve these remaining problems, and then release appropriate patches. We have updated somewhat our experimental hypertext document accessible worldwide via Mosaic. To access all of these on line, you need a Mosaic configured with sound capabilities, MPEG video display (for the animated demo mockup), and postscript display (such as ghostview). Any Mosaic setup can access the overview, look at a couple of block diagrams, and download code or postscript files. To access this, the URL (universal resource locator) for the home page is: file://ptolemy.eecs.berkeley.edu/pub/ptolemy/www/Ptolemy.html Our home page is also available through a worldwide DSP document that is under development, accessible with URL: http://tjev.tel.etf.hr/josip/DSP/sigproc.html 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 in July or August that will incorporate all existing patches. 5. Next Period Activities We are looking at a "cyclo-static" dataflow model, developed at the Katholic University at Leuven. This model is based on SDF, but an actor can produce or consume a varying number of tokens; the variation follows a pattern specified at compile time. For instance, our downsample star could be written to consume one sample every time it fires, and produce one sample in some n-th firing, followed by zero samples in the next N firings. The motivation for this is to reduce the memory allocated to buffering data. It does not add any fundamentally new capability. Sriram and Shuvra Bhattacharrya have started investigating how this technique could be combined with loop scheduling. Although they have preliminary ideas, the solution is not yet obvious. 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 None this time. 8. Other Comments We welcome feedback on the content and format of this report, as we would like these reports as useful as possible.