COMMENT ⊗   VALID 00015 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.DEVICE XGP 
C00003 00003	.once center
C00005 00004	STAN-CS-78-700
C00010 00005	STAN-CS-79-701
C00016 00006	STAN-CS-78-702
C00018 00007	STAN-CS-79-703
C00020 00008	STAN-CS-79-704
C00021 00009	STAN-CS-79-705
C00027 00010	STAN-CS-79-706
C00028 00011	STAN-CS-79-707
C00030 00012	STAN-CS-79-708
C00032 00013	STAN-CS-78-709
C00034 00014	.next page <<systems optimization lab>>
C00046 00015	.next page <<CSL>>
C00060 ENDMK
C⊗;
.DEVICE XGP; 
.
.turn on "↔" for "→"
.turn on "%,π,α,#,&,∂,↑,↓,[,]"
.turn on "∩" for "↑"
.turn on "∪" for "↓"
.
.font 1 "nonm";
.font 2 "baxm30";
.font 3 "math30";
.font 4 "fix25";
.font 5 "grkl30";
.
.sides←1;
.require "twocol.pub[sub,sys]" source file;
.
.SELECT 1
.at "@" ⊂"####"⊃
.at "|cd" ⊂"%3α*%1"⊃
.at "≤" ⊂"%4α≤%1"⊃
.
.at "!!" txt ";"	⊂
.("txt"[1]&"∩["&"txt"[2]&"]&∪[ "&"txt"[3]&"]");
.  ⊃
.
.PLACE TEXT;
.
.next page
.once center
%1MOST RECENT CS REPORTS - APRIL 1979

@Listed below are abstracts of the most recent reports published by the
Computer Science Department of Stanford University.

@TO REQUEST REPORTS:  Check the appropriate places on the enclosed order
form, and return the entire order form page (including mailing label) by
April 27, 1979.  In many cases we can print only a limited number of copies,
and requests will be filled on a first come, first serve basis.  If the code
(FREE) is printed on your mailing label, you will not be charged for hardcopy.
This exemption from payment is limited primarily to libraries.  (The costs
shown include all applicable sales taxes.  PLEASE SEND NO MONEY NOW, WAIT UNTIL 
YOU GET AN INVOICE.)

@ALTERNATIVELY:  Copies of most Stanford CS Reports may be obtained by writing
(about 2 months after MOST RECENT CS REPORTS listing) to NATIONAL TECHNICAL
INFORMATION SERVICE, 5285 Port Royal Road, Springfield, Virginia 22161.
Stanford Ph.D. theses are available from UNIVERSITY MICROFILMS, 300 North
Zeeb Road, Ann Arbor, Michigan 48106.
.begin nofill
--↔--
.end
STAN-CS-78-700
.once preface 0
@A FRAMEWORK FOR PROBLEM SOLVING IN A DISTRIBUTED PROCESSING 
ENVIRONMENT

Author:  Reid Garfield Smith↔(Thesis)

@Abstract:  The concept of %2Distributed Problem Solving%1, or the cooperative
solution of problems by a decentralized and loosely-coupled collection of
knowledge-sources that operates in a distributed processor architecture is
presented.  Such architectures offer high-speed reliable computation at low
cost and are an effective way to utilize the new LSI processors and the developments
of the recent synthesis of computer and communications technology.

@A conceptual framework called the %2Contract Net%1 framework that specifies
communications, control, and knowledge organization has been developed.
Task distribution is viewed as an interactive process, a %2discussion%1
carred on between a node with a task to be executed and a group of nodes
that may be able to execute the task.  This is the origin of the contract
metaphor for control, where task distribution corresponds to contract
negotiation.

@The types of knowledge used in such a problem solver are discussed,
together with the ways that the knowledge is indexed with an individual
node and distributed among the collection of nodes.  The use of two
primary types of knowledge (referred to as %2Task-Centered%1 and
%2Knowledge-Source Centered%1) is shown.

@We illustrate the kinds of information that must be passed between nodes
in the distributed processor in order to carry out task and data
distribution.  We suggest that a common internode language is required and
that the task-specific %2expertise%1 required by a processor node can be
obtained by internode transfer of procedures and data.

@The use of the contract net framework is demonstrated with two implemented
examples:  search in the context of the N Queens problem and area
surveillance by a Distributed Sensing System.  Consideration is also given
to the implementation of a number of familiar Artificial Intelligence
problem solvers.

