leff@smu.UUCP (Laurence Leff) (09/04/88)
Naomi Schulman
Publications
COMPUTER SYSTEMS LABORATORY
STANFORD UNIVERSITY
Stanford, CA 94305-4055
(415) 273-1430 (M-Th, 8-1)
RECENT REPORTS & NOTES
LIST #14
AUGUST 1988
To order reports, see end of this announcement.
ABSTRACTS
CSL-TR-88-353
THE MEANING OF TSL: AN ABSTRACT IMPLEMENTATION OF TSL-1
David P. Helmbold
March 1988 41 pages.....$4.55
TSL-1 is a language for specifying the sequences of tasking events which occur
during the execution of an Ada tasking program. The specifications appear in
the program as formal comments and are intended to help test and debug the
program. In addition, the specifications can form the basis of a comprehensive
toolset aiding the design, analysis, and implementation of parallel software.
There is a working prototype TSL-1 specification checker currently in use at
Stanford University.
This document presents the TSL-1 language constructs and defines their meaning
though an abstract implementation using event graphs. Each specification will
be associated with one or more event graphs. Tokens are placed on the event
graphs to record the progress made in satisfying the specifications. The
abstract implementation consists primarily of the detailed rules for the
placing of tokens on event graphs.
-------------------------------------------------------------------------------
CSL-TR-88-354
THE VMP MULTIPROCESSOR: INITIAL EXPERIENCE, REFINEMENTS AND PERFORMANCE
EVALUATION
D. R. Cheriton, A. Gupta, P. D. Boyle and H. A. Goosen
March 1988 26 pages.....$3.80
VMP is an experimental multiprocessor being developed at Stanford University,
suitable for high-performance workstations and server machines. Its primary
novelty lies in the use of software management of the per-processor caches and
the design decisions in the cache and bus that make this approach feasible.
The design and some uniprocessor trace-driven simulations indicating its
performance have been reported previously.
In this paper, we present our initial experience with the VMP design based on a
running prototype as well as various refinements to the design. Performance
evaluation is based both on measurement of actual execution as well as
trace-driven simulation of multiprocessor executions from the Mach operating
system.
-------------------------------------------------------------------------------
CSL-TR-88-355
INTRODUCTORY USER'S GUIDE TO THE ARCHITECT'S WORKBENCH TOOLS
1
Josep Torrellas, Brian Bray, Kathy Cuderman, Stephen Goldschmidt, Alan Kobrin,
and Andrew Zimmerman
May 1988 43 pages.....$4.65
The Architect's Workbench is a set of simulation tools to provide insight on
how the instruction set and the organization of registers and cache affect
processor-memory traffic and, as a result, processor performance. This report
is designed to be an introductory guide to the tools for the novice user.
-------------------------------------------------------------------------------
CSL-TR-88-356
COMPUTER-AIDED DESIGN AND OPTIMIZATION OF CONTROL UNITS FOR VLSI
PROCESSORS
Giovanni DeMicheli
March 1988 37 pages.....$4.35
This review presents the models, methods and algorithms for synthesis and
optimization of control units for VLSI processors. First, circuit structures
used for control in the state-of-the-art processors are described. The control
synthesis methods are then presented as well as the algorithms for optimizing
the control unit representation. Among these techniques, the symbolic design
methodology is described that can be applied to optimize the silicon area taken
by some particular structures of control units.
-------------------------------------------------------------------------------
CSL-TR-88-357
DESIGN AND VERIFICATION OF DISTRIBUTED TASKING SUPERVISORS
FOR CONCURRENT PROGAMMING LANGUAGES
David S. Rosenblum
March 1988 233 pages.....$14.50
A tasking supervisor implements the concurrency constructs of a concurrent
programming language. This thesis addresses two fundamental issues in
constructing distributed implementations of a concurrent language: (1)
Principles for designing a tasking supervisor for the language, and (2)
Practical techniques for verifying that the supervisor correctly implements the
semantics of the language. Previous research in concurrent languages has
focused on the design of constructs for expressing concurrency, while ignoring
these two important implementation issues.
The theory and practice of concurrent programming is in its infancy. The
research described in this thesis represents a major step toward the
development of a theory of constructing multiprocessor implementations of
concurrent programming languages.
-------------------------------------------------------------------------------
CSL-TR-88-358
INTERVIEWS: A C++ GRAPHICAL INTERFACE TOOLKIT
Mark A. Linton, Paul R. Calder, and John M. Vlissides
July 1988 14 pages.....$3.20
We have implemented an object-oriented user interface package, called
InterViews, that supports the composition of a graphical user interface from a
set of interactive objects. The base class for interactive objects, called an
interactor, and base class for composite objects, called a scene, define a
protocol for combining interactive behaviors. Subclasses of scene define
common types of composition: a box tiles its components, a tray allows
components to overlap or constrain each other's placement, a deck stacks its
components so that only one is visible, a frame adds a border, and a viewport
2
shows part of a component. Predefined components include menus, scrollers,
buttons, and text editors. InterViews also includes classes for structured
text and graphics. InterViews is written in C++ and runs on top of the X
window system.
-------------------------------------------------------------------------------
CSL-TR-88-359
The Unified Management of Memory in the V Distributed System
D. R. Cheriton
June 1988 24 pages.....$3.85
The low cost of random access memory (RAM) makes it feasible to put large
amounts of RAM on workstation-class machines. Given the choice, a large RAM is
attractive in place of a local disk because RAM is much faster than a disk.
However, many operating systems limit the effective utilization of RAM by
fragmenting the management of the memory across several cache and buffering
mechanisms, handling page frames, disk buffers and network buffers separately.
In particular, performance is lost due to: (1) inter-cache copies, (2)
duplication of data, and (3) competition and fragmentation between different
caching mechanisms for RAM. In addition, maintaining data consistency between
machines is difficult with multiple caches.
This paper describes a unified approach to the handling of RAM in the V
Distributed System. The design leads to a relatively simple kernel mechanism,
yet provides sophisticated file caching, demand-paged virtual memory with
consistency between machines and mapped I/O. Measurements indicate that the
design is comparable in performance to conventional kernel-based file systems,
but at a fraction of the kernel size.
-------------------------------------------------------------------------------
CSL-TR-88-360
EXPLOITING RECURSION TO SIMPLIFY RPC COMMUNICATION ARCHITECTURES
David R. Cheriton
June 1988 15 pages.....$3.25
Current communication architectures suffer from a growing collection of
protocols in the host operating systems, gateways and applications, resulting
in increasing implementation and maintenance cost, unreliability and
difficulties with interoperability. The remote procedure call (RPC) approach
has been used in some distributed systems to contain the diversity of
application layer protocols within the procedure call abstraction. However,
the same technique cannot be applied to lower layer protocols without violating
the strict notion of layers.
In this paper, we show how the RPC approach can be used for lower layer
protocols so that the resulting "layer violations" generate a simple recursive
structure. The benefits of exploiting recursion in a communication
architecture are similar to those realized from its
use as a programming technique; the resulting protocol architecture minimizes
the complexity and duplications of protocols and mechanism, thereby reducing
the cost of implementation and verification. We also sketch a redesigned DoD
Internet architecture that illustrates the potential benefits of this approach.
-------------------------------------------------------------------------------
CSL-TR-88-361
MULTICAST ROUTING IN INTERNETWORKS AND EXTENDED LANS
Stephen E. Deering
July 1988 16 pages.....$3.30
Multicasting is used within local-area networks to make distributed
3
applications more robust and more efficient. The growing need to distribute
applications across multiple, interconnected networks, and the increasing
availability of high-performance, high-capacity switching nodes and networks,
lead us to consider providing LAN-style multicasting across an internetwork.
In this paper, we propose extensions to two common internetwork routing
algorithms -- distance-vector routing and link-state routing -- to support
low-delay datagram multicasting. We also suggest modifications to the
single-spanning-tree routing algorithm, commonly used by link-layer bridges, to
reduce the costs of multicasting in large extended LANs. Finally, we show how
different link-layer and network-layer multicast routing algorithms can be
combined hierarchically to support multicasting across large, heterogeneous
internetworks.
-------------------------------------------------------------------------------
CSL-TR-88-362
HARDWARE C - A LANGUAGE FOR HARDWARE DESIGN
David C. Ku and Giovanni De Micheli
August 1988 47.....$4.85
High-Level synthesis is the transformation from a behavioral level
specification of hardware to a register transfer level description, which may
be mapped to a VLSI implementation. The success of high-level synthesis
systems is heavily dependent on how effectively the behavioral language
captures the ideas of the designer in a simple and understandable way. This
paper describes HardwareC, a hardware description language that is based on the
C programming language, extended with notions of concurrent processes, message
passing, explicit instantiation of procedures, and templates. The language is
used by the HERCULES High-Level Synthesis System.
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
CSL-TR-88-363
COMPUTER-AIDED SYNTHESIS OF A BIDIMENSIONAL DISCRETE COSINE TRANSFORM CHIP
Vittorio Rampa and Giovanni De Micheli
August l988 32 pages.....$4.10
This paper describes the design of an integrated circuit implementing a
Bidimensional Discrete Cosine Tranform (BDCT). Such a circuit may be used to
reduce redundancy of video information in low bit-rate transmission channels
and video compression for image storage and retrieval.
The chip architecture is motivated by the consideration that the BDCT equations
can be solved row-by-row and column-by-column by a simpler Monodimensional DCT
(MDCT). Therefore the chip structure is partitioned into three stages: the
first and the last one implement MDCTs while the second stage is a shared
memory array.
The DCT design was achieved by means of the OLYMPUS synthesis system, an
experimental suite of synthesis tools developed at Stanford University. A
parametrized behavioral description of the monodimensional DCT operator was
specified in a high-level language in terms of concurrent process communicating
through a shared medium. The circuit layout was synthesized automatically from
this description.
-------------------------------------------------------------------------------
CSL-TR-88-364
APPLYING OBJECT-ORIENTED DESIGN TO STRUCTURED GRAPHICS
John M. Vlissides and Mark A. Linton
August l988 16 pages.....$3.30
4
Structured graphics is useful for building applications that use a direct
manipulation metaphor. Object-oriented languages offer inheritance,
encapsulation, and runtime binding of operations to objects. Unfortunately,
standard structured graphics packages do not use an object-oriented model, and
object-oriented systems do not provide general-purpose structured graphics,
relying instead on low-level graphics primitives. An object-oriented approach
to structured graphics can give application programmers the benefits of both
paradigms.
We have implemented a two-dimensional structured graphics library in C++ that
presents an object-oriented model to the programmer. The graphic class defines
a general graphical object from which all others are derived. The picture
subclass supports hierarchical composition of graphics. Programmers can define
new graphical objects either statically by subclassing or dynamically by
composing instances of existing classes. We have used both this library and an
earlier, non-object-oriented library to implement a MacDraw-like drawing
editor. We discuss the fundamentals of the object-oriented design and its
advantages based on our experiences with both libraries.
-------------------------------------------------------------------------------
5
Naomi Schulman
COMPUTER SYSTEMS LABORATORY
Stanford University
Stanford, CA 94305-4055
EM:Schulman@Sierra.Stanford.Edu
415-723-1430
Hours: M-Th, 8-1
ORDER FORM
To Order Reports: Print or type your name and address in the space provided.
Check or circle the report(s) you wish to purchase, whether hardcopy or
microfiche. All orders must be PREPAID. CALIFORNIA RESIDENTS must add sales
tax of their local county. Return this order form with your check or money
order made payable to Stanford University. FOREIGN ORDERS must be paid with an
international money order or a check drawn on a U.S. bank, payable in dollars.
Please type or print your name and complete address:
______________________________________________
______________________________________________
______________________________________________
______________________________________________
______________________________________________
______________________________________________
Report # Hardcopy Microfiche Report # Hardcopy Microfiche
-------- -------- ---------- -------- -------- ----------
TR 353 $4.55 $2.00 TR 359 $3.85 $2.00
TR 354 $3.80 $2.00 TR 360 $3.25 $2.00
TR 355 $4.65 $2.00 TR 361 $3.30 $2.00
TR 356 $4.35 $2.00 TR 362 $4.85 $2.00
TR 357 $14.50 $4.00 TR 363 $4.10 $2.00
TR 358 $3.20 $2.00 TR 364 $3.30 $2.00
Subtotal __________
Your Local CA County tax __________
Total __________
-------