bluuebunny/crossref_metadata_2025_split huggingface dataset:
Exceptional C or C with exceptions
Authors: Gehani N. H. 
Published: November 2006

AbstractC does not have exception handling facilities. Errors are handled by examining the value returned by each function and signals (conditions reported to the program) are handled by using library functions. These approaches lead to ad hoc error‐handling techniques and can make programs hard to understand. Exceptional C, a superset of C, provides exception handling facilities. Exceptional C integrates the two techniques used by C programmers (i.e., status values and signals) to handle errors into one unified exception handling mechanism. In this paper, I review exception handling models, specify the criteria used for designing the exception handling facilities in Exceptional C, and then describe these facilities. I also illustrate the use of the exception handling facilities with examples.
Linkage analysis of processes
Authors: Yaung Alan T. , Raz Tzvi 
Published: November 2006

AbstractThis paper presents a methodology for the analysis of the linkage among the processes in an organization. The methodology has three main steps: model construction; connectivity analysis; and structure analysis. The model construction step generates a linkage matrix which is used in the following steps. The connectivity analysis is based on linkage consistency and interprocess coupling metrics, which are defined for each process individually and for all the processes in the organization as a group. The clustering algorithm is based on a linkage intensity measure derived from the linkage matrix. Following a detailed description of the methodology and its metrics and algorithms, the results obtained in a medium‐size software development organization are presented.
Stress testing of compilers for modula‐2
Authors: Pronk C. 
Published: November 2006

AbstractDuring standardization discussions on Modula‐2 the question was raised whether the future standard should need a clause stating a set of minimal requirements for conforming implementations regarding the ‘structuredness’ of lexical, syntactical and run‐time constructs in programs written in this language. It was decided to test a number of compilers to find their actual limits on the structuredness of some of these constructs. The test results do not only show these limits, but the inability of some compilers to handle large and complex inputs is shown as well.
Experimenting with dynamic linking with ADA
Authors: Inverardi Paola , Mazzanti Franco 
Published: November 2006

AbstractAn approach to achieving dynamic reconfiguration within the framework of Ada1 is described. A technique for introducing a kernel facility for dynamic reconfiguration in Ada is illustrated, and its implementation using the Verdix VADS 5.5 Ada compiling system on a Sun3–120 running the 4.3 BSD Unix operating system is discussed. This experimental kernel allows an Ada program to change its own configuration dynamically, linking new pieces of code at run‐time. It is shown how this dynamic facility can be integrated consistently at the Ada language level, without introducing severe inconsistencies with respect to the Standard semantics.
Techniques for fast instruction cache performance evaluation
Authors: Whalley David B. 
Published: November 2006

AbstractCache performance has become a very crucial factor in the overall system performance of machines. Effective analysis of a cache design requires the evaluation of the performance of the cache for typical programs that are to be executed on the machine. Recent attempts to reduce the time required for such evaluations either result in a loss of accuracy or require an initial pass by a filter to reduce the length of the trace. This paper evaluates techniques that attempt to overcome these problems for instruction cache performance evaluation. For each technique variations with and without periodic context switches are examined. Information calculated during the compilation is used to reduce the number of references in the trace. Thus, in effect references are stripped before the initial trace is generated. These techniques are shown to significantly reduce the time required for evaluating instruction caches with no loss of accuracy.
Experience with PMS‐Prolog: A distributed, coarse‐grain‐parallel prolog with processes, modules and streams
Authors: Wise Michael J. 
Published: November 2006

AbstractPMS‐Prolog is an implementation of Prolog designed for distributed systems, and therefore uses coarsegrain parallelism in preference to the fine‐grain parallelism of other implementations. Prolog processes are formally defined and interprocess communication is explicit. An overview of PMS‐Prolog is provided, followed by an examination of the PMS‐Prolog solutions to four problems. These solutions are also compared to other solutions from the literature. From this, the strengths and weaknesses of the PMS‐Prolog model can be seen. Avenues for improving the model are then suggested.
Reducing object storage requirements in a multi‐user environment
Authors: Boysen Pete , Shah Pinaki 
Published: November 2006

