leff@smu.CSNET.UUCP (02/20/87)
Naomi Schulman
Publications
COMPUTER SYSTEMS LABORATORY
STANFORD UNIVERSITY
Stanford, CA 94305
RECENT REPORTS & NOTES
LIST #7
JUNE, 1986
To order reports see end of this announcement.
ABSTRACTS
CSL TR-85-282
Partitioning of Function in a Distributed Graphics System
by William I. Nowicki
March 1985 146 pages.....$9.80
Although recent advances in graphics workstations promise much computing power
for the future needs of researchers, traditional approaches to software
organization waste much of this power. Most systems treat the workstation as
either a fixed-function terminal or a self-contained personal computer; these
roles have limitations that can be overcome by considering the workstation a
multi-function component of a distributed system. Traditional standard
graphics packages and object-oriented window systems offer important
functionality, but a third approach, virtual terminal management systems, is
more appropriate for a distributed operating system.
The Stanford Distributed Systems Group has implemented such a distributed
system for graphics workstations, organized as a collection of servers
providing services to clients. Major issues are how to partition functions
between the server and its clients, and physically partition the server. In
particular, the service that displays graphical objects is called the Virtual
Graphics Terminal Service (VGTS). The VGTS architecture is described, as well
as a prototype implementation.
This thesis discusses the trade-offs involved in partitioning of function in a
distributed graphics system. Performance is one important property traded for
advanced functionality or decreased cost. To provide adequate performance in a
distributed system, communication costs should be kept low, as well as the
frequency of the communication. By providing modeling as well as viewing
facilities, the VGTS reduces the communication required between applications
and the service.
Measurements verify that performance is insensitive to network bandwidth, but
depends heavily on CPU speed and protocol characteristics. Using structure
provides important speed improvements in some cases, but other basic factors
such as inner loop optimization and proper batching of requests make even
larger differences.
Finally, conclusions are drawn regarding the partitioning approaches taken in
the VGTS. The VGTS is suitable for a large class of applications that perform
graphics as an aid to user interface, and is portable to a wide range of
powerful workstations. Moreover, the VGTS can be used as a basis for further
research on many open questions in distributed systems.
-------------------------------------------------------------------------------
CSL-TR-85-283
Message-Passing on a Local Network
by Willy Zwaenepoel
October 1985 110 pages.....$8.00
This thesis focuses on understanding the cost of transparent interprocess
communication in a distributed system consisting of a set of machines connected
by a local network. Interprocess communication is transparent if processes can
communicate without regard to physical host boundaries. Transparent
interprocess communication is a very powerful tool because it allows us to view
the collection of different machines as a single, logically unified computer
system. We concentrate on the efficiency aspects of transparent interprocess
communication on a local network.
In order to obtain experimental evidence, a transparent message-passing
mechanism has been implemented as part of the distributed V kernel. This
message-passing mechanism has been used as the basis for various distributed
applications. In particular, it has been used extensively for providing
transparent file access from diskless workstations to a set of network-based
file servers. Based in part on experience gained from the implementation and
use of the distributed V kernel, this thesis presents four contributions:
1. An empirical evaluation of high-performance message passing on a
local network.
2. A queueing network model of file access from diskless workstations
over a local area network to a set of file servers.
3. An analysis of the protocol used to support the V interprocess
communication on a broadcast network.
4. The integration of the broadcast and multicast capabilities of local
area networks into message-based interprocess communication.
-------------------------------------------------------------------------------
CSL-TR-85-284
Taliesin: A Distributed Bulletin Board System
by Judy L. Edighoffer & Keith A. Lantz
September 1985 12 pages.....$3.10
This paper describes a computer bulletin board facility intended to support
replicated bulletin boards on a network that may frequently be in a state of
partition. The two major design issues covered are the choice of a name space
and a replication algorithm. The impact of the name space on communication
costs is explained. A special purpose replication algorithm providing high
availability and response despite network partition is introduced.
-------------------------------------------------------------------------------
CSL-TR-85-285
Architectural Elements for Bitmap Graphics
by Cary D. Kornfeld
April 1985 133 pages.....$9.15
This dissertation examines two closely related aspects of bitmap
graphics-- methods for manipulating bitmap images and techniques for displaying
these images. First, it looks at the implementation of three primitive
operations useful when manipulating images - Mirror, Rotate and Translate
(BitBlt). When implemented on conventional bitmap systems these fundamental
operations tend to be awkward (inefficient) to implement, often requiring
extensive memory and processor activity.Several new alternative architectures
for bitmap graphic systems are explored. Two new architectural elements that
significantly improve system performance are defined, designed and implemented
in VLSI. The first, a RasterOP unit, combines four bitmap images under
arbitrary merging operations at video data rates. The second element, called
an Image Prism, generates orthogonal image transformations on bitmap images
within the memory system without requiring processor interaction. As a result,
these fundamental operations can be performed several hundred times faster than
before. Fast VLSI implementations of each are described and their actual
behavior and performance is reviewed.
The second thrust of this research focuses on the design and development of a
research display device. Three major architectural components of traditional
CRT-based bitmap display systems - frame buffer, display controller and display
device - are combined and integrated into a single, exceptionally thin, flat
panel display device of which several working prototypes have been built. The
entire display device is constructed using conventional microelectronic IC
fabrication processing technology so that all required electronics are
integrated onto a single silicon wafer which is then coated with a layer of
electrophoretic display material. A number of interesting research topics are
explored including new techniques for controlling display material at low
voltage and a novel new approach to defect tolerant wafer scale VLSI design.
The behavior of the fabricated display devices is reviewed and analyzed.
-------------------------------------------------------------------------------
CSL-TR-85-286
Towards a Universal Directory Service
by K.A. Lantz, J.L. Edighoffer & B.L. Hitson
August 1985 21 pages.....$3.55
Directory services and name servers have been discussed and implemented for a
number of distributed systems. Most have been tightly interwoven with the
particular distributed systems of which they are a part; a few are more general
in nature. In this paper we survey recent work in this area and discuss the
advantages and disadvantages of a number of approaches. From this, we are able
to extract some fundamental requirements of a naming system capable of handling
a wide variety of object types in a heterogeneous environment. We outline how
these requirements can be met in a universal directory service.
-------------------------------------------------------------------------------
CSL-TR-85-287
An Empirical Study of Distributed Application Performance
by K.A. Lantz, W.I. Nowicki, & M.M. Theimer
October 1985 24 pages.....$3.70
A major reason for the rarity of distributed applications, despite the
proliferation of networks, is the sensitivity of their performance to various
aspects of the network environment. We demonstrate that distributed
applications can run faster than local ones, using common hardware. We also
show that the primary factors affecting performance are, in approximate order
of importance: speed of the user's workstation, speed of the remote host (if
any), and the high-level (above the transport level) protocols used. In
particular, the use of batching, pipelining, and structure in high-level
protocols reduces the degradation often experienced between different bandwidth
networks. Less significant, but still noticeable improvements result from
proper design and implementation of the underlying transport protocols.
Ultimately, with proper application of these techniques, network bandwidth is
rendered virtually insignificant.
-------------------------------------------------------------------------------
CSL-TR-85-288
Preemptable Remote Execution Facilities for the V-System
by M.M. Theimer, K.A. Lantz & D.R. Cheriton
September 1985 17 pages.....$3.35
A remote execution facility allows a user of a workstation-based distributed
system to offload programs onto idle workstations, thereby providing the user
with access to computational resources beyond that provided by his personal
workstation. In this paper, we describe the design and performance of the
remote execution facility in the V distributed system, as well as several
implementation issues of interest. In particular, we focus on network
transparency of the execution environment, preemption and migration of remotely
executed programs, and avoidance of residual dependencies on the original host.
We argue that preemptable remote execution allows idle workstations to be used
as a ``pool of processors'' without interfering with use by their owners and
without significant overhead for the normal execution of programs. In general,
we conclude that the cost of providing preemption is modest compared to
providing a similar amount of computation service by dedicated ``computation
engines''.
-------------------------------------------------------------------------------
CSL-86-289
MIPS-X Instruction Set and Programmer's Manual
Paul Chow
May 1986 98 pages.....$7.40
MIPS-X is a high performance second generation reduced instruction set
microprocessor. This document describes the visible architecture of the
machine, the basic timing of the instructions, and the instruction set.
-------------------------------------------------------------------------------
CSL-86-290
High-Resolution Printing Without a Frame Buffer
Carolyn F. Bell
December 1985 125 pages.....$8.75
Laser printers have become popular because of the high quality of their output.
This thesis analyzes the characteristics of high-quality text as resolution is
varied, introduces a new algorithm for scan conversion, and proposes a printer
controller using edge descriptions. The resulting method of printing
represents characters with edges, which are simple to generate and manipulate,
provides an algorithm which uses the slope of the edge to key the scan
conversion, and uses a hardware data structure which describes an image with
edges rather than pixels. The propsed controller is not as general as a
controller using a frame buffer, since a page too complex for it to print can
always be specified. However, for a page containing 4000 characters and
printed at 2000 pixels per inch, the edge buffer controller requires about
one-fortieth the memory, one-tenth the memory accesses, and one-twentieth the
running time of a frame buffer controller.
-------------------------------------------------------------------------------
CSL T.R. 86-291
Lisp and Prolog Memory Performance
Evan Tick
January 1986 37 pages.....$4.35
This report presents a comparison between a Lisp and Prolog architecture based
on memory performance. Four Lisp programs were translated into Common Lisp and
Prolog abstract machine instruction sets. The translated programs were
emulated and memory reference counts collected. Memory usage statistics
indicate how the two languages do fundamental computations different ways with
varying efficiency. Additional measurements of production systems running on a
conventional host are presented.
-------------------------------------------------------------------------------
NOTES
CSL-TN-85-283
PareseGen: A LALR(1 Parser Generator)
by Rob Chang
November 1985 3l pages.....$4.05
ParseGen is a LALR(1) Parser Generator. Given a context free grammar, ParseGen
will generate an Ada package and a parsing table. This information can then be
used by a parser skeleton - a shift-reduce parser - in order to parse input and
produce an associated abstract syntax tree.
Both ParseGen and the parser skeleton are written in Ada and are able to
process large languages. ParseGen has successfully processed language grammars
for Ada and extensions of Ada; the latter exceeds three hundred productions.
-------------------------------------------------------------------------------
CSL-TN-86-286
Microprogram Control of a Prolog Machine
by Kiyomi Koyama
January 1986 30 pages.....$4.00
A Prolog machine design and its control are described. The machine features
two-stage pipelining, a triple bus interconnection data path and support for
concurrent control of micro-operations. The objective of this design is to
improve execution of a Prolog processor by simultaneously performing multiple
micro-operations. Capabilities of concurrent operation support are described
in detail and demonstrated using some example Prolog functions. Two-stage
pipeline technique as applied to non-deterministic control of Prolog program
execution will be presented.
-------------------------------------------------------------------------------
Publications
COMPUTER SYSTEMS LABORATORY
Stanford University
Stanford, CA 94305
415-723-1430
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 282 $9.80 $3.00 TR 287 $3.70 $2.00
TR 283 $8.00 $3.00 TR 288 $3.35 $2.00
TR 284 $3.10 $2.00 TR 289 $7.40 $2.00
TR 285 $9.15 $3.00 TR 290 $8.75 $3.00
TR 286 $3.55 $2.00 TR 291 $4.35 $2.00
TN 283 $4.05 $2.00 TN 286 $4.00 $2.00
Subtotal __________
Your Local County CA tax __________
Total __________
-------