bluuebunny/crossref_metadata_2025_split huggingface dataset:
Parallel algorithm design for workstation clusters
Authors: Magee J. N. , Cheung S. C. 
Published: November 2006

AbstractClusters of workstations connected by local area networks are in common use in many organizations. The combined processing power of these clusters is rarely exploited owing to the lack of suitable parallel algorithms. The paper describes a parallel programming paradigm calledsupervisor‐worker, suitable for the workstation environment, which can be used to speed up the execution of a large class of existing sequential programs. Simple formulae are developed to predict the speed‐up of a parallel algorithm developed in this way. The predictions depend on two easily‐determined parameters of the sequential program and the characteristic communication cost of the workstation cluster. Consequently, it is possible to estimate the benefits of the parallel program before proceeding with detailed implementation. As an example, the parallel version of a travelling salesman program is developed and the measured speed‐up compared with the predicted speed‐up.
A syntax‐directed integrated programming environment for developing simd supercomputer software
Authors: Perrott R. H. , Lunney T. F. 
Published: November 2006

AbstractThe increasing availability and use of supercomputers has highlighted the need for better software development techniques and tools. Supercomputers have traditionally been extensively used by engineers and scientists whose preference for Fortran is well established and recognized. However, in the parallel environment offered by the latest configurations of supercomputers, more sophisticated languages and tools are required. The present experiment is concerned with devising a syntax‐directed integrated programming environment based on the language Actus, which enables a user to develop and debug programs before submitting them to an actual supercomputer. Actus is a high‐level, Pascal‐like language, with SIMD parallel processing features. It enables the user to ignore the idiosyncrasies of the chosen supercomputer by abstracting the parallel processing detail to a higher level. The editing, compilation and testing phases of program development are all integrated, providing a single consistent interface for all activities relating to program development.
Performance of lazy combinator graph reduction
Authors: Hartel Pieter H. 
Published: November 2006

AbstractThe performance of program‐derived combinator graph reduction is known to be superior to that of graph reduction based on a fixed set of standard combinators. The major advantage of program‐derived combinator reduction is that it uses less transient store than standard combinator reduction. We show on what activities a combinator reduction algorithm spends its execution time. Based on this analysis we show that it depends to a large extent on the application how much faster a program will run if program‐derived combinators are used instead of standard combinators. The analysis is based on experimental evidence obtained from a small bench‐mark of medium‐size functional programs. Performance gains of up to 11 x are reported for target architectures on which each memory reference consumes one unit of time. The results are valid for implementations of combinator graph reduction that use binary graphs.
A parallel implementation of the douglas‐peucker line simplification algorithm
Authors: Vaughan Jon , Whyatt Duncan , Brookes Graham 
Published: November 2006

AbstractAs parallel machines become more widely available, many existing algorithms are being converted to take advantage of the improved speed offered by such computers. However, the method by which the algorithm is distributed is crucial towards obtaining the speed‐ups required for many real‐time tasks. This paper presents three parallel implementations of the Douglas—Peucker line simplification algorithm on a Sequent Symmetry computer and compares the performance of each with the original sequential algorithm.
An approach to genuine dynamic linking
Authors: Ho W. Wilson , Olsson Ronald A. 
Published: November 2006

AbstractThis paper describes a new approach to dynamic link/unlink editing. The basis of this approach is a library of link editing functions that can add compiled object code to or remove such code from a process any time during its execution. Loading modules, searching libraries, resolving external references, and allocating storage for global and static data structures are all performed at run time. This approach provides the efficiency of native machine code execution along with the flexibility to modify a program during its execution, thereby making many new applications possible. This paper also describes three sample applications of these dynamic link editing functions: program customization, incremental program development, and support for debugging and testing. A prototype of this approach is implemented under UNIX as a library package called dld for the C programming language and is available for VAX, Sun 3 and SPARCstation machines.
Reactive C: An extension of C to program reactive systems
Authors: Boussinot Frédéric 
Published: November 2006

AbstractReactive systems are interactive programs that react continuously to sequences of activations coming from the external world. Reactive programming leads to a new programming style where one programs in terms of reactions to activations and reasons in a logic of instants. This paper describes an extension of the C programming language called RC (for ‘Reactive C’) to program reactive systems. The language RC is described, then some programming examples are given to illustrate the reactive approach. The main RC notions come directly from the Esterel synchronous programming language. Finally, the Esterel and RC languages are compared.
Utility servers in charlotte
Authors: Yang Cui‐Qing , Finkel Raphael 
Published: November 2006