AbstractMany Smalltalk implementations store objects in a large file called a virtual image. Each user must have a copy of the virtual image to execute. Since the image can exceed a megabyte in size, considerable disk space is required to support such a system in a multi‐user environment. In this paper, a method is described which can reduce storage requirements for systems which use generation scavenging as a memory reclamation technique. This method also improves the performance of the checkpoint operation and offline garbage‐collection.
Success rate of interpolation in subsegment prediction
Authors: Wright William E. , Jeyaratnam Sakthivel 
Published: November 2006

AbstractWe consider the accuracy of linear interpolation in predicting which subsegment contains a random key, given that the key is contained in a particular segment consisting of a fixed number of subsegments. We assume that keys are stored in a file in sorted order, that the file is divided into fixed‐size segments, and that the first key in the segment containing the desired key is known, as is the first key of the next segment. We present empirical results for real files in which keys are social security numbers, names and telephone numbers, and for files of keys generated randomly from the uniform and from the exponential distributions. We present a theoretical analysis of the average success rate for the case in which keys are uniformly distributed. We show that the success rate depends on the number of subsegments in a segment, the size of a subsegment, and the distribution of keys, and that it is much higher than for random guessing. We describe practical applications in which this technique can be efficiently used.
Bonsai: A compact representation of trees
Authors: Darragh John J. , Cleary John G. , Witten Ian H. 
Published: November 2006

AbstractThis paper shows how trees can be stored in a very compact form, called ‘Bonsai’, using hash tables. A method is described that is suitable for large trees that grow monotonically within a predefined maximum size limit. Using it, pointers in any tree can be represented within 6 + [log2n] bits per node where n is the maximum number of children a node can have. We first describe a general way of storing trees in hash tables, and then introduce the idea of compact hashing which underlies the Bonsai structure. These two techniques are combined to give a compact representation of trees, and a practical methodology is set out to permit the design of these structures. The new representation is compared with two conventional tree implementations in terms of the storage required per node. Examples of programs that must store large trees within a strict maximum size include those that operate on trie structures derived from natural language text. We describe how the Bonsai technique has been applied to the trees that arise in text compression and adaptive prediction, and include a discussion of the design parameters that work well in practice.
Visualizing a hierarchy of performance models for software systems
Authors: Ammar Reda A. , Rosiene Carolyn Pe 
Published: November 2006

AbstractDefinition of a software process to be analyzed is normally top‐down. Analysis starts with a rough description and evolves into finer granularity as more performance and functional requirements become available. This process involves different performance models at each stage. The relationship between these models forms a hierarchy of performance models. Performance parameters propagate bottom‐up and the analysis of these models is very complex, so that it is essential to develop computer aided performance evaluation (CAPE) tools to support the evaluation process. In this work, we developed a graphical interface for CAPE environments called the GRAphical Performance Evaluation (GRAPE) system. GRAPE supports the structural design of five different performance models: queueing, state, computation structure, data flow and statistical models. These models can be used to design parallel/distributed real‐time software systems at different levels of granularity. GRAPE is the front‐end tool for a CAPE environment that will allow the user to integrate the relationships between different performance metrics at different levels of analysis. These metrics propagate between the modeling hierarchy to arrive at a final quantitative or symbolic measure of its performance.
Kibitz—connecting multiple interactive programs together
Authors: Libes Don 
Published: November 2006

AbstractExpect is a programming language for automating interactive programs. Recently, people have begun using Expect to connect multiple interactive programs together, allowing for new classes of applications. With some basic building blocks and a little scripting, it is possible to build such applications quickly.This paper discusses the general technique, while focusing on a particular example: Kibitz. Kibitz connects multiple sessions and applications together, providing a means for consulting, group editing, or other cooperative tasks. Kibitz in turn, can be used as a module in building additional programs of this type. Using Kibitz, we demonstrate how to enable cron or background processes to call upon and interact with users, e.g. for guidance or debugging.Owing to program reuse, our approach avoids many portability issues already addressed and solved by existing programs. Kibitz has no special coding for byte swapping, structure encoding, or job control, and requires neither kernel modifications nor setuid or other permissions even though it runs over a network and deals with multiple users, job control, and sophisticated programs such as shells and fullscreen editors.
Reducing compilation time by a compilation server
Authors: Onodera Tamiya 
Published: November 2006

