Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: Internet Mail; site waltz.UUCP Path: utzoo!decvax!ucbvax!ucdavis!lll-crg!mordor!ut-sally!sally!techreports-request From: techreports-request@sally.UUCP Newsgroups: mod.techreports Subject: Stanford Tech Reports Message-ID: <8601040956.AA12152@csevax.smu> Date: Sat, 4-Jan-86 04:56:39 EST Article-I.D.: csevax.8601040956.AA12152 Posted: Sat Jan 4 04:56:39 1986 Date-Received: Sun, 5-Jan-86 01:22:36 EST Lines: 344 Approved: techreports-request@sally.UUCP Posted-Date: Sat, 4 Jan 86 03:56:39 cst To: post-mod-tr@ut-sally.UUCP 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 -------