bluuebunny/crossref_metadata_2025_split huggingface dataset:
Experience compiling Fortran to program dependence graphs
Authors: Ottenstein Kar L. J. , Ellcey Steven J. 
Published: November 2006

AbstractThe program dependence graph (PDG) is being used in research projects for compilation to parallel architectures, program version integration and program semantics. This paper describes the methods used in a prototype Fortran‐to‐PDG translator called the PDG Testbed. Implementation decisions and details of the PDG Testbed project are described as a complement to the formal papers detailing the abstract PDG. In addition, experimental results are given that show the storage consumption for a PDG relative to a conventional internal representation as well as execution times for several analysis and optimization steps.
Optimizing stack frame accesses for processors with restricted addressing modes
Authors: Hartley David H. 
Published: November 2006

AbstractRandom access to local variables stored in a stack frame is more difficult for compiled functions when the target processor lacks register‐plus‐offset addressing. One alternative technique employs a roving pointer which the program increments or decrements as needed between stack accesses. Processors which support auto‐increment and auto‐decrement addressing modes are often capable of performing these increments for free when consecutive accesses are to adjacent stack locations. For these processors, the compiler's chosen ordering for the local variables in the stack frame can substantially affect the execution speed of the compiled program.This paper is concerned with finding an ordering for the local variables in the frame that maximizes the likelihood that two consecutive references at run‐time will be to the same or to adjacent stack locations. We have formulated a solution to this problem in terms of finding a Hamiltonian path in a graph. Although this problem is NP‐complete in general, we have developed a heuristic algorithm that delivers good results with acceptable performance.
Experience with Fagan's inspection method
Authors: Doolan E. P. 
Published: November 2006

AbstractFagan's inspection method was used by a software development group to validate requirements specifications for software functions. The experiences of that group are described in this paper. In general, they have proved to be favourable. Because the costs of fixing errors in software were known, the payback for every hour invested in inspection was shown to be a factor 30. There are also other benefits that are much more difficult to quantify directly but whose effect is significant in terms of the overall quality of the software.Some pointers are given at the end of this paper for those who want to introduce Fagan's inspection method into their own development environment.
The practical integration of manufacturing applications
Authors: Busby J. S. , Hutchison D. 
Published: November 2006

AbstractThe need to integrate the operation of computer applications is becoming an increasingly prominent issue in industrial firms. Mechanisms have to be developed to allow these systems to share the information they generate and use—to ensure that elements of data with a common meaning, in different systems, have consistent values. The applications are normally proprietary packages, of widely varying types, usually selected for their effectiveness as free‐standing systems; they cannot as a result be modified to any appreciable extent during integration. An approach to integration that is based on the distributed updates of complex objects just before use is described in this paper.The implementation provides a transportation service that moves information from one location to another, and a transcription service that transforms objects from their native formats in one application to those comprehensible in another. Transcription is based on using an intermediate neutral data model—independent of data formats in particular applications. The transport facilities are modelled satisfactorily in a process‐oriented notation such as CSP, whereas the transcription operations are modelled better with a set‐based notation such as Z. These specifications have been implemented primarily using Unix communication mechanisms and a proprietary relational database management system.
The design and implementation of a grammar‐based data generator
Authors: Maurer Peter M. 
Published: November 2006

AbstractDGL is a context‐free grammar‐based language for generating test data. Although many of the features of DGL are implemented in a straighforward way, the implementation of several of the most important features is neither trivial nor obvious. Before one can understand the implementation of these features, however, it is necessary to understand the overall structure of the compiler and its output, which was designed to be flexible enough to incorporate new features easily. Variables and chains are two of the most important features of DGL, and also two of the trickiest features to implement. The run‐time dictionaires, which are built into the C code generated by the compiler, are implemented as pure code rather than as table‐look‐up routines. The compiler itself is reasonably straightforward, except for the expansion of character sets and compile‐time macros. These two features can cause the ‘multi‐dimensional’ expansion of a string, the implementation of which must be carefully designed.
Profile‐guided automatic inline expansion for C programs
Authors: Chang Pohua P. , Mahlke Scott A. , Chen William Y. , Hwu Wen‐Mei W. 
Published: November 2006