@Features of the framework applicable to problem solving in general are abstracted
from the results of this preliminary study.  Comparisons with PLANNER, HEARSAY-II,
and PUP6 are used to demonstrate that %2negotiation%1, the two-way transfer of
information combined with mutual selection prior to invocation, is a natural
extension to the control mechanisms used in earlier problem-solving systems.
.begin nofill

No. of pages:  150
Cost:  $ 5.90
--↔--
.end
STAN-CS-79-701
.once preface 0
@MONITORING SYSTEM BEHAVIOR IN A COMPLEX COMPUTATIONAL 
ENVIRONMENT

Author:  Mitch L Model↔(Thesis)

@Abstract:  Complex programming environments such as the representation systems
constructed in Artificial Intelligence research present new kinds of difficulties
for their environment, the traditional tools and techniques available for this
task are inadequate.  Not only do traditional tools address state and process
elements at too low a conceptual level, but an Artificial Intelligence system
typically imposes its own data and control structures on top of those of its
implementation language, thereby evading the reach of traditional program-level
debugging tools.  This work is directed at the development of appropriate
monitoring tools for complex systems, in particular, the representation systems
of Artificial Intelligence research.

@The first half of this work provides the foundation for the design approach put
forth and demonstrated in the second.  Certain facts concerning limitations on
human information processing abilities which formed the background for much of
the research are introduced.  The nature of computer programs is discussed, and
a concept of %2computational behavior%1 is defined.  A thematic survey of
traditional debugging tools is presented, followed by a summary of recent work.
Observation of program behavior (%2monitoring%1) is shown to be the main function
of most debugging tools and techniques.  Concluding this first part is an analysis
of the particular difficulties involved in monitoring the behavior of programs
in large and complex AI systems.

@The second half presents an approach to the design of monitoring facilities
for complex systems.  The need for system-level tools similar to the ones
traditionally available is indicated.  A new concept called "meta-monitoring"
replaces traditional dumps and traces with selective reporting of high-level
information %2about%1 computations.  The importance of the visually-oriented
analogical presentation of high-level information and the need to take into
account differences between states and active processes are stressed.  A
generalized method for generating descriptions of system activity is developed.
This method is based on a theoretical schematization of the fundamental structures
and operations of computational systems and is easily instantiated for any
particular AI system.  Some specific display-based monitoring tools and
techniques which were implemented for this work are exhibited.  Several of the
experimental monitoring facilities which were constructed in accordance with
the principles of the proposed approach are described and their application to
existing Artificial Intelligence Systems illustrated.  While much of the research
was performed in the context of the KRL-1 system developed at Xerox Palo Alto
Research Center, the general applicability of the theory and techniques of the
present work is demonstrated by one of thes facilities, which acts as a monitor
for MYCIN, a medical diagnosis system developed at Stanford University that
embodies knowledge in the form of production rules.
.begin nofill

No. of pages:  189
Available in microfiche only.
--↔--
.end
STAN-CS-78-702
.once preface 0
@AN O(n|cdIlog↑2I) MAXIMUM-FLOW ALGORITHM

Author:  Yossi Shiloach

@Abstract:  In this paper we present an algorithm to find a maximum flow in a
network which has n vertices and m edges in time of O(n|cdIlog↑2I), where
I = m+n , the input size (up to a constant factor).  This result improves
the previous upper bound of Z. Galil [G] which has an O(I∩[7/3]) worst-case
performance.

@The algorithm is basically an implementation of Dinic's algorithm in a
data-structure which enables us to store sections of paths that have already
been traversed and also cut and paste such sections, find their bottlenecks
and update the residual capacities of their edges in logarithmic time.
.begin nofill

No. of pages:  33
Cost:  $ 2.65
--↔--
.end
STAN-CS-79-703
.once preface 0
@A POLYNOMIAL TIME ALGORITHM FOR SOLVING SYSTEMS OF LINEAR 
INEQUALITIES WITH TWO VARIABLES PER INEQUALITY

Author:  Bengt Aspval & Yossi Shiloach

