leff@smu.CSNET.UUCP (07/10/87)
Naomi Schulman
Publications
COMPUTER SYSTEMS LABORATORY
STANFORD UNIVERSITY
Stanford, CA 94305
RECENT REPORTS & NOTES
LIST #9
OCTOBER, 1986
To order reports see end of this announcement.
ABSTRACTS
CSL-TR-86-302
Preemptable Remote Execution Facilities for Loosely-Coupled Distributed
Systems
Marvin M. Theimer
June 1986 139 pages.....$9.45
A loosely-coupled distributed system consisting of a cluster of workstations
and server machines represents a large amount of computational power, much of
which is frequently idle. Users would like to take advantage of this idle
processing power by running one or more jobs in parallel on underutilized
workstations. In this thesis, we study the key design and performance issues
that affect preemptable remote execution in a loosely-coupled distributed
system. Five major topics are addressed in our work: (1) provision of
network-transparent execution environments for programs, (2) structuring
migration facilities such that they interfere with the normal operation of the
system in a minimal manner, (3) elimination of residual dependencies that occur
when a program migrates but has state information left in machine-relative
servers on the original machine, (4) provision of global scheduling facilities
for finding idle/lightly loaded machines for remote execution and migration of
programs, and (5) provision of fair access to global resources among the
programs and users of a system. In the process of addressing these topics we
delineate when remote execution facilities, with or without migration
facilities, are useful and under what conditions they are easy (or difficult)
to provide.
-------------------------------------------------------------------------------
T.R. 86-303
The Semantics of Timing Constructs in Hardware Description Languages
David C. Luckham, Youm Huh & Alec G. Stanculescu
August 1986 31 pages.....$4.05
Three different approaches to the representation of time in high level hardware
design languages are described and compared. The first is the timed assignment
statement of ADLIB/SABLE which anticipates future events. The second is the
timed assignment of VHDL which predicts future events and allows predictions to
be preempted by other predictions. The third is a new proposed method of
expressing time dependency by qualifying expressions so that their values are
required to be constant over a specified time interval. Examples comparing
these three approaches are given. It is shown how time-qualified expressions
could be introduced into a hardware description language. The possibility of
proving correctness of hardware models in this language is illustrated.
-------------------------------------------------------------------------------
CSL T.R. 86-304
An Analytical Cache Model
Anant Agarwal, Mark Horowitz & John Hennessy
September 1986 47 pages.....$4.85
Trace driven simulation and hardware measurement are the techniques most often
used to obtain accurate performance figures for caches. The former requires a
large amount of simulation time to evaluate each cache configuration while the
latter is restricted to measurements of existing caches. An analytical cache
model that uses parameters extracted from address traces of programs can
provide estimates of cache performance and show the effects of varying cache
parameters. By representing the factors that affect cache performance, we
develop an analytical model that gives miss rates for a given trace as a
function of cache-size, degree of associativity, block-size, multiprogramming
level, task switch interval, and observation interval. The predicted values
closely approximate the results of trace drive simulations while requiring only
a small fraction of the computation cost.
-------------------------------------------------------------------------------
CSL-TR-86-305
An Environment for Ada Software Development Based on Formal Specification
David C. Luckham, Randall Neff and David Rosenblum
August 1986 46 pages.....$4.80
This report gives an overview of the current status and plans to construct a
prototype environment of advanced tools for software and hardware development
based on the use of wide-spectrum languages. The wide-spectrum languages
include Anna (ANNotated Ada), TSL (Task Sequencing Language), and HDL (Hardware
Design Language). The tools described here provide interactive aid at all
stages in the system development process, including both the software and
hardware components of systems. Special emphasis is placed on distributed
computing, both in providing tools for handling parallelism in the subject
system, and in designing tools that utilize parallelism in the programming
environment. Applications of these tools include requirements analysis, formal
specification, rapid prototyping, testing, formal verfication and construction
of self-testing Ada software for multi-processor systems.
-------------------------------------------------------------------------------
CSL-TR-86-306
Queueing Network Models for Parallel Processing of Task Systems:
An Operational Approach
by Victor W.K. Mak
September 1986 27 pages.....$3.85
Computer performance modeling of possibly complex computations running on
highly concurrent systems is considered. Earlier works in this area either
dealt with a very simple program structure or resulted in methods with
exponential complexity. A computationally efficient approximate solution
method is developed to compute the performance measures for series-parallel-
reducible task systems using queueing network models. Numerical results for a
number of test cases are presented and compared to those of simulations.
-------------------------------------------------------------------------------
CSL-TR-86-307
A Survey of Concurrent Architectures
Victor W.K. Mak
September 1986 34 pages.....$4.20
A survey of 18 different concurrent architectures is presented in this report.
Although this is by no means complete, it does cover a wide spectrum of both
commercial and research architectures. A scheme is proposed to describe
concurrent architectures using different dimensions: models of computation,
interconnection network, processing element, memory system, and application
areas.
-------------------------------------------------------------------------------
CSL-TR-86-308
Performance Optimization of Digital VLSI Circuits
David P. Marple
September 1986 141 pages.....$9.55
Designers of digital VLSI circuits have virtually no computer tools available
for the optimization of circuit performance. Instead, a designer relies
extensively on circuit analysis tools, such as circuit simulation SPICE, and/or
critical delay path analysis. A circuit analysis approach to digital design is
very labor intensive and seldom produces a circuit with optimum area/delay or
power/delay tradeoff.
The goal of this research is to provide a synthesis approach to the design of
digital circuits by finding the sizes of transistors that optimize circuit
performance (delay, area, power). Solutions are found which are optimum for
all possible delay paths of a given circuit and not for just a single path.
The approach of this research is to formulate the problem of area/delay or
power/delay optimization as a nonlinear program. Conditions for optimality are
then established using graph theory and Kuhn-Tucker conditions. Finally the
use of augmented Lagrangian and projected Lagrangian algorithms are reviewed
for the solution of the nonlinear programs. Two computer programs, PLATO and
COP, have been developed by the author to optimize CMOS PLA's PLATO and general
CMOS circuits COP. These tools provably find the globally optimum transistor
sizes for a given circuit. Results are presented for PLA's and small to medium
sized cells.
-------------------------------------------------------------------------------
CSL-TR-86-309
Design of Testbed and Emulation Tools
by Stephen F. Lundstrom and Michael J. Flynn
September 1986 85 pages.....$6.75
The research summarized in this report was concerned with the design of testbed
and emulation tools suitable to assist in projecting, with reasonable accuracy,
the expected performance of highly concurrent computing systems on large,
complete applications. Such testbed and emulation tools are intended for the
eventual use of those exploring new concurrent system architectures and
organizations, either as users or as designers of such systems. While a range
of alternatives was considered, a software-based set of hierarchical tools was
chosen to provide maximum flexibility, to ease in moving to new computers as
technology improves and to take advantage of the inherent reliability and
availability of commercially available computing systems.
-------------------------------------------------------------------------------
CSL-TR-86-311
Distributed, Replicated Computer Bulletin Board Service
by July L. Edighoffer
June 1986 160 pages.....$10.50
Computer systems offer a variety of services to assist communication between
people. This dissertation examines computer bulletin boards, one such facility
that allows recipients to arrange for the delivery of messages on topics of
personal interest. The thesis focuses on the problems of replication and cost
scaling.
It is no longer necessarily true that users are closely tied to a single host,
yet current methods for replicating bulletin boards do not provice a good way
to represent what a person has seen that is independent of the copy read.
Existing replication algorithms either don't support copy-independent read
records or offer too little concurrency for this application. An original
replication algorithm provides a copy-independent ordering for submissions
using just a single copy of a bulletin board during the execution of the user
operations. The algorithm works well even on a network frequently in a state
of partition.
A more significant problem from the viewpoint of computer system administrators
is the cost of a distributed bulletin board service. In existing mail systems
and bulletin board systems, such as distribution on the Arpanet and USENET
running under UNIX, the cost per participating computer tends to grow in
proportion to the network size. The causes for this poor scaling will be
examined, then it will be explained how a structured name space together with
suitable operations on it leads to improved scaling by encouraging the creation
of highly specialized bulletin boards.
-------------------------------------------------------------------------------
CSL-TR-86-312
Concurrent Runtime Checking of Annotated Ada Programs
by David S. Rosenblum, Sriram Sankar and David C. Luckham
November 1986 40 pages.....$4.50
Anna is a language for writing machine-processable annotations of Ada programs.
One of the main applications of Anna is the runtime checking of an Ada program
for consistency with its formal specifications written in Anna. On
single-processor systems, Anna runtime checks are used during testing and
debugging of software.
This paper describes strategies for distributing Anna runtime checks so that
they are executed in parallel with the Ada program. Concurrent checking of an
annotated program can offer a substantial computational speedup over a
sequentially checked version of the same program. Concurrent checking of Anna
is therefore a crucial step in producing a self-checking program by allowing
runtime checks for annotations to reside permanently in production versions of
the program. Parallel checking will not always be useful in self-checking
code, but certain kinds of annotations require parallel checking in real-time
and interactive programs.
This paper defines an efficient parallel checking model in which checking is
performed by Ada tasks running in parallel with the underlying Ada program
being checked. The difficulties in reporting Anna consistency violations in a
parallel environment are also described. Finally, the paper discusses some of
the practical aspects of mixing checking strategies whereby sequential checking
may be applied to some kinds of annotations and distributed checking to other
kinds.
-------------------------------------------------------------------------------
Technical Notes
CSL T.N. 86-289
Architecture and Cache Simulation Results for Individual Benchmarks
by Chad L. Mitchell
June 1986 163 pages.....$10.65
This technical note contains the detailed simulation results for the work
discussed in CSL T.R. 86-296. Over fifty architectures were simulated for five
benchmarks. This note gives the results for each individual architecture and
benchmark combination with 26 different memory configurations.
-------------------------------------------------------------------------------
CSL T.N. 86-302
A Performance Comparison Between PLM and an MC68020 Prolog Processor
Hans Mulder and Evan Tick
September 1986 75 pages.....$6.25
This report compares the performance of the UC Berkeley Programmed Logic
Machine (PLM) and a generic MC68020 processor running large Prolog programs.
The PLM compiler translates Prolog source programs into the Warren Abstract
Machine (WAM) instruction set. The PLM is a microcoded host for the WAM.
Important built-in functions, e.g., general unification, are implemented in
microcode. The MC68020 model used assumes a compiler which first translates
Prolog source programs into WAM intermediate code and then into native MC68020
code. Important built-in functions are implemented as MC68020 subroutines.
Timing measurements of benchmark programs, in terms of cycles executed and
logical inferences per second (LIPS), are given for variants of these
architecture models. Results indicate that the MC68020 needs approximately 2.5
to 3.5 times the number of cycles needed by the PLM, primarily due to poor tag
handling.
-------------------------------------------------------------------------------
Publications
COMPUTER SYSTEMS LABORATORY
Stanford University
Stanford, CA 94305
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 302 $9.45 $3.00 TR 307 $4.20 $2.00
TR 303 $4.05 $2.00 TR 308 $9.55 $3.00
TR 304 $4.85 $2.00 TR 309 $6.75 $2.00
TR 305 $4.80 $2.00 TR 311 $10.50 $3.00
TR 306 $3.85 $2.00 TR 312 $4.50 $2.00
TN 289 $10.65
TN 302 $6.25
Subtotal __________
Your Local County CA tax __________
Total __________
-------