AbstractThis paper describes critical implementation issues that must be addressed to develop a fully automatic inliner. These issues are: integration into a compiler, program representation, hazard prevention, expansion sequence control, and program modification. An automatic inter‐file inliner that uses profile information has been implemented and integrated into an optimizing C compiler. The experimental results show that this inliner achieves significant speedups for production C programs.
Tuning a parallel database algorithm on a shared‐memory multiprocessor
Authors: Graefe Goetz , Thakkar Shreekant S. 
Published: November 2006

AbstractDatabase query processing can benefit significantly from parallelism. Parallel database algorithms combine substantial CPU and I/O activity, memory requirements, and massive data exchange between processes, all of which must be considered to obtain optimal performance. Since parallel external sorting is a very typical example, we have focused on sorting to tune Volcano, a new query processing system. The purpose of the Volcano project is to provide efficient, extensible tools for query and request processing in novel application domains, particularly in object‐oriented and scientific database systems, and for experimental database performance research. It includes all query processing algorithms conventionally used in relational database systems as well as several new ones, and can execute all of them in parallel. In this article, we present Volcano's parallel external sorting algorithm and a sequence of enhancements to improve its performance. We obtained very good absolute performance, 84 seconds for 100 MB of data, as well as near‐linear speedup with sixteen CPUs and disks. Furthermore, these results were achieved on a shared‐memory machine despite the common belief that parallel query processing is best implemented on distributed‐memory systems. We detail our tuning measures and report on their effectiveness.
Extension table built‐ins for prolog
Authors: Fan Changguan , Dietrich Suzanne Wagner 
Published: November 2006

AbstractThe ET* algorithm is a complete evaluation strategy for Datalog programs, which are logic programs without function symbols. The ET* algorithm uses extension tables and depth‐first iterative deepening to provide the evaluation of pure function‐free logic programs as declarative specifications. Extension tables are a memo facility that the algorithm uses both to cut infinite derivation paths for complete evaluation and to optimise the evaluation of logic programs.The original implementation of the ET* algorithm incorporated extension tables as part of the Prolog database using the built‐in predicates assert and retract. The advantage of implementing the extension table using the Prolog database is the portability of the ET* algorithm. There are several disadvantages, however, with this approach. One disadvantage is the cost associated with the built‐in predicates assert and retract, which are known to be expensive operations in most current Prolog systems. Another disadvantage is the differences across implementations in the semantics that these built‐ins provide for dynamic predicates. This paper presents an efficient implementation of extension tables as a global data structure in Prolog, which includes a set of built‐in primitives for manipulating the extension table. The ET* algorithm is updated to reflect the utilisation of the global extension table data structure. The implementations of the ET* algorithm are compared using time and space performance on a variety of benchmark programs.
An efficient implementation of trie structures
Authors: Aoe Jun‐Ichi , Morimoto Katsushi , Sato Takashi 
Published: November 2006

AbstractA new internal array structure, called a double‐array, implementing a trie structure is presented. The double‐array combines the fast access of a matrix form with the compactness of a list form. The algorithms for retrieval, insertion and deletion are introduced through examples. Although insertion is rather slow, it is still practical, and both the deletion and the retrieval time can be improved from the list form. From the comparison with the list for various large sets of keys, it is shown that the size of the double‐array can be about 17 per cent smaller than that of the list, and that the retrieval speed of the double‐array can be from 3–1 to 5–1 times faster than that of the list.
Incrementally maintained network→relational database mapping
Authors: Mark Leo , Roussopoulos Nick , Newsome Tina , Laohapipattana Piriya 
Published: November 2006

AbstractAn incrementally maintained mapping from a network to a relational database is presented. This mapping may be established either to support the efficient retrieval of data from a network database through a relational interface, or as the first step in a gradual conversion of data and applications from a network to a relational database system. After the mapping has been established, the only data mapped from the network to the relational database are the increments resulting from updates on the network database. The mapping is therefore an efficient alternative to mappings that repeatedly map the results of retrievals through the relational interface from the network database to the relational database. This is in particular the case when the two databases reside on different hosts. Applications on the network database may, under certain restrictions, gradually be moved to the relational database, while the mapping incrementally maintains the relational database for the applications that remain on the network database.A detailed, but generic, account of how to build such a mapping from a network to a relational database is given, including all the algorithms needed and examples of their use.
Designing and implementing multi‐user applications: A case study
Authors: Dewan Prasun 
Published: November 2006

