Monthly R&D Status Report
Date: October 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
Most notable in this reporting period were a number of technical
improvements to Ptolemy, including an interface to Tcl for setting
parameter values, a major redesign of the Ptolemy makefiles, and
significant improvements in our management of documentation. Also, we saw
the first signs of life for a version of Ptolemy on a Macintosh (using the
Tycho interface).
This reporting period was also notable for the turnover in the group.
Three long-time members of the group have left, having completed (or almost
completed) their Ph.D's. We have a new postdoc, a new industrial fellow,
three new graduate students, and two new undergraduates in the group.
We have fully updated the research summaries, which describe the
activities of each member of the group. They are accessible through our
web page, http://ptolemy.eecs.berkeley.edu.
Other progress included a new release of Mathematica packages and
notebooks for working with algebraic representations of signals and
systems, and a new resynchronization algorithm for two processor
systems.
2. Significant Accomplishments
2.1. Parallel Processing
Shuvra Bhattacharyya (now of Hitachi America) and S. Sriram have
developed a new, general, latency constrained resynchronization
(LCR) algorithm for 2 processor systems that is capable of handling
delays. This algorithm is provably optimal, and the proof is relatively
simple.
2.2. Symbolic Processing
Brian Evans' Mathematica notebooks designed for teaching signal processing
(and keyed to the popular textbook by Strum and Kirk) have been released in
a new, commercial version. The notebooks are based on a new version of
the Signal Processing Packages, which have been rewritten to conform with
the rest of Mathematica and contain many new functions and bug fixes. The
previous version of the packages is still available for free on the net
(pointers are on the Ptolemy World Wide Web page).
Some of the enhanced functionality of Version 3.0 of the Signal Processing
Packages includes improvements in the convolution routines to handle
intervals with symbolic endpoints, graphical design of two-dimensional
decimators, signal plotting and the digital and analog analysis/reporting
functions. Special thanks to John Novak at Wolfram Research Inc. for
working with Brian on this upgrade.
Version 3.0 is currently available in two commercial products:
1. Brian L. Evans and John M. Novak, "Signals and Systems Pack," a
volume in the Mathematica Applications Library, Wolfram Research
Inc., October 2, 1995.
2. Brian L. Evans, Steve X. Gu, Edward A. Lee, and Philip Chen,
"Mathematica Notebooks to Accompany Contemporary Linear Systems
Using MATLAB", PWS Publishing Company, ISBN 0-534-93509-5 (PC) and
0-534-93507-9 (Mac), June, 1995, an interactive companion to the
textbook Robert D. Strum and Donald E. Kirk, Contemporary Linear
Systems Using MATLAB, PWS Publishing Company, ISBN 0-534-94710-7,
1995.
The Wolfram Research Inc. product retails for $295, is backed by their
Technical Support Staff, is fully documented by a 200-page report, has
automatic installation, and contains Version 3.0.1 of the Signal
Processing Packages. Documentation is in printed and notebook form,
and is geared for the design engineer.
The PWS product retails for $30. The tradeoff for this significantly
lower price is that it comes with limited technical support, manual
installation instructions, and no printed user or reference manuals.
It is, however, electronically documented by means of 20 Mathematica
notebooks. Two of the notebooks serve as an introduction to Mathematica
and to the Signal Processing Packages, respectively. Each pair of
remaining notebooks corresponds to one chapter in the textbook. One
notebook in each pair works the example problems, gives the homework
problems, and automatically checks student answers to homework problems.
The other notebook in each pair explains the solutions to the homework
problems. This Mathematica Companion can be used independently of the
Strum/Kirk textbook.
2.3. Technical Improvements to Ptolemy
Brian Evans built into the parameter expression parser in Ptolemy the
ability to evaluate arbitrary Tcl scripts. When an exclamation point
("!") is encounted, the next token is evaluated as a Tcl command. The
designer can now access the transcendental math functions of Tcl, such as
cosine and square root. This approach not only augments our parameter
expression language with the full power of Tcl, but also provides a generic
mechanism for interfacing to foreign tools, such as Mathematica, via Tcl.
Steve Gu and Brian Evans are continuing working on a Tcl interface to
Mathematica.
Brian has also systematically removed several remaining memory leaks in
Ptolemy, and has also replaced somewhat fragile code that was based on
fixed-length strings with code that dynamically allocates memory. He has
also fixed a number of problems with the compile-SDF target, which
generates a standalone C++ program from a Ptolemy schematic. This target,
in the past, did not work with Tcl/Tk blocks.
Jose Pino and Christopher Hylands have redesigned the Ptolemy makefiles
to remove a great deal of code duplication and to make it easy to construct
customized versions of Ptolemy with specific domains and block libraries
included.
Christopher Hylands has continued to improve the way we use shared
libraries in Ptolemy, striking a balance between small binaries and quick
startup.
Jose Pino has created a perl script to translate our FrameMaker master
publications directory into HTML, thus enabling us to upgrade to version
5.0 of Frame. Jose also converted the User's manual to Adobe's PDF
format, which can be read off the net with an acrobat reader. This
format is much more sophisticated than HTML, allowing us to provide a
fully usable on-line user's manual.
Steven Kimball of Sanders provided a patch that makes our current Ptolemy
release operational under Unixware 1.1. Neal Becker (of Comsat) has
provided a patch that makes our current Ptolemy release operational on
Linux-ELF.
2.4. Technical Improvements to Tycho
Christopher Hylands installed the alpha release of Tcl 7.5, which partially
works on Macintosh and Microsoft Windows PCs. He was able to get some of
the basic Tycho functionality operational on a Mac. He has also installed
a beta version of Itcl 2.0, and we have begun porting Tycho to take
advantage of its new features. Most importantly, Itcl 2.0 supports the
notion of mega-widgets, composite graphical objects that behave exactly
like native Tk widgets, but can be constructed using a fully
object-oriented approach.
2.5 Multidimensional Multirate Signal Processing
The design of multidimensional multirate signal processing systems. e.g.
systems that change video formats in non-separable ways, often require
application-specific design tools. For example, much of the design work
in computing system parameters in multidimensional multirate systems can
be simplified with a combination of computational geometry, integer
matrix algebra, and state-space formulations. In multiple dimensions,
rate-changing operations are defined by a change in sampling grids.
Sampling grids can be represented as a set of basis vectors, which can be
considered as the column vectors that make up a sampling matrix. Mapping
one sampling matrix onto another is a linear mapping represented by a
rational matrix, called a resampling matrix. Brian Evans and Juergen Teich
have shown how to design two-dimensional rate changing systems (upsampler,
filter, and downsampler in cascade) based on a geometric sketch of the
passband to retain. From the sketched region, we use computational
geometric techniques to find the minimal enclosing parallelogram using a
linear time and linear space algorithm we have developed. We then use the
minimal enclosing parallelogram to compute the resampling matrix to perform
the sampling conversion using Chen and Vaidyanathan's approach. Then, we
factor the resampling matrix into the upsampling and downsampling matrices
for the rate changer. The procedure will find the best compression rate
based on a parallelogram-shaped passband. The only other admissible
geometry is a hexagonal-shaped passband, which will always do at least as
well as the parallelogram-shaped passband. Generalizing this approach to
multiple channels will enable the graphical design of two-dimensional filter
banks and wavelets, on which Bill Chen and Brian Evans are working. Brian
Evans has already shown how to apply integer matrix algebra to simplify the
design of multidimensional filter banks and wavelets.
3. Personnel changes
Asawaree Kalavade, having completed her Ph.D., has joined AT&T Bell Labs.
S. Sriram, who will be imminently filing his Ph.D. thesis, has taken a job
at Texas Instruments. Tom Parks has accepted a job at Lincoln Labs, and
is finishing his Ph.D. thesis in Cambridge.
John Reekie has joined our group as a postdoctoral researcher. John comes
from the Technical University of Sydney, Australia, and is interested in
functional language theory and compilers and parallel implementations of
signal processing algorithms. His postdoc position is funded by SRC.
Takashi Miyazaki, an industrial fellow from NEC, has joined the group
to work on real-time video signal processing and DSP architectures.
There are three new graduate students in the group as well. Stephen
Edwards comes from the CAD group at Berkeley, and is interested in
hierarchical finite state machines, statecharts, Esterel, Esterel
compilers, and software engineering. Ron Galicia joins the group after
getting his masters in image processing, and is interested in
hardware/software codesign. William Chen will be working on
2-D filter bank design based on geometric decompositions.
Two undergraduates have also joined the group. Huang Pan is working on
code generation in C and William Tsu is working on integrated VHDL
simulators.
4. Meetings and Presentations
Edward Lee presided over the semi-annual technical review board
meeting of the Sanders (a Lockheed-Martin Company) RASSP project
on October 13.
Relevant presentations made by Others at Berkeley:
[1] Jack B. Dennis, Associate Member, MIT Laboratory for Computer Science
"Mapping of Stream-Based Computations for Distributed Execution," Sept.
22, 1995.
[2] Andrea Casotto, from Runtime Design Automation, "Design Management
using Run-time Tracing," September 28, 1995.
5. Publications
The following memorandum has been completed:
[1] S. S. Bhattacharyya, S. Sriram, and E. A. Lee, "Resynchronization for
Embedded Multiprocessors", Memorandum UCB/ERL M95/70, Electronics
Research Laboratory, University of California at Berkeley, September,
1995.
The following paper has been submitted:
[2] S. S. Bhattacharyya, S. Sriram, and E. A. Lee, "Self-timed
Resynchronization: a Post-optimization for Staic Multiprocessor
Schedules," submitted to the International Parallel Processing
Symposium, September 18, 1995.