AbstractIn language systems that support separate compilation, we often observe that header files are internalized over and over again when the source files that depend on them are compiled. Making a compiler a long‐lived server eliminates such redundant processing of header files, thus reducing the compilation time. The paper first describes compilation servers for C‐family languages in general, and then a compilation server for our C‐based object‐oriented language in particular. The performance results of our server show that a compilation server can substantially shorten the compilation time.
An execution profiler for window‐oriented applications
Authors: Gupta Aloke , Hwu Wen‐Mei W. 
Published: November 2006

AbstractExecution profiles are important in analyzing the performance of computer programs on a given computer system. However, accurate and complete profiles are difficult to arrive at for programs that follow the client‐server model of computing, as in the popular X Window System. In X Window applications, considerable computation is invoked at the display server and this computation is an important part of the overall execution profile. The profiler presented in this paper generates meaningful profiles for X Window applications by estimating the time spent in servicing the messages in the display server. The central idea is to analyze a protocol‐level trace of the interaction between the application and the display server and thereby construct an execution profile from the trace and a set of metrics about the target display server. Experience using the profiler for examining bottlenecks is presented.
Lexical analysis of inflected Arabic words using exhaustive search of an augmented transition network
Authors: Rafea Ahmed A. , Shaalan Khaled F. 
Published: November 2006

AbstractThis paper presents a lexical analyser for inflected Arabic words. An augmented transition network (ATN) technique was used to represent the context‐sensitive knowledge about the relation between a stem and inflectional additions. An exhaustive‐search algorithm is developed to traverse the ATN, generating all possible interpretations of an inflected Arabic word. The arcs of the ATN are augmented with rules containing conditions and actions. More than one rule is associated with some arcs. The states of the ATN are represented by Pascal procedures.
Debugging with dynamic slicing and backtracking
Authors: Agrawal Hiralal , Demillo Richard A. , Spafford Eugene H. 
Published: November 2006

AbstractProgrammers spend considerable time debugging code. Symbolic debuggers provide some help but the task remains complex and difficult. Other than breakpoints and tracing, these tools provide little high‐level help. Programmers must perform many tasks manually that the tools could perform automatically, such as finding which statements in the program affect the value of an output variable for a given test case, and what was the value of a given variable when the control last reached a given program location. If debugging tools provided explicit support for these tasks, the debugging process could be automated to a significant extent.In this paper we present a debugging model, based on dynamic program slicing and execution backtracking techniques, that easily lends itself to automation. This model is based on experience with using these techniques to debug software. We also present a prototype debugging tool, SPYDER, that explicitly supports the proposed model, and with which we are performing further debugging research.
Emulating an operating system on top of another
Authors: Franz Michael 
Published: November 2006

AbstractIn this paper, we present the design of an operating‐system emulator. This software interface provides the services of one operating system (Oberon) on a machine running a different operating system (Macintosh), by mapping the functions of the first onto equivalent calls to the second. The construction of this emulator proceeded in four distinct phases, documented here through examples from each of these phases. We believe that our four‐phase approach can be beneficial whenever a larger software system needs to be adapted from one architecture onto another. In conclusion, we relate some of the lessons learned and propose guidelines for similar engineering projects.
Lock‐and‐key strategies for handling undefined variables
Authors: Borie Richard B. , Parrish Allen S. , Mandyam Srinivas 
Published: November 2006

AbstractMost programming languages ignore the problem of undefined variables and permit compilers to allow the leftover contents of the memory cells belonging to such variables to be referenced. Although efficient, this type of semantics does not support software engineering, because defects might arise in subtle ways and might be difficult to locate. Two other types of semantics that better support software engineering are to either initialize all variables to some default, e.g. zero, or to require that all references to undefined variables be treated as errors. However, these types of semantics are obviously more expensive than simply ignoring the undefined variables entirely.In this paper, we propose a simple technique that works equally well for both of these latter two types of semantics, and whose efficiency compares favorably for certain realistic programs with more traditional implementations of these semantics. Furthermore, we provide a mechanism for using this technique through Ada implementations of two abstract data types where undefined variables respectively exhibit these two types of semantics, and whose implementations of these semantics use our technique. These abstract data types allow our technique to be selectively used in strictly those situations where the cost of the technique is justified. We provide practical examples illustrating these situations.
Longest‐match string searching for ziv‐lempel compression
Authors: Bell Timothy , Kulp David 
Published: November 2006