@Abstract:  We present a constructive algorithm for solving systems of linear
inequalities (LI) with at most two variables per inequality.  The algorithm is
polynomial in the size of the input.  The LI problem is of importance in
complexity theory since it is polynomial time equivalent to linear programming.
The subclass of LI treated in this paper is also of practical interest in
mechanical verification systems, and we believe that the ideas presented can be
extended to the general linear inequalities problem.
.begin nofill

No. of pages:  25
Cost:  $ 2.40
--↔--
.end
STAN-CS-79-704
.once preface 0
@A SURVEY OF THE STATE OF SOFTWARE FOR PARTIAL DIFFERENTIAL 
EQUATIONS 

Author:  Roland A. Sweet

@Abstract:  This paper surveys the state of general purpose software for the
solution of partial differential equations.  A discussion of the purported
capabilities of twenty-one programs is presented.  No testing of the routines
is performed.
.begin nofill

No. of pages:  31
Cost:  $ 2.60
--↔--
.end
STAN-CS-79-705
.once preface 0
@GENERALIZED VORONOI DIAGRAMS AND GEOMETRIC SEARCHING

Author:  Robert Lewis (Scot) Drysdale, III↔(Thesis)

@Abstract:  A Voronoi diagram is a partitioning of the plane into n polygonal
regions, one region associated with each of n given points.  The region associated
with point p consists of all points in the plane closer to p than to any of the
other n-1 given points.  Michael Shamos developed a divide-and-conquer algorithm
which computes the diagram in O(n log n) time.  He showed that the all-nearest-neighbors
problem, and other seemingly unrelated problems can all be solved in time which
is optimal to within a constant factor by first computing the Voronoi diagram.
These kinds of problems arise in wire layout, facilities location, cutting-stock
problems, geometric optimization problems, clustering problems, and contouring
problems.

@A natural question is, "Can the Voronoi diagram be generalized to other shapes
and to other metrics on R↑2?"  Ignoring the 200-mile limit, the territorial
waters of a country are precisely its Voronoi diagram.  Therefore the question
is of interest in map-making.  Lee and Wong studied the Voronoi diagram for
points under the L↓1 and L%4↓∞ %1metrics and its applications to two-dimensional
memory storage systems.  Shamos posed the problem of quickly computing minimum
spanning trees for circles and line segments.  A fast procedure for computing
the Voronoi diagram for circles and line segments would solve this problem.
Many of the applications mentioned above have analogs where the objects under
consideration are best represented by geometric shapes other than points (e.g.,
conductors or components in wire layout problems may be rectangles, circles, or
line segments).  Applications also arise in computer graphics.

@This paper presents a divide-and-conquer method for computing Voronoi diagrams
for a wide variety of geometric shapes (including line segments, circles, and
polygons) in the Euclidean plane in O(n c∩[%3\%1log n]) %2basic steps%1, where
the %2basic steps%1 include such operations as finding the locus of points
equidistant from two objects, find the intersection of two such loci, and
finding the lines of support between two objects.  Part of this algorithm is
a procedure for computing the convex hull of a set of n convex objects in
O(n log n) basic steps, which is interesting in its own right.  It is shown
that these methods work for a wide variety of metrics on R↑2, including the
L↓p metrics for 1#<#p#<#%4∞%1.

@There is a strong temptation when working with geometric algorithms to say,
"It's obvious!  Look at the diagram!"  Geometric intuitions are vital, but
are occasionally wrong.  There important facts are stated as lemmas and proved.

@An O(n c∩[%3\%1log n])-time algorithm may be worse than asymptotically slower
algorithms for %2practical sized%1 problems.  For this reason this paper presents
methods for efficiently implementing the algorithm and includes a complete
implementation of the algorithm for line segments as an Appendix.  The results
of these tests comparing running times for the nearest-neighbor problem
solved directly and by using the Voronoi diagram for various sized data sets
seem to indicate that there are applications where the algorithm would be
valuable.  For some types of input it was faster to use the Voronoi diagram
whenever the number of objects was greater than 100.
.begin nofill

No. of pages:  196
Available in microfiche only.
--↔--
.end
STAN-CS-79-706
.once preface 0
@GRAPH 2-ISOMORPHISM IS NP-COMPLETE

Author:  F. Francis Yao

