Monthly R&D Status Report
Date: December 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

Major advances in this time period include an improved infrastructure
for Ptolemy/Matlab interaction, a first-cut design-methodology management
capability in Ptolemy, a fundamental advance in synchronous scheduling,
and major improvements in heterogeneous scheduling and code generation.


2. Significant Accomplishments

2.1. Matlab Integration

Brian Evans has defined a Tcl procedure for interfacing with Matlab
that provides all of the functionality of the C++ interface that we have
been using to date.  This makes it considerably more convenient to
integrate Matlab activities into Ptolemy designs.  For example,
Matlab commands can be used in parameter calculations, Tcl scripts,
and interfaces to Matlab during cosimulation. The commands included are:

   terminate connection:       matlab end
   evaluate Matlab script:     matlab eval <script>
   get matrix as Tcl strings:  matlab get <name>
   evaluate Matlab script:     matlab send <script>
   set matrix as Tcl strings:  matlab set <name> <rows> <cols> <real> ?<imag>?
   start the Matlab process:   matlab start
   unset a matrix:             matlab unset

The "matlab send" command will not return the output generated by
Matlab, whereas "matlab eval" will return it as a single string. As an
example, "matlab send {plot( [1 2 3] )}" will create a simple plot.
These commands can be invoked manually or by scripts from within
Ptolemy or Tycho.  The interface is generic enough to be used in any
C or C++ program.


2.2 Design Methodology Management

Asawaree Kalavade has installed the DMM (design methodology management)
domain and the associated design assistant.  The design assistant is a
target the manages complex design flows within the DMM domain.  Various
members of the group are studying the design of this domain and tuning
the code.  Brian Evans made a detailed pass over the code, removing
memory leaks and redundant code.


2.2. Control and Signal Processing

In collaboration with Bart Kienhuis of Philips Research Laboratories
in the Netherlands, we have begun to port Ptolemy's thread classes to
the POSIX thread implementation in Hewlett Packard's HPUX operating
system.  This will give us an implementation of the Process Network
(PN) domain for HPUX, in addition to the existing SunOS and Solaris
implementations of the domain.  Tom Parks has been working on a
port to Solaris 2.5, which has built-in POSIX threads.


2.3. Mixing Models of Computation

Our research effort on mixing models of computation has focused on
the interaction between dataflow and discrete-event models.  The main
issue is in handling the different notions of "time", i.e. the
ordering relations among events, in these two models.  We have already
implemented in Ptolemy one reasonable policy to handle this timing
issue.  We are now studying this issue in more general terms, trying
to define a proper policy for handling the dataflow/discrete-event
interaction, as well as re-examining Ptolemy's current policy.  Our
guiding principle is to have determinate computation whenever
possible.  We found that the concept of an "iteration" in executing a
dataflow graph plays a major role in handling time.  This raises
interesting issues and has important implications on how to schedule a
dataflow graph so that it can interact with a discrete-event subsystem
in a determinate fashion.


2.4. Code Generation Wormholes

Jose Pino has redesigned the clustering classes in Ptolemy and has
reimplemented his hierarchical scheduler to use these new classes. The
new Cluster class is derived from a dynamic galaxy. It is intended to
modify the original graph specified by the user. It uses a new Scope
class to preserve the inherited parameters and the original name. This
separate scoping of the parameters solves a major problem that we had
with algorithms that involved modifying the graph structure during the
scheduling process. Jose spent a lot of effort to make the absorb/merge
operations efficient.

The default clustering classes do not use wormholes. We believe these
are only necessary when interfacing schedulers that were not designed
to directly interact. Jose's hierarchical scheduler, by contrast, is
designed to manage the interfacing of different schedulers.

As a side effect of these changes, Jose improved the list classes in
the Ptolemy kernel to make it possible to remove members of a list while
there are active iterators operating on the list.  This restriction had
been a major source of complexity in some of the kernel code.
List iteration becomes linear in the number of items instead of quadratic:
before, if we deleted an item, we had to reset the pointer to the
beginning of the list.

