bluuebunny/crossref_metadata_2025_split huggingface dataset:
Report of session on concurrency
Authors: Schroeder Michael D. , Dennis Jack 
Published: November 2005

This session was devoted to discussion of primitives for synchronizing the execution of concurrent processes. Jack Dennis introduced the session by noting that concurrent activity in a computer systems leads to the possibility of nondeterminacy. While most users with applications programs do not want nondeterminate results, some applications are inherently nondeterminate in part, e.g., an airline seat reservation system. At a lower level, the programmers of the operating system itself need to write both determinate and nondeterminate programs. The challenge is in providing primitives at each level in a system which guarantee determinacy when that is required, yet allow the construction of nondeterminate programs when that is required. As a basis for discussion, Dennis invited Rick Holt to make a short presentation on the levels in a computer system and their relationship to synchronizing primitives.
Holt indicated that the principle reason we have concurrency in computer systems is the economic necessity to run I/O devices in parallel with the much faster central processors. There are also fancier reasons, like constructing nondeterminate computations. Concurrency is usually handled by embedding various synchronizing primitives in the system or in high-level programming languages. In order to decide what primitives are appropriate you need to know what problems are to be solved. The problems being solved depend in turn upon the level of the computer system being considered. A computer system can be divided into five levels: hardware, kernel, nucleus, subsystems, and applications. The kernel multiplexes the central processors, implementing processes. At this level very simple synchronization primitives may be sufficient, like turning off interrupts. A critical problem at this level is the processor allocation strategy and maintaining queues of waiting processes. The nucleus is responsible for sharing devices. We want to be able to write device managers that multiplex data paths and schedule the use of these paths. These managers can be built in two ways: distributed managers that execute as part of user processes or centralized managers that execute in their own processes. Dijkstra has told us how to handle the concurrency generated by decentralized managers using primitives like P and V. Message passing works for centralized managers. (Note that message buffers are an important system resource to be managed. They cannot be managed using message switching, so this management must occur in the kernel.) At the levels of subsystems and applications something more complex and specifically suited to certain applications may be required to control concurrency. At all levels concurrency is interrelated with problems of protection, reliability, and pre-emption. If we ignore these problems we will miss entirely the problems of implementing primitives to control concurrency. Holt also discussed the primitives used at the various levels in the SUE system, as described in his working paper.
Specification languages for control programs
Authors: Austin Joseph H. 
Published: November 2005

This study (1) describes an approach to the formal specification of control programs based on the generalized concept of binding. From this viewpoint, the individual operations of a control program may be described by a graphic specification language [related to mem-theory (2)], whose statements are pairs of graphs depicting the original and final binding states of system elements. A global view of interrelationships and dynamic behavior of the system may be described by an extension of Petri-nets (3, 4) depicting the flow of system elements from one state of local binding to another.
A rational approach to the design of a new programming language must begin with an analysis of the “meanings” that are to be expressed; an appropriate, compilable syntax can then be developed around this skeleton. Consequently, we seek to identify, the characteristic features of operating system programming, and in particular those that differentiate these programs from conventional ones.
Towards ISMs for OPSs
Authors: Berry Daniel M. 
Published: November 2005

Information structure models (ISMs) [Weg70] have been applied successfully to the study of programming languages both in their definitions [LW69, Wlk68,70,Wgb70] and in proofs of correctness and equivalence of various implementation strategies [Luc69,JH70,JL71,McG71,Bry72].
This paper examines briefly the possibility using ISMs to define operating systems (OPSs). We give a definition of the notion of ISM and indicate how to use them. Then we describe methods by which the process notion has been defined in the past in the hope that this will give some idea of the applicability of the ISM approach to the definition of OPSs.
A modest proposal for vector extensions to ALGOL
Authors: Zosel Mary E. 
Published: November 2005

Machines that possess instructions that are actually “higher level” than high-level language statements require extensions to traditional programming language. This paper explores the kinds of extensions necessary for adequate access to the CDC STAR instruction set. Specific problem areas considered are: access to the vector instructions, definition of descriptors, support of the variety of hardware data-types, and facilities for memory and register management.
It is fairly straightforward to define language facilities to cover most of these problems with minimum disruption of existing language features. Informal descriptions are given for syntactic and semantic extensions to ALA, an ALGOL based language. Features include declaration and usage of vector and descriptor variables, generation of vector values, subscripting slicing, and procedure linkage. The language constructs described are not limited in application to either the STAR or ALA. They should be easily adaptable to other languages and machines where vector constructs would enhance programming power.
Types, distribution, and test and correction times for programming errors
Authors: Shooman M. L. , Bolsky M. I. 
Published: November 2005