AbstractMost distributed operating systems are built with a kernel replicated in each machine that supports only basic interprocess communication (IPC) and process control. All other system services, such as memory management, file system, and name service, are distributed in a set of utility servers, which are ordinary processes (except perhaps for some privileges) residing at various machines. Design and implementation of such utility servers in distributed environments are far different from those in a centralized system.This paper presents our experience in building utility servers in Charlotte, a message‐based distributed operating system running on a loosely‐coupled multicomputer. Utility services in Charlotte are provided by server squads. Each member in a squad covers services to its own community. The squad as a whole co‐operatively provides services to the entire system. These servers are designed with the goals of simplicity, efficiency and robustness. They are intended to support a multiprogramming system for the development of distributed algorithms and other distributed applications. We address several major issues in developing a utility server, including the server structure, the management of message buffers, deadlock, and the robustness of server processes. Several utility servers in the Charlotte system are discussed as real examples.
A modular fully‐lazy lambda lifter in Haskell
Authors: Jones Simon L. Peyton , Lester David 
Published: November 2006

AbstractAn important step in many compilers for functional languages is lambda lifting. In his thesis, Hughes showed that by doing lambda lifting in a particular way, a useful property called full laziness can be preserved. Full laziness has been seen as intertwined with lambda lifting ever since.We show that, on the contrary, full laziness can be regarded as a completely separate process to lambda lifting, thus making it easy to use different lambda lifters following a full‐laziness transformation, or to use the full‐laziness transformation in compilers which do not require lambda lifting.On the way, we present the complete code for our modular fully‐lazy lambda lifter, written in the HASKELL functional programming language.
A fortran language system for mutation‐based software testing
Authors: King K. N. , Offutt A. Jefferson 
Published: November 2006

AbstractMutation analysis is a powerful technique for testing software systems. The Mothra software testing project uses mutation analysis as the basis for an integrated software testing environment. Mutation analysis requires executing many slightly differing versions of the same program to evaluate the quality of the data used to test the program. The current version of Mothra includes a complete language system that translates a program to be tested into intermediate code so that it and its mutated versions can be executed by an interpreter.In this paper, we discuss some of the unique requirements of a language system used in a mutation‐based testing environment. We then describe how these requirements affected the design and implementation of the Fortran 77 version of the Mothra system. We also describe the intermediate language used by Mothra and the features of the language system that are needed for software testing. The appendices contain a full description of the intermediate language and the mutation operators used by Mothra.The design and implementation techniques that were developed for Mothra are applicable for constructing not just software testing systems, but any type of program analysis system or language system for a special‐purpose application. In particular, we discuss decisions made and techniques developed by the Mothra team that can be useful in such applications as debuggers, program measurement tools, software development environments and other types of program analysis systems.
Tlex
Authors: Kearns Steven M. 
Published: November 2006

AbstractTLex is a pattern matching and parsing library for C++. In comparison to existing pattern matching tools, TLex sets a new standard for expressiveness when nearly optimal speed is required. It incorporates recent advances in regular expression technology that make it easier to write patterns and extract information from a successful match. An overview of TLex is presented, the pattern and parsing languages are described, and actual results of its use are discussed.
A methodology for constructing predicate transition net specifications
Authors: He Xudong , Lee John A. N. 
Published: November 2006

AbstractIn this paper, a methodology for constructing hierarchical and structured predicate transition net specifications is developed, which includes new systematic notation extensions for supporting various transformation techniques upon predicate transition nets and several rules for applying such transformation techniques. The levelling technique in data‐flow diagrams is adapted in the refinement and the abstraction techniques, and the state decomposition idea in state‐charts is employed in designing various label formulation operators. The methodology is illustrated through the specification of a lift system. The methodology can significantly reduce the constructing complexity and enhance the comprehensibility of large predicate transition net specifications.
A code generation interface for ANSI C
Authors: Fraser Christopher W. , Hanson David R. 
Published: November 2006

Abstract1cc is a retargetable, production compiler for ANSI C; it has been ported to the VAX, Motorola 68020, SPARC, and MIPS R3000, and some versions have been in use for over a year and a half. It is smaller and faster than generally available alternatives, and its local code is comparable. This paper describes the interface between the target‐independent front end and the target‐dependent back ends. The interface consists of shared data structures, a few functions, and a dag language. While this approach couples the front and back ends tightly, it results in efficient, compact compilers. The interface is illustrated by detailing a code generator that emits naive VAX code.
Administrators and multiprocessor rendezvous mechanisms
Authors: Gentleman W. Morven , Shepard Terry , Thoreson Douglas V. P. 
Published: November 2006