AbstractWe have developed a new multi‐user application that integrates and extends the concepts in a variety of current multi‐user applications. It allows multiple users to store, retrieve and browse through information, communicate information both synchronously and asynchronously, create ‘pipes’ of consistent, editable and persistent views, and interactively specify handlers for events. It has been implemented using the experimental technologies of distributed objects and multi‐user editor generation. Our work on this application suggests a new and practical model for designing and implementing multi‐user applications. In this paper, we describe the user interface and implementation of the application, give the rationale for our design choices, describe our experience with the tools and techniques used in the implementation, and present conclusions and directions for future work.
High‐level management of computation history for the design and implementation of a prolog system
Authors: Loia Vincenzo , Quaggetto Michel 
Published: November 2006

AbstractWe present the implementation of a Prolog system composed of interpreter and compiler. The originality of our work consists in the adoption of a new framework to realize the main components of the system. The framework relies on new mechanisms, called sleepers. With their help we have developed a complete Prolog interpreter in which all the control activities, from backtracking up to last‐call optimization, are performed by the sleeper mechanism. We have also produced a Prolog compiler by using a philosophy and tactics that are completely independent of hardware constraints; it exploits an incremental and abstract implementation technique, based on a delayed non‐local execution protocol. Our approach to Prolog system implementation has been extremely useful both in terms of software design and overall performance.
Iconic control graph representation
Authors: Robillard Pierre N. , Simoneau Mario 
Published: November 2006

AbstractThis paper presents a new representation of control flow graphs which is readable and concise, keeping all pertinent information as it appears in the source code. The iconic control graph provides an exact transformation of the source code. It is a basis for control flow visualization, unstructuredness identification, path crossing and path computation. The representation is programming‐language independent. The iconic control flow construction is automated.
Query by diagram: A visual environment for querying databases
Authors: Santucci Giuseppe , Sottile Pier Angelo 
Published: November 2006

AbstractIn recent years, several attempts have been made to define query languages characterized by both high expressive power and easy query formulation. Several issues concern graphical applications, based on the diagrammatic representation of a semantic model and visual interaction. This paper describes the architecture and the implementation of a graphical query system, based on the diagrammatic representation of entity relationship schemata. The query language underlying the system allows the formulation of recursive queries; moreover, user interaction in both managing diagrams and expressing queries is simplified by the presence of a fully visual environment and a rich set of interaction strategies.
An implementation of precompiled headers
Authors: Litman Andy 
Published: November 2006

AbstractCompilation time can be improved by precompiling interfaces so that the compiler can avoid processing unreferenced declarations. However, in C‐based languages precompiling a header is difficult because a header can have several meanings depending on the context in which it is included. We present anad hocsolution to this problem, and give the results of our precompilation strategy, which improved compile times by 25 to 65 per cent over compilation without precompiled headers.
Construction of an interactive programming environment for control of theatrical‐set effects via object‐oriented methods
Authors: Thirion Bernard 
Published: November 2006

AbstractThis paper describes the object‐oriented design of a novel application, for control of complex theatricalset effects defined by an appropriate language. Besides giving a general description of the proposed system, the paper presents the language and its programming environment, which is intended for inexperienced users and integrates facilities to create, edit, check and run the effect scripts. The description of the implementation demonstrates the relevance of an object‐oriented approach when it is associated with compiler techniques. The object paradigm is used to build support classes such as character streams, run‐time values or symbols as well as syntactic objects. Each syntactic‐object class models a different LL(1) grammar non‐terminal and allows for an object‐oriented predictive parsing. Moreover, organizing the instances of these classes as an object‐based parse tree simplifies parsing, unparsing, syntax‐directed editing, syntax‐directed help, interpretation, etc. The description of these various operations shows the flexibility of our method, e.g. with respect to an iterative prototyping of the language and its environment.
The duality of fault‐tolerant system structures
Authors: Shrivastava Santosh K. , Mancini Luigi V. , Randell Brian 
Published: November 2006

AbstractAn examination of the structure of fault‐tolerant systems incorporating backward error recovery indicates a partitioning into two broad classes. Two canonical models, each representing a particular class of systems, have been constructed. The first model incorporates objects and actions as the entities for program construction whereas the second model employs communicating processes and conversations. Applications in areas such as office information and banking systems are typically described and built in terms of the first model whereas applications in the area of process control are usually described and built in terms of the second model. The paper claims that the two models are duals of each other and presents arguments and examples to substantiate this claim. It will be shown that the techniques that have been developed within the context of one model turn out to have interesting and hitherto unexplored duals in the other model.
A method for fast tape backups and restores
Authors: Drizis Leonidas 
Published: November 2006

AbstractThis paper describes a method for fast backups and restores on tape drives. By using a tight synchronization between disk and tape accesses, the total throughput can be accelerated by a factor ranging from 30 to 100 per cent. The method imposes no special requirements on an operating system; only a timer with a resolution better than one fiftieth of a second is needed. Further, it can be used with virtually all types of streaming tapes and backup data formats.
ISA [k] trees: A class of binary search trees with minimal or near minimal internal path length
Authors: Abuali Faris N. , Wainwright Roger L. 
Published: November 2006

AbstractIn recent years several authors have investigated binary search trees with minimal internal path length. In this paper we propose relaxing the requirement of inserting all nodes on one level before going to the next level. This leads to a new class of binary search trees called ISA [k] trees. We investigated the average locate cost per node, average shift cost per node, total insertion cost, and average successful search cost for ISA[k] trees. We also present an insertion algorithm with associated predecessor and successor functions for ISA[k] trees. For large binary search trees (over 160 nodes) our results suggest the use of ISA[2] or ISA[3] trees for best performance.
Utopia: A load sharing facility for large, heterogeneous distributed computer systems
Authors: Zhou Songnian , Zheng Xiaohu , Wang Jingwen , Delisle Pierre 
Published: November 2006

AbstractLoad sharing in large, heterogeneous distributed systems allows users to access vast amounts of computing resources scattered around the system and may provide substantial performance improvements to applications. We discuss the design and implementation issues in Utopia, a load sharing facility specifically built for large and heterogeneous systems. The system has no restriction on the types of tasks that can be remotely executed, involves few application changes and no operating system change, supports a high degree of transparency for remote task execution, and incurs low overhead. The algorithms for managing resource load information and task placement take advantage of the clustering nature of large‐scale distributed systems; centralized algorithms are used within host clusters, and directed graph algorithms are used among the clusters to make Utopia scalable to thousands of hosts. Task placements in Utopia exploit the heterogeneous hosts and consider varying resource demands of the tasks. A range of mechanisms for remote execution is available in Utopia that provides varying degrees of transparency and efficiency.A number of applications have been developed for Utopia, ranging from a load sharing command interpreter, to parallel and distributed applications, to a distributed batch facility. For example, an enhanced Unix command interpreter allows arbitrary commands and user jobs to be executed remotely, and a parallel make facility achieves speed‐ups of 15 or more by processing a collection of tasks in parallel on a number of hosts.
A faster scrabble move generation algorithm
Authors: Gordon Steven A. 
Published: November 2006

AbstractAppel and Jacobson1 presented a fast algorithm for generating every possible move in a given position in the game of Scrabble using a DAWG, a finite automaton derived from the trie of a large lexicon. This paper presents a faster algorithm that uses a GADDAG, a finite automaton that avoids the non‐deterministic prefix generation of the DAWG algorithm by encoding a bidirectional path starting from each letter of each word in the lexicon. For a typical lexicon, the GADDAG is nearly five times larger than the DAWG, but generates moves more than twice as fast. This time/space trade‐off is justified not only by the decreasing cost of computer memory, but also by the extensive use of move‐generation in the analysis of board positions used by Gordon2 in the probabilistic search for the most appropriate play in a given position within realistic time constraints.
Implementations and performances of two RPC‐based LAN gateway applications
Authors: Yasrebi Mehrad 
Published: November 2006

AbstractA predominant (‘base’) scheme currently used in many circuit‐switched LAN‐WAN gateway applications is based on device‐driver LAN redirections. Various functional and performance deficiencies associated with the LAN redirection (base) scheme and an RPC programming interface are described. This RPC definition supports the base scheme, as well as another (‘enhanced’) scheme. The enhanced scheme overcomes the various outlined functional deficiencies associated with the cited implementations of the base scheme. Implementations of these two client‐server application schemes on top of the IEEE portable operating‐system interface and the Open Software Foundation RPC are described for both schemes. Performances of these two schemes are compared, both based on a simplified Markov chain model and on actual implementations and long‐duration experiments. Some of the similarities between the predictive simple‐model behaviors and the actual experienced results for the applications are encouraging. This experience shows that the described RPC programming interface is a reasonable candidate for immediate practical implementations on heterogeneous systems.