In order to develop some basic information on software errors, an experiment in collecting data on types and frequencies of such errors was conducted at Bell Laboratories.
The paper reports the results of this experiment, whose objectives were to: (1) Develop and utilize a set of terms for describing possible types of errors, their nature, and their frequency; (2) Perform a pilot study to determine if data of the type reported in this paper could be collected; (3) Investigate the error density and its correspondence to predictions from previous data reported; (4) Develop data on how resources are expended in debugging.
A program of approximately 4K machine instructions (final size) was chosen. Programmers were asked to fill out for each error, in addition to the regular Trouble Report/Correction Report (TR/CR) form, a special Supplementary TR/CR form for the purposes of this experiment. Sixty-three TR/CR and Supplementary forms were completed during the Test and Integration phase of the program.
In general, the data collected were felt to be accurate enough for the purposes of the analyses presented. The 63 forms represented a little over 1-1/2% of the total number of machine instructions of the program. (In good agreement with the 1% to 2% range noted in previous studies.)
It was discovered that a large percentage of the errors was found by hand processing (without the aid of a computer). This method was found to be much cheaper than techniques involving machine testing.
Early experience with Mesa
Authors: Geschke Charles M. , Morris James H. , Satterthwaite Edwin H. 
Published: November 2005

The experiences of Mesa's first users—primarily its implementers—are discussed, and some implications for Mesa and similar programming languages are suggested. The specific topics addressed are:
module structure and its use in defining abstractions,
data-structuring facilities in Mesa,
equivalence algorithm for types and type coercions,
benefits of the type system and why it is breached occasionally,
difficulty of making the treatment of variant records safe.
A unifying model for consistent distributed software development environments
Authors: Walpole J. , Blair G. S. , Malik J. , Nicol J. R. 
Published: November 2005

The increase in size and complexity of software projects over recent years has lead to the need for Software Development Environments (SDEs). SDEs are intended to provide assistance in the development of large software systems involving teams of people. It is generally agreed that SDE's should be built on a distributed base. However, the distribution of computer systems introduces several problems which make it very difficult to maintain the
consistency
of data.

To ensure that changes to data are made consistently the concept of atomic transactions is usually adopted. However, existing transaction mechanisms are unsuitable for use in a distributed SDE. Furthermore, transactions are not the only mechanism concerned with controlling changes to the SDE database. The control of change is also a task for version and configuration control mechanisms. Traditionally, the functions of version control, configuration control and transactions have been treated as separate, unrelated issues.
This paper presents a new model which unifies all three concepts in a distributed SDE. Mechanisms for supporting the new model are presented and the application of the model to the Cosmos Distributed SDE is discussed.
Modified structured decision table and its complexity
Authors: Misra A. K. , Chaudhary B. D. 
Published: November 2005

A modified structured decision table (MSDT) is introduced [7]
which is a modification of Structured decision Table (SDT) [6] to
document stages of the topdown program development. The level
definition of MSDT is kept such as to maintain conformation with
the top-down methodology of program construction. Further, the MSDT
besides functionally converting any flowchart, exposes the
construction of a program by considering one basic program
construct at a time.
In a Conventional Decision Tables (CDT) the conditions are
assumed to be independent of execution of action and the fact that
execution of an action may affect the outcome of a condition test
is not considered. It is also not taken into account that there may
be an action defining a variable without which condition test is
not possisble. But in case of MSDT such an assumption is not made
and the construction of a MSDT proceeds in such a way that these
facts are always taken into account.
Further in a CDT conditions can be tested in any sequence
independent of their occurences, where as in a MSDT conditions are
tested in a sequence totally dependent of their occurences, and
there exists a definite ordering in testing of conditions in
MSDT.
It has been shown that MSDT is also capable of representing both
structured as well as unstructured flowcharts or programs without
any change in the basic notions used for the construction of MSDT.
It is possible to convert unstructured flowcharts where
unstructuredness is due to intersecting Ifs, Loop with multiple
exit and multiple entry and Loop with mid exit, to MSDT without any
change in execution sequence with c+1 levels where c is the number
of basic program constructs in a program or flowchart. It is also
possible to obtain CDT or decision table suggested in [4] from
SDT.
The two complexity measures defined in [4] for decision tables
are level complexity (&and;) which is the number of values its
sequencing variable assumes when &infin; is not counted and
cyclomatic complexity (V<sub>T</sub>) is equal to
&rho;&minus;&and; where &rho; is the number of
rules in a decision table. Applying these measures, complexities of
different example decision tables has also been evaluated and it
has been shown that complexity of a MSDT of program or flowchart is
equal to the sum of complexities of the basic program constructs
available in the program or flowchart. Further the level and
cyclomatic complexities of these MSDT's compares very favourably
with other decision tables.
Dependence analysis for pointer variables
Authors: Horwitz S. , Pfeiffer P. , Reps T. 
Published: November 2005

