Monthly R&D Status Report Date: April 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 We have released an alpha version of Ptolemy version 0.5.2, and expect to release the beta version on April 20. We have begun serious work on a software architecture that will support modular syntax, to complement our underlying theme of modular semantics. A number of more fundamental advances are reported below. 2. Significant Accomplishments 2.1. Hiearchical Scheduling Jose Pino has demonstrated hierarchical scheduling on a heterogeneous platform consisting of a Sun workstation running Solaris 2.4 and a programmable DSP on an S-bus card. His demonstrations incrementally compile real-time subsystems for the DSP and embed them within a non-real-time process running on the Unix workstation. Communication between them is asynchronous, using what Jose calls a "peek/poke" mechanism to asynchronously read and write into the DSP memory. His demonstration systems are acoustic modems (modems that transmit from an audio loudspeaker to an audio microphone through air). Animated, interactive signal displays are produced on the workstation, enabling better evaluation and understanding of the algorithms and their performance. The hierarchical scheduling mechanism permits the use of highly optimized loop scheduling techniques developed in our group by Shuvra Bhattacharyya. Without hiearchical scheduling, it was not possible to use these because they had not been designed for use in parallel systems. Because the applications are multirate, without hierarchical scheduling they required considerably more memory than was available on the DSP card. Moreover, scheduling time was substantial (because a rather large precedence graph was constructed). Thus, Jose has demonstrated that hiearchical scheduling enables modular use of scheduling optimizations, and has shown that in practical examples, considerable savings in embedded system memory are achieved. The scheduling time speedups are substantial, and the assembly code size is dramatically smaller for all examples, compared to results using non-hierarchical scheduling. 2.2 Embedded sofware synthesis Shuvra Bhattacharyya (of Hitachi America) and Praveen Murthy have developed a dynamic programming technique for post-processing a single appearance schedule with the goal of generating a modified single appearance schedule that has a significantly lower buffer memory requirement. The technique is an extension of an algorithm previously reported for constructing single appearance schedules for chain-structured SDF graphs. In [4] we report the generalization of the algorithm that handles delays and arbitrary topologies, and show that while the original algorithm always preserves the lexical ordering of the input schedule, the generalization may change the lexical ordering (for a graph that has delays). Thus, it may compute a schedule that has lower buffer memory requirement than all single appearance schedules that have the same lexical ordering as the input schedule. Experimental results are given in [4]. In addition, an adaptation of the dynamic programming algorithm is given that optimally solves the converse problem of minimizing code size by optimally organizing loops for an arbitrary (not necessarily single appearance) schedule. Thus, for example, a schedule that has been constructed for minimum buffer memory can be post-optimized to improve the code size, while preserving the buffer optimality. 2.3 Modular Syntax We have begun development of a software architecture that will support modular syntax in much the way the Ptolemy kernel supports modular semantics. While the C++ classes in the Ptolemy kernel equip a software laboratory for experimenting with models of computation, this new layer will equip a software laboratory for experimenting with visual syntaxes and sophisticated design visualization techniques. This will be long-term, experimental activity. The first prototype, dubbed Galileo, is being written in [incr tcl], an object-oriented extension to the Tcl language that we currently use in Ptolemy for scripting. This extension has much the flavor of C++, but is an interpreted language compatible with Tk, the X-Window toolkit associated with Tcl. [Incr tcl] was developed at AT&T and is freely distributed, using a license agreement similar to that of Tcl/Tk and Ptolemy. We have several long-term objectives: a. Textual syntax is used throughout Ptolemy (C++, C, Tcl/Tk, VHDL, Silage), but we have no editing or visualization tools any more sophisticated than emacs. We believe the textual languages should be given equal weight with the visual, block-diagram languages embodied in the Ptolemy domains. b. The visual syntax required for forthcoming domains (notably those using finite-state machine semantics, is significantly different from the visual syntax that we have been using for dataflow and discrete-event models. A domain should therefore modularly encapsulate its visual editor. c. The user view of library blocks needs to be customized. For instance, the parameters of a digital filter, which are considerably more complicated than the parameters of a multipler, should be edited using a more sophisticated user interface. Thus, user interaction with a library block needs to be polymorphic. We are evaluating and prototyping a software architecture that meets all of these objectives. 2.4 Generalized Multidimensional Dataflow Praveen Murthy has generalized the multidimensional dataflow model of computation to support interpolation and decimation of images on non-rectangular lattices. One practical application is conversion to and from 2:1 interlaced video signals. A paper on this topic is being prepared. 2.5 The Process Network Domain Tom Parks has converted the Process Network (PN) domain to use the gthreads package, a POSIX thread implementation from Florida State University that is distributed under the GNU General Library License. This gives us a head start on threaded computation under a standard that is expected to be supported by several workstation vendors, including Sun. He has identified a bug in the assembly code implementing context switching on Sparcstation in this package, but was able to get the PN domain working by using a C code version. 2.6 Technical Improvements to Ptolemy Jose Pino has installed his CGC Target Wormhole, which provides a generic mechanism for all code generation domains to interact with one another through synthesized C code. Although support for this is not complete in all domains, this mechanism is expected to allow the code generation domains to benefit from the same heterogeneous design style that has been used for some time in the simulation domains. Alan Kamas has added a subset of Emacs bindings to the Text widget in Tk. This gives a more uniform text editing style throughout the Ptolemy GUI. Christopher Hylands, starting with some input from Kevin Kissells, has completed a port of Ptolemy to DEC Alpha processors running Ultrix. He has also installed some changes contributed by Alexander Kurpiers of the Technical University of Darmstadt, Germany, to support the IBM RS6000 running AIX with gcc and AIX with IBM xlC c++ compiler. Brian Evans has improved the interface to Matlab so that the makefiles do not need to be modified to incorporate it. Various team members contributed various minor bug fixes and enhancements for the 0.5.2 release. 2.7 The Next Ptolemy Release The 0.5.2 alpha release has occurred. The alpha sites include Structured Software Systems SGS Thomson the Technical University of Darmstadt, Germany Boston University Compass Design Automation Lockheed Sanders Comsat Other groups at Berkeley Initial reports indicate remarkably few problems. We expect to announce the beta release by April 20. Special thanks to Jose Pino for contributing a number of bug fixes that allowed for timely release of the alpha version. 2.8 Infrastructure Christopher Hylands has upgraded our Solaris machines to version 2.4. He has also installed Octave, which we are evaluation as freely distributable alternative to Matlab. Octave is a high-level language, primarily intended for numerical computations. It provides a convenient command line interface for solving linear and nonlinear problems numerically, and for performing other numerical experiments. It may also be used as a batch-oriented language. Its free distribution could significantly simplify our installation scripts, since we can include it with Ptolemy, while Matlab cannot be included with Ptolemy. 3. Problems Encountered We continue to have problems with signals on Solaris machines. While we had found workarounds for Solaris version 2.3, these failed on Solaris 2.4. 4. Schedule Reconciliation No changes. 5. Next Period Activities Aside from normal continuation of ongoing activities, we anticipate the following activities. - Release 0.5.2 beta. - Continue incremental compilation experiments. - Investigate Hybrid Systems for applicability to combined dataflow/FSM. - Continue implementation of FSM capabilities. - Continue work on a software architecture supporting modular syntax. 6. Conferences, Meetings, and Trips Presentations: [1] "An Overview of the Ptolemy Project," Edward A. Lee, at Stanford University, April 13, 1995. [2] "A View of System-Level Design," Edward A. Lee, at the Alta Group of Cadence Design Systems, April 13, 1995. [3] "A View of System-Level Design," Edward A. Lee, at the DSP Seminar, UC Berkeley, April 14, 1995. Meetings: Edward Lee participated in an NSF workshop on system level design held in Boulder, Colorado on April 3 and 4. Wim Smits, of Philips Research, Eindhoven, visited our Lab for three days, April 12-14, to help set up a programmable video signal processing facility. This is now functional. 7. Publications The following publications have been completed or accepted for publication in this reporting period: [4] S. S. Bhattacharyya, P. K. Murthy, and E. A. Lee, "Optimal Parenthesization of Lexical Orderings for DSP Block 'Diagrams," submitted to the 1995 IEEE Workshop on VLSI Signal Processing, March 28, 1995. [5] B. L. Evans, Douglas R. Firth, Kennard D. White, and E. A. Lee, "Automatic Generation of Programs That Jointly Optimize Characteristics of Analog Filter Designs," to appear Proc. of European Conference on Circuit Theory and Design, August 27-31, 1995, Istanbul, Turkey. The following has appeared in print: [6] S. S. Bhattacharyya, J. T. Buck, S. Ha, and E. A. Lee, "Generating Compact Code from Dataflow Specifications of Multirate Signal Processing Algorithms," IEEE Transactions on Circuits and Systems - I: Fundamental Theory and Applications, Vol. 42, No. 3, pages 138-150, March, 1995.