Jose has also defined some new iterators to help traverse a graph:

        BlockInputIter
        BlockOutputIter
        SuccessorIter
        PredecessorIter

He also added some cluster-specific iterators:

        ClusterIter
        SuccessorClusterIter
        PredecessorClusterIter

He has also defined a couple of useful visualization functions:

        printDot - outputs a galaxy hierarchy in dotty format
        printClusterDot - outputs the galaxy in it's clustered form

These outputs interface directly to a freely available graph visualization
program.


2.5. Technical Improvements to Ptolemy

Wan-Teh Chang and Jose Pino have modified the default single-processor
scheduler in the synchronous dataflow domains to be the loop scheduler.
This scheduler generates much more compact schedules for multirate systems,
and runs considerably faster than the previous scheduler.

Bilung Lee and Brian Evans reorganized the image processing capabilies
in Ptolemy to remove classes in the SDF (synchronous dataflow) domain
that properly belong in the DE (discrete event) domain.

Jose Pino and Brian Evans have removed almost all memory leaks from
the Ptolemy kernel and the SDF domain.


2.6. Technical Improvements to Tycho

We have created an HTML browser in Tycho and are using to integrate all
of the Tycho documentation. It uses a library written by Stephen Uhler
(stephen.uhler@sun.com) of Sun Microsystems to do the rendering. It
supports an extension of HTML with embedded Tcl scripts. The scripts
are colored (in blue, by default). If the user double clicks on a
script, the Tcl script is executed in the global namespace. Currently,
http references are not supported.


3. Infrastructure

Christopher Hylands spent considerable time responding to break-ins
and tightening security on our machines.

We have obtained an Ultrasparc and have begun to port Ptolemy to
Solaris2.5.


4. Meetings and Presentations

   * H. John Reekie, Specifying Visual Languages Visually, Digital
     Signal Processing Seminar, Nov. 17, 1995.

   * Edward A. Lee, An Overview of Research in Design Methodology for
     DSP, ALTA Group Seminar, November 29, 1995.

   * Praveen Murthy was invited to visit Thomson in Paris, where he
     gave a talk on multidimensional dataflow.  He also met with
     members of the Array oriented language team (Alain Demeure), and
     the constrained logic programming team (Jean Jourdan).

   * The Ptolemy team met with representatives from Thomson to discuss
     their decision to use Ptolemy for system-level design on Dec. 7, 1995.

   * The Ptolemy team met with representatives from Thomson to discuss
     multidimensional signal processing in Ptolemy on Dec. 8, 1995.

Relevant presentations made by Others at Berkeley:

   * Michael Jackson (Motorola), Design Technology at Motorola, CAD
     Seminar, November 15, 1995.

   * Denis Caromel (INRIA), Parallel Object-Oriented Programming within
     the SLOOP System, Special Seminar, December 11, 1995.

   * Isabelle Attali (INRIA), A Formal Semantics and an Interactive
     Environment for Sisal, Special Seminar, December 11, 1995.


5. Publications

The following Ph.D. thesis has been completed and filed:

[1] Thomas M. Parks, Bounded Scheduling of Process Networks. PhD
    Dissertation, Department of Electrical Engineering and Computer
    Sciences, University of California. Berkeley CA 94720. December 1995.

The following paper has been accepted:

[2] S. S. Bhattacharyya, S. Sriram, and E. A. Lee, "Self-Timed
    Resynchronization: a Post-Optimization for Static Multiprocessor
    Schedule," accepted to Int. Parallel Processing Symposium, 1996.

The following invited papers have been completed:

[3] A. Kalavade and E. A. Lee, "The Extended Partitioning Problem:
    Hardware/Software Mapping, Scheduling, and Implementation-bin
    Selection," invited to Design Automation for Embedded Systems Journal,
    special issue on System Partitioning. Ed. Rajesh Gupta.

[4] K. Chiang, B. L. Evans, W. T. Huang, F. Kovac, E. A. Lee, H. J. Reekie, D.
    G. Messerschmitt, and S. Sastry, ``Real-Time DSP for Sophomores,'' to
    appear in Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal
    Processing, Atlanta, GA, May 1996.