techreports-request@sally.UUCP (01/04/86)
From: smu!leff@waltz.UUCP (Laurence Leff)
Naomi Schulman
Publications
COMPUTER SYSTEMS LABORATORY
STANFORD UNIVERSITY
Stanford, CA 94305
RECENT REPORTS & NOTES
LIST #5
OCTOBER, 1985
ABSTRACTS
-------------------------------------------------------------------------------
T.R. 84-263
FILE ACCESS PERFORMANCE OF DISKLESS WORKSTATIONS
by E.D. Lazowska, J. Zahorjan, D.R. Cheriton, and W. Zwaenepoel
June 1984 27 pages.....$2.90
This paper studies the performance of single-user workstations that access
files remotely over a local area network. From the environmental, economic,
and administrative points of view, workstations that are diskless or that have
limited secondary storage are desirable at this point in time. Even with
changing technology, access to shared data will continue to be important. It
is likely that some performance penalty must be paid for remote rather than
local file access. Our objective is to assess this penalty, and to explore a
number of design alternatives that can serve to minimize it, using queueing
network performance models as an aid. We concluded from our study that a
system of diskless workstations with a shared file server can have satisfactory
performance comparable to that of a local disk in the lightly loaded case.
>From a performance point of view, augmenting the capabilities of the shared
file server may be more cost effective than augmenting the capabilities of the
client workstations.
-------------------------------------------------------------------------------
T.R. 84-264
ONE-TO-MANY INTERPROCESS COMMUNICATION IN THE V-SYSTEM
by D.R. Cheriton and W. Zwaenepoel
August 1984 10 pages.....$2.50
Interprocess communication (IPC) normally allows one process to communicate
with only one other process at a time. One-to-many IPC allows one process to
communicate simultaneously with a group of processes, possibly of unknown
membership. While the broadcast and multicast facilities of local networks
support efficient one-to-many communication between hosts, its use between
processes has been limited by the lack of support in distributed operating
systems. This paper describes the integration of one-to-many communication
into the V interprocess communication system. We discuss different models of
use and reliability and present some initial applications.
-------------------------------------------------------------------------------
T.R. 84-265
AN OVERVIEW OF ANNA - A SPECIFICATION LANGUAGE FOR ADA
by D. Luckham and F.W. von Henke
September 1984 23 pages.....$2.80
A specification language permits information about various aspects of a program
to be expressed in a precise machine processable form. This information is not
normally part of the program itself. Specification languages are viewed as
evolving from modern high level programming languages. The first step in this
evolution is cautious extension of the programming language. Some of the
features of Anna, a specification language extending Ada, are discussed. The
extensions include generalizations of constructs (such as type constraints)
that are already in Ada, and new constructs for specifying subprograms,
packages, exceptions, and contexts.
-------------------------------------------------------------------------------
CSL T.R. 84-266
TIMING VERIFICATION AND PERFORMANCE IMPROVEMENT OF MOS VLSI DESIGNS
by Norman Jouppi
October 1984 126 pages.....$6.40
This report is based upon the author's thesis. It investigates three aspects
of timing verification of MOS VLSI circuits. First, methods for estimating
design performance are developed. Second, methods for assisting the designer
in improving design performance are studied. Third, a high-performance
clocking discipline and algorithms for its verification are presented.
-------------------------------------------------------------------------------
CSL T.R. 84-267
THE INSTRUCTION BANDWIDTH OF DIRECT CORRESPONDENCE ARCHITECTURES
by Chad Leland Mitchell
December 1984 41 pages.....$3.50
This report describes evaluation of factors affecting the instruction bandwidth
of a class of architectures known as Direct Correspondence Architectures
(DCAs). These architectures exhibit very low instruction bandwidth when
compared to other classes of architectures. The contributions of various
factors to this low instruction bandwidth were evaluated by simulating
variations on a typical DCA architecture known as Adept. The simulations were
performed by modifying an Adept interpreter to estimate the instruction word
fetch counts for each variation. The results indicated that the methods used
by DCAs for very dense encoding of explicit operands allow DCA instructions to
carry more information than instructions in other architectures without
increasing the average instruction size. This accounts for most of the savings
in instruction bandwidth. The methods used by DCAs to reduce the number of
explicit operands greatly lower instruction bandwidth requirements only when
used with less dense operand encoding techniques.
-------------------------------------------------------------------------------
CSL T.R. 85-268
FABRIC: A PACKAGE FOR MANAGING INTERWOVEN DATA
by Mark A. Linton
March 1985 16 pages.....$2.55
Software development environments manage large databases of information about
programs. Since the relational data model does not directly support recursively
defined data structures such as the abstract syntax tree of a program,
representation of these structures in a relational system is inconvenient and
queries on these structures, such as to retrieve a subtree, are inefficient.
To support the needs of applications such as software developemtn environments,
we are designing and implementin g package for managing both relational and
recursively structured data. This package, called FABRIC, provides a set of
procedures for creating and accessing interwoven files of records, called
threads. The interface to FABRIC allows for experimentation with a variety of
implementations; we are exploring both interfacting to an existing database
system and the use of outward indices for clustering recursively defined data.
-------------------------------------------------------------------------------
CSL T.R. 85-269
A METHODOLOGY FOR THE DESIGN OF ADA TRANSFORMATION TOOLS IN
A DIANA ENVIRONMENT
by David S. Rosenblum
February 1985 21 pages.....$2.75
This paper describes a methodology for the design of a class of Ada software
tools which perform source-to-source transformations of Ada programs. The
tools perform the transformations on the DIANA representaion of an input source
program using a package of templates which are the DIANA representation of
source program textual insertions.
Following a brief overview of DIANA, the environment required by these tools is
described; a typical environment consists of an implementation of DIANA and a
set of utility programs. Next, the paper describes a "skeleton: program which
is used to implement a tool; the tool skeleton is a recursive DIANA tree
traversal program which is expanded incrementally with code to perform a set of
specific transformations. The next portion of the paper gives a detailed
description of the design methodology; the methodology provides for the mapping
of a source-level specification of a transformation tool to a DIANA- level
specification, which serves as an implementation guide for the tool. Finally,
a description is given of an application of the design methodology, a
preprocessor for the task monitoring system described by Helmbold and Luckham.
To conclude the paper, a summary of the advantages and suggested applications
of the design methodology is presented. The major advantage of the methodology
is that is allows the transformations performed by a tool to be implemented and
tested incrementally, making debugging less complex and implementaion more
efficient.
-------------------------------------------------------------------------------
CSL T.R. 85-270
A MODEL AND TEMPORAL PROOF SYSTEM FOR NETWORKS OF PROCESSES
by Van Nguyen, David Gries and Susan Owicki
February 1985 12 pages.....$2.40
A model and a sound and complete proof system for networks of processes in
which component processes communicate exclusively through messages is given.
The model, an extension of the trace model, can describe both synchronous and
asynchronous networks. The proof system uses temporal-logic assertions on
sequences of observations - a generalization of traces. The use of
observations (traces) makes the proof system simple, compositional and modular,
since internal details can be hidden. The expressive power of temporal logic
makes it possible to prove temporal properties (safety, liveness, precedence,
etc.) in the system. The proof system is language-independent and works for
both synchronous and asynchronous networks.
-------------------------------------------------------------------------------
CSL T.R. 85-271
TOPOLOGICAL DESIGN OF FIBER OPTICS LOCAL AREA NETWORKS WITH
APPLICATION TO EXPRESSNET
by M. Mehdi Nassehi, Fouad A. Tobagi and Michel E. Marhic
February 1985 78 pages.....$4.75
The use of fiber optics technology as a transmission medium in Local Area
Networks (LAN's) brings about primarily three benefits: high bandwidth,
immunity to electromagnetic interference, and light weight. But in
(multi-tapped) passive broadcast bus configurations, the characteristics of
certain fiber optics components that are needed, (such as reciprocity and
excess loss in optical taps,) place severe constraints which must be taken into
account in the topological design of such networks. These constraints manifest
themselves in the form of a limitation on the maximum number of stations that a
particular network configuration can support, given the components'
characteristics and special requirements introduced by the access scheme. In
this paper we provide a general and unified approach to the power budget
analysis and optimization problem, and apply the technique to the study of a
number of interesting high-performance LAN's, among others, Expressnet.
-------------------------------------------------------------------------------
CSL T.R. 85-272
BIBLIOGRAPHY OF THE COMPUTER SYSTEMS LABORATORY: 1968-1985
Edited by Naomi Schulman
March 1985 52 pages.....$5.00
This report lists, in chronological order, all technical reports and notes
published by the Computer Systems Laboratory (formerly named Digital Systems
Laboratory) of Stanford University, from l968 to date. Information regarding
availability, prices, and alternative sources is included.
-------------------------------------------------------------------------------
Several years have passed since our last announcement. We have decided to
include the abstracts of only 10 more recent reports, but have listed the
titles, authors, number of pages and prices of the other reports not previously
announced.
UNANNOUNCED REPORTS LIST
T.R. 83-239 SELF DESCRIBED PROGRAMMING ENVIRONMENTS -
AN APPLICATION OF A THEORY OF DESIGN TO PROGRAMMING SYSTEMS,
J. Phillips, 262 pages, $10.50
T.R. 83-240 ADAM - AN ADA-BASED LANGUAGE FOR MULTI-
PROCESSING, D.C. Luckham, F.W. von Henke, et al., 60 pages,
$4.10
T.R. 83-241 VERIFICATION OF HARDWARE DESIGN CORRECTNESS;
SYMBOLIC EXECUTION TECHNIQUES AND CRITERIA FOR CONSISTENCY,
W.E. Cory, 118 pages, $6.15
T.R. 83-242 FAULT SIMULATION IN ADLIB-SABLE, S. Ghosh &
W.M. vanCleemput, 92 pages, $5.20
T.R. 83-243 COMPARATIVE ANALYSIS OF COMPUTER ARCHITECTURES,
J.C. Huck, 96 pages, $5.35
T.R. 83-244 HIGH SPEED IMAGE RASTERIZATION USING A HIGHLY
PARALLEL SMART BULK MEMORY, S. Demetrescu, 38 pages, $3.40
T.R. 83-245 EDT; A SYNTAX-BASED PROGRAM EDITOR REFERENCE
MANUAL, R.S. Finlayson, 46 pages, $3.60
T.R. 83-246 THE DISTRIBUTED V KERNEL AND ITS PERFORMANCE
FOR DISKLESS WORK STATIONS, D.R. Cheriton & W. Zwaenepoel,
12 pages, $2.40
T.R. 83-247 MAINTAINING THE TIME IN A DISTRIBUTED SYSTEM,
K. Marzullo & S.S. Owicki, 13 pages, $2.45
T.R. 83-248 FABLE: A PROGRAMMING-LANGUAGE SOLUTION TO IC
PROCESS AUTOMATION PROBLEMS, H.L. Ossher & B.K. Reid,
36 pages, $3.25
T.R. 83-249 RUNTIME DETECTION AND DESCRIPTION OF DEADNESS
ERRORS IN ADA TASKING, D. Helmbold & D.C. Luckham, 62 pages,
$4.20
T.R. 83-250 DATA BUFFERS FOR EXECUTION ARCHITECTURES,
D. Alpert, 32 pages, $3.20
T.R. 83-251 GEM: A TOOL FOR CONCURRENCY SPECIFICATION AND
VERIFICATION, A.L. Lansky & S.S. Owicki, 16 pages, $2.55
T.R. 83-252 PERFORMANCE OF UNIDIRECTIONAL BROADCAST LOCAL
AREA NETWORKS: EXPRESS-NET AND FASNET, M. Fine & F.A. Tobagi,
86 pages, $5.00
T.R. 83-253 EVALUATION OF AN INTERPRETED ARCHITECTURE FOR
PASCAL ON A PERSONAL COMPUTER, C.L. Mitchell, 28 pages, $3.00
T.R. 83-254 A PORTABLE MACHINE-INDEPENDENT GLOBAL
OPTIMIZER - DESIGN AND MEASUREMENTS, F.C. Chow, 178 pages, $8.25
T.R. 83-255 CODE OPTIMIZATION OF PIPELINE CONSTRAINTS,
T. Gross, 112 pages, $5.90
T.R. 84-256 INSTRUCTION SELECTION BY ATTRIBUTED PARSING,
M.Ganapathi & C.N. Fischer, 32 pages, $3.80
T.R. 84-257 REVERSE SYNTHESIS COMPILATION FOR ARCHI-
TECTURAL RESEARCH, M. Ganapathi, J.L. Hennessy & V. Sarkar,
82 pages, $4.85
T.R. 84-258 A STRONGLY TYPED LANGUAGE FOR SPECIFYING PRO-
GRAMS, F.W. von Henke, 32 pages, $3.20
T.R. 84-259 ORGANIZATION AND VLSI IMPLEMENTATION OF MIPS,
S. Przybylski, T.R. Gross, et al., 40 pages, $3.40
T.R. 84-260 MEMORY HIERARCHIES FOR DIRECTLY EXECUTED LAN-
GUAGE MICROPROCESSORS, D. Alpert, 148 pages, $7.20
T.R. 84-261 ANNA: A LANGUAGE FOR ANNOTATING ADA PROGRAMS,
D.C. Luckham, et al., 144 pages, $7.05
T.R. 84-262 DEBUGGING ADA TASKING PROGRAMS, D. Helmbold &
D.C. Luckham, 19 pages, $2.65
-------------------------------------------------------------------------------
Publications
COMPUTER SYSTEMS LABORATORY
Stanford University
Stanford, CA 94305
ORDER FORM
To Order Reports: Print or type your name and address in the space provided.
If your address differs from our mailing label, please indicate that it is new
or corrected.
Check the report(s) you wish to purchase, whether hardcopy or microfiche. All
orders must be PREPAID. California residents must add 7% sales tax. 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 payable in dollars through a U.S. bank.
Please type or print your name and complete address:
Report # Hardcopy Microfiche Report # Hardcopy Microfiche
T.R. 239 $10.50 $4.00 T.R. 256 $3.80 $2.00
T.R. 240 $4.10 $2.00 T.R. 257 $4.85 $2.00
T.R. 241 $6.15 $3.00 T.R. 258 $3.20 $2.00
T.R. 242 $5.20 $2.00 T.R. 259 $3.40 $2.00
T.R. 243 $5.35 $2.00 T.R. 260 $7.20 $3.00
T.R. 244 $3.40 $2.00 T.R. 261 $7.05 $3.00
T.R. 245 $3.60 $2.00 T.R. 262 $2.65 $2.00
T.R. 246 $2.40 $2.00 T.R. 263 $2.90 $2.00
T.R. 247 $2.45 $2.00 T.R. 264 $2.50 $2.00
T.R. 248 $3.25 $2.00 T.R. 265 $2.80 $2.00
T.R. 249 $4.20 $2.00 T.R. 266 $6.40 $3.00
T.R. 250 $3.20 $2.00 T.R. 267 $3.50 $2.00
T.R. 251 $2.55 $2.00 T.R. 268 $2.55 $2.00
T.R. 252 $5.00 $2.00 T.R. 269 $2.75 $2.00
T.R. 253 $3.00 $2.00 T.R. 270 $2.40 $2.00
T.R. 254 $8.25 $3.00 T.R. 271 $4.75 $2.00
T.R. 255 $5.90 $3.00 T.R. 272 $5.00 $2.00
Subtotal
CA Residents only 7% Tax
Total
-------