AbstractThis paper discusses rendezvous on multiprocessors. Three different approaches are compared, represented by three specific systems: Ada, Harmony and BNR Pascal. All three permit tasks to run on multiple processors and use blocking communications primitives, but there are significant differences. For example, control over replying to messages out of sequence and over the allocation of tasks to processors is omitted in Ada, but is available in Harmony. The approach represented by BNR Pascal follows a middle road between Harmony and Ada: a low level protocol, invisible to the programmer, is used to ensure communications reliability, but the programmer is aware of when a rendezvous is remote. If performance considerations and verbosity and robustness are ignored, all three approaches are equivalent. To illustrate this equivalence, and to demonstrate clearly the complexity of the Ada rendezvous, an Ada rendezvous administrator written using Harmony is described. A second method of adapting Harmony to Ada is also presented, in which the Harmony primitives are modified to be closer to Ada. In practice, using Harmony primitives directly will usually result in better programs. It is argued that something very much like the rendezvous adminstrator is needed for any actual implementation of the Ada rendezvous.
User interface—application communication in the Chimera user interface management system
Authors: Wood Catherine A. , Gray Philip D. 
Published: November 2006

AbstractUntil quite recently, perhaps the least appreciated part of user interface management system (UIMS) architecture has been the interface to the application. A number of approaches to interface‐application communication have been attempted, but these have suffered as a result of being non‐programmable, unstructured and/or static. This paper presents the user‐interface‐application communication system developed for the Chimera UIMS, which attempts to address these problems. This system enables interprocess communication between user interface and application via an explicit, programmable UIMS component—an application linkage, which is structured, dynamic and reconfigurable at run‐time. The internal structure of the linkage is described, along with the mechanism for communication with dialogue control and application. An extensive example is developed in order to illustrate the communication process to and from the user via dialogue control and linkage to the application.
μC++: Concurrency in the object‐oriented language C++
Authors: Buhr P. A. , Ditchfield Glen , Stroobosscher R. A. , Younger B. M. , Zarnke C. R. 
Published: November 2006

AbstractWe present a design, including its motivation, for introducing concurrency into C++. The design work is based on a set of requirements and elementary execution properties that generate a corresponding set of programming language constructs needed to express concurrency. The new constructs continue to support object‐oriented facilities such as inheritance and code reuse. Features that allow flexibility in accepting and subsequently postponing servicing of requests are provided. Currently, a major portion of the design is implemented, supporting concurrent programs on shared‐memory uniprocessor and mulitprocessor computers.
Adding run‐time checking to the portable C compiler
Authors: Steffen Joseph L. 
Published: November 2006

AbstractRun‐time checking of array subscripts and pointer bounds was added to the Portable C Compiler (PCC). Memory overwrite bugs are then caught as they happen instead of when the overwritten memory is used later in the program execution. The run‐time checking compiler is used both to find the true cause of a core dump and to eliminate run‐time errors as the cause of unexpected program behavior. On average, it takes about 40 percent longer to compile, the generated code is about three times larger, and it runs about ten times slower. This performance may seem slow, but it typically reduces days of debugging to less than an hour. The implementation described herein can be adapted to any C compiler as it describes how to generate run‐time checking code in a machine/compiler independent way by changing the intermediate expression trees. In four years of use it has found latent bugs and the cause of intermittent core dumps in programs used for many years by thousands of people.
The elaboration order problem of ada
Authors: Lander Leslie C. , Mitra Sandeep , Singhvi Nitin , Piatkowski Thomas F. 
Published: November 2006

AbstractA serious problem in large Ada programs is finding a satisfactory order of elaboration for all of the program's compilation units. Some elaboration sequence must be selected but access to a program entity before its elaboration will raise the exception (PROGRAM_ERROR) shortly after execution of the program begins. The rules of the 1983 Ada standard1fail to ensure that validated compilers produce a satisfactory elaboration order, or report an error if static analysis shows that such an order may not exist. The problem can make programs non‐portable and sensitive to modifications. This paper presents an algorithm ada_elab which determines an order of elaboration, free of PROGRAM_ERROR, if link‐time, static analysis can determine that there is one. Examples are used to illustrate the occurrence of elaboration errors and the inadequacy of pragma ELABORATE to resolve the problem. The paper closes with descriptions of elaboration and elaboration‐related problems that cannot be handled by ada_elab, access before initialization and coding practices that should avoid elaboration and initialization errors. While Ada is the subject of this paper, the problem being studied could occur in any language that permits a complex initialization of individual program modules prior to the execution of the main program module.
The evolution of an object‐oriented compiler framework
Authors: Graver Justin O. 
Published: November 2006