@Abstract:  Two graphs G and G' are said to be k-isomorphic if their edge sets
can be partitioned into E(G) = E↓1 %4α∪%1 E↓2 %4α∪%1...%4α∪%1 E↓k and 
E(G') = !!E'1; %4α∪%1 !!E'2; %4α∪%1...%4α∪%1 !!E'k; 
such that as graphs, E↓i and
!!E'i; are isomorphic for 1#≤#i#≤#k .  In this note we show that it is
NP-complete to decide whether two graphs are 2-isomorphic.
.begin nofill

No. of pages:  12
Cost:  $ 2.05
--↔--
.end
STAN-CS-79-707
.once preface 0
@A PROGRAMMING AND PROBLEM-SOLVING SEMINAR

Authors:  Chris Van Wyk & Donald E. Knuth

@Abstract:  This report contains edited transcripts of the discussions held
in Stanford's course CS 204, Problem Seminar, during autumn quarter 1978.  Since
the topics span a large range of ideas in computer science, and since most of the
important research paradigms and programming paradigms came up during the
discussions, these notes may be of interest to graduate students of computer
science at other universities, as well as to their professors and to professional
people in the "real world."
.begin nofill

No. of pages:  83
Cost:  $ 4.05
--↔--
.end
STAN-CS-79-708
.once preface 0
@AN ANALYSIS OF A MEMORY ALLOCATION SCHEME FOR IMPLEMENTING STACKS

Author:  Andrew C. Yao

@Abstract:  Consider the implementation of two stacks by letting them grow 
towards each other in a table of size m.  Suppose a random sequence of
%2insertions%1 and %2deletions%1 are executed, with each instruction having
a fixed probability p#(0#<#p#<#1/2) to be a deletion.  Let A↓p(m) denote
the expected value of 
maxα{x,yα},
where x and y are the stack heights when
the table first becomes full.  We shall prove that, as m#%2→#%4∞%1,
A↓p(m) = m/2 + %3\%1m/(2%5p%1(1-2p)) + 0((log m)/%3\%1m).  This gives a
solution to an open problem in Knuth [%2The Art of Computer Programming%1
Vol. 1, Exercise 2.2.2-13].
.begin nofill

No. of pages:  18
Cost:  $ 2.20
--↔--
.end
STAN-CS-78-709
.once preface 0
@DESIGN AND ANALYSIS OF A DATA STRUCTURE FOR REPRESENTING SORTED
LISTS

Authors:  Mark R. Brown & Robert E. Tarjan

@Abstract:  In this paper we explore the use of 2-3 trees to represent sorted
lists.  We analyze the worst-case cost of sequences of insertions and deletions
in 2-3 trees under each of the following three assumptions:  (i) only insertions
are performed; (ii) only deletions are performed; (iii) deletions occure only at
the small end of the list and insertions occur only away from the small end.
Our analysis leads to a data structure for representing sorted lists when the 
access pattern exhibits a (perhaps time-varying) locality of reference.  This
structure has many of the properties of the representation proposed by
Guibas, McCreight, Plass, and Roberts [4], but it is substantially simpler
and may be practical for lists of moderate size.
.begin nofill

No. of pages:  50
Cost:  $ 3.10
--↔--
.end
.next page <<systems optimization lab>>
.once center
SYSTEMS OPTIMIZATION LABORATORY

@The following reports are available from the Systems Optimization Lab.
Further information on them can be obtained from:
Gail L. Stein, Systems Optimization 
Laboratory, Department of Operations Research, Stanford University, Stanford, 
California 94305 U.S.A.
.begin nofill
--↔--
.end
SOL 78-8
.once preface 0
@FORTRAN SUBROUTINES TO SOLVE THE LINEAR LEAST-SQUARES PROBLEM AND 
COMPUTE THE COMPLETE ORTHOGONAL FACTORIZATION

Authors:  Margaret H. Wright & Steven C. Glassman

@Abstract:  This report describes the computational procedures involved in:
(i) solution of linear least-squares problems (including systems of non-singular,
orer- and under-determined linear equations); (ii) formation of the complete
orthogonal factorization of a general real matrix.  Some aspects of implementation
and the estimation of rank are discussed.  Full documentation (including source
code) is given for a modular set of Fortran subroutines to solve problems (i)
and (ii), and several related problems.
.begin nofill
--↔--
.end
SOL 78-23
.once preface 0
@PROJECTED LAGRANGIAN METHODS BASED ON THE TRAJECTORIES OF PENALTY AND 
BARRIER FUNCTIONS

Authors:   Walter Murray & Margaret H. Wright

@Abstract:  This report contains a complete derivation and description of two
algorithms for nonlinearly constrained optimization which are based on
properties of  the solution trajectory of the quadratic penalty function and
the logarithmic barrier function.  The methods utilize the penalty and barrier
functions only as merit functions, and do not generate iterates by solving a
sequence of ill-conditioned problems.  The search direction is the solution of
a simple, well-posed quadratic program (QP), where the quadratic objective
function is an approximation to the Lagrangian function; the steplength is
based on a sufficient decrease in a penalty or barrier function, to ensure
progress toward the solution.

@The penalty trajectory algorithm was first proposed by Murray in 1969; the
barrier trajectory algorithm, which retains feasibility throughout, was
given by Wright in 1976.  Here we give a unified presentation of both algorithms,
and indicate their relationship to other QP-based methods.  Full details of
implementation are included, as well as numerical results that display the
success of the methods on non-trivial problems.
.begin nofill
--↔--
.end
SOL 78-27
.once preface 0
@ERROR PROPAGATION AND SOLUTION RECONSTRUCTION IN NESTED DECOMPOSITION

Author:  Larry Nazareth

@Abstract:  We study some of the numerical properties of the nested decomposition
algorithm of Ho and Manne.  In particular we seek to show how well developed
theory in the area of computational linear algebra, due primarily to J. H.
Wilkinson, carries over to linear programming and yields useful insight into
the behavior of algorithms in this area.
.begin nofill
--↔--
.end
SOL 78-28
.once preface 0
@MODULES TO AID THE IMPLEMENTATION OF LP ALGORITHMS

Author:  Larry Nazareth

@Abstract:  Implementing large scale LP algorithms is a difficult, laborious
and often poorly rewarded task.  This is particularly true of algorithms which
exploit the structure of the LP matrix.  For this reason many algorithms have
been proposed in the literature, but few have been turned into good computer
codes.  Very little is known about the relative performance of different
algorithms.  In this paper we discuss some of the suggestions that have been
made for alleviating this problem and describe an approach based upon a carefully
defined collection of subroutines which are designed to aid the task of
implementing and comparing LP algorithms.  These subroutines or modules
may be regarded as the 'primitives' of a language for implementing experimental
LP algorithms, particularly algorithms which exploit matrix structure.  A set of
such modules is described.  These have been implemented in FORTRAN, and user
documentation is available.
.begin nofill
--↔--
.end
SOL 78-29
.once preface 0
@A STUDY OF CONJUGAT GRADIENT METHODS

Authors:  L. Nazareth & J. Nocedal

@Abstract:  We prove a number of new properties of algorithms of the Conjugate
Gradient type, paying particular attention to methods which utilize variable
metric information in determining the conjugate gradient search directions.  We
attempt to a comprehensive discussion of the conjugate gradient methods, and
present each algorithm within the context of other existing algorithms, an
approach which provides fresh insights and some new algorithms.
.begin nofill
--↔--
.end
SOL 78-30
.once preface 0
@DUALLY EQUIVALENT DECOMPOSITION ALGORITHMS WITH APPLICATION TO SOLVING
STAIRCASE STRUCTURES

Author:  Larry Nazareth

@Abstract:  We briefly go over the well known dual relationship between 
Dantzig-Wolfe Decomposition and Benders Decomposition, in order to develop
suitable e notation, and then elaborate upon the dual relationship between
nested versions of Dantzig-Wolfe and Benders Decomposition.  Next we develop
a new pair of dually related decompositions termed symmetric Dantzig-Wolfe and
symmetric Benders Decomposition.  Finally we discuss the advantages and
disadvantages of applying nested and symmetric decompositions to structured
LP problems, in particular to staircase structures.
.begin nofill
--↔--
.end
SOL 78-31
.once preface 0
@A LAND MANAGEMENT MODEL USING DANTZIG-WOLFE DECOMPOSITION

Author:  Larry Nazareth

@Abstract:  This paper deals with a mathematical model designed to provide
guidelines for managing a land resource over an extended period of time.

@We develop a framework which permits sequences of management decisions to be
conveniently formulated, and their associated costs and benefits specified.
This takes the form of a network.  Each path in the network represents a
possible decision sequence.  We study how to select suitable decision sequences
and what proportion of the resource to manage with each selected sequence, so
as to optimize some specified objective and meet the constraints imposed on
management of the resource.  An L.P. model is formulated.  The solutio strategy
decomposes the L.P. matrix using Dantzig-Wolfe decomposition and solves the
subproblems efficiently by dynamic programming or a network flow algorithm.
Computational aspects are discussed and the concepts and procedures are
illustrated in the Appendix, for forest management.
.begin nofill
--↔--
.end
SOL 78-32
.once preface 0
@SOFTWARE FOR OPTIMIZATION

Author:  Larry Nazareth

@Abstract:  Our aim in this paper is to provide the reader with:

@a)  Some feel for what quality software entails.