Our concern is how to determine data dependencies between program constructs in programming languages with pointer variables. We are particularly interested in computing data dependencies for languages that manipulate heap-allocated storage, such as Lisp and Pascal. We have defined a family of algorithms that compute safe approximations to the flow, output, and anti-dependencies of a program written in such a language. Our algorithms account for destructive updates to fields of a structure and thus are
not
limited to the cases where all structures are trees or acyclic graphs; they
are
applicable to programs that build cyclic structures.

Our technique extends an analysis method described by Jones and Muchnick that determines an approximation to the actual layouts of memory that can arise at each program point during execution. We extend the domain used in their abstract interpretation so that the (abstract) memory locations are labeled by the program points that set their contents. Data dependencies are then determined from these memory layouts according to the component labels found along the access paths that must be traversed during execution to evaluate the program's statements and predicates.
For structured programming constructs, the technique can be extended to distinguish between loop-carried and loop-independent dependencies, as well as to determine lower bounds on minimum distances for loop-carried dependencies.
Type inference in the presence of type abstraction
Authors: Boehm H.-J. 
Published: November 2005

A number of recent programming language designs incorporate a type checking system based on the Girard-Reynolds polymorphic λ-calculus. This allows the construction of general purpose, reusable software without sacrificing compile-time type checking. A major factor constraining the implementation of these languages is the difficulty of automatically inferring the lengthy type information that is otherwise required if full use is made of these languages. There is no known algorithm to solve any natural and fully general formulation of this “type inference” problem. One very reasonable formulation of the problem is known to be undecidable.
Here we define a restricted version of the type inference problem and present an efficient algorithm for its solution. We argue that the restriction is sufficiently weak to be unobtrusive in practice.
Link-time optimization of address calculation on a 64-bit architecture
Authors: Srivastava Amitabh , Wall David W. 
Published: November 2005

Compilers for new machines with 64-bit addresses must generate code that works when the memory used by the program is large. Procedures and global variables are accessed indirectly via
global address tables
, and calling conventions include code to establish the addressability of the appropriate tables. In the common case of a program that does
not
require a lot of memory, all of this can be simplified considerably, with a corresponding reduction in program size and execution time.

We have used our link-time code modification system OM to perform program transformations related to global address use on the Alpha AXP. Though simple, many of these are
whole-program
optimizations that can be done only when we can see the entire program at once, so link-time is an ideal occasion to perform them.

This paper describes the optimizations performed and shows their effects on program size and performance. Relatively modest transformations, possible without moving code, improve the performance of SPEC benchmarks by an average of 1.5%. More ambitious transformations, requiring an understanding of program structure that is thorough but not difficult at link-time, can do even better, reducing program size by 10% or more, and improving performance by an average of 3.8%.
Even a program compiled monolithically with interprocedural optimization can benefit nearly as much from this technique, if it contains statically-linked pre-compiled library code. When the benchmark sources were compiled in this way, we were still able to improve their performance by 1.35% with the modest transformations and 3.4% with the ambitious transformations.
Counting solutions to Presburger formulas
Authors: Pugh William 
Published: November 2005

We describe methods that are able to count the number of integer solutions to selected free variables of a Presburger formula, or sum a polynomial over all integer solutions of selected free variables of a Presburger formula. This answer is given symbolically, in terms of symbolic constants (the remaining free variables in the Presburger formula).
For example, we can create a Presburger formula who's solutions correspond to the iterations of a loop. By counting these, we obtain an estimate of the execution time of the loop.
In more complicated applications, we can create Presburger formulas who's solutions correspond to the distinct memory locations or cache lines touched by a loop, the flops executed by a loop, or the array elements that need to be communicated at a particular point in a distributed computation. By counting the number of solutions, we can evaluate the computation/memory balance of a computation, determine if a loop is load balanced and evaluate message traffic and allocate message buffers.
Engineering a production code generator
Authors: Crawford John 
Published: November 2005