AbstractZiv‐Lempel coding is currently one of the more practical data compression schemes. It operates by replacing a substring of a text with a pointer to its longest previous occurrence in the input, for each coding step. Decoding a compressed file is very fast, but encoding involves searching at each coding step to find the longest match for the next few characters. This paper presents eight data structures that can be used to accelerate the searching, including adaptations of four methods normally used for exact matching searching. The algorithms are evaluated analytically and empirically, indicating the trade‐offs available between compression speed and memory consumption. Two of the algorithms are well‐known methods of finding the longest match—the time‐consuming linear search, and the storage‐intensive trie (digital search tree). The trie is adapted along the lines of a PATRICIA tree to operate economically. Hashing, binary search trees, splay trees and the Boyer‐Moore searching algorithm are traditionally used to search for exact matches, but we show how these can be adapted to find longest matches. In addition, two data structures specifically designed for the application are presented.
Aesthetic layout of generalized trees
Authors: Bloesch Anthony 
Published: November 2006

AbstractResearch on the aesthetic layout of trees has been largely concerned with the special case of binary trees with small constant‐sized nodes. Yet, without otherwise requiring the power of general graph‐layout algorithms, many layout problems involve n‐ary trees with variable‐sized nodes. This paper addresses the general issue of the aesthetic layout of such trees. Two algorithms are presented for the layout of generalized trees, and general issues, such as appropriate aesthetics, are discussed. The algorithms described are suitable for such tasks as the layout of class hierarchies, directory trees and tableau‐style proofs.
Pictures that play: Design notations for real‐time and distributed systems
Authors: Buhr R. J. A. 
Published: November 2006

Abstract‘Pictures that play’ are design diagrams that give enough visual cues to enable a person to trace causality sequences that cut across them, without referring to (or even knowing) the kind of details that would enable a tool to execute the design or to generate executable code. Playing design diagrams is particularly important while exploring alternative solutions during the early stages of designing all kinds of systems. It is done either by mentally tracing sequences across diagrams on paper or a computer screen, or physically tracing them on whiteboards with a pointer or finger during design meetings. Two complementary pictorial design notations are described and used together in an example to illustrate the concept of play and to show how to do it: timethreads, a new notation for causality sequences that cut across many components and across the system end‐to‐end, and machine charts, an older notation for architecture presented here from a new angle. These notations are specifically designed to support play during the design process, not just record the end result. The focus is on real‐time and distributed (RTD) systems, but the approach has wider applicability.
Compile‐time copy elimination
Authors: Schnorf Peter , Ganapathi Mahadevan , Hennessy John L. 
Published: November 2006

AbstractSingle‐assignment and functional languages have value semantics that do not permit side‐effects. This lack of side‐effects makes automatic detection of parallelism and optimization for data locality in programs much easier. However, the same property poses a challenge in implementing these languages efficiently. This paper describes an optimizing compiler system that solves the key problem of aggregate copy elimination. The methods developed rely exclusively on compile‐time algorithms, including interprocedural analysis, that are applied to an intermediate data flow representation. By dividing the problem into update‐in‐place and build‐in‐place analysis, a small set of relatively simple techniques—edge substitution, graph pattern matching, substructure sharing and substructure targeting—was found to be very powerful. If combined properly and implemented carefully, the algorithms eliminate unnecessary copy operations to a very high degree. No run‐time overhead is imposed on the compiled programs.
Interprocedural alias analysis: Implementation and empirical results
Authors: Mayer Herbert G. , Wolfe Michael 
Published: November 2006

AbstractWe report our experiences with the implementation of InterProcedural Alias Analysis (IPA) for Fortran. Implicit aliasing caused by reference parameter passing can be uncovered in a program with multiple compilation units by interprocedural analysis. For scalar objects and for full arrays, the IPA processor described here finds all alias relations. For indexed array elements and partial arrays, conservative assumptions must still be made in the absence of precise knowledge about the subscripts. IPA has been integrated into nascent, the front‐end of a Fortran translator under development at the Oregon Graduate Institute (OGI). This report explains the goals and limitations of alias analysis for conventional procedural languages with reference parameters, shows in detail the actual design and implementation of IPA, and provides algorithmic and speed improvements over the best previously known aliasing algorithms. Empirical results gathered during the analysis of large Fortran programs are also listed and discussed.