perm filename APRIL.ABS[BIB,CSR] blob sn#413878 filedate 1979-01-30 generic text, type C, neo UTF8

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