This paper describes the structure of a code generator formed by merging the best aspects of three code generation techniques: Graham-Glanville parser-driven code generation [G] [GG] [GR] [HG], the register allocation/spill mechanism from the Portable C Compiler [J], and a code template expander [W]. The Graham-Glanville method was modified to use a standard LALR parser and table builder, and the register allocation method was extended in several significant ways in order to make optimal use of a machine with characterized registers.
This code generator is a part of the Pascal-86 compiler developed by Intel Corporation as one of several compilers supporting its iAPX-86 (8086) microprocessor family. The language supported by the compiler is an extension of the Draft International Standard Pascal, level 0. Object code generated by this method compares favorably to code produced by other compilers for the 8086, as well as Pascal compilers for other machines. Since its release in March 1981, the code generator has proved to be quite reliable and easy to maintain.
Control flow aspects of semantics directed compiling (Summary)
Authors: Sethi Ravi 
Published: November 2005

We focus on the part of a compiler between syntax analysis and code generation. A language is specified by adding semantic rules in a functional notation to the syntax of the language. Starting with a small sublanguage of while statements, the semantics of the statement constructs of C is built up incrementally. Using a small ad hoc code generator, a compiler has automatically been constructed from the semantics. The semantic description is analogous to a syntax directed construction of a flow diagram for a program. In analogy with grammars and parser generators, minimal knowledge of the underlying theory is required.
For the control flow aspects of languages, efficient compilers can quickly be generated.
The document editor
Authors: Walker Janet H. 
Published: November 2005

As understanding of a particular problem domain matures, its tools become more specialized, moving from general low-level tools to more specialized high-level tools. Early work in a field applies the same set of low-level aids to all problems. Gradually more specialized tools emerge as we come to better understand the problem and the tools that are best for it.
Since the emergence of the first program editors in the early 1960s we have learned a lot about the editing process and about building editors. Recently several editors specialized for editing program sources, text, and data structures have been developed. To date, little work has been reported on specialized document editors for editing complex text. This paper describes a research effort into identifying the requirements for an interactive environment for editing complex documents and an initial implementation for the environment.
Porting the Zed compiler
Authors: Bonkowski G. B. , Gentleman W. M. , Malcolm M. A. 
Published: November 2005

Zed is the base language used to implement the portable realtime operating system Thoth[7], and to write commands, utilities, application programs, and other software which run under Thoth. (Zed is similar to C, although language details are not important in this paper.) One of the founding principles of Thoth is our experience that the hardest problems in porting programs usually arise when interfacing to different operating systems. By porting the whole operating system first, we ensure that other programs see the same system interface. Hence, with a modicum of care in programming, programs can be machine independent in that, without change, they can be compiled for any machine to which Thoth has been ported. Since the Zed compiler is a program which runs under the Thoth operating system, it is portable in this sense, and the same source serves to produce either native mode or cross compilers because it does not depend on the machine on which the compiler will run.
Compilers, in common with certain other “system software”, are, however, machine specific in that the output from executing a compiler must be different depending upon the machine on which that output is destined to be run. Clearly, for Thoth to be ported to many machines, the compiler should be portable in this second sense: as much as possible of the source of the compiler should be machine invariant, that is, independent of the target machine, and for those parts which are machine specific, there must be a well organized scheme to assist realizing versions for new machines. The Zed compiler is designed to ease such ports. Actually, the objective is broader than that, because the initial port is only part of the problem: once versions of the compiler are available for several machines, we still have the problems of maintaining all these different versions, enhancing them, and evolving them to follow changes in the language. To do this, we need a structure that is easy to understand and to work with. We also want to minimize the amount of source code for which multiple versions must exist.
The design of a global optimizer
Authors: Mintz Ronald J. , Fisher Gerald A. , Sharir Micha 
Published: November 2005

We are constructing a compiler for a high level systems and applications programming language. Because the compiler is required to generate efficient object code, a global optimization phase and register allocation phase are an integral part of the design. It was determined that the familiar optimizations of code motion, redundant expression elimination, and dead code removal would be sufficient.
The optimizer design was to be based on the most recent applicable theoretical results, yet simple and straightforward to implement. Traditional approaches were considered inadequate because they assume a primitive intermediate code representation (quadruples), elaborate flow graph constructions, and numerous special cases. High level data flow analysis as proposed by Rosen [1,2] provided the framework we sought. Using his approach, the parse tree of the program, with its high level control structures intact, becomes a suitable intermediate representation. Complex statement structures are analyzed quickly in two tree traversals to determine the solutions to data flow problems.