Monthly R&D Status Report
Date: December 15, 1996
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 period was dominated by preparations for the release of Tycho,
which will occur within a few days. Other major accomplishments
include completion of a PhD thesis on scheduling techniques for
synchronous and multidimensional synchronous dataflow.
2. Significant Accomplishments
2.1 Scheduling
Praveen Murthy has completed and filed a PhD thesis on scheduling
techniques for synchronous and multidimensional synchronous dataflow.
Below is the abstract.
"In this thesis, we present various scheduling techniques for
programs expressed as Synchronous Dataflow (SDF) and
Multidimensional Synchronous dataflow graphs. Synchronous dataflow
has proven efficient as a specification model for block-diagram
based programming environments for signal processing. Two key
reasons for its popularity are that a) static schedules can be
constructed at compile time, thus eliminating the overhead due to
dynamic scheduling, and b) it models multirate signal processing
application very naturally and intuitively. The first property is
particularly important in environments where code-synthesis for
embedded processors is desirable, since embedded signal processing
applications have rigid throughput requirements in order to meet
hard- real-time constraints. Multidimensional Synchronous Dataflow
(MDSDF) is an extension of SDF to multiple dimensions; in this
model, applications such as image and video signal processing,
which operate on multidimensional signal spaces, are more naturally
modeled and specified than in SDF.
The amount of on-chip memory available on embedded processors is
often severely limited. Adding off-chip memory is usually not an
option because it entails a speed penalty, it increases overall
system cost and size, and increases power requirements. Thus, when
generating software implementations from SDF specifications for a
uniprocessor, the scheduling problem of minimizing code size and
buffer memory size becomes crucial. If the scheduling is not done
carefully, the blowup in the size of the implementation can
preclude implementation on the processor. Previous techniques have
focused on scheduling to minimize code size. However, this
neglected the buffer memory usage of the schedule; in this thesis,
we develop techniques that jointly minimize for code size and
buffer-memory size of the software implementation. We give three
polynomial-time algorithms: a dynamic programming algorithm that is
used as a post-optimization step, and two heuristics that use
different approaches to constructing these schedules. The general
problem is shown to be NP-complete, thus justifying the use of
heuristics. An extensive experimental study is given to show the
efficacy of all these techniques.
We extend these scheduling results to MDSDF specifications. We then
tackle a problem of a different type. A multidimensional signal can
be sampled in many different ways. A straightforward extension of
one-dimensional sampling results in the so-called rectangular
sampling structure, where the samples lie on a rectangular grid.
However, a more general sampling structure is a geometrical
lattice; sampling lattices that are not rectangular can have many
advantages in certain applications. For example, a signal sampled
on a non-rectangular lattice can have a lower sampling density than
one sampled on an equivalent rectangular lattice. For real-time
processing of multidimensional signals, a lower sampling density
means fewer samples to process in a given time interval. The
standard MDSDF model suffers from the inability to model
multidimensional systems sampled on arbitrary sampling lattices;
hence, we give an extension of MDSDF that is capable of modeling
such systems. The model we give preserves the property of static,
compile-time schedulability. However, constructing such schedules
requires the solution to some challenging problems. In particular,
we show that an augmented set of balance equations have to be
solved simultaneously in the extended model. The additional
equations are quite different from the usual balance equations in
SDF and MDSDF; they involve computing so-called "integer volumes"
of parallelepipeds. This computation turns out to be an interesting
number-theoretic problem, and we present several approaches for
solving it. Finally, we present a practical example of a video
sampling structure conversion system to show the usefulness of the
generalized MDSDF model."
2.2 Specification and Modeling of Reactive Real-Time Systems Class
The class on specification and modeling of reactive real-time systems
has concluded, and project presentations were made on the following
topics:
* Synchronous/Reactive Domain in Ptolemy
* A study of Trace Theory and its application to modeling concurrent systems
* Kahn Process Networks in Java
* Concurrent models based on Java Threads
* Comparing Reactive Languages
* Petri Nets related to Dataflow
* FMSs and Dataflow combined
* Simulation of Hybrid Systems in Java
2.3 Improvements to Tycho
There were a very large number of improvements to Tycho in this time
period in preparation for a release. These include:
* many bug fixes,
* interactive documentation of the graphics infrastructure,
* improvements to dynamic loading,
* construction of a standalone Tcl profiler (independent of TclX),
* printing of text and graphics files,
* exporting of graphics files to EPS, GIF, and XWD formats,
* enhanced dialog construction tools,
* speed improvements in graph layout code, and
* enhanced library for portable operating system interaction.
The Macintosh and NT ports of Tycho are progressing, although the
Macintosh port continues to show problems. We will not hold up the
release for it.
2.4 Other uses of Ptolemy
The CAD group at Berkeley has announced the public availability of the
POLIS-v0.2 co-design environment for control-dominated embedded
systems, which is based on Ptolemy.
POLIS offers an integrated interactive environment for specification,
co-simulation, formal verification, and synthesis of embedded systems
implemented as a mix of hardware and software components. Version 0.2
offer many add features, including brand new microcontroller resource
library handling and Ptolemy simulation debugging.
Most of the information about POLIS, including pointers to source and
object code (for various CPUs and OSes) is available at our WEB site:
http://www-cad.eecs.berkeley.edu/Respep/Research/hsc/abstract.html
3. Publications and Presentations
3.1 Publications
[1] "Scheduling Techniques for Synchronous And Multidimensional
Synchronous Dataflow," Praveen Murthy, PhD thesis, November 1996.
3.2 Presentations
* "Synchronous programming languages for reactive systems," Alain
Girault, Visiting Scholar, Dept. of Electrical Engineering and Computer
Science, UC Berkeley, November 21, 1996. See:
http://ptolemy.eecs.berkeley.edu/design-seminar/nov21.html
* "Moderated Panel," Edward Lee, Richard Newton, and Jan Rabaey,
Design, Modeling, and Specification of Systems Seminar, Thursday
December 5.
* "Abstractions for System-Level Design," Prof. Edward A. Lee, UC Berkeley,
Invited talk at UC Davis Dept. of ECE, December 6, 1996.
* "The SR Domain Ptolemy," Stephen Edwards, Workshop on
Synchronous Languages, Dagstuhl, December 9, 1996.
* "Modelling Distribution with Partial Orders," Alain Girault, Workshop on
Synchronous Languages, Dagstuhl, December 12, 1996.
3.3 Guest Presentations
* "Methods, Models and a CAD Methodology," Daniel Gajski, Information
and Computer Science, University of California at Irvine, CAD Seminar,
Wednesday, December 4, 1996.