@b)  An overview of various aspects of optimization software.

@c)  Information on solution techniques and available software in the form
of a decision tree.

@d)  An extensive bibliography so that the reader can further pursue specific
topics of interest.

@We concentrate upon linear programming, non-linear unconstrained optimization
and related areas, and non-linear programming.

@This paper is intended to supplement an earlier oral presentation at the Texas
Conferenct on Mathematical Software entitled "State of Software for
Optimization".
.begin nofill
--↔--
.end
.next page <<CSL>>
.once center
CSL REPORTS

@The following reports are available from the Computer Systems Lab.  Further
information on them can be obtained from:
Naomi Schulman, Computer Science Laboratory, ERL-234,
Stanford University, Stanford, California 94305 U.S.A.
.begin nofill
--↔--
.end
CSL TR-156
.once preface 0
@OPTIMAL PROGRAM CONTROL STRUCTURES BASED ON THE CONCEPT OF DECISION ENTROPY

Author:  Ruby Bei-Loh Lee

@Abstract:  The ability to make decisions dynamically during program execution
is a very powerful and valuable tool.  Unfortunately, it also causes severe
performance degradations in high-speed computer organizations which use parallel,
pipelined or lookahead techniques to speed up program execution.  An optimal
control structure is one where the average number of decisions to be made during
program execution is minimal among all control structures for the program.
Since decisions are usually represented by conditional branch instructions,
finding an optimal control structure is equivalent to minimizing the expected
number of conditional branch insturctions to be encountered per program execution.