AbstractIncreasing code reuse in software systems is an important way to decrease development and maintenance costs, reduce the time required to respond to new requirements, and significantly advance the feasible complexity limits for new systems. Object‐oriented programming languages and environments provide fundamental support for truly reusable code through abstraction, inheritance, and polymorphism. Reusable code is a prerequisite for a significantly more powerful concept: reusable design. Frameworks of resuable design abstractions are difficult to create and typically evolve over a long period of use and refinement. Thus, it is important to understand how systems evolve and how this evolution can be directed to achieve the best results.This article illustrates some of the standard transformations, called refactorings, that occur in object‐oriented systems as they evolve by describing the creation and evolution of a framework for building general‐purpose string‐to‐object translators. It reflects our experiences with object‐oriented compilers over a five year period while working on the Typed Smalltalk compiler project.
Practical experience with OS/2 installable file systems
Authors: Ogle David M. , Sullivan Neil G. , Williams E. Hollins 
Published: November 2006

AbstractThe installable file system (IFS) faculty on OS/2 offers an efficient mechanism for expanding the abilities of the OS/2 kernel. Two prototypes illustrate the usefulness of the IFS facility. An OS/2 port of the Andrew File System (AFS) allows users to access global community files while retaining the private local file system on the OS/2 machine. An IFS implementation of a network protocol mapper, which maps TCP/IP socket calls to SNA Advanced Program‐to‐Program Communication (APPC) calls, provides the ability to run any socket program on an APPC network after simply re‐linking with the mapping library. The only impediment to the development of these prototypes is the lack of kernel‐level interfaces to operating system devices, resulting in time‐consuming data movement back up to the user level to access the network and the local disks. This impediment will disappear as OS/2 and its associated support software matures.
Issues in porting software from c to c++
Authors: Hashemi Reza , Leach Ronald J. 
Published: November 2006

AbstractThis paper describes an experiment in the development of a small piece of software in both the languages C and C++ in a university setting. The C++ codes were found to be more modular than the corresponding C codes. Some of the other effects of C++ on program quality are very briefly discussed.The paper also discusses some of the errors that C programmers may make as novice C++ programmers, and the testing of object‐oriented programs. Some of the error types possible in C++, but not in C, include delays in the flushing of output buffers and polymorphism.
A group process for defining local software quality: Field applications and validation experiments
Authors: Trammell Carmen J. , Poore J. H. 
Published: November 2006

Abstract‘Global’ measures of software quality are generally not used by practitioners because they have not been calibrated for local operating environments. A participative process for defining local software quality has been defined, applied in the field, and evaluated in formal validation experiments. In four field applications of the process, a ‘jury’ of seasoned practitioners ranked a sample of modules from the organization's inventory of code and produced a ‘software quality rule set’. The results of each field application were tested in a formal validation experiment to determine whether the obtained rule set was a valid representation of the organization's sense of quality, i.e. whether the locally‐derived rules could enable non‐organizational programmers to make judgments about quality that were similar to those of the jury. In each experiment, non‐organizational programmers ranked the same set of modules that were ranked by the organization's jury, using either the locally‐derived rules, generic (textbook) rules, placebo (non‐helpful) rules, or no rules. The correlation between the judgments of non‐organizational programmers using local rules and the jury was statistically significant at p < 0–005; all other correlations were significant at p < 0–005. The results support a conclusion that the group process for defining local software quality is reliable in producing valid rule sets.
Garbage collection alternatives for icon
Authors: Fernandez Mary F. , Hanson David R. 
Published: November 2006

AbstractCopying garbage collectors are becoming the collectors of choice for very high‐level languages and for functional and object‐oriented languages. Copying collectors are particularly efficient for large storage regions because their execution time is proportional only to the amount of accessible data, and they identify and compact this data in one pass. In contrast, mark‐and‐sweep collectors execute in time proportional to the memory size and compacting collectors require another pass to compact accessible data. The performance of existing systems with old compacting mark‐and‐sweep collectors might be improved by replacing their collectors with copying collectors. This paper explores this possibility by describing the results of replacing the compacting mark‐and‐sweep collector in the Icon programming language with four alternative collectors, three of which are copying collectors. Copying collectors do indeed run faster than the original collector, but at a significant cost in space. An improved variant of the compacting mark‐and‐sweep collector ran even faster and used little additional space.