Monthly R&D Status Report Date: August 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 This month has been extremely busy, and there is much to report, both in terms of fundamental contributions and in software development. 2. Significant Accomplishments 2.1 Software Release Ptolemy 0.5.1-alpha has been released, but only to selected sites with intensive users (Fiat Labs, IMEC, White Eagle Systems, Synospys, Comsat, Berkeley Design Technology, and Structured Software Systems). Users at these sites have been extremely cooperative, helping us ensure compatibility with Linux, HP cfront, and Solaris 2.3. We thank them for their hard work. 2.2 Fundamental Progress Karim Khiar (a visitor from Thomson CSF) has completed a variety of sizable radar applications using the new higher-order function capability and a technique called multiprojection transformations to manage multidimensional data. Radar data typically has up to seven dimensions. The traditional representation of such algorithms uses multidimensional arrays. The multiprojection transformations serve the same role as transpositions of the arrays in the traditional representation. Karim has proven that the Distributor and Commutator stars in the synchronous dataflow (SDF) domain in Ptolemy can be combined to achieve the effect of any desired transposition. Thus, there is no loss of flexibility in going with the SDF representation for these algorithms. Moreover, we believe that the SDF representation is more intuitive and maintainable, and that it has no fundamental reason to be less efficient. We have not yet completed profiling of the execution, however, to determine whether our particular implementation is efficient. We have submitted a paper abstract to ICASSP '95 describing this work [2]. Our patent application for the ordered transaction architecture has been allowed by the patent office. This is a multiprocessor architecture that takes advantage of approximate compile-time predictability in an algorithm. Transactions between processors are fully synchronized, as if semaphores were being used, but without the overhead of semaphores. We have been experimenting with a prototype of this architecture that we constructed last year using four Motorola DSP96000 processors. The CG96 domain in Ptolemy generates code for this multiprocessor system, fully automating the partitioning and scheduling, using synchronous dataflow semantics. We are currently investigating how to support the more general Boolean dataflow semantics. Jose Pino has prototyped a heterogeneous scheduling framework in which a dataflow graph is divided into subgraphs through a clustering procedure. A parallelizing scheduler then partitions the clustered graph for parallel execution, while a loop scheduler handles the software synthesis within each cluster. We believe that this will solve a critical problem that we had encountered with our parallel schedulers with applications involving large sample-rate changes, namely that the code size of the synthesized software was often very large. Being able to use loop scheduling techniques greatly reduces the code size. We have submitted a paper proposal to ICASSP '95 describing this work [3]. Asawaree Kalavade has completed a very preliminary version of the Design Methodology Management (DMM) domain in Ptolemy. This will be used to graphically manage design flows that involve a variety of tools and modules working in concert. The domain has make-like semantics and communication between primitives (stars) is via files. The objective is to consider the design flow a first-class part of the design, having as much importance as other design details. Tom Parks has adapted results from preemptive rate-monotonic scheduling theory to non-preemptive scheduling of real-time signal processing systems. A process network model of computation [1] allows the flexible dynamic scheduling required by complex systems. A real-time multi-threaded dataflow execution model will be used for efficient implementation. An ICASSP paper proprosal has been prepared [4]. Bilung Lee has completed a library of stars in the SDF domain in Ptolemy for vector quantization. These will be included in the next release of Ptolemy (0.6?). 2.3 Technical Improvements to Ptolemy Jose Pino has made a number of technical improvements to the Target and CGTarget class in Ptolemy. Among these changes, he has made the HOF domain a subdomain of every other Ptolemy domain, with the principal objective of supporting higher-order functions in the code generation. Christopher Hylands, with some help from Jose Pino and Joe Buck (of Synopsys) has compiled Ptolemy under gcc version 2.6.0, in the process identifying one compiler bug, one change in the C++ language, and a few violations of information hiding in Ptolemy. He fixed the violations, installed a work-around for the compiler bug, and modified the code that violates the new C++ definition, ensuring that version 0.5.1 will compile under g++ version 2.6.0. However, since this version of the compiler is largely untested, the executables we distribute will still be built under version 2.5.8. Douglas Niehaus, of the University of Kansas, worked with us to modify the run control panel for Ptolemy applications to allow for easier development of Tcl scripts to control a simulation or code generation process. The modification introduces a new button, labeled "script", that opens a text editing window into which a Tcl script may be entered. This script is then stored in the design database along with the block diagram itself. 2.4 Interactions Dick Stevens and Chris Scannell of the Naval Research Labs spent 10 days at Berkeley working with us on two key tasks: (1) improvements to our dynamic dataflow scheduling techniques, and (2) support for the PGM concept of graph variables. Both of these tasks still need more work, but considerable progress was made. We plan to incorporate these improvements in the next version (0.6?) of Ptolemy. We have begun experimenting with Tcl scripts interfaced to the HTML WWW server to process more interactive requests, such as subscribing to a mailing list. Pending full understanding of the security issues, we have not yet made our prototypes publically available on the mosaic server (http://ptolemy.eecs.berkeley.edu). Gyorgy Csertan of the Technical University in Budapest has delivered most of the Ptolemy manual in HTML form. Thus, we now have a convenient on-line version of the manual with hypertext links. We are discussing a strategy for jointly maintaining the paper and on-line versions of the manual. Prof. Ron Fearing, in our own EECS department, has begun using the CGC domain in Ptolemy to develop real-time control code for robots. 2.5 Papers The following papers and proposals have been completed in this reporting period: [1] Edward A. Lee, "Dataflow Process Networks," UCB/ERL memorandum number 94/53, Electronics Research Laboratory, Univ. of California, Berkeley, CA 94720. Also available by ftp at ptolemy.eecs.berkeley.edu, in the file pub/ptolemy/papersprocessNets.ps.Z. [2] Karim P. Khiar and E. A. Lee, "Modeling Radar Systems Using Hierarchical Dataflow," paper proposal sent to ICASSP '95. [3] Jose Luis Pino and E. A. Lee, "Hierarchical Static Scheduling of Dataflow Graphs onto Multiple Processors," paper proposal sent to ICASSP '95. [4] T. M. Parks and E. A. Lee, "Non-Preemptive Real-Time Scheduling of Dataflow Systems," paper proposal sent to ICASSP '95. 3. Problems Encountered We have not yet received the HP workstation that we ordered, and cannot get access to an HP workstation with the Cfront version of C++. We have already planned a two week delay in the 0.5.1 release to give us more time to solve this problem. We are working with our alpha test sites to try to get complete testing of the HP port. The new mechamism developed by Christopher Hylands for dynamic linking based on the system V dlopen() function has a fundamental problem. When a module is relinked, replacing a previous dynamically linked version, any instances of objects created with the previous version are orphaned, with the memory containing their previous definition now having unpredictable contents. This can cause the Ptolemy system to crash if these obsolete instances are referenced. We are evaluating alternatives for dealing with this. Clearly, dynamic linking is something that needs work in Unix systems in general. Silicon Graphics is demanding what we believe to be inordinately high fees for software maintainance for their system software, much larger than the industry standard. As a consequence, we are cancelling the software maintainance contract. It is not clear at this point what impact this will have on our ability to support an SGI port of Ptolemy. 4. Schedule Reconciliation We are slightly behind schedule. The 0.5.1 has been postponed until August 29 (from August 15) to permit testing on an HP platform. This release will incorporate all existing patches, and will add the multidimensional dataflow domain (which is still very experimental), higher-order functions, initializable delays, the Matlab interface, and a number of additional functional blocks (stars). 5. Next Period Activities We plan to finalize the addendum to the User's Manual for the 0.5.1 release and post the release on the net. We plan to incorporate higher-order functions into the code generation domains. This will be particularly advantageous for describing applications that are to be executed in parallel. We plan to investigate using knowledge of the semantics of higher-order functions in the parallel schedulers in order to encapsulate in a modular way expertise about how to parallelize certain classes of algorithms. 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 Joe Buck of Synopsys organized a meeting with Sebastian Ritz, Matthias Pankert, and Peter Zepter, all of Prof. Heinrich Myer's research group from the University of Technology at Aachen. This group originated COSSAP and continues to feed research results into Cadis (now part of Synopsys). Topics of discussion included VHDL code generation, higher-order functions, Boolean dataflow code generation, and scheduling for embedded software synthesis. Brian Evans, Alan Kamas, and Edward Lee are attending the RASSP conference in Washington DC. A Ptolemy demo in the Lockheed/Sanders exhibit area is planned, and Prof. Lee will present a paper.