@By decision entropy, we mean a quantitive characterization of the uncertainty
in the instruction stream due to dynamic decisions imbedded in the program.  We
define this concept of decision entropy in the Shannon information-theoretic
sense.  We show that a program's intrinsic decision entropy is an absolute lower
bound on the expeced number of decisions, or conditional brance instructions, per
program execution.  We show that this lower bound is achieved if each decision 
has maximum uncertainty.  We also indicate how optimal control structures may
be constructed.
.begin nofill
--↔--
.end
CSL TR-158
.once preface 0
@PERFORMANCE CHARACTERIZATION OF PARALLEL COMPUTATIONS

Author:  Ruby Bei-Loh Lee

@Abstract:  This paper defines and interprets quantitative measure by which
we may characterise the absolute and relative performance of a parallel
computation, compared with an equivalent serial computation.  The absolute
performance measure are the Parallelism Index, PI(P), the Utilization, U(P),
and the maximum Quality, Q(P).  The corresponding relative performance measures
are the Speedup, S(P,1), the Efficiency, E(P,1), and the Quality, Q(P,1).  We
show how the corresponding absolute and relative performance measures are related
via the Redundancy measure, R(P,1).  We also examine the range of permissible
values for each performance measure.

@Ideally, we would like to compare an optimal parallel computation with an optimal
equivalent serial computation, in order to determine the prformance improvements
due solely to parallel versus serial processing.  Toward this end, we define optimal
parallel and serial computations, and show how such optimality may be approximated
in practice.

@In order to facilitate the calculation of the above performance measures, we
show how the complexity of modelling an arbitrary parallel computation may be
reduced substantially to two simple canonical forms, which we denote the
computations's Parallelism Profile and TOP-form.

@Finally, we show how all the canonical forms and performance measures may be
generalized from one computation to a set of computations, to arrive at
aggregate canonical and performance descriptions.
.begin nofill
--↔--
.end
CSL TR-159
.once preface 0
@SPECIFICATION AND VERIFICATION OF A NETWORK MAIL SYSTEM

Author:  Susan S. Owicki

@Abstract:  Techniques for describing and verifying modular systems are
issustrated using a simple network mail problem.  The design is presented in a 
top-down style.  At each level of refinement, the specifications of the higher
level are verified from the specifications of lower level components.
.begin nofill
--↔--
.end
CSL TR-160↔(STAN-CS-79-714)
.once preface 0
@PCFORT:  A FORTRAN-TO-PCODE TRANSLATOR

Authors:  Fernando Castaneda, Frederick Chow, Peter Nye, Dan Sleator & Gio Wiederhold

@Abstract:  PCFORT is a compiler for the FORTRAN language designed to fit as a
building block into a PASCAL oriented environment.  It forms part of the
programming systems being developed for the S-1 multiprocessor.  It is written
in PASCAL, and generates P-code, an intermediate language used by transportable
PASCAL compilers to represent the program in a simple form.  P-code is either
compiled or interpreted depending upon the objectives of the programming system.

@A PASCAL written FORTRAN compiler provides a bridge between the FORTRAN and
PASCAL communities.  The implementation allows PASCAL and FORTRAN generated
code to be combined into one program.  The FORTRAN language supported here is
FOTRAN to the full 1966 standard, extended with those features commonly expected
by available large scientific programs.
.begin nofill
--↔--
.end
CSL TR-161↔(STAN-CS-79-715)
.once preface 0
@S-1 ARCHITECTURE MANUAL

Authors:  Brent T. Hailpern & Bruce L. Hitson

@Abstract:  This manual provides a complete description of the instruction-set
architectures of the S-1 Uniprocessor (Mark IIA), exclusive of vector operations.
It is assumed that the reader has a general knowledge of computer architecture.
The manual was designed to be both a detailed introduction to the S-1 and an
architecture reference manual.  Also included are user manuals for the FASM
.begin nofill
--↔--
.end
CSL TN-145
.once preface 0
@DESIGN FOR MAINTAINABILITY AND TESTABILITY

Author:  Edward J. McClukey

@Abstract:  This paper presents a survey of various techniques that have been
proposed for design of digital systems that can be easily tested or maintained
or both.  An extensive bibliography is included.
.begin nofill
--↔--
.end
CSL TN-146
.once preface 0
@PERFORMANCE COMPARISON OF UPDATE ALGORITHMS FOR DISTRIBUTED DATABASES

Author:  Hector Garcia-Molina

@Abstract:  A centralized locking update algorithm for distributed databases
was presented and its performance analyzed in [1].  (The algorithm was studied
in the case of completely duplicated databases in a no failure update only
environment.)  In that algorithm, an update sequence number was added to all
lock grant and perfomr update messages in order to properly sequence conflicting
updates.  Even though it was not mentioned in that report, each lock grant and
perform update message issued must contain additional information because otherwise
the updates are performed with reduced parallelism.

@This report will describe this additional information and why it is needed.  The
effect on prformance of only including a fraction of this information in the
messages is then studied through simulations.  Finally, several implementation
alternatives are suggested for coding and handling the additional information
in the messages.
.begin nofill
--↔--
.end
CSL TN-147   
.once preface 0
@S-1 INTERMEDIATE LOADER FORMAT AND S-1 LINKER

Authors:  Arthur Keller & Gio Wiederhold

@Abstract:  The loader format for the S-1 and the Linker for the S-1  using
this  format  are  described.   The  loader  format  was  designed  to  be
transportable, easily  human  readable,  and editable  on  available  text
editors.  For  these  reasons,  it  only uses  a  minimal  subset  of  the
printable ASCII character set.  It is  used for both the Linker input  and
output, so that linking can proceed in stages.

@The Linker is part of the S-1 programming system.  It was designed
to support  linking modules  from compilers  of different  languages.   In
order to make it transportable, it was written in PASCAL.  The output  can
be relocatable or absolute, but it is usually absolute.
.begin nofill
--↔--
.end
CSL TN-148    
.once preface 0
@P-CODE INTERMEDIATE ASSEMBLER LANGUAGE  

Authors:  Erick J. Gilbert & David W. Wall

@Abstract:  The syntax and semantics of P-Code, the inter
mediate language used in the current S-1 programming system 
is described.
.begin nofill